VirtualBox

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

Last change on this file was 100308, checked in by vboxsync, 11 months ago

Runtime: Replace occurence of PAGE_SIZE with RTSystemgetPageSize() in code used by linux.arm64 guest additions, bugref:10476
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 31.0 KB
Line 
1/* $Id: heapsimple.cpp 100308 2023-06-28 10:24:38Z vboxsync $ */
2/** @file
3 * IPRT - A Simple Heap.
4 */
5
6/*
7 * Copyright (C) 2006-2023 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. */
59typedef struct RTHEAPSIMPLEINTERNAL *PRTHEAPSIMPLEINTERNAL;
60/** Pointer to a heap block. */
61typedef struct RTHEAPSIMPLEBLOCK *PRTHEAPSIMPLEBLOCK;
62/** Pointer to a free heap block. */
63typedef 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 */
70typedef 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;
81AssertCompileSizeAlignment(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 */
128typedef 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 */
148typedef 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;
165AssertCompileSizeAlignment(RTHEAPSIMPLEINTERNAL, 32);
166
167
168/** The minimum allocation size. */
169#define RTHEAPSIMPLE_MIN_BLOCK (sizeof(RTHEAPSIMPLEBLOCK))
170AssertCompile(RTHEAPSIMPLE_MIN_BLOCK >= sizeof(RTHEAPSIMPLEBLOCK));
171AssertCompile(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
284static void rtHeapSimpleAssertAll(PRTHEAPSIMPLEINTERNAL pHeapInt);
285#endif
286static PRTHEAPSIMPLEBLOCK rtHeapSimpleAllocBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, size_t cb, size_t uAlignment);
287static void rtHeapSimpleFreeBlock(PRTHEAPSIMPLEINTERNAL pHeapInt, PRTHEAPSIMPLEBLOCK pBlock);
288
289
290RTDECL(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}
345RT_EXPORT_SYMBOL(RTHeapSimpleInit);
346
347
348RTDECL(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}
396RT_EXPORT_SYMBOL(RTHeapSimpleRelocate);
397
398
399RTDECL(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}
433RT_EXPORT_SYMBOL(RTHeapSimpleAlloc);
434
435
436RTDECL(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}
471RT_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 */
486static 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
649RTDECL(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}
685RT_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 */
694static 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 */
816static 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
842RTDECL(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}
872RT_EXPORT_SYMBOL(RTHeapSimpleSize);
873
874
875RTDECL(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}
887RT_EXPORT_SYMBOL(RTHeapSimpleGetHeapSize);
888
889
890RTDECL(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}
902RT_EXPORT_SYMBOL(RTHeapSimpleGetFreeSize);
903
904
905RTDECL(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}
929RT_EXPORT_SYMBOL(RTHeapSimpleDump);
930
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use