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