60a7029fcd
type names are reserved by POSIX. - iana portlist update git-svn-id: https://unbound.nlnetlabs.nl/svn/trunk@3989 be551aaa-1e26-0410-a405-d3ace91eadb9
427 lines
12 KiB
C
427 lines
12 KiB
C
/*
|
|
* 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);
|
|
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");
|
|
}
|
|
|
|
/** 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;
|
|
}
|
|
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;
|
|
}
|