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/fixed_size_vector.h"
24 #include "chre/util/non_copyable.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  private:
80   /**
81    * The unused storage for this MemoryPool maintains the list of free slots.
82    * As such, a union is used to allow storage of both the Element and the index
83    * of the next free block in the same space.
84    */
85   union MemoryPoolBlock {
86     /**
87      * Construct a MemoryPoolBlock given the index of the next free block.
88      *
89      * @param The index of the next free block in the free list.
90      */
91     MemoryPoolBlock(size_t nextFreeBlockIndex);
92 
93     //! The element stored in the slot.
94     ElementType mElement;
95 
96     //! The index of the next free block in the unused storage.
97     size_t mNextFreeBlockIndex;
98   };
99 
100   //! A vector of memory pool blocks.
101   FixedSizeVector<MemoryPoolBlock, kSize> mBlocks;
102 
103   //! The index of the head of the free slot list.
104   size_t mNextFreeBlockIndex = 0;
105 
106   //! The number of free slots available.
107   size_t mFreeBlockCount = kSize;
108 };
109 
110 }  // namespace chre
111 
112 #include "chre/util/memory_pool_impl.h"
113 
114 #endif  // CHRE_UTIL_MEMORY_POOL_H_
115