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 }