heapsimple.cpp@ 5799

Last change on this file since 5799 was 5605, checked in by vboxsync, 17 years ago
BIT => RT_BIT, BIT64 => RT_BIT_64. BIT() is defined in Linux 2.6.24
Property svn:keywords set to `Id`
File size: 30.0 KB

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

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

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

Download in other formats: