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 #ifndef CHRE_UTIL_MEMORY_POOL_H_ 18 #define CHRE_UTIL_MEMORY_POOL_H_ 19 20 #include <cstddef> 21 #include <type_traits> 22 23 #include "chre/util/non_copyable.h" 24 25 namespace chre { 26 27 /** 28 * A memory pool (slab allocator) used for very efficient allocation and 29 * deallocation of objects with a uniform size. The goal is to avoid costly 30 * malloc/free calls. 31 * 32 * This implementation is based on the following paper: 33 * 34 * Fast Efficient Fixed-Size Memory Pool 35 * No Loops and No Overhead 36 * Ben Kenwright 37 * 38 * Allocations and deallocation are handled in O(1) time and memory. The list 39 * of unused blocks is stored in the space of unused blocks. This means that 40 * this data structure has a minimum element size of sizeof(size_t) and means 41 * it may not be suitable for very small objects (whose size is less than 42 * sizeof(size_t)). 43 * 44 * One variation is made relative to the allocator described in the paper. To 45 * minimize allocation/deallocation latency, the free list is built at 46 * construction time. 47 */ 48 template <typename ElementType, size_t kSize> 49 class MemoryPool : public NonCopyable { 50 public: 51 /** 52 * Constructs a MemoryPool and initializes the initial conditions of the 53 * allocator. 54 */ 55 MemoryPool(); 56 57 /** 58 * Allocates space for an object, constructs it and returns the pointer to 59 * that object. 60 * 61 * @param The arguments to be forwarded to the constructor of the object. 62 * @return A pointer to a constructed object or nullptr if the allocation 63 * fails. 64 */ 65 template <typename... Args> 66 ElementType *allocate(Args &&... args); 67 68 /** 69 * Releases the memory of a previously allocated element. The pointer provided 70 * here must be one that was produced by a previous call to the allocate() 71 * function. The destructor is invoked on the object. 72 * 73 * @param A pointer to an element that was previously allocated by the 74 * allocate() function. 75 */ 76 void deallocate(ElementType *element); 77 78 /** 79 * @return the number of unused blocks in this memory pool. 80 */ 81 size_t getFreeBlockCount() const; 82 83 private: 84 /** 85 * The unused storage for this MemoryPool maintains the list of free slots. 86 * As such, a union is used to allow storage of both the Element and the index 87 * of the next free block in the same space. 88 */ 89 union MemoryPoolBlock { 90 //! Intentionally not destructing any leaked blocks, will consider doing 91 //! this differently later if required. 92 ~MemoryPoolBlock() = delete; 93 94 //! The element stored in the slot. 95 ElementType mElement; 96 97 //! The index of the next free block in the unused storage. 98 size_t mNextFreeBlockIndex; 99 }; 100 101 /** 102 * Obtains a pointer to the underlying storage for the memory pool blocks. 103 * 104 * @return A pointer to the memory pool block storage. 105 */ 106 MemoryPoolBlock *blocks(); 107 108 //! Storage for memory pool blocks. To avoid static initialization of members, 109 //! std::aligned_storage is used. 110 typename std::aligned_storage<sizeof(MemoryPoolBlock), 111 alignof(MemoryPoolBlock)>::type mBlocks[kSize]; 112 113 //! The index of the head of the free slot list. 114 size_t mNextFreeBlockIndex = 0; 115 116 //! The number of free slots available. 117 size_t mFreeBlockCount = kSize; 118 }; 119 120 } // namespace chre 121 122 #include "chre/util/memory_pool_impl.h" 123 124 #endif // CHRE_UTIL_MEMORY_POOL_H_ 125