gc.c 6.01 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* gc.c
 *
 * Simple mark&sweep garbage collector.
 *
 * $Id$ */

/* lsh, an implementation of the ssh protocol
 *
 * Copyright (C) 1998 Niels Mller
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
J.H.M. Dassen's avatar
J.H.M. Dassen committed
23
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
Niels Möller's avatar
Niels Möller committed
24
25
26
27
 */

#include "gc.h"

28
#include "io.h"
Niels Möller's avatar
Niels Möller committed
29
#include "resource.h"
Niels Möller's avatar
Niels Möller committed
30
31
32
33
34
35
#include "werror.h"
#include "xalloc.h"

#include <assert.h>

/* Global variables */
36
static struct lsh_object *all_objects = NULL;
Niels Möller's avatar
Niels Möller committed
37
38
static unsigned number_of_objects = 0;
static unsigned live_objects = 0;
Niels Möller's avatar
Niels Möller committed
39
static struct resource_list *root_set = NULL;
40

41
42
static int gc_scheduled = 0;

Niels Möller's avatar
Niels Möller committed
43
#if DEBUG_ALLOC
Niels Möller's avatar
Niels Möller committed
44
45
46
47
48
49
static void sanity_check_object_list(void)
{
  unsigned i = 0;
  struct lsh_object *o;

#if 0
Niels Möller's avatar
Niels Möller committed
50
  wwrite("sanity_check_object_list: Objects on list:\n");
Niels Möller's avatar
Niels Möller committed
51
  for(o = all_objects; o; o = o->next)
52
    werror("  %xi, class: %z\n", (UINT32) o, o->isa ? o->isa->name : "UNKNOWN");
Niels Möller's avatar
Niels Möller committed
53
54
55
56
57
58
#endif
  
  for(o = all_objects; o; o = o->next)
    i++;

  if (i != number_of_objects)
59
    fatal("sanity_check_object_list: Found %i objects, expected %i.\n",
Niels Möller's avatar
Niels Möller committed
60
61
	  i, number_of_objects);
}
Niels Möller's avatar
Niels Möller committed
62
63
#else
#define sanity_check_object_list()
Niels Möller's avatar
Niels Möller committed
64
65
#endif

66
/* FIXME: This function recurses heavily. One could use some trickery
Niels Möller's avatar
Niels Möller committed
67
68
69
70
 * to emulate tail recursion, which would help marking linked lists.
 * Or one could use some more efficient datastructures than the C
 * stack for keeping track of the marked but not yet traced objects.
 * Or use something more sophisticated, like pointer reversal. */
Niels Möller's avatar
Niels Möller committed
71
72
static void gc_mark(struct lsh_object *o)
{
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
  if (!o)
    return;
  
  switch(o->alloc_method)
    {
    case LSH_ALLOC_STACK:
      fatal("gc_mark: Unexpected stack object!\n");

    case LSH_ALLOC_HEAP:
      if (o->marked)
	return;
      o->marked = 1;
      /* Fall through */
    case LSH_ALLOC_STATIC:
      /* Can't use mark bit on static objects, as there's no way to
       * reset all the bits */
      assert(!o->dead);
Niels Möller's avatar
Niels Möller committed
90
      {
91
	struct lsh_class *class;
Niels Möller's avatar
Niels Möller committed
92

Niels Möller's avatar
Niels Möller committed
93
#if 0
94
	debug("gc_mark: Marking object of class '%z'\n",
Niels Möller's avatar
Niels Möller committed
95
	      o->isa ? o->isa->name : "UNKNOWN");
Niels Möller's avatar
Niels Möller committed
96
#endif
Niels Möller's avatar
Niels Möller committed
97
	
Niels Möller's avatar
Niels Möller committed
98
	for (class = o->isa; class; class = class->super_class)
99
100
101
102
	  {
	    if (class->mark_instance)
	      MARK_INSTANCE(class, o, gc_mark);
	  }
Niels Möller's avatar
Niels Möller committed
103
      }
104
105
106
107
      break;
    default:
      fatal("gc_mark: Memory corrupted!\n");
    }
Niels Möller's avatar
Niels Möller committed
108
109
110
111
112
113
114
115
116
117
118
119
120
}

static void gc_sweep(void)
{
  struct lsh_object *o;
  struct lsh_object **o_p;

  live_objects = 0;
  
  for(o_p = &all_objects; (o = *o_p); )
    {
      if (o->marked)
	{
Niels Möller's avatar
Niels Möller committed
121
	  /* Paralyze the living... */
Niels Möller's avatar
Niels Möller committed
122
123
124
125
126
	  live_objects++;
	  o->marked = 0;
	}
      else
	{
Niels Möller's avatar
Niels Möller committed
127
	  /* ... and resurrect the dead. */
Niels Möller's avatar
Niels Möller committed
128
	  struct lsh_class *class;
Niels Möller's avatar
Niels Möller committed
129

Niels Möller's avatar
Niels Möller committed
130
#if 0
131
	  debug("gc_sweep: Freeing object of class '%z'\n",
Niels Möller's avatar
Niels Möller committed
132
		o->isa->name);
Niels Möller's avatar
Niels Möller committed
133
#endif  
Niels Möller's avatar
Niels Möller committed
134
135
136
137
138
139
140
141
142
143
144
145
	  for (class = o->isa; class; class = class->super_class)
	    if (class->free_instance)
	      FREE_INSTANCE(class, o);

	  *o_p = o->next;
	  number_of_objects--;
	  
	  lsh_object_free(o);
	  continue;
	}
      o_p = &o->next;
    }
Niels Möller's avatar
Niels Möller committed
146
  assert(live_objects == number_of_objects);
Niels Möller's avatar
Niels Möller committed
147
148
}

149
150
151
152
153
154
155
156
157
158
159
160
161
162
static void
do_gc(struct lsh_callback *s UNUSED)
{
  assert(gc_scheduled);
  gc_scheduled = 0;

  gc();
}

struct lsh_callback
gc_callback = { STATIC_HEADER, do_gc };

void
gc_register(struct lsh_object *o)
Niels Möller's avatar
Niels Möller committed
163
{
Niels Möller's avatar
Niels Möller committed
164
  sanity_check_object_list();
Niels Möller's avatar
Niels Möller committed
165

Niels Möller's avatar
Niels Möller committed
166
167
168
169
  o->marked = o->dead = 0;
  o->next = all_objects;
  all_objects = o;

170
  number_of_objects++;
Niels Möller's avatar
Niels Möller committed
171

172
173
174
175
176
177
  if (!gc_scheduled && (number_of_objects > 100 + 2 * live_objects))
    {
      gc_scheduled = 1;
      io_callout(&gc_callback);
    }
  
Niels Möller's avatar
Niels Möller committed
178
179
  sanity_check_object_list();
}
180

181
/* NOTE: If the object is close to the start of the object list, it is
Niels Möller's avatar
Niels Möller committed
182
 * deallocated and forgotten immediately. If the object is not found,
183
 * we don't search the entire list, but instead defer deallocation to
184
 * gc_sweep. */
Niels Möller's avatar
Niels Möller committed
185
186
void gc_kill(struct lsh_object *o)
{
Niels Möller's avatar
Niels Möller committed
187
188
  sanity_check_object_list();

189
190
  if (!o)
    return;
191

Niels Möller's avatar
Niels Möller committed
192
193
194
  assert(!o->dead);

  o->dead = 1;
Niels Möller's avatar
Niels Möller committed
195

196
#if 0
197
198
  debug("gc_kill: Killing object of type %z.\n",
	o->isa ? o->isa->name : "UNKNOWN");
199
#endif
200
201
202
203
204
  
  if (o == all_objects)
    {
      struct lsh_class *class;
      
205
#if 0
206
      debug("gc_kill:   Deallocating immediately.\n");
207
208
#endif
      
209
210
211
212
213
214
215
216
217
      for (class = o->isa; class; class = class->super_class)
	if (class->free_instance)
	  FREE_INSTANCE(class, o);

      all_objects = o->next;
      number_of_objects--;
      lsh_object_free(o);
    }
  else
218
219
    {
#if 0
220
      debug("gc_kill:   Deferring deallocation to gc_sweep\n");
221
222
223
#endif
    }
  
Niels Möller's avatar
Niels Möller committed
224
  sanity_check_object_list();
Niels Möller's avatar
Niels Möller committed
225
226
}

Niels Möller's avatar
Niels Möller committed
227
228
229
230
void
gc_global(struct resource *o)
{
  if (!root_set)
Niels Möller's avatar
Niels Möller committed
231
    root_set = make_resource_list();
Niels Möller's avatar
Niels Möller committed
232
233
234
235
236
237
238
  
  assert(root_set->super.alive);

  REMEMBER_RESOURCE(root_set, o);
}

void gc(void)
Niels Möller's avatar
Niels Möller committed
239
{
240
  unsigned objects_before = number_of_objects;
241
#if DEBUG_ALLOC
242
  unsigned strings_before = number_of_strings;
243
244
#endif

245
246
  verbose("garbage collecting...\n");
  
Niels Möller's avatar
Niels Möller committed
247
  gc_mark(&root_set->super.super);  
Niels Möller's avatar
Niels Möller committed
248
  gc_sweep();
249
  
250
251
  verbose("Objects alive: %i, garbage collected: %i\n",
	  live_objects, objects_before - live_objects);
252
#if DEBUG_ALLOC
253
254
  verbose("Used strings:  %i, garbage collected: %i\n",
	  number_of_strings, strings_before - number_of_strings);
255
#endif
Niels Möller's avatar
Niels Möller committed
256
257
}

258
259

/* Deallocate all objects. */
260

261
262
void gc_final(void)
{
263
264
265
266
267
  if (root_set)
    {
      KILL_RESOURCE_LIST(root_set);
      root_set = NULL;
    }
268
269

#if DEBUG_ALLOC
Niels Möller's avatar
Niels Möller committed
270

271
  gc_sweep();
272
  assert(!number_of_objects);
273

274
  if (number_of_strings)
275
276
277
278
279
280
281
    {
      struct lsh_string *s;
      werror("gc_final: %i strings leaked!\n", number_of_strings);
      for (s = all_strings; s; s = s->header.next)
	werror("  clue: %z\n", s->header.clue);
      fatal("gc_final: Internal error!\n");
    }
282
#endif /* DEBUG_ALLOC */
283
}