Annotation of OpenXM_contrib/gc/mark_rts.c, Revision 1.1
1.1 ! maekawa 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, October 9, 1995 1:06 pm PDT */
! 15: # include <stdio.h>
! 16: # include "gc_priv.h"
! 17:
! 18: /* Data structure for list of root sets. */
! 19: /* We keep a hash table, so that we can filter out duplicate additions. */
! 20: /* Under Win32, we need to do a better job of filtering overlaps, so */
! 21: /* we resort to sequential search, and pay the price. */
! 22: /* This is really declared in gc_priv.h:
! 23: struct roots {
! 24: ptr_t r_start;
! 25: ptr_t r_end;
! 26: # ifndef MSWIN32
! 27: struct roots * r_next;
! 28: # endif
! 29: GC_bool r_tmp;
! 30: -- Delete before registering new dynamic libraries
! 31: };
! 32:
! 33: struct roots GC_static_roots[MAX_ROOT_SETS];
! 34: */
! 35:
! 36: static int n_root_sets = 0;
! 37:
! 38: /* GC_static_roots[0..n_root_sets) contains the valid root sets. */
! 39:
! 40: # if !defined(NO_DEBUGGING)
! 41: /* For debugging: */
! 42: void GC_print_static_roots()
! 43: {
! 44: register int i;
! 45: size_t total = 0;
! 46:
! 47: for (i = 0; i < n_root_sets; i++) {
! 48: GC_printf2("From 0x%lx to 0x%lx ",
! 49: (unsigned long) GC_static_roots[i].r_start,
! 50: (unsigned long) GC_static_roots[i].r_end);
! 51: if (GC_static_roots[i].r_tmp) {
! 52: GC_printf0(" (temporary)\n");
! 53: } else {
! 54: GC_printf0("\n");
! 55: }
! 56: total += GC_static_roots[i].r_end - GC_static_roots[i].r_start;
! 57: }
! 58: GC_printf1("Total size: %ld\n", (unsigned long) total);
! 59: if (GC_root_size != total) {
! 60: GC_printf1("GC_root_size incorrect: %ld!!\n",
! 61: (unsigned long) GC_root_size);
! 62: }
! 63: }
! 64: # endif /* NO_DEBUGGING */
! 65:
! 66: /* Primarily for debugging support: */
! 67: /* Is the address p in one of the registered static */
! 68: /* root sections? */
! 69: GC_bool GC_is_static_root(p)
! 70: ptr_t p;
! 71: {
! 72: static int last_root_set = 0;
! 73: register int i;
! 74:
! 75:
! 76: if (p >= GC_static_roots[last_root_set].r_start
! 77: && p < GC_static_roots[last_root_set].r_end) return(TRUE);
! 78: for (i = 0; i < n_root_sets; i++) {
! 79: if (p >= GC_static_roots[i].r_start
! 80: && p < GC_static_roots[i].r_end) {
! 81: last_root_set = i;
! 82: return(TRUE);
! 83: }
! 84: }
! 85: return(FALSE);
! 86: }
! 87:
! 88: #ifndef MSWIN32
! 89: /*
! 90: # define LOG_RT_SIZE 6
! 91: # define RT_SIZE (1 << LOG_RT_SIZE) -- Power of 2, may be != MAX_ROOT_SETS
! 92:
! 93: struct roots * GC_root_index[RT_SIZE];
! 94: -- Hash table header. Used only to check whether a range is
! 95: -- already present.
! 96: -- really defined in gc_priv.h
! 97: */
! 98:
! 99: static int rt_hash(addr)
! 100: char * addr;
! 101: {
! 102: word result = (word) addr;
! 103: # if CPP_WORDSZ > 8*LOG_RT_SIZE
! 104: result ^= result >> 8*LOG_RT_SIZE;
! 105: # endif
! 106: # if CPP_WORDSZ > 4*LOG_RT_SIZE
! 107: result ^= result >> 4*LOG_RT_SIZE;
! 108: # endif
! 109: result ^= result >> 2*LOG_RT_SIZE;
! 110: result ^= result >> LOG_RT_SIZE;
! 111: result &= (RT_SIZE-1);
! 112: return(result);
! 113: }
! 114:
! 115: /* Is a range starting at b already in the table? If so return a */
! 116: /* pointer to it, else NIL. */
! 117: struct roots * GC_roots_present(b)
! 118: char *b;
! 119: {
! 120: register int h = rt_hash(b);
! 121: register struct roots *p = GC_root_index[h];
! 122:
! 123: while (p != 0) {
! 124: if (p -> r_start == (ptr_t)b) return(p);
! 125: p = p -> r_next;
! 126: }
! 127: return(FALSE);
! 128: }
! 129:
! 130: /* Add the given root structure to the index. */
! 131: static void add_roots_to_index(p)
! 132: struct roots *p;
! 133: {
! 134: register int h = rt_hash(p -> r_start);
! 135:
! 136: p -> r_next = GC_root_index[h];
! 137: GC_root_index[h] = p;
! 138: }
! 139:
! 140: # else /* MSWIN32 */
! 141:
! 142: # define add_roots_to_index(p)
! 143:
! 144: # endif
! 145:
! 146:
! 147:
! 148:
! 149: word GC_root_size = 0;
! 150:
! 151: void GC_add_roots(b, e)
! 152: char * b; char * e;
! 153: {
! 154: DCL_LOCK_STATE;
! 155:
! 156: DISABLE_SIGNALS();
! 157: LOCK();
! 158: GC_add_roots_inner(b, e, FALSE);
! 159: UNLOCK();
! 160: ENABLE_SIGNALS();
! 161: }
! 162:
! 163:
! 164: /* Add [b,e) to the root set. Adding the same interval a second time */
! 165: /* is a moderately fast noop, and hence benign. We do not handle */
! 166: /* different but overlapping intervals efficiently. (We do handle */
! 167: /* them correctly.) */
! 168: /* Tmp specifies that the interval may be deleted before */
! 169: /* reregistering dynamic libraries. */
! 170: void GC_add_roots_inner(b, e, tmp)
! 171: char * b; char * e;
! 172: GC_bool tmp;
! 173: {
! 174: struct roots * old;
! 175:
! 176: # ifdef MSWIN32
! 177: /* Spend the time to ensure that there are no overlapping */
! 178: /* or adjacent intervals. */
! 179: /* This could be done faster with e.g. a */
! 180: /* balanced tree. But the execution time here is */
! 181: /* virtually guaranteed to be dominated by the time it */
! 182: /* takes to scan the roots. */
! 183: {
! 184: register int i;
! 185:
! 186: for (i = 0; i < n_root_sets; i++) {
! 187: old = GC_static_roots + i;
! 188: if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
! 189: if ((ptr_t)b < old -> r_start) {
! 190: old -> r_start = (ptr_t)b;
! 191: GC_root_size += (old -> r_start - (ptr_t)b);
! 192: }
! 193: if ((ptr_t)e > old -> r_end) {
! 194: old -> r_end = (ptr_t)e;
! 195: GC_root_size += ((ptr_t)e - old -> r_end);
! 196: }
! 197: old -> r_tmp &= tmp;
! 198: break;
! 199: }
! 200: }
! 201: if (i < n_root_sets) {
! 202: /* merge other overlapping intervals */
! 203: struct roots *other;
! 204:
! 205: for (i++; i < n_root_sets; i++) {
! 206: other = GC_static_roots + i;
! 207: b = (char *)(other -> r_start);
! 208: e = (char *)(other -> r_end);
! 209: if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
! 210: if ((ptr_t)b < old -> r_start) {
! 211: old -> r_start = (ptr_t)b;
! 212: GC_root_size += (old -> r_start - (ptr_t)b);
! 213: }
! 214: if ((ptr_t)e > old -> r_end) {
! 215: old -> r_end = (ptr_t)e;
! 216: GC_root_size += ((ptr_t)e - old -> r_end);
! 217: }
! 218: old -> r_tmp &= other -> r_tmp;
! 219: /* Delete this entry. */
! 220: GC_root_size -= (other -> r_end - other -> r_start);
! 221: other -> r_start = GC_static_roots[n_root_sets-1].r_start;
! 222: other -> r_end = GC_static_roots[n_root_sets-1].r_end;
! 223: n_root_sets--;
! 224: }
! 225: }
! 226: return;
! 227: }
! 228: }
! 229: # else
! 230: old = GC_roots_present(b);
! 231: if (old != 0) {
! 232: if ((ptr_t)e <= old -> r_end) /* already there */ return;
! 233: /* else extend */
! 234: GC_root_size += (ptr_t)e - old -> r_end;
! 235: old -> r_end = (ptr_t)e;
! 236: return;
! 237: }
! 238: # endif
! 239: if (n_root_sets == MAX_ROOT_SETS) {
! 240: ABORT("Too many root sets\n");
! 241: }
! 242: GC_static_roots[n_root_sets].r_start = (ptr_t)b;
! 243: GC_static_roots[n_root_sets].r_end = (ptr_t)e;
! 244: GC_static_roots[n_root_sets].r_tmp = tmp;
! 245: # ifndef MSWIN32
! 246: GC_static_roots[n_root_sets].r_next = 0;
! 247: # endif
! 248: add_roots_to_index(GC_static_roots + n_root_sets);
! 249: GC_root_size += (ptr_t)e - (ptr_t)b;
! 250: n_root_sets++;
! 251: }
! 252:
! 253: void GC_clear_roots GC_PROTO((void))
! 254: {
! 255: DCL_LOCK_STATE;
! 256:
! 257: DISABLE_SIGNALS();
! 258: LOCK();
! 259: n_root_sets = 0;
! 260: GC_root_size = 0;
! 261: # ifndef MSWIN32
! 262: {
! 263: register int i;
! 264:
! 265: for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
! 266: }
! 267: # endif
! 268: UNLOCK();
! 269: ENABLE_SIGNALS();
! 270: }
! 271:
! 272: /* Internal use only; lock held. */
! 273: void GC_remove_tmp_roots()
! 274: {
! 275: register int i;
! 276:
! 277: for (i = 0; i < n_root_sets; ) {
! 278: if (GC_static_roots[i].r_tmp) {
! 279: GC_root_size -=
! 280: (GC_static_roots[i].r_end - GC_static_roots[i].r_start);
! 281: GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start;
! 282: GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end;
! 283: GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp;
! 284: n_root_sets--;
! 285: } else {
! 286: i++;
! 287: }
! 288: }
! 289: # ifndef MSWIN32
! 290: {
! 291: register int i;
! 292:
! 293: for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
! 294: for (i = 0; i < n_root_sets; i++)
! 295: add_roots_to_index(GC_static_roots + i);
! 296: }
! 297: # endif
! 298:
! 299: }
! 300:
! 301: ptr_t GC_approx_sp()
! 302: {
! 303: word dummy;
! 304:
! 305: return((ptr_t)(&dummy));
! 306: }
! 307:
! 308: /*
! 309: * Data structure for excluded static roots.
! 310: * Real declaration is in gc_priv.h.
! 311:
! 312: struct exclusion {
! 313: ptr_t e_start;
! 314: ptr_t e_end;
! 315: };
! 316:
! 317: struct exclusion GC_excl_table[MAX_EXCLUSIONS];
! 318: -- Array of exclusions, ascending
! 319: -- address order.
! 320: */
! 321:
! 322: size_t GC_excl_table_entries = 0; /* Number of entries in use. */
! 323:
! 324: /* Return the first exclusion range that includes an address >= start_addr */
! 325: /* Assumes the exclusion table contains at least one entry (namely the */
! 326: /* GC data structures). */
! 327: struct exclusion * GC_next_exclusion(start_addr)
! 328: ptr_t start_addr;
! 329: {
! 330: size_t low = 0;
! 331: size_t high = GC_excl_table_entries - 1;
! 332: size_t mid;
! 333:
! 334: while (high > low) {
! 335: mid = (low + high) >> 1;
! 336: /* low <= mid < high */
! 337: if ((word) GC_excl_table[mid].e_end <= (word) start_addr) {
! 338: low = mid + 1;
! 339: } else {
! 340: high = mid;
! 341: }
! 342: }
! 343: if ((word) GC_excl_table[low].e_end <= (word) start_addr) return 0;
! 344: return GC_excl_table + low;
! 345: }
! 346:
! 347: void GC_exclude_static_roots(start, finish)
! 348: GC_PTR start;
! 349: GC_PTR finish;
! 350: {
! 351: struct exclusion * next;
! 352: size_t next_index, i;
! 353:
! 354: if (0 == GC_excl_table_entries) {
! 355: next = 0;
! 356: } else {
! 357: next = GC_next_exclusion(start);
! 358: }
! 359: if (0 != next) {
! 360: if ((word)(next -> e_start) < (word) finish) {
! 361: /* incomplete error check. */
! 362: ABORT("exclusion ranges overlap");
! 363: }
! 364: if ((word)(next -> e_start) == (word) finish) {
! 365: /* extend old range backwards */
! 366: next -> e_start = (ptr_t)start;
! 367: return;
! 368: }
! 369: next_index = next - GC_excl_table;
! 370: for (i = GC_excl_table_entries; i > next_index; --i) {
! 371: GC_excl_table[i] = GC_excl_table[i-1];
! 372: }
! 373: } else {
! 374: next_index = GC_excl_table_entries;
! 375: }
! 376: if (GC_excl_table_entries == MAX_EXCLUSIONS) ABORT("Too many exclusions");
! 377: GC_excl_table[next_index].e_start = (ptr_t)start;
! 378: GC_excl_table[next_index].e_end = (ptr_t)finish;
! 379: ++GC_excl_table_entries;
! 380: }
! 381:
! 382: /* Invoke push_conditional on ranges that are not excluded. */
! 383: void GC_push_conditional_with_exclusions(bottom, top, all)
! 384: ptr_t bottom;
! 385: ptr_t top;
! 386: int all;
! 387: {
! 388: struct exclusion * next;
! 389: ptr_t excl_start;
! 390:
! 391: while (bottom < top) {
! 392: next = GC_next_exclusion(bottom);
! 393: if (0 == next || (excl_start = next -> e_start) >= top) {
! 394: GC_push_conditional(bottom, top, all);
! 395: return;
! 396: }
! 397: if (excl_start > bottom) GC_push_conditional(bottom, excl_start, all);
! 398: bottom = next -> e_end;
! 399: }
! 400: }
! 401:
! 402: /*
! 403: * In the absence of threads, push the stack contents.
! 404: * In the presence of threads, push enough of the current stack
! 405: * to ensure that callee-save registers saved in collector frames have been
! 406: * seen.
! 407: */
! 408: void GC_push_current_stack(cold_gc_frame)
! 409: ptr_t cold_gc_frame;
! 410: {
! 411: # if defined(THREADS)
! 412: if (0 == cold_gc_frame) return;
! 413: # ifdef STACK_GROWS_DOWN
! 414: GC_push_all_eager(GC_approx_sp(), cold_gc_frame);
! 415: # else
! 416: GC_push_all_eager( cold_gc_frame, GC_approx_sp() );
! 417: # endif
! 418: # else
! 419: # ifdef STACK_GROWS_DOWN
! 420: GC_push_all_stack_partially_eager( GC_approx_sp(), GC_stackbottom,
! 421: cold_gc_frame );
! 422: # else
! 423: GC_push_all_stack_partially_eager( GC_stackbottom, GC_approx_sp(),
! 424: cold_gc_frame );
! 425: # endif
! 426: # endif /* !THREADS */
! 427: }
! 428:
! 429: /*
! 430: * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional
! 431: * on groups of pointers) on every top level accessible pointer.
! 432: * If all is FALSE, arrange to push only possibly altered values.
! 433: * Cold_gc_frame is an address inside a GC frame that
! 434: * remains valid until all marking is complete.
! 435: * A zero value indicates that it's OK to miss some
! 436: * register values.
! 437: */
! 438: void GC_push_roots(all, cold_gc_frame)
! 439: GC_bool all;
! 440: ptr_t cold_gc_frame;
! 441: {
! 442: register int i;
! 443:
! 444: /*
! 445: * push registers - i.e., call GC_push_one(r) for each
! 446: * register contents r.
! 447: */
! 448: # ifdef USE_GENERIC_PUSH_REGS
! 449: GC_generic_push_regs(cold_gc_frame);
! 450: # else
! 451: GC_push_regs(); /* usually defined in machine_dep.c */
! 452: # endif
! 453:
! 454: /*
! 455: * Next push static data. This must happen early on, since it's
! 456: * not robust against mark stack overflow.
! 457: */
! 458: /* Reregister dynamic libraries, in case one got added. */
! 459: # if (defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(PCR)) \
! 460: && !defined(SRC_M3)
! 461: GC_remove_tmp_roots();
! 462: GC_register_dynamic_libraries();
! 463: # endif
! 464: /* Mark everything in static data areas */
! 465: for (i = 0; i < n_root_sets; i++) {
! 466: GC_push_conditional_with_exclusions(
! 467: GC_static_roots[i].r_start,
! 468: GC_static_roots[i].r_end, all);
! 469: }
! 470:
! 471: /*
! 472: * Now traverse stacks.
! 473: */
! 474: # if !defined(USE_GENERIC_PUSH_REGS)
! 475: GC_push_current_stack(cold_gc_frame);
! 476: /* IN the threads case, this only pushes collector frames. */
! 477: /* In the USE_GENERIC_PUSH_REGS case, this is done inside */
! 478: /* GC_push_regs, so that we catch callee-save registers saved */
! 479: /* inside the GC_push_regs frame. */
! 480: # endif
! 481: if (GC_push_other_roots != 0) (*GC_push_other_roots)();
! 482: /* In the threads case, this also pushes thread stacks. */
! 483: }
! 484:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mark_rts.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gc