heapoffset.cpp@ 28298

Last change on this file since 28298 was 26525, checked in by vboxsync, 15 years ago
Runtime: win.amd64 warnings.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 33.0 KB

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

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

source: vbox/trunk/src/VBox/Runtime/common/alloc/heapoffset.cpp@ 28298

Download in other formats: