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