advapi32: LookupAccountSid buffer size query tests.
[wine] / dlls / ntdll / heap.c
1 /*
2  * Win32 heap functions
3  *
4  * Copyright 1996 Alexandre Julliard
5  * Copyright 1998 Ulrich Weigand
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20  */
21
22 #include "config.h"
23
24 #include <assert.h>
25 #include <stdlib.h>
26 #include <stdarg.h>
27 #include <stdio.h>
28 #include <string.h>
29 #ifdef HAVE_VALGRIND_MEMCHECK_H
30 #include <valgrind/memcheck.h>
31 #endif
32
33 #define NONAMELESSUNION
34 #define NONAMELESSSTRUCT
35 #include "ntstatus.h"
36 #define WIN32_NO_STATUS
37 #include "windef.h"
38 #include "winternl.h"
39 #include "winnt.h"
40 #include "winternl.h"
41 #include "wine/list.h"
42 #include "wine/debug.h"
43 #include "wine/server.h"
44
45 WINE_DEFAULT_DEBUG_CHANNEL(heap);
46
47 /* Note: the heap data structures are based on what Pietrek describes in his
48  * book 'Windows 95 System Programming Secrets'. The layout is not exactly
49  * the same, but could be easily adapted if it turns out some programs
50  * require it.
51  */
52
53 /* FIXME: use SIZE_T for 'size' structure members, but we need to make sure
54  * that there is no unaligned accesses to structure fields.
55  */
56
57 typedef struct tagARENA_INUSE
58 {
59     DWORD  size;                    /* Block size; must be the first field */
60     DWORD  magic : 24;              /* Magic number */
61     DWORD  unused_bytes : 8;        /* Number of bytes in the block not used by user data (max value is HEAP_MIN_DATA_SIZE+HEAP_MIN_SHRINK_SIZE) */
62 } ARENA_INUSE;
63
64 typedef struct tagARENA_FREE
65 {
66     DWORD                 size;     /* Block size; must be the first field */
67     DWORD                 magic;    /* Magic number */
68     struct list           entry;    /* Entry in free list */
69 } ARENA_FREE;
70
71 #define ARENA_FLAG_FREE        0x00000001  /* flags OR'ed with arena size */
72 #define ARENA_FLAG_PREV_FREE   0x00000002
73 #define ARENA_SIZE_MASK        (~3)
74 #define ARENA_INUSE_MAGIC      0x455355        /* Value for arena 'magic' field */
75 #define ARENA_FREE_MAGIC       0x45455246      /* Value for arena 'magic' field */
76
77 #define ARENA_INUSE_FILLER     0x55
78 #define ARENA_FREE_FILLER      0xaa
79
80 #define ALIGNMENT              8   /* everything is aligned on 8 byte boundaries */
81 #define ROUND_SIZE(size)       (((size) + ALIGNMENT - 1) & ~(ALIGNMENT-1))
82
83 #define QUIET                  1           /* Suppress messages  */
84 #define NOISY                  0           /* Report all errors  */
85
86 /* minimum data size (without arenas) of an allocated block */
87 /* make sure that it's larger than a free list entry */
88 #define HEAP_MIN_DATA_SIZE    (2 * sizeof(struct list))
89 /* minimum size that must remain to shrink an allocated block */
90 #define HEAP_MIN_SHRINK_SIZE  (HEAP_MIN_DATA_SIZE+sizeof(ARENA_FREE))
91
92 /* Max size of the blocks on the free lists */
93 static const DWORD HEAP_freeListSizes[] =
94 {
95     0x10, 0x20, 0x30, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x1000, ~0UL
96 };
97 #define HEAP_NB_FREE_LISTS  (sizeof(HEAP_freeListSizes)/sizeof(HEAP_freeListSizes[0]))
98
99 typedef struct
100 {
101     ARENA_FREE  arena;
102 } FREE_LIST_ENTRY;
103
104 struct tagHEAP;
105
106 typedef struct tagSUBHEAP
107 {
108     DWORD               size;       /* Size of the whole sub-heap */
109     DWORD               commitSize; /* Committed size of the sub-heap */
110     DWORD               headerSize; /* Size of the heap header */
111     struct tagSUBHEAP  *next;       /* Next sub-heap */
112     struct tagHEAP     *heap;       /* Main heap structure */
113     DWORD               magic;      /* Magic number */
114 } SUBHEAP;
115
116 #define SUBHEAP_MAGIC    ((DWORD)('S' | ('U'<<8) | ('B'<<16) | ('H'<<24)))
117
118 typedef struct tagHEAP
119 {
120     SUBHEAP          subheap;       /* First sub-heap */
121     struct list      entry;         /* Entry in process heap list */
122     RTL_CRITICAL_SECTION critSection; /* Critical section for serialization */
123     FREE_LIST_ENTRY  freeList[HEAP_NB_FREE_LISTS];  /* Free lists */
124     DWORD            flags;         /* Heap flags */
125     DWORD            magic;         /* Magic number */
126 } HEAP;
127
128 #define HEAP_MAGIC       ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
129
130 #define HEAP_DEF_SIZE        0x110000   /* Default heap size = 1Mb + 64Kb */
131 #define COMMIT_MASK          0xffff  /* bitmask for commit/decommit granularity */
132
133 static HEAP *processHeap;  /* main process heap */
134
135 static BOOL HEAP_IsRealArena( HEAP *heapPtr, DWORD flags, LPCVOID block, BOOL quiet );
136
137 /* mark a block of memory as free for debugging purposes */
138 static inline void mark_block_free( void *ptr, SIZE_T size )
139 {
140     if (TRACE_ON(heap)) memset( ptr, ARENA_FREE_FILLER, size );
141 #ifdef VALGRIND_MAKE_NOACCESS
142     VALGRIND_DISCARD( VALGRIND_MAKE_NOACCESS( ptr, size ));
143 #endif
144 }
145
146 /* mark a block of memory as initialized for debugging purposes */
147 static inline void mark_block_initialized( void *ptr, SIZE_T size )
148 {
149 #ifdef VALGRIND_MAKE_READABLE
150     VALGRIND_DISCARD( VALGRIND_MAKE_READABLE( ptr, size ));
151 #endif
152 }
153
154 /* mark a block of memory as uninitialized for debugging purposes */
155 static inline void mark_block_uninitialized( void *ptr, SIZE_T size )
156 {
157 #ifdef VALGRIND_MAKE_WRITABLE
158     VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
159 #endif
160     if (TRACE_ON(heap))
161     {
162         memset( ptr, ARENA_INUSE_FILLER, size );
163 #ifdef VALGRIND_MAKE_WRITABLE
164         /* make it uninitialized to valgrind again */
165         VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
166 #endif
167     }
168 }
169
170 /* clear contents of a block of memory */
171 static inline void clear_block( void *ptr, SIZE_T size )
172 {
173     mark_block_initialized( ptr, size );
174     memset( ptr, 0, size );
175 }
176
177 /* locate a free list entry of the appropriate size */
178 /* size is the size of the whole block including the arena header */
179 static inline unsigned int get_freelist_index( SIZE_T size )
180 {
181     unsigned int i;
182
183     size -= sizeof(ARENA_FREE);
184     for (i = 0; i < HEAP_NB_FREE_LISTS - 1; i++) if (size <= HEAP_freeListSizes[i]) break;
185     return i;
186 }
187
188 static RTL_CRITICAL_SECTION_DEBUG process_heap_critsect_debug =
189 {
190     0, 0, NULL,  /* will be set later */
191     { &process_heap_critsect_debug.ProcessLocksList, &process_heap_critsect_debug.ProcessLocksList },
192       0, 0, { (DWORD_PTR)(__FILE__ ": main process heap section") }
193 };
194
195
196 /***********************************************************************
197  *           HEAP_Dump
198  */
199 static void HEAP_Dump( HEAP *heap )
200 {
201     int i;
202     SUBHEAP *subheap;
203     char *ptr;
204
205     DPRINTF( "Heap: %p\n", heap );
206     DPRINTF( "Next: %p  Sub-heaps: %p",
207              LIST_ENTRY( heap->entry.next, HEAP, entry ), &heap->subheap );
208     subheap = &heap->subheap;
209     while (subheap->next)
210     {
211         DPRINTF( " -> %p", subheap->next );
212         subheap = subheap->next;
213     }
214
215     DPRINTF( "\nFree lists:\n Block   Stat   Size    Id\n" );
216     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
217         DPRINTF( "%p free %08lx prev=%p next=%p\n",
218                  &heap->freeList[i].arena, HEAP_freeListSizes[i],
219                  LIST_ENTRY( heap->freeList[i].arena.entry.prev, ARENA_FREE, entry ),
220                  LIST_ENTRY( heap->freeList[i].arena.entry.next, ARENA_FREE, entry ));
221
222     subheap = &heap->subheap;
223     while (subheap)
224     {
225         SIZE_T freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
226         DPRINTF( "\n\nSub-heap %p: size=%08lx committed=%08lx\n",
227                 subheap, subheap->size, subheap->commitSize );
228
229         DPRINTF( "\n Block   Stat   Size    Id\n" );
230         ptr = (char*)subheap + subheap->headerSize;
231         while (ptr < (char *)subheap + subheap->size)
232         {
233             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
234             {
235                 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
236                 DPRINTF( "%p free %08lx prev=%p next=%p\n",
237                          pArena, pArena->size & ARENA_SIZE_MASK,
238                          LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ),
239                          LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ) );
240                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
241                 arenaSize += sizeof(ARENA_FREE);
242                 freeSize += pArena->size & ARENA_SIZE_MASK;
243             }
244             else if (*(DWORD *)ptr & ARENA_FLAG_PREV_FREE)
245             {
246                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
247                 DPRINTF( "%p Used %08lx back=%p\n",
248                         pArena, pArena->size & ARENA_SIZE_MASK, *((ARENA_FREE **)pArena - 1) );
249                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
250                 arenaSize += sizeof(ARENA_INUSE);
251                 usedSize += pArena->size & ARENA_SIZE_MASK;
252             }
253             else
254             {
255                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
256                 DPRINTF( "%p used %08lx\n", pArena, pArena->size & ARENA_SIZE_MASK );
257                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
258                 arenaSize += sizeof(ARENA_INUSE);
259                 usedSize += pArena->size & ARENA_SIZE_MASK;
260             }
261         }
262         DPRINTF( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
263               subheap->size, subheap->commitSize, freeSize, usedSize,
264               arenaSize, (arenaSize * 100) / subheap->size );
265         subheap = subheap->next;
266     }
267 }
268
269
270 static void HEAP_DumpEntry( LPPROCESS_HEAP_ENTRY entry )
271 {
272     WORD rem_flags;
273     TRACE( "Dumping entry %p\n", entry );
274     TRACE( "lpData\t\t: %p\n", entry->lpData );
275     TRACE( "cbData\t\t: %08lx\n", entry->cbData);
276     TRACE( "cbOverhead\t: %08x\n", entry->cbOverhead);
277     TRACE( "iRegionIndex\t: %08x\n", entry->iRegionIndex);
278     TRACE( "WFlags\t\t: ");
279     if (entry->wFlags & PROCESS_HEAP_REGION)
280         TRACE( "PROCESS_HEAP_REGION ");
281     if (entry->wFlags & PROCESS_HEAP_UNCOMMITTED_RANGE)
282         TRACE( "PROCESS_HEAP_UNCOMMITTED_RANGE ");
283     if (entry->wFlags & PROCESS_HEAP_ENTRY_BUSY)
284         TRACE( "PROCESS_HEAP_ENTRY_BUSY ");
285     if (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE)
286         TRACE( "PROCESS_HEAP_ENTRY_MOVEABLE ");
287     if (entry->wFlags & PROCESS_HEAP_ENTRY_DDESHARE)
288         TRACE( "PROCESS_HEAP_ENTRY_DDESHARE ");
289     rem_flags = entry->wFlags &
290         ~(PROCESS_HEAP_REGION | PROCESS_HEAP_UNCOMMITTED_RANGE |
291           PROCESS_HEAP_ENTRY_BUSY | PROCESS_HEAP_ENTRY_MOVEABLE|
292           PROCESS_HEAP_ENTRY_DDESHARE);
293     if (rem_flags)
294         TRACE( "Unknown %08x", rem_flags);
295     TRACE( "\n");
296     if ((entry->wFlags & PROCESS_HEAP_ENTRY_BUSY )
297         && (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE))
298     {
299         /* Treat as block */
300         TRACE( "BLOCK->hMem\t\t:%p\n", entry->u.Block.hMem);
301     }
302     if (entry->wFlags & PROCESS_HEAP_REGION)
303     {
304         TRACE( "Region.dwCommittedSize\t:%08lx\n",entry->u.Region.dwCommittedSize);
305         TRACE( "Region.dwUnCommittedSize\t:%08lx\n",entry->u.Region.dwUnCommittedSize);
306         TRACE( "Region.lpFirstBlock\t:%p\n",entry->u.Region.lpFirstBlock);
307         TRACE( "Region.lpLastBlock\t:%p\n",entry->u.Region.lpLastBlock);
308     }
309 }
310
311 /***********************************************************************
312  *           HEAP_GetPtr
313  * RETURNS
314  *      Pointer to the heap
315  *      NULL: Failure
316  */
317 static HEAP *HEAP_GetPtr(
318              HANDLE heap /* [in] Handle to the heap */
319 ) {
320     HEAP *heapPtr = (HEAP *)heap;
321     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
322     {
323         ERR("Invalid heap %p!\n", heap );
324         return NULL;
325     }
326     if (TRACE_ON(heap) && !HEAP_IsRealArena( heapPtr, 0, NULL, NOISY ))
327     {
328         HEAP_Dump( heapPtr );
329         assert( FALSE );
330         return NULL;
331     }
332     return heapPtr;
333 }
334
335
336 /***********************************************************************
337  *           HEAP_InsertFreeBlock
338  *
339  * Insert a free block into the free list.
340  */
341 static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last )
342 {
343     FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( pArena->size + sizeof(*pArena) );
344     if (last)
345     {
346         /* insert at end of free list, i.e. before the next free list entry */
347         pEntry++;
348         if (pEntry == &heap->freeList[HEAP_NB_FREE_LISTS]) pEntry = heap->freeList;
349         list_add_before( &pEntry->arena.entry, &pArena->entry );
350     }
351     else
352     {
353         /* insert at head of free list */
354         list_add_after( &pEntry->arena.entry, &pArena->entry );
355     }
356     pArena->size |= ARENA_FLAG_FREE;
357 }
358
359
360 /***********************************************************************
361  *           HEAP_FindSubHeap
362  * Find the sub-heap containing a given address.
363  *
364  * RETURNS
365  *      Pointer: Success
366  *      NULL: Failure
367  */
368 static SUBHEAP *HEAP_FindSubHeap(
369                 const HEAP *heap, /* [in] Heap pointer */
370                 LPCVOID ptr /* [in] Address */
371 ) {
372     const SUBHEAP *sub = &heap->subheap;
373     while (sub)
374     {
375         if (((const char *)ptr >= (const char *)sub) &&
376             ((const char *)ptr < (const char *)sub + sub->size)) return (SUBHEAP*)sub;
377         sub = sub->next;
378     }
379     return NULL;
380 }
381
382
383 /***********************************************************************
384  *           HEAP_Commit
385  *
386  * Make sure the heap storage is committed for a given size in the specified arena.
387  */
388 static inline BOOL HEAP_Commit( SUBHEAP *subheap, ARENA_INUSE *pArena, SIZE_T data_size )
389 {
390     void *ptr = (char *)(pArena + 1) + data_size + sizeof(ARENA_FREE);
391     SIZE_T size = (char *)ptr - (char *)subheap;
392     size = (size + COMMIT_MASK) & ~COMMIT_MASK;
393     if (size > subheap->size) size = subheap->size;
394     if (size <= subheap->commitSize) return TRUE;
395     size -= subheap->commitSize;
396     ptr = (char *)subheap + subheap->commitSize;
397     if (NtAllocateVirtualMemory( NtCurrentProcess(), &ptr, 0,
398                                  &size, MEM_COMMIT, PAGE_READWRITE ))
399     {
400         WARN("Could not commit %08lx bytes at %p for heap %p\n",
401                  size, ptr, subheap->heap );
402         return FALSE;
403     }
404     subheap->commitSize += size;
405     return TRUE;
406 }
407
408
409 /***********************************************************************
410  *           HEAP_Decommit
411  *
412  * If possible, decommit the heap storage from (including) 'ptr'.
413  */
414 static inline BOOL HEAP_Decommit( SUBHEAP *subheap, void *ptr )
415 {
416     void *addr;
417     SIZE_T decommit_size;
418     SIZE_T size = (char *)ptr - (char *)subheap;
419
420     /* round to next block and add one full block */
421     size = ((size + COMMIT_MASK) & ~COMMIT_MASK) + COMMIT_MASK + 1;
422     if (size >= subheap->commitSize) return TRUE;
423     decommit_size = subheap->commitSize - size;
424     addr = (char *)subheap + size;
425
426     if (NtFreeVirtualMemory( NtCurrentProcess(), &addr, &decommit_size, MEM_DECOMMIT ))
427     {
428         WARN("Could not decommit %08lx bytes at %p for heap %p\n",
429                 decommit_size, (char *)subheap + size, subheap->heap );
430         return FALSE;
431     }
432     subheap->commitSize -= decommit_size;
433     return TRUE;
434 }
435
436
437 /***********************************************************************
438  *           HEAP_CreateFreeBlock
439  *
440  * Create a free block at a specified address. 'size' is the size of the
441  * whole block, including the new arena.
442  */
443 static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, SIZE_T size )
444 {
445     ARENA_FREE *pFree;
446     char *pEnd;
447     BOOL last;
448
449     /* Create a free arena */
450     mark_block_uninitialized( ptr, sizeof( ARENA_FREE ) );
451     pFree = (ARENA_FREE *)ptr;
452     pFree->magic = ARENA_FREE_MAGIC;
453
454     /* If debugging, erase the freed block content */
455
456     pEnd = (char *)ptr + size;
457     if (pEnd > (char *)subheap + subheap->commitSize) pEnd = (char *)subheap + subheap->commitSize;
458     if (pEnd > (char *)(pFree + 1)) mark_block_free( pFree + 1, pEnd - (char *)(pFree + 1) );
459
460     /* Check if next block is free also */
461
462     if (((char *)ptr + size < (char *)subheap + subheap->size) &&
463         (*(DWORD *)((char *)ptr + size) & ARENA_FLAG_FREE))
464     {
465         /* Remove the next arena from the free list */
466         ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
467         list_remove( &pNext->entry );
468         size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
469         mark_block_free( pNext, sizeof(ARENA_FREE) );
470     }
471
472     /* Set the next block PREV_FREE flag and pointer */
473
474     last = ((char *)ptr + size >= (char *)subheap + subheap->size);
475     if (!last)
476     {
477         DWORD *pNext = (DWORD *)((char *)ptr + size);
478         *pNext |= ARENA_FLAG_PREV_FREE;
479         mark_block_initialized( pNext - 1, sizeof( ARENA_FREE * ) );
480         *((ARENA_FREE **)pNext - 1) = pFree;
481     }
482
483     /* Last, insert the new block into the free list */
484
485     pFree->size = size - sizeof(*pFree);
486     HEAP_InsertFreeBlock( subheap->heap, pFree, last );
487 }
488
489
490 /***********************************************************************
491  *           HEAP_MakeInUseBlockFree
492  *
493  * Turn an in-use block into a free block. Can also decommit the end of
494  * the heap, and possibly even free the sub-heap altogether.
495  */
496 static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
497 {
498     ARENA_FREE *pFree;
499     SIZE_T size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
500
501     /* Check if we can merge with previous block */
502
503     if (pArena->size & ARENA_FLAG_PREV_FREE)
504     {
505         pFree = *((ARENA_FREE **)pArena - 1);
506         size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
507         /* Remove it from the free list */
508         list_remove( &pFree->entry );
509     }
510     else pFree = (ARENA_FREE *)pArena;
511
512     /* Create a free block */
513
514     HEAP_CreateFreeBlock( subheap, pFree, size );
515     size = (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
516     if ((char *)pFree + size < (char *)subheap + subheap->size)
517         return;  /* Not the last block, so nothing more to do */
518
519     /* Free the whole sub-heap if it's empty and not the original one */
520
521     if (((char *)pFree == (char *)subheap + subheap->headerSize) &&
522         (subheap != &subheap->heap->subheap))
523     {
524         SIZE_T size = 0;
525         SUBHEAP *pPrev = &subheap->heap->subheap;
526         /* Remove the free block from the list */
527         list_remove( &pFree->entry );
528         /* Remove the subheap from the list */
529         while (pPrev && (pPrev->next != subheap)) pPrev = pPrev->next;
530         if (pPrev) pPrev->next = subheap->next;
531         /* Free the memory */
532         subheap->magic = 0;
533         NtFreeVirtualMemory( NtCurrentProcess(), (void **)&subheap, &size, MEM_RELEASE );
534         return;
535     }
536
537     /* Decommit the end of the heap */
538
539     if (!(subheap->heap->flags & HEAP_SHARED)) HEAP_Decommit( subheap, pFree + 1 );
540 }
541
542
543 /***********************************************************************
544  *           HEAP_ShrinkBlock
545  *
546  * Shrink an in-use block.
547  */
548 static void HEAP_ShrinkBlock(SUBHEAP *subheap, ARENA_INUSE *pArena, SIZE_T size)
549 {
550     if ((pArena->size & ARENA_SIZE_MASK) >= size + HEAP_MIN_SHRINK_SIZE)
551     {
552         HEAP_CreateFreeBlock( subheap, (char *)(pArena + 1) + size,
553                               (pArena->size & ARENA_SIZE_MASK) - size );
554         /* assign size plus previous arena flags */
555         pArena->size = size | (pArena->size & ~ARENA_SIZE_MASK);
556     }
557     else
558     {
559         /* Turn off PREV_FREE flag in next block */
560         char *pNext = (char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK);
561         if (pNext < (char *)subheap + subheap->size)
562             *(DWORD *)pNext &= ~ARENA_FLAG_PREV_FREE;
563     }
564 }
565
566 /***********************************************************************
567  *           HEAP_InitSubHeap
568  */
569 static BOOL HEAP_InitSubHeap( HEAP *heap, LPVOID address, DWORD flags,
570                               SIZE_T commitSize, SIZE_T totalSize )
571 {
572     SUBHEAP *subheap;
573     FREE_LIST_ENTRY *pEntry;
574     int i;
575
576     /* Commit memory */
577
578     if (flags & HEAP_SHARED)
579         commitSize = totalSize;  /* always commit everything in a shared heap */
580     if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0,
581                                  &commitSize, MEM_COMMIT, PAGE_READWRITE ))
582     {
583         WARN("Could not commit %08lx bytes for sub-heap %p\n", commitSize, address );
584         return FALSE;
585     }
586
587     /* Fill the sub-heap structure */
588
589     subheap = (SUBHEAP *)address;
590     subheap->heap       = heap;
591     subheap->size       = totalSize;
592     subheap->commitSize = commitSize;
593     subheap->magic      = SUBHEAP_MAGIC;
594
595     if ( subheap != (SUBHEAP *)heap )
596     {
597         /* If this is a secondary subheap, insert it into list */
598
599         subheap->headerSize = ROUND_SIZE( sizeof(SUBHEAP) );
600         subheap->next       = heap->subheap.next;
601         heap->subheap.next  = subheap;
602     }
603     else
604     {
605         /* If this is a primary subheap, initialize main heap */
606
607         subheap->headerSize = ROUND_SIZE( sizeof(HEAP) );
608         subheap->next       = NULL;
609         heap->flags         = flags;
610         heap->magic         = HEAP_MAGIC;
611
612         /* Build the free lists */
613
614         list_init( &heap->freeList[0].arena.entry );
615         for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
616         {
617             pEntry->arena.size = 0 | ARENA_FLAG_FREE;
618             pEntry->arena.magic = ARENA_FREE_MAGIC;
619             if (i) list_add_after( &pEntry[-1].arena.entry, &pEntry->arena.entry );
620         }
621
622         /* Initialize critical section */
623
624         if (!processHeap)  /* do it by hand to avoid memory allocations */
625         {
626             heap->critSection.DebugInfo      = &process_heap_critsect_debug;
627             heap->critSection.LockCount      = -1;
628             heap->critSection.RecursionCount = 0;
629             heap->critSection.OwningThread   = 0;
630             heap->critSection.LockSemaphore  = 0;
631             heap->critSection.SpinCount      = 0;
632             process_heap_critsect_debug.CriticalSection = &heap->critSection;
633         }
634         else RtlInitializeCriticalSection( &heap->critSection );
635
636         if (flags & HEAP_SHARED)
637         {
638             /* let's assume that only one thread at a time will try to do this */
639             HANDLE sem = heap->critSection.LockSemaphore;
640             if (!sem) NtCreateSemaphore( &sem, SEMAPHORE_ALL_ACCESS, NULL, 0, 1 );
641
642             NtDuplicateObject( NtCurrentProcess(), sem, NtCurrentProcess(), &sem, 0, 0,
643                                DUP_HANDLE_MAKE_GLOBAL | DUP_HANDLE_SAME_ACCESS | DUP_HANDLE_CLOSE_SOURCE );
644             heap->critSection.LockSemaphore = sem;
645         }
646     }
647
648     /* Create the first free block */
649
650     HEAP_CreateFreeBlock( subheap, (LPBYTE)subheap + subheap->headerSize,
651                           subheap->size - subheap->headerSize );
652
653     return TRUE;
654 }
655
656 /***********************************************************************
657  *           HEAP_CreateSubHeap
658  *
659  * Create a sub-heap of the given size.
660  * If heap == NULL, creates a main heap.
661  */
662 static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, void *base, DWORD flags,
663                                     SIZE_T commitSize, SIZE_T totalSize )
664 {
665     LPVOID address = base;
666
667     /* round-up sizes on a 64K boundary */
668     totalSize  = (totalSize + 0xffff) & 0xffff0000;
669     commitSize = (commitSize + 0xffff) & 0xffff0000;
670     if (!commitSize) commitSize = 0x10000;
671     if (totalSize < commitSize) totalSize = commitSize;
672
673     if (!address)
674     {
675         /* allocate the memory block */
676         if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &totalSize,
677                                      MEM_RESERVE, PAGE_READWRITE ))
678         {
679             WARN("Could not allocate %08lx bytes\n", totalSize );
680             return NULL;
681         }
682     }
683
684     /* Initialize subheap */
685
686     if (!HEAP_InitSubHeap( heap ? heap : (HEAP *)address,
687                            address, flags, commitSize, totalSize ))
688     {
689         SIZE_T size = 0;
690         if (!base) NtFreeVirtualMemory( NtCurrentProcess(), &address, &size, MEM_RELEASE );
691         return NULL;
692     }
693
694     return (SUBHEAP *)address;
695 }
696
697
698 /***********************************************************************
699  *           HEAP_FindFreeBlock
700  *
701  * Find a free block at least as large as the requested size, and make sure
702  * the requested size is committed.
703  */
704 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size,
705                                        SUBHEAP **ppSubHeap )
706 {
707     SUBHEAP *subheap;
708     struct list *ptr;
709     FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( size + sizeof(ARENA_INUSE) );
710
711     /* Find a suitable free list, and in it find a block large enough */
712
713     ptr = &pEntry->arena.entry;
714     while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
715     {
716         ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
717         SIZE_T arena_size = (pArena->size & ARENA_SIZE_MASK) +
718                             sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
719         if (arena_size >= size)
720         {
721             subheap = HEAP_FindSubHeap( heap, pArena );
722             if (!HEAP_Commit( subheap, (ARENA_INUSE *)pArena, size )) return NULL;
723             *ppSubHeap = subheap;
724             return pArena;
725         }
726     }
727
728     /* If no block was found, attempt to grow the heap */
729
730     if (!(heap->flags & HEAP_GROWABLE))
731     {
732         WARN("Not enough space in heap %p for %08lx bytes\n", heap, size );
733         return NULL;
734     }
735     /* make sure that we have a big enough size *committed* to fit another
736      * last free arena in !
737      * So just one heap struct, one first free arena which will eventually
738      * get used, and a second free arena that might get assigned all remaining
739      * free space in HEAP_ShrinkBlock() */
740     size += ROUND_SIZE(sizeof(SUBHEAP)) + sizeof(ARENA_INUSE) + sizeof(ARENA_FREE);
741     if (!(subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, size,
742                                         max( HEAP_DEF_SIZE, size ) )))
743         return NULL;
744
745     TRACE("created new sub-heap %p of %08lx bytes for heap %p\n",
746             subheap, size, heap );
747
748     *ppSubHeap = subheap;
749     return (ARENA_FREE *)(subheap + 1);
750 }
751
752
753 /***********************************************************************
754  *           HEAP_IsValidArenaPtr
755  *
756  * Check that the pointer is inside the range possible for arenas.
757  */
758 static BOOL HEAP_IsValidArenaPtr( const HEAP *heap, const void *ptr )
759 {
760     int i;
761     const SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
762     if (!subheap) return FALSE;
763     if ((const char *)ptr >= (const char *)subheap + subheap->headerSize) return TRUE;
764     if (subheap != &heap->subheap) return FALSE;
765     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
766         if (ptr == (const void *)&heap->freeList[i].arena) return TRUE;
767     return FALSE;
768 }
769
770
771 /***********************************************************************
772  *           HEAP_ValidateFreeArena
773  */
774 static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
775 {
776     ARENA_FREE *prev, *next;
777     char *heapEnd = (char *)subheap + subheap->size;
778
779     /* Check for unaligned pointers */
780     if ( (ULONG_PTR)pArena % ALIGNMENT != 0 )
781     {
782         ERR("Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
783         return FALSE;
784     }
785
786     /* Check magic number */
787     if (pArena->magic != ARENA_FREE_MAGIC)
788     {
789         ERR("Heap %p: invalid free arena magic for %p\n", subheap->heap, pArena );
790         return FALSE;
791     }
792     /* Check size flags */
793     if (!(pArena->size & ARENA_FLAG_FREE) ||
794         (pArena->size & ARENA_FLAG_PREV_FREE))
795     {
796         ERR("Heap %p: bad flags %08lx for free arena %p\n",
797             subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
798         return FALSE;
799     }
800     /* Check arena size */
801     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
802     {
803         ERR("Heap %p: bad size %08lx for free arena %p\n",
804             subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
805         return FALSE;
806     }
807     /* Check that next pointer is valid */
808     next = LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry );
809     if (!HEAP_IsValidArenaPtr( subheap->heap, next ))
810     {
811         ERR("Heap %p: bad next ptr %p for arena %p\n",
812             subheap->heap, next, pArena );
813         return FALSE;
814     }
815     /* Check that next arena is free */
816     if (!(next->size & ARENA_FLAG_FREE) || (next->magic != ARENA_FREE_MAGIC))
817     {
818         ERR("Heap %p: next arena %p invalid for %p\n",
819             subheap->heap, next, pArena );
820         return FALSE;
821     }
822     /* Check that prev pointer is valid */
823     prev = LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry );
824     if (!HEAP_IsValidArenaPtr( subheap->heap, prev ))
825     {
826         ERR("Heap %p: bad prev ptr %p for arena %p\n",
827             subheap->heap, prev, pArena );
828         return FALSE;
829     }
830     /* Check that prev arena is free */
831     if (!(prev->size & ARENA_FLAG_FREE) || (prev->magic != ARENA_FREE_MAGIC))
832     {
833         /* this often means that the prev arena got overwritten
834          * by a memory write before that prev arena */
835         ERR("Heap %p: prev arena %p invalid for %p\n",
836             subheap->heap, prev, pArena );
837         return FALSE;
838     }
839     /* Check that next block has PREV_FREE flag */
840     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
841     {
842         if (!(*(DWORD *)((char *)(pArena + 1) +
843             (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
844         {
845             ERR("Heap %p: free arena %p next block has no PREV_FREE flag\n",
846                 subheap->heap, pArena );
847             return FALSE;
848         }
849         /* Check next block back pointer */
850         if (*((ARENA_FREE **)((char *)(pArena + 1) +
851             (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
852         {
853             ERR("Heap %p: arena %p has wrong back ptr %p\n",
854                 subheap->heap, pArena,
855                 *((ARENA_FREE **)((char *)(pArena+1) + (pArena->size & ARENA_SIZE_MASK)) - 1));
856             return FALSE;
857         }
858     }
859     return TRUE;
860 }
861
862
863 /***********************************************************************
864  *           HEAP_ValidateInUseArena
865  */
866 static BOOL HEAP_ValidateInUseArena( const SUBHEAP *subheap, const ARENA_INUSE *pArena, BOOL quiet )
867 {
868     const char *heapEnd = (const char *)subheap + subheap->size;
869
870     /* Check for unaligned pointers */
871     if ( (ULONG_PTR)pArena % ALIGNMENT != 0 )
872     {
873         if ( quiet == NOISY )
874         {
875             ERR( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
876             if ( TRACE_ON(heap) )
877                 HEAP_Dump( subheap->heap );
878         }
879         else if ( WARN_ON(heap) )
880         {
881             WARN( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
882             if ( TRACE_ON(heap) )
883                 HEAP_Dump( subheap->heap );
884         }
885         return FALSE;
886     }
887
888     /* Check magic number */
889     if (pArena->magic != ARENA_INUSE_MAGIC)
890     {
891         if (quiet == NOISY) {
892             ERR("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
893             if (TRACE_ON(heap))
894                HEAP_Dump( subheap->heap );
895         }  else if (WARN_ON(heap)) {
896             WARN("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
897             if (TRACE_ON(heap))
898                HEAP_Dump( subheap->heap );
899         }
900         return FALSE;
901     }
902     /* Check size flags */
903     if (pArena->size & ARENA_FLAG_FREE)
904     {
905         ERR("Heap %p: bad flags %08lx for in-use arena %p\n",
906             subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
907         return FALSE;
908     }
909     /* Check arena size */
910     if ((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
911     {
912         ERR("Heap %p: bad size %08lx for in-use arena %p\n",
913             subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
914         return FALSE;
915     }
916     /* Check next arena PREV_FREE flag */
917     if (((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
918         (*(const DWORD *)((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
919     {
920         ERR("Heap %p: in-use arena %p next block has PREV_FREE flag\n",
921             subheap->heap, pArena );
922         return FALSE;
923     }
924     /* Check prev free arena */
925     if (pArena->size & ARENA_FLAG_PREV_FREE)
926     {
927         const ARENA_FREE *pPrev = *((const ARENA_FREE * const*)pArena - 1);
928         /* Check prev pointer */
929         if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
930         {
931             ERR("Heap %p: bad back ptr %p for arena %p\n",
932                 subheap->heap, pPrev, pArena );
933             return FALSE;
934         }
935         /* Check that prev arena is free */
936         if (!(pPrev->size & ARENA_FLAG_FREE) ||
937             (pPrev->magic != ARENA_FREE_MAGIC))
938         {
939             ERR("Heap %p: prev arena %p invalid for in-use %p\n",
940                 subheap->heap, pPrev, pArena );
941             return FALSE;
942         }
943         /* Check that prev arena is really the previous block */
944         if ((const char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (const char *)pArena)
945         {
946             ERR("Heap %p: prev arena %p is not prev for in-use %p\n",
947                 subheap->heap, pPrev, pArena );
948             return FALSE;
949         }
950     }
951     return TRUE;
952 }
953
954
955 /***********************************************************************
956  *           HEAP_IsRealArena  [Internal]
957  * Validates a block is a valid arena.
958  *
959  * RETURNS
960  *      TRUE: Success
961  *      FALSE: Failure
962  */
963 static BOOL HEAP_IsRealArena( HEAP *heapPtr,   /* [in] ptr to the heap */
964               DWORD flags,   /* [in] Bit flags that control access during operation */
965               LPCVOID block, /* [in] Optional pointer to memory block to validate */
966               BOOL quiet )   /* [in] Flag - if true, HEAP_ValidateInUseArena
967                               *             does not complain    */
968 {
969     SUBHEAP *subheap;
970     BOOL ret = TRUE;
971
972     flags &= HEAP_NO_SERIALIZE;
973     flags |= heapPtr->flags;
974     /* calling HeapLock may result in infinite recursion, so do the critsect directly */
975     if (!(flags & HEAP_NO_SERIALIZE))
976         RtlEnterCriticalSection( &heapPtr->critSection );
977
978     if (block)
979     {
980         /* Only check this single memory block */
981
982         if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
983             ((const char *)block < (char *)subheap + subheap->headerSize
984                                    + sizeof(ARENA_INUSE)))
985         {
986             if (quiet == NOISY)
987                 ERR("Heap %p: block %p is not inside heap\n", heapPtr, block );
988             else if (WARN_ON(heap))
989                 WARN("Heap %p: block %p is not inside heap\n", heapPtr, block );
990             ret = FALSE;
991         } else
992             ret = HEAP_ValidateInUseArena( subheap, (const ARENA_INUSE *)block - 1, quiet );
993
994         if (!(flags & HEAP_NO_SERIALIZE))
995             RtlLeaveCriticalSection( &heapPtr->critSection );
996         return ret;
997     }
998
999     subheap = &heapPtr->subheap;
1000     while (subheap && ret)
1001     {
1002         char *ptr = (char *)subheap + subheap->headerSize;
1003         while (ptr < (char *)subheap + subheap->size)
1004         {
1005             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1006             {
1007                 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr )) {
1008                     ret = FALSE;
1009                     break;
1010                 }
1011                 ptr += sizeof(ARENA_FREE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1012             }
1013             else
1014             {
1015                 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY )) {
1016                     ret = FALSE;
1017                     break;
1018                 }
1019                 ptr += sizeof(ARENA_INUSE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1020             }
1021         }
1022         subheap = subheap->next;
1023     }
1024
1025     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1026     return ret;
1027 }
1028
1029
1030 /***********************************************************************
1031  *           RtlCreateHeap   (NTDLL.@)
1032  *
1033  * Create a new Heap.
1034  *
1035  * PARAMS
1036  *  flags      [I] HEAP_ flags from "winnt.h"
1037  *  addr       [I] Desired base address
1038  *  totalSize  [I] Total size of the heap, or 0 for a growable heap
1039  *  commitSize [I] Amount of heap space to commit
1040  *  unknown    [I] Not yet understood
1041  *  definition [I] Heap definition
1042  *
1043  * RETURNS
1044  *  Success: A HANDLE to the newly created heap.
1045  *  Failure: a NULL HANDLE.
1046  */
1047 HANDLE WINAPI RtlCreateHeap( ULONG flags, PVOID addr, SIZE_T totalSize, SIZE_T commitSize,
1048                              PVOID unknown, PRTL_HEAP_DEFINITION definition )
1049 {
1050     SUBHEAP *subheap;
1051
1052     /* Allocate the heap block */
1053
1054     if (!totalSize)
1055     {
1056         totalSize = HEAP_DEF_SIZE;
1057         flags |= HEAP_GROWABLE;
1058     }
1059
1060     if (!(subheap = HEAP_CreateSubHeap( NULL, addr, flags, commitSize, totalSize ))) return 0;
1061
1062     /* link it into the per-process heap list */
1063     if (processHeap)
1064     {
1065         HEAP *heapPtr = subheap->heap;
1066         RtlEnterCriticalSection( &processHeap->critSection );
1067         list_add_head( &processHeap->entry, &heapPtr->entry );
1068         RtlLeaveCriticalSection( &processHeap->critSection );
1069     }
1070     else
1071     {
1072         processHeap = subheap->heap;  /* assume the first heap we create is the process main heap */
1073         list_init( &processHeap->entry );
1074     }
1075
1076     return (HANDLE)subheap;
1077 }
1078
1079
1080 /***********************************************************************
1081  *           RtlDestroyHeap   (NTDLL.@)
1082  *
1083  * Destroy a Heap created with RtlCreateHeap().
1084  *
1085  * PARAMS
1086  *  heap [I] Heap to destroy.
1087  *
1088  * RETURNS
1089  *  Success: A NULL HANDLE, if heap is NULL or it was destroyed
1090  *  Failure: The Heap handle, if heap is the process heap.
1091  */
1092 HANDLE WINAPI RtlDestroyHeap( HANDLE heap )
1093 {
1094     HEAP *heapPtr = HEAP_GetPtr( heap );
1095     SUBHEAP *subheap;
1096
1097     TRACE("%p\n", heap );
1098     if (!heapPtr) return heap;
1099
1100     if (heap == processHeap) return heap; /* cannot delete the main process heap */
1101
1102     /* remove it from the per-process list */
1103     RtlEnterCriticalSection( &processHeap->critSection );
1104     list_remove( &heapPtr->entry );
1105     RtlLeaveCriticalSection( &processHeap->critSection );
1106
1107     RtlDeleteCriticalSection( &heapPtr->critSection );
1108     subheap = &heapPtr->subheap;
1109     while (subheap)
1110     {
1111         SUBHEAP *next = subheap->next;
1112         SIZE_T size = 0;
1113         void *addr = subheap;
1114         NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE );
1115         subheap = next;
1116     }
1117     return 0;
1118 }
1119
1120
1121 /***********************************************************************
1122  *           RtlAllocateHeap   (NTDLL.@)
1123  *
1124  * Allocate a memory block from a Heap.
1125  *
1126  * PARAMS
1127  *  heap  [I] Heap to allocate block from
1128  *  flags [I] HEAP_ flags from "winnt.h"
1129  *  size  [I] Size of the memory block to allocate
1130  *
1131  * RETURNS
1132  *  Success: A pointer to the newly allocated block
1133  *  Failure: NULL.
1134  *
1135  * NOTES
1136  *  This call does not SetLastError().
1137  */
1138 PVOID WINAPI RtlAllocateHeap( HANDLE heap, ULONG flags, SIZE_T size )
1139 {
1140     ARENA_FREE *pArena;
1141     ARENA_INUSE *pInUse;
1142     SUBHEAP *subheap;
1143     HEAP *heapPtr = HEAP_GetPtr( heap );
1144     SIZE_T rounded_size;
1145
1146     /* Validate the parameters */
1147
1148     if (!heapPtr) return NULL;
1149     flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1150     flags |= heapPtr->flags;
1151     rounded_size = ROUND_SIZE(size);
1152     if (rounded_size < HEAP_MIN_DATA_SIZE) rounded_size = HEAP_MIN_DATA_SIZE;
1153
1154     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1155     /* Locate a suitable free block */
1156
1157     if (!(pArena = HEAP_FindFreeBlock( heapPtr, rounded_size, &subheap )))
1158     {
1159         TRACE("(%p,%08lx,%08lx): returning NULL\n",
1160                   heap, flags, size  );
1161         if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1162         if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1163         return NULL;
1164     }
1165
1166     /* Remove the arena from the free list */
1167
1168     list_remove( &pArena->entry );
1169
1170     /* Build the in-use arena */
1171
1172     pInUse = (ARENA_INUSE *)pArena;
1173
1174     /* in-use arena is smaller than free arena,
1175      * so we have to add the difference to the size */
1176     pInUse->size  = (pInUse->size & ~ARENA_FLAG_FREE) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1177     pInUse->magic = ARENA_INUSE_MAGIC;
1178
1179     /* Shrink the block */
1180
1181     HEAP_ShrinkBlock( subheap, pInUse, rounded_size );
1182     pInUse->unused_bytes = (pInUse->size & ARENA_SIZE_MASK) - size;
1183
1184     if (flags & HEAP_ZERO_MEMORY)
1185         clear_block( pInUse + 1, pInUse->size & ARENA_SIZE_MASK );
1186     else
1187         mark_block_uninitialized( pInUse + 1, pInUse->size & ARENA_SIZE_MASK );
1188
1189     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1190
1191     TRACE("(%p,%08lx,%08lx): returning %p\n", heap, flags, size, pInUse + 1 );
1192     return (LPVOID)(pInUse + 1);
1193 }
1194
1195
1196 /***********************************************************************
1197  *           RtlFreeHeap   (NTDLL.@)
1198  *
1199  * Free a memory block allocated with RtlAllocateHeap().
1200  *
1201  * PARAMS
1202  *  heap  [I] Heap that block was allocated from
1203  *  flags [I] HEAP_ flags from "winnt.h"
1204  *  ptr   [I] Block to free
1205  *
1206  * RETURNS
1207  *  Success: TRUE, if ptr is NULL or was freed successfully.
1208  *  Failure: FALSE.
1209  */
1210 BOOLEAN WINAPI RtlFreeHeap( HANDLE heap, ULONG flags, PVOID ptr )
1211 {
1212     ARENA_INUSE *pInUse;
1213     SUBHEAP *subheap;
1214     HEAP *heapPtr;
1215
1216     /* Validate the parameters */
1217
1218     if (!ptr) return TRUE;  /* freeing a NULL ptr isn't an error in Win2k */
1219
1220     heapPtr = HEAP_GetPtr( heap );
1221     if (!heapPtr)
1222     {
1223         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1224         return FALSE;
1225     }
1226
1227     flags &= HEAP_NO_SERIALIZE;
1228     flags |= heapPtr->flags;
1229     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1230
1231     /* Some sanity checks */
1232
1233     pInUse  = (ARENA_INUSE *)ptr - 1;
1234     if (!(subheap = HEAP_FindSubHeap( heapPtr, pInUse ))) goto error;
1235     if ((char *)pInUse < (char *)subheap + subheap->headerSize) goto error;
1236     if (!HEAP_ValidateInUseArena( subheap, pInUse, QUIET )) goto error;
1237
1238     /* Turn the block into a free block */
1239
1240     HEAP_MakeInUseBlockFree( subheap, pInUse );
1241
1242     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1243
1244     TRACE("(%p,%08lx,%p): returning TRUE\n", heap, flags, ptr );
1245     return TRUE;
1246
1247 error:
1248     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1249     RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1250     TRACE("(%p,%08lx,%p): returning FALSE\n", heap, flags, ptr );
1251     return FALSE;
1252 }
1253
1254
1255 /***********************************************************************
1256  *           RtlReAllocateHeap   (NTDLL.@)
1257  *
1258  * Change the size of a memory block allocated with RtlAllocateHeap().
1259  *
1260  * PARAMS
1261  *  heap  [I] Heap that block was allocated from
1262  *  flags [I] HEAP_ flags from "winnt.h"
1263  *  ptr   [I] Block to resize
1264  *  size  [I] Size of the memory block to allocate
1265  *
1266  * RETURNS
1267  *  Success: A pointer to the resized block (which may be different).
1268  *  Failure: NULL.
1269  */
1270 PVOID WINAPI RtlReAllocateHeap( HANDLE heap, ULONG flags, PVOID ptr, SIZE_T size )
1271 {
1272     ARENA_INUSE *pArena;
1273     HEAP *heapPtr;
1274     SUBHEAP *subheap;
1275     SIZE_T oldSize, rounded_size;
1276
1277     if (!ptr) return NULL;
1278     if (!(heapPtr = HEAP_GetPtr( heap )))
1279     {
1280         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1281         return NULL;
1282     }
1283
1284     /* Validate the parameters */
1285
1286     flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY |
1287              HEAP_REALLOC_IN_PLACE_ONLY;
1288     flags |= heapPtr->flags;
1289     rounded_size = ROUND_SIZE(size);
1290     if (rounded_size < HEAP_MIN_DATA_SIZE) rounded_size = HEAP_MIN_DATA_SIZE;
1291
1292     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1293
1294     pArena = (ARENA_INUSE *)ptr - 1;
1295     if (!(subheap = HEAP_FindSubHeap( heapPtr, pArena ))) goto error;
1296     if ((char *)pArena < (char *)subheap + subheap->headerSize) goto error;
1297     if (!HEAP_ValidateInUseArena( subheap, pArena, QUIET )) goto error;
1298
1299     /* Check if we need to grow the block */
1300
1301     oldSize = (pArena->size & ARENA_SIZE_MASK);
1302     if (rounded_size > oldSize)
1303     {
1304         char *pNext = (char *)(pArena + 1) + oldSize;
1305         if ((pNext < (char *)subheap + subheap->size) &&
1306             (*(DWORD *)pNext & ARENA_FLAG_FREE) &&
1307             (oldSize + (*(DWORD *)pNext & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) >= rounded_size))
1308         {
1309             /* The next block is free and large enough */
1310             ARENA_FREE *pFree = (ARENA_FREE *)pNext;
1311             list_remove( &pFree->entry );
1312             pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
1313             if (!HEAP_Commit( subheap, pArena, rounded_size ))
1314             {
1315                 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1316                 if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1317                 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_NO_MEMORY );
1318                 return NULL;
1319             }
1320             HEAP_ShrinkBlock( subheap, pArena, rounded_size );
1321         }
1322         else  /* Do it the hard way */
1323         {
1324             ARENA_FREE *pNew;
1325             ARENA_INUSE *pInUse;
1326             SUBHEAP *newsubheap;
1327
1328             if ((flags & HEAP_REALLOC_IN_PLACE_ONLY) ||
1329                 !(pNew = HEAP_FindFreeBlock( heapPtr, rounded_size, &newsubheap )))
1330             {
1331                 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1332                 if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1333                 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_NO_MEMORY );
1334                 return NULL;
1335             }
1336
1337             /* Build the in-use arena */
1338
1339             list_remove( &pNew->entry );
1340             pInUse = (ARENA_INUSE *)pNew;
1341             pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
1342                            + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1343             pInUse->magic = ARENA_INUSE_MAGIC;
1344             HEAP_ShrinkBlock( newsubheap, pInUse, rounded_size );
1345             mark_block_initialized( pInUse + 1, oldSize );
1346             memcpy( pInUse + 1, pArena + 1, oldSize );
1347
1348             /* Free the previous block */
1349
1350             HEAP_MakeInUseBlockFree( subheap, pArena );
1351             subheap = newsubheap;
1352             pArena  = pInUse;
1353         }
1354     }
1355     else HEAP_ShrinkBlock( subheap, pArena, rounded_size );  /* Shrink the block */
1356
1357     pArena->unused_bytes = (pArena->size & ARENA_SIZE_MASK) - size;
1358
1359     /* Clear the extra bytes if needed */
1360
1361     if (rounded_size > oldSize)
1362     {
1363         if (flags & HEAP_ZERO_MEMORY)
1364             clear_block( (char *)(pArena + 1) + oldSize,
1365                          (pArena->size & ARENA_SIZE_MASK) - oldSize );
1366         else
1367             mark_block_uninitialized( (char *)(pArena + 1) + oldSize,
1368                                       (pArena->size & ARENA_SIZE_MASK) - oldSize );
1369     }
1370
1371     /* Return the new arena */
1372
1373     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1374
1375     TRACE("(%p,%08lx,%p,%08lx): returning %p\n", heap, flags, ptr, size, pArena + 1 );
1376     return (LPVOID)(pArena + 1);
1377
1378 error:
1379     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1380     RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1381     TRACE("(%p,%08lx,%p,%08lx): returning NULL\n", heap, flags, ptr, size );
1382     return NULL;
1383 }
1384
1385
1386 /***********************************************************************
1387  *           RtlCompactHeap   (NTDLL.@)
1388  *
1389  * Compact the free space in a Heap.
1390  *
1391  * PARAMS
1392  *  heap  [I] Heap that block was allocated from
1393  *  flags [I] HEAP_ flags from "winnt.h"
1394  *
1395  * RETURNS
1396  *  The number of bytes compacted.
1397  *
1398  * NOTES
1399  *  This function is a harmless stub.
1400  */
1401 ULONG WINAPI RtlCompactHeap( HANDLE heap, ULONG flags )
1402 {
1403     FIXME( "stub\n" );
1404     return 0;
1405 }
1406
1407
1408 /***********************************************************************
1409  *           RtlLockHeap   (NTDLL.@)
1410  *
1411  * Lock a Heap.
1412  *
1413  * PARAMS
1414  *  heap  [I] Heap to lock
1415  *
1416  * RETURNS
1417  *  Success: TRUE. The Heap is locked.
1418  *  Failure: FALSE, if heap is invalid.
1419  */
1420 BOOLEAN WINAPI RtlLockHeap( HANDLE heap )
1421 {
1422     HEAP *heapPtr = HEAP_GetPtr( heap );
1423     if (!heapPtr) return FALSE;
1424     RtlEnterCriticalSection( &heapPtr->critSection );
1425     return TRUE;
1426 }
1427
1428
1429 /***********************************************************************
1430  *           RtlUnlockHeap   (NTDLL.@)
1431  *
1432  * Unlock a Heap.
1433  *
1434  * PARAMS
1435  *  heap  [I] Heap to unlock
1436  *
1437  * RETURNS
1438  *  Success: TRUE. The Heap is unlocked.
1439  *  Failure: FALSE, if heap is invalid.
1440  */
1441 BOOLEAN WINAPI RtlUnlockHeap( HANDLE heap )
1442 {
1443     HEAP *heapPtr = HEAP_GetPtr( heap );
1444     if (!heapPtr) return FALSE;
1445     RtlLeaveCriticalSection( &heapPtr->critSection );
1446     return TRUE;
1447 }
1448
1449
1450 /***********************************************************************
1451  *           RtlSizeHeap   (NTDLL.@)
1452  *
1453  * Get the actual size of a memory block allocated from a Heap.
1454  *
1455  * PARAMS
1456  *  heap  [I] Heap that block was allocated from
1457  *  flags [I] HEAP_ flags from "winnt.h"
1458  *  ptr   [I] Block to get the size of
1459  *
1460  * RETURNS
1461  *  Success: The size of the block.
1462  *  Failure: -1, heap or ptr are invalid.
1463  *
1464  * NOTES
1465  *  The size may be bigger than what was passed to RtlAllocateHeap().
1466  */
1467 SIZE_T WINAPI RtlSizeHeap( HANDLE heap, ULONG flags, PVOID ptr )
1468 {
1469     SIZE_T ret;
1470     HEAP *heapPtr = HEAP_GetPtr( heap );
1471
1472     if (!heapPtr)
1473     {
1474         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1475         return ~0UL;
1476     }
1477     flags &= HEAP_NO_SERIALIZE;
1478     flags |= heapPtr->flags;
1479     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1480     if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1481     {
1482         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1483         ret = ~0UL;
1484     }
1485     else
1486     {
1487         ARENA_INUSE *pArena = (ARENA_INUSE *)ptr - 1;
1488         ret = (pArena->size & ARENA_SIZE_MASK) - pArena->unused_bytes;
1489     }
1490     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1491
1492     TRACE("(%p,%08lx,%p): returning %08lx\n", heap, flags, ptr, ret );
1493     return ret;
1494 }
1495
1496
1497 /***********************************************************************
1498  *           RtlValidateHeap   (NTDLL.@)
1499  *
1500  * Determine if a block is a valid allocation from a heap.
1501  *
1502  * PARAMS
1503  *  heap  [I] Heap that block was allocated from
1504  *  flags [I] HEAP_ flags from "winnt.h"
1505  *  ptr   [I] Block to check
1506  *
1507  * RETURNS
1508  *  Success: TRUE. The block was allocated from heap.
1509  *  Failure: FALSE, if heap is invalid or ptr was not allocated from it.
1510  */
1511 BOOLEAN WINAPI RtlValidateHeap( HANDLE heap, ULONG flags, LPCVOID ptr )
1512 {
1513     HEAP *heapPtr = HEAP_GetPtr( heap );
1514     if (!heapPtr) return FALSE;
1515     return HEAP_IsRealArena( heapPtr, flags, ptr, QUIET );
1516 }
1517
1518
1519 /***********************************************************************
1520  *           RtlWalkHeap    (NTDLL.@)
1521  *
1522  * FIXME
1523  *  The PROCESS_HEAP_ENTRY flag values seem different between this
1524  *  function and HeapWalk(). To be checked.
1525  */
1526 NTSTATUS WINAPI RtlWalkHeap( HANDLE heap, PVOID entry_ptr )
1527 {
1528     LPPROCESS_HEAP_ENTRY entry = entry_ptr; /* FIXME */
1529     HEAP *heapPtr = HEAP_GetPtr(heap);
1530     SUBHEAP *sub, *currentheap = NULL;
1531     NTSTATUS ret;
1532     char *ptr;
1533     int region_index = 0;
1534
1535     if (!heapPtr || !entry) return STATUS_INVALID_PARAMETER;
1536
1537     if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1538
1539     /* set ptr to the next arena to be examined */
1540
1541     if (!entry->lpData) /* first call (init) ? */
1542     {
1543         TRACE("begin walking of heap %p.\n", heap);
1544         currentheap = &heapPtr->subheap;
1545         ptr = (char*)currentheap + currentheap->headerSize;
1546     }
1547     else
1548     {
1549         ptr = entry->lpData;
1550         sub = &heapPtr->subheap;
1551         while (sub)
1552         {
1553             if (((char *)ptr >= (char *)sub) &&
1554                 ((char *)ptr < (char *)sub + sub->size))
1555             {
1556                 currentheap = sub;
1557                 break;
1558             }
1559             sub = sub->next;
1560             region_index++;
1561         }
1562         if (currentheap == NULL)
1563         {
1564             ERR("no matching subheap found, shouldn't happen !\n");
1565             ret = STATUS_NO_MORE_ENTRIES;
1566             goto HW_end;
1567         }
1568
1569         ptr += entry->cbData; /* point to next arena */
1570         if (ptr > (char *)currentheap + currentheap->size - 1)
1571         {   /* proceed with next subheap */
1572             if (!(currentheap = currentheap->next))
1573             {  /* successfully finished */
1574                 TRACE("end reached.\n");
1575                 ret = STATUS_NO_MORE_ENTRIES;
1576                 goto HW_end;
1577             }
1578             ptr = (char*)currentheap + currentheap->headerSize;
1579         }
1580     }
1581
1582     entry->wFlags = 0;
1583     if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1584     {
1585         ARENA_FREE *pArena = (ARENA_FREE *)ptr;
1586
1587         /*TRACE("free, magic: %04x\n", pArena->magic);*/
1588
1589         entry->lpData = pArena + 1;
1590         entry->cbData = pArena->size & ARENA_SIZE_MASK;
1591         entry->cbOverhead = sizeof(ARENA_FREE);
1592         entry->wFlags = PROCESS_HEAP_UNCOMMITTED_RANGE;
1593     }
1594     else
1595     {
1596         ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
1597
1598         /*TRACE("busy, magic: %04x\n", pArena->magic);*/
1599
1600         entry->lpData = pArena + 1;
1601         entry->cbData = pArena->size & ARENA_SIZE_MASK;
1602         entry->cbOverhead = sizeof(ARENA_INUSE);
1603         entry->wFlags = PROCESS_HEAP_ENTRY_BUSY;
1604         /* FIXME: can't handle PROCESS_HEAP_ENTRY_MOVEABLE
1605         and PROCESS_HEAP_ENTRY_DDESHARE yet */
1606     }
1607
1608     entry->iRegionIndex = region_index;
1609
1610     /* first element of heap ? */
1611     if (ptr == (char *)(currentheap + currentheap->headerSize))
1612     {
1613         entry->wFlags |= PROCESS_HEAP_REGION;
1614         entry->u.Region.dwCommittedSize = currentheap->commitSize;
1615         entry->u.Region.dwUnCommittedSize =
1616                 currentheap->size - currentheap->commitSize;
1617         entry->u.Region.lpFirstBlock = /* first valid block */
1618                 currentheap + currentheap->headerSize;
1619         entry->u.Region.lpLastBlock  = /* first invalid block */
1620                 currentheap + currentheap->size;
1621     }
1622     ret = STATUS_SUCCESS;
1623     if (TRACE_ON(heap)) HEAP_DumpEntry(entry);
1624
1625 HW_end:
1626     if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1627     return ret;
1628 }
1629
1630
1631 /***********************************************************************
1632  *           RtlGetProcessHeaps    (NTDLL.@)
1633  *
1634  * Get the Heaps belonging to the current process.
1635  *
1636  * PARAMS
1637  *  count [I] size of heaps
1638  *  heaps [O] Destination array for heap HANDLE's
1639  *
1640  * RETURNS
1641  *  Success: The number of Heaps allocated by the process.
1642  *  Failure: 0.
1643  */
1644 ULONG WINAPI RtlGetProcessHeaps( ULONG count, HANDLE *heaps )
1645 {
1646     ULONG total = 1;  /* main heap */
1647     struct list *ptr;
1648
1649     RtlEnterCriticalSection( &processHeap->critSection );
1650     LIST_FOR_EACH( ptr, &processHeap->entry ) total++;
1651     if (total <= count)
1652     {
1653         *heaps++ = processHeap;
1654         LIST_FOR_EACH( ptr, &processHeap->entry )
1655             *heaps++ = LIST_ENTRY( ptr, HEAP, entry );
1656     }
1657     RtlLeaveCriticalSection( &processHeap->critSection );
1658     return total;
1659 }