Wednesday, May 27, 2015

Deferred function call in C++

In embedded software development there is often a need for a mechanism to do some work asynchronously, often in a different thread context. For an example, the UI framework may not be thread safe so updating of the user interface must happen in the UI thread.  Another common use case is the interrupt handler, there are lots of limitations on what can safely be done in an interrupt handler routine so we usually want to schedule a piece of code to be invoked later in a user mode thread.

Traditionally these are often implemented with message id and switch block:

enum EventID
{
    kDoThis,
    kDoThat,
    ....
};
 
struct Event
{
    EventID id;
    union
    {
        int   argForThis;
        short argtForThat;
        ...
    } data;
};
 
...
 
// Sender
Event event;
event.id = kDoThis;
event.data.argForThis = 123;
enqueue(queue, event);
 
...
 
// Receiver
Event event = dequeue(queue);
switch(event.id)
{
case kDoThis:
    doThis(event.data.argForThis);
    break;
case kDoThat:
    doThat(event.data.argForThat);
    break;
...
}

Whenever we need to do something new, we must manually

* add a member to the enum EventID
* Add the argument to the data union member in the Event struct
* Add a case to the big switch block to call the function we want

This solution works. But there must be a better way. The ideal solution would be something like this:

// Sender
DeferredCall theCall(foo, arg1, arg2);
enqueue(queue, theCall);

...

// Receiver
DeferredCall theCall = dequeue(queue);
theCall.call(); // Here it calls foo(arg1, arg2)

It sounds a lot like the C++11 std::function or boost::function.  However these are not suitable for embedded projects because they all have internal heap allocations, which is 1) expensive 2) fragments the heap and 3) unsafe to use in interrupt handlers.

What we need is a fixed sized object, that has value semantic, can be created on stack and easily passing around like any value objects.  Thanks to variadic templates, the code it takes to implement such an object is suprisingly small in C++11:

#include <tuple>

// ----------------------------------------------------------------------
// Expand tuple to parameter pack
template <int ...>
struct Indexes {};
template <int N, int ... REST>
struct UnpackArguments : UnpackArguments <N-1, N-1, REST...> {};
template <int ... REST>
struct UnpackArguments<0, REST...> { using type = Indexes<REST...>; };

// ----------------------------------------------------------------------
// Base class of callable objects
struct DeferredCallBase
{
    virtual ~DeferredCallBase() {}
    virtual void copy(void*) const = 0;
    virtual void call() = 0;
};

// ----------------------------------------------------------------------
// Functions and functors
template <class FUNC, typename... ARGS>
struct DeferredFunctionCall : DeferredCallBase
{
    FUNC func;
    std::tuple<ARGS...> arguments;
    DeferredFunctionCall(FUNC f, ARGS&&... args) :
        func(f), arguments(std::forward<ARGS>(args)...)
    {}
    void copy(void* p) const
    {
        new(p)DeferredFunctionCall(*this);
    }
    void call()
    {
        call_i(typename UnpackArguments<sizeof...(ARGS)>::type());
    }
    template<int ... S>
    void call_i(Indexes<S...>)
    {
        func(std::get<S>(arguments)...);
    }
};

// ----------------------------------------------------------------------
// The container
template<unsigned kExtraSize = 0>
struct DeferredCall
{
    enum { kBufferSize = 4 * sizeof(uintptr_t) + kExtraSize };
    char buf[kBufferSize];

    // default constructor
    DeferredCall()
    {
        auto nullfunc = []{};
        new(buf)DeferredFunctionCall<decltype(nullfunc)>(nullfunc);
    }
    // constructor
    template <class F, typename... ARGS>
    DeferredCall(F f, ARGS&&... args)
    {
        using DeferredCallType = DeferredFunctionCall<F, ARGS...>;
        static_assert(sizeof(DeferredCallType) <= kBufferSize, "kBufferSize too small");
        new(buf)DeferredCallType(f, std::forward<ARGS>(args)...);
    }
    // copy constructor
    DeferredCall(const DeferredCall& other)
    {
        reinterpret_cast<const DeferredCallBase*>(other.buf)->copy(buf);
    }
    // copy assignment
    DeferredCall& operator= (const DeferredCall& other)
    {
        reinterpret_cast<const DeferredCallBase*>(other.buf)->copy(buf);
        return *this;
    }   
    // destructor
    ~DeferredCall()
    {
        reinterpret_cast<DeferredCallBase*>(buf)->~DeferredCallBase();
    }
    void call()
    {
        reinterpret_cast<DeferredCallBase*>(buf)->call();
    }
};

The idea is to use placement new operator to construct polymorph objects in a fixed buffer. Because the object has fixed size, you must specify how large you want it to be in the template argument kExtraSize.  The more bytes you give it, the more arguments you can pack in a deferred call. If the buffer size is not large enough to hold all arguments the compiler will emit an error (from the static_assert() statement).

Lets's see how well this little class works:

using DeferredCallType = DeferredCall<32>;
// Plain functions
void foo()
{
    cout << "foo" << endl;
}
void foo1(int x)
{
    cout << "foo " << x << endl;
}
void foo2(int x, int y)
{
    cout << "foo " << x << y << endl;
}
...
DeferredCallType(foo).call();
DeferredCallType(foo1, 30).call();
DeferredCallType(foo2, 30, 60).call();

// Function objects
struct Functor2
{
    void operator() (int x, string y)
    {
        cout << "functor" << x << y << endl;
    }
};
...
DeferredCallType(Functor2(), 30, string("abc")).call();

// Member functions
class MyObject
{
public:
    void foo2(int x, string y)
    {
        cout << "foo " << x << y << endl;
    }
};
...
DeferredCallType(std::mem_fn(&MyObject::foo2), &o, 30, string("xyz")).call();

They can be copied:

DeferredCallType theCall(Functor2(), 30, string("abc"));
DeferredCallType copy = theCall;
copy.call();

And they can be put in containers:

vector<DeferredCallType> v;
v.push_back(x);
v.begin()->call();

That's it, a fixed size lightweight std::function alternative for embedded projects.

4 comments:

Jeff Trull said...

This seems to have similar behavior to std::function when it comes to heap allocations, and for similar reasons... can you elaborate on the heap allocation advantages of your class?

mosra said...

Great post, I was searching for something like this for some time...

One note, though -- shouldn't the following line be also in the copy assignment operator to avoid leaks?

reinterpret_cast(buf)->~DeferredCallBase();

finalpatch said...

You are right mosra. The copy assignment operator should call the destructor too.

Nir said...

First off, stateless lambdas do not trigger heap allocations when placed in std::functions, at least under clang, and probably by now in gcc as well: http://stackoverflow.com/questions/12452022/g-stdfunction-intialized-with-closure-type-always-uses-heap-allocation.

Also, I don't see why your problem can't be better solved by using std::function with a custom allocator/memory pool: http://stackoverflow.com/questions/21094052/how-can-i-create-a-stdfunction-with-a-custom-allocator.