fallible memory allocation

[SchrodingerZhu]

Client language like rust may want to provide fallible memory allocation APIs.
https://rust-lang.github.io/rfcs/2116-alloc-me-maybe.html

It is of course not a required feature. The std library states that Alloc implementation is allowed to be implemented on top of a native allocator that aborts on allocation failure. However, it can be good is consider support fallible allocation in snmalloc.

#pragma once
#include <variant>
namespace snmalloc
{
  using Unit = std::monostate;
  enum class ErrorCode : size_t
  {
    Uninitialised = 0,
    OutOfMemory = 1,
    InternalLogicError = 2,
    InvalidArgument = 3,
    OsFailure = 4
  };

  struct Error
  {
    ErrorCode err_code;
    char const* description;
  };

  template<typename T>
  class Result
  {
    using ImplType = std::variant<Error, T>;
    std::variant<Error, T> impl; // 0 => failed, 1 => success

    static constexpr size_t SUCCESS = 1;
    static constexpr size_t FAILURE = 0;
    static constexpr bool EXCEPTION_STATE =
      noexcept(std::construct_at(std::declval<T*>(), std::declval<T&&>()));

    constexpr Result(std::variant<Error, T> x) : impl(std::move(x)) {}

  public:
    Result(const Result&) = default;
    Result(Result&&) noexcept(EXCEPTION_STATE) = default;
    static constexpr Result<T> uninitialised()
    {
      return ImplType(Error{ErrorCode::Uninitialised, "uninitialised result"});
    }

    template<typename... Args>
    static constexpr Result<T> success(Args&&... args)
    {
      return ImplType(T{std::forward<Args>(args)...});
    }

    static constexpr Result<T>
    failure(ErrorCode err_code, char const* description)
    {
      return ImplType(Error{err_code, description});
    }

    T unsafe_unwrap()
    {
      auto storage = uninitialised();
      impl.swap(storage.impl);
      auto* pointer = std::get_if<T>(&storage.impl);
      SNMALLOC_ASSUME(pointer);
      return std::move(*pointer);
    }

    T unwrap()
    {
      auto storage = uninitialised();
      impl.swap(storage.impl);
      if (auto* pointer = std::get_if<T>(&storage.impl))
      {
        return std::move(*pointer);
      }
      snmalloc::error("unwrap value from a failed result");
    }

    Error unsafe_error()
    {
      auto* pointer = std::get_if<Error>(&impl);
      SNMALLOC_ASSUME(pointer);
      return *pointer;
    }

    Error error()
    {
      if (auto* pointer = std::get_if<Error>(&impl))
      {
        return *pointer;
      }
      snmalloc::error("expecting error from a successful result");
    }

    T& unsafe_ref()
    {
      auto* pointer = std::get_if<T>(&impl);
      SNMALLOC_ASSUME(pointer);
      return *pointer;
    }

    T& ref()
    {
      if (auto* pointer = std::get_if<T>(&impl))
      {
        return *pointer;
      }
      snmalloc::error("referencing value from a failed result");
    }

    T const& unsafe_ref() const
    {
      auto const* pointer = std::get_if<T>(&impl);
      SNMALLOC_ASSUME(pointer);
      return *pointer;
    }

    T const& ref() const
    {
      if (auto const* pointer = std::get_if<T>(&impl))
      {
        return *pointer;
      }
      snmalloc::error("referencing value from a failed result");
    }

    template<class F>
    auto map(F func)
    {
      using TargetType = decltype(func(unsafe_unwrap()));
      if (std::get_if<T>(&impl))
      {
        return Result<TargetType>{func(unsafe_unwrap())};
      }
      // without assume, GCC will generate ud2
      // another option is to use std::visit, but its codegen scares me.
      auto err = std::get_if<Error>(&impl);
      SNMALLOC_ASSUME(err);
      return Result<TargetType>{*err};
    }

    template<class F>
    auto flat_map(F func)
    {
      using TargetType = decltype(func(unsafe_unwrap()));
      if (std::get_if<T>(&impl))
      {
        return func(unsafe_unwrap());
      }
      // without assume, GCC will generate ud2
      // another option is to use std::visit, but its codegen scares me.
      auto err = std::get_if<Error>(&impl);
      SNMALLOC_ASSUME(err);
      return TargetType{*err};
    }

    bool is_success() const
    {
      return SUCCESS == impl.index();
    }

    bool is_failure() const
    {
      return FAILURE == impl.index();
    }
  };

} // namespace snmalloc

I am now prototyping this with the structure above. We can provide sth like the following on par:

  template<typename PAL>
  concept ConceptPAL_get_entropy64 = requires()
  {
    { PAL::get_entropy64() } -> ConceptSame<uint64_t>;
    { PAL::get_entropy64_fallible() } -> ConceptSame<Result<uint64_t>>;
  };

But it may require a big refactor across the project to finally support the feature.

[mjp41]

So I like the principle of making a more principled error message from failed allocation. My big concern is that it needs to not affect the fast path. As such I am concerned about passing around a wrapper as you propose as it will likely affect the perf.

I wonder if we want the allocator to have a field for the last error code, and then that can be inspected on a nullptr return from malloc?

Then, various points that convert failure into a nullptr on the next level could write the failure status into the field. We could then provide a

snmalloc_errno

like feature. That returns the reason for a nullptr return from malloc. This gets more difficult if we can fail to deallocate an object. As there is not something obvious to inspect.

Also with SNMALLOC_CHECK_CLIENT there are a second class of errors. Personally, I think these should be handled differently.

@nwf, @davidchisnall any thoughts?

[SchrodingerZhu]

Thanks for the reply! I meant to develop two separate paths (fallible and infallible) on par. But with the above discussion, maybe it can be easier to use sth like

snmalloc_errno

[mjp41]

My concern with two paths is the code uses a lot of tail recursive calls that get optimised into jumps. This might be tricky to maintain if there are two continuations. But I am happy to look at a sketch of any design.

[davidchisnall]

I'm nervous of setting a field in a structure because that's hard for the compiler to elide. I wonder if we could add an extra template parameter (what's one more, between friends?) to the alloc functions to take an error delegate that is called with the error code? The Rust functions would then pass a lambda that set a local variable to this and, after all of the inlining, it should just be an extra register update. The malloc ones would take the default empty function which, after inlining, should not disrupt codegen at all.