1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_object_pool.h
28 // vogl_object_pool is a straightforward freelist class.
29 // It's fast, but it's very greedy. It never frees allocated blocks unless you explictly call clear() (fast) or free_unused_blocks() (not as fast if some blocks are still allocated).
31 #ifndef VOGL_OBJECT_POOL_H
32 #define VOGL_OBJECT_POOL_H
34 #include "vogl_core.h"
35 #include "vogl_console.h"
37 // Set to 1 to enable allocation debugging using rmalloc.c (much slower)
38 #ifndef VOGL_OBJECT_POOL_DEBUGGING
39 #define VOGL_OBJECT_POOL_DEBUGGING 1
42 #if VOGL_OBJECT_POOL_DEBUGGING
43 // #warning vogl_object_pool.h: Object pool debugging enabled
46 VOGL_NAMESPACE_BEGIN(vogl)
48 #define CHECK_FAILURE check_failure(__LINE__);
50 class object_pool_no_lock_policy
62 class object_pool_spinlock_locking_policy
64 mutable spinlock m_lock;
78 class object_pool_mutex_locking_policy
94 enum object_pool_flags
96 cObjectPoolGrowExponential = 1,
97 cObjectPoolClearOnDestruction = 2
100 template <typename T, typename LockingPolicy = object_pool_no_lock_policy>
101 class object_pool : public LockingPolicy
103 VOGL_NO_COPY_OR_ASSIGNMENT_OP(object_pool);
105 typedef object_pool<T, LockingPolicy> base;
109 const object_pool &m_pool;
112 scoped_lock(const object_pool &pool)
124 object_pool(size_t grow_size = 0, uint flags = cObjectPoolGrowExponential | cObjectPoolClearOnDestruction)
126 m_grow_size(grow_size),
127 m_next_grow_size(math::maximum<size_t>(1U, grow_size)),
129 m_total_heap_bytes(0),
130 m_pFirst_free_node(NULL),
132 m_total_free_nodes(0),
135 utils::zero_object(m_blocks);
136 m_blocks.m_pPrev = &m_blocks;
137 m_blocks.m_pNext = &m_blocks;
142 if (m_flags & cObjectPoolClearOnDestruction)
148 node *pNode = alloc_node();
149 T *pObj = pNode->get_object_ptr();
150 scalar_type<T>::construct(pObj);
154 template <typename U>
155 inline T *alloc(const U &a)
157 node *pNode = alloc_node();
158 T *pObj = pNode->get_object_ptr();
159 scalar_type<T>::construct(pObj, a);
163 template <typename U, typename V>
164 inline T *alloc(const U &a, const V &b)
166 node *pNode = alloc_node();
167 T *pObj = pNode->get_object_ptr();
168 new (static_cast<void *>(pObj)) T(a, b);
172 template <typename U, typename V, typename W>
173 inline T *alloc(const U &a, const V &b, const W &c)
175 node *pNode = alloc_node();
176 T *pObj = pNode->get_object_ptr();
177 new (static_cast<void *>(pObj)) T(a, b, c);
181 template <typename U, typename V, typename W, typename X>
182 inline T *alloc(const U &a, const V &b, const W &c, const X &d)
184 node *pNode = alloc_node();
185 T *pObj = pNode->get_object_ptr();
186 new (static_cast<void *>(pObj)) T(a, b, c, d);
190 template <typename U, typename V, typename W, typename X, typename Y>
191 inline T *alloc(const U &a, const V &b, const W &c, const X &d, const Y &e)
193 node *pNode = alloc_node();
194 T *pObj = pNode->get_object_ptr();
195 new (static_cast<void *>(pObj)) T(a, b, c, d, e);
199 inline T *alloc_no_construction()
201 node *pNode = alloc_node();
202 return pNode->get_object_ptr();
205 inline void destroy_no_destruction(T *p)
207 VOGL_ASSERT(!m_update_flag);
208 VOGL_ASSERT(m_total_blocks);
213 node *pNode = reinterpret_cast<node *>(reinterpret_cast<uint8 *>(p) - static_cast<int>(VOGL_OFFSETOF(node, m_obj)));
215 #if VOGL_OBJECT_POOL_DEBUGGING
216 VOGL_ASSERT(pNode->m_marker == cUsedNodeMarker);
217 pNode->m_marker = cFreeNodeMarker;
220 LockingPolicy::lock();
222 pNode->m_pNext = m_pFirst_free_node;
223 m_pFirst_free_node = pNode;
225 ++m_total_free_nodes;
227 LockingPolicy::unlock();
230 inline void destroy(T *p)
234 scalar_type<T>::destruct(p);
235 destroy_no_destruction(p);
239 // This frees all allocated memory, but does NOT destroy all objects. That's the caller's responsibility.
242 scoped_lock lock(*this);
243 return clear_internal();
246 // TODO: until vogl::vector supports size_t sizes there are some ugly casts in here.
247 // This is a lot more complex than I originally thought it would be, and we're probably not going to need it.
248 // If the free lists were hung off each block this would be much simpler, but that would require more node overhead (or more costly frees).
249 size_t free_unused_blocks()
251 scoped_lock lock(*this);
253 VOGL_ASSERT(!m_update_flag);
255 if (!m_total_free_nodes)
258 if (m_total_free_nodes == m_total_nodes)
259 return clear_internal();
261 if ((m_total_free_nodes > cUINT32_MAX) || (m_total_nodes > cUINT32_MAX) || (m_total_blocks > cUINT32_MAX))
267 m_update_flag = true;
269 vogl::vector<node *> free_nodes;
270 free_nodes.reserve((uint)m_total_free_nodes);
272 // Put all freelist nodes into the free_nodes array and sort it by pointer address
273 node *pCur_node = m_pFirst_free_node;
276 #if VOGL_OBJECT_POOL_DEBUGGING
277 if (pCur_node->m_marker != cFreeNodeMarker)
280 m_update_flag = false;
284 free_nodes.push_back(pCur_node);
285 pCur_node = pCur_node->m_pNext;
290 VOGL_ASSERT(free_nodes.size() == m_total_free_nodes);
292 // Now put all block pointers into the blocks array and sort it by address
293 vogl::vector<block *> blocks;
294 blocks.reserve((uint)m_total_blocks);
296 block *pCur_block = m_blocks.m_pNext;
297 while (pCur_block != &m_blocks)
299 blocks.push_back(pCur_block);
300 pCur_block = pCur_block->m_pNext;
303 VOGL_ASSERT(blocks.size() == m_total_blocks);
307 // Now find which block each free node pointer belongs in, and keep a tally of the # of free nodes we've found in each block (along with the first block index for each block)
308 vogl::vector<uint> free_nodes_in_block(blocks.size());
309 vogl::vector<uint> first_node_indices(blocks.size());
311 int prev_block_index = -1;
313 for (uint i = 0; i < free_nodes.size(); i++)
315 node *pNode = free_nodes[i];
317 if (prev_block_index >= 0)
319 node *pFirst_node = blocks[prev_block_index]->get_first_node_ptr();
320 node *pEnd_node = blocks[prev_block_index]->get_end_node_ptr();
322 if ((pNode >= pFirst_node) && (pNode < pEnd_node))
324 free_nodes_in_block[prev_block_index]++;
329 // Binary search to find which block this node belongs in
330 int l = 0, h = blocks.size() - 1;
333 int m = l + ((h - l) >> 1);
334 node *pFirst_node = blocks[m]->get_first_node_ptr();
335 node *pEnd_node = blocks[m]->get_end_node_ptr();
337 if ((pNode >= pFirst_node) && (pNode < pEnd_node))
339 // We've found which block this node belongs to. See if all nodes in this block are free.
340 first_node_indices[m] = i;
341 free_nodes_in_block[m]++;
342 prev_block_index = m;
344 size_t n = blocks[m]->m_total_nodes;
345 if ((n > 1) && ((i + n - 1) < free_nodes.size()))
347 pNode = free_nodes[(uint)(i + n - 1)];
348 if (pNode == (pEnd_node - 1))
350 free_nodes_in_block[m] = (uint)n;
357 else if (pNode >= pEnd_node)
366 m_update_flag = false;
371 // Now loop through each block and free the ones that have all-freed nodes
372 size_t total_nodes_freed = 0;
373 size_t total_blocks_freed = 0;
374 size_t total_bytes_freed = 0;
376 size_t prev_highwater_free_node_index = 0;
378 for (uint block_index = 0; block_index < blocks.size(); ++block_index)
380 block *pBlock = blocks[block_index];
382 if (pBlock->m_total_nodes != free_nodes_in_block[block_index])
385 size_t total_nodes = pBlock->m_total_nodes;
387 VOGL_ASSERT(m_total_nodes >= total_nodes);
388 m_total_nodes -= total_nodes;
390 VOGL_ASSERT(m_total_free_nodes >= total_nodes);
391 m_total_free_nodes -= total_nodes;
393 VOGL_ASSERT(m_total_blocks);
396 size_t block_size_in_bytes = vogl_msize(pBlock);
397 total_bytes_freed += block_size_in_bytes;
399 VOGL_ASSERT(m_total_heap_bytes >= block_size_in_bytes);
400 m_total_heap_bytes -= block_size_in_bytes;
402 total_nodes_freed += total_nodes;
404 uint first_node_index = first_node_indices[block_index];
406 VOGL_ASSERT(first_node_index >= prev_highwater_free_node_index);
408 if (!total_blocks_freed)
409 m_pFirst_free_node = NULL;
411 // Put any free nodes before the ones we're removing back into the freelist
412 // TODO: This just puts the nodes back in any old order. This should prioritize the freelist order by those blocks which are must occupied.
413 size_t n = first_node_index - prev_highwater_free_node_index;
414 for (size_t i = 0; i < n; i++)
416 node *pFree_node = free_nodes[(uint)(prev_highwater_free_node_index + i)];
417 pFree_node->m_pNext = m_pFirst_free_node;
418 m_pFirst_free_node = pFree_node;
421 prev_highwater_free_node_index = first_node_index + total_nodes;
425 total_blocks_freed++;
427 blocks[block_index] = NULL;
430 if (!total_blocks_freed)
432 m_update_flag = false;
436 if (prev_highwater_free_node_index != free_nodes.size())
438 // Put any remaining free nodes before the ones we're removing back into the freelist
439 size_t n = free_nodes.size() - prev_highwater_free_node_index;
440 for (size_t i = 0; i < n; i++)
442 node *pFree_node = free_nodes[(uint)(prev_highwater_free_node_index + i)];
443 pFree_node->m_pNext = m_pFirst_free_node;
444 m_pFirst_free_node = pFree_node;
448 m_blocks.m_pPrev = &m_blocks;
449 m_blocks.m_pNext = &m_blocks;
453 // Now fix up the block list
454 for (uint block_index = 0; block_index < blocks.size(); ++block_index)
456 block *pBlock = blocks[block_index];
459 pBlock->m_pPrev = &m_blocks;
460 pBlock->m_pNext = m_blocks.m_pNext;
462 m_blocks.m_pNext->m_pPrev = pBlock;
463 m_blocks.m_pNext = pBlock;
468 m_update_flag = false;
470 return total_bytes_freed;
473 bool is_valid_ptr(const T *p, bool check_freelist = false) const
478 scoped_lock lock(*this);
480 block *pCur_block = m_blocks.m_pNext;
481 while (pCur_block != &m_blocks)
483 if (pCur_block->m_begin_marker != cBlockBeginMarker)
489 if (pCur_block->m_end_marker != cBlockEndMarker)
495 if (!pCur_block->m_total_nodes)
501 if ((p >= pCur_block->get_first_node_ptr()->get_object_ptr()) && (p <= (pCur_block->get_first_node_ptr() + pCur_block->m_total_nodes - 1)->get_object_ptr()))
503 std::ptrdiff_t ofs = reinterpret_cast<const uint8 *>(p) - reinterpret_cast<uint8 *>(pCur_block->get_first_node_ptr()->get_object_ptr());
504 if (ofs % sizeof(node))
512 node *pCur_node = m_pFirst_free_node;
515 if (p == pCur_node->get_object_ptr())
520 pCur_node = pCur_node->m_pNext;
526 pCur_block = pCur_block->m_pNext;
534 scoped_lock lock(*this);
536 VOGL_ASSERT(!m_update_flag);
538 if (m_total_blocks > static_cast<size_t>(cINT32_MAX))
544 m_update_flag = true;
548 size_t total_blocks_found = 0;
549 size_t total_heap_bytes_found = 0;
551 size_t total_nodes_found = 0;
553 vogl::vector<block *> blocks;
554 blocks.reserve(static_cast<uint>(m_total_blocks));
556 block *pCur_block = m_blocks.m_pNext;
557 while (pCur_block != &m_blocks)
559 if (pCur_block->m_begin_marker != cBlockBeginMarker)
566 if (pCur_block->m_end_marker != cBlockEndMarker)
573 if (!pCur_block->m_total_nodes)
580 size_t block_heap_size = vogl_msize(pCur_block);
581 if (block_heap_size < (sizeof(block) + pCur_block->m_total_nodes * sizeof(node)))
588 total_heap_bytes_found += block_heap_size;
590 total_blocks_found++;
591 if (total_blocks_found > m_total_blocks)
598 total_nodes_found += pCur_block->m_total_nodes;
600 blocks.push_back(pCur_block);
602 pCur_block = pCur_block->m_pNext;
609 m_update_flag = false;
613 if (total_blocks_found != m_total_blocks)
619 if (total_heap_bytes_found != m_total_heap_bytes)
625 size_t total_free_nodes_found = 0;
627 node *pCur_node = m_pFirst_free_node;
630 #if VOGL_OBJECT_POOL_DEBUGGING
631 if (pCur_node->m_marker != cFreeNodeMarker)
639 total_free_nodes_found++;
640 if (total_free_nodes_found > total_nodes_found)
647 int l = 0, h = blocks.size() - 1;
650 int m = l + ((h - l) >> 1);
651 node *pFirst_node = blocks[m]->get_first_node_ptr();
652 node *pEnd_node = blocks[m]->get_end_node_ptr();
654 if ((pCur_node >= pFirst_node) && (pCur_node < pEnd_node))
656 else if (pCur_node >= pEnd_node)
669 pCur_node = pCur_node->m_pNext;
672 if (total_free_nodes_found != m_total_free_nodes)
678 m_update_flag = false;
683 uint get_flags() const
687 size_t get_grow_size() const
691 size_t get_total_blocks() const
693 return m_total_blocks;
695 size_t get_total_heap_bytes() const
697 return m_total_heap_bytes;
699 size_t get_total_nodes() const
701 return m_total_nodes;
703 size_t get_total_free_nodes() const
705 return m_total_free_nodes;
707 size_t get_total_used_nodes() const
709 return m_total_nodes - m_total_free_nodes;
712 void swap(object_pool &other)
714 std::swap(m_flags, other.m_flags);
715 std::swap(m_grow_size, other.m_grow_size);
717 std::swap(m_next_grow_size, other.m_next_grow_size);
719 std::swap(m_total_blocks, other.m_total_blocks);
720 std::swap(m_total_heap_bytes, other.m_total_heap_bytes);
722 std::swap(m_pFirst_free_node, other.m_pFirst_free_node);
723 std::swap(m_total_nodes, other.m_total_nodes);
724 std::swap(m_total_free_nodes, other.m_total_free_nodes);
726 std::swap(m_update_flag, other.m_update_flag);
728 // Now swap m_blocks and other.m_blocks, which is tricky because nodes can point into either.
729 block temp_blocks(other.m_blocks);
731 // move m_blocks into other.m_blocks
732 if (m_blocks.m_pNext == &m_blocks)
733 other.m_blocks.m_pNext = &other.m_blocks;
736 other.m_blocks.m_pNext = m_blocks.m_pNext;
737 VOGL_ASSERT(m_blocks.m_pNext->m_pPrev == &m_blocks);
738 m_blocks.m_pNext->m_pPrev = &other.m_blocks;
741 if (m_blocks.m_pPrev == &m_blocks)
742 other.m_blocks.m_pPrev = &other.m_blocks;
745 other.m_blocks.m_pPrev = m_blocks.m_pPrev;
746 VOGL_ASSERT(m_blocks.m_pPrev->m_pNext == &m_blocks);
747 m_blocks.m_pPrev->m_pNext = &other.m_blocks;
750 // move other.m_blocks into m_blocks
751 if (temp_blocks.m_pNext == &other.m_blocks)
752 m_blocks.m_pNext = &m_blocks;
755 m_blocks.m_pNext = temp_blocks.m_pNext;
756 VOGL_ASSERT(temp_blocks.m_pNext->m_pPrev == &other.m_blocks);
757 temp_blocks.m_pNext->m_pPrev = &m_blocks;
760 if (temp_blocks.m_pPrev == &other.m_blocks)
761 m_blocks.m_pPrev = &m_blocks;
764 m_blocks.m_pPrev = temp_blocks.m_pPrev;
765 VOGL_ASSERT(temp_blocks.m_pPrev->m_pNext == &other.m_blocks);
766 temp_blocks.m_pPrev->m_pNext = &m_blocks;
769 std::swap(m_blocks.m_total_nodes, other.m_blocks.m_total_nodes);
775 cBlockBeginMarker = 0x1234ABCD,
776 cBlockEndMarker = 0xEABC5678,
777 cUsedNodeMarker = 0xCC139876,
778 cFreeNodeMarker = 0xFF137654
783 uint64_t m_bytes[(sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
788 #if VOGL_OBJECT_POOL_DEBUGGING
798 const T *get_object_ptr() const
800 return reinterpret_cast<const T *>(&m_obj);
805 return reinterpret_cast<T *>(&m_obj);
816 size_t m_total_nodes;
820 node *get_first_node_ptr()
822 return reinterpret_cast<node *>(reinterpret_cast<uint8 *>(this) + sizeof(block));
824 node *get_end_node_ptr()
826 return reinterpret_cast<node *>(reinterpret_cast<uint8 *>(this) + sizeof(block)) + m_total_nodes;
833 size_t m_next_grow_size;
836 size_t m_total_blocks;
837 size_t m_total_heap_bytes;
839 node *m_pFirst_free_node;
840 size_t m_total_nodes;
841 size_t m_total_free_nodes;
843 mutable bool m_update_flag;
845 void check_failure(uint line) const
847 console::debug("%s: check_failure() obj %p on line %u\n", VOGL_METHOD_NAME, this, line);
851 block *add_block(size_t size)
854 size = math::maximum<size_t>(1U, size);
856 block *pBlock = static_cast<block *>(vogl_malloc(sizeof(block) + size * sizeof(node)));
859 m_total_heap_bytes += vogl_msize(pBlock);
861 m_total_nodes += size;
862 m_total_free_nodes += size;
864 pBlock->m_begin_marker = cBlockBeginMarker;
865 pBlock->m_end_marker = cBlockEndMarker;
867 pBlock->m_total_nodes = size;
869 pBlock->m_pPrev = &m_blocks;
870 pBlock->m_pNext = m_blocks.m_pNext;
872 VOGL_ASSERT(m_blocks.m_pNext->m_pPrev == &m_blocks);
873 m_blocks.m_pNext->m_pPrev = pBlock;
875 m_blocks.m_pNext = pBlock;
877 for (size_t i = size; i; --i)
879 node *pNode = pBlock->get_first_node_ptr() + i - 1;
881 #if VOGL_OBJECT_POOL_DEBUGGING
882 pNode->m_marker = cFreeNodeMarker;
885 pNode->m_pNext = m_pFirst_free_node;
886 m_pFirst_free_node = pNode;
894 add_block(m_next_grow_size);
896 if (m_flags & cObjectPoolGrowExponential)
898 size_t prev_grow_size = m_next_grow_size;
900 m_next_grow_size <<= 1U;
902 if ((m_next_grow_size >> 1U) != prev_grow_size)
903 m_next_grow_size = prev_grow_size;
906 return m_blocks.m_pNext;
909 inline node *alloc_node()
911 VOGL_ASSERT(!m_update_flag);
913 LockingPolicy::lock();
915 if (!m_pFirst_free_node)
918 VOGL_ASSERT(m_total_free_nodes);
920 node *pNode = m_pFirst_free_node;
922 #if VOGL_OBJECT_POOL_DEBUGGING
923 VOGL_ASSERT(pNode->m_marker == cFreeNodeMarker);
924 pNode->m_marker = cUsedNodeMarker;
927 m_pFirst_free_node = pNode->m_pNext;
929 --m_total_free_nodes;
931 LockingPolicy::unlock();
936 size_t clear_internal()
938 VOGL_ASSERT(!m_update_flag);
940 m_update_flag = true;
942 size_t total_bytes_freed = m_total_heap_bytes;
944 size_t total_blocks_found = 0;
945 VOGL_NOTE_UNUSED(total_blocks_found);
947 block *pCur_block = m_blocks.m_pNext;
948 while (pCur_block != &m_blocks)
950 VOGL_ASSERT(pCur_block->m_begin_marker == cBlockBeginMarker);
951 VOGL_ASSERT(pCur_block->m_end_marker == cBlockEndMarker);
953 total_blocks_found++;
954 VOGL_ASSERT(total_blocks_found <= m_total_blocks);
956 block *pNext_block = pCur_block->m_pNext;
958 vogl_free(pCur_block);
960 pCur_block = pNext_block;
963 VOGL_ASSERT(total_blocks_found == m_total_blocks);
965 m_next_grow_size = math::maximum<size_t>(1U, m_grow_size);
967 m_blocks.m_pPrev = &m_blocks;
968 m_blocks.m_pNext = &m_blocks;
970 m_pFirst_free_node = NULL;
972 m_total_free_nodes = 0;
975 m_total_heap_bytes = 0;
977 m_update_flag = false;
979 return total_bytes_freed;
985 bool object_pool_test();
987 VOGL_NAMESPACE_END(vogl)
989 #endif // VOGL_OBJECT_POOL_H