Back to index

plt-scheme  4.2.1
codetab.inc
Go to the documentation of this file.
00001 
00002 /* Implementation of the "symbol table" for mapping code
00003    pointers to function names. */
00004 
00005 #ifndef MZ_PRECISE_GC
00006 # ifdef USE_SENORA_GC
00007 extern void *GC_base(void *d);
00008 #  define GC_is_marked(p) GC_base(p)
00009 # else
00010 extern MZ_DLLIMPORT int GC_is_marked(void *);
00011 # endif
00012 #endif
00013 
00014 #define LOG_KEY_SIZE 4
00015 #define KEY_MASK ((1 << LOG_KEY_SIZE) - 1)
00016 #define KEY_COUNT (1 << LOG_KEY_SIZE)
00017 
00018 /* In words: */
00019 #define NODE_HEADER_SIZE 3
00020 #define NODE_STARTS_OFFSET 1
00021 #define NODE_GCABLE_OFFSET 2
00022 
00023 static void **tree;
00024 
00025 static int do_clear_symbols(void **t, unsigned long start, int offset, unsigned long addr, int clearing);
00026 static int during_set;
00027 
00028 static void *find_symbol(unsigned long v)
00029 {
00030   unsigned long k;
00031   void **t = tree, *val;
00032   int offset = (JIT_WORD_SIZE * 8);
00033   
00034   while (offset) {
00035     if (!t)
00036       return NULL;
00037     offset -= LOG_KEY_SIZE;
00038     k = ((v >> offset) & KEY_MASK) + NODE_HEADER_SIZE;
00039     val = t[k];
00040     if (!val)
00041       return NULL;
00042     if (*(Scheme_Type *)val)
00043       return val;
00044     t = (void **)val;
00045   }
00046 
00047   printf("Error: walked off end of tree\n");
00048   return NULL;
00049 }
00050 
00051 static void **malloc_node()
00052 {
00053   void **v;
00054   v = (void **)scheme_malloc((KEY_COUNT + NODE_HEADER_SIZE) * sizeof(void *));
00055 
00056   /* Set low bit in each of STARTS and GCABLE so that they're not confused
00057      for pointers: */
00058   ((unsigned long *)v)[NODE_STARTS_OFFSET] = 0x1;
00059   ((unsigned long *)v)[NODE_GCABLE_OFFSET] = 0x1;
00060 
00061   return v;
00062 }
00063 
00064 static void add_symbol(unsigned long start, unsigned long end, void *value, int gc_able)
00065 {
00066   unsigned long k1, k2, split_t_start = 0, split_t_end = 0, i;
00067   int m;
00068   int offset = (JIT_WORD_SIZE * 8), split_offset = 0;
00069   void **t1, **t2, **split_t, *val1, *val2;
00070 
00071   if (!tree) {
00072     REGISTER_SO(tree);
00073     tree = malloc_node();
00074   }
00075 
00076   during_set++;
00077   
00078   t1 = t2 = tree;
00079   split_t = NULL;
00080   while (offset) {
00081     offset -= LOG_KEY_SIZE;
00082 
00083     k1 = ((start >> offset) & KEY_MASK) + NODE_HEADER_SIZE;
00084     if (offset) {
00085       val1 = t1[k1];
00086       if (!val1) {
00087        val1 = malloc_node();
00088        t1[k1] = val1;
00089       }
00090     } else
00091       val1 = t1;
00092 
00093     k2 = ((end >> offset) & KEY_MASK) + NODE_HEADER_SIZE;
00094     if (offset) {
00095       /* Need to go deeper... */
00096       val2 = t2[k2];
00097       if (!val2) {
00098        val2 = malloc_node();
00099        t2[k2] = val2;
00100       }
00101     } else
00102       val2 = t2;
00103 
00104     if (!split_t && (val1 != val2)) {
00105       split_t = t1;
00106       split_t_start = k1;
00107       split_t_end = k2;
00108       split_offset = offset;
00109     }
00110 
00111     t1 = val1;
00112     t2 = val2;
00113   }
00114 
00115   if (!split_t) {
00116     /* assert: t1 == t2 */
00117     split_t = t1;
00118     split_t_start = k1;
00119     split_t_end = k2;
00120   }
00121 
00122   /* Mark start bit: */
00123   m = (1 << (k1 - NODE_HEADER_SIZE + 1));
00124   ((unsigned long *)t1)[NODE_STARTS_OFFSET] |= m;
00125 #ifndef MZ_PRECISE_GC
00126   /* GCABLE flag indicates whether to check for GC later */
00127   if (gc_able)
00128     ((unsigned long *)t1)[NODE_GCABLE_OFFSET] |= m;
00129 #else
00130   /* GCABLE flag indicates whether it's been GCed: */
00131   if (!value)
00132     ((unsigned long *)t1)[NODE_GCABLE_OFFSET] |= m;
00133 #endif
00134 
00135   /* Fill in start and end: */
00136   t1[k1] = value;
00137   t2[k2] = value;
00138   /* Fill in range between branches: */
00139   for (i = split_t_start + 1; i < split_t_end; i++) {
00140     split_t[i] = value;
00141   }
00142   /* Fill in places to right of start branches: */
00143   if (t1 != split_t) {
00144     k1 = ((start >> split_offset) & KEY_MASK) + NODE_HEADER_SIZE;
00145     t1 = split_t[k1];
00146     offset = split_offset;
00147     while (offset) {
00148       offset -= LOG_KEY_SIZE;
00149       k1 = ((start >> offset) & KEY_MASK) + NODE_HEADER_SIZE;
00150       for (i = k1 + 1; i < KEY_COUNT + NODE_HEADER_SIZE; i++) {
00151        t1[i] = value;
00152       }
00153       t1 = t1[k1];
00154     }
00155   }
00156   /* Fill in places to left of end branch: */
00157   if (t2 != split_t) {
00158     k2 = ((end >> split_offset) & KEY_MASK) + NODE_HEADER_SIZE;
00159     t2 = split_t[k2];
00160     offset = split_offset;
00161     while (offset) {
00162       offset -= LOG_KEY_SIZE;
00163       k2 = ((end >> offset) & KEY_MASK) + NODE_HEADER_SIZE;
00164       for (i = NODE_HEADER_SIZE; i < k2; i++) {
00165        t2[i] = value;
00166       }
00167       t2 = t2[k2];
00168     }
00169   }
00170 
00171   --during_set;
00172 
00173 #ifdef MZ_PRECISE_GC
00174   if (!value) {
00175     /* Prune empty branches in the tree. Only do this if this
00176        object is mapped deeply enough in the tree, otherwise
00177        we end up scanning the whole tree. */
00178     do_clear_symbols(tree, start, 0, 0, 0);
00179   }
00180 #endif
00181 }
00182 
00183 static int do_clear_symbols(void **t, unsigned long start, int offset, unsigned long addr, int clearing)
00184   /* If MZ_PRECISE_GC, then offset and addr are not used. */
00185 {
00186   int i, m, j;
00187   void *p, *val, **subt;
00188 
00189   /* Note: this function might be called  (via a GC callback)
00190      while add_symbol is running. */
00191 
00192   for (i = ((start >> offset) & KEY_MASK); i < KEY_COUNT; i++) {
00193     m = (1 << (i + 1));
00194     if (((unsigned long *)t)[NODE_STARTS_OFFSET] & m) {
00195       clearing = 0;
00196       if (((unsigned long *)t)[NODE_GCABLE_OFFSET] & m) {
00197        /* GCable pointer starts here */
00198 #ifndef MZ_PRECISE_GC
00199        /* Conservative GC: GCable flag means use GC_is_marked */
00200        p = (void *)(addr + (i << offset));
00201        if (!GC_is_marked(p))
00202          clearing = 1;
00203 #else
00204        /* Precise GC: GCable flag means it's gone */
00205        clearing = 1;
00206 #endif
00207        if (clearing) {
00208          /* Collected... */
00209          ((unsigned long *)t)[NODE_STARTS_OFFSET] -= m;
00210          ((unsigned long *)t)[NODE_GCABLE_OFFSET] -= m;
00211        }
00212       } else {
00213 #ifdef MZ_PRECISE_GC
00214        return 0;
00215 #endif
00216       }
00217     }
00218 
00219 #ifdef MZ_PRECISE_GC
00220     if (!clearing)
00221       val = NULL;
00222     else
00223 #endif
00224       val = t[i + NODE_HEADER_SIZE];
00225 
00226     if (val) {
00227       if (!*(Scheme_Type *)val) {
00228        subt = (void **)val;
00229        clearing = do_clear_symbols(subt, start,
00230                                 offset - LOG_KEY_SIZE,
00231                                 (addr + (i << offset)),
00232                                 clearing);
00233        if (!during_set) {
00234          /* If the branch is empty, then drop it. */
00235          for (j = 0; j < KEY_COUNT; j++) {
00236            if (subt[j + NODE_HEADER_SIZE])
00237              break;
00238          }
00239          if (j == KEY_COUNT) {
00240            t[i + NODE_HEADER_SIZE] = NULL;
00241          }
00242        }
00243 #ifdef MZ_PRECISE_GC
00244        if (!clearing) {
00245          /* Finished clearing the one item, so return. */
00246          return 0;
00247        }
00248 #endif
00249       } else if (clearing)
00250        t[i + NODE_HEADER_SIZE] = NULL;
00251     }
00252   }
00253 
00254   return clearing;
00255 }
00256 
00257 #ifndef MZ_PRECISE_GC
00258 
00259 static void clear_symbols_for_collected()
00260 {
00261   if (tree) {
00262     do_clear_symbols(tree, 0, (JIT_WORD_SIZE * 8) - LOG_KEY_SIZE, 0, 0); 
00263   }
00264 }
00265 
00266 #endif
00267 
00268 /*============================================================*/
00269 /*                          testing                           */
00270 /*============================================================*/
00271 
00272 #if 0
00273 
00274 Scheme_Type a[] = {1};
00275 Scheme_Type b[] = {2};
00276 Scheme_Type c[] = {3};
00277 
00278 static char *nameof(void *p)
00279 {
00280   if (p == a) return "a";
00281   if (p == b) return "b";
00282   if (p == c) return "c";
00283   if (!p) return "NULL";
00284   return "?";
00285 }
00286 
00287 void *alt_gc;
00288 void *gcs[3];
00289 
00290 int GC_is_marked(void *p)
00291 {
00292   if (alt_gc) {
00293     if (p == alt_gc)
00294       return 1;
00295     else
00296       return 0;
00297   } else {
00298     if ((p == gcs[0])
00299        || (p == gcs[1])
00300        || (p == gcs[2]))
00301       return 0;
00302     else
00303       return 1;
00304   }
00305 }
00306 
00307 void check(int j, int delta, int i, void *expect, unsigned long addr)
00308 {
00309   void *got;
00310 
00311   got = find_symbol(addr);
00312 
00313   if (i == 2)
00314     expect = NULL;
00315 
00316   if (expect != got)
00317     printf("(%d,%d,%d) Expected %s, found %s at %p\n", 
00318           j, delta, i,
00319           nameof(expect), nameof(got),
00320           addr);
00321 }
00322 
00323 int main()
00324 {
00325   int i, d, delta, j;
00326 
00327   for (j = 0; j < 2; j++) {
00328     for (d = 0; d < 16; d++) {
00329       delta = d;
00330       for (i = 0; i < 3; i++) {
00331        if (i != 1)
00332          check(j, delta, 1, NULL, (delta + 0x12341234));
00333        if (!i)
00334          add_symbol(delta + 0x12341200, delta + 0x12341234, a, 1);
00335        check(j, delta, i, a, ((delta + 0x12341234)));
00336        check(j, delta, i, a, ((delta + 0x12341200)));
00337        check(j, delta, i, a, ((delta + 0x12341201)));
00338        check(j, delta, i, a, ((delta + 0x12341210)));
00339        check(j, delta, i, a, ((delta + 0x12341231)));
00340        check(j, delta, i, a, ((delta + 0x12341200)));
00341 
00342        if (i != 1)
00343          check(j, delta, i, NULL, ((delta + 0x12341236)));
00344        if (!i)
00345          add_symbol(delta + 0x12341236, delta + 0x12370000, b, 1);
00346        check(j, delta, i, a, ((delta + 0x12341234)));
00347        if (!i)
00348          check(j, delta, i, NULL, ((delta + 0x12341235)));
00349        check(j, delta, i, b, ((delta + 0x12341236)));
00350        check(j, delta, i, b, ((delta + 0x12370000)));
00351        check(j, delta, i, NULL, ((delta + 0x12370001)));
00352        check(j, delta, i, b, ((delta + 0x12351236)));
00353        check(j, delta, i, b, ((delta + 0x12350000)));
00354        check(j, delta, i, b, ((delta + 0x12360000)));
00355 
00356        if (!i) {
00357          check(j, delta, i, NULL, ((delta + 0x12341235)));
00358          add_symbol(delta + 0x12341235, delta + 0x12341235, c, 1);
00359        }
00360        check(j, delta, i, a, ((delta + 0x12341234)));
00361        check(j, delta, i == 2 ? 0 : i, c, ((delta + 0x12341235)));
00362        check(j, delta, i, b, ((delta + 0x12341236)));
00363 
00364        if (!delta) {
00365          if (!i && !j) {
00366            check(j, delta, i, NULL, ((0x55556666)));
00367            add_symbol(0x55556663, 0x55556669, a, 0); /* Not GCable */
00368          }
00369        }
00370        check(j, delta, 0, a, ((0x55556666)));
00371        check(j, delta, 0, a, ((0x55556663)));
00372        check(j, delta, 0, a, ((0x55556669)));
00373 
00374        if (i == 0) {
00375          alt_gc = NULL;
00376          gcs[0] = NULL;
00377          gcs[1] = NULL;
00378          gcs[2] = NULL;
00379        } else {
00380          if (0)
00381            alt_gc = (void *)0x55556663;
00382          gcs[0] = (void *)(delta + 0x12341200);
00383          gcs[1] = (void *)(delta + 0x12341236);
00384          if (i == 2)
00385            gcs[2] = (void *)(delta + 0x12341235);
00386          else
00387            gcs[2] = NULL;
00388        }
00389 
00390        clear_symbols_for_collected();
00391       }
00392     }
00393   }
00394 }
00395 
00396 #endif