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 collection statistics (timing, global counter, etc)
  26
  27 /*
  28   root
  29 */
  30 void
  31 acogc_root_init (AcogcRoot self)
  32 {
  33   ACOGC_TRACE (2, "self %p", self);
  34   llist_init (&self->factories);
  35   self->collection_freq_avg = 0;
  36   self->allocation_counter = 0;
  37   self->stack = NULL;
  38   self->nomemhandler = NULL;
  39   self->nomemsupp = NULL;
  40   self->state = ACOGC_STATE_FIRST;
  41 }
  42
  43
  44 void
  45 acogc_root_erase (AcogcRoot self)
  46 {
  47   LLIST_FOREACH (&self->factories, fnode)
  48     {
  49       AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
  50       /* remove all roots (dynamic objects go to the alive list, uncollectable objects get dropped) */
  51       LLIST_WHILE_HEAD (&f->roots, i)
  52         acogc_removeroot (acogc_memory_from_object (LLIST_TO_STRUCTP (i, acogc_object, node)));
  53
  54       /* remove objects from the freelist */
  55       LLIST_WHILE_HEAD (&f->dead, i)
  56         {
  57           AcogcObject tmp = LLIST_TO_STRUCTP (i, acogc_object, node);
  58           ACOGC_TRACE (5, "erasing from dead %p", acogc_memory_from_object(tmp));
  59           if (tmp->factory->finalize)
  60             tmp->factory->finalize (acogc_memory_from_object (tmp));
  61           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
  62           llist_unlink (i);
  63           acogc_free (&tmp);
  64         }
  65
  66       /* remove objects in the alive list */
  67       LLIST_WHILE_HEAD (&f->alive, i)
  68         {
  69           AcogcObject tmp = LLIST_TO_STRUCTP (i, acogc_object, node);
  70           ACOGC_TRACE (2, "erasing from alive %p", acogc_memory_from_object(tmp));
  71           if (tmp->factory->finalize)
  72             tmp->factory->finalize (acogc_memory_from_object (tmp));
  73           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
  74           llist_unlink (i);
  75           acogc_free (&tmp);
  76         }
  77
  78       /* reset factory */
  79       f->objects_allocated = 0;
  80       f->objects_used = 0;
  81       f->was_free = 0;
  82     }
  83
  84   /* reset self */
  85   self->collection_freq_avg = 0;
  86   self->allocation_counter = 0;
  87   self->state = ACOGC_STATE_FIRST;
  88   self->stack = NULL;
  89 }
  90
  91 void
  92 acogc_root_collect (AcogcRoot self, enum acogc_freeing_policy pol)
  93 {
  94   /* we can short-circruit the collection we just did one and no user-code has been run */
  95   if (self->allocation_counter != 0 || pol >= ACOGC_COLLECT_FORCEALL || pol == ACOGC_COLLECT_DONTFREE)
  96     {
  97       /* calculate new average and reset stat */
  98       self->collection_freq_avg = (self->collection_freq_avg + self->allocation_counter) / 2 + 1;
  99       self->allocation_counter = 0;
 100       ACOGC_TRACE (2, "start collection %p, collection_freq %lu", self, self->collection_freq_avg);
 101
 102       /* move all previous alive objects to the tmp lists */
 103       LLIST_FOREACH (&self->factories, fnode)
 104         {
 105           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
 106           llist_insert_list_before (&f->alive, &f->tmp);
 107         }
 108
 109       ++self->state;
 110       // check for state overflow and reinit GC states (happens *very* rarely)
 111       if (self->state == ACOGC_STATE_LAST)
 112         {
 113           self->state = ACOGC_STATE_START;
 114           LLIST_FOREACH (&self->factories, fnode)
 115             {
 116               AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
 117               LLIST_FOREACH (&f->tmp, i)
 118                 LLIST_TO_STRUCTP (i, acogc_object, node)->state = ACOGC_STATE_FIRST;
 119               LLIST_FOREACH (&f->dead, i)
 120                 LLIST_TO_STRUCTP (i, acogc_object, node)->state = ACOGC_STATE_FIRST;
 121             }
 122         }
 123
 124       // and now go, marking is copying alive objects back to the alive list
 125       LLIST_FOREACH (&self->factories, fnode)
 126         {
 127           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
 128           f->objects_used = 0;
 129           LLIST_FOREACH (&f->roots, i)
 130             {
 131               ACOGC_TRACE (4, "root marker %p", acogc_memory_from_object (LLIST_TO_STRUCTP (i, acogc_object, node)));
 132               acogc_object_markreally (LLIST_TO_STRUCTP (i, acogc_object, node));
 133             }
 134         }
 135       // and for all root->stack references
 136       for (AcogcStack r = self->stack; r; r = r->prev)
 137         {
 138           ACOGC_TRACE (4, "stack marker %p", r->ptr);
 139           acogc_object_mark (r->ptr);
 140         }
 141
 142       /* move remaining cruft in the tmplist to the freelist */
 143       LLIST_FOREACH (&self->factories, fnode)
 144         {
 145           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
 146           llist_insert_list_before (&f->tmp, &f->dead);
 147         }
 148     }
 149
 150   /* now the freeing pass */
 151
 152   switch (pol)
 153     {
 154     case ACOGC_COLLECT_DONTFREE:
 155     case ACOGC_COLLECT_NORMAL:
 156     case ACOGC_COLLECT_FORCEMID:
 157     case ACOGC_COLLECT_FORCELOW:
 158     case ACOGC_COLLECT_FORCEALL:
 159       break;
 160     case ACOGC_COLLECT_USER1:
 161     case ACOGC_COLLECT_USER2:
 162     case ACOGC_COLLECT_USER3:
 163       if (self->nomemhandler)
 164         self->nomemhandler (self->nomemsupp, pol);
 165       return;
 166     case ACOGC_COLLECT_FAILED:
 167       abort();
 168     }
 169
 170   LLIST_FOREACH (&self->factories, fnode)
 171     {
 172       AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
 173
 174       unsigned free_limit = 0;
 175       switch (pol)
 176         {
 177         case ACOGC_COLLECT_DONTFREE:
 178           free_limit = 100;
 179           break;
 180         case ACOGC_COLLECT_NORMAL:
 181           free_limit = f->high_water;
 182           break;
 183         case ACOGC_COLLECT_FORCEMID:
 184           free_limit = (f->high_water + f->low_water)/2;
 185           break;
 186         case ACOGC_COLLECT_FORCELOW:
 187           free_limit = f->low_water;
 188           break;
 189         case ACOGC_COLLECT_FORCEALL:
 190           free_limit = 0;
 191           break;
 192         case ACOGC_COLLECT_USER1:
 193         case ACOGC_COLLECT_USER2:
 194         case ACOGC_COLLECT_USER3:
 195         case ACOGC_COLLECT_FAILED:
 196           ; /*unreached*/
 197         }
 198
 199       while (!llist_is_empty (&f->dead) && f->objects_allocated &&
 200              (f->was_free = 100 - (f->objects_used * 100 / f->objects_allocated)) > free_limit)
 201         {
 202           AcogcObject tmp = LLIST_TO_STRUCTP (llist_get_head (&f->dead), acogc_object, node);
 203
 204           ACOGC_TRACE (4, "freeing %p", acogc_memory_from_object (tmp));
 205
 206           if (tmp->factory->finalize)
 207             tmp->factory->finalize (acogc_memory_from_object (tmp));
 208
 209           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
 210
 211           llist_unlink (&tmp->node);
 212           acogc_free (&tmp);
 213           --f->objects_allocated;
 214         }
 215     }
 216
 217   ACOGC_TRACE (2, "collection complete");
 218 }
 219
 220
 221 /*
 222   factory
 223 */
 224 void
 225 acogc_factory_init (AcogcFactory self,
 226                     AcogcRoot root,
 227                     size_t size,
 228                     unsigned low_water,
 229                     unsigned high_water,
 230                     acogc_mark_func mark,
 231                     acogc_initize_func initize,
 232                     acogc_finalize_func finalize)
 233 {
 234   ACOGC_TRACE (1, "%p", self);
 235
 236   llist_init (&self->factories);
 237   llist_insert_tail (&root->factories, &self->factories);
 238
 239   llist_init (&self->roots);
 240   llist_init (&self->alive);
 241   llist_init (&self->dead);
 242   llist_init (&self->tmp);
 243
 244   self->root = root;
 245
 246   self->objects_allocated = self->objects_used = 0;
 247   self->was_free = 0;
 248   self->high_water = high_water;
 249   self->low_water = low_water;
 250   self->size = size;
 251   self->mark = mark;
 252   self->initize = initize;
 253   self->finalize = finalize;
 254 }
 255
 256
 257 void *
 258 acogc_factory_alloc (AcogcFactory self)
 259 {
 260   AcogcObject object;
 261
 262   ACOGC_TRACE (4, "self %p", self);
 263
 264   ++self->root->allocation_counter;
 265
 266   /* call a collection if the freelist is empty */
 267   if (llist_is_empty (&self->dead) &&
 268       (/* and there where enough free objects last time */
 269        (self->was_free > self->low_water) ||
 270        /* or we did more allocations so far than we did on average */
 271        self->root->allocation_counter > self->root->collection_freq_avg))
 272     {
 273       acogc_root_collect (self->root, ACOGC_COLLECT_NORMAL);
 274     }
 275
 276   if (llist_is_empty (&self->dead))
 277     {
 278       /* allocate a new object */
 279       object = NULL;
 280       acogc_alloc (&object, sizeof (acogc_object) + self->size, self->root);
 281
 282       llist_init (&object->node);
 283       llist_insert_tail (&self->alive, &object->node);
 284
 285       ++self->objects_allocated;
 286       ACOGC_TRACE (4, "from malloc %p", acogc_memory_from_object (object));
 287     }
 288   else
 289     {
 290       /* get one from free-queue */
 291       llist_insert_tail (&self->alive, llist_get_head (&self->dead));
 292
 293       object = LLIST_TO_STRUCTP(llist_get_tail (&self->alive), acogc_object, node);
 294
 295       if (self->finalize)
 296         self->finalize (acogc_memory_from_object (object));
 297
 298       acogc_object_weakref_invalidate (acogc_memory_from_object (object));
 299
 300       ACOGC_TRACE (4, "from freelist %p", acogc_memory_from_object (object));
 301     }
 302
 303   if (self->initize)
 304     self->initize (acogc_memory_from_object (object));
 305
 306   object->factory = self;
 307
 308   object->weakrefs = (AcogcWeakref)&object->weakrefs;
 309   object->state = self->root->state;
 310
 311   ++self->objects_used;
 312
 313   return acogc_memory_from_object (object);
 314 }
 315
 316 /*
 317   object
 318 */
 319 void
 320 acogc_object_markreally (AcogcObject self)
 321 {
 322   ACOGC_TRACE (4, "mark object %p, state %d", acogc_memory_from_object (self), self->state);
 323
 324   ACOGC_TRACE (0, "factory %p", self->factory);
 325
 326   ACOGC_ASSERT (self->state != self->factory->root->state, "marking already marked object %p", acogc_memory_from_object (self));
 327
 328   if (self->state >= ACOGC_STATE_FIRST)
 329     self->state = ACOGC_STATE_BUSY;
 330
 331   if (!self->factory->mark || self->factory->mark (acogc_memory_from_object (self)) == ACOGC_KEEP)
 332     {
 333       if (self->state <= ACOGC_STATE_ROOT || self->state == ACOGC_STATE_BUSY)
 334         /* is a dynamically allocated object */
 335         ++self->factory->objects_used;
 336
 337       if (self->state == ACOGC_STATE_BUSY)
 338         {
 339           /* is a collectable object, store it in the alive list */
 340           llist_insert_tail (&self->factory->alive, &self->node);
 341           self->state = self->factory->root->state;
 342         }
 343     }
 344 }
 345
 346 /* register a GC root object */
 347 void
 348 acogc_addroot (void* object)
 349 {
 350   ACOGC_TRACE (3, "object %p", object);
 351   if(!object)
 352     return;
 353
 354   AcogcObject o = acogc_object_from_memory (object);
 355
 356   if (o->state <= ACOGC_STATE_ROOT)
 357     {
 358       /* nested addroot */
 359       --o->state;
 360     }
 361   else
 362     {
 363       llist_insert_tail (&o->factory->roots, &o->node);
 364       if (o->state >= ACOGC_STATE_FIRST)
 365         o->state = ACOGC_STATE_ROOT;
 366     }
 367 }
 368
 369 /* unregister a GC root object, collectable objects go back to the alive list, uncollectable objects are reset and removed from the GC */
 370 void
 371 acogc_removeroot (void* object)
 372 {
 373   ACOGC_TRACE (3, "object %p", object);
 374   if(!object)
 375     return;
 376
 377   AcogcObject o = acogc_object_from_memory (object);
 378
 379   if (o->state < ACOGC_STATE_ROOT)
 380     /* dynamic object, nested */
 381     ++o->state;
 382   else
 383     {
 384       AcogcFactory factory = o->factory;
 385       if (o->state == ACOGC_STATE_ROOT)
 386         {
 387           /* dynamic object, removeroot */
 388           ACOGC_TRACE (3, "dynamic");
 389           llist_insert_tail (&factory->alive, &o->node);
 390           o->state = factory->root->state;
 391         }
 392       else
 393         {
 394           /* uncollectable object */
 395           ACOGC_TRACE (3, "uncollectable");
 396           if (o->state == ACOGC_STATE_UNCOLLECTABLE && factory->finalize)
 397             factory->finalize (object);
 398
 399           acogc_object_weakref_invalidate (object);
 400
 401           if (factory->initize)
 402             factory->initize (object);
 403
 404           llist_unlink (&o->node);
 405         }
 406     }
 407 }
 408
 409
 410 /*
 411   weakrefs
 412 */
 413 void
 414 acogc_weakref_link (AcogcWeakref self, void* o)
 415 {
 416   if (self->ref != o)
 417     {
 418       ACOGC_TRACE (4, "weaklink %p to %p", self, o);
 419       if(self->next)
 420         acogc_weakref_unlink (self);
 421
 422       self->ref = o;
 423
 424       AcogcObject object = acogc_object_from_memory (o);
 425       ACOGC_ASSERT (object->weakrefs, "weakref not initialized");
 426       self->next = object->weakrefs;
 427       object->weakrefs = self;
 428     }
 429 }
 430
 431 void
 432 acogc_weakref_unlink (AcogcWeakref self)
 433 {
 434   AcogcWeakref_ref prev = &self->next;
 435   AcogcWeakref i = self->next;
 436   if (i)
 437     {
 438       while (i != self)
 439         {
 440           ACOGC_ASSERT (i->next, "zero in weak cycle");
 441           prev = &i->next;
 442           i = i->next;
 443         }
 444       ACOGC_TRACE (4, "unlink %p from after %p, before %p", self, prev, self->next);
 445       *prev = self->next;
 446       self->ref = NULL;
 447       self->next = NULL;
 448     }
 449   else
 450     ACOGC_ASSERT (!self->ref, "weakref not linked");
 451 }
 452
 453 void
 454 acogc_object_weakref_invalidate (void* memory)
 455 {
 456   ACOGC_TRACE (3, "invalidate %p, weak %p", memory, acogc_object_from_memory(memory)->weakrefs);
 457   AcogcWeakref_ref object = &acogc_object_from_memory(memory)->weakrefs;
 458   if (*object)
 459     {
 460       while ((*object)->next != *object)
 461         {
 462           AcogcWeakref tmp = *object;
 463           ACOGC_TRACE (3, "invalidate %p, ref %p", tmp, tmp->ref);
 464           (*object) = (*object)->next;
 465           tmp->ref = NULL;
 466           tmp->next = NULL;
 467         }
 468     }
 469 }
 470
 471
 472 void *
 473 acogc_weakref_reinstget (AcogcWeakref self)
 474 {
 475   if (!self->ref)
 476     return NULL;
 477
 478   AcogcObject o = acogc_object_from_memory (self->ref);
 479
 480   if (o->state >= ACOGC_STATE_START && o->state < o->factory->root->state)
 481     {
 482       o->state = o->factory->root->state;
 483       llist_insert_tail (&o->factory->alive, &o->node);
 484       ++o->factory->objects_used;
 485     }
 486   return self->ref;
 487 }
 488
 489 void *
 490 acogc_weakref_get (AcogcWeakref self)
 491 {
 492   if (!self->ref)
 493     return NULL;
 494
 495   AcogcObject o = acogc_object_from_memory (self->ref);
 496
 497   if (o->state >= ACOGC_STATE_START && o->state < o->factory->root->state)
 498     return NULL;
 499
 500   return self->ref;
 501 }
 502
 503 void
 504 acogc_weakref_assert_cleared (AcogcWeakref p)
 505 {
 506   (void) p;
 507   ACOGC_ASSERT (!p->next && ! p->ref,
 508                 "weak-weakref %p not cleared at end of scope", p);
 509 }
 510
 511 /* malloc / free wrapers */
 512 void
 513 acogc_alloc_ (void ** addr, size_t size, AcogcRoot root)
 514 {
 515   void * ret;
 516   enum acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
 517
 518   /* alloc memory */
 519  retry:
 520   ret = realloc (*addr, size);
 521   if (!root && !ret)
 522     abort();
 523   if (!ret)
 524     {
 525       acogc_root_collect (root, pol);
 526       ++pol;
 527       goto retry;
 528     }
 529
 530   *addr = ret;
 531 }
 532
 533
 534 size_t
 535 acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcRoot root)
 536 {
 537   void * ret;
 538   enum acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
 539
 540   size_t n;
 541   for (n = actual>16 ? actual : 16; n <= needed; n += (n>>1)); /*n = n * 1.5*/
 542
 543  retry:
 544   ret = realloc (*addr, n);
 545   if (!ret)
 546     {
 547       n = needed;
 548       acogc_root_collect (root, pol);
 549       ++pol;
 550       goto retry;
 551     }
 552
 553   *addr = ret;
 554
 555   return n;
 556 }
 557
 558
 559 void
 560 acogc_free_ (void ** addr)
 561 {
 562   free (*addr);
 563   *addr = NULL;
 564 }
 565
 566 /*
 567   assertion for cleanup
 568 */
 569 void
 570 acogc_assert_stackframeleft (AcogcStack_ref p)
 571 {
 572   assert (*p == (AcogcStack) p);
 573   (void) p;
 574 }
 575
 576 /*
 577 // Local Variables:
 578 // mode: C
 579 // c-file-style: "gnu"
 580 // End:
 581 // arch-tag: 2a29f53b-906e-4025-bf90-8e12b4182474
 582 // end_of_file
 583 */