1 /* $Id: HGSMIMemAlloc.cpp $ */
3 * VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
7 * Copyright (C) 2014-2016 Oracle Corporation
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.
22 * Area [0; AreaSize) contains only the data, control structures are separate.
23 * Block sizes are power of 2: 32B, ..., 1MB
24 * Area size can be anything and will be divided initially to largest possible free blocks.
26 * The entire area is described by a list of 32 bit block descriptors:
27 * * bits 0..3 - order, which is log2 size of the block - 5: 2^(0+5) ... 2^(15+5) == 32B .. 1MB
28 * * bit 4 - 1 for free blocks.
29 * * bits 5..31 - block offset.
31 * 31 ... 5 | 4 | 3 ... 0
34 * There is a sorted collection of all block descriptors
35 * (key is the block offset, bits 0...4 do not interfere with sorting).
36 * Also there are lists of free blocks for each size for fast allocation.
42 * The blocks collection is a sorted linear list.
44 * Initially the entire area consists of one or more largest blocks followed by smaller blocks:
45 * * 100B area - 64B block with descriptor: 0x00000011
46 * 32B block with descriptor: 0x00000030
48 * * 64K area - one 64K block with descriptor: 0x0000001C
49 * * 512K area - one 512K block with descriptor: 0x0000001F
51 * When allocating a new block:
52 * * larger free blocks are splitted when there are no smaller free blocks;
53 * * smaller free blocks are merged if they can build a requested larger block.
55 #include <VBox/HGSMI/HGSMIMemAlloc.h>
56 #include <VBox/HGSMI/HGSMI.h>
59 #include <iprt/string.h>
62 DECLINLINE(HGSMIOFFSET
) hgsmiMADescriptor(HGSMIOFFSET off
, bool fFree
, HGSMIOFFSET order
)
64 return (off
& HGSMI_MA_DESC_OFFSET_MASK
) |
65 (fFree
? HGSMI_MA_DESC_FREE_MASK
: 0) |
66 (order
& HGSMI_MA_DESC_ORDER_MASK
);
69 static void hgsmiMABlockFree(HGSMIMADATA
*pMA
, HGSMIMABLOCK
*pBlock
)
71 pMA
->env
.pfnFree(pMA
->env
.pvEnv
, pBlock
);
74 static int hgsmiMABlockAlloc(HGSMIMADATA
*pMA
, HGSMIMABLOCK
**ppBlock
)
76 int rc
= VINF_SUCCESS
;
78 HGSMIMABLOCK
*pBlock
= (HGSMIMABLOCK
*)pMA
->env
.pfnAlloc(pMA
->env
.pvEnv
, sizeof(HGSMIMABLOCK
));
81 RT_ZERO(pBlock
->nodeBlock
);
92 /* Divide entire area to free blocks. */
93 static int hgsmiMAFormat(HGSMIMADATA
*pMA
)
95 int rc
= VINF_SUCCESS
;
97 /* Initial value, it will be updated in the loop below. */
98 pMA
->cbMaxBlock
= HGSMI_MA_BLOCK_SIZE_MIN
;
101 HGSMISIZE cbBlock
= HGSMI_MA_BLOCK_SIZE_MAX
;
102 HGSMISIZE cbRemaining
= pMA
->area
.cbArea
;
105 while (cbBlock
>= HGSMI_MA_BLOCK_SIZE_MIN
)
107 /* Build a list of free memory blocks with u32BlockSize. */
108 uint32_t cBlocks
= cbRemaining
/ cbBlock
;
111 if (pMA
->cbMaxBlock
< cbBlock
)
113 pMA
->cbMaxBlock
= cbBlock
;
116 HGSMIOFFSET order
= HGSMIMASize2Order(cbBlock
);
119 for (i
= 0; i
< cBlocks
; ++i
)
121 /* A new free block. */
122 HGSMIMABLOCK
*pBlock
;
123 rc
= hgsmiMABlockAlloc(pMA
, &pBlock
);
129 pBlock
->descriptor
= hgsmiMADescriptor(off
, true, order
);
130 RTListAppend(&pMA
->listBlocks
, &pBlock
->nodeBlock
);
134 cbRemaining
-= cbBlock
;
149 static int hgsmiMARebuildFreeLists(HGSMIMADATA
*pMA
)
151 int rc
= VINF_SUCCESS
;
154 RTListForEach(&pMA
->listBlocks
, pIter
, HGSMIMABLOCK
, nodeBlock
)
156 if (HGSMI_MA_DESC_IS_FREE(pIter
->descriptor
))
158 HGSMIOFFSET order
= HGSMI_MA_DESC_ORDER(pIter
->descriptor
);
159 RTListAppend(&pMA
->aListFreeBlocks
[order
], &pIter
->nodeFree
);
166 static int hgsmiMARestore(HGSMIMADATA
*pMA
, HGSMIOFFSET
*paDescriptors
, uint32_t cDescriptors
, HGSMISIZE cbMaxBlock
)
168 int rc
= VINF_SUCCESS
;
170 pMA
->cbMaxBlock
= cbMaxBlock
;
173 HGSMISIZE cbRemaining
= pMA
->area
.cbArea
;
177 for (i
= 0; i
< cDescriptors
; ++i
)
179 /* Verify the descriptor. */
180 HGSMISIZE cbBlock
= HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(paDescriptors
[i
]));
181 if ( off
!= HGSMI_MA_DESC_OFFSET(paDescriptors
[i
])
182 || cbBlock
> cbRemaining
183 || cbBlock
> pMA
->cbMaxBlock
)
185 rc
= VERR_INVALID_PARAMETER
;
189 /* A new free block. */
190 HGSMIMABLOCK
*pBlock
;
191 rc
= hgsmiMABlockAlloc(pMA
, &pBlock
);
197 pBlock
->descriptor
= paDescriptors
[i
];
198 RTListAppend(&pMA
->listBlocks
, &pBlock
->nodeBlock
);
202 cbRemaining
-= cbBlock
;
208 static HGSMIMABLOCK
*hgsmiMAGetFreeBlock(HGSMIMADATA
*pMA
, HGSMIOFFSET order
)
210 HGSMIMABLOCK
*pBlock
= NULL
;
213 for (i
= order
; i
< RT_ELEMENTS(pMA
->aListFreeBlocks
); ++i
)
215 pBlock
= RTListGetFirst(&pMA
->aListFreeBlocks
[i
], HGSMIMABLOCK
, nodeFree
);
224 AssertReturn(HGSMI_MA_DESC_IS_FREE(pBlock
->descriptor
), NULL
);
226 /* Where the block starts. */
227 HGSMIOFFSET off
= HGSMI_MA_DESC_OFFSET(pBlock
->descriptor
);
229 /* 'i' is the order of the block. */
232 /* A larger block was found and need to be split to 2 smaller blocks. */
233 HGSMIMABLOCK
*pBlock2
;
234 int rc
= hgsmiMABlockAlloc(pMA
, &pBlock2
);
241 /* Create 2 blocks with descreased order. */
244 /* Remove from the free list. */
245 RTListNodeRemove(&pBlock
->nodeFree
);
247 pBlock
->descriptor
= hgsmiMADescriptor(off
, true, i
);
248 pBlock2
->descriptor
= hgsmiMADescriptor(off
+ HGSMIMAOrder2Size(i
), true, i
);
250 /* Update list of all blocks by inserting pBlock2 after pBlock. */
251 RTListNodeInsertAfter(&pBlock
->nodeBlock
, &pBlock2
->nodeBlock
);
254 /* Update the free list. */
255 RTListAppend(&pMA
->aListFreeBlocks
[i
], &pBlock
->nodeFree
);
256 RTListAppend(&pMA
->aListFreeBlocks
[i
], &pBlock2
->nodeFree
);
263 static void hgsmiMAReformatFreeBlocks(HGSMIMADATA
*pMA
, HGSMIOFFSET maxId
,
264 HGSMIMABLOCK
*pStart
, HGSMIMABLOCK
*pEnd
, HGSMISIZE cbBlocks
)
266 int rc
= VINF_SUCCESS
;
269 * Blocks starting from pStart until pEnd will be replaced with
270 * another set of blocks.
272 * The new set will include the block with the required order.
273 * Since the required order is larger than any existing block,
274 * it will replace at least two existing blocks.
275 * The new set will also have minimal possible number of blocks.
276 * Therefore the new set will have at least one block less.
277 * Blocks will be updated in place and remaining blocks will be
281 HGSMISIZE u32BlockSize
= HGSMIMAOrder2Size(maxId
);
282 HGSMISIZE cbRemaining
= cbBlocks
;
283 HGSMIOFFSET off
= HGSMI_MA_DESC_OFFSET(pStart
->descriptor
);
284 HGSMIMABLOCK
*pBlock
= pStart
;
286 while (u32BlockSize
>= HGSMI_MA_BLOCK_SIZE_MIN
&& cbRemaining
)
288 /* Build a list of free memory blocks with u32BlockSize. */
289 uint32_t cBlocks
= cbRemaining
/ u32BlockSize
;
292 HGSMIOFFSET order
= HGSMIMASize2Order(u32BlockSize
);
295 for (i
= 0; i
< cBlocks
; ++i
)
299 /* Should never happen because the new set of blocks is supposed to be smaller. */
301 rc
= VERR_OUT_OF_RESOURCES
;
305 /* Remove from the free list. */
306 RTListNodeRemove(&pBlock
->nodeFree
);
308 pBlock
->descriptor
= hgsmiMADescriptor(off
, true, order
);
310 RTListAppend(&pMA
->aListFreeBlocks
[order
], &pBlock
->nodeFree
);
313 cbRemaining
-= u32BlockSize
;
315 pBlock
= RTListGetNext(&pMA
->listBlocks
, pBlock
, HGSMIMABLOCK
, nodeBlock
);
327 Assert(cbRemaining
== 0);
331 /* Remove remaining free blocks from pBlock until pEnd */
334 bool fEnd
= (pBlock
== pEnd
);
335 HGSMIMABLOCK
*pNext
= RTListGetNext(&pMA
->listBlocks
, pBlock
, HGSMIMABLOCK
, nodeBlock
);
337 RTListNodeRemove(&pBlock
->nodeFree
);
338 RTListNodeRemove(&pBlock
->nodeBlock
);
341 hgsmiMABlockFree(pMA
, pBlock
);
353 static void hgsmiMAQueryFreeRange(HGSMIMADATA
*pMA
, HGSMIMABLOCK
*pBlock
, HGSMISIZE cbRequired
,
354 HGSMIMABLOCK
**ppStart
, HGSMIMABLOCK
**ppEnd
, HGSMISIZE
*pcbBlocks
)
356 Assert(HGSMI_MA_DESC_IS_FREE(pBlock
->descriptor
));
358 *pcbBlocks
= HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(pBlock
->descriptor
));
365 p
= RTListGetNext(&pMA
->listBlocks
, *ppEnd
, HGSMIMABLOCK
, nodeBlock
);
366 if (!p
|| !HGSMI_MA_DESC_IS_FREE(p
->descriptor
))
370 *pcbBlocks
+= HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p
->descriptor
));
373 if (cbRequired
&& *pcbBlocks
>= cbRequired
)
380 p
= RTListGetPrev(&pMA
->listBlocks
, *ppStart
, HGSMIMABLOCK
, nodeBlock
);
381 if (!p
|| !HGSMI_MA_DESC_IS_FREE(p
->descriptor
))
385 *pcbBlocks
+= HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p
->descriptor
));
388 if (cbRequired
&& *pcbBlocks
>= cbRequired
)
395 static void hgsmiMAMergeFreeBlocks(HGSMIMADATA
*pMA
, HGSMIOFFSET order
)
397 /* Try to create a free block with the order from smaller free blocks. */
400 /* No smaller blocks. */
404 HGSMISIZE cbRequired
= HGSMIMAOrder2Size(order
);
406 /* Scan all free lists of smaller blocks.
408 * Get the sequence of free blocks before and after each free block.
409 * If possible, re-split the sequence to get the required block and other free block(s).
410 * If not possible, try the next free block.
412 * Free blocks are scanned from i to 0 orders.
414 HGSMIOFFSET i
= order
- 1;
418 RTListForEach(&pMA
->aListFreeBlocks
[i
], pIter
, HGSMIMABLOCK
, nodeFree
)
420 Assert(HGSMI_MA_DESC_ORDER(pIter
->descriptor
) == i
);
423 HGSMIMABLOCK
*pFreeStart
;
424 HGSMIMABLOCK
*pFreeEnd
;
425 hgsmiMAQueryFreeRange(pMA
, pIter
, cbRequired
, &pFreeStart
, &pFreeEnd
, &cbBlocks
);
427 Assert((cbBlocks
/ HGSMI_MA_BLOCK_SIZE_MIN
) * HGSMI_MA_BLOCK_SIZE_MIN
== cbBlocks
);
429 /* Verify whether cbBlocks is enough for the requested block. */
430 if (cbBlocks
>= cbRequired
)
432 /* Build new free blocks starting from the requested. */
433 hgsmiMAReformatFreeBlocks(pMA
, order
, pFreeStart
, pFreeEnd
, cbBlocks
);
434 i
= 0; /* Leave the loop. */
448 static HGSMIOFFSET
hgsmiMAAlloc(HGSMIMADATA
*pMA
, HGSMISIZE cb
)
450 if (cb
> pMA
->cbMaxBlock
)
452 return HGSMIOFFSET_VOID
;
455 if (cb
< HGSMI_MA_BLOCK_SIZE_MIN
)
457 cb
= HGSMI_MA_BLOCK_SIZE_MIN
;
460 HGSMIOFFSET order
= HGSMIPopCnt32(cb
- 1) - HGSMI_MA_DESC_ORDER_BASE
;
462 AssertReturn(HGSMIMAOrder2Size(order
) >= cb
, HGSMIOFFSET_VOID
);
463 AssertReturn(order
< RT_ELEMENTS(pMA
->aListFreeBlocks
), HGSMIOFFSET_VOID
);
465 HGSMIMABLOCK
*pBlock
= hgsmiMAGetFreeBlock(pMA
, order
);
466 if (RT_UNLIKELY(pBlock
== NULL
))
468 /* No free block with large enough size. Merge smaller free blocks and try again. */
469 hgsmiMAMergeFreeBlocks(pMA
, order
);
470 pBlock
= hgsmiMAGetFreeBlock(pMA
, order
);
473 if (RT_LIKELY(pBlock
!= NULL
))
475 RTListNodeRemove(&pBlock
->nodeFree
);
476 pBlock
->descriptor
&= ~HGSMI_MA_DESC_FREE_MASK
;
477 return HGSMI_MA_DESC_OFFSET(pBlock
->descriptor
);
480 return HGSMIOFFSET_VOID
;
483 static void hgsmiMAFree(HGSMIMADATA
*pMA
, HGSMIOFFSET off
)
485 if (off
== HGSMIOFFSET_VOID
)
490 /* Find the block corresponding to the offset. */
491 Assert((off
/ HGSMI_MA_BLOCK_SIZE_MIN
) * HGSMI_MA_BLOCK_SIZE_MIN
== off
);
493 HGSMIMABLOCK
*pBlock
= HGSMIMASearchOffset(pMA
, off
);
496 if (HGSMI_MA_DESC_OFFSET(pBlock
->descriptor
) == off
)
498 /* Found the right block, mark it as free. */
499 pBlock
->descriptor
|= HGSMI_MA_DESC_FREE_MASK
;
500 RTListAppend(&pMA
->aListFreeBlocks
[HGSMI_MA_DESC_ORDER(pBlock
->descriptor
)], &pBlock
->nodeFree
);
508 int HGSMIMAInit(HGSMIMADATA
*pMA
, const HGSMIAREA
*pArea
,
509 HGSMIOFFSET
*paDescriptors
, uint32_t cDescriptors
, HGSMISIZE cbMaxBlock
,
510 const HGSMIENV
*pEnv
)
512 AssertReturn(pArea
->cbArea
< UINT32_C(0x80000000), VERR_INVALID_PARAMETER
);
513 AssertReturn(pArea
->cbArea
>= HGSMI_MA_BLOCK_SIZE_MIN
, VERR_INVALID_PARAMETER
);
517 HGSMISIZE cb
= (pArea
->cbArea
/ HGSMI_MA_BLOCK_SIZE_MIN
) * HGSMI_MA_BLOCK_SIZE_MIN
;
519 int rc
= HGSMIAreaInitialize(&pMA
->area
, pArea
->pu8Base
, cb
, 0);
525 for (i
= 0; i
< RT_ELEMENTS(pMA
->aListFreeBlocks
); ++i
)
527 RTListInit(&pMA
->aListFreeBlocks
[i
]);
529 RTListInit(&pMA
->listBlocks
);
533 rc
= hgsmiMARestore(pMA
, paDescriptors
, cDescriptors
, cbMaxBlock
);
537 rc
= hgsmiMAFormat(pMA
);
542 rc
= hgsmiMARebuildFreeLists(pMA
);
549 void HGSMIMAUninit(HGSMIMADATA
*pMA
)
554 RTListForEachSafe(&pMA
->listBlocks
, pIter
, pNext
, HGSMIMABLOCK
, nodeBlock
)
556 RTListNodeRemove(&pIter
->nodeBlock
);
557 hgsmiMABlockFree(pMA
, pIter
);
563 HGSMIOFFSET
HGSMIMAPointerToOffset(const HGSMIMADATA
*pMA
, const void *pv
)
565 if (HGSMIAreaContainsPointer(&pMA
->area
, pv
))
567 return HGSMIPointerToOffset(&pMA
->area
, pv
);
571 return HGSMIOFFSET_VOID
;
574 void *HGSMIMAOffsetToPointer(const HGSMIMADATA
*pMA
, HGSMIOFFSET off
)
576 if (HGSMIAreaContainsOffset(&pMA
->area
, off
))
578 return HGSMIOffsetToPointer(&pMA
->area
, off
);
585 void *HGSMIMAAlloc(HGSMIMADATA
*pMA
, HGSMISIZE cb
)
587 HGSMIOFFSET off
= hgsmiMAAlloc(pMA
, cb
);
588 return HGSMIMAOffsetToPointer(pMA
, off
);
591 void HGSMIMAFree(HGSMIMADATA
*pMA
, void *pv
)
593 HGSMIOFFSET off
= HGSMIMAPointerToOffset(pMA
, pv
);
594 if (off
!= HGSMIOFFSET_VOID
)
596 hgsmiMAFree(pMA
, off
);
604 HGSMIMABLOCK
*HGSMIMASearchOffset(HGSMIMADATA
*pMA
, HGSMIOFFSET off
)
606 /* Binary search in the block list for the offset. */
607 HGSMIMABLOCK
*pStart
= RTListGetFirst(&pMA
->listBlocks
, HGSMIMABLOCK
, nodeBlock
);
608 HGSMIMABLOCK
*pEnd
= RTListGetLast(&pMA
->listBlocks
, HGSMIMABLOCK
, nodeBlock
);
609 HGSMIMABLOCK
*pMiddle
;
612 uint32_t iEnd
= pMA
->cBlocks
;
618 iMiddle
= iStart
+ (iEnd
- iStart
) / 2;
619 if (iMiddle
== iStart
)
624 /* Find the block with the iMiddle index. Never go further than pEnd. */
626 for (i
= iStart
; i
< iMiddle
&& pMiddle
!= pEnd
; ++i
)
628 pMiddle
= RTListNodeGetNext(&pMiddle
->nodeBlock
, HGSMIMABLOCK
, nodeBlock
);
631 HGSMIOFFSET offMiddle
= HGSMI_MA_DESC_OFFSET(pMiddle
->descriptor
);
652 uint32_t HGSMIPopCnt32(uint32_t u32
)
655 if (u32
> 0xFFFF) { c
+= 16; u32
>>= 16; }
656 if (u32
> 0xFF) { c
+= 8; u32
>>= 8; }
657 if (u32
> 0xF) { c
+= 4; u32
>>= 4; }
658 if (u32
> 0x3) { c
+= 2; u32
>>= 2; }
659 if (u32
> 0x1) { c
+= 1; u32
>>= 1; }