24 Indep nodes using address of model fields

Read and write barriers generated by Xcpp

Consider the following example:

@import "Ceda/cxObject/IObject.h"

$struct X :
    model
    {
        int x;
    }
{
};

Xcpp generates read and write barriers on access to the member variable x as follows:

struct X_model
{
    void EvictDgsNodes() const;
    ...

    int x;
};

template <typename BC>
struct X_model_mixin : public BC
{
    ...

    void EvictDgsNodes() const {BC::EvictDgsNodes();_model_.EvictDgsNodes();}

    int const& Getx() const
    {
        ceda::DataSourceReadBarrier(&_model_.x,ceda::null,"X::_model_.x");
        return _model_.x;
    }
    int& Writex()
    {
        ceda::DataSourceWriteBarrier(&_model_.x,ceda::null,"X::_model_.x");
        return _model_.x;
    }
    void Setx(int const& _v)
    {
        ceda::DataSourceWriteBarrier(&_model_.x,ceda::null,"X::_model_.x");
        _model_.x = _v;
    }
    union
    {
        struct
        {
            operator int const&() const { return CONST_ATTRIB_CAST(X_model_mixin,x)->Getx(); }
            int const& read() const { return CONST_ATTRIB_CAST(X_model_mixin,x)->Getx(); }
            int & write() { return ATTRIB_CAST(X_model_mixin,x)->Writex(); }
            void operator=(int const& _v) { ATTRIB_CAST(X_model_mixin,x)->Setx(_v); }
        } x;
    };

    X_model const& read() const
    {
        ceda::DataSourceReadBarrier(static_cast<const typename BC::FinalClass*>(this), ceda::null,"X");
        return _model_;
    }
    X_model & write()
    {
        ceda::DataSourceWriteBarrier(static_cast<typename BC::FinalClass*>(this), ceda::null,"X");
        return _model_;
    }

    X_model _model_;
};

struct X : public X_model_mixin<ceda::BaseMixin<X,ceda::EmptyBase>>
{
    typedef X_model_mixin<ceda::BaseMixin<X,ceda::EmptyBase>> BaseClass;
};

void X_model::EvictDgsNodes() const
{
    ceda::DataSourceEvict(&x);
}

IObject.h

IObject.h declares the following free functions, these are read/write barriers for an independent field that takes part in the Dependency Graph System (DGS):

void DataSourceEvict(const void* fieldAddress);
void DataSourceReadBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name);
void DataSourceWriteBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name);

obj is an IObject that contains a field located at 'fieldAddress'. obj is (only) passed in order to allow the DGS to visit the object containing the field so that it is strongly reachable and therefore protected from GC. It is permissible to call with obj = null, if visiting of the containing object is not required.

fieldAddress must not be nullptr.

The type of the field is irrelevant to the DGS - its identity is simply associated with its address in memory. Note therefore that it cannot be relocated (e.g. be an element of an xvector).

DGSystem.cpp

These functions are implemented in DGSystem.cpp as follows:

void DataSourceReadBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name)
{
    cxAssert(fieldAddress);
    if (DGSystem* dgs = TryGetThreadDGSystem())
    {
        dgs->DataSourceReadBarrier(fieldAddress,obj,name);
    }
}

void DataSourceWriteBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name)
{
    cxAssert(fieldAddress);
    if (DGSystem* dgs = TryGetThreadDGSystem())
    {
        dgs->DataSourceWriteBarrier(fieldAddress,obj,name);
    }
}

void DataSourceEvict(const void* fieldAddress)
{
    cxAssert(fieldAddress);
    if (DGSystem* dgs = TryGetThreadDGSystem())
    {
        dgs->DataSourceEvict(fieldAddress);
    }
}

void DGSystem::DataSourceEvict(const void* fieldAddress)
{
    // Independent nodes must not be accessed from OnInvalidate() handler of a dependent node
    cxAssert(m_callback == ECB_None);

    DGIndepNodeId id(fieldAddress,null,nullptr);
    if (DGIndepNodeForDataModelField* node = indepNodeMap_.TryGetNode(id))
    {
        cxVerify( node->TryEvict(false) );
    }
}

void DGSystem::DataSourceReadBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name)
{
    // Independent nodes must not be accessed from OnInvalidate() handler of a dependent node
    cxAssert(m_callback == ECB_None);

    if (m_currentNodeBeingCalculated)
    {
        DGIndepNodeId id(fieldAddress,obj,name);
        DGIndepNodeForDataModelField* node = indepNodeMap_.AlwaysGetNode(id);
        cxAssert(node);
        node->ReadBarrier();
    }
}

void DGSystem::DataSourceWriteBarrier(const void* fieldAddress, ptr<const IObject> obj, const char* name)
{
    // Independent nodes must not be accessed from OnInvalidate() handler of a dependent node
    cxAssert(m_callback == ECB_None);

    // This assertion trips if the programmer has tried to modify a model while recalculating
    // a node
    cxAssert(!m_currentNodeBeingCalculated);

    DGIndepNodeId id(fieldAddress,obj,name);
    if (DGIndepNodeForDataModelField* node = indepNodeMap_.TryGetNode(id))
    {
        node->OnChange();
    }
}

Issues with dynamic arrays, vectors, maps, sets

Consider the following model and data source

$model Point
{
    float64 x;
    float64 y;
};

$struct X isa ceda::IObject :
    model
    {
        int32 x1;
        int32 x2;
        int32 x3;
        set<int> x4;
        vector<Point> x5;
        vector<pref<Ix> > x6;
        map<int32,float64> x7;
        int32 x8[10];
    }
{
};

The model variables x1,...,x8 can potentially take part in the DG system as independent nodes.

Note that dependency on elements within x4,x5,x6,x7 is not supported. In fact typically we assume the elements of collections are immutable - even for x5, because there are significant overheads in the repository for supporting mutable elements in vectors.

It is assumed that the address of a field within a model is a reliable identifier of that field. This is generally the case because objects with active model variables are pinned in memory, and we don't support a dependency on elements of vectors, sets, bags and maps.

In theory it should be possible to support dependencies on individual elements of an array (like x8).

There is no need for additional state to support the DG in the data source. This is an advantage if there are many data source objects resident in memory and not taking part in the DG. The downside is the overhead of a map look up to access the DG independent node information for a given data source field.

Note that supporting a dependency on elements of vectors would be quite complex. For example the map would need to store paths that aren't affected by realocation of buffers in vectors. Furthermore, when elements are deleted/inserted in vectors, paths would need to be updated.

Pref members

The comments below are old and not really applicable anymore

Editable data managed with operational transform must support conservation of matter. Therefore we allow for vector<pref<>> members, but not single pref<> members. Examples are the chapters of a book, items in a folder or on a board, etc.

A client may support asynchronous download of the prefs in a vector<pref<>> member. This means that the client avoids calling operator*(), and instead calls GetResident() on a pref. This method returns nullptr if the object is not resident in memory and the client must deals appropriately in that case (e.g. by displaying a progress bar to the user in place of the referenced object).

When the dependency on the vector<pref<>> member is established (i.e. it transitions to active) the system asynchronously begins faulting in the pref'd objects (whether this means loading from disk or downloading from a repository etc).

DGIndepNodeId

An independent node is assumed to be uniquely identified by a DGIndepNodeId. This identifies the IObject and the address of the field.

A total ordering (<) is defined on DGIndepNodeId based only on the address of the field in memory, allowing it to be used for the key of a STL map.

Objects with active independent variables need to be kept alive. This is achieved by storing a pointer to the object containing the independent field in DGIndepNodeId, and allowing these to be visited.

// (fully defined in DGSystem.h)

class DGIndepNodeId
{
public:
    // Requires fieldAddress != nullptr.   object can be null (it simply means no object will be
    // visited, keeping it alive).
    DGIndepNodeId(const void* fieldAddress, ptr<const IObject> object, const char* name) :
        m_fieldAddress(fieldAddress),
        m_object(object),
        m_name(name)
    {
        cxAssert(fieldAddress);
    }

    void VisitObjects(IObjectVisitor& v) const { v << m_object; }

    bool operator==(const DGIndepNodeId& rhs) const { return m_fieldAddress == rhs.m_fieldAddress; }
    bool operator!=(const DGIndepNodeId& rhs) const { return m_fieldAddress != rhs.m_fieldAddress; }
    bool operator<(const DGIndepNodeId& rhs) const  { return m_fieldAddress < rhs.m_fieldAddress; }

    const char* Name() const { return m_name; }

private:
    const void* m_fieldAddress;
    ptr<const IObject> m_object;  // Can be null
    const char* m_name;

    friend class DGIndepNodeForDataModelField;
};

DGIndepNodeForDataModelField

DGIndepNodeForDataModelField is a subclass of DGIndepNode. It represents an independent DGS node for a field of an object.

On a 64 bit platform the estimated space taken up by each DGIndepNodeForDataModelField is 96 bytes:

    SetElementOverhead                    = 24
    sizeof(DGIndepNodeId)                 = 32
    sizeof(DGIndepNodeForDataModelField)  = 40
                                            --
                                            96

class DGIndepNodeForDataModelField : public DGIndepNode
{
public:
    virtual ssize_t ByteSize() const;
    virtual void VisitContainingObject(IObjectVisitor& v) const {}
    virtual xstring Name() const;
    virtual void OnEvict() const;
};

ssize_t DGIndepNodeForDataModelField::ByteSize() const
{
    const ssize_t SetElementOverhead = 3*sizeof(void*);   // Parent, left child and right child pointers
    const ssize_t SetElementSize = sizeof(DGIndepNodeId) + sizeof(DGIndepNodeForDataModelField);
    return SetElementOverhead + SetElementSize;
}

xstring DGIndepNodeForDataModelField::Name() const
{
    const DGIndepNodeId* id = DGActiveIndepNodeMap::GetId(this);
    if (id->m_name)
    {
        return id->m_name;
    }
    else
    {
        if (id->m_object)
        {
            octet_t const* self = (octet_t const*) id->m_object.m_self;
            ssize_t offset = (octet_t const*) id->m_fieldAddress - self;
            if (const ReflectedClass* rc = id->m_object->GetReflectedClass())
            {
                ssize_t offset2;
                const ReflectedClass& rc_model = rc->GetModel(offset2);
                offset -= offset2;

                for (int i=0 ; i < rc_model.m_numModelFields ; ++i)
                {
                    if (offset == rc_model.m_modelFields[i].m_offset)
                    {
                        return cxMakeString(rc->m_name << "::" << rc_model.m_modelFields[i].m_name);
                    }
                }
                return cxMakeString(rc->m_name << " + " << offset);
            }
            else
            {
                return cxMakeString(id->m_object << " + " << offset);
            }
        }
        else
        {
            return cxMakeString(id->m_object << " + " << id->m_fieldAddress);
        }
    }
}

void DGIndepNodeForDataModelField::OnEvict() const
{
    GetThreadDGSystem().DeleteIndepNode(this);
}

DGActiveIndepNodeMap

All the active independent nodes are registered in a singleton map, keyed by DGIndepNodeId. Rather than use a map, a set of Element is used, where Element combines the key and value of the map. The reason is to allow for an element to be deleted given a pointer to the value. It is assumed we can apply a negative offset to the address of the value!

Independent nodes are inserted into the DGActiveIndepNodeMap whenever DGActiveIndepNodeMap::AlwaysGetNode() is called - i.e. when whey are read-accessed while a dependent node is being calculated (see DGSystem::DataSourceReadBarrier())

Independent nodes are removed from the map by the eviction system

class DGActiveIndepNodeMap
{
public:
    void VisitObjects(IObjectVisitor& v) const;
    void Delete(const DGIndepNodeForDataModelField* node);
    DGIndepNodeForDataModelField* TryGetNode(const DGIndepNodeId& id);
    DGIndepNodeForDataModelField* AlwaysGetNode(const DGIndepNodeId& id);
    bool empty() const { return m_set.empty(); }

    static const DGIndepNodeId* GetId(const DGIndepNodeForDataModelField* node);

private:
    struct Element
    {
        explicit Element(const DGIndepNodeId& id) : m_id(id) {}
        bool operator<(const Element& rhs) const { return m_id < rhs.m_id; }
        bool operator==(const Element& rhs) const { return m_id == rhs.m_id; }
        DGIndepNodeId m_id;
        DGIndepNodeForDataModelField m_node;
    };

    typedef std::set<Element> SET;
    SET m_set;
};

void DGActiveIndepNodeMap::VisitObjects(IObjectVisitor& v) const
{
    for (auto& i : m_set)
    {
        i.m_id.VisitObjects(v);
    }
}

#define CONST_FIELD_TO_CLASS_CAST(className,fieldName,fieldptr)  \
    reinterpret_cast<const className*>(reinterpret_cast<const ceda::octet_t*>(fieldptr) - offsetof(className,fieldName))

/*static*/ const DGIndepNodeId* DGActiveIndepNodeMap::GetId(const DGIndepNodeForDataModelField* node)
{
    const Element* e = CONST_FIELD_TO_CLASS_CAST(Element,m_node,node);
    return &e->m_id;
}

void DGActiveIndepNodeMap::Delete(const DGIndepNodeForDataModelField* node)
{
    // Remove entry from the map, and delete the node
    const Element* e = CONST_FIELD_TO_CLASS_CAST(Element,m_node,node);
    cxVerify(m_set.erase(*e) == 1);
}

DGIndepNodeForDataModelField* DGActiveIndepNodeMap::TryGetNode(const DGIndepNodeId& id)
{
    SET::iterator i = m_set.find(Element(id));
    if (i == m_set.end())
    {
        return nullptr;
    }
    else
    {
        return const_cast<DGIndepNodeForDataModelField*>(&i->m_node);
    }
}

DGIndepNodeForDataModelField* DGActiveIndepNodeMap::AlwaysGetNode(const DGIndepNodeId& id)
{
    std::pair<SET::iterator, bool> r = m_set.insert(Element(id));
    return const_cast<DGIndepNodeForDataModelField*>(&r.first->m_node);
}