heapsimple.cpp@ 7169

Last change on this file since 7169 was 7169, checked in by vboxsync, 17 years ago
Doxygen fixes.
Property svn:keywords set to `Id`
File size: 30.4 KB

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

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

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

Download in other formats: