git.oblomov.eu Git - wine/blob - memory/heap.c

   1 /*
   2  * Win32 heap functions
   3  *
   4  * Copyright 1996 Alexandre Julliard
   5  * Copyright 1998 Ulrich Weigand
   6  */
   7
   8 #include <assert.h>
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include <string.h>
  12 #include "wine/winbase16.h"
  13 #include "wine/winestring.h"
  14 #include "selectors.h"
  15 #include "global.h"
  16 #include "winbase.h"
  17 #include "winerror.h"
  18 #include "winnt.h"
  19 #include "heap.h"
  20 #include "toolhelp.h"
  21 #include "debugtools.h"
  22
  23 DEFAULT_DEBUG_CHANNEL(heap);
  24
  25 /* Note: the heap data structures are based on what Pietrek describes in his
  26  * book 'Windows 95 System Programming Secrets'. The layout is not exactly
  27  * the same, but could be easily adapted if it turns out some programs
  28  * require it.
  29  */
  30
  31 typedef struct tagARENA_INUSE
  32 {
  33     DWORD  size;                    /* Block size; must be the first field */
  34     WORD   threadId;                /* Allocating thread id */
  35     WORD   magic;                   /* Magic number */
  36     void  *callerEIP;               /* EIP of caller upon allocation */
  37 } ARENA_INUSE;
  38
  39 typedef struct tagARENA_FREE
  40 {
  41     DWORD                 size;     /* Block size; must be the first field */
  42     WORD                  threadId; /* Freeing thread id */
  43     WORD                  magic;    /* Magic number */
  44     struct tagARENA_FREE *next;     /* Next free arena */
  45     struct tagARENA_FREE *prev;     /* Prev free arena */
  46 } ARENA_FREE;
  47
  48 #define ARENA_FLAG_FREE        0x00000001  /* flags OR'ed with arena size */
  49 #define ARENA_FLAG_PREV_FREE   0x00000002
  50 #define ARENA_SIZE_MASK        0xfffffffc
  51 #define ARENA_INUSE_MAGIC      0x4842      /* Value for arena 'magic' field */
  52 #define ARENA_FREE_MAGIC       0x4846      /* Value for arena 'magic' field */
  53
  54 #define ARENA_INUSE_FILLER     0x55
  55 #define ARENA_FREE_FILLER      0xaa
  56
  57 #define QUIET                  1           /* Suppress messages  */
  58 #define NOISY                  0           /* Report all errors  */
  59
  60 #define HEAP_NB_FREE_LISTS   4   /* Number of free lists */
  61
  62 /* Max size of the blocks on the free lists */
  63 static const DWORD HEAP_freeListSizes[HEAP_NB_FREE_LISTS] =
  64 {
  65     0x20, 0x80, 0x200, 0xffffffff
  66 };
  67
  68 typedef struct
  69 {
  70     DWORD       size;
  71     ARENA_FREE  arena;
  72 } FREE_LIST_ENTRY;
  73
  74 struct tagHEAP;
  75
  76 typedef struct tagSUBHEAP
  77 {
  78     DWORD               size;       /* Size of the whole sub-heap */
  79     DWORD               commitSize; /* Committed size of the sub-heap */
  80     DWORD               headerSize; /* Size of the heap header */
  81     struct tagSUBHEAP  *next;       /* Next sub-heap */
  82     struct tagHEAP     *heap;       /* Main heap structure */
  83     DWORD               magic;      /* Magic number */
  84     WORD                selector;   /* Selector for HEAP_WINE_SEGPTR heaps */
  85 } SUBHEAP;
  86
  87 #define SUBHEAP_MAGIC    ((DWORD)('S' | ('U'<<8) | ('B'<<16) | ('H'<<24)))
  88
  89 typedef struct tagHEAP
  90 {
  91     SUBHEAP          subheap;       /* First sub-heap */
  92     struct tagHEAP  *next;          /* Next heap for this process */
  93     FREE_LIST_ENTRY  freeList[HEAP_NB_FREE_LISTS];  /* Free lists */
  94     CRITICAL_SECTION critSection;   /* Critical section for serialization */
  95     DWORD            flags;         /* Heap flags */
  96     DWORD            magic;         /* Magic number */
  97     void            *private;       /* Private pointer for the user of the heap */
  98 } HEAP;
  99
 100 #define HEAP_MAGIC       ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
 101
 102 #define HEAP_DEF_SIZE        0x110000   /* Default heap size = 1Mb + 64Kb */
 103 #define HEAP_MIN_BLOCK_SIZE  (8+sizeof(ARENA_FREE))  /* Min. heap block size */
 104 #define COMMIT_MASK          0xffff  /* bitmask for commit/decommit granularity */
 105
 106 HANDLE SystemHeap = 0;
 107 HANDLE SegptrHeap = 0;
 108
 109 SYSTEM_HEAP_DESCR *SystemHeapDescr = 0;
 110
 111 static HEAP *processHeap;  /* main process heap */
 112 static HEAP *firstHeap;    /* head of secondary heaps list */
 113
 114 /* address where we try to map the system heap */
 115 #define SYSTEM_HEAP_BASE  ((void*)0x65430000)
 116
 117 static BOOL HEAP_IsRealArena( HANDLE heap, DWORD flags, LPCVOID block, BOOL quiet );
 118
 119 #ifdef __GNUC__
 120 #define GET_EIP()    (__builtin_return_address(0))
 121 #define SET_EIP(ptr) ((ARENA_INUSE*)(ptr) - 1)->callerEIP = GET_EIP()
 122 #else
 123 #define GET_EIP()    0
 124 #define SET_EIP(ptr) /* nothing */
 125 #endif  /* __GNUC__ */
 126
 127 /***********************************************************************
 128  *           HEAP_Dump
 129  */
 130 void HEAP_Dump( HEAP *heap )
 131 {
 132     int i;
 133     SUBHEAP *subheap;
 134     char *ptr;
 135
 136     DPRINTF( "Heap: %08lx\n", (DWORD)heap );
 137     DPRINTF( "Next: %08lx  Sub-heaps: %08lx",
 138           (DWORD)heap->next, (DWORD)&heap->subheap );
 139     subheap = &heap->subheap;
 140     while (subheap->next)
 141     {
 142         DPRINTF( " -> %08lx", (DWORD)subheap->next );
 143         subheap = subheap->next;
 144     }
 145
 146     DPRINTF( "\nFree lists:\n Block   Stat   Size    Id\n" );
 147     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 148         DPRINTF( "%08lx free %08lx %04x prev=%08lx next=%08lx\n",
 149               (DWORD)&heap->freeList[i].arena, heap->freeList[i].arena.size,
 150               heap->freeList[i].arena.threadId,
 151               (DWORD)heap->freeList[i].arena.prev,
 152               (DWORD)heap->freeList[i].arena.next );
 153
 154     subheap = &heap->subheap;
 155     while (subheap)
 156     {
 157         DWORD freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
 158         DPRINTF( "\n\nSub-heap %08lx: size=%08lx committed=%08lx\n",
 159               (DWORD)subheap, subheap->size, subheap->commitSize );
 160
 161         DPRINTF( "\n Block   Stat   Size    Id\n" );
 162         ptr = (char*)subheap + subheap->headerSize;
 163         while (ptr < (char *)subheap + subheap->size)
 164         {
 165             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
 166             {
 167                 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
 168                 DPRINTF( "%08lx free %08lx %04x prev=%08lx next=%08lx\n",
 169                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 170                       pArena->threadId, (DWORD)pArena->prev,
 171                       (DWORD)pArena->next);
 172                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 173                 arenaSize += sizeof(ARENA_FREE);
 174                 freeSize += pArena->size & ARENA_SIZE_MASK;
 175             }
 176             else if (*(DWORD *)ptr & ARENA_FLAG_PREV_FREE)
 177             {
 178                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 179                 DPRINTF( "%08lx Used %08lx %04x back=%08lx EIP=%p\n",
 180                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 181                       pArena->threadId, *((DWORD *)pArena - 1),
 182                       pArena->callerEIP );
 183                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 184                 arenaSize += sizeof(ARENA_INUSE);
 185                 usedSize += pArena->size & ARENA_SIZE_MASK;
 186             }
 187             else
 188             {
 189                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 190                 DPRINTF( "%08lx used %08lx %04x EIP=%p\n",
 191                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 192                       pArena->threadId, pArena->callerEIP );
 193                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 194                 arenaSize += sizeof(ARENA_INUSE);
 195                 usedSize += pArena->size & ARENA_SIZE_MASK;
 196             }
 197         }
 198         DPRINTF( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
 199               subheap->size, subheap->commitSize, freeSize, usedSize,
 200               arenaSize, (arenaSize * 100) / subheap->size );
 201         subheap = subheap->next;
 202     }
 203 }
 204
 205
 206 /***********************************************************************
 207  *           HEAP_GetPtr
 208  * RETURNS
 209  *      Pointer to the heap
 210  *      NULL: Failure
 211  */
 212 static HEAP *HEAP_GetPtr(
 213              HANDLE heap /* [in] Handle to the heap */
 214 ) {
 215     HEAP *heapPtr = (HEAP *)heap;
 216     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
 217     {
 218         ERR("Invalid heap %08x!\n", heap );
 219         SetLastError( ERROR_INVALID_HANDLE );
 220         return NULL;
 221     }
 222     if (TRACE_ON(heap) && !HEAP_IsRealArena( heap, 0, NULL, NOISY ))
 223     {
 224         HEAP_Dump( heapPtr );
 225         assert( FALSE );
 226         SetLastError( ERROR_INVALID_HANDLE );
 227         return NULL;
 228     }
 229     return heapPtr;
 230 }
 231
 232
 233 /***********************************************************************
 234  *           HEAP_InsertFreeBlock
 235  *
 236  * Insert a free block into the free list.
 237  */
 238 static void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena )
 239 {
 240     FREE_LIST_ENTRY *pEntry = heap->freeList;
 241     while (pEntry->size < pArena->size) pEntry++;
 242     pArena->size      |= ARENA_FLAG_FREE;
 243     pArena->next       = pEntry->arena.next;
 244     pArena->next->prev = pArena;
 245     pArena->prev       = &pEntry->arena;
 246     pEntry->arena.next = pArena;
 247 }
 248
 249
 250 /***********************************************************************
 251  *           HEAP_FindSubHeap
 252  * Find the sub-heap containing a given address.
 253  *
 254  * RETURNS
 255  *      Pointer: Success
 256  *      NULL: Failure
 257  */
 258 static SUBHEAP *HEAP_FindSubHeap(
 259                 HEAP *heap, /* [in] Heap pointer */
 260                 LPCVOID ptr /* [in] Address */
 261 ) {
 262     SUBHEAP *sub = &heap->subheap;
 263     while (sub)
 264     {
 265         if (((char *)ptr >= (char *)sub) &&
 266             ((char *)ptr < (char *)sub + sub->size)) return sub;
 267         sub = sub->next;
 268     }
 269     return NULL;
 270 }
 271
 272
 273 /***********************************************************************
 274  *           HEAP_Commit
 275  *
 276  * Make sure the heap storage is committed up to (not including) ptr.
 277  */
 278 static inline BOOL HEAP_Commit( SUBHEAP *subheap, void *ptr )
 279 {
 280     DWORD size = (DWORD)((char *)ptr - (char *)subheap);
 281     size = (size + COMMIT_MASK) & ~COMMIT_MASK;
 282     if (size > subheap->size) size = subheap->size;
 283     if (size <= subheap->commitSize) return TRUE;
 284     if (!VirtualAlloc( (char *)subheap + subheap->commitSize,
 285                        size - subheap->commitSize, MEM_COMMIT,
 286                        PAGE_EXECUTE_READWRITE))
 287     {
 288         WARN("Could not commit %08lx bytes at %08lx for heap %08lx\n",
 289                  size - subheap->commitSize,
 290                  (DWORD)((char *)subheap + subheap->commitSize),
 291                  (DWORD)subheap->heap );
 292         return FALSE;
 293     }
 294     subheap->commitSize = size;
 295     return TRUE;
 296 }
 297
 298
 299 /***********************************************************************
 300  *           HEAP_Decommit
 301  *
 302  * If possible, decommit the heap storage from (including) 'ptr'.
 303  */
 304 static inline BOOL HEAP_Decommit( SUBHEAP *subheap, void *ptr )
 305 {
 306     DWORD size = (DWORD)((char *)ptr - (char *)subheap);
 307     /* round to next block and add one full block */
 308     size = ((size + COMMIT_MASK) & ~COMMIT_MASK) + COMMIT_MASK + 1;
 309     if (size >= subheap->commitSize) return TRUE;
 310     if (!VirtualFree( (char *)subheap + size,
 311                       subheap->commitSize - size, MEM_DECOMMIT ))
 312     {
 313         WARN("Could not decommit %08lx bytes at %08lx for heap %08lx\n",
 314                  subheap->commitSize - size,
 315                  (DWORD)((char *)subheap + size),
 316                  (DWORD)subheap->heap );
 317         return FALSE;
 318     }
 319     subheap->commitSize = size;
 320     return TRUE;
 321 }
 322
 323
 324 /***********************************************************************
 325  *           HEAP_CreateFreeBlock
 326  *
 327  * Create a free block at a specified address. 'size' is the size of the
 328  * whole block, including the new arena.
 329  */
 330 static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, DWORD size )
 331 {
 332     ARENA_FREE *pFree;
 333
 334     /* Create a free arena */
 335
 336     pFree = (ARENA_FREE *)ptr;
 337     pFree->threadId = GetCurrentTask();
 338     pFree->magic = ARENA_FREE_MAGIC;
 339
 340     /* If debugging, erase the freed block content */
 341
 342     if (TRACE_ON(heap))
 343     {
 344         char *pEnd = (char *)ptr + size;
 345         if (pEnd > (char *)subheap + subheap->commitSize)
 346             pEnd = (char *)subheap + subheap->commitSize;
 347         if (pEnd > (char *)(pFree + 1))
 348             memset( pFree + 1, ARENA_FREE_FILLER, pEnd - (char *)(pFree + 1) );
 349     }
 350
 351     /* Check if next block is free also */
 352
 353     if (((char *)ptr + size < (char *)subheap + subheap->size) &&
 354         (*(DWORD *)((char *)ptr + size) & ARENA_FLAG_FREE))
 355     {
 356         /* Remove the next arena from the free list */
 357         ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
 358         pNext->next->prev = pNext->prev;
 359         pNext->prev->next = pNext->next;
 360         size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
 361         if (TRACE_ON(heap))
 362             memset( pNext, ARENA_FREE_FILLER, sizeof(ARENA_FREE) );
 363     }
 364
 365     /* Set the next block PREV_FREE flag and pointer */
 366
 367     if ((char *)ptr + size < (char *)subheap + subheap->size)
 368     {
 369         DWORD *pNext = (DWORD *)((char *)ptr + size);
 370         *pNext |= ARENA_FLAG_PREV_FREE;
 371         *(ARENA_FREE **)(pNext - 1) = pFree;
 372     }
 373
 374     /* Last, insert the new block into the free list */
 375
 376     pFree->size = size - sizeof(*pFree);
 377     HEAP_InsertFreeBlock( subheap->heap, pFree );
 378 }
 379
 380
 381 /***********************************************************************
 382  *           HEAP_MakeInUseBlockFree
 383  *
 384  * Turn an in-use block into a free block. Can also decommit the end of
 385  * the heap, and possibly even free the sub-heap altogether.
 386  */
 387 static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
 388 {
 389     ARENA_FREE *pFree;
 390     DWORD size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
 391
 392     /* Check if we can merge with previous block */
 393
 394     if (pArena->size & ARENA_FLAG_PREV_FREE)
 395     {
 396         pFree = *((ARENA_FREE **)pArena - 1);
 397         size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
 398         /* Remove it from the free list */
 399         pFree->next->prev = pFree->prev;
 400         pFree->prev->next = pFree->next;
 401     }
 402     else pFree = (ARENA_FREE *)pArena;
 403
 404     /* Create a free block */
 405
 406     HEAP_CreateFreeBlock( subheap, pFree, size );
 407     size = (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
 408     if ((char *)pFree + size < (char *)subheap + subheap->size)
 409         return;  /* Not the last block, so nothing more to do */
 410
 411     /* Free the whole sub-heap if it's empty and not the original one */
 412
 413     if (((char *)pFree == (char *)subheap + subheap->headerSize) &&
 414         (subheap != &subheap->heap->subheap))
 415     {
 416         SUBHEAP *pPrev = &subheap->heap->subheap;
 417         /* Remove the free block from the list */
 418         pFree->next->prev = pFree->prev;
 419         pFree->prev->next = pFree->next;
 420         /* Remove the subheap from the list */
 421         while (pPrev && (pPrev->next != subheap)) pPrev = pPrev->next;
 422         if (pPrev) pPrev->next = subheap->next;
 423         /* Free the memory */
 424         subheap->magic = 0;
 425         if (subheap->selector) FreeSelector16( subheap->selector );
 426         VirtualFree( subheap, 0, MEM_RELEASE );
 427         return;
 428     }
 429
 430     /* Decommit the end of the heap */
 431
 432     if (!(subheap->heap->flags & HEAP_WINE_SHARED)) HEAP_Decommit( subheap, pFree + 1 );
 433 }
 434
 435
 436 /***********************************************************************
 437  *           HEAP_ShrinkBlock
 438  *
 439  * Shrink an in-use block.
 440  */
 441 static void HEAP_ShrinkBlock(SUBHEAP *subheap, ARENA_INUSE *pArena, DWORD size)
 442 {
 443     if ((pArena->size & ARENA_SIZE_MASK) >= size + HEAP_MIN_BLOCK_SIZE)
 444     {
 445         HEAP_CreateFreeBlock( subheap, (char *)(pArena + 1) + size,
 446                               (pArena->size & ARENA_SIZE_MASK) - size );
 447         pArena->size = (pArena->size & ~ARENA_SIZE_MASK) | size;
 448     }
 449     else
 450     {
 451         /* Turn off PREV_FREE flag in next block */
 452         char *pNext = (char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK);
 453         if (pNext < (char *)subheap + subheap->size)
 454             *(DWORD *)pNext &= ~ARENA_FLAG_PREV_FREE;
 455     }
 456 }
 457
 458 /***********************************************************************
 459  *           HEAP_InitSubHeap
 460  */
 461 static BOOL HEAP_InitSubHeap( HEAP *heap, LPVOID address, DWORD flags,
 462                                 DWORD commitSize, DWORD totalSize )
 463 {
 464     SUBHEAP *subheap = (SUBHEAP *)address;
 465     WORD selector = 0;
 466     FREE_LIST_ENTRY *pEntry;
 467     int i;
 468
 469     /* Commit memory */
 470
 471     if (flags & HEAP_WINE_SHARED)
 472         commitSize = totalSize;  /* always commit everything in a shared heap */
 473     if (!VirtualAlloc(address, commitSize, MEM_COMMIT, PAGE_EXECUTE_READWRITE))
 474     {
 475         WARN("Could not commit %08lx bytes for sub-heap %08lx\n",
 476                    commitSize, (DWORD)address );
 477         return FALSE;
 478     }
 479
 480     /* Allocate a selector if needed */
 481
 482     if (flags & HEAP_WINE_SEGPTR)
 483     {
 484         selector = SELECTOR_AllocBlock( address, totalSize,
 485                            (flags & (HEAP_WINE_CODESEG|HEAP_WINE_CODE16SEG))
 486                             ? SEGMENT_CODE : SEGMENT_DATA,
 487                            (flags & HEAP_WINE_CODESEG) != 0, FALSE );
 488         if (!selector)
 489         {
 490             ERR("Could not allocate selector\n" );
 491             return FALSE;
 492         }
 493     }
 494
 495     /* Fill the sub-heap structure */
 496
 497     subheap->heap       = heap;
 498     subheap->selector   = selector;
 499     subheap->size       = totalSize;
 500     subheap->commitSize = commitSize;
 501     subheap->magic      = SUBHEAP_MAGIC;
 502
 503     if ( subheap != (SUBHEAP *)heap )
 504     {
 505         /* If this is a secondary subheap, insert it into list */
 506
 507         subheap->headerSize = sizeof(SUBHEAP);
 508         subheap->next       = heap->subheap.next;
 509         heap->subheap.next  = subheap;
 510     }
 511     else
 512     {
 513         /* If this is a primary subheap, initialize main heap */
 514
 515         subheap->headerSize = sizeof(HEAP);
 516         subheap->next       = NULL;
 517         heap->next          = NULL;
 518         heap->flags         = flags;
 519         heap->magic         = HEAP_MAGIC;
 520
 521         /* Build the free lists */
 522
 523         for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
 524         {
 525             pEntry->size           = HEAP_freeListSizes[i];
 526             pEntry->arena.size     = 0 | ARENA_FLAG_FREE;
 527             pEntry->arena.next     = i < HEAP_NB_FREE_LISTS-1 ?
 528                          &heap->freeList[i+1].arena : &heap->freeList[0].arena;
 529             pEntry->arena.prev     = i ? &heap->freeList[i-1].arena :
 530                                    &heap->freeList[HEAP_NB_FREE_LISTS-1].arena;
 531             pEntry->arena.threadId = 0;
 532             pEntry->arena.magic    = ARENA_FREE_MAGIC;
 533         }
 534
 535         /* Initialize critical section */
 536
 537         InitializeCriticalSection( &heap->critSection );
 538         if (!SystemHeap) MakeCriticalSectionGlobal( &heap->critSection );
 539     }
 540
 541     /* Create the first free block */
 542
 543     HEAP_CreateFreeBlock( subheap, (LPBYTE)subheap + subheap->headerSize,
 544                           subheap->size - subheap->headerSize );
 545
 546     return TRUE;
 547 }
 548
 549 /***********************************************************************
 550  *           HEAP_CreateSubHeap
 551  *
 552  * Create a sub-heap of the given size.
 553  * If heap == NULL, creates a main heap.
 554  */
 555 static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, DWORD flags,
 556                                     DWORD commitSize, DWORD totalSize )
 557 {
 558     LPVOID address;
 559
 560     /* Round-up sizes on a 64K boundary */
 561
 562     if (flags & HEAP_WINE_SEGPTR)
 563     {
 564         totalSize = commitSize = 0x10000;  /* Only 64K at a time for SEGPTRs */
 565     }
 566     else
 567     {
 568         totalSize  = (totalSize + 0xffff) & 0xffff0000;
 569         commitSize = (commitSize + 0xffff) & 0xffff0000;
 570         if (!commitSize) commitSize = 0x10000;
 571         if (totalSize < commitSize) totalSize = commitSize;
 572     }
 573
 574     /* Allocate the memory block */
 575
 576     if (!(address = VirtualAlloc( NULL, totalSize,
 577                                   MEM_RESERVE, PAGE_EXECUTE_READWRITE )))
 578     {
 579         WARN("Could not VirtualAlloc %08lx bytes\n",
 580                  totalSize );
 581         return NULL;
 582     }
 583
 584     /* Initialize subheap */
 585
 586     if (!HEAP_InitSubHeap( heap? heap : (HEAP *)address,
 587                            address, flags, commitSize, totalSize ))
 588     {
 589         VirtualFree( address, 0, MEM_RELEASE );
 590         return NULL;
 591     }
 592
 593     return (SUBHEAP *)address;
 594 }
 595
 596
 597 /***********************************************************************
 598  *           HEAP_FindFreeBlock
 599  *
 600  * Find a free block at least as large as the requested size, and make sure
 601  * the requested size is committed.
 602  */
 603 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, DWORD size,
 604                                        SUBHEAP **ppSubHeap )
 605 {
 606     SUBHEAP *subheap;
 607     ARENA_FREE *pArena;
 608     FREE_LIST_ENTRY *pEntry = heap->freeList;
 609
 610     /* Find a suitable free list, and in it find a block large enough */
 611
 612     while (pEntry->size < size) pEntry++;
 613     pArena = pEntry->arena.next;
 614     while (pArena != &heap->freeList[0].arena)
 615     {
 616         if (pArena->size > size)
 617         {
 618             subheap = HEAP_FindSubHeap( heap, pArena );
 619             if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
 620                                                + size + HEAP_MIN_BLOCK_SIZE))
 621                 return NULL;
 622             *ppSubHeap = subheap;
 623             return pArena;
 624         }
 625
 626         pArena = pArena->next;
 627     }
 628
 629     /* If no block was found, attempt to grow the heap */
 630
 631     if (!(heap->flags & HEAP_GROWABLE))
 632     {
 633         WARN("Not enough space in heap %08lx for %08lx bytes\n",
 634                  (DWORD)heap, size );
 635         return NULL;
 636     }
 637     size += sizeof(SUBHEAP) + sizeof(ARENA_FREE);
 638     if (!(subheap = HEAP_CreateSubHeap( heap, heap->flags, size,
 639                                         max( HEAP_DEF_SIZE, size ) )))
 640         return NULL;
 641
 642     TRACE("created new sub-heap %08lx of %08lx bytes for heap %08lx\n",
 643                 (DWORD)subheap, size, (DWORD)heap );
 644
 645     *ppSubHeap = subheap;
 646     return (ARENA_FREE *)(subheap + 1);
 647 }
 648
 649
 650 /***********************************************************************
 651  *           HEAP_IsValidArenaPtr
 652  *
 653  * Check that the pointer is inside the range possible for arenas.
 654  */
 655 static BOOL HEAP_IsValidArenaPtr( HEAP *heap, void *ptr )
 656 {
 657     int i;
 658     SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
 659     if (!subheap) return FALSE;
 660     if ((char *)ptr >= (char *)subheap + subheap->headerSize) return TRUE;
 661     if (subheap != &heap->subheap) return FALSE;
 662     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 663         if (ptr == (void *)&heap->freeList[i].arena) return TRUE;
 664     return FALSE;
 665 }
 666
 667
 668 /***********************************************************************
 669  *           HEAP_ValidateFreeArena
 670  */
 671 static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
 672 {
 673     char *heapEnd = (char *)subheap + subheap->size;
 674
 675     /* Check magic number */
 676     if (pArena->magic != ARENA_FREE_MAGIC)
 677     {
 678         ERR("Heap %08lx: invalid free arena magic for %08lx\n",
 679                  (DWORD)subheap->heap, (DWORD)pArena );
 680         return FALSE;
 681     }
 682     /* Check size flags */
 683     if (!(pArena->size & ARENA_FLAG_FREE) ||
 684         (pArena->size & ARENA_FLAG_PREV_FREE))
 685     {
 686         ERR("Heap %08lx: bad flags %lx for free arena %08lx\n",
 687                  (DWORD)subheap->heap, pArena->size & ~ARENA_SIZE_MASK, (DWORD)pArena );
 688     }
 689     /* Check arena size */
 690     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
 691     {
 692         ERR("Heap %08lx: bad size %08lx for free arena %08lx\n",
 693                  (DWORD)subheap->heap, (DWORD)pArena->size & ARENA_SIZE_MASK, (DWORD)pArena );
 694         return FALSE;
 695     }
 696     /* Check that next pointer is valid */
 697     if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->next ))
 698     {
 699         ERR("Heap %08lx: bad next ptr %08lx for arena %08lx\n",
 700                  (DWORD)subheap->heap, (DWORD)pArena->next, (DWORD)pArena );
 701         return FALSE;
 702     }
 703     /* Check that next arena is free */
 704     if (!(pArena->next->size & ARENA_FLAG_FREE) ||
 705         (pArena->next->magic != ARENA_FREE_MAGIC))
 706     {
 707         ERR("Heap %08lx: next arena %08lx invalid for %08lx\n",
 708                  (DWORD)subheap->heap, (DWORD)pArena->next, (DWORD)pArena );
 709         return FALSE;
 710     }
 711     /* Check that prev pointer is valid */
 712     if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->prev ))
 713     {
 714         ERR("Heap %08lx: bad prev ptr %08lx for arena %08lx\n",
 715                  (DWORD)subheap->heap, (DWORD)pArena->prev, (DWORD)pArena );
 716         return FALSE;
 717     }
 718     /* Check that prev arena is free */
 719     if (!(pArena->prev->size & ARENA_FLAG_FREE) ||
 720         (pArena->prev->magic != ARENA_FREE_MAGIC))
 721     {
 722         ERR("Heap %08lx: prev arena %08lx invalid for %08lx\n",
 723                  (DWORD)subheap->heap, (DWORD)pArena->prev, (DWORD)pArena );
 724         return FALSE;
 725     }
 726     /* Check that next block has PREV_FREE flag */
 727     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
 728     {
 729         if (!(*(DWORD *)((char *)(pArena + 1) +
 730             (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
 731         {
 732             ERR("Heap %08lx: free arena %08lx next block has no PREV_FREE flag\n",
 733                      (DWORD)subheap->heap, (DWORD)pArena );
 734             return FALSE;
 735         }
 736         /* Check next block back pointer */
 737         if (*((ARENA_FREE **)((char *)(pArena + 1) +
 738             (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
 739         {
 740             ERR("Heap %08lx: arena %08lx has wrong back ptr %08lx\n",
 741                      (DWORD)subheap->heap, (DWORD)pArena,
 742                      *((DWORD *)((char *)(pArena+1)+ (pArena->size & ARENA_SIZE_MASK)) - 1));
 743             return FALSE;
 744         }
 745     }
 746     return TRUE;
 747 }
 748
 749
 750 /***********************************************************************
 751  *           HEAP_ValidateInUseArena
 752  */
 753 static BOOL HEAP_ValidateInUseArena( SUBHEAP *subheap, ARENA_INUSE *pArena, BOOL quiet )
 754 {
 755     char *heapEnd = (char *)subheap + subheap->size;
 756
 757     /* Check magic number */
 758     if (pArena->magic != ARENA_INUSE_MAGIC)
 759     {
 760         if (quiet == NOISY) {
 761         ERR("Heap %08lx: invalid in-use arena magic for %08lx\n",
 762                  (DWORD)subheap->heap, (DWORD)pArena );
 763             if (TRACE_ON(heap))
 764                HEAP_Dump( subheap->heap );
 765         }  else if (WARN_ON(heap)) {
 766             WARN("Heap %08lx: invalid in-use arena magic for %08lx\n",
 767                  (DWORD)subheap->heap, (DWORD)pArena );
 768             if (TRACE_ON(heap))
 769                HEAP_Dump( subheap->heap );
 770         }
 771         return FALSE;
 772     }
 773     /* Check size flags */
 774     if (pArena->size & ARENA_FLAG_FREE)
 775     {
 776         ERR("Heap %08lx: bad flags %lx for in-use arena %08lx\n",
 777                  (DWORD)subheap->heap, pArena->size & ~ARENA_SIZE_MASK, (DWORD)pArena );
 778     }
 779     /* Check arena size */
 780     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
 781     {
 782         ERR("Heap %08lx: bad size %08lx for in-use arena %08lx\n",
 783                  (DWORD)subheap->heap, (DWORD)pArena->size & ARENA_SIZE_MASK, (DWORD)pArena );
 784         return FALSE;
 785     }
 786     /* Check next arena PREV_FREE flag */
 787     if (((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
 788         (*(DWORD *)((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
 789     {
 790         ERR("Heap %08lx: in-use arena %08lx next block has PREV_FREE flag\n",
 791                  (DWORD)subheap->heap, (DWORD)pArena );
 792         return FALSE;
 793     }
 794     /* Check prev free arena */
 795     if (pArena->size & ARENA_FLAG_PREV_FREE)
 796     {
 797         ARENA_FREE *pPrev = *((ARENA_FREE **)pArena - 1);
 798         /* Check prev pointer */
 799         if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
 800         {
 801             ERR("Heap %08lx: bad back ptr %08lx for arena %08lx\n",
 802                     (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 803             return FALSE;
 804         }
 805         /* Check that prev arena is free */
 806         if (!(pPrev->size & ARENA_FLAG_FREE) ||
 807             (pPrev->magic != ARENA_FREE_MAGIC))
 808         {
 809             ERR("Heap %08lx: prev arena %08lx invalid for in-use %08lx\n",
 810                      (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 811             return FALSE;
 812         }
 813         /* Check that prev arena is really the previous block */
 814         if ((char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (char *)pArena)
 815         {
 816             ERR("Heap %08lx: prev arena %08lx is not prev for in-use %08lx\n",
 817                      (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 818             return FALSE;
 819         }
 820     }
 821     return TRUE;
 822 }
 823
 824
 825 /***********************************************************************
 826  *           HEAP_IsInsideHeap
 827  * Checks whether the pointer points to a block inside a given heap.
 828  *
 829  * NOTES
 830  *      Should this return BOOL32?
 831  *
 832  * RETURNS
 833  *      !0: Success
 834  *      0: Failure
 835  */
 836 int HEAP_IsInsideHeap(
 837     HANDLE heap, /* [in] Heap */
 838     DWORD flags,   /* [in] Flags */
 839     LPCVOID ptr    /* [in] Pointer */
 840 ) {
 841     HEAP *heapPtr = HEAP_GetPtr( heap );
 842     SUBHEAP *subheap;
 843     int ret;
 844
 845     /* Validate the parameters */
 846
 847     if (!heapPtr) return 0;
 848     flags |= heapPtr->flags;
 849     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
 850     ret = (((subheap = HEAP_FindSubHeap( heapPtr, ptr )) != NULL) &&
 851            (((char *)ptr >= (char *)subheap + subheap->headerSize
 852                               + sizeof(ARENA_INUSE))));
 853     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
 854     return ret;
 855 }
 856
 857
 858 /***********************************************************************
 859  *           HEAP_GetSegptr
 860  *
 861  * Transform a linear pointer into a SEGPTR. The pointer must have been
 862  * allocated from a HEAP_WINE_SEGPTR heap.
 863  */
 864 SEGPTR HEAP_GetSegptr( HANDLE heap, DWORD flags, LPCVOID ptr )
 865 {
 866     HEAP *heapPtr = HEAP_GetPtr( heap );
 867     SUBHEAP *subheap;
 868     SEGPTR ret;
 869
 870     /* Validate the parameters */
 871
 872     if (!heapPtr) return 0;
 873     flags |= heapPtr->flags;
 874     if (!(flags & HEAP_WINE_SEGPTR))
 875     {
 876         ERR("Heap %08x is not a SEGPTR heap\n",
 877                  heap );
 878         return 0;
 879     }
 880     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
 881
 882     /* Get the subheap */
 883
 884     if (!(subheap = HEAP_FindSubHeap( heapPtr, ptr )))
 885     {
 886         ERR("%p is not inside heap %08x\n",
 887                  ptr, heap );
 888         if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
 889         return 0;
 890     }
 891
 892     /* Build the SEGPTR */
 893
 894     ret = PTR_SEG_OFF_TO_SEGPTR(subheap->selector, (DWORD)ptr-(DWORD)subheap);
 895     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
 896     return ret;
 897 }
 898
 899 /***********************************************************************
 900  *           HEAP_IsRealArena  [Internal]
 901  * Validates a block is a valid arena.
 902  *
 903  * RETURNS
 904  *      TRUE: Success
 905  *      FALSE: Failure
 906  */
 907 static BOOL HEAP_IsRealArena(
 908               HANDLE heap,   /* [in] Handle to the heap */
 909               DWORD flags,   /* [in] Bit flags that control access during operation */
 910               LPCVOID block, /* [in] Optional pointer to memory block to validate */
 911               BOOL quiet     /* [in] Flag - if true, HEAP_ValidateInUseArena
 912                               *             does not complain    */
 913 ) {
 914     SUBHEAP *subheap;
 915     HEAP *heapPtr = (HEAP *)(heap);
 916     BOOL ret = TRUE;
 917
 918     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
 919     {
 920         ERR("Invalid heap %08x!\n", heap );
 921         return FALSE;
 922     }
 923
 924     flags &= HEAP_NO_SERIALIZE;
 925     flags |= heapPtr->flags;
 926     /* calling HeapLock may result in infinite recursion, so do the critsect directly */
 927     if (!(flags & HEAP_NO_SERIALIZE))
 928         EnterCriticalSection( &heapPtr->critSection );
 929
 930     if (block)
 931     {
 932         /* Only check this single memory block */
 933
 934         /* The following code is really HEAP_IsInsideHeap   *
 935          * with serialization already done.                 */
 936         if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
 937             ((char *)block < (char *)subheap + subheap->headerSize
 938                               + sizeof(ARENA_INUSE)))
 939         {
 940             if (quiet == NOISY)
 941                 ERR("Heap %08lx: block %08lx is not inside heap\n",
 942                      (DWORD)heap, (DWORD)block );
 943             else if (WARN_ON(heap))
 944                 WARN("Heap %08lx: block %08lx is not inside heap\n",
 945                      (DWORD)heap, (DWORD)block );
 946             ret = FALSE;
 947         } else
 948             ret = HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)block - 1, quiet );
 949
 950         if (!(flags & HEAP_NO_SERIALIZE))
 951             LeaveCriticalSection( &heapPtr->critSection );
 952         return ret;
 953     }
 954
 955     subheap = &heapPtr->subheap;
 956     while (subheap && ret)
 957     {
 958         char *ptr = (char *)subheap + subheap->headerSize;
 959         while (ptr < (char *)subheap + subheap->size)
 960         {
 961             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
 962             {
 963                 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr )) {
 964                     ret = FALSE;
 965                     break;
 966                 }
 967                 ptr += sizeof(ARENA_FREE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
 968             }
 969             else
 970             {
 971                 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY )) {
 972                     ret = FALSE;
 973                     break;
 974                 }
 975                 ptr += sizeof(ARENA_INUSE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
 976             }
 977         }
 978         subheap = subheap->next;
 979     }
 980
 981     if (!(flags & HEAP_NO_SERIALIZE))
 982         LeaveCriticalSection( &heapPtr->critSection );
 983     return ret;
 984 }
 985
 986
 987 /***********************************************************************
 988  *           HeapCreate   (KERNEL32.336)
 989  * RETURNS
 990  *      Handle of heap: Success
 991  *      NULL: Failure
 992  */
 993 HANDLE WINAPI HeapCreate(
 994                 DWORD flags,       /* [in] Heap allocation flag */
 995                 DWORD initialSize, /* [in] Initial heap size */
 996                 DWORD maxSize      /* [in] Maximum heap size */
 997 ) {
 998     SUBHEAP *subheap;
 999
1000     /* Allocate the heap block */
1001
1002     if (!maxSize)
1003     {
1004         maxSize = HEAP_DEF_SIZE;
1005         flags |= HEAP_GROWABLE;
1006     }
1007     if (!(subheap = HEAP_CreateSubHeap( NULL, flags, initialSize, maxSize )))
1008     {
1009         SetLastError( ERROR_OUTOFMEMORY );
1010         return 0;
1011     }
1012
1013     /* link it into the per-process heap list */
1014     if (processHeap)
1015     {
1016         HEAP *heapPtr = subheap->heap;
1017         EnterCriticalSection( &processHeap->critSection );
1018         heapPtr->next = firstHeap;
1019         firstHeap = heapPtr;
1020         LeaveCriticalSection( &processHeap->critSection );
1021     }
1022     else  /* assume the first heap we create is the process main heap */
1023     {
1024         processHeap = subheap->heap;
1025     }
1026
1027     return (HANDLE)subheap;
1028 }
1029
1030 /***********************************************************************
1031  *           HeapDestroy   (KERNEL32.337)
1032  * RETURNS
1033  *      TRUE: Success
1034  *      FALSE: Failure
1035  */
1036 BOOL WINAPI HeapDestroy( HANDLE heap /* [in] Handle of heap */ )
1037 {
1038     HEAP *heapPtr = HEAP_GetPtr( heap );
1039     SUBHEAP *subheap;
1040
1041     TRACE("%08x\n", heap );
1042     if (!heapPtr) return FALSE;
1043
1044     if (heapPtr == processHeap)  /* cannot delete the main process heap */
1045     {
1046         SetLastError( ERROR_INVALID_PARAMETER );
1047         return FALSE;
1048     }
1049     else /* remove it from the per-process list */
1050     {
1051         HEAP **pptr;
1052         EnterCriticalSection( &processHeap->critSection );
1053         pptr = &firstHeap;
1054         while (*pptr && *pptr != heapPtr) pptr = &(*pptr)->next;
1055         if (*pptr) *pptr = (*pptr)->next;
1056         LeaveCriticalSection( &processHeap->critSection );
1057     }
1058
1059     DeleteCriticalSection( &heapPtr->critSection );
1060     subheap = &heapPtr->subheap;
1061     while (subheap)
1062     {
1063         SUBHEAP *next = subheap->next;
1064         if (subheap->selector) FreeSelector16( subheap->selector );
1065         VirtualFree( subheap, 0, MEM_RELEASE );
1066         subheap = next;
1067     }
1068     return TRUE;
1069 }
1070
1071
1072 /***********************************************************************
1073  *           HeapAlloc   (KERNEL32.334)
1074  * RETURNS
1075  *      Pointer to allocated memory block
1076  *      NULL: Failure
1077  */
1078 LPVOID WINAPI HeapAlloc(
1079               HANDLE heap, /* [in] Handle of private heap block */
1080               DWORD flags,   /* [in] Heap allocation control flags */
1081               DWORD size     /* [in] Number of bytes to allocate */
1082 ) {
1083     ARENA_FREE *pArena;
1084     ARENA_INUSE *pInUse;
1085     SUBHEAP *subheap;
1086     HEAP *heapPtr = HEAP_GetPtr( heap );
1087
1088     /* Validate the parameters */
1089
1090     if (!heapPtr) return NULL;
1091     flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1092     flags |= heapPtr->flags;
1093     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
1094     size = (size + 3) & ~3;
1095     if (size < HEAP_MIN_BLOCK_SIZE) size = HEAP_MIN_BLOCK_SIZE;
1096
1097     /* Locate a suitable free block */
1098
1099     if (!(pArena = HEAP_FindFreeBlock( heapPtr, size, &subheap )))
1100     {
1101         TRACE("(%08x,%08lx,%08lx): returning NULL\n",
1102                   heap, flags, size  );
1103         if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1104         SetLastError( ERROR_COMMITMENT_LIMIT );
1105         return NULL;
1106     }
1107
1108     /* Remove the arena from the free list */
1109
1110     pArena->next->prev = pArena->prev;
1111     pArena->prev->next = pArena->next;
1112
1113     /* Build the in-use arena */
1114
1115     pInUse = (ARENA_INUSE *)pArena;
1116     pInUse->size      = (pInUse->size & ~ARENA_FLAG_FREE)
1117                         + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1118     pInUse->callerEIP = GET_EIP();
1119     pInUse->threadId  = GetCurrentTask();
1120     pInUse->magic     = ARENA_INUSE_MAGIC;
1121
1122     /* Shrink the block */
1123
1124     HEAP_ShrinkBlock( subheap, pInUse, size );
1125
1126     if (flags & HEAP_ZERO_MEMORY)
1127         memset( pInUse + 1, 0, pInUse->size & ARENA_SIZE_MASK );
1128     else if (TRACE_ON(heap))
1129         memset( pInUse + 1, ARENA_INUSE_FILLER, pInUse->size & ARENA_SIZE_MASK );
1130
1131     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1132
1133     TRACE("(%08x,%08lx,%08lx): returning %08lx\n",
1134                   heap, flags, size, (DWORD)(pInUse + 1) );
1135     return (LPVOID)(pInUse + 1);
1136 }
1137
1138
1139 /***********************************************************************
1140  *           HeapFree   (KERNEL32.338)
1141  * RETURNS
1142  *      TRUE: Success
1143  *      FALSE: Failure
1144  */
1145 BOOL WINAPI HeapFree(
1146               HANDLE heap, /* [in] Handle of heap */
1147               DWORD flags,   /* [in] Heap freeing flags */
1148               LPVOID ptr     /* [in] Address of memory to free */
1149 ) {
1150     ARENA_INUSE *pInUse;
1151     SUBHEAP *subheap;
1152     HEAP *heapPtr = HEAP_GetPtr( heap );
1153
1154     /* Validate the parameters */
1155
1156     if (!heapPtr) return FALSE;
1157     if (!ptr)  /* Freeing a NULL ptr is doesn't indicate an error in Win2k */
1158     {
1159         WARN("(%08x,%08lx,%08lx): asked to free NULL\n",
1160                    heap, flags, (DWORD)ptr );
1161         return TRUE;
1162     }
1163
1164     flags &= HEAP_NO_SERIALIZE;
1165     flags |= heapPtr->flags;
1166     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
1167     if (!HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1168     {
1169         if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1170         SetLastError( ERROR_INVALID_PARAMETER );
1171         TRACE("(%08x,%08lx,%08lx): returning FALSE\n",
1172                       heap, flags, (DWORD)ptr );
1173         return FALSE;
1174     }
1175
1176     /* Turn the block into a free block */
1177
1178     pInUse  = (ARENA_INUSE *)ptr - 1;
1179     subheap = HEAP_FindSubHeap( heapPtr, pInUse );
1180     HEAP_MakeInUseBlockFree( subheap, pInUse );
1181
1182     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1183
1184     TRACE("(%08x,%08lx,%08lx): returning TRUE\n",
1185                   heap, flags, (DWORD)ptr );
1186     return TRUE;
1187 }
1188
1189
1190 /***********************************************************************
1191  *           HeapReAlloc   (KERNEL32.340)
1192  * RETURNS
1193  *      Pointer to reallocated memory block
1194  *      NULL: Failure
1195  */
1196 LPVOID WINAPI HeapReAlloc(
1197               HANDLE heap, /* [in] Handle of heap block */
1198               DWORD flags,   /* [in] Heap reallocation flags */
1199               LPVOID ptr,    /* [in] Address of memory to reallocate */
1200               DWORD size     /* [in] Number of bytes to reallocate */
1201 ) {
1202     ARENA_INUSE *pArena;
1203     DWORD oldSize;
1204     HEAP *heapPtr;
1205     SUBHEAP *subheap;
1206
1207     if (!ptr) return HeapAlloc( heap, flags, size );  /* FIXME: correct? */
1208     if (!(heapPtr = HEAP_GetPtr( heap ))) return FALSE;
1209
1210     /* Validate the parameters */
1211
1212     flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY |
1213              HEAP_REALLOC_IN_PLACE_ONLY;
1214     flags |= heapPtr->flags;
1215     size = (size + 3) & ~3;
1216     if (size < HEAP_MIN_BLOCK_SIZE) size = HEAP_MIN_BLOCK_SIZE;
1217
1218     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
1219     if (!HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1220     {
1221         if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1222         SetLastError( ERROR_INVALID_PARAMETER );
1223         TRACE("(%08x,%08lx,%08lx,%08lx): returning NULL\n",
1224                       heap, flags, (DWORD)ptr, size );
1225         return NULL;
1226     }
1227
1228     /* Check if we need to grow the block */
1229
1230     pArena = (ARENA_INUSE *)ptr - 1;
1231     pArena->threadId = GetCurrentTask();
1232     subheap = HEAP_FindSubHeap( heapPtr, pArena );
1233     oldSize = (pArena->size & ARENA_SIZE_MASK);
1234     if (size > oldSize)
1235     {
1236         char *pNext = (char *)(pArena + 1) + oldSize;
1237         if ((pNext < (char *)subheap + subheap->size) &&
1238             (*(DWORD *)pNext & ARENA_FLAG_FREE) &&
1239             (oldSize + (*(DWORD *)pNext & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) >= size))
1240         {
1241             /* The next block is free and large enough */
1242             ARENA_FREE *pFree = (ARENA_FREE *)pNext;
1243             pFree->next->prev = pFree->prev;
1244             pFree->prev->next = pFree->next;
1245             pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
1246             if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
1247                                                + size + HEAP_MIN_BLOCK_SIZE))
1248             {
1249                 if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1250                 SetLastError( ERROR_OUTOFMEMORY );
1251                 return NULL;
1252             }
1253             HEAP_ShrinkBlock( subheap, pArena, size );
1254         }
1255         else  /* Do it the hard way */
1256         {
1257             ARENA_FREE *pNew;
1258             ARENA_INUSE *pInUse;
1259             SUBHEAP *newsubheap;
1260
1261             if ((flags & HEAP_REALLOC_IN_PLACE_ONLY) ||
1262                 !(pNew = HEAP_FindFreeBlock( heapPtr, size, &newsubheap )))
1263             {
1264                 if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1265                 SetLastError( ERROR_OUTOFMEMORY );
1266                 return NULL;
1267             }
1268
1269             /* Build the in-use arena */
1270
1271             pNew->next->prev = pNew->prev;
1272             pNew->prev->next = pNew->next;
1273             pInUse = (ARENA_INUSE *)pNew;
1274             pInUse->size     = (pInUse->size & ~ARENA_FLAG_FREE)
1275                                + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1276             pInUse->threadId = GetCurrentTask();
1277             pInUse->magic    = ARENA_INUSE_MAGIC;
1278             HEAP_ShrinkBlock( newsubheap, pInUse, size );
1279             memcpy( pInUse + 1, pArena + 1, oldSize );
1280
1281             /* Free the previous block */
1282
1283             HEAP_MakeInUseBlockFree( subheap, pArena );
1284             subheap = newsubheap;
1285             pArena  = pInUse;
1286         }
1287     }
1288     else HEAP_ShrinkBlock( subheap, pArena, size );  /* Shrink the block */
1289
1290     /* Clear the extra bytes if needed */
1291
1292     if (size > oldSize)
1293     {
1294         if (flags & HEAP_ZERO_MEMORY)
1295             memset( (char *)(pArena + 1) + oldSize, 0,
1296                     (pArena->size & ARENA_SIZE_MASK) - oldSize );
1297         else if (TRACE_ON(heap))
1298             memset( (char *)(pArena + 1) + oldSize, ARENA_INUSE_FILLER,
1299                     (pArena->size & ARENA_SIZE_MASK) - oldSize );
1300     }
1301
1302     /* Return the new arena */
1303
1304     pArena->callerEIP = GET_EIP();
1305     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1306
1307     TRACE("(%08x,%08lx,%08lx,%08lx): returning %08lx\n",
1308                   heap, flags, (DWORD)ptr, size, (DWORD)(pArena + 1) );
1309     return (LPVOID)(pArena + 1);
1310 }
1311
1312
1313 /***********************************************************************
1314  *           HeapCompact   (KERNEL32.335)
1315  */
1316 DWORD WINAPI HeapCompact( HANDLE heap, DWORD flags )
1317 {
1318     SetLastError(ERROR_CALL_NOT_IMPLEMENTED);
1319     return 0;
1320 }
1321
1322
1323 /***********************************************************************
1324  *           HeapLock   (KERNEL32.339)
1325  * Attempts to acquire the critical section object for a specified heap.
1326  *
1327  * RETURNS
1328  *      TRUE: Success
1329  *      FALSE: Failure
1330  */
1331 BOOL WINAPI HeapLock(
1332               HANDLE heap /* [in] Handle of heap to lock for exclusive access */
1333 ) {
1334     HEAP *heapPtr = HEAP_GetPtr( heap );
1335     if (!heapPtr) return FALSE;
1336     EnterCriticalSection( &heapPtr->critSection );
1337     return TRUE;
1338 }
1339
1340
1341 /***********************************************************************
1342  *           HeapUnlock   (KERNEL32.342)
1343  * Releases ownership of the critical section object.
1344  *
1345  * RETURNS
1346  *      TRUE: Success
1347  *      FALSE: Failure
1348  */
1349 BOOL WINAPI HeapUnlock(
1350               HANDLE heap /* [in] Handle to the heap to unlock */
1351 ) {
1352     HEAP *heapPtr = HEAP_GetPtr( heap );
1353     if (!heapPtr) return FALSE;
1354     LeaveCriticalSection( &heapPtr->critSection );
1355     return TRUE;
1356 }
1357
1358
1359 /***********************************************************************
1360  *           HeapSize   (KERNEL32.341)
1361  * RETURNS
1362  *      Size in bytes of allocated memory
1363  *      0xffffffff: Failure
1364  */
1365 DWORD WINAPI HeapSize(
1366              HANDLE heap, /* [in] Handle of heap */
1367              DWORD flags,   /* [in] Heap size control flags */
1368              LPVOID ptr     /* [in] Address of memory to return size for */
1369 ) {
1370     DWORD ret;
1371     HEAP *heapPtr = HEAP_GetPtr( heap );
1372
1373     if (!heapPtr) return FALSE;
1374     flags &= HEAP_NO_SERIALIZE;
1375     flags |= heapPtr->flags;
1376     if (!(flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
1377     if (!HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1378     {
1379         SetLastError( ERROR_INVALID_PARAMETER );
1380         ret = 0xffffffff;
1381     }
1382     else
1383     {
1384         ARENA_INUSE *pArena = (ARENA_INUSE *)ptr - 1;
1385         ret = pArena->size & ARENA_SIZE_MASK;
1386     }
1387     if (!(flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1388
1389     TRACE("(%08x,%08lx,%08lx): returning %08lx\n",
1390                   heap, flags, (DWORD)ptr, ret );
1391     return ret;
1392 }
1393
1394
1395 /***********************************************************************
1396  *           HeapValidate   (KERNEL32.343)
1397  * Validates a specified heap.
1398  *
1399  * NOTES
1400  *      Flags is ignored.
1401  *
1402  * RETURNS
1403  *      TRUE: Success
1404  *      FALSE: Failure
1405  */
1406 BOOL WINAPI HeapValidate(
1407               HANDLE heap, /* [in] Handle to the heap */
1408               DWORD flags,   /* [in] Bit flags that control access during operation */
1409               LPCVOID block  /* [in] Optional pointer to memory block to validate */
1410 ) {
1411
1412     return HEAP_IsRealArena( heap, flags, block, QUIET );
1413 }
1414
1415
1416 /***********************************************************************
1417  *           HeapWalk   (KERNEL32.344)
1418  * Enumerates the memory blocks in a specified heap.
1419  * See HEAP_Dump() for info on heap structure.
1420  *
1421  * TODO
1422  *   - handling of PROCESS_HEAP_ENTRY_MOVEABLE and
1423  *     PROCESS_HEAP_ENTRY_DDESHARE (needs heap.c support)
1424  *
1425  * RETURNS
1426  *      TRUE: Success
1427  *      FALSE: Failure
1428  */
1429 BOOL WINAPI HeapWalk(
1430               HANDLE heap,               /* [in]  Handle to heap to enumerate */
1431               LPPROCESS_HEAP_ENTRY entry /* [out] Pointer to structure of enumeration info */
1432 ) {
1433     HEAP *heapPtr = HEAP_GetPtr(heap);
1434     SUBHEAP *sub, *currentheap = NULL;
1435     BOOL ret = FALSE;
1436     char *ptr;
1437     int region_index = 0;
1438
1439     if (!heapPtr || !entry)
1440     {
1441         SetLastError(ERROR_INVALID_PARAMETER);
1442         return FALSE;
1443     }
1444
1445     if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) EnterCriticalSection( &heapPtr->critSection );
1446
1447     /* set ptr to the next arena to be examined */
1448
1449     if (!entry->lpData) /* first call (init) ? */
1450     {
1451         TRACE("begin walking of heap 0x%08x.\n", heap);
1452         /*HEAP_Dump(heapPtr);*/
1453         currentheap = &heapPtr->subheap;
1454         ptr = (char*)currentheap + currentheap->headerSize;
1455     }
1456     else
1457     {
1458         ptr = entry->lpData;
1459         sub = &heapPtr->subheap;
1460         while (sub)
1461         {
1462             if (((char *)ptr >= (char *)sub) &&
1463                 ((char *)ptr < (char *)sub + sub->size))
1464             {
1465                 currentheap = sub;
1466                 break;
1467             }
1468             sub = sub->next;
1469             region_index++;
1470         }
1471         if (currentheap == NULL)
1472         {
1473             ERR("no matching subheap found, shouldn't happen !\n");
1474             SetLastError(ERROR_NO_MORE_ITEMS);
1475             goto HW_end;
1476         }
1477
1478         ptr += entry->cbData; /* point to next arena */
1479         if (ptr > (char *)currentheap + currentheap->size - 1)
1480         {   /* proceed with next subheap */
1481             if (!(currentheap = currentheap->next))
1482             {  /* successfully finished */
1483                 TRACE("end reached.\n");
1484                 SetLastError(ERROR_NO_MORE_ITEMS);
1485                 goto HW_end;
1486             }
1487             ptr = (char*)currentheap + currentheap->headerSize;
1488         }
1489     }
1490
1491     entry->wFlags = 0;
1492     if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1493     {
1494         ARENA_FREE *pArena = (ARENA_FREE *)ptr;
1495
1496         /*TRACE("free, magic: %04x\n", pArena->magic);*/
1497
1498         entry->lpData = pArena + 1;
1499         entry->cbData = pArena->size & ARENA_SIZE_MASK;
1500         entry->cbOverhead = sizeof(ARENA_FREE);
1501         entry->wFlags = PROCESS_HEAP_UNCOMMITTED_RANGE;
1502     }
1503     else
1504     {
1505         ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
1506
1507         /*TRACE("busy, magic: %04x\n", pArena->magic);*/
1508
1509         entry->lpData = pArena + 1;
1510         entry->cbData = pArena->size & ARENA_SIZE_MASK;
1511         entry->cbOverhead = sizeof(ARENA_INUSE);
1512         entry->wFlags = PROCESS_HEAP_ENTRY_BUSY;
1513         /* FIXME: can't handle PROCESS_HEAP_ENTRY_MOVEABLE
1514         and PROCESS_HEAP_ENTRY_DDESHARE yet */
1515     }
1516
1517     entry->iRegionIndex = region_index;
1518
1519     /* first element of heap ? */
1520     if (ptr == (char *)(currentheap + currentheap->headerSize))
1521     {
1522         entry->wFlags |= PROCESS_HEAP_REGION;
1523         entry->Foo.Region.dwCommittedSize = currentheap->commitSize;
1524         entry->Foo.Region.dwUnCommittedSize =
1525                 currentheap->size - currentheap->commitSize;
1526         entry->Foo.Region.lpFirstBlock = /* first valid block */
1527                 currentheap + currentheap->headerSize;
1528         entry->Foo.Region.lpLastBlock  = /* first invalid block */
1529                 currentheap + currentheap->size;
1530     }
1531     ret = TRUE;
1532
1533 HW_end:
1534     if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) LeaveCriticalSection( &heapPtr->critSection );
1535
1536     return ret;
1537 }
1538
1539
1540 /***********************************************************************
1541  *           HEAP_CreateSystemHeap
1542  *
1543  * Create the system heap.
1544  */
1545 BOOL HEAP_CreateSystemHeap(void)
1546 {
1547     SYSTEM_HEAP_DESCR *descr;
1548     HANDLE heap;
1549     HEAP *heapPtr;
1550     int created;
1551
1552     HANDLE map = CreateFileMappingA( INVALID_HANDLE_VALUE, NULL, SEC_COMMIT | PAGE_READWRITE,
1553                                      0, HEAP_DEF_SIZE, "__SystemHeap" );
1554     if (!map) return FALSE;
1555     created = (GetLastError() != ERROR_ALREADY_EXISTS);
1556
1557     if (!(heapPtr = MapViewOfFileEx( map, FILE_MAP_ALL_ACCESS, 0, 0, 0, SYSTEM_HEAP_BASE )))
1558     {
1559         /* pre-defined address not available, use any one */
1560         fprintf( stderr, "Warning: system heap base address %p not available\n",
1561                  SYSTEM_HEAP_BASE );
1562         if (!(heapPtr = MapViewOfFile( map, FILE_MAP_ALL_ACCESS, 0, 0, 0 )))
1563         {
1564             CloseHandle( map );
1565             return FALSE;
1566         }
1567     }
1568     heap = (HANDLE)heapPtr;
1569
1570     if (created)  /* newly created heap */
1571     {
1572         HEAP_InitSubHeap( heapPtr, heapPtr, HEAP_WINE_SHARED, 0, HEAP_DEF_SIZE );
1573         HeapLock( heap );
1574         descr = heapPtr->private = HeapAlloc( heap, HEAP_ZERO_MEMORY, sizeof(*descr) );
1575         assert( descr );
1576     }
1577     else
1578     {
1579         /* wait for the heap to be initialized */
1580         while (!heapPtr->private) Sleep(1);
1581         HeapLock( heap );
1582         /* remap it to the right address if necessary */
1583         if (heapPtr->subheap.heap != heapPtr)
1584         {
1585             void *base = heapPtr->subheap.heap;
1586             HeapUnlock( heap );
1587             UnmapViewOfFile( heapPtr );
1588             if (!(heapPtr = MapViewOfFileEx( map, FILE_MAP_ALL_ACCESS, 0, 0, 0, base )))
1589             {
1590                 fprintf( stderr, "Couldn't map system heap at the correct address (%p)\n", base );
1591                 CloseHandle( map );
1592                 return FALSE;
1593             }
1594             heap = (HANDLE)heapPtr;
1595             HeapLock( heap );
1596         }
1597         descr = heapPtr->private;
1598         assert( descr );
1599     }
1600     SystemHeap = heap;
1601     SystemHeapDescr = descr;
1602     HeapUnlock( heap );
1603     CloseHandle( map );
1604     return TRUE;
1605 }
1606
1607
1608 /***********************************************************************
1609  *           GetProcessHeap    (KERNEL32.259)
1610  */
1611 HANDLE WINAPI GetProcessHeap(void)
1612 {
1613     return (HANDLE)processHeap;
1614 }
1615
1616
1617 /***********************************************************************
1618  *           GetProcessHeaps    (KERNEL32.376)
1619  */
1620 DWORD WINAPI GetProcessHeaps( DWORD count, HANDLE *heaps )
1621 {
1622     DWORD total;
1623     HEAP *ptr;
1624
1625     if (!processHeap) return 0;  /* should never happen */
1626     total = 1;  /* main heap */
1627     EnterCriticalSection( &processHeap->critSection );
1628     for (ptr = firstHeap; ptr; ptr = ptr->next) total++;
1629     if (total <= count)
1630     {
1631         *heaps++ = (HANDLE)processHeap;
1632         for (ptr = firstHeap; ptr; ptr = ptr->next) *heaps++ = (HANDLE)ptr;
1633     }
1634     LeaveCriticalSection( &processHeap->critSection );
1635     return total;
1636 }
1637
1638
1639 /***********************************************************************
1640  *           HEAP_strdupA
1641  */
1642 LPSTR HEAP_strdupA( HANDLE heap, DWORD flags, LPCSTR str )
1643 {
1644     LPSTR p = HeapAlloc( heap, flags, strlen(str) + 1 );
1645     if(p) {
1646         SET_EIP(p);
1647         strcpy( p, str );
1648     }
1649     return p;
1650 }
1651
1652
1653 /***********************************************************************
1654  *           HEAP_strdupW
1655  */
1656 LPWSTR HEAP_strdupW( HANDLE heap, DWORD flags, LPCWSTR str )
1657 {
1658     INT len = lstrlenW(str) + 1;
1659     LPWSTR p = HeapAlloc( heap, flags, len * sizeof(WCHAR) );
1660     if(p) {
1661         SET_EIP(p);
1662         lstrcpyW( p, str );
1663     }
1664     return p;
1665 }
1666
1667
1668 /***********************************************************************
1669  *           HEAP_strdupAtoW
1670  */
1671 LPWSTR HEAP_strdupAtoW( HANDLE heap, DWORD flags, LPCSTR str )
1672 {
1673     LPWSTR ret;
1674
1675     if (!str) return NULL;
1676     ret = HeapAlloc( heap, flags, (strlen(str)+1) * sizeof(WCHAR) );
1677     if (ret) {
1678         SET_EIP(ret);
1679         lstrcpyAtoW( ret, str );
1680     }
1681     return ret;
1682 }
1683
1684
1685 /***********************************************************************
1686  *           HEAP_strdupWtoA
1687  */
1688 LPSTR HEAP_strdupWtoA( HANDLE heap, DWORD flags, LPCWSTR str )
1689 {
1690     LPSTR ret;
1691
1692     if (!str) return NULL;
1693     ret = HeapAlloc( heap, flags, lstrlenW(str) + 1 );
1694     if(ret) {
1695         SET_EIP(ret);
1696         lstrcpyWtoA( ret, str );
1697     }
1698     return ret;
1699 }
1700
1701
1702
1703 /***********************************************************************
1704  * 32-bit local heap functions (Win95; undocumented)
1705  */
1706
1707 #define HTABLE_SIZE      0x10000
1708 #define HTABLE_PAGESIZE  0x1000
1709 #define HTABLE_NPAGES    (HTABLE_SIZE / HTABLE_PAGESIZE)
1710
1711 #include "pshpack1.h"
1712 typedef struct _LOCAL32HEADER
1713 {
1714     WORD     freeListFirst[HTABLE_NPAGES];
1715     WORD     freeListSize[HTABLE_NPAGES];
1716     WORD     freeListLast[HTABLE_NPAGES];
1717
1718     DWORD    selectorTableOffset;
1719     WORD     selectorTableSize;
1720     WORD     selectorDelta;
1721
1722     DWORD    segment;
1723     LPBYTE   base;
1724
1725     DWORD    limit;
1726     DWORD    flags;
1727
1728     DWORD    magic;
1729     HANDLE heap;
1730
1731 } LOCAL32HEADER;
1732 #include "poppack.h"
1733
1734 #define LOCAL32_MAGIC    ((DWORD)('L' | ('H'<<8) | ('3'<<16) | ('2'<<24)))
1735
1736 /***********************************************************************
1737  *           Local32Init   (KERNEL.208)
1738  */
1739 HANDLE WINAPI Local32Init16( WORD segment, DWORD tableSize,
1740                              DWORD heapSize, DWORD flags )
1741 {
1742     DWORD totSize, segSize = 0;
1743     LPBYTE base;
1744     LOCAL32HEADER *header;
1745     HEAP *heap;
1746     WORD *selectorTable;
1747     WORD selectorEven, selectorOdd;
1748     int i, nrBlocks;
1749
1750     /* Determine new heap size */
1751
1752     if ( segment )
1753     {
1754         if ( (segSize = GetSelectorLimit16( segment )) == 0 )
1755             return 0;
1756         else
1757             segSize++;
1758     }
1759
1760     if ( heapSize == -1L )
1761         heapSize = 1024L*1024L;   /* FIXME */
1762
1763     heapSize = (heapSize + 0xffff) & 0xffff0000;
1764     segSize  = (segSize  + 0x0fff) & 0xfffff000;
1765     totSize  = segSize + HTABLE_SIZE + heapSize;
1766
1767
1768     /* Allocate memory and initialize heap */
1769
1770     if ( !(base = VirtualAlloc( NULL, totSize, MEM_RESERVE, PAGE_READWRITE )) )
1771         return 0;
1772
1773     if ( !VirtualAlloc( base, segSize + HTABLE_PAGESIZE,
1774                         MEM_COMMIT, PAGE_READWRITE ) )
1775     {
1776         VirtualFree( base, 0, MEM_RELEASE );
1777         return 0;
1778     }
1779
1780     heap = (HEAP *)(base + segSize + HTABLE_SIZE);
1781     if ( !HEAP_InitSubHeap( heap, (LPVOID)heap, 0, 0x10000, heapSize ) )
1782     {
1783         VirtualFree( base, 0, MEM_RELEASE );
1784         return 0;
1785     }
1786
1787
1788     /* Set up header and handle table */
1789
1790     header = (LOCAL32HEADER *)(base + segSize);
1791     header->base    = base;
1792     header->limit   = HTABLE_PAGESIZE-1;
1793     header->flags   = 0;
1794     header->magic   = LOCAL32_MAGIC;
1795     header->heap    = (HANDLE)heap;
1796
1797     header->freeListFirst[0] = sizeof(LOCAL32HEADER);
1798     header->freeListLast[0]  = HTABLE_PAGESIZE - 4;
1799     header->freeListSize[0]  = (HTABLE_PAGESIZE - sizeof(LOCAL32HEADER)) / 4;
1800
1801     for (i = header->freeListFirst[0]; i < header->freeListLast[0]; i += 4)
1802         *(DWORD *)((LPBYTE)header + i) = i+4;
1803
1804     header->freeListFirst[1] = 0xffff;
1805
1806
1807     /* Set up selector table */
1808
1809     nrBlocks      = (totSize + 0x7fff) >> 15;
1810     selectorTable = (LPWORD) HeapAlloc( header->heap,  0, nrBlocks * 2 );
1811     selectorEven  = SELECTOR_AllocBlock( base, totSize,
1812                                          SEGMENT_DATA, FALSE, FALSE );
1813     selectorOdd   = SELECTOR_AllocBlock( base + 0x8000, totSize - 0x8000,
1814                                          SEGMENT_DATA, FALSE, FALSE );
1815
1816     if ( !selectorTable || !selectorEven || !selectorOdd )
1817     {
1818         if ( selectorTable ) HeapFree( header->heap, 0, selectorTable );
1819         if ( selectorEven  ) SELECTOR_FreeBlock( selectorEven, totSize >> 16 );
1820         if ( selectorOdd   ) SELECTOR_FreeBlock( selectorOdd, (totSize-0x8000) >> 16 );
1821         HeapDestroy( header->heap );
1822         VirtualFree( base, 0, MEM_RELEASE );
1823         return 0;
1824     }
1825
1826     header->selectorTableOffset = (LPBYTE)selectorTable - header->base;
1827     header->selectorTableSize   = nrBlocks * 4;  /* ??? Win95 does it this way! */
1828     header->selectorDelta       = selectorEven - selectorOdd;
1829     header->segment             = segment? segment : selectorEven;
1830
1831     for (i = 0; i < nrBlocks; i++)
1832         selectorTable[i] = (i & 1)? selectorOdd  + ((i >> 1) << __AHSHIFT)
1833                                   : selectorEven + ((i >> 1) << __AHSHIFT);
1834
1835     /* Move old segment */
1836
1837     if ( segment )
1838     {
1839         /* FIXME: This is somewhat ugly and relies on implementation
1840                   details about 16-bit global memory handles ... */
1841
1842         LPBYTE oldBase = (LPBYTE)GetSelectorBase( segment );
1843         memcpy( base, oldBase, segSize );
1844         GLOBAL_MoveBlock( segment, base, totSize );
1845         HeapFree( SystemHeap, 0, oldBase );
1846     }
1847
1848     return (HANDLE)header;
1849 }
1850
1851 /***********************************************************************
1852  *           Local32_SearchHandle
1853  */
1854 static LPDWORD Local32_SearchHandle( LOCAL32HEADER *header, DWORD addr )
1855 {
1856     LPDWORD handle;
1857
1858     for ( handle = (LPDWORD)((LPBYTE)header + sizeof(LOCAL32HEADER));
1859           handle < (LPDWORD)((LPBYTE)header + header->limit);
1860           handle++)
1861     {
1862         if (*handle == addr)
1863             return handle;
1864     }
1865
1866     return NULL;
1867 }
1868
1869 /***********************************************************************
1870  *           Local32_ToHandle
1871  */
1872 static VOID Local32_ToHandle( LOCAL32HEADER *header, INT16 type,
1873                               DWORD addr, LPDWORD *handle, LPBYTE *ptr )
1874 {
1875     *handle = NULL;
1876     *ptr    = NULL;
1877
1878     switch (type)
1879     {
1880         case -2:    /* 16:16 pointer, no handles */
1881             *ptr    = PTR_SEG_TO_LIN( addr );
1882             *handle = (LPDWORD)*ptr;
1883             break;
1884
1885         case -1:    /* 32-bit offset, no handles */
1886             *ptr    = header->base + addr;
1887             *handle = (LPDWORD)*ptr;
1888             break;
1889
1890         case 0:     /* handle */
1891             if (    addr >= sizeof(LOCAL32HEADER)
1892                  && addr <  header->limit && !(addr & 3)
1893                  && *(LPDWORD)((LPBYTE)header + addr) >= HTABLE_SIZE )
1894             {
1895                 *handle = (LPDWORD)((LPBYTE)header + addr);
1896                 *ptr    = header->base + **handle;
1897             }
1898             break;
1899
1900         case 1:     /* 16:16 pointer */
1901             *ptr    = PTR_SEG_TO_LIN( addr );
1902             *handle = Local32_SearchHandle( header, *ptr - header->base );
1903             break;
1904
1905         case 2:     /* 32-bit offset */
1906             *ptr    = header->base + addr;
1907             *handle = Local32_SearchHandle( header, *ptr - header->base );
1908             break;
1909     }
1910 }
1911
1912 /***********************************************************************
1913  *           Local32_FromHandle
1914  */
1915 static VOID Local32_FromHandle( LOCAL32HEADER *header, INT16 type,
1916                                 DWORD *addr, LPDWORD handle, LPBYTE ptr )
1917 {
1918     switch (type)
1919     {
1920         case -2:    /* 16:16 pointer */
1921         case  1:
1922         {
1923             WORD *selTable = (LPWORD)(header->base + header->selectorTableOffset);
1924             DWORD offset   = (LPBYTE)ptr - header->base;
1925             *addr = MAKELONG( offset & 0x7fff, selTable[offset >> 15] );
1926         }
1927         break;
1928
1929         case -1:    /* 32-bit offset */
1930         case  2:
1931             *addr = ptr - header->base;
1932             break;
1933
1934         case  0:    /* handle */
1935             *addr = (LPBYTE)handle - (LPBYTE)header;
1936             break;
1937     }
1938 }
1939
1940 /***********************************************************************
1941  *           Local32Alloc   (KERNEL.209)
1942  */
1943 DWORD WINAPI Local32Alloc16( HANDLE heap, DWORD size, INT16 type, DWORD flags )
1944 {
1945     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
1946     LPDWORD handle;
1947     LPBYTE ptr;
1948     DWORD addr;
1949
1950     /* Allocate memory */
1951     ptr = HeapAlloc( header->heap,
1952                      (flags & LMEM_MOVEABLE)? HEAP_ZERO_MEMORY : 0, size );
1953     if (!ptr) return 0;
1954
1955
1956     /* Allocate handle if requested */
1957     if (type >= 0)
1958     {
1959         int page, i;
1960
1961         /* Find first page of handle table with free slots */
1962         for (page = 0; page < HTABLE_NPAGES; page++)
1963             if (header->freeListFirst[page] != 0)
1964                 break;
1965         if (page == HTABLE_NPAGES)
1966         {
1967             WARN("Out of handles!\n" );
1968             HeapFree( header->heap, 0, ptr );
1969             return 0;
1970         }
1971
1972         /* If virgin page, initialize it */
1973         if (header->freeListFirst[page] == 0xffff)
1974         {
1975             if ( !VirtualAlloc( (LPBYTE)header + (page << 12),
1976                                 0x1000, MEM_COMMIT, PAGE_READWRITE ) )
1977             {
1978                 WARN("Cannot grow handle table!\n" );
1979                 HeapFree( header->heap, 0, ptr );
1980                 return 0;
1981             }
1982
1983             header->limit += HTABLE_PAGESIZE;
1984
1985             header->freeListFirst[page] = 0;
1986             header->freeListLast[page]  = HTABLE_PAGESIZE - 4;
1987             header->freeListSize[page]  = HTABLE_PAGESIZE / 4;
1988
1989             for (i = 0; i < HTABLE_PAGESIZE; i += 4)
1990                 *(DWORD *)((LPBYTE)header + i) = i+4;
1991
1992             if (page < HTABLE_NPAGES-1)
1993                 header->freeListFirst[page+1] = 0xffff;
1994         }
1995
1996         /* Allocate handle slot from page */
1997         handle = (LPDWORD)((LPBYTE)header + header->freeListFirst[page]);
1998         if (--header->freeListSize[page] == 0)
1999             header->freeListFirst[page] = header->freeListLast[page] = 0;
2000         else
2001             header->freeListFirst[page] = *handle;
2002
2003         /* Store 32-bit offset in handle slot */
2004         *handle = ptr - header->base;
2005     }
2006     else
2007     {
2008         handle = (LPDWORD)ptr;
2009         header->flags |= 1;
2010     }
2011
2012
2013     /* Convert handle to requested output type */
2014     Local32_FromHandle( header, type, &addr, handle, ptr );
2015     return addr;
2016 }
2017
2018 /***********************************************************************
2019  *           Local32ReAlloc   (KERNEL.210)
2020  */
2021 DWORD WINAPI Local32ReAlloc16( HANDLE heap, DWORD addr, INT16 type,
2022                              DWORD size, DWORD flags )
2023 {
2024     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2025     LPDWORD handle;
2026     LPBYTE ptr;
2027
2028     if (!addr)
2029         return Local32Alloc16( heap, size, type, flags );
2030
2031     /* Retrieve handle and pointer */
2032     Local32_ToHandle( header, type, addr, &handle, &ptr );
2033     if (!handle) return FALSE;
2034
2035     /* Reallocate memory block */
2036     ptr = HeapReAlloc( header->heap,
2037                        (flags & LMEM_MOVEABLE)? HEAP_ZERO_MEMORY : 0,
2038                        ptr, size );
2039     if (!ptr) return 0;
2040
2041     /* Modify handle */
2042     if (type >= 0)
2043         *handle = ptr - header->base;
2044     else
2045         handle = (LPDWORD)ptr;
2046
2047     /* Convert handle to requested output type */
2048     Local32_FromHandle( header, type, &addr, handle, ptr );
2049     return addr;
2050 }
2051
2052 /***********************************************************************
2053  *           Local32Free   (KERNEL.211)
2054  */
2055 BOOL WINAPI Local32Free16( HANDLE heap, DWORD addr, INT16 type )
2056 {
2057     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2058     LPDWORD handle;
2059     LPBYTE ptr;
2060
2061     /* Retrieve handle and pointer */
2062     Local32_ToHandle( header, type, addr, &handle, &ptr );
2063     if (!handle) return FALSE;
2064
2065     /* Free handle if necessary */
2066     if (type >= 0)
2067     {
2068         int offset = (LPBYTE)handle - (LPBYTE)header;
2069         int page   = offset >> 12;
2070
2071         /* Return handle slot to page free list */
2072         if (header->freeListSize[page]++ == 0)
2073             header->freeListFirst[page] = header->freeListLast[page]  = offset;
2074         else
2075             *(LPDWORD)((LPBYTE)header + header->freeListLast[page]) = offset,
2076             header->freeListLast[page] = offset;
2077
2078         *handle = 0;
2079
2080         /* Shrink handle table when possible */
2081         while (page > 0 && header->freeListSize[page] == HTABLE_PAGESIZE / 4)
2082         {
2083             if ( VirtualFree( (LPBYTE)header +
2084                               (header->limit & ~(HTABLE_PAGESIZE-1)),
2085                               HTABLE_PAGESIZE, MEM_DECOMMIT ) )
2086                 break;
2087
2088             header->limit -= HTABLE_PAGESIZE;
2089             header->freeListFirst[page] = 0xffff;
2090             page--;
2091         }
2092     }
2093
2094     /* Free memory */
2095     return HeapFree( header->heap, 0, ptr );
2096 }
2097
2098 /***********************************************************************
2099  *           Local32Translate   (KERNEL.213)
2100  */
2101 DWORD WINAPI Local32Translate16( HANDLE heap, DWORD addr, INT16 type1, INT16 type2 )
2102 {
2103     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2104     LPDWORD handle;
2105     LPBYTE ptr;
2106
2107     Local32_ToHandle( header, type1, addr, &handle, &ptr );
2108     if (!handle) return 0;
2109
2110     Local32_FromHandle( header, type2, &addr, handle, ptr );
2111     return addr;
2112 }
2113
2114 /***********************************************************************
2115  *           Local32Size   (KERNEL.214)
2116  */
2117 DWORD WINAPI Local32Size16( HANDLE heap, DWORD addr, INT16 type )
2118 {
2119     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2120     LPDWORD handle;
2121     LPBYTE ptr;
2122
2123     Local32_ToHandle( header, type, addr, &handle, &ptr );
2124     if (!handle) return 0;
2125
2126     return HeapSize( header->heap, 0, ptr );
2127 }
2128
2129 /***********************************************************************
2130  *           Local32ValidHandle   (KERNEL.215)
2131  */
2132 BOOL WINAPI Local32ValidHandle16( HANDLE heap, WORD addr )
2133 {
2134     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2135     LPDWORD handle;
2136     LPBYTE ptr;
2137
2138     Local32_ToHandle( header, 0, addr, &handle, &ptr );
2139     return handle != NULL;
2140 }
2141
2142 /***********************************************************************
2143  *           Local32GetSegment   (KERNEL.229)
2144  */
2145 WORD WINAPI Local32GetSegment16( HANDLE heap )
2146 {
2147     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2148     return header->segment;
2149 }
2150
2151 /***********************************************************************
2152  *           Local32_GetHeap
2153  */
2154 static LOCAL32HEADER *Local32_GetHeap( HGLOBAL16 handle )
2155 {
2156     WORD selector = GlobalHandleToSel16( handle );
2157     DWORD base  = GetSelectorBase( selector );
2158     DWORD limit = GetSelectorLimit16( selector );
2159
2160     /* Hmmm. This is a somewhat stupid heuristic, but Windows 95 does
2161        it this way ... */
2162
2163     if ( limit > 0x10000 && ((LOCAL32HEADER *)base)->magic == LOCAL32_MAGIC )
2164         return (LOCAL32HEADER *)base;
2165
2166     base  += 0x10000;
2167     limit -= 0x10000;
2168
2169     if ( limit > 0x10000 && ((LOCAL32HEADER *)base)->magic == LOCAL32_MAGIC )
2170         return (LOCAL32HEADER *)base;
2171
2172     return NULL;
2173 }
2174
2175 /***********************************************************************
2176  *           Local32Info   (KERNEL.444)  (TOOLHELP.84)
2177  */
2178 BOOL16 WINAPI Local32Info16( LOCAL32INFO *pLocal32Info, HGLOBAL16 handle )
2179 {
2180     SUBHEAP *heapPtr;
2181     LPBYTE ptr;
2182     int i;
2183
2184     LOCAL32HEADER *header = Local32_GetHeap( handle );
2185     if ( !header ) return FALSE;
2186
2187     if ( !pLocal32Info || pLocal32Info->dwSize < sizeof(LOCAL32INFO) )
2188         return FALSE;
2189
2190     heapPtr = (SUBHEAP *)HEAP_GetPtr( header->heap );
2191     pLocal32Info->dwMemReserved = heapPtr->size;
2192     pLocal32Info->dwMemCommitted = heapPtr->commitSize;
2193     pLocal32Info->dwTotalFree = 0L;
2194     pLocal32Info->dwLargestFreeBlock = 0L;
2195
2196     /* Note: Local32 heaps always have only one subheap! */
2197     ptr = (LPBYTE)heapPtr + heapPtr->headerSize;
2198     while ( ptr < (LPBYTE)heapPtr + heapPtr->size )
2199     {
2200         if (*(DWORD *)ptr & ARENA_FLAG_FREE)
2201         {
2202             ARENA_FREE *pArena = (ARENA_FREE *)ptr;
2203             DWORD size = (pArena->size & ARENA_SIZE_MASK);
2204             ptr += sizeof(*pArena) + size;
2205
2206             pLocal32Info->dwTotalFree += size;
2207             if ( size > pLocal32Info->dwLargestFreeBlock )
2208                 pLocal32Info->dwLargestFreeBlock = size;
2209         }
2210         else
2211         {
2212             ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
2213             DWORD size = (pArena->size & ARENA_SIZE_MASK);
2214             ptr += sizeof(*pArena) + size;
2215         }
2216     }
2217
2218     pLocal32Info->dwcFreeHandles = 0;
2219     for ( i = 0; i < HTABLE_NPAGES; i++ )
2220     {
2221         if ( header->freeListFirst[i] == 0xffff ) break;
2222         pLocal32Info->dwcFreeHandles += header->freeListSize[i];
2223     }
2224     pLocal32Info->dwcFreeHandles += (HTABLE_NPAGES - i) * HTABLE_PAGESIZE/4;
2225
2226     return TRUE;
2227 }
2228
2229 /***********************************************************************
2230  *           Local32First   (KERNEL.445)  (TOOLHELP.85)
2231  */
2232 BOOL16 WINAPI Local32First16( LOCAL32ENTRY *pLocal32Entry, HGLOBAL16 handle )
2233 {
2234     FIXME("(%p, %04X): stub!\n", pLocal32Entry, handle );
2235     return FALSE;
2236 }
2237
2238 /***********************************************************************
2239  *           Local32Next   (KERNEL.446)  (TOOLHELP.86)
2240  */
2241 BOOL16 WINAPI Local32Next16( LOCAL32ENTRY *pLocal32Entry )
2242 {
2243     FIXME("(%p): stub!\n", pLocal32Entry );
2244     return FALSE;
2245 }
2246