VirtualBox

source: vbox/trunk/src/VBox/GuestHost/HGSMI/HGSMIMemAlloc.cpp

Last change on this file was 103457, checked in by vboxsync, 3 months ago

HGSMI: Some symbol visibility cleanup, bugref:3409
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.0 KB
Line 
1/* $Id: HGSMIMemAlloc.cpp 103457 2024-02-19 15:51:24Z 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
83DECLINLINE(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
90static void hgsmiMABlockFree(HGSMIMADATA *pMA, HGSMIMABLOCK *pBlock)
91{
92 pMA->env.pfnFree(pMA->env.pvEnv, pBlock);
93}
94
95static 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. */
114static 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
170static 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
187static 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
229static 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
284static 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
374static 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
416static 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
469static 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
504static 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
529int 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
570void 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
587static 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
597static 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
608void RT_UNTRUSTED_VOLATILE_HSTGST *HGSMIMAAlloc(HGSMIMADATA *pMA, HGSMISIZE cb)
609{
610 HGSMIOFFSET off = hgsmiMAAlloc(pMA, cb);
611 return HGSMIMAOffsetToPointer(pMA, off);
612}
613
614void 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
627HGSMIMABLOCK *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
675uint32_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}
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use