[BACK]Return to blacklst.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / gc5.3

Annotation of OpenXM_contrib2/asir2000/gc5.3/blacklst.c, Revision 1.1.1.1

1.1       noro        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, August 9, 1995 6:09 pm PDT */
                     15: # include "gc_priv.h"
                     16:
                     17: /*
                     18:  * We maintain several hash tables of hblks that have had false hits.
                     19:  * Each contains one bit per hash bucket;  If any page in the bucket
                     20:  * has had a false hit, we assume that all of them have.
                     21:  * See the definition of page_hash_table in gc_private.h.
                     22:  * False hits from the stack(s) are much more dangerous than false hits
                     23:  * from elsewhere, since the former can pin a large object that spans the
                     24:  * block, eventhough it does not start on the dangerous block.
                     25:  */
                     26:
                     27: /*
                     28:  * Externally callable routines are:
                     29:
                     30:  * GC_add_to_black_list_normal
                     31:  * GC_add_to_black_list_stack
                     32:  * GC_promote_black_lists
                     33:  * GC_is_black_listed
                     34:  *
                     35:  * All require that the allocator lock is held.
                     36:  */
                     37:
                     38: /* Pointers to individual tables.  We replace one table by another by  */
                     39: /* switching these pointers.                                           */
                     40: word * GC_old_normal_bl;
                     41:                /* Nonstack false references seen at last full          */
                     42:                /* collection.                                          */
                     43: word * GC_incomplete_normal_bl;
                     44:                /* Nonstack false references seen since last            */
                     45:                /* full collection.                                     */
                     46: word * GC_old_stack_bl;
                     47: word * GC_incomplete_stack_bl;
                     48:
                     49: word GC_total_stack_black_listed;
                     50:
                     51: word GC_black_list_spacing = MINHINCR*HBLKSIZE;  /* Initial rough guess */
                     52:
                     53: void GC_clear_bl();
                     54:
                     55: void GC_default_print_heap_obj_proc(p)
                     56: ptr_t p;
                     57: {
                     58:     ptr_t base = GC_base(p);
                     59:
                     60:     GC_err_printf2("start: 0x%lx, appr. length: %ld", base, GC_size(base));
                     61: }
                     62:
                     63: void (*GC_print_heap_obj)(/* char * s, ptr_t p */) =
                     64:                                GC_default_print_heap_obj_proc;
                     65:
                     66: void GC_print_source_ptr(p)
                     67: ptr_t p;
                     68: {
                     69:     ptr_t base = GC_base(p);
                     70:     if (0 == base) {
                     71:        if (0 == p) {
                     72:            GC_err_printf0("in register");
                     73:        } else {
                     74:            GC_err_printf0("in root set");
                     75:        }
                     76:     } else {
                     77:        GC_err_printf0("in object at ");
                     78:        (*GC_print_heap_obj)(base);
                     79:     }
                     80: }
                     81:
                     82: void GC_bl_init()
                     83: {
                     84: # ifndef ALL_INTERIOR_POINTERS
                     85:     GC_old_normal_bl = (word *)
                     86:                         GC_scratch_alloc((word)(sizeof (page_hash_table)));
                     87:     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
                     88:                                        ((word)(sizeof(page_hash_table)));
                     89:     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
                     90:         GC_err_printf0("Insufficient memory for black list\n");
                     91:         EXIT();
                     92:     }
                     93:     GC_clear_bl(GC_old_normal_bl);
                     94:     GC_clear_bl(GC_incomplete_normal_bl);
                     95: # endif
                     96:     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
                     97:     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
                     98:                                        ((word)(sizeof(page_hash_table)));
                     99:     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
                    100:         GC_err_printf0("Insufficient memory for black list\n");
                    101:         EXIT();
                    102:     }
                    103:     GC_clear_bl(GC_old_stack_bl);
                    104:     GC_clear_bl(GC_incomplete_stack_bl);
                    105: }
                    106:
                    107: void GC_clear_bl(doomed)
                    108: word *doomed;
                    109: {
                    110:     BZERO(doomed, sizeof(page_hash_table));
                    111: }
                    112:
                    113: void GC_copy_bl(old, new)
                    114: word *new, *old;
                    115: {
                    116:     BCOPY(old, new, sizeof(page_hash_table));
                    117: }
                    118:
                    119: static word total_stack_black_listed();
                    120:
                    121: /* Signal the completion of a collection.  Turn the incomplete black   */
                    122: /* lists into new black lists, etc.                                    */
                    123: void GC_promote_black_lists()
                    124: {
                    125:     word * very_old_normal_bl = GC_old_normal_bl;
                    126:     word * very_old_stack_bl = GC_old_stack_bl;
                    127:
                    128:     GC_old_normal_bl = GC_incomplete_normal_bl;
                    129:     GC_old_stack_bl = GC_incomplete_stack_bl;
                    130: #   ifndef ALL_INTERIOR_POINTERS
                    131:       GC_clear_bl(very_old_normal_bl);
                    132: #   endif
                    133:     GC_clear_bl(very_old_stack_bl);
                    134:     GC_incomplete_normal_bl = very_old_normal_bl;
                    135:     GC_incomplete_stack_bl = very_old_stack_bl;
                    136:     GC_total_stack_black_listed = total_stack_black_listed();
                    137: #   ifdef PRINTSTATS
                    138:        GC_printf1("%ld bytes in heap blacklisted for interior pointers\n",
                    139:                   (unsigned long)GC_total_stack_black_listed);
                    140: #   endif
                    141:     if (GC_total_stack_black_listed != 0) {
                    142:         GC_black_list_spacing =
                    143:                HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed);
                    144:     }
                    145:     if (GC_black_list_spacing < 3 * HBLKSIZE) {
                    146:        GC_black_list_spacing = 3 * HBLKSIZE;
                    147:     }
                    148:     if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) {
                    149:        GC_black_list_spacing = MAXHINCR * HBLKSIZE;
                    150:        /* Makes it easier to allocate really huge blocks, which otherwise */
                    151:        /* may have problems with nonuniform blacklist distributions.      */
                    152:        /* This way we should always succeed immediately after growing the */
                    153:        /* heap.                                                           */
                    154:     }
                    155: }
                    156:
                    157: void GC_unpromote_black_lists()
                    158: {
                    159: #   ifndef ALL_INTERIOR_POINTERS
                    160:       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
                    161: #   endif
                    162:     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
                    163: }
                    164:
                    165: # ifndef ALL_INTERIOR_POINTERS
                    166: /* P is not a valid pointer reference, but it falls inside     */
                    167: /* the plausible heap bounds.                                  */
                    168: /* Add it to the normal incomplete black list if appropriate.  */
                    169: #ifdef PRINT_BLACK_LIST
                    170:   void GC_add_to_black_list_normal(p, source)
                    171:   ptr_t source;
                    172: #else
                    173:   void GC_add_to_black_list_normal(p)
                    174: #endif
                    175: word p;
                    176: {
                    177:     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
                    178:     {
                    179:         register int index = PHT_HASH(p);
                    180:
                    181:         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
                    182: #          ifdef PRINT_BLACK_LIST
                    183:                if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
                    184:                  GC_err_printf2(
                    185:                        "Black listing (normal) 0x%lx referenced from 0x%lx ",
                    186:                        (unsigned long) p, (unsigned long) source);
                    187:                  GC_print_source_ptr(source);
                    188:                  GC_err_puts("\n");
                    189:                }
                    190: #           endif
                    191:             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
                    192:         } /* else this is probably just an interior pointer to an allocated */
                    193:           /* object, and isn't worth black listing.                        */
                    194:     }
                    195: }
                    196: # endif
                    197:
                    198: /* And the same for false pointers from the stack. */
                    199: #ifdef PRINT_BLACK_LIST
                    200:   void GC_add_to_black_list_stack(p, source)
                    201:   ptr_t source;
                    202: #else
                    203:   void GC_add_to_black_list_stack(p)
                    204: #endif
                    205: word p;
                    206: {
                    207:     register int index = PHT_HASH(p);
                    208:
                    209:     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
                    210: #      ifdef PRINT_BLACK_LIST
                    211:            if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
                    212:                  GC_err_printf2(
                    213:                        "Black listing (stack) 0x%lx referenced from 0x%lx ",
                    214:                        (unsigned long)p, (unsigned long)source);
                    215:                  GC_print_source_ptr(source);
                    216:                  GC_err_puts("\n");
                    217:            }
                    218: #       endif
                    219:        set_pht_entry_from_index(GC_incomplete_stack_bl, index);
                    220:     }
                    221: }
                    222:
                    223: /*
                    224:  * Is the block starting at h of size len bytes black listed?   If so,
                    225:  * return the address of the next plausible r such that (r, len) might not
                    226:  * be black listed.  (R may not actually be in the heap.  We guarantee only
                    227:  * that every smaller value of r after h is also black listed.)
                    228:  * If (h,len) is not black listed, return 0.
                    229:  * Knows about the structure of the black list hash tables.
                    230:  */
                    231: struct hblk * GC_is_black_listed(h, len)
                    232: struct hblk * h;
                    233: word len;
                    234: {
                    235:     register int index = PHT_HASH((word)h);
                    236:     register word i;
                    237:     word nblocks = divHBLKSZ(len);
                    238:
                    239: #   ifndef ALL_INTERIOR_POINTERS
                    240:       if (get_pht_entry_from_index(GC_old_normal_bl, index)
                    241:           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
                    242:         return(h+1);
                    243:       }
                    244: #   endif
                    245:
                    246:     for (i = 0; ; ) {
                    247:         if (GC_old_stack_bl[divWORDSZ(index)] == 0
                    248:             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
                    249:             /* An easy case */
                    250:             i += WORDSZ - modWORDSZ(index);
                    251:         } else {
                    252:           if (get_pht_entry_from_index(GC_old_stack_bl, index)
                    253:               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
                    254:             return(h+i+1);
                    255:           }
                    256:           i++;
                    257:         }
                    258:         if (i >= nblocks) break;
                    259:         index = PHT_HASH((word)(h+i));
                    260:     }
                    261:     return(0);
                    262: }
                    263:
                    264:
                    265: /* Return the number of blacklisted blocks in a given range.   */
                    266: /* Used only for statistical purposes.                         */
                    267: /* Looks only at the GC_incomplete_stack_bl.                   */
                    268: word GC_number_stack_black_listed(start, endp1)
                    269: struct hblk *start, *endp1;
                    270: {
                    271:     register struct hblk * h;
                    272:     word result = 0;
                    273:
                    274:     for (h = start; h < endp1; h++) {
                    275:         register int index = PHT_HASH((word)h);
                    276:
                    277:         if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++;
                    278:     }
                    279:     return(result);
                    280: }
                    281:
                    282:
                    283: /* Return the total number of (stack) black-listed bytes. */
                    284: static word total_stack_black_listed()
                    285: {
                    286:     register unsigned i;
                    287:     word total = 0;
                    288:
                    289:     for (i = 0; i < GC_n_heap_sects; i++) {
                    290:        struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start;
                    291:        word len = (word) GC_heap_sects[i].hs_bytes;
                    292:        struct hblk * endp1 = start + len/HBLKSIZE;
                    293:
                    294:        total += GC_number_stack_black_listed(start, endp1);
                    295:     }
                    296:     return(total * HBLKSIZE);
                    297: }
                    298:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>