1 | // SPDX-License-Identifier: GPL-2.0+ |
2 | /* |
3 | * Sleepable Read-Copy Update mechanism for mutual exclusion, |
4 | * tiny version for non-preemptible single-CPU use. |
5 | * |
6 | * Copyright (C) IBM Corporation, 2017 |
7 | * |
8 | * Author: Paul McKenney <paulmck@linux.ibm.com> |
9 | */ |
10 | |
11 | #include <linux/export.h> |
12 | #include <linux/mutex.h> |
13 | #include <linux/preempt.h> |
14 | #include <linux/rcupdate_wait.h> |
15 | #include <linux/sched.h> |
16 | #include <linux/delay.h> |
17 | #include <linux/srcu.h> |
18 | |
19 | #include <linux/rcu_node_tree.h> |
20 | #include "rcu_segcblist.h" |
21 | #include "rcu.h" |
22 | |
23 | int rcu_scheduler_active __read_mostly; |
24 | static LIST_HEAD(srcu_boot_list); |
25 | static bool srcu_init_done; |
26 | |
27 | static int init_srcu_struct_fields(struct srcu_struct *ssp) |
28 | { |
29 | ssp->srcu_lock_nesting[0] = 0; |
30 | ssp->srcu_lock_nesting[1] = 0; |
31 | init_swait_queue_head(&ssp->srcu_wq); |
32 | ssp->srcu_cb_head = NULL; |
33 | ssp->srcu_cb_tail = &ssp->srcu_cb_head; |
34 | ssp->srcu_gp_running = false; |
35 | ssp->srcu_gp_waiting = false; |
36 | ssp->srcu_idx = 0; |
37 | ssp->srcu_idx_max = 0; |
38 | INIT_WORK(&ssp->srcu_work, srcu_drive_gp); |
39 | INIT_LIST_HEAD(list: &ssp->srcu_work.entry); |
40 | return 0; |
41 | } |
42 | |
43 | #ifdef CONFIG_DEBUG_LOCK_ALLOC |
44 | |
45 | int __init_srcu_struct(struct srcu_struct *ssp, const char *name, |
46 | struct lock_class_key *key) |
47 | { |
48 | /* Don't re-initialize a lock while it is held. */ |
49 | debug_check_no_locks_freed(from: (void *)ssp, len: sizeof(*ssp)); |
50 | lockdep_init_map(lock: &ssp->dep_map, name, key, subclass: 0); |
51 | return init_srcu_struct_fields(ssp); |
52 | } |
53 | EXPORT_SYMBOL_GPL(__init_srcu_struct); |
54 | |
55 | #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ |
56 | |
57 | /* |
58 | * init_srcu_struct - initialize a sleep-RCU structure |
59 | * @ssp: structure to initialize. |
60 | * |
61 | * Must invoke this on a given srcu_struct before passing that srcu_struct |
62 | * to any other function. Each srcu_struct represents a separate domain |
63 | * of SRCU protection. |
64 | */ |
65 | int init_srcu_struct(struct srcu_struct *ssp) |
66 | { |
67 | return init_srcu_struct_fields(ssp); |
68 | } |
69 | EXPORT_SYMBOL_GPL(init_srcu_struct); |
70 | |
71 | #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ |
72 | |
73 | /* |
74 | * cleanup_srcu_struct - deconstruct a sleep-RCU structure |
75 | * @ssp: structure to clean up. |
76 | * |
77 | * Must invoke this after you are finished using a given srcu_struct that |
78 | * was initialized via init_srcu_struct(), else you leak memory. |
79 | */ |
80 | void cleanup_srcu_struct(struct srcu_struct *ssp) |
81 | { |
82 | WARN_ON(ssp->srcu_lock_nesting[0] || ssp->srcu_lock_nesting[1]); |
83 | flush_work(work: &ssp->srcu_work); |
84 | WARN_ON(ssp->srcu_gp_running); |
85 | WARN_ON(ssp->srcu_gp_waiting); |
86 | WARN_ON(ssp->srcu_cb_head); |
87 | WARN_ON(&ssp->srcu_cb_head != ssp->srcu_cb_tail); |
88 | WARN_ON(ssp->srcu_idx != ssp->srcu_idx_max); |
89 | WARN_ON(ssp->srcu_idx & 0x1); |
90 | } |
91 | EXPORT_SYMBOL_GPL(cleanup_srcu_struct); |
92 | |
93 | /* |
94 | * Removes the count for the old reader from the appropriate element of |
95 | * the srcu_struct. |
96 | */ |
97 | void __srcu_read_unlock(struct srcu_struct *ssp, int idx) |
98 | { |
99 | int newval = READ_ONCE(ssp->srcu_lock_nesting[idx]) - 1; |
100 | |
101 | WRITE_ONCE(ssp->srcu_lock_nesting[idx], newval); |
102 | if (!newval && READ_ONCE(ssp->srcu_gp_waiting) && in_task()) |
103 | swake_up_one(q: &ssp->srcu_wq); |
104 | } |
105 | EXPORT_SYMBOL_GPL(__srcu_read_unlock); |
106 | |
107 | /* |
108 | * Workqueue handler to drive one grace period and invoke any callbacks |
109 | * that become ready as a result. Single-CPU and !PREEMPTION operation |
110 | * means that we get away with murder on synchronization. ;-) |
111 | */ |
112 | void srcu_drive_gp(struct work_struct *wp) |
113 | { |
114 | int idx; |
115 | struct rcu_head *lh; |
116 | struct rcu_head *rhp; |
117 | struct srcu_struct *ssp; |
118 | |
119 | ssp = container_of(wp, struct srcu_struct, srcu_work); |
120 | if (ssp->srcu_gp_running || ULONG_CMP_GE(ssp->srcu_idx, READ_ONCE(ssp->srcu_idx_max))) |
121 | return; /* Already running or nothing to do. */ |
122 | |
123 | /* Remove recently arrived callbacks and wait for readers. */ |
124 | WRITE_ONCE(ssp->srcu_gp_running, true); |
125 | local_irq_disable(); |
126 | lh = ssp->srcu_cb_head; |
127 | ssp->srcu_cb_head = NULL; |
128 | ssp->srcu_cb_tail = &ssp->srcu_cb_head; |
129 | local_irq_enable(); |
130 | idx = (ssp->srcu_idx & 0x2) / 2; |
131 | WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1); |
132 | WRITE_ONCE(ssp->srcu_gp_waiting, true); /* srcu_read_unlock() wakes! */ |
133 | swait_event_exclusive(ssp->srcu_wq, !READ_ONCE(ssp->srcu_lock_nesting[idx])); |
134 | WRITE_ONCE(ssp->srcu_gp_waiting, false); /* srcu_read_unlock() cheap. */ |
135 | WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1); |
136 | |
137 | /* Invoke the callbacks we removed above. */ |
138 | while (lh) { |
139 | rhp = lh; |
140 | lh = lh->next; |
141 | debug_rcu_head_callback(rhp); |
142 | local_bh_disable(); |
143 | rhp->func(rhp); |
144 | local_bh_enable(); |
145 | } |
146 | |
147 | /* |
148 | * Enable rescheduling, and if there are more callbacks, |
149 | * reschedule ourselves. This can race with a call_srcu() |
150 | * at interrupt level, but the ->srcu_gp_running checks will |
151 | * straighten that out. |
152 | */ |
153 | WRITE_ONCE(ssp->srcu_gp_running, false); |
154 | if (ULONG_CMP_LT(ssp->srcu_idx, READ_ONCE(ssp->srcu_idx_max))) |
155 | schedule_work(work: &ssp->srcu_work); |
156 | } |
157 | EXPORT_SYMBOL_GPL(srcu_drive_gp); |
158 | |
159 | static void srcu_gp_start_if_needed(struct srcu_struct *ssp) |
160 | { |
161 | unsigned long cookie; |
162 | |
163 | cookie = get_state_synchronize_srcu(ssp); |
164 | if (ULONG_CMP_GE(READ_ONCE(ssp->srcu_idx_max), cookie)) |
165 | return; |
166 | WRITE_ONCE(ssp->srcu_idx_max, cookie); |
167 | if (!READ_ONCE(ssp->srcu_gp_running)) { |
168 | if (likely(srcu_init_done)) |
169 | schedule_work(work: &ssp->srcu_work); |
170 | else if (list_empty(head: &ssp->srcu_work.entry)) |
171 | list_add(new: &ssp->srcu_work.entry, head: &srcu_boot_list); |
172 | } |
173 | } |
174 | |
175 | /* |
176 | * Enqueue an SRCU callback on the specified srcu_struct structure, |
177 | * initiating grace-period processing if it is not already running. |
178 | */ |
179 | void call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp, |
180 | rcu_callback_t func) |
181 | { |
182 | unsigned long flags; |
183 | |
184 | rhp->func = func; |
185 | rhp->next = NULL; |
186 | local_irq_save(flags); |
187 | *ssp->srcu_cb_tail = rhp; |
188 | ssp->srcu_cb_tail = &rhp->next; |
189 | local_irq_restore(flags); |
190 | srcu_gp_start_if_needed(ssp); |
191 | } |
192 | EXPORT_SYMBOL_GPL(call_srcu); |
193 | |
194 | /* |
195 | * synchronize_srcu - wait for prior SRCU read-side critical-section completion |
196 | */ |
197 | void synchronize_srcu(struct srcu_struct *ssp) |
198 | { |
199 | struct rcu_synchronize rs; |
200 | |
201 | srcu_lock_sync(map: &ssp->dep_map); |
202 | |
203 | RCU_LOCKDEP_WARN(lockdep_is_held(ssp) || |
204 | lock_is_held(&rcu_bh_lock_map) || |
205 | lock_is_held(&rcu_lock_map) || |
206 | lock_is_held(&rcu_sched_lock_map), |
207 | "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section" ); |
208 | |
209 | if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE) |
210 | return; |
211 | |
212 | might_sleep(); |
213 | init_rcu_head_on_stack(head: &rs.head); |
214 | init_completion(x: &rs.completion); |
215 | call_srcu(ssp, &rs.head, wakeme_after_rcu); |
216 | wait_for_completion(&rs.completion); |
217 | destroy_rcu_head_on_stack(head: &rs.head); |
218 | } |
219 | EXPORT_SYMBOL_GPL(synchronize_srcu); |
220 | |
221 | /* |
222 | * get_state_synchronize_srcu - Provide an end-of-grace-period cookie |
223 | */ |
224 | unsigned long get_state_synchronize_srcu(struct srcu_struct *ssp) |
225 | { |
226 | unsigned long ret; |
227 | |
228 | barrier(); |
229 | ret = (READ_ONCE(ssp->srcu_idx) + 3) & ~0x1; |
230 | barrier(); |
231 | return ret; |
232 | } |
233 | EXPORT_SYMBOL_GPL(get_state_synchronize_srcu); |
234 | |
235 | /* |
236 | * start_poll_synchronize_srcu - Provide cookie and start grace period |
237 | * |
238 | * The difference between this and get_state_synchronize_srcu() is that |
239 | * this function ensures that the poll_state_synchronize_srcu() will |
240 | * eventually return the value true. |
241 | */ |
242 | unsigned long start_poll_synchronize_srcu(struct srcu_struct *ssp) |
243 | { |
244 | unsigned long ret = get_state_synchronize_srcu(ssp); |
245 | |
246 | srcu_gp_start_if_needed(ssp); |
247 | return ret; |
248 | } |
249 | EXPORT_SYMBOL_GPL(start_poll_synchronize_srcu); |
250 | |
251 | /* |
252 | * poll_state_synchronize_srcu - Has cookie's grace period ended? |
253 | */ |
254 | bool poll_state_synchronize_srcu(struct srcu_struct *ssp, unsigned long cookie) |
255 | { |
256 | unsigned long cur_s = READ_ONCE(ssp->srcu_idx); |
257 | |
258 | barrier(); |
259 | return ULONG_CMP_GE(cur_s, cookie) || ULONG_CMP_LT(cur_s, cookie - 3); |
260 | } |
261 | EXPORT_SYMBOL_GPL(poll_state_synchronize_srcu); |
262 | |
263 | /* Lockdep diagnostics. */ |
264 | void __init rcu_scheduler_starting(void) |
265 | { |
266 | rcu_scheduler_active = RCU_SCHEDULER_RUNNING; |
267 | } |
268 | |
269 | /* |
270 | * Queue work for srcu_struct structures with early boot callbacks. |
271 | * The work won't actually execute until the workqueue initialization |
272 | * phase that takes place after the scheduler starts. |
273 | */ |
274 | void __init srcu_init(void) |
275 | { |
276 | struct srcu_struct *ssp; |
277 | |
278 | srcu_init_done = true; |
279 | while (!list_empty(head: &srcu_boot_list)) { |
280 | ssp = list_first_entry(&srcu_boot_list, |
281 | struct srcu_struct, srcu_work.entry); |
282 | list_del_init(entry: &ssp->srcu_work.entry); |
283 | schedule_work(work: &ssp->srcu_work); |
284 | } |
285 | } |
286 | |