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 constexpr 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 constexpr 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