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