heapsimple.cpp@ 35398

Last change on this file since 35398 was 35398, checked in by vboxsync, 14 years ago
re-applied r69255, r69257: properly wrap mem* to xf86mem* for older XF86 modules
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 30.2 KB

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

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

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

Download in other formats: