Pass type-erased SwissTable key data via `EncodedHashKey` instead of `const void*`. Using a byte-array struct copied with `std::memcpy` allows passing small trivially copyable keys by value without UB or MSan errors when the key contains padding or uninitialized bytes. PiperOrigin-RevId: 1016446749
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index f3057d1..69204c0 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -593,7 +593,6 @@ size_t seed; }; -using EncodedHashKey = absl::hash_internal::EncodedHashKey; using HashForKeyFn = absl::hash_internal::HashForKeyFn; // No arguments hash function for a specific key. @@ -603,13 +602,13 @@ template <class Hash, class Key, bool kIsAbsl, size_t kSeedShift, bool kUseCanonical> struct HashKey { - static size_t GetHash(EncodedHashKey data, size_t seed) { - const auto& self = *data.ToPtr<HashKey>(); + static size_t GetHash(const void* data, size_t seed) { + const auto& self = *static_cast<const HashKey*>(data); return HashElement<Hash, kIsAbsl, kSeedShift>{self.hash, seed}(self.key); } // `data()` and `get_hash_fn()` are passed to type erased functions. - EncodedHashKey data() const { return EncodedHashKey::FromPtr(this); } + const void* data() const { return this; } static constexpr HashForKeyFn get_hash_fn() { return &GetHash; } ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index c7978df..82d2025 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -395,7 +395,7 @@ int32_t a = 1; size_t seed = 100; HashKeyCustom hk{hash, a}; - EXPECT_EQ(hk.data().ToPtr<HashKeyCustom>(), &hk); + EXPECT_EQ(hk.data(), &hk); EXPECT_EQ(HashKeyCustom::get_hash_fn()(hk.data(), seed), (HashElement<decltype(hash), /*kIsAbsl=*/false, 0>(hash, seed)(a))); }
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index bd36659..60dc669 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -1149,7 +1149,7 @@ ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportSingleElementTableGrowthToInfozAndForceSample( CommonFields& common, const AllocPolicy& __restrict policy, - EncodedHashKey hasher, HashForKeyFn get_hash) { + const void* hasher, HashForKeyFn get_hash) { HashtablezInfoHandle infoz = ForcedTrySample(policy); common.generate_new_seed(/*has_infoz=*/true); ReportGrowthToInfozImpl(common, infoz, get_hash(hasher, common.seed().seed()), @@ -1170,7 +1170,7 @@ // `common` is first and `get_hash` is third to match argument order in callers. ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportInsertMissToInfozAndComputeHash(CommonFields& common, size_t probe_length, - EncodedHashKey hasher, + const void* hasher, HashForKeyFn get_hash) { common.infoz().RecordInsertMiss(get_hash(hasher, common.seed().seed()), probe_length); @@ -1905,7 +1905,7 @@ void* Grow1To3AndPrepareInsert(CommonFields& common, const PolicyFunctions& __restrict policy, - EncodedHashKey hasher, HashForKeyFn get_hash, + const void* hasher, HashForKeyFn get_hash, bool has_infoz, void* new_slots) { // TODO(b/413062340): Refactor to reuse more code with // GrowSooTableToNextCapacityAndPrepareInsert. @@ -2078,7 +2078,7 @@ void* PrepareInsertSmallNonSoo(CommonFields& common, const PolicyFunctions& __restrict policy, - EncodedHashKey hasher, HashForKeyFn get_hash) { + const void* hasher, HashForKeyFn get_hash) { ABSL_SWISSTABLE_ASSERT(common.is_small()); ABSL_SWISSTABLE_ASSERT(!policy.alloc_policy->soo_enabled); const bool is_empty = common.empty_when_small(); @@ -2239,7 +2239,7 @@ ABSL_ATTRIBUTE_NOINLINE void* GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( CommonFields& common, const AllocPolicy& __restrict policy, - EncodedHashKey hasher, HashForKeyFn get_hash) { + const void* hasher, HashForKeyFn get_hash) { const size_t kNewCapacity = NextCapacity(SooCapacity()); ResizeEmptyNonAllocatedTableImpl(common, policy, kNewCapacity, /*blocked_element_count=*/0, @@ -2341,7 +2341,7 @@ template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> void* GrowSooTableToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - EncodedHashKey hasher, HashForKeyFn get_hash, bool force_sampling) { + const void* hasher, HashForKeyFn get_hash, bool force_sampling) { AssertSoo(common, *policy.alloc_policy); if (ABSL_PREDICT_FALSE(force_sampling)) { // The table is empty, it is only used for forced sampling of SOO tables. @@ -2628,7 +2628,7 @@ void* PrepareInsertLargeGenerationsEnabled( CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash, Group::NonIterableBitMaskType mask_empty, size_t target_group_offset, - EncodedHashKey hasher, HashForKeyFn recompute_hash) { + const void* hasher, HashForKeyFn recompute_hash) { // NOLINTNEXTLINE(misc-static-assert) ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled()); const size_t cap = common.capacity(); @@ -2676,18 +2676,18 @@ // We need to instantiate ALL possible template combinations because we define // the function in the cc file. template void* GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, EncodedHashKey, HashForKeyFn, bool); + CommonFields&, const PolicyFunctions&, const void*, HashForKeyFn, bool); template void* GrowSooTableToNextCapacityAndPrepareInsert< OptimalMemcpySizeForSooSlotTransfer(1), true>(CommonFields&, const PolicyFunctions&, - EncodedHashKey, HashForKeyFn, + const void*, HashForKeyFn, bool); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 3)); template void* GrowSooTableToNextCapacityAndPrepareInsert< OptimalMemcpySizeForSooSlotTransfer(3), true>(CommonFields&, const PolicyFunctions&, - EncodedHashKey, HashForKeyFn, + const void*, HashForKeyFn, bool); #if UINTPTR_MAX == UINT32_MAX @@ -2698,7 +2698,7 @@ template void* GrowSooTableToNextCapacityAndPrepareInsert< OptimalMemcpySizeForSooSlotTransfer(8), true>(CommonFields&, const PolicyFunctions&, - EncodedHashKey, HashForKeyFn, + const void*, HashForKeyFn, bool); static_assert(MaxSooSlotSize() == 8); #endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 2cf149b..8c92b87 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2419,7 +2419,7 @@ template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> void* GrowSooTableToNextCapacityAndPrepareInsert(CommonFields& common, const PolicyFunctions& policy, - EncodedHashKey hasher, + const void* hasher, HashForKeyFn get_hash, bool force_sampling); @@ -2429,7 +2429,7 @@ // (is_small()==false). void* PrepareInsertSmallNonSoo(CommonFields& common, const PolicyFunctions& policy, - EncodedHashKey hasher, HashForKeyFn get_hash); + const void* hasher, HashForKeyFn get_hash); // Resizes table with allocated slots and change the table seed. // Tables with SOO enabled must have capacity > policy.soo_capacity. @@ -2621,7 +2621,7 @@ void* PrepareInsertLargeGenerationsEnabled( CommonFields& common, const PolicyFunctions& policy, size_t hash, Group::NonIterableBitMaskType mask_empty, size_t target_group_offset, - EncodedHashKey hasher, HashForKeyFn recompute_hash); + const void* hasher, HashForKeyFn recompute_hash); template <typename Policy, typename Hash, typename Eq, typename Alloc> struct InstantiateRawHashSet { @@ -4763,14 +4763,14 @@ // Extern template instantiations reduce binary size and linker input size. // Function definition is in raw_hash_set.cc. extern template void* GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, EncodedHashKey, HashForKeyFn, bool); + CommonFields&, const PolicyFunctions&, const void*, HashForKeyFn, bool); extern template void* GrowSooTableToNextCapacityAndPrepareInsert<1, true>( - CommonFields&, const PolicyFunctions&, EncodedHashKey, HashForKeyFn, bool); + CommonFields&, const PolicyFunctions&, const void*, HashForKeyFn, bool); extern template void* GrowSooTableToNextCapacityAndPrepareInsert<4, true>( - CommonFields&, const PolicyFunctions&, EncodedHashKey, HashForKeyFn, bool); + CommonFields&, const PolicyFunctions&, const void*, HashForKeyFn, bool); #if UINTPTR_MAX == UINT64_MAX extern template void* GrowSooTableToNextCapacityAndPrepareInsert<8, true>( - CommonFields&, const PolicyFunctions&, EncodedHashKey, HashForKeyFn, bool); + CommonFields&, const PolicyFunctions&, const void*, HashForKeyFn, bool); #endif extern template void
diff --git a/absl/hash/internal/canonical_hash.h b/absl/hash/internal/canonical_hash.h index fe98837..c7ceb26 100644 --- a/absl/hash/internal/canonical_hash.h +++ b/absl/hash/internal/canonical_hash.h
@@ -17,7 +17,6 @@ #include <cstddef> #include <cstdint> -#include <cstring> #include <type_traits> #include "absl/base/casts.h" @@ -51,56 +50,32 @@ } } -// Type-erased key argument passed by value in a single register on common ABIs. -struct EncodedHashKey { - // Returns true if `key` should be passed by value inside `EncodedHashKey`, - // avoiding spilling it to the stack at the call site. - template <class T> - static constexpr bool ShouldPassByValue() { - return FitsIn64BitsPowerOf2<T>::value && sizeof(T) <= sizeof(bytes) && - alignof(T) <= alignof(EncodedHashKey) && - // Required for `memcpy` (false for types with non-trivial - // `operator=` or destructor, such as `std::pair`). - std::is_trivially_copyable_v<T>; - } +using HashForKeyFn = size_t (*)(const void* hasher, size_t seed); - template <class T> - static EncodedHashKey FromValue(const T& v) { - static_assert(ShouldPassByValue<T>()); - EncodedHashKey res{}; - std::memcpy(res.bytes, &v, sizeof(T)); - return res; - } - - static EncodedHashKey FromPtr(const void* ptr) { return FromValue(ptr); } - - template <class T> - const T& ToValue() const { - static_assert(ShouldPassByValue<T>()); - return *reinterpret_cast<const T*>(bytes); - } - - template <class T> - const T* ToPtr() const { - return absl::bit_cast<const T*>(bytes); - } - - // Byte array (rather than `const void*`) avoids UB and MSan `noundef` errors - // when a small key contains padding or uninitialized bytes. - alignas(void*) unsigned char bytes[sizeof(void*)]; -}; - -using HashForKeyFn = size_t (*)(EncodedHashKey hasher, size_t seed); +// Returns true if `key` is passed by value inside the `const void*` argument of +// `HashForKeyFn`, which avoids spilling it to the stack at the call site. +// Only uniquely represented types qualify: types with padding or otherwise +// uninitialized bits (e.g. a disengaged `std::optional`) would pass those bits +// as a function argument, which MemorySanitizer reports as a use of an +// uninitialized value. +template <class T> +constexpr bool PassKeyByValueInVoidPtr() { + // The `sizeof(uintptr_t)` check is not redundant on 32-bit platforms. + return is_uniquely_represented<T>::value && FitsIn64BitsPowerOf2<T>::value && + sizeof(T) <= sizeof(uintptr_t); +} // Type erased function to apply `Hasher` (the result of `CanonicalHasher<T>()`) // to the key encoded by `CanonicalHashKey::data()`. template <class Hasher> -size_t TypeErasedApplyAbslHashToKeyFn(EncodedHashKey key, size_t seed) { +size_t TypeErasedApplyAbslHashToKeyFn(const void* key, size_t seed) { using T = typename Hasher::KeyType; - if constexpr (EncodedHashKey::ShouldPassByValue<T>()) { - return HashWithSeed().hash(Hasher(), key.ToValue<T>(), seed); + if constexpr (PassKeyByValueInVoidPtr<T>()) { + const auto val = + static_cast<UintOfSizeT<sizeof(T)>>(reinterpret_cast<uintptr_t>(key)); + return HashWithSeed().hash(Hasher(), absl::bit_cast<T>(val), seed); } else { - return HashWithSeed().hash(Hasher(), *key.ToPtr<T>(), seed); + return HashWithSeed().hash(Hasher(), *static_cast<const T*>(key), seed); } } @@ -116,13 +91,16 @@ explicit CanonicalHashKey(const NonConstK& k) : key(k) {} // `data()` and `get_hash_fn()` are passed to type erased functions. - EncodedHashKey data() const { - // Check `CanonicalKey` to match `TypeErasedApplyAbslHashToKeyFn`. - if constexpr (EncodedHashKey::ShouldPassByValue<CanonicalKey>()) { + const void* data() const { + if constexpr (PassKeyByValueInVoidPtr<CanonicalKey>()) { + // Small keys are encoded by value inside the pointer, other keys by + // address. The decision is made on `CanonicalKey` so that it matches the + // decoding in `TypeErasedApplyAbslHashToKeyFn`. static_assert(sizeof(NonConstK) == sizeof(CanonicalKey)); - return EncodedHashKey::FromValue(key); + return reinterpret_cast<const void*>( + uintptr_t{absl::bit_cast<UintOfSizeT<sizeof(CanonicalKey)>>(key)}); } else { - return EncodedHashKey::FromPtr(&key); + return &key; } } static constexpr HashForKeyFn get_hash_fn() {
diff --git a/absl/hash/internal/canonical_hash_test.cc b/absl/hash/internal/canonical_hash_test.cc index c9e2f71..c2bf854 100644 --- a/absl/hash/internal/canonical_hash_test.cc +++ b/absl/hash/internal/canonical_hash_test.cc
@@ -17,10 +17,8 @@ #include <array> #include <cstddef> #include <cstdint> -#include <optional> #include <string> #include <type_traits> -#include <utility> #include "gtest/gtest.h" #include "absl/base/config.h" @@ -96,42 +94,18 @@ // Small keys are encoded by value. int32_t a = 42; CanonicalHashKey<int32_t> hk_int32{a}; - EXPECT_EQ(hk_int32.data().ToValue<int32_t>(), 42); + EXPECT_EQ(reinterpret_cast<uintptr_t>(hk_int32.data()), 42u); // Cheap to copy keys are stored by value. absl::string_view sv = "hello"; CanonicalHashKey<absl::string_view> hk_sv{sv}; - EXPECT_EQ(hk_sv.data().ToPtr<absl::string_view>(), &hk_sv.key); - EXPECT_NE(hk_sv.data().ToPtr<absl::string_view>(), &sv); + EXPECT_EQ(hk_sv.data(), &hk_sv.key); + EXPECT_NE(hk_sv.data(), &sv); // Expensive to copy keys are stored by reference. std::string s = "hello"; CanonicalHashKey<std::string> hk_str{s}; - EXPECT_EQ(hk_str.data().ToPtr<std::string>(), &s); -} - -struct NonDefaultConstructibleSmallKey { - explicit NonDefaultConstructibleSmallKey(int32_t v) : val(v) {} - template <typename H> - friend H AbslHashValue(H h, const NonDefaultConstructibleSmallKey& k) { - return H::combine(std::move(h), k.val); - } - int32_t val; -}; - -TEST(CanonicalHashKeyTest, PaddedAndPartiallyInitializedSmallKeys) { - auto check = [](const auto& key) { - using Key = absl::remove_cvref_t<decltype(key)>; - EXPECT_TRUE(EncodedHashKey::ShouldPassByValue<Key>()); - const size_t seed = 100; - CanonicalHashKey<Key> hk{key}; - EXPECT_EQ(CanonicalHashKey<Key>::get_hash_fn()(hk.data(), seed), - HashWithSeed().hash(absl::Hash<Key>{}, key, seed)); - }; - - // Disengaged std::optional has uninitialized payload and padding bytes. - check(std::optional<int16_t>(std::nullopt)); - check(NonDefaultConstructibleSmallKey{123}); + EXPECT_EQ(hk_str.data(), &s); } } // namespace