Home | History | Annotate | Line # | Download | only in kern
subr_lockdebug.c revision 1.8.6.8
      1  1.8.6.8    joerg /*	$NetBSD: subr_lockdebug.c,v 1.8.6.8 2007/12/03 16:14:56 joerg Exp $	*/
      2      1.2       ad 
      3      1.2       ad /*-
      4      1.2       ad  * Copyright (c) 2006, 2007 The NetBSD Foundation, Inc.
      5      1.2       ad  * All rights reserved.
      6      1.2       ad  *
      7      1.2       ad  * This code is derived from software contributed to The NetBSD Foundation
      8      1.2       ad  * by Andrew Doran.
      9      1.2       ad  *
     10      1.2       ad  * Redistribution and use in source and binary forms, with or without
     11      1.2       ad  * modification, are permitted provided that the following conditions
     12      1.2       ad  * are met:
     13      1.2       ad  * 1. Redistributions of source code must retain the above copyright
     14      1.2       ad  *    notice, this list of conditions and the following disclaimer.
     15      1.2       ad  * 2. Redistributions in binary form must reproduce the above copyright
     16      1.2       ad  *    notice, this list of conditions and the following disclaimer in the
     17      1.2       ad  *    documentation and/or other materials provided with the distribution.
     18      1.2       ad  * 3. All advertising materials mentioning features or use of this software
     19      1.2       ad  *    must display the following acknowledgement:
     20      1.2       ad  *	This product includes software developed by the NetBSD
     21      1.2       ad  *	Foundation, Inc. and its contributors.
     22      1.2       ad  * 4. Neither the name of The NetBSD Foundation nor the names of its
     23      1.2       ad  *    contributors may be used to endorse or promote products derived
     24      1.2       ad  *    from this software without specific prior written permission.
     25      1.2       ad  *
     26      1.2       ad  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     27      1.2       ad  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     28      1.2       ad  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     29      1.2       ad  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     30      1.2       ad  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     31      1.2       ad  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     32      1.2       ad  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     33      1.2       ad  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     34      1.2       ad  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     35      1.2       ad  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     36      1.2       ad  * POSSIBILITY OF SUCH DAMAGE.
     37      1.2       ad  */
     38      1.2       ad 
     39      1.2       ad /*
     40  1.8.6.3    joerg  * Basic lock debugging code shared among lock primitives.
     41      1.2       ad  */
     42      1.2       ad 
     43  1.8.6.1    joerg #include <sys/cdefs.h>
     44  1.8.6.8    joerg __KERNEL_RCSID(0, "$NetBSD: subr_lockdebug.c,v 1.8.6.8 2007/12/03 16:14:56 joerg Exp $");
     45  1.8.6.1    joerg 
     46      1.2       ad #include "opt_multiprocessor.h"
     47      1.2       ad #include "opt_ddb.h"
     48      1.2       ad 
     49      1.2       ad #include <sys/param.h>
     50      1.2       ad #include <sys/proc.h>
     51      1.2       ad #include <sys/systm.h>
     52  1.8.6.2    joerg #include <sys/kernel.h>
     53      1.2       ad #include <sys/kmem.h>
     54      1.2       ad #include <sys/lock.h>
     55      1.2       ad #include <sys/lockdebug.h>
     56      1.2       ad #include <sys/sleepq.h>
     57  1.8.6.2    joerg #include <sys/cpu.h>
     58  1.8.6.8    joerg #include <sys/atomic.h>
     59      1.2       ad 
     60  1.8.6.6    joerg #include <lib/libkern/rb.h>
     61  1.8.6.6    joerg 
     62      1.2       ad #ifdef LOCKDEBUG
     63      1.2       ad 
     64      1.2       ad #define	LD_BATCH_SHIFT	9
     65      1.2       ad #define	LD_BATCH	(1 << LD_BATCH_SHIFT)
     66      1.2       ad #define	LD_BATCH_MASK	(LD_BATCH - 1)
     67      1.2       ad #define	LD_MAX_LOCKS	1048576
     68      1.2       ad #define	LD_SLOP		16
     69      1.2       ad 
     70      1.2       ad #define	LD_LOCKED	0x01
     71      1.2       ad #define	LD_SLEEPER	0x02
     72      1.2       ad 
     73      1.2       ad typedef union lockdebuglk {
     74      1.2       ad 	struct {
     75      1.2       ad 		__cpu_simple_lock_t	lku_lock;
     76      1.2       ad 		int			lku_oldspl;
     77      1.2       ad 	} ul;
     78      1.2       ad 	uint8_t	lk_pad[64];
     79      1.2       ad } volatile __aligned(64) lockdebuglk_t;
     80      1.2       ad 
     81      1.2       ad #define	lk_lock		ul.lku_lock
     82      1.2       ad #define	lk_oldspl	ul.lku_oldspl
     83      1.2       ad 
     84      1.2       ad typedef struct lockdebug {
     85  1.8.6.6    joerg 	struct rb_node	ld_rb_node;	/* must be the first member */
     86      1.2       ad 	_TAILQ_ENTRY(struct lockdebug, volatile) ld_chain;
     87      1.2       ad 	_TAILQ_ENTRY(struct lockdebug, volatile) ld_achain;
     88      1.2       ad 	volatile void	*ld_lock;
     89      1.2       ad 	lockops_t	*ld_lockops;
     90      1.2       ad 	struct lwp	*ld_lwp;
     91      1.2       ad 	uintptr_t	ld_locked;
     92      1.2       ad 	uintptr_t	ld_unlocked;
     93  1.8.6.2    joerg 	uintptr_t	ld_initaddr;
     94      1.2       ad 	uint16_t	ld_shares;
     95      1.2       ad 	uint16_t	ld_cpu;
     96      1.2       ad 	uint8_t		ld_flags;
     97      1.2       ad 	uint8_t		ld_shwant;	/* advisory */
     98      1.2       ad 	uint8_t		ld_exwant;	/* advisory */
     99      1.2       ad 	uint8_t		ld_unused;
    100      1.2       ad } volatile lockdebug_t;
    101      1.2       ad 
    102      1.2       ad typedef _TAILQ_HEAD(lockdebuglist, struct lockdebug, volatile) lockdebuglist_t;
    103      1.2       ad 
    104  1.8.6.6    joerg lockdebuglk_t		ld_tree_lk;
    105      1.2       ad lockdebuglk_t		ld_sleeper_lk;
    106      1.2       ad lockdebuglk_t		ld_spinner_lk;
    107      1.2       ad lockdebuglk_t		ld_free_lk;
    108      1.2       ad 
    109  1.8.6.5    joerg lockdebuglist_t		ld_sleepers = TAILQ_HEAD_INITIALIZER(ld_sleepers);
    110  1.8.6.5    joerg lockdebuglist_t		ld_spinners = TAILQ_HEAD_INITIALIZER(ld_spinners);
    111  1.8.6.5    joerg lockdebuglist_t		ld_free = TAILQ_HEAD_INITIALIZER(ld_free);
    112  1.8.6.5    joerg lockdebuglist_t		ld_all = TAILQ_HEAD_INITIALIZER(ld_all);
    113      1.2       ad int			ld_nfree;
    114      1.2       ad int			ld_freeptr;
    115      1.2       ad int			ld_recurse;
    116      1.5       ad bool			ld_nomore;
    117      1.2       ad lockdebug_t		*ld_table[LD_MAX_LOCKS / LD_BATCH];
    118      1.2       ad 
    119      1.2       ad lockdebug_t		ld_prime[LD_BATCH];
    120      1.2       ad 
    121      1.5       ad static void	lockdebug_abort1(lockdebug_t *, lockdebuglk_t *lk,
    122  1.8.6.2    joerg 				 const char *, const char *, bool);
    123      1.5       ad static void	lockdebug_more(void);
    124      1.5       ad static void	lockdebug_init(void);
    125      1.2       ad 
    126  1.8.6.6    joerg static signed int
    127  1.8.6.6    joerg ld_rb_compare_nodes(const struct rb_node *n1, const struct rb_node *n2)
    128  1.8.6.6    joerg {
    129  1.8.6.6    joerg 	const lockdebug_t *ld1 = (const void *)n1;
    130  1.8.6.6    joerg 	const lockdebug_t *ld2 = (const void *)n2;
    131  1.8.6.7    joerg 	const uintptr_t a = (uintptr_t)ld1->ld_lock;
    132  1.8.6.7    joerg 	const uintptr_t b = (uintptr_t)ld2->ld_lock;
    133  1.8.6.7    joerg 
    134  1.8.6.7    joerg 	if (a < b)
    135  1.8.6.6    joerg 		return 1;
    136  1.8.6.7    joerg 	if (a > b)
    137  1.8.6.7    joerg 		return -1;
    138  1.8.6.6    joerg 	return 0;
    139  1.8.6.6    joerg }
    140  1.8.6.6    joerg 
    141  1.8.6.6    joerg static signed int
    142  1.8.6.6    joerg ld_rb_compare_key(const struct rb_node *n, const void *key)
    143  1.8.6.6    joerg {
    144  1.8.6.6    joerg 	const lockdebug_t *ld = (const void *)n;
    145  1.8.6.7    joerg 	const uintptr_t a = (uintptr_t)ld->ld_lock;
    146  1.8.6.7    joerg 	const uintptr_t b = (uintptr_t)key;
    147  1.8.6.7    joerg 
    148  1.8.6.7    joerg 	if (a < b)
    149  1.8.6.6    joerg 		return 1;
    150  1.8.6.7    joerg 	if (a > b)
    151  1.8.6.7    joerg 		return -1;
    152  1.8.6.6    joerg 	return 0;
    153  1.8.6.6    joerg }
    154  1.8.6.6    joerg 
    155  1.8.6.6    joerg static struct rb_tree ld_rb_tree;
    156  1.8.6.6    joerg 
    157  1.8.6.6    joerg static const struct rb_tree_ops ld_rb_tree_ops = {
    158  1.8.6.6    joerg 	.rb_compare_nodes = ld_rb_compare_nodes,
    159  1.8.6.6    joerg 	.rb_compare_key = ld_rb_compare_key,
    160  1.8.6.6    joerg };
    161  1.8.6.6    joerg 
    162      1.2       ad static inline void
    163      1.2       ad lockdebug_lock(lockdebuglk_t *lk)
    164      1.2       ad {
    165      1.2       ad 	int s;
    166      1.2       ad 
    167      1.8       ad 	s = splhigh();
    168      1.2       ad 	__cpu_simple_lock(&lk->lk_lock);
    169      1.2       ad 	lk->lk_oldspl = s;
    170      1.2       ad }
    171      1.2       ad 
    172      1.2       ad static inline void
    173      1.2       ad lockdebug_unlock(lockdebuglk_t *lk)
    174      1.2       ad {
    175      1.2       ad 	int s;
    176      1.2       ad 
    177      1.2       ad 	s = lk->lk_oldspl;
    178      1.2       ad 	__cpu_simple_unlock(&(lk->lk_lock));
    179      1.2       ad 	splx(s);
    180      1.2       ad }
    181      1.2       ad 
    182  1.8.6.6    joerg static inline lockdebug_t *
    183  1.8.6.6    joerg lockdebug_lookup1(volatile void *lock, lockdebuglk_t **lk)
    184  1.8.6.2    joerg {
    185  1.8.6.6    joerg 	lockdebug_t *ld;
    186  1.8.6.6    joerg 
    187  1.8.6.6    joerg 	lockdebug_lock(&ld_tree_lk);
    188  1.8.6.6    joerg 	ld = (lockdebug_t *)rb_tree_find_node(&ld_rb_tree, __UNVOLATILE(lock));
    189  1.8.6.6    joerg 	lockdebug_unlock(&ld_tree_lk);
    190  1.8.6.6    joerg 	if (ld == NULL)
    191  1.8.6.6    joerg 		return NULL;
    192  1.8.6.6    joerg 
    193  1.8.6.6    joerg 	if ((ld->ld_flags & LD_SLEEPER) != 0)
    194  1.8.6.6    joerg 		*lk = &ld_sleeper_lk;
    195  1.8.6.6    joerg 	else
    196  1.8.6.6    joerg 		*lk = &ld_spinner_lk;
    197  1.8.6.2    joerg 
    198  1.8.6.2    joerg 	lockdebug_lock(*lk);
    199  1.8.6.6    joerg 	return ld;
    200  1.8.6.2    joerg }
    201  1.8.6.2    joerg 
    202      1.2       ad /*
    203      1.2       ad  * lockdebug_lookup:
    204      1.2       ad  *
    205  1.8.6.6    joerg  *	Find a lockdebug structure by a pointer to a lock and return it locked.
    206      1.2       ad  */
    207      1.2       ad static inline lockdebug_t *
    208  1.8.6.6    joerg lockdebug_lookup(volatile void *lock, lockdebuglk_t **lk)
    209      1.2       ad {
    210  1.8.6.6    joerg 	lockdebug_t *ld;
    211      1.2       ad 
    212  1.8.6.6    joerg 	ld = lockdebug_lookup1(lock, lk);
    213  1.8.6.6    joerg 	if (ld == NULL)
    214  1.8.6.6    joerg 		panic("lockdebug_lookup: uninitialized lock (lock=%p)", lock);
    215      1.2       ad 	return ld;
    216      1.2       ad }
    217      1.2       ad 
    218      1.2       ad /*
    219      1.2       ad  * lockdebug_init:
    220      1.2       ad  *
    221      1.2       ad  *	Initialize the lockdebug system.  Allocate an initial pool of
    222      1.2       ad  *	lockdebug structures before the VM system is up and running.
    223      1.2       ad  */
    224      1.5       ad static void
    225      1.2       ad lockdebug_init(void)
    226      1.2       ad {
    227      1.2       ad 	lockdebug_t *ld;
    228      1.2       ad 	int i;
    229      1.2       ad 
    230  1.8.6.6    joerg 	__cpu_simple_lock_init(&ld_tree_lk.lk_lock);
    231      1.2       ad 	__cpu_simple_lock_init(&ld_sleeper_lk.lk_lock);
    232      1.2       ad 	__cpu_simple_lock_init(&ld_spinner_lk.lk_lock);
    233      1.2       ad 	__cpu_simple_lock_init(&ld_free_lk.lk_lock);
    234      1.2       ad 
    235  1.8.6.6    joerg 	rb_tree_init(&ld_rb_tree, &ld_rb_tree_ops);
    236  1.8.6.6    joerg 
    237      1.2       ad 	ld = ld_prime;
    238      1.2       ad 	ld_table[0] = ld;
    239      1.2       ad 	for (i = 1, ld++; i < LD_BATCH; i++, ld++) {
    240      1.2       ad 		TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain);
    241      1.2       ad 		TAILQ_INSERT_TAIL(&ld_all, ld, ld_achain);
    242      1.2       ad 	}
    243      1.2       ad 	ld_freeptr = 1;
    244      1.2       ad 	ld_nfree = LD_BATCH - 1;
    245      1.2       ad }
    246      1.2       ad 
    247      1.2       ad /*
    248      1.2       ad  * lockdebug_alloc:
    249      1.2       ad  *
    250      1.2       ad  *	A lock is being initialized, so allocate an associated debug
    251      1.2       ad  *	structure.
    252      1.2       ad  */
    253  1.8.6.6    joerg bool
    254  1.8.6.2    joerg lockdebug_alloc(volatile void *lock, lockops_t *lo, uintptr_t initaddr)
    255      1.2       ad {
    256      1.2       ad 	struct cpu_info *ci;
    257      1.2       ad 	lockdebug_t *ld;
    258  1.8.6.6    joerg 	lockdebuglk_t *lk;
    259      1.2       ad 
    260      1.5       ad 	if (lo == NULL || panicstr != NULL)
    261  1.8.6.6    joerg 		return false;
    262      1.5       ad 	if (ld_freeptr == 0)
    263      1.5       ad 		lockdebug_init();
    264      1.2       ad 
    265  1.8.6.6    joerg 	if ((ld = lockdebug_lookup1(lock, &lk)) != NULL) {
    266  1.8.6.6    joerg 		lockdebug_abort1(ld, lk, __func__, "already initialized", true);
    267  1.8.6.6    joerg 		/* NOTREACHED */
    268  1.8.6.6    joerg 	}
    269  1.8.6.6    joerg 
    270      1.2       ad 	ci = curcpu();
    271      1.2       ad 
    272      1.2       ad 	/*
    273      1.2       ad 	 * Pinch a new debug structure.  We may recurse because we call
    274      1.2       ad 	 * kmem_alloc(), which may need to initialize new locks somewhere
    275      1.7    skrll 	 * down the path.  If not recursing, we try to maintain at least
    276      1.2       ad 	 * LD_SLOP structures free, which should hopefully be enough to
    277      1.2       ad 	 * satisfy kmem_alloc().  If we can't provide a structure, not to
    278      1.2       ad 	 * worry: we'll just mark the lock as not having an ID.
    279      1.2       ad 	 */
    280      1.2       ad 	lockdebug_lock(&ld_free_lk);
    281      1.2       ad 	ci->ci_lkdebug_recurse++;
    282      1.2       ad 
    283      1.2       ad 	if (TAILQ_EMPTY(&ld_free)) {
    284      1.5       ad 		if (ci->ci_lkdebug_recurse > 1 || ld_nomore) {
    285      1.2       ad 			ci->ci_lkdebug_recurse--;
    286      1.2       ad 			lockdebug_unlock(&ld_free_lk);
    287  1.8.6.6    joerg 			return false;
    288      1.2       ad 		}
    289      1.2       ad 		lockdebug_more();
    290      1.2       ad 	} else if (ci->ci_lkdebug_recurse == 1 && ld_nfree < LD_SLOP)
    291      1.2       ad 		lockdebug_more();
    292      1.2       ad 
    293      1.2       ad 	if ((ld = TAILQ_FIRST(&ld_free)) == NULL) {
    294      1.2       ad 		lockdebug_unlock(&ld_free_lk);
    295  1.8.6.6    joerg 		return false;
    296      1.2       ad 	}
    297      1.2       ad 
    298      1.2       ad 	TAILQ_REMOVE(&ld_free, ld, ld_chain);
    299      1.2       ad 	ld_nfree--;
    300      1.2       ad 
    301      1.2       ad 	ci->ci_lkdebug_recurse--;
    302      1.2       ad 	lockdebug_unlock(&ld_free_lk);
    303      1.2       ad 
    304      1.2       ad 	if (ld->ld_lock != NULL)
    305      1.2       ad 		panic("lockdebug_alloc: corrupt table");
    306      1.2       ad 
    307      1.2       ad 	if (lo->lo_sleeplock)
    308      1.2       ad 		lockdebug_lock(&ld_sleeper_lk);
    309      1.2       ad 	else
    310      1.2       ad 		lockdebug_lock(&ld_spinner_lk);
    311      1.2       ad 
    312      1.2       ad 	/* Initialise the structure. */
    313      1.2       ad 	ld->ld_lock = lock;
    314      1.2       ad 	ld->ld_lockops = lo;
    315      1.2       ad 	ld->ld_locked = 0;
    316      1.2       ad 	ld->ld_unlocked = 0;
    317      1.2       ad 	ld->ld_lwp = NULL;
    318  1.8.6.2    joerg 	ld->ld_initaddr = initaddr;
    319      1.2       ad 
    320  1.8.6.6    joerg 	lockdebug_lock(&ld_tree_lk);
    321  1.8.6.6    joerg 	rb_tree_insert_node(&ld_rb_tree, __UNVOLATILE(&ld->ld_rb_node));
    322  1.8.6.6    joerg 	lockdebug_unlock(&ld_tree_lk);
    323  1.8.6.6    joerg 
    324      1.2       ad 	if (lo->lo_sleeplock) {
    325      1.2       ad 		ld->ld_flags = LD_SLEEPER;
    326      1.2       ad 		lockdebug_unlock(&ld_sleeper_lk);
    327      1.2       ad 	} else {
    328      1.2       ad 		ld->ld_flags = 0;
    329      1.2       ad 		lockdebug_unlock(&ld_spinner_lk);
    330      1.2       ad 	}
    331      1.2       ad 
    332  1.8.6.6    joerg 	return true;
    333      1.2       ad }
    334      1.2       ad 
    335      1.2       ad /*
    336      1.2       ad  * lockdebug_free:
    337      1.2       ad  *
    338      1.2       ad  *	A lock is being destroyed, so release debugging resources.
    339      1.2       ad  */
    340      1.2       ad void
    341  1.8.6.6    joerg lockdebug_free(volatile void *lock)
    342      1.2       ad {
    343      1.2       ad 	lockdebug_t *ld;
    344      1.2       ad 	lockdebuglk_t *lk;
    345      1.2       ad 
    346      1.2       ad 	if (panicstr != NULL)
    347      1.2       ad 		return;
    348      1.2       ad 
    349  1.8.6.6    joerg 	ld = lockdebug_lookup(lock, &lk);
    350  1.8.6.6    joerg 	if (ld == NULL) {
    351      1.2       ad 		panic("lockdebug_free: destroying uninitialized lock %p"
    352  1.8.6.6    joerg 		    "(ld_lock=%p)", lock, ld->ld_lock);
    353  1.8.6.2    joerg 		lockdebug_abort1(ld, lk, __func__, "lock record follows",
    354  1.8.6.2    joerg 		    true);
    355      1.2       ad 	}
    356      1.2       ad 	if ((ld->ld_flags & LD_LOCKED) != 0 || ld->ld_shares != 0)
    357  1.8.6.2    joerg 		lockdebug_abort1(ld, lk, __func__, "is locked", true);
    358  1.8.6.6    joerg 	lockdebug_lock(&ld_tree_lk);
    359  1.8.6.6    joerg 	rb_tree_remove_node(&ld_rb_tree, __UNVOLATILE(&ld->ld_rb_node));
    360  1.8.6.6    joerg 	lockdebug_unlock(&ld_tree_lk);
    361      1.2       ad 	ld->ld_lock = NULL;
    362      1.2       ad 	lockdebug_unlock(lk);
    363      1.2       ad 
    364      1.2       ad 	lockdebug_lock(&ld_free_lk);
    365      1.2       ad 	TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain);
    366      1.2       ad 	ld_nfree++;
    367      1.2       ad 	lockdebug_unlock(&ld_free_lk);
    368      1.2       ad }
    369      1.2       ad 
    370      1.2       ad /*
    371      1.2       ad  * lockdebug_more:
    372      1.2       ad  *
    373      1.2       ad  *	Allocate a batch of debug structures and add to the free list.
    374      1.2       ad  *	Must be called with ld_free_lk held.
    375      1.2       ad  */
    376      1.5       ad static void
    377      1.2       ad lockdebug_more(void)
    378      1.2       ad {
    379      1.2       ad 	lockdebug_t *ld;
    380      1.2       ad 	void *block;
    381      1.5       ad 	int i, base, m;
    382      1.2       ad 
    383      1.2       ad 	while (ld_nfree < LD_SLOP) {
    384      1.2       ad 		lockdebug_unlock(&ld_free_lk);
    385      1.2       ad 		block = kmem_zalloc(LD_BATCH * sizeof(lockdebug_t), KM_SLEEP);
    386      1.2       ad 		lockdebug_lock(&ld_free_lk);
    387      1.2       ad 
    388      1.2       ad 		if (block == NULL)
    389      1.2       ad 			return;
    390      1.2       ad 
    391      1.2       ad 		if (ld_nfree > LD_SLOP) {
    392      1.2       ad 			/* Somebody beat us to it. */
    393      1.2       ad 			lockdebug_unlock(&ld_free_lk);
    394      1.2       ad 			kmem_free(block, LD_BATCH * sizeof(lockdebug_t));
    395      1.2       ad 			lockdebug_lock(&ld_free_lk);
    396      1.2       ad 			continue;
    397      1.2       ad 		}
    398      1.2       ad 
    399      1.2       ad 		base = ld_freeptr;
    400      1.2       ad 		ld_nfree += LD_BATCH;
    401      1.2       ad 		ld = block;
    402      1.2       ad 		base <<= LD_BATCH_SHIFT;
    403      1.5       ad 		m = min(LD_MAX_LOCKS, base + LD_BATCH);
    404      1.5       ad 
    405      1.5       ad 		if (m == LD_MAX_LOCKS)
    406      1.5       ad 			ld_nomore = true;
    407      1.2       ad 
    408      1.5       ad 		for (i = base; i < m; i++, ld++) {
    409      1.2       ad 			TAILQ_INSERT_TAIL(&ld_free, ld, ld_chain);
    410      1.2       ad 			TAILQ_INSERT_TAIL(&ld_all, ld, ld_achain);
    411      1.2       ad 		}
    412      1.2       ad 
    413  1.8.6.8    joerg 		membar_producer();
    414      1.2       ad 		ld_table[ld_freeptr++] = block;
    415      1.2       ad 	}
    416      1.2       ad }
    417      1.2       ad 
    418      1.2       ad /*
    419      1.2       ad  * lockdebug_wantlock:
    420      1.2       ad  *
    421      1.2       ad  *	Process the preamble to a lock acquire.
    422      1.2       ad  */
    423      1.2       ad void
    424  1.8.6.6    joerg lockdebug_wantlock(volatile void *lock, uintptr_t where, int shared)
    425      1.2       ad {
    426      1.2       ad 	struct lwp *l = curlwp;
    427      1.2       ad 	lockdebuglk_t *lk;
    428      1.2       ad 	lockdebug_t *ld;
    429      1.3  thorpej 	bool recurse;
    430      1.2       ad 
    431      1.2       ad 	(void)shared;
    432      1.4  thorpej 	recurse = false;
    433      1.2       ad 
    434      1.2       ad 	if (panicstr != NULL)
    435      1.2       ad 		return;
    436      1.2       ad 
    437  1.8.6.6    joerg 	if ((ld = lockdebug_lookup(lock, &lk)) == NULL)
    438      1.2       ad 		return;
    439      1.2       ad 
    440      1.2       ad 	if ((ld->ld_flags & LD_LOCKED) != 0) {
    441      1.2       ad 		if ((ld->ld_flags & LD_SLEEPER) != 0) {
    442      1.2       ad 			if (ld->ld_lwp == l)
    443      1.4  thorpej 				recurse = true;
    444      1.2       ad 		} else if (ld->ld_cpu == (uint16_t)cpu_number())
    445      1.4  thorpej 			recurse = true;
    446      1.2       ad 	}
    447      1.2       ad 
    448  1.8.6.2    joerg #ifdef notyet
    449  1.8.6.2    joerg 	if (cpu_intr_p()) {
    450  1.8.6.2    joerg 		if ((ld->ld_flags & LD_SLEEPER) != 0)
    451  1.8.6.2    joerg 			lockdebug_abort1(ld, lk, __func__,
    452  1.8.6.2    joerg 			    "acquiring sleep lock from interrupt context",
    453  1.8.6.2    joerg 			    true);
    454  1.8.6.2    joerg 	}
    455  1.8.6.2    joerg #endif
    456  1.8.6.2    joerg 
    457      1.2       ad 	if (shared)
    458      1.2       ad 		ld->ld_shwant++;
    459      1.2       ad 	else
    460      1.2       ad 		ld->ld_exwant++;
    461      1.2       ad 
    462      1.2       ad 	if (recurse)
    463  1.8.6.2    joerg 		lockdebug_abort1(ld, lk, __func__, "locking against myself",
    464  1.8.6.2    joerg 		    true);
    465      1.2       ad 
    466      1.2       ad 	lockdebug_unlock(lk);
    467      1.2       ad }
    468      1.2       ad 
    469      1.2       ad /*
    470      1.2       ad  * lockdebug_locked:
    471      1.2       ad  *
    472      1.2       ad  *	Process a lock acquire operation.
    473      1.2       ad  */
    474      1.2       ad void
    475  1.8.6.6    joerg lockdebug_locked(volatile void *lock, uintptr_t where, int shared)
    476      1.2       ad {
    477      1.2       ad 	struct lwp *l = curlwp;
    478      1.2       ad 	lockdebuglk_t *lk;
    479      1.2       ad 	lockdebug_t *ld;
    480      1.2       ad 
    481      1.2       ad 	if (panicstr != NULL)
    482      1.2       ad 		return;
    483      1.2       ad 
    484  1.8.6.6    joerg 	if ((ld = lockdebug_lookup(lock, &lk)) == NULL)
    485      1.2       ad 		return;
    486      1.2       ad 
    487      1.2       ad 	if (shared) {
    488      1.2       ad 		l->l_shlocks++;
    489      1.2       ad 		ld->ld_shares++;
    490      1.2       ad 		ld->ld_shwant--;
    491      1.2       ad 	} else {
    492      1.2       ad 		if ((ld->ld_flags & LD_LOCKED) != 0)
    493      1.2       ad 			lockdebug_abort1(ld, lk, __func__,
    494  1.8.6.2    joerg 			    "already locked", true);
    495      1.2       ad 
    496      1.2       ad 		ld->ld_flags |= LD_LOCKED;
    497      1.2       ad 		ld->ld_locked = where;
    498      1.2       ad 		ld->ld_cpu = (uint16_t)cpu_number();
    499      1.2       ad 		ld->ld_lwp = l;
    500      1.2       ad 		ld->ld_exwant--;
    501      1.2       ad 
    502      1.2       ad 		if ((ld->ld_flags & LD_SLEEPER) != 0) {
    503      1.2       ad 			l->l_exlocks++;
    504      1.2       ad 			TAILQ_INSERT_TAIL(&ld_sleepers, ld, ld_chain);
    505      1.2       ad 		} else {
    506      1.2       ad 			curcpu()->ci_spin_locks2++;
    507      1.2       ad 			TAILQ_INSERT_TAIL(&ld_spinners, ld, ld_chain);
    508      1.2       ad 		}
    509      1.2       ad 	}
    510      1.2       ad 
    511      1.2       ad 	lockdebug_unlock(lk);
    512      1.2       ad }
    513      1.2       ad 
    514      1.2       ad /*
    515      1.2       ad  * lockdebug_unlocked:
    516      1.2       ad  *
    517      1.2       ad  *	Process a lock release operation.
    518      1.2       ad  */
    519      1.2       ad void
    520  1.8.6.6    joerg lockdebug_unlocked(volatile void *lock, uintptr_t where, int shared)
    521      1.2       ad {
    522      1.2       ad 	struct lwp *l = curlwp;
    523      1.2       ad 	lockdebuglk_t *lk;
    524      1.2       ad 	lockdebug_t *ld;
    525      1.2       ad 
    526      1.2       ad 	if (panicstr != NULL)
    527      1.2       ad 		return;
    528      1.2       ad 
    529  1.8.6.6    joerg 	if ((ld = lockdebug_lookup(lock, &lk)) == NULL)
    530      1.2       ad 		return;
    531      1.2       ad 
    532      1.2       ad 	if (shared) {
    533      1.2       ad 		if (l->l_shlocks == 0)
    534      1.2       ad 			lockdebug_abort1(ld, lk, __func__,
    535  1.8.6.2    joerg 			    "no shared locks held by LWP", true);
    536      1.2       ad 		if (ld->ld_shares == 0)
    537      1.2       ad 			lockdebug_abort1(ld, lk, __func__,
    538  1.8.6.2    joerg 			    "no shared holds on this lock", true);
    539      1.2       ad 		l->l_shlocks--;
    540      1.2       ad 		ld->ld_shares--;
    541      1.2       ad 	} else {
    542      1.2       ad 		if ((ld->ld_flags & LD_LOCKED) == 0)
    543  1.8.6.2    joerg 			lockdebug_abort1(ld, lk, __func__, "not locked",
    544  1.8.6.2    joerg 			    true);
    545      1.2       ad 
    546      1.2       ad 		if ((ld->ld_flags & LD_SLEEPER) != 0) {
    547      1.2       ad 			if (ld->ld_lwp != curlwp)
    548      1.2       ad 				lockdebug_abort1(ld, lk, __func__,
    549  1.8.6.2    joerg 				    "not held by current LWP", true);
    550      1.2       ad 			ld->ld_flags &= ~LD_LOCKED;
    551      1.2       ad 			ld->ld_unlocked = where;
    552      1.2       ad 			ld->ld_lwp = NULL;
    553      1.2       ad 			curlwp->l_exlocks--;
    554      1.2       ad 			TAILQ_REMOVE(&ld_sleepers, ld, ld_chain);
    555      1.2       ad 		} else {
    556      1.2       ad 			if (ld->ld_cpu != (uint16_t)cpu_number())
    557      1.2       ad 				lockdebug_abort1(ld, lk, __func__,
    558  1.8.6.2    joerg 				    "not held by current CPU", true);
    559      1.2       ad 			ld->ld_flags &= ~LD_LOCKED;
    560      1.2       ad 			ld->ld_unlocked = where;
    561      1.2       ad 			ld->ld_lwp = NULL;
    562      1.2       ad 			curcpu()->ci_spin_locks2--;
    563      1.2       ad 			TAILQ_REMOVE(&ld_spinners, ld, ld_chain);
    564      1.2       ad 		}
    565      1.2       ad 	}
    566      1.2       ad 
    567      1.2       ad 	lockdebug_unlock(lk);
    568      1.2       ad }
    569      1.2       ad 
    570      1.2       ad /*
    571      1.2       ad  * lockdebug_barrier:
    572      1.2       ad  *
    573      1.2       ad  *	Panic if we hold more than one specified spin lock, and optionally,
    574      1.2       ad  *	if we hold sleep locks.
    575      1.2       ad  */
    576      1.2       ad void
    577      1.2       ad lockdebug_barrier(volatile void *spinlock, int slplocks)
    578      1.2       ad {
    579      1.2       ad 	struct lwp *l = curlwp;
    580      1.2       ad 	lockdebug_t *ld;
    581      1.2       ad 	uint16_t cpuno;
    582      1.2       ad 
    583      1.2       ad 	if (panicstr != NULL)
    584      1.2       ad 		return;
    585      1.2       ad 
    586      1.2       ad 	if (curcpu()->ci_spin_locks2 != 0) {
    587      1.2       ad 		cpuno = (uint16_t)cpu_number();
    588      1.2       ad 
    589      1.2       ad 		lockdebug_lock(&ld_spinner_lk);
    590      1.2       ad 		TAILQ_FOREACH(ld, &ld_spinners, ld_chain) {
    591      1.2       ad 			if (ld->ld_lock == spinlock) {
    592      1.2       ad 				if (ld->ld_cpu != cpuno)
    593      1.2       ad 					lockdebug_abort1(ld, &ld_spinner_lk,
    594      1.2       ad 					    __func__,
    595  1.8.6.2    joerg 					    "not held by current CPU", true);
    596      1.2       ad 				continue;
    597      1.2       ad 			}
    598  1.8.6.4    joerg 			if (ld->ld_cpu == cpuno && (l->l_pflag & LP_INTR) == 0)
    599      1.2       ad 				lockdebug_abort1(ld, &ld_spinner_lk,
    600  1.8.6.2    joerg 				    __func__, "spin lock held", true);
    601      1.2       ad 		}
    602      1.2       ad 		lockdebug_unlock(&ld_spinner_lk);
    603      1.2       ad 	}
    604      1.2       ad 
    605      1.2       ad 	if (!slplocks) {
    606      1.2       ad 		if (l->l_exlocks != 0) {
    607      1.2       ad 			lockdebug_lock(&ld_sleeper_lk);
    608      1.2       ad 			TAILQ_FOREACH(ld, &ld_sleepers, ld_chain) {
    609      1.2       ad 				if (ld->ld_lwp == l)
    610      1.2       ad 					lockdebug_abort1(ld, &ld_sleeper_lk,
    611  1.8.6.2    joerg 					    __func__, "sleep lock held", true);
    612      1.2       ad 			}
    613      1.2       ad 			lockdebug_unlock(&ld_sleeper_lk);
    614      1.2       ad 		}
    615      1.2       ad 		if (l->l_shlocks != 0)
    616      1.2       ad 			panic("lockdebug_barrier: holding %d shared locks",
    617      1.2       ad 			    l->l_shlocks);
    618      1.2       ad 	}
    619      1.2       ad }
    620      1.2       ad 
    621      1.2       ad /*
    622  1.8.6.2    joerg  * lockdebug_mem_check:
    623  1.8.6.2    joerg  *
    624  1.8.6.2    joerg  *	Check for in-use locks within a memory region that is
    625  1.8.6.6    joerg  *	being freed.
    626  1.8.6.2    joerg  */
    627  1.8.6.2    joerg void
    628  1.8.6.2    joerg lockdebug_mem_check(const char *func, void *base, size_t sz)
    629  1.8.6.2    joerg {
    630  1.8.6.2    joerg 	lockdebug_t *ld;
    631  1.8.6.6    joerg 	lockdebuglk_t *lk;
    632  1.8.6.6    joerg 	uintptr_t lock;
    633  1.8.6.2    joerg 
    634  1.8.6.6    joerg 	lockdebug_lock(&ld_tree_lk);
    635  1.8.6.6    joerg 	ld = (lockdebug_t *)rb_tree_find_node_geq(&ld_rb_tree, base);
    636  1.8.6.6    joerg 	lockdebug_unlock(&ld_tree_lk);
    637  1.8.6.6    joerg 	if (ld == NULL)
    638  1.8.6.6    joerg 		return;
    639  1.8.6.6    joerg 
    640  1.8.6.6    joerg 	if ((ld->ld_flags & LD_SLEEPER) != 0)
    641  1.8.6.6    joerg 		lk = &ld_sleeper_lk;
    642  1.8.6.6    joerg 	else
    643  1.8.6.6    joerg 		lk = &ld_spinner_lk;
    644  1.8.6.2    joerg 
    645  1.8.6.6    joerg 	lockdebug_lock(lk);
    646  1.8.6.6    joerg 	lock = (uintptr_t)ld->ld_lock;
    647  1.8.6.7    joerg 	if ((uintptr_t)base > lock)
    648  1.8.6.7    joerg 		lockdebug_abort1(ld, lk, func, "corrupt tree", true);
    649  1.8.6.7    joerg 	if (lock < (uintptr_t)base + sz) {
    650  1.8.6.6    joerg 		lockdebug_abort1(ld, lk, func,
    651  1.8.6.6    joerg 		    "allocation contains active lock", !cold);
    652  1.8.6.6    joerg 		return;
    653  1.8.6.2    joerg 	}
    654  1.8.6.2    joerg 	lockdebug_unlock(lk);
    655  1.8.6.2    joerg }
    656  1.8.6.2    joerg 
    657  1.8.6.2    joerg /*
    658      1.2       ad  * lockdebug_dump:
    659      1.2       ad  *
    660      1.2       ad  *	Dump information about a lock on panic, or for DDB.
    661      1.2       ad  */
    662      1.2       ad static void
    663      1.2       ad lockdebug_dump(lockdebug_t *ld, void (*pr)(const char *, ...))
    664      1.2       ad {
    665      1.2       ad 	int sleeper = (ld->ld_flags & LD_SLEEPER);
    666      1.2       ad 
    667      1.2       ad 	(*pr)(
    668      1.2       ad 	    "lock address : %#018lx type     : %18s\n"
    669      1.2       ad 	    "shared holds : %18u exclusive: %18u\n"
    670      1.2       ad 	    "shares wanted: %18u exclusive: %18u\n"
    671      1.2       ad 	    "current cpu  : %18u last held: %18u\n"
    672      1.2       ad 	    "current lwp  : %#018lx last held: %#018lx\n"
    673  1.8.6.2    joerg 	    "last locked  : %#018lx unlocked : %#018lx\n"
    674  1.8.6.2    joerg 	    "initialized  : %#018lx\n",
    675      1.2       ad 	    (long)ld->ld_lock, (sleeper ? "sleep/adaptive" : "spin"),
    676      1.2       ad 	    (unsigned)ld->ld_shares, ((ld->ld_flags & LD_LOCKED) != 0),
    677      1.2       ad 	    (unsigned)ld->ld_shwant, (unsigned)ld->ld_exwant,
    678      1.2       ad 	    (unsigned)cpu_number(), (unsigned)ld->ld_cpu,
    679      1.2       ad 	    (long)curlwp, (long)ld->ld_lwp,
    680  1.8.6.2    joerg 	    (long)ld->ld_locked, (long)ld->ld_unlocked,
    681  1.8.6.2    joerg 	    (long)ld->ld_initaddr);
    682      1.2       ad 
    683      1.2       ad 	if (ld->ld_lockops->lo_dump != NULL)
    684      1.2       ad 		(*ld->ld_lockops->lo_dump)(ld->ld_lock);
    685      1.2       ad 
    686      1.2       ad 	if (sleeper) {
    687      1.2       ad 		(*pr)("\n");
    688      1.2       ad 		turnstile_print(ld->ld_lock, pr);
    689      1.2       ad 	}
    690      1.2       ad }
    691      1.2       ad 
    692      1.2       ad /*
    693      1.2       ad  * lockdebug_dump:
    694      1.2       ad  *
    695      1.2       ad  *	Dump information about a known lock.
    696      1.2       ad  */
    697      1.5       ad static void
    698      1.2       ad lockdebug_abort1(lockdebug_t *ld, lockdebuglk_t *lk, const char *func,
    699  1.8.6.2    joerg 		 const char *msg, bool dopanic)
    700      1.2       ad {
    701      1.2       ad 
    702      1.2       ad 	printf_nolog("%s error: %s: %s\n\n", ld->ld_lockops->lo_name,
    703      1.2       ad 	    func, msg);
    704      1.2       ad 	lockdebug_dump(ld, printf_nolog);
    705      1.2       ad 	lockdebug_unlock(lk);
    706      1.2       ad 	printf_nolog("\n");
    707  1.8.6.2    joerg 	if (dopanic)
    708  1.8.6.2    joerg 		panic("LOCKDEBUG");
    709      1.2       ad }
    710      1.2       ad 
    711      1.2       ad #endif	/* LOCKDEBUG */
    712      1.2       ad 
    713      1.2       ad /*
    714      1.2       ad  * lockdebug_lock_print:
    715      1.2       ad  *
    716      1.2       ad  *	Handle the DDB 'show lock' command.
    717      1.2       ad  */
    718      1.2       ad #ifdef DDB
    719      1.2       ad void
    720      1.2       ad lockdebug_lock_print(void *addr, void (*pr)(const char *, ...))
    721      1.2       ad {
    722      1.2       ad #ifdef LOCKDEBUG
    723      1.2       ad 	lockdebug_t *ld;
    724      1.2       ad 
    725      1.2       ad 	TAILQ_FOREACH(ld, &ld_all, ld_achain) {
    726      1.2       ad 		if (ld->ld_lock == addr) {
    727      1.2       ad 			lockdebug_dump(ld, pr);
    728      1.2       ad 			return;
    729      1.2       ad 		}
    730      1.2       ad 	}
    731      1.2       ad 	(*pr)("Sorry, no record of a lock with address %p found.\n", addr);
    732      1.2       ad #else
    733      1.2       ad 	(*pr)("Sorry, kernel not built with the LOCKDEBUG option.\n");
    734      1.2       ad #endif	/* LOCKDEBUG */
    735      1.2       ad }
    736      1.2       ad #endif	/* DDB */
    737      1.2       ad 
    738      1.2       ad /*
    739      1.2       ad  * lockdebug_abort:
    740      1.2       ad  *
    741      1.2       ad  *	An error has been trapped - dump lock info and call panic().
    742      1.2       ad  */
    743      1.2       ad void
    744  1.8.6.6    joerg lockdebug_abort(volatile void *lock, lockops_t *ops, const char *func,
    745  1.8.6.6    joerg 		const char *msg)
    746      1.2       ad {
    747      1.2       ad #ifdef LOCKDEBUG
    748      1.2       ad 	lockdebug_t *ld;
    749      1.2       ad 	lockdebuglk_t *lk;
    750      1.2       ad 
    751  1.8.6.6    joerg 	if ((ld = lockdebug_lookup(lock, &lk)) != NULL) {
    752  1.8.6.2    joerg 		lockdebug_abort1(ld, lk, func, msg, true);
    753      1.2       ad 		/* NOTREACHED */
    754      1.2       ad 	}
    755      1.2       ad #endif	/* LOCKDEBUG */
    756      1.2       ad 
    757      1.2       ad 	printf_nolog("%s error: %s: %s\n\n"
    758      1.2       ad 	    "lock address : %#018lx\n"
    759      1.2       ad 	    "current cpu  : %18d\n"
    760      1.2       ad 	    "current lwp  : %#018lx\n",
    761      1.2       ad 	    ops->lo_name, func, msg, (long)lock, (int)cpu_number(),
    762      1.2       ad 	    (long)curlwp);
    763      1.2       ad 
    764      1.2       ad 	(*ops->lo_dump)(lock);
    765      1.2       ad 
    766      1.2       ad 	printf_nolog("\n");
    767      1.2       ad 	panic("lock error");
    768      1.2       ad }
    769