Linux-kernel examples for LKMM recipes
Hello!
At Linux Plumbers Conference, we got requests for a recipes document, and a further request to point to actual code in the Linux kernel. I have pulled together some examples for various litmus-test families, as shown below. The decoder ring for the abbreviations (ISA2, LB, SB, MP, ...) is here:
https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
This document is also checked into the memory-models git archive:
https://github.com/aparri/memory-model.git
I would be especially interested in simpler examples in general, and of course any example at all for the cases where I was unable to find any. Thoughts?
Thanx, Paul
------------------------------------------------------------------------
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter by rcu_nmi_enter() and rcu_nmi_exit() qualifies (see kernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.
b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?
1. MP (see test6.pdf for nickname translation)
a. smp_store_release() / smp_load_acquire()
init_stack_slab() in lib/stackdepot.c uses release-acquire to handle initialization of a slab of the stack. Working out the mutual-exclusion design is left as an exercise for the reader.
b. rcu_assign_pointer() / rcu_dereference()
expand_to_next_prime() does the rcu_assign_pointer(), and next_prime_number() does the rcu_dereference(). This mediates access to a bit vector that is expanded as additional primes are needed. These two functions are in lib/prime_numbers.c.
c. smp_wmb() / smp_rmb()
xlog_state_switch_iclogs() contains the following:
log->l_curr_block -= log->l_logBBsize; ASSERT(log->l_curr_block >= 0); smp_wmb(); log->l_curr_cycle++;
And xlog_valid_lsn() contains the following:
cur_cycle = ACCESS_ONCE(log->l_curr_cycle); smp_rmb();
cur_block = ACCESS_ONCE(log->l_curr_block);
d. Replacing either of the above with smp_mb()
Holding off on this one for the moment...
2. Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
Lots of variety here, can in some cases substitute:
a. READ_ONCE() for smp_load_acquire()
b. WRITE_ONCE() for smp_store_release()
c. Dependencies for both smp_load_acquire() and
smp_store_release().
d. smp_wmb() for smp_store_release() in first thread
of ISA2 and Z6.2.
e. smp_rmb() for smp_load_acquire() in last thread of ISA2.
The canonical illustration of LB involves the various memory allocators, where you don't want a load from about-to-be-freed memory to see a store initializing a later incarnation of that same memory area. But the per-CPU caches make this a very long and complicated example.
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
Thoughts?
3. SB
a. smp_mb(), as in lockless wait-wakeup coordination.
And as in sys_membarrier()-scheduler coordination,
for that matter.
Examples seem to be lacking. Most cases use locking.
Here is one rather strange one from RCU:
void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func)
{
unsigned long flags;
bool needwake;
bool havetask = READ_ONCE(rcu_tasks_kthread_ptr);
rhp->next = NULL;
rhp->func = func;
raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
needwake = !rcu_tasks_cbs_head;
*rcu_tasks_cbs_tail = rhp;
rcu_tasks_cbs_tail = &rhp->next;
raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
/* We can't create the thread unless interrupts are enabled. */
if ((needwake && havetask) ||
(!havetask && !irqs_disabled_flags(flags))) {
rcu_spawn_tasks_kthread();
wake_up(&rcu_tasks_cbs_wq);
}
}
And for the wait side, using synchronize_sched() to supply
the barrier for both ends, with the preemption disabling
due to raw_spin_lock_irqsave() serving as the read-side
critical section:
if (!list) {
wait_event_interruptible(rcu_tasks_cbs_wq,
rcu_tasks_cbs_head);
if (!rcu_tasks_cbs_head) {
WARN_ON(signal_pending(current));
schedule_timeout_interruptible(HZ/10);
}
continue;
}
synchronize_sched();
-----------------
Here is another one that uses atomic_cmpxchg() as a
full memory barrier:
if (!wait_event_timeout(*wait, !atomic_read(stopping),
msecs_to_jiffies(1000))) {
atomic_set(stopping, 0);
smp_mb();
return -ETIMEDOUT;
}
int omap3isp_module_sync_is_stopping(wait_queue_head_t *wait,
atomic_t *stopping)
{
if (atomic_cmpxchg(stopping, 1, 0)) {
wake_up(wait);
return 1;
}
return 0;
}Quoted 93 lines · Paul E. McKenney
Hello!
At Linux Plumbers Conference, we got requests for a recipes document, and a further request to point to actual code in the Linux kernel. I have pulled together some examples for various litmus-test families, as shown below. The decoder ring for the abbreviations (ISA2, LB, SB, MP, ...) is here:
https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdfThis document is also checked into the memory-models git archive:
https://github.com/aparri/memory-model.git
I would be especially interested in simpler examples in general, and of course any example at all for the cases where I was unable to find any. Thoughts?
Thanx, Paul
------------------------------------------------------------------------
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?1. MP (see test6.pdf for nickname translation)
a.
smp_store_release()/smp_load_acquire()
init_stack_slab()inlib/stackdepot.cuses release-acquire to handle initialization of a slab of the stack. Working out the mutual-exclusion design is left as an exercise for the reader.b.
rcu_assign_pointer()/rcu_dereference()
expand_to_next_prime()does thercu_assign_pointer(), andnext_prime_number()does thercu_dereference(). This mediates access to a bit vector that is expanded as additional primes are needed. These two functions are inlib/prime_numbers.c.c.
smp_wmb()/smp_rmb()
xlog_state_switch_iclogs()contains the following:
log->l_curr_block-=log->l_logBBsize;ASSERT(log->l_curr_block >= 0);smp_wmb(); log->l_curr_cycle++;And
xlog_valid_lsn()contains the following:
cur_cycle=ACCESS_ONCE(log->l_curr_cycle);smp_rmb();
cur_block=ACCESS_ONCE(log->l_curr_block);d. Replacing either of the above with
smp_mb()Holding off on this one for the moment...
2. Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
Lots of variety here, can in some cases substitute:
a.
READ_ONCE()forsmp_load_acquire()
b.WRITE_ONCE()forsmp_store_release()
c. Dependencies for bothsmp_load_acquire()and
smp_store_release().
d.smp_wmb()forsmp_store_release()in first thread
of ISA2 and Z6.2.
e.smp_rmb()forsmp_load_acquire()in last thread of ISA2.The canonical illustration of LB involves the various memory allocators, where you don't want a load from about-to-be-freed memory to see a store initializing a later incarnation of that same memory area. But the per-CPU caches make this a very long and complicated example.
Quoted 4 lines
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
The "Program-Order guarantees" case in scheduler? See the comments written by Peter above try_to_wake_up():
* The basic program-order guarantee on SMP systems is that when a task [t]
* migrates, all its activity on its old CPU [c0] happens-before any subsequent
* execution on its new CPU [c1].
...
* For blocking we (obviously) need to provide the same guarantee as for
* migration. However the means are completely different as there is no lock
* chain to provide order. Instead we do:
*
* 1) smp_store_release(X->on_cpu, 0)
* 2) smp_cond_load_acquire(!X->on_cpu)
*
* Example:
*
* CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
*
* LOCK rq(0)->lock LOCK X->pi_lock * dequeue X * sched-out X * smp_store_release(X->on_cpu, 0); * * smp_cond_load_acquire(&X->on_cpu, !VAL); * X->state = WAKING * set_task_cpu(X,2) * * LOCK rq(2)->lock * enqueue X * X->state = RUNNING * UNLOCK rq(2)->lock * * LOCK rq(2)->lock // orders against CPU1 * sched-out Z * sched-in X * UNLOCK rq(2)->lock
*
* UNLOCK X->pi_lock
* UNLOCK rq(0)->lock
This is a chain mixed with lock and acquire-release(maybe even better?).
And another example would be osq_{lock,unlock}() on multiple(more than three) CPUs.
Regards,
Boqun
Quoted 71 lines
Thoughts?
3. SB
a. smp_mb(), as in lockless wait-wakeup coordination. And as in sys_membarrier()-scheduler coordination, for that matter. Examples seem to be lacking. Most cases use locking. Here is one rather strange one from RCU: void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func) { unsigned long flags; bool needwake; bool havetask = READ_ONCE(rcu_tasks_kthread_ptr); rhp->next = NULL; rhp->func = func; raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags); needwake = !rcu_tasks_cbs_head; *rcu_tasks_cbs_tail = rhp; rcu_tasks_cbs_tail = &rhp->next; raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags); /* We can't create the thread unless interrupts are enabled. */ if ((needwake && havetask) || (!havetask && !irqs_disabled_flags(flags))) { rcu_spawn_tasks_kthread(); wake_up(&rcu_tasks_cbs_wq); } } And for the wait side, using synchronize_sched() to supply the barrier for both ends, with the preemption disabling due to raw_spin_lock_irqsave() serving as the read-side critical section: if (!list) { wait_event_interruptible(rcu_tasks_cbs_wq, rcu_tasks_cbs_head); if (!rcu_tasks_cbs_head) { WARN_ON(signal_pending(current)); schedule_timeout_interruptible(HZ/10); } continue; } synchronize_sched(); ----------------- Here is another one that uses atomic_cmpxchg() as a full memory barrier: if (!wait_event_timeout(*wait, !atomic_read(stopping), msecs_to_jiffies(1000))) { atomic_set(stopping, 0); smp_mb(); return -ETIMEDOUT; } int omap3isp_module_sync_is_stopping(wait_queue_head_t *wait, atomic_t *stopping) { if (atomic_cmpxchg(stopping, 1, 0)) { wake_up(wait); return 1; } return 0; }
Quoted 46 lines · Boqun Feng
Quoted 4 lines · Paul E. McKenney
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
The "Program-Order guarantees" case in scheduler? See the comments written by Peter above
try_to_wake_up():* The basic program-order guarantee on SMP systems is that when a task [t]
* migrates, all its activity on its old CPU [c0] happens-before any subsequent
* execution on its new CPU [c1].
...
* For blocking we (obviously) need to provide the same guarantee as for
* migration. However the means are completely different as there is no lock
* chain to provide order. Instead we do:
*
* 1)smp_store_release(X->on_cpu, 0)
* 2)smp_cond_load_acquire(!X->on_cpu)
*
* Example:
*
* CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
** LOCK rq(0)->lock LOCK X->pi_lock * dequeue X * sched-out X * smp_store_release(X->on_cpu, 0); * * smp_cond_load_acquire(&X->on_cpu, !VAL); * X->state = WAKING * set_task_cpu(X,2) * * LOCK rq(2)->lock * enqueue X * X->state = RUNNING * UNLOCK rq(2)->lock * * LOCK rq(2)->lock // orders against CPU1 * sched-out Z * sched-in X * UNLOCK rq(2)->lock*
* UNLOCKX->pi_lock
* UNLOCK rq(0)->lock
Quoted 5 lines
This is a chain mixed with lock and acquire-release(maybe even better?).
And another example would be osq_{lock,unlock}() on multiple(more than three) CPUs.
I think the qrwlock also has something similar with the writer fairness issue fixed:
CPU0: (writer doing an unlock)smp_store_release(&lock->wlocked, 0); // Bottom byte of lock->cnts
CPU1: (waiting writer on slowpath) atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
...arch_spin_unlock(&lock->wait_lock);
CPU2: (reader on slowpath)arch_spin_lock(&lock->wait_lock);
and there's mixed-size accesses here too. Fun stuff!
Will
Quoted 66 lines · Will Deacon
Quoted 46 lines · Boqun Feng
Quoted 4 lines · Paul E. McKenney
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
The "Program-Order guarantees" case in scheduler? See the comments written by Peter above
try_to_wake_up():* The basic program-order guarantee on SMP systems is that when a task [t]
* migrates, all its activity on its old CPU [c0] happens-before any subsequent
* execution on its new CPU [c1].
...
* For blocking we (obviously) need to provide the same guarantee as for
* migration. However the means are completely different as there is no lock
* chain to provide order. Instead we do:
*
* 1)smp_store_release(X->on_cpu, 0)
* 2)smp_cond_load_acquire(!X->on_cpu)
*
* Example:
*
* CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
** LOCK rq(0)->lock LOCK X->pi_lock * dequeue X * sched-out X * smp_store_release(X->on_cpu, 0); * * smp_cond_load_acquire(&X->on_cpu, !VAL); * X->state = WAKING * set_task_cpu(X,2) * * LOCK rq(2)->lock * enqueue X * X->state = RUNNING * UNLOCK rq(2)->lock * * LOCK rq(2)->lock // orders against CPU1 * sched-out Z * sched-in X * UNLOCK rq(2)->lock*
* UNLOCKX->pi_lock
* UNLOCK rq(0)->lockQuoted 5 lines
This is a chain mixed with lock and acquire-release(maybe even better?).
And another example would be osq_{lock,unlock}() on multiple(more than three) CPUs.
I think the qrwlock also has something similar with the writer fairness issue fixed:
CPU0: (writer doing an unlock)
smp_store_release(&lock->wlocked, 0); // Bottom byte oflock->cntsCPU1: (waiting writer on slowpath)
atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
...arch_spin_unlock(&lock->wait_lock);
Quoted 4 lines
CPU2: (reader on slowpath)
arch_spin_lock(&lock->wait_lock);and there's mixed-size accesses here too. Fun stuff!
You had me going there until you mentioned the mixed-size accesses. ;-)
Thanx, Paul
Quoted 135 lines · Boqun Feng
Quoted 93 lines · Paul E. McKenney
Hello!
At Linux Plumbers Conference, we got requests for a recipes document, and a further request to point to actual code in the Linux kernel. I have pulled together some examples for various litmus-test families, as shown below. The decoder ring for the abbreviations (ISA2, LB, SB, MP, ...) is here:
https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdfThis document is also checked into the memory-models git archive:
https://github.com/aparri/memory-model.git
I would be especially interested in simpler examples in general, and of course any example at all for the cases where I was unable to find any. Thoughts?
Thanx, Paul
------------------------------------------------------------------------
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?1. MP (see test6.pdf for nickname translation)
a.
smp_store_release()/smp_load_acquire()
init_stack_slab()inlib/stackdepot.cuses release-acquire to handle initialization of a slab of the stack. Working out the mutual-exclusion design is left as an exercise for the reader.b.
rcu_assign_pointer()/rcu_dereference()
expand_to_next_prime()does thercu_assign_pointer(), andnext_prime_number()does thercu_dereference(). This mediates access to a bit vector that is expanded as additional primes are needed. These two functions are inlib/prime_numbers.c.c.
smp_wmb()/smp_rmb()
xlog_state_switch_iclogs()contains the following:
log->l_curr_block-=log->l_logBBsize;ASSERT(log->l_curr_block >= 0);smp_wmb(); log->l_curr_cycle++;And
xlog_valid_lsn()contains the following:
cur_cycle=ACCESS_ONCE(log->l_curr_cycle);smp_rmb();
cur_block=ACCESS_ONCE(log->l_curr_block);d. Replacing either of the above with
smp_mb()Holding off on this one for the moment...
2. Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
Lots of variety here, can in some cases substitute:
a.
READ_ONCE()forsmp_load_acquire()
b.WRITE_ONCE()forsmp_store_release()
c. Dependencies for bothsmp_load_acquire()and
smp_store_release().
d.smp_wmb()forsmp_store_release()in first thread
of ISA2 and Z6.2.
e.smp_rmb()forsmp_load_acquire()in last thread of ISA2.The canonical illustration of LB involves the various memory allocators, where you don't want a load from about-to-be-freed memory to see a store initializing a later incarnation of that same memory area. But the per-CPU caches make this a very long and complicated example.
Quoted 4 lines
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
The "Program-Order guarantees" case in scheduler? See the comments written by Peter above
try_to_wake_up():* The basic program-order guarantee on SMP systems is that when a task [t]
* migrates, all its activity on its old CPU [c0] happens-before any subsequent
* execution on its new CPU [c1].
...
* For blocking we (obviously) need to provide the same guarantee as for
* migration. However the means are completely different as there is no lock
* chain to provide order. Instead we do:
*
* 1)smp_store_release(X->on_cpu, 0)
* 2)smp_cond_load_acquire(!X->on_cpu)
*
* Example:
*
* CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
** LOCK rq(0)->lock LOCK X->pi_lock * dequeue X * sched-out X * smp_store_release(X->on_cpu, 0); * * smp_cond_load_acquire(&X->on_cpu, !VAL); * X->state = WAKING * set_task_cpu(X,2) * * LOCK rq(2)->lock * enqueue X * X->state = RUNNING * UNLOCK rq(2)->lock * * LOCK rq(2)->lock // orders against CPU1 * sched-out Z * sched-in X * UNLOCK rq(2)->lock
Quoted 5 lines
*
* UNLOCKX->pi_lock
* UNLOCK rq(0)->lockThis is a chain mixed with lock and acquire-release(maybe even better?).
I added this one, though it might be outside of the scope of recipes.
Thanx, Paul
Quoted 77 lines
And another example would be osq_{lock,unlock}() on multiple(more than three) CPUs.
Regards,
BoqunQuoted 71 lines
Thoughts?
3. SB
a. smp_mb(), as in lockless wait-wakeup coordination. And as in sys_membarrier()-scheduler coordination, for that matter. Examples seem to be lacking. Most cases use locking. Here is one rather strange one from RCU: void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func) { unsigned long flags; bool needwake; bool havetask = READ_ONCE(rcu_tasks_kthread_ptr); rhp->next = NULL; rhp->func = func; raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags); needwake = !rcu_tasks_cbs_head; *rcu_tasks_cbs_tail = rhp; rcu_tasks_cbs_tail = &rhp->next; raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags); /* We can't create the thread unless interrupts are enabled. */ if ((needwake && havetask) || (!havetask && !irqs_disabled_flags(flags))) { rcu_spawn_tasks_kthread(); wake_up(&rcu_tasks_cbs_wq); } } And for the wait side, using synchronize_sched() to supply the barrier for both ends, with the preemption disabling due to raw_spin_lock_irqsave() serving as the read-side critical section: if (!list) { wait_event_interruptible(rcu_tasks_cbs_wq, rcu_tasks_cbs_head); if (!rcu_tasks_cbs_head) { WARN_ON(signal_pending(current)); schedule_timeout_interruptible(HZ/10); } continue; } synchronize_sched(); ----------------- Here is another one that uses atomic_cmpxchg() as a full memory barrier: if (!wait_event_timeout(*wait, !atomic_read(stopping), msecs_to_jiffies(1000))) { atomic_set(stopping, 0); smp_mb(); return -ETIMEDOUT; } int omap3isp_module_sync_is_stopping(wait_queue_head_t *wait, atomic_t *stopping) { if (atomic_cmpxchg(stopping, 1, 0)) { wake_up(wait); return 1; } return 0; }
Hi Paul,
Quoted 10 lines · Paul E. McKenney
Hello!
At Linux Plumbers Conference, we got requests for a recipes document, and a further request to point to actual code in the Linux kernel. I have pulled together some examples for various litmus-test families, as shown below. The decoder ring for the abbreviations (ISA2, LB, SB, MP, ...) is here:
https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
Quoted 7 lines
This document is also checked into the memory-models git archive:
https://github.com/aparri/memory-model.git
I would be especially interested in simpler examples in general, and of course any example at all for the cases where I was unable to find any. Thoughts?
Below are some examples we did discuss (at some point):
The comment in kernel/events/ring_buffer.c:perf_output_put_handle() describes instances of MP+wmb+rmb and LB+ctrl+mb.
The comments in kernel/sched/core.c:try_to_wake_up() describes more instances of MP ("plus locking") and LB (see finish_lock_switch()).
The comment in kernel/sched/core.c:task_rq_lock() describes an ins- tance of MP+wmb+addr-acqpo.
The comment in include/linux/wait.h:waitqueue_active() describes an instance of SB+mb+mb.
63cae12bce986 ("perf/core: Fix sys_perf_event_open() vs. hotplug") describes an instance of W+RWC+porel+mb+mb.
[...]
I wish we could say "any barrier (explicit or implicit) in sources is accompanied by a comment mentioning the interested pattern...", but life is not always this simple. ;-)
Andrea
Quoted 151 lines
Thanx, Paul
------------------------------------------------------------------------
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?1. MP (see test6.pdf for nickname translation)
a.
smp_store_release()/smp_load_acquire()
init_stack_slab()inlib/stackdepot.cuses release-acquire to handle initialization of a slab of the stack. Working out the mutual-exclusion design is left as an exercise for the reader.b.
rcu_assign_pointer()/rcu_dereference()
expand_to_next_prime()does thercu_assign_pointer(), andnext_prime_number()does thercu_dereference(). This mediates access to a bit vector that is expanded as additional primes are needed. These two functions are inlib/prime_numbers.c.c.
smp_wmb()/smp_rmb()
xlog_state_switch_iclogs()contains the following:
log->l_curr_block-=log->l_logBBsize;ASSERT(log->l_curr_block >= 0);smp_wmb(); log->l_curr_cycle++;And
xlog_valid_lsn()contains the following:
cur_cycle=ACCESS_ONCE(log->l_curr_cycle);smp_rmb();
cur_block=ACCESS_ONCE(log->l_curr_block);d. Replacing either of the above with
smp_mb()Holding off on this one for the moment...
2. Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
Lots of variety here, can in some cases substitute:
a.
READ_ONCE()forsmp_load_acquire()
b.WRITE_ONCE()forsmp_store_release()
c. Dependencies for bothsmp_load_acquire()and
smp_store_release().
d.smp_wmb()forsmp_store_release()in first thread
of ISA2 and Z6.2.
e.smp_rmb()forsmp_load_acquire()in last thread of ISA2.The canonical illustration of LB involves the various memory allocators, where you don't want a load from about-to-be-freed memory to see a store initializing a later incarnation of that same memory area. But the per-CPU caches make this a very long and complicated example.
I am not aware of any three-CPU release-acquire chains in the Linux kernel. There are three-CPU lock-based chains in RCU, but these are not at all simple, either.
Thoughts?
3. SB
a. smp_mb(), as in lockless wait-wakeup coordination. And as in sys_membarrier()-scheduler coordination, for that matter. Examples seem to be lacking. Most cases use locking. Here is one rather strange one from RCU: void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func) { unsigned long flags; bool needwake; bool havetask = READ_ONCE(rcu_tasks_kthread_ptr); rhp->next = NULL; rhp->func = func; raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags); needwake = !rcu_tasks_cbs_head; *rcu_tasks_cbs_tail = rhp; rcu_tasks_cbs_tail = &rhp->next; raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags); /* We can't create the thread unless interrupts are enabled. */ if ((needwake && havetask) || (!havetask && !irqs_disabled_flags(flags))) { rcu_spawn_tasks_kthread(); wake_up(&rcu_tasks_cbs_wq); } } And for the wait side, using synchronize_sched() to supply the barrier for both ends, with the preemption disabling due to raw_spin_lock_irqsave() serving as the read-side critical section: if (!list) { wait_event_interruptible(rcu_tasks_cbs_wq, rcu_tasks_cbs_head); if (!rcu_tasks_cbs_head) { WARN_ON(signal_pending(current)); schedule_timeout_interruptible(HZ/10); } continue; } synchronize_sched(); ----------------- Here is another one that uses atomic_cmpxchg() as a full memory barrier: if (!wait_event_timeout(*wait, !atomic_read(stopping), msecs_to_jiffies(1000))) { atomic_set(stopping, 0); smp_mb(); return -ETIMEDOUT; } int omap3isp_module_sync_is_stopping(wait_queue_head_t *wait, atomic_t *stopping) { if (atomic_cmpxchg(stopping, 1, 0)) { wake_up(wait); return 1; } return 0; }
Quoted 17 lines · Andrea Parri
Hi Paul,
Quoted 14 lines · Paul E. McKenney
Hello!
At Linux Plumbers Conference, we got requests for a recipes document, and a further request to point to actual code in the Linux kernel. I have pulled together some examples for various litmus-test families, as shown below. The decoder ring for the abbreviations (ISA2, LB, SB, MP, ...) is here:
https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdfThis document is also checked into the memory-models git archive:
Quoted 8 lines
Quoted 3 lines
I would be especially interested in simpler examples in general, and of course any example at all for the cases where I was unable to find any. Thoughts?
Below are some examples we did discuss (at some point):
The comment in kernel/events/ring_buffer.c:perf_output_put_handle() describes instances of MP+wmb+rmb and LB+ctrl+mb.
I added this as an alternative for MP and as the example for LB.
Quoted 2 lines
The comments in kernel/sched/core.c:try_to_wake_up() describes more instances of MP ("plus locking") and LB (see
finish_lock_switch()).
This one looks a bit more messy, so I will set it aside, for the moment, anyway.
Quoted 2 lines
The comment in kernel/sched/core.c:task_rq_lock() describes an ins- tance of MP+wmb+addr-acqpo.
This one also looks a bit messy, so I am setting it aside as well.
Quoted 2 lines
The comment in include/linux/wait.h:waitqueue_active() describes an instance of SB+mb+mb.
Very good, I took this as the generic pattern for the current pair of SB examples.
Quoted 2 lines
63cae12bce986("perf/core: Fixsys_perf_event_open()vs. hotplug") describes an instance of W+RWC+porel+mb+mb.
Well, this one certainly is of historical interest. After all, it might well be the first Linux-kernel commit containing a litmus test. ;-)
I put it in recipes-LKcode-63cae12bce986.txt and reference it from recipes-LKcode.txt.
Quoted 5 lines
[...]
I wish we could say "any barrier (explicit or implicit) in sources is accompanied by a comment mentioning the interested pattern...", but life is not always this simple. ;-)
Well, at least scripts/checkpatch.pl now complains if you try to add a new comment-free barrier. Not that these complaints are always paid attention to...
Thanx, Paul
Quoted 4 lines · Paul E. McKenney
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
Quoted 8 lines
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.
I'm not sure that single-variable SC can really be represented by an example. It gets used literally all over the kernel -- it's such a large part of the way we think about computer programs that we rely on it unconsciously.
For example, the very first function in the very first C source file in the kernel/ directory (namely, check_free_space() in kernel/acct.c) includes this code:
if (acct->active) {
u64 suspend = sbuf.f_blocks * SUSPEND;
do_div(suspend, 100);How do we know that the value which gets divided by 100 is sbuf.f_blocks * SUSPEND and not the random garbage which was stored in suspend's memory location before it was initialized? Answer:
per-variable SC.
Okay, maybe that's not really applicable, since it doesn't involve accesses to shared memory. Here's an example that does. get_futex_key() in kernel/futex.c calls READ_ONCE(page->mapping) twice. How do we know that the value retrieved by the second call was not stored _earlier_ than the value retrieved by the first call? Per-variable SC.
Quoted 3 lines
b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?
Pretty much any code that accesses the same shared variable twice on the same CPU could be an example of per-variable SC. But I don't think people would learn much by studying such examples.
Alan
Quoted 40 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
Quoted 8 lines
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.I'm not sure that single-variable SC can really be represented by an example. It gets used literally all over the kernel -- it's such a large part of the way we think about computer programs that we rely on it unconsciously.
For example, the very first function in the very first C source file in the
kernel/directory (namely,check_free_space()inkernel/acct.c) includes this code:if (acct->active) { u64 suspend = sbuf.f_blocks * SUSPEND; do_div(suspend, 100);How do we know that the value which gets divided by 100 is sbuf.f_blocks * SUSPEND and not the random garbage which was stored in suspend's memory location before it was initialized? Answer:
per-variable SC.Okay, maybe that's not really applicable, since it doesn't involve accesses to shared memory. Here's an example that does.
get_futex_key()inkernel/futex.ccallsREAD_ONCE(page->mapping)twice. How do we know that the value retrieved by the second call was not stored _earlier_ than the value retrieved by the first call? Per-variable SC.
Quoted 7 lines
Quoted 3 lines
b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?Pretty much any code that accesses the same shared variable twice on the same CPU could be an example of per-variable SC. But I don't think people would learn much by studying such examples.
Perhaps the recipes document should just baldly state that any execution having only one thread and/or having only one variable will be fully ordered?
Thanx, Paul
Quoted 45 lines · Paul E. McKenney
Quoted 44 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
This document lists the litmus-test patterns that we have been discussing, along with examples from the Linux kernel. This is intended to feed into the recipes document. All examples are from v4.13.
Quoted 8 lines
0. Single-variable SC.
a. Within a single CPU, the use of the ->dynticks_nmi_nesting
counter byrcu_nmi_enter()andrcu_nmi_exit()qualifies (seekernel/rcu/tree.c). The counter is accessed by interrupts and NMIs as well as by process-level code. This counter can be accessed by other CPUs, but only for debug output.I'm not sure that single-variable SC can really be represented by an example. It gets used literally all over the kernel -- it's such a large part of the way we think about computer programs that we rely on it unconsciously.
For example, the very first function in the very first C source file in the
kernel/directory (namely,check_free_space()inkernel/acct.c) includes this code:if (acct->active) { u64 suspend = sbuf.f_blocks * SUSPEND; do_div(suspend, 100);How do we know that the value which gets divided by 100 is sbuf.f_blocks * SUSPEND and not the random garbage which was stored in suspend's memory location before it was initialized? Answer:
per-variable SC.Okay, maybe that's not really applicable, since it doesn't involve accesses to shared memory. Here's an example that does.
get_futex_key()inkernel/futex.ccallsREAD_ONCE(page->mapping)twice. How do we know that the value retrieved by the second call was not stored _earlier_ than the value retrieved by the first call? Per-variable SC.Quoted 3 lines
b. Between CPUs, I would put forward the ->dflags
updates, but this is anything but simple. But maybe OK for an illustration?
Quoted 7 lines
Quoted 3 lines
Pretty much any code that accesses the same shared variable twice on the same CPU could be an example of per-variable SC. But I don't think people would learn much by studying such examples.
Perhaps the recipes document should just baldly state that any execution having only one thread and/or having only one variable will be fully ordered?
That wouldn't be a bad idea. (Although the part about only one thread should be pretty obvious.)
Also, you have to be a little careful because the ordering of the execution may not always agree with the ordering of the source code. The compiler is allowed to evaluate the arguments to a function call, for example, in any order it likes.
Alan
Quoted 3 lines · Alan Stern
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Alan Stern
On Wed, 11 Oct 2017, Paul E. McKenney wrote:
[ . . . ]
Quoted 11 lines
Quoted 3 lines
Perhaps the recipes document should just baldly state that any execution having only one thread and/or having only one variable will be fully ordered?
That wouldn't be a bad idea. (Although the part about only one thread should be pretty obvious.)
Also, you have to be a little careful because the ordering of the execution may not always agree with the ordering of the source code. The compiler is allowed to evaluate the arguments to a function call, for example, in any order it likes.
How about this?
0. Simple special cases
If there is only one CPU on the one hand or only one variable on the other, the code will execute in order. There are (as usual) some things to be careful of:
a. There are some aspects of the C language that are
unordered. For example, the compiler can output code computing arguments of a multi-parameter function in any order it likes, or even interleaved if it so chooses.
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.
c. If there is only one variable but multiple CPUs, all
accesses to that variable must be aligned and full sized. Variables that straddle cachelines or pages void your full-ordering warranty, as do undersized accesses that load from or store to only part of the variable.
Thanx, Paul
Quoted 4 lines · Paul E. McKenney
How about this?
0. Simple special cases
Quoted 8 lines
If there is only one CPU on the one hand or only one variable on the other, the code will execute in order. There are (as usual) some things to be careful of:
a. There are some aspects of the C language that are
unordered. For example, the compiler can output code computing arguments of a multi-parameter function in any order it likes, or even interleaved if it so chooses.
That parses a little oddly. I wouldn't agree that the compiler outputs the code in any order it likes!
In fact, I wouldn't even mention the compiler at all. Just say that (with a few exceptions) the language doesn't specify the order in which the arguments of a function or operation should be evaluated. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Quoted 2 lines
c. If there is only one variable but multiple CPUs, all
accesses to that variable must be aligned and full sized.
I would say that the variable is what needs to be aligned, not the accesses. (Although, if the variable is aligned and all the accesses are full sized, then they must necessarily be aligned as well.)
Quoted 3 lines
Variables that straddle cachelines or pages void your full-ordering warranty, as do undersized accesses that load from or store to only part of the variable.
How can a variable straddle pages without also straddling cache lines?
Alan
Quoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
How about this?
0. Simple special cases
If there is only one CPU on the one hand or only one variable on the other, the code will execute in order. There are (as usual) some things to be careful of:
Quoted 7 lines
Quoted 4 lines
a. There are some aspects of the C language that are
unordered. For example, the compiler can output code computing arguments of a multi-parameter function in any order it likes, or even interleaved if it so chooses.That parses a little oddly. I wouldn't agree that the compiler outputs the code in any order it likes!
When was the last time you talked to a compiler writer? ;-)
Quoted 6 lines
In fact, I wouldn't even mention the compiler at all. Just say that (with a few exceptions) the language doesn't specify the order in which the arguments of a function or operation should be evaluated. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Nevertheless, I took your suggestion:
a. There are some aspects of the C language that are
unordered. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Quoted 7 lines
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.
Quoted 5 lines
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Ah, I omitted an important qualifier:
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.
I have seen people (including kernel hackers) surprised by what optimizers do, so I would prefer that the last sentence remain.
Quoted 6 lines
Quoted 2 lines
c. If there is only one variable but multiple CPUs, all
accesses to that variable must be aligned and full sized.I would say that the variable is what needs to be aligned, not the accesses. (Although, if the variable is aligned and all the accesses are full sized, then they must necessarily be aligned as well.)
I was thinking in terms of an unaligned 16-bit access to a 32-bit variable. But how about this?
c. If there is only one variable but multiple CPUs, all
that variable must be properly aligned and all accesses to that variable must be full sized.
Quoted 5 lines
Quoted 3 lines
Variables that straddle cachelines or pages void your full-ordering warranty, as do undersized accesses that load from or store to only part of the variable.
How can a variable straddle pages without also straddling cache lines?
Well, a variable -can- straddle cachelines without straddling pages, which justifies the "or". Furthermore, given that cacheline sizes have been growing, but pages are still 4KB, it is probably only a matter of time. ;-)
Thanx, Paul
Quoted 28 lines · Paul E. McKenney
Quoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
How about this?
0. Simple special cases
If there is only one CPU on the one hand or only one variable on the other, the code will execute in order. There are (as usual) some things to be careful of:
Quoted 7 lines
Quoted 4 lines
a. There are some aspects of the C language that are
unordered. For example, the compiler can output code computing arguments of a multi-parameter function in any order it likes, or even interleaved if it so chooses.That parses a little oddly. I wouldn't agree that the compiler outputs the code in any order it likes!
When was the last time you talked to a compiler writer? ;-)
Quoted 6 lines
In fact, I wouldn't even mention the compiler at all. Just say that (with a few exceptions) the language doesn't specify the order in which the arguments of a function or operation should be evaluated. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Quoted 7 lines
Nevertheless, I took your suggestion:
a. There are some aspects of the C language that are
unordered. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Good.
Quoted 13 lines
Quoted 7 lines
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.Quoted 5 lines
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Quoted 8 lines
Ah, I omitted an important qualifier:
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.
That's okay for the single-CPU case. I don't think it covers the multiple-CPU single-variable case correctly, though. If you don't use READ_ONCE or WRITE_ONCE, isn't the compiler allowed to tear the loads and stores? And won't that potentially cause the end result to be different from what you would get if the code had appeared to execute in order?
Quoted 6 lines
I have seen people (including kernel hackers) surprised by what optimizers do, so I would prefer that the last sentence remain.
Quoted 3 lines
Quoted 2 lines
c. If there is only one variable but multiple CPUs, all
accesses to that variable must be aligned and full sized.
Quoted 6 lines
Quoted 3 lines
I would say that the variable is what needs to be aligned, not the accesses. (Although, if the variable is aligned and all the accesses are full sized, then they must necessarily be aligned as well.)
I was thinking in terms of an unaligned 16-bit access to a 32-bit variable.
That wouldn't be full sized.
Quoted 3 lines
But how about this?
c. If there is only one variable but multiple CPUs, all
Extra "all". Otherwise okay.
Quoted 7 lines
that variable must be properly aligned and all accesses to that variable must be full sized.
Quoted 4 lines
Quoted 3 lines
Variables that straddle cachelines or pages void your full-ordering warranty, as do undersized accesses that load from or store to only part of the variable.
Quoted 6 lines
Quoted 1 line
How can a variable straddle pages without also straddling cache lines?
Well, a variable -can- straddle cachelines without straddling pages, which justifies the "or". Furthermore, given that cacheline sizes have been growing, but pages are still 4KB, it is probably only a matter of time. ;-)
By that time, we'll probably be using 64-KB pages. Or even bigger!
Alan
Quoted 62 lines · Alan Stern
Quoted 28 lines · Paul E. McKenney
Quoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
How about this?
0. Simple special cases
If there is only one CPU on the one hand or only one variable on the other, the code will execute in order. There are (as usual) some things to be careful of:
Quoted 7 lines
Quoted 4 lines
a. There are some aspects of the C language that are
unordered. For example, the compiler can output code computing arguments of a multi-parameter function in any order it likes, or even interleaved if it so chooses.That parses a little oddly. I wouldn't agree that the compiler outputs the code in any order it likes!
When was the last time you talked to a compiler writer? ;-)
Quoted 6 lines
In fact, I wouldn't even mention the compiler at all. Just say that (with a few exceptions) the language doesn't specify the order in which the arguments of a function or operation should be evaluated. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.
Quoted 7 lines
Nevertheless, I took your suggestion:
a. There are some aspects of the C language that are
unordered. For example, in the expression "f(x) + g(y)", the order in which f and g are called is not defined; the object code is allowed to use either order or even to interleave the computations.Good.
Quoted 13 lines
Quoted 7 lines
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.Quoted 5 lines
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Quoted 8 lines
Ah, I omitted an important qualifier:
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.
Quoted 6 lines
That's okay for the single-CPU case. I don't think it covers the multiple-CPU single-variable case correctly, though. If you don't use
READ_ONCEorWRITE_ONCE, isn't the compiler allowed to tear the loads and stores? And won't that potentially cause the end result to be different from what you would get if the code had appeared to execute in order?
Ah, good point, I need yet another qualifier. How about the following?
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes for normal accesses, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.
I added "for normal accesses", which excludes READ_ONCE(), WRITE_ONCE(), and atomics. This, in conjunction with the previously added "single-threaded execution" means that yes, the compiler is permitted to tear normal loads and stores. The reason is that a single-threaded run could not tell the difference. Interrupt handlers or multiple threads are required to detect load/store tearing.
So, what am I still missing? ;-)
Quoted 13 lines
Quoted 6 lines
I have seen people (including kernel hackers) surprised by what optimizers do, so I would prefer that the last sentence remain.
Quoted 3 lines
Quoted 2 lines
c. If there is only one variable but multiple CPUs, all
accesses to that variable must be aligned and full sized.Quoted 6 lines
Quoted 3 lines
I would say that the variable is what needs to be aligned, not the accesses. (Although, if the variable is aligned and all the accesses are full sized, then they must necessarily be aligned as well.)
I was thinking in terms of an unaligned 16-bit access to a 32-bit variable.
Quoted 7 lines
That wouldn't be full sized.
Quoted 3 lines
But how about this?
c. If there is only one variable but multiple CPUs, all
Extra "all". Otherwise okay.
Good catch, I removed the extra "all".
Quoted 7 lines
Quoted 7 lines
that variable must be properly aligned and all accesses to that variable must be full sized.
Quoted 4 lines
Quoted 3 lines
Variables that straddle cachelines or pages void your full-ordering warranty, as do undersized accesses that load from or store to only part of the variable.
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
How can a variable straddle pages without also straddling cache lines?
Well, a variable -can- straddle cachelines without straddling pages, which justifies the "or". Furthermore, given that cacheline sizes have been growing, but pages are still 4KB, it is probably only a matter of time. ;-)
By that time, we'll probably be using 64-KB pages. Or even bigger!
PowerPC's server builds have had a minimum page size of 64KB for quite a few years. This helps in many cases, but of course hurts for those occasional application that insist on doing a pile of independent 4K mappings. ;-)
So I would guess that the move from 4K pages to 64K (or whatever) pages could be quite painful for some CPU families.
Thanx, Paul
Quoted 39 lines · Paul E. McKenney
Quoted 22 lines
Quoted 13 lines
Quoted 7 lines
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.Quoted 5 lines
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Quoted 8 lines
Ah, I omitted an important qualifier:
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.Quoted 6 lines
That's okay for the single-CPU case. I don't think it covers the multiple-CPU single-variable case correctly, though. If you don't use
READ_ONCEorWRITE_ONCE, isn't the compiler allowed to tear the loads and stores? And won't that potentially cause the end result to be different from what you would get if the code had appeared to execute in order?Ah, good point, I need yet another qualifier. How about the following?
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes for normal accesses, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.
Quoted 8 lines
I added "for normal accesses", which excludes
READ_ONCE(),WRITE_ONCE(), and atomics. This, in conjunction with the previously added "single-threaded execution" means that yes, the compiler is permitted to tear normal loads and stores. The reason is that a single-threaded run could not tell the difference. Interrupt handlers or multiple threads are required to detect load/store tearing.So, what am I still missing? ;-)
Well, you could explicitly mention that in the multi-thread case, this means all accesses to the shared variable had better use READ_ONCE() or WRITE_ONCE().
Alan
Quoted 48 lines · Alan Stern
Quoted 46 lines · Paul E. McKenney
Quoted 22 lines
Quoted 13 lines
Quoted 7 lines
Quoted 6 lines
b. Compilers are permitted to use the "as-if" rule.
That is, a compiler can emit whatever code it likes, as long as the results appear just as if the compiler had followed all the relevant rules. To see this, compiler with a high level of optimization and run the debugger on the resulting binary.Quoted 5 lines
You might omit the last sentence. Furthermore, if the accesses don't use READ_ONCE/WRITE_ONCE then the code might not get the same result as if it had executed in order (even for a single variable!), and if you do use READ_ONCE/WRITE_ONCE then the compiler can't emit whatever code it likes.
Quoted 8 lines
Ah, I omitted an important qualifier:
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.Quoted 6 lines
That's okay for the single-CPU case. I don't think it covers the multiple-CPU single-variable case correctly, though. If you don't use
READ_ONCEorWRITE_ONCE, isn't the compiler allowed to tear the loads and stores? And won't that potentially cause the end result to be different from what you would get if the code had appeared to execute in order?Ah, good point, I need yet another qualifier. How about the following?
b. Compilers are permitted to use the "as-if" rule. That is,
a compiler can emit whatever code it likes for normal accesses, as long as the results of a single-threaded execution appear just as if the compiler had followed all the relevant rules. To see this, compile with a high level of optimization and run the debugger on the resulting binary.I added "for normal accesses", which excludes
READ_ONCE(),WRITE_ONCE(), and atomics. This, in conjunction with the previously added "single-threaded execution" means that yes, the compiler is permitted to tear normal loads and stores. The reason is that a single-threaded run could not tell the difference. Interrupt handlers or multiple threads are required to detect load/store tearing.
Quoted 5 lines
Quoted 1 line
So, what am I still missing? ;-)
Well, you could explicitly mention that in the multi-thread case, this means all accesses to the shared variable had better use
READ_ONCE()orWRITE_ONCE().
Like this?
Thanx, Paul
------------------------------------------------------------------------
d. If there are multiple CPUs, accesses to shared variables
should use READ_ONCE() and WRITE_ONCE() or stronger to prevent load/store tearing, load/store fusing, and invented loads and stores. There are exceptions to this rule, for example:
i. When there is no possibility of a given
shared variable being updated, for example, while holding the update-side lock, reads from that variable need not use READ_ONCE().
ii. When there is no possibility of a given shared
variable being either read or updated, for example, when running during early boot, reads from that variable need not use READ_ONCE() and writes to that variable need not use WRITE_ONCE().
Quoted 21 lines · Paul E. McKenney
Quoted 3 lines
Well, you could explicitly mention that in the multi-thread case, this means all accesses to the shared variable had better use
READ_ONCE()orWRITE_ONCE().Like this?
Thanx, Paul
------------------------------------------------------------------------
d. If there are multiple CPUs, accesses to shared variables
should useREAD_ONCE()andWRITE_ONCE()or stronger to prevent load/store tearing, load/store fusing, and invented loads and stores. There are exceptions to this rule, for example:i. When there is no possibility of a given
shared variable being updated, for example, while holding the update-side lock, reads from that variable need not useREAD_ONCE().
Quoted 5 lines
ii. When there is no possibility of a given shared
variable being either read or updated, for example, when running during early boot, reads from that variable need not useREAD_ONCE()and writes to that variable need not useWRITE_ONCE().
Yeah, except that you mean being read or updated by another thread.
Alan
Quoted 23 lines · Alan Stern
Quoted 21 lines · Paul E. McKenney
Quoted 3 lines
Well, you could explicitly mention that in the multi-thread case, this means all accesses to the shared variable had better use
READ_ONCE()orWRITE_ONCE().Like this?
Thanx, Paul
------------------------------------------------------------------------
d. If there are multiple CPUs, accesses to shared variables
should useREAD_ONCE()andWRITE_ONCE()or stronger to prevent load/store tearing, load/store fusing, and invented loads and stores. There are exceptions to this rule, for example:i. When there is no possibility of a given
shared variable being updated, for example, while holding the update-side lock, reads from that variable need not useREAD_ONCE().
Quoted 7 lines
Quoted 5 lines
ii. When there is no possibility of a given shared
variable being either read or updated, for example, when running during early boot, reads from that variable need not useREAD_ONCE()and writes to that variable need not useWRITE_ONCE().Yeah, except that you mean being read or updated by another thread.
Good point, added that qualifier.
Thanx, Paul