]> git.ipfire.org Git - thirdparty/squid.git/commit
Fix the ABA problem with Ipc::Mem::PageStack::pop() in c3408a3 (#587)
authorAlex Rousskov <rousskov@measurement-factory.com>
Wed, 13 May 2020 06:37:31 +0000 (06:37 +0000)
committerSquid Anubis <squid-anubis@squid-cache.org>
Wed, 13 May 2020 10:23:53 +0000 (10:23 +0000)
commita58608546341c5d2f53f7a4798ae464921961d9f
tree0531a701fed0008a3444ae85e13228bf60b48e40
parent8636e7c13150421ccc096a9681f967280e5dfcc8
Fix the ABA problem with Ipc::Mem::PageStack::pop() in c3408a3 (#587)

Suspected symptoms:

    assertion failed: mem/PageStack.cc:35: "old == expected"
    assertion failed: mem/PageStack.cc:27: "nxt != TakenPage"
    assertion failed: mem/PageStack.cc:33: "nxt != TakenPage"
    assertion failed: StoreMap.cc:337: "validSlice(sliceId)"

Replaced a list-based PageStack implementation with a tree-based one.
The new code uses a deterministic binary tree. Inner nodes count the
number of available IDs in their child subtrees. Leaf nodes store IDs
using bitmasks. The root node tells the pop() method whether it is going
to find a free page. The method then adjusts counters in 1-23 nodes
(depending on the tree hight) on the path to the leaf containing a page.
The push() method adds a bit to the leaf node and adjusts the counters
of all the inner nodes (1-23) on the way up to the root one. All the
adjustments are lockless. Push may also be wait-free. No ABA problems.

An alternative fix that preserved list-based implementation was
implemented but ultimately rejected: Avoiding ABA problems required
complex code, and that complexity prevented meaningful validation using
Rust's Loom. Also, dirty performance tests of outside-of-Squid code
showed unexplained significant response time growth of the list-based
implementation when concurrency levels were being increased beyond a few
threads. While these validation and performance concerns could be red
herrings, their existence decreased our confidence in the list-based
algorithm that already had a history of fooling developers.

The tree-based PageStack implementation needs 8-16x less RAM. Roughly:
* list-based: sizeof(uint32_t) * capacity          or  4*capacity
* tree-based: sizeof(uint64_t) * 2 * rcapacity/64  or  rcapacity/4
  where rounded capacity is somewhere between capacity and 2*capacity

The absolute RAM savings are minor for most environments, but the
footprint reduction might be enough to fit a significant part of some
hot index in a modern L1 CPU cache: (e.g., a 32GB rock cache_dir may
have 16GB/16KB = 1M slot IDs = 512KB tree size).

The tree-based structure may make future support for caches with more
than 2^25 entries easier because it does not heavily rely on combining a
cache entry ID and an ABA version/nonce in a single 64-bit atomic.

TODO: While absolute tree- and list-based operation costs are all small
(under 1 microsecond), tree-based implementation cost are higher. Since
rock code pops all disk slots at startup (a known performance bug), rock
startup costs increased significantly. For example, a 200 GB disk cache
test shows ~18 seconds startup time for the tree-based implementation
versus ~4 seconds for list-based. This will be addressed by fixing that
known performance bug. The fix will not alter the tree algorithm.

TODO: The PageStack class should be renamed. Ideally, that renaming
should coincide with refactoring the PagePool/PageStack split, which is
an old XXX also currently exposes a lot of internal PageStack code.

See also: https://en.wikipedia.org/wiki/ABA_problem
src/Makefile.am
src/ipc/Makefile.am
src/ipc/mem/PageStack.cc
src/ipc/mem/PageStack.h