reactos/lib/kjs/src/heap.c

   1 /*
   2  * Dynamic memory allocation.
   3  * Copyright (c) 1998 New Generation Software (NGS) Oy
   4  *
   5  * Author: Markku Rossi <mtr@ngs.fi>
   6  */
   7
   8 /*
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Library General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Library General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Library General Public
  20  * License along with this library; if not, write to the Free
  21  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  22  * MA 02111-1307, USA
  23  */
  24
  25 /*
  26  * $Source: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/kjs/src/heap.c,v $
  27  * $Id$
  28  */
  29
  30 #include "jsint.h"
  31
  32 /*
  33  * Types and definitions.
  34  */
  35
  36 #if SIZEOF_INT == 2
  37 #define BLOCK_SIZE      (63 * 1024)
  38 #else
  39 #define BLOCK_SIZE      (100 * 1024)
  40 #endif
  41
  42 /*
  43  * The size of the minimum block that can be allocated from the heap.
  44  * The block must be big enought to hold one pointer that is used when
  45  * then block is entered to the freelist.
  46  */
  47 #define MIN_ALLOC       (sizeof (void *))
  48
  49 #if JS_MEM_DEBUG
  50 #define MAGIC 0xfe109abe
  51 #endif
  52
  53 /*
  54  * Prototypes for static functions.
  55  */
  56
  57 static inline unsigned int
  58 list (unsigned int size)
  59 {
  60   unsigned int list = 0;
  61   size >>= 3;
  62
  63   while (size > 0)
  64     {
  65       size >>= 1;
  66       list++;
  67     }
  68   if (list >= JS_NUM_HEAP_FREELISTS)
  69     list = JS_NUM_HEAP_FREELISTS - 1;
  70
  71   return list;
  72 }
  73
  74
  75 static inline void
  76 delete_destroyable (JSHeapMemoryBlock *b)
  77 {
  78   JSHeapDestroyable *destroyable
  79     = (JSHeapDestroyable *) ((unsigned char *) b
  80                              + sizeof (JSHeapMemoryBlock));
  81
  82   if (destroyable->destroy)
  83     (*destroyable->destroy) (destroyable);
  84 }
  85
  86
  87 static unsigned long
  88 sweep (JSVirtualMachine *vm)
  89 {
  90   JSHeapBlock *hb;
  91   unsigned long bytes_in_use = 0;
  92   int i;
  93   unsigned int freelist;
  94
  95   for (i = 0; i < JS_NUM_HEAP_FREELISTS; i++)
  96     vm->heap_freelists[i] = NULL;
  97
  98   vm->gc.bytes_free = 0;
  99   vm->gc.bytes_allocated = 0;
 100
 101   for (hb = vm->heap; hb; hb = hb->next)
 102     {
 103       JSHeapMemoryBlock *b, *e, *bnext;
 104
 105       b = (JSHeapMemoryBlock *) ((unsigned char *) hb + sizeof (JSHeapBlock));
 106       e = (JSHeapMemoryBlock *) ((unsigned char *) hb + sizeof (JSHeapBlock)
 107                                  + hb->size);
 108       for (; b < e; b = bnext)
 109         {
 110 #if JS_MEM_DEBUG
 111           assert (b->magic == MAGIC);
 112 #endif
 113           bnext = (JSHeapMemoryBlock *) ((unsigned char *) b
 114                                          + sizeof (JSHeapMemoryBlock)
 115                                          + b->size);
 116
 117           if (b->flag_mark)
 118             {
 119               bytes_in_use += b->size;
 120               b->flag_mark = 0;
 121               vm->gc.bytes_allocated = b->size;
 122             }
 123           else
 124             {
 125               if (b->flag_destroyable)
 126                 delete_destroyable (b);
 127
 128               /* Pack consecutive free blocks to one big block. */
 129               while (bnext < e && bnext->flag_mark == 0)
 130                 {
 131 #if JS_MEM_DEBUG
 132                   assert (bnext->magic == MAGIC);
 133 #endif
 134                   if (bnext->flag_destroyable)
 135                     delete_destroyable (bnext);
 136
 137                   b->size += bnext->size + sizeof (JSHeapMemoryBlock);
 138                   bnext = (JSHeapMemoryBlock *) ((unsigned char *) bnext
 139                                                  + sizeof (JSHeapMemoryBlock)
 140                                                  + bnext->size);
 141                 }
 142
 143               JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b);
 144
 145               /* Link it to the freelist. */
 146               freelist = list (b->size);
 147
 148               ((JSHeapFreelistBlock *) b)->next = vm->heap_freelists[freelist];
 149               vm->heap_freelists[freelist] = b;
 150               vm->gc.bytes_free += b->size;
 151             }
 152         }
 153     }
 154
 155   return bytes_in_use;
 156 }
 157
 158
 159 /*
 160  * Global functions.
 161  */
 162
 163 void *
 164 js_vm_alloc (JSVirtualMachine *vm, unsigned int size)
 165 {
 166   JSHeapMemoryBlock *b, *prev;
 167   unsigned int alloc_size;
 168   JSHeapBlock *hb;
 169   unsigned int to_alloc;
 170   unsigned int freelist;
 171   char buf[512];
 172
 173   /* Round it up to the next pow of two. */
 174   for (alloc_size = MIN_ALLOC; alloc_size < size; alloc_size *= 2)
 175     ;
 176
 177  retry:
 178
 179   /* Take first block from the freelist that is big enough for us. */
 180   for (freelist = list (alloc_size); freelist < JS_NUM_HEAP_FREELISTS;
 181        freelist++)
 182     for (prev = NULL, b = vm->heap_freelists[freelist]; b;
 183          prev = b, b = ((JSHeapFreelistBlock *) b)->next)
 184       if (b->size >= alloc_size)
 185         {
 186           /* Ok, take this one. */
 187           if (prev)
 188             ((JSHeapFreelistBlock *) prev)->next
 189               = ((JSHeapFreelistBlock *) b)->next;
 190           else
 191             vm->heap_freelists[freelist] = ((JSHeapFreelistBlock *) b)->next;
 192
 193           if (b->size > alloc_size + sizeof (JSHeapMemoryBlock) + MIN_ALLOC)
 194             {
 195               JSHeapMemoryBlock *nb;
 196
 197               /* We can split it. */
 198               nb = ((JSHeapMemoryBlock *)
 199                     ((unsigned char *) b
 200                      + sizeof (JSHeapMemoryBlock) + alloc_size));
 201
 202 #if JS_MEM_DEBUG
 203               nb->magic = MAGIC;
 204 #endif
 205               JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (nb);
 206               nb->size = b->size - sizeof (JSHeapMemoryBlock) - alloc_size;
 207
 208               vm->gc.bytes_free -= sizeof (JSHeapMemoryBlock);
 209
 210               freelist = list (nb->size);
 211               ((JSHeapFreelistBlock *) nb)->next
 212                 = vm->heap_freelists[freelist];
 213               vm->heap_freelists[freelist] = nb;
 214
 215               b->size = alloc_size;
 216             }
 217
 218           JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b);
 219           vm->gc.bytes_free -= b->size;
 220           vm->gc.bytes_allocated += b->size;
 221
 222           return (unsigned char *) b + sizeof (JSHeapMemoryBlock);
 223         }
 224
 225   /* Must allocate new blocks to the freelist. */
 226
 227   if (alloc_size > (BLOCK_SIZE
 228                     - sizeof (JSHeapBlock)
 229                     - sizeof (JSHeapMemoryBlock)))
 230     to_alloc = alloc_size + sizeof (JSHeapBlock) + sizeof (JSHeapMemoryBlock);
 231   else
 232     to_alloc = BLOCK_SIZE;
 233
 234   if (vm->verbose > 2)
 235     {
 236       sprintf (buf,
 237                "VM: heap: malloc(%u): needed=%u, size=%lu, free=%lu, allocated=%lu%s",
 238                to_alloc, alloc_size, vm->heap_size, vm->gc.bytes_free,
 239                vm->gc.bytes_allocated,
 240                JS_HOST_LINE_BREAK);
 241       js_iostream_write (vm->s_stderr, buf, strlen (buf));
 242     }
 243
 244   hb = js_malloc (vm, to_alloc);
 245
 246   vm->heap_size += to_alloc;
 247   hb->next = vm->heap;
 248   vm->heap = hb;
 249   hb->size = to_alloc - sizeof (JSHeapBlock);
 250
 251   /* Link it to the freelist. */
 252   b = (JSHeapMemoryBlock *) ((unsigned char *) hb + sizeof (JSHeapBlock));
 253
 254 #if JS_MEM_DEBUG
 255   b->magic = MAGIC;
 256 #endif
 257   JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b);
 258   b->size = hb->size - sizeof (JSHeapMemoryBlock);
 259
 260   freelist = list (b->size);
 261
 262   ((JSHeapFreelistBlock *) b)->next = vm->heap_freelists[freelist];
 263   vm->heap_freelists[freelist] = b;
 264
 265   vm->gc.bytes_free += b->size;
 266
 267   goto retry;
 268
 269   /* NOTRECHED */
 270   return NULL;
 271 }
 272
 273
 274 void *
 275 js_vm_alloc_destroyable (JSVirtualMachine *vm, unsigned int size)
 276 {
 277   unsigned char *bi;
 278   JSHeapMemoryBlock *b;
 279
 280   bi = js_vm_alloc (vm, size);
 281   memset (bi, 0, size);
 282
 283   b = (JSHeapMemoryBlock *) (bi - sizeof (JSHeapMemoryBlock));
 284   b->flag_destroyable = 1;
 285
 286   return bi;
 287 }
 288
 289
 290 void *
 291 js_vm_realloc (JSVirtualMachine *vm, void *ptr, unsigned int new_size)
 292 {
 293   JSHeapMemoryBlock *b;
 294   void *nptr;
 295
 296   if (ptr == NULL)
 297     return js_vm_alloc (vm, new_size);
 298
 299   /* Can be use the old block? */
 300
 301   b = (JSHeapMemoryBlock *) ((unsigned char *) ptr
 302                              - sizeof (JSHeapMemoryBlock));
 303
 304 #if JS_MEM_DEBUG
 305   assert (b->magic == MAGIC);
 306 #endif
 307
 308   if (b->size >= new_size)
 309     /* Yes we can. */
 310     return ptr;
 311
 312   /* No we can't.  Must allocate a new one. */
 313   nptr = js_vm_alloc (vm, new_size);
 314   memcpy (nptr, ptr, b->size < new_size ? b->size : new_size);
 315
 316   js_vm_free (vm, ptr);
 317
 318   return nptr;
 319 }
 320
 321
 322 void
 323 js_vm_free (JSVirtualMachine *vm, void *ptr)
 324 {
 325   JSHeapMemoryBlock *b;
 326   unsigned int freelist;
 327
 328   b = (JSHeapMemoryBlock *) ((unsigned char *) ptr
 329                              - sizeof (JSHeapMemoryBlock));
 330
 331 #if JS_MEM_DEBUG
 332   assert (b->magic == MAGIC);
 333 #endif
 334
 335   freelist = list (b->size);
 336
 337   ((JSHeapFreelistBlock *) b)->next = vm->heap_freelists[freelist];
 338   vm->heap_freelists[freelist] = b;
 339   vm->gc.bytes_free += b->size;
 340
 341   /*
 342    * We could try to compact the heap, but we left it to the garbage
 343    * collection.
 344    */
 345 }
 346
 347
 348 int
 349 js_vm_mark_ptr (void *ptr)
 350 {
 351   JSHeapMemoryBlock *b;
 352
 353   if (ptr == NULL)
 354     return 0;
 355
 356   b = (JSHeapMemoryBlock *) ((unsigned char *) ptr
 357                              - sizeof (JSHeapMemoryBlock));
 358 #if JS_MEM_DEBUG
 359   assert (b->magic == MAGIC);
 360 #endif
 361
 362   if (b->flag_mark)
 363     return 0;
 364
 365   b->flag_mark = 1;
 366
 367   return 1;
 368 }
 369
 370
 371 int
 372 js_vm_is_marked_ptr (void *ptr)
 373 {
 374   JSHeapMemoryBlock *b;
 375
 376   if (ptr == NULL)
 377     return 1;
 378
 379   b = (JSHeapMemoryBlock *) ((unsigned char *) ptr
 380                              - sizeof (JSHeapMemoryBlock));
 381 #if JS_MEM_DEBUG
 382   assert (b->magic == MAGIC);
 383 #endif
 384
 385   if (b->flag_mark)
 386     return 1;
 387
 388   return 0;
 389 }
 390
 391
 392 void
 393 js_vm_mark (JSNode *n)
 394 {
 395   unsigned int i;
 396
 397   switch (n->type)
 398     {
 399     case JS_UNDEFINED:
 400     case JS_NULL:
 401     case JS_BOOLEAN:
 402     case JS_INTEGER:
 403     case JS_FLOAT:
 404     case JS_SYMBOL:
 405     case JS_NAN:
 406     case JS_IPTR:
 407     case JS_ARGS_FIX:
 408       /* Nothing here. */
 409       break;
 410
 411     case JS_STRING:
 412       js_vm_mark_ptr (n->u.vstring);
 413       if (!n->u.vstring->staticp)
 414         js_vm_mark_ptr (n->u.vstring->data);
 415
 416       js_vm_object_mark (n->u.vstring->prototype);
 417       break;
 418
 419     case JS_OBJECT:
 420       js_vm_object_mark (n->u.vobject);
 421       break;
 422
 423     case JS_ARRAY:
 424       if (js_vm_mark_ptr (n->u.varray))
 425         {
 426           js_vm_mark_ptr (n->u.varray->data);
 427
 428           for (i = 0; i < n->u.varray->length; i++)
 429             js_vm_mark (&n->u.varray->data[i]);
 430
 431           js_vm_object_mark (n->u.varray->prototype);
 432         }
 433       break;
 434
 435     case JS_BUILTIN:
 436       if (js_vm_mark_ptr (n->u.vbuiltin))
 437         {
 438           js_vm_mark_ptr (n->u.vbuiltin->info);
 439
 440           js_vm_object_mark (n->u.vbuiltin->info->prototype);
 441           js_vm_object_mark (n->u.vbuiltin->prototype);
 442
 443           if (n->u.vbuiltin->info->mark_proc)
 444             (*n->u.vbuiltin->info->mark_proc) (
 445                                         n->u.vbuiltin->info,
 446                                         n->u.vbuiltin->instance_context);
 447         }
 448       break;
 449
 450     case JS_FUNC:
 451       js_vm_mark_ptr (n->u.vfunction);
 452       js_vm_mark_ptr (n->u.vfunction->implementation);
 453       js_vm_object_mark (n->u.vfunction->prototype);
 454       break;
 455     }
 456 }
 457
 458 #define GC_TIMES 0
 459
 460 void
 461 js_vm_garbage_collect (JSVirtualMachine *vm, JSNode *fp, JSNode *sp)
 462 {
 463   unsigned int i;
 464   unsigned long bytes_in_use;
 465   char buf[512];
 466 #if GC_TIMES
 467   clock_t start_clock;
 468   clock_t after_mark_clock;
 469   clock_t after_sweep_clock;
 470 #endif
 471
 472   if (vm->verbose > 1)
 473     {
 474       sprintf (buf,
 475                "VM: heap: garbage collect: num_consts=%u, num_globals=%u%s",
 476                vm->num_consts, vm->num_globals,
 477                JS_HOST_LINE_BREAK);
 478       js_iostream_write (vm->s_stderr, buf, strlen (buf));
 479     }
 480
 481   vm->gc.count++;
 482
 483   /* Mark */
 484
 485 #if GC_TIMES
 486   start_clock = clock ();
 487 #endif
 488
 489   /* Mark all constants. */
 490   for (i = 0; i < vm->num_consts; i++)
 491     js_vm_mark (&vm->consts[i]);
 492
 493   /* Mark all globals. */
 494   for (i = 0; i < vm->num_globals; i++)
 495     js_vm_mark (&vm->globals[i]);
 496
 497   /* Mark the buitin-infos of the core objects. */
 498   for (i = 0; i <= JS_IPTR; i++)
 499     js_vm_mark_ptr (vm->prim[i]);
 500
 501   /* Mark stack. */
 502
 503   /* STACKFRAME */
 504
 505   /* Use brute force and mark the whole stack. */
 506   for (sp++; sp < vm->stack + vm->stack_size; sp++)
 507     {
 508       if (sp->type == JS_IPTR)
 509         {
 510           /* Handle the stack frames here. */
 511
 512           /* Skip the return address. */
 513           sp++;
 514
 515           /* Possible with-chain. */
 516           if (sp->u.iptr)
 517             {
 518               JSUIntAlign *uip = sp->u.iptr;
 519               JSUIntAlign ui = *uip;
 520               JSNode *wp;
 521
 522               /* Mark the with-chain block. */
 523               js_vm_mark_ptr (uip);
 524
 525               /* Mark the objects in the with-chain. */
 526               wp = (JSNode *) ((unsigned char *) uip + sizeof (JSUIntAlign));
 527
 528               for (i = 0; i < ui; i++)
 529                 js_vm_mark (&wp[i]);
 530
 531             }
 532           sp++;
 533
 534           /* Skip the args_fix. */
 535           sp++;
 536
 537           /*
 538            * And now we point to the old_fp.  We skip it too at the
 539            * for-loop.
 540            */
 541         }
 542       else
 543         /* Mark this stack item. */
 544         js_vm_mark (sp);
 545     }
 546
 547   /* Sweep all blocks and collect free nodes to the freelist. */
 548
 549 #if GC_TIMES
 550   after_mark_clock = clock ();
 551 #endif
 552
 553   bytes_in_use = sweep (vm);
 554
 555 #if GC_TIMES
 556   after_sweep_clock = clock ();
 557 #endif
 558
 559   if (vm->verbose > 1)
 560     {
 561       sprintf (buf, "VM: heap: bytes_in_use=%lu, bytes_free=%lu%s",
 562                bytes_in_use, vm->gc.bytes_free,
 563                JS_HOST_LINE_BREAK);
 564       js_iostream_write (vm->s_stderr, buf, strlen (buf));
 565     }
 566
 567 #if GC_TIMES
 568   if (vm->verbose > 1)
 569     {
 570       sprintf (buf, "VM: heap: mark_time=%.4f, sweep_time=%.4f%s",
 571                (double) (after_mark_clock - start_clock) / CLOCKS_PER_SEC,
 572                (double) (after_sweep_clock - after_mark_clock)
 573                / CLOCKS_PER_SEC,
 574                JS_HOST_LINE_BREAK);
 575       js_iostream_write (vm->s_stderr, buf, strlen (buf));
 576     }
 577 #endif
 578 }
 579
 580
 581 void
 582 js_vm_clear_heap (JSVirtualMachine *vm)
 583 {
 584   /* Just sweep without marking. */
 585   sweep (vm);
 586 }