6d82a70b3339cad778c6b31f60c61e8ce3196956
[acogc] / 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 // TODO collection statistics (timing, global counter, etc)
25
26 /* nobug init*/
27 NOBUG_DEFINE_FLAG(acogc);
28 NOBUG_DEFINE_FLAG(acogc_mark);
29 NOBUG_DEFINE_FLAG(acogc_collect);
30 NOBUG_DEFINE_FLAG(acogc_alloc);
31 NOBUG_DEFINE_FLAG(acogc_weak);
32
33 void acogc_nobug_init()
34 {
35   NOBUG_INIT_FLAG(acogc);
36   NOBUG_INIT_FLAG(acogc_mark);
37   NOBUG_INIT_FLAG(acogc_collect);
38   NOBUG_INIT_FLAG(acogc_alloc);
39   NOBUG_INIT_FLAG(acogc_weak);
40 }
41
42 /*
43   root
44 */
45 void
46 acogc_root_init (AcogcRoot self)
47 {
48   REQUIRE (self);
49   NOTICE (acogc, "self %p", self);
50
51   llist_init (&self->factories);
52   self->allocation_counter = 0;
53   self->collection_freq = 32;
54   self->stack = NULL;
55   self->last = NULL;
56   self->nomemhandler = NULL;
57   self->nomemsupp = NULL;
58   self->state = ACOGC_STATE_FIRST;
59 }
60
61
62 void
63 acogc_root_erase (AcogcRoot self)
64 {
65   REQUIRE (self);
66   NOTICE (acogc, "self %p", self);
67
68   LLIST_FOREACH (&self->factories, fnode)
69     {
70       AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
71       /* remove all roots (dynamic objects go to the alive list, uncollectable objects get dropped) */
72       LLIST_WHILE_HEAD (&f->roots, i)
73         acogc_removeroot (acogc_memory_from_object (LLIST_TO_STRUCTP (i, acogc_object, node)));
74
75       /* remove objects from the freelist */
76       LLIST_WHILE_HEAD (&f->dead, i)
77         {
78           AcogcObject tmp = LLIST_TO_STRUCTP (i, acogc_object, node);
79           TRACE_DBG (acogc, "erasing from dead %p", acogc_memory_from_object(tmp));
80           if (tmp->factory->finalize)
81             tmp->factory->finalize (acogc_memory_from_object (tmp));
82           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
83           llist_unlink (i);
84           acogc_free (&tmp);
85         }
86
87       /* remove objects in the alive list */
88       LLIST_WHILE_HEAD (&f->alive, i)
89         {
90           AcogcObject tmp = LLIST_TO_STRUCTP (i, acogc_object, node);
91           TRACE_DBG (acogc, "erasing from alive %p", acogc_memory_from_object(tmp));
92           if (tmp->factory->finalize)
93             tmp->factory->finalize (acogc_memory_from_object (tmp));
94           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
95           llist_unlink (i);
96           acogc_free (&tmp);
97         }
98
99       /* reset factory */
100       f->objects_allocated = 0;
101       f->objects_used = 0;
102       f->objects_new = 0;
103     }
104
105   /* reset self */
106   self->allocation_counter = 0;
107   self->state = ACOGC_STATE_FIRST;
108   self->stack = NULL;
109 }
110
111 void
112 acogc_root_collect (AcogcRoot self, acogc_freeing_policy pol)
113 {
114   REQUIRE (self);
115   NOTICE (acogc_collect, "self %p, policy %d", self, pol);
116
117   /* we can short-circruit the collection we just did one and no user-code has been run */
118   if (self->allocation_counter != 0 || pol > ACOGC_COLLECT_USER1 || pol == ACOGC_COLLECT_DONTFREE)
119     {
120       self->allocation_counter = 0;
121
122       /* move all previous alive objects to the tmp lists */
123       LLIST_FOREACH (&self->factories, fnode)
124         {
125           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
126           llist_insert_list_before (&f->alive, &f->tmp);
127         }
128
129       ++self->state;
130       // check for state overflow and reinit GC states (happens *very* rarely, once every 2^31 collections at worst)
131       if (self->state == ACOGC_STATE_LAST)
132         {
133           NOTICE (acogc_collect, "gc state overflow, recycle");
134           self->state = ACOGC_STATE_START;
135           LLIST_FOREACH (&self->factories, fnode)
136             {
137               AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
138               LLIST_FOREACH (&f->tmp, i)
139                 LLIST_TO_STRUCTP (i, acogc_object, node)->state = ACOGC_STATE_FIRST;
140               LLIST_FOREACH (&f->dead, i)
141                 LLIST_TO_STRUCTP (i, acogc_object, node)->state = ACOGC_STATE_FIRST;
142             }
143         }
144
145       // and now go, marking is copying alive objects back to the alive list
146       LLIST_FOREACH (&self->factories, fnode)
147         {
148           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
149           TRACE (acogc_collect, "marking roots in %s", f->factory_name);
150           f->objects_used = 0;
151           f->objects_new = 0;
152           LLIST_FOREACH (&f->roots, i)
153             {
154               TRACE_DBG (acogc_collect, "root marker %p",
155                        acogc_memory_from_object (LLIST_TO_STRUCTP (i, acogc_object, node)));
156               acogc_object_markreally (LLIST_TO_STRUCTP (i, acogc_object, node));
157               ++f->objects_used;
158             }
159         }
160
161       // and for all root->stack references
162       TRACE (acogc_collect, "marking stack references");
163       for (AcogcStack r = self->stack; r; r = r->prev)
164         {
165           ASSERT (r != r->prev, "stack corruption, maybe ACOGC_STACK_PTR redefinition in a loop");
166           TRACE_DBG (acogc_collect, "stack marker %p", r->ptr);
167           acogc_object_mark (r->ptr);
168         }
169
170       /* move remaining cruft in the tmplist to the freelist */
171       LLIST_FOREACH (&self->factories, fnode)
172         {
173           AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
174           NOTICE (acogc_collect, "collected %d %s", llist_count (&f->tmp), f->factory_name);
175           llist_insert_list_before (&f->tmp, &f->dead);
176         }
177     }
178
179   /* now the freeing pass */
180
181   switch (pol)
182     {
183     case ACOGC_COLLECT_DONTFREE:
184     case ACOGC_COLLECT_NORMAL:
185     case ACOGC_COLLECT_FORCEMID:
186     case ACOGC_COLLECT_FORCELOW:
187     case ACOGC_COLLECT_FORCEALL:
188       break;
189     case ACOGC_COLLECT_USER1:
190     case ACOGC_COLLECT_USER2:
191     case ACOGC_COLLECT_USER3:
192       if (self->nomemhandler)
193         self->nomemhandler (self->nomemsupp, pol);
194       return;
195     case ACOGC_COLLECT_FAILED:
196       abort();
197     }
198
199   unsigned long had_objects = 0;
200   unsigned long freed_objects = 0;
201
202   LLIST_FOREACH (&self->factories, fnode)
203     {
204       AcogcFactory f = LLIST_TO_STRUCTP (fnode, acogc_factory, factories);
205
206       had_objects += f->objects_allocated;
207
208       unsigned keep_limit = 0;
209       switch (pol)
210         {
211         case ACOGC_COLLECT_DONTFREE:
212           keep_limit = 100;
213           break;
214         case ACOGC_COLLECT_NORMAL:
215           keep_limit = f->high_water;
216           break;
217         case ACOGC_COLLECT_FORCEMID:
218           keep_limit = (f->high_water + f->low_water)/2;
219           break;
220         case ACOGC_COLLECT_FORCELOW:
221           keep_limit = f->low_water;
222           break;
223         case ACOGC_COLLECT_FORCEALL:
224           keep_limit = 0;
225           break;
226         case ACOGC_COLLECT_USER1:
227         case ACOGC_COLLECT_USER2:
228         case ACOGC_COLLECT_USER3:
229         case ACOGC_COLLECT_FAILED:
230           NOTREACHED;
231         }
232
233       while (!llist_is_empty (&f->dead) && (f->objects_used * 100 / f->objects_allocated > keep_limit))
234         {
235           ++freed_objects;
236
237           INFO (acogc_collect, "free rate: %lu", f->objects_used * 100 / f->objects_allocated);
238           AcogcObject tmp = LLIST_TO_STRUCTP (llist_get_head (&f->dead), acogc_object, node);
239
240           TRACE_DBG (acogc_collect, "freeing %p", acogc_memory_from_object (tmp));
241
242           if (tmp->factory->finalize)
243             tmp->factory->finalize (acogc_memory_from_object (tmp));
244
245           acogc_object_weakref_invalidate (acogc_memory_from_object (tmp));
246
247           llist_unlink (&tmp->node);
248           acogc_free (&tmp);
249           --f->objects_allocated;
250         }
251       NOTICE (acogc_collect, "after freeing: allocated %lu, used %lu, ", f->objects_allocated,f->objects_used);
252     }
253
254   if (freed_objects > 16)
255     {
256       self->collection_freq = (self->collection_freq * (had_objects-freed_objects) / had_objects)/2 +1;
257       TRACE (acogc_collect, "decreased collection freq: %lu", self->collection_freq);
258     }
259
260   NOTICE_DBG (acogc_collect, "collection complete");
261 }
262
263
264 /*
265   factory
266 */
267 void
268 acogc_factory_init (AcogcFactory self,
269                     AcogcRoot root,
270                     size_t size,
271                     unsigned low_water,
272                     unsigned high_water,
273                     acogc_mark_func mark,
274                     acogc_initize_func initize,
275                     acogc_finalize_func finalize)
276 {
277   REQUIRE (self);
278   REQUIRE (root);
279
280   REQUIRE (size > 0);
281   REQUIRE (low_water < 100);
282   REQUIRE (high_water < 100);
283   REQUIRE (low_water <= high_water);
284
285   NOTICE (acogc, "self %p", self);
286
287   llist_init (&self->factories);
288   llist_insert_tail (&root->factories, &self->factories);
289
290   llist_init (&self->roots);
291   llist_init (&self->alive);
292   llist_init (&self->dead);
293   llist_init (&self->tmp);
294
295   self->root = root;
296
297   self->objects_allocated = 0;
298   self->objects_used = 0;
299   self->objects_new = 0;
300   self->high_water = high_water;
301   self->low_water = low_water;
302   self->size = size;
303   self->mark = mark;
304   self->initize = initize;
305   self->finalize = finalize;
306   self->factory_name = NULL;
307 }
308
309
310 void *
311 acogc_factory_alloc (AcogcFactory self)
312 {
313   REQUIRE (self);
314   AcogcObject object;
315
316   INFO (acogc_alloc);
317
318   ++self->root->allocation_counter;
319
320   /* maybe call a collection if the freelist is empty */
321   if (llist_is_empty (&self->dead) &&
322       self->root->allocation_counter > self->root->collection_freq)
323     {
324       acogc_root_collect (self->root, ACOGC_COLLECT_NORMAL);
325       if (self->objects_allocated &&
326           100 - (self->objects_used * 100 / self->objects_allocated) < self->low_water)
327         {
328           // collected less than low_water, increase collection_freq and allocate
329           self->root->collection_freq = self->root->collection_freq*3/2 +1;
330           TRACE (acogc_collect, "increased collection freq: %lu", self->root->collection_freq);
331           goto allocate;
332         }
333     }
334
335   if (llist_is_empty (&self->dead))
336     {
337       /* allocate a new object */
338     allocate:
339       object = NULL;
340       acogc_alloc (&object, sizeof (acogc_object) + self->size, self->root);
341
342       llist_init (&object->node);
343       llist_insert_tail (&self->alive, &object->node);
344
345       ++self->objects_allocated;
346       TRACE_DBG (acogc_alloc, "from malloc %p", acogc_memory_from_object (object));
347     }
348   else
349     {
350       /* get one from free-queue */
351       llist_insert_tail (&self->alive, llist_get_head (&self->dead));
352
353       object = LLIST_TO_STRUCTP(llist_get_tail (&self->alive), acogc_object, node);
354
355       if (self->finalize)
356         self->finalize (acogc_memory_from_object (object));
357
358       acogc_object_weakref_invalidate (acogc_memory_from_object (object));
359
360       TRACE_DBG (acogc_alloc, "from freelist %p", acogc_memory_from_object (object));
361     }
362
363   if (self->initize)
364     self->initize (acogc_memory_from_object (object));
365
366   object->factory = self;
367
368   object->weakrefs = (AcogcWeakref)&object->weakrefs;
369   object->state = self->root->state;
370
371   ++self->objects_new;
372   ++self->objects_used;
373
374   return acogc_memory_from_object (object);
375 }
376
377 /*
378   object
379 */
380 acogc_mark_result
381 acogc_object_markreally (AcogcObject self)
382 {
383   REQUIRE (self);
384
385  tailcall:
386   TRACE (acogc_mark, "mark object %p, state %d", acogc_memory_from_object (self), self->state);
387
388   REQUIRE (self->state != self->factory->root->state, "marking already marked object %p", acogc_memory_from_object (self));
389
390   if (!self->factory->mark || self->factory->mark (acogc_memory_from_object (self)) == ACOGC_KEEP)
391     {
392       TRACE_DBG (acogc_mark, "keep object %p", acogc_memory_from_object (self));
393       if (self->state >= ACOGC_STATE_BUSY)
394         {
395           /* is a dynamically allocated object */
396           ++self->factory->objects_used;
397
398           /* is a collectable object, store it in the alive list */
399           llist_insert_tail (&self->factory->alive, &self->node);
400           self->state = self->factory->root->state;
401         }
402
403       if (self->factory->root->last)
404         {
405           self = self->factory->root->last;
406           self->factory->root->last = NULL;
407           TRACE (acogc_mark, "tailcall");
408           goto tailcall;
409         }
410       return ACOGC_KEEP;
411     }
412   return ACOGC_COLLECT;
413 }
414
415 /* register a GC root object */
416 void
417 acogc_addroot (void* object)
418 {
419   REQUIRE (object);
420   TRACE (acogc, "object: %p", object);
421   //if(!object)
422   //  return;
423
424   AcogcObject o = acogc_object_from_memory (object);
425
426   if (o->state <= ACOGC_STATE_ROOT)
427     {
428       /* nested addroot */
429       --o->state;
430       INFO_DBG (acogc, "object: %p already root, nested %d", object, -o->state);
431     }
432   else
433     {
434       llist_insert_tail (&o->factory->roots, &o->node);
435       if (o->state >= ACOGC_STATE_FIRST)
436         o->state = ACOGC_STATE_ROOT;
437     }
438 }
439
440 /* unregister a GC root object, collectable objects go back to the alive list, uncollectable objects are reset and removed from the GC */
441 void
442 acogc_removeroot (void* object)
443 {
444   REQUIRE (object);
445
446   TRACE (acogc, "object: %p", object);
447   //if(!object)
448   //  return;
449
450   AcogcObject o = acogc_object_from_memory (object);
451
452   if (o->state < ACOGC_STATE_ROOT)
453     {
454       /* dynamic object, nested */
455       ++o->state;
456       INFO_DBG (acogc, "object: %p still root, nested %d", object, -o->state);
457     }
458   else
459     {
460       AcogcFactory factory = o->factory;
461       if (o->state == ACOGC_STATE_ROOT)
462         {
463           /* dynamic object, removeroot */
464           TRACE_DBG (acogc, " ..dynamic, removed from root");
465           llist_insert_tail (&factory->alive, &o->node);
466           o->state = factory->root->state;
467         }
468       else
469         {
470           /* uncollectable object */
471           TRACE_DBG (acogc, " ..uncollectable, removed from root");
472           if (o->state == ACOGC_STATE_UNCOLLECTABLE && factory->finalize)
473             factory->finalize (object);
474
475           acogc_object_weakref_invalidate (object);
476
477           if (factory->initize)
478             factory->initize (object);
479
480           llist_unlink (&o->node);
481         }
482     }
483 }
484
485
486 /*
487   weakrefs
488 */
489 void
490 acogc_weakref_link (AcogcWeakref self, void* o)
491 {
492   REQUIRE (self);
493   REQUIRE (o);
494
495   TRACE (acogc_weak, "%p to %p", self, o);
496
497   if (self->ref != o)
498     {
499       NOTICE (acogc_weak, "already linked together");
500       if(self->next)
501         {
502           NOTICE (acogc_weak, "weakref linked to another object");
503           acogc_weakref_unlink (self);
504         }
505
506       self->ref = o;
507
508       AcogcObject object = acogc_object_from_memory (o);
509       ASSERT (object->weakrefs, "weakref not initialized");
510       self->next = object->weakrefs;
511       object->weakrefs = self;
512     }
513 }
514
515 void
516 acogc_weakref_unlink (AcogcWeakref self)
517 {
518   REQUIRE (self);
519
520   TRACE (acogc_weak, "%p", self);
521
522   AcogcWeakref_ref prev = &self->next;
523   AcogcWeakref i = self->next;
524   if (i)
525     {
526       while (i != self)
527         {
528           ASSERT (i->next, "zero in weak cycle");
529           prev = &i->next;
530           i = i->next;
531         }
532       TRACE_DBG (acogc_weak, "unlink %p from after %p, before %p", self, prev, self->next);
533       *prev = self->next;
534       self->ref = NULL;
535       self->next = NULL;
536     }
537   else
538     {
539       ASSERT (!self->ref, "weakref not linked");
540     }
541 }
542
543 void
544 acogc_object_weakref_invalidate (void* memory)
545 {
546   REQUIRE (memory);
547   TRACE (acogc_weak, "%p, weak %p", memory, acogc_object_from_memory(memory)->weakrefs);
548
549   AcogcWeakref_ref object = &acogc_object_from_memory(memory)->weakrefs;
550   if (*object)
551     {
552       while ((*object)->next != *object)
553         {
554           AcogcWeakref tmp = *object;
555           TRACE_DBG (acogc_weak, "invalidate %p, ref %p", tmp, tmp->ref);
556           (*object) = (*object)->next;
557           tmp->ref = NULL;
558           tmp->next = NULL;
559         }
560     }
561 }
562
563
564 void *
565 acogc_weakref_reinstget (AcogcWeakref self)
566 {
567   REQUIRE (self);
568   TRACE (acogc_weak, "%p", self);
569
570   if (!self->ref)
571     {
572       TRACE_DBG (acogc_weak, "reinst miss %p", self);
573       return NULL;
574     }
575
576   AcogcObject o = acogc_object_from_memory (self->ref);
577
578   if (o->state >= ACOGC_STATE_FIRST && o->state < o->factory->root->state)
579     {
580       TRACE_DBG (acogc_weak, "reinst hit %p, object %p", self, self->ref);
581       o->state = o->factory->root->state;
582       llist_insert_tail (&o->factory->alive, &o->node);
583       ++o->factory->objects_used;
584     }
585   return self->ref;
586 }
587
588 void *
589 acogc_weakref_get (AcogcWeakref self)
590 {
591   REQUIRE (self);
592   TRACE (acogc_weak, "%p", self);
593
594   if (!self->ref)
595     return NULL;
596
597   AcogcObject o = acogc_object_from_memory (self->ref);
598
599   if (o->state >= ACOGC_STATE_FIRST && o->state < o->factory->root->state)
600     {
601       INFO_DBG (acogc_weak, "already invalidated");
602       return NULL;
603     }
604
605   INFO_DBG (acogc_weak, "resolved %p", self->ref);
606
607   return self->ref;
608 }
609
610 void
611 acogc_weakref_assert_cleared (AcogcWeakref p)
612 {
613   REQUIRE (p);
614   (void) p;
615   ASSERT (!p->next && ! p->ref, "weak-weakref %p not cleared at end of scope", p);
616 }
617
618 /* malloc / free wrapers */
619 void
620 acogc_alloc_ (void ** addr, size_t size, AcogcRoot root)
621 {
622   REQUIRE (addr);
623   REQUIRE (size > 0);
624   TRACE (acogc_alloc);
625
626   void * ret;
627   acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
628
629   /* alloc memory */
630  retry:
631   ret = realloc (*addr, size);
632
633   if (!ret)
634     {
635       if (root)
636         {
637           acogc_root_collect (root, pol);
638           ++pol;
639           goto retry;
640         }
641       else
642         {
643           ERROR (NOBUG_ON, "out of memory");
644           abort();
645         }
646     }
647
648   *addr = ret;
649 }
650
651
652 size_t
653 acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcRoot root)
654 {
655   REQUIRE (addr);
656   REQUIRE (actual > 0);
657   REQUIRE (needed > 0);
658   TRACE (acogc_alloc);
659
660   void * ret;
661   acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
662
663   size_t n;
664   for (n = actual>16 ? actual : 16; n <= needed; n += (n>>1)); /*n = n * 1.5*/
665
666  retry:
667   PLANNED("realloc only 'needed' when memory is low");
668   ret = realloc (*addr, n);
669   if (!ret)
670     {
671       if (root)
672         {
673           n = needed;
674           acogc_root_collect (root, pol);
675           ++pol;
676           goto retry;
677         }
678       else
679         {
680           ERROR (NOBUG_ON, "out of memory");
681           abort();
682         }
683     }
684
685   *addr = ret;
686
687   return n;
688 }
689
690
691 void
692 acogc_free_ (void ** addr)
693 {
694   REQUIRE (addr);
695   TRACE (acogc_alloc);
696   free (*addr);
697   *addr = NULL;
698 }
699
700 /*
701   assertion for cleanup
702 */
703 void
704 acogc_assert_stackframeleft (AcogcStack_ref p)
705 {
706   REQUIRE (p);
707   REQUIRE (*p);
708   ASSERT (*p == (AcogcStack) p);
709   (void) p;
710 }
711
712 /*
713 // Local Variables:
714 // mode: C
715 // c-file-style: "gnu"
716 // End:
717 // arch-tag: 2a29f53b-906e-4025-bf90-8e12b4182474
718 // end_of_file
719 */