gc.c

unix-like 系统下c实现的垃圾回收器

    /* Barrier to entering the reclaim critical section. */
    if ( gc_global.inreclaim || CASIO(&gc_global.inreclaim, 0, 1) ) return;

    /*
     * Grab first ptst structure *before* barrier -- prevent bugs
     * on weak-ordered architectures.
     */
    first_ptst = ptst_first();
    MB();
    curr_epoch = gc_global.current;

    /* Have all threads seen the current epoch, or not in mutator code? */
    for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
    {
        if ( (ptst->count > 1) && (ptst->gc->epoch != curr_epoch) ) goto out;
    }

    /*
     * Three-epoch-old garbage lists move to allocation lists.
     * Two-epoch-old garbage lists are cleaned out.
     */
    two_ago   = (curr_epoch+2) % NR_EPOCHS;
    three_ago = (curr_epoch+1) % NR_EPOCHS;
    if ( gc_global.nr_hooks != 0 )
        our_ptst = (ptst_t *)pthread_getspecific(ptst_key);
    for ( ptst = first_ptst; ptst != NULL; ptst = ptst_next(ptst) )
    {
        gc = ptst->gc;

        for ( i = 0; i < gc_global.nr_sizes; i++ )
        {
#ifdef WEAK_MEM_ORDER
            int sz = gc_global.blk_sizes[i];
            if ( gc->garbage[two_ago][i] != NULL )
            {
                chunk_t *head = gc->garbage[two_ago][i];
                ch = head;
                do {
                    int j;
                    for ( j = 0; j < ch->i; j++ )
                        INITIALISE_NODES(ch->blk[j], sz);
                }
                while ( (ch = ch->next) != head );
            }
#endif

            /* NB. Leave one chunk behind, as it is probably not yet full. */
            t = gc->garbage[three_ago][i];
            if ( (t == NULL) || ((ch = t->next) == t) ) continue;
            gc->garbage_tail[three_ago][i]->next = ch;
            gc->garbage_tail[three_ago][i] = t;
            t->next = t;
            add_chunks_to_list(ch, gc_global.alloc[i]);
        }

        for ( i = 0; i < gc_global.nr_hooks; i++ )
        {
            hook_fn_t fn = gc_global.hook_fns[i];
            ch = gc->hook[three_ago][i];
            if ( ch == NULL ) continue;
            gc->hook[three_ago][i] = NULL;

            t = ch;
            do { for ( j = 0; j < t->i; j++ ) fn(our_ptst, t->blk[j]); }
            while ( (t = t->next) != ch );

            add_chunks_to_list(ch, gc_global.free_chunks);
        }
    }

    /* Update current epoch. */
    WMB();
    gc_global.current = (curr_epoch+1) % NR_EPOCHS;

 out:
    gc_global.inreclaim = 0;
}
#endif /* MINIMAL_GC */


void *gc_alloc(ptst_t *ptst, int alloc_id)
{
    gc_t *gc = ptst->gc;
    chunk_t *ch;

    ch = gc->alloc[alloc_id];
    if ( ch->i == 0 )
    {
        if ( gc->alloc_chunks[alloc_id]++ == 100 )
        {
            gc->alloc_chunks[alloc_id] = 0;
            add_chunks_to_list(ch, gc_global.free_chunks);
            gc->alloc[alloc_id] = ch = get_alloc_chunk(gc, alloc_id);
        }
        else
        {
            chunk_t *och = ch;
            ch = get_alloc_chunk(gc, alloc_id);
            ch->next  = och->next;
            och->next = ch;
            gc->alloc[alloc_id] = ch;        
        }
    }

    return ch->blk[--ch->i];
}


static chunk_t *chunk_from_cache(gc_t *gc)
{
    chunk_t *ch = gc->chunk_cache, *p = ch->next;

    if ( ch == p )
    {
        gc->chunk_cache = get_empty_chunks(100);
    }
    else
    {
        ch->next = p->next;
        p->next  = p;
    }

    p->i = 0;
    return(p);
}


void gc_free(ptst_t *ptst, void *p, int alloc_id) 
{
#ifndef MINIMAL_GC
    gc_t *gc = ptst->gc;
    chunk_t *prev, *new, *ch = gc->garbage[gc->epoch][alloc_id];

    if ( ch == NULL )
    {
        gc->garbage[gc->epoch][alloc_id] = ch = chunk_from_cache(gc);
        gc->garbage_tail[gc->epoch][alloc_id] = ch;
    }
    else if ( ch->i == BLKS_PER_CHUNK )
    {
        prev = gc->garbage_tail[gc->epoch][alloc_id];
        new  = chunk_from_cache(gc);
        gc->garbage[gc->epoch][alloc_id] = new;
        new->next  = ch;
        prev->next = new;
        ch = new;
    }

    ch->blk[ch->i++] = p;
#endif
}


void gc_add_ptr_to_hook_list(ptst_t *ptst, void *ptr, int hook_id)
{
    gc_t *gc = ptst->gc;
    chunk_t *och, *ch = gc->hook[gc->epoch][hook_id];

    if ( ch == NULL )
    {
        gc->hook[gc->epoch][hook_id] = ch = chunk_from_cache(gc);
    }
    else
    {
        ch = ch->next;
        if ( ch->i == BLKS_PER_CHUNK )
        {
            och       = gc->hook[gc->epoch][hook_id];
            ch        = chunk_from_cache(gc);
            ch->next  = och->next;
            och->next = ch;
        }
    }

    ch->blk[ch->i++] = ptr;
}


void gc_unsafe_free(ptst_t *ptst, void *p, int alloc_id)
{
    gc_t *gc = ptst->gc;
    chunk_t *ch;

    ch = gc->alloc[alloc_id];
    if ( ch->i < BLKS_PER_CHUNK )
    {
        ch->blk[ch->i++] = p;
    }
    else
    {
        gc_free(ptst, p, alloc_id);
    }
}


void gc_enter(ptst_t *ptst)
{
#ifdef MINIMAL_GC
    ptst->count++;
    MB();
#else
    gc_t *gc = ptst->gc;
    int new_epoch, cnt;
 
 retry:
    cnt = ptst->count++;
    MB();
    if ( cnt == 1 )
    {
        new_epoch = gc_global.current;
        if ( gc->epoch != new_epoch )
        {
            gc->epoch = new_epoch;
            gc->entries_since_reclaim        = 0;
#ifdef YIELD_TO_HELP_PROGRESS
            gc->reclaim_attempts_since_yield = 0;
#endif
        }
        else if ( gc->entries_since_reclaim++ == 100 )
        {
            ptst->count--;
#ifdef YIELD_TO_HELP_PROGRESS
            if ( gc->reclaim_attempts_since_yield++ == 10000 )
            {
                gc->reclaim_attempts_since_yield = 0;
                sched_yield();
            }
#endif
            gc->entries_since_reclaim = 0;
            gc_reclaim();
            goto retry;    
        }
    }
#endif
}


void gc_exit(ptst_t *ptst)
{
    MB();
    ptst->count--;
}


gc_t *gc_init(void)
{
    gc_t *gc;
    int   i;

    gc = ALIGNED_ALLOC(sizeof(*gc));
    if ( gc == NULL ) MEM_FAIL(sizeof(*gc));
    memset(gc, 0, sizeof(*gc));

#ifdef WEAK_MEM_ORDER
    /* Initialise shootdown state. */
    gc->async_page = mmap(NULL, gc_global.page_size, PROT_NONE, 
                          MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if ( gc->async_page == (void *)MAP_FAILED ) MEM_FAIL(gc_global.page_size);
    gc->async_page_state = 1;
#endif

    gc->chunk_cache = get_empty_chunks(100);

    /* Get ourselves a set of allocation chunks. */
    for ( i = 0; i < gc_global.nr_sizes; i++ )
    {
        gc->alloc[i] = get_alloc_chunk(gc, i);
    }
    for ( ; i < MAX_SIZES; i++ )
    {
        gc->alloc[i] = chunk_from_cache(gc);
    }

    return(gc);
}


int gc_add_allocator(int alloc_size)
{
    int ni, i = gc_global.nr_sizes;
    while ( (ni = CASIO(&gc_global.nr_sizes, i, i+1)) != i ) i = ni;
    gc_global.blk_sizes[i]  = alloc_size;
    gc_global.alloc_size[i] = ALLOC_CHUNKS_PER_LIST;
    gc_global.alloc[i] = get_filled_chunks(ALLOC_CHUNKS_PER_LIST, alloc_size);
    return i;
}


void gc_remove_allocator(int alloc_id)
{
    /* This is a no-op for now. */
}


int gc_add_hook(hook_fn_t fn)
{
    int ni, i = gc_global.nr_hooks;
    while ( (ni = CASIO(&gc_global.nr_hooks, i, i+1)) != i ) i = ni;
    gc_global.hook_fns[i] = fn;
    return i;    
}


void gc_remove_hook(int hook_id)
{
    /* This is a no-op for now. */
}


void _destroy_gc_subsystem(void)
{
#ifdef PROFILE_GC
    printf("Total heap: %u bytes (%.2fMB) in %u allocations\n",
           gc_global.total_size, (double)gc_global.total_size / 1000000,
           gc_global.allocations);
#endif
}


void _init_gc_subsystem(void)
{
    memset(&gc_global, 0, sizeof(gc_global));

    gc_global.page_size   = (unsigned int)sysconf(_SC_PAGESIZE);
    gc_global.free_chunks = alloc_more_chunks();

    gc_global.nr_hooks = 0;
    gc_global.nr_sizes = 0;
}