libgc/finalize.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1996 by Xerox Corporation.  All rights reserved.
   4  * Copyright (c) 1996-1999 by Silicon Graphics.  All rights reserved.
   5
   6  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   7  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   8  *
   9  * Permission is hereby granted to use or copy this program
  10  * for any purpose,  provided the above notices are retained on all copies.
  11  * Permission to modify the code and to distribute modified code is granted,
  12  * provided the above notices are retained, and a notice that the code was
  13  * modified is included with the above copyright notice.
  14  */
  15 /* Boehm, February 1, 1996 1:19 pm PST */
  16 # define I_HIDE_POINTERS
  17 # include "private/gc_pmark.h"
  18
  19 # ifdef FINALIZE_ON_DEMAND
  20     int GC_finalize_on_demand = 1;
  21 # else
  22     int GC_finalize_on_demand = 0;
  23 # endif
  24
  25 # ifdef JAVA_FINALIZATION
  26     int GC_java_finalization = 1;
  27 # else
  28     int GC_java_finalization = 0;
  29 # endif
  30
  31 /* Type of mark procedure used for marking from finalizable object.     */
  32 /* This procedure normally does not mark the object, only its           */
  33 /* descendents.                                                         */
  34 typedef void finalization_mark_proc(/* ptr_t finalizable_obj_ptr */);
  35
  36 # define HASH3(addr,size,log_size) \
  37     ((((word)(addr) >> 3) ^ ((word)(addr) >> (3+(log_size)))) \
  38     & ((size) - 1))
  39 #define HASH2(addr,log_size) HASH3(addr, 1 << log_size, log_size)
  40
  41 struct hash_chain_entry {
  42     word hidden_key;
  43     struct hash_chain_entry * next;
  44 };
  45
  46 unsigned GC_finalization_failures = 0;
  47         /* Number of finalization requests that failed for lack of memory. */
  48
  49 struct disappearing_link {
  50     struct hash_chain_entry prolog;
  51 #   define dl_hidden_link prolog.hidden_key
  52                                 /* Field to be cleared.         */
  53 #   define dl_next(x) (struct disappearing_link *)((x) -> prolog.next)
  54 #   define dl_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  55
  56     word dl_hidden_obj;         /* Pointer to object base       */
  57 };
  58
  59 struct dl_hashtbl_s {
  60     struct disappearing_link **head;
  61     signed_word log_size;
  62     word entries;
  63 };
  64
  65 /* Forward decls. */
  66 static int GC_register_disappearing_link_inner(struct dl_hashtbl_s *dl_hashtbl, GC_PTR * link, GC_PTR obj);
  67 static int GC_unregister_disappearing_link_inner(struct dl_hashtbl_s *dl_hashtbl, GC_PTR * link);
  68
  69 static struct dl_hashtbl_s GC_dl_hashtbl = {
  70     /* head */ NULL, /* log_size */ -1, /* entries */ 0 };
  71
  72 static struct dl_hashtbl_s GC_ll_hashtbl = { NULL, -1, 0 };
  73
  74
  75 static struct finalizable_object {
  76     struct hash_chain_entry prolog;
  77 #   define fo_hidden_base prolog.hidden_key
  78                                 /* Pointer to object base.      */
  79                                 /* No longer hidden once object */
  80                                 /* is on finalize_now queue.    */
  81 #   define fo_next(x) (struct finalizable_object *)((x) -> prolog.next)
  82 #   define fo_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  83     GC_finalization_proc fo_fn; /* Finalizer.                   */
  84     ptr_t fo_client_data;
  85     word fo_object_size;        /* In bytes.                    */
  86     finalization_mark_proc * fo_mark_proc;      /* Mark-through procedure */
  87 } **fo_head = 0;
  88
  89 struct finalizable_object * GC_finalize_now = 0;
  90         /* LIst of objects that should be finalized now.        */
  91
  92 static signed_word log_fo_table_size = -1;
  93
  94 word GC_fo_entries = 0;
  95
  96 void GC_push_finalizer_structures GC_PROTO((void))
  97 {
  98     GC_push_all((ptr_t)(&GC_ll_hashtbl.head),
  99                 (ptr_t)(&GC_ll_hashtbl.head) + sizeof(word));
 100     GC_push_all((ptr_t)(&GC_dl_hashtbl.head),
 101                 (ptr_t)(&GC_dl_hashtbl.head) + sizeof(word));
 102     GC_push_all((ptr_t)(&fo_head), (ptr_t)(&fo_head) + sizeof(word));
 103     GC_push_all((ptr_t)(&GC_finalize_now),
 104                 (ptr_t)(&GC_finalize_now) + sizeof(word));
 105 }
 106
 107 /* Double the size of a hash table. *size_ptr is the log of its current */
 108 /* size.  May be a noop.                                                */
 109 /* *table is a pointer to an array of hash headers.  If we succeed, we  */
 110 /* update both *table and *log_size_ptr.                                */
 111 /* Lock is held.  Signals are disabled.                                 */
 112 void GC_grow_table(table, log_size_ptr)
 113 struct hash_chain_entry ***table;
 114 signed_word * log_size_ptr;
 115 {
 116     register word i;
 117     register struct hash_chain_entry *p;
 118     int log_old_size = *log_size_ptr;
 119     register int log_new_size = log_old_size + 1;
 120     word old_size = ((log_old_size == -1)? 0: (1 << log_old_size));
 121     register word new_size = 1 << log_new_size;
 122     struct hash_chain_entry **new_table = (struct hash_chain_entry **)
 123         GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(
 124                 (size_t)new_size * sizeof(struct hash_chain_entry *), NORMAL);
 125
 126     if (new_table == 0) {
 127         if (table == 0) {
 128             ABORT("Insufficient space for initial table allocation");
 129         } else {
 130             return;
 131         }
 132     }
 133     for (i = 0; i < old_size; i++) {
 134       p = (*table)[i];
 135       while (p != 0) {
 136         register ptr_t real_key = (ptr_t)REVEAL_POINTER(p -> hidden_key);
 137         register struct hash_chain_entry *next = p -> next;
 138         register int new_hash = HASH3(real_key, new_size, log_new_size);
 139
 140         p -> next = new_table[new_hash];
 141         new_table[new_hash] = p;
 142         p = next;
 143       }
 144     }
 145     *log_size_ptr = log_new_size;
 146     *table = new_table;
 147 }
 148
 149 # if defined(__STDC__) || defined(__cplusplus)
 150     int GC_register_disappearing_link(GC_PTR * link)
 151 # else
 152     int GC_register_disappearing_link(link)
 153     GC_PTR * link;
 154 # endif
 155 {
 156     ptr_t base;
 157
 158     base = (ptr_t)GC_base((GC_PTR)link);
 159     if (base == 0)
 160         ABORT("Bad arg to GC_register_disappearing_link");
 161     return(GC_general_register_disappearing_link(link, base));
 162 }
 163
 164 # if defined(__STDC__) || defined(__cplusplus)
 165     int GC_general_register_disappearing_link(GC_PTR * link,
 166                                               GC_PTR obj)
 167 # else
 168     int GC_general_register_disappearing_link(link, obj)
 169     GC_PTR * link;
 170     GC_PTR obj;
 171 # endif
 172 {
 173     return GC_register_disappearing_link_inner(&GC_dl_hashtbl, link, obj);
 174 }
 175
 176 # if defined(__STDC__) || defined(__cplusplus)
 177     static int GC_register_disappearing_link_inner(struct dl_hashtbl_s *dl_hashtbl, GC_PTR * link,
 178                                               GC_PTR obj)
 179 # else
 180     static int GC_register_disappearing_link_inner(dl_hashtbl, link, obj)
 181         struct dl_hashtbl_s *dl_hashtbl
 182     GC_PTR * link;
 183     GC_PTR obj;
 184 # endif
 185 {
 186     struct disappearing_link *curr_dl;
 187     int index;
 188     struct disappearing_link * new_dl;
 189     DCL_LOCK_STATE;
 190
 191     if ((word)link & (ALIGNMENT-1))
 192         ABORT("Bad arg to GC_general_register_disappearing_link");
 193 #   ifdef THREADS
 194         DISABLE_SIGNALS();
 195         LOCK();
 196 #   endif
 197     if (dl_hashtbl -> log_size == -1
 198         || dl_hashtbl -> entries > ((word)1 << dl_hashtbl -> log_size)) {
 199 #       ifndef THREADS
 200             DISABLE_SIGNALS();
 201 #       endif
 202         GC_grow_table((struct hash_chain_entry ***)(&dl_hashtbl -> head),
 203                       &dl_hashtbl -> log_size);
 204 #       ifdef CONDPRINT
 205           if (GC_print_stats) {
 206             GC_printf1("Grew dl table to %lu entries\n",
 207                         (unsigned long)(1 << dl_hashtbl -> log_size));
 208           }
 209 #       endif
 210 #       ifndef THREADS
 211             ENABLE_SIGNALS();
 212 #       endif
 213     }
 214     index = HASH2(link, dl_hashtbl -> log_size);
 215     curr_dl = dl_hashtbl -> head[index];
 216     for (curr_dl = dl_hashtbl -> head[index]; curr_dl != 0; curr_dl = dl_next(curr_dl)) {
 217         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 218             curr_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 219 #           ifdef THREADS
 220                 UNLOCK();
 221                 ENABLE_SIGNALS();
 222 #           endif
 223             return(1);
 224         }
 225     }
 226     new_dl = (struct disappearing_link *)
 227         GC_INTERNAL_MALLOC(sizeof(struct disappearing_link),NORMAL);
 228     if (0 == new_dl) {
 229 #     ifdef THREADS
 230         UNLOCK();
 231         ENABLE_SIGNALS();
 232 #     endif
 233       new_dl = (struct disappearing_link *)
 234               GC_oom_fn(sizeof(struct disappearing_link));
 235       if (0 == new_dl) {
 236         GC_finalization_failures++;
 237         return(0);
 238       }
 239       /* It's not likely we'll make it here, but ... */
 240 #     ifdef THREADS
 241         DISABLE_SIGNALS();
 242         LOCK();
 243 #     endif
 244     }
 245     new_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 246     new_dl -> dl_hidden_link = HIDE_POINTER(link);
 247     dl_set_next(new_dl, dl_hashtbl -> head[index]);
 248     dl_hashtbl -> head[index] = new_dl;
 249     dl_hashtbl -> entries++;
 250 #   ifdef THREADS
 251         UNLOCK();
 252         ENABLE_SIGNALS();
 253 #   endif
 254     return(0);
 255 }
 256
 257 # if defined(__STDC__) || defined(__cplusplus)
 258     int GC_unregister_disappearing_link(GC_PTR * link)
 259 # else
 260     int GC_unregister_disappearing_link(link)
 261     GC_PTR * link;
 262 # endif
 263 {
 264         return GC_unregister_disappearing_link_inner(&GC_dl_hashtbl, link);
 265 }
 266
 267 # if defined(__STDC__) || defined(__cplusplus)
 268     static int GC_unregister_disappearing_link_inner(struct dl_hashtbl_s *dl_hashtbl, GC_PTR * link)
 269 # else
 270     static int GC_unregister_disappearing_link_inner(dl_hashtbl, link)
 271         struct dl_hashtbl_s *dl_hashtbl;
 272     GC_PTR * link;
 273 # endif
 274 {
 275     struct disappearing_link *curr_dl, *prev_dl;
 276     int index;
 277     DCL_LOCK_STATE;
 278
 279     DISABLE_SIGNALS();
 280     LOCK();
 281     index = HASH2(link, dl_hashtbl->log_size);
 282     if (((unsigned long)link & (ALIGNMENT-1))) goto out;
 283     prev_dl = 0; curr_dl = dl_hashtbl -> head[index];
 284     while (curr_dl != 0) {
 285         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 286             if (prev_dl == 0) {
 287                 dl_hashtbl -> head[index] = dl_next(curr_dl);
 288             } else {
 289                 dl_set_next(prev_dl, dl_next(curr_dl));
 290             }
 291             dl_hashtbl -> entries--;
 292             UNLOCK();
 293             ENABLE_SIGNALS();
 294 #           ifdef DBG_HDRS_ALL
 295               dl_set_next(curr_dl, 0);
 296 #           else
 297               GC_free((GC_PTR)curr_dl);
 298 #           endif
 299             return(1);
 300         }
 301         prev_dl = curr_dl;
 302         curr_dl = dl_next(curr_dl);
 303     }
 304 out:
 305     UNLOCK();
 306     ENABLE_SIGNALS();
 307     return(0);
 308 }
 309
 310 /* toggleref support */
 311 typedef struct {
 312         GC_PTR strong_ref;
 313         GC_hidden_pointer weak_ref;
 314 } GCToggleRef;
 315
 316 static GC_ToggleRefStatus (*GC_toggleref_callback) (GC_PTR obj);
 317 static GCToggleRef *GC_toggleref_array;
 318 static int GC_toggleref_array_size;
 319 static int GC_toggleref_array_capacity;
 320
 321
 322 void
 323 GC_process_togglerefs (void)
 324 {
 325         int i, w;
 326         int toggle_ref_counts [3] = { 0, 0, 0 };
 327
 328         for (i = w = 0; i < GC_toggleref_array_size; ++i) {
 329                 GC_ToggleRefStatus res;
 330                 GCToggleRef r = GC_toggleref_array [i];
 331
 332                 GC_PTR obj;
 333
 334                 if (r.strong_ref)
 335                         obj = r.strong_ref;
 336                 else if (r.weak_ref)
 337                         obj = REVEAL_POINTER (r.weak_ref);
 338                 else
 339                         continue;
 340
 341                 res = GC_toggleref_callback (obj);
 342                 ++toggle_ref_counts [res];
 343                 switch (res) {
 344                 case GC_TOGGLE_REF_DROP:
 345                         break;
 346                 case GC_TOGGLE_REF_STRONG:
 347                         GC_toggleref_array [w].strong_ref = obj;
 348                         GC_toggleref_array [w].weak_ref = (GC_hidden_pointer)NULL;
 349                         ++w;
 350                         break;
 351                 case GC_TOGGLE_REF_WEAK:
 352                         GC_toggleref_array [w].strong_ref = NULL;
 353                         GC_toggleref_array [w].weak_ref = HIDE_POINTER (obj);
 354                         ++w;
 355                         break;
 356                 default:
 357                         ABORT("Invalid callback result");
 358                 }
 359         }
 360
 361         for (i = w; i < GC_toggleref_array_size; ++i) {
 362                 GC_toggleref_array [w].strong_ref = NULL;
 363                 GC_toggleref_array [w].weak_ref = (GC_hidden_pointer)NULL;
 364         }
 365
 366         GC_toggleref_array_size = w;
 367 }
 368
 369 /* Finalizer proc support */
 370 static void (*GC_object_finalized_proc) (GC_PTR obj);
 371
 372 void
 373 GC_set_await_finalize_proc (void (*proc) (GC_PTR obj))
 374 {
 375         GC_object_finalized_proc = proc;
 376 }
 377
 378
 379 static void push_and_mark_object (GC_PTR p)
 380 {
 381     hdr * hhdr = HDR(p);
 382
 383     PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top,
 384              &(GC_mark_stack[GC_mark_stack_size]));
 385
 386         while (!GC_mark_stack_empty()) MARK_FROM_MARK_STACK();
 387         GC_set_mark_bit (p);
 388         if (GC_mark_state != MS_NONE)
 389         while (!GC_mark_some((ptr_t)0)) {}
 390 }
 391
 392 static void GC_mark_togglerefs ()
 393 {
 394         int i;
 395         if (!GC_toggleref_array)
 396                 return;
 397
 398         GC_set_mark_bit ((GC_PTR)GC_toggleref_array);
 399         for (i = 0; i < GC_toggleref_array_size; ++i) {
 400                 if (GC_toggleref_array [i].strong_ref) {
 401                         GC_PTR object = GC_toggleref_array [i].strong_ref;
 402
 403                         push_and_mark_object (object);
 404                 }
 405         }
 406 }
 407
 408 static void GC_clear_togglerefs ()
 409 {
 410         int i;
 411         for (i = 0; i < GC_toggleref_array_size; ++i) {
 412                 if (GC_toggleref_array [i].weak_ref) {
 413                         GC_PTR object = REVEAL_POINTER (GC_toggleref_array [i].weak_ref);
 414
 415                         if (!GC_is_marked (object)) {
 416                                 GC_toggleref_array [i].weak_ref = (GC_hidden_pointer)NULL; /* We defer compaction to only happen on the callback step. */
 417                         } else {
 418                                 /*No need to copy, boehm is non-moving */
 419                         }
 420                 }
 421         }
 422 }
 423
 424
 425
 426 void GC_set_toggleref_func(GC_ToggleRefStatus (*proccess_toggleref) (GC_PTR obj))
 427 {
 428         GC_toggleref_callback = proccess_toggleref;
 429 }
 430
 431 static GC_bool
 432 ensure_toggleref_capacity (int capacity)
 433 {
 434         if (!GC_toggleref_array) {
 435                 GC_toggleref_array_capacity = 32;
 436                 GC_toggleref_array = (GCToggleRef *) GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE (GC_toggleref_array_capacity * sizeof (GCToggleRef), NORMAL);
 437                 if (!GC_toggleref_array)
 438                         return FALSE;
 439         }
 440         if (GC_toggleref_array_size + capacity >= GC_toggleref_array_capacity) {
 441                 GCToggleRef *tmp;
 442                 int old_capacity = GC_toggleref_array_capacity;
 443                 while (GC_toggleref_array_capacity < GC_toggleref_array_size + capacity)
 444                         GC_toggleref_array_capacity *= 2;
 445
 446                 tmp = (GCToggleRef *) GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE (GC_toggleref_array_capacity * sizeof (GCToggleRef), NORMAL);
 447                 if (!tmp)
 448                         return FALSE;
 449                 memcpy (tmp, GC_toggleref_array, GC_toggleref_array_size * sizeof (GCToggleRef));
 450                 GC_INTERNAL_FREE (GC_toggleref_array);
 451                 GC_toggleref_array = tmp;
 452         }
 453         return TRUE;
 454 }
 455
 456 int
 457 GC_toggleref_add (GC_PTR object, int strong_ref)
 458 {
 459         int res = GC_SUCCESS;
 460     DCL_LOCK_STATE;
 461 # ifdef THREADS
 462         DISABLE_SIGNALS();
 463         LOCK();
 464 # endif
 465
 466         if (!GC_toggleref_callback)
 467                 goto end;
 468
 469         if (!ensure_toggleref_capacity (1)) {
 470                 res = GC_NO_MEMORY;
 471                 goto end;
 472         }
 473         GC_toggleref_array [GC_toggleref_array_size].strong_ref = strong_ref ? object : NULL;
 474         GC_toggleref_array [GC_toggleref_array_size].weak_ref = strong_ref ? (GC_hidden_pointer)NULL : HIDE_POINTER (object);
 475         ++GC_toggleref_array_size;
 476
 477 end:
 478 # ifdef THREADS
 479         UNLOCK();
 480         ENABLE_SIGNALS();
 481 # endif
 482         return res;
 483 }
 484
 485
 486
 487 # if defined(__STDC__) || defined(__cplusplus)
 488     int GC_register_long_link(GC_PTR * link, GC_PTR obj)
 489 # else
 490     int GC_register_long_link(link, obj)
 491     GC_PTR * link;
 492         GC_PTR obj;
 493 # endif
 494 {
 495     return GC_register_disappearing_link_inner(&GC_ll_hashtbl, link, obj);
 496 }
 497
 498 # if defined(__STDC__) || defined(__cplusplus)
 499     int GC_unregister_long_link(GC_PTR * link)
 500 # else
 501     int GC_unregister_long_link(link)
 502     GC_PTR * link;
 503 # endif
 504 {
 505         return GC_unregister_disappearing_link_inner(&GC_ll_hashtbl, link);
 506 }
 507
 508 /* Possible finalization_marker procedures.  Note that mark stack       */
 509 /* overflow is handled by the caller, and is not a disaster.            */
 510 GC_API void GC_normal_finalize_mark_proc(p)
 511 ptr_t p;
 512 {
 513     hdr * hhdr = HDR(p);
 514
 515     PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top,
 516              &(GC_mark_stack[GC_mark_stack_size]));
 517 }
 518
 519 /* This only pays very partial attention to the mark descriptor.        */
 520 /* It does the right thing for normal and atomic objects, and treats    */
 521 /* most others as normal.                                               */
 522 GC_API void GC_ignore_self_finalize_mark_proc(p)
 523 ptr_t p;
 524 {
 525     hdr * hhdr = HDR(p);
 526     word descr = hhdr -> hb_descr;
 527     ptr_t q, r;
 528     ptr_t scan_limit;
 529     ptr_t target_limit = p + WORDS_TO_BYTES(hhdr -> hb_sz) - 1;
 530
 531     if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) {
 532        scan_limit = p + descr - sizeof(word);
 533     } else {
 534        scan_limit = target_limit + 1 - sizeof(word);
 535     }
 536     for (q = p; q <= scan_limit; q += ALIGNMENT) {
 537         r = *(ptr_t *)q;
 538         if (r < p || r > target_limit) {
 539             GC_PUSH_ONE_HEAP((word)r, q);
 540         }
 541     }
 542 }
 543
 544 /*ARGSUSED*/
 545 GC_API void GC_null_finalize_mark_proc(p)
 546 ptr_t p;
 547 {
 548 }
 549
 550
 551
 552 /* Register a finalization function.  See gc.h for details.     */
 553 /* in the nonthreads case, we try to avoid disabling signals,   */
 554 /* since it can be expensive.  Threads packages typically       */
 555 /* make it cheaper.                                             */
 556 /* The last parameter is a procedure that determines            */
 557 /* marking for finalization ordering.  Any objects marked       */
 558 /* by that procedure will be guaranteed to not have been        */
 559 /* finalized when this finalizer is invoked.                    */
 560 GC_API void GC_register_finalizer_inner(obj, fn, cd, ofn, ocd, mp)
 561 GC_PTR obj;
 562 GC_finalization_proc fn;
 563 GC_PTR cd;
 564 GC_finalization_proc * ofn;
 565 GC_PTR * ocd;
 566 finalization_mark_proc * mp;
 567 {
 568     ptr_t base;
 569     struct finalizable_object * curr_fo, * prev_fo;
 570     int index;
 571     struct finalizable_object *new_fo;
 572     hdr *hhdr;
 573     DCL_LOCK_STATE;
 574
 575 #   ifdef THREADS
 576         DISABLE_SIGNALS();
 577         LOCK();
 578 #   endif
 579     if (log_fo_table_size == -1
 580         || GC_fo_entries > ((word)1 << log_fo_table_size)) {
 581 #       ifndef THREADS
 582             DISABLE_SIGNALS();
 583 #       endif
 584         GC_grow_table((struct hash_chain_entry ***)(&fo_head),
 585                       &log_fo_table_size);
 586 #       ifdef CONDPRINT
 587           if (GC_print_stats) {
 588             GC_printf1("Grew fo table to %lu entries\n",
 589                         (unsigned long)(1 << log_fo_table_size));
 590           }
 591 #       endif
 592 #       ifndef THREADS
 593             ENABLE_SIGNALS();
 594 #       endif
 595     }
 596     /* in the THREADS case signals are disabled and we hold allocation  */
 597     /* lock; otherwise neither is true.  Proceed carefully.             */
 598     base = (ptr_t)obj;
 599     index = HASH2(base, log_fo_table_size);
 600     prev_fo = 0; curr_fo = fo_head[index];
 601     while (curr_fo != 0) {
 602         if (curr_fo -> fo_hidden_base == HIDE_POINTER(base)) {
 603             /* Interruption by a signal in the middle of this   */
 604             /* should be safe.  The client may see only *ocd    */
 605             /* updated, but we'll declare that to be his        */
 606             /* problem.                                         */
 607             if (ocd) *ocd = (GC_PTR) curr_fo -> fo_client_data;
 608             if (ofn) *ofn = curr_fo -> fo_fn;
 609             /* Delete the structure for base. */
 610                 if (prev_fo == 0) {
 611                   fo_head[index] = fo_next(curr_fo);
 612                 } else {
 613                   fo_set_next(prev_fo, fo_next(curr_fo));
 614                 }
 615             if (fn == 0) {
 616                 GC_fo_entries--;
 617                   /* May not happen if we get a signal.  But a high     */
 618                   /* estimate will only make the table larger than      */
 619                   /* necessary.                                         */
 620 #               if !defined(THREADS) && !defined(DBG_HDRS_ALL)
 621                   GC_free((GC_PTR)curr_fo);
 622 #               endif
 623             } else {
 624                 curr_fo -> fo_fn = fn;
 625                 curr_fo -> fo_client_data = (ptr_t)cd;
 626                 curr_fo -> fo_mark_proc = mp;
 627                 /* Reinsert it.  We deleted it first to maintain        */
 628                 /* consistency in the event of a signal.                */
 629                 if (prev_fo == 0) {
 630                   fo_head[index] = curr_fo;
 631                 } else {
 632                   fo_set_next(prev_fo, curr_fo);
 633                 }
 634             }
 635 #           ifdef THREADS
 636                 UNLOCK();
 637                 ENABLE_SIGNALS();
 638 #           endif
 639             return;
 640         }
 641         prev_fo = curr_fo;
 642         curr_fo = fo_next(curr_fo);
 643     }
 644     if (ofn) *ofn = 0;
 645     if (ocd) *ocd = 0;
 646     if (fn == 0) {
 647 #       ifdef THREADS
 648             UNLOCK();
 649             ENABLE_SIGNALS();
 650 #       endif
 651         return;
 652     }
 653     GET_HDR(base, hhdr);
 654     if (0 == hhdr) {
 655       /* We won't collect it, hence finalizer wouldn't be run. */
 656 #     ifdef THREADS
 657           UNLOCK();
 658           ENABLE_SIGNALS();
 659 #     endif
 660       return;
 661     }
 662     new_fo = (struct finalizable_object *)
 663         GC_INTERNAL_MALLOC(sizeof(struct finalizable_object),NORMAL);
 664     if (0 == new_fo) {
 665 #     ifdef THREADS
 666         UNLOCK();
 667         ENABLE_SIGNALS();
 668 #     endif
 669       new_fo = (struct finalizable_object *)
 670               GC_oom_fn(sizeof(struct finalizable_object));
 671       if (0 == new_fo) {
 672         GC_finalization_failures++;
 673         return;
 674       }
 675       /* It's not likely we'll make it here, but ... */
 676 #     ifdef THREADS
 677         DISABLE_SIGNALS();
 678         LOCK();
 679 #     endif
 680     }
 681     new_fo -> fo_hidden_base = (word)HIDE_POINTER(base);
 682     new_fo -> fo_fn = fn;
 683     new_fo -> fo_client_data = (ptr_t)cd;
 684     new_fo -> fo_object_size = hhdr -> hb_sz;
 685     new_fo -> fo_mark_proc = mp;
 686     fo_set_next(new_fo, fo_head[index]);
 687     GC_fo_entries++;
 688     fo_head[index] = new_fo;
 689 #   ifdef THREADS
 690         UNLOCK();
 691         ENABLE_SIGNALS();
 692 #   endif
 693 }
 694
 695 # if defined(__STDC__)
 696     void GC_register_finalizer(void * obj,
 697                                GC_finalization_proc fn, void * cd,
 698                                GC_finalization_proc *ofn, void ** ocd)
 699 # else
 700     void GC_register_finalizer(obj, fn, cd, ofn, ocd)
 701     GC_PTR obj;
 702     GC_finalization_proc fn;
 703     GC_PTR cd;
 704     GC_finalization_proc * ofn;
 705     GC_PTR * ocd;
 706 # endif
 707 {
 708     GC_register_finalizer_inner(obj, fn, cd, ofn,
 709                                 ocd, GC_normal_finalize_mark_proc);
 710 }
 711
 712 # if defined(__STDC__)
 713     void GC_register_finalizer_ignore_self(void * obj,
 714                                GC_finalization_proc fn, void * cd,
 715                                GC_finalization_proc *ofn, void ** ocd)
 716 # else
 717     void GC_register_finalizer_ignore_self(obj, fn, cd, ofn, ocd)
 718     GC_PTR obj;
 719     GC_finalization_proc fn;
 720     GC_PTR cd;
 721     GC_finalization_proc * ofn;
 722     GC_PTR * ocd;
 723 # endif
 724 {
 725     GC_register_finalizer_inner(obj, fn, cd, ofn,
 726                                 ocd, GC_ignore_self_finalize_mark_proc);
 727 }
 728
 729 # if defined(__STDC__)
 730     void GC_register_finalizer_no_order(void * obj,
 731                                GC_finalization_proc fn, void * cd,
 732                                GC_finalization_proc *ofn, void ** ocd)
 733 # else
 734     void GC_register_finalizer_no_order(obj, fn, cd, ofn, ocd)
 735     GC_PTR obj;
 736     GC_finalization_proc fn;
 737     GC_PTR cd;
 738     GC_finalization_proc * ofn;
 739     GC_PTR * ocd;
 740 # endif
 741 {
 742     GC_register_finalizer_inner(obj, fn, cd, ofn,
 743                                 ocd, GC_null_finalize_mark_proc);
 744 }
 745
 746 #ifndef NO_DEBUGGING
 747
 748 static void GC_dump_finalization_links(struct dl_hashtbl_s *dl_hashtbl)
 749 {
 750   struct disappearing_link *curr_dl;
 751   ptr_t real_ptr, real_link;
 752   size_t dl_size = dl_hashtbl->log_size == -1 ? 0 :
 753                               1 << dl_hashtbl->log_size;
 754   int i;
 755
 756   for (i = 0; i < dl_size; i++) {
 757     for (curr_dl = dl_hashtbl -> head[i]; curr_dl != 0;
 758          curr_dl = dl_next(curr_dl)) {
 759       real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 760       real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 761       GC_printf2("Object: %lx, link: %lx\n", real_ptr, real_link);
 762     }
 763   }
 764 }
 765
 766 void GC_dump_finalization()
 767 {
 768     struct finalizable_object * curr_fo;
 769     ptr_t real_ptr;
 770     int fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 771     int i;
 772
 773     GC_printf0("Disappearing (short) links:\n");
 774     GC_dump_finalization_links(&GC_dl_hashtbl);
 775     GC_printf0("Disappearing long links:\n");
 776     GC_dump_finalization_links(&GC_ll_hashtbl);
 777
 778     GC_printf0("Finalizers:\n");
 779     for (i = 0; i < fo_size; i++) {
 780       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 781         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 782         GC_printf1("Finalizable object: 0x%lx\n", real_ptr);
 783       }
 784     }
 785 }
 786 #endif
 787
 788 static void GC_make_disappearing_links_disappear(struct dl_hashtbl_s *dl_hashtbl)
 789 {
 790     struct disappearing_link * curr_dl, * prev_dl, * next_dl;
 791     ptr_t real_ptr, real_link;
 792     register int i;
 793     int dl_size = (dl_hashtbl -> log_size == -1 ) ? 0 : (1 << dl_hashtbl -> log_size);
 794
 795     for (i = 0; i < dl_size; i++) {
 796       curr_dl = dl_hashtbl -> head[i];
 797       prev_dl = 0;
 798       while (curr_dl != 0) {
 799         real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 800         real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 801         if (!GC_is_marked(real_ptr)) {
 802             *(word *)real_link = 0;
 803             next_dl = dl_next(curr_dl);
 804             if (prev_dl == 0) {
 805                 dl_hashtbl -> head[i] = next_dl;
 806             } else {
 807                 dl_set_next(prev_dl, next_dl);
 808             }
 809             GC_clear_mark_bit((ptr_t)curr_dl);
 810             dl_hashtbl -> entries--;
 811             curr_dl = next_dl;
 812         } else {
 813             prev_dl = curr_dl;
 814             curr_dl = dl_next(curr_dl);
 815         }
 816       }
 817     }
 818 }
 819
 820 static void GC_remove_dangling_disappearing_links(struct dl_hashtbl_s *dl_hashtbl)
 821 {
 822     struct disappearing_link * curr_dl, * prev_dl, * next_dl;
 823     ptr_t real_ptr, real_link;
 824     register int i;
 825     int dl_size = (dl_hashtbl -> log_size == -1 ) ? 0 : (1 << dl_hashtbl -> log_size);
 826
 827     for (i = 0; i < dl_size; i++) {
 828       curr_dl = dl_hashtbl -> head[i];
 829       prev_dl = 0;
 830       while (curr_dl != 0) {
 831         real_link = GC_base((ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link));
 832         if (real_link != 0 && !GC_is_marked(real_link)) {
 833             next_dl = dl_next(curr_dl);
 834             if (prev_dl == 0) {
 835                 dl_hashtbl -> head[i] = next_dl;
 836             } else {
 837                 dl_set_next(prev_dl, next_dl);
 838             }
 839             GC_clear_mark_bit((ptr_t)curr_dl);
 840             dl_hashtbl -> entries--;
 841             curr_dl = next_dl;
 842         } else {
 843             prev_dl = curr_dl;
 844             curr_dl = dl_next(curr_dl);
 845         }
 846       }
 847     }
 848 }
 849
 850 /* Called with world stopped.  Cause disappearing links to disappear,   */
 851 /* and invoke finalizers.                                               */
 852 void GC_finalize()
 853 {
 854     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 855     ptr_t real_ptr;
 856     register int i;
 857     int fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 858
 859         GC_mark_togglerefs();
 860
 861   /* Make non-tracking disappearing links disappear */
 862         GC_make_disappearing_links_disappear(&GC_dl_hashtbl);
 863
 864   /* Mark all objects reachable via chains of 1 or more pointers        */
 865   /* from finalizable objects.                                          */
 866     GC_ASSERT(GC_mark_state == MS_NONE);
 867     for (i = 0; i < fo_size; i++) {
 868       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 869         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 870         if (!GC_is_marked(real_ptr)) {
 871             GC_MARKED_FOR_FINALIZATION(real_ptr);
 872             GC_MARK_FO(real_ptr, curr_fo -> fo_mark_proc);
 873             if (GC_is_marked(real_ptr)) {
 874                 WARN("Finalization cycle involving %lx\n", real_ptr);
 875             }
 876         }
 877       }
 878     }
 879   /* Enqueue for finalization all objects that are still                */
 880   /* unreachable.                                                       */
 881     GC_words_finalized = 0;
 882     for (i = 0; i < fo_size; i++) {
 883       curr_fo = fo_head[i];
 884       prev_fo = 0;
 885       while (curr_fo != 0) {
 886         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 887         if (!GC_is_marked(real_ptr)) {
 888             if (!GC_java_finalization) {
 889               GC_set_mark_bit(real_ptr);
 890             }
 891             /* Delete from hash table */
 892               next_fo = fo_next(curr_fo);
 893               if (prev_fo == 0) {
 894                 fo_head[i] = next_fo;
 895               } else {
 896                 fo_set_next(prev_fo, next_fo);
 897               }
 898               GC_fo_entries--;
 899
 900                           if (GC_object_finalized_proc)
 901                                   GC_object_finalized_proc (real_ptr);
 902
 903             /* Add to list of objects awaiting finalization.    */
 904               fo_set_next(curr_fo, GC_finalize_now);
 905               GC_finalize_now = curr_fo;
 906               /* unhide object pointer so any future collections will   */
 907               /* see it.                                                */
 908               curr_fo -> fo_hidden_base =
 909                         (word) REVEAL_POINTER(curr_fo -> fo_hidden_base);
 910               GC_words_finalized +=
 911                         ALIGNED_WORDS(curr_fo -> fo_object_size)
 912                         + ALIGNED_WORDS(sizeof(struct finalizable_object));
 913             GC_ASSERT(GC_is_marked(GC_base((ptr_t)curr_fo)));
 914             curr_fo = next_fo;
 915         } else {
 916             prev_fo = curr_fo;
 917             curr_fo = fo_next(curr_fo);
 918         }
 919       }
 920     }
 921
 922   if (GC_java_finalization) {
 923     /* make sure we mark everything reachable from objects finalized
 924        using the no_order mark_proc */
 925       for (curr_fo = GC_finalize_now;
 926          curr_fo != NULL; curr_fo = fo_next(curr_fo)) {
 927         real_ptr = (ptr_t)curr_fo -> fo_hidden_base;
 928         if (!GC_is_marked(real_ptr)) {
 929             if (curr_fo -> fo_mark_proc == GC_null_finalize_mark_proc) {
 930                 GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 931             }
 932             GC_set_mark_bit(real_ptr);
 933         }
 934       }
 935   }
 936
 937   /* Remove dangling disappearing links. */
 938   GC_remove_dangling_disappearing_links(&GC_dl_hashtbl);
 939
 940         GC_clear_togglerefs ();
 941
 942   /* Make long links disappear and remove dangling ones. */
 943   GC_make_disappearing_links_disappear(&GC_ll_hashtbl);
 944   GC_remove_dangling_disappearing_links(&GC_ll_hashtbl);
 945 }
 946
 947 #ifndef JAVA_FINALIZATION_NOT_NEEDED
 948
 949 /* Enqueue all remaining finalizers to be run - Assumes lock is
 950  * held, and signals are disabled */
 951 void GC_enqueue_all_finalizers()
 952 {
 953     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 954     ptr_t real_ptr;
 955     register int i;
 956     int fo_size;
 957
 958     fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 959     GC_words_finalized = 0;
 960     for (i = 0; i < fo_size; i++) {
 961         curr_fo = fo_head[i];
 962         prev_fo = 0;
 963       while (curr_fo != 0) {
 964           real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 965           GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 966           GC_set_mark_bit(real_ptr);
 967
 968           /* Delete from hash table */
 969           next_fo = fo_next(curr_fo);
 970           if (prev_fo == 0) {
 971               fo_head[i] = next_fo;
 972           } else {
 973               fo_set_next(prev_fo, next_fo);
 974           }
 975           GC_fo_entries--;
 976
 977           /* Add to list of objects awaiting finalization.      */
 978           fo_set_next(curr_fo, GC_finalize_now);
 979           GC_finalize_now = curr_fo;
 980
 981           /* unhide object pointer so any future collections will       */
 982           /* see it.                                            */
 983           curr_fo -> fo_hidden_base =
 984                         (word) REVEAL_POINTER(curr_fo -> fo_hidden_base);
 985
 986           GC_words_finalized +=
 987                 ALIGNED_WORDS(curr_fo -> fo_object_size)
 988                         + ALIGNED_WORDS(sizeof(struct finalizable_object));
 989           curr_fo = next_fo;
 990         }
 991     }
 992
 993     return;
 994 }
 995
 996 /* Invoke all remaining finalizers that haven't yet been run.
 997  * This is needed for strict compliance with the Java standard,
 998  * which can make the runtime guarantee that all finalizers are run.
 999  * Unfortunately, the Java standard implies we have to keep running
1000  * finalizers until there are no more left, a potential infinite loop.
1001  * YUCK.
1002  * Note that this is even more dangerous than the usual Java
1003  * finalizers, in that objects reachable from static variables
1004  * may have been finalized when these finalizers are run.
1005  * Finalizers run at this point must be prepared to deal with a
1006  * mostly broken world.
1007  * This routine is externally callable, so is called without
1008  * the allocation lock.
1009  */
1010 GC_API void GC_finalize_all()
1011 {
1012     DCL_LOCK_STATE;
1013
1014     DISABLE_SIGNALS();
1015     LOCK();
1016     while (GC_fo_entries > 0) {
1017       GC_enqueue_all_finalizers();
1018       UNLOCK();
1019       ENABLE_SIGNALS();
1020       GC_INVOKE_FINALIZERS();
1021       DISABLE_SIGNALS();
1022       LOCK();
1023     }
1024     UNLOCK();
1025     ENABLE_SIGNALS();
1026 }
1027 #endif
1028
1029 /* Returns true if it is worth calling GC_invoke_finalizers. (Useful if */
1030 /* finalizers can only be called from some kind of `safe state' and     */
1031 /* getting into that safe state is expensive.)                          */
1032 int GC_should_invoke_finalizers GC_PROTO((void))
1033 {
1034     return GC_finalize_now != 0;
1035 }
1036
1037 /* Invoke finalizers for all objects that are ready to be finalized.    */
1038 /* Should be called without allocation lock.                            */
1039 int GC_invoke_finalizers()
1040 {
1041     struct finalizable_object * curr_fo;
1042     int count = 0;
1043     word mem_freed_before;
1044     DCL_LOCK_STATE;
1045
1046     while (GC_finalize_now != 0) {
1047 #       ifdef THREADS
1048             DISABLE_SIGNALS();
1049             LOCK();
1050 #       endif
1051         if (count == 0) {
1052             mem_freed_before = GC_mem_freed;
1053         }
1054         curr_fo = GC_finalize_now;
1055 #       ifdef THREADS
1056             if (curr_fo != 0) GC_finalize_now = fo_next(curr_fo);
1057             UNLOCK();
1058             ENABLE_SIGNALS();
1059             if (curr_fo == 0) break;
1060 #       else
1061             GC_finalize_now = fo_next(curr_fo);
1062 #       endif
1063         fo_set_next(curr_fo, 0);
1064         (*(curr_fo -> fo_fn))((ptr_t)(curr_fo -> fo_hidden_base),
1065                               curr_fo -> fo_client_data);
1066         curr_fo -> fo_client_data = 0;
1067         ++count;
1068 #       ifdef UNDEFINED
1069             /* This is probably a bad idea.  It throws off accounting if */
1070             /* nearly all objects are finalizable.  O.w. it shouldn't    */
1071             /* matter.                                                   */
1072             GC_free((GC_PTR)curr_fo);
1073 #       endif
1074     }
1075     if (count != 0 && mem_freed_before != GC_mem_freed) {
1076         LOCK();
1077         GC_finalizer_mem_freed += (GC_mem_freed - mem_freed_before);
1078         UNLOCK();
1079     }
1080     return count;
1081 }
1082
1083 void (* GC_finalizer_notifier)() = (void (*) GC_PROTO((void)))0;
1084
1085 static GC_word last_finalizer_notification = 0;
1086
1087 void GC_notify_or_invoke_finalizers GC_PROTO((void))
1088 {
1089     /* This is a convenient place to generate backtraces if appropriate, */
1090     /* since that code is not callable with the allocation lock.         */
1091 #   if defined(KEEP_BACK_PTRS) || defined(MAKE_BACK_GRAPH)
1092       static word last_back_trace_gc_no = 1;    /* Skip first one. */
1093
1094       if (GC_gc_no > last_back_trace_gc_no) {
1095         word i;
1096
1097 #       ifdef KEEP_BACK_PTRS
1098           LOCK();
1099           /* Stops when GC_gc_no wraps; that's OK.      */
1100           last_back_trace_gc_no = (word)(-1);  /* disable others. */
1101           for (i = 0; i < GC_backtraces; ++i) {
1102               /* FIXME: This tolerates concurrent heap mutation,        */
1103               /* which may cause occasional mysterious results.         */
1104               /* We need to release the GC lock, since GC_print_callers */
1105               /* acquires it.  It probably shouldn't.                   */
1106               UNLOCK();
1107               GC_generate_random_backtrace_no_gc();
1108               LOCK();
1109           }
1110           last_back_trace_gc_no = GC_gc_no;
1111           UNLOCK();
1112 #       endif
1113 #       ifdef MAKE_BACK_GRAPH
1114           if (GC_print_back_height)
1115             GC_print_back_graph_stats();
1116 #       endif
1117       }
1118 #   endif
1119     if (GC_finalize_now == 0) return;
1120     if (!GC_finalize_on_demand) {
1121         (void) GC_invoke_finalizers();
1122 #       ifndef THREADS
1123           GC_ASSERT(GC_finalize_now == 0);
1124 #       endif   /* Otherwise GC can run concurrently and add more */
1125         return;
1126     }
1127     if (GC_finalizer_notifier != (void (*) GC_PROTO((void)))0
1128         && last_finalizer_notification != GC_gc_no) {
1129         last_finalizer_notification = GC_gc_no;
1130         GC_finalizer_notifier();
1131     }
1132 }
1133
1134 # ifdef __STDC__
1135     GC_PTR GC_call_with_alloc_lock(GC_fn_type fn,
1136                                          GC_PTR client_data)
1137 # else
1138     GC_PTR GC_call_with_alloc_lock(fn, client_data)
1139     GC_fn_type fn;
1140     GC_PTR client_data;
1141 # endif
1142 {
1143     GC_PTR result;
1144     DCL_LOCK_STATE;
1145
1146 #   ifdef THREADS
1147       DISABLE_SIGNALS();
1148       LOCK();
1149       SET_LOCK_HOLDER();
1150 #   endif
1151     result = (*fn)(client_data);
1152 #   ifdef THREADS
1153 #     ifndef GC_ASSERTIONS
1154         UNSET_LOCK_HOLDER();
1155 #     endif /* o.w. UNLOCK() does it implicitly */
1156       UNLOCK();
1157       ENABLE_SIGNALS();
1158 #   endif
1159     return(result);
1160 }
1161
1162 #if !defined(NO_DEBUGGING)
1163
1164 void GC_print_finalization_stats()
1165 {
1166     struct finalizable_object *fo = GC_finalize_now;
1167     size_t ready = 0;
1168
1169     GC_printf3("%lu finalization table entries; %lu/%lu short/long disappearing links alive\n",
1170                GC_fo_entries, (unsigned long)GC_dl_hashtbl.entries, (unsigned long)GC_ll_hashtbl.entries);
1171     for (; 0 != fo; fo = fo_next(fo)) ++ready;
1172     GC_printf1("%lu objects are eligible for immediate finalization\n", ready);
1173 }
1174
1175 #endif /* NO_DEBUGGING */