VBoxGuestR0LibPhysHeap.cpp@ 69149

Last change on this file since 69149 was 68654, checked in by vboxsync, 7 years ago
VBoxGuestR0Lib: Function prefix and DECL macro cleanups.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 17.7 KB

Line
1	/* $Id: VBoxGuestR0LibPhysHeap.cpp 68654 2017-09-05 17:22:12Z vboxsync $ */
2	/** @file
3	* VBoxGuestLibR0 - Physical memory heap.
4	*/
5
6	/*
7	* Copyright (C) 2006-2016 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	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*/
26
27	/*********************************************************************************************************************************
28	* Header Files *
29	*********************************************************************************************************************************/
30	#include "VBoxGuestR0LibInternal.h"
31
32	#include <iprt/assert.h>
33	#include <iprt/semaphore.h>
34	#include <iprt/alloc.h>
35
36	/* Physical memory heap consists of double linked list
37	* of chunks. Memory blocks are allocated inside these chunks
38	* and are members of Allocated and Free double linked lists.
39	*
40	* When allocating a block, we search in Free linked
41	* list for a suitable free block. If there is no such block,
42	* a new chunk is allocated and the new block is taken from
43	* the new chunk as the only chunk-sized free block.
44	* Allocated block is excluded from the Free list and goes to
45	* Alloc list.
46	*
47	* When freeing block, we check the pointer and then
48	* exclude block from Alloc list and move it to free list.
49	*
50	* For each chunk we maintain the allocated blocks counter.
51	* if 2 (or more) entire chunks are free they are immediately
52	* deallocated, so we always have at most 1 free chunk.
53	*
54	* When freeing blocks, two subsequent free blocks are always
55	* merged together. Current implementation merges blocks only
56	* when there is a block after the just freed one.
57	*
58	*/
59
60	#define VBGL_PH_ASSERT Assert
61	#define VBGL_PH_ASSERTMsg AssertMsg
62
63	// #define DUMPHEAP
64
65	#ifdef DUMPHEAP
66	# define VBGL_PH_dprintf(a) RTAssertMsg2Weak a
67	#else
68	# define VBGL_PH_dprintf(a)
69	#endif
70
71	/* Heap block signature */
72	#define VBGL_PH_BLOCKSIGNATURE (0xADDBBBBB)
73
74
75	/* Heap chunk signature */
76	#define VBGL_PH_CHUNKSIGNATURE (0xADDCCCCC)
77	/* Heap chunk allocation unit */
78	#define VBGL_PH_CHUNKSIZE (0x10000)
79
80	/* Heap block bit flags */
81	#define VBGL_PH_BF_ALLOCATED (0x1)
82
83	struct _VBGLPHYSHEAPBLOCK
84	{
85	uint32_t u32Signature;
86
87	/* Size of user data in the block. Does not include the block header. */
88	uint32_t cbDataSize;
89
90	uint32_t fu32Flags;
91
92	struct _VBGLPHYSHEAPBLOCK *pNext;
93	struct _VBGLPHYSHEAPBLOCK *pPrev;
94
95	struct _VBGLPHYSHEAPCHUNK *pChunk;
96	};
97
98	struct _VBGLPHYSHEAPCHUNK
99	{
100	uint32_t u32Signature;
101
102	/* Size of the chunk. Includes the chunk header. */
103	uint32_t cbSize;
104
105	/* Physical address of the chunk */
106	uint32_t physAddr;
107
108	/* Number of allocated blocks in the chunk */
109	int32_t cAllocatedBlocks;
110
111	struct _VBGLPHYSHEAPCHUNK *pNext;
112	struct _VBGLPHYSHEAPCHUNK *pPrev;
113	};
114
115
116	#ifndef DUMPHEAP
117	#define dumpheap(a)
118	#else
119	void dumpheap (char *point)
120	{
121	VBGL_PH_dprintf(("VBGL_PH dump at '%s'\n", point));
122
123	VBGL_PH_dprintf(("Chunks:\n"));
124
125	VBGLPHYSHEAPCHUNK *pChunk = g_vbgldata.pChunkHead;
126
127	while (pChunk)
128	{
129	VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, allocated = %8d, phys = %08X\n",
130	pChunk, pChunk->pNext, pChunk->pPrev, pChunk->u32Signature, pChunk->cbSize, pChunk->cAllocatedBlocks, pChunk->physAddr));
131
132	pChunk = pChunk->pNext;
133	}
134
135	VBGL_PH_dprintf(("Allocated blocks:\n"));
136
137	VBGLPHYSHEAPBLOCK *pBlock = g_vbgldata.pAllocBlocksHead;
138
139	while (pBlock)
140	{
141	VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
142	pBlock, pBlock->pNext, pBlock->pPrev, pBlock->u32Signature, pBlock->cbDataSize, pBlock->fu32Flags, pBlock->pChunk));
143
144	pBlock = pBlock->pNext;
145	}
146
147	VBGL_PH_dprintf(("Free blocks:\n"));
148
149	pBlock = g_vbgldata.pFreeBlocksHead;
150
151	while (pBlock)
152	{
153	VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
154	pBlock, pBlock->pNext, pBlock->pPrev, pBlock->u32Signature, pBlock->cbDataSize, pBlock->fu32Flags, pBlock->pChunk));
155
156	pBlock = pBlock->pNext;
157	}
158
159	VBGL_PH_dprintf(("VBGL_PH dump at '%s' done\n", point));
160	}
161	#endif
162
163
164	DECLINLINE(void ) vbglPhysHeapBlock2Data (VBGLPHYSHEAPBLOCK pBlock)
165	{
166	return (void )(pBlock? (char )pBlock + sizeof (VBGLPHYSHEAPBLOCK): NULL);
167	}
168
169	DECLINLINE(VBGLPHYSHEAPBLOCK ) vbglPhysHeapData2Block (void p)
170	{
171	VBGLPHYSHEAPBLOCK pBlock = (VBGLPHYSHEAPBLOCK )(p? (char *)p - sizeof (VBGLPHYSHEAPBLOCK): NULL);
172
173	VBGL_PH_ASSERTMsg(pBlock == NULL \|\| pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE,
174	("pBlock->u32Signature = %08X\n", pBlock->u32Signature));
175
176	return pBlock;
177	}
178
179	DECLINLINE(int) vbglPhysHeapEnter (void)
180	{
181	int rc = RTSemFastMutexRequest(g_vbgldata.mutexHeap);
182
183	VBGL_PH_ASSERTMsg(RT_SUCCESS(rc),
184	("Failed to request heap mutex, rc = %Rrc\n", rc));
185
186	return rc;
187	}
188
189	DECLINLINE(void) vbglPhysHeapLeave (void)
190	{
191	RTSemFastMutexRelease(g_vbgldata.mutexHeap);
192	}
193
194
195	static void vbglPhysHeapInitBlock (VBGLPHYSHEAPBLOCK pBlock, VBGLPHYSHEAPCHUNK pChunk, uint32_t cbDataSize)
196	{
197	VBGL_PH_ASSERT(pBlock != NULL);
198	VBGL_PH_ASSERT(pChunk != NULL);
199
200	pBlock->u32Signature = VBGL_PH_BLOCKSIGNATURE;
201	pBlock->cbDataSize = cbDataSize;
202	pBlock->fu32Flags = 0;
203	pBlock->pNext = NULL;
204	pBlock->pPrev = NULL;
205	pBlock->pChunk = pChunk;
206	}
207
208
209	static void vbglPhysHeapInsertBlock (VBGLPHYSHEAPBLOCK pInsertAfter, VBGLPHYSHEAPBLOCK pBlock)
210	{
211	VBGL_PH_ASSERTMsg(pBlock->pNext == NULL,
212	("pBlock->pNext = %p\n", pBlock->pNext));
213	VBGL_PH_ASSERTMsg(pBlock->pPrev == NULL,
214	("pBlock->pPrev = %p\n", pBlock->pPrev));
215
216	if (pInsertAfter)
217	{
218	pBlock->pNext = pInsertAfter->pNext;
219	pBlock->pPrev = pInsertAfter;
220
221	if (pInsertAfter->pNext)
222	{
223	pInsertAfter->pNext->pPrev = pBlock;
224	}
225
226	pInsertAfter->pNext = pBlock;
227	}
228	else
229	{
230	/* inserting to head of list */
231	pBlock->pPrev = NULL;
232
233	if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
234	{
235	pBlock->pNext = g_vbgldata.pAllocBlocksHead;
236
237	if (g_vbgldata.pAllocBlocksHead)
238	{
239	g_vbgldata.pAllocBlocksHead->pPrev = pBlock;
240	}
241
242	g_vbgldata.pAllocBlocksHead = pBlock;
243	}
244	else
245	{
246	pBlock->pNext = g_vbgldata.pFreeBlocksHead;
247
248	if (g_vbgldata.pFreeBlocksHead)
249	{
250	g_vbgldata.pFreeBlocksHead->pPrev = pBlock;
251	}
252
253	g_vbgldata.pFreeBlocksHead = pBlock;
254	}
255	}
256	}
257
258	static void vbglPhysHeapExcludeBlock (VBGLPHYSHEAPBLOCK *pBlock)
259	{
260	if (pBlock->pNext)
261	{
262	pBlock->pNext->pPrev = pBlock->pPrev;
263	}
264	else
265	{
266	/* this is tail of list but we do not maintain tails of block lists.
267	* so do nothing.
268	*/
269	;
270	}
271
272	if (pBlock->pPrev)
273	{
274	pBlock->pPrev->pNext = pBlock->pNext;
275	}
276	else
277	{
278	/* this is head of list but we do not maintain tails of block lists. */
279	if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
280	{
281	g_vbgldata.pAllocBlocksHead = pBlock->pNext;
282	}
283	else
284	{
285	g_vbgldata.pFreeBlocksHead = pBlock->pNext;
286	}
287	}
288
289	pBlock->pNext = NULL;
290	pBlock->pPrev = NULL;
291	}
292
293	static VBGLPHYSHEAPBLOCK *vbglPhysHeapChunkAlloc (uint32_t cbSize)
294	{
295	RTCCPHYS physAddr;
296	VBGLPHYSHEAPCHUNK *pChunk;
297	VBGLPHYSHEAPBLOCK *pBlock;
298	VBGL_PH_dprintf(("Allocating new chunk of size %d\n", cbSize));
299
300	/* Compute chunk size to allocate */
301	if (cbSize < VBGL_PH_CHUNKSIZE)
302	{
303	/* Includes case of block size 0 during initialization */
304	cbSize = VBGL_PH_CHUNKSIZE;
305	}
306	else
307	{
308	/* Round up to next chunk size, which must be power of 2 */
309	cbSize = (cbSize + (VBGL_PH_CHUNKSIZE - 1)) & ~(VBGL_PH_CHUNKSIZE - 1);
310	}
311
312	physAddr = 0;
313	/* This function allocates physical contiguous memory (below 4GB) according to the IPRT docs.
314	* Address < 4G is required for the port IO.
315	*/
316	pChunk = (VBGLPHYSHEAPCHUNK *)RTMemContAlloc (&physAddr, cbSize);
317
318	if (!pChunk)
319	{
320	LogRel(("vbglPhysHeapChunkAlloc: failed to alloc %u contiguous bytes.\n", cbSize));
321	return NULL;
322	}
323
324	AssertRelease(physAddr < _4G && physAddr + cbSize <= _4G);
325
326	pChunk->u32Signature = VBGL_PH_CHUNKSIGNATURE;
327	pChunk->cbSize = cbSize;
328	pChunk->physAddr = (uint32_t)physAddr;
329	pChunk->cAllocatedBlocks = 0;
330	pChunk->pNext = g_vbgldata.pChunkHead;
331	pChunk->pPrev = NULL;
332
333	/* Initialize the free block, which now occupies entire chunk. */
334	pBlock = (VBGLPHYSHEAPBLOCK )((char )pChunk + sizeof (VBGLPHYSHEAPCHUNK));
335
336	vbglPhysHeapInitBlock (pBlock, pChunk, cbSize - sizeof (VBGLPHYSHEAPCHUNK) - sizeof (VBGLPHYSHEAPBLOCK));
337
338	vbglPhysHeapInsertBlock (NULL, pBlock);
339
340	g_vbgldata.pChunkHead = pChunk;
341
342	VBGL_PH_dprintf(("Allocated chunk %p, block = %p size=%x\n", pChunk, pBlock, cbSize));
343
344	return pBlock;
345	}
346
347
348	void vbglPhysHeapChunkDelete (VBGLPHYSHEAPCHUNK *pChunk)
349	{
350	char *p;
351	VBGL_PH_ASSERT(pChunk != NULL);
352	VBGL_PH_ASSERTMsg(pChunk->u32Signature == VBGL_PH_CHUNKSIGNATURE,
353	("pChunk->u32Signature = %08X\n", pChunk->u32Signature));
354
355	VBGL_PH_dprintf(("Deleting chunk %p size %x\n", pChunk, pChunk->cbSize));
356
357	/* first scan the chunk and exclude all blocks from lists */
358
359	p = (char *)pChunk + sizeof (VBGLPHYSHEAPCHUNK);
360
361	while (p < (char *)pChunk + pChunk->cbSize)
362	{
363	VBGLPHYSHEAPBLOCK pBlock = (VBGLPHYSHEAPBLOCK )p;
364
365	p += pBlock->cbDataSize + sizeof (VBGLPHYSHEAPBLOCK);
366
367	vbglPhysHeapExcludeBlock (pBlock);
368	}
369
370	VBGL_PH_ASSERTMsg(p == (char *)pChunk + pChunk->cbSize,
371	("p = %p, (char *)pChunk + pChunk->cbSize = %p, pChunk->cbSize = %08X\n",
372	p, (char *)pChunk + pChunk->cbSize, pChunk->cbSize));
373
374	/* Exclude chunk from the chunk list */
375	if (pChunk->pNext)
376	{
377	pChunk->pNext->pPrev = pChunk->pPrev;
378	}
379	else
380	{
381	/* we do not maintain tail */
382	;
383	}
384
385	if (pChunk->pPrev)
386	{
387	pChunk->pPrev->pNext = pChunk->pNext;
388	}
389	else
390	{
391	/* the chunk was head */
392	g_vbgldata.pChunkHead = pChunk->pNext;
393	}
394
395	RTMemContFree (pChunk, pChunk->cbSize);
396	}
397
398
399	DECLR0VBGL(void *) VbglR0PhysHeapAlloc (uint32_t cbSize)
400	{
401	VBGLPHYSHEAPBLOCK pBlock, iter;
402	int rc = vbglPhysHeapEnter ();
403
404	if (RT_FAILURE(rc))
405	return NULL;
406
407	dumpheap ("pre alloc");
408
409	pBlock = NULL;
410
411	/* If there are free blocks in the heap, look at them. */
412	iter = g_vbgldata.pFreeBlocksHead;
413
414	/* There will be not many blocks in the heap, so
415	* linear search would be fast enough.
416	*/
417
418	while (iter)
419	{
420	if (iter->cbDataSize == cbSize)
421	{
422	/* exact match */
423	pBlock = iter;
424	break;
425	}
426
427	/* Looking for a free block with nearest size */
428	if (iter->cbDataSize > cbSize)
429	{
430	if (pBlock)
431	{
432	if (iter->cbDataSize < pBlock->cbDataSize)
433	{
434	pBlock = iter;
435	}
436	}
437	else
438	{
439	pBlock = iter;
440	}
441	}
442
443	iter = iter->pNext;
444	}
445
446	if (!pBlock)
447	{
448	/* No free blocks, allocate a new chunk,
449	* the only free block of the chunk will
450	* be returned.
451	*/
452	pBlock = vbglPhysHeapChunkAlloc (cbSize);
453	}
454
455	if (pBlock)
456	{
457	VBGL_PH_ASSERTMsg(pBlock->u32Signature == VBGL_PH_BLOCKSIGNATURE,
458	("pBlock = %p, pBlock->u32Signature = %08X\n", pBlock, pBlock->u32Signature));
459	VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) == 0,
460	("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
461
462	/* We have a free block, either found or allocated. */
463
464	if (pBlock->cbDataSize > 2*(cbSize + sizeof (VBGLPHYSHEAPBLOCK)))
465	{
466	/* Data will occupy less than a half of the block,
467	* the block should be split.
468	*/
469	iter = (VBGLPHYSHEAPBLOCK )((char )pBlock + sizeof (VBGLPHYSHEAPBLOCK) + cbSize);
470
471	/* Init the new 'iter' block, initialized blocks are always marked as free. */
472	vbglPhysHeapInitBlock (iter, pBlock->pChunk, pBlock->cbDataSize - cbSize - sizeof (VBGLPHYSHEAPBLOCK));
473
474	pBlock->cbDataSize = cbSize;
475
476	/* Insert the new 'iter' block after the 'pBlock' in the free list */
477	vbglPhysHeapInsertBlock (pBlock, iter);
478	}
479
480	/* Exclude pBlock from free list */
481	vbglPhysHeapExcludeBlock (pBlock);
482
483	/* Mark as allocated */
484	pBlock->fu32Flags \|= VBGL_PH_BF_ALLOCATED;
485
486	/* Insert to allocated list */
487	vbglPhysHeapInsertBlock (NULL, pBlock);
488
489	/* Adjust the chunk allocated blocks counter */
490	pBlock->pChunk->cAllocatedBlocks++;
491	}
492
493	dumpheap ("post alloc");
494
495	vbglPhysHeapLeave ();
496	VBGL_PH_dprintf(("VbglR0PhysHeapAlloc %x size %x\n", vbglPhysHeapBlock2Data (pBlock), pBlock->cbDataSize));
497
498	return vbglPhysHeapBlock2Data (pBlock);
499	}
500
501	DECLR0VBGL(uint32_t) VbglR0PhysHeapGetPhysAddr (void *p)
502	{
503	uint32_t physAddr = 0;
504	VBGLPHYSHEAPBLOCK *pBlock = vbglPhysHeapData2Block (p);
505
506	if (pBlock)
507	{
508	VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) != 0,
509	("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
510
511	if (pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED)
512	physAddr = pBlock->pChunk->physAddr + (uint32_t)((uintptr_t)p - (uintptr_t)pBlock->pChunk);
513	}
514
515	return physAddr;
516	}
517
518	DECLR0VBGL(void) VbglR0PhysHeapFree(void *p)
519	{
520	VBGLPHYSHEAPBLOCK *pBlock;
521	VBGLPHYSHEAPBLOCK *pNeighbour;
522
523	int rc = vbglPhysHeapEnter ();
524	if (RT_FAILURE(rc))
525	return;
526
527	dumpheap ("pre free");
528
529	pBlock = vbglPhysHeapData2Block (p);
530
531	if (!pBlock)
532	{
533	vbglPhysHeapLeave ();
534	return;
535	}
536
537	VBGL_PH_ASSERTMsg((pBlock->fu32Flags & VBGL_PH_BF_ALLOCATED) != 0,
538	("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock, pBlock->fu32Flags));
539
540	/* Exclude from allocated list */
541	vbglPhysHeapExcludeBlock (pBlock);
542
543	dumpheap ("post exclude");
544
545	VBGL_PH_dprintf(("VbglR0PhysHeapFree %x size %x\n", p, pBlock->cbDataSize));
546
547	/* Mark as free */
548	pBlock->fu32Flags &= ~VBGL_PH_BF_ALLOCATED;
549
550	/* Insert to free list */
551	vbglPhysHeapInsertBlock (NULL, pBlock);
552
553	dumpheap ("post insert");
554
555	/* Adjust the chunk allocated blocks counter */
556	pBlock->pChunk->cAllocatedBlocks--;
557
558	VBGL_PH_ASSERT(pBlock->pChunk->cAllocatedBlocks >= 0);
559
560	/* Check if we can merge 2 free blocks. To simplify heap maintenance,
561	* we will look at block after the just freed one.
562	* This will not prevent us from detecting free memory chunks.
563	* Also in most cases blocks are deallocated in reverse allocation order
564	* and in that case the merging will work.
565	*/
566
567	pNeighbour = (VBGLPHYSHEAPBLOCK )((char )p + pBlock->cbDataSize);
568
569	if ((char )pNeighbour < (char )pBlock->pChunk + pBlock->pChunk->cbSize
570	&& (pNeighbour->fu32Flags & VBGL_PH_BF_ALLOCATED) == 0)
571	{
572	/* The next block is free as well. */
573
574	/* Adjust size of current memory block */
575	pBlock->cbDataSize += pNeighbour->cbDataSize + sizeof (VBGLPHYSHEAPBLOCK);
576
577	/* Exclude the next neighbour */
578	vbglPhysHeapExcludeBlock (pNeighbour);
579	}
580
581	dumpheap ("post merge");
582
583	/* now check if there are 2 or more free chunks */
584	if (pBlock->pChunk->cAllocatedBlocks == 0)
585	{
586	VBGLPHYSHEAPCHUNK *pChunk = g_vbgldata.pChunkHead;
587
588	uint32_t u32FreeChunks = 0;
589
590	while (pChunk)
591	{
592	if (pChunk->cAllocatedBlocks == 0)
593	{
594	u32FreeChunks++;
595	}
596
597	pChunk = pChunk->pNext;
598	}
599
600	if (u32FreeChunks > 1)
601	{
602	/* Delete current chunk, it will also exclude all free blocks
603	* remaining in the chunk from the free list, so the pBlock
604	* will also be invalid after this.
605	*/
606	vbglPhysHeapChunkDelete (pBlock->pChunk);
607	}
608	}
609
610	dumpheap ("post free");
611
612	vbglPhysHeapLeave ();
613	}
614
615	DECLR0VBGL(int) VbglR0PhysHeapInit (void)
616	{
617	int rc = VINF_SUCCESS;
618
619	/* Allocate the first chunk of the heap. */
620	VBGLPHYSHEAPBLOCK *pBlock = vbglPhysHeapChunkAlloc (0);
621
622	if (!pBlock)
623	rc = VERR_NO_MEMORY;
624
625	RTSemFastMutexCreate(&g_vbgldata.mutexHeap);
626
627	return rc;
628	}
629
630	DECLR0VBGL(void) VbglR0PhysHeapTerminate (void)
631	{
632	while (g_vbgldata.pChunkHead)
633	{
634	vbglPhysHeapChunkDelete (g_vbgldata.pChunkHead);
635	}
636
637	RTSemFastMutexDestroy(g_vbgldata.mutexHeap);
638	}
639

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

source: vbox/trunk/src/VBox/Additions/common/VBoxGuest/lib/VBoxGuestR0LibPhysHeap.cpp@ 69149

Download in other formats: