gcimpl.cpp

"More for C++" is a class library that provides some features that are usually common for object ori

//
//  This file is part of the "More for C++" library
//
//  Copyright (c) 1999-2003 by Thorsten Goertz ([e-mail])
//
//  The "More for C++" library is free software; you can redistribute it and/or
//  modify it under the terms of the license that comes with this package.
//
//  Read "license.txt" for more details.
//
//  THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
//  WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
//  OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.

////////////////////////////////////////////////////////////////////////////////

#include <cstring>
#include <more/compiler.hpp>
#include <more/create.hpp>
#include <more/synchronized.hpp>
#include "bitmask.hpp"
#include "gcimpl.hpp"

using namespace more;
using namespace more::core;
using namespace more::os;
using namespace more::util;

////////////////////////////////////////////////////////////////////////////////

typedef unsigned char byte;

////////////////////////////////////////////////////////////////////////////////

static GCImpl gc;
static size_t magicKey = 0x22021969;
static char magicPattern[4] = { 0x55, 0x55, 0x55, 0x55 };

////////////////////////////////////////////////////////////////////////////////

void GCImpl::init
(
  HeapManager* pHeapManager
)
{
  if( pHeapManager == 0 )
  {
#ifdef CC_VISUAL_C
    pHeapManager = &aligningHeapManager;
#else
    pHeapManager = &defaultHeapManager;
#endif
  }

  gc.m_pHeapManager = pHeapManager;
  gc.m_pLastObject = 0;
  gc.m_nNoOfObjects = 0;
  gc.m_nNoOfTareObjects = 0;
  gc.m_bCollecting = false;
  gc.m_pMarkStack = new ObjectStack( );
  gc.m_ppMutex = new p<Mutex>;
  gc.m_ppCollectorThread = new p<Thread>;

  *gc.m_ppMutex = Mutex::create( );
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::shutDown( )
{
  *gc.m_ppCollectorThread = 0;
  *gc.m_ppMutex = 0;

  while( gc.m_nNoOfObjects > 0 )
  {
    collectObjects( );
  }

  delete gc.m_ppCollectorThread;
  delete gc.m_ppMutex;
  delete gc.m_pMarkStack;

  gc.m_ppCollectorThread = 0;
  gc.m_ppMutex = 0;
  gc.m_pMarkStack = 0;
  gc.m_bCollecting = false;
  gc.m_nNoOfTareObjects = 0;
  gc.m_nNoOfObjects = 0;
  gc.m_pLastObject = 0;
  gc.m_pHeapManager = 0;
}

////////////////////////////////////////////////////////////////////////////////

void* GCImpl::createObject
(
  size_t  nSizeOfObject,
  bool    bMayBeNode
)
{
  Handle* pHandle;
  size_t  nConcreteSize = sizeof( Handle ) + nSizeOfObject;
  size_t  nNoOfBytesForBits;

  if( bMayBeNode )
  {
    nNoOfBytesForBits = BitMask::calcSize( nSizeOfObject );
    nConcreteSize += nNoOfBytesForBits;
  }

  synchronized( *gc.m_ppMutex )
  {
    pHandle = ( Handle* ) gc.m_pHeapManager -> createObject( nConcreteSize );

  } end_synchronized

  pHandle -> m_nFlags = 0x00000000;
  pHandle -> m_pPrevObject = 0;
  pHandle -> m_pFinalizable = 0;
  pHandle -> m_nSizeOfObject = nSizeOfObject;
  pHandle -> m_nNoOfRootPointers = 1; // !!!
  pHandle -> m_pForRootPointers = 0;
  pHandle -> m_pForPointers = 0;
  pHandle -> m_pMagicKey = magicKey;

  if( bMayBeNode )
  {
    byte*   pBytesForBits = ( byte* ) ( pHandle + 1 ) + nSizeOfObject;
    BitMask bits( pBytesForBits, nNoOfBytesForBits, nSizeOfObject );

    memset( pHandle + 1, magicPattern[0], nSizeOfObject );
    gc.setNodeFlag( pHandle, true );
    bits.clear( );
  }

  gc.addObject( pHandle );

  return pHandle + 1;
}

////////////////////////////////////////////////////////////////////////////////

bool GCImpl::isRootPointer
(
  void** ppObject
)
{
  size_t* pKey = ( size_t* ) ppObject;

  return pKey[1] != magicKey;
}

////////////////////////////////////////////////////////////////////////////////

Handle* GCImpl::resolveObject
(
  void* pObject
)
{
  size_t* pKey = ( size_t* ) pObject;

  while( pKey[-1] != magicKey )
  {
    pKey--;
  }

  return ( ( Handle* ) pKey ) - 1;
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::initPointer
(
  void**&       rppObject,
  void*         pObject,
  Finalizable*  pFinalizable
)
{
  bool    bIsRootPointer = true;
  byte*   pFirstByteOfObject = 0;
  size_t  nSizeOfObject = 0;
  size_t  nDistance = 0;

  if( memcmp( &rppObject, magicPattern, 4 ) == 0 )
  {
    synchronized( *gc.m_ppMutex )
    {
      Handle* pHandle = gc.getLastObject( );

      while( bIsRootPointer == true && pHandle != 0 )
      {
        byte* pFirstByteOfPointer = ( byte* ) &rppObject;

        pFirstByteOfObject = ( byte* ) ( pHandle + 1 );
        nSizeOfObject = pHandle -> m_nSizeOfObject;
        nDistance = size_t( pFirstByteOfPointer - pFirstByteOfObject );

        if( nDistance < nSizeOfObject )
        {
          bIsRootPointer = false;
        }

        pHandle = gc.getPreviousObject( pHandle );
      }

    } end_synchronized
  }

  assignObject( rppObject, pObject, pFinalizable, bIsRootPointer );

  if( bIsRootPointer == false )
  {
    byte*   pBytesForBits = pFirstByteOfObject + nSizeOfObject;
    size_t  nNoOfBytesForBits = BitMask::calcSize( nSizeOfObject );
    BitMask bitMask( pBytesForBits, nNoOfBytesForBits, nSizeOfObject );

    bitMask.setBit( nDistance, true );
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::assignObject
(
  void**&       rppObject,
  void*         pObject,
  Finalizable*  pFinalizable,
  bool          bIsRootPointer
)
{
  Handle* pHandle;
  bool    bUnlockUnassignedObject = false;

  if( pObject == 0 )
  {
    pHandle = &nilHandle;
  }
  else
  {
    pHandle = resolveObject( pObject );

    if( pHandle -> m_pForPointers == 0 )
    {
      bUnlockUnassignedObject = true;

      pHandle -> m_pFinalizable = pFinalizable;
      pHandle -> m_pForRootPointers = pObject;
      pHandle -> m_pForPointers = pObject;
    }
  }

  if( bIsRootPointer )
  {
    rppObject = &pHandle -> m_pForRootPointers;
    pHandle -> m_nNoOfRootPointers++;
  }
  else
  {
    rppObject = &pHandle -> m_pForPointers;
  }

  if( bUnlockUnassignedObject )
  {
    pHandle -> m_nNoOfRootPointers--; // !!!
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::forgetObject
(
  void**& rppObject,
  bool    bIsRootPointer
)
{
  Handle* pHandle;

  if( *rppObject == 0 )
  {
    pHandle = &nilHandle;
  }
  else
  {
    pHandle = resolveObject( *rppObject );
  }

  if( bIsRootPointer )
  {
    rppObject = &nilHandle.m_pForRootPointers;
    pHandle -> m_nNoOfRootPointers--;
  }
  else
  {
    rppObject = &nilHandle.m_pForPointers;
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::forgetUnassignedObject
(
  void* pObject
)
{
  Handle* pHandle = resolveObject( pObject );

  if( pHandle -> m_pForPointers == 0 )
  {
    pHandle -> m_pFinalizable = 0;
    pHandle -> m_pForRootPointers = pObject;
    pHandle -> m_pForPointers = pObject;
    pHandle -> m_nNoOfRootPointers--;
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::startCollectorThread( )
{
  class Runner: public Thread::Runnable
  {
    virtual void run
    (
      const p<Thread::Controller>& pController
    )
    {
      while( pController -> scheduled( ) )
      {
        GCImpl::collectObjects( );
        Thread::sleep( 1000 );
      }
    }
  };

  if( *gc.m_ppCollectorThread == 0 )
  {
    synchronized( *gc.m_ppMutex )
    {
      if( *gc.m_ppCollectorThread == 0 )
      {
        *gc.m_ppCollectorThread = Thread::create( );
        ( *gc.m_ppCollectorThread ) -> execute( CREATE Runner( ) );
      }

    } end_synchronized
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::stopCollectorThread( )
{
  bool bStopThread = false;

  if( *gc.m_ppCollectorThread != 0 )
  {
    synchronized( *gc.m_ppMutex )
    {
      if( *gc.m_ppCollectorThread != 0 )
      {
        bStopThread = true;
      }

    } end_synchronized
  }

  if( bStopThread )
  {
    ( *gc.m_ppCollectorThread ) -> terminate( );
    ( *gc.m_ppCollectorThread ) -> join( );

    synchronized( *gc.m_ppMutex )
    {
      *gc.m_ppCollectorThread = 0;

    } end_synchronized
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::declareObjectsTare( )
{
  gc.m_nNoOfTareObjects = gc.m_nNoOfObjects;
}

////////////////////////////////////////////////////////////////////////////////

size_t GCImpl::getNoOfObjects( )
{
  return gc.m_nNoOfObjects - gc.m_nNoOfTareObjects;
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::collectObjects( )
{
  bool bCollectNow = false;

  if( gc.m_bCollecting == false )
  {
    synchronized( *gc.m_ppMutex )
    {
      if( gc.m_bCollecting == false )
      {
        gc.m_bCollecting = true;
        bCollectNow = true;
      }

    } end_synchronized
  }

  if( bCollectNow )
  {
    gc.markObjects( );
    gc.unmarkRootObjectTree( );
    gc.finalizeMarkedObjects( );
    gc.sweepMarkedObjects( );

    synchronized( *gc.m_ppMutex )
    {
      gc.m_bCollecting = false;

    } end_synchronized
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::addObject
(
  Handle* pObject
)
{
  synchronized( *m_ppMutex )
  {
    pObject -> m_pPrevObject = m_pLastObject;
    m_pLastObject = pObject;
    m_nNoOfObjects++;

  } end_synchronized
}

////////////////////////////////////////////////////////////////////////////////

Handle* GCImpl::getLastObject( ) const
{
  Handle* pResult;

  synchronized( *m_ppMutex )
  {
    pResult = m_pLastObject;

  } end_synchronized

  return pResult;
}

////////////////////////////////////////////////////////////////////////////////

Handle* GCImpl::getPreviousObject( Handle *pHandle ) const
{
  Handle* pResult;

  synchronized( *m_ppMutex )
  {
    pResult = pHandle -> m_pPrevObject;

  } end_synchronized

  return pResult;
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::removeObject
(
  Handle* pObject,
  Handle* pNextObject
)
{
  synchronized( *m_ppMutex )
  {
    m_nNoOfObjects--;

    if( pObject == m_pLastObject )
    {
  //  assert( pNextObject == 0 );
      m_pLastObject = pObject -> m_pPrevObject;
    }
    else
    {
  //  assert( pNextObject != 0 );
      pNextObject -> m_pPrevObject = pObject -> m_pPrevObject;
    }

  } end_synchronized
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::markObjects( )
{
  Handle* pHandle = getLastObject( );

  while( pHandle != 0 )
  {
    setGarbageFlag( pHandle, true );

    if( pHandle -> m_nNoOfRootPointers > 0 )
    {
      m_pMarkStack -> pushObject( pHandle );
    }

    pHandle = getPreviousObject( pHandle );
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::unmarkRootObjectTree( )
{
  while( m_pMarkStack -> isEmpty( ) == false )
  {
    Handle* pHandle = ( Handle* ) m_pMarkStack -> popObject( );

    if( objectIsGarbage( pHandle ) )
    {
      setGarbageFlag( pHandle, false );

      if( objectMayBeNode( pHandle ) )
      {
        unmarkChildObjects( pHandle );
      }
    }
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::unmarkChildObjects
(
  Handle* pHandle
)
{
  size_t  i = 0;
  byte*   pObject = ( byte* ) ( pHandle + 1 );
  size_t  nSizeOfObject = pHandle -> m_nSizeOfObject;
  byte*   pBytesForBits = pObject + nSizeOfObject;
  size_t  nNoOfBytesForBits = BitMask::calcSize( nSizeOfObject );
  BitMask bitMask( pBytesForBits, nNoOfBytesForBits, nSizeOfObject );

  while( i < nSizeOfObject )
  {
    if( bitMask.getBit( i ) )
    {
      void*** pppChildObject = ( void*** ) ( pObject + i );
      void**  ppChildObject = *pppChildObject;
      void*   pChildObject = *ppChildObject;

      if( pChildObject != 0 )
      {
        pHandle = resolveObject( pChildObject );

        if( pHandle != 0 && objectIsGarbage( pHandle ) )
        {
          m_pMarkStack -> pushObject( pHandle );
        }
      }

      i += sizeof( pppChildObject );
    }
    else
    {
      i += 2;
    }
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::finalizeMarkedObjects( )
{
  Handle* pObject = getLastObject( );

  while( pObject != 0 )
  {
    if( objectIsGarbage( pObject ) )
    {
      Finalizable* pFinalizable = pObject -> m_pFinalizable;

      if( pFinalizable != 0 )
      {
        pFinalizable -> finalize( );
      }
    }

    pObject = getPreviousObject( pObject );
  }
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::sweepMarkedObjects( )
{
  ObjectStack garbage;

  synchronized( *gc.m_ppMutex )
  {
    Handle* pPreviousObject = 0;
    Handle* pObject = getLastObject( );

    while( pObject != 0 )
    {
      if( objectIsGarbage( pObject ) )
      {
        Handle* pGarbage = pObject;

        garbage.pushObject( pGarbage );
        pObject = getPreviousObject( pGarbage );
        removeObject( pGarbage, pPreviousObject );
      }
      else
      {
        pPreviousObject = pObject;
        pObject = getPreviousObject( pObject );
      }
    }

    while( !garbage.isEmpty( ) )
    {
      m_pHeapManager -> destroyObject( garbage.popObject( ) );
    }

    m_pHeapManager -> compactHeap( );

  } end_synchronized
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::setNodeFlag
(
  Handle* pHandle,
  bool    bObjectMayBeNode
)
{
  if( bObjectMayBeNode )
  {
    pHandle -> m_nFlags |= 0x00000001;
  }
  else
  {
    pHandle -> m_nFlags &= 0xFFFFFFFE;
  }
}

////////////////////////////////////////////////////////////////////////////////

bool GCImpl::objectMayBeNode
(
  Handle* pHandle

) const
{
  return ( pHandle -> m_nFlags & 0x00000001 ) == 0x00000001;
}

////////////////////////////////////////////////////////////////////////////////

void GCImpl::setGarbageFlag
(
  Handle* pHandle,
  bool    bGarbage
)
{
  if( bGarbage )
  {
    pHandle -> m_nFlags |= 0x00000002;
  }
  else
  {
    pHandle -> m_nFlags &= 0xFFFFFFFD;
  }
}

////////////////////////////////////////////////////////////////////////////////

bool GCImpl::objectIsGarbage
(
  Handle* pHandle

) const
{
  return ( pHandle -> m_nFlags & 0x00000002 ) == 0x00000002;
}

////////////////////////////////////////////////////////////////////////////////

Handle GCImpl::nilHandle = { 0, 0, 0, 0, 0, 0, 0, magicKey };
DefaultHeapManager GCImpl::defaultHeapManager;
AligningHeapManager GCImpl::aligningHeapManager;

////////////////////////////////////////////////////////////////////////////////