1 /* 2 * COPYRIGHT: See COPYING in the top level directory 3 * PROJECT: ReactOS system libraries 4 * FILE: lib/rtl/heap.c 5 * PURPOSE: RTL Heap backend allocator 6 * PROGRAMMERS: Copyright 2010 Aleksey Bragin 7 * Copyright 2020 Katayama Hirofumi MZ 8 */ 9 10 /* Useful references: 11 http://msdn.microsoft.com/en-us/library/ms810466.aspx 12 http://msdn.microsoft.com/en-us/library/ms810603.aspx 13 http://www.securitylab.ru/analytics/216376.php 14 http://binglongx.spaces.live.com/blog/cns!142CBF6D49079DE8!596.entry 15 http://www.phreedom.org/research/exploits/asn1-bitstring/ 16 http://illmatics.com/Understanding_the_LFH.pdf 17 http://www.alex-ionescu.com/?p=18 18 */ 19 20 /* INCLUDES *****************************************************************/ 21 22 #include <rtl.h> 23 #include <heap.h> 24 25 #define NDEBUG 26 #include <debug.h> 27 28 /* Bitmaps stuff */ 29 30 /* How many least significant bits are clear */ 31 UCHAR RtlpBitsClearLow[] = 32 { 33 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 34 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 35 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 36 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 37 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 38 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 39 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 40 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 41 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 42 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 43 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 44 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 45 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 46 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 47 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 48 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 49 }; 50 51 FORCEINLINE 52 UCHAR 53 RtlpFindLeastSetBit(ULONG Bits) 54 { 55 if (Bits & 0xFFFF) 56 { 57 if (Bits & 0xFF) 58 return RtlpBitsClearLow[Bits & 0xFF]; /* Lowest byte */ 59 else 60 return RtlpBitsClearLow[(Bits >> 8) & 0xFF] + 8; /* 2nd byte */ 61 } 62 else 63 { 64 if ((Bits >> 16) & 0xFF) 65 return RtlpBitsClearLow[(Bits >> 16) & 0xFF] + 16; /* 3rd byte */ 66 else 67 return RtlpBitsClearLow[(Bits >> 24) & 0xFF] + 24; /* Highest byte */ 68 } 69 } 70 71 /* Maximum size of a tail-filling pattern used for compare operation */ 72 UCHAR FillPattern[HEAP_ENTRY_SIZE] = 73 { 74 HEAP_TAIL_FILL, 75 HEAP_TAIL_FILL, 76 HEAP_TAIL_FILL, 77 HEAP_TAIL_FILL, 78 HEAP_TAIL_FILL, 79 HEAP_TAIL_FILL, 80 HEAP_TAIL_FILL, 81 HEAP_TAIL_FILL 82 }; 83 84 static 85 BOOLEAN 86 RtlpIsLastCommittedEntry(PHEAP_ENTRY Entry) 87 { 88 if (Entry->Flags & HEAP_ENTRY_LAST_ENTRY) 89 return TRUE; 90 91 Entry = Entry + Entry->Size; 92 93 /* 1-sized busy last entry are the committed range guard entries */ 94 if ((Entry->Flags != (HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY)) || (Entry->Size != 1)) 95 return FALSE; 96 97 /* This must be the last or the penultimate entry in the page */ 98 ASSERT(((PVOID)PAGE_ROUND_UP(Entry) == (Entry + 1)) || 99 ((PVOID)PAGE_ROUND_UP(Entry)== (Entry + 2))); 100 return TRUE; 101 } 102 103 /* FUNCTIONS *****************************************************************/ 104 105 NTSTATUS NTAPI 106 RtlpInitializeHeap(OUT PHEAP Heap, 107 IN ULONG Flags, 108 IN PHEAP_LOCK Lock OPTIONAL, 109 IN PRTL_HEAP_PARAMETERS Parameters) 110 { 111 ULONG NumUCRs = 8; 112 ULONG Index; 113 SIZE_T HeaderSize; 114 NTSTATUS Status; 115 PHEAP_UCR_DESCRIPTOR UcrDescriptor; 116 SIZE_T DeCommitFreeBlockThreshold; 117 118 /* Preconditions */ 119 ASSERT(Heap != NULL); 120 ASSERT(Parameters != NULL); 121 ASSERT(!(Flags & HEAP_LOCK_USER_ALLOCATED)); 122 ASSERT(!(Flags & HEAP_NO_SERIALIZE) || (Lock == NULL)); /* HEAP_NO_SERIALIZE => no lock */ 123 124 /* Make sure we're not doing stupid things */ 125 DeCommitFreeBlockThreshold = Parameters->DeCommitFreeBlockThreshold >> HEAP_ENTRY_SHIFT; 126 /* Start out with the size of a plain Heap header + our hints of free entries + the bitmap */ 127 HeaderSize = FIELD_OFFSET(HEAP, FreeHints[DeCommitFreeBlockThreshold]) 128 + (ROUND_UP(DeCommitFreeBlockThreshold, RTL_BITS_OF(ULONG)) / RTL_BITS_OF(ULONG)) * sizeof(ULONG); 129 130 /* Check if space needs to be added for the Heap Lock */ 131 if (!(Flags & HEAP_NO_SERIALIZE)) 132 { 133 if (Lock != NULL) 134 /* The user manages the Heap Lock */ 135 Flags |= HEAP_LOCK_USER_ALLOCATED; 136 else 137 if (RtlpGetMode() == UserMode) 138 { 139 /* In user mode, the Heap Lock trails the Heap header */ 140 Lock = (PHEAP_LOCK) ((ULONG_PTR) (Heap) + HeaderSize); 141 HeaderSize += sizeof(HEAP_LOCK); 142 } 143 } 144 145 /* Add space for the initial Heap UnCommitted Range Descriptor list */ 146 UcrDescriptor = (PHEAP_UCR_DESCRIPTOR) ((ULONG_PTR) (Heap) + HeaderSize); 147 HeaderSize += NumUCRs * sizeof(HEAP_UCR_DESCRIPTOR); 148 149 HeaderSize = ROUND_UP(HeaderSize, HEAP_ENTRY_SIZE); 150 /* Sanity check */ 151 ASSERT(HeaderSize <= PAGE_SIZE); 152 153 /* Initialise the Heap Entry header containing the Heap header */ 154 Heap->Entry.Size = (USHORT)(HeaderSize >> HEAP_ENTRY_SHIFT); 155 Heap->Entry.Flags = HEAP_ENTRY_BUSY; 156 Heap->Entry.SmallTagIndex = LOBYTE(Heap->Entry.Size) ^ HIBYTE(Heap->Entry.Size) ^ Heap->Entry.Flags; 157 Heap->Entry.PreviousSize = 0; 158 Heap->Entry.SegmentOffset = 0; 159 Heap->Entry.UnusedBytes = 0; 160 161 /* Initialise the Heap header */ 162 Heap->Signature = HEAP_SIGNATURE; 163 Heap->Flags = Flags; 164 Heap->ForceFlags = (Flags & (HEAP_NO_SERIALIZE | 165 HEAP_GENERATE_EXCEPTIONS | 166 HEAP_ZERO_MEMORY | 167 HEAP_REALLOC_IN_PLACE_ONLY | 168 HEAP_VALIDATE_PARAMETERS_ENABLED | 169 HEAP_VALIDATE_ALL_ENABLED | 170 HEAP_TAIL_CHECKING_ENABLED | 171 HEAP_CREATE_ALIGN_16 | 172 HEAP_FREE_CHECKING_ENABLED)); 173 174 /* Initialise the Heap parameters */ 175 Heap->VirtualMemoryThreshold = ROUND_UP(Parameters->VirtualMemoryThreshold, sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT; 176 Heap->SegmentReserve = Parameters->SegmentReserve; 177 Heap->SegmentCommit = Parameters->SegmentCommit; 178 Heap->DeCommitFreeBlockThreshold = DeCommitFreeBlockThreshold; 179 Heap->DeCommitTotalFreeThreshold = Parameters->DeCommitTotalFreeThreshold >> HEAP_ENTRY_SHIFT; 180 Heap->MaximumAllocationSize = Parameters->MaximumAllocationSize; 181 Heap->CommitRoutine = Parameters->CommitRoutine; 182 183 /* Initialise the Heap validation info */ 184 Heap->HeaderValidateCopy = NULL; 185 Heap->HeaderValidateLength = (USHORT)HeaderSize; 186 187 /* Initialise the Heap Lock */ 188 if (!(Flags & HEAP_NO_SERIALIZE) && !(Flags & HEAP_LOCK_USER_ALLOCATED)) 189 { 190 Status = RtlInitializeHeapLock(&Lock); 191 if (!NT_SUCCESS(Status)) 192 return Status; 193 } 194 Heap->LockVariable = Lock; 195 196 /* Initialise the Heap alignment info */ 197 if (Flags & HEAP_CREATE_ALIGN_16) 198 { 199 Heap->AlignMask = (ULONG) ~15; 200 Heap->AlignRound = 15 + sizeof(HEAP_ENTRY); 201 } 202 else 203 { 204 Heap->AlignMask = (ULONG) ~(sizeof(HEAP_ENTRY) - 1); 205 Heap->AlignRound = 2 * sizeof(HEAP_ENTRY) - 1; 206 } 207 208 if (Flags & HEAP_TAIL_CHECKING_ENABLED) 209 Heap->AlignRound += sizeof(HEAP_ENTRY); 210 211 /* Initialise the Heap Segment list */ 212 for (Index = 0; Index < HEAP_SEGMENTS; ++Index) 213 Heap->Segments[Index] = NULL; 214 215 /* Initialise the free entry lists. */ 216 InitializeListHead(&Heap->FreeLists); 217 RtlInitializeBitMap(&Heap->FreeHintBitmap, 218 (PULONG)&Heap->FreeHints[DeCommitFreeBlockThreshold], 219 DeCommitFreeBlockThreshold); 220 RtlClearAllBits(&Heap->FreeHintBitmap); 221 RtlZeroMemory(&Heap->FreeHints[0], sizeof(Heap->FreeHints[0]) * DeCommitFreeBlockThreshold); 222 223 /* Initialise the Heap Virtual Allocated Blocks list */ 224 InitializeListHead(&Heap->VirtualAllocdBlocks); 225 226 /* Initialise the Heap UnCommitted Region lists */ 227 InitializeListHead(&Heap->UCRSegments); 228 InitializeListHead(&Heap->UCRList); 229 230 /* Register the initial Heap UnCommitted Region Descriptors */ 231 for (Index = 0; Index < NumUCRs; ++Index) 232 InsertTailList(&Heap->UCRList, &UcrDescriptor[Index].ListEntry); 233 234 return STATUS_SUCCESS; 235 } 236 237 VOID NTAPI 238 RtlpInsertFreeBlockHelper(PHEAP Heap, 239 PHEAP_FREE_ENTRY FreeEntry, 240 SIZE_T BlockSize, 241 BOOLEAN NoFill) 242 { 243 ULONG HintIndex, NextHintIndex; 244 245 ASSERT(FreeEntry->Size == BlockSize); 246 247 /* Fill if it's not denied */ 248 if (!NoFill) 249 { 250 FreeEntry->Flags &= ~(HEAP_ENTRY_FILL_PATTERN | 251 HEAP_ENTRY_EXTRA_PRESENT | 252 HEAP_ENTRY_BUSY); 253 254 if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) 255 { 256 RtlFillMemoryUlong((PCHAR)(FreeEntry + 1), 257 (BlockSize << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry), 258 ARENA_FREE_FILLER); 259 260 FreeEntry->Flags |= HEAP_ENTRY_FILL_PATTERN; 261 } 262 } 263 else 264 { 265 /* Clear out all flags except the last entry one */ 266 FreeEntry->Flags &= HEAP_ENTRY_LAST_ENTRY; 267 } 268 269 /* See if this should go to the dedicated list */ 270 if (BlockSize > Heap->DeCommitFreeBlockThreshold) 271 { 272 PLIST_ENTRY ListEntry = Heap->FreeHints[0]; 273 274 /* Check if we have a hint there */ 275 if (ListEntry == NULL) 276 { 277 ASSERT(!RtlTestBit(&Heap->FreeHintBitmap, 0)); 278 Heap->FreeHints[0] = &FreeEntry->FreeList; 279 RtlSetBit(&Heap->FreeHintBitmap, 0); 280 InsertTailList(&Heap->FreeLists, &FreeEntry->FreeList); 281 return; 282 } 283 284 ASSERT(RtlTestBit(&Heap->FreeHintBitmap, 0)); 285 286 while (ListEntry != &Heap->FreeLists) 287 { 288 PHEAP_FREE_ENTRY PreviousEntry = CONTAINING_RECORD(ListEntry, 289 HEAP_FREE_ENTRY, 290 FreeList); 291 if (PreviousEntry->Size >= BlockSize) 292 { 293 DPRINT("Inserting size %lu before %lu.\n", BlockSize, PreviousEntry->Size); 294 break; 295 } 296 297 ListEntry = ListEntry->Flink; 298 } 299 300 InsertTailList(ListEntry, &FreeEntry->FreeList); 301 302 /* Update our hint if needed */ 303 if (Heap->FreeHints[0] == ListEntry) 304 Heap->FreeHints[0] = &FreeEntry->FreeList; 305 306 return; 307 } 308 309 ASSERT(BlockSize >= 2); 310 HintIndex = BlockSize - 1; 311 312 if (Heap->FreeHints[HintIndex] != NULL) 313 { 314 ASSERT(RtlTestBit(&Heap->FreeHintBitmap, HintIndex)); 315 316 /* Insert it after our hint. */ 317 InsertHeadList(Heap->FreeHints[HintIndex], &FreeEntry->FreeList); 318 319 return; 320 } 321 322 /* This is the first time we insert such an entry in the list. */ 323 ASSERT(!RtlTestBit(&Heap->FreeHintBitmap, HintIndex)); 324 if (IsListEmpty(&Heap->FreeLists)) 325 { 326 /* First entry inserted in this list ever */ 327 InsertHeadList(&Heap->FreeLists, &FreeEntry->FreeList); 328 RtlSetBit(&Heap->FreeHintBitmap, HintIndex); 329 Heap->FreeHints[HintIndex] = &FreeEntry->FreeList; 330 return; 331 } 332 333 /* Find the closest one */ 334 NextHintIndex = RtlFindSetBits(&Heap->FreeHintBitmap, 1, HintIndex); 335 ASSERT(NextHintIndex != 0xFFFFFFFF); 336 if ((NextHintIndex == 0) || (NextHintIndex > HintIndex)) 337 { 338 /* 339 * We found a larger entry. Insert this one before. 340 * It is guaranteed to be our successor in the list. 341 */ 342 InsertTailList(Heap->FreeHints[NextHintIndex], &FreeEntry->FreeList); 343 } 344 else 345 { 346 /* We only found an entry smaller than us. Then we will be the largest one. */ 347 ASSERT(CONTAINING_RECORD(Heap->FreeLists.Blink, HEAP_FREE_ENTRY, FreeList)->Size < BlockSize); 348 InsertTailList(&Heap->FreeLists, &FreeEntry->FreeList); 349 } 350 351 /* Setup our hint */ 352 RtlSetBit(&Heap->FreeHintBitmap, HintIndex); 353 Heap->FreeHints[HintIndex] = &FreeEntry->FreeList; 354 } 355 356 VOID NTAPI 357 RtlpInsertFreeBlock(PHEAP Heap, 358 PHEAP_FREE_ENTRY FreeEntry, 359 SIZE_T BlockSize) 360 { 361 USHORT Size, PreviousSize; 362 UCHAR SegmentOffset, Flags; 363 PHEAP_SEGMENT Segment; 364 365 DPRINT("RtlpInsertFreeBlock(%p %p %x)\n", Heap, FreeEntry, BlockSize); 366 367 /* Increase the free size counter */ 368 Heap->TotalFreeSize += BlockSize; 369 370 /* Remember certain values */ 371 Flags = FreeEntry->Flags; 372 PreviousSize = FreeEntry->PreviousSize; 373 SegmentOffset = FreeEntry->SegmentOffset; 374 Segment = Heap->Segments[SegmentOffset]; 375 376 /* Process it */ 377 while (BlockSize) 378 { 379 /* Check for the max size */ 380 if (BlockSize > HEAP_MAX_BLOCK_SIZE) 381 { 382 Size = HEAP_MAX_BLOCK_SIZE; 383 384 /* Special compensation if it goes above limit just by 1 */ 385 if (BlockSize == (HEAP_MAX_BLOCK_SIZE + 1)) 386 Size -= 16; 387 388 FreeEntry->Flags = 0; 389 } 390 else 391 { 392 Size = (USHORT)BlockSize; 393 FreeEntry->Flags = Flags; 394 } 395 396 /* Change its size and insert it into a free list */ 397 FreeEntry->Size = Size; 398 FreeEntry->PreviousSize = PreviousSize; 399 FreeEntry->SegmentOffset = SegmentOffset; 400 401 /* Call a helper to actually insert the block */ 402 RtlpInsertFreeBlockHelper(Heap, FreeEntry, Size, FALSE); 403 404 /* Update sizes */ 405 PreviousSize = Size; 406 BlockSize -= Size; 407 408 /* Go to the next entry */ 409 FreeEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + Size); 410 411 /* Check if that's all */ 412 if ((PHEAP_ENTRY)FreeEntry >= Segment->LastValidEntry) return; 413 } 414 415 /* Update previous size if needed */ 416 if (!(Flags & HEAP_ENTRY_LAST_ENTRY)) 417 FreeEntry->PreviousSize = PreviousSize; 418 } 419 420 static 421 VOID 422 RtlpRemoveFreeBlock(PHEAP Heap, 423 PHEAP_FREE_ENTRY FreeEntry, 424 BOOLEAN NoFill) 425 { 426 SIZE_T Result, RealSize; 427 ULONG HintIndex; 428 429 /* Remove the free block */ 430 if (FreeEntry->Size > Heap->DeCommitFreeBlockThreshold) 431 HintIndex = 0; 432 else 433 HintIndex = FreeEntry->Size - 1; 434 435 ASSERT(RtlTestBit(&Heap->FreeHintBitmap, HintIndex)); 436 437 /* Are we removing the hint entry for this size ? */ 438 if (Heap->FreeHints[HintIndex] == &FreeEntry->FreeList) 439 { 440 PHEAP_FREE_ENTRY NewHintEntry = NULL; 441 if (FreeEntry->FreeList.Flink != &Heap->FreeLists) 442 { 443 NewHintEntry = CONTAINING_RECORD(FreeEntry->FreeList.Flink, 444 HEAP_FREE_ENTRY, 445 FreeList); 446 /* 447 * In non-dedicated list, we just put the next entry as hint. 448 * For the dedicated ones, we take care of putting entries of the right size hint. 449 */ 450 if ((HintIndex != 0) && (NewHintEntry->Size != FreeEntry->Size)) 451 { 452 /* Of course this must be a larger one after us */ 453 ASSERT(NewHintEntry->Size > FreeEntry->Size); 454 NewHintEntry = NULL; 455 } 456 } 457 458 /* Replace the hint, if we can */ 459 if (NewHintEntry != NULL) 460 { 461 Heap->FreeHints[HintIndex] = &NewHintEntry->FreeList; 462 } 463 else 464 { 465 Heap->FreeHints[HintIndex] = NULL; 466 RtlClearBit(&Heap->FreeHintBitmap, HintIndex); 467 } 468 } 469 470 RemoveEntryList(&FreeEntry->FreeList); 471 472 /* Fill with pattern if necessary */ 473 if (!NoFill && 474 (FreeEntry->Flags & HEAP_ENTRY_FILL_PATTERN)) 475 { 476 RealSize = (FreeEntry->Size << HEAP_ENTRY_SHIFT) - sizeof(*FreeEntry); 477 478 /* Deduct extra stuff from block's real size */ 479 if (FreeEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT && 480 RealSize > sizeof(HEAP_FREE_ENTRY_EXTRA)) 481 { 482 RealSize -= sizeof(HEAP_FREE_ENTRY_EXTRA); 483 } 484 485 /* Check if the free filler is intact */ 486 Result = RtlCompareMemoryUlong((PCHAR)(FreeEntry + 1), 487 RealSize, 488 ARENA_FREE_FILLER); 489 490 if (Result != RealSize) 491 { 492 DPRINT1("Free heap block %p modified at %p after it was freed\n", 493 FreeEntry, 494 (PCHAR)(FreeEntry + 1) + Result); 495 } 496 } 497 } 498 499 SIZE_T NTAPI 500 RtlpGetSizeOfBigBlock(PHEAP_ENTRY HeapEntry) 501 { 502 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry; 503 504 /* Get pointer to the containing record */ 505 VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock); 506 ASSERT(VirtualEntry->BusyBlock.Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY)); 507 508 /* Restore the real size */ 509 return VirtualEntry->CommitSize - HeapEntry->Size; 510 } 511 512 PHEAP_UCR_DESCRIPTOR NTAPI 513 RtlpCreateUnCommittedRange(PHEAP_SEGMENT Segment) 514 { 515 PLIST_ENTRY Entry; 516 PHEAP_UCR_DESCRIPTOR UcrDescriptor; 517 PHEAP_UCR_SEGMENT UcrSegment; 518 PHEAP Heap = Segment->Heap; 519 SIZE_T ReserveSize = 16 * PAGE_SIZE; 520 SIZE_T CommitSize = 1 * PAGE_SIZE; 521 NTSTATUS Status; 522 523 DPRINT("RtlpCreateUnCommittedRange(%p)\n", Segment); 524 525 /* Check if we have unused UCRs */ 526 if (IsListEmpty(&Heap->UCRList)) 527 { 528 /* Get a pointer to the first UCR segment */ 529 UcrSegment = CONTAINING_RECORD(Heap->UCRSegments.Flink, HEAP_UCR_SEGMENT, ListEntry); 530 531 /* Check the list of UCR segments */ 532 if (IsListEmpty(&Heap->UCRSegments) || 533 UcrSegment->ReservedSize == UcrSegment->CommittedSize) 534 { 535 /* We need to create a new one. Reserve 16 pages for it */ 536 UcrSegment = NULL; 537 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 538 (PVOID *)&UcrSegment, 539 0, 540 &ReserveSize, 541 MEM_RESERVE, 542 PAGE_READWRITE); 543 544 if (!NT_SUCCESS(Status)) return NULL; 545 546 /* Commit one page */ 547 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 548 (PVOID *)&UcrSegment, 549 0, 550 &CommitSize, 551 MEM_COMMIT, 552 PAGE_READWRITE); 553 554 if (!NT_SUCCESS(Status)) 555 { 556 /* Release reserved memory */ 557 ZwFreeVirtualMemory(NtCurrentProcess(), 558 (PVOID *)&UcrSegment, 559 &ReserveSize, 560 MEM_RELEASE); 561 return NULL; 562 } 563 564 /* Set it's data */ 565 UcrSegment->ReservedSize = ReserveSize; 566 UcrSegment->CommittedSize = CommitSize; 567 568 /* Add it to the head of the list */ 569 InsertHeadList(&Heap->UCRSegments, &UcrSegment->ListEntry); 570 571 /* Get a pointer to the first available UCR descriptor */ 572 UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)(UcrSegment + 1); 573 } 574 else 575 { 576 /* It's possible to use existing UCR segment. Commit one more page */ 577 UcrDescriptor = (PHEAP_UCR_DESCRIPTOR)((PCHAR)UcrSegment + UcrSegment->CommittedSize); 578 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 579 (PVOID *)&UcrDescriptor, 580 0, 581 &CommitSize, 582 MEM_COMMIT, 583 PAGE_READWRITE); 584 585 if (!NT_SUCCESS(Status)) return NULL; 586 587 ASSERT((PCHAR)UcrDescriptor == ((PCHAR)UcrSegment + UcrSegment->CommittedSize)); 588 589 /* Update sizes */ 590 UcrSegment->CommittedSize += CommitSize; 591 } 592 593 /* There is a whole bunch of new UCR descriptors. Put them into the unused list */ 594 while ((PCHAR)(UcrDescriptor + 1) <= (PCHAR)UcrSegment + UcrSegment->CommittedSize) 595 { 596 InsertTailList(&Heap->UCRList, &UcrDescriptor->ListEntry); 597 UcrDescriptor++; 598 } 599 } 600 601 /* There are unused UCRs, just get the first one */ 602 Entry = RemoveHeadList(&Heap->UCRList); 603 UcrDescriptor = CONTAINING_RECORD(Entry, HEAP_UCR_DESCRIPTOR, ListEntry); 604 return UcrDescriptor; 605 } 606 607 VOID NTAPI 608 RtlpDestroyUnCommittedRange(PHEAP_SEGMENT Segment, 609 PHEAP_UCR_DESCRIPTOR UcrDescriptor) 610 { 611 /* Zero it out */ 612 UcrDescriptor->Address = NULL; 613 UcrDescriptor->Size = 0; 614 615 /* Put it into the heap's list of unused UCRs */ 616 InsertHeadList(&Segment->Heap->UCRList, &UcrDescriptor->ListEntry); 617 } 618 619 VOID NTAPI 620 RtlpInsertUnCommittedPages(PHEAP_SEGMENT Segment, 621 ULONG_PTR Address, 622 SIZE_T Size) 623 { 624 PLIST_ENTRY Current; 625 PHEAP_UCR_DESCRIPTOR UcrDescriptor; 626 627 DPRINT("RtlpInsertUnCommittedPages(%p %08Ix %Ix)\n", Segment, Address, Size); 628 629 /* Go through the list of UCR descriptors, they are sorted from lowest address 630 to the highest */ 631 Current = Segment->UCRSegmentList.Flink; 632 while (Current != &Segment->UCRSegmentList) 633 { 634 UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry); 635 636 if ((ULONG_PTR)UcrDescriptor->Address > Address) 637 { 638 /* Check for a really lucky case */ 639 if ((Address + Size) == (ULONG_PTR)UcrDescriptor->Address) 640 { 641 /* Exact match */ 642 UcrDescriptor->Address = (PVOID)Address; 643 UcrDescriptor->Size += Size; 644 return; 645 } 646 647 /* We found the block before which the new one should go */ 648 break; 649 } 650 else if (((ULONG_PTR)UcrDescriptor->Address + UcrDescriptor->Size) == Address) 651 { 652 /* Modify this entry */ 653 Address = (ULONG_PTR)UcrDescriptor->Address; 654 Size += UcrDescriptor->Size; 655 656 /* Advance to the next descriptor */ 657 Current = Current->Flink; 658 659 /* Remove the current descriptor from the list and destroy it */ 660 RemoveEntryList(&UcrDescriptor->SegmentEntry); 661 RtlpDestroyUnCommittedRange(Segment, UcrDescriptor); 662 663 Segment->NumberOfUnCommittedRanges--; 664 } 665 else 666 { 667 /* Advance to the next descriptor */ 668 Current = Current->Flink; 669 } 670 } 671 672 /* Create a new UCR descriptor */ 673 UcrDescriptor = RtlpCreateUnCommittedRange(Segment); 674 if (!UcrDescriptor) return; 675 676 UcrDescriptor->Address = (PVOID)Address; 677 UcrDescriptor->Size = Size; 678 679 /* "Current" is the descriptor before which our one should go */ 680 InsertTailList(Current, &UcrDescriptor->SegmentEntry); 681 682 DPRINT("Added segment UCR with base %08Ix, size 0x%x\n", Address, Size); 683 684 /* Increase counters */ 685 Segment->NumberOfUnCommittedRanges++; 686 } 687 688 static 689 PHEAP_FREE_ENTRY 690 RtlpFindAndCommitPages(PHEAP Heap, 691 PHEAP_SEGMENT Segment, 692 PSIZE_T Size, 693 PVOID AddressRequested) 694 { 695 PLIST_ENTRY Current; 696 NTSTATUS Status; 697 698 DPRINT("RtlpFindAndCommitPages(%p %p %Ix %p)\n", Heap, Segment, *Size, AddressRequested); 699 700 /* Go through UCRs in a segment */ 701 Current = Segment->UCRSegmentList.Flink; 702 while (Current != &Segment->UCRSegmentList) 703 { 704 PHEAP_UCR_DESCRIPTOR UcrDescriptor = CONTAINING_RECORD(Current, HEAP_UCR_DESCRIPTOR, SegmentEntry); 705 706 /* Check if we can use that one right away */ 707 if (UcrDescriptor->Size >= *Size && 708 (UcrDescriptor->Address == AddressRequested || !AddressRequested)) 709 { 710 PHEAP_ENTRY GuardEntry, FreeEntry; 711 PVOID Address = UcrDescriptor->Address; 712 713 /* Commit it */ 714 if (Heap->CommitRoutine) 715 { 716 Status = Heap->CommitRoutine(Heap, &Address, Size); 717 } 718 else 719 { 720 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 721 &Address, 722 0, 723 Size, 724 MEM_COMMIT, 725 PAGE_READWRITE); 726 } 727 728 DPRINT("Committed %Iu bytes at base %08Ix, UCR size is %lu\n", *Size, Address, UcrDescriptor->Size); 729 730 /* Fail in unsuccessful case */ 731 if (!NT_SUCCESS(Status)) 732 { 733 DPRINT1("Committing page failed with status 0x%08X\n", Status); 734 return NULL; 735 } 736 737 /* Update tracking numbers */ 738 Segment->NumberOfUnCommittedPages -= (ULONG)(*Size / PAGE_SIZE); 739 740 /* Update UCR descriptor */ 741 UcrDescriptor->Address = (PVOID)((ULONG_PTR)UcrDescriptor->Address + *Size); 742 UcrDescriptor->Size -= *Size; 743 744 /* Grab the previous guard entry */ 745 GuardEntry = (PHEAP_ENTRY)Address - 1; 746 ASSERT(GuardEntry->Flags & HEAP_ENTRY_LAST_ENTRY); 747 ASSERT(GuardEntry->Flags & HEAP_ENTRY_BUSY); 748 ASSERT(GuardEntry->Size == 1); 749 750 /* Did we have a double guard entry ? */ 751 if (GuardEntry->PreviousSize == 1) 752 { 753 /* Use the one before instead */ 754 GuardEntry--; 755 756 ASSERT(GuardEntry->Flags & HEAP_ENTRY_LAST_ENTRY); 757 ASSERT(GuardEntry->Flags & HEAP_ENTRY_BUSY); 758 ASSERT(GuardEntry->Size == 1); 759 760 /* We gain one slot more */ 761 *Size += HEAP_ENTRY_SIZE; 762 } 763 764 /* This will become our returned free entry. 765 * Now we can make it span the whole committed range. 766 * But we keep one slot for a guard entry, if needed. 767 */ 768 FreeEntry = GuardEntry; 769 770 FreeEntry->Flags &= ~(HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY); 771 FreeEntry->Size = (*Size) >> HEAP_ENTRY_SHIFT; 772 773 DPRINT("Updating UcrDescriptor %p, new Address %p, size %lu\n", 774 UcrDescriptor, UcrDescriptor->Address, UcrDescriptor->Size); 775 776 /* Check if anything left in this UCR */ 777 if (UcrDescriptor->Size == 0) 778 { 779 /* It's fully exhausted. Take the guard entry for us */ 780 FreeEntry->Size++; 781 *Size += HEAP_ENTRY_SIZE; 782 783 ASSERT((FreeEntry + FreeEntry->Size) == UcrDescriptor->Address); 784 785 /* Check if this is the end of the segment */ 786 if(UcrDescriptor->Address == Segment->LastValidEntry) 787 { 788 FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY; 789 } 790 else 791 { 792 PHEAP_ENTRY NextEntry = UcrDescriptor->Address; 793 794 /* We should not have a UCR right behind us */ 795 ASSERT((UcrDescriptor->SegmentEntry.Flink == &Segment->UCRSegmentList) 796 || (CONTAINING_RECORD(UcrDescriptor->SegmentEntry.Flink, HEAP_UCR_DESCRIPTOR, SegmentEntry)->Address > UcrDescriptor->Address)); 797 798 ASSERT(NextEntry->PreviousSize == 0); 799 ASSERT(NextEntry == FreeEntry + FreeEntry->Size); 800 NextEntry->PreviousSize = FreeEntry->Size; 801 } 802 803 /* This UCR needs to be removed because it became useless */ 804 RemoveEntryList(&UcrDescriptor->SegmentEntry); 805 806 RtlpDestroyUnCommittedRange(Segment, UcrDescriptor); 807 Segment->NumberOfUnCommittedRanges--; 808 } 809 else 810 { 811 /* Setup a guard entry */ 812 GuardEntry = (PHEAP_ENTRY)UcrDescriptor->Address - 1; 813 ASSERT(GuardEntry == FreeEntry + FreeEntry->Size); 814 GuardEntry->Flags = HEAP_ENTRY_LAST_ENTRY | HEAP_ENTRY_BUSY; 815 GuardEntry->Size = 1; 816 GuardEntry->PreviousSize = FreeEntry->Size; 817 GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; 818 DPRINT("Setting %p as UCR guard entry.\n", GuardEntry); 819 } 820 821 /* We're done */ 822 return (PHEAP_FREE_ENTRY)FreeEntry; 823 } 824 825 /* Advance to the next descriptor */ 826 Current = Current->Flink; 827 } 828 829 return NULL; 830 } 831 832 static 833 VOID 834 RtlpDeCommitFreeBlock(PHEAP Heap, 835 PHEAP_FREE_ENTRY FreeEntry, 836 SIZE_T Size) 837 { 838 PHEAP_SEGMENT Segment; 839 PHEAP_ENTRY NextEntry, GuardEntry; 840 PHEAP_UCR_DESCRIPTOR UcrDescriptor; 841 SIZE_T PrecedingSize, DecommitSize; 842 ULONG_PTR DecommitBase, DecommitEnd; 843 NTSTATUS Status; 844 845 DPRINT("Decommitting %p %p %x\n", Heap, FreeEntry, Size); 846 847 /* We can't decommit if there is a commit routine! */ 848 if (Heap->CommitRoutine) 849 { 850 /* Just add it back the usual way */ 851 RtlpInsertFreeBlock(Heap, FreeEntry, Size); 852 return; 853 } 854 855 /* Get the segment */ 856 Segment = Heap->Segments[FreeEntry->SegmentOffset]; 857 858 /* Get the preceding entry */ 859 DecommitBase = ROUND_UP(FreeEntry, PAGE_SIZE); 860 PrecedingSize = (PHEAP_ENTRY)DecommitBase - (PHEAP_ENTRY)FreeEntry; 861 862 if (PrecedingSize == 0) 863 { 864 /* We need some space in order to insert our guard entry */ 865 DecommitBase += PAGE_SIZE; 866 PrecedingSize += PAGE_SIZE >> HEAP_ENTRY_SHIFT; 867 } 868 869 /* Get the entry after this one. */ 870 871 /* Do we really have a next entry */ 872 if (RtlpIsLastCommittedEntry((PHEAP_ENTRY)FreeEntry)) 873 { 874 /* No, Decommit till the next UCR. */ 875 DecommitEnd = PAGE_ROUND_UP((PHEAP_ENTRY)FreeEntry + FreeEntry->Size); 876 NextEntry = NULL; 877 } 878 else 879 { 880 NextEntry = (PHEAP_ENTRY)FreeEntry + Size; 881 DecommitEnd = PAGE_ROUND_DOWN(NextEntry); 882 883 /* Can we make a free entry out of what's left ? */ 884 if ((NextEntry - (PHEAP_ENTRY)DecommitEnd) == 1) 885 { 886 /* Nope. Let's keep one page before this */ 887 DecommitEnd -= PAGE_SIZE; 888 } 889 } 890 891 if (DecommitEnd <= DecommitBase) 892 { 893 /* There's nothing left to decommit. */ 894 RtlpInsertFreeBlock(Heap, FreeEntry, Size); 895 return; 896 } 897 898 DecommitSize = DecommitEnd - DecommitBase; 899 900 /* A decommit is necessary. Create a UCR descriptor */ 901 UcrDescriptor = RtlpCreateUnCommittedRange(Segment); 902 if (!UcrDescriptor) 903 { 904 DPRINT1("HEAP: Failed to create UCR descriptor\n"); 905 RtlpInsertFreeBlock(Heap, FreeEntry, PrecedingSize); 906 return; 907 } 908 909 /* Decommit the memory */ 910 Status = ZwFreeVirtualMemory(NtCurrentProcess(), 911 (PVOID *)&DecommitBase, 912 &DecommitSize, 913 MEM_DECOMMIT); 914 ASSERT((DecommitBase + DecommitSize) == DecommitEnd); 915 916 /* Delete that UCR. This is needed to assure there is an unused UCR entry in the list */ 917 RtlpDestroyUnCommittedRange(Segment, UcrDescriptor); 918 919 if (!NT_SUCCESS(Status)) 920 { 921 RtlpInsertFreeBlock(Heap, FreeEntry, Size); 922 return; 923 } 924 925 /* Insert uncommitted pages */ 926 RtlpInsertUnCommittedPages(Segment, DecommitBase, DecommitSize); 927 Segment->NumberOfUnCommittedPages += (ULONG)(DecommitSize / PAGE_SIZE); 928 929 /* Insert our guard entry before this */ 930 GuardEntry = (PHEAP_ENTRY)DecommitBase - 1; 931 GuardEntry->Size = 1; 932 GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; 933 GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; 934 DPRINT("Setting %p as UCR guard entry.\n", GuardEntry); 935 936 /* Now see what's really behind us */ 937 PrecedingSize--; 938 switch (PrecedingSize) 939 { 940 case 1: 941 /* No space left for a free entry. Make this another guard entry */ 942 GuardEntry->PreviousSize = 1; 943 GuardEntry--; 944 GuardEntry->Size = 1; 945 GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; 946 GuardEntry->SegmentOffset = FreeEntry->SegmentOffset; 947 /* Fall-through */ 948 case 0: 949 /* There was just enough space four our guard entry */ 950 ASSERT((PHEAP_ENTRY)FreeEntry == GuardEntry); 951 GuardEntry->PreviousSize = FreeEntry->PreviousSize; 952 break; 953 default: 954 /* We can insert this as a free entry */ 955 GuardEntry->PreviousSize = PrecedingSize; 956 FreeEntry->Size = PrecedingSize; 957 FreeEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY; 958 FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &PrecedingSize, FALSE); 959 RtlpInsertFreeBlock(Heap, FreeEntry, PrecedingSize); 960 break; 961 } 962 963 /* Now the next one */ 964 if (NextEntry) 965 { 966 ASSERT((PHEAP_ENTRY)DecommitEnd <= NextEntry); 967 968 SIZE_T NextSize = NextEntry - (PHEAP_ENTRY)DecommitEnd; 969 if (NextSize) 970 { 971 PHEAP_FREE_ENTRY NextFreeEntry = (PHEAP_FREE_ENTRY)DecommitEnd; 972 973 /* Make sure this is all valid */ 974 ASSERT((PHEAP_ENTRY)DecommitEnd < Segment->LastValidEntry); 975 ASSERT(NextSize >= 2); 976 977 /* Adjust size of this free entry and insert it */ 978 NextFreeEntry->Flags = 0; 979 NextFreeEntry->PreviousSize = 0; 980 NextFreeEntry->SegmentOffset = Segment->Entry.SegmentOffset; 981 NextFreeEntry->Size = (USHORT)NextSize; 982 983 NextEntry->PreviousSize = NextSize; 984 ASSERT(NextEntry == (PHEAP_ENTRY)NextFreeEntry + NextFreeEntry->Size); 985 986 NextFreeEntry = RtlpCoalesceFreeBlocks(Heap, NextFreeEntry, &NextSize, FALSE); 987 RtlpInsertFreeBlock(Heap, NextFreeEntry, NextSize); 988 } 989 else 990 { 991 /* This one must be at the beginning of a page */ 992 ASSERT(NextEntry == (PHEAP_ENTRY)PAGE_ROUND_DOWN(NextEntry)); 993 /* And we must have a gap betwwen */ 994 ASSERT(NextEntry > (PHEAP_ENTRY)DecommitBase); 995 NextEntry->PreviousSize = 0; 996 } 997 } 998 } 999 1000 NTSTATUS 1001 NTAPI 1002 RtlpInitializeHeapSegment(IN OUT PHEAP Heap, 1003 OUT PHEAP_SEGMENT Segment, 1004 IN UCHAR SegmentIndex, 1005 IN ULONG SegmentFlags, 1006 IN SIZE_T SegmentReserve, 1007 IN SIZE_T SegmentCommit) 1008 { 1009 /* Preconditions */ 1010 ASSERT(Heap != NULL); 1011 ASSERT(Segment != NULL); 1012 ASSERT(SegmentCommit >= PAGE_SIZE); 1013 ASSERT(ROUND_DOWN(SegmentCommit, PAGE_SIZE) == SegmentCommit); 1014 ASSERT(SegmentReserve >= SegmentCommit); 1015 ASSERT(ROUND_DOWN(SegmentReserve, PAGE_SIZE) == SegmentReserve); 1016 1017 DPRINT("RtlpInitializeHeapSegment(%p %p %x %x %lx %lx)\n", Heap, Segment, SegmentIndex, SegmentFlags, SegmentReserve, SegmentCommit); 1018 1019 /* Initialise the Heap Entry header if this is not the first Heap Segment */ 1020 if ((PHEAP_SEGMENT) (Heap) != Segment) 1021 { 1022 Segment->Entry.Size = ROUND_UP(sizeof(HEAP_SEGMENT), sizeof(HEAP_ENTRY)) >> HEAP_ENTRY_SHIFT; 1023 Segment->Entry.Flags = HEAP_ENTRY_BUSY; 1024 Segment->Entry.SmallTagIndex = LOBYTE(Segment->Entry.Size) ^ HIBYTE(Segment->Entry.Size) ^ Segment->Entry.Flags; 1025 Segment->Entry.PreviousSize = 0; 1026 Segment->Entry.SegmentOffset = SegmentIndex; 1027 Segment->Entry.UnusedBytes = 0; 1028 } 1029 1030 /* Sanity check */ 1031 ASSERT((Segment->Entry.Size << HEAP_ENTRY_SHIFT) <= PAGE_SIZE); 1032 1033 /* Initialise the Heap Segment header */ 1034 Segment->SegmentSignature = HEAP_SEGMENT_SIGNATURE; 1035 Segment->SegmentFlags = SegmentFlags; 1036 Segment->Heap = Heap; 1037 Heap->Segments[SegmentIndex] = Segment; 1038 1039 /* Initialise the Heap Segment location information */ 1040 Segment->BaseAddress = Segment; 1041 Segment->NumberOfPages = (ULONG)(SegmentReserve >> PAGE_SHIFT); 1042 1043 /* Initialise the Heap Entries contained within the Heap Segment */ 1044 Segment->FirstEntry = &Segment->Entry + Segment->Entry.Size; 1045 Segment->LastValidEntry = (PHEAP_ENTRY)((ULONG_PTR)Segment + SegmentReserve); 1046 1047 /* Initialise the Heap Segment UnCommitted Range information */ 1048 Segment->NumberOfUnCommittedPages = (ULONG)((SegmentReserve - SegmentCommit) >> PAGE_SHIFT); 1049 Segment->NumberOfUnCommittedRanges = 0; 1050 InitializeListHead(&Segment->UCRSegmentList); 1051 1052 /* We must have space for a guard entry ! */ 1053 ASSERT (((SegmentCommit >> HEAP_ENTRY_SHIFT) > Segment->Entry.Size) || (Segment->NumberOfUnCommittedPages == 0)); 1054 1055 if (((SIZE_T)Segment->Entry.Size << HEAP_ENTRY_SHIFT) < SegmentCommit) 1056 { 1057 PHEAP_ENTRY FreeEntry = NULL; 1058 1059 if (Segment->NumberOfUnCommittedPages != 0) 1060 { 1061 /* Ensure we put our guard entry at the end of the last committed page */ 1062 PHEAP_ENTRY GuardEntry = &Segment->Entry + (SegmentCommit >> HEAP_ENTRY_SHIFT) - 1; 1063 1064 ASSERT(GuardEntry > &Segment->Entry); 1065 GuardEntry->Size = 1; 1066 GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; 1067 GuardEntry->SegmentOffset = SegmentIndex; 1068 GuardEntry->PreviousSize = GuardEntry - Segment->FirstEntry; 1069 1070 /* Chack what is left behind us */ 1071 switch (GuardEntry->PreviousSize) 1072 { 1073 case 1: 1074 /* There is not enough space for a free entry. Double the guard entry */ 1075 GuardEntry--; 1076 GuardEntry->Size = 1; 1077 GuardEntry->Flags = HEAP_ENTRY_BUSY | HEAP_ENTRY_LAST_ENTRY; 1078 GuardEntry->SegmentOffset = SegmentIndex; 1079 DPRINT1("Setting %p as UCR guard entry.\n", GuardEntry); 1080 /* Fall through */ 1081 case 0: 1082 ASSERT(GuardEntry == Segment->FirstEntry); 1083 GuardEntry->PreviousSize = Segment->Entry.Size; 1084 break; 1085 default: 1086 /* There will be a free entry between the segment and the guard entry */ 1087 FreeEntry = Segment->FirstEntry; 1088 FreeEntry->PreviousSize = Segment->Entry.Size; 1089 FreeEntry->SegmentOffset = SegmentIndex; 1090 FreeEntry->Size = GuardEntry->PreviousSize; 1091 FreeEntry->Flags = 0; 1092 break; 1093 } 1094 } 1095 else 1096 { 1097 /* Prepare a Free Heap Entry header */ 1098 FreeEntry = Segment->FirstEntry; 1099 FreeEntry->PreviousSize = Segment->Entry.Size; 1100 FreeEntry->SegmentOffset = SegmentIndex; 1101 FreeEntry->Flags = HEAP_ENTRY_LAST_ENTRY; 1102 FreeEntry->Size = (SegmentCommit >> HEAP_ENTRY_SHIFT) - Segment->Entry.Size; 1103 } 1104 1105 /* Register the Free Heap Entry */ 1106 if (FreeEntry) 1107 RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)FreeEntry, FreeEntry->Size); 1108 } 1109 1110 /* Register the UnCommitted Range of the Heap Segment */ 1111 if (Segment->NumberOfUnCommittedPages != 0) 1112 RtlpInsertUnCommittedPages(Segment, (ULONG_PTR) (Segment) + SegmentCommit, SegmentReserve - SegmentCommit); 1113 1114 return STATUS_SUCCESS; 1115 } 1116 1117 VOID NTAPI 1118 RtlpDestroyHeapSegment(PHEAP_SEGMENT Segment) 1119 { 1120 NTSTATUS Status; 1121 PVOID BaseAddress; 1122 SIZE_T Size = 0; 1123 1124 /* Make sure it's not user allocated */ 1125 if (Segment->SegmentFlags & HEAP_USER_ALLOCATED) return; 1126 1127 BaseAddress = Segment->BaseAddress; 1128 DPRINT("Destroying segment %p, BA %p\n", Segment, BaseAddress); 1129 1130 /* Release virtual memory */ 1131 Status = ZwFreeVirtualMemory(NtCurrentProcess(), 1132 &BaseAddress, 1133 &Size, 1134 MEM_RELEASE); 1135 1136 if (!NT_SUCCESS(Status)) 1137 { 1138 DPRINT1("HEAP: Failed to release segment's memory with status 0x%08X\n", Status); 1139 } 1140 } 1141 1142 PHEAP_FREE_ENTRY NTAPI 1143 RtlpCoalesceHeap(PHEAP Heap) 1144 { 1145 UNIMPLEMENTED; 1146 return NULL; 1147 } 1148 1149 PHEAP_FREE_ENTRY NTAPI 1150 RtlpCoalesceFreeBlocks (PHEAP Heap, 1151 PHEAP_FREE_ENTRY FreeEntry, 1152 PSIZE_T FreeSize, 1153 BOOLEAN Remove) 1154 { 1155 PHEAP_FREE_ENTRY CurrentEntry, NextEntry; 1156 UCHAR SegmentOffset; 1157 1158 /* Get the previous entry */ 1159 CurrentEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry - FreeEntry->PreviousSize); 1160 1161 /* Check it */ 1162 if (CurrentEntry != FreeEntry && 1163 !(CurrentEntry->Flags & HEAP_ENTRY_BUSY) && 1164 (*FreeSize + CurrentEntry->Size) <= HEAP_MAX_BLOCK_SIZE) 1165 { 1166 ASSERT(FreeEntry->PreviousSize == CurrentEntry->Size); 1167 1168 /* Remove it if asked for */ 1169 if (Remove) 1170 { 1171 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE); 1172 Heap->TotalFreeSize -= FreeEntry->Size; 1173 1174 /* Remove it only once! */ 1175 Remove = FALSE; 1176 } 1177 1178 /* Remove previous entry too */ 1179 RtlpRemoveFreeBlock(Heap, CurrentEntry, FALSE); 1180 1181 /* Copy flags */ 1182 CurrentEntry->Flags = FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY; 1183 1184 /* Advance FreeEntry and update sizes */ 1185 FreeEntry = CurrentEntry; 1186 *FreeSize = *FreeSize + CurrentEntry->Size; 1187 Heap->TotalFreeSize -= CurrentEntry->Size; 1188 FreeEntry->Size = (USHORT)(*FreeSize); 1189 1190 /* Also update previous size if needed */ 1191 if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) 1192 { 1193 ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize); 1194 } 1195 else 1196 { 1197 SegmentOffset = FreeEntry->SegmentOffset; 1198 ASSERT(SegmentOffset < HEAP_SEGMENTS); 1199 } 1200 } 1201 1202 /* Check the next block if it exists */ 1203 if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) 1204 { 1205 NextEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)FreeEntry + *FreeSize); 1206 1207 if (!(NextEntry->Flags & HEAP_ENTRY_BUSY) && 1208 NextEntry->Size + *FreeSize <= HEAP_MAX_BLOCK_SIZE) 1209 { 1210 ASSERT(*FreeSize == NextEntry->PreviousSize); 1211 1212 /* Remove it if asked for */ 1213 if (Remove) 1214 { 1215 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE); 1216 Heap->TotalFreeSize -= FreeEntry->Size; 1217 } 1218 1219 /* Copy flags */ 1220 FreeEntry->Flags = NextEntry->Flags & HEAP_ENTRY_LAST_ENTRY; 1221 1222 /* Remove next entry now */ 1223 RtlpRemoveFreeBlock(Heap, NextEntry, FALSE); 1224 1225 /* Update sizes */ 1226 *FreeSize = *FreeSize + NextEntry->Size; 1227 Heap->TotalFreeSize -= NextEntry->Size; 1228 FreeEntry->Size = (USHORT)(*FreeSize); 1229 1230 /* Also update previous size if needed */ 1231 if (!(FreeEntry->Flags & HEAP_ENTRY_LAST_ENTRY)) 1232 { 1233 ((PHEAP_ENTRY)FreeEntry + *FreeSize)->PreviousSize = (USHORT)(*FreeSize); 1234 } 1235 else 1236 { 1237 SegmentOffset = FreeEntry->SegmentOffset; 1238 ASSERT(SegmentOffset < HEAP_SEGMENTS); 1239 } 1240 } 1241 } 1242 return FreeEntry; 1243 } 1244 1245 static 1246 PHEAP_FREE_ENTRY 1247 RtlpExtendHeap(PHEAP Heap, 1248 SIZE_T Size) 1249 { 1250 ULONG Pages; 1251 UCHAR Index, EmptyIndex; 1252 SIZE_T FreeSize, CommitSize, ReserveSize; 1253 PHEAP_SEGMENT Segment; 1254 PHEAP_FREE_ENTRY FreeEntry; 1255 NTSTATUS Status; 1256 1257 DPRINT("RtlpExtendHeap(%p %x)\n", Heap, Size); 1258 1259 /* Calculate amount in pages */ 1260 Pages = (ULONG)((Size + PAGE_SIZE - 1) / PAGE_SIZE); 1261 FreeSize = Pages * PAGE_SIZE; 1262 DPRINT("Pages %x, FreeSize %x. Going through segments...\n", Pages, FreeSize); 1263 1264 /* Find an empty segment */ 1265 EmptyIndex = HEAP_SEGMENTS; 1266 for (Index = 0; Index < HEAP_SEGMENTS; Index++) 1267 { 1268 Segment = Heap->Segments[Index]; 1269 1270 if (Segment) DPRINT("Segment[%u] %p with NOUCP %x\n", Index, Segment, Segment->NumberOfUnCommittedPages); 1271 1272 /* Check if its size suits us */ 1273 if (Segment && 1274 Pages <= Segment->NumberOfUnCommittedPages) 1275 { 1276 DPRINT("This segment is suitable\n"); 1277 1278 /* Commit needed amount */ 1279 FreeEntry = RtlpFindAndCommitPages(Heap, Segment, &FreeSize, NULL); 1280 1281 /* Coalesce it with adjacent entries */ 1282 if (FreeEntry) 1283 { 1284 FreeSize = FreeSize >> HEAP_ENTRY_SHIFT; 1285 FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE); 1286 RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize); 1287 return FreeEntry; 1288 } 1289 } 1290 else if (!Segment && 1291 EmptyIndex == HEAP_SEGMENTS) 1292 { 1293 /* Remember the first unused segment index */ 1294 EmptyIndex = Index; 1295 } 1296 } 1297 1298 /* No luck, need to grow the heap */ 1299 if ((Heap->Flags & HEAP_GROWABLE) && 1300 (EmptyIndex != HEAP_SEGMENTS)) 1301 { 1302 Segment = NULL; 1303 1304 /* Reserve the memory */ 1305 if ((Size + PAGE_SIZE) <= Heap->SegmentReserve) 1306 ReserveSize = Heap->SegmentReserve; 1307 else 1308 ReserveSize = Size + PAGE_SIZE; 1309 1310 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 1311 (PVOID)&Segment, 1312 0, 1313 &ReserveSize, 1314 MEM_RESERVE, 1315 PAGE_READWRITE); 1316 1317 /* If it failed, retry again with a half division algorithm */ 1318 while (!NT_SUCCESS(Status) && 1319 ReserveSize != Size + PAGE_SIZE) 1320 { 1321 ReserveSize /= 2; 1322 1323 if (ReserveSize < (Size + PAGE_SIZE)) 1324 ReserveSize = Size + PAGE_SIZE; 1325 1326 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 1327 (PVOID)&Segment, 1328 0, 1329 &ReserveSize, 1330 MEM_RESERVE, 1331 PAGE_READWRITE); 1332 } 1333 1334 /* Proceed only if it's success */ 1335 if (NT_SUCCESS(Status)) 1336 { 1337 Heap->SegmentReserve += ReserveSize; 1338 1339 /* Now commit the memory */ 1340 if ((Size + PAGE_SIZE) <= Heap->SegmentCommit) 1341 CommitSize = Heap->SegmentCommit; 1342 else 1343 CommitSize = Size + PAGE_SIZE; 1344 1345 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 1346 (PVOID)&Segment, 1347 0, 1348 &CommitSize, 1349 MEM_COMMIT, 1350 PAGE_READWRITE); 1351 1352 DPRINT("Committed %lu bytes at base %p\n", CommitSize, Segment); 1353 1354 /* Initialize heap segment if commit was successful */ 1355 if (NT_SUCCESS(Status)) 1356 Status = RtlpInitializeHeapSegment(Heap, Segment, EmptyIndex, 0, ReserveSize, CommitSize); 1357 1358 /* If everything worked - cool */ 1359 if (NT_SUCCESS(Status)) return (PHEAP_FREE_ENTRY)Segment->FirstEntry; 1360 1361 DPRINT1("Committing failed with status 0x%08X\n", Status); 1362 1363 /* Nope, we failed. Free memory */ 1364 ZwFreeVirtualMemory(NtCurrentProcess(), 1365 (PVOID)&Segment, 1366 &ReserveSize, 1367 MEM_RELEASE); 1368 } 1369 else 1370 { 1371 DPRINT1("Reserving failed with status 0x%08X\n", Status); 1372 } 1373 } 1374 1375 if (RtlpGetMode() == UserMode) 1376 { 1377 /* If coalescing on free is disabled in usermode, then do it here */ 1378 if (Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE) 1379 { 1380 FreeEntry = RtlpCoalesceHeap(Heap); 1381 1382 /* If it's a suitable one - return it */ 1383 if (FreeEntry && 1384 FreeEntry->Size >= Size) 1385 { 1386 return FreeEntry; 1387 } 1388 } 1389 } 1390 1391 return NULL; 1392 } 1393 1394 /*********************************************************************** 1395 * RtlCreateHeap 1396 * RETURNS 1397 * Handle of heap: Success 1398 * NULL: Failure 1399 * 1400 * @implemented 1401 */ 1402 HANDLE NTAPI 1403 RtlCreateHeap(ULONG Flags, 1404 PVOID Addr, 1405 SIZE_T TotalSize, 1406 SIZE_T CommitSize, 1407 PVOID Lock, 1408 PRTL_HEAP_PARAMETERS Parameters) 1409 { 1410 PVOID CommittedAddress = NULL, UncommittedAddress = NULL; 1411 PHEAP Heap = NULL; 1412 RTL_HEAP_PARAMETERS SafeParams = {0}; 1413 ULONG_PTR MaximumUserModeAddress; 1414 SYSTEM_BASIC_INFORMATION SystemInformation; 1415 MEMORY_BASIC_INFORMATION MemoryInfo; 1416 ULONG NtGlobalFlags = RtlGetNtGlobalFlags(); 1417 ULONG HeapSegmentFlags = 0; 1418 NTSTATUS Status; 1419 ULONG MaxBlockSize; 1420 1421 /* Check for a special heap */ 1422 if (RtlpPageHeapEnabled && !Addr && !Lock) 1423 { 1424 Heap = RtlpPageHeapCreate(Flags, Addr, TotalSize, CommitSize, Lock, Parameters); 1425 if (Heap) return Heap; 1426 1427 /* Reset a special Parameters == -1 hack */ 1428 if ((ULONG_PTR)Parameters == (ULONG_PTR)-1) 1429 Parameters = NULL; 1430 else 1431 DPRINT1("Enabling page heap failed\n"); 1432 } 1433 1434 /* Check validation flags */ 1435 if (!(Flags & HEAP_SKIP_VALIDATION_CHECKS) && (Flags & ~HEAP_CREATE_VALID_MASK)) 1436 { 1437 DPRINT1("Invalid flags 0x%08x, fixing...\n", Flags); 1438 Flags &= HEAP_CREATE_VALID_MASK; 1439 } 1440 1441 /* Capture parameters */ 1442 if (Parameters) 1443 { 1444 _SEH2_TRY 1445 { 1446 /* If size of structure correct, then copy it */ 1447 if (Parameters->Length == sizeof(RTL_HEAP_PARAMETERS)) 1448 RtlCopyMemory(&SafeParams, Parameters, sizeof(RTL_HEAP_PARAMETERS)); 1449 } 1450 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 1451 { 1452 _SEH2_YIELD(return NULL); 1453 } 1454 _SEH2_END; 1455 } 1456 1457 Parameters = &SafeParams; 1458 1459 /* Check global flags */ 1460 if (NtGlobalFlags & FLG_HEAP_DISABLE_COALESCING) 1461 Flags |= HEAP_DISABLE_COALESCE_ON_FREE; 1462 1463 if (NtGlobalFlags & FLG_HEAP_ENABLE_FREE_CHECK) 1464 Flags |= HEAP_FREE_CHECKING_ENABLED; 1465 1466 if (NtGlobalFlags & FLG_HEAP_ENABLE_TAIL_CHECK) 1467 Flags |= HEAP_TAIL_CHECKING_ENABLED; 1468 1469 if (RtlpGetMode() == UserMode) 1470 { 1471 /* Also check these flags if in usermode */ 1472 if (NtGlobalFlags & FLG_HEAP_VALIDATE_ALL) 1473 Flags |= HEAP_VALIDATE_ALL_ENABLED; 1474 1475 if (NtGlobalFlags & FLG_HEAP_VALIDATE_PARAMETERS) 1476 Flags |= HEAP_VALIDATE_PARAMETERS_ENABLED; 1477 1478 if (NtGlobalFlags & FLG_USER_STACK_TRACE_DB) 1479 Flags |= HEAP_CAPTURE_STACK_BACKTRACES; 1480 } 1481 1482 /* Set tunable parameters */ 1483 RtlpSetHeapParameters(Parameters); 1484 1485 /* Get the max um address */ 1486 Status = ZwQuerySystemInformation(SystemBasicInformation, 1487 &SystemInformation, 1488 sizeof(SystemInformation), 1489 NULL); 1490 1491 if (!NT_SUCCESS(Status)) 1492 { 1493 DPRINT1("Getting max usermode address failed with status 0x%08x\n", Status); 1494 return NULL; 1495 } 1496 1497 MaximumUserModeAddress = SystemInformation.MaximumUserModeAddress; 1498 1499 /* Calculate max alloc size */ 1500 if (!Parameters->MaximumAllocationSize) 1501 Parameters->MaximumAllocationSize = MaximumUserModeAddress - (ULONG_PTR)0x10000 - PAGE_SIZE; 1502 1503 MaxBlockSize = 0x80000 - PAGE_SIZE; 1504 1505 if (!Parameters->VirtualMemoryThreshold || 1506 Parameters->VirtualMemoryThreshold > MaxBlockSize) 1507 { 1508 Parameters->VirtualMemoryThreshold = MaxBlockSize; 1509 } 1510 1511 if (Parameters->DeCommitFreeBlockThreshold != PAGE_SIZE) 1512 { 1513 DPRINT1("WARNING: Ignoring DeCommitFreeBlockThreshold %lx, setting it to PAGE_SIZE.\n", 1514 Parameters->DeCommitFreeBlockThreshold); 1515 Parameters->DeCommitFreeBlockThreshold = PAGE_SIZE; 1516 } 1517 1518 /* Check reserve/commit sizes and set default values */ 1519 if (!CommitSize) 1520 { 1521 CommitSize = PAGE_SIZE; 1522 if (TotalSize) 1523 TotalSize = ROUND_UP(TotalSize, PAGE_SIZE); 1524 else 1525 TotalSize = 64 * PAGE_SIZE; 1526 } 1527 else 1528 { 1529 /* Round up the commit size to be at least the page size */ 1530 CommitSize = ROUND_UP(CommitSize, PAGE_SIZE); 1531 1532 if (TotalSize) 1533 TotalSize = ROUND_UP(TotalSize, PAGE_SIZE); 1534 else 1535 TotalSize = ROUND_UP(CommitSize, 16 * PAGE_SIZE); 1536 } 1537 1538 /* Call special heap */ 1539 if (RtlpHeapIsSpecial(Flags)) 1540 return RtlDebugCreateHeap(Flags, Addr, TotalSize, CommitSize, Lock, Parameters); 1541 1542 /* Without serialization, a lock makes no sense */ 1543 if ((Flags & HEAP_NO_SERIALIZE) && (Lock != NULL)) 1544 return NULL; 1545 1546 /* See if we are already provided with an address for the heap */ 1547 if (Addr) 1548 { 1549 if (Parameters->CommitRoutine) 1550 { 1551 /* There is a commit routine, so no problem here, check params */ 1552 if ((Flags & HEAP_GROWABLE) || 1553 !Parameters->InitialCommit || 1554 !Parameters->InitialReserve || 1555 (Parameters->InitialCommit > Parameters->InitialReserve)) 1556 { 1557 /* Fail */ 1558 return NULL; 1559 } 1560 1561 /* Calculate committed and uncommitted addresses */ 1562 CommittedAddress = Addr; 1563 UncommittedAddress = (PCHAR)Addr + Parameters->InitialCommit; 1564 TotalSize = Parameters->InitialReserve; 1565 1566 /* Zero the initial page ourselves */ 1567 RtlZeroMemory(CommittedAddress, PAGE_SIZE); 1568 } 1569 else 1570 { 1571 /* Commit routine is absent, so query how much memory caller reserved */ 1572 Status = ZwQueryVirtualMemory(NtCurrentProcess(), 1573 Addr, 1574 MemoryBasicInformation, 1575 &MemoryInfo, 1576 sizeof(MemoryInfo), 1577 NULL); 1578 1579 if (!NT_SUCCESS(Status)) 1580 { 1581 DPRINT1("Querying amount of user supplied memory failed with status 0x%08X\n", Status); 1582 return NULL; 1583 } 1584 1585 /* Validate it */ 1586 if (MemoryInfo.BaseAddress != Addr || 1587 MemoryInfo.State == MEM_FREE) 1588 { 1589 return NULL; 1590 } 1591 1592 /* Validation checks passed, set committed/uncommitted addresses */ 1593 CommittedAddress = Addr; 1594 1595 /* Check if it's committed or not */ 1596 if (MemoryInfo.State == MEM_COMMIT) 1597 { 1598 /* Zero it out because it's already committed */ 1599 RtlZeroMemory(CommittedAddress, PAGE_SIZE); 1600 1601 /* Calculate uncommitted address value */ 1602 CommitSize = MemoryInfo.RegionSize; 1603 TotalSize = CommitSize; 1604 UncommittedAddress = (PCHAR)Addr + CommitSize; 1605 1606 /* Check if uncommitted address is reserved */ 1607 Status = ZwQueryVirtualMemory(NtCurrentProcess(), 1608 UncommittedAddress, 1609 MemoryBasicInformation, 1610 &MemoryInfo, 1611 sizeof(MemoryInfo), 1612 NULL); 1613 1614 if (NT_SUCCESS(Status) && 1615 MemoryInfo.State == MEM_RESERVE) 1616 { 1617 /* It is, so add it up to the reserve size */ 1618 TotalSize += MemoryInfo.RegionSize; 1619 } 1620 } 1621 else 1622 { 1623 /* It's not committed, inform following code that a commit is necessary */ 1624 CommitSize = PAGE_SIZE; 1625 UncommittedAddress = Addr; 1626 } 1627 } 1628 1629 /* Mark this as a user-committed mem */ 1630 HeapSegmentFlags = HEAP_USER_ALLOCATED; 1631 Heap = (PHEAP)Addr; 1632 } 1633 else 1634 { 1635 /* Check commit routine */ 1636 if (Parameters->CommitRoutine) return NULL; 1637 1638 /* Reserve memory */ 1639 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 1640 (PVOID *)&Heap, 1641 0, 1642 &TotalSize, 1643 MEM_RESERVE, 1644 PAGE_READWRITE); 1645 1646 if (!NT_SUCCESS(Status)) 1647 { 1648 DPRINT1("Failed to reserve memory with status 0x%08x\n", Status); 1649 return NULL; 1650 } 1651 1652 /* Set base addresses */ 1653 CommittedAddress = Heap; 1654 UncommittedAddress = Heap; 1655 } 1656 1657 /* Check if we need to commit something */ 1658 if (CommittedAddress == UncommittedAddress) 1659 { 1660 /* Commit the required size */ 1661 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 1662 &CommittedAddress, 1663 0, 1664 &CommitSize, 1665 MEM_COMMIT, 1666 PAGE_READWRITE); 1667 1668 DPRINT("Committed %Iu bytes at base %p\n", CommitSize, CommittedAddress); 1669 1670 if (!NT_SUCCESS(Status)) 1671 { 1672 DPRINT1("Failure, Status 0x%08X\n", Status); 1673 1674 /* Release memory if it was reserved */ 1675 if (!Addr) ZwFreeVirtualMemory(NtCurrentProcess(), 1676 (PVOID *)&Heap, 1677 &TotalSize, 1678 MEM_RELEASE); 1679 1680 return NULL; 1681 } 1682 1683 /* Calculate new uncommitted address */ 1684 UncommittedAddress = (PCHAR)UncommittedAddress + CommitSize; 1685 } 1686 1687 /* Initialize the heap */ 1688 Status = RtlpInitializeHeap(Heap, Flags, Lock, Parameters); 1689 if (!NT_SUCCESS(Status)) 1690 { 1691 DPRINT1("Failed to initialize heap (%x)\n", Status); 1692 return NULL; 1693 } 1694 1695 /* Initialize heap's first segment */ 1696 Status = RtlpInitializeHeapSegment(Heap, (PHEAP_SEGMENT) (Heap), 0, HeapSegmentFlags, TotalSize, CommitSize); 1697 if (!NT_SUCCESS(Status)) 1698 { 1699 DPRINT1("Failed to initialize heap segment (%x)\n", Status); 1700 return NULL; 1701 } 1702 1703 DPRINT("Created heap %p, CommitSize %x, ReserveSize %x\n", Heap, CommitSize, TotalSize); 1704 1705 /* Add heap to process list in case of usermode heap */ 1706 if (RtlpGetMode() == UserMode) 1707 { 1708 RtlpAddHeapToProcessList(Heap); 1709 1710 // FIXME: What about lookasides? 1711 } 1712 1713 return Heap; 1714 } 1715 1716 /*********************************************************************** 1717 * RtlDestroyHeap 1718 * RETURNS 1719 * TRUE: Success 1720 * FALSE: Failure 1721 * 1722 * @implemented 1723 * 1724 * RETURNS 1725 * Success: A NULL HANDLE, if heap is NULL or it was destroyed 1726 * Failure: The Heap handle, if heap is the process heap. 1727 */ 1728 HANDLE NTAPI 1729 RtlDestroyHeap(HANDLE HeapPtr) /* [in] Handle of heap */ 1730 { 1731 PHEAP Heap = (PHEAP)HeapPtr; 1732 PLIST_ENTRY Current; 1733 PHEAP_UCR_SEGMENT UcrSegment; 1734 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry; 1735 PVOID BaseAddress; 1736 SIZE_T Size; 1737 LONG i; 1738 PHEAP_SEGMENT Segment; 1739 1740 if (!HeapPtr) return NULL; 1741 1742 /* Call page heap routine if required */ 1743 if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) return RtlpPageHeapDestroy(HeapPtr); 1744 1745 /* Call special heap */ 1746 if (RtlpHeapIsSpecial(Heap->Flags)) 1747 { 1748 if (!RtlDebugDestroyHeap(Heap)) return HeapPtr; 1749 } 1750 1751 /* Check for a process heap */ 1752 if (RtlpGetMode() == UserMode && 1753 HeapPtr == NtCurrentPeb()->ProcessHeap) return HeapPtr; 1754 1755 /* Free up all big allocations */ 1756 Current = Heap->VirtualAllocdBlocks.Flink; 1757 while (Current != &Heap->VirtualAllocdBlocks) 1758 { 1759 VirtualEntry = CONTAINING_RECORD(Current, HEAP_VIRTUAL_ALLOC_ENTRY, Entry); 1760 BaseAddress = (PVOID)VirtualEntry; 1761 Current = Current->Flink; 1762 Size = 0; 1763 ZwFreeVirtualMemory(NtCurrentProcess(), 1764 &BaseAddress, 1765 &Size, 1766 MEM_RELEASE); 1767 } 1768 1769 /* Delete tags and remove heap from the process heaps list in user mode */ 1770 if (RtlpGetMode() == UserMode) 1771 { 1772 // FIXME DestroyTags 1773 RtlpRemoveHeapFromProcessList(Heap); 1774 } 1775 1776 /* Delete the heap lock */ 1777 if (!(Heap->Flags & HEAP_NO_SERIALIZE)) 1778 { 1779 /* Delete it if it wasn't user allocated */ 1780 if (!(Heap->Flags & HEAP_LOCK_USER_ALLOCATED)) 1781 RtlDeleteHeapLock(Heap->LockVariable); 1782 1783 /* Clear out the lock variable */ 1784 Heap->LockVariable = NULL; 1785 } 1786 1787 /* Free UCR segments if any were created */ 1788 Current = Heap->UCRSegments.Flink; 1789 while (Current != &Heap->UCRSegments) 1790 { 1791 UcrSegment = CONTAINING_RECORD(Current, HEAP_UCR_SEGMENT, ListEntry); 1792 1793 /* Advance to the next descriptor */ 1794 Current = Current->Flink; 1795 1796 BaseAddress = (PVOID)UcrSegment; 1797 Size = 0; 1798 1799 /* Release that memory */ 1800 ZwFreeVirtualMemory(NtCurrentProcess(), 1801 &BaseAddress, 1802 &Size, 1803 MEM_RELEASE); 1804 } 1805 1806 /* Go through segments and destroy them */ 1807 for (i = HEAP_SEGMENTS - 1; i >= 0; i--) 1808 { 1809 Segment = Heap->Segments[i]; 1810 if (Segment) RtlpDestroyHeapSegment(Segment); 1811 } 1812 1813 return NULL; 1814 } 1815 1816 PHEAP_ENTRY NTAPI 1817 RtlpSplitEntry(PHEAP Heap, 1818 ULONG Flags, 1819 PHEAP_FREE_ENTRY FreeBlock, 1820 SIZE_T AllocationSize, 1821 SIZE_T Index, 1822 SIZE_T Size) 1823 { 1824 PHEAP_FREE_ENTRY SplitBlock, SplitBlock2; 1825 UCHAR FreeFlags, EntryFlags = HEAP_ENTRY_BUSY; 1826 PHEAP_ENTRY InUseEntry; 1827 SIZE_T FreeSize; 1828 UCHAR SegmentOffset; 1829 1830 /* Add extra flags in case of settable user value feature is requested, 1831 or there is a tag (small or normal) or there is a request to 1832 capture stack backtraces */ 1833 if ((Flags & HEAP_EXTRA_FLAGS_MASK) || 1834 Heap->PseudoTagEntries) 1835 { 1836 /* Add flag which means that the entry will have extra stuff attached */ 1837 EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT; 1838 1839 /* NB! AllocationSize is already adjusted by RtlAllocateHeap */ 1840 } 1841 1842 /* Add settable user flags, if any */ 1843 EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4; 1844 1845 /* Save flags, update total free size */ 1846 FreeFlags = FreeBlock->Flags; 1847 Heap->TotalFreeSize -= FreeBlock->Size; 1848 1849 /* Make this block an in-use one */ 1850 InUseEntry = (PHEAP_ENTRY)FreeBlock; 1851 InUseEntry->Flags = EntryFlags; 1852 InUseEntry->SmallTagIndex = 0; 1853 1854 /* Calculate the extra amount */ 1855 FreeSize = InUseEntry->Size - Index; 1856 1857 /* Update it's size fields (we don't need their data anymore) */ 1858 InUseEntry->Size = (USHORT)Index; 1859 InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size); 1860 1861 /* If there is something to split - do the split */ 1862 if (FreeSize != 0) 1863 { 1864 /* Don't split if resulting entry can't contain any payload data 1865 (i.e. being just HEAP_ENTRY_SIZE) */ 1866 if (FreeSize == 1) 1867 { 1868 /* Increase sizes of the in-use entry */ 1869 InUseEntry->Size++; 1870 InUseEntry->UnusedBytes += sizeof(HEAP_ENTRY); 1871 } 1872 else 1873 { 1874 /* Calculate a pointer to the new entry */ 1875 SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index); 1876 1877 /* Initialize it */ 1878 SplitBlock->Flags = FreeFlags; 1879 SplitBlock->SegmentOffset = InUseEntry->SegmentOffset; 1880 SplitBlock->Size = (USHORT)FreeSize; 1881 SplitBlock->PreviousSize = (USHORT)Index; 1882 1883 /* Check if it's the last entry */ 1884 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) 1885 { 1886 /* Insert it to the free list if it's the last entry */ 1887 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE); 1888 Heap->TotalFreeSize += FreeSize; 1889 } 1890 else 1891 { 1892 /* Not so easy - need to update next's previous size too */ 1893 SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize); 1894 1895 if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) 1896 { 1897 SplitBlock2->PreviousSize = (USHORT)FreeSize; 1898 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE); 1899 Heap->TotalFreeSize += FreeSize; 1900 } 1901 else 1902 { 1903 /* Even more complex - the next entry is free, so we can merge them into one! */ 1904 SplitBlock->Flags = SplitBlock2->Flags; 1905 1906 /* Remove that next entry */ 1907 RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE); 1908 1909 /* Update sizes */ 1910 FreeSize += SplitBlock2->Size; 1911 Heap->TotalFreeSize -= SplitBlock2->Size; 1912 1913 if (FreeSize <= HEAP_MAX_BLOCK_SIZE) 1914 { 1915 /* Insert it back */ 1916 SplitBlock->Size = (USHORT)FreeSize; 1917 1918 /* Don't forget to update previous size of the next entry! */ 1919 if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) 1920 { 1921 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize; 1922 } 1923 1924 /* Actually insert it */ 1925 RtlpInsertFreeBlockHelper(Heap, SplitBlock, (USHORT)FreeSize, FALSE); 1926 1927 /* Update total size */ 1928 Heap->TotalFreeSize += FreeSize; 1929 } 1930 else 1931 { 1932 /* Resulting block is quite big */ 1933 RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize); 1934 } 1935 } 1936 } 1937 1938 /* Reset flags of the free entry */ 1939 FreeFlags = 0; 1940 if (SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY) 1941 { 1942 SegmentOffset = SplitBlock->SegmentOffset; 1943 ASSERT(SegmentOffset < HEAP_SEGMENTS); 1944 } 1945 } 1946 } 1947 1948 /* Set last entry flag */ 1949 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) 1950 InUseEntry->Flags |= HEAP_ENTRY_LAST_ENTRY; 1951 1952 return InUseEntry; 1953 } 1954 1955 static 1956 PVOID 1957 RtlpAllocateNonDedicated(PHEAP Heap, 1958 ULONG Flags, 1959 SIZE_T Size, 1960 SIZE_T AllocationSize, 1961 SIZE_T Index, 1962 BOOLEAN HeapLocked) 1963 { 1964 PHEAP_FREE_ENTRY FreeBlock; 1965 1966 /* The entries in the list must be too small for us */ 1967 ASSERT(IsListEmpty(&Heap->FreeLists) || 1968 (CONTAINING_RECORD(Heap->FreeLists.Blink, HEAP_FREE_ENTRY, FreeList)->Size < Index)); 1969 1970 /* Extend the heap */ 1971 FreeBlock = RtlpExtendHeap(Heap, AllocationSize); 1972 1973 /* Use the new biggest entry we've got */ 1974 if (FreeBlock) 1975 { 1976 PHEAP_ENTRY InUseEntry; 1977 PHEAP_ENTRY_EXTRA Extra; 1978 1979 RtlpRemoveFreeBlock(Heap, FreeBlock, TRUE); 1980 1981 /* Split it */ 1982 InUseEntry = RtlpSplitEntry(Heap, Flags, FreeBlock, AllocationSize, Index, Size); 1983 1984 /* Release the lock */ 1985 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 1986 1987 /* Zero memory if that was requested */ 1988 if (Flags & HEAP_ZERO_MEMORY) 1989 RtlZeroMemory(InUseEntry + 1, Size); 1990 else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) 1991 { 1992 /* Fill this block with a special pattern */ 1993 RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER); 1994 } 1995 1996 /* Fill tail of the block with a special pattern too if requested */ 1997 if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) 1998 { 1999 RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL); 2000 InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN; 2001 } 2002 2003 /* Prepare extra if it's present */ 2004 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 2005 { 2006 Extra = RtlpGetExtraStuffPointer(InUseEntry); 2007 RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA)); 2008 2009 // TODO: Tagging 2010 } 2011 2012 /* Return pointer to the */ 2013 return InUseEntry + 1; 2014 } 2015 2016 /* Really unfortunate, out of memory condition */ 2017 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY); 2018 2019 /* Generate an exception */ 2020 if (Flags & HEAP_GENERATE_EXCEPTIONS) 2021 { 2022 EXCEPTION_RECORD ExceptionRecord; 2023 2024 ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; 2025 ExceptionRecord.ExceptionRecord = NULL; 2026 ExceptionRecord.NumberParameters = 1; 2027 ExceptionRecord.ExceptionFlags = 0; 2028 ExceptionRecord.ExceptionInformation[0] = AllocationSize; 2029 2030 RtlRaiseException(&ExceptionRecord); 2031 } 2032 2033 /* Release the lock */ 2034 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 2035 DPRINT1("HEAP: Allocation failed!\n"); 2036 DPRINT1("Flags %x\n", Heap->Flags); 2037 return NULL; 2038 } 2039 2040 /*********************************************************************** 2041 * HeapAlloc (KERNEL32.334) 2042 * RETURNS 2043 * Pointer to allocated memory block 2044 * NULL: Failure 2045 * 0x7d030f60--invalid flags in RtlHeapAllocate 2046 * @implemented 2047 */ 2048 PVOID NTAPI 2049 RtlAllocateHeap(IN PVOID HeapPtr, 2050 IN ULONG Flags, 2051 IN SIZE_T Size) 2052 { 2053 PHEAP Heap = (PHEAP)HeapPtr; 2054 SIZE_T AllocationSize; 2055 SIZE_T Index; 2056 UCHAR EntryFlags = HEAP_ENTRY_BUSY; 2057 BOOLEAN HeapLocked = FALSE; 2058 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualBlock = NULL; 2059 PHEAP_ENTRY_EXTRA Extra; 2060 NTSTATUS Status; 2061 2062 /* Force flags */ 2063 Flags |= Heap->ForceFlags; 2064 2065 /* Call special heap */ 2066 if (RtlpHeapIsSpecial(Flags)) 2067 return RtlDebugAllocateHeap(Heap, Flags, Size); 2068 2069 /* Check for the maximum size */ 2070 if (Size >= 0x80000000) 2071 { 2072 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY); 2073 DPRINT1("HEAP: Allocation failed!\n"); 2074 return NULL; 2075 } 2076 2077 if (Flags & (HEAP_CREATE_ENABLE_TRACING)) 2078 { 2079 DPRINT1("HEAP: RtlAllocateHeap is called with unsupported flags %x, ignoring\n", Flags); 2080 } 2081 2082 //DPRINT("RtlAllocateHeap(%p %x %x)\n", Heap, Flags, Size); 2083 2084 /* Calculate allocation size and index */ 2085 if (Size) 2086 AllocationSize = Size; 2087 else 2088 AllocationSize = 1; 2089 AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask; 2090 2091 /* Add extra flags in case of settable user value feature is requested, 2092 or there is a tag (small or normal) or there is a request to 2093 capture stack backtraces */ 2094 if ((Flags & HEAP_EXTRA_FLAGS_MASK) || 2095 Heap->PseudoTagEntries) 2096 { 2097 /* Add flag which means that the entry will have extra stuff attached */ 2098 EntryFlags |= HEAP_ENTRY_EXTRA_PRESENT; 2099 2100 /* Account for extra stuff size */ 2101 AllocationSize += sizeof(HEAP_ENTRY_EXTRA); 2102 } 2103 2104 /* Add settable user flags, if any */ 2105 EntryFlags |= (Flags & HEAP_SETTABLE_USER_FLAGS) >> 4; 2106 2107 Index = AllocationSize >> HEAP_ENTRY_SHIFT; 2108 2109 /* Acquire the lock if necessary */ 2110 if (!(Flags & HEAP_NO_SERIALIZE)) 2111 { 2112 RtlEnterHeapLock(Heap->LockVariable, TRUE); 2113 HeapLocked = TRUE; 2114 } 2115 2116 /* Depending on the size, the allocation is going to be done from dedicated, 2117 non-dedicated lists or a virtual block of memory */ 2118 if (Index <= Heap->VirtualMemoryThreshold) 2119 { 2120 PHEAP_ENTRY InUseEntry; 2121 PHEAP_FREE_ENTRY FreeEntry; 2122 2123 /* First quick check: Anybody here ? */ 2124 if (IsListEmpty(&Heap->FreeLists)) 2125 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked); 2126 2127 /* Second quick check: Is there someone for us ? */ 2128 FreeEntry = CONTAINING_RECORD(Heap->FreeLists.Blink, HEAP_FREE_ENTRY, FreeList); 2129 if (FreeEntry->Size < Index) 2130 { 2131 /* Largest entry in the list doesnt fit. */ 2132 return RtlpAllocateNonDedicated(Heap, Flags, Size, AllocationSize, Index, HeapLocked); 2133 } 2134 2135 if (Index > Heap->DeCommitFreeBlockThreshold) 2136 { 2137 /* Find an entry from the non dedicated list */ 2138 FreeEntry = CONTAINING_RECORD(Heap->FreeHints[0], 2139 HEAP_FREE_ENTRY, 2140 FreeList); 2141 2142 while (FreeEntry->Size < Index) 2143 { 2144 /* We made sure we had the right size available */ 2145 ASSERT(FreeEntry->FreeList.Flink != &Heap->FreeLists); 2146 FreeEntry = CONTAINING_RECORD(FreeEntry->FreeList.Flink, 2147 HEAP_FREE_ENTRY, 2148 FreeList); 2149 } 2150 } 2151 else 2152 { 2153 /* Get the free entry from the hint */ 2154 ULONG HintIndex = RtlFindSetBits(&Heap->FreeHintBitmap, 1, Index - 1); 2155 ASSERT(HintIndex != 0xFFFFFFFF); 2156 ASSERT((HintIndex >= (Index - 1)) || (HintIndex == 0)); 2157 FreeEntry = CONTAINING_RECORD(Heap->FreeHints[HintIndex], 2158 HEAP_FREE_ENTRY, 2159 FreeList); 2160 } 2161 2162 /* Remove the free block, split, profit. */ 2163 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE); 2164 InUseEntry = RtlpSplitEntry(Heap, Flags, FreeEntry, AllocationSize, Index, Size); 2165 2166 /* Release the lock */ 2167 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 2168 2169 /* Zero memory if that was requested */ 2170 if (Flags & HEAP_ZERO_MEMORY) 2171 RtlZeroMemory(InUseEntry + 1, Size); 2172 else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) 2173 { 2174 /* Fill this block with a special pattern */ 2175 RtlFillMemoryUlong(InUseEntry + 1, Size & ~0x3, ARENA_INUSE_FILLER); 2176 } 2177 2178 /* Fill tail of the block with a special pattern too if requested */ 2179 if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) 2180 { 2181 RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, sizeof(HEAP_ENTRY), HEAP_TAIL_FILL); 2182 InUseEntry->Flags |= HEAP_ENTRY_FILL_PATTERN; 2183 } 2184 2185 /* Prepare extra if it's present */ 2186 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 2187 { 2188 Extra = RtlpGetExtraStuffPointer(InUseEntry); 2189 RtlZeroMemory(Extra, sizeof(HEAP_ENTRY_EXTRA)); 2190 2191 // TODO: Tagging 2192 } 2193 2194 /* User data starts right after the entry's header */ 2195 return InUseEntry + 1; 2196 } 2197 2198 if (Heap->Flags & HEAP_GROWABLE) 2199 { 2200 /* We've got a very big allocation request, satisfy it by directly allocating virtual memory */ 2201 AllocationSize += sizeof(HEAP_VIRTUAL_ALLOC_ENTRY) - sizeof(HEAP_ENTRY); 2202 2203 Status = ZwAllocateVirtualMemory(NtCurrentProcess(), 2204 (PVOID *)&VirtualBlock, 2205 0, 2206 &AllocationSize, 2207 MEM_COMMIT, 2208 PAGE_READWRITE); 2209 2210 if (!NT_SUCCESS(Status)) 2211 { 2212 // Set STATUS! 2213 /* Release the lock */ 2214 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 2215 DPRINT1("HEAP: Allocation failed!\n"); 2216 return NULL; 2217 } 2218 2219 /* Initialize the newly allocated block */ 2220 VirtualBlock->BusyBlock.Size = (USHORT)(AllocationSize - Size); 2221 ASSERT(VirtualBlock->BusyBlock.Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY)); 2222 VirtualBlock->BusyBlock.Flags = EntryFlags | HEAP_ENTRY_VIRTUAL_ALLOC | HEAP_ENTRY_EXTRA_PRESENT; 2223 VirtualBlock->CommitSize = AllocationSize; 2224 VirtualBlock->ReserveSize = AllocationSize; 2225 2226 /* Insert it into the list of virtual allocations */ 2227 InsertTailList(&Heap->VirtualAllocdBlocks, &VirtualBlock->Entry); 2228 2229 /* Release the lock */ 2230 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 2231 2232 /* Return pointer to user data */ 2233 return VirtualBlock + 1; 2234 } 2235 2236 /* Generate an exception */ 2237 if (Flags & HEAP_GENERATE_EXCEPTIONS) 2238 { 2239 EXCEPTION_RECORD ExceptionRecord; 2240 2241 ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; 2242 ExceptionRecord.ExceptionRecord = NULL; 2243 ExceptionRecord.NumberParameters = 1; 2244 ExceptionRecord.ExceptionFlags = 0; 2245 ExceptionRecord.ExceptionInformation[0] = AllocationSize; 2246 2247 RtlRaiseException(&ExceptionRecord); 2248 } 2249 2250 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_BUFFER_TOO_SMALL); 2251 2252 /* Release the lock */ 2253 if (HeapLocked) RtlLeaveHeapLock(Heap->LockVariable); 2254 DPRINT1("HEAP: Allocation failed!\n"); 2255 return NULL; 2256 } 2257 2258 2259 /*********************************************************************** 2260 * HeapFree (KERNEL32.338) 2261 * RETURNS 2262 * TRUE: Success 2263 * FALSE: Failure 2264 * 2265 * @implemented 2266 */ 2267 BOOLEAN NTAPI RtlFreeHeap( 2268 HANDLE HeapPtr, /* [in] Handle of heap */ 2269 ULONG Flags, /* [in] Heap freeing flags */ 2270 PVOID Ptr /* [in] Address of memory to free */ 2271 ) 2272 { 2273 PHEAP Heap; 2274 PHEAP_ENTRY HeapEntry; 2275 USHORT TagIndex = 0; 2276 SIZE_T BlockSize; 2277 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry; 2278 BOOLEAN Locked = FALSE; 2279 NTSTATUS Status; 2280 2281 /* Freeing NULL pointer is a legal operation */ 2282 if (!Ptr) return TRUE; 2283 2284 /* Get pointer to the heap and force flags */ 2285 Heap = (PHEAP)HeapPtr; 2286 Flags |= Heap->ForceFlags; 2287 2288 /* Call special heap */ 2289 if (RtlpHeapIsSpecial(Flags)) 2290 return RtlDebugFreeHeap(Heap, Flags, Ptr); 2291 2292 /* Get pointer to the heap entry */ 2293 HeapEntry = (PHEAP_ENTRY)Ptr - 1; 2294 2295 /* Protect with SEH in case the pointer is not valid */ 2296 _SEH2_TRY 2297 { 2298 /* Check this entry, fail if it's invalid */ 2299 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY) || 2300 (((ULONG_PTR)Ptr & 0x7) != 0) || 2301 (HeapEntry->SegmentOffset >= HEAP_SEGMENTS)) 2302 { 2303 /* This is an invalid block */ 2304 DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr); 2305 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 2306 _SEH2_YIELD(return FALSE); 2307 } 2308 } 2309 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 2310 { 2311 /* The pointer was invalid */ 2312 DPRINT1("HEAP: Trying to free an invalid address %p!\n", Ptr); 2313 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 2314 _SEH2_YIELD(return FALSE); 2315 } 2316 _SEH2_END; 2317 2318 /* Lock if necessary */ 2319 if (!(Flags & HEAP_NO_SERIALIZE)) 2320 { 2321 RtlEnterHeapLock(Heap->LockVariable, TRUE); 2322 Locked = TRUE; 2323 } 2324 2325 if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 2326 { 2327 /* Big allocation */ 2328 VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock); 2329 2330 /* Remove it from the list */ 2331 RemoveEntryList(&VirtualEntry->Entry); 2332 2333 // TODO: Tagging 2334 2335 BlockSize = 0; 2336 Status = ZwFreeVirtualMemory(NtCurrentProcess(), 2337 (PVOID *)&VirtualEntry, 2338 &BlockSize, 2339 MEM_RELEASE); 2340 2341 if (!NT_SUCCESS(Status)) 2342 { 2343 DPRINT1("HEAP: Failed releasing memory with Status 0x%08X. Heap %p, ptr %p, base address %p\n", 2344 Status, Heap, Ptr, VirtualEntry); 2345 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(Status); 2346 } 2347 } 2348 else 2349 { 2350 /* Normal allocation */ 2351 BlockSize = HeapEntry->Size; 2352 2353 // TODO: Tagging 2354 2355 /* Coalesce in kernel mode, and in usermode if it's not disabled */ 2356 if (RtlpGetMode() == KernelMode || 2357 (RtlpGetMode() == UserMode && !(Heap->Flags & HEAP_DISABLE_COALESCE_ON_FREE))) 2358 { 2359 HeapEntry = (PHEAP_ENTRY)RtlpCoalesceFreeBlocks(Heap, 2360 (PHEAP_FREE_ENTRY)HeapEntry, 2361 &BlockSize, 2362 FALSE); 2363 } 2364 2365 /* See if we should decommit this block */ 2366 if ((BlockSize >= Heap->DeCommitFreeBlockThreshold) || 2367 (Heap->TotalFreeSize + BlockSize >= Heap->DeCommitTotalFreeThreshold)) 2368 { 2369 RtlpDeCommitFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); 2370 } 2371 else 2372 { 2373 /* Insert into the free list */ 2374 RtlpInsertFreeBlock(Heap, (PHEAP_FREE_ENTRY)HeapEntry, BlockSize); 2375 2376 if (RtlpGetMode() == UserMode && 2377 TagIndex != 0) 2378 { 2379 // FIXME: Tagging 2380 UNIMPLEMENTED; 2381 } 2382 } 2383 } 2384 2385 /* Release the heap lock */ 2386 if (Locked) RtlLeaveHeapLock(Heap->LockVariable); 2387 2388 return TRUE; 2389 } 2390 2391 BOOLEAN NTAPI 2392 RtlpGrowBlockInPlace (IN PHEAP Heap, 2393 IN ULONG Flags, 2394 IN PHEAP_ENTRY InUseEntry, 2395 IN SIZE_T Size, 2396 IN SIZE_T Index) 2397 { 2398 UCHAR EntryFlags, RememberFlags; 2399 PHEAP_FREE_ENTRY FreeEntry, UnusedEntry, FollowingEntry; 2400 SIZE_T FreeSize, PrevSize, TailPart, AddedSize = 0; 2401 PHEAP_ENTRY_EXTRA OldExtra, NewExtra; 2402 UCHAR SegmentOffset; 2403 2404 /* We can't grow beyond specified threshold */ 2405 if (Index > Heap->VirtualMemoryThreshold) 2406 return FALSE; 2407 2408 /* Get entry flags */ 2409 EntryFlags = InUseEntry->Flags; 2410 2411 if (RtlpIsLastCommittedEntry(InUseEntry)) 2412 { 2413 /* There is no next block, just uncommitted space. Calculate how much is needed */ 2414 FreeSize = (Index - InUseEntry->Size) << HEAP_ENTRY_SHIFT; 2415 FreeSize = ROUND_UP(FreeSize, PAGE_SIZE); 2416 2417 /* Find and commit those pages */ 2418 FreeEntry = RtlpFindAndCommitPages(Heap, 2419 Heap->Segments[InUseEntry->SegmentOffset], 2420 &FreeSize, 2421 (PVOID)PAGE_ROUND_UP(InUseEntry + InUseEntry->Size)); 2422 2423 /* Fail if it failed... */ 2424 if (!FreeEntry) return FALSE; 2425 2426 /* It was successful, perform coalescing */ 2427 FreeSize = FreeSize >> HEAP_ENTRY_SHIFT; 2428 FreeEntry = RtlpCoalesceFreeBlocks(Heap, FreeEntry, &FreeSize, FALSE); 2429 2430 /* Check if it's enough */ 2431 if (FreeSize + InUseEntry->Size < Index) 2432 { 2433 /* Still not enough */ 2434 RtlpInsertFreeBlock(Heap, FreeEntry, FreeSize); 2435 Heap->TotalFreeSize += FreeSize; 2436 return FALSE; 2437 } 2438 2439 /* Remember flags of this free entry */ 2440 RememberFlags = FreeEntry->Flags; 2441 2442 /* Sum up sizes */ 2443 FreeSize += InUseEntry->Size; 2444 } 2445 else 2446 { 2447 FreeEntry = (PHEAP_FREE_ENTRY)(InUseEntry + InUseEntry->Size); 2448 2449 /* The next block indeed exists. Check if it's free or in use */ 2450 if (FreeEntry->Flags & HEAP_ENTRY_BUSY) return FALSE; 2451 2452 /* Next entry is free, check if it can fit the block we need */ 2453 FreeSize = InUseEntry->Size + FreeEntry->Size; 2454 if (FreeSize < Index) return FALSE; 2455 2456 /* Remember flags of this free entry */ 2457 RememberFlags = FreeEntry->Flags; 2458 2459 /* Remove this block from the free list */ 2460 RtlpRemoveFreeBlock(Heap, FreeEntry, FALSE); 2461 Heap->TotalFreeSize -= FreeEntry->Size; 2462 } 2463 2464 PrevSize = (InUseEntry->Size << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes; 2465 FreeSize -= Index; 2466 2467 /* Don't produce too small blocks */ 2468 if (FreeSize <= 2) 2469 { 2470 Index += FreeSize; 2471 FreeSize = 0; 2472 } 2473 2474 /* Process extra stuff */ 2475 if (EntryFlags & HEAP_ENTRY_EXTRA_PRESENT) 2476 { 2477 /* Calculate pointers */ 2478 OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1); 2479 NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1); 2480 2481 /* Copy contents */ 2482 *NewExtra = *OldExtra; 2483 2484 // FIXME Tagging 2485 } 2486 2487 /* Update sizes */ 2488 InUseEntry->Size = (USHORT)Index; 2489 InUseEntry->UnusedBytes = (UCHAR)((Index << HEAP_ENTRY_SHIFT) - Size); 2490 2491 /* Check if there is a free space remaining after merging those blocks */ 2492 if (!FreeSize) 2493 { 2494 /* Update flags and sizes */ 2495 InUseEntry->Flags |= RememberFlags & HEAP_ENTRY_LAST_ENTRY; 2496 2497 /* Either update previous size of the next entry or mark it as a last 2498 entry in the segment */ 2499 if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY)) 2500 { 2501 (InUseEntry + InUseEntry->Size)->PreviousSize = InUseEntry->Size; 2502 } 2503 else 2504 { 2505 SegmentOffset = InUseEntry->SegmentOffset; 2506 ASSERT(SegmentOffset < HEAP_SEGMENTS); 2507 } 2508 } 2509 else 2510 { 2511 /* Complex case, we need to split the block to give unused free space 2512 back to the heap */ 2513 UnusedEntry = (PHEAP_FREE_ENTRY)(InUseEntry + Index); 2514 UnusedEntry->PreviousSize = (USHORT)Index; 2515 UnusedEntry->SegmentOffset = InUseEntry->SegmentOffset; 2516 2517 /* Update the following block or set the last entry in the segment */ 2518 if (RememberFlags & HEAP_ENTRY_LAST_ENTRY) 2519 { 2520 SegmentOffset = UnusedEntry->SegmentOffset; 2521 ASSERT(SegmentOffset < HEAP_SEGMENTS); 2522 2523 /* Set flags and size */ 2524 UnusedEntry->Flags = RememberFlags; 2525 UnusedEntry->Size = (USHORT)FreeSize; 2526 2527 /* Insert it to the heap and update total size */ 2528 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE); 2529 Heap->TotalFreeSize += FreeSize; 2530 } 2531 else 2532 { 2533 /* There is a block after this one */ 2534 FollowingEntry = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)UnusedEntry + FreeSize); 2535 2536 if (FollowingEntry->Flags & HEAP_ENTRY_BUSY) 2537 { 2538 /* Update flags and set size of the unused space entry */ 2539 UnusedEntry->Flags = RememberFlags & (~HEAP_ENTRY_LAST_ENTRY); 2540 UnusedEntry->Size = (USHORT)FreeSize; 2541 2542 /* Update previous size of the following entry */ 2543 FollowingEntry->PreviousSize = (USHORT)FreeSize; 2544 2545 /* Insert it to the heap and update total free size */ 2546 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE); 2547 Heap->TotalFreeSize += FreeSize; 2548 } 2549 else 2550 { 2551 /* That following entry is also free, what a fortune! */ 2552 RememberFlags = FollowingEntry->Flags; 2553 2554 /* Remove it */ 2555 RtlpRemoveFreeBlock(Heap, FollowingEntry, FALSE); 2556 Heap->TotalFreeSize -= FollowingEntry->Size; 2557 2558 /* And make up a new combined block */ 2559 FreeSize += FollowingEntry->Size; 2560 UnusedEntry->Flags = RememberFlags; 2561 2562 /* Check where to put it */ 2563 if (FreeSize <= HEAP_MAX_BLOCK_SIZE) 2564 { 2565 /* Fine for a dedicated list */ 2566 UnusedEntry->Size = (USHORT)FreeSize; 2567 2568 if (!(RememberFlags & HEAP_ENTRY_LAST_ENTRY)) 2569 { 2570 ((PHEAP_ENTRY)UnusedEntry + FreeSize)->PreviousSize = (USHORT)FreeSize; 2571 } 2572 else 2573 { 2574 SegmentOffset = UnusedEntry->SegmentOffset; 2575 ASSERT(SegmentOffset < HEAP_SEGMENTS); 2576 } 2577 2578 /* Insert it back and update total size */ 2579 RtlpInsertFreeBlockHelper(Heap, UnusedEntry, FreeSize, FALSE); 2580 Heap->TotalFreeSize += FreeSize; 2581 } 2582 else 2583 { 2584 /* The block is very large, leave all the hassle to the insertion routine */ 2585 RtlpInsertFreeBlock(Heap, UnusedEntry, FreeSize); 2586 } 2587 } 2588 } 2589 } 2590 2591 /* Properly "zero out" (and fill!) the space */ 2592 if (Flags & HEAP_ZERO_MEMORY) 2593 { 2594 RtlZeroMemory((PCHAR)(InUseEntry + 1) + PrevSize, Size - PrevSize); 2595 } 2596 else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) 2597 { 2598 /* Calculate tail part which we need to fill */ 2599 TailPart = PrevSize & (sizeof(ULONG) - 1); 2600 2601 /* "Invert" it as usual */ 2602 if (TailPart) TailPart = 4 - TailPart; 2603 2604 if (Size > (PrevSize + TailPart)) 2605 AddedSize = (Size - (PrevSize + TailPart)) & ~(sizeof(ULONG) - 1); 2606 2607 if (AddedSize) 2608 { 2609 RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + PrevSize + TailPart, 2610 AddedSize, 2611 ARENA_INUSE_FILLER); 2612 } 2613 } 2614 2615 /* Fill the new tail */ 2616 if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) 2617 { 2618 RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, 2619 HEAP_ENTRY_SIZE, 2620 HEAP_TAIL_FILL); 2621 } 2622 2623 /* Copy user settable flags */ 2624 InUseEntry->Flags &= ~HEAP_ENTRY_SETTABLE_FLAGS; 2625 InUseEntry->Flags |= ((Flags & HEAP_SETTABLE_USER_FLAGS) >> 4); 2626 2627 /* Return success */ 2628 return TRUE; 2629 } 2630 2631 PHEAP_ENTRY_EXTRA NTAPI 2632 RtlpGetExtraStuffPointer(PHEAP_ENTRY HeapEntry) 2633 { 2634 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualEntry; 2635 2636 /* Check if it's a big block */ 2637 if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 2638 { 2639 VirtualEntry = CONTAINING_RECORD(HeapEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock); 2640 2641 /* Return a pointer to the extra stuff*/ 2642 return &VirtualEntry->ExtraStuff; 2643 } 2644 else 2645 { 2646 /* This is a usual entry, which means extra stuff follows this block */ 2647 return (PHEAP_ENTRY_EXTRA)(HeapEntry + HeapEntry->Size - 1); 2648 } 2649 } 2650 2651 2652 /*********************************************************************** 2653 * RtlReAllocateHeap 2654 * PARAMS 2655 * Heap [in] Handle of heap block 2656 * Flags [in] Heap reallocation flags 2657 * Ptr, [in] Address of memory to reallocate 2658 * Size [in] Number of bytes to reallocate 2659 * 2660 * RETURNS 2661 * Pointer to reallocated memory block 2662 * NULL: Failure 2663 * 0x7d030f60--invalid flags in RtlHeapAllocate 2664 * @implemented 2665 */ 2666 PVOID NTAPI 2667 RtlReAllocateHeap(HANDLE HeapPtr, 2668 ULONG Flags, 2669 PVOID Ptr, 2670 SIZE_T Size) 2671 { 2672 PHEAP Heap = (PHEAP)HeapPtr; 2673 PHEAP_ENTRY InUseEntry, NewInUseEntry; 2674 PHEAP_ENTRY_EXTRA OldExtra, NewExtra; 2675 SIZE_T AllocationSize, FreeSize, DecommitSize; 2676 BOOLEAN HeapLocked = FALSE; 2677 PVOID NewBaseAddress; 2678 PHEAP_FREE_ENTRY SplitBlock, SplitBlock2; 2679 SIZE_T OldSize, Index, OldIndex; 2680 UCHAR FreeFlags; 2681 NTSTATUS Status; 2682 PVOID DecommitBase; 2683 SIZE_T RemainderBytes, ExtraSize; 2684 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock; 2685 EXCEPTION_RECORD ExceptionRecord; 2686 UCHAR SegmentOffset; 2687 2688 /* Return success in case of a null pointer */ 2689 if (!Ptr) 2690 { 2691 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_SUCCESS); 2692 return NULL; 2693 } 2694 2695 /* Force heap flags */ 2696 Flags |= Heap->ForceFlags; 2697 2698 /* Call special heap */ 2699 if (RtlpHeapIsSpecial(Flags)) 2700 return RtlDebugReAllocateHeap(Heap, Flags, Ptr, Size); 2701 2702 /* Make sure size is valid */ 2703 if (Size >= 0x80000000) 2704 { 2705 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY); 2706 return NULL; 2707 } 2708 2709 /* Calculate allocation size and index */ 2710 if (Size) 2711 AllocationSize = Size; 2712 else 2713 AllocationSize = 1; 2714 AllocationSize = (AllocationSize + Heap->AlignRound) & Heap->AlignMask; 2715 2716 /* Add up extra stuff, if it is present anywhere */ 2717 if (((((PHEAP_ENTRY)Ptr)-1)->Flags & HEAP_ENTRY_EXTRA_PRESENT) || 2718 (Flags & HEAP_EXTRA_FLAGS_MASK) || 2719 Heap->PseudoTagEntries) 2720 { 2721 AllocationSize += sizeof(HEAP_ENTRY_EXTRA); 2722 } 2723 2724 /* Acquire the lock if necessary */ 2725 if (!(Flags & HEAP_NO_SERIALIZE)) 2726 { 2727 RtlEnterHeapLock(Heap->LockVariable, TRUE); 2728 HeapLocked = TRUE; 2729 /* Do not acquire the lock anymore for re-entrant call */ 2730 Flags |= HEAP_NO_SERIALIZE; 2731 } 2732 2733 /* Get the pointer to the in-use entry */ 2734 InUseEntry = (PHEAP_ENTRY)Ptr - 1; 2735 2736 /* If that entry is not really in-use, we have a problem */ 2737 if (!(InUseEntry->Flags & HEAP_ENTRY_BUSY)) 2738 { 2739 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 2740 2741 /* Release the lock and return */ 2742 if (HeapLocked) 2743 RtlLeaveHeapLock(Heap->LockVariable); 2744 return Ptr; 2745 } 2746 2747 if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 2748 { 2749 /* This is a virtually allocated block. Get its size */ 2750 OldSize = RtlpGetSizeOfBigBlock(InUseEntry); 2751 2752 /* Convert it to an index */ 2753 OldIndex = (OldSize + InUseEntry->Size) >> HEAP_ENTRY_SHIFT; 2754 2755 /* Calculate new allocation size and round it to the page size */ 2756 AllocationSize += FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock); 2757 AllocationSize = ROUND_UP(AllocationSize, PAGE_SIZE); 2758 } 2759 else 2760 { 2761 /* Usual entry */ 2762 OldIndex = InUseEntry->Size; 2763 2764 OldSize = (OldIndex << HEAP_ENTRY_SHIFT) - InUseEntry->UnusedBytes; 2765 } 2766 2767 /* Calculate new index */ 2768 Index = AllocationSize >> HEAP_ENTRY_SHIFT; 2769 2770 /* Check for 4 different scenarios (old size, new size, old index, new index) */ 2771 if (Index <= OldIndex) 2772 { 2773 /* Difference must be greater than 1, adjust if it's not so */ 2774 if (Index + 1 == OldIndex) 2775 { 2776 Index++; 2777 AllocationSize += sizeof(HEAP_ENTRY); 2778 } 2779 2780 /* Calculate new size */ 2781 if (InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 2782 { 2783 /* Simple in case of a virtual alloc - just an unused size */ 2784 InUseEntry->Size = (USHORT)(AllocationSize - Size); 2785 ASSERT(InUseEntry->Size >= sizeof(HEAP_VIRTUAL_ALLOC_ENTRY)); 2786 } 2787 else if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 2788 { 2789 /* There is extra stuff, take it into account */ 2790 OldExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + InUseEntry->Size - 1); 2791 NewExtra = (PHEAP_ENTRY_EXTRA)(InUseEntry + Index - 1); 2792 *NewExtra = *OldExtra; 2793 2794 // FIXME Tagging, TagIndex 2795 2796 /* Update unused bytes count */ 2797 InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size); 2798 } 2799 else 2800 { 2801 // FIXME Tagging, SmallTagIndex 2802 InUseEntry->UnusedBytes = (UCHAR)(AllocationSize - Size); 2803 } 2804 2805 /* If new size is bigger than the old size */ 2806 if (Size > OldSize) 2807 { 2808 /* Zero out that additional space if required */ 2809 if (Flags & HEAP_ZERO_MEMORY) 2810 { 2811 RtlZeroMemory((PCHAR)Ptr + OldSize, Size - OldSize); 2812 } 2813 else if (Heap->Flags & HEAP_FREE_CHECKING_ENABLED) 2814 { 2815 /* Fill it on free if required */ 2816 RemainderBytes = OldSize & (sizeof(ULONG) - 1); 2817 2818 if (RemainderBytes) 2819 RemainderBytes = 4 - RemainderBytes; 2820 2821 if (Size > (OldSize + RemainderBytes)) 2822 { 2823 /* Calculate actual amount of extra bytes to fill */ 2824 ExtraSize = (Size - (OldSize + RemainderBytes)) & ~(sizeof(ULONG) - 1); 2825 2826 /* Fill them if there are any */ 2827 if (ExtraSize != 0) 2828 { 2829 RtlFillMemoryUlong((PCHAR)(InUseEntry + 1) + OldSize + RemainderBytes, 2830 ExtraSize, 2831 ARENA_INUSE_FILLER); 2832 } 2833 } 2834 } 2835 } 2836 2837 /* Fill tail of the heap entry if required */ 2838 if (Heap->Flags & HEAP_TAIL_CHECKING_ENABLED) 2839 { 2840 RtlFillMemory((PCHAR)(InUseEntry + 1) + Size, 2841 HEAP_ENTRY_SIZE, 2842 HEAP_TAIL_FILL); 2843 } 2844 2845 /* Check if the difference is significant or not */ 2846 if (Index != OldIndex) 2847 { 2848 /* Save flags */ 2849 FreeFlags = InUseEntry->Flags & ~HEAP_ENTRY_BUSY; 2850 2851 if (FreeFlags & HEAP_ENTRY_VIRTUAL_ALLOC) 2852 { 2853 /* This is a virtual block allocation */ 2854 VirtualAllocBlock = CONTAINING_RECORD(InUseEntry, HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock); 2855 2856 // FIXME Tagging! 2857 2858 DecommitBase = (PCHAR)VirtualAllocBlock + AllocationSize; 2859 DecommitSize = (OldIndex << HEAP_ENTRY_SHIFT) - AllocationSize; 2860 2861 /* Release the memory */ 2862 Status = ZwFreeVirtualMemory(NtCurrentProcess(), 2863 (PVOID *)&DecommitBase, 2864 &DecommitSize, 2865 MEM_RELEASE); 2866 2867 if (!NT_SUCCESS(Status)) 2868 { 2869 DPRINT1("HEAP: Unable to release memory (pointer %p, size 0x%x), Status %08x\n", DecommitBase, DecommitSize, Status); 2870 } 2871 else 2872 { 2873 /* Otherwise reduce the commit size */ 2874 VirtualAllocBlock->CommitSize -= DecommitSize; 2875 } 2876 } 2877 else 2878 { 2879 /* Reduce size of the block and possibly split it */ 2880 SplitBlock = (PHEAP_FREE_ENTRY)(InUseEntry + Index); 2881 2882 /* Initialize this entry */ 2883 SplitBlock->Flags = FreeFlags; 2884 SplitBlock->PreviousSize = (USHORT)Index; 2885 SplitBlock->SegmentOffset = InUseEntry->SegmentOffset; 2886 2887 /* Remember free size */ 2888 FreeSize = InUseEntry->Size - Index; 2889 2890 /* Set new size */ 2891 InUseEntry->Size = (USHORT)Index; 2892 InUseEntry->Flags &= ~HEAP_ENTRY_LAST_ENTRY; 2893 2894 /* Is that the last entry */ 2895 if (FreeFlags & HEAP_ENTRY_LAST_ENTRY) 2896 { 2897 SegmentOffset = SplitBlock->SegmentOffset; 2898 ASSERT(SegmentOffset < HEAP_SEGMENTS); 2899 2900 /* Set its size and insert it to the list */ 2901 SplitBlock->Size = (USHORT)FreeSize; 2902 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE); 2903 2904 /* Update total free size */ 2905 Heap->TotalFreeSize += FreeSize; 2906 } 2907 else 2908 { 2909 /* Get the block after that one */ 2910 SplitBlock2 = (PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize); 2911 2912 if (SplitBlock2->Flags & HEAP_ENTRY_BUSY) 2913 { 2914 /* It's in use, add it here*/ 2915 SplitBlock->Size = (USHORT)FreeSize; 2916 2917 /* Update previous size of the next entry */ 2918 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize; 2919 2920 /* Insert it to the list */ 2921 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE); 2922 2923 /* Update total size */ 2924 Heap->TotalFreeSize += FreeSize; 2925 } 2926 else 2927 { 2928 /* Next entry is free, so merge with it */ 2929 SplitBlock->Flags = SplitBlock2->Flags; 2930 2931 /* Remove it, update total size */ 2932 RtlpRemoveFreeBlock(Heap, SplitBlock2, FALSE); 2933 Heap->TotalFreeSize -= SplitBlock2->Size; 2934 2935 /* Calculate total free size */ 2936 FreeSize += SplitBlock2->Size; 2937 2938 if (FreeSize <= HEAP_MAX_BLOCK_SIZE) 2939 { 2940 SplitBlock->Size = (USHORT)FreeSize; 2941 2942 if (!(SplitBlock->Flags & HEAP_ENTRY_LAST_ENTRY)) 2943 { 2944 /* Update previous size of the next entry */ 2945 ((PHEAP_FREE_ENTRY)((PHEAP_ENTRY)SplitBlock + FreeSize))->PreviousSize = (USHORT)FreeSize; 2946 } 2947 else 2948 { 2949 SegmentOffset = SplitBlock->SegmentOffset; 2950 ASSERT(SegmentOffset < HEAP_SEGMENTS); 2951 } 2952 2953 /* Insert the new one back and update total size */ 2954 RtlpInsertFreeBlockHelper(Heap, SplitBlock, FreeSize, FALSE); 2955 Heap->TotalFreeSize += FreeSize; 2956 } 2957 else 2958 { 2959 /* Just add it */ 2960 RtlpInsertFreeBlock(Heap, SplitBlock, FreeSize); 2961 } 2962 } 2963 } 2964 } 2965 } 2966 } 2967 else 2968 { 2969 /* We're growing the block */ 2970 if ((InUseEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) || 2971 !RtlpGrowBlockInPlace(Heap, Flags, InUseEntry, Size, Index)) 2972 { 2973 /* Growing in place failed, so growing out of place */ 2974 if (Flags & HEAP_REALLOC_IN_PLACE_ONLY) 2975 { 2976 DPRINT1("Realloc in place failed, but it was the only option\n"); 2977 Ptr = NULL; 2978 } 2979 else 2980 { 2981 /* Clear tag bits */ 2982 Flags &= ~HEAP_TAG_MASK; 2983 2984 /* Process extra stuff */ 2985 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 2986 { 2987 /* Preserve user settable flags */ 2988 Flags &= ~HEAP_SETTABLE_USER_FLAGS; 2989 2990 Flags |= HEAP_SETTABLE_USER_VALUE | ((InUseEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4); 2991 2992 /* Get pointer to the old extra data */ 2993 OldExtra = RtlpGetExtraStuffPointer(InUseEntry); 2994 2995 /* Save tag index if it was set */ 2996 if (OldExtra->TagIndex && 2997 !(OldExtra->TagIndex & HEAP_PSEUDO_TAG_FLAG)) 2998 { 2999 Flags |= OldExtra->TagIndex << HEAP_TAG_SHIFT; 3000 } 3001 } 3002 else if (InUseEntry->SmallTagIndex) 3003 { 3004 /* Take small tag index into account */ 3005 Flags |= InUseEntry->SmallTagIndex << HEAP_TAG_SHIFT; 3006 } 3007 3008 /* Allocate new block from the heap */ 3009 NewBaseAddress = RtlAllocateHeap(HeapPtr, 3010 Flags & ~HEAP_ZERO_MEMORY, 3011 Size); 3012 3013 /* Proceed if it didn't fail */ 3014 if (NewBaseAddress) 3015 { 3016 /* Get new entry pointer */ 3017 NewInUseEntry = (PHEAP_ENTRY)NewBaseAddress - 1; 3018 3019 /* Process extra stuff if it exists */ 3020 if (NewInUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 3021 { 3022 NewExtra = RtlpGetExtraStuffPointer(NewInUseEntry); 3023 3024 if (InUseEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 3025 { 3026 OldExtra = RtlpGetExtraStuffPointer(InUseEntry); 3027 NewExtra->Settable = OldExtra->Settable; 3028 } 3029 else 3030 { 3031 RtlZeroMemory(NewExtra, sizeof(*NewExtra)); 3032 } 3033 } 3034 3035 /* Copy actual user bits */ 3036 if (Size < OldSize) 3037 RtlMoveMemory(NewBaseAddress, Ptr, Size); 3038 else 3039 RtlMoveMemory(NewBaseAddress, Ptr, OldSize); 3040 3041 /* Zero remaining part if required */ 3042 if (Size > OldSize && 3043 (Flags & HEAP_ZERO_MEMORY)) 3044 { 3045 RtlZeroMemory((PCHAR)NewBaseAddress + OldSize, Size - OldSize); 3046 } 3047 3048 /* Free the old block */ 3049 RtlFreeHeap(HeapPtr, Flags, Ptr); 3050 } 3051 3052 Ptr = NewBaseAddress; 3053 } 3054 } 3055 } 3056 3057 /* Did resizing fail? */ 3058 if (!Ptr && (Flags & HEAP_GENERATE_EXCEPTIONS)) 3059 { 3060 /* Generate an exception if required */ 3061 ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; 3062 ExceptionRecord.ExceptionRecord = NULL; 3063 ExceptionRecord.NumberParameters = 1; 3064 ExceptionRecord.ExceptionFlags = 0; 3065 ExceptionRecord.ExceptionInformation[0] = AllocationSize; 3066 3067 RtlRaiseException(&ExceptionRecord); 3068 } 3069 3070 /* Release the heap lock if it was acquired */ 3071 if (HeapLocked) 3072 RtlLeaveHeapLock(Heap->LockVariable); 3073 3074 return Ptr; 3075 } 3076 3077 3078 /*********************************************************************** 3079 * RtlCompactHeap 3080 * 3081 * @unimplemented 3082 */ 3083 ULONG NTAPI 3084 RtlCompactHeap(HANDLE Heap, 3085 ULONG Flags) 3086 { 3087 UNIMPLEMENTED; 3088 return 0; 3089 } 3090 3091 3092 /*********************************************************************** 3093 * RtlLockHeap 3094 * Attempts to acquire the critical section object for a specified heap. 3095 * 3096 * PARAMS 3097 * Heap [in] Handle of heap to lock for exclusive access 3098 * 3099 * RETURNS 3100 * TRUE: Success 3101 * FALSE: Failure 3102 * 3103 * @implemented 3104 */ 3105 BOOLEAN NTAPI 3106 RtlLockHeap(IN HANDLE HeapPtr) 3107 { 3108 PHEAP Heap = (PHEAP)HeapPtr; 3109 3110 /* Check for page heap */ 3111 if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) 3112 { 3113 return RtlpPageHeapLock(Heap); 3114 } 3115 3116 /* Check if it's really a heap */ 3117 if (Heap->Signature != HEAP_SIGNATURE) return FALSE; 3118 3119 /* Lock if it's lockable */ 3120 if (!(Heap->Flags & HEAP_NO_SERIALIZE)) 3121 { 3122 RtlEnterHeapLock(Heap->LockVariable, TRUE); 3123 } 3124 3125 return TRUE; 3126 } 3127 3128 3129 /*********************************************************************** 3130 * RtlUnlockHeap 3131 * Releases ownership of the critical section object. 3132 * 3133 * PARAMS 3134 * Heap [in] Handle to the heap to unlock 3135 * 3136 * RETURNS 3137 * TRUE: Success 3138 * FALSE: Failure 3139 * 3140 * @implemented 3141 */ 3142 BOOLEAN NTAPI 3143 RtlUnlockHeap(HANDLE HeapPtr) 3144 { 3145 PHEAP Heap = (PHEAP)HeapPtr; 3146 3147 /* Check for page heap */ 3148 if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) 3149 { 3150 return RtlpPageHeapUnlock(Heap); 3151 } 3152 3153 /* Check if it's really a heap */ 3154 if (Heap->Signature != HEAP_SIGNATURE) return FALSE; 3155 3156 /* Unlock if it's lockable */ 3157 if (!(Heap->Flags & HEAP_NO_SERIALIZE)) 3158 { 3159 RtlLeaveHeapLock(Heap->LockVariable); 3160 } 3161 3162 return TRUE; 3163 } 3164 3165 3166 /*********************************************************************** 3167 * RtlSizeHeap 3168 * PARAMS 3169 * Heap [in] Handle of heap 3170 * Flags [in] Heap size control flags 3171 * Ptr [in] Address of memory to return size for 3172 * 3173 * RETURNS 3174 * Size in bytes of allocated memory 3175 * 0xffffffff: Failure 3176 * 3177 * @implemented 3178 */ 3179 SIZE_T NTAPI 3180 RtlSizeHeap( 3181 HANDLE HeapPtr, 3182 ULONG Flags, 3183 PVOID Ptr 3184 ) 3185 { 3186 PHEAP Heap = (PHEAP)HeapPtr; 3187 PHEAP_ENTRY HeapEntry; 3188 SIZE_T EntrySize; 3189 3190 // FIXME This is a hack around missing SEH support! 3191 if (!Heap) 3192 { 3193 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_HANDLE); 3194 return (SIZE_T)-1; 3195 } 3196 3197 /* Force flags */ 3198 Flags |= Heap->ForceFlags; 3199 3200 /* Call special heap */ 3201 if (RtlpHeapIsSpecial(Flags)) 3202 return RtlDebugSizeHeap(Heap, Flags, Ptr); 3203 3204 /* Get the heap entry pointer */ 3205 HeapEntry = (PHEAP_ENTRY)Ptr - 1; 3206 3207 /* Return -1 if that entry is free */ 3208 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) 3209 { 3210 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 3211 return (SIZE_T)-1; 3212 } 3213 3214 /* Get size of this block depending if it's a usual or a big one */ 3215 if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 3216 { 3217 EntrySize = RtlpGetSizeOfBigBlock(HeapEntry); 3218 } 3219 else 3220 { 3221 /* Calculate it */ 3222 EntrySize = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes; 3223 } 3224 3225 /* Return calculated size */ 3226 return EntrySize; 3227 } 3228 3229 BOOLEAN NTAPI 3230 RtlpCheckInUsePattern(PHEAP_ENTRY HeapEntry) 3231 { 3232 SIZE_T Size, Result; 3233 PCHAR TailPart; 3234 3235 /* Calculate size */ 3236 if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) 3237 Size = RtlpGetSizeOfBigBlock(HeapEntry); 3238 else 3239 Size = (HeapEntry->Size << HEAP_ENTRY_SHIFT) - HeapEntry->UnusedBytes; 3240 3241 /* Calculate pointer to the tail part of the block */ 3242 TailPart = (PCHAR)(HeapEntry + 1) + Size; 3243 3244 /* Compare tail pattern */ 3245 Result = RtlCompareMemory(TailPart, 3246 FillPattern, 3247 HEAP_ENTRY_SIZE); 3248 3249 if (Result != HEAP_ENTRY_SIZE) 3250 { 3251 DPRINT1("HEAP: Heap entry (size %x) %p tail is modified at %p\n", Size, HeapEntry, TailPart + Result); 3252 return FALSE; 3253 } 3254 3255 /* All is fine */ 3256 return TRUE; 3257 } 3258 3259 BOOLEAN NTAPI 3260 RtlpValidateHeapHeaders( 3261 PHEAP Heap, 3262 BOOLEAN Recalculate) 3263 { 3264 // We skip header validation for now 3265 return TRUE; 3266 } 3267 3268 BOOLEAN NTAPI 3269 RtlpValidateHeapEntry( 3270 PHEAP Heap, 3271 PHEAP_ENTRY HeapEntry) 3272 { 3273 BOOLEAN BigAllocation, EntryFound = FALSE; 3274 PHEAP_SEGMENT Segment; 3275 ULONG SegmentOffset; 3276 3277 /* Perform various consistency checks of this entry */ 3278 if (!HeapEntry) goto invalid_entry; 3279 if ((ULONG_PTR)HeapEntry & (HEAP_ENTRY_SIZE - 1)) goto invalid_entry; 3280 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) goto invalid_entry; 3281 3282 BigAllocation = HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC; 3283 Segment = Heap->Segments[HeapEntry->SegmentOffset]; 3284 3285 if (BigAllocation && 3286 (((ULONG_PTR)HeapEntry & (PAGE_SIZE - 1)) != FIELD_OFFSET(HEAP_VIRTUAL_ALLOC_ENTRY, BusyBlock))) 3287 goto invalid_entry; 3288 3289 if (!BigAllocation && (HeapEntry->SegmentOffset >= HEAP_SEGMENTS || 3290 !Segment || 3291 HeapEntry < Segment->FirstEntry || 3292 HeapEntry >= Segment->LastValidEntry)) 3293 goto invalid_entry; 3294 3295 if ((HeapEntry->Flags & HEAP_ENTRY_FILL_PATTERN) && 3296 !RtlpCheckInUsePattern(HeapEntry)) 3297 goto invalid_entry; 3298 3299 /* Checks are done, if this is a virtual entry, that's all */ 3300 if (HeapEntry->Flags & HEAP_ENTRY_VIRTUAL_ALLOC) return TRUE; 3301 3302 /* Go through segments and check if this entry fits into any of them */ 3303 for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++) 3304 { 3305 Segment = Heap->Segments[SegmentOffset]; 3306 if (!Segment) continue; 3307 3308 if ((HeapEntry >= Segment->FirstEntry) && 3309 (HeapEntry < Segment->LastValidEntry)) 3310 { 3311 /* Got it */ 3312 EntryFound = TRUE; 3313 break; 3314 } 3315 } 3316 3317 /* Return our result of finding entry in the segments */ 3318 return EntryFound; 3319 3320 invalid_entry: 3321 DPRINT1("HEAP: Invalid heap entry %p in heap %p\n", HeapEntry, Heap); 3322 return FALSE; 3323 } 3324 3325 BOOLEAN NTAPI 3326 RtlpValidateHeapSegment( 3327 PHEAP Heap, 3328 PHEAP_SEGMENT Segment, 3329 UCHAR SegmentOffset, 3330 PULONG FreeEntriesCount, 3331 PSIZE_T TotalFreeSize, 3332 PSIZE_T TagEntries, 3333 PSIZE_T PseudoTagEntries) 3334 { 3335 PHEAP_UCR_DESCRIPTOR UcrDescriptor; 3336 PLIST_ENTRY UcrEntry; 3337 SIZE_T ByteSize, Size, Result; 3338 PHEAP_ENTRY CurrentEntry; 3339 ULONG UnCommittedPages; 3340 ULONG UnCommittedRanges; 3341 ULONG PreviousSize; 3342 3343 UnCommittedPages = 0; 3344 UnCommittedRanges = 0; 3345 3346 if (IsListEmpty(&Segment->UCRSegmentList)) 3347 { 3348 UcrEntry = NULL; 3349 UcrDescriptor = NULL; 3350 } 3351 else 3352 { 3353 UcrEntry = Segment->UCRSegmentList.Flink; 3354 UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry); 3355 } 3356 3357 if (Segment->BaseAddress == Heap) 3358 CurrentEntry = &Heap->Entry; 3359 else 3360 CurrentEntry = &Segment->Entry; 3361 3362 while (CurrentEntry < Segment->LastValidEntry) 3363 { 3364 if (UcrDescriptor && 3365 ((PVOID)CurrentEntry >= UcrDescriptor->Address)) 3366 { 3367 DPRINT1("HEAP: Entry %p is not inside uncommited range [%p .. %p)\n", 3368 CurrentEntry, UcrDescriptor->Address, 3369 (PCHAR)UcrDescriptor->Address + UcrDescriptor->Size); 3370 3371 return FALSE; 3372 } 3373 3374 PreviousSize = 0; 3375 3376 while (CurrentEntry < Segment->LastValidEntry) 3377 { 3378 if (PreviousSize != CurrentEntry->PreviousSize) 3379 { 3380 DPRINT1("HEAP: Entry %p has incorrect PreviousSize %x instead of %x\n", 3381 CurrentEntry, CurrentEntry->PreviousSize, PreviousSize); 3382 3383 return FALSE; 3384 } 3385 3386 PreviousSize = CurrentEntry->Size; 3387 Size = CurrentEntry->Size << HEAP_ENTRY_SHIFT; 3388 3389 if (CurrentEntry->Flags & HEAP_ENTRY_BUSY) 3390 { 3391 if (TagEntries) 3392 { 3393 UNIMPLEMENTED; 3394 } 3395 3396 /* Check fill pattern */ 3397 if (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN) 3398 { 3399 if (!RtlpCheckInUsePattern(CurrentEntry)) 3400 return FALSE; 3401 } 3402 } 3403 else 3404 { 3405 /* The entry is free, increase free entries count and total free size */ 3406 *FreeEntriesCount = *FreeEntriesCount + 1; 3407 *TotalFreeSize += CurrentEntry->Size; 3408 3409 if ((Heap->Flags & HEAP_FREE_CHECKING_ENABLED) && 3410 (CurrentEntry->Flags & HEAP_ENTRY_FILL_PATTERN)) 3411 { 3412 ByteSize = Size - sizeof(HEAP_FREE_ENTRY); 3413 3414 if ((CurrentEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) && 3415 (ByteSize > sizeof(HEAP_FREE_ENTRY_EXTRA))) 3416 { 3417 ByteSize -= sizeof(HEAP_FREE_ENTRY_EXTRA); 3418 } 3419 3420 Result = RtlCompareMemoryUlong((PCHAR)((PHEAP_FREE_ENTRY)CurrentEntry + 1), 3421 ByteSize, 3422 ARENA_FREE_FILLER); 3423 3424 if (Result != ByteSize) 3425 { 3426 DPRINT1("HEAP: Free heap block %p modified at %p after it was freed\n", 3427 CurrentEntry, 3428 (PCHAR)(CurrentEntry + 1) + Result); 3429 3430 return FALSE; 3431 } 3432 } 3433 } 3434 3435 if (CurrentEntry->SegmentOffset != SegmentOffset) 3436 { 3437 DPRINT1("HEAP: Heap entry %p SegmentOffset is incorrect %x (should be %x)\n", 3438 CurrentEntry, SegmentOffset, CurrentEntry->SegmentOffset); 3439 return FALSE; 3440 } 3441 3442 /* Check if it's the last entry */ 3443 if (CurrentEntry->Flags & HEAP_ENTRY_LAST_ENTRY) 3444 { 3445 CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size); 3446 3447 if (!UcrDescriptor) 3448 { 3449 /* Check if it's not really the last one */ 3450 if (CurrentEntry != Segment->LastValidEntry) 3451 { 3452 DPRINT1("HEAP: Heap entry %p is not last block in segment (%p)\n", 3453 CurrentEntry, Segment->LastValidEntry); 3454 return FALSE; 3455 } 3456 } 3457 else if (CurrentEntry != UcrDescriptor->Address) 3458 { 3459 DPRINT1("HEAP: Heap entry %p does not match next uncommitted address (%p)\n", 3460 CurrentEntry, UcrDescriptor->Address); 3461 3462 return FALSE; 3463 } 3464 else 3465 { 3466 UnCommittedPages += (ULONG)(UcrDescriptor->Size / PAGE_SIZE); 3467 UnCommittedRanges++; 3468 3469 CurrentEntry = (PHEAP_ENTRY)((PCHAR)UcrDescriptor->Address + UcrDescriptor->Size); 3470 3471 /* Go to the next UCR descriptor */ 3472 UcrEntry = UcrEntry->Flink; 3473 if (UcrEntry == &Segment->UCRSegmentList) 3474 { 3475 UcrEntry = NULL; 3476 UcrDescriptor = NULL; 3477 } 3478 else 3479 { 3480 UcrDescriptor = CONTAINING_RECORD(UcrEntry, HEAP_UCR_DESCRIPTOR, SegmentEntry); 3481 } 3482 } 3483 3484 break; 3485 } 3486 3487 /* Advance to the next entry */ 3488 CurrentEntry = (PHEAP_ENTRY)((PCHAR)CurrentEntry + Size); 3489 } 3490 } 3491 3492 /* Check total numbers of UCP and UCR */ 3493 if (Segment->NumberOfUnCommittedPages != UnCommittedPages) 3494 { 3495 DPRINT1("HEAP: Segment %p NumberOfUnCommittedPages is invalid (%x != %x)\n", 3496 Segment, Segment->NumberOfUnCommittedPages, UnCommittedPages); 3497 3498 return FALSE; 3499 } 3500 3501 if (Segment->NumberOfUnCommittedRanges != UnCommittedRanges) 3502 { 3503 DPRINT1("HEAP: Segment %p NumberOfUnCommittedRanges is invalid (%x != %x)\n", 3504 Segment, Segment->NumberOfUnCommittedRanges, UnCommittedRanges); 3505 3506 return FALSE; 3507 } 3508 3509 return TRUE; 3510 } 3511 3512 BOOLEAN NTAPI 3513 RtlpValidateHeap(PHEAP Heap, 3514 BOOLEAN ForceValidation) 3515 { 3516 UCHAR SegmentOffset; 3517 SIZE_T TotalFreeSize; 3518 PLIST_ENTRY ListHead, NextEntry; 3519 ULONG FreeBlocksCount, FreeListEntriesCount; 3520 ULONG HintIndex; 3521 3522 /* Check headers */ 3523 if (!RtlpValidateHeapHeaders(Heap, FALSE)) 3524 return FALSE; 3525 3526 /* Skip validation if it's not needed */ 3527 if (!ForceValidation && !(Heap->Flags & HEAP_VALIDATE_ALL_ENABLED)) 3528 return TRUE; 3529 3530 /* Check free list */ 3531 FreeListEntriesCount = 0; 3532 ListHead = &Heap->FreeLists; 3533 NextEntry = ListHead->Flink; 3534 3535 while (NextEntry != ListHead) 3536 { 3537 PHEAP_FREE_ENTRY FreeEntry = CONTAINING_RECORD(NextEntry, HEAP_FREE_ENTRY, FreeList); 3538 3539 NextEntry = NextEntry->Flink; 3540 3541 if (NextEntry != ListHead) 3542 { 3543 PHEAP_FREE_ENTRY NextFreeEntry = CONTAINING_RECORD(NextEntry, HEAP_FREE_ENTRY, FreeList); 3544 /* Free entries must be sorted */ 3545 if (FreeEntry->Size > NextFreeEntry->Size) 3546 { 3547 DPRINT1("Dedicated free entry %p of size %ld is not put in order.\n", FreeEntry, FreeEntry->Size); 3548 } 3549 } 3550 3551 /* Check that the hint is there */ 3552 if (FreeEntry->Size > Heap->DeCommitFreeBlockThreshold) 3553 { 3554 if (Heap->FreeHints[0] == NULL) 3555 { 3556 DPRINT1("No hint pointing to the non-dedicated list although there is a free entry %p of size %ld.\n", 3557 FreeEntry, FreeEntry->Size); 3558 } 3559 if (!RtlTestBit(&Heap->FreeHintBitmap, 0)) 3560 { 3561 DPRINT1("Hint bit 0 is not set although there is a free entry %p of size %ld.\n", 3562 FreeEntry, FreeEntry->Size); 3563 } 3564 } 3565 else 3566 { 3567 if (Heap->FreeHints[FreeEntry->Size - 1] == NULL) 3568 { 3569 DPRINT1("No hint pointing to the dedicated list although there is a free entry %p of size %ld.\n", 3570 FreeEntry, FreeEntry->Size); 3571 } 3572 if (!RtlTestBit(&Heap->FreeHintBitmap, FreeEntry->Size - 1)) 3573 { 3574 DPRINT1("Hint bit 0 is not set although there is a free entry %p of size %ld.\n", 3575 FreeEntry, FreeEntry->Size); 3576 } 3577 } 3578 3579 /* If there is an in-use entry in a free list - that's quite a big problem */ 3580 if (FreeEntry->Flags & HEAP_ENTRY_BUSY) 3581 { 3582 DPRINT1("HEAP: Free element %p is marked in-use\n", FreeEntry); 3583 return FALSE; 3584 } 3585 3586 /* Add up to the total amount of free entries */ 3587 FreeListEntriesCount++; 3588 } 3589 3590 /* Check free list hints */ 3591 for (HintIndex = 0; HintIndex < Heap->DeCommitFreeBlockThreshold; HintIndex++) 3592 { 3593 if (Heap->FreeHints[HintIndex] != NULL) 3594 { 3595 PHEAP_FREE_ENTRY FreeEntry = CONTAINING_RECORD(Heap->FreeHints[HintIndex], HEAP_FREE_ENTRY, FreeList); 3596 3597 if (!RtlTestBit(&Heap->FreeHintBitmap, HintIndex)) 3598 { 3599 DPRINT1("Hint bitmap bit at %u is not set, but there is a hint entry.\n", HintIndex); 3600 } 3601 3602 if (HintIndex == 0) 3603 { 3604 if (FreeEntry->Size <= Heap->DeCommitFreeBlockThreshold) 3605 { 3606 DPRINT1("There is an entry %p of size %lu, smaller than the decommit threshold %lu in the non-dedicated free list hint.\n", 3607 FreeEntry, FreeEntry->Size, Heap->DeCommitFreeBlockThreshold); 3608 } 3609 } 3610 else 3611 { 3612 if (HintIndex != FreeEntry->Size - 1) 3613 { 3614 DPRINT1("There is an entry %p of size %lu at the position %u in the free entry hint array.\n", 3615 FreeEntry, FreeEntry->Size, HintIndex); 3616 } 3617 3618 if (FreeEntry->FreeList.Blink != &Heap->FreeLists) 3619 { 3620 /* The entry right before the hint must be smaller. */ 3621 PHEAP_FREE_ENTRY PreviousFreeEntry = CONTAINING_RECORD(FreeEntry->FreeList.Blink, 3622 HEAP_FREE_ENTRY, 3623 FreeList); 3624 if (PreviousFreeEntry->Size >= FreeEntry->Size) 3625 { 3626 DPRINT1("Free entry hint %p of size %lu is larger than the entry before it %p, which is of size %lu.\n", 3627 FreeEntry, FreeEntry->Size, PreviousFreeEntry, PreviousFreeEntry->Size); 3628 } 3629 } 3630 } 3631 } 3632 else if (RtlTestBit(&Heap->FreeHintBitmap, HintIndex)) 3633 { 3634 DPRINT1("Hint bitmap bit at %u is set, but there is no hint entry.\n", HintIndex); 3635 } 3636 } 3637 3638 /* Check big allocations */ 3639 ListHead = &Heap->VirtualAllocdBlocks; 3640 NextEntry = ListHead->Flink; 3641 3642 while (ListHead != NextEntry) 3643 { 3644 PHEAP_VIRTUAL_ALLOC_ENTRY VirtualAllocBlock = CONTAINING_RECORD(NextEntry, HEAP_VIRTUAL_ALLOC_ENTRY, Entry); 3645 3646 /* We can only check the fill pattern */ 3647 if (VirtualAllocBlock->BusyBlock.Flags & HEAP_ENTRY_FILL_PATTERN) 3648 { 3649 if (!RtlpCheckInUsePattern(&VirtualAllocBlock->BusyBlock)) 3650 return FALSE; 3651 } 3652 3653 NextEntry = NextEntry->Flink; 3654 } 3655 3656 /* Check all segments */ 3657 FreeBlocksCount = 0; 3658 TotalFreeSize = 0; 3659 3660 for (SegmentOffset = 0; SegmentOffset < HEAP_SEGMENTS; SegmentOffset++) 3661 { 3662 PHEAP_SEGMENT Segment = Heap->Segments[SegmentOffset]; 3663 3664 /* Go to the next one if there is no segment */ 3665 if (!Segment) continue; 3666 3667 if (!RtlpValidateHeapSegment(Heap, 3668 Segment, 3669 SegmentOffset, 3670 &FreeBlocksCount, 3671 &TotalFreeSize, 3672 NULL, 3673 NULL)) 3674 { 3675 return FALSE; 3676 } 3677 } 3678 3679 if (FreeListEntriesCount != FreeBlocksCount) 3680 { 3681 DPRINT1("HEAP: Free blocks count in arena (%lu) does not match free blocks number in the free lists (%lu)\n", FreeBlocksCount, FreeListEntriesCount); 3682 return FALSE; 3683 } 3684 3685 if (Heap->TotalFreeSize != TotalFreeSize) 3686 { 3687 DPRINT1("HEAP: Total size of free blocks in arena (%Iu) does not equal to the one in heap header (%Iu)\n", TotalFreeSize, Heap->TotalFreeSize); 3688 return FALSE; 3689 } 3690 3691 return TRUE; 3692 } 3693 3694 /*********************************************************************** 3695 * RtlValidateHeap 3696 * Validates a specified heap. 3697 * 3698 * PARAMS 3699 * Heap [in] Handle to the heap 3700 * Flags [in] Bit flags that control access during operation 3701 * Block [in] Optional pointer to memory block to validate 3702 * 3703 * NOTES 3704 * Flags is ignored. 3705 * 3706 * RETURNS 3707 * TRUE: Success 3708 * FALSE: Failure 3709 * 3710 * @implemented 3711 */ 3712 BOOLEAN NTAPI RtlValidateHeap( 3713 HANDLE HeapPtr, 3714 ULONG Flags, 3715 PVOID Block 3716 ) 3717 { 3718 PHEAP Heap = (PHEAP)HeapPtr; 3719 BOOLEAN HeapLocked = FALSE; 3720 BOOLEAN HeapValid; 3721 3722 /* Check for page heap */ 3723 if (Heap->ForceFlags & HEAP_FLAG_PAGE_ALLOCS) 3724 return RtlpDebugPageHeapValidate(HeapPtr, Flags, Block); 3725 3726 /* Check signature */ 3727 if (Heap->Signature != HEAP_SIGNATURE) 3728 { 3729 DPRINT1("HEAP: Signature %lx is invalid for heap %p\n", Heap->Signature, Heap); 3730 return FALSE; 3731 } 3732 3733 /* Force flags */ 3734 Flags |= Heap->ForceFlags; 3735 3736 /* Acquire the lock if necessary */ 3737 if (!(Flags & HEAP_NO_SERIALIZE)) 3738 { 3739 RtlEnterHeapLock(Heap->LockVariable, TRUE); 3740 HeapLocked = TRUE; 3741 } 3742 3743 /* Either validate whole heap or just one entry */ 3744 if (!Block) 3745 HeapValid = RtlpValidateHeap(Heap, TRUE); 3746 else 3747 HeapValid = RtlpValidateHeapEntry(Heap, (PHEAP_ENTRY)Block - 1); 3748 3749 /* Unlock if it's lockable */ 3750 if (HeapLocked) 3751 { 3752 RtlLeaveHeapLock(Heap->LockVariable); 3753 } 3754 3755 return HeapValid; 3756 } 3757 3758 /* 3759 * @implemented 3760 */ 3761 NTSTATUS NTAPI 3762 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine, 3763 PVOID lParam) 3764 { 3765 UNIMPLEMENTED; 3766 return STATUS_NOT_IMPLEMENTED; 3767 } 3768 3769 3770 /* 3771 * @implemented 3772 */ 3773 ULONG NTAPI 3774 RtlGetProcessHeaps(ULONG count, 3775 HANDLE *heaps) 3776 { 3777 UNIMPLEMENTED; 3778 return 0; 3779 } 3780 3781 3782 /* 3783 * @implemented 3784 */ 3785 BOOLEAN NTAPI 3786 RtlValidateProcessHeaps(VOID) 3787 { 3788 UNIMPLEMENTED; 3789 return TRUE; 3790 } 3791 3792 3793 /* 3794 * @unimplemented 3795 */ 3796 BOOLEAN NTAPI 3797 RtlZeroHeap( 3798 IN PVOID HeapHandle, 3799 IN ULONG Flags 3800 ) 3801 { 3802 UNIMPLEMENTED; 3803 return FALSE; 3804 } 3805 3806 /* 3807 * @implemented 3808 */ 3809 BOOLEAN 3810 NTAPI 3811 RtlSetUserValueHeap(IN PVOID HeapHandle, 3812 IN ULONG Flags, 3813 IN PVOID BaseAddress, 3814 IN PVOID UserValue) 3815 { 3816 PHEAP Heap = (PHEAP)HeapHandle; 3817 PHEAP_ENTRY HeapEntry; 3818 PHEAP_ENTRY_EXTRA Extra; 3819 BOOLEAN HeapLocked = FALSE, ValueSet = FALSE; 3820 3821 /* Force flags */ 3822 Flags |= Heap->ForceFlags; 3823 3824 /* Call special heap */ 3825 if (RtlpHeapIsSpecial(Flags)) 3826 return RtlDebugSetUserValueHeap(Heap, Flags, BaseAddress, UserValue); 3827 3828 /* Lock if it's lockable */ 3829 if (!(Heap->Flags & HEAP_NO_SERIALIZE)) 3830 { 3831 RtlEnterHeapLock(Heap->LockVariable, TRUE); 3832 HeapLocked = TRUE; 3833 } 3834 3835 /* Get a pointer to the entry */ 3836 HeapEntry = (PHEAP_ENTRY)BaseAddress - 1; 3837 3838 /* If it's a free entry - return error */ 3839 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) 3840 { 3841 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 3842 3843 /* Release the heap lock if it was acquired */ 3844 if (HeapLocked) 3845 RtlLeaveHeapLock(Heap->LockVariable); 3846 3847 return FALSE; 3848 } 3849 3850 /* Check if this entry has an extra stuff associated with it */ 3851 if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 3852 { 3853 /* Use extra to store the value */ 3854 Extra = RtlpGetExtraStuffPointer(HeapEntry); 3855 Extra->Settable = (ULONG_PTR)UserValue; 3856 3857 /* Indicate that value was set */ 3858 ValueSet = TRUE; 3859 } 3860 3861 /* Release the heap lock if it was acquired */ 3862 if (HeapLocked) 3863 RtlLeaveHeapLock(Heap->LockVariable); 3864 3865 return ValueSet; 3866 } 3867 3868 /* 3869 * @implemented 3870 */ 3871 BOOLEAN 3872 NTAPI 3873 RtlSetUserFlagsHeap(IN PVOID HeapHandle, 3874 IN ULONG Flags, 3875 IN PVOID BaseAddress, 3876 IN ULONG UserFlagsReset, 3877 IN ULONG UserFlagsSet) 3878 { 3879 PHEAP Heap = (PHEAP)HeapHandle; 3880 PHEAP_ENTRY HeapEntry; 3881 BOOLEAN HeapLocked = FALSE; 3882 3883 /* Force flags */ 3884 Flags |= Heap->ForceFlags; 3885 3886 /* Call special heap */ 3887 if (RtlpHeapIsSpecial(Flags)) 3888 return RtlDebugSetUserFlagsHeap(Heap, Flags, BaseAddress, UserFlagsReset, UserFlagsSet); 3889 3890 /* Lock if it's lockable */ 3891 if (!(Flags & HEAP_NO_SERIALIZE)) 3892 { 3893 RtlEnterHeapLock(Heap->LockVariable, TRUE); 3894 HeapLocked = TRUE; 3895 } 3896 3897 /* Get a pointer to the entry */ 3898 HeapEntry = (PHEAP_ENTRY)BaseAddress - 1; 3899 3900 /* If it's a free entry - return error */ 3901 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) 3902 { 3903 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 3904 3905 /* Release the heap lock if it was acquired */ 3906 if (HeapLocked) 3907 RtlLeaveHeapLock(Heap->LockVariable); 3908 3909 return FALSE; 3910 } 3911 3912 /* Set / reset flags */ 3913 HeapEntry->Flags &= ~(UserFlagsReset >> 4); 3914 HeapEntry->Flags |= (UserFlagsSet >> 4); 3915 3916 /* Release the heap lock if it was acquired */ 3917 if (HeapLocked) 3918 RtlLeaveHeapLock(Heap->LockVariable); 3919 3920 return TRUE; 3921 } 3922 3923 /* 3924 * @implemented 3925 */ 3926 BOOLEAN 3927 NTAPI 3928 RtlGetUserInfoHeap(IN PVOID HeapHandle, 3929 IN ULONG Flags, 3930 IN PVOID BaseAddress, 3931 OUT PVOID *UserValue, 3932 OUT PULONG UserFlags) 3933 { 3934 PHEAP Heap = (PHEAP)HeapHandle; 3935 PHEAP_ENTRY HeapEntry; 3936 PHEAP_ENTRY_EXTRA Extra; 3937 BOOLEAN HeapLocked = FALSE; 3938 3939 /* Force flags */ 3940 Flags |= Heap->ForceFlags; 3941 3942 /* Call special heap */ 3943 if (RtlpHeapIsSpecial(Flags)) 3944 return RtlDebugGetUserInfoHeap(Heap, Flags, BaseAddress, UserValue, UserFlags); 3945 3946 /* Lock if it's lockable */ 3947 if (!(Flags & HEAP_NO_SERIALIZE)) 3948 { 3949 RtlEnterHeapLock(Heap->LockVariable, TRUE); 3950 HeapLocked = TRUE; 3951 } 3952 3953 /* Get a pointer to the entry */ 3954 HeapEntry = (PHEAP_ENTRY)BaseAddress - 1; 3955 3956 /* If it's a free entry - return error */ 3957 if (!(HeapEntry->Flags & HEAP_ENTRY_BUSY)) 3958 { 3959 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 3960 3961 /* Release the heap lock if it was acquired */ 3962 if (HeapLocked) 3963 RtlLeaveHeapLock(Heap->LockVariable); 3964 3965 return FALSE; 3966 } 3967 3968 /* Check if this entry has an extra stuff associated with it */ 3969 if (HeapEntry->Flags & HEAP_ENTRY_EXTRA_PRESENT) 3970 { 3971 /* Get pointer to extra data */ 3972 Extra = RtlpGetExtraStuffPointer(HeapEntry); 3973 3974 /* Pass user value */ 3975 if (UserValue) 3976 *UserValue = (PVOID)Extra->Settable; 3977 } 3978 3979 /* Decode and return user flags */ 3980 if (UserFlags) 3981 *UserFlags = (HeapEntry->Flags & HEAP_ENTRY_SETTABLE_FLAGS) << 4; 3982 3983 /* Release the heap lock if it was acquired */ 3984 if (HeapLocked) 3985 RtlLeaveHeapLock(Heap->LockVariable); 3986 3987 return TRUE; 3988 } 3989 3990 /* 3991 * @unimplemented 3992 */ 3993 NTSTATUS 3994 NTAPI 3995 RtlUsageHeap(IN HANDLE Heap, 3996 IN ULONG Flags, 3997 OUT PRTL_HEAP_USAGE Usage) 3998 { 3999 /* TODO */ 4000 UNIMPLEMENTED; 4001 return STATUS_NOT_IMPLEMENTED; 4002 } 4003 4004 PWSTR 4005 NTAPI 4006 RtlQueryTagHeap(IN PVOID HeapHandle, 4007 IN ULONG Flags, 4008 IN USHORT TagIndex, 4009 IN BOOLEAN ResetCounters, 4010 OUT PRTL_HEAP_TAG_INFO HeapTagInfo) 4011 { 4012 /* TODO */ 4013 UNIMPLEMENTED; 4014 return NULL; 4015 } 4016 4017 ULONG 4018 NTAPI 4019 RtlExtendHeap(IN HANDLE Heap, 4020 IN ULONG Flags, 4021 IN PVOID P, 4022 IN SIZE_T Size) 4023 { 4024 /* TODO */ 4025 UNIMPLEMENTED; 4026 return 0; 4027 } 4028 4029 ULONG 4030 NTAPI 4031 RtlCreateTagHeap(IN HANDLE HeapHandle, 4032 IN ULONG Flags, 4033 IN PWSTR TagName, 4034 IN PWSTR TagSubName) 4035 { 4036 /* TODO */ 4037 UNIMPLEMENTED; 4038 return 0; 4039 } 4040 4041 NTSTATUS 4042 NTAPI 4043 RtlWalkHeap(IN HANDLE HeapHandle, 4044 IN PVOID HeapEntry) 4045 { 4046 UNIMPLEMENTED; 4047 return STATUS_NOT_IMPLEMENTED; 4048 } 4049 4050 PVOID 4051 NTAPI 4052 RtlProtectHeap(IN PVOID HeapHandle, 4053 IN BOOLEAN ReadOnly) 4054 { 4055 UNIMPLEMENTED; 4056 return NULL; 4057 } 4058 4059 NTSTATUS 4060 NTAPI 4061 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL, 4062 IN HEAP_INFORMATION_CLASS HeapInformationClass, 4063 IN PVOID HeapInformation, 4064 IN SIZE_T HeapInformationLength) 4065 { 4066 /* Setting heap information is not really supported except for enabling LFH */ 4067 if (HeapInformationClass == HeapCompatibilityInformation) 4068 { 4069 /* Check buffer length */ 4070 if (HeapInformationLength < sizeof(ULONG)) 4071 { 4072 /* The provided buffer is too small */ 4073 return STATUS_BUFFER_TOO_SMALL; 4074 } 4075 4076 /* Check for a special magic value for enabling LFH */ 4077 if (*(PULONG)HeapInformation != 2) 4078 { 4079 return STATUS_UNSUCCESSFUL; 4080 } 4081 4082 DPRINT1("RtlSetHeapInformation() needs to enable LFH\n"); 4083 return STATUS_SUCCESS; 4084 } 4085 4086 return STATUS_SUCCESS; 4087 } 4088 4089 NTSTATUS 4090 NTAPI 4091 RtlQueryHeapInformation(HANDLE HeapHandle, 4092 HEAP_INFORMATION_CLASS HeapInformationClass, 4093 PVOID HeapInformation, 4094 SIZE_T HeapInformationLength, 4095 PSIZE_T ReturnLength OPTIONAL) 4096 { 4097 PHEAP Heap = (PHEAP)HeapHandle; 4098 4099 /* Only HeapCompatibilityInformation is supported */ 4100 if (HeapInformationClass == HeapCompatibilityInformation) 4101 { 4102 /* Set result length */ 4103 if (ReturnLength) 4104 *ReturnLength = sizeof(ULONG); 4105 4106 /* Check buffer length */ 4107 if (HeapInformationLength < sizeof(ULONG)) 4108 { 4109 /* It's too small, return needed length */ 4110 return STATUS_BUFFER_TOO_SMALL; 4111 } 4112 4113 /* Return front end heap type */ 4114 *(PULONG)HeapInformation = Heap->FrontEndHeapType; 4115 4116 return STATUS_SUCCESS; 4117 } 4118 4119 return STATUS_UNSUCCESSFUL; 4120 } 4121 4122 /* @implemented */ 4123 ULONG 4124 NTAPI 4125 RtlMultipleAllocateHeap(IN PVOID HeapHandle, 4126 IN ULONG Flags, 4127 IN SIZE_T Size, 4128 IN ULONG Count, 4129 OUT PVOID *Array) 4130 { 4131 ULONG Index; 4132 EXCEPTION_RECORD ExceptionRecord; 4133 4134 for (Index = 0; Index < Count; ++Index) 4135 { 4136 Array[Index] = RtlAllocateHeap(HeapHandle, Flags, Size); 4137 if (Array[Index] == NULL) 4138 { 4139 /* ERROR_NOT_ENOUGH_MEMORY */ 4140 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_NO_MEMORY); 4141 4142 if (Flags & HEAP_GENERATE_EXCEPTIONS) 4143 { 4144 ExceptionRecord.ExceptionCode = STATUS_NO_MEMORY; 4145 ExceptionRecord.ExceptionRecord = NULL; 4146 ExceptionRecord.NumberParameters = 0; 4147 ExceptionRecord.ExceptionFlags = 0; 4148 4149 RtlRaiseException(&ExceptionRecord); 4150 } 4151 break; 4152 } 4153 } 4154 4155 return Index; 4156 } 4157 4158 /* @implemented */ 4159 ULONG 4160 NTAPI 4161 RtlMultipleFreeHeap(IN PVOID HeapHandle, 4162 IN ULONG Flags, 4163 IN ULONG Count, 4164 OUT PVOID *Array) 4165 { 4166 ULONG Index; 4167 4168 for (Index = 0; Index < Count; ++Index) 4169 { 4170 if (Array[Index] == NULL) 4171 continue; 4172 4173 _SEH2_TRY 4174 { 4175 if (!RtlFreeHeap(HeapHandle, Flags, Array[Index])) 4176 { 4177 /* ERROR_INVALID_PARAMETER */ 4178 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 4179 break; 4180 } 4181 } 4182 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 4183 { 4184 /* ERROR_INVALID_PARAMETER */ 4185 RtlSetLastWin32ErrorAndNtStatusFromNtStatus(STATUS_INVALID_PARAMETER); 4186 break; 4187 } 4188 _SEH2_END; 4189 } 4190 4191 return Index; 4192 } 4193 4194 /* 4195 * Info: 4196 * - https://securityxploded.com/enumheaps.php 4197 * - https://evilcodecave.wordpress.com/2009/04/14/rtlqueryprocessheapinformation-as-anti-dbg-trick/ 4198 */ 4199 struct _DEBUG_BUFFER; 4200 4201 NTSTATUS 4202 NTAPI 4203 RtlQueryProcessHeapInformation( 4204 IN struct _DEBUG_BUFFER *DebugBuffer) 4205 { 4206 UNIMPLEMENTED; 4207 return STATUS_NOT_IMPLEMENTED; 4208 } 4209 4210 /* EOF */ 4211 4212