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