[utils] Add HeapArray Add dawn::HeapArray, similar to base::HeapArray. It is like std::unique_ptr<T[]>, but carries its size so it can be used safely. Unlike base::HeapArray, it uses a typed index. Note that unlike dawn::Span, it's always index-typed. Clients use dawn::HeapArray<size_t, T> if they want untyped indices. Used subsequently. Bug: 512465980 Change-Id: I971cbcb95c75d296295bc885f07672ab8ff92451 Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/302858 Auto-Submit: Kai Ninomiya <kainino@chromium.org> Reviewed-by: Corentin Wallez <cwallez@chromium.org> Commit-Queue: Kai Ninomiya <kainino@chromium.org>
diff --git a/src/dawn/native/BlobCache.cpp b/src/dawn/native/BlobCache.cpp index 7e95989..f3d0aa7 100644 --- a/src/dawn/native/BlobCache.cpp +++ b/src/dawn/native/BlobCache.cpp
@@ -50,7 +50,7 @@ std::vector<std::byte> GenerateHashPrefixedPayload(std::span<const std::byte> value) { // Create a buffer for holding hash+payload. - // TODO(crbug.com/512465980): Use ityp::heap_array instead of std::vector. + // TODO(https://crbug.com/512465980): Use HeapArray instead of std::vector. const size_t byteSizeWithHash = value.size() + kHashByteSize; std::vector<std::byte> result(byteSizeWithHash);
diff --git a/src/utils/BUILD.bazel b/src/utils/BUILD.bazel index 6edb2ba..6f5ec91 100644 --- a/src/utils/BUILD.bazel +++ b/src/utils/BUILD.bazel
@@ -37,6 +37,7 @@ "compiler.h", "force_crash.h", "gtest.h", + "heap_array.h", "log.h", "non_copyable.h", "non_movable.h",
diff --git a/src/utils/BUILD.gn b/src/utils/BUILD.gn index 18319dc..1d0da38 100644 --- a/src/utils/BUILD.gn +++ b/src/utils/BUILD.gn
@@ -286,6 +286,7 @@ "assert.h", "compiler.h", "force_crash.h", + "heap_array.h", "log.cc", "log.h", "non_copyable.h", @@ -317,6 +318,7 @@ dawn_nocompile_source_set("nocompile_sources") { deps = [ ":utils" ] sources = [ + "heap_array_nocompile.nc", "numeric_nocompile.nc", "span_nocompile.nc", "typed_integer_nocompile.nc", @@ -339,6 +341,7 @@ sources = [ "assert_test.cc", + "heap_array_test.cc", "numeric_test.cc", "span_tests.cc", "typed_integer_tests.cc",
diff --git a/src/utils/CMakeLists.txt b/src/utils/CMakeLists.txt index bdd5ad4..5fde89d 100644 --- a/src/utils/CMakeLists.txt +++ b/src/utils/CMakeLists.txt
@@ -30,6 +30,7 @@ "compiler.h" "force_crash.h" "gtest.h" + "heap_array.h" "log.h" "non_copyable.h" "non_movable.h"
diff --git a/src/utils/compiler.h b/src/utils/compiler.h index 5766a64..6ad9912 100644 --- a/src/utils/compiler.h +++ b/src/utils/compiler.h
@@ -105,6 +105,19 @@ #endif #endif +// DAWN_MSAN_ENABLED() +// +// Checks whether MSan is enabled. +#if DAWN_COMPILER_IS(CLANG) +#define DAWN_MSAN_ENABLED() __has_feature(memory_sanitizer) +#elif DAWN_COMPILER_IS(GCC) || DAWN_COMPILER_IS(MSVC) +#if defined(__SANITIZE_ADDRESS__) +#define DAWN_MSAN_ENABLED() 1 +#else +#define DAWN_MSAN_ENABLED() 0 +#endif +#endif + // DAWN_NO_SANITIZE(instrumentation) // // Annotate a function or a global variable declaration to specify that a particular instrumentation
diff --git a/src/utils/heap_array.h b/src/utils/heap_array.h new file mode 100644 index 0000000..db653d8 --- /dev/null +++ b/src/utils/heap_array.h
@@ -0,0 +1,244 @@ +// Copyright 2026 The Dawn & Tint Authors +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef SRC_UTILS_HEAP_ARRAY_H_ +#define SRC_UTILS_HEAP_ARRAY_H_ + +#include <algorithm> +#include <cstddef> +#include <limits> +#include <ranges> +#include <type_traits> +#include <utility> + +#include "src/utils/non_copyable.h" +#include "src/utils/numeric.h" +#include "src/utils/span.h" +#include "src/utils/underlying_type.h" + +namespace dawn { + +namespace ityp { + +// "Lite", index-typed version of base::HeapArray from Chromium. It's like a safer, sized +// std::unique_ptr<T[]>, and it has a nicer (span-like / std::ranges-compatible) interface. +// To convert to an actual span, use `Span{heapArray}`, which constructs it via std::ranges. +// +// Note that just like new[], it's invalid to reinterpret to another type UNLESS the element type is +// char or std::byte AND the target type's alignment is <= alignof(std::max_align_t). +template <HasUnsignedUnderlyingType Index, typename Value> +class HeapArray : + // Could be copyable, if needed, but we haven't needed it. + public NonCopyable { + private: + using I = UnderlyingType<Index>; + // TODO(https://crbug.com/526537224): This should probably be a RawSpan. + using TSpan = ityp::span<Index, Value>; + + // HeapArrays never start with data in them, so a constant HeapArray wouldn't be usable. + // If we really want that, we can implement a move-constructor from non-const to const. + static_assert(!std::is_const_v<Value>, + "Array contents cannot be constant. Use `const HeapArray<I, V>` instead of " + "`HeapArray<I, const V>`."); + + public: + // Constructs an empty HeapArray. (Note it cannot be resized.) + constexpr HeapArray() = default; + + constexpr HeapArray(HeapArray<Index, Value>&& other) { *this = std::move(other); } + constexpr HeapArray<Index, Value>& operator=(HeapArray<Index, Value>&& other) { + mOwnedData = other.mOwnedData; + other.mOwnedData = {}; + return *this; + } + + constexpr ~HeapArray() { + if (Value* ptr = mOwnedData.data()) { + mOwnedData = {}; + delete[] ptr; + } + } + + // Constructs a zero-initialized HeapArray with count `count`. + constexpr explicit HeapArray(Index count) + // SAFETY: Allocation size matches container size. + : DAWN_UNSAFE_BUFFERS(HeapArray{Alloc(count, InitType::Init), count}) { + // Even if count is 0, the new[] shouldn't have returned nullptr. + DAWN_ASSERT(mOwnedData.data() != nullptr); + } + // Constructs a zero-initialized HeapArray with count `count`. + // If allocation fails, returns a falsy object, with .data() == nullptr and .size() == 0. + constexpr HeapArray(Index count, std::nothrow_t) + // SAFETY: Allocation size matches container size; private constructor handles if it fails. + : DAWN_UNSAFE_BUFFERS(HeapArray{AllocNoThrow(count, InitType::Init), count}) { + if (mOwnedData.data() == nullptr) { + DAWN_ASSERT(mOwnedData.size() == Index{}); + } + } + + // Constructs an uninitialized HeapArray with count `count`. + // This can only be used with POD types, as other types are always initialized. + [[nodiscard]] DAWN_UNSAFE_BUFFER_USAGE static constexpr HeapArray<Index, Value> Uninit( + Index count) + requires std::is_trivially_default_constructible_v<Value> + { + return HeapArray<Index, Value>{Alloc(count, InitType::Uninit), count}; + } + // Constructs an uninitialized HeapArray with count `count`, or count 0 if allocation fails. + // This can only be used with POD types, as other types are always initialized. + [[nodiscard]] DAWN_UNSAFE_BUFFER_USAGE static constexpr HeapArray<Index, Value> Uninit( + Index count, + std::nothrow_t) + requires std::is_trivially_default_constructible_v<Value> + { + return HeapArray<Index, Value>{AllocNoThrow(count, InitType::Uninit), count}; + } + + // Acquire the contents as a raw pointer and size (kind of like what you get from new[] - it's + // valid to delete using `delete[]`). + // Useful with std::tie when returning a size+ptr array (e.g. via the webgpu.h API). + constexpr std::pair<size_t, Value*> MoveToRawPointer() && { + auto data = mOwnedData; + mOwnedData = {}; + return {checked_cast<size_t>(data.size()), data.data()}; + } + + // Returns true if the allocation succeeded. This can be used like `if (myHeapArray) {}` to + // check if nothrow allocation succeeded. Note, even if the size is 0, this may return true. + constexpr explicit operator bool() { return mOwnedData.data() != nullptr; } + + // Span-like interface + constexpr inline auto empty() const { return mOwnedData.empty(); } + constexpr inline auto data() { return mOwnedData.data(); } + constexpr inline auto data() const { return mOwnedData.data(); } + constexpr inline auto size() const { return mOwnedData.size(); } + constexpr inline auto begin() { return mOwnedData.begin(); } + constexpr inline auto begin() const { return mOwnedData.begin(); } + constexpr inline auto end() { return mOwnedData.end(); } + constexpr inline auto end() const { return mOwnedData.end(); } + constexpr inline auto subspan(Index offset) { return mOwnedData.subspan(offset); } + constexpr inline auto subspan(Index offset) const { return mOwnedData.subspan(offset); } + constexpr inline auto subspan(Index offset, Index count) { + return mOwnedData.subspan(offset, count); + } + constexpr inline auto subspan(Index offset, Index count) const { + return mOwnedData.subspan(offset, count); + } + constexpr inline auto& front() { return mOwnedData.front(); } + constexpr inline const auto& front() const { return mOwnedData.front(); } + constexpr inline auto& back() { return mOwnedData.back(); } + constexpr inline const auto& back() const { return mOwnedData.back(); } + constexpr inline auto& operator[](Index i) { return mOwnedData[i]; } + constexpr inline const auto& operator[](Index i) const { return mOwnedData[i]; } + + private: + // Constructs a HeapArray by taking ownership of an existing allocation that was allocated with + // new[] (we will free it with delete[]). If the allocation is nullptr, we treat it as a failed + // allocation (e.g. from AllocNoThrow), and replace the count with 0. + [[nodiscard]] DAWN_UNSAFE_BUFFER_USAGE constexpr HeapArray(Value* data, Index count) + : mOwnedData{data ? TSpan{data, count} : TSpan{}} {} + + enum class InitType { + // Value-initialized + Init, + // For trivially constructible default types this uses their default-initialization which + // leaves the value as uninitialized memory. + Uninit, + }; + + static constexpr Value* Alloc(Index count, InitType initType) { + switch (initType) { + case InitType::Init: + return new Value[checked_cast<size_t>(count)]{}; + case InitType::Uninit: + return new Value[checked_cast<size_t>(count)]; + } + DAWN_UNREACHABLE(); + return nullptr; + } + + static constexpr Value* AllocNoThrow(Index count, InitType initType) { +#if DAWN_ASAN_ENABLED() || DAWN_MSAN_ENABLED() + // std::nothrow isn't implemented in sanitizers and they often have a 2GB allocation + // limit. Catch large allocations and error out so fuzzers make progress. + constexpr size_t kLargestAllowedAllocationAttemptBytes = 0x70000000; +#else + constexpr size_t kLargestAllowedAllocationAttemptBytes = + std::numeric_limits<size_t>::max() - 4095; +#endif + + // Early-fail to cover two cases: + // - The checked_cast is going to fail. + // - The total allocation size is going to be too close to the whole address space. + // PartitionAlloc in particular crashes instead of failing if (size >= SIZE_MAX - 23). + if (I{count} > kLargestAllowedAllocationAttemptBytes / sizeof(Value)) { + return nullptr; + } + + switch (initType) { + case InitType::Init: + return new (std::nothrow) Value[checked_cast<size_t>(count)]{}; + case InitType::Uninit: + return new (std::nothrow) Value[checked_cast<size_t>(count)]; + } + DAWN_UNREACHABLE(); + return nullptr; + } + + // We store this as a span, but we own its allocation. + // {nullptr, 0} = failed to allocate. (operator bool() returns false) + // {non-null, size} = succeeded in allocating, even if size==0. (operator bool() returns true) + TSpan mOwnedData; +}; + +// Construct a HeapArray by copying its data from a range. +template <typename Index> +[[nodiscard]] static constexpr auto HeapArrayFrom(const std::ranges::sized_range auto& src) { + // Infer the value type. (HeapArrayFrom is defined outside HeapArray so that we can do this.) + using Value = std::ranges::range_value_t<decltype(src)>; + + Index size = checked_cast<Index>(std::ranges::size(src)); + + // SAFETY: Initialized by the copy. + auto result = DAWN_UNSAFE_BUFFERS(HeapArray<Index, Value>::Uninit(size)); + std::ranges::copy(src, result.begin()); + return result; +} + +} // namespace ityp + +// Aliases in the dawn:: namespace with size_t for the index type. +template <typename Value> +using HeapArray = ityp::HeapArray<size_t, Value>; + +[[nodiscard]] static constexpr auto HeapArrayFrom(const std::ranges::sized_range auto& src) { + return ityp::HeapArrayFrom<size_t>(src); +} + +} // namespace dawn + +#endif // SRC_UTILS_HEAP_ARRAY_H_
diff --git a/src/utils/heap_array_nocompile.nc b/src/utils/heap_array_nocompile.nc new file mode 100644 index 0000000..473b6e3 --- /dev/null +++ b/src/utils/heap_array_nocompile.nc
@@ -0,0 +1,94 @@ +// Copyright 2026 The Dawn & Tint Authors +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// Test the type checks of dawn::Span. +// Note: all unsafe buffer warning tests are in warning_nocompile.nc. + +#include <array> + +#include "src/utils/heap_array.h" +#include "src/utils/typed_integer.h" + +namespace dawn { + +static constexpr std::array<int, 5> kSpanData = {1, 2, 3, 4, 5}; + +using Index = TypedInteger<struct IndexT, uint32_t>; +using IndexSizeT = TypedInteger<struct IndexT, size_t>; +enum class Val {}; + +using TypedHeapArray = ityp::HeapArray<Index, Val>; +using UntypedHeapArray = HeapArray<Val>; +using SmallUntypedHeapArray = ityp::HeapArray<uint8_t, Val>; +using TypedHeapArrayPOD = ityp::HeapArray<Index, int>; + +void TestConstValue() { + { HeapArray<const int> x; } // expected-error@heap_array.h:* {{Array contents cannot be constant}} +} + +// Uninit can only be used when the value type is capable of being uninitialized. +void TestUninit() { + (void)HeapArray<int>::Uninit(4); + (void)HeapArray<Val>::Uninit(4); + (void)HeapArray<Index>::Uninit(4); // expected-error {{no matching function for call to 'Uninit'}} +} + +void TestConversionToSpan() { + TypedHeapArray arr{Index{10u}}; + + // dawn::Span cannot construct from a range with a different index type. + // This probably isn't important and could be changed. + (void)ityp::span<Index, Val>(arr); + (void)dawn::Span<Val>(arr); // expected-error {{no matching conversion for functional-style cast from}} +} + +void TestIndexing() { + { + TypedHeapArray arr(Index{4u}); + arr[Index{0u}]; // Control case. + arr[0u]; // expected-error {{no viable overloaded operator[]}} + } + { + UntypedHeapArray arr(4); + arr[0u]; // Control case. + // TODO(https://crbug.com/42240462): This should be an invalid implicit integer conversion. + arr[0]; // Control case. + arr[Index{0u}]; // expected-error {{no viable overloaded operator[]}} + } + { + SmallUntypedHeapArray arr(4); + arr[255]; // Control case. + arr[256]; // expected-error {{implicit conversion from 'int' to 'unsigned char' changes value}} + + arr[uint8_t{0}]; // Control case. + // TODO(https://crbug.com/42240462): These should be invalid implicit integer conversions. + arr[uint32_t{0}]; + arr[int8_t{0}]; + } +} + +} // namespace dawn
diff --git a/src/utils/heap_array_test.cc b/src/utils/heap_array_test.cc new file mode 100644 index 0000000..ea6d0ee --- /dev/null +++ b/src/utils/heap_array_test.cc
@@ -0,0 +1,385 @@ +// Copyright 2026 The Dawn & Tint Authors +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "src/utils/heap_array.h" + +#include <array> +#include <limits> +#include <ranges> + +#include "src/utils/gtest.h" +#include "src/utils/typed_integer.h" + +namespace dawn { +namespace { + +class HeapArrayTest : public ::testing::Test { + protected: + using Index = TypedInteger<struct KeyT, size_t>; + using Val = TypedInteger<struct ValT, uint32_t>; + using HeapArrayVal = ityp::HeapArray<Index, Val>; + + // Type for use with Uninit() which requires a POD value type. + using HeapArrayPOD = ityp::HeapArray<Index, int>; +}; + +// Name "*DeathTest" per https://google.github.io/googletest/advanced.html#death-test-naming +using HeapArrayDeathTest = HeapArrayTest; + +TEST_F(HeapArrayTest, KeyTypes) { + (void)ityp::HeapArray<TypedInteger<struct KU8, uint8_t>, int>(); + (void)ityp::HeapArray<TypedInteger<struct KU32, uint32_t>, int>(); + (void)ityp::HeapArray<TypedInteger<struct KSizeT, size_t>, int>(); + + enum class E : uint32_t {}; + (void)ityp::HeapArray<E, int>(); + + (void)ityp::HeapArray<uint16_t, int>(); +} + +// Test that values can be set at an index and retrieved from the same index. +TEST_F(HeapArrayTest, Indexing) { + HeapArrayVal arr{Index{10u}}; + { + arr[Index{2u}] = Val{5u}; + arr[Index{1u}] = Val{9u}; + arr[Index{9u}] = Val{2u}; + arr.front() = Val{8u}; + + EXPECT_EQ(arr[Index{2u}], Val{5u}); + EXPECT_EQ(arr[Index{1u}], Val{9u}); + EXPECT_EQ(arr[Index{9u}], Val{2u}); + EXPECT_EQ(arr.front(), Val{8u}); + } +} + +// Test that the HeapArray can be iterated in order with a range-based for loop +TEST_F(HeapArrayTest, RangeBasedIteration) { + // Also check that it satisfies various range concepts. + static_assert(std::ranges::common_range<HeapArrayVal>); + static_assert(std::ranges::contiguous_range<HeapArrayVal>); + static_assert(std::ranges::input_range<HeapArrayVal>); + static_assert(std::ranges::output_range<HeapArrayVal, Val>); + static_assert(std::ranges::sized_range<HeapArrayVal>); + static_assert(std::ranges::viewable_range<HeapArrayVal>); + static_assert(!std::ranges::borrowed_range<HeapArrayVal>); + static_assert(!std::ranges::view<HeapArrayVal>); + + HeapArrayVal arr{Index{10u}}; + EXPECT_TRUE(bool{arr}); + + // Assign in a non-const range-based for loop + for (uint32_t i = 0; Val& val : arr) { + val = Val(i); + } + + // Check values in a const range-based for loop + for (uint32_t i = 0; Val val : static_cast<const HeapArrayVal&>(arr)) { + EXPECT_EQ(val, arr[Index(i++)]); + } +} + +// Test that begin/end/front/back/data return pointers/references to the correct elements. +TEST_F(HeapArrayTest, BeginEndFrontBackData) { + HeapArrayVal arr{Index{10u}}; + + // non-const versions + EXPECT_EQ(&*arr.begin(), &arr[Index{0u}]); + EXPECT_EQ(&*arr.end(), + // SAFETY: Comparing safe implementation with unsafe re-implementation. + DAWN_UNSAFE_BUFFERS(&arr[Index{0u}] + static_cast<size_t>(arr.size()))); + EXPECT_EQ(&arr.front(), &arr[Index{0u}]); + EXPECT_EQ(&arr.back(), &arr[Index{9u}]); + EXPECT_EQ(arr.data(), &arr[Index{0u}]); + + // const versions + const HeapArrayVal& constArr = arr; + EXPECT_EQ(&*constArr.begin(), &constArr[Index{0u}]); + EXPECT_EQ(&*constArr.end(), + // SAFETY: Comparing safe implementation with unsafe re-implementation. + DAWN_UNSAFE_BUFFERS(&constArr[Index{0u}] + static_cast<size_t>(constArr.size()))); + EXPECT_EQ(&constArr.front(), &constArr[Index{0u}]); + EXPECT_EQ(&constArr.back(), &constArr[Index{9u}]); + EXPECT_EQ(constArr.data(), &constArr[Index{0u}]); +} + +// Empty HeapArray. +TEST_F(HeapArrayTest, Empty) { + { + HeapArrayVal arr{Index{0u}}; + EXPECT_TRUE(bool{arr}); + EXPECT_NE(nullptr, arr.data()); + EXPECT_EQ(Index{0u}, arr.size()); + } + { + HeapArrayVal arr{Index{0u}, std::nothrow}; + EXPECT_TRUE(bool{arr}); + EXPECT_NE(nullptr, arr.data()); + EXPECT_EQ(Index{0u}, arr.size()); + } +} + +// `Uninit`ialized HeapArray. +TEST_F(HeapArrayTest, Uninit) { + // SAFETY: Testing unsafe API. + auto arr = DAWN_UNSAFE_BUFFERS(HeapArrayPOD::Uninit(Index{1u})); + EXPECT_TRUE(bool{arr}); + + arr[Index{0u}] = 5; + EXPECT_EQ(arr[Index{0u}], 5); +} + +// Tests for the HeapArrayFrom helper. +TEST_F(HeapArrayTest, HeapArrayFrom) { + constexpr std::array<int, 5> kSrc = {1, 2, 3, 4, 5}; + { + auto arr = ityp::HeapArrayFrom<Index>(kSrc); + EXPECT_EQ(arr[Index{0u}], 1); + EXPECT_EQ(arr[Index{4u}], 5); + } + { + auto arr = HeapArrayFrom(kSrc); + EXPECT_EQ(arr[0], 1); + EXPECT_EQ(arr[4], 5); + } +} + +// Test HeapArray can be used as a range (by converting it to span). +TEST_F(HeapArrayTest, Range) { + HeapArrayVal arr{Index{10u}}; + + // Explicit construction. + (void)std::span<Val>(arr); + // Dawn's span requires the index type to match. + (void)ityp::span<Index, Val>(arr); + + // Spans also allow implicit construction from a range. + [[maybe_unused]] std::span<Val> s1 = arr; + [[maybe_unused]] ityp::span<Index, Val> s2 = arr; +} + +// Test HeapArrayFrom handles when the source range is larger than its index type. +// (There are no other HeapArray constructors that need to check this.) +TEST_F(HeapArrayDeathTest, SmallIndex) { + using IndexU8 = TypedInteger<struct IndexU8T, uint8_t>; + { + (void)ityp::HeapArrayFrom<IndexU8>(std::array<int, 254>{}); + + // 255 is invalid because it's reserved as a sentinel value by dawn::SpanBase. + EXPECT_DEATH_IF_SUPPORTED((void)ityp::HeapArrayFrom<IndexU8>(std::array<int, 255>{}), ""); + } +} + +// Checks that various byte types are always aligned to alignof(std::max_align_t). +template <typename HA> +void CheckByteAllocation(const HA& ha) { + EXPECT_EQ(reinterpret_cast<uintptr_t>(ha.data()) % alignof(std::max_align_t), 0u); +} +TEST_F(HeapArrayTest, ByteTypeAlignment) { + CheckByteAllocation(HeapArray<std::byte>(16)); + CheckByteAllocation(HeapArray<char>(16)); + // uint8_t is not technically guaranteed to be max-aligned, but in practice it will be. + // As of this writing, some Dawn code relies on it. + CheckByteAllocation(HeapArray<uint8_t>(16)); +} + +// Check that various non-byte types are always aligned as expected. +template <typename T> +void CheckTypedAllocation(const HeapArray<T>& ha) { + EXPECT_EQ(reinterpret_cast<uintptr_t>(ha.data()) % alignof(T), 0u); +} +TEST_F(HeapArrayTest, NonByteTypeAlignment) { + CheckTypedAllocation(HeapArray<uint32_t>(16)); + struct A { + uint8_t x; + }; + CheckTypedAllocation(HeapArray<A>{16}); + struct B { + std::max_align_t x; + }; + CheckTypedAllocation(HeapArray<B>{16}); + struct alignas(256) C { + int x; + }; + static_assert(alignof(C) == 256); + CheckTypedAllocation(HeapArray<C>{16}); +} + +// Test allocations close to the size of the address space. +TEST_F(HeapArrayTest, OutOfMemoryAtLimit) { + // Allocation of uint8_t values + { + // Test sizes that are blocked by the HeapArray implementation before trying to allocate, + // and one element smaller so that HeapArray will actually try to allocate. + for (size_t leaveSpace : {0, 4094, 4095}) { + HeapArray<uint8_t> arr{std::numeric_limits<size_t>::max() - leaveSpace, std::nothrow}; + // Access the pointer first to prevent the allocation from being optimized away by + // the compiler assuming it will succeed. + EXPECT_EQ(arr.data(), nullptr); + EXPECT_FALSE(bool{arr}); + } + } + // Allocation of uint32_t values + { + static constexpr size_t kMaxSize = std::numeric_limits<size_t>::max() / sizeof(uint32_t); + + // Test sizes that are blocked by the HeapArray implementation before trying to allocate, + // and one element smaller so that HeapArray will actually try to allocate. + for (size_t leaveSpace : {0, 1022, 1023}) { + HeapArray<uint32_t> arr{kMaxSize - leaveSpace, std::nothrow}; + // Access the pointer first to prevent the allocation from being optimized away. + EXPECT_EQ(arr.data(), nullptr); + EXPECT_FALSE(bool{arr}); + } + + // Cases where size * sizeof(val) is larger than the address space and could overflow. + { + HeapArray<uint32_t> arr{kMaxSize + 1, std::nothrow}; + EXPECT_FALSE(bool{arr}); + } + { + HeapArray<uint32_t> arr{kMaxSize + 2, std::nothrow}; + EXPECT_FALSE(bool{arr}); + } + } +} + +// 64-bit size is way too large to allocate (but well within size_t on 64-bit). +TEST_F(HeapArrayTest, OutOfMemory64) { + using Key64 = TypedInteger<struct Key64T, uint64_t>; + static constexpr Key64 kHugeSize{0x1000'0000'0000'0000u}; + + { + ityp::HeapArray<Key64, Val> arr{kHugeSize, std::nothrow}; + // Access the pointer first to prevent the allocation from being optimized away. + EXPECT_EQ(arr.data(), nullptr); + EXPECT_FALSE(bool{arr}); + } + { + auto arr = + // SAFETY: Testing unsafe API. + DAWN_UNSAFE_BUFFERS(ityp::HeapArray<Key64, int>::Uninit(kHugeSize, std::nothrow)); + // Access the pointer first to prevent the allocation from being optimized away. + EXPECT_EQ(arr.data(), nullptr); + EXPECT_FALSE(bool{arr}); + } +} + +// Test allocations close to the size of the address space. +TEST_F(HeapArrayDeathTest, OutOfMemoryAtLimit) { + // We store the allocation's pointer here so the allocation attempt can't be optimized away. + void* volatile ptr; + + // Allocation of uint8_t values + { + // Exact maximum amount that will fit in the address space + EXPECT_DEATH_IF_SUPPORTED( + (ptr = HeapArray<uint8_t>{std::numeric_limits<size_t>::max()}.data()), ""); + // And a bit less. + EXPECT_DEATH_IF_SUPPORTED( + (ptr = HeapArray<uint8_t>{std::numeric_limits<size_t>::max() - 4095}.data()), ""); + } + // Allocation of uint32_t values + { + static constexpr size_t kMaxSize = std::numeric_limits<size_t>::max() / sizeof(uint32_t); + // Maximum amount that will fit in the address space + EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize}.data()), ""); + // And a bit less. + EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize - 1023}.data()), ""); + + // Cases where size * sizeof(val) is larger than the address space and could overflow. + EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize + 1}.data()), ""); + EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize + 2}.data()), ""); + } +} + +// 64-bit size is way too large to allocate (but well within size_t on 64-bit). +TEST_F(HeapArrayDeathTest, OutOfMemory64) { + using Key64 = TypedInteger<struct Key64T, uint64_t>; + static constexpr Key64 kHugeSize{0x1000'0000'0000'0000u}; + + // We store the allocation's pointer here so the allocation attempt can't be optimized away. + void* volatile ptr; + + EXPECT_DEATH_IF_SUPPORTED((ptr = ityp::HeapArray<Key64, Val>{kHugeSize}.data()), ""); + EXPECT_DEATH_IF_SUPPORTED( + // SAFETY: Testing unsafe API. + (ptr = DAWN_UNSAFE_BUFFERS(ityp::HeapArray<Key64, int>::Uninit(kHugeSize)).data()), ""); +} + +// Out of bounds accesses should crash even in release (the underlying container +// should have asserts enabled). +TEST_F(HeapArrayDeathTest, OutOfBounds) { + // MSVC doesn't have asserts (without _MSVC_STL_HARDENING). + if constexpr (DAWN_COMPILER_IS(MSVC)) { + GTEST_SKIP(); + } + + HeapArrayVal arr{Index{10u}}; + EXPECT_DEATH_IF_SUPPORTED(arr[Index{10u}], ""); + + const HeapArrayVal& constArr = arr; + EXPECT_DEATH_IF_SUPPORTED(constArr[Index{10u}], ""); +} + +// If the index/size is 64-bit, it needs to be narrowed to size_t. Verify that's checked correctly. +TEST_F(HeapArrayDeathTest, OversizedIndex) { + // These tests are only relevant on 32-bit builds. + if constexpr (sizeof(size_t) > sizeof(uint32_t)) { + GTEST_SKIP(); + } + + using Key64 = TypedInteger<struct Key64T, uint64_t>; + static constexpr Key64 kHugeKey64{0x1000'0000'0000'0000u}; + + // Crash either due to OOM (on 64-bit) or due to narrowing (on 32-bit). + EXPECT_DEATH_IF_SUPPORTED((ityp::HeapArray<Key64, Val>(kHugeKey64)), ""); + + ityp::HeapArray<Key64, Val> vec(Key64{10u}); + + vec[Key64{9u}]; + // Regular out-of-bounds. + EXPECT_DEATH_IF_SUPPORTED(vec[Key64{10u}], ""); + + vec[Key64{0u}]; + // If this were cast to a 32-bit size_t without a check, it would be in-bounds. + EXPECT_DEATH_IF_SUPPORTED(vec[kHugeKey64], ""); +} + +// Using uninitialized memory should crash on MSan builds. +TEST_F(HeapArrayDeathTest, ReadUninitWithPODType) { + if constexpr (!DAWN_MSAN_ENABLED()) { + GTEST_SKIP(); + } + + // SAFETY: Testing unsafe API. + auto arr = DAWN_UNSAFE_BUFFERS(HeapArrayPOD::Uninit(Index{1u})); + EXPECT_DEATH_IF_SUPPORTED([&]() { printf("%d\n", arr[Index{0u}]); }(), ""); +} + +} // anonymous namespace +} // namespace dawn
diff --git a/src/utils/typed_integer_tests.cc b/src/utils/typed_integer_tests.cc index 2c58caa..afe4536 100644 --- a/src/utils/typed_integer_tests.cc +++ b/src/utils/typed_integer_tests.cc
@@ -26,6 +26,7 @@ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <limits> +#include <type_traits> #include "src/utils/gtest.h" #include "src/utils/typed_integer.h" @@ -50,6 +51,10 @@ static_assert(static_cast<int32_t>(Signed(3)) == 3); static_assert(static_cast<uint32_t>(Unsigned(28u)) == 28); + + // TypedInteger shouldn't be trivially default constructible, because it is + // always initialized (initialization is a "non-trivial" operation). + static_assert(!std::is_trivially_default_constructible_v<Unsigned>); } // Test that typed integers can be explicitly cast to other integral types
diff --git a/src/utils/warning_nocompile.nc b/src/utils/warning_nocompile.nc index 03a45ca..9c9722a 100644 --- a/src/utils/warning_nocompile.nc +++ b/src/utils/warning_nocompile.nc
@@ -33,6 +33,7 @@ #include <array> #include <span> +#include "src/utils/heap_array.h" #include "src/utils/span.h" namespace dawn { @@ -87,4 +88,13 @@ } } +// -Wunsafe-buffer-usage: dawn::HeapArray::Uninit() +void TestUnsafeBuffersDawnHeapArrayConstructors() { + { [[maybe_unused]] auto x = DAWN_UNSAFE_BUFFERS(HeapArray<int>::Uninit(4)); } // Control case. + { [[maybe_unused]] auto x = HeapArray<int>::Uninit(4); } // expected-error {{introduces unsafe buffer manipulation}} + + { [[maybe_unused]] auto x = DAWN_UNSAFE_BUFFERS(HeapArray<int>::Uninit(4, std::nothrow)); } // Control case. + { [[maybe_unused]] auto x = HeapArray<int>::Uninit(4, std::nothrow); } // expected-error {{introduces unsafe buffer manipulation}} +} + }