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