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/hea... ============================================================================== --- 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); }