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