diff options
Diffstat (limited to 'libbase/include/core/memory')
| -rw-r--r-- | libbase/include/core/memory/Alignment.h | 342 | ||||
| -rw-r--r-- | libbase/include/core/memory/AllocatorBase.h | 154 | ||||
| -rw-r--r-- | libbase/include/core/memory/MemAlloc.h | 124 |
3 files changed, 620 insertions, 0 deletions
diff --git a/libbase/include/core/memory/Alignment.h b/libbase/include/core/memory/Alignment.h new file mode 100644 index 0000000..a3b5d38 --- /dev/null +++ b/libbase/include/core/memory/Alignment.h @@ -0,0 +1,342 @@ +/* + R *CC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===-- rcc/Memory/Alignment.h - Useful alignment functions ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains types to represent alignments. +// They are instrumented to guarantee some invariants are preserved and prevent +// invalid manipulations. +// +// - Align represents an alignment in bytes, it is always set and always a valid +// power of two, its minimum value is 1 which means no alignment requirements. +// +// - MaybeAlign is an optional type, it may be undefined or set. When it's set +// you can get the underlying Align type by using the value() method. +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_SUPPORT_ALIGNMENT_H_ +#define LIBBASE_SUPPORT_ALIGNMENT_H_ + +#include "core/math/MathExtras.h" +#include <cassert> +#include <optional> +#ifndef NDEBUG +#include <string> +#endif // NDEBUG + +namespace rcc { + +#define ALIGN_CHECK_ISPOSITIVE(decl) \ + assert(decl > 0 && (#decl " should be defined")) + +/// This struct is a compact representation of a valid (non-zero power of two) +/// alignment. +/// It is suitable for use as static global constants. +struct Align { +private: + uint8_t ShiftValue = 0; /// The log2 of the required alignment. + /// ShiftValue is less than 64 by construction. + + friend struct MaybeAlign; + friend unsigned Log2(Align); + friend bool operator==(Align Lhs, Align Rhs); + friend bool operator!=(Align Lhs, Align Rhs); + friend bool operator<=(Align Lhs, Align Rhs); + friend bool operator>=(Align Lhs, Align Rhs); + friend bool operator<(Align Lhs, Align Rhs); + friend bool operator>(Align Lhs, Align Rhs); + friend unsigned encode(struct MaybeAlign A); + friend struct MaybeAlign decodeMaybeAlign(unsigned Value); + +public: + /// Default is byte-aligned. + constexpr Align() = default; + /// Do not perform checks in case of copy/move construct/assign, because the + /// checks have been performed when building `Other`. + constexpr Align(const Align &Other) = default; + constexpr Align(Align &&Other) = default; + constexpr Align &operator=(const Align &Other) = default; + constexpr Align &operator=(Align &&Other) = default; + + explicit Align(uint64_t Value) { + assert(Value > 0 && "Value must not be 0"); + assert(rcc::isPowerOf2_64(Value) && "Alignment is not a power of 2"); + ShiftValue = Log2_64(Value); + assert(ShiftValue < 64 && "Broken invariant"); + } + + /// Returns an alignment of `1 << Log2Value` bytes. + constexpr static Align fromLog2(unsigned Log2Value) { + assert(Log2Value < 64 && "Alignment exponent is too large"); + Align Out; + Out.ShiftValue = Log2Value; + return Out; + } + + /// This is a hole in the type system and should not be abused. + /// Needed to interact with C for instance. + constexpr uint64_t value() const { return uint64_t(1) << ShiftValue; } + + // Returns the previous alignment. + Align previous() const { + assert(ShiftValue != 0 && "Undefined operation"); + Align Out; + Out.ShiftValue = ShiftValue - 1; + return Out; + } + + /// Allow constructions of constexpr Align. + template <size_t kValue> constexpr static Align Constant() { + return fromLog2(ConstantLog2<kValue>()); + } + + /// Allow constructions of constexpr Align from types. + /// Compile time equivalent to Align(alignof(T)). + template <typename T> constexpr static Align Of() { + return Constant<std::alignment_of_v<T>>(); + } +}; + +/// Treats the value 0 as a 1, so Align is always at least 1. +inline Align assumeAligned(uint64_t Value) { + return Value ? Align(Value) : Align(); +} + +/// This struct is a compact representation of a valid (power of two) or +/// undefined (0) alignment. +struct MaybeAlign : std::optional<Align> { +private: + using UP = std::optional<Align>; + +public: + /// Default is undefined. + MaybeAlign() = default; + /// Do not perform checks in case of copy/move construct/assign, because the + /// checks have been performed when building `Other`. + MaybeAlign(const MaybeAlign &Other) = default; + MaybeAlign &operator=(const MaybeAlign &Other) = default; + MaybeAlign(MaybeAlign &&Other) = default; + MaybeAlign &operator=(MaybeAlign &&Other) = default; + + constexpr MaybeAlign(std::nullopt_t None) : UP(None) {} + constexpr MaybeAlign(Align Value) : UP(Value) {} + explicit MaybeAlign(uint64_t Value) { + assert((Value == 0 || rcc::isPowerOf2_64(Value)) && + "Alignment is neither 0 nor a power of 2"); + if (Value) + emplace(Value); + } + + /// For convenience, returns a valid alignment or 1 if undefined. + Align valueOrOne() const { return value_or(Align()); } +}; + +/// Checks that SizeInBytes is a multiple of the alignment. +inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { + return SizeInBytes % Lhs.value() == 0; +} + +/// Checks that Addr is a multiple of the alignment. +inline bool isAddrAligned(Align Lhs, const void *Addr) { + return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr)); +} + +/// Returns a multiple of A needed to store `Size` bytes. +constexpr inline uint64_t alignTo(uint64_t Size, Align A) { + const uint64_t Value = A.value(); + // The following line is equivalent to `(Size + Value - 1) / Value * Value`. + + // The division followed by a multiplication can be thought of as a right + // shift followed by a left shift which zeros out the extra bits produced in + // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out + // are just zero. + + // Most compilers can generate this code but the pattern may be missed when + // multiple functions gets inlined. + return (Size + Value - 1) & ~(Value - 1U); +} + +/// If non-zero \p Skew is specified, the return value will be a minimal integer +/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for +/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p +/// Skew mod \p A'. +/// +/// Examples: +/// \code +/// alignTo(5, Align(8), 7) = 7 +/// alignTo(17, Align(8), 1) = 17 +/// alignTo(~0LL, Align(8), 3) = 3 +/// \endcode +inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { + const uint64_t Value = A.value(); + Skew %= Value; + return alignTo(Size - Skew, A) + Skew; +} + +/// Aligns `Addr` to `Alignment` bytes, rounding up. +inline uintptr_t alignAddr(const void *Addr, Align Alignment) { + uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); + assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >= + ArithAddr && + "Overflow"); + return alignTo(ArithAddr, Alignment); +} + +/// Returns the offset to the next integer (mod 2**64) that is greater than +/// or equal to \p Value and is a multiple of \p Align. +inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { + return alignTo(Value, Alignment) - Value; +} + +/// Returns the necessary adjustment for aligning `Addr` to `Alignment` +/// bytes, rounding up. +inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { + return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment); +} + +/// Returns the log2 of the alignment. +inline unsigned Log2(Align A) { return A.ShiftValue; } + +/// Returns the alignment that satisfies both alignments. +/// Same semantic as MinAlign. +inline Align commonAlignment(Align A, uint64_t Offset) { + return Align(MinAlign(A.value(), Offset)); +} + +/// Returns a representation of the alignment that encodes undefined as 0. +inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } + +/// Dual operation of the encode function above. +inline MaybeAlign decodeMaybeAlign(unsigned Value) { + if (Value == 0) + return MaybeAlign(); + Align Out; + Out.ShiftValue = Value - 1; + return Out; +} + +/// Returns a representation of the alignment, the encoded value is positive by +/// definition. +inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } + +/// Comparisons between Align and scalars. Rhs must be positive. +inline bool operator==(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() == Rhs; +} +inline bool operator!=(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() != Rhs; +} +inline bool operator<=(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() <= Rhs; +} +inline bool operator>=(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() >= Rhs; +} +inline bool operator<(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() < Rhs; +} +inline bool operator>(Align Lhs, uint64_t Rhs) { + ALIGN_CHECK_ISPOSITIVE(Rhs); + return Lhs.value() > Rhs; +} + +/// Comparisons operators between Align. +inline bool operator==(Align Lhs, Align Rhs) { + return Lhs.ShiftValue == Rhs.ShiftValue; +} +inline bool operator!=(Align Lhs, Align Rhs) { + return Lhs.ShiftValue != Rhs.ShiftValue; +} +inline bool operator<=(Align Lhs, Align Rhs) { + return Lhs.ShiftValue <= Rhs.ShiftValue; +} +inline bool operator>=(Align Lhs, Align Rhs) { + return Lhs.ShiftValue >= Rhs.ShiftValue; +} +inline bool operator<(Align Lhs, Align Rhs) { + return Lhs.ShiftValue < Rhs.ShiftValue; +} +inline bool operator>(Align Lhs, Align Rhs) { + return Lhs.ShiftValue > Rhs.ShiftValue; +} + +// Don't allow relational comparisons with MaybeAlign. +bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; +bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; +bool operator<(Align Lhs, MaybeAlign Rhs) = delete; +bool operator>(Align Lhs, MaybeAlign Rhs) = delete; + +bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; +bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; +bool operator<(MaybeAlign Lhs, Align Rhs) = delete; +bool operator>(MaybeAlign Lhs, Align Rhs) = delete; + +bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; + +// Allow equality comparisons between Align and MaybeAlign. +inline bool operator==(MaybeAlign Lhs, Align Rhs) { return Lhs && *Lhs == Rhs; } +inline bool operator!=(MaybeAlign Lhs, Align Rhs) { return !(Lhs == Rhs); } +inline bool operator==(Align Lhs, MaybeAlign Rhs) { return Rhs == Lhs; } +inline bool operator!=(Align Lhs, MaybeAlign Rhs) { return !(Rhs == Lhs); } +// Allow equality comparisons with MaybeAlign. +inline bool operator==(MaybeAlign Lhs, MaybeAlign Rhs) { + return (Lhs && Rhs && (*Lhs == *Rhs)) || (!Lhs && !Rhs); +} +inline bool operator!=(MaybeAlign Lhs, MaybeAlign Rhs) { return !(Lhs == Rhs); } +// Allow equality comparisons with std::nullopt. +inline bool operator==(MaybeAlign Lhs, std::nullopt_t) { return !bool(Lhs); } +inline bool operator!=(MaybeAlign Lhs, std::nullopt_t) { return bool(Lhs); } +inline bool operator==(std::nullopt_t, MaybeAlign Rhs) { return !bool(Rhs); } +inline bool operator!=(std::nullopt_t, MaybeAlign Rhs) { return bool(Rhs); } + +#ifndef NDEBUG +// For usage in LLVM_DEBUG macros. +inline std::string DebugStr(const Align &A) { + return std::to_string(A.value()); +} +// For usage in LLVM_DEBUG macros. +inline std::string DebugStr(const MaybeAlign &MA) { + if (MA) + return std::to_string(MA->value()); + return "None"; +} +#endif // NDEBUG + +#undef ALIGN_CHECK_ISPOSITIVE + +} // namespace rcc + +#endif // LIBBASE_SUPPORT_ALIGNMENT_H_ diff --git a/libbase/include/core/memory/AllocatorBase.h b/libbase/include/core/memory/AllocatorBase.h new file mode 100644 index 0000000..248ea9b --- /dev/null +++ b/libbase/include/core/memory/AllocatorBase.h @@ -0,0 +1,154 @@ +/* + R *CC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- AllocatorBase.h - Simple memory allocation abstraction ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines MallocAllocator. MallocAllocator conforms to the LLVM +/// "Allocator" concept which consists of an Allocate method accepting a size +/// and alignment, and a Deallocate accepting a pointer and size. Further, the +/// LLVM "Allocator" concept has overloads of Allocate and Deallocate for +/// setting size and alignment based on the final type. These overloads are +/// typically provided by a base class template \c AllocatorBase. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_SUPPORT_ALLOCATORBASE_H +#define LIBBASE_SUPPORT_ALLOCATORBASE_H + +#ifdef _MSC_VER +#define LIBBASE_ALLOCATORHOLDER_EMPTYBASE __declspec(empty_bases) +#else +#define LIBBASE_ALLOCATORHOLDER_EMPTYBASE +#endif // _MSC_VER + +#include "core/compiler/Compiler.h" +#include "core/memory/MemAlloc.h" +#include <type_traits> +#include <utility> + +namespace rcc { + +/// CRTP base class providing obvious overloads for the core \c +/// Allocate() methods of LLVM-style allocators. +/// +/// This base class both documents the full public interface exposed by all +/// LLVM-style allocators, and redirects all of the overloads to a single core +/// set of methods which the derived class must define. +template <typename DerivedT> class AllocatorBase { +public: + /// Allocate \a Size bytes of \a Alignment aligned memory. This method + /// must be implemented by \c DerivedT. + void *Allocate(size_t Size, size_t Alignment) { +#ifdef __clang__ + static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>( + &AllocatorBase::Allocate) != + static_cast<void *(DerivedT::*)(size_t, size_t)>( + &DerivedT::Allocate), + "Class derives from AllocatorBase without implementing the " + "core Allocate(size_t, size_t) overload!"); +#endif + return static_cast<DerivedT *>(this)->Allocate(Size, Alignment); + } + + /// Deallocate \a Ptr to \a Size bytes of memory allocated by this + /// allocator. + void Deallocate(const void *Ptr, size_t Size, size_t Alignment) { +#ifdef __clang__ + static_assert( + static_cast<void (AllocatorBase::*)(const void *, size_t, size_t)>( + &AllocatorBase::Deallocate) != + static_cast<void (DerivedT::*)(const void *, size_t, size_t)>( + &DerivedT::Deallocate), + "Class derives from AllocatorBase without implementing the " + "core Deallocate(void *) overload!"); +#endif + return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size, Alignment); + } + + // The rest of these methods are helpers that redirect to one of the above + // core methods. + + /// Allocate space for a sequence of objects without constructing them. + template <typename T> T *Allocate(size_t Num = 1) { + return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T))); + } + + /// Deallocate space for a sequence of objects without constructing them. + template <typename T> + std::enable_if_t<!std::is_same_v<std::remove_cv_t<T>, void>, void> + Deallocate(T *Ptr, size_t Num = 1) { + Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T), alignof(T)); + } +}; + +class MallocAllocator : public AllocatorBase<MallocAllocator> { +public: + void Reset() {} + + LIBBASE_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size, size_t Alignment) { + return allocate_buffer(Size, Alignment); + } + + // Pull in base class overloads. + using AllocatorBase<MallocAllocator>::Allocate; + + void Deallocate(const void *Ptr, size_t Size, size_t Alignment) { + deallocate_buffer(const_cast<void *>(Ptr), Size, Alignment); + } + + // Pull in base class overloads. + using AllocatorBase<MallocAllocator>::Deallocate; + + void PrintStats() const {} +}; + +namespace detail { + +template <typename Alloc> class AllocatorHolder : Alloc { +public: + AllocatorHolder() = default; + AllocatorHolder(const Alloc &A) : Alloc(A) {} + AllocatorHolder(Alloc &&A) : Alloc(std::move(A)) {} + Alloc &getAllocator() { return *this; } + const Alloc &getAllocator() const { return *this; } +}; + +template <typename Alloc> class AllocatorHolder<Alloc &> { + Alloc &A; + +public: + AllocatorHolder(Alloc &A) : A(A) {} + Alloc &getAllocator() { return A; } + const Alloc &getAllocator() const { return A; } +}; + +} // namespace detail + +} // namespace rcc + +#endif // LIBBASE_SUPPORT_ALLOCATORBASE_H diff --git a/libbase/include/core/memory/MemAlloc.h b/libbase/include/core/memory/MemAlloc.h new file mode 100644 index 0000000..bd98864 --- /dev/null +++ b/libbase/include/core/memory/MemAlloc.h @@ -0,0 +1,124 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- MemAlloc.h - Memory allocation functions -----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines counterparts of C library allocation functions defined in +/// the namespace 'std'. The new allocation functions crash on allocation +/// failure instead of returning null pointer. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_SUPPORT_MEMALLOC_H +#define LIBBASE_SUPPORT_MEMALLOC_H + +#include "core/compiler/Compiler.h" +#include "core/error/ErrorHandling.h" +#include <cstdlib> + +namespace rcc +{ + +LIBBASE_ATTRIBUTE_RETURNS_NONNULL inline void * +safe_malloc (size_t Sz) +{ + void *Result = std::malloc (Sz); + if (Result == nullptr) + { + // It is implementation-defined whether allocation occurs if the space + // requested is zero (ISO/IEC 9899:2018 7.22.3). Retry, requesting + // non-zero, if the space requested was zero. + if (Sz == 0) + { + return safe_malloc (1); + } + report_bad_alloc_error ("Allocation failed"); + } + return Result; +} + +LIBBASE_ATTRIBUTE_RETURNS_NONNULL inline void * +safe_calloc (size_t Count, size_t Sz) +{ + void *Result = std::calloc (Count, Sz); + if (Result == nullptr) + { + // It is implementation-defined whether allocation occurs if the space + // requested is zero (ISO/IEC 9899:2018 7.22.3). Retry, requesting + // non-zero, if the space requested was zero. + if (Count == 0 || Sz == 0) + { + return safe_malloc (1); + } + report_bad_alloc_error ("Allocation failed"); + } + return Result; +} + +LIBBASE_ATTRIBUTE_RETURNS_NONNULL inline void * +safe_realloc (void *Ptr, size_t Sz) +{ + void *Result = std::realloc (Ptr, Sz); + if (Result == nullptr) + { + // It is implementation-defined whether allocation occurs if the space + // requested is zero (ISO/IEC 9899:2018 7.22.3). Retry, requesting + // non-zero, if the space requested was zero. + if (Sz == 0) + { + return safe_malloc (1); + } + report_bad_alloc_error ("Allocation failed"); + } + return Result; +} + +/// Allocate a buffer of memory with the given size and alignment. +/// +/// When the compiler supports aligned operator new, this will use it to +/// handle even over-aligned allocations. +/// +/// However, this doesn't make any attempt to leverage the fancier techniques +/// like posix_memalign due to portability. It is mostly intended to allow +/// compatibility with platforms that, after aligned allocation was added, use +/// reduced default alignment. +LIBBASE_ABI LIBBASE_ATTRIBUTE_RETURNS_NONNULL LIBBASE_ATTRIBUTE_RETURNS_NOALIAS void * +allocate_buffer (size_t Size, size_t Alignment); + +/// Deallocate a buffer of memory with the given size and alignment. +/// +/// If supported, this will used the sized delete operator. Also if supported, +/// this will pass the alignment to the delete operator. +/// +/// The pointer must have been allocated with the corresponding new operator, +/// most likely using the above helper. +LIBBASE_ABI void +deallocate_buffer (void *Ptr, size_t Size, size_t Alignment); + +} // namespace rcc +#endif |