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_IMPL_H_
18 #define CHRE_UTIL_MEMORY_POOL_IMPL_H_
19
20 // IWYU pragma: private
21 #include <cinttypes>
22 #include <type_traits>
23 #include <utility>
24
25 #include "chre/util/container_support.h"
26 #include "chre/util/memory_pool.h"
27
28 namespace chre {
29 template <typename ElementType, size_t kSize>
MemoryPool()30 MemoryPool<ElementType, kSize>::MemoryPool() {
31 // Initialize the free block list. The initial condition is such that each
32 // block points to the next as being empty. The mFreeBlockCount is used to
33 // ensure that we never allocate out of bounds so we don't need to worry about
34 // the last block referring to one that is non-existent.
35 for (size_t i = 0; i < kSize; ++i) {
36 blocks()[i].mNextFreeBlockIndex = i + 1;
37 }
38
39 for (size_t i = 0; i < kNumActiveTrackerBlocks; ++i) {
40 mActiveTrackerBlocks[i] = 0;
41 }
42 }
43
44 template <typename ElementType, size_t kSize>
45 template <typename... Args>
allocate(Args &&...args)46 ElementType *MemoryPool<ElementType, kSize>::allocate(Args &&... args) {
47 if (mFreeBlockCount == 0) {
48 return nullptr;
49 }
50
51 size_t blockIndex = mNextFreeBlockIndex;
52 mNextFreeBlockIndex = blocks()[blockIndex].mNextFreeBlockIndex;
53 mFreeBlockCount--;
54 setBlockActiveStatus(blockIndex, /* isActive= */ true);
55
56 return new (&blocks()[blockIndex].mElement)
57 ElementType(std::forward<Args>(args)...);
58 }
59
60 template <typename ElementType, size_t kSize>
deallocate(ElementType * element)61 void MemoryPool<ElementType, kSize>::deallocate(ElementType *element) {
62 size_t blockIndex;
63 CHRE_ASSERT(getBlockIndex(element, &blockIndex));
64
65 blocks()[blockIndex].mElement.~ElementType();
66 blocks()[blockIndex].mNextFreeBlockIndex = mNextFreeBlockIndex;
67 mNextFreeBlockIndex = blockIndex;
68 mFreeBlockCount++;
69 setBlockActiveStatus(blockIndex, /* isActive= */ false);
70 }
71
72 template <typename ElementType, size_t kSize>
containsAddress(ElementType * element)73 bool MemoryPool<ElementType, kSize>::containsAddress(ElementType *element) {
74 size_t temp;
75 return getBlockIndex(element, &temp);
76 }
77
78 template <typename ElementType, size_t kSize>
find(MatchingFunction * matchingFunction,void * data)79 ElementType *MemoryPool<ElementType, kSize>::find(
80 MatchingFunction *matchingFunction, void *data) {
81 if (matchingFunction == nullptr) {
82 return nullptr;
83 }
84
85 for (size_t i = 0; i < kNumActiveTrackerBlocks; ++i) {
86 for (size_t j = 0; j < kBitSizeOfUInt32; ++j) {
87 size_t blockIndex = (i * kBitSizeOfUInt32) + j;
88 if (blockIndex < kSize) {
89 bool isElementActive = (mActiveTrackerBlocks[i] >> j) % 2 > 0;
90 ElementType *element = &blocks()[blockIndex].mElement;
91 if (isElementActive && matchingFunction(element, data)) {
92 return element;
93 }
94 }
95 }
96 }
97 return nullptr;
98 }
99
100 template <typename ElementType, size_t kSize>
getBlockIndex(ElementType * element,size_t * indexOutput)101 bool MemoryPool<ElementType, kSize>::getBlockIndex(ElementType *element,
102 size_t *indexOutput) {
103 uintptr_t elementAddress = reinterpret_cast<uintptr_t>(element);
104 uintptr_t baseAddress = reinterpret_cast<uintptr_t>(&blocks()[0].mElement);
105 *indexOutput = (elementAddress - baseAddress) / sizeof(MemoryPoolBlock);
106
107 return elementAddress >= baseAddress &&
108 elementAddress <=
109 reinterpret_cast<uintptr_t>(&blocks()[kSize - 1].mElement) &&
110 ((elementAddress - baseAddress) % sizeof(MemoryPoolBlock) == 0);
111 }
112
113 template <typename ElementType, size_t kSize>
setBlockActiveStatus(size_t blockIndex,bool isActive)114 void MemoryPool<ElementType, kSize>::setBlockActiveStatus(size_t blockIndex,
115 bool isActive) {
116 size_t activeTrackerBlockIndex = blockIndex / kBitSizeOfUInt32;
117 size_t indexInsideActiveTrackerBlock =
118 blockIndex - (activeTrackerBlockIndex * kBitSizeOfUInt32);
119
120 if (isActive) {
121 mActiveTrackerBlocks[activeTrackerBlockIndex] |=
122 (1 << indexInsideActiveTrackerBlock);
123 } else {
124 mActiveTrackerBlocks[activeTrackerBlockIndex] &=
125 (static_cast<uint32_t>(-1) - (1 << indexInsideActiveTrackerBlock));
126 }
127 }
128
129 template <typename ElementType, size_t kSize>
getFreeBlockCount()130 size_t MemoryPool<ElementType, kSize>::getFreeBlockCount() const {
131 return mFreeBlockCount;
132 }
133
134 template <typename ElementType, size_t kSize>
135 typename MemoryPool<ElementType, kSize>::MemoryPoolBlock *
blocks()136 MemoryPool<ElementType, kSize>::blocks() {
137 return mBlocks.data();
138 }
139
140 } // namespace chre
141
142 #endif // CHRE_UTIL_MEMORY_POOL_IMPL_H_
143