Count graph nodes per address bucket so ForgetDeadlockInfo() can skip deadlock_graph_mu.

In debug builds with deadlock detection enabled, ~Mutex() calls
ForgetDeadlockInfo(), which takes the global deadlock_graph_mu spinlock to
remove the Mutex's node from deadlock_graph. Only Mutexes involved in nested
locking get a node, so for most destroyed Mutexes there is nothing to remove.

Keep a count of deadlock_graph nodes for each hash bucket of Mutex addresses.
ForgetDeadlockInfo() reads the count for the Mutex's bucket without the lock,
and returns early if it is zero:

- Counts change only under deadlock_graph_mu, when GetGraphIdLocked() creates a
  node and when ForgetDeadlockInfo() removes one. GraphCycles::GetId() can now
  report whether it created a node, and RemoveNode() returns whether the node
  existed.
- If the Mutex has a node, the DeadlockCheck() call that created it either
  happens-before ForgetDeadlockInfo() or races with it. In the first case,
  ForgetDeadlockInfo() sees a nonzero count. In the second case,
  DeadlockCheck() could also create the node just after the removal, so the
  early return adds no new race.
- Counts saturate at 255 and then never change, so a saturated bucket is never
  treated as empty again. Counts below 255 are exact.

There are 2^18 buckets, with 8-bit counts packed four per 32-bit atomic word.
8-bit counts give 4x as many buckets as 32-bit counts in the same memory, so a
larger fraction of buckets is empty. Packing keeps the array
constant-initialized: an array of 2^18 one-byte atomics exceeds the compiler's
constexpr evaluation step limit for ABSL_CONST_INIT.

Cost: a 256 KiB zero-initialized static array, touched only in debug builds
with deadlock detection enabled.
PiperOrigin-RevId: 997581888
4 files changed
tree: cb51a282268a03488fc67c4d40f8694913f9c16c
  1. .github/
  2. absl/
  3. ci/
  4. CMake/
  5. .bazelrc
  6. .clang-format
  7. .gitignore
  8. ABSEIL_ISSUE_TEMPLATE.md
  9. AUTHORS
  10. BUILD.bazel
  11. CMakeLists.txt
  12. conanfile.py
  13. CONTRIBUTING.md
  14. create_lts.py
  15. FAQ.md
  16. LICENSE
  17. MODULE.bazel
  18. PrivacyInfo.xcprivacy
  19. README.md
  20. UPGRADES.md
README.md

Abseil - C++ Common Libraries

The repository contains the Abseil C++ library code. Abseil is an open-source collection of C++ code (compliant to C++17) designed to augment the C++ standard library.

Table of Contents

About Abseil

Abseil is an open-source collection of C++ library code designed to augment the C++ standard library. The Abseil library code is collected from Google's own C++ code base, has been extensively tested and used in production, and is the same code we depend on in our daily coding lives.

In some cases, Abseil provides pieces missing from the C++ standard; in others, Abseil provides alternatives to the standard for special needs we've found through usage in the Google code base. We denote those cases clearly within the library code we provide you.

Abseil is not meant to be a competitor to the standard library; we've just found that many of these utilities serve a purpose within our code base, and we now want to provide those resources to the C++ community as a whole.

Quickstart

If you want to just get started, make sure you at least run through the Abseil Quickstart. The Quickstart contains information about setting up your development environment, downloading the Abseil code, running tests, and getting a simple binary working.

Building Abseil

Bazel and CMake are the official build systems for Abseil. See the quickstart for more information on building Abseil using the Bazel build system. If you require CMake support, please check the CMake build instructions and CMake Quickstart.

Support

Abseil follows Google's Foundational C++ Support Policy. See this table for a list of currently supported versions compilers, platforms, and build tools.

Codemap

Abseil contains the following C++ library components:

  • base
    The base library contains initialization code and other code which all other Abseil code depends on. Code within base may not depend on any other code (other than the C++ standard library).
  • algorithm
    The algorithm library contains additions to the C++ <algorithm> library and container-based versions of such algorithms.
  • cleanup
    The cleanup library contains the control-flow-construct-like type absl::Cleanup which is used for executing a callback on scope exit.
  • container
    The container library contains additional STL-style containers, including Abseil's unordered “Swiss table” containers.
  • crc The crc library contains code for computing error-detecting cyclic redundancy checks on data.
  • debugging
    The debugging library contains code useful for enabling leak checks, and stacktrace and symbolization utilities.
  • flags
    The flags library contains code for handling command line flags for libraries and binaries built with Abseil.
  • hash
    The hash library contains the hashing framework and default hash functor implementations for hashable types in Abseil.
  • log
    The log library contains LOG and CHECK macros and facilities for writing logged messages out to disk, stderr, or user-extensible destinations.
  • memory
    The memory library contains memory management facilities that augment C++'s <memory> library.
  • meta
    The meta library contains type checks similar to those available in the C++ <type_traits> library.
  • numeric
    The numeric library contains 128-bit integer types as well as implementations of C++20's bitwise math functions.
  • profiling
    The profiling library contains utility code for profiling C++ entities. It is currently a private dependency of other Abseil libraries.
  • random
    The random library contains functions for generating pseudorandom values.
  • status
    The status library contains abstractions for error handling, specifically absl::Status and absl::StatusOr<T>.
  • strings
    The strings library contains a variety of strings routines and utilities.
  • synchronization
    The synchronization library contains concurrency primitives (Abseil's absl::Mutex class, an alternative to std::mutex) and a variety of synchronization abstractions.
  • time
    The time library contains abstractions for computing with absolute points in time, durations of time, and formatting and parsing time within time zones.
  • types
    The types library contains non-container utility types.
  • utility
    The utility library contains utility and helper code.

Releases

Abseil recommends users “live-at-head” (update to the latest commit from the master branch as often as possible). However, we realize this philosophy doesn't work for every project, so we also provide Long Term Support Releases to which we backport fixes for severe bugs. See our release management document for more details.

License

The Abseil C++ library is licensed under the terms of the Apache license. See LICENSE for more information.

Links

For more information about Abseil: