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