heapsimple.cpp@ 3392

Last change on this file since 3392 was 2981, checked in by vboxsync, 17 years ago
InnoTek -> innotek: all the headers and comments.
Property svn:keywords set to `Id`
File size: 30.2 KB

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

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

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

Download in other formats: