projects / reactos.git / blob
? search:


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