root/trunk/orca/gc.c

/*============================================================================
    ORCA 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 "ovalue.h"
#include "internal.h"
#include "orca_atoms.h"


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

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


/**
  Excludes all current data from all future garbage collection.
*/
void orLockGarbageCollector()
{
    orEnv->freeBlocks.sweepStart  = orEnv->blocks.used;
    orEnv->freeStrings.sweepStart = orEnv->strings.used;
    orEnv->sweepStartAtom         = orEnv->atoms.used;
}


static OArray*   _abuf;
static OArrayGC* _agc;

static void _freeArrayX( OArray* arr )
{
    if( arr->buf )
    {
        memFree( arr->buf );
        arr->buf  = 0;
    }

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

    // Link to free list.
    arr->used  = _agc->freeList;
    _agc->freeList = arr - _abuf;

    _agc->count += 1;
}


/**
  Do not call orFreeBlock() from inside garbage collector.
*/
void orFreeBlock( OIndex blkN )
{
    _agc  = &orEnv->freeBlocks;
    _abuf = (OArray*) orEnv->blocks.buf;
    _freeArrayX( _abuf + blkN );
}


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

static void orSweepArray( OArray* mark, OArrayGC* af, OArray* arr )
{
    int start = af->sweepStart;
    OArray* tmp;
    OArray* ait = ((OArray*) arr->buf) + start;
    uint8_t* it  = mark->byteArray;
    uint8_t* end = it + mark->used;
    int count = arr->used - start;


    _abuf = (OArray*) arr->buf;
    _agc  = af;

    // 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( "orSweepArray %p start: %d elem: %d 0x%02x\n",
                    arr->buf, start, ait - ((OArray*) 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 = ((OArray*) arr->buf) + arr->used - 1;
    while( arr->used && (ait->avail == -1) )
    {
        --ait;
        --arr->used;
        *_freeCount -= 1;
    }
#endif
}



static OBinary bsBlk;
static OBinary bsStr;
static OBinary blkChecked;

#ifdef OR_CONFIG_NUMBER_ARRAYS
static OBinary bsDecArr;
static OBinary bsIntArr;
#endif


static void checkBlock( OBlock* blk )
{
    int idx;
    OValue* it  = blk->values;
    OValue* end = it + blk->used;

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

    if( ! it )
        return;

    while( it != end )
    {
        switch( it->type )
        {
            case OT_WORD:
            case OT_SETWORD:
            //case OT_LITWORD:      // Only atom is used in lit-words?
                idx = it->word.wordBlk - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );

                idx = it->word.context - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );
                break;

            case OT_STRING:
            case OT_FILE:
            case OT_ISSUE:
            case OT_TAG:
            case OT_BINARY:
            case OT_BITSET:
            case OT_MATRIX:
                idx = it->index - orEnv->freeStrings.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsStr.byteArray, idx );
                break;

#ifdef OR_CONFIG_NUMBER_ARRAYS
            case OT_DEC_ARRAY:
                idx = it->index - orEnv->freeDecArr.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsDecArr.byteArray, idx );
                break;

            case OT_INT_ARRAY:
                idx = it->index - orEnv->freeIntArr.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsIntArr.byteArray, idx );
                break;
#endif

            case OT_ERROR:
                if( orErrorType(it) != OR_ERROR_THROW )
                {
                    idx = it->error.msg - orEnv->freeStrings.sweepStart;
                    if( idx >= 0 )
                        orSetBit( bsStr.byteArray, idx );
                }

                idx = it->error.block - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );
                break;

            case OT_OBJECT:
            case OT_PORT:
                idx = it->ctx.wblkN - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                {
                    // Word block only contains words so block is marked
                    // as checked.
                    int ai   = idx >> 3;
                    int bitm = 1 << (idx & 7);
                    bsBlk.byteArray[ ai ] |= bitm;
                    blkChecked.byteArray[ ai ] |= bitm;
                }

                idx = it->ctx.vblkN - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );
                break;

            case OT_FUNCTION:
                idx = it->func.specBlk - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );

                idx = it->func.bodyBlk - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );

                idx = it->func.context - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                {
                    orSetBit( bsBlk.byteArray, idx );
                }
                else if( it->func.context )
                {
                    // Must check contents of argument block even if below
                    // sweepStart.
                    // During recursion this will waste some time
                    // rechecking stack values.
                    checkBlock( orBLOCKS + it->func.context );
                }
                break;

            case OT_LIST:
            case OT_BLOCK:
            case OT_PAREN:
                idx = it->index - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                {
                    int ai   = idx >> 3;
                    int bitm = 1 << (idx & 7);
                    bsBlk.byteArray[ ai ] |= bitm;
                    if( ! (blkChecked.byteArray[ ai ] & bitm) )
                    {
                        blkChecked.byteArray[ ai ] |= bitm;
                        checkBlock( orBLOCKS + it->index );
                    }
                }
                break;

            case OT_PATH:
            case OT_SETPATH:
            case OT_LITPATH:
                idx = it->index - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );
                break;
        }
        ++it;
    }
}


static void checkHolds( OHold* it, OHold* end )
{
    int idx;
    while( it != end )
    {
        switch( it->dataType )
        {
            case OT_BLOCK:
            case OT_PAREN:
            case OT_PATH:
            case OT_SETPATH:
            case OT_LIST:
                idx = it->which - orEnv->freeBlocks.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsBlk.byteArray, idx );
                break;

            case OT_STRING:
            case OT_FILE:
            case OT_ISSUE:
            case OT_TAG:
            case OT_BINARY:
            case OT_BITSET:
            case OT_MATRIX:
                idx = it->which - orEnv->freeStrings.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsStr.byteArray, idx );
                break;

#ifdef OR_CONFIG_NUMBER_ARRAYS
            case OT_DEC_ARRAY:
                idx = it->which - orEnv->freeDecArr.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsDecArr.byteArray, idx );
                break;

            case OT_INT_ARRAY:
                idx = it->which - orEnv->freeIntArr.sweepStart;
                if( idx >= 0 )
                    orSetBit( bsIntArr.byteArray, idx );
                break;
#endif

            case OT_UNSET:
                break;

            case OT_OBJECT:
            case OT_PORT:
            default:
                assert( 0 && "Reference type not handled" );
                break;
        }
        ++it;
    }
}


/*
   Check selected parts of system object.
   This will be needed as long as orLockGarbageCollector() is used.
*/
static void checkSystem()
{
    OValue* val;

    val = orLookupPath( OT_WORD, OR_ATOM_SYSTEM,
                        OT_WORD, OR_ATOM_SCRIPT,
                        OR_LPATH_END );
    if( val && orIs(val, OT_OBJECT ) )
    {
        checkBlock( orBlockPtr( val->ctx.vblkN ) );
    }
}


/*
   Mark values in OC_SETPATH CallRecords as used.
*/
static void checkCallStack()
{
    CallRecord* start;
    CallRecord* it;
    OValue* val;
    OArray* call;
    int idx;

    call = &orEnv->callStack;
    if( call->used > 2 )
    {
        start = (CallRecord*) call->buf;
        it = start + (call->used - 1);

        while( it != start )
        {
            if( it->opcode == OC_SETPATH )
            {
                it -= 2;
                val = (OValue*) it;
                switch( val->type )
                {
                    case OT_LIST:
                    case OT_BLOCK:
                    case OT_PAREN:
                    case OT_PATH:
                    case OT_SETPATH:
                    case OT_LITPATH:
                        idx = val->index - orEnv->freeBlocks.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsBlk.byteArray, idx );
                        break;

                    case OT_STRING:
                    case OT_FILE:
                    case OT_ISSUE:
                    case OT_TAG:
                    case OT_BINARY:
                    case OT_BITSET:
                    case OT_MATRIX:
                        idx = val->index - orEnv->freeStrings.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsStr.byteArray, idx );
                        break;

#ifdef OR_CONFIG_NUMBER_ARRAYS
                    case OT_DEC_ARRAY:
                        idx = val->index - orEnv->freeDecArr.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsDecArr.byteArray, idx );
                        break;

                    case OT_INT_ARRAY:
                        idx = val->index - orEnv->freeIntArr.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsIntArr.byteArray, idx );
                        break;
#endif
                    case OT_WORD:
                        idx = val->word.wordBlk - orEnv->freeBlocks.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsBlk.byteArray, idx );

                        idx = val->word.context - orEnv->freeBlocks.sweepStart;
                        if( idx >= 0 )
                            orSetBit( bsBlk.byteArray, idx );
                        break;

                    default:
                        assert( 0 && "set-path type not series! or word!" );
                        break;
                }
            }
            --it;
        }
    }
}


#ifdef DEBUG
void orShowGC()
{
    dprint( "  Array    Buf       Max Used  Free\n" );
    dprint( "  ---------------------------------\n" );
    dprint( "  Blocks   %p   %4d   %4d\n", orEnv->blocks.buf,
                                           orEnv->blocks.used,
                                           orEnv->freeBlocks.count );
    dprint( "  Strings  %p   %4d   %4d\n", orEnv->strings.buf,
                                           orEnv->strings.used,
                                           orEnv->freeStrings.count );
}
#endif


/**
  Perform garbage collection.

  A tracing mark-sweep collector.
  Starts with global context & data stack and only traces used values.
*/
void orCollectGarbage()
{
    int byteSize;
    uint8_t* markset;
    uint8_t* doneset;
    int i;
    int bitm;
    int ai;
    OBlock* blk;
    int blkCount;

#ifdef GC_TIME
    clock_t t1, t1e;
#endif

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


#ifdef GC_REPORT
    int pass = 0;
    dprint( "\norCollectGarbage() Report:\n\n" );
    orShowGC();
#endif

#ifdef GC_TIME
    t1 = clock();
#endif

    GC_BITSET( bsBlk, orEnv->blocks,     orEnv->freeBlocks.sweepStart );
    GC_BITSET( bsStr, orEnv->strings,    orEnv->freeStrings.sweepStart );

    GC_BITSET( blkChecked, orEnv->blocks,   orEnv->freeBlocks.sweepStart );

#ifdef OR_CONFIG_NUMBER_ARRAYS
    GC_BITSET( bsDecArr, orEnv->decArr,     orEnv->freeDecArr.sweepStart );
    GC_BITSET( bsIntArr, orEnv->intArr,     orEnv->freeIntArr.sweepStart );
#endif

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

    // Make sure there is no unhandled error.
    assert( orEnv->error == 0 );


    // Enable this if orLockGarbageCollector() is removed.
    //orSetBit( bsStr.byteArray, BIN_ATOM_NAMES );

    blk = (OBlock*) orEnv->blocks.buf;

    checkBlock( &orEnv->dataStack );
    checkBlock( blk + GLOBAL_CTXN );

    checkSystem();
    checkCallStack();

    checkHolds( orEnv->quickHolds,
                orEnv->quickHolds + orEnv->quickHoldsUsed );

    if( orEnv->holds.used )
    {
        OHold* hold;
        hold = (OHold*) orEnv->holds.buf;
        checkHolds( hold, hold + orEnv->holds.used );
    }


    // 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.
        {
        OBlock* bit;
        OBlock* bend;

        i = 0;
        markset = bsBlk.byteArray;
        doneset = blkChecked.byteArray;

        bit  = blk + orEnv->freeBlocks.sweepStart;
        bend = blk + orEnv->blocks.used;

        while( bit != bend )
        {
            ai   = i >> 3;
            bitm = 1 << (i & 7);
            if( markset[ ai ] & bitm )              // orBitIsSet(markset, i)
            {
                if( ! (doneset[ ai ] & bitm) )      // orBitIsSet(doneset, i)
                {
                    doneset[ ai ] |= bitm;          // orSetBit(doneset, i)
                    ++blkCount;
                    checkBlock( bit );
                }
            }
            ++bit;
            ++i;
        }
        }

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


    orSweepArray( &bsBlk, &orEnv->freeBlocks,  &orEnv->blocks );
    orSweepArray( &bsStr, &orEnv->freeStrings, &orEnv->strings );

#ifdef OR_CONFIG_NUMBER_ARRAYS
    orSweepArray( &bsDecArr, &orEnv->freeDecArr, &orEnv->decArr );
    orSweepArray( &bsIntArr, &orEnv->freeIntArr, &orEnv->intArr );

    orArrayFree( &bsDecArr );
    orArrayFree( &bsIntArr );
#endif

    orArrayFree( &blkChecked );

    orArrayFree( &bsBlk );
    orArrayFree( &bsStr );

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

#ifdef GC_REPORT
    dprint( "\n  %d passes\n", pass );
    orShowGC();
#endif
}


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


/**
  Creates a hold on a complex value so that it will not be garbage collected.
  Returns a handle to the hold.
*/
OIndex orHold( int type, OIndex which )
{
    OIndex index;
    OHold* hold;
    OArray* arr = &orEnv->holds;

    if( orEnv->freeHolds.count )
    {
        OArrayGC* gc = &orEnv->freeHolds;

        index = gc->freeList;
        hold = ((OHold*) arr->buf) + index;

        assert( gc->freeList > -1 );
        assert( hold->dataType == OT_UNSET );

        gc->freeList = hold->which;
        gc->count--;
    }
    else
    {
        index = arr->used;
        OA_EXPAND1( OHold, arr, hold );
    }

    //hold->refCount = 1;        // refCount is currently unused.
    hold->dataType = type;
    hold->which    = which;

    return index;
}


OIndex orHoldIndex( OIndex holdIndex )
{
    OHold* hold = ((OHold*) orEnv->holds.buf) + holdIndex;
    return hold->which;
}


/**
  Releases a hold created with orHold().
*/
void orRelease( OIndex holdIndex )
{
    OHold* hold;
    OArrayGC* gc;

    hold = ((OHold*) orEnv->holds.buf) + holdIndex;

    // Flag as unused.
    hold->dataType = OT_UNSET;

    // Link to free list.
    gc = &orEnv->freeHolds;
    hold->which = gc->freeList;
    gc->freeList = holdIndex;

    gc->count++;
}


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


#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 );
}


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


/*EOF*/