[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.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, 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>