1 /*-------------------------------------------------------------------------
2 * drawElements Memory Pool Library
3 * --------------------------------
4 *
5 * Copyright 2014 The Android Open Source Project
6 *
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
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
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.
18 *
19 *//*!
20 * \file
21 * \brief Memory pool management.
22 *//*--------------------------------------------------------------------*/
23
24 #include "deMemPool.h"
25 #include "deMemory.h"
26 #include "deInt32.h"
27
28 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
29 # include "deRandom.h"
30 #endif
31
32 #include <stdlib.h>
33 #include <string.h>
34
35 enum
36 {
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. */
40 };
41
42 typedef struct MemPage_s MemPage;
43
44 /*--------------------------------------------------------------------*//*!
45 * \internal
46 * \brief Memory page header.
47 *
48 * Represent a page of memory allocate by a memory pool.
49 *//*--------------------------------------------------------------------*/
50 struct MemPage_s
51 {
52 int capacity;
53 int bytesAllocated;
54
55 MemPage* nextPage;
56 };
57
58 #if defined(DE_SUPPORT_DEBUG_POOLS)
59 typedef struct DebugAlloc_s DebugAlloc;
60
61 struct DebugAlloc_s
62 {
63 void* memPtr;
64 DebugAlloc* next;
65 };
66 #endif
67
68 /*--------------------------------------------------------------------*//*!
69 * \brief Memory pool.
70 *
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
74 * is destroyed.
75 *
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
78 * the pool itself.
79 *
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
84 * fails.
85 *//*--------------------------------------------------------------------*/
86 struct deMemPool_s
87 {
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. */
95
96 MemPage* currentPage; /*!< Current memory page from which to allocate. */
97
98 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
99 deBool allowFailing; /*!< Is allocation failure simulation enabled? */
100 deRandom failRandom; /*!< RNG for failing allocations. */
101 #endif
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. */
105
106 int lastAllocatedIndex; /*!< Index of last allocated pool (rootPool only). */
107 int allocIndex; /*!< Allocation index (running counter). */
108 #endif
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. */
112 #endif
113 };
114
115 /*--------------------------------------------------------------------*//*!
116 * \internal
117 * \brief Initialize a memory page.
118 * \param page Memory page to initialize.
119 * \param capacity Capacity allocated for the memory page.
120 *//*--------------------------------------------------------------------*/
MemPage_init(MemPage * page,size_t capacity)121 static void MemPage_init (MemPage* page, size_t capacity)
122 {
123 memset(page, 0, sizeof(MemPage));
124 #if defined(DE_DEBUG)
125 memset(page + 1, 0xCD, capacity);
126 #endif
127 page->capacity = (int)capacity;
128 }
129
130 /*--------------------------------------------------------------------*//*!
131 * \internal
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 *//*--------------------------------------------------------------------*/
MemPage_create(size_t capacity)136 static MemPage* MemPage_create (size_t capacity)
137 {
138 MemPage* page = (MemPage*)deMalloc(sizeof(MemPage) + capacity);
139 if (!page)
140 return DE_NULL;
141
142 DE_ASSERT(deIsAlignedPtr(page+1, MEM_PAGE_BASE_ALIGN));
143
144 MemPage_init(page, capacity);
145 return page;
146 }
147
148 /*--------------------------------------------------------------------*//*!
149 * \internal
150 * \brief Destroy a memory page.
151 * \param page Memory page to destroy.
152 *//*--------------------------------------------------------------------*/
MemPage_destroy(MemPage * page)153 static void MemPage_destroy (MemPage* page)
154 {
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);
159 #endif
160 deFree(page);
161 }
162
163 /*--------------------------------------------------------------------*//*!
164 * \internal
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 *//*--------------------------------------------------------------------*/
createPoolInternal(deMemPool * parent)169 static deMemPool* createPoolInternal (deMemPool* parent)
170 {
171 deMemPool* pool;
172 MemPage* initialPage;
173
174 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
175 if (parent && parent->allowFailing)
176 {
177 if ((deRandom_getUint32(&parent->failRandom) & 16383) <= 15)
178 return DE_NULL;
179 }
180 #endif
181
182 /* Init first page. */
183 initialPage = MemPage_create(INITIAL_PAGE_SIZE);
184 if (!initialPage)
185 return DE_NULL;
186
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);
191
192 memset(pool, 0, sizeof(deMemPool));
193 pool->currentPage = initialPage;
194
195 /* Register to parent. */
196 pool->parent = parent;
197 if (parent)
198 {
199 parent->numChildren++;
200 if (parent->firstChild) parent->firstChild->prevPool = pool;
201 pool->nextPool = parent->firstChild;
202 parent->firstChild = pool;
203 }
204
205 /* Get utils from parent. */
206 pool->util = parent ? parent->util : DE_NULL;
207
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);
211 #endif
212
213 #if defined(DE_SUPPORT_DEBUG_POOLS)
214 pool->enableDebugAllocs = parent ? parent->enableDebugAllocs : DE_FALSE;
215 pool->debugAllocListHead = DE_NULL;
216
217 /* Pool allocation index. */
218 {
219 deMemPool* root = pool;
220 while (root->parent)
221 root = root->parent;
222
223 if (pool == root)
224 root->lastAllocatedIndex = 0;
225
226 pool->allocIndex = ++root->lastAllocatedIndex;
227
228 /* \note Put the index of leaking pool here and add a breakpoint to catch leaks easily. */
229 /* if (pool->allocIndex == 51)
230 root = root;*/
231 }
232 #endif
233
234 return pool;
235 }
236
237 /*--------------------------------------------------------------------*//*!
238 * \brief Create a new root memory pool.
239 * \return The created memory pool (or null on failure).
240 *//*--------------------------------------------------------------------*/
deMemPool_createRoot(const deMemPoolUtil * util,deUint32 flags)241 deMemPool* deMemPool_createRoot (const deMemPoolUtil* util, deUint32 flags)
242 {
243 deMemPool* pool = createPoolInternal(DE_NULL);
244 if (!pool)
245 return DE_NULL;
246 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
247 if (flags & DE_MEMPOOL_ENABLE_FAILING_ALLOCS)
248 pool->allowFailing = DE_TRUE;
249 #endif
250 #if defined(DE_SUPPORT_DEBUG_POOLS)
251 if (flags & DE_MEMPOOL_ENABLE_DEBUG_ALLOCS)
252 {
253 pool->enableDebugAllocs = DE_TRUE;
254 pool->debugAllocListHead = DE_NULL;
255 }
256 #endif
257 DE_UNREF(flags); /* in case no debug features enabled */
258
259 /* Get copy of utilities. */
260 if (util)
261 {
262 deMemPoolUtil* utilCopy = DE_POOL_NEW(pool, deMemPoolUtil);
263 DE_ASSERT(util->allocFailCallback);
264 if (!utilCopy)
265 {
266 deMemPool_destroy(pool);
267 return DE_NULL;
268 }
269
270 memcpy(utilCopy, util, sizeof(deMemPoolUtil));
271 pool->util = utilCopy;
272 }
273
274 return pool;
275 }
276
277 /*--------------------------------------------------------------------*//*!
278 * \brief Create a sub-pool for an existing memory pool.
279 * \return The created memory pool (or null on failure).
280 *//*--------------------------------------------------------------------*/
deMemPool_create(deMemPool * parent)281 deMemPool* deMemPool_create (deMemPool* parent)
282 {
283 deMemPool* pool;
284 DE_ASSERT(parent);
285 pool = createPoolInternal(parent);
286 if (!pool && parent->util)
287 parent->util->allocFailCallback(parent->util->userPointer);
288 return pool;
289 }
290
291 /*--------------------------------------------------------------------*//*!
292 * \brief Destroy a memory pool.
293 * \param pool Pool to be destroyed.
294 *
295 * Frees all the memory allocated from the pool. Also destroyed any child
296 * pools that the pool has (recursively).
297 *//*--------------------------------------------------------------------*/
deMemPool_destroy(deMemPool * pool)298 void deMemPool_destroy (deMemPool* pool)
299 {
300 deMemPool* iter;
301 deMemPool* iterNext;
302
303 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
304 /* Update memory consumption statistics. */
305 if (pool->parent)
306 {
307 deMemPool* root = pool->parent;
308 while (root->parent)
309 root = root->parent;
310 root->maxMemoryAllocated = deMax32(root->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(root, DE_TRUE));
311 root->maxMemoryCapacity = deMax32(root->maxMemoryCapacity, deMemPool_getCapacity(root, DE_TRUE));
312 }
313 #endif
314
315 /* Destroy all children. */
316 iter = pool->firstChild;
317 while (iter)
318 {
319 iterNext = iter->nextPool;
320 deMemPool_destroy(iter);
321 iter = iterNext;
322 }
323
324 DE_ASSERT(pool->numChildren == 0);
325
326 /* Update pointers. */
327 if (pool->prevPool) pool->prevPool->nextPool = pool->nextPool;
328 if (pool->nextPool) pool->nextPool->prevPool = pool->prevPool;
329
330 if (pool->parent)
331 {
332 deMemPool* parent = pool->parent;
333 if (parent->firstChild == pool)
334 parent->firstChild = pool->nextPool;
335
336 parent->numChildren--;
337 DE_ASSERT(parent->numChildren >= 0);
338 }
339
340 #if defined(DE_SUPPORT_DEBUG_POOLS)
341 /* Free all debug allocations. */
342 if (pool->enableDebugAllocs)
343 {
344 DebugAlloc* alloc = pool->debugAllocListHead;
345 DebugAlloc* next;
346
347 while (alloc)
348 {
349 next = alloc->next;
350 deAlignedFree(alloc->memPtr);
351 deFree(alloc);
352 alloc = next;
353 }
354
355 pool->debugAllocListHead = DE_NULL;
356 }
357 #endif
358
359 /* Free pages. */
360 /* \note Pool itself is allocated from first page, so we must not touch the pool after freeing the page! */
361 {
362 MemPage* page = pool->currentPage;
363 MemPage* nextPage;
364
365 while (page)
366 {
367 nextPage = page->nextPage;
368 MemPage_destroy(page);
369 page = nextPage;
370 }
371 }
372 }
373
374 /*--------------------------------------------------------------------*//*!
375 * \brief Get the number of children for a pool.
376 * \return The number of (immediate) child pools a memory pool has.
377 *//*--------------------------------------------------------------------*/
deMemPool_getNumChildren(const deMemPool * pool)378 int deMemPool_getNumChildren (const deMemPool* pool)
379 {
380 return pool->numChildren;
381 }
382
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 *//*--------------------------------------------------------------------*/
deMemPool_getNumAllocatedBytes(const deMemPool * pool,deBool recurse)390 int deMemPool_getNumAllocatedBytes (const deMemPool* pool, deBool recurse)
391 {
392 int numAllocatedBytes = 0;
393 MemPage* memPage;
394
395 for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
396 numAllocatedBytes += memPage->bytesAllocated;
397
398 if (recurse)
399 {
400 deMemPool* child;
401 for (child = pool->firstChild; child; child = child->nextPool)
402 numAllocatedBytes += deMemPool_getNumAllocatedBytes(child, DE_TRUE);
403 }
404
405 return numAllocatedBytes;
406 }
407
deMemPool_getCapacity(const deMemPool * pool,deBool recurse)408 int deMemPool_getCapacity (const deMemPool* pool, deBool recurse)
409 {
410 int numCapacityBytes = 0;
411 MemPage* memPage;
412
413 for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
414 numCapacityBytes += memPage->capacity;
415
416 if (recurse)
417 {
418 deMemPool* child;
419 for (child = pool->firstChild; child; child = child->nextPool)
420 numCapacityBytes += deMemPool_getCapacity(child, DE_TRUE);
421 }
422
423 return numCapacityBytes;
424 }
425
deMemPool_allocInternal(deMemPool * pool,size_t numBytes,deUint32 alignBytes)426 DE_INLINE void* deMemPool_allocInternal (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
427 {
428 MemPage* curPage = pool->currentPage;
429
430 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
431 if (pool->allowFailing)
432 {
433 if ((deRandom_getUint32(&pool->failRandom) & 16383) <= 15)
434 return DE_NULL;
435 }
436 #endif
437
438 #if defined(DE_SUPPORT_DEBUG_POOLS)
439 if (pool->enableDebugAllocs)
440 {
441 DebugAlloc* header = DE_NEW(DebugAlloc);
442 void* ptr = deAlignedMalloc(numBytes, alignBytes);
443
444 if (!header || !ptr)
445 {
446 deFree(header);
447 deAlignedFree(ptr);
448 return DE_NULL;
449 }
450
451 header->memPtr = ptr;
452 header->next = pool->debugAllocListHead;
453 pool->debugAllocListHead = header;
454
455 return ptr;
456 }
457 #endif
458
459 DE_ASSERT(curPage);
460 DE_ASSERT(deIsPowerOfTwo32((int)alignBytes));
461 {
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);
465
466 if (numBytes + alignPadding > (size_t)(curPage->capacity - curPage->bytesAllocated))
467 {
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);
471
472 curPage = MemPage_create((size_t)newPageCapacity);
473 if (!curPage)
474 return DE_NULL;
475
476 curPage->nextPage = pool->currentPage;
477 pool->currentPage = curPage;
478
479 DE_ASSERT(curPage->bytesAllocated == 0);
480
481 curPagePtr = (void*)(curPage + 1);
482 alignedPtr = deAlignPtr(curPagePtr, alignBytes);
483 alignPadding = (size_t)((deUintptr)alignedPtr - (deUintptr)curPagePtr);
484
485 DE_ASSERT(numBytes + alignPadding <= (size_t)curPage->capacity);
486 }
487
488 curPage->bytesAllocated += (int)(numBytes + alignPadding);
489 return alignedPtr;
490 }
491 }
492
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 *//*--------------------------------------------------------------------*/
deMemPool_alloc(deMemPool * pool,size_t numBytes)499 void* deMemPool_alloc (deMemPool* pool, size_t numBytes)
500 {
501 void* ptr;
502 DE_ASSERT(pool);
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);
507 return ptr;
508 }
509
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 *//*--------------------------------------------------------------------*/
deMemPool_alignedAlloc(deMemPool * pool,size_t numBytes,deUint32 alignBytes)517 void* deMemPool_alignedAlloc (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
518 {
519 void* ptr;
520 DE_ASSERT(pool);
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);
527 return ptr;
528 }
529
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 *//*--------------------------------------------------------------------*/
deMemPool_memDup(deMemPool * pool,const void * ptr,size_t numBytes)536 void* deMemPool_memDup (deMemPool* pool, const void* ptr, size_t numBytes)
537 {
538 void* newPtr = deMemPool_alloc(pool, numBytes);
539 if (newPtr)
540 memcpy(newPtr, ptr, numBytes);
541 return newPtr;
542 }
543
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 *//*--------------------------------------------------------------------*/
deMemPool_strDup(deMemPool * pool,const char * str)550 char* deMemPool_strDup (deMemPool* pool, const char* str)
551 {
552 size_t len = strlen(str);
553 char* newStr = (char*)deMemPool_alloc(pool, len+1);
554 if (newStr)
555 memcpy(newStr, str, len+1);
556 return newStr;
557 }
558
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 *//*--------------------------------------------------------------------*/
deMemPool_strnDup(deMemPool * pool,const char * str,int maxLength)566 char* deMemPool_strnDup (deMemPool* pool, const char* str, int maxLength)
567 {
568 size_t len = (size_t)deMin32((int)strlen(str), deMax32(0, maxLength));
569 char* newStr = (char*)deMemPool_alloc(pool, len + 1);
570
571 DE_ASSERT(maxLength >= 0);
572
573 if (newStr)
574 {
575 memcpy(newStr, str, len);
576 newStr[len] = 0;
577 }
578 return newStr;
579 }
580
581 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
582
deMemPool_getMaxNumAllocatedBytes(const deMemPool * pool)583 int deMemPool_getMaxNumAllocatedBytes (const deMemPool* pool)
584 {
585 DE_ASSERT(pool && !pool->parent); /* must be root */
586 return deMax32(pool->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(pool, DE_TRUE));
587 }
588
deMemPool_getMaxCapacity(const deMemPool * pool)589 int deMemPool_getMaxCapacity (const deMemPool* pool)
590 {
591 DE_ASSERT(pool && !pool->parent); /* must be root */
592 return deMax32(pool->maxMemoryCapacity, deMemPool_getCapacity(pool, DE_TRUE));
593 }
594
595 #endif
596