1 | /* $Id: HGSMIMemAlloc.cpp 98103 2023-01-17 14:15:46Z vboxsync $ */
|
---|
2 | /** @file
|
---|
3 | * VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
|
---|
4 | */
|
---|
5 |
|
---|
6 | /*
|
---|
7 | * Copyright (C) 2014-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 | * SPDX-License-Identifier: GPL-3.0-only
|
---|
26 | */
|
---|
27 |
|
---|
28 | /*
|
---|
29 | * Memory allocator
|
---|
30 | * ----------------
|
---|
31 | *
|
---|
32 | * Area [0; AreaSize) contains only the data, control structures are separate.
|
---|
33 | * Block sizes are power of 2: 32B, ..., 1MB
|
---|
34 | * Area size can be anything and will be divided initially to largest possible free blocks.
|
---|
35 | *
|
---|
36 | * The entire area is described by a list of 32 bit block descriptors:
|
---|
37 | * * bits 0..3 - order, which is log2 size of the block - 5: 2^(0+5) ... 2^(15+5) == 32B .. 1MB
|
---|
38 | * * bit 4 - 1 for free blocks.
|
---|
39 | * * bits 5..31 - block offset.
|
---|
40 | *
|
---|
41 | * 31 ... 5 | 4 | 3 ... 0
|
---|
42 | * offset F order
|
---|
43 | *
|
---|
44 | * There is a sorted collection of all block descriptors
|
---|
45 | * (key is the block offset, bits 0...4 do not interfere with sorting).
|
---|
46 | * Also there are lists of free blocks for each size for fast allocation.
|
---|
47 | *
|
---|
48 | *
|
---|
49 | * Implementation
|
---|
50 | * --------------
|
---|
51 | *
|
---|
52 | * The blocks collection is a sorted linear list.
|
---|
53 | *
|
---|
54 | * Initially the entire area consists of one or more largest blocks followed by smaller blocks:
|
---|
55 | * * 100B area - 64B block with descriptor: 0x00000011
|
---|
56 | * 32B block with descriptor: 0x00000030
|
---|
57 | * 4B unused
|
---|
58 | * * 64K area - one 64K block with descriptor: 0x0000001C
|
---|
59 | * * 512K area - one 512K block with descriptor: 0x0000001F
|
---|
60 | *
|
---|
61 | * When allocating a new block:
|
---|
62 | * * larger free blocks are splitted when there are no smaller free blocks;
|
---|
63 | * * smaller free blocks are merged if they can build a requested larger block.
|
---|
64 | */
|
---|
65 | #include <HGSMIMemAlloc.h>
|
---|
66 | #include <HGSMI.h>
|
---|
67 |
|
---|
68 | #include <VBoxVideoIPRT.h>
|
---|
69 |
|
---|
70 | /*
|
---|
71 | * We do not want assertions in Linux kernel code to reduce symbol dependencies.
|
---|
72 | */
|
---|
73 | #if defined(IN_RING0) && defined(RT_OS_LINUX)
|
---|
74 | # define HGSMI_ASSERT_RETURN(a, b) if (!(a)) return (b)
|
---|
75 | # define HGSMI_ASSERT_FAILED() do {} while (0)
|
---|
76 | # define HGSMI_ASSERT(expr) do {} while (0)
|
---|
77 | #else
|
---|
78 | # define HGSMI_ASSERT_RETURN(a, b) AssertReturn(a, b)
|
---|
79 | # define HGSMI_ASSERT_FAILED() AssertFailed()
|
---|
80 | # define HGSMI_ASSERT(expr) Assert(expr)
|
---|
81 | #endif /* !IN_RING0 && RT_OS_LINUX */
|
---|
82 |
|
---|
83 | DECLINLINE(HGSMIOFFSET) hgsmiMADescriptor(HGSMIOFFSET off, bool fFree, HGSMIOFFSET order)
|
---|
84 | {
|
---|
85 | return (off & HGSMI_MA_DESC_OFFSET_MASK) |
|
---|
86 | (fFree? HGSMI_MA_DESC_FREE_MASK: 0) |
|
---|
87 | (order & HGSMI_MA_DESC_ORDER_MASK);
|
---|
88 | }
|
---|
89 |
|
---|
90 | static void hgsmiMABlockFree(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock)
|
---|
91 | {
|
---|
92 | pMA->env.pfnFree(pMA->env.pvEnv, pBlock);
|
---|
93 | }
|
---|
94 |
|
---|
95 | static int hgsmiMABlockAlloc(HGSMIMADATA *pMA, HGSMIMABLOCK **ppBlock)
|
---|
96 | {
|
---|
97 | int rc = VINF_SUCCESS;
|
---|
98 |
|
---|
99 | HGSMIMABLOCK *pBlock = (HGSMIMABLOCK *)pMA->env.pfnAlloc(pMA->env.pvEnv, sizeof(HGSMIMABLOCK));
|
---|
100 | if (pBlock)
|
---|
101 | {
|
---|
102 | RT_ZERO(pBlock->nodeBlock);
|
---|
103 | *ppBlock = pBlock;
|
---|
104 | }
|
---|
105 | else
|
---|
106 | {
|
---|
107 | rc = VERR_NO_MEMORY;
|
---|
108 | }
|
---|
109 |
|
---|
110 | return rc;
|
---|
111 | }
|
---|
112 |
|
---|
113 | /* Divide entire area to free blocks. */
|
---|
114 | static int hgsmiMAFormat(HGSMIMADATA *pMA)
|
---|
115 | {
|
---|
116 | int rc = VINF_SUCCESS;
|
---|
117 |
|
---|
118 | /* Initial value, it will be updated in the loop below. */
|
---|
119 | pMA->cbMaxBlock = HGSMI_MA_BLOCK_SIZE_MIN;
|
---|
120 | pMA->cBlocks = 0;
|
---|
121 |
|
---|
122 | HGSMISIZE cbBlock = HGSMI_MA_BLOCK_SIZE_MAX;
|
---|
123 | HGSMISIZE cbRemaining = pMA->area.cbArea;
|
---|
124 | HGSMIOFFSET off = 0;
|
---|
125 |
|
---|
126 | while (cbBlock >= HGSMI_MA_BLOCK_SIZE_MIN)
|
---|
127 | {
|
---|
128 | /* Build a list of free memory blocks with u32BlockSize. */
|
---|
129 | uint32_t cBlocks = cbRemaining / cbBlock;
|
---|
130 | if (cBlocks > 0)
|
---|
131 | {
|
---|
132 | if (pMA->cbMaxBlock < cbBlock)
|
---|
133 | {
|
---|
134 | pMA->cbMaxBlock = cbBlock;
|
---|
135 | }
|
---|
136 |
|
---|
137 | HGSMIOFFSET order = HGSMIMASize2Order(cbBlock);
|
---|
138 |
|
---|
139 | uint32_t i;
|
---|
140 | for (i = 0; i < cBlocks; ++i)
|
---|
141 | {
|
---|
142 | /* A new free block. */
|
---|
143 | HGSMIMABLOCK *pBlock;
|
---|
144 | rc = hgsmiMABlockAlloc(pMA, &pBlock);
|
---|
145 | if (RT_FAILURE(rc))
|
---|
146 | {
|
---|
147 | break;
|
---|
148 | }
|
---|
149 |
|
---|
150 | pBlock->descriptor = hgsmiMADescriptor(off, true, order);
|
---|
151 | RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
|
---|
152 | ++pMA->cBlocks;
|
---|
153 |
|
---|
154 | off += cbBlock;
|
---|
155 | cbRemaining -= cbBlock;
|
---|
156 | }
|
---|
157 | }
|
---|
158 |
|
---|
159 | if (RT_FAILURE(rc))
|
---|
160 | {
|
---|
161 | break;
|
---|
162 | }
|
---|
163 |
|
---|
164 | cbBlock /= 2;
|
---|
165 | }
|
---|
166 |
|
---|
167 | return rc;
|
---|
168 | }
|
---|
169 |
|
---|
170 | static int hgsmiMARebuildFreeLists(HGSMIMADATA *pMA)
|
---|
171 | {
|
---|
172 | int rc = VINF_SUCCESS;
|
---|
173 |
|
---|
174 | HGSMIMABLOCK *pIter;
|
---|
175 | RTListForEach(&pMA->listBlocks, pIter, HGSMIMABLOCK, nodeBlock)
|
---|
176 | {
|
---|
177 | if (HGSMI_MA_DESC_IS_FREE(pIter->descriptor))
|
---|
178 | {
|
---|
179 | HGSMIOFFSET order = HGSMI_MA_DESC_ORDER(pIter->descriptor);
|
---|
180 | RTListAppend(&pMA->aListFreeBlocks[order], &pIter->nodeFree);
|
---|
181 | }
|
---|
182 | }
|
---|
183 |
|
---|
184 | return rc;
|
---|
185 | }
|
---|
186 |
|
---|
187 | static int hgsmiMARestore(HGSMIMADATA *pMA, HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock)
|
---|
188 | {
|
---|
189 | int rc = VINF_SUCCESS;
|
---|
190 |
|
---|
191 | pMA->cbMaxBlock = cbMaxBlock;
|
---|
192 | pMA->cBlocks = 0;
|
---|
193 |
|
---|
194 | HGSMISIZE cbRemaining = pMA->area.cbArea;
|
---|
195 | HGSMIOFFSET off = 0;
|
---|
196 |
|
---|
197 | uint32_t i;
|
---|
198 | for (i = 0; i < cDescriptors; ++i)
|
---|
199 | {
|
---|
200 | /* Verify the descriptor. */
|
---|
201 | HGSMISIZE cbBlock = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(paDescriptors[i]));
|
---|
202 | if ( off != HGSMI_MA_DESC_OFFSET(paDescriptors[i])
|
---|
203 | || cbBlock > cbRemaining
|
---|
204 | || cbBlock > pMA->cbMaxBlock)
|
---|
205 | {
|
---|
206 | rc = VERR_INVALID_PARAMETER;
|
---|
207 | break;
|
---|
208 | }
|
---|
209 |
|
---|
210 | /* A new free block. */
|
---|
211 | HGSMIMABLOCK *pBlock;
|
---|
212 | rc = hgsmiMABlockAlloc(pMA, &pBlock);
|
---|
213 | if (RT_FAILURE(rc))
|
---|
214 | {
|
---|
215 | break;
|
---|
216 | }
|
---|
217 |
|
---|
218 | pBlock->descriptor = paDescriptors[i];
|
---|
219 | RTListAppend(&pMA->listBlocks, &pBlock->nodeBlock);
|
---|
220 | ++pMA->cBlocks;
|
---|
221 |
|
---|
222 | off += cbBlock;
|
---|
223 | cbRemaining -= cbBlock;
|
---|
224 | }
|
---|
225 |
|
---|
226 | return rc;
|
---|
227 | }
|
---|
228 |
|
---|
229 | static HGSMIMABLOCK *hgsmiMAGetFreeBlock(HGSMIMADATA *pMA, HGSMIOFFSET order)
|
---|
230 | {
|
---|
231 | HGSMIMABLOCK *pBlock = NULL;
|
---|
232 |
|
---|
233 | HGSMIOFFSET i;
|
---|
234 | for (i = order; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
|
---|
235 | {
|
---|
236 | pBlock = RTListGetFirst(&pMA->aListFreeBlocks[i], HGSMIMABLOCK, nodeFree);
|
---|
237 | if (pBlock)
|
---|
238 | {
|
---|
239 | break;
|
---|
240 | }
|
---|
241 | }
|
---|
242 |
|
---|
243 | if (pBlock)
|
---|
244 | {
|
---|
245 | HGSMI_ASSERT_RETURN(HGSMI_MA_DESC_IS_FREE(pBlock->descriptor), NULL);
|
---|
246 |
|
---|
247 | /* Where the block starts. */
|
---|
248 | HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pBlock->descriptor);
|
---|
249 |
|
---|
250 | /* 'i' is the order of the block. */
|
---|
251 | while (i != order)
|
---|
252 | {
|
---|
253 | /* A larger block was found and need to be split to 2 smaller blocks. */
|
---|
254 | HGSMIMABLOCK *pBlock2;
|
---|
255 | int rc = hgsmiMABlockAlloc(pMA, &pBlock2);
|
---|
256 | if (RT_FAILURE(rc))
|
---|
257 | {
|
---|
258 | pBlock = NULL;
|
---|
259 | break;
|
---|
260 | }
|
---|
261 |
|
---|
262 | /* Create 2 blocks with descreased order. */
|
---|
263 | --i;
|
---|
264 |
|
---|
265 | /* Remove from the free list. */
|
---|
266 | RTListNodeRemove(&pBlock->nodeFree);
|
---|
267 |
|
---|
268 | pBlock->descriptor = hgsmiMADescriptor(off, true, i);
|
---|
269 | pBlock2->descriptor = hgsmiMADescriptor(off + HGSMIMAOrder2Size(i), true, i);
|
---|
270 |
|
---|
271 | /* Update list of all blocks by inserting pBlock2 after pBlock. */
|
---|
272 | RTListNodeInsertAfter(&pBlock->nodeBlock, &pBlock2->nodeBlock);
|
---|
273 | ++pMA->cBlocks;
|
---|
274 |
|
---|
275 | /* Update the free list. */
|
---|
276 | RTListAppend(&pMA->aListFreeBlocks[i], &pBlock->nodeFree);
|
---|
277 | RTListAppend(&pMA->aListFreeBlocks[i], &pBlock2->nodeFree);
|
---|
278 | }
|
---|
279 | }
|
---|
280 |
|
---|
281 | return pBlock;
|
---|
282 | }
|
---|
283 |
|
---|
284 | static void hgsmiMAReformatFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET maxId,
|
---|
285 | HGSMIMABLOCK *pStart, HGSMIMABLOCK *pEnd, HGSMISIZE cbBlocks)
|
---|
286 | {
|
---|
287 | int rc = VINF_SUCCESS;
|
---|
288 |
|
---|
289 | /*
|
---|
290 | * Blocks starting from pStart until pEnd will be replaced with
|
---|
291 | * another set of blocks.
|
---|
292 | *
|
---|
293 | * The new set will include the block with the required order.
|
---|
294 | * Since the required order is larger than any existing block,
|
---|
295 | * it will replace at least two existing blocks.
|
---|
296 | * The new set will also have minimal possible number of blocks.
|
---|
297 | * Therefore the new set will have at least one block less.
|
---|
298 | * Blocks will be updated in place and remaining blocks will be
|
---|
299 | * deallocated.
|
---|
300 | */
|
---|
301 |
|
---|
302 | HGSMISIZE u32BlockSize = HGSMIMAOrder2Size(maxId);
|
---|
303 | HGSMISIZE cbRemaining = cbBlocks;
|
---|
304 | HGSMIOFFSET off = HGSMI_MA_DESC_OFFSET(pStart->descriptor);
|
---|
305 | HGSMIMABLOCK *pBlock = pStart;
|
---|
306 |
|
---|
307 | while (u32BlockSize >= HGSMI_MA_BLOCK_SIZE_MIN && cbRemaining)
|
---|
308 | {
|
---|
309 | /* Build a list of free memory blocks with u32BlockSize. */
|
---|
310 | uint32_t cBlocks = cbRemaining / u32BlockSize;
|
---|
311 | if (cBlocks > 0)
|
---|
312 | {
|
---|
313 | HGSMIOFFSET order = HGSMIMASize2Order(u32BlockSize);
|
---|
314 |
|
---|
315 | uint32_t i;
|
---|
316 | for (i = 0; i < cBlocks; ++i)
|
---|
317 | {
|
---|
318 | if (pBlock == pEnd)
|
---|
319 | {
|
---|
320 | /* Should never happen because the new set of blocks is supposed to be smaller. */
|
---|
321 | HGSMI_ASSERT_FAILED();
|
---|
322 | rc = VERR_OUT_OF_RESOURCES;
|
---|
323 | break;
|
---|
324 | }
|
---|
325 |
|
---|
326 | /* Remove from the free list. */
|
---|
327 | RTListNodeRemove(&pBlock->nodeFree);
|
---|
328 |
|
---|
329 | pBlock->descriptor = hgsmiMADescriptor(off, true, order);
|
---|
330 |
|
---|
331 | RTListAppend(&pMA->aListFreeBlocks[order], &pBlock->nodeFree);
|
---|
332 |
|
---|
333 | off += u32BlockSize;
|
---|
334 | cbRemaining -= u32BlockSize;
|
---|
335 |
|
---|
336 | pBlock = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
|
---|
337 | }
|
---|
338 | }
|
---|
339 |
|
---|
340 | if (RT_FAILURE(rc))
|
---|
341 | {
|
---|
342 | break;
|
---|
343 | }
|
---|
344 |
|
---|
345 | u32BlockSize /= 2;
|
---|
346 | }
|
---|
347 |
|
---|
348 | HGSMI_ASSERT(cbRemaining == 0);
|
---|
349 |
|
---|
350 | if (RT_SUCCESS(rc))
|
---|
351 | {
|
---|
352 | /* Remove remaining free blocks from pBlock until pEnd */
|
---|
353 | for (;;)
|
---|
354 | {
|
---|
355 | bool fEnd = (pBlock == pEnd);
|
---|
356 | HGSMIMABLOCK *pNext = RTListGetNext(&pMA->listBlocks, pBlock, HGSMIMABLOCK, nodeBlock);
|
---|
357 |
|
---|
358 | RTListNodeRemove(&pBlock->nodeFree);
|
---|
359 | RTListNodeRemove(&pBlock->nodeBlock);
|
---|
360 | --pMA->cBlocks;
|
---|
361 |
|
---|
362 | hgsmiMABlockFree(pMA, pBlock);
|
---|
363 |
|
---|
364 | if (fEnd)
|
---|
365 | {
|
---|
366 | break;
|
---|
367 | }
|
---|
368 |
|
---|
369 | pBlock = pNext;
|
---|
370 | }
|
---|
371 | }
|
---|
372 | }
|
---|
373 |
|
---|
374 | static void hgsmiMAQueryFreeRange(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock, HGSMISIZE cbRequired,
|
---|
375 | HGSMIMABLOCK **ppStart, HGSMIMABLOCK **ppEnd, HGSMISIZE *pcbBlocks)
|
---|
376 | {
|
---|
377 | HGSMI_ASSERT(HGSMI_MA_DESC_IS_FREE(pBlock->descriptor));
|
---|
378 |
|
---|
379 | *pcbBlocks = HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(pBlock->descriptor));
|
---|
380 | *ppStart = pBlock;
|
---|
381 | *ppEnd = pBlock;
|
---|
382 |
|
---|
383 | HGSMIMABLOCK *p;
|
---|
384 | for (;;)
|
---|
385 | {
|
---|
386 | p = RTListGetNext(&pMA->listBlocks, *ppEnd, HGSMIMABLOCK, nodeBlock);
|
---|
387 | if (!p || !HGSMI_MA_DESC_IS_FREE(p->descriptor))
|
---|
388 | {
|
---|
389 | break;
|
---|
390 | }
|
---|
391 | *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
|
---|
392 | *ppEnd = p;
|
---|
393 |
|
---|
394 | if (cbRequired && *pcbBlocks >= cbRequired)
|
---|
395 | {
|
---|
396 | return;
|
---|
397 | }
|
---|
398 | }
|
---|
399 | for (;;)
|
---|
400 | {
|
---|
401 | p = RTListGetPrev(&pMA->listBlocks, *ppStart, HGSMIMABLOCK, nodeBlock);
|
---|
402 | if (!p || !HGSMI_MA_DESC_IS_FREE(p->descriptor))
|
---|
403 | {
|
---|
404 | break;
|
---|
405 | }
|
---|
406 | *pcbBlocks += HGSMIMAOrder2Size(HGSMI_MA_DESC_ORDER(p->descriptor));
|
---|
407 | *ppStart = p;
|
---|
408 |
|
---|
409 | if (cbRequired && *pcbBlocks >= cbRequired)
|
---|
410 | {
|
---|
411 | return;
|
---|
412 | }
|
---|
413 | }
|
---|
414 | }
|
---|
415 |
|
---|
416 | static void hgsmiMAMergeFreeBlocks(HGSMIMADATA *pMA, HGSMIOFFSET order)
|
---|
417 | {
|
---|
418 | /* Try to create a free block with the order from smaller free blocks. */
|
---|
419 | if (order == 0)
|
---|
420 | {
|
---|
421 | /* No smaller blocks. */
|
---|
422 | return;
|
---|
423 | }
|
---|
424 |
|
---|
425 | HGSMISIZE cbRequired = HGSMIMAOrder2Size(order);
|
---|
426 |
|
---|
427 | /* Scan all free lists of smaller blocks.
|
---|
428 | *
|
---|
429 | * Get the sequence of free blocks before and after each free block.
|
---|
430 | * If possible, re-split the sequence to get the required block and other free block(s).
|
---|
431 | * If not possible, try the next free block.
|
---|
432 | *
|
---|
433 | * Free blocks are scanned from i to 0 orders.
|
---|
434 | */
|
---|
435 | HGSMIOFFSET i = order - 1;
|
---|
436 | for (;;)
|
---|
437 | {
|
---|
438 | HGSMIMABLOCK *pIter;
|
---|
439 | RTListForEach(&pMA->aListFreeBlocks[i], pIter, HGSMIMABLOCK, nodeFree)
|
---|
440 | {
|
---|
441 | HGSMI_ASSERT(HGSMI_MA_DESC_ORDER(pIter->descriptor) == i);
|
---|
442 |
|
---|
443 | HGSMISIZE cbBlocks;
|
---|
444 | HGSMIMABLOCK *pFreeStart;
|
---|
445 | HGSMIMABLOCK *pFreeEnd;
|
---|
446 | hgsmiMAQueryFreeRange(pMA, pIter, cbRequired, &pFreeStart, &pFreeEnd, &cbBlocks);
|
---|
447 |
|
---|
448 | HGSMI_ASSERT((cbBlocks / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == cbBlocks);
|
---|
449 |
|
---|
450 | /* Verify whether cbBlocks is enough for the requested block. */
|
---|
451 | if (cbBlocks >= cbRequired)
|
---|
452 | {
|
---|
453 | /* Build new free blocks starting from the requested. */
|
---|
454 | hgsmiMAReformatFreeBlocks(pMA, order, pFreeStart, pFreeEnd, cbBlocks);
|
---|
455 | i = 0; /* Leave the loop. */
|
---|
456 | break;
|
---|
457 | }
|
---|
458 | }
|
---|
459 |
|
---|
460 | if (i == 0)
|
---|
461 | {
|
---|
462 | break;
|
---|
463 | }
|
---|
464 |
|
---|
465 | --i;
|
---|
466 | }
|
---|
467 | }
|
---|
468 |
|
---|
469 | static HGSMIOFFSET hgsmiMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
|
---|
470 | {
|
---|
471 | if (cb > pMA->cbMaxBlock)
|
---|
472 | {
|
---|
473 | return HGSMIOFFSET_VOID;
|
---|
474 | }
|
---|
475 |
|
---|
476 | if (cb < HGSMI_MA_BLOCK_SIZE_MIN)
|
---|
477 | {
|
---|
478 | cb = HGSMI_MA_BLOCK_SIZE_MIN;
|
---|
479 | }
|
---|
480 |
|
---|
481 | HGSMIOFFSET order = HGSMIPopCnt32(cb - 1) - HGSMI_MA_DESC_ORDER_BASE;
|
---|
482 |
|
---|
483 | HGSMI_ASSERT_RETURN(HGSMIMAOrder2Size(order) >= cb, HGSMIOFFSET_VOID);
|
---|
484 | HGSMI_ASSERT_RETURN(order < RT_ELEMENTS(pMA->aListFreeBlocks), HGSMIOFFSET_VOID);
|
---|
485 |
|
---|
486 | HGSMIMABLOCK *pBlock = hgsmiMAGetFreeBlock(pMA, order);
|
---|
487 | if (RT_UNLIKELY(pBlock == NULL))
|
---|
488 | {
|
---|
489 | /* No free block with large enough size. Merge smaller free blocks and try again. */
|
---|
490 | hgsmiMAMergeFreeBlocks(pMA, order);
|
---|
491 | pBlock = hgsmiMAGetFreeBlock(pMA, order);
|
---|
492 | }
|
---|
493 |
|
---|
494 | if (RT_LIKELY(pBlock != NULL))
|
---|
495 | {
|
---|
496 | RTListNodeRemove(&pBlock->nodeFree);
|
---|
497 | pBlock->descriptor &= ~HGSMI_MA_DESC_FREE_MASK;
|
---|
498 | return HGSMI_MA_DESC_OFFSET(pBlock->descriptor);
|
---|
499 | }
|
---|
500 |
|
---|
501 | return HGSMIOFFSET_VOID;
|
---|
502 | }
|
---|
503 |
|
---|
504 | static void hgsmiMAFree(HGSMIMADATA *pMA, HGSMIOFFSET off)
|
---|
505 | {
|
---|
506 | if (off == HGSMIOFFSET_VOID)
|
---|
507 | {
|
---|
508 | return;
|
---|
509 | }
|
---|
510 |
|
---|
511 | /* Find the block corresponding to the offset. */
|
---|
512 | HGSMI_ASSERT((off / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN == off);
|
---|
513 |
|
---|
514 | HGSMIMABLOCK *pBlock = HGSMIMASearchOffset(pMA, off);
|
---|
515 | if (pBlock)
|
---|
516 | {
|
---|
517 | if (HGSMI_MA_DESC_OFFSET(pBlock->descriptor) == off)
|
---|
518 | {
|
---|
519 | /* Found the right block, mark it as free. */
|
---|
520 | pBlock->descriptor |= HGSMI_MA_DESC_FREE_MASK;
|
---|
521 | RTListAppend(&pMA->aListFreeBlocks[HGSMI_MA_DESC_ORDER(pBlock->descriptor)], &pBlock->nodeFree);
|
---|
522 | return;
|
---|
523 | }
|
---|
524 | }
|
---|
525 |
|
---|
526 | HGSMI_ASSERT_FAILED();
|
---|
527 | }
|
---|
528 |
|
---|
529 | int HGSMIMAInit(HGSMIMADATA *pMA, const HGSMIAREA *pArea,
|
---|
530 | HGSMIOFFSET *paDescriptors, uint32_t cDescriptors, HGSMISIZE cbMaxBlock,
|
---|
531 | const HGSMIENV *pEnv)
|
---|
532 | {
|
---|
533 | HGSMI_ASSERT_RETURN(pArea->cbArea < UINT32_C(0x80000000), VERR_INVALID_PARAMETER);
|
---|
534 | HGSMI_ASSERT_RETURN(pArea->cbArea >= HGSMI_MA_BLOCK_SIZE_MIN, VERR_INVALID_PARAMETER);
|
---|
535 |
|
---|
536 | RT_ZERO(*pMA);
|
---|
537 |
|
---|
538 | HGSMISIZE cb = (pArea->cbArea / HGSMI_MA_BLOCK_SIZE_MIN) * HGSMI_MA_BLOCK_SIZE_MIN;
|
---|
539 |
|
---|
540 | int rc = HGSMIAreaInitialize(&pMA->area, pArea->pu8Base, cb, 0);
|
---|
541 | if (RT_SUCCESS(rc))
|
---|
542 | {
|
---|
543 | pMA->env = *pEnv;
|
---|
544 |
|
---|
545 | uint32_t i;
|
---|
546 | for (i = 0; i < RT_ELEMENTS(pMA->aListFreeBlocks); ++i)
|
---|
547 | {
|
---|
548 | RTListInit(&pMA->aListFreeBlocks[i]);
|
---|
549 | }
|
---|
550 | RTListInit(&pMA->listBlocks);
|
---|
551 |
|
---|
552 | if (cDescriptors)
|
---|
553 | {
|
---|
554 | rc = hgsmiMARestore(pMA, paDescriptors, cDescriptors, cbMaxBlock);
|
---|
555 | }
|
---|
556 | else
|
---|
557 | {
|
---|
558 | rc = hgsmiMAFormat(pMA);
|
---|
559 | }
|
---|
560 |
|
---|
561 | if (RT_SUCCESS(rc))
|
---|
562 | {
|
---|
563 | rc = hgsmiMARebuildFreeLists(pMA);
|
---|
564 | }
|
---|
565 | }
|
---|
566 |
|
---|
567 | return rc;
|
---|
568 | }
|
---|
569 |
|
---|
570 | void HGSMIMAUninit(HGSMIMADATA *pMA)
|
---|
571 | {
|
---|
572 | HGSMIMABLOCK *pIter;
|
---|
573 | HGSMIMABLOCK *pNext;
|
---|
574 | /* If it has been initialized. */
|
---|
575 | if (pMA->listBlocks.pNext)
|
---|
576 | {
|
---|
577 | RTListForEachSafe(&pMA->listBlocks, pIter, pNext, HGSMIMABLOCK, nodeBlock)
|
---|
578 | {
|
---|
579 | RTListNodeRemove(&pIter->nodeBlock);
|
---|
580 | hgsmiMABlockFree(pMA, pIter);
|
---|
581 | }
|
---|
582 | }
|
---|
583 |
|
---|
584 | RT_ZERO(*pMA);
|
---|
585 | }
|
---|
586 |
|
---|
587 | HGSMIOFFSET HGSMIMAPointerToOffset(const HGSMIMADATA *pMA, const void RT_UNTRUSTED_VOLATILE_GUEST *pv)
|
---|
588 | {
|
---|
589 | uintptr_t off = (uintptr_t)pv - (uintptr_t)pMA->area.pu8Base;
|
---|
590 | if (off < pMA->area.cbArea)
|
---|
591 | return pMA->area.offBase + off;
|
---|
592 |
|
---|
593 | HGSMI_ASSERT_FAILED();
|
---|
594 | return HGSMIOFFSET_VOID;
|
---|
595 | }
|
---|
596 |
|
---|
597 | static void RT_UNTRUSTED_VOLATILE_HSTGST *HGSMIMAOffsetToPointer(const HGSMIMADATA *pMA, HGSMIOFFSET off)
|
---|
598 | {
|
---|
599 | if (HGSMIAreaContainsOffset(&pMA->area, off))
|
---|
600 | {
|
---|
601 | return HGSMIOffsetToPointer(&pMA->area, off);
|
---|
602 | }
|
---|
603 |
|
---|
604 | HGSMI_ASSERT_FAILED();
|
---|
605 | return NULL;
|
---|
606 | }
|
---|
607 |
|
---|
608 | void RT_UNTRUSTED_VOLATILE_HSTGST *HGSMIMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
|
---|
609 | {
|
---|
610 | HGSMIOFFSET off = hgsmiMAAlloc(pMA, cb);
|
---|
611 | return HGSMIMAOffsetToPointer(pMA, off);
|
---|
612 | }
|
---|
613 |
|
---|
614 | void HGSMIMAFree(HGSMIMADATA *pMA, void RT_UNTRUSTED_VOLATILE_GUEST *pv)
|
---|
615 | {
|
---|
616 | HGSMIOFFSET off = HGSMIMAPointerToOffset(pMA, pv);
|
---|
617 | if (off != HGSMIOFFSET_VOID)
|
---|
618 | {
|
---|
619 | hgsmiMAFree(pMA, off);
|
---|
620 | }
|
---|
621 | else
|
---|
622 | {
|
---|
623 | HGSMI_ASSERT_FAILED();
|
---|
624 | }
|
---|
625 | }
|
---|
626 |
|
---|
627 | HGSMIMABLOCK *HGSMIMASearchOffset(HGSMIMADATA *pMA, HGSMIOFFSET off)
|
---|
628 | {
|
---|
629 | /* Binary search in the block list for the offset. */
|
---|
630 | HGSMIMABLOCK *pStart = RTListGetFirst(&pMA->listBlocks, HGSMIMABLOCK, nodeBlock);
|
---|
631 | HGSMIMABLOCK *pEnd = RTListGetLast(&pMA->listBlocks, HGSMIMABLOCK, nodeBlock);
|
---|
632 | HGSMIMABLOCK *pMiddle;
|
---|
633 |
|
---|
634 | uint32_t iStart = 0;
|
---|
635 | uint32_t iEnd = pMA->cBlocks;
|
---|
636 | uint32_t iMiddle;
|
---|
637 |
|
---|
638 | for (;;)
|
---|
639 | {
|
---|
640 | pMiddle = pStart;
|
---|
641 | iMiddle = iStart + (iEnd - iStart) / 2;
|
---|
642 | if (iMiddle == iStart)
|
---|
643 | {
|
---|
644 | break;
|
---|
645 | }
|
---|
646 |
|
---|
647 | /* Find the block with the iMiddle index. Never go further than pEnd. */
|
---|
648 | uint32_t i;
|
---|
649 | for (i = iStart; i < iMiddle && pMiddle != pEnd; ++i)
|
---|
650 | {
|
---|
651 | pMiddle = RTListNodeGetNext(&pMiddle->nodeBlock, HGSMIMABLOCK, nodeBlock);
|
---|
652 | }
|
---|
653 |
|
---|
654 | HGSMIOFFSET offMiddle = HGSMI_MA_DESC_OFFSET(pMiddle->descriptor);
|
---|
655 | if (offMiddle > off)
|
---|
656 | {
|
---|
657 | pEnd = pMiddle;
|
---|
658 | iEnd = iMiddle;
|
---|
659 | }
|
---|
660 | else
|
---|
661 | {
|
---|
662 | pStart = pMiddle;
|
---|
663 | iStart = iMiddle;
|
---|
664 | }
|
---|
665 | }
|
---|
666 |
|
---|
667 | return pMiddle;
|
---|
668 | }
|
---|
669 |
|
---|
670 |
|
---|
671 | /*
|
---|
672 | * Helper.
|
---|
673 | */
|
---|
674 |
|
---|
675 | uint32_t HGSMIPopCnt32(uint32_t u32)
|
---|
676 | {
|
---|
677 | uint32_t c = 0;
|
---|
678 | if (u32 > 0xFFFF) { c += 16; u32 >>= 16; }
|
---|
679 | if (u32 > 0xFF) { c += 8; u32 >>= 8; }
|
---|
680 | if (u32 > 0xF) { c += 4; u32 >>= 4; }
|
---|
681 | if (u32 > 0x3) { c += 2; u32 >>= 2; }
|
---|
682 | if (u32 > 0x1) { c += 1; u32 >>= 1; }
|
---|
683 | return c + u32;
|
---|
684 | }
|
---|