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