Google Git
Sign in
opensecura / 3p / cheriot-rtos / c744ab276b8398363f2d8067700e332a14d98ac2 / . / sdk / core / allocator / alloc.h
blob: 010d57f0192da7cddeaeeac43346b58c2f3fa434 [file] [log] [blame]
// Copyright Microsoft and CHERIoT Contributors.
// SPDX-License-Identifier: MIT
#pragma once
#include "alloc_config.h"
#include "compartment-macros.h"
#include "revoker.h"
#include <algorithm>
#include <cdefs.h>
#include <cheri.hh>
#include <cheriot-atomic.hh>
#include <ds/bits.h>
#include <ds/linked_list.h>
#include <ds/pointer.h>
#include <ds/ring_buffer.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <thread.h>
extern Revocation::Revoker revoker;
using cheriot::atomic;
using namespace CHERI;
/// Do we have temporal safety support in hardware?
constexpr bool HasTemporalSafety =
!std::is_same_v<Revocation::Revoker, Revocation::NoTemporalSafety>;
// the byte and bit size of a size_t
constexpr size_t BitsInSizeT = utils::bytes2bits(sizeof(size_t));
constexpr size_t NSmallBinsShift = 3U;
// number of small bins
constexpr size_t NSmallBins = 1U << NSmallBinsShift;
// number of large (tree) bins
constexpr size_t NTreeBins = 12U;
// shift needed to get the index of small bin
constexpr size_t SmallBinShift = MallocAlignShift;
// shift needed to get the index of tree bin
constexpr size_t TreeBinShift = MallocAlignShift + NSmallBinsShift;
// the max size (including header) that still falls in small bins
constexpr size_t MaxSmallSize = 1U << TreeBinShift;
// the compressed size. The actual size is SmallSize * MallocAlignment.
using SmallSize = uint16_t;
constexpr size_t MaxChunkSize = (1U << utils::bytes2bits(sizeof(SmallSize)))
<< MallocAlignShift;
// the compressed pointer. Used to point to prev and next in free lists.
using SmallPtr = size_t;
// the index to one of the bins
using BIndex = uint32_t;
// the bit map of all the bins. 1 for in-use and 0 for empty.
using Binmap = uint32_t;
static_assert(NSmallBins < utils::bytes2bits(sizeof(Binmap)));
static_assert(NTreeBins < utils::bytes2bits(sizeof(Binmap)));
// Convert small size header into the actual size in bytes.
static inline constexpr size_t head2size(SmallSize h)
{
return static_cast<size_t>(h) << MallocAlignShift;
}
// Convert byte size into small size header.
static inline constexpr SmallSize size2head(size_t s)
{
return s >> MallocAlignShift;
}
// Generate a bit mask for a single index.
static inline Binmap idx2bit(BIndex i)
{
return static_cast<Binmap>(1) << i;
}
// index of the bit mask
static inline BIndex bit2idx(Binmap x)
{
return ctz(x);
}
// Return treebin index for size s.
static inline BIndex compute_tree_index(size_t s)
{
/*
* The upper bits of the size after TreeBinShift, if larger than this, must
* be thrown into the largest bin. Every two tree bins handle one
* power-of-two.
*/
constexpr size_t MaxTreeComputeMask = (1U << (NTreeBins >> 1)) - 1;
size_t x = s >> TreeBinShift, k;
if (x == 0)
{
return 0;
}
if (x > MaxTreeComputeMask)
{
return NTreeBins - 1;
}
k = utils::bytes2bits(sizeof(x)) - 1 - clz(x);
BIndex ret = (k << 1) + ((s >> (k + (TreeBinShift - 1)) & 1));
Debug::Assert(
ret < NTreeBins, "Return value {} is out of range 0-{}", ret, NTreeBins);
return ret;
}
// shift placing maximum resolved bit in a treebin at i as sign bit
static inline size_t leftshift_for_tree_index(BIndex i)
{
return i == NTreeBins - 1 ? 0
: (BitsInSizeT - ((i >> 1) + TreeBinShift - 1U));
}
/**
* After size << leftshift_for_tree_index, the bit to be resolved must be at the
* sign bit. Checking if the bit is 1 only needs to check val < 0. This assumes
* 2's complement.
*
* @param val the value already shifted by leftshift_for_tree_index()
*/
static inline size_t leftshifted_val_msb(size_t val)
{
return static_cast<ssize_t>(val) < 0 ? 1 : 0;
}
// the size of the smallest chunk held in bin with index i
static inline size_t minsize_for_tree_index(BIndex i)
{
return (1U << ((i >> 1) + TreeBinShift)) |
((1U & i) << ((i >> 1) + TreeBinShift - 1));
}
/**
* The index of the small bin this size should live in.
* Size 1 to MallocAlignment live in bin 0, MallocAlignment + 1 to
* 2 * MallocAlignment live in bin 1, etc.
*/
static inline BIndex small_index(size_t s)
{
return (s - 1) >> SmallBinShift;
}
// Is this a smallbin size?
static inline bool is_small(size_t s)
{
return small_index(s) < NSmallBins;
}
// Convert smallbin index to the size it contains.
static inline size_t small_index2size(BIndex i)
{
return (static_cast<size_t>(i) + 1) << SmallBinShift;
}
namespace displacement_proxy
{
template<auto F, typename D>
concept Decoder = requires(D d)
{
{
F(d)
} -> std::same_as<size_t>;
};
template<auto F, typename D>
concept Encoder = requires(size_t s)
{
{
F(s)
} -> std::same_as<D>;
};
/**
* Equipped with a context for bounds, a reference to a displacement can be
* a proxy for a pointer.
*/
template<typename T, typename D, bool Positive, auto Decode, auto Encode>
requires Decoder<Decode, D> && Encoder<Encode, D>
class Proxy
{
CHERI::Capability<void> ctx;
D &d;
__always_inline void set(T *p)
{
size_t diff =
Positive ? ds::pointer::diff(ctx, p) : ds::pointer::diff(p, ctx);
d = Encode(diff);
}
public:
using Type = T;
__always_inline Proxy(void *c, D &r) : ctx(c), d(r) {}
__always_inline operator T *() const
{
size_t disp = Decode(d);
auto p = CHERI::Capability{ctx};
auto a = p.address();
if constexpr (Positive)
{
a += disp;
}
else
{
a -= disp;
}
return reinterpret_cast<T *>(a.ptr());
}
__always_inline T *operator->()
{
return *this;
}
__always_inline operator ptraddr_t()
{
return CHERI::Capability{static_cast<T *>(*this)}.address();
}
__always_inline Proxy &operator=(T *p)
{
set(p);
return *this;
}
__always_inline Proxy &operator=(Proxy const &p)
{
set(p);
return *this;
}
__always_inline bool operator==(Proxy const &p) const
{
return static_cast<T *>(*this) == static_cast<T *>(p);
}
__always_inline auto operator<=>(Proxy const &p) const
{
return static_cast<T *>(*this) <=> static_cast<T *>(p);
}
};
static_assert(ds::pointer::proxy::Proxies<
Proxy<void, SmallSize, false, head2size, size2head>,
void>);
} // namespace displacement_proxy
/**
* Every chunk, in use or not, includes a minimal header. That is, this is a
* classic malloc, not something like a slab or sizeclass allocator or a
* "BIBOP"-inspired design.
*
* This header uses relative displacements to refer to the address-order
* predecessor and successor adjacent headers. The details of encoding are
* encapsulated using the displacement_proxy::Proxy above and the
* cell_{next,prev} methods herein.
*
* Chunks are in one of four states:
*
* - Allocated / "In Use" by the application
*
* - body() is untyped memory.
* - Not indexed by any other structures in the MState
*
* - Quarantined (until revocation scrubs inward pointers from the system)
*
* - body() is a MChunk (and not a TChunk)
* - Collected in a quarantine ring using body()'s MChunk::ring linkages
*
* - Free for allocation and small
*
* - body() is a MChunk (and not a TChunk)
* - Collected in a smallbin ring using body()'s MChunk::ring
*
* - Free for allocation and large
*
* - body() is a TChunk
* - Collected in a treebin ring, using either/both the TChunk linkages
* or/and the MChunk::ring links present in body().
*/
struct __packed __aligned(MallocAlignment)
MChunkHeader
{
/**
* Each chunk has a 16-bit metadata field that is used to store a small
* bitfield and the owner ID in the remaining bits. This is the space not
* consumed by the metadata. It must be reduced if additional bits are
* stolen for other fields.
*/
static constexpr size_t OwnerIDWidth = 13;
/**
* Compressed size of the predecessor chunk. See cell_prev().
*/
SmallSize prevSize;
/**
* Compressed size of this chunk. See cell_next().
*/
SmallSize currSize;
/// The unique identifier of the allocator.
uint16_t ownerID : OwnerIDWidth;
/**
* Is this a sealed object? If so, it should be exempted from free in
* `heap_free_all` because deallocation requires consensus between the
* holder of the allocator capability and the holder of the sealing
* capability.
*/
bool isSealedObject : 1;
bool isPrevInUse : 1;
bool isCurrInUse : 1;
/// Head of a linked list of claims on this allocation
uint16_t claims;
__always_inline auto cell_prev()
{
return displacement_proxy::
Proxy<MChunkHeader, SmallSize, false, head2size, size2head>(this,
prevSize);
}
__always_inline auto cell_next()
{
return displacement_proxy::
Proxy<MChunkHeader, SmallSize, true, head2size, size2head>(this,
currSize);
}
/**
* Returns the owner for an in-use chunk. This should not be called with a
* not-in-use chunk.
*/
uint16_t owner()
{
Debug::Assert(is_in_use(),
"owner does not make sense on unallocated chunk");
return ownerID;
}
/**
* Sets the owner for an in-use chunk. This should not be called with a
* not-in-use chunk.
*/
void set_owner(uint16_t newOwner)
{
Debug::Assert(is_in_use(),
"owner does not make sense on unallocated chunk");
ownerID = newOwner;
}
/**
* Erase the header fields
*/
__always_inline void clear()
{
/*
* This is spelled slightly oddly as using memset results in a call
* rather than a single store instruction.
*/
static_assert(sizeof(*this) == sizeof(uintptr_t));
*reinterpret_cast<uintptr_t *>(this) = 0;
}
bool is_in_use()
{
return isCurrInUse;
}
bool is_prev_in_use()
{
return isPrevInUse;
}
// size of the previous chunk
size_t prevsize_get()
{
return head2size(prevSize);
}
// size of this chunk
size_t size_get()
{
return head2size(currSize);
}
void mark_in_use()
{
isCurrInUse = true;
cell_next()->isPrevInUse = true;
}
void mark_free()
{
isCurrInUse = false;
isSealedObject = false;
cell_next()->isPrevInUse = false;
}
/**
* Obtain a pointer to the body of this chunk.
*
* This relies on the CHERI bounds of `this` being (at least) to the
* entire object. In practice, they will be to the entire heap.
*/
template<typename T = void>
__always_inline CHERI::Capability<T> body()
{
return ds::pointer::offset<T>(this, sizeof(MChunkHeader));
}
static MChunkHeader *from_body(void *body)
{
return ds::pointer::offset<MChunkHeader>(body, -sizeof(MChunkHeader));
}
/**
* Land a new header somewhere within an existing chunk.
*
* The resulting header inherits its in-use status from this one, which
* leaves consistent the "previous in use" bits of both this new header and
* the successor header, but this can violate other invariants of the
* system. In particular, if this is a free chunk, then the result will be
* two free chunks in a row; the caller is expected to fix this by marking
* at least one of the two split chunks as in-use.
*
* Note that we keep the invariant that all headers correspond to shadow
* bits that are set. For this to be true, new headers are assumed to be
* created only by split() after initialisation which is in charge of
* setting the bits.
*/
MChunkHeader *split(size_t offset)
{
auto newloc = ds::pointer::offset<void>(this, offset);
auto newnext = new (newloc) MChunkHeader();
newnext->clear();
// Invariant that headers must point to shadow bits that are set.
revoker.shadow_paint_single(CHERI::Capability{newloc}.address(), true);
ds::linked_list::emplace_after(this, newnext);
newnext->isCurrInUse = newnext->isPrevInUse = isCurrInUse;
return newnext;
}
/**
* Build an initial pair of chunk headers. The returned header is at the
* indicated base and is suitable for installation into a free list (or
* tree). The other header is a sentinel of sorts, at the end of the
* indicated span of memory. To prevent the system from attempting to walk
* beyond these bounds, ficitious "in use" bits are set true: the first
* chunk claims that its predecessor is in use and the second claims that
* it itself is.
*
* This function is marked always-inlined as it is called exactly once.
*/
__always_inline static MChunkHeader *make(void *base, size_t size)
{
size -= sizeof(MChunkHeader);
auto first = new (base) MChunkHeader();
first->clear();
first->currSize = size2head(size);
first->isPrevInUse = true;
first->isCurrInUse = false;
revoker.shadow_paint_single(CHERI::Capability{first}.address(), true);
auto footer =
new (ds::pointer::offset<void>(base, size)) MChunkHeader();
footer->clear();
footer->prevSize = size;
footer->currSize = size2head(sizeof(MChunkHeader));
footer->isPrevInUse = false;
footer->isCurrInUse = true;
revoker.shadow_paint_single(CHERI::Capability{footer}.address(), true);
return first;
}
private:
/*
* Hide a no-op constructor; the only calls should be make() and split()
* above, which carry out initialization.
*/
MChunkHeader() = default;
};
static_assert(sizeof(MChunkHeader) == 8);
static_assert(std::is_standard_layout_v<MChunkHeader>);
static_assert(
offsetof(MChunkHeader, claims) == 2 * sizeof(SmallSize) + sizeof(uint16_t),
"Metadata is no longer 16 bits. Update the OwnerIDWidth constant to correct "
"the space used for the owner ID to match the remaining space.");
// the maximum requested size that is still categorised as a small bin
constexpr size_t MaxSmallRequest = MaxSmallSize - sizeof(MChunkHeader);
// Pad request bytes into a usable size.
static inline size_t pad_request(size_t req)
{
return ((req) + sizeof(MChunkHeader) + MallocAlignMask) & ~MallocAlignMask;
}
/*
* Chunk headers are also, sort of, a linked list encoding. They're not a ring
* and not exactly a typical list, in that the first and last nodes rely on "out
* of band" bits (the InUse flags) to prevent any traversals past those nodes.
* But, since we never try to insert before the first or after the last, it all
* basically works out.
*/
static_assert(ds::linked_list::cell::HasCellOperations<MChunkHeader>);
/**
* When chunks are not allocated, they are treated as nodes of either
* lists or trees.
*
* Quarantined chunks of any size are stored as MChunk-s on a ring
* threaded through one of the quarantine sentinels.
*
* Free small chunks are stored as MChunk-s on a ring threaded through
* one of the smallbin[] sentinels.
*
* Larger free chunks are indexed in a form of bitwise digital trees
* (aka tries) keyed on chunksizes. Because TChunk are only for
* free chunks greater than 64 bytes, their size doesn't impose any
* constraints on user chunk sizes.
*
* Each tree holding treenodes is a tree of unique chunk sizes. Chunks
* of the same size are arranged in a circularly-linked list (a "tree
* ring"), with only one chunk per size actually in the tree, whose
* ring link field serves as the tree ring's sentinel. (Large nodes
* are distinguished by their parent pointer, with tree roots and
* tree ring nodes having designated values.) If a chunk with the same
* size an an existing node is inserted, it is linked off the existing
* node using the MChunk::ring field.
*
* Each tree contains a power of 2 sized range of chunk sizes (the
* smallest is 0x100 <= x < 0x180), which is is divided in half at each
* tree level, with the chunks in the smaller half of the range (0x100
* <= x < 0x140 for the top nose) in the left subtree and the larger
* half (0x140 <= x < 0x180) in the right subtree. This is, of course,
* done by inspecting individual bits.
*
* Using these rules, each node's left subtree contains all smaller
* sizes than its right subtree. However, the node at the root of each
* subtree has no particular ordering relationship to either. (The
* dividing line between the subtree sizes is based on trie relation.)
* If we remove the last chunk of a given size from the interior of the
* tree, we need to replace it with a leaf node. The tree ordering
* rules permit a node to be replaced by any leaf below it.
*
* The smallest chunk in a tree (a common operation in a best-fit
* allocator) can be found by walking a path to the leftmost leaf in
* the tree. Unlike a usual binary tree, where we follow left child
* pointers until we reach a null, here we follow the right child
* pointer any time the left one is null, until we reach a leaf with
* both child pointers null. The smallest chunk in the tree will be
* somewhere along that path.
*
* The worst case number of steps to add, find, or remove a node is
* bounded by the number of bits differentiating chunks within
* bins. Under current bin calculations, this ranges from 6 up to 21
* (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
* is of course much better.
*/
using ChunkFreeLink = ds::linked_list::cell::PtrAddr;
/**
* Class of a free allocator chunk's metadata.
*
* This class can reference either a smallbin chunk or a TChunk (and is the base
* class of TChunk). Header fields should never be accessed directly since the
* format is subject to change (hence private). The public wrappers also take
* care of converting chunks and sizes into internal compressed formats.
*
* Several methods in this file are said to "initialize the linkages" of a
* MChunk. This means that these functions assume the adjacent MChunkHeader is
* set up appropriately (that is, present and linked to adjacent headers), but
* the MChunk::ring link node and any tree state (in a TChunk) is undefined on
* the way in and paved over by initialization. Use of these functions can
* relax the usual invariants of data structures; it is, for example, OK to
* feed an unsafe_remove'd MChunk to such a function or to simply build a new
* MChunk header in the heap.
*/
class __packed __aligned(MallocAlignment)
MChunk
{
friend class MChunkAssertions;
friend class TChunk;
/**
* Given a MChunkHeader, interpret its body as a MChunk. This may be
* the MChunk at the start of a TChunk, too; see TChunk::from_mchunk().
*/
__always_inline static MChunk *from_header(MChunkHeader * p)
{
return p->body<MChunk>();
}
/**
* Each MChunk participates in a circular doubly-linked list. The
* exact form of that participation varies by the state and role of the
* node:
*
* - Small chunks are on the ring whose sentinel node is a smallbin[]
*
* - Large chunks directly included in the tree (TChunk-s) use this
* link *as* the sentinel element of a ring of equally sized nodes
*
* - Large chunks not directly included in the tree again use this
* link as the link for the above ring.
*
* This is no_subobject_bounds so that from_ring() below will work even if
* subobject bounds are turned on.
*/
ChunkFreeLink ring __attribute__((__cheri_no_subobject_bounds__)) = {};
/**
* Container-of for the above field.
*/
__always_inline static MChunk *from_ring(ChunkFreeLink * c)
{
return reinterpret_cast<MChunk *>(reinterpret_cast<uintptr_t>(c) -
offsetof(MChunk, ring));
}
// the internal small pointer representation of this chunk
SmallPtr ptr()
{
return CHERI::Capability{this}.address();
}
/**
* The friend needs to access bk, fd and ptr() to rederive chunks.
* XXX: How do we grant access to only these?
*/
friend class MState;
public:
// Is the bk field pointing to p?
bool bk_equals(MChunk * p)
{
return ring.cell_prev() == &p->ring;
}
// Is the fd field pointing to p?
bool fd_equals(MChunk * p)
{
return ring.cell_next() == &p->ring;
}
/**
* Erase the MChunk-specific metadata of this chunk (specifically, ring).
*/
__always_inline void metadata_clear()
{
static_assert(sizeof(*this) == sizeof(ring));
/*
* This is spelled slightly oddly as using memset results in a call
* rather than a single store instruction.
*/
static_assert(sizeof(ring) == sizeof(uintptr_t));
*reinterpret_cast<uintptr_t *>(&this->ring) = 0;
}
};
class MChunkAssertions
{
static_assert(sizeof(MChunk) == 8);
static_assert(std::is_standard_layout_v<MChunk>);
};
// the minimum size of a chunk (including the header)
constexpr size_t MinChunkSize =
(sizeof(MChunkHeader) + sizeof(MChunk) + MallocAlignMask) & ~MallocAlignMask;
// the minimum size of a chunk (excluding the header)
constexpr size_t MinRequest = MinChunkSize - sizeof(MChunkHeader);
// true if cap address a has acceptable alignment
static inline bool is_aligned(CHERI::Capability<void> a)
{
return (a.address() & MallocAlignMask) == 0;
}
// true if the size has acceptable alignment
static inline bool is_aligned(size_t s)
{
return (s & MallocAlignMask) == 0;
}
// the number of bytes to offset an address to align it
static inline size_t align_offset(CHERI::Capability<void> a)
{
return is_aligned(a) ? 0
: MallocAlignment - (a.address() & MallocAlignMask);
}
/**
* Format of a large chunk living in large tree bins. The beginning of the
* header shares the same format with small chunk, and may be accessed with
* a MChunk pointer when not performing tree operations.
*
* Since we have enough room (large/tree chunks are at least 65 bytes), we just
* put full capabilities here, and the format probably won't change, ever.
*/
class __packed __aligned(MallocAlignment)
TChunk
{
friend class TChunkAssertions;
friend class MState;
/**
* TChunk-s also have MChunk rings up front, making it safe to interpret
* any free chunk as a MChunk.
*/
MChunk mchunk = {};
/**
* Container-of for the above field.
*/
__always_inline static TChunk *from_mchunk(MChunk * p)
{
return ds::pointer::offset<TChunk>(p, offsetof(TChunk, mchunk));
}
// pointers to left and right children in the tree
TChunk *child[2] = {nullptr, nullptr};
// pointer to parent
TChunk *parent;
// the tree index this chunk is in
BIndex index;
/*
* There's padding to alignment here, so if we needed more metadata, it
* could be "free", in spatial terms.
*
* This padding doesn't break our targeted zeroing in metadata_clear()
* because said padding will be zeroed before we view the chunk as a TChunk
* and we won't store to it.
*/
TChunk *leftmost_child()
{
if (child[0] != nullptr)
return child[0];
return child[1];
}
/**
* Fictitious root for ring-linked nodes
*/
static constexpr uintptr_t RingParent = 0;
/**
* Fictitious root for roots of tree bins.
*/
static constexpr uintptr_t RootParent = 1;
/**
* Is this the root of a tree bin?
*/
bool is_root()
{
return reinterpret_cast<uintptr_t>(parent) == RootParent;
}
/**
* Is this TChunk linked by its mchunk.ring to the tree, rather than its
* parent/child nodes? That is, is there an equal-size node already in
* the tree?
*/
bool is_tree_ring()
{
return parent == reinterpret_cast<TChunk *>(RingParent);
}
/**
* TChunk's `mchunk.ring` fields are sentinels for their rings of
* equal-sized nodes.
*/
template<typename F>
bool ring_search(F f)
{
return ds::linked_list::search(&mchunk.ring, [&](ChunkFreeLink *&p) {
return f(MChunk::from_ring(p));
});
}
/**
* Convenience composition of two container-of operations to get us from
* a TChunk's ring node back to the TChunk.
*/
__always_inline static TChunk *from_ring(ChunkFreeLink * c)
{
return TChunk::from_mchunk(MChunk::from_ring(c));
}
/**
* Construct a TChunk in `tHeader`, place it on the same free ring as
* `this`, and initialize its linkages.
*/
__always_inline void ring_emplace(BIndex ix, MChunkHeader * tHeader)
{
ds::linked_list::emplace_before(
&mchunk.ring,
&(new (tHeader->body())
TChunk(ix, reinterpret_cast<TChunk *>(RingParent)))
->mchunk.ring);
}
/**
* Wipe the TChunk metadata.
*/
__always_inline void metadata_clear()
{
/*
* This is spelled slightly oddly as using memset results in a call
* rather than a few store instructions. Even a loop with constant
* limits lowers to an actual loop.
*/
static_assert(sizeof(*this) == 5 * sizeof(uintptr_t));
uintptr_t *body = reinterpret_cast<uintptr_t *>(this);
body[0] = body[1] = body[2] = body[3] = body[4] = 0;
}
/**
* Construct a root leaf node for the given trie index.
*/
TChunk(BIndex ix)
: index(ix), parent(reinterpret_cast<TChunk *>(RootParent))
{
}
/**
* Construct a non-root leaf node for the given trie index with indicated
* parent.
*/
TChunk(BIndex ix, TChunk * p) : index(ix), parent(p) {}
public:
/**
* Remove default constructor
*/
TChunk() = delete;
};
class TChunkAssertions
{
static_assert(std::is_standard_layout_v<TChunk>);
static_assert(offsetof(TChunk, mchunk) == 0);
};
class MState
{
public:
CHERI::Capability<void> heapStart;
/**
* Array of objects whose lifetime has been extended by hazard pointers,
* but that have been freed.
*/
Capability<void *> hazardQuarantine;
using RingSentinel = ds::linked_list::Sentinel<ChunkFreeLink>;
/*
* Rings for each small bin size. Use smallbin_at() for access to
* ensure proper CHERI bounds!
*/
RingSentinel smallbins[NSmallBins];
/* Tree root nodes for each large bin */
TChunk *treebins[NTreeBins];
/*
* Chunks may be enqueued into quarantine in at most three different epochs.
* The opening of a fourth epoch necessarily implies that the eldest of the
* three being tracked is finished. Moreover, at least two of those three
* will exit quarantine at the same time, so we track up to two sets of
* chunks still in quarantine.
*
* Each pending quarantine ring has a sentinel and an epoch. The rings are
* threaded through MChunk::ring-s. We don't struct-ure these together to
* avoid some padding. We use a small ring buffer Cursors object to tell us
* which one to use. There's some redundancy in this aggregate encoding,
* but it's small.
*/
static constexpr size_t QuarantineRings = 2;
RingSentinel quarantinePendingChunks[QuarantineRings];
size_t quarantinePendingEpoch[QuarantineRings];
ds::ring_buffer::Cursors<Debug, QuarantineRings, uint8_t>
quarantinePendingRing;
RingSentinel *quarantine_pending_get(size_t ix)
{
return rederive<RingSentinel>(
CHERI::Capability{&quarantinePendingChunks[ix]}.address());
}
/*
* Chunks that have progressed through quarantine completely are moved onto
* this ring to be dequeued into the free bins above. Entire _pending rings
* can move in O(1) onto this ring, but each chunk needs individual
* attention to be pushed into bins.
*/
RingSentinel quarantineFinishedSentinel;
auto quarantine_finished_get()
{
return rederive<RingSentinel>(
CHERI::Capability{&quarantineFinishedSentinel}.address());
}
// bitmap telling which bins are empty which are not
Binmap smallmap;
Binmap treemap;
size_t heapTotalSize;
size_t heapFreeSize;
size_t heapQuarantineSize;
/**
* The number of entries currently in the `hazardQuarantine` array.
*/
size_t hazardQuarantineOccupancy = 0;
/**
* Returns true if there are no objects in the `hazardQuarantine` array.
*/
bool hazard_quarantine_is_empty()
{
return hazardQuarantineOccupancy == 0;
}
/**
* Adds the object to the end of hazard quarantine. Does not check that
* there is space, it is the responsibility of the caller to ensure that
* the quarantine is always drained before adding new objects. It is sized
* such that it is not possible (by construction) for there to be more
* objects in quarantine than there are hazard pointers.
*/
void hazard_quarantine_add(void *ptr)
{
hazardQuarantine[hazardQuarantineOccupancy++] = ptr;
}
bool is_free_cap_inbounds(CHERI::Capability<void> mem)
{
return mem.is_subset_of(heapStart);
}
/// Rederive a capability to a `T` from the heap range. This does not
/// apply bounds to the result.
template<typename T>
T *rederive(SmallPtr ptr)
{
CHERI::Capability<T> cap{heapStart.cast<T>()};
cap.address() = ptr;
return cap;
}
// Returns the smallbin head for index i.
auto smallbin_at(BIndex i)
{
return rederive<RingSentinel>(
CHERI::Capability{&smallbins[i]}.address());
}
// Returns a pointer to the pointer to the root chunk of a tree.
TChunk **treebin_at(BIndex i)
{
return &treebins[i];
}
// Mark the bit at smallbin index i.
void smallmap_mark(BIndex i)
{
smallmap |= idx2bit(i);
}
// Clear the bit at smallbin index i.
void smallmap_clear(BIndex i)
{
smallmap &= ~idx2bit(i);
}
// Is the bit at smallbin index i set?
bool is_smallmap_marked(BIndex i)
{
return smallmap & idx2bit(i);
}
// Mark the bit at treebin index i.
void treemap_mark(BIndex i)
{
treemap |= idx2bit(i);
}
// Clear the bit at treebin index i.
void treemap_clear(BIndex i)
{
treemap &= ~idx2bit(i);
}
// Is the bit at treebin index i set?
bool is_treemap_marked(BIndex i)
{
return treemap & idx2bit(i);
}
// Initialize bins for a new MState.
void init_bins()
{
// Establish circular links for smallbins.
for (BIndex i = 0; i < NSmallBins; ++i)
{
smallbin_at(i)->reset();
}
// The treebins should be all nullptrs due to memset earlier.
// Initialise quarantine
for (auto &quarantinePendingChunk : quarantinePendingChunks)
{
quarantinePendingChunk.reset();
}
quarantinePendingRing.reset();
quarantineFinishedSentinel.reset();
heapQuarantineSize = 0;
}
/**
* Begin hazard list manipulation. Returns a guard object that must be
* held until all hazard list manipulation is done.
*/
[[nodiscard]] __always_inline auto hazard_list_begin()
{
auto *lockWord{SHARED_OBJECT(uint32_t, allocator_epoch)};
uint32_t epoch = *lockWord >> 16;
Debug::Invariant(
(epoch & 1) == 0,
"Acquiring hazard lock while lock is already held. Epoch is {}",
epoch);
// Increment the epoch and mark us as waiting.
// This happens only with the allocator lock held, so we can avoid any
// CAS operations.
epoch++;
*lockWord = (epoch << 16) | thread_id_get();
epoch++;
struct Guard
{
volatile uint32_t *lockWord;
uint32_t epoch;
__always_inline ~Guard()
{
// Release the epoch.
*lockWord = (epoch << 16);
}
};
return Guard{lockWord, epoch};
}
/**
* @brief Called when adding the first memory chunk to this MState.
* At the moment we only support one contiguous MChunk for each MState.
*
* @param p The chunk used to initialise the MState. It must have the
* previous-in-use bit set and the next chunk's in-use bit set to prevent
* free() from coalescing below and above, unless you really know what you
* are doing.
*/
void mspace_firstchunk_add(void *base, size_t size)
{
// Should only be called once during mstate_init() for now.
Debug::Assert((heapTotalSize == 0) && (heapFreeSize == 0),
"First chunk added more than once. Heap size {} and "
"free size {} should both be 0",
heapTotalSize,
heapFreeSize);
auto p = MChunkHeader::make(base, size);
heapTotalSize += size;
heapFreeSize += p->size_get();
insert_chunk(p, p->size_get());
}
/**
* Tag type indicating that the requested allocation can never succeed.
*/
struct AllocationFailurePermanent
{
};
/**
* Tag type indicating that the requested allocation may be able to succeed
* once the revoker has finished, as long as nothing else uses the
* available memory until then.
*/
struct AllocationFailureRevocationNeeded
{
size_t waitingEpoch;
};
/**
* Tag type indicating that the requested allocation cannot succeed until
* some objects have been freed in the passed quota.
*/
struct AllocationFailureQuotaExceeded
{
};
/**
* Tag type indicating that the requested allocation cannot succeed until
* some objects have been freed.
*/
struct AllocationFailureHeapFull
{
};
/**
* Possible outcomes of an attempt to allocate memory.
*/
using AllocationResult = std::variant<AllocationFailurePermanent,
AllocationFailureRevocationNeeded,
AllocationFailureQuotaExceeded,
AllocationFailureHeapFull,
CHERI::Capability<void>>;
/**
* @brief Adjust size and alignment to ensure precise representability, and
* paint the shadow bit for the header to detect valid free().
*
* The `quota` is the amount of memory that the caller is still permitted
* to allocate. This is decremented by the amount allocated on successful
* allocation. The `identifier` will be stored as the owner in the header
* of a successful allocation.
*
* If `isSealed` is true then the allocation will be marked as a sealed
* object. This allows it to be skipped when freeing all objects allocated
* with a given quota.
*
* @return User pointer if request can be satisfied, or a tag type
* representing the error otherwise.
*/
AllocationResult mspace_dispatch(size_t bytes,
size_t &quota,
uint16_t identifier,
bool isSealed = false)
{
if (!hazard_quarantine_is_empty())
{
auto guard = hazard_list_begin();
hazard_pointers_recheck();
}
size_t alignSize =
(CHERI::representable_length(bytes) + MallocAlignMask) &
~MallocAlignMask;
// This 0 size check is for:
// 1. We choose to return nullptr for 0-byte requests.
// 2. crrl overflows to 0 if bytes is too big. Force failure.
if (alignSize == 0)
{
return AllocationFailurePermanent{};
}
// Check this first so that quota exhaustion doesn't return temporary
// failure.
if (heapTotalSize < alignSize)
{
return AllocationFailurePermanent{};
}
// Return failure if the quota is exhausted.
if (alignSize > quota)
{
Debug::log("Quota exhausted trying to allocate {} bytes (remaining "
"quota is {})",
alignSize,
quota);
return AllocationFailureQuotaExceeded{};
}
CHERI::Capability<void> ret{mspace_memalign(
alignSize, -CHERI::representable_alignment_mask(bytes))};
if (ret == nullptr)
{
auto neededSize = alignSize + sizeof(MChunkHeader);
if (heapQuarantineSize > 0 &&
(heapQuarantineSize + heapFreeSize) >= neededSize)
{
/* Quarantine is nonempty; there must be an eldest epoch. */
return AllocationFailureRevocationNeeded{
quarantinePendingEpoch[quarantinePendingRing
.head_get_unsafe()]};
}
if (heapTotalSize < neededSize)
{
return AllocationFailurePermanent{};
}
return AllocationFailureHeapFull{};
}
auto header = MChunkHeader::from_body(ret);
// The allocation might be just on the boundary where the requested
// size is less than the quota but the allocated size is greater. In
// this case, return the memory without quarantining and retry.
if (header->size_get() > quota)
{
Debug::log("Quota exhausted trying to allocate {} bytes (remaining "
"quota is {})",
header->size_get(),
quota);
mspace_free_internal(header);
return AllocationFailureQuotaExceeded{};
}
if constexpr (DEBUG_ALLOCATOR)
{
// Periodically sanity check the entire state for this mspace.
static size_t sanityCounter = 0;
static constexpr size_t MStateSanityInterval = 128;
if (sanityCounter % MStateSanityInterval == 0)
{
ok_malloc_state();
}
++sanityCounter;
}
size_t bodySize = header->size_get() - sizeof(MChunkHeader);
header->isSealedObject = isSealed;
header->set_owner(identifier);
quota -= header->size_get();
if (CHERI::is_precise_range(ret.address(), bodySize))
{
// Can we use this whole chunk as is? Yes!
ret.bounds() = bodySize;
}
else
{
/*
* Using the whole chunk cannot give a precise capability, so only
* use the portion that gives us a precise capability.
*/
ret.bounds() = alignSize;
Debug::Assert(bodySize == alignSize + MallocAlignment,
"bodySize {} should only be {} bytes larger than "
"alignSize {} when bodySize is not representable",
bodySize,
MallocAlignment,
alignSize);
}
return ret;
}
/**
* Returns
* the size of the allocation associated with `chunk`.
*/
size_t chunk_body_size(MChunkHeader &chunk) const
{
size_t bodySize = chunk.size_get() - sizeof(MChunkHeader);
ptraddr_t base = chunk.body().address();
if (!CHERI::is_precise_range(base, bodySize))
{
/*
* If we can't give a precise capability covering the whole chunk,
* then we must have given out the representable portion.
* See also the logic in mspace_dispatch().
*/
bodySize -= MallocAlignment;
Debug::Assert(
CHERI::is_precise_range(base, bodySize),
"Neither bodySize nor bodySize - 8 can give a precise "
"capability. "
"Something is wrong during allocation.");
}
return bodySize;
}
/**
* Check whether `allocation` is in the hazard list. Returns true if it is.
*
* This must be called in between `hazard_list_begin` and the guard going
* out of scope.
*/
bool hazard_pointer_check(Capability<void> allocation)
{
// It is now safe to walk the hazard list.
Capability<void *> hazards =
const_cast<void **>(SHARED_OBJECT_WITH_PERMISSIONS(
void *, allocator_hazard_pointers, true, true, true, false));
size_t pointers = hazards.length() / sizeof(void *);
for (size_t i = 0; i < pointers; i++)
{
Capability hazardPointer{hazards[i]};
if (hazardPointer.is_valid() &&
hazardPointer.is_subset_of(allocation))
{
Debug::log("Found hazard pointer for {} (thread: {})",
allocation,
((i / 2) + 1));
return true;
}
}
return false;
}
/**
* Recheck all of the pointers in the hazard quarantine and free any that
* are no longer on active hazard lists.
*
* This must be called in between `hazard_list_begin` and the guard that
* `hazard_list_begin` returns going out of scope.
*
* Returns true if `skip` is found in the list, false otherwise.
*/
bool hazard_pointers_recheck(Capability<void> skip = nullptr)
{
size_t insert = 0;
bool foundSkippedValue = false;
for (size_t i = 0; i < hazardQuarantineOccupancy; i++)
{
Capability ptr = hazardQuarantine[i];
if (hazard_pointer_check(ptr))
{
hazardQuarantine[insert++] = ptr;
}
else
{
if (ptr == skip)
{
foundSkippedValue = true;
continue;
}
Debug::log("Found safe-to-free object in hazard list: {}", ptr);
// Re-derive a pointer to the chunk.
Capability heap{heapStart};
heap.address() = ptr.address();
auto chunk = MChunkHeader::from_body(heap);
// We know this isn't in the hazard lists (we just checked!) so
// free it without doing any hazard pointer checks checks.
mspace_free(*chunk, ptr.length(), true);
}
}
hazardQuarantineOccupancy = insert;
return foundSkippedValue;
}
/**
* Free a chunk. The `bodySize` parameter specifies the size of the
* allocated space that must be zeroed. This must be calculated by the
* caller and so is provided here to avoid recalculating it.
*/
int mspace_free(MChunkHeader &chunk,
size_t bodySize,
bool skipHazardCheck = false)
{
// Expand the bounds of the freed object to the whole heap and set the
// address that we're looking at to the base of the requested
// capability.
Capability mem{chunk.body()};
bool isDoubleFree = false;
if (__predict_false(skipHazardCheck))
{
// Paint before zeroing, see comment on the `else` code path.
revoker.shadow_paint_range<true>(mem.address(), chunk.cell_next());
}
else
{
Capability bounded{mem};
bounded.bounds() = bodySize;
// Set the hazard epoch to odd so that no other threads can
// successfully add things to the hazard list until we're done.
// The epoch will be incremented to even at the end of this scope.
auto guard = hazard_list_begin();
// Free any objects whose lifetimes were extended by hazards,
// skipping freeing this one to avoid a double free.
// Track if we're freeing an object that has already been freed but
// is kept alive by a hazard pointer.
isDoubleFree = hazard_pointers_recheck(bounded);
// If this object is on a live hazard list, capture it and don't
// free yet.
if (hazard_pointer_check(bounded))
{
hazard_quarantine_add(bounded);
return isDoubleFree ? -EINVAL : 0;
}
if (!bounded.is_valid())
{
return -EINVAL;
}
/*
* Paint the shadow bitmap with the hazard epoch odd. This must
* happen before we increment the epoch so that any threads that saw
* that they are waiting for us to walk the epoch list will block
* until we're done.
*
* It must also happen before zeroing because the allocator is
* running with interrupts enabled. Were we to zero and then paint,
* there would be a window in which preemption could allow a store
* through a copy of the user capability (or its progeny) that undid
* our work of zeroing!
*/
revoker.shadow_paint_range<true>(mem.address(), chunk.cell_next());
}
/*
* Shadow bits have been painted. From now on user caps to this chunk
* will not come to exist in registers due to load barrier. Any that
* are already there will be addressed (either zeroed or reloaded and,
* so, tag-cleared) when we return from this compartment.
*/
auto epoch = revoker.system_epoch_get();
capaligned_zero(mem, bodySize);
/*
* We do not need to store lists for odd epochs (that is, things freed
* during a revocation sweep); just step the counter as if they had
* been freed after this pass had finished.
*/
epoch += epoch & 1;
/*
* Enqueue this chunk to quarantine. Its header is still marked as
* being allocated.
*/
quarantine_pending_push(epoch, &chunk);
heapQuarantineSize += chunk.size_get();
/*
* Perhaps there has been some progress on revocation. Dequeue 3 times.
* 3 is chosen randomly. At least 2 is needed for easy argument that the
* allocator stays ahead of its quarantine.
*/
mspace_qtbin_deqn(3);
mspace_bg_revoker_kick();
return isDoubleFree ? -EINVAL : 0;
}
/**
* Given a pointer that is probably in an allocation, try to find the start
* of that allocation. Returns the header if this is a valid pointer into
* an allocation, nullptr otherwise.
*/
MChunkHeader *allocation_start(ptraddr_t address)
{
address &= ~MallocAlignMask;
ptraddr_t base = heapStart.address();
if ((address < base) || (address > heapStart.top()))
{
return nullptr;
}
// If we don't have shadow bits, skip this check and just assume that
// this is the start of an allocation. This mode is for benchmark
// baselines only.
if constexpr (std::is_same_v<Revocation::Revoker,
Revocation::NoTemporalSafety>)
{
address -= MallocAlignment;
}
else
{
if (revoker.shadow_bit_get(address))
{
return nullptr;
}
while (!revoker.shadow_bit_get(address) && (address > base))
{
address -= MallocAlignment;
}
}
CHERI::Capability<MChunkHeader> header{heapStart.cast<MChunkHeader>()};
header.address() = address;
if (header->is_in_use())
{
return header;
}
return nullptr;
}
/**
* Try to dequeue some objects from quarantine.
*
* Returns true if any objects were dequeued, false otherwise.
*/
__always_inline bool quarantine_dequeue()
{
// 4 chosen by fair die roll.
return mspace_qtbin_deqn(4) > 0;
}
private:
/**
* @brief helper to perform operation on a range of capability words
* @param start beginning of the range
* @param size the size of the range
* @param fn what to be done for each word. Returns true to break loop
* @return true if something breaks the loop. false otherwise
*/
static bool __always_inline capaligned_range_do(void *start,
size_t size,
bool (*fn)(void **))
{
Debug::Assert((size & (sizeof(void *) - 1)) == 0,
"Cap range is not aligned");
void **capstart = static_cast<void **>(start);
for (size_t i = 0; i < size / sizeof(void *); ++i)
{
if (fn(&capstart[i]))
{
return true;
}
}
return false;
}
static void capaligned_zero(void *start, size_t size)
{
capaligned_range_do(start, size, [](void **word) {
*word = nullptr;
return false;
});
}
/**
* Internal debug checks. Crashes the allocator when inconsistency detected.
* No-ops in Release build.
*/
bool ok_address(ptraddr_t a)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return true;
}
return a >= heapStart.base();
}
bool ok_address(void *p)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return true;
}
return ok_address(CHERI::Capability{p}.address());
}
void ok_any_chunk(MChunkHeader *p)
{
if constexpr (HasTemporalSafety && DEBUG_ALLOCATOR)
{
bool thisShadowBit =
revoker.shadow_bit_get(CHERI::Capability{p}.address());
Debug::Assert(thisShadowBit,
"Chunk header does not point to a set shadow bit: {}",
p);
MChunkHeader *next = p->cell_next();
bool nextShadowBit =
revoker.shadow_bit_get(CHERI::Capability{next}.address());
Debug::Assert(
nextShadowBit,
"Next chunk header does not point to a set shadow bit: {}",
next);
Debug::Assert(
is_aligned(p->body()), "Chunk is not correctly aligned: {}", p);
Debug::Assert(
ok_address(p->body()), "Invalid address {} for chunk", p->body());
}
}
// Sanity check an in-use chunk.
void ok_in_use_chunk(MChunkHeader *p)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
ok_any_chunk(p);
Debug::Assert(p->is_in_use(), "In use chunk {} is not in use", p);
Debug::Assert(p->cell_next()->is_prev_in_use(),
"In use chunk {} is in a list with chunk that expects it "
"to not be in use",
p);
Debug::Assert(p->is_prev_in_use() || p->cell_prev()->cell_next() == p,
"Previous chunk is not in use or the chunk list is "
"corrupt for chunk {}",
p);
}
// Sanity check a free chunk.
void ok_free_chunk(MChunkHeader *pHeader)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
auto p = MChunk::from_header(pHeader);
size_t sz = pHeader->size_get();
auto nextHeader = pHeader->cell_next();
ok_any_chunk(pHeader);
if (!pHeader->is_in_use())
{
Debug::Assert(!pHeader->isSealedObject,
"Sealed objects should not be free");
}
Debug::Assert(
!pHeader->is_in_use(), "Free chunk {} is marked as in use", p);
Debug::Assert(
!nextHeader->is_prev_in_use(),
"Free chunk {} is in list with chunk that expects it to be in use",
p);
Debug::Assert(ds::linked_list::is_well_formed(&p->ring),
"Chunk {} cons cell is not well formed",
p);
if (sz >= MinChunkSize)
{
Debug::Assert((sz & MallocAlignMask) == 0,
"Chunk size {} is incorrectly aligned",
sz);
Debug::Assert(is_aligned(pHeader->body()),
"Chunk {} is insufficiently aligned",
pHeader);
Debug::Assert(
nextHeader->prevsize_get() == sz,
"Chunk {} has size {}, next node expects its size to be {}",
pHeader,
sz,
nextHeader->prevsize_get());
Debug::Assert(pHeader->is_prev_in_use(),
"Free chunk {} should follow an in-use chunk",
pHeader);
Debug::Assert(nextHeader->is_in_use(),
"Free chunk {} should be followed by an in-use chunk",
pHeader);
Debug::Assert(
ds::linked_list::is_well_formed(&p->ring),
"Forward and backwards chunk pointers are inconsistent for {}",
p);
}
else // Markers are just the MChunkHeader.
{
Debug::Assert(sz == sizeof(MChunkHeader),
"Marker chunk size is {}, should always be {}",
sz,
sizeof(MChunkHeader));
}
}
// Sanity check a chunk that was just malloced.
void ok_malloced_chunk(MChunkHeader *p, size_t s)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
if (p != nullptr)
{
size_t sz = p->size_get();
ok_in_use_chunk(p);
Debug::Assert((sz & MallocAlignMask) == 0,
"Chunk size {} is insufficiently aligned",
sz);
Debug::Assert(sz >= MinChunkSize,
"Chunk size {} is smaller than minimum size {}",
sz,
MinChunkSize);
Debug::Assert(sz >= s,
"Chunk size {} is smaller that requested size {}",
sz,
s);
/*
* Size is less than MinChunkSize more than request. If this does
* not hold, then it should have been split into two mallocs.
*/
Debug::Assert(sz < (s + MinChunkSize),
"Chunk of size {} returned for requested size {}, "
"should have been split",
sz,
s);
}
}
/**
* @brief Advance to the next tree chunk.
*/
void ok_tree_next(TChunk *from, TChunk *t)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
if (from == t->parent)
{
/* Came from parent; descend as leftwards as we can */
if (t->child[0])
{
[[clang::musttail]] return ok_tree(t, t->child[0]);
}
if (t->child[1])
{
[[clang::musttail]] return ok_tree(t, t->child[1]);
}
/* Leaf nodes fall through */
}
else if (from == t->child[0] && t->child[1])
{
/* Came from left child; descend right if there is one */
[[clang::musttail]] return ok_tree(t, t->child[1]);
}
if (!t->is_root())
{
/* Leaf node or came from rightmost child; ascend */
[[clang::musttail]] return ok_tree_next(t, t->parent);
}
/* Otherwise, we are the root node and we have nowhere to go, so stop */
}
/**
* @brief Sanity check all the chunks in a tree.
*
* @param from the previously visited node or TChunk::RootParent
* @param t the root of a whole tree or a subtree
*/
void ok_tree(TChunk *from, TChunk *t)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
auto tHeader = MChunkHeader::from_body(t);
BIndex tindex = t->index;
size_t tsize = tHeader->size_get();
BIndex idx = compute_tree_index(tsize);
Debug::Assert(
tindex == idx, "Chunk index {}, expected {}", tindex, idx);
Debug::Assert(tsize > MaxSmallSize,
"Size {} is smaller than the minimum size",
tsize);
Debug::Assert(tsize >= minsize_for_tree_index(idx),
"Size {} is smaller than the minimum size for tree {}",
tsize,
idx);
Debug::Assert((idx == NTreeBins - 1) ||
(tsize < minsize_for_tree_index((idx + 1))),
"Tree shape is invalid");
/* Properties of this tree node */
ok_any_chunk(tHeader);
ok_free_chunk(tHeader);
Debug::Assert(t->index == tindex,
"Chunk has index {}, expected {}",
t->index,
tindex);
Debug::Assert(tHeader->size_get() == tsize,
"Chunk has size {}, expected {}",
tHeader->size_get(),
tsize);
Debug::Assert(
!t->is_tree_ring(), "Tree node {} marked as tree ring node", tHeader);
Debug::Assert(t->parent != t, "Chunk {} is its own parent", tHeader);
Debug::Assert(t->is_root() || t->parent->child[0] == t ||
t->parent->child[1] == t,
"Chunk {} is neither root nor a child of its parent",
tHeader);
/* Equal-sized chunks */
t->ring_search([this, tsize](MChunk *uMchunk) {
auto u = TChunk::from_mchunk(uMchunk);
auto uHeader = MChunkHeader::from_body(uMchunk);
ok_any_chunk(uHeader);
ok_free_chunk(uHeader);
Debug::Assert(
uHeader->size_get() == tsize, "Large chunk {} has wrong size", u);
Debug::Assert(
u->is_tree_ring(), "Chunk {} is not in tree but has parent", u);
Debug::Assert(u->child[0] == nullptr,
"Chunk {} has no parent but has a child {}",
uHeader,
u->child[0]);
Debug::Assert(u->child[1] == nullptr,
"Chunk {} has no parent but has a child {}",
uHeader,
u->child[1]);
return false;
});
auto checkChild = [&](int childIndex) {
auto child = t->child[childIndex];
if (child != nullptr)
{
Debug::Assert(child->parent == t,
"Chunk {} has child {} ({}) that has parent {}",
t,
childIndex,
child,
child->parent);
Debug::Assert(child != t,
"Chunk {} is its its own child ({})",
t,
childIndex);
Debug::Assert(MChunkHeader::from_body(child)->size_get() !=
tsize,
"Chunk {} has child {} with equal size {}",
t,
child,
tsize);
}
};
checkChild(0);
checkChild(1);
if ((t->child[0] != nullptr) && (t->child[1] != nullptr))
{
auto childHeaderSize = [&](int ix) {
return MChunkHeader::from_body(t->child[ix])->size_get();
};
Debug::Assert(childHeaderSize(0) < childHeaderSize(1),
"Chunk {}'s children are not sorted by size",
tHeader);
}
[[clang::musttail]] return ok_tree_next(from, t);
}
// Sanity check the tree at treebin[i].
void ok_treebin(BIndex i)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
TChunk **tb = treebin_at(i);
TChunk *t = *tb;
bool empty = (treemap & (1U << i)) == 0;
if (t == nullptr)
{
Debug::Assert(empty, "Null tree is not empty");
}
if (!empty)
{
Debug::Assert(
t->is_root(), "Non-empty bin has non-root tree node {}", t);
ok_tree(t->parent, t);
}
}
// Sanity check smallbin[i].
void ok_smallbin(BIndex i)
{
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
auto b = smallbin_at(i);
bool empty = (smallmap & (1U << i)) == 0;
Debug::Assert(empty == b->is_empty(),
"Small bin {} empty flag and list disagree",
i);
b->search([this, i](auto pRing) {
auto pHeader = MChunkHeader::from_body(MChunk::from_ring(pRing));
// Each chunk claims to be free.
ok_free_chunk(pHeader);
// Chunk belongs in this bin.
size_t size = pHeader->size_get();
Debug::Assert(small_index(size) == i,
"Chunk is in bin with index {} but should be in {}",
i,
small_index(size));
return false;
});
}
// Sanity check the entire malloc state in this MState.
void ok_malloc_state()
{
if constexpr (Revocation::Revoker::IsAsynchronous)
{
mspace_bg_revoker_kick();
}
if constexpr (!DEBUG_ALLOCATOR)
{
return;
}
BIndex i;
size_t total;
// Check all the bins.
for (i = 0; i < NSmallBins; ++i)
{
ok_smallbin(i);
}
for (i = 0; i < NTreeBins; ++i)
{
ok_treebin(i);
}
}
private:
/*
* Link a free chunk into a smallbin.
*
* Initializes the linkages of p.
*/
void insert_small_chunk(MChunkHeader *p, size_t size)
{
BIndex i = small_index(size);
auto bin = smallbin_at(i);
Debug::Assert(
size >= MinChunkSize, "Size {} is not a small chunk size", size);
if (!is_smallmap_marked(i))
{
smallmap_mark(i);
}
else if (!RTCHECK(ok_address(bin)))
{
corruption_error_action();
}
/*
* The constructor and emplacement are expected to inline and not
* generate redundant stores.
*/
bin->append_emplace(&(new (p->body()) MChunk())->ring);
}
/// Unlink a chunk from a smallbin.
void unlink_small_chunk(MChunk *p, size_t s)
{
auto fr = p->ring.cell_next();
auto *f = MChunk::from_ring(fr);
auto br = p->ring.cell_prev();
auto *b = MChunk::from_ring(br);
auto pHeader = MChunkHeader::from_body(p);
BIndex i = small_index(s);
auto bin = smallbin_at(i);
Debug::Assert(!ds::linked_list::is_singleton(&p->ring),
"Chunk {} is circularly referenced",
p);
Debug::Assert(pHeader->size_get() == small_index2size(i),
"Chunk {} is has size {} but is in bin for size {}",
pHeader,
pHeader->size_get(),
small_index2size(i));
if (RTCHECK(&p->ring == bin->last() ||
(ok_address(f->ptr()) && f->bk_equals(p))))
{
if (br == fr)
{
// This is the last chunk in this bin.
smallmap_clear(i);
bin->reset();
}
else if (RTCHECK(&p->ring == smallbin_at(i)->first() ||
(ok_address(b->ptr()) && b->fd_equals(p))))
{
ds::linked_list::unsafe_remove(&p->ring);
}
else
{
corruption_error_action();
}
}
else
{
corruption_error_action();
}
p->metadata_clear();
}
// Unlink the first chunk from a smallbin.
MChunkHeader *unlink_first_small_chunk(BIndex i)
{
auto b = smallbin_at(i);
Debug::Assert(ds::linked_list::is_well_formed(&b->sentinel),
"Smallbin {} sentinel (at {}) is not well formed",
i,
b);
MChunk *p = MChunk::from_ring(b->unsafe_take_first());
Debug::Assert(
ok_address(p->ptr()), "Removed chunk {} has bad address", p);
if (b->is_empty())
{
smallmap_clear(i);
}
p->metadata_clear();
MChunkHeader *pHeader = MChunkHeader::from_body(p);
Debug::Assert(pHeader->size_get() == small_index2size(i),
"Chunk {} is has size {} but is in bin for size {}",
pHeader,
pHeader->size_get(),
small_index2size(i));
return pHeader;
}
/**
* Insert chunk into tree.
*
* Initializes the linkages of x.
*/
void insert_large_chunk(MChunkHeader *xHeader, size_t s)
{
TChunk **head;
BIndex i = compute_tree_index(s);
head = treebin_at(i);
if (!is_treemap_marked(i))
{
treemap_mark(i);
*head = new (xHeader->body()) TChunk(i);
}
else
{
TChunk *t = *head;
size_t k = s << leftshift_for_tree_index(i);
for (;;)
{
if (MChunkHeader::from_body(t)->size_get() != s)
{
CHERI::Capability<TChunk *> c =
&(t->child[leftshifted_val_msb(k)]);
k <<= 1;
if (*c != nullptr)
{
t = *c;
}
else if (RTCHECK(ok_address(c.address())))
{
*c = new (xHeader->body()) TChunk(i, t);
break;
}
else
{
corruption_error_action();
break;
}
}
else
{
TChunk *back =
TChunk::from_ring(t->mchunk.ring.cell_prev());
if (RTCHECK(ok_address(t->mchunk.ptr()) &&
ok_address(back->mchunk.ptr())))
{
t->ring_emplace(i, xHeader);
break;
}
corruption_error_action();
break;
}
}
}
}
/**
* Unlink steps:
*
* 1. If x is a chained node, unlink it from its same-sized fd/bk links
* and choose its bk node as its replacement.
* 2. If x was the last node of its size, but not a leaf node, it must
* be replaced with a leaf node (not merely one with an open left or
* right), to make sure that lefts and rights of descendents
* correspond properly to bit masks. We use the rightmost descendent
* of x. We could use any other leaf, but this is easy to locate and
* tends to counteract removal of leftmosts elsewhere, and so keeps
* paths shorter than minimally guaranteed. This doesn't loop much
* because on average a node in a tree is near the bottom.
* 3. If x is the base of a chain (i.e., has parent links) relink
* x's parent and children to x's replacement (or null if none).
*
* Always zeros the chunk linkages.
*/
void unlink_large_chunk(TChunk *x)
{
TChunk *xp = x->parent;
TChunk *r;
if (!ds::linked_list::is_singleton(&x->mchunk.ring))
{
TChunk *f = TChunk::from_ring(x->mchunk.ring.cell_next());
r = TChunk::from_ring(x->mchunk.ring.cell_prev());
if (RTCHECK(ok_address(f->mchunk.ptr()) &&
f->mchunk.bk_equals(&x->mchunk) &&
r->mchunk.fd_equals(&x->mchunk)))
{
ds::linked_list::unsafe_remove(&x->mchunk.ring);
}
else
{
corruption_error_action();
}
}
else
{
CHERI::Capability<TChunk *> rp;
if (((r = *(rp = &(x->child[1]))) != nullptr) ||
((r = *(rp = &(x->child[0]))) != nullptr))
{
TChunk **cp;
while ((*(cp = &(r->child[1])) != nullptr) ||
(*(cp = &(r->child[0])) != nullptr))
{
r = *(rp = cp);
}
if (RTCHECK(ok_address(rp.address())))
{
*rp = nullptr;
}
else
{
corruption_error_action();
}
}
}
if (!x->is_tree_ring())
{
TChunk **h = treebin_at(x->index);
if (x == *h)
{
if ((*h = r) == nullptr)
{
treemap_clear(x->index);
}
}
else if (RTCHECK(ok_address(xp->mchunk.ptr())))
{
if (xp->child[0] == x)
{
xp->child[0] = r;
}
else
{
xp->child[1] = r;
}
}
else
{
corruption_error_action();
}
if (r != nullptr)
{
if (RTCHECK(ok_address(r->mchunk.ptr())))
{
TChunk *c0, *c1;
r->parent = xp;
if ((c0 = x->child[0]) != nullptr)
{
if (RTCHECK(ok_address(c0->mchunk.ptr())))
{
r->child[0] = c0;
c0->parent = r;
}
else
{
corruption_error_action();
}
}
if ((c1 = x->child[1]) != nullptr)
{
if (RTCHECK(ok_address(c1->mchunk.ptr())))
{
r->child[1] = c1;
c1->parent = r;
}
else
{
corruption_error_action();
}
}
}
else
{
corruption_error_action();
}
}
}
x->metadata_clear();
}
/**
* Throw p into the correct bin based on s. Initializes the linkages of p.
*/
void insert_chunk(MChunkHeader *p, size_t s)
{
if (is_small(s))
{
insert_small_chunk(p, s);
}
else
{
insert_large_chunk(p, s);
}
}
// Unlink p from the correct bin based on s.
void unlink_chunk(MChunk *p, size_t s)
{
if (is_small(s))
{
unlink_small_chunk(p, s);
}
else
{
unlink_large_chunk(TChunk::from_mchunk(p));
}
}
/**
* @brief Find the smallest chunk in t and allocate nb bytes from it.
*
* @return Should always succeed because we made sure this tree has chunks
* and all chunks in this tree are larger than nb. The chunk holding the
* returned memory has had its linkages cleared.
*/
MChunkHeader *tmalloc_smallest(TChunk *t, size_t nb)
{
auto tHeader = MChunkHeader::from_body(t);
size_t rsize = tHeader->size_get() - nb;
TChunk *v = t;
Debug::Assert(t != nullptr, "Chunk must not be null");
/*
* Clang analyser isn't quite clever enough and so concludes that we
* might get here with a null `t` through tmalloc_small() and a
* non-zero treemap, but a non-zero treemap means that tmalloc_small()
* will certainly find a TChunk for us.
*/
// NOLINTNEXTLINE(clang-analyzer-core.CallAndMessage)
while ((t = t->leftmost_child()) != nullptr)
{
tHeader = MChunkHeader::from_body(t);
size_t trem = tHeader->size_get() - nb;
if (trem < rsize)
{
rsize = trem;
v = t;
}
}
/*
* Prefer to unlink a ring node rather than a tree node, as this
* simplifies the work in unlink_large_chunk() below, leaving the
* tree structure unmodified.
*/
v = TChunk::from_ring(v->mchunk.ring.cell_next());
if (RTCHECK(ok_address(v->mchunk.ptr())))
{
auto vHeader = MChunkHeader::from_body(v);
Debug::Assert(vHeader->size_get() == rsize + nb,
"Chunk {} size is {}, should be {}",
v,
vHeader->size_get(),
rsize + nb);
Debug::Assert(vHeader->is_prev_in_use(),
"Free chunk {} follows another free chunk",
v);
unlink_large_chunk(v);
if (rsize >= MinChunkSize)
{
/*
* The remainder is big enough to to used by another
* allocation, place it into the free list.
*/
auto r = vHeader->split(nb);
insert_chunk(r, rsize);
}
/*
* Having split off any residual, mark this chunk in use.
*/
vHeader->mark_in_use();
return vHeader;
}
corruption_error_action();
return nullptr;
}
/**
* Allocate a large request from the best fitting chunk in a treebin.
*
* The chunk holding the returned memory has had its linkages cleared.
*/
MChunkHeader *tmalloc_large(size_t nb)
{
TChunk *v = nullptr;
size_t rsize = -nb; // unsigned negation
TChunk *t;
BIndex idx = compute_tree_index(nb);
if ((t = *treebin_at(idx)) != nullptr)
{
// Traverse tree for this bin looking for node with size >= nb.
size_t sizebits = nb << leftshift_for_tree_index(idx);
TChunk *rst = nullptr; // the deepest untaken right subtree
for (;;)
{
TChunk *rt;
auto tHeader = MChunkHeader::from_body(t);
size_t trem = tHeader->size_get() - nb;
if (trem < rsize)
{
v = t;
if ((rsize = trem) == 0)
{
break;
}
}
rt = t->child[1];
t = t->child[leftshifted_val_msb(sizebits)];
if (rt != nullptr && rt != t)
{
rst = rt;
}
if (t == nullptr)
{
t = rst; // Set t to least subtree holding sizes > nb.
break;
}
sizebits <<= 1;
}
}
if (t == nullptr && v == nullptr)
{
/*
* We didn't find anything usable in the tree, so use the next tree
* if there is one. Set t to root of next non-empty treebin.
*/
Binmap leftbits = ds::bits::above_least(idx2bit(idx)) & treemap;
if (leftbits != 0)
{
BIndex i;
Binmap leastbit = ds::bits::isolate_least(leftbits);
i = bit2idx(leastbit);
t = *treebin_at(i);
}
else
{
return nullptr;
}
}
else if (v)
{
t = v;
}
return tmalloc_smallest(t, nb);
}
/**
* @brief Allocate a small request from a tree bin. It should return a valid
* chunk successfully as long as one tree exists, because all tree chunks
* are larger than a small request.
*
* The chunk holding the returned memory has had its linkages cleared.
*/
MChunkHeader *tmalloc_small(size_t nb)
{
TChunk *t;
size_t rsize;
BIndex i;
Binmap leastbit = ds::bits::isolate_least(treemap);
i = bit2idx(leastbit);
t = *treebin_at(i);
return tmalloc_smallest(t, nb);
}
/**
* Move a chunk back onto free lists.
*
* Note that this chunk does not have to come from quarantine, because it
* can come from initialisation or splitting a free chunk. Assumes that the
* revocation shadow bits are clear in either case.
*
* Initializes the linkages of p.
*/
void mspace_free_internal(MChunkHeader *p)
{
ok_in_use_chunk(p);
heapFreeSize += p->size_get();
if (!p->is_prev_in_use())
{
// Consolidate backward
MChunkHeader *prev = p->cell_prev();
unlink_chunk(MChunk::from_header(prev), prev->size_get());
ds::linked_list::unsafe_remove_link(prev, p);
p->clear();
// p is no longer a header. Clear the shadow bit.
revoker.shadow_paint_single(CHERI::Capability{p}.address(), false);
p = prev;
}
MChunkHeader *next = p->cell_next();
if (!next->is_in_use())
{
// Consolidate forward
unlink_chunk(MChunk::from_header(next), next->size_get());
ds::linked_list::unsafe_remove_link(p, next);
next->clear();
// next is no longer a header. Clear the shadow bit.
revoker.shadow_paint_single(CHERI::Capability{next}.address(),
false);
}
p->mark_free();
insert_chunk(p, p->size_get());
ok_free_chunk(p);
}
/**
* Move a pending quarantine ring whose epoch is now past onto the finished
* quarantine ring.
*/
void quarantine_pending_to_finished()
{
if (quarantinePendingRing.is_empty())
{
for (size_t ix = 0; ix < QuarantineRings; ix++)
{
Debug::Assert(quarantine_pending_get(ix)->is_empty(),
"Empty quarantine with non-empty ring!");
}
}
decltype(quarantinePendingRing)::Ix oldestPendingIx;
if (!quarantinePendingRing.head_get(oldestPendingIx))
{
return;
}
if (!revoker.has_revocation_finished_for_epoch(
quarantinePendingEpoch[oldestPendingIx]))
{
return;
}
auto qring = quarantine_pending_get(oldestPendingIx);
/*
* If and when we support consolidation in quarantine, it may happen
* that this ring is empty, because everything that was here got
* consolidated with younger chunks. Until then, this is_empty()
* check is somewhat redundant, but take_all() behaves poorly on
* empty rings, so best to have it.
*/
if (!qring->is_empty())
{
quarantine_finished_get()->append(qring->take_all());
}
quarantinePendingRing.head_advance();
}
/**
* Push a chunk to a pending quarantine ring, possibly opening a new one
*/
void quarantine_pending_push(size_t epoch, MChunkHeader *header)
{
decltype(quarantinePendingRing)::Ix youngestPendingIx;
if (!quarantinePendingRing.tail_get(youngestPendingIx) ||
quarantinePendingEpoch[youngestPendingIx] != epoch)
{
/*
* We need to insert this object onto a new pending ring for the
* new epoch. Ensure that we have room by transferring a pending
* ring whose epoch is past onto the finished ring, if any. We can
* be waiting for at most three epochs to age out, two of which are
* merged onto one ring, and have room for two in our pending ring
* buffer. As long as the passed-in epoch is a later observation
* than those that went into the pending ring, either there is
* already room for that epoch or this will create it.
*/
quarantine_pending_to_finished();
auto opened = quarantinePendingRing.tail_next(youngestPendingIx);
quarantinePendingRing.tail_advance();
Debug::Assert(opened, "Failed to open epoch ring");
quarantinePendingEpoch[youngestPendingIx] = epoch;
}
quarantine_pending_get(youngestPendingIx)
->append_emplace(&(new (header->body()) MChunk())->ring);
}
/**
* @brief Start revocation if this MState has accumulated enough things in
* quarantine or the free space is too low.
* @param Force force start a revocation regardless of heuristics
*
* @return true if there are things in the quarantine
*/
template<bool Force = false>
bool mspace_bg_revoker_kick()
{
if (heapQuarantineSize == 0)
{
return 0;
}
/*
* Async revocation can run in the background, but sync revocation
* blocks and we don't want it to sweep too early, so we have different
* quarantine thresholds here.
*/
bool shouldKick;
if constexpr (Revocation::Revoker::IsAsynchronous)
{
shouldKick = heapQuarantineSize > heapFreeSize / 4 ||
heapFreeSize < heapTotalSize / 8;
}
else
{
shouldKick = heapQuarantineSize > heapFreeSize / 4 * 3;
}
if (Force || shouldKick)
{
revoker.system_bg_revoker_kick();
}
return 1;
}
/**
* @brief Try to dequeue the quarantine list multiple times.
*
* @param loops how many times do we try to dequeue
*/
int mspace_qtbin_deqn(size_t loops)
{
int dequeued = 0;
auto quarantine = quarantine_finished_get();
for (size_t i = 0; i < loops; i++)
{
/*
* If we're out of nodes on the finished ring, try grabbing some
* from the pending rings.
*/
if (quarantine->is_empty())
{
quarantine_pending_to_finished();
if (quarantine->is_empty())
{
break;
}
}
MChunk *fore = MChunk::from_ring(quarantine->first());
MChunkHeader *foreHeader = MChunkHeader::from_body(fore);
/*
* Detach from quarantine and zero the ring linkage; the rest of
* this chunk, apart from its header, is also zero, thanks to the
* capaligned_zero() done in mspace_free() before the chunk was
* put into quarantine. mspace_free_internal() will either rebuild
* this cons cell, if it cannot consolidate backwards, or it will
* discard the idea that this is a link cell at all by detaching
* and clearing fore's header.
*/
ds::linked_list::unsafe_remove(&fore->ring);
fore->metadata_clear();
heapQuarantineSize -= foreHeader->size_get();
/* Clear the shadow bits that marked this region as quarantined */
revoker.shadow_paint_range<false>(foreHeader->body().address(),
foreHeader->cell_next());
mspace_free_internal(foreHeader);
dequeued++;
}
return dequeued;
}
/**
* Successful end to mspace_malloc()
*/
void *mspace_malloc_success(MChunkHeader *p)
{
// If we reached here, then it means we took a real chunk off the free
// list without errors. Zero the user portion metadata.
size_t size = p->size_get();
/*
* We sanity check that things off the free list are indeed zeroed out,
* and none corresponds to a set shadow bit. We need to wrap *word
* inside a Capability because that gives exact equal for nullptr.
*/
Debug::Assert(
[&]() -> bool {
return capaligned_range_do(
p->body(), size - sizeof(MChunkHeader), [](void **word) {
CHERI::Capability eachCap{*word};
bool shadowBit = true;
if constexpr (HasTemporalSafety)
{
shadowBit = revoker.shadow_bit_get(
CHERI::Capability{word}.address());
}
return eachCap != nullptr && shadowBit;
}) == false;
},
"Memory from free list is not entirely zeroed, size {}",
size);
heapFreeSize -= size;
return p->body();
}
/**
* This is the only function that takes memory from the free list. All other
* wrappers that take memory must call this in the end.
*/
MChunkHeader *mspace_malloc_internal(size_t bytes)
{
size_t nb;
/* Move O(1) nodes from quarantine, if any are available */
quarantine_dequeue();
if (bytes <= MaxSmallRequest)
{
BIndex idx;
Binmap smallbits;
nb = (bytes < MinRequest) ? MinChunkSize : pad_request(bytes);
idx = small_index(nb);
smallbits = smallmap >> idx;
if (smallbits & 0x1U)
{ // exact match
auto p = unlink_first_small_chunk(idx);
p->mark_in_use();
ok_malloced_chunk(p, nb);
return p;
}
if (smallbits != 0)
{ // Use chunk in next nonempty smallbin.
Binmap leftbits =
(smallbits << idx) & ds::bits::above_least(idx2bit(idx));
Binmap leastbit = ds::bits::isolate_least(leftbits);
BIndex i = bit2idx(leastbit);
auto p = unlink_first_small_chunk(i);
size_t rsize = small_index2size(i) - nb;
if (rsize >= MinChunkSize)
{
auto r = p->split(nb);
insert_small_chunk(r, rsize);
}
p->mark_in_use();
ok_malloced_chunk(p, nb);
return p;
}
MChunkHeader *p;
if (treemap != 0 && (p = tmalloc_small(nb)) != nullptr)
{
ok_malloced_chunk(p, nb);
return p;
}
}
else
{
MChunkHeader *p;
nb = pad_request(bytes);
if (treemap != 0 && (p = tmalloc_large(nb)) != nullptr)
{
ok_malloced_chunk(p, nb);
return p;
}
}
/*
* Exhausted all allocation options. Force start a revocation or
* continue with synchronous revocation.
*/
mspace_bg_revoker_kick<true>();
return nullptr;
}
__always_inline void *mspace_malloc(size_t bytes)
{
auto p = mspace_malloc_internal(bytes);
if (p != nullptr)
{
return mspace_malloc_success(p);
}
return nullptr;
}
// Allocate memory with specific alignment.
void *mspace_memalign(size_t bytes, size_t alignment)
{
auto nb = pad_request(bytes);
// Make sure alignment is power of 2 (in case MINSIZE is not).
Debug::Assert((alignment & (alignment - 1)) == 0,
"Alignment {} is not a power of two",
alignment);
// fast path for not-too-big objects
if (alignment <= MallocAlignment)
{
return mspace_malloc(bytes);
}
/*
* Strategy: find a spot within that chunk that meets the alignment
* request, and then possibly free the leading and trailing space.
* Call malloc with worst case padding to hit alignment.
*/
auto p = mspace_malloc_internal(nb + alignment + MinChunkSize);
if (p == nullptr)
{
return p;
}
ptraddr_t memAddress = p->body().address();
if ((memAddress % alignment) != 0)
{
/*
* Find an aligned spot inside chunk. Since we need to give back
* leading space in a chunk of at least MINSIZE, if the first
* calculation places us at a spot with less than MINSIZE
* leader, we can move to the next aligned spot -- we've
* allocated enough total room so that this is always possible.
*/
size_t alignpad =
alignment - (memAddress & static_cast<ssize_t>(alignment - 1));
if (alignpad < MinChunkSize)
{
alignpad += alignment;
}
/*
* Break off the first chunk. This is a little subtle, in that the
* short expression here is the result of some cancellation: we
* want to generate an aligned pointer, so we need to create a
* chunk that is misaligned by -sizeof(MChunkHeader). Having used
* the ->body() address (memAddress) to compute alignpad, we have
* computed the offset from the beginning of this chunk's body to
* the aligned address. When we ask this chunk's *header* to split
* at that length, it will offset by -sizeof(MChunkHeader), since
* headers always measure lengths inclusive of themselves!
*/
auto r = p->split(alignpad);
/*
* XXX Were we to not use the general mspace_malloc above, but
* have a raw, free MChunk* from the free pool here, we could
* avoid a futile test and a presently useless test:
*
* - consolidation forward (with r) won't happen (ever), as that's
* the (start of the) chunk we're about to return.
*
* - consolidation backward won't happen either, at present, as
* mspace_malloc does not displace into the chunk it finds from
* the free pool, but, in principle, it could.
*/
mspace_free_internal(p);
p = r;
}
// Also give back spare room at the end.
auto size = p->size_get();
if (size >= nb + MinChunkSize)
{
auto r = p->split(nb);
/*
* XXX Were we to not use the general mspace_malloc above, but
* have a raw, free MChunk* from the free pool here, we could
* avoid a futile test and some duplicated work.
*
* - consolidation backward won't happen (ever), as that's the
* (tail of the) chunk we're about to return.
*
* - consolidation forward *can* happen right now, because the
* generic mspace_malloc doesn't know that we're also poised
* to trim our tail, so it may well have trimmed the chunk
* it used to satisfy our request.
*/
mspace_free_internal(r);
}
ok_malloced_chunk(p, nb);
return mspace_malloc_success(p);
}
void corruption_error_action()
{
ABORT();
}
};