Back to index

lightning-sunbird  0.9+nobinonly
blacklst.c
Go to the documentation of this file.
00001 /* 
00002  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
00003  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
00004  *
00005  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00006  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00007  *
00008  * Permission is hereby granted to use or copy this program
00009  * for any purpose,  provided the above notices are retained on all copies.
00010  * Permission to modify the code and to distribute modified code is granted,
00011  * provided the above notices are retained, and a notice that the code was
00012  * modified is included with the above copyright notice.
00013  */
00014 /* Boehm, August 9, 1995 6:09 pm PDT */
00015 # include "gc_priv.h"
00016 
00017 /*
00018  * We maintain several hash tables of hblks that have had false hits.
00019  * Each contains one bit per hash bucket;  If any page in the bucket
00020  * has had a false hit, we assume that all of them have.
00021  * See the definition of page_hash_table in gc_private.h.
00022  * False hits from the stack(s) are much more dangerous than false hits
00023  * from elsewhere, since the former can pin a large object that spans the
00024  * block, eventhough it does not start on the dangerous block.
00025  */
00026  
00027 /*
00028  * Externally callable routines are:
00029  
00030  * GC_add_to_black_list_normal
00031  * GC_add_to_black_list_stack
00032  * GC_promote_black_lists
00033  * GC_is_black_listed
00034  *
00035  * All require that the allocator lock is held.
00036  */
00037 
00038 /* Pointers to individual tables.  We replace one table by another by        */
00039 /* switching these pointers.                                          */
00040 word * GC_old_normal_bl;
00041               /* Nonstack false references seen at last full          */
00042               /* collection.                                          */
00043 word * GC_incomplete_normal_bl;
00044               /* Nonstack false references seen since last            */
00045               /* full collection.                              */
00046 word * GC_old_stack_bl;
00047 word * GC_incomplete_stack_bl;
00048 
00049 word GC_total_stack_black_listed;
00050 
00051 word GC_black_list_spacing = MINHINCR*HBLKSIZE;  /* Initial rough guess */
00052 
00053 void GC_clear_bl();
00054 
00055 void GC_default_print_heap_obj_proc(p)
00056 ptr_t p;
00057 {
00058     ptr_t base = GC_base(p);
00059 
00060     GC_err_printf2("start: 0x%lx, appr. length: %ld", base, GC_size(base));
00061 }
00062 
00063 void (*GC_print_heap_obj)(/* char * s, ptr_t p */) =
00064                             GC_default_print_heap_obj_proc;
00065 
00066 void GC_print_source_ptr(p)
00067 ptr_t p;
00068 {
00069     ptr_t base = GC_base(p);
00070     if (0 == base) {
00071        if (0 == p) {
00072            GC_err_printf0("in register");
00073        } else {
00074            GC_err_printf0("in root set");
00075        }
00076     } else {
00077        GC_err_printf0("in object at ");
00078        (*GC_print_heap_obj)(base);
00079     }
00080 }
00081 
00082 void GC_bl_init()
00083 {
00084 # ifndef ALL_INTERIOR_POINTERS
00085     GC_old_normal_bl = (word *)
00086                       GC_scratch_alloc((word)(sizeof (page_hash_table)));
00087     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
00088                                    ((word)(sizeof(page_hash_table)));
00089     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
00090         GC_err_printf0("Insufficient memory for black list\n");
00091         EXIT();
00092     }
00093     GC_clear_bl(GC_old_normal_bl);
00094     GC_clear_bl(GC_incomplete_normal_bl);
00095 # endif
00096     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
00097     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
00098                                    ((word)(sizeof(page_hash_table)));
00099     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
00100         GC_err_printf0("Insufficient memory for black list\n");
00101         EXIT();
00102     }
00103     GC_clear_bl(GC_old_stack_bl);
00104     GC_clear_bl(GC_incomplete_stack_bl);
00105 }
00106               
00107 void GC_clear_bl(doomed)
00108 word *doomed;
00109 {
00110     BZERO(doomed, sizeof(page_hash_table));
00111 }
00112 
00113 void GC_copy_bl(old, new)
00114 word *new, *old;
00115 {
00116     BCOPY(old, new, sizeof(page_hash_table));
00117 }
00118 
00119 static word total_stack_black_listed();
00120 
00121 /* Signal the completion of a collection.  Turn the incomplete black  */
00122 /* lists into new black lists, etc.                                   */                    
00123 void GC_promote_black_lists()
00124 {
00125     word * very_old_normal_bl = GC_old_normal_bl;
00126     word * very_old_stack_bl = GC_old_stack_bl;
00127     
00128     GC_old_normal_bl = GC_incomplete_normal_bl;
00129     GC_old_stack_bl = GC_incomplete_stack_bl;
00130 #   ifndef ALL_INTERIOR_POINTERS
00131       GC_clear_bl(very_old_normal_bl);
00132 #   endif
00133     GC_clear_bl(very_old_stack_bl);
00134     GC_incomplete_normal_bl = very_old_normal_bl;
00135     GC_incomplete_stack_bl = very_old_stack_bl;
00136     GC_total_stack_black_listed = total_stack_black_listed();
00137 #   ifdef PRINTSTATS
00138        GC_printf1("%ld bytes in heap blacklisted for interior pointers\n",
00139                  (unsigned long)GC_total_stack_black_listed);
00140 #   endif
00141     if (GC_total_stack_black_listed != 0) {
00142         GC_black_list_spacing =
00143               HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
00144     }
00145     if (GC_black_list_spacing < 3 * HBLKSIZE) {
00146        GC_black_list_spacing = 3 * HBLKSIZE;
00147     }
00148 }
00149 
00150 void GC_unpromote_black_lists()
00151 {
00152 #   ifndef ALL_INTERIOR_POINTERS
00153       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
00154 #   endif
00155     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
00156 }
00157 
00158 # ifndef ALL_INTERIOR_POINTERS
00159 /* P is not a valid pointer reference, but it falls inside     */
00160 /* the plausible heap bounds.                                  */
00161 /* Add it to the normal incomplete black list if appropriate.  */
00162 #ifdef PRINT_BLACK_LIST
00163   void GC_add_to_black_list_normal(p, source)
00164   ptr_t source;
00165 #else
00166   void GC_add_to_black_list_normal(p)
00167 #endif
00168 word p;
00169 {
00170     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
00171     {
00172         register int index = PHT_HASH(p);
00173         
00174         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
00175 #          ifdef PRINT_BLACK_LIST
00176               if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
00177                 GC_err_printf2(
00178                      "Black listing (normal) 0x%lx referenced from 0x%lx ",
00179                       (unsigned long) p, (unsigned long) source);
00180                 GC_print_source_ptr(source);
00181                 GC_err_puts("\n");
00182               }
00183 #           endif
00184             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
00185         } /* else this is probably just an interior pointer to an allocated */
00186           /* object, and isn't worth black listing.                       */
00187     }
00188 }
00189 # endif
00190 
00191 /* And the same for false pointers from the stack. */
00192 #ifdef PRINT_BLACK_LIST
00193   void GC_add_to_black_list_stack(p, source)
00194   ptr_t source;
00195 #else
00196   void GC_add_to_black_list_stack(p)
00197 #endif
00198 word p;
00199 {
00200     register int index = PHT_HASH(p);
00201         
00202     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
00203 #      ifdef PRINT_BLACK_LIST
00204            if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
00205                 GC_err_printf2(
00206                      "Black listing (stack) 0x%lx referenced from 0x%lx ",
00207                       (unsigned long)p, (unsigned long)source);
00208                 GC_print_source_ptr(source);
00209                 GC_err_puts("\n");
00210            }
00211 #       endif
00212        set_pht_entry_from_index(GC_incomplete_stack_bl, index);
00213     }
00214 }
00215 
00216 /*
00217  * Is the block starting at h of size len bytes black listed?   If so,
00218  * return the address of the next plausible r such that (r, len) might not
00219  * be black listed.  (R may not actually be in the heap.  We guarantee only
00220  * that every smaller value of r after h is also black listed.)
00221  * If (h,len) is not black listed, return 0.
00222  * Knows about the structure of the black list hash tables.
00223  */
00224 struct hblk * GC_is_black_listed(h, len)
00225 struct hblk * h;
00226 word len;
00227 {
00228     register int index = PHT_HASH((word)h);
00229     register word i;
00230     word nblocks = divHBLKSZ(len);
00231 
00232 #   ifndef ALL_INTERIOR_POINTERS
00233       if (get_pht_entry_from_index(GC_old_normal_bl, index)
00234           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
00235         return(h+1);
00236       }
00237 #   endif
00238     
00239     for (i = 0; ; ) {
00240         if (GC_old_stack_bl[divWORDSZ(index)] == 0
00241             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
00242             /* An easy case */
00243             i += WORDSZ - modWORDSZ(index);
00244         } else {
00245           if (get_pht_entry_from_index(GC_old_stack_bl, index)
00246               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
00247             return(h+i+1);
00248           }
00249           i++;
00250         }
00251         if (i >= nblocks) break;
00252         index = PHT_HASH((word)(h+i));
00253     }
00254     return(0);
00255 }
00256 
00257 
00258 /* Return the number of blacklisted blocks in a given range.   */
00259 /* Used only for statistical purposes.                         */
00260 /* Looks only at the GC_incomplete_stack_bl.                   */
00261 word GC_number_stack_black_listed(start, endp1)
00262 struct hblk *start, *endp1;
00263 {
00264     register struct hblk * h;
00265     word result = 0;
00266     
00267     for (h = start; h < endp1; h++) {
00268         register int index = PHT_HASH((word)h);
00269         
00270         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
00271     }
00272     return(result);
00273 }
00274 
00275 
00276 /* Return the total number of (stack) black-listed bytes. */
00277 static word total_stack_black_listed()
00278 {
00279     register unsigned i;
00280     word total = 0;
00281     
00282     for (i = 0; i < GC_n_heap_sects; i++) {
00283        struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
00284        word len = (word) GC_heap_sects[i].hs_bytes;
00285        struct hblk * endp1 = start + len/HBLKSIZE;
00286        
00287        total += GC_number_stack_black_listed(start, endp1);
00288     }
00289     return(total * HBLKSIZE);
00290 }
00291