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
 105 HANDLE SystemHeap = 0;
 106 HANDLE SegptrHeap = 0;
 107
 108 SYSTEM_HEAP_DESCR *SystemHeapDescr = 0;
 109
 110 static HEAP *processHeap;  /* main process heap */
 111 static HEAP *firstHeap;    /* head of secondary heaps list */
 112
 113 /* address where we try to map the system heap */
 114 #define SYSTEM_HEAP_BASE  ((void*)0x65430000)
 115
 116 static BOOL HEAP_IsRealArena( HANDLE heap, DWORD flags, LPCVOID block, BOOL quiet );
 117
 118 #ifdef __GNUC__
 119 #define GET_EIP()    (__builtin_return_address(0))
 120 #define SET_EIP(ptr) ((ARENA_INUSE*)(ptr) - 1)->callerEIP = GET_EIP()
 121 #else
 122 #define GET_EIP()    0
 123 #define SET_EIP(ptr) /* nothing */
 124 #endif  /* __GNUC__ */
 125
 126 /***********************************************************************
 127  *           HEAP_Dump
 128  */
 129 void HEAP_Dump( HEAP *heap )
 130 {
 131     int i;
 132     SUBHEAP *subheap;
 133     char *ptr;
 134
 135     DPRINTF( "Heap: %08lx\n", (DWORD)heap );
 136     DPRINTF( "Next: %08lx  Sub-heaps: %08lx",
 137           (DWORD)heap->next, (DWORD)&heap->subheap );
 138     subheap = &heap->subheap;
 139     while (subheap->next)
 140     {
 141         DPRINTF( " -> %08lx", (DWORD)subheap->next );
 142         subheap = subheap->next;
 143     }
 144
 145     DPRINTF( "\nFree lists:\n Block   Stat   Size    Id\n" );
 146     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 147         DPRINTF( "%08lx free %08lx %04x prev=%08lx next=%08lx\n",
 148               (DWORD)&heap->freeList[i].arena, heap->freeList[i].arena.size,
 149               heap->freeList[i].arena.threadId,
 150               (DWORD)heap->freeList[i].arena.prev,
 151               (DWORD)heap->freeList[i].arena.next );
 152
 153     subheap = &heap->subheap;
 154     while (subheap)
 155     {
 156         DWORD freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
 157         DPRINTF( "\n\nSub-heap %08lx: size=%08lx committed=%08lx\n",
 158               (DWORD)subheap, subheap->size, subheap->commitSize );
 159
 160         DPRINTF( "\n Block   Stat   Size    Id\n" );
 161         ptr = (char*)subheap + subheap->headerSize;
 162         while (ptr < (char *)subheap + subheap->size)
 163         {
 164             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
 165             {
 166                 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
 167                 DPRINTF( "%08lx free %08lx %04x prev=%08lx next=%08lx\n",
 168                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 169                       pArena->threadId, (DWORD)pArena->prev,
 170                       (DWORD)pArena->next);
 171                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 172                 arenaSize += sizeof(ARENA_FREE);
 173                 freeSize += pArena->size & ARENA_SIZE_MASK;
 174             }
 175             else if (*(DWORD *)ptr & ARENA_FLAG_PREV_FREE)
 176             {
 177                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 178                 DPRINTF( "%08lx Used %08lx %04x back=%08lx EIP=%p\n",
 179                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 180                       pArena->threadId, *((DWORD *)pArena - 1),
 181                       pArena->callerEIP );
 182                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 183                 arenaSize += sizeof(ARENA_INUSE);
 184                 usedSize += pArena->size & ARENA_SIZE_MASK;
 185             }
 186             else
 187             {
 188                 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
 189                 DPRINTF( "%08lx used %08lx %04x EIP=%p\n",
 190                       (DWORD)pArena, pArena->size & ARENA_SIZE_MASK,
 191                       pArena->threadId, pArena->callerEIP );
 192                 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
 193                 arenaSize += sizeof(ARENA_INUSE);
 194                 usedSize += pArena->size & ARENA_SIZE_MASK;
 195             }
 196         }
 197         DPRINTF( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
 198               subheap->size, subheap->commitSize, freeSize, usedSize,
 199               arenaSize, (arenaSize * 100) / subheap->size );
 200         subheap = subheap->next;
 201     }
 202 }
 203
 204
 205 /***********************************************************************
 206  *           HEAP_GetPtr
 207  * RETURNS
 208  *      Pointer to the heap
 209  *      NULL: Failure
 210  */
 211 static HEAP *HEAP_GetPtr(
 212              HANDLE heap /* [in] Handle to the heap */
 213 ) {
 214     HEAP *heapPtr = (HEAP *)heap;
 215     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
 216     {
 217         ERR("Invalid heap %08x!\n", heap );
 218         SetLastError( ERROR_INVALID_HANDLE );
 219         return NULL;
 220     }
 221     if (TRACE_ON(heap) && !HEAP_IsRealArena( heap, 0, NULL, NOISY ))
 222     {
 223         HEAP_Dump( heapPtr );
 224         assert( FALSE );
 225         SetLastError( ERROR_INVALID_HANDLE );
 226         return NULL;
 227     }
 228     return heapPtr;
 229 }
 230
 231
 232 /***********************************************************************
 233  *           HEAP_InsertFreeBlock
 234  *
 235  * Insert a free block into the free list.
 236  */
 237 static void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena )
 238 {
 239     FREE_LIST_ENTRY *pEntry = heap->freeList;
 240     while (pEntry->size < pArena->size) pEntry++;
 241     pArena->size      |= ARENA_FLAG_FREE;
 242     pArena->next       = pEntry->arena.next;
 243     pArena->next->prev = pArena;
 244     pArena->prev       = &pEntry->arena;
 245     pEntry->arena.next = pArena;
 246 }
 247
 248
 249 /***********************************************************************
 250  *           HEAP_FindSubHeap
 251  * Find the sub-heap containing a given address.
 252  *
 253  * RETURNS
 254  *      Pointer: Success
 255  *      NULL: Failure
 256  */
 257 static SUBHEAP *HEAP_FindSubHeap(
 258                 HEAP *heap, /* [in] Heap pointer */
 259                 LPCVOID ptr /* [in] Address */
 260 ) {
 261     SUBHEAP *sub = &heap->subheap;
 262     while (sub)
 263     {
 264         if (((char *)ptr >= (char *)sub) &&
 265             ((char *)ptr < (char *)sub + sub->size)) return sub;
 266         sub = sub->next;
 267     }
 268     return NULL;
 269 }
 270
 271
 272 /***********************************************************************
 273  *           HEAP_Commit
 274  *
 275  * Make sure the heap storage is committed up to (not including) ptr.
 276  */
 277 static BOOL HEAP_Commit( SUBHEAP *subheap, void *ptr )
 278 {
 279     DWORD size = (DWORD)((char *)ptr - (char *)subheap);
 280     DWORD pageMask = VIRTUAL_GetPageSize() - 1;
 281     size = (size + pageMask) & ~pageMask;  /* Align size on a page boundary */
 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 BOOL HEAP_Decommit( SUBHEAP *subheap, void *ptr )
 305 {
 306     DWORD size = (DWORD)((char *)ptr - (char *)subheap);
 307     DWORD pageMask = VIRTUAL_GetPageSize() - 1;
 308     size = (size + pageMask) & ~pageMask;  /* Align size on a page boundary */
 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         /* FIXME: once separate address spaces are implemented, only */
 539         /* the SystemHeap critical section should be global */
 540         /* if (!SystemHeap) */
 541         MakeCriticalSectionGlobal( &heap->critSection );
 542     }
 543
 544     /* Create the first free block */
 545
 546     HEAP_CreateFreeBlock( subheap, (LPBYTE)subheap + subheap->headerSize,
 547                           subheap->size - subheap->headerSize );
 548
 549     return TRUE;
 550 }
 551
 552 /***********************************************************************
 553  *           HEAP_CreateSubHeap
 554  *
 555  * Create a sub-heap of the given size.
 556  * If heap == NULL, creates a main heap.
 557  */
 558 static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, DWORD flags,
 559                                     DWORD commitSize, DWORD totalSize )
 560 {
 561     LPVOID address;
 562
 563     /* Round-up sizes on a 64K boundary */
 564
 565     if (flags & HEAP_WINE_SEGPTR)
 566     {
 567         totalSize = commitSize = 0x10000;  /* Only 64K at a time for SEGPTRs */
 568     }
 569     else
 570     {
 571         totalSize  = (totalSize + 0xffff) & 0xffff0000;
 572         commitSize = (commitSize + 0xffff) & 0xffff0000;
 573         if (!commitSize) commitSize = 0x10000;
 574         if (totalSize < commitSize) totalSize = commitSize;
 575     }
 576
 577     /* Allocate the memory block */
 578
 579     if (!(address = VirtualAlloc( NULL, totalSize,
 580                                   MEM_RESERVE, PAGE_EXECUTE_READWRITE )))
 581     {
 582         WARN("Could not VirtualAlloc %08lx bytes\n",
 583                  totalSize );
 584         return NULL;
 585     }
 586
 587     /* Initialize subheap */
 588
 589     if (!HEAP_InitSubHeap( heap? heap : (HEAP *)address,
 590                            address, flags, commitSize, totalSize ))
 591     {
 592         VirtualFree( address, 0, MEM_RELEASE );
 593         return NULL;
 594     }
 595
 596     return (SUBHEAP *)address;
 597 }
 598
 599
 600 /***********************************************************************
 601  *           HEAP_FindFreeBlock
 602  *
 603  * Find a free block at least as large as the requested size, and make sure
 604  * the requested size is committed.
 605  */
 606 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, DWORD size,
 607                                        SUBHEAP **ppSubHeap )
 608 {
 609     SUBHEAP *subheap;
 610     ARENA_FREE *pArena;
 611     FREE_LIST_ENTRY *pEntry = heap->freeList;
 612
 613     /* Find a suitable free list, and in it find a block large enough */
 614
 615     while (pEntry->size < size) pEntry++;
 616     pArena = pEntry->arena.next;
 617     while (pArena != &heap->freeList[0].arena)
 618     {
 619         if (pArena->size > size)
 620         {
 621             subheap = HEAP_FindSubHeap( heap, pArena );
 622             if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
 623                                                + size + HEAP_MIN_BLOCK_SIZE))
 624                 return NULL;
 625             *ppSubHeap = subheap;
 626             return pArena;
 627         }
 628
 629         pArena = pArena->next;
 630     }
 631
 632     /* If no block was found, attempt to grow the heap */
 633
 634     if (!(heap->flags & HEAP_GROWABLE))
 635     {
 636         WARN("Not enough space in heap %08lx for %08lx bytes\n",
 637                  (DWORD)heap, size );
 638         return NULL;
 639     }
 640     size += sizeof(SUBHEAP) + sizeof(ARENA_FREE);
 641     if (!(subheap = HEAP_CreateSubHeap( heap, heap->flags, size,
 642                                         max( HEAP_DEF_SIZE, size ) )))
 643         return NULL;
 644
 645     TRACE("created new sub-heap %08lx of %08lx bytes for heap %08lx\n",
 646                 (DWORD)subheap, size, (DWORD)heap );
 647
 648     *ppSubHeap = subheap;
 649     return (ARENA_FREE *)(subheap + 1);
 650 }
 651
 652
 653 /***********************************************************************
 654  *           HEAP_IsValidArenaPtr
 655  *
 656  * Check that the pointer is inside the range possible for arenas.
 657  */
 658 static BOOL HEAP_IsValidArenaPtr( HEAP *heap, void *ptr )
 659 {
 660     int i;
 661     SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
 662     if (!subheap) return FALSE;
 663     if ((char *)ptr >= (char *)subheap + subheap->headerSize) return TRUE;
 664     if (subheap != &heap->subheap) return FALSE;
 665     for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
 666         if (ptr == (void *)&heap->freeList[i].arena) return TRUE;
 667     return FALSE;
 668 }
 669
 670
 671 /***********************************************************************
 672  *           HEAP_ValidateFreeArena
 673  */
 674 static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
 675 {
 676     char *heapEnd = (char *)subheap + subheap->size;
 677
 678     /* Check magic number */
 679     if (pArena->magic != ARENA_FREE_MAGIC)
 680     {
 681         ERR("Heap %08lx: invalid free arena magic for %08lx\n",
 682                  (DWORD)subheap->heap, (DWORD)pArena );
 683         return FALSE;
 684     }
 685     /* Check size flags */
 686     if (!(pArena->size & ARENA_FLAG_FREE) ||
 687         (pArena->size & ARENA_FLAG_PREV_FREE))
 688     {
 689         ERR("Heap %08lx: bad flags %lx for free arena %08lx\n",
 690                  (DWORD)subheap->heap, pArena->size & ~ARENA_SIZE_MASK, (DWORD)pArena );
 691     }
 692     /* Check arena size */
 693     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
 694     {
 695         ERR("Heap %08lx: bad size %08lx for free arena %08lx\n",
 696                  (DWORD)subheap->heap, (DWORD)pArena->size & ARENA_SIZE_MASK, (DWORD)pArena );
 697         return FALSE;
 698     }
 699     /* Check that next pointer is valid */
 700     if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->next ))
 701     {
 702         ERR("Heap %08lx: bad next ptr %08lx for arena %08lx\n",
 703                  (DWORD)subheap->heap, (DWORD)pArena->next, (DWORD)pArena );
 704         return FALSE;
 705     }
 706     /* Check that next arena is free */
 707     if (!(pArena->next->size & ARENA_FLAG_FREE) ||
 708         (pArena->next->magic != ARENA_FREE_MAGIC))
 709     {
 710         ERR("Heap %08lx: next arena %08lx invalid for %08lx\n",
 711                  (DWORD)subheap->heap, (DWORD)pArena->next, (DWORD)pArena );
 712         return FALSE;
 713     }
 714     /* Check that prev pointer is valid */
 715     if (!HEAP_IsValidArenaPtr( subheap->heap, pArena->prev ))
 716     {
 717         ERR("Heap %08lx: bad prev ptr %08lx for arena %08lx\n",
 718                  (DWORD)subheap->heap, (DWORD)pArena->prev, (DWORD)pArena );
 719         return FALSE;
 720     }
 721     /* Check that prev arena is free */
 722     if (!(pArena->prev->size & ARENA_FLAG_FREE) ||
 723         (pArena->prev->magic != ARENA_FREE_MAGIC))
 724     {
 725         ERR("Heap %08lx: prev arena %08lx invalid for %08lx\n",
 726                  (DWORD)subheap->heap, (DWORD)pArena->prev, (DWORD)pArena );
 727         return FALSE;
 728     }
 729     /* Check that next block has PREV_FREE flag */
 730     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
 731     {
 732         if (!(*(DWORD *)((char *)(pArena + 1) +
 733             (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
 734         {
 735             ERR("Heap %08lx: free arena %08lx next block has no PREV_FREE flag\n",
 736                      (DWORD)subheap->heap, (DWORD)pArena );
 737             return FALSE;
 738         }
 739         /* Check next block back pointer */
 740         if (*((ARENA_FREE **)((char *)(pArena + 1) +
 741             (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
 742         {
 743             ERR("Heap %08lx: arena %08lx has wrong back ptr %08lx\n",
 744                      (DWORD)subheap->heap, (DWORD)pArena,
 745                      *((DWORD *)((char *)(pArena+1)+ (pArena->size & ARENA_SIZE_MASK)) - 1));
 746             return FALSE;
 747         }
 748     }
 749     return TRUE;
 750 }
 751
 752
 753 /***********************************************************************
 754  *           HEAP_ValidateInUseArena
 755  */
 756 static BOOL HEAP_ValidateInUseArena( SUBHEAP *subheap, ARENA_INUSE *pArena, BOOL quiet )
 757 {
 758     char *heapEnd = (char *)subheap + subheap->size;
 759
 760     /* Check magic number */
 761     if (pArena->magic != ARENA_INUSE_MAGIC)
 762     {
 763         if (quiet == NOISY) {
 764         ERR("Heap %08lx: invalid in-use arena magic for %08lx\n",
 765                  (DWORD)subheap->heap, (DWORD)pArena );
 766             if (TRACE_ON(heap))
 767                HEAP_Dump( subheap->heap );
 768         }  else if (WARN_ON(heap)) {
 769             WARN("Heap %08lx: invalid in-use arena magic for %08lx\n",
 770                  (DWORD)subheap->heap, (DWORD)pArena );
 771             if (TRACE_ON(heap))
 772                HEAP_Dump( subheap->heap );
 773         }
 774         return FALSE;
 775     }
 776     /* Check size flags */
 777     if (pArena->size & ARENA_FLAG_FREE)
 778     {
 779         ERR("Heap %08lx: bad flags %lx for in-use arena %08lx\n",
 780                  (DWORD)subheap->heap, pArena->size & ~ARENA_SIZE_MASK, (DWORD)pArena );
 781     }
 782     /* Check arena size */
 783     if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
 784     {
 785         ERR("Heap %08lx: bad size %08lx for in-use arena %08lx\n",
 786                  (DWORD)subheap->heap, (DWORD)pArena->size & ARENA_SIZE_MASK, (DWORD)pArena );
 787         return FALSE;
 788     }
 789     /* Check next arena PREV_FREE flag */
 790     if (((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
 791         (*(DWORD *)((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
 792     {
 793         ERR("Heap %08lx: in-use arena %08lx next block has PREV_FREE flag\n",
 794                  (DWORD)subheap->heap, (DWORD)pArena );
 795         return FALSE;
 796     }
 797     /* Check prev free arena */
 798     if (pArena->size & ARENA_FLAG_PREV_FREE)
 799     {
 800         ARENA_FREE *pPrev = *((ARENA_FREE **)pArena - 1);
 801         /* Check prev pointer */
 802         if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
 803         {
 804             ERR("Heap %08lx: bad back ptr %08lx for arena %08lx\n",
 805                     (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 806             return FALSE;
 807         }
 808         /* Check that prev arena is free */
 809         if (!(pPrev->size & ARENA_FLAG_FREE) ||
 810             (pPrev->magic != ARENA_FREE_MAGIC))
 811         {
 812             ERR("Heap %08lx: prev arena %08lx invalid for in-use %08lx\n",
 813                      (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 814             return FALSE;
 815         }
 816         /* Check that prev arena is really the previous block */
 817         if ((char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (char *)pArena)
 818         {
 819             ERR("Heap %08lx: prev arena %08lx is not prev for in-use %08lx\n",
 820                      (DWORD)subheap->heap, (DWORD)pPrev, (DWORD)pArena );
 821             return FALSE;
 822         }
 823     }
 824     return TRUE;
 825 }
 826
 827
 828 /***********************************************************************
 829  *           HEAP_IsInsideHeap
 830  * Checks whether the pointer points to a block inside a given heap.
 831  *
 832  * NOTES
 833  *      Should this return BOOL32?
 834  *
 835  * RETURNS
 836  *      !0: Success
 837  *      0: Failure
 838  */
 839 int HEAP_IsInsideHeap(
 840     HANDLE heap, /* [in] Heap */
 841     DWORD flags,   /* [in] Flags */
 842     LPCVOID ptr    /* [in] Pointer */
 843 ) {
 844     HEAP *heapPtr = HEAP_GetPtr( heap );
 845     SUBHEAP *subheap;
 846     int ret;
 847
 848     /* Validate the parameters */
 849
 850     if (!heapPtr) return 0;
 851     flags |= heapPtr->flags;
 852     if (!(flags & HEAP_NO_SERIALIZE)) HeapLock( heap );
 853     ret = (((subheap = HEAP_FindSubHeap( heapPtr, ptr )) != NULL) &&
 854            (((char *)ptr >= (char *)subheap + subheap->headerSize
 855                               + sizeof(ARENA_INUSE))));
 856     if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
 857     return ret;
 858 }
 859
 860
 861 /***********************************************************************
 862  *           HEAP_GetSegptr
 863  *
 864  * Transform a linear pointer into a SEGPTR. The pointer must have been
 865  * allocated from a HEAP_WINE_SEGPTR heap.
 866  */
 867 SEGPTR HEAP_GetSegptr( HANDLE heap, DWORD flags, LPCVOID ptr )
 868 {
 869     HEAP *heapPtr = HEAP_GetPtr( heap );
 870     SUBHEAP *subheap;
 871     SEGPTR ret;
 872
 873     /* Validate the parameters */
 874
 875     if (!heapPtr) return 0;
 876     flags |= heapPtr->flags;
 877     if (!(flags & HEAP_WINE_SEGPTR))
 878     {
 879         ERR("Heap %08x is not a SEGPTR heap\n",
 880                  heap );
 881         return 0;
 882     }
 883     if (!(flags & HEAP_NO_SERIALIZE)) HeapLock( heap );
 884
 885     /* Get the subheap */
 886
 887     if (!(subheap = HEAP_FindSubHeap( heapPtr, ptr )))
 888     {
 889         ERR("%p is not inside heap %08x\n",
 890                  ptr, heap );
 891         if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
 892         return 0;
 893     }
 894
 895     /* Build the SEGPTR */
 896
 897     ret = PTR_SEG_OFF_TO_SEGPTR(subheap->selector, (DWORD)ptr-(DWORD)subheap);
 898     if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
 899     return ret;
 900 }
 901
 902 /***********************************************************************
 903  *           HEAP_IsRealArena  [Internal]
 904  * Validates a block is a valid arena.
 905  *
 906  * RETURNS
 907  *      TRUE: Success
 908  *      FALSE: Failure
 909  */
 910 static BOOL HEAP_IsRealArena(
 911               HANDLE heap,   /* [in] Handle to the heap */
 912               DWORD flags,   /* [in] Bit flags that control access during operation */
 913               LPCVOID block, /* [in] Optional pointer to memory block to validate */
 914               BOOL quiet     /* [in] Flag - if true, HEAP_ValidateInUseArena
 915                               *             does not complain    */
 916 ) {
 917     SUBHEAP *subheap;
 918     HEAP *heapPtr = (HEAP *)(heap);
 919     BOOL ret = TRUE;
 920
 921     if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
 922     {
 923         ERR("Invalid heap %08x!\n", heap );
 924         return FALSE;
 925     }
 926
 927     flags &= HEAP_NO_SERIALIZE;
 928     flags |= heapPtr->flags;
 929     /* calling HeapLock may result in infinite recursion, so do the critsect directly */
 930     if (!(flags & HEAP_NO_SERIALIZE))
 931         EnterCriticalSection( &heapPtr->critSection );
 932
 933     if (block)
 934     {
 935         /* Only check this single memory block */
 936
 937         /* The following code is really HEAP_IsInsideHeap   *
 938          * with serialization already done.                 */
 939         if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
 940             ((char *)block < (char *)subheap + subheap->headerSize
 941                               + sizeof(ARENA_INUSE)))
 942         {
 943             if (quiet == NOISY)
 944                 ERR("Heap %08lx: block %08lx is not inside heap\n",
 945                      (DWORD)heap, (DWORD)block );
 946             else if (WARN_ON(heap))
 947                 WARN("Heap %08lx: block %08lx is not inside heap\n",
 948                      (DWORD)heap, (DWORD)block );
 949             ret = FALSE;
 950         } else
 951             ret = HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)block - 1, quiet );
 952
 953         if (!(flags & HEAP_NO_SERIALIZE))
 954             LeaveCriticalSection( &heapPtr->critSection );
 955         return ret;
 956     }
 957
 958     subheap = &heapPtr->subheap;
 959     while (subheap && ret)
 960     {
 961         char *ptr = (char *)subheap + subheap->headerSize;
 962         while (ptr < (char *)subheap + subheap->size)
 963         {
 964             if (*(DWORD *)ptr & ARENA_FLAG_FREE)
 965             {
 966                 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr )) {
 967                     ret = FALSE;
 968                     break;
 969                 }
 970                 ptr += sizeof(ARENA_FREE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
 971             }
 972             else
 973             {
 974                 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY )) {
 975                     ret = FALSE;
 976                     break;
 977                 }
 978                 ptr += sizeof(ARENA_INUSE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
 979             }
 980         }
 981         subheap = subheap->next;
 982     }
 983
 984     if (!(flags & HEAP_NO_SERIALIZE))
 985         LeaveCriticalSection( &heapPtr->critSection );
 986     return ret;
 987 }
 988
 989
 990 /***********************************************************************
 991  *           HeapCreate   (KERNEL32.336)
 992  * RETURNS
 993  *      Handle of heap: Success
 994  *      NULL: Failure
 995  */
 996 HANDLE WINAPI HeapCreate(
 997                 DWORD flags,       /* [in] Heap allocation flag */
 998                 DWORD initialSize, /* [in] Initial heap size */
 999                 DWORD maxSize      /* [in] Maximum heap size */
1000 ) {
1001     SUBHEAP *subheap;
1002
1003     /* Allocate the heap block */
1004
1005     if (!maxSize)
1006     {
1007         maxSize = HEAP_DEF_SIZE;
1008         flags |= HEAP_GROWABLE;
1009     }
1010     if (!(subheap = HEAP_CreateSubHeap( NULL, flags, initialSize, maxSize )))
1011     {
1012         SetLastError( ERROR_OUTOFMEMORY );
1013         return 0;
1014     }
1015
1016     /* link it into the per-process heap list */
1017     if (processHeap)
1018     {
1019         HEAP *heapPtr = subheap->heap;
1020         EnterCriticalSection( &processHeap->critSection );
1021         heapPtr->next = firstHeap;
1022         firstHeap = heapPtr;
1023         LeaveCriticalSection( &processHeap->critSection );
1024     }
1025     else  /* assume the first heap we create is the process main heap */
1026     {
1027         processHeap = subheap->heap;
1028     }
1029
1030     return (HANDLE)subheap;
1031 }
1032
1033 /***********************************************************************
1034  *           HeapDestroy   (KERNEL32.337)
1035  * RETURNS
1036  *      TRUE: Success
1037  *      FALSE: Failure
1038  */
1039 BOOL WINAPI HeapDestroy( HANDLE heap /* [in] Handle of heap */ )
1040 {
1041     HEAP *heapPtr = HEAP_GetPtr( heap );
1042     SUBHEAP *subheap;
1043
1044     TRACE("%08x\n", heap );
1045     if (!heapPtr) return FALSE;
1046
1047     if (heapPtr == processHeap)  /* cannot delete the main process heap */
1048     {
1049         SetLastError( ERROR_INVALID_PARAMETER );
1050         return FALSE;
1051     }
1052     else /* remove it from the per-process list */
1053     {
1054         HEAP **pptr;
1055         EnterCriticalSection( &processHeap->critSection );
1056         pptr = &firstHeap;
1057         while (*pptr && *pptr != heapPtr) pptr = &(*pptr)->next;
1058         if (*pptr) *pptr = (*pptr)->next;
1059         LeaveCriticalSection( &processHeap->critSection );
1060     }
1061
1062     DeleteCriticalSection( &heapPtr->critSection );
1063     subheap = &heapPtr->subheap;
1064     while (subheap)
1065     {
1066         SUBHEAP *next = subheap->next;
1067         if (subheap->selector) FreeSelector16( subheap->selector );
1068         VirtualFree( subheap, 0, MEM_RELEASE );
1069         subheap = next;
1070     }
1071     return TRUE;
1072 }
1073
1074
1075 /***********************************************************************
1076  *           HeapAlloc   (KERNEL32.334)
1077  * RETURNS
1078  *      Pointer to allocated memory block
1079  *      NULL: Failure
1080  */
1081 LPVOID WINAPI HeapAlloc(
1082               HANDLE heap, /* [in] Handle of private heap block */
1083               DWORD flags,   /* [in] Heap allocation control flags */
1084               DWORD size     /* [in] Number of bytes to allocate */
1085 ) {
1086     ARENA_FREE *pArena;
1087     ARENA_INUSE *pInUse;
1088     SUBHEAP *subheap;
1089     HEAP *heapPtr = HEAP_GetPtr( heap );
1090
1091     /* Validate the parameters */
1092
1093     if (!heapPtr) return NULL;
1094     flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1095     flags |= heapPtr->flags;
1096     if (!(flags & HEAP_NO_SERIALIZE)) HeapLock( heap );
1097     size = (size + 3) & ~3;
1098     if (size < HEAP_MIN_BLOCK_SIZE) size = HEAP_MIN_BLOCK_SIZE;
1099
1100     /* Locate a suitable free block */
1101
1102     if (!(pArena = HEAP_FindFreeBlock( heapPtr, size, &subheap )))
1103     {
1104         TRACE("(%08x,%08lx,%08lx): returning NULL\n",
1105                   heap, flags, size  );
1106         if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
1107         SetLastError( ERROR_COMMITMENT_LIMIT );
1108         return NULL;
1109     }
1110
1111     /* Remove the arena from the free list */
1112
1113     pArena->next->prev = pArena->prev;
1114     pArena->prev->next = pArena->next;
1115
1116     /* Build the in-use arena */
1117
1118     pInUse = (ARENA_INUSE *)pArena;
1119     pInUse->size      = (pInUse->size & ~ARENA_FLAG_FREE)
1120                         + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1121     pInUse->callerEIP = GET_EIP();
1122     pInUse->threadId  = GetCurrentTask();
1123     pInUse->magic     = ARENA_INUSE_MAGIC;
1124
1125     /* Shrink the block */
1126
1127     HEAP_ShrinkBlock( subheap, pInUse, size );
1128
1129     if (flags & HEAP_ZERO_MEMORY) memset( pInUse + 1, 0, size );
1130     else if (TRACE_ON(heap)) memset( pInUse + 1, ARENA_INUSE_FILLER, size );
1131
1132     if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
1133
1134     TRACE("(%08x,%08lx,%08lx): returning %08lx\n",
1135                   heap, flags, size, (DWORD)(pInUse + 1) );
1136     return (LPVOID)(pInUse + 1);
1137 }
1138
1139
1140 /***********************************************************************
1141  *           HeapFree   (KERNEL32.338)
1142  * RETURNS
1143  *      TRUE: Success
1144  *      FALSE: Failure
1145  */
1146 BOOL WINAPI HeapFree(
1147               HANDLE heap, /* [in] Handle of heap */
1148               DWORD flags,   /* [in] Heap freeing flags */
1149               LPVOID ptr     /* [in] Address of memory to free */
1150 ) {
1151     ARENA_INUSE *pInUse;
1152     SUBHEAP *subheap;
1153     HEAP *heapPtr = HEAP_GetPtr( heap );
1154
1155     /* Validate the parameters */
1156
1157     if (!heapPtr) return FALSE;
1158     flags &= HEAP_NO_SERIALIZE;
1159     flags |= heapPtr->flags;
1160     if (!(flags & HEAP_NO_SERIALIZE)) HeapLock( heap );
1161     if (!ptr)
1162     {
1163         WARN("(%08x,%08lx,%08lx): asked to free NULL\n",
1164                    heap, flags, (DWORD)ptr );
1165     }
1166     if (!ptr || !HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1167     {
1168         if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
1169         SetLastError( ERROR_INVALID_PARAMETER );
1170         TRACE("(%08x,%08lx,%08lx): returning FALSE\n",
1171                       heap, flags, (DWORD)ptr );
1172         return FALSE;
1173     }
1174
1175     /* Turn the block into a free block */
1176
1177     pInUse  = (ARENA_INUSE *)ptr - 1;
1178     subheap = HEAP_FindSubHeap( heapPtr, pInUse );
1179     HEAP_MakeInUseBlockFree( subheap, pInUse );
1180
1181     if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
1182 /*    SetLastError( 0 ); */
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)) HeapLock( heap );
1219     if (!HEAP_IsRealArena( heap, HEAP_NO_SERIALIZE, ptr, QUIET ))
1220     {
1221         if (!(flags & HEAP_NO_SERIALIZE)) HeapUnlock( heap );
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)) HeapUnlock( heap );
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)) HeapUnlock( heap );
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)) HeapUnlock( heap );
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)) HeapLock( heap );
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)) HeapUnlock( heap );
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  *
1420  * RETURNS
1421  *      TRUE: Success
1422  *      FALSE: Failure
1423  */
1424 BOOL WINAPI HeapWalk(
1425               HANDLE heap,               /* [in]  Handle to heap to enumerate */
1426               LPPROCESS_HEAP_ENTRY entry  /* [out] Pointer to structure of enumeration info */
1427 ) {
1428     FIXME("(%08x): stub.\n", heap );
1429     return FALSE;
1430 }
1431
1432
1433 /***********************************************************************
1434  *           HEAP_CreateSystemHeap
1435  *
1436  * Create the system heap.
1437  */
1438 BOOL HEAP_CreateSystemHeap(void)
1439 {
1440     SYSTEM_HEAP_DESCR *descr;
1441     HANDLE heap;
1442     HEAP *heapPtr;
1443     int created;
1444
1445     HANDLE map = CreateFileMappingA( INVALID_HANDLE_VALUE, NULL, SEC_COMMIT | PAGE_READWRITE,
1446                                      0, HEAP_DEF_SIZE, "__SystemHeap" );
1447     if (!map) return FALSE;
1448     created = (GetLastError() != ERROR_ALREADY_EXISTS);
1449
1450     if (!(heapPtr = MapViewOfFileEx( map, FILE_MAP_ALL_ACCESS, 0, 0, 0, SYSTEM_HEAP_BASE )))
1451     {
1452         /* pre-defined address not available, use any one */
1453         fprintf( stderr, "Warning: system heap base address %p not available\n",
1454                  SYSTEM_HEAP_BASE );
1455         if (!(heapPtr = MapViewOfFile( map, FILE_MAP_ALL_ACCESS, 0, 0, 0 )))
1456         {
1457             CloseHandle( map );
1458             return FALSE;
1459         }
1460     }
1461     heap = (HANDLE)heapPtr;
1462
1463     if (created)  /* newly created heap */
1464     {
1465         HEAP_InitSubHeap( heapPtr, heapPtr, HEAP_WINE_SHARED, 0, HEAP_DEF_SIZE );
1466         HeapLock( heap );
1467         descr = heapPtr->private = HeapAlloc( heap, HEAP_ZERO_MEMORY, sizeof(*descr) );
1468         assert( descr );
1469     }
1470     else
1471     {
1472         /* wait for the heap to be initialized */
1473         while (!heapPtr->private) Sleep(1);
1474         HeapLock( heap );
1475         /* remap it to the right address if necessary */
1476         if (heapPtr->subheap.heap != heapPtr)
1477         {
1478             void *base = heapPtr->subheap.heap;
1479             HeapUnlock( heap );
1480             UnmapViewOfFile( heapPtr );
1481             if (!(heapPtr = MapViewOfFileEx( map, FILE_MAP_ALL_ACCESS, 0, 0, 0, base )))
1482             {
1483                 fprintf( stderr, "Couldn't map system heap at the correct address (%p)\n", base );
1484                 CloseHandle( map );
1485                 return FALSE;
1486             }
1487             heap = (HANDLE)heapPtr;
1488             HeapLock( heap );
1489         }
1490         descr = heapPtr->private;
1491         assert( descr );
1492     }
1493     SystemHeap = heap;
1494     SystemHeapDescr = descr;
1495     HeapUnlock( heap );
1496     CloseHandle( map );
1497     return TRUE;
1498 }
1499
1500
1501 /***********************************************************************
1502  *           GetProcessHeap    (KERNEL32.259)
1503  */
1504 HANDLE WINAPI GetProcessHeap(void)
1505 {
1506     return (HANDLE)processHeap;
1507 }
1508
1509
1510 /***********************************************************************
1511  *           GetProcessHeaps    (KERNEL32.376)
1512  */
1513 DWORD WINAPI GetProcessHeaps( DWORD count, HANDLE *heaps )
1514 {
1515     DWORD total;
1516     HEAP *ptr;
1517
1518     if (!processHeap) return 0;  /* should never happen */
1519     total = 1;  /* main heap */
1520     EnterCriticalSection( &processHeap->critSection );
1521     for (ptr = firstHeap; ptr; ptr = ptr->next) total++;
1522     if (total <= count)
1523     {
1524         *heaps++ = (HANDLE)processHeap;
1525         for (ptr = firstHeap; ptr; ptr = ptr->next) *heaps++ = (HANDLE)ptr;
1526     }
1527     LeaveCriticalSection( &processHeap->critSection );
1528     return total;
1529 }
1530
1531
1532 /***********************************************************************
1533  *           HEAP_xalloc
1534  *
1535  * Same as HeapAlloc(), but die on failure.
1536  */
1537 LPVOID HEAP_xalloc( HANDLE heap, DWORD flags, DWORD size )
1538 {
1539     LPVOID p = HeapAlloc( heap, flags, size );
1540     if (!p)
1541     {
1542         MESSAGE("Virtual memory exhausted.\n" );
1543         exit(1);
1544     }
1545     SET_EIP(p);
1546     return p;
1547 }
1548
1549
1550 /***********************************************************************
1551  *           HEAP_xrealloc
1552  *
1553  * Same as HeapReAlloc(), but die on failure.
1554  */
1555 LPVOID HEAP_xrealloc( HANDLE heap, DWORD flags, LPVOID lpMem, DWORD size )
1556 {
1557     LPVOID p = HeapReAlloc( heap, flags, lpMem, size );
1558     if (!p)
1559     {
1560         MESSAGE("Virtual memory exhausted.\n" );
1561         exit(1);
1562     }
1563     SET_EIP(p);
1564     return p;
1565 }
1566
1567
1568 /***********************************************************************
1569  *           HEAP_strdupA
1570  */
1571 LPSTR HEAP_strdupA( HANDLE heap, DWORD flags, LPCSTR str )
1572 {
1573     LPSTR p = HEAP_xalloc( heap, flags, strlen(str) + 1 );
1574     SET_EIP(p);
1575     strcpy( p, str );
1576     return p;
1577 }
1578
1579
1580 /***********************************************************************
1581  *           HEAP_strdupW
1582  */
1583 LPWSTR HEAP_strdupW( HANDLE heap, DWORD flags, LPCWSTR str )
1584 {
1585     INT len = lstrlenW(str) + 1;
1586     LPWSTR p = HEAP_xalloc( heap, flags, len * sizeof(WCHAR) );
1587     SET_EIP(p);
1588     lstrcpyW( p, str );
1589     return p;
1590 }
1591
1592
1593 /***********************************************************************
1594  *           HEAP_strdupAtoW
1595  */
1596 LPWSTR HEAP_strdupAtoW( HANDLE heap, DWORD flags, LPCSTR str )
1597 {
1598     LPWSTR ret;
1599
1600     if (!str) return NULL;
1601     ret = HEAP_xalloc( heap, flags, (strlen(str)+1) * sizeof(WCHAR) );
1602     SET_EIP(ret);
1603     lstrcpyAtoW( ret, str );
1604     return ret;
1605 }
1606
1607
1608 /***********************************************************************
1609  *           HEAP_strdupWtoA
1610  */
1611 LPSTR HEAP_strdupWtoA( HANDLE heap, DWORD flags, LPCWSTR str )
1612 {
1613     LPSTR ret;
1614
1615     if (!str) return NULL;
1616     ret = HEAP_xalloc( heap, flags, lstrlenW(str) + 1 );
1617     SET_EIP(ret);
1618     lstrcpyWtoA( ret, str );
1619     return ret;
1620 }
1621
1622
1623
1624 /***********************************************************************
1625  * 32-bit local heap functions (Win95; undocumented)
1626  */
1627
1628 #define HTABLE_SIZE      0x10000
1629 #define HTABLE_PAGESIZE  0x1000
1630 #define HTABLE_NPAGES    (HTABLE_SIZE / HTABLE_PAGESIZE)
1631
1632 #include "pshpack1.h"
1633 typedef struct _LOCAL32HEADER
1634 {
1635     WORD     freeListFirst[HTABLE_NPAGES];
1636     WORD     freeListSize[HTABLE_NPAGES];
1637     WORD     freeListLast[HTABLE_NPAGES];
1638
1639     DWORD    selectorTableOffset;
1640     WORD     selectorTableSize;
1641     WORD     selectorDelta;
1642
1643     DWORD    segment;
1644     LPBYTE   base;
1645
1646     DWORD    limit;
1647     DWORD    flags;
1648
1649     DWORD    magic;
1650     HANDLE heap;
1651
1652 } LOCAL32HEADER;
1653 #include "poppack.h"
1654
1655 #define LOCAL32_MAGIC    ((DWORD)('L' | ('H'<<8) | ('3'<<16) | ('2'<<24)))
1656
1657 /***********************************************************************
1658  *           Local32Init   (KERNEL.208)
1659  */
1660 HANDLE WINAPI Local32Init16( WORD segment, DWORD tableSize,
1661                              DWORD heapSize, DWORD flags )
1662 {
1663     DWORD totSize, segSize = 0;
1664     LPBYTE base;
1665     LOCAL32HEADER *header;
1666     HEAP *heap;
1667     WORD *selectorTable;
1668     WORD selectorEven, selectorOdd;
1669     int i, nrBlocks;
1670
1671     /* Determine new heap size */
1672
1673     if ( segment )
1674     {
1675         if ( (segSize = GetSelectorLimit16( segment )) == 0 )
1676             return 0;
1677         else
1678             segSize++;
1679     }
1680
1681     if ( heapSize == -1L )
1682         heapSize = 1024L*1024L;   /* FIXME */
1683
1684     heapSize = (heapSize + 0xffff) & 0xffff0000;
1685     segSize  = (segSize  + 0x0fff) & 0xfffff000;
1686     totSize  = segSize + HTABLE_SIZE + heapSize;
1687
1688
1689     /* Allocate memory and initialize heap */
1690
1691     if ( !(base = VirtualAlloc( NULL, totSize, MEM_RESERVE, PAGE_READWRITE )) )
1692         return 0;
1693
1694     if ( !VirtualAlloc( base, segSize + HTABLE_PAGESIZE,
1695                         MEM_COMMIT, PAGE_READWRITE ) )
1696     {
1697         VirtualFree( base, 0, MEM_RELEASE );
1698         return 0;
1699     }
1700
1701     heap = (HEAP *)(base + segSize + HTABLE_SIZE);
1702     if ( !HEAP_InitSubHeap( heap, (LPVOID)heap, 0, 0x10000, heapSize ) )
1703     {
1704         VirtualFree( base, 0, MEM_RELEASE );
1705         return 0;
1706     }
1707
1708
1709     /* Set up header and handle table */
1710
1711     header = (LOCAL32HEADER *)(base + segSize);
1712     header->base    = base;
1713     header->limit   = HTABLE_PAGESIZE-1;
1714     header->flags   = 0;
1715     header->magic   = LOCAL32_MAGIC;
1716     header->heap    = (HANDLE)heap;
1717
1718     header->freeListFirst[0] = sizeof(LOCAL32HEADER);
1719     header->freeListLast[0]  = HTABLE_PAGESIZE - 4;
1720     header->freeListSize[0]  = (HTABLE_PAGESIZE - sizeof(LOCAL32HEADER)) / 4;
1721
1722     for (i = header->freeListFirst[0]; i < header->freeListLast[0]; i += 4)
1723         *(DWORD *)((LPBYTE)header + i) = i+4;
1724
1725     header->freeListFirst[1] = 0xffff;
1726
1727
1728     /* Set up selector table */
1729
1730     nrBlocks      = (totSize + 0x7fff) >> 15;
1731     selectorTable = (LPWORD) HeapAlloc( header->heap,  0, nrBlocks * 2 );
1732     selectorEven  = SELECTOR_AllocBlock( base, totSize,
1733                                          SEGMENT_DATA, FALSE, FALSE );
1734     selectorOdd   = SELECTOR_AllocBlock( base + 0x8000, totSize - 0x8000,
1735                                          SEGMENT_DATA, FALSE, FALSE );
1736
1737     if ( !selectorTable || !selectorEven || !selectorOdd )
1738     {
1739         if ( selectorTable ) HeapFree( header->heap, 0, selectorTable );
1740         if ( selectorEven  ) SELECTOR_FreeBlock( selectorEven, totSize >> 16 );
1741         if ( selectorOdd   ) SELECTOR_FreeBlock( selectorOdd, (totSize-0x8000) >> 16 );
1742         HeapDestroy( header->heap );
1743         VirtualFree( base, 0, MEM_RELEASE );
1744         return 0;
1745     }
1746
1747     header->selectorTableOffset = (LPBYTE)selectorTable - header->base;
1748     header->selectorTableSize   = nrBlocks * 4;  /* ??? Win95 does it this way! */
1749     header->selectorDelta       = selectorEven - selectorOdd;
1750     header->segment             = segment? segment : selectorEven;
1751
1752     for (i = 0; i < nrBlocks; i++)
1753         selectorTable[i] = (i & 1)? selectorOdd  + ((i >> 1) << __AHSHIFT)
1754                                   : selectorEven + ((i >> 1) << __AHSHIFT);
1755
1756     /* Move old segment */
1757
1758     if ( segment )
1759     {
1760         /* FIXME: This is somewhat ugly and relies on implementation
1761                   details about 16-bit global memory handles ... */
1762
1763         LPBYTE oldBase = (LPBYTE)GetSelectorBase( segment );
1764         memcpy( base, oldBase, segSize );
1765         GLOBAL_MoveBlock( segment, base, totSize );
1766         HeapFree( SystemHeap, 0, oldBase );
1767     }
1768
1769     return (HANDLE)header;
1770 }
1771
1772 /***********************************************************************
1773  *           Local32_SearchHandle
1774  */
1775 static LPDWORD Local32_SearchHandle( LOCAL32HEADER *header, DWORD addr )
1776 {
1777     LPDWORD handle;
1778
1779     for ( handle = (LPDWORD)((LPBYTE)header + sizeof(LOCAL32HEADER));
1780           handle < (LPDWORD)((LPBYTE)header + header->limit);
1781           handle++)
1782     {
1783         if (*handle == addr)
1784             return handle;
1785     }
1786
1787     return NULL;
1788 }
1789
1790 /***********************************************************************
1791  *           Local32_ToHandle
1792  */
1793 static VOID Local32_ToHandle( LOCAL32HEADER *header, INT16 type,
1794                               DWORD addr, LPDWORD *handle, LPBYTE *ptr )
1795 {
1796     *handle = NULL;
1797     *ptr    = NULL;
1798
1799     switch (type)
1800     {
1801         case -2:    /* 16:16 pointer, no handles */
1802             *ptr    = PTR_SEG_TO_LIN( addr );
1803             *handle = (LPDWORD)*ptr;
1804             break;
1805
1806         case -1:    /* 32-bit offset, no handles */
1807             *ptr    = header->base + addr;
1808             *handle = (LPDWORD)*ptr;
1809             break;
1810
1811         case 0:     /* handle */
1812             if (    addr >= sizeof(LOCAL32HEADER)
1813                  && addr <  header->limit && !(addr & 3)
1814                  && *(LPDWORD)((LPBYTE)header + addr) >= HTABLE_SIZE )
1815             {
1816                 *handle = (LPDWORD)((LPBYTE)header + addr);
1817                 *ptr    = header->base + **handle;
1818             }
1819             break;
1820
1821         case 1:     /* 16:16 pointer */
1822             *ptr    = PTR_SEG_TO_LIN( addr );
1823             *handle = Local32_SearchHandle( header, *ptr - header->base );
1824             break;
1825
1826         case 2:     /* 32-bit offset */
1827             *ptr    = header->base + addr;
1828             *handle = Local32_SearchHandle( header, *ptr - header->base );
1829             break;
1830     }
1831 }
1832
1833 /***********************************************************************
1834  *           Local32_FromHandle
1835  */
1836 static VOID Local32_FromHandle( LOCAL32HEADER *header, INT16 type,
1837                                 DWORD *addr, LPDWORD handle, LPBYTE ptr )
1838 {
1839     switch (type)
1840     {
1841         case -2:    /* 16:16 pointer */
1842         case  1:
1843         {
1844             WORD *selTable = (LPWORD)(header->base + header->selectorTableOffset);
1845             DWORD offset   = (LPBYTE)ptr - header->base;
1846             *addr = MAKELONG( offset & 0x7fff, selTable[offset >> 15] );
1847         }
1848         break;
1849
1850         case -1:    /* 32-bit offset */
1851         case  2:
1852             *addr = ptr - header->base;
1853             break;
1854
1855         case  0:    /* handle */
1856             *addr = (LPBYTE)handle - (LPBYTE)header;
1857             break;
1858     }
1859 }
1860
1861 /***********************************************************************
1862  *           Local32Alloc   (KERNEL.209)
1863  */
1864 DWORD WINAPI Local32Alloc16( HANDLE heap, DWORD size, INT16 type, DWORD flags )
1865 {
1866     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
1867     LPDWORD handle;
1868     LPBYTE ptr;
1869     DWORD addr;
1870
1871     /* Allocate memory */
1872     ptr = HeapAlloc( header->heap,
1873                      (flags & LMEM_MOVEABLE)? HEAP_ZERO_MEMORY : 0, size );
1874     if (!ptr) return 0;
1875
1876
1877     /* Allocate handle if requested */
1878     if (type >= 0)
1879     {
1880         int page, i;
1881
1882         /* Find first page of handle table with free slots */
1883         for (page = 0; page < HTABLE_NPAGES; page++)
1884             if (header->freeListFirst[page] != 0)
1885                 break;
1886         if (page == HTABLE_NPAGES)
1887         {
1888             WARN("Out of handles!\n" );
1889             HeapFree( header->heap, 0, ptr );
1890             return 0;
1891         }
1892
1893         /* If virgin page, initialize it */
1894         if (header->freeListFirst[page] == 0xffff)
1895         {
1896             if ( !VirtualAlloc( (LPBYTE)header + (page << 12),
1897                                 0x1000, MEM_COMMIT, PAGE_READWRITE ) )
1898             {
1899                 WARN("Cannot grow handle table!\n" );
1900                 HeapFree( header->heap, 0, ptr );
1901                 return 0;
1902             }
1903
1904             header->limit += HTABLE_PAGESIZE;
1905
1906             header->freeListFirst[page] = 0;
1907             header->freeListLast[page]  = HTABLE_PAGESIZE - 4;
1908             header->freeListSize[page]  = HTABLE_PAGESIZE / 4;
1909
1910             for (i = 0; i < HTABLE_PAGESIZE; i += 4)
1911                 *(DWORD *)((LPBYTE)header + i) = i+4;
1912
1913             if (page < HTABLE_NPAGES-1)
1914                 header->freeListFirst[page+1] = 0xffff;
1915         }
1916
1917         /* Allocate handle slot from page */
1918         handle = (LPDWORD)((LPBYTE)header + header->freeListFirst[page]);
1919         if (--header->freeListSize[page] == 0)
1920             header->freeListFirst[page] = header->freeListLast[page] = 0;
1921         else
1922             header->freeListFirst[page] = *handle;
1923
1924         /* Store 32-bit offset in handle slot */
1925         *handle = ptr - header->base;
1926     }
1927     else
1928     {
1929         handle = (LPDWORD)ptr;
1930         header->flags |= 1;
1931     }
1932
1933
1934     /* Convert handle to requested output type */
1935     Local32_FromHandle( header, type, &addr, handle, ptr );
1936     return addr;
1937 }
1938
1939 /***********************************************************************
1940  *           Local32ReAlloc   (KERNEL.210)
1941  */
1942 DWORD WINAPI Local32ReAlloc16( HANDLE heap, DWORD addr, INT16 type,
1943                              DWORD size, DWORD flags )
1944 {
1945     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
1946     LPDWORD handle;
1947     LPBYTE ptr;
1948
1949     if (!addr)
1950         return Local32Alloc16( heap, size, type, flags );
1951
1952     /* Retrieve handle and pointer */
1953     Local32_ToHandle( header, type, addr, &handle, &ptr );
1954     if (!handle) return FALSE;
1955
1956     /* Reallocate memory block */
1957     ptr = HeapReAlloc( header->heap,
1958                        (flags & LMEM_MOVEABLE)? HEAP_ZERO_MEMORY : 0,
1959                        ptr, size );
1960     if (!ptr) return 0;
1961
1962     /* Modify handle */
1963     if (type >= 0)
1964         *handle = ptr - header->base;
1965     else
1966         handle = (LPDWORD)ptr;
1967
1968     /* Convert handle to requested output type */
1969     Local32_FromHandle( header, type, &addr, handle, ptr );
1970     return addr;
1971 }
1972
1973 /***********************************************************************
1974  *           Local32Free   (KERNEL.211)
1975  */
1976 BOOL WINAPI Local32Free16( HANDLE heap, DWORD addr, INT16 type )
1977 {
1978     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
1979     LPDWORD handle;
1980     LPBYTE ptr;
1981
1982     /* Retrieve handle and pointer */
1983     Local32_ToHandle( header, type, addr, &handle, &ptr );
1984     if (!handle) return FALSE;
1985
1986     /* Free handle if necessary */
1987     if (type >= 0)
1988     {
1989         int offset = (LPBYTE)handle - (LPBYTE)header;
1990         int page   = offset >> 12;
1991
1992         /* Return handle slot to page free list */
1993         if (header->freeListSize[page]++ == 0)
1994             header->freeListFirst[page] = header->freeListLast[page]  = offset;
1995         else
1996             *(LPDWORD)((LPBYTE)header + header->freeListLast[page]) = offset,
1997             header->freeListLast[page] = offset;
1998
1999         *handle = 0;
2000
2001         /* Shrink handle table when possible */
2002         while (page > 0 && header->freeListSize[page] == HTABLE_PAGESIZE / 4)
2003         {
2004             if ( VirtualFree( (LPBYTE)header +
2005                               (header->limit & ~(HTABLE_PAGESIZE-1)),
2006                               HTABLE_PAGESIZE, MEM_DECOMMIT ) )
2007                 break;
2008
2009             header->limit -= HTABLE_PAGESIZE;
2010             header->freeListFirst[page] = 0xffff;
2011             page--;
2012         }
2013     }
2014
2015     /* Free memory */
2016     return HeapFree( header->heap, 0, ptr );
2017 }
2018
2019 /***********************************************************************
2020  *           Local32Translate   (KERNEL.213)
2021  */
2022 DWORD WINAPI Local32Translate16( HANDLE heap, DWORD addr, INT16 type1, INT16 type2 )
2023 {
2024     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2025     LPDWORD handle;
2026     LPBYTE ptr;
2027
2028     Local32_ToHandle( header, type1, addr, &handle, &ptr );
2029     if (!handle) return 0;
2030
2031     Local32_FromHandle( header, type2, &addr, handle, ptr );
2032     return addr;
2033 }
2034
2035 /***********************************************************************
2036  *           Local32Size   (KERNEL.214)
2037  */
2038 DWORD WINAPI Local32Size16( HANDLE heap, DWORD addr, INT16 type )
2039 {
2040     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2041     LPDWORD handle;
2042     LPBYTE ptr;
2043
2044     Local32_ToHandle( header, type, addr, &handle, &ptr );
2045     if (!handle) return 0;
2046
2047     return HeapSize( header->heap, 0, ptr );
2048 }
2049
2050 /***********************************************************************
2051  *           Local32ValidHandle   (KERNEL.215)
2052  */
2053 BOOL WINAPI Local32ValidHandle16( HANDLE heap, WORD addr )
2054 {
2055     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2056     LPDWORD handle;
2057     LPBYTE ptr;
2058
2059     Local32_ToHandle( header, 0, addr, &handle, &ptr );
2060     return handle != NULL;
2061 }
2062
2063 /***********************************************************************
2064  *           Local32GetSegment   (KERNEL.229)
2065  */
2066 WORD WINAPI Local32GetSegment16( HANDLE heap )
2067 {
2068     LOCAL32HEADER *header = (LOCAL32HEADER *)heap;
2069     return header->segment;
2070 }
2071
2072 /***********************************************************************
2073  *           Local32_GetHeap
2074  */
2075 static LOCAL32HEADER *Local32_GetHeap( HGLOBAL16 handle )
2076 {
2077     WORD selector = GlobalHandleToSel16( handle );
2078     DWORD base  = GetSelectorBase( selector );
2079     DWORD limit = GetSelectorLimit16( selector );
2080
2081     /* Hmmm. This is a somewhat stupid heuristic, but Windows 95 does
2082        it this way ... */
2083
2084     if ( limit > 0x10000 && ((LOCAL32HEADER *)base)->magic == LOCAL32_MAGIC )
2085         return (LOCAL32HEADER *)base;
2086
2087     base  += 0x10000;
2088     limit -= 0x10000;
2089
2090     if ( limit > 0x10000 && ((LOCAL32HEADER *)base)->magic == LOCAL32_MAGIC )
2091         return (LOCAL32HEADER *)base;
2092
2093     return NULL;
2094 }
2095
2096 /***********************************************************************
2097  *           Local32Info   (KERNEL.444)  (TOOLHELP.84)
2098  */
2099 BOOL16 WINAPI Local32Info16( LOCAL32INFO *pLocal32Info, HGLOBAL16 handle )
2100 {
2101     SUBHEAP *heapPtr;
2102     LPBYTE ptr;
2103     int i;
2104
2105     LOCAL32HEADER *header = Local32_GetHeap( handle );
2106     if ( !header ) return FALSE;
2107
2108     if ( !pLocal32Info || pLocal32Info->dwSize < sizeof(LOCAL32INFO) )
2109         return FALSE;
2110
2111     heapPtr = (SUBHEAP *)HEAP_GetPtr( header->heap );
2112     pLocal32Info->dwMemReserved = heapPtr->size;
2113     pLocal32Info->dwMemCommitted = heapPtr->commitSize;
2114     pLocal32Info->dwTotalFree = 0L;
2115     pLocal32Info->dwLargestFreeBlock = 0L;
2116
2117     /* Note: Local32 heaps always have only one subheap! */
2118     ptr = (LPBYTE)heapPtr + heapPtr->headerSize;
2119     while ( ptr < (LPBYTE)heapPtr + heapPtr->size )
2120     {
2121         if (*(DWORD *)ptr & ARENA_FLAG_FREE)
2122         {
2123             ARENA_FREE *pArena = (ARENA_FREE *)ptr;
2124             DWORD size = (pArena->size & ARENA_SIZE_MASK);
2125             ptr += sizeof(*pArena) + size;
2126
2127             pLocal32Info->dwTotalFree += size;
2128             if ( size > pLocal32Info->dwLargestFreeBlock )
2129                 pLocal32Info->dwLargestFreeBlock = size;
2130         }
2131         else
2132         {
2133             ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
2134             DWORD size = (pArena->size & ARENA_SIZE_MASK);
2135             ptr += sizeof(*pArena) + size;
2136         }
2137     }
2138
2139     pLocal32Info->dwcFreeHandles = 0;
2140     for ( i = 0; i < HTABLE_NPAGES; i++ )
2141     {
2142         if ( header->freeListFirst[i] == 0xffff ) break;
2143         pLocal32Info->dwcFreeHandles += header->freeListSize[i];
2144     }
2145     pLocal32Info->dwcFreeHandles += (HTABLE_NPAGES - i) * HTABLE_PAGESIZE/4;
2146
2147     return TRUE;
2148 }
2149
2150 /***********************************************************************
2151  *           Local32First   (KERNEL.445)  (TOOLHELP.85)
2152  */
2153 BOOL16 WINAPI Local32First16( LOCAL32ENTRY *pLocal32Entry, HGLOBAL16 handle )
2154 {
2155     FIXME("(%p, %04X): stub!\n", pLocal32Entry, handle );
2156     return FALSE;
2157 }
2158
2159 /***********************************************************************
2160  *           Local32Next   (KERNEL.446)  (TOOLHELP.86)
2161  */
2162 BOOL16 WINAPI Local32Next16( LOCAL32ENTRY *pLocal32Entry )
2163 {
2164     FIXME("(%p): stub!\n", pLocal32Entry );
2165     return FALSE;
2166 }
2167