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