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