1 /* $NetBSD: linux_rcu.c,v 1.4 2021/12/19 11:49:11 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2018 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #include <sys/cdefs.h> 33 __KERNEL_RCSID(0, "$NetBSD: linux_rcu.c,v 1.4 2021/12/19 11:49:11 riastradh Exp $"); 34 35 #include <sys/param.h> 36 #include <sys/types.h> 37 #include <sys/condvar.h> 38 #include <sys/cpu.h> 39 #include <sys/kthread.h> 40 #include <sys/mutex.h> 41 #include <sys/sdt.h> 42 #include <sys/xcall.h> 43 44 #include <linux/rcupdate.h> 45 #include <linux/slab.h> 46 47 SDT_PROBE_DEFINE0(sdt, linux, rcu, synchronize__start); 48 SDT_PROBE_DEFINE1(sdt, linux, rcu, synchronize__cpu, "unsigned"/*cpu*/); 49 SDT_PROBE_DEFINE0(sdt, linux, rcu, synchronize__done); 50 SDT_PROBE_DEFINE0(sdt, linux, rcu, barrier__start); 51 SDT_PROBE_DEFINE0(sdt, linux, rcu, barrier__done); 52 SDT_PROBE_DEFINE2(sdt, linux, rcu, call__queue, 53 "struct rcu_head *"/*head*/, "void (*)(struct rcu_head *)"/*callback*/); 54 SDT_PROBE_DEFINE2(sdt, linux, rcu, call__run, 55 "struct rcu_head *"/*head*/, "void (*)(struct rcu_head *)"/*callback*/); 56 SDT_PROBE_DEFINE2(sdt, linux, rcu, call__done, 57 "struct rcu_head *"/*head*/, "void (*)(struct rcu_head *)"/*callback*/); 58 SDT_PROBE_DEFINE2(sdt, linux, rcu, kfree__queue, 59 "struct rcu_head *"/*head*/, "void *"/*obj*/); 60 SDT_PROBE_DEFINE2(sdt, linux, rcu, kfree__free, 61 "struct rcu_head *"/*head*/, "void *"/*obj*/); 62 SDT_PROBE_DEFINE2(sdt, linux, rcu, kfree__done, 63 "struct rcu_head *"/*head*/, "void *"/*obj*/); 64 65 static struct { 66 kmutex_t lock; 67 kcondvar_t cv; 68 struct rcu_head *first_callback; 69 struct rcu_head *first_kfree; 70 struct lwp *lwp; 71 uint64_t gen; 72 bool dying; 73 } gc __cacheline_aligned; 74 75 static void 76 synchronize_rcu_xc(void *a, void *b) 77 { 78 79 SDT_PROBE1(sdt, linux, rcu, synchronize__cpu, cpu_index(curcpu())); 80 } 81 82 /* 83 * synchronize_rcu() 84 * 85 * Wait for any pending RCU read section on every CPU to complete 86 * by triggering on every CPU activity that is blocked by an RCU 87 * read section. 88 * 89 * May sleep. (Practically guaranteed to sleep!) 90 */ 91 void 92 synchronize_rcu(void) 93 { 94 95 SDT_PROBE0(sdt, linux, rcu, synchronize__start); 96 xc_wait(xc_broadcast(0, &synchronize_rcu_xc, NULL, NULL)); 97 SDT_PROBE0(sdt, linux, rcu, synchronize__done); 98 } 99 100 /* 101 * synchronize_rcu_expedited() 102 * 103 * Wait for any pending RCU read section on every CPU to complete 104 * by triggering on every CPU activity that is blocked by an RCU 105 * read section. Try to get an answer faster than 106 * synchronize_rcu, at the cost of more activity triggered on 107 * other CPUs. 108 * 109 * May sleep. (Practically guaranteed to sleep!) 110 */ 111 void 112 synchronize_rcu_expedited(void) 113 { 114 115 synchronize_rcu(); 116 } 117 118 /* 119 * cookie = get_state_synchronize_rcu(), cond_synchronize_rcu(cookie) 120 * 121 * Optimization for synchronize_rcu -- skip if it has already 122 * happened between get_state_synchronize_rcu and 123 * cond_synchronize_rcu. get_state_synchronize_rcu implies a full 124 * SMP memory barrier (membar_sync). 125 */ 126 unsigned long 127 get_state_synchronize_rcu(void) 128 { 129 130 membar_sync(); 131 return 0; 132 } 133 134 void 135 cond_synchronize_rcu(unsigned long cookie) 136 { 137 138 synchronize_rcu(); 139 } 140 141 /* 142 * rcu_barrier() 143 * 144 * Wait for all pending RCU callbacks to complete. 145 * 146 * Does not imply, and is not implied by, synchronize_rcu. 147 */ 148 void 149 rcu_barrier(void) 150 { 151 uint64_t gen; 152 153 SDT_PROBE0(sdt, linux, rcu, barrier__start); 154 mutex_enter(&gc.lock); 155 if (gc.first_callback != NULL || gc.first_kfree != NULL) { 156 gen = gc.gen; 157 do { 158 cv_wait(&gc.cv, &gc.lock); 159 } while (gc.gen == gen); 160 } 161 mutex_exit(&gc.lock); 162 SDT_PROBE0(sdt, linux, rcu, barrier__done); 163 } 164 165 /* 166 * call_rcu(head, callback) 167 * 168 * Arrange to call callback(head) after any pending RCU read 169 * sections on every CPU is complete. Return immediately. 170 */ 171 void 172 call_rcu(struct rcu_head *head, void (*callback)(struct rcu_head *)) 173 { 174 175 head->rcuh_u.callback = callback; 176 177 mutex_enter(&gc.lock); 178 head->rcuh_next = gc.first_callback; 179 gc.first_callback = head; 180 cv_broadcast(&gc.cv); 181 SDT_PROBE2(sdt, linux, rcu, call__queue, head, callback); 182 mutex_exit(&gc.lock); 183 } 184 185 /* 186 * _kfree_rcu(head, obj) 187 * 188 * kfree_rcu helper: schedule kfree(obj) using head for storage. 189 */ 190 void 191 _kfree_rcu(struct rcu_head *head, void *obj) 192 { 193 194 head->rcuh_u.obj = obj; 195 196 mutex_enter(&gc.lock); 197 head->rcuh_next = gc.first_kfree; 198 gc.first_kfree = head; 199 cv_broadcast(&gc.cv); 200 SDT_PROBE2(sdt, linux, rcu, kfree__queue, head, obj); 201 mutex_exit(&gc.lock); 202 } 203 204 static void 205 gc_thread(void *cookie) 206 { 207 struct rcu_head *head_callback, *head_kfree, *head, *next; 208 209 mutex_enter(&gc.lock); 210 for (;;) { 211 /* Start with no work. */ 212 bool work = false; 213 214 /* Grab the list of callbacks. */ 215 if ((head_callback = gc.first_callback) != NULL) { 216 gc.first_callback = NULL; 217 work = true; 218 } 219 220 /* Grab the list of objects to kfree. */ 221 if ((head_kfree = gc.first_kfree) != NULL) { 222 gc.first_kfree = NULL; 223 work = true; 224 } 225 226 /* 227 * If no work, then either stop, if we're dying, or 228 * wait for work, if not. 229 */ 230 if (!work) { 231 if (gc.dying) 232 break; 233 cv_wait(&gc.cv, &gc.lock); 234 continue; 235 } 236 237 /* We have work to do. Drop the lock to do it. */ 238 mutex_exit(&gc.lock); 239 240 /* Wait for activity on all CPUs. */ 241 synchronize_rcu(); 242 243 /* Call the callbacks. */ 244 for (head = head_callback; head != NULL; head = next) { 245 void (*callback)(struct rcu_head *) = 246 head->rcuh_u.callback; 247 next = head->rcuh_next; 248 SDT_PROBE2(sdt, linux, rcu, call__run, 249 head, callback); 250 (*callback)(head); 251 /* 252 * Can't dereference head or invoke 253 * callback after this point. 254 */ 255 SDT_PROBE2(sdt, linux, rcu, call__done, 256 head, callback); 257 } 258 259 /* Free the objects to kfree. */ 260 for (head = head_kfree; head != NULL; head = next) { 261 void *obj = head->rcuh_u.obj; 262 next = head->rcuh_next; 263 SDT_PROBE2(sdt, linux, rcu, kfree__free, head, obj); 264 kfree(obj); 265 /* Can't dereference head or obj after this point. */ 266 SDT_PROBE2(sdt, linux, rcu, kfree__done, head, obj); 267 } 268 269 /* Return to the lock. */ 270 mutex_enter(&gc.lock); 271 272 /* Finished a batch of work. Notify rcu_barrier. */ 273 gc.gen++; 274 cv_broadcast(&gc.cv); 275 } 276 KASSERT(gc.first_callback == NULL); 277 KASSERT(gc.first_kfree == NULL); 278 mutex_exit(&gc.lock); 279 280 kthread_exit(0); 281 } 282 283 void 284 init_rcu_head(struct rcu_head *head) 285 { 286 } 287 288 void 289 destroy_rcu_head(struct rcu_head *head) 290 { 291 } 292 293 int 294 linux_rcu_gc_init(void) 295 { 296 int error; 297 298 mutex_init(&gc.lock, MUTEX_DEFAULT, IPL_VM); 299 cv_init(&gc.cv, "lnxrcugc"); 300 gc.first_callback = NULL; 301 gc.first_kfree = NULL; 302 gc.gen = 0; 303 gc.dying = false; 304 305 error = kthread_create(PRI_NONE, 306 KTHREAD_MPSAFE|KTHREAD_TS|KTHREAD_MUSTJOIN, NULL, &gc_thread, NULL, 307 &gc.lwp, "lnxrcugc"); 308 if (error) 309 goto fail; 310 311 /* Success! */ 312 return 0; 313 314 fail: cv_destroy(&gc.cv); 315 mutex_destroy(&gc.lock); 316 return error; 317 } 318 319 void 320 linux_rcu_gc_fini(void) 321 { 322 323 mutex_enter(&gc.lock); 324 gc.dying = true; 325 cv_broadcast(&gc.cv); 326 mutex_exit(&gc.lock); 327 328 kthread_join(gc.lwp); 329 gc.lwp = NULL; 330 KASSERT(gc.first_callback == NULL); 331 KASSERT(gc.first_kfree == NULL); 332 cv_destroy(&gc.cv); 333 mutex_destroy(&gc.lock); 334 } 335