Logo Search packages:      
Sourcecode: unbound version File versions  Download package

lock_verify.c

Go to the documentation of this file.
/*
 * testcode/lock_verify.c - verifier program for lock traces, checks order.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file checks the lock traces generated by checklock.c.
 * Checks if locks are consistently locked in the same order.
 * If not, this can lead to deadlock if threads execute the different
 * ordering at the same time.
 * 
 */

#include "config.h"
#include "util/log.h"
#include "util/rbtree.h"
#include "util/locks.h"
#include "testcode/checklocks.h"

/* --- data structures --- */
struct lock_ref;

/** a lock */
00056 struct order_lock {
      /** rbnode in all tree */
00058       rbnode_t node;
      /** lock id */
00060       struct order_id id;
      /** the creation file */
00062       char* create_file;
      /** creation line */
00064       int create_line;
      /** set of all locks that are smaller than this one (locked earlier) */
00066       rbtree_t* smaller;
      /** during depthfirstsearch, this is a linked list of the stack 
       * of locks. points to the next lock bigger than this one. */
00069       struct lock_ref* dfs_next;
      /** if lock has been visited (all smaller locks have been compared to
       * this lock), only need to compare this with all unvisited(bigger) 
       * locks */
00073       int visited;
};

/** reference to a lock in a rbtree set */
00077 struct lock_ref {
      /** rbnode, key is an order_id ptr */
00079       rbnode_t node;
      /** the lock referenced */
00081       struct order_lock* lock;
      /** why is this ref */
00083       char* file;
      /** line number */
00085       int line;
};

/** count of errors detected */
00089 static int errors_detected = 0;
/** verbose? */
00091 static int verb = 0;

/** print program usage help */
static void
00095 usage()
{
      printf("lock_verify <trace files>\n");
}

/** read header entry. 
 * @param in: file to read header of.
 * @return: False if it does not belong to the rest. */
static int 
00104 read_header(FILE* in)
{
      time_t t;
      pid_t p;
      int thrno;
      static int have_values = 0;
      static time_t the_time;
      static pid_t the_pid;
      static int threads[256];

      if(fread(&t, sizeof(t), 1, in) != 1 ||    
            fread(&thrno, sizeof(thrno), 1, in) != 1 ||
            fread(&p, sizeof(p), 1, in) != 1) {
            fatal_exit("fread failed");
      }
      /* check these values are sorta OK */
      if(!have_values) {
            the_time = t;
            the_pid = p;
            memset(threads, 0, 256*sizeof(int));
            if(thrno >= 256) {
                  fatal_exit("Thread number too big. %d", thrno);
            }
            threads[thrno] = 1;
            have_values = 1;
            printf(" trace %d from pid %u on %s", thrno, 
                  (unsigned)p, ctime(&t));
      } else {
            if(the_pid != p) {
                  printf(" has pid %u, not %u. Skipped.\n",
                        (unsigned)p, (unsigned)the_pid);
                  return 0;
            }
            if(threads[thrno])
                  fatal_exit("same threadno in two files");
            threads[thrno] = 1;
            if( abs((int)(the_time - t)) > 3600)
                  fatal_exit("input files from different times: %u %u",
                        (unsigned)the_time, (unsigned)t);
            printf(" trace of thread %u:%d\n", (unsigned)p, thrno);
      }
      return 1;
}

/** max length of strings: filenames and function names. */
00149 #define STRMAX 1024
/** read a string from file, false on error */
00151 static int readup_str(char** str, FILE* in)
{
      char buf[STRMAX];
      int len = 0;
      int c;
      /* ends in zero */
      while( (c = fgetc(in)) != 0) {
            if(c == EOF)
                  fatal_exit("eof in readstr, file too short");
            buf[len++] = c;
            if(len == STRMAX) {
                  fatal_exit("string too long, bad file format");
            }
      }
      buf[len] = 0;
      *str = strdup(buf);
      return 1;
}

/** read creation entry */
00171 static void read_create(rbtree_t* all, FILE* in)
{
      struct order_lock* o = calloc(1, sizeof(struct order_lock));
      if(!o) fatal_exit("malloc failure");
      if(fread(&o->id.thr, sizeof(int), 1, in) != 1 ||      
         fread(&o->id.instance, sizeof(int), 1, in) != 1 || 
         !readup_str(&o->create_file, in) ||
         fread(&o->create_line, sizeof(int), 1, in) != 1)
            fatal_exit("fread failed");
      o->smaller = rbtree_create(order_lock_cmp);
      o->node.key = &o->id;
      if(!rbtree_insert(all, &o->node)) {
            /* already inserted */
            struct order_lock* a = (struct order_lock*)rbtree_search(all, 
                  &o->id);
            log_assert(a);
            a->create_file = o->create_file;
            a->create_line = o->create_line;
            free(o->smaller);
            free(o);
            o = a;
      }
      if(verb) printf("read create %u %u %s %d\n", 
            (unsigned)o->id.thr, (unsigned)o->id.instance,
            o->create_file, o->create_line);
}

/** insert lock entry (empty) into list */
static struct order_lock* 
00200 insert_lock(rbtree_t* all, struct order_id* id)
{
      struct order_lock* o = calloc(1, sizeof(struct order_lock));
      if(!o) fatal_exit("malloc failure");
      o->smaller = rbtree_create(order_lock_cmp);
      o->id = *id;
      o->node.key = &o->id;
      if(!rbtree_insert(all, &o->node))
            fatal_exit("insert fail should not happen");
      return o;
}

/** read lock entry */
00213 static void read_lock(rbtree_t* all, FILE* in, int val)
{
      struct order_id prev_id, now_id;
      struct lock_ref* ref;
      struct order_lock* prev, *now;
      ref = (struct lock_ref*)calloc(1, sizeof(struct lock_ref));
      if(!ref) fatal_exit("malloc failure");
      prev_id.thr = val;
      if(fread(&prev_id.instance, sizeof(int), 1, in) != 1 ||     
         fread(&now_id.thr, sizeof(int), 1, in) != 1 ||     
         fread(&now_id.instance, sizeof(int), 1, in) != 1 ||      
         !readup_str(&ref->file, in) ||
         fread(&ref->line, sizeof(int), 1, in) != 1)
            fatal_exit("fread failed");
      if(verb) printf("read lock %u %u %u %u %s %d\n", 
            (unsigned)prev_id.thr, (unsigned)prev_id.instance,
            (unsigned)now_id.thr, (unsigned)now_id.instance,
            ref->file, ref->line);
      /* find the two locks involved */
      prev = (struct order_lock*)rbtree_search(all, &prev_id);
      now = (struct order_lock*)rbtree_search(all, &now_id);
      /* if not there - insert 'em */
      if(!prev) prev = insert_lock(all, &prev_id);
      if(!now) now = insert_lock(all, &now_id);
      ref->lock = prev;
      ref->node.key = &prev->id;
      if(!rbtree_insert(now->smaller, &ref->node)) {
            free(ref->file);
            free(ref);
      }
}

/** read input file */
00246 static void readinput(rbtree_t* all, char* file)
{
      FILE *in = fopen(file, "r");
      int fst;
      if(!in) {
            perror(file);
            exit(1);
      }
      printf("file %s", file);
      if(!read_header(in)) {
            fclose(in);
            return;
      }
      while(fread(&fst, sizeof(fst), 1, in) == 1) {
            if(fst == -1)
                  read_create(all, in);
            else  read_lock(all, in, fst);
      }
      fclose(in);
}

/** print cycle message */
00268 static void found_cycle(struct lock_ref* visit, int level)
{
      struct lock_ref* p;
      int i = 0;
      errors_detected++;
      printf("Found inconsistent locking order of length %d\n", level);
      printf("for lock %d %d created %s %d\n", 
            visit->lock->id.thr, visit->lock->id.instance,
            visit->lock->create_file, visit->lock->create_line);
      printf("sequence is:\n");
      p = visit;
      while(p) {
            struct order_lock* next = 
                  p->lock->dfs_next?p->lock->dfs_next->lock:visit->lock;
            printf("[%d] is locked at line %s %d before lock %d %d\n",
                  i, p->file, p->line, next->id.thr, next->id.instance);
            printf("[%d] lock %d %d is created at %s %d\n",
                  i, next->id.thr, next->id.instance,
                  next->create_file, next->create_line); 
            i++;
            p = p->lock->dfs_next;
            if(p && p->lock == visit->lock)
                  break;
      }
}

/** Detect cycle by comparing visited now with all (unvisited) bigger nodes */
00295 static int detect_cycle(struct lock_ref* visit, struct lock_ref* from)
{
      struct lock_ref* p = from;
      while(p) {
            if(p->lock == visit->lock)
                  return 1;
            p = p->lock->dfs_next;
      }
      return 0;
}

/** recursive function to depth first search for cycles.
 * @param visit: the lock visited at this step.
 *    its dfs_next pointer gives the visited lock up in recursion.
 *    same as lookfor at level 0.
 * @param level: depth of recursion. 0 is start.
 * @param from: search for matches from unvisited node upwards.
 */
00313 static void search_cycle(struct lock_ref* visit, int level, 
      struct lock_ref* from)
{
      struct lock_ref* ref;
      /* check for cycle */
      if(detect_cycle(visit, from) && level != 0) {
            found_cycle(visit, level);
            fatal_exit("found lock order cycle");
      }
      /* recurse */
      if(!visit->lock->visited)
            from = visit;
      if(verb > 1) fprintf(stderr, "[%d] visit lock %u %u %s %d\n", level,
                  (unsigned)visit->lock->id.thr, 
                  (unsigned)visit->lock->id.instance,
                  visit->lock->create_file, visit->lock->create_line);
      RBTREE_FOR(ref, struct lock_ref*, visit->lock->smaller) {
            ref->lock->dfs_next = visit;
            search_cycle(ref, level+1, from);
      }
      visit->lock->visited = 1;
}

/** Check ordering of one lock */
00337 static void check_order_lock(struct order_lock* lock)
{
      struct lock_ref start;
      if(lock->visited) return;

      start.node.key = &lock->id;
      start.lock = lock;
      start.file = lock->create_file;
      start.line = lock->create_line;

      if(!lock->create_file)
            log_err("lock %u %u does not have create info",
                  (unsigned)lock->id.thr, (unsigned)lock->id.instance);

      /* depth first search to find cycle with this lock at head */
      lock->dfs_next = NULL;
      search_cycle(&start, 0, &start);
}

/** Check ordering of locks */
00357 static void check_order(rbtree_t* all_locks)
{
      /* check each lock */
      struct order_lock* lock;
      int i=0;
      RBTREE_FOR(lock, struct order_lock*, all_locks) {
            if(verb)
                printf("[%d/%d] Checking lock %d %d %s %d\n",
                  i, (int)all_locks->count,
                  lock->id.thr, lock->id.instance, 
                  lock->create_file, lock->create_line);
            else if (i % ((all_locks->count/75)<1?1:all_locks->count/75) 
                  == 0) 
                fprintf(stderr, ".");
            i++;
            check_order_lock(lock);
      }
      fprintf(stderr, "\n");
}

/** main program to verify all traces passed */
int
00379 main(int argc, char* argv[])
{
      rbtree_t* all_locks;
      int i;
      time_t starttime = time(NULL);
      if(argc <= 1) {
            usage();
            return 1;
      }
      log_init(NULL, 0, NULL);
      log_ident_set("lock-verify");
      /* init */
      all_locks = rbtree_create(order_lock_cmp);
      errors_detected = 0;

      /* read the input files */
      for(i=1; i<argc; i++) {
            readinput(all_locks, argv[i]);
      }

      /* check ordering */
      check_order(all_locks);

      /* do not free a thing, OS will do it */
      printf("checked %d locks in %d seconds with %d errors.\n", 
            (int)all_locks->count, (int)(time(NULL)-starttime),
            errors_detected);
      if(errors_detected) return 1;
      return 0;
}

Generated by  Doxygen 1.6.0   Back to index