1 /*- 2 * Copyright (c) 2016 Matthew Macy (mmacy@mattmacy.io) 3 * Copyright (c) 2017-2021 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 #include <sys/types.h> 30 #include <sys/systm.h> 31 #include <sys/malloc.h> 32 #include <sys/kernel.h> 33 #include <sys/lock.h> 34 #include <sys/mutex.h> 35 #include <sys/proc.h> 36 #include <sys/sched.h> 37 #include <sys/smp.h> 38 #include <sys/queue.h> 39 #include <sys/taskqueue.h> 40 #include <sys/kdb.h> 41 42 #include <ck_epoch.h> 43 44 #include <linux/rcupdate.h> 45 #include <linux/srcu.h> 46 #include <linux/slab.h> 47 #include <linux/kernel.h> 48 #include <linux/compat.h> 49 #include <linux/llist.h> 50 #include <linux/irq_work.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 union { 64 STAILQ_ENTRY(callback_head) entry; 65 struct llist_node node; 66 }; 67 rcu_callback_t func; 68 }; 69 70 struct linux_epoch_head { 71 struct llist_head cb_head; 72 struct task task; 73 } __aligned(CACHE_LINE_SIZE); 74 75 struct linux_epoch_record { 76 ck_epoch_record_t epoch_record; 77 TAILQ_HEAD(, task_struct) ts_head; 78 int cpuid; 79 int type; 80 } __aligned(CACHE_LINE_SIZE); 81 82 /* 83 * Verify that "struct rcu_head" is big enough to hold "struct 84 * callback_head". This has been done to avoid having to add special 85 * compile flags for including ck_epoch.h to all clients of the 86 * LinuxKPI. 87 */ 88 CTASSERT(sizeof(struct rcu_head) == sizeof(struct callback_head)); 89 90 /* 91 * Verify that "rcu_section[0]" has the same size as 92 * "ck_epoch_section_t". This has been done to avoid having to add 93 * special compile flags for including ck_epoch.h to all clients of 94 * the LinuxKPI. 95 */ 96 CTASSERT(sizeof(((struct task_struct *)0)->rcu_section[0] == 97 sizeof(ck_epoch_section_t))); 98 99 /* 100 * Verify that "epoch_record" is at beginning of "struct 101 * linux_epoch_record": 102 */ 103 CTASSERT(offsetof(struct linux_epoch_record, epoch_record) == 0); 104 105 CTASSERT(TS_RCU_TYPE_MAX == RCU_TYPE_MAX); 106 107 static ck_epoch_t linux_epoch[RCU_TYPE_MAX]; 108 static struct linux_epoch_head linux_epoch_head[RCU_TYPE_MAX]; 109 DPCPU_DEFINE_STATIC(struct linux_epoch_record, linux_epoch_record[RCU_TYPE_MAX]); 110 111 static void linux_rcu_cleaner_func(void *, int); 112 113 static void 114 linux_rcu_runtime_init(void *arg __unused) 115 { 116 struct linux_epoch_head *head; 117 int i; 118 int j; 119 120 for (j = 0; j != RCU_TYPE_MAX; j++) { 121 ck_epoch_init(&linux_epoch[j]); 122 123 head = &linux_epoch_head[j]; 124 125 TASK_INIT(&head->task, 0, linux_rcu_cleaner_func, head); 126 init_llist_head(&head->cb_head); 127 128 CPU_FOREACH(i) { 129 struct linux_epoch_record *record; 130 131 record = &DPCPU_ID_GET(i, linux_epoch_record[j]); 132 133 record->cpuid = i; 134 record->type = j; 135 ck_epoch_register(&linux_epoch[j], 136 &record->epoch_record, NULL); 137 TAILQ_INIT(&record->ts_head); 138 } 139 } 140 } 141 SYSINIT(linux_rcu_runtime, SI_SUB_CPU, SI_ORDER_ANY, linux_rcu_runtime_init, NULL); 142 143 static void 144 linux_rcu_cleaner_func(void *context, int pending __unused) 145 { 146 struct linux_epoch_head *head = context; 147 struct callback_head *rcu; 148 STAILQ_HEAD(, callback_head) tmp_head; 149 struct llist_node *node, *next; 150 uintptr_t offset; 151 152 /* move current callbacks into own queue */ 153 STAILQ_INIT(&tmp_head); 154 llist_for_each_safe(node, next, llist_del_all(&head->cb_head)) { 155 rcu = container_of(node, struct callback_head, node); 156 /* re-reverse list to restore chronological order */ 157 STAILQ_INSERT_HEAD(&tmp_head, rcu, entry); 158 } 159 160 /* synchronize */ 161 linux_synchronize_rcu(head - linux_epoch_head); 162 163 /* dispatch all callbacks, if any */ 164 while ((rcu = STAILQ_FIRST(&tmp_head)) != NULL) { 165 STAILQ_REMOVE_HEAD(&tmp_head, entry); 166 167 offset = (uintptr_t)rcu->func; 168 169 if (offset < LINUX_KFREE_RCU_OFFSET_MAX) 170 kfree((char *)rcu - offset); 171 else 172 rcu->func((struct rcu_head *)rcu); 173 } 174 } 175 176 void 177 linux_rcu_read_lock(unsigned type) 178 { 179 struct linux_epoch_record *record; 180 struct task_struct *ts; 181 182 MPASS(type < RCU_TYPE_MAX); 183 184 if (RCU_SKIP()) 185 return; 186 187 ts = current; 188 189 /* assert valid refcount */ 190 MPASS(ts->rcu_recurse[type] != INT_MAX); 191 192 if (++(ts->rcu_recurse[type]) != 1) 193 return; 194 195 /* 196 * Pin thread to current CPU so that the unlock code gets the 197 * same per-CPU epoch record: 198 */ 199 sched_pin(); 200 201 record = &DPCPU_GET(linux_epoch_record[type]); 202 203 /* 204 * Use a critical section to prevent recursion inside 205 * ck_epoch_begin(). Else this function supports recursion. 206 */ 207 critical_enter(); 208 ck_epoch_begin(&record->epoch_record, 209 (ck_epoch_section_t *)&ts->rcu_section[type]); 210 TAILQ_INSERT_TAIL(&record->ts_head, ts, rcu_entry[type]); 211 critical_exit(); 212 } 213 214 void 215 linux_rcu_read_unlock(unsigned type) 216 { 217 struct linux_epoch_record *record; 218 struct task_struct *ts; 219 220 MPASS(type < RCU_TYPE_MAX); 221 222 if (RCU_SKIP()) 223 return; 224 225 ts = current; 226 227 /* assert valid refcount */ 228 MPASS(ts->rcu_recurse[type] > 0); 229 230 if (--(ts->rcu_recurse[type]) != 0) 231 return; 232 233 record = &DPCPU_GET(linux_epoch_record[type]); 234 235 /* 236 * Use a critical section to prevent recursion inside 237 * ck_epoch_end(). Else this function supports recursion. 238 */ 239 critical_enter(); 240 ck_epoch_end(&record->epoch_record, 241 (ck_epoch_section_t *)&ts->rcu_section[type]); 242 TAILQ_REMOVE(&record->ts_head, ts, rcu_entry[type]); 243 critical_exit(); 244 245 sched_unpin(); 246 } 247 248 static void 249 linux_synchronize_rcu_cb(ck_epoch_t *epoch __unused, ck_epoch_record_t *epoch_record, void *arg __unused) 250 { 251 struct linux_epoch_record *record = 252 container_of(epoch_record, struct linux_epoch_record, epoch_record); 253 struct thread *td = curthread; 254 struct task_struct *ts; 255 256 /* check if blocked on the current CPU */ 257 if (record->cpuid == PCPU_GET(cpuid)) { 258 bool is_sleeping = 0; 259 u_char prio = 0; 260 261 /* 262 * Find the lowest priority or sleeping thread which 263 * is blocking synchronization on this CPU core. All 264 * the threads in the queue are CPU-pinned and cannot 265 * go anywhere while the current thread is locked. 266 */ 267 TAILQ_FOREACH(ts, &record->ts_head, rcu_entry[record->type]) { 268 if (ts->task_thread->td_priority > prio) 269 prio = ts->task_thread->td_priority; 270 is_sleeping |= (ts->task_thread->td_inhibitors != 0); 271 } 272 273 if (is_sleeping) { 274 thread_unlock(td); 275 pause("W", 1); 276 thread_lock(td); 277 } else { 278 /* set new thread priority */ 279 sched_prio(td, prio); 280 /* task switch */ 281 mi_switch(SW_VOL | SWT_RELINQUISH); 282 /* 283 * It is important the thread lock is dropped 284 * while yielding to allow other threads to 285 * acquire the lock pointed to by 286 * TDQ_LOCKPTR(td). Currently mi_switch() will 287 * unlock the thread lock before 288 * returning. Else a deadlock like situation 289 * might happen. 290 */ 291 thread_lock(td); 292 } 293 } else { 294 /* 295 * To avoid spinning move execution to the other CPU 296 * which is blocking synchronization. Set highest 297 * thread priority so that code gets run. The thread 298 * priority will be restored later. 299 */ 300 sched_prio(td, 0); 301 sched_bind(td, record->cpuid); 302 } 303 } 304 305 void 306 linux_synchronize_rcu(unsigned type) 307 { 308 struct thread *td; 309 int was_bound; 310 int old_cpu; 311 int old_pinned; 312 u_char old_prio; 313 314 MPASS(type < RCU_TYPE_MAX); 315 316 if (RCU_SKIP()) 317 return; 318 319 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, 320 "linux_synchronize_rcu() can sleep"); 321 322 td = curthread; 323 DROP_GIANT(); 324 325 /* 326 * Synchronizing RCU might change the CPU core this function 327 * is running on. Save current values: 328 */ 329 thread_lock(td); 330 331 old_cpu = PCPU_GET(cpuid); 332 old_pinned = td->td_pinned; 333 old_prio = td->td_priority; 334 was_bound = sched_is_bound(td); 335 sched_unbind(td); 336 td->td_pinned = 0; 337 sched_bind(td, old_cpu); 338 339 ck_epoch_synchronize_wait(&linux_epoch[type], 340 &linux_synchronize_rcu_cb, NULL); 341 342 /* restore CPU binding, if any */ 343 if (was_bound != 0) { 344 sched_bind(td, old_cpu); 345 } else { 346 /* get thread back to initial CPU, if any */ 347 if (old_pinned != 0) 348 sched_bind(td, old_cpu); 349 sched_unbind(td); 350 } 351 /* restore pinned after bind */ 352 td->td_pinned = old_pinned; 353 354 /* restore thread priority */ 355 sched_prio(td, old_prio); 356 thread_unlock(td); 357 358 PICKUP_GIANT(); 359 } 360 361 void 362 linux_rcu_barrier(unsigned type) 363 { 364 struct linux_epoch_head *head; 365 366 MPASS(type < RCU_TYPE_MAX); 367 368 /* 369 * This function is not obligated to wait for a grace period. 370 * It only waits for RCU callbacks that have already been posted. 371 * If there are no RCU callbacks posted, rcu_barrier() can return 372 * immediately. 373 */ 374 head = &linux_epoch_head[type]; 375 376 /* wait for callbacks to complete */ 377 taskqueue_drain(linux_irq_work_tq, &head->task); 378 } 379 380 void 381 linux_call_rcu(unsigned type, struct rcu_head *context, rcu_callback_t func) 382 { 383 struct callback_head *rcu; 384 struct linux_epoch_head *head; 385 386 MPASS(type < RCU_TYPE_MAX); 387 388 rcu = (struct callback_head *)context; 389 head = &linux_epoch_head[type]; 390 391 rcu->func = func; 392 llist_add(&rcu->node, &head->cb_head); 393 taskqueue_enqueue(linux_irq_work_tq, &head->task); 394 } 395 396 int 397 init_srcu_struct(struct srcu_struct *srcu) 398 { 399 return (0); 400 } 401 402 void 403 cleanup_srcu_struct(struct srcu_struct *srcu) 404 { 405 } 406 407 int 408 srcu_read_lock(struct srcu_struct *srcu) 409 { 410 linux_rcu_read_lock(RCU_TYPE_SLEEPABLE); 411 return (0); 412 } 413 414 void 415 srcu_read_unlock(struct srcu_struct *srcu, int key __unused) 416 { 417 linux_rcu_read_unlock(RCU_TYPE_SLEEPABLE); 418 } 419 420 void 421 synchronize_srcu(struct srcu_struct *srcu) 422 { 423 linux_synchronize_rcu(RCU_TYPE_SLEEPABLE); 424 } 425 426 void 427 srcu_barrier(struct srcu_struct *srcu) 428 { 429 linux_rcu_barrier(RCU_TYPE_SLEEPABLE); 430 } 431