testcode/lock_verify.c

   1 /*
   2  * testcode/lock_verify.c - verifier program for lock traces, checks order.
   3  *
   4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * This file checks the lock traces generated by checklock.c.
  40  * Checks if locks are consistently locked in the same order.
  41  * If not, this can lead to deadlock if threads execute the different
  42  * ordering at the same time.
  43  *
  44  */
  45
  46 #include "config.h"
  47 #include "util/log.h"
  48 #include "util/rbtree.h"
  49 #include "util/locks.h"
  50 #include "util/fptr_wlist.h"
  51
  52 /* --- data structures --- */
  53 struct lock_ref;
  54
  55 /** keep track of lock id in lock-verify application
  56  * Also defined in smallapp/worker_cb.c for fptr_wlist encapsulation
  57  * breakage (the security tests break encapsulation for this test app) */
  58 struct order_id {
  59         /** the thread id that created it */
  60         int thr;
  61         /** the instance number of creation */
  62         int instance;
  63 };
  64
  65 /** a lock */
  66 struct order_lock {
  67         /** rbnode in all tree */
  68         rbnode_t node;
  69         /** lock id */
  70         struct order_id id;
  71         /** the creation file */
  72         char* create_file;
  73         /** creation line */
  74         int create_line;
  75         /** set of all locks that are smaller than this one (locked earlier) */
  76         rbtree_t* smaller;
  77         /** during depthfirstsearch, this is a linked list of the stack
  78          * of locks. points to the next lock bigger than this one. */
  79         struct lock_ref* dfs_next;
  80         /** if lock has been visited (all smaller locks have been compared to
  81          * this lock), only need to compare this with all unvisited(bigger)
  82          * locks */
  83         int visited;
  84 };
  85
  86 /** reference to a lock in a rbtree set */
  87 struct lock_ref {
  88         /** rbnode, key is an order_id ptr */
  89         rbnode_t node;
  90         /** the lock referenced */
  91         struct order_lock* lock;
  92         /** why is this ref */
  93         char* file;
  94         /** line number */
  95         int line;
  96 };
  97
  98 /** count of errors detected */
  99 static int errors_detected = 0;
 100 /** verbose? */
 101 static int verb = 0;
 102
 103 /** print program usage help */
 104 static void
 105 usage()
 106 {
 107         printf("lock_verify <trace files>\n");
 108 }
 109
 110 /** read header entry.
 111  * @param in: file to read header of.
 112  * @return: False if it does not belong to the rest. */
 113 static int
 114 read_header(FILE* in)
 115 {
 116         time_t t;
 117         pid_t p;
 118         int thrno;
 119         static int have_values = 0;
 120         static time_t the_time;
 121         static pid_t the_pid;
 122         static int threads[256];
 123
 124         if(fread(&t, sizeof(t), 1, in) != 1 ||
 125                 fread(&thrno, sizeof(thrno), 1, in) != 1 ||
 126                 fread(&p, sizeof(p), 1, in) != 1) {
 127                 fatal_exit("fread failed");
 128         }
 129         /* check these values are sorta OK */
 130         if(!have_values) {
 131                 the_time = t;
 132                 the_pid = p;
 133                 memset(threads, 0, 256*sizeof(int));
 134                 if(thrno >= 256) {
 135                         fatal_exit("Thread number too big. %d", thrno);
 136                 }
 137                 threads[thrno] = 1;
 138                 have_values = 1;
 139                 printf(" trace %d from pid %u on %s", thrno,
 140                         (unsigned)p, ctime(&t));
 141         } else {
 142                 if(the_pid != p) {
 143                         printf(" has pid %u, not %u. Skipped.\n",
 144                                 (unsigned)p, (unsigned)the_pid);
 145                         return 0;
 146                 }
 147                 if(threads[thrno])
 148                         fatal_exit("same threadno in two files");
 149                 threads[thrno] = 1;
 150                 if( abs((int)(the_time - t)) > 3600)
 151                         fatal_exit("input files from different times: %u %u",
 152                                 (unsigned)the_time, (unsigned)t);
 153                 printf(" trace of thread %u:%d\n", (unsigned)p, thrno);
 154         }
 155         return 1;
 156 }
 157
 158 /** max length of strings: filenames and function names. */
 159 #define STRMAX 1024
 160 /** read a string from file, false on error */
 161 static int readup_str(char** str, FILE* in)
 162 {
 163         char buf[STRMAX];
 164         int len = 0;
 165         int c;
 166         /* ends in zero */
 167         while( (c = fgetc(in)) != 0) {
 168                 if(c == EOF)
 169                         fatal_exit("eof in readstr, file too short");
 170                 buf[len++] = c;
 171                 if(len == STRMAX) {
 172                         fatal_exit("string too long, bad file format");
 173                 }
 174         }
 175         buf[len] = 0;
 176         *str = strdup(buf);
 177         return 1;
 178 }
 179
 180 /** read creation entry */
 181 static void read_create(rbtree_t* all, FILE* in)
 182 {
 183         struct order_lock* o = calloc(1, sizeof(struct order_lock));
 184         if(!o) fatal_exit("malloc failure");
 185         if(fread(&o->id.thr, sizeof(int), 1, in) != 1 ||
 186            fread(&o->id.instance, sizeof(int), 1, in) != 1 ||
 187            !readup_str(&o->create_file, in) ||
 188            fread(&o->create_line, sizeof(int), 1, in) != 1)
 189                 fatal_exit("fread failed");
 190         o->smaller = rbtree_create(order_lock_cmp);
 191         o->node.key = &o->id;
 192         if(!rbtree_insert(all, &o->node)) {
 193                 /* already inserted */
 194                 struct order_lock* a = (struct order_lock*)rbtree_search(all,
 195                         &o->id);
 196                 log_assert(a);
 197                 a->create_file = o->create_file;
 198                 a->create_line = o->create_line;
 199                 free(o->smaller);
 200                 free(o);
 201                 o = a;
 202         }
 203         if(verb) printf("read create %u %u %s %d\n",
 204                 (unsigned)o->id.thr, (unsigned)o->id.instance,
 205                 o->create_file, o->create_line);
 206 }
 207
 208 /** insert lock entry (empty) into list */
 209 static struct order_lock*
 210 insert_lock(rbtree_t* all, struct order_id* id)
 211 {
 212         struct order_lock* o = calloc(1, sizeof(struct order_lock));
 213         if(!o) fatal_exit("malloc failure");
 214         o->smaller = rbtree_create(order_lock_cmp);
 215         o->id = *id;
 216         o->node.key = &o->id;
 217         if(!rbtree_insert(all, &o->node))
 218                 fatal_exit("insert fail should not happen");
 219         return o;
 220 }
 221
 222 /** read lock entry */
 223 static void read_lock(rbtree_t* all, FILE* in, int val)
 224 {
 225         struct order_id prev_id, now_id;
 226         struct lock_ref* ref;
 227         struct order_lock* prev, *now;
 228         ref = (struct lock_ref*)calloc(1, sizeof(struct lock_ref));
 229         if(!ref) fatal_exit("malloc failure");
 230         prev_id.thr = val;
 231         if(fread(&prev_id.instance, sizeof(int), 1, in) != 1 ||
 232            fread(&now_id.thr, sizeof(int), 1, in) != 1 ||
 233            fread(&now_id.instance, sizeof(int), 1, in) != 1 ||
 234            !readup_str(&ref->file, in) ||
 235            fread(&ref->line, sizeof(int), 1, in) != 1)
 236                 fatal_exit("fread failed");
 237         if(verb) printf("read lock %u %u %u %u %s %d\n",
 238                 (unsigned)prev_id.thr, (unsigned)prev_id.instance,
 239                 (unsigned)now_id.thr, (unsigned)now_id.instance,
 240                 ref->file, ref->line);
 241         /* find the two locks involved */
 242         prev = (struct order_lock*)rbtree_search(all, &prev_id);
 243         now = (struct order_lock*)rbtree_search(all, &now_id);
 244         /* if not there - insert 'em */
 245         if(!prev) prev = insert_lock(all, &prev_id);
 246         if(!now) now = insert_lock(all, &now_id);
 247         ref->lock = prev;
 248         ref->node.key = &prev->id;
 249         if(!rbtree_insert(now->smaller, &ref->node)) {
 250                 free(ref->file);
 251                 free(ref);
 252         }
 253 }
 254
 255 /** read input file */
 256 static void readinput(rbtree_t* all, char* file)
 257 {
 258         FILE *in = fopen(file, "r");
 259         int fst;
 260         if(!in) {
 261                 perror(file);
 262                 exit(1);
 263         }
 264         printf("file %s", file);
 265         if(!read_header(in)) {
 266                 fclose(in);
 267                 return;
 268         }
 269         while(fread(&fst, sizeof(fst), 1, in) == 1) {
 270                 if(fst == -1)
 271                         read_create(all, in);
 272                 else    read_lock(all, in, fst);
 273         }
 274         fclose(in);
 275 }
 276
 277 /** print cycle message */
 278 static void found_cycle(struct lock_ref* visit, int level)
 279 {
 280         struct lock_ref* p;
 281         int i = 0;
 282         errors_detected++;
 283         printf("Found inconsistent locking order of length %d\n", level);
 284         printf("for lock %d %d created %s %d\n",
 285                 visit->lock->id.thr, visit->lock->id.instance,
 286                 visit->lock->create_file, visit->lock->create_line);
 287         printf("sequence is:\n");
 288         p = visit;
 289         while(p) {
 290                 struct order_lock* next =
 291                         p->lock->dfs_next?p->lock->dfs_next->lock:visit->lock;
 292                 printf("[%d] is locked at line %s %d before lock %d %d\n",
 293                         i, p->file, p->line, next->id.thr, next->id.instance);
 294                 printf("[%d] lock %d %d is created at %s %d\n",
 295                         i, next->id.thr, next->id.instance,
 296                         next->create_file, next->create_line);
 297                 i++;
 298                 p = p->lock->dfs_next;
 299                 if(p && p->lock == visit->lock)
 300                         break;
 301         }
 302 }
 303
 304 /** Detect cycle by comparing visited now with all (unvisited) bigger nodes */
 305 static int detect_cycle(struct lock_ref* visit, struct lock_ref* from)
 306 {
 307         struct lock_ref* p = from;
 308         while(p) {
 309                 if(p->lock == visit->lock)
 310                         return 1;
 311                 p = p->lock->dfs_next;
 312         }
 313         return 0;
 314 }
 315
 316 /** recursive function to depth first search for cycles.
 317  * @param visit: the lock visited at this step.
 318  *      its dfs_next pointer gives the visited lock up in recursion.
 319  *      same as lookfor at level 0.
 320  * @param level: depth of recursion. 0 is start.
 321  * @param from: search for matches from unvisited node upwards.
 322  */
 323 static void search_cycle(struct lock_ref* visit, int level,
 324         struct lock_ref* from)
 325 {
 326         struct lock_ref* ref;
 327         /* check for cycle */
 328         if(detect_cycle(visit, from) && level != 0) {
 329                 found_cycle(visit, level);
 330                 fatal_exit("found lock order cycle");
 331         }
 332         /* recurse */
 333         if(!visit->lock->visited)
 334                 from = visit;
 335         if(verb > 1) fprintf(stderr, "[%d] visit lock %u %u %s %d\n", level,
 336                         (unsigned)visit->lock->id.thr,
 337                         (unsigned)visit->lock->id.instance,
 338                         visit->lock->create_file, visit->lock->create_line);
 339         RBTREE_FOR(ref, struct lock_ref*, visit->lock->smaller) {
 340                 ref->lock->dfs_next = visit;
 341                 search_cycle(ref, level+1, from);
 342         }
 343         visit->lock->visited = 1;
 344 }
 345
 346 /** Check ordering of one lock */
 347 static void check_order_lock(struct order_lock* lock)
 348 {
 349         struct lock_ref start;
 350         if(lock->visited) return;
 351
 352         start.node.key = &lock->id;
 353         start.lock = lock;
 354         start.file = lock->create_file;
 355         start.line = lock->create_line;
 356
 357         if(!lock->create_file)
 358                 log_err("lock %u %u does not have create info",
 359                         (unsigned)lock->id.thr, (unsigned)lock->id.instance);
 360
 361         /* depth first search to find cycle with this lock at head */
 362         lock->dfs_next = NULL;
 363         search_cycle(&start, 0, &start);
 364 }
 365
 366 /** Check ordering of locks */
 367 static void check_order(rbtree_t* all_locks)
 368 {
 369         /* check each lock */
 370         struct order_lock* lock;
 371         int i=0;
 372         RBTREE_FOR(lock, struct order_lock*, all_locks) {
 373                 if(verb)
 374                     printf("[%d/%d] Checking lock %d %d %s %d\n",
 375                         i, (int)all_locks->count,
 376                         lock->id.thr, lock->id.instance,
 377                         lock->create_file, lock->create_line);
 378                 else if (i % ((all_locks->count/75)<1?1:all_locks->count/75)
 379                         == 0)
 380                     fprintf(stderr, ".");
 381                 i++;
 382                 check_order_lock(lock);
 383         }
 384         fprintf(stderr, "\n");
 385 }
 386
 387 /** main program to verify all traces passed */
 388 int
 389 main(int argc, char* argv[])
 390 {
 391         rbtree_t* all_locks;
 392         int i;
 393         time_t starttime = time(NULL);
 394         if(argc <= 1) {
 395                 usage();
 396                 return 1;
 397         }
 398         log_init(NULL, 0, NULL);
 399         log_ident_set("lock-verify");
 400         /* init */
 401         all_locks = rbtree_create(order_lock_cmp);
 402         errors_detected = 0;
 403
 404         /* read the input files */
 405         for(i=1; i<argc; i++) {
 406                 readinput(all_locks, argv[i]);
 407         }
 408
 409         /* check ordering */
 410         check_order(all_locks);
 411
 412         /* do not free a thing, OS will do it */
 413         printf("checked %d locks in %d seconds with %d errors.\n",
 414                 (int)all_locks->count, (int)(time(NULL)-starttime),
 415                 errors_detected);
 416         if(errors_detected) return 1;
 417         return 0;
 418 }