xref: /dragonfly/sys/kern/kern_mutex.c (revision 25a2db75)
1 /*
2  * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 /*
35  * Implement fast persistent locks based on atomic_cmpset_int() with
36  * semantics similar to lockmgr locks but faster and taking up much less
37  * space.  Taken from HAMMER's lock implementation.
38  *
39  * These are meant to complement our LWKT tokens.  Tokens are only held
40  * while the thread is running.  Mutexes can be held across blocking
41  * conditions.
42  *
43  * Most of the support is in sys/mutex[2].h.  We mostly provide backoff
44  * functions here.
45  */
46 
47 #include <sys/param.h>
48 #include <sys/systm.h>
49 #include <sys/kernel.h>
50 #include <sys/sysctl.h>
51 #include <sys/thread.h>
52 
53 #include <machine/cpufunc.h>
54 
55 #include <sys/thread2.h>
56 #include <sys/mutex2.h>
57 
58 static __int64_t mtx_contention_count;
59 static __int64_t mtx_collision_count;
60 static __int64_t mtx_wakeup_count;
61 
62 SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW,
63 	    &mtx_contention_count, 0, "");
64 SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW,
65 	    &mtx_collision_count, 0, "");
66 SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW,
67 	    &mtx_wakeup_count, 0, "");
68 
69 static void mtx_chain_link(mtx_t mtx);
70 static void mtx_delete_link(mtx_t mtx, mtx_link_t link);
71 
72 /*
73  * Exclusive-lock a mutex, block until acquired.  Recursion is allowed.
74  *
75  * Returns 0 on success, or the tsleep() return code on failure.
76  * An error can only be returned if PCATCH is specified in the flags.
77  */
78 static __inline int
79 __mtx_lock_ex(mtx_t mtx, mtx_link_t link, const char *ident, int flags, int to)
80 {
81 	u_int	lock;
82 	u_int	nlock;
83 	int	error;
84 
85 	for (;;) {
86 		lock = mtx->mtx_lock;
87 		if (lock == 0) {
88 			nlock = MTX_EXCLUSIVE | 1;
89 			if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
90 				mtx->mtx_owner = curthread;
91 				error = 0;
92 				break;
93 			}
94 		} else if ((lock & MTX_EXCLUSIVE) &&
95 			   mtx->mtx_owner == curthread) {
96 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
97 			nlock = lock + 1;
98 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
99 				error = 0;
100 				break;
101 			}
102 		} else {
103 			/*
104 			 * Clearing MTX_EXLINK in lock causes us to loop until
105 			 * MTX_EXLINK is available.  However, to avoid
106 			 * unnecessary cpu cache traffic we poll instead.
107 			 *
108 			 * Setting MTX_EXLINK in nlock causes us to loop until
109 			 * we can acquire MTX_EXLINK.
110 			 *
111 			 * Also set MTX_EXWANTED coincident with EXLINK, if
112 			 * not already set.
113 			 */
114 			thread_t td;
115 
116 			if (lock & MTX_EXLINK) {
117 				cpu_pause();
118 				++mtx_collision_count;
119 				continue;
120 			}
121 			td = curthread;
122 			/*lock &= ~MTX_EXLINK;*/
123 			nlock = lock | MTX_EXWANTED | MTX_EXLINK;
124 			++td->td_critcount;
125 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
126 				/*
127 				 * Check for early abort
128 				 */
129 				if (link->state == MTX_LINK_ABORTED) {
130 					atomic_clear_int(&mtx->mtx_lock,
131 							 MTX_EXLINK);
132 					--td->td_critcount;
133 					error = ENOLCK;
134 					if (mtx->mtx_link == NULL) {
135 						atomic_clear_int(&mtx->mtx_lock,
136 								 MTX_EXWANTED);
137 					}
138 					break;
139 				}
140 
141 				/*
142 				 * Success.  Link in our structure then
143 				 * release EXLINK and sleep.
144 				 */
145 				link->owner = td;
146 				link->state = MTX_LINK_LINKED;
147 				if (mtx->mtx_link) {
148 					link->next = mtx->mtx_link;
149 					link->prev = link->next->prev;
150 					link->next->prev = link;
151 					link->prev->next = link;
152 				} else {
153 					link->next = link;
154 					link->prev = link;
155 					mtx->mtx_link = link;
156 				}
157 				tsleep_interlock(link, 0);
158 				atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
159 				--td->td_critcount;
160 
161 				error = tsleep(link, flags, ident, to);
162 				++mtx_contention_count;
163 
164 				/*
165 				 * Normal unlink, we should own the exclusive
166 				 * lock now.
167 				 */
168 				if (link->state == MTX_LINK_LINKED)
169 					mtx_delete_link(mtx, link);
170 				if (link->state == MTX_LINK_ACQUIRED) {
171 					KKASSERT(mtx->mtx_owner == link->owner);
172 					error = 0;
173 					break;
174 				}
175 
176 				/*
177 				 * Aborted lock (mtx_abort_ex called).
178 				 */
179 				if (link->state == MTX_LINK_ABORTED) {
180 					error = ENOLCK;
181 					break;
182 				}
183 
184 				/*
185 				 * tsleep error, else retry.
186 				 */
187 				if (error)
188 					break;
189 			} else {
190 				--td->td_critcount;
191 			}
192 		}
193 		++mtx_collision_count;
194 	}
195 	return (error);
196 }
197 
198 int
199 _mtx_lock_ex_link(mtx_t mtx, mtx_link_t link,
200 		  const char *ident, int flags, int to)
201 {
202 	return(__mtx_lock_ex(mtx, link, ident, flags, to));
203 }
204 
205 int
206 _mtx_lock_ex(mtx_t mtx, const char *ident, int flags, int to)
207 {
208 	struct mtx_link link;
209 
210 	mtx_link_init(&link);
211 	return(__mtx_lock_ex(mtx, &link, ident, flags, to));
212 }
213 
214 int
215 _mtx_lock_ex_quick(mtx_t mtx, const char *ident)
216 {
217 	struct mtx_link link;
218 
219 	mtx_link_init(&link);
220 	return(__mtx_lock_ex(mtx, &link, ident, 0, 0));
221 }
222 
223 /*
224  * Share-lock a mutex, block until acquired.  Recursion is allowed.
225  *
226  * Returns 0 on success, or the tsleep() return code on failure.
227  * An error can only be returned if PCATCH is specified in the flags.
228  *
229  * NOTE: Shared locks get a mass-wakeup so if the tsleep fails we
230  *	 do not have to chain the wakeup().
231  */
232 static __inline int
233 __mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
234 {
235 	u_int	lock;
236 	u_int	nlock;
237 	int	error;
238 
239 	for (;;) {
240 		lock = mtx->mtx_lock;
241 		if ((lock & MTX_EXCLUSIVE) == 0) {
242 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
243 			nlock = lock + 1;
244 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
245 				error = 0;
246 				break;
247 			}
248 		} else {
249 			nlock = lock | MTX_SHWANTED;
250 			tsleep_interlock(mtx, 0);
251 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
252 				error = tsleep(mtx, flags, ident, to);
253 				if (error)
254 					break;
255 				++mtx_contention_count;
256 				/* retry */
257 			} else {
258 				crit_enter();
259 				tsleep_remove(curthread);
260 				crit_exit();
261 			}
262 		}
263 		++mtx_collision_count;
264 	}
265 	return (error);
266 }
267 
268 int
269 _mtx_lock_sh(mtx_t mtx, const char *ident, int flags, int to)
270 {
271 	return (__mtx_lock_sh(mtx, ident, flags, to));
272 }
273 
274 int
275 _mtx_lock_sh_quick(mtx_t mtx, const char *ident)
276 {
277 	return (__mtx_lock_sh(mtx, ident, 0, 0));
278 }
279 
280 /*
281  * Get an exclusive spinlock the hard way.
282  */
283 void
284 _mtx_spinlock(mtx_t mtx)
285 {
286 	u_int	lock;
287 	u_int	nlock;
288 	int	bb = 1;
289 	int	bo;
290 
291 	for (;;) {
292 		lock = mtx->mtx_lock;
293 		if (lock == 0) {
294 			nlock = MTX_EXCLUSIVE | 1;
295 			if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
296 				mtx->mtx_owner = curthread;
297 				break;
298 			}
299 		} else if ((lock & MTX_EXCLUSIVE) &&
300 			   mtx->mtx_owner == curthread) {
301 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
302 			nlock = lock + 1;
303 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
304 				break;
305 		} else {
306 			/* MWAIT here */
307 			if (bb < 1000)
308 				++bb;
309 			cpu_pause();
310 			for (bo = 0; bo < bb; ++bo)
311 				;
312 			++mtx_contention_count;
313 		}
314 		cpu_pause();
315 		++mtx_collision_count;
316 	}
317 }
318 
319 /*
320  * Attempt to acquire a spinlock, if we fail we must undo the
321  * gd->gd_spinlocks/gd->gd_curthead->td_critcount predisposition.
322  *
323  * Returns 0 on success, EAGAIN on failure.
324  */
325 int
326 _mtx_spinlock_try(mtx_t mtx)
327 {
328 	globaldata_t gd = mycpu;
329 	u_int	lock;
330 	u_int	nlock;
331 	int	res = 0;
332 
333 	for (;;) {
334 		lock = mtx->mtx_lock;
335 		if (lock == 0) {
336 			nlock = MTX_EXCLUSIVE | 1;
337 			if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
338 				mtx->mtx_owner = gd->gd_curthread;
339 				break;
340 			}
341 		} else if ((lock & MTX_EXCLUSIVE) &&
342 			   mtx->mtx_owner == gd->gd_curthread) {
343 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
344 			nlock = lock + 1;
345 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
346 				break;
347 		} else {
348 			--gd->gd_spinlocks;
349 			cpu_ccfence();
350 			--gd->gd_curthread->td_critcount;
351 			res = EAGAIN;
352 			break;
353 		}
354 		cpu_pause();
355 		++mtx_collision_count;
356 	}
357 	return res;
358 }
359 
360 #if 0
361 
362 void
363 _mtx_spinlock_sh(mtx_t mtx)
364 {
365 	u_int	lock;
366 	u_int	nlock;
367 	int	bb = 1;
368 	int	bo;
369 
370 	for (;;) {
371 		lock = mtx->mtx_lock;
372 		if ((lock & MTX_EXCLUSIVE) == 0) {
373 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
374 			nlock = lock + 1;
375 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
376 				break;
377 		} else {
378 			/* MWAIT here */
379 			if (bb < 1000)
380 				++bb;
381 			cpu_pause();
382 			for (bo = 0; bo < bb; ++bo)
383 				;
384 			++mtx_contention_count;
385 		}
386 		cpu_pause();
387 		++mtx_collision_count;
388 	}
389 }
390 
391 #endif
392 
393 int
394 _mtx_lock_ex_try(mtx_t mtx)
395 {
396 	u_int	lock;
397 	u_int	nlock;
398 	int	error = 0;
399 
400 	for (;;) {
401 		lock = mtx->mtx_lock;
402 		if (lock == 0) {
403 			nlock = MTX_EXCLUSIVE | 1;
404 			if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) {
405 				mtx->mtx_owner = curthread;
406 				break;
407 			}
408 		} else if ((lock & MTX_EXCLUSIVE) &&
409 			   mtx->mtx_owner == curthread) {
410 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
411 			nlock = lock + 1;
412 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
413 				break;
414 		} else {
415 			error = EAGAIN;
416 			break;
417 		}
418 		cpu_pause();
419 		++mtx_collision_count;
420 	}
421 	return (error);
422 }
423 
424 int
425 _mtx_lock_sh_try(mtx_t mtx)
426 {
427 	u_int	lock;
428 	u_int	nlock;
429 	int	error = 0;
430 
431 	for (;;) {
432 		lock = mtx->mtx_lock;
433 		if ((lock & MTX_EXCLUSIVE) == 0) {
434 			KKASSERT((lock & MTX_MASK) != MTX_MASK);
435 			nlock = lock + 1;
436 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
437 				break;
438 		} else {
439 			error = EAGAIN;
440 			break;
441 		}
442 		cpu_pause();
443 		++mtx_collision_count;
444 	}
445 	return (error);
446 }
447 
448 /*
449  * If the lock is held exclusively it must be owned by the caller.  If the
450  * lock is already a shared lock this operation is a NOP.  A panic will
451  * occur if the lock is not held either shared or exclusive.
452  *
453  * The exclusive count is converted to a shared count.
454  */
455 void
456 _mtx_downgrade(mtx_t mtx)
457 {
458 	u_int	lock;
459 	u_int	nlock;
460 
461 	for (;;) {
462 		lock = mtx->mtx_lock;
463 		if ((lock & MTX_EXCLUSIVE) == 0) {
464 			KKASSERT((lock & MTX_MASK) > 0);
465 			break;
466 		}
467 		KKASSERT(mtx->mtx_owner == curthread);
468 		nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED);
469 		if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
470 			if (lock & MTX_SHWANTED) {
471 				wakeup(mtx);
472 				++mtx_wakeup_count;
473 			}
474 			break;
475 		}
476 		cpu_pause();
477 		++mtx_collision_count;
478 	}
479 }
480 
481 /*
482  * Upgrade a shared lock to an exclusive lock.  The upgrade will fail if
483  * the shared lock has a count other then 1.  Optimize the most likely case
484  * but note that a single cmpset can fail due to WANTED races.
485  *
486  * If the lock is held exclusively it must be owned by the caller and
487  * this function will simply return without doing anything.   A panic will
488  * occur if the lock is held exclusively by someone other then the caller.
489  *
490  * Returns 0 on success, EDEADLK on failure.
491  */
492 int
493 _mtx_upgrade_try(mtx_t mtx)
494 {
495 	u_int	lock;
496 	u_int	nlock;
497 	int	error = 0;
498 
499 	for (;;) {
500 		lock = mtx->mtx_lock;
501 
502 		if ((lock & ~MTX_EXWANTED) == 1) {
503 			nlock = lock | MTX_EXCLUSIVE;
504 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
505 				mtx->mtx_owner = curthread;
506 				break;
507 			}
508 		} else if (lock & MTX_EXCLUSIVE) {
509 			KKASSERT(mtx->mtx_owner == curthread);
510 			break;
511 		} else {
512 			error = EDEADLK;
513 			break;
514 		}
515 		cpu_pause();
516 		++mtx_collision_count;
517 	}
518 	return (error);
519 }
520 
521 /*
522  * Unlock a lock.  The caller must hold the lock either shared or exclusive.
523  *
524  * Any release which makes the lock available when others want an exclusive
525  * lock causes us to chain the owner to the next exclusive lock instead of
526  * releasing the lock.
527  */
528 void
529 _mtx_unlock(mtx_t mtx)
530 {
531 	u_int	lock;
532 	u_int	nlock;
533 
534 	for (;;) {
535 		lock = mtx->mtx_lock;
536 		nlock = lock & ~(MTX_SHWANTED | MTX_EXLINK);
537 
538 		if (nlock == 1) {
539 			/*
540 			 * Last release, shared lock, no exclusive waiters.
541 			 */
542 			nlock = lock & MTX_EXLINK;
543 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
544 				break;
545 		} else if (nlock == (MTX_EXCLUSIVE | 1)) {
546 			/*
547 			 * Last release, exclusive lock, no exclusive waiters.
548 			 * Wake up any shared waiters.
549 			 */
550 			mtx->mtx_owner = NULL;
551 			nlock = lock & MTX_EXLINK;
552 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
553 				if (lock & MTX_SHWANTED) {
554 					wakeup(mtx);
555 					++mtx_wakeup_count;
556 				}
557 				break;
558 			}
559 		} else if (nlock == (MTX_EXWANTED | 1)) {
560 			/*
561 			 * Last release, shared lock, with exclusive
562 			 * waiters.
563 			 *
564 			 * Wait for EXLINK to clear, then acquire it.
565 			 * We could use the cmpset for this but polling
566 			 * is better on the cpu caches.
567 			 *
568 			 * Acquire an exclusive lock leaving the lockcount
569 			 * set to 1, and get EXLINK for access to mtx_link.
570 			 */
571 			thread_t td;
572 
573 			if (lock & MTX_EXLINK) {
574 				cpu_pause();
575 				++mtx_collision_count;
576 				continue;
577 			}
578 			td = curthread;
579 			/*lock &= ~MTX_EXLINK;*/
580 			nlock |= MTX_EXLINK | MTX_EXCLUSIVE;
581 			nlock |= (lock & MTX_SHWANTED);
582 			++td->td_critcount;
583 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
584 				mtx_chain_link(mtx);
585 				--td->td_critcount;
586 				break;
587 			}
588 			--td->td_critcount;
589 		} else if (nlock == (MTX_EXCLUSIVE | MTX_EXWANTED | 1)) {
590 			/*
591 			 * Last release, exclusive lock, with exclusive
592 			 * waiters.
593 			 *
594 			 * leave the exclusive lock intact and the lockcount
595 			 * set to 1, and get EXLINK for access to mtx_link.
596 			 */
597 			thread_t td;
598 
599 			if (lock & MTX_EXLINK) {
600 				cpu_pause();
601 				++mtx_collision_count;
602 				continue;
603 			}
604 			td = curthread;
605 			/*lock &= ~MTX_EXLINK;*/
606 			nlock |= MTX_EXLINK;
607 			nlock |= (lock & MTX_SHWANTED);
608 			++td->td_critcount;
609 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
610 				mtx_chain_link(mtx);
611 				--td->td_critcount;
612 				break;
613 			}
614 			--td->td_critcount;
615 		} else {
616 			/*
617 			 * Not the last release (shared or exclusive)
618 			 */
619 			nlock = lock - 1;
620 			KKASSERT((nlock & MTX_MASK) != MTX_MASK);
621 			if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
622 				break;
623 		}
624 		cpu_pause();
625 		++mtx_collision_count;
626 	}
627 }
628 
629 /*
630  * Chain mtx_chain_link.  Called with the lock held exclusively with a
631  * single ref count, and also with MTX_EXLINK held.
632  */
633 static void
634 mtx_chain_link(mtx_t mtx)
635 {
636 	mtx_link_t link;
637 	u_int	lock;
638 	u_int	nlock;
639 	u_int	clock;	/* bits we own and want to clear */
640 
641 	/*
642 	 * Chain the exclusive lock to the next link.  The caller cleared
643 	 * SHWANTED so if there is no link we have to wake up any shared
644 	 * waiters.
645 	 */
646 	clock = MTX_EXLINK;
647 	if ((link = mtx->mtx_link) != NULL) {
648 		KKASSERT(link->state == MTX_LINK_LINKED);
649 		if (link->next == link) {
650 			mtx->mtx_link = NULL;
651 			clock |= MTX_EXWANTED;
652 		} else {
653 			mtx->mtx_link = link->next;
654 			link->next->prev = link->prev;
655 			link->prev->next = link->next;
656 		}
657 		link->state = MTX_LINK_ACQUIRED;
658 		mtx->mtx_owner = link->owner;
659 	} else {
660 		/*
661 		 * Chain was empty, release the exclusive lock's last count
662 		 * as well the bits shown.
663 		 */
664 		clock |= MTX_EXCLUSIVE | MTX_EXWANTED | MTX_SHWANTED | 1;
665 	}
666 
667 	/*
668 	 * We have to uset cmpset here to deal with MTX_SHWANTED.  If
669 	 * we just clear the bits we can miss a wakeup or, worse,
670 	 * leave mtx_lock unlocked with MTX_SHWANTED still set.
671 	 */
672 	for (;;) {
673 		lock = mtx->mtx_lock;
674 		nlock = lock & ~clock;
675 
676 		if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) {
677 			if (link) {
678 				/*
679 				 * Wakeup new exclusive holder.  Leave
680 				 * SHWANTED intact.
681 				 */
682 				wakeup(link);
683 			} else if (lock & MTX_SHWANTED) {
684 				/*
685 				 * Signal any shared waiters (and we also
686 				 * clear SHWANTED).
687 				 */
688 				mtx->mtx_owner = NULL;
689 				wakeup(mtx);
690 				++mtx_wakeup_count;
691 			}
692 			break;
693 		}
694 		cpu_pause();
695 		++mtx_collision_count;
696 	}
697 }
698 
699 /*
700  * Delete a link structure after tsleep has failed.  This code is not
701  * in the critical path as most exclusive waits are chained.
702  */
703 static
704 void
705 mtx_delete_link(mtx_t mtx, mtx_link_t link)
706 {
707 	thread_t td = curthread;
708 	u_int	lock;
709 	u_int	nlock;
710 
711 	/*
712 	 * Acquire MTX_EXLINK.
713 	 *
714 	 * Do not use cmpxchg to wait for EXLINK to clear as this might
715 	 * result in too much cpu cache traffic.
716 	 */
717 	++td->td_critcount;
718 	for (;;) {
719 		lock = mtx->mtx_lock;
720 		if (lock & MTX_EXLINK) {
721 			cpu_pause();
722 			++mtx_collision_count;
723 			continue;
724 		}
725 		/* lock &= ~MTX_EXLINK; */
726 		nlock = lock | MTX_EXLINK;
727 		if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
728 			break;
729 		cpu_pause();
730 		++mtx_collision_count;
731 	}
732 
733 	/*
734 	 * Delete the link and release EXLINK.
735 	 */
736 	if (link->state == MTX_LINK_LINKED) {
737 		if (link->next == link) {
738 			mtx->mtx_link = NULL;
739 		} else {
740 			mtx->mtx_link = link->next;
741 			link->next->prev = link->prev;
742 			link->prev->next = link->next;
743 		}
744 		link->state = MTX_LINK_IDLE;
745 	}
746 	atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
747 	--td->td_critcount;
748 }
749 
750 /*
751  * Abort a mutex locking operation, causing mtx_lock_ex_link() to
752  * return ENOLCK.  This may be called at any time after the
753  * mtx_link is initialized, including both before and after the call
754  * to mtx_lock_ex_link().
755  */
756 void
757 mtx_abort_ex_link(mtx_t mtx, mtx_link_t link)
758 {
759 	thread_t td = curthread;
760 	u_int	lock;
761 	u_int	nlock;
762 
763 	/*
764 	 * Acquire MTX_EXLINK
765 	 */
766 	++td->td_critcount;
767 	for (;;) {
768 		lock = mtx->mtx_lock;
769 		if (lock & MTX_EXLINK) {
770 			cpu_pause();
771 			++mtx_collision_count;
772 			continue;
773 		}
774 		/* lock &= ~MTX_EXLINK; */
775 		nlock = lock | MTX_EXLINK;
776 		if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock))
777 			break;
778 		cpu_pause();
779 		++mtx_collision_count;
780 	}
781 
782 	/*
783 	 * Do the abort
784 	 */
785 	switch(link->state) {
786 	case MTX_LINK_IDLE:
787 		/*
788 		 * Link not started yet
789 		 */
790 		link->state = MTX_LINK_ABORTED;
791 		break;
792 	case MTX_LINK_LINKED:
793 		/*
794 		 * de-link, mark aborted, and wakeup the thread.
795 		 */
796 		if (link->next == link) {
797 			mtx->mtx_link = NULL;
798 		} else {
799 			mtx->mtx_link = link->next;
800 			link->next->prev = link->prev;
801 			link->prev->next = link->next;
802 		}
803 		link->state = MTX_LINK_ABORTED;
804 		wakeup(link);
805 		break;
806 	case MTX_LINK_ACQUIRED:
807 		/*
808 		 * Too late, the lock was acquired.  Let it complete.
809 		 */
810 		break;
811 	default:
812 		/*
813 		 * link already aborted, do nothing.
814 		 */
815 		break;
816 	}
817 	atomic_clear_int(&mtx->mtx_lock, MTX_EXLINK);
818 	--td->td_critcount;
819 }
820