heapsimple.cpp@ 24344

Last change on this file since 24344 was 22281, checked in by vboxsync, 15 years ago
IPRT: parentheses
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 33.5 KB

Line
1	/* $Id: heapsimple.cpp 22281 2009-08-17 08:04:06Z 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 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.
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	* Relocater the heap internal structures after copying it to a new location.
352	*
353	* This can be used when loading a saved heap.
354	*
355	* @returns IPRT status code.
356	* @param hHeap Heap handle that has already been adjusted by to the new
357	* location. That is to say, when calling
358	* RTHeapSimpleInit, the caller must note the offset of the
359	* returned heap handle into the heap memory. This offset
360	* must be used when calcuating the handle value for the
361	* new location. The offset may in some cases not be zero!
362	* @param offDelta The delta between the new and old location, i.e. what
363	* should be added to the internal pointers.
364	*/
365	RTDECL(int) RTHeapSimpleRelocate(RTHEAPSIMPLE hHeap, uintptr_t offDelta)
366	{
367	PRTHEAPSIMPLEINTERNAL pHeapInt = hHeap;
368	PRTHEAPSIMPLEFREE pCur;
369
370	/*
371	* Validate input.
372	*/
373	AssertPtrReturn(pHeapInt, VERR_INVALID_HANDLE);
374	AssertReturn(pHeapInt->uMagic == RTHEAPSIMPLE_MAGIC, VERR_INVALID_HANDLE);
375	AssertMsgReturn((uintptr_t)pHeapInt - (uintptr_t)pHeapInt->pvEnd + pHeapInt->cbHeap == offDelta,
376	("offDelta=%p, expected=%p\n", offDelta, (uintptr_t)pHeapInt->pvEnd - pHeapInt->cbHeap - (uintptr_t)pHeapInt),
377	VERR_INVALID_PARAMETER);
378
379	/*
380	* Relocate the heap anchor block.
381	*/
382	#define RELOCATE_IT(var, type, offDelta) do { if (RT_UNLIKELY((var) != NULL)) { (var) = (type)((uintptr_t)(var) + offDelta); } } while (0)
383	RELOCATE_IT(pHeapInt->pvEnd, void *, offDelta);
384	RELOCATE_IT(pHeapInt->pFreeHead, PRTHEAPSIMPLEFREE, offDelta);
385	RELOCATE_IT(pHeapInt->pFreeTail, PRTHEAPSIMPLEFREE, offDelta);
386
387	/*
388	* Walk the heap blocks.
389	*/
390	for (pCur = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
391	pCur && (uintptr_t)pCur < (uintptr_t)pHeapInt->pvEnd;
392	pCur = (PRTHEAPSIMPLEFREE)pCur->Core.pNext)
393	{
394	RELOCATE_IT(pCur->Core.pNext, PRTHEAPSIMPLEBLOCK, offDelta);
395	RELOCATE_IT(pCur->Core.pPrev, PRTHEAPSIMPLEBLOCK, offDelta);
396	RELOCATE_IT(pCur->Core.pHeap, PRTHEAPSIMPLEINTERNAL, offDelta);
397	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pCur->Core))
398	{
399	RELOCATE_IT(pCur->pNext, PRTHEAPSIMPLEFREE, offDelta);
400	RELOCATE_IT(pCur->pPrev, PRTHEAPSIMPLEFREE, offDelta);
401	}
402	}
403	#undef RELOCATE_IT
404
405	#ifdef RTHEAPSIMPLE_STRICT
406	/*
407	* Give it a once over before we return.
408	*/
409	rtHeapSimpleAssertAll(pHeapInt);
410	#endif
411	return VINF_SUCCESS;
412	}
413	RT_EXPORT_SYMBOL(RTHeapSimpleRelocate);
414
415
416
417	/**
418	* Allocates memory from the specified simple heap.
419	*
420	* @returns Pointer to the allocated memory block on success.
421	* @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
422	*
423	* @param Heap The heap to allocate the memory on.
424	* @param cb The requested heap block size.
425	* @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
426	* Must be a power of 2.
427	*/
428	RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
429	{
430	PRTHEAPSIMPLEINTERNAL pHeapInt = Heap;
431	PRTHEAPSIMPLEBLOCK pBlock;
432
433	/*
434	* Validate and adjust the input.
435	*/
436	AssertPtrReturn(pHeapInt, NULL);
437	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
438	cb = RTHEAPSIMPLE_MIN_BLOCK;
439	else
440	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
441	if (!cbAlignment)
442	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
443	else
444	{
445	Assert(!(cbAlignment & (cbAlignment - 1)));
446	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
447	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
448	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
449	}
450
451	/*
452	* Do the allocation.
453	*/
454	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
455	if (RT_LIKELY(pBlock))
456	{
457	void *pv = pBlock + 1;
458	return pv;
459	}
460	return NULL;
461	}
462	RT_EXPORT_SYMBOL(RTHeapSimpleAlloc);
463
464
465	/**
466	* Allocates zeroed memory from the specified simple heap.
467	*
468	* @returns Pointer to the allocated memory block on success.
469	* @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)
470	*
471	* @param Heap The heap to allocate the memory on.
472	* @param cb The requested heap block size.
473	* @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.
474	* Must be a power of 2.
475	*/
476	RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment)
477	{
478	PRTHEAPSIMPLEINTERNAL pHeapInt = Heap;
479	PRTHEAPSIMPLEBLOCK pBlock;
480
481	/*
482	* Validate and adjust the input.
483	*/
484	AssertPtrReturn(pHeapInt, NULL);
485	if (cb < RTHEAPSIMPLE_MIN_BLOCK)
486	cb = RTHEAPSIMPLE_MIN_BLOCK;
487	else
488	cb = RT_ALIGN_Z(cb, RTHEAPSIMPLE_ALIGNMENT);
489	if (!cbAlignment)
490	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
491	else
492	{
493	Assert(!(cbAlignment & (cbAlignment - 1)));
494	Assert((cbAlignment & ~(cbAlignment - 1)) == cbAlignment);
495	if (cbAlignment < RTHEAPSIMPLE_ALIGNMENT)
496	cbAlignment = RTHEAPSIMPLE_ALIGNMENT;
497	}
498
499	/*
500	* Do the allocation.
501	*/
502	pBlock = rtHeapSimpleAllocBlock(pHeapInt, cb, cbAlignment);
503	if (RT_LIKELY(pBlock))
504	{
505	void *pv = pBlock + 1;
506	memset(pv, 0, cb);
507	return pv;
508	}
509	return NULL;
510	}
511	RT_EXPORT_SYMBOL(RTHeapSimpleAllocZ);
512
513
514	/**
515	* Allocates a block of memory from the specified heap.
516	*
517	* No parameter validation or adjustment is performed.
518	*
519	* @returns Pointer to the allocated block.
520	* @returns NULL on failure.
521	* @param pHeapInt The heap.
522	* @param cb Size of the memory block to allocate.
523	* @param uAlignment The alignment specifications for the allocated block.
524	*/
525	static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment)
526	{
527	PRTHEAPSIMPLEBLOCK pRet = NULL;
528	PRTHEAPSIMPLEFREE pFree;
529
530	#ifdef RTHEAPSIMPLE_STRICT
531	rtHeapSimpleAssertAll(pHeapInt);
532	#endif
533
534	/*
535	* Search for a fitting block from the lower end of the heap.
536	*/
537	for (pFree = pHeapInt->pFreeHead;
538	pFree;
539	pFree = pFree->pNext)
540	{
541	uintptr_t offAlign;
542	ASSERT_BLOCK_FREE(pHeapInt, pFree);
543
544	/*
545	* Match for size and alignment.
546	*/
547	if (pFree->cb < cb)
548	continue;
549	offAlign = (uintptr_t)(&pFree->Core + 1) & (uAlignment - 1);
550	if (offAlign)
551	{
552	RTHEAPSIMPLEFREE Free;
553	PRTHEAPSIMPLEBLOCK pPrev;
554
555	offAlign = uAlignment - offAlign;
556	if (pFree->cb - offAlign < cb)
557	continue;
558
559	/*
560	* Make a stack copy of the free block header and adjust the pointer.
561	*/
562	Free = *pFree;
563	pFree = (PRTHEAPSIMPLEFREE)((uintptr_t)pFree + offAlign);
564
565	/*
566	* Donate offAlign bytes to the node in front of us.
567	* If we're the head node, we'll have to create a fake node. We'll
568	* mark it USED for simplicity.
569	*
570	* (Should this policy of donating memory to the guy in front of us
571	* cause big 'leaks', we could create a new free node if there is room
572	* for that.)
573	*/
574	pPrev = Free.Core.pPrev;
575	if (pPrev)
576	{
577	AssertMsg(!RTHEAPSIMPLEBLOCK_IS_FREE(pPrev), ("Impossible!\n"));
578	pPrev->pNext = &pFree->Core;
579	}
580	else
581	{
582	pPrev = (PRTHEAPSIMPLEBLOCK)(pHeapInt + 1);
583	Assert(pPrev == &pFree->Core);
584	pPrev->pPrev = NULL;
585	pPrev->pNext = &pFree->Core;
586	pPrev->pHeap = pHeapInt;
587	pPrev->fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC;
588	}
589	pHeapInt->cbFree -= offAlign;
590
591	/*
592	* Recreate pFree in the new position and adjust the neighbors.
593	*/
594	*pFree = Free;
595
596	/* the core */
597	if (pFree->Core.pNext)
598	pFree->Core.pNext->pPrev = &pFree->Core;
599	pFree->Core.pPrev = pPrev;
600
601	/* the free part */
602	pFree->cb -= offAlign;
603	if (pFree->pNext)
604	pFree->pNext->pPrev = pFree;
605	else
606	pHeapInt->pFreeTail = pFree;
607	if (pFree->pPrev)
608	pFree->pPrev->pNext = pFree;
609	else
610	pHeapInt->pFreeHead = pFree;
611	ASSERT_BLOCK_FREE(pHeapInt, pFree);
612	ASSERT_BLOCK_USED(pHeapInt, pPrev);
613	}
614
615	/*
616	* Split off a new FREE block?
617	*/
618	if (pFree->cb >= cb + RT_ALIGN_Z(sizeof(RTHEAPSIMPLEFREE), RTHEAPSIMPLE_ALIGNMENT))
619	{
620	/*
621	* Move the FREE block up to make room for the new USED block.
622	*/
623	PRTHEAPSIMPLEFREE pNew = (PRTHEAPSIMPLEFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPSIMPLEBLOCK));
624
625	pNew->Core.pNext = pFree->Core.pNext;
626	if (pFree->Core.pNext)
627	pFree->Core.pNext->pPrev = &pNew->Core;
628	pNew->Core.pPrev = &pFree->Core;
629	pNew->Core.pHeap = pHeapInt;
630	pNew->Core.fFlags = RTHEAPSIMPLEBLOCK_FLAGS_MAGIC \| RTHEAPSIMPLEBLOCK_FLAGS_FREE;
631
632	pNew->pNext = pFree->pNext;
633	if (pNew->pNext)
634	pNew->pNext->pPrev = pNew;
635	else
636	pHeapInt->pFreeTail = pNew;
637	pNew->pPrev = pFree->pPrev;
638	if (pNew->pPrev)
639	pNew->pPrev->pNext = pNew;
640	else
641	pHeapInt->pFreeHead = pNew;
642	pNew->cb = (pNew->Core.pNext ? (uintptr_t)pNew->Core.pNext : (uintptr_t)pHeapInt->pvEnd) \
643	- (uintptr_t)pNew - sizeof(RTHEAPSIMPLEBLOCK);
644	ASSERT_BLOCK_FREE(pHeapInt, pNew);
645
646	/*
647	* Update the old FREE node making it a USED node.
648	*/
649	pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
650	pFree->Core.pNext = &pNew->Core;
651	pHeapInt->cbFree -= pFree->cb;
652	pHeapInt->cbFree += pNew->cb;
653	pRet = &pFree->Core;
654	ASSERT_BLOCK_USED(pHeapInt, pRet);
655	}
656	else
657	{
658	/*
659	* Link it out of the free list.
660	*/
661	if (pFree->pNext)
662	pFree->pNext->pPrev = pFree->pPrev;
663	else
664	pHeapInt->pFreeTail = pFree->pPrev;
665	if (pFree->pPrev)
666	pFree->pPrev->pNext = pFree->pNext;
667	else
668	pHeapInt->pFreeHead = pFree->pNext;
669
670	/*
671	* Convert it to a used block.
672	*/
673	pHeapInt->cbFree -= pFree->cb;
674	pFree->Core.fFlags &= ~RTHEAPSIMPLEBLOCK_FLAGS_FREE;
675	pRet = &pFree->Core;
676	ASSERT_BLOCK_USED(pHeapInt, pRet);
677	}
678	break;
679	}
680
681	#ifdef RTHEAPSIMPLE_STRICT
682	rtHeapSimpleAssertAll(pHeapInt);
683	#endif
684	return pRet;
685	}
686
687
688
689
690	/**
691	* Frees memory allocated from a simple heap.
692	*
693	* @param Heap The heap. This is optional and will only be used for strict assertions.
694	* @param pv The heap block returned by RTHeapSimple
695	*/
696	RTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE Heap, void *pv)
697	{
698	PRTHEAPSIMPLEINTERNAL pHeapInt;
699	PRTHEAPSIMPLEBLOCK pBlock;
700
701	/*
702	* Validate input.
703	*/
704	if (!pv)
705	return;
706	AssertPtr(pv);
707	Assert(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv);
708
709	/*
710	* Get the block and heap. If in strict mode, validate these.
711	*/
712	pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
713	pHeapInt = pBlock->pHeap;
714	ASSERT_BLOCK_USED(pHeapInt, pBlock);
715	ASSERT_ANCHOR(pHeapInt);
716	Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)Heap \|\| !Heap);
717
718	#ifdef RTHEAPSIMPLE_FREE_POISON
719	/*
720	* Poison the block.
721	*/
722	const size_t cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
723	- (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
724	memset(pBlock + 1, RTHEAPSIMPLE_FREE_POISON, cbBlock);
725	#endif
726
727	/*
728	* Call worker which does the actual job.
729	*/
730	rtHeapSimpleFreeBlock(pHeapInt, pBlock);
731	}
732	RT_EXPORT_SYMBOL(RTHeapSimpleFree);
733
734
735	/**
736	* Free a memory block.
737	*
738	* @param pHeapInt The heap.
739	* @param pBlock The memory block to free.
740	*/
741	static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock)
742	{
743	PRTHEAPSIMPLEFREE pFree = (PRTHEAPSIMPLEFREE)pBlock;
744	PRTHEAPSIMPLEFREE pLeft;
745	PRTHEAPSIMPLEFREE pRight;
746
747	#ifdef RTHEAPSIMPLE_STRICT
748	rtHeapSimpleAssertAll(pHeapInt);
749	#endif
750
751	/*
752	* Look for the closest free list blocks by walking the blocks right
753	* of us (both lists are sorted by address).
754	*/
755	pLeft = NULL;
756	pRight = NULL;
757	if (pHeapInt->pFreeTail)
758	{
759	pRight = (PRTHEAPSIMPLEFREE)pFree->Core.pNext;
760	while (pRight && !RTHEAPSIMPLEBLOCK_IS_FREE(&pRight->Core))
761	{
762	ASSERT_BLOCK(pHeapInt, &pRight->Core);
763	pRight = (PRTHEAPSIMPLEFREE)pRight->Core.pNext;
764	}
765	if (!pRight)
766	pLeft = pHeapInt->pFreeTail;
767	else
768	{
769	ASSERT_BLOCK_FREE(pHeapInt, pRight);
770	pLeft = pRight->pPrev;
771	}
772	if (pLeft)
773	ASSERT_BLOCK_FREE(pHeapInt, pLeft);
774	}
775	AssertMsgReturnVoid(pLeft != pFree, ("Freed twice! pv=%p (pBlock=%p)\n", pBlock + 1, pBlock));
776	ASSERT_L(pLeft, pFree);
777	Assert(!pRight \|\| (uintptr_t)pRight > (uintptr_t)pFree);
778	Assert(!pLeft \|\| pLeft->pNext == pRight);
779
780	/*
781	* Insert at the head of the free block list?
782	*/
783	if (!pLeft)
784	{
785	Assert(pRight == pHeapInt->pFreeHead);
786	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
787	pFree->pPrev = NULL;
788	pFree->pNext = pRight;
789	if (pRight)
790	pRight->pPrev = pFree;
791	else
792	pHeapInt->pFreeTail = pFree;
793	pHeapInt->pFreeHead = pFree;
794	}
795	else
796	{
797	/*
798	* Can we merge with left hand free block?
799	*/
800	if (pLeft->Core.pNext == &pFree->Core)
801	{
802	pLeft->Core.pNext = pFree->Core.pNext;
803	if (pFree->Core.pNext)
804	pFree->Core.pNext->pPrev = &pLeft->Core;
805	pHeapInt->cbFree -= pLeft->cb;
806	pFree = pLeft;
807	}
808	/*
809	* No, just link it into the free list then.
810	*/
811	else
812	{
813	pFree->Core.fFlags \|= RTHEAPSIMPLEBLOCK_FLAGS_FREE;
814	pFree->pNext = pRight;
815	pFree->pPrev = pLeft;
816	pLeft->pNext = pFree;
817	if (pRight)
818	pRight->pPrev = pFree;
819	else
820	pHeapInt->pFreeTail = pFree;
821	}
822	}
823
824	/*
825	* Can we merge with right hand free block?
826	*/
827	if ( pRight
828	&& pRight->Core.pPrev == &pFree->Core)
829	{
830	/* core */
831	pFree->Core.pNext = pRight->Core.pNext;
832	if (pRight->Core.pNext)
833	pRight->Core.pNext->pPrev = &pFree->Core;
834
835	/* free */
836	pFree->pNext = pRight->pNext;
837	if (pRight->pNext)
838	pRight->pNext->pPrev = pFree;
839	else
840	pHeapInt->pFreeTail = pFree;
841	pHeapInt->cbFree -= pRight->cb;
842	}
843
844	/*
845	* Calculate the size and update free stats.
846	*/
847	pFree->cb = (pFree->Core.pNext ? (uintptr_t)pFree->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
848	- (uintptr_t)pFree - sizeof(RTHEAPSIMPLEBLOCK);
849	pHeapInt->cbFree += pFree->cb;
850	ASSERT_BLOCK_FREE(pHeapInt, pFree);
851
852	#ifdef RTHEAPSIMPLE_STRICT
853	rtHeapSimpleAssertAll(pHeapInt);
854	#endif
855	}
856
857
858	#ifdef RTHEAPSIMPLE_STRICT
859	/**
860	* Internal consistency check (relying on assertions).
861	* @param pHeapInt
862	*/
863	static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt)
864	{
865	PRTHEAPSIMPLEFREE pPrev = NULL;
866	PRTHEAPSIMPLEFREE pPrevFree = NULL;
867	PRTHEAPSIMPLEFREE pBlock;
868	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
869	pBlock;
870	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
871	{
872	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
873	{
874	ASSERT_BLOCK_FREE(pHeapInt, pBlock);
875	Assert(pBlock->pPrev == pPrevFree);
876	Assert(pPrevFree \|\| pHeapInt->pFreeHead == pBlock);
877	pPrevFree = pBlock;
878	}
879	else
880	ASSERT_BLOCK_USED(pHeapInt, &pBlock->Core);
881	Assert(!pPrev \|\| pPrev == (PRTHEAPSIMPLEFREE)pBlock->Core.pPrev);
882	pPrev = pBlock;
883	}
884	Assert(pHeapInt->pFreeTail == pPrevFree);
885	}
886	#endif
887
888
889	/**
890	* Gets the size of the specified heap block.
891	*
892	* @returns The actual size of the heap block.
893	* @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An invalid \a pv
894	* can also cause traps or trigger assertions.
895	* @param Heap The heap. This is optional and will only be used for strict assertions.
896	* @param pv The heap block returned by RTHeapSimple
897	*/
898	RTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE Heap, void *pv)
899	{
900	PRTHEAPSIMPLEINTERNAL pHeapInt;
901	PRTHEAPSIMPLEBLOCK pBlock;
902	size_t cbBlock;
903
904	/*
905	* Validate input.
906	*/
907	if (!pv)
908	return 0;
909	AssertPtrReturn(pv, 0);
910	AssertReturn(RT_ALIGN_P(pv, RTHEAPSIMPLE_ALIGNMENT) == pv, 0);
911
912	/*
913	* Get the block and heap. If in strict mode, validate these.
914	*/
915	pBlock = (PRTHEAPSIMPLEBLOCK)pv - 1;
916	pHeapInt = pBlock->pHeap;
917	ASSERT_BLOCK_USED(pHeapInt, pBlock);
918	ASSERT_ANCHOR(pHeapInt);
919	Assert(pHeapInt == (PRTHEAPSIMPLEINTERNAL)Heap \|\| !Heap);
920
921	/*
922	* Calculate the block size.
923	*/
924	cbBlock = (pBlock->pNext ? (uintptr_t)pBlock->pNext : (uintptr_t)pHeapInt->pvEnd)
925	- (uintptr_t)pBlock- sizeof(RTHEAPSIMPLEBLOCK);
926	return cbBlock;
927	}
928	RT_EXPORT_SYMBOL(RTHeapSimpleSize);
929
930
931	/**
932	* Gets the size of the heap.
933	*
934	* This size includes all the internal heap structures. So, even if the heap is
935	* empty the RTHeapSimpleGetFreeSize() will never reach the heap size returned
936	* by this function.
937	*
938	* @returns The heap size.
939	* @returns 0 if heap was safely detected as being bad.
940	* @param Heap The heap.
941	*/
942	RTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE Heap)
943	{
944	PRTHEAPSIMPLEINTERNAL pHeapInt;
945
946	if (Heap == NIL_RTHEAPSIMPLE)
947	return 0;
948
949	pHeapInt = Heap;
950	AssertPtrReturn(pHeapInt, 0);
951	ASSERT_ANCHOR(pHeapInt);
952	return pHeapInt->cbHeap;
953	}
954	RT_EXPORT_SYMBOL(RTHeapSimpleGetHeapSize);
955
956
957	/**
958	* Returns the sum of all free heap blocks.
959	*
960	* This is the amount of memory you can theoretically allocate
961	* if you do allocations exactly matching the free blocks.
962	*
963	* @returns The size of the free blocks.
964	* @returns 0 if heap was safely detected as being bad.
965	* @param Heap The heap.
966	*/
967	RTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE Heap)
968	{
969	PRTHEAPSIMPLEINTERNAL pHeapInt;
970
971	if (Heap == NIL_RTHEAPSIMPLE)
972	return 0;
973
974	pHeapInt = Heap;
975	AssertPtrReturn(pHeapInt, 0);
976	ASSERT_ANCHOR(pHeapInt);
977	return pHeapInt->cbFree;
978	}
979	RT_EXPORT_SYMBOL(RTHeapSimpleGetFreeSize);
980
981
982	/**
983	* Dumps the hypervisor heap.
984	*
985	* @param Heap The heap handle.
986	* @param pfnPrintf Printf like function that groks IPRT formatting.
987	*/
988	RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE Heap, PFNRTHEAPSIMPLEPRINTF pfnPrintf)
989	{
990	PRTHEAPSIMPLEINTERNAL pHeapInt = (PRTHEAPSIMPLEINTERNAL)Heap;
991	PRTHEAPSIMPLEFREE pBlock;
992
993	pfnPrintf("** Dumping Heap %p - cbHeap=%zx cbFree=%zx **\n",
994	Heap, pHeapInt->cbHeap, pHeapInt->cbFree);
995
996	for (pBlock = (PRTHEAPSIMPLEFREE)(pHeapInt + 1);
997	pBlock;
998	pBlock = (PRTHEAPSIMPLEFREE)pBlock->Core.pNext)
999	{
1000	size_t cb = (pBlock->pNext ? (uintptr_t)pBlock->Core.pNext : (uintptr_t)pHeapInt->pvEnd)
1001	- (uintptr_t)pBlock - sizeof(RTHEAPSIMPLEBLOCK);
1002	if (RTHEAPSIMPLEBLOCK_IS_FREE(&pBlock->Core))
1003	pfnPrintf("%p %06x FREE pNext=%p pPrev=%p fFlags=%#x cb=%#06x : cb=%#06x pNext=%p pPrev=%p\n",
1004	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb,
1005	pBlock->cb, pBlock->pNext, pBlock->pPrev);
1006	else
1007	pfnPrintf("%p %06x USED pNext=%p pPrev=%p fFlags=%#x cb=%#06x\n",
1008	pBlock, (uintptr_t)pBlock - (uintptr_t)(pHeapInt + 1), pBlock->Core.pNext, pBlock->Core.pPrev, pBlock->Core.fFlags, cb);
1009	}
1010	pfnPrintf("** Done dumping Heap %p **\n", Heap);
1011	}
1012	RT_EXPORT_SYMBOL(RTHeapSimpleDump);
1013

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

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

Download in other formats: