death to trailing whitespace
[openafs.git] / src / mcas / gc.c
1 /******************************************************************************
2  * gc.c
3  *
4  * A fully recycling epoch-based garbage collector. Works by counting
5  * threads in and out of critical regions, to work out when
6  * garbage queues can be fully deleted.
7  *
8  * Copyright (c) 2001-2003, K A Fraser
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions are
12 met:
13
14     * Redistributions of source code must retain the above copyright
15     * notice, this list of conditions and the following disclaimer.
16     * Redistributions in binary form must reproduce the above
17     * copyright notice, this list of conditions and the following
18     * disclaimer in the documentation and/or other materials provided
19     * with the distribution.  Neither the name of the Keir Fraser
20     * nor the names of its contributors may be used to endorse or
21     * promote products derived from this software without specific
22     * prior written permission.
23
24 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  */
36
37 #include <assert.h>
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <sys/mman.h>
42 #include <unistd.h>
43 #include "portable_defns.h"
44 #include "gc.h"
45
46 #include <afsconfig.h>
47 #include <afs/param.h>
48 #include <afs/afsutil.h>
49
50 /*#define MINIMAL_GC*/
51 /*#define YIELD_TO_HELP_PROGRESS*/
52 #define PROFILE_GC
53
54 /* Recycled nodes are filled with this value if WEAK_MEM_ORDER. */
55 #define INVALID_BYTE 0
56 #define INITIALISE_NODES(_p,_c) memset((_p), INVALID_BYTE, (_c));
57
58 /* Number of unique block sizes we can deal with. Equivalently, the
59  * number of unique object caches which can be created. */
60 #define MAX_SIZES 30
61
62 #define MAX_HOOKS 4
63
64 /*
65  * The initial number of allocation chunks for each per-blocksize list.
66  * Popular allocation lists will steadily increase the allocation unit
67  * in line with demand.
68  */
69 #define ALLOC_CHUNKS_PER_LIST 10
70
71 /*
72  * How many times should a thread call gc_enter(), seeing the same epoch
73  * each time, before it makes a reclaim attempt?
74  */
75 #define ENTRIES_PER_RECLAIM_ATTEMPT 100
76
77 /*
78  *  0: current epoch -- threads are moving to this;
79  * -1: some threads may still throw garbage into this epoch;
80  * -2: no threads can see this epoch => we can zero garbage lists;
81  * -3: all threads see zeros in these garbage lists => move to alloc lists.
82  */
83 #ifdef WEAK_MEM_ORDER
84 #define NR_EPOCHS 4
85 #else
86 #define NR_EPOCHS 3
87 #endif
88
89 /*
90  * A chunk amortises the cost of allocation from shared lists. It also
91  * helps when zeroing nodes, as it increases per-cacheline pointer density
92  * and means that node locations don't need to be brought into the cache
93  * (most architectures have a non-temporal store instruction).
94  */
95 #define BLKS_PER_CHUNK 100
96 typedef struct chunk_st chunk_t;
97 struct chunk_st
98 {
99     chunk_t *next;             /* chunk chaining                 */
100     unsigned int i;            /* the next entry in blk[] to use */
101     void *blk[BLKS_PER_CHUNK];
102 };
103
104 static struct gc_global_st
105 {
106     CACHE_PAD(0);
107
108     /* The current epoch. */
109     VOLATILE unsigned int current;
110     CACHE_PAD(1);
111
112     /* Exclusive access to gc_reclaim(). */
113     VOLATILE unsigned int inreclaim;
114     CACHE_PAD(2);
115
116
117     /* Allocator caches currently defined */
118     long n_allocators;
119
120     /*
121      * RUN-TIME CONSTANTS (to first approximation)
122      */
123
124     /* Memory page size, in bytes. */
125     unsigned int page_size;
126
127     /* Node sizes (run-time constants). */
128     int nr_sizes;
129     int blk_sizes[MAX_SIZES];
130
131     /* tags (trace support) */
132     char *tags[MAX_SIZES];
133
134     /* Registered epoch hooks. */
135     int nr_hooks;
136     hook_fn_t hook_fns[MAX_HOOKS];
137     CACHE_PAD(3);
138
139     /*
140      * DATA WE MAY HIT HARD
141      */
142
143     /* Chain of free, empty chunks. */
144     chunk_t * VOLATILE free_chunks;
145
146     /* Main allocation lists. */
147     chunk_t * VOLATILE alloc[MAX_SIZES];
148     VOLATILE unsigned int alloc_size[MAX_SIZES];
149 #ifdef PROFILE_GC
150     VOLATILE unsigned int total_size;
151     VOLATILE unsigned int allocations;
152 #endif
153 } gc_global;
154
155
156 /* Per-thread state. */
157 struct gc_st
158 {
159     /* Epoch that this thread sees. */
160     unsigned int epoch;
161
162     /* Number of calls to gc_entry() since last gc_reclaim() attempt. */
163     unsigned int entries_since_reclaim;
164
165 #ifdef YIELD_TO_HELP_PROGRESS
166     /* Number of calls to gc_reclaim() since we last yielded. */
167     unsigned int reclaim_attempts_since_yield;
168 #endif
169
170     /* Used by gc_async_barrier(). */
171     void *async_page;
172     int   async_page_state;
173
174     /* Garbage lists. */
175     chunk_t *garbage[NR_EPOCHS][MAX_SIZES];
176     chunk_t *garbage_tail[NR_EPOCHS][MAX_SIZES];
177     chunk_t *chunk_cache;
178
179     /* Local allocation lists. */
180     chunk_t *alloc[MAX_SIZES];
181     unsigned int alloc_chunks[MAX_SIZES];
182
183     /* Hook pointer lists. */
184     chunk_t *hook[NR_EPOCHS][MAX_HOOKS];
185 };
186
187 /* XXX generalize */
188 #ifndef KERNEL
189
190 #define MEM_FAIL(_s) \
191 do { \
192     fprintf(stderr, "OUT OF MEMORY: %d bytes at line %d\n", (_s), __LINE__); \
193     abort(); \
194 } while ( 0 )
195 #endif
196
197 /* Allocate more empty chunks from the heap. */
198 #define CHUNKS_PER_ALLOC 1000
199 static chunk_t *alloc_more_chunks(void)
200 {
201     int i;
202     chunk_t *h, *p;
203
204     ViceLog(11, ("GC: alloc_more_chunks alloc %lu chunks\n",
205         CHUNKS_PER_ALLOC));
206
207     h = p = ALIGNED_ALLOC(CHUNKS_PER_ALLOC * sizeof(*h));
208     if ( h == NULL ) MEM_FAIL(CHUNKS_PER_ALLOC * sizeof(*h));
209
210     for ( i = 1; i < CHUNKS_PER_ALLOC; i++ )
211     {
212         p->next = p + 1;
213         p++;
214     }
215
216     p->next = h;
217
218     return(h);
219 }
220
221
222 /* Put a chain of chunks onto a list. */
223 static void add_chunks_to_list(chunk_t *ch, chunk_t *head)
224 {
225     chunk_t *h_next, *new_h_next, *ch_next;
226     ch_next    = ch->next;
227     new_h_next = head->next;
228     do { ch->next = h_next = new_h_next; WMB_NEAR_CAS(); }
229     while ( (new_h_next = CASPO(&head->next, h_next, ch_next)) != h_next );
230 }
231
232
233 /* Allocate a chain of @n empty chunks. Pointers may be garbage. */
234 static chunk_t *get_empty_chunks(int n)
235 {
236     int i;
237     chunk_t *new_rh, *rh, *rt, *head;
238
239  retry:
240     head = gc_global.free_chunks;
241     new_rh = head->next;
242     do {
243         rh = new_rh;
244         rt = head;
245         WEAK_DEP_ORDER_RMB();
246         for ( i = 0; i < n; i++ )
247         {
248             if ( (rt = rt->next) == head )
249             {
250                 /* Allocate some more chunks. */
251                 add_chunks_to_list(alloc_more_chunks(), head);
252                 goto retry;
253             }
254         }
255     }
256     while ( (new_rh = CASPO(&head->next, rh, rt->next)) != rh );
257
258     rt->next = rh;
259     return(rh);
260 }
261
262
263 /* Get @n filled chunks, pointing at blocks of @sz bytes each. */
264 static chunk_t *get_filled_chunks(int n, int sz)
265 {
266     chunk_t *h, *p;
267     char *node;
268     int i;
269
270 #ifdef PROFILE_GC
271     ADD_TO(gc_global.total_size, n * BLKS_PER_CHUNK * sz);
272     ADD_TO(gc_global.allocations, 1);
273 #endif
274
275     node = ALIGNED_ALLOC(n * BLKS_PER_CHUNK * sz);
276     if ( node == NULL ) MEM_FAIL(n * BLKS_PER_CHUNK * sz);
277 #ifdef WEAK_MEM_ORDER
278     INITIALISE_NODES(node, n * BLKS_PER_CHUNK * sz);
279 #endif
280
281     h = p = get_empty_chunks(n);
282     do {
283         p->i = BLKS_PER_CHUNK;
284         for ( i = 0; i < BLKS_PER_CHUNK; i++ )
285         {
286             p->blk[i] = node;
287             node += sz;
288         }
289     }
290     while ( (p = p->next) != h );
291
292     return(h);
293 }
294
295
296 /*
297  * gc_async_barrier: Cause an asynchronous barrier in all other threads. We do
298  * this by causing a TLB shootdown to be propagated to all other processors.
299  * Each time such an action is required, this function calls:
300  *   mprotect(async_page, <page size>, <new flags>)
301  * Each thread's state contains a memory page dedicated for this purpose.
302  */
303 #ifdef WEAK_MEM_ORDER
304 static void gc_async_barrier(gc_t *gc)
305 {
306     mprotect(gc->async_page, gc_global.page_size,
307              gc->async_page_state ? PROT_READ : PROT_NONE);
308     gc->async_page_state = !gc->async_page_state;
309 }
310 #else
311 #define gc_async_barrier(_g) ((void)0)
312 #endif
313
314
315 /* Grab a level @i allocation chunk from main chain. */
316 static chunk_t *get_alloc_chunk(gc_t *gc, int i)
317 {
318     chunk_t *alloc, *p, *new_p, *nh;
319     unsigned int sz;
320
321     alloc = gc_global.alloc[i];
322     new_p = alloc->next;
323
324     do {
325         p = new_p;
326         while ( p == alloc )
327         {
328             sz = gc_global.alloc_size[i];
329             nh = get_filled_chunks(sz, gc_global.blk_sizes[i]);
330             ADD_TO(gc_global.alloc_size[i], sz >> 3);
331             gc_async_barrier(gc);
332             add_chunks_to_list(nh, alloc);
333             p = alloc->next;
334         }
335         WEAK_DEP_ORDER_RMB();
336     }
337     while ( (new_p = CASPO(&alloc->next, p, p->next)) != p );
338
339     p->next = p;
340     assert(p->i == BLKS_PER_CHUNK);
341     return(p);
342 }
343
344
345 #ifndef MINIMAL_GC
346 /*
347  * gc_reclaim: Scans the list of struct gc_perthread looking for the lowest
348  * maximum epoch number seen by a thread that's in the list code. If it's the
349  * current epoch, the "nearly-free" lists from the previous epoch are
350  * reclaimed, and the epoch is incremented.
351  */
352 static void gc_reclaim(void)
353 {
354     ptst_t       *ptst, *first_ptst, *our_ptst = NULL;
355     gc_t         *gc = NULL;
356     unsigned long curr_epoch;
357     chunk_t      *ch, *t;
358     int           two_ago, three_ago, i, j;
359
360     ViceLog(11, ("GC: gc_reclaim enter\n"));
361
362     /* Barrier to entering the reclaim critical section. */
363     if ( gc_global.inreclaim || CASIO(&gc_global.inreclaim, 0, 1) ) return;
364
365     ViceLog(11, ("GC: gc_reclaim after inreclaim barrier\n"));
366
367     /*
368      * Grab first ptst structure *before* barrier -- prevent bugs
369      * on weak-ordered architectures.
370      */
371     first_ptst = ptst_first();
372     MB();
373     curr_epoch = gc_global.current;
374
375     /* Have all threads seen the current epoch, or not in mutator code? */
376     for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
377     {
378         if ( (ptst->count > 1) && (ptst->gc->epoch != curr_epoch) ) goto out;
379     }
380
381
382     ViceLog(11, ("GC: gc_reclaim all-threads see current epoch\n"));
383
384     /*
385      * Three-epoch-old garbage lists move to allocation lists.
386      * Two-epoch-old garbage lists are cleaned out.
387      */
388     two_ago   = (curr_epoch+2) % NR_EPOCHS;
389     three_ago = (curr_epoch+1) % NR_EPOCHS;
390     if ( gc_global.nr_hooks != 0 )
391         our_ptst = (ptst_t *)pthread_getspecific(ptst_key);
392     for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
393     {
394         gc = ptst->gc;
395
396         for ( i = 0; i < gc_global.nr_sizes; i++ )
397         {
398 #ifdef WEAK_MEM_ORDER
399             int sz = gc_global.blk_sizes[i];
400             if ( gc->garbage[two_ago][i] != NULL )
401             {
402                 chunk_t *head = gc->garbage[two_ago][i];
403                 ch = head;
404                 do {
405                     int j;
406                     for ( j = 0; j < ch->i; j++ )
407                         INITIALISE_NODES(ch->blk[j], sz);
408                 }
409                 while ( (ch = ch->next) != head );
410             }
411 #endif
412
413             /* NB. Leave one chunk behind, as it is probably not yet full. */
414             t = gc->garbage[three_ago][i];
415             if ( (t == NULL) || ((ch = t->next) == t) ) continue;
416             gc->garbage_tail[three_ago][i]->next = ch;
417             gc->garbage_tail[three_ago][i] = t;
418             t->next = t;
419
420                         /* gc inst: compute and log size of returned list */
421                         {
422                                 chunk_t *ch_head, *ch_next;
423                                 int r_ix, r_len, r_size;
424                                 r_ix = 0;
425                                 r_len = 0;
426                                 r_size = 0;
427
428                                 /* XXX: nonfatal, may be missing multiplier */
429                                 ch_head = ch;
430                             do {
431                                         r_len++;
432                                 } while (ch->next && (ch->next != ch_head)
433                                                  && (ch_next = ch->next));
434
435                                 ViceLog(11, ("GC: return %d chunks of size %d to "
436                                                          "gc_global.alloc[%d]\n",
437                                                          r_len,
438                                                          gc_global.blk_sizes[i],
439                                                          i));
440                         }
441
442
443             add_chunks_to_list(ch, gc_global.alloc[i]);
444         }
445
446         for ( i = 0; i < gc_global.nr_hooks; i++ )
447         {
448             hook_fn_t fn = gc_global.hook_fns[i];
449             ch = gc->hook[three_ago][i];
450             if ( ch == NULL ) continue;
451             gc->hook[three_ago][i] = NULL;
452
453             t = ch;
454             do { for ( j = 0; j < t->i; j++ ) fn(our_ptst, t->blk[j]); }
455             while ( (t = t->next) != ch );
456
457                         /* gc inst: compute and log size of returned list */
458                         {
459                                 chunk_t *ch_head, *ch_next;
460                                 int r_ix, r_len, r_size;
461                                 r_ix = 0;
462                                 r_len = 0;
463
464                                 /* XXX: nonfatal, may be missing multiplier */
465                                 ch_head = ch;
466                             do {
467                                         r_len++;
468                                 } while (ch->next && (ch->next != ch_head)
469                                                  && (ch_next = ch->next));
470
471                                 ViceLog(11, ("GC: return %d chunks to gc_global.free_chunks\n",
472                                                          r_len));
473                         }
474
475             add_chunks_to_list(ch, gc_global.free_chunks);
476         }
477     }
478
479     /* Update current epoch. */
480     ViceLog(11, ("GC: gc_reclaim epoch transition (leaving %lu)\n",
481                                  curr_epoch));
482
483     WMB();
484     gc_global.current = (curr_epoch+1) % NR_EPOCHS;
485
486  out:
487     gc_global.inreclaim = 0;
488 }
489 #endif /* MINIMAL_GC */
490
491
492 void *gc_alloc(ptst_t *ptst, int alloc_id)
493 {
494     gc_t *gc = ptst->gc;
495     chunk_t *ch;
496
497     ch = gc->alloc[alloc_id];
498     if ( ch->i == 0 )
499     {
500         if ( gc->alloc_chunks[alloc_id]++ == 100 )
501         {
502             gc->alloc_chunks[alloc_id] = 0;
503             add_chunks_to_list(ch, gc_global.free_chunks);
504             gc->alloc[alloc_id] = ch = get_alloc_chunk(gc, alloc_id);
505         }
506         else
507         {
508             chunk_t *och = ch;
509             ch = get_alloc_chunk(gc, alloc_id);
510             ch->next  = och->next;
511             och->next = ch;
512             gc->alloc[alloc_id] = ch;
513         }
514     }
515
516     return ch->blk[--ch->i];
517 }
518
519 int
520 gc_get_blocksize(int alloc_id)
521 {
522     return (gc_global.blk_sizes[alloc_id]);
523 }
524
525 char *
526 gc_get_tag(int alloc_id)
527 {
528     return (gc_global.tags[alloc_id]);
529 }
530
531 static chunk_t *chunk_from_cache(gc_t *gc)
532 {
533     chunk_t *ch = gc->chunk_cache, *p = ch->next;
534
535     if ( ch == p )
536     {
537         gc->chunk_cache = get_empty_chunks(100);
538     }
539     else
540     {
541         ch->next = p->next;
542         p->next  = p;
543     }
544
545     p->i = 0;
546     return(p);
547 }
548
549
550 void gc_free(ptst_t *ptst, void *p, int alloc_id)
551 {
552 #ifndef MINIMAL_GC
553     gc_t *gc = ptst->gc;
554     chunk_t *prev, *new, *ch = gc->garbage[gc->epoch][alloc_id];
555
556     if ( ch == NULL )
557     {
558         gc->garbage[gc->epoch][alloc_id] = ch = chunk_from_cache(gc);
559         gc->garbage_tail[gc->epoch][alloc_id] = ch;
560     }
561     else if ( ch->i == BLKS_PER_CHUNK )
562     {
563         prev = gc->garbage_tail[gc->epoch][alloc_id];
564         new  = chunk_from_cache(gc);
565         gc->garbage[gc->epoch][alloc_id] = new;
566         new->next  = ch;
567         prev->next = new;
568         ch = new;
569     }
570
571     ch->blk[ch->i++] = p;
572 #endif
573 }
574
575
576 void gc_add_ptr_to_hook_list(ptst_t *ptst, void *ptr, int hook_id)
577 {
578     gc_t *gc = ptst->gc;
579     chunk_t *och, *ch = gc->hook[gc->epoch][hook_id];
580
581     if ( ch == NULL )
582     {
583         gc->hook[gc->epoch][hook_id] = ch = chunk_from_cache(gc);
584     }
585     else
586     {
587         ch = ch->next;
588         if ( ch->i == BLKS_PER_CHUNK )
589         {
590             och       = gc->hook[gc->epoch][hook_id];
591             ch        = chunk_from_cache(gc);
592             ch->next  = och->next;
593             och->next = ch;
594         }
595     }
596
597     ch->blk[ch->i++] = ptr;
598 }
599
600
601 void gc_unsafe_free(ptst_t *ptst, void *p, int alloc_id)
602 {
603     gc_t *gc = ptst->gc;
604     chunk_t *ch;
605
606     ch = gc->alloc[alloc_id];
607     if ( ch->i < BLKS_PER_CHUNK )
608     {
609         ch->blk[ch->i++] = p;
610     }
611     else
612     {
613         gc_free(ptst, p, alloc_id);
614     }
615 }
616
617
618 void gc_enter(ptst_t *ptst)
619 {
620 #ifdef MINIMAL_GC
621     ptst->count++;
622     MB();
623 #else
624     gc_t *gc = ptst->gc;
625     int new_epoch, cnt;
626
627  retry:
628     cnt = ptst->count++;
629     MB();
630     if ( cnt == 1 )
631     {
632         new_epoch = gc_global.current;
633         if ( gc->epoch != new_epoch )
634         {
635             gc->epoch = new_epoch;
636             gc->entries_since_reclaim        = 0;
637 #ifdef YIELD_TO_HELP_PROGRESS
638             gc->reclaim_attempts_since_yield = 0;
639 #endif
640         }
641         else if ( gc->entries_since_reclaim++ == 100 )
642         {
643             ptst->count--;
644 #ifdef YIELD_TO_HELP_PROGRESS
645             if ( gc->reclaim_attempts_since_yield++ == 10000 )
646             {
647                 gc->reclaim_attempts_since_yield = 0;
648                 sched_yield();
649             }
650 #endif
651             gc->entries_since_reclaim = 0;
652             gc_reclaim();
653             goto retry;
654         }
655     }
656 #endif
657 }
658
659
660 void gc_exit(ptst_t *ptst)
661 {
662     MB();
663     ptst->count--;
664 }
665
666
667 gc_t *gc_init(void)
668 {
669     gc_t *gc;
670     int   i;
671
672     gc = ALIGNED_ALLOC(sizeof(*gc));
673     if ( gc == NULL ) MEM_FAIL(sizeof(*gc));
674     memset(gc, 0, sizeof(*gc));
675
676 #ifdef WEAK_MEM_ORDER
677     /* Initialise shootdown state. */
678     gc->async_page = mmap(NULL, gc_global.page_size, PROT_NONE,
679                           MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
680     if ( gc->async_page == (void *)MAP_FAILED ) MEM_FAIL(gc_global.page_size);
681     gc->async_page_state = 1;
682 #endif
683
684     gc->chunk_cache = get_empty_chunks(100);
685
686     /* Get ourselves a set of allocation chunks. */
687     for ( i = 0; i < gc_global.nr_sizes; i++ )
688     {
689         gc->alloc[i] = get_alloc_chunk(gc, i);
690     }
691     for ( ; i < MAX_SIZES; i++ )
692     {
693         gc->alloc[i] = chunk_from_cache(gc);
694     }
695
696     return(gc);
697 }
698
699
700 int
701 gc_add_allocator(int alloc_size, char *tag)
702 {
703     int ni, i;
704
705     RMB();
706     FASPO(&gc_global.n_allocators, gc_global.n_allocators + 1);
707     if (gc_global.n_allocators > MAX_SIZES) {
708         /* critical error */
709 #if !defined(KERNEL)
710         printf("MCAS gc max allocators exceeded, aborting\n");
711 #endif
712         abort();
713     }
714
715     i = gc_global.nr_sizes;
716     while ((ni = CASIO(&gc_global.nr_sizes, i, i + 1)) != i)
717         i = ni;
718     gc_global.blk_sizes[i] = alloc_size;
719     gc_global.tags[i] = strdup(tag);
720     gc_global.alloc_size[i] = ALLOC_CHUNKS_PER_LIST;
721     gc_global.alloc[i] = get_filled_chunks(ALLOC_CHUNKS_PER_LIST, alloc_size);
722     return i;
723 }
724
725
726 void gc_remove_allocator(int alloc_id)
727 {
728     /* This is a no-op for now. */
729 }
730
731
732 int gc_add_hook(hook_fn_t fn)
733 {
734     int ni, i = gc_global.nr_hooks;
735     while ( (ni = CASIO(&gc_global.nr_hooks, i, i+1)) != i ) i = ni;
736     gc_global.hook_fns[i] = fn;
737     return i;
738 }
739
740
741 void gc_remove_hook(int hook_id)
742 {
743     /* This is a no-op for now. */
744 }
745
746
747 void _destroy_gc_subsystem(void)
748 {
749 #ifdef PROFILE_GC
750     printf("Total heap: %u bytes (%.2fMB) in %u allocations\n",
751            gc_global.total_size, (double)gc_global.total_size / 1000000,
752            gc_global.allocations);
753 #endif
754 }
755
756
757 void _init_gc_subsystem(void)
758 {
759     memset(&gc_global, 0, sizeof(gc_global));
760
761     gc_global.page_size   = (unsigned int)sysconf(_SC_PAGESIZE);
762     gc_global.free_chunks = alloc_more_chunks();
763
764     gc_global.nr_hooks = 0;
765     gc_global.nr_sizes = 0;
766 }