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