1 ======================================
2 Sequence counters and sequential locks
3 ======================================
8 Sequence counters are a reader-writer consistency mechanism with
9 lockless readers (read-only retry loops), and no writer starvation. They
10 are used for data that's rarely written to (e.g. system time), where the
11 reader wants a consistent set of information and is willing to retry if
12 that information changes.
14 A data set is consistent when the sequence count at the beginning of the
15 read side critical section is even and the same sequence count value is
16 read again at the end of the critical section. The data in the set must
17 be copied out inside the read side critical section. If the sequence
18 count has changed between the start and the end of the critical section,
19 the reader must retry.
21 Writers increment the sequence count at the start and the end of their
22 critical section. After starting the critical section the sequence count
23 is odd and indicates to the readers that an update is in progress. At
24 the end of the write side critical section the sequence count becomes
25 even again which lets readers make progress.
27 A sequence counter write side critical section must never be preempted
28 or interrupted by read side sections. Otherwise the reader will spin for
29 the entire scheduler tick due to the odd sequence count value and the
30 interrupted writer. If that reader belongs to a real-time scheduling
31 class, it can spin forever and the kernel will livelock.
33 This mechanism cannot be used if the protected data contains pointers,
34 as the writer can invalidate a pointer that the reader is following.
39 Sequence counters (``seqcount_t``)
40 ==================================
42 This is the the raw counting mechanism, which does not protect against
43 multiple writers. Write side critical sections must thus be serialized
46 If the write serialization primitive is not implicitly disabling
47 preemption, preemption must be explicitly disabled before entering the
48 write side section. If the read section can be invoked from hardirq or
49 softirq contexts, interrupts or bottom halves must also be respectively
50 disabled before entering the write section.
52 If it's desired to automatically handle the sequence counter
53 requirements of writer serialization and non-preemptibility, use
54 :ref:`seqlock_t` instead.
59 seqcount_t foo_seqcount;
60 seqcount_init(&foo_seqcount);
63 static seqcount_t foo_seqcount = SEQCNT_ZERO(foo_seqcount);
67 .seq = SEQCNT_ZERO(foo.seq),
72 /* Serialized context with disabled preemption */
74 write_seqcount_begin(&foo_seqcount);
76 /* ... [[write-side critical section]] ... */
78 write_seqcount_end(&foo_seqcount);
83 seq = read_seqcount_begin(&foo_seqcount);
85 /* ... [[read-side critical section]] ... */
87 } while (read_seqcount_retry(&foo_seqcount, seq));
90 .. _seqcount_locktype_t:
92 Sequence counters with associated locks (``seqcount_LOCKTYPE_t``)
93 -----------------------------------------------------------------
95 As discussed at :ref:`seqcount_t`, sequence count write side critical
96 sections must be serialized and non-preemptible. This variant of
97 sequence counters associate the lock used for writer serialization at
98 initialization time, which enables lockdep to validate that the write
99 side critical sections are properly serialized.
101 This lock association is a NOOP if lockdep is disabled and has neither
102 storage nor runtime overhead. If lockdep is enabled, the lock pointer is
103 stored in struct seqcount and lockdep's "lock is held" assertions are
104 injected at the beginning of the write side critical section to validate
105 that it is properly protected.
107 For lock types which do not implicitly disable preemption, preemption
108 protection is enforced in the write side function.
110 The following sequence counters with associated locks are defined:
112 - ``seqcount_spinlock_t``
113 - ``seqcount_raw_spinlock_t``
114 - ``seqcount_rwlock_t``
115 - ``seqcount_mutex_t``
116 - ``seqcount_ww_mutex_t``
118 The plain seqcount read and write APIs branch out to the specific
119 seqcount_LOCKTYPE_t implementation at compile-time. This avoids kernel
120 API explosion per each new seqcount LOCKTYPE.
122 Initialization (replace "LOCKTYPE" with one of the supported locks)::
125 seqcount_LOCKTYPE_t foo_seqcount;
126 seqcount_LOCKTYPE_init(&foo_seqcount, &lock);
129 static seqcount_LOCKTYPE_t foo_seqcount =
130 SEQCNT_LOCKTYPE_ZERO(foo_seqcount, &lock);
132 /* C99 struct init */
134 .seq = SEQCNT_LOCKTYPE_ZERO(foo.seq, &lock),
137 Write path: same as in :ref:`seqcount_t`, while running from a context
138 with the associated LOCKTYPE lock acquired.
140 Read path: same as in :ref:`seqcount_t`.
143 .. _seqcount_latch_t:
145 Latch sequence counters (``seqcount_latch_t``)
146 ----------------------------------------------
148 Latch sequence counters are a multiversion concurrency control mechanism
149 where the embedded seqcount_t counter even/odd value is used to switch
150 between two copies of protected data. This allows the sequence counter
151 read path to safely interrupt its own write side critical section.
153 Use seqcount_latch_t when the write side sections cannot be protected
154 from interruption by readers. This is typically the case when the read
155 side can be invoked from NMI handlers.
157 Check `raw_write_seqcount_latch()` for more information.
162 Sequential locks (``seqlock_t``)
163 ================================
165 This contains the :ref:`seqcount_t` mechanism earlier discussed, plus an
166 embedded spinlock for writer serialization and non-preemptibility.
168 If the read side section can be invoked from hardirq or softirq context,
169 use the write side function variants which disable interrupts or bottom
175 seqlock_t foo_seqlock;
176 seqlock_init(&foo_seqlock);
179 static DEFINE_SEQLOCK(foo_seqlock);
181 /* C99 struct init */
183 .seql = __SEQLOCK_UNLOCKED(foo.seql)
188 write_seqlock(&foo_seqlock);
190 /* ... [[write-side critical section]] ... */
192 write_sequnlock(&foo_seqlock);
194 Read path, three categories:
196 1. Normal Sequence readers which never block a writer but they must
197 retry if a writer is in progress by detecting change in the sequence
198 number. Writers do not wait for a sequence reader::
201 seq = read_seqbegin(&foo_seqlock);
203 /* ... [[read-side critical section]] ... */
205 } while (read_seqretry(&foo_seqlock, seq));
207 2. Locking readers which will wait if a writer or another locking reader
208 is in progress. A locking reader in progress will also block a writer
209 from entering its critical section. This read lock is
210 exclusive. Unlike rwlock_t, only one locking reader can acquire it::
212 read_seqlock_excl(&foo_seqlock);
214 /* ... [[read-side critical section]] ... */
216 read_sequnlock_excl(&foo_seqlock);
218 3. Conditional lockless reader (as in 1), or locking reader (as in 2),
219 according to a passed marker. This is used to avoid lockless readers
220 starvation (too much retry loops) in case of a sharp spike in write
221 activity. First, a lockless read is tried (even marker passed). If
222 that trial fails (odd sequence counter is returned, which is used as
223 the next iteration marker), the lockless read is transformed to a
224 full locking read and no retry loop is necessary::
226 /* marker; even initialization */
229 read_seqbegin_or_lock(&foo_seqlock, &seq);
231 /* ... [[read-side critical section]] ... */
233 } while (need_seqretry(&foo_seqlock, seq));
234 done_seqretry(&foo_seqlock, seq);
240 .. kernel-doc:: include/linux/seqlock.h