From 05e0f50d0cc058b8ffd504af0b1b62d68b6b6f26 Mon Sep 17 00:00:00 2001 From: Christian Thaeter Date: Sat, 24 Jun 2006 04:45:10 +0200 Subject: [PATCH] [project @ chth@gmx.net-20060624024510-17b61a029bc9d94f] some work --- lib/acogc.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- lib/acogc.h | 125 +++++++++++++++++++++++++++++---------------- 2 files changed, 227 insertions(+), 63 deletions(-) diff --git a/lib/acogc.c b/lib/acogc.c index b3bfc5f..4f5a790 100644 --- a/lib/acogc.c +++ b/lib/acogc.c @@ -172,18 +172,18 @@ acogc_factory_init (AcogcFactory self, size_t size, unsigned free_limit, unsigned object_cluster, - acogc_touch_func touch, + acogc_scan_func scan, acogc_finalize_func finalize) { llist_init (&self->factories); if (other) llist_insert_after (&self->factories, &other->factories); - llist_init (&self->ecru); - self->grey = self->black = self->white = &self->ecru; + llist_init (&self->bottom); + self->top = self->scan = self->free = &self->bottom; - llist_init (&self->red); - self->yellow = &self->red; + llist_init (&self->roots); + self->scanned_roots = &self->roots; self->gc_lock = 0; self->ecru_color = 0x1; @@ -193,14 +193,16 @@ acogc_factory_init (AcogcFactory self, self->scan_at_once = object_cluster/4?object_cluster/4:1; /* statistics counters */ + self->scan_counter = 1; + self->objects_allocated = 0; + self->objects_black = 0; + self->objects_white = 0; self->scanned = 0; self->idle = 0; - self->overscan = 0; /* statistics state */ self->scan_freq_avg = 1; self->idle_avg = 0; - self->overscan_avg = 0; /*size_t memory_allocated; */ @@ -209,8 +211,8 @@ acogc_factory_init (AcogcFactory self, self->size = size; - self->finalize = finalize; - self->touch = touch; + self->finalize_func = finalize; + self->scan_func = scan; //void * touch_data; /* supplemental user data passed to touch */ //void (*nomemhandler)(void); /* called when no memory can be allocated, defaults to abort() */ } @@ -220,14 +222,14 @@ acogc_factory_new (AcogcFactory other, size_t size, unsigned free_limit, unsigned object_cluster, - acogc_touch_func touch, - acogc_finalize_func finalize) + acogc_scan_func scan, + acogc_finalize_func finalize) { AcogcFactory self = malloc (sizeof (acogc_factory)); if (!self) return NULL; - acogc_factory_init (self, other, size, free_limit, object_cluster, touch, finalize); + acogc_factory_init (self, other, size, free_limit, object_cluster, scan, finalize); return self; } @@ -256,36 +258,159 @@ acogc_factory_erase (AcogcFactory self) void * acogc_factory_alloc (AcogcFactory self) { - (void) self; - return NULL; + AcogcObject object; + + if (!self->scan_counter--) + acogc_factory_scan (self); + + if (!self->gc_lock && self->scan == self->top && !self->objects_white) + acogc_factory_flip (self); + + if (!self->objects_white) + { + if (self->scan == self->top) + self->idle++; + else + self->idle--; + + object = malloc (sizeof (acogc_object) + self->size); + // TODO lowmem strategy + if (!object) + abort (); + + llist_init (&object->objects); + acogc_object_set_factory_flags_ (object, self, ACOGC_FLAG_UNINITIALIZED); + object->weakrefs = NULL; + + self->objects_allocated++; + } + else + { + object = LLIST_TO_STRUCTP(self->free, acogc_object, objects); + self->free = llist_get_next (self->free); + if (self->finalize_func) + self->finalize_func (acogc_memory_from_object_ (object)); + + acogc_object_weakreference_invalidate (object); + + self->objects_white--; + acogc_object_set_flags_ (object, ACOGC_FLAG_UNINITIALIZED); + } + + self->objects_black++; + + if (self->objects_allocated > 2 * self->object_cluster && + ((100 * self->objects_white) / self->objects_allocated) > self->free_limit) + { + for (unsigned i = self->object_cluster; i; --i) + { + // TODO remove from head or from tail? + //AcogcObject deleteme = LLIST_TO_STRUCTP(llist_get_prev (&self->bottom), acogc_object, objects); + AcogcObject deleteme = LLIST_TO_STRUCTP(llist_get_next (self->free), acogc_object, objects); + + if (self->finalize_func) + self->finalize_func (acogc_memory_from_object_ (deleteme)); + + acogc_object_weakreference_invalidate (deleteme); + + llist_unlink (&deleteme->objects); + + self->objects_white--; + self->objects_allocated--; + + free (deleteme); + } + } + + return acogc_memory_from_object_ (object); } +void +acogc_factory_scan (AcogcFactory self) +{ + ACOGC_TRACE (1,"scanning %p", self); + + self->scan_counter = self->scan_freq; + + for (int i = self->scan_at_once; i; --i) + { + ACOGC_TRACE (2,"%d", i); + + LList l; + while (self->scan == self->top && (l = llist_get_prev (self->scanned_roots)) != &self->roots) + { + // touch root chain until we fetched at least one gray object or we scanned all nodes in the root chain + ACOGC_TRACE (3, "fetching root %p", acogc_memory_from_list_ (l)); + acogc_object_touch (acogc_memory_from_list_ (l)); + self->scanned_roots = l; + } + + if (self->scan == self->top) + { + ACOGC_TRACE (4, "scan already completed"); + self->idle++; + } + else + { + if (!self->objects_white) + { + ACOGC_TRACE (4, "scan runing while freelist is empty"); + self->idle--; + } + + ACOGC_TRACE (3, "touching %p", acogc_memory_from_list_ (self->scan)); + acogc_object_touch (acogc_memory_from_list_ (self->scan)); + self->scan = llist_get_prev (self->scan); + } + } +} + +void +acogc_factory_flip (AcogcFactory self) +{ + assert (!self->gc_lock && self->scan == self->top && !self->objects_white); + + // reestimate settings + // reset statistics calculate averages + +} + + + + /* object */ -/* register a object as GC root object, should be done as soon as possible after allocation */ void -acogc_addroot (void* object) +acogc_object_touch_really_ (AcogcObject object) { (void) object; //TODO + + // set color to black, increment black counter + + //if (!self->scan_counter--) + // acogc_factory_scan (self); + } -/* unregister a GC root object, it becomes normal collectable by this. can be expensive */ + + +/* register a object as GC root object, should be done as soon as possible after allocation */ void -acogc_removeroot (void* object) +acogc_addroot (void* object) { (void) object; //TODO } +/* unregister a GC root object, it becomes normal collectable by this. can be expensive */ void -acogc_object_touch_really_ (void* object) +acogc_removeroot (void* object) { (void) object; //TODO } - /* reference */ diff --git a/lib/acogc.h b/lib/acogc.h index e22e89c..f60301d 100644 --- a/lib/acogc.h +++ b/lib/acogc.h @@ -77,11 +77,10 @@ ACOGC_DECLARE(weakreference,WeakReference); //typedef void (*acogc_initize_func)(void*, size_t); /* - the user needs to provide custom touch functions for his objects, + 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 int (*acogc_touch_func)(void* obj, int m, void* supp); -typedef void (*acogc_touch_func)(void* obj); +typedef void (*acogc_scan_func)(void* obj); typedef void (*acogc_finalize_func)(void*); @@ -226,13 +225,13 @@ struct acogc_factory_struct { llist factories; - llist ecru; - LList grey; - LList black; - LList white; + llist bottom; + LList top; + LList scan; + LList free; - llist red; - LList yellow; + 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 @@ -242,24 +241,26 @@ struct acogc_factory_struct 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 - unsigned idle; // count scan attempts after collection completed - unsigned overscan; // count forced scans after the freelist got empty + 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 - unsigned idle_avg; // count scan attempts after collection completed - unsigned overscan_avg; // count forced scans after the freelist got empty - - /*size_t memory_allocated; */ + 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; /* called when a object is freed or reused (but not reinstantiated) */ - acogc_touch_func touch; /* called when a object is marked */ + 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() */ }; @@ -274,7 +275,7 @@ acogc_factory_new (AcogcFactory other, size_t size, unsigned free_limit, unsigned object_cluster, - acogc_touch_func touch, + acogc_scan_func scan, acogc_finalize_func finalize); void @@ -289,7 +290,7 @@ acogc_factory_init (AcogcFactory self, size_t size, unsigned free_limit, unsigned object_cluster, - acogc_touch_func touch, + acogc_scan_func scan, acogc_finalize_func finalize); @@ -307,6 +308,14 @@ acogc_factory_alloc (AcogcFactory self); //acogc_factory_collectfree (AcogcFactory self, enum acogc_emergency_level elvl); +void +acogc_factory_scan (AcogcFactory self); + +void +acogc_factory_flip (AcogcFactory self); + + + /* object @@ -321,77 +330,107 @@ struct acogc_object_struct // rotate last 3 bits left static inline unsigned -acogc_flags_rol (unsigned x) +acogc_flags_rol_ (unsigned x) { return x==4?1:x+x; } // rotate last 3 bits right static inline unsigned -acogc_flags_ror (unsigned x) +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 (void * object) +acogc_object_factory_get_ (AcogcObject object) { - return (AcogcFactory)((uintptr_t)(((AcogcObject)(object - sizeof (acogc_object)))->factory) & (uintptr_t)~0x7); + return (AcogcFactory)((uintptr_t)(object->factory) & (uintptr_t)~0x7); } static inline unsigned -acogc_object_flags_get (void * object) +acogc_object_flags_get_ (AcogcObject object) { - return (unsigned)((uintptr_t)(((AcogcObject)(object - sizeof (acogc_object)))->factory) & (uintptr_t)0x7); + return (unsigned)((uintptr_t)(object->factory) & (uintptr_t)0x7); } static inline void -acogc_object_set_flags (void * object, const unsigned flags) +acogc_object_set_factory_flags_ (AcogcObject object, AcogcFactory factory, const unsigned flags) { - uintptr_t f = (uintptr_t)((AcogcObject)((char*)object - sizeof (acogc_object)))->factory; - - f = (f & (uintptr_t)~0x7) | (uintptr_t)flags; - - ((AcogcObject)((char*)object - sizeof (acogc_object)))->factory = (AcogcFactory)f; + 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 (void* object) +acogc_object_factory_ecru_ (AcogcObject object) { - return acogc_object_factory_get (object)->ecru_color; + return acogc_object_factory_get_ (object)->ecru_color; } static inline unsigned -acogc_object_factory_white (void * object) +acogc_object_factory_white_ (AcogcObject object) { - return acogc_flags_ror (acogc_object_factory_ecru (object)); + return acogc_flags_ror_ (acogc_object_factory_ecru_ (object)); } static inline unsigned -acogc_object_factory_black (void * object) +acogc_object_factory_black_ (AcogcObject object) { - return acogc_flags_rol (acogc_object_factory_ecru (object)); + return acogc_flags_rol_ (acogc_object_factory_ecru_ (object)); } /* implements a read barrier */ void -acogc_object_touch_really_ (void* object); +acogc_object_touch_really_ (AcogcObject object); static inline void acogc_object_touch (void* object) { - if (acogc_object_flags_get (object) == acogc_object_factory_ecru (object)) - acogc_object_touch_really_ (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) { - ACOGC_ASSERT (acogc_object_flags_get (object) == ACOGC_FLAG_UNINITIALIZED, "object is not uninitialized"); - acogc_object_set_flags (object, acogc_object_factory_black (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); @@ -440,7 +479,7 @@ void acogc_weakreference_unlink (AcogcWeakReference self); void -acogc_weakreference_invalidate (void* object); +acogc_object_weakreference_invalidate (void* object); /* -- 2.11.4.GIT