heapsimple.cpp@ 490

Last change on this file since 490 was 331, checked in by vboxsync, 18 years ago
Bool and AMD64 hacking.
Property svn:keywords set to `Id`
File size: 30.1 KB

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

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

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

Download in other formats: