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