lib/acogc.c

   1 /*
   2   acogc.c - 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
  20 #include <assert.h>
  21 #include <stdlib.h>
  22
  23 #include "acogc.h"
  24
  25 // TODO statistic to auto-adjust the GC (freq, highwater, lowwater)
  26 // TODO return value for lowmemhandler ABORT, RETRY
  27 // TODO prepare for a acogc_object_touch read barrier and a incremental GC scheme
  28
  29 /*
  30   tool 'macros' first
  31 */
  32
  33 static inline void
  34 object_set_factory (AcogcObject self, const_AcogcFactory factory)
  35 {
  36   self->factory = (AcogcFactory)factory;
  37 }
  38
  39 static inline void
  40 object_set_factory_color (AcogcObject self,
  41                           const_AcogcFactory factory,
  42                           const unsigned color)
  43 {
  44   self->factory = (AcogcFactory)((uintptr_t)factory | (uintptr_t)color);
  45 }
  46
  47 static inline unsigned
  48 object_color_get (const_AcogcObject self)
  49 {
  50   return (unsigned)!!(((uintptr_t)self->factory) & (uintptr_t)0x1);
  51 }
  52
  53
  54 static inline void*
  55 object_to_memory (const_AcogcObject const self)
  56 {
  57   return (void*)self + sizeof (acogc_object);
  58 }
  59
  60 static inline AcogcObject
  61 memory_to_object (const void * const self)
  62 {
  63   return (AcogcObject)(self - sizeof (acogc_object));
  64 }
  65
  66
  67 /* malloc / free wrapers */
  68 void
  69 acogc_alloc_ (void ** addr, size_t size, AcogcFactory factory)
  70 {
  71   void * ret;
  72   enum acogc_emergency_level emergency = ACOGC_COLLECT_NORMAL;
  73
  74   /* alloc memory */
  75  retry:
  76   ret = realloc (*addr, size);
  77   if (!ret)
  78     {
  79       ACOGC_TRACE (2, "emergency %d", emergency + 1);
  80       if ((emergency += 2) >= ACOGC_COLLECT_FAILED)
  81         {
  82           (void) factory;
  83           // TODO factory->nomemhandler ();
  84           return;
  85         }
  86       // TODO acogc_root_collect (root, emergency);
  87       goto retry;
  88     }
  89   *addr = ret;
  90 }
  91
  92
  93 size_t
  94 acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcFactory factory)
  95 {
  96   size_t n;
  97
  98   for (n = actual>16 ? actual : 16; n <= needed; n += (n>>1)); /*n = n * 1.5*/
  99
 100   acogc_alloc (addr, n, factory);
 101
 102   // TODO lowmem backoff handler (retry with n=needed)
 103   return n;
 104 }
 105
 106
 107 void
 108 acogc_free_ (void ** addr)
 109 {
 110   if (!acogc_is_ref (*addr))
 111     free (*addr);
 112   *addr = NULL;
 113 }
 114
 115 #if 0
 116 /*
 117   marker
 118 */
 119 void
 120 acogc_marker_init (AcogcMarker self, acogc_mark_func marker, void* object, void* data)
 121 {
 122   self->next = NULL;
 123   self->marker = marker;
 124   self->object = object;
 125   self->data = data;
 126 }
 127
 128
 129 void
 130 acogc_root_register_marker (AcogcRoot self, AcogcMarker marker)
 131 {
 132   ACOGC_TRACE (2, "register marker func %p  data %p",marker->marker, marker->data);
 133   marker->next = self->markers;
 134   self->markers = marker;
 135 }
 136
 137 void
 138 acogc_root_marker_unregister (AcogcRoot self, AcogcMarker marker)
 139 {
 140   AcogcMarker_ref prev = &self->markers;
 141   AcogcMarker i = *prev;
 142
 143   while(i)
 144     {
 145       if (i == marker)
 146         {
 147           *prev = i->next;
 148           i->next = i->object = NULL;
 149           break;
 150         }
 151       else
 152         {
 153           prev = &i->next;
 154           i = i->next;
 155         }
 156     }
 157 }
 158
 159 void
 160 acogc_marker_assert_unregistered_root (AcogcMarker m)
 161 {
 162   (void) m;
 163   ACOGC_ASSERT (m->object == NULL, "root not unregistered");
 164 }
 165 #endif
 166 /*
 167   factory
 168 */
 169 void
 170 acogc_factory_init (AcogcFactory self,
 171                     AcogcFactory other,
 172                     size_t size,
 173                     unsigned free_limit,
 174                     unsigned object_cluster,
 175                     acogc_scan_func scan,
 176                     acogc_finalize_func finalize)
 177 {
 178   llist_init (&self->factories);
 179   if (other)
 180     llist_insert_after (&self->factories, &other->factories);
 181
 182   llist_init (&self->bottom);
 183   self->top = self->scan = self->free = &self->bottom;
 184
 185   llist_init (&self->roots);
 186   self->scanned_roots = &self->roots;
 187
 188   self->gc_lock = 0;
 189   self->ecru_color = 0x1;
 190
 191   /* configuration */
 192   self->scan_freq = 1;
 193   self->scan_at_once = object_cluster/4?object_cluster/4:1;
 194
 195   /* statistics counters */
 196   self->scan_counter = 1;
 197   self->objects_allocated = 0;
 198   self->objects_black = 0;
 199   self->objects_white = 0;
 200   self->scanned = 0;
 201   self->idle = 0;
 202
 203   /* statistics state */
 204   self->scan_freq_avg = 1;
 205   self->idle_avg = 0;
 206
 207   /*size_t memory_allocated; */
 208
 209   self->free_limit = free_limit;
 210   self->object_cluster = object_cluster;
 211
 212   self->size = size;
 213
 214   self->finalize_func = finalize;
 215   self->scan_func = scan;
 216   //void * touch_data;                    /* supplemental user data passed to touch */
 217   //void (*nomemhandler)(void);           /* called when no memory can be allocated, defaults to abort() */
 218 }
 219
 220 AcogcFactory
 221 acogc_factory_new (AcogcFactory other,
 222                    size_t size,
 223                    unsigned free_limit,
 224                    unsigned object_cluster,
 225                    acogc_scan_func scan,
 226                    acogc_finalize_func finalize)
 227 {
 228   AcogcFactory self = malloc (sizeof (acogc_factory));
 229   if (!self)
 230     return NULL;
 231
 232   acogc_factory_init (self, other, size, free_limit, object_cluster, scan, finalize);
 233
 234   return self;
 235 }
 236
 237 void
 238 acogc_factory_free (AcogcFactory self)
 239 {
 240   if (!self)
 241     return;
 242
 243   acogc_factory_erase (self);
 244
 245   llist_unlink (&self->factories);
 246   free (self);
 247 }
 248
 249 void
 250 acogc_factory_erase (AcogcFactory self)
 251 {
 252   (void) self;
 253   // TODO
 254   // unregister all roots
 255   // free all objects
 256 }
 257
 258 void *
 259 acogc_factory_alloc (AcogcFactory self)
 260 {
 261   AcogcObject object;
 262
 263   if (!self->scan_counter--)
 264     acogc_factory_scan (self);
 265
 266   if (!self->gc_lock && self->scan == self->top && !self->objects_white)
 267     acogc_factory_flip (self);
 268
 269   if (!self->objects_white)
 270     {
 271       if (self->scan == self->top)
 272         self->idle++;
 273       else
 274         self->idle--;
 275
 276       object = malloc (sizeof (acogc_object) + self->size);
 277       // TODO lowmem strategy
 278       if (!object)
 279         abort ();
 280
 281       llist_init (&object->objects);
 282       acogc_object_set_factory_flags_ (object, self, ACOGC_FLAG_UNINITIALIZED);
 283       object->weakrefs = NULL;
 284
 285       self->objects_allocated++;
 286     }
 287   else
 288     {
 289       object = LLIST_TO_STRUCTP(self->free, acogc_object, objects);
 290       self->free = llist_get_next (self->free);
 291       if (self->finalize_func)
 292         self->finalize_func (acogc_memory_from_object_ (object));
 293
 294       acogc_object_weakreference_invalidate (object);
 295
 296       self->objects_white--;
 297       acogc_object_set_flags_ (object, ACOGC_FLAG_UNINITIALIZED);
 298     }
 299
 300   self->objects_black++;
 301
 302   if (self->objects_allocated > 2 * self->object_cluster &&
 303       ((100 * self->objects_white) / self->objects_allocated) > self->free_limit)
 304     {
 305       for (unsigned i = self->object_cluster; i; --i)
 306         {
 307           // TODO remove from head or from tail?
 308           //AcogcObject deleteme = LLIST_TO_STRUCTP(llist_get_prev (&self->bottom), acogc_object, objects);
 309           AcogcObject deleteme = LLIST_TO_STRUCTP(llist_get_next (self->free), acogc_object, objects);
 310
 311           if (self->finalize_func)
 312             self->finalize_func (acogc_memory_from_object_ (deleteme));
 313
 314           acogc_object_weakreference_invalidate (deleteme);
 315
 316           llist_unlink (&deleteme->objects);
 317
 318           self->objects_white--;
 319           self->objects_allocated--;
 320
 321           free (deleteme);
 322         }
 323     }
 324
 325   return acogc_memory_from_object_ (object);
 326 }
 327
 328
 329 void
 330 acogc_factory_scan (AcogcFactory self)
 331 {
 332   ACOGC_TRACE (1,"scanning %p", self);
 333
 334   self->scan_counter = self->scan_freq;
 335
 336   for (int i = self->scan_at_once; i; --i)
 337     {
 338       ACOGC_TRACE (2,"%d", i);
 339
 340       LList l;
 341       while (self->scan == self->top && (l = llist_get_prev (self->scanned_roots)) != &self->roots)
 342         {
 343           // touch root chain until we fetched at least one gray object or we scanned all nodes in the root chain
 344           ACOGC_TRACE (3, "fetching root %p", acogc_memory_from_list_ (l));
 345           acogc_object_touch (acogc_memory_from_list_ (l));
 346           self->scanned_roots = l;
 347         }
 348
 349       if (self->scan == self->top)
 350         {
 351           ACOGC_TRACE (4, "scan already completed");
 352           self->idle++;
 353         }
 354       else
 355         {
 356           if (!self->objects_white)
 357             {
 358               ACOGC_TRACE (4, "scan runing while freelist is empty");
 359               self->idle--;
 360             }
 361
 362           ACOGC_TRACE (3, "touching %p", acogc_memory_from_list_ (self->scan));
 363           acogc_object_touch (acogc_memory_from_list_ (self->scan));
 364           self->scan = llist_get_prev (self->scan);
 365         }
 366     }
 367 }
 368
 369 void
 370 acogc_factory_flip (AcogcFactory self)
 371 {
 372   assert (!self->gc_lock && self->scan == self->top && !self->objects_white);
 373
 374   // reestimate settings
 375   // reset statistics calculate averages
 376
 377 }
 378
 379
 380
 381
 382 /*
 383   object
 384 */
 385 void
 386 acogc_object_touch_really_ (AcogcObject object)
 387 {
 388   (void) object; //TODO
 389
 390   // set color to black, increment black counter
 391
 392   //if (!self->scan_counter--)
 393   //  acogc_factory_scan (self);
 394
 395 }
 396
 397
 398
 399 /* register a object as GC root object, should be done as soon as possible after allocation */
 400 void
 401 acogc_addroot (void* object)
 402 {
 403   (void) object; //TODO
 404 }
 405
 406 /* unregister a GC root object, it becomes normal collectable by this. can be expensive */
 407 void
 408 acogc_removeroot (void* object)
 409 {
 410   (void) object; //TODO
 411 }
 412
 413
 414 /*
 415   reference
 416 */
 417 void
 418 acogc_weakreference_link (AcogcWeakReference self, void* object)
 419 {
 420   (void) self;
 421   (void) object;
 422 #if 0 // TODO
 423   if (self->ref != object)
 424     {
 425       ACOGC_TRACE (4, "weaklink %p to %p", self, object);
 426       if(self->next)
 427         acogc_reference_weak_unlink (self);
 428       self->ref = object;
 429       self->next = *member?*member:(AcogcReference)member;
 430       *member = self;
 431     }
 432 #endif
 433 }
 434
 435 void
 436 acogc_weakreference_unlink (AcogcWeakReference self)
 437 {
 438   (void) self;
 439 #if 0 // TODO
 440   AcogcReference_ref prev = &self->next;
 441   AcogcReference i = self->next;
 442   if (i)
 443     {
 444       while (i != self)
 445         {
 446           ACOGC_ASSERT (i->next, "zero in weak cycle");
 447           prev = &i->next;
 448           i = i->next;
 449         }
 450       ACOGC_TRACE (4, "unlink %p from after %p, before %p", self, prev, self->next);
 451       *prev = self->next;
 452       if (*prev == (AcogcReference)prev)
 453         {
 454           ACOGC_TRACE (3, "weaklinks now empty %p", prev);
 455           prev = NULL;
 456         }
 457       self->ref = NULL;
 458       self->next = NULL;
 459     }
 460   else
 461     ACOGC_ASSERT (!self->ref, "reference not linked");
 462 #endif
 463 }
 464
 465 void
 466 acogc_object_weakreference_invalidate (void * object)
 467 {
 468   (void) object;
 469 #if 0 //TODO
 470   if (*self)
 471     {
 472       while ((*self)->next != *self)
 473         {
 474           AcogcReference tmp = *self;
 475           ACOGC_TRACE (3, "invalidate %p, ref %p", tmp, tmp->ref);
 476           (*self) = (*self)->next;
 477           tmp->ref = NULL;
 478           tmp->next = NULL;
 479         }
 480       *self = NULL;
 481     }
 482 #endif
 483 }
 484
 485
 486 void *
 487 acogc_weakreference_reinstget (AcogcWeakReference self)
 488 {
 489   (void) self; // TODO
 490
 491 #if 0
 492   if (!self->ref)
 493     return NULL;
 494
 495   AcogcObject o = memory_to_object (self->ref);
 496
 497   if (object_swept_get (o))
 498     {
 499       ACOGC_TRACE (4, "reinst %p", self->ref);
 500
 501       AcogcFactory ofactory = object_factory_get (o);
 502       AcogcObject i = ofactory->free_head;
 503       AcogcObject prev = NULL;
 504
 505       while (i != o)
 506         {
 507           prev = i;
 508           i = i->next;
 509         }
 510
 511       // remove from freequeue
 512       if (prev)
 513         prev->next = i->next;
 514       else
 515         ofactory->free_head = i->next;
 516
 517       if (ofactory->free_tail == i)
 518         ofactory->free_tail = prev;
 519
 520       // add to used
 521       i->next = ofactory->root->used;
 522       ofactory->root->used = i;
 523
 524       object_set_mark (i, ofactory->root->mark);
 525       object_set_swept (i, 0);
 526
 527       -- ofactory->objects_free;
 528       ++ ofactory->objects_used;
 529
 530       if (ofactory->reinst_initize)
 531         ofactory->reinst_initize (self->ref, ofactory->size);
 532     }
 533
 534   ACOGC_ASSERT (self->ref, "");
 535   return self->ref;
 536 #endif
 537   return NULL;
 538 }
 539
 540 void *
 541 acogc_weakreference_get (AcogcWeakReference self)
 542 {
 543   (void) self;
 544 #if 0 // TODO
 545   if (!self || !self->ref)
 546     return NULL;
 547
 548   if (object_swept_get (memory_to_object (self->ref)))
 549     return NULL;
 550
 551   return self->ref;
 552 #endif
 553   return NULL;
 554 }
 555
 556 void
 557 acogc_reference_assert_cleared (AcogcWeakReference p)
 558 {
 559   (void) p;
 560   ACOGC_ASSERT (!p->next && ! p->ref, "weak-reference %p not cleared", p);
 561 }
 562
 563 /*
 564   inline
 565   void *
 566   acogc_reference_get (AcogcReference self)
 567   {
 568     return self->ref;
 569   }
 570 */
 571
 572 /*
 573 // Local Variables:
 574 // mode: C
 575 // c-file-style: "gnu"
 576 // End:
 577 // arch-tag: 2a29f53b-906e-4025-bf90-8e12b4182474
 578 // end_of_file
 579 */