1 /*-------------------------------------------------------------------------
2 * drawElements Memory Pool Library
3 * --------------------------------
5 * Copyright 2014 The Android Open Source Project
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
21 * \brief Memory pool management.
22 *//*--------------------------------------------------------------------*/
24 #include "deMemPool.h"
28 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
29 # include "deRandom.h"
37 INITIAL_PAGE_SIZE = 128, /*!< Size for the first allocated memory page. */
38 MAX_PAGE_SIZE = 8096, /*!< Maximum size for a memory page. */
39 MEM_PAGE_BASE_ALIGN = 4 /*!< Base alignment guarantee for mem page data ptr. */
42 typedef struct MemPage_s MemPage;
44 /*--------------------------------------------------------------------*//*!
46 * \brief Memory page header.
48 * Represent a page of memory allocate by a memory pool.
49 *//*--------------------------------------------------------------------*/
58 #if defined(DE_SUPPORT_DEBUG_POOLS)
59 typedef struct DebugAlloc_s DebugAlloc;
68 /*--------------------------------------------------------------------*//*!
71 * A pool of memory from which individual memory allocations can be made.
72 * The memory pools don't have a freeing operation for individual allocations,
73 * but rather all of the memory allocated from a pool is freed when the pool
76 * The pools can be arranged into a hierarchy. If a pool with children is
77 * destroyed, all of the children are first recursively destroyed and then
80 * The memory pools support a feature where individual allocations can be
81 * made to simulate failure (i.e., return null). This can be enabled by
82 * creating the root pool with the deMemPool_createFailingRoot() function.
83 * When the feature is enabled, also creation of sub-pools occasionally
85 *//*--------------------------------------------------------------------*/
88 deUint32 flags; /*!< Flags. */
89 deMemPool* parent; /*!< Pointer to parent (null for root pools). */
90 deMemPoolUtil* util; /*!< Utilities (callbacks etc.). */
91 int numChildren; /*!< Number of child pools. */
92 deMemPool* firstChild; /*!< Pointer to first child pool in linked list. */
93 deMemPool* prevPool; /*!< Previous pool in parent's linked list. */
94 deMemPool* nextPool; /*!< Next pool in parent's linked list. */
96 MemPage* currentPage; /*!< Current memory page from which to allocate. */
98 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
99 deBool allowFailing; /*!< Is allocation failure simulation enabled? */
100 deRandom failRandom; /*!< RNG for failing allocations. */
102 #if defined(DE_SUPPORT_DEBUG_POOLS)
103 deBool enableDebugAllocs; /*!< If true, always allocates using deMalloc(). */
104 DebugAlloc* debugAllocListHead; /*!< List of allocation in debug mode. */
106 int lastAllocatedIndex; /*!< Index of last allocated pool (rootPool only). */
107 int allocIndex; /*!< Allocation index (running counter). */
109 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
110 int maxMemoryAllocated; /*!< Maximum amount of memory allocated from pools. */
111 int maxMemoryCapacity; /*!< Maximum amount of memory allocated for pools. */
115 /*--------------------------------------------------------------------*//*!
117 * \brief Initialize a memory page.
118 * \param page Memory page to initialize.
119 * \param capacity Capacity allocated for the memory page.
120 *//*--------------------------------------------------------------------*/
121 static void MemPage_init (MemPage* page, size_t capacity)
123 memset(page, 0, sizeof(MemPage));
124 #if defined(DE_DEBUG)
125 memset(page + 1, 0xCD, capacity);
127 page->capacity = (int)capacity;
130 /*--------------------------------------------------------------------*//*!
132 * \brief Create a new memory page.
133 * \param capacity Capacity for the memory page.
134 * \return The created memory page (or null on failure).
135 *//*--------------------------------------------------------------------*/
136 static MemPage* MemPage_create (size_t capacity)
138 MemPage* page = (MemPage*)deMalloc(sizeof(MemPage) + capacity);
142 DE_ASSERT(deIsAlignedPtr(page+1, MEM_PAGE_BASE_ALIGN));
144 MemPage_init(page, capacity);
148 /*--------------------------------------------------------------------*//*!
150 * \brief Destroy a memory page.
151 * \param page Memory page to destroy.
152 *//*--------------------------------------------------------------------*/
153 static void MemPage_destroy (MemPage* page)
155 #if defined(DE_DEBUG)
156 /* Fill with garbage to hopefully catch dangling pointer bugs easier. */
157 deUint8* dataPtr = (deUint8*)(page + 1);
158 memset(dataPtr, 0xCD, (size_t)page->capacity);
163 /*--------------------------------------------------------------------*//*!
165 * \brief Internal function for creating a new memory pool.
166 * \param parent Parent pool (may be null).
167 * \return The created memory pool (or null on failure).
168 *//*--------------------------------------------------------------------*/
169 static deMemPool* createPoolInternal (deMemPool* parent)
172 MemPage* initialPage;
174 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
175 if (parent && parent->allowFailing)
177 if ((deRandom_getUint32(&parent->failRandom) & 16383) <= 15)
182 /* Init first page. */
183 initialPage = MemPage_create(INITIAL_PAGE_SIZE);
187 /* Alloc pool from initial page. */
188 DE_ASSERT((int)sizeof(deMemPool) <= initialPage->capacity);
189 pool = (deMemPool*)(initialPage + 1);
190 initialPage->bytesAllocated += (int)sizeof(deMemPool);
192 memset(pool, 0, sizeof(deMemPool));
193 pool->currentPage = initialPage;
195 /* Register to parent. */
196 pool->parent = parent;
199 parent->numChildren++;
200 if (parent->firstChild) parent->firstChild->prevPool = pool;
201 pool->nextPool = parent->firstChild;
202 parent->firstChild = pool;
205 /* Get utils from parent. */
206 pool->util = parent ? parent->util : DE_NULL;
208 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
209 pool->allowFailing = parent ? parent->allowFailing : DE_FALSE;
210 deRandom_init(&pool->failRandom, parent ? deRandom_getUint32(&parent->failRandom) : 0x1234abcd);
213 #if defined(DE_SUPPORT_DEBUG_POOLS)
214 pool->enableDebugAllocs = parent ? parent->enableDebugAllocs : DE_FALSE;
215 pool->debugAllocListHead = DE_NULL;
217 /* Pool allocation index. */
219 deMemPool* root = pool;
224 root->lastAllocatedIndex = 0;
226 pool->allocIndex = ++root->lastAllocatedIndex;
228 /* \note Put the index of leaking pool here and add a breakpoint to catch leaks easily. */
229 /* if (pool->allocIndex == 51)
237 /*--------------------------------------------------------------------*//*!
238 * \brief Create a new root memory pool.
239 * \return The created memory pool (or null on failure).
240 *//*--------------------------------------------------------------------*/
241 deMemPool* deMemPool_createRoot (const deMemPoolUtil* util, deUint32 flags)
243 deMemPool* pool = createPoolInternal(DE_NULL);
246 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
247 if (flags & DE_MEMPOOL_ENABLE_FAILING_ALLOCS)
248 pool->allowFailing = DE_TRUE;
250 #if defined(DE_SUPPORT_DEBUG_POOLS)
251 if (flags & DE_MEMPOOL_ENABLE_DEBUG_ALLOCS)
253 pool->enableDebugAllocs = DE_TRUE;
254 pool->debugAllocListHead = DE_NULL;
257 DE_UNREF(flags); /* in case no debug features enabled */
259 /* Get copy of utilities. */
262 deMemPoolUtil* utilCopy = DE_POOL_NEW(pool, deMemPoolUtil);
263 DE_ASSERT(util->allocFailCallback);
266 deMemPool_destroy(pool);
270 memcpy(utilCopy, util, sizeof(deMemPoolUtil));
271 pool->util = utilCopy;
277 /*--------------------------------------------------------------------*//*!
278 * \brief Create a sub-pool for an existing memory pool.
279 * \return The created memory pool (or null on failure).
280 *//*--------------------------------------------------------------------*/
281 deMemPool* deMemPool_create (deMemPool* parent)
285 pool = createPoolInternal(parent);
286 if (!pool && parent->util)
287 parent->util->allocFailCallback(parent->util->userPointer);
291 /*--------------------------------------------------------------------*//*!
292 * \brief Destroy a memory pool.
293 * \param pool Pool to be destroyed.
295 * Frees all the memory allocated from the pool. Also destroyed any child
296 * pools that the pool has (recursively).
297 *//*--------------------------------------------------------------------*/
298 void deMemPool_destroy (deMemPool* pool)
303 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
304 /* Update memory consumption statistics. */
307 deMemPool* root = pool->parent;
310 root->maxMemoryAllocated = deMax32(root->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(root, DE_TRUE));
311 root->maxMemoryCapacity = deMax32(root->maxMemoryCapacity, deMemPool_getCapacity(root, DE_TRUE));
315 /* Destroy all children. */
316 iter = pool->firstChild;
319 iterNext = iter->nextPool;
320 deMemPool_destroy(iter);
324 DE_ASSERT(pool->numChildren == 0);
326 /* Update pointers. */
327 if (pool->prevPool) pool->prevPool->nextPool = pool->nextPool;
328 if (pool->nextPool) pool->nextPool->prevPool = pool->prevPool;
332 deMemPool* parent = pool->parent;
333 if (parent->firstChild == pool)
334 parent->firstChild = pool->nextPool;
336 parent->numChildren--;
337 DE_ASSERT(parent->numChildren >= 0);
340 #if defined(DE_SUPPORT_DEBUG_POOLS)
341 /* Free all debug allocations. */
342 if (pool->enableDebugAllocs)
344 DebugAlloc* alloc = pool->debugAllocListHead;
350 deAlignedFree(alloc->memPtr);
355 pool->debugAllocListHead = DE_NULL;
360 /* \note Pool itself is allocated from first page, so we must not touch the pool after freeing the page! */
362 MemPage* page = pool->currentPage;
367 nextPage = page->nextPage;
368 MemPage_destroy(page);
374 /*--------------------------------------------------------------------*//*!
375 * \brief Get the number of children for a pool.
376 * \return The number of (immediate) child pools a memory pool has.
377 *//*--------------------------------------------------------------------*/
378 int deMemPool_getNumChildren (const deMemPool* pool)
380 return pool->numChildren;
383 /*--------------------------------------------------------------------*//*!
384 * \brief Get the number of bytes allocated (by the user) from the pool.
385 * \param pool Pool pointer.
386 * \param recurse Is operation recursive to child pools?
387 * \return The number of bytes allocated by the pool (including child pools
388 * if 'recurse' is true).
389 *//*--------------------------------------------------------------------*/
390 int deMemPool_getNumAllocatedBytes (const deMemPool* pool, deBool recurse)
392 int numAllocatedBytes = 0;
395 for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
396 numAllocatedBytes += memPage->bytesAllocated;
401 for (child = pool->firstChild; child; child = child->nextPool)
402 numAllocatedBytes += deMemPool_getNumAllocatedBytes(child, DE_TRUE);
405 return numAllocatedBytes;
408 int deMemPool_getCapacity (const deMemPool* pool, deBool recurse)
410 int numCapacityBytes = 0;
413 for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
414 numCapacityBytes += memPage->capacity;
419 for (child = pool->firstChild; child; child = child->nextPool)
420 numCapacityBytes += deMemPool_getCapacity(child, DE_TRUE);
423 return numCapacityBytes;
426 DE_INLINE void* deMemPool_allocInternal (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
428 MemPage* curPage = pool->currentPage;
430 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
431 if (pool->allowFailing)
433 if ((deRandom_getUint32(&pool->failRandom) & 16383) <= 15)
438 #if defined(DE_SUPPORT_DEBUG_POOLS)
439 if (pool->enableDebugAllocs)
441 DebugAlloc* header = DE_NEW(DebugAlloc);
442 void* ptr = deAlignedMalloc(numBytes, alignBytes);
451 header->memPtr = ptr;
452 header->next = pool->debugAllocListHead;
453 pool->debugAllocListHead = header;
460 DE_ASSERT(deIsPowerOfTwo32((int)alignBytes));
462 void* curPagePtr = (void*)((deUint8*)(curPage + 1) + curPage->bytesAllocated);
463 void* alignedPtr = deAlignPtr(curPagePtr, alignBytes);
464 size_t alignPadding = (size_t)((deUintptr)alignedPtr - (deUintptr)curPagePtr);
466 if (numBytes + alignPadding > (size_t)(curPage->capacity - curPage->bytesAllocated))
468 /* Does not fit to current page. */
469 int maxAlignPadding = deMax32(0, ((int)alignBytes)-MEM_PAGE_BASE_ALIGN);
470 int newPageCapacity = deMax32(deMin32(2*curPage->capacity, MAX_PAGE_SIZE), ((int)numBytes)+maxAlignPadding);
472 curPage = MemPage_create((size_t)newPageCapacity);
476 curPage->nextPage = pool->currentPage;
477 pool->currentPage = curPage;
479 DE_ASSERT(curPage->bytesAllocated == 0);
481 curPagePtr = (void*)(curPage + 1);
482 alignedPtr = deAlignPtr(curPagePtr, alignBytes);
483 alignPadding = (size_t)((deUintptr)alignedPtr - (deUintptr)curPagePtr);
485 DE_ASSERT(numBytes + alignPadding <= (size_t)curPage->capacity);
488 curPage->bytesAllocated += (int)(numBytes + alignPadding);
493 /*--------------------------------------------------------------------*//*!
494 * \brief Allocate memory from a pool.
495 * \param pool Memory pool to allocate from.
496 * \param numBytes Number of bytes to allocate.
497 * \return Pointer to the allocate memory (or null on failure).
498 *//*--------------------------------------------------------------------*/
499 void* deMemPool_alloc (deMemPool* pool, size_t numBytes)
503 DE_ASSERT(numBytes > 0);
504 ptr = deMemPool_allocInternal(pool, numBytes, DE_POOL_DEFAULT_ALLOC_ALIGNMENT);
505 if (!ptr && pool->util)
506 pool->util->allocFailCallback(pool->util->userPointer);
510 /*--------------------------------------------------------------------*//*!
511 * \brief Allocate aligned memory from a pool.
512 * \param pool Memory pool to allocate from.
513 * \param numBytes Number of bytes to allocate.
514 * \param alignBytes Required alignment in bytes, must be power of two.
515 * \return Pointer to the allocate memory (or null on failure).
516 *//*--------------------------------------------------------------------*/
517 void* deMemPool_alignedAlloc (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
521 DE_ASSERT(numBytes > 0);
522 DE_ASSERT(deIsPowerOfTwo32((int)alignBytes));
523 ptr = deMemPool_allocInternal(pool, numBytes, alignBytes);
524 DE_ASSERT(deIsAlignedPtr(ptr, alignBytes));
525 if (!ptr && pool->util)
526 pool->util->allocFailCallback(pool->util->userPointer);
530 /*--------------------------------------------------------------------*//*!
531 * \brief Duplicate a piece of memory into a memory pool.
532 * \param pool Memory pool to allocate from.
533 * \param ptr Piece of memory to duplicate.
534 * \return Pointer to the copied memory block (or null on failure).
535 *//*--------------------------------------------------------------------*/
536 void* deMemPool_memDup (deMemPool* pool, const void* ptr, size_t numBytes)
538 void* newPtr = deMemPool_alloc(pool, numBytes);
540 memcpy(newPtr, ptr, numBytes);
544 /*--------------------------------------------------------------------*//*!
545 * \brief Duplicate a string into a memory pool.
546 * \param pool Memory pool to allocate from.
547 * \param str String to duplicate.
548 * \return Pointer to the new string (or null on failure).
549 *//*--------------------------------------------------------------------*/
550 char* deMemPool_strDup (deMemPool* pool, const char* str)
552 size_t len = strlen(str);
553 char* newStr = (char*)deMemPool_alloc(pool, len+1);
555 memcpy(newStr, str, len+1);
559 /*--------------------------------------------------------------------*//*!
560 * \brief Duplicate a string into a memory pool, with a maximum length.
561 * \param pool Memory pool to allocate from.
562 * \param str String to duplicate.
563 * \param maxLength Maximum number of characters to duplicate.
564 * \return Pointer to the new string (or null on failure).
565 *//*--------------------------------------------------------------------*/
566 char* deMemPool_strnDup (deMemPool* pool, const char* str, int maxLength)
568 size_t len = (size_t)deMin32((int)strlen(str), deMax32(0, maxLength));
569 char* newStr = (char*)deMemPool_alloc(pool, len + 1);
571 DE_ASSERT(maxLength >= 0);
575 memcpy(newStr, str, len);
581 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
583 int deMemPool_getMaxNumAllocatedBytes (const deMemPool* pool)
585 DE_ASSERT(pool && !pool->parent); /* must be root */
586 return deMax32(pool->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(pool, DE_TRUE));
589 int deMemPool_getMaxCapacity (const deMemPool* pool)
591 DE_ASSERT(pool && !pool->parent); /* must be root */
592 return deMax32(pool->maxMemoryCapacity, deMemPool_getCapacity(pool, DE_TRUE));