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