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 #include "chre/util/raw_storage.h" 25 26 namespace chre { 27 28 /** 29 * A memory pool (slab allocator) used for very efficient allocation and 30 * deallocation of objects with a uniform size. The goal is to avoid costly 31 * malloc/free calls. 32 * 33 * This implementation is based on the following paper: 34 * 35 * Fast Efficient Fixed-Size Memory Pool 36 * No Loops and No Overhead 37 * Ben Kenwright 38 * 39 * Allocations and deallocation are handled in O(1) time and memory. The list 40 * of unused blocks is stored in the space of unused blocks. This means that 41 * this data structure has a minimum element size of sizeof(size_t) and means 42 * it may not be suitable for very small objects (whose size is less than 43 * sizeof(size_t)). 44 * 45 * One variation is made relative to the allocator described in the paper. To 46 * minimize allocation/deallocation latency, the free list is built at 47 * construction time. 48 */ 49 template <typename ElementType, size_t kSize> 50 class MemoryPool : public NonCopyable { 51 public: 52 /** 53 * Constructs a MemoryPool and initializes the initial conditions of the 54 * allocator. 55 */ 56 MemoryPool(); 57 58 /** 59 * Allocates space for an object, constructs it and returns the pointer to 60 * that object. 61 * 62 * @param The arguments to be forwarded to the constructor of the object. 63 * @return A pointer to a constructed object or nullptr if the allocation 64 * fails. 65 */ 66 template <typename... Args> 67 ElementType *allocate(Args &&... args); 68 69 /** 70 * Releases the memory of a previously allocated element. The pointer provided 71 * here must be one that was produced by a previous call to the allocate() 72 * function. The destructor is invoked on the object. 73 * 74 * @param A pointer to an element that was previously allocated by the 75 * allocate() function. 76 */ 77 void deallocate(ElementType *element); 78 79 /** 80 * Checks if the address of the element provided is within the range managed 81 * by this event pool. 82 * NOTE: If this method returns true, that does not mean that the provided 83 * element has not already been deallocated. It's up to the caller to ensure 84 * they don't double deallocate a given element. 85 * 86 * @param element Address to the element to check if it is in the current 87 * memory pool. 88 * @return true Returns true if the address of the provided element is 89 * managed by this pool. 90 */ 91 bool containsAddress(ElementType *element); 92 93 /** 94 * @return the number of unused blocks in this memory pool. 95 */ 96 size_t getFreeBlockCount() const; 97 98 /** 99 * @return true Return true if this memory pool is empty. 100 */ empty()101 bool empty() { 102 return mFreeBlockCount == kSize; 103 } 104 105 private: 106 /** 107 * The unused storage for this MemoryPool maintains the list of free slots. 108 * As such, a union is used to allow storage of both the Element and the index 109 * of the next free block in the same space. 110 */ 111 union MemoryPoolBlock { 112 //! Intentionally not destructing any leaked blocks, will consider doing 113 //! this differently later if required. 114 ~MemoryPoolBlock() = delete; 115 116 //! The element stored in the slot. 117 ElementType mElement; 118 119 //! The index of the next free block in the unused storage. 120 size_t mNextFreeBlockIndex; 121 }; 122 123 /** 124 * Obtains a pointer to the underlying storage for the memory pool blocks. 125 * 126 * @return A pointer to the memory pool block storage. 127 */ 128 MemoryPoolBlock *blocks(); 129 130 /** 131 * Calculate the block index that allocates the element if it belongs to 132 * this memory pool. 133 * 134 * @param element Address to the element. 135 * @param indexOutput Calculated block index output. 136 * @return false if the address of element does not belong to this memory 137 * pool. 138 */ 139 bool getBlockIndex(ElementType *element, size_t *indexOutput); 140 141 //! Storage for memory pool blocks. 142 RawStorage<MemoryPoolBlock, kSize> mBlocks; 143 144 //! The index of the head of the free slot list. 145 size_t mNextFreeBlockIndex = 0; 146 147 //! The number of free slots available. 148 size_t mFreeBlockCount = kSize; 149 }; 150 151 } // namespace chre 152 153 #include "chre/util/memory_pool_impl.h" 154 155 #endif // CHRE_UTIL_MEMORY_POOL_H_ 156