heapsimple.cpp@ 80346

Last change on this file since 80346 was 76553, checked in by vboxsync, 6 years ago
scm --update-copyright-year
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 30.7 KB

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

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

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

Download in other formats: