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 22 #include "chre/util/non_copyable.h" 23 #include "chre/util/raw_storage.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 * Function used to decide if an element in the pool matches a certain 53 * condition. 54 * 55 * @param element The element. 56 * @param data The data passed to the find function. 57 * @see find. 58 * @return true if the element matched, false otherwise. 59 */ 60 using MatchingFunction = bool(ElementType *element, void *data); 61 62 /** 63 * Constructs a MemoryPool and initializes the initial conditions of the 64 * allocator. 65 */ 66 MemoryPool(); 67 68 /** 69 * Allocates space for an object, constructs it and returns the pointer to 70 * that object. 71 * 72 * @param The arguments to be forwarded to the constructor of the object. 73 * @return A pointer to a constructed object or nullptr if the allocation 74 * fails. 75 */ 76 template <typename... Args> 77 ElementType *allocate(Args &&... args); 78 79 /** 80 * Releases the memory of a previously allocated element. The pointer provided 81 * here must be one that was produced by a previous call to the allocate() 82 * function. The destructor is invoked on the object. 83 * 84 * @param A pointer to an element that was previously allocated by the 85 * allocate() function. 86 */ 87 void deallocate(ElementType *element); 88 89 /** 90 * Checks if the address of the element provided is within the range managed 91 * by this event pool. 92 * NOTE: If this method returns true, that does not mean that the provided 93 * element has not already been deallocated. It's up to the caller to ensure 94 * they don't double deallocate a given element. 95 * 96 * @param element Address to the element to check if it is in the current 97 * memory pool. 98 * @return true Returns true if the address of the provided element is 99 * managed by this pool. 100 */ 101 bool containsAddress(ElementType *element); 102 103 /** 104 * Searches the active blocks in the memory pool, calling 105 * the matchingFunction. The first element such that 106 * matchingFunction returns true is returned, else nullptr. 107 * 108 * @param matchingFunction The function to match. 109 * @param data The data passed to matchingFunction. 110 * @return the first matching element or nullptr if not found. 111 */ 112 ElementType *find(MatchingFunction *matchingFunction, void *data); 113 114 /** 115 * @return the number of unused blocks in this memory pool. 116 */ 117 size_t getFreeBlockCount() const; 118 119 /** 120 * @return true Return true if this memory pool is empty. 121 */ empty()122 bool empty() { 123 return mFreeBlockCount == kSize; 124 } 125 126 private: 127 /** 128 * The unused storage for this MemoryPool maintains the list of free slots. 129 * As such, a union is used to allow storage of both the Element and the index 130 * of the next free block in the same space. 131 */ 132 union MemoryPoolBlock { 133 //! Intentionally not destructing any leaked blocks, will consider doing 134 //! this differently later if required. 135 ~MemoryPoolBlock() = delete; 136 137 //! The element stored in the slot. 138 ElementType mElement; 139 140 //! The index of the next free block in the unused storage. 141 size_t mNextFreeBlockIndex; 142 }; 143 144 //! The number of bits in a uint32_t. 145 static constexpr size_t kBitSizeOfUInt32 = sizeof(uint32_t) * 8; 146 147 //! the number of active tracker blocks - one bit per element. 148 static constexpr uint32_t kNumActiveTrackerBlocks = 149 kSize % kBitSizeOfUInt32 == 0 ? kSize / kBitSizeOfUInt32 150 : (kSize / kBitSizeOfUInt32) + 1; 151 152 /** 153 * Obtains a pointer to the underlying storage for the memory pool blocks. 154 * 155 * @return A pointer to the memory pool block storage. 156 */ 157 MemoryPoolBlock *blocks(); 158 159 /** 160 * Calculate the block index that allocates the element if it belongs to 161 * this memory pool. 162 * 163 * @param element Address to the element. 164 * @param indexOutput Calculated block index output. 165 * @return false if the address of element does not belong to this memory 166 * pool. 167 */ 168 bool getBlockIndex(ElementType *element, size_t *indexOutput); 169 170 /** 171 * Sets the bit inside the active tracker blocks to 1 if isActive 172 * is true, else 0. 173 * 174 * @param blockIndex The index of the block inside the storage. 175 * @param isActive If the block should be marked active. 176 */ 177 void setBlockActiveStatus(size_t blockIndex, bool isActive); 178 179 //! Storage for memory pool blocks. 180 RawStorage<MemoryPoolBlock, kSize> mBlocks; 181 182 //! The index of the head of the free slot list. 183 size_t mNextFreeBlockIndex = 0; 184 185 //! The number of free slots available. 186 size_t mFreeBlockCount = kSize; 187 188 //! Used to track the active blocks using one bit per block. 189 uint32_t mActiveTrackerBlocks[kNumActiveTrackerBlocks]; 190 }; 191 192 } // namespace chre 193 194 #include "chre/util/memory_pool_impl.h" // IWYU pragma: export 195 196 #endif // CHRE_UTIL_MEMORY_POOL_H_ 197