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