[ros-diffs] [tkreuzer] 53989: {FREE[FREELDR] Improve the new heap to use a freelist, which boosts allocation performance by a factor of 7. Its now even slightly faster then bget.
tkreuzer at svn.reactos.org
tkreuzer at svn.reactos.org
Tue Oct 4 14:55:23 UTC 2011
Author: tkreuzer
Date: Tue Oct 4 14:55:23 2011
New Revision: 53989
URL: http://svn.reactos.org/svn/reactos?rev=53989&view=rev
Log:
{FREE[FREELDR]
Improve the new heap to use a freelist, which boosts allocation performance by a factor of 7. Its now even slightly faster then bget.
Modified:
trunk/reactos/boot/freeldr/freeldr/mm/heap_new.c
Modified: trunk/reactos/boot/freeldr/freeldr/mm/heap_new.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/boot/freeldr/freeldr/mm/heap_new.c?rev=53989&r1=53988&r2=53989&view=diff
==============================================================================
--- trunk/reactos/boot/freeldr/freeldr/mm/heap_new.c [iso-8859-1] (original)
+++ trunk/reactos/boot/freeldr/freeldr/mm/heap_new.c [iso-8859-1] Tue Oct 4 14:55:23 2011
@@ -28,12 +28,23 @@
PVOID FrLdrDefaultHeap;
PVOID FrLdrTempHeap;
-typedef struct _HEAP_BLOCK
+typedef struct _BLOCK_HEADER
{
USHORT Size;
USHORT PreviousSize;
ULONG Tag;
- UCHAR Data[];
+} BLOCK_HEADER, *PBLOCK_HEADER;
+
+typedef struct _BLOCK_DATA
+{
+ ULONG Flink;
+ ULONG Blink;
+} BLOCK_DATA, *PBLOCK_DATA;
+
+typedef struct _HEAP_BLOCK
+{
+ BLOCK_HEADER;
+ BLOCK_DATA Data[];
} HEAP_BLOCK, *PHEAP_BLOCK;
typedef struct _HEAP
@@ -44,6 +55,9 @@
ULONG NumAllocs;
ULONG NumFrees;
ULONG LargestAllocation;
+ ULONGLONG AllocationTime;
+ ULONGLONG FreeTime;
+ ULONG TerminatingBlock;
HEAP_BLOCK Blocks;
} HEAP, *PHEAP;
@@ -59,6 +73,7 @@
TRACE("HeapCreate(MemoryType=%ld)\n", MemoryType);
/* Allocate some memory for the heap */
+ MaximumSize = ALIGN_UP_BY(MaximumSize, MM_PAGE_SIZE);
Heap = MmAllocateMemoryWithType(MaximumSize, MemoryType);
if (!Heap)
{
@@ -68,7 +83,7 @@
}
/* Initialize the heap header */
- Heap->MaximumSize = ALIGN_UP_BY(MaximumSize, MM_PAGE_SIZE);
+ Heap->MaximumSize = MaximumSize;
Heap->CurrentAllocBytes = 0;
Heap->MaxAllocBytes = 0;
Heap->NumAllocs = 0;
@@ -79,8 +94,8 @@
Remaining = (MaximumSize - sizeof(HEAP)) / sizeof(HEAP_BLOCK);
TRACE("Remaining = %ld\n", Remaining);
- /* Substract one for the terminating entry */
- Remaining--;
+ /* Substract 2 for the terminating entry (header + free entry) */
+ Remaining -= 2;
Block = &Heap->Blocks;
PreviousSize = 0;
@@ -92,6 +107,8 @@
Block->Size = (USHORT)min(MAXUSHORT, Remaining - 1);
Block->PreviousSize = PreviousSize;
Block->Tag = 0;
+ Block->Data[0].Flink = (Block - &Heap->Blocks) + Block->Size + 1;
+ Block->Data[0].Blink = (Block - &Heap->Blocks) - 1 - PreviousSize;
/* Substract current block size from remainder */
Remaining -= (Block->Size + 1);
@@ -104,9 +121,13 @@
}
/* Now finish with a terminating block */
+ Heap->TerminatingBlock = Block - &Heap->Blocks;
Block->Size = 0;
Block->PreviousSize = PreviousSize;
Block->Tag = 'dnE#';
+ Block->Data[0].Flink = 0;
+ Block->Data[0].Blink = (Block - &Heap->Blocks) - 1 - PreviousSize;
+ Heap->Blocks.Data[0].Blink = Heap->TerminatingBlock;
return Heap;
}
@@ -117,11 +138,11 @@
{
PHEAP Heap = HeapHandle;
- /* Mark all pages free */
+ /* Mark all pages as firmware temporary, so they are free for the kernel */
MmMarkPagesInLookupTable(PageLookupTableAddress,
(ULONG_PTR)Heap / MM_PAGE_SIZE,
Heap->MaximumSize / MM_PAGE_SIZE,
- LoaderFree);
+ LoaderFirmwareTemporary);
}
VOID
@@ -173,7 +194,7 @@
if (Block->Size == 0) break;
}
- TRACE("HeapRelease() done, freed %ld pages\n", AllFreePages);
+ ERR("HeapRelease() done, freed %ld pages\n", AllFreePages);
}
VOID
@@ -182,17 +203,20 @@
PHEAP Heap;
Heap = FrLdrDefaultHeap;
- TRACE("Heap statistics for default heap:\n"
+ ERR("Heap statistics for default heap:\n"
"CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
"NumAllocs=%ld, NumFrees=%ld\n",
Heap->CurrentAllocBytes, Heap->MaxAllocBytes, Heap->LargestAllocation,
Heap->NumAllocs, Heap->NumFrees);
+ ERR("AllocTime = %I64d, FreeTime = %I64d, sum = %I64d\n",
+ Heap->AllocationTime, Heap->FreeTime, Heap->AllocationTime + Heap->FreeTime);
+
/* Release fre pages */
HeapRelease(FrLdrDefaultHeap);
Heap = FrLdrTempHeap;
- TRACE("Heap statistics for temp heap:\n"
+ ERR("Heap statistics for temp heap:\n"
"CurrentAlloc=0x%lx, MaxAlloc=0x%lx, LargestAllocation=0x%lx\n"
"NumAllocs=%ld, NumFrees=%ld\n",
Heap->CurrentAllocBytes, Heap->MaxAllocBytes, Heap->LargestAllocation,
@@ -200,6 +224,46 @@
/* Destroy the heap */
HeapDestroy(FrLdrTempHeap);
+}
+
+static VOID
+HeapRemoveFreeList(
+ PHEAP Heap,
+ PHEAP_BLOCK Block)
+{
+ PHEAP_BLOCK Previous, Next;
+
+ Next = &Heap->Blocks + Block->Data[0].Flink;
+ Previous = &Heap->Blocks + Block->Data[0].Blink;
+ ASSERT((Next->Tag == 0) || (Next->Tag == 'dnE#'));
+ ASSERT(Next->Data[0].Blink == Block - &Heap->Blocks);
+ ASSERT((Previous->Tag == 0) || (Previous->Tag == 'dnE#'));
+ ASSERT(Previous->Data[0].Flink == Block - &Heap->Blocks);
+
+ Next->Data[0].Blink = Previous - &Heap->Blocks;
+ Previous->Data[0].Flink = Next - &Heap->Blocks;
+}
+
+static VOID
+HeapInsertFreeList(
+ PHEAP Heap,
+ PHEAP_BLOCK FreeBlock)
+{
+ PHEAP_BLOCK ListHead, NextBlock;
+ ASSERT(FreeBlock->Tag == 0);
+
+ /* Terminating block serves as free list head */
+ ListHead = &Heap->Blocks + Heap->TerminatingBlock;
+
+ for (NextBlock = &Heap->Blocks + ListHead->Data[0].Flink;
+ NextBlock < FreeBlock;
+ NextBlock = &Heap->Blocks + NextBlock->Data[0].Flink);
+
+ FreeBlock->Data[0].Flink = NextBlock - &Heap->Blocks;
+ FreeBlock->Data[0].Blink = NextBlock->Data[0].Blink;
+ NextBlock->Data[0].Blink = FreeBlock - &Heap->Blocks;
+ NextBlock = &Heap->Blocks + FreeBlock->Data[0].Blink;
+ NextBlock->Data[0].Flink = FreeBlock - &Heap->Blocks;
}
PVOID
@@ -210,7 +274,8 @@
{
PHEAP Heap = HeapHandle;
PHEAP_BLOCK Block, NextBlock;
- USHORT BlockSize, PreviousSize = 0, Remaining;
+ USHORT BlockSize, Remaining;
+ ULONGLONG Time = __rdtsc();
/* Check if the allocation is too large */
if ((ByteSize + sizeof(HEAP_BLOCK)) > MAXUSHORT * sizeof(HEAP_BLOCK))
@@ -225,22 +290,22 @@
/* Calculate alloc size */
BlockSize = (USHORT)((ByteSize + sizeof(HEAP_BLOCK) - 1) / sizeof(HEAP_BLOCK));
- /* Loop all heap chunks */
- for (Block = &Heap->Blocks;
+ /* Walk the free block list */
+ Block = &Heap->Blocks + Heap->TerminatingBlock;
+ for (Block = &Heap->Blocks + Block->Data[0].Flink;
Block->Size != 0;
- Block = Block + 1 + Block->Size)
- {
- ASSERT(Block->PreviousSize == PreviousSize);
- PreviousSize = Block->Size;
-
- /* Continue, if its not free */
- if (Block->Tag != 0) continue;
+ Block = &Heap->Blocks + Block->Data[0].Flink)
+ {
+ ASSERT(Block->Tag == 0);
/* Continue, if its too small */
if (Block->Size < BlockSize) continue;
/* This block is just fine, use it */
Block->Tag = Tag;
+
+ /* Remove this entry from the free list */
+ HeapRemoveFreeList(Heap, Block);
/* Calculate the remaining size */
Remaining = Block->Size - BlockSize;
@@ -259,6 +324,7 @@
NextBlock->Size = Remaining - 1;
NextBlock->PreviousSize = BlockSize;
BlockSize = NextBlock->Size;
+ HeapInsertFreeList(Heap, NextBlock);
/* Advance to the next block */
NextBlock = NextBlock + 1 + BlockSize;
@@ -281,6 +347,7 @@
Heap->MaxAllocBytes = max(Heap->MaxAllocBytes, Heap->CurrentAllocBytes);
Heap->LargestAllocation = max(Heap->LargestAllocation,
Block->Size * sizeof(HEAP_BLOCK));
+ Heap->AllocationTime += (__rdtsc() - Time);
TRACE("HeapAllocate(%p, %ld, %.4s) -> return %p\n",
HeapHandle, ByteSize, &Tag, Block->Data);
@@ -303,6 +370,7 @@
PHEAP Heap = HeapHandle;
PHEAP_BLOCK Block, PrevBlock, NextBlock;
USHORT PreviousSize = 0;
+ ULONGLONG Time = __rdtsc();
TRACE("HeapFree(%p, %p)\n", HeapHandle, Pointer);
ASSERT(Tag != 'dnE#');
@@ -317,10 +385,10 @@
Block = ((PHEAP_BLOCK)Pointer) - 1;
/* Check if the tag matches */
- if (Tag && (Block->Tag != Tag))
- {
- ERR("HEAP: Bad tag! Pointer = %p: block tag '%.4s', requested '%.4s'\n",
- Pointer, &Block->Tag, &Tag);
+ if ((Tag && (Block->Tag != Tag)) || (Block->Tag == 0))
+ {
+ ERR("HEAP: Bad tag! Pointer=%p: block tag '%.4s', requested '%.4s', size=0x%lx\n",
+ Pointer, &Block->Tag, &Tag, Block->Size);
ASSERT(FALSE);
}
@@ -336,29 +404,34 @@
NextBlock = Block + Block->Size + 1;
/* Check if next block is free */
- if (NextBlock->Tag == 0)
- {
- /* Check if their combined size if small enough */
- if ((Block->Size + NextBlock->Size + 1) <= MAXUSHORT)
- {
- /* Merge next block into current */
- Block->Size += NextBlock->Size + 1;
- NextBlock = Block + Block->Size + 1;
- NextBlock->PreviousSize = Block->Size;
- }
+ if ((NextBlock->Tag == 0) &&
+ ((Block->Size + NextBlock->Size + 1) <= MAXUSHORT))
+ {
+ /* Merge next block into current */
+ Block->Size += NextBlock->Size + 1;
+ HeapRemoveFreeList(Heap, NextBlock);
+
+ NextBlock = Block + Block->Size + 1;
}
/* Check if there is a block before and it's free */
- if ((Block->PreviousSize != 0) && (PrevBlock->Tag == 0))
- {
- /* Check if their combined size if small enough */
- if ((PrevBlock->Size + Block->Size + 1) <= MAXUSHORT)
- {
- /* Merge current block into previous */
- PrevBlock->Size += Block->Size + 1;
- NextBlock->PreviousSize = PrevBlock->Size;
- }
- }
+ if ((Block->PreviousSize != 0) && (PrevBlock->Tag == 0) &&
+ ((PrevBlock->Size + Block->Size + 1) <= MAXUSHORT))
+ {
+ /* Merge current block into previous */
+ PrevBlock->Size += Block->Size + 1;
+ Block = PrevBlock;
+ }
+ else
+ {
+ /* Insert the entry into the free list */
+ HeapInsertFreeList(Heap, Block);
+ }
+
+ /* Update the next block's back link */
+ NextBlock->PreviousSize = Block->Size;
+
+ Heap->FreeTime += (__rdtsc() - Time);
}
More information about the Ros-diffs
mailing list