| 1 | |
| 2 |
|
| 3 | ======================================
|
| 4 | Sequence counters and sequential locks
|
| 5 | ======================================
|
| 6 |
|
| 7 | Introduction
|
| 8 | ============
|
| 9 |
|
| 10 | Sequence counters are a reader-writer consistency mechanism with
|
| 11 | lockless readers (read-only retry loops), and no writer starvation. They
|
| 12 | are used for data that's rarely written to (e.g. system time), where the
|
| 13 | reader wants a consistent set of information and is willing to retry if
|
| 14 | that information changes.
|
| 15 |
|
| 16 | A data set is consistent when the sequence count at the beginning of the
|
| 17 | read side critical section is even and the same sequence count value is
|
| 18 | read again at the end of the critical section. The data in the set must
|
| 19 | be copied out inside the read side critical section. If the sequence
|
| 20 | count has changed between the start and the end of the critical section,
|
| 21 | the reader must retry.
|
| 22 |
|
| 23 | Writers increment the sequence count at the start and the end of their
|
| 24 | critical section. After starting the critical section the sequence count
|
| 25 | is odd and indicates to the readers that an update is in progress. At
|
| 26 | the end of the write side critical section the sequence count becomes
|
| 27 | even again which lets readers make progress.
|
| 28 |
|
| 29 | A sequence counter write side critical section must never be preempted
|
| 30 | or interrupted by read side sections. Otherwise the reader will spin for
|
| 31 | the entire scheduler tick due to the odd sequence count value and the
|
| 32 | interrupted writer. If that reader belongs to a real-time scheduling
|
| 33 | class, it can spin forever and the kernel will livelock.
|
| 34 |
|
| 35 | This mechanism cannot be used if the protected data contains pointers,
|
| 36 | as the writer can invalidate a pointer that the reader is following.
|
| 37 |
|
| 38 |
|
| 39 | .. _seqcount_t:
|
| 40 |
|
| 41 | Sequence counters (``seqcount_t``)
|
| 42 | ==================================
|
| 43 |
|
| 44 | This is the raw counting mechanism, which does not protect against
|
| 45 | multiple writers. Write side critical sections must thus be serialized
|
| 46 | by an external lock.
|
| 47 |
|
| 48 | If the write serialization primitive is not implicitly disabling
|
| 49 | preemption, preemption must be explicitly disabled before entering the
|
| 50 | write side section. If the read section can be invoked from hardirq or
|
| 51 | softirq contexts, interrupts or bottom halves must also be respectively
|
| 52 | disabled before entering the write section.
|
| 53 |
|
| 54 | If it's desired to automatically handle the sequence counter
|
| 55 | requirements of writer serialization and non-preemptibility, use
|
| 56 | :ref:`seqlock_t` instead.
|
| 57 |
|
| 58 | Initialization::
|
| 59 |
|
| 60 | /* dynamic */
|
| 61 | seqcount_t foo_seqcount;
|
| 62 | seqcount_init(&foo_seqcount);
|
| 63 |
|
| 64 | /* static */
|
| 65 | static seqcount_t foo_seqcount = SEQCNT_ZERO(foo_seqcount);
|
| 66 |
|
| 67 | /* C99 struct init */
|
| 68 | struct {
|
| 69 | .seq = SEQCNT_ZERO(foo.seq),
|
| 70 | } foo;
|
| 71 |
|
| 72 | Write path::
|
| 73 |
|
| 74 | /* Serialized context with disabled preemption */
|
| 75 |
|
| 76 | write_seqcount_begin(&foo_seqcount);
|
| 77 |
|
| 78 | /* ... [[write-side critical section]] ... */
|
| 79 |
|
| 80 | write_seqcount_end(&foo_seqcount);
|
| 81 |
|
| 82 | Read path::
|
| 83 |
|
| 84 | do {
|
| 85 | seq = read_seqcount_begin(&foo_seqcount);
|
| 86 |
|
| 87 | /* ... [[read-side critical section]] ... */
|
| 88 |
|
| 89 | } while (read_seqcount_retry(&foo_seqcount, seq));
|
| 90 |
|
| 91 |
|
| 92 | .. _seqcount_locktype_t:
|
| 93 |
|
| 94 | Sequence counters with associated locks (``seqcount_LOCKNAME_t``)
|
| 95 | -----------------------------------------------------------------
|
| 96 |
|
| 97 | As discussed at :ref:`seqcount_t`, sequence count write side critical
|
| 98 | sections must be serialized and non-preemptible. This variant of
|
| 99 | sequence counters associate the lock used for writer serialization at
|
| 100 | initialization time, which enables lockdep to validate that the write
|
| 101 | side critical sections are properly serialized.
|
| 102 |
|
| 103 | This lock association is a NOOP if lockdep is disabled and has neither
|
| 104 | storage nor runtime overhead. If lockdep is enabled, the lock pointer is
|
| 105 | stored in struct seqcount and lockdep's "lock is held" assertions are
|
| 106 | injected at the beginning of the write side critical section to validate
|
| 107 | that it is properly protected.
|
| 108 |
|
| 109 | For lock types which do not implicitly disable preemption, preemption
|
| 110 | protection is enforced in the write side function.
|
| 111 |
|
| 112 | The following sequence counters with associated locks are defined:
|
| 113 |
|
| 114 | - ``seqcount_spinlock_t``
|
| 115 | - ``seqcount_raw_spinlock_t``
|
| 116 | - ``seqcount_rwlock_t``
|
| 117 | - ``seqcount_mutex_t``
|
| 118 | - ``seqcount_ww_mutex_t``
|
| 119 |
|
| 120 | The sequence counter read and write APIs can take either a plain
|
| 121 | seqcount_t or any of the seqcount_LOCKNAME_t variants above.
|
| 122 |
|
| 123 | Initialization (replace "LOCKNAME" with one of the supported locks)::
|
| 124 |
|
| 125 | /* dynamic */
|
| 126 | seqcount_LOCKNAME_t foo_seqcount;
|
| 127 | seqcount_LOCKNAME_init(&foo_seqcount, &lock);
|
| 128 |
|
| 129 | /* static */
|
| 130 | static seqcount_LOCKNAME_t foo_seqcount =
|
| 131 | SEQCNT_LOCKNAME_ZERO(foo_seqcount, &lock);
|
| 132 |
|
| 133 | /* C99 struct init */
|
| 134 | struct {
|
| 135 | .seq = SEQCNT_LOCKNAME_ZERO(foo.seq, &lock),
|
| 136 | } foo;
|
| 137 |
|
| 138 | Write path: same as in :ref:`seqcount_t`, while running from a context
|
| 139 | with the associated write serialization lock acquired.
|
| 140 |
|
| 141 | Read path: same as in :ref:`seqcount_t`.
|
| 142 |
|
| 143 |
|
| 144 | .. _seqcount_latch_t:
|
| 145 |
|
| 146 | Latch sequence counters (``seqcount_latch_t``)
|
| 147 | ----------------------------------------------
|
| 148 |
|
| 149 | Latch sequence counters are a multiversion concurrency control mechanism
|
| 150 | where the embedded seqcount_t counter even/odd value is used to switch
|
| 151 | between two copies of protected data. This allows the sequence counter
|
| 152 | read path to safely interrupt its own write side critical section.
|
| 153 |
|
| 154 | Use seqcount_latch_t when the write side sections cannot be protected
|
| 155 | from interruption by readers. This is typically the case when the read
|
| 156 | side can be invoked from NMI handlers.
|
| 157 |
|
| 158 | Check `write_seqcount_latch()` for more information.
|
| 159 |
|
| 160 |
|
| 161 | .. _seqlock_t:
|
| 162 |
|
| 163 | Sequential locks (``seqlock_t``)
|
| 164 | ================================
|
| 165 |
|
| 166 | This contains the :ref:`seqcount_t` mechanism earlier discussed, plus an
|
| 167 | embedded spinlock for writer serialization and non-preemptibility.
|
| 168 |
|
| 169 | If the read side section can be invoked from hardirq or softirq context,
|
| 170 | use the write side function variants which disable interrupts or bottom
|
| 171 | halves respectively.
|
| 172 |
|
| 173 | Initialization::
|
| 174 |
|
| 175 | /* dynamic */
|
| 176 | seqlock_t foo_seqlock;
|
| 177 | seqlock_init(&foo_seqlock);
|
| 178 |
|
| 179 | /* static */
|
| 180 | static DEFINE_SEQLOCK(foo_seqlock);
|
| 181 |
|
| 182 | /* C99 struct init */
|
| 183 | struct {
|
| 184 | .seql = __SEQLOCK_UNLOCKED(foo.seql)
|
| 185 | } foo;
|
| 186 |
|
| 187 | Write path::
|
| 188 |
|
| 189 | write_seqlock(&foo_seqlock);
|
| 190 |
|
| 191 | /* ... [[write-side critical section]] ... */
|
| 192 |
|
| 193 | write_sequnlock(&foo_seqlock);
|
| 194 |
|
| 195 | Read path, three categories:
|
| 196 |
|
| 197 | 1. Normal Sequence readers which never block a writer but they must
|
| 198 | retry if a writer is in progress by detecting change in the sequence
|
| 199 | number. Writers do not wait for a sequence reader::
|
| 200 |
|
| 201 | do {
|
| 202 | seq = read_seqbegin(&foo_seqlock);
|
| 203 |
|
| 204 | /* ... [[read-side critical section]] ... */
|
| 205 |
|
| 206 | } while (read_seqretry(&foo_seqlock, seq));
|
| 207 |
|
| 208 | 2. Locking readers which will wait if a writer or another locking reader
|
| 209 | is in progress. A locking reader in progress will also block a writer
|
| 210 | from entering its critical section. This read lock is
|
| 211 | exclusive. Unlike rwlock_t, only one locking reader can acquire it::
|
| 212 |
|
| 213 | read_seqlock_excl(&foo_seqlock);
|
| 214 |
|
| 215 | /* ... [[read-side critical section]] ... */
|
| 216 |
|
| 217 | read_sequnlock_excl(&foo_seqlock);
|
| 218 |
|
| 219 | 3. Conditional lockless reader (as in 1), or locking reader (as in 2),
|
| 220 | according to a passed marker. This is used to avoid lockless readers
|
| 221 | starvation (too much retry loops) in case of a sharp spike in write
|
| 222 | activity. First, a lockless read is tried (even marker passed). If
|
| 223 | that trial fails (sequence counter doesn't match), make the marker
|
| 224 | odd for the next iteration, the lockless read is transformed to a
|
| 225 | full locking read and no retry loop is necessary, for example::
|
| 226 |
|
| 227 | /* marker; even initialization */
|
| 228 | int seq = 1;
|
| 229 | do {
|
| 230 | seq++; /* 2 on the 1st/lockless path, otherwise odd */
|
| 231 | read_seqbegin_or_lock(&foo_seqlock, &seq);
|
| 232 |
|
| 233 | /* ... [[read-side critical section]] ... */
|
| 234 |
|
| 235 | } while (need_seqretry(&foo_seqlock, seq));
|
| 236 | done_seqretry(&foo_seqlock, seq);
|
| 237 |
|
| 238 |
|
| 239 | API documentation
|
| 240 | =================
|
| 241 |
|
| 242 | .. kernel-doc:: include/linux/seqlock.h
|