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