2 files changed, 0 insertions, 426 deletions

diff --git a/external/unbound b/external/unbound
new file mode 160000
+Subproject 193bdc4ee3fe2b0d17e547e86512528c2614483
diff --git a/external/unbound/testcode/lock_verify.c b/external/unbound/testcode/lock_verify.c
deleted file mode 100644
index 666a7029d..000000000
--- a/external/unbound/testcode/lock_verify.c
+++ /dev/null
@@ -1,426 +0,0 @@
-/*
- * 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;
-}