heapsimple.cpp@ 21337

Last change on this file since 21337 was 21337, checked in by vboxsync, 15 years ago
IPRT,HostDrv,AddDrv: Export public IPRT symbols for the linux kernel (pain).
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 30.9 KB

Line
1	/* $Id: heapsimple.cpp 21337 2009-07-07 14:58:27Z 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	#include <iprt/heap.h>
37	#include "internal/iprt.h"
38
39	#include <iprt/assert.h>
40	#include <iprt/asm.h>
41	#include <iprt/string.h>
42	#include <iprt/err.h>
43	#include <iprt/log.h>
44	#include <iprt/param.h>
45
46	#include "internal/magics.h"
47
48
49	/*******************************************************************************
50	* Structures and Typedefs *
51	*******************************************************************************/
52	/** Pointer to the heap anchor block. */
53	typedef struct RTHEAPSIMPLEINTERNAL *PRTHEAPSIMPLEINTERNAL;
54	/** Pointer to a heap block. */
55	typedef struct RTHEAPSIMPLEBLOCK *PRTHEAPSIMPLEBLOCK;
56	/** Pointer to a free heap block. */
57	typedef struct RTHEAPSIMPLEFREE *PRTHEAPSIMPLEFREE;
58
59	/**
60	* Structure describing a simple heap block.
61	* If this block is allocated, it is followed by the user data.
62	* If this block is free, see RTHEAPSIMPLEFREE.
63	*/
64	typedef struct RTHEAPSIMPLEBLOCK
65	{
66	/** The next block in the global block list. */
67	PRTHEAPSIMPLEBLOCK pNext;
68	/** The previous block in the global block list. */
69	PRTHEAPSIMPLEBLOCK pPrev;
70	/** Pointer to the heap anchor block. */
71	PRTHEAPSIMPLEINTERNAL pHeap;
72	/** Flags + magic. */
73	uintptr_t fFlags;
74	} RTHEAPSIMPLEBLOCK;
75	AssertCompileSizeAlignment(RTHEAPSIMPLEBLOCK, 16);
76
77	/** The block is free if this flag is set. When cleared it's allocated. */
78	#define RTHEAPSIMPLEBLOCK_FLAGS_FREE ((uintptr_t)RT_BIT(0))
79	/** The magic value. */
80	#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC ((uintptr_t)0xabcdef00)
81	/** The mask that needs to be applied to RTHEAPSIMPLEBLOCK::fFlags to obtain the magic value. */
82	#define RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK (~(uintptr_t)RT_BIT(0))
83
84	/**
85	* Checks if the specified block is valid or not.
86	* @returns boolean answer.
87	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
88	*/
89	#define RTHEAPSIMPLEBLOCK_IS_VALID(pBlock) \
90	( ((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK) == RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
91
92	/**
93	* Checks if the specified block is valid and in use.
94	* @returns boolean answer.
95	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
96	*/
97	#define RTHEAPSIMPLEBLOCK_IS_VALID_USED(pBlock) \
98	( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK \| RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
99	== RTHEAPSIMPLEBLOCK_FLAGS_MAGIC )
100
101	/**
102	* Checks if the specified block is valid and free.
103	* @returns boolean answer.
104	* @param pBlock Pointer to a RTHEAPSIMPLEBLOCK structure.
105	*/
106	#define RTHEAPSIMPLEBLOCK_IS_VALID_FREE(pBlock) \
107	( ((pBlock)->fFlags & (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC_MASK \| RTHEAPSIMPLEBLOCK_FLAGS_FREE)) \
108	== (RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE) )
109
110	/**
111	* Checks if the specified block is free or not.
112	* @returns boolean answer.
113	* @param pBlock Pointer to a valid RTHEAPSIMPLEBLOCK structure.
114	*/
115	#define RTHEAPSIMPLEBLOCK_IS_FREE(pBlock) (!!((pBlock)->fFlags & RTHEAPSIMPLEBLOCK_FLAGS_FREE))
116
117	/**
118	* A free heap block.
119	* This is an extended version of RTHEAPSIMPLEBLOCK that takes the unused
120	* user data to store free list pointers and a cached size value.
121	*/
122	typedef struct RTHEAPSIMPLEFREE
123	{
124	/** Core stuff. */
125	RTHEAPSIMPLEBLOCK Core;
126	/** Pointer to the next free block. */
127	PRTHEAPSIMPLEFREE pNext;
128	/** Pointer to the previous free block. */
129	PRTHEAPSIMPLEFREE pPrev;
130	/** The size of the block (excluding the RTHEAPSIMPLEBLOCK part). */
131	size_t cb;
132	/** An alignment filler to make it a multiple of (sizeof(void ) 2). */
133	size_t Alignment;
134	} RTHEAPSIMPLEFREE;
135
136
137	/**
138	* The heap anchor block.
139	* This structure is placed at the head of the memory block specified to RTHeapSimpleInit(),
140	* which means that the first RTHEAPSIMPLEBLOCK appears immediately after this structure.
141	*/
142	typedef struct RTHEAPSIMPLEINTERNAL
143	{
144	/** The typical magic (RTHEAPSIMPLE_MAGIC). */
145	size_t uMagic;
146	/** The heap size. (This structure is not included!) */
147	size_t cbHeap;
148	/** Pointer to the end of the heap. */
149	void *pvEnd;
150	/** The amount of free memory in the heap. */
151	size_t cbFree;
152	/** Free head pointer. */
153	PRTHEAPSIMPLEFREE pFreeHead;
154	/** Free tail pointer. */
155	PRTHEAPSIMPLEFREE pFreeTail;
156	/** Make the size of this structure is a multiple of 32. */
157	size_t auAlignment[2];
158	} RTHEAPSIMPLEINTERNAL;
159	AssertCompileSizeAlignment(RTHEAPSIMPLEINTERNAL, 32);
160
161
162	/** The minimum allocation size. */
163	#define RTHEAPSIMPLE_MIN_BLOCK (sizeof(RTHEAPSIMPLEBLOCK))
164	AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEBLOCK));
165	AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEFREE) - sizeof(RTHEAPSIMPLEBLOCK));
166
167	/** The minimum and default alignment. */
168	#define RTHEAPSIMPLE_ALIGNMENT (sizeof(RTHEAPSIMPLEBLOCK))
169
170
171	/*******************************************************************************
172	* Defined Constants And Macros *
173	*******************************************************************************/
174	#ifdef RT_STRICT
175	# define RTHEAPSIMPLE_STRICT 1
176	#endif
177
178	#define ASSERT_L(a, b) AssertMsg((uintptr_t)(a) < (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
179	#define ASSERT_LE(a, b) AssertMsg((uintptr_t)(a) <= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
180	#define ASSERT_G(a, b) AssertMsg((uintptr_t)(a) > (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
181	#define ASSERT_GE(a, b) AssertMsg((uintptr_t)(a) >= (uintptr_t)(b), ("a=%p b=%p\n", (uintptr_t)(a), (uintptr_t)(b)))
182	#define ASSERT_ALIGN(a) AssertMsg(!((uintptr_t)(a) & (RTHEAPSIMPLE_ALIGNMENT - 1)), ("a=%p\n", (uintptr_t)(a)))
183
184	#define ASSERT_PREV(pHeapInt, pBlock) \
185	do { ASSERT_ALIGN((pBlock)->pPrev); \
186	if ((pBlock)->pPrev) \
187	{ \
188	ASSERT_L((pBlock)->pPrev, (pBlock)); \
189	ASSERT_GE((pBlock)->pPrev, (pHeapInt) + 1); \
190	} \
191	else \
192	Assert((pBlock) == (PRTHEAPSIMPLEBLOCK)((pHeapInt) + 1)); \
193	} while (0)
194
195	#define ASSERT_NEXT(pHeap, pBlock) \
196	do { ASSERT_ALIGN((pBlock)->pNext); \
197	if ((pBlock)->pNext) \
198	{ \
199	ASSERT_L((pBlock)->pNext, (pHeapInt)->pvEnd); \
200	ASSERT_G((pBlock)->pNext, (pBlock)); \
201	} \
202	} while (0)
203
204	#define ASSERT_BLOCK(pHeapInt, pBlock) \
205	do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID(pBlock), ("%#x\n", (pBlock)->fFlags)); \
206	AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
207	ASSERT_GE((pBlock), (pHeapInt) + 1); \
208	ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
209	ASSERT_NEXT(pHeapInt, pBlock); \
210	ASSERT_PREV(pHeapInt, pBlock); \
211	} while (0)
212
213	#define ASSERT_BLOCK_USED(pHeapInt, pBlock) \
214	do { AssertMsg(RTHEAPSIMPLEBLOCK_IS_VALID_USED((pBlock)), ("%#x\n", (pBlock)->fFlags)); \
215	AssertMsg((pBlock)->pHeap == (pHeapInt), ("%p != %p\n", (pBlock)->pHeap, (pHeapInt))); \
216	ASSERT_GE((pBlock), (pHeapInt) + 1); \
217	ASSERT_L((pBlock), (pHeapInt)->pvEnd); \
218	ASSERT_NEXT(pHeapInt, pBlock); \
219	ASSERT_PREV(pHeapInt, pBlock); \
220	} while (0)
221
222	#define ASSERT_FREE_PREV(pHeapInt, pBlock) \
223	do { ASSERT_ALIGN((pBlock)->pPrev); \
224	if ((pBlock)->pPrev) \
225	{ \
226	ASSERT_GE((pBlock)->pPrev, (pHeapInt)->pFreeHead); \
227	ASSERT_L((pBlock)->pPrev, (pBlock)); \
228	ASSERT_LE((pBlock)->pPrev, (pBlock)->Core.pPrev); \
229	} \
230	else \
231	Assert((pBlock) == (pHeapInt)->pFreeHead); \
232	} while (0)
233
234	#define ASSERT_FREE_NEXT(pHeapInt, pBlock) \
235	do { ASSERT_ALIGN((pBlock)->pNext); \
236	if ((pBlock)->pNext) \
237	{ \
238	ASSERT_LE((pBlock)->pNext, (pHeapInt)->pFreeTail); \
239	ASSERT_G((pBlock)->pNext, (pBlock)); \
240	ASSERT_GE((pBlock)->pNext, (pBlock)->Core.pNext); \
241	} \
242	else \
243	Assert((pBlock) == (pHeapInt)->pFreeTail); \
244	} while (0)
245
246	#ifdef RTHEAPSIMPLE_STRICT
247	# define ASSERT_FREE_CB(pHeapInt, pBlock) \
248	do { size_t cbCalc = ((pBlock)->Core.pNext ? (uintptr_t)(pBlock)->Core.pNext : (uintptr_t)(pHeapInt)->pvEnd) \
249	- (uintptr_t)(pBlock) - sizeof(RTHEAPSIMPLEBLOCK); \
250	AssertMsg((pBlock)->cb == cbCalc, ("cb=%#zx cbCalc=%#zx\n", (pBlock)->cb, cbCalc)); \
251	} while (0)
252	#else
253	# define ASSERT_FREE_CB(pHeapInt, pBlock) do {} while (0)
254	#endif
255
256	/** Asserts that a free block is valid. */
257	#define ASSERT_BLOCK_FREE(pHeapInt, pBlock) \
258	do { ASSERT_BLOCK(pHeapInt, &(pBlock)->Core); \
259	Assert(RTHEAPSIMPLEBLOCK_IS_VALID_FREE(&(pBlock)->Core)); \
260	ASSERT_GE((pBlock), (pHeapInt)->pFreeHead); \
261	ASSERT_LE((pBlock), (pHeapInt)->pFreeTail); \
262	ASSERT_FREE_NEXT(pHeapInt, pBlock); \
263	ASSERT_FREE_PREV(pHeapInt, pBlock); \
264	ASSERT_FREE_CB(pHeapInt, pBlock); \
265	} while (0)
266
267	/** Asserts that the heap anchor block is ok. */
268	#define ASSERT_ANCHOR(pHeapInt) \
269	do { AssertPtr(pHeapInt);\
270	Assert((pHeapInt)->uMagic == RTHEAPSIMPLE_MAGIC); \
271	} while (0)
272
273
274	/*******************************************************************************
275	* Internal Functions *
276	*******************************************************************************/
277	#ifdef RTHEAPSIMPLE_STRICT
278	static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt);
279	#endif
280	static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment);
281	static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock);
282
283
284	/**
285	* Initializes the heap.
286	*
287	* @returns IPRT status code on success.
288	* @param pHeap Where to store the heap anchor block on success.
289	* @param pvMemory Pointer to the heap memory.
290	* @param cbMemory The size of the heap memory.
291	*/
292	RTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE pHeap, void *pvMemory, size_t cbMemory)
293	{
294	PRTHEAPSIMPLEINTERNAL pHeapInt;
295	PRTHEAPSIMPLEFREE pFree;
296	unsigned i;
297
298	/*
299	* Validate input. The imposed minimum heap size is just a convenient value.
300	*/
301	AssertReturn(cbMemory >= PAGE_SIZE, VERR_INVALID_PARAMETER);
302	AssertPtrReturn(pvMemory, VERR_INVALID_POINTER);
303	AssertReturn((uintptr_t)pvMemory + (cbMemory - 1) > (uintptr_t)cbMemory, VERR_INVALID_PARAMETER);
304
305	/*
306	* Place the heap anchor block at the start of the heap memory,
307	* enforce 32 byte alignment of it. Also align the heap size correctly.
308	*/
309	pHeapInt = (PRTHEAPSIMPLEINTERNAL)pvMemory;
310	if ((uintptr_t)pvMemory & 31)
311	{
312	const uintptr_t off = 32 - ((uintptr_t)pvMemory & 31);
313	cbMemory -= off;
314	pHeapInt = (PRTHEAPSIMPLEINTERNAL)((uintptr_t)pvMemory + off);
315	}
316	cbMemory &= ~(RTHEAPSIMPLE_ALIGNMENT - 1);
317
318
319	/* Init the heap anchor block. */
320	pHeapInt->uMagic = RTHEAPSIMPLE_MAGIC;
321	pHeapInt->pvEnd = (uint8_t *)pHeapInt + cbMemory;
322	pHeapInt->cbHeap = cbMemory;
323	pHeapInt->cbFree = cbMemory
324	- sizeof(RTHEAPSIMPLEBLOCK)
325	- sizeof(RTHEAPSIMPLEINTERNAL);
326	pHeapInt->pFreeTail = pHeapInt->pFreeHead = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
327	for (i = 0; i < RT_ELEMENTS(pHeapInt->auAlignment); i++)
328	pHeapInt->auAlignment[i] = ~(size_t)0;
329
330	/* Init the single free block. */
331	pFree = pHeapInt->pFreeHead;
332	pFree->Core.pNext = NULL;
333	pFree->Core.pPrev = NULL;
334	pFree->Core.pHeap = pHeapInt;
335	pFree->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE;
336	pFree->pNext = NULL;
337	pFree->pPrev = NULL;
338	pFree->cb = pHeapInt->cbFree;
339
340	*pHeap = pHeapInt;
341
342	#ifdef RTHEAPSIMPLE_STRICT
343	rtHeapSimpleAssertAll(pHeapInt);
344	#endif
345	return VINF_SUCCESS;
346	}
347	RT_EXPORT_SYMBOL(RTHeapSimpleInit);
348
349
350
351	/**
352	* Allocates memory from the specified simple heap.
353	*
354	* @returns Pointer to the allocated memory block on success.
355	* @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
356	*
357	* @param Heap The heap to allocate the memory on.
358	* @param cb The requested heap block size.
359	* @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
360	* Must be a power of 2.
361	*/
362	RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
363	{
364	PRTHEAPSIMPLEINTERNAL pHeapInt = Heap;
365	PRTHEAPSIMPLEBLOCK pBlock;
366
367	/*
368	* Validate and adjust the input.
369	*/
370	AssertPtrReturn(pHeapInt, NULL);
371	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
372	cb = RTHEAPSIMPLE_MIN_BLOCK;
373	else
374	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
375	if (!cbAlignment)
376	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
377	else
378	{
379	Assert(!(cbAlignment & (cbAlignment - 1)));
380	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
381	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
382	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
383	}
384
385	/*
386	* Do the allocation.
387	*/
388	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
389	if (RT_LIKELY(pBlock))
390	{
391	void *pv = pBlock + 1;
392	return pv;
393	}
394	return NULL;
395	}
396	RT_EXPORT_SYMBOL(RTHeapSimpleAlloc);
397
398
399	/**
400	* Allocates zeroed memory from the specified simple heap.
401	*
402	* @returns Pointer to the allocated memory block on success.
403	* @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
404	*
405	* @param Heap The heap to allocate the memory on.
406	* @param cb The requested heap block size.
407	* @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
408	* Must be a power of 2.
409	*/
410	RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
411	{
412	PRTHEAPSIMPLEINTERNAL pHeapInt = Heap;
413	PRTHEAPSIMPLEBLOCK pBlock;
414
415	/*
416	* Validate and adjust the input.
417	*/
418	AssertPtrReturn(pHeapInt, NULL);
419	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
420	cb = RTHEAPSIMPLE_MIN_BLOCK;
421	else
422	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
423	if (!cbAlignment)
424	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
425	else
426	{
427	Assert(!(cbAlignment & (cbAlignment - 1)));
428	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
429	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
430	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
431	}
432
433	/*
434	* Do the allocation.
435	*/
436	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
437	if (RT_LIKELY(pBlock))
438	{
439	void *pv = pBlock + 1;
440	memset(pv, 0, cb);
441	return pv;
442	}
443	return NULL;
444	}
445	RT_EXPORT_SYMBOL(RTHeapSimpleAllocZ);
446
447
448	/**
449	* Allocates a block of memory from the specified heap.
450	*
451	* No parameter validation or adjustment is performed.
452	*
453	* @returns Pointer to the allocated block.
454	* @returns NULL on failure.
455	* @param pHeapInt The heap.
456	* @param cb Size of the memory block to allocate.
457	* @param uAlignment The alignment specifications for the allocated block.
458	*/
459	static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment)
460	{
461	PRTHEAPSIMPLEBLOCK pRet = NULL;
462	PRTHEAPSIMPLEFREE pFree;
463
464	#ifdef RTHEAPSIMPLE_STRICT
465	rtHeapSimpleAssertAll(pHeapInt);
466	#endif
467
468	/*
469	* Search for a fitting block from the lower end of the heap.
470	*/
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 neighbors.
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	RT_EXPORT_SYMBOL(RTHeapSimpleFree);
667
668
669	/**
670	* Free a memory block.
671	*
672	* @param pHeapInt The heap.
673	* @param pBlock The memory block to free.
674	*/
675	static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock)
676	{
677	PRTHEAPSIMPLEFREE pFree = (PRTHEAPSIMPLEFREE)pBlock;
678	PRTHEAPSIMPLEFREE pLeft;
679	PRTHEAPSIMPLEFREE pRight;
680
681	#ifdef RTHEAPSIMPLE_STRICT
682	rtHeapSimpleAssertAll(pHeapInt);
683	#endif
684
685	/*
686	* Look for the closest free list blocks by walking the blocks right
687	* of us (both lists are sorted by address).
688	*/
689	pLeft = NULL;
690	pRight = NULL;
691	if (pHeapInt->pFreeTail)
692	{
693	pRight = (PRTHEAPSIMPLEFREE)pFree->Core.pNext;
694	while (pRight && !RTHEAPSIMPLEBLOCK_IS_FREE(&pRight->Core))
695	{
696	ASSERT_BLOCK(pHeapInt, &pRight->Core);
697	pRight = (PRTHEAPSIMPLEFREE)pRight->Core.pNext;
698	}
699	if (!pRight)
700	pLeft = pHeapInt->pFreeTail;
701	else
702	{
703	ASSERT_BLOCK_FREE(pHeapInt, pRight);
704	pLeft = pRight->pPrev;
705	}
706	if (pLeft)
707	ASSERT_BLOCK_FREE(pHeapInt, pLeft);
708	}
709	AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock));
710	ASSERT_L(pLeft, pFree);
711	Assert(!pRight \|\| (uintptr_t)pRight > (uintptr_t)pFree);
712	Assert(!pLeft \|\| pLeft->pNext == pRight);
713
714	/*
715	* Insert at the head of the free block list?
716	*/
717	if (!pLeft)
718	{
719	Assert(pRight == pHeapInt->pFreeHead);
720	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
721	pFree->pPrev = NULL;
722	pFree->pNext = pRight;
723	if (pRight)
724	pRight->pPrev = pFree;
725	else
726	pHeapInt->pFreeTail = pFree;
727	pHeapInt->pFreeHead = pFree;
728	}
729	else
730	{
731	/*
732	* Can we merge with left hand free block?
733	*/
734	if (pLeft->Core.pNext == &pFree->Core)
735	{
736	pLeft->Core.pNext = pFree->Core.pNext;
737	if (pFree->Core.pNext)
738	pFree->Core.pNext->pPrev = &pLeft->Core;
739	pHeapInt->cbFree -= pLeft->cb;
740	pFree = pLeft;
741	}
742	/*
743	* No, just link it into the free list then.
744	*/
745	else
746	{
747	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
748	pFree->pNext = pRight;
749	pFree->pPrev = pLeft;
750	pLeft->pNext = pFree;
751	if (pRight)
752	pRight->pPrev = pFree;
753	else
754	pHeapInt->pFreeTail = pFree;
755	}
756	}
757
758	/*
759	* Can we merge with right hand free block?
760	*/
761	if ( pRight
762	&& pRight->Core.pPrev == &pFree->Core)
763	{
764	/* core */
765	pFree->Core.pNext = pRight->Core.pNext;
766	if (pRight->Core.pNext)
767	pRight->Core.pNext->pPrev = &pFree->Core;
768
769	/* free */
770	pFree->pNext = pRight->pNext;
771	if (pRight->pNext)
772	pRight->pNext->pPrev = pFree;
773	else
774	pHeapInt->pFreeTail = pFree;
775	pHeapInt->cbFree -= pRight->cb;
776	}
777
778	/*
779	* Calculate the size and update free stats.
780	*/
781	pFree->cb = (pFree->Core.pNext ? (uintptr_t)pFree->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
782	- (uintptr_t)pFree - sizeof(RTHEAPSIMPLEBLOCK);
783	pHeapInt->cbFree += pFree->cb;
784	ASSERT_BLOCK_FREE(pHeapInt, pFree);
785
786	#ifdef RTHEAPSIMPLE_STRICT
787	rtHeapSimpleAssertAll(pHeapInt);
788	#endif
789	}
790
791
792	#ifdef RTHEAPSIMPLE_STRICT
793	/**
794	* Internal consistency check (relying on assertions).
795	* @param pHeapInt
796	*/
797	static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt)
798	{
799	PRTHEAPSIMPLEFREE pPrev = NULL;
800	PRTHEAPSIMPLEFREE pPrevFree = NULL;
801	PRTHEAPSIMPLEFREE pBlock;
802	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
803	pBlock;
804	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
805	{
806	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
807	{
808	ASSERT_BLOCK_FREE(pHeapInt, pBlock);
809	Assert(pBlock->pPrev == pPrevFree);
810	Assert(pPrevFree \|\| pHeapInt->pFreeHead == pBlock);
811	pPrevFree = pBlock;
812	}
813	else
814	ASSERT_BLOCK_USED(pHeapInt, &pBlock->Core);
815	Assert(!pPrev \|\| pPrev == (PRTHEAPSIMPLEFREE)pBlock->Core.pPrev);
816	pPrev = pBlock;
817	}
818	Assert(pHeapInt->pFreeTail == pPrevFree);
819	}
820	#endif
821
822
823	/**
824	* Gets the size of the specified heap block.
825	*
826	* @returns The actual size of the heap block.
827	* @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An invalid \a pv
828	* can also cause traps or trigger assertions.
829	* @param Heap The heap. This is optional and will only be used for strict assertions.
830	* @param pv The heap block returned by RTHeapSimple
831	*/
832	RTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE Heap, void *pv)
833	{
834	PRTHEAPSIMPLEINTERNAL pHeapInt;
835	PRTHEAPSIMPLEBLOCK pBlock;
836	size_t cbBlock;
837
838	/*
839	* Validate input.
840	*/
841	if (!pv)
842	return 0;
843	AssertPtrReturn(pv, 0);
844	AssertReturn(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv, 0);
845
846	/*
847	* Get the block and heap. If in strict mode, validate these.
848	*/
849	pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
850	pHeapInt = pBlock->pHeap;
851	ASSERT_BLOCK_USED(pHeapInt, pBlock);
852	ASSERT_ANCHOR(pHeapInt);
853	Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)Heap \|\| !Heap);
854
855	/*
856	* Calculate the block size.
857	*/
858	cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
859	- (uintptr_t)pBlock- sizeof(RTHEAPSIMPLEBLOCK);
860	return cbBlock;
861	}
862	RT_EXPORT_SYMBOL(RTHeapSimpleSize);
863
864
865	/**
866	* Gets the size of the heap.
867	*
868	* This size includes all the internal heap structures. So, even if the heap is
869	* empty the RTHeapSimpleGetFreeSize() will never reach the heap size returned
870	* by this function.
871	*
872	* @returns The heap size.
873	* @returns 0 if heap was safely detected as being bad.
874	* @param Heap The heap.
875	*/
876	RTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE Heap)
877	{
878	PRTHEAPSIMPLEINTERNAL pHeapInt;
879
880	if (Heap == NIL_RTHEAPSIMPLE)
881	return 0;
882
883	pHeapInt = Heap;
884	AssertPtrReturn(pHeapInt, 0);
885	ASSERT_ANCHOR(pHeapInt);
886	return pHeapInt->cbHeap;
887	}
888	RT_EXPORT_SYMBOL(RTHeapSimpleGetHeapSize);
889
890
891	/**
892	* Returns the sum of all free heap blocks.
893	*
894	* This is the amount of memory you can theoretically allocate
895	* if you do allocations exactly matching the free blocks.
896	*
897	* @returns The size of the free blocks.
898	* @returns 0 if heap was safely detected as being bad.
899	* @param Heap The heap.
900	*/
901	RTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE Heap)
902	{
903	PRTHEAPSIMPLEINTERNAL pHeapInt;
904
905	if (Heap == NIL_RTHEAPSIMPLE)
906	return 0;
907
908	pHeapInt = Heap;
909	AssertPtrReturn(pHeapInt, 0);
910	ASSERT_ANCHOR(pHeapInt);
911	return pHeapInt->cbFree;
912	}
913	RT_EXPORT_SYMBOL(RTHeapSimpleGetFreeSize);
914
915
916	/**
917	* Dumps the hypervisor heap.
918	*
919	* @param Heap The heap handle.
920	* @param pfnPrintf Printf like function that groks IPRT formatting.
921	*/
922	RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE Heap, PFNRTHEAPSIMPLEPRINTF pfnPrintf)
923	{
924	PRTHEAPSIMPLEINTERNAL pHeapInt = (PRTHEAPSIMPLEINTERNAL)Heap;
925	PRTHEAPSIMPLEFREE pBlock;
926
927	pfnPrintf("** Dumping Heap %p - cbHeap=%zx cbFree=%zx **\n",
928	Heap, pHeapInt->cbHeap, pHeapInt->cbFree);
929
930	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
931	pBlock;
932	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
933	{
934	size_t cb = (pBlock->pNext ? (uintptr_t)pBlock->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
935	- (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
936	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
937	pfnPrintf("%p %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
938	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb,
939	pBlock->cb, pBlock->pNext, pBlock->pPrev);
940	else
941	pfnPrintf("%p %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",
942	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb);
943	}
944	pfnPrintf("** Done dumping Heap %p **\n", Heap);
945	}
946	RT_EXPORT_SYMBOL(RTHeapSimpleDump);
947

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

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

Download in other formats: