10

I am working in a memory constrained embedded environment where malloc/free new/delete are not advisable, and I'm trying to use the std::function pattern to register callbacks. I do not have access to any of the STL methods in my target code so I'm in the unfortunate situation of having to replicate some of the STL functionality myself. Function pointers are not an option for me due to the necessity for callers to have captures.

For instance, I wish to declare a class Mailbox where an onChange event can be registered

class Mailbox {
    std::function<void(int,int)> onChange;
};

That way, callers can register a lambda onChange handler that could capture this or other variables that matter for handling the event.

Since this is part of an API, I want to give the users of Mailbox maximim flexibility to either provide a function pointer, a lambda or a functor.

I have managed to find a great implementation of a std::function that appears to be exceptionally low-overhead and has exactly what I need except that it involves dynamic memory.

If you look at the following code, dynamic memory is used in exactly one place, and it appears fully scoped to the object being templated, suggesting to me that its size ought to be known at compile-time.

Can anyone help me understand how to refactor this implementation so that it is fully static and removes the use of new/malloc? I'm having trouble understanding why the size of CallableT wouldn't be calculable at compile-time.

Code below (not for the faint of heart). Note, it uses make_unique / unique_ptr but those can easily be substituted with new and * and I have tested that use case successfully.

#include <iostream>
#include <memory>
#include <cassert>
using namespace std;

template <typename T>
class naive_function;

template <typename ReturnValue, typename... Args>
class naive_function<ReturnValue(Args...)> {
public:
    template <typename T>
    naive_function& operator=(T t) {
        callable_ = std::make_unique<CallableT<T>>(t);
        return *this;
    }

    ReturnValue operator()(Args... args) const {
        assert(callable_);
        return callable_->Invoke(args...);
    }

private:
    class ICallable {
    public:
        virtual ~ICallable() = default;
        virtual ReturnValue Invoke(Args...) = 0;
    };

    template <typename T>
    class CallableT : public ICallable {
    public:
        CallableT(const T& t)
            : t_(t) {
        }

        ~CallableT() override = default;

        ReturnValue Invoke(Args... args) override {
            return t_(args...);
        }

    private:
        T t_;
    };

    std::unique_ptr<ICallable> callable_;
};

void func() {
    cout << "func" << endl;
}

struct functor {
    void operator()() {
        cout << "functor" << endl;
    }
};

int main() {
    naive_function<void()> f;
    f = func;
    f();
    f = functor();
    f();
    f = []() { cout << "lambda" << endl; };
    f();
}

Edit: added clarification on STL

Jeremy Gilbert
  • 151
  • 1
  • 6
  • 4
    You can get away with function pointers just fine. Implement C-Style callback mechanism when user supplies a regular function pointer and an opaque param (maybe with a thin wrapper around it). – user7860670 Jul 13 '17 at 18:48
  • 1
    Also take a look at https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11 – Curious Jul 13 '17 at 18:49
  • @VTT by opaque param you mean a way when registering the callback you let the caller stash away some user data (like the pointer to an object) which they then cast back inside the callback? I guess I had been hoping for something more elegant. – Jeremy Gilbert Jul 13 '17 at 18:51
  • @curious much appreciated, I should mention that I don't have access to any of the standard template library. Would love to find a observer/event model that is optimized. The best find I have right now is here: https://codereview.stackexchange.com/questions/47098/delegate-and-observer-pattern-implementation-for-an-embedded-system – Jeremy Gilbert Jul 13 '17 at 18:55
  • Yes, that is exactly one place where dynamic memory is used, namely where you store the actual callable object, because the `function` interface itself is but a typed wrapper agnostic of the actual type-erased underlying implementation. You can, say, store it in an inner member buffer rather than on the heap but this way you limit the maximum allowed size of actual callable objects (which is fine if you know that they can ONLY be of a few simple small types). You can resort to templates rather than polymorphic interface implementations, but templated callbacks are still a tricky matter. – bipll Jul 13 '17 at 19:09
  • I just proposed an implementation that does not take ownership of the callable by which it is constructed but does not avoid any and all dynamic allocation. – HeroicKatora Jul 13 '17 at 22:14

4 Answers4

5

The name for what you're looking for is "in-place function". At least one very good implementation exists today:

There is also tj::inplace_any<Size, Align>, if you need/want the semantics of any.

Quuxplusone
  • 23,928
  • 8
  • 94
  • 159
4

Let me preface this answer by saying that storing a general callable faces an interesting choice in terms of memory management. Yes, we can deduce the size of any callable at compile time but we can not store any callable into the same object without memory management. That's because our own object needs to have size independently of the callables its supposed to store but those can be arbitrarily big.

To put this reasoning into one sentence: The layout of our class (and its interface) needs to be compiled without knowledge about all of the callers.

This leaves us with essentially 3 choices

  1. We embrace memory management. We dynamically copy the callable and properly manage that memory through means of unique pointer (std or boost), or through custom calls to new and delete. This is what the original code you found does and is also done by std::function.
  2. We only allow certain callables. We create some custom storage inside our object to hold some forms of callables. This storage has a pre-determined size and we reject any callable given that can not adhere to this requirement (e.g. by a static_assert). Note that this does not necessarily restrict the set of possible callers. Instead, any user of the interface could set up a proxy-class holding merely a pointer but forwarding the call operator. We could even offer such a proxy class ourselves as part of the library. But this does nothing more than shifting the point of allocation from inside the function implementation to outside. It's still worth a try, and @radosław-cybulski comes closest to this in his answer.
  3. We don't do memory management. We could design our interface in a way that it deliberately refuses to take ownership of the callable given to it. This way, we don't need to to memory management and this part is completely up to our caller. This is what I will give code for below. It is not a drop-in replacement for std::function but the only way I see to have a generic, allocation-free, copiable type for the purpose you inteded it.

And here is the code for possibility 3, completely without allocation and fully self-contained (does not need any library import)

template<typename>
class FunctionReference;

namespace detail {
    template<typename T>
    static T&  forward(T& t)  { return t; }
    template<typename T>
    static T&& forward(T&& t) { return static_cast<T&&>(t); }

    template<typename C, typename R, typename... Args>
    constexpr auto get_call(R (C::* o)(Args...)) // We take the argument for sfinae
    -> typename FunctionReference<R(Args...)>::ptr_t {
        return [](void* t, Args... args) { return (static_cast<C*>(t)->operator())(forward<Args>(args)...); };
    }

    template<typename C, typename R, typename... Args>
    constexpr auto get_call(R (C::* o)(Args...) const) // We take the argument for sfinae
    -> typename FunctionReference<R(Args...)>::ptr_t {
        return [](void* t, Args... args) { return (static_cast<const C*>(t)->operator())(forward<Args>(args)...); };
    }

    template<typename R, typename... Args>
    constexpr auto expand_call(R (*)(Args...))
    -> typename FunctionReference<R(Args...)>::ptr_t {
        return [](void* t, Args... args) { return (static_cast<R (*)(Args...)>(t))(forward<Args>(args)...); };
    }
}

template<typename R, typename... Args>
class FunctionReference<R(Args...)> {
public:
    using signature_t = R(Args...);
    using ptr_t       = R(*)(void*, Args...);
private:
    void* self;
    ptr_t function;
public:

    template<typename C>
    FunctionReference(C* c) : // Pointer to embrace that we do not manage this object
    self(c),
    function(detail::get_call(&C::operator()))
    { }

    using rawfn_ptr_t = R (*)(Args...);
    FunctionReference(rawfn_ptr_t fnptr) : 
    self(fnptr),
    function(detail::expand_call(fnptr))
    { }

    R operator()(Args... args) {
        return function(self, detail::forward<Args>(args)...);
    }
};

For seeing how this then works in action, go to https://godbolt.org/g/6mKoca

HeroicKatora
  • 958
  • 8
  • 17
  • 1
    This is really brilliant. Does it work with lambda's or does that require additional magic? For instance, the following thing I tried didn't work: `RefType referl = {[=](int a)->int { return a+123; }}`. Also, how would the setCallback call work? – Jeremy Gilbert Jul 15 '17 at 01:55
  • 1
    The lambda expression itself will create a temporary object. This needs to be stored somewhere and `FunctionReference` itself can not do that. Instead, you'd need `auto lambda = [=](int a)->int { return a+123; }; RefType referl = {&lambda};`. And don't forget to keep the lambda object alive for at least as long as the `FunctionReference` – HeroicKatora Jul 15 '17 at 07:28
  • IIUC the main trick here is that `get_call` returns a lambda which has "no internal state" - because doesn't capture anything - so it can pretend to be a regular function (ptr_t) - it has it's unique address, which is all one needs to call it. So, the compiler will produce one such function for each possible C, and then all we need is to store the address to such magic function, and address of C instance, both of which have always the same "size"/layout. Beautiful! – qbolec Apr 06 '22 at 16:32
2

Try this:

template <class A> class naive_function;
template <typename ReturnValue, typename... Args>
class naive_function<ReturnValue(Args...)> {
public:
    naive_function() { }
    template <typename T>
    naive_function(T t) : set_(true) {
        assert(sizeof(CallableT<T>) <= sizeof(callable_));
        new (_get()) CallableT<T>(t);
    }
    template <typename T>
    naive_function(T *ptr, ReturnValue(T::*t)(Args...)) : set_(true) {
        assert(sizeof(CallableT<T>) <= sizeof(callable_));
        new (_get()) CallableT<T>(ptr, t);
    }
    naive_function(const naive_function &c) : set_(c.set_) {
        if (c.set_) c._get()->Copy(&callable_);
    }
    ~naive_function() { 
        if (set_) _get()->~ICallable();
    }

    naive_function &operator = (const naive_function &c) {
        if (this != &c) {
            if (set_) _get()->~ICallable();
            if (c.set_) {
                set_ = true;
                c._get()->Copy(&callable_);
            }
            else
                set_ = false;
        }
        return *this;
    }
    ReturnValue operator()(Args... args) const {
        return _get()->Invoke(args...);
    }
    ReturnValue operator()(Args... args) {
        return _get()->Invoke(args...);
    }

private:
    class ICallable {
    public:
        virtual ~ICallable() = default;
        virtual ReturnValue Invoke(Args...) = 0;
        virtual void Copy(void *dst) const = 0;
    };
    ICallable *_get() { 
        return ((ICallable*)&callable_); 
    }
    const ICallable *_get() const { return ((const ICallable*)&callable_); }
    template <typename T>
    class CallableT : public ICallable {
    public:
        CallableT(const T& t)
            : t_(t) {
        }

        ~CallableT() override = default;

        ReturnValue Invoke(Args... args) override {
            return t_(std::forward<ARGS>(args)...);
        }
        void Copy(void *dst) const override {
            new (dst) CallableT(*this);
        }
    private:
        T t_;
    };
    template <typename T>
    class CallableT<ReturnValue(T::*)(Args...)> : public ICallable {
    public:
        CallableT(T *ptr, ReturnValue(T::*)(Args...))
            : ptr_(ptr), t_(t) {
        }

        ~CallableT() override = default;

        ReturnValue Invoke(Args... args) override {
            return (ptr_->*t_)(std::forward<ARGS>(args)...);
        }
        void Copy(void *dst) const override {
            new (dst) CallableT(*this);
        }
    private:
        T *ptr_;
        ReturnValue(T::*t_)(Args...);
    };

    static constexpr size_t size() {
        auto f = []()->void {};
        return std::max(
            sizeof(CallableT<void(*)()>),
            std::max(
                sizeof(CallableT<decltype(f)>),
                sizeof(CallableT<void (CallableT<void(*)()>::*)()>)
            )
        );
    };
    typedef unsigned char callable_array[size()];
    typename std::aligned_union<0, callable_array, CallableT<void(*)()>, CallableT<void (CallableT<void(*)()>::*)()>>::type callable_;

    bool set_ = false;
};

Keep in mind, that sort of tricks tend to be slightly fragile.

In this case to avoid memory allocation i used unsigned char[] array of assumed max size - max of CallableT with pointer to function, pointer to member function and lambda object. Types of pointer to function and member function dont matter, as standard guarantees, that for all types those pointers will have the same size. Lambda should be pointer to object, but if for some reason isnt and it's size will change depending on lambda types, then you're out of luck. First callable_ is initialized with placement new and correct CallableT type. Then, when you try to call, i use beginning of callable_ as pointer to ICallable. This all is standard safe.

Keep in mind, that you copy naive_function object, it's template argument T's copy operator is NOT called.

UPDATE: some improvements (at least try to force alignment) + addition of copying constructor / copy assignment.

Radosław Cybulski
  • 2,952
  • 10
  • 21
  • This could be even better by replacing `unsigned char [size()]`with `std::aligned_union` (http://en.cppreference.com/w/cpp/types/aligned_union) or `std::aligned_storage`, in order to fulfill alignment requirements. – HeroicKatora Jul 13 '17 at 20:27
  • If you want to insert all types into aligned_union, then you cant, as type T, which will be assigned to naive_function is know only in constructor. But using union as itself is nice idea. aligned_storage will require c++17 i think to properly evaluate size() as it's template argument (it has to be function, otherwise i cant get sizeof(lambda object)...). – Radosław Cybulski Jul 13 '17 at 20:32
  • What about using `std::aligned_union<0, CallableT, CallableTvoid {})>, CallableT::*)()>>` that should to exactly what your size() and array does but is more expressive and has correct(er) alignment – HeroicKatora Jul 13 '17 at 21:22
  • You cant use `CallableTvoid {})>` outside of function body. – Radosław Cybulski Jul 13 '17 at 21:46
  • 1
    See https://godbolt.org/g/w2cEaq for a *compiling* version of your code and the usage of `decltype(lambda)`. It also avoid using `std::aligned_union` by inlining the reference implementation from cppreference. – HeroicKatora Jul 13 '17 at 22:23
  • Brilliant. I don't mind insisting on a "cap" to the size of the closure state. Is there any way to avoid the use of std::forward or else a simple way to implemented that? That's a deal killer for me since its not implemented in arm-none-eabi-g++ AFAIK. – Jeremy Gilbert Jul 15 '17 at 01:58
  • It depends on your usage of `naive_function` (read this http://en.cppreference.com/w/cpp/utility/forward ). In general `std::forward` forwards (duh) arguments. If all your types dont mint being copied rather than moved, then you can remove std::forward at (probaly minor) cost of additional argument copy. – Radosław Cybulski Jul 16 '17 at 07:47
0

My attempt to run the solution given Here, encountered with some issues. After fixing them, seems to work fine.

Will be happy for any review as I am not a c++ expert!

Issues and fixes:

  • error: lambda expression in an unevaluated operand.

removed the decltype. ( was not present in original code so I guess its safe(???)

using aligned_t = detail::aligned_union<0,
                                        CallableT<void(*)()>, 
                                        //CallableT<decltype([]()->void {})>,
                                        CallableT<void (CallableT<void(*)()>::*)()>
                                >;

  • Under C++11, errors in code block:

error: fields must have a constant size: 'variable length array in structure' extension will never be supported

error: 'aligned' attribute requires integer constant

error: constexpr variable 'alignment_value' must be initialized by a constant expression

(Note: this code is replacing std::aligned_union)

namespace detail { 
    template <size_t Len, class... Types>
    struct aligned_union {
        static constexpr size_t alignment_value = std::max({alignof(Types)...}); // ERROR HERE C++11
        struct type {
            alignas(alignment_value) char _s[std::max({Len, sizeof(Types)...})];  // ERROR HERE C++11
        };
    };
}

Used 'external' help from ETLCPP - which has support for embedded, file: largest.h. Error block was replaced with :

#include"etl/largest.h"
template<typename ...Types>
using largest_t = typename etl::largest_type<Types...>::type;

namespace detail {
template <size_t Len, class... Types>
struct aligned_union {
    static constexpr size_t alignment_value = etl::largest_alignment<Types...>::value; //std::max({alignof(Types)...});
    struct type {
        alignas(alignment_value) char _s[sizeof(largest_t<Types...>)]; //[std::max({Len, sizeof(Types)...})];
    };
};
}

Looked redundant, removed:

//static constexpr size_t size() {
    //    auto f = []()->void {};
    //    return std::max(
    //        sizeof(CallableT<void(*)()>),
    //        std::max(
    //            sizeof(CallableT<decltype(f)>),
    //            sizeof(CallableT<void (CallableT<void(*)()>::*)()>)
    //        )
    //    );
    //};

  • replaced std::forward with etl::forward file: utility.h

  • Had anew ,and delete errors : Undefined symbol operator delete (void)*

So added ( I never allocate.. ):

  // Define placement new if no new header is available
  inline void* operator new(size_t, void* p) { return p; }
  inline void* operator new[](size_t, void* p) { return p; }

  inline void operator delete(void*, void*) {}
  inline void operator delete[](void*, void*) {}
  inline void operator delete[](void*) {}

Still getting a warning thought (???):

: warning: replacement function 'operator delete' cannot be declared 'inline' [-Winline-new-delete]
    inline void operator delete(void* )  {}

  • Linker error: Error: L6218E: Undefined symbol __cxa_pure_virtual ).

Probably because of virtual distractor : (ref)

 virtual ~ICallable() = default;

Had to add this : ( any other solution ???)

extern "C" void __cxa_pure_virtual() { while (1); }
schanti schul
  • 681
  • 3
  • 14