heapsimple.cpp@ 8911

Last change on this file since 8911 was 8245, checked in by vboxsync, 17 years ago
rebranding: IPRT files again.
Property svn:keywords set to `Id`
File size: 30.6 KB

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

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

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

Download in other formats: