heapoffset.cpp@ 44300

Last change on this file since 44300 was 40938, checked in by vboxsync, 13 years ago
runtime: backed out r77481,r77482,r77483,r77484,r77485
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 32.8 KB

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

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

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

Download in other formats: