src/mm/boehm-gc/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  * Copyright (C) 2007 Free Software Foundation, Inc
   6
   7  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   8  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   9  *
  10  * Permission is hereby granted to use or copy this program
  11  * for any purpose,  provided the above notices are retained on all copies.
  12  * Permission to modify the code and to distribute modified code is granted,
  13  * provided the above notices are retained, and a notice that the code was
  14  * modified is included with the above copyright notice.
  15  */
  16 /* Boehm, February 1, 1996 1:19 pm PST */
  17
  18 #include "config.h"
  19
  20 # define I_HIDE_POINTERS
  21 # include "private/gc_pmark.h"
  22
  23 # ifdef FINALIZE_ON_DEMAND
  24     int GC_finalize_on_demand = 1;
  25 # else
  26     int GC_finalize_on_demand = 0;
  27 # endif
  28
  29 # ifdef JAVA_FINALIZATION
  30     int GC_java_finalization = 1;
  31 # else
  32     int GC_java_finalization = 0;
  33 # endif
  34
  35 /* Type of mark procedure used for marking from finalizable object.     */
  36 /* This procedure normally does not mark the object, only its           */
  37 /* descendents.                                                         */
  38 typedef void finalization_mark_proc(/* ptr_t finalizable_obj_ptr */);
  39
  40 # define HASH3(addr,size,log_size) \
  41     ((((word)(addr) >> 3) ^ ((word)(addr) >> (3+(log_size)))) \
  42     & ((size) - 1))
  43 #define HASH2(addr,log_size) HASH3(addr, 1 << log_size, log_size)
  44
  45 struct hash_chain_entry {
  46     word hidden_key;
  47     struct hash_chain_entry * next;
  48 };
  49
  50 unsigned GC_finalization_failures = 0;
  51         /* Number of finalization requests that failed for lack of memory. */
  52
  53 static struct disappearing_link {
  54     struct hash_chain_entry prolog;
  55 #   define dl_hidden_link prolog.hidden_key
  56                                 /* Field to be cleared.         */
  57 #   define dl_next(x) (struct disappearing_link *)((x) -> prolog.next)
  58 #   define dl_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  59
  60     word dl_hidden_obj;         /* Pointer to object base       */
  61 } **dl_head = 0;
  62
  63 static signed_word log_dl_table_size = -1;
  64                         /* Binary log of                                */
  65                         /* current size of array pointed to by dl_head. */
  66                         /* -1 ==> size is 0.                            */
  67
  68 word GC_dl_entries = 0; /* Number of entries currently in disappearing  */
  69                         /* link table.                                  */
  70
  71 static struct finalizable_object {
  72     struct hash_chain_entry prolog;
  73 #   define fo_hidden_base prolog.hidden_key
  74                                 /* Pointer to object base.      */
  75                                 /* No longer hidden once object */
  76                                 /* is on finalize_now queue.    */
  77 #   define fo_next(x) (struct finalizable_object *)((x) -> prolog.next)
  78 #   define fo_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  79     GC_finalization_proc fo_fn; /* Finalizer.                   */
  80     ptr_t fo_client_data;
  81     word fo_object_size;        /* In bytes.                    */
  82     finalization_mark_proc * fo_mark_proc;      /* Mark-through procedure */
  83 } **fo_head = 0;
  84
  85 struct finalizable_object * GC_finalize_now = 0;
  86         /* LIst of objects that should be finalized now.        */
  87
  88 static signed_word log_fo_table_size = -1;
  89
  90 word GC_fo_entries = 0;
  91
  92 void GC_push_finalizer_structures(void)
  93 {
  94     GC_push_all((ptr_t)(&dl_head), (ptr_t)(&dl_head) + sizeof(word));
  95     GC_push_all((ptr_t)(&fo_head), (ptr_t)(&fo_head) + sizeof(word));
  96     GC_push_all((ptr_t)(&GC_finalize_now),
  97                 (ptr_t)(&GC_finalize_now) + sizeof(word));
  98 }
  99
 100 /* Double the size of a hash table. *size_ptr is the log of its current */
 101 /* size.  May be a noop.                                                */
 102 /* *table is a pointer to an array of hash headers.  If we succeed, we  */
 103 /* update both *table and *log_size_ptr.                                */
 104 /* Lock is held.  Signals are disabled.                                 */
 105 void GC_grow_table(struct hash_chain_entry ***table,
 106                    signed_word *log_size_ptr)
 107 {
 108     register word i;
 109     register struct hash_chain_entry *p;
 110     signed_word log_old_size = *log_size_ptr;
 111     signed_word log_new_size = log_old_size + 1;
 112     word old_size = ((log_old_size == -1)? 0: (1 << log_old_size));
 113     word new_size = (word)1 << log_new_size;
 114     /* FIXME: Power of 2 size often gets rounded up to one more page. */
 115     struct hash_chain_entry **new_table = (struct hash_chain_entry **)
 116         GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(
 117                 (size_t)new_size * sizeof(struct hash_chain_entry *), NORMAL);
 118
 119     if (new_table == 0) {
 120         if (*table == 0) {
 121             ABORT("Insufficient space for initial table allocation");
 122         } else {
 123             return;
 124         }
 125     }
 126     for (i = 0; i < old_size; i++) {
 127       p = (*table)[i];
 128       while (p != 0) {
 129         ptr_t real_key = (ptr_t)REVEAL_POINTER(p -> hidden_key);
 130         struct hash_chain_entry *next = p -> next;
 131         size_t new_hash = HASH3(real_key, new_size, log_new_size);
 132
 133         p -> next = new_table[new_hash];
 134         new_table[new_hash] = p;
 135         p = next;
 136       }
 137     }
 138     *log_size_ptr = log_new_size;
 139     *table = new_table;
 140 }
 141
 142 int GC_register_disappearing_link(void * * link)
 143 {
 144     ptr_t base;
 145
 146     base = (ptr_t)GC_base((void *)link);
 147     if (base == 0)
 148         ABORT("Bad arg to GC_register_disappearing_link");
 149     return(GC_general_register_disappearing_link(link, base));
 150 }
 151
 152 int GC_general_register_disappearing_link(void * * link, void * obj)
 153 {
 154     struct disappearing_link *curr_dl;
 155     size_t index;
 156     struct disappearing_link * new_dl;
 157     DCL_LOCK_STATE;
 158
 159     if ((word)link & (ALIGNMENT-1))
 160         ABORT("Bad arg to GC_general_register_disappearing_link");
 161 #   ifdef THREADS
 162         LOCK();
 163 #   endif
 164     if (log_dl_table_size == -1
 165         || GC_dl_entries > ((word)1 << log_dl_table_size)) {
 166         GC_grow_table((struct hash_chain_entry ***)(&dl_head),
 167                       &log_dl_table_size);
 168         if (GC_print_stats) {
 169             GC_log_printf("Grew dl table to %u entries\n",
 170                       (1 << log_dl_table_size));
 171         }
 172     }
 173     index = HASH2(link, log_dl_table_size);
 174     curr_dl = dl_head[index];
 175     for (curr_dl = dl_head[index]; curr_dl != 0; curr_dl = dl_next(curr_dl)) {
 176         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 177             curr_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 178 #           ifdef THREADS
 179                 UNLOCK();
 180 #           endif
 181             return(1);
 182         }
 183     }
 184     new_dl = (struct disappearing_link *)
 185         GC_INTERNAL_MALLOC(sizeof(struct disappearing_link),NORMAL);
 186     if (0 == new_dl) {
 187 #     ifdef THREADS
 188         UNLOCK();
 189 #     endif
 190       new_dl = (struct disappearing_link *)
 191               GC_oom_fn(sizeof(struct disappearing_link));
 192       if (0 == new_dl) {
 193         GC_finalization_failures++;
 194         return(2);
 195       }
 196       /* It's not likely we'll make it here, but ... */
 197 #     ifdef THREADS
 198         LOCK();
 199 #     endif
 200     }
 201     new_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 202     new_dl -> dl_hidden_link = HIDE_POINTER(link);
 203     dl_set_next(new_dl, dl_head[index]);
 204     dl_head[index] = new_dl;
 205     GC_dl_entries++;
 206 #   ifdef THREADS
 207         UNLOCK();
 208 #   endif
 209     return(0);
 210 }
 211
 212 int GC_unregister_disappearing_link(void * * link)
 213 {
 214     struct disappearing_link *curr_dl, *prev_dl;
 215     size_t index;
 216     DCL_LOCK_STATE;
 217
 218     LOCK();
 219     index = HASH2(link, log_dl_table_size);
 220     if (((word)link & (ALIGNMENT-1))) goto out;
 221     prev_dl = 0; curr_dl = dl_head[index];
 222     while (curr_dl != 0) {
 223         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 224             if (prev_dl == 0) {
 225                 dl_head[index] = dl_next(curr_dl);
 226             } else {
 227                 dl_set_next(prev_dl, dl_next(curr_dl));
 228             }
 229             GC_dl_entries--;
 230             UNLOCK();
 231 #           ifdef DBG_HDRS_ALL
 232               dl_set_next(curr_dl, 0);
 233 #           else
 234               GC_free((void *)curr_dl);
 235 #           endif
 236             return(1);
 237         }
 238         prev_dl = curr_dl;
 239         curr_dl = dl_next(curr_dl);
 240     }
 241 out:
 242     UNLOCK();
 243     return(0);
 244 }
 245
 246 /* Possible finalization_marker procedures.  Note that mark stack       */
 247 /* overflow is handled by the caller, and is not a disaster.            */
 248 GC_API void GC_normal_finalize_mark_proc(ptr_t p)
 249 {
 250     hdr * hhdr = HDR(p);
 251
 252     PUSH_OBJ(p, hhdr, GC_mark_stack_top,
 253              &(GC_mark_stack[GC_mark_stack_size]));
 254 }
 255
 256 /* This only pays very partial attention to the mark descriptor.        */
 257 /* It does the right thing for normal and atomic objects, and treats    */
 258 /* most others as normal.                                               */
 259 GC_API void GC_ignore_self_finalize_mark_proc(ptr_t p)
 260 {
 261     hdr * hhdr = HDR(p);
 262     word descr = hhdr -> hb_descr;
 263     ptr_t q, r;
 264     ptr_t scan_limit;
 265     ptr_t target_limit = p + hhdr -> hb_sz - 1;
 266
 267     if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) {
 268        scan_limit = p + descr - sizeof(word);
 269     } else {
 270        scan_limit = target_limit + 1 - sizeof(word);
 271     }
 272     for (q = p; q <= scan_limit; q += ALIGNMENT) {
 273         r = *(ptr_t *)q;
 274         if (r < p || r > target_limit) {
 275             GC_PUSH_ONE_HEAP(r, q);
 276         }
 277     }
 278 }
 279
 280 /*ARGSUSED*/
 281 GC_API void GC_null_finalize_mark_proc(ptr_t p)
 282 {
 283 }
 284
 285 /* Possible finalization_marker procedures.  Note that mark stack       */
 286 /* overflow is handled by the caller, and is not a disaster.            */
 287
 288 /* GC_unreachable_finalize_mark_proc is an alias for normal marking,    */
 289 /* but it is explicitly tested for, and triggers different              */
 290 /* behavior.  Objects registered in this way are not finalized          */
 291 /* if they are reachable by other finalizable objects, eve if those     */
 292 /* other objects specify no ordering.                                   */
 293 GC_API void GC_unreachable_finalize_mark_proc(ptr_t p)
 294 {
 295     GC_normal_finalize_mark_proc(p);
 296 }
 297
 298
 299
 300 /* Register a finalization function.  See gc.h for details.     */
 301 /* in the nonthreads case, we try to avoid disabling signals,   */
 302 /* since it can be expensive.  Threads packages typically       */
 303 /* make it cheaper.                                             */
 304 /* The last parameter is a procedure that determines            */
 305 /* marking for finalization ordering.  Any objects marked       */
 306 /* by that procedure will be guaranteed to not have been        */
 307 /* finalized when this finalizer is invoked.                    */
 308 GC_API void GC_register_finalizer_inner(void * obj,
 309                                         GC_finalization_proc fn, void *cd,
 310                                         GC_finalization_proc *ofn, void **ocd,
 311                                         finalization_mark_proc mp)
 312 {
 313     ptr_t base;
 314     struct finalizable_object * curr_fo, * prev_fo;
 315     size_t index;
 316     struct finalizable_object *new_fo;
 317     hdr *hhdr;
 318     DCL_LOCK_STATE;
 319
 320 #   ifdef THREADS
 321         LOCK();
 322 #   endif
 323     if (log_fo_table_size == -1
 324         || GC_fo_entries > ((word)1 << log_fo_table_size)) {
 325         GC_grow_table((struct hash_chain_entry ***)(&fo_head),
 326                       &log_fo_table_size);
 327         if (GC_print_stats) {
 328             GC_log_printf("Grew fo table to %u entries\n",
 329                           (1 << log_fo_table_size));
 330         }
 331     }
 332     /* in the THREADS case signals are disabled and we hold allocation  */
 333     /* lock; otherwise neither is true.  Proceed carefully.             */
 334     base = (ptr_t)obj;
 335     index = HASH2(base, log_fo_table_size);
 336     prev_fo = 0; curr_fo = fo_head[index];
 337     while (curr_fo != 0) {
 338         GC_ASSERT(GC_size(curr_fo) >= sizeof(struct finalizable_object));
 339         if (curr_fo -> fo_hidden_base == HIDE_POINTER(base)) {
 340             /* Interruption by a signal in the middle of this   */
 341             /* should be safe.  The client may see only *ocd    */
 342             /* updated, but we'll declare that to be his        */
 343             /* problem.                                         */
 344             if (ocd) *ocd = (void *) (curr_fo -> fo_client_data);
 345             if (ofn) *ofn = curr_fo -> fo_fn;
 346             /* Delete the structure for base. */
 347                 if (prev_fo == 0) {
 348                   fo_head[index] = fo_next(curr_fo);
 349                 } else {
 350                   fo_set_next(prev_fo, fo_next(curr_fo));
 351                 }
 352             if (fn == 0) {
 353                 GC_fo_entries--;
 354                   /* May not happen if we get a signal.  But a high     */
 355                   /* estimate will only make the table larger than      */
 356                   /* necessary.                                         */
 357 #               if !defined(THREADS) && !defined(DBG_HDRS_ALL)
 358                   GC_free((void *)curr_fo);
 359 #               endif
 360             } else {
 361                 curr_fo -> fo_fn = fn;
 362                 curr_fo -> fo_client_data = (ptr_t)cd;
 363                 curr_fo -> fo_mark_proc = mp;
 364                 /* Reinsert it.  We deleted it first to maintain        */
 365                 /* consistency in the event of a signal.                */
 366                 if (prev_fo == 0) {
 367                   fo_head[index] = curr_fo;
 368                 } else {
 369                   fo_set_next(prev_fo, curr_fo);
 370                 }
 371             }
 372 #           ifdef THREADS
 373                 UNLOCK();
 374 #           endif
 375             return;
 376         }
 377         prev_fo = curr_fo;
 378         curr_fo = fo_next(curr_fo);
 379     }
 380     if (ofn) *ofn = 0;
 381     if (ocd) *ocd = 0;
 382     if (fn == 0) {
 383 #       ifdef THREADS
 384             UNLOCK();
 385 #       endif
 386         return;
 387     }
 388     GET_HDR(base, hhdr);
 389     if (0 == hhdr) {
 390       /* We won't collect it, hence finalizer wouldn't be run. */
 391 #     ifdef THREADS
 392           UNLOCK();
 393 #     endif
 394       return;
 395     }
 396     new_fo = (struct finalizable_object *)
 397         GC_INTERNAL_MALLOC(sizeof(struct finalizable_object),NORMAL);
 398     if (EXPECT(0 == new_fo, FALSE)) {
 399 #     ifdef THREADS
 400         UNLOCK();
 401 #     endif
 402       new_fo = (struct finalizable_object *)
 403               GC_oom_fn(sizeof(struct finalizable_object));
 404       if (0 == new_fo) {
 405         GC_finalization_failures++;
 406         return;
 407       }
 408       /* It's not likely we'll make it here, but ... */
 409 #     ifdef THREADS
 410         LOCK();
 411 #     endif
 412     }
 413     GC_ASSERT(GC_size(new_fo) >= sizeof(struct finalizable_object));
 414     new_fo -> fo_hidden_base = (word)HIDE_POINTER(base);
 415     new_fo -> fo_fn = fn;
 416     new_fo -> fo_client_data = (ptr_t)cd;
 417     new_fo -> fo_object_size = hhdr -> hb_sz;
 418     new_fo -> fo_mark_proc = mp;
 419     fo_set_next(new_fo, fo_head[index]);
 420     GC_fo_entries++;
 421     fo_head[index] = new_fo;
 422 #   ifdef THREADS
 423         UNLOCK();
 424 #   endif
 425 }
 426
 427 void GC_register_finalizer(void * obj,
 428                                GC_finalization_proc fn, void * cd,
 429                                GC_finalization_proc *ofn, void ** ocd)
 430 {
 431     GC_register_finalizer_inner(obj, fn, cd, ofn,
 432                                 ocd, GC_normal_finalize_mark_proc);
 433 }
 434
 435 void GC_register_finalizer_ignore_self(void * obj,
 436                                GC_finalization_proc fn, void * cd,
 437                                GC_finalization_proc *ofn, void ** ocd)
 438 {
 439     GC_register_finalizer_inner(obj, fn, cd, ofn,
 440                                 ocd, GC_ignore_self_finalize_mark_proc);
 441 }
 442
 443 void GC_register_finalizer_no_order(void * obj,
 444                                GC_finalization_proc fn, void * cd,
 445                                GC_finalization_proc *ofn, void ** ocd)
 446 {
 447     GC_register_finalizer_inner(obj, fn, cd, ofn,
 448                                 ocd, GC_null_finalize_mark_proc);
 449 }
 450
 451 static GC_bool need_unreachable_finalization = FALSE;
 452         /* Avoid the work if this isn't used.   */
 453
 454 void GC_register_finalizer_unreachable(void * obj,
 455                                GC_finalization_proc fn, void * cd,
 456                                GC_finalization_proc *ofn, void ** ocd)
 457 {
 458     need_unreachable_finalization = TRUE;
 459     GC_ASSERT(GC_java_finalization);
 460     GC_register_finalizer_inner(obj, fn, cd, ofn,
 461                                 ocd, GC_unreachable_finalize_mark_proc);
 462 }
 463
 464 #ifndef NO_DEBUGGING
 465 void GC_dump_finalization(void)
 466 {
 467     struct disappearing_link * curr_dl;
 468     struct finalizable_object * curr_fo;
 469     ptr_t real_ptr, real_link;
 470     int dl_size = (log_dl_table_size == -1 ) ? 0 : (1 << log_dl_table_size);
 471     int fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 472     int i;
 473
 474     GC_printf("Disappearing links:\n");
 475     for (i = 0; i < dl_size; i++) {
 476       for (curr_dl = dl_head[i]; curr_dl != 0; curr_dl = dl_next(curr_dl)) {
 477         real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 478         real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 479         GC_printf("Object: %p, Link:%p\n", real_ptr, real_link);
 480       }
 481     }
 482     GC_printf("Finalizers:\n");
 483     for (i = 0; i < fo_size; i++) {
 484       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 485         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 486         GC_printf("Finalizable object: %p\n", real_ptr);
 487       }
 488     }
 489 }
 490 #endif
 491
 492 /* Called with world stopped.  Cause disappearing links to disappear,   */
 493 /* and invoke finalizers.                                               */
 494 void GC_finalize(void)
 495 {
 496     struct disappearing_link * curr_dl, * prev_dl, * next_dl;
 497     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 498     ptr_t real_ptr, real_link;
 499     size_t i;
 500     size_t dl_size = (log_dl_table_size == -1 ) ? 0 : (1 << log_dl_table_size);
 501     size_t fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 502
 503   /* Make disappearing links disappear */
 504     for (i = 0; i < dl_size; i++) {
 505       curr_dl = dl_head[i];
 506       prev_dl = 0;
 507       while (curr_dl != 0) {
 508         real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 509         real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 510         if (!GC_is_marked(real_ptr)) {
 511             *(word *)real_link = 0;
 512             next_dl = dl_next(curr_dl);
 513             if (prev_dl == 0) {
 514                 dl_head[i] = next_dl;
 515             } else {
 516                 dl_set_next(prev_dl, next_dl);
 517             }
 518             GC_clear_mark_bit((ptr_t)curr_dl);
 519             GC_dl_entries--;
 520             curr_dl = next_dl;
 521         } else {
 522             prev_dl = curr_dl;
 523             curr_dl = dl_next(curr_dl);
 524         }
 525       }
 526     }
 527   /* Mark all objects reachable via chains of 1 or more pointers        */
 528   /* from finalizable objects.                                          */
 529     GC_ASSERT(GC_mark_state == MS_NONE);
 530     for (i = 0; i < fo_size; i++) {
 531       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 532         GC_ASSERT(GC_size(curr_fo) >= sizeof(struct finalizable_object));
 533         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 534         if (!GC_is_marked(real_ptr)) {
 535             GC_MARKED_FOR_FINALIZATION(real_ptr);
 536             GC_MARK_FO(real_ptr, curr_fo -> fo_mark_proc);
 537             if (GC_is_marked(real_ptr)) {
 538                 WARN("Finalization cycle involving %lx\n", real_ptr);
 539             }
 540         }
 541       }
 542     }
 543   /* Enqueue for finalization all objects that are still                */
 544   /* unreachable.                                                       */
 545     GC_bytes_finalized = 0;
 546     for (i = 0; i < fo_size; i++) {
 547       curr_fo = fo_head[i];
 548       prev_fo = 0;
 549       while (curr_fo != 0) {
 550         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 551         if (!GC_is_marked(real_ptr)) {
 552             if (!GC_java_finalization) {
 553               GC_set_mark_bit(real_ptr);
 554             }
 555             /* Delete from hash table */
 556               next_fo = fo_next(curr_fo);
 557               if (prev_fo == 0) {
 558                 fo_head[i] = next_fo;
 559               } else {
 560                 fo_set_next(prev_fo, next_fo);
 561               }
 562               GC_fo_entries--;
 563             /* Add to list of objects awaiting finalization.    */
 564               fo_set_next(curr_fo, GC_finalize_now);
 565               GC_finalize_now = curr_fo;
 566               /* unhide object pointer so any future collections will   */
 567               /* see it.                                                */
 568               curr_fo -> fo_hidden_base =
 569                         (word) REVEAL_POINTER(curr_fo -> fo_hidden_base);
 570               GC_bytes_finalized +=
 571                         curr_fo -> fo_object_size
 572                         + sizeof(struct finalizable_object);
 573             GC_ASSERT(GC_is_marked(GC_base((ptr_t)curr_fo)));
 574             curr_fo = next_fo;
 575         } else {
 576             prev_fo = curr_fo;
 577             curr_fo = fo_next(curr_fo);
 578         }
 579       }
 580     }
 581
 582   if (GC_java_finalization) {
 583     /* make sure we mark everything reachable from objects finalized
 584        using the no_order mark_proc */
 585       for (curr_fo = GC_finalize_now;
 586          curr_fo != NULL; curr_fo = fo_next(curr_fo)) {
 587         real_ptr = (ptr_t)curr_fo -> fo_hidden_base;
 588         if (!GC_is_marked(real_ptr)) {
 589             if (curr_fo -> fo_mark_proc == GC_null_finalize_mark_proc) {
 590                 GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 591             }
 592             if (curr_fo -> fo_mark_proc != GC_unreachable_finalize_mark_proc) {
 593                 GC_set_mark_bit(real_ptr);
 594             }
 595         }
 596       }
 597
 598     /* now revive finalize-when-unreachable objects reachable from
 599        other finalizable objects */
 600       if (need_unreachable_finalization) {
 601         curr_fo = GC_finalize_now;
 602         prev_fo = 0;
 603         while (curr_fo != 0) {
 604           next_fo = fo_next(curr_fo);
 605           if (curr_fo -> fo_mark_proc == GC_unreachable_finalize_mark_proc) {
 606             real_ptr = (ptr_t)curr_fo -> fo_hidden_base;
 607             if (!GC_is_marked(real_ptr)) {
 608               GC_set_mark_bit(real_ptr);
 609             } else {
 610               if (prev_fo == 0)
 611                 GC_finalize_now = next_fo;
 612               else
 613                 fo_set_next(prev_fo, next_fo);
 614
 615               curr_fo -> fo_hidden_base =
 616                         (word) HIDE_POINTER(curr_fo -> fo_hidden_base);
 617               GC_bytes_finalized -=
 618                         curr_fo -> fo_object_size + sizeof(struct finalizable_object);
 619
 620               i = HASH2(real_ptr, log_fo_table_size);
 621               fo_set_next (curr_fo, fo_head[i]);
 622               GC_fo_entries++;
 623               fo_head[i] = curr_fo;
 624               curr_fo = prev_fo;
 625             }
 626           }
 627           prev_fo = curr_fo;
 628           curr_fo = next_fo;
 629         }
 630       }
 631   }
 632
 633   /* Remove dangling disappearing links. */
 634     for (i = 0; i < dl_size; i++) {
 635       curr_dl = dl_head[i];
 636       prev_dl = 0;
 637       while (curr_dl != 0) {
 638         real_link = GC_base((ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link));
 639         if (real_link != 0 && !GC_is_marked(real_link)) {
 640             next_dl = dl_next(curr_dl);
 641             if (prev_dl == 0) {
 642                 dl_head[i] = next_dl;
 643             } else {
 644                 dl_set_next(prev_dl, next_dl);
 645             }
 646             GC_clear_mark_bit((ptr_t)curr_dl);
 647             GC_dl_entries--;
 648             curr_dl = next_dl;
 649         } else {
 650             prev_dl = curr_dl;
 651             curr_dl = dl_next(curr_dl);
 652         }
 653       }
 654     }
 655 }
 656
 657 #ifndef JAVA_FINALIZATION_NOT_NEEDED
 658
 659 /* Enqueue all remaining finalizers to be run - Assumes lock is
 660  * held, and signals are disabled */
 661 void GC_enqueue_all_finalizers(void)
 662 {
 663     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 664     ptr_t real_ptr;
 665     register int i;
 666     int fo_size;
 667
 668     fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
 669     GC_bytes_finalized = 0;
 670     for (i = 0; i < fo_size; i++) {
 671         curr_fo = fo_head[i];
 672         prev_fo = 0;
 673       while (curr_fo != 0) {
 674           real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 675           GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 676           GC_set_mark_bit(real_ptr);
 677
 678           /* Delete from hash table */
 679           next_fo = fo_next(curr_fo);
 680           if (prev_fo == 0) {
 681               fo_head[i] = next_fo;
 682           } else {
 683               fo_set_next(prev_fo, next_fo);
 684           }
 685           GC_fo_entries--;
 686
 687           /* Add to list of objects awaiting finalization.      */
 688           fo_set_next(curr_fo, GC_finalize_now);
 689           GC_finalize_now = curr_fo;
 690
 691           /* unhide object pointer so any future collections will       */
 692           /* see it.                                            */
 693           curr_fo -> fo_hidden_base =
 694                         (word) REVEAL_POINTER(curr_fo -> fo_hidden_base);
 695
 696           GC_bytes_finalized +=
 697                 curr_fo -> fo_object_size + sizeof(struct finalizable_object);
 698           curr_fo = next_fo;
 699         }
 700     }
 701
 702     return;
 703 }
 704
 705 /* Invoke all remaining finalizers that haven't yet been run.
 706  * This is needed for strict compliance with the Java standard,
 707  * which can make the runtime guarantee that all finalizers are run.
 708  * Unfortunately, the Java standard implies we have to keep running
 709  * finalizers until there are no more left, a potential infinite loop.
 710  * YUCK.
 711  * Note that this is even more dangerous than the usual Java
 712  * finalizers, in that objects reachable from static variables
 713  * may have been finalized when these finalizers are run.
 714  * Finalizers run at this point must be prepared to deal with a
 715  * mostly broken world.
 716  * This routine is externally callable, so is called without
 717  * the allocation lock.
 718  */
 719 GC_API void GC_finalize_all(void)
 720 {
 721     DCL_LOCK_STATE;
 722
 723     LOCK();
 724     while (GC_fo_entries > 0) {
 725       GC_enqueue_all_finalizers();
 726       UNLOCK();
 727       GC_INVOKE_FINALIZERS();
 728       LOCK();
 729     }
 730     UNLOCK();
 731 }
 732 #endif
 733
 734 /* Returns true if it is worth calling GC_invoke_finalizers. (Useful if */
 735 /* finalizers can only be called from some kind of `safe state' and     */
 736 /* getting into that safe state is expensive.)                          */
 737 int GC_should_invoke_finalizers(void)
 738 {
 739     return GC_finalize_now != 0;
 740 }
 741
 742 /* Invoke finalizers for all objects that are ready to be finalized.    */
 743 /* Should be called without allocation lock.                            */
 744 int GC_invoke_finalizers(void)
 745 {
 746     struct finalizable_object * curr_fo;
 747     int count = 0;
 748     word bytes_freed_before;
 749     DCL_LOCK_STATE;
 750
 751     while (GC_finalize_now != 0) {
 752 #       ifdef THREADS
 753             LOCK();
 754 #       endif
 755         if (count == 0) {
 756             bytes_freed_before = GC_bytes_freed;
 757             /* Don't do this outside, since we need the lock. */
 758         }
 759         curr_fo = GC_finalize_now;
 760 #       ifdef THREADS
 761             if (curr_fo != 0) GC_finalize_now = fo_next(curr_fo);
 762             UNLOCK();
 763             if (curr_fo == 0) break;
 764 #       else
 765             GC_finalize_now = fo_next(curr_fo);
 766 #       endif
 767         fo_set_next(curr_fo, 0);
 768         (*(curr_fo -> fo_fn))((ptr_t)(curr_fo -> fo_hidden_base),
 769                               curr_fo -> fo_client_data);
 770         curr_fo -> fo_client_data = 0;
 771         ++count;
 772 #       ifdef UNDEFINED
 773             /* This is probably a bad idea.  It throws off accounting if */
 774             /* nearly all objects are finalizable.  O.w. it shouldn't    */
 775             /* matter.                                                   */
 776             GC_free((void *)curr_fo);
 777 #       endif
 778     }
 779     /* bytes_freed_before is initialized whenever count != 0 */
 780     if (count != 0 && bytes_freed_before != GC_bytes_freed) {
 781         LOCK();
 782         GC_finalizer_bytes_freed += (GC_bytes_freed - bytes_freed_before);
 783         UNLOCK();
 784     }
 785     return count;
 786 }
 787
 788 void (* GC_finalizer_notifier)() = (void (*) (void))0;
 789
 790 static GC_word last_finalizer_notification = 0;
 791
 792 void GC_notify_or_invoke_finalizers(void)
 793 {
 794     /* This is a convenient place to generate backtraces if appropriate, */
 795     /* since that code is not callable with the allocation lock.         */
 796 #   if defined(KEEP_BACK_PTRS) || defined(MAKE_BACK_GRAPH)
 797       static word last_back_trace_gc_no = 1;    /* Skip first one. */
 798
 799       if (GC_gc_no > last_back_trace_gc_no) {
 800         word i;
 801
 802 #       ifdef KEEP_BACK_PTRS
 803           LOCK();
 804           /* Stops when GC_gc_no wraps; that's OK.      */
 805           last_back_trace_gc_no = (word)(-1);  /* disable others. */
 806           for (i = 0; i < GC_backtraces; ++i) {
 807               /* FIXME: This tolerates concurrent heap mutation,        */
 808               /* which may cause occasional mysterious results.         */
 809               /* We need to release the GC lock, since GC_print_callers */
 810               /* acquires it.  It probably shouldn't.                   */
 811               UNLOCK();
 812               GC_generate_random_backtrace_no_gc();
 813               LOCK();
 814           }
 815           last_back_trace_gc_no = GC_gc_no;
 816           UNLOCK();
 817 #       endif
 818 #       ifdef MAKE_BACK_GRAPH
 819           if (GC_print_back_height)
 820             GC_print_back_graph_stats();
 821 #       endif
 822       }
 823 #   endif
 824     if (GC_finalize_now == 0) return;
 825     if (!GC_finalize_on_demand) {
 826         (void) GC_invoke_finalizers();
 827 #       ifndef THREADS
 828           GC_ASSERT(GC_finalize_now == 0);
 829 #       endif   /* Otherwise GC can run concurrently and add more */
 830         return;
 831     }
 832     if (GC_finalizer_notifier != (void (*) (void))0
 833         && last_finalizer_notification != GC_gc_no) {
 834         last_finalizer_notification = GC_gc_no;
 835         GC_finalizer_notifier();
 836     }
 837 }
 838
 839 void * GC_call_with_alloc_lock(GC_fn_type fn, void * client_data)
 840 {
 841     void * result;
 842     DCL_LOCK_STATE;
 843
 844 #   ifdef THREADS
 845       LOCK();
 846       /* FIXME - This looks wrong!! */
 847       SET_LOCK_HOLDER();
 848 #   endif
 849     result = (*fn)(client_data);
 850 #   ifdef THREADS
 851 #     ifndef GC_ASSERTIONS
 852         UNSET_LOCK_HOLDER();
 853 #     endif /* o.w. UNLOCK() does it implicitly */
 854       UNLOCK();
 855 #   endif
 856     return(result);
 857 }
 858
 859 #if !defined(NO_DEBUGGING)
 860
 861 void GC_print_finalization_stats(void)
 862 {
 863     struct finalizable_object *fo = GC_finalize_now;
 864     size_t ready = 0;
 865
 866     GC_printf("%u finalization table entries; %u disappearing links\n",
 867                GC_fo_entries, GC_dl_entries);
 868     for (; 0 != fo; fo = fo_next(fo)) ++ready;
 869     GC_printf("%u objects are eligible for immediate finalization\n", ready);
 870 }
 871
 872 #endif /* NO_DEBUGGING */