/*
* 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 COPYRIGHT
* HOLDER 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"
#ifdef HAVE_TIME_H
#include <time.h>
#endif
#include "util/log.h"
#include "util/rbtree.h"
#include "util/locks.h"
#include "util/fptr_wlist.h"

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

/** keep track of lock id in lock-verify application
* Also defined in smallapp/worker_cb.c for fptr_wlist encapsulation
* breakage (the security tests break encapsulation for this test app) */
struct order_id {
       /** the thread id that created it */
       int thr;
       /** the instance number of creation */
       int instance;
};

/** a lock */
struct order_lock {
       /** rbnode in all tree */
       rbnode_type node;
       /** lock id */
       struct order_id id;
       /** the creation file */
       char* create_file;
       /** creation line */
       int create_line;
       /** set of all locks that are smaller than this one (locked earlier) */
       rbtree_type* smaller;
       /** during depthfirstsearch, this is a linked list of the stack
        * of locks. points to the next lock bigger than this one. */
       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 */
       int visited;
};

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

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

/** print program usage help */
static void
usage(void)
{
       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
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. */
#define STRMAX 1024
/** read a string from file, false on error */
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);
       if(!*str)
               fatal_exit("strdup failed: out of memory");
       return 1;
}

/** read creation entry */
static void read_create(rbtree_type* 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*
insert_lock(rbtree_type* 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 */
static void read_lock(rbtree_type* 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 */
static void readinput(rbtree_type* 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 */
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 */
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.
*/
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 */
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 */
static void check_order(rbtree_type* 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");
}

/** delete lock ref */
static void dellockref(rbnode_type* node, void* ATTR_UNUSED(arg))
{
       struct lock_ref* o = (struct lock_ref*)node;
       if(!o) return;
       free(o->file);
       free(o);
}

/** delete lock node */
static void delnode(rbnode_type* node, void* ATTR_UNUSED(arg))
{
       struct order_lock* o = (struct order_lock*)node;
       if(!o) return;
       free(o->create_file);
       if(o->smaller) {
               traverse_postorder(o->smaller, &dellockref, NULL);
               free(o->smaller);
       }
       free(o);
}

/** delete allocated memory */
static void locks_free(rbtree_type* all_locks)
{
       if(!all_locks)
               return;
       traverse_postorder(all_locks, &delnode, NULL);
       free(all_locks);
}

/** main program to verify all traces passed */
int
main(int argc, char* argv[])
{
       rbtree_type* all_locks;
       int i;
       time_t starttime = time(NULL);
#ifdef USE_THREAD_DEBUG
       /* do not overwrite the ublocktrace files with the ones generated
        * by this program (i.e. when the log code creates a lock) */
       check_locking_order = 0;
#endif
       if(argc <= 1) {
               usage();
               return 1;
       }
       checklock_start();
       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);
       locks_free(all_locks);
       if(errors_detected) return 1;
       return 0;
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.