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