[DPDK/core Bug 2060] RCU ackec_token wrong value

[bugzilla at dpdk.org]

https://bugs.dpdk.org/show_bug.cgi?id=2060

            Bug ID: 2060
           Summary: RCU ackec_token wrong value
           Product: DPDK
           Version: unspecified
          Hardware: All
                OS: All
            Status: UNCONFIRMED
          Severity: critical
          Priority: Normal
         Component: core
          Assignee: dev at dpdk.org
          Reporter: kipi at servers.com
  Target Milestone: ---

Created attachment 408
  --> https://bugs.dpdk.org/attachment.cgi?id=408&action=edit
a minimal example demonstrating the problem

__rte_rcu_qsbr_check_all() and __rte_rcu_qsbr_check_selective() compute
acked_token as the minimum of the counters of the threads that were online when
read, and store it into v->acked_token. rte_rcu_qsbr_check(v, t) then returns 1
without walking whenever t <= v->acked_token. But a walk for token t only
proves that grace periods up to t are over. The minimum of the counters it has
seen can be larger than t, and for the tokens in between the proof does not
hold: a thread read as __RTE_QSBR_CNT_THR_OFFLINE may have come online during
the walk, at a token below those, holding a pointer that a later period
unpublished. A second writer whose token falls into that range then frees the
pointer from the cached fast path while the first reader still uses it.

Interleaving (two writers A and B, reader R toggling offline/online, reader Q
reporting steadily, current token 5)

A calls rte_rcu_qsbr_check(v, 5). The walk reads R's counter: OFFLINE, skipped.
R calls rte_rcu_qsbr_thread_online() (counter = 5) and loads head, getting Y.
B unpublishes Y (head = Z) and calls rte_rcu_qsbr_start(), which returns 6.
Q calls rte_rcu_qsbr_quiescent(), its counter becomes 6.
A's walk reads Q's counter: 6 >= 5, fine. The walk ends, acked_token = min = 6,
stored into v->acked_token.
B calls rte_rcu_qsbr_check(v, 6): 6 <= v->acked_token, returns 1 without a
walk. B frees Y.
R is online with counter 5 and still dereferences Y.
Step 1 is correct for token 5: Y was unpublished after A's
rte_rcu_qsbr_start(), so the proof for 5 is not affected. Step 5 is the defect:
the walk never saw R online, yet the cache now claims period 6 is over. Any
user with two writers (for example two rte_rcu_qsbr_dq instances) and readers
that use rte_rcu_qsbr_thread_offline()/_online() is exposed.

Reproduction

A single-file C program with direct rte_rcu_qsbr_* calls, no EAL, is attached
(dpdk-qsbr-repro.c). It registers 512 threads with the toggling reader at id 0,
the steady reporter at id 511 and every id between them registered and offline,
so that a walk takes about a microsecond. Two writers swap the head, call
rte_rcu_qsbr_start(), spin on rte_rcu_qsbr_check(t, false) and poison the old
node instead of freeing it. The reader counts poisoned reads.


$ ./dpdk-qsbr-repro
cached: reads 203668, violations 136
$ ./dpdk-qsbr-repro --no-cache     # writers call __rte_rcu_qsbr_check_all()
directly
no cache: reads 200204, violations 0
Three runs each: 136 / 32 / 136 violations with the fast path, 0 / 0 / 0
without it. Each run takes about 0.3 s on a 22-thread desktop CPU.

Suggested fix

Store the checked token, not the minimum of the counters. Every counter that
passed the walk is >= t, so t is exactly what the walk proves, and the "nobody
online" and "only move forward" conditions can stay as they are:

        /* All readers are checked: every counter seen is >= t, and the walk
         * proves nothing beyond t, a thread read as offline may be online by
         * now at a lower token. Cache t, not the minimum of the counters.
         */
        if (acked_token != __RTE_QSBR_CNT_MAX)
                rte_atomic_store_explicit(&v->acked_token, t,
                        rte_memory_order_relaxed);

with the acked_token > c updates in the loops reduced to a flag that some
thread was online. The cost is more walks when tokens are checked out of order,
the semantics of rte_rcu_qsbr_check() do not change.

A related, smaller issue: v->acked_token is stored and loaded with
rte_memory_order_relaxed. A writer that takes the fast path therefore has no
happens-before relation with the readers' critical sections that the other
writer's walk observed with acquire loads. On x86 this is harmless, on weakly
ordered CPUs it is not. Store release / load acquire fixes it at no cost on
x86.

-- 
You are receiving this mail because:
You are the assignee for the bug.