Back to index

lightning-sunbird  0.9+nobinonly
headers.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  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
00005  *
00006  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
00007  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
00008  *
00009  * Permission is hereby granted to use or copy this program
00010  * for any purpose,  provided the above notices are retained on all copies.
00011  * Permission to modify the code and to distribute modified code is granted,
00012  * provided the above notices are retained, and a notice that the code was
00013  * modified is included with the above copyright notice.
00014  */
00015  
00016 /*
00017  * This implements:
00018  * 1. allocation of heap block headers
00019  * 2. A map from addresses to heap block addresses to heap block headers
00020  *
00021  * Access speed is crucial.  We implement an index structure based on a 2
00022  * level tree.
00023  */
00024  
00025 # include "gc_priv.h"
00026 
00027 bottom_index * GC_all_bottom_indices = 0;
00028  
00029 /* Non-macro version of header location routine */
00030 hdr * GC_find_header(h)
00031 ptr_t h;
00032 {
00033 #   ifdef HASH_TL
00034        register hdr * result;
00035        GET_HDR(h, result);
00036        return(result);
00037 #   else
00038        return(HDR_INNER(h));
00039 #   endif
00040 }
00041  
00042 /* Routines to dynamically allocate collector data structures that will */
00043 /* never be freed.                                              */
00044  
00045 static ptr_t scratch_free_ptr = 0;
00046  
00047 ptr_t GC_scratch_end_ptr = 0;
00048 
00049 ptr_t GC_scratch_last_end_ptr = 0;
00050               /* End point of last obtained scratch area */
00051  
00052 ptr_t GC_scratch_alloc(bytes)
00053 register word bytes;
00054 {
00055     register ptr_t result = scratch_free_ptr;
00056 
00057 #   ifdef ALIGN_DOUBLE
00058 #      define GRANULARITY (2 * sizeof(word))
00059 #   else
00060 #      define GRANULARITY sizeof(word)
00061 #   endif
00062     bytes += GRANULARITY-1;
00063     bytes &= ~(GRANULARITY-1);
00064     scratch_free_ptr += bytes;
00065     if (scratch_free_ptr <= GC_scratch_end_ptr) {
00066         return(result);
00067     }
00068     {
00069         word bytes_to_get = MINHINCR * HBLKSIZE;
00070          
00071         if (bytes_to_get <= bytes) {
00072           /* Undo the damage, and get memory directly */
00073            bytes_to_get = bytes;
00074 #          ifdef USE_MMAP
00075               bytes_to_get += GC_page_size - 1;
00076               bytes_to_get &= ~(GC_page_size - 1);
00077 #          endif
00078            result = (ptr_t)GET_MEM(bytes_to_get);
00079             scratch_free_ptr -= bytes;
00080            GC_scratch_last_end_ptr = result + bytes;
00081             return(result);
00082         }
00083         result = (ptr_t)GET_MEM(bytes_to_get);
00084         if (result == 0) {
00085 #          ifdef PRINTSTATS
00086                 GC_printf0("Out of memory - trying to allocate less\n");
00087 #          endif
00088             scratch_free_ptr -= bytes;
00089            bytes_to_get = bytes;
00090 #          ifdef USE_MMAP
00091               bytes_to_get += GC_page_size - 1;
00092               bytes_to_get &= ~(GC_page_size - 1);
00093 #          endif
00094             return((ptr_t)GET_MEM(bytes_to_get));
00095         }
00096         scratch_free_ptr = result;
00097         GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get;
00098         GC_scratch_last_end_ptr = GC_scratch_end_ptr;
00099         return(GC_scratch_alloc(bytes));
00100     }
00101 }
00102 
00103 static hdr * hdr_free_list = 0;
00104 
00105 /* Return an uninitialized header */
00106 static hdr * alloc_hdr()
00107 {
00108     register hdr * result;
00109     
00110     if (hdr_free_list == 0) {
00111         result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr)));
00112     } else {
00113         result = hdr_free_list;
00114         hdr_free_list = (hdr *) (result -> hb_next);
00115     }
00116     return(result);
00117 }
00118 
00119 static void free_hdr(hhdr)
00120 hdr * hhdr;
00121 {
00122     hhdr -> hb_next = (struct hblk *) hdr_free_list;
00123     hdr_free_list = hhdr;
00124 }
00125  
00126 void GC_init_headers()
00127 {
00128     register unsigned i;
00129     
00130     GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index));
00131     BZERO(GC_all_nils, sizeof(bottom_index));
00132     for (i = 0; i < TOP_SZ; i++) {
00133         GC_top_index[i] = GC_all_nils;
00134     }
00135 }
00136 
00137 /* Make sure that there is a bottom level index block for address addr  */
00138 /* Return FALSE on failure.                                    */
00139 static GC_bool get_index(addr)
00140 register word addr;
00141 {
00142     register word hi =
00143               (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
00144     register bottom_index * r;
00145     register bottom_index * p;
00146     register bottom_index ** prev;
00147 #   ifdef HASH_TL
00148       register unsigned i = TL_HASH(hi);
00149       register bottom_index * old;
00150       
00151       old = p = GC_top_index[i];
00152       while(p != GC_all_nils) {
00153           if (p -> key == hi) return(TRUE);
00154           p = p -> hash_link;
00155       }
00156       r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
00157       if (r == 0) return(FALSE);
00158       BZERO(r, sizeof (bottom_index));
00159       r -> hash_link = old;
00160       GC_top_index[i] = r;
00161 #   else
00162       if (GC_top_index[hi] != GC_all_nils) return(TRUE);
00163       r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
00164       if (r == 0) return(FALSE);
00165       GC_top_index[hi] = r;
00166       BZERO(r, sizeof (bottom_index));
00167 # endif
00168     r -> key = hi;
00169     /* Add it to the list of bottom indices */
00170       prev = &GC_all_bottom_indices;
00171       while ((p = *prev) != 0 && p -> key < hi) prev = &(p -> asc_link);
00172       r -> asc_link = p;
00173       *prev = r;
00174     return(TRUE);
00175 }
00176 
00177 /* Install a header for block h.  */
00178 /* The header is uninitialized.      */
00179 /* Returns FALSE on failure.         */
00180 GC_bool GC_install_header(h)
00181 register struct hblk * h;
00182 {
00183     hdr * result;
00184     
00185     if (!get_index((word) h)) return(FALSE);
00186     result = alloc_hdr();
00187     SET_HDR(h, result);
00188     return(result != 0);
00189 }
00190 
00191 /* Set up forwarding counts for block h of size sz */
00192 GC_bool GC_install_counts(h, sz)
00193 register struct hblk * h;
00194 register word sz; /* bytes */
00195 {
00196     register struct hblk * hbp;
00197     register int i;
00198     
00199     for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) {
00200         if (!get_index((word) hbp)) return(FALSE);
00201     }
00202     if (!get_index((word)h + sz - 1)) return(FALSE);
00203     for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) {
00204         i = HBLK_PTR_DIFF(hbp, h);
00205         SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i));
00206     }
00207     return(TRUE);
00208 }
00209 
00210 /* Remove the header for block h */
00211 void GC_remove_header(h)
00212 register struct hblk * h;
00213 {
00214     hdr ** ha;
00215     
00216     GET_HDR_ADDR(h, ha);
00217     free_hdr(*ha);
00218     *ha = 0;
00219 }
00220 
00221 /* Remove forwarding counts for h */
00222 void GC_remove_counts(h, sz)
00223 register struct hblk * h;
00224 register word sz; /* bytes */
00225 {
00226     register struct hblk * hbp;
00227     
00228     for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) {
00229         SET_HDR(hbp, 0);
00230     }
00231 }
00232 
00233 /* Apply fn to all allocated blocks */
00234 /*VARARGS1*/
00235 void GC_apply_to_all_blocks(fn, client_data)
00236 void (*fn)(/* struct hblk *h, word client_data */);
00237 word client_data;
00238 {
00239     register int j;
00240     register bottom_index * index_p;
00241     
00242     for (index_p = GC_all_bottom_indices; index_p != 0;
00243          index_p = index_p -> asc_link) {
00244         for (j = BOTTOM_SZ-1; j >= 0;) {
00245             if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) {
00246                 if (index_p->index[j]->hb_map != GC_invalid_map) {
00247                     (*fn)(((struct hblk *)
00248                            (((index_p->key << LOG_BOTTOM_SZ) + (word)j)
00249                             << LOG_HBLKSIZE)),
00250                           client_data);
00251                 }
00252                 j--;
00253              } else if (index_p->index[j] == 0) {
00254                 j--;
00255              } else {
00256                 j -= (word)(index_p->index[j]);
00257              }
00258          }
00259      }
00260 }
00261 
00262 /* Get the next valid block whose address is at least h */
00263 /* Return 0 if there is none.                           */
00264 struct hblk * GC_next_block(h)
00265 struct hblk * h;
00266 {
00267     register bottom_index * bi;
00268     register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
00269     
00270     GET_BI(h, bi);
00271     if (bi == GC_all_nils) {
00272         register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
00273         bi = GC_all_bottom_indices;
00274         while (bi != 0 && bi -> key < hi) bi = bi -> asc_link;
00275         j = 0;
00276     }
00277     while(bi != 0) {
00278         while (j < BOTTOM_SZ) {
00279             if (IS_FORWARDING_ADDR_OR_NIL(bi -> index[j])) {
00280                 j++;
00281             } else {
00282                 if (bi->index[j]->hb_map != GC_invalid_map) {
00283                     return((struct hblk *)
00284                            (((bi -> key << LOG_BOTTOM_SZ) + j)
00285                             << LOG_HBLKSIZE));
00286                 } else {
00287                     j += divHBLKSZ(bi->index[j] -> hb_sz);
00288                 }
00289             }
00290         }
00291         j = 0;
00292         bi = bi -> asc_link;
00293     }
00294     return(0);
00295 }