reactos/lib/rtl/heap.c

   1 /* COPYRIGHT:       See COPYING in the top level directory
   2  * PROJECT:         ReactOS system libraries
   3  * FILE:            lib/rtl/image.c
   4  * PURPOSE:         Image handling functions
   5  * PROGRAMMERS:     Copyright 1996 Alexandre Julliard
   6  *                  Copyright 1998 Ulrich Weigand
   7  */
   8
   9 //
  10 // Note: This is a slightly modified implementation of WINE's.
  11 //
  12 // WINE's implementation is a hack based on Windows 95's heap implementation,
  13 // itself a hack of DOS memory management.It supports 3 out of the 18 possible
  14 // NT Heap Flags, does not support custom allocation/deallocation routines,
  15 // and is about 50-80x slower with fragmentation rates up to 500x higher when
  16 // compared to NT's LFH. WINE is lucky because the advanced NT Heap features are
  17 // used in kernel-mode usually, not in user-mode, and they are crossing their
  18 // fingers for this being the same. Note that several high-end SQL/Database
  19 // applications would significantly benefit from custom heap features provided
  20 // by NT.
  21 //
  22 // ROS's changes include:
  23 //  - Using Zw instead of Nt calls, because this matters when in Kernel Mode
  24 //  - Not using per-process heap lists while in Kernel Mode
  25 //  - Using a macro to handle the Critical Section, because it's meaningless
  26 //    in Kernel Mode.
  27 //  - Crappy support for a custom Commit routine.
  28 //  - Crappy support for User-defined flags and the User-defined value.
  29 //  - Ripping out all the code for shared heaps, because those don't exist on NT.
  30 //
  31 // Be aware of these changes when you try to sync something back.
  32 //
  33
  34 /* INCLUDES *****************************************************************/
  35
  36 #include <rtl.h>
  37 #undef LIST_FOR_EACH
  38 #undef LIST_FOR_EACH_SAFE
  39 #include <wine/list.h>
  40
  41 #define NDEBUG
  42 #include <debug.h>
  43
  44 #define TRACE DPRINT
  45 #define WARN DPRINT1
  46 #define ERR DPRINT1
  47 #define DPRINTF DPRINT
  48
  49 /* FUNCTIONS *****************************************************************/
  50
  51 #define WARN_ON(x) (1)
  52
  53 #ifdef NDEBUG
  54 #define TRACE_ON(x) (0)
  55 #else
  56 #define TRACE_ON(x) (1)
  57 #endif
  58
  59 /* Note: the heap data structures are based on what Pietrek describes in his
  60  * book 'Windows 95 System Programming Secrets'. The layout is not exactly
  61  * the same, but could be easily adapted if it turns out some programs
  62  * require it.
  63  */
  64
  65 /* FIXME: use SIZE_T for 'size' structure members, but we need to make sure
  66  * that there is no unaligned accesses to structure fields.
  67  */
  68
  69 typedef struct tagARENA_INUSE
  70 {
  71     SIZE_T size;                    /* Block size; must be the first field */
  72     DWORD  magic : 23;              /* Magic number */
  73     DWORD  has_user_data : 1;       /* There is user data associated with this block */
  74     DWORD  unused_bytes : 8;        /* Number of bytes in the block not used by user data (max value is HEAP_MIN_DATA_SIZE+HEAP_MIN_SHRINK_SIZE) */
  75 } ARENA_INUSE;
  76
  77 typedef struct tagARENA_FREE
  78 {
  79     SIZE_T                size;     /* Block size; must be the first field */
  80     DWORD                 magic;    /* Magic number */
  81     struct list           entry;    /* Entry in free list */
  82 } ARENA_FREE;
  83
  84 #define ARENA_FLAG_FREE        0x00000001  /* flags OR'ed with arena size */
  85 #define ARENA_FLAG_PREV_FREE   0x00000002
  86 #define ARENA_SIZE_MASK        (~3)
  87 #define ARENA_INUSE_MAGIC      0x455355        /* Value for arena 'magic' field */
  88 #define ARENA_FREE_MAGIC       0x45455246      /* Value for arena 'magic' field */
  89
  90 #define ARENA_INUSE_FILLER     0x55
  91 #define ARENA_FREE_FILLER      0xaa
  92
  93 /* everything is aligned on 8 byte boundaries (16 for Win64)*/
  94 #define ALIGNMENT              (2*sizeof(void*))
  95 #define ARENA_OFFSET (ALIGNMENT - sizeof(ARENA_INUSE))
  96
  97 #define ROUND_SIZE(size)       ((((size) + ALIGNMENT - 1) & ~(ALIGNMENT-1)) + ARENA_OFFSET)
  98
  99
 100 #define QUIET                  1           /* Suppress messages  */
 101 #define NOISY                  0           /* Report all errors  */
 102
 103 /* minimum data size (without arenas) of an allocated block */
 104 #define HEAP_MIN_DATA_SIZE    ROUND_SIZE(2 * sizeof(struct list))
 105 /* minimum size that must remain to shrink an allocated block */
 106 #define HEAP_MIN_SHRINK_SIZE  (HEAP_MIN_DATA_SIZE+sizeof(ARENA_FREE))
 107
 108 #define HEAP_NB_FREE_LISTS   4   /* Number of free lists */
 109
 110 /* Max size of the blocks on the free lists */
 111 static const DWORD HEAP_freeListSizes[HEAP_NB_FREE_LISTS] =
 112 {
 113     0x20, 0x80, 0x200, ~0UL
 114 };
 115
 116 typedef struct
 117 {
 118     ARENA_FREE  arena;
 119     void        *aligment[4];
 120 } FREE_LIST_ENTRY;
 121
 122 struct tagHEAP;
 123
 124 typedef struct tagSUBHEAP
 125 {
 126     SIZE_T              size;       /* Size of the whole sub-heap */
 127     SIZE_T              commitSize; /* Committed size of the sub-heap */
 128     DWORD               headerSize; /* Size of the heap header */
 129     struct tagSUBHEAP  *next;       /* Next sub-heap */
 130     struct tagHEAP     *heap;       /* Main heap structure */
 131     DWORD               magic;      /* Magic number */
 132 } SUBHEAP;
 133
 134 #define SUBHEAP_MAGIC    ((DWORD)('S' | ('U'<<8) | ('B'<<16) | ('H'<<24)))
 135
 136 typedef struct tagHEAP_USER_DATA
 137 {
 138     LIST_ENTRY          ListEntry;
 139     PVOID               BaseAddress;
 140     ULONG               UserFlags;
 141     PVOID               UserValue;
 142 } HEAP_USER_DATA, *PHEAP_USER_DATA;
 143
 144 typedef struct tagHEAP
 145 {
 146     SUBHEAP          subheap;       /* First sub-heap */
 147     struct list      entry;         /* Entry in process heap list */
 148     RTL_CRITICAL_SECTION critSection; /* Critical section for serialization */
 149     FREE_LIST_ENTRY  freeList[HEAP_NB_FREE_LISTS];  /* Free lists */
 150     DWORD            flags;         /* Heap flags */
 151     DWORD            magic;         /* Magic number */
 152     PRTL_HEAP_COMMIT_ROUTINE commitRoutine;
 153     LIST_ENTRY       UserDataHead;
 154 } HEAP;
 155
 156 #define HEAP_MAGIC       ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
 157
 158 #define HEAP_DEF_SIZE        0x110000   /* Default heap size = 1Mb + 64Kb */
 159 #define COMMIT_MASK          0xffff  /* bitmask for commit/decommit granularity */
 160
 161 static HEAP *processHeap;  /* main process heap */
 162
 163 static BOOL HEAP_IsRealArena( HEAP *heapPtr, DWORD flags, LPCVOID block, BOOL quiet );
 164
 165 /* mark a block of memory as free for debugging purposes */
 166 static __inline void mark_block_free( void *ptr, SIZE_T size )
 167 {
 168     if (TRACE_ON(heap)) memset( ptr, ARENA_FREE_FILLER, size );
 169 #ifdef VALGRIND_MAKE_NOACCESS
 170     VALGRIND_DISCARD( VALGRIND_MAKE_NOACCESS( ptr, size ));
 171 #endif
 172 }
 173
 174 /* mark a block of memory as initialized for debugging purposes */
 175 static __inline void mark_block_initialized( void *ptr, SIZE_T size )
 176 {
 177 #ifdef VALGRIND_MAKE_READABLE
 178     VALGRIND_DISCARD( VALGRIND_MAKE_READABLE( ptr, size ));
 179 #endif
 180 }
 181
 182 /* mark a block of memory as uninitialized for debugging purposes */
 183 static __inline void mark_block_uninitialized( void *ptr, SIZE_T size )
 184 {
 185 #ifdef VALGRIND_MAKE_WRITABLE
 186     VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
 187 #endif
 188     if (TRACE_ON(heap))
 189     {
 190         memset( ptr, ARENA_INUSE_FILLER, size );
 191 #ifdef VALGRIND_MAKE_WRITABLE
 192         /* make it uninitialized to valgrind again */
 193         VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
 194 #endif
 195     }
 196 }
 197
 198 /* clear contents of a block of memory */
 199 static __inline void clear_block( void *ptr, SIZE_T size )
 200 {
 201     mark_block_initialized( ptr, size );
 202     memset( ptr, 0, size );
 203 }
 204
 205 /* locate a free list entry of the appropriate size */
 206 /* size is the size of the whole block including the arena header */
 207 static __inline unsigned int get_freelist_index( SIZE_T size )
 208 {
 209     unsigned int i;
 210
 211     size -= sizeof(ARENA_FREE);
 212     for (i = 0; i < HEAP_NB_FREE_LISTS - 1; i++) if (size <= HEAP_freeListSizes[i]) break;
 213     return i;
 214 }
 215
 216 /* get the memory protection type to use for a given heap */
 217 static inline ULONG get_protection_type( DWORD flags )
 218 {
 219     return (flags & HEAP_CREATE_ENABLE_EXECUTE) ? PAGE_EXECUTE_READWRITE : PAGE_READWRITE;
 220 }
 221
 222 static RTL_CRITICAL_SECTION_DEBUG process_heap_critsect_debug =
 223 {
 224     0, 0, NULL,  /* will be set later */
 225     { &process_heap_critsect_debug.ProcessLocksList, &process_heap_critsect_debug.ProcessLocksList },
 226       0, 0, 0, 0, 0
 227 };
 228
 229 /***********************************************************************
 230  *           HEAP_Dump
 231  */
 232 static void HEAP_Dump( HEAP *heap )
 233 {
 234     int i;
 235     SUBHEAP *subheap;
 236     char *ptr;
 237
 238     DPRINTF( "Heap: %p\n", heap );
 239     DPRINTF( "Next: %p  Sub-heaps: %p",
 240              LIST_ENTRY( heap->entry.next, HEAP, entry ), &heap->subheap );
 241     subheap = &heap->subheap;
 242     while (subheap->next)
 243     {
 244         DPRINTF( " -> %p", subheap->next );
 245         subheap = subheap->next;
 246     }
 247
 248     DPRINTF( "\nFree lists:\n Block   Stat   Size    Id\n" );
 249     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 250         DPRINTF( "%p free %08lx prev=%p next=%p\n",
 251                  &heap->freeList[i].arena, HEAP_freeListSizes[i],
 252                  LIST_ENTRY( heap->freeList[i].arena.entry.prev, ARENA_FREE, entry ),
 253                  LIST_ENTRY( heap->freeList[i].arena.entry.next, ARENA_FREE, entry ));
 254
 255     subheap = &heap->subheap;
 256     while (subheap)
 257     {
 258         SIZE_T freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
 259         DPRINTF( "\n\nSub-heap %p: size=%08lx committed=%08lx\n",
 260                 subheap, subheap->size, subheap->commitSize );
 261
 262         DPRINTF( "\n Block   Stat   Size    Id\n" );
 263         ptr = (char*)subheap + subheap->headerSize;
 264         while (ptr < (char *)subheap + subheap->size)
 265         {
 266             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
 267             {
 268                 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
 269                 DPRINTF( "%p free %08lx prev=%p next=%p\n",
 270                          pArena, pArena->size & ARENA_SIZE_MASK,
 271                          LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ),
 272                          LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ) );
 273                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 274                 arenaSize += sizeof(ARENA_FREE);
 275                 freeSize += pArena->size & ARENA_SIZE_MASK;
 276             }
 277             else if (*(DWORD *)ptr & ARENA_FLAG_PREV_FREE)
 278             {
 279                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 280                 DPRINTF( "%p Used %08lx back=%p\n",
 281                         pArena, pArena->size & ARENA_SIZE_MASK, *((ARENA_FREE **)pArena - 1) );
 282                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 283                 arenaSize += sizeof(ARENA_INUSE);
 284                 usedSize += pArena->size & ARENA_SIZE_MASK;
 285             }
 286             else
 287             {
 288                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 289                 DPRINTF( "%p used %08lx\n", pArena, pArena->size & ARENA_SIZE_MASK );
 290                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 291                 arenaSize += sizeof(ARENA_INUSE);
 292                 usedSize += pArena->size & ARENA_SIZE_MASK;
 293             }
 294         }
 295         DPRINTF( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
 296           subheap->size, subheap->commitSize, freeSize, usedSize,
 297           arenaSize, (arenaSize * 100) / subheap->size );
 298         subheap = subheap->next;
 299     }
 300 }
 301
 302 #if 0
 303 static void HEAP_DumpEntry( LPPROCESS_HEAP_ENTRY entry )
 304 {
 305     WORD rem_flags;
 306     TRACE( "Dumping entry %p\n", entry );
 307     TRACE( "lpData\t\t: %p\n", entry->lpData );
 308     TRACE( "cbData\t\t: %08lx\n", entry->cbData);
 309     TRACE( "cbOverhead\t: %08x\n", entry->cbOverhead);
 310     TRACE( "iRegionIndex\t: %08x\n", entry->iRegionIndex);
 311     TRACE( "WFlags\t\t: ");
 312     if (entry->wFlags & PROCESS_HEAP_REGION)
 313         TRACE( "PROCESS_HEAP_REGION ");
 314     if (entry->wFlags & PROCESS_HEAP_UNCOMMITTED_RANGE)
 315         TRACE( "PROCESS_HEAP_UNCOMMITTED_RANGE ");
 316     if (entry->wFlags & PROCESS_HEAP_ENTRY_BUSY)
 317         TRACE( "PROCESS_HEAP_ENTRY_BUSY ");
 318     if (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE)
 319         TRACE( "PROCESS_HEAP_ENTRY_MOVEABLE ");
 320     if (entry->wFlags & PROCESS_HEAP_ENTRY_DDESHARE)
 321         TRACE( "PROCESS_HEAP_ENTRY_DDESHARE ");
 322     rem_flags = entry->wFlags &
 323         ~(PROCESS_HEAP_REGION | PROCESS_HEAP_UNCOMMITTED_RANGE |
 324           PROCESS_HEAP_ENTRY_BUSY | PROCESS_HEAP_ENTRY_MOVEABLE|
 325           PROCESS_HEAP_ENTRY_DDESHARE);
 326     if (rem_flags)
 327         TRACE( "Unknown %08x", rem_flags);
 328     TRACE( "\n");
 329     if ((entry->wFlags & PROCESS_HEAP_ENTRY_BUSY )
 330         && (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE))
 331     {
 332         /* Treat as block */
 333         TRACE( "BLOCK->hMem\t\t:%p\n", entry->Block.hMem);
 334     }
 335     if (entry->wFlags & PROCESS_HEAP_REGION)
 336     {
 337         TRACE( "Region.dwCommittedSize\t:%08lx\n",entry->Region.dwCommittedSize);
 338         TRACE( "Region.dwUnCommittedSize\t:%08lx\n",entry->Region.dwUnCommittedSize);
 339         TRACE( "Region.lpFirstBlock\t:%p\n",entry->Region.lpFirstBlock);
 340         TRACE( "Region.lpLastBlock\t:%p\n",entry->Region.lpLastBlock);
 341     }
 342 }
 343 #endif
 344
 345 static PHEAP_USER_DATA HEAP_GetUserData(HEAP *heapPtr, PVOID BaseAddress)
 346 {
 347   PLIST_ENTRY CurrentEntry;
 348   PHEAP_USER_DATA udata;
 349
 350   CurrentEntry = heapPtr->UserDataHead.Flink;
 351   while (CurrentEntry != &heapPtr->UserDataHead)
 352   {
 353       udata = CONTAINING_RECORD(CurrentEntry, HEAP_USER_DATA, ListEntry);
 354       if (udata->BaseAddress == BaseAddress)
 355           return udata;
 356       CurrentEntry = CurrentEntry->Flink;
 357   }
 358   return NULL;
 359 }
 360
 361 static PHEAP_USER_DATA HEAP_AllocUserData(HEAP *heapPtr, PVOID BaseAddress)
 362 {
 363     /* Allocate user data entry */
 364     ARENA_INUSE *pInUse;
 365     PHEAP_USER_DATA udata = RtlAllocateHeap(heapPtr, 0, sizeof(HEAP_USER_DATA));
 366     if (!udata) return NULL;
 367     udata->BaseAddress = BaseAddress;
 368     InsertTailList(&heapPtr->UserDataHead, &udata->ListEntry);
 369     pInUse  = (ARENA_INUSE *)BaseAddress - 1;
 370     pInUse->has_user_data = 1;
 371     return udata;
 372 }
 373
 374 /***********************************************************************
 375  *           HEAP_GetPtr
 376  * RETURNS
 377  *      Pointer to the heap
 378  *      NULL: Failure
 379  */
 380 static HEAP *HEAP_GetPtr(
 381              HANDLE heap /* [in] Handle to the heap */
 382 ) {
 383     HEAP *heapPtr = (HEAP *)heap;
 384     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
 385     {
 386         if (heapPtr)
 387             ERR("Invalid heap %p, magic:%.4s!\n", heap, &heapPtr->magic );
 388         else
 389             ERR("Invalid heap %p!\n", heap );
 390         //KeDumpStackFrames(NULL);
 391         return NULL;
 392     }
 393     if (TRACE_ON(heap) && !HEAP_IsRealArena( heapPtr, 0, NULL, NOISY ))
 394     {
 395         HEAP_Dump( heapPtr );
 396         assert( FALSE );
 397         return NULL;
 398     }
 399     return heapPtr;
 400 }
 401
 402
 403 /***********************************************************************
 404  *           HEAP_InsertFreeBlock
 405  *
 406  * Insert a free block into the free list.
 407  */
 408 static __inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last )
 409 {
 410     FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( pArena->size + sizeof(*pArena) );
 411     if (last)
 412     {
 413         /* insert at end of free list, i.e. before the next free list entry */
 414         pEntry++;
 415         if (pEntry == &heap->freeList[HEAP_NB_FREE_LISTS]) pEntry = heap->freeList;
 416         list_add_before( &pEntry->arena.entry, &pArena->entry );
 417     }
 418     else
 419     {
 420         /* insert at head of free list */
 421         list_add_after( &pEntry->arena.entry, &pArena->entry );
 422     }
 423     pArena->size |= ARENA_FLAG_FREE;
 424 }
 425
 426
 427 /***********************************************************************
 428  *           HEAP_FindSubHeap
 429  * Find the sub-heap containing a given address.
 430  *
 431  * RETURNS
 432  *      Pointer: Success
 433  *      NULL: Failure
 434  */
 435 static SUBHEAP *HEAP_FindSubHeap(
 436                 const HEAP *heap, /* [in] Heap pointer */
 437                 LPCVOID ptr /* [in] Address */
 438 ) {
 439     const SUBHEAP *sub = &heap->subheap;
 440     while (sub)
 441     {
 442         if (((const char *)ptr >= (const char *)sub) &&
 443             ((const char *)ptr < (const char *)sub + sub->size)) return (SUBHEAP*)sub;
 444         sub = sub->next;
 445     }
 446     return NULL;
 447 }
 448
 449 /***********************************************************************
 450  *           HEAP_Commit
 451  *
 452  * Make sure the heap storage is committed for a given size in the specified arena.
 453  */
 454 static __inline BOOL HEAP_Commit( SUBHEAP *subheap, ARENA_INUSE *pArena, SIZE_T data_size )
 455 {
 456     NTSTATUS Status;
 457     void *ptr = (char *)(pArena + 1) + data_size + sizeof(ARENA_FREE);
 458     SIZE_T size = (char *)ptr - (char *)subheap;
 459     size = (size + COMMIT_MASK) & ~COMMIT_MASK;
 460     if (size > subheap->size) size = subheap->size;
 461     if (size <= subheap->commitSize) return TRUE;
 462     size -= subheap->commitSize;
 463     ptr = (char *)subheap + subheap->commitSize;
 464    if (subheap->heap->commitRoutine != NULL)
 465    {
 466       Status = subheap->heap->commitRoutine(subheap->heap, &ptr, &size);
 467    }
 468    else
 469    {
 470         Status = ZwAllocateVirtualMemory( NtCurrentProcess(), &ptr, 0,
 471                                  &size, MEM_COMMIT, get_protection_type(subheap->heap->flags) );
 472    }
 473     if (!NT_SUCCESS(Status))
 474     {
 475         WARN("Could not commit %08lx bytes at %p for heap %p\n",
 476                  size, ptr, subheap->heap );
 477         return FALSE;
 478     }
 479     subheap->commitSize += size;
 480     return TRUE;
 481 }
 482
 483 #if 0
 484 /***********************************************************************
 485  *           HEAP_Decommit
 486  *
 487  * If possible, decommit the heap storage from (including) 'ptr'.
 488  */
 489 static inline BOOL HEAP_Decommit( SUBHEAP *subheap, void *ptr )
 490 {
 491     void *addr;
 492     SIZE_T decommit_size;
 493     SIZE_T size = (char *)ptr - (char *)subheap;
 494
 495     /* round to next block and add one full block */
 496     size = ((size + COMMIT_MASK) & ~COMMIT_MASK) + COMMIT_MASK + 1;
 497     if (size >= subheap->commitSize) return TRUE;
 498     decommit_size = subheap->commitSize - size;
 499     addr = (char *)subheap + size;
 500
 501     if (ZwFreeVirtualMemory( NtCurrentProcess(), &addr, &decommit_size, MEM_DECOMMIT ))
 502     {
 503         WARN("Could not decommit %08lx bytes at %p for heap %p\n",
 504                 decommit_size, (char *)subheap + size, subheap->heap );
 505         return FALSE;
 506     }
 507     subheap->commitSize -= decommit_size;
 508     return TRUE;
 509 }
 510 #endif
 511
 512 /***********************************************************************
 513  *           HEAP_CreateFreeBlock
 514  *
 515  * Create a free block at a specified address. 'size' is the size of the
 516  * whole block, including the new arena.
 517  */
 518 static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, SIZE_T size )
 519 {
 520     ARENA_FREE *pFree;
 521     char *pEnd;
 522     BOOL last;
 523
 524     /* Create a free arena */
 525     mark_block_uninitialized( ptr, sizeof( ARENA_FREE ) );
 526     pFree = (ARENA_FREE *)ptr;
 527     pFree->magic = ARENA_FREE_MAGIC;
 528
 529     /* If debugging, erase the freed block content */
 530
 531     pEnd = (char *)ptr + size;
 532     if (pEnd > (char *)subheap + subheap->commitSize) pEnd = (char *)subheap + subheap->commitSize;
 533     if (pEnd > (char *)(pFree + 1)) mark_block_free( pFree + 1, pEnd - (char *)(pFree + 1) );
 534
 535     /* Check if next block is free also */
 536
 537     if (((char *)ptr + size < (char *)subheap + subheap->size) &&
 538         (*(DWORD *)((char *)ptr + size) & ARENA_FLAG_FREE))
 539     {
 540         /* Remove the next arena from the free list */
 541         ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
 542         list_remove( &pNext->entry );
 543         size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
 544         mark_block_free( pNext, sizeof(ARENA_FREE) );
 545     }
 546
 547     /* Set the next block PREV_FREE flag and pointer */
 548
 549     last = ((char *)ptr + size >= (char *)subheap + subheap->size);
 550     if (!last)
 551     {
 552         DWORD *pNext = (DWORD *)((char *)ptr + size);
 553         *pNext |= ARENA_FLAG_PREV_FREE;
 554         mark_block_initialized( pNext - 1, sizeof( ARENA_FREE * ) );
 555         *((ARENA_FREE **)pNext - 1) = pFree;
 556     }
 557
 558     /* Last, insert the new block into the free list */
 559
 560     pFree->size = size - sizeof(*pFree);
 561     HEAP_InsertFreeBlock( subheap->heap, pFree, last );
 562 }
 563
 564
 565 /***********************************************************************
 566  *           HEAP_MakeInUseBlockFree
 567  *
 568  * Turn an in-use block into a free block. Can also decommit the end of
 569  * the heap, and possibly even free the sub-heap altogether.
 570  */
 571 static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
 572 {
 573     ARENA_FREE *pFree;
 574     SIZE_T size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
 575     PHEAP_USER_DATA udata;
 576
 577     /* Find and free user data */
 578     if (pArena->has_user_data)
 579     {
 580         udata = HEAP_GetUserData(subheap->heap, pArena + 1);
 581         if (udata)
 582         {
 583             RemoveEntryList(&udata->ListEntry);
 584             RtlFreeHeap(subheap->heap, 0, udata);
 585         }
 586     }
 587
 588     /* Check if we can merge with previous block */
 589
 590     if (pArena->size & ARENA_FLAG_PREV_FREE)
 591     {
 592         pFree = *((ARENA_FREE **)pArena - 1);
 593         size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
 594         /* Remove it from the free list */
 595         list_remove( &pFree->entry );
 596     }
 597     else pFree = (ARENA_FREE *)pArena;
 598
 599     /* Create a free block */
 600
 601     HEAP_CreateFreeBlock( subheap, pFree, size );
 602     size = (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
 603     if ((char *)pFree + size < (char *)subheap + subheap->size)
 604         return;  /* Not the last block, so nothing more to do */
 605
 606     /* Free the whole sub-heap if it's empty and not the original one */
 607
 608     if (((char *)pFree == (char *)subheap + subheap->headerSize) &&
 609         (subheap != &subheap->heap->subheap))
 610     {
 611         SIZE_T size = 0;
 612         SUBHEAP *pPrev = &subheap->heap->subheap;
 613         /* Remove the free block from the list */
 614         list_remove( &pFree->entry );
 615         /* Remove the subheap from the list */
 616         while (pPrev && (pPrev->next != subheap)) pPrev = pPrev->next;
 617         if (pPrev) pPrev->next = subheap->next;
 618         /* Free the memory */
 619         subheap->magic = 0;
 620         ZwFreeVirtualMemory( NtCurrentProcess(), (void **)&subheap, &size, MEM_RELEASE );
 621         return;
 622     }
 623
 624     /* Decommit the end of the heap */
 625 }
 626
 627 /***********************************************************************
 628  *           HEAP_ShrinkBlock
 629  *
 630  * Shrink an in-use block.
 631  */
 632 static void HEAP_ShrinkBlock(SUBHEAP *subheap, ARENA_INUSE *pArena, SIZE_T size)
 633 {
 634     if ((pArena->size & ARENA_SIZE_MASK) >= size + HEAP_MIN_SHRINK_SIZE)
 635     {
 636         HEAP_CreateFreeBlock( subheap, (char *)(pArena + 1) + size,
 637                               (pArena->size & ARENA_SIZE_MASK) - size );
 638         /* assign size plus previous arena flags */
 639         pArena->size = size | (pArena->size & ~ARENA_SIZE_MASK);
 640     }
 641     else
 642     {
 643         /* Turn off PREV_FREE flag in next block */
 644         char *pNext = (char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK);
 645         if (pNext < (char *)subheap + subheap->size)
 646             *(DWORD *)pNext &= ~ARENA_FLAG_PREV_FREE;
 647     }
 648 }
 649
 650 /***********************************************************************
 651  *           HEAP_InitSubHeap
 652  */
 653 static BOOL HEAP_InitSubHeap( HEAP *heap, LPVOID address, DWORD flags,
 654                               SIZE_T commitSize, SIZE_T totalSize,
 655                               PRTL_HEAP_PARAMETERS Parameters)
 656 {
 657     SUBHEAP *subheap;
 658     FREE_LIST_ENTRY *pEntry;
 659     int i;
 660     NTSTATUS Status;
 661
 662     if (!address && ZwAllocateVirtualMemory( NtCurrentProcess(), &address, 0,
 663                                  &commitSize, MEM_COMMIT, get_protection_type(flags) ))
 664     {
 665         WARN("Could not commit %08lx bytes for sub-heap %p\n", commitSize, address );
 666         return FALSE;
 667     }
 668
 669     /* Fill the sub-heap structure */
 670
 671     subheap = (SUBHEAP *)address;
 672     subheap->heap       = heap;
 673     subheap->size       = totalSize;
 674     subheap->commitSize = commitSize;
 675     subheap->magic      = SUBHEAP_MAGIC;
 676
 677     if ( subheap != (SUBHEAP *)heap )
 678     {
 679         /* If this is a secondary subheap, insert it into list */
 680
 681         subheap->headerSize = ROUND_SIZE( sizeof(SUBHEAP) );
 682         subheap->next       = heap->subheap.next;
 683         heap->subheap.next  = subheap;
 684     }
 685     else
 686     {
 687         /* If this is a primary subheap, initialize main heap */
 688
 689         subheap->headerSize = ROUND_SIZE( sizeof(HEAP) );
 690         subheap->next       = NULL;
 691         heap->flags         = flags;
 692         heap->magic         = HEAP_MAGIC;
 693       if (Parameters)
 694          heap->commitRoutine = Parameters->CommitRoutine;
 695       else
 696          heap->commitRoutine = NULL;
 697         InitializeListHead(&heap->UserDataHead);
 698
 699         /* Build the free lists */
 700
 701         list_init( &heap->freeList[0].arena.entry );
 702         for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
 703         {
 704             pEntry->arena.size = 0 | ARENA_FLAG_FREE;
 705             pEntry->arena.magic = ARENA_FREE_MAGIC;
 706             if (i) list_add_after( &pEntry[-1].arena.entry, &pEntry->arena.entry );
 707         }
 708
 709           /* Initialize critical section */
 710
 711           if (RtlpGetMode() == UserMode)
 712           {
 713             if (!processHeap)  /* do it by hand to avoid memory allocations */
 714             {
 715                 heap->critSection.DebugInfo      = &process_heap_critsect_debug;
 716                 heap->critSection.LockCount      = -1;
 717                 heap->critSection.RecursionCount = 0;
 718                 heap->critSection.OwningThread   = 0;
 719                 heap->critSection.LockSemaphore  = 0;
 720                 heap->critSection.SpinCount      = 0;
 721                 process_heap_critsect_debug.CriticalSection = &heap->critSection;
 722             }
 723             else RtlInitializeHeapLock( &heap->critSection );
 724           }
 725     }
 726
 727     /* Commit memory */
 728     if (heap->commitRoutine)
 729     {
 730       if (subheap != (SUBHEAP *)heap)
 731       {
 732          Status = heap->commitRoutine(heap, &address, &commitSize);
 733       }
 734       else
 735       {
 736          /* the caller is responsible for committing the first page! */
 737          Status = STATUS_SUCCESS;
 738       }
 739     }
 740     else
 741     {
 742       Status = ZwAllocateVirtualMemory(NtCurrentProcess(),
 743                                        &address,
 744                                        0,
 745                                        &commitSize,
 746                                        MEM_COMMIT,
 747                                        get_protection_type(flags));
 748     }
 749     if (!NT_SUCCESS(Status))
 750     {
 751       DPRINT("Could not commit %08lx bytes for sub-heap %p\n",
 752              commitSize, address);
 753       return FALSE;
 754     }
 755
 756     /* Create the first free block */
 757
 758     HEAP_CreateFreeBlock( subheap, (LPBYTE)subheap + subheap->headerSize,
 759                           subheap->size - subheap->headerSize );
 760
 761     return TRUE;
 762 }
 763
 764 /***********************************************************************
 765  *           HEAP_CreateSubHeap
 766  *
 767  * Create a sub-heap of the given size.
 768  * If heap == NULL, creates a main heap.
 769  */
 770 static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, void *base, DWORD flags,
 771                                     SIZE_T commitSize, SIZE_T totalSize,
 772                                     IN PRTL_HEAP_PARAMETERS Parameters)
 773 {
 774     LPVOID address = base;
 775
 776     /* round-up sizes on a 64K boundary */
 777     totalSize  = (totalSize + 0xffff) & 0xffff0000;
 778     commitSize = (commitSize + 0xffff) & 0xffff0000;
 779     if (!commitSize) commitSize = 0x10000;
 780     totalSize = min( totalSize, 0xffff0000 );  /* don't allow a heap larger than 4Gb */
 781     if (totalSize < commitSize) totalSize = commitSize;
 782
 783     if (!address)
 784     {
 785         /* allocate the memory block */
 786         if (ZwAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &totalSize,
 787                                      MEM_RESERVE | MEM_COMMIT, get_protection_type(flags) ))
 788         {
 789             WARN("Could not allocate %08lx bytes\n", totalSize );
 790             return NULL;
 791         }
 792     }
 793
 794     /* Initialize subheap */
 795
 796     if (!HEAP_InitSubHeap( heap ? heap : (HEAP *)address,
 797                            address, flags, commitSize, totalSize, Parameters ))
 798     {
 799         SIZE_T size = 0;
 800         if (!base) ZwFreeVirtualMemory( NtCurrentProcess(), &address, &size, MEM_RELEASE );
 801         return NULL;
 802     }
 803
 804     return (SUBHEAP *)address;
 805 }
 806
 807
 808 /***********************************************************************
 809  *           HEAP_FindFreeBlock
 810  *
 811  * Find a free block at least as large as the requested size, and make sure
 812  * the requested size is committed.
 813  */
 814 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size,
 815                                        SUBHEAP **ppSubHeap )
 816 {
 817     SUBHEAP *subheap;
 818     struct list *ptr;
 819     SIZE_T total_size;
 820     FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( size + sizeof(ARENA_INUSE) );
 821
 822     /* Find a suitable free list, and in it find a block large enough */
 823
 824     ptr = &pEntry->arena.entry;
 825     while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
 826     {
 827         ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
 828         SIZE_T arena_size = (pArena->size & ARENA_SIZE_MASK) +
 829                             sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
 830         if (arena_size >= size)
 831         {
 832             subheap = HEAP_FindSubHeap( heap, pArena );
 833             if (!HEAP_Commit( subheap, (ARENA_INUSE *)pArena, size )) return NULL;
 834             *ppSubHeap = subheap;
 835             return pArena;
 836         }
 837     }
 838
 839     /* If no block was found, attempt to grow the heap */
 840
 841     if (!(heap->flags & HEAP_GROWABLE))
 842     {
 843         ERR("Not enough space in heap %p for %08lx bytes\n", heap, size );
 844         return NULL;
 845     }
 846     /* make sure that we have a big enough size *committed* to fit another
 847      * last free arena in !
 848      * So just one heap struct, one first free arena which will eventually
 849      * get used, and a second free arena that might get assigned all remaining
 850      * free space in HEAP_ShrinkBlock() */
 851     total_size = size + ROUND_SIZE(sizeof(SUBHEAP)) + sizeof(ARENA_INUSE) + sizeof(ARENA_FREE);
 852     if (total_size < size) return NULL;  /* overflow */
 853
 854     if (!(subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, total_size,
 855                                         max( HEAP_DEF_SIZE, total_size ), NULL )))
 856         return NULL;
 857
 858     TRACE("created new sub-heap %p of %08lx bytes for heap %p\n",
 859             subheap, size, heap );
 860
 861     *ppSubHeap = subheap;
 862     return (ARENA_FREE *)(subheap + 1);
 863 }
 864
 865 /***********************************************************************
 866  *           HEAP_IsValidArenaPtr
 867  *
 868  * Check that the pointer is inside the range possible for arenas.
 869  */
 870 static BOOL HEAP_IsValidArenaPtr( const HEAP *heap, const void *ptr )
 871 {
 872     int i;
 873     const SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
 874     if (!subheap) return FALSE;
 875     if ((const char *)ptr >= (const char *)subheap + subheap->headerSize) return TRUE;
 876     if (subheap != &heap->subheap) return FALSE;
 877     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 878         if (ptr == (const void *)&heap->freeList[i].arena) return TRUE;
 879     return FALSE;
 880 }
 881
 882
 883 /***********************************************************************
 884  *           HEAP_ValidateFreeArena
 885  */
 886 static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
 887 {
 888     ARENA_FREE *prev, *next;
 889     char *heapEnd = (char *)subheap + subheap->size;
 890
 891     /* Check for unaligned pointers */
 892     if ( (ULONG_PTR)pArena % ALIGNMENT != ARENA_OFFSET )
 893     {
 894         ERR("Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
 895         return FALSE;
 896     }
 897
 898     /* Check magic number */
 899     if (pArena->magic != ARENA_FREE_MAGIC)
 900     {
 901         ERR("Heap %p: invalid free arena magic for %p\n", subheap->heap, pArena );
 902         return FALSE;
 903     }
 904     /* Check size flags */
 905     if (!(pArena->size & ARENA_FLAG_FREE) ||
 906         (pArena->size & ARENA_FLAG_PREV_FREE))
 907     {
 908         ERR("Heap %p: bad flags %08lx for free arena %p\n",
 909             subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
 910         return FALSE;
 911     }
 912     /* Check arena size */
 913     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
 914     {
 915         ERR("Heap %p: bad size %08lx for free arena %p\n",
 916             subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
 917         return FALSE;
 918     }
 919     /* Check that next pointer is valid */
 920     next = LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry );
 921     if (!HEAP_IsValidArenaPtr( subheap->heap, next ))
 922     {
 923         ERR("Heap %p: bad next ptr %p for arena %p\n",
 924             subheap->heap, next, pArena );
 925         return FALSE;
 926     }
 927     /* Check that next arena is free */
 928     if (!(next->size & ARENA_FLAG_FREE) || (next->magic != ARENA_FREE_MAGIC))
 929     {
 930         ERR("Heap %p: next arena %p invalid for %p\n",
 931             subheap->heap, next, pArena );
 932         return FALSE;
 933     }
 934     /* Check that prev pointer is valid */
 935     prev = LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry );
 936     if (!HEAP_IsValidArenaPtr( subheap->heap, prev ))
 937     {
 938         ERR("Heap %p: bad prev ptr %p for arena %p\n",
 939             subheap->heap, prev, pArena );
 940         return FALSE;
 941     }
 942     /* Check that prev arena is free */
 943     if (!(prev->size & ARENA_FLAG_FREE) || (prev->magic != ARENA_FREE_MAGIC))
 944     {
 945         /* this often means that the prev arena got overwritten
 946          * by a memory write before that prev arena */
 947         ERR("Heap %p: prev arena %p invalid for %p\n",
 948             subheap->heap, prev, pArena );
 949         return FALSE;
 950     }
 951     /* Check that next block has PREV_FREE flag */
 952     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
 953     {
 954         if (!(*(DWORD *)((char *)(pArena + 1) +
 955             (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
 956         {
 957             ERR("Heap %p: free arena %p next block has no PREV_FREE flag\n",
 958                 subheap->heap, pArena );
 959             return FALSE;
 960         }
 961         /* Check next block back pointer */
 962         if (*((ARENA_FREE **)((char *)(pArena + 1) +
 963             (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
 964         {
 965             ERR("Heap %p: arena %p has wrong back ptr %p\n",
 966                 subheap->heap, pArena,
 967                 *((ARENA_FREE **)((char *)(pArena+1) + (pArena->size & ARENA_SIZE_MASK)) - 1));
 968             return FALSE;
 969         }
 970     }
 971     return TRUE;
 972 }
 973
 974 /***********************************************************************
 975  *           HEAP_ValidateInUseArena
 976  */
 977 static BOOL HEAP_ValidateInUseArena( const SUBHEAP *subheap, const ARENA_INUSE *pArena, BOOL quiet )
 978 {
 979     const char *heapEnd = (const char *)subheap + subheap->size;
 980
 981     /* Check for unaligned pointers */
 982     if ( (ULONG_PTR)pArena % ALIGNMENT != ARENA_OFFSET )
 983     {
 984         if ( quiet == NOISY )
 985         {
 986             ERR( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
 987             if ( TRACE_ON(heap) )
 988                 HEAP_Dump( subheap->heap );
 989         }
 990         else if ( WARN_ON(heap) )
 991         {
 992             WARN( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
 993             if ( TRACE_ON(heap) )
 994                 HEAP_Dump( subheap->heap );
 995         }
 996         return FALSE;
 997     }
 998
 999     /* Check magic number */
1000     if (pArena->magic != ARENA_INUSE_MAGIC)
1001     {
1002         if (quiet == NOISY) {
1003             ERR("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
1004             if (TRACE_ON(heap))
1005                HEAP_Dump( subheap->heap );
1006         }  else if (WARN_ON(heap)) {
1007             WARN("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
1008             if (TRACE_ON(heap))
1009                HEAP_Dump( subheap->heap );
1010         }
1011         return FALSE;
1012     }
1013     /* Check size flags */
1014     if (pArena->size & ARENA_FLAG_FREE)
1015     {
1016         ERR("Heap %p: bad flags %08lx for in-use arena %p\n",
1017             subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
1018         return FALSE;
1019     }
1020     /* Check arena size */
1021     if ((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
1022     {
1023         ERR("Heap %p: bad size %08lx for in-use arena %p\n",
1024             subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
1025         return FALSE;
1026     }
1027     /* Check next arena PREV_FREE flag */
1028     if (((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
1029         (*(const DWORD *)((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
1030     {
1031         ERR("Heap %p: in-use arena %p next block has PREV_FREE flag\n",
1032             subheap->heap, pArena );
1033         return FALSE;
1034     }
1035     /* Check prev free arena */
1036     if (pArena->size & ARENA_FLAG_PREV_FREE)
1037     {
1038         const ARENA_FREE *pPrev = *((const ARENA_FREE * const*)pArena - 1);
1039         /* Check prev pointer */
1040         if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
1041         {
1042             ERR("Heap %p: bad back ptr %p for arena %p\n",
1043                 subheap->heap, pPrev, pArena );
1044             return FALSE;
1045         }
1046         /* Check that prev arena is free */
1047         if (!(pPrev->size & ARENA_FLAG_FREE) ||
1048             (pPrev->magic != ARENA_FREE_MAGIC))
1049         {
1050             ERR("Heap %p: prev arena %p invalid for in-use %p\n",
1051                 subheap->heap, pPrev, pArena );
1052             return FALSE;
1053         }
1054         /* Check that prev arena is really the previous block */
1055         if ((const char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (const char *)pArena)
1056         {
1057             ERR("Heap %p: prev arena %p is not prev for in-use %p\n",
1058                 subheap->heap, pPrev, pArena );
1059             return FALSE;
1060         }
1061     }
1062     return TRUE;
1063 }
1064
1065 /***********************************************************************
1066  *           HEAP_IsRealArena  [Internal]
1067  * Validates a block is a valid arena.
1068  *
1069  * RETURNS
1070  *      TRUE: Success
1071  *      FALSE: Failure
1072  */
1073 static BOOL HEAP_IsRealArena( HEAP *heapPtr,   /* [in] ptr to the heap */
1074               DWORD flags,   /* [in] Bit flags that control access during operation */
1075               LPCVOID block, /* [in] Optional pointer to memory block to validate */
1076               BOOL quiet )   /* [in] Flag - if true, HEAP_ValidateInUseArena
1077                               *             does not complain    */
1078 {
1079     SUBHEAP *subheap;
1080     BOOL ret = TRUE;
1081
1082     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
1083     {
1084         ERR("Invalid heap %p!\n", heapPtr );
1085         return FALSE;
1086     }
1087
1088     flags &= HEAP_NO_SERIALIZE;
1089     flags |= heapPtr->flags;
1090     /* calling HeapLock may result in infinite recursion, so do the critsect directly */
1091     if (!(flags & HEAP_NO_SERIALIZE))
1092         RtlEnterHeapLock( &heapPtr->critSection );
1093
1094     if (block)
1095     {
1096         /* Only check this single memory block */
1097
1098         if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
1099             ((const char *)block < (char *)subheap + subheap->headerSize
1100                                    + sizeof(ARENA_INUSE)))
1101         {
1102             if (quiet == NOISY)
1103                 ERR("Heap %p: block %p is not inside heap\n", heapPtr, block );
1104             else if (WARN_ON(heap))
1105                 WARN("Heap %p: block %p is not inside heap\n", heapPtr, block );
1106             ret = FALSE;
1107         } else
1108             ret = HEAP_ValidateInUseArena( subheap, (const ARENA_INUSE *)block - 1, quiet );
1109
1110         if (!(flags & HEAP_NO_SERIALIZE))
1111             RtlLeaveHeapLock( &heapPtr->critSection );
1112         return ret;
1113     }
1114
1115     subheap = &heapPtr->subheap;
1116     while (subheap && ret)
1117     {
1118         char *ptr = (char *)subheap + subheap->headerSize;
1119         while (ptr < (char *)subheap + subheap->size)
1120         {
1121             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1122             {
1123                 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr )) {
1124                     ret = FALSE;
1125                     break;
1126                 }
1127                 ptr += sizeof(ARENA_FREE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1128             }
1129             else
1130             {
1131                 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY )) {
1132                     ret = FALSE;
1133                     break;
1134                 }
1135                 ptr += sizeof(ARENA_INUSE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1136             }
1137         }
1138         subheap = subheap->next;
1139     }
1140
1141     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1142     return ret;
1143 }
1144
1145
1146 /***********************************************************************
1147  *           HeapCreate   (KERNEL32.336)
1148  * RETURNS
1149  * Handle of heap: Success
1150  * NULL: Failure
1151  *
1152  * @implemented
1153  */
1154 HANDLE NTAPI
1155 RtlCreateHeap(ULONG flags,
1156               PVOID addr,
1157               SIZE_T totalSize,
1158               SIZE_T commitSize,
1159               PVOID Lock,
1160               PRTL_HEAP_PARAMETERS Parameters)
1161 {
1162    SUBHEAP *subheap;
1163
1164    /* Allocate the heap block */
1165
1166     if (!totalSize)
1167     {
1168         totalSize = HEAP_DEF_SIZE;
1169         flags |= HEAP_GROWABLE;
1170     }
1171     if (!(subheap = HEAP_CreateSubHeap( NULL, addr, flags, commitSize, totalSize, Parameters ))) return 0;
1172
1173    if (RtlpGetMode() == UserMode)
1174    {
1175         /* link it into the per-process heap list */
1176         if (processHeap)
1177         {
1178             HEAP *heapPtr = subheap->heap;
1179             RtlEnterHeapLock( &processHeap->critSection );
1180             list_add_head( &processHeap->entry, &heapPtr->entry );
1181             RtlLeaveHeapLock( &processHeap->critSection );
1182         }
1183         else
1184         {
1185             processHeap = subheap->heap;  /* assume the first heap we create is the process main heap */
1186             list_init( &processHeap->entry );
1187             assert( (ULONG_PTR)processHeap->freeList % ALIGNMENT == ARENA_OFFSET );
1188         }
1189    }
1190
1191    return (HANDLE)subheap;
1192 }
1193
1194 /***********************************************************************
1195  *           HeapDestroy   (KERNEL32.337)
1196  * RETURNS
1197  * TRUE: Success
1198  * FALSE: Failure
1199  *
1200  * @implemented
1201  *
1202  * RETURNS
1203  *  Success: A NULL HANDLE, if heap is NULL or it was destroyed
1204  *  Failure: The Heap handle, if heap is the process heap.
1205  */
1206 HANDLE NTAPI
1207 RtlDestroyHeap(HANDLE heap) /* [in] Handle of heap */
1208 {
1209    HEAP *heapPtr = HEAP_GetPtr( heap );
1210    SUBHEAP *subheap;
1211
1212    DPRINT("%p\n", heap );
1213    if (!heapPtr)
1214       return heap;
1215
1216    if (RtlpGetMode() == UserMode)
1217    {
1218       if (heap == NtCurrentPeb()->ProcessHeap)
1219          return heap; /* cannot delete the main process heap */
1220
1221       /* remove it from the per-process list */
1222       RtlEnterHeapLock( &processHeap->critSection );
1223       list_remove( &heapPtr->entry );
1224       RtlLeaveHeapLock( &processHeap->critSection );
1225    }
1226
1227     RtlDeleteHeapLock( &heapPtr->critSection );
1228     subheap = &heapPtr->subheap;
1229     while (subheap)
1230     {
1231         SUBHEAP *next = subheap->next;
1232         SIZE_T size = 0;
1233         void *addr = subheap;
1234         ZwFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE );
1235         subheap = next;
1236     }
1237    return (HANDLE)NULL;
1238 }
1239
1240
1241 /***********************************************************************
1242  *           HeapAlloc   (KERNEL32.334)
1243  * RETURNS
1244  * Pointer to allocated memory block
1245  * NULL: Failure
1246  * 0x7d030f60--invalid flags in RtlHeapAllocate
1247  * @implemented
1248  */
1249 PVOID NTAPI
1250 RtlAllocateHeap(HANDLE heap,   /* [in] Handle of private heap block */
1251                 ULONG flags,   /* [in] Heap allocation control flags */
1252                 ULONG size)    /* [in] Number of bytes to allocate */
1253 {
1254    ARENA_FREE *pArena;
1255    ARENA_INUSE *pInUse;
1256    SUBHEAP *subheap;
1257    HEAP *heapPtr = HEAP_GetPtr( heap );
1258    SIZE_T rounded_size;
1259
1260    /* Validate the parameters */
1261
1262    if (!heapPtr)
1263    {
1264       if (flags & HEAP_GENERATE_EXCEPTIONS)
1265          RtlRaiseStatus( STATUS_NO_MEMORY );
1266       return NULL;
1267    }
1268    //flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1269     flags |= heapPtr->flags;
1270     rounded_size = ROUND_SIZE(size);
1271     if (rounded_size < size)  /* overflow */
1272     {
1273         if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1274         return NULL;
1275     }
1276
1277     if (rounded_size < HEAP_MIN_DATA_SIZE) rounded_size = HEAP_MIN_DATA_SIZE;
1278
1279     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterHeapLock( &heapPtr->critSection );
1280     /* Locate a suitable free block */
1281     if (!(pArena = HEAP_FindFreeBlock( heapPtr, rounded_size, &subheap )))
1282     {
1283         TRACE("(%p,%08lx,%08lx): returning NULL\n",
1284                   heap, flags, size  );
1285         if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1286         if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1287         return NULL;
1288     }
1289
1290    /* Remove the arena from the free list */
1291
1292     list_remove( &pArena->entry );
1293
1294     /* Build the in-use arena */
1295
1296     pInUse = (ARENA_INUSE *)pArena;
1297
1298     /* in-use arena is smaller than free arena,
1299      * so we have to add the difference to the size */
1300     pInUse->size  = (pInUse->size & ~ARENA_FLAG_FREE) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1301     pInUse->magic = ARENA_INUSE_MAGIC;
1302     pInUse->has_user_data = 0;
1303
1304     /* Shrink the block */
1305
1306     HEAP_ShrinkBlock( subheap, pInUse, rounded_size );
1307     pInUse->unused_bytes = (pInUse->size & ARENA_SIZE_MASK) - size;
1308
1309     if (flags & HEAP_ZERO_MEMORY)
1310     {
1311         clear_block( pInUse + 1, size );
1312         mark_block_uninitialized( (char *)(pInUse + 1) + size, pInUse->unused_bytes );
1313     }
1314     else
1315         mark_block_uninitialized( pInUse + 1, pInUse->size & ARENA_SIZE_MASK );
1316
1317     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1318
1319     TRACE("(%p,%08lx,%08lx): returning %p\n", heap, flags, size, pInUse + 1 );
1320     return (LPVOID)(pInUse + 1);
1321 }
1322
1323
1324 /***********************************************************************
1325  *           HeapFree   (KERNEL32.338)
1326  * RETURNS
1327  * TRUE: Success
1328  * FALSE: Failure
1329  *
1330  * @implemented
1331  */
1332 BOOLEAN NTAPI RtlFreeHeap(
1333    HANDLE heap, /* [in] Handle of heap */
1334    ULONG flags,   /* [in] Heap freeing flags */
1335    PVOID ptr     /* [in] Address of memory to free */
1336 )
1337 {
1338     ARENA_INUSE *pInUse;
1339     SUBHEAP *subheap;
1340     HEAP *heapPtr;
1341
1342     /* Validate the parameters */
1343
1344     if (!ptr) return TRUE;  /* freeing a NULL ptr isn't an error in Win2k */
1345
1346     heapPtr = HEAP_GetPtr( heap );
1347     if (!heapPtr)
1348     {
1349         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1350         return FALSE;
1351     }
1352
1353     flags &= HEAP_NO_SERIALIZE;
1354     flags |= heapPtr->flags;
1355     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterHeapLock( &heapPtr->critSection );
1356     if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1357     {
1358         if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1359         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1360         TRACE("(%p,%08lx,%p): returning FALSE\n", heap, flags, ptr );
1361         return FALSE;
1362     }
1363
1364     /* Some sanity checks */
1365     pInUse  = (ARENA_INUSE *)ptr - 1;
1366     subheap = HEAP_FindSubHeap( heapPtr, pInUse );
1367     if ((char *)pInUse < (char *)subheap + subheap->headerSize) goto error;
1368     if (!HEAP_ValidateInUseArena( subheap, pInUse, QUIET )) goto error;
1369
1370     /* Turn the block into a free block */
1371
1372     HEAP_MakeInUseBlockFree( subheap, pInUse );
1373
1374     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1375
1376     TRACE("(%p,%08lx,%p): returning TRUE\n", heap, flags, ptr );
1377     return TRUE;
1378
1379 error:
1380     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1381     RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1382     TRACE("(%p,%08x,%p): returning FALSE\n", heap, flags, ptr );
1383     return FALSE;
1384 }
1385
1386
1387 /***********************************************************************
1388  *           RtlReAllocateHeap
1389  * PARAMS
1390  *   Heap   [in] Handle of heap block
1391  *   Flags    [in] Heap reallocation flags
1392  *   Ptr,    [in] Address of memory to reallocate
1393  *   Size     [in] Number of bytes to reallocate
1394  *
1395  * RETURNS
1396  * Pointer to reallocated memory block
1397  * NULL: Failure
1398  * 0x7d030f60--invalid flags in RtlHeapAllocate
1399  * @implemented
1400  */
1401 PVOID NTAPI RtlReAllocateHeap(
1402    HANDLE heap,
1403    ULONG flags,
1404    PVOID ptr,
1405    SIZE_T size
1406 )
1407 {
1408     ARENA_INUSE *pArena;
1409     HEAP *heapPtr;
1410     SUBHEAP *subheap;
1411     SIZE_T oldBlockSize, oldActualSize, rounded_size;
1412
1413     if (!ptr) return NULL;
1414     if (!(heapPtr = HEAP_GetPtr( heap )))
1415     {
1416         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1417         return NULL;
1418     }
1419
1420    /* Validate the parameters */
1421
1422    //Flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY |
1423    //         HEAP_REALLOC_IN_PLACE_ONLY;
1424     flags |= heapPtr->flags;
1425     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterHeapLock( &heapPtr->critSection );
1426
1427     rounded_size = ROUND_SIZE(size);
1428     if (rounded_size < size) goto oom;  /* overflow */
1429     if (rounded_size < HEAP_MIN_DATA_SIZE) rounded_size = HEAP_MIN_DATA_SIZE;
1430
1431     pArena = (ARENA_INUSE *)ptr - 1;
1432     if(!(subheap = HEAP_FindSubHeap( heapPtr, pArena ))) goto done;
1433     if ((char *)pArena < (char *)subheap + subheap->headerSize) goto error;
1434     if (!HEAP_ValidateInUseArena( subheap, pArena, QUIET )) goto error;
1435
1436     oldBlockSize = (pArena->size & ARENA_SIZE_MASK);
1437     oldActualSize = (pArena->size & ARENA_SIZE_MASK) - pArena->unused_bytes;
1438
1439     if (rounded_size > oldBlockSize)
1440     {
1441         char *pNext = (char *)(pArena + 1) + oldBlockSize;
1442         if ((pNext < (char *)subheap + subheap->size) &&
1443             (*(DWORD *)pNext & ARENA_FLAG_FREE) &&
1444             (oldBlockSize + (*(DWORD *)pNext & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) >= rounded_size))
1445         {
1446             ARENA_FREE *pFree = (ARENA_FREE *)pNext;
1447             list_remove( &pFree->entry );
1448             pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
1449
1450             if (!HEAP_Commit( subheap, pArena, rounded_size )) goto oom;
1451
1452             HEAP_ShrinkBlock( subheap, pArena, rounded_size );
1453             mark_block_initialized( pArena + 1, oldActualSize );
1454         }
1455         else  /* Do it the hard way */
1456         {
1457             ARENA_FREE *pNew;
1458             ARENA_INUSE *pInUse;
1459             SUBHEAP *newsubheap;
1460             if ((flags & HEAP_REALLOC_IN_PLACE_ONLY) ||
1461                 !(pNew = HEAP_FindFreeBlock( heapPtr, rounded_size, &newsubheap )))
1462                 goto oom;
1463
1464             /* Build the in-use arena */
1465
1466             list_remove( &pNew->entry );
1467             pInUse = (ARENA_INUSE *)pNew;
1468             pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
1469                            + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1470             pInUse->magic = ARENA_INUSE_MAGIC;
1471             HEAP_ShrinkBlock( newsubheap, pInUse, rounded_size );
1472
1473             mark_block_initialized( pInUse + 1, oldActualSize );
1474             memcpy( pInUse + 1, pArena + 1, oldActualSize );
1475
1476             /* Free the previous block */
1477
1478             HEAP_MakeInUseBlockFree( subheap, pArena );
1479             subheap = newsubheap;
1480             pArena  = pInUse;
1481         }
1482     }
1483     else
1484     {
1485         HEAP_ShrinkBlock( subheap, pArena, rounded_size );  /* Shrink the block */
1486         mark_block_initialized( pArena + 1, size );
1487     }
1488
1489     pArena->unused_bytes = (pArena->size & ARENA_SIZE_MASK) - size;
1490
1491     /* Clear the extra bytes if needed */
1492
1493     if (size > oldActualSize)
1494     {
1495         if (flags & HEAP_ZERO_MEMORY)
1496         {
1497             clear_block( (char *)(pArena + 1) + oldActualSize, size - oldActualSize );
1498             mark_block_uninitialized( (char *)(pArena + 1) + size,
1499                                       (pArena->size & ARENA_SIZE_MASK) - oldActualSize );
1500         }
1501         else
1502             mark_block_uninitialized( (char *)(pArena + 1) + oldActualSize,
1503                                       (pArena->size & ARENA_SIZE_MASK) - oldActualSize );
1504     }
1505
1506     /* Return the new arena */
1507 done:
1508     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1509     TRACE("(%p,%08lx,%p,%08lx): returning %p\n", heap, flags, ptr, size, pArena + 1 );
1510     return (LPVOID)(pArena + 1);
1511
1512 oom:
1513      if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1514      if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1515      RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_NO_MEMORY );
1516      TRACE("(%p,%08x,%p,%08lx): returning oom\n", heap, flags, ptr, size );
1517      return NULL;
1518
1519 error:
1520     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1521     RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1522     TRACE("(%p,%08x,%p,%08lx): returning error\n", heap, flags, ptr, size );
1523     return NULL;
1524 }
1525
1526
1527 /***********************************************************************
1528  *           RtlCompactHeap
1529  *
1530  * @unimplemented
1531  */
1532 ULONG NTAPI
1533 RtlCompactHeap(HANDLE Heap,
1534                 ULONG Flags)
1535 {
1536    UNIMPLEMENTED;
1537    return 0;
1538 }
1539
1540
1541 /***********************************************************************
1542  *           RtlLockHeap
1543  * Attempts to acquire the critical section object for a specified heap.
1544  *
1545  * PARAMS
1546  *   Heap  [in] Handle of heap to lock for exclusive access
1547  *
1548  * RETURNS
1549  * TRUE: Success
1550  * FALSE: Failure
1551  *
1552  * @implemented
1553  */
1554 BOOLEAN NTAPI
1555 RtlLockHeap(IN HANDLE Heap)
1556 {
1557    HEAP *heapPtr = HEAP_GetPtr( Heap );
1558    if (!heapPtr)
1559       return FALSE;
1560    RtlEnterHeapLock( &heapPtr->critSection );
1561    return TRUE;
1562 }
1563
1564
1565 /***********************************************************************
1566  *           RtlUnlockHeap
1567  * Releases ownership of the critical section object.
1568  *
1569  * PARAMS
1570  *   Heap  [in] Handle to the heap to unlock
1571  *
1572  * RETURNS
1573  * TRUE: Success
1574  * FALSE: Failure
1575  *
1576  * @implemented
1577  */
1578 BOOLEAN NTAPI
1579 RtlUnlockHeap(HANDLE Heap)
1580 {
1581    HEAP *heapPtr = HEAP_GetPtr( Heap );
1582    if (!heapPtr)
1583       return FALSE;
1584    RtlLeaveHeapLock( &heapPtr->critSection );
1585    return TRUE;
1586 }
1587
1588
1589 /***********************************************************************
1590  *           RtlSizeHeap
1591  * PARAMS
1592  *   Heap  [in] Handle of heap
1593  *   Flags   [in] Heap size control flags
1594  *   Ptr     [in] Address of memory to return size for
1595  *
1596  * RETURNS
1597  * Size in bytes of allocated memory
1598  * 0xffffffff: Failure
1599  *
1600  * @implemented
1601  */
1602 ULONG NTAPI
1603 RtlSizeHeap(
1604    HANDLE heap,
1605    ULONG flags,
1606    PVOID ptr
1607 )
1608 {
1609    SIZE_T ret;
1610     HEAP *heapPtr = HEAP_GetPtr( heap );
1611
1612     if (!heapPtr)
1613     {
1614         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1615         return ~0UL;
1616     }
1617     flags &= HEAP_NO_SERIALIZE;
1618     flags |= heapPtr->flags;
1619     if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterHeapLock( &heapPtr->critSection );
1620     if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1621     {
1622         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1623         ret = ~0UL;
1624     }
1625     else
1626     {
1627         const ARENA_INUSE *pArena = (const ARENA_INUSE *)ptr - 1;
1628         ret = (pArena->size & ARENA_SIZE_MASK) - pArena->unused_bytes;
1629     }
1630     if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveHeapLock( &heapPtr->critSection );
1631
1632     TRACE("(%p,%08lx,%p): returning %08lx\n", heap, flags, ptr, ret );
1633     return ret;
1634 }
1635
1636
1637 /***********************************************************************
1638  *           RtlValidateHeap
1639  * Validates a specified heap.
1640  *
1641  * PARAMS
1642  *   Heap  [in] Handle to the heap
1643  *   Flags   [in] Bit flags that control access during operation
1644  *   Block  [in] Optional pointer to memory block to validate
1645  *
1646  * NOTES
1647  * Flags is ignored.
1648  *
1649  * RETURNS
1650  * TRUE: Success
1651  * FALSE: Failure
1652  *
1653  * @implemented
1654  */
1655 BOOLEAN NTAPI RtlValidateHeap(
1656    HANDLE Heap,
1657    ULONG Flags,
1658    PVOID Block
1659 )
1660 {
1661    HEAP *heapPtr = HEAP_GetPtr( Heap );
1662    if (!heapPtr)
1663       return FALSE;
1664    return HEAP_IsRealArena( heapPtr, Flags, Block, QUIET );
1665 }
1666
1667 VOID
1668 RtlInitializeHeapManager(VOID)
1669 {
1670    PPEB Peb;
1671
1672    Peb = NtCurrentPeb();
1673
1674    Peb->NumberOfHeaps = 0;
1675    Peb->MaximumNumberOfHeaps = -1; /* no limit */
1676    Peb->ProcessHeaps = NULL;
1677
1678    //RtlInitializeHeapLock(&RtlpProcessHeapsListLock);
1679 }
1680
1681
1682 /*
1683  * @implemented
1684  */
1685 NTSTATUS NTAPI
1686 RtlEnumProcessHeaps(PHEAP_ENUMERATION_ROUTINE HeapEnumerationRoutine,
1687                     PVOID lParam)
1688 {
1689     NTSTATUS Status = STATUS_SUCCESS;
1690
1691     struct list *ptr=NULL;
1692     RtlEnterHeapLock(&processHeap->critSection);
1693     Status=HeapEnumerationRoutine(processHeap,lParam);
1694
1695     LIST_FOR_EACH( ptr, &processHeap->entry )
1696     {
1697         if (!NT_SUCCESS(Status)) break;
1698         Status = HeapEnumerationRoutine(ptr,lParam);
1699     }
1700
1701     RtlLeaveHeapLock(&processHeap->critSection);
1702
1703     return Status;
1704 }
1705
1706
1707 /*
1708  * @implemented
1709  */
1710 ULONG NTAPI
1711 RtlGetProcessHeaps(ULONG count,
1712                    HANDLE *heaps )
1713 {
1714     ULONG total = 1;  /* main heap */
1715     struct list *ptr;
1716     ULONG i=0;
1717     RtlEnterHeapLock( &processHeap->critSection );
1718     LIST_FOR_EACH( ptr, &processHeap->entry ) total++;
1719     //if (total <= count)
1720     {
1721         *(heaps++) = processHeap;
1722         i++;
1723         LIST_FOR_EACH( ptr, &processHeap->entry )
1724         {
1725             if (i >= count) break;
1726             i++;
1727             *(heaps++) = LIST_ENTRY( ptr, HEAP, entry );
1728         }
1729     }
1730     RtlLeaveHeapLock( &processHeap->critSection );
1731     return i;
1732 }
1733
1734
1735 /*
1736  * @implemented
1737  */
1738 BOOLEAN NTAPI
1739 RtlValidateProcessHeaps(VOID)
1740 {
1741    BOOLEAN Result = TRUE;
1742    HEAP ** pptr;
1743
1744    RtlEnterHeapLock( &processHeap->critSection );
1745
1746    for (pptr = (HEAP**)&NtCurrentPeb()->ProcessHeaps; *pptr; pptr++)
1747    {
1748       if (!RtlValidateHeap(*pptr, 0, NULL))
1749       {
1750          Result = FALSE;
1751          break;
1752       }
1753    }
1754
1755    RtlLeaveHeapLock( &processHeap->critSection );
1756    return Result;
1757 }
1758
1759
1760 /*
1761  * @unimplemented
1762  */
1763 BOOLEAN NTAPI
1764 RtlZeroHeap(
1765     IN PVOID HeapHandle,
1766     IN ULONG Flags
1767     )
1768 {
1769     UNIMPLEMENTED;
1770     return FALSE;
1771 }
1772
1773 /*
1774  * @implemented
1775  */
1776 BOOLEAN
1777 NTAPI
1778 RtlSetUserValueHeap(IN PVOID HeapHandle,
1779                     IN ULONG Flags,
1780                     IN PVOID BaseAddress,
1781                     IN PVOID UserValue)
1782 {
1783     HEAP *heapPtr;
1784     PHEAP_USER_DATA udata;
1785
1786     heapPtr = HEAP_GetPtr(HeapHandle);
1787     if (!heapPtr)
1788     {
1789         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1790         return FALSE;
1791     }
1792     udata = HEAP_GetUserData(heapPtr, BaseAddress);
1793     if (!udata)
1794     {
1795         udata = HEAP_AllocUserData(heapPtr, BaseAddress);
1796         if (!udata) return FALSE;
1797     }
1798     udata->UserValue = UserValue;
1799     return TRUE;
1800 }
1801
1802 /*
1803  * @implemented
1804  */
1805 BOOLEAN
1806 NTAPI
1807 RtlSetUserFlagsHeap(IN PVOID HeapHandle,
1808                     IN ULONG Flags,
1809                     IN PVOID BaseAddress,
1810                     IN ULONG UserFlags)
1811 {
1812     HEAP *heapPtr;
1813     PHEAP_USER_DATA udata;
1814
1815     heapPtr = HEAP_GetPtr(HeapHandle);
1816     if (!heapPtr)
1817     {
1818         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1819         return FALSE;
1820     }
1821     udata = HEAP_GetUserData(heapPtr, BaseAddress);
1822     if (!udata)
1823     {
1824         udata = HEAP_AllocUserData(heapPtr, BaseAddress);
1825         if (!udata) return FALSE;
1826     }
1827     udata->UserFlags = UserFlags & HEAP_SETTABLE_USER_FLAGS;
1828     return TRUE;
1829 }
1830
1831 /*
1832  * @implemented
1833  */
1834 BOOLEAN
1835 NTAPI
1836 RtlGetUserInfoHeap(IN PVOID HeapHandle,
1837                    IN ULONG Flags,
1838                    IN PVOID BaseAddress,
1839                    OUT PVOID *UserValue,
1840                    OUT PULONG UserFlags)
1841 {
1842     HEAP *heapPtr;
1843     PHEAP_USER_DATA udata;
1844
1845     heapPtr = HEAP_GetPtr(HeapHandle);
1846     if (!heapPtr)
1847     {
1848         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1849         return FALSE;
1850     }
1851     udata = HEAP_GetUserData(heapPtr, BaseAddress);
1852     if (!udata)
1853     {
1854         RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1855         return FALSE;
1856     }
1857     if (UserValue) *UserValue = udata->UserValue;
1858     if (UserFlags) *UserFlags = udata->UserFlags;
1859     return TRUE;
1860 }
1861
1862 /*
1863  * @unimplemented
1864  */
1865 NTSTATUS
1866 NTAPI
1867 RtlUsageHeap(IN HANDLE Heap,
1868              IN ULONG Flags,
1869              OUT PRTL_HEAP_USAGE Usage)
1870 {
1871     /* TODO */
1872     UNIMPLEMENTED;
1873     return STATUS_NOT_IMPLEMENTED;
1874 }
1875
1876 PWSTR
1877 NTAPI
1878 RtlQueryTagHeap(IN PVOID HeapHandle,
1879                 IN ULONG Flags,
1880                 IN USHORT TagIndex,
1881                 IN BOOLEAN ResetCounters,
1882                 OUT PRTL_HEAP_TAG_INFO HeapTagInfo)
1883 {
1884     /* TODO */
1885     UNIMPLEMENTED;
1886     return NULL;
1887 }
1888
1889 ULONG
1890 NTAPI
1891 RtlExtendHeap(IN HANDLE Heap,
1892               IN ULONG Flags,
1893               IN PVOID P,
1894               IN ULONG Size)
1895 {
1896     /* TODO */
1897     UNIMPLEMENTED;
1898     return 0;
1899 }
1900
1901 ULONG
1902 NTAPI
1903 RtlCreateTagHeap(IN HANDLE HeapHandle,
1904                  IN ULONG Flags,
1905                  IN PWSTR TagName,
1906                  IN PWSTR TagSubName)
1907 {
1908     /* TODO */
1909     UNIMPLEMENTED;
1910     return 0;
1911 }
1912
1913 NTSTATUS
1914 NTAPI
1915 RtlWalkHeap(IN HANDLE HeapHandle,
1916             IN PVOID HeapEntry)
1917 {
1918     UNIMPLEMENTED;
1919     return STATUS_NOT_IMPLEMENTED;
1920 }
1921
1922 PVOID
1923 NTAPI
1924 RtlProtectHeap(IN PVOID HeapHandle,
1925                IN BOOLEAN ReadOnly)
1926 {
1927     UNIMPLEMENTED;
1928     return NULL;
1929 }
1930
1931 DWORD
1932 NTAPI
1933 RtlSetHeapInformation(IN HANDLE HeapHandle OPTIONAL,
1934                       IN HEAP_INFORMATION_CLASS HeapInformationClass,
1935                       IN PVOID HeapInformation,
1936                       IN SIZE_T HeapInformationLength)
1937 {
1938     UNIMPLEMENTED;
1939     return 0;
1940 }
1941
1942 DWORD
1943 NTAPI
1944 RtlQueryHeapInformation(HANDLE HeapHandle,
1945                         HEAP_INFORMATION_CLASS HeapInformationClass,
1946                         PVOID HeapInformation OPTIONAL,
1947                         SIZE_T HeapInformationLength OPTIONAL,
1948                         PSIZE_T ReturnLength OPTIONAL)
1949 {
1950     UNIMPLEMENTED;
1951     return 0;
1952 }
1953
1954 DWORD
1955 NTAPI
1956 RtlMultipleAllocateHeap(IN PVOID HeapHandle,
1957                         IN DWORD Flags,
1958                         IN SIZE_T Size,
1959                         IN DWORD Count,
1960                         OUT PVOID *Array)
1961 {
1962     UNIMPLEMENTED;
1963     return 0;
1964 }
1965
1966 DWORD
1967 NTAPI
1968 RtlMultipleFreeHeap(IN PVOID HeapHandle,
1969                     IN DWORD Flags,
1970                     IN DWORD Count,
1971                     OUT PVOID *Array)
1972 {
1973     UNIMPLEMENTED;
1974     return 0;
1975 }