URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [boehm-gc/] [blacklst.c] - Rev 739
Go to most recent revision | Compare with Previous | Blame | View Log
/* * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. * * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. * * Permission is hereby granted to use or copy this program * for any purpose, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was * modified is included with the above copyright notice. */ /* Boehm, August 9, 1995 6:09 pm PDT */ # include "private/gc_priv.h" /* * We maintain several hash tables of hblks that have had false hits. * Each contains one bit per hash bucket; If any page in the bucket * has had a false hit, we assume that all of them have. * See the definition of page_hash_table in gc_private.h. * False hits from the stack(s) are much more dangerous than false hits * from elsewhere, since the former can pin a large object that spans the * block, eventhough it does not start on the dangerous block. */ /* * Externally callable routines are: * GC_add_to_black_list_normal * GC_add_to_black_list_stack * GC_promote_black_lists * GC_is_black_listed * * All require that the allocator lock is held. */ /* Pointers to individual tables. We replace one table by another by */ /* switching these pointers. */ word * GC_old_normal_bl; /* Nonstack false references seen at last full */ /* collection. */ word * GC_incomplete_normal_bl; /* Nonstack false references seen since last */ /* full collection. */ word * GC_old_stack_bl; word * GC_incomplete_stack_bl; word GC_total_stack_black_listed; word GC_black_list_spacing = MINHINCR*HBLKSIZE; /* Initial rough guess */ void GC_clear_bl(); # if defined(__STDC__) || defined(__cplusplus) void GC_default_print_heap_obj_proc(ptr_t p) # else void GC_default_print_heap_obj_proc(p) ptr_t p; # endif { ptr_t base = GC_base(p); GC_err_printf2("start: 0x%lx, appr. length: %ld", base, GC_size(base)); } void (*GC_print_heap_obj) GC_PROTO((ptr_t p)) = GC_default_print_heap_obj_proc; void GC_print_source_ptr(p) ptr_t p; { ptr_t base = GC_base(p); if (0 == base) { if (0 == p) { GC_err_printf0("in register"); } else { GC_err_printf0("in root set"); } } else { GC_err_printf0("in object at "); (*GC_print_heap_obj)(base); } } void GC_bl_init() { if (!GC_all_interior_pointers) { GC_old_normal_bl = (word *) GC_scratch_alloc((word)(sizeof (page_hash_table))); GC_incomplete_normal_bl = (word *)GC_scratch_alloc ((word)(sizeof(page_hash_table))); if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) { GC_err_printf0("Insufficient memory for black list\n"); EXIT(); } GC_clear_bl(GC_old_normal_bl); GC_clear_bl(GC_incomplete_normal_bl); } GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table))); GC_incomplete_stack_bl = (word *)GC_scratch_alloc ((word)(sizeof(page_hash_table))); if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) { GC_err_printf0("Insufficient memory for black list\n"); EXIT(); } GC_clear_bl(GC_old_stack_bl); GC_clear_bl(GC_incomplete_stack_bl); } void GC_clear_bl(doomed) word *doomed; { BZERO(doomed, sizeof(page_hash_table)); } void GC_copy_bl(old, new) word *new, *old; { BCOPY(old, new, sizeof(page_hash_table)); } static word total_stack_black_listed(); /* Signal the completion of a collection. Turn the incomplete black */ /* lists into new black lists, etc. */ void GC_promote_black_lists() { word * very_old_normal_bl = GC_old_normal_bl; word * very_old_stack_bl = GC_old_stack_bl; GC_old_normal_bl = GC_incomplete_normal_bl; GC_old_stack_bl = GC_incomplete_stack_bl; if (!GC_all_interior_pointers) { GC_clear_bl(very_old_normal_bl); } GC_clear_bl(very_old_stack_bl); GC_incomplete_normal_bl = very_old_normal_bl; GC_incomplete_stack_bl = very_old_stack_bl; GC_total_stack_black_listed = total_stack_black_listed(); # ifdef PRINTSTATS GC_printf1("%ld bytes in heap blacklisted for interior pointers\n", (unsigned long)GC_total_stack_black_listed); # endif if (GC_total_stack_black_listed != 0) { GC_black_list_spacing = HBLKSIZE*(GC_heapsize/GC_total_stack_black_listed); } if (GC_black_list_spacing < 3 * HBLKSIZE) { GC_black_list_spacing = 3 * HBLKSIZE; } if (GC_black_list_spacing > MAXHINCR * HBLKSIZE) { GC_black_list_spacing = MAXHINCR * HBLKSIZE; /* Makes it easier to allocate really huge blocks, which otherwise */ /* may have problems with nonuniform blacklist distributions. */ /* This way we should always succeed immediately after growing the */ /* heap. */ } } void GC_unpromote_black_lists() { if (!GC_all_interior_pointers) { GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl); } GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl); } /* P is not a valid pointer reference, but it falls inside */ /* the plausible heap bounds. */ /* Add it to the normal incomplete black list if appropriate. */ #ifdef PRINT_BLACK_LIST void GC_add_to_black_list_normal(p, source) ptr_t source; #else void GC_add_to_black_list_normal(p) #endif word p; { if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return; { register int index = PHT_HASH(p); if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) { # ifdef PRINT_BLACK_LIST if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) { GC_err_printf2( "Black listing (normal) 0x%lx referenced from 0x%lx ", (unsigned long) p, (unsigned long) source); GC_print_source_ptr(source); GC_err_puts("\n"); } # endif set_pht_entry_from_index(GC_incomplete_normal_bl, index); } /* else this is probably just an interior pointer to an allocated */ /* object, and isn't worth black listing. */ } } /* And the same for false pointers from the stack. */ #ifdef PRINT_BLACK_LIST void GC_add_to_black_list_stack(p, source) ptr_t source; #else void GC_add_to_black_list_stack(p) #endif word p; { register int index = PHT_HASH(p); if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) { # ifdef PRINT_BLACK_LIST if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) { GC_err_printf2( "Black listing (stack) 0x%lx referenced from 0x%lx ", (unsigned long)p, (unsigned long)source); GC_print_source_ptr(source); GC_err_puts("\n"); } # endif set_pht_entry_from_index(GC_incomplete_stack_bl, index); } } /* * Is the block starting at h of size len bytes black listed? If so, * return the address of the next plausible r such that (r, len) might not * be black listed. (R may not actually be in the heap. We guarantee only * that every smaller value of r after h is also black listed.) * If (h,len) is not black listed, return 0. * Knows about the structure of the black list hash tables. */ struct hblk * GC_is_black_listed(h, len) struct hblk * h; word len; { register int index = PHT_HASH((word)h); register word i; word nblocks = divHBLKSZ(len); if (!GC_all_interior_pointers) { if (get_pht_entry_from_index(GC_old_normal_bl, index) || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) { return(h+1); } } for (i = 0; ; ) { if (GC_old_stack_bl[divWORDSZ(index)] == 0 && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) { /* An easy case */ i += WORDSZ - modWORDSZ(index); } else { if (get_pht_entry_from_index(GC_old_stack_bl, index) || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) { return(h+i+1); } i++; } if (i >= nblocks) break; index = PHT_HASH((word)(h+i)); } return(0); } /* Return the number of blacklisted blocks in a given range. */ /* Used only for statistical purposes. */ /* Looks only at the GC_incomplete_stack_bl. */ word GC_number_stack_black_listed(start, endp1) struct hblk *start, *endp1; { register struct hblk * h; word result = 0; for (h = start; h < endp1; h++) { register int index = PHT_HASH((word)h); if (get_pht_entry_from_index(GC_old_stack_bl, index)) result++; } return(result); } /* Return the total number of (stack) black-listed bytes. */ static word total_stack_black_listed() { register unsigned i; word total = 0; for (i = 0; i < GC_n_heap_sects; i++) { struct hblk * start = (struct hblk *) GC_heap_sects[i].hs_start; word len = (word) GC_heap_sects[i].hs_bytes; struct hblk * endp1 = start + len/HBLKSIZE; total += GC_number_stack_black_listed(start, endp1); } return(total * HBLKSIZE); }
Go to most recent revision | Compare with Previous | Blame | View Log