src/st-memory.c

   1 /*
   2  * st-memory.c
   3  *
   4  * Copyright (C) 2008 Vincent Geddes
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to deal
   8  * in the Software without restriction, including without limitation the rights
   9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23 */
  24
  25 #include "st-memory.h"
  26 #include "st-types.h"
  27 #include "st-utils.h"
  28 #include "st-float.h"
  29 #include "st-large-integer.h"
  30 #include "st-object.h"
  31 #include "st-behavior.h"
  32 #include "st-array.h"
  33 #include "st-context.h"
  34 #include "st-method.h"
  35 #include "st-association.h"
  36 #include "st-array.h"
  37 #include "st-system.h"
  38 #include "st-handle.h"
  39
  40 #include <unistd.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <errno.h>
  44 #include <sys/mman.h>
  45 #include <string.h>
  46 #include <time.h>
  47
  48 static inline st_oop    remap_oop  (st_oop ref);
  49 static void      garbage_collect   ();
  50
  51 static void
  52 timer_start (struct timespec *spec)
  53 {
  54     clock_gettime (CLOCK_PROCESS_CPUTIME_ID, spec);
  55 }
  56
  57 static void
  58 timer_stop (struct timespec *spec)
  59 {
  60     struct timespec tmp;
  61     clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &tmp);
  62     st_timespec_difference (spec, &tmp, spec);
  63 }
  64
  65
  66 // RESERVE 1000 MB worth of virtual address space
  67 #define RESERVED_SIZE        (1000 * 1024 * 1024)
  68 #define INITIAL_COMMIT_SIZE  (1 * 1024 * 1024)
  69
  70 #define MARK_STACK_SIZE      (256 * 1024)
  71 #define MARK_STACK_SIZE_OOPS (MARK_STACK_SIZE / sizeof (st_oop))
  72
  73 #define BLOCK_SIZE       256
  74 #define BLOCK_SIZE_OOPS  (BLOCK_SIZE / sizeof (st_oop))
  75
  76 static void
  77 verify (st_oop object)
  78 {
  79     st_assert (st_object_is_mark (ST_OBJECT_MARK (object)));
  80 }
  81
  82 static void
  83 ensure_metadata (void)
  84 {
  85     /* The bit arrays are implemented using bytes as smallest element of storage.
  86      * If there are N oops in the heap, then we need ((N + 7) / 8) bytes
  87      * for a bit array with 32 elements. We need to reserve space for
  88      * two bit arrays (mark, alloc), as well as the offsets array.
  89      */
  90     st_uint   size, bits_size, offsets_size;
  91     st_uchar *metadata_start;
  92
  93     size = memory->end - memory->start;
  94     bits_size    = ((size + 7) / 8);
  95     offsets_size = (size / BLOCK_SIZE_OOPS) * sizeof (st_oop *);
  96
  97     st_free (memory->mark_bits);
  98     st_free (memory->alloc_bits);
  99     st_free (memory->offsets);
 100
 101     memory->mark_bits  = st_malloc (bits_size);
 102     memory->alloc_bits = st_malloc (bits_size);
 103     memory->bits_size  = bits_size;
 104
 105     memory->offsets      = st_malloc (offsets_size);
 106     memory->offsets_size = offsets_size;
 107 }
 108
 109 static void
 110 grow_heap (st_uint min_size_oops)
 111 {
 112     /* we grow the heap by roughly 0.25 or size_oops, whichever is larger */
 113
 114     st_uint  size, grow_size;
 115     st_heap *heap;
 116
 117     heap = memory->heap;
 118     size = heap->p - heap->start;
 119     grow_size = MAX (size / 4, min_size_oops * sizeof (st_oop));
 120
 121     st_heap_grow (heap, grow_size);
 122
 123     memory->start = (st_oop *) heap->start;
 124     memory->end = (st_oop *) heap->p;
 125
 126     ensure_metadata ();
 127 }
 128
 129 st_memory *
 130 st_memory_new (void)
 131 {
 132     st_oop    *ptr;
 133     st_ulong   size_bits;
 134     st_heap   *heap;
 135
 136     heap = st_heap_new (RESERVED_SIZE);
 137     if (!heap)
 138         abort ();
 139
 140     if (!st_heap_grow (heap, INITIAL_COMMIT_SIZE))
 141         abort ();
 142
 143     memory = st_new0 (st_memory);
 144
 145     memory->heap = heap;
 146     memory->start = (st_oop *) heap->start;
 147     memory->end   = (st_oop *) heap->p;
 148     memory->p = memory->start;
 149
 150     memory->roots = ptr_array_new (15);
 151
 152     memory->total_pause_time.tv_sec = 0;
 153     memory->total_pause_time.tv_nsec = 0;
 154     memory->counter = 0;
 155
 156     memory->mark_stack = st_malloc (MARK_STACK_SIZE);
 157     memory->mark_stack_size = MARK_STACK_SIZE;
 158
 159     memory->mark_bits   = NULL;
 160     memory->alloc_bits  = NULL;
 161     memory->offsets     = NULL;
 162
 163     memory->free_context = 0;
 164     memory->free_context_large = 0;
 165
 166     memory->ht = st_identity_hashtable_new ();
 167
 168     ensure_metadata ();
 169
 170     return memory;
 171 }
 172
 173 void
 174 st_memory_destroy (void)
 175 {
 176     st_free (memory);
 177 }
 178
 179 void
 180 st_memory_add_root (st_oop object)
 181 {
 182     ptr_array_append (memory->roots, (st_pointer) object);
 183 }
 184
 185 void
 186 st_memory_remove_root (st_oop object)
 187 {
 188     ptr_array_remove_fast (memory->roots, (st_pointer) object);
 189 }
 190
 191 st_oop
 192 st_memory_allocate (st_uint size)
 193 {
 194     st_oop *chunk;
 195
 196     st_assert (size >= 2);
 197
 198     if (memory->counter > ST_COLLECTION_THRESHOLD)
 199         return 0;
 200     if ((memory->p + size) >= memory->end)
 201         grow_heap (size);
 202
 203     chunk = memory->p;
 204     memory->p += size;
 205     memory->counter += (size * sizeof (st_oop));
 206
 207     return st_tag_pointer (chunk);
 208 }
 209
 210 st_oop
 211 st_memory_allocate_context (bool large)
 212 {
 213     st_oop context;
 214
 215     if (large) {
 216         if (ST_LIKELY (memory->free_context_large)) {
 217             context = memory->free_context_large;
 218             memory->free_context_large = ST_CONTEXT_PART_SENDER (memory->free_context_large);
 219             return context;
 220         }
 221     } else {
 222         if (ST_LIKELY (memory->free_context)) {
 223             context = memory->free_context;
 224             memory->free_context = ST_CONTEXT_PART_SENDER (memory->free_context);
 225             return context;
 226         }
 227     }
 228
 229     context = st_memory_allocate (ST_SIZE_OOPS (struct st_method_context) + (large ? 32 : 12));
 230     if (context == 0) {
 231         st_memory_perform_gc ();
 232         context = st_memory_allocate (ST_SIZE_OOPS (struct st_method_context) + (large ? 32 : 12));
 233         st_assert (context != 0);
 234     }
 235     st_object_initialize_header (context, ST_METHOD_CONTEXT_CLASS);
 236     st_object_set_large_context (context, large);
 237
 238     return context;
 239 }
 240
 241 void
 242 st_memory_recycle_context  (st_oop context)
 243 {
 244     if (st_object_large_context (context)) {
 245         ST_CONTEXT_PART_SENDER (context) = memory->free_context_large;
 246         memory->free_context_large = context;
 247     } else {
 248         ST_CONTEXT_PART_SENDER (context) = memory->free_context;
 249         memory->free_context = context;
 250     }
 251 }
 252
 253 static inline bool
 254 get_bit (st_uchar *bits, st_uint index)
 255 {
 256     return (bits[index >> 3] >> (index & 0x7)) & 1;
 257 }
 258
 259 static inline void
 260 set_bit (st_uchar *bits, st_uint index)
 261 {
 262     bits[index >> 3] |= 1 << (index & 0x7);
 263 }
 264
 265 static inline st_uint
 266 bit_index (st_oop object)
 267 {
 268     return st_detag_pointer (object) - memory->start;
 269 }
 270
 271 static inline bool
 272 ismarked (st_oop object)
 273 {
 274     return get_bit (memory->mark_bits,  bit_index (object));
 275 }
 276
 277 static inline void
 278 set_marked (st_oop object)
 279 {
 280     set_bit (memory->mark_bits,  bit_index (object));
 281 }
 282
 283 static inline bool
 284 get_alloc_bit (st_oop object)
 285 {
 286     return get_bit (memory->alloc_bits,  bit_index (object));
 287 }
 288
 289 static inline void
 290 set_alloc_bit (st_oop object)
 291 {
 292     set_bit (memory->alloc_bits, bit_index (object));
 293 }
 294
 295 static inline st_uint
 296 get_block_index (st_oop *object)
 297 {
 298     return (object - memory->start) / BLOCK_SIZE_OOPS;
 299 }
 300
 301 static st_uint
 302 object_size (st_oop object)
 303 {
 304     switch (st_object_format (object)) {
 305     case ST_FORMAT_OBJECT:
 306         return ST_SIZE_OOPS (struct st_header) + st_object_instance_size (object);
 307     case ST_FORMAT_FLOAT:
 308         return ST_SIZE_OOPS (struct st_float);
 309     case ST_FORMAT_LARGE_INTEGER:
 310         return ST_SIZE_OOPS (struct st_large_integer);
 311     case ST_FORMAT_HANDLE:
 312         return ST_SIZE_OOPS (struct st_handle);
 313     case ST_FORMAT_ARRAY:
 314         return ST_SIZE_OOPS (struct st_arrayed_object) + st_smi_value (st_arrayed_object_size (object));
 315     case ST_FORMAT_BYTE_ARRAY:
 316         return ST_SIZE_OOPS (struct st_arrayed_object) + ST_ROUNDED_UP_OOPS (st_smi_value (st_arrayed_object_size (object)) + 1);
 317     case ST_FORMAT_WORD_ARRAY:
 318         return ST_SIZE_OOPS (struct st_arrayed_object)
 319             + (st_smi_value (st_arrayed_object_size (object)) / (sizeof (st_oop) / sizeof (st_uint)));
 320     case ST_FORMAT_FLOAT_ARRAY:
 321         return ST_SIZE_OOPS (struct st_arrayed_object) + (st_smi_value (st_arrayed_object_size (object)) * ST_SIZE_OOPS (double));
 322     case ST_FORMAT_INTEGER_ARRAY:
 323         /* object format not used yet */
 324         abort ();
 325         break;
 326     case ST_FORMAT_CONTEXT:
 327         return ST_SIZE_OOPS (struct st_header) + st_object_instance_size (object) + (st_object_large_context (object) ? 32 : 12);
 328     }
 329     /* should not reach */
 330     abort ();
 331     return 0;
 332 }
 333
 334 static void
 335 object_contents (st_oop object, st_oop **oops, st_uint *size)
 336 {
 337     switch (st_object_format (object)) {
 338     case ST_FORMAT_OBJECT:
 339         *oops = ST_OBJECT_FIELDS (object);
 340         *size = st_object_instance_size (object);
 341         break;
 342     case ST_FORMAT_ARRAY:
 343         *oops = st_array_elements (object);
 344         *size = st_smi_value (st_arrayed_object_size (object));
 345         break;
 346     case ST_FORMAT_CONTEXT:
 347         *oops = ST_OBJECT_FIELDS (object);
 348         *size = st_object_instance_size (object) + st_smi_value (ST_CONTEXT_PART_SP (object));
 349         break;
 350     case ST_FORMAT_FLOAT:
 351     case ST_FORMAT_LARGE_INTEGER:
 352     case ST_FORMAT_HANDLE:
 353     case ST_FORMAT_BYTE_ARRAY:
 354     case ST_FORMAT_WORD_ARRAY:
 355     case ST_FORMAT_FLOAT_ARRAY:
 356     case ST_FORMAT_INTEGER_ARRAY:
 357         *oops = NULL;
 358         *size = 0;
 359         break;
 360     default:
 361         /* should not reach */
 362         abort ();
 363     }
 364 }
 365
 366 static inline st_uint
 367 compute_ordinal_number (st_memory *memory, st_oop ref)
 368 {
 369     st_uint i, k, ordinal;
 370
 371     ordinal = 0;
 372     k = bit_index (ref);
 373     i = k & ~(BLOCK_SIZE_OOPS - 1);
 374
 375     while (true) {
 376         if (get_bit (memory->mark_bits, i)) {
 377             ordinal++;
 378             if (i == k)
 379                 return ordinal;
 380         }
 381         i++;
 382     }
 383 }
 384
 385 static inline st_oop
 386 remap_oop (st_oop ref)
 387 {
 388     st_uint  b, i = 0, j = 0;
 389     st_uint  ordinal;
 390     st_oop  *offset;
 391
 392     if (!st_object_is_heap (ref) || ref == ST_NIL)
 393         return ref;
 394
 395     ordinal = compute_ordinal_number (memory, ref);
 396     offset  = memory->offsets[get_block_index (st_detag_pointer (ref))];
 397     b = bit_index (st_tag_pointer (offset));
 398
 399     while (true) {
 400         if (get_bit (memory->alloc_bits, b + i)) {
 401             if (++j == ordinal) {
 402                 return st_tag_pointer (offset + i);
 403             }
 404         }
 405         i++;
 406     }
 407
 408     abort ();
 409     return 0;
 410 }
 411
 412 static void
 413 st_memory_remap (void)
 414 {
 415     /* Remaps all object references in the heap */
 416     st_oop *oops, *p;
 417     st_uint size;
 418
 419     p = memory->start;
 420     while (p < memory->p) {
 421         p[1] = remap_oop (p[1]);
 422         object_contents (st_tag_pointer (p), &oops, &size);
 423         for (st_uint i = 0; i < size; i++) {
 424             oops[i] = remap_oop (oops[i]);
 425         }
 426         p += object_size (st_tag_pointer (p));
 427     }
 428 }
 429
 430 static inline void
 431 basic_finalize (st_oop object)
 432 {
 433     if (ST_UNLIKELY (st_object_format (object) == ST_FORMAT_LARGE_INTEGER))
 434         mp_clear (st_large_integer_value (object));
 435 }
 436
 437
 438 static void
 439 st_memory_compact (void)
 440 {
 441     st_oop *p, *from, *to;
 442     st_uint  size;
 443     st_uint block = 0;
 444
 445     p = memory->start;
 446
 447     while (ismarked (st_tag_pointer (p)) && p < memory->p) {
 448         set_alloc_bit (st_tag_pointer (p));
 449         if (block < (get_block_index (p) + 1)) {
 450             block = get_block_index (p);
 451             memory->offsets[block] = p;
 452             block += 1;
 453         }
 454         p += object_size (st_tag_pointer (p));
 455     }
 456     to = p;
 457
 458     while (!ismarked (st_tag_pointer (p)) && p < memory->p) {
 459         basic_finalize (st_tag_pointer (p));
 460         p += object_size (st_tag_pointer (p));
 461     }
 462     from = p;
 463
 464     if (from == to && p >= memory->p)
 465        goto out;
 466
 467     while (from < memory->p) {
 468
 469         if (ismarked (st_tag_pointer (from))) {
 470
 471             if (st_object_is_hashed (st_tag_pointer (from)))
 472                 st_identity_hashtable_rehash_object (memory->ht, st_tag_pointer (from), st_tag_pointer (to));
 473
 474             set_alloc_bit (st_tag_pointer (to));
 475             size = object_size (st_tag_pointer (from));
 476             st_oops_move (to, from, size);
 477
 478             if (block < (get_block_index (from) + 1)) {
 479                 block = get_block_index (from);
 480                 memory->offsets[block] = to;
 481                 block += 1;
 482             }
 483
 484             to   += size;
 485             from += size;
 486         } else {
 487             basic_finalize (st_tag_pointer (from));
 488             if (st_object_is_hashed (st_tag_pointer (from)))
 489                 st_identity_hashtable_remove (memory->ht, st_tag_pointer (from));
 490             from += object_size (st_tag_pointer (from));
 491         }
 492     }
 493
 494 out:
 495
 496     memory->bytes_collected = (memory->p - to) * sizeof (st_oop);
 497     memory->bytes_allocated -= memory->bytes_collected;
 498     memory->p = to;
 499 }
 500
 501 static st_uint
 502 grow_marking_stack (void)
 503 {
 504     memory->mark_stack_size *= 2;
 505     memory->mark_stack = st_realloc (memory->mark_stack, memory->mark_stack_size);
 506
 507     return memory->mark_stack_size / sizeof (st_oop);
 508 }
 509
 510 static void
 511 st_memory_mark (void)
 512 {
 513     st_oop   object;
 514     st_oop  *oops, *stack;
 515     st_uint  size, stack_size, sp;
 516
 517     sp = 0;
 518     stack = memory->mark_stack;
 519     stack_size = memory->mark_stack_size / sizeof (st_oop);
 520
 521     for (st_uint i = 0; i < memory->roots->length; i++)
 522         stack[sp++] = (st_oop) ptr_array_get_index (memory->roots, i);
 523     stack[sp++] = __machine.context;
 524
 525     while (sp > 0) {
 526         object = stack[--sp];
 527         if (!st_object_is_heap (object) || ismarked (object))
 528             continue;
 529
 530         set_marked (object);
 531         if (ST_UNLIKELY (sp >= stack_size)) {
 532             stack_size = grow_marking_stack ();
 533             stack = memory->mark_stack;
 534             st_log ("gc", "increased size of marking stack");
 535         }
 536         stack[sp++] = ST_OBJECT_CLASS (object);
 537         object_contents (object, &oops, &size);
 538         for (st_uint i = 0; i < size; i++) {
 539             if (ST_UNLIKELY (sp >= stack_size)) {
 540                 stack_size = grow_marking_stack ();
 541                 stack = memory->mark_stack;
 542                 st_log ("gc", "increased size of marking stack");
 543             }
 544             if (oops[i] != ST_NIL) {
 545                 stack[sp++] = oops[i];
 546             }
 547         }
 548     }
 549 }
 550
 551 static void
 552 remap_machine (struct st_machine *machine)
 553 {
 554     st_oop context, home;
 555
 556     context = remap_oop (machine->context);
 557     if (ST_OBJECT_CLASS (context) == ST_BLOCK_CONTEXT_CLASS) {
 558         home = ST_BLOCK_CONTEXT_HOME (context);
 559         machine->method   = ST_METHOD_CONTEXT_METHOD (home);
 560         machine->receiver = ST_METHOD_CONTEXT_RECEIVER (home);
 561         machine->temps    = ST_METHOD_CONTEXT_STACK (home);
 562         machine->stack    = ST_BLOCK_CONTEXT_STACK (context);
 563     } else {
 564         machine->method   = ST_METHOD_CONTEXT_METHOD (context);
 565         machine->receiver = ST_METHOD_CONTEXT_RECEIVER (context);
 566         machine->temps    = ST_METHOD_CONTEXT_STACK (context);
 567         machine->stack    = ST_METHOD_CONTEXT_STACK (context);
 568     }
 569
 570     machine->context  = context;
 571     machine->bytecode = st_method_bytecode_bytes (machine->method);
 572     machine->message_receiver = remap_oop (machine->message_receiver);
 573     machine->message_selector = remap_oop (machine->message_selector);
 574     machine->new_method = remap_oop (machine->new_method);
 575 }
 576
 577 static void
 578 remap_globals (void)
 579 {
 580     st_uint i;
 581
 582     for (i = 0; i < ST_N_ELEMENTS (__machine.globals); i++)
 583         __machine.globals[i] = remap_oop (__machine.globals[i]);
 584
 585     for (i = 0; i < ST_N_ELEMENTS (__machine.selectors); i++)
 586         __machine.selectors[i] = remap_oop (__machine.selectors[i]);
 587
 588     for (i = 0; i < memory->roots->length; i++) {
 589         ptr_array_set_index (memory->roots, i,
 590                              (st_pointer) remap_oop ((st_oop) ptr_array_get_index (memory->roots, i)));
 591     }
 592 }
 593
 594 static void
 595 clear_metadata (void)
 596 {
 597     memset (memory->mark_bits, 0, memory->bits_size);
 598     memset (memory->alloc_bits, 0, memory->bits_size);
 599     memset (memory->offsets, 0, memory->offsets_size);
 600 }
 601
 602
 603 void
 604 st_memory_perform_gc (void)
 605 {
 606     garbage_collect ();
 607 }
 608
 609 static void
 610 garbage_collect (void)
 611 {
 612     double times[3];
 613     struct timespec tm;
 614
 615     /* clear context pool */
 616     memory->free_context = 0;
 617     memory->free_context_large = 0;
 618
 619     memory->bytes_allocated += memory->counter;
 620
 621     clear_metadata ();
 622
 623     /* marking */
 624     timer_start (&tm);
 625     st_memory_mark ();
 626     timer_stop (&tm);
 627
 628     times[0] = st_timespec_to_double_seconds (&tm);
 629     st_timespec_add (&memory->total_pause_time, &tm, &memory->total_pause_time);
 630
 631     /* compaction */
 632     timer_start (&tm);
 633     st_memory_compact ();
 634     timer_stop (&tm);
 635
 636     times[1] = st_timespec_to_double_seconds (&tm);
 637     st_timespec_add (&memory->total_pause_time, &tm, &memory->total_pause_time);
 638
 639     /* remapping */
 640     timer_start (&tm);
 641     st_memory_remap ();
 642     remap_globals ();
 643     remap_machine (&__machine);
 644     timer_stop (&tm);
 645
 646     times[2] = st_timespec_to_double_seconds (&tm);
 647     st_timespec_add (&memory->total_pause_time, &tm, &memory->total_pause_time);
 648
 649     st_machine_clear_caches (&__machine);
 650     memory->counter = 0;
 651
 652     st_log ("gc", "\n"
 653             "collected:       %uK\n"
 654             "heapSize:        %uK\n"
 655             "marking time:    %.6fs\n"
 656             "compaction time: %.6fs\n"
 657             "remapping time:  %.6fs\n",
 658             memory->bytes_collected / 1024,
 659             (memory->bytes_collected + memory->bytes_allocated) / 1024,
 660             times[0], times[1], times[2]);
 661 }
 662
 663 st_oop
 664 st_memory_remap_reference (st_oop reference)
 665 {
 666     return remap_oop (reference);
 667 }