comm-central/third_party/botan/src/lib/utils/mem_pool
Name Description Size
info.txt 91
mem_pool.cpp Memory pool theory of operation This allocator is not useful for general purpose but works well within the context of allocating cryptographic keys. It makes several assumptions which don't work for implementing malloc but simplify and speed up the implementation: - There is some set of pages, which cannot be expanded later. These are pages which were allocated, mlocked and passed to the Memory_Pool constructor. - The allocator is allowed to return null anytime it feels like not servicing a request, in which case the request will be sent to calloc instead. In particular, requests which are too small or too large are rejected. - Most allocations are powers of 2, the remainder are usually a multiple of 8 - Free requests include the size of the allocation, so there is no need to track this within the pool. - Alignment is important to the caller. For this allocator, any allocation of size N is aligned evenly at N bytes. Initially each page is in the free page list. Each page is used for just one size of allocation, with requests bucketed into a small number of common sizes. If the allocation would be too big or too small it is rejected by the pool. The free list is maintained by a bitmap, one per page/Bucket. Since each Bucket only maintains objects of a single size, each bit set or clear indicates the status of one object. An allocation walks the list of buckets and asks each in turn if there is space. If a Bucket does not have any space, it sets a boolean flag m_is_full so that it does not need to rescan when asked again. The flag is cleared on first free from that bucket. If no bucket has space, but there are some free pages left, a free page is claimed as a new Bucket for that size. In this case it is pushed to the front of the list so it is first in line to service new requests. A deallocation also walks the list of buckets for the size and asks each Bucket in turn if it recognizes the pointer. When a Bucket becomes empty as a result of a deallocation, it is recycled back into the free pool. When this happens, the Buckets page goes to the end of the free list. All pages on the free list are marked in the MMU as noaccess, so anything touching them will immediately crash. They are only marked R/W once placed into a new bucket. Making the free list FIFO maximizes the time between the last free of a bucket and that page being writable again, maximizing chances of crashing after a use-after-free. Future work ------------- The allocator is protected by a global lock. It would be good to break this up, since almost all of the work can actually be done in parallel especially when allocating objects of different sizes (which can't possibly share a bucket). It may be worthwhile to optimize deallocation by storing the Buckets in order (by pointer value) which would allow binary search to find the owning bucket. A useful addition would be to randomize the allocations. Memory_Pool would be changed to receive also a RandomNumberGenerator& object (presumably the system RNG, or maybe a ChaCha_RNG seeded with system RNG). Then the bucket to use and the offset within the bucket would be chosen randomly, instead of using first fit. Right now we don't make any provision for threading, so if two threads both allocate 32 byte values one after the other, the two allocations will likely share a cache line. Ensuring that distinct threads will (tend to) use distinct buckets would reduce this. Supporting a realloc-style API may be useful. 12900
mem_pool.h Initialize a memory pool. The memory is not owned by *this, it must be freed by the caller. @param pages a list of pages to allocate from @param page_size the system page size, each page should point to exactly this much memory. 1305