c498dbc6b6a09aece360fc954287668fc05f16d0
[acogc] / lib / acogc.h
1 /*
2   acogc.h - simple accurate/cooperative garbage collector
3
4   Copyright (C) 2006, Christian Thaeter <chth@gmx.net>
5
6   This program is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License version 2 as
8   published by the Free Software Foundation.
9
10   This program is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with this program; if not, contact me.
17
18 */
19 \f
20 #ifndef ACOGC_H
21 #define ACOGC_H
22
23 /*
24 accurate
25   only real references are used for marking objects instead scanning all objects
26
27 cooperative
28   the programmer has to supply functions which mark references in his datastructures
29 */
30
31 #include <stdlib.h>
32 #include <stdint.h>
33 #include <limits.h>
34 #include <nobug.h>
35
36 #include "llist.h"
37
38 NOBUG_DECLARE_FLAG(acogc);
39 NOBUG_DECLARE_FLAG(acogc_mark);
40 NOBUG_DECLARE_FLAG(acogc_collect);
41 NOBUG_DECLARE_FLAG(acogc_alloc);
42 NOBUG_DECLARE_FLAG(acogc_weak);
43
44
45 /*
46   object types and handles
47 */
48 #define ACOGC_DECLARE(name,Handle) \
49   struct acogc_##name##_struct; \
50   typedef struct acogc_##name##_struct acogc_##name;\
51   typedef const acogc_##name * const_Acogc##Handle;\
52   typedef acogc_##name * Acogc##Handle;\
53   typedef acogc_##name ** Acogc##Handle##_ref;\
54   typedef const acogc_##name ** const_Acogc##Handle##_ref
55
56 ACOGC_DECLARE(root,Root);
57 ACOGC_DECLARE(stack,Stack);
58 ACOGC_DECLARE(factory,Factory);
59 ACOGC_DECLARE(object,Object);
60 ACOGC_DECLARE(weakref,Weakref);
61
62 /*
63   Macros
64  */
65
66 /*
67   uncollectable objects (static or stack) have to be defined with this macro
68 */
69 #define ACOGC_OBJECT(state, factory, type, name, ...)           \
70       struct { acogc_object acogc_header; type object;}         \
71       name ## _acogc = {ACOGC_OBJECT_INITIALIZER( state,        \
72                         factory, name),                         \
73                         __VA_ARGS__};                           \
74       type* name=&name ## _acogc.object
75
76 #define ACOGC_OBJECT_INITIALIZER(state, factory, name)          \
77       {LLIST_INITIALIZER (name ## _acogc.acogc_header.node ),   \
78        factory, NULL, ACOGC_STATE_ ## state}
79
80 /*
81   tracking pointers on the stack with the GC
82 */
83 struct acogc_stack_struct
84 {
85   void* ptr;
86   AcogcStack prev;
87 };
88
89 #define ACOGC_STACK_ENTER(gcroot)                                                               \
90 AcogcStack_ref acogc_stack_root = &(gcroot)->stack;                                             \
91 AcogcStack acogc_stack_entry NOBUG_CLEANUP (acogc_assert_stackframeleft) = *acogc_stack_root
92
93 #define ACOGC_STACK_PTR(ptrtype, name)          \
94 union {                                         \
95   acogc_stack stack;                            \
96   ptrtype ptr;                                  \
97 }name; name.ptr = NULL;                         \
98 name.stack.prev = *acogc_stack_root;            \
99 *acogc_stack_root = &name.stack
100
101 // TODO #define ACOGC_STACK_FORGET
102
103 #define ACOGC_STACK_LEAVE                               \
104 *acogc_stack_root = acogc_stack_entry;                  \
105 acogc_stack_entry = (AcogcStack)&acogc_stack_entry
106
107 void
108 acogc_assert_stackframeleft (AcogcStack_ref p);
109
110 /* declare a weak reference als automatic variable, asserts that the reference gets unlinked when the stackframe is left */
111 #define ACOGC_WEAK_REFERENCE(name) acogc_weakref name NOBUG_CLEANUP(acogc_weakref_assert_cleared) = ACOGC_WEAKREF_INITIALIZER
112 #define ACOGC_WEAKREF_INITIALIZER {NULL, NULL}
113
114
115 /*
116   freeing policy:
117   in case no memory is available the GC will gradually free more unused memory
118   when this has no effect it calls a user setable routine 3 times to give the user a chance to handle the situation
119   this user routine gets the current policy and a pointer to supplemental data (hint: use a jmp_buf) as parameter
120   if all fails it will call abort() finally
121 */
122 typedef enum
123   {
124     ACOGC_COLLECT_DONTFREE,     /* just collect, do not free */
125     ACOGC_COLLECT_NORMAL,       /* normal collection freeing down to highwater */
126     ACOGC_COLLECT_FORCEMID,     /* freeing down to (lowwater+highwater)/2 */
127     ACOGC_COLLECT_FORCELOW,     /* freeing down to lowwater */
128     ACOGC_COLLECT_FORCEALL,     /* free all freeable objects */
129     ACOGC_COLLECT_USER1,        /* call userhook first time (free some mem) */
130     ACOGC_COLLECT_USER2,        /* call userhook second time (free memory hardly) */
131     ACOGC_COLLECT_USER3,        /* call userhook third time (handle memory failure or free memory even harder) */
132     ACOGC_COLLECT_FAILED        /* still no memory available, will abort() */
133   } acogc_freeing_policy;
134
135 typedef enum
136   {
137     ACOGC_STATE_ROOT = -1,
138     ACOGC_STATE_UNCOLLECTABLE_NONFINALIZEABLE,
139     ACOGC_STATE_UNCOLLECTABLE,
140     ACOGC_STATE_BUSY,
141     ACOGC_STATE_FIRST,
142     ACOGC_STATE_START,
143     ACOGC_STATE_LAST = INT_MAX
144   } acogc_object_state;
145
146 typedef enum
147   {
148     ACOGC_COLLECT,              /* collect the object */
149     ACOGC_KEEP,                 /* let the GC mark the object */
150     ACOGC_KEPT,                 /* returned to the user if the object was already marked */
151     ACOGC_LAST,                 /* manual tail-call optimization in effect */
152   } acogc_mark_result;
153
154 typedef enum
155   {
156     // first states are not GC controlled and memory tagged with them has no gc descriptor
157     ACOGC_UNSET,        /* undefined */
158     ACOGC_ALLOC,        /* malloc/free acogoc_alloc/acogc_free */
159     // next states for memory with gc descriptor
160     ACOGC_STATIC,       /* non freeable */
161     ACOGC_GC,           /* garbage collected */
162   } acogc_alloc_type;
163
164 /*
165   function types
166 */
167 typedef void (*acogc_initize_func)(void*);
168 typedef void (*acogc_finalize_func)(void*);
169 typedef acogc_mark_result (*acogc_mark_func)(void*);
170
171 /* nobug init */
172 void acogc_nobug_init();
173
174 /*
175   root
176
177   the acogc_root manages all memory allocated with acogc.
178   A program can use more than one acogc_root for implementing diffrent memory domains which must not cross-reference objects
179 */
180 struct acogc_root_struct
181 {
182   llist factories;
183
184   int state;                            /* actually a counter, 0 is reserved for root objects */
185
186   AcogcStack stack;
187
188   unsigned long allocation_counter;     /* counts every allocation since the last collection */
189   unsigned long collection_freq;        /* number of objects allocated since last collection */
190
191   AcogcObject last;                     /* buffer for last-call marking*/
192
193   void (*nomemhandler)(void*, acogc_freeing_policy);    /* called when no memory can be allocated */
194   void* nomemsupp;                                      /* supplemental data for the nomem handler*/
195 };
196
197
198 /*
199   initialize a acogc_root structure
200 */
201 void
202 acogc_root_init (AcogcRoot self);
203
204
205 /*
206   free all memory associated with a acogc_root,
207 */
208 void
209 acogc_root_erase (AcogcRoot self);
210
211 /*
212   do a collection, ususaly automatically triggered
213 */
214 void
215 acogc_root_collect (AcogcRoot self, acogc_freeing_policy pol);
216
217
218 /*
219   factory
220
221   the factory holds the static size for all objects it manages.
222   Objects are allocated with 'acogc_factory_alloc'.
223   Collected objects are cached and freed based on the high_water/low_water policies.
224   Collected, not-yet-freed objects can be reinstantiated and
225   the user can implement fancy caching schemes.
226 */
227 struct acogc_factory_struct
228 {
229   AcogcRoot root;                       /* points back to the root */
230   llist factories;                      /* links all factories of one root together */
231
232   llist roots;                          /* root objects for this factory */
233   llist alive;                          /* objects in use */
234   llist dead;                           /* unused objects (might still be referenced by weak pointers and reinstantiated on demand) */
235   llist tmp;                            /* temporary list for collection */
236
237   unsigned long objects_allocated;      /* grand number of objects (including free) */
238   unsigned long objects_used;           /* number of objects in use at the last collection */
239   unsigned long objects_new;            /* number of objects allocated since last collection */
240
241   unsigned low_water;                   /* allocate more when less than this % of objects are unused */
242   unsigned high_water;                  /* start freeing when more than this % of objects are unused */
243
244   size_t size;                          /* size od objects allocated by this factory */
245
246   acogc_mark_func mark;                 /* marker function */
247   acogc_initize_func initize;           /* initizer for NULL'ing referencess */
248   acogc_finalize_func finalize;         /* finalizer called before a object is free()'ed */
249
250   const char* factory_name;             /* only for debugging purpose */
251 };
252
253 /*
254   initialize a acogc_factory
255 */
256 void
257 acogc_factory_init (AcogcFactory self,
258                     AcogcRoot root,
259                     size_t size,
260                     unsigned low_water,
261                     unsigned high_water,
262                     acogc_mark_func mark,
263                     acogc_initize_func initize,
264                     acogc_finalize_func finalize);
265
266
267 /* alloc memory from factory */
268 void *
269 acogc_factory_alloc (AcogcFactory self);
270
271
272 /*
273   object
274
275   a acogc_object prepends each user allocated block
276 */
277 struct acogc_object_struct
278 {
279   llist node;
280   AcogcFactory factory;
281   AcogcWeakref weakrefs;
282   int state;
283 };
284
285 /* register a object as GC root object, should be done as soon as possible after allocation */
286 void
287 acogc_addroot (void* object);
288
289 /* unregister a GC root object, it becomes normal collectable by this. */
290 void
291 acogc_removeroot (void* object);
292
293 /*
294   object
295  */
296 static inline void*
297 acogc_memory_from_object (const_AcogcObject const self)
298 {
299   return (void*)self + sizeof (acogc_object);
300 }
301
302 static inline AcogcObject
303 acogc_object_from_memory (const void * const self)
304 {
305   return (AcogcObject)(self - sizeof (acogc_object));
306 }
307
308 /*
309   factories can be used to identify the type of a object
310  */
311 static inline AcogcFactory
312 acogc_object_type (const void * o)
313 {
314   REQUIRE (o);
315   return acogc_object_from_memory (o)->factory;
316 }
317
318 /*
319   marking objects
320 */
321 acogc_mark_result
322 acogc_object_markreally (AcogcObject object);
323
324 static inline acogc_mark_result
325 acogc_object_mark (void * o)
326 {
327   TRACE(acogc_mark, "%p", o);
328
329   if (o)
330     {
331       AcogcObject object = acogc_object_from_memory (o);
332
333       TRACE_DBG (acogc_mark, "state %d", object->state);
334       TRACE_DBG (acogc_mark, "factory %p", object->factory);
335       TRACE_DBG (acogc_mark, "factory->root %p", object->factory->root);
336       TRACE_DBG (acogc_mark, "factory->root->state %d", object->factory->root->state);
337
338       if (object->state >= ACOGC_STATE_FIRST && object->state < object->factory->root->state)
339         {
340           /* not yet marked, mark now */
341           object->state = ACOGC_STATE_BUSY;
342           return acogc_object_markreally (object);
343         }
344       else
345         return ACOGC_KEPT;      /* already marked */
346     }
347   return ACOGC_COLLECT;         /* when o was NULL */
348 }
349
350 static inline acogc_mark_result
351 acogc_object_lastmark (void * o)
352 {
353   TRACE(acogc_mark, "lastmark %p", o);
354
355   if (o)
356     {
357       INFO (acogc_mark, "object %p", o);
358       AcogcObject object = acogc_object_from_memory (o);
359
360       TRACE_DBG (acogc_mark, "state %d", object->state);
361       TRACE_DBG (acogc_mark, "factory %p", object->factory);
362       TRACE_DBG (acogc_mark, "factory->root %p", object->factory->root);
363       TRACE_DBG (acogc_mark, "factory->root->state %d", object->factory->root->state);
364
365       if (object->state >= ACOGC_STATE_FIRST && object->state < object->factory->root->state)
366         {
367           ASSERT (object->factory->root->last == NULL, "last_mark not last in a marker");
368
369           object->state = ACOGC_STATE_BUSY;
370           object->factory->root->last = object;
371           return ACOGC_KEEP;
372           //return acogc_object_markreally (object);
373         }
374       else
375         return ACOGC_KEPT;
376     }
377   return ACOGC_COLLECT;       // when o was NULL
378 }
379
380
381 /*
382   weakrefs
383
384   weak references are lists which must be maintained by the programmer
385 */
386 struct acogc_weakref_struct
387 {
388   AcogcWeakref next;
389   void * ref;
390 };
391
392 static inline void
393 acogc_weakref_init (AcogcWeakref self)
394 {
395   REQUIRE (self);
396   self->next = self->ref = NULL;
397 }
398
399 void
400 acogc_weakref_link (AcogcWeakref self, void* object);
401
402 void
403 acogc_weakref_unlink (AcogcWeakref self);
404
405 void
406 acogc_object_weakref_invalidate (void* memory);
407
408
409 /*
410   when a object is swept but still not freed it can be reinstatiated (for example if a weak-reference points to it)
411 */
412
413 /* dereference a weak reference, reinstantiate it if required */
414 void *
415 acogc_weakref_reinstget (AcogcWeakref self);
416
417 /* dereference a weak reference, do not reinstantiate it if swept, return NULL */
418 void *
419 acogc_weakref_get (AcogcWeakref self);
420
421 void
422 acogc_weakref_assert_cleared (AcogcWeakref p);
423
424 /*
425   manual allocation not garbagge collected, needs to be acogc_free()'d
426   the advantage of these are that malloc will initiate a garbagge collection
427   if no memory is available and call the registered nomemhandler.
428   This functions are guranteed to be interchangeable with malloc/realloc/free as
429   long the pointer doesn't hold a reference, see below.
430 */
431
432 /*
433   try to (re-)allocate some block of memory with a new size
434   *addr has to be initialized to NULL
435   trying to reallocate a reference is illegal.
436
437   unfotunally we need some ugly casts here
438 */
439 void
440 acogc_alloc_ (void ** addr, size_t size, AcogcRoot factory);
441 #define acogc_alloc(addr, size, root) acogc_alloc_ ((void*)addr, size, root)
442
443 /*
444   realloc a memory block to at least needed size, min 16 bytes, increased by a 1.5 factor on resizing
445   return the amount really reserved
446   when resizing is finsished one might fixate it by calling acogc_alloc with the real required size at last,
447   some realloc implementations might free some memory thereafter.
448 */
449 size_t
450 acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcRoot root);
451 #define acogc_reserve(addr, actual, needed, root) acogc_reserve_ ((void*)addr, actual, needed, root)
452
453 /*
454   free *addr if not a reference and set it to NULL
455 */
456 void
457 acogc_free_ (void ** addr);
458 #define acogc_free(addr) acogc_free_ ((void*)addr)
459
460 void
461 acogc_assert_stackframeleft (AcogcStack_ref p);
462
463 #endif
464 /*
465 // Local Variables:
466 // mode: C
467 // c-file-style: "gnu"
468 // End:
469 // arch-tag: 855b7025-8227-4892-ac25-9b0a3d57dd0b
470 // end_of_file
471 */