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