heapsimple.cpp@ 106579

Last change on this file since 106579 was 106061, checked in by vboxsync, 3 months ago
Copyright year updates by scm.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 31.0 KB

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

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

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

Download in other formats: