1 #include <linux/kernel.h>
2 #include <linux/kthread.h>
3 #include <linux/spinlock.h>
10 // Number of outputs possible before output stops
11 // set to zero to remove the limit
12 #define OUTPUT_LIMIT 0
14 // Number of outputs to skip before
15 // printing and counting
19 // Whether or not to print these events
21 #define PRINT_LOCK_ALLOC 0
22 #define PRINT_LOCK_FREE 0
23 #define PRINT_LOCK_LOCK 0
24 #define PRINT_LOCK_UNLOCK 0
26 // How far up the stack to track the caller
29 // 2 => caller of v3_lock..
31 #define STEP_BACK_DEPTH_FIRST 1
32 #define STEP_BACK_DEPTH_LAST 4
33 #define STEP_BACK_DEPTH (STEP_BACK_DEPTH_LAST-STEP_BACK_DEPTH_FIRST+1)
35 // show when multiple locks are held simultaneously
36 // This is the minimum number
37 #define WARN_MULTIPLE_THRESHOLD 3
39 // Detect when last lock a processor holds is released
40 // but interrupts remain off, similarly for first acquire
41 #define CHECK_IRQ_LAST_RELEASE 0
42 #define CHECK_IRQ_FIRST_ACQUIRE 1
45 // Whether lockcheck should lock its own data structures during an
46 // event (alloc, dealloc, lock, unlock, etc) and the subsequent
47 // checking. If this is off, it will only lock on a lock allocation,
48 // in order to assure each lock has a distinct slot. If this is off,
49 // lockcheck may miss problems (or see additional problems) due to
50 // internal race conditions. However, if it is on, lockcheck is
51 // essentially adding a global lock acuire to each lock operation in
52 // palacios, which will perturb palacios.
58 int inuse; // nonzero if this is in use
59 void *lock; // the lock
60 void *holder; // current thread holding it
61 u32 holdingcpu; // on which cpu it acquired it
62 void *allocator[STEP_BACK_DEPTH];
64 int lockcount; // how many times it's been locked/unlocked (lock=+1, unlock=-1)
65 int irqcount; // how many times interrupts have been turned off (+1/-1)
66 void *lastlocker[STEP_BACK_DEPTH];
68 void *lastunlocker[STEP_BACK_DEPTH];
70 void *lastirqlocker[STEP_BACK_DEPTH];
72 unsigned long lastlockflags; // their flags
73 void *lastirqunlocker[STEP_BACK_DEPTH]
74 ; // who last unlocked
75 unsigned long lastunlockflags; // their flags
79 // This lock is currently used only to control
80 // allocation of entries in the global state
81 static spinlock_t mylock;
82 static lockcheck_state_t state[NUM_LOCKS];
86 #define DEBUG_OUTPUT(fmt, args...) \
89 if (numout>=OUTPUT_SKIP) { \
90 if (OUTPUT_LIMIT==0 ||(numout-OUTPUT_SKIP)<OUTPUT_LIMIT) { \
93 if ((numout-OUTPUT_SKIP)==OUTPUT_LIMIT) { \
94 DEBUG("LOCKCHECK: Output limit hit - no further printouts\n"); \
100 #define DEBUG_DUMPSTACK() \
102 if (numout>=OUTPUT_SKIP) { \
103 if (OUTPUT_LIMIT==0 || (numout-OUTPUT_SKIP)<OUTPUT_LIMIT) { \
110 #define LOCK_DECL unsigned long f
111 #define LOCK() spin_lock_irqsave(&mylock,f)
112 #define UNLOCK() spin_unlock_irqrestore(&mylock,f)
113 #define LOCK_ALLOC_DECL
115 #define UNLOCK_ALLOC()
120 #define LOCK_ALLOC_DECL unsigned long f
121 #define LOCK_ALLOC() spin_lock_irqsave(&mylock,f)
122 #define UNLOCK_ALLOC() spin_unlock_irqrestore(&mylock,f)
125 static void printlock(char *prefix, lockcheck_state_t *l);
129 u32 top; // next open slot 0..
130 void *lock[LOCK_STACK_DEPTH]; // the stack
131 char irq[LOCK_STACK_DEPTH]; // locked with irqsave?
132 char irqoff[LOCK_STACK_DEPTH]; // if so, what was the flag?
135 static DEFINE_PER_CPU(lock_stack_t, lock_stack);
137 static lockcheck_state_t *get_lock_entry(void)
140 lockcheck_state_t *l;
144 for (i=0;i<NUM_LOCKS;i++) {
161 static lockcheck_state_t *find_lock_entry(void *lock)
164 lockcheck_state_t *l;
166 for (i=0;i<NUM_LOCKS;i++) {
168 if (l->inuse && l->lock == lock) {
176 static void free_lock_entry(lockcheck_state_t *l)
182 static void lock_stack_print(void)
186 lock_stack_t *mystack = &(get_cpu_var(lock_stack));
187 u32 cpu = get_cpu(); put_cpu();
189 if ((mystack->top)>0) {
190 for (i=mystack->top; i>0;i--) {
191 snprintf(buf,64,"LOCK STACK (cpu=%u, index=%u, irq=%d, irqoff=%d)",cpu, i-1, (int)(mystack->irq[i-1]), (int)(mystack->irqoff[i-1]));
192 printlock(buf,find_lock_entry(mystack->lock[i-1]));
195 put_cpu_var(lock_stack);
199 static void lock_stack_lock(void *lock, char irq, unsigned long flags)
201 lock_stack_t *mystack = &(get_cpu_var(lock_stack));
202 u32 cpu = get_cpu(); put_cpu();
204 if (mystack->top>=(LOCK_STACK_DEPTH-1)) {
205 put_cpu_var(lock_stack);
206 DEBUG_OUTPUT("LOCKCHECK: Locking lock 0x%p on cpu %u exceeds stack limit of %d\n",lock,cpu,LOCK_STACK_DEPTH);
209 int oldtop = mystack->top;
210 mystack->lock[mystack->top] = lock;
211 mystack->irq[mystack->top] = irq;
212 mystack->irqoff[mystack->top] = irqs_disabled_flags(flags);
214 put_cpu_var(lock_stack);
215 if (CHECK_IRQ_FIRST_ACQUIRE && oldtop==0 && irqs_disabled_flags(flags) ) {
216 DEBUG_OUTPUT("LOCKCHECK: First lock on lock stack of processor %d but irqs were already disabled - stack trace follows\n", cpu);
225 static void lock_stack_unlock(void *lock, char irq, unsigned long flags)
227 lock_stack_t *mystack = &(get_cpu_var(lock_stack));
228 u32 cpu = get_cpu(); put_cpu();
230 if (mystack->top==0) {
231 put_cpu_var(lock_stack);
232 DEBUG_OUTPUT("LOCKCHECK: Unlocking lock 0x%p on cpu %u when lock stack is empty\n",lock,cpu);
234 if (mystack->lock[mystack->top-1] != lock) {
235 void *otherlock=mystack->lock[mystack->top-1];
236 put_cpu_var(lock_stack);
237 DEBUG_OUTPUT("LOCKCHECK: Unlocking lock 0x%p on cpu %u when top of stack is lock 0x%p\n",lock,cpu, otherlock);
240 if (irq!=mystack->irq[mystack->top-1]) {
241 char otherirq = mystack->irq[mystack->top-1];
242 put_cpu_var(lock_stack);
243 DEBUG_OUTPUT("LOCKCHECK: Unlocking lock 0x%p on cpu %u with irq=%d, but was locked with irq=%d\n",lock,cpu,irq,otherirq);
245 mystack = &(get_cpu_var(lock_stack));
247 put_cpu_var(lock_stack);
250 if (irqs_disabled_flags(flags)!=mystack->irqoff[mystack->top-1]) {
251 char otherirqoff = mystack->irqoff[mystack->top-1];
252 put_cpu_var(lock_stack);
253 DEBUG_OUTPUT("LOCKCHECK: Unlocking lock 0x%p on cpu %u sets irqoff=%d but the matching lock returned irqoff=%d\n", lock, cpu, irqs_disabled_flags(flags), otherirqoff);
255 mystack = &(get_cpu_var(lock_stack));
257 put_cpu_var(lock_stack);
259 // irq, and irq states match - good
261 put_cpu_var(lock_stack);
264 // !irq - we are good
266 put_cpu_var(lock_stack);
272 mystack = &(get_cpu_var(lock_stack));
273 if (mystack->top == 0) {
274 put_cpu_var(lock_stack);
275 if (CHECK_IRQ_LAST_RELEASE && irqs_disabled()) {
276 DEBUG_OUTPUT("LOCKCHECK: Lock stack on cpu %u is now empty, but irqs are still disabled! Stack trace follows\n", cpu);
280 put_cpu_var(lock_stack);
285 void palacios_lockcheck_init()
287 memset(state,0,sizeof(lockcheck_state_t)*NUM_LOCKS);
288 spin_lock_init(&mylock);
289 DEBUG_OUTPUT("LOCKCHECK: LOCK CHECKING INITED (internal locking: %d, output limit: %d, output skip: %d)\n",LOCK_SELF,OUTPUT_LIMIT,OUTPUT_SKIP);
293 // This needs to be defined explictly since the intrinsic does not take a var
295 #define backtrace(t) \
296 t[0]=__builtin_return_address(STEP_BACK_DEPTH_FIRST); \
297 t[1]=__builtin_return_address(STEP_BACK_DEPTH_FIRST+1); \
298 t[2]=__builtin_return_address(STEP_BACK_DEPTH_FIRST+2); \
299 t[3]=__builtin_return_address(STEP_BACK_DEPTH_FIRST+3);
302 // For printing a backtrace
305 #define backtrace_format "%pS << %pS << %pS << %pS"
306 #define backtrace_expand(t) ((t)[0]),((t)[1]),((t)[2]),((t)[3])
309 static void clear_trace(void **trace)
313 for (i=0;i<STEP_BACK_DEPTH;i++) {
319 static void printlock(char *prefix, lockcheck_state_t *l)
321 if (!l || !(l->lock) ) {
322 DEBUG_OUTPUT("LOCKCHECK: %s: lock 0x%p BOGUS\n",prefix,l);
326 DEBUG_OUTPUT("LOCKCHECK: %s: lock 0x%p, holder %s on %u, allocator="
328 ", lockcount=%d, lastlocker="
332 ", irqcount=%d, lastirqlocker="
334 ", lastlockflags=%lu, lastirqunlocker="
336 ", lastunlockflags=%lu\n",
338 l->holder ? ((struct task_struct *)(l->holder))->comm : "none",
340 backtrace_expand(l->allocator),
342 backtrace_expand(l->lastlocker),
343 backtrace_expand(l->lastunlocker),
345 backtrace_expand(l->lastirqlocker),
347 backtrace_expand(l->lastirqunlocker),
354 static void find_multiple_locks_held(void)
358 lockcheck_state_t *l;
361 for (i=0;i<NUM_LOCKS;i++) {
363 if (l->inuse && l->lockcount>0) {
365 if (have>=WARN_MULTIPLE_THRESHOLD) {
371 if (have>=WARN_MULTIPLE_THRESHOLD) {
373 for (i=0;i<NUM_LOCKS;i++) {
375 if (l->inuse && l->lockcount>0) {
376 snprintf(buf,64,"MULTIPLE LOCKS HELD (%d)",have);
385 static void find_multiple_irqs_held(void)
389 lockcheck_state_t *l;
392 for (i=0;i<NUM_LOCKS;i++) {
394 if (l->inuse && l->irqcount>0) {
396 if (have>=WARN_MULTIPLE_THRESHOLD) {
402 if (have>=WARN_MULTIPLE_THRESHOLD) {
404 for (i=0;i<NUM_LOCKS;i++) {
406 if (l->inuse && l->irqcount>0) {
407 snprintf(buf,64,"MULTIPLE IRQS HELD (%d)",have);
417 void palacios_lockcheck_deinit()
420 lockcheck_state_t *l;
425 for (i=0;i<NUM_LOCKS;i++) {
428 printlock("ALLOCATED LOCK AT DEINIT",l);
429 if ((l->lockcount)) {
430 printlock("BAD LOCK COUNT AT DEINIT",l);
433 printlock("BAD IRQ COUNT AT DEINIT",l);
438 INFO("LOCKCHECK: DEINITED\n");
442 void palacios_lockcheck_alloc(void *lock)
444 lockcheck_state_t *l;
452 DEBUG_OUTPUT("LOCKCHECK: UNABLE TO ALLOCATE TRACKING DATA FOR LOCK 0x%p\n",lock);
455 backtrace(l->allocator);
456 l->lockcount=l->irqcount=0;
457 clear_trace(l->lastlocker);
458 clear_trace(l->lastunlocker);
459 clear_trace(l->lastirqlocker);
460 clear_trace(l->lastirqunlocker);
461 //INFO("LOCKCHECK: LOCK ALLOCATE 0x%p\n",lock);
463 printlock("NEW LOCK", l);
469 void palacios_lockcheck_free(void *lock)
471 lockcheck_state_t *l;
475 l=find_lock_entry(lock);
479 DEBUG_OUTPUT("LOCKCHECK: FREEING UNTRACKED LOCK 0x%p - stack trace follows\n",lock);
484 if ((l->lockcount)) {
485 printlock("BAD LOCK COUNT AT FREE",l);
489 printlock("BAD IRQ COUNT AT FREE",l);
493 printlock("FREE LOCK",l);
502 void palacios_lockcheck_lock(void *lock)
505 lockcheck_state_t *l;
510 l=find_lock_entry(lock);
514 DEBUG_OUTPUT("LOCKCHECK: LOCKING UNTRACKED LOCK 0x%p - stack follows\n",lock);
519 if (l->lockcount!=0) {
520 printlock("BAD LOCKCOUNT AT LOCK - stack follows",l);
523 if (l->irqcount!=0) {
524 printlock("BAD IRQCOUNT AT LOCK - stack follows",l);
530 l->holdingcpu=get_cpu(); put_cpu();
531 backtrace(l->lastlocker);
533 find_multiple_locks_held();
535 lock_stack_lock(lock,0,0);
544 void palacios_lockcheck_unlock(void *lock)
547 lockcheck_state_t *l;
551 l=find_lock_entry(lock);
555 DEBUG_OUTPUT("LOCKCHECK: UNLOCKING UNTRACKED LOCK 0x%p - stack follows\n",lock);
560 if (l->lockcount!=1) {
561 printlock("LOCKCHECK: BAD LOCKCOUNT AT UNLOCK - stack follows",l);
564 if (l->irqcount!=0) {
565 printlock("LOCKCHECK: BAD IRQCOUNT AT UNLOCK - stack follows",l);
569 lock_stack_unlock(lock,0,0);
574 backtrace(l->lastunlocker);
576 #if PRINT_LOCK_UNLOCK
577 printlock("UNLOCK",l);
584 void palacios_lockcheck_lock_irqsave(void *lock,unsigned long flags)
587 lockcheck_state_t *l;
591 l=find_lock_entry(lock);
595 DEBUG_OUTPUT("LOCKCHECK: IRQ LOCKING UNTRACKED LOCK 0x%p - stack follows\n",lock);
600 if (l->lockcount!=0) {
601 printlock("BAD LOCKCOUNT AT IRQ LOCK - stack follows",l);
604 if (l->irqcount!=0) {
605 printlock("BAD IRQCOUNT AT IRQ LOCK - stack follows",l);
611 l->holdingcpu=get_cpu(); put_cpu();
612 l->lastlockflags=flags;
613 backtrace(l->lastirqlocker);
615 find_multiple_irqs_held();
617 lock_stack_lock(lock,1,flags);
620 printlock("LOCK_IRQSAVE",l);
630 // This is separated into two components to avoid a race between
631 // the underlying spin_unlock_irqrestore and the next lockcheck_lock_irqsave
632 // If simply record the state after the unlock, we might see that the
633 // irqcount has already increased. Therefore, we will acquire the
634 // lockchecker lock in _pre and release it in _post. Note that when
635 // we release the lock in _post, we restore the flags provided by the
636 // code under test - NOT our original flags
638 // unlock_pre() - stores flags, takes mylock discard flags
639 // At this point, a lockcheck_lock cannot enter, since it's stuck on mylock
640 // spinunlock - restores lock, restores original flags
641 // unlock_post() - restores mylock WITH orig flags
643 void palacios_lockcheck_unlock_irqrestore_pre(void *lock,unsigned long flags)
647 LOCK(); // flags are discarded
648 // at this point, the actual spin unlock can run
649 // if another thread hits lockcheck_irqsave at this point, it
650 // will block on mylock
653 void palacios_lockcheck_unlock_irqrestore_post(void *lock,unsigned long flags)
656 lockcheck_state_t *l;
659 // when we unlock, want to restore the flags *the user wants*
663 // Note that we DO NOT take mylock here, since we already took it in
666 l=find_lock_entry(lock);
669 UNLOCK(); // release any waiting threads on lockcheck_lock_irqsave
670 DEBUG_OUTPUT("LOCKCHECK: IRQ UNLOCKING UNTRACKED LOCK 0x%p - stack follows\n",lock);
675 if (l->lockcount!=0) {
676 printlock("LOCKCHECK: BAD LOCKCOUNT AT IRQ UNLOCK - stack follows",l);
679 if (l->irqcount!=1) {
680 printlock("LOCKCHECK: BAD IRQCOUNT AT IRQ UNLOCK - stack follows",l);
687 l->lastunlockflags = flags;
689 lock_stack_unlock(lock,1,flags);
691 backtrace(l->lastirqunlocker);
693 #if PRINT_LOCK_UNLOCK
694 printlock("UNLOCK_IRQRESTORE",l);
696 UNLOCK(); // release any waiting threads on lockcheck_lock_irqsave