1 // Copyright 2018 The Android Open Source Project 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 #include "android/base/Pool.h" 15 16 #include "android/base/AlignedBuf.h" 17 18 #include <vector> 19 20 #define DEBUG_POOL 0 21 22 #if DEBUG_POOL 23 24 #define D(fmt,...) fprintf(stderr, "%s: " fmt "\n", __func__, ##__VA_ARGS__); 25 26 #else 27 28 #define D(fmt,...) 29 30 #endif 31 32 namespace android { 33 namespace base { 34 35 // A Pool consists of: 36 // - Heaps one for each allocation size 37 // A Heap consists of: 38 // - Block(s) for servicing allocation requests with actual memory backing 39 // A Block consists of: 40 // - A buffer that is the memory backing 41 // - Chunks that correspond to usable units of the allocation size 42 // 43 // Block implementation: 44 // 45 // We want to make it fast to alloc new chunks and to free existing chunks from 46 // this block, while not having to invalidate all existing pointers when 47 // allocating new objects. 48 // I'm p sure by now there's no way to do that withtout 49 // - significant pre allocation 50 // - linked list of blocks 51 // 52 // So that means some block chain (hehehehe, pun v much intended) 53 // implementation Wherein, each block has fast allocation of chunks 54 // correponding tot he desired allocation size. 55 // 56 // Any low overhead scheme of that kind, like slab alloc or buddy alloc, is 57 // fine. This one is based on: 58 // 59 // Ben Kenwright (b.kenwright (at) ncl.ac.uk): "Fast Efficient Fixed-Size Memory 60 // Pool: No Loops and No Overhead" In COMPUTATION TOOLS 2012: The Third 61 // International Conference on Computational Logics, Algebras, Programming, 62 // Tools, and Benchmarking 63 64 // Interval: 65 // Make it easy to track all ranges involved so we know which free() 66 // in which heap to use. 67 // Assuming this doesn't grow too much past around 100 intervals 68 // so we dont need to use fancy algorithms to key on it. 69 struct Interval { 70 uintptr_t start; 71 uintptr_t end; 72 }; 73 74 static size_t ilog2Floor(size_t n) { 75 size_t res = 0; 76 size_t test = 1; 77 78 while (test < n) { 79 test <<= 1; 80 ++res; 81 } 82 83 return res; 84 } 85 86 struct Block { 87 Block(size_t _chunkSize, size_t _numChunks) { 88 if (_chunkSize < sizeof(void*)) { 89 fprintf( 90 stderr, 91 "FATAL: Cannot allocate block with chunk size " 92 "less then %zu (wanted: %zu)!\n", 93 sizeof(void*), 94 _chunkSize); 95 abort(); 96 } 97 98 chunkSize = _chunkSize; 99 chunkSizeLog2 = ilog2Floor(chunkSize); 100 numChunks = _numChunks; 101 102 D("chunk size %zu log2 %zu numChunks %zu", 103 chunkSize, 104 chunkSizeLog2, 105 numChunks); 106 107 sizeBytes = chunkSize * numChunks; 108 109 storage.resize(sizeBytes); 110 data = storage.data(); 111 112 numFree = numChunks; 113 numAlloced = 0; 114 nextFree = (size_t*)data; 115 } 116 117 Interval getInterval() const { 118 uintptr_t start = (uintptr_t)data; 119 uintptr_t end = (uintptr_t)(data + sizeBytes); 120 return { start, end }; 121 } 122 123 bool isFull() const { return numFree == 0; } 124 125 uint8_t* getPtr(size_t element) { 126 uint8_t* res = 127 data + (uintptr_t)chunkSize * 128 (uintptr_t)element; 129 D("got %p element %zu chunkSize %zu", 130 res, element, chunkSize); 131 return res; 132 } 133 134 size_t getElement(void* ptr) { 135 uintptr_t ptrVal = (uintptr_t)ptr; 136 ptrVal -= (uintptr_t)data; 137 return (size_t)(ptrVal >> chunkSizeLog2); 138 } 139 140 void* alloc() { 141 // Lazily constructs the index to the 142 // next unallocated chunk. 143 if (numAlloced < numChunks) { 144 size_t* nextUnallocPtr = 145 (size_t*)getPtr(numAlloced); 146 147 ++numAlloced; 148 *nextUnallocPtr = numAlloced; 149 } 150 151 // Returns the next free object, 152 // if there is space remaining. 153 void* res = nullptr; 154 if (numFree) { 155 156 D("alloc new ptr @ %p\n", nextFree); 157 158 res = (void*)nextFree; 159 --numFree; 160 if (numFree) { 161 // Update nextFree to _point_ at the index 162 // of the next free chunk. 163 D("store %zu in %p as next free chunk", 164 *nextFree, 165 getPtr(*nextFree)); 166 nextFree = (size_t*)getPtr(*nextFree); 167 } else { 168 // Signal that there are no more 169 // chunks available. 170 nextFree = nullptr; 171 } 172 } 173 174 return res; 175 } 176 177 void free(void* toFree) { 178 size_t* toFreeIndexPtr = (size_t*)toFree; 179 if (nextFree) { 180 D("freeing %p: still have other chunks available.", toFree); 181 D("nextFree: %p (end: %p)", nextFree, getPtr(numChunks)); 182 D("nextFreeElt: %zu\n", getElement(nextFree)); 183 // If there is a chunk available, 184 // point the just-freed chunk to that. 185 *toFreeIndexPtr = getElement(nextFree); 186 } else { 187 D("freeing free %p: no other chunks available.", toFree); 188 // If there are no chunks available, 189 // point the just-freed chunk to past the end. 190 *(size_t*)toFree = numChunks; 191 } 192 nextFree = (size_t*)toFree; 193 D("set next free to %p", nextFree); 194 ++numFree; 195 } 196 197 // To free everything, just reset back to the initial state :p 198 void freeAll() { 199 numFree = numChunks; 200 numAlloced = 0; 201 nextFree = (size_t*)data; 202 } 203 204 Block* next = nullptr; // Unused for now 205 206 size_t chunkSize = 0; 207 size_t chunkSizeLog2 = 0; 208 size_t numChunks = 0; 209 size_t sizeBytes = 0; 210 211 AlignedBuf<uint8_t, 64> storage { 0 }; 212 uint8_t* data = nullptr; 213 214 size_t numFree = 0; 215 size_t numAlloced = 0; 216 217 size_t* nextFree = 0; 218 }; 219 220 // Straight passthrough to Block for now unless 221 // we find it necessary to track more than |kMaxAllocs| 222 // allocs per heap. 223 class Heap { 224 public: 225 Heap(size_t allocSize, size_t chunksPerSize) : 226 mBlock(allocSize, chunksPerSize) { 227 } 228 229 Interval getInterval() const { 230 return mBlock.getInterval(); 231 } 232 233 bool isFull() const { 234 return mBlock.isFull(); 235 } 236 237 void* alloc() { 238 return mBlock.alloc(); 239 } 240 241 void free(void* ptr) { 242 mBlock.free(ptr); 243 } 244 245 void freeAll() { 246 mBlock.freeAll(); 247 } 248 249 private: 250 // Just one block for now 251 Block mBlock; 252 }; 253 254 static size_t leastPowerof2(size_t n) { 255 size_t res = 1; 256 while (res < n) { 257 res <<= 1; 258 } 259 return res; 260 } 261 262 class Pool::Impl { 263 public: 264 Impl(size_t minSize, 265 size_t maxSize, 266 size_t chunksPerSize) : 267 // Need to bump up min alloc size 268 // because Blocks use free space for bookkeeping 269 // purposes. 270 mMinAllocSize(std::max(sizeof(void*), minSize)), 271 // Compute mMinAllocLog2. 272 // mMinAllocLog2 stores 273 // the number of bits to shift 274 // in order to obtain the heap index 275 // corresponding to a desired allocation size. 276 mMinAllocLog2(ilog2Floor(mMinAllocSize)), 277 mMaxFastSize(maxSize), 278 mChunksPerSize(chunksPerSize) { 279 280 size_t numHeaps = 281 1 + ilog2Floor(mMaxFastSize >> mMinAllocLog2); 282 283 for (size_t i = 0; i < numHeaps; i++) { 284 285 size_t allocSize = mMinAllocSize << i; 286 287 D("create heap for size %zu", allocSize); 288 289 Heap* newHeap = new Heap(allocSize, mChunksPerSize); 290 291 HeapInfo info = { 292 newHeap, 293 allocSize, 294 newHeap->getInterval(), 295 }; 296 297 mHeapInfos.push_back(info); 298 } 299 } 300 301 ~Impl() { 302 for (auto& info : mHeapInfos) { 303 delete info.heap; 304 } 305 } 306 307 void* alloc(size_t wantedSize) { 308 if (wantedSize > mMaxFastSize) { 309 D("requested size %zu too large", wantedSize); 310 return nullptr; 311 } 312 313 size_t minAllocSizeNeeded = 314 std::max(mMinAllocSize, leastPowerof2(wantedSize)); 315 316 size_t index = 317 ilog2Floor(minAllocSizeNeeded >> mMinAllocLog2); 318 319 D("wanted: %zu min serviceable: %zu heap index: %zu", 320 wantedSize, minAllocSizeNeeded, index); 321 322 auto heap = mHeapInfos[index].heap; 323 324 if (heap->isFull()) { 325 D("heap %zu is full", index); 326 return nullptr; 327 } 328 329 return heap->alloc(); 330 } 331 332 bool free(void* ptr) { 333 334 D("for %p:", ptr); 335 336 uintptr_t ptrVal = (uintptr_t)ptr; 337 338 // Scan through linearly to find any matching 339 // interval. Interval information has been 340 // brought up to be stored directly in HeapInfo 341 // so this should be quite easy on the cache 342 // at least until a match is found. 343 for (auto& info : mHeapInfos) { 344 uintptr_t start = info.interval.start; 345 uintptr_t end = info.interval.end; 346 347 if (ptrVal >= start && ptrVal < end) { 348 D("found heap to free %p.", ptr) 349 info.heap->free(ptr); 350 return true; 351 } 352 } 353 354 D("%p not found in any heap.", ptr); 355 return false; 356 } 357 358 void freeAll() { 359 for (auto& info : mHeapInfos) { 360 info.heap->freeAll(); 361 } 362 } 363 364 private: 365 size_t mMinAllocSize; 366 size_t mMinAllocLog2; 367 size_t mMaxFastSize; 368 size_t mChunksPerSize; 369 370 // No need to get really complex if there are 371 // not that many heaps. 372 struct HeapInfo { 373 Heap* heap; 374 size_t allocSize; 375 Interval interval; 376 }; 377 378 std::vector<HeapInfo> mHeapInfos; 379 }; 380 381 Pool::Pool(size_t minSize, 382 size_t maxSize, 383 size_t mChunksPerSize) : 384 mImpl(new Pool::Impl(minSize, 385 maxSize, 386 mChunksPerSize)) { 387 } 388 389 Pool::~Pool() { 390 delete mImpl; 391 392 for (auto ptr : mFallbackPtrs) { 393 D("delete fallback ptr %p\n", ptr); 394 ::free(ptr); 395 } 396 } 397 398 // Fall back to normal alloc if it cannot be 399 // serviced by the implementation. 400 void* Pool::alloc(size_t wantedSize) { 401 void* ptr = mImpl->alloc(wantedSize); 402 403 if (ptr) return ptr; 404 405 D("Fallback to malloc"); 406 407 ptr = ::malloc(wantedSize); 408 409 if (!ptr) { 410 D("Failed to service allocation for %zu bytes", wantedSize); 411 abort(); 412 } 413 414 mFallbackPtrs.insert(ptr); 415 416 D("Fallback to malloc: got ptr %p", ptr); 417 418 return ptr; 419 } 420 421 // Fall back to normal free if it cannot be 422 // serviced by the implementation. 423 void Pool::free(void* ptr) { 424 if (mImpl->free(ptr)) return; 425 426 D("fallback to free for %p", ptr); 427 mFallbackPtrs.erase(ptr); 428 ::free(ptr); 429 } 430 431 void Pool::freeAll() { 432 mImpl->freeAll(); 433 for (auto ptr : mFallbackPtrs) { 434 ::free(ptr); 435 } 436 mFallbackPtrs.clear(); 437 } 438 439 } // namespace base 440 } // namespace android 441