forked from OctaForge/libostd
541 lines
17 KiB
C++
541 lines
17 KiB
C++
/** @addtogroup Concurrency
|
|
* @{
|
|
*/
|
|
|
|
/** @file context_stack.hh
|
|
*
|
|
* @brief Stack allocation for coroutines and other context-using types.
|
|
*
|
|
* Contexts, which are used by coroutines, generators and tasks in certain
|
|
* concurrency scheduler types, need stacks to work. This file provides
|
|
* several types of stack allocators to suit their needs.
|
|
*
|
|
* This API is mostly inspired by Boost.Context stack API.
|
|
*
|
|
* @copyright See COPYING.md in the project tree for further information.
|
|
*/
|
|
|
|
#ifndef OSTD_CONTEXT_STACK_HH
|
|
#define OSTD_CONTEXT_STACK_HH
|
|
|
|
#include <cstddef>
|
|
#include <new>
|
|
#include <algorithm>
|
|
|
|
#include <ostd/platform.hh>
|
|
|
|
#ifdef OSTD_USE_VALGRIND
|
|
# include <valgrind/valgrind.h>
|
|
#endif
|
|
|
|
namespace ostd {
|
|
|
|
/** @addtogroup Concurrency
|
|
* @{
|
|
*/
|
|
|
|
struct coroutine_context;
|
|
|
|
namespace detail {
|
|
/* from boost.fcontext */
|
|
using fcontext_t = void *;
|
|
|
|
struct transfer_t {
|
|
fcontext_t ctx;
|
|
void *data;
|
|
};
|
|
|
|
extern "C" OSTD_EXPORT
|
|
transfer_t OSTD_CDECL ostd_jump_fcontext(
|
|
fcontext_t const to, void *vp
|
|
);
|
|
|
|
extern "C" OSTD_EXPORT
|
|
fcontext_t OSTD_CDECL ostd_make_fcontext(
|
|
void *sp, std::size_t size, void (*fn)(transfer_t)
|
|
);
|
|
|
|
extern "C" OSTD_EXPORT
|
|
transfer_t OSTD_CDECL ostd_ontop_fcontext(
|
|
fcontext_t const to, void *vp, transfer_t (*fn)(transfer_t)
|
|
);
|
|
|
|
OSTD_EXPORT extern thread_local coroutine_context *coro_current;
|
|
} /* namespace detail */
|
|
|
|
/** @brief An allocated stack.
|
|
*
|
|
* This represents a stack allocated by a stack allocator. It doesn't
|
|
* release itself so it has to be deallocated using the same stack allocator.
|
|
*
|
|
* On architectures where the stack grows down, the stack pointer is actually
|
|
* `allocated_memory + stack_size`. This is the majority of architectures and
|
|
* all architectures this module supports.
|
|
*/
|
|
struct stack_context {
|
|
void *ptr = nullptr; ///< The stack pointer.
|
|
std::size_t size = 0; ///< The stack size.
|
|
#ifdef OSTD_USE_VALGRIND
|
|
int valgrind_id = 0;
|
|
#endif
|
|
};
|
|
|
|
/** @brief The stack traits to check properties of stacks.
|
|
*
|
|
* This structure allows stack allocators (and potentially others) to check
|
|
* various properties of stacks on your system, mainly sizing-wise.
|
|
*/
|
|
struct OSTD_EXPORT stack_traits {
|
|
/** @brief Checks if the stack is unbounded.
|
|
*
|
|
* This checks whether the stack is limited in size. If it's not, it
|
|
* means the stack you can allocate can take up as much memory as you
|
|
* want. Otherwise it means that there is some limit to it, which you
|
|
* can query with maximum_size().
|
|
*/
|
|
static bool is_unbounded() noexcept;
|
|
|
|
/** @brief Gets the page size on your system.
|
|
*
|
|
* The returned size is in bytes. Typically this is 4 KiB, but can be
|
|
* some other value too. Stack sizes are typically a multiple of page
|
|
* size.
|
|
*/
|
|
static std::size_t page_size() noexcept;
|
|
|
|
/** @brief Gets the minimum size a stack can have.
|
|
*
|
|
* You need at least this for coroutine stacks. On POSIX systems, this
|
|
* typically defaults to `SIGSTKSZ`. On Windows, we specify 8 KiB as
|
|
* the minimum size. The returned size is in bytes.
|
|
*
|
|
* @see maximum_size(), default_size()
|
|
*/
|
|
static std::size_t minimum_size() noexcept;
|
|
|
|
/** @brief Gets the maximum size a stack can have.
|
|
*
|
|
* Please remember that if is_unbounded() returns `true`, the result
|
|
* of claling this is undefined. Therefore, only use this if there is
|
|
* a stack limit in place. The returned size is in bytes.
|
|
*
|
|
* @see minimum_size(), default_size()
|
|
*/
|
|
static std::size_t maximum_size() noexcept;
|
|
|
|
/** @brief Gets the default size for stacks.
|
|
*
|
|
* Returns a reasonable size for a coroutine stack (not the main stack).
|
|
* Currently this is set to be 64 KiB, unless minimum_size() returns a
|
|
* bigger value (in which case it's the result of minimum_size()).
|
|
*
|
|
* @see minimum_size(), maximum_size()
|
|
*/
|
|
static std::size_t default_size() noexcept;
|
|
};
|
|
|
|
namespace detail {
|
|
OSTD_EXPORT void *stack_alloc(std::size_t sz);
|
|
OSTD_EXPORT void stack_free(void *p, std::size_t sz) noexcept;
|
|
OSTD_EXPORT void stack_protect(void *p, std::size_t sz) noexcept;
|
|
OSTD_EXPORT std::size_t stack_main_size() noexcept;
|
|
}
|
|
|
|
/** @brief A fixed size stack.
|
|
*
|
|
* A normal stack with a fixed size. The size of stacks alloated by this
|
|
* is always at least one page. Protected stacks add an extra guard page
|
|
* to the end, which is not usable by the stack. The size of the stack
|
|
* is always a multiple of page size. If the requested size is not a
|
|
* multiple, it's rounded up to the nearest multiple.
|
|
*
|
|
* System specific facilities are used to allocate the stacks. On POSIX
|
|
* systems, this tends to be `mmap()` with `MAP_ANON` or `MAP_ANONYMOUS`,
|
|
* unless not available (in which case the fallback is just `malloc`).
|
|
* On Windows, `VirtualAlloc()` is used.
|
|
*
|
|
* This allocator can also be used in places a stack pool is necessary,
|
|
* allocating single stacks (not from a pool). See ostd::basic_stack_pool
|
|
* for more information.
|
|
*
|
|
* @tparam Traits The stack traits to use (typically ostd::stack_traits).
|
|
* @tparam Protected Whether to protect the stack.
|
|
*/
|
|
template<typename Traits, bool Protected>
|
|
struct basic_fixedsize_stack {
|
|
/** @brief The traits type used for the stacks. */
|
|
using traits_type = Traits;
|
|
|
|
/** @brief The allocator type, here it's the allocator itself.
|
|
*
|
|
* This allows the plain allocator to be used in cases where a stack
|
|
* pool is expected to be used for allocations. See get_allocator().
|
|
*/
|
|
using allocator_type = basic_fixedsize_stack;
|
|
|
|
/** @brief Fixed size stacks are thread safe by default.
|
|
*
|
|
* You can allocate stacks from multiple threads using the same
|
|
* structure without any locking, there is no mutable shared state.
|
|
*/
|
|
static constexpr bool is_thread_safe = true;
|
|
|
|
/** @brief Constructs the stack allocator.
|
|
*
|
|
* The provided argument is the size used for the stacks. It defaults
|
|
* to the default size used for the stacks according to the traits.
|
|
*/
|
|
basic_fixedsize_stack(std::size_t ss = Traits::default_size()) noexcept:
|
|
p_size(
|
|
Traits::is_unbounded()
|
|
? std::max(ss, Traits::minimum_size())
|
|
: std::clamp(ss, Traits::minimum_size(), Traits::maximum_size())
|
|
)
|
|
{}
|
|
|
|
/** @brief Allocates a stack. */
|
|
stack_context allocate() {
|
|
std::size_t ss = p_size;
|
|
|
|
std::size_t pgs = Traits::page_size();
|
|
std::size_t asize = ss + pgs - 1 - (ss - 1) % pgs + (pgs * Protected);
|
|
|
|
void *p = detail::stack_alloc(asize);
|
|
if constexpr(Protected) {
|
|
/* a single guard page */
|
|
detail::stack_protect(p, pgs);
|
|
}
|
|
|
|
stack_context ret{static_cast<unsigned char *>(p) + asize, asize};
|
|
#ifdef OSTD_USE_VALGRIND
|
|
ret.valgrind_id = VALGRIND_STACK_REGISTER(ret.ptr, p);
|
|
#endif
|
|
return ret;
|
|
}
|
|
|
|
/** @brief Deallocates a stack. */
|
|
void deallocate(stack_context &st) noexcept {
|
|
if (!st.ptr) {
|
|
return;
|
|
}
|
|
#ifdef OSTD_USE_VALGRIND
|
|
VALGRIND_STACK_DEREGISTER(st.valgrind_id);
|
|
#endif
|
|
detail::stack_free(
|
|
static_cast<unsigned char *>(st.ptr) - st.size, st.size
|
|
);
|
|
st.ptr = nullptr;
|
|
}
|
|
|
|
/** @brief A no-op function for stack pool uses.
|
|
*
|
|
* When a stack pool is used to allocate stacks somewhere, multiple
|
|
* stacks can be reserved ahead of time. This allocates only one stack
|
|
* at a time, so this function does nothing.
|
|
*/
|
|
void reserve(std::size_t) {}
|
|
|
|
/** @brief Gets the allocator for stack pool uses.
|
|
*
|
|
* Since this is not a stack pool, this function returns a copy of
|
|
* this object. This allows the stack allocator to be used as if
|
|
* it was a pool.
|
|
*/
|
|
allocator_type get_allocator() noexcept {
|
|
return *this;
|
|
}
|
|
|
|
private:
|
|
std::size_t p_size;
|
|
};
|
|
|
|
/** @brief An unprotected fixed size stack using ostd::stack_traits. */
|
|
using fixedsize_stack = basic_fixedsize_stack<stack_traits, false>;
|
|
|
|
/** @brief A protected fixed size stack using ostd::stack_traits. */
|
|
using protected_fixedsize_stack = basic_fixedsize_stack<stack_traits, true>;
|
|
|
|
/** @brief A stack pool.
|
|
*
|
|
* A stack pool allocates multiple stacks at a time and gives them out as
|
|
* requested. When the preallocated stacks run out, a new chunk of stacks
|
|
* is allocated. You can also preallocate as many stacks as you want in
|
|
* the pool to prevent allocations from being done at later time.
|
|
*
|
|
* When a stack is "freed" using the pool or a stack allocator requested
|
|
* from the pool, the stack is not actually freed, just returned to the pool
|
|
* and reused next time something else requests a stack.
|
|
*
|
|
* The allocated stacks are fixed size and allocated exactly the same as
|
|
* ostd::basic_fixedsize_stack would.
|
|
*
|
|
* Keep in mind that stack pools are not thread safe, so external locking
|
|
* has to be done (see is_thread_safe).
|
|
*
|
|
* @tparam Traits The stack traits to use (typically ostd::stack_traits).
|
|
* @tparam Protected Whether to protect the stack.
|
|
*/
|
|
template<typename Traits, bool Protected>
|
|
struct basic_stack_pool {
|
|
private:
|
|
struct allocator {
|
|
allocator() = delete;
|
|
allocator(basic_stack_pool &p) noexcept: p_pool(&p) {}
|
|
|
|
stack_context allocate() {
|
|
return p_pool->allocate();
|
|
}
|
|
|
|
void deallocate(stack_context &st) noexcept {
|
|
p_pool->deallocate(st);
|
|
}
|
|
|
|
private:
|
|
basic_stack_pool *p_pool;
|
|
};
|
|
|
|
public:
|
|
/** @brief The default number of stacks to store in each chunk. */
|
|
static constexpr std::size_t DEFAULT_CHUNK_SIZE = 32;
|
|
|
|
/** @brief The traits type used for the stacks. */
|
|
using traits_type = Traits;
|
|
|
|
/** @brief The allocator type for the pool.
|
|
*
|
|
* Using get_allocator(), you can request an allocator from the pool
|
|
* which will be just a regular stack allocator except sourcing stacks
|
|
* from the pool. This is the allocator type used for that.
|
|
*/
|
|
using allocator_type = allocator;
|
|
|
|
/** @brief Stack pools are not thread safe.
|
|
*
|
|
* There is some shared state, so it's necessary to lock when requesting
|
|
* stacks from multiple threads. This is typically not a problem, as in
|
|
* the typical case of doing this some lock needs to be there anyway
|
|
* (typically to handle creation of the objects the stacks will be
|
|
* used in), but sometimes it might be necessary to check this.
|
|
*/
|
|
static constexpr bool is_thread_safe = false;
|
|
|
|
/** @brief Creates a stack pool.
|
|
*
|
|
* The parameters are optional. The stack size defaults to the default
|
|
* size used for stacks according to the traits. The number of stacks
|
|
* in each chunk defaults to `DEFAULT_CHUNK_SIZE`.
|
|
*
|
|
* @param ss The stack size used for the individual stacks.
|
|
* @param cs The number of stacks in each chunk.
|
|
*/
|
|
basic_stack_pool(
|
|
std::size_t ss = Traits::default_size(),
|
|
std::size_t cs = DEFAULT_CHUNK_SIZE
|
|
) {
|
|
/* precalculate the sizes */
|
|
std::size_t pgs = Traits::page_size();
|
|
std::size_t asize = ss + pgs - 1 - (ss - 1) % pgs + (pgs * Protected);
|
|
p_stacksize = asize;
|
|
p_chunksize = cs * asize;
|
|
}
|
|
|
|
/** @brief Stack pools are not copy constructible. */
|
|
basic_stack_pool(basic_stack_pool const &) = delete;
|
|
|
|
/** @brief Moves the stack pool.
|
|
*
|
|
* Moves all state from the other pool to this one. The other pool
|
|
* is emptied (no allocated chunks, no capacity) with its stack and
|
|
* chunk sizes remaining the same.
|
|
*/
|
|
basic_stack_pool(basic_stack_pool &&p) noexcept {
|
|
p_chunk = p.p_chunk;
|
|
p_unused = p.p_unused;
|
|
p_chunksize = p.p_chunksize;
|
|
p_stacksize = p.p_stacksize;
|
|
p_capacity = p.p_capacity;
|
|
p.p_chunk = nullptr;
|
|
p.p_unused = nullptr;
|
|
p.p_capacity = 0;
|
|
}
|
|
|
|
/** @brief Stack pools are not copy assignable. */
|
|
basic_stack_pool &operator=(basic_stack_pool const &) = delete;
|
|
|
|
/** @brief Move assigns another pool to this one.
|
|
*
|
|
* Basically performs swap(basic_stack_pool &). If the other pool
|
|
* is not used, the former state of this one is destroyed with it.
|
|
*/
|
|
basic_stack_pool &operator=(basic_stack_pool &&p) noexcept {
|
|
swap(p);
|
|
return *this;
|
|
}
|
|
|
|
/** @brief Destroys the stack pool and all memory managed by it. */
|
|
~basic_stack_pool() {
|
|
std::size_t ss = p_stacksize;
|
|
std::size_t cs = p_chunksize;
|
|
void *pc = p_chunk;
|
|
while (pc) {
|
|
void *p = pc;
|
|
pc = get_node(p, ss, 1)->next_chunk;
|
|
detail::stack_free(p, cs);
|
|
}
|
|
}
|
|
|
|
/** @brief Reserves a number of stacks.
|
|
*
|
|
* The given number is the actual number of stacks the pool is supposed
|
|
* to contain. If it already contains that number or more, this function
|
|
* does nothing. Otherwise it potentially reserves some extra chunks.
|
|
*/
|
|
void reserve(std::size_t n) {
|
|
std::size_t cap = p_capacity;
|
|
if (n <= cap) {
|
|
return;
|
|
}
|
|
std::size_t cnum = p_chunksize / p_stacksize;
|
|
p_unused = alloc_chunks(p_unused, (n - cap + cnum - 1) / cnum);
|
|
}
|
|
|
|
/** @brief Requests a stack directly from the pool.
|
|
*
|
|
* As stack allocators are copyable and pools are not, this might not
|
|
* be prectical in most cases. Instead, the pool will be stored somewhere
|
|
* and allocations from it will be done via get_allocator().
|
|
*/
|
|
stack_context allocate() {
|
|
stack_node *nd = request();
|
|
std::size_t ss = p_stacksize - sizeof(stack_node);
|
|
[[maybe_unused]] auto *p = reinterpret_cast<unsigned char *>(nd) - ss;
|
|
if constexpr(Protected) {
|
|
detail::stack_protect(p, Traits::page_size());
|
|
}
|
|
stack_context ret{nd, ss};
|
|
#ifdef OSTD_USE_VALGRIND
|
|
ret.valgrind_id = VALGRIND_STACK_REGISTER(ret.ptr, p);
|
|
#endif
|
|
return ret;
|
|
}
|
|
|
|
/** @brief Returns a stack back to the pool.
|
|
*
|
|
* This returns the given stack back to the pool for reuse. Stack pool
|
|
* only frees all of its memory when it's destroyed.
|
|
*/
|
|
void deallocate(stack_context &st) noexcept {
|
|
if (!st.ptr) {
|
|
return;
|
|
}
|
|
#ifdef OSTD_USE_VALGRIND
|
|
VALGRIND_STACK_DEREGISTER(st.valgrind_id);
|
|
#endif
|
|
stack_node *nd = static_cast<stack_node *>(st.ptr);
|
|
stack_node *unused = p_unused;
|
|
nd->next = unused;
|
|
p_unused = nd;
|
|
}
|
|
|
|
/** @brief Swaps two stack pools. */
|
|
void swap(basic_stack_pool &p) noexcept {
|
|
using std::swap;
|
|
swap(p_chunk, p.p_chunk);
|
|
swap(p_unused, p.p_unused);
|
|
swap(p_chunksize, p.p_chunksize);
|
|
swap(p_stacksize, p.p_stacksize);
|
|
swap(p_capacity, p.p_capacity);
|
|
}
|
|
|
|
/** @brief Gets a stack allocator that uses the pool.
|
|
*
|
|
* The returned allocator will use allocate() and
|
|
* deallocate(stack_context &) to manage the stacks.
|
|
* You will typically want to use this wherever pools are used.
|
|
*/
|
|
allocator_type get_allocator() noexcept {
|
|
return allocator{*this};
|
|
}
|
|
|
|
private:
|
|
struct stack_node {
|
|
void *next_chunk;
|
|
stack_node *next;
|
|
};
|
|
|
|
stack_node *alloc_chunks(stack_node *un, std::size_t n) {
|
|
std::size_t ss = p_stacksize;
|
|
std::size_t cs = p_chunksize;
|
|
std::size_t cnum = cs / ss;
|
|
|
|
for (std::size_t ci = 0; ci < n; ++ci) {
|
|
void *chunk = detail::stack_alloc(cs);
|
|
stack_node *prevn = un;
|
|
for (std::size_t i = cnum; i >= 2; --i) {
|
|
auto nd = get_node(chunk, ss, i);
|
|
nd->next_chunk = nullptr;
|
|
nd->next = prevn;
|
|
prevn = nd;
|
|
}
|
|
auto *fnd = get_node(chunk, ss, 1);
|
|
fnd->next_chunk = p_chunk;
|
|
/* write every time so that a potential failure results
|
|
* in all previously allocated chunks being freed in dtor
|
|
*/
|
|
p_chunk = chunk;
|
|
fnd->next = prevn;
|
|
un = fnd;
|
|
}
|
|
p_capacity += (n * cnum);
|
|
|
|
return un;
|
|
}
|
|
|
|
stack_node *request() {
|
|
stack_node *r = p_unused;
|
|
if (!r) {
|
|
r = alloc_chunks(nullptr, 1);
|
|
}
|
|
p_unused = r->next;
|
|
return r;
|
|
}
|
|
|
|
stack_node *get_node(void *chunk, std::size_t ssize, std::size_t n) {
|
|
return reinterpret_cast<stack_node *>(
|
|
static_cast<unsigned char *>(chunk) + (ssize * n) - sizeof(stack_node)
|
|
);
|
|
}
|
|
|
|
void *p_chunk = nullptr;
|
|
stack_node *p_unused = nullptr;
|
|
|
|
std::size_t p_chunksize;
|
|
std::size_t p_stacksize;
|
|
std::size_t p_capacity = 0;
|
|
};
|
|
|
|
/** @brief Swaps two stack pools. */
|
|
template<typename Traits, bool P>
|
|
inline void swap(
|
|
basic_stack_pool<Traits, P> &a, basic_stack_pool<Traits, P> &b
|
|
) noexcept {
|
|
a.swap(b);
|
|
}
|
|
|
|
/** @brief An unprotected stack pool using ostd::stack_traits. */
|
|
using stack_pool = basic_stack_pool<stack_traits, false>;
|
|
|
|
/** @brief A protected stack pool using ostd::stack_traits. */
|
|
using protected_stack_pool = basic_stack_pool<stack_traits, true>;
|
|
|
|
/** @brief The default stack allocator to use when none is provided. */
|
|
using default_stack = fixedsize_stack;
|
|
|
|
/** @} */
|
|
|
|
} /* namespace ostd */
|
|
|
|
#endif
|
|
|
|
/** @} */
|