gc.c

   1 /**********************************************************************
   2
   3   gc.c -
   4
   5   $Author$
   6   created at: Tue Oct  5 09:44:46 JST 1993
   7
   8   Copyright (C) 1993-2007 Yukihiro Matsumoto
   9   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  10   Copyright (C) 2000  Information-technology Promotion Agency, Japan
  11
  12 **********************************************************************/
  13
  14 #include "ruby/ruby.h"
  15 #include "ruby/signal.h"
  16 #include "ruby/st.h"
  17 #include "ruby/node.h"
  18 #include "ruby/re.h"
  19 #include "ruby/io.h"
  20 #include "ruby/util.h"
  21 #include "eval_intern.h"
  22 #include "vm_core.h"
  23 #include "gc.h"
  24 #include <stdio.h>
  25 #include <setjmp.h>
  26 #include <sys/types.h>
  27
  28 #ifdef HAVE_SYS_TIME_H
  29 #include <sys/time.h>
  30 #endif
  31
  32 #ifdef HAVE_SYS_RESOURCE_H
  33 #include <sys/resource.h>
  34 #endif
  35
  36 #if defined _WIN32 || defined __CYGWIN__
  37 #include <windows.h>
  38 #endif
  39
  40 #ifdef HAVE_VALGRIND_MEMCHECK_H
  41 # include <valgrind/memcheck.h>
  42 # ifndef VALGRIND_MAKE_MEM_DEFINED
  43 #  define VALGRIND_MAKE_MEM_DEFINED(p, n) VALGRIND_MAKE_READABLE(p, n)
  44 # endif
  45 # ifndef VALGRIND_MAKE_MEM_UNDEFINED
  46 #  define VALGRIND_MAKE_MEM_UNDEFINED(p, n) VALGRIND_MAKE_WRITABLE(p, n)
  47 # endif
  48 #else
  49 # define VALGRIND_MAKE_MEM_DEFINED(p, n) /* empty */
  50 # define VALGRIND_MAKE_MEM_UNDEFINED(p, n) /* empty */
  51 #endif
  52
  53 int rb_io_fptr_finalize(struct rb_io_t*);
  54
  55 #define rb_setjmp(env) RUBY_SETJMP(env)
  56 #define rb_jmp_buf rb_jmpbuf_t
  57
  58 /* Make alloca work the best possible way.  */
  59 #ifdef __GNUC__
  60 # ifndef atarist
  61 #  ifndef alloca
  62 #   define alloca __builtin_alloca
  63 #  endif
  64 # endif /* atarist */
  65 #else
  66 # ifdef HAVE_ALLOCA_H
  67 #  include <alloca.h>
  68 # else
  69 #  ifdef _AIX
  70  #pragma alloca
  71 #  else
  72 #   ifndef alloca /* predefined by HP cc +Olibcalls */
  73 void *alloca ();
  74 #   endif
  75 #  endif /* AIX */
  76 # endif /* HAVE_ALLOCA_H */
  77 #endif /* __GNUC__ */
  78
  79 #ifndef GC_MALLOC_LIMIT
  80 #if defined(MSDOS) || defined(__human68k__)
  81 #define GC_MALLOC_LIMIT 200000
  82 #else
  83 #define GC_MALLOC_LIMIT 8000000
  84 #endif
  85 #endif
  86
  87 #define nomem_error GET_VM()->special_exceptions[ruby_error_nomemory]
  88
  89 #define MARK_STACK_MAX 1024
  90
  91 int ruby_gc_debug_indent = 0;
  92
  93 #undef GC_DEBUG
  94
  95 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
  96 #pragma pack(push, 1) /* magic for reducing sizeof(RVALUE): 24 -> 20 */
  97 #endif
  98
  99 typedef struct RVALUE {
 100     union {
 101         struct {
 102             VALUE flags;                /* always 0 for freed obj */
 103             struct RVALUE *next;
 104         } free;
 105         struct RBasic  basic;
 106         struct RObject object;
 107         struct RClass  klass;
 108         struct RFloat  flonum;
 109         struct RString string;
 110         struct RArray  array;
 111         struct RRegexp regexp;
 112         struct RHash   hash;
 113         struct RData   data;
 114         struct RStruct rstruct;
 115         struct RBignum bignum;
 116         struct RFile   file;
 117         struct RNode   node;
 118         struct RMatch  match;
 119         struct RRational rational;
 120         struct RComplex complex;
 121     } as;
 122 #ifdef GC_DEBUG
 123     char *file;
 124     int   line;
 125 #endif
 126 } RVALUE;
 127
 128 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
 129 #pragma pack(pop)
 130 #endif
 131
 132 struct heaps_slot {
 133     void *membase;
 134     RVALUE *slot;
 135     int limit;
 136 };
 137
 138 #define HEAP_MIN_SLOTS 10000
 139 #define FREE_MIN  4096
 140
 141 struct gc_list {
 142     VALUE *varptr;
 143     struct gc_list *next;
 144 };
 145
 146 #define CALC_EXACT_MALLOC_SIZE 0
 147
 148 typedef struct rb_objspace {
 149     struct {
 150         size_t limit;
 151         size_t increase;
 152 #if CALC_EXACT_MALLOC_SIZE
 153         size_t allocated_size;
 154         size_t allocations;
 155 #endif
 156     } malloc_params;
 157     struct {
 158         size_t increment;
 159         struct heaps_slot *ptr;
 160         size_t length;
 161         size_t used;
 162         RVALUE *freelist;
 163         RVALUE *range[2];
 164         RVALUE *freed;
 165     } heap;
 166     struct {
 167         int dont_gc;
 168         int during_gc;
 169     } flags;
 170     struct {
 171         st_table *table;
 172         RVALUE *deferred;
 173     } final;
 174     struct {
 175         VALUE buffer[MARK_STACK_MAX];
 176         VALUE *ptr;
 177         int overflow;
 178     } markstack;
 179     struct gc_list *global_list;
 180     unsigned int count;
 181     int gc_stress;
 182 } rb_objspace_t;
 183
 184 #if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
 185 #define rb_objspace (*GET_VM()->objspace)
 186 static int ruby_initial_gc_stress = 0;
 187 int *ruby_initial_gc_stress_ptr = &ruby_initial_gc_stress;
 188 #else
 189 static rb_objspace_t rb_objspace = {{GC_MALLOC_LIMIT}, {HEAP_MIN_SLOTS}};
 190 int *ruby_initial_gc_stress_ptr = &rb_objspace.gc_stress;
 191 #endif
 192 #define malloc_limit            objspace->malloc_params.limit
 193 #define malloc_increase         objspace->malloc_params.increase
 194 #define heap_slots              objspace->heap.slots
 195 #define heaps                   objspace->heap.ptr
 196 #define heaps_length            objspace->heap.length
 197 #define heaps_used              objspace->heap.used
 198 #define freelist                objspace->heap.freelist
 199 #define lomem                   objspace->heap.range[0]
 200 #define himem                   objspace->heap.range[1]
 201 #define heaps_inc               objspace->heap.increment
 202 #define heaps_freed             objspace->heap.freed
 203 #define dont_gc                 objspace->flags.dont_gc
 204 #define during_gc               objspace->flags.during_gc
 205 #define finalizer_table         objspace->final.table
 206 #define deferred_final_list     objspace->final.deferred
 207 #define mark_stack              objspace->markstack.buffer
 208 #define mark_stack_ptr          objspace->markstack.ptr
 209 #define mark_stack_overflow     objspace->markstack.overflow
 210 #define global_List             objspace->global_list
 211 #define ruby_gc_stress          objspace->gc_stress
 212
 213 #define need_call_final         (finalizer_table && finalizer_table->num_entries)
 214
 215 #if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
 216 rb_objspace_t *
 217 rb_objspace_alloc(void)
 218 {
 219     rb_objspace_t *objspace = malloc(sizeof(rb_objspace_t));
 220     memset(objspace, 0, sizeof(*objspace));
 221     malloc_limit = GC_MALLOC_LIMIT;
 222     ruby_gc_stress = ruby_initial_gc_stress;
 223
 224     return objspace;
 225 }
 226 #endif
 227
 228 /* tiny heap size */
 229 /* 32KB */
 230 /*#define HEAP_SIZE 0x8000 */
 231 /* 128KB */
 232 /*#define HEAP_SIZE 0x20000 */
 233 /* 64KB */
 234 /*#define HEAP_SIZE 0x10000 */
 235 /* 16KB */
 236 #define HEAP_SIZE 0x4000
 237 /* 8KB */
 238 /*#define HEAP_SIZE 0x2000 */
 239 /* 4KB */
 240 /*#define HEAP_SIZE 0x1000 */
 241 /* 2KB */
 242 /*#define HEAP_SIZE 0x800 */
 243
 244 #define HEAP_OBJ_LIMIT (HEAP_SIZE / sizeof(struct RVALUE))
 245
 246 extern st_table *rb_class_tbl;
 247
 248 int ruby_disable_gc_stress = 0;
 249
 250 static void run_final(rb_objspace_t *objspace, VALUE obj);
 251 static int garbage_collect(rb_objspace_t *objspace);
 252
 253 void
 254 rb_global_variable(VALUE *var)
 255 {
 256     rb_gc_register_address(var);
 257 }
 258
 259 void
 260 rb_memerror(void)
 261 {
 262     rb_thread_t *th = GET_THREAD();
 263     if (!nomem_error ||
 264         (rb_thread_raised_p(th, RAISED_NOMEMORY) && rb_safe_level() < 4)) {
 265         fprintf(stderr, "[FATAL] failed to allocate memory\n");
 266         exit(EXIT_FAILURE);
 267     }
 268     if (rb_thread_raised_p(th, RAISED_NOMEMORY)) {
 269         rb_thread_raised_clear(th);
 270         GET_THREAD()->errinfo = nomem_error;
 271         JUMP_TAG(TAG_RAISE);
 272     }
 273     rb_thread_raised_set(th, RAISED_NOMEMORY);
 274     rb_exc_raise(nomem_error);
 275 }
 276
 277 /*
 278  *  call-seq:
 279  *    GC.stress                 => true or false
 280  *
 281  *  returns current status of GC stress mode.
 282  */
 283
 284 static VALUE
 285 gc_stress_get(VALUE self)
 286 {
 287     rb_objspace_t *objspace = &rb_objspace;
 288     return ruby_gc_stress ? Qtrue : Qfalse;
 289 }
 290
 291 /*
 292  *  call-seq:
 293  *    GC.stress = bool          => bool
 294  *
 295  *  updates GC stress mode.
 296  *
 297  *  When GC.stress = true, GC is invoked for all GC opportunity:
 298  *  all memory and object allocation.
 299  *
 300  *  Since it makes Ruby very slow, it is only for debugging.
 301  */
 302
 303 static VALUE
 304 gc_stress_set(VALUE self, VALUE bool)
 305 {
 306     rb_objspace_t *objspace = &rb_objspace;
 307     rb_secure(2);
 308     ruby_gc_stress = RTEST(bool);
 309     return bool;
 310 }
 311
 312 static void *
 313 vm_xmalloc(rb_objspace_t *objspace, size_t size)
 314 {
 315     void *mem;
 316
 317     if (size < 0) {
 318         rb_raise(rb_eNoMemError, "negative allocation size (or too big)");
 319     }
 320     if (size == 0) size = 1;
 321
 322 #if CALC_EXACT_MALLOC_SIZE
 323     size += sizeof(size_t);
 324 #endif
 325
 326     if ((ruby_gc_stress && !ruby_disable_gc_stress) ||
 327         (malloc_increase+size) > malloc_limit) {
 328         garbage_collect(objspace);
 329     }
 330     RUBY_CRITICAL(mem = malloc(size));
 331     if (!mem) {
 332         if (garbage_collect(objspace)) {
 333             RUBY_CRITICAL(mem = malloc(size));
 334         }
 335         if (!mem) {
 336             rb_memerror();
 337         }
 338     }
 339     malloc_increase += size;
 340
 341 #if CALC_EXACT_MALLOC_SIZE
 342     objspace->malloc_params.allocated_size += size;
 343     objspace->malloc_params.allocations++;
 344     ((size_t *)mem)[0] = size;
 345     mem = (size_t *)mem + 1;
 346 #endif
 347
 348     return mem;
 349 }
 350
 351 static void *
 352 vm_xrealloc(rb_objspace_t *objspace, void *ptr, size_t size)
 353 {
 354     void *mem;
 355
 356     if (size < 0) {
 357         rb_raise(rb_eArgError, "negative re-allocation size");
 358     }
 359     if (!ptr) return ruby_xmalloc(size);
 360     if (size == 0) size = 1;
 361     if (ruby_gc_stress && !ruby_disable_gc_stress) garbage_collect(objspace);
 362
 363 #if CALC_EXACT_MALLOC_SIZE
 364     size += sizeof(size_t);
 365     objspace->malloc_params.allocated_size -= size;
 366     ptr = (size_t *)ptr - 1;
 367 #endif
 368
 369     RUBY_CRITICAL(mem = realloc(ptr, size));
 370     if (!mem) {
 371         if (garbage_collect(objspace)) {
 372             RUBY_CRITICAL(mem = realloc(ptr, size));
 373         }
 374         if (!mem) {
 375             rb_memerror();
 376         }
 377     }
 378     malloc_increase += size;
 379
 380 #if CALC_EXACT_MALLOC_SIZE
 381     objspace->malloc_params.allocated_size += size;
 382     ((size_t *)mem)[0] = size;
 383     mem = (size_t *)mem + 1;
 384 #endif
 385
 386     return mem;
 387 }
 388
 389 static void
 390 vm_xfree(rb_objspace_t *objspace, void *ptr)
 391 {
 392 #if CALC_EXACT_MALLOC_SIZE
 393     size_t size;
 394     ptr = ((size_t *)ptr) - 1;
 395     size = ((size_t*)ptr)[0];
 396     objspace->malloc_params.allocated_size -= size;
 397     objspace->malloc_params.allocations--;
 398 #endif
 399
 400     RUBY_CRITICAL(free(ptr));
 401 }
 402
 403 void *
 404 ruby_xmalloc(size_t size)
 405 {
 406     return vm_xmalloc(&rb_objspace, size);
 407 }
 408
 409 void *
 410 ruby_xmalloc2(size_t n, size_t size)
 411 {
 412     size_t len = size * n;
 413     if (n != 0 && size != len / n) {
 414         rb_raise(rb_eArgError, "malloc: possible integer overflow");
 415     }
 416     return vm_xmalloc(&rb_objspace, len);
 417 }
 418
 419 void *
 420 ruby_xcalloc(size_t n, size_t size)
 421 {
 422     void *mem = ruby_xmalloc2(n, size);
 423     memset(mem, 0, n * size);
 424
 425     return mem;
 426 }
 427
 428 void *
 429 ruby_xrealloc(void *ptr, size_t size)
 430 {
 431     return vm_xrealloc(&rb_objspace, ptr, size);
 432 }
 433
 434 void *
 435 ruby_xrealloc2(void *ptr, size_t n, size_t size)
 436 {
 437     size_t len = size * n;
 438     if (n != 0 && size != len / n) {
 439         rb_raise(rb_eArgError, "realloc: possible integer overflow");
 440     }
 441     return ruby_xrealloc(ptr, len);
 442 }
 443
 444 void
 445 ruby_xfree(void *x)
 446 {
 447     if (x)
 448       vm_xfree(&rb_objspace, x);
 449 }
 450
 451
 452 /*
 453  *  call-seq:
 454  *     GC.enable    => true or false
 455  *
 456  *  Enables garbage collection, returning <code>true</code> if garbage
 457  *  collection was previously disabled.
 458  *
 459  *     GC.disable   #=> false
 460  *     GC.enable    #=> true
 461  *     GC.enable    #=> false
 462  *
 463  */
 464
 465 VALUE
 466 rb_gc_enable(void)
 467 {
 468     rb_objspace_t *objspace = &rb_objspace;
 469     int old = dont_gc;
 470
 471     dont_gc = Qfalse;
 472     return old;
 473 }
 474
 475 /*
 476  *  call-seq:
 477  *     GC.disable    => true or false
 478  *
 479  *  Disables garbage collection, returning <code>true</code> if garbage
 480  *  collection was already disabled.
 481  *
 482  *     GC.disable   #=> false
 483  *     GC.disable   #=> true
 484  *
 485  */
 486
 487 VALUE
 488 rb_gc_disable(void)
 489 {
 490     rb_objspace_t *objspace = &rb_objspace;
 491     int old = dont_gc;
 492
 493     dont_gc = Qtrue;
 494     return old;
 495 }
 496
 497 VALUE rb_mGC;
 498
 499 void
 500 rb_register_mark_object(VALUE obj)
 501 {
 502     VALUE ary = GET_THREAD()->vm->mark_object_ary;
 503     rb_ary_push(ary, obj);
 504 }
 505
 506 void
 507 rb_gc_register_address(VALUE *addr)
 508 {
 509     rb_objspace_t *objspace = &rb_objspace;
 510     struct gc_list *tmp;
 511
 512     tmp = ALLOC(struct gc_list);
 513     tmp->next = global_List;
 514     tmp->varptr = addr;
 515     global_List = tmp;
 516 }
 517
 518 void
 519 rb_gc_unregister_address(VALUE *addr)
 520 {
 521     rb_objspace_t *objspace = &rb_objspace;
 522     struct gc_list *tmp = global_List;
 523
 524     if (tmp->varptr == addr) {
 525         global_List = tmp->next;
 526         xfree(tmp);
 527         return;
 528     }
 529     while (tmp->next) {
 530         if (tmp->next->varptr == addr) {
 531             struct gc_list *t = tmp->next;
 532
 533             tmp->next = tmp->next->next;
 534             xfree(t);
 535             break;
 536         }
 537         tmp = tmp->next;
 538     }
 539 }
 540
 541
 542 static void
 543 allocate_heaps(rb_objspace_t *objspace, size_t next_heaps_length)
 544 {
 545     struct heaps_slot *p;
 546     size_t size;
 547
 548     size = next_heaps_length*sizeof(struct heaps_slot);
 549     RUBY_CRITICAL(
 550                   if (heaps_used > 0) {
 551                       p = (struct heaps_slot *)realloc(heaps, size);
 552                       if (p) heaps = p;
 553                   }
 554                   else {
 555                       p = heaps = (struct heaps_slot *)malloc(size);
 556                   }
 557                   );
 558     if (p == 0) rb_memerror();
 559     heaps_length = next_heaps_length;
 560 }
 561
 562 static void
 563 assign_heap_slot(rb_objspace_t *objspace)
 564 {
 565     RVALUE *p, *pend, *membase;
 566     size_t hi, lo, mid;
 567     int objs;
 568
 569     objs = HEAP_OBJ_LIMIT;
 570     RUBY_CRITICAL(p = (RVALUE*)malloc(HEAP_SIZE));
 571     if (p == 0)
 572         rb_memerror();
 573
 574     membase = p;
 575     if ((VALUE)p % sizeof(RVALUE) != 0) {
 576         p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
 577         if ((HEAP_SIZE - HEAP_OBJ_LIMIT * sizeof(RVALUE)) < ((char*)p - (char*)membase)) {
 578             objs--;
 579         }
 580     }
 581
 582     lo = 0;
 583     hi = heaps_used;
 584     while (lo < hi) {
 585         register RVALUE *mid_membase;
 586         mid = (lo + hi) / 2;
 587         mid_membase = heaps[mid].membase;
 588         if (mid_membase < membase) {
 589             lo = mid + 1;
 590         }
 591         else if (mid_membase > membase) {
 592             hi = mid;
 593         }
 594         else {
 595             rb_bug("same heap slot is allocated: %p at %"PRIuVALUE, membase, (VALUE)mid);
 596         }
 597     }
 598     if (hi < heaps_used) {
 599         MEMMOVE(&heaps[hi+1], &heaps[hi], struct heaps_slot, heaps_used - hi);
 600     }
 601     heaps[hi].membase = membase;
 602     heaps[hi].slot = p;
 603     heaps[hi].limit = objs;
 604     pend = p + objs;
 605     if (lomem == 0 || lomem > p) lomem = p;
 606     if (himem < pend) himem = pend;
 607     heaps_used++;
 608
 609     while (p < pend) {
 610         p->as.free.flags = 0;
 611         p->as.free.next = freelist;
 612         freelist = p;
 613         p++;
 614     }
 615 }
 616
 617 static void
 618 init_heap(rb_objspace_t *objspace)
 619 {
 620     size_t add, i;
 621
 622     add = HEAP_MIN_SLOTS / HEAP_OBJ_LIMIT;
 623
 624     if ((heaps_used + add) > heaps_length) {
 625         allocate_heaps(objspace, heaps_used + add);
 626     }
 627
 628     for (i = 0; i < add; i++) {
 629         assign_heap_slot(objspace);
 630     }
 631     heaps_inc = 0;
 632 }
 633
 634
 635 static void
 636 set_heaps_increment(rb_objspace_t *objspace)
 637 {
 638     size_t next_heaps_length = heaps_used * 1.8;
 639     heaps_inc = next_heaps_length - heaps_used;
 640
 641     if (next_heaps_length > heaps_length) {
 642         allocate_heaps(objspace, next_heaps_length);
 643     }
 644 }
 645
 646 static int
 647 heaps_increment(rb_objspace_t *objspace)
 648 {
 649     if (heaps_inc > 0) {
 650         assign_heap_slot(objspace);
 651         heaps_inc--;
 652         return Qtrue;
 653     }
 654     return Qfalse;
 655 }
 656
 657 #define RANY(o) ((RVALUE*)(o))
 658
 659 static VALUE
 660 rb_newobj_from_heap(rb_objspace_t *objspace)
 661 {
 662     VALUE obj;
 663
 664     if ((ruby_gc_stress && !ruby_disable_gc_stress) || !freelist) {
 665         if (!heaps_increment(objspace) && !garbage_collect(objspace)) {
 666             rb_memerror();
 667         }
 668     }
 669
 670     obj = (VALUE)freelist;
 671     freelist = freelist->as.free.next;
 672
 673     MEMZERO((void*)obj, RVALUE, 1);
 674 #ifdef GC_DEBUG
 675     RANY(obj)->file = rb_sourcefile();
 676     RANY(obj)->line = rb_sourceline();
 677 #endif
 678
 679     return obj;
 680 }
 681
 682 #if USE_VALUE_CACHE
 683 static VALUE
 684 rb_fill_value_cache(rb_thread_t *th)
 685 {
 686     rb_objspace_t *objspace = &rb_objspace;
 687     int i;
 688     VALUE rv;
 689
 690     /* LOCK */
 691     for (i=0; i<RUBY_VM_VALUE_CACHE_SIZE; i++) {
 692         VALUE v = rb_newobj_from_heap(objspace);
 693
 694         th->value_cache[i] = v;
 695         RBASIC(v)->flags = FL_MARK;
 696     }
 697     th->value_cache_ptr = &th->value_cache[0];
 698     rv = rb_newobj_from_heap(objspace);
 699     /* UNLOCK */
 700     return rv;
 701 }
 702 #endif
 703
 704 int
 705 rb_during_gc(void)
 706 {
 707     rb_objspace_t *objspace = &rb_objspace;
 708     return during_gc;
 709 }
 710
 711 VALUE
 712 rb_newobj(void)
 713 {
 714 #if USE_VALUE_CACHE || (defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE)
 715     rb_thread_t *th = GET_THREAD();
 716 #endif
 717 #if USE_VALUE_CACHE
 718     VALUE v = *th->value_cache_ptr;
 719 #endif
 720 #if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
 721     rb_objspace_t *objspace = th->vm->objspace;
 722 #else
 723     rb_objspace_t *objspace = &rb_objspace;
 724 #endif
 725
 726     if (during_gc) {
 727         dont_gc = 1;
 728         during_gc = 0;
 729         rb_bug("object allocation during garbage collection phase");
 730     }
 731
 732 #if USE_VALUE_CACHE
 733     if (v) {
 734         RBASIC(v)->flags = 0;
 735         th->value_cache_ptr++;
 736     }
 737     else {
 738         v = rb_fill_value_cache(th);
 739     }
 740
 741 #if defined(GC_DEBUG)
 742     printf("cache index: %d, v: %p, th: %p\n",
 743            th->value_cache_ptr - th->value_cache, v, th);
 744 #endif
 745     return v;
 746 #else
 747     return rb_newobj_from_heap(objspace);
 748 #endif
 749 }
 750
 751 NODE*
 752 rb_node_newnode(enum node_type type, VALUE a0, VALUE a1, VALUE a2)
 753 {
 754     NODE *n = (NODE*)rb_newobj();
 755
 756     n->flags |= T_NODE;
 757     nd_set_type(n, type);
 758
 759     n->u1.value = a0;
 760     n->u2.value = a1;
 761     n->u3.value = a2;
 762
 763     return n;
 764 }
 765
 766 VALUE
 767 rb_data_object_alloc(VALUE klass, void *datap, RUBY_DATA_FUNC dmark, RUBY_DATA_FUNC dfree)
 768 {
 769     NEWOBJ(data, struct RData);
 770     if (klass) Check_Type(klass, T_CLASS);
 771     OBJSETUP(data, klass, T_DATA);
 772     data->data = datap;
 773     data->dfree = dfree;
 774     data->dmark = dmark;
 775
 776     return (VALUE)data;
 777 }
 778
 779 #ifdef __ia64
 780 #define SET_STACK_END (SET_MACHINE_STACK_END(&th->machine_stack_end), th->machine_register_stack_end = rb_ia64_bsp())
 781 #else
 782 #define SET_STACK_END SET_MACHINE_STACK_END(&th->machine_stack_end)
 783 #endif
 784
 785 #define STACK_START (th->machine_stack_start)
 786 #define STACK_END (th->machine_stack_end)
 787 #define STACK_LEVEL_MAX (th->machine_stack_maxsize/sizeof(VALUE))
 788
 789 #if STACK_GROW_DIRECTION < 0
 790 # define STACK_LENGTH  (STACK_START - STACK_END)
 791 #elif STACK_GROW_DIRECTION > 0
 792 # define STACK_LENGTH  (STACK_END - STACK_START + 1)
 793 #else
 794 # define STACK_LENGTH  ((STACK_END < STACK_START) ? STACK_START - STACK_END\
 795                                            : STACK_END - STACK_START + 1)
 796 #endif
 797 #if !STACK_GROW_DIRECTION
 798 int ruby_stack_grow_direction;
 799 int
 800 ruby_get_stack_grow_direction(VALUE *addr)
 801 {
 802     rb_thread_t *th = GET_THREAD();
 803     SET_STACK_END;
 804
 805     if (STACK_END > addr) return ruby_stack_grow_direction = 1;
 806     return ruby_stack_grow_direction = -1;
 807 }
 808 #endif
 809
 810 #define GC_WATER_MARK 512
 811
 812 int
 813 ruby_stack_length(VALUE **p)
 814 {
 815     rb_thread_t *th = GET_THREAD();
 816     SET_STACK_END;
 817     if (p) *p = STACK_UPPER(STACK_END, STACK_START, STACK_END);
 818     return STACK_LENGTH;
 819 }
 820
 821 int
 822 ruby_stack_check(void)
 823 {
 824     int ret;
 825     rb_thread_t *th = GET_THREAD();
 826     SET_STACK_END;
 827     ret = STACK_LENGTH > STACK_LEVEL_MAX - GC_WATER_MARK;
 828 #ifdef __ia64
 829     if (!ret) {
 830         ret = (VALUE*)rb_ia64_bsp() - th->machine_register_stack_start >
 831               th->machine_register_stack_maxsize/sizeof(VALUE) - GC_WATER_MARK;
 832     }
 833 #endif
 834     return ret;
 835 }
 836
 837 static void
 838 init_mark_stack(rb_objspace_t *objspace)
 839 {
 840     mark_stack_overflow = 0;
 841     mark_stack_ptr = mark_stack;
 842 }
 843
 844 #define MARK_STACK_EMPTY (mark_stack_ptr == mark_stack)
 845
 846 static void gc_mark(rb_objspace_t *objspace, VALUE ptr, int lev);
 847 static void gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev);
 848
 849 static void
 850 gc_mark_all(rb_objspace_t *objspace)
 851 {
 852     RVALUE *p, *pend;
 853     size_t i;
 854
 855     init_mark_stack(objspace);
 856     for (i = 0; i < heaps_used; i++) {
 857         p = heaps[i].slot; pend = p + heaps[i].limit;
 858         while (p < pend) {
 859             if ((p->as.basic.flags & FL_MARK) &&
 860                 (p->as.basic.flags != FL_MARK)) {
 861                 gc_mark_children(objspace, (VALUE)p, 0);
 862             }
 863             p++;
 864         }
 865     }
 866 }
 867
 868 static void
 869 gc_mark_rest(rb_objspace_t *objspace)
 870 {
 871     VALUE tmp_arry[MARK_STACK_MAX];
 872     VALUE *p;
 873
 874     p = (mark_stack_ptr - mark_stack) + tmp_arry;
 875     MEMCPY(tmp_arry, mark_stack, VALUE, p - tmp_arry);
 876
 877     init_mark_stack(objspace);
 878     while (p != tmp_arry) {
 879         p--;
 880         gc_mark_children(objspace, *p, 0);
 881     }
 882 }
 883
 884 static inline int
 885 is_pointer_to_heap(rb_objspace_t *objspace, void *ptr)
 886 {
 887     register RVALUE *p = RANY(ptr);
 888     register struct heaps_slot *heap;
 889     register size_t hi, lo, mid;
 890
 891     if (p < lomem || p > himem) return Qfalse;
 892     if ((VALUE)p % sizeof(RVALUE) != 0) return Qfalse;
 893
 894     /* check if p looks like a pointer using bsearch*/
 895     lo = 0;
 896     hi = heaps_used;
 897     while (lo < hi) {
 898         mid = (lo + hi) / 2;
 899         heap = &heaps[mid];
 900         if (heap->slot <= p) {
 901             if (p < heap->slot + heap->limit)
 902                 return Qtrue;
 903             lo = mid + 1;
 904         }
 905         else {
 906             hi = mid;
 907         }
 908     }
 909     return Qfalse;
 910 }
 911
 912 static void
 913 mark_locations_array(rb_objspace_t *objspace, register VALUE *x, register long n)
 914 {
 915     VALUE v;
 916     while (n--) {
 917         v = *x;
 918         VALGRIND_MAKE_MEM_DEFINED(&v, sizeof(v));
 919         if (is_pointer_to_heap(objspace, (void *)v)) {
 920             gc_mark(objspace, v, 0);
 921         }
 922         x++;
 923     }
 924 }
 925
 926 static void
 927 gc_mark_locations(rb_objspace_t *objspace, VALUE *start, VALUE *end)
 928 {
 929     long n;
 930
 931     if (end <= start) return;
 932     n = end - start;
 933     mark_locations_array(objspace, start, n);
 934 }
 935
 936 void
 937 rb_gc_mark_locations(VALUE *start, VALUE *end)
 938 {
 939     gc_mark_locations(&rb_objspace, start, end);
 940 }
 941
 942 #define rb_gc_mark_locations(start, end) gc_mark_locations(objspace, start, end)
 943
 944 struct mark_tbl_arg {
 945     rb_objspace_t *objspace;
 946     int lev;
 947 };
 948
 949 static int
 950 mark_entry(ID key, VALUE value, st_data_t data)
 951 {
 952     struct mark_tbl_arg *arg = (void*)data;
 953     gc_mark(arg->objspace, value, arg->lev);
 954     return ST_CONTINUE;
 955 }
 956
 957 static void
 958 mark_tbl(rb_objspace_t *objspace, st_table *tbl, int lev)
 959 {
 960     struct mark_tbl_arg arg;
 961     if (!tbl) return;
 962     arg.objspace = objspace;
 963     arg.lev = lev;
 964     st_foreach(tbl, mark_entry, (st_data_t)&arg);
 965 }
 966
 967 void
 968 rb_mark_tbl(st_table *tbl)
 969 {
 970     mark_tbl(&rb_objspace, tbl, 0);
 971 }
 972
 973 static int
 974 mark_key(VALUE key, VALUE value, st_data_t data)
 975 {
 976     struct mark_tbl_arg *arg = (void*)data;
 977     gc_mark(arg->objspace, key, arg->lev);
 978     return ST_CONTINUE;
 979 }
 980
 981 static void
 982 mark_set(rb_objspace_t *objspace, st_table *tbl, int lev)
 983 {
 984     struct mark_tbl_arg arg;
 985     if (!tbl) return;
 986     arg.objspace = objspace;
 987     arg.lev = lev;
 988     st_foreach(tbl, mark_key, (st_data_t)&arg);
 989 }
 990
 991 void
 992 rb_mark_set(st_table *tbl)
 993 {
 994     mark_set(&rb_objspace, tbl, 0);
 995 }
 996
 997 static int
 998 mark_keyvalue(VALUE key, VALUE value, st_data_t data)
 999 {
1000     struct mark_tbl_arg *arg = (void*)data;
1001     gc_mark(arg->objspace, key, arg->lev);
1002     gc_mark(arg->objspace, value, arg->lev);
1003     return ST_CONTINUE;
1004 }
1005
1006 static void
1007 mark_hash(rb_objspace_t *objspace, st_table *tbl, int lev)
1008 {
1009     struct mark_tbl_arg arg;
1010     if (!tbl) return;
1011     arg.objspace = objspace;
1012     arg.lev = lev;
1013     st_foreach(tbl, mark_keyvalue, (st_data_t)&arg);
1014 }
1015
1016 void
1017 rb_mark_hash(st_table *tbl)
1018 {
1019     mark_hash(&rb_objspace, tbl, 0);
1020 }
1021
1022 void
1023 rb_gc_mark_maybe(VALUE obj)
1024 {
1025     if (is_pointer_to_heap(&rb_objspace, (void *)obj)) {
1026         gc_mark(&rb_objspace, obj, 0);
1027     }
1028 }
1029
1030 #define GC_LEVEL_MAX 250
1031
1032 static void
1033 gc_mark(rb_objspace_t *objspace, VALUE ptr, int lev)
1034 {
1035     register RVALUE *obj;
1036
1037     obj = RANY(ptr);
1038     if (rb_special_const_p(ptr)) return; /* special const not marked */
1039     if (obj->as.basic.flags == 0) return;       /* free cell */
1040     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
1041     obj->as.basic.flags |= FL_MARK;
1042
1043     if (lev > GC_LEVEL_MAX || (lev == 0 && ruby_stack_check())) {
1044         if (!mark_stack_overflow) {
1045             if (mark_stack_ptr - mark_stack < MARK_STACK_MAX) {
1046                 *mark_stack_ptr = ptr;
1047                 mark_stack_ptr++;
1048             }
1049             else {
1050                 mark_stack_overflow = 1;
1051             }
1052         }
1053         return;
1054     }
1055     gc_mark_children(objspace, ptr, lev+1);
1056 }
1057
1058 void
1059 rb_gc_mark(VALUE ptr)
1060 {
1061     gc_mark(&rb_objspace, ptr, 0);
1062 }
1063
1064 static void
1065 gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
1066 {
1067     register RVALUE *obj = RANY(ptr);
1068
1069     goto marking;               /* skip */
1070
1071   again:
1072     obj = RANY(ptr);
1073     if (rb_special_const_p(ptr)) return; /* special const not marked */
1074     if (obj->as.basic.flags == 0) return;       /* free cell */
1075     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
1076     obj->as.basic.flags |= FL_MARK;
1077
1078   marking:
1079     if (FL_TEST(obj, FL_EXIVAR)) {
1080         rb_mark_generic_ivar(ptr);
1081     }
1082
1083     switch (BUILTIN_TYPE(obj)) {
1084       case T_NIL:
1085       case T_FIXNUM:
1086         rb_bug("rb_gc_mark() called for broken object");
1087         break;
1088
1089       case T_NODE:
1090         switch (nd_type(obj)) {
1091           case NODE_IF:         /* 1,2,3 */
1092           case NODE_FOR:
1093           case NODE_ITER:
1094           case NODE_WHEN:
1095           case NODE_MASGN:
1096           case NODE_RESCUE:
1097           case NODE_RESBODY:
1098           case NODE_CLASS:
1099           case NODE_BLOCK_PASS:
1100             gc_mark(objspace, (VALUE)obj->as.node.u2.node, lev);
1101             /* fall through */
1102           case NODE_BLOCK:      /* 1,3 */
1103           case NODE_OPTBLOCK:
1104           case NODE_ARRAY:
1105           case NODE_DSTR:
1106           case NODE_DXSTR:
1107           case NODE_DREGX:
1108           case NODE_DREGX_ONCE:
1109           case NODE_ENSURE:
1110           case NODE_CALL:
1111           case NODE_DEFS:
1112           case NODE_OP_ASGN1:
1113           case NODE_ARGS:
1114             gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1115             /* fall through */
1116           case NODE_SUPER:      /* 3 */
1117           case NODE_FCALL:
1118           case NODE_DEFN:
1119           case NODE_ARGS_AUX:
1120             ptr = (VALUE)obj->as.node.u3.node;
1121             goto again;
1122
1123           case NODE_METHOD:     /* 1,2 */
1124           case NODE_WHILE:
1125           case NODE_UNTIL:
1126           case NODE_AND:
1127           case NODE_OR:
1128           case NODE_CASE:
1129           case NODE_SCLASS:
1130           case NODE_DOT2:
1131           case NODE_DOT3:
1132           case NODE_FLIP2:
1133           case NODE_FLIP3:
1134           case NODE_MATCH2:
1135           case NODE_MATCH3:
1136           case NODE_OP_ASGN_OR:
1137           case NODE_OP_ASGN_AND:
1138           case NODE_MODULE:
1139           case NODE_ALIAS:
1140           case NODE_VALIAS:
1141           case NODE_ARGSCAT:
1142             gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1143             /* fall through */
1144           case NODE_FBODY:      /* 2 */
1145           case NODE_GASGN:
1146           case NODE_LASGN:
1147           case NODE_DASGN:
1148           case NODE_DASGN_CURR:
1149           case NODE_IASGN:
1150           case NODE_IASGN2:
1151           case NODE_CVASGN:
1152           case NODE_COLON3:
1153           case NODE_OPT_N:
1154           case NODE_EVSTR:
1155           case NODE_UNDEF:
1156           case NODE_POSTEXE:
1157             ptr = (VALUE)obj->as.node.u2.node;
1158             goto again;
1159
1160           case NODE_HASH:       /* 1 */
1161           case NODE_LIT:
1162           case NODE_STR:
1163           case NODE_XSTR:
1164           case NODE_DEFINED:
1165           case NODE_MATCH:
1166           case NODE_RETURN:
1167           case NODE_BREAK:
1168           case NODE_NEXT:
1169           case NODE_YIELD:
1170           case NODE_COLON2:
1171           case NODE_SPLAT:
1172           case NODE_TO_ARY:
1173             ptr = (VALUE)obj->as.node.u1.node;
1174             goto again;
1175
1176           case NODE_SCOPE:      /* 2,3 */
1177           case NODE_CDECL:
1178           case NODE_OPT_ARG:
1179             gc_mark(objspace, (VALUE)obj->as.node.u3.node, lev);
1180             ptr = (VALUE)obj->as.node.u2.node;
1181             goto again;
1182
1183           case NODE_ZARRAY:     /* - */
1184           case NODE_ZSUPER:
1185           case NODE_CFUNC:
1186           case NODE_VCALL:
1187           case NODE_GVAR:
1188           case NODE_LVAR:
1189           case NODE_DVAR:
1190           case NODE_IVAR:
1191           case NODE_CVAR:
1192           case NODE_NTH_REF:
1193           case NODE_BACK_REF:
1194           case NODE_REDO:
1195           case NODE_RETRY:
1196           case NODE_SELF:
1197           case NODE_NIL:
1198           case NODE_TRUE:
1199           case NODE_FALSE:
1200           case NODE_ERRINFO:
1201           case NODE_ATTRSET:
1202           case NODE_BLOCK_ARG:
1203             break;
1204           case NODE_ALLOCA:
1205             mark_locations_array(objspace,
1206                                  (VALUE*)obj->as.node.u1.value,
1207                                  obj->as.node.u3.cnt);
1208             ptr = (VALUE)obj->as.node.u2.node;
1209             goto again;
1210
1211           default:              /* unlisted NODE */
1212             if (is_pointer_to_heap(objspace, obj->as.node.u1.node)) {
1213                 gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1214             }
1215             if (is_pointer_to_heap(objspace, obj->as.node.u2.node)) {
1216                 gc_mark(objspace, (VALUE)obj->as.node.u2.node, lev);
1217             }
1218             if (is_pointer_to_heap(objspace, obj->as.node.u3.node)) {
1219                 gc_mark(objspace, (VALUE)obj->as.node.u3.node, lev);
1220             }
1221         }
1222         return;                 /* no need to mark class. */
1223     }
1224
1225     gc_mark(objspace, obj->as.basic.klass, lev);
1226     switch (BUILTIN_TYPE(obj)) {
1227       case T_ICLASS:
1228       case T_CLASS:
1229       case T_MODULE:
1230         mark_tbl(objspace, RCLASS_M_TBL(obj), lev);
1231         mark_tbl(objspace, RCLASS_IV_TBL(obj), lev);
1232         ptr = RCLASS_SUPER(obj);
1233         goto again;
1234
1235       case T_ARRAY:
1236         if (FL_TEST(obj, ELTS_SHARED)) {
1237             ptr = obj->as.array.aux.shared;
1238             goto again;
1239         }
1240         else {
1241             long i, len = RARRAY_LEN(obj);
1242             VALUE *ptr = RARRAY_PTR(obj);
1243             for (i=0; i < len; i++) {
1244                 gc_mark(objspace, *ptr++, lev);
1245             }
1246         }
1247         break;
1248
1249       case T_HASH:
1250         mark_hash(objspace, obj->as.hash.ntbl, lev);
1251         ptr = obj->as.hash.ifnone;
1252         goto again;
1253
1254       case T_STRING:
1255 #define STR_ASSOC FL_USER3   /* copied from string.c */
1256         if (FL_TEST(obj, RSTRING_NOEMBED) && FL_ANY(obj, ELTS_SHARED|STR_ASSOC)) {
1257             ptr = obj->as.string.as.heap.aux.shared;
1258             goto again;
1259         }
1260         break;
1261
1262       case T_DATA:
1263         if (obj->as.data.dmark) (*obj->as.data.dmark)(DATA_PTR(obj));
1264         break;
1265
1266       case T_OBJECT:
1267         {
1268             long i, len = ROBJECT_NUMIV(obj);
1269             VALUE *ptr = ROBJECT_IVPTR(obj);
1270             for (i  = 0; i < len; i++) {
1271                 gc_mark(objspace, *ptr++, lev);
1272             }
1273         }
1274         break;
1275
1276       case T_FILE:
1277         if (obj->as.file.fptr)
1278             gc_mark(objspace, obj->as.file.fptr->tied_io_for_writing, lev);
1279         break;
1280
1281       case T_REGEXP:
1282         gc_mark(objspace, obj->as.regexp.src, lev);
1283         break;
1284
1285       case T_FLOAT:
1286       case T_BIGNUM:
1287         break;
1288
1289       case T_MATCH:
1290         gc_mark(objspace, obj->as.match.regexp, lev);
1291         if (obj->as.match.str) {
1292             ptr = obj->as.match.str;
1293             goto again;
1294         }
1295         break;
1296
1297       case T_RATIONAL:
1298         gc_mark(objspace, obj->as.rational.num, lev);
1299         gc_mark(objspace, obj->as.rational.den, lev);
1300         break;
1301
1302       case T_COMPLEX:
1303         gc_mark(objspace, obj->as.complex.real, lev);
1304         gc_mark(objspace, obj->as.complex.image, lev);
1305         break;
1306
1307       case T_STRUCT:
1308         {
1309             long len = RSTRUCT_LEN(obj);
1310             VALUE *ptr = RSTRUCT_PTR(obj);
1311
1312             while (len--) {
1313                 gc_mark(objspace, *ptr++, lev);
1314             }
1315         }
1316         break;
1317
1318       default:
1319         rb_bug("rb_gc_mark(): unknown data type 0x%lx(%p) %s",
1320                BUILTIN_TYPE(obj), obj,
1321                is_pointer_to_heap(objspace, obj) ? "corrupted object" : "non object");
1322     }
1323 }
1324
1325 static int obj_free(rb_objspace_t *, VALUE);
1326
1327 static inline void
1328 add_freelist(rb_objspace_t *objspace, RVALUE *p)
1329 {
1330     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
1331     p->as.free.flags = 0;
1332     p->as.free.next = freelist;
1333     freelist = p;
1334 }
1335
1336 static void
1337 finalize_list(rb_objspace_t *objspace, RVALUE *p)
1338 {
1339     while (p) {
1340         RVALUE *tmp = p->as.free.next;
1341         run_final(objspace, (VALUE)p);
1342         if (!FL_TEST(p, FL_SINGLETON)) { /* not freeing page */
1343             add_freelist(objspace, p);
1344         }
1345         else {
1346             struct heaps_slot *slot = (struct heaps_slot *)RDATA(p)->dmark;
1347             slot->limit--;
1348         }
1349         p = tmp;
1350     }
1351 }
1352
1353 static void
1354 free_unused_heaps(rb_objspace_t *objspace)
1355 {
1356     size_t i, j;
1357     RVALUE *last = 0;
1358
1359     for (i = j = 1; j < heaps_used; i++) {
1360         if (heaps[i].limit == 0) {
1361             if (!last) {
1362                 last = heaps[i].membase;
1363             }
1364             else {
1365                 free(heaps[i].membase);
1366             }
1367             heaps_used--;
1368         }
1369         else {
1370             if (i != j) {
1371                 heaps[j] = heaps[i];
1372             }
1373             j++;
1374         }
1375     }
1376     if (last) {
1377         if (last < heaps_freed) {
1378             free(heaps_freed);
1379             heaps_freed = last;
1380         }
1381         else {
1382             free(last);
1383         }
1384     }
1385 }
1386
1387 static void
1388 gc_sweep(rb_objspace_t *objspace)
1389 {
1390     RVALUE *p, *pend, *final_list;
1391     size_t freed = 0;
1392     size_t i;
1393     size_t live = 0, free_min = 0, do_heap_free = 0;
1394
1395     do_heap_free = (heaps_used * HEAP_OBJ_LIMIT) * 0.65;
1396     free_min = (heaps_used * HEAP_OBJ_LIMIT)  * 0.2;
1397
1398     if (free_min < FREE_MIN) {
1399         do_heap_free = heaps_used * HEAP_OBJ_LIMIT;
1400         free_min = FREE_MIN;
1401     }
1402
1403     freelist = 0;
1404     final_list = deferred_final_list;
1405     deferred_final_list = 0;
1406     for (i = 0; i < heaps_used; i++) {
1407         int n = 0;
1408         RVALUE *free = freelist;
1409         RVALUE *final = final_list;
1410         int deferred;
1411
1412         p = heaps[i].slot; pend = p + heaps[i].limit;
1413         while (p < pend) {
1414             if (!(p->as.basic.flags & FL_MARK)) {
1415                 if (p->as.basic.flags &&
1416                     ((deferred = obj_free(objspace, (VALUE)p)) ||
1417                      ((FL_TEST(p, FL_FINALIZE)) && need_call_final))) {
1418                     if (!deferred) {
1419                         p->as.free.flags = T_DEFERRED;
1420                         RDATA(p)->dfree = 0;
1421                     }
1422                     p->as.free.flags |= FL_MARK;
1423                     p->as.free.next = final_list;
1424                     final_list = p;
1425                 }
1426                 else {
1427                     add_freelist(objspace, p);
1428                 }
1429                 n++;
1430             }
1431             else if (BUILTIN_TYPE(p) == T_DEFERRED) {
1432                 /* objects to be finalized */
1433                 /* do nothing remain marked */
1434             }
1435             else {
1436                 RBASIC(p)->flags &= ~FL_MARK;
1437                 live++;
1438             }
1439             p++;
1440         }
1441         if (n == heaps[i].limit && freed > do_heap_free) {
1442             RVALUE *pp;
1443             int f_count = 0;
1444
1445             for (pp = final_list; pp != final; pp = pp->as.free.next) {
1446                 f_count++;
1447                 RDATA(pp)->dmark = (void *)&heaps[i];
1448                 pp->as.free.flags |= FL_SINGLETON; /* freeing page mark */
1449             }
1450             heaps[i].limit = f_count;
1451
1452             freelist = free;    /* cancel this page from freelist */
1453         }
1454         else {
1455             freed += n;
1456         }
1457     }
1458     if (malloc_increase > malloc_limit) {
1459         malloc_limit += (malloc_increase - malloc_limit) * (double)live / (live + freed);
1460         if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
1461     }
1462     malloc_increase = 0;
1463     if (freed < free_min) {
1464         set_heaps_increment(objspace);
1465         heaps_increment(objspace);
1466     }
1467     during_gc = 0;
1468
1469     /* clear finalization list */
1470     if (final_list) {
1471         deferred_final_list = final_list;
1472         RUBY_VM_SET_FINALIZER_INTERRUPT(GET_THREAD());
1473     }
1474     else{
1475         free_unused_heaps(objspace);
1476     }
1477 }
1478
1479 void
1480 rb_gc_force_recycle(VALUE p)
1481 {
1482     rb_objspace_t *objspace = &rb_objspace;
1483     add_freelist(objspace, (RVALUE *)p);
1484 }
1485
1486 static int
1487 obj_free(rb_objspace_t *objspace, VALUE obj)
1488 {
1489     switch (BUILTIN_TYPE(obj)) {
1490       case T_NIL:
1491       case T_FIXNUM:
1492       case T_TRUE:
1493       case T_FALSE:
1494         rb_bug("obj_free() called for broken object");
1495         break;
1496     }
1497
1498     if (FL_TEST(obj, FL_EXIVAR)) {
1499         rb_free_generic_ivar((VALUE)obj);
1500     }
1501
1502     switch (BUILTIN_TYPE(obj)) {
1503       case T_OBJECT:
1504         if (!(RANY(obj)->as.basic.flags & ROBJECT_EMBED) &&
1505             RANY(obj)->as.object.as.heap.ivptr) {
1506             xfree(RANY(obj)->as.object.as.heap.ivptr);
1507         }
1508         break;
1509       case T_MODULE:
1510       case T_CLASS:
1511         rb_clear_cache_by_class((VALUE)obj);
1512         st_free_table(RCLASS_M_TBL(obj));
1513         if (RCLASS_IV_TBL(obj)) {
1514             st_free_table(RCLASS_IV_TBL(obj));
1515         }
1516         if (RCLASS_IV_INDEX_TBL(obj)) {
1517             st_free_table(RCLASS_IV_INDEX_TBL(obj));
1518         }
1519         xfree(RANY(obj)->as.klass.ptr);
1520         break;
1521       case T_STRING:
1522         rb_str_free(obj);
1523         break;
1524       case T_ARRAY:
1525         rb_ary_free(obj);
1526         break;
1527       case T_HASH:
1528         if (RANY(obj)->as.hash.ntbl) {
1529             st_free_table(RANY(obj)->as.hash.ntbl);
1530         }
1531         break;
1532       case T_REGEXP:
1533         if (RANY(obj)->as.regexp.ptr) {
1534             onig_free(RANY(obj)->as.regexp.ptr);
1535         }
1536         break;
1537       case T_DATA:
1538         if (DATA_PTR(obj)) {
1539             if ((long)RANY(obj)->as.data.dfree == -1) {
1540                 xfree(DATA_PTR(obj));
1541             }
1542             else if (RANY(obj)->as.data.dfree) {
1543                 if (1) {
1544                     RANY(obj)->as.basic.flags &= ~T_MASK;
1545                     RANY(obj)->as.basic.flags |= T_DEFERRED;
1546                     return 1;
1547                 }
1548                 else {
1549                     (*RANY(obj)->as.data.dfree)(DATA_PTR(obj));
1550                 }
1551             }
1552         }
1553         break;
1554       case T_MATCH:
1555         if (RANY(obj)->as.match.rmatch) {
1556             struct rmatch *rm = RANY(obj)->as.match.rmatch;
1557             onig_region_free(&rm->regs, 0);
1558             if (rm->char_offset)
1559               xfree(rm->char_offset);
1560             xfree(rm);
1561         }
1562         break;
1563       case T_FILE:
1564         if (RANY(obj)->as.file.fptr) {
1565             rb_io_t *fptr = RANY(obj)->as.file.fptr;
1566             if (1) {
1567                 RANY(obj)->as.basic.flags &= ~T_MASK;
1568                 RANY(obj)->as.basic.flags |= T_DEFERRED;
1569                 RDATA(obj)->dfree = (void (*)(void*))rb_io_fptr_finalize;
1570                 RDATA(obj)->data = fptr;
1571                 return 1;
1572             }
1573             else {
1574                 rb_io_fptr_finalize(fptr);
1575             }
1576         }
1577         break;
1578       case T_RATIONAL:
1579       case T_COMPLEX:
1580         break;
1581       case T_ICLASS:
1582         /* iClass shares table with the module */
1583         break;
1584
1585       case T_FLOAT:
1586         break;
1587
1588       case T_BIGNUM:
1589         if (!(RBASIC(obj)->flags & RBIGNUM_EMBED_FLAG) && RBIGNUM_DIGITS(obj)) {
1590             xfree(RBIGNUM_DIGITS(obj));
1591         }
1592         break;
1593       case T_NODE:
1594         switch (nd_type(obj)) {
1595           case NODE_SCOPE:
1596             if (RANY(obj)->as.node.u1.tbl) {
1597                 xfree(RANY(obj)->as.node.u1.tbl);
1598             }
1599             break;
1600           case NODE_ALLOCA:
1601             xfree(RANY(obj)->as.node.u1.node);
1602             break;
1603         }
1604         break;                  /* no need to free iv_tbl */
1605
1606       case T_STRUCT:
1607         if ((RBASIC(obj)->flags & RSTRUCT_EMBED_LEN_MASK) == 0 &&
1608             RANY(obj)->as.rstruct.as.heap.ptr) {
1609             xfree(RANY(obj)->as.rstruct.as.heap.ptr);
1610         }
1611         break;
1612
1613       default:
1614         rb_bug("gc_sweep(): unknown data type 0x%lx(%p)",
1615                BUILTIN_TYPE(obj), (void*)obj);
1616     }
1617
1618     return 0;
1619 }
1620
1621 #ifdef __GNUC__
1622 #if defined(__human68k__) || defined(DJGPP)
1623 #undef rb_setjmp
1624 #undef rb_jmp_buf
1625 #if defined(__human68k__)
1626 typedef unsigned long rb_jmp_buf[8];
1627 __asm__ (".even\n\
1628 _rb_setjmp:\n\
1629         move.l  4(sp),a0\n\
1630         movem.l d3-d7/a3-a5,(a0)\n\
1631         moveq.l #0,d0\n\
1632         rts");
1633 #else
1634 #if defined(DJGPP)
1635 typedef unsigned long rb_jmp_buf[6];
1636 __asm__ (".align 4\n\
1637 _rb_setjmp:\n\
1638         pushl   %ebp\n\
1639         movl    %esp,%ebp\n\
1640         movl    8(%ebp),%ebp\n\
1641         movl    %eax,(%ebp)\n\
1642         movl    %ebx,4(%ebp)\n\
1643         movl    %ecx,8(%ebp)\n\
1644         movl    %edx,12(%ebp)\n\
1645         movl    %esi,16(%ebp)\n\
1646         movl    %edi,20(%ebp)\n\
1647         popl    %ebp\n\
1648         xorl    %eax,%eax\n\
1649         ret");
1650 #endif
1651 #endif
1652 int rb_setjmp (rb_jmp_buf);
1653 #endif /* __human68k__ or DJGPP */
1654 #endif /* __GNUC__ */
1655
1656 #define GC_NOTIFY 0
1657
1658 void rb_vm_mark(void *ptr);
1659
1660 static void
1661 mark_current_machine_context(rb_objspace_t *objspace, rb_thread_t *th)
1662 {
1663     rb_jmp_buf save_regs_gc_mark;
1664     VALUE *stack_start, *stack_end;
1665
1666     SET_STACK_END;
1667 #if STACK_GROW_DIRECTION < 0
1668     stack_start = th->machine_stack_end;
1669     stack_end = th->machine_stack_start;
1670 #elif STACK_GROW_DIRECTION > 0
1671     stack_start = th->machine_stack_start;
1672     stack_end = th->machine_stack_end + 1;
1673 #else
1674     if (th->machine_stack_end < th->machine_stack_start) {
1675         stack_start = th->machine_stack_end;
1676         stack_end = th->machine_stack_start;
1677     }
1678     else {
1679         stack_start = th->machine_stack_start;
1680         stack_end = th->machine_stack_end + 1;
1681     }
1682 #endif
1683
1684     FLUSH_REGISTER_WINDOWS;
1685     /* This assumes that all registers are saved into the jmp_buf (and stack) */
1686     rb_setjmp(save_regs_gc_mark);
1687     mark_locations_array(objspace,
1688                          (VALUE*)save_regs_gc_mark,
1689                          sizeof(save_regs_gc_mark) / sizeof(VALUE));
1690
1691     rb_gc_mark_locations(stack_start, stack_end);
1692 #ifdef __ia64
1693     rb_gc_mark_locations(th->machine_register_stack_start, th->machine_register_stack_end);
1694 #endif
1695 #if defined(__human68k__) || defined(__mc68000__)
1696     mark_locations_array((VALUE*)((char*)STACK_END + 2),
1697                          (STACK_START - STACK_END));
1698 #endif
1699 }
1700
1701 void rb_gc_mark_encodings(void);
1702
1703 static int
1704 garbage_collect(rb_objspace_t *objspace)
1705 {
1706     struct gc_list *list;
1707     rb_thread_t *th = GET_THREAD();
1708
1709     if (GC_NOTIFY) printf("start garbage_collect()\n");
1710
1711     if (!heaps) {
1712         return Qfalse;
1713     }
1714
1715     if (dont_gc || during_gc) {
1716         if (!freelist) {
1717             if (!heaps_increment(objspace)) {
1718                 set_heaps_increment(objspace);
1719                 heaps_increment(objspace);
1720             }
1721         }
1722         return Qtrue;
1723     }
1724     during_gc++;
1725     objspace->count++;
1726
1727     SET_STACK_END;
1728
1729     init_mark_stack(objspace);
1730
1731     th->vm->self ? rb_gc_mark(th->vm->self) : rb_vm_mark(th->vm);
1732
1733     if (finalizer_table) {
1734         mark_tbl(objspace, finalizer_table, 0);
1735     }
1736
1737     mark_current_machine_context(objspace, th);
1738
1739     rb_gc_mark_threads();
1740     rb_gc_mark_symbols();
1741     rb_gc_mark_encodings();
1742
1743     /* mark protected global variables */
1744     for (list = global_List; list; list = list->next) {
1745         rb_gc_mark_maybe(*list->varptr);
1746     }
1747     rb_mark_end_proc();
1748     rb_gc_mark_global_tbl();
1749
1750     mark_tbl(objspace, rb_class_tbl, 0);
1751     rb_gc_mark_trap_list();
1752
1753     /* mark generic instance variables for special constants */
1754     rb_mark_generic_ivar_tbl();
1755
1756     rb_gc_mark_parser();
1757
1758     /* gc_mark objects whose marking are not completed*/
1759     while (!MARK_STACK_EMPTY) {
1760         if (mark_stack_overflow) {
1761             gc_mark_all(objspace);
1762         }
1763         else {
1764             gc_mark_rest(objspace);
1765         }
1766     }
1767
1768     gc_sweep(objspace);
1769
1770     if (GC_NOTIFY) printf("end garbage_collect()\n");
1771     return Qtrue;
1772 }
1773
1774 int
1775 rb_garbage_collect(void)
1776 {
1777     return garbage_collect(&rb_objspace);
1778 }
1779
1780 void
1781 rb_gc_mark_machine_stack(rb_thread_t *th)
1782 {
1783     rb_objspace_t *objspace = &rb_objspace;
1784 #if STACK_GROW_DIRECTION < 0
1785     rb_gc_mark_locations(th->machine_stack_end, th->machine_stack_start);
1786 #elif STACK_GROW_DIRECTION > 0
1787     rb_gc_mark_locations(th->machine_stack_start, th->machine_stack_end);
1788 #else
1789     if (th->machine_stack_start < th->machine_stack_end) {
1790         rb_gc_mark_locations(th->machine_stack_start, th->machine_stack_end);
1791     }
1792     else {
1793         rb_gc_mark_locations(th->machine_stack_end, th->machine_stack_start);
1794     }
1795 #endif
1796 #ifdef __ia64
1797     rb_gc_mark_locations(th->machine_register_stack_start, th->machine_register_stack_end);
1798 #endif
1799 }
1800
1801
1802 /*
1803  *  call-seq:
1804  *     GC.start                     => nil
1805  *     gc.garbage_collect           => nil
1806  *     ObjectSpace.garbage_collect  => nil
1807  *
1808  *  Initiates garbage collection, unless manually disabled.
1809  *
1810  */
1811
1812 VALUE
1813 rb_gc_start(void)
1814 {
1815     rb_gc();
1816     return Qnil;
1817 }
1818
1819 #undef Init_stack
1820
1821 void
1822 Init_stack(VALUE *addr)
1823 {
1824     ruby_init_stack(addr);
1825 }
1826
1827 /*
1828  * Document-class: ObjectSpace
1829  *
1830  *  The <code>ObjectSpace</code> module contains a number of routines
1831  *  that interact with the garbage collection facility and allow you to
1832  *  traverse all living objects with an iterator.
1833  *
1834  *  <code>ObjectSpace</code> also provides support for object
1835  *  finalizers, procs that will be called when a specific object is
1836  *  about to be destroyed by garbage collection.
1837  *
1838  *     include ObjectSpace
1839  *
1840  *
1841  *     a = "A"
1842  *     b = "B"
1843  *     c = "C"
1844  *
1845  *
1846  *     define_finalizer(a, proc {|id| puts "Finalizer one on #{id}" })
1847  *     define_finalizer(a, proc {|id| puts "Finalizer two on #{id}" })
1848  *     define_finalizer(b, proc {|id| puts "Finalizer three on #{id}" })
1849  *
1850  *  <em>produces:</em>
1851  *
1852  *     Finalizer three on 537763470
1853  *     Finalizer one on 537763480
1854  *     Finalizer two on 537763480
1855  *
1856  */
1857
1858 void
1859 Init_heap(void)
1860 {
1861     init_heap(&rb_objspace);
1862 }
1863
1864 static VALUE
1865 os_obj_of(rb_objspace_t *objspace, VALUE of)
1866 {
1867     size_t i;
1868     size_t n = 0;
1869     RVALUE *membase = 0;
1870     RVALUE *p, *pend;
1871     volatile VALUE v;
1872
1873     i = 0;
1874     while (i < heaps_used) {
1875         while (0 < i && (uintptr_t)membase < (uintptr_t)heaps[i-1].membase)
1876             i--;
1877         while (i < heaps_used && (uintptr_t)heaps[i].membase <= (uintptr_t)membase )
1878             i++;
1879         if (heaps_used <= i)
1880             break;
1881         membase = heaps[i].membase;
1882
1883         p = heaps[i].slot; pend = p + heaps[i].limit;
1884         for (;p < pend; p++) {
1885             if (p->as.basic.flags) {
1886                 switch (BUILTIN_TYPE(p)) {
1887                   case T_NONE:
1888                   case T_ICLASS:
1889                   case T_NODE:
1890                   case T_DEFERRED:
1891                     continue;
1892                   case T_CLASS:
1893                     if (FL_TEST(p, FL_SINGLETON)) continue;
1894                   default:
1895                     if (!p->as.basic.klass) continue;
1896                     v = (VALUE)p;
1897                     if (!of || rb_obj_is_kind_of(v, of)) {
1898                         rb_yield(v);
1899                         n++;
1900                     }
1901                 }
1902             }
1903         }
1904     }
1905
1906     return SIZET2NUM(n);
1907 }
1908
1909 /*
1910  *  call-seq:
1911  *     ObjectSpace.each_object([module]) {|obj| ... } => fixnum
1912  *
1913  *  Calls the block once for each living, nonimmediate object in this
1914  *  Ruby process. If <i>module</i> is specified, calls the block
1915  *  for only those classes or modules that match (or are a subclass of)
1916  *  <i>module</i>. Returns the number of objects found. Immediate
1917  *  objects (<code>Fixnum</code>s, <code>Symbol</code>s
1918  *  <code>true</code>, <code>false</code>, and <code>nil</code>) are
1919  *  never returned. In the example below, <code>each_object</code>
1920  *  returns both the numbers we defined and several constants defined in
1921  *  the <code>Math</code> module.
1922  *
1923  *     a = 102.7
1924  *     b = 95       # Won't be returned
1925  *     c = 12345678987654321
1926  *     count = ObjectSpace.each_object(Numeric) {|x| p x }
1927  *     puts "Total count: #{count}"
1928  *
1929  *  <em>produces:</em>
1930  *
1931  *     12345678987654321
1932  *     102.7
1933  *     2.71828182845905
1934  *     3.14159265358979
1935  *     2.22044604925031e-16
1936  *     1.7976931348623157e+308
1937  *     2.2250738585072e-308
1938  *     Total count: 7
1939  *
1940  */
1941
1942 static VALUE
1943 os_each_obj(int argc, VALUE *argv, VALUE os)
1944 {
1945     VALUE of;
1946
1947     rb_secure(4);
1948     if (argc == 0) {
1949         of = 0;
1950     }
1951     else {
1952         rb_scan_args(argc, argv, "01", &of);
1953     }
1954     RETURN_ENUMERATOR(os, 1, &of);
1955     return os_obj_of(&rb_objspace, of);
1956 }
1957
1958 /*
1959  *  call-seq:
1960  *     ObjectSpace.undefine_finalizer(obj)
1961  *
1962  *  Removes all finalizers for <i>obj</i>.
1963  *
1964  */
1965
1966 static VALUE
1967 undefine_final(VALUE os, VALUE obj)
1968 {
1969     rb_objspace_t *objspace = &rb_objspace;
1970     if (finalizer_table) {
1971         st_delete(finalizer_table, (st_data_t*)&obj, 0);
1972     }
1973     return obj;
1974 }
1975
1976 /*
1977  *  call-seq:
1978  *     ObjectSpace.define_finalizer(obj, aProc=proc())
1979  *
1980  *  Adds <i>aProc</i> as a finalizer, to be called after <i>obj</i>
1981  *  was destroyed.
1982  *
1983  */
1984
1985 static VALUE
1986 define_final(int argc, VALUE *argv, VALUE os)
1987 {
1988     rb_objspace_t *objspace = &rb_objspace;
1989     VALUE obj, block, table;
1990
1991     rb_scan_args(argc, argv, "11", &obj, &block);
1992     if (argc == 1) {
1993         block = rb_block_proc();
1994     }
1995     else if (!rb_respond_to(block, rb_intern("call"))) {
1996         rb_raise(rb_eArgError, "wrong type argument %s (should be callable)",
1997                  rb_obj_classname(block));
1998     }
1999     FL_SET(obj, FL_FINALIZE);
2000
2001     block = rb_ary_new3(2, INT2FIX(rb_safe_level()), block);
2002
2003     if (!finalizer_table) {
2004         finalizer_table = st_init_numtable();
2005     }
2006     if (st_lookup(finalizer_table, obj, &table)) {
2007         rb_ary_push(table, block);
2008     }
2009     else {
2010         st_add_direct(finalizer_table, obj, rb_ary_new3(1, block));
2011     }
2012     return block;
2013 }
2014
2015 void
2016 rb_gc_copy_finalizer(VALUE dest, VALUE obj)
2017 {
2018     rb_objspace_t *objspace = &rb_objspace;
2019     VALUE table;
2020
2021     if (!finalizer_table) return;
2022     if (!FL_TEST(obj, FL_FINALIZE)) return;
2023     if (st_lookup(finalizer_table, obj, &table)) {
2024         st_insert(finalizer_table, dest, table);
2025     }
2026     FL_SET(dest, FL_FINALIZE);
2027 }
2028
2029 static VALUE
2030 run_single_final(VALUE arg)
2031 {
2032     VALUE *args = (VALUE *)arg;
2033     rb_eval_cmd(args[0], args[1], (int)args[2]);
2034     return Qnil;
2035 }
2036
2037 static void
2038 run_final(rb_objspace_t *objspace, VALUE obj)
2039 {
2040     long i;
2041     int status;
2042     VALUE args[3], table, objid;
2043
2044     objid = rb_obj_id(obj);     /* make obj into id */
2045
2046     if (RDATA(obj)->dfree) {
2047         (*RDATA(obj)->dfree)(DATA_PTR(obj));
2048     }
2049
2050     if (finalizer_table &&
2051         st_delete(finalizer_table, (st_data_t*)&obj, &table)) {
2052         args[1] = 0;
2053         args[2] = (VALUE)rb_safe_level();
2054         if (!args[1] && RARRAY_LEN(table) > 0) {
2055             args[1] = rb_obj_freeze(rb_ary_new3(1, objid));
2056         }
2057         for (i=0; i<RARRAY_LEN(table); i++) {
2058             VALUE final = RARRAY_PTR(table)[i];
2059             args[0] = RARRAY_PTR(final)[1];
2060             args[2] = FIX2INT(RARRAY_PTR(final)[0]);
2061             rb_protect(run_single_final, (VALUE)args, &status);
2062         }
2063     }
2064 }
2065
2066 static void
2067 gc_finalize_deferred(rb_objspace_t *objspace)
2068 {
2069     RVALUE *p = deferred_final_list;
2070     deferred_final_list = 0;
2071
2072     if (p) {
2073         finalize_list(objspace, p);
2074     }
2075     free_unused_heaps(objspace);
2076 }
2077
2078 void
2079 rb_gc_finalize_deferred(void)
2080 {
2081     gc_finalize_deferred(&rb_objspace);
2082 }
2083
2084 static int
2085 chain_finalized_object(st_data_t key, st_data_t val, st_data_t arg)
2086 {
2087     RVALUE *p = (RVALUE *)key, **final_list = (RVALUE **)arg;
2088     if (p->as.basic.flags & FL_FINALIZE) {
2089         if (BUILTIN_TYPE(p) != T_DEFERRED) {
2090             p->as.free.flags = FL_MARK | T_DEFERRED; /* remain marked */
2091             RDATA(p)->dfree = 0;
2092         }
2093         p->as.free.next = *final_list;
2094         *final_list = p;
2095     }
2096     return ST_CONTINUE;
2097 }
2098
2099 void
2100 rb_gc_call_finalizer_at_exit(void)
2101 {
2102     rb_objspace_t *objspace = &rb_objspace;
2103     RVALUE *p, *pend;
2104     size_t i;
2105
2106     /* run finalizers */
2107     if (need_call_final) {
2108         do {
2109             p = deferred_final_list;
2110             deferred_final_list = 0;
2111             finalize_list(objspace, p);
2112             st_foreach(finalizer_table, chain_finalized_object,
2113                        (st_data_t)&deferred_final_list);
2114         } while (deferred_final_list);
2115     }
2116     /* finalizers are part of garbage collection */
2117     during_gc++;
2118     /* run data object's finalizers */
2119     for (i = 0; i < heaps_used; i++) {
2120         p = heaps[i].slot; pend = p + heaps[i].limit;
2121         while (p < pend) {
2122             if (BUILTIN_TYPE(p) == T_DATA &&
2123                 DATA_PTR(p) && RANY(p)->as.data.dfree &&
2124                 RANY(p)->as.basic.klass != rb_cThread) {
2125                 p->as.free.flags = 0;
2126                 if ((long)RANY(p)->as.data.dfree == -1) {
2127                     xfree(DATA_PTR(p));
2128                 }
2129                 else if (RANY(p)->as.data.dfree) {
2130                     (*RANY(p)->as.data.dfree)(DATA_PTR(p));
2131                 }
2132                 VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
2133             }
2134             else if (BUILTIN_TYPE(p) == T_FILE) {
2135                 if (rb_io_fptr_finalize(RANY(p)->as.file.fptr)) {
2136                     p->as.free.flags = 0;
2137                     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
2138                 }
2139             }
2140             p++;
2141         }
2142     }
2143     during_gc = 0;
2144 }
2145
2146 void
2147 rb_gc(void)
2148 {
2149     rb_objspace_t *objspace = &rb_objspace;
2150     garbage_collect(objspace);
2151     gc_finalize_deferred(objspace);
2152 }
2153
2154 /*
2155  *  call-seq:
2156  *     ObjectSpace._id2ref(object_id) -> an_object
2157  *
2158  *  Converts an object id to a reference to the object. May not be
2159  *  called on an object id passed as a parameter to a finalizer.
2160  *
2161  *     s = "I am a string"                    #=> "I am a string"
2162  *     r = ObjectSpace._id2ref(s.object_id)   #=> "I am a string"
2163  *     r == s                                 #=> true
2164  *
2165  */
2166
2167 static VALUE
2168 id2ref(VALUE obj, VALUE objid)
2169 {
2170 #if SIZEOF_LONG == SIZEOF_VOIDP
2171 #define NUM2PTR(x) NUM2ULONG(x)
2172 #elif SIZEOF_LONG_LONG == SIZEOF_VOIDP
2173 #define NUM2PTR(x) NUM2ULL(x)
2174 #endif
2175     rb_objspace_t *objspace = &rb_objspace;
2176     VALUE ptr;
2177     void *p0;
2178
2179     rb_secure(4);
2180     ptr = NUM2PTR(objid);
2181     p0 = (void *)ptr;
2182
2183     if (ptr == Qtrue) return Qtrue;
2184     if (ptr == Qfalse) return Qfalse;
2185     if (ptr == Qnil) return Qnil;
2186     if (FIXNUM_P(ptr)) return (VALUE)ptr;
2187     ptr = objid ^ FIXNUM_FLAG;  /* unset FIXNUM_FLAG */
2188
2189     if ((ptr % sizeof(RVALUE)) == (4 << 2)) {
2190         ID symid = ptr / sizeof(RVALUE);
2191         if (rb_id2name(symid) == 0)
2192             rb_raise(rb_eRangeError, "%p is not symbol id value", p0);
2193         return ID2SYM(symid);
2194     }
2195
2196     if (!is_pointer_to_heap(objspace, (void *)ptr) ||
2197         BUILTIN_TYPE(ptr) > T_FIXNUM || BUILTIN_TYPE(ptr) == T_ICLASS) {
2198         rb_raise(rb_eRangeError, "%p is not id value", p0);
2199     }
2200     if (BUILTIN_TYPE(ptr) == 0 || RBASIC(ptr)->klass == 0) {
2201         rb_raise(rb_eRangeError, "%p is recycled object", p0);
2202     }
2203     return (VALUE)ptr;
2204 }
2205
2206 /*
2207  *  Document-method: __id__
2208  *  Document-method: object_id
2209  *
2210  *  call-seq:
2211  *     obj.__id__       => fixnum
2212  *     obj.object_id    => fixnum
2213  *
2214  *  Returns an integer identifier for <i>obj</i>. The same number will
2215  *  be returned on all calls to <code>id</code> for a given object, and
2216  *  no two active objects will share an id.
2217  *  <code>Object#object_id</code> is a different concept from the
2218  *  <code>:name</code> notation, which returns the symbol id of
2219  *  <code>name</code>. Replaces the deprecated <code>Object#id</code>.
2220  */
2221
2222 /*
2223  *  call-seq:
2224  *     obj.hash    => fixnum
2225  *
2226  *  Generates a <code>Fixnum</code> hash value for this object. This
2227  *  function must have the property that <code>a.eql?(b)</code> implies
2228  *  <code>a.hash == b.hash</code>. The hash value is used by class
2229  *  <code>Hash</code>. Any hash value that exceeds the capacity of a
2230  *  <code>Fixnum</code> will be truncated before being used.
2231  */
2232
2233 VALUE
2234 rb_obj_id(VALUE obj)
2235 {
2236     /*
2237      *                32-bit VALUE space
2238      *          MSB ------------------------ LSB
2239      *  false   00000000000000000000000000000000
2240      *  true    00000000000000000000000000000010
2241      *  nil     00000000000000000000000000000100
2242      *  undef   00000000000000000000000000000110
2243      *  symbol  ssssssssssssssssssssssss00001110
2244      *  object  oooooooooooooooooooooooooooooo00        = 0 (mod sizeof(RVALUE))
2245      *  fixnum  fffffffffffffffffffffffffffffff1
2246      *
2247      *                    object_id space
2248      *                                       LSB
2249      *  false   00000000000000000000000000000000
2250      *  true    00000000000000000000000000000010
2251      *  nil     00000000000000000000000000000100
2252      *  undef   00000000000000000000000000000110
2253      *  symbol   000SSSSSSSSSSSSSSSSSSSSSSSSSSS0        S...S % A = 4 (S...S = s...s * A + 4)
2254      *  object   oooooooooooooooooooooooooooooo0        o...o % A = 0
2255      *  fixnum  fffffffffffffffffffffffffffffff1        bignum if required
2256      *
2257      *  where A = sizeof(RVALUE)/4
2258      *
2259      *  sizeof(RVALUE) is
2260      *  20 if 32-bit, double is 4-byte aligned
2261      *  24 if 32-bit, double is 8-byte aligned
2262      *  40 if 64-bit
2263      */
2264     if (TYPE(obj) == T_SYMBOL) {
2265         return (SYM2ID(obj) * sizeof(RVALUE) + (4 << 2)) | FIXNUM_FLAG;
2266     }
2267     if (SPECIAL_CONST_P(obj)) {
2268         return LONG2NUM((SIGNED_VALUE)obj);
2269     }
2270     return (VALUE)((SIGNED_VALUE)obj|FIXNUM_FLAG);
2271 }
2272
2273 static int
2274 set_zero(st_data_t key, st_data_t val, st_data_t arg)
2275 {
2276     VALUE k = (VALUE)key;
2277     VALUE hash = (VALUE)arg;
2278     rb_hash_aset(hash, k, INT2FIX(0));
2279     return ST_CONTINUE;
2280 }
2281
2282 /*
2283  *  call-seq:
2284  *     ObjectSpace.count_objects([result_hash]) -> hash
2285  *
2286  *  Counts objects for each type.
2287  *
2288  *  It returns a hash as:
2289  *  {:TOTAL=>10000, :FREE=>3011, :T_OBJECT=>6, :T_CLASS=>404, ...}
2290  *
2291  *  If the optional argument, result_hash, is given,
2292  *  it is overwritten and returned.
2293  *  This is intended to avoid probe effect.
2294  *
2295  *  The contents of the returned hash is implementation defined.
2296  *  It may be changed in future.
2297  *
2298  *  This method is not expected to work except C Ruby.
2299  *
2300  */
2301
2302 static VALUE
2303 count_objects(int argc, VALUE *argv, VALUE os)
2304 {
2305     rb_objspace_t *objspace = &rb_objspace;
2306     size_t counts[T_MASK+1];
2307     size_t freed = 0;
2308     size_t total = 0;
2309     size_t i;
2310     VALUE hash;
2311
2312     if (rb_scan_args(argc, argv, "01", &hash) == 1) {
2313         if (TYPE(hash) != T_HASH)
2314             rb_raise(rb_eTypeError, "non-hash given");
2315     }
2316
2317     for (i = 0; i <= T_MASK; i++) {
2318         counts[i] = 0;
2319     }
2320
2321     for (i = 0; i < heaps_used; i++) {
2322         RVALUE *p, *pend;
2323
2324         p = heaps[i].slot; pend = p + heaps[i].limit;
2325         for (;p < pend; p++) {
2326             if (p->as.basic.flags) {
2327                 counts[BUILTIN_TYPE(p)]++;
2328             }
2329             else {
2330                 freed++;
2331             }
2332         }
2333         total += heaps[i].limit;
2334     }
2335
2336     if (hash == Qnil) {
2337         hash = rb_hash_new();
2338     }
2339     else if (!RHASH_EMPTY_P(hash)) {
2340         st_foreach(RHASH_TBL(hash), set_zero, hash);
2341     }
2342     rb_hash_aset(hash, ID2SYM(rb_intern("TOTAL")), SIZET2NUM(total));
2343     rb_hash_aset(hash, ID2SYM(rb_intern("FREE")), SIZET2NUM(freed));
2344     for (i = 0; i <= T_MASK; i++) {
2345         VALUE type;
2346         switch (i) {
2347 #define COUNT_TYPE(t) case t: type = ID2SYM(rb_intern(#t)); break;
2348             COUNT_TYPE(T_NONE);
2349             COUNT_TYPE(T_OBJECT);
2350             COUNT_TYPE(T_CLASS);
2351             COUNT_TYPE(T_MODULE);
2352             COUNT_TYPE(T_FLOAT);
2353             COUNT_TYPE(T_STRING);
2354             COUNT_TYPE(T_REGEXP);
2355             COUNT_TYPE(T_ARRAY);
2356             COUNT_TYPE(T_HASH);
2357             COUNT_TYPE(T_STRUCT);
2358             COUNT_TYPE(T_BIGNUM);
2359             COUNT_TYPE(T_FILE);
2360             COUNT_TYPE(T_DATA);
2361             COUNT_TYPE(T_MATCH);
2362             COUNT_TYPE(T_COMPLEX);
2363             COUNT_TYPE(T_RATIONAL);
2364             COUNT_TYPE(T_NIL);
2365             COUNT_TYPE(T_TRUE);
2366             COUNT_TYPE(T_FALSE);
2367             COUNT_TYPE(T_SYMBOL);
2368             COUNT_TYPE(T_FIXNUM);
2369             COUNT_TYPE(T_UNDEF);
2370             COUNT_TYPE(T_NODE);
2371             COUNT_TYPE(T_ICLASS);
2372             COUNT_TYPE(T_DEFERRED);
2373 #undef COUNT_TYPE
2374           default:              type = INT2NUM(i); break;
2375         }
2376         if (counts[i])
2377             rb_hash_aset(hash, type, SIZET2NUM(counts[i]));
2378     }
2379
2380     return hash;
2381 }
2382
2383 /*
2384  *  call-seq:
2385  *     GC.count -> Integer
2386  *
2387  *  The number of times GC occured.
2388  *
2389  *  It returns the number of times GC occured since the process started.
2390  *
2391  */
2392
2393 static VALUE
2394 gc_count(VALUE self)
2395 {
2396     return UINT2NUM((&rb_objspace)->count);
2397 }
2398
2399 #if CALC_EXACT_MALLOC_SIZE
2400 /*
2401  *  call-seq:
2402  *     GC.malloc_allocated_size -> Integer
2403  *
2404  *  The allocated size by malloc().
2405  *
2406  *  It returns the allocated size by malloc().
2407  */
2408
2409 static VALUE
2410 gc_malloc_allocated_size(VALUE self)
2411 {
2412     return UINT2NUM((&rb_objspace)->malloc_params.allocated_size);
2413 }
2414
2415 /*
2416  *  call-seq:
2417  *     GC.malloc_allocations -> Integer
2418  *
2419  *  The number of allocated memory object by malloc().
2420  *
2421  *  It returns the number of allocated memory object by malloc().
2422  */
2423
2424 static VALUE
2425 gc_malloc_allocations(VALUE self)
2426 {
2427     return UINT2NUM((&rb_objspace)->malloc_params.allocations);
2428 }
2429 #endif
2430
2431 /*
2432  *  The <code>GC</code> module provides an interface to Ruby's mark and
2433  *  sweep garbage collection mechanism. Some of the underlying methods
2434  *  are also available via the <code>ObjectSpace</code> module.
2435  */
2436
2437 void
2438 Init_GC(void)
2439 {
2440     VALUE rb_mObSpace;
2441
2442     rb_mGC = rb_define_module("GC");
2443     rb_define_singleton_method(rb_mGC, "start", rb_gc_start, 0);
2444     rb_define_singleton_method(rb_mGC, "enable", rb_gc_enable, 0);
2445     rb_define_singleton_method(rb_mGC, "disable", rb_gc_disable, 0);
2446     rb_define_singleton_method(rb_mGC, "stress", gc_stress_get, 0);
2447     rb_define_singleton_method(rb_mGC, "stress=", gc_stress_set, 1);
2448     rb_define_singleton_method(rb_mGC, "count", gc_count, 0);
2449     rb_define_method(rb_mGC, "garbage_collect", rb_gc_start, 0);
2450
2451     rb_mObSpace = rb_define_module("ObjectSpace");
2452     rb_define_module_function(rb_mObSpace, "each_object", os_each_obj, -1);
2453     rb_define_module_function(rb_mObSpace, "garbage_collect", rb_gc_start, 0);
2454
2455     rb_define_module_function(rb_mObSpace, "define_finalizer", define_final, -1);
2456     rb_define_module_function(rb_mObSpace, "undefine_finalizer", undefine_final, 1);
2457
2458     rb_define_module_function(rb_mObSpace, "_id2ref", id2ref, 1);
2459
2460     nomem_error = rb_exc_new3(rb_eNoMemError,
2461                               rb_obj_freeze(rb_str_new2("failed to allocate memory")));
2462     OBJ_TAINT(nomem_error);
2463     OBJ_FREEZE(nomem_error);
2464
2465     rb_define_method(rb_mKernel, "hash", rb_obj_id, 0);
2466     rb_define_method(rb_mKernel, "__id__", rb_obj_id, 0);
2467     rb_define_method(rb_mKernel, "object_id", rb_obj_id, 0);
2468
2469     rb_define_module_function(rb_mObSpace, "count_objects", count_objects, -1);
2470
2471 #if CALC_EXACT_MALLOC_SIZE
2472     rb_define_singleton_method(rb_mGC, "malloc_allocated_size", gc_malloc_allocated_size, 0);
2473     rb_define_singleton_method(rb_mGC, "malloc_allocations", gc_malloc_allocations, 0);
2474 #endif
2475 }