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