1 /*- 2 * Copyright (c) 2016 Matthew Macy (mmacy@mattmacy.io) 3 * Copyright (c) 2017 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; 94 static struct linux_epoch_head linux_epoch_head; 95 DPCPU_DEFINE_STATIC(struct linux_epoch_record, linux_epoch_record); 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 105 ck_epoch_init(&linux_epoch); 106 107 head = &linux_epoch_head; 108 109 mtx_init(&head->lock, "LRCU-HEAD", NULL, MTX_DEF); 110 TASK_INIT(&head->task, 0, linux_rcu_cleaner_func, NULL); 111 STAILQ_INIT(&head->cb_head); 112 113 CPU_FOREACH(i) { 114 struct linux_epoch_record *record; 115 116 record = &DPCPU_ID_GET(i, linux_epoch_record); 117 118 record->cpuid = i; 119 ck_epoch_register(&linux_epoch, &record->epoch_record, NULL); 120 TAILQ_INIT(&record->ts_head); 121 } 122 } 123 SYSINIT(linux_rcu_runtime, SI_SUB_CPU, SI_ORDER_ANY, linux_rcu_runtime_init, NULL); 124 125 static void 126 linux_rcu_runtime_uninit(void *arg __unused) 127 { 128 struct linux_epoch_head *head; 129 130 head = &linux_epoch_head; 131 132 /* destroy head lock */ 133 mtx_destroy(&head->lock); 134 } 135 SYSUNINIT(linux_rcu_runtime, SI_SUB_LOCK, SI_ORDER_SECOND, linux_rcu_runtime_uninit, NULL); 136 137 static void 138 linux_rcu_cleaner_func(void *context __unused, int pending __unused) 139 { 140 struct linux_epoch_head *head; 141 struct callback_head *rcu; 142 STAILQ_HEAD(, callback_head) tmp_head; 143 144 linux_set_current(curthread); 145 146 head = &linux_epoch_head; 147 148 /* move current callbacks into own queue */ 149 mtx_lock(&head->lock); 150 STAILQ_INIT(&tmp_head); 151 STAILQ_CONCAT(&tmp_head, &head->cb_head); 152 mtx_unlock(&head->lock); 153 154 /* synchronize */ 155 linux_synchronize_rcu(); 156 157 /* dispatch all callbacks, if any */ 158 while ((rcu = STAILQ_FIRST(&tmp_head)) != NULL) { 159 uintptr_t offset; 160 161 STAILQ_REMOVE_HEAD(&tmp_head, entry); 162 163 offset = (uintptr_t)rcu->func; 164 165 if (offset < LINUX_KFREE_RCU_OFFSET_MAX) 166 kfree((char *)rcu - offset); 167 else 168 rcu->func((struct rcu_head *)rcu); 169 } 170 } 171 172 void 173 linux_rcu_read_lock(void) 174 { 175 struct linux_epoch_record *record; 176 struct task_struct *ts; 177 178 if (RCU_SKIP()) 179 return; 180 181 /* 182 * Pin thread to current CPU so that the unlock code gets the 183 * same per-CPU epoch record: 184 */ 185 sched_pin(); 186 187 record = &DPCPU_GET(linux_epoch_record); 188 ts = current; 189 190 /* 191 * Use a critical section to prevent recursion inside 192 * ck_epoch_begin(). Else this function supports recursion. 193 */ 194 critical_enter(); 195 ck_epoch_begin(&record->epoch_record, NULL); 196 ts->rcu_recurse++; 197 if (ts->rcu_recurse == 1) 198 TAILQ_INSERT_TAIL(&record->ts_head, ts, rcu_entry); 199 critical_exit(); 200 } 201 202 void 203 linux_rcu_read_unlock(void) 204 { 205 struct linux_epoch_record *record; 206 struct task_struct *ts; 207 208 if (RCU_SKIP()) 209 return; 210 211 record = &DPCPU_GET(linux_epoch_record); 212 ts = current; 213 214 /* 215 * Use a critical section to prevent recursion inside 216 * ck_epoch_end(). Else this function supports recursion. 217 */ 218 critical_enter(); 219 ck_epoch_end(&record->epoch_record, NULL); 220 ts->rcu_recurse--; 221 if (ts->rcu_recurse == 0) 222 TAILQ_REMOVE(&record->ts_head, ts, rcu_entry); 223 critical_exit(); 224 225 sched_unpin(); 226 } 227 228 static void 229 linux_synchronize_rcu_cb(ck_epoch_t *epoch __unused, ck_epoch_record_t *epoch_record, void *arg __unused) 230 { 231 struct linux_epoch_record *record = 232 container_of(epoch_record, struct linux_epoch_record, epoch_record); 233 struct thread *td = curthread; 234 struct task_struct *ts; 235 236 /* check if blocked on the current CPU */ 237 if (record->cpuid == PCPU_GET(cpuid)) { 238 bool is_sleeping = 0; 239 u_char prio = 0; 240 241 /* 242 * Find the lowest priority or sleeping thread which 243 * is blocking synchronization on this CPU core. All 244 * the threads in the queue are CPU-pinned and cannot 245 * go anywhere while the current thread is locked. 246 */ 247 TAILQ_FOREACH(ts, &record->ts_head, rcu_entry) { 248 if (ts->task_thread->td_priority > prio) 249 prio = ts->task_thread->td_priority; 250 is_sleeping |= (ts->task_thread->td_inhibitors != 0); 251 } 252 253 if (is_sleeping) { 254 thread_unlock(td); 255 pause("W", 1); 256 thread_lock(td); 257 } else { 258 /* set new thread priority */ 259 sched_prio(td, prio); 260 /* task switch */ 261 mi_switch(SW_VOL | SWT_RELINQUISH); 262 /* 263 * It is important the thread lock is dropped 264 * while yielding to allow other threads to 265 * acquire the lock pointed to by 266 * TDQ_LOCKPTR(td). Currently mi_switch() will 267 * unlock the thread lock before 268 * returning. Else a deadlock like situation 269 * might happen. 270 */ 271 thread_lock(td); 272 } 273 } else { 274 /* 275 * To avoid spinning move execution to the other CPU 276 * which is blocking synchronization. Set highest 277 * thread priority so that code gets run. The thread 278 * priority will be restored later. 279 */ 280 sched_prio(td, 0); 281 sched_bind(td, record->cpuid); 282 } 283 } 284 285 void 286 linux_synchronize_rcu(void) 287 { 288 struct thread *td; 289 int was_bound; 290 int old_cpu; 291 int old_pinned; 292 u_char old_prio; 293 294 if (RCU_SKIP()) 295 return; 296 297 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, 298 "linux_synchronize_rcu() can sleep"); 299 300 td = curthread; 301 DROP_GIANT(); 302 303 /* 304 * Synchronizing RCU might change the CPU core this function 305 * is running on. Save current values: 306 */ 307 thread_lock(td); 308 309 old_cpu = PCPU_GET(cpuid); 310 old_pinned = td->td_pinned; 311 old_prio = td->td_priority; 312 was_bound = sched_is_bound(td); 313 sched_unbind(td); 314 td->td_pinned = 0; 315 sched_bind(td, old_cpu); 316 317 ck_epoch_synchronize_wait(&linux_epoch, 318 &linux_synchronize_rcu_cb, NULL); 319 320 /* restore CPU binding, if any */ 321 if (was_bound != 0) { 322 sched_bind(td, old_cpu); 323 } else { 324 /* get thread back to initial CPU, if any */ 325 if (old_pinned != 0) 326 sched_bind(td, old_cpu); 327 sched_unbind(td); 328 } 329 /* restore pinned after bind */ 330 td->td_pinned = old_pinned; 331 332 /* restore thread priority */ 333 sched_prio(td, old_prio); 334 thread_unlock(td); 335 336 PICKUP_GIANT(); 337 } 338 339 void 340 linux_rcu_barrier(void) 341 { 342 struct linux_epoch_head *head; 343 344 linux_synchronize_rcu(); 345 346 head = &linux_epoch_head; 347 348 /* wait for callbacks to complete */ 349 taskqueue_drain(taskqueue_fast, &head->task); 350 } 351 352 void 353 linux_call_rcu(struct rcu_head *context, rcu_callback_t func) 354 { 355 struct callback_head *rcu = (struct callback_head *)context; 356 struct linux_epoch_head *head = &linux_epoch_head; 357 358 mtx_lock(&head->lock); 359 rcu->func = func; 360 STAILQ_INSERT_TAIL(&head->cb_head, rcu, entry); 361 taskqueue_enqueue(taskqueue_fast, &head->task); 362 mtx_unlock(&head->lock); 363 } 364 365 int 366 init_srcu_struct(struct srcu_struct *srcu) 367 { 368 return (0); 369 } 370 371 void 372 cleanup_srcu_struct(struct srcu_struct *srcu) 373 { 374 } 375 376 int 377 srcu_read_lock(struct srcu_struct *srcu) 378 { 379 linux_rcu_read_lock(); 380 return (0); 381 } 382 383 void 384 srcu_read_unlock(struct srcu_struct *srcu, int key __unused) 385 { 386 linux_rcu_read_unlock(); 387 } 388 389 void 390 synchronize_srcu(struct srcu_struct *srcu) 391 { 392 linux_synchronize_rcu(); 393 } 394 395 void 396 srcu_barrier(struct srcu_struct *srcu) 397 { 398 linux_rcu_barrier(); 399 } 400