Remove the time (or time-based) entropy being added to Map's seed.
This is similar in effect to if GOOGLE_PROTOBUF_NO_RDTSC define was enabled always.
Hashing the address of the table plus the per-process entropy added by absl::Hash is sufficient amount of entropy for this usecase.
PiperOrigin-RevId: 696982713
diff --git a/src/google/protobuf/map.h b/src/google/protobuf/map.h
index 3d65e7c..637926c 100644
--- a/src/google/protobuf/map.h
+++ b/src/google/protobuf/map.h
@@ -31,11 +31,6 @@
#include "absl/memory/memory.h"
#include "google/protobuf/message_lite.h"
-#if !defined(GOOGLE_PROTOBUF_NO_RDTSC) && defined(__APPLE__) && \
- (!defined(_POSIX_C_SOURCE) || defined(_DARWIN_C_SOURCE))
-#include <time.h>
-#endif
-
#include "absl/base/attributes.h"
#include "absl/container/btree_map.h"
#include "absl/hash/hash.h"
@@ -563,7 +558,6 @@
explicit constexpr UntypedMapBase(Arena* arena)
: num_elements_(0),
num_buckets_(internal::kGlobalEmptyTableSize),
- seed_(0),
index_of_first_non_null_(internal::kGlobalEmptyTableSize),
table_(const_cast<TableEntryPtr*>(internal::kGlobalEmptyTable)),
alloc_(arena) {}
@@ -581,7 +575,6 @@
void InternalSwap(UntypedMapBase* other) {
std::swap(num_elements_, other->num_elements_);
std::swap(num_buckets_, other->num_buckets_);
- std::swap(seed_, other->seed_);
std::swap(index_of_first_non_null_, other->index_of_first_non_null_);
std::swap(table_, other->table_);
std::swap(alloc_, other->alloc_);
@@ -621,7 +614,7 @@
return false;
#else
// Doing modulo with a prime mixes the bits more.
- return (reinterpret_cast<uintptr_t>(node) ^ seed_) % 13 > 6;
+ return absl::HashOf(node, table_) % 13 > 6;
#endif
}
@@ -708,12 +701,12 @@
}
map_index_t VariantBucketNumber(absl::string_view key) const {
- return static_cast<map_index_t>(absl::HashOf(seed_, key) &
+ return static_cast<map_index_t>(absl::HashOf(key, table_) &
(num_buckets_ - 1));
}
map_index_t VariantBucketNumber(uint64_t key) const {
- return static_cast<map_index_t>(absl::HashOf(key ^ seed_) &
+ return static_cast<map_index_t>(absl::HashOf(key, table_) &
(num_buckets_ - 1));
}
@@ -725,34 +718,6 @@
return result;
}
- // Return a randomish value.
- map_index_t Seed() const {
- uint64_t s = 0;
-#if !defined(GOOGLE_PROTOBUF_NO_RDTSC)
-#if defined(__APPLE__) && \
- (!defined(_POSIX_C_SOURCE) || defined(_DARWIN_C_SOURCE))
- // Use a commpage-based fast time function on Apple environments (MacOS,
- // iOS, tvOS, watchOS, etc), if we think the system headers expose it.
- s = clock_gettime_nsec_np(CLOCK_UPTIME_RAW);
-#elif defined(__x86_64__) && defined(__GNUC__)
- uint32_t hi, lo;
- asm volatile("rdtsc" : "=a"(lo), "=d"(hi));
- s = ((static_cast<uint64_t>(hi) << 32) | lo);
-#elif defined(__aarch64__) && defined(__GNUC__)
- // There is no rdtsc on ARMv8. CNTVCT_EL0 is the virtual counter of the
- // system timer. It runs at a different frequency than the CPU's, but is
- // the best source of time-based entropy we get.
- uint64_t virtual_timer_value;
- asm volatile("mrs %0, cntvct_el0" : "=r"(virtual_timer_value));
- s = virtual_timer_value;
-#endif
-#endif // !defined(GOOGLE_PROTOBUF_NO_RDTSC)
- // Add entropy from the address of the map and the address of the table
- // array.
- return static_cast<map_index_t>(
- absl::HashOf(s, table_, static_cast<const void*>(this)));
- }
-
enum {
kKeyIsString = 1 << 0,
kValueIsString = 1 << 1,
@@ -812,7 +777,6 @@
map_index_t num_elements_;
map_index_t num_buckets_;
- map_index_t seed_;
map_index_t index_of_first_non_null_;
TableEntryPtr* table_; // an array with num_buckets_ entries
Allocator alloc_;
@@ -1096,7 +1060,6 @@
// Just overwrite with a new one. No need to transfer or free anything.
num_buckets_ = index_of_first_non_null_ = kMinTableSize;
table_ = CreateEmptyTable(num_buckets_);
- seed_ = Seed();
return;
}
diff --git a/src/google/protobuf/map_test.inc b/src/google/protobuf/map_test.inc
index a87f9dc..40233b7 100644
--- a/src/google/protobuf/map_test.inc
+++ b/src/google/protobuf/map_test.inc
@@ -201,14 +201,6 @@
map.Resize(num_buckets);
}
- template <typename T>
- static bool HasTreeBuckets(T& map) {
- for (size_t i = 0; i < map.num_buckets_; ++i) {
- if (TableEntryIsTree(map.table_[i])) return true;
- }
- return false;
- }
-
static int CalculateHiCutoff(int num_buckets) {
return Map<int, int>::CalculateHiCutoff(num_buckets);
}
@@ -513,48 +505,6 @@
static int k1 = 1312938717;
static int k2 = 1321555333;
-// Finds inputs that will fall in the first few buckets for this particular map
-// (with the random seed it has) and this particular size.
-static std::vector<int> FindBadInputs(Map<int, int>& map, int num_inputs) {
- // Make sure the seed and the size is set so that BucketNumber works.
- while (map.size() < num_inputs) map[map.size()];
- map.clear();
-
- std::vector<int> out;
-
- for (int i = 0; out.size() < num_inputs; ++i) {
- if (MapTestPeer::BucketNumber(map, i) < 3) {
- out.push_back(i);
- }
- }
-
- // Reset the table to get it to grow from scratch again.
- // The capacity will be lost, but we will get it again on insertion.
- // It will also keep the seed.
- map.clear();
- MapTestPeer::Resize(map, 8);
-
- return out;
-}
-
-TEST_F(MapImplTest, TreePathWorksAsExpected) {
- const std::vector<int> s = FindBadInputs(map_, 1000);
-
- for (int i : s) {
- map_[i] = 0;
- }
- // Make sure we are testing what we think we are testing.
- ASSERT_TRUE(MapTestPeer::HasTreeBuckets(map_));
- for (int i : s) {
- ASSERT_NE(map_.find(i), map_.end()) << i;
- }
- for (int i : s) {
- ASSERT_EQ(1, map_.erase(i)) << i;
- }
- EXPECT_FALSE(MapTestPeer::HasTreeBuckets(map_));
- EXPECT_TRUE(map_.empty());
-}
-
TEST_F(MapImplTest, CopyIteratorStressTest) {
std::vector<Map<int32_t, int32_t>::iterator> v;
