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