libguile/gc-segment-table.c

   1 /* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2006, 2008 Free Software Foundation, Inc.
   2  *
   3  * This library is free software; you can redistribute it and/or
   4  * modify it under the terms of the GNU Lesser General Public
   5  * License as published by the Free Software Foundation; either
   6  * version 2.1 of the License, or (at your option) any later version.
   7  *
   8  * This library is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public
  14  * License along with this library; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  16  */
  17
  18 #ifdef HAVE_CONFIG_H
  19 # include <config.h>
  20 #endif
  21
  22 #include <assert.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25
  26 #include "libguile/_scm.h"
  27 #include "libguile/pairs.h"
  28 #include "libguile/gc.h"
  29 #include "libguile/private-gc.h"
  30
  31
  32 /*
  33   Heap segment table.
  34
  35   The table is sorted by the address of the data itself. This makes
  36   for easy lookups. This is not portable: according to ANSI C,
  37   pointers can only be compared within the same object (i.e. the same
  38   block of malloced memory.). For machines with weird architectures,
  39   this should be revised.
  40
  41   (Apparently, for this reason 1.6 and earlier had macros for pointer
  42   comparison. )
  43
  44   perhaps it is worthwhile to remove the 2nd level of indirection in
  45   the table, but this certainly makes for cleaner code.
  46 */
  47 scm_t_heap_segment **scm_i_heap_segment_table;
  48 size_t scm_i_heap_segment_table_size;
  49 static scm_t_cell *lowest_cell;
  50 static scm_t_cell *highest_cell;
  51
  52
  53 /*
  54   RETURN: index of inserted segment.
  55  */
  56 int
  57 scm_i_insert_segment (scm_t_heap_segment *seg)
  58 {
  59   size_t size = (scm_i_heap_segment_table_size + 1) * sizeof (scm_t_heap_segment *);
  60   SCM_SYSCALL (scm_i_heap_segment_table
  61               = ((scm_t_heap_segment **)
  62                  realloc ((char *)scm_i_heap_segment_table, size)));
  63
  64   /*
  65     We can't alloc 4 more bytes. This is hopeless.
  66    */
  67   if (!scm_i_heap_segment_table)
  68     {
  69       fprintf (stderr, "scm_i_get_new_heap_segment: Could not grow heap segment table.\n");
  70       abort ();
  71     }
  72
  73   if (!lowest_cell)
  74     {
  75       lowest_cell = seg->bounds[0];
  76       highest_cell = seg->bounds[1];
  77     }
  78   else
  79     {
  80       lowest_cell = SCM_MIN (lowest_cell, seg->bounds[0]);
  81       highest_cell = SCM_MAX (highest_cell, seg->bounds[1]);
  82     }
  83
  84
  85   {
  86     int i = 0;
  87     int j = 0;
  88
  89     while (i < scm_i_heap_segment_table_size
  90            && scm_i_heap_segment_table[i]->bounds[0] <= seg->bounds[0])
  91       i++;
  92
  93     /*
  94       We insert a new entry; if that happens to be before the
  95       "current" segment of a freelist, we must move the freelist index
  96       as well.
  97     */
  98     if (scm_i_master_freelist.heap_segment_idx >= i)
  99       scm_i_master_freelist.heap_segment_idx ++;
 100     if (scm_i_master_freelist2.heap_segment_idx >= i)
 101       scm_i_master_freelist2.heap_segment_idx ++;
 102
 103     for (j = scm_i_heap_segment_table_size; j > i; --j)
 104       scm_i_heap_segment_table[j] = scm_i_heap_segment_table[j - 1];
 105
 106     scm_i_heap_segment_table[i] = seg;
 107     scm_i_heap_segment_table_size ++;
 108
 109     return i;
 110   }
 111 }
 112
 113
 114 /*
 115   Determine whether the given value does actually represent a cell in
 116   some heap segment.  If this is the case, the number of the heap
 117   segment is returned.  Otherwise, -1 is returned.  Binary search is
 118   used to determine the heap segment that contains the cell.
 119
 120   I think this function is too long to be inlined. --hwn
 121 */
 122
 123 int
 124 scm_i_find_heap_segment_containing_object (SCM obj)
 125 {
 126   if (!CELL_P (obj))
 127     return -1;
 128
 129   scm_i_find_heap_calls ++;
 130   if ((scm_t_cell *) obj < lowest_cell || (scm_t_cell *) obj >= highest_cell)
 131     return -1;
 132
 133   {
 134     scm_t_cell *ptr = SCM2PTR (obj);
 135     unsigned int i = 0;
 136     unsigned int j = scm_i_heap_segment_table_size - 1;
 137
 138     if (ptr < scm_i_heap_segment_table[i]->bounds[0])
 139       return -1;
 140     else if (scm_i_heap_segment_table[j]->bounds[1] <= ptr)
 141       return -1;
 142     else
 143       {
 144         while (i < j)
 145           {
 146             if (ptr < scm_i_heap_segment_table[i]->bounds[1])
 147               {
 148                 break;
 149               }
 150             else if (scm_i_heap_segment_table[j]->bounds[0] <= ptr)
 151               {
 152                 i = j;
 153                 break;
 154               }
 155             else
 156               {
 157                 unsigned long int k = (i + j) / 2;
 158
 159                 if (k == i)
 160                   return -1;
 161                 else if (ptr <  scm_i_heap_segment_table[k]->bounds[1])
 162                   {
 163                     j = k;
 164                     ++i;
 165                     if (ptr <  scm_i_heap_segment_table[i]->bounds[0])
 166                       return -1;
 167                   }
 168                 else if (scm_i_heap_segment_table[k]->bounds[0] <= ptr)
 169                   {
 170                     i = k;
 171                     --j;
 172                     if (scm_i_heap_segment_table[j]->bounds[1] <= ptr)
 173                       return -1;
 174                   }
 175               }
 176           }
 177
 178         if (!SCM_DOUBLECELL_ALIGNED_P (obj) && scm_i_heap_segment_table[i]->span == 2)
 179           return -1;
 180         else if (SCM_GC_IN_CARD_HEADERP (ptr))
 181           return -1;
 182         else
 183           return i;
 184       }
 185   }
 186 }
 187
 188
 189 int
 190 scm_i_marked_count (void)
 191 {
 192   int i = 0;
 193   int c = 0;
 194   for (; i < scm_i_heap_segment_table_size; i++)
 195     {
 196       c += scm_i_heap_segment_marked_count (scm_i_heap_segment_table[i]);
 197     }
 198   return c;
 199 }
 200
 201
 202 SCM
 203 scm_i_sweep_some_segments (scm_t_cell_type_statistics *freelist,
 204                            scm_t_sweep_statistics *sweep_stats)
 205 {
 206   int i = freelist->heap_segment_idx;
 207   SCM collected = SCM_EOL;
 208
 209   if (i == -1)                  /* huh? --hwn */
 210     i++;
 211
 212   for (;
 213        i < scm_i_heap_segment_table_size; i++)
 214     {
 215       if (scm_i_heap_segment_table[i]->freelist != freelist)
 216         continue;
 217
 218       collected = scm_i_sweep_some_cards (scm_i_heap_segment_table[i],
 219                                           sweep_stats,
 220                                           DEFAULT_SWEEP_AMOUNT);
 221
 222       if (collected != SCM_EOL)       /* Don't increment i */
 223         break;
 224     }
 225
 226   freelist->heap_segment_idx = i;
 227
 228   return collected;
 229 }
 230
 231 void
 232 scm_i_reset_segments (void)
 233 {
 234   int i = 0;
 235   for (; i < scm_i_heap_segment_table_size; i++)
 236     {
 237       scm_t_heap_segment *seg = scm_i_heap_segment_table[i];
 238       seg->next_free_card = seg->bounds[0];
 239     }
 240 }
 241
 242
 243
 244
 245 /*
 246   Return a hashtab with counts of live objects, with tags as keys.
 247  */
 248 SCM
 249 scm_i_all_segments_statistics (SCM tab)
 250 {
 251   int i = 0;
 252   for (; i < scm_i_heap_segment_table_size; i++)
 253     {
 254       scm_t_heap_segment *seg = scm_i_heap_segment_table[i];
 255       scm_i_heap_segment_statistics (seg, tab);
 256     }
 257
 258   return tab;
 259 }
 260
 261
 262 unsigned long*
 263 scm_i_segment_table_info (int* size)
 264 {
 265   *size = scm_i_heap_segment_table_size;
 266   unsigned long *bounds = malloc (sizeof (unsigned long) * *size * 2);
 267   int i;
 268   if (!bounds)
 269     abort ();
 270   for (i = *size; i-- > 0; )
 271     {
 272       bounds[2*i] = (unsigned long)scm_i_heap_segment_table[i]->bounds[0];
 273       bounds[2*i+1] = (unsigned long)scm_i_heap_segment_table[i]->bounds[1];
 274     }
 275   return bounds;
 276 }
 277
 278
 279 void
 280 scm_i_sweep_all_segments (char const *reason,
 281                           scm_t_sweep_statistics *sweep_stats)
 282 {
 283   unsigned i= 0;
 284   for (i = 0; i < scm_i_heap_segment_table_size; i++)
 285     {
 286       scm_i_sweep_segment (scm_i_heap_segment_table[i], sweep_stats);
 287     }
 288 }
 289
 290
 291 void
 292 scm_i_clear_mark_space (void)
 293 {
 294   int i = 0;
 295   for (; i < scm_i_heap_segment_table_size; i++)
 296     {
 297       scm_i_clear_segment_mark_space (scm_i_heap_segment_table[i]);
 298     }
 299 }