Export of internal Abseil changes

--
a5af5874c1c5cc02bd2a748d455321f82b6f2a93 by Andy Getzendanner <durandal@google.com>:

fix compile fails with asan and -Wredundant-decls

Import of https://github.com/abseil/abseil-cpp/pull/801

PiperOrigin-RevId: 336693223

--
ed9df42ab2b742386c6692c2bed015374c919d9c by Derek Mauro <dmauro@google.com>:

Fix integer conversion warning

Fixes #814

PiperOrigin-RevId: 336651814

--
0ab4c23884e72dce17b67c1eb520f9dbb802565d by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 336585378

--
eba0e3dccd52a6e91bcff84075bef0affc650b74 by Matt Kulukundis <kfm@google.com>:

Add bitset operations to Futex helper.

PiperOrigin-RevId: 336409368

--
8b0709a8b4500bf5f0af4b602d76a298d81645e8 by Abseil Team <absl-team@google.com>:

Fix code indentation in a comment.

PiperOrigin-RevId: 336368167

--
bc3961c87a7e7760c10319a5b0349c279f7ae3ad by Samuel Benzaquen <sbenza@google.com>:

Improve performance of the registry:
 - Reduce contention
 - Reduce memory usage for each flag by `6*sizeof(void*)`.
 - Replace one immortal allocation per-flag with a single one for all the flags
 - Slightly improve single-threaded performance by avoiding the std::map indirections.

PiperOrigin-RevId: 336365904

--
264ad9f28f935aad8b6b1437f8bf804fa9104346 by Abseil Team <absl-team@google.com>:

Fix typo in comment on absl::Condition.

PiperOrigin-RevId: 336311680

--
b5b808a8c75ca0df7b09eff9a423ec171d80f771 by Derek Mauro <dmauro@google.com>:

Add missing Apache license headers

PiperOrigin-RevId: 336294980

--
89446c3a4793df8b95060385cf3e219357c3db1d by Andy Soffer <asoffer@google.com>:

Internal changes

PiperOrigin-RevId: 336287465

--
57c8be4e294881bc79a6a44b8e4bf7ecbb19b9b9 by Matt Kulukundis <kfm@google.com>:

Extract Futex from an implementation detail of Wait to a private interface.

PiperOrigin-RevId: 336123209
GitOrigin-RevId: a5af5874c1c5cc02bd2a748d455321f82b6f2a93
Change-Id: Ie5a0ebe28e571814e3e11d4c05ca308523ccf311

7 files changed, 158 insertions, 75 deletions

diff --git a/absl/synchronization/BUILD.bazel b/absl/synchronization/BUILD.bazel
index b2df4131..cd4009a1 100644
--- a/absl/synchronization/BUILD.bazel
+++ b/absl/synchronization/BUILD.bazel
@@ -80,6 +80,7 @@ cc_library(
         "barrier.h",
         "blocking_counter.h",
         "internal/create_thread_identity.h",
+        "internal/futex.h",
         "internal/per_thread_sem.h",
         "internal/waiter.h",
         "mutex.h",
diff --git a/absl/synchronization/CMakeLists.txt b/absl/synchronization/CMakeLists.txt
index c255b03e..e633d0bf 100644
--- a/absl/synchronization/CMakeLists.txt
+++ b/absl/synchronization/CMakeLists.txt
@@ -52,6 +52,7 @@ absl_cc_library(
     "barrier.h"
     "blocking_counter.h"
     "internal/create_thread_identity.h"
+    "internal/futex.h"
     "internal/per_thread_sem.h"
     "internal/waiter.h"
     "mutex.h"
diff --git a/absl/synchronization/internal/futex.h b/absl/synchronization/internal/futex.h
new file mode 100644
index 00000000..3539f491
--- /dev/null
+++ b/absl/synchronization/internal/futex.h
@@ -0,0 +1,139 @@
+// Copyright 2020 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+#ifndef ABSL_SYNCHRONIZATION_INTERNAL_FUTEX_H_
+#define ABSL_SYNCHRONIZATION_INTERNAL_FUTEX_H_
+
+#include "absl/base/config.h"
+
+#ifdef _WIN32
+#include <windows.h>
+#else
+#include <sys/time.h>
+#include <unistd.h>
+#endif
+
+#ifdef __linux__
+#include <linux/futex.h>
+#include <sys/syscall.h>
+#endif
+
+#include <errno.h>
+#include <stdio.h>
+#include <time.h>
+
+#include <atomic>
+#include <cstdint>
+
+#include "absl/base/optimization.h"
+#include "absl/synchronization/internal/kernel_timeout.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace synchronization_internal {
+
+// Some Android headers are missing these definitions even though they
+// support these futex operations.
+#ifdef __BIONIC__
+#ifndef SYS_futex
+#define SYS_futex __NR_futex
+#endif
+#ifndef FUTEX_WAIT_BITSET
+#define FUTEX_WAIT_BITSET 9
+#endif
+#ifndef FUTEX_PRIVATE_FLAG
+#define FUTEX_PRIVATE_FLAG 128
+#endif
+#ifndef FUTEX_CLOCK_REALTIME
+#define FUTEX_CLOCK_REALTIME 256
+#endif
+#ifndef FUTEX_BITSET_MATCH_ANY
+#define FUTEX_BITSET_MATCH_ANY 0xFFFFFFFF
+#endif
+#endif
+
+#if defined(__NR_futex_time64) && !defined(SYS_futex_time64)
+#define SYS_futex_time64 __NR_futex_time64
+#endif
+
+#if defined(SYS_futex_time64) && !defined(SYS_futex)
+#define SYS_futex SYS_futex_time64
+#endif
+
+class FutexImpl {
+ public:
+  static int WaitUntil(std::atomic<int32_t> *v, int32_t val,
+                       KernelTimeout t) {
+    int err = 0;
+    if (t.has_timeout()) {
+      // https://locklessinc.com/articles/futex_cheat_sheet/
+      // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET uses absolute time.
+      struct timespec abs_timeout = t.MakeAbsTimespec();
+      // Atomically check that the futex value is still 0, and if it
+      // is, sleep until abs_timeout or until woken by FUTEX_WAKE.
+      err = syscall(
+          SYS_futex, reinterpret_cast<int32_t *>(v),
+          FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG | FUTEX_CLOCK_REALTIME, val,
+          &abs_timeout, nullptr, FUTEX_BITSET_MATCH_ANY);
+    } else {
+      // Atomically check that the futex value is still 0, and if it
+      // is, sleep until woken by FUTEX_WAKE.
+      err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
+                    FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, nullptr);
+    }
+    if (ABSL_PREDICT_FALSE(err != 0)) {
+      err = -errno;
+    }
+    return err;
+  }
+
+  static int WaitBitsetAbsoluteTimeout(std::atomic<int32_t> *v, int32_t val,
+                                       int32_t bits,
+                                       const struct timespec *abstime) {
+    int err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
+                      FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG, val, abstime,
+                      nullptr, bits);
+    if (ABSL_PREDICT_FALSE(err != 0)) {
+      err = -errno;
+    }
+    return err;
+  }
+
+  static int Wake(std::atomic<int32_t> *v, int32_t count) {
+    int err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
+                      FUTEX_WAKE | FUTEX_PRIVATE_FLAG, count);
+    if (ABSL_PREDICT_FALSE(err < 0)) {
+      err = -errno;
+    }
+    return err;
+  }
+
+  // FUTEX_WAKE_BITSET
+  static int WakeBitset(std::atomic<int32_t> *v, int32_t count, int32_t bits) {
+    int err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
+                      FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, count, nullptr,
+                      nullptr, bits);
+    if (ABSL_PREDICT_FALSE(err < 0)) {
+      err = -errno;
+    }
+    return err;
+  }
+};
+
+class Futex : public FutexImpl {};
+
+}  // namespace synchronization_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_SYNCHRONIZATION_INTERNAL_FUTEX_H_
diff --git a/absl/synchronization/internal/kernel_timeout.h b/absl/synchronization/internal/kernel_timeout.h
index 1084e1e6..bbd4d2d7 100644
--- a/absl/synchronization/internal/kernel_timeout.h
+++ b/absl/synchronization/internal/kernel_timeout.h
@@ -26,6 +26,7 @@
 #define ABSL_SYNCHRONIZATION_INTERNAL_KERNEL_TIMEOUT_H_
 
 #include <time.h>
+
 #include <algorithm>
 #include <limits>
 
@@ -142,7 +143,7 @@ inline struct timespec KernelTimeout::MakeAbsTimespec() {
 
   struct timespec abstime;
   int64_t seconds = (std::min)(n / kNanosPerSecond,
-                             int64_t{(std::numeric_limits<time_t>::max)()});
+                               int64_t{(std::numeric_limits<time_t>::max)()});
   abstime.tv_sec = static_cast<time_t>(seconds);
   abstime.tv_nsec = static_cast<decltype(abstime.tv_nsec)>(n % kNanosPerSecond);
   return abstime;
diff --git a/absl/synchronization/internal/waiter.cc b/absl/synchronization/internal/waiter.cc
index b6150b9b..c51855b0 100644
--- a/absl/synchronization/internal/waiter.cc
+++ b/absl/synchronization/internal/waiter.cc
@@ -48,6 +48,11 @@
 #include "absl/base/optimization.h"
 #include "absl/synchronization/internal/kernel_timeout.h"
 
+#if ABSL_WAITER_MODE == ABSL_WAITER_MODE_FUTEX
+#include "absl/synchronization/internal/futex.h"
+#endif
+
+
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace synchronization_internal {
@@ -66,71 +71,6 @@ static void MaybeBecomeIdle() {
 
 #if ABSL_WAITER_MODE == ABSL_WAITER_MODE_FUTEX
 
-// Some Android headers are missing these definitions even though they
-// support these futex operations.
-#ifdef __BIONIC__
-#ifndef SYS_futex
-#define SYS_futex __NR_futex
-#endif
-#ifndef FUTEX_WAIT_BITSET
-#define FUTEX_WAIT_BITSET 9
-#endif
-#ifndef FUTEX_PRIVATE_FLAG
-#define FUTEX_PRIVATE_FLAG 128
-#endif
-#ifndef FUTEX_CLOCK_REALTIME
-#define FUTEX_CLOCK_REALTIME 256
-#endif
-#ifndef FUTEX_BITSET_MATCH_ANY
-#define FUTEX_BITSET_MATCH_ANY 0xFFFFFFFF
-#endif
-#endif
-
-#if defined(__NR_futex_time64) && !defined(SYS_futex_time64)
-#define SYS_futex_time64 __NR_futex_time64
-#endif
-
-#if defined(SYS_futex_time64) && !defined(SYS_futex)
-#define SYS_futex SYS_futex_time64
-#endif
-
-class Futex {
- public:
-  static int WaitUntil(std::atomic<int32_t> *v, int32_t val,
-                       KernelTimeout t) {
-    int err = 0;
-    if (t.has_timeout()) {
-      // https://locklessinc.com/articles/futex_cheat_sheet/
-      // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET uses absolute time.
-      struct timespec abs_timeout = t.MakeAbsTimespec();
-      // Atomically check that the futex value is still 0, and if it
-      // is, sleep until abs_timeout or until woken by FUTEX_WAKE.
-      err = syscall(
-          SYS_futex, reinterpret_cast<int32_t *>(v),
-          FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG | FUTEX_CLOCK_REALTIME, val,
-          &abs_timeout, nullptr, FUTEX_BITSET_MATCH_ANY);
-    } else {
-      // Atomically check that the futex value is still 0, and if it
-      // is, sleep until woken by FUTEX_WAKE.
-      err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
-                    FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, nullptr);
-    }
-    if (err != 0) {
-      err = -errno;
-    }
-    return err;
-  }
-
-  static int Wake(std::atomic<int32_t> *v, int32_t count) {
-    int err = syscall(SYS_futex, reinterpret_cast<int32_t *>(v),
-                      FUTEX_WAKE | FUTEX_PRIVATE_FLAG, count);
-    if (ABSL_PREDICT_FALSE(err < 0)) {
-      err = -errno;
-    }
-    return err;
-  }
-};
-
 Waiter::Waiter() {
   futex_.store(0, std::memory_order_relaxed);
 }
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc
index 9b7f088a..63f09408 100644
--- a/absl/synchronization/mutex.cc
+++ b/absl/synchronization/mutex.cc
@@ -88,8 +88,8 @@ ABSL_CONST_INIT std::atomic<OnDeadlockCycle> synch_deadlock_detection(
 ABSL_CONST_INIT std::atomic<bool> synch_check_invariants(false);
 
 ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES
-    absl::base_internal::AtomicHook<void (*)(int64_t wait_cycles)>
-        submit_profile_data;
+absl::base_internal::AtomicHook<void (*)(int64_t wait_cycles)>
+    submit_profile_data;
 ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES absl::base_internal::AtomicHook<void (*)(
     const char *msg, const void *obj, int64_t wait_cycles)>
     mutex_tracer;
@@ -491,7 +491,7 @@ struct SynchWaitParams {
   std::atomic<intptr_t> *cv_word;
 
   int64_t contention_start_cycles;  // Time (in cycles) when this thread started
-                                  // to contend for the mutex.
+                                    // to contend for the mutex.
 };
 
 struct SynchLocksHeld {
@@ -2311,7 +2311,8 @@ ABSL_ATTRIBUTE_NOINLINE void Mutex::UnlockSlow(SynchWaitParams *waitp) {
     if (!cond_waiter) {
       // Sample lock contention events only if the (first) waiter was trying to
       // acquire the lock, not waiting on a condition variable or Condition.
-      int64_t wait_cycles = base_internal::CycleClock::Now() - enqueue_timestamp;
+      int64_t wait_cycles =
+          base_internal::CycleClock::Now() - enqueue_timestamp;
       mutex_tracer("slow release", this, wait_cycles);
       ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0);
       submit_profile_data(enqueue_timestamp);
diff --git a/absl/synchronization/mutex.h b/absl/synchronization/mutex.h
index 6340bd63..f686c4df 100644
--- a/absl/synchronization/mutex.h
+++ b/absl/synchronization/mutex.h
@@ -667,10 +667,10 @@ class Condition {
   //   };
   //   mu_.Await(Condition(&reached));
   //
-  // NOTE: never use "mu_.AssertHeld()" instead of "mu_.AssertReadHeld()" in the
-  // lambda as it may be called when the mutex is being unlocked from a scope
-  // holding only a reader lock, which will make the assertion not fulfilled and
-  // crash the binary.
+  // NOTE: never use "mu_.AssertHeld()" instead of "mu_.AssertReaderHeld()" in
+  // the lambda as it may be called when the mutex is being unlocked from a
+  // scope holding only a reader lock, which will make the assertion not
+  // fulfilled and crash the binary.
 
   // See class comment for performance advice. In particular, if there
   // might be more than one waiter for the same condition, make sure
@@ -954,7 +954,7 @@ void RegisterMutexProfiler(void (*fn)(int64_t wait_timestamp));
 //
 // This has the same memory ordering concerns as RegisterMutexProfiler() above.
 void RegisterMutexTracer(void (*fn)(const char *msg, const void *obj,
-                              int64_t wait_cycles));
+                                    int64_t wait_cycles));
 
 // TODO(gfalcon): Combine RegisterMutexProfiler() and RegisterMutexTracer()
 // into a single interface, since they are only ever called in pairs.