1// Copyright 2015 The Gemmlowp Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// allocator.h: a buffer allocator that allows avoiding most of the
16// malloc/free overhead, by:
17// 1. Requiring all N allocations to be reserved in advance, and
18//    then commited at once, turning N allocations into 1.
19// 2. Being persistent, the allocated storage is reused across commits,
20//    and only reallocated as needed when the commit size gets larger.
21//
22// This is driven by Android-specific needs:
23// 1. On Android, the default (Bionic) allocator tends to aggressively
24// unmap pages, which means that malloc/free can be surprisingly expensive.
25// 2. On Android, stack allocations with alloca() can't be as large as on
26// desktop platforms.
27//
28// General usage:
29// 1. Reserve blocks by calling Reserve(), which returns a Handle.
30// 2. Call Commit() once.
31// 3. Now it is possible to get pointers to allocated buffers by calling
32//    GetPointer().
33// 4. Call Decommit() once.
34// 5. The allocator is now reverted to its original state, except that
35//    it retained its allocated storage, so the next Commit() will be faster.
36//    The allocated storage is only freed when the Allocator object is
37//    destroyed.
38
39#ifndef GEMMLOWP_INTERNAL_ALLOCATOR_H_
40#define GEMMLOWP_INTERNAL_ALLOCATOR_H_
41
42#include "common.h"
43
44namespace gemmlowp {
45
46enum class TypeId : std::uint8_t { Uint8, Int8, Uint16, Int16, Uint32, Int32 };
47
48template <typename T>
49struct GetTypeIdImpl {};
50
51template <typename T>
52inline TypeId GetTypeId() {
53  return GetTypeIdImpl<T>::Value;
54}
55
56template <typename T>
57struct GetTypeIdImpl<const T> : GetTypeIdImpl<T> {};
58
59#define GEMMLOWP_REGISTER_TYPEID(type_, id) \
60  template <>                               \
61  struct GetTypeIdImpl<type_> {             \
62    static const TypeId Value = TypeId::id; \
63  };
64
65GEMMLOWP_REGISTER_TYPEID(std::uint8_t, Uint8)
66GEMMLOWP_REGISTER_TYPEID(std::int8_t, Int8)
67GEMMLOWP_REGISTER_TYPEID(std::uint16_t, Uint16)
68GEMMLOWP_REGISTER_TYPEID(std::int16_t, Int16)
69GEMMLOWP_REGISTER_TYPEID(std::uint32_t, Uint32)
70GEMMLOWP_REGISTER_TYPEID(std::int32_t, Int32)
71
72class Allocator {
73 public:
74  Allocator()
75      : committed_(false),
76        storage_size_(0),
77        storage_(nullptr),
78        reserved_blocks_(0),
79        reserved_bytes_(0),
80        generation_(0) {}
81
82  ~Allocator() {
83    assert(!committed_);
84    assert(!reserved_blocks_);
85    DeallocateStorage();
86  }
87
88  // Alignment of allocated blocks.
89  static const std::size_t kAlignment = kDefaultCacheLineSize;
90
91  // This is all we need so far, and since the usage pattern is fixed,
92  // there is no point in allowing more until we need to.
93  static const std::size_t kMaxBlocks = 5;
94
95  void Commit() {
96    assert(!committed_);
97
98    if (reserved_bytes_ > storage_size_) {
99      DeallocateStorage();
100      storage_size_ = RoundUpToPowerOfTwo(reserved_bytes_);
101      storage_ = aligned_alloc(kAlignment, storage_size_);
102    }
103
104    ReleaseBuildAssertion(!storage_size_ || storage_, "allocation failure");
105    committed_ = true;
106  }
107
108  void Decommit() {
109    assert(committed_);
110    committed_ = false;
111    generation_++;
112
113    reserved_blocks_ = 0;
114    reserved_bytes_ = 0;
115  }
116
117  // See generation_
118  typedef std::size_t generation_t;
119
120  // A handle on a reserved block. The user obtains
121  // one by calling Reserve() and, after committing,
122  // passes it to GetPointer().
123  class Handle {
124    std::uint8_t index_;
125    generation_t generation_;
126    TypeId type_;
127
128    friend class Allocator;
129  };
130
131  // Reserves a block sized for n elements of type T, and
132  // returns a handle to it. Must be called before committing.
133  template <typename T>
134  Handle Reserve(std::size_t n) {
135    assert(!committed_ && "can't reserve blocks while committed");
136    assert(reserved_blocks_ < kMaxBlocks &&
137           "didn't expect to allocate this many blocks");
138    const std::size_t bytes = RoundUp<kAlignment>(n * sizeof(T));
139    const std::size_t offset = reserved_bytes_;
140    const std::size_t index = reserved_blocks_;
141
142    reserved_blocks_offsets_[index] = offset;
143    Handle h;
144    h.index_ = index;
145    h.generation_ = generation_;
146    h.type_ = GetTypeId<T>();
147
148    reserved_blocks_++;
149    reserved_bytes_ += bytes;
150
151    return h;
152  }
153
154  // Returns the pointer to the allocated buffer for the given handle.
155  // Must be called after committing.
156  template <typename T>
157  T* GetPointer(const Handle& h) const {
158    assert(committed_ && "can't get block pointers unless committed");
159    assert(h.index_ < reserved_blocks_ &&
160           "bad handle, points to inexistant block");
161    assert(h.generation_ == generation_ &&
162           "handle from earlier generation, have decommitted since");
163    assert(h.type_ == GetTypeId<T>() && "type mismatch");
164    std::size_t offset = reserved_blocks_offsets_[h.index_];
165    std::uintptr_t addr = reinterpret_cast<std::uintptr_t>(storage_) + offset;
166    return reinterpret_cast<T*>(addr);
167  }
168
169 private:
170  void DeallocateStorage() {
171    assert(!committed_);
172    aligned_free(storage_);
173    storage_size_ = 0;
174  }
175
176  // Set to true by Commit() and to false by Decommit(). Initially false.
177  bool committed_;
178
179  // The actually allocated storage size and buffer pointer.
180  std::size_t storage_size_;
181  mutable void* storage_;
182
183  // The number of blocks that have been reserved by Reserve().
184  std::size_t reserved_blocks_;
185  // The number of bytes that have been reserved by Reserve().
186  std::size_t reserved_bytes_;
187  // The offsets of reserved blocks into the storage buffer.
188  std::size_t reserved_blocks_offsets_[kMaxBlocks];
189
190  // The 'generation' is incremented on Decommit() and allows catching
191  // bad GetPointer() calls still referring to a previous commit.
192  generation_t generation_;
193};
194
195}  // namespace gemmlowp
196
197#endif  // GEMMLOWP_INTERNAL_ALLOCATOR_H_
198