1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 // Header page:
18 //
19 // For minimum allocation size (8 bytes), bitmap can store used allocations for
20 // up to 4032*8*8=258048, which is 256KiB minus the header page
21
22 #include <assert.h>
23 #include <stdlib.h>
24
25 #include <sys/cdefs.h>
26 #include <sys/mman.h>
27
28 #include <cmath>
29 #include <cstddef>
30 #include <cstdint>
31 #include <memory>
32 #include <mutex>
33
34 #include "android-base/macros.h"
35
36 #include "anon_vma_naming.h"
37 #include "Allocator.h"
38 #include "LinkedList.h"
39
40 // runtime interfaces used:
41 // abort
42 // assert - fprintf + mmap
43 // mmap
44 // munmap
45 // prctl
46
const_log2(size_t n,size_t p=0)47 constexpr size_t const_log2(size_t n, size_t p = 0) {
48 return (n <= 1) ? p : const_log2(n / 2, p + 1);
49 }
50
div_round_up(unsigned int x,unsigned int y)51 constexpr unsigned int div_round_up(unsigned int x, unsigned int y) {
52 return (x + y - 1) / y;
53 }
54
55 #define ARRAY_SIZE(x) (sizeof(x)/sizeof((x)[0]))
56
57 static constexpr size_t kPageSize = 4096;
58 static constexpr size_t kChunkSize = 256 * 1024;
59 static constexpr size_t kUsableChunkSize = kChunkSize - kPageSize;
60 static constexpr size_t kMaxBucketAllocationSize = kChunkSize / 4;
61 static constexpr size_t kMinBucketAllocationSize = 8;
62 static constexpr unsigned int kNumBuckets = const_log2(kMaxBucketAllocationSize)
63 - const_log2(kMinBucketAllocationSize) + 1;
64 static constexpr unsigned int kUsablePagesPerChunk = kUsableChunkSize
65 / kPageSize;
66
67 std::atomic<int> heap_count;
68
69 class Chunk;
70
71 class HeapImpl {
72 public:
73 HeapImpl();
74 ~HeapImpl();
75 void* operator new(std::size_t count) noexcept;
76 void operator delete(void* ptr);
77
78 void* Alloc(size_t size);
79 void Free(void* ptr);
80 bool Empty();
81
82 void MoveToFullList(Chunk* chunk, int bucket_);
83 void MoveToFreeList(Chunk* chunk, int bucket_);
84
85 private:
86 DISALLOW_COPY_AND_ASSIGN(HeapImpl);
87
88 LinkedList<Chunk*> free_chunks_[kNumBuckets];
89 LinkedList<Chunk*> full_chunks_[kNumBuckets];
90
91 void MoveToList(Chunk* chunk, LinkedList<Chunk*>* head);
92 void* MapAlloc(size_t size);
93 void MapFree(void* ptr);
94 void* AllocLocked(size_t size);
95 void FreeLocked(void* ptr);
96
97 struct MapAllocation {
98 void *ptr;
99 size_t size;
100 MapAllocation* next;
101 };
102 MapAllocation* map_allocation_list_;
103 std::mutex m_;
104 };
105
106 // Integer log 2, rounds down
log2(size_t n)107 static inline unsigned int log2(size_t n) {
108 return 8 * sizeof(unsigned long long) - __builtin_clzll(n) - 1;
109 }
110
size_to_bucket(size_t size)111 static inline unsigned int size_to_bucket(size_t size) {
112 if (size < kMinBucketAllocationSize)
113 return kMinBucketAllocationSize;
114 return log2(size - 1) + 1 - const_log2(kMinBucketAllocationSize);
115 }
116
bucket_to_size(unsigned int bucket)117 static inline size_t bucket_to_size(unsigned int bucket) {
118 return kMinBucketAllocationSize << bucket;
119 }
120
MapAligned(size_t size,size_t align)121 static void* MapAligned(size_t size, size_t align) {
122 const int prot = PROT_READ | PROT_WRITE;
123 const int flags = MAP_ANONYMOUS | MAP_PRIVATE;
124
125 size = (size + kPageSize - 1) & ~(kPageSize - 1);
126
127 // Over-allocate enough to align
128 size_t map_size = size + align - kPageSize;
129 if (map_size < size) {
130 return nullptr;
131 }
132
133 void* ptr = mmap(NULL, map_size, prot, flags, -1, 0);
134 if (ptr == MAP_FAILED) {
135 return nullptr;
136 }
137
138 size_t aligned_size = map_size;
139 void* aligned_ptr = ptr;
140
141 std::align(align, size, aligned_ptr, aligned_size);
142
143 // Trim beginning
144 if (aligned_ptr != ptr) {
145 ptrdiff_t extra = reinterpret_cast<uintptr_t>(aligned_ptr)
146 - reinterpret_cast<uintptr_t>(ptr);
147 munmap(ptr, extra);
148 map_size -= extra;
149 ptr = aligned_ptr;
150 }
151
152 // Trim end
153 if (map_size != size) {
154 assert(map_size > size);
155 assert(ptr != NULL);
156 munmap(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(ptr) + size),
157 map_size - size);
158 }
159
160 #define PR_SET_VMA 0x53564d41
161 #define PR_SET_VMA_ANON_NAME 0
162 prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME,
163 reinterpret_cast<uintptr_t>(ptr), size, "leak_detector_malloc");
164
165 return ptr;
166 }
167
168 class Chunk {
169 public:
170 static void* operator new(std::size_t count) noexcept;
171 static void operator delete(void* ptr);
172 Chunk(HeapImpl* heap, int bucket);
~Chunk()173 ~Chunk() {}
174
175 void *Alloc();
176 void Free(void* ptr);
177 void Purge();
178 bool Empty();
179
ptr_to_chunk(void * ptr)180 static Chunk* ptr_to_chunk(void* ptr) {
181 return reinterpret_cast<Chunk*>(reinterpret_cast<uintptr_t>(ptr)
182 & ~(kChunkSize - 1));
183 }
is_chunk(void * ptr)184 static bool is_chunk(void* ptr) {
185 return (reinterpret_cast<uintptr_t>(ptr) & (kChunkSize - 1)) != 0;
186 }
187
free_count()188 unsigned int free_count() {
189 return free_count_;
190 }
heap()191 HeapImpl* heap() {
192 return heap_;
193 }
194 LinkedList<Chunk*> node_; // linked list sorted by minimum free count
195
196 private:
197 DISALLOW_COPY_AND_ASSIGN(Chunk);
198 HeapImpl* heap_;
199 unsigned int bucket_;
200 unsigned int allocation_size_; // size of allocations in chunk, min 8 bytes
201 unsigned int max_allocations_; // maximum number of allocations in the chunk
202 unsigned int first_free_bitmap_; // index into bitmap for first non-full entry
203 unsigned int free_count_; // number of available allocations
204 unsigned int frees_since_purge_; // number of calls to Free since last Purge
205
206 // bitmap of pages that have been dirtied
207 uint32_t dirty_pages_[div_round_up(kUsablePagesPerChunk, 32)];
208
209 // bitmap of free allocations.
210 uint32_t free_bitmap_[kUsableChunkSize / kMinBucketAllocationSize / 32];
211
212 char data_[0];
213
ptr_to_n(void * ptr)214 unsigned int ptr_to_n(void* ptr) {
215 ptrdiff_t offset = reinterpret_cast<uintptr_t>(ptr)
216 - reinterpret_cast<uintptr_t>(data_);
217 return offset / allocation_size_;
218 }
n_to_ptr(unsigned int n)219 void* n_to_ptr(unsigned int n) {
220 return data_ + n * allocation_size_;
221 }
222 };
223 static_assert(sizeof(Chunk) <= kPageSize, "header must fit in page");
224
225 // Override new operator on chunk to use mmap to allocate kChunkSize
operator new(std::size_t count)226 void* Chunk::operator new(std::size_t count __attribute__((unused))) noexcept {
227 assert(count == sizeof(Chunk));
228 void* mem = MapAligned(kChunkSize, kChunkSize);
229 if (!mem) {
230 abort(); //throw std::bad_alloc;
231 }
232
233 return mem;
234 }
235
236 // Override new operator on chunk to use mmap to allocate kChunkSize
operator delete(void * ptr)237 void Chunk::operator delete(void *ptr) {
238 assert(reinterpret_cast<Chunk*>(ptr) == ptr_to_chunk(ptr));
239 munmap(ptr, kChunkSize);
240 }
241
Chunk(HeapImpl * heap,int bucket)242 Chunk::Chunk(HeapImpl* heap, int bucket) :
243 node_(this), heap_(heap), bucket_(bucket), allocation_size_(
244 bucket_to_size(bucket)), max_allocations_(
245 kUsableChunkSize / allocation_size_), first_free_bitmap_(0), free_count_(
246 max_allocations_), frees_since_purge_(0) {
247 memset(dirty_pages_, 0, sizeof(dirty_pages_));
248 memset(free_bitmap_, 0xff, sizeof(free_bitmap_));
249 }
250
Empty()251 bool Chunk::Empty() {
252 return free_count_ == max_allocations_;
253 }
254
Alloc()255 void* Chunk::Alloc() {
256 assert(free_count_ > 0);
257
258 unsigned int i = first_free_bitmap_;
259 while (free_bitmap_[i] == 0)
260 i++;
261 assert(i < ARRAY_SIZE(free_bitmap_));
262 unsigned int bit = __builtin_ffs(free_bitmap_[i]) - 1;
263 assert(free_bitmap_[i] & (1U << bit));
264 free_bitmap_[i] &= ~(1U << bit);
265 unsigned int n = i * 32 + bit;
266 assert(n < max_allocations_);
267
268 unsigned int page = n * allocation_size_ / kPageSize;
269 assert(page / 32 < ARRAY_SIZE(dirty_pages_));
270 dirty_pages_[page / 32] |= 1U << (page % 32);
271
272 free_count_--;
273 if (free_count_ == 0) {
274 heap_->MoveToFullList(this, bucket_);
275 }
276
277 return n_to_ptr(n);
278 }
279
Free(void * ptr)280 void Chunk::Free(void* ptr) {
281 assert(is_chunk(ptr));
282 assert(ptr_to_chunk(ptr) == this);
283
284 unsigned int n = ptr_to_n(ptr);
285 unsigned int i = n / 32;
286 unsigned int bit = n % 32;
287
288 assert(i < ARRAY_SIZE(free_bitmap_));
289 assert(!(free_bitmap_[i] & (1U << bit)));
290 free_bitmap_[i] |= 1U << bit;
291 free_count_++;
292
293 if (i < first_free_bitmap_) {
294 first_free_bitmap_ = i;
295 }
296
297 if (free_count_ == 1) {
298 heap_->MoveToFreeList(this, bucket_);
299 } else {
300 // TODO(ccross): move down free list if necessary
301 }
302
303 if (frees_since_purge_++ * allocation_size_ > 16 * kPageSize) {
304 Purge();
305 }
306 }
307
Purge()308 void Chunk::Purge() {
309 frees_since_purge_ = 0;
310
311 //unsigned int allocsPerPage = kPageSize / allocation_size_;
312 }
313
314 // Override new operator on HeapImpl to use mmap to allocate a page
operator new(std::size_t count)315 void* HeapImpl::operator new(std::size_t count __attribute__((unused)))
316 noexcept {
317 assert(count == sizeof(HeapImpl));
318 void* mem = MapAligned(kPageSize, kPageSize);
319 if (!mem) {
320 abort(); //throw std::bad_alloc;
321 }
322
323 heap_count++;
324 return mem;
325 }
326
operator delete(void * ptr)327 void HeapImpl::operator delete(void *ptr) {
328 munmap(ptr, kPageSize);
329 }
330
HeapImpl()331 HeapImpl::HeapImpl() :
332 free_chunks_(), full_chunks_(), map_allocation_list_(NULL) {
333 }
334
Empty()335 bool HeapImpl::Empty() {
336 for (unsigned int i = 0; i < kNumBuckets; i++) {
337 for (LinkedList<Chunk*> *it = free_chunks_[i].next(); it->data() != NULL; it = it->next()) {
338 if (!it->data()->Empty()) {
339 return false;
340 }
341 }
342 for (LinkedList<Chunk*> *it = full_chunks_[i].next(); it->data() != NULL; it = it->next()) {
343 if (!it->data()->Empty()) {
344 return false;
345 }
346 }
347 }
348
349 return true;
350 }
351
~HeapImpl()352 HeapImpl::~HeapImpl() {
353 for (unsigned int i = 0; i < kNumBuckets; i++) {
354 while (!free_chunks_[i].empty()) {
355 Chunk *chunk = free_chunks_[i].next()->data();
356 chunk->node_.remove();
357 delete chunk;
358 }
359 while (!full_chunks_[i].empty()) {
360 Chunk *chunk = full_chunks_[i].next()->data();
361 chunk->node_.remove();
362 delete chunk;
363 }
364 }
365 }
366
Alloc(size_t size)367 void* HeapImpl::Alloc(size_t size) {
368 std::lock_guard<std::mutex> lk(m_);
369 return AllocLocked(size);
370 }
371
AllocLocked(size_t size)372 void* HeapImpl::AllocLocked(size_t size) {
373 if (size > kMaxBucketAllocationSize) {
374 return MapAlloc(size);
375 }
376 int bucket = size_to_bucket(size);
377 if (free_chunks_[bucket].empty()) {
378 Chunk *chunk = new Chunk(this, bucket);
379 free_chunks_[bucket].insert(chunk->node_);
380 }
381 return free_chunks_[bucket].next()->data()->Alloc();
382 }
383
Free(void * ptr)384 void HeapImpl::Free(void *ptr) {
385 std::lock_guard<std::mutex> lk(m_);
386 FreeLocked(ptr);
387 }
388
FreeLocked(void * ptr)389 void HeapImpl::FreeLocked(void *ptr) {
390 if (!Chunk::is_chunk(ptr)) {
391 HeapImpl::MapFree(ptr);
392 } else {
393 Chunk* chunk = Chunk::ptr_to_chunk(ptr);
394 assert(chunk->heap() == this);
395 chunk->Free(ptr);
396 }
397 }
398
MapAlloc(size_t size)399 void* HeapImpl::MapAlloc(size_t size) {
400 size = (size + kPageSize - 1) & ~(kPageSize - 1);
401
402 MapAllocation* allocation = reinterpret_cast<MapAllocation*>(AllocLocked(
403 sizeof(MapAllocation)));
404 void* ptr = MapAligned(size, kChunkSize);
405 if (!ptr) {
406 FreeLocked(allocation);
407 abort(); //throw std::bad_alloc;
408 }
409 allocation->ptr = ptr;
410 allocation->size = size;
411 allocation->next = map_allocation_list_;
412 map_allocation_list_ = allocation;
413
414 return ptr;
415 }
416
MapFree(void * ptr)417 void HeapImpl::MapFree(void *ptr) {
418 MapAllocation **allocation = &map_allocation_list_;
419 while (*allocation && (*allocation)->ptr != ptr)
420 allocation = &(*allocation)->next;
421
422 assert(*allocation != nullptr);
423
424 munmap((*allocation)->ptr, (*allocation)->size);
425 FreeLocked(*allocation);
426
427 *allocation = (*allocation)->next;
428 }
429
MoveToFreeList(Chunk * chunk,int bucket)430 void HeapImpl::MoveToFreeList(Chunk *chunk, int bucket) {
431 MoveToList(chunk, &free_chunks_[bucket]);
432 }
433
MoveToFullList(Chunk * chunk,int bucket)434 void HeapImpl::MoveToFullList(Chunk *chunk, int bucket) {
435 MoveToList(chunk, &full_chunks_[bucket]);
436 }
437
MoveToList(Chunk * chunk,LinkedList<Chunk * > * head)438 void HeapImpl::MoveToList(Chunk *chunk, LinkedList<Chunk*>* head) {
439 // Remove from old list
440 chunk->node_.remove();
441
442 LinkedList<Chunk*> *node = head;
443 // Insert into new list, sorted by lowest free count
444 while (node->next() != head && node->data() != nullptr
445 && node->data()->free_count() < chunk->free_count())
446 node = node->next();
447
448 node->insert(chunk->node_);
449 }
450
Heap()451 Heap::Heap() {
452 // HeapImpl overloads the operator new in order to mmap itself instead of
453 // allocating with new.
454 // Can't use a shared_ptr to store the result because shared_ptr needs to
455 // allocate, and Allocator<T> is still being constructed.
456 impl_ = new HeapImpl();
457 owns_impl_ = true;
458 }
459
~Heap()460 Heap::~Heap() {
461 if (owns_impl_) {
462 delete impl_;
463 }
464 }
465
allocate(size_t size)466 void* Heap::allocate(size_t size) {
467 return impl_->Alloc(size);
468 }
469
deallocate(void * ptr)470 void Heap::deallocate(void* ptr) {
471 impl_->Free(ptr);
472 }
473
deallocate(HeapImpl * impl,void * ptr)474 void Heap::deallocate(HeapImpl*impl, void* ptr) {
475 impl->Free(ptr);
476 }
477
empty()478 bool Heap::empty() {
479 return impl_->Empty();
480 }
481