[project @ chth@gmx.net-20060624024510-17b61a029bc9d94f]

[acogc.git] / lib / acogc.h

/*
  acogc.h - simple accurate/cooperative garbage collector

  Copyright (C) 2006, Christian Thaeter <chth@gmx.net>

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License version 2 as
  published by the Free Software Foundation.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, contact me.

*/
\f
#ifndef ACOGC_H
#define ACOGC_H

/*
accurate
  only real references are used for marking objects instead scanning all objects

cooperative
  the programmer has to supply functions which mark references in his datastructures
*/


#include <stdlib.h>
#include <stdint.h>
#include <valgrind/valgrind.h>
#include "llist.h"

#ifdef EBUG_ACOGC       /* CFLAGS+=-DEBUG_ACOGC */
#include <assert.h>
#include <stdio.h>
#include <string.h>
#define ACOGC_TRACE(lvl,fmt,...) do{if(lvl<=EBUG_ACOGC)VALGRIND_PRINTF("%s@%d %s " fmt, strrchr(__FILE__, '/')?strrchr(__FILE__, '/') + 1 : __FILE__,__LINE__, __func__ , ## __VA_ARGS__);}while(0)
#define ACOGC_ASSERT(expr,fmt,...) do{if(!(expr)){VALGRIND_PRINTF_BACKTRACE("%s " fmt, #expr, ## __VA_ARGS__);abort();}}while(0)

#ifdef __GNUC__
#define ACOGC_CLEANUP(fn)  __attribute__((cleanup(fn)))
#endif

#else
#define ACOGC_TRACE(fmt,...) do{}while(0)
#define ACOGC_ASSERT(expr,fmt,...) do{}while(0)
#endif

#ifdef __GNUC__
#define ACOGC_CLEANUP(fn)  __attribute__((cleanup(fn)))
#endif

/*
  object types and handles
*/
#define ACOGC_DECLARE(name,Handle) \
  struct acogc_##name##_struct; \
  typedef struct acogc_##name##_struct acogc_##name;\
  typedef const acogc_##name * const_Acogc##Handle;\
  typedef acogc_##name * Acogc##Handle;\
  typedef acogc_##name ** Acogc##Handle##_ref;\
  typedef const acogc_##name ** const_Acogc##Handle##_ref

//ACOGC_DECLARE(marker,Marker);
ACOGC_DECLARE(factory,Factory);
ACOGC_DECLARE(object,Object);
ACOGC_DECLARE(weakreference,WeakReference);

/*
  function types
*/

//typedef void (*acogc_initize_func)(void*, size_t);

/*
  the user needs to provide custom scan functions for his objects,
  ?TODO? returning !0 normally but 1 if the object should not be marked (unmarked)
*/
typedef void (*acogc_scan_func)(void* obj);
typedef void (*acogc_finalize_func)(void*);


/*
  enumerations
*/
enum acogc_emergency_level
  {
    ACOGC_COLLECT_DONTFREE,     /* just collect, do not free */
    ACOGC_COLLECT_NORMAL,       /* normal collection */
    ACOGC_COLLECT_FORCELOW,     /* free down to lowwater in this factory */
    ACOGC_COLLECT_ALLFORCELOW,  /* free down to lowwater in all factories */
    ACOGC_COLLECT_FREEABLE,     /* free all freeable objects in this factory */
    ACOGC_COLLECT_ALLFREEABLE,  /* free all freeable objects in all factories */
    ACOGC_COLLECT_FAILED        /* can' reclaim any memory */
  };

enum acogc_flags
  {
    ACOGC_FLAG_UNINITIALIZED = 0x0,     // allocated but not yet initialized object (keeps GC locked, becomes black)
    /* the interpretation of colors cycles through 3 states 001 010 100 starting with ecru == 001 followed by white and black */
    ACOGC_COLOR_1 = 0x1,                // 001
    ACOGC_COLOR_2 = 0x2,                // 010
    ACOGC_COLOR_3 = 0x4,                // 100
    /* next some values are reserved for special purposes where flags > 0x4 */
    ACOGC_FLAG_ROOT_COLLECTABLE = 0x5,  // 101
    ACOGC_FLAG_ROOT_STATIC      = 0x6,  // 110
    ACOGC_FLAG_RESERVED         = 0x7   // 111 unused for now
  };

/*
  manual allocation not garbagge collected, needs to be acogc_free()'d
  the advantage of these are that malloc will initiate a garbagge collection
  if no memory is available and call the registered nomemhandler.
  This functions are guranteed to be interchangeable with malloc/realloc/free as
  long the pointer doesn't hold a reference, see below.

  as special feature a address can be setref'ed to another address,
  the lowest bit is used to indicate this. So only aligned addresses are
  allowed for this. use the acogc_deref() function to mask it out.
*/

/*
  unfortunally C doesn't require to align string literals, which is needed when you use the reference feature.
  This can be enforced with this macro.
*/
#ifdef __GNUC__
#define ACOGC_ALIGNED_STRING(string) (const char*)&((char __attribute__((aligned(sizeof(int))))[sizeof(string)]){string})
#else // fallback for other compilers
#define ACOGC_ALIGNED_STRING(string) (const char*)(&((struct {int nil; char str [sizeof(string)];}){0,string}.str))
#endif

/*
  try to (re-)allocate some block of memory with a new size
  *addr has to be initialized to NULL
  trying to reallocate a reference is illegal.
*/
void
acogc_alloc_ (void ** addr, size_t size, AcogcFactory factory);
#define acogc_alloc(addr, size, root) acogc_alloc_ ((void**)addr, size, root)

/*
  realloc a memory block to at least needed size, min 16 bytes, increased by a 1.5 factor on resizing
  return the amount really reserved
  when resizing is finsished one might fixate it by calling acogc_alloc with the real required size at last,
  some realloc implementations might free some memory thereafter.
*/
size_t
acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcFactory factory);
#define acogc_reserve(addr, actual, needed, root) acogc_reserve_ ((void**)addr, actual, needed, root)

/*
  free *addr if not a reference and set it to NULL
*/
void
acogc_free_ (void ** addr);
#define acogc_free(addr) acogc_free_ ((void**)addr)

/*
  set addr as reference to ref
*/
static inline void
acogc_set_ref_ (void ** addr, const void * ref)
{
  *addr = ref?(void*) (((uintptr_t)ref) | 1):NULL;
}
#define acogc_set_ref(addr, ref) acogc_set_ref_ ((void**)addr, ref)


/*
  just return the real address value from a possible reference
*/
static inline void *
acogc_ref_get_ (void * addr)
{
  return (void*) (((uintptr_t)addr) & ~(uintptr_t)1);
}
#define acogc_ref_get(addr) (typeof(addr)) acogc_ref_get_ ((void*)addr)

static inline int
acogc_is_ref (void * addr)
{
  return (int)(((uintptr_t)addr) & 1);
}


// TODO cleanup check does not work
#define ACOGC_ROOT_REGISTER(name, marker, gcroot, data)         \
  acogc_marker name##_acogc_marker                              \
    ACOGC_CLEANUP (acogc_marker_assert_unregistered_root)       \
    = {NULL, marker, &name, data};                              \
  acogc_root_register_marker (gcroot, &name##_acogc_marker)

#define ACOGC_ROOT_UNREGISTER(name, gcroot)                     \
  acogc_root_marker_unregister (gcroot, &name##_acogc_marker)

/*
  factory

  factories are manage classes of memory objects, there are 2 modes in which these factories can operate:

  first the factory holds the static size for all objects it manages. objects are allocated with 'acogc_factory_alloc'. In this mode swept objects are cached and freed based on the high_water/low_water values. objects can be reinstantiated and the user can implement fancy caching schemes.

  second when the 'size' is initialized to 0, dynamic sized objects will be allocated with 'acogc_factory_alloc_size', the swept-queue will not be used for allocations

*/
  /*
    adaptive auto configuration:

    ideally a collection (all grey nodes scanned) should be finish just before the freelist
    gets empty this would give the optimal memory utilization.

    If it finishes earlier the time spend in incremental collecting was not ideally distributed which has a small performance impact or there are too much free objects available for the required working set.

    if the collection is not complete when the freelist becomes empty we have to force a scan if the GC is not locked to get a new freelist or allocate new objects despite there may be enough potential free objects which we cant use yet.

    So the goal is to optimize the scan_freq in a way that the collection completes before the freelist becomes empty and avoid cases where the collection takes to long.

  */

struct acogc_factory_struct
{
  llist factories;

  llist bottom;
  LList top;
  LList scan;
  LList free;

  llist roots;
  LList scanned_roots;

  int gc_lock;                  // if >0 then dont flip (collector locked)
  int ecru_color;               // 001 010 100 .. current value which tags ecru

  /* configuration */
  unsigned scan_freq;           // scan every this actions (alloc or touch)
  unsigned scan_at_once;        // scan this much elements in a scan-round

  /* statistics counters */
  unsigned scan_counter;        // decremented from scan_freq to 0 to initiate a scan an then reset
  unsigned objects_allocated;   // how many objects are in this factory
  unsigned objects_black;       // how many objects are marked black (in use when the collection is complete)
  unsigned objects_white;       // how many objects are marked free

  unsigned scanned;             // count scanned objects
  signed idle;                  // increment for scan attempts after collection completed,
                                // decrement for each allocation when the collection is not yet complete

  /* statistics state */
  unsigned scan_freq_avg;       // cumulating average of the scan freq
  signed idle_avg;              // count scan attempts after collection completed

  unsigned free_limit;          /* keep at most free_limit% objects free else start really freeing objects */
  unsigned object_cluster;      /* this many objects are allocated or freed at once */

  size_t size;                  /* 0 for dynamic sized factory */

  acogc_finalize_func finalize_func;    /* called when a object is freed or reused (but not reinstantiated) */
  acogc_scan_func scan_func;            /* called when a object is marked */
  //void * touch_data;                    /* supplemental user data passed to touch */
  //void (*nomemhandler)(void);           /* called when no memory can be allocated, defaults to abort() */
};

/*
  initialize a acogc_factory
  when size==0 this factory will be used for dynamic sized allocations
  the user must supply a custom mark function which calls acogc_object_mark for all (nonweak) references within his object
*/
AcogcFactory
acogc_factory_new (AcogcFactory other,
                   size_t size,
                   unsigned free_limit,
                   unsigned object_cluster,
                   acogc_scan_func scan,
                   acogc_finalize_func finalize);

void
acogc_factory_erase (AcogcFactory self);

void
acogc_factory_free (AcogcFactory self);

void
acogc_factory_init (AcogcFactory self,
                    AcogcFactory other,
                    size_t size,
                    unsigned free_limit,
                    unsigned object_cluster,
                    acogc_scan_func scan,
                    acogc_finalize_func finalize);


//void * mark_data);


/* alloc memory from factory with predefined size */
void *
acogc_factory_alloc (AcogcFactory self);

// TODO macro for ensuring a acogc_object_initialized?

/* free() swept objects, normally called automatically by the collector */
//void
//acogc_factory_collectfree (AcogcFactory self, enum acogc_emergency_level elvl);


void
acogc_factory_scan (AcogcFactory self);

void
acogc_factory_flip (AcogcFactory self);



/*
  object

  a acogc_object prepends each user allocated block
*/
struct acogc_object_struct
{
  llist objects;
  AcogcFactory factory;         /* last bits are used as flags */
  AcogcWeakReference weakrefs;
};

// rotate last 3 bits left
static inline unsigned
acogc_flags_rol_ (unsigned x)
{
  return x==4?1:x+x;
}

// rotate last 3 bits right
static inline unsigned
acogc_flags_ror_ (unsigned x)
{
  return x==1?4:x>>1;
}

static inline AcogcObject
acogc_object_from_memory_ (void * object)
{
  return (AcogcObject)(object - sizeof (acogc_object));
} 

static inline void *
acogc_memory_from_object_ (AcogcObject object)
{
  return (void*)object + sizeof (acogc_object);
} 

static inline AcogcObject
acogc_object_from_list_ (LList object)
{
  return LLIST_TO_STRUCTP (object, acogc_object, objects);
}

static inline void *
acogc_memory_from_list_ (LList object)
{
  return acogc_memory_from_object_ (LLIST_TO_STRUCTP (object, acogc_object, objects));
}

static inline AcogcFactory
acogc_object_factory_get_ (AcogcObject object)
{
  return (AcogcFactory)((uintptr_t)(object->factory) & (uintptr_t)~0x7);
}

static inline unsigned
acogc_object_flags_get_ (AcogcObject object)
{
  return (unsigned)((uintptr_t)(object->factory) & (uintptr_t)0x7);
}

static inline void
acogc_object_set_factory_flags_ (AcogcObject object, AcogcFactory factory, const unsigned flags)
{
  object->factory = (AcogcFactory)((uintptr_t)factory | (uintptr_t)flags);
}

static inline void
acogc_object_set_flags_ (AcogcObject object, const unsigned flags)
{
  uintptr_t f = (uintptr_t)object->factory & (uintptr_t)~0x7;
  object->factory = (AcogcFactory)(f | (uintptr_t)flags);
}

static inline unsigned
acogc_object_factory_ecru_ (AcogcObject object)
{
  return acogc_object_factory_get_ (object)->ecru_color;
}

static inline unsigned
acogc_object_factory_white_ (AcogcObject object)
{
  return acogc_flags_ror_ (acogc_object_factory_ecru_ (object));
}

static inline unsigned
acogc_object_factory_black_ (AcogcObject object)
{
  return acogc_flags_rol_ (acogc_object_factory_ecru_ (object));
}

/* implements a read barrier */
void
acogc_object_touch_really_ (AcogcObject object);

static inline void
acogc_object_touch (void* object)
{
  AcogcObject o = acogc_object_from_memory_ (object);
  if (acogc_object_flags_get_ (o) == acogc_object_factory_ecru_ (o))
    acogc_object_touch_really_ (o);
}

static inline void
acogc_object_initialized (void* object)
{
  AcogcObject o = acogc_object_from_memory_ (object);
  ACOGC_ASSERT (acogc_object_flags_get_ (o) == ACOGC_FLAG_UNINITIALIZED, "object is not uninitialized");
  acogc_object_set_flags_ (o, acogc_object_factory_black_ (o));
  --acogc_object_factory_get_ (o)->gc_lock;
}


/* register a object as GC root object, should be done as soon as possible after allocation */
void
acogc_object_addroot (void* object);

/* unregister a GC root object, it becomes normal collectable by this. */
void
acogc_object_removeroot (void* object);




/*
  references

  weak references are lists which must be maintained by the programmer
*/
struct acogc_weakreference_struct
{
  AcogcWeakReference next;
  void * ref;
};

static inline void
acogc_weakreference_init (AcogcWeakReference self)
{
  self->next = self->ref = NULL;
}

/*
  intrusive weak references:
  objects which allow weak references to them need to implement a

  AcogcReference member;  head of a linked list, initialized to NULL

  when the object is collected one must use acogc_reference_weak_invalidate with this pointer to invalidate all weak refs. This can be done in sweep_finalizer or in free_finalizer. It becomes possible that weak references point to dead, not yet freed objects one should then use acogc_object_reinstantiate to make the object life again and establish a some normal reference to this object, else it will be collected soon again and become dead.

  A weak reference is of type acogc_reference with both members initialized to NULL

  a weak reference is set up with acogc_reference_link_weak and one must not forget to acogc_reference_weak_unlink before the reference object gets deleted

*/
void
acogc_weakreference_link (AcogcWeakReference self, void* object);

void
acogc_weakreference_unlink (AcogcWeakReference self);

void
acogc_object_weakreference_invalidate (void* object);


/*
  when a object is swept but still not freed it can be reinstatiated (for example if a weak-reference points to it)
*/

/* dereference a weak reference, reinstantiate it if required */
void *
acogc_weakreference_reinstget (AcogcWeakReference self);

/* dereference a weak reference, do not reinstantiate it, return NULL if in freelist */
void *
acogc_weakreference_get (AcogcWeakReference self);


//enum acogc_reference_state
//acogc_reference_state (AcogcWeakReference self);

void
acogc_reference_assert_cleared (AcogcWeakReference p);

/* declare a weak reference als automatic variable, asserts that the reference gets unlinked when the stackframe is left (-DEBUG_ACOGC on gcc only) */
#define ACOGC_WEAKREFERENCE(name) acogc_weakreference name ACOGC_CLEANUP(acogc_weakreference_assert_cleared) = {NULL, NULL}

#define ACOGC_REFERENCE_INIT(name) acogc_weakreference name ACOGC_CLEANUP(acogc_weakreference_assert_cleared) = {NULL, NULL}


#endif
/*
// Local Variables:
// mode: C
// c-file-style: "gnu"
// End:
// arch-tag: 855b7025-8227-4892-ac25-9b0a3d57dd0b
// end_of_file
*/