memory_pool.h revision a51ef01822ac68061a1d6e686389cfbcb0e1f8da 
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
25namespace 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 */
48template<typename ElementType, size_t kSize>
49class 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 private:
79  /**
80   * The unused storage for this MemoryPool maintains the list of free slots.
81   * As such, a union is used to allow storage of both the Element and the index
82   * of the next free block in the same space.
83   */
84  union MemoryPoolBlock {
85    //! Intentionally not destructing any leaked blocks, will consider doing
86    //! this differently later if required.
87    ~MemoryPoolBlock() = delete;
88
89    //! The element stored in the slot.
90    ElementType mElement;
91
92    //! The index of the next free block in the unused storage.
93    size_t mNextFreeBlockIndex;
94  };
95
96  /**
97   * Obtains a pointer to the underlying storage for the memory pool blocks.
98   *
99   * @return A pointer to the memory pool block storage.
100   */
101  MemoryPoolBlock *blocks();
102
103  //! Storage for memory pool blocks. To avoid static initialization of members,
104  //! std::aligned_storage is used.
105  typename std::aligned_storage<sizeof(MemoryPoolBlock),
106      alignof(MemoryPoolBlock)>::type mBlocks[kSize];
107
108  //! The index of the head of the free slot list.
109  size_t mNextFreeBlockIndex = 0;
110
111  //! The number of free slots available.
112  size_t mFreeBlockCount = kSize;
113};
114
115}  // namespace chre
116
117#include "chre/util/memory_pool_impl.h"
118
119#endif  // CHRE_UTIL_MEMORY_POOL_H_
120