root/trunk/thune/gc.c

/*============================================================================
    Thune Interpreter
    Copyright (C) 2005-2006  Karl Robillard

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
===========================================================================*/


#include "os.h"
#include "urlan.h"
#include "internal.h"
//#include "pairpool.h"


#ifdef DEBUG
//#define GC_REPORT   1
//#define GC_VERBOSE  1
#endif

//#define GC_TIME     1
#ifdef GC_TIME
#include <time.h>
#endif


static void _freeArrayX( UArray* arr, UGCArray* agc, UArray* abuf )
{
    if( arr->ptr.v )
    {
        memFree( arr->ptr.v );
        arr->ptr.v  = 0;
    }

    // Flag as unused.
    arr->avail = -1;

    // Link to free list.
    arr->used  = agc->freeList;
    agc->freeList = arr - abuf;

    agc->freeCount += 1;
}


#if 0
/**
  Do not call ur_freeBlock() from inside garbage collector.
*/
void ur_freeBlock( UIndex blkN )
{
    UArray* abuf = (UArray*) ut->blocks.arr.ptr.v;
    _freeArrayX( abuf + blkN, &ut->blocks, abuf );
}
#endif


#define FREE_ARRAY(it) \
    tmp = it; \
    if( tmp->avail > -1 ) \
        _freeArrayX( tmp, af, abuf );

static void _sweepArray( UArray* mark, UGCArray* af )
{
    UArray* tmp;
    UArray* arr  = &af->arr;
    UArray* abuf = (UArray*) arr->ptr.v;
    UArray* ait  = abuf;
    uint8_t* it  = mark->ptr.b;
    uint8_t* end = it + mark->used;
    int count = arr->used;


    // Mark padding bits at end as used.
    if( count & 7 )
        end[-1] |= 0xff << (count & 7);


    // Check mark bitset for unused elements.
    while( it != end )
    {
        if( *it != 0xff )
        {
            int mask = *it;

#if 0
            dprint( "_sweepArray %p elem: %d 0x%02x\n",
                    arr->buf, ait - ((UArray*) arr->buf), mask );
#endif

            if( (mask & 0x0f) != 0x0f )
            {
                if( (mask & 0x01) == 0 ) { FREE_ARRAY( ait ) }
                if( (mask & 0x02) == 0 ) { FREE_ARRAY( ait + 1 ) }
                if( (mask & 0x04) == 0 ) { FREE_ARRAY( ait + 2 ) }
                if( (mask & 0x08) == 0 ) { FREE_ARRAY( ait + 3 ) }
            }

            if( (mask & 0xf0) != 0xf0 )
            {
                if( (mask & 0x10) == 0 ) { FREE_ARRAY( ait + 4 ) }
                if( (mask & 0x20) == 0 ) { FREE_ARRAY( ait + 5 ) }
                if( (mask & 0x40) == 0 ) { FREE_ARRAY( ait + 6 ) }
                if( (mask & 0x80) == 0 ) { FREE_ARRAY( ait + 7 ) }
            }
        }
        ++it;
        ait += 8;
    }


#if 0
    // Move the top of the array down.
    ait = ((UArray*) arr->buf) + arr->used - 1;
    while( arr->used && (ait->avail == -1) )
    {
        --ait;
        --arr->used;
        *_freeCount -= 1;
    }
#endif
}


static void _freeResource( UDatatype* customDT, UGCArray* agc, UResource* buf )
{
    int idx = ((int) buf->dataType) - UT_BI_COUNT;
    if( idx >= 0 )
    {
#if 0
        printf( "freeResource %ld %s\n",
                buf - (UResource*) agc->arr.ptr.v, customDT[idx].name );
#endif
        customDT[ idx ].gcDestroyResource( buf );
    }

    // Flag as unused.
    buf->dataType = UT_UNSET;

    // Link to free list.
    buf->link = agc->freeList;
    agc->freeList = buf - ((UResource*) agc->arr.ptr.v);

    agc->freeCount += 1;
}


#define FREE_BUFFER(buf) \
    btmp = buf; \
    if( btmp->dataType != UT_UNSET ) \
        _freeResource( dt, agc, btmp );

static void _sweepResources( UDatatype* dt, UArray* mark, UGCArray* agc )
{
    UResource* btmp;
    UResource* ait = (UResource*) agc->arr.ptr.v;
    uint8_t* it  = mark->ptr.b;
    uint8_t* end = it + mark->used;


    // Mark padding bits at end as used.
    {
    int padBits = agc->arr.used & 7;
    if( padBits )
        end[-1] |= 0xff << padBits;
    }

    // Check mark bitset for unused elements.
    while( it != end )
    {
        if( *it != 0xff )
        {
            int mask = *it;

            if( (mask & 0x0f) != 0x0f )
            {
                if( (mask & 0x01) == 0 ) { FREE_BUFFER( ait ) }
                if( (mask & 0x02) == 0 ) { FREE_BUFFER( ait + 1 ) }
                if( (mask & 0x04) == 0 ) { FREE_BUFFER( ait + 2 ) }
                if( (mask & 0x08) == 0 ) { FREE_BUFFER( ait + 3 ) }
            }

            if( (mask & 0xf0) != 0xf0 )
            {
                if( (mask & 0x10) == 0 ) { FREE_BUFFER( ait + 4 ) }
                if( (mask & 0x20) == 0 ) { FREE_BUFFER( ait + 5 ) }
                if( (mask & 0x40) == 0 ) { FREE_BUFFER( ait + 6 ) }
                if( (mask & 0x80) == 0 ) { FREE_BUFFER( ait + 7 ) }
            }
        }
        ++it;
        ait += 8;
    }
}


void ur_gcMarkBin( UCollector* gc, UIndex idx )
{
    ur_setBit( gc->bsBin.ptr.b, idx );
}


void ur_gcMarkBlock( UCollector* gc, UIndex idx )
{
    ur_setBit( gc->bsBlock.ptr.b, idx );
}


void ur_gcMarkResource( UCollector* gc, UIndex idx )
{
    ur_setBit( gc->bsRes.ptr.b, idx );
}


#define SET_BIT_BLOCK(bn) \
    ur_setBit( gc->bsBlock.ptr.b, bn );

#define SET_BIT_BLOCK_L(bn) \
    idx = bn; if( ur_isLocal(idx) ) ur_setBit( gc->bsBlock.ptr.b, idx );

#define SET_BIT_BIN(bn) \
    ur_setBit( gc->bsBin.ptr.b, bn );

#define SET_BIT_BIN_L(bn) \
    idx = bn; if( ur_isLocal(idx) ) ur_setBit( gc->bsBin.ptr.b, idx );


static void _checkBlock( UThread* ut, UCollector* gc, UBlock* blk )
{
    UCell* it  = blk->ptr.cells;

#ifdef GC_VERBOSE
    printf( "GC _checkBlock %ld\n", orBlockN(blk) );
#endif

    if( it )
        ur_gcMarkCells( ut, gc, it, it + blk->used );
}


void ur_gcMarkCells( UThread* ut, UCollector* gc, UCell* it, const UCell* end )
{
    int idx;
    while( it != end )
    {
        switch( ur_type(it) )
        {
            case UT_UNSET:
            case UT_DATATYPE:
            case UT_NONE:
            case UT_LOGIC:
            case UT_OPCODE:
            case UT_CHAR:
            case UT_INT:
            case UT_DECIMAL:
            case UT_COORD:
            case UT_VEC3:
                break;

            case UT_WORD:
            case UT_SETWORD:
            //case UT_LITWORD:      // Only atom is used in lit-words?
                SET_BIT_BLOCK_L( it->word.wordBlk )
                idx = it->word.valBlk;
                if( idx > 0 )
                    SET_BIT_BLOCK( idx )
                break;

            case UT_BINARY:
            case UT_STRING:
            case UT_VECTOR:
            case UT_BITSET:
                SET_BIT_BIN_L( it->series.n )
                break;

            case UT_CONTEXT:
            case UT_PORT:
            case UT_COMPONENT:
                idx = it->ctx.wordBlk;
                if( ur_isLocal(idx) )
                {
                    // Word block only contains words so block is marked
                    // as checked.
                    int ai   = idx >> 3;
                    int bitm = 1 << (idx & 7);
                    gc->bsBlock.ptr.b[ ai ] |= bitm;
                    gc->blkChecked.ptr.b[ ai ] |= bitm;
                }

                SET_BIT_BLOCK_L( it->ctx.valBlk )
                break;

            case UT_FUNCTION:
                SET_BIT_BLOCK_L( it->func.bodyN )
                SET_BIT_BLOCK_L( it->func.sigN )
                //SET_BIT_BLOCK_L( it->func.closureN )
                break;

            case UT_LIST:
            case UT_BLOCK:
            case UT_PAREN:
            case UT_MACRO:
#ifdef UR_CONFIG_HASHMAP
mark_block:
#endif
                idx = it->series.n;
                if( ur_isLocal(idx) )
                {
                    int ai   = idx >> 3;
                    int bitm = 1 << (idx & 7);
                    gc->bsBlock.ptr.b[ ai ] |= bitm;
                    if( ! (gc->blkChecked.ptr.b[ ai ] & bitm) )
                    {
                        gc->blkChecked.ptr.b[ ai ] |= bitm;
                        _checkBlock( ut, gc, ur_block( it ) );
                    }
                }
                break;

#ifdef PAIRPOOL_H
            case UT_SLIST:
            {
                UCell* pair = uc_pair(it);
                ur_pairPoolGCMark( it );
            }
                break;
#endif
            case UT_PATH:
            case UT_SETPATH:
            //case UT_LITPATH:
                SET_BIT_BLOCK_L( it->series.n )
                break;

            case UT_ERROR:
                idx = it->err.messageStr;
                if( idx )
                    SET_BIT_BIN( idx )

                idx = it->err.traceBlk;
                if( idx > 0 )
                    SET_BIT_BLOCK( idx )
                break;

#ifdef UR_CONFIG_DT_CODE
            case UT_CODE:
            {
                ur_language( it )->codeGC( gc, it );
            }
                break;
#endif
#ifdef UR_CONFIG_HASHMAP
            case UT_HASH_MAP:
                SET_BIT_BIN_L( ur_hashMapBin(it) )
                goto mark_block;
#endif
            default:
                idx = ur_type(it) - UT_BI_COUNT;
                if( idx >= 0 )
                    ut->env->customDT[ idx ].gcMark( gc, it );
                break;
        }
        ++it;
    }
}


#ifdef LANG_THUNE
static void _checkControlStack( UThread* ut, UCollector* gc )
{
    int idx;
    CEntry* it;
    CEntry* end;

    it  = UR_TOC - 1;
    end = UR_BOC - 1;

    while( it != end )
    {
        switch( it->id.code )
        {
            case CC_FUNC:
            case CC_FUNC_LOOP:
                SET_BIT_BLOCK_L( it->func.bodyN )
                idx = it->func.sigN;
                if( idx > 0 )
                    SET_BIT_BLOCK( idx )
                it -= CC_LEN_FUNC;
                break;

            case CC_EVAL:
            case CC_EVAL_RUNNING:
            case CC_FOREVER:
                SET_BIT_BLOCK_L( it->eval.n )
                it -= CC_LEN_EVAL;
                break;

            case CC_LOOP:
                --it;
                SET_BIT_BLOCK_L( it->cell.series.n )
                --it;
                break;

            case CC_REDUCE:
                SET_BIT_BLOCK_L( it->reduce.n )
                it -= CC_LEN_REDUCE;
                break;

            case CC_ITER:
            case CC_EACH:
            {
                UCell* cell = ((UCell*) it) - 1;
                SET_BIT_BLOCK_L( it->cp.n )
                ur_gcMarkCells( ut, gc, cell, cell + 1 );
                it -= CC_LEN_ITER;
            }
                break;

            case CC_CATCH:
                SET_BIT_BLOCK_L( (it - 1)->eval.n )
                it -= CC_LEN_CATCH;
                break;

            case CC_TERM:
            case CC_END:
                SET_BIT_BLOCK_L( it->end.blkN )
                it -= CC_LEN_END;
                break;

            default:
                assert( 0 && "Invalid Control Code" );
        }
    }
}
#endif


#ifdef LANG_RUNE
static void _checkControlStack( UThread* ut, UCollector* gc )
{
    assert( UR_TOC >= UR_BOC );

    ur_gcMarkCells( ut, gc, UR_BOC, UR_TOC );
}
#endif


static void _checkDataStack( UThread* ut, UCollector* gc )
{
#ifndef LANG_RUNE
    assert( ur_is(UR_BOS, UT_UNSET) );
#endif
    assert( UR_TOS >= UR_BOS );

    ur_gcMarkCells( ut, gc, UR_BOS + 1, UR_TOS + 1 );
}


#if defined(GC_REPORT) || defined(DEBUG)
typedef struct
{
    UGCArray  bin;
    UGCArray  blocks;
    UGCArray  resources;
}
DataStore;


void ur_gcReport( DataStore* store )
{
    int used;
    int unused;

    dprint( "  Array    Buf       Max Used  Free    Bytes  Bytes Wasted\n" );
    dprint( "  --------------------------------------------------------\n" );
    {
        UBinary* it  = (UBinary*) store->bin.arr.ptr.v;
        UBinary* end = it + store->bin.arr.used;

        used = 0;
        unused = 0;
        while( it != end )
        {
            if( it->avail > 0 )
            {
                used   += it->used;
                unused += it->avail - it->used;
            }
            ++it;
        }
        dprint( "  Binaries %p   %4d   %4d   %7d   %7d\n",
                store->bin.arr.ptr.v,
                store->bin.arr.used,
                store->bin.freeCount,
                used, unused );
    }
    {
        UBlock* it  = (UBlock*) store->blocks.arr.ptr.v;
        UBlock* end = it + store->blocks.arr.used;

        used = 0;
        unused = 0;
        while( it != end )
        {
            if( it->avail > 0 )
            {
                used   += it->used;
                unused += it->avail - it->used;
            }
            ++it;
        }
        dprint( "  Blocks   %p   %4d   %4d   %7d   %7d\n",
                store->blocks.arr.ptr.v,
                store->blocks.arr.used,
                store->blocks.freeCount,
                used * 16, unused * 16 );
    }
    dprint( "\n" );
}
#endif


/**
  Perform garbage collection.

  A tracing mark-sweep collector.
  Starts with global context & data stack and only traces used values.
*/
void ur_recycle( UThread* ut )
{
    UCollector gc;
    int byteSize;
    uint8_t* markset;
    uint8_t* doneset;
    int i;
    int bitm;
    int ai;
    UBlock* blk;
    int blkCount;
    UrlanEnv* env = ut->env;

#ifdef GC_TIME
    clock_t t1, t1e;
#endif

#define GC_BITSET(bin,ga,offset) \
    byteSize = ga.arr.used - offset; \
    byteSize = (byteSize + 7) / 8; \
    ur_arrayInit(&bin, sizeof(uint8_t), byteSize); \
    bin.used = byteSize; \
    memSet(bin.ptr.v, 0, bin.avail)


#ifdef GC_REPORT
    int pass = 0;
    dprint( "\nRecycle report:\n\n" );
    ur_gcReport( (DataStore*) ut );
#endif

#ifdef GC_TIME
    t1 = clock();
#endif

    GC_BITSET( gc.bsBin,   ut->bin,       0 );
    GC_BITSET( gc.bsBlock, ut->blocks,    0 );
    GC_BITSET( gc.bsRes,   ut->resources, 0 );

    GC_BITSET( gc.blkChecked, ut->blocks, 0 );

    gc.ut = ut;

#ifdef PAIRPOOL_H
    ur_pairPoolGCClear();
#endif

    if( env->dtCount > UT_BI_COUNT )
    {
        // Tell custom types marking will begin.
        ai = 0;
        for( i = UT_BI_COUNT; i < env->dtCount; ++i )
        {
            env->customDT[ ai ].recycle( env, UR_GC_PHASE_MARK );
            ++ai;
        }
    }


    // Mark all complex values used.
    // Start by checking the data stack, global context and any blocks
    // currently being referenced.

    // Check global context.

    blk = (UBlock*) ut->blocks.arr.ptr.v;

    _checkBlock( ut, &gc, blk + BLK_THREAD_HOLD );
    _checkBlock( ut, &gc, blk + BLK_GLOBAL_VAL );
    _checkBlock( ut, &gc, blk + BLK_CTX_STACK );

    doneset = gc.blkChecked.ptr.b;
    ur_setBit( doneset, BLK_GLOBAL_WORD );
    ur_setBit( doneset, BLK_GLOBAL_VAL );
    ur_setBit( doneset, BLK_CTX_STACK );

#if 1
    gc.bsBlock.ptr.b[0] |= 0x0f;    // Quick version of code below.
#else
    ur_setBit( gc.bsBlock.ptr.b, BLK_THREAD_HOLD );
    ur_setBit( gc.bsBlock.ptr.b, BLK_GLOBAL_WORD );
    ur_setBit( gc.bsBlock.ptr.b, BLK_GLOBAL_VAL );
    ur_setBit( gc.bsBlock.ptr.b, BLK_CTX_STACK );
    //ur_setBit( gc.bsBlock.ptr.b, BLK_DSTACK );
#endif

    ur_setBit( gc.bsBin.ptr.b, BIN_THREAD_TMP );

    _checkDataStack( ut, &gc );
    _checkControlStack( ut, &gc );


    // Blocks and objects may refer to other blocks and objects so we must
    // check until no unchecked items are found.

    do
    {
        blkCount = 0;

        // Mark complex values used in blocks.
        {
        UBlock* bit;
        UBlock* bend;

        i = 0;
        markset = gc.bsBlock.ptr.b;
        doneset = gc.blkChecked.ptr.b;

        bit  = blk;
        bend = blk + ut->blocks.arr.used;

        while( bit != bend )
        {
            ai   = i >> 3;
            bitm = 1 << (i & 7);
            if( markset[ ai ] & bitm )              // ur_bitIsSet(markset, i)
            {
                if( ! (doneset[ ai ] & bitm) )      // ur_bitIsSet(doneset, i)
                {
                    doneset[ ai ] |= bitm;          // ur_setBit(doneset, i)
                    ++blkCount;
                    _checkBlock( ut, &gc, bit );
                }
            }
            ++bit;
            ++i;
        }
        }

#ifdef GC_REPORT
        dprint( "  GC pass %d - blocks checked: %d\n", pass, blkCount );
        ++pass;
#endif
    }
    while( blkCount );


    if( env->dtCount > UT_BI_COUNT )
    {
        // Tell custom types sweep will begin.
        ai = 0;
        for( i = UT_BI_COUNT; i < env->dtCount; ++i )
        {
            env->customDT[ ai ].recycle( env, UR_GC_PHASE_SWEEP );
            ++ai;
        }
    }

#ifdef PAIRPOOL_H
    ur_pairPoolGCSweep();
#endif

    _sweepResources( env->customDT, &gc.bsRes, &ut->resources );
    _sweepArray( &gc.bsBlock, &ut->blocks );
    _sweepArray( &gc.bsBin,   &ut->bin );

    ur_arrayFree( &gc.blkChecked );

    ur_arrayFree( &gc.bsRes );
    ur_arrayFree( &gc.bsBlock );
    ur_arrayFree( &gc.bsBin );

#ifdef GC_TIME
    t1e = clock() - t1;
    printf( "gc seconds: %g\n", ((double) t1e) / CLOCKS_PER_SEC );
#endif

#ifdef GC_REPORT
    dprint( "  %d passes\n\n", pass );
    ur_gcReport( (DataStore*) ut );
#endif
}


/*--------------------------------------------------------------------------*/


#ifdef TRACK_MALLOC
typedef struct OListNode OListNode;

struct OListNode
{
    OListNode*  prev;
    OListNode*  next;
};

typedef struct
{
    OListNode   head;
    OListNode   tail;
}
OList;

static void _listAppend( OListNode* node, OListNode* after )
{
    node->prev = after;
    node->next = after->next;
    after->next->prev = node;
    after->next = node;
}

static void _listRemove( OListNode* node )
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->prev = node->next = 0;
}


typedef struct
{
    OListNode link;
    void* ptr;
    size_t size;
}
MallocRecord;


static OList _list = { {0,&_list.tail}, {&_list.head,0} };


void* memAlloc( size_t size )
{
    MallocRecord* rec;
    void* ptr = malloc( size );

    if( ptr )
    {
        // Add ptr to list.

        rec = (MallocRecord*) malloc( sizeof(MallocRecord) );
        assert( rec );
        rec->ptr  = ptr;
        rec->size = size;
        _listAppend( &rec->link, &_list.head );
    }

    return ptr;
}


void memFree( void* ptr )
{
    OListNode* it;
    MallocRecord* rec;

    // Remove ptr from list.

    rec = 0;
    it = _list.head.next;
    while( it->next )
    {
        if( ((MallocRecord*) it)->ptr == ptr )
        {
            rec = (MallocRecord*) it;
            break;
        }
        it = it->next;
    }

    if( rec )
    {
        free( rec->ptr );
        _listRemove( &rec->link );
        free( rec );
    }
    else
    {
        cprint( "memFree - %p was not allocted with memAlloc!\n", ptr );
    }
}


void memReport( int verbose )
{
    size_t total;
    int count;
    OListNode* it;
    MallocRecord* rec;

    cprint( "memReport:\n" );

    count = total = 0;
    it = _list.head.next;
    while( it->next )
    {
        rec = (MallocRecord*) it;

        total += rec->size;
        ++count;

        if( verbose )
            cprint( "  %d bytes at %p\n", rec->size, rec->ptr );

        it = it->next;
    }

    cprint( "  %d allocations\n  %d bytes\n", count, total );
}


void orMemoryNative( UCell* a1 )
{
    (void) a1;
    memReport( 0 );
}
#endif


/*EOF*/