diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 9fbd476..749c54f 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel
@@ -70,6 +70,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = [ "//absl:__subpackages__", + "@do_not_use_for_gloop_visibility_only//gloop/util/coding/elias_fano:__subpackages__", "@do_not_use_for_gloop_visibility_only//gloop/util/sysinfo/topology:__subpackages__", ], deps = [
diff --git a/absl/base/attributes.h b/absl/base/attributes.h index fe544c6..e432bb7 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h
@@ -99,10 +99,23 @@ // ABSL_ATTRIBUTE_NOINLINE // // Forces functions to either inline or not inline. Introduced in gcc 3.1. +// +// Note that guarantees are ultimately toolchain-dependent. For example, MSVC +// will not inline any function by default, meaning at least /Ob1 or a higher +// levels of optimization is necessary. #if ABSL_HAVE_ATTRIBUTE(always_inline) || \ (defined(__GNUC__) && !defined(__clang__)) #define ABSL_ATTRIBUTE_ALWAYS_INLINE __attribute__((always_inline)) #define ABSL_HAVE_ATTRIBUTE_ALWAYS_INLINE 1 +#elif defined(_MSC_VER) && \ + (_MSC_VER >= 1937 || \ + (_MSC_VER >= 1927 && ABSL_INTERNAL_CPLUSPLUS_LANG > 201703L)) +#define ABSL_ATTRIBUTE_ALWAYS_INLINE \ + _Pragma("warning(push)") \ + _Pragma("warning(error: 4649)") /* error on misplaced attributes */ \ + [[msvc::forceinline]] /* */ \ + _Pragma("warning(pop)") +#define ABSL_HAVE_ATTRIBUTE_ALWAYS_INLINE 1 #else #define ABSL_ATTRIBUTE_ALWAYS_INLINE #endif @@ -110,6 +123,15 @@ #if ABSL_HAVE_ATTRIBUTE(noinline) || (defined(__GNUC__) && !defined(__clang__)) #define ABSL_ATTRIBUTE_NOINLINE __attribute__((noinline)) #define ABSL_HAVE_ATTRIBUTE_NOINLINE 1 +#elif defined(_MSC_VER) && \ + (_MSC_VER >= 1937 || \ + (_MSC_VER >= 1927 && ABSL_INTERNAL_CPLUSPLUS_LANG > 201703L)) +#define ABSL_ATTRIBUTE_NOINLINE \ + _Pragma("warning(push)") \ + _Pragma("warning(error: 4649)") /* error on misplaced attributes */ \ + [[msvc::noinline]] /* */ \ + _Pragma("warning(pop)") +#define ABSL_HAVE_ATTRIBUTE_NOINLINE 1 #else #define ABSL_ATTRIBUTE_NOINLINE #endif @@ -453,13 +475,27 @@ // Example: // // int foo() ABSL_ATTRIBUTE_HOT; -#if ABSL_HAVE_ATTRIBUTE(hot) || (defined(__GNUC__) && !defined(__clang__)) +#if defined(__cplusplus) && defined(__clang__) && \ + ABSL_HAVE_CPP_ATTRIBUTE(gnu::hot) +#define ABSL_ATTRIBUTE_HOT \ + _Pragma("clang diagnostic push") \ + _Pragma("clang diagnostic error \"-Wignored-attributes\"") \ + [[gnu::hot]] /* */ \ + _Pragma("clang diagnostic pop") +#elif ABSL_HAVE_ATTRIBUTE(hot) || (defined(__GNUC__) && !defined(__clang__)) #define ABSL_ATTRIBUTE_HOT __attribute__((hot)) #else #define ABSL_ATTRIBUTE_HOT #endif -#if ABSL_HAVE_ATTRIBUTE(cold) || (defined(__GNUC__) && !defined(__clang__)) +#if defined(__cplusplus) && defined(__clang__) && \ + ABSL_HAVE_CPP_ATTRIBUTE(gnu::cold) +#define ABSL_ATTRIBUTE_COLD \ + _Pragma("clang diagnostic push") \ + _Pragma("clang diagnostic error \"-Wignored-attributes\"") \ + [[gnu::cold]] /* */ \ + _Pragma("clang diagnostic pop") +#elif ABSL_HAVE_ATTRIBUTE(cold) || (defined(__GNUC__) && !defined(__clang__)) #define ABSL_ATTRIBUTE_COLD __attribute__((cold)) #else #define ABSL_ATTRIBUTE_COLD @@ -681,26 +717,11 @@ // GCC/Clang's `-Wdeprecated-declarations` option. Google's production toolchain // turns this warning off by default, instead relying on clang-tidy to report // new uses of deprecated code. -#if ABSL_HAVE_ATTRIBUTE(deprecated) -#if defined(__cplusplus) && defined(__clang__) && \ - ABSL_HAVE_ATTRIBUTE(diagnose_if) && !defined(SWIG) -struct [[deprecated( - "Use [[deprecated(...)]] instead.")]] _absl_deprecated_macro; -// Trick: We use __attribute__((diagnose_if(...))) to refer to our own -// deprecated symbol, which then causes a deprecation message to be emitted when -// the macro is used. Since diagnose_if() isn't valid on every declaration, we -// also suppress the warning regarding that. -#define ABSL_DEPRECATED(message) \ - _Pragma("clang diagnostic push") /* */ \ - _Pragma("clang diagnostic ignored \"-Wignored-attributes\"") \ - __attribute__((diagnose_if( \ - sizeof(_absl_deprecated_macro*) == 0, "", \ - "warning"))) /* */ \ - _Pragma("clang diagnostic pop") /* */ \ - __attribute__((deprecated(message))) -#else -#define ABSL_DEPRECATED(message) __attribute__((deprecated(message))) +#ifdef ABSL_DEPRECATED +#error "ABSL_DEPRECATED should not be defined." #endif +#if ABSL_HAVE_ATTRIBUTE(deprecated) +#define ABSL_DEPRECATED(message) [[deprecated(message)]] #else #define ABSL_DEPRECATED(message) #endif
diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h index 81210ca..93a9f1c 100644 --- a/absl/base/internal/spinlock.h +++ b/absl/base/internal/spinlock.h
@@ -231,8 +231,8 @@ } uint32_t TryLockInternal(uint32_t lock_value, uint32_t wait_cycles); - void SlowLock() ABSL_ATTRIBUTE_COLD; - void SlowUnlock(uint32_t lock_value) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD void SlowLock(); + ABSL_ATTRIBUTE_COLD void SlowUnlock(uint32_t lock_value); uint32_t SpinLoop(); inline bool TryLockImpl() {
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 8c12057..d325e39 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -458,6 +458,7 @@ ":test_instance_tracker", "//absl/base:config", "//absl/base:no_destructor", + "//absl/functional:overload", "//absl/meta:type_traits", "//absl/strings:string_view", "@googletest//:gtest", @@ -732,6 +733,7 @@ "//absl/base:core_headers", "//absl/base:throw_delegate", "//absl/meta:type_traits", + "//absl/numeric:bits", ], ) @@ -833,6 +835,7 @@ "//absl/memory", "//absl/meta:type_traits", "//absl/numeric:bits", + "//absl/strings:string_view", "//absl/utility", ], )
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index cb0b6de..79bcee0 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -504,6 +504,7 @@ absl::config absl::container_memory absl::no_destructor + absl::overload absl::string_view absl::test_instance_tracker absl::type_traits @@ -745,6 +746,7 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::bits absl::common_policy_traits absl::config absl::container_memory @@ -829,6 +831,7 @@ absl::optional absl::prefetch absl::raw_logging_internal + absl::string_view absl::utility absl::weakly_mixed_integer PUBLIC
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index b03eb95..01fe8d0 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -195,17 +195,18 @@ inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; } template <class F, class S> std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) { - return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)), + return {std::forward_as_tuple(std::forward<F>(f)), std::forward_as_tuple(std::forward<S>(s))}; } template <class F, class S> std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs( const std::pair<F, S>& p) { - return PairArgs(p.first, p.second); + return container_internal::PairArgs(p.first, p.second); } template <class F, class S> std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) { - return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second)); + return container_internal::PairArgs(std::forward<F>(p.first), + std::forward<S>(p.second)); } template <class F, class S> auto PairArgs(std::piecewise_construct_t, F&& f, S&& s) @@ -215,13 +216,61 @@ memory_internal::TupleRef(std::forward<S>(s))); } +// Ensures the argument is a std::pair, and returns std::pair::first as const&. +// Necessary for proper handling of public subclasses of std::pair. +template <class T1, class T2> +const T1& PairConstFirst(const std::pair<T1, T2>* p) { + return p->first; +} + +template <class Ref, class Else> +using IfReference = std::conditional_t<std::is_reference_v<Ref>, Ref, Else>; + // A helper function for implementing apply() in map policies. -template <class F, class... Args> -auto DecomposePair(F&& f, Args&&... args) - -> decltype(memory_internal::DecomposePairImpl( - std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) { - return memory_internal::DecomposePairImpl( - std::forward<F>(f), PairArgs(std::forward<Args>(args)...)); +template <class F, class Pair> +auto DecomposePair(F&& f, Pair&& p) -> decltype(std::forward<F>(f)( + container_internal::PairConstFirst(std::addressof(p)), + static_cast<IfReference<typename std::remove_reference_t<Pair>::first_type, + decltype((std::forward<Pair>(p).first))>>(p.first), + static_cast<IfReference<typename std::remove_reference_t<Pair>::second_type, + decltype((std::forward<Pair>(p).second))>>( + p.second))) { + // The code here is tricky because a naive std::forward<Pair>(p).second would + // incorrectly turn into an lvalue when second_type is an rvalue reference. + return std::forward<F>(f)( + container_internal::PairConstFirst(std::addressof(p)), + static_cast< + IfReference<typename std::remove_reference_t<Pair>::first_type, + decltype((std::forward<Pair>(p).first))>>(p.first), + static_cast< + IfReference<typename std::remove_reference_t<Pair>::second_type, + decltype((std::forward<Pair>(p).second))>>(p.second)); +} + +template <class F, class K, class V> +auto DecomposePair(F&& f, K&& k, V&& v) + -> decltype(std::forward<F>(f)(std::declval<const K&>(), std::forward<K>(k), + std::forward<V>(v))) { + const auto& key = k; + return std::forward<F>(f)(key, std::forward<K>(k), std::forward<V>(v)); +} + +template <class F, class TK, class TV> +auto DecomposePair( + F&& f, + std::enable_if_t<(std::tuple_size_v<remove_cvref_t<TK>> == 1 && + std::tuple_size_v<remove_cvref_t<TV>> >= 0), + std::piecewise_construct_t>, + TK&& tk, TV&& tv) + -> decltype(std::forward<F>(f)( + std::declval<const std::tuple_element_t<0, remove_cvref_t<TK>>&>(), + std::piecewise_construct, + memory_internal::TupleRef(std::forward<TK>(tk)), + memory_internal::TupleRef(std::forward<TV>(tv)))) { + const auto& key = std::get<0>(tk); + return std::forward<F>(f)(key, std::piecewise_construct, + memory_internal::TupleRef(std::forward<TK>(tk)), + memory_internal::TupleRef(std::forward<TV>(tv))); } // A helper function for implementing apply() in set policies.
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index 70fc0ea..f6fdd5c 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -23,7 +23,6 @@ #include <tuple> #include <type_traits> #include <typeindex> -#include <typeinfo> #include <utility> #include "gmock/gmock.h" @@ -31,6 +30,7 @@ #include "absl/base/config.h" #include "absl/base/no_destructor.h" #include "absl/container/internal/test_instance_tracker.h" +#include "absl/functional/overload.h" #include "absl/meta/type_traits.h" #include "absl/strings/string_view.h" @@ -174,7 +174,7 @@ } template <class F, class Arg> -const char* DecomposeValueImpl(char, F&& f, Arg&& arg) { +const char* DecomposeValueImpl(char, F&&, Arg&&) { return "not decomposable"; } @@ -208,7 +208,7 @@ } template <class F, class... Args> -const char* DecomposePairImpl(char, F&& f, Args&&... args) { +const char* DecomposePairImpl(char, F&&, Args&&...) { return "not decomposable"; } @@ -219,14 +219,21 @@ } TEST(DecomposePair, Decomposable) { - auto f = [](const int& x, // NOLINT - std::piecewise_construct_t, std::tuple<int&&> k, - std::tuple<double>&& v) { - EXPECT_EQ(&x, &std::get<0>(k)); + static constexpr auto f0 = [](const int& x, // NOLINT + int&& k, double&& v) { + EXPECT_EQ(&x, &k); EXPECT_EQ(42, x); - EXPECT_EQ(0.5, std::get<0>(v)); + EXPECT_EQ(0.5, v); return 'A'; }; + static constexpr auto f = absl::Overload( + [](const int& x, // NOLINT + std::piecewise_construct_t, std::tuple<int&&> k, + std::tuple<double>&& v) { + return f0(x, std::get<0>(std::move(k)), std::get<0>(std::move(v))); + }, + f0); + EXPECT_EQ('A', TryDecomposePair(f, std::pair<int&&, double&&>(42, 0.5))); EXPECT_EQ('A', TryDecomposePair(f, 42, 0.5)); EXPECT_EQ('A', TryDecomposePair(f, std::make_pair(42, 0.5))); EXPECT_EQ('A', TryDecomposePair(f, std::piecewise_construct,
diff --git a/absl/container/internal/raw_hash_map.h b/absl/container/internal/raw_hash_map.h index 8301b50..e35954a 100644 --- a/absl/container/internal/raw_hash_map.h +++ b/absl/container/internal/raw_hash_map.h
@@ -15,6 +15,8 @@ #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ #define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ +#include <cstddef> +#include <memory> #include <tuple> #include <type_traits> #include <utility> @@ -26,6 +28,7 @@ #include "absl/container/internal/container_memory.h" #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -76,12 +79,18 @@ // // TODO(b/402804213): Remove these traits and simplify the overloads whenever // we have a better mechanism available to handle lifetime analysis. - template <class K, bool Value, typename = void> - using LifetimeBoundK = HasValue< - Value, std::conditional_t<policy_trait_element_is_owner<Policy>::value, - std::false_type, - type_traits_internal::IsLifetimeBoundAssignment< - typename Policy::key_type, K>>>; + // + // MovableOrVoid is an optional, extra constraint (via SFINAE) to guard + // separate move-only overloads. + template <class K, bool Value, typename MovableOrVoid = void> + using LifetimeBoundK = std::bool_constant< + (std::is_void_v<MovableOrVoid> || + !IsAllocMoveSameAsCopy<absl::remove_cvref_t<K>, Alloc>::value) && + HasValue<Value, std::conditional_t< + policy_trait_element_is_owner<Policy>::value, + std::false_type, + type_traits_internal::IsLifetimeBoundAssignment< + typename Policy::key_type, K>>>::value>; template <class V, bool Value, typename = void> using LifetimeBoundV = HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment< @@ -365,9 +374,41 @@ ABSL_ATTRIBUTE_LIFETIME_BOUND { auto res = this->find_or_prepare_insert(k); if (res.second) { - this->emplace_at(res.first, std::piecewise_construct, - std::forward_as_tuple(std::forward<K>(k)), - std::forward_as_tuple(std::forward<Args>(args)...)); + // Try to avoid using std::tuple since that slows compilation. + // (example: https://godbolt.org/z/nefW93T6K) + + // Simple trick to bypass instantiating a bunch of templates in cases + // where they're irrelevant. + using V = std::conditional_t< + sizeof...(Args) == 0 && + std::is_same_v<typename std::allocator_traits< + Alloc>::template rebind_alloc<char>, + std::allocator<char>>, + mapped_type, void>; + + if constexpr (std::is_trivially_move_constructible_v<V> && + std::is_trivially_destructible_v<V> && + // Check if size is a power of 2, to ensure cheap calls. + absl::has_single_bit(sizeof(mapped_type)) && + // Check if copying 1-2 registers is enough. We don't want + // (for example) 32 one-byte values to move around. + alignof(mapped_type) * 2 >= sizeof(mapped_type) && + sizeof(mapped_type) <= sizeof(std::pair<void*, size_t>)) { + // Common case: operator[] + // Note: This has a different run-time performance characteristic than + // the other branches, due to the usage of a temporary object. In the + // event that this causes problems (such as a performance regression or + // a stack overflow), this branch should be modified or removed. + this->emplace_at(res.first, std::forward<K>(k), mapped_type()); + } else if constexpr (sizeof...(Args) == 1) { + this->emplace_at(res.first, std::forward<K>(k), + std::forward<Args>(args)...); + } else { + // This is expensive to compile, so only use it as a last resort. + this->emplace_at(res.first, std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(k)), + std::forward_as_tuple(std::forward<Args>(args)...)); + } } return {this->non_iterable_iterator_at_slot(res.first), res.second}; }
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index a493b9f..15a80cb 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -175,7 +175,6 @@ return mask; } seq.next(); - ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity && "full table!"); } } @@ -277,6 +276,20 @@ } // namespace +#ifndef NDEBUG +ReentranceGuard::ReentranceGuard(CommonFields& common) + : common_(common), capacity_(common.maybe_invalid_capacity()) { + common_.set_capacity(HashtableCapacity::CreateReentrance()); +} + +ReentranceGuard::~ReentranceGuard() { common_.set_capacity(capacity_); } +#endif // NDEBUG + +void CommonFields::AssertInSooModeImpl() const { + ABSL_SWISSTABLE_ASSERT(capacity() == SooCapacity()); + ABSL_SWISSTABLE_ASSERT(!has_infoz()); +} + void CommonFields::AssertNotDebugCapacityImpl() const { const HashtableCapacity cap = maybe_invalid_capacity(); if (ABSL_PREDICT_TRUE(cap.IsValid())) { @@ -807,7 +820,7 @@ template <bool kSooEnabled> void* SingleSlotAddress(CommonFields& c) { - return kSooEnabled ? c.soo_data() : c.slot_array(/*capacity=*/1); + return kSooEnabled ? c.soo_data() : c.single_non_soo_slot(); } template <bool kSooEnabled> @@ -840,7 +853,7 @@ if (c.is_small()) { if (!c.empty()) { static_assert(kMaxSmallCapacity == 1); - policy.destroy_slot(&c, c.slot_array(/*capacity=*/1)); + policy.destroy_slot(&c, c.single_non_soo_slot()); } } else { DestroySlots(c, policy.slot_size, policy.destroy_slot); @@ -980,7 +993,8 @@ size_t FindNewPositionsAndTransferSlots( CommonFields& common, const PolicyFunctions& __restrict policy, ctrl_t* old_ctrl, void* old_slots, size_t old_capacity) { - void* new_slots = common.slot_array(common.capacity()); + void* new_slots = common.is_small() ? common.single_non_soo_slot() + : common.slot_array(common.capacity()); const void* hash_fn = policy.hash_fn(common); const size_t slot_size = policy.slot_size; const size_t seed = common.seed().seed(); @@ -1012,7 +1026,7 @@ return total_probe_length; } -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportGrowthToInfozImpl( +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportGrowthToInfozImpl( CommonFields& common, HashtablezInfoHandle infoz, size_t hash, size_t total_probe_length, size_t distance_from_desired) { infoz.RecordStorageChanged(common.size() - 1, common.capacity()); @@ -1023,7 +1037,7 @@ } // Specialization to avoid passing two 0s from hot function. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportSingleGroupTableGrowthToInfoz(CommonFields& common, ctrl_t* old_ctrl, size_t hash) { ReportGrowthToInfozImpl(common, common.infoz_from_control(old_ctrl), hash, @@ -1032,7 +1046,7 @@ } // Specialization that computes hash and generates new seed. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportSingleElementTableGrowthToInfozAndForceSample( CommonFields& common, const PolicyFunctions& __restrict policy, absl::FunctionRef<size_t(size_t)> get_hash) { @@ -1048,7 +1062,7 @@ // Outlines cold infoz recording so callers do not inline infoz extraction // or spill registers across SetCtrl. `common` is first and `hash` is third to // match argument order in callers. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportInsertMissToInfoz( +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportInsertMissToInfoz( CommonFields& common, size_t probe_length, size_t hash) { common.infoz().RecordInsertMiss(hash, probe_length); } @@ -1056,7 +1070,7 @@ // Outlines cold infoz recording with computation of hash so callers can // avoid calling the hash function and seed extraction in the hot path. // `common` is first and `get_hash` is third to match argument order in callers. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportInsertMissToInfozAndComputeHash( CommonFields& common, size_t probe_length, absl::FunctionRef<size_t(size_t)> get_hash) { @@ -1066,26 +1080,25 @@ // Outlines cold infoz recording with computation of probe_length so callers can // skip tracking of probe_length. `common` is first and `hash` is third to match // argument order in callers. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportInsertMissToInfozAndComputeProbeLength(CommonFields& common, size_t target, size_t hash) { const size_t cap = common.capacity(); auto seq = probe(ProbeCapacity{cap}, hash); while (((target - seq.offset()) & cap) >= Group::kWidth) { seq.next(); - ABSL_SWISSTABLE_ASSERT(seq.index() < common.capacity()); } common.infoz().RecordInsertMiss(hash, seq.index()); } -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportGrowthToInfoz( +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportGrowthToInfoz( CommonFields& common, ctrl_t* old_ctrl, size_t hash, size_t total_probe_length, size_t distance_from_desired) { ReportGrowthToInfozImpl(common, common.infoz_from_control(old_ctrl), hash, total_probe_length, distance_from_desired); } -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportResizeToInfoz( +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportResizeToInfoz( CommonFields& common, HashtablezInfoHandle infoz, size_t total_probe_length) { infoz.RecordStorageChanged(common.size(), common.capacity()); @@ -1094,7 +1107,7 @@ common.set_infoz(infoz); } -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportResizeToInfozAndForceSample(CommonFields& common, const PolicyFunctions& __restrict policy, size_t total_probe_length) { @@ -1407,6 +1420,7 @@ ABSL_ATTRIBUTE_NOINLINE size_t DecodeAndInsertImpl( CommonFields& c, const PolicyFunctions& __restrict policy, const ProbedItem* start, const ProbedItem* end, void* old_slots) { + ABSL_SWISSTABLE_ASSERT(!c.is_small()); const HashtableCapacity new_capacity = c.capacity_impl(); void* new_slots = c.slot_array(new_capacity.capacity()); @@ -1445,9 +1459,10 @@ ABSL_ATTRIBUTE_NOINLINE size_t ProcessProbedMarkedElements( CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* old_ctrl, void* old_slots, size_t start) { - size_t old_capacity = PreviousCapacity(c.capacity()); + const size_t new_capacity = c.capacity(); + const size_t old_capacity = PreviousCapacity(new_capacity); const size_t slot_size = policy.slot_size; - void* new_slots = c.slot_array(c.capacity()); + void* new_slots = c.slot_array(new_capacity); size_t total_probe_length = 0; const void* hash_fn = policy.hash_fn(c); auto hash_slot = policy.hash_slot; @@ -1746,7 +1761,7 @@ ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; constexpr size_t kNewCapacity = NextCapacity(kOldCapacity); - void* old_slots = common.slot_array(kOldCapacity); + void* old_slots = common.single_non_soo_slot(); // old_slots == old_ctrl in case of capacity == 1. ctrl_t* old_ctrl = static_cast<ctrl_t*>(old_slots); @@ -1881,7 +1896,7 @@ if (common.empty()) { IncrementSmallSizeNonSoo(common, policy); // Compute before `RecordInsertMissCold` to avoid reloading `control_`. - void* res = common.slot_array(/*capacity=*/1); + void* res = common.single_non_soo_slot(); // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, @@ -1921,7 +1936,7 @@ // Called whenever the table needs to vacate empty slots either by removing // tombstones via rehash or growth to next capacity. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void* +ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void* RehashOrGrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_hash) { @@ -2134,7 +2149,9 @@ const size_t old_capacity = common.capacity(); ctrl_t* const old_ctrl = common.control(); - void* const old_slots = common.slot_array(old_capacity); + void* const old_slots = IsSmallCapacity(old_capacity) + ? common.single_non_soo_slot() + : common.slot_array(old_capacity); const size_t old_blocked_element_count = common.blocked_element_count(); const size_t slot_size = policy.slot_size; @@ -2262,8 +2279,10 @@ ABSL_SWISSTABLE_ASSERT(common.has_infoz()); return; } + // Reducing from large capacity to SOO. ABSL_SWISSTABLE_ASSERT(slot_size <= sizeof(HeapOrSoo)); ABSL_SWISSTABLE_ASSERT(policy.slot_align <= alignof(HeapOrSoo)); + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); HeapOrSoo tmp_slot; size_t begin_offset = FindFirstFullSlot(0, cap, common.control()); policy.transfer_n( @@ -2319,7 +2338,7 @@ const void* other_slot = other_capacity <= soo_capacity ? other.soo_data() : IsSmallCapacity(other_capacity) - ? other.slot_array(other_capacity) + ? other.single_non_soo_slot() : SlotAddress(other.slot_array(other_capacity), FindFirstFullSlot(0, other_capacity, other.control()), slot_size);
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 7d5802d..7c01b9e 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -181,6 +181,7 @@ #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_ #include <algorithm> +#include <array> #include <cassert> #include <cmath> #include <cstddef> @@ -191,9 +192,12 @@ #include <iterator> #include <limits> #include <memory> +#include <optional> #include <tuple> #include <type_traits> +#include <typeindex> #include <utility> +#include <variant> #include "absl/base/attributes.h" #include "absl/base/casts.h" @@ -222,6 +226,7 @@ #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" #include "absl/numeric/bits.h" +#include "absl/strings/string_view.h" #include "absl/utility/utility.h" #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L @@ -741,9 +746,12 @@ class HashtableInlineData { // The number of bits in the seed. It is big enough to ensure // non-determinism of iteration order. We store the seed inside a uint64_t - // together with size and other metadata. When absl::Hash is inlined, it can - // have lower latency knowing that the high bits of the seed are zero. - static constexpr size_t kSeedBitCount = 5; + // together with size and other metadata. The seed occupies the entire second + // byte of `data_` so that on the critical path of lookups it can be loaded + // with a single byte load and passed to the hash function without any + // masking. When absl::Hash is inlined, it can have lower latency knowing that + // the high bits of the seed are zero. + static constexpr size_t kSeedBitCount = 8; public: static constexpr size_t kGrowthInfoLowerBoundBitCount = 8; @@ -754,23 +762,33 @@ static constexpr size_t kSizeBitCount = 64 - (kBlockedElementBitCount + kSeedBitCount + kGrowthInfoLowerBoundBitCount + - /*has_infoz*/ 1 + kCapacityBitCount); + /*unused*/ 1 + /*has_infoz*/ 1 + kCapacityBitCount); explicit HashtableInlineData(uninitialized_tag_t) {} explicit HashtableInlineData(HashtableCapacity capacity, no_seed_empty_tag_t) - : capacity_internal_(capacity.ToRawData()), data_(0) {} + : data_(CapacityBits(capacity)) {} HashtableInlineData(HashtableCapacity capacity, full_soo_tag_t, bool has_tried_sampling) - : capacity_internal_(capacity.ToRawData()), - data_(kSizeOneNoMetadata | + : data_(CapacityBits(capacity) | kSizeOneNoMetadata | (has_tried_sampling ? kSooHasTriedSamplingMask : 0)) {} HashtableCapacity capacity() const { - return HashtableCapacity::FromRawData(capacity_internal_); + // Reading the capacity via a single byte load (rather than a wide load of + // `data_` followed by masking) allows the compiler to also use a single + // byte load for the seed on the critical path of lookups. The high bits of + // the byte are not part of the capacity. + return HashtableCapacity::FromRawData( + static_cast<uint8_t>(read_byte(kCapacityByteIndex) & kCapacityMask)); } bool is_small() const { return capacity().is_small(); } - void set_capacity(HashtableCapacity c) { capacity_internal_ = c.ToRawData(); } + void set_capacity(HashtableCapacity c) { + data_ = (data_ & ~kCapacityMask) | CapacityBits(c); + } + // Allow for preventing the compiler from optimizing away the store. + void set_capacity(HashtableCapacity c) volatile { + data_ = (data_ & ~kCapacityMask) | CapacityBits(c); + } void set_capacity(size_t c) { set_capacity(HashtableCapacity(c)); } // Returns actual size of the table. @@ -798,7 +816,10 @@ } PerTableSeed seed() const { - return PerTableSeed(ToPublicSeed(data_ & kSeedMask)); + // The seed is stored in exactly one byte, so we read it with a single byte + // load. This lets the compiler feed it directly into the hash function + // without a masking instruction on the critical path of lookups. + return PerTableSeed(read_byte(kSeedByteIndex)); } void generate_new_seed() { set_seed(NextHashTableSeed()); } @@ -807,9 +828,7 @@ // hashes use the same seed and can e.g. identify stuck bits accurately. void set_sampled_seed() { set_seed(kSampledSeed); } - bool is_sampled_seed() const { - return seed().seed() == ToPublicSeed(kSampledSeed); - } + bool is_sampled_seed() const { return seed().seed() == kSampledSeed; } // Returns true if the table has infoz. bool has_infoz() const { @@ -888,24 +907,32 @@ void set_no_seed_for_testing() { data_ &= ~kSeedMask; } private: - // Bit layout of `data_` and `capacity_internal_` from MSB to LSB: - // (41 bits) : size + // Bit layout of `data_` from MSB to LSB: + // (37 bits) : size // (8 bits) : growth_info_lower_bound // (3 bits) : blocked_element_count + // (8 bits) : seed (the whole second byte) + // (1 bit) : unused // (1 bit) : has_infoz - // (5 bits) : seed - // (6 bits) : capacity - // We don't split these components of `data_` into separate bit field elements - // because we get worse generated code that way. + // (6 bits) : capacity (the low 6 bits of the first byte) + // Note: for size to overflow would require ~2^40 bytes of RAM, which is + // impractical. The seed and the capacity are deliberately byte-aligned and + // accessed with byte loads: this lets lookups avoid a wide load plus masking + // on the critical path. We don't split these components of `data_` into + // separate bit field elements because we get worse generated code that way + // (the compiler loads the whole word and extracts the fields). - static constexpr size_t kDataBitCount = 64 - kCapacityBitCount; - static constexpr size_t kSizeShift = kDataBitCount - kSizeBitCount; + static constexpr size_t kSizeShift = 64 - kSizeBitCount; static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift; static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1; - static constexpr uint64_t kSeedMask = (uint64_t{1} << kSeedBitCount) - 1; - // The next bit after the seed. - static constexpr uint64_t kHasInfozMask = kSeedMask + 1; - static constexpr uint64_t kBlockedElementsShift = kSeedBitCount + 1; + static constexpr uint64_t kCapacityMask = (1 << kCapacityBitCount) - 1; + static constexpr size_t kHasInfozShift = kCapacityBitCount; + static constexpr uint64_t kHasInfozMask = uint64_t{1} << kHasInfozShift; + static constexpr size_t kSeedShift = + kHasInfozShift + /*has_infoz*/ 1 + /*unused*/ 1; + static constexpr uint64_t kSeedMask = ((uint64_t{1} << kSeedBitCount) - 1) + << kSeedShift; + static constexpr uint64_t kBlockedElementsShift = kSeedShift + kSeedBitCount; static constexpr uint64_t kBlockedElementMask = kMaxBlockedElementCount << kBlockedElementsShift; static constexpr uint64_t kGrowthInfoLowerBoundShift = @@ -914,27 +941,47 @@ uint64_t{1} << kGrowthInfoLowerBoundShift; static constexpr uint64_t kGrowthInfoLowerBoundMask = uint64_t{0xff} << kGrowthInfoLowerBoundShift; - // For SOO tables, the seed is unused, and bit 0 is repurposed to track - // whether the table has already queried should_sample_soo(). - static constexpr uint64_t kSooHasTriedSamplingMask = 1; + static_assert(kGrowthInfoLowerBoundShift + kGrowthInfoLowerBoundBitCount == + kSizeShift); + // For SOO tables, the seed is unused, and its lowest bit is repurposed to + // track whether the table has already queried should_sample_soo(). + static constexpr uint64_t kSooHasTriedSamplingMask = uint64_t{1} + << kSeedShift; // We need to use a constant seed when the table is sampled so that sampled // hashes use the same seed and can e.g. identify stuck bits accurately. static constexpr uint8_t kSampledSeed = (1 << kSeedBitCount) - 1; - static constexpr uint64_t ToPublicSeed(uint64_t seed) { - // We shift public seed to the left to keep bits of the seed in the original - // place. It allows us to use single instruction to access the seed (e.g., - // `andl $0x7c0, %r8d`). - return seed << kCapacityBitCount; + // Indices of the bytes of `data_` that hold the capacity and the seed. + static_assert(kSeedShift == 8); + static_assert(kSeedBitCount == 8); +#ifdef ABSL_IS_LITTLE_ENDIAN + static constexpr size_t kCapacityByteIndex = 0; + static constexpr size_t kSeedByteIndex = 1; +#else + static constexpr size_t kCapacityByteIndex = 7; + static constexpr size_t kSeedByteIndex = 6; +#endif + + // Returns the `index`-th byte of `data_`. Accessing the storage through + // `unsigned char` is always allowed by the aliasing rules. Note: the reason + // we read the data this way rather than using bit manipulations as with other + // fields is that it results in better generated code (we get movzbl to read + // the seed this way). + uint8_t read_byte(size_t index) const { + return reinterpret_cast<const unsigned char*>(&data_)[index]; + } + + // Returns the bits of `data_` that encode `capacity`. + static uint64_t CapacityBits(HashtableCapacity capacity) { + return uint64_t{capacity.ToRawData()}; } void set_seed(uint8_t seed) { - data_ = (data_ & ~kSeedMask) | (seed & kSeedMask); + data_ = (data_ & ~kSeedMask) | ((uint64_t{seed} << kSeedShift) & kSeedMask); } - uint64_t capacity_internal_ : kCapacityBitCount; - uint64_t data_ : kDataBitCount; + uint64_t data_; }; static_assert(sizeof(HashtableCapacity) == 1); @@ -1101,9 +1148,14 @@ // `Group::kWidth`-width probe window starting from any control byte. constexpr size_t NumClonedBytes() { return Group::kWidth - 1; } +// Returns the number of control bytes including cloned assuming large table. +constexpr size_t NumControlBytesForLargeTable(size_t capacity) { + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(capacity)); + return capacity + 1 + NumClonedBytes(); +} // Returns the number of control bytes including cloned. constexpr size_t NumControlBytes(size_t capacity) { - return IsSmallCapacity(capacity) ? 0 : capacity + 1 + NumClonedBytes(); + return IsSmallCapacity(capacity) ? 0 : NumControlBytesForLargeTable(capacity); } // Returns the size in bytes table with given capacity use to store GrowthInfo. @@ -1224,6 +1276,24 @@ unsigned char soo_data[MaxSooSlotSize()]; }; +class CommonFields; + +// RAII object that guards against reentrant calls to hash table methods in +// debug mode. +class ReentranceGuard { + public: +#ifdef NDEBUG + explicit ReentranceGuard(CommonFields&) {} +#else // NDEBUG + explicit ReentranceGuard(CommonFields& common); + ~ReentranceGuard(); + + private: + CommonFields& common_; + HashtableCapacity capacity_; +#endif // NDEBUG +}; + // CommonFields hold the fields in raw_hash_set that do not depend // on template parameters. This allows us to conveniently pass all // of this state to helper functions as a single argument. @@ -1279,13 +1349,17 @@ // Note: we can't use slots() because Qt defines "slots" as a macro. // Returns pointer to the slots of a table with explicit capacity that must be // equal to the actual capacity of the table. - // Capacity is often known at compile time or already in register with some - // ABSL_ASSUME conditions. We require passing it explicitly to eliminate - // branches inside of NumControlBytes in majority of cases. + // Table must be large. void* slot_array(size_t capacity) const { ABSL_SWISSTABLE_ASSERT(capacity == this->capacity()); + ABSL_ASSUME(capacity > kMaxSmallCapacity); ctrl_t* ctrl = control(); - return ctrl + NumControlBytes(capacity); + return ctrl + NumControlBytesForLargeTable(capacity); + } + // Returns pointer to the single slot of a table with capacity 1. + void* single_non_soo_slot() const { + ABSL_SWISSTABLE_ASSERT(capacity() == 1); + return control(); } // The number of filled slots. @@ -1351,6 +1425,10 @@ return inline_data_.capacity(); } void set_capacity(HashtableCapacity c) { inline_data_.set_capacity(c); } + // Allow for preventing the compiler from optimizing away the store. + void set_capacity(HashtableCapacity c) volatile { + inline_data_.set_capacity(c); + } void set_capacity(size_t c) { set_capacity(HashtableCapacity(c)); } @@ -1465,20 +1543,6 @@ std::count(control(), control() + capacity(), ctrl_t::kDeleted)); } - // Helper to enable sanitizer mode validation to protect against reentrant - // calls during element constructor/destructor. - template <typename F> - void RunWithReentrancyGuard(F f) { - if constexpr (!kIsDebug) { - f(); - } else { - const HashtableCapacity cap = maybe_invalid_capacity(); - set_capacity(HashtableCapacity::CreateReentrance()); - f(); - set_capacity(cap); - } - } - // Asserts that the capacity is not a sentinel invalid value. void AssertNotDebugCapacity() const { if constexpr (SwisstableGenerationsOrDebugEnabled()) { @@ -1517,10 +1581,12 @@ // We can't assert that SOO is enabled because we don't have SooEnabled(), but // we assert what we can. void AssertInSooMode() const { - ABSL_SWISSTABLE_ASSERT(capacity() == SooCapacity()); - ABSL_SWISSTABLE_ASSERT(!has_infoz()); + if constexpr (kIsDebug) { + AssertInSooModeImpl(); + } } + void AssertInSooModeImpl() const; void AssertNotDebugCapacityImpl() const; HashtableInlineData inline_data_; @@ -1783,6 +1849,7 @@ size_t offset(size_t i) const { return (offset_ + i) & capacity_; } void next() { + ABSL_SWISSTABLE_ASSERT(next_index_ <= capacity_ && "full table!"); offset_ += next_index_; offset_ &= capacity_; next_index_ += Width; @@ -2230,6 +2297,63 @@ TypeList<Policy, Hash, Eq, Alloc>>::type; }; +template <class T> +using HasTrivialCopyAndMove = + std::bool_constant<std::is_trivially_copy_constructible_v<T> && + std::is_trivially_move_constructible_v<T>>; + +// In principle, being trivially copy- and move-constructible is sufficient +// (though not necessary) for proving copy and move equivalence. However, we +// can't even test that for all types, because not all types are complete at the +// point of evaluation of this trait. Therefore, we restrict this trait to a +// subset of common types that we know to be complete at the point of evaluation +// of this trait. +template <class T> +inline constexpr bool kIsMoveSameAsCopy = HasTrivialCopyAndMove< + std::conditional_t<(!std::is_class_v<T> && !std::is_union_v<T>) || + std::is_same_v<T, std::type_index> || + std::is_same_v<T, absl::string_view>, + T, void>>::value; + +template <class T, class Traits> +inline constexpr bool kIsMoveSameAsCopy<std::basic_string_view<T, Traits>> = + std::is_trivially_copy_constructible_v<std::basic_string_view<T, Traits>>; + +template <class T, size_t N> +inline constexpr bool kIsMoveSameAsCopy<std::array<T, N>> = + kIsMoveSameAsCopy<T>; + +template <class T> +inline constexpr bool kIsMoveSameAsCopy<std::optional<T>> = + kIsMoveSameAsCopy<T>; + +template <class T1, class T2> +inline constexpr bool kIsMoveSameAsCopy<std::pair<T1, T2>> = + kIsMoveSameAsCopy<T1> && kIsMoveSameAsCopy<T2>; + +template <class... T> +inline constexpr bool kIsMoveSameAsCopy<std::tuple<T...>> = + (true && ... && kIsMoveSameAsCopy<T>); + +template <class... T> +inline constexpr bool kIsMoveSameAsCopy<std::variant<T...>> = + (true && ... && kIsMoveSameAsCopy<T>); + +template <class T, class Alloc = std::allocator<T>> +using IsAllocMoveSameAsCopy = + std::bool_constant<kIsMoveSameAsCopy<std::conditional_t< + std::is_same_v<std::allocator<T>, typename std::allocator_traits< + Alloc>::template rebind_alloc<T>>, + T, void>>>; + +template <class T, class Alloc = std::allocator<T>> +using PreferredParamType = std::conditional_t< + IsAllocMoveSameAsCopy<T, Alloc>::value, + std::conditional_t<std::is_arithmetic_v<T> || std::is_enum_v<T> || + std::is_member_pointer_v<T>, + T, const T&>, + T&&>; + // A SwissTable. // // Policy: a policy defines how to perform different operations on @@ -2304,6 +2428,11 @@ using slot_type = typename PolicyTraits::slot_type; + using IsDefaultPolicy = + std::bool_constant<std::is_same_v<Hash, typename Policy::DefaultHash> && + std::is_same_v<Eq, typename Policy::DefaultEq> && + std::is_same_v<Alloc, typename Policy::DefaultAlloc>>; + constexpr static bool kIsAbslHash = std::is_same_v<hasher, absl::Hash<key_type>> || (!HasAbslContainerHash<key_type>::value && @@ -2316,14 +2445,13 @@ // "absl::hash_internal::TransparentHash" is directly included`. // Maybe we should make "internal/hash.h" be a separate library. is_instance_of<hasher, absl::hash_internal::TransparentHash>::value; - // For non-default hashers it is required to have low bits entropy because - // (a) in such cases, the seed is xor'ed with the hash value rather than being - // used as a seed for the hash function, (b) the seed has low bits that are - // all 0s, and (c) we require random iteration order for small tables. - // In ToPublicSeed we shift the seed by kCapacityBitCount as an optimization - // for default hashers. For non-default hashers, we shift it back. - constexpr static size_t kSeedShift = - kIsAbslHash ? 0 : HashtableInlineData::kCapacityBitCount; + // For non-default hashers the seed is xor'ed with the hash value rather than + // being used as a seed for the hash function. Because we require random + // iteration order for small tables, the seed must have entropy in its low + // bits. The seed is loaded as a single byte from the inline data, so it + // already has low bits entropy and no shift is needed. + // TODO(ezb): get rid of kSeedShift. + constexpr static size_t kSeedShift = 0; constexpr static bool SooEnabled() { return PolicyTraits::soo_enabled() && @@ -2394,8 +2522,13 @@ using Insertable = std::disjunction< std::is_same<absl::remove_cvref_t<reference>, absl::remove_cvref_t<T>>, std::is_convertible<T, init_type>>; + + // Bit-fields cannot be moved, and types with trivial copy and move + // constructors should also not be moved. template <class T> - using IsNotBitField = std::is_pointer<T*>; + using EnableElementMoveFrom = + std::bool_constant<std::is_pointer_v<T*> && + !IsAllocMoveSameAsCopy<T, Alloc>::value>; // RequiresNotInit is a workaround for gcc prior to 7.1. // See https://godbolt.org/g/Y4xsUh. @@ -2800,7 +2933,9 @@ ~raw_hash_set() { destructor_impl(); if constexpr (SwisstableGenerationsOrDebugEnabled()) { - common().set_capacity(HashtableCapacity::CreateDestroyed()); + // Prevent the compiler from optimizing away the store. + const_cast<volatile CommonFields&>(common()).set_capacity( + HashtableCapacity::CreateDestroyed()); } } @@ -2862,7 +2997,7 @@ // m.insert(std::make_pair("abc", 42)); template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> std::pair<iterator, bool> insert(T&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { @@ -2871,7 +3006,7 @@ template <class T, int&..., std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> std::pair<iterator, bool> insert( @@ -2914,7 +3049,7 @@ // // flat_hash_map<std::string, int> s; // s.insert({"abc", 42}); - std::pair<iterator, bool> insert(init_type&& value) + std::pair<iterator, bool> insert(PreferredParamType<init_type, Alloc> value) ABSL_ATTRIBUTE_LIFETIME_BOUND #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L requires(!IsLifetimeBoundAssignmentFrom<init_type>::value) @@ -2923,8 +3058,8 @@ return emplace(std::move(value)); } #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L - std::pair<iterator, bool> insert( - init_type&& value ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY_THIS) + std::pair<iterator, bool> insert(PreferredParamType<init_type, Alloc> value + ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY_THIS) ABSL_ATTRIBUTE_LIFETIME_BOUND requires(IsLifetimeBoundAssignmentFrom<init_type>::value) { @@ -2934,7 +3069,7 @@ template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> iterator insert(const_iterator, T&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { @@ -2942,7 +3077,7 @@ } template <class T, int&..., std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> iterator insert(const_iterator hint, @@ -2958,8 +3093,8 @@ return insert(value).first; } - iterator insert(const_iterator, - init_type&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { + iterator insert(const_iterator, PreferredParamType<init_type, Alloc> value) + ABSL_ATTRIBUTE_LIFETIME_BOUND { return insert(std::move(value)).first; } @@ -3418,47 +3553,43 @@ template <typename... Args> void construct(slot_type* slot, Args&&... args) { - common().RunWithReentrancyGuard([&] { - allocator_type alloc(char_alloc_ref()); - PolicyTraits::construct(&alloc, slot, std::forward<Args>(args)...); - }); + ReentranceGuard guard(common()); + allocator_type alloc(char_alloc_ref()); + PolicyTraits::construct(&alloc, slot, std::forward<Args>(args)...); } void destroy(slot_type* slot) { - common().RunWithReentrancyGuard([&] { - allocator_type alloc(char_alloc_ref()); - PolicyTraits::destroy(&alloc, slot); - }); + ReentranceGuard guard(common()); + allocator_type alloc(char_alloc_ref()); + PolicyTraits::destroy(&alloc, slot); } void transfer(slot_type* to, slot_type* from) { - common().RunWithReentrancyGuard([&] { - allocator_type alloc(char_alloc_ref()); - PolicyTraits::transfer(&alloc, to, from); - }); + ReentranceGuard guard(common()); + allocator_type alloc(char_alloc_ref()); + PolicyTraits::transfer(&alloc, to, from); } // TODO(b/289225379): consider having a helper class that has the impls for // SOO functionality. template <class K = key_type> ABSL_ATTRIBUTE_ALWAYS_INLINE iterator find_small(const key_arg<K>& key) { - ABSL_SWISSTABLE_ASSERT(is_small()); return empty() || !equal_to(key, single_slot()) ? end() : single_iterator(); } template <class K = key_type> iterator find_large(const key_arg<K>& key) { - ABSL_SWISSTABLE_ASSERT(!is_small()); const size_t cap = common().capacity(); ABSL_ASSUME(cap > kMaxSmallCapacity); const size_t hash = hash_of(key); auto seq = probe(ProbeCapacity{cap}, hash); const h2_t h2 = H2(hash); ctrl_t* ctrl = control(); - slot_type* slot_array = to_slot(common().slot_array(cap)); + slot_type* slot_array = this->slot_array(cap); while (true) { + // Loading the group before slot prefetch decreases critical path latency. + Group g{ctrl + seq.offset()}; #ifndef ABSL_HAVE_MEMORY_SANITIZER absl::PrefetchToLocalCache(slot_array + seq.offset()); #endif - Group g{ctrl + seq.offset()}; for (uint32_t i : g.Match(h2)) { const size_t offset = seq.offset(i); if (ABSL_PREDICT_TRUE(equal_to(key, slot_array + offset))) @@ -3466,7 +3597,6 @@ } if (ABSL_PREDICT_TRUE(g.MaskEmpty())) return end(); seq.next(); - ABSL_SWISSTABLE_ASSERT(seq.index() <= cap && "full table!"); } } @@ -3575,7 +3705,7 @@ // Casting directly from e.g. char* to slot_type* can cause compilation errors // on objective-C. This function converts to void* first, avoiding the issue. - static ABSL_ATTRIBUTE_ALWAYS_INLINE slot_type* to_slot(void* buf) { + ABSL_ATTRIBUTE_ALWAYS_INLINE static slot_type* to_slot(void* buf) { return static_cast<slot_type*>(buf); } @@ -3586,12 +3716,10 @@ lhs = std::move(rhs); } else { lhs.move_non_heap_or_soo_fields(rhs); - rhs.RunWithReentrancyGuard([&] { - lhs.RunWithReentrancyGuard([&] { - PolicyTraits::transfer(&rhs_alloc, to_slot(lhs.soo_data()), - to_slot(rhs.soo_data())); - }); - }); + ReentranceGuard lhs_guard(lhs); + ReentranceGuard rhs_guard(rhs); + PolicyTraits::transfer(&rhs_alloc, to_slot(lhs.soo_data()), + to_slot(rhs.soo_data())); } } @@ -3695,7 +3823,6 @@ template <class K> ABSL_ATTRIBUTE_ALWAYS_INLINE std::pair<slot_type*, bool> find_or_prepare_insert_soo(const K& key) { - ABSL_SWISSTABLE_ASSERT(is_soo()); bool force_sampling; slot_type* slot = single_slot(); if (empty()) { @@ -3709,7 +3836,6 @@ } else { force_sampling = false; } - ABSL_SWISSTABLE_ASSERT(capacity() == 1); constexpr bool kUseMemcpy = PolicyTraits::transfer_uses_memcpy() && SooEnabled(); slot = to_slot( @@ -3726,7 +3852,6 @@ template <class K> ABSL_ATTRIBUTE_ALWAYS_INLINE std::pair<slot_type*, bool> find_or_prepare_insert_small(const K& key) { - ABSL_SWISSTABLE_ASSERT(is_small()); if constexpr (SooEnabled()) { return find_or_prepare_insert_soo(key); } @@ -3743,20 +3868,19 @@ template <class K> std::pair<slot_type*, bool> find_or_prepare_insert_large(const K& key) { - ABSL_SWISSTABLE_ASSERT(!is_soo()); prefetch_heap_block(); const size_t cap = capacity(); - ABSL_ASSUME(cap > kMaxSmallCapacity); const size_t hash = hash_of(key); auto seq = probe(ProbeCapacity{cap}, hash); const h2_t h2 = H2(hash); const ctrl_t* ctrl = control(); - slot_type* slot_array = to_slot(common().slot_array(cap)); + slot_type* slot_array = this->slot_array(cap); while (true) { + // Loading the group before slot prefetch decreases critical path latency. + Group g{ctrl + seq.offset()}; #ifndef ABSL_HAVE_MEMORY_SANITIZER absl::PrefetchToLocalCache(slot_array + seq.offset()); #endif - Group g{ctrl + seq.offset()}; for (uint32_t i : g.Match(h2)) { slot_type* slot = slot_array + seq.offset(i); if (ABSL_PREDICT_TRUE(equal_to(key, slot))) { @@ -3778,7 +3902,6 @@ return {to_slot(slot), true}; } seq.next(); - ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!"); } } @@ -3911,7 +4034,6 @@ return common().control(); } slot_type* slot_array(size_t capacity) const { - ABSL_SWISSTABLE_ASSERT(!is_soo()); return static_cast<slot_type*>(common().slot_array(capacity)); } slot_type* soo_slot() { @@ -3925,9 +4047,7 @@ } slot_type* single_slot() { ABSL_SWISSTABLE_ASSERT(is_small()); - return SooEnabled() - ? soo_slot() - : to_slot(common().slot_array(/*capacity=*/1)); + return SooEnabled() ? soo_slot() : to_slot(common().single_non_soo_slot()); } const slot_type* single_slot() const { return const_cast<raw_hash_set*>(this)->single_slot();
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 3b799c3..a4254ed 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -36,11 +36,13 @@ #include <random> #include <set> #include <string> +#include <string_view> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> +#include <variant> #include <vector> #include "gmock/gmock.h" @@ -82,8 +84,8 @@ return std::forward<C>(c).common(); } template <typename C> - static auto GetSlots(const C& c) -> decltype(c.slot_array(c.capacity())) { - return c.slot_array(c.capacity()); + static auto GetSlots(C& c) -> decltype(c.slot_array(c.capacity())) { + return c.is_small() ? c.single_slot() : c.slot_array(c.capacity()); } template <typename C> static size_t CountTombstones(const C& c) { @@ -723,15 +725,16 @@ size_t capacity = 127; probe_seq<16> seq(ProbeCapacity{capacity}, /*hash=*/0); auto gen = [&]() { - size_t res = seq.offset(); seq.next(); - return res; + return seq.offset(); }; std::vector<size_t> offsets(8); - std::generate_n(offsets.begin(), 8, gen); + offsets[0] = seq.offset(); + std::generate_n(offsets.begin() + 1, 7, gen); EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); seq = probe_seq<16>(ProbeCapacity{capacity}, /*hash=*/128); - std::generate_n(offsets.begin(), 8, gen); + offsets[0] = seq.offset(); + std::generate_n(offsets.begin() + 1, 7, gen); EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); } @@ -819,7 +822,9 @@ EXPECT_EQ(data.size(), 5); constexpr size_t kHugeIncrement = - (size_t(1) << (sizeof(size_t) == 4 ? 31 : 39)); + (size_t(1) << (sizeof(size_t) == 4 + ? 31 + : HashtableInlineData::kSizeBitCount - 2)); data.increment_size(kHugeIncrement); EXPECT_EQ(data.size(), kHugeIncrement + 5); @@ -1918,6 +1923,94 @@ Pair("DEF", "!!!"))); } +struct CopyTracker { + static inline int num_copies = 0; + CopyTracker() = default; + CopyTracker(const CopyTracker&) { ++num_copies; } + CopyTracker(CopyTracker&&) = default; + + bool operator==(const CopyTracker&) const { return true; } + + template <typename H> + friend H AbslHashValue(H h, const CopyTracker&) { + return H::combine(std::move(h)); + } +}; + +struct MoveTracker { + static inline int num_destructions = 0; + static inline int num_moves = 0; + ~MoveTracker() { ++num_destructions; } + MoveTracker() = default; + MoveTracker(const MoveTracker&) = default; + MoveTracker(MoveTracker&&) { ++num_moves; } + + bool operator==(const MoveTracker&) const { return true; } + + template <typename H> + friend H AbslHashValue(H h, const MoveTracker&) { + return H::combine(std::move(h)); + } +}; + +TEST(Table, InsertDoesNotAccidentallyCopy) { + CopyTracker::num_copies = 0; + { + ValueTable<CopyTracker> tc; + EXPECT_TRUE(tc.insert(CopyTracker()).second); + tc.insert(tc.end(), CopyTracker()); + } + EXPECT_EQ(CopyTracker::num_copies, 0); + + int num_default_constructs = 0; + MoveTracker::num_moves = 0; + MoveTracker::num_destructions = 0; + { + ValueTable<MoveTracker> tm; + EXPECT_TRUE(tm.insert((++num_default_constructs, MoveTracker())).second); + tm.insert(tm.end(), (++num_default_constructs, MoveTracker())); + } + EXPECT_EQ(MoveTracker::num_destructions - num_default_constructs, + MoveTracker::num_moves); +} + +TEST(Table, InsertWithMovesCollapsedIntoCopy) { + { + ValueTable<std::string_view> t; + EXPECT_TRUE(t.insert(std::string_view("a")).second); + EXPECT_EQ(*t.insert(t.end(), std::string_view("b")), "b"); + } + { + ValueTable<std::array<int, 2>> t; + EXPECT_TRUE(t.insert(std::array<int, 2>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::array<int, 2>{3, 4}), + (std::array<int, 2>{3, 4})); + } + { + ValueTable<std::optional<int>> t; + EXPECT_TRUE(t.insert(std::optional<int>(1)).second); + EXPECT_EQ(*t.insert(t.end(), std::optional<int>(2)), 2); + } + { + ValueTable<std::pair<int, int>> t; + EXPECT_TRUE(t.insert(std::pair<int, int>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::pair<int, int>{3, 4}), + (std::pair<int, int>{3, 4})); + } + { + ValueTable<std::tuple<int, int>> t; + EXPECT_TRUE(t.insert(std::tuple<int, int>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::tuple<int, int>{3, 4}), + (std::tuple<int, int>{3, 4})); + } + { + ValueTable<std::variant<int, double>> t; + EXPECT_TRUE(t.insert(std::variant<int, double>{1}).second); + EXPECT_EQ(*t.insert(t.end(), std::variant<int, double>{2.5}), + (std::variant<int, double>{2.5})); + } +} + TYPED_TEST(SooTest, LargeTable) { TypeParam t; for (int64_t i = 0; i != 10000; ++i) { @@ -5119,7 +5212,9 @@ if (key_size <= 4) { ASSERT_EQ(max_size, uint64_t{1} << 8 * key_size); } else if (i <= 21) { - ASSERT_GE(max_size, uint64_t{1} << 40); + // Small slot sizes are limited only by the number of size bits. + ASSERT_GE(max_size, + (uint64_t{1} << HashtableInlineData::kSizeBitCount) - 1); } ASSERT_LE(max_size, uint64_t{1} << HashtableInlineData::kSizeBitCount); ASSERT_LT(absl::uint128(max_size) * slot_size, uint64_t{1} << 63);
diff --git a/absl/container/linked_hash_map.h b/absl/container/linked_hash_map.h index 6d0e320..d04807b 100644 --- a/absl/container/linked_hash_map.h +++ b/absl/container/linked_hash_map.h
@@ -248,6 +248,7 @@ if (get_allocator() == other.get_allocator()) { *this = std::move(other); } else { + reserve(other.size()); CopyFrom(std::move(other)); } } @@ -267,11 +268,32 @@ linked_hash_map& operator=(linked_hash_map&& other) noexcept { if (this != &other) { - // underlying containers will handle progagate_on_container_move details - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.set_.clear(); - other.list_.clear(); + using AllocTraits = std::allocator_traits<Alloc>; + if constexpr (AllocTraits::propagate_on_container_move_assignment:: + value) { + set_ = std::move(other.set_); + list_ = std::move(other.list_); + other.clear(); + } else if (AllocTraits::is_always_equal::value || + get_allocator() == other.get_allocator()) { + // The allocators are equal, so the list can take over other's nodes. + // std::list's move assignment can not be used here: with an allocator + // that does not propagate on move assignment it element-assigns, which + // is ill-formed for value_type, std::pair<const K, V>. + clear(); + set_ = std::move(other.set_); + list_.splice(list_.end(), other.list_); + other.set_.clear(); + } else if constexpr (!AllocTraits::is_always_equal::value) { + // The list can not take over other's nodes, so move each element into + // a new node allocated with this map's allocator and rebuild the index + // over them, adopting other's hash and equality state. This is the + // same pattern as raw_hash_set::move_assign. + clear(); + set_ = SetType(other.size(), other.set_.hash_function(), + other.set_.key_eq(), get_allocator()); + CopyFrom(std::move(other)); + } } return *this; } @@ -621,6 +643,12 @@ for (auto& elem : other.list_) { set_.insert(list_.insert(list_.end(), std::move(elem))); } + if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { + // When moving from `other`, `std::move(elem)` above mutates the elements + // of `other.list_` in place, invalidating `other.set_`'s index over them. + // Clear `other` so its `set_` and `list_` remain consistent and empty. + other.clear(); + } assert(set_.size() == list_.size()); }
diff --git a/absl/container/linked_hash_map_test.cc b/absl/container/linked_hash_map_test.cc index a905e92..ef03e13 100644 --- a/absl/container/linked_hash_map_test.cc +++ b/absl/container/linked_hash_map_test.cc
@@ -47,6 +47,7 @@ namespace { using ::testing::ElementsAre; +using ::testing::IsEmpty; using ::testing::Pair; using ::testing::Pointee; @@ -821,6 +822,136 @@ << "extract(key) failed to use the same allocator"; } +// Move-assigning with an unequal, non-propagating allocator must move each +// element into a node allocated with the destination's allocator and rebuild +// the index over those nodes. Previously the index kept pointing at the +// source's nodes, which the source then freed, so the first lookup read freed +// memory (heap-use-after-free). +TEST(LinkedHashMap, MoveAssignWithUnequalNonPropagatingAllocator) { + using Alloc = + absl::container_internal::CountingAllocator<std::pair<const int, int>>; + int64_t bytes_used_a = 0; + int64_t bytes_used_b = 0; + Alloc alloc_a(&bytes_used_a); + Alloc alloc_b(&bytes_used_b); + ASSERT_NE(alloc_a, alloc_b); + using Map = linked_hash_map<int, int, linked_hash_map<int, int>::hasher, + std::equal_to<>, Alloc>; + + { + Map a(alloc_a); + a.insert({11, 110}); + a.insert({22, 220}); + a.insert({33, 330}); + const int64_t bytes_used_a_before = bytes_used_a; + EXPECT_GT(bytes_used_a_before, 0); + EXPECT_EQ(bytes_used_b, 0); + + // Move-assign into an empty map. + Map b(alloc_b); + b = std::move(a); + EXPECT_EQ(b.get_allocator(), alloc_b); + EXPECT_LT(bytes_used_a, bytes_used_a_before); + EXPECT_GT(bytes_used_b, 0); + EXPECT_THAT(b, ElementsAre(Pair(11, 110), Pair(22, 220), Pair(33, 330))); + auto found = b.find(22); + ASSERT_NE(found, b.end()); + EXPECT_EQ(found->second, 220); + EXPECT_EQ(b.erase(22), 1); + EXPECT_THAT(b, ElementsAre(Pair(11, 110), Pair(33, 330))); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + + // Move-assign into a non-empty map: the old elements must be gone. + Map c(alloc_b); + c.insert({1, 10}); + c.insert({2, 20}); + a.clear(); + a.insert({44, 440}); + a.insert({55, 550}); + c = std::move(a); + EXPECT_EQ(c.get_allocator(), alloc_b); + EXPECT_THAT(c, ElementsAre(Pair(44, 440), Pair(55, 550))); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + } + EXPECT_EQ(bytes_used_a, 0); + EXPECT_EQ(bytes_used_b, 0); +} + +// Move-assigning with equal allocators must keep taking over the source's +// nodes (and its index) without allocating. +TEST(LinkedHashMap, MoveAssignWithEqualAllocatorTakesOverNodes) { + using Alloc = + absl::container_internal::CountingAllocator<std::pair<const int, int>>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + using Map = linked_hash_map<int, int, linked_hash_map<int, int>::hasher, + std::equal_to<>, Alloc>; + + { + // Note: some STL implementations (e.g. MSVC) allocate a sentinel node + // (and debug proxy) in std::list's default constructor. + Map a(alloc); + const int64_t empty_map_bytes = bytes_used; + a.insert({11, 110}); + a.insert({22, 220}); + Map b(alloc); + const int64_t bytes_used_before = bytes_used; + b = std::move(a); + EXPECT_EQ(bytes_used, bytes_used_before); + EXPECT_THAT(b, ElementsAre(Pair(11, 110), Pair(22, 220))); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + + // Move-assign into a non-empty map: the old elements must be freed and the + // source's nodes taken over without new allocations. + Map c(alloc); + c.insert({1, 10}); + c.insert({2, 20}); + c.insert({3, 30}); + EXPECT_GT(bytes_used, bytes_used_before + empty_map_bytes); + c = std::move(b); + EXPECT_EQ(bytes_used, bytes_used_before + empty_map_bytes); + EXPECT_THAT(c, ElementsAre(Pair(11, 110), Pair(22, 220))); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(b, IsEmpty()); + } + EXPECT_EQ(bytes_used, 0); +} + +// Move-assigning with an allocator that propagates on move assignment must +// propagate the allocator, even when the allocators are unequal. +TEST(LinkedHashMap, MoveAssignWithPropagatingAllocatorPropagates) { + using Alloc = absl::container_internal::MoveAssignPropagatingCountingAlloc< + std::pair<const int, int>>; + int64_t bytes_used_a = 0; + int64_t bytes_used_b = 0; + Alloc alloc_a(&bytes_used_a); + Alloc alloc_b(&bytes_used_b); + ASSERT_NE(alloc_a, alloc_b); + using Map = linked_hash_map<int, int, linked_hash_map<int, int>::hasher, + std::equal_to<>, Alloc>; + + { + Map a(alloc_a); + a.insert({11, 110}); + a.insert({22, 220}); + const int64_t bytes_used_a_before = bytes_used_a; + Map b(alloc_b); + const int64_t empty_map_bytes = bytes_used_b; + b = std::move(a); + EXPECT_EQ(b.get_allocator(), alloc_a); + EXPECT_EQ(bytes_used_a, bytes_used_a_before + empty_map_bytes); + EXPECT_EQ(bytes_used_b, 0); + EXPECT_THAT(b, ElementsAre(Pair(11, 110), Pair(22, 220))); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + } + EXPECT_EQ(bytes_used_a, 0); + EXPECT_EQ(bytes_used_b, 0); +} + TEST(LinkedHashMap, Merge) { linked_hash_map<int, int> m = {{1, 7}, {3, 6}}; linked_hash_map<int, int> src = {{1, 10}, {2, 9}, {4, 16}};
diff --git a/absl/container/linked_hash_set.h b/absl/container/linked_hash_set.h index 7fe0adc..10ba289 100644 --- a/absl/container/linked_hash_set.h +++ b/absl/container/linked_hash_set.h
@@ -237,6 +237,7 @@ if (get_allocator() == other.get_allocator()) { *this = std::move(other); } else { + reserve(other.size()); CopyFrom(std::move(other)); } } @@ -256,10 +257,33 @@ linked_hash_set& operator=(linked_hash_set&& other) noexcept { if (this != &other) { - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.set_.clear(); - other.list_.clear(); + using AllocTraits = std::allocator_traits<Alloc>; + if constexpr (AllocTraits::propagate_on_container_move_assignment:: + value) { + set_ = std::move(other.set_); + list_ = std::move(other.list_); + other.clear(); + } else if (AllocTraits::is_always_equal::value || + get_allocator() == other.get_allocator()) { + // The allocators are equal, so the list can take over other's nodes. + // std::list's move assignment can not be used here: with an allocator + // that does not propagate on move assignment it element-assigns, which + // is ill-formed for value types that are not assignable, such as + // linked_hash_map's std::pair<const K, V>. + clear(); + set_ = std::move(other.set_); + list_.splice(list_.end(), other.list_); + other.set_.clear(); + } else if constexpr (!AllocTraits::is_always_equal::value) { + // The list can not take over other's nodes, so move each element into + // a new node allocated with this set's allocator and rebuild the index + // over them, adopting other's hash and equality state. This is the + // same pattern as raw_hash_set::move_assign. + clear(); + set_ = SetType(other.size(), other.set_.hash_function(), + other.set_.key_eq(), get_allocator()); + CopyFrom(std::move(other)); + } } return *this; } @@ -494,6 +518,12 @@ for (auto& elem : other.list_) { set_.insert(list_.insert(list_.end(), std::move(elem))); } + if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { + // When moving from `other`, `std::move(elem)` above mutates the elements + // of `other.list_` in place, invalidating `other.set_`'s index over them. + // Clear `other` so its `set_` and `list_` remain consistent and empty. + other.clear(); + } assert(set_.size() == list_.size()); }
diff --git a/absl/container/linked_hash_set_test.cc b/absl/container/linked_hash_set_test.cc index 340d6e3..5e4c176 100644 --- a/absl/container/linked_hash_set_test.cc +++ b/absl/container/linked_hash_set_test.cc
@@ -45,6 +45,7 @@ using ::testing::ElementsAre; using ::testing::ElementsAreArray; +using ::testing::IsEmpty; using ::testing::Pointee; template <class T> @@ -851,6 +852,134 @@ << "extract(key) failed to use the same allocator"; } +// Move-assigning with an unequal, non-propagating allocator must move each +// element into a node allocated with the destination's allocator and rebuild +// the index over those nodes. Previously the index kept pointing at the +// source's nodes, which the source then freed, so the first lookup read freed +// memory (heap-use-after-free). +TEST(LinkedHashSet, MoveAssignWithUnequalNonPropagatingAllocator) { + using Alloc = absl::container_internal::CountingAllocator<int>; + int64_t bytes_used_a = 0; + int64_t bytes_used_b = 0; + Alloc alloc_a(&bytes_used_a); + Alloc alloc_b(&bytes_used_b); + ASSERT_NE(alloc_a, alloc_b); + using Set = linked_hash_set<int, linked_hash_set<int>::hasher, + std::equal_to<>, Alloc>; + + { + Set a(alloc_a); + a.insert(11); + a.insert(22); + a.insert(33); + const int64_t bytes_used_a_before = bytes_used_a; + EXPECT_GT(bytes_used_a_before, 0); + EXPECT_EQ(bytes_used_b, 0); + + // Move-assign into an empty set. + Set b(alloc_b); + b = std::move(a); + EXPECT_EQ(b.get_allocator(), alloc_b); + EXPECT_LT(bytes_used_a, bytes_used_a_before); + EXPECT_GT(bytes_used_b, 0); + EXPECT_THAT(b, ElementsAre(11, 22, 33)); + auto found = b.find(22); + ASSERT_NE(found, b.end()); + EXPECT_EQ(*found, 22); + EXPECT_EQ(b.erase(22), 1); + EXPECT_THAT(b, ElementsAre(11, 33)); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + + // Move-assign into a non-empty set: the old elements must be gone. + Set c(alloc_b); + c.insert(1); + c.insert(2); + a.clear(); + a.insert(44); + a.insert(55); + c = std::move(a); + EXPECT_EQ(c.get_allocator(), alloc_b); + EXPECT_THAT(c, ElementsAre(44, 55)); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + } + EXPECT_EQ(bytes_used_a, 0); + EXPECT_EQ(bytes_used_b, 0); +} + +// Move-assigning with equal allocators must keep taking over the source's +// nodes (and its index) without allocating. +TEST(LinkedHashSet, MoveAssignWithEqualAllocatorTakesOverNodes) { + using Alloc = absl::container_internal::CountingAllocator<int>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + using Set = linked_hash_set<int, linked_hash_set<int>::hasher, + std::equal_to<>, Alloc>; + + { + // Note: some STL implementations (e.g. MSVC) allocate a sentinel node + // (and debug proxy) in std::list's default constructor. + Set a(alloc); + const int64_t empty_set_bytes = bytes_used; + a.insert(11); + a.insert(22); + Set b(alloc); + const int64_t bytes_used_before = bytes_used; + b = std::move(a); + EXPECT_EQ(bytes_used, bytes_used_before); + EXPECT_THAT(b, ElementsAre(11, 22)); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + + // Move-assign into a non-empty set: the old elements must be freed and the + // source's nodes taken over without new allocations. + Set c(alloc); + c.insert(1); + c.insert(2); + c.insert(3); + EXPECT_GT(bytes_used, bytes_used_before + empty_set_bytes); + c = std::move(b); + EXPECT_EQ(bytes_used, bytes_used_before + empty_set_bytes); + EXPECT_THAT(c, ElementsAre(11, 22)); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(b, IsEmpty()); + } + EXPECT_EQ(bytes_used, 0); +} + +// Move-assigning with an allocator that propagates on move assignment must +// propagate the allocator, even when the allocators are unequal. +TEST(LinkedHashSet, MoveAssignWithPropagatingAllocatorPropagates) { + using Alloc = + absl::container_internal::MoveAssignPropagatingCountingAlloc<int>; + int64_t bytes_used_a = 0; + int64_t bytes_used_b = 0; + Alloc alloc_a(&bytes_used_a); + Alloc alloc_b(&bytes_used_b); + ASSERT_NE(alloc_a, alloc_b); + using Set = linked_hash_set<int, linked_hash_set<int>::hasher, + std::equal_to<>, Alloc>; + + { + Set a(alloc_a); + a.insert(11); + a.insert(22); + const int64_t bytes_used_a_before = bytes_used_a; + Set b(alloc_b); + const int64_t empty_set_bytes = bytes_used_b; + b = std::move(a); + EXPECT_EQ(b.get_allocator(), alloc_a); + EXPECT_EQ(bytes_used_a, bytes_used_a_before + empty_set_bytes); + EXPECT_EQ(bytes_used_b, 0); + EXPECT_THAT(b, ElementsAre(11, 22)); + // NOLINTNEXTLINE(bugprone-use-after-move) + EXPECT_THAT(a, IsEmpty()); + } + EXPECT_EQ(bytes_used_a, 0); + EXPECT_EQ(bytes_used_b, 0); +} + TEST(LinkedHashSet, Merge) { linked_hash_set<int> m = {1, 7, 3, 6, 10}; linked_hash_set<int> src = {1, 2, 9, 10, 4, 16};
diff --git a/absl/crc/BUILD.bazel b/absl/crc/BUILD.bazel index 10b5a5f..7d634ce 100644 --- a/absl/crc/BUILD.bazel +++ b/absl/crc/BUILD.bazel
@@ -143,6 +143,9 @@ visibility = ["//visibility:private"], deps = [ ":crc32c", + ":crc_internal", + "//absl/base:config", + "//absl/base:core_headers", "//absl/memory", "//absl/random", "//absl/random:distributions",
diff --git a/absl/crc/CMakeLists.txt b/absl/crc/CMakeLists.txt index 4269396..fb9beea 100644 --- a/absl/crc/CMakeLists.txt +++ b/absl/crc/CMakeLists.txt
@@ -112,7 +112,10 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::config + absl::core_headers absl::crc32c + absl::crc_internal absl::memory absl::random_distributions absl::random_random
diff --git a/absl/crc/crc32c.cc b/absl/crc/crc32c.cc index 3c5e59b..9020563 100644 --- a/absl/crc/crc32c.cc +++ b/absl/crc/crc32c.cc
@@ -74,7 +74,7 @@ crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count, crc32c_t initial_crc) { return static_cast<crc32c_t>( - crc_internal::Crc32CAndCopy(dest, src, count, initial_crc)); + crc_internal::Crc32CAndCopy(dest, src, count, initial_crc, false)); } // Remove a Suffix of given size from a buffer
diff --git a/absl/crc/internal/crc.cc b/absl/crc/internal/crc.cc index 8019248..6041c43 100644 --- a/absl/crc/internal/crc.cc +++ b/absl/crc/internal/crc.cc
@@ -46,6 +46,7 @@ #include <cstring> #include <iterator> +#include "absl/base/attributes.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/prefetch.h" @@ -426,7 +427,8 @@ CRC::CRC() {} void CRC::ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const { + const void* __restrict src, size_t length, + bool /*non_temporal*/) const { std::memcpy(dst, src, length); Extend(crc, dst, length); } @@ -437,6 +439,16 @@ return singleton; } +#ifndef NDEBUG +ABSL_ATTRIBUTE_WEAK +#endif +void DebugReportNonTemporalStore() {} + +#ifndef NDEBUG +ABSL_ATTRIBUTE_WEAK +#endif +void DebugReportStoreFence() {} + } // namespace crc_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/crc/internal/crc.h b/absl/crc/internal/crc.h index 49487c6..5f9306c 100644 --- a/absl/crc/internal/crc.h +++ b/absl/crc/internal/crc.h
@@ -18,6 +18,7 @@ #include <cstddef> #include <cstdint> +#include "absl/base/attributes.h" #include "absl/base/config.h" // This class implements CRCs (aka Rabin Fingerprints). @@ -50,7 +51,8 @@ // Copy 'length' bytes from 'src' to 'dst' and extend the CRC with the copied // bytes. virtual void ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const; + const void* __restrict src, size_t length, + bool non_temporal) const; // Equivalent to Extend(crc, bytes, length) where "bytes" // points to an array of "length" zero bytes. @@ -81,6 +83,10 @@ CRC(const CRC&) = delete; CRC& operator=(const CRC&) = delete; }; +// Bookkeeping hooks called by non-temporal store functions and +// NonTemporalStoreFence(), for use in tests. +void DebugReportNonTemporalStore(); +void DebugReportStoreFence(); } // namespace crc_internal ABSL_NAMESPACE_END
diff --git a/absl/crc/internal/crc32_x86_arm_combined_simd.h b/absl/crc/internal/crc32_x86_arm_combined_simd.h index 3acde80..f1bb85b 100644 --- a/absl/crc/internal/crc32_x86_arm_combined_simd.h +++ b/absl/crc/internal/crc32_x86_arm_combined_simd.h
@@ -22,6 +22,7 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/crc/internal/crc.h" #ifdef __SSE4_2__ #include <immintrin.h> @@ -78,18 +79,18 @@ ABSL_NAMESPACE_BEGIN namespace crc_internal { -#if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || \ - defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) - #if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) using V128 = uint64x2_t; -#else +#elif defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) // Note: Do not use __m128i_u, it is not portable. // Use V128_LoadU() perform an unaligned load from __m128i*. using V128 = __m128i; +#else +using V128 = std::array<uint64_t, 2>; #endif -#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) +#if (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ + defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) using V256 = __m256i; #else // Placeholder for V256 when AVX is not available. @@ -158,10 +159,16 @@ // Add packed 64-bit integers in |l| and |r|. V128 V128_Add64(const V128 l, const V128 r); -// Performs a store fence on architectures that require it. -void StoreFence(); +// Performs a store fence on architectures that require it (x86) after +// non-temporal stores. +// +// Debug builds track that this function is called after all tracked +// non-temporal store functions, via the weak hooks +// DebugReportNonTemporalStore() and DebugReportStoreFence() in crc.h. +void NonTemporalStoreFence(); -#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) +#if (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ + defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_LoadU(const void* src); ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_Broadcast128(const V128* src); ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreU(void* dst, V256 data); @@ -193,8 +200,6 @@ ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairNonTemporal( void* dst, const void* src); -#endif - #if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) inline uint32_t CRC32_u8(uint32_t crc, uint8_t v) { @@ -261,9 +266,6 @@ inline V128 V128_Add64(const V128 l, const V128 r) { return _mm_add_epi64(l, r); } - -inline void StoreFence() { _mm_sfence(); } - #elif defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) inline uint32_t CRC32_u8(uint32_t crc, uint8_t v) { return __crc32cb(crc, v); } @@ -370,10 +372,16 @@ } inline V128 V128_Add64(const V128 l, const V128 r) { return vaddq_u64(l, r); } +#endif // ABSL_CRC_INTERNAL_HAVE_X86_SIMD || ABSL_CRC_INTERNAL_HAVE_ARM_SIMD -inline void StoreFence() {} - +inline void NonTemporalStoreFence() { +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) + _mm_sfence(); #endif + // Despite other architectures not needing an actual fence instruction, we + // note the fence in debug builds for consistency with x86. + DebugReportStoreFence(); +} #if (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) @@ -393,9 +401,9 @@ ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreNonTemporal(void* dst, V256 data) { _mm256_stream_si256(reinterpret_cast<__m256i*>(dst), data); + DebugReportNonTemporalStore(); } -#elif defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) || \ - defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) +#else template <typename T> inline T V256_LoadU(const void* src) { T res; @@ -416,12 +424,14 @@ template <typename T> inline void V256_StoreNonTemporal(void* dst, const T& data) { + // This architecture has no streaming store, so the data goes through the + // cache and is already strongly ordered. It is still counted, so that the + // StoreFence() contract is checked identically on every architecture. std::memcpy(dst, &data, sizeof(T)); + DebugReportNonTemporalStore(); } -#endif - -#if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || \ - defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) +#endif // (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && + // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_LoadPairU(const void* src, V256* v0, V256* v1) { @@ -459,9 +469,6 @@ V256_StorePairNonTemporal(dst, v0, v1); } -#endif // defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || - // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) - } // namespace crc_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/crc/internal/crc_memcpy.h b/absl/crc/internal/crc_memcpy.h index 72d7ce4..04eafce 100644 --- a/absl/crc/internal/crc_memcpy.h +++ b/absl/crc/internal/crc_memcpy.h
@@ -52,10 +52,11 @@ public: static crc32c_t CrcAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}) { + crc32c_t initial_crc = crc32c_t{0}, + bool non_temporal = false) { uint32_t crc = static_cast<uint32_t>(initial_crc); crc ^= 0xffffffffU; - CRC::Crc32c()->ExtendAndCopy(&crc, dst, src, length); + CRC::Crc32c()->ExtendAndCopy(&crc, dst, src, length, non_temporal); crc ^= 0xffffffffU; return crc32c_t{crc}; } @@ -113,8 +114,9 @@ // the generic fallback version. inline crc32c_t Crc32CAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}) { - return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc); + crc32c_t initial_crc = crc32c_t{0}, + bool non_temporal = false) { + return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc, non_temporal); } } // namespace crc_internal
diff --git a/absl/crc/internal/crc_memcpy_test.cc b/absl/crc/internal/crc_memcpy_test.cc index 045a1e5..021f5e5 100644 --- a/absl/crc/internal/crc_memcpy_test.cc +++ b/absl/crc/internal/crc_memcpy_test.cc
@@ -14,6 +14,7 @@ #include "absl/crc/internal/crc_memcpy.h" +#include <array> #include <cstddef> #include <cstdint> #include <cstring> @@ -21,15 +22,49 @@ #include <memory> #include <string> #include <utility> +#include <vector> #include "gtest/gtest.h" +#include "absl/base/attributes.h" +#include "absl/base/config.h" #include "absl/crc/crc32c.h" +#include "absl/crc/internal/crc.h" +#include "absl/crc/internal/crc32_x86_arm_combined_simd.h" #include "absl/memory/memory.h" #include "absl/random/distributions.h" #include "absl/random/random.h" #include "absl/strings/str_cat.h" #include "absl/strings/string_view.h" +static int64_t g_num_fences = 0; +static int64_t g_num_unfenced_stores = 0; + +#if !defined(NDEBUG) && ABSL_HAVE_ATTRIBUTE_WEAK +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace crc_internal { +// The following definitions are overrides for weak symbols in crc.h. +void DebugReportNonTemporalStore() { ++g_num_unfenced_stores; } +void DebugReportStoreFence() { + ++g_num_fences; + g_num_unfenced_stores = 0; +} +} // namespace crc_internal +ABSL_NAMESPACE_END +} // namespace absl +#endif // !defined(NDEBUG) && ABSL_HAVE_ATTRIBUTE_WEAK +// Check whether we can test non-temporal stores and store fences, which are +// only used when AVX is supported. These tests also rely on weak symbols, so we +// skip these tests when the weak attribute is not supported. Since these tests +// rely on bookkeeping that is disabled in optimized builds, we also skip them +// in that case. +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ + ABSL_HAVE_ATTRIBUTE_WEAK && !defined(NDEBUG) +constexpr bool kCanTestNonTemporalStores = true; +#else +constexpr bool kCanTestNonTemporalStores = false; +#endif + namespace { enum CrcEngine { @@ -174,4 +209,153 @@ // Non Temporal TestParams{NONTEMPORAL, 0, 0})); +// AVX2 loads and stores need 32-byte alignment. +template <size_t N> +struct alignas(32) SimdTestBuffer : std::array<char, N> {}; + +template <size_t N> +SimdTestBuffer<N> MakeSimdTestBuffer(char first, char last) { + SimdTestBuffer<N> source = {}; + std::fill(source.begin(), source.end(), 0); + source[0] = first; + source[N - 1] = last; + return source; +} + +// Test that bookkeeping for non-temporal stores is correct. +TEST(CrcMemcpyNonTemporalFenceTest, V256_StoreNonTemporal) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + const auto source = MakeSimdTestBuffer<32>( + /*first=*/0x12, /*last=*/0x45); + auto destination = MakeSimdTestBuffer<32>( + /*first=*/0, /*last=*/0); + g_num_fences = 0; + g_num_unfenced_stores = 0; + absl::crc_internal::V256_StoreNonTemporal( + destination.data(), absl::crc_internal::V256_LoadU(source.data())); + EXPECT_EQ(g_num_fences, 0); + EXPECT_EQ(g_num_unfenced_stores, 1); + absl::crc_internal::NonTemporalStoreFence(); + EXPECT_EQ(g_num_fences, 1); + EXPECT_EQ(g_num_unfenced_stores, 0); + EXPECT_EQ(destination, source); +} + +TEST(CrcMemcpyNonTemporalFenceTest, V256_StorePairNonTemporal) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + const auto source = MakeSimdTestBuffer<64>( + /*first=*/0x12, /*last=*/0x45); + auto destination = MakeSimdTestBuffer<64>( + /*first=*/0, /*last=*/0); + g_num_fences = 0; + g_num_unfenced_stores = 0; + absl::crc_internal::V256_StorePairNonTemporal( + destination.data(), absl::crc_internal::V256_LoadU(source.data()), + absl::crc_internal::V256_LoadU(source.data() + 32)); + EXPECT_EQ(g_num_fences, 0); + EXPECT_EQ(g_num_unfenced_stores, 2); + absl::crc_internal::NonTemporalStoreFence(); + EXPECT_EQ(g_num_fences, 1); + EXPECT_EQ(g_num_unfenced_stores, 0); + EXPECT_EQ(destination, source); +} + +TEST(CrcMemcpyNonTemporalFenceTest, V256_CopyPairNonTemporal) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + const auto source = MakeSimdTestBuffer<64>( + /*first=*/0x12, /*last=*/0x45); + auto destination = MakeSimdTestBuffer<64>( + /*first=*/0, /*last=*/0); + g_num_fences = 0; + g_num_unfenced_stores = 0; + absl::crc_internal::V256_CopyPairNonTemporal(destination.data(), + source.data()); + EXPECT_EQ(g_num_fences, 0); + EXPECT_EQ(g_num_unfenced_stores, 2); + absl::crc_internal::NonTemporalStoreFence(); + EXPECT_EQ(g_num_fences, 1); + EXPECT_EQ(g_num_unfenced_stores, 0); + EXPECT_EQ(destination, source); +} + +TEST(CrcMemcpyNonTemporalFenceTest, V256_StoreU) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + const auto source = MakeSimdTestBuffer<32>( + /*first=*/0x12, /*last=*/0x45); + auto destination = MakeSimdTestBuffer<32>( + /*first=*/0, /*last=*/0); + g_num_fences = 0; + g_num_unfenced_stores = 0; + // Regular (temporal) stores should not change the counts. + absl::crc_internal::V256_StoreU( + destination.data(), absl::crc_internal::V256_LoadU(source.data())); + EXPECT_EQ(g_num_fences, 0); + EXPECT_EQ(g_num_unfenced_stores, 0); + EXPECT_EQ(destination, source); +} + +TEST(CrcMemcpyNonTemporalFenceTest, NonTemporalStoreFence) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + g_num_unfenced_stores = 1; + g_num_fences = 0; + absl::crc_internal::NonTemporalStoreFence(); + EXPECT_EQ(g_num_fences, 1); + EXPECT_EQ(g_num_unfenced_stores, 0); +} + +// Non-temporal stores are weakly ordered, so Crc32CAndCopy() has to fence them +// before it returns, or the copy is not guaranteed to be visible to the thread +// that reads it next. This checks that it always does, across the sizes and +// alignments that select between the implementation's code paths. +// +// Only the accelerated implementation issues non-temporal stores, and only for +// copies large enough to reach its PCLMUL path, so a fence is not expected +// after every call; what is checked is that no call ever leaves a non-temporal +// store unfenced. +TEST(CrcMemcpyNonTemporalFenceTest, Crc32CAndCopyMemoryFence) { + if (!kCanTestNonTemporalStores) { + GTEST_SKIP() << "Test does not support this build configuration."; + } + // Enough room for the largest copy below, plus the largest alignment + // offset. + constexpr size_t kMaxCopySize = size_t{1} << 16; + constexpr size_t kMaxAlignment = 64; + const std::vector<char> source(kMaxCopySize + kMaxAlignment, 0x45); + auto destination = std::make_unique<char[]>(kMaxCopySize + kMaxAlignment); + + // Sizes straddling the cutoffs between the memcpy-based path and the PCLMUL + // path, which is the one that stores non-temporally. + constexpr size_t kSizes[] = {0, 1, 63, 64, 255, 256, + 1024, 2047, 2048, 4096, kMaxCopySize}; + // Offsets that leave the destination variously cache-line aligned and + // misaligned, since the implementation peels a differently sized head off + // the copy depending on the alignment. + constexpr size_t kOffsets[] = {0, 1, 8, 63}; + + g_num_unfenced_stores = 0; + for (size_t size : kSizes) { + for (size_t destination_offset : kOffsets) { + for (size_t source_offset : kOffsets) { + absl::crc_internal::Crc32CAndCopy( + destination.get() + destination_offset, + source.data() + source_offset, size, absl::crc32c_t{0}, + /*non_temporal=*/true); + EXPECT_EQ(g_num_unfenced_stores, 0) + << "Crc32CAndCopy() returned with non-temporal stores that were " + "never fenced, so the copy may not be visible to other " + "threads."; + } + } + } +} } // namespace
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index 42c100d..8a2a400 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -225,15 +225,48 @@ NEON_PCLMUL_EOR3, }; +// Selects the kind of stores used to write the destination buffer when the CRC +// is computed while copying. +enum class CopyType { + // Don't copy at all, just compute the CRC of the input. + kNone, + // Copy with regular stores, leaving the destination in the cache. + kTemporal, + // Copy with non-temporal stores, which bypass some levels of cache. + kNonTemporal, +}; + // Base class for CRC32AcceleratedX86ARMCombinedMultipleStreams containing the // methods and data that don't need the template arguments. class CRC32AcceleratedX86ARMCombinedMultipleStreamsBase : public CRC32AcceleratedX86ARMCombined { protected: + // Copies 64 bytes from `src` to `dst`, using the kind of stores selected by + // `copy_type`. Does nothing if `copy_type` is NONE. + template <CopyType copy_type> ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE static void - Copy64Bytes(char* dst, const uint8_t* src) { - PrefetchToLocalCache(reinterpret_cast<const char*>(src) + kPrefetchHorizon); - V256_CopyPairU(dst, src); + Copy64Bytes(uint8_t* dst, const uint8_t* src) { + if constexpr (copy_type == CopyType::kNonTemporal) { + V256_CopyPairNonTemporal(dst, src); + } else if constexpr (copy_type == CopyType::kTemporal) { + V256_CopyPairU(dst, src); + } else { + static_assert(copy_type == CopyType::kNone); + } + } + + // Stores the 64 bytes held in `v0` and `v1` to `dst`, using the kind of + // stores selected by `copy_type`. Does nothing if `copy_type` is NONE. + template <CopyType copy_type> + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE static void + Store64Bytes(uint8_t* dst, V256 v0, V256 v1) { + if constexpr (copy_type == CopyType::kNonTemporal) { + V256_StorePairNonTemporal(dst, v0, v1); + } else if constexpr (copy_type == CopyType::kTemporal) { + V256_StorePairU(dst, v0, v1); + } else { + static_assert(copy_type == CopyType::kNone); + } } // Update partialCRC with crc of 64 byte block. Calling FinalizePclmulStream @@ -318,7 +351,6 @@ return crc; } - template <bool copy_data = false> ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(V256, V256, V128*) const {} @@ -570,29 +602,33 @@ public: void Extend(uint32_t* crc, const void* bytes, const size_t length) const override { - Extend<false>(crc, bytes, length); + Extend<CopyType::kNone>(crc, bytes, length); } void ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const override { - Extend<true>(crc, src, length, dst); - StoreFence(); + const void* __restrict src, size_t length, + bool non_temporal) const override { + if (non_temporal) { + Extend<CopyType::kNonTemporal>(crc, src, length, dst); + } else { + Extend<CopyType::kTemporal>(crc, src, length, dst); + } } - template <bool copy = false> + template <CopyType copy_type> ABSL_ATTRIBUTE_HOT void Extend(uint32_t* crc, const void* bytes, const size_t length, void* __restrict dst = nullptr) const { if constexpr (pclmul_stream_type != PclmulStreamType::NONE) { if (length >= kMediumCutoff) { - ExtendWithPclmul<copy>(crc, bytes, length, dst); + ExtendWithPclmul<copy_type>(crc, bytes, length, dst); return; } } - ExtendWithoutPclmul<copy>(crc, bytes, length, dst); + ExtendWithoutPclmul<copy_type != CopyType::kNone>(crc, bytes, length, dst); } - template <bool copy = false> + template <bool copy> ABSL_ATTRIBUTE_HOT void ExtendWithoutPclmul( uint32_t* crc, const void* bytes, const size_t length, void* __restrict dst = nullptr) const { @@ -701,7 +737,7 @@ *crc = l; } - template <bool copy = false> + template <CopyType copy_type> ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_HOT void ExtendWithPclmul( uint32_t* crc, const void* bytes, const size_t length, void* __restrict dst = nullptr) const { @@ -715,8 +751,10 @@ uint32_t l = *crc; uint64_t l64; - if constexpr (copy) { - // Align destination pointer for V256 non-temporal stores. + if constexpr (copy_type != CopyType::kNone) { + // Align the destination pointer to a cache line. Non-temporal stores + // require the destination to be aligned to the store size, and aligning + // regular stores avoids writes that straddle two cache lines. constexpr size_t kAlignment = 64; uintptr_t dst_addr = reinterpret_cast<uintptr_t>(d); size_t bytes_to_align = @@ -756,7 +794,7 @@ uint8_t* dst_crc_streams[kMaxStreams]; uint8_t* dst_pclmul_streams[kMaxStreams]; - if constexpr (copy) { + if constexpr (copy_type != CopyType::kNone) { uint8_t* dst_stream_start = reinterpret_cast<uint8_t*>(d); for (size_t i = 0; i < num_crc_streams; i++) { dst_crc_streams[i] = dst_stream_start; @@ -778,14 +816,14 @@ V256_LoadPairU(pclmul_streams[j], &pclmul_v0_0[j], &pclmul_v1_0[j]); } - if constexpr (copy) { + if constexpr (copy_type != CopyType::kNone) { for (size_t j = 0; j < num_crc_streams; j++) { - V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j]); + Copy64Bytes<copy_type>(dst_crc_streams[j], crc_streams[j]); dst_crc_streams[j] += 64; } for (size_t j = 0; j < num_pclmul_streams; j++) { - V256_StorePairNonTemporal(dst_pclmul_streams[j], pclmul_v0_0[j], - pclmul_v1_0[j]); + Store64Bytes<copy_type>(dst_pclmul_streams[j], pclmul_v0_0[j], + pclmul_v1_0[j]); dst_pclmul_streams[j] += 64; } } @@ -822,12 +860,13 @@ } for (size_t j = 0; j < num_pclmul_streams; j++) { - if constexpr (copy) { - ProcessPclmulStream<true>(pclmul_streams[j], dst_pclmul_streams[j], - partialCRC[j]); + if constexpr (copy_type != CopyType::kNone) { + ProcessPclmulStream<copy_type>(pclmul_streams[j], + dst_pclmul_streams[j], partialCRC[j]); dst_pclmul_streams[j] += 64; } else { - ProcessPclmulStream<false>(pclmul_streams[j], nullptr, partialCRC[j]); + ProcessPclmulStream<CopyType::kNone>(pclmul_streams[j], nullptr, + partialCRC[j]); } pclmul_streams[j] += 64; } @@ -846,9 +885,9 @@ crc_streams[1] += 16 * 4; crc_streams[2] += 16 * 4; } - if constexpr (copy) { + if constexpr (copy_type != CopyType::kNone) { for (size_t j = 0; j < num_crc_streams; j++) { - V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j] - 64); + Copy64Bytes<copy_type>(dst_crc_streams[j], crc_streams[j] - 64); dst_crc_streams[j] += 64; } } @@ -876,14 +915,14 @@ // Update p and d. if constexpr (num_pclmul_streams > 0) { p = pclmul_streams[num_pclmul_streams - 1]; - if constexpr (copy) { + if constexpr (copy_type != CopyType::kNone) { d = reinterpret_cast<char*>(dst_pclmul_streams[num_pclmul_streams - 1]); size_t remaining_to_copy = static_cast<size_t>(e - p); std::memcpy(d, p, remaining_to_copy); } } else { p = crc_streams[num_crc_streams - 1]; - if constexpr (copy) { + if constexpr (copy_type != CopyType::kNone) { d = reinterpret_cast<char*>(dst_crc_streams[num_crc_streams - 1]); size_t remaining_to_copy = static_cast<size_t>(e - p); std::memcpy(d, p, remaining_to_copy); @@ -913,6 +952,17 @@ } *crc = l; + + if constexpr (copy_type == CopyType::kNonTemporal) { + // According to the Intel 64 Software Developer's Manual + // (https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html), + // non-temporal stores are weakly ordered due to bypassing caches, so + // they have to be fenced before the copy is visible to other threads. + // Regular stores are ordered and need no fence. Note that the fence is + // placed after all stores, to avoid unnecessary serialization and a + // performance hit. + NonTemporalStoreFence(); + } } private: @@ -934,7 +984,7 @@ } } - template <bool copy = false> + template <CopyType copy_type> ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void ProcessPclmulStream(const uint8_t* stream, uint8_t* dst_stream, V128* partialCRC) const { @@ -944,9 +994,7 @@ const uint8_t* src_ptr = stream; V256 v0, v1; V256_LoadPairU(src_ptr, &v0, &v1); - if constexpr (copy) { - V256_StorePairNonTemporal(dst_stream, v0, v1); - } + Store64Bytes<copy_type>(dst_stream, v0, v1); if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { V256 loopMultiplicands = V256_Broadcast128( reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -1020,15 +1068,23 @@ return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 3, 1, PclmulStreamType::PCLMUL>(); #endif + case CpuType::kIntelSapphirerapids: + case CpuType::kIntelEmeraldrapids: + case CpuType::kIntelGraniterapids: +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ + (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ + (!defined(_MSC_VER) || defined(__clang__)) + return new CRC32AcceleratedX86ARMCombinedMultipleStreams< + 3, 3, PclmulStreamType::VPCLMUL>(); +#else + [[fallthrough]]; +#endif // PCLMULQDQ is fast, use combined PCLMULQDQ + CRC implementation. case CpuType::kIntelCascadelakeXeon: case CpuType::kIntelSkylakeXeon: case CpuType::kIntelBroadwell: case CpuType::kIntelSkylake: case CpuType::kIntelIcelake: - case CpuType::kIntelSapphirerapids: - case CpuType::kIntelEmeraldrapids: - case CpuType::kIntelGraniterapids: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 3, 2, PclmulStreamType::PCLMUL>(); // PCLMULQDQ is slow, don't use it.
diff --git a/absl/debugging/stacktrace_test.cc b/absl/debugging/stacktrace_test.cc index 02950bc..3cdd999 100644 --- a/absl/debugging/stacktrace_test.cc +++ b/absl/debugging/stacktrace_test.cc
@@ -339,13 +339,13 @@ ABSL_BLOCK_TAIL_CALL_OPTIMIZATION(); } -ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS ABSL_ATTRIBUTE_NOINLINE void RaiseSignal() { +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS void RaiseSignal() { g_return_address = __builtin_return_address(0); raise(SIGUSR1); ABSL_BLOCK_TAIL_CALL_OPTIMIZATION(); } -ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS ABSL_ATTRIBUTE_NOINLINE void +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS void TestNestedSignal() { constexpr size_t kAltstackSize = 1 << 14; // Allocate altstack on regular stack to make sure it'll have a higher
diff --git a/absl/debugging/symbolize_elf.inc b/absl/debugging/symbolize_elf.inc index 3fdf2ff..07b1167 100644 --- a/absl/debugging/symbolize_elf.inc +++ b/absl/debugging/symbolize_elf.inc
@@ -292,8 +292,8 @@ memcpy(dst, s, len + 1); return dst; } - ObjFile *FindObjFile(const void *const start, - size_t size) ABSL_ATTRIBUTE_NOINLINE; + ABSL_ATTRIBUTE_NOINLINE ObjFile* FindObjFile(const void* const start, + size_t size); static bool RegisterObjFile(const char *filename, const void *const start_addr, const void *const end_addr, uint64_t offset, @@ -547,9 +547,9 @@ // and return true. Otherwise, return false. // To keep stack consumption low, we would like this function to not get // inlined. -static ABSL_ATTRIBUTE_NOINLINE bool GetSectionHeaderByType( - CachingFile *file, ElfW(Half) sh_num, const off_t sh_offset, - ElfW(Word) type, ElfW(Shdr) * out, char *tmp_buf, size_t tmp_buf_size) { +ABSL_ATTRIBUTE_NOINLINE static bool GetSectionHeaderByType( + CachingFile* file, ElfW(Half) sh_num, const off_t sh_offset, + ElfW(Word) type, ElfW(Shdr) * out, char* tmp_buf, size_t tmp_buf_size) { ElfW(Shdr) *buf = reinterpret_cast<ElfW(Shdr) *>(tmp_buf); const size_t buf_entries = tmp_buf_size / sizeof(buf[0]); const size_t buf_bytes = buf_entries * sizeof(buf[0]); @@ -758,10 +758,10 @@ // If the symbol is not found, SYMBOL_NOT_FOUND is returned; // To keep stack consumption low, we would like this function to not get // inlined. -static ABSL_ATTRIBUTE_NOINLINE FindSymbolResult FindSymbol( - const void *const pc, CachingFile *file, char *out, size_t out_size, +ABSL_ATTRIBUTE_NOINLINE static FindSymbolResult FindSymbol( + const void* const pc, CachingFile* file, char* out, size_t out_size, ptrdiff_t relocation, const ElfW(Shdr) * strtab, const ElfW(Shdr) * symtab, - const ElfW(Shdr) * opd, char *tmp_buf, size_t tmp_buf_size) { + const ElfW(Shdr) * opd, char* tmp_buf, size_t tmp_buf_size) { if (symtab == nullptr) { return SYMBOL_NOT_FOUND; } @@ -1092,10 +1092,10 @@ // Read /proc/self/maps and run "callback" for each mmapped file found. If // "callback" returns false, stop scanning and return true. Else continue // scanning /proc/self/maps. Return true if no parse error is found. -static ABSL_ATTRIBUTE_NOINLINE bool ReadAddrMap( - bool (*callback)(const char *filename, const void *const start_addr, - const void *const end_addr, uint64_t offset, void *arg), - void *arg, void *tmp_buf, size_t tmp_buf_size) { +ABSL_ATTRIBUTE_NOINLINE static bool ReadAddrMap( + bool (*callback)(const char* filename, const void* const start_addr, + const void* const end_addr, uint64_t offset, void* arg), + void* arg, void* tmp_buf, size_t tmp_buf_size) { // Use /proc/self/task/<pid>/maps instead of /proc/self/maps. The latter // requires kernel to stop all threads, and is significantly slower when there // are 1000s of threads. @@ -1300,8 +1300,8 @@ // where the input symbol is demangled in-place. // To keep stack consumption low, we would like this function to not // get inlined. -static ABSL_ATTRIBUTE_NOINLINE void DemangleInplace(char *out, size_t out_size, - char *tmp_buf, +ABSL_ATTRIBUTE_NOINLINE static void DemangleInplace(char* out, size_t out_size, + char* tmp_buf, size_t tmp_buf_size) { if (Demangle(out, tmp_buf, tmp_buf_size)) { // Demangling succeeded. Copy to out if the space allows.
diff --git a/absl/debugging/symbolize_test.cc b/absl/debugging/symbolize_test.cc index 05de541..8fcdb84 100644 --- a/absl/debugging/symbolize_test.cc +++ b/absl/debugging/symbolize_test.cc
@@ -166,7 +166,7 @@ defined(ABSL_INTERNAL_HAVE_EMSCRIPTEN_SYMBOLIZE) // Test with a return address. -void ABSL_ATTRIBUTE_NOINLINE TestWithReturnAddress() { +ABSL_ATTRIBUTE_NOINLINE static void TestWithReturnAddress() { #if defined(ABSL_HAVE_ATTRIBUTE_NOINLINE) void *return_address = __builtin_return_address(0); const char *symbol = TrySymbolize(return_address); @@ -575,7 +575,7 @@ return pc; } -void *ABSL_ATTRIBUTE_NOINLINE non_inline_func() { +ABSL_ATTRIBUTE_NOINLINE void* non_inline_func() { void *pc = nullptr; #if defined(__i386__) __asm__ __volatile__("call 1f;\n 1: pop %[PC]" : [PC] "=r"(pc)); @@ -585,7 +585,7 @@ return pc; } -void ABSL_ATTRIBUTE_NOINLINE TestWithPCInsideNonInlineFunction() { +ABSL_ATTRIBUTE_NOINLINE void TestWithPCInsideNonInlineFunction() { #if defined(ABSL_HAVE_ATTRIBUTE_NOINLINE) && \ (defined(__i386__) || defined(__x86_64__)) void *pc = non_inline_func(); @@ -596,7 +596,7 @@ #endif } -void ABSL_ATTRIBUTE_NOINLINE TestWithPCInsideInlineFunction() { +ABSL_ATTRIBUTE_NOINLINE void TestWithPCInsideInlineFunction() { #if defined(ABSL_HAVE_ATTRIBUTE_ALWAYS_INLINE) && \ (defined(__i386__) || defined(__x86_64__)) void *pc = inline_func(); // Must be inlined. @@ -640,7 +640,7 @@ return x * x * x; } -void ABSL_ATTRIBUTE_NOINLINE TestArmThumbOverlap() { +ABSL_ATTRIBUTE_NOINLINE void TestArmThumbOverlap() { #if defined(ABSL_HAVE_ATTRIBUTE_NOINLINE) const char *symbol = TrySymbolize((void *)&ArmThumbOverlapArm); ASSERT_NE(symbol, nullptr) << "TestArmThumbOverlap failed";
diff --git a/absl/functional/function_type_benchmark.cc b/absl/functional/function_type_benchmark.cc index e4ba3a5..cc8b817 100644 --- a/absl/functional/function_type_benchmark.cc +++ b/absl/functional/function_type_benchmark.cc
@@ -40,7 +40,7 @@ }; template <typename Function, typename... Args> -void ABSL_ATTRIBUTE_NOINLINE CallFunction(Function f, Args&&... args) { +ABSL_ATTRIBUTE_NOINLINE void CallFunction(Function f, Args&&... args) { f(std::forward<Args>(args)...); }
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index 43cb561..df75c25 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc
@@ -235,21 +235,28 @@ // We combine state and data with _mm_add_epi64/_mm_sub_epi64 before applying // AES encryption to make hash function dependent on the order of the blocks. // See comments in LowLevelHash33To64 for more considerations. - auto mix_ab = [&state0, - &state1](const uint8_t* p) ABSL_ATTRIBUTE_ALWAYS_INLINE { - Vector128 a = Load128(p); - Vector128 b = Load128(p + 16); - state0 = MixA(a, state0); - state1 = MixB(b, state1); + struct MixerAB { + Vector128& state0; + Vector128& state1; + ABSL_ATTRIBUTE_ALWAYS_INLINE auto operator()(const uint8_t* p) const { + Vector128 a = Load128(p); + Vector128 b = Load128(p + 16); + state0 = MixA(a, state0); + state1 = MixB(b, state1); + } }; - auto mix_cd = [&state2, - &state3](const uint8_t* p) ABSL_ATTRIBUTE_ALWAYS_INLINE { - Vector128 c = Load128(p); - Vector128 d = Load128(p + 16); - state2 = MixC(c, state2); - state3 = MixD(d, state3); + MixerAB mix_ab = {state0, state1}; + struct MixerCD { + Vector128& state2; + Vector128& state3; + ABSL_ATTRIBUTE_ALWAYS_INLINE auto operator()(const uint8_t* p) const { + Vector128 c = Load128(p); + Vector128 d = Load128(p + 16); + state2 = MixC(c, state2); + state3 = MixD(d, state3); + } }; - + MixerCD mix_cd = {state2, state3}; do { PrefetchFutureDataToLocalCache(ptr); mix_ab(ptr);
diff --git a/absl/log/internal/check_op.h b/absl/log/internal/check_op.h index ce2c76f..69f0c3b 100644 --- a/absl/log/internal/check_op.h +++ b/absl/log/internal/check_op.h
@@ -425,8 +425,8 @@ // Build the error message string. Specify no inlining for code size. template <typename T1, typename T2> -ABSL_ATTRIBUTE_RETURNS_NONNULL const char* absl_nonnull MakeCheckOpString( - T1 v1, T2 v2, const char* absl_nonnull exprtext) ABSL_ATTRIBUTE_NOINLINE; +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_RETURNS_NONNULL const char* absl_nonnull +MakeCheckOpString(T1 v1, T2 v2, const char* absl_nonnull exprtext); template <typename T1, typename T2> const char* absl_nonnull MakeCheckOpString(T1 v1, T2 v2,
diff --git a/absl/log/internal/log_message.cc b/absl/log/internal/log_message.cc index 4e5da95..e56ef25 100644 --- a/absl/log/internal/log_message.cc +++ b/absl/log/internal/log_message.cc
@@ -605,7 +605,8 @@ // `str_type`. Truncates `str` if necessary, but emits nothing and marks the // buffer full if even the field headers do not fit. template <LogMessage::StringType str_type> -void LogMessage::CopyToEncodedBuffer(absl::string_view str) { +ABSL_ATTRIBUTE_NOINLINE void LogMessage::CopyToEncodedBuffer( + absl::string_view str) { auto encoded_remaining_copy = data_->encoded_remaining(); constexpr uint8_t tag_value = str_type == StringType::kLiteral ? ValueTag::kStringLiteral @@ -632,7 +633,8 @@ template void LogMessage::CopyToEncodedBuffer< LogMessage::StringType::kNotLiteral>(absl::string_view str); template <LogMessage::StringType str_type> -void LogMessage::CopyToEncodedBuffer(char ch, size_t num) { +ABSL_ATTRIBUTE_NOINLINE void LogMessage::CopyToEncodedBuffer(char ch, + size_t num) { auto encoded_remaining_copy = data_->encoded_remaining(); constexpr uint8_t tag_value = str_type == StringType::kLiteral ? ValueTag::kStringLiteral @@ -660,7 +662,8 @@ LogMessage::StringType::kNotLiteral>(char ch, size_t num); template <LogMessage::StringType str_type> -void LogMessage::CopyToEncodedBuffer(std::wstring_view str) { +ABSL_ATTRIBUTE_NOINLINE void LogMessage::CopyToEncodedBuffer( + std::wstring_view str) { auto encoded_remaining_copy = data_->encoded_remaining(); constexpr uint8_t tag_value = str_type == StringType::kLiteral ? ValueTag::kStringLiteral @@ -698,7 +701,8 @@ absl::string_view str); template <LogMessage::StringType str_type> -void LogMessage::CopyToEncodedBufferWithStructuredProtoField( +ABSL_ATTRIBUTE_NOINLINE void +LogMessage::CopyToEncodedBufferWithStructuredProtoField( StructuredProtoField field, absl::string_view str) { auto encoded_remaining_copy = data_->encoded_remaining(); size_t encoded_field_size = BufferSizeForStructuredProtoField(field);
diff --git a/absl/log/internal/log_message.h b/absl/log/internal/log_message.h index b9b533e..cd12833 100644 --- a/absl/log/internal/log_message.h +++ b/absl/log/internal/log_message.h
@@ -68,22 +68,22 @@ // Used for `LOG`. Taking `const char *` instead of `string_view` keeps // callsites a little bit smaller at the cost of doing `strlen` at runtime. - LogMessage(const char* absl_nonnull file, int line, - absl::LogSeverity severity) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessage(const char* absl_nonnull file, int line, + absl::LogSeverity severity); // Used for FFI integrations that don't have a NUL-terminated string. - LogMessage(absl::string_view file, int line, - absl::LogSeverity severity) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessage(absl::string_view file, int line, + absl::LogSeverity severity); // These constructors are slightly smaller/faster to call; the severity is // curried into the function pointer. - LogMessage(const char* absl_nonnull file, int line, - InfoTag) ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE; - LogMessage(const char* absl_nonnull file, int line, - WarningTag) ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE; - LogMessage(const char* absl_nonnull file, int line, - ErrorTag) ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE; + ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE + LogMessage(const char* absl_nonnull file, int line, InfoTag); + ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE + LogMessage(const char* absl_nonnull file, int line, WarningTag); + ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE + LogMessage(const char* absl_nonnull file, int line, ErrorTag); LogMessage(const LogMessage&) = delete; LogMessage& operator=(const LogMessage&) = delete; - ~LogMessage() ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD ~LogMessage(); // Overrides the location inferred from the callsite. The string pointed to // by `file` must be valid until the end of the statement. @@ -209,14 +209,14 @@ // This prevents non-const `char[]` arrays from looking like literals. template <int SIZE> - LogMessage& operator<<(char (&buf)[SIZE]) ABSL_ATTRIBUTE_NOINLINE; + ABSL_ATTRIBUTE_NOINLINE LogMessage& operator<<(char (&buf)[SIZE]); // `wchar_t[SIZE]` is handled by `operator<< <const wchar_t*>`. // Types that support `AbslStringify()` are serialized that way. // Types that don't support `AbslStringify()` but do support streaming into a // `std::ostream&` are serialized that way. template <typename T> - LogMessage& operator<<(const T& v) ABSL_ATTRIBUTE_NOINLINE; + ABSL_ATTRIBUTE_NOINLINE LogMessage& operator<<(const T& v); // Dispatches the completed `absl::LogEntry` to applicable `absl::LogSink`s. void Flush(); @@ -271,18 +271,17 @@ kNotLiteral, }; template <StringType str_type> - void CopyToEncodedBuffer(absl::string_view str) ABSL_ATTRIBUTE_NOINLINE; + void CopyToEncodedBuffer(absl::string_view str); template <StringType str_type> - void CopyToEncodedBuffer(char ch, size_t num) ABSL_ATTRIBUTE_NOINLINE; + void CopyToEncodedBuffer(char ch, size_t num); template <StringType str_type> - void CopyToEncodedBuffer(std::wstring_view str) ABSL_ATTRIBUTE_NOINLINE; + void CopyToEncodedBuffer(std::wstring_view str); // Copies `field` to the encoded buffer, then appends `str` after it // (truncating `str` if necessary to fit). template <StringType str_type> void CopyToEncodedBufferWithStructuredProtoField(StructuredProtoField field, - absl::string_view str) - ABSL_ATTRIBUTE_NOINLINE; + absl::string_view str); // Returns `true` if the message is fatal or enabled debug-fatal. bool IsFatal() const; @@ -422,9 +421,9 @@ // message. class LogMessageFatal final : public LogMessage { public: - LogMessageFatal(const char* absl_nonnull file, int line) ABSL_ATTRIBUTE_COLD; - LogMessageFatal(const char* absl_nonnull file, int line, - const char* absl_nonnull failure_msg) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessageFatal(const char* absl_nonnull file, int line); + ABSL_ATTRIBUTE_COLD LogMessageFatal(const char* absl_nonnull file, int line, + const char* absl_nonnull failure_msg); [[noreturn]] ~LogMessageFatal(); }; @@ -433,8 +432,8 @@ // for DLOG(FATAL) variants. class LogMessageDebugFatal final : public LogMessage { public: - LogMessageDebugFatal(const char* absl_nonnull file, - int line) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessageDebugFatal(const char* absl_nonnull file, + int line); ~LogMessageDebugFatal(); }; @@ -443,19 +442,19 @@ // DLOG(QFATAL) calls this instead of LogMessageQuietlyFatal to make sure the // destructor is not [[noreturn]] even if this is always FATAL as this is only // invoked when DLOG() is enabled. - LogMessageQuietlyDebugFatal(const char* absl_nonnull file, - int line) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessageQuietlyDebugFatal(const char* absl_nonnull file, + int line); ~LogMessageQuietlyDebugFatal(); }; // Used for LOG(QFATAL) to make sure it's properly understood as [[noreturn]]. class LogMessageQuietlyFatal final : public LogMessage { public: - LogMessageQuietlyFatal(const char* absl_nonnull file, - int line) ABSL_ATTRIBUTE_COLD; - LogMessageQuietlyFatal(const char* absl_nonnull file, int line, - const char* absl_nonnull failure_msg) - ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD LogMessageQuietlyFatal(const char* absl_nonnull file, + int line); + ABSL_ATTRIBUTE_COLD LogMessageQuietlyFatal( + const char* absl_nonnull file, int line, + const char* absl_nonnull failure_msg); [[noreturn]] ~LogMessageQuietlyFatal(); };
diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc index a58b772..54e2a8c 100644 --- a/absl/numeric/int128.cc +++ b/absl/numeric/int128.cc
@@ -42,7 +42,7 @@ // For example: // Given: 5 (decimal) == 101 (binary) // Returns: 2 -inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { ABSL_ASSUME(hi != 0); return 127 - countl_zero(hi);
diff --git a/absl/status/status_macros.h b/absl/status/status_macros.h index b823e0d..965ea8e 100644 --- a/absl/status/status_macros.h +++ b/absl/status/status_macros.h
@@ -22,6 +22,7 @@ #define ABSL_STATUS_STATUS_MACROS_H_ #include <cstddef> +#include <string> #include <type_traits> #include <utility> @@ -174,13 +175,9 @@ ABSL_INTERNAL_STATUS_MACROS_IMPL_ASSIGN_OR_RETURN_2_)) \ (return_keyword, __VA_ARGS__) -constexpr bool HasPotentialConditionalOperator(const char* lhs, int size) { - for (int i = 0; i < size; ++i) { - if (lhs[i] == '?') { - return true; - } - } - return false; +constexpr bool HasPotentialConditionalOperator(const char* lhs, size_t size) { + return lhs[0] == '(' && lhs[size - 1] == ')' && + std::char_traits<char>::find(lhs, size, '?') != nullptr; } template <std::size_t N> @@ -241,26 +238,24 @@ (void)_; /* error_expression is allowed to not use this variable */ \ return_keyword(error_expression)) -#define ABSL_INTERNAL_STATUS_MACROS_IMPL_ASSIGN_OR_RETURN_( \ - statusor, lhs, rexpr, error_expression) \ - auto statusor = (rexpr); \ - if (ABSL_PREDICT_FALSE(!statusor.ok())) { \ - error_expression; \ - } \ - { \ - static_assert( \ - !IsEnclosedByParentheses(#lhs) || \ - !HasPotentialConditionalOperator(#lhs, sizeof(#lhs) - 2), \ - "Identified potential conditional operator, consider not " \ - "using ABSL_ASSIGN_OR_RETURN"); \ - } \ - { \ - static_assert( \ - absl::status_macro_internal::IsAllowedStatusOrMacroType< \ - std::remove_const_t<decltype(statusor)>>(), \ - "ABSL_ASSIGN_OR_RETURN should only be used with absl::StatusOr<>"); \ - } \ - ABSL_INTERNAL_STATUS_MACROS_IMPL_UNPARENTHESIZE_IF_PARENTHESIZED(lhs) = \ +#define ABSL_INTERNAL_STATUS_MACROS_IMPL_ASSIGN_OR_RETURN_( \ + statusor, lhs, rexpr, error_expression) \ + auto statusor = (rexpr); \ + if (ABSL_PREDICT_FALSE(!statusor.ok())) { \ + error_expression; \ + } \ + { \ + static_assert(!HasPotentialConditionalOperator(#lhs, sizeof(#lhs) - 1), \ + "Identified potential conditional operator, consider not " \ + "using ABSL_ASSIGN_OR_RETURN"); \ + } \ + { \ + static_assert( \ + absl::status_macro_internal::IsAllowedStatusOrMacroType< \ + std::remove_const_t<decltype(statusor)>>(), \ + "ABSL_ASSIGN_OR_RETURN should only be used with absl::StatusOr<>"); \ + } \ + ABSL_INTERNAL_STATUS_MACROS_IMPL_UNPARENTHESIZE_IF_PARENTHESIZED(lhs) = \ (*std::move(statusor)) // Internal helpers for macro expansion.
diff --git a/absl/status/statusor_benchmark.cc b/absl/status/statusor_benchmark.cc index ac353bb..0a9d29d 100644 --- a/absl/status/statusor_benchmark.cc +++ b/absl/status/statusor_benchmark.cc
@@ -360,12 +360,12 @@ // below for the variants. bool bm_cond = true; -bool SimpleIntInterface(int64_t* v) ABSL_ATTRIBUTE_NOINLINE; -bool SimpleIntInterfaceWithErrorMessage(int64_t* v, std::string* msg) - ABSL_ATTRIBUTE_NOINLINE; -absl::Status SimpleIntInterfaceWithErrorStatus(int64_t* v) - ABSL_ATTRIBUTE_NOINLINE; -absl::StatusOr<int64_t> SimpleIntStatusOrInterface() ABSL_ATTRIBUTE_NOINLINE; +ABSL_ATTRIBUTE_NOINLINE bool SimpleIntInterface(int64_t* v); +ABSL_ATTRIBUTE_NOINLINE bool SimpleIntInterfaceWithErrorMessage( + int64_t* v, std::string* msg); +ABSL_ATTRIBUTE_NOINLINE absl::Status SimpleIntInterfaceWithErrorStatus( + int64_t* v); +ABSL_ATTRIBUTE_NOINLINE absl::StatusOr<int64_t> SimpleIntStatusOrInterface(); // (a): Just a boolean return value with an out int64* parameter bool SimpleIntInterface(int64_t* v) {
diff --git a/absl/strings/internal/cordz_info.h b/absl/strings/internal/cordz_info.h index 04609cd..b3d88a8 100644 --- a/absl/strings/internal/cordz_info.h +++ b/absl/strings/internal/cordz_info.h
@@ -252,7 +252,7 @@ const int64_t sampling_stride_; }; -inline ABSL_ATTRIBUTE_ALWAYS_INLINE void CordzInfo::MaybeTrackCord( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline void CordzInfo::MaybeTrackCord( InlineData& cord, MethodIdentifier method) { auto stride = cordz_should_profile(); if (ABSL_PREDICT_FALSE(stride > 0)) { @@ -260,14 +260,14 @@ } } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE void CordzInfo::MaybeTrackCord( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline void CordzInfo::MaybeTrackCord( InlineData& cord, const InlineData& src, MethodIdentifier method) { if (ABSL_PREDICT_FALSE(InlineData::is_either_profiled(cord, src))) { MaybeTrackCordImpl(cord, src, method); } } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE void CordzInfo::MaybeUntrackCord( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline void CordzInfo::MaybeUntrackCord( CordzInfo* info) { if (ABSL_PREDICT_FALSE(info)) { info->Untrack();
diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index 924c912..c574dee 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc
@@ -256,7 +256,7 @@ return buffer + 16; } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU32( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline char* absl_nonnull EncodeFullU32( uint32_t n, char* absl_nonnull out_str) { if (n < 10) { *out_str = static_cast<char>('0' + n); @@ -279,7 +279,7 @@ return out_str + sizeof(bottom); } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU64( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline char* absl_nonnull EncodeFullU64( uint64_t i, char* absl_nonnull buffer) { if (i <= std::numeric_limits<uint32_t>::max()) { return EncodeFullU32(static_cast<uint32_t>(i), buffer); @@ -304,7 +304,7 @@ return buffer + sizeof(mod_result); } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU128( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline char* absl_nonnull EncodeFullU128( uint128 i, char* absl_nonnull buffer) { if (absl::Uint128High64(i) == 0) { return EncodeFullU64(absl::Uint128Low64(i), buffer);
diff --git a/absl/synchronization/mutex.h b/absl/synchronization/mutex.h index b81c595..0fbc9a5 100644 --- a/absl/synchronization/mutex.h +++ b/absl/synchronization/mutex.h
@@ -559,10 +559,11 @@ const Condition* absl_nullable cond, synchronization_internal::KernelTimeout t, int flags); - void LockSlow(MuHow absl_nonnull how, const Condition* absl_nullable cond, - int flags) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD void LockSlow(MuHow absl_nonnull how, + const Condition* absl_nullable cond, + int flags); // slow path release - void UnlockSlow(SynchWaitParams* absl_nullable waitp) ABSL_ATTRIBUTE_COLD; + ABSL_ATTRIBUTE_COLD void UnlockSlow(SynchWaitParams* absl_nullable waitp); // TryLock slow path. bool TryLockSlow(); // ReaderTryLock slow path.
diff --git a/absl/time/clock.cc b/absl/time/clock.cc index d368659..1e0f6a0 100644 --- a/absl/time/clock.cc +++ b/absl/time/clock.cc
@@ -271,7 +271,7 @@ return current_time_nanos_from_system; } -static int64_t GetCurrentTimeNanosSlowPath() ABSL_ATTRIBUTE_COLD; +ABSL_ATTRIBUTE_COLD static int64_t GetCurrentTimeNanosSlowPath(); // Read the contents of *atomic into *sample. // Each field is read atomically, but to maintain atomicity between fields, @@ -399,9 +399,9 @@ return quotient; } -static uint64_t UpdateLastSample( +ABSL_ATTRIBUTE_COLD static uint64_t UpdateLastSample( uint64_t now_cycles, uint64_t now_ns, uint64_t delta_cycles, - const struct TimeSample* sample) ABSL_ATTRIBUTE_COLD; + const struct TimeSample* sample); // The slow path of GetCurrentTimeNanos(). This is taken while gathering // initial samples, when enough time has elapsed since the last sample, and if