https://git.reactos.org/?p=reactos.git;a=commitdiff;h=325737f855d7ea89c08e7ddf6902863ff02ce743
commit 325737f855d7ea89c08e7ddf6902863ff02ce743 Author: Jérôme Gardou <[email protected]> AuthorDate: Fri Mar 5 13:04:52 2021 +0100 Commit: Jérôme Gardou <[email protected]> CommitDate: Tue Mar 16 13:23:21 2021 +0100 [SDK:RTL] Track the end of uncommitted ranges thanks to a "Guard" entry that we put at the end of each committed page This avoids busy loop to get the last valid entry of the previous committed range when committing a new one. CORE-15793 --- sdk/lib/rtl/heap.c | 459 ++++++++++++++++++++++++++++++----------------------- sdk/lib/rtl/heap.h | 4 +- 2 files changed, 263 insertions(+), 200 deletions(-) diff --git a/sdk/lib/rtl/heap.c b/sdk/lib/rtl/heap.c index 2eba86e046e..0e24cd48428 100644 --- a/sdk/lib/rtl/heap.c +++ b/sdk/lib/rtl/heap.c @@ -81,6 +81,25 @@ UCHAR FillPattern[HEAP_ENTRY_SIZE] = HEAP_TAIL_FILL }; +static +BOOLEAN +RtlpIsLastCommittedEntry(PHEAP_ENTRY Entry) +{ + if (Entry->Flags & HEAP_ENTRY_LAST_ENTRY) + return TRUE; + + Entry = Entry + Entry->Size; + + /* 1-sized busy last entry are the committed range guard entries */ + if ((Entry->Flags != (HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY)) || (Entry->Size != 1)) + return FALSE; + + /* This must be the last or the penultimate entry in the page */ + ASSERT(((PVOID)PAGE_ROUND_UP(Entry) == (Entry + 1)) || + ((PVOID)PAGE_ROUND_UP(Entry)== (Entry + 2))); + return TRUE; +} + /* FUNCTIONS *****************************************************************/ NTSTATUS NTAPI @@ -509,6 +528,8 @@ RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment) if (!NT_SUCCESS(Status)) return NULL; + ASSERT((PCHAR)UcrDescriptor == ((PCHAR)UcrSegment + UcrSegment->CommittedSize)); + /* Update sizes */ UcrSegment->CommittedSize += CommitSize; } @@ -608,42 +629,40 @@ RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment, Segment->NumberOfUnCommittedRanges++; } -PHEAP_FREE_ENTRY NTAPI +static +PHEAP_FREE_ENTRY RtlpFindAndCommitPages(PHEAP Heap, PHEAP_SEGMENT Segment, PSIZE_T Size, PVOID AddressRequested) { PLIST_ENTRY Current; - ULONG_PTR Address = 0; - PHEAP_UCR_DESCRIPTOR UcrDescriptor, PreviousUcr = NULL; - PHEAP_ENTRY FirstEntry, LastEntry; NTSTATUS Status; - DPRINT("RtlpFindAndCommitPages(%p %p %Ix %08Ix)\n", Heap, Segment, *Size, Address); + DPRINT("RtlpFindAndCommitPages(%p %p %Ix %p)\n", Heap, Segment, *Size, AddressRequested); /* Go through UCRs in a segment */ Current = Segment->UCRSegmentList.Flink; while (Current != &Segment->UCRSegmentList) { - UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry); + PHEAP_UCR_DESCRIPTOR UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry); /* Check if we can use that one right away */ if (UcrDescriptor->Size >= *Size && (UcrDescriptor->Address == AddressRequested || !AddressRequested)) { - /* Get the address */ - Address = (ULONG_PTR)UcrDescriptor->Address; + PHEAP_ENTRY GuardEntry, FreeEntry; + PVOID Address = UcrDescriptor->Address; /* Commit it */ if (Heap->CommitRoutine) { - Status = Heap->CommitRoutine(Heap, (PVOID *)&Address, Size); + Status = Heap->CommitRoutine(Heap, &Address, Size); } else { Status = ZwAllocateVirtualMemory(NtCurrentProcess(), - (PVOID *)&Address, + &Address, 0, Size, MEM_COMMIT, @@ -662,60 +681,67 @@ RtlpFindAndCommitPages(PHEAP Heap, /* Update tracking numbers */ Segment->NumberOfUnCommittedPages -= (ULONG)(*Size / PAGE_SIZE); - /* Calculate first and last entries */ - FirstEntry = (PHEAP_ENTRY)Address; + /* Update UCR descriptor */ + UcrDescriptor->Address = (PVOID)((ULONG_PTR)UcrDescriptor->Address + *Size); + UcrDescriptor->Size -= *Size; + + /* Grab the previous guard entry */ + GuardEntry = (PHEAP_ENTRY)Address - 1; + ASSERT(GuardEntry->Flags & HEAP_ENTRY_LAST_ENTRY); + ASSERT(GuardEntry->Flags & HEAP_ENTRY_BUSY); + ASSERT(GuardEntry->Size == 1); - LastEntry = Segment->LastEntryInSegment; - if (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY) || - LastEntry + LastEntry->Size != FirstEntry) + /* Did we have a double guard entry ? */ + if (GuardEntry->PreviousSize == 1) { - /* Go through the entries to find the last one */ - if (PreviousUcr) - LastEntry = (PHEAP_ENTRY)((ULONG_PTR)PreviousUcr->Address + PreviousUcr->Size); - else - LastEntry = &Segment->Entry; + /* Use the one before instead */ + GuardEntry--; - while (!(LastEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) - { - ASSERT(LastEntry->Size != 0); - LastEntry += LastEntry->Size; - } + ASSERT(GuardEntry->Flags & HEAP_ENTRY_LAST_ENTRY); + ASSERT(GuardEntry->Flags & HEAP_ENTRY_BUSY); + ASSERT(GuardEntry->Size == 1); + + /* We gain one slot more */ + *Size += HEAP_ENTRY_SIZE; } - ASSERT((LastEntry + LastEntry->Size) == FirstEntry); - /* Unmark it as a last entry */ - LastEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY; + /* This will become our returned free entry. + * Now we can make it span the whole committed range. + * But we keep one slot for a guard entry, if needed. + */ + FreeEntry = GuardEntry; - /* Update UCR descriptor */ - UcrDescriptor->Address = (PVOID)((ULONG_PTR)UcrDescriptor->Address + *Size); - UcrDescriptor->Size -= *Size; + FreeEntry->Flags &= ~(HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY); + FreeEntry->Size = (*Size) >> HEAP_ENTRY_SHIFT; DPRINT("Updating UcrDescriptor %p, new Address %p, size %lu\n", UcrDescriptor, UcrDescriptor->Address, UcrDescriptor->Size); - /* Set various first entry fields */ - FirstEntry->SegmentOffset = LastEntry->SegmentOffset; - FirstEntry->Size = (USHORT)(*Size >> HEAP_ENTRY_SHIFT); - FirstEntry->PreviousSize = LastEntry->Size; - /* Check if anything left in this UCR */ if (UcrDescriptor->Size == 0) { - /* It's fully exhausted */ + /* It's fully exhausted. Take the guard entry for us */ + FreeEntry->Size++; + *Size += HEAP_ENTRY_SIZE; + + ASSERT((FreeEntry + FreeEntry->Size) == UcrDescriptor->Address); /* Check if this is the end of the segment */ if(UcrDescriptor->Address == Segment->LastValidEntry) { - FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY; - Segment->LastEntryInSegment = FirstEntry; + FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY; } else { - FirstEntry->Flags = 0; - Segment->LastEntryInSegment = Segment->FirstEntry; - /* Update field of next entry */ - ASSERT((FirstEntry + FirstEntry->Size)->PreviousSize == 0); - (FirstEntry + FirstEntry->Size)->PreviousSize = FirstEntry->Size; + PHEAP_ENTRY NextEntry = UcrDescriptor->Address; + + /* We should not have a UCR right behind us */ + ASSERT((UcrDescriptor->SegmentEntry.Flink == &Segment->UCRSegmentList) + || (CONTAINING_RECORD(UcrDescriptor->SegmentEntry.Flink, HEAP_UCR_DESCRIPTOR, SegmentEntry)->Address > UcrDescriptor->Address)); + + ASSERT(NextEntry->PreviousSize == 0); + ASSERT(NextEntry == FreeEntry + FreeEntry->Size); + NextEntry->PreviousSize = FreeEntry->Size; } /* This UCR needs to be removed because it became useless */ @@ -726,33 +752,38 @@ RtlpFindAndCommitPages(PHEAP Heap, } else { - FirstEntry->Flags = HEAP_ENTRY_LAST_ENTRY; - Segment->LastEntryInSegment = FirstEntry; + /* Setup a guard entry */ + GuardEntry = (PHEAP_ENTRY)UcrDescriptor->Address - 1; + ASSERT(GuardEntry == FreeEntry + FreeEntry->Size); + GuardEntry->Flags = HEAP_ENTRY_LAST_ENTRY | HEAP_ENTRY_BUSY; + GuardEntry->Size = 1; + GuardEntry->PreviousSize = FreeEntry->Size; + GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; + DPRINT("Setting %p as UCR guard entry.\n", GuardEntry); } /* We're done */ - return (PHEAP_FREE_ENTRY)FirstEntry; + return (PHEAP_FREE_ENTRY)FreeEntry; } /* Advance to the next descriptor */ - PreviousUcr = UcrDescriptor; Current = Current->Flink; } return NULL; } -VOID NTAPI +static +VOID RtlpDeCommitFreeBlock(PHEAP Heap, PHEAP_FREE_ENTRY FreeEntry, SIZE_T Size) { PHEAP_SEGMENT Segment; - PHEAP_ENTRY PrecedingInUseEntry = NULL, NextInUseEntry = NULL; - PHEAP_FREE_ENTRY NextFreeEntry; + PHEAP_ENTRY NextEntry, GuardEntry; PHEAP_UCR_DESCRIPTOR UcrDescriptor; - SIZE_T PrecedingSize, NextSize, DecommitSize; - ULONG_PTR DecommitBase; + SIZE_T PrecedingSize, DecommitSize; + ULONG_PTR DecommitBase, DecommitEnd; NTSTATUS Status; DPRINT("Decommitting %p %p %x\n", Heap, FreeEntry, Size); @@ -772,49 +803,44 @@ RtlpDeCommitFreeBlock(PHEAP Heap, DecommitBase = ROUND_UP(FreeEntry, PAGE_SIZE); PrecedingSize = (PHEAP_ENTRY)DecommitBase - (PHEAP_ENTRY)FreeEntry; - if (PrecedingSize == 1) + if (PrecedingSize == 0) { - /* Just 1 heap entry, increase the base/size */ + /* We need some space in order to insert our guard entry */ DecommitBase += PAGE_SIZE; PrecedingSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT; } - else if (FreeEntry->PreviousSize && - (DecommitBase == (ULONG_PTR)FreeEntry)) - { - PrecedingInUseEntry = (PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize; - } - /* Get the next entry */ - NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size); - DecommitSize = ROUND_DOWN(NextFreeEntry, PAGE_SIZE); - NextSize = (PHEAP_ENTRY)NextFreeEntry - (PHEAP_ENTRY)DecommitSize; + /* Get the entry after this one. */ - if (NextSize == 1) + /* Do we really have a next entry */ + if (RtlpIsLastCommittedEntry((PHEAP_ENTRY)FreeEntry)) { - /* Just 1 heap entry, increase the size */ - DecommitSize -= PAGE_SIZE; - NextSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT; + /* No, Decommit till the next UCR. */ + DecommitEnd = PAGE_ROUND_UP((PHEAP_ENTRY)FreeEntry + FreeEntry->Size); + NextEntry = NULL; } - else if (NextSize == 0 && - !(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) + else { - NextInUseEntry = (PHEAP_ENTRY)NextFreeEntry; - } + NextEntry = (PHEAP_ENTRY)FreeEntry + Size; + DecommitEnd = PAGE_ROUND_DOWN(NextEntry); - NextFreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry - NextSize); - - /* Calculate real decommit size */ - if (DecommitSize > DecommitBase) - { - DecommitSize -= DecommitBase; + /* Can we make a free entry out of what's left ? */ + if ((NextEntry - (PHEAP_ENTRY)DecommitEnd) == 1) + { + /* Nope. Let's keep one page before this */ + DecommitEnd -= PAGE_SIZE; + } } - else + + if (DecommitEnd <= DecommitBase) { - /* Nothing to decommit */ + /* There's nothing left to decommit. */ RtlpInsertFreeBlock(Heap, FreeEntry, Size); return; } + DecommitSize = DecommitEnd - DecommitBase; + /* A decommit is necessary. Create a UCR descriptor */ UcrDescriptor = RtlpCreateUnCommittedRange(Segment); if (!UcrDescriptor) @@ -829,6 +855,7 @@ RtlpDeCommitFreeBlock(PHEAP Heap, (PVOID *)&DecommitBase, &DecommitSize, MEM_DECOMMIT); + ASSERT((DecommitBase + DecommitSize) == DecommitEnd); /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */ RtlpDestroyUnCommittedRange(Segment, UcrDescriptor); @@ -843,47 +870,74 @@ RtlpDeCommitFreeBlock(PHEAP Heap, RtlpInsertUnCommittedPages(Segment, DecommitBase, DecommitSize); Segment->NumberOfUnCommittedPages += (ULONG)(DecommitSize / PAGE_SIZE); - if (PrecedingSize) - { - /* Adjust size of this free entry and insert it */ - FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY; - FreeEntry->Size = (USHORT)PrecedingSize; - Heap->TotalFreeSize += PrecedingSize; - Segment->LastEntryInSegment = FreeEntry; - - /* Insert it into the free list */ - RtlpInsertFreeBlockHelper(Heap, FreeEntry, PrecedingSize, FALSE); - } - else if (PrecedingInUseEntry) - { - /* Adjust preceding in use entry */ - PrecedingInUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY; - Segment->LastEntryInSegment = PrecedingInUseEntry; - } - else if ((ULONG_PTR)Segment->LastEntryInSegment >= DecommitBase && - (ULONG_PTR)Segment->LastEntryInSegment < DecommitBase + DecommitSize) - { - /* Invalidate last entry */ - Segment->LastEntryInSegment = Segment->FirstEntry; + /* Insert our guard entry before this */ + GuardEntry = (PHEAP_ENTRY)DecommitBase - 1; + GuardEntry->Size = 1; + GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; + GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; + DPRINT("Setting %p as UCR guard entry.\n", GuardEntry); + + /* Now see what's really behind us */ + PrecedingSize--; + switch (PrecedingSize) + { + case 1: + /* No space left for a free entry. Make this another guard entry */ + GuardEntry->PreviousSize = 1; + GuardEntry--; + GuardEntry->Size = 1; + GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; + GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; + /* Fall-through */ + case 0: + /* There was just enough space four our guard entry */ + ASSERT((PHEAP_ENTRY)FreeEntry == GuardEntry); + GuardEntry->PreviousSize = FreeEntry->PreviousSize; + break; + default: + /* We can insert this as a free entry */ + GuardEntry->PreviousSize = PrecedingSize; + FreeEntry->Size = PrecedingSize; + FreeEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY; + FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &PrecedingSize, FALSE); + RtlpInsertFreeBlock(Heap, FreeEntry, PrecedingSize); + break; } /* Now the next one */ - if (NextSize) + if (NextEntry) { - /* Adjust size of this free entry and insert it */ - NextFreeEntry->Flags = 0; - NextFreeEntry->PreviousSize = 0; - NextFreeEntry->SegmentOffset = Segment->Entry.SegmentOffset; - NextFreeEntry->Size = (USHORT)NextSize; + ASSERT((PHEAP_ENTRY)DecommitEnd <= NextEntry); - ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)NextFreeEntry + NextSize))->PreviousSize = (USHORT)NextSize; + SIZE_T NextSize = NextEntry - (PHEAP_ENTRY)DecommitEnd; + if (NextSize) + { + PHEAP_FREE_ENTRY NextFreeEntry = (PHEAP_FREE_ENTRY)DecommitEnd; - Heap->TotalFreeSize += NextSize; - RtlpInsertFreeBlockHelper(Heap, NextFreeEntry, NextSize, FALSE); - } - else if (NextInUseEntry) - { - NextInUseEntry->PreviousSize = 0; + /* Make sure this is all valid */ + ASSERT((PHEAP_ENTRY)DecommitEnd < Segment->LastValidEntry); + ASSERT(NextSize >= 2); + + /* Adjust size of this free entry and insert it */ + NextFreeEntry->Flags = 0; + NextFreeEntry->PreviousSize = 0; + NextFreeEntry->SegmentOffset = Segment->Entry.SegmentOffset; + NextFreeEntry->Size = (USHORT)NextSize; + + NextEntry->PreviousSize = NextSize; + ASSERT(NextEntry == (PHEAP_ENTRY)NextFreeEntry + NextFreeEntry->Size); + + NextFreeEntry = RtlpCoalesceFreeBlocks(Heap, NextFreeEntry, &NextSize, FALSE); + RtlpInsertFreeBlock(Heap, NextFreeEntry, NextSize); + } + else + { + /* This one must be at the beginning of a page */ + ASSERT(NextEntry == (PHEAP_ENTRY)PAGE_ROUND_DOWN(NextEntry)); + /* And we must have a gap betwwen */ + ASSERT(NextEntry > (PHEAP_ENTRY)DecommitBase); + NextEntry->PreviousSize = 0; + } } } @@ -896,8 +950,6 @@ RtlpInitializeHeapSegment(IN OUT PHEAP Heap, IN SIZE_T SegmentReserve, IN SIZE_T SegmentCommit) { - PHEAP_ENTRY HeapEntry; - /* Preconditions */ ASSERT(Heap != NULL); ASSERT(Segment != NULL); @@ -936,26 +988,68 @@ RtlpInitializeHeapSegment(IN OUT PHEAP Heap, Segment->FirstEntry = &Segment->Entry + Segment->Entry.Size; Segment->LastValidEntry = (PHEAP_ENTRY)((ULONG_PTR)Segment + SegmentReserve); + /* Initialise the Heap Segment UnCommitted Range information */ + Segment->NumberOfUnCommittedPages = (ULONG)((SegmentReserve - SegmentCommit) >> PAGE_SHIFT); + Segment->NumberOfUnCommittedRanges = 0; + InitializeListHead(&Segment->UCRSegmentList); + + /* We must have space for a guard entry ! */ + ASSERT (((SegmentCommit >> HEAP_ENTRY_SHIFT) > Segment->Entry.Size) || (Segment->NumberOfUnCommittedPages == 0)); + if (((SIZE_T)Segment->Entry.Size << HEAP_ENTRY_SHIFT) < SegmentCommit) { - HeapEntry = Segment->FirstEntry; + PHEAP_ENTRY FreeEntry = NULL; - /* Prepare a Free Heap Entry header */ - HeapEntry->Flags = HEAP_ENTRY_LAST_ENTRY; - HeapEntry->PreviousSize = Segment->Entry.Size; - HeapEntry->SegmentOffset = SegmentIndex; + if (Segment->NumberOfUnCommittedPages != 0) + { + /* Ensure we put our guard entry at the end of the last committed page */ + PHEAP_ENTRY GuardEntry = &Segment->Entry + (SegmentCommit >> HEAP_ENTRY_SHIFT) - 1; - /* Register the Free Heap Entry */ - RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY) HeapEntry, (SegmentCommit >> HEAP_ENTRY_SHIFT) - Segment->Entry.Size); - } + ASSERT(GuardEntry > &Segment->Entry); + GuardEntry->Size = 1; + GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; + GuardEntry->SegmentOffset = SegmentIndex; + GuardEntry->PreviousSize = GuardEntry - Segment->FirstEntry; - /* Always point to a valid entry */ - Segment->LastEntryInSegment = Segment->FirstEntry; + /* Chack what is left behind us */ + switch (GuardEntry->PreviousSize) + { + case 1: + /* There is not enough space for a free entry. Double the guard entry */ + GuardEntry--; + GuardEntry->Size = 1; + GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; + GuardEntry->SegmentOffset = SegmentIndex; + DPRINT1("Setting %p as UCR guard entry.\n", GuardEntry); + /* Fall through */ + case 0: + ASSERT(GuardEntry == Segment->FirstEntry); + GuardEntry->PreviousSize = Segment->Entry.Size; + break; + default: + /* There will be a free entry between the segment and the guard entry */ + FreeEntry = Segment->FirstEntry; + FreeEntry->PreviousSize = Segment->Entry.Size; + FreeEntry->SegmentOffset = SegmentIndex; + FreeEntry->Size = GuardEntry->PreviousSize; + FreeEntry->Flags = 0; + break; + } + } + else + { + /* Prepare a Free Heap Entry header */ + FreeEntry = Segment->FirstEntry; + FreeEntry->PreviousSize = Segment->Entry.Size; + FreeEntry->SegmentOffset = SegmentIndex; + FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY; + FreeEntry->Size = (SegmentCommit >> HEAP_ENTRY_SHIFT) - Segment->Entry.Size; + } - /* Initialise the Heap Segment UnCommitted Range information */ - Segment->NumberOfUnCommittedPages = (ULONG)((SegmentReserve - SegmentCommit) >> PAGE_SHIFT); - Segment->NumberOfUnCommittedRanges = 0; - InitializeListHead(&Segment->UCRSegmentList); + /* Register the Free Heap Entry */ + if (FreeEntry) + RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)FreeEntry, FreeEntry->Size); + } /* Register the UnCommitted Range of the Heap Segment */ if (Segment->NumberOfUnCommittedPages != 0) @@ -1046,7 +1140,6 @@ RtlpCoalesceFreeBlocks (PHEAP Heap, { SegmentOffset = FreeEntry->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = FreeEntry; } } @@ -1087,7 +1180,6 @@ RtlpCoalesceFreeBlocks (PHEAP Heap, { SegmentOffset = FreeEntry->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = FreeEntry; } } } @@ -1785,7 +1877,6 @@ RtlpSplitEntry(PHEAP Heap, { SegmentOffset = SplitBlock->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = SplitBlock; } } } @@ -1956,10 +2047,8 @@ RtlAllocateHeap(IN PVOID HeapPtr, IN SIZE_T Size) { PHEAP Heap = (PHEAP)HeapPtr; - PULONG FreeListsInUse; - ULONG FreeListsInUseUlong; SIZE_T AllocationSize; - SIZE_T Index, InUseIndex, i; + SIZE_T Index; PLIST_ENTRY FreeListHead; PHEAP_ENTRY InUseEntry; PHEAP_FREE_ENTRY FreeBlock; @@ -2053,34 +2142,34 @@ RtlAllocateHeap(IN PVOID HeapPtr, else { /* Find smallest free block which this request could fit in */ - InUseIndex = Index >> 5; - FreeListsInUse = &Heap->u.FreeListsInUseUlong[InUseIndex]; - - /* This bit magic disables all sizes which are less than the requested allocation size */ - FreeListsInUseUlong = *FreeListsInUse++ & ~((1 << ((ULONG)Index & 0x1f)) - 1); - - /* If size is definitily more than our lists - go directly to the non-dedicated one */ - if (InUseIndex > 3) - return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked); - - /* Go through the list */ - for (i = InUseIndex; i < 4; i++) + ULONG InUseIndex = Index >> 5; + ULONG InUseMask; + ULONG Bit; + + /* Sanity check */ + ASSERT(InUseIndex < ARRAYSIZE(Heap->u.FreeListsInUseUlong)); + + /* Now check if there is a free entry for us. Beware of getting the right bit mask for the first iteration. */ + InUseMask = ~((1UL << (Index & 0x1F)) - 1); + InUseMask &= Heap->u.FreeListsInUseUlong[InUseIndex]; + DPRINT("InUseIndex %u, InUseMask %x, Index %u\n", InUseIndex, InUseMask, Index); + while (!BitScanForward(&Bit, InUseMask)) { - if (FreeListsInUseUlong) + InUseIndex++; + if (InUseIndex == ARRAYSIZE(Heap->u.FreeListsInUseUlong)) { - FreeListHead = &Heap->FreeLists[i * 32]; - break; + /* No luck this time. Go the dedicated way */ + return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked); } - - if (i < 3) FreeListsInUseUlong = *FreeListsInUse++; + InUseMask = Heap->u.FreeListsInUseUlong[InUseIndex]; } - /* Nothing found, search in the non-dedicated list */ - if (i == 4) - return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked); + /* Of course we must be in a list for entries bigger than what we were looking for in the first place */ + DPRINT("InUseIndex %u, Bit %u, Index %u\n", InUseIndex, Bit, Index); + ASSERT(((InUseIndex << 5) + Bit) > Index); + FreeListHead = &Heap->FreeLists[(InUseIndex << 5) + Bit]; - /* That list is found, now calculate exact block */ - FreeListHead += RtlpFindLeastSetBit(FreeListsInUseUlong); + ASSERT(!IsListEmpty(FreeListHead)); /* Take this entry and remove it from the list of free blocks */ FreeBlock = CONTAINING_RECORD(FreeListHead->Blink, @@ -2293,31 +2382,16 @@ BOOLEAN NTAPI RtlFreeHeap( FALSE); } - /* If there is no need to decommit the block - put it into a free list */ - if (BlockSize < Heap->DeCommitFreeBlockThreshold || - (Heap->TotalFreeSize + BlockSize < Heap->DeCommitTotalFreeThreshold)) + /* See if we should decommit this block */ + if ((BlockSize >= Heap->DeCommitFreeBlockThreshold) || + (Heap->TotalFreeSize + BlockSize >= Heap->DeCommitTotalFreeThreshold)) { - /* Check if it needs to go to a 0 list */ - if (BlockSize > HEAP_MAX_BLOCK_SIZE) - { - /* General-purpose 0 list */ - RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); - } - else - { - /* Usual free list */ - RtlpInsertFreeBlockHelper(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize, FALSE); - - /* Assert sizes are consistent */ - if (!(HeapEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) - { - ASSERT((HeapEntry + BlockSize)->PreviousSize == BlockSize); - } - - /* Increase the free size */ - Heap->TotalFreeSize += BlockSize; - } - + RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); + } + else + { + /* Insert into the free list */ + RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); if (RtlpGetMode() == UserMode && TagIndex != 0) @@ -2326,11 +2400,6 @@ BOOLEAN NTAPI RtlFreeHeap( UNIMPLEMENTED; } } - else - { - /* Decommit this block */ - RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); - } } /* Release the heap lock */ @@ -2359,10 +2428,7 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, /* Get entry flags */ EntryFlags = InUseEntry->Flags; - /* Get the next free entry */ - FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size); - - if (EntryFlags & HEAP_ENTRY_LAST_ENTRY) + if (RtlpIsLastCommittedEntry(InUseEntry)) { /* There is no next block, just uncommitted space. Calculate how much is needed */ FreeSize = (Index - InUseEntry->Size) << HEAP_ENTRY_SHIFT; @@ -2372,7 +2438,7 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, FreeEntry = RtlpFindAndCommitPages(Heap, Heap->Segments[InUseEntry->SegmentOffset], &FreeSize, - FreeEntry); + (PVOID)PAGE_ROUND_UP(InUseEntry + InUseEntry->Size)); /* Fail if it failed... */ if (!FreeEntry) return FALSE; @@ -2398,6 +2464,8 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, } else { + FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size); + /* The next block indeed exists. Check if it's free or in use */ if (FreeEntry->Flags & HEAP_ENTRY_BUSY) return FALSE; @@ -2456,7 +2524,6 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, { SegmentOffset = InUseEntry->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = InUseEntry; } } else @@ -2472,7 +2539,6 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, { SegmentOffset = UnusedEntry->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = UnusedEntry; /* Set flags and size */ UnusedEntry->Flags = RememberFlags; @@ -2527,7 +2593,6 @@ RtlpGrowBlockInPlace (IN PHEAP Heap, { SegmentOffset = UnusedEntry->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = UnusedEntry; } /* Insert it back and update total size */ @@ -2851,7 +2916,6 @@ RtlReAllocateHeap(HANDLE HeapPtr, { SegmentOffset = SplitBlock->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = SplitBlock; /* Set its size and insert it to the list */ SplitBlock->Size = (USHORT)FreeSize; @@ -2904,7 +2968,6 @@ RtlReAllocateHeap(HANDLE HeapPtr, { SegmentOffset = SplitBlock->SegmentOffset; ASSERT(SegmentOffset < HEAP_SEGMENTS); - Heap->Segments[SegmentOffset]->LastEntryInSegment = SplitBlock; } /* Insert the new one back and update total size */ diff --git a/sdk/lib/rtl/heap.h b/sdk/lib/rtl/heap.h index aef68e5edcd..881897d589c 100644 --- a/sdk/lib/rtl/heap.h +++ b/sdk/lib/rtl/heap.h @@ -144,6 +144,7 @@ C_ASSERT(sizeof(HEAP_ENTRY) == 16); C_ASSERT(sizeof(HEAP_ENTRY) == 8); #endif C_ASSERT((1 << HEAP_ENTRY_SHIFT) == sizeof(HEAP_ENTRY)); +C_ASSERT((2 << HEAP_ENTRY_SHIFT) == sizeof(HEAP_FREE_ENTRY)); typedef struct _HEAP_TAG_ENTRY { @@ -217,8 +218,7 @@ typedef struct _HEAP_LIST_LOOKUP ULONG NumberOfUnCommittedRanges; \ USHORT SegmentAllocatorBackTraceIndex; \ USHORT Reserved; \ - LIST_ENTRY UCRSegmentList; \ - PVOID LastEntryInSegment //FIXME: non-Vista + LIST_ENTRY UCRSegmentList typedef struct _HEAP {
