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