diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index ef97b4e..3724ad1 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel
@@ -685,7 +685,6 @@ cc_test( name = "thread_identity_test", - size = "small", srcs = ["internal/thread_identity_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS,
diff --git a/absl/base/macros.h b/absl/base/macros.h index ff89944..f9acdc8 100644 --- a/absl/base/macros.h +++ b/absl/base/macros.h
@@ -197,9 +197,9 @@ // While open-source users do not have access to this service, the macro is // provided for compatibility, and so that users receive deprecation warnings. #if ABSL_HAVE_CPP_ATTRIBUTE(deprecated) && \ - ABSL_HAVE_CPP_ATTRIBUTE(clang::annotate) + ABSL_HAVE_CPP_ATTRIBUTE(clang::annotate) && !defined(SWIG) #define ABSL_DEPRECATE_AND_INLINE() [[deprecated, clang::annotate("inline-me")]] -#elif ABSL_HAVE_CPP_ATTRIBUTE(deprecated) +#elif ABSL_HAVE_CPP_ATTRIBUTE(deprecated) && !defined(SWIG) #define ABSL_DEPRECATE_AND_INLINE() [[deprecated]] #else #define ABSL_DEPRECATE_AND_INLINE()
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 339e662..cea225e 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -118,6 +118,14 @@ return hash ^ seed.seed(); } +// Returns the offset of the new element after resize from capacity 1 to 3. +size_t Resize1To3NewOffset(size_t hash, PerTableSeed seed) { + // After resize from capacity 1 to 3, we always have exactly the slot with + // index 1 occupied, so we need to insert either at index 0 or index 2. + static_assert(SooSlotIndex() == 1); + return SingleGroupTableH1(hash, seed) & 2; +} + // Returns the address of the slot `i` iterations after `slot` assuming each // slot has the specified size. inline void* NextSlot(void* slot, size_t slot_size, size_t i = 1) { @@ -175,35 +183,36 @@ } } -// Whether a table is "small". A small table fits entirely into a probing -// group, i.e., has a capacity < `Group::kWidth`. +// Whether a table fits in half a group. A half-group table fits entirely into a +// probing group, i.e., has a capacity < `Group::kWidth`. // -// In small mode we are able to use the whole capacity. The extra control +// In half-group mode we are able to use the whole capacity. The extra control // bytes give us at least one "empty" control byte to stop the iteration. // This is important to make 1 a valid capacity. // -// In small mode only the first `capacity` control bytes after the sentinel +// In half-group mode only the first `capacity` control bytes after the sentinel // are valid. The rest contain dummy ctrl_t::kEmpty values that do not // represent a real slot. -constexpr bool is_small(size_t capacity) { +constexpr bool is_half_group(size_t capacity) { return capacity < Group::kWidth - 1; } template <class Fn> void IterateOverFullSlotsImpl(const CommonFields& c, size_t slot_size, Fn cb) { const size_t cap = c.capacity(); + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); const ctrl_t* ctrl = c.control(); void* slot = c.slot_array(); - if (is_small(cap)) { - // Mirrored/cloned control bytes in small table are also located in the + if (is_half_group(cap)) { + // Mirrored/cloned control bytes in half-group table are also located in the // first group (starting from position 0). We are taking group from position // `capacity` in order to avoid duplicates. - // Small tables capacity fits into portable group, where + // Half-group tables capacity fits into portable group, where // GroupPortableImpl::MaskFull is more efficient for the // capacity <= GroupPortableImpl::kWidth. ABSL_SWISSTABLE_ASSERT(cap <= GroupPortableImpl::kWidth && - "unexpectedly large small capacity"); + "unexpectedly large half-group capacity"); static_assert(Group::kWidth >= GroupPortableImpl::kWidth, "unexpected group width"); // Group starts from kSentinel slot, so indices in the mask will @@ -410,7 +419,7 @@ return find_info.offset; } -static bool WasNeverFull(CommonFields& c, size_t index) { +bool WasNeverFull(CommonFields& c, size_t index) { if (is_single_group(c.capacity())) { return true; } @@ -449,38 +458,11 @@ SanitizerPoisonMemoryRegion(common.slot_array(), slot_size * capacity); } -// Initializes control bytes for single element table. -// Capacity of the table must be 1. -ABSL_ATTRIBUTE_ALWAYS_INLINE inline void InitializeSingleElementControlBytes( - uint64_t h2, ctrl_t* new_ctrl) { - static constexpr uint64_t kEmptyXorSentinel = - static_cast<uint8_t>(ctrl_t::kEmpty) ^ - static_cast<uint8_t>(ctrl_t::kSentinel); - static constexpr uint64_t kEmpty64 = static_cast<uint8_t>(ctrl_t::kEmpty); - // The first 8 bytes, where present slot positions are replaced with 0. - static constexpr uint64_t kFirstCtrlBytesWithZeroes = - k8EmptyBytes ^ kEmpty64 ^ (kEmptyXorSentinel << 8) ^ (kEmpty64 << 16); - - // Fill the original 0th and mirrored 2nd bytes with the hash. - // Result will look like: - // HSHEEEEE - // Where H = h2, E = kEmpty, S = kSentinel. - const uint64_t first_ctrl_bytes = - (h2 | kFirstCtrlBytesWithZeroes) | (h2 << 16); - // Fill last bytes with kEmpty. - std::memset(new_ctrl + 1, static_cast<int8_t>(ctrl_t::kEmpty), Group::kWidth); - // Overwrite the first 3 bytes with HSH. Other bytes will not be changed. - absl::little_endian::Store64(new_ctrl, first_ctrl_bytes); -} - -// Initializes control bytes for growing after SOO to the next capacity. -// `soo_ctrl` is placed in the position `SooSlotIndex()`. -// `new_hash` is placed in the position `new_offset`. -// The table must be non-empty SOO. -ABSL_ATTRIBUTE_ALWAYS_INLINE inline void -InitializeThreeElementsControlBytesAfterSoo(ctrl_t soo_ctrl, size_t new_hash, - size_t new_offset, - ctrl_t* new_ctrl) { +// Initializes control bytes for growing from capacity 1 to 3. +// `orig_h2` is placed in the position `SooSlotIndex()`. +// `new_h2` is placed in the position `new_offset`. +ABSL_ATTRIBUTE_ALWAYS_INLINE inline void InitializeThreeElementsControlBytes( + h2_t orig_h2, h2_t new_h2, size_t new_offset, ctrl_t* new_ctrl) { static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); static_assert(kNewCapacity == 3); static_assert(is_single_group(kNewCapacity)); @@ -501,9 +483,9 @@ (kEmptyXorSentinel << (8 * kNewCapacity)) ^ (kEmpty64 << (8 * kMirroredSooSlotIndex)); - const uint64_t soo_h2 = static_cast<uint64_t>(soo_ctrl); - const uint64_t new_h2_xor_empty = static_cast<uint64_t>( - H2(new_hash) ^ static_cast<uint8_t>(ctrl_t::kEmpty)); + const uint64_t soo_h2 = static_cast<uint64_t>(orig_h2); + const uint64_t new_h2_xor_empty = + static_cast<uint64_t>(new_h2 ^ static_cast<uint8_t>(ctrl_t::kEmpty)); // Fill the original and mirrored bytes for SOO slot. // Result will look like: // EHESEHEE @@ -550,6 +532,12 @@ c.decrement_size(); c.infoz().RecordErase(); + if (c.is_small()) { + SanitizerPoisonMemoryRegion(c.slot_array(), slot_size); + c.growth_info().OverwriteFullAsEmpty(); + return; + } + if (WasNeverFull(c, index)) { SetCtrl(c, index, ctrl_t::kEmpty, slot_size); c.growth_info().OverwriteFullAsEmpty(); @@ -608,6 +596,10 @@ slot, 1); return target.probe_length; }; + if (old_capacity == 1) { + if (common.size() == 1) insert_slot(old_slots); + return 0; + } size_t total_probe_length = 0; for (size_t i = 0; i < old_capacity; ++i) { if (IsFull(old_ctrl[i])) { @@ -618,6 +610,27 @@ return total_probe_length; } +struct BackingArrayPtrs { + ctrl_t* ctrl; + void* slots; +}; + +BackingArrayPtrs AllocBackingArray(CommonFields& common, + const PolicyFunctions& __restrict policy, + size_t new_capacity, bool has_infoz, + void* alloc) { + RawHashSetLayout layout(new_capacity, policy.slot_size, policy.slot_align, + has_infoz); + char* mem = static_cast<char*>(policy.alloc(alloc, layout.alloc_size())); + const GenerationType old_generation = common.generation(); + common.set_generation_ptr( + reinterpret_cast<GenerationType*>(mem + layout.generation_offset())); + common.set_generation(NextGeneration(old_generation)); + + return {reinterpret_cast<ctrl_t*>(mem + layout.control_offset()), + mem + layout.slot_offset()}; +} + template <ResizeNonSooMode kMode> void ResizeNonSooImpl(CommonFields& common, const PolicyFunctions& __restrict policy, @@ -632,19 +645,13 @@ const size_t slot_size = policy.slot_size; const size_t slot_align = policy.slot_align; const bool has_infoz = infoz.IsSampled(); + void* alloc = policy.get_char_alloc(common); common.set_capacity(new_capacity); - RawHashSetLayout layout(new_capacity, slot_size, slot_align, has_infoz); - void* alloc = policy.get_char_alloc(common); - char* mem = static_cast<char*>(policy.alloc(alloc, layout.alloc_size())); - const GenerationType old_generation = common.generation(); - common.set_generation_ptr( - reinterpret_cast<GenerationType*>(mem + layout.generation_offset())); - common.set_generation(NextGeneration(old_generation)); - - ctrl_t* new_ctrl = reinterpret_cast<ctrl_t*>(mem + layout.control_offset()); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); common.set_control</*kGenerateSeed=*/true>(new_ctrl); - common.set_slots(mem + layout.slot_offset()); + common.set_slots(new_slots); size_t total_probe_length = 0; ResetCtrl(common, slot_size); @@ -739,7 +746,7 @@ ResizeFullSooTableSamplingMode sampling_mode) { AssertFullSoo(common, policy); const size_t slot_size = policy.slot_size; - const size_t slot_align = policy.slot_align; + void* alloc = policy.get_char_alloc(common); HashtablezInfoHandle infoz; if (sampling_mode == @@ -758,18 +765,10 @@ common.set_capacity(new_capacity); - RawHashSetLayout layout(new_capacity, slot_size, slot_align, has_infoz); - void* alloc = policy.get_char_alloc(common); - char* mem = static_cast<char*>(policy.alloc(alloc, layout.alloc_size())); - const GenerationType old_generation = common.generation(); - common.set_generation_ptr( - reinterpret_cast<GenerationType*>(mem + layout.generation_offset())); - common.set_generation(NextGeneration(old_generation)); - // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. - ctrl_t* new_ctrl = reinterpret_cast<ctrl_t*>(mem + layout.control_offset()); - void* new_slots = mem + layout.slot_offset(); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); const size_t soo_slot_hash = policy.hash_slot(policy.hash_fn(common), common.soo_data()); @@ -1224,19 +1223,31 @@ } } -// Grows to next capacity and prepares insert for the given new_hash. -// Returns the offset of the new element. +void IncrementSmallSize(CommonFields& common, + const PolicyFunctions& __restrict policy) { + ABSL_SWISSTABLE_ASSERT(common.is_small()); + if (policy.soo_enabled) { + common.set_full_soo(); + } else { + common.increment_size(); + common.growth_info().OverwriteEmptyAsFull(); + SanitizerUnpoisonMemoryRegion(common.slot_array(), policy.slot_size); + } +} + +} // namespace + size_t GrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_hash) { ABSL_SWISSTABLE_ASSERT(common.growth_left() == 0); const size_t old_capacity = common.capacity(); - ABSL_SWISSTABLE_ASSERT(old_capacity == 0 || - old_capacity > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); const size_t new_capacity = NextCapacity(old_capacity); ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(new_capacity)); ctrl_t* old_ctrl = common.control(); void* old_slots = common.slot_array(); @@ -1244,29 +1255,12 @@ common.set_capacity(new_capacity); const size_t slot_size = policy.slot_size; const size_t slot_align = policy.slot_align; - HashtablezInfoHandle infoz; - if (old_capacity > 0) { - infoz = common.infoz(); - } else { - const bool should_sample = - policy.is_hashtablez_eligible && ShouldSampleNextTable(); - if (ABSL_PREDICT_FALSE(should_sample)) { - infoz = ForcedTrySample(slot_size, policy.key_size, policy.value_size, - policy.soo_capacity()); - } - } + void* alloc = policy.get_char_alloc(common); + HashtablezInfoHandle infoz = common.infoz(); const bool has_infoz = infoz.IsSampled(); - RawHashSetLayout layout(new_capacity, slot_size, slot_align, has_infoz); - void* alloc = policy.get_char_alloc(common); - char* mem = static_cast<char*>(policy.alloc(alloc, layout.alloc_size())); - const GenerationType old_generation = common.generation(); - common.set_generation_ptr( - reinterpret_cast<GenerationType*>(mem + layout.generation_offset())); - common.set_generation(NextGeneration(old_generation)); - - ctrl_t* new_ctrl = reinterpret_cast<ctrl_t*>(mem + layout.control_offset()); - void* new_slots = mem + layout.slot_offset(); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, alloc); common.set_control</*kGenerateSeed=*/false>(new_ctrl); common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size); @@ -1274,41 +1268,43 @@ h2_t new_h2 = H2(new_hash); size_t total_probe_length = 0; FindInfo find_info; - if (old_capacity == 0) { - static_assert(NextCapacity(0) == 1); - InitializeSingleElementControlBytes(new_h2, new_ctrl); - common.generate_new_seed(); - find_info = FindInfo{0, 0}; - SanitizerUnpoisonMemoryRegion(new_slots, slot_size); - } else { - if (ABSL_PREDICT_TRUE(is_single_group(new_capacity))) { + if (ABSL_PREDICT_TRUE(is_single_group(new_capacity))) { + size_t offset; + if (old_capacity == 1) { + size_t orig_hash = policy.hash_slot(policy.hash_fn(common), old_slots); + offset = Resize1To3NewOffset(new_hash, common.seed()); + InitializeThreeElementsControlBytes(H2(orig_hash), new_h2, offset, + new_ctrl); + void* target_slot = SlotAddress(new_slots, offset, slot_size); + SanitizerUnpoisonMemoryRegion(target_slot, slot_size); + } else { GrowIntoSingleGroupShuffleControlBytes(old_ctrl, old_capacity, new_ctrl, new_capacity); - // Single group tables have all slots full on resize. So we can transfer - // all slots without checking the control bytes. - ABSL_SWISSTABLE_ASSERT(common.size() == old_capacity); - auto* target = NextSlot(new_slots, slot_size); - SanitizerUnpoisonMemoryRegion(target, old_capacity * slot_size); - policy.transfer_n(&common, target, old_slots, old_capacity); // We put the new element either at the beginning or at the end of the // table with approximately equal probability. - size_t offset = SingleGroupTableH1(new_hash, common.seed()) & 1 - ? 0 - : new_capacity - 1; + offset = SingleGroupTableH1(new_hash, common.seed()) & 1 + ? 0 + : new_capacity - 1; ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[offset])); SetCtrlInSingleGroupTable(common, offset, new_h2, policy.slot_size); - find_info = FindInfo{offset, 0}; - } else { - total_probe_length = - GrowToNextCapacityDispatch(common, policy, old_ctrl, old_slots); - find_info = find_first_non_full(common, new_hash); - SetCtrlInLargeTable(common, find_info.offset, new_h2, policy.slot_size); } - ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); - (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz); + find_info = FindInfo{offset, 0}; + // Single group tables have all slots full on resize. So we can transfer + // all slots without checking the control bytes. + ABSL_SWISSTABLE_ASSERT(common.size() == old_capacity); + void* target = NextSlot(new_slots, slot_size); + SanitizerUnpoisonMemoryRegion(target, old_capacity * slot_size); + policy.transfer_n(&common, target, old_slots, old_capacity); + } else { + total_probe_length = + GrowToNextCapacityDispatch(common, policy, old_ctrl, old_slots); + find_info = find_first_non_full(common, new_hash); + SetCtrlInLargeTable(common, find_info.offset, new_h2, policy.slot_size); } + ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); + (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, + has_infoz); PrepareInsertCommon(common); ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, common.size()); @@ -1323,6 +1319,55 @@ return find_info.offset; } +void SmallEmptyNonSooPrepareInsert(CommonFields& common, + const PolicyFunctions& __restrict policy, + absl::FunctionRef<size_t()> get_hash) { + ABSL_SWISSTABLE_ASSERT(common.is_small()); + ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); + if (common.capacity() == 1) { + IncrementSmallSize(common, policy); + return; + } + + constexpr size_t kNewCapacity = 1; + + common.set_capacity(kNewCapacity); + HashtablezInfoHandle infoz; + const bool should_sample = + policy.is_hashtablez_eligible && ShouldSampleNextTable(); + if (ABSL_PREDICT_FALSE(should_sample)) { + infoz = ForcedTrySample(policy.slot_size, policy.key_size, + policy.value_size, policy.soo_capacity()); + } + const bool has_infoz = infoz.IsSampled(); + void* alloc = policy.get_char_alloc(common); + + // TODO(b/413062340): don't allocate control bytes for capacity 1 tables. We + // don't use the control bytes in this case. + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc); + common.set_control</*kGenerateSeed=*/true>(new_ctrl); + common.set_slots(new_slots); + + static_assert(NextCapacity(0) == 1); + PrepareInsertCommon(common); + // TODO(b/413062340): maybe don't allocate growth info for capacity 1 tables. + // Doing so may require additional branches/complexity so it might not be + // worth it. + GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(0); + + if (ABSL_PREDICT_TRUE(!has_infoz)) return; + // TODO(b/413062340): we could potentially store infoz in place of the control + // pointer for the capacity 1 case. + common.set_has_infoz(); + infoz.RecordStorageChanged(/*size=*/0, kNewCapacity); + infoz.RecordRehash(/*total_probe_length=*/0); + infoz.RecordInsert(get_hash(), /*distance_from_desired=*/0); + common.set_infoz(infoz); +} + +namespace { + // Called whenever the table needs to vacate empty slots either by removing // tombstones via rehash or growth to next capacity. ABSL_ATTRIBUTE_NOINLINE @@ -1511,36 +1556,25 @@ ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); const size_t slot_size = policy.slot_size; - const size_t slot_align = policy.slot_align; + void* alloc = policy.get_char_alloc(common); common.set_capacity(kNewCapacity); // Since the table is not empty, it will not be sampled. // The decision to sample was already made during the first insertion. - RawHashSetLayout layout(kNewCapacity, slot_size, slot_align, - /*has_infoz=*/false); - void* alloc = policy.get_char_alloc(common); - char* mem = static_cast<char*>(policy.alloc(alloc, layout.alloc_size())); - const GenerationType old_generation = common.generation(); - common.set_generation_ptr( - reinterpret_cast<GenerationType*>(mem + layout.generation_offset())); - common.set_generation(NextGeneration(old_generation)); - + // // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. - ctrl_t* new_ctrl = reinterpret_cast<ctrl_t*>(mem + layout.control_offset()); - void* new_slots = mem + layout.slot_offset(); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, policy, kNewCapacity, /*has_infoz=*/false, alloc); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2); common.generate_new_seed(); - // After resize from capacity 1 to 3, we always have exactly the slot with - // index 1 occupied, so we need to insert either at index 0 or index 2. - static_assert(SooSlotIndex() == 1); - const size_t offset = SingleGroupTableH1(new_hash, common.seed()) & 2; - InitializeThreeElementsControlBytesAfterSoo(soo_slot_ctrl, new_hash, offset, - new_ctrl); + const size_t offset = Resize1To3NewOffset(new_hash, common.seed()); + InitializeThreeElementsControlBytes(static_cast<h2_t>(soo_slot_ctrl), + H2(new_hash), offset, new_ctrl); SanitizerPoisonMemoryRegion(new_slots, slot_size * kNewCapacity); void* target_slot = SlotAddress(new_slots, SooSlotIndex(), slot_size); @@ -1612,7 +1646,7 @@ } ABSL_SWISSTABLE_ASSERT(slot_size <= sizeof(HeapOrSoo)); ABSL_SWISSTABLE_ASSERT(policy.slot_align <= alignof(HeapOrSoo)); - HeapOrSoo tmp_slot(uninitialized_tag_t{}); + HeapOrSoo tmp_slot; size_t begin_offset = FindFirstFullSlot(0, cap, common.control()); policy.transfer_n( &common, &tmp_slot, @@ -1655,19 +1689,22 @@ ABSL_SWISSTABLE_ASSERT(size > 0); const size_t soo_capacity = policy.soo_capacity(); const size_t slot_size = policy.slot_size; - if (size <= soo_capacity) { - ABSL_SWISSTABLE_ASSERT(size == 1); - common.set_full_soo(); + const bool soo_enabled = policy.soo_enabled; + if (size == 1) { + if (!soo_enabled) ReserveTableToFitNewSize(common, policy, 1); + IncrementSmallSize(common, policy); + const size_t other_capacity = other.capacity(); const void* other_slot = - other.capacity() <= soo_capacity - ? other.soo_data() - : SlotAddress( - other.slot_array(), - FindFirstFullSlot(0, other.capacity(), other.control()), - slot_size); - copy_fn(common.soo_data(), other_slot); + other_capacity <= soo_capacity ? other.soo_data() + : other.is_small() + ? other.slot_array() + : SlotAddress(other.slot_array(), + FindFirstFullSlot(0, other_capacity, other.control()), + slot_size); + copy_fn(soo_enabled ? common.soo_data() : common.slot_array(), other_slot); - if (policy.is_hashtablez_eligible && ShouldSampleNextTable()) { + if (soo_enabled && policy.is_hashtablez_eligible && + ShouldSampleNextTable()) { GrowFullSooTableToNextCapacityForceSampling(common, policy); } return;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 3effc44..f5fdf66 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -150,11 +150,11 @@ // To `insert`, we compose `unchecked_insert` with `find`. We compute `h(x)` and // perform a `find` to see if it's already present; if it is, we're done. If // it's not, we may decide the table is getting overcrowded (i.e. the load -// factor is greater than 7/8 for big tables; `is_small()` tables use a max load -// factor of 1); in this case, we allocate a bigger array, `unchecked_insert` -// each element of the table into the new array (we know that no insertion here -// will insert an already-present value), and discard the old backing array. At -// this point, we may `unchecked_insert` the value `x`. +// factor is greater than 7/8 for big tables; tables smaller than one probing +// group use a max load factor of 1); in this case, we allocate a bigger array, +// `unchecked_insert` each element of the table into the new array (we know that +// no insertion here will insert an already-present value), and discard the old +// backing array. At this point, we may `unchecked_insert` the value `x`. // // Below, `unchecked_insert` is partly implemented by `prepare_insert`, which // presents a viable, initialized slot pointee to the caller. @@ -381,6 +381,8 @@ } // See definition comment for why this is size 32. +// TODO(b/413062340): we can probably reduce this to 16 now that it's only used +// for default-constructed iterators. ABSL_DLL extern const ctrl_t kEmptyGroup[32]; // We use these sentinel capacity values in debug mode to indicate different @@ -395,10 +397,11 @@ kSelfMovedFrom, }; -// Returns a pointer to a control byte group that can be used by empty tables. +// Returns a pointer to a control byte group that can be used by +// default-constructed iterators. inline ctrl_t* EmptyGroup() { // Const must be cast away here; no uses of this function will actually write - // to it because it is only used for empty tables. + // to it because it is only used for default-constructed iterators. return const_cast<ctrl_t*>(kEmptyGroup + 16); } @@ -781,6 +784,9 @@ // A valid capacity is a non-zero integer `2^m - 1`. constexpr bool IsValidCapacity(size_t n) { return ((n + 1) & n) == 0 && n > 0; } +// Whether a table is small enough that we don't need to hash any keys. +constexpr bool IsSmallCapacity(size_t capacity) { return capacity <= 1; } + // Returns the number of "cloned control bytes". // // This is the number of control bytes that are present both at the beginning @@ -865,31 +871,28 @@ // This allows us to work around an uninitialized memory warning when // constructing begin() iterators in empty hashtables. +template <typename T> union MaybeInitializedPtr { - void* get() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(p); } - void set(void* ptr) { p = ptr; } + T* get() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(p); } + void set(T* ptr) { p = ptr; } - void* p; + T* p; }; struct HeapPtrs { - explicit HeapPtrs(uninitialized_tag_t) {} - explicit HeapPtrs(ctrl_t* c) : control(c) {} - // The control bytes (and, also, a pointer near to the base of the backing // array). // - // This contains `capacity + 1 + NumClonedBytes()` entries, even - // when the table is empty (hence EmptyGroup). + // This contains `capacity + 1 + NumClonedBytes()` entries. // // Note that growth_info is stored immediately before this pointer. - // May be uninitialized for SOO tables. - ctrl_t* control; + // May be uninitialized for small tables. + MaybeInitializedPtr<ctrl_t> control; // The beginning of the slots, located at `SlotOffset()` bytes after // `control`. May be uninitialized for empty tables. // Note: we can't use `slots` because Qt defines "slots" as a macro. - MaybeInitializedPtr slot_array; + MaybeInitializedPtr<void> slot_array; }; // Returns the maximum size of the SOO slot. @@ -898,19 +901,16 @@ // Manages the backing array pointers or the SOO slot. When raw_hash_set::is_soo // is true, the SOO slot is stored in `soo_data`. Otherwise, we use `heap`. union HeapOrSoo { - explicit HeapOrSoo(uninitialized_tag_t) : heap(uninitialized_tag_t{}) {} - explicit HeapOrSoo(ctrl_t* c) : heap(c) {} - - ctrl_t*& control() { + MaybeInitializedPtr<ctrl_t>& control() { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control); } - ctrl_t* control() const { + MaybeInitializedPtr<ctrl_t> control() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control); } - MaybeInitializedPtr& slot_array() { + MaybeInitializedPtr<void>& slot_array() { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array); } - MaybeInitializedPtr slot_array() const { + MaybeInitializedPtr<void> slot_array() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array); } void* get_soo_data() { @@ -939,20 +939,13 @@ class CommonFields : public CommonFieldsGenerationInfo { public: explicit CommonFields(soo_tag_t) - : capacity_(SooCapacity()), - size_(no_seed_empty_tag_t{}), - heap_or_soo_(uninitialized_tag_t{}) {} + : capacity_(SooCapacity()), size_(no_seed_empty_tag_t{}) {} explicit CommonFields(full_soo_tag_t) - : capacity_(SooCapacity()), - size_(full_soo_tag_t{}), - heap_or_soo_(uninitialized_tag_t{}) {} + : capacity_(SooCapacity()), size_(full_soo_tag_t{}) {} explicit CommonFields(non_soo_tag_t) - : capacity_(0), - size_(no_seed_empty_tag_t{}), - heap_or_soo_(EmptyGroup()) {} + : capacity_(0), size_(no_seed_empty_tag_t{}) {} // For use in swapping. - explicit CommonFields(uninitialized_tag_t) - : size_(uninitialized_tag_t{}), heap_or_soo_(uninitialized_tag_t{}) {} + explicit CommonFields(uninitialized_tag_t) : size_(uninitialized_tag_t{}) {} // Not copyable CommonFields(const CommonFields&) = delete; @@ -979,7 +972,9 @@ const void* soo_data() const { return heap_or_soo_.get_soo_data(); } void* soo_data() { return heap_or_soo_.get_soo_data(); } - ctrl_t* control() const { return heap_or_soo_.control(); } + ctrl_t* control() const { + ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap_or_soo_.control().get()); + } // When we set the control bytes, we also often want to generate a new seed. // So we bundle these two operations together to make sure we don't forget to @@ -989,7 +984,7 @@ // being changed. In such cases, we will need to rehash the table. template <bool kGenerateSeed> void set_control(ctrl_t* c) { - heap_or_soo_.control() = c; + heap_or_soo_.control().set(c); if constexpr (kGenerateSeed) { generate_new_seed(); } @@ -1003,7 +998,9 @@ // Note: we can't use slots() because Qt defines "slots" as a macro. void* slot_array() const { return heap_or_soo_.slot_array().get(); } - MaybeInitializedPtr slots_union() const { return heap_or_soo_.slot_array(); } + MaybeInitializedPtr<void> slots_union() const { + return heap_or_soo_.slot_array(); + } void set_slots(void* s) { heap_or_soo_.slot_array().set(s); } // The number of filled slots. @@ -1049,6 +1046,7 @@ c > kAboveMaxValidCapacity); capacity_ = c; } + bool is_small() const { return IsSmallCapacity(capacity_); } // The number of slots we can still fill without needing to rehash. // This is stored in the heap allocation before the control bytes. @@ -1223,6 +1221,10 @@ // NormalizeCapacity(size). int leading_zeros = absl::countl_zero(size); constexpr size_t kLast3Bits = size_t{7} << (sizeof(size_t) * 8 - 3); + // max_size_for_next_capacity = max_load_factor * next_capacity + // = (7/8) * (~size_t{} >> leading_zeros) + // = (7/8*~size_t{}) >> leading_zeros + // = kLast3Bits >> leading_zeros size_t max_size_for_next_capacity = kLast3Bits >> leading_zeros; // Decrease shift if size is too big for the minimum capacity. leading_zeros -= static_cast<int>(size > max_size_for_next_capacity); @@ -1820,6 +1822,17 @@ void GrowFullSooTableToNextCapacityForceSampling(CommonFields& common, const PolicyFunctions& policy); +// Grows to next capacity and prepares insert for the given new_hash. +// Returns the offset of the new element. +size_t GrowToNextCapacityAndPrepareInsert(CommonFields& common, + const PolicyFunctions& policy, + size_t new_hash); +// When growing from capacity 0 to 1, we only need the hash if the table ends up +// being sampled so don't compute it unless needed. +void SmallEmptyNonSooPrepareInsert(CommonFields& common, + const PolicyFunctions& policy, + absl::FunctionRef<size_t()> get_hash); + // Resizes table with allocated slots and change the table seed. // Tables with SOO enabled must have capacity > policy.soo_capacity. // No sampling will be performed since table is already allocated. @@ -1948,6 +1961,8 @@ bool is_soo() const { return fits_in_soo(capacity()); } bool is_full_soo() const { return is_soo() && !empty(); } + bool is_small() const { return common().is_small(); } + // Give an early error when key_type is not hashable/eq. auto KeyTypeCanBeHashed(const Hash& h, const key_type& k) -> decltype(h(k)); auto KeyTypeCanBeEq(const Eq& eq, const key_type& k) -> decltype(eq(k, k)); @@ -2068,7 +2083,7 @@ // This constructor is used in begin() to avoid an MSan // use-of-uninitialized-value error. Delegating from this constructor to // the previous one doesn't avoid the error. - iterator(ctrl_t* ctrl, MaybeInitializedPtr slot, + iterator(ctrl_t* ctrl, MaybeInitializedPtr<void> slot, const GenerationType* generation_ptr) : HashSetIteratorGenerationInfo(generation_ptr), ctrl_(ctrl), @@ -2365,7 +2380,7 @@ iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND { if (ABSL_PREDICT_FALSE(empty())) return end(); - if (capacity() == 1) return single_iterator(); + if (is_small()) return single_iterator(); iterator it = {control(), common().slots_union(), common().generation_ptr()}; it.skip_empty_or_deleted(); @@ -2419,9 +2434,11 @@ const size_t cap = capacity(); if (cap == 0) { // Already guaranteed to be empty; so nothing to do. - } else if (is_soo()) { - if (!empty()) destroy(soo_slot()); - common().set_empty_soo(); + } else if (is_small()) { + if (!empty()) { + destroy(single_slot()); + decrement_small_size(); + } } else { destroy_slots(); clear_backing_array(/*reuse=*/cap < 128); @@ -2697,14 +2714,11 @@ // This overload is necessary because otherwise erase<K>(const K&) would be // a better match if non-const iterator is passed as an argument. void erase(iterator it) { + ABSL_SWISSTABLE_ASSERT(capacity() > 0); AssertNotDebugCapacity(); AssertIsFull(it.control(), it.generation(), it.generation_ptr(), "erase()"); destroy(it.slot()); - if (is_soo()) { - common().set_empty_soo(); - } else { - erase_meta_only(it); - } + erase_meta_only(it); } iterator erase(const_iterator first, @@ -2714,9 +2728,9 @@ // capacity() > 0 as a precondition. if (empty()) return end(); if (first == last) return last.inner_; - if (is_soo()) { - destroy(soo_slot()); - common().set_empty_soo(); + if (is_small()) { + destroy(single_slot()); + erase_meta_only(single_iterator()); return end(); } if (first == begin() && last == end()) { @@ -2748,9 +2762,10 @@ .second; }; - if (src.is_soo()) { + if (src.is_small()) { if (src.empty()) return; - if (insert_slot(src.soo_slot())) src.common().set_empty_soo(); + if (insert_slot(src.single_slot())) + src.erase_meta_only(src.single_iterator()); return; } for (auto it = src.begin(), e = src.end(); it != e;) { @@ -2771,11 +2786,7 @@ position.inner_.generation_ptr(), "extract()"); allocator_type alloc(char_alloc_ref()); auto node = CommonAccess::Transfer<node_type>(alloc, position.slot()); - if (is_soo()) { - common().set_empty_soo(); - } else { - erase_meta_only(position); - } + erase_meta_only(position); return node; } @@ -2851,7 +2862,7 @@ template <class K = key_type> iterator find(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND { AssertOnFind(key); - if (capacity() <= 1) return find_small(key); + if (is_small()) return find_small(key); prefetch_heap_block(); return find_large(key, hash_of(key)); } @@ -3031,18 +3042,16 @@ // SOO functionality. template <class K = key_type> iterator find_small(const key_arg<K>& key) { - ABSL_SWISSTABLE_ASSERT(capacity() <= 1); - return empty() || !PolicyTraits::apply( - EqualElement<K>{key, eq_ref()}, - PolicyTraits::element(single_slot())) + ABSL_SWISSTABLE_ASSERT(is_small()); + return empty() || !PolicyTraits::apply(EqualElement<K>{key, eq_ref()}, + PolicyTraits::element(single_slot())) ? end() : single_iterator(); } template <class K = key_type> iterator find_large(const key_arg<K>& key, size_t hash) { - ABSL_SWISSTABLE_ASSERT(capacity() > 1); - ABSL_SWISSTABLE_ASSERT(!is_soo()); + ABSL_SWISSTABLE_ASSERT(!is_small()); auto seq = probe(common(), hash); const h2_t h2 = H2(hash); const ctrl_t* ctrl = control(); @@ -3079,7 +3088,7 @@ } void destroy_slots() { - ABSL_SWISSTABLE_ASSERT(!is_soo()); + ABSL_SWISSTABLE_ASSERT(!is_small()); if (PolicyTraits::template destroy_is_trivial<Alloc>()) return; auto destroy_slot = [&](const ctrl_t*, void* slot) { this->destroy(static_cast<slot_type*>(slot)); @@ -3111,13 +3120,14 @@ return; } if (capacity() == 0) return; - if (is_soo()) { + if (is_small()) { if (!empty()) { - ABSL_SWISSTABLE_IGNORE_UNINITIALIZED(destroy(soo_slot())); + ABSL_SWISSTABLE_IGNORE_UNINITIALIZED(destroy(single_slot())); } - return; + if constexpr (SooEnabled()) return; + } else { + destroy_slots(); } - destroy_slots(); dealloc(); } @@ -3126,7 +3136,10 @@ // This merely updates the pertinent control byte. This can be used in // conjunction with Policy::transfer to move the object to another place. void erase_meta_only(const_iterator it) { - ABSL_SWISSTABLE_ASSERT(!is_soo()); + if (is_soo()) { + common().set_empty_soo(); + return; + } EraseMetaOnly(common(), static_cast<size_t>(it.control() - control()), sizeof(slot_type)); } @@ -3249,31 +3262,46 @@ } template <class K> - std::pair<iterator, bool> find_or_prepare_insert_soo(const K& key) { - ctrl_t soo_slot_ctrl; + std::pair<iterator, bool> find_or_prepare_insert_small(const K& key) { + ABSL_SWISSTABLE_ASSERT(is_small()); + [[maybe_unused]] ctrl_t soo_slot_ctrl; if (empty()) { + if (!SooEnabled()) { + SmallEmptyNonSooPrepareInsert(common(), GetPolicyFunctions(), + [&] { return hash_of(key); }); + return {single_iterator(), true}; + } if (!should_sample_soo()) { common().set_full_soo(); - return {soo_iterator(), true}; + return {single_iterator(), true}; } soo_slot_ctrl = ctrl_t::kEmpty; } else if (PolicyTraits::apply(EqualElement<K>{key, eq_ref()}, - PolicyTraits::element(soo_slot()))) { - return {soo_iterator(), false}; - } else { - soo_slot_ctrl = static_cast<ctrl_t>(H2(hash_of(soo_slot()))); + PolicyTraits::element(single_slot()))) { + return {single_iterator(), false}; + } else if constexpr (SooEnabled()) { + soo_slot_ctrl = static_cast<ctrl_t>(H2(hash_of(single_slot()))); } - constexpr bool kUseMemcpy = - PolicyTraits::transfer_uses_memcpy() && SooEnabled(); - size_t index = GrowSooTableToNextCapacityAndPrepareInsert< - kUseMemcpy ? OptimalMemcpySizeForSooSlotTransfer(sizeof(slot_type)) : 0, - kUseMemcpy>(common(), GetPolicyFunctions(), hash_of(key), - soo_slot_ctrl); + ABSL_SWISSTABLE_ASSERT(capacity() == 1); + const size_t hash = hash_of(key); + size_t index; + if constexpr (SooEnabled()) { + constexpr bool kUseMemcpy = + PolicyTraits::transfer_uses_memcpy() && SooEnabled(); + index = GrowSooTableToNextCapacityAndPrepareInsert< + kUseMemcpy ? OptimalMemcpySizeForSooSlotTransfer(sizeof(slot_type)) + : 0, + kUseMemcpy>(common(), GetPolicyFunctions(), hash, soo_slot_ctrl); + } else { + // TODO(b/413062340): add specialized function for growing from 1 to 3. + index = GrowToNextCapacityAndPrepareInsert(common(), GetPolicyFunctions(), + hash); + } return {iterator_at(index), true}; } template <class K> - std::pair<iterator, bool> find_or_prepare_insert_non_soo(const K& key) { + std::pair<iterator, bool> find_or_prepare_insert_large(const K& key) { ABSL_SWISSTABLE_ASSERT(!is_soo()); prefetch_heap_block(); const size_t hash = hash_of(key); @@ -3378,8 +3406,8 @@ "hash/eq functors are inconsistent."); }; - if (is_soo()) { - assert_consistent(/*unused*/ nullptr, soo_slot()); + if (is_small()) { + assert_consistent(/*unused*/ nullptr, single_slot()); return; } // We only do validation for small tables so that it's constant time. @@ -3393,8 +3421,8 @@ template <class K> std::pair<iterator, bool> find_or_prepare_insert(const K& key) { AssertOnFind(key); - if (is_soo()) return find_or_prepare_insert_soo(key); - return find_or_prepare_insert_non_soo(key); + if (is_small()) return find_or_prepare_insert_small(key); + return find_or_prepare_insert_large(key); } // Constructs the value in the space pointed by the iterator. This only works @@ -3409,9 +3437,9 @@ void emplace_at(iterator iter, Args&&... args) { construct(iter.slot(), std::forward<Args>(args)...); - // When capacity is 1, find calls find_small and if size is 0, then it will + // When is_small, find calls find_small and if size is 0, then it will // return an end iterator. This can happen in the raw_hash_set copy ctor. - assert((capacity() == 1 || + assert((is_small() || PolicyTraits::apply(FindElement{*this}, *iter) == iter) && "constructed value does not match the lookup key"); } @@ -3482,22 +3510,23 @@ ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN( const_cast<raw_hash_set*>(this)->soo_slot()); } - iterator soo_iterator() { - return {SooControl(), soo_slot(), common().generation_ptr()}; - } - const_iterator soo_iterator() const { - return const_cast<raw_hash_set*>(this)->soo_iterator(); - } slot_type* single_slot() { - ABSL_SWISSTABLE_ASSERT(capacity() <= 1); + ABSL_SWISSTABLE_ASSERT(is_small()); return SooEnabled() ? soo_slot() : slot_array(); } const slot_type* single_slot() const { return const_cast<raw_hash_set*>(this)->single_slot(); } + void decrement_small_size() { + ABSL_SWISSTABLE_ASSERT(is_small()); + SooEnabled() ? common().set_empty_soo() : common().decrement_size(); + if (!SooEnabled()) { + SanitizerPoisonObject(single_slot()); + growth_info().OverwriteFullAsEmpty(); + } + } iterator single_iterator() { - return {SooEnabled() ? SooControl() : control(), single_slot(), - common().generation_ptr()}; + return {SooControl(), single_slot(), common().generation_ptr()}; } const_iterator single_iterator() const { return const_cast<raw_hash_set*>(this)->single_iterator(); @@ -3642,15 +3671,15 @@ if (c->empty()) { return 0; } - if (c->is_soo()) { - auto it = c->soo_iterator(); + if (c->is_small()) { + auto it = c->single_iterator(); if (!pred(*it)) { ABSL_SWISSTABLE_ASSERT(c->size() == 1 && "hash table was modified unexpectedly"); return 0; } c->destroy(it.slot()); - c->common().set_empty_soo(); + c->erase_meta_only(it); return 1; } ABSL_ATTRIBUTE_UNUSED const size_t original_size_for_assert = c->size(); @@ -3680,8 +3709,8 @@ if (c->empty()) { return; } - if (c->is_soo()) { - cb(*c->soo_iterator()); + if (c->is_small()) { + cb(*c->single_iterator()); return; } using SlotType = typename Set::slot_type;
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 9a323c4..a5cbd44 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1283,6 +1283,9 @@ t.clear(); EXPECT_FALSE(t.contains(0)); + + EXPECT_TRUE(t.insert(0).second); + EXPECT_TRUE(t.contains(0)); } int decompose_constructed; @@ -2083,8 +2086,6 @@ TEST(Table, GrowthInfoDeletedBit) { BadTable t; - EXPECT_TRUE( - RawHashSetTestOnlyAccess::GetCommon(t).growth_info().HasNoDeleted()); int64_t init_count = static_cast<int64_t>( CapacityToGrowth(NormalizeCapacity(Group::kWidth + 1))); for (int64_t i = 0; i < init_count; ++i) { @@ -2604,6 +2605,19 @@ EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0"))); } +TEST(Table, MergeSmall) { + StringTable t1, t2; + t1.emplace("1", "1"); + t2.emplace("2", "2"); + + EXPECT_THAT(t1, UnorderedElementsAre(Pair("1", "1"))); + EXPECT_THAT(t2, UnorderedElementsAre(Pair("2", "2"))); + + t2.merge(t1); + EXPECT_EQ(t1.size(), 0); + EXPECT_THAT(t2, UnorderedElementsAre(Pair("1", "1"), Pair("2", "2"))); +} + TEST(Table, IteratorEmplaceConstructibleRequirement) { struct Value { explicit Value(absl::string_view view) : value(view) {} @@ -2690,6 +2704,24 @@ EXPECT_FALSE(node); // NOLINT(bugprone-use-after-move) } +TEST(Nodes, ExtractInsertSmall) { + constexpr char k0[] = "Very long string zero."; + StringTable t = {{k0, ""}}; + EXPECT_THAT(t, UnorderedElementsAre(Pair(k0, ""))); + + auto node = t.extract(k0); + EXPECT_EQ(t.size(), 0); + EXPECT_TRUE(node); + EXPECT_FALSE(node.empty()); + + StringTable t2; + StringTable::insert_return_type res = t2.insert(std::move(node)); + EXPECT_TRUE(res.inserted); + EXPECT_THAT(*res.position, Pair(k0, "")); + EXPECT_FALSE(res.node); + EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, ""))); +} + TYPED_TEST(SooTest, HintInsert) { TypeParam t = {1, 2, 3}; auto node = t.extract(1); @@ -2828,12 +2860,12 @@ NonSooIntTable t; // Extra simple "regexp" as regexp support is highly varied across platforms. - EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), - "erase.* called on end.. iterator."); + EXPECT_DEATH_IF_SUPPORTED(++t.end(), "operator.* called on end.. iterator."); typename NonSooIntTable::iterator iter; EXPECT_DEATH_IF_SUPPORTED( ++iter, "operator.* called on default-constructed iterator."); t.insert(0); + t.insert(1); iter = t.begin(); t.erase(iter); const char* const kErasedDeathMessage = @@ -3644,11 +3676,13 @@ EXPECT_DEATH_IF_SUPPORTED(void(t1.end() == default_constructed_iter), "Invalid iterator comparison.*default-constructed"); t1.insert(0); + t1.insert(1); EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.end()), "Invalid iterator comparison.*empty hashtable"); EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == default_constructed_iter), "Invalid iterator comparison.*default-constructed"); t2.insert(0); + t2.insert(1); EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.end()), "Invalid iterator comparison.*end.. iterator"); EXPECT_DEATH_IF_SUPPORTED(void(t1.begin() == t2.begin()), @@ -3687,40 +3721,47 @@ GTEST_SKIP() << "Only run under NDEBUG: `assert` statements may cause " "redundant hashing."; } + // When the table is sampled, we need to hash on the first insertion. + DisableSampling(); using Table = CountedHashIntTable; auto HashCount = [](const Table& t) { return t.hash_function().count; }; { Table t; + t.find(0); EXPECT_EQ(HashCount(t), 0); } { Table t; t.insert(1); - EXPECT_EQ(HashCount(t), 1); + t.find(1); + EXPECT_EQ(HashCount(t), 0); t.erase(1); - EXPECT_LE(HashCount(t), 2); + EXPECT_EQ(HashCount(t), 0); + t.insert(1); + t.insert(2); + EXPECT_EQ(HashCount(t), 2); } { Table t; t.insert(3); - EXPECT_EQ(HashCount(t), 1); + EXPECT_EQ(HashCount(t), 0); auto node = t.extract(3); - EXPECT_LE(HashCount(t), 2); + EXPECT_EQ(HashCount(t), 0); t.insert(std::move(node)); - EXPECT_LE(HashCount(t), 3); + EXPECT_EQ(HashCount(t), 0); } { Table t; t.emplace(5); - EXPECT_EQ(HashCount(t), 1); + EXPECT_EQ(HashCount(t), 0); } { Table src; src.insert(7); Table dst; dst.merge(src); - EXPECT_EQ(HashCount(dst), 1); + EXPECT_EQ(HashCount(dst), 0); } } @@ -3731,9 +3772,7 @@ auto fail_if_any = [](const ctrl_t*, void* i) { FAIL() << "expected no slots " << **static_cast<SlotType*>(i); }; - container_internal::IterateOverFullSlots( - RawHashSetTestOnlyAccess::GetCommon(t), sizeof(SlotType), fail_if_any); - for (size_t i = 0; i < 256; ++i) { + for (size_t i = 2; i < 256; ++i) { t.reserve(i); container_internal::IterateOverFullSlots( RawHashSetTestOnlyAccess::GetCommon(t), sizeof(SlotType), fail_if_any); @@ -3745,7 +3784,9 @@ using SlotType = NonSooIntTableSlotType; std::vector<int64_t> expected_slots; - for (int64_t idx = 0; idx < 128; ++idx) { + t.insert(0); + expected_slots.push_back(0); + for (int64_t idx = 1; idx < 128; ++idx) { t.insert(idx); expected_slots.push_back(idx);
diff --git a/absl/debugging/internal/stacktrace_x86-inl.inc b/absl/debugging/internal/stacktrace_x86-inl.inc index 96b128e..bf6e5ab 100644 --- a/absl/debugging/internal/stacktrace_x86-inl.inc +++ b/absl/debugging/internal/stacktrace_x86-inl.inc
@@ -261,17 +261,18 @@ // it's supposed to. if (STRICT_UNWINDING && (!WITH_CONTEXT || uc == nullptr || new_fp_u != GetFP(uc))) { - // With the stack growing downwards, older stack frame must be - // at a greater address that the current one. - if (new_fp_u <= old_fp_u) return nullptr; - + // With the stack growing downwards, older stack frame should be + // at a greater address that the current one. However if we get multiple + // signals handled on altstack the new frame pointer might return to the + // main stack, but be different than the value from the most recent + // ucontext. // If we get a very large frame size, it may be an indication that we // guessed frame pointers incorrectly and now risk a paging fault // dereferencing a wrong frame pointer. Or maybe not because large frames // are possible as well. The main stack is assumed to be readable, // so we assume the large frame is legit if we know the real stack bounds // and are within the stack. - if (new_fp_u - old_fp_u > kMaxFrameBytes) { + if (new_fp_u <= old_fp_u || new_fp_u - old_fp_u > kMaxFrameBytes) { if (stack_high < kUnknownStackEnd && static_cast<size_t>(getpagesize()) < stack_low) { // Stack bounds are known.
diff --git a/absl/debugging/stacktrace_test.cc b/absl/debugging/stacktrace_test.cc index 4477d84..e5565c1 100644 --- a/absl/debugging/stacktrace_test.cc +++ b/absl/debugging/stacktrace_test.cc
@@ -18,6 +18,9 @@ #include <stdint.h> #include <algorithm> +#include <cerrno> +#include <csignal> +#include <cstring> #include "gmock/gmock.h" #include "gtest/gtest.h" @@ -295,4 +298,74 @@ } #endif +// This test is Linux specific. +#if defined(__linux__) +const void* g_return_address = nullptr; +bool g_sigusr2_raised = false; + +void SigUsr2Handler(int, siginfo_t*, void* uc) { + // Many platforms don't support this by default. + bool support_is_expected = false; + constexpr int kMaxStackDepth = 64; + void* result[kMaxStackDepth]; + int depth = + absl::GetStackTraceWithContext(result, kMaxStackDepth, 0, uc, nullptr); + // Verify we can unwind past the nested signal handlers. + if (support_is_expected) { + EXPECT_THAT(absl::MakeSpan(result, static_cast<size_t>(depth)), + Contains(g_return_address).Times(1)); + } + depth = absl::GetStackTrace(result, kMaxStackDepth, 0); + if (support_is_expected) { + EXPECT_THAT(absl::MakeSpan(result, static_cast<size_t>(depth)), + Contains(g_return_address).Times(1)); + } + g_sigusr2_raised = true; +} + +void SigUsr1Handler(int, siginfo_t*, void*) { + raise(SIGUSR2); + ABSL_BLOCK_TAIL_CALL_OPTIMIZATION(); +} + +ABSL_ATTRIBUTE_NOINLINE void RaiseSignal() { + g_return_address = __builtin_return_address(0); + raise(SIGUSR1); + ABSL_BLOCK_TAIL_CALL_OPTIMIZATION(); +} + +ABSL_ATTRIBUTE_NOINLINE void TestNestedSignal() { + constexpr size_t kAltstackSize = 1 << 14; + // Allocate altstack on regular stack to make sure it'll have a higher + // address than some of the regular stack frames. + char space[kAltstackSize]; + stack_t altstack; + stack_t old_stack; + altstack.ss_sp = space; + altstack.ss_size = kAltstackSize; + altstack.ss_flags = 0; + ASSERT_EQ(sigaltstack(&altstack, &old_stack), 0) << strerror(errno); + struct sigaction act; + struct sigaction oldusr1act; + struct sigaction oldusr2act; + act.sa_sigaction = SigUsr1Handler; + act.sa_flags = SA_SIGINFO | SA_ONSTACK; + sigemptyset(&act.sa_mask); + ASSERT_EQ(sigaction(SIGUSR1, &act, &oldusr1act), 0) << strerror(errno); + act.sa_sigaction = SigUsr2Handler; + ASSERT_EQ(sigaction(SIGUSR2, &act, &oldusr2act), 0) << strerror(errno); + RaiseSignal(); + ASSERT_EQ(sigaltstack(&old_stack, nullptr), 0) << strerror(errno); + ASSERT_EQ(sigaction(SIGUSR1, &oldusr1act, nullptr), 0) << strerror(errno); + ASSERT_EQ(sigaction(SIGUSR2, &oldusr2act, nullptr), 0) << strerror(errno); + ABSL_BLOCK_TAIL_CALL_OPTIMIZATION(); +} + +TEST(StackTrace, NestedSignal) { + // Verify we can unwind past the nested signal handlers. + TestNestedSignal(); + EXPECT_TRUE(g_sigusr2_raised); +} +#endif + } // namespace