Fix prototype of RtlCreateHeap and respect the CommitRoutine if passed. Also fix...
[reactos.git] / reactos / lib / rtl / heap.c
1 /*
2 * Win32 heap functions
3 *
4 * Copyright 1996 Alexandre Julliard
5 * Copyright 1998 Ulrich Weigand
6 */
7
8
9 /* Note: the heap data structures are based on what Pietrek describes in his
10 * book 'Windows 95 System Programming Secrets'. The layout is not exactly
11 * the same, but could be easily adapted if it turns out some programs
12 * require it.
13 */
14
15 #include <rtl.h>
16
17 #define NDEBUG
18 #include <debug.h>
19
20 #define WARN_ON(x) (1)
21
22 #ifdef NDEBUG
23 #define TRACE_ON(x) (0)
24 #else
25 #define TRACE_ON(x) (1)
26 #endif
27
28 static RTL_CRITICAL_SECTION RtlpProcessHeapsListLock;
29
30
31 typedef struct tagARENA_INUSE
32 {
33 ULONG size; /* Block size; must be the first field */
34 USHORT threadId; /* Allocating thread id */
35 USHORT magic; /* Magic number */
36 }
37 ARENA_INUSE;
38
39 typedef struct tagARENA_FREE
40 {
41 ULONG size; /* Block size; must be the first field */
42 USHORT threadId; /* Freeing thread id */
43 USHORT magic; /* Magic number */
44 struct tagARENA_FREE *next; /* Next free arena */
45 struct tagARENA_FREE *prev; /* Prev free arena */
46 }
47 ARENA_FREE;
48
49 #define ARENA_FLAG_FREE 0x00000001 /* flags OR'ed with arena size */
50 #define ARENA_FLAG_PREV_FREE 0x00000002
51 #define ARENA_SIZE_MASK 0xfffffffc
52 #define ARENA_INUSE_MAGIC 0x4842 /* Value for arena 'magic' field */
53 #define ARENA_FREE_MAGIC 0x4846 /* Value for arena 'magic' field */
54
55 #define ARENA_INUSE_FILLER 0x55
56 #define ARENA_FREE_FILLER 0xaa
57
58 #define QUIET 1 /* Suppress messages */
59 #define NOISY 0 /* Report all errors */
60
61 #define HEAP_NB_FREE_LISTS 4 /* Number of free lists */
62
63 /* Max size of the blocks on the free lists */
64 static const ULONG HEAP_freeListSizes[HEAP_NB_FREE_LISTS] =
65 {
66 0x20, 0x80, 0x200, 0xffffffff
67 };
68
69 typedef struct
70 {
71 ULONG size;
72 ARENA_FREE arena;
73 }
74 FREE_LIST_ENTRY;
75
76 struct tagHEAP;
77
78 typedef struct tagSUBHEAP
79 {
80 ULONG size; /* Size of the whole sub-heap */
81 ULONG commitSize; /* Committed size of the sub-heap */
82 ULONG headerSize; /* Size of the heap header */
83 struct tagSUBHEAP *next; /* Next sub-heap */
84 struct tagHEAP *heap; /* Main heap structure */
85 ULONG magic; /* Magic number */
86 }
87 SUBHEAP, *PSUBHEAP;
88
89 #define SUBHEAP_MAGIC ((ULONG)('S' | ('U'<<8) | ('B'<<16) | ('H'<<24)))
90
91 typedef struct tagHEAP
92 {
93 SUBHEAP subheap; /* First sub-heap */
94 struct tagHEAP *next; /* Next heap for this process */
95 FREE_LIST_ENTRY freeList[HEAP_NB_FREE_LISTS]; /* Free lists */
96 RTL_CRITICAL_SECTION critSection; /* Critical section for serialization */
97 ULONG flags; /* Heap flags */
98 ULONG magic; /* Magic number */
99 PRTL_HEAP_COMMIT_ROUTINE commitRoutine;
100 }
101 HEAP, *PHEAP;
102
103 #define HEAP_MAGIC ((ULONG)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
104
105 #define HEAP_DEF_SIZE 0x110000 /* Default heap size = 1Mb + 64Kb */
106 #define HEAP_MIN_BLOCK_SIZE (sizeof(ARENA_FREE) + 8) /* Min. heap block size */
107 #define COMMIT_MASK 0xffff /* bitmask for commit/decommit granularity */
108
109
110 static BOOLEAN HEAP_IsRealArena( HANDLE heap, ULONG flags, PVOID block, BOOLEAN quiet );
111
112
113 /***********************************************************************
114 * HEAP_Dump
115 */
116 VOID
117 HEAP_Dump(PHEAP heap)
118 {
119 int i;
120 SUBHEAP *subheap;
121 char *ptr;
122
123 DPRINT( "Heap: %p\n", heap );
124 DPRINT( "Next: %p Sub-heaps: %p",
125 heap->next, &heap->subheap );
126 subheap = &heap->subheap;
127 while (subheap->next)
128 {
129 DPRINT( " -> %p", subheap->next );
130 subheap = subheap->next;
131 }
132
133 DPRINT( "\nFree lists:\n Block Stat Size Id\n" );
134 for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
135 DPRINT( "%p free %08lx %04x prev=%p next=%p\n",
136 &heap->freeList[i].arena,
137 heap->freeList[i].arena.size,
138 heap->freeList[i].arena.threadId,
139 heap->freeList[i].arena.prev,
140 heap->freeList[i].arena.next );
141
142 subheap = &heap->subheap;
143 while (subheap)
144 {
145 ULONG freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
146 DPRINT( "\n\nSub-heap %p: size=%08lx committed=%08lx\n",
147 subheap, subheap->size, subheap->commitSize );
148
149 DPRINT( "\n Block Stat Size Id\n" );
150 ptr = (char*)subheap + subheap->headerSize;
151 while (ptr < (char *)subheap + subheap->size)
152 {
153 if (*(PULONG)ptr & ARENA_FLAG_FREE)
154 {
155 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
156 DPRINT( "%p free %08lx %04x prev=%p next=%p\n",
157 pArena, pArena->size & ARENA_SIZE_MASK,
158 pArena->threadId, pArena->prev,
159 pArena->next);
160 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
161 arenaSize += sizeof(ARENA_FREE);
162 freeSize += pArena->size & ARENA_SIZE_MASK;
163 }
164 else if (*(PULONG)ptr & ARENA_FLAG_PREV_FREE)
165 {
166 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
167 DPRINT( "%p Used %08lx %04x back=%08lx\n",
168 pArena, pArena->size & ARENA_SIZE_MASK,
169 pArena->threadId, *((PULONG)pArena - 1));
170 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
171 arenaSize += sizeof(ARENA_INUSE);
172 usedSize += pArena->size & ARENA_SIZE_MASK;
173 }
174 else
175 {
176 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
177 DPRINT( "%p used %08lx %04x\n",
178 pArena, pArena->size & ARENA_SIZE_MASK,
179 pArena->threadId);
180 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
181 arenaSize += sizeof(ARENA_INUSE);
182 usedSize += pArena->size & ARENA_SIZE_MASK;
183 }
184 }
185 DPRINT( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
186 subheap->size, subheap->commitSize, freeSize, usedSize,
187 arenaSize, (arenaSize * 100) / subheap->size );
188 subheap = subheap->next;
189 }
190 }
191
192
193 /***********************************************************************
194 * HEAP_GetPtr
195 * RETURNS
196 * Pointer to the heap
197 * NULL: Failure
198 */
199 static PHEAP
200 HEAP_GetPtr(HANDLE heap) /* [in] Handle to the heap */
201 {
202 HEAP *heapPtr = (HEAP *)heap;
203 if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
204 {
205 DPRINT("Invalid heap %08x!\n", heap );
206 return NULL;
207 }
208 if (TRACE_ON(heap) && !HEAP_IsRealArena( heap, 0, NULL, NOISY ))
209 {
210 HEAP_Dump( heapPtr );
211 ASSERT( FALSE );
212 return NULL;
213 }
214 return heapPtr;
215 }
216
217
218 /***********************************************************************
219 * HEAP_InsertFreeBlock
220 *
221 * Insert a free block into the free list.
222 */
223 static VOID
224 HEAP_InsertFreeBlock(PHEAP heap,
225 ARENA_FREE *pArena,
226 BOOLEAN last)
227 {
228 FREE_LIST_ENTRY *pEntry = heap->freeList;
229 while (pEntry->size < pArena->size)
230 pEntry++;
231 if (last)
232 {
233 /* insert at end of free list, i.e. before next free list entry */
234 pEntry++;
235 if (pEntry == &heap->freeList[HEAP_NB_FREE_LISTS])
236 {
237 pEntry = heap->freeList;
238 }
239 pArena->prev = pEntry->arena.prev;
240 pArena->prev->next = pArena;
241 pArena->next = &pEntry->arena;
242 pEntry->arena.prev = pArena;
243 }
244 else
245 {
246 /* insert at head of free list */
247 pArena->next = pEntry->arena.next;
248 pArena->next->prev = pArena;
249 pArena->prev = &pEntry->arena;
250 pEntry->arena.next = pArena;
251 }
252 pArena->size |= ARENA_FLAG_FREE;
253 }
254
255
256 /***********************************************************************
257 * HEAP_FindSubHeap
258 * Find the sub-heap containing a given address.
259 *
260 * RETURNS
261 * Pointer: Success
262 * NULL: Failure
263 */
264 static PSUBHEAP
265 HEAP_FindSubHeap(HEAP *heap, /* [in] Heap pointer */
266 PVOID ptr) /* [in] Address */
267 {
268 PSUBHEAP sub = &heap->subheap;
269 while (sub)
270 {
271 if (((char *)ptr >= (char *)sub) &&
272 ((char *)ptr < (char *)sub + sub->size))
273 return sub;
274 sub = sub->next;
275 }
276 return NULL;
277 }
278
279
280 /***********************************************************************
281 * HEAP_Commit
282 *
283 * Make sure the heap storage is committed up to (not including) ptr.
284 */
285 static inline BOOLEAN
286 HEAP_Commit(SUBHEAP *subheap,
287 PVOID ptr,
288 ULONG flags)
289 {
290 ULONG size = (ULONG)((char *)ptr - (char *)subheap);
291 NTSTATUS Status;
292 PVOID address;
293 ULONG commitsize;
294
295 size = (size + COMMIT_MASK) & ~COMMIT_MASK;
296 if (size > subheap->size)
297 size = subheap->size;
298 if (size <= subheap->commitSize)
299 return TRUE;
300
301 address = (PVOID)((char *)subheap + subheap->commitSize);
302 commitsize = size - subheap->commitSize;
303
304 if (subheap->heap->commitRoutine != NULL)
305 {
306 Status = subheap->heap->commitRoutine(subheap->heap, &address, &commitsize);
307 }
308 else
309 {
310 Status = NtAllocateVirtualMemory(NtCurrentProcess(),
311 &address,
312 0,
313 &commitsize,
314 MEM_COMMIT,
315 PAGE_EXECUTE_READWRITE);
316 }
317 if (!NT_SUCCESS(Status))
318 {
319 DPRINT( "Could not commit %08lx bytes at %p for heap %p\n",
320 size - subheap->commitSize,
321 ((char *)subheap + subheap->commitSize),
322 subheap->heap );
323 return FALSE;
324 }
325
326 subheap->commitSize += commitsize;
327 return TRUE;
328 }
329
330
331 #if 0
332 /***********************************************************************
333 * HEAP_Decommit
334 *
335 * If possible, decommit the heap storage from (including) 'ptr'.
336 */
337 static inline BOOLEAN HEAP_Decommit( SUBHEAP *subheap, PVOID ptr, ULONG flags )
338 {
339 ULONG size = (ULONG)((char *)ptr - (char *)subheap);
340 PVOID address;
341 ULONG decommitsize;
342 NTSTATUS Status;
343 /* round to next block and add one full block */
344 size = ((size + COMMIT_MASK) & ~COMMIT_MASK) + COMMIT_MASK + 1;
345 if (size >= subheap->commitSize)
346 return TRUE;
347
348 address = (PVOID)((char *)subheap + size);
349 decommitsize = subheap->commitSize - size;
350
351 Status = ZwFreeVirtualMemory(NtCurrentProcess(),
352 &address,
353 &decommitsize,
354 MEM_DECOMMIT);
355 if (!NT_SUCCESS(Status))
356 {
357 DPRINT( "Could not decommit %08lx bytes at %p for heap %p\n",
358 subheap->commitSize - size,
359 ((char *)subheap + size),
360 subheap->heap );
361 return FALSE;
362 }
363
364 subheap->commitSize -= decommitsize;
365 return TRUE;
366 }
367 #endif
368
369 /***********************************************************************
370 * HEAP_CreateFreeBlock
371 *
372 * Create a free block at a specified address. 'size' is the size of the
373 * whole block, including the new arena.
374 */
375 static VOID HEAP_CreateFreeBlock( SUBHEAP *subheap, PVOID ptr, ULONG size )
376 {
377 ARENA_FREE *pFree;
378 BOOLEAN last;
379
380 /* Create a free arena */
381
382 pFree = (ARENA_FREE *)ptr;
383 pFree->threadId = (ULONG)NtCurrentTeb()->Cid.UniqueThread;
384 pFree->magic = ARENA_FREE_MAGIC;
385
386 /* If debugging, erase the freed block content */
387
388 if (TRACE_ON(heap))
389 {
390 char *pEnd = (char *)ptr + size;
391 if (pEnd > (char *)subheap + subheap->commitSize)
392 pEnd = (char *)subheap + subheap->commitSize;
393 if (pEnd > (char *)(pFree + 1))
394 memset( pFree + 1, ARENA_FREE_FILLER, pEnd - (char *)(pFree + 1) );
395 }
396
397 /* Check if next block is free also */
398
399 if (((char *)ptr + size < (char *)subheap + subheap->size) &&
400 (*(PULONG)((char *)ptr + size) & ARENA_FLAG_FREE))
401 {
402 /* Remove the next arena from the free list */
403 ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
404 pNext->next->prev = pNext->prev;
405 pNext->prev->next = pNext->next;
406 size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
407 if (TRACE_ON(heap))
408 memset( pNext, ARENA_FREE_FILLER, sizeof(ARENA_FREE) );
409 }
410
411 /* Set the next block PREV_FREE flag and pointer */
412
413 last = ((char *)ptr + size >= (char *)subheap + subheap->size);
414 if (!last)
415 {
416 PULONG pNext = (PULONG)((char *)ptr + size);
417 *pNext |= ARENA_FLAG_PREV_FREE;
418 *(ARENA_FREE **)(pNext - 1) = pFree;
419 }
420
421 /* Last, insert the new block into the free list */
422
423 pFree->size = size - sizeof(*pFree);
424 HEAP_InsertFreeBlock( subheap->heap, pFree, last );
425 }
426
427
428 /***********************************************************************
429 * HEAP_MakeInUseBlockFree
430 *
431 * Turn an in-use block into a free block. Can also decommit the end of
432 * the heap, and possibly even free the sub-heap altogether.
433 */
434 static VOID HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena,
435 ULONG flags)
436 {
437 ARENA_FREE *pFree;
438 ULONG size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
439 ULONG dummySize = 0;
440
441 /* Check if we can merge with previous block */
442
443 if (pArena->size & ARENA_FLAG_PREV_FREE)
444 {
445 pFree = *((ARENA_FREE **)pArena - 1);
446 size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
447 /* Remove it from the free list */
448 pFree->next->prev = pFree->prev;
449 pFree->prev->next = pFree->next;
450 }
451 else
452 pFree = (ARENA_FREE *)pArena;
453
454 /* Create a free block */
455
456 HEAP_CreateFreeBlock( subheap, pFree, size );
457 size = (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
458 if ((char *)pFree + size < (char *)subheap + subheap->size)
459 return; /* Not the last block, so nothing more to do */
460
461 /* Free the whole sub-heap if it's empty and not the original one */
462
463 if (((char *)pFree == (char *)subheap + subheap->headerSize) &&
464 (subheap != &subheap->heap->subheap))
465 {
466 SUBHEAP *pPrev = &subheap->heap->subheap;
467 /* Remove the free block from the list */
468 pFree->next->prev = pFree->prev;
469 pFree->prev->next = pFree->next;
470 /* Remove the subheap from the list */
471 while (pPrev && (pPrev->next != subheap))
472 pPrev = pPrev->next;
473 if (pPrev)
474 pPrev->next = subheap->next;
475 /* Free the memory */
476 subheap->magic = 0;
477 ZwFreeVirtualMemory(NtCurrentProcess(),
478 (PVOID*)&subheap,
479 &dummySize,
480 MEM_RELEASE);
481 return;
482 }
483
484 /* Decommit the end of the heap */
485 }
486
487
488 /***********************************************************************
489 * HEAP_ShrinkBlock
490 *
491 * Shrink an in-use block.
492 */
493 static void HEAP_ShrinkBlock(SUBHEAP *subheap, ARENA_INUSE *pArena, ULONG size)
494 {
495 if ((pArena->size & ARENA_SIZE_MASK) >= size + HEAP_MIN_BLOCK_SIZE)
496 {
497 HEAP_CreateFreeBlock( subheap, (char *)(pArena + 1) + size,
498 (pArena->size & ARENA_SIZE_MASK) - size );
499 /* assign size plus previous arena flags */
500 pArena->size = size | (pArena->size & ~ARENA_SIZE_MASK);
501 }
502 else
503 {
504 /* Turn off PREV_FREE flag in next block */
505 char *pNext = (char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK);
506 if (pNext < (char *)subheap + subheap->size)
507 *(PULONG)pNext &= ~ARENA_FLAG_PREV_FREE;
508 }
509 }
510
511 /***********************************************************************
512 * HEAP_InitSubHeap
513 */
514 static BOOLEAN HEAP_InitSubHeap( HEAP *heap, PVOID address, ULONG flags,
515 ULONG commitSize, ULONG totalSize,
516 PRTL_HEAP_PARAMETERS Parameters )
517 {
518 SUBHEAP *subheap = (SUBHEAP *)address;
519 FREE_LIST_ENTRY *pEntry;
520 int i;
521 NTSTATUS Status;
522
523 /* Fill the sub-heap structure */
524
525 subheap = (PSUBHEAP)address;
526 subheap->heap = heap;
527 subheap->size = totalSize;
528 subheap->commitSize = commitSize;
529 subheap->magic = SUBHEAP_MAGIC;
530
531 if ( subheap != (SUBHEAP *)heap )
532 {
533 /* If this is a secondary subheap, insert it into list */
534
535 subheap->headerSize = sizeof(SUBHEAP);
536 subheap->next = heap->subheap.next;
537 heap->subheap.next = subheap;
538 }
539 else
540 {
541 /* If this is a primary subheap, initialize main heap */
542
543 subheap->headerSize = sizeof(HEAP);
544 subheap->next = NULL;
545 heap->next = NULL;
546 heap->flags = flags;
547 heap->magic = HEAP_MAGIC;
548 if (Parameters)
549 heap->commitRoutine = Parameters->CommitRoutine;
550 else
551 heap->commitRoutine = NULL;
552
553 /* Build the free lists */
554
555 for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
556 {
557 pEntry->size = HEAP_freeListSizes[i];
558 pEntry->arena.size = 0 | ARENA_FLAG_FREE;
559 pEntry->arena.next = i < HEAP_NB_FREE_LISTS-1 ?
560 &heap->freeList[i+1].arena : &heap->freeList[0].arena;
561 pEntry->arena.prev = i ? &heap->freeList[i-1].arena :
562 &heap->freeList[HEAP_NB_FREE_LISTS-1].arena;
563 pEntry->arena.threadId = 0;
564 pEntry->arena.magic = ARENA_FREE_MAGIC;
565 }
566
567 /* Initialize critical section */
568
569 RtlInitializeCriticalSection( &heap->critSection );
570 }
571
572 /* Commit memory */
573 if (heap->commitRoutine)
574 {
575 Status = heap->commitRoutine(heap, &address, &commitSize);
576 }
577 else
578 {
579 Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
580 &address,
581 0,
582 &commitSize,
583 MEM_COMMIT,
584 PAGE_EXECUTE_READWRITE);
585 }
586 if (!NT_SUCCESS(Status))
587 {
588 DPRINT("Could not commit %08lx bytes for sub-heap %p\n",
589 commitSize, address);
590 return FALSE;
591 }
592
593 /* Create the first free block */
594
595 HEAP_CreateFreeBlock( subheap, (PUCHAR)subheap + subheap->headerSize,
596 subheap->size - subheap->headerSize );
597
598 return TRUE;
599 }
600
601 /***********************************************************************
602 * HEAP_CreateSubHeap
603 *
604 * Create a sub-heap of the given size.
605 * If heap == NULL, creates a main heap.
606 */
607 static PSUBHEAP
608 HEAP_CreateSubHeap(PVOID BaseAddress,
609 HEAP *heap, ULONG flags,
610 ULONG commitSize, ULONG totalSize,
611 PRTL_HEAP_PARAMETERS Parameters )
612 {
613 PVOID address;
614 NTSTATUS Status;
615
616 /* Round-up sizes on a 64K boundary */
617
618 totalSize = (totalSize + 0xffff) & 0xffff0000;
619 commitSize = (commitSize + 0xffff) & 0xffff0000;
620 if (!commitSize)
621 commitSize = 0x10000;
622 if (totalSize < commitSize)
623 totalSize = commitSize;
624
625 /* Allocate the memory block */
626 address = BaseAddress;
627 if (!address)
628 {
629 Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
630 &address,
631 0,
632 (PULONG)&totalSize,
633 MEM_RESERVE | MEM_COMMIT,
634 PAGE_EXECUTE_READWRITE);
635 if (!NT_SUCCESS(Status))
636 {
637 DPRINT("Could not VirtualAlloc %08lx bytes\n",
638 totalSize );
639 return NULL;
640 }
641 }
642
643 /* Initialize subheap */
644
645 if (!HEAP_InitSubHeap( heap ? heap : (HEAP *)address,
646 address, flags, commitSize, totalSize,
647 Parameters ))
648 {
649 if (!BaseAddress)
650 {
651 ULONG dummySize = 0;
652 ZwFreeVirtualMemory(NtCurrentProcess(),
653 &address,
654 &dummySize,
655 MEM_RELEASE);
656 }
657 return NULL;
658 }
659
660 return (SUBHEAP *)address;
661 }
662
663
664 /***********************************************************************
665 * HEAP_FindFreeBlock
666 *
667 * Find a free block at least as large as the requested size, and make sure
668 * the requested size is committed.
669 */
670 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, ULONG size,
671 SUBHEAP **ppSubHeap )
672 {
673 SUBHEAP *subheap;
674 ARENA_FREE *pArena;
675 FREE_LIST_ENTRY *pEntry = heap->freeList;
676
677 /* Find a suitable free list, and in it find a block large enough */
678
679 while (pEntry->size < size)
680 pEntry++;
681 pArena = pEntry->arena.next;
682 while (pArena != &heap->freeList[0].arena)
683 {
684 ULONG arena_size = (pArena->size & ARENA_SIZE_MASK) +
685 sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
686 if (arena_size >= size)
687 {
688 subheap = HEAP_FindSubHeap( heap, pArena );
689 if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
690 + size + HEAP_MIN_BLOCK_SIZE,
691 heap->flags))
692 return NULL;
693 *ppSubHeap = subheap;
694 return pArena;
695 }
696
697 pArena = pArena->next;
698 }
699
700 /* If no block was found, attempt to grow the heap */
701
702 if (!(heap->flags & HEAP_GROWABLE))
703 {
704 DPRINT("Not enough space in heap %p for %08lx bytes\n",
705 heap, size );
706 return NULL;
707 }
708 /* make sure that we have a big enough size *committed* to fit another
709 * last free arena in !
710 * So just one heap struct, one first free arena which will eventually
711 * get inuse, and HEAP_MIN_BLOCK_SIZE for the second free arena that
712 * might get assigned all remaining free space in HEAP_ShrinkBlock() */
713 size += sizeof(SUBHEAP) + sizeof(ARENA_FREE) + HEAP_MIN_BLOCK_SIZE;
714 if (!(subheap = HEAP_CreateSubHeap( NULL, heap, heap->flags, size,
715 max( HEAP_DEF_SIZE, size ), NULL )))
716 return NULL;
717
718 DPRINT("created new sub-heap %p of %08lx bytes for heap %p\n",
719 subheap, size, heap );
720
721 *ppSubHeap = subheap;
722 return (ARENA_FREE *)(subheap + 1);
723 }
724
725
726 /***********************************************************************
727 * HEAP_IsValidArenaPtr
728 *
729 * Check that the pointer is inside the range possible for arenas.
730 */
731 static BOOLEAN HEAP_IsValidArenaPtr( HEAP *heap, PVOID ptr )
732 {
733 int i;
734 SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
735 if (!subheap)
736 return FALSE;
737 if ((char *)ptr >= (char *)subheap + subheap->headerSize)
738 return TRUE;
739 if (subheap != &heap->subheap)
740 return FALSE;
741 for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
742 if (ptr == (PVOID)&heap->freeList[i].arena)
743 return TRUE;
744 return FALSE;
745 }
746
747
748 /***********************************************************************
749 * HEAP_ValidateFreeArena
750 */
751 static BOOLEAN HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
752 {
753 char *heapEnd = (char *)subheap + subheap->size;
754
755 /* Check magic number */
756 if (pArena->magic != ARENA_FREE_MAGIC)
757 {
758 DPRINT("Heap %p: invalid free arena magic for %p\n",
759 subheap->heap, pArena);
760 return FALSE;
761 }
762 /* Check size flags */
763 if (!(pArena->size & ARENA_FLAG_FREE) ||
764 (pArena->size & ARENA_FLAG_PREV_FREE))
765 {
766 DPRINT("Heap %p: bad flags %lx for free arena %p\n",
767 subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena);
768 }
769 /* Check arena size */
770 if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
771 {
772 DPRINT("Heap %p: bad size %08lx for free arena %p\n",
773 subheap->heap, (ULONG)pArena->size & ARENA_SIZE_MASK, pArena );
774 return FALSE;
775 }
776 /* Check that next pointer is valid */
777 if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->next ))
778 {
779 DPRINT("Heap %p: bad next ptr %p for arena %p\n",
780 subheap->heap, pArena->next, pArena);
781 return FALSE;
782 }
783 /* Check that next arena is free */
784 if (!(pArena->next->size & ARENA_FLAG_FREE) ||
785 (pArena->next->magic != ARENA_FREE_MAGIC))
786 {
787 DPRINT("Heap %p: next arena %p invalid for %p\n",
788 subheap->heap, pArena->next, pArena);
789 return FALSE;
790 }
791 /* Check that prev pointer is valid */
792 if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->prev ))
793 {
794 DPRINT("Heap %p: bad prev ptr %p for arena %p\n",
795 subheap->heap, pArena->prev, pArena);
796 return FALSE;
797 }
798 /* Check that prev arena is free */
799 if (!(pArena->prev->size & ARENA_FLAG_FREE) ||
800 (pArena->prev->magic != ARENA_FREE_MAGIC))
801 {
802 DPRINT("Heap %p: prev arena %p invalid for %p\n",
803 subheap->heap, pArena->prev, pArena);
804 return FALSE;
805 }
806 /* Check that next block has PREV_FREE flag */
807 if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
808 {
809 if (!(*(PULONG)((char *)(pArena + 1) +
810 (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
811 {
812 DPRINT("Heap %p: free arena %p next block has no PREV_FREE flag\n",
813 subheap->heap, pArena);
814 return FALSE;
815 }
816 /* Check next block back pointer */
817 if (*((ARENA_FREE **)((char *)(pArena + 1) +
818 (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
819 {
820 DPRINT("Heap %p: arena %p has wrong back ptr %p\n",
821 subheap->heap, pArena,
822 *((PULONG)((char *)(pArena+1)+ (pArena->size & ARENA_SIZE_MASK)) - 1));
823 return FALSE;
824 }
825 }
826 return TRUE;
827 }
828
829
830 /***********************************************************************
831 * HEAP_ValidateInUseArena
832 */
833 static BOOLEAN HEAP_ValidateInUseArena( SUBHEAP *subheap, ARENA_INUSE *pArena, BOOLEAN quiet )
834 {
835 char *heapEnd = (char *)subheap + subheap->size;
836
837 /* Check magic number */
838 if (pArena->magic != ARENA_INUSE_MAGIC)
839 {
840 if (quiet == NOISY)
841 {
842 DPRINT("Heap %p: invalid in-use arena magic for %p\n",
843 subheap->heap, pArena);
844 if (TRACE_ON(heap))
845 HEAP_Dump( subheap->heap );
846 }
847 else if (WARN_ON(heap))
848 {
849 DPRINT("Heap %p: invalid in-use arena magic for %p\n",
850 subheap->heap, pArena);
851 if (TRACE_ON(heap))
852 HEAP_Dump( subheap->heap );
853 }
854 return FALSE;
855 }
856 /* Check size flags */
857 if (pArena->size & ARENA_FLAG_FREE)
858 {
859 DPRINT("Heap %p: bad flags %lx for in-use arena %p\n",
860 subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena);
861 return FALSE;
862 }
863 /* Check arena size */
864 if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
865 {
866 DPRINT("Heap %p: bad size %08lx for in-use arena %p\n",
867 subheap->heap, (ULONG)pArena->size & ARENA_SIZE_MASK, pArena);
868 return FALSE;
869 }
870 /* Check next arena PREV_FREE flag */
871 if (((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
872 (*(PULONG)((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
873 {
874 DPRINT("Heap %p: in-use arena %p next block has PREV_FREE flag\n",
875 subheap->heap, pArena);
876 return FALSE;
877 }
878 /* Check prev free arena */
879 if (pArena->size & ARENA_FLAG_PREV_FREE)
880 {
881 ARENA_FREE *pPrev = *((ARENA_FREE **)pArena - 1);
882 /* Check prev pointer */
883 if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
884 {
885 DPRINT("Heap %p: bad back ptr %p for arena %p\n",
886 subheap->heap, pPrev, pArena );
887 return FALSE;
888 }
889 /* Check that prev arena is free */
890 if (!(pPrev->size & ARENA_FLAG_FREE) ||
891 (pPrev->magic != ARENA_FREE_MAGIC))
892 {
893 DPRINT("Heap %p: prev arena %p invalid for in-use %p\n",
894 subheap->heap, pPrev, pArena);
895 return FALSE;
896 }
897 /* Check that prev arena is really the previous block */
898 if ((char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (char *)pArena)
899 {
900 DPRINT("Heap %p: prev arena %p is not prev for in-use %p\n",
901 subheap->heap, pPrev, pArena );
902 return FALSE;
903 }
904 }
905 return TRUE;
906 }
907
908
909 /***********************************************************************
910 * HEAP_IsInsideHeap
911 * Checks whether the pointer points to a block inside a given heap.
912 *
913 * NOTES
914 * Should this return BOOL32?
915 *
916 * RETURNS
917 * !0: Success
918 * 0: Failure
919 */
920 int HEAP_IsInsideHeap(
921 HANDLE heap, /* [in] Heap */
922 ULONG flags, /* [in] Flags */
923 PVOID ptr /* [in] Pointer */
924 )
925 {
926 HEAP *heapPtr = HEAP_GetPtr( heap );
927 SUBHEAP *subheap;
928 int ret;
929
930 /* Validate the parameters */
931
932 if (!heapPtr)
933 return 0;
934 flags |= heapPtr->flags;
935 if (!(flags & HEAP_NO_SERIALIZE))
936 RtlEnterCriticalSection( &heapPtr->critSection );
937 ret = (((subheap = HEAP_FindSubHeap( heapPtr, ptr )) != NULL) &&
938 (((char *)ptr >= (char *)subheap + subheap->headerSize
939 + sizeof(ARENA_INUSE))));
940 if (!(flags & HEAP_NO_SERIALIZE))
941 RtlLeaveCriticalSection( &heapPtr->critSection );
942 return ret;
943 }
944
945
946 void DumpStackFrames ( PULONG Frame, ULONG FrameCount )
947 {
948 ULONG i=0;
949
950 DbgPrint("Frames: ");
951 if ( !Frame )
952 {
953 #if defined __GNUC__
954 __asm__("mov %%ebp, %%ebx" : "=b" (Frame) : );
955 #elif defined(_MSC_VER)
956 __asm mov [Frame], ebp
957 #endif
958 Frame = (PULONG)Frame[0]; // step out of DumpStackFrames
959 }
960 while ( Frame != 0 && (ULONG)Frame != 0xDEADBEEF && (ULONG)Frame != 0xcdcdcdcd && (ULONG)Frame != 0xcccccccc && i++ < FrameCount )
961 {
962 DbgPrint("<%p>", (PVOID)Frame[1]);
963 if (Frame[1] == 0xdeadbeef)
964 break;
965 Frame = (PULONG)Frame[0];
966 DbgPrint(" ");
967 }
968 DbgPrint("\n");
969 }
970
971 /***********************************************************************
972 * HEAP_IsRealArena [Internal]
973 * Validates a block is a valid arena.
974 *
975 * RETURNS
976 * TRUE: Success
977 * FALSE: Failure
978 */
979 static BOOLEAN HEAP_IsRealArena(
980 HANDLE heap, /* [in] Handle to the heap */
981 ULONG flags, /* [in] Bit flags that control access during operation */
982 PVOID block, /* [in] Optional pointer to memory block to validate */
983 BOOLEAN quiet /* [in] Flag - if true, HEAP_ValidateInUseArena
984 * does not complain */
985 )
986 {
987 SUBHEAP *subheap;
988 HEAP *heapPtr = (HEAP *)(heap);
989 BOOLEAN ret = TRUE;
990
991 if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
992 {
993 DPRINT("Invalid heap %08x!\n", heap );
994 return FALSE;
995 }
996
997 flags &= HEAP_NO_SERIALIZE;
998 flags |= heapPtr->flags;
999 /* calling HeapLock may result in infinite recursion, so do the critsect directly */
1000 if (!(flags & HEAP_NO_SERIALIZE))
1001 RtlEnterCriticalSection( &heapPtr->critSection );
1002
1003 if (block)
1004 {
1005 /* Only check this single memory block */
1006
1007 /* The following code is really HEAP_IsInsideHeap *
1008 * with serialization already done. */
1009 if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
1010 ((char *)block < (char *)subheap + subheap->headerSize
1011 + sizeof(ARENA_INUSE)))
1012 {
1013 if (quiet == NOISY)
1014 {
1015 DPRINT("Heap %p: block %p is not inside heap\n",
1016 heap, block );
1017 DumpStackFrames(NULL,10);
1018 }
1019 else if (WARN_ON(heap))
1020 {
1021 DPRINT1("Heap %p: block %p is not inside heap\n",
1022 heap, block );
1023 DumpStackFrames(NULL,10);
1024 }
1025 ret = FALSE;
1026 }
1027 else
1028 ret = HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)block - 1, quiet );
1029
1030 if (!(flags & HEAP_NO_SERIALIZE))
1031 RtlLeaveCriticalSection( &heapPtr->critSection );
1032 return ret;
1033 }
1034
1035 subheap = &heapPtr->subheap;
1036 while (subheap && ret)
1037 {
1038 char *ptr = (char *)subheap + subheap->headerSize;
1039 while (ptr < (char *)subheap + subheap->size)
1040 {
1041 if (*(PULONG)ptr & ARENA_FLAG_FREE)
1042 {
1043 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr ))
1044 {
1045 ret = FALSE;
1046 break;
1047 }
1048 ptr += sizeof(ARENA_FREE) + (*(PULONG)ptr & ARENA_SIZE_MASK);
1049 }
1050 else
1051 {
1052 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY ))
1053 {
1054 ret = FALSE;
1055 break;
1056 }
1057 ptr += sizeof(ARENA_INUSE) + (*(PULONG)ptr & ARENA_SIZE_MASK);
1058 }
1059 }
1060 subheap = subheap->next;
1061 }
1062
1063 if (!(flags & HEAP_NO_SERIALIZE))
1064 RtlLeaveCriticalSection( &heapPtr->critSection );
1065 return ret;
1066 }
1067
1068
1069 /***********************************************************************
1070 * HeapCreate (KERNEL32.336)
1071 * RETURNS
1072 * Handle of heap: Success
1073 * NULL: Failure
1074 *
1075 * @implemented
1076 */
1077 HANDLE STDCALL
1078 RtlCreateHeap(ULONG flags,
1079 PVOID BaseAddress,
1080 SIZE_T maxSize,
1081 SIZE_T initialSize,
1082 PVOID Lock,
1083 PRTL_HEAP_PARAMETERS Parameters)
1084 {
1085 SUBHEAP *subheap;
1086 HEAP *heapPtr;
1087
1088 /* Allocate the heap block */
1089
1090 if (!maxSize)
1091 {
1092 maxSize = HEAP_DEF_SIZE;
1093 flags |= HEAP_GROWABLE;
1094 }
1095 if (!(subheap = HEAP_CreateSubHeap( BaseAddress, NULL, flags, initialSize,
1096 maxSize, Parameters )))
1097 {
1098 return 0;
1099 }
1100
1101 if (RtlpGetMode() == UserMode)
1102 {
1103 /* link it into the per-process heap list */
1104 RtlEnterCriticalSection (&RtlpProcessHeapsListLock);
1105
1106 heapPtr = subheap->heap;
1107 heapPtr->next = (HEAP*)NtCurrentPeb()->ProcessHeaps;
1108 NtCurrentPeb()->ProcessHeaps = (HANDLE)heapPtr;
1109 NtCurrentPeb()->NumberOfHeaps++;
1110
1111 RtlLeaveCriticalSection (&RtlpProcessHeapsListLock);
1112 }
1113
1114 return (HANDLE)subheap;
1115 }
1116
1117 /***********************************************************************
1118 * HeapDestroy (KERNEL32.337)
1119 * RETURNS
1120 * TRUE: Success
1121 * FALSE: Failure
1122 *
1123 * @implemented
1124 *
1125 * RETURNS
1126 * Success: A NULL HANDLE, if heap is NULL or it was destroyed
1127 * Failure: The Heap handle, if heap is the process heap.
1128 */
1129 HANDLE STDCALL
1130 RtlDestroyHeap(HANDLE heap) /* [in] Handle of heap */
1131 {
1132 HEAP *heapPtr = HEAP_GetPtr( heap );
1133 SUBHEAP *subheap;
1134 ULONG flags;
1135 HEAP **pptr;
1136
1137 DPRINT("%08x\n", heap );
1138 if (!heapPtr)
1139 return heap;
1140
1141 if (RtlpGetMode() == UserMode)
1142 {
1143 if (heap == NtCurrentPeb()->ProcessHeap)
1144 return heap; /* cannot delete the main process heap */
1145
1146 /* remove it from the per-process list */
1147 RtlEnterCriticalSection (&RtlpProcessHeapsListLock);
1148
1149 pptr = (HEAP**)&NtCurrentPeb()->ProcessHeaps;
1150 while (*pptr && *pptr != heapPtr) pptr = &(*pptr)->next;
1151 if (*pptr) *pptr = (*pptr)->next;
1152 NtCurrentPeb()->NumberOfHeaps--;
1153
1154 RtlLeaveCriticalSection (&RtlpProcessHeapsListLock);
1155 }
1156
1157 RtlDeleteCriticalSection( &heapPtr->critSection );
1158 subheap = &heapPtr->subheap;
1159 // We must save the flags. The first subheap is located after
1160 // the heap structure. If we release the first subheap,
1161 // we release also the heap structure.
1162 flags = heapPtr->flags;
1163 while (subheap)
1164 {
1165 SUBHEAP *next = subheap->next;
1166 ULONG dummySize = 0;
1167 ZwFreeVirtualMemory(NtCurrentProcess(),
1168 (PVOID*)&subheap,
1169 &dummySize,
1170 MEM_RELEASE);
1171 subheap = next;
1172 }
1173 return (HANDLE)NULL;
1174 }
1175
1176
1177 /***********************************************************************
1178 * HeapAlloc (KERNEL32.334)
1179 * RETURNS
1180 * Pointer to allocated memory block
1181 * NULL: Failure
1182 * 0x7d030f60--invalid flags in RtlHeapAllocate
1183 * @implemented
1184 */
1185 PVOID STDCALL
1186 RtlAllocateHeap(HANDLE heap, /* [in] Handle of private heap block */
1187 ULONG flags, /* [in] Heap allocation control flags */
1188 ULONG size) /* [in] Number of bytes to allocate */
1189 {
1190 ARENA_FREE *pArena;
1191 ARENA_INUSE *pInUse;
1192 SUBHEAP *subheap;
1193 HEAP *heapPtr = HEAP_GetPtr( heap );
1194
1195 /* Validate the parameters */
1196
1197 if (!heapPtr)
1198 {
1199 if (flags & HEAP_GENERATE_EXCEPTIONS)
1200 RtlRaiseStatus( STATUS_NO_MEMORY );
1201 return NULL;
1202 }
1203 flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1204 flags |= heapPtr->flags;
1205 if (!(flags & HEAP_NO_SERIALIZE))
1206 RtlEnterCriticalSection( &heapPtr->critSection );
1207 size = (size + 7) & ~7;
1208 if (size < HEAP_MIN_BLOCK_SIZE)
1209 size = HEAP_MIN_BLOCK_SIZE;
1210
1211 /* Locate a suitable free block */
1212
1213 if (!(pArena = HEAP_FindFreeBlock( heapPtr, size, &subheap )))
1214 {
1215 DPRINT("(%08x,%08lx,%08lx): returning NULL\n",
1216 heap, flags, size );
1217 if (!(flags & HEAP_NO_SERIALIZE))
1218 RtlLeaveCriticalSection( &heapPtr->critSection );
1219 if (flags & HEAP_GENERATE_EXCEPTIONS)
1220 RtlRaiseStatus( STATUS_NO_MEMORY );
1221 return NULL;
1222 }
1223
1224 /* Remove the arena from the free list */
1225
1226 pArena->next->prev = pArena->prev;
1227 pArena->prev->next = pArena->next;
1228
1229 /* Build the in-use arena */
1230
1231 pInUse = (ARENA_INUSE *)pArena;
1232 pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
1233 + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1234 pInUse->threadId = (ULONG)NtCurrentTeb()->Cid.UniqueThread;
1235 pInUse->magic = ARENA_INUSE_MAGIC;
1236
1237 /* Shrink the block */
1238
1239 HEAP_ShrinkBlock( subheap, pInUse, size );
1240
1241 if (flags & HEAP_ZERO_MEMORY)
1242 memset( pInUse + 1, 0, pInUse->size & ARENA_SIZE_MASK );
1243 else if (TRACE_ON(heap))
1244 memset( pInUse + 1, ARENA_INUSE_FILLER, pInUse->size & ARENA_SIZE_MASK );
1245
1246 if (!(flags & HEAP_NO_SERIALIZE))
1247 RtlLeaveCriticalSection( &heapPtr->critSection );
1248
1249 DPRINT("(%08x,%08lx,%08lx): returning %p\n",
1250 heap, flags, size, (PVOID)(pInUse + 1) );
1251 return (PVOID)(pInUse + 1);
1252 }
1253
1254
1255 /***********************************************************************
1256 * HeapFree (KERNEL32.338)
1257 * RETURNS
1258 * TRUE: Success
1259 * FALSE: Failure
1260 *
1261 * @implemented
1262 */
1263 BOOLEAN STDCALL RtlFreeHeap(
1264 HANDLE heap, /* [in] Handle of heap */
1265 ULONG flags, /* [in] Heap freeing flags */
1266 PVOID ptr /* [in] Address of memory to free */
1267 )
1268 {
1269 ARENA_INUSE *pInUse;
1270 SUBHEAP *subheap;
1271 HEAP *heapPtr = HEAP_GetPtr( heap );
1272
1273 /* Validate the parameters */
1274
1275 if (!heapPtr)
1276 return FALSE;
1277 if (!ptr) /* Freeing a NULL ptr is doesn't indicate an error in Win2k */
1278 {
1279 DPRINT("(%08x,%08lx,%p): asked to free NULL\n",
1280 heap, flags, ptr );
1281 return TRUE;
1282 }
1283
1284 flags &= HEAP_NO_SERIALIZE;
1285 flags |= heapPtr->flags;
1286 if (!(flags & HEAP_NO_SERIALIZE))
1287 RtlEnterCriticalSection( &heapPtr->critSection );
1288 if (!HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1289 {
1290 if (!(flags & HEAP_NO_SERIALIZE))
1291 RtlLeaveCriticalSection( &heapPtr->critSection );
1292 DPRINT("(%08x,%08lx,%p): returning FALSE\n",
1293 heap, flags, ptr );
1294 return FALSE;
1295 }
1296
1297 /* Turn the block into a free block */
1298
1299 pInUse = (ARENA_INUSE *)ptr - 1;
1300 subheap = HEAP_FindSubHeap( heapPtr, pInUse );
1301 HEAP_MakeInUseBlockFree( subheap, pInUse, heapPtr->flags );
1302
1303 if (!(flags & HEAP_NO_SERIALIZE))
1304 RtlLeaveCriticalSection( &heapPtr->critSection );
1305
1306 DPRINT("(%08x,%08lx,%p): returning TRUE\n",
1307 heap, flags, ptr );
1308 return TRUE;
1309 }
1310
1311
1312 /***********************************************************************
1313 * RtlReAllocateHeap
1314 * PARAMS
1315 * Heap [in] Handle of heap block
1316 * Flags [in] Heap reallocation flags
1317 * Ptr, [in] Address of memory to reallocate
1318 * Size [in] Number of bytes to reallocate
1319 *
1320 * RETURNS
1321 * Pointer to reallocated memory block
1322 * NULL: Failure
1323 * 0x7d030f60--invalid flags in RtlHeapAllocate
1324 * @implemented
1325 */
1326 PVOID STDCALL RtlReAllocateHeap(
1327 HANDLE Heap,
1328 ULONG Flags,
1329 PVOID Ptr,
1330 ULONG Size
1331 )
1332 {
1333 ARENA_INUSE *pArena;
1334 ULONG oldSize;
1335 HEAP *heapPtr;
1336 SUBHEAP *subheap;
1337
1338 if (!Ptr)
1339 return FALSE;
1340 if (!(heapPtr = HEAP_GetPtr( Heap )))
1341 return FALSE;
1342
1343 /* Validate the parameters */
1344
1345 Flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY |
1346 HEAP_REALLOC_IN_PLACE_ONLY;
1347 Flags |= heapPtr->flags;
1348 Size = (Size + 7) & ~7;
1349 if (Size < HEAP_MIN_BLOCK_SIZE)
1350 Size = HEAP_MIN_BLOCK_SIZE;
1351
1352 if (!(Flags & HEAP_NO_SERIALIZE))
1353 RtlEnterCriticalSection( &heapPtr->critSection );
1354 if (!HEAP_IsRealArena( Heap, HEAP_NO_SERIALIZE, Ptr, QUIET ))
1355 {
1356 if (!(Flags & HEAP_NO_SERIALIZE))
1357 RtlLeaveCriticalSection( &heapPtr->critSection );
1358 DPRINT("(%08x,%08lx,%p,%08lx): returning NULL\n",
1359 Heap, Flags, Ptr, Size );
1360 if (Flags & HEAP_GENERATE_EXCEPTIONS)
1361 RtlRaiseStatus( STATUS_NO_MEMORY );
1362 return NULL;
1363 }
1364
1365 /* Check if we need to grow the block */
1366
1367 pArena = (ARENA_INUSE *)Ptr - 1;
1368 pArena->threadId = (ULONG)NtCurrentTeb()->Cid.UniqueThread;
1369
1370 subheap = HEAP_FindSubHeap( heapPtr, pArena );
1371 oldSize = (pArena->size & ARENA_SIZE_MASK);
1372 if (Size > oldSize)
1373 {
1374 char *pNext = (char *)(pArena + 1) + oldSize;
1375 if ((pNext < (char *)subheap + subheap->size) &&
1376 (*(PULONG)pNext & ARENA_FLAG_FREE) &&
1377 (oldSize + (*(PULONG)pNext & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) >= Size))
1378 {
1379 /* The next block is free and large enough */
1380 ARENA_FREE *pFree = (ARENA_FREE *)pNext;
1381 pFree->next->prev = pFree->prev;
1382 pFree->prev->next = pFree->next;
1383 pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
1384 if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
1385 + Size + HEAP_MIN_BLOCK_SIZE,
1386 heapPtr->flags))
1387 {
1388 if (!(Flags & HEAP_NO_SERIALIZE))
1389 RtlLeaveCriticalSection( &heapPtr->critSection );
1390 if (Flags & HEAP_GENERATE_EXCEPTIONS)
1391 RtlRaiseStatus( STATUS_NO_MEMORY );
1392 return NULL;
1393 }
1394 HEAP_ShrinkBlock( subheap, pArena, Size );
1395 }
1396 else /* Do it the hard way */
1397 {
1398 ARENA_FREE *pNew;
1399 ARENA_INUSE *pInUse;
1400 SUBHEAP *newsubheap;
1401
1402 if ((Flags & HEAP_REALLOC_IN_PLACE_ONLY) ||
1403 !(pNew = HEAP_FindFreeBlock( heapPtr, Size, &newsubheap )))
1404 {
1405 if (!(Flags & HEAP_NO_SERIALIZE))
1406 RtlLeaveCriticalSection( &heapPtr->critSection );
1407 if (Flags & HEAP_GENERATE_EXCEPTIONS)
1408 RtlRaiseStatus( STATUS_NO_MEMORY );
1409 return NULL;
1410 }
1411
1412 /* Build the in-use arena */
1413
1414 pNew->next->prev = pNew->prev;
1415 pNew->prev->next = pNew->next;
1416 pInUse = (ARENA_INUSE *)pNew;
1417 pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
1418 + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1419 pInUse->threadId = (ULONG)NtCurrentTeb()->Cid.UniqueThread;
1420 pInUse->magic = ARENA_INUSE_MAGIC;
1421 HEAP_ShrinkBlock( newsubheap, pInUse, Size );
1422 memcpy( pInUse + 1, pArena + 1, oldSize );
1423
1424 /* Free the previous block */
1425
1426 HEAP_MakeInUseBlockFree( subheap, pArena, Flags );
1427 subheap = newsubheap;
1428 pArena = pInUse;
1429 }
1430 }
1431 else
1432 HEAP_ShrinkBlock( subheap, pArena, Size ); /* Shrink the block */
1433
1434 /* Clear the extra bytes if needed */
1435
1436 if (Size > oldSize)
1437 {
1438 if (Flags & HEAP_ZERO_MEMORY)
1439 memset( (char *)(pArena + 1) + oldSize, 0,
1440 (pArena->size & ARENA_SIZE_MASK) - oldSize );
1441 else if (TRACE_ON(heap))
1442 memset( (char *)(pArena + 1) + oldSize, ARENA_INUSE_FILLER,
1443 (pArena->size & ARENA_SIZE_MASK) - oldSize );
1444 }
1445
1446 /* Return the new arena */
1447
1448 if (!(Flags & HEAP_NO_SERIALIZE))
1449 RtlLeaveCriticalSection( &heapPtr->critSection );
1450
1451 DPRINT("(%08x,%08lx,%p,%08lx): returning %p\n",
1452 Heap, Flags, Ptr, Size, (PVOID)(pArena + 1) );
1453 return (PVOID)(pArena + 1);
1454 }
1455
1456
1457 /***********************************************************************
1458 * RtlCompactHeap
1459 *
1460 * @unimplemented
1461 */
1462 ULONG STDCALL
1463 RtlCompactHeap(HANDLE Heap,
1464 ULONG Flags)
1465 {
1466 UNIMPLEMENTED;
1467 return 0;
1468 }
1469
1470
1471 /***********************************************************************
1472 * RtlLockHeap
1473 * Attempts to acquire the critical section object for a specified heap.
1474 *
1475 * PARAMS
1476 * Heap [in] Handle of heap to lock for exclusive access
1477 *
1478 * RETURNS
1479 * TRUE: Success
1480 * FALSE: Failure
1481 *
1482 * @implemented
1483 */
1484 BOOLEAN STDCALL
1485 RtlLockHeap(IN HANDLE Heap)
1486 {
1487 HEAP *heapPtr = HEAP_GetPtr( Heap );
1488 if (!heapPtr)
1489 return FALSE;
1490 RtlEnterCriticalSection( &heapPtr->critSection );
1491 return TRUE;
1492 }
1493
1494
1495 /***********************************************************************
1496 * RtlUnlockHeap
1497 * Releases ownership of the critical section object.
1498 *
1499 * PARAMS
1500 * Heap [in] Handle to the heap to unlock
1501 *
1502 * RETURNS
1503 * TRUE: Success
1504 * FALSE: Failure
1505 *
1506 * @implemented
1507 */
1508 BOOLEAN STDCALL
1509 RtlUnlockHeap(HANDLE Heap)
1510 {
1511 HEAP *heapPtr = HEAP_GetPtr( Heap );
1512 if (!heapPtr)
1513 return FALSE;
1514 RtlLeaveCriticalSection( &heapPtr->critSection );
1515 return TRUE;
1516 }
1517
1518
1519 /***********************************************************************
1520 * RtlSizeHeap
1521 * PARAMS
1522 * Heap [in] Handle of heap
1523 * Flags [in] Heap size control flags
1524 * Ptr [in] Address of memory to return size for
1525 *
1526 * RETURNS
1527 * Size in bytes of allocated memory
1528 * 0xffffffff: Failure
1529 *
1530 * @implemented
1531 */
1532 ULONG STDCALL
1533 RtlSizeHeap(
1534 HANDLE Heap,
1535 ULONG Flags,
1536 PVOID Ptr
1537 )
1538 {
1539 ULONG ret;
1540 HEAP *heapPtr = HEAP_GetPtr( Heap );
1541
1542 if (!heapPtr)
1543 return 0;
1544 Flags &= HEAP_NO_SERIALIZE;
1545 Flags |= heapPtr->flags;
1546 if (!(Flags & HEAP_NO_SERIALIZE))
1547 RtlEnterCriticalSection( &heapPtr->critSection );
1548 if (!HEAP_IsRealArena( Heap, HEAP_NO_SERIALIZE, Ptr, QUIET ))
1549 {
1550 ret = 0xffffffff;
1551 }
1552 else
1553 {
1554 ARENA_INUSE *pArena = (ARENA_INUSE *)Ptr - 1;
1555 ret = pArena->size & ARENA_SIZE_MASK;
1556 }
1557 if (!(Flags & HEAP_NO_SERIALIZE))
1558 RtlLeaveCriticalSection( &heapPtr->critSection );
1559
1560 DPRINT("(%08x,%08lx,%p): returning %08lx\n",
1561 Heap, Flags, Ptr, ret );
1562 return ret;
1563 }
1564
1565
1566 /***********************************************************************
1567 * RtlValidateHeap
1568 * Validates a specified heap.
1569 *
1570 * PARAMS
1571 * Heap [in] Handle to the heap
1572 * Flags [in] Bit flags that control access during operation
1573 * Block [in] Optional pointer to memory block to validate
1574 *
1575 * NOTES
1576 * Flags is ignored.
1577 *
1578 * RETURNS
1579 * TRUE: Success
1580 * FALSE: Failure
1581 *
1582 * @implemented
1583 */
1584 BOOLEAN STDCALL RtlValidateHeap(
1585 HANDLE Heap,
1586 ULONG Flags,
1587 PVOID Block
1588 )
1589 {
1590 HEAP *heapPtr = HEAP_GetPtr( Heap );
1591 if (!heapPtr)
1592 return FALSE;
1593 return HEAP_IsRealArena( heapPtr, Flags, Block, QUIET );
1594 }
1595
1596
1597 /***********************************************************************
1598 * HeapWalk (KERNEL32.344)
1599 * Enumerates the memory blocks in a specified heap.
1600 * See HEAP_Dump() for info on heap structure.
1601 *
1602 * TODO
1603 * - handling of PROCESS_HEAP_ENTRY_MOVEABLE and
1604 * PROCESS_HEAP_ENTRY_DDESHARE (needs heap.c support)
1605 *
1606 * RETURNS
1607 * TRUE: Success
1608 * FALSE: Failure
1609 */
1610 #if 0
1611 BOOLEAN STDCALL HeapWalk(
1612 HANDLE heap, /* [in] Handle to heap to enumerate */
1613 LPPROCESS_HEAP_ENTRY entry /* [out] Pointer to structure of enumeration info */
1614 )
1615 {
1616 HEAP *heapPtr = HEAP_GetPtr(heap);
1617 SUBHEAP *sub, *currentheap = NULL;
1618 BOOLEAN ret = FALSE;
1619 char *ptr;
1620 int region_index = 0;
1621
1622 if (!heapPtr || !entry)
1623 {
1624 return FALSE;
1625 }
1626
1627 if (!(heapPtr->flags & HEAP_NO_SERIALIZE))
1628 RtlEnterCriticalSection( &heapPtr->critSection );
1629
1630 /* set ptr to the next arena to be examined */
1631
1632 if (!entry->lpData) /* first call (init) ? */
1633 {
1634 DPRINT("begin walking of heap 0x%08x.\n", heap);
1635 /*HEAP_Dump(heapPtr);*/
1636 currentheap = &heapPtr->subheap;
1637 ptr = (char*)currentheap + currentheap->headerSize;
1638 }
1639 else
1640 {
1641 ptr = entry->lpData;
1642 sub = &heapPtr->subheap;
1643 while (sub)
1644 {
1645 if (((char *)ptr >= (char *)sub) &&
1646 ((char *)ptr < (char *)sub + sub->size))
1647 {
1648 currentheap = sub;
1649 break;
1650 }
1651 sub = sub->next;
1652 region_index++;
1653 }
1654 if (currentheap == NULL)
1655 {
1656 DPRINT("no matching subheap found, shouldn't happen !\n");
1657 goto HW_end;
1658 }
1659
1660 ptr += entry->cbData; /* point to next arena */
1661 if (ptr > (char *)currentheap + currentheap->size - 1)
1662 { /* proceed with next subheap */
1663 if (!(currentheap = currentheap->next))
1664 { /* successfully finished */
1665 DPRINT("end reached.\n");
1666 goto HW_end;
1667 }
1668 ptr = (char*)currentheap + currentheap->headerSize;
1669 }
1670 }
1671
1672 entry->wFlags = 0;
1673 if (*(PULONG)ptr & ARENA_FLAG_FREE)
1674 {
1675 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
1676
1677 /*DPRINT("free, magic: %04x\n", pArena->magic);*/
1678
1679 entry->lpData = pArena + 1;
1680 entry->cbData = pArena->size & ARENA_SIZE_MASK;
1681 entry->cbOverhead = sizeof(ARENA_FREE);
1682 entry->wFlags = PROCESS_HEAP_UNCOMMITTED_RANGE;
1683 }
1684 else
1685 {
1686 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
1687
1688 /*DPRINT("busy, magic: %04x\n", pArena->magic);*/
1689
1690 entry->lpData = pArena + 1;
1691 entry->cbData = pArena->size & ARENA_SIZE_MASK;
1692 entry->cbOverhead = sizeof(ARENA_INUSE);
1693 entry->wFlags = PROCESS_HEAP_ENTRY_BUSY;
1694 /* FIXME: can't handle PROCESS_HEAP_ENTRY_MOVEABLE
1695 and PROCESS_HEAP_ENTRY_DDESHARE yet */
1696 }
1697
1698 entry->iRegionIndex = region_index;
1699
1700 /* first element of heap ? */
1701 if (ptr == (char *)(currentheap + currentheap->headerSize))
1702 {
1703 entry->wFlags |= PROCESS_HEAP_REGION;
1704 entry->Foo.Region.dwCommittedSize = currentheap->commitSize;
1705 entry->Foo.Region.dwUnCommittedSize =
1706 currentheap->size - currentheap->commitSize;
1707 entry->Foo.Region.lpFirstBlock = /* first valid block */
1708 currentheap + currentheap->headerSize;
1709 entry->Foo.Region.lpLastBlock = /* first invalid block */
1710 currentheap + currentheap->size;
1711 }
1712 ret = TRUE;
1713
1714 HW_end:
1715 if (!(heapPtr->flags & HEAP_NO_SERIALIZE))
1716 RtlLeaveCriticalSection( &heapPtr->critSection );
1717
1718 return ret;
1719 }
1720 #endif
1721
1722
1723 VOID
1724 RtlInitializeHeapManager(VOID)
1725 {
1726 PPEB Peb;
1727
1728 Peb = NtCurrentPeb();
1729
1730 Peb->NumberOfHeaps = 0;
1731 Peb->MaximumNumberOfHeaps = -1; /* no limit */
1732 Peb->ProcessHeaps = NULL;
1733
1734 RtlInitializeCriticalSection(&RtlpProcessHeapsListLock);
1735 }
1736
1737
1738 /*
1739 * @implemented
1740 */
1741 NTSTATUS STDCALL
1742 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine,
1743 PVOID lParam)
1744 {
1745 NTSTATUS Status = STATUS_SUCCESS;
1746 HEAP** pptr;
1747
1748 RtlEnterCriticalSection(&RtlpProcessHeapsListLock);
1749
1750 for (pptr = (HEAP**)&NtCurrentPeb()->ProcessHeaps; *pptr; pptr = &(*pptr)->next)
1751 {
1752 Status = HeapEnumerationRoutine(*pptr,lParam);
1753 if (!NT_SUCCESS(Status))
1754 break;
1755 }
1756
1757 RtlLeaveCriticalSection(&RtlpProcessHeapsListLock);
1758
1759 return Status;
1760 }
1761
1762
1763 /*
1764 * @implemented
1765 */
1766 ULONG STDCALL
1767 RtlGetProcessHeaps(ULONG HeapCount,
1768 HANDLE *HeapArray)
1769 {
1770 ULONG Result = 0;
1771 HEAP ** pptr;
1772
1773 RtlEnterCriticalSection(&RtlpProcessHeapsListLock);
1774
1775 Result = NtCurrentPeb()->NumberOfHeaps;
1776
1777 if (NtCurrentPeb()->NumberOfHeaps <= HeapCount)
1778 {
1779 int i = 0;
1780 for (pptr = (HEAP**)&NtCurrentPeb()->ProcessHeaps; *pptr; pptr = &(*pptr)->next)
1781 {
1782 HeapArray[i++] = *pptr;
1783 }
1784 }
1785
1786 RtlLeaveCriticalSection (&RtlpProcessHeapsListLock);
1787
1788 return Result;
1789 }
1790
1791
1792 /*
1793 * @implemented
1794 */
1795 BOOLEAN STDCALL
1796 RtlValidateProcessHeaps(VOID)
1797 {
1798 BOOLEAN Result = TRUE;
1799 HEAP ** pptr;
1800
1801 RtlEnterCriticalSection(&RtlpProcessHeapsListLock);
1802
1803 for (pptr = (HEAP**)&NtCurrentPeb()->ProcessHeaps; *pptr; pptr = &(*pptr)->next)
1804 {
1805 if (!RtlValidateHeap(*pptr, 0, NULL))
1806 {
1807 Result = FALSE;
1808 break;
1809 }
1810 }
1811
1812 RtlLeaveCriticalSection (&RtlpProcessHeapsListLock);
1813
1814 return Result;
1815 }
1816
1817
1818 /*
1819 * @unimplemented
1820 */
1821 BOOLEAN STDCALL
1822 RtlZeroHeap(
1823 IN PVOID HeapHandle,
1824 IN ULONG Flags
1825 )
1826 {
1827 UNIMPLEMENTED;
1828 return FALSE;
1829 }
1830
1831 /* EOF */