ID Layer

The job of this layer is handle the message ID information.

• When new message is received, appropriate message object needs to be created, prior to invoking read operation of the next (wrapped) layer.

• When any message is about to get sent, just get the ID information from the message object and serialise it prior to invoking the write operation of the next layer.

The code of the layer is pretty straightforward:

namespace comms
{
// TField is type of the field used to read/write message ID
// TNext is the next layer this one wraps
template <typename TField, typename TNext, ... /* other parameters */>
class MsgIdLayer
{
public:
    // Type of the field object used to read/write message ID value.
    using Field = TField;

    // Take type of the ReadIterator from the next layer
    using ReadIterator = typename TNext::ReadIterator;

    // Take type of the WriteIterator from the next layer
    using WriteIterator = typename TNext::WriteIterator;

    // Take type of the message interface from the next layer
    using Message = typename TNext::Message;

    // Type of the message ID
    using MsgIdType = typename Message::MsgIdType;

    // Redefine pointer to message type (described later)
    using MsgPtr = ...; 

    ErrorStatus read(MsgPtr& msgPtr, ReadIterator& iter, std::size_t len)
    {
        Field field;
        auto es = field.read(iter, len);
        if (es != ErrorStatus::Success) {
            return es;
        }
        msgPtr = createMsg(field.value()); // create message object based on ID
        if (!msgPtr) {
            // Unknown ID
            return ErrorStatus::InvalidMsgId;
        } 
        es = m_next.read(iter, len - field.length());
        if (es != ErrorStatus::Success) {
            msgPtr.reset(); // Discard allocated message;
        } 
        return es;
    }

    ErrorStatus write(const Message& msg, WriteIterator& iter, std::size_t len) const
    {
        Field field;
        field.value() = msg.id();
        auto es = field.write(iter, len);
        if (es != ErrorStatus::Success) {
            return es;
        }
        return m_next.write(msg, iter, len - field.length());
    }
private:
    MsgPtr createMsg(MsgIdType id)
    {
        ... // TODO: create message object (described later)
    }
    TNext m_next;
};
} // namespace comms

To properly finalise the implementation above we need to resolve two main challenges:

• Implement createMsg() function which receives ID of the message and

  creates the message object.

• Define the MsgPtr smart pointer type, which is responsible to hold the

  allocated message object. In most cases defining it to be

  std::unique_ptr<Message> will do the job. However, the main problem here is usage of dynamic memory

  allocation. Bare metal platform may not have such luxury. There must be a

  way to support

  "in place" allocation as well.

Creating Message Object

Let's start with creation of proper message object, given the numeric message ID. It must be as efficient as possible.

In many cases the IDs of the messages are sequential ones and defined using some enumeration type.

enum MsgId
{
    MsgId_Message1,
    MsgId_Message2,
    ...
    MsgId_NumOfMessages
};

Let's assume that we have FactoryMethod class with polymorphic createMsg() function, that returns allocated message object wrapped in a MsgPtr smart pointer.

class FactoryMethod
{
public:
    MsgPtr createMsg() const
    {
        return createMsgImpl();
    }

protected:
    virtual MsgPtr createMsgImpl() const = 0;
};

In this case, the most efficient way is to have an array of pointers to polymorphic class FactoryMethod. The index of the array cell corresponds to a message ID.

Image: Message Factory

The code of MsgIdLayer::createMsg() function is quite simple:

namespace comms
{
template <...>
class MsgIdLayer
{
private:
    MsgPtr createMsg(MsgIdType id)
    {
        auto& registry = ...; // reference to the array of pointers to FactoryMethod-s
        if ((registry.size() <= id) ||
            (registry[id] == nullptr)){
            return MsgPtr();
        }

        return registry[id]->createMsg();
    }
};
} // namespace comms

The runtime complexity of such code is O(1).

However, there are many protocols that their ID map is quite sparse and it is impractical to use an array for direct mapping:

enum MsgId
{
    MsgId_Message1 = 0x0101,
    MsgId_Message2 = 0x0205,
    MsgId_Message3 = 0x0308,
    ...
    MsgId_NumOfMessages
};

In this case the array of FactoryMethods described earlier must be packed and binary search algorithm used to find required method. To support such search, the FactoryMethod must be able to report ID of the messages it creates.

class FactoryMethod
{
public:
    MsgIdType id() const
    {
        return idImpl();
    }

    MsgPtr createMsg() const
    {
        return createMsgImpl();
    }

protected:
    virtual MsgIdType idImpl() const = 0;
    virtual MsgPtr createMsgImpl() const = 0;
};

Then the code of MsgIdLayer::createMsg() needs to apply binary search to find the required method:

namespace comms
{
template <...>
class MsgIdLayer
{
private:
    MsgPtr createMsg(MsgIdType id)
    {
        auto& registry = ...; // reference to the array of pointers to FactoryMethod-s
        auto iter = 
            std::lower_bound(
                registry.begin(), registry.end(), id, 
                [](FactoryMethod* method, MsgIdType idVal) -> bool 
                {
                    return method->id() < idVal;
                });

        if ((iter == registry.end()) ||
            ((*iter)->id() != id)) {
            return MsgPtr();
        }
        return (*iter)->createMsg();
    }
};
} // namespace comms

Note, that std::lower_bound algorithm requires FactoryMethods in the "registry" to be sorted by the message ID. The runtime complexity of such code is O(log(n)), where n is size of the registry.

Some communication protocols define multiple variants of the same message, which are differentiated by some other means, such as serialisation length of the message. It may be convenient to implement such variants as separate message classes, which will require separate FactoryMethods to instantiate them. In this case, the MsgIdLayer::createMsg() function may use std::equal_range algorithm instead of std::lower_bound, and use additional parameter to specify which of the methods to pick from the equal range found:

namespace comms
{
template <...>
class MsgIdLayer
{
private:
    MsgPtr createMsg(MsgIdType id, unsigned idx = 0)
    {
        auto& registry = ...; // reference to the array of pointers to FactoryMethod-s
        auto iters = std::equal_range(...);

        if ((iters.first == iters.second) ||
            (iters.second < (iters.first + idx))) {
            return MsgPtr();
        }

        return (*(iter.first + idx))->createMsg();
    }
};
} // namespace comms

Please note, that MsgIdLayer::read() function also needs to be modified to support multiple attempts to create message object with the same id. It must increment the idx parameter, passed to createMsg() member function, on every failing attempt to read the message contents, and try again until the found equal range is exhausted. I leave the implementation of this extra logic as an exercise to the reader.

To complete the message allocation subject we need to come up with an automatic way to create the registry of FactoryMethods used earlier. Please remember, that FactoryMethod was just a polymorphic interface. We need to implement actual method that implements the virtual functionality.

template <typename TActualMessage>
class ActualFactoryMethod : public FactoryMethod
{
protected:
    virtual MsgIdType idImpl() const
    {
        return TActualMessage::ImplOptions::MsgId;
    }

    virtual MsgPtr createMsgImpl() const
    {
        return MsgPtr(new TActualMessage());
    }
}

Note, that the code above assumes that comms::option::StaticNumIdImpl option (described in Generalising Message Implementation chapter) was used to specify numeric message ID when defining the ActualMessage* class.

Also note, that the example above uses dynamic memory allocation to allocate actual message object. This is just for idea demonstration purposes. The Allocating Message Object section below will describe how to support "in-place" allocation.

The types of the messages, that can be received over I/O link, are usually known at compile time. If we bundle them together in std::tuple, it is easy to apply already familiar meta-programming technique of iterating over the provided types and instantiate proper ActualFactoryMethod<> object.

using AllMessages = std::tuple<
    ActualMessage1, 
    ActualMessage2,
    ActualMessage3,
    ...
>;

The size of the registry can easily be identified using std::tuple_size.

static const RegistrySize = std::tuple_size<AllMessages>::value;
using Registry = std::array<FactoryMethod*, RegistrySize>;
Registry m_registry; // registry object

Now it's time to iterate (at compile time) over all the types defined in the AllMessages tuple and create separate ActualFactoryMethod<> for each and every one of them. Remember tupleForEach? We need something similar here, but missing the tuple object itself. We are just iterating over types, not the elements of the tuple object. We'll call it tupleForEachType(). See Appendix D for implementation details.

We also require a functor class that will be invoked for every message type and will be responsible to fill the provided registry:

class MsgFactoryCreator
{
public:
    MsgFactoryCreator(Registry& registry)
      : registry_(registry)
    {
    }

    template <typename TMessage>
    void operator()()
    {
        static const ActualFactoryMethod<TMessage> Factory;
        registry_[idx_] = &Factory;
        ++idx_;
    }

private:
    Registry& registry_;
    unsigned idx_ = 0;
};

The initialisation function may be as simple as:

void initRegistry()
{
    tupleForEachType<AllMessages>(MsgFactoryCreator(m_registry));
}

NOTE, that ActualFactoryMethod<> factories do not have any internal state and are defined as static objects. It is safe just to store pointers to them in the registry array.

To summarise this section, let's redefine comms::MsgIdLayer and add the message creation functionality.

namespace comms
{
// TField is type of the field used to read/write message ID
// TAllMessages is all messages bundled in std::tuple.
// TNext is the next layer this one wraps
template <typename TField, typename TAllMessages, typename TNext>
class MsgIdLayer
{
public:
    // Type of the field object used to read/write message ID value.
    using Field = TField;

    // Take type of the ReadIterator from the next layer
    using ReadIterator = typename TNext::ReadIterator;

    // Take type of the WriteIterator from the next layer
    using WriteIterator = typename TNext::WriteIterator;

    // Take type of the message interface from the next layer
    using Message = typename TNext::Message;

    // Type of the message ID
    using MsgIdType = typename Message::MsgIdType;

    // Redefine pointer to message type:
    using MsgPtr = ...;

    // Constructor
    MsgIdLayer()
    {
        tupleForEachType<AllMessages>(MsgFactoryCreator(m_registry));
    }

    // Read operation
    ErrorStatus read(MsgPtr& msgPtr, ReadIterator& iter, std::size_t len) {...}

    // Write operation
    ErrorStatus write(const Message& msg, WriteIterator& iter, std::size_t len) const {...}

private:
    class FactoryMethod {...};

    template <typename TMessage>
    class ActualFactoryMethod : public FactoryMethod {...};

    class MsgFactoryCreator {...};

    // Registry of Factories
    static const auto RegistrySize = std::tuple_size<TAllMessages>::value;
    using Registry = std::array<FactoryMethod*, RegistrySize>;


    // Create message
    MsgPtr createMsg(MsgIdType id, unsigned idx = 0)
    {
        auto iters = std::equal_range(m_registry.begin(), m_registry.end(), ...);
        ...
    }

    Registry m_registry;
    TNext m_next;

};
} // namespace comms

Allocating Message Object

At this stage, the only missing piece of information is definition of the smart pointer type responsible to hold the allocated message object (MsgPtr) and allowing "in place" allocation instead of using dymaic memory.

When dynamic memory allocation is allowed, everything is simple, just use std::unique_ptr with standard deleter. However, it is a bit more difficult when such allocations are not allowed.

Let's start with the calculation of the buffer size which is big enough to hold any message in the provided AllMessages bundle. It is similar to the size of the union below.

union AllMessagesU
{
    ActualMessage1 msg1;
    ActualMessage2 msg2;
    ...
};

However, all the required message types are provided as std::tuple, not as union. What we need is something like std::aligned_union, but for the types already bundled in std::tuple. It turns out it is very easy to implement using template specialisation:

template <typename TTuple>
struct TupleAsAlignedUnion;

template <typename... TTypes>
struct TupleAsAlignedUnion<std::tuple<TTypes...> >
{
    using Type = typename std::aligned_union<0, TTypes...>::type;
};

NOTE, that some compilers (gcc v5.0 and below) may not implement std::aligned_union type, but they do implement std::aligned_storage. The Appendix E shows how to implement aligned union functionality using std::aligned_storage.

The "in place" allocation area, that can fit in any message type listed in AllMessages tuple, can be defined as:

using InPlaceStorage = typename TupleAsAlignedUnion<AllMessages>::Type;

The "in place" allocation is simple:

InPlaceStorage inPlaceStorage;
new (&inPlaceStorage) TMessage(); // TMessage is type of the message being created.

The "in place" allocation requires "in place" deletion, i.e. destruction of the allocated element.

template <typename T>
struct InPlaceDeleter
{
    void operator()(T* obj) {
        obj->~T();
    }
};

The smart pointer to Message interface class may be defined as std::unique_ptr<Message, InPlaceDeleter<Message> >.

Now, let's define two independent allocation policies with the similar interface. One for dynamic memory allocation, and the other for "in place" allocation.

template <typename TMessageInterface>
struct DynMemAllocationPolicy
{
    using MsgPtr = std::unique_ptr<TMessageInterface>;

    template <typename TMessage>
    MsgPtr allocMsg()
    {
        return MsgPtr(new TMessage());
    }
}

template <typename TMessageInterface, typename TAllMessages>
class InPlaceAllocationPolicy
{
public:
    template <typename T>
    struct InPlaceDeleter {...};

    using MsgPtr = std::unique_ptr<TMessageInterface, InPlaceDeleter<TMessageInterface> >;

    template <typename TMessage>
    MsgPtr allocMsg()
    {
        new (&m_storage) TMessage();
        return MsgPtr(
            reinterpret_cast<TMessageInterface*>(&m_storage),
            InPlaceDeleter<TMessageInterface>());
    }

private:
    using InPlaceStorage = typename TupleAsAlignedUnion<TAllMessages>::Type;
    InPlaceStorage m_storage;
}

Please pay attention, that the implementation of InPlaceAllocationPolicy is the simplest possible one. In production quality code, it is recommended to insert protection against double allocation in the used storage area, by introducing boolean flag indicating, that the storage area is or isn't free. The pointer/reference to such flag must also be passed to the deleter object, which is responsible to update it when deletion takes place.

The choice of the allocation policy used in comms::MsgIdLayer may be implemented using the already familiar technique of using options.

namespace comms
{
template <
    typename TField, 
    typename TAllMessages, 
    typename TNext, 
    typename... TOptions>
class MsgIdLayer
{
    ...
};
} // namespace comms

If no option is specified, the DynMemAllocationPolicy must be chosen. To force "in place" message allocation a separate option may be defined and passed as template parameter to comms::MsgIdLayer.

namespace comms
{
namespace option
{
struct InPlaceAllocation {};
} // namespace option
} // namespace comms

Using the familiar technique of options parsing, we can create a structure, where a boolean value HasInPlaceAllocation defaults to false and can be set to true, if the option mentioned above is used. As the result, the policy choice may be implemented as:

namespace comms
{
template <
    typename TField, 
    typename TAllMessages, 
    typename TNext, 
    typename... TOptions>
class MsgIdLayer
{
public:
    // TOptions parsed into struct
    using ParsedOptions = ...; 

    // Take type of the message interface from the next layer
    using Message = typename TNext::Message;

    // Choice of the allocation policy
    using AllocPolicy = typename std::conditional<
        ParsedOptions::HasInPlaceAllocation,
        InPlaceAllocationPolicy<Message, TAllMessages>,
        DynMemAllocationPolicy<Message>
    >::type;

    // Redefine pointer to message type
    using MsgPtr = typename AllocPolicy::MsgPtr;
    ...
private:
    AllocPolicy m_policy;
};
} // namespace comms

What remains to be done is to provide the ActualFactoryMethod<> class with an ability to use allocation policy for allocating the message. Please remember, that ActualFactoryMethod<> objects are stateless static ones. It means that the allocation policy object needs to passed as the parameter to its allocation function.

namespace comms
{
template <
    typename TField, 
    typename TAllMessages, 
    typename TNext, 
    typename... TOptions>
class MsgIdLayer
{
public:
    // Choice of the allocation policy
    using AllocPolicy = ...;

    // Redefine pointer to message type
    using MsgPtr = typename AllocPolicy::MsgPtr;
    ...
private:
    class FactoryMethod
    {
    public:
        MsgPtr createMsg(AllocPolicy& policy) const
        {
            return createMsgImpl(policy);
        }

    protected:
        virtual MsgPtr createMsgImpl(AllocPolicy& policy) const = 0;
    };

    template <typename TActualMessage>
    class ActualFactoryMethod : public FactoryMethod
    {
    protected:
        virtual MsgPtr createMsgImpl(AllocPolicy& policy) const
        {
            return policy.allocMsg<TActualMessage>();
        }
    }

    AllocPolicy m_policy;
};
} // namespace comms

Summary

The final implementation of the ID Layer (comms::MsgIdLayer) is a generic piece of code. It receives a list of message classes, it must recognise, as a template parameter. The whole logic of creating the right message object given the numeric ID of the message is automatically generated by the compiler using only static memory. When new message is added to the protocol, what needs to be updated is the bundle of available message classes (AllMessages). Nothing else is required. Recompilation of the sources will generate a code that supports new message as well. The implementation of comms::MsgIdLayer above has O(log(n)) runtime complexity of finding the right factory method and creating appropriate message object. It also supports multiple variants of the same message which are implemented as different message classes, but report the same message ID. By default comms::MsgIdLayer uses dynamic memory to allocate new message object. It can easily be changed by providing comms::option::InPlaceAllocation option to it, which will force usage of "in place" allocation. The "in place" allocation may create one message at a time. In order to be able to create a new message object, the previous one must be destructed and de-allocated before.