Skip to content

A
abseil-cpp
Switch branch/tag
  1. 31 May, 2022 4 commits
    • Allow for using b-tree with `value_type`s that can only be constructed by the… · aeb2dc9c 
      Allow for using b-tree with `value_type`s that can only be constructed by the allocator (ignoring copy/move constructors).

We were using `init_type`s for temp values that we would move into slots, but in this case, we need to have actual slots. We use node handles for managing slots outside of nodes.

Also, in btree::copy_or_move_values_in_order, pass the slots from the iterators rather than references to values. This allows for moving from map keys instead of copying for standard layout types.

In the test, fix a couple of ClangTidy warnings from missing includes and calling `new` instead of `make_unique`.

PiperOrigin-RevId: 452062967
Change-Id: I870e89ae1aa5b3cfa62ae6e75b73ffc3d52e731c
      Evan Brown committed
    • Stop using sleep timeouts for Linux futex-based SpinLock · a4cc270d 
      Timeouts were once necessary when the SpinLock Unlock used an atomic
store and could therefore have a race and a missed wakeup, however,
the Unlock path now uses an atomic exchange, so the missed wakeup
cannot happen.

Fixes #1179

PiperOrigin-RevId: 452047517
Change-Id: I844944879b51b7f7ddac148e063a376cddd0d05a
      Derek Mauro committed
    • Automated rollback of commit f2463433. · ea78ded7 
      PiperOrigin-RevId: 451979149
Change-Id: Ic9b02306f2c5324b6648989a895f128c9eb5743d
      Abseil Team committed
    • time.h: Use uint32_t literals for calls to overloaded MakeDuration · f2463433 
      This fixes an overload that is ambiguous for some toolchains, because
0U does not always refer to a uint32_t (on some toolchains, uint32_t
is an unsigned long).

PiperOrigin-RevId: 451962182
Change-Id: Id13700817ea3eb6d04e2cc02f20726040eb447fb
      Anqi D committed
  3. 27 May, 2022 2 commits
  5. 26 May, 2022 3 commits
    • Enable __thread on Asylo · 89cdaed6 
      PiperOrigin-RevId: 451201387
Change-Id: Ibeac4f24d00e28bbfc61e476936d669321a2cb24
      Abseil Team committed
    • Add implementation of is_invocable_r to absl::base_internal for C++ < 17, define… · 0bc4bc23 
      Add implementation of is_invocable_r to absl::base_internal for C++ < 17, define it as alias of std::is_invocable_r when C++ >= 17

PiperOrigin-RevId: 451171660
Change-Id: I6dc0e40eabac72b82c4a19e292158e43118cb080
      Dino Radakovic committed
    • Optimize SwissMap iteration for aarch64 by 5-6% · 591a2cda 
      Benchmarks: https://pastebin.com/tZ7dr67W. Works well especially on smaller ranges.

After a week on spending optimizing NEON SIMD where I almost managed to make hash tables work with NEON SIMD without performance hits (still 1 cycle to optimize and I gave up a little), I found an interesting optimization for aarch64 to use cls instruction (count leading sign bits).

The loop has a property that ctrl_ group is not matched against count when the first slot is empty or deleted.

```
void skip_empty_or_deleted() {
      while (IsEmptyOrDeleted(*ctrl_)) {
        uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted();
        ctrl_ += shift;
        slot_ += shift;
      }
      ...
}
```

However, `kEmpty` and `kDeleted` have format of `1xxxxxx0` and `~ctrl & (ctrl >> 7)` always sets the lowest bit to 1.

In naive implementation, it does +1 to start counting zero bits, however, in aarch64 we may start counting one bits immediately. This saves 1 cycle and 5% of iteration performance.

Then it becomes hard to find a supported and sustainable C++ version of it.

`__clsll` is not supported by GCC and was supported only since clang 8, `__builtin_clrsb` is not producing optimal codegen for clang. `__rbit` is not supported by GCC and there is no intrinsic to do that, however, in clang we have `__builtin_bitreverse{32,64}`. For now I decided to enable this only for clang, only if they have appropriate builtins.

PiperOrigin-RevId: 451168570
Change-Id: I7e9256a60aecdc88ced4e6eb15ebc257281b6664
      Abseil Team committed
  7. 25 May, 2022 1 commit
  9. 24 May, 2022 1 commit
  11. 23 May, 2022 2 commits
  13. 20 May, 2022 3 commits
  15. 18 May, 2022 3 commits
  17. 17 May, 2022 4 commits
    • Use NullSafeStringView for const char* args to absl::StrCat, treating null pointers as "" · e92505d8 
      Fixes #1167

PiperOrigin-RevId: 449328725
Change-Id: I813785db77b94efa49eeeff4c93449334c380935
      Dino Radakovic committed
    • raw_logging: Extract the inlined no-hook-registered behavior for LogPrefixHook… · 7d3b4c86 
      raw_logging: Extract the inlined no-hook-registered behavior for LogPrefixHook to a default implementation.

PiperOrigin-RevId: 449306617
Change-Id: Ia3e87d2edcae7e9874998f21a0e2ff245e48fd96
      Andy Getzendanner committed
    • absl: fix use-after-free in Mutex/CondVar · 9444b11e 
      Both Mutex and CondVar signal PerThreadSem/Waiter after satisfying the wait condition,
as the result the waiting thread may return w/o waiting on the
PerThreadSem/Waiter at all. If the waiting thread then exits, it currently
destroys Waiter object. As the result Waiter::Post can be called on
already destroyed object.
PerThreadSem/Waiter must be type-stable after creation and must not be destroyed.
The futex-based implementation is the only one that is not affected by the bug
since there is effectively nothing to destroy (maybe only UBSan/ASan
could complain about calling methods on a destroyed object).

Here is the problematic sequence of events:

1: void Mutex::Block(PerThreadSynch *s) {
2:   while (s->state.load(std::memory_order_acquire) == PerThreadSynch::kQueued) {
3:     if (!DecrementSynchSem(this, s, s->waitp->timeout)) {

4: PerThreadSynch *Mutex::Wakeup(PerThreadSynch *w) {
5:   ...
6:   w->state.store(PerThreadSynch::kAvailable, std::memory_order_release);
7:   IncrementSynchSem(this, w);
8:   ...
9: }

Consider line 6 is executed, then line 2 observes kAvailable and
line 3 is not called. The thread executing Mutex::Block returns from
the method, acquires the mutex, releases the mutex, exits and destroys
PerThreadSem/Waiter.
Now Mutex::Wakeup resumes and executes line 7 on the destroyed object. Boom!

CondVar uses a similar pattern.

Moreover the semaphore-based Waiter implementation is not even destruction-safe
(the Waiter cannot be used to signal own destruction). So even if Mutex/CondVar
would always pair Waiter::Post with Waiter::Wait before destroying PerThreadSem/Waiter,
it would still be subject to use-after-free bug on the semaphore.

PiperOrigin-RevId: 449159939
Change-Id: I497134fa8b6ce1294a422827c5f0de0e897cea31
      Abseil Team committed
    • absl: fix live-lock in CondVar · aac2279f 
      CondVar::WaitWithTimeout can live-lock when timeout is racing with Signal/SignalAll
and Signal/SignalAll thread is not scheduled due to priorities, affinity or other
scheduler artifacts. This could lead to stalls of up to tens of seconds in some cases.
PiperOrigin-RevId: 449159670
Change-Id: I64bbd277c1f91964cfba3306ba8a80eeadf85f64
      Abseil Team committed
  19. 16 May, 2022 1 commit
  21. 13 May, 2022 1 commit
  23. 12 May, 2022 3 commits
  25. 11 May, 2022 1 commit
  27. 10 May, 2022 1 commit
  29. 05 May, 2022 2 commits
  31. 04 May, 2022 4 commits
  33. 03 May, 2022 2 commits
  35. 02 May, 2022 1 commit
  37. 29 Apr, 2022 1 commit