heapsimple.cpp@ 25055

Last change on this file since 25055 was 25055, checked in by vboxsync, 15 years ago
iprt/heap.h: Prototypes an offset based variation of the simple heap. Docs in the header only. Cleanup before code fork.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 30.2 KB

Line
1	/* $Id: heapsimple.cpp 25055 2009-11-27 15:45:49Z vboxsync $ */
2	/** @file
3	* IPRT - A Simple Heap.
4	*/
5
6	/*
7	* Copyright (C) 2006-2007 Sun Microsystems, Inc.
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.virtualbox.org. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*
17	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*
26	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27	* Clara, CA 95054 USA or visit http://www.sun.com if you need
28	* additional information or have any questions.
29	*/
30
31
32	/*******************************************************************************
33	* Header Files *
34	*******************************************************************************/
35	#define LOG_GROUP RTLOGGROUP_DEFAULT
36	#include <iprt/heap.h>
37	#include "internal/iprt.h"
38
39	#include <iprt/assert.h>
40	#include <iprt/asm.h>
41	#include <iprt/string.h>
42	#include <iprt/err.h>
43	#include <iprt/log.h>
44	#include <iprt/param.h>
45
46	#include "internal/magics.h"
47
48
49	/*******************************************************************************
50	* Structures and Typedefs *
51	*******************************************************************************/
52	/** Pointer to the heap anchor block. */
53	typedef struct RTHEAPSIMPLEINTERNAL *PRTHEAPSIMPLEINTERNAL;
54	/** Pointer to a heap block. */
55	typedef struct RTHEAPSIMPLEBLOCK *PRTHEAPSIMPLEBLOCK;
56	/** Pointer to a free heap block. */
57	typedef struct RTHEAPSIMPLEFREE *PRTHEAPSIMPLEFREE;
58
59	/**
60	* Structure describing a simple heap block.
61	* If this block is allocated, it is followed by the user data.
62	* If this block is free, see RTHEAPSIMPLEFREE.
63	*/
64	typedef struct RTHEAPSIMPLEBLOCK
65	{
66	/** The next block in the global block list. */
67	PRTHEAPSIMPLEBLOCK pNext;
68	/** The previous block in the global block list. */
69	PRTHEAPSIMPLEBLOCK pPrev;
70	/** Pointer to the heap anchor block. */
71	PRTHEAPSIMPLEINTERNAL pHeap;
72	/** Flags + magic. */
73	uintptr_t fFlags;
74	} RTHEAPSIMPLEBLOCK;
75	AssertCompileSizeAlignment(RTHEAPSIMPLEBLOCK, 16);
76
77	/** The block is free if this flag is set. When cleared it's allocated. */
78	#define RTHEAPSIMPLEBLOCK_FLAGS_FREE ((uintptr_t)RT_BIT(0))
79	/** The magic value. */
80	#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC ((uintptr_t)0xabcdef00)
81	/** The mask that needs to be applied to RTHEAPSIMPLEBLOCK::fFlags to obtain the magic value. */
82	#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK (~(uintptr_t)RT_BIT(0))
83
84	/**
85	* Checks if the specified block is valid or not.
86	* @returns boolean answer.
87	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
88	*/
89	#define RTHEAPSIMPLEBLOCK_IS_VALID(pBlock) \
90	( ((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK) == RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
91
92	/**
93	* Checks if the specified block is valid and in use.
94	* @returns boolean answer.
95	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
96	*/
97	#define RTHEAPSIMPLEBLOCK_IS_VALID_USED(pBlock) \
98	( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK \| RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
99	== RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
100
101	/**
102	* Checks if the specified block is valid and free.
103	* @returns boolean answer.
104	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
105	*/
106	#define RTHEAPSIMPLEBLOCK_IS_VALID_FREE(pBlock) \
107	( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK \| RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
108	== (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE) )
109
110	/**
111	* Checks if the specified block is free or not.
112	* @returns boolean answer.
113	* @param pBlock Pointer to a valid RTHEAPSIMPLEBLOCK structure.
114	*/
115	#define RTHEAPSIMPLEBLOCK_IS_FREE(pBlock) (!!((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_FREE))
116
117	/**
118	* A free heap block.
119	* This is an extended version of RTHEAPSIMPLEBLOCK that takes the unused
120	* user data to store free list pointers and a cached size value.
121	*/
122	typedef struct RTHEAPSIMPLEFREE
123	{
124	/** Core stuff. */
125	RTHEAPSIMPLEBLOCK Core;
126	/** Pointer to the next free block. */
127	PRTHEAPSIMPLEFREE pNext;
128	/** Pointer to the previous free block. */
129	PRTHEAPSIMPLEFREE pPrev;
130	/** The size of the block (excluding the RTHEAPSIMPLEBLOCK part). */
131	size_t cb;
132	/** An alignment filler to make it a multiple of (sizeof(void ) 2). */
133	size_t Alignment;
134	} RTHEAPSIMPLEFREE;
135
136
137	/**
138	* The heap anchor block.
139	* This structure is placed at the head of the memory block specified to RTHeapSimpleInit(),
140	* which means that the first RTHEAPSIMPLEBLOCK appears immediately after this structure.
141	*/
142	typedef struct RTHEAPSIMPLEINTERNAL
143	{
144	/** The typical magic (RTHEAPSIMPLE_MAGIC). */
145	size_t uMagic;
146	/** The heap size. (This structure is included!) */
147	size_t cbHeap;
148	/** Pointer to the end of the heap. */
149	void *pvEnd;
150	/** The amount of free memory in the heap. */
151	size_t cbFree;
152	/** Free head pointer. */
153	PRTHEAPSIMPLEFREE pFreeHead;
154	/** Free tail pointer. */
155	PRTHEAPSIMPLEFREE pFreeTail;
156	/** Make the size of this structure is a multiple of 32. */
157	size_t auAlignment[2];
158	} RTHEAPSIMPLEINTERNAL;
159	AssertCompileSizeAlignment(RTHEAPSIMPLEINTERNAL, 32);
160
161
162	/** The minimum allocation size. */
163	#define RTHEAPSIMPLE_MIN_BLOCK (sizeof(RTHEAPSIMPLEBLOCK))
164	AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEBLOCK));
165	AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEFREE) - sizeof(RTHEAPSIMPLEBLOCK));
166
167	/** The minimum and default alignment. */
168	#define RTHEAPSIMPLE_ALIGNMENT (sizeof(RTHEAPSIMPLEBLOCK))
169
170
171	/*******************************************************************************
172	* Defined Constants And Macros *
173	*******************************************************************************/
174	#ifdef RT_STRICT
175	# define RTHEAPSIMPLE_STRICT 1
176	#endif
177
178	#define ASSERT_L(a, b) AssertMsg((uintptr_t)(a) < (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
179	#define ASSERT_LE(a, b) AssertMsg((uintptr_t)(a) <= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
180	#define ASSERT_G(a, b) AssertMsg((uintptr_t)(a) > (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
181	#define ASSERT_GE(a, b) AssertMsg((uintptr_t)(a) >= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
182	#define ASSERT_ALIGN(a) AssertMsg(!((uintptr_t)(a) & (RTHEAPSIMPLE_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a)))
183
184	#define ASSERT_PREV(pHeapInt, pBlock) \
185	do { ASSERT_ALIGN((pBlock)->pPrev); \
186	if ((pBlock)->pPrev) \
187	{ \
188	ASSERT_L((pBlock)->pPrev, (pBlock)); \
189	ASSERT_GE((pBlock)->pPrev, (pHeapInt) + 1); \
190	} \
191	else \
192	Assert((pBlock) == (PRTHEAPSIMPLEBLOCK)((pHeapInt) + 1)); \
193	} while (0)
194
195	#define ASSERT_NEXT(pHeap, pBlock) \
196	do { ASSERT_ALIGN((pBlock)->pNext); \
197	if ((pBlock)->pNext) \
198	{ \
199	ASSERT_L((pBlock)->pNext, (pHeapInt)->pvEnd); \
200	ASSERT_G((pBlock)->pNext, (pBlock)); \
201	} \
202	} while (0)
203
204	#define ASSERT_BLOCK(pHeapInt, pBlock) \
205	do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID(pBlock), ("%#x\n", (pBlock)->fFlags)); \
206	AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
207	ASSERT_GE((pBlock), (pHeapInt) + 1); \
208	ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
209	ASSERT_NEXT(pHeapInt, pBlock); \
210	ASSERT_PREV(pHeapInt, pBlock); \
211	} while (0)
212
213	#define ASSERT_BLOCK_USED(pHeapInt, pBlock) \
214	do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID_USED((pBlock)), ("%#x\n", (pBlock)->fFlags)); \
215	AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
216	ASSERT_GE((pBlock), (pHeapInt) + 1); \
217	ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
218	ASSERT_NEXT(pHeapInt, pBlock); \
219	ASSERT_PREV(pHeapInt, pBlock); \
220	} while (0)
221
222	#define ASSERT_FREE_PREV(pHeapInt, pBlock) \
223	do { ASSERT_ALIGN((pBlock)->pPrev); \
224	if ((pBlock)->pPrev) \
225	{ \
226	ASSERT_GE((pBlock)->pPrev, (pHeapInt)->pFreeHead); \
227	ASSERT_L((pBlock)->pPrev, (pBlock)); \
228	ASSERT_LE((pBlock)->pPrev, (pBlock)->Core.pPrev); \
229	} \
230	else \
231	Assert((pBlock) == (pHeapInt)->pFreeHead); \
232	} while (0)
233
234	#define ASSERT_FREE_NEXT(pHeapInt, pBlock) \
235	do { ASSERT_ALIGN((pBlock)->pNext); \
236	if ((pBlock)->pNext) \
237	{ \
238	ASSERT_LE((pBlock)->pNext, (pHeapInt)->pFreeTail); \
239	ASSERT_G((pBlock)->pNext, (pBlock)); \
240	ASSERT_GE((pBlock)->pNext, (pBlock)->Core.pNext); \
241	} \
242	else \
243	Assert((pBlock) == (pHeapInt)->pFreeTail); \
244	} while (0)
245
246	#ifdef RTHEAPSIMPLE_STRICT
247	# define ASSERT_FREE_CB(pHeapInt, pBlock) \
248	do { size_t cbCalc = ((pBlock)->Core.pNext ? (uintptr_t)(pBlock)->Core.pNext : (uintptr_t)(pHeapInt)->pvEnd) \
249	- (uintptr_t)(pBlock) - sizeof(RTHEAPSIMPLEBLOCK); \
250	AssertMsg((pBlock)->cb == cbCalc, ("cb=%#zx cbCalc=%#zx\n", (pBlock)->cb, cbCalc)); \
251	} while (0)
252	#else
253	# define ASSERT_FREE_CB(pHeapInt, pBlock) do {} while (0)
254	#endif
255
256	/** Asserts that a free block is valid. */
257	#define ASSERT_BLOCK_FREE(pHeapInt, pBlock) \
258	do { ASSERT_BLOCK(pHeapInt, &(pBlock)->Core); \
259	Assert(RTHEAPSIMPLEBLOCK_IS_VALID_FREE(&(pBlock)->Core)); \
260	ASSERT_GE((pBlock), (pHeapInt)->pFreeHead); \
261	ASSERT_LE((pBlock), (pHeapInt)->pFreeTail); \
262	ASSERT_FREE_NEXT(pHeapInt, pBlock); \
263	ASSERT_FREE_PREV(pHeapInt, pBlock); \
264	ASSERT_FREE_CB(pHeapInt, pBlock); \
265	} while (0)
266
267	/** Asserts that the heap anchor block is ok. */
268	#define ASSERT_ANCHOR(pHeapInt) \
269	do { AssertPtr(pHeapInt);\
270	Assert((pHeapInt)->uMagic == RTHEAPSIMPLE_MAGIC); \
271	} while (0)
272
273
274	/*******************************************************************************
275	* Internal Functions *
276	*******************************************************************************/
277	#ifdef RTHEAPSIMPLE_STRICT
278	static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt);
279	#endif
280	static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment);
281	static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock);
282
283
284	RTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE phHeap, void *pvMemory, size_t cbMemory)
285	{
286	PRTHEAPSIMPLEINTERNAL pHeapInt;
287	PRTHEAPSIMPLEFREE pFree;
288	unsigned i;
289
290	/*
291	* Validate input. The imposed minimum heap size is just a convenient value.
292	*/
293	AssertReturn(cbMemory >= PAGE_SIZE, VERR_INVALID_PARAMETER);
294	AssertPtrReturn(pvMemory, VERR_INVALID_POINTER);
295	AssertReturn((uintptr_t)pvMemory + (cbMemory - 1) > (uintptr_t)cbMemory, VERR_INVALID_PARAMETER);
296
297	/*
298	* Place the heap anchor block at the start of the heap memory,
299	* enforce 32 byte alignment of it. Also align the heap size correctly.
300	*/
301	pHeapInt = (PRTHEAPSIMPLEINTERNAL)pvMemory;
302	if ((uintptr_t)pvMemory & 31)
303	{
304	const uintptr_t off = 32 - ((uintptr_t)pvMemory & 31);
305	cbMemory -= off;
306	pHeapInt = (PRTHEAPSIMPLEINTERNAL)((uintptr_t)pvMemory + off);
307	}
308	cbMemory &= ~(RTHEAPSIMPLE_ALIGNMENT - 1);
309
310
311	/* Init the heap anchor block. */
312	pHeapInt->uMagic = RTHEAPSIMPLE_MAGIC;
313	pHeapInt->pvEnd = (uint8_t *)pHeapInt + cbMemory;
314	pHeapInt->cbHeap = cbMemory;
315	pHeapInt->cbFree = cbMemory
316	- sizeof(RTHEAPSIMPLEBLOCK)
317	- sizeof(RTHEAPSIMPLEINTERNAL);
318	pHeapInt->pFreeTail = pHeapInt->pFreeHead = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
319	for (i = 0; i < RT_ELEMENTS(pHeapInt->auAlignment); i++)
320	pHeapInt->auAlignment[i] = ~(size_t)0;
321
322	/* Init the single free block. */
323	pFree = pHeapInt->pFreeHead;
324	pFree->Core.pNext = NULL;
325	pFree->Core.pPrev = NULL;
326	pFree->Core.pHeap = pHeapInt;
327	pFree->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE;
328	pFree->pNext = NULL;
329	pFree->pPrev = NULL;
330	pFree->cb = pHeapInt->cbFree;
331
332	*phHeap = pHeapInt;
333
334	#ifdef RTHEAPSIMPLE_STRICT
335	rtHeapSimpleAssertAll(pHeapInt);
336	#endif
337	return VINF_SUCCESS;
338	}
339	RT_EXPORT_SYMBOL(RTHeapSimpleInit);
340
341
342	RTDECL(int) RTHeapSimpleRelocate(RTHEAPSIMPLE hHeap, uintptr_t offDelta)
343	{
344	PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
345	PRTHEAPSIMPLEFREE pCur;
346
347	/*
348	* Validate input.
349	*/
350	AssertPtrReturn(pHeapInt, VERR_INVALID_HANDLE);
351	AssertReturn(pHeapInt->uMagic == RTHEAPSIMPLE_MAGIC, VERR_INVALID_HANDLE);
352	AssertMsgReturn((uintptr_t)pHeapInt - (uintptr_t)pHeapInt->pvEnd + pHeapInt->cbHeap == offDelta,
353	("offDelta=%p, expected=%p\n", offDelta, (uintptr_t)pHeapInt->pvEnd - pHeapInt->cbHeap - (uintptr_t)pHeapInt),
354	VERR_INVALID_PARAMETER);
355
356	/*
357	* Relocate the heap anchor block.
358	*/
359	#define RELOCATE_IT(var, type, offDelta) do { if (RT_UNLIKELY((var) != NULL)) { (var) = (type)((uintptr_t)(var) + offDelta); } } while (0)
360	RELOCATE_IT(pHeapInt->pvEnd, void *, offDelta);
361	RELOCATE_IT(pHeapInt->pFreeHead, PRTHEAPSIMPLEFREE, offDelta);
362	RELOCATE_IT(pHeapInt->pFreeTail, PRTHEAPSIMPLEFREE, offDelta);
363
364	/*
365	* Walk the heap blocks.
366	*/
367	for (pCur = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
368	pCur && (uintptr_t)pCur < (uintptr_t)pHeapInt->pvEnd;
369	pCur = (PRTHEAPSIMPLEFREE)pCur->Core.pNext)
370	{
371	RELOCATE_IT(pCur->Core.pNext, PRTHEAPSIMPLEBLOCK, offDelta);
372	RELOCATE_IT(pCur->Core.pPrev, PRTHEAPSIMPLEBLOCK, offDelta);
373	RELOCATE_IT(pCur->Core.pHeap, PRTHEAPSIMPLEINTERNAL, offDelta);
374	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pCur->Core))
375	{
376	RELOCATE_IT(pCur->pNext, PRTHEAPSIMPLEFREE, offDelta);
377	RELOCATE_IT(pCur->pPrev, PRTHEAPSIMPLEFREE, offDelta);
378	}
379	}
380	#undef RELOCATE_IT
381
382	#ifdef RTHEAPSIMPLE_STRICT
383	/*
384	* Give it a once over before we return.
385	*/
386	rtHeapSimpleAssertAll(pHeapInt);
387	#endif
388	return VINF_SUCCESS;
389	}
390	RT_EXPORT_SYMBOL(RTHeapSimpleRelocate);
391
392
393	RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE hHeap, size_t cb, size_t cbAlignment)
394	{
395	PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
396	PRTHEAPSIMPLEBLOCK pBlock;
397
398	/*
399	* Validate and adjust the input.
400	*/
401	AssertPtrReturn(pHeapInt, NULL);
402	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
403	cb = RTHEAPSIMPLE_MIN_BLOCK;
404	else
405	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
406	if (!cbAlignment)
407	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
408	else
409	{
410	Assert(!(cbAlignment & (cbAlignment - 1)));
411	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
412	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
413	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
414	}
415
416	/*
417	* Do the allocation.
418	*/
419	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
420	if (RT_LIKELY(pBlock))
421	{
422	void *pv = pBlock + 1;
423	return pv;
424	}
425	return NULL;
426	}
427	RT_EXPORT_SYMBOL(RTHeapSimpleAlloc);
428
429
430	RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE hHeap, size_t cb, size_t cbAlignment)
431	{
432	PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
433	PRTHEAPSIMPLEBLOCK pBlock;
434
435	/*
436	* Validate and adjust the input.
437	*/
438	AssertPtrReturn(pHeapInt, NULL);
439	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
440	cb = RTHEAPSIMPLE_MIN_BLOCK;
441	else
442	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
443	if (!cbAlignment)
444	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
445	else
446	{
447	Assert(!(cbAlignment & (cbAlignment - 1)));
448	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
449	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
450	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
451	}
452
453	/*
454	* Do the allocation.
455	*/
456	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
457	if (RT_LIKELY(pBlock))
458	{
459	void *pv = pBlock + 1;
460	memset(pv, 0, cb);
461	return pv;
462	}
463	return NULL;
464	}
465	RT_EXPORT_SYMBOL(RTHeapSimpleAllocZ);
466
467
468	/**
469	* Allocates a block of memory from the specified heap.
470	*
471	* No parameter validation or adjustment is performed.
472	*
473	* @returns Pointer to the allocated block.
474	* @returns NULL on failure.
475	*
476	* @param pHeapInt The heap.
477	* @param cb Size of the memory block to allocate.
478	* @param uAlignment The alignment specifications for the allocated block.
479	*/
480	static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment)
481	{
482	PRTHEAPSIMPLEBLOCK pRet = NULL;
483	PRTHEAPSIMPLEFREE pFree;
484
485	#ifdef RTHEAPSIMPLE_STRICT
486	rtHeapSimpleAssertAll(pHeapInt);
487	#endif
488
489	/*
490	* Search for a fitting block from the lower end of the heap.
491	*/
492	for (pFree = pHeapInt->pFreeHead;
493	pFree;
494	pFree = pFree->pNext)
495	{
496	uintptr_t offAlign;
497	ASSERT_BLOCK_FREE(pHeapInt, pFree);
498
499	/*
500	* Match for size and alignment.
501	*/
502	if (pFree->cb < cb)
503	continue;
504	offAlign = (uintptr_t)(&pFree->Core + 1) & (uAlignment - 1);
505	if (offAlign)
506	{
507	RTHEAPSIMPLEFREE Free;
508	PRTHEAPSIMPLEBLOCK pPrev;
509
510	offAlign = uAlignment - offAlign;
511	if (pFree->cb - offAlign < cb)
512	continue;
513
514	/*
515	* Make a stack copy of the free block header and adjust the pointer.
516	*/
517	Free = *pFree;
518	pFree = (PRTHEAPSIMPLEFREE)((uintptr_t)pFree + offAlign);
519
520	/*
521	* Donate offAlign bytes to the node in front of us.
522	* If we're the head node, we'll have to create a fake node. We'll
523	* mark it USED for simplicity.
524	*
525	* (Should this policy of donating memory to the guy in front of us
526	* cause big 'leaks', we could create a new free node if there is room
527	* for that.)
528	*/
529	pPrev = Free.Core.pPrev;
530	if (pPrev)
531	{
532	AssertMsg(!RTHEAPSIMPLEBLOCK_IS_FREE(pPrev), ("Impossible!\n"));
533	pPrev->pNext = &pFree->Core;
534	}
535	else
536	{
537	pPrev = (PRTHEAPSIMPLEBLOCK)(pHeapInt + 1);
538	Assert(pPrev == &pFree->Core);
539	pPrev->pPrev = NULL;
540	pPrev->pNext = &pFree->Core;
541	pPrev->pHeap = pHeapInt;
542	pPrev->fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC;
543	}
544	pHeapInt->cbFree -= offAlign;
545
546	/*
547	* Recreate pFree in the new position and adjust the neighbors.
548	*/
549	*pFree = Free;
550
551	/* the core */
552	if (pFree->Core.pNext)
553	pFree->Core.pNext->pPrev = &pFree->Core;
554	pFree->Core.pPrev = pPrev;
555
556	/* the free part */
557	pFree->cb -= offAlign;
558	if (pFree->pNext)
559	pFree->pNext->pPrev = pFree;
560	else
561	pHeapInt->pFreeTail = pFree;
562	if (pFree->pPrev)
563	pFree->pPrev->pNext = pFree;
564	else
565	pHeapInt->pFreeHead = pFree;
566	ASSERT_BLOCK_FREE(pHeapInt, pFree);
567	ASSERT_BLOCK_USED(pHeapInt, pPrev);
568	}
569
570	/*
571	* Split off a new FREE block?
572	*/
573	if (pFree->cb >= cb + RT_ALIGN_Z(sizeof(RTHEAPSIMPLEFREE), RTHEAPSIMPLE_ALIGNMENT))
574	{
575	/*
576	* Move the FREE block up to make room for the new USED block.
577	*/
578	PRTHEAPSIMPLEFREE pNew = (PRTHEAPSIMPLEFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPSIMPLEBLOCK));
579
580	pNew->Core.pNext = pFree->Core.pNext;
581	if (pFree->Core.pNext)
582	pFree->Core.pNext->pPrev = &pNew->Core;
583	pNew->Core.pPrev = &pFree->Core;
584	pNew->Core.pHeap = pHeapInt;
585	pNew->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE;
586
587	pNew->pNext = pFree->pNext;
588	if (pNew->pNext)
589	pNew->pNext->pPrev = pNew;
590	else
591	pHeapInt->pFreeTail = pNew;
592	pNew->pPrev = pFree->pPrev;
593	if (pNew->pPrev)
594	pNew->pPrev->pNext = pNew;
595	else
596	pHeapInt->pFreeHead = pNew;
597	pNew->cb = (pNew->Core.pNext ? (uintptr_t)pNew->Core.pNext : (uintptr_t)pHeapInt->pvEnd) \
598	- (uintptr_t)pNew - sizeof(RTHEAPSIMPLEBLOCK);
599	ASSERT_BLOCK_FREE(pHeapInt, pNew);
600
601	/*
602	* Update the old FREE node making it a USED node.
603	*/
604	pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
605	pFree->Core.pNext = &pNew->Core;
606	pHeapInt->cbFree -= pFree->cb;
607	pHeapInt->cbFree += pNew->cb;
608	pRet = &pFree->Core;
609	ASSERT_BLOCK_USED(pHeapInt, pRet);
610	}
611	else
612	{
613	/*
614	* Link it out of the free list.
615	*/
616	if (pFree->pNext)
617	pFree->pNext->pPrev = pFree->pPrev;
618	else
619	pHeapInt->pFreeTail = pFree->pPrev;
620	if (pFree->pPrev)
621	pFree->pPrev->pNext = pFree->pNext;
622	else
623	pHeapInt->pFreeHead = pFree->pNext;
624
625	/*
626	* Convert it to a used block.
627	*/
628	pHeapInt->cbFree -= pFree->cb;
629	pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
630	pRet = &pFree->Core;
631	ASSERT_BLOCK_USED(pHeapInt, pRet);
632	}
633	break;
634	}
635
636	#ifdef RTHEAPSIMPLE_STRICT
637	rtHeapSimpleAssertAll(pHeapInt);
638	#endif
639	return pRet;
640	}
641
642
643	RTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE hHeap, void *pv)
644	{
645	PRTHEAPSIMPLEINTERNAL pHeapInt;
646	PRTHEAPSIMPLEBLOCK pBlock;
647
648	/*
649	* Validate input.
650	*/
651	if (!pv)
652	return;
653	AssertPtr(pv);
654	Assert(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv);
655
656	/*
657	* Get the block and heap. If in strict mode, validate these.
658	*/
659	pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
660	pHeapInt = pBlock->pHeap;
661	ASSERT_BLOCK_USED(pHeapInt, pBlock);
662	ASSERT_ANCHOR(pHeapInt);
663	Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)hHeap \|\| !hHeap);
664
665	#ifdef RTHEAPSIMPLE_FREE_POISON
666	/*
667	* Poison the block.
668	*/
669	const size_t cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
670	- (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
671	memset(pBlock + 1, RTHEAPSIMPLE_FREE_POISON, cbBlock);
672	#endif
673
674	/*
675	* Call worker which does the actual job.
676	*/
677	rtHeapSimpleFreeBlock(pHeapInt, pBlock);
678	}
679	RT_EXPORT_SYMBOL(RTHeapSimpleFree);
680
681
682	/**
683	* Free a memory block.
684	*
685	* @param pHeapInt The heap.
686	* @param pBlock The memory block to free.
687	*/
688	static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock)
689	{
690	PRTHEAPSIMPLEFREE pFree = (PRTHEAPSIMPLEFREE)pBlock;
691	PRTHEAPSIMPLEFREE pLeft;
692	PRTHEAPSIMPLEFREE pRight;
693
694	#ifdef RTHEAPSIMPLE_STRICT
695	rtHeapSimpleAssertAll(pHeapInt);
696	#endif
697
698	/*
699	* Look for the closest free list blocks by walking the blocks right
700	* of us (both lists are sorted by address).
701	*/
702	pLeft = NULL;
703	pRight = NULL;
704	if (pHeapInt->pFreeTail)
705	{
706	pRight = (PRTHEAPSIMPLEFREE)pFree->Core.pNext;
707	while (pRight && !RTHEAPSIMPLEBLOCK_IS_FREE(&pRight->Core))
708	{
709	ASSERT_BLOCK(pHeapInt, &pRight->Core);
710	pRight = (PRTHEAPSIMPLEFREE)pRight->Core.pNext;
711	}
712	if (!pRight)
713	pLeft = pHeapInt->pFreeTail;
714	else
715	{
716	ASSERT_BLOCK_FREE(pHeapInt, pRight);
717	pLeft = pRight->pPrev;
718	}
719	if (pLeft)
720	ASSERT_BLOCK_FREE(pHeapInt, pLeft);
721	}
722	AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock));
723	ASSERT_L(pLeft, pFree);
724	Assert(!pRight \|\| (uintptr_t)pRight > (uintptr_t)pFree);
725	Assert(!pLeft \|\| pLeft->pNext == pRight);
726
727	/*
728	* Insert at the head of the free block list?
729	*/
730	if (!pLeft)
731	{
732	Assert(pRight == pHeapInt->pFreeHead);
733	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
734	pFree->pPrev = NULL;
735	pFree->pNext = pRight;
736	if (pRight)
737	pRight->pPrev = pFree;
738	else
739	pHeapInt->pFreeTail = pFree;
740	pHeapInt->pFreeHead = pFree;
741	}
742	else
743	{
744	/*
745	* Can we merge with left hand free block?
746	*/
747	if (pLeft->Core.pNext == &pFree->Core)
748	{
749	pLeft->Core.pNext = pFree->Core.pNext;
750	if (pFree->Core.pNext)
751	pFree->Core.pNext->pPrev = &pLeft->Core;
752	pHeapInt->cbFree -= pLeft->cb;
753	pFree = pLeft;
754	}
755	/*
756	* No, just link it into the free list then.
757	*/
758	else
759	{
760	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
761	pFree->pNext = pRight;
762	pFree->pPrev = pLeft;
763	pLeft->pNext = pFree;
764	if (pRight)
765	pRight->pPrev = pFree;
766	else
767	pHeapInt->pFreeTail = pFree;
768	}
769	}
770
771	/*
772	* Can we merge with right hand free block?
773	*/
774	if ( pRight
775	&& pRight->Core.pPrev == &pFree->Core)
776	{
777	/* core */
778	pFree->Core.pNext = pRight->Core.pNext;
779	if (pRight->Core.pNext)
780	pRight->Core.pNext->pPrev = &pFree->Core;
781
782	/* free */
783	pFree->pNext = pRight->pNext;
784	if (pRight->pNext)
785	pRight->pNext->pPrev = pFree;
786	else
787	pHeapInt->pFreeTail = pFree;
788	pHeapInt->cbFree -= pRight->cb;
789	}
790
791	/*
792	* Calculate the size and update free stats.
793	*/
794	pFree->cb = (pFree->Core.pNext ? (uintptr_t)pFree->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
795	- (uintptr_t)pFree - sizeof(RTHEAPSIMPLEBLOCK);
796	pHeapInt->cbFree += pFree->cb;
797	ASSERT_BLOCK_FREE(pHeapInt, pFree);
798
799	#ifdef RTHEAPSIMPLE_STRICT
800	rtHeapSimpleAssertAll(pHeapInt);
801	#endif
802	}
803
804
805	#ifdef RTHEAPSIMPLE_STRICT
806	/**
807	* Internal consistency check (relying on assertions).
808	* @param pHeapInt
809	*/
810	static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt)
811	{
812	PRTHEAPSIMPLEFREE pPrev = NULL;
813	PRTHEAPSIMPLEFREE pPrevFree = NULL;
814	PRTHEAPSIMPLEFREE pBlock;
815	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
816	pBlock;
817	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
818	{
819	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
820	{
821	ASSERT_BLOCK_FREE(pHeapInt, pBlock);
822	Assert(pBlock->pPrev == pPrevFree);
823	Assert(pPrevFree \|\| pHeapInt->pFreeHead == pBlock);
824	pPrevFree = pBlock;
825	}
826	else
827	ASSERT_BLOCK_USED(pHeapInt, &pBlock->Core);
828	Assert(!pPrev \|\| pPrev == (PRTHEAPSIMPLEFREE)pBlock->Core.pPrev);
829	pPrev = pBlock;
830	}
831	Assert(pHeapInt->pFreeTail == pPrevFree);
832	}
833	#endif
834
835
836	RTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE hHeap, void *pv)
837	{
838	PRTHEAPSIMPLEINTERNAL pHeapInt;
839	PRTHEAPSIMPLEBLOCK pBlock;
840	size_t cbBlock;
841
842	/*
843	* Validate input.
844	*/
845	if (!pv)
846	return 0;
847	AssertPtrReturn(pv, 0);
848	AssertReturn(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv, 0);
849
850	/*
851	* Get the block and heap. If in strict mode, validate these.
852	*/
853	pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
854	pHeapInt = pBlock->pHeap;
855	ASSERT_BLOCK_USED(pHeapInt, pBlock);
856	ASSERT_ANCHOR(pHeapInt);
857	Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)hHeap \|\| !hHeap);
858
859	/*
860	* Calculate the block size.
861	*/
862	cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
863	- (uintptr_t)pBlock- sizeof(RTHEAPSIMPLEBLOCK);
864	return cbBlock;
865	}
866	RT_EXPORT_SYMBOL(RTHeapSimpleSize);
867
868
869	RTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE hHeap)
870	{
871	PRTHEAPSIMPLEINTERNAL pHeapInt;
872
873	if (hHeap == NIL_RTHEAPSIMPLE)
874	return 0;
875
876	pHeapInt = hHeap;
877	AssertPtrReturn(pHeapInt, 0);
878	ASSERT_ANCHOR(pHeapInt);
879	return pHeapInt->cbHeap;
880	}
881	RT_EXPORT_SYMBOL(RTHeapSimpleGetHeapSize);
882
883
884	RTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE hHeap)
885	{
886	PRTHEAPSIMPLEINTERNAL pHeapInt;
887
888	if (hHeap == NIL_RTHEAPSIMPLE)
889	return 0;
890
891	pHeapInt = hHeap;
892	AssertPtrReturn(pHeapInt, 0);
893	ASSERT_ANCHOR(pHeapInt);
894	return pHeapInt->cbFree;
895	}
896	RT_EXPORT_SYMBOL(RTHeapSimpleGetFreeSize);
897
898
899	RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE hHeap, PFNRTHEAPSIMPLEPRINTF pfnPrintf)
900	{
901	PRTHEAPSIMPLEINTERNAL pHeapInt = (PRTHEAPSIMPLEINTERNAL)hHeap;
902	PRTHEAPSIMPLEFREE pBlock;
903
904	pfnPrintf("** Dumping Heap %p - cbHeap=%zx cbFree=%zx **\n",
905	hHeap, pHeapInt->cbHeap, pHeapInt->cbFree);
906
907	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
908	pBlock;
909	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
910	{
911	size_t cb = (pBlock->pNext ? (uintptr_t)pBlock->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
912	- (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
913	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
914	pfnPrintf("%p %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
915	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb,
916	pBlock->cb, pBlock->pNext, pBlock->pPrev);
917	else
918	pfnPrintf("%p %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",
919	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb);
920	}
921	pfnPrintf("** Done dumping Heap %p **\n", hHeap);
922	}
923	RT_EXPORT_SYMBOL(RTHeapSimpleDump);
924

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Runtime/common/alloc/heapsimple.cpp@ 25055

Download in other formats: