HGSMIMemAlloc.cpp@ 106061

Last change on this file since 106061 was 106061, checked in by vboxsync, 2 months ago
Copyright year updates by scm.
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 106061 2024-09-16 14:03:52Z vboxsync $ */
2	/** @file
3	* VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
4	*/
5
6	/*
7	* Copyright (C) 2014-2024 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	static 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	}

Note: See TracBrowser for help on using the repository browser.

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

Download in other formats: