Back to index

plt-scheme  4.2.1
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 "private/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 # if defined(__STDC__) || defined(__cplusplus)
00056     void GC_default_print_heap_obj_proc(ptr_t p)
00057 # else
00058     void GC_default_print_heap_obj_proc(p)
00059     ptr_t p;
00060 # endif
00061 {
00062     ptr_t base = GC_base(p);
00063 
00064     GC_err_printf2("start: 0x%lx, appr. length: %ld", base, GC_size(base));
00065 }
00066 
00067 void (*GC_print_heap_obj) GC_PROTO((ptr_t p)) =
00068                             GC_default_print_heap_obj_proc;
00069 
00070 void GC_print_source_ptr(p)
00071 ptr_t p;
00072 {
00073     ptr_t base = GC_base(p);
00074     if (0 == base) {
00075        if (0 == p) {
00076            GC_err_printf0("in register");
00077        } else {
00078            GC_err_printf0("in root set");
00079        }
00080     } else {
00081        GC_err_printf0("in object at ");
00082        (*GC_print_heap_obj)(base);
00083     }
00084 }
00085 
00086 void GC_bl_init()
00087 {
00088     if (!GC_all_interior_pointers) {
00089       GC_old_normal_bl = (word *)
00090                       GC_scratch_alloc((word)(sizeof (page_hash_table)));
00091       GC_incomplete_normal_bl = (word *)GC_scratch_alloc
00092                                    ((word)(sizeof(page_hash_table)));
00093       if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
00094         GC_err_printf0("Insufficient memory for black list\n");
00095         EXIT();
00096       }
00097       GC_clear_bl(GC_old_normal_bl);
00098       GC_clear_bl(GC_incomplete_normal_bl);
00099     }
00100     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
00101     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
00102                                    ((word)(sizeof(page_hash_table)));
00103     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
00104         GC_err_printf0("Insufficient memory for black list\n");
00105         EXIT();
00106     }
00107     GC_clear_bl(GC_old_stack_bl);
00108     GC_clear_bl(GC_incomplete_stack_bl);
00109 }
00110               
00111 void GC_clear_bl(doomed)
00112 word *doomed;
00113 {
00114     BZERO(doomed, sizeof(page_hash_table));
00115 }
00116 
00117 void GC_copy_bl(old, new)
00118 word *new, *old;
00119 {
00120     BCOPY(old, new, sizeof(page_hash_table));
00121 }
00122 
00123 static word total_stack_black_listed();
00124 
00125 /* Signal the completion of a collection.  Turn the incomplete black  */
00126 /* lists into new black lists, etc.                                   */                    
00127 void GC_promote_black_lists()
00128 {
00129     word * very_old_normal_bl = GC_old_normal_bl;
00130     word * very_old_stack_bl = GC_old_stack_bl;
00131     
00132     GC_old_normal_bl = GC_incomplete_normal_bl;
00133     GC_old_stack_bl = GC_incomplete_stack_bl;
00134     if (!GC_all_interior_pointers) {
00135       GC_clear_bl(very_old_normal_bl);
00136     }
00137     GC_clear_bl(very_old_stack_bl);
00138     GC_incomplete_normal_bl = very_old_normal_bl;
00139     GC_incomplete_stack_bl = very_old_stack_bl;
00140     GC_total_stack_black_listed = total_stack_black_listed();
00141 #   ifdef PRINTSTATS
00142        GC_printf1("%ld bytes in heap blacklisted for interior pointers\n",
00143                  (unsigned long)GC_total_stack_black_listed);
00144 #   endif
00145     if (GC_total_stack_black_listed != 0) {
00146         GC_black_list_spacing =
00147               HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
00148     }
00149     if (GC_black_list_spacing < 3 * HBLKSIZE) {
00150        GC_black_list_spacing = 3 * HBLKSIZE;
00151     }
00152     if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
00153        GC_black_list_spacing = MAXHINCR * HBLKSIZE;
00154        /* Makes it easier to allocate really huge blocks, which otherwise */
00155        /* may have problems with nonuniform blacklist distributions.     */
00156        /* This way we should always succeed immediately after growing the */ 
00157        /* heap.                                                   */
00158     }
00159 }
00160 
00161 void GC_unpromote_black_lists()
00162 {
00163     if (!GC_all_interior_pointers) {
00164       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
00165     }
00166     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
00167 }
00168 
00169 /* P is not a valid pointer reference, but it falls inside     */
00170 /* the plausible heap bounds.                                  */
00171 /* Add it to the normal incomplete black list if appropriate.  */
00172 #ifdef PRINT_BLACK_LIST
00173   void GC_add_to_black_list_normal(p, source)
00174   ptr_t source;
00175 #else
00176   void GC_add_to_black_list_normal(p)
00177 #endif
00178 word p;
00179 {
00180     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
00181     {
00182         register int index = PHT_HASH(p);
00183         
00184         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
00185 #          ifdef PRINT_BLACK_LIST
00186               if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
00187                 GC_err_printf2(
00188                      "Black listing (normal) 0x%lx referenced from 0x%lx ",
00189                       (unsigned long) p, (unsigned long) source);
00190                 GC_print_source_ptr(source);
00191                 GC_err_puts("\n");
00192               }
00193 #           endif
00194             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
00195         } /* else this is probably just an interior pointer to an allocated */
00196           /* object, and isn't worth black listing.                       */
00197     }
00198 }
00199 
00200 /* And the same for false pointers from the stack. */
00201 #ifdef PRINT_BLACK_LIST
00202   void GC_add_to_black_list_stack(p, source)
00203   ptr_t source;
00204 #else
00205   void GC_add_to_black_list_stack(p)
00206 #endif
00207 word p;
00208 {
00209     register int index = PHT_HASH(p);
00210         
00211     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
00212 #      ifdef PRINT_BLACK_LIST
00213            if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
00214                 GC_err_printf2(
00215                      "Black listing (stack) 0x%lx referenced from 0x%lx ",
00216                       (unsigned long)p, (unsigned long)source);
00217                 GC_print_source_ptr(source);
00218                 GC_err_puts("\n");
00219            }
00220 #       endif
00221        set_pht_entry_from_index(GC_incomplete_stack_bl, index);
00222     }
00223 }
00224 
00225 /*
00226  * Is the block starting at h of size len bytes black listed?   If so,
00227  * return the address of the next plausible r such that (r, len) might not
00228  * be black listed.  (R may not actually be in the heap.  We guarantee only
00229  * that every smaller value of r after h is also black listed.)
00230  * If (h,len) is not black listed, return 0.
00231  * Knows about the structure of the black list hash tables.
00232  */
00233 struct hblk * GC_is_black_listed(h, len)
00234 struct hblk * h;
00235 word len;
00236 {
00237     register int index = PHT_HASH((word)h);
00238     register word i;
00239     word nblocks = divHBLKSZ(len);
00240 
00241     if (!GC_all_interior_pointers) {
00242       if (get_pht_entry_from_index(GC_old_normal_bl, index)
00243           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
00244         return(h+1);
00245       }
00246     }
00247     
00248     for (i = 0; ; ) {
00249         if (GC_old_stack_bl[divWORDSZ(index)] == 0
00250             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
00251             /* An easy case */
00252             i += WORDSZ - modWORDSZ(index);
00253         } else {
00254           if (get_pht_entry_from_index(GC_old_stack_bl, index)
00255               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
00256             return(h+i+1);
00257           }
00258           i++;
00259         }
00260         if (i >= nblocks) break;
00261         index = PHT_HASH((word)(h+i));
00262     }
00263     return(0);
00264 }
00265 
00266 
00267 /* Return the number of blacklisted blocks in a given range.   */
00268 /* Used only for statistical purposes.                         */
00269 /* Looks only at the GC_incomplete_stack_bl.                   */
00270 word GC_number_stack_black_listed(start, endp1)
00271 struct hblk *start, *endp1;
00272 {
00273     register struct hblk * h;
00274     word result = 0;
00275     
00276     for (h = start; h < endp1; h++) {
00277         register int index = PHT_HASH((word)h);
00278         
00279         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
00280     }
00281     return(result);
00282 }
00283 
00284 
00285 /* Return the total number of (stack) black-listed bytes. */
00286 static word total_stack_black_listed()
00287 {
00288     register unsigned i;
00289     word total = 0;
00290     
00291     for (i = 0; i < GC_n_heap_sects; i++) {
00292        struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
00293        word len = (word) GC_heap_sects[i].hs_bytes;
00294        struct hblk * endp1 = start + len/HBLKSIZE;
00295        
00296        total += GC_number_stack_black_listed(start, endp1);
00297     }
00298     return(total * HBLKSIZE);
00299 }
00300