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