From d587c966ed86dc3b94362444e2b20fc3c5c4224e Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 15 Nov 2021 11:29:23 -0800 Subject: Export of internal Abseil changes -- 355b8f7b0070b005d53d94ee4180e95559ba2c88 by Derek Mauro : Documentation: don't define absl::Status::ok() in terms of itself Fixes #1058 PiperOrigin-RevId: 410035651 -- 31c512c834b3a8979297adc5006c3727a3c6554b by Evan Brown : 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 : 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 : Add Span dependency PiperOrigin-RevId: 409198889 GitOrigin-RevId: 355b8f7b0070b005d53d94ee4180e95559ba2c88 Change-Id: I7f4df3ec7739fdfde61d8ba983f07a08f6f1c7d7 --- absl/container/btree_map.h | 60 ++++++++++++ absl/container/btree_set.h | 74 ++++++++++++++ absl/container/internal/btree.h | 122 ++---------------------- absl/debugging/internal/address_is_readable.cc | 127 +++++++++---------------- absl/status/status.h | 5 +- absl/strings/BUILD.bazel | 1 + absl/strings/CMakeLists.txt | 1 + 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 +struct map_params; + +} // namespace container_internal + // absl::btree_map<> // // An `absl::btree_map` is an ordered associative container of @@ -812,6 +820,58 @@ void erase_if(btree_multimap &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 +struct map_params : common_params> { + 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 + 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 + 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 +struct set_slot_policy; + +template +struct set_params; + +} // namespace container_internal + // absl::btree_set<> // // An `absl::btree_set` is an ordered associative container of unique key @@ -724,6 +735,69 @@ void erase_if(btree_multiset &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 +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 + static void construct(Alloc *alloc, slot_type *slot, Args &&...args) { + absl::allocator_traits::construct(*alloc, slot, + std::forward(args)...); + } + + template + static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { + absl::allocator_traits::construct(*alloc, slot, std::move(*other)); + } + + template + static void destroy(Alloc *alloc, slot_type *slot) { + absl::allocator_traits::destroy(*alloc, slot); + } + + template + static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) { + using std::swap; + swap(*a, *b); + } + + template + 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 +struct set_params : common_params> { + 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 + 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::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 -struct map_params : common_params> { - 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 - 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 - 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 -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 - static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { - absl::allocator_traits::construct(*alloc, slot, - std::forward(args)...); - } - - template - static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { - absl::allocator_traits::construct(*alloc, slot, std::move(*other)); - } - - template - static void destroy(Alloc *alloc, slot_type *slot) { - absl::allocator_traits::destroy(*alloc, slot); - } - - template - static void swap(Alloc * /*alloc*/, slot_type *a, slot_type *b) { - using std::swap; - swap(*a, *b); - } - - template - 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 -struct set_params : common_params> { - 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 - 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

::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 +#include #include +#include #include -#include #include -#include #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 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 -- cgit v1.2.3