Branch data Line data Source code
1 : : #ifndef __LINUX_SEQLOCK_H
2 : : #define __LINUX_SEQLOCK_H
3 : : /*
4 : : * Reader/writer consistent mechanism without starving writers. This type of
5 : : * lock for data where the reader wants a consistent set of information
6 : : * and is willing to retry if the information changes. There are two types
7 : : * of readers:
8 : : * 1. Sequence readers which never block a writer but they may have to retry
9 : : * if a writer is in progress by detecting change in sequence number.
10 : : * Writers do not wait for a sequence reader.
11 : : * 2. Locking readers which will wait if a writer or another locking reader
12 : : * is in progress. A locking reader in progress will also block a writer
13 : : * from going forward. Unlike the regular rwlock, the read lock here is
14 : : * exclusive so that only one locking reader can get it.
15 : : *
16 : : * This is not as cache friendly as brlock. Also, this may not work well
17 : : * for data that contains pointers, because any writer could
18 : : * invalidate a pointer that a reader was following.
19 : : *
20 : : * Expected non-blocking reader usage:
21 : : * do {
22 : : * seq = read_seqbegin(&foo);
23 : : * ...
24 : : * } while (read_seqretry(&foo, seq));
25 : : *
26 : : *
27 : : * On non-SMP the spin locks disappear but the writer still needs
28 : : * to increment the sequence variables because an interrupt routine could
29 : : * change the state of the data.
30 : : *
31 : : * Based on x86_64 vsyscall gettimeofday
32 : : * by Keith Owens and Andrea Arcangeli
33 : : */
34 : :
35 : : #include <linux/spinlock.h>
36 : : #include <linux/preempt.h>
37 : : #include <linux/lockdep.h>
38 : : #include <asm/processor.h>
39 : :
40 : : /*
41 : : * Version using sequence counter only.
42 : : * This can be used when code has its own mutex protecting the
43 : : * updating starting before the write_seqcountbeqin() and ending
44 : : * after the write_seqcount_end().
45 : : */
46 : : typedef struct seqcount {
47 : : unsigned sequence;
48 : : #ifdef CONFIG_DEBUG_LOCK_ALLOC
49 : : struct lockdep_map dep_map;
50 : : #endif
51 : : } seqcount_t;
52 : :
53 : : static inline void __seqcount_init(seqcount_t *s, const char *name,
54 : : struct lock_class_key *key)
55 : : {
56 : : /*
57 : : * Make sure we are not reinitializing a held lock:
58 : : */
59 : : lockdep_init_map(&s->dep_map, name, key, 0);
60 : 5657851 : s->sequence = 0;
61 : : }
62 : :
63 : : #ifdef CONFIG_DEBUG_LOCK_ALLOC
64 : : # define SEQCOUNT_DEP_MAP_INIT(lockname) \
65 : : .dep_map = { .name = #lockname } \
66 : :
67 : : # define seqcount_init(s) \
68 : : do { \
69 : : static struct lock_class_key __key; \
70 : : __seqcount_init((s), #s, &__key); \
71 : : } while (0)
72 : :
73 : : static inline void seqcount_lockdep_reader_access(const seqcount_t *s)
74 : : {
75 : : seqcount_t *l = (seqcount_t *)s;
76 : : unsigned long flags;
77 : :
78 : : local_irq_save(flags);
79 : : seqcount_acquire_read(&l->dep_map, 0, 0, _RET_IP_);
80 : : seqcount_release(&l->dep_map, 1, _RET_IP_);
81 : : local_irq_restore(flags);
82 : : }
83 : :
84 : : #else
85 : : # define SEQCOUNT_DEP_MAP_INIT(lockname)
86 : : # define seqcount_init(s) __seqcount_init(s, NULL, NULL)
87 : : # define seqcount_lockdep_reader_access(x)
88 : : #endif
89 : :
90 : : #define SEQCNT_ZERO(lockname) { .sequence = 0, SEQCOUNT_DEP_MAP_INIT(lockname)}
91 : :
92 : :
93 : : /**
94 : : * __read_seqcount_begin - begin a seq-read critical section (without barrier)
95 : : * @s: pointer to seqcount_t
96 : : * Returns: count to be passed to read_seqcount_retry
97 : : *
98 : : * __read_seqcount_begin is like read_seqcount_begin, but has no smp_rmb()
99 : : * barrier. Callers should ensure that smp_rmb() or equivalent ordering is
100 : : * provided before actually loading any of the variables that are to be
101 : : * protected in this critical section.
102 : : *
103 : : * Use carefully, only in critical code, and comment how the barrier is
104 : : * provided.
105 : : */
106 : : static inline unsigned __read_seqcount_begin(const seqcount_t *s)
107 : : {
108 : : unsigned ret;
109 : :
110 : : repeat:
111 : 465892156 : ret = ACCESS_ONCE(s->sequence);
112 [ + + ][ + + ]: 465892156 : if (unlikely(ret & 1)) {
[ + + ][ + + ]
[ + + ][ - + ]
[ + + ][ - + ]
[ + + ][ - + ]
[ - + ][ - + ]
[ + + ][ + + ]
113 : 923968 : cpu_relax();
114 : : goto repeat;
115 : : }
116 : : return ret;
117 : : }
118 : :
119 : : /**
120 : : * raw_read_seqcount_begin - start seq-read critical section w/o lockdep
121 : : * @s: pointer to seqcount_t
122 : : * Returns: count to be passed to read_seqcount_retry
123 : : *
124 : : * raw_read_seqcount_begin opens a read critical section of the given
125 : : * seqcount, but without any lockdep checking. Validity of the critical
126 : : * section is tested by checking read_seqcount_retry function.
127 : : */
128 : : static inline unsigned raw_read_seqcount_begin(const seqcount_t *s)
129 : : {
130 : : unsigned ret = __read_seqcount_begin(s);
131 : 453653722 : smp_rmb();
132 : : return ret;
133 : : }
134 : :
135 : : /**
136 : : * read_seqcount_begin - begin a seq-read critical section
137 : : * @s: pointer to seqcount_t
138 : : * Returns: count to be passed to read_seqcount_retry
139 : : *
140 : : * read_seqcount_begin opens a read critical section of the given seqcount.
141 : : * Validity of the critical section is tested by checking read_seqcount_retry
142 : : * function.
143 : : */
144 : : static inline unsigned read_seqcount_begin(const seqcount_t *s)
145 : : {
146 : : seqcount_lockdep_reader_access(s);
147 : : return raw_read_seqcount_begin(s);
148 : : }
149 : :
150 : : /**
151 : : * raw_seqcount_begin - begin a seq-read critical section
152 : : * @s: pointer to seqcount_t
153 : : * Returns: count to be passed to read_seqcount_retry
154 : : *
155 : : * raw_seqcount_begin opens a read critical section of the given seqcount.
156 : : * Validity of the critical section is tested by checking read_seqcount_retry
157 : : * function.
158 : : *
159 : : * Unlike read_seqcount_begin(), this function will not wait for the count
160 : : * to stabilize. If a writer is active when we begin, we will fail the
161 : : * read_seqcount_retry() instead of stabilizing at the beginning of the
162 : : * critical section.
163 : : */
164 : : static inline unsigned raw_seqcount_begin(const seqcount_t *s)
165 : : {
166 : 22708637 : unsigned ret = ACCESS_ONCE(s->sequence);
167 : :
168 : : seqcount_lockdep_reader_access(s);
169 : 22708637 : smp_rmb();
170 : 22709073 : return ret & ~1;
171 : : }
172 : :
173 : : /**
174 : : * __read_seqcount_retry - end a seq-read critical section (without barrier)
175 : : * @s: pointer to seqcount_t
176 : : * @start: count, from read_seqcount_begin
177 : : * Returns: 1 if retry is required, else 0
178 : : *
179 : : * __read_seqcount_retry is like read_seqcount_retry, but has no smp_rmb()
180 : : * barrier. Callers should ensure that smp_rmb() or equivalent ordering is
181 : : * provided before actually loading any of the variables that are to be
182 : : * protected in this critical section.
183 : : *
184 : : * Use carefully, only in critical code, and comment how the barrier is
185 : : * provided.
186 : : */
187 : : static inline int __read_seqcount_retry(const seqcount_t *s, unsigned start)
188 : : {
189 : 506371526 : return unlikely(s->sequence != start);
190 : : }
191 : :
192 : : /**
193 : : * read_seqcount_retry - end a seq-read critical section
194 : : * @s: pointer to seqcount_t
195 : : * @start: count, from read_seqcount_begin
196 : : * Returns: 1 if retry is required, else 0
197 : : *
198 : : * read_seqcount_retry closes a read critical section of the given seqcount.
199 : : * If the critical section was invalid, it must be ignored (and typically
200 : : * retried).
201 : : */
202 : : static inline int read_seqcount_retry(const seqcount_t *s, unsigned start)
203 : : {
204 : 484862731 : smp_rmb();
205 : : return __read_seqcount_retry(s, start);
206 : : }
207 : :
208 : :
209 : :
210 : : static inline void raw_write_seqcount_begin(seqcount_t *s)
211 : : {
212 : 19252818 : s->sequence++;
213 : 18986430 : smp_wmb();
214 : : }
215 : :
216 : : static inline void raw_write_seqcount_end(seqcount_t *s)
217 : : {
218 : 18986404 : smp_wmb();
219 : 19236238 : s->sequence++;
220 : : }
221 : :
222 : : /*
223 : : * Sequence counter only version assumes that callers are using their
224 : : * own mutexing.
225 : : */
226 : : static inline void write_seqcount_begin_nested(seqcount_t *s, int subclass)
227 : : {
228 : : raw_write_seqcount_begin(s);
229 : : seqcount_acquire(&s->dep_map, subclass, 0, _RET_IP_);
230 : : }
231 : :
232 : : static inline void write_seqcount_begin(seqcount_t *s)
233 : : {
234 : : write_seqcount_begin_nested(s, 0);
235 : : }
236 : :
237 : : static inline void write_seqcount_end(seqcount_t *s)
238 : : {
239 : : seqcount_release(&s->dep_map, 1, _RET_IP_);
240 : : raw_write_seqcount_end(s);
241 : : }
242 : :
243 : : /**
244 : : * write_seqcount_barrier - invalidate in-progress read-side seq operations
245 : : * @s: pointer to seqcount_t
246 : : *
247 : : * After write_seqcount_barrier, no read-side seq operations will complete
248 : : * successfully and see data older than this.
249 : : */
250 : : static inline void write_seqcount_barrier(seqcount_t *s)
251 : : {
252 : 6263070 : smp_wmb();
253 : 2196108 : s->sequence+=2;
254 : : }
255 : :
256 : : typedef struct {
257 : : struct seqcount seqcount;
258 : : spinlock_t lock;
259 : : } seqlock_t;
260 : :
261 : : /*
262 : : * These macros triggered gcc-3.x compile-time problems. We think these are
263 : : * OK now. Be cautious.
264 : : */
265 : : #define __SEQLOCK_UNLOCKED(lockname) \
266 : : { \
267 : : .seqcount = SEQCNT_ZERO(lockname), \
268 : : .lock = __SPIN_LOCK_UNLOCKED(lockname) \
269 : : }
270 : :
271 : : #define seqlock_init(x) \
272 : : do { \
273 : : seqcount_init(&(x)->seqcount); \
274 : : spin_lock_init(&(x)->lock); \
275 : : } while (0)
276 : :
277 : : #define DEFINE_SEQLOCK(x) \
278 : : seqlock_t x = __SEQLOCK_UNLOCKED(x)
279 : :
280 : : /*
281 : : * Read side functions for starting and finalizing a read side section.
282 : : */
283 : : static inline unsigned read_seqbegin(const seqlock_t *sl)
284 : : {
285 : : return read_seqcount_begin(&sl->seqcount);
286 : : }
287 : :
288 : : static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start)
289 : : {
290 : : return read_seqcount_retry(&sl->seqcount, start);
291 : : }
292 : :
293 : : /*
294 : : * Lock out other writers and update the count.
295 : : * Acts like a normal spin_lock/unlock.
296 : : * Don't need preempt_disable() because that is in the spin_lock already.
297 : : */
298 : : static inline void write_seqlock(seqlock_t *sl)
299 : : {
300 : : spin_lock(&sl->lock);
301 : : write_seqcount_begin(&sl->seqcount);
302 : : }
303 : :
304 : : static inline void write_sequnlock(seqlock_t *sl)
305 : : {
306 : : write_seqcount_end(&sl->seqcount);
307 : : spin_unlock(&sl->lock);
308 : : }
309 : :
310 : : static inline void write_seqlock_bh(seqlock_t *sl)
311 : : {
312 : : spin_lock_bh(&sl->lock);
313 : : write_seqcount_begin(&sl->seqcount);
314 : : }
315 : :
316 : : static inline void write_sequnlock_bh(seqlock_t *sl)
317 : : {
318 : : write_seqcount_end(&sl->seqcount);
319 : : spin_unlock_bh(&sl->lock);
320 : : }
321 : :
322 : : static inline void write_seqlock_irq(seqlock_t *sl)
323 : : {
324 : : spin_lock_irq(&sl->lock);
325 : : write_seqcount_begin(&sl->seqcount);
326 : : }
327 : :
328 : : static inline void write_sequnlock_irq(seqlock_t *sl)
329 : : {
330 : : write_seqcount_end(&sl->seqcount);
331 : : spin_unlock_irq(&sl->lock);
332 : : }
333 : :
334 : : static inline unsigned long __write_seqlock_irqsave(seqlock_t *sl)
335 : : {
336 : : unsigned long flags;
337 : :
338 : : spin_lock_irqsave(&sl->lock, flags);
339 : : write_seqcount_begin(&sl->seqcount);
340 : : return flags;
341 : : }
342 : :
343 : : #define write_seqlock_irqsave(lock, flags) \
344 : : do { flags = __write_seqlock_irqsave(lock); } while (0)
345 : :
346 : : static inline void
347 : : write_sequnlock_irqrestore(seqlock_t *sl, unsigned long flags)
348 : : {
349 : : write_seqcount_end(&sl->seqcount);
350 : : spin_unlock_irqrestore(&sl->lock, flags);
351 : : }
352 : :
353 : : /*
354 : : * A locking reader exclusively locks out other writers and locking readers,
355 : : * but doesn't update the sequence number. Acts like a normal spin_lock/unlock.
356 : : * Don't need preempt_disable() because that is in the spin_lock already.
357 : : */
358 : : static inline void read_seqlock_excl(seqlock_t *sl)
359 : : {
360 : : spin_lock(&sl->lock);
361 : : }
362 : :
363 : : static inline void read_sequnlock_excl(seqlock_t *sl)
364 : : {
365 : : spin_unlock(&sl->lock);
366 : : }
367 : :
368 : : /**
369 : : * read_seqbegin_or_lock - begin a sequence number check or locking block
370 : : * @lock: sequence lock
371 : : * @seq : sequence number to be checked
372 : : *
373 : : * First try it once optimistically without taking the lock. If that fails,
374 : : * take the lock. The sequence number is also used as a marker for deciding
375 : : * whether to be a reader (even) or writer (odd).
376 : : * N.B. seq must be initialized to an even number to begin with.
377 : : */
378 : : static inline void read_seqbegin_or_lock(seqlock_t *lock, int *seq)
379 : : {
380 [ + - ][ + - ]: 255537 : if (!(*seq & 1)) /* Even */
[ + - ][ + - ]
381 : 28 : *seq = read_seqbegin(lock);
382 : : else /* Odd */
383 : : read_seqlock_excl(lock);
384 : : }
385 : :
386 : : static inline int need_seqretry(seqlock_t *lock, int seq)
387 : : {
388 [ + - + - ]: 513295 : return !(seq & 1) && read_seqretry(lock, seq);
[ + + + ]
[ + + + + ]
[ + - + - ]
[ + + + ]
389 : : }
390 : :
391 : : static inline void done_seqretry(seqlock_t *lock, int seq)
392 : : {
393 [ - + ][ - + ]: 255559 : if (seq & 1)
[ - + - + ]
394 : : read_sequnlock_excl(lock);
395 : : }
396 : :
397 : : static inline void read_seqlock_excl_bh(seqlock_t *sl)
398 : : {
399 : : spin_lock_bh(&sl->lock);
400 : : }
401 : :
402 : : static inline void read_sequnlock_excl_bh(seqlock_t *sl)
403 : : {
404 : : spin_unlock_bh(&sl->lock);
405 : : }
406 : :
407 : : static inline void read_seqlock_excl_irq(seqlock_t *sl)
408 : : {
409 : : spin_lock_irq(&sl->lock);
410 : : }
411 : :
412 : : static inline void read_sequnlock_excl_irq(seqlock_t *sl)
413 : : {
414 : : spin_unlock_irq(&sl->lock);
415 : : }
416 : :
417 : : static inline unsigned long __read_seqlock_excl_irqsave(seqlock_t *sl)
418 : : {
419 : : unsigned long flags;
420 : :
421 : : spin_lock_irqsave(&sl->lock, flags);
422 : : return flags;
423 : : }
424 : :
425 : : #define read_seqlock_excl_irqsave(lock, flags) \
426 : : do { flags = __read_seqlock_excl_irqsave(lock); } while (0)
427 : :
428 : : static inline void
429 : : read_sequnlock_excl_irqrestore(seqlock_t *sl, unsigned long flags)
430 : : {
431 : : spin_unlock_irqrestore(&sl->lock, flags);
432 : : }
433 : :
434 : : #endif /* __LINUX_SEQLOCK_H */
|
