[BACK]Return to mark_rts.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / gc

Annotation of OpenXM_contrib2/asir2000/gc/mark_rts.c, Revision 1.3

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, 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);
1.3     ! noro      415:          /* For IA64, the register stack backing store is handled      */
        !           416:          /* in the thread-specific code.                               */
1.1       noro      417: #       else
                    418:          GC_push_all_eager( cold_gc_frame, GC_approx_sp() );
                    419: #       endif
                    420: #   else
                    421: #      ifdef STACK_GROWS_DOWN
                    422:            GC_push_all_stack_partially_eager( GC_approx_sp(), GC_stackbottom,
                    423:                                               cold_gc_frame );
1.2       noro      424: #          ifdef IA64
                    425:              /* We also need to push the register stack backing store. */
                    426:              /* This should really be done in the same way as the      */
                    427:              /* regular stack.  For now we fudge it a bit.             */
                    428:              /* Note that the backing store grows up, so we can't use  */
                    429:              /* GC_push_all_stack_partially_eager.                     */
                    430:              {
                    431:                extern word GC_save_regs_ret_val;
                    432:                        /* Previously set to backing store pointer.     */
                    433:                ptr_t bsp = (ptr_t) GC_save_regs_ret_val;
                    434:                ptr_t cold_gc_bs_pointer;
                    435: #              ifdef ALL_INTERIOR_POINTERS
                    436:                  cold_gc_bs_pointer = bsp - 2048;
                    437:                  if (cold_gc_bs_pointer < BACKING_STORE_BASE) {
                    438:                    cold_gc_bs_pointer = BACKING_STORE_BASE;
                    439:                  }
                    440:                  GC_push_all(BACKING_STORE_BASE, cold_gc_bs_pointer);
                    441: #              else
                    442:                  cold_gc_bs_pointer = BACKING_STORE_BASE;
                    443: #              endif
                    444:                GC_push_all_eager(cold_gc_bs_pointer, bsp);
                    445:                /* All values should be sufficiently aligned that we    */
                    446:                /* dont have to worry about the boundary.               */
                    447:              }
                    448: #          endif
1.1       noro      449: #       else
                    450:            GC_push_all_stack_partially_eager( GC_stackbottom, GC_approx_sp(),
                    451:                                               cold_gc_frame );
                    452: #       endif
                    453: #   endif /* !THREADS */
                    454: }
                    455:
                    456: /*
                    457:  * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional
                    458:  * on groups of pointers) on every top level accessible pointer.
                    459:  * If all is FALSE, arrange to push only possibly altered values.
                    460:  * Cold_gc_frame is an address inside a GC frame that
                    461:  * remains valid until all marking is complete.
                    462:  * A zero value indicates that it's OK to miss some
                    463:  * register values.
                    464:  */
                    465: void GC_push_roots(all, cold_gc_frame)
                    466: GC_bool all;
                    467: ptr_t cold_gc_frame;
                    468: {
                    469:     register int i;
                    470:
                    471:     /*
                    472:      * push registers - i.e., call GC_push_one(r) for each
                    473:      * register contents r.
                    474:      */
                    475: #   ifdef USE_GENERIC_PUSH_REGS
                    476:        GC_generic_push_regs(cold_gc_frame);
                    477: #   else
                    478:         GC_push_regs(); /* usually defined in machine_dep.c */
                    479: #   endif
                    480:
                    481:     /*
                    482:      * Next push static data.  This must happen early on, since it's
                    483:      * not robust against mark stack overflow.
                    484:      */
                    485:      /* Reregister dynamic libraries, in case one got added.   */
                    486: #      if (defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(PCR)) \
                    487:            && !defined(SRC_M3)
                    488:          GC_remove_tmp_roots();
                    489:          GC_register_dynamic_libraries();
                    490: #      endif
                    491:      /* Mark everything in static data areas                             */
                    492:        for (i = 0; i < n_root_sets; i++) {
                    493:          GC_push_conditional_with_exclusions(
                    494:                             GC_static_roots[i].r_start,
                    495:                             GC_static_roots[i].r_end, all);
                    496:        }
                    497:
                    498:     /*
                    499:      * Now traverse stacks.
                    500:      */
                    501: #   if !defined(USE_GENERIC_PUSH_REGS)
                    502:        GC_push_current_stack(cold_gc_frame);
                    503:        /* IN the threads case, this only pushes collector frames.      */
                    504:        /* In the USE_GENERIC_PUSH_REGS case, this is done inside       */
                    505:        /* GC_push_regs, so that we catch callee-save registers saved   */
                    506:        /* inside the GC_push_regs frame.                               */
1.3     ! noro      507:        /* In the case of linux threads on Ia64, the hot section of     */
        !           508:        /* the main stack is marked here, but the register stack        */
        !           509:        /* backing store is handled in the threads-specific code.       */
1.1       noro      510: #   endif
                    511:     if (GC_push_other_roots != 0) (*GC_push_other_roots)();
                    512:        /* In the threads case, this also pushes thread stacks. */
                    513: }
                    514:

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