BlockAllocator.cpp
Go to the documentation of this file.
1 /*
2  * Original work Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
3  * Modified work Copyright (c) 2017 Louis Langholtz https://github.com/louis-langholtz/PlayRho
4  *
5  * This software is provided 'as-is', without any express or implied
6  * warranty. In no event will the authors be held liable for any damages
7  * arising from the use of this software.
8  * Permission is granted to anyone to use this software for any purpose,
9  * including commercial applications, and to alter it and redistribute it
10  * freely, subject to the following restrictions:
11  * 1. The origin of this software must not be misrepresented; you must not
12  * claim that you wrote the original software. If you use this software
13  * in a product, an acknowledgment in the product documentation would be
14  * appreciated but is not required.
15  * 2. Altered source versions must be plainly marked as such, and must not be
16  * misrepresented as being the original software.
17  * 3. This notice may not be removed or altered from any source distribution.
18  */
19 
20 #include <PlayRho/Common/BlockAllocator.hpp>
21 #include <PlayRho/Common/DynamicMemory.hpp>
22 #include <limits>
23 #include <cstring>
24 #include <cstddef>
25 
26 namespace playrho {
27 
28 static_assert(size(AllocatorBlockSizes) == 14,
29  "Invalid number of elements of AllocatorBlockSizes");
30 static_assert(BlockAllocator::GetMaxBlockSize() == 640,
31  "Invalid maximum block size of AllocatorBlockSizes");
32 
33 #if 0
34 struct LookupTable
35 {
36  constexpr LookupTable(): elements()
37  {
38  constexpr auto maxIndex = BlockAllocator::GetMaxBlockSize() + 1;
39  auto j = std::uint8_t{0};
40  elements[0] = 0;
41  for (auto i = std::size_t{1}; i < maxIndex; ++i)
42  {
43  if (i > AllocatorBlockSizes[j])
44  {
45  ++j;
46  }
47  elements[i] = j;
48  }
49  }
50 
51  std::uint8_t elements[BlockAllocator::GetMaxBlockSize() + 1];
52 };
53 static constexpr const LookupTable BlockSizeLookup;
54 #endif
55 
57 static PLAYRHO_CONSTEXPR const std::uint8_t s_blockSizeLookup[BlockAllocator::GetMaxBlockSize() + 1] =
58 {
59  0,
60  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 1-16
61  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 17-32
62  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // 33-64
63  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, // 65-96
64  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 97-128
65  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 129-160
66  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 161-192
67  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 193-224
68  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 225-256
69  9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, // 257-288
70  9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, // 288-320
71  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, // 321-352
72  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, // 353-384
73  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, // 385-416
74  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, // 427-448
75  12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, // 449-480
76  12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, // 481-512
77  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, // 513-544
78  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, // 545-576
79  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, // 577-608
80  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, // 608-640
81 };
82 
84 static inline std::uint8_t GetBlockSizeIndex(std::size_t n)
85 {
86  assert(n < size(s_blockSizeLookup));
87  return s_blockSizeLookup[n];
88 }
89 
91 struct BlockAllocator::Chunk
92 {
93  using size_type = std::size_t;
94 
95  size_type blockSize;
96  Block* blocks;
97 };
98 
100 struct BlockAllocator::Block
101 {
102  Block* next;
103 };
104 
105 BlockAllocator::BlockAllocator():
106  m_chunks(Alloc<Chunk>(m_chunkSpace))
107 {
108  static_assert(size(AllocatorBlockSizes) < std::numeric_limits<std::uint8_t>::max(),
109  "AllocatorBlockSizes too big");
110  std::memset(m_chunks, 0, m_chunkSpace * sizeof(Chunk));
111  std::memset(m_freeLists, 0, sizeof(m_freeLists));
112 }
113 
114 BlockAllocator::~BlockAllocator() noexcept
115 {
116  for (auto i = decltype(m_chunkCount){0}; i < m_chunkCount; ++i)
117  {
118  playrho::Free(m_chunks[i].blocks);
119  }
120  playrho::Free(m_chunks);
121 }
122 
123 void* BlockAllocator::Allocate(size_type n)
124 {
125  if (n == 0)
126  {
127  return nullptr;
128  }
129 
130  if (n > GetMaxBlockSize())
131  {
132  return Alloc(n);
133  }
134 
135  const auto index = GetBlockSizeIndex(n);
136  assert((0 <= index) && (index < size(m_freeLists)));
137  {
138  const auto block = m_freeLists[index];
139  if (block)
140  {
141  m_freeLists[index] = block->next;
142  return block;
143  }
144  }
145 
146  if (m_chunkCount == m_chunkSpace)
147  {
148  m_chunkSpace += GetChunkArrayIncrement();
149  m_chunks = Realloc<Chunk>(m_chunks, m_chunkSpace);
150  std::memset(m_chunks + m_chunkCount, 0, GetChunkArrayIncrement() * sizeof(Chunk));
151  }
152 
153  const auto chunk = m_chunks + m_chunkCount;
154  chunk->blocks = static_cast<Block*>(Alloc(ChunkSize));
155 #if defined(_DEBUG)
156  std::memset(chunk->blocks, 0xcd, ChunkSize);
157 #endif
158  const auto blockSize = AllocatorBlockSizes[index];
159  assert(blockSize > 0);
160  chunk->blockSize = blockSize;
161  const auto blockCount = ChunkSize / blockSize;
162  assert((blockCount * blockSize) <= ChunkSize);
163  const auto chunkBlocks = reinterpret_cast<std::int8_t*>(chunk->blocks);
164  for (auto i = decltype(blockCount){0}; i < blockCount - 1; ++i)
165  {
166  const auto block = reinterpret_cast<Block*>(chunkBlocks + blockSize * i);
167  const auto next = reinterpret_cast<Block*>(chunkBlocks + blockSize * (i + 1));
168  block->next = next;
169  }
170  const auto last = reinterpret_cast<Block*>(chunkBlocks + blockSize * (blockCount - 1));
171  last->next = nullptr;
172  m_freeLists[index] = chunk->blocks->next;
173  ++m_chunkCount;
174 
175  return chunk->blocks;
176 }
177 
178 void BlockAllocator::Free(void* p, size_type n)
179 {
180  if (n > GetMaxBlockSize())
181  {
182  playrho::Free(p);
183  }
184  else if (n > 0)
185  {
186  const auto index = GetBlockSizeIndex(n);
187  assert((0 <= index) && (index < size(m_freeLists)));
188 #ifdef _DEBUG
189  // Verify the memory address and size is valid.
190  assert((0 <= index) && (index < size(AllocatorBlockSizes)));
191  const auto blockSize = AllocatorBlockSizes[index];
192  bool found = false;
193  for (auto i = decltype(m_chunkCount){0}; i < m_chunkCount; ++i)
194  {
195  const auto chunk = m_chunks + i;
196  const auto chunkBlocks = (std::int8_t*)chunk->blocks;
197  if (chunk->blockSize != blockSize)
198  {
199  assert(((std::int8_t*)p + blockSize <= chunkBlocks) || (chunkBlocks + ChunkSize <= (std::int8_t*)p));
200  }
201  else
202  {
203  if ((chunkBlocks <= (std::int8_t*)p) && ((std::int8_t*)p + blockSize <= chunkBlocks + ChunkSize))
204  {
205  found = true;
206  }
207  }
208  }
209  assert(found);
210  std::memset(p, 0xfd, blockSize);
211 #endif
212  const auto block = static_cast<Block*>(p);
213  block->next = m_freeLists[index];
214  m_freeLists[index] = block;
215  }
216 }
217 
218 void BlockAllocator::Clear()
219 {
220  for (auto i = decltype(m_chunkCount){0}; i < m_chunkCount; ++i)
221  {
222  playrho::Free(m_chunks[i].blocks);
223  }
224 
225  m_chunkCount = 0;
226  std::memset(m_chunks, 0, m_chunkSpace * sizeof(Chunk));
227  std::memset(m_freeLists, 0, sizeof(m_freeLists));
228 }
229 
230 } // namespace playrho