HGSMIMemAlloc.cpp@ 86763

Last change on this file since 86763 was 82968, checked in by vboxsync, 5 years ago
Copyright year updates by scm.
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 82968 2020-02-04 10:35:17Z vboxsync $ */
2	/** @file
3	* VBox Host Guest Shared Memory Interface (HGSMI) - Memory allocator.
4	*/
5
6	/*
7	* Copyright (C) 2014-2020 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
73	DECLINLINE(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
80	static void hgsmiMABlockFree(HGSMIMADATA pMA, HGSMIMABLOCK pBlock)
81	{
82	pMA->env.pfnFree(pMA->env.pvEnv, pBlock);
83	}
84
85	static 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. */
104	static 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
160	static 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
177	static 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
219	static 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
274	static 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
364	static 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
406	static 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
459	static 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
494	static 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
519	int 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
560	void 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
577	HGSMIOFFSET 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
587	static 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
598	void RT_UNTRUSTED_VOLATILE_HSTGST HGSMIMAAlloc(HGSMIMADATA pMA, HGSMISIZE cb)
599	{
600	HGSMIOFFSET off = hgsmiMAAlloc(pMA, cb);
601	return HGSMIMAOffsetToPointer(pMA, off);
602	}
603
604	void 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
617	HGSMIMABLOCK 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
665	uint32_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.

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

Download in other formats: