Export of internal Abseil changes

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

Documentation: don't define absl::Status::ok() in terms of itself

Fixes #1058

PiperOrigin-RevId: 410035651

--
31c512c834b3a8979297adc5006c3727a3c6554b by Evan Brown <ezb@google.com>:

Cleanup: move set_params/set_slot_policy into btree_set.h and move map_params into btree_map.h.

Also change some `sizeof(value_type)`s to `sizeof(slot_type)`s and update some comments/variable names referring to values to refer to slots as appropriate in btree.h.

Motivation: preliminary cleanup towards node_btree_*.
PiperOrigin-RevId: 409991342

--
3129ca320d61a82f1c9ee8c02a23d25024eea4ab by Abseil Team <absl-team@google.com>:

Use simpler implementation for AddressIsReadable.

In particular, current solution doesn't work on systems configured with large
pid_t space.

PiperOrigin-RevId: 409397716

--
f71067f7494b19ce4a2e1df730b934dc931c51b2 by Martijn Vels <mvels@google.com>:

Add Span dependency

PiperOrigin-RevId: 409198889
GitOrigin-RevId: 355b8f7b0070b005d53d94ee4180e95559ba2c88
Change-Id: I7f4df3ec7739fdfde61d8ba983f07a08f6f1c7d7

7 files changed, 195 insertions, 195 deletions

diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h
index 96ebcb77..4eafe062 100644
--- a/absl/container/btree_map.h
+++ b/absl/container/btree_map.h
@@ -56,6 +56,14 @@
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 
+namespace container_internal {
+
+template <typename Key, typename Data, typename Compare, typename Alloc,
+          int TargetNodeSize, bool Multi>
+struct map_params;
+
+}  // namespace container_internal
+
 // absl::btree_map<>
 //
 // An `absl::btree_map<K, V>` is an ordered associative container of
@@ -812,6 +820,58 @@ void erase_if(btree_multimap<K, V, C, A> &map, Pred pred) {
   }
 }
 
+namespace container_internal {
+
+// A parameters structure for holding the type parameters for a btree_map.
+// Compare and Alloc should be nothrow copy-constructible.
+template <typename Key, typename Data, typename Compare, typename Alloc,
+          int TargetNodeSize, bool Multi>
+struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
+                                  map_slot_policy<Key, Data>> {
+  using super_type = typename map_params::common_params;
+  using mapped_type = Data;
+  // This type allows us to move keys when it is safe to do so. It is safe
+  // for maps in which value_type and mutable_value_type are layout compatible.
+  using slot_policy = typename super_type::slot_policy;
+  using slot_type = typename super_type::slot_type;
+  using value_type = typename super_type::value_type;
+  using init_type = typename super_type::init_type;
+
+  using original_key_compare = typename super_type::original_key_compare;
+  // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare
+  class value_compare {
+    template <typename Params>
+    friend class btree;
+
+   protected:
+    explicit value_compare(original_key_compare c) : comp(std::move(c)) {}
+
+    original_key_compare comp;  // NOLINT
+
+   public:
+    auto operator()(const value_type &lhs, const value_type &rhs) const
+        -> decltype(comp(lhs.first, rhs.first)) {
+      return comp(lhs.first, rhs.first);
+    }
+  };
+  using is_map_container = std::true_type;
+
+  template <typename V>
+  static auto key(const V &value) -> decltype(value.first) {
+    return value.first;
+  }
+  static const Key &key(const slot_type *s) { return slot_policy::key(s); }
+  static const Key &key(slot_type *s) { return slot_policy::key(s); }
+  // For use in node handle.
+  static auto mutable_key(slot_type *s)
+      -> decltype(slot_policy::mutable_key(s)) {
+    return slot_policy::mutable_key(s);
+  }
+  static mapped_type &value(value_type *value) { return value->second; }
+};
+
+}  // namespace container_internal
+
 ABSL_NAMESPACE_END
 }  // namespace absl
 
diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h
index f587ca22..8c96e0ed 100644
--- a/absl/container/btree_set.h
+++ b/absl/container/btree_set.h
@@ -55,6 +55,17 @@
 namespace absl {
 ABSL_NAMESPACE_BEGIN
 
+namespace container_internal {
+
+template <typename Key>
+struct set_slot_policy;
+
+template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
+          bool Multi>
+struct set_params;
+
+}  // namespace container_internal
+
 // absl::btree_set<>
 //
 // An `absl::btree_set<K>` is an ordered associative container of unique key
@@ -724,6 +735,69 @@ void erase_if(btree_multiset<K, C, A> &set, Pred pred) {
   }
 }
 
+namespace container_internal {
+
+// This type implements the necessary functions from the
+// absl::container_internal::slot_type interface for btree_(multi)set.
+template <typename Key>
+struct set_slot_policy {
+  using slot_type = Key;
+  using value_type = Key;
+  using mutable_value_type = Key;
+
+  static value_type &element(slot_type *slot) { return *slot; }
+  static const value_type &element(const slot_type *slot) { return *slot; }
+
+  template <typename Alloc, class... Args>
+  static void construct(Alloc *alloc, slot_type *slot, Args &&...args) {
+    absl::allocator_traits<Alloc>::construct(*alloc, slot,
+                                             std::forward<Args>(args)...);
+  }
+
+  template <typename Alloc>
+  static void construct(Alloc *alloc, slot_type *slot, slot_type *other) {
+    absl::allocator_traits<Alloc>::construct(*alloc, slot, std::move(*other));
+  }
+
+  template <typename Alloc>
+  static void destroy(Alloc *alloc, slot_type *slot) {
+    absl::allocator_traits<Alloc>::destroy(*alloc, slot);
+  }
+
+  template <typename Alloc>
+  static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) {
+    using std::swap;
+    swap(*a, *b);
+  }
+
+  template <typename Alloc>
+  static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) {
+    *dest = std::move(*src);
+  }
+};
+
+// A parameters structure for holding the type parameters for a btree_set.
+// Compare and Alloc should be nothrow copy-constructible.
+template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
+          bool Multi>
+struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
+                                  set_slot_policy<Key>> {
+  using value_type = Key;
+  using slot_type = typename set_params::common_params::slot_type;
+  using value_compare =
+      typename set_params::common_params::original_key_compare;
+  using is_map_container = std::false_type;
+
+  template <typename V>
+  static const V &key(const V &value) {
+    return value;
+  }
+  static const Key &key(const slot_type *slot) { return *slot; }
+  static const Key &key(slot_type *slot) { return *slot; }
+};
+
+}  // namespace container_internal
+
 ABSL_NAMESPACE_END
 }  // namespace absl
 
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index f636c5fc..bf65a03d 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -270,17 +270,17 @@ struct common_params {
   enum {
     kTargetNodeSize = TargetNodeSize,
 
-    // Upper bound for the available space for values. This is largest for leaf
+    // Upper bound for the available space for slots. This is largest for leaf
     // nodes, which have overhead of at least a pointer + 4 bytes (for storing
     // 3 field_types and an enum).
-    kNodeValueSpace =
+    kNodeSlotSpace =
         TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4),
   };
 
-  // This is an integral type large enough to hold as many
-  // ValueSize-values as will fit a node of TargetNodeSize bytes.
+  // This is an integral type large enough to hold as many slots as will fit a
+  // node of TargetNodeSize bytes.
   using node_count_type =
-      absl::conditional_t<(kNodeValueSpace / sizeof(value_type) >
+      absl::conditional_t<(kNodeSlotSpace / sizeof(slot_type) >
                            (std::numeric_limits<uint8_t>::max)()),
                           uint16_t, uint8_t>;  // NOLINT
 
@@ -314,111 +314,6 @@ struct common_params {
   }
 };
 
-// A parameters structure for holding the type parameters for a btree_map.
-// Compare and Alloc should be nothrow copy-constructible.
-template <typename Key, typename Data, typename Compare, typename Alloc,
-          int TargetNodeSize, bool Multi>
-struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
-                                  map_slot_policy<Key, Data>> {
-  using super_type = typename map_params::common_params;
-  using mapped_type = Data;
-  // This type allows us to move keys when it is safe to do so. It is safe
-  // for maps in which value_type and mutable_value_type are layout compatible.
-  using slot_policy = typename super_type::slot_policy;
-  using slot_type = typename super_type::slot_type;
-  using value_type = typename super_type::value_type;
-  using init_type = typename super_type::init_type;
-
-  using original_key_compare = typename super_type::original_key_compare;
-  // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare
-  class value_compare {
-    template <typename Params>
-    friend class btree;
-
-   protected:
-    explicit value_compare(original_key_compare c) : comp(std::move(c)) {}
-
-    original_key_compare comp;  // NOLINT
-
-   public:
-    auto operator()(const value_type &lhs, const value_type &rhs) const
-        -> decltype(comp(lhs.first, rhs.first)) {
-      return comp(lhs.first, rhs.first);
-    }
-  };
-  using is_map_container = std::true_type;
-
-  template <typename V>
-  static auto key(const V &value) -> decltype(value.first) {
-    return value.first;
-  }
-  static const Key &key(const slot_type *s) { return slot_policy::key(s); }
-  static const Key &key(slot_type *s) { return slot_policy::key(s); }
-  // For use in node handle.
-  static auto mutable_key(slot_type *s)
-      -> decltype(slot_policy::mutable_key(s)) {
-    return slot_policy::mutable_key(s);
-  }
-  static mapped_type &value(value_type *value) { return value->second; }
-};
-
-// This type implements the necessary functions from the
-// absl::container_internal::slot_type interface.
-template <typename Key>
-struct set_slot_policy {
-  using slot_type = Key;
-  using value_type = Key;
-  using mutable_value_type = Key;
-
-  static value_type &element(slot_type *slot) { return *slot; }
-  static const value_type &element(const slot_type *slot) { return *slot; }
-
-  template <typename Alloc, class... Args>
-  static void construct(Alloc *alloc, slot_type *slot, Args &&... args) {
-    absl::allocator_traits<Alloc>::construct(*alloc, slot,
-                                             std::forward<Args>(args)...);
-  }
-
-  template <typename Alloc>
-  static void construct(Alloc *alloc, slot_type *slot, slot_type *other) {
-    absl::allocator_traits<Alloc>::construct(*alloc, slot, std::move(*other));
-  }
-
-  template <typename Alloc>
-  static void destroy(Alloc *alloc, slot_type *slot) {
-    absl::allocator_traits<Alloc>::destroy(*alloc, slot);
-  }
-
-  template <typename Alloc>
-  static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) {
-    using std::swap;
-    swap(*a, *b);
-  }
-
-  template <typename Alloc>
-  static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) {
-    *dest = std::move(*src);
-  }
-};
-
-// A parameters structure for holding the type parameters for a btree_set.
-// Compare and Alloc should be nothrow copy-constructible.
-template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
-          bool Multi>
-struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi,
-                                  set_slot_policy<Key>> {
-  using value_type = Key;
-  using slot_type = typename set_params::common_params::slot_type;
-  using value_compare =
-      typename set_params::common_params::original_key_compare;
-  using is_map_container = std::false_type;
-
-  template <typename V>
-  static const V &key(const V &value) { return value; }
-  static const Key &key(const slot_type *slot) { return *slot; }
-  static const Key &key(slot_type *slot) { return *slot; }
-};
-
 // An adapter class that converts a lower-bound compare into an upper-bound
 // compare. Note: there is no need to make a version of this adapter specialized
 // for key-compare-to functors because the upper-bound (the first value greater
@@ -562,9 +457,9 @@ class btree_node {
                        /*children*/ 0)
         .AllocSize();
   }
-  // A lower bound for the overhead of fields other than values in a leaf node.
+  // A lower bound for the overhead of fields other than slots in a leaf node.
   constexpr static size_type MinimumOverhead() {
-    return SizeWithNSlots(1) - sizeof(value_type);
+    return SizeWithNSlots(1) - sizeof(slot_type);
   }
 
   // Compute how many values we can fit onto a leaf node taking into account
@@ -1397,6 +1292,7 @@ class btree {
   }
 
   // The total number of bytes used by the btree.
+  // TODO(b/169338300): update to support node_btree_*.
   size_type bytes_used() const {
     node_stats stats = internal_stats(root());
     if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) {
@@ -1929,7 +1825,7 @@ constexpr bool btree<P>::static_assert_validation() {
       "key comparison function must return absl::{weak,strong}_ordering or "
       "bool.");
 
-  // Test the assumption made in setting kNodeValueSpace.
+  // Test the assumption made in setting kNodeSlotSpace.
   static_assert(node_type::MinimumOverhead() >= sizeof(void *) + 4,
                 "node space assumption incorrect");
 
diff --git a/absl/debugging/internal/address_is_readable.cc b/absl/debugging/internal/address_is_readable.cc
index 329c285f..26df3289 100644
--- a/absl/debugging/internal/address_is_readable.cc
+++ b/absl/debugging/internal/address_is_readable.cc
@@ -33,12 +33,12 @@ ABSL_NAMESPACE_END
 #else
 
 #include <fcntl.h>
+#include <sys/stat.h>
 #include <sys/syscall.h>
+#include <sys/types.h>
 #include <unistd.h>
 
-#include <atomic>
 #include <cerrno>
-#include <cstdint>
 
 #include "absl/base/internal/errno_saver.h"
 #include "absl/base/internal/raw_logging.h"
@@ -47,89 +47,56 @@ namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace debugging_internal {
 
-// Pack a pid and two file descriptors into a 64-bit word,
-// using 16, 24, and 24 bits for each respectively.
-static uint64_t Pack(uint64_t pid, uint64_t read_fd, uint64_t write_fd) {
-  ABSL_RAW_CHECK((read_fd >> 24) == 0 && (write_fd >> 24) == 0,
-                 "fd out of range");
-  return (pid << 48) | ((read_fd & 0xffffff) << 24) | (write_fd & 0xffffff);
-}
-
-// Unpack x into a pid and two file descriptors, where x was created with
-// Pack().
-static void Unpack(uint64_t x, int *pid, int *read_fd, int *write_fd) {
-  *pid = x >> 48;
-  *read_fd = (x >> 24) & 0xffffff;
-  *write_fd = x & 0xffffff;
-}
-
-// Return whether the byte at *addr is readable, without faulting.
-// Save and restores errno.   Returns true on systems where
-// unimplemented.
-// This is a namespace-scoped variable for correct zero-initialization.
-static std::atomic<uint64_t> pid_and_fds;  // initially 0, an invalid pid.
-
 bool AddressIsReadable(const void *addr) {
+  int fd = 0;
   absl::base_internal::ErrnoSaver errno_saver;
-  // We test whether a byte is readable by using write().  Normally, this would
-  // be done via a cached file descriptor to /dev/null, but linux fails to
-  // check whether the byte is readable when the destination is /dev/null, so
-  // we use a cached pipe.  We store the pid of the process that created the
-  // pipe to handle the case where a process forks, and the child closes all
-  // the file descriptors and then calls this routine.  This is not perfect:
-  // the child could use the routine, then close all file descriptors and then
-  // use this routine again.  But the likely use of this routine is when
-  // crashing, to test the validity of pages when dumping the stack.  Beware
-  // that we may leak file descriptors, but we're unlikely to leak many.
-  int bytes_written;
-  int current_pid = getpid() & 0xffff;   // we use only the low order 16 bits
-  do {  // until we do not get EBADF trying to use file descriptors
-    int pid;
-    int read_fd;
-    int write_fd;
-    uint64_t local_pid_and_fds = pid_and_fds.load(std::memory_order_acquire);
-    Unpack(local_pid_and_fds, &pid, &read_fd, &write_fd);
-    while (current_pid != pid) {
-      int p[2];
-      // new pipe
-      if (pipe(p) != 0) {
-        ABSL_RAW_LOG(FATAL, "Failed to create pipe, errno=%d", errno);
-      }
-      fcntl(p[0], F_SETFD, FD_CLOEXEC);
-      fcntl(p[1], F_SETFD, FD_CLOEXEC);
-      uint64_t new_pid_and_fds = Pack(current_pid, p[0], p[1]);
-      if (pid_and_fds.compare_exchange_strong(
-              local_pid_and_fds, new_pid_and_fds, std::memory_order_release,
-              std::memory_order_relaxed)) {
-        local_pid_and_fds = new_pid_and_fds;  // fds exposed to other threads
-      } else {  // fds not exposed to other threads; we can close them.
-        close(p[0]);
-        close(p[1]);
-        local_pid_and_fds = pid_and_fds.load(std::memory_order_acquire);
-      }
-      Unpack(local_pid_and_fds, &pid, &read_fd, &write_fd);
-    }
-    errno = 0;
-    // Use syscall(SYS_write, ...) instead of write() to prevent ASAN
-    // and other checkers from complaining about accesses to arbitrary
-    // memory.
+  for (int j = 0; j < 2; j++) {
+    // Here we probe with some syscall which
+    // - accepts a one-byte region of user memory as input
+    // - tests for EFAULT before other validation
+    // - has no problematic side-effects
+    //
+    // connect(2) works for this.  It copies the address into kernel
+    // memory before any validation beyond requiring an open fd.
+    // But a one byte address is never valid (sa_family is two bytes),
+    // so the call cannot succeed and change any state.
+    //
+    // This strategy depends on Linux implementation details,
+    // so we rely on the test to alert us if it stops working.
+    //
+    // Some discarded past approaches:
+    // - msync() doesn't reject PROT_NONE regions
+    // - write() on /dev/null doesn't return EFAULT
+    // - write() on a pipe requires creating it and draining the writes
+    //
+    // Use syscall(SYS_connect, ...) instead of connect() to prevent ASAN
+    // and other checkers from complaining about accesses to arbitrary memory.
     do {
-      bytes_written = syscall(SYS_write, write_fd, addr, 1);
-    } while (bytes_written == -1 && errno == EINTR);
-    if (bytes_written == 1) {   // remove the byte from the pipe
-      char c;
-      while (read(read_fd, &c, 1) == -1 && errno == EINTR) {
+      ABSL_RAW_CHECK(syscall(SYS_connect, fd, addr, 1) == -1,
+                     "should never succeed");
+    } while (errno == EINTR);
+    if (errno == EFAULT) return false;
+    if (errno == EBADF) {
+      if (j != 0) {
+        // Unclear what happened.
+        ABSL_RAW_LOG(ERROR, "unexpected EBADF on fd %d", fd);
+        return false;
       }
+      // fd 0 must have been closed. Try opening it again.
+      // Note: we shouldn't leak too many file descriptors here, since we expect
+      // to get fd==0 reopened.
+      fd = open("/dev/null", O_RDONLY);
+      if (fd == -1) {
+        ABSL_RAW_LOG(ERROR, "can't open /dev/null");
+        return false;
+      }
+    } else {
+      // probably EINVAL or ENOTSOCK; we got past EFAULT validation.
+      return true;
     }
-    if (errno == EBADF) {  // Descriptors invalid.
-      // If pid_and_fds contains the problematic file descriptors we just used,
-      // this call will forget them, and the loop will try again.
-      pid_and_fds.compare_exchange_strong(local_pid_and_fds, 0,
-                                          std::memory_order_release,
-                                          std::memory_order_relaxed);
-    }
-  } while (errno == EBADF);
-  return bytes_written == 1;
+  }
+  ABSL_RAW_CHECK(false, "unreachable");
+  return false;
 }
 
 }  // namespace debugging_internal
diff --git a/absl/status/status.h b/absl/status/status.h
index 39071e5f..5a09faeb 100644
--- a/absl/status/status.h
+++ b/absl/status/status.h
@@ -469,8 +469,9 @@ class Status final {
 
   // Status::ok()
   //
-  // Returns `true` if `this->ok()`. Prefer checking for an OK status using this
-  // member function.
+  // Returns `true` if `this->code()` == `absl::StatusCode::kOk`,
+  // indicating the absence of an error.
+  // Prefer checking for an OK status using this member function.
   ABSL_MUST_USE_RESULT bool ok() const;
 
   // Status::code()
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 0c47ca54..4e37151e 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -437,6 +437,7 @@ cc_library(
         "//absl/functional:function_ref",
         "//absl/meta:type_traits",
         "//absl/types:optional",
+        "//absl/types:span",
     ],
 )
 
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index aab97efd..0eef91df 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -851,6 +851,7 @@ absl_cc_library(
     absl::inlined_vector
     absl::optional
     absl::raw_logging_internal
+    absl::span
     absl::strings
     absl::type_traits
   PUBLIC