Rev 5270 | Rev 6934 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5270 | serge | 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 | * |
||
6082 | serge | 31 | * Based on x86_64 vsyscall gettimeofday |
5270 | serge | 32 | * by Keith Owens and Andrea Arcangeli |
33 | */ |
||
34 | |||
35 | #include |
||
36 | //#include |
||
37 | #include |
||
6082 | serge | 38 | #include |
5270 | serge | 39 | #include |
40 | |||
41 | /* |
||
42 | * Version using sequence counter only. |
||
43 | * This can be used when code has its own mutex protecting the |
||
44 | * updating starting before the write_seqcountbeqin() and ending |
||
45 | * after the write_seqcount_end(). |
||
46 | */ |
||
47 | typedef struct seqcount { |
||
48 | unsigned sequence; |
||
49 | #ifdef CONFIG_DEBUG_LOCK_ALLOC |
||
50 | struct lockdep_map dep_map; |
||
51 | #endif |
||
52 | } seqcount_t; |
||
53 | |||
54 | static inline void __seqcount_init(seqcount_t *s, const char *name, |
||
55 | struct lock_class_key *key) |
||
56 | { |
||
57 | /* |
||
58 | * Make sure we are not reinitializing a held lock: |
||
59 | */ |
||
60 | lockdep_init_map(&s->dep_map, name, key, 0); |
||
61 | s->sequence = 0; |
||
62 | } |
||
63 | |||
64 | #ifdef CONFIG_DEBUG_LOCK_ALLOC |
||
65 | # define SEQCOUNT_DEP_MAP_INIT(lockname) \ |
||
66 | .dep_map = { .name = #lockname } \ |
||
67 | |||
68 | # define seqcount_init(s) \ |
||
69 | do { \ |
||
70 | static struct lock_class_key __key; \ |
||
71 | __seqcount_init((s), #s, &__key); \ |
||
72 | } while (0) |
||
73 | |||
74 | static inline void seqcount_lockdep_reader_access(const seqcount_t *s) |
||
75 | { |
||
76 | seqcount_t *l = (seqcount_t *)s; |
||
77 | unsigned long flags; |
||
78 | |||
79 | local_irq_save(flags); |
||
80 | seqcount_acquire_read(&l->dep_map, 0, 0, _RET_IP_); |
||
81 | seqcount_release(&l->dep_map, 1, _RET_IP_); |
||
82 | local_irq_restore(flags); |
||
83 | } |
||
84 | |||
85 | #else |
||
86 | # define SEQCOUNT_DEP_MAP_INIT(lockname) |
||
87 | # define seqcount_init(s) __seqcount_init(s, NULL, NULL) |
||
88 | # define seqcount_lockdep_reader_access(x) |
||
89 | #endif |
||
90 | |||
91 | #define SEQCNT_ZERO(lockname) { .sequence = 0, SEQCOUNT_DEP_MAP_INIT(lockname)} |
||
92 | |||
93 | |||
94 | /** |
||
95 | * __read_seqcount_begin - begin a seq-read critical section (without barrier) |
||
96 | * @s: pointer to seqcount_t |
||
97 | * Returns: count to be passed to read_seqcount_retry |
||
98 | * |
||
99 | * __read_seqcount_begin is like read_seqcount_begin, but has no smp_rmb() |
||
100 | * barrier. Callers should ensure that smp_rmb() or equivalent ordering is |
||
101 | * provided before actually loading any of the variables that are to be |
||
102 | * protected in this critical section. |
||
103 | * |
||
104 | * Use carefully, only in critical code, and comment how the barrier is |
||
105 | * provided. |
||
106 | */ |
||
107 | static inline unsigned __read_seqcount_begin(const seqcount_t *s) |
||
108 | { |
||
109 | unsigned ret; |
||
110 | |||
111 | repeat: |
||
6082 | serge | 112 | ret = READ_ONCE(s->sequence); |
5270 | serge | 113 | if (unlikely(ret & 1)) { |
114 | cpu_relax(); |
||
115 | goto repeat; |
||
116 | } |
||
117 | return ret; |
||
118 | } |
||
119 | |||
120 | /** |
||
121 | * raw_read_seqcount - Read the raw seqcount |
||
122 | * @s: pointer to seqcount_t |
||
123 | * Returns: count to be passed to read_seqcount_retry |
||
124 | * |
||
125 | * raw_read_seqcount opens a read critical section of the given |
||
126 | * seqcount without any lockdep checking and without checking or |
||
127 | * masking the LSB. Calling code is responsible for handling that. |
||
128 | */ |
||
129 | static inline unsigned raw_read_seqcount(const seqcount_t *s) |
||
130 | { |
||
6082 | serge | 131 | unsigned ret = READ_ONCE(s->sequence); |
5270 | serge | 132 | smp_rmb(); |
133 | return ret; |
||
134 | } |
||
135 | |||
136 | /** |
||
137 | * raw_read_seqcount_begin - start seq-read critical section w/o lockdep |
||
138 | * @s: pointer to seqcount_t |
||
139 | * Returns: count to be passed to read_seqcount_retry |
||
140 | * |
||
141 | * raw_read_seqcount_begin opens a read critical section of the given |
||
142 | * seqcount, but without any lockdep checking. Validity of the critical |
||
143 | * section is tested by checking read_seqcount_retry function. |
||
144 | */ |
||
145 | static inline unsigned raw_read_seqcount_begin(const seqcount_t *s) |
||
146 | { |
||
147 | unsigned ret = __read_seqcount_begin(s); |
||
148 | smp_rmb(); |
||
149 | return ret; |
||
150 | } |
||
151 | |||
152 | /** |
||
153 | * read_seqcount_begin - begin a seq-read critical section |
||
154 | * @s: pointer to seqcount_t |
||
155 | * Returns: count to be passed to read_seqcount_retry |
||
156 | * |
||
157 | * read_seqcount_begin opens a read critical section of the given seqcount. |
||
158 | * Validity of the critical section is tested by checking read_seqcount_retry |
||
159 | * function. |
||
160 | */ |
||
161 | static inline unsigned read_seqcount_begin(const seqcount_t *s) |
||
162 | { |
||
163 | seqcount_lockdep_reader_access(s); |
||
164 | return raw_read_seqcount_begin(s); |
||
165 | } |
||
166 | |||
167 | /** |
||
168 | * raw_seqcount_begin - begin a seq-read critical section |
||
169 | * @s: pointer to seqcount_t |
||
170 | * Returns: count to be passed to read_seqcount_retry |
||
171 | * |
||
172 | * raw_seqcount_begin opens a read critical section of the given seqcount. |
||
173 | * Validity of the critical section is tested by checking read_seqcount_retry |
||
174 | * function. |
||
175 | * |
||
176 | * Unlike read_seqcount_begin(), this function will not wait for the count |
||
177 | * to stabilize. If a writer is active when we begin, we will fail the |
||
178 | * read_seqcount_retry() instead of stabilizing at the beginning of the |
||
179 | * critical section. |
||
180 | */ |
||
181 | static inline unsigned raw_seqcount_begin(const seqcount_t *s) |
||
182 | { |
||
6082 | serge | 183 | unsigned ret = READ_ONCE(s->sequence); |
5270 | serge | 184 | smp_rmb(); |
185 | return ret & ~1; |
||
186 | } |
||
187 | |||
188 | /** |
||
189 | * __read_seqcount_retry - end a seq-read critical section (without barrier) |
||
190 | * @s: pointer to seqcount_t |
||
191 | * @start: count, from read_seqcount_begin |
||
192 | * Returns: 1 if retry is required, else 0 |
||
193 | * |
||
194 | * __read_seqcount_retry is like read_seqcount_retry, but has no smp_rmb() |
||
195 | * barrier. Callers should ensure that smp_rmb() or equivalent ordering is |
||
196 | * provided before actually loading any of the variables that are to be |
||
197 | * protected in this critical section. |
||
198 | * |
||
199 | * Use carefully, only in critical code, and comment how the barrier is |
||
200 | * provided. |
||
201 | */ |
||
202 | static inline int __read_seqcount_retry(const seqcount_t *s, unsigned start) |
||
203 | { |
||
204 | return unlikely(s->sequence != start); |
||
205 | } |
||
206 | |||
207 | /** |
||
208 | * read_seqcount_retry - end a seq-read critical section |
||
209 | * @s: pointer to seqcount_t |
||
210 | * @start: count, from read_seqcount_begin |
||
211 | * Returns: 1 if retry is required, else 0 |
||
212 | * |
||
213 | * read_seqcount_retry closes a read critical section of the given seqcount. |
||
214 | * If the critical section was invalid, it must be ignored (and typically |
||
215 | * retried). |
||
216 | */ |
||
217 | static inline int read_seqcount_retry(const seqcount_t *s, unsigned start) |
||
218 | { |
||
219 | smp_rmb(); |
||
220 | return __read_seqcount_retry(s, start); |
||
221 | } |
||
222 | |||
223 | |||
224 | |||
225 | static inline void raw_write_seqcount_begin(seqcount_t *s) |
||
226 | { |
||
227 | s->sequence++; |
||
228 | smp_wmb(); |
||
229 | } |
||
230 | |||
231 | static inline void raw_write_seqcount_end(seqcount_t *s) |
||
232 | { |
||
233 | smp_wmb(); |
||
234 | s->sequence++; |
||
235 | } |
||
236 | |||
237 | /* |
||
238 | * raw_write_seqcount_latch - redirect readers to even/odd copy |
||
239 | * @s: pointer to seqcount_t |
||
6082 | serge | 240 | * |
241 | * The latch technique is a multiversion concurrency control method that allows |
||
242 | * queries during non-atomic modifications. If you can guarantee queries never |
||
243 | * interrupt the modification -- e.g. the concurrency is strictly between CPUs |
||
244 | * -- you most likely do not need this. |
||
245 | * |
||
246 | * Where the traditional RCU/lockless data structures rely on atomic |
||
247 | * modifications to ensure queries observe either the old or the new state the |
||
248 | * latch allows the same for non-atomic updates. The trade-off is doubling the |
||
249 | * cost of storage; we have to maintain two copies of the entire data |
||
250 | * structure. |
||
251 | * |
||
252 | * Very simply put: we first modify one copy and then the other. This ensures |
||
253 | * there is always one copy in a stable state, ready to give us an answer. |
||
254 | * |
||
255 | * The basic form is a data structure like: |
||
256 | * |
||
257 | * struct latch_struct { |
||
258 | * seqcount_t seq; |
||
259 | * struct data_struct data[2]; |
||
260 | * }; |
||
261 | * |
||
262 | * Where a modification, which is assumed to be externally serialized, does the |
||
263 | * following: |
||
264 | * |
||
265 | * void latch_modify(struct latch_struct *latch, ...) |
||
266 | * { |
||
267 | * smp_wmb(); <- Ensure that the last data[1] update is visible |
||
268 | * latch->seq++; |
||
269 | * smp_wmb(); <- Ensure that the seqcount update is visible |
||
270 | * |
||
271 | * modify(latch->data[0], ...); |
||
272 | * |
||
273 | * smp_wmb(); <- Ensure that the data[0] update is visible |
||
274 | * latch->seq++; |
||
275 | * smp_wmb(); <- Ensure that the seqcount update is visible |
||
276 | * |
||
277 | * modify(latch->data[1], ...); |
||
278 | * } |
||
279 | * |
||
280 | * The query will have a form like: |
||
281 | * |
||
282 | * struct entry *latch_query(struct latch_struct *latch, ...) |
||
283 | * { |
||
284 | * struct entry *entry; |
||
285 | * unsigned seq, idx; |
||
286 | * |
||
287 | * do { |
||
288 | * seq = lockless_dereference(latch->seq); |
||
289 | * |
||
290 | * idx = seq & 0x01; |
||
291 | * entry = data_query(latch->data[idx], ...); |
||
292 | * |
||
293 | * smp_rmb(); |
||
294 | * } while (seq != latch->seq); |
||
295 | * |
||
296 | * return entry; |
||
297 | * } |
||
298 | * |
||
299 | * So during the modification, queries are first redirected to data[1]. Then we |
||
300 | * modify data[0]. When that is complete, we redirect queries back to data[0] |
||
301 | * and we can modify data[1]. |
||
302 | * |
||
303 | * NOTE: The non-requirement for atomic modifications does _NOT_ include |
||
304 | * the publishing of new entries in the case where data is a dynamic |
||
305 | * data structure. |
||
306 | * |
||
307 | * An iteration might start in data[0] and get suspended long enough |
||
308 | * to miss an entire modification sequence, once it resumes it might |
||
309 | * observe the new entry. |
||
310 | * |
||
311 | * NOTE: When data is a dynamic data structure; one should use regular RCU |
||
312 | * patterns to manage the lifetimes of the objects within. |
||
5270 | serge | 313 | */ |
314 | static inline void raw_write_seqcount_latch(seqcount_t *s) |
||
315 | { |
||
316 | smp_wmb(); /* prior stores before incrementing "sequence" */ |
||
317 | s->sequence++; |
||
318 | smp_wmb(); /* increment "sequence" before following stores */ |
||
319 | } |
||
320 | |||
321 | /* |
||
322 | * Sequence counter only version assumes that callers are using their |
||
323 | * own mutexing. |
||
324 | */ |
||
325 | static inline void write_seqcount_begin_nested(seqcount_t *s, int subclass) |
||
326 | { |
||
327 | raw_write_seqcount_begin(s); |
||
328 | seqcount_acquire(&s->dep_map, subclass, 0, _RET_IP_); |
||
329 | } |
||
330 | |||
331 | static inline void write_seqcount_begin(seqcount_t *s) |
||
332 | { |
||
333 | write_seqcount_begin_nested(s, 0); |
||
334 | } |
||
335 | |||
336 | static inline void write_seqcount_end(seqcount_t *s) |
||
337 | { |
||
338 | seqcount_release(&s->dep_map, 1, _RET_IP_); |
||
339 | raw_write_seqcount_end(s); |
||
340 | } |
||
341 | |||
342 | /** |
||
6082 | serge | 343 | * write_seqcount_invalidate - invalidate in-progress read-side seq operations |
5270 | serge | 344 | * @s: pointer to seqcount_t |
345 | * |
||
6082 | serge | 346 | * After write_seqcount_invalidate, no read-side seq operations will complete |
5270 | serge | 347 | * successfully and see data older than this. |
348 | */ |
||
6082 | serge | 349 | static inline void write_seqcount_invalidate(seqcount_t *s) |
5270 | serge | 350 | { |
351 | smp_wmb(); |
||
352 | s->sequence+=2; |
||
353 | } |
||
354 | |||
355 | typedef struct { |
||
356 | struct seqcount seqcount; |
||
357 | spinlock_t lock; |
||
358 | } seqlock_t; |
||
359 | |||
360 | /* |
||
361 | * These macros triggered gcc-3.x compile-time problems. We think these are |
||
362 | * OK now. Be cautious. |
||
363 | */ |
||
364 | #define __SEQLOCK_UNLOCKED(lockname) \ |
||
365 | { \ |
||
366 | .seqcount = SEQCNT_ZERO(lockname), \ |
||
367 | .lock = __SPIN_LOCK_UNLOCKED(lockname) \ |
||
368 | } |
||
369 | |||
370 | #define seqlock_init(x) \ |
||
371 | do { \ |
||
372 | seqcount_init(&(x)->seqcount); \ |
||
373 | spin_lock_init(&(x)->lock); \ |
||
374 | } while (0) |
||
375 | |||
376 | #define DEFINE_SEQLOCK(x) \ |
||
377 | seqlock_t x = __SEQLOCK_UNLOCKED(x) |
||
378 | |||
379 | /* |
||
380 | * Read side functions for starting and finalizing a read side section. |
||
381 | */ |
||
382 | static inline unsigned read_seqbegin(const seqlock_t *sl) |
||
383 | { |
||
384 | return read_seqcount_begin(&sl->seqcount); |
||
385 | } |
||
386 | |||
387 | static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start) |
||
388 | { |
||
389 | return read_seqcount_retry(&sl->seqcount, start); |
||
390 | } |
||
391 | |||
392 | /* |
||
393 | * Lock out other writers and update the count. |
||
394 | * Acts like a normal spin_lock/unlock. |
||
395 | * Don't need preempt_disable() because that is in the spin_lock already. |
||
396 | */ |
||
397 | static inline void write_seqlock(seqlock_t *sl) |
||
398 | { |
||
399 | spin_lock(&sl->lock); |
||
400 | write_seqcount_begin(&sl->seqcount); |
||
401 | } |
||
402 | |||
403 | static inline void write_sequnlock(seqlock_t *sl) |
||
404 | { |
||
405 | write_seqcount_end(&sl->seqcount); |
||
406 | spin_unlock(&sl->lock); |
||
407 | } |
||
408 | |||
409 | static inline void write_seqlock_bh(seqlock_t *sl) |
||
410 | { |
||
411 | spin_lock_bh(&sl->lock); |
||
412 | write_seqcount_begin(&sl->seqcount); |
||
413 | } |
||
414 | |||
415 | static inline void write_sequnlock_bh(seqlock_t *sl) |
||
416 | { |
||
417 | write_seqcount_end(&sl->seqcount); |
||
418 | spin_unlock_bh(&sl->lock); |
||
419 | } |
||
420 | |||
421 | static inline void write_seqlock_irq(seqlock_t *sl) |
||
422 | { |
||
423 | spin_lock_irq(&sl->lock); |
||
424 | write_seqcount_begin(&sl->seqcount); |
||
425 | } |
||
426 | |||
427 | static inline void write_sequnlock_irq(seqlock_t *sl) |
||
428 | { |
||
429 | write_seqcount_end(&sl->seqcount); |
||
430 | spin_unlock_irq(&sl->lock); |
||
431 | } |
||
432 | |||
433 | static inline unsigned long __write_seqlock_irqsave(seqlock_t *sl) |
||
434 | { |
||
435 | unsigned long flags; |
||
436 | |||
437 | spin_lock_irqsave(&sl->lock, flags); |
||
438 | write_seqcount_begin(&sl->seqcount); |
||
439 | return flags; |
||
440 | } |
||
441 | |||
442 | #define write_seqlock_irqsave(lock, flags) \ |
||
443 | do { flags = __write_seqlock_irqsave(lock); } while (0) |
||
444 | |||
445 | static inline void |
||
446 | write_sequnlock_irqrestore(seqlock_t *sl, unsigned long flags) |
||
447 | { |
||
448 | write_seqcount_end(&sl->seqcount); |
||
449 | spin_unlock_irqrestore(&sl->lock, flags); |
||
450 | } |
||
451 | |||
452 | /* |
||
453 | * A locking reader exclusively locks out other writers and locking readers, |
||
454 | * but doesn't update the sequence number. Acts like a normal spin_lock/unlock. |
||
455 | * Don't need preempt_disable() because that is in the spin_lock already. |
||
456 | */ |
||
457 | static inline void read_seqlock_excl(seqlock_t *sl) |
||
458 | { |
||
459 | spin_lock(&sl->lock); |
||
460 | } |
||
461 | |||
462 | static inline void read_sequnlock_excl(seqlock_t *sl) |
||
463 | { |
||
464 | spin_unlock(&sl->lock); |
||
465 | } |
||
466 | |||
467 | /** |
||
468 | * read_seqbegin_or_lock - begin a sequence number check or locking block |
||
469 | * @lock: sequence lock |
||
470 | * @seq : sequence number to be checked |
||
471 | * |
||
472 | * First try it once optimistically without taking the lock. If that fails, |
||
473 | * take the lock. The sequence number is also used as a marker for deciding |
||
474 | * whether to be a reader (even) or writer (odd). |
||
475 | * N.B. seq must be initialized to an even number to begin with. |
||
476 | */ |
||
477 | static inline void read_seqbegin_or_lock(seqlock_t *lock, int *seq) |
||
478 | { |
||
479 | if (!(*seq & 1)) /* Even */ |
||
480 | *seq = read_seqbegin(lock); |
||
481 | else /* Odd */ |
||
482 | read_seqlock_excl(lock); |
||
483 | } |
||
484 | |||
485 | static inline int need_seqretry(seqlock_t *lock, int seq) |
||
486 | { |
||
487 | return !(seq & 1) && read_seqretry(lock, seq); |
||
488 | } |
||
489 | |||
490 | static inline void done_seqretry(seqlock_t *lock, int seq) |
||
491 | { |
||
492 | if (seq & 1) |
||
493 | read_sequnlock_excl(lock); |
||
494 | } |
||
495 | |||
496 | static inline void read_seqlock_excl_bh(seqlock_t *sl) |
||
497 | { |
||
498 | spin_lock_bh(&sl->lock); |
||
499 | } |
||
500 | |||
501 | static inline void read_sequnlock_excl_bh(seqlock_t *sl) |
||
502 | { |
||
503 | spin_unlock_bh(&sl->lock); |
||
504 | } |
||
505 | |||
506 | static inline void read_seqlock_excl_irq(seqlock_t *sl) |
||
507 | { |
||
508 | spin_lock_irq(&sl->lock); |
||
509 | } |
||
510 | |||
511 | static inline void read_sequnlock_excl_irq(seqlock_t *sl) |
||
512 | { |
||
513 | spin_unlock_irq(&sl->lock); |
||
514 | } |
||
515 | |||
516 | static inline unsigned long __read_seqlock_excl_irqsave(seqlock_t *sl) |
||
517 | { |
||
518 | unsigned long flags; |
||
519 | |||
520 | spin_lock_irqsave(&sl->lock, flags); |
||
521 | return flags; |
||
522 | } |
||
523 | |||
524 | #define read_seqlock_excl_irqsave(lock, flags) \ |
||
525 | do { flags = __read_seqlock_excl_irqsave(lock); } while (0) |
||
526 | |||
527 | static inline void |
||
528 | read_sequnlock_excl_irqrestore(seqlock_t *sl, unsigned long flags) |
||
529 | { |
||
530 | spin_unlock_irqrestore(&sl->lock, flags); |
||
531 | } |
||
532 | |||
533 | static inline unsigned long |
||
534 | read_seqbegin_or_lock_irqsave(seqlock_t *lock, int *seq) |
||
535 | { |
||
536 | unsigned long flags = 0; |
||
537 | |||
538 | if (!(*seq & 1)) /* Even */ |
||
539 | *seq = read_seqbegin(lock); |
||
540 | else /* Odd */ |
||
541 | read_seqlock_excl_irqsave(lock, flags); |
||
542 | |||
543 | return flags; |
||
544 | } |
||
545 | |||
546 | static inline void |
||
547 | done_seqretry_irqrestore(seqlock_t *lock, int seq, unsigned long flags) |
||
548 | { |
||
549 | if (seq & 1) |
||
550 | read_sequnlock_excl_irqrestore(lock, flags); |
||
551 | } |
||
552 | #endif /* __LINUX_SEQLOCK_H */->->->-> |