VirtualBox

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

Last change on this file since 82781 was 76553, checked in by vboxsync, 5 years ago

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

© 2023 Oracle
Contact – Privacy policy – Terms of Use