~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Wine Cross Reference
wine/dlls/kernel32/local16.c

Version: ~ [ wine-1.0-rc1 ] ~ [ wine-0.9.61 ] ~ [ wine-0.9.60 ] ~ [ wine-0.9.59 ] ~ [ wine-0.9.58 ] ~ [ wine-0.9.57 ] ~ [ wine-0.9.56 ] ~ [ wine-0.9.55 ] ~ [ wine-0.9.54 ] ~ [ wine-0.9.53 ] ~ [ wine-0.9.52 ] ~ [ wine-0.9.51 ] ~ [ wine-0.9.50 ] ~ [ wine-0.9.49 ] ~ [ wine-0.9.48 ] ~ [ wine-0.9.47 ] ~ [ wine-0.9.46 ] ~ [ wine-0.9.45 ] ~ [ wine-0.9.44 ] ~ [ wine-0.9.43 ] ~ [ wine-0.9.42 ] ~ [ wine-0.9.41 ] ~ [ wine-0.9.40 ] ~ [ wine-0.9.39 ] ~ [ wine-0.9.38 ] ~ [ wine-0.9.37 ] ~ [ wine-0.9.36 ] ~ [ wine-0.9.35 ] ~ [ wine-0.9.34 ] ~ [ wine-0.9.33 ] ~ [ wine-0.9.32 ] ~ [ wine-0.9.31 ] ~ [ wine-0.9.30 ] ~ [ wine-0.9.29 ] ~ [ wine-0.9.28 ] ~ [ wine-0.9.27 ] ~ [ wine-0.9.26 ] ~ [ wine-0.9.25 ] ~ [ wine-0.9.24 ] ~ [ wine-0.9.23 ] ~ [ wine-0.9.22 ] ~ [ wine-0.9.21 ] ~ [ wine-0.9.20 ] ~ [ wine-0.9.19 ] ~ [ wine-0.9.18 ] ~ [ wine-0.9.17 ] ~ [ wine-0.9.16 ] ~ [ wine-0.9.15 ] ~ [ wine-0.9.14 ] ~ [ wine-0.9.13 ] ~ [ wine-0.9.12 ] ~ [ wine-0.9.11 ] ~ [ wine-0.9.10 ] ~ [ wine-0.9.9 ] ~ [ wine-0.9.8 ] ~ [ wine-0.9.7 ] ~ [ wine-0.9.6 ] ~ [ wine-0.9.5 ] ~ [ wine-0.9.4 ] ~ [ wine-0.9.3 ] ~ [ wine-0.9.2 ] ~ [ wine-0.9.1 ] ~ [ wine-0.9 ] ~ [ wine20050930 ] ~ [ wine20050830 ] ~ [ wine20050725 ] ~ [ wine20050628 ] ~ [ wine20050524 ] ~ [ wine20050419 ] ~ [ wine20050310 ] ~ [ wine20050211 ] ~ [ wine20050111 ] ~ [ wine20041201 ] ~ [ wine20041019 ] ~ [ wine20040914 ] ~ [ wine20040813 ] ~ [ wine20040716 ] ~ [ wine20040615 ] ~ [ wine20040505 ] ~ [ wine20040408 ] ~ [ wine20040309 ] ~ [ wine20040213 ] ~ [ wine20040121 ] ~ [ wine20031212 ] ~ [ wine20031118 ] ~ [ wine20031016 ] ~ [ wine20030911 ] ~ [ wine20030813 ] ~ [ wine20030709 ] ~ [ wine20030618 ] ~ [ wine20030508 ] ~ [ wine20030408 ] ~ [ wine20030318 ] ~ [ wine20030219 ] ~ [ wine20030115 ] ~ [ wine20021219 ] ~ [ wine20021125 ] ~ [ wine20021031 ] ~ [ wine20021007 ] ~ [ wine20020904 ] ~ [ wine20020804 ] ~ [ wine20020710 ] ~ [ wine20020605 ] ~ [ wine20020509 ] ~ [ wine20020411 ] ~ [ wine20020310 ] ~ [ wine20020228 ] ~ [ wine20011226 ] ~ [ wine20011108 ] ~ [ wine20011004 ] ~ [ wine20010824 ] ~ [ wine20010731 ] ~ [ wine20010629 ] ~ [ wine20010510 ] ~ [ wine20010418 ] ~ [ wine20010326 ] ~ [ wine20010305 ] ~ [ wine20010216 ] ~ [ wine20010112 ] ~ [ wine20001222 ] ~ [ wine20001202 ] ~ [ wine20001026 ] ~ [ wine20001002 ] ~ [ wine20000909 ] ~ [ wine20000821 ] ~ [ wine20000801 ] ~ [ wine20000716 ] ~ [ wine20000326 ] ~ [ wine20000227 ] ~ [ wine20000130 ] ~ [ wine20000109 ] ~

  1 /*
  2  * 16-bit local heap functions
  3  *
  4  * Copyright 1995 Alexandre Julliard
  5  * Copyright 1996 Huw Davies
  6  * Copyright 1998 Ulrich Weigand
  7  *
  8  * This library is free software; you can redistribute it and/or
  9  * modify it under the terms of the GNU Lesser General Public
 10  * License as published by the Free Software Foundation; either
 11  * version 2.1 of the License, or (at your option) any later version.
 12  *
 13  * This library is distributed in the hope that it will be useful,
 14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 16  * Lesser General Public License for more details.
 17  *
 18  * You should have received a copy of the GNU Lesser General Public
 19  * License along with this library; if not, write to the Free Software
 20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 21  */
 22 
 23 /*
 24  * Note:
 25  * All local heap functions need the current DS as first parameter
 26  * when called from the emulation library, so they take one more
 27  * parameter than usual.
 28  */
 29 
 30 #include "config.h"
 31 
 32 #define NONAMELESSUNION
 33 #define NONAMELESSSTRUCT
 34 #include <stdlib.h>
 35 #include <string.h>
 36 #include "wine/winbase16.h"
 37 #include "wownt32.h"
 38 #include "toolhelp.h"
 39 #include "winternl.h"
 40 #include "kernel_private.h"
 41 #include "kernel16_private.h"
 42 #include "wine/debug.h"
 43 
 44 WINE_DEFAULT_DEBUG_CHANNEL(local);
 45 
 46 typedef struct
 47 {
 48 /* Arena header */
 49     WORD prev;          /* Previous arena | arena type */
 50     WORD next;          /* Next arena */
 51 /* Start of the memory block or free-list info */
 52     WORD size;          /* Size of the free block */
 53     WORD free_prev;     /* Previous free block */
 54     WORD free_next;     /* Next free block */
 55 } LOCALARENA;
 56 
 57 #define ARENA_HEADER_SIZE      4
 58 #define ARENA_HEADER( handle) ((handle) - ARENA_HEADER_SIZE)
 59 
 60   /* Arena types (stored in 'prev' field of the arena) */
 61 #define LOCAL_ARENA_FREE       0
 62 #define LOCAL_ARENA_FIXED      1
 63 
 64 /* LocalNotify() msgs */
 65 
 66 #define LN_OUTOFMEM     0
 67 #define LN_MOVE         1
 68 #define LN_DISCARD      2
 69 
 70 /* Layout of a handle entry table
 71  *
 72  * WORD                     count of entries
 73  * LOCALHANDLEENTRY[count]  entries
 74  * WORD                     near ptr to next table
 75  */
 76 typedef struct
 77 {
 78     WORD addr;                /* Address of the MOVEABLE block */
 79     BYTE flags;               /* Flags for this block */
 80     BYTE lock;                /* Lock count */
 81 } LOCALHANDLEENTRY;
 82 
 83 /*
 84  * We make addr = 4n + 2 and set *((WORD *)addr - 1) = &addr like Windows does
 85  * in case something actually relies on this.
 86  * Note that if the architecture does not allow unaligned accesses, we make
 87  * addr = 4n + 4 to avoid returning unaligned pointers from LocalAlloc etc.
 88  *
 89  * An unused handle has lock = flags = 0xff. In windows addr is that of next
 90  * free handle, at the moment in wine we set it to 0.
 91  *
 92  * A discarded block's handle has lock = addr = 0 and flags = 0x40
 93  * (LMEM_DISCARDED >> 8)
 94  */
 95 
 96 #ifdef ALLOW_UNALIGNED_ACCESS
 97 # define MOVEABLE_PREFIX sizeof(HLOCAL16)
 98 #else
 99 # define MOVEABLE_PREFIX sizeof(int)
100 #endif
101 
102 
103 #include "pshpack1.h"
104 
105 typedef struct
106 {
107     WORD check;                 /* 00 Heap checking flag */
108     WORD freeze;                /* 02 Heap frozen flag */
109     WORD items;                 /* 04 Count of items on the heap */
110     WORD first;                 /* 06 First item of the heap */
111     WORD pad1;                  /* 08 Always 0 */
112     WORD last;                  /* 0a Last item of the heap */
113     WORD pad2;                  /* 0c Always 0 */
114     BYTE ncompact;              /* 0e Compactions counter */
115     BYTE dislevel;              /* 0f Discard level */
116     DWORD distotal;             /* 10 Total bytes discarded */
117     WORD htable;                /* 14 Pointer to handle table */
118     WORD hfree;                 /* 16 Pointer to free handle table */
119     WORD hdelta;                /* 18 Delta to expand the handle table */
120     WORD expand;                /* 1a Pointer to expand function (unused) */
121     WORD pstat;                 /* 1c Pointer to status structure (unused) */
122     FARPROC16 notify;           /* 1e Pointer to LocalNotify() function */
123     WORD lock;                  /* 22 Lock count for the heap */
124     WORD extra;                 /* 24 Extra bytes to allocate when expanding */
125     WORD minsize;               /* 26 Minimum size of the heap */
126     WORD magic;                 /* 28 Magic number */
127 } LOCALHEAPINFO;
128 
129 #include "poppack.h"
130 
131 #define LOCAL_HEAP_MAGIC  0x484c  /* 'LH' */
132 
133   /* All local heap allocations are aligned on 4-byte boundaries */
134 #define LALIGN(word)          (((word) + 3) & ~3)
135 
136 #define ARENA_PTR(ptr,arena)       ((LOCALARENA *)((char *)(ptr)+(arena)))
137 #define ARENA_PREV(ptr,arena)      (ARENA_PTR((ptr),(arena))->prev & ~3)
138 #define ARENA_NEXT(ptr,arena)      (ARENA_PTR((ptr),(arena))->next)
139 #define ARENA_FLAGS(ptr,arena)     (ARENA_PTR((ptr),(arena))->prev & 3)
140 
141   /* determine whether the handle belongs to a fixed or a moveable block */
142 #define HANDLE_FIXED(handle) (((handle) & 3) == 0)
143 #define HANDLE_MOVEABLE(handle) (((handle) & 3) == 2)
144 
145 
146 /* 32-bit heap definitions */
147 
148 #define HTABLE_SIZE      0x10000
149 #define HTABLE_PAGESIZE  0x1000
150 #define HTABLE_NPAGES    (HTABLE_SIZE / HTABLE_PAGESIZE)
151 
152 #include "pshpack1.h"
153 typedef struct _LOCAL32HEADER
154 {
155     WORD     freeListFirst[HTABLE_NPAGES];
156     WORD     freeListSize[HTABLE_NPAGES];
157     WORD     freeListLast[HTABLE_NPAGES];
158 
159     DWORD    selectorTableOffset;
160     WORD     selectorTableSize;
161     WORD     selectorDelta;
162 
163     DWORD    segment;
164     LPBYTE   base;
165 
166     DWORD    limit;
167     DWORD    flags;
168 
169     DWORD    magic;
170     HANDLE heap;
171 
172 } LOCAL32HEADER;
173 #include "poppack.h"
174 
175 #define LOCAL32_MAGIC    ((DWORD)('L' | ('H'<<8) | ('3'<<16) | ('2'<<24)))
176 
177 
178 static inline BOOL16 call_notify_func( FARPROC16 proc, WORD msg, HLOCAL16 handle, WORD arg )
179 {
180     DWORD ret;
181     WORD args[3];
182 
183     if (!proc) return FALSE;
184     args[2] = msg;
185     args[1] = handle;
186     args[0] = arg;
187     WOWCallback16Ex( (DWORD)proc, WCB16_PASCAL, sizeof(args), args, &ret );
188     return LOWORD(ret);
189 }
190 
191 
192 /***********************************************************************
193  *           LOCAL_GetHeap
194  *
195  * Return a pointer to the local heap, making sure it exists.
196  */
197 static LOCALHEAPINFO *LOCAL_GetHeap( HANDLE16 ds )
198 {
199     LOCALHEAPINFO *pInfo;
200     INSTANCEDATA *ptr = MapSL( MAKESEGPTR( ds, 0 ));
201     TRACE("Heap at %p, %04x\n", ptr, (ptr != NULL ? ptr->heap : 0xFFFF));
202     if (!ptr || !ptr->heap) return NULL;
203     if (IsBadReadPtr16( (SEGPTR)MAKELONG(ptr->heap,ds), sizeof(LOCALHEAPINFO)))
204     {
205         WARN("Bad pointer\n");
206         return NULL;
207     }
208     pInfo = (LOCALHEAPINFO*)((char*)ptr + ptr->heap);
209     if (pInfo->magic != LOCAL_HEAP_MAGIC)
210     {
211         WARN("Bad magic\n");
212         return NULL;
213     }
214     return pInfo;
215 }
216 
217 
218 /***********************************************************************
219  *           LOCAL_MakeBlockFree
220  *
221  * Make a block free, inserting it in the free-list.
222  * 'block' is the handle of the block arena; 'baseptr' points to
223  * the beginning of the data segment containing the heap.
224  */
225 static void LOCAL_MakeBlockFree( char *baseptr, WORD block )
226 {
227     LOCALARENA *pArena, *pNext;
228     WORD next;
229 
230       /* Mark the block as free */
231 
232     pArena = ARENA_PTR( baseptr, block );
233     pArena->prev = (pArena->prev & ~3) | LOCAL_ARENA_FREE;
234     pArena->size = pArena->next - block;
235 
236       /* Find the next free block (last block is always free) */
237 
238     next = pArena->next;
239     for (;;)
240     {
241         pNext = ARENA_PTR( baseptr, next );
242         if ((pNext->prev & 3) == LOCAL_ARENA_FREE) break;
243         next = pNext->next;
244     }
245 
246     TRACE("%04x, next %04x\n", block, next );
247       /* Insert the free block in the free-list */
248 
249     pArena->free_prev = pNext->free_prev;
250     pArena->free_next = next;
251     ARENA_PTR(baseptr,pNext->free_prev)->free_next = block;
252     pNext->free_prev  = block;
253 }
254 
255 
256 /***********************************************************************
257  *           LOCAL_RemoveFreeBlock
258  *
259  * Remove a block from the free-list.
260  * 'block' is the handle of the block arena; 'baseptr' points to
261  * the beginning of the data segment containing the heap.
262  */
263 static void LOCAL_RemoveFreeBlock( char *baseptr, WORD block )
264 {
265       /* Mark the block as fixed */
266 
267     LOCALARENA *pArena = ARENA_PTR( baseptr, block );
268     pArena->prev = (pArena->prev & ~3) | LOCAL_ARENA_FIXED;
269 
270       /* Remove it from the list */
271 
272     ARENA_PTR(baseptr,pArena->free_prev)->free_next = pArena->free_next;
273     ARENA_PTR(baseptr,pArena->free_next)->free_prev = pArena->free_prev;
274 }
275 
276 
277 /***********************************************************************
278  *           LOCAL_AddBlock
279  *
280  * Insert a new block in the heap.
281  * 'new' is the handle of the new block arena; 'baseptr' points to
282  * the beginning of the data segment containing the heap; 'prev' is
283  * the block before the new one.
284  */
285 static void LOCAL_AddBlock( char *baseptr, WORD prev, WORD new )
286 {
287     LOCALARENA *pPrev = ARENA_PTR( baseptr, prev );
288     LOCALARENA *pNew  = ARENA_PTR( baseptr, new );
289 
290     pNew->prev = (prev & ~3) | LOCAL_ARENA_FIXED;
291     pNew->next = pPrev->next;
292     ARENA_PTR(baseptr,pPrev->next)->prev &= 3;
293     ARENA_PTR(baseptr,pPrev->next)->prev |= new;
294     pPrev->next = new;
295 }
296 
297 
298 /***********************************************************************
299  *           LOCAL_RemoveBlock
300  *
301  * Remove a block from the heap.
302  * 'block' is the handle of the block arena; 'baseptr' points to
303  * the beginning of the data segment containing the heap.
304  */
305 static void LOCAL_RemoveBlock( char *baseptr, WORD block )
306 {
307     LOCALARENA *pArena, *pTmp;
308 
309       /* Remove the block from the free-list */
310 
311     TRACE("\n");
312     pArena = ARENA_PTR( baseptr, block );
313     if ((pArena->prev & 3) == LOCAL_ARENA_FREE)
314         LOCAL_RemoveFreeBlock( baseptr, block );
315 
316       /* If the previous block is free, expand its size */
317 
318     pTmp = ARENA_PTR( baseptr, pArena->prev & ~3 );
319     if ((pTmp->prev & 3) == LOCAL_ARENA_FREE)
320         pTmp->size += pArena->next - block;
321 
322       /* Remove the block from the linked list */
323 
324     pTmp->next = pArena->next;
325     pTmp = ARENA_PTR( baseptr, pArena->next );
326     pTmp->prev = (pTmp->prev & 3) | (pArena->prev & ~3);
327 }
328 
329 
330 /***********************************************************************
331  *           LOCAL_PrintHeap
332  */
333 static void LOCAL_PrintHeap( HANDLE16 ds )
334 {
335     char *ptr;
336     LOCALHEAPINFO *pInfo;
337     WORD arena;
338 
339     /* FIXME - the test should be done when calling the function!
340                plus is not clear that we should print this info
341                only when TRACE_ON is on! */
342     if(!TRACE_ON(local)) return;
343 
344     ptr = MapSL( MAKESEGPTR( ds, 0 ));
345     pInfo = LOCAL_GetHeap( ds );
346 
347     if (!pInfo)
348     {
349         ERR( "Local Heap corrupted!  ds=%04x\n", ds );
350         return;
351     }
352     TRACE( "Local Heap  ds=%04x first=%04x last=%04x items=%d\n",
353              ds, pInfo->first, pInfo->last, pInfo->items );
354 
355     arena = pInfo->first;
356     for (;;)
357     {
358         LOCALARENA *pArena = ARENA_PTR(ptr,arena);
359         TRACE( "  %04x: prev=%04x next=%04x type=%d\n", arena,
360                pArena->prev & ~3, pArena->next, pArena->prev & 3 );
361         if (arena == pInfo->first)
362         {
363             TRACE( "        size=%d free_prev=%04x free_next=%04x\n",
364                      pArena->size, pArena->free_prev, pArena->free_next );
365         }
366         if ((pArena->prev & 3) == LOCAL_ARENA_FREE)
367         {
368             TRACE( "        size=%d free_prev=%04x free_next=%04x\n",
369                      pArena->size, pArena->free_prev, pArena->free_next );
370             if (pArena->next == arena) break;  /* last one */
371             if (ARENA_PTR(ptr,pArena->free_next)->free_prev != arena)
372             {
373                 TRACE( "*** arena->free_next->free_prev != arena\n" );
374                 break;
375             }
376         }
377         if (pArena->next == arena)
378         {
379             TRACE( "*** last block is not marked free\n" );
380             break;
381         }
382         if ((ARENA_PTR(ptr,pArena->next)->prev & ~3) != arena)
383         {
384             TRACE( "*** arena->next->prev != arena (%04x, %04x)\n",
385                      pArena->next, ARENA_PTR(ptr,pArena->next)->prev);
386             break;
387         }
388         arena = pArena->next;
389     }
390 }
391 
392 
393 /***********************************************************************
394  *           LocalInit   (KERNEL.4)
395  */
396 BOOL16 WINAPI LocalInit16( HANDLE16 selector, WORD start, WORD end )
397 {
398     char *ptr;
399     WORD heapInfoArena, freeArena, lastArena;
400     LOCALHEAPINFO *pHeapInfo;
401     LOCALARENA *pArena, *pFirstArena, *pLastArena;
402     BOOL16 ret = FALSE;
403 
404       /* The initial layout of the heap is: */
405       /* - first arena         (FIXED)      */
406       /* - heap info structure (FIXED)      */
407       /* - large free block    (FREE)       */
408       /* - last arena          (FREE)       */
409 
410     TRACE("%04x %04x-%04x\n", selector, start, end);
411     if (!selector) selector = CURRENT_DS;
412 
413     if (TRACE_ON(local))
414     {
415         /* If TRACE_ON(heap) is set, the global heap blocks are */
416         /* cleared before use, so we can test for double initialization. */
417         if (LOCAL_GetHeap(selector))
418         {
419             ERR("Heap %04x initialized twice.\n", selector);
420             LOCAL_PrintHeap(selector);
421         }
422     }
423 
424     if (start == 0)
425     {
426         /* start == 0 means: put the local heap at the end of the segment */
427 
428         DWORD size = GlobalSize16( GlobalHandle16( selector ) );
429         start = (WORD)(size > 0xffff ? 0xffff : size) - 1;
430         if ( end > 0xfffe ) end = 0xfffe;
431         start -= end;
432         end += start;
433     }
434     ptr = MapSL( MAKESEGPTR( selector, 0 ) );
435 
436     start = LALIGN( max( start, sizeof(INSTANCEDATA) ) );
437     heapInfoArena = LALIGN(start + sizeof(LOCALARENA) );
438     freeArena = LALIGN( heapInfoArena + ARENA_HEADER_SIZE
439                         + sizeof(LOCALHEAPINFO) );
440     lastArena = (end - sizeof(LOCALARENA)) & ~3;
441 
442       /* Make sure there's enough space.       */
443 
444     if (freeArena + sizeof(LOCALARENA) >= lastArena) goto done;
445 
446       /* Initialise the first arena */
447 
448     pFirstArena = ARENA_PTR( ptr, start );
449     pFirstArena->prev      = start | LOCAL_ARENA_FIXED;
450     pFirstArena->next      = heapInfoArena;
451     pFirstArena->size      = LALIGN(sizeof(LOCALARENA));
452     pFirstArena->free_prev = start;  /* this one */
453     pFirstArena->free_next = freeArena;
454 
455       /* Initialise the arena of the heap info structure */
456 
457     pArena = ARENA_PTR( ptr, heapInfoArena );
458     pArena->prev = start | LOCAL_ARENA_FIXED;
459     pArena->next = freeArena;
460 
461       /* Initialise the heap info structure */
462 
463     pHeapInfo = (LOCALHEAPINFO *) (ptr + heapInfoArena + ARENA_HEADER_SIZE );
464     memset( pHeapInfo, 0, sizeof(LOCALHEAPINFO) );
465     pHeapInfo->items   = 4;
466     pHeapInfo->first   = start;
467     pHeapInfo->last    = lastArena;
468     pHeapInfo->htable  = 0;
469     pHeapInfo->hdelta  = 0x20;
470     pHeapInfo->extra   = 0x200;
471     pHeapInfo->minsize = lastArena - freeArena;
472     pHeapInfo->magic   = LOCAL_HEAP_MAGIC;
473 
474       /* Initialise the large free block */
475 
476     pArena = ARENA_PTR( ptr, freeArena );
477     pArena->prev      = heapInfoArena | LOCAL_ARENA_FREE;
478     pArena->next      = lastArena;
479     pArena->size      = lastArena - freeArena;
480     pArena->free_prev = start;
481     pArena->free_next = lastArena;
482 
483       /* Initialise the last block */
484 
485     pLastArena = ARENA_PTR( ptr, lastArena );
486     pLastArena->prev      = freeArena | LOCAL_ARENA_FREE;
487     pLastArena->next      = lastArena;  /* this one */
488     pLastArena->size      = LALIGN(sizeof(LOCALARENA));
489     pLastArena->free_prev = freeArena;
490     pLastArena->free_next = lastArena;  /* this one */
491 
492       /* Store the local heap address in the instance data */
493 
494     ((INSTANCEDATA *)ptr)->heap = heapInfoArena + ARENA_HEADER_SIZE;
495     LOCAL_PrintHeap( selector );
496     ret = TRUE;
497 
498  done:
499     CURRENT_STACK16->ecx = ret;  /* must be returned in cx too */
500     return ret;
501 }
502 
503 
504 /***********************************************************************
505  *           LOCAL_GrowHeap
506  */
507 static BOOL16 LOCAL_GrowHeap( HANDLE16 ds )
508 {
509     HANDLE16 hseg;
510     LONG oldsize;
511     LONG end;
512     LOCALHEAPINFO *pHeapInfo;
513     WORD freeArena, lastArena;
514     LOCALARENA *pArena, *pLastArena;
515     char *ptr;
516 
517     hseg = GlobalHandle16( ds );
518     /* maybe mem allocated by Virtual*() ? */
519     if (!hseg) return FALSE;
520 
521     oldsize = GlobalSize16( hseg );
522     /* if nothing can be gained, return */
523     if (oldsize > 0xfff0) return FALSE;
524     hseg = GlobalReAlloc16( hseg, 0x10000, GMEM_FIXED );
525     ptr = MapSL( MAKESEGPTR( ds, 0 ) );
526     pHeapInfo = LOCAL_GetHeap( ds );
527     if (pHeapInfo == NULL) {
528         ERR("Heap not found\n" );
529         return FALSE;
530     }
531     end = GlobalSize16( hseg );
532     lastArena = (end - sizeof(LOCALARENA)) & ~3;
533 
534       /* Update the HeapInfo */
535     pHeapInfo->items++;
536     freeArena = pHeapInfo->last;
537     pHeapInfo->last = lastArena;
538     pHeapInfo->minsize += end - oldsize;
539 
540       /* grow the old last block */
541     pArena = ARENA_PTR( ptr, freeArena );
542     pArena->size      = lastArena - freeArena;
543     pArena->next      = lastArena;
544     pArena->free_next = lastArena;
545 
546       /* Initialise the new last block */
547 
548     pLastArena = ARENA_PTR( ptr, lastArena );
549     pLastArena->prev      = freeArena | LOCAL_ARENA_FREE;
550     pLastArena->next      = lastArena;  /* this one */
551     pLastArena->size      = LALIGN(sizeof(LOCALARENA));
552     pLastArena->free_prev = freeArena;
553     pLastArena->free_next = lastArena;  /* this one */
554 
555     /* If block before freeArena is also free then merge them */
556     if((ARENA_PTR(ptr, (pArena->prev & ~3))->prev & 3) == LOCAL_ARENA_FREE)
557     {
558         LOCAL_RemoveBlock(ptr, freeArena);
559         pHeapInfo->items--;
560     }
561 
562     TRACE("Heap expanded\n" );
563     LOCAL_PrintHeap( ds );
564     return TRUE;
565 }
566 
567 
568 /***********************************************************************
569  *           LOCAL_FreeArena
570  */
571 static HLOCAL16 LOCAL_FreeArena( WORD ds, WORD arena )
572 {
573     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
574     LOCALHEAPINFO *pInfo;
575     LOCALARENA *pArena, *pPrev;
576 
577     TRACE("%04x ds=%04x\n", arena, ds );
578     if (!(pInfo = LOCAL_GetHeap( ds ))) return arena;
579 
580     pArena = ARENA_PTR( ptr, arena );
581     if ((pArena->prev & 3) == LOCAL_ARENA_FREE)
582     {
583         /* shouldn't happen */
584         ERR("Trying to free block %04x twice!\n",
585                  arena );
586         LOCAL_PrintHeap( ds );
587         return arena;
588     }
589 
590       /* Check if we can merge with the previous block */
591 
592     pPrev = ARENA_PTR( ptr, pArena->prev & ~3 );
593     if ((pPrev->prev & 3) == LOCAL_ARENA_FREE)
594     {
595         arena  = pArena->prev & ~3;
596         pArena = pPrev;
597         LOCAL_RemoveBlock( ptr, pPrev->next );
598         pInfo->items--;
599     }
600     else  /* Make a new free block */
601     {
602         LOCAL_MakeBlockFree( ptr, arena );
603     }
604 
605       /* Check if we can merge with the next block */
606 
607     if ((pArena->next == pArena->free_next) &&
608         (pArena->next != pInfo->last))
609     {
610         LOCAL_RemoveBlock( ptr, pArena->next );
611         pInfo->items--;
612     }
613     return 0;
614 }
615 
616 
617 /***********************************************************************
618  *           LOCAL_ShrinkArena
619  *
620  * Shrink an arena by creating a free block at its end if possible.
621  * 'size' includes the arena header, and must be aligned.
622  */
623 static void LOCAL_ShrinkArena( WORD ds, WORD arena, WORD size )
624 {
625     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
626     LOCALARENA *pArena = ARENA_PTR( ptr, arena );
627 
628     if (arena + size + LALIGN(sizeof(LOCALARENA)) < pArena->next)
629     {
630         LOCALHEAPINFO *pInfo = LOCAL_GetHeap( ds );
631         if (!pInfo) return;
632         LOCAL_AddBlock( ptr, arena, arena + size );
633         pInfo->items++;
634         LOCAL_FreeArena( ds, arena + size );
635     }
636 }
637 
638 
639 /***********************************************************************
640  *           LOCAL_GrowArenaDownward
641  *
642  * Grow an arena downward by using the previous arena (must be free).
643  */
644 static void LOCAL_GrowArenaDownward( WORD ds, WORD arena, WORD newsize )
645 {
646     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
647     LOCALHEAPINFO *pInfo;
648     LOCALARENA *pArena = ARENA_PTR( ptr, arena );
649     WORD prevArena = pArena->prev & ~3;
650     LOCALARENA *pPrevArena = ARENA_PTR( ptr, prevArena );
651     WORD offset, size;
652     char *p;
653 
654     if (!(pInfo = LOCAL_GetHeap( ds ))) return;
655     offset = pPrevArena->size;
656     size = pArena->next - arena - ARENA_HEADER_SIZE;
657     LOCAL_RemoveFreeBlock( ptr, prevArena );
658     LOCAL_RemoveBlock( ptr, arena );
659     pInfo->items--;
660     p = (char *)pPrevArena + ARENA_HEADER_SIZE;
661     while (offset < size)
662     {
663         memcpy( p, p + offset, offset );
664         p += offset;
665         size -= offset;
666     }
667     if (size) memcpy( p, p + offset, size );
668     LOCAL_ShrinkArena( ds, prevArena, newsize );
669 }
670 
671 
672 
673 /***********************************************************************
674  *           LOCAL_GrowArenaUpward
675  *
676  * Grow an arena upward by using the next arena (must be free and big
677  * enough). Newsize includes the arena header and must be aligned.
678  */
679 static void LOCAL_GrowArenaUpward( WORD ds, WORD arena, WORD newsize )
680 {
681     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
682     LOCALHEAPINFO *pInfo;
683     LOCALARENA *pArena = ARENA_PTR( ptr, arena );
684     WORD nextArena = pArena->next;
685 
686     if (!(pInfo = LOCAL_GetHeap( ds ))) return;
687     LOCAL_RemoveBlock( ptr, nextArena );
688     pInfo->items--;
689     LOCAL_ShrinkArena( ds, arena, newsize );
690 }
691 
692 
693 /***********************************************************************
694  *           LOCAL_GetFreeSpace
695  */
696 static WORD LOCAL_GetFreeSpace(WORD ds, WORD countdiscard)
697 {
698     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
699     LOCALHEAPINFO *pInfo;
700     LOCALARENA *pArena;
701     WORD arena;
702     WORD freespace = 0;
703 
704     if (!(pInfo = LOCAL_GetHeap( ds )))
705     {
706         ERR("Local heap not found\n" );
707         LOCAL_PrintHeap(ds);
708         return 0;
709     }
710     arena = pInfo->first;
711     pArena = ARENA_PTR( ptr, arena );
712     while (arena != pArena->free_next)
713     {
714         arena = pArena->free_next;
715         pArena = ARENA_PTR( ptr, arena );
716         if (pArena->size >= freespace) freespace = pArena->size;
717     }
718     /* FIXME doesn't yet calculate space that would become free if everything
719        were discarded when countdiscard == 1 */
720     if (freespace < ARENA_HEADER_SIZE) freespace = 0;
721     else freespace -= ARENA_HEADER_SIZE;
722     return freespace;
723 }
724 
725 
726 /***********************************************************************
727  *           LOCAL_Compact
728  */
729 static UINT16 LOCAL_Compact( HANDLE16 ds, UINT16 minfree, UINT16 flags )
730 {
731     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
732     LOCALHEAPINFO *pInfo;
733     LOCALARENA *pArena, *pMoveArena, *pFinalArena;
734     WORD arena, movearena, finalarena, table;
735     WORD count, movesize, size;
736     WORD freespace;
737     LOCALHANDLEENTRY *pEntry;
738 
739     if (!(pInfo = LOCAL_GetHeap( ds )))
740     {
741         ERR("Local heap not found\n" );
742         LOCAL_PrintHeap(ds);
743         return 0;
744     }
745     TRACE("ds = %04x, minfree = %04x, flags = %04x\n",
746                  ds, minfree, flags);
747     freespace = LOCAL_GetFreeSpace(ds, minfree ? 0 : 1);
748     if(freespace >= minfree || (flags & LMEM_NOCOMPACT))
749     {
750         TRACE("Returning %04x.\n", freespace);
751         return freespace;
752     }
753     TRACE("Compacting heap %04x.\n", ds);
754     table = pInfo->htable;
755     while(table)
756     {
757         pEntry = (LOCALHANDLEENTRY *)(ptr + table + sizeof(WORD));
758         for(count = *(WORD *)(ptr + table); count > 0; count--, pEntry++)
759         {
760             if((pEntry->lock == 0) && (pEntry->flags != (LMEM_DISCARDED >> 8)))
761             {
762                 /* OK we can move this one if we want */
763                 TRACE("handle %04x (block %04x) can be moved.\n",
764                              (WORD)((char *)pEntry - ptr), pEntry->addr);
765                 movearena = ARENA_HEADER(pEntry->addr - MOVEABLE_PREFIX);
766                 pMoveArena = ARENA_PTR(ptr, movearena);
767                 movesize = pMoveArena->next - movearena;
768                 arena = pInfo->first;
769                 pArena = ARENA_PTR(ptr, arena);
770                 size = 0xffff;
771                 finalarena = 0;
772                 /* Try to find the smallest arena that will do, */
773                 /* which is below us in memory */
774                 for(;;)
775                 {
776                     arena = pArena->free_next;
777                     pArena = ARENA_PTR(ptr, arena);
778                     if(arena >= movearena)
779                         break;
780                     if(arena == pArena->free_next)
781                         break;
782                     if((pArena->size >= movesize) && (pArena->size < size))
783                     {
784                         size = pArena->size;
785                         finalarena = arena;
786                     }
787                 }
788                 if (finalarena) /* Actually got somewhere to move */
789                 {
790                     TRACE("Moving it to %04x.\n", finalarena);
791                     pFinalArena = ARENA_PTR(ptr, finalarena);
792                     size = pFinalArena->size;
793                     LOCAL_RemoveFreeBlock(ptr, finalarena);
794                     LOCAL_ShrinkArena( ds, finalarena, movesize );
795                     /* Copy the arena to it's new location */
796                     memcpy((char *)pFinalArena + ARENA_HEADER_SIZE,
797                            (char *)pMoveArena + ARENA_HEADER_SIZE,
798                            movesize - ARENA_HEADER_SIZE );
799                     /* Free the old location */
800                     LOCAL_FreeArena(ds, movearena);
801                     call_notify_func(pInfo->notify, LN_MOVE,
802                                      (WORD)((char *)pEntry - ptr), pEntry->addr);
803                     /* Update handle table entry */
804                     pEntry->addr = finalarena + ARENA_HEADER_SIZE + MOVEABLE_PREFIX;
805                 }
806                 else if((ARENA_PTR(ptr, pMoveArena->prev & ~3)->prev & 3)
807                                == LOCAL_ARENA_FREE)
808                 {
809                     /* Previous arena is free (but < movesize)  */
810                     /* so we can 'slide' movearena down into it */
811                     finalarena = pMoveArena->prev & ~3;
812                     LOCAL_GrowArenaDownward( ds, movearena, movesize );
813                     /* Update handle table entry */
814                     pEntry->addr = finalarena + ARENA_HEADER_SIZE + MOVEABLE_PREFIX;
815                 }
816             }
817         }
818         table = *(WORD *)pEntry;
819     }
820     freespace = LOCAL_GetFreeSpace(ds, minfree ? 0 : 1);
821     if(freespace >= minfree || (flags & LMEM_NODISCARD))
822     {
823         TRACE("Returning %04x.\n", freespace);
824         return freespace;
825     }
826 
827     table = pInfo->htable;
828     while(table)
829     {
830         pEntry = (LOCALHANDLEENTRY *)(ptr + table + sizeof(WORD));
831         for(count = *(WORD *)(ptr + table); count > 0; count--, pEntry++)
832         {
833             if(pEntry->addr && pEntry->lock == 0 &&
834              (pEntry->flags & (LMEM_DISCARDABLE >> 8)))
835             {
836                 TRACE("Discarding handle %04x (block %04x).\n",
837                               (char *)pEntry - ptr, pEntry->addr);
838                 LOCAL_FreeArena(ds, ARENA_HEADER(pEntry->addr - MOVEABLE_PREFIX));
839                 call_notify_func(pInfo->notify, LN_DISCARD, (char *)pEntry - ptr, pEntry->flags);
840                 pEntry->addr = 0;
841                 pEntry->flags = (LMEM_DISCARDED >> 8);
842             }
843         }
844         table = *(WORD *)pEntry;
845     }
846     return LOCAL_Compact(ds, 0xffff, LMEM_NODISCARD);
847 }
848 
849 
850 /***********************************************************************
851  *           LOCAL_FindFreeBlock
852  */
853 static HLOCAL16 LOCAL_FindFreeBlock( HANDLE16 ds, WORD size )
854 {
855     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
856     LOCALHEAPINFO *pInfo;
857     LOCALARENA *pArena;
858     WORD arena;
859 
860     if (!(pInfo = LOCAL_GetHeap( ds )))
861     {
862         ERR("Local heap not found\n" );
863         LOCAL_PrintHeap(ds);
864         return 0;
865     }
866 
867     arena = pInfo->first;
868     pArena = ARENA_PTR( ptr, arena );
869     for (;;) {
870         arena = pArena->free_next;
871         pArena = ARENA_PTR( ptr, arena );
872         if (arena == pArena->free_next) break;
873         if (pArena->size >= size) return arena;
874     }
875     TRACE("not enough space\n" );
876     LOCAL_PrintHeap(ds);
877     return 0;
878 }
879 
880 
881 /***********************************************************************
882  *           get_heap_name
883  */
884 static const char *get_heap_name( WORD ds )
885 {
886     HINSTANCE16 inst = LoadLibrary16( "GDI" );
887     if (ds == GlobalHandleToSel16( inst ))
888     {
889         FreeLibrary16( inst );
890         return "GDI";
891     }
892     FreeLibrary16( inst );
893     inst = LoadLibrary16( "USER" );
894     if (ds == GlobalHandleToSel16( inst ))
895     {
896         FreeLibrary16( inst );
897         return "USER";
898     }
899     FreeLibrary16( inst );
900     return "local";
901 }
902 
903 /***********************************************************************
904  *           LOCAL_GetBlock
905  * The segment may get moved around in this function, so all callers
906  * should reset their pointer variables.
907  */
908 static HLOCAL16 LOCAL_GetBlock( HANDLE16 ds, WORD size, WORD flags )
909 {
910     char *ptr = MapSL( MAKESEGPTR( ds, 0 ) );
911     LOCALHEAPINFO *pInfo;
912     LOCALARENA *pArena;
913     WORD arena;
914 
915     if (!(pInfo = LOCAL_GetHeap( ds )))
916     {
917         ERR("Local heap not found\n");
918         LOCAL_PrintHeap(ds);
919         return 0;
920     }
921 
922     size += ARENA_HEADER_SIZE;
923     size = LALIGN( max( size, sizeof(LOCALARENA) ) );
924 
925 #if 0
926 notify_done:
927 #endif
928       /* Find a suitable free block */
929     arena = LOCAL_FindFreeBlock( ds, size );
930     if (arena == 0) {
931         /* no space: try to make some */
932         LOCAL_Compact( ds, size, flags );
933         arena = LOCAL_FindFreeBlock( ds, size );
934     }
935     if (arena == 0) {
936         /* still no space: try to grow the segment */
937         if (!(LOCAL_GrowHeap( ds )))
938         {
939 #if 0
940             /* FIXME: doesn't work correctly yet */
941             if (call_notify_func(pInfo->notify, LN_OUTOFMEM, ds - 20, size)) /* FIXME: "size" correct ? (should indicate bytes needed) */
942                 goto notify_done;
943 #endif
944             ERR( "not enough space in %s heap %04x for %d bytes\n",
945                  get_heap_name(ds), ds, size );
946             return 0;
947         }
948         ptr = MapSL( MAKESEGPTR( ds, 0 ) );
949         pInfo = LOCAL_GetHeap( ds );
950         arena = LOCAL_FindFreeBlock( ds, size );
951     }
952     if (arena == 0) {
953         ERR( "not enough space in %s heap %04x for %d bytes\n",
954              get_heap_name(ds), ds, size );
955 #if 0
956         /* FIXME: "size" correct ? (should indicate bytes needed) */
957         if (call_notify_func(pInfo->notify, LN_OUTOFMEM, ds, size)) goto notify_done;
958 #endif
959         return 0;
960     }
961 
962       /* Make a block out of the free arena */
963     pArena = ARENA_PTR( ptr, arena );
964     TRACE("size = %04x, arena %04x size %04x\n", size, arena, pArena->size );
965     LOCAL_Re