home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / BLACKLST.C < prev    next >
C/C++ Source or Header  |  1994-05-19  |  6KB  |  182 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, May 19, 1994 1:56 pm PDT */
  15. # include "gc_priv.h"
  16.  
  17. /*
  18.  * We maintain several hash tables of hblks that have had false hits.
  19.  * Each contains one bit per hash bucket;  If any page in the bucket
  20.  * has had a false hit, we assume that all of them have.
  21.  * See the definition of page_hash_table in gc_private.h.
  22.  * False hits from the stack(s) are much more dangerous than false hits
  23.  * from elsewhere, since the former can pin a large object that spans the
  24.  * block, eventhough it does not start on the dangerous block.
  25.  */
  26.  
  27. /*
  28.  * Externally callable routines are:
  29.  
  30.  * GC_add_to_black_list_normal
  31.  * GC_add_to_black_list_stack
  32.  * GC_promote_black_lists
  33.  * GC_is_black_listed
  34.  *
  35.  * All require that the allocator lock is held.
  36.  */
  37.  
  38. /* Pointers to individual tables.  We replace one table by another by     */
  39. /* switching these pointers.                         */
  40. word * GC_old_normal_bl;
  41.         /* Nonstack false references seen at last full        */
  42.         /* collection.                        */
  43. word * GC_incomplete_normal_bl;
  44.         /* Nonstack false references seen since last        */
  45.         /* full collection.                    */
  46. word * GC_old_stack_bl;
  47. word * GC_incomplete_stack_bl;
  48.  
  49. void GC_clear_bl();
  50.  
  51. void GC_bl_init()
  52. {
  53. # ifndef ALL_INTERIOR_POINTERS
  54.     GC_old_normal_bl = (word *)
  55.                  GC_scratch_alloc((word)(sizeof (page_hash_table)));
  56.     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  57.                         ((word)(sizeof(page_hash_table)));
  58.     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  59.         GC_err_printf0("Insufficient memory for black list\n");
  60.         EXIT();
  61.     }
  62.     GC_clear_bl(GC_old_normal_bl);
  63.     GC_clear_bl(GC_incomplete_normal_bl);
  64. # endif
  65.     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
  66.     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  67.                         ((word)(sizeof(page_hash_table)));
  68.     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
  69.         GC_err_printf0("Insufficient memory for black list\n");
  70.         EXIT();
  71.     }
  72.     GC_clear_bl(GC_old_stack_bl);
  73.     GC_clear_bl(GC_incomplete_stack_bl);
  74. }
  75.         
  76. void GC_clear_bl(doomed)
  77. word *doomed;
  78. {
  79.     BZERO(doomed, sizeof(page_hash_table));
  80. }
  81.  
  82. /* Signal the completion of a collection.  Turn the incomplete black    */
  83. /* lists into new black lists, etc.                    */             
  84. void GC_promote_black_lists()
  85. {
  86.     word * very_old_normal_bl = GC_old_normal_bl;
  87.     word * very_old_stack_bl = GC_old_stack_bl;
  88.     
  89.     GC_old_normal_bl = GC_incomplete_normal_bl;
  90.     GC_old_stack_bl = GC_incomplete_stack_bl;
  91. #   ifndef ALL_INTERIOR_POINTERS
  92.       GC_clear_bl(very_old_normal_bl);
  93. #   endif
  94.     GC_clear_bl(very_old_stack_bl);
  95.     GC_incomplete_normal_bl = very_old_normal_bl;
  96.     GC_incomplete_stack_bl = very_old_stack_bl;
  97. }
  98.  
  99. # ifndef ALL_INTERIOR_POINTERS
  100. /* P is not a valid pointer reference, but it falls inside    */
  101. /* the plausible heap bounds.                    */
  102. /* Add it to the normal incomplete black list if appropriate.    */
  103. void GC_add_to_black_list_normal(p)
  104. word p;
  105. {
  106.     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
  107.     {
  108.         register int index = PHT_HASH(p);
  109.         
  110.         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
  111. #           ifdef PRINTBLACKLIST
  112.         if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
  113.               GC_printf1("Black listing (normal) 0x%lx\n",
  114.                        (unsigned long) p);
  115.             }
  116. #           endif
  117.             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
  118.         } /* else this is probably just an interior pointer to an allocated */
  119.           /* object, and isn't worth black listing.                */
  120.     }
  121. }
  122. # endif
  123.  
  124. /* And the same for false pointers from the stack. */
  125. void GC_add_to_black_list_stack(p)
  126. word p;
  127. {
  128.     register int index = PHT_HASH(p);
  129.         
  130.     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
  131. #       ifdef PRINTBLACKLIST
  132.         if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
  133.               GC_printf1("Black listing (stack) 0x%lx\n",
  134.                          (unsigned long)p);
  135.         }
  136. #       endif
  137.     set_pht_entry_from_index(GC_incomplete_stack_bl, index);
  138.     }
  139. }
  140.  
  141. /*
  142.  * Is the block starting at h of size len bytes black listed?   If so,
  143.  * return the address of the next plausible r such that (r, len) might not
  144.  * be black listed.  (R may not actually be in the heap.  We guarantee only
  145.  * that every smaller value of r after h is also black listed.)
  146.  * If (h,len) is not black listed, return 0.
  147.  * Knows about the structure of the black list hash tables.
  148.  */
  149. struct hblk * GC_is_black_listed(h, len)
  150. struct hblk * h;
  151. word len;
  152. {
  153.     register int index = PHT_HASH((word)h);
  154.     register word i;
  155.     word nblocks = divHBLKSZ(len);
  156.  
  157. #   ifndef ALL_INTERIOR_POINTERS
  158.       if (get_pht_entry_from_index(GC_old_normal_bl, index)
  159.           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
  160.         return(h+1);
  161.       }
  162. #   endif
  163.     
  164.     for (i = 0; ; ) {
  165.         if (GC_old_stack_bl[divWORDSZ(index)] == 0
  166.             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
  167.             /* An easy case */
  168.             i += WORDSZ - modWORDSZ(index);
  169.         } else {
  170.           if (get_pht_entry_from_index(GC_old_stack_bl, index)
  171.               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
  172.             return(h+i+1);
  173.           }
  174.           i++;
  175.         }
  176.         if (i >= nblocks) break;
  177.         index = PHT_HASH((word)(h+i));
  178.     }
  179.     return(0);
  180. }
  181.  
  182.