git.oblomov.eu Git - wine/blob - 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 }