• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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