1 /*-
2  * Copyright (c) 2016 Matthew Macy (mmacy@mattmacy.io)
3  * Copyright (c) 2017-2020 Hans Petter Selasky (hselasky@freebsd.org)
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice unmodified, this list of conditions, and the following
11  *    disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
30 
31 #include <sys/types.h>
32 #include <sys/systm.h>
33 #include <sys/malloc.h>
34 #include <sys/kernel.h>
35 #include <sys/lock.h>
36 #include <sys/mutex.h>
37 #include <sys/proc.h>
38 #include <sys/sched.h>
39 #include <sys/smp.h>
40 #include <sys/queue.h>
41 #include <sys/taskqueue.h>
42 #include <sys/kdb.h>
43 
44 #include <ck_epoch.h>
45 
46 #include <linux/rcupdate.h>
47 #include <linux/srcu.h>
48 #include <linux/slab.h>
49 #include <linux/kernel.h>
50 #include <linux/compat.h>
51 
52 /*
53  * By defining CONFIG_NO_RCU_SKIP LinuxKPI RCU locks and asserts will
54  * not be skipped during panic().
55  */
56 #ifdef CONFIG_NO_RCU_SKIP
57 #define	RCU_SKIP(void) 0
58 #else
59 #define	RCU_SKIP(void)	unlikely(SCHEDULER_STOPPED() || kdb_active)
60 #endif
61 
62 struct callback_head {
63 	STAILQ_ENTRY(callback_head) entry;
64 	rcu_callback_t func;
65 };
66 
67 struct linux_epoch_head {
68 	STAILQ_HEAD(, callback_head) cb_head;
69 	struct mtx lock;
70 	struct task task;
71 } __aligned(CACHE_LINE_SIZE);
72 
73 struct linux_epoch_record {
74 	ck_epoch_record_t epoch_record;
75 	TAILQ_HEAD(, task_struct) ts_head;
76 	int cpuid;
77 } __aligned(CACHE_LINE_SIZE);
78 
79 /*
80  * Verify that "struct rcu_head" is big enough to hold "struct
81  * callback_head". This has been done to avoid having to add special
82  * compile flags for including ck_epoch.h to all clients of the
83  * LinuxKPI.
84  */
85 CTASSERT(sizeof(struct rcu_head) == sizeof(struct callback_head));
86 
87 /*
88  * Verify that "epoch_record" is at beginning of "struct
89  * linux_epoch_record":
90  */
91 CTASSERT(offsetof(struct linux_epoch_record, epoch_record) == 0);
92 
93 static ck_epoch_t linux_epoch[RCU_TYPE_MAX];
94 static struct linux_epoch_head linux_epoch_head[RCU_TYPE_MAX];
95 DPCPU_DEFINE_STATIC(struct linux_epoch_record, linux_epoch_record[RCU_TYPE_MAX]);
96 
97 static void linux_rcu_cleaner_func(void *, int);
98 
99 static void
100 linux_rcu_runtime_init(void *arg __unused)
101 {
102 	struct linux_epoch_head *head;
103 	int i;
104 	int j;
105 
106 	for (j = 0; j != RCU_TYPE_MAX; j++) {
107 		ck_epoch_init(&linux_epoch[j]);
108 
109 		head = &linux_epoch_head[j];
110 
111 		mtx_init(&head->lock, "LRCU-HEAD", NULL, MTX_DEF);
112 		TASK_INIT(&head->task, 0, linux_rcu_cleaner_func, head);
113 		STAILQ_INIT(&head->cb_head);
114 
115 		CPU_FOREACH(i) {
116 			struct linux_epoch_record *record;
117 
118 			record = &DPCPU_ID_GET(i, linux_epoch_record[j]);
119 
120 			record->cpuid = i;
121 			ck_epoch_register(&linux_epoch[j],
122 			    &record->epoch_record, NULL);
123 			TAILQ_INIT(&record->ts_head);
124 		}
125 	}
126 }
127 SYSINIT(linux_rcu_runtime, SI_SUB_CPU, SI_ORDER_ANY, linux_rcu_runtime_init, NULL);
128 
129 static void
130 linux_rcu_runtime_uninit(void *arg __unused)
131 {
132 	struct linux_epoch_head *head;
133 	int j;
134 
135 	for (j = 0; j != RCU_TYPE_MAX; j++) {
136 		head = &linux_epoch_head[j];
137 
138 		mtx_destroy(&head->lock);
139 	}
140 }
141 SYSUNINIT(linux_rcu_runtime, SI_SUB_LOCK, SI_ORDER_SECOND, linux_rcu_runtime_uninit, NULL);
142 
143 static void
144 linux_rcu_cleaner_func(void *context, int pending __unused)
145 {
146 	struct linux_epoch_head *head;
147 	struct callback_head *rcu;
148 	STAILQ_HEAD(, callback_head) tmp_head;
149 	uintptr_t offset;
150 
151 	linux_set_current(curthread);
152 
153 	head = context;
154 
155 	/* move current callbacks into own queue */
156 	mtx_lock(&head->lock);
157 	STAILQ_INIT(&tmp_head);
158 	STAILQ_CONCAT(&tmp_head, &head->cb_head);
159 	mtx_unlock(&head->lock);
160 
161 	/* synchronize */
162 	linux_synchronize_rcu(head - linux_epoch_head);
163 
164 	/* dispatch all callbacks, if any */
165 	while ((rcu = STAILQ_FIRST(&tmp_head)) != NULL) {
166 
167 		STAILQ_REMOVE_HEAD(&tmp_head, entry);
168 
169 		offset = (uintptr_t)rcu->func;
170 
171 		if (offset < LINUX_KFREE_RCU_OFFSET_MAX)
172 			kfree((char *)rcu - offset);
173 		else
174 			rcu->func((struct rcu_head *)rcu);
175 	}
176 }
177 
178 void
179 linux_rcu_read_lock(unsigned type)
180 {
181 	struct linux_epoch_record *record;
182 	struct task_struct *ts;
183 
184 	MPASS(type < RCU_TYPE_MAX);
185 
186 	if (RCU_SKIP())
187 		return;
188 
189 	/*
190 	 * Pin thread to current CPU so that the unlock code gets the
191 	 * same per-CPU epoch record:
192 	 */
193 	sched_pin();
194 
195 	record = &DPCPU_GET(linux_epoch_record[type]);
196 	ts = current;
197 
198 	/*
199 	 * Use a critical section to prevent recursion inside
200 	 * ck_epoch_begin(). Else this function supports recursion.
201 	 */
202 	critical_enter();
203 	ck_epoch_begin(&record->epoch_record, NULL);
204 	ts->rcu_recurse++;
205 	if (ts->rcu_recurse == 1)
206 		TAILQ_INSERT_TAIL(&record->ts_head, ts, rcu_entry);
207 	critical_exit();
208 }
209 
210 void
211 linux_rcu_read_unlock(unsigned type)
212 {
213 	struct linux_epoch_record *record;
214 	struct task_struct *ts;
215 
216 	MPASS(type < RCU_TYPE_MAX);
217 
218 	if (RCU_SKIP())
219 		return;
220 
221 	record = &DPCPU_GET(linux_epoch_record[type]);
222 	ts = current;
223 
224 	/*
225 	 * Use a critical section to prevent recursion inside
226 	 * ck_epoch_end(). Else this function supports recursion.
227 	 */
228 	critical_enter();
229 	ck_epoch_end(&record->epoch_record, NULL);
230 	ts->rcu_recurse--;
231 	if (ts->rcu_recurse == 0)
232 		TAILQ_REMOVE(&record->ts_head, ts, rcu_entry);
233 	critical_exit();
234 
235 	sched_unpin();
236 }
237 
238 static void
239 linux_synchronize_rcu_cb(ck_epoch_t *epoch __unused, ck_epoch_record_t *epoch_record, void *arg __unused)
240 {
241 	struct linux_epoch_record *record =
242 	    container_of(epoch_record, struct linux_epoch_record, epoch_record);
243 	struct thread *td = curthread;
244 	struct task_struct *ts;
245 
246 	/* check if blocked on the current CPU */
247 	if (record->cpuid == PCPU_GET(cpuid)) {
248 		bool is_sleeping = 0;
249 		u_char prio = 0;
250 
251 		/*
252 		 * Find the lowest priority or sleeping thread which
253 		 * is blocking synchronization on this CPU core. All
254 		 * the threads in the queue are CPU-pinned and cannot
255 		 * go anywhere while the current thread is locked.
256 		 */
257 		TAILQ_FOREACH(ts, &record->ts_head, rcu_entry) {
258 			if (ts->task_thread->td_priority > prio)
259 				prio = ts->task_thread->td_priority;
260 			is_sleeping |= (ts->task_thread->td_inhibitors != 0);
261 		}
262 
263 		if (is_sleeping) {
264 			thread_unlock(td);
265 			pause("W", 1);
266 			thread_lock(td);
267 		} else {
268 			/* set new thread priority */
269 			sched_prio(td, prio);
270 			/* task switch */
271 			mi_switch(SW_VOL | SWT_RELINQUISH);
272 			/*
273 			 * It is important the thread lock is dropped
274 			 * while yielding to allow other threads to
275 			 * acquire the lock pointed to by
276 			 * TDQ_LOCKPTR(td). Currently mi_switch() will
277 			 * unlock the thread lock before
278 			 * returning. Else a deadlock like situation
279 			 * might happen.
280 			 */
281 			thread_lock(td);
282 		}
283 	} else {
284 		/*
285 		 * To avoid spinning move execution to the other CPU
286 		 * which is blocking synchronization. Set highest
287 		 * thread priority so that code gets run. The thread
288 		 * priority will be restored later.
289 		 */
290 		sched_prio(td, 0);
291 		sched_bind(td, record->cpuid);
292 	}
293 }
294 
295 void
296 linux_synchronize_rcu(unsigned type)
297 {
298 	struct thread *td;
299 	int was_bound;
300 	int old_cpu;
301 	int old_pinned;
302 	u_char old_prio;
303 
304 	MPASS(type < RCU_TYPE_MAX);
305 
306 	if (RCU_SKIP())
307 		return;
308 
309 	WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
310 	    "linux_synchronize_rcu() can sleep");
311 
312 	td = curthread;
313 	DROP_GIANT();
314 
315 	/*
316 	 * Synchronizing RCU might change the CPU core this function
317 	 * is running on. Save current values:
318 	 */
319 	thread_lock(td);
320 
321 	old_cpu = PCPU_GET(cpuid);
322 	old_pinned = td->td_pinned;
323 	old_prio = td->td_priority;
324 	was_bound = sched_is_bound(td);
325 	sched_unbind(td);
326 	td->td_pinned = 0;
327 	sched_bind(td, old_cpu);
328 
329 	ck_epoch_synchronize_wait(&linux_epoch[type],
330 	    &linux_synchronize_rcu_cb, NULL);
331 
332 	/* restore CPU binding, if any */
333 	if (was_bound != 0) {
334 		sched_bind(td, old_cpu);
335 	} else {
336 		/* get thread back to initial CPU, if any */
337 		if (old_pinned != 0)
338 			sched_bind(td, old_cpu);
339 		sched_unbind(td);
340 	}
341 	/* restore pinned after bind */
342 	td->td_pinned = old_pinned;
343 
344 	/* restore thread priority */
345 	sched_prio(td, old_prio);
346 	thread_unlock(td);
347 
348 	PICKUP_GIANT();
349 }
350 
351 void
352 linux_rcu_barrier(unsigned type)
353 {
354 	struct linux_epoch_head *head;
355 
356 	MPASS(type < RCU_TYPE_MAX);
357 
358 	linux_synchronize_rcu(type);
359 
360 	head = &linux_epoch_head[type];
361 
362 	/* wait for callbacks to complete */
363 	taskqueue_drain(taskqueue_fast, &head->task);
364 }
365 
366 void
367 linux_call_rcu(unsigned type, struct rcu_head *context, rcu_callback_t func)
368 {
369 	struct callback_head *rcu;
370 	struct linux_epoch_head *head;
371 
372 	MPASS(type < RCU_TYPE_MAX);
373 
374 	rcu = (struct callback_head *)context;
375 	head = &linux_epoch_head[type];
376 
377 	mtx_lock(&head->lock);
378 	rcu->func = func;
379 	STAILQ_INSERT_TAIL(&head->cb_head, rcu, entry);
380 	taskqueue_enqueue(taskqueue_fast, &head->task);
381 	mtx_unlock(&head->lock);
382 }
383 
384 int
385 init_srcu_struct(struct srcu_struct *srcu)
386 {
387 	return (0);
388 }
389 
390 void
391 cleanup_srcu_struct(struct srcu_struct *srcu)
392 {
393 }
394 
395 int
396 srcu_read_lock(struct srcu_struct *srcu)
397 {
398 	linux_rcu_read_lock(RCU_TYPE_SLEEPABLE);
399 	return (0);
400 }
401 
402 void
403 srcu_read_unlock(struct srcu_struct *srcu, int key __unused)
404 {
405 	linux_rcu_read_unlock(RCU_TYPE_SLEEPABLE);
406 }
407 
408 void
409 synchronize_srcu(struct srcu_struct *srcu)
410 {
411 	linux_synchronize_rcu(RCU_TYPE_SLEEPABLE);
412 }
413 
414 void
415 srcu_barrier(struct srcu_struct *srcu)
416 {
417 	linux_rcu_barrier(RCU_TYPE_SLEEPABLE);
418 }
419