projects / reactos.git / blob
? search:


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