summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
Diffstat (limited to 'absl')
-rw-r--r--absl/base/internal/direct_mmap.h5
-rw-r--r--absl/container/internal/raw_hash_set.h26
-rw-r--r--absl/container/internal/raw_hash_set_test.cc12
-rw-r--r--absl/crc/internal/crc_memcpy.h7
-rw-r--r--absl/crc/internal/crc_memcpy_fallback.cc4
-rw-r--r--absl/crc/internal/crc_memcpy_x86_64.cc4
-rw-r--r--absl/flags/BUILD.bazel1
-rw-r--r--absl/flags/CMakeLists.txt1
-rw-r--r--absl/hash/BUILD.bazel1
-rw-r--r--absl/hash/CMakeLists.txt1
-rw-r--r--absl/hash/internal/hash.h20
11 files changed, 59 insertions, 23 deletions
diff --git a/absl/base/internal/direct_mmap.h b/absl/base/internal/direct_mmap.h
index 815b8d23..14efc637 100644
--- a/absl/base/internal/direct_mmap.h
+++ b/absl/base/internal/direct_mmap.h
@@ -72,7 +72,7 @@ namespace base_internal {
// Platform specific logic extracted from
// https://chromium.googlesource.com/linux-syscall-support/+/master/linux_syscall_support.h
inline void* DirectMmap(void* start, size_t length, int prot, int flags, int fd,
- off64_t offset) noexcept {
+ off_t offset) noexcept {
#if defined(__i386__) || defined(__ARM_ARCH_3__) || defined(__ARM_EABI__) || \
defined(__m68k__) || defined(__sh__) || \
(defined(__hppa__) && !defined(__LP64__)) || \
@@ -101,8 +101,7 @@ inline void* DirectMmap(void* start, size_t length, int prot, int flags, int fd,
static_cast<size_t>(offset / pagesize));
#else
return reinterpret_cast<void*>(
- syscall(SYS_mmap2, start, length, prot, flags, fd,
- static_cast<off_t>(offset / pagesize)));
+ syscall(SYS_mmap2, start, length, prot, flags, fd, offset / pagesize));
#endif
#elif defined(__s390x__)
// On s390x, mmap() arguments are passed in memory.
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 3762820d..0baca2a3 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -832,8 +832,8 @@ class HashSetIteratorGenerationInfoEnabled {
void set_generation_ptr(const GenerationType* ptr) { generation_ptr_ = ptr; }
private:
- const GenerationType* generation_ptr_ = nullptr;
- GenerationType generation_ = 0;
+ const GenerationType* generation_ptr_ = EmptyGeneration();
+ GenerationType generation_ = *generation_ptr_;
};
class HashSetIteratorGenerationInfoDisabled {
@@ -1021,12 +1021,17 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
} while (0)
// Note that for comparisons, null/end iterators are valid.
-// TODO(b/254649633): when generations are enabled, detect cases of invalid
-// iterators being compared.
-inline void AssertIsValidForComparison(const ctrl_t* ctrl) {
+inline void AssertIsValidForComparison(const ctrl_t* ctrl,
+ GenerationType generation,
+ const GenerationType* generation_ptr) {
ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) &&
"Invalid iterator comparison. The element might have "
"been erased or the table might have rehashed.");
+ if (SwisstableGenerationsEnabled() && generation != *generation_ptr) {
+ ABSL_INTERNAL_LOG(FATAL,
+ "Invalid iterator comparison. The table could have "
+ "rehashed since this iterator was initialized.");
+ }
}
// If the two iterators come from the same container, then their pointers will
@@ -1426,8 +1431,8 @@ class raw_hash_set {
friend bool operator==(const iterator& a, const iterator& b) {
AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_);
- AssertIsValidForComparison(a.ctrl_);
- AssertIsValidForComparison(b.ctrl_);
+ AssertIsValidForComparison(a.ctrl_, a.generation(), a.generation_ptr());
+ AssertIsValidForComparison(b.ctrl_, b.generation(), b.generation_ptr());
return a.ctrl_ == b.ctrl_;
}
friend bool operator!=(const iterator& a, const iterator& b) {
@@ -1444,6 +1449,9 @@ class raw_hash_set {
// not equal to any end iterator.
ABSL_ASSUME(ctrl != nullptr);
}
+ // For end() iterators.
+ explicit iterator(const GenerationType* generation_ptr)
+ : HashSetIteratorGenerationInfo(generation_ptr) {}
// Fixes up `ctrl_` to point to a full by advancing it and `slot_` until
// they reach one.
@@ -1700,12 +1708,12 @@ class raw_hash_set {
it.skip_empty_or_deleted();
return it;
}
- iterator end() { return {}; }
+ iterator end() { return iterator(common().generation_ptr()); }
const_iterator begin() const {
return const_cast<raw_hash_set*>(this)->begin();
}
- const_iterator end() const { return {}; }
+ const_iterator end() const { return iterator(common().generation_ptr()); }
const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 8096567c..801b758e 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1819,7 +1819,6 @@ TEST(Table, HeterogeneousLookupOverloads) {
EXPECT_TRUE((VerifyResultOf<CallCount, TransparentTable>()));
}
-// TODO(alkis): Expand iterator tests.
TEST(Iterator, IsDefaultConstructible) {
StringTable::iterator i;
EXPECT_TRUE(i == StringTable::iterator());
@@ -2249,7 +2248,8 @@ TEST(Table, AlignOne) {
// Invalid iterator use can trigger heap-use-after-free in asan,
// use-of-uninitialized-value in msan, or invalidated iterator assertions.
constexpr const char* kInvalidIteratorDeathMessage =
- "heap-use-after-free|use-of-uninitialized-value|invalidated iterator";
+ "heap-use-after-free|use-of-uninitialized-value|invalidated "
+ "iterator|Invalid iterator";
#if defined(__clang__) && defined(_MSC_VER)
constexpr bool kLexan = true;
@@ -2257,7 +2257,7 @@ constexpr bool kLexan = true;
constexpr bool kLexan = false;
#endif
-TEST(Table, InvalidIteratorUse) {
+TEST(Iterator, InvalidUseCrashesWithSanitizers) {
if (!SwisstableGenerationsEnabled()) GTEST_SKIP() << "Generations disabled.";
if (kLexan) GTEST_SKIP() << "Lexan doesn't support | in regexp.";
@@ -2268,10 +2268,12 @@ TEST(Table, InvalidIteratorUse) {
auto it = t.begin();
t.insert(i);
EXPECT_DEATH_IF_SUPPORTED(*it, kInvalidIteratorDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(it == t.begin()),
+ kInvalidIteratorDeathMessage);
}
}
-TEST(Table, InvalidIteratorUseWithReserve) {
+TEST(Iterator, InvalidUseWithReserveCrashesWithSanitizers) {
if (!SwisstableGenerationsEnabled()) GTEST_SKIP() << "Generations disabled.";
if (kLexan) GTEST_SKIP() << "Lexan doesn't support | in regexp.";
@@ -2290,6 +2292,8 @@ TEST(Table, InvalidIteratorUseWithReserve) {
// Unreserved growth can rehash.
t.insert(10);
EXPECT_DEATH_IF_SUPPORTED(*it, kInvalidIteratorDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(it == t.begin()),
+ kInvalidIteratorDeathMessage);
}
TEST(Table, ReservedGrowthUpdatesWhenTableDoesntGrow) {
diff --git a/absl/crc/internal/crc_memcpy.h b/absl/crc/internal/crc_memcpy.h
index ae9cccad..4909d433 100644
--- a/absl/crc/internal/crc_memcpy.h
+++ b/absl/crc/internal/crc_memcpy.h
@@ -21,6 +21,13 @@
#include "absl/base/config.h"
#include "absl/crc/crc32c.h"
+// Defined if the class AcceleratedCrcMemcpyEngine exists.
+#if defined(__x86_64__) && defined(__SSE4_2__)
+#define ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE 1
+#elif defined(_MSC_VER) && defined(__AVX__)
+#define ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE 1
+#endif
+
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace crc_internal {
diff --git a/absl/crc/internal/crc_memcpy_fallback.cc b/absl/crc/internal/crc_memcpy_fallback.cc
index 4579c164..15b4b055 100644
--- a/absl/crc/internal/crc_memcpy_fallback.cc
+++ b/absl/crc/internal/crc_memcpy_fallback.cc
@@ -54,7 +54,7 @@ absl::crc32c_t FallbackCrcMemcpyEngine::Compute(void* __restrict dst,
}
// Compile the following only if we don't have
-#ifndef __SSE4_2__
+#ifndef ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE
CrcMemcpy::ArchSpecificEngines CrcMemcpy::GetArchSpecificEngines() {
CrcMemcpy::ArchSpecificEngines engines;
@@ -68,7 +68,7 @@ std::unique_ptr<CrcMemcpyEngine> CrcMemcpy::GetTestEngine(int /*vector*/,
return std::make_unique<FallbackCrcMemcpyEngine>();
}
-#endif
+#endif // ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE
} // namespace crc_internal
ABSL_NAMESPACE_END
diff --git a/absl/crc/internal/crc_memcpy_x86_64.cc b/absl/crc/internal/crc_memcpy_x86_64.cc
index a148fe17..66f784de 100644
--- a/absl/crc/internal/crc_memcpy_x86_64.cc
+++ b/absl/crc/internal/crc_memcpy_x86_64.cc
@@ -59,7 +59,7 @@
#include "absl/crc/internal/crc_memcpy.h"
#include "absl/strings/string_view.h"
-#if defined(__SSE4_2__) || (defined(_MSC_VER) && defined(__AVX__))
+#ifdef ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE
namespace absl {
ABSL_NAMESPACE_BEGIN
@@ -431,4 +431,4 @@ std::unique_ptr<CrcMemcpyEngine> CrcMemcpy::GetTestEngine(int vector,
ABSL_NAMESPACE_END
} // namespace absl
-#endif // defined(__SSE4_2__) || (defined(_MSC_VER) && defined(__AVX__))
+#endif // ABSL_INTERNAL_HAVE_X86_64_ACCELERATED_CRC_MEMCPY_ENGINE
diff --git a/absl/flags/BUILD.bazel b/absl/flags/BUILD.bazel
index 3d6d59e6..f5b3e033 100644
--- a/absl/flags/BUILD.bazel
+++ b/absl/flags/BUILD.bazel
@@ -309,6 +309,7 @@ cc_library(
":reflection",
":usage",
":usage_internal",
+ "//absl/algorithm:container",
"//absl/base:config",
"//absl/base:core_headers",
"//absl/strings",
diff --git a/absl/flags/CMakeLists.txt b/absl/flags/CMakeLists.txt
index 3e9d5adf..2f234aa4 100644
--- a/absl/flags/CMakeLists.txt
+++ b/absl/flags/CMakeLists.txt
@@ -279,6 +279,7 @@ absl_cc_library(
LINKOPTS
${ABSL_DEFAULT_LINKOPTS}
DEPS
+ absl::algorithm_container
absl::config
absl::core_headers
absl::flags_config
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel
index 4a95f054..a0db919b 100644
--- a/absl/hash/BUILD.bazel
+++ b/absl/hash/BUILD.bazel
@@ -43,6 +43,7 @@ cc_library(
"//absl/container:fixed_array",
"//absl/functional:function_ref",
"//absl/meta:type_traits",
+ "//absl/numeric:bits",
"//absl/numeric:int128",
"//absl/strings",
"//absl/types:optional",
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt
index 0514c296..f99f35bc 100644
--- a/absl/hash/CMakeLists.txt
+++ b/absl/hash/CMakeLists.txt
@@ -25,6 +25,7 @@ absl_cc_library(
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
+ absl::bits
absl::city
absl::config
absl::core_headers
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index dbdc2050..ccf4cc1a 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -49,6 +49,7 @@
#include "absl/hash/internal/city.h"
#include "absl/hash/internal/low_level_hash.h"
#include "absl/meta/type_traits.h"
+#include "absl/numeric/bits.h"
#include "absl/numeric/int128.h"
#include "absl/strings/string_view.h"
#include "absl/types/optional.h"
@@ -1052,7 +1053,7 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> {
uint64_t most_significant = low_mem;
uint64_t least_significant = high_mem;
#endif
- return {least_significant, most_significant >> (128 - len * 8)};
+ return {least_significant, most_significant};
}
// Reads 4 to 8 bytes from p. Zero pads to fill uint64_t.
@@ -1183,9 +1184,22 @@ inline uint64_t MixingHashState::CombineContiguousImpl(
}
v = Hash64(first, len);
} else if (len > 8) {
+ // This hash function was constructed by the ML-driven algorithm discovery
+ // using reinforcement learning. We fed the agent lots of inputs from
+ // microbenchmarks, SMHasher, low hamming distance from generated inputs and
+ // picked up the one that was good on micro and macrobenchmarks.
auto p = Read9To16(first, len);
- state = Mix(state, p.first);
- v = p.second;
+ uint64_t lo = p.first;
+ uint64_t hi = p.second;
+ // Rotation by 53 was found to be most often useful when discovering these
+ // hashing algorithms with ML techniques.
+ lo = absl::rotr(lo, 53);
+ state += kMul;
+ lo += state;
+ state ^= hi;
+ uint128 m = state;
+ m *= lo;
+ return static_cast<uint64_t>(m ^ (m >> 64));
} else if (len >= 4) {
v = Read4To8(first, len);
} else if (len > 0) {
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 19:04:40 +0000