Back to index

lightning-sunbird  0.9+nobinonly
mark_rts.c
Go to the documentation of this file.
00001 /* 
00002  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
00003  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
00004  *
00005  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00006  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00007  *
00008  * Permission is hereby granted to use or copy this program
00009  * for any purpose,  provided the above notices are retained on all copies.
00010  * Permission to modify the code and to distribute modified code is granted,
00011  * provided the above notices are retained, and a notice that the code was
00012  * modified is included with the above copyright notice.
00013  */
00014 /* Boehm, October 9, 1995 1:06 pm PDT */
00015 # include <stdio.h>
00016 # include "gc_priv.h"
00017 
00018 /* Data structure for list of root sets.                       */
00019 /* We keep a hash table, so that we can filter out duplicate additions.      */
00020 /* Under Win32, we need to do a better job of filtering overlaps, so  */
00021 /* we resort to sequential search, and pay the price.                 */
00022 /* This is really declared in gc_priv.h:
00023 struct roots {
00024        ptr_t r_start;
00025        ptr_t r_end;
00026  #     ifndef MSWIN32
00027          struct roots * r_next;
00028  #     endif
00029        GC_bool r_tmp;
00030               -- Delete before registering new dynamic libraries
00031 };
00032 
00033 struct roots GC_static_roots[MAX_ROOT_SETS];
00034 */
00035 
00036 static int n_root_sets = 0;
00037 
00038        /* GC_static_roots[0..n_root_sets) contains the valid root sets. */
00039 
00040 # if !defined(NO_DEBUGGING)
00041 /* For debugging:    */
00042 void GC_print_static_roots()
00043 {
00044     register int i;
00045     size_t total = 0;
00046     
00047     for (i = 0; i < n_root_sets; i++) {
00048         GC_printf2("From 0x%lx to 0x%lx ",
00049                  (unsigned long) GC_static_roots[i].r_start,
00050                  (unsigned long) GC_static_roots[i].r_end);
00051         if (GC_static_roots[i].r_tmp) {
00052             GC_printf0(" (temporary)\n");
00053         } else {
00054             GC_printf0("\n");
00055         }
00056         total += GC_static_roots[i].r_end - GC_static_roots[i].r_start;
00057     }
00058     GC_printf1("Total size: %ld\n", (unsigned long) total);
00059     if (GC_root_size != total) {
00060        GC_printf1("GC_root_size incorrect: %ld!!\n",
00061                  (unsigned long) GC_root_size);
00062     }
00063 }
00064 # endif /* NO_DEBUGGING */
00065 
00066 /* Primarily for debugging support:       */
00067 /* Is the address p in one of the registered static                   */
00068 /* root sections?                                              */
00069 GC_bool GC_is_static_root(p)
00070 ptr_t p;
00071 {
00072     static int last_root_set = 0;
00073     register int i;
00074     
00075     
00076     if (p >= GC_static_roots[last_root_set].r_start
00077         && p < GC_static_roots[last_root_set].r_end) return(TRUE);
00078     for (i = 0; i < n_root_sets; i++) {
00079        if (p >= GC_static_roots[i].r_start
00080             && p < GC_static_roots[i].r_end) {
00081             last_root_set = i;
00082             return(TRUE);
00083         }
00084     }
00085     return(FALSE);
00086 }
00087 
00088 #ifndef MSWIN32
00089 /* 
00090 #   define LOG_RT_SIZE 6
00091 #   define RT_SIZE (1 << LOG_RT_SIZE)  -- Power of 2, may be != MAX_ROOT_SETS
00092 
00093     struct roots * GC_root_index[RT_SIZE];
00094        -- Hash table header.  Used only to check whether a range is
00095        -- already present.
00096        -- really defined in gc_priv.h
00097 */
00098 
00099 static int rt_hash(addr)
00100 char * addr;
00101 {
00102     word result = (word) addr;
00103 #   if CPP_WORDSZ > 8*LOG_RT_SIZE
00104        result ^= result >> 8*LOG_RT_SIZE;
00105 #   endif
00106 #   if CPP_WORDSZ > 4*LOG_RT_SIZE
00107        result ^= result >> 4*LOG_RT_SIZE;
00108 #   endif
00109     result ^= result >> 2*LOG_RT_SIZE;
00110     result ^= result >> LOG_RT_SIZE;
00111     result &= (RT_SIZE-1);
00112     return(result);
00113 }
00114 
00115 /* Is a range starting at b already in the table? If so return a      */
00116 /* pointer to it, else NIL.                                    */
00117 struct roots * GC_roots_present(b)
00118 char *b;
00119 {
00120     register int h = rt_hash(b);
00121     register struct roots *p = GC_root_index[h];
00122     
00123     while (p != 0) {
00124         if (p -> r_start == (ptr_t)b) return(p);
00125         p = p -> r_next;
00126     }
00127     return(FALSE);
00128 }
00129 
00130 /* Add the given root structure to the index. */
00131 static void add_roots_to_index(p)
00132 struct roots *p;
00133 {
00134     register int h = rt_hash(p -> r_start);
00135     
00136     p -> r_next = GC_root_index[h];
00137     GC_root_index[h] = p;
00138 }
00139 
00140 # else /* MSWIN32 */
00141 
00142 #   define add_roots_to_index(p)
00143 
00144 # endif
00145 
00146 
00147 
00148 
00149 word GC_root_size = 0;
00150 
00151 void GC_add_roots(b, e)
00152 char * b; char * e;
00153 {
00154     DCL_LOCK_STATE;
00155     
00156     DISABLE_SIGNALS();
00157     LOCK();
00158     GC_add_roots_inner(b, e, FALSE);
00159     UNLOCK();
00160     ENABLE_SIGNALS();
00161 }
00162 
00163 /* Add [b,e) to the root set.  Adding the same interval a second time */
00164 /* is a moderately fast noop, and hence benign.  We do not handle     */
00165 /* different but overlapping intervals efficiently.  (We do handle    */
00166 /* them correctly.)                                            */
00167 /* Tmp specifies that the interval may be deleted before              */
00168 /* reregistering dynamic libraries.                                   */ 
00169 void GC_add_roots_inner(b, e, tmp)
00170 char * b; char * e;
00171 GC_bool tmp;
00172 {
00173     struct roots * old;
00174     
00175 #   ifdef MSWIN32
00176       /* Spend the time to ensure that there are no overlapping       */
00177       /* or adjacent intervals.                                */
00178       /* This could be done faster with e.g. a                 */
00179       /* balanced tree.  But the execution time here is        */
00180       /* virtually guaranteed to be dominated by the time it   */
00181       /* takes to scan the roots.                       */
00182       {
00183         register int i;
00184         
00185         for (i = 0; i < n_root_sets; i++) {
00186             old = GC_static_roots + i;
00187             if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
00188                 if ((ptr_t)b < old -> r_start) {
00189                     old -> r_start = (ptr_t)b;
00190                     GC_root_size += (old -> r_start - (ptr_t)b);
00191                 }
00192                 if ((ptr_t)e > old -> r_end) {
00193                     old -> r_end = (ptr_t)e;
00194                     GC_root_size += ((ptr_t)e - old -> r_end);
00195                 }
00196                 old -> r_tmp &= tmp;
00197                 break;
00198             }
00199         }
00200         if (i < n_root_sets) {
00201           /* merge other overlapping intervals */
00202             struct roots *other;
00203             
00204             for (i++; i < n_root_sets; i++) {
00205               other = GC_static_roots + i;
00206               b = (char *)(other -> r_start);
00207               e = (char *)(other -> r_end);
00208               if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
00209                 if ((ptr_t)b < old -> r_start) {
00210                     old -> r_start = (ptr_t)b;
00211                     GC_root_size += (old -> r_start - (ptr_t)b);
00212                 }
00213                 if ((ptr_t)e > old -> r_end) {
00214                     old -> r_end = (ptr_t)e;
00215                     GC_root_size += ((ptr_t)e - old -> r_end);
00216                 }
00217                 old -> r_tmp &= other -> r_tmp;
00218                 /* Delete this entry. */
00219                   GC_root_size -= (other -> r_end - other -> r_start);
00220                   other -> r_start = GC_static_roots[n_root_sets-1].r_start;
00221                   other -> r_end = GC_static_roots[n_root_sets-1].r_end;
00222                                   n_root_sets--;
00223               }
00224             }
00225           return;
00226         }
00227       }
00228 #   else
00229       old = GC_roots_present(b);
00230       if (old != 0) {
00231         if ((ptr_t)e <= old -> r_end) /* already there */ return;
00232         /* else extend */
00233         GC_root_size += (ptr_t)e - old -> r_end;
00234         old -> r_end = (ptr_t)e;
00235         return;
00236       }
00237 #   endif
00238     if (n_root_sets == MAX_ROOT_SETS) {
00239         ABORT("Too many root sets\n");
00240     }
00241     GC_static_roots[n_root_sets].r_start = (ptr_t)b;
00242     GC_static_roots[n_root_sets].r_end = (ptr_t)e;
00243     GC_static_roots[n_root_sets].r_tmp = tmp;
00244 #   ifndef MSWIN32
00245       GC_static_roots[n_root_sets].r_next = 0;
00246 #   endif
00247     add_roots_to_index(GC_static_roots + n_root_sets);
00248     GC_root_size += (ptr_t)e - (ptr_t)b;
00249     n_root_sets++;
00250 }
00251 
00252 void GC_remove_roots(b, e)
00253 char * b; char * e;
00254 {
00255     DCL_LOCK_STATE;
00256     
00257     DISABLE_SIGNALS();
00258     LOCK();
00259     GC_remove_roots_inner(b, e);
00260     UNLOCK();
00261     ENABLE_SIGNALS();
00262 }
00263 
00264 void GC_remove_roots_inner(b, e)
00265 char * b; char * e;
00266 {
00267     register int i;
00268     
00269     for (i = 0; i < n_root_sets; ) {
00270        if (GC_static_roots[i].r_start == (ptr_t)b && GC_static_roots[i].r_end == (ptr_t)e) {
00271            GC_root_size -=
00272               (GC_static_roots[i].r_end - GC_static_roots[i].r_start);
00273            GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start;
00274            GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end;
00275            GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp;
00276            n_root_sets--;
00277        } else {
00278            i++;
00279        }
00280     }
00281 #   ifndef MSWIN32
00282     /* rehash the root table. */
00283     for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
00284     for (i = 0; i < n_root_sets; i++)
00285         add_roots_to_index(GC_static_roots + i);
00286 #   endif
00287 }
00288 
00289 void GC_clear_roots GC_PROTO((void))
00290 {
00291     DCL_LOCK_STATE;
00292     
00293     DISABLE_SIGNALS();
00294     LOCK();
00295     n_root_sets = 0;
00296     GC_root_size = 0;
00297 #   ifndef MSWIN32
00298     {
00299        register int i;
00300        
00301        for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
00302     }
00303 #   endif
00304     UNLOCK();
00305     ENABLE_SIGNALS();
00306 }
00307 
00308 /* Internal use only; lock held.   */
00309 void GC_remove_tmp_roots()
00310 {
00311     register int i;
00312     
00313     for (i = 0; i < n_root_sets; ) {
00314        if (GC_static_roots[i].r_tmp) {
00315            GC_root_size -=
00316               (GC_static_roots[i].r_end - GC_static_roots[i].r_start);
00317            GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start;
00318            GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end;
00319            GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp;
00320            n_root_sets--;
00321        } else {
00322            i++;
00323        }
00324     }
00325 #   ifndef MSWIN32
00326     {
00327        register int i;
00328        
00329        for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0;
00330        for (i = 0; i < n_root_sets; i++)
00331               add_roots_to_index(GC_static_roots + i);
00332     }
00333 #   endif
00334     
00335 }
00336 
00337 ptr_t GC_approx_sp()
00338 {
00339     word dummy;
00340     
00341     return((ptr_t)(&dummy));
00342 }
00343 
00344 /*
00345  * Data structure for excluded static roots.
00346  * Real declaration is in gc_priv.h.
00347 
00348 struct exclusion {
00349     ptr_t e_start;
00350     ptr_t e_end;
00351 };
00352 
00353 struct exclusion GC_excl_table[MAX_EXCLUSIONS];
00354                                    -- Array of exclusions, ascending
00355                                    -- address order.
00356 */
00357 
00358 size_t GC_excl_table_entries = 0;  /* Number of entries in use.         */
00359 
00360 /* Return the first exclusion range that includes an address >= start_addr */
00361 /* Assumes the exclusion table contains at least one entry (namely the          */
00362 /* GC data structures).                                                  */
00363 struct exclusion * GC_next_exclusion(start_addr)
00364 ptr_t start_addr;
00365 {
00366     size_t low = 0;
00367     size_t high = GC_excl_table_entries - 1;
00368     size_t mid;
00369 
00370     while (high > low) {
00371        mid = (low + high) >> 1;
00372        /* low <= mid < high */
00373        if ((word) GC_excl_table[mid].e_end <= (word) start_addr) {
00374            low = mid + 1;
00375        } else {
00376            high = mid;
00377        }
00378     }
00379     if ((word) GC_excl_table[low].e_end <= (word) start_addr) return 0;
00380     return GC_excl_table + low;
00381 }
00382 
00383 void GC_exclude_static_roots(start, finish)
00384 GC_PTR start;
00385 GC_PTR finish;
00386 {
00387     struct exclusion * next;
00388     size_t next_index, i;
00389 
00390     if (0 == GC_excl_table_entries) {
00391        next = 0;
00392     } else {
00393        next = GC_next_exclusion(start);
00394     }
00395     if (0 != next) {
00396       if ((word)(next -> e_start) < (word) finish) {
00397        /* incomplete error check. */
00398        ABORT("exclusion ranges overlap");
00399       }  
00400       if ((word)(next -> e_start) == (word) finish) {
00401         /* extend old range backwards     */
00402           next -> e_start = (ptr_t)start;
00403          return;
00404       }
00405       next_index = next - GC_excl_table;
00406       for (i = GC_excl_table_entries; i > next_index; --i) {
00407        GC_excl_table[i] = GC_excl_table[i-1];
00408       }
00409     } else {
00410       next_index = GC_excl_table_entries;
00411     }
00412     if (GC_excl_table_entries == MAX_EXCLUSIONS) ABORT("Too many exclusions");
00413     GC_excl_table[next_index].e_start = (ptr_t)start;
00414     GC_excl_table[next_index].e_end = (ptr_t)finish;
00415     ++GC_excl_table_entries;
00416 }
00417 
00418 /* Invoke push_conditional on ranges that are not excluded. */
00419 void GC_push_conditional_with_exclusions(bottom, top, all)
00420 ptr_t bottom;
00421 ptr_t top;
00422 int all;
00423 {
00424     struct exclusion * next;
00425     ptr_t excl_start;
00426 
00427     while (bottom < top) {
00428         next = GC_next_exclusion(bottom);
00429        if (0 == next || (excl_start = next -> e_start) >= top) {
00430            GC_push_conditional(bottom, top, all);
00431            return;
00432        }
00433        if (excl_start > bottom) GC_push_conditional(bottom, excl_start, all);
00434        bottom = next -> e_end;
00435     }
00436 }
00437 
00438 /*
00439  * In the absence of threads, push the stack contents.
00440  * In the presence of threads, push enough of the current stack
00441  * to ensure that callee-save registers saved in collector frames have been
00442  * seen.
00443  */
00444 void GC_push_current_stack(cold_gc_frame)
00445 ptr_t cold_gc_frame;
00446 {
00447 #   if defined(THREADS)
00448        if (0 == cold_gc_frame) return;
00449 #       ifdef STACK_GROWS_DOWN
00450          GC_push_all_eager(GC_approx_sp(), cold_gc_frame);
00451 #       else
00452          GC_push_all_eager( cold_gc_frame, GC_approx_sp() );
00453 #       endif
00454 #   else
00455 #      ifdef STACK_GROWS_DOWN
00456            GC_push_all_stack_partially_eager( GC_approx_sp(), GC_stackbottom,
00457                                           cold_gc_frame );
00458 #       else
00459            GC_push_all_stack_partially_eager( GC_stackbottom, GC_approx_sp(),
00460                                           cold_gc_frame );
00461 #       endif
00462 #   endif /* !THREADS */
00463 }
00464 
00465 /*
00466  * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional
00467  * on groups of pointers) on every top level accessible pointer.
00468  * If all is FALSE, arrange to push only possibly altered values.
00469  * Cold_gc_frame is an address inside a GC frame that
00470  * remains valid until all marking is complete.
00471  * A zero value indicates that it's OK to miss some
00472  * register values.
00473  */
00474 void GC_push_roots(all, cold_gc_frame)
00475 GC_bool all;
00476 ptr_t cold_gc_frame;
00477 {
00478     register int i;
00479 
00480     /*
00481      * push registers - i.e., call GC_push_one(r) for each
00482      * register contents r.
00483      */
00484 #   ifdef USE_GENERIC_PUSH_REGS
00485        GC_generic_push_regs(cold_gc_frame);
00486 #   else
00487         GC_push_regs(); /* usually defined in machine_dep.c */
00488 #   endif
00489         
00490     /*
00491      * Next push static data.  This must happen early on, since it's
00492      * not robust against mark stack overflow.
00493      */
00494      /* Reregister dynamic libraries, in case one got added.   */
00495 #      if (defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(PCR)) \
00496            && !defined(SRC_M3)
00497          GC_remove_tmp_roots();
00498          if (GC_root_size)
00499              GC_register_dynamic_libraries();
00500 #      endif
00501      /* Mark everything in static data areas                             */
00502        for (i = 0; i < n_root_sets; i++) {
00503          GC_push_conditional_with_exclusions(
00504                           GC_static_roots[i].r_start,
00505                           GC_static_roots[i].r_end, all);
00506        }
00507 
00508     /*
00509      * Now traverse stacks.
00510      */
00511 #   if !defined(USE_GENERIC_PUSH_REGS)
00512        GC_push_current_stack(cold_gc_frame);
00513        /* IN the threads case, this only pushes collector frames.      */
00514        /* In the USE_GENERIC_PUSH_REGS case, this is done inside      */
00515        /* GC_push_regs, so that we catch callee-save registers saved  */
00516        /* inside the GC_push_regs frame.                       */
00517 #   endif
00518     if (GC_push_other_roots != 0) (*GC_push_other_roots)();
00519        /* In the threads case, this also pushes thread stacks. */
00520 }
00521