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, June 9, 1994 2:17 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_generic_malloc_inner_ignore_off_page(
  96                 (size_t)new_size * sizeof(struct hash_chain_entry *), NORMAL);
  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 # if defined(__STDC__)
 236     void GC_register_finalizer(void * obj,
 237                                GC_finalization_proc fn, void * cd,
 238                                GC_finalization_proc *ofn, void ** ocd)
 239 # else
 240     void GC_register_finalizer(obj, fn, cd, ofn, ocd)
 241     extern_ptr_t obj;
 242     GC_finalization_proc fn;
 243     extern_ptr_t cd;
 244     GC_finalization_proc * ofn;
 245     extern_ptr_t * ocd;
 246 # endif
 247 {
 248     ptr_t base;
 249     struct finalizable_object * curr_fo, * prev_fo;
 250     int index;
 251     struct finalizable_object *new_fo;
 252     DCL_LOCK_STATE;
 253
 254 #   ifdef THREADS
 255         DISABLE_SIGNALS();
 256         LOCK();
 257 #   endif
 258     if (log_fo_table_size == -1
 259         || GC_fo_entries > ((word)1 << log_fo_table_size)) {
 260 #       ifndef THREADS
 261             DISABLE_SIGNALS();
 262 #       endif
 263         GC_grow_table((struct hash_chain_entry ***)(&fo_head),
 264                       &log_fo_table_size);
 265 #       ifdef PRINTSTATS
 266             GC_printf1("Grew fo table to %lu entries\n",
 267                         (unsigned long)(1 << log_fo_table_size));
 268 #       endif
 269 #       ifndef THREADS
 270             ENABLE_SIGNALS();
 271 #       endif
 272     }
 273     /* in the THREADS case signals are disabled and we hold allocation  */
 274     /* lock; otherwise neither is true.  Proceed carefully.             */
 275     base = (ptr_t)obj;
 276     index = HASH2(base, log_fo_table_size);
 277     prev_fo = 0; curr_fo = fo_head[index];
 278     while (curr_fo != 0) {
 279         if (curr_fo -> fo_hidden_base == HIDE_POINTER(base)) {
 280             /* Interruption by a signal in the middle of this   */
 281             /* should be safe.  The client may see only *ocd    */
 282             /* updated, but we'll declare that to be his        */
 283             /* problem.                                         */
 284             if (ocd) *ocd = (extern_ptr_t) curr_fo -> fo_client_data;
 285             if (ofn) *ofn = curr_fo -> fo_fn;
 286             /* Delete the structure for base. */
 287                 if (prev_fo == 0) {
 288                   fo_head[index] = fo_next(curr_fo);
 289                 } else {
 290                   fo_set_next(prev_fo, fo_next(curr_fo));
 291                 }
 292             if (fn == 0) {
 293                 GC_fo_entries--;
 294                   /* May not happen if we get a signal.  But a high     */
 295                   /* estimate will only make the table larger than      */
 296                   /* necessary.                                         */
 297 #               ifndef THREADS
 298                   GC_free((extern_ptr_t)curr_fo);
 299 #               endif
 300             } else {
 301                 curr_fo -> fo_fn = fn;
 302                 curr_fo -> fo_client_data = (ptr_t)cd;
 303                 /* Reinsert it.  We deleted it first to maintain        */
 304                 /* consistency in the event of a signal.                */
 305                 if (prev_fo == 0) {
 306                   fo_head[index] = curr_fo;
 307                 } else {
 308                   fo_set_next(prev_fo, curr_fo);
 309                 }
 310             }
 311 #           ifdef THREADS
 312                 UNLOCK();
 313                 ENABLE_SIGNALS();
 314 #           endif
 315             return;
 316         }
 317         prev_fo = curr_fo;
 318         curr_fo = fo_next(curr_fo);
 319     }
 320     if (ofn) *ofn = 0;
 321     if (ocd) *ocd = 0;
 322     if (fn == 0) {
 323 #       ifdef THREADS
 324             UNLOCK();
 325             ENABLE_SIGNALS();
 326 #       endif
 327         return;
 328     }
 329 #   ifdef THREADS
 330       new_fo = (struct finalizable_object *)
 331         GC_generic_malloc_inner(sizeof(struct finalizable_object),NORMAL);
 332 #   else
 333       new_fo = GC_NEW(struct finalizable_object);
 334 #   endif
 335     if (new_fo != 0) {
 336         new_fo -> fo_hidden_base = (word)HIDE_POINTER(base);
 337         new_fo -> fo_fn = fn;
 338         new_fo -> fo_client_data = (ptr_t)cd;
 339         new_fo -> fo_object_size = GC_size(base);
 340         fo_set_next(new_fo, fo_head[index]);
 341         GC_fo_entries++;
 342         fo_head[index] = new_fo;
 343     } else {
 344         GC_finalization_failures++;
 345     }
 346 #   ifdef THREADS
 347         UNLOCK();
 348         ENABLE_SIGNALS();
 349 #   endif
 350 }
 351
 352 /* Called with world stopped.  Cause disappearing links to disappear,   */
 353 /* and invoke finalizers.                                               */
 354 void GC_finalize()
 355 {
 356     struct disappearing_link * curr_dl, * prev_dl, * next_dl;
 357     struct finalizable_object * curr_fo, * prev_fo, * next_fo;
 358     ptr_t real_ptr, real_link;
 359     register int i;
 360     int dl_size = 1 << log_dl_table_size;
 361     int fo_size = 1 << log_fo_table_size;
 362
 363   /* Make disappearing links disappear */
 364     for (i = 0; i < dl_size; i++) {
 365       curr_dl = dl_head[i];
 366       prev_dl = 0;
 367       while (curr_dl != 0) {
 368         real_ptr = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_obj);
 369         real_link = (ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link);
 370         if (!GC_is_marked(real_ptr)) {
 371             *(word *)real_link = 0;
 372             next_dl = dl_next(curr_dl);
 373             if (prev_dl == 0) {
 374                 dl_head[i] = next_dl;
 375             } else {
 376                 dl_set_next(prev_dl, next_dl);
 377             }
 378             GC_clear_mark_bit((ptr_t)curr_dl);
 379             GC_dl_entries--;
 380             curr_dl = next_dl;
 381         } else {
 382             prev_dl = curr_dl;
 383             curr_dl = dl_next(curr_dl);
 384         }
 385       }
 386     }
 387   /* Mark all objects reachable via chains of 1 or more pointers        */
 388   /* from finalizable objects.                                          */
 389 #   ifdef PRINTSTATS
 390         if (GC_mark_state != MS_NONE) ABORT("Bad mark state");
 391 #   endif
 392     for (i = 0; i < fo_size; i++) {
 393       for (curr_fo = fo_head[i]; curr_fo != 0; curr_fo = fo_next(curr_fo)) {
 394         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 395         if (!GC_is_marked(real_ptr)) {
 396             hdr * hhdr = HDR(real_ptr);
 397
 398             PUSH_OBJ((word *)real_ptr, hhdr, GC_mark_stack_top,
 399                      &(GC_mark_stack[GC_mark_stack_size]));
 400             while (!GC_mark_stack_empty()) GC_mark_from_mark_stack();
 401             if (GC_mark_state != MS_NONE) {
 402                 /* Mark stack overflowed. Very unlikely. */
 403 #               ifdef PRINTSTATS
 404                     if (GC_mark_state != MS_INVALID) ABORT("Bad mark state");
 405                     GC_printf0("Mark stack overflowed in finalization!!\n");
 406 #               endif
 407                 /* Make mark bits consistent again.  Forget about       */
 408                 /* finalizing this object for now.                      */
 409                     GC_set_mark_bit(real_ptr);
 410                     while (!GC_mark_some());
 411             }
 412             /*
 413             if (GC_is_marked(real_ptr)) {
 414                 --> Report finalization cycle here, if desired
 415             }
 416             */
 417         }
 418
 419       }
 420     }
 421   /* Enqueue for finalization all objects that are still                */
 422   /* unreachable.                                                       */
 423     for (i = 0; i < fo_size; i++) {
 424       curr_fo = fo_head[i];
 425       prev_fo = 0;
 426       while (curr_fo != 0) {
 427         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 428         if (!GC_is_marked(real_ptr)) {
 429             GC_set_mark_bit(real_ptr);
 430             /* Delete from hash table */
 431               next_fo = fo_next(curr_fo);
 432               if (prev_fo == 0) {
 433                 fo_head[i] = next_fo;
 434               } else {
 435                 fo_set_next(prev_fo, next_fo);
 436               }
 437               GC_fo_entries--;
 438             /* Add to list of objects awaiting finalization.    */
 439               fo_set_next(curr_fo, GC_finalize_now);
 440               GC_finalize_now = curr_fo;
 441 #           ifdef PRINTSTATS
 442               if (!GC_is_marked((ptr_t)curr_fo)) {
 443                 ABORT("GC_finalize: found accessible unmarked object\n");
 444               }
 445 #           endif
 446             curr_fo = next_fo;
 447         } else {
 448             prev_fo = curr_fo;
 449             curr_fo = fo_next(curr_fo);
 450         }
 451       }
 452     }
 453   /* Remove dangling disappearing links. */
 454     for (i = 0; i < dl_size; i++) {
 455       curr_dl = dl_head[i];
 456       prev_dl = 0;
 457       while (curr_dl != 0) {
 458         real_link = GC_base((ptr_t)REVEAL_POINTER(curr_dl -> dl_hidden_link));
 459         if (real_link != 0 && !GC_is_marked(real_link)) {
 460             next_dl = dl_next(curr_dl);
 461             if (prev_dl == 0) {
 462                 dl_head[i] = next_dl;
 463             } else {
 464                 dl_set_next(prev_dl, next_dl);
 465             }
 466             GC_clear_mark_bit((ptr_t)curr_dl);
 467             GC_dl_entries--;
 468             curr_dl = next_dl;
 469         } else {
 470             prev_dl = curr_dl;
 471             curr_dl = dl_next(curr_dl);
 472         }
 473       }
 474     }
 475 }
 476
 477 /* Invoke finalizers for all objects that are ready to be finalized.    */
 478 /* Should be called without allocation lock.                            */
 479 void GC_invoke_finalizers()
 480 {
 481     ptr_t real_ptr;
 482     register struct finalizable_object * curr_fo;
 483     DCL_LOCK_STATE;
 484
 485     while (GC_finalize_now != 0) {
 486 #       ifdef THREADS
 487             DISABLE_SIGNALS();
 488             LOCK();
 489 #       endif
 490         curr_fo = GC_finalize_now;
 491 #       ifdef THREADS
 492             if (curr_fo != 0) GC_finalize_now = fo_next(curr_fo);
 493             UNLOCK();
 494             ENABLE_SIGNALS();
 495             if (curr_fo == 0) break;
 496 #       else
 497             GC_finalize_now = fo_next(curr_fo);
 498 #       endif
 499         real_ptr = (ptr_t)REVEAL_POINTER(curr_fo -> fo_hidden_base);
 500         (*(curr_fo -> fo_fn))(real_ptr, curr_fo -> fo_client_data);
 501 #       ifndef THREADS
 502             GC_free((extern_ptr_t)curr_fo);
 503 #       endif
 504     }
 505 }
 506
 507 # ifdef __STDC__
 508     extern_ptr_t GC_call_with_alloc_lock(GC_fn_type fn, extern_ptr_t client_data)
 509 # else
 510     extern_ptr_t GC_call_with_alloc_lock(fn, client_data)
 511     GC_fn_type fn;
 512     extern_ptr_t client_data;
 513 # endif
 514 {
 515     extern_ptr_t result;
 516     DCL_LOCK_STATE;
 517
 518 #   ifdef THREADS
 519       DISABLE_SIGNALS();
 520       LOCK();
 521 #   endif
 522     result = (*fn)(client_data);
 523 #   ifdef THREADS
 524       UNLOCK();
 525       ENABLE_SIGNALS();
 526 #   endif
 527     return(result);
 528 }
 529