home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / MARK_RTS.C < prev    next >
C/C++ Source or Header  |  1994-09-15  |  9KB  |  308 lines
  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, September 15, 1994 2:15 pm PDT */
  15. # include <stdio.h>
  16. # include "gc_priv.h"
  17.  
  18. # ifdef PCR
  19. #   define MAX_ROOT_SETS 1024
  20. # else
  21. #   ifdef MSWIN32
  22. #    define MAX_ROOT_SETS 512
  23.         /* Under NT, we add only written pages, which can result     */
  24.         /* in many small root sets.                    */
  25. #   else
  26. #       define MAX_ROOT_SETS 64
  27. #   endif
  28. # endif
  29.  
  30. /* Data structure for list of root sets.                */
  31. /* We keep a hash table, so that we can filter out duplicate additions.    */
  32. /* Under Win32, we need to do a better job of filtering overlaps, so    */
  33. /* we resort to sequential search, and pay the price.            */
  34. struct roots {
  35.     ptr_t r_start;
  36.     ptr_t r_end;
  37. #    ifndef MSWIN32
  38.       struct roots * r_next;
  39. #    endif
  40. };
  41.  
  42. static struct roots static_roots[MAX_ROOT_SETS];
  43.  
  44. static int n_root_sets = 0;
  45.  
  46.     /* static_roots[0..n_root_sets) contains the valid root sets. */
  47.  
  48. /* Primarily for debugging support:    */
  49. /* Is the address p in one of the registered static            */
  50. /* root sections?                            */
  51. bool GC_is_static_root(p)
  52. ptr_t p;
  53. {
  54.     static int last_root_set = 0;
  55.     register int i;
  56.     
  57.     
  58.     if (p >= static_roots[last_root_set].r_start
  59.         && p < static_roots[last_root_set].r_end) return(TRUE);
  60.     for (i = 0; i < n_root_sets; i++) {
  61.         if (p >= static_roots[i].r_start
  62.             && p < static_roots[i].r_end) {
  63.             last_root_set = i;
  64.             return(TRUE);
  65.         }
  66.     }
  67.     return(FALSE);
  68. }
  69.  
  70. #ifndef MSWIN32
  71. #   define LOG_RT_SIZE 6
  72. #   define RT_SIZE (1 << LOG_RT_SIZE)  /* Power of 2, may be != MAX_ROOT_SETS */
  73.  
  74.     static struct roots * root_index[RT_SIZE];
  75.     /* Hash table header.  Used only to check whether a range is     */
  76.     /* already present.                        */
  77.  
  78. static int rt_hash(addr)
  79. char * addr;
  80. {
  81.     word result = (word) addr;
  82. #   if CPP_WORDSZ > 8*LOG_RT_SIZE
  83.     result ^= result >> 8*LOG_RT_SIZE;
  84. #   endif
  85. #   if CPP_WORDSZ > 4*LOG_RT_SIZE
  86.     result ^= result >> 4*LOG_RT_SIZE;
  87. #   endif
  88.     result ^= result >> 2*LOG_RT_SIZE;
  89.     result ^= result >> LOG_RT_SIZE;
  90.     result &= (RT_SIZE-1);
  91.     return(result);
  92. }
  93.  
  94. /* Is a range starting at b already in the table? If so return a    */
  95. /* pointer to it, else NIL.                        */
  96. struct roots * GC_roots_present(b)
  97. char *b;
  98. {
  99.     register int h = rt_hash(b);
  100.     register struct roots *p = root_index[h];
  101.     
  102.     while (p != 0) {
  103.         if (p -> r_start == (ptr_t)b) return(p);
  104.         p = p -> r_next;
  105.     }
  106.     return(FALSE);
  107. }
  108.  
  109. /* Add the given root structure to the index. */
  110. static void add_roots_to_index(p)
  111. struct roots *p;
  112. {
  113.     register int h = rt_hash(p -> r_start);
  114.     
  115.     p -> r_next = root_index[h];
  116.     root_index[h] = p;
  117. }
  118.  
  119. # else /* MSWIN32 */
  120.  
  121. #   define add_roots_to_index(p)
  122.  
  123. # endif
  124.  
  125.  
  126.  
  127.  
  128. word GC_root_size = 0;
  129.  
  130. void GC_add_roots(b, e)
  131. char * b; char * e;
  132. {
  133.     DCL_LOCK_STATE;
  134.     
  135.     DISABLE_SIGNALS();
  136.     LOCK();
  137.     GC_add_roots_inner(b, e);
  138.     UNLOCK();
  139.     ENABLE_SIGNALS();
  140. }
  141.  
  142.  
  143. /* Add [b,e) to the root set.  Adding the same interval a second time    */
  144. /* is a moderately fast noop, and hence benign.  We do not handle    */
  145. /* different but overlapping intervals efficiently.  (We do handle    */
  146. /* them correctly.)                            */
  147. void GC_add_roots_inner(b, e)
  148. char * b; char * e;
  149. {
  150.     struct roots * old;
  151.     
  152.     /* We exclude GC data structures from root sets.  It's usually safe    */
  153.     /* to mark from those, but it is a waste of time.            */
  154.     if ( (ptr_t)b < endGC_arrays && (ptr_t)e > beginGC_arrays) {
  155.         if ((ptr_t)e <= endGC_arrays) {
  156.             if ((ptr_t)b >= beginGC_arrays) return;
  157.             e = (char *)beginGC_arrays;
  158.         } else if ((ptr_t)b >= beginGC_arrays) {
  159.             b = (char *)endGC_arrays;
  160.         } else {
  161.             GC_add_roots_inner(b, (char *)beginGC_arrays);
  162.             GC_add_roots_inner((char *)endGC_arrays, e);
  163.             return;
  164.         }
  165.     }
  166. #   ifdef MSWIN32
  167.       /* Spend the time to ensure that there are no overlapping    */
  168.       /* or adjacent intervals.                    */
  169.       /* This could be done faster with e.g. a            */
  170.       /* balanced tree.  But the execution time here is        */
  171.       /* virtually guaranteed to be dominated by the time it    */
  172.       /* takes to scan the roots.                */
  173.       {
  174.         register int i;
  175.         
  176.         for (i = 0; i < n_root_sets; i++) {
  177.             old = static_roots + i;
  178.             if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
  179.                 if ((ptr_t)b < old -> r_start) {
  180.                     old -> r_start = (ptr_t)b;
  181.                 }
  182.                 if ((ptr_t)e > old -> r_end) {
  183.                     old -> r_end = (ptr_t)e;
  184.                 }
  185.                 break;
  186.             }
  187.         }
  188.         if (i < n_root_sets) {
  189.           /* merge other overlapping intervals */
  190.             struct roots *other;
  191.             
  192.             for (i++; i < n_root_sets; i++) {
  193.               other = static_roots + i;
  194.               b = (char *)(other -> r_start);
  195.               e = (char *)(other -> r_end);
  196.               if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) {
  197.                 if ((ptr_t)b < old -> r_start) {
  198.                     old -> r_start = (ptr_t)b;
  199.                 }
  200.                 if ((ptr_t)e > old -> r_end) {
  201.                     old -> r_end = (ptr_t)e;
  202.                 }
  203.                 /* Delete this entry. */
  204.                   other -> r_start = static_roots[n_root_sets-1].r_start;
  205.                   other -> r_end = static_roots[n_root_sets-1].r_end;
  206.                   n_root_sets--;
  207.               }
  208.             }
  209.           return;
  210.         }
  211.       }
  212. #   else
  213.       old = GC_roots_present(b);
  214.       if (old != 0) {
  215.         if ((ptr_t)e <= old -> r_end) /* already there */ return;
  216.         /* else extend */
  217.         GC_root_size += (ptr_t)e - old -> r_end;
  218.         old -> r_end = (ptr_t)e;
  219.         return;
  220.       }
  221. #   endif
  222.     if (n_root_sets == MAX_ROOT_SETS) {
  223.         ABORT("Too many root sets\n");
  224.     }
  225.     static_roots[n_root_sets].r_start = (ptr_t)b;
  226.     static_roots[n_root_sets].r_end = (ptr_t)e;
  227. #   ifndef MSWIN32
  228.       static_roots[n_root_sets].r_next = 0;
  229. #   endif
  230.     add_roots_to_index(static_roots + n_root_sets);
  231.     GC_root_size += (ptr_t)e - (ptr_t)b;
  232.     n_root_sets++;
  233. }
  234.  
  235. void GC_clear_roots(NO_PARAMS)
  236. {
  237.     DCL_LOCK_STATE;
  238.     
  239.     DISABLE_SIGNALS();
  240.     LOCK();
  241.     n_root_sets = 0;
  242.     GC_root_size = 0;
  243. #   ifndef MSWIN32
  244.     {
  245.         register int i;
  246.         
  247.         for (i = 0; i < RT_SIZE; i++) root_index[i] = 0;
  248.     }
  249. #   endif
  250.     UNLOCK();
  251.     ENABLE_SIGNALS();
  252. }
  253.  
  254. ptr_t GC_approx_sp()
  255. {
  256.     word dummy;
  257.     
  258.     return((ptr_t)(&dummy));
  259. }
  260.  
  261. /*
  262.  * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional
  263.  * on groups of pointers) on every top level accessible pointer.
  264.  * If all is FALSE, arrange to push only possibly altered values.
  265.  */
  266.  
  267. void GC_push_roots(all)
  268. bool all;
  269. {
  270.     register int i;
  271.  
  272.     /*
  273.      * push registers - i.e., call GC_push_one(r) for each
  274.      * register contents r.
  275.      */
  276.         GC_push_regs(); /* usually defined in machine_dep.c */
  277.         
  278.     /*
  279.      * Next push static data.  This must happen early on, since it's
  280.      * not robust against mark stack overflow.
  281.      */
  282.      /* Reregister dynamic libraries, in case one got added.    */
  283. #      if (defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(PCR)) \
  284.            && !defined(SRC_M3)
  285.          GC_register_dynamic_libraries();
  286. #      endif
  287.      /* Mark everything in static data areas                             */
  288.        for (i = 0; i < n_root_sets; i++) {
  289.          GC_push_conditional(static_roots[i].r_start,
  290.                  static_roots[i].r_end, all);
  291.        }
  292.  
  293.     /*
  294.      * Now traverse stacks.
  295.      */
  296. #   ifndef THREADS
  297.         /* Mark everything on the stack.           */
  298. #         ifdef STACK_GROWS_DOWN
  299.         GC_push_all_stack( GC_approx_sp(), GC_stackbottom );
  300. #      else
  301.         GC_push_all_stack( GC_stackbottom, GC_approx_sp() );
  302. #      endif
  303. #   endif
  304.     if (GC_push_other_roots != 0) (*GC_push_other_roots)();
  305.         /* In the threads case, this also pushes thread stacks.    */
  306. }
  307.  
  308.