VirtualBox

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

Last change on this file since 628 was 331, checked in by vboxsync, 18 years ago

Bool and AMD64 hacking.

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette