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