xref: /freebsd/sys/kern/kern_rmlock.c (revision 39beb93c) 
1 /*-
2  * Copyright (c) 2007 Stephan Uphoff <ups@FreeBSD.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the author nor the names of any co-contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 /*
31  * Machine independent bits of reader/writer lock implementation.
32  */
33 
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
36 
37 #include "opt_ddb.h"
38 
39 #include <sys/param.h>
40 #include <sys/systm.h>
41 
42 #include <sys/kernel.h>
43 #include <sys/ktr.h>
44 #include <sys/lock.h>
45 #include <sys/mutex.h>
46 #include <sys/proc.h>
47 #include <sys/rmlock.h>
48 #include <sys/sched.h>
49 #include <sys/smp.h>
50 #include <sys/systm.h>
51 #include <sys/turnstile.h>
52 #include <sys/lock_profile.h>
53 #include <machine/cpu.h>
54 
55 #ifdef DDB
56 #include <ddb/ddb.h>
57 #endif
58 
59 #define RMPF_ONQUEUE	1
60 #define RMPF_SIGNAL	2
61 
62 /*
63  * To support usage of rmlock in CVs and msleep
64  * yet another list for the priority tracker
65  * would be needed.
66  * Using this lock for cv and msleep also does
67  * not seem very useful
68  */
69 
70 static __inline void compiler_memory_barrier(void) {
71 	__asm __volatile("":::"memory");
72 }
73 
74 static void assert_rm(struct lock_object *lock, int what);
75 static void lock_rm(struct lock_object *lock, int how);
76 static int unlock_rm(struct lock_object *lock);
77 
78 struct lock_class lock_class_rm = {
79 	.lc_name = "rm",
80 	.lc_flags = LC_SLEEPLOCK | LC_RECURSABLE,
81 	.lc_assert = assert_rm,
82 #if 0
83 #ifdef DDB
84 	.lc_ddb_show = db_show_rwlock,
85 #endif
86 #endif
87 	.lc_lock = lock_rm,
88 	.lc_unlock = unlock_rm,
89 };
90 
91 static void
92 assert_rm(struct lock_object *lock, int what)
93 {
94 
95 	panic("assert_rm called");
96 }
97 
98 static void
99 lock_rm(struct lock_object *lock, int how) {
100 	panic("lock_rm called");
101 }
102 
103 static int
104 unlock_rm(struct lock_object *lock) {
105 	panic("unlock_rm called");
106 }
107 
108 static struct mtx rm_spinlock;
109 
110 MTX_SYSINIT(rm_spinlock, &rm_spinlock, "rm_spinlock", MTX_SPIN);
111 
112 /*
113  * Add or remove tracker from per cpu list.
114  * The per cpu list can be traversed at any time in forward
115  * direction from an interrupt on the *local* cpu.
116  */
117 
118 static void inline
119 rm_tracker_add(struct pcpu *pc, struct rm_priotracker* tracker) {
120 	struct rm_queue* next;
121 	/* Initialize all tracker pointers */
122 	tracker->rmp_cpuQueue.rmq_prev = &pc->pc_rm_queue;
123 	next = pc->pc_rm_queue.rmq_next;
124 	tracker->rmp_cpuQueue.rmq_next = next;
125 	/* rmq_prev is not used during froward traversal */
126 	next->rmq_prev = &tracker->rmp_cpuQueue;
127 	/* Update pointer to first element */
128 	pc->pc_rm_queue.rmq_next =  &tracker->rmp_cpuQueue;
129 }
130 
131 
132 static void inline
133 rm_tracker_remove(struct pcpu *pc, struct rm_priotracker* tracker) {
134 	struct rm_queue *next, *prev;
135 	next =   tracker->rmp_cpuQueue.rmq_next;
136 	prev =   tracker->rmp_cpuQueue.rmq_prev;
137 	/* Not used during forward traversal */
138 	next->rmq_prev = prev;
139 	/* Remove from list */
140 	prev->rmq_next = next;
141 }
142 
143 
144 
145 
146 static void rm_cleanIPI(void *arg) {
147 	struct pcpu *pc;
148 	struct rmlock* rm = arg;
149 	struct rm_priotracker *tracker;
150 	struct rm_queue* queue;
151 	pc = pcpu_find(curcpu);
152 
153 	for(queue = pc->pc_rm_queue.rmq_next;
154 	    queue !=  &pc->pc_rm_queue;
155 	    queue = queue->rmq_next) {
156 		tracker = (struct rm_priotracker *) queue;
157 		if(tracker->rmp_rmlock == rm && tracker->rmp_flags == 0 ) {
158 			tracker->rmp_flags = RMPF_ONQUEUE;
159 			mtx_lock_spin(&rm_spinlock);
160 			LIST_INSERT_HEAD(&rm->rm_activeReaders,tracker,
161 			    rmp_qentry);
162 			mtx_unlock_spin(&rm_spinlock);
163 		}
164 	}
165 	return;
166 }
167 
168 
169 
170 void
171 rm_init(struct rmlock *rm, const char *name, int opts)
172 {
173 	rm->rm_noreadtoken = 1;
174 	LIST_INIT(&rm->rm_activeReaders);
175 	mtx_init(&rm->rm_lock, name, "RM_MTX",MTX_NOWITNESS);
176 	lock_init(&rm->lock_object, &lock_class_rm, name, NULL, (opts & LO_RECURSABLE)| LO_WITNESS);
177 
178 }
179 
180 void
181 rm_destroy(struct rmlock *rm)
182 {
183 	mtx_destroy(&rm->rm_lock);
184 	lock_destroy(&rm->lock_object);
185 }
186 
187 int
188 rm_wowned(struct rmlock *rm)
189 {
190 
191 	return (mtx_owned(&rm->rm_lock));
192 }
193 
194 void
195 rm_sysinit(void *arg)
196 {
197 	struct rm_args *args = arg;
198 	rm_init(args->ra_rm, args->ra_desc, args->ra_opts);
199 }
200 
201 
202 static void
203 _rm_rlock_hard(struct rmlock *rm, struct rm_priotracker* tracker)
204 {
205 	struct pcpu *pc;
206 	struct rm_queue *queue;
207 	struct rm_priotracker* atracker;
208 
209 	critical_enter();
210 	pc = pcpu_find(curcpu);
211 
212 	/* Check if we just need to do a proper critical_exit */
213 	if (0 == rm->rm_noreadtoken) {
214 		critical_exit();
215 		return;
216 	}
217 
218 	/* Remove our tracker from the per cpu list */
219 	rm_tracker_remove(pc,tracker);
220 
221 	/* Check to see if the IPI granted us the lock after all */
222 	if(tracker->rmp_flags) {
223 		/* Just add back tracker - we hold the lock */
224 		rm_tracker_add(pc,tracker);
225 		critical_exit();
226 		return;
227 	}
228 
229 
230 
231 	/*
232 	 * We allow readers to aquire a lock even if a writer
233 	 * is blocked if the lock is recursive and the reader
234 	 * already holds the lock
235 	 */
236 
237 	if ((rm->lock_object.lo_flags & LO_RECURSABLE) != 0) {
238 		/*
239 		 * Just grand the lock if this thread already have a tracker
240 		 * for this lock on the per cpu queue
241 		 */
242 
243 		for(queue = pc->pc_rm_queue.rmq_next;
244 		    queue !=  &pc->pc_rm_queue;
245 		    queue = queue->rmq_next) {
246 			atracker = (struct rm_priotracker *) queue;
247 			if (( atracker->rmp_rmlock == rm) &&
248 			    ( atracker->rmp_thread == tracker->rmp_thread )) {
249 				mtx_lock_spin(&rm_spinlock);
250 				LIST_INSERT_HEAD(&rm->rm_activeReaders,tracker,
251 				    rmp_qentry);
252 				tracker->rmp_flags = RMPF_ONQUEUE;
253 				mtx_unlock_spin(&rm_spinlock);
254 				rm_tracker_add(pc,tracker);
255 				critical_exit();
256 				return;
257 			}
258 		}
259 	}
260 
261 
262 	sched_unpin();
263 	critical_exit();
264 
265 	mtx_lock(&rm->rm_lock);
266 	rm->rm_noreadtoken = 0;
267 	critical_enter();
268 
269 	pc = pcpu_find(curcpu);
270 	rm_tracker_add(pc,tracker);
271 	sched_pin();
272 	critical_exit();
273 
274 	mtx_unlock(&rm->rm_lock);
275 	return;
276 }
277 
278 void
279 _rm_rlock(struct rmlock *rm, struct rm_priotracker* tracker)
280 {
281 	struct thread *td = curthread;
282 	struct pcpu *pc;
283 
284 	tracker->rmp_flags  = 0;
285 	tracker->rmp_thread = td;
286 	tracker->rmp_rmlock = rm;
287 
288 	td->td_critnest++;	/* critical_enter(); */
289 
290 	compiler_memory_barrier();
291 
292 	pc = cpuid_to_pcpu[td->td_oncpu]; /* pcpu_find(td->td_oncpu); */
293 
294 	rm_tracker_add(pc,tracker);
295 
296 	td->td_pinned++; /*  sched_pin(); */
297 
298 	compiler_memory_barrier();
299 
300 	td->td_critnest--;
301 
302 	/*
303 	 * Fast path to combine two common conditions
304 	 * into a single conditional jump
305 	 */
306 
307 	if (0 == (td->td_owepreempt |  rm->rm_noreadtoken)) {
308 		return;
309 	}
310 
311 	/* We do not have a read token and need to acquire one */
312 	_rm_rlock_hard(rm,tracker);
313 }
314 
315 
316 static void
317 _rm_unlock_hard(struct thread *td,struct rm_priotracker* tracker)
318 {
319 
320 	if (td->td_owepreempt) {
321 		td->td_critnest++;
322 		critical_exit();
323 	}
324 
325 	if (!tracker->rmp_flags) {
326 		return;
327 	}
328 
329 
330 	mtx_lock_spin(&rm_spinlock);
331 	LIST_REMOVE(tracker,rmp_qentry);
332 
333 	if (tracker->rmp_flags & RMPF_SIGNAL) {
334 		struct rmlock *rm;
335 		struct turnstile* ts;
336 
337 		rm = tracker->rmp_rmlock;
338 
339 		turnstile_chain_lock(&rm->lock_object);
340 		mtx_unlock_spin(&rm_spinlock);
341 
342 		ts = turnstile_lookup(&rm->lock_object);
343 
344 		turnstile_signal(ts, TS_EXCLUSIVE_QUEUE);
345 		turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
346 		turnstile_chain_unlock(&rm->lock_object);
347 
348 
349 	} else
350 		mtx_unlock_spin(&rm_spinlock);
351 
352 }
353 
354 void
355 _rm_runlock(struct rmlock *rm, struct rm_priotracker* tracker)
356 {
357 	struct pcpu *pc;
358 	struct thread *td = tracker->rmp_thread;
359 
360 	td->td_critnest++;	/* critical_enter(); */
361 	pc = cpuid_to_pcpu[td->td_oncpu]; /* pcpu_find(td->td_oncpu); */
362 	rm_tracker_remove(pc,tracker);
363 	td->td_critnest--;
364 	td->td_pinned--; /*  sched_unpin(); */
365 
366 	if (0 == (td->td_owepreempt | tracker->rmp_flags))
367 		return;
368 
369 
370 	_rm_unlock_hard(td,tracker);
371 
372 
373 }
374 
375 
376 void
377 _rm_wlock(struct rmlock *rm)
378 {
379 	struct rm_priotracker *prio;
380 	struct turnstile *ts;
381 
382 	mtx_lock(&rm->rm_lock);
383 
384 	if (rm->rm_noreadtoken == 0) {
385 		/* Get all read tokens back */
386 
387 		rm->rm_noreadtoken = 1;
388 
389 		/*
390 		 * Assumes rm->rm_noreadtoken update is visible
391 		 * on other CPUs before rm_cleanIPI is called
392 		 */
393 #ifdef SMP
394    		smp_rendezvous(smp_no_rendevous_barrier,
395 		    rm_cleanIPI,
396 		    smp_no_rendevous_barrier
397 		    ,rm);
398 
399 #else
400 		rm_cleanIPI(rm);
401 #endif
402 
403 
404 		mtx_lock_spin(&rm_spinlock);
405 
406 		while((prio = LIST_FIRST(&rm->rm_activeReaders)) != NULL) {
407 			ts = turnstile_trywait(&rm->lock_object);
408 			prio->rmp_flags = RMPF_ONQUEUE | RMPF_SIGNAL;
409 			mtx_unlock_spin(&rm_spinlock);
410 			turnstile_wait(ts,prio->rmp_thread,
411 		    TS_EXCLUSIVE_QUEUE);
412 			mtx_lock_spin(&rm_spinlock);
413 
414 		}
415 
416 		mtx_unlock_spin(&rm_spinlock);
417 	}
418 
419 }
420 
421 
422 void
423 _rm_wunlock(struct rmlock *rm)
424 {
425 	mtx_unlock(&rm->rm_lock);
426 }
427 
428 
429 #ifdef LOCK_DEBUG
430 
431 void _rm_wlock_debug(struct rmlock *rm, const char *file, int line)
432 {
433 
434 
435 	WITNESS_CHECKORDER(&rm->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE,
436 	    file, line, NULL);
437 
438 	_rm_wlock(rm);
439 
440 	LOCK_LOG_LOCK("RMWLOCK", &rm->lock_object, 0, 0, file, line);
441 
442 	WITNESS_LOCK(&rm->lock_object, LOP_EXCLUSIVE, file, line);
443 
444 	curthread->td_locks++;
445 
446 }
447 
448 void	_rm_wunlock_debug(struct rmlock *rm, const char *file, int line)
449 {
450 	curthread->td_locks--;
451 	WITNESS_UNLOCK(&rm->lock_object, LOP_EXCLUSIVE, file, line);
452 	LOCK_LOG_LOCK("RMWUNLOCK", &rm->lock_object, 0, 0, file, line);
453 	_rm_wunlock(rm);
454 }
455 
456 
457 void
458 _rm_rlock_debug(struct rmlock *rm, struct rm_priotracker *tracker,
459     const char *file, int line)
460 {
461 
462 
463 	WITNESS_CHECKORDER(&rm->lock_object, LOP_NEWORDER , file, line, NULL);
464 
465 	_rm_rlock(rm, tracker);
466 
467 	LOCK_LOG_LOCK("RMRLOCK", &rm->lock_object, 0, 0, file, line);
468 
469 	WITNESS_LOCK(&rm->lock_object, 0 , file, line);
470 
471 	curthread->td_locks++;
472 }
473 
474 void
475 _rm_runlock_debug(struct rmlock *rm,  struct rm_priotracker *tracker,
476     const char *file, int line) {
477 	curthread->td_locks--;
478 	WITNESS_UNLOCK(&rm->lock_object, 0 , file, line);
479 	LOCK_LOG_LOCK("RMRUNLOCK", &rm->lock_object, 0, 0, file, line);
480 	_rm_runlock(rm, tracker);
481 }
482 
483 
484 
485 
486 #else
487 /*
488  * Just strip out file and line arguments if no lock debugging is enabled
489  * in the kernel - we are called from a kernel module.
490 */
491 
492 
493 void _rm_wlock_debug(struct rmlock *rm, const char *file, int line)
494 {
495 	_rm_wlock(rm);
496 }
497 
498 void	_rm_wunlock_debug(struct rmlock *rm, const char *file, int line)
499 {
500 	_rm_wunlock(rm);
501 }
502 
503 void
504 _rm_rlock_debug(struct rmlock *rm, struct rm_priotracker *tracker,
505     const char *file, int line)
506 {
507 	_rm_rlock(rm, tracker);
508 }
509 
510 void
511 _rm_runlock_debug(struct rmlock *rm,  struct rm_priotracker *tracker,
512     const char *file, int line) {
513 	_rm_runlock(rm, tracker);
514 }
515 
516 #endif
517