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