Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
7.8 kB · 242 lines
at master
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243.. SPDX-License-Identifier: GPL-2.0
======================================Sequence counters and sequential locks======================================
Introduction============
Sequence counters are a reader-writer consistency mechanism withlockless readers (read-only retry loops), and no writer starvation. Theyare used for data that's rarely written to (e.g. system time), where thereader wants a consistent set of information and is willing to retry ifthat information changes.
A data set is consistent when the sequence count at the beginning of theread side critical section is even and the same sequence count value isread again at the end of the critical section. The data in the set mustbe copied out inside the read side critical section. If the sequencecount has changed between the start and the end of the critical section,the reader must retry.
Writers increment the sequence count at the start and the end of theircritical section. After starting the critical section the sequence countis odd and indicates to the readers that an update is in progress. Atthe end of the write side critical section the sequence count becomeseven again which lets readers make progress.
A sequence counter write side critical section must never be preemptedor interrupted by read side sections. Otherwise the reader will spin forthe entire scheduler tick due to the odd sequence count value and theinterrupted writer. If that reader belongs to a real-time schedulingclass, it can spin forever and the kernel will livelock.
This mechanism cannot be used if the protected data contains pointers,as the writer can invalidate a pointer that the reader is following.
.. _seqcount_t:
Sequence counters (``seqcount_t``)==================================
This is the raw counting mechanism, which does not protect againstmultiple writers. Write side critical sections must thus be serializedby an external lock.
If the write serialization primitive is not implicitly disablingpreemption, preemption must be explicitly disabled before entering thewrite side section. If the read section can be invoked from hardirq orsoftirq contexts, interrupts or bottom halves must also be respectivelydisabled before entering the write section.
If it's desired to automatically handle the sequence counterrequirements of writer serialization and non-preemptibility, use:ref:`seqlock_t` instead.
Initialization::
/* dynamic */ seqcount_t foo_seqcount; seqcount_init(&foo_seqcount);
/* static */ static seqcount_t foo_seqcount = SEQCNT_ZERO(foo_seqcount);
/* C99 struct init */ struct { .seq = SEQCNT_ZERO(foo.seq), } foo;
Write path::
/* Serialized context with disabled preemption */
write_seqcount_begin(&foo_seqcount);
/* ... [[write-side critical section]] ... */
write_seqcount_end(&foo_seqcount);
Read path::
do { seq = read_seqcount_begin(&foo_seqcount);
/* ... [[read-side critical section]] ... */
} while (read_seqcount_retry(&foo_seqcount, seq));
.. _seqcount_locktype_t:
Sequence counters with associated locks (``seqcount_LOCKNAME_t``)-----------------------------------------------------------------
As discussed at :ref:`seqcount_t`, sequence count write side criticalsections must be serialized and non-preemptible. This variant ofsequence counters associate the lock used for writer serialization atinitialization time, which enables lockdep to validate that the writeside critical sections are properly serialized.
This lock association is a NOOP if lockdep is disabled and has neitherstorage nor runtime overhead. If lockdep is enabled, the lock pointer isstored in struct seqcount and lockdep's "lock is held" assertions areinjected at the beginning of the write side critical section to validatethat it is properly protected.
For lock types which do not implicitly disable preemption, preemptionprotection is enforced in the write side function.
The following sequence counters with associated locks are defined:
- ``seqcount_spinlock_t`` - ``seqcount_raw_spinlock_t`` - ``seqcount_rwlock_t`` - ``seqcount_mutex_t`` - ``seqcount_ww_mutex_t``
The sequence counter read and write APIs can take either a plainseqcount_t or any of the seqcount_LOCKNAME_t variants above.
Initialization (replace "LOCKNAME" with one of the supported locks)::
/* dynamic */ seqcount_LOCKNAME_t foo_seqcount; seqcount_LOCKNAME_init(&foo_seqcount, &lock);
/* static */ static seqcount_LOCKNAME_t foo_seqcount = SEQCNT_LOCKNAME_ZERO(foo_seqcount, &lock);
/* C99 struct init */ struct { .seq = SEQCNT_LOCKNAME_ZERO(foo.seq, &lock), } foo;
Write path: same as in :ref:`seqcount_t`, while running from a contextwith the associated write serialization lock acquired.
Read path: same as in :ref:`seqcount_t`.
.. _seqcount_latch_t:
Latch sequence counters (``seqcount_latch_t``)----------------------------------------------
Latch sequence counters are a multiversion concurrency control mechanismwhere the embedded seqcount_t counter even/odd value is used to switchbetween two copies of protected data. This allows the sequence counterread path to safely interrupt its own write side critical section.
Use seqcount_latch_t when the write side sections cannot be protectedfrom interruption by readers. This is typically the case when the readside can be invoked from NMI handlers.
Check `write_seqcount_latch()` for more information.
.. _seqlock_t:
Sequential locks (``seqlock_t``)================================
This contains the :ref:`seqcount_t` mechanism earlier discussed, plus anembedded spinlock for writer serialization and non-preemptibility.
If the read side section can be invoked from hardirq or softirq context,use the write side function variants which disable interrupts or bottomhalves respectively.
Initialization::
/* dynamic */ seqlock_t foo_seqlock; seqlock_init(&foo_seqlock);
/* static */ static DEFINE_SEQLOCK(foo_seqlock);
/* C99 struct init */ struct { .seql = __SEQLOCK_UNLOCKED(foo.seql) } foo;
Write path::
write_seqlock(&foo_seqlock);
/* ... [[write-side critical section]] ... */
write_sequnlock(&foo_seqlock);
Read path, three categories:
1. Normal Sequence readers which never block a writer but they must retry if a writer is in progress by detecting change in the sequence number. Writers do not wait for a sequence reader::
do { seq = read_seqbegin(&foo_seqlock);
/* ... [[read-side critical section]] ... */
} while (read_seqretry(&foo_seqlock, seq));
2. Locking readers which will wait if a writer or another locking reader is in progress. A locking reader in progress will also block a writer from entering its critical section. This read lock is exclusive. Unlike rwlock_t, only one locking reader can acquire it::
read_seqlock_excl(&foo_seqlock);
/* ... [[read-side critical section]] ... */
read_sequnlock_excl(&foo_seqlock);
3. Conditional lockless reader (as in 1), or locking reader (as in 2), according to a passed marker. This is used to avoid lockless readers starvation (too much retry loops) in case of a sharp spike in write activity. First, a lockless read is tried (even marker passed). If that trial fails (sequence counter doesn't match), make the marker odd for the next iteration, the lockless read is transformed to a full locking read and no retry loop is necessary, for example::
/* marker; even initialization */ int seq = 1; do { seq++; /* 2 on the 1st/lockless path, otherwise odd */ read_seqbegin_or_lock(&foo_seqlock, &seq);
/* ... [[read-side critical section]] ... */
} while (need_seqretry(&foo_seqlock, seq)); done_seqretry(&foo_seqlock, seq);
API documentation=================
.. kernel-doc:: include/linux/seqlock.h