1 // Copyright 2015 Google Inc. 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
44 #if defined ANDROID || defined __ANDROID__
45 #include <android/api-level.h>
46 #if __ANDROID_API__ < 16
47 #include <malloc.h>
48 #define GEMMLOWP_USE_MEMALIGN
49 #endif
50 #endif
51
52 namespace gemmlowp {
53
54 enum class TypeId : std::uint8_t { Uint8, Int8, Uint16, Int16, Uint32, Int32 };
55
56 template <typename T>
57 struct GetTypeIdImpl {};
58
59 template <typename T>
GetTypeId()60 inline TypeId GetTypeId() {
61 return GetTypeIdImpl<T>::Value;
62 }
63
64 template <typename T>
65 struct GetTypeIdImpl<const T> : GetTypeIdImpl<T> {};
66
67 #define GEMMLOWP_REGISTER_TYPEID(type_, id) \
68 template <> \
69 struct GetTypeIdImpl<type_> { \
70 static const TypeId Value = TypeId::id; \
71 };
72
73 GEMMLOWP_REGISTER_TYPEID(std::uint8_t, Uint8)
74 GEMMLOWP_REGISTER_TYPEID(std::int8_t, Int8)
75 GEMMLOWP_REGISTER_TYPEID(std::uint16_t, Uint16)
76 GEMMLOWP_REGISTER_TYPEID(std::int16_t, Int16)
77 GEMMLOWP_REGISTER_TYPEID(std::uint32_t, Uint32)
78 GEMMLOWP_REGISTER_TYPEID(std::int32_t, Int32)
79
80 class Allocator {
81 public:
82 Allocator()
83 : committed_(false),
84 storage_size_(0),
85 storage_(nullptr),
86 reserved_blocks_(0),
87 reserved_bytes_(0),
88 generation_(0) {}
89
90 ~Allocator() {
91 assert(!committed_);
92 assert(!reserved_blocks_);
93 DeallocateStorage();
94 }
95
96 // Alignment of allocated blocks.
97 static const std::size_t kAlignment = kDefaultCacheLineSize;
98
99 // This is all we need so far, and since the usage pattern is fixed,
100 // there is no point in allowing more until we need to.
101 static const std::size_t kMaxBlocks = 5;
102
103 void Commit() {
104 assert(!committed_);
105
106 if (reserved_bytes_ > storage_size_) {
107 DeallocateStorage();
108 storage_size_ = RoundUpToPowerOfTwo(reserved_bytes_);
109 #ifdef GEMMLOWP_USE_MEMALIGN
110 storage_ = memalign(kAlignment, storage_size_);
111 #else
112 if (posix_memalign(&storage_, kAlignment, storage_size_)) {
113 storage_ = nullptr;
114 }
115 #endif
116 }
117
118 ReleaseBuildAssertion(!storage_size_ || storage_, "allocation failure");
119 committed_ = true;
120 }
121
122 void Decommit() {
123 assert(committed_);
124 committed_ = false;
125 generation_++;
126
127 reserved_blocks_ = 0;
128 reserved_bytes_ = 0;
129 }
130
131 // See generation_
132 typedef std::size_t generation_t;
133
134 // A handle on a reserved block. The user obtains
135 // one by calling Reserve() and, after committing,
136 // passes it to GetPointer().
137 class Handle {
138 std::uint8_t index_;
139 generation_t generation_;
140 TypeId type_;
141
142 friend class Allocator;
143 };
144
145 // Reserves a block sized for n elements of type T, and
146 // returns a handle to it. Must be called before committing.
147 template <typename T>
148 Handle Reserve(std::size_t n) {
149 assert(!committed_ && "can't reserve blocks while committed");
150 assert(reserved_blocks_ < kMaxBlocks &&
151 "didn't expect to allocate this many blocks");
152 const std::size_t bytes = RoundUp<kAlignment>(n * sizeof(T));
153 const std::size_t offset = reserved_bytes_;
154 const std::size_t index = reserved_blocks_;
155
156 reserved_blocks_offsets_[index] = offset;
157 Handle h;
158 h.index_ = index;
159 h.generation_ = generation_;
160 h.type_ = GetTypeId<T>();
161
162 reserved_blocks_++;
163 reserved_bytes_ += bytes;
164
165 return h;
166 }
167
168 // Returns the pointer to the allocated buffer for the given handle.
169 // Must be called after committing.
170 template <typename T>
171 T* GetPointer(const Handle& h) const {
172 assert(committed_ && "can't get block pointers unless committed");
173 assert(h.index_ < reserved_blocks_ &&
174 "bad handle, points to inexistant block");
175 assert(h.generation_ == generation_ &&
176 "handle from earlier generation, have decommitted since");
177 assert(h.type_ == GetTypeId<T>() && "type mismatch");
178 std::size_t offset = reserved_blocks_offsets_[h.index_];
179 std::uintptr_t addr = reinterpret_cast<std::uintptr_t>(storage_) + offset;
180 return reinterpret_cast<T*>(addr);
181 }
182
183 private:
184 void DeallocateStorage() {
185 assert(!committed_);
186 free(storage_);
187 storage_size_ = 0;
188 }
189
190 // Set to true by Commit() and to false by Decommit(). Initially false.
191 bool committed_;
192
193 // The actually allocated storage size and buffer pointer.
194 std::size_t storage_size_;
195 mutable void* storage_;
196
197 // The number of blocks that have been reserved by Reserve().
198 std::size_t reserved_blocks_;
199 // The number of bytes that have been reserved by Reserve().
200 std::size_t reserved_bytes_;
201 // The offsets of reserved blocks into the storage buffer.
202 std::size_t reserved_blocks_offsets_[kMaxBlocks];
203
204 // The 'generation' is incremented on Decommit() and allows catching
205 // bad GetPointer() calls still referring to a previous commit.
206 generation_t generation_;
207 };
208
209 } // namespace gemmlowp
210
211 #endif // GEMMLOWP_INTERNAL_ALLOCATOR_H_
212