]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - ubuntu/vbox/vboxguest/PhysHeap.c
1 /* $Id: PhysHeap.cpp $ */
3 * VBoxGuestLibR0 - Physical memory heap.
7 * Copyright (C) 2006-2016 Oracle Corporation
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.
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.
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.
27 #include "VBGLInternal.h"
29 #include <iprt/assert.h>
30 #include <iprt/semaphore.h>
31 #include <iprt/alloc.h>
33 /* Physical memory heap consists of double linked list
34 * of chunks. Memory blocks are allocated inside these chunks
35 * and are members of Allocated and Free double linked lists.
37 * When allocating a block, we search in Free linked
38 * list for a suitable free block. If there is no such block,
39 * a new chunk is allocated and the new block is taken from
40 * the new chunk as the only chunk-sized free block.
41 * Allocated block is excluded from the Free list and goes to
44 * When freeing block, we check the pointer and then
45 * exclude block from Alloc list and move it to free list.
47 * For each chunk we maintain the allocated blocks counter.
48 * if 2 (or more) entire chunks are free they are immediately
49 * deallocated, so we always have at most 1 free chunk.
51 * When freeing blocks, two subsequent free blocks are always
52 * merged together. Current implementation merges blocks only
53 * when there is a block after the just freed one.
57 #define VBGL_PH_ASSERT Assert
58 #define VBGL_PH_ASSERTMsg AssertMsg
63 # define VBGL_PH_dprintf(a) RTAssertMsg2Weak a
65 # define VBGL_PH_dprintf(a)
68 /* Heap block signature */
69 #define VBGL_PH_BLOCKSIGNATURE (0xADDBBBBB)
72 /* Heap chunk signature */
73 #define VBGL_PH_CHUNKSIGNATURE (0xADDCCCCC)
74 /* Heap chunk allocation unit */
75 #define VBGL_PH_CHUNKSIZE (0x10000)
77 /* Heap block bit flags */
78 #define VBGL_PH_BF_ALLOCATED (0x1)
80 struct _VBGLPHYSHEAPBLOCK
82 uint32_t u32Signature
;
84 /* Size of user data in the block. Does not include the block header. */
89 struct _VBGLPHYSHEAPBLOCK
*pNext
;
90 struct _VBGLPHYSHEAPBLOCK
*pPrev
;
92 struct _VBGLPHYSHEAPCHUNK
*pChunk
;
95 struct _VBGLPHYSHEAPCHUNK
97 uint32_t u32Signature
;
99 /* Size of the chunk. Includes the chunk header. */
102 /* Physical address of the chunk */
105 /* Number of allocated blocks in the chunk */
106 int32_t cAllocatedBlocks
;
108 struct _VBGLPHYSHEAPCHUNK
*pNext
;
109 struct _VBGLPHYSHEAPCHUNK
*pPrev
;
116 void dumpheap (char *point
)
118 VBGL_PH_dprintf(("VBGL_PH dump at '%s'\n", point
));
120 VBGL_PH_dprintf(("Chunks:\n"));
122 VBGLPHYSHEAPCHUNK
*pChunk
= g_vbgldata
.pChunkHead
;
126 VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, allocated = %8d, phys = %08X\n",
127 pChunk
, pChunk
->pNext
, pChunk
->pPrev
, pChunk
->u32Signature
, pChunk
->cbSize
, pChunk
->cAllocatedBlocks
, pChunk
->physAddr
));
129 pChunk
= pChunk
->pNext
;
132 VBGL_PH_dprintf(("Allocated blocks:\n"));
134 VBGLPHYSHEAPBLOCK
*pBlock
= g_vbgldata
.pAllocBlocksHead
;
138 VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
139 pBlock
, pBlock
->pNext
, pBlock
->pPrev
, pBlock
->u32Signature
, pBlock
->cbDataSize
, pBlock
->fu32Flags
, pBlock
->pChunk
));
141 pBlock
= pBlock
->pNext
;
144 VBGL_PH_dprintf(("Free blocks:\n"));
146 pBlock
= g_vbgldata
.pFreeBlocksHead
;
150 VBGL_PH_dprintf(("%p: pNext = %p, pPrev = %p, sign = %08X, size = %8d, flags = %08X, pChunk = %p\n",
151 pBlock
, pBlock
->pNext
, pBlock
->pPrev
, pBlock
->u32Signature
, pBlock
->cbDataSize
, pBlock
->fu32Flags
, pBlock
->pChunk
));
153 pBlock
= pBlock
->pNext
;
156 VBGL_PH_dprintf(("VBGL_PH dump at '%s' done\n", point
));
161 DECLINLINE(void *) vbglPhysHeapBlock2Data (VBGLPHYSHEAPBLOCK
*pBlock
)
163 return (void *)(pBlock
? (char *)pBlock
+ sizeof (VBGLPHYSHEAPBLOCK
): NULL
);
166 DECLINLINE(VBGLPHYSHEAPBLOCK
*) vbglPhysHeapData2Block (void *p
)
168 VBGLPHYSHEAPBLOCK
*pBlock
= (VBGLPHYSHEAPBLOCK
*)(p
? (char *)p
- sizeof (VBGLPHYSHEAPBLOCK
): NULL
);
170 VBGL_PH_ASSERTMsg(pBlock
== NULL
|| pBlock
->u32Signature
== VBGL_PH_BLOCKSIGNATURE
,
171 ("pBlock->u32Signature = %08X\n", pBlock
->u32Signature
));
176 DECLINLINE(int) vbglPhysHeapEnter (void)
178 int rc
= RTSemFastMutexRequest(g_vbgldata
.mutexHeap
);
180 VBGL_PH_ASSERTMsg(RT_SUCCESS(rc
),
181 ("Failed to request heap mutex, rc = %Rrc\n", rc
));
186 DECLINLINE(void) vbglPhysHeapLeave (void)
188 RTSemFastMutexRelease(g_vbgldata
.mutexHeap
);
192 static void vbglPhysHeapInitBlock (VBGLPHYSHEAPBLOCK
*pBlock
, VBGLPHYSHEAPCHUNK
*pChunk
, uint32_t cbDataSize
)
194 VBGL_PH_ASSERT(pBlock
!= NULL
);
195 VBGL_PH_ASSERT(pChunk
!= NULL
);
197 pBlock
->u32Signature
= VBGL_PH_BLOCKSIGNATURE
;
198 pBlock
->cbDataSize
= cbDataSize
;
199 pBlock
->fu32Flags
= 0;
200 pBlock
->pNext
= NULL
;
201 pBlock
->pPrev
= NULL
;
202 pBlock
->pChunk
= pChunk
;
206 static void vbglPhysHeapInsertBlock (VBGLPHYSHEAPBLOCK
*pInsertAfter
, VBGLPHYSHEAPBLOCK
*pBlock
)
208 VBGL_PH_ASSERTMsg(pBlock
->pNext
== NULL
,
209 ("pBlock->pNext = %p\n", pBlock
->pNext
));
210 VBGL_PH_ASSERTMsg(pBlock
->pPrev
== NULL
,
211 ("pBlock->pPrev = %p\n", pBlock
->pPrev
));
215 pBlock
->pNext
= pInsertAfter
->pNext
;
216 pBlock
->pPrev
= pInsertAfter
;
218 if (pInsertAfter
->pNext
)
220 pInsertAfter
->pNext
->pPrev
= pBlock
;
223 pInsertAfter
->pNext
= pBlock
;
227 /* inserting to head of list */
228 pBlock
->pPrev
= NULL
;
230 if (pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
)
232 pBlock
->pNext
= g_vbgldata
.pAllocBlocksHead
;
234 if (g_vbgldata
.pAllocBlocksHead
)
236 g_vbgldata
.pAllocBlocksHead
->pPrev
= pBlock
;
239 g_vbgldata
.pAllocBlocksHead
= pBlock
;
243 pBlock
->pNext
= g_vbgldata
.pFreeBlocksHead
;
245 if (g_vbgldata
.pFreeBlocksHead
)
247 g_vbgldata
.pFreeBlocksHead
->pPrev
= pBlock
;
250 g_vbgldata
.pFreeBlocksHead
= pBlock
;
255 static void vbglPhysHeapExcludeBlock (VBGLPHYSHEAPBLOCK
*pBlock
)
259 pBlock
->pNext
->pPrev
= pBlock
->pPrev
;
263 /* this is tail of list but we do not maintain tails of block lists.
271 pBlock
->pPrev
->pNext
= pBlock
->pNext
;
275 /* this is head of list but we do not maintain tails of block lists. */
276 if (pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
)
278 g_vbgldata
.pAllocBlocksHead
= pBlock
->pNext
;
282 g_vbgldata
.pFreeBlocksHead
= pBlock
->pNext
;
286 pBlock
->pNext
= NULL
;
287 pBlock
->pPrev
= NULL
;
290 static VBGLPHYSHEAPBLOCK
*vbglPhysHeapChunkAlloc (uint32_t cbSize
)
293 VBGLPHYSHEAPCHUNK
*pChunk
;
294 VBGLPHYSHEAPBLOCK
*pBlock
;
295 VBGL_PH_dprintf(("Allocating new chunk of size %d\n", cbSize
));
297 /* Compute chunk size to allocate */
298 if (cbSize
< VBGL_PH_CHUNKSIZE
)
300 /* Includes case of block size 0 during initialization */
301 cbSize
= VBGL_PH_CHUNKSIZE
;
305 /* Round up to next chunk size, which must be power of 2 */
306 cbSize
= (cbSize
+ (VBGL_PH_CHUNKSIZE
- 1)) & ~(VBGL_PH_CHUNKSIZE
- 1);
310 /* This function allocates physical contiguous memory (below 4GB) according to the IPRT docs.
311 * Address < 4G is required for the port IO.
313 pChunk
= (VBGLPHYSHEAPCHUNK
*)RTMemContAlloc (&physAddr
, cbSize
);
317 LogRel(("vbglPhysHeapChunkAlloc: failed to alloc %u contiguous bytes.\n", cbSize
));
321 AssertRelease(physAddr
< _4G
&& physAddr
+ cbSize
<= _4G
);
323 pChunk
->u32Signature
= VBGL_PH_CHUNKSIGNATURE
;
324 pChunk
->cbSize
= cbSize
;
325 pChunk
->physAddr
= (uint32_t)physAddr
;
326 pChunk
->cAllocatedBlocks
= 0;
327 pChunk
->pNext
= g_vbgldata
.pChunkHead
;
328 pChunk
->pPrev
= NULL
;
330 /* Initialize the free block, which now occupies entire chunk. */
331 pBlock
= (VBGLPHYSHEAPBLOCK
*)((char *)pChunk
+ sizeof (VBGLPHYSHEAPCHUNK
));
333 vbglPhysHeapInitBlock (pBlock
, pChunk
, cbSize
- sizeof (VBGLPHYSHEAPCHUNK
) - sizeof (VBGLPHYSHEAPBLOCK
));
335 vbglPhysHeapInsertBlock (NULL
, pBlock
);
337 g_vbgldata
.pChunkHead
= pChunk
;
339 VBGL_PH_dprintf(("Allocated chunk %p, block = %p size=%x\n", pChunk
, pBlock
, cbSize
));
345 void vbglPhysHeapChunkDelete (VBGLPHYSHEAPCHUNK
*pChunk
)
348 VBGL_PH_ASSERT(pChunk
!= NULL
);
349 VBGL_PH_ASSERTMsg(pChunk
->u32Signature
== VBGL_PH_CHUNKSIGNATURE
,
350 ("pChunk->u32Signature = %08X\n", pChunk
->u32Signature
));
352 VBGL_PH_dprintf(("Deleting chunk %p size %x\n", pChunk
, pChunk
->cbSize
));
354 /* first scan the chunk and exclude all blocks from lists */
356 p
= (char *)pChunk
+ sizeof (VBGLPHYSHEAPCHUNK
);
358 while (p
< (char *)pChunk
+ pChunk
->cbSize
)
360 VBGLPHYSHEAPBLOCK
*pBlock
= (VBGLPHYSHEAPBLOCK
*)p
;
362 p
+= pBlock
->cbDataSize
+ sizeof (VBGLPHYSHEAPBLOCK
);
364 vbglPhysHeapExcludeBlock (pBlock
);
367 VBGL_PH_ASSERTMsg(p
== (char *)pChunk
+ pChunk
->cbSize
,
368 ("p = %p, (char *)pChunk + pChunk->cbSize = %p, pChunk->cbSize = %08X\n",
369 p
, (char *)pChunk
+ pChunk
->cbSize
, pChunk
->cbSize
));
371 /* Exclude chunk from the chunk list */
374 pChunk
->pNext
->pPrev
= pChunk
->pPrev
;
378 /* we do not maintain tail */
384 pChunk
->pPrev
->pNext
= pChunk
->pNext
;
388 /* the chunk was head */
389 g_vbgldata
.pChunkHead
= pChunk
->pNext
;
392 RTMemContFree (pChunk
, pChunk
->cbSize
);
396 DECLVBGL(void *) VbglPhysHeapAlloc (uint32_t cbSize
)
398 VBGLPHYSHEAPBLOCK
*pBlock
, *iter
;
399 int rc
= vbglPhysHeapEnter ();
404 dumpheap ("pre alloc");
408 /* If there are free blocks in the heap, look at them. */
409 iter
= g_vbgldata
.pFreeBlocksHead
;
411 /* There will be not many blocks in the heap, so
412 * linear search would be fast enough.
417 if (iter
->cbDataSize
== cbSize
)
424 /* Looking for a free block with nearest size */
425 if (iter
->cbDataSize
> cbSize
)
429 if (iter
->cbDataSize
< pBlock
->cbDataSize
)
445 /* No free blocks, allocate a new chunk,
446 * the only free block of the chunk will
449 pBlock
= vbglPhysHeapChunkAlloc (cbSize
);
454 VBGL_PH_ASSERTMsg(pBlock
->u32Signature
== VBGL_PH_BLOCKSIGNATURE
,
455 ("pBlock = %p, pBlock->u32Signature = %08X\n", pBlock
, pBlock
->u32Signature
));
456 VBGL_PH_ASSERTMsg((pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
) == 0,
457 ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock
, pBlock
->fu32Flags
));
459 /* We have a free block, either found or allocated. */
461 if (pBlock
->cbDataSize
> 2*(cbSize
+ sizeof (VBGLPHYSHEAPBLOCK
)))
463 /* Data will occupy less than a half of the block,
464 * the block should be split.
466 iter
= (VBGLPHYSHEAPBLOCK
*)((char *)pBlock
+ sizeof (VBGLPHYSHEAPBLOCK
) + cbSize
);
468 /* Init the new 'iter' block, initialized blocks are always marked as free. */
469 vbglPhysHeapInitBlock (iter
, pBlock
->pChunk
, pBlock
->cbDataSize
- cbSize
- sizeof (VBGLPHYSHEAPBLOCK
));
471 pBlock
->cbDataSize
= cbSize
;
473 /* Insert the new 'iter' block after the 'pBlock' in the free list */
474 vbglPhysHeapInsertBlock (pBlock
, iter
);
477 /* Exclude pBlock from free list */
478 vbglPhysHeapExcludeBlock (pBlock
);
480 /* Mark as allocated */
481 pBlock
->fu32Flags
|= VBGL_PH_BF_ALLOCATED
;
483 /* Insert to allocated list */
484 vbglPhysHeapInsertBlock (NULL
, pBlock
);
486 /* Adjust the chunk allocated blocks counter */
487 pBlock
->pChunk
->cAllocatedBlocks
++;
490 dumpheap ("post alloc");
492 vbglPhysHeapLeave ();
493 VBGL_PH_dprintf(("VbglPhysHeapAlloc %x size %x\n", vbglPhysHeapBlock2Data (pBlock
), pBlock
->cbDataSize
));
495 return vbglPhysHeapBlock2Data (pBlock
);
498 DECLVBGL(uint32_t) VbglPhysHeapGetPhysAddr (void *p
)
500 uint32_t physAddr
= 0;
501 VBGLPHYSHEAPBLOCK
*pBlock
= vbglPhysHeapData2Block (p
);
505 VBGL_PH_ASSERTMsg((pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
) != 0,
506 ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock
, pBlock
->fu32Flags
));
508 if (pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
)
509 physAddr
= pBlock
->pChunk
->physAddr
+ (uint32_t)((uintptr_t)p
- (uintptr_t)pBlock
->pChunk
);
515 DECLVBGL(void) VbglPhysHeapFree(void *p
)
517 VBGLPHYSHEAPBLOCK
*pBlock
;
518 VBGLPHYSHEAPBLOCK
*pNeighbour
;
520 int rc
= vbglPhysHeapEnter ();
524 dumpheap ("pre free");
526 pBlock
= vbglPhysHeapData2Block (p
);
530 vbglPhysHeapLeave ();
534 VBGL_PH_ASSERTMsg((pBlock
->fu32Flags
& VBGL_PH_BF_ALLOCATED
) != 0,
535 ("pBlock = %p, pBlock->fu32Flags = %08X\n", pBlock
, pBlock
->fu32Flags
));
537 /* Exclude from allocated list */
538 vbglPhysHeapExcludeBlock (pBlock
);
540 dumpheap ("post exclude");
542 VBGL_PH_dprintf(("VbglPhysHeapFree %x size %x\n", p
, pBlock
->cbDataSize
));
545 pBlock
->fu32Flags
&= ~VBGL_PH_BF_ALLOCATED
;
547 /* Insert to free list */
548 vbglPhysHeapInsertBlock (NULL
, pBlock
);
550 dumpheap ("post insert");
552 /* Adjust the chunk allocated blocks counter */
553 pBlock
->pChunk
->cAllocatedBlocks
--;
555 VBGL_PH_ASSERT(pBlock
->pChunk
->cAllocatedBlocks
>= 0);
557 /* Check if we can merge 2 free blocks. To simplify heap maintenance,
558 * we will look at block after the just freed one.
559 * This will not prevent us from detecting free memory chunks.
560 * Also in most cases blocks are deallocated in reverse allocation order
561 * and in that case the merging will work.
564 pNeighbour
= (VBGLPHYSHEAPBLOCK
*)((char *)p
+ pBlock
->cbDataSize
);
566 if ((char *)pNeighbour
< (char *)pBlock
->pChunk
+ pBlock
->pChunk
->cbSize
567 && (pNeighbour
->fu32Flags
& VBGL_PH_BF_ALLOCATED
) == 0)
569 /* The next block is free as well. */
571 /* Adjust size of current memory block */
572 pBlock
->cbDataSize
+= pNeighbour
->cbDataSize
+ sizeof (VBGLPHYSHEAPBLOCK
);
574 /* Exclude the next neighbour */
575 vbglPhysHeapExcludeBlock (pNeighbour
);
578 dumpheap ("post merge");
580 /* now check if there are 2 or more free chunks */
581 if (pBlock
->pChunk
->cAllocatedBlocks
== 0)
583 VBGLPHYSHEAPCHUNK
*pChunk
= g_vbgldata
.pChunkHead
;
585 uint32_t u32FreeChunks
= 0;
589 if (pChunk
->cAllocatedBlocks
== 0)
594 pChunk
= pChunk
->pNext
;
597 if (u32FreeChunks
> 1)
599 /* Delete current chunk, it will also exclude all free blocks
600 * remaining in the chunk from the free list, so the pBlock
601 * will also be invalid after this.
603 vbglPhysHeapChunkDelete (pBlock
->pChunk
);
607 dumpheap ("post free");
609 vbglPhysHeapLeave ();
612 DECLVBGL(int) VbglPhysHeapInit (void)
614 int rc
= VINF_SUCCESS
;
616 /* Allocate the first chunk of the heap. */
617 VBGLPHYSHEAPBLOCK
*pBlock
= vbglPhysHeapChunkAlloc (0);
622 RTSemFastMutexCreate(&g_vbgldata
.mutexHeap
);
627 DECLVBGL(void) VbglPhysHeapTerminate (void)
629 while (g_vbgldata
.pChunkHead
)
631 vbglPhysHeapChunkDelete (g_vbgldata
.pChunkHead
);
634 RTSemFastMutexDestroy(g_vbgldata
.mutexHeap
);