heapsimple.cpp@ 17822

Last change on this file since 17822 was 14318, checked in by vboxsync, 16 years ago
Fix a couple of words doubled in comments. No code changes.
Property svn:keywords set to `Id`
File size: 31.0 KB

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

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

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

Download in other formats: