projects / reactos.git / blob
? search:


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