memory_manager.cxx

#include <memory_manager.hpp>
#include <gc++.hpp>
#include <common.hpp>
#include <VERSION>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <numeric>
#include <detail/gc++.hpp>
#include <boost/bind.hpp>

using namespace GCpp;
using namespace std;

namespace
{

GCPP_MUTEX global_gc_mutex;

struct BlockHeader
{
    MemoryAllocatorBase* allocator;
    BlockHeader* next;
    bool mark;
    
    BlockHeader (MemoryAllocatorBase* p_allocator)
    : allocator (p_allocator),
      mark (true)
    {}
};

inline
BlockHeader* EXTRACT_HEADER (void* p_data)
{
    return reinterpret_cast<BlockHeader*> (static_cast<Byte*> (p_data) - sizeof (BlockHeader));
}

inline
void* OBJECT (void* p_data)
{
    return static_cast<Byte*>(p_data) + sizeof (BlockHeader);
}

inline
GCBasePointer* CALC_POINTER (void* p_data, size_t p_offset)
{
    return reinterpret_cast<GCBasePointer*> (static_cast<Byte*> (p_data) + p_offset);
}

typedef size_t (MemoryAllocatorBase::*SumMember) ();

struct Sum : binary_function<size_t, MemoryAllocatorBase*, size_t>
{
    SumMember f_sum;
    
    Sum (SumMember p_sum)
    : f_sum (p_sum)
    {}
    
    size_t operator() (size_t p_value, MemoryAllocatorBase* p_item)
    {
        return p_value + (p_item->*f_sum) ();
    }
};

const Byte analyzed_tag = 0x01;
const Byte assured_tag = 0x02;

} // anonymous namespace

MemoryAllocatorBase::MemoryAllocatorBase (size_t p_block_size)
: FixedSizeAllocator (p_block_size + sizeof (BlockHeader)),
  f_status (0),
  f_destroyed (0),
  f_allocated (0),
  f_blocks (0)
{
    GC::f_allocators.push_back (this);
}

MemoryAllocatorBase::~MemoryAllocatorBase ()
{
    GC::f_allocators.remove (this);
}

void MemoryAllocatorBase::analyze (void* p_block)
{
    Byte* org (static_cast<Byte*> (p_block));
    Byte* ptr (org);
    int lmt (block_size () - sizeof (void*) - sizeof (BlockHeader));
    
    while (ptr - org < lmt)
    {
        if (GCPointerManager::is_pointer (ptr))
        {
            f_offsets.push_back (ptr - org);
            ptr += sizeof (void*);
        }
        else
            ++ptr;
    }
    
    f_status |= analyzed_tag;
}

void MemoryAllocatorBase::mark_contained_pointers (void* p_block)
{
    if (f_status % 2 == 0)
        analyze (p_block);
    
    vector<size_t>::iterator itr (f_offsets.begin ());
    vector<size_t>::iterator end (f_offsets.end ());
    
    vector<size_t> err;
    
    for (; itr != end; ++itr)
    {
        GCBasePointer* ptr (CALC_POINTER (p_block, *itr));
        
        // if we have completed at least one complete cycle, we do not validate the
        // pointers any more, because we have done it several times now and are
        // reasonable sure, that the pointers calculated from the f_offsets array are valid
        if (f_status & assured_tag or GCPointerManager::is_pointer (ptr))
            static_cast<GCBasePointer*> (ptr)->mark ();
        else
            err.push_back (*itr);
    }
    
    if (not err.empty ())
    {
        vector<size_t>::iterator rtr (err.begin ());
        vector<size_t>::iterator rnd (err.end ());
    
        for (; rtr != rnd; ++rtr)
            f_offsets.erase (remove (f_offsets.begin (), f_offsets.end (), *rtr), f_offsets.end ());
    }
}

void MemoryAllocatorBase::sweep ()
{
    BlockHeader* hdr (static_cast<BlockHeader*>(f_blocks));
    f_blocks = 0;
    size_t dst (0);
    
    while (hdr)
    {
        assert (hdr->allocator == this);
        BlockHeader* del (hdr);
        
        if (not hdr->mark)
        {
            hdr = hdr->next;
            f_destroy_item (OBJECT (del));
            del->allocator = 0;
            free (del);
            ++dst;
        }
        else
        {
            hdr->mark = false;
            hdr = hdr->next;
            del->next = static_cast<BlockHeader*>(f_blocks);
            f_blocks = del;
        }
    }
    
    f_destroyed += dst;
    f_status |= assured_tag;
}

void MemoryAllocatorBase::unmark ()
{
    BlockHeader* hdr (static_cast<BlockHeader*>(f_blocks));
    
    while (hdr)
    {
        assert (hdr->allocator == this);
        hdr->mark = false;
        hdr = hdr->next;
    }
}

void* MemoryAllocatorBase::malloc ()
{
    GCPP_LOCK mlc (global_gc_mutex);
    
    Byte* dat (GC::stopped () ? static_cast<Byte*> (FixedSizeAllocator::malloc ()) : static_cast<Byte*> (internal_malloc ()));
    
    if (dat == 0)
    {
        size_t old (f_destroyed);
        
        GC::internal_collect ();
        
        if (old != f_destroyed)
            dat = static_cast<Byte*> (internal_malloc ());
        else
        {
            dat = static_cast<Byte*> (internal_add_block ());
            GC::f_threshold += GC::f_threshold / 4;
        }
    }
    
    BlockHeader* blk (new (dat) BlockHeader (this));
    blk->next = static_cast<BlockHeader*> (f_blocks);
    f_blocks = blk;
    
    ++f_allocated;
    
    return OBJECT (dat);
}

void* MemoryAllocatorBase::confirm (void* p_storage)
{
    BlockHeader* hdr (EXTRACT_HEADER (p_storage));
    
    if (hdr->allocator == this)
        return p_storage;
    
    return 0;
}

bool GC::f_stop (false);
size_t GC::f_allocated (0);
size_t GC::f_threshold (50000000);
IntrusiveList<MemoryAllocatorBase> GC::f_allocators;

void GC::start ()
{
    f_stop = false;
}

void GC::stop ()
{
    f_stop = true;
}

void GC::mark (void* p_block)
{
    if (not static_cast<GCBasePointer*> (p_block)->is_contained ())
        static_cast<GCBasePointer*> (p_block)->mark ();
}

void GC::mark_recursively (void* p_pointer)
{
    GCBasePointer* ptr (static_cast<GCBasePointer*> (p_pointer));
    
    if (ptr->storage ())
    {
        BlockHeader* hdr (EXTRACT_HEADER (ptr->storage ()));
            
        // we were already here, return to avoid endless recursion
        if (hdr->mark)
            return;
                
        hdr->mark = true;
        hdr->allocator->mark_contained_pointers (ptr->storage ());
    }
}

void GC::internal_collect ()
{
    if (f_allocated < f_threshold)
        return;
    
    if (not f_stop)
    {
        for_each (GCPointerManager::begin (), GCPointerManager::end (), mark);
        for_each (f_allocators.begin (), f_allocators.end (), boost::bind (&MemoryAllocatorBase::sweep, _1));
    }
}

void GC::collect ()
{
    GCPP_LOCK lck (global_gc_mutex);
    
    bool old (f_stop);
    f_stop = false;
    size_t alc (f_allocated);
    f_allocated = f_threshold;

    for_each (f_allocators.begin (), f_allocators.end (), boost::bind (&MemoryAllocatorBase::unmark, _1));
    internal_collect ();
    
    f_stop = old;
    f_allocated = alc;
}

bool GC::stopped ()
{
    return f_stop;
}

size_t GC::destroyed ()
{
    Sum sum (&MemoryAllocatorBase::destroyed);
    return accumulate (f_allocators.begin (), f_allocators.end (), 0, sum);
}

size_t GC::allocated ()
{
    Sum sum (&MemoryAllocatorBase::allocated);
    return accumulate (f_allocators.begin (), f_allocators.end (), 0, sum);
}

string GC::version ()
{
    return string (VERSION_STRING);
}

size_t GC::in_use ()
{
    return f_allocated;
}
        
size_t GC::threshold ()
{
    return f_threshold;
}
        
void GC::compact (bool p_new_limit)
{
    GCPP_LOCK lck (global_gc_mutex);
    for_each (f_allocators.begin (), f_allocators.end (), boost::bind (&MemoryAllocatorBase::compact, _1));
    
    if (p_new_limit)
        f_threshold = max (f_allocated, static_cast<size_t> (50000000));
}

void GC::finalize ()
{
    size_t old;
    
    do
    {
        old = GC::destroyed ();
        GC::collect ();
    } while (GC::destroyed () > old);
}

Byte* GCpp::OS_malloc (size_t p_size)
{
    Byte* ret (static_cast<Byte*> (::malloc (p_size + sizeof (size_t))));
    *reinterpret_cast<size_t*> (ret) = p_size;
    GC::f_allocated += p_size;
    return ret + sizeof (size_t);
}

void GCpp::OS_free (Byte* p_block)
{
    Byte* blk (p_block - sizeof (size_t));
    GC::f_allocated-= *reinterpret_cast<size_t*> (blk);
    ::free (blk);
}

---