How are self-destructing type erasure classes like std::function implemented?

Question

I want to understand how the implementation of std::function works. For simplicity, let's consider move-only functions with no arguments.

I understand that std::function erases the type of its target through typical type erasure techniques:

template<class Result>
struct function
{
  public:
    template<class Function>
    function(Function&& f)
      : f_(std::make_unique<callable_base>(std::forward<Function>(f)))
    {}

    // XXX how to implement constructor with allocator?
    template<class Alloc, class Function>
    function(const Alloc& alloc, Function&& f);

    Result operator()() const
    {
      return (*f_)();
    }

  private:
    struct callable_base
    {
      virtual Result operator()() const = 0;
      virtual ~callable_base(){}
    };

    template<class Function>
    struct callable
    {
      mutable Function f;

      virtual Result operator()() const
      {
        return f;
      }
    };

    // XXX what should the deleter used below do?
    struct deleter;

    std::unique_ptr<callable_base, deleter> f_;
};

I'd like to extend the functionality of this type to support custom allocation. I'll need to erase the type of the allocator, but that's difficult to do with the use of the std::unique_ptr. The custom deleter given to the unique_ptr needs to know the concrete type of the Function given to the constructor to be able to properly deallocate its storage. I could use another unique_ptr to type erase the deleter, but that solution is circular.

It seems like the callable<Function> needs to deallocate itself. What's the correct way to do that? If I deallocate inside of callable<Function>'s destructor, that seems too early because its members are still alive.

Note that allocator support for `std::function` is being removed in C++17. — Brian Bi, Mar 28 '17 at 10:48

score 2 · Answer 1 · edited May 23 '17 at 12:26

I don't think that it is possible to do this in a portable way, relying only on the supplied allocator for memory management.

I was looking for the implementation of std::shared_ptr, because it supports type erasure also for it's deleter and allocator (see overload 6): In an sketch implementation I found around here there is an auxiliary object used that stores copies of these, but this object is allocated using operator new and free'd with operator delete, thus bypassing the supplied allocator and deleter.

I was thinking about using a temporary copy (on the stack) of the allocator in order to free both the stored allocator (from which the copy is made) as well as the stored object. The problem is: How do you get a copy when you don't know the type, without using new/delete? Unfortunately, covariance is ruled out by this (requires to return a pointer).

And now, we get to the non standard solutions: If you're comfortable using either alloca or variable length arrays, then you can have a deleter that creates a sufficiently sized memory area on the stack and let the stored allocator create a copy of itself into that memory. This stack allocated (thus automatic storage duration) copy can then free both the stored allocator and the stored object, and get finally destructed by the deleter function (which, being the point of all this, doesn't know the concrete type of the allocator). A rough sketch:

struct aux_base {
  // also provide access to stored function
  virtual size_t my_size(void) const = 0;
  virtual aux_base * copy_in(void * memory) const = 0;
  virtual void free(void * ptr) = 0;
  virtual ~aux_base() {}
};

template<class Alloc, class Function>
struct aux : public aux_base {
  // Store allocator and function here

  size_t my_size(void) const {
    return sizeof(*this);
  }
  aux_base * copy_in(void * memory) const {
    // attention for alignment issues!
    return new (memory) aux(*this);
  }
  void free(void * ptr) {
    aux * stored = reinterpret_cast<aux *>(ptr);
    // do your stuff
  }
};

void deleter_for_aux(aux_base * ptr) {
  char memory[ptr->my_size()];
  aux_base * copy = ptr->copy_in(memory);
  copy->free(ptr);
  copy->~aux_base(); // call destructor
}

That said, if there is a way to do this in standard C++ without relying on another dynamic memory source than the supplied allocator I'd be very happy to know about it! :)

> How do you get a copy when you don't know the type, without using new/delete? You have a virtual function call that does it for you. — Billy ONeal, May 09 '17 at 19:13
@BillyONeal And how do you pass that copy from within that virtual function back to its caller? Without dynamic (heap) memory? — Daniel Jour, May 09 '17 at 20:25

Billy ONeal · Accepted Answer · 2017-05-09T19:37:13.193

std::function lost its allocators in C++17 in part because of problems with type erased allocators. However, the general pattern is to rebind the allocator to whatever type you're using to do the type erasure, store the original allocator in the type erased thing, and rebind the allocator again when deleting the type erased thing.

template<class Ret, class... Args>
struct Call_base {
    virtual Ret Call(Args&&...);
    virtual void DeleteThis();
protected:
    ~Call_base() {}
};

template<class Allocator, class Fx, class Ret, class... Args>
struct Call_fn : Call_base<Ret, Args...> {
    Allocator a;
    decay_t<Fx> fn;

    Call_fn(Allocator a_, Fx&& fn_)
        : a(a_), fn(forward<Fx>(fn_))
        {}

    virtual Ret Call(Args&& vals) override {
        return invoke(fn, forward<Args>(vals)...);
    }
    virtual void DeleteThis() override {
        // Rebind the allocator to an allocator to Call_fn:
        using ReboundAllocator = typename allocator_traits<Allocator>::
            template rebind_alloc<Call_fn>;
        ReboundAllocator aRebound(a);
        allocator_traits<ReboundAllocator>::destroy(aRebound, this);
        aRebound.deallocate(this, 1);
    }
};

template<class Allocator, class Fx, class Ret, class... Args>
Call_base<Ret, Args...> * Make_call_fn(Allocator a, Fx&& fn) {
    using TypeEraseType = Call_fn<Allocator, Fx, Ret, Args...>;
    using ReboundAllocator = typename allocator_traits<Allocator>::
        template rebind_alloc<TypeEraseType>;
    ReboundAllocator aRebound(a);
    auto ptr = aRebound.allocate(1); // throws
    try {
        allocator_traits<ReboundAllocator>::construct(aRebound, ptr, a, forward<Fx>(fn));
    } catch (...) {
        aRebound.deallocate(ptr, 1);
        throw;
    }

    return ptr;
}

score 0 · Answer 3 · answered Mar 12 '16 at 21:51

Here's an approximation I came up with. I don't believe it's entirely correct, but it works for my use case.

The idea is to use a "no-op" deleter with the unique_ptr. The deleter calls the object's destructor but does not deallocate its storage. The object self-deallocates within its destructor through a callback.

template<class Result>
struct function
{
  public:
    template<class Function>
    function(Function&& f)
      : f_(std::make_unique<callable_base>(std::forward<Function>(f)))
    {}

    template<class Alloc, class Function>
    function(const Alloc& alloc, Function&& f)
      : f_(allocate_unique(alloc, std::forward<Function>(f)))
    {}

    Result operator()() const
    {
      return (*f_)();
    }

  private:
    struct callable_base
    {
      // a deallocation callback to use within our destructor
      using deallocate_function_type = void(*)(callable_base*);
      deallocate_function_type deallocate_function;

      template<class Function>
      callable_base(Function callback)
        : deallocate_function(callback)
      {}

      virtual Result operator()() const = 0;

      virtual ~callable_base()
      {
        // deallocate this object's storage with the callback
        deallocate_function(this);
      }
    };

    template<class Alloc, class Function>
    struct callable : callable_base
    {
      mutable Function f;

      callable(Function&& f)
        : callable_base(deallocate),
          f(std::forward<Function>(f))
      {}

      virtual Result operator()() const
      {
        return f;
      }

      static void deallocate(callable_base* ptr)
      {
        // upcast to the right type of pointer
        callable* self = static_cast<callable*>(ptr);

        // XXX it seems like creating a new allocator here is cheating
        //     instead, we should use some member allocator, but it's
        //     not clear where to put it
        Alloc alloc;
        alloc.deallocate(self);
      }
    };

    struct self_deallocator_deleter
    {
      template<class T>
      void operator()(T* ptr) const
      {
        // call T's destructor but do not deallocate ptr
        ptr->~T();
      }
    };

    template<class Alloc, class Function>
    static std::unique_ptr<callable_base, self_deallocator_deleter>
      allocate_unique(const Alloc& alloc, Function&& f)
    {
      // allocate and construct the concrete callable object
      auto f_ptr = std::allocator_traits<Alloc>::allocate(alloc, 1);
      std::allocator_traits<Alloc>::construct(f_ptr, std::forward<Function>(f));

      // return the pointer through a unique_ptr
      return std::unique_ptr<callable_base,self_deallocator_deleter>(f_ptr);
    }

    std::unique_ptr<callable_base, self_deallocator_deleter> f_;
};

The solution would be better if the given allocator became a member of the callable object instead of a new allocator object being created on the fly inside of callable::deallocate. The problem is that we can't make the allocator a member of callable because the callable object is no longer alive at the point where callable::deallocate is called.

How are self-destructing type erasure classes like std::function implemented?

3 Answers3