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
  17 #include "private/gc_pmark.h"
  18
  19 #ifndef GC_NO_FINALIZATION
  20
  21 /* Type of mark procedure used for marking from finalizable object.     */
  22 /* This procedure normally does not mark the object, only its           */
  23 /* descendents.                                                         */
  24 typedef void (* finalization_mark_proc)(ptr_t /* finalizable_obj_ptr */);
  25
  26 #define HASH3(addr,size,log_size) \
  27         ((((word)(addr) >> 3) ^ ((word)(addr) >> (3 + (log_size)))) \
  28          & ((size) - 1))
  29 #define HASH2(addr,log_size) HASH3(addr, 1 << (log_size), log_size)
  30
  31 struct hash_chain_entry {
  32     word hidden_key;
  33     struct hash_chain_entry * next;
  34 };
  35
  36 STATIC struct disappearing_link {
  37     struct hash_chain_entry prolog;
  38 #   define dl_hidden_link prolog.hidden_key
  39                                 /* Field to be cleared.         */
  40 #   define dl_next(x) (struct disappearing_link *)((x) -> prolog.next)
  41 #   define dl_set_next(x, y) \
  42                 (void)((x)->prolog.next = (struct hash_chain_entry *)(y))
  43
  44     word dl_hidden_obj;         /* Pointer to object base       */
  45 };
  46
  47 STATIC struct dl_hashtbl_s {
  48     struct disappearing_link **head;
  49     signed_word log_size;
  50     word entries;
  51 } GC_dl_hashtbl = { /* head */ NULL, /* log_size */ -1, /* entries */ 0},
  52   GC_ll_hashtbl = { /* head */ NULL, /* log_size */ -1, /* entries */ 0};
  53
  54 STATIC struct finalizable_object {
  55     struct hash_chain_entry prolog;
  56 #   define fo_hidden_base prolog.hidden_key
  57                                 /* Pointer to object base.      */
  58                                 /* No longer hidden once object */
  59                                 /* is on finalize_now queue.    */
  60 #   define fo_next(x) (struct finalizable_object *)((x) -> prolog.next)
  61 #   define fo_set_next(x,y) ((x)->prolog.next = (struct hash_chain_entry *)(y))
  62     GC_finalization_proc fo_fn; /* Finalizer.                   */
  63     ptr_t fo_client_data;
  64     word fo_object_size;        /* In bytes.                    */
  65     finalization_mark_proc fo_mark_proc;        /* Mark-through procedure */
  66 } **GC_fo_head = 0;
  67
  68 STATIC struct finalizable_object * GC_finalize_now = 0;
  69         /* List of objects that should be finalized now.        */
  70
  71 static signed_word log_fo_table_size = -1;
  72
  73 GC_INNER void GC_push_finalizer_structures(void)
  74 {
  75     GC_ASSERT((word)&GC_dl_hashtbl.head % sizeof(word) == 0);
  76     GC_ASSERT((word)&GC_ll_hashtbl.head % sizeof(word) == 0);
  77     GC_ASSERT((word)&GC_fo_head % sizeof(word) == 0);
  78     GC_ASSERT((word)&GC_finalize_now % sizeof(word) == 0);
  79
  80     GC_push_all((ptr_t)(&GC_dl_hashtbl.head),
  81                 (ptr_t)(&GC_dl_hashtbl.head) + sizeof(word));
  82     GC_push_all((ptr_t)(&GC_ll_hashtbl.head),
  83                 (ptr_t)(&GC_ll_hashtbl.head) + sizeof(word));
  84     GC_push_all((ptr_t)(&GC_fo_head), (ptr_t)(&GC_fo_head) + sizeof(word));
  85     GC_push_all((ptr_t)(&GC_finalize_now),
  86                 (ptr_t)(&GC_finalize_now) + sizeof(word));
  87 }
  88
  89 /* Double the size of a hash table. *size_ptr is the log of its current */
  90 /* size.  May be a no-op.                                               */
  91 /* *table is a pointer to an array of hash headers.  If we succeed, we  */
  92 /* update both *table and *log_size_ptr.                                */
  93 /* Lock is held.                                                        */
  94 STATIC void GC_grow_table(struct hash_chain_entry ***table,
  95                           signed_word *log_size_ptr)
  96 {
  97     register word i;
  98     register struct hash_chain_entry *p;
  99     signed_word log_old_size = *log_size_ptr;
 100     signed_word log_new_size = log_old_size + 1;
 101     word old_size = ((log_old_size == -1)? 0: (1 << log_old_size));
 102     word new_size = (word)1 << log_new_size;
 103     /* FIXME: Power of 2 size often gets rounded up to one more page. */
 104     struct hash_chain_entry **new_table = (struct hash_chain_entry **)
 105         GC_INTERNAL_MALLOC_IGNORE_OFF_PAGE(
 106                 (size_t)new_size * sizeof(struct hash_chain_entry *), NORMAL);
 107
 108     if (new_table == 0) {
 109         if (*table == 0) {
 110             ABORT("Insufficient space for initial table allocation");
 111         } else {
 112             return;
 113         }
 114     }
 115     for (i = 0; i < old_size; i++) {
 116       p = (*table)[i];
 117       while (p != 0) {
 118         ptr_t real_key = GC_REVEAL_POINTER(p -> hidden_key);
 119         struct hash_chain_entry *next = p -> next;
 120         size_t new_hash = HASH3(real_key, new_size, log_new_size);
 121
 122         p -> next = new_table[new_hash];
 123         new_table[new_hash] = p;
 124         p = next;
 125       }
 126     }
 127     *log_size_ptr = log_new_size;
 128     *table = new_table;
 129 }
 130
 131 GC_API int GC_CALL GC_register_disappearing_link(void * * link)
 132 {
 133     ptr_t base;
 134
 135     base = (ptr_t)GC_base(link);
 136     if (base == 0)
 137         ABORT("Bad arg to GC_register_disappearing_link");
 138     return(GC_general_register_disappearing_link(link, base));
 139 }
 140
 141 GC_INLINE int GC_register_disappearing_link_inner(
 142                         struct dl_hashtbl_s *dl_hashtbl, void **link,
 143                         const void *obj)
 144 {
 145     struct disappearing_link *curr_dl;
 146     size_t index;
 147     struct disappearing_link * new_dl;
 148     DCL_LOCK_STATE;
 149
 150     LOCK();
 151     GC_ASSERT(obj != NULL && GC_base_C(obj) == obj);
 152     if (dl_hashtbl -> log_size == -1
 153         || dl_hashtbl -> entries > ((word)1 << dl_hashtbl -> log_size)) {
 154         GC_grow_table((struct hash_chain_entry ***)&dl_hashtbl -> head,
 155                       &dl_hashtbl -> log_size);
 156         GC_COND_LOG_PRINTF("Grew dl table to %u entries\n",
 157                            1 << (unsigned)dl_hashtbl -> log_size);
 158     }
 159     index = HASH2(link, dl_hashtbl -> log_size);
 160     for (curr_dl = dl_hashtbl -> head[index]; curr_dl != 0;
 161          curr_dl = dl_next(curr_dl)) {
 162         if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {
 163             curr_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);
 164             UNLOCK();
 165             return GC_DUPLICATE;
 166         }
 167     }
 168     new_dl = (struct disappearing_link *)
 169         GC_INTERNAL_MALLOC(sizeof(struct disappearing_link),NORMAL);
 170     if (0 == new_dl) {
 171       GC_oom_func oom_fn = GC_oom_fn;
 172       UNLOCK();
 173       new_dl = (struct disappearing_link *)
 174                 (*oom_fn)(sizeof(struct disappearing_link));
 175       if (0 == new_dl) {
 176         return GC_NO_MEMORY;
 177       }
 178       /* It's not likely we'll make it here, but ... */
 179       LOCK();
 180       /* Recalculate index since the table may grow.    */
 181       index = HASH2(link, dl_hashtbl -> log_size);
 182       /* Check again that our disappearing link not in the table. */
 183       for (curr_dl = dl_hashtbl -> head[index]; curr_dl != 0;
 184            curr_dl = dl_next(curr_dl)) {
 185         if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {
 186           curr_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);
 187           UNLOCK();
 188 #         ifndef DBG_HDRS_ALL
 189             /* Free unused new_dl returned by GC_oom_fn() */
 190             GC_free((void *)new_dl);
 191 #         endif
 192           return GC_DUPLICATE;
 193         }
 194       }
 195     }
 196     new_dl -> dl_hidden_obj = GC_HIDE_POINTER(obj);
 197     new_dl -> dl_hidden_link = GC_HIDE_POINTER(link);
 198     dl_set_next(new_dl, dl_hashtbl -> head[index]);
 199     dl_hashtbl -> head[index] = new_dl;
 200     dl_hashtbl -> entries++;
 201     UNLOCK();
 202     return GC_SUCCESS;
 203 }
 204
 205 GC_API int GC_CALL GC_general_register_disappearing_link(void * * link,
 206                                                          const void * obj)
 207 {
 208     if (((word)link & (ALIGNMENT-1)) != 0 || NULL == link)
 209         ABORT("Bad arg to GC_general_register_disappearing_link");
 210     return GC_register_disappearing_link_inner(&GC_dl_hashtbl, link, obj);
 211 }
 212
 213 GC_API int GC_CALL GC_register_long_link(void * * link, const void * obj)
 214 {
 215     if (((word)link & (ALIGNMENT-1)) != 0 || NULL == link)
 216         ABORT("Bad arg to GC_register_long_link");
 217     return GC_register_disappearing_link_inner(&GC_ll_hashtbl, link, obj);
 218 }
 219
 220 #ifdef DBG_HDRS_ALL
 221 # define FREE_DL_ENTRY(curr_dl) dl_set_next(curr_dl, NULL)
 222 #else
 223 # define FREE_DL_ENTRY(curr_dl) GC_free(curr_dl)
 224 #endif
 225
 226 /* Unregisters given link and returns the link entry to free.   */
 227 /* Assume the lock is held.                                     */
 228 GC_INLINE struct disappearing_link *GC_unregister_disappearing_link_inner(
 229                                 struct dl_hashtbl_s *dl_hashtbl, void **link)
 230 {
 231     struct disappearing_link *curr_dl;
 232     struct disappearing_link *prev_dl = NULL;
 233     size_t index = HASH2(link, dl_hashtbl->log_size);
 234
 235     for (curr_dl = dl_hashtbl -> head[index]; curr_dl;
 236          curr_dl = dl_next(curr_dl)) {
 237         if (curr_dl -> dl_hidden_link == GC_HIDE_POINTER(link)) {
 238             /* Remove found entry from the table. */
 239             if (NULL == prev_dl) {
 240                 dl_hashtbl -> head[index] = dl_next(curr_dl);
 241             } else {
 242                 dl_set_next(prev_dl, dl_next(curr_dl));
 243             }
 244             dl_hashtbl -> entries--;
 245             break;
 246         }
 247         prev_dl = curr_dl;
 248     }
 249     return curr_dl;
 250 }
 251
 252 GC_API int GC_CALL GC_unregister_disappearing_link(void * * link)
 253 {
 254     struct disappearing_link *curr_dl;
 255     DCL_LOCK_STATE;
 256
 257     if (((word)link & (ALIGNMENT-1)) != 0) return(0); /* Nothing to do. */
 258
 259     LOCK();
 260     curr_dl = GC_unregister_disappearing_link_inner(&GC_dl_hashtbl, link);
 261     UNLOCK();
 262     if (NULL == curr_dl) return 0;
 263     FREE_DL_ENTRY(curr_dl);
 264     return 1;
 265 }
 266
 267 GC_API int GC_CALL GC_unregister_long_link(void * * link)
 268 {
 269     struct disappearing_link *curr_dl;
 270     DCL_LOCK_STATE;
 271
 272     if (((word)link & (ALIGNMENT-1)) != 0) return(0); /* Nothing to do. */
 273
 274     LOCK();
 275     curr_dl = GC_unregister_disappearing_link_inner(&GC_ll_hashtbl, link);
 276     UNLOCK();
 277     if (NULL == curr_dl) return 0;
 278     FREE_DL_ENTRY(curr_dl);
 279     return 1;
 280 }
 281
 282 #ifndef GC_MOVE_DISAPPEARING_LINK_NOT_NEEDED
 283   /* Moves a link.  Assume the lock is held.    */
 284   GC_INLINE int GC_move_disappearing_link_inner(
 285                                 struct dl_hashtbl_s *dl_hashtbl,
 286                                 void **link, void **new_link)
 287   {
 288     struct disappearing_link *curr_dl, *prev_dl, *new_dl;
 289     size_t curr_index, new_index;
 290     word curr_hidden_link;
 291     word new_hidden_link;
 292
 293     /* Find current link.       */
 294     curr_index = HASH2(link, dl_hashtbl -> log_size);
 295     curr_hidden_link = GC_HIDE_POINTER(link);
 296     prev_dl = NULL;
 297     for (curr_dl = dl_hashtbl -> head[curr_index]; curr_dl;
 298          curr_dl = dl_next(curr_dl)) {
 299       if (curr_dl -> dl_hidden_link == curr_hidden_link)
 300         break;
 301       prev_dl = curr_dl;
 302     }
 303
 304     if (NULL == curr_dl) {
 305       return GC_NOT_FOUND;
 306     }
 307
 308     if (link == new_link) {
 309       return GC_SUCCESS; /* Nothing to do.      */
 310     }
 311
 312     /* link found; now check new_link not present.      */
 313     new_index = HASH2(new_link, dl_hashtbl -> log_size);
 314     new_hidden_link = GC_HIDE_POINTER(new_link);
 315     for (new_dl = dl_hashtbl -> head[new_index]; new_dl;
 316          new_dl = dl_next(new_dl)) {
 317       if (new_dl -> dl_hidden_link == new_hidden_link) {
 318         /* Target already registered; bail.     */
 319         return GC_DUPLICATE;
 320       }
 321     }
 322
 323     /* Remove from old, add to new, update link.        */
 324     if (NULL == prev_dl) {
 325       dl_hashtbl -> head[curr_index] = dl_next(curr_dl);
 326     } else {
 327       dl_set_next(prev_dl, dl_next(curr_dl));
 328     }
 329     curr_dl -> dl_hidden_link = new_hidden_link;
 330     dl_set_next(curr_dl, dl_hashtbl -> head[new_index]);
 331     dl_hashtbl -> head[new_index] = curr_dl;
 332     return GC_SUCCESS;
 333   }
 334
 335   GC_API int GC_CALL GC_move_disappearing_link(void **link, void **new_link)
 336   {
 337     int result;
 338     DCL_LOCK_STATE;
 339
 340     if (((word)new_link & (ALIGNMENT-1)) != 0 || new_link == NULL)
 341       ABORT("Bad new_link arg to GC_move_disappearing_link");
 342     if (((word)link & (ALIGNMENT-1)) != 0)
 343       return GC_NOT_FOUND; /* Nothing to do. */
 344
 345     LOCK();
 346     result = GC_move_disappearing_link_inner(&GC_dl_hashtbl, link, new_link);
 347     UNLOCK();
 348     return result;
 349   }
 350
 351   GC_API int GC_CALL GC_move_long_link(void **link, void **new_link)
 352   {
 353     int result;
 354     DCL_LOCK_STATE;
 355
 356     if (((word)new_link & (ALIGNMENT-1)) != 0 || new_link == NULL)
 357       ABORT("Bad new_link arg to GC_move_disappearing_link");
 358     if (((word)link & (ALIGNMENT-1)) != 0)
 359       return GC_NOT_FOUND; /* Nothing to do. */
 360
 361     LOCK();
 362     result = GC_move_disappearing_link_inner(&GC_ll_hashtbl, link, new_link);
 363     UNLOCK();
 364     return result;
 365   }
 366 #endif /* !GC_MOVE_DISAPPEARING_LINK_NOT_NEEDED */
 367
 368 /* Possible finalization_marker procedures.  Note that mark stack       */
 369 /* overflow is handled by the caller, and is not a disaster.            */
 370 STATIC void GC_normal_finalize_mark_proc(ptr_t p)
 371 {
 372     hdr * hhdr = HDR(p);
 373
 374     PUSH_OBJ(p, hhdr, GC_mark_stack_top,
 375              &(GC_mark_stack[GC_mark_stack_size]));
 376 }
 377
 378 /* This only pays very partial attention to the mark descriptor.        */
 379 /* It does the right thing for normal and atomic objects, and treats    */
 380 /* most others as normal.                                               */
 381 STATIC void GC_ignore_self_finalize_mark_proc(ptr_t p)
 382 {
 383     hdr * hhdr = HDR(p);
 384     word descr = hhdr -> hb_descr;
 385     ptr_t q;
 386     word r;
 387     ptr_t scan_limit;
 388     ptr_t target_limit = p + hhdr -> hb_sz - 1;
 389
 390     if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) {
 391        scan_limit = p + descr - sizeof(word);
 392     } else {
 393        scan_limit = target_limit + 1 - sizeof(word);
 394     }
 395     for (q = p; (word)q <= (word)scan_limit; q += ALIGNMENT) {
 396         r = *(word *)q;
 397         if (r < (word)p || r > (word)target_limit) {
 398             GC_PUSH_ONE_HEAP(r, q, GC_mark_stack_top);
 399         }
 400     }
 401 }
 402
 403 STATIC void GC_null_finalize_mark_proc(ptr_t p GC_ATTR_UNUSED) {}
 404
 405 /* Possible finalization_marker procedures.  Note that mark stack       */
 406 /* overflow is handled by the caller, and is not a disaster.            */
 407
 408 /* GC_unreachable_finalize_mark_proc is an alias for normal marking,    */
 409 /* but it is explicitly tested for, and triggers different              */
 410 /* behavior.  Objects registered in this way are not finalized          */
 411 /* if they are reachable by other finalizable objects, even if those    */
 412 /* other objects specify no ordering.                                   */
 413 STATIC void GC_unreachable_finalize_mark_proc(ptr_t p)
 414 {
 415     GC_normal_finalize_mark_proc(p);
 416 }
 417
 418 /* Register a finalization function.  See gc.h for details.     */
 419 /* The last parameter is a procedure that determines            */
 420 /* marking for finalization ordering.  Any objects marked       */
 421 /* by that procedure will be guaranteed to not have been        */
 422 /* finalized when this finalizer is invoked.                    */
 423 STATIC void GC_register_finalizer_inner(void * obj,
 424                                         GC_finalization_proc fn, void *cd,
 425                                         GC_finalization_proc *ofn, void **ocd,
 426                                         finalization_mark_proc mp)
 427 {
 428     ptr_t base;
 429     struct finalizable_object * curr_fo, * prev_fo;
 430     size_t index;
 431     struct finalizable_object *new_fo = 0;
 432     hdr *hhdr = NULL; /* initialized to prevent warning. */
 433     GC_oom_func oom_fn;
 434     DCL_LOCK_STATE;
 435
 436     LOCK();
 437     if (log_fo_table_size == -1
 438         || GC_fo_entries > ((word)1 << log_fo_table_size)) {
 439         GC_grow_table((struct hash_chain_entry ***)&GC_fo_head,
 440                       &log_fo_table_size);
 441         GC_COND_LOG_PRINTF("Grew fo table to %u entries\n",
 442                            1 << (unsigned)log_fo_table_size);
 443     }
 444     /* in the THREADS case we hold allocation lock.             */
 445     base = (ptr_t)obj;
 446     for (;;) {
 447       index = HASH2(base, log_fo_table_size);
 448       prev_fo = 0;
 449       curr_fo = GC_fo_head[index];
 450       while (curr_fo != 0) {
 451         GC_ASSERT(GC_size(curr_fo) >= sizeof(struct finalizable_object));
 452         if (curr_fo -> fo_hidden_base == GC_HIDE_POINTER(base)) {
 453           /* Interruption by a signal in the middle of this     */
 454           /* should be safe.  The client may see only *ocd      */
 455           /* updated, but we'll declare that to be his problem. */
 456           if (ocd) *ocd = (void *) (curr_fo -> fo_client_data);
 457           if (ofn) *ofn = curr_fo -> fo_fn;
 458           /* Delete the structure for base. */
 459           if (prev_fo == 0) {
 460             GC_fo_head[index] = fo_next(curr_fo);
 461           } else {
 462             fo_set_next(prev_fo, fo_next(curr_fo));
 463           }
 464           if (fn == 0) {
 465             GC_fo_entries--;
 466             /* May not happen if we get a signal.  But a high   */
 467             /* estimate will only make the table larger than    */
 468             /* necessary.                                       */
 469 #           if !defined(THREADS) && !defined(DBG_HDRS_ALL)
 470               GC_free((void *)curr_fo);
 471 #           endif
 472           } else {
 473             curr_fo -> fo_fn = fn;
 474             curr_fo -> fo_client_data = (ptr_t)cd;
 475             curr_fo -> fo_mark_proc = mp;
 476             /* Reinsert it.  We deleted it first to maintain    */
 477             /* consistency in the event of a signal.            */
 478             if (prev_fo == 0) {
 479               GC_fo_head[index] = curr_fo;
 480             } else {
 481               fo_set_next(prev_fo, curr_fo);
 482             }
 483           }
 484           UNLOCK();
 485 #         ifndef DBG_HDRS_ALL
 486             if (EXPECT(new_fo != 0, FALSE)) {
 487               /* Free unused new_fo returned by GC_oom_fn() */
 488               GC_free((void *)new_fo);
 489             }
 490 #         endif
 491           return;
 492         }
 493         prev_fo = curr_fo;
 494         curr_fo = fo_next(curr_fo);
 495       }
 496       if (EXPECT(new_fo != 0, FALSE)) {
 497         /* new_fo is returned by GC_oom_fn(), so fn != 0 and hhdr != 0. */
 498         break;
 499       }
 500       if (fn == 0) {
 501         if (ocd) *ocd = 0;
 502         if (ofn) *ofn = 0;
 503         UNLOCK();
 504         return;
 505       }
 506       GET_HDR(base, hhdr);
 507       if (EXPECT(0 == hhdr, FALSE)) {
 508         /* We won't collect it, hence finalizer wouldn't be run. */
 509         if (ocd) *ocd = 0;
 510         if (ofn) *ofn = 0;
 511         UNLOCK();
 512         return;
 513       }
 514       new_fo = (struct finalizable_object *)
 515         GC_INTERNAL_MALLOC(sizeof(struct finalizable_object),NORMAL);
 516       if (EXPECT(new_fo != 0, TRUE))
 517         break;
 518       oom_fn = GC_oom_fn;
 519       UNLOCK();
 520       new_fo = (struct finalizable_object *)
 521                 (*oom_fn)(sizeof(struct finalizable_object));
 522       if (0 == new_fo) {
 523         /* No enough memory.  *ocd and *ofn remains unchanged.  */
 524         return;
 525       }
 526       /* It's not likely we'll make it here, but ... */
 527       LOCK();
 528       /* Recalculate index since the table may grow and         */
 529       /* check again that our finalizer is not in the table.    */
 530     }
 531     GC_ASSERT(GC_size(new_fo) >= sizeof(struct finalizable_object));
 532     if (ocd) *ocd = 0;
 533     if (ofn) *ofn = 0;
 534     new_fo -> fo_hidden_base = GC_HIDE_POINTER(base);
 535     new_fo -> fo_fn = fn;
 536     new_fo -> fo_client_data = (ptr_t)cd;
 537     new_fo -> fo_object_size = hhdr -> hb_sz;
 538     new_fo -> fo_mark_proc = mp;
 539     fo_set_next(new_fo, GC_fo_head[index]);
 540     GC_fo_entries++;
 541     GC_fo_head[index] = new_fo;
 542     UNLOCK();
 543 }
 544
 545 GC_API void GC_CALL GC_register_finalizer(void * obj,
 546                                   GC_finalization_proc fn, void * cd,
 547                                   GC_finalization_proc *ofn, void ** ocd)
 548 {
 549     GC_register_finalizer_inner(obj, fn, cd, ofn,
 550                                 ocd, GC_normal_finalize_mark_proc);
 551 }
 552
 553 GC_API void GC_CALL GC_register_finalizer_ignore_self(void * obj,
 554                                GC_finalization_proc fn, void * cd,
 555                                GC_finalization_proc *ofn, void ** ocd)
 556 {
 557     GC_register_finalizer_inner(obj, fn, cd, ofn,
 558                                 ocd, GC_ignore_self_finalize_mark_proc);
 559 }
 560
 561 GC_API void GC_CALL GC_register_finalizer_no_order(void * obj,
 562                                GC_finalization_proc fn, void * cd,
 563                                GC_finalization_proc *ofn, void ** ocd)
 564 {
 565     GC_register_finalizer_inner(obj, fn, cd, ofn,
 566                                 ocd, GC_null_finalize_mark_proc);
 567 }
 568
 569 static GC_bool need_unreachable_finalization = FALSE;
 570         /* Avoid the work if this isn't used.   */
 571
 572 GC_API void GC_CALL GC_register_finalizer_unreachable(void * obj,
 573                                GC_finalization_proc fn, void * cd,
 574                                GC_finalization_proc *ofn, void ** ocd)
 575 {
 576     need_unreachable_finalization = TRUE;
 577     GC_ASSERT(GC_java_finalization);
 578     GC_register_finalizer_inner(obj, fn, cd, ofn,
 579                                 ocd, GC_unreachable_finalize_mark_proc);
 580 }
 581
 582 #ifndef NO_DEBUGGING
 583   GC_INLINE void GC_dump_finalization_links(struct dl_hashtbl_s* dl_hashtbl)
 584   {
 585     struct disappearing_link * curr_dl;
 586     ptr_t real_ptr, real_link;
 587     size_t dl_size = dl_hashtbl -> log_size == -1 ? 0 :
 588                                 1 << dl_hashtbl -> log_size;
 589     size_t i;
 590
 591     for (i = 0; i < dl_size; i++) {
 592       for (curr_dl = dl_hashtbl -> head[i]; curr_dl != 0;
 593            curr_dl = dl_next(curr_dl)) {
 594         real_ptr = GC_REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 595         real_link = GC_REVEAL_POINTER(curr_dl -> dl_hidden_link);
 596         GC_printf("Object: %p, Link:%p\n", real_ptr, real_link);
 597       }
 598     }
 599   }
 600
 601   void GC_dump_finalization(void)
 602   {
 603     struct finalizable_object * curr_fo;
 604     size_t fo_size = log_fo_table_size == -1 ? 0 : 1 << log_fo_table_size;
 605     ptr_t real_ptr;
 606     size_t i;
 607
 608     GC_printf("Disappearing short links:\n");
 609     GC_dump_finalization_links(&GC_dl_hashtbl);
 610     GC_printf("Disappearing long links:\n");
 611     GC_dump_finalization_links(&GC_ll_hashtbl);
 612     GC_printf("Finalizers:\n");
 613     for (i = 0; i < fo_size; i++) {
 614       for (curr_fo = GC_fo_head[i]; curr_fo != 0;
 615            curr_fo = fo_next(curr_fo)) {
 616         real_ptr = GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 617         GC_printf("Finalizable object: %p\n", real_ptr);
 618       }
 619     }
 620   }
 621 #endif /* !NO_DEBUGGING */
 622
 623 #ifndef SMALL_CONFIG
 624   /* for stats printing */
 625   STATIC word GC_old_dl_entries = 0, GC_old_ll_entries = 0;
 626 #endif
 627
 628 #ifndef THREADS
 629   /* Global variables to minimize the level of recursion when a client  */
 630   /* finalizer allocates memory.                                        */
 631   STATIC int GC_finalizer_nested = 0;
 632                         /* Only the lowest byte is used, the rest is    */
 633                         /* padding for proper global data alignment     */
 634                         /* required for some compilers (like Watcom).   */
 635   STATIC unsigned GC_finalizer_skipped = 0;
 636
 637   /* Checks and updates the level of finalizers recursion.              */
 638   /* Returns NULL if GC_invoke_finalizers() should not be called by the */
 639   /* collector (to minimize the risk of a deep finalizers recursion),   */
 640   /* otherwise returns a pointer to GC_finalizer_nested.                */
 641   STATIC unsigned char *GC_check_finalizer_nested(void)
 642   {
 643     unsigned nesting_level = *(unsigned char *)&GC_finalizer_nested;
 644     if (nesting_level) {
 645       /* We are inside another GC_invoke_finalizers().          */
 646       /* Skip some implicitly-called GC_invoke_finalizers()     */
 647       /* depending on the nesting (recursion) level.            */
 648       if (++GC_finalizer_skipped < (1U << nesting_level)) return NULL;
 649       GC_finalizer_skipped = 0;
 650     }
 651     *(char *)&GC_finalizer_nested = (char)(nesting_level + 1);
 652     return (unsigned char *)&GC_finalizer_nested;
 653   }
 654 #endif /* THREADS */
 655
 656 #define ITERATE_DL_HASHTBL_BEGIN(dl_hashtbl, curr_dl, prev_dl) \
 657   { \
 658     size_t i; \
 659     size_t dl_size = dl_hashtbl->log_size == -1 ? 0 : \
 660                                 1 << dl_hashtbl->log_size; \
 661     for (i = 0; i < dl_size; i++) { \
 662       curr_dl = dl_hashtbl -> head[i]; \
 663       prev_dl = NULL; \
 664       while (curr_dl) {
 665
 666 #define ITERATE_DL_HASHTBL_END(curr_dl, prev_dl) \
 667         prev_dl = curr_dl; \
 668         curr_dl = dl_next(curr_dl); \
 669       } \
 670     } \
 671   }
 672
 673 #define DELETE_DL_HASHTBL_ENTRY(dl_hashtbl, curr_dl, prev_dl, next_dl) \
 674   { \
 675     next_dl = dl_next(curr_dl); \
 676     if (NULL == prev_dl) { \
 677         dl_hashtbl -> head[i] = next_dl; \
 678     } else { \
 679         dl_set_next(prev_dl, next_dl); \
 680     } \
 681     GC_clear_mark_bit(curr_dl); \
 682     dl_hashtbl -> entries--; \
 683     curr_dl = next_dl; \
 684     continue; \
 685   }
 686
 687 GC_INLINE void GC_make_disappearing_links_disappear(
 688                                 struct dl_hashtbl_s* dl_hashtbl)
 689 {
 690     struct disappearing_link *curr, *prev, *next;
 691     ptr_t real_ptr, real_link;
 692
 693     ITERATE_DL_HASHTBL_BEGIN(dl_hashtbl, curr, prev)
 694         real_ptr = GC_REVEAL_POINTER(curr -> dl_hidden_obj);
 695         real_link = GC_REVEAL_POINTER(curr -> dl_hidden_link);
 696         if (!GC_is_marked(real_ptr)) {
 697             *(word *)real_link = 0;
 698             GC_clear_mark_bit(curr);
 699             DELETE_DL_HASHTBL_ENTRY(dl_hashtbl, curr, prev, next);
 700         }
 701     ITERATE_DL_HASHTBL_END(curr, prev)
 702 }
 703
 704 GC_INLINE void GC_remove_dangling_disappearing_links(
 705                                 struct dl_hashtbl_s* dl_hashtbl)
 706 {
 707     struct disappearing_link *curr, *prev, *next;
 708     ptr_t real_link;
 709
 710     ITERATE_DL_HASHTBL_BEGIN(dl_hashtbl, curr, prev)
 711         real_link = GC_base(GC_REVEAL_POINTER(curr -> dl_hidden_link));
 712         if (NULL != real_link && !GC_is_marked(real_link)) {
 713             GC_clear_mark_bit(curr);
 714             DELETE_DL_HASHTBL_ENTRY(dl_hashtbl, curr, prev, next);
 715         }
 716     ITERATE_DL_HASHTBL_END(curr, prev)
 717 }
 718
 719 /* Called with held lock (but the world is running).                    */
 720 /* Cause disappearing links to disappear and unreachable objects to be  */
 721 /* enqueued for finalization.                                           */
 722 GC_INNER void GC_finalize(void)
 723 {
 724     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 725     ptr_t real_ptr;
 726     size_t i;
 727     size_t fo_size = log_fo_table_size == -1 ? 0 : 1 << log_fo_table_size;
 728
 729 #   ifndef SMALL_CONFIG
 730       /* Save current GC_[dl/ll]_entries value for stats printing */
 731       GC_old_dl_entries = GC_dl_hashtbl.entries;
 732       GC_old_ll_entries = GC_ll_hashtbl.entries;
 733 #   endif
 734
 735     GC_make_disappearing_links_disappear(&GC_dl_hashtbl);
 736
 737   /* Mark all objects reachable via chains of 1 or more pointers        */
 738   /* from finalizable objects.                                          */
 739     GC_ASSERT(GC_mark_state == MS_NONE);
 740     for (i = 0; i < fo_size; i++) {
 741       for (curr_fo = GC_fo_head[i]; curr_fo != 0;
 742            curr_fo = fo_next(curr_fo)) {
 743         GC_ASSERT(GC_size(curr_fo) >= sizeof(struct finalizable_object));
 744         real_ptr = GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 745         if (!GC_is_marked(real_ptr)) {
 746             GC_MARKED_FOR_FINALIZATION(real_ptr);
 747             GC_MARK_FO(real_ptr, curr_fo -> fo_mark_proc);
 748             if (GC_is_marked(real_ptr)) {
 749                 WARN("Finalization cycle involving %p\n", real_ptr);
 750             }
 751         }
 752       }
 753     }
 754   /* Enqueue for finalization all objects that are still                */
 755   /* unreachable.                                                       */
 756     GC_bytes_finalized = 0;
 757     for (i = 0; i < fo_size; i++) {
 758       curr_fo = GC_fo_head[i];
 759       prev_fo = 0;
 760       while (curr_fo != 0) {
 761         real_ptr = GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 762         if (!GC_is_marked(real_ptr)) {
 763             if (!GC_java_finalization) {
 764               GC_set_mark_bit(real_ptr);
 765             }
 766             /* Delete from hash table */
 767               next_fo = fo_next(curr_fo);
 768               if (prev_fo == 0) {
 769                 GC_fo_head[i] = next_fo;
 770               } else {
 771                 fo_set_next(prev_fo, next_fo);
 772               }
 773               GC_fo_entries--;
 774             /* Add to list of objects awaiting finalization.    */
 775               fo_set_next(curr_fo, GC_finalize_now);
 776               GC_finalize_now = curr_fo;
 777               /* unhide object pointer so any future collections will   */
 778               /* see it.                                                */
 779               curr_fo -> fo_hidden_base =
 780                         (word)GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 781               GC_bytes_finalized +=
 782                         curr_fo -> fo_object_size
 783                         + sizeof(struct finalizable_object);
 784             GC_ASSERT(GC_is_marked(GC_base(curr_fo)));
 785             curr_fo = next_fo;
 786         } else {
 787             prev_fo = curr_fo;
 788             curr_fo = fo_next(curr_fo);
 789         }
 790       }
 791     }
 792
 793   if (GC_java_finalization) {
 794     /* make sure we mark everything reachable from objects finalized
 795        using the no_order mark_proc */
 796       for (curr_fo = GC_finalize_now;
 797          curr_fo != NULL; curr_fo = fo_next(curr_fo)) {
 798         real_ptr = (ptr_t)curr_fo -> fo_hidden_base;
 799         if (!GC_is_marked(real_ptr)) {
 800             if (curr_fo -> fo_mark_proc == GC_null_finalize_mark_proc) {
 801                 GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 802             }
 803             if (curr_fo -> fo_mark_proc != GC_unreachable_finalize_mark_proc) {
 804                 GC_set_mark_bit(real_ptr);
 805             }
 806         }
 807       }
 808
 809     /* now revive finalize-when-unreachable objects reachable from
 810        other finalizable objects */
 811       if (need_unreachable_finalization) {
 812         curr_fo = GC_finalize_now;
 813         prev_fo = 0;
 814         while (curr_fo != 0) {
 815           next_fo = fo_next(curr_fo);
 816           if (curr_fo -> fo_mark_proc == GC_unreachable_finalize_mark_proc) {
 817             real_ptr = (ptr_t)curr_fo -> fo_hidden_base;
 818             if (!GC_is_marked(real_ptr)) {
 819               GC_set_mark_bit(real_ptr);
 820             } else {
 821               if (prev_fo == 0)
 822                 GC_finalize_now = next_fo;
 823               else
 824                 fo_set_next(prev_fo, next_fo);
 825
 826               curr_fo -> fo_hidden_base =
 827                                 GC_HIDE_POINTER(curr_fo -> fo_hidden_base);
 828               GC_bytes_finalized -=
 829                   curr_fo->fo_object_size + sizeof(struct finalizable_object);
 830
 831               i = HASH2(real_ptr, log_fo_table_size);
 832               fo_set_next (curr_fo, GC_fo_head[i]);
 833               GC_fo_entries++;
 834               GC_fo_head[i] = curr_fo;
 835               curr_fo = prev_fo;
 836             }
 837           }
 838           prev_fo = curr_fo;
 839           curr_fo = next_fo;
 840         }
 841       }
 842   }
 843
 844   GC_make_disappearing_links_disappear(&GC_ll_hashtbl);
 845
 846   GC_remove_dangling_disappearing_links(&GC_dl_hashtbl);
 847   GC_remove_dangling_disappearing_links(&GC_ll_hashtbl);
 848
 849   if (GC_fail_count) {
 850     /* Don't prevent running finalizers if there has been an allocation */
 851     /* failure recently.                                                */
 852 #   ifdef THREADS
 853       GC_reset_finalizer_nested();
 854 #   else
 855       GC_finalizer_nested = 0;
 856 #   endif
 857   }
 858 }
 859
 860 #ifndef JAVA_FINALIZATION_NOT_NEEDED
 861
 862   /* Enqueue all remaining finalizers to be run - Assumes lock is held. */
 863   STATIC void GC_enqueue_all_finalizers(void)
 864   {
 865     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 866     ptr_t real_ptr;
 867     register int i;
 868     int fo_size;
 869
 870     fo_size = log_fo_table_size == -1 ? 0 : 1 << log_fo_table_size;
 871     GC_bytes_finalized = 0;
 872     for (i = 0; i < fo_size; i++) {
 873         curr_fo = GC_fo_head[i];
 874         prev_fo = 0;
 875       while (curr_fo != 0) {
 876           real_ptr = GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 877           GC_MARK_FO(real_ptr, GC_normal_finalize_mark_proc);
 878           GC_set_mark_bit(real_ptr);
 879
 880           /* Delete from hash table */
 881           next_fo = fo_next(curr_fo);
 882           if (prev_fo == 0) {
 883               GC_fo_head[i] = next_fo;
 884           } else {
 885               fo_set_next(prev_fo, next_fo);
 886           }
 887           GC_fo_entries--;
 888
 889           /* Add to list of objects awaiting finalization.      */
 890           fo_set_next(curr_fo, GC_finalize_now);
 891           GC_finalize_now = curr_fo;
 892
 893           /* unhide object pointer so any future collections will       */
 894           /* see it.                                                    */
 895           curr_fo -> fo_hidden_base =
 896                         (word)GC_REVEAL_POINTER(curr_fo -> fo_hidden_base);
 897           GC_bytes_finalized +=
 898                 curr_fo -> fo_object_size + sizeof(struct finalizable_object);
 899           curr_fo = next_fo;
 900         }
 901     }
 902   }
 903
 904   /* Invoke all remaining finalizers that haven't yet been run.
 905    * This is needed for strict compliance with the Java standard,
 906    * which can make the runtime guarantee that all finalizers are run.
 907    * Unfortunately, the Java standard implies we have to keep running
 908    * finalizers until there are no more left, a potential infinite loop.
 909    * YUCK.
 910    * Note that this is even more dangerous than the usual Java
 911    * finalizers, in that objects reachable from static variables
 912    * may have been finalized when these finalizers are run.
 913    * Finalizers run at this point must be prepared to deal with a
 914    * mostly broken world.
 915    * This routine is externally callable, so is called without
 916    * the allocation lock.
 917    */
 918   GC_API void GC_CALL GC_finalize_all(void)
 919   {
 920     DCL_LOCK_STATE;
 921
 922     LOCK();
 923     while (GC_fo_entries > 0) {
 924       GC_enqueue_all_finalizers();
 925       UNLOCK();
 926       GC_invoke_finalizers();
 927       /* Running the finalizers in this thread is arguably not a good   */
 928       /* idea when we should be notifying another thread to run them.   */
 929       /* But otherwise we don't have a great way to wait for them to    */
 930       /* run.                                                           */
 931       LOCK();
 932     }
 933     UNLOCK();
 934   }
 935
 936 #endif /* !JAVA_FINALIZATION_NOT_NEEDED */
 937
 938 /* Returns true if it is worth calling GC_invoke_finalizers. (Useful if */
 939 /* finalizers can only be called from some kind of `safe state' and     */
 940 /* getting into that safe state is expensive.)                          */
 941 GC_API int GC_CALL GC_should_invoke_finalizers(void)
 942 {
 943     return GC_finalize_now != 0;
 944 }
 945
 946 /* Invoke finalizers for all objects that are ready to be finalized.    */
 947 /* Should be called without allocation lock.                            */
 948 GC_API int GC_CALL GC_invoke_finalizers(void)
 949 {
 950     struct finalizable_object * curr_fo;
 951     int count = 0;
 952     word bytes_freed_before = 0; /* initialized to prevent warning. */
 953     DCL_LOCK_STATE;
 954
 955     while (GC_finalize_now != 0) {
 956 #       ifdef THREADS
 957             LOCK();
 958 #       endif
 959         if (count == 0) {
 960             bytes_freed_before = GC_bytes_freed;
 961             /* Don't do this outside, since we need the lock. */
 962         }
 963         curr_fo = GC_finalize_now;
 964 #       ifdef THREADS
 965             if (curr_fo != 0) GC_finalize_now = fo_next(curr_fo);
 966             UNLOCK();
 967             if (curr_fo == 0) break;
 968 #       else
 969             GC_finalize_now = fo_next(curr_fo);
 970 #       endif
 971         fo_set_next(curr_fo, 0);
 972         (*(curr_fo -> fo_fn))((ptr_t)(curr_fo -> fo_hidden_base),
 973                               curr_fo -> fo_client_data);
 974         curr_fo -> fo_client_data = 0;
 975         ++count;
 976 #       ifdef UNDEFINED
 977             /* This is probably a bad idea.  It throws off accounting if */
 978             /* nearly all objects are finalizable.  O.w. it shouldn't    */
 979             /* matter.                                                   */
 980             GC_free((void *)curr_fo);
 981 #       endif
 982     }
 983     /* bytes_freed_before is initialized whenever count != 0 */
 984     if (count != 0 && bytes_freed_before != GC_bytes_freed) {
 985         LOCK();
 986         GC_finalizer_bytes_freed += (GC_bytes_freed - bytes_freed_before);
 987         UNLOCK();
 988     }
 989     return count;
 990 }
 991
 992 static GC_word last_finalizer_notification = 0;
 993
 994 GC_INNER void GC_notify_or_invoke_finalizers(void)
 995 {
 996     GC_finalizer_notifier_proc notifier_fn = 0;
 997 #   if defined(KEEP_BACK_PTRS) || defined(MAKE_BACK_GRAPH)
 998       static word last_back_trace_gc_no = 1;    /* Skip first one. */
 999 #   endif
1000     DCL_LOCK_STATE;
1001
1002 #   if defined(THREADS) && !defined(KEEP_BACK_PTRS) \
1003        && !defined(MAKE_BACK_GRAPH)
1004       /* Quick check (while unlocked) for an empty finalization queue.  */
1005       if (GC_finalize_now == 0) return;
1006 #   endif
1007     LOCK();
1008
1009     /* This is a convenient place to generate backtraces if appropriate, */
1010     /* since that code is not callable with the allocation lock.         */
1011 #   if defined(KEEP_BACK_PTRS) || defined(MAKE_BACK_GRAPH)
1012       if (GC_gc_no > last_back_trace_gc_no) {
1013 #       ifdef KEEP_BACK_PTRS
1014           long i;
1015           /* Stops when GC_gc_no wraps; that's OK.      */
1016           last_back_trace_gc_no = (word)(-1);  /* disable others. */
1017           for (i = 0; i < GC_backtraces; ++i) {
1018               /* FIXME: This tolerates concurrent heap mutation,        */
1019               /* which may cause occasional mysterious results.         */
1020               /* We need to release the GC lock, since GC_print_callers */
1021               /* acquires it.  It probably shouldn't.                   */
1022               UNLOCK();
1023               GC_generate_random_backtrace_no_gc();
1024               LOCK();
1025           }
1026           last_back_trace_gc_no = GC_gc_no;
1027 #       endif
1028 #       ifdef MAKE_BACK_GRAPH
1029           if (GC_print_back_height) {
1030             UNLOCK();
1031             GC_print_back_graph_stats();
1032             LOCK();
1033           }
1034 #       endif
1035       }
1036 #   endif
1037     if (GC_finalize_now == 0) {
1038       UNLOCK();
1039       return;
1040     }
1041
1042     if (!GC_finalize_on_demand) {
1043       unsigned char *pnested = GC_check_finalizer_nested();
1044       UNLOCK();
1045       /* Skip GC_invoke_finalizers() if nested */
1046       if (pnested != NULL) {
1047         (void) GC_invoke_finalizers();
1048         *pnested = 0; /* Reset since no more finalizers. */
1049 #       ifndef THREADS
1050           GC_ASSERT(GC_finalize_now == 0);
1051 #       endif   /* Otherwise GC can run concurrently and add more */
1052       }
1053       return;
1054     }
1055
1056     /* These variables require synchronization to avoid data races.     */
1057     if (last_finalizer_notification != GC_gc_no) {
1058         last_finalizer_notification = GC_gc_no;
1059         notifier_fn = GC_finalizer_notifier;
1060     }
1061     UNLOCK();
1062     if (notifier_fn != 0)
1063         (*notifier_fn)(); /* Invoke the notifier */
1064 }
1065
1066 #ifndef SMALL_CONFIG
1067   GC_INNER void GC_print_finalization_stats(void)
1068   {
1069     struct finalizable_object *fo = GC_finalize_now;
1070     unsigned long ready = 0;
1071
1072     GC_log_printf(
1073         "%lu finalization table entries; "
1074         "%lu short/%lu long disappearing links alive\n",
1075         (unsigned long)GC_fo_entries,
1076         (unsigned long)GC_dl_hashtbl.entries,
1077         (unsigned long)GC_ll_hashtbl.entries);
1078     for (; 0 != fo; fo = fo_next(fo)) ++ready;
1079     GC_log_printf("%lu objects are ready for finalization; "
1080                   "%ld short/%ld long links cleared\n",
1081                   ready,
1082                   (long)GC_old_dl_entries - (long)GC_dl_hashtbl.entries,
1083                   (long)GC_old_ll_entries - (long)GC_ll_hashtbl.entries);
1084   }
1085 #endif /* !SMALL_CONFIG */
1086
1087 #endif /* !GC_NO_FINALIZATION */