add typecheck by string literal
[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->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->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                     const char* name)
277 {
278   REQUIRE (self);
279   REQUIRE (root);
280
281   REQUIRE (size > 0);
282   REQUIRE (low_water < 100);
283   REQUIRE (high_water < 100);
284   REQUIRE (low_water <= high_water);
285
286   NOTICE (acogc, "self %p", self);
287
288   llist_init (&self->factories);
289   llist_insert_tail (&root->factories, &self->factories);
290
291   llist_init (&self->roots);
292   llist_init (&self->alive);
293   llist_init (&self->dead);
294   llist_init (&self->tmp);
295
296   self->root = root;
297
298   self->objects_allocated = 0;
299   self->objects_used = 0;
300   self->objects_new = 0;
301   self->high_water = high_water;
302   self->low_water = low_water;
303   self->size = size;
304   self->mark = mark;
305   self->initize = initize;
306   self->finalize = finalize;
307   self->name = name;
308 }
309
310
311 void *
312 acogc_factory_alloc (AcogcFactory self)
313 {
314   REQUIRE (self);
315   AcogcObject object;
316
317   INFO (acogc_alloc);
318
319   ++self->root->allocation_counter;
320
321   /* maybe call a collection if the freelist is empty */
322   if (llist_is_empty (&self->dead) &&
323       self->root->allocation_counter > self->root->collection_freq)
324     {
325       acogc_root_collect (self->root, ACOGC_COLLECT_NORMAL);
326       if (self->objects_allocated &&
327           100 - (self->objects_used * 100 / self->objects_allocated) < self->low_water)
328         {
329           // collected less than low_water, increase collection_freq and allocate
330           self->root->collection_freq = self->root->collection_freq*3/2 +1;
331           TRACE (acogc_collect, "increased collection freq: %lu", self->root->collection_freq);
332           goto allocate;
333         }
334     }
335
336   if (llist_is_empty (&self->dead))
337     {
338       /* allocate a new object */
339     allocate:
340       object = NULL;
341       acogc_alloc (&object, sizeof (acogc_object) + self->size, self->root);
342
343       llist_init (&object->node);
344       llist_insert_tail (&self->alive, &object->node);
345
346       ++self->objects_allocated;
347       TRACE_DBG (acogc_alloc, "from malloc %p", acogc_memory_from_object (object));
348     }
349   else
350     {
351       /* get one from free-queue */
352       llist_insert_tail (&self->alive, llist_get_head (&self->dead));
353
354       object = LLIST_TO_STRUCTP(llist_get_tail (&self->alive), acogc_object, node);
355
356       if (self->finalize)
357         self->finalize (acogc_memory_from_object (object));
358
359       acogc_object_weakref_invalidate (acogc_memory_from_object (object));
360
361       TRACE_DBG (acogc_alloc, "from freelist %p", acogc_memory_from_object (object));
362     }
363
364   if (self->initize)
365     self->initize (acogc_memory_from_object (object));
366
367   object->factory = self;
368
369   object->weakrefs = (AcogcWeakref)&object->weakrefs;
370   object->state = self->root->state;
371
372   ++self->objects_new;
373   ++self->objects_used;
374
375   return acogc_memory_from_object (object);
376 }
377
378 /*
379   object
380 */
381 acogc_mark_result
382 acogc_object_markreally (AcogcObject self)
383 {
384   REQUIRE (self);
385
386  tailcall:
387   TRACE (acogc_mark, "mark object %p, state %d", acogc_memory_from_object (self), self->state);
388
389   REQUIRE (self->state != self->factory->root->state, "marking already marked object %p", acogc_memory_from_object (self));
390
391   if (!self->factory->mark || self->factory->mark (acogc_memory_from_object (self)) == ACOGC_KEEP)
392     {
393       TRACE_DBG (acogc_mark, "keep object %p", acogc_memory_from_object (self));
394       if (self->state >= ACOGC_STATE_BUSY)
395         {
396           /* is a dynamically allocated object */
397           ++self->factory->objects_used;
398
399           /* is a collectable object, store it in the alive list */
400           llist_insert_tail (&self->factory->alive, &self->node);
401           self->state = self->factory->root->state;
402         }
403
404       if (self->factory->root->last)
405         {
406           self = self->factory->root->last;
407           self->factory->root->last = NULL;
408           TRACE (acogc_mark, "tailcall");
409           goto tailcall;
410         }
411       return ACOGC_KEEP;
412     }
413   return ACOGC_COLLECT;
414 }
415
416 /* register a GC root object */
417 void
418 acogc_addroot (void* object)
419 {
420   REQUIRE (object);
421   TRACE (acogc, "object: %p", object);
422   //if(!object)
423   //  return;
424
425   AcogcObject o = acogc_object_from_memory (object);
426
427   if (o->state <= ACOGC_STATE_ROOT)
428     {
429       /* nested addroot */
430       --o->state;
431       INFO_DBG (acogc, "object: %p already root, nested %d", object, -o->state);
432     }
433   else
434     {
435       llist_insert_tail (&o->factory->roots, &o->node);
436       if (o->state >= ACOGC_STATE_FIRST)
437         o->state = ACOGC_STATE_ROOT;
438     }
439 }
440
441 /* unregister a GC root object, collectable objects go back to the alive list, uncollectable objects are reset and removed from the GC */
442 void
443 acogc_removeroot (void* object)
444 {
445   REQUIRE (object);
446
447   TRACE (acogc, "object: %p", object);
448   //if(!object)
449   //  return;
450
451   AcogcObject o = acogc_object_from_memory (object);
452
453   if (o->state < ACOGC_STATE_ROOT)
454     {
455       /* dynamic object, nested */
456       ++o->state;
457       INFO_DBG (acogc, "object: %p still root, nested %d", object, -o->state);
458     }
459   else
460     {
461       AcogcFactory factory = o->factory;
462       if (o->state == ACOGC_STATE_ROOT)
463         {
464           /* dynamic object, removeroot */
465           TRACE_DBG (acogc, " ..dynamic, removed from root");
466           llist_insert_tail (&factory->alive, &o->node);
467           o->state = factory->root->state;
468         }
469       else
470         {
471           /* uncollectable object */
472           TRACE_DBG (acogc, " ..uncollectable, removed from root");
473           if (o->state == ACOGC_STATE_UNCOLLECTABLE && factory->finalize)
474             factory->finalize (object);
475
476           acogc_object_weakref_invalidate (object);
477
478           if (factory->initize)
479             factory->initize (object);
480
481           llist_unlink (&o->node);
482         }
483     }
484 }
485
486
487 /*
488   weakrefs
489 */
490 void
491 acogc_weakref_link (AcogcWeakref self, void* o)
492 {
493   REQUIRE (self);
494   REQUIRE (o);
495
496   TRACE (acogc_weak, "%p to %p", self, o);
497
498   if (self->ref != o)
499     {
500       NOTICE (acogc_weak, "already linked together");
501       if(self->next)
502         {
503           NOTICE (acogc_weak, "weakref linked to another object");
504           acogc_weakref_unlink (self);
505         }
506
507       self->ref = o;
508
509       AcogcObject object = acogc_object_from_memory (o);
510       ASSERT (object->weakrefs, "weakref not initialized");
511       self->next = object->weakrefs;
512       object->weakrefs = self;
513     }
514 }
515
516 void
517 acogc_weakref_unlink (AcogcWeakref self)
518 {
519   REQUIRE (self);
520
521   TRACE (acogc_weak, "%p", self);
522
523   AcogcWeakref_ref prev = &self->next;
524   AcogcWeakref i = self->next;
525   if (i)
526     {
527       while (i != self)
528         {
529           ASSERT (i->next, "zero in weak cycle");
530           prev = &i->next;
531           i = i->next;
532         }
533       TRACE_DBG (acogc_weak, "unlink %p from after %p, before %p", self, prev, self->next);
534       *prev = self->next;
535       self->ref = NULL;
536       self->next = NULL;
537     }
538   else
539     {
540       ASSERT (!self->ref, "weakref not linked");
541     }
542 }
543
544 void
545 acogc_object_weakref_invalidate (void* memory)
546 {
547   REQUIRE (memory);
548   TRACE (acogc_weak, "%p, weak %p", memory, acogc_object_from_memory(memory)->weakrefs);
549
550   AcogcWeakref_ref object = &acogc_object_from_memory(memory)->weakrefs;
551   if (*object)
552     {
553       while ((*object)->next != *object)
554         {
555           AcogcWeakref tmp = *object;
556           TRACE_DBG (acogc_weak, "invalidate %p, ref %p", tmp, tmp->ref);
557           (*object) = (*object)->next;
558           tmp->ref = NULL;
559           tmp->next = NULL;
560         }
561     }
562 }
563
564
565 void *
566 acogc_weakref_reinstget (AcogcWeakref self)
567 {
568   REQUIRE (self);
569   TRACE (acogc_weak, "%p", self);
570
571   if (!self->ref)
572     {
573       TRACE_DBG (acogc_weak, "reinst miss %p", self);
574       return NULL;
575     }
576
577   AcogcObject o = acogc_object_from_memory (self->ref);
578
579   if (o->state >= ACOGC_STATE_FIRST && o->state < o->factory->root->state)
580     {
581       TRACE_DBG (acogc_weak, "reinst hit %p, object %p", self, self->ref);
582       o->state = o->factory->root->state;
583       llist_insert_tail (&o->factory->alive, &o->node);
584       ++o->factory->objects_used;
585     }
586   return self->ref;
587 }
588
589 void *
590 acogc_weakref_get (AcogcWeakref self)
591 {
592   REQUIRE (self);
593   TRACE (acogc_weak, "%p", self);
594
595   if (!self->ref)
596     return NULL;
597
598   AcogcObject o = acogc_object_from_memory (self->ref);
599
600   if (o->state >= ACOGC_STATE_FIRST && o->state < o->factory->root->state)
601     {
602       INFO_DBG (acogc_weak, "already invalidated");
603       return NULL;
604     }
605
606   INFO_DBG (acogc_weak, "resolved %p", self->ref);
607
608   return self->ref;
609 }
610
611 void
612 acogc_weakref_assert_cleared (AcogcWeakref p)
613 {
614   REQUIRE (p);
615   (void) p;
616   ASSERT (!p->next && ! p->ref, "weak-weakref %p not cleared at end of scope", p);
617 }
618
619 /* malloc / free wrapers */
620 void
621 acogc_alloc_ (void ** addr, size_t size, AcogcRoot root)
622 {
623   REQUIRE (addr);
624   REQUIRE (size > 0);
625   TRACE (acogc_alloc);
626
627   void * ret;
628   acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
629
630   /* alloc memory */
631  retry:
632   ret = realloc (*addr, size);
633
634   if (!ret)
635     {
636       if (root)
637         {
638           acogc_root_collect (root, pol);
639           ++pol;
640           goto retry;
641         }
642       else
643         {
644           ERROR (NOBUG_ON, "out of memory");
645           abort();
646         }
647     }
648
649   *addr = ret;
650 }
651
652
653 size_t
654 acogc_reserve_ (void ** addr, size_t actual, size_t needed, AcogcRoot root)
655 {
656   REQUIRE (addr);
657   REQUIRE (actual > 0);
658   REQUIRE (needed > 0);
659   TRACE (acogc_alloc);
660
661   void * ret;
662   acogc_freeing_policy pol = ACOGC_COLLECT_NORMAL;
663
664   size_t n;
665   for (n = actual>16 ? actual : 16; n <= needed; n += (n>>1)); /*n = n * 1.5*/
666
667  retry:
668   PLANNED("realloc only 'needed' when memory is low");
669   ret = realloc (*addr, n);
670   if (!ret)
671     {
672       if (root)
673         {
674           n = needed;
675           acogc_root_collect (root, pol);
676           ++pol;
677           goto retry;
678         }
679       else
680         {
681           ERROR (NOBUG_ON, "out of memory");
682           abort();
683         }
684     }
685
686   *addr = ret;
687
688   return n;
689 }
690
691
692 void
693 acogc_free_ (void ** addr)
694 {
695   REQUIRE (addr);
696   TRACE (acogc_alloc);
697   free (*addr);
698   *addr = NULL;
699 }
700
701 /*
702   assertion for cleanup
703 */
704 void
705 acogc_assert_stackframeleft (AcogcStack_ref p)
706 {
707   REQUIRE (p);
708   REQUIRE (*p);
709   ASSERT (*p == (AcogcStack) p);
710   (void) p;
711 }
712
713 /*
714 // Local Variables:
715 // mode: C
716 // c-file-style: "gnu"
717 // End:
718 // arch-tag: 2a29f53b-906e-4025-bf90-8e12b4182474
719 // end_of_file
720 */