finalize.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
   4
   5  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   6  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   7  *
   8  * Permission is hereby granted to use or copy this program
   9  * for any purpose,  provided the above notices are retained on all copies.
  10  * Permission to modify the code and to distribute modified code is granted,
  11  * provided the above notices are retained, and a notice that the code was
  12  * modified is included with the above copyright notice.
  13  */
  14 /* Boehm, May 19, 1994 2:08 pm PDT */
  15 # define I_HIDE_POINTERS
  16 # include "gc.h"
  17 # include "gc_priv.h"
  18 # include "gc_mark.h"
  19
  20 # define HASH3(addr,size,log_size) \
  21     ((((word)(addr) >> 3) ^ ((word)(addr) >> (3+(log_size)))) \
  22     & ((size) - 1))
  23 #define HASH2(addr,log_size) HASH3(addr, 1 << log_size, log_size)
  24
  25 struct hash_chain_entry {
  26     word hidden_key;
  27     struct hash_chain_entry * next;
  28 };
  29
  30 unsigned GC_finalization_failures = 0;
  31         /* Number of finalization requests that failed for lack of memory. */
  32
  33 static struct disappearing_link {
  34     struct hash_chain_entry prolog;
  35 #   define dl_hidden_link prolog.hidden_key
  36                                 /* Field to be cleared.         */
  37 #   define dl_next(x) (struct disappearing_link *)((x) -> prolog.next)
  38 #   define dl_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  39
  40     word dl_hidden_obj;         /* Pointer to object base       */
  41 } **dl_head = 0;
  42
  43 static signed_word log_dl_table_size = -1;
  44                         /* Binary log of                                */
  45                         /* current size of array pointed to by dl_head. */
  46                         /* -1 ==> size is 0.                            */
  47
  48 word GC_dl_entries = 0; /* Number of entries currently in disappearing  */
  49                         /* link table.                                  */
  50
  51 static struct finalizable_object {
  52     struct hash_chain_entry prolog;
  53 #   define fo_hidden_base prolog.hidden_key
  54                                 /* Pointer to object base.      */
  55 #   define fo_next(x) (struct finalizable_object *)((x) -> prolog.next)
  56 #   define fo_set_next(x,y) (x) -> prolog.next = (struct hash_chain_entry *)(y)
  57     GC_finalization_proc fo_fn; /* Finalizer.                   */
  58     ptr_t fo_client_data;
  59     word fo_object_size;        /* In bytes.                    */
  60 } **fo_head = 0;
  61
  62 struct finalizable_object * GC_finalize_now = 0;
  63         /* LIst of objects that should be finalized now.        */
  64
  65 static signed_word log_fo_table_size = -1;
  66
  67 word GC_fo_entries = 0;
  68
  69 # ifdef SRC_M3
  70 void GC_push_finalizer_structures()
  71 {
  72     GC_push_all((ptr_t)(&dl_head), (ptr_t)(&dl_head) + sizeof(word));
  73     GC_push_all((ptr_t)(&fo_head), (ptr_t)(&fo_head) + sizeof(word));
  74 }
  75 # endif
  76
  77 # define ALLOC(x, t) t *x = GC_NEW(t)
  78
  79 /* Double the size of a hash table. *size_ptr is the log of its current */
  80 /* size.  May be a noop.                                                */
  81 /* *table is a pointer to an array of hash headers.  If we succeed, we  */
  82 /* update both *table and *log_size_ptr.                                */
  83 /* Lock is held.  Signals are disabled.                                 */
  84 void GC_grow_table(table, log_size_ptr)
  85 struct hash_chain_entry ***table;
  86 signed_word * log_size_ptr;
  87 {
  88     register word i;
  89     register struct hash_chain_entry *p;
  90     int log_old_size = *log_size_ptr;
  91     register int log_new_size = log_old_size + 1;
  92     word old_size = ((log_old_size == -1)? 0: (1 << log_old_size));
  93     register word new_size = 1 << log_new_size;
  94     struct hash_chain_entry **new_table = (struct hash_chain_entry **)
  95         GC_malloc_ignore_off_page_inner(
  96                 (size_t)new_size * sizeof(struct hash_chain_entry *));
  97
  98     if (new_table == 0) {
  99         if (table == 0) {
 100             ABORT("Insufficient space for initial table allocation");
 101         } else {
 102             return;
 103         }
 104     }
 105     for (i = 0; i < old_size; i++) {
 106       p = (*table)[i];
 107       while (p != 0) {
 108         register ptr_t real_key = (ptr_t)REVEAL_POINTER(p -> hidden_key);
 109         register struct hash_chain_entry *next = p -> next;
 110         register int new_hash = HASH3(real_key, new_size, log_new_size);
 111
 112         p -> next = new_table[new_hash];
 113         new_table[new_hash] = p;
 114         p = next;
 115       }
 116     }
 117     *log_size_ptr = log_new_size;
 118     *table = new_table;
 119 }
 120
 121
 122 int GC_register_disappearing_link(link)
 123 extern_ptr_t * link;
 124 {
 125     ptr_t base;
 126
 127     base = (ptr_t)GC_base((extern_ptr_t)link);
 128     if (base == 0)
 129         ABORT("Bad arg to GC_register_disappearing_link");
 130     return(GC_general_register_disappearing_link(link, base));
 131 }
 132
 133 int GC_general_register_disappearing_link(link, obj)
 134 extern_ptr_t * link;
 135 extern_ptr_t obj;
 136 {
 137     struct disappearing_link *curr_dl;
 138     int index;
 139     struct disappearing_link * new_dl;
 140     DCL_LOCK_STATE;
 141
 142     if ((word)link & (ALIGNMENT-1))
 143         ABORT("Bad arg to GC_general_register_disappearing_link");
 144 #   ifdef THREADS
 145         DISABLE_SIGNALS();
 146         LOCK();
 147 #   endif
 148     if (log_dl_table_size == -1
 149         || GC_dl_entries > ((word)1 << log_dl_table_size)) {
 150 #       ifndef THREADS
 151             DISABLE_SIGNALS();
 152 #       endif
 153         GC_grow_table((struct hash_chain_entry ***)(&dl_head),
 154                       &log_dl_table_size);
 155 #       ifdef PRINTSTATS
 156             GC_printf1("Grew dl table to %lu entries\n",
 157                         (unsigned long)(1 << log_dl_table_size));
 158 #       endif
 159 #       ifndef THREADS
 160             ENABLE_SIGNALS();
 161 #       endif
 162     }
 163     index = HASH2(link, log_dl_table_size);
 164     curr_dl = dl_head[index];
 165     for (curr_dl = dl_head[index]; curr_dl != 0; curr_dl = dl_next(curr_dl)) {
 166         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 167             curr_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 168 #           ifdef THREADS
 169                 UNLOCK();
 170                 ENABLE_SIGNALS();
 171 #           endif
 172             return(1);
 173         }
 174     }
 175 #   ifdef THREADS
 176       new_dl = (struct disappearing_link *)
 177         GC_generic_malloc_inner(sizeof(struct disappearing_link),NORMAL);
 178 #   else
 179       new_dl = GC_NEW(struct disappearing_link);
 180 #   endif
 181     if (new_dl != 0) {
 182         new_dl -> dl_hidden_obj = HIDE_POINTER(obj);
 183         new_dl -> dl_hidden_link = HIDE_POINTER(link);
 184         dl_set_next(new_dl, dl_head[index]);
 185         dl_head[index] = new_dl;
 186         GC_dl_entries++;
 187     } else {
 188         GC_finalization_failures++;
 189     }
 190 #   ifdef THREADS
 191         UNLOCK();
 192         ENABLE_SIGNALS();
 193 #   endif
 194     return(0);
 195 }
 196
 197 int GC_unregister_disappearing_link(link)
 198 extern_ptr_t * link;
 199 {
 200     struct disappearing_link *curr_dl, *prev_dl;
 201     int index;
 202     DCL_LOCK_STATE;
 203
 204     DISABLE_SIGNALS();
 205     LOCK();
 206     index = HASH2(link, log_dl_table_size);
 207     if (((unsigned long)link & (ALIGNMENT-1))) goto out;
 208     prev_dl = 0; curr_dl = dl_head[index];
 209     while (curr_dl != 0) {
 210         if (curr_dl -> dl_hidden_link == HIDE_POINTER(link)) {
 211             if (prev_dl == 0) {
 212                 dl_head[index] = dl_next(curr_dl);
 213             } else {
 214                 dl_set_next(prev_dl, dl_next(curr_dl));
 215             }
 216             GC_dl_entries--;
 217             UNLOCK();
 218             ENABLE_SIGNALS();
 219             GC_free((extern_ptr_t)curr_dl);
 220             return(1);
 221         }
 222         prev_dl = curr_dl;
 223         curr_dl = dl_next(curr_dl);
 224     }
 225 out:
 226     UNLOCK();
 227     ENABLE_SIGNALS();
 228     return(0);
 229 }
 230
 231 /* Register a finalization function.  See gc.h for details.     */
 232 /* in the nonthreads case, we try to avoid disabling signals,   */
 233 /* since it can be expensive.  Threads packages typically       */
 234 /* make it cheaper.                                             */
 235 void GC_register_finalizer(obj, fn, cd, ofn, ocd)
 236 extern_ptr_t obj;
 237 GC_finalization_proc fn;
 238 extern_ptr_t cd;
 239 GC_finalization_proc * ofn;
 240 extern_ptr_t * ocd;
 241 {
 242     ptr_t base;
 243     struct finalizable_object * curr_fo, * prev_fo;
 244     int index;
 245     struct finalizable_object *new_fo;
 246     DCL_LOCK_STATE;
 247
 248 #   ifdef THREADS
 249         DISABLE_SIGNALS();
 250         LOCK();
 251 #   endif
 252     if (log_fo_table_size == -1
 253         || GC_fo_entries > ((word)1 << log_fo_table_size)) {
 254 #       ifndef THREADS
 255             DISABLE_SIGNALS();
 256 #       endif
 257         GC_grow_table((struct hash_chain_entry ***)(&fo_head),
 258                       &log_fo_table_size);
 259 #       ifdef PRINTSTATS
 260             GC_printf1("Grew fo table to %lu entries\n",
 261                         (unsigned long)(1 << log_fo_table_size));
 262 #       endif
 263 #       ifndef THREADS
 264             ENABLE_SIGNALS();
 265 #       endif
 266     }
 267     /* in the THREADS case signals are disabled and we hold allocation  */
 268     /* lock; otherwise neither is true.  Proceed carefully.             */
 269     base = (ptr_t)obj;
 270     index = HASH2(base, log_fo_table_size);
 271     prev_fo = 0; curr_fo = fo_head[index];
 272     while (curr_fo != 0) {
 273         if (curr_fo -> fo_hidden_base == HIDE_POINTER(base)) {
 274             /* Interruption by a signal in the middle of this   */
 275             /* should be safe.  The client may see only *ocd    */
 276             /* updated, but we'll declare that to be his        */
 277             /* problem.                                         */
 278             if (ocd) *ocd = (extern_ptr_t) curr_fo -> fo_client_data;
 279             if (ofn) *ofn = curr_fo -> fo_fn;
 280             /* Delete the structure for base. */
 281                 if (prev_fo == 0) {
 282                   fo_head[index] = fo_next(curr_fo);
 283                 } else {
 284                   fo_set_next(prev_fo, fo_next(curr_fo));
 285                 }
 286             if (fn == 0) {
 287                 GC_fo_entries--;
 288                   /* May not happen if we get a signal.  But a high     */
 289                   /* estimate will only make the table larger than      */
 290                   /* necessary.                                         */
 291 #               ifndef THREADS
 292                   GC_free((extern_ptr_t)curr_fo);
 293 #               endif
 294             } else {
 295                 curr_fo -> fo_fn = fn;
 296                 curr_fo -> fo_client_data = (ptr_t)cd;
 297                 /* Reinsert it.  We deleted it first to maintain        */
 298                 /* consistency in the event of a signal.                */
 299                 if (prev_fo == 0) {
 300                   fo_head[index] = curr_fo;
 301                 } else {
 302                   fo_set_next(prev_fo, curr_fo);
 303                 }
 304             }
 305 #           ifdef THREADS
 306                 UNLOCK();
 307                 ENABLE_SIGNALS();
 308 #           endif
 309             return;
 310         }
 311         prev_fo = curr_fo;
 312         curr_fo = fo_next(curr_fo);
 313     }
 314     if (ofn) *ofn = 0;
 315     if (ocd) *ocd = 0;
 316     if (fn == 0) {
 317 #       ifdef THREADS
 318             UNLOCK();
 319             ENABLE_SIGNALS();
 320 #       endif
 321         return;
 322     }
 323 #   ifdef THREADS
 324       new_fo = (struct finalizable_object *)
 325         GC_generic_malloc_inner(sizeof(struct finalizable_object),NORMAL);
 326 #   else
 327       new_fo = GC_NEW(struct finalizable_object);
 328 #   endif
 329     if (new_fo != 0) {
 330         new_fo -> fo_hidden_base = (word)HIDE_POINTER(base);
 331         new_fo -> fo_fn = fn;
 332         new_fo -> fo_client_data = (ptr_t)cd;
 333         new_fo -> fo_object_size = GC_size(base);
 334         fo_set_next(new_fo, fo_head[index]);
 335         GC_fo_entries++;
 336         fo_head[index] = new_fo;
 337     } else {
 338         GC_finalization_failures++;
 339     }
 340 #   ifdef THREADS
 341         UNLOCK();
 342         ENABLE_SIGNALS();
 343 #   endif
 344 }
 345
 346 /* Called with world stopped.  Cause disappearing links to disappear,   */
 347 /* and invoke finalizers.                                               */
 348 void GC_finalize()
 349 {
 350     struct disappearing_link * curr_dl, * prev_dl, * next_dl;
 351     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 352     ptr_t real_ptr, real_link;
 353     register int i;
 354     int dl_size = 1 << log_dl_table_size;
 355     int fo_size = 1 << log_fo_table_size;
 356
 357   /* Make disappearing links disappear */
 358     for (i = 0; i < dl_size; i++) {
 359       curr_dl = dl_head[i];
 360       prev_dl = 0;
 361       while (curr_dl != 0) {
 362         real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 363         real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 364         if (!GC_is_marked(real_ptr)) {
 365             *(word *)real_link = 0;
 366             next_dl = dl_next(curr_dl);
 367             if (prev_dl == 0) {
 368                 dl_head[i] = next_dl;
 369             } else {
 370                 dl_set_next(prev_dl, next_dl);
 371             }
 372             GC_clear_mark_bit((ptr_t)curr_dl);
 373             GC_dl_entries--;
 374             curr_dl = next_dl;
 375         } else {
 376             prev_dl = curr_dl;
 377             curr_dl = dl_next(curr_dl);
 378         }
 379       }
 380     }
 381   /* Mark all objects reachable via chains of 1 or more pointers        */
 382   /* from finalizable objects.                                          */
 383 #   ifdef PRINTSTATS
 384         if (GC_mark_state != MS_NONE) ABORT("Bad mark state");
 385 #   endif
 386     for (i = 0; i < fo_size; i++) {
 387       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 388         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 389         if (!GC_is_marked(real_ptr)) {
 390             hdr * hhdr = HDR(real_ptr);
 391
 392             PUSH_OBJ((word *)real_ptr, hhdr, GC_mark_stack_top,
 393                      &(GC_mark_stack[GC_mark_stack_size]));
 394             while (!GC_mark_stack_empty()) GC_mark_from_mark_stack();
 395             if (GC_mark_state != MS_NONE) {
 396                 /* Mark stack overflowed. Very unlikely. */
 397 #               ifdef PRINTSTATS
 398                     if (GC_mark_state != MS_INVALID) ABORT("Bad mark state");
 399                     GC_printf0("Mark stack overflowed in finalization!!\n");
 400 #               endif
 401                 /* Make mark bits consistent again.  Forget about       */
 402                 /* finalizing this object for now.                      */
 403                     GC_set_mark_bit(real_ptr);
 404                     while (!GC_mark_some());
 405             }
 406             /*
 407             if (GC_is_marked(real_ptr)) {
 408                 --> Report finalization cycle here, if desired
 409             }
 410             */
 411         }
 412
 413       }
 414     }
 415   /* Enqueue for finalization all objects that are still                */
 416   /* unreachable.                                                       */
 417     for (i = 0; i < fo_size; i++) {
 418       curr_fo = fo_head[i];
 419       prev_fo = 0;
 420       while (curr_fo != 0) {
 421         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 422         if (!GC_is_marked(real_ptr)) {
 423             GC_set_mark_bit(real_ptr);
 424             /* Delete from hash table */
 425               next_fo = fo_next(curr_fo);
 426               if (prev_fo == 0) {
 427                 fo_head[i] = next_fo;
 428               } else {
 429                 fo_set_next(prev_fo, next_fo);
 430               }
 431               GC_fo_entries--;
 432             /* Add to list of objects awaiting finalization.    */
 433               fo_set_next(curr_fo, GC_finalize_now);
 434               GC_finalize_now = curr_fo;
 435 #           ifdef PRINTSTATS
 436               if (!GC_is_marked((ptr_t)curr_fo)) {
 437                 ABORT("GC_finalize: found accessible unmarked object\n");
 438               }
 439 #           endif
 440             curr_fo = next_fo;
 441         } else {
 442             prev_fo = curr_fo;
 443             curr_fo = fo_next(curr_fo);
 444         }
 445       }
 446     }
 447   /* Remove dangling disappearing links. */
 448     for (i = 0; i < dl_size; i++) {
 449       curr_dl = dl_head[i];
 450       prev_dl = 0;
 451       while (curr_dl != 0) {
 452         real_link = GC_base((ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link));
 453         if (real_link != 0 && !GC_is_marked(real_link)) {
 454             next_dl = dl_next(curr_dl);
 455             if (prev_dl == 0) {
 456                 dl_head[i] = next_dl;
 457             } else {
 458                 dl_set_next(prev_dl, next_dl);
 459             }
 460             GC_clear_mark_bit((ptr_t)curr_dl);
 461             GC_dl_entries--;
 462             curr_dl = next_dl;
 463         } else {
 464             prev_dl = curr_dl;
 465             curr_dl = dl_next(curr_dl);
 466         }
 467       }
 468     }
 469 }
 470
 471 /* Invoke finalizers for all objects that are ready to be finalized.    */
 472 /* Should be called without allocation lock.                            */
 473 void GC_invoke_finalizers()
 474 {
 475     ptr_t real_ptr;
 476     register struct finalizable_object * curr_fo;
 477     DCL_LOCK_STATE;
 478
 479     while (GC_finalize_now != 0) {
 480 #       ifdef THREADS
 481             DISABLE_SIGNALS();
 482             LOCK();
 483 #       endif
 484         curr_fo = GC_finalize_now;
 485 #       ifdef THREADS
 486             if (curr_fo != 0) GC_finalize_now = fo_next(curr_fo);
 487             UNLOCK();
 488             ENABLE_SIGNALS();
 489             if (curr_fo == 0) break;
 490 #       else
 491             GC_finalize_now = fo_next(curr_fo);
 492 #       endif
 493         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 494         (*(curr_fo -> fo_fn))(real_ptr, curr_fo -> fo_client_data);
 495 #       ifndef THREADS
 496             GC_free((extern_ptr_t)curr_fo);
 497 #       endif
 498     }
 499 }
 500
 501 # ifdef __STDC__
 502     extern_ptr_t GC_call_with_alloc_lock(GC_fn_type fn, extern_ptr_t client_data)
 503 # else
 504     extern_ptr_t GC_call_with_alloc_lock(fn, client_data)
 505     GC_fn_type fn;
 506     extern_ptr_t client_data;
 507 # endif
 508 {
 509     extern_ptr_t result;
 510     DCL_LOCK_STATE;
 511
 512 #   ifdef THREADS
 513       DISABLE_SIGNALS();
 514       LOCK();
 515 #   endif
 516     result = (*fn)(client_data);
 517 #   ifdef THREADS
 518       UNLOCK();
 519       ENABLE_SIGNALS();
 520 #   endif
 521     return(result);
 522 }
 523