VBoxGuestR0LibPhysHeap.cpp@ 72352

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

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

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

Download in other formats: