git » libfiu » commit 8e39c4e

diff --git a/libfiu/Makefile b/libfiu/Makefile
index bd46690..3a543ba 100644
--- a/libfiu/Makefile
+++ b/libfiu/Makefile
@@ -26,7 +26,7 @@ DESTDIR=$(PREFIX)
 INSTALL=install
 
 
-OBJS = fiu.o fiu-rc.o backtrace.o
+OBJS = fiu.o fiu-rc.o backtrace.o wtable.o
 
 
 ifneq ($(V), 1)
diff --git a/libfiu/fiu.c b/libfiu/fiu.c
index 68cab04..c03e075 100644
--- a/libfiu/fiu.c
+++ b/libfiu/fiu.c
@@ -12,6 +12,7 @@
 #include "fiu.h"
 #include "fiu-control.h"
 #include "internal.h"
+#include "wtable.h"
 
 
 /* Different methods to decide when a point of failure fails */
@@ -49,17 +50,47 @@ struct pf_info {
 	} minfo;
 };
 
+/* Creates a new pf_info.
+ * Only the common fields are filled, the caller should take care of the
+ * method-specific ones. For internal use only. */
+static struct pf_info *pf_create(const char *name, int failnum,
+		void *failinfo, unsigned int flags, enum pf_method method)
+{
+	struct pf_info *pf;
+
+	rec_count++;
+
+	pf = malloc(sizeof(struct pf_info));
+	if (pf == NULL)
+		goto exit;
+
+	pf->name = strdup(name);
+	if (pf->name == NULL) {
+		free(pf);
+		pf = NULL;
+		goto exit;
+	}
+
+	pf->namelen = strlen(name);
+	pf->failnum = failnum;
+	pf->failinfo = failinfo;
+	pf->flags = flags;
+	pf->method = method;
+
+exit:
+	rec_count--;
+	return pf;
+}
+
+static void pf_free(struct pf_info *pf) {
+	free(pf->name);
+	free(pf);
+}
+
 
-/* Array used to keep the information about the enabled points of failure.
- * It's an array because we assume it's going to be short enough for the
- * linear lookup not matter.
- * In the future, if it turns out it's normal that it grows large enough, we
- * may be interested in a more sophisticated structure like a hash table
- * and/or a bloom filter. */
-static struct pf_info *enabled_fails = NULL;
-static struct pf_info *enabled_fails_last = NULL;
-static size_t enabled_fails_len = 0;
-static size_t enabled_fails_nfree = 0;
+/* Table used to keep the information about the enabled points of failure.
+ * It is protected by enabled_fails_lock. */
+wtable_t *enabled_fails = NULL;
 static pthread_rwlock_t enabled_fails_lock = PTHREAD_RWLOCK_INITIALIZER;
 
 #define ef_rlock() do { pthread_rwlock_rdlock(&enabled_fails_lock); } while (0)
@@ -67,6 +98,7 @@ static pthread_rwlock_t enabled_fails_lock = PTHREAD_RWLOCK_INITIALIZER;
 #define ef_runlock() do { pthread_rwlock_unlock(&enabled_fails_lock); } while (0)
 #define ef_wunlock() do { pthread_rwlock_unlock(&enabled_fails_lock); } while (0)
 
+
 /* To prevent unwanted recursive calls that would deadlock, we use a
  * thread-local recursion count. Unwanted recursive calls can result from
  * using functions that have been modified to call fiu_fail(), which can
@@ -83,15 +115,6 @@ static pthread_rwlock_t enabled_fails_lock = PTHREAD_RWLOCK_INITIALIZER;
 __thread int rec_count = 0;
 
 
-/* Maximum number of free elements in enabled_fails (used to decide when to
- * shrink). */
-#define EF_MAX_FREE 3
-
-/* How much to grow enabled_fails by each time, it's recommended that this is
- * less than EF_MAX_FREE. */
-#define EF_GROW 2
-
-
 /* Used to keep the last failinfo via TLS */
 static pthread_key_t last_failinfo_key;
 
@@ -100,80 +123,6 @@ static pthread_key_t last_failinfo_key;
  * Miscelaneous internal functions
  */
 
-/* Disables the given pf_info, assuming it's inside enabled_fails. Must be
- * called with enabled_fails_lock acquired. */
-static void disable_pf(struct pf_info *pf)
-{
-	/* free the name we've allocated in setup_fail() via strdup() */
-	free(pf->name);
-	pf->name = NULL;
-	pf->namelen = 0;
-	pf->failnum = 0;
-	pf->failinfo = NULL;
-	pf->flags = 0;
-}
-
-/* Return the last position where s1 and s2 match. */
-static unsigned int strlast(const char *s1, const char *s2)
-{
-	unsigned int i = 0;
-
-	while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2) {
-		i++;
-		s1++;
-		s2++;
-	}
-
-	return i;
-}
-
-/* Checks if pf's name matches the one given. pf->name can be NULL. */
-static int name_matches(const struct pf_info *pf, const char *name, int exact)
-{
-	if (pf->name == NULL || name == NULL)
-		return 0;
-
-	if (exact || pf->name[pf->namelen - 1] != '*')
-		return strcmp(pf->name, name) == 0;
-
-	/* Inexact match */
-	return strlast(pf->name, name) >= pf->namelen - 1;
-}
-
-/* Shrink enabled_fails, used when it has too many free elements. Must be
- * called with enabled_fails_lock acquired. */
-static int shrink_enabled_fails(void)
-{
-	int i;
-	size_t new_len;
-	struct pf_info *new, *pf;
-
-	new_len = enabled_fails_len - enabled_fails_nfree + EF_GROW;
-
-	new = malloc(new_len * sizeof(struct pf_info));
-	if (new == NULL)
-		return -1;
-
-	i = 0;
-	for (pf = enabled_fails; pf <= enabled_fails_last; pf++) {
-		if (pf->name == NULL)
-			continue;
-
-		memcpy(new + i, pf, sizeof(struct pf_info));
-		i++;
-	}
-
-	memset(new + i, 0, (new_len - i) * sizeof(struct pf_info));
-
-	free(enabled_fails);
-	enabled_fails = new;
-	enabled_fails_len = new_len;
-	enabled_fails_last = new + new_len - 1;
-	enabled_fails_nfree = EF_GROW;
-
-	return 0;
-}
-
 /* Determines if the given address is within the function code. */
 static int pc_in_func(struct pf_info *pf, void *pc)
 {
@@ -271,10 +220,7 @@ int fiu_init(unsigned int flags)
 
 	pthread_key_create(&last_failinfo_key, NULL);
 
-	enabled_fails = NULL;
-	enabled_fails_last = NULL;
-	enabled_fails_len = 0;
-	enabled_fails_nfree = 0;
+	enabled_fails = wtable_create((void (*)(void *)) pf_free);
 
 	if (pthread_atfork(NULL, NULL, atfork_child) != 0) {
 		ef_wunlock();
@@ -310,39 +256,36 @@ int fiu_fail(const char *name)
 
 	ef_rlock();
 
-	if (enabled_fails == NULL) {
+	pf = wtable_get(enabled_fails, name);
+
+	/* None found. */
+	if (pf == NULL) {
 		ef_runlock();
 		rec_count--;
 		return 0;
 	}
 
-	for (pf = enabled_fails; pf <= enabled_fails_last; pf++) {
-		if (name_matches(pf, name, 0)) {
-			switch (pf->method) {
-			case PF_ALWAYS:
+	switch (pf->method) {
+		case PF_ALWAYS:
+			goto exit_fail;
+			break;
+		case PF_PROB:
+			if (pf->minfo.probability > randd())
 				goto exit_fail;
-				break;
-			case PF_PROB:
-				if (pf->minfo.probability > randd())
-					goto exit_fail;
-				break;
-			case PF_EXTERNAL:
-				if (pf->minfo.external_cb(pf->name,
-						&(pf->failnum),
-						&(pf->failinfo),
-						&(pf->flags)))
-					goto exit_fail;
-				break;
-			case PF_STACK:
-				if (should_stack_fail(pf))
-					goto exit_fail;
-				break;
-			default:
-				break;
-			}
-
 			break;
-		}
+		case PF_EXTERNAL:
+			if (pf->minfo.external_cb(pf->name,
+					&(pf->failnum),
+					&(pf->failinfo),
+					&(pf->flags)))
+				goto exit_fail;
+			break;
+		case PF_STACK:
+			if (should_stack_fail(pf))
+				goto exit_fail;
+			break;
+		default:
+			break;
 	}
 
 	ef_runlock();
@@ -355,8 +298,7 @@ exit_fail:
 	failnum = pf->failnum;
 
 	if (pf->flags & FIU_ONETIME) {
-		disable_pf(pf);
-		enabled_fails_nfree++;
+		wtable_del(enabled_fails, name);
 	}
 
 	ef_runlock();
@@ -375,94 +317,20 @@ void *fiu_failinfo(void)
  * Control API
  */
 
-/* Sets up the given pf.
- * Only the common fields are filled, the caller should take care of the
- * method-specific ones. For internal use only. */
-static int setup_fail(struct pf_info *pf, const char *name, int failnum,
-		void *failinfo, unsigned int flags, enum pf_method method)
-{
-	pf->name = strdup(name);
-	if (pf->name == NULL)
-		return -1;
-
-	pf->namelen = strlen(name);
-	pf->failnum = failnum;
-	pf->failinfo = failinfo;
-	pf->flags = flags;
-	pf->method = method;
-
-	return 0;
-}
-
-/* Creates a new pf in the enabled_fails table.
- * Only the common fields are filled, the caller should take care of the
- * method-specific ones. For internal use only. */
-static struct pf_info *insert_new_fail(const char *name, int failnum,
-		void *failinfo, unsigned int flags, enum pf_method method)
+/* Inserts a pf into in the enabled_fails table.
+ * Returns 0 on success, -1 on failure. */
+static int insert_pf(struct pf_info *pf)
 {
-	struct pf_info *pf = NULL;
-	int rv = -1;
-	size_t prev_len;
+	bool success;
 
 	rec_count++;
 
-	/* See if it's already there and update the data if so, or if we have
-	 * a free spot where to put it */
 	ef_wlock();
-	if (enabled_fails != NULL && enabled_fails_nfree > 0) {
-		for (pf = enabled_fails; pf <= enabled_fails_last; pf++) {
-			if (pf->name == NULL || strcmp(pf->name, name) == 0) {
-				rv = setup_fail(pf, name, failnum, failinfo,
-						flags, method);
-				if (rv != 0) {
-					pf = NULL;
-					goto exit;
-				}
-
-				enabled_fails_nfree--;
-				goto exit;
-			}
-		}
-
-		/* There should be a free slot, but couldn't find one! This
-		 * shouldn't happen */
-		pf = NULL;
-		goto exit;
-	}
-
-	/* There are no free slots in enabled_fails, so we must grow it */
-	enabled_fails = realloc(enabled_fails,
-			(enabled_fails_len + EF_GROW) * sizeof(struct pf_info));
-	if (enabled_fails == NULL) {
-		enabled_fails_last = NULL;
-		enabled_fails_len = 0;
-		enabled_fails_nfree = 0;
-		pf = NULL;
-		goto exit;
-	}
-
-	prev_len = enabled_fails_len;
-	enabled_fails_len += EF_GROW;
-	enabled_fails_nfree = EF_GROW;
-
-	memset(enabled_fails + prev_len, 0,
-			EF_GROW * sizeof(struct pf_info));
-
-	enabled_fails_last = enabled_fails + enabled_fails_len - 1;
-
-	pf = enabled_fails + prev_len;
-	rv = setup_fail(pf, name, failnum, failinfo, flags, method);
-	if (rv != 0) {
-		pf = NULL;
-		goto exit;
-	}
-
-	enabled_fails_nfree--;
-
-exit:
+	success = wtable_set(enabled_fails, pf->name, pf);
 	ef_wunlock();
+
 	rec_count--;
-	return pf;
+	return success ? 0 : -1;
 }
 
 /* Makes the given name fail. */
@@ -471,11 +339,11 @@ int fiu_enable(const char *name, int failnum, void *failinfo,
 {
 	struct pf_info *pf;
 
-	pf = insert_new_fail(name, failnum, failinfo, flags, PF_ALWAYS);
+	pf = pf_create(name, failnum, failinfo, flags, PF_ALWAYS);
 	if (pf == NULL)
 		return -1;
 
-	return 0;
+	return insert_pf(pf);
 }
 
 /* Makes the given name fail with the given probability. */
@@ -484,12 +352,12 @@ int fiu_enable_random(const char *name, int failnum, void *failinfo,
 {
 	struct pf_info *pf;
 
-	pf = insert_new_fail(name, failnum, failinfo, flags, PF_PROB);
+	pf = pf_create(name, failnum, failinfo, flags, PF_PROB);
 	if (pf == NULL)
 		return -1;
 
 	pf->minfo.probability = probability;
-	return 0;
+	return insert_pf(pf);
 }
 
 /* Makes the given name fail when the external function returns != 0. */
@@ -498,12 +366,12 @@ int fiu_enable_external(const char *name, int failnum, void *failinfo,
 {
 	struct pf_info *pf;
 
-	pf = insert_new_fail(name, failnum, failinfo, flags, PF_EXTERNAL);
+	pf = pf_create(name, failnum, failinfo, flags, PF_EXTERNAL);
 	if (pf == NULL)
 		return -1;
 
 	pf->minfo.external_cb = external_cb;
-	return 0;
+	return insert_pf(pf);
 }
 
 /* Makes the given name fail when func is in the stack at func_pos.
@@ -520,7 +388,7 @@ int fiu_enable_stack(const char *name, int failnum, void *failinfo,
 	if (backtrace_works((void (*)()) fiu_enable_stack) == 0)
 		return -1;
 
-	pf = insert_new_fail(name, failnum, failinfo, flags, PF_STACK);
+	pf = pf_create(name, failnum, failinfo, flags, PF_STACK);
 	if (pf == NULL)
 		return -1;
 
@@ -530,7 +398,7 @@ int fiu_enable_stack(const char *name, int failnum, void *failinfo,
 	 * to make it work, see pc_in_func() above. */
 	pf->minfo.stack.func_end = get_func_end(func);
 	pf->minfo.stack.func_pos_in_stack = func_pos_in_stack;
-	return 0;
+	return insert_pf(pf);
 }
 
 /* Same as fiu_enable_stack(), but takes a function name. */
@@ -557,35 +425,17 @@ int fiu_enable_stack_by_name(const char *name, int failnum, void *failinfo,
 /* Makes the given name NOT fail. */
 int fiu_disable(const char *name)
 {
-	struct pf_info *pf;
+	bool success;
 
 	rec_count++;
 
-	/* just find the point of failure and mark it as free by setting its
-	 * name to NULL */
+	/* Just find the point of failure and remove it. */
 	ef_wlock();
-
-	if (enabled_fails == NULL) {
-		ef_wunlock();
-		rec_count--;
-		return -1;
-	}
-
-	for (pf = enabled_fails; pf <= enabled_fails_last; pf++) {
-		if (name_matches(pf, name, 1)) {
-			disable_pf(pf);
-			enabled_fails_nfree++;
-			if (enabled_fails_nfree > EF_MAX_FREE)
-				shrink_enabled_fails();
-			ef_wunlock();
-			rec_count--;
-			return 0;
-		}
-	}
-
+	success = wtable_del(enabled_fails, name);
 	ef_wunlock();
+
 	rec_count--;
-	return -1;
+	return success ? 0 : -1;
 }
 
 
diff --git a/libfiu/wtable.c b/libfiu/wtable.c
new file mode 100644
index 0000000..11dc764
--- /dev/null
+++ b/libfiu/wtable.c
@@ -0,0 +1,281 @@
+
+/*
+ * Wildcard table.
+ *
+ * This is a simple key-value table that associates a key (\0-terminated
+ * string) with a value (void *).
+ *
+ * The keys can end in a wildcard ('*'), and then a lookup will match them as
+ * expected.
+ *
+ * The current implementation is a very simple dynamic array, which is good
+ * enough for a small number of elements (< 100), but we should optimize this
+ * in the future, in particular to speed up lookups.
+ *
+ * If more than one entry matches, we do not guarantee any order, although
+ * this may change in the future.
+ */
+
+#include <sys/types.h>		/* for size_t */
+#include <stdint.h>		/* for [u]int*_t */
+#include <stdbool.h>		/* for bool */
+#include <stdlib.h>		/* for malloc() */
+#include <string.h>		/* for memcpy()/memcmp() */
+#include <stdio.h>		/* snprintf() */
+#include "wtable.h"
+
+
+struct entry {
+	char *key;
+	size_t key_len;
+
+	void *value;
+	bool in_use;
+};
+
+struct wtable {
+	struct entry *entries;
+	size_t table_size;
+	size_t nentries;
+	void (*destructor)(void *);
+};
+
+
+/* Minimum table size. */
+#define MIN_SIZE 10
+
+struct wtable *wtable_create(void (*destructor)(void *))
+{
+	struct wtable *t = malloc(sizeof(struct wtable));
+	if (t == NULL)
+		return NULL;
+
+	t->entries = malloc(sizeof(struct entry) * MIN_SIZE);
+	if (t->entries == NULL) {
+		free(t);
+		return NULL;
+	}
+
+	memset(t->entries, 0, sizeof(struct entry) * MIN_SIZE);
+
+	t->table_size = MIN_SIZE;
+	t->nentries = 0;
+	t->destructor = destructor;
+
+	return t;
+}
+
+void wtable_free(struct wtable *t)
+{
+	int i;
+	struct entry *entry;
+
+	for (i = 0; i < t->table_size; i++) {
+		entry = t->entries + i;
+		if (entry->in_use) {
+			t->destructor(entry->value);
+			free(entry->key);
+		}
+	}
+
+	free(t->entries);
+	free(t);
+}
+
+/* Return the last position where s1 and s2 match. */
+static unsigned int strlast(const char *s1, const char *s2)
+{
+	unsigned int i = 0;
+
+	while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2) {
+		i++;
+		s1++;
+		s2++;
+	}
+
+	return i;
+}
+
+/* Checks if ws matches s.
+ *
+ * ws is a "wildcard string", which can end in a '*', in which case we compare
+ * only up to that position, to do a wildcard matching.
+ */
+static bool ws_matches_s(
+		const char *ws, size_t ws_len,
+		const char *s, size_t s_len,
+		bool exact)
+{
+	if (ws == NULL || s == NULL)
+		return false;
+
+	if (exact || ws[ws_len - 1] != '*') {
+		/* Exact match */
+		if (ws_len != s_len)
+			return false;
+		return strcmp(ws, s) == 0;
+	} else {
+		/* Inexact match */
+		return strlast(ws, s) >= ws_len - 1;
+	}
+}
+
+/* Find the entry matching the given key.
+ *
+ * If exact == true, then the key must match exactly (no wildcard matching).
+ * If first_free is not NULL, then it will be made to point to the first free
+ * entry found during the lookup.
+ *
+ * Returns a pointer to the entry, or NULL if not found.
+ */
+static struct entry *find_entry(struct wtable *t, const char *key,
+		bool exact, struct entry **first_free)
+{
+	size_t key_len;
+	size_t pos;
+	struct entry *entry;
+	bool found_free = false;
+
+	key_len = strlen(key);
+
+	for (pos = 0; pos < t->table_size; pos++) {
+		entry = t->entries + pos;
+		if (!entry->in_use) {
+			if (!found_free && first_free) {
+				*first_free = entry;
+				found_free = true;
+			}
+			continue;
+
+		} else if (ws_matches_s(entry->key, entry->key_len,
+				key, key_len, exact)) {
+			/* The key matches. */
+			return entry;
+		}
+	}
+
+	/* No match. */
+	return NULL;
+
+}
+
+void *wtable_get(struct wtable *t, const char *key)
+{
+	struct entry *entry = find_entry(t, key, false, NULL);
+
+	if (entry)
+		return entry->value;
+	return NULL;
+}
+
+/* Internal version of wtable_set().
+ * It uses the key as-is (it won't copy it), and it won't resize the array
+ * either. */
+static bool _wtable_set(struct wtable *t, char *key, void *value)
+{
+	struct entry *entry, *first_free;
+
+	first_free = NULL;
+	entry = find_entry(t, key, true, &first_free);
+
+	if (entry) {
+		/* Found a match, override the value. */
+		free(entry->key);
+		entry->key = key;
+		t->destructor(entry->value);
+		entry->value = value;
+		return true;
+	} else if (first_free) {
+		/* We are inserting a new entry. */
+		first_free->key = key;
+		first_free->key_len = strlen(key);
+		first_free->value = value;
+		first_free->in_use = true;
+		t->nentries++;
+		return true;
+	}
+
+	/* This should never happen, as we should always have space by the
+	 * time this function is called. */
+	return false;
+}
+
+static bool resize_table(struct wtable *t, size_t new_size)
+{
+	size_t i;
+	struct entry *old_entries, *e;
+	size_t old_size;
+
+	if (new_size < MIN_SIZE) {
+		/* Do not resize below the minimum size. */
+		return true;
+	}
+
+	old_entries = t->entries;
+	old_size = t->table_size;
+
+	t->entries = malloc(sizeof(struct entry) * new_size);
+	if (t->entries == NULL)
+		return false;
+
+	memset(t->entries, 0, sizeof(struct entry) * new_size);
+	t->table_size = new_size;
+	t->nentries = 0;
+
+	/* Insert the old entries into the new table. We use the internal
+	 * version _wtable_set() to avoid copying the keys again. */
+	for (i = 0; i < old_size; i++) {
+		e = old_entries + i;
+		if (e->in_use) {
+			_wtable_set(t, e->key, e->value);
+		}
+	}
+
+	return true;
+}
+
+bool wtable_set(struct wtable *t, const char *key, void *value)
+{
+	if ((t->table_size - t->nentries) <= 1) {
+		/* If we only have one entry left, grow by 30%, plus one to
+		 * make sure we always increase even if the percentage isn't
+		 * enough. */
+		if (!resize_table(t, t->table_size * 1.3 + 1))
+			return false;
+	}
+
+	return _wtable_set(t, strdup(key), value);
+}
+
+
+bool wtable_del(struct wtable *t, const char *key)
+{
+	struct entry *entry;
+
+	entry = find_entry(t, key, true, NULL);
+
+	if (!entry) {
+		/* Key not found. */
+		return false;
+	}
+
+	/* Mark the entry as free. */
+	free(entry->key);
+	entry->key = NULL;
+	entry->key_len = 0;
+	t->destructor(entry->value);
+	entry->value = NULL;
+	entry->in_use = false;
+
+	t->nentries--;
+
+	/* Shrink if the table is less than 60% occupied. */
+	if (t->table_size > MIN_SIZE &&
+			(float) t->nentries / t->table_size < 0.6) {
+		if (!resize_table(t, t->nentries + 3))
+			return false;
+	}
+
+	return true;
+}
+
diff --git a/libfiu/wtable.h b/libfiu/wtable.h
new file mode 100644
index 0000000..e39f6c5
--- /dev/null
+++ b/libfiu/wtable.h
@@ -0,0 +1,24 @@
+
+/* Wildcard table.
+ *
+ * This is a simple key-value table that associates a key (\0-terminated
+ * string) with a value (void *).
+ *
+ * See wtable.c for more information. */
+
+#ifndef _WTABLE_H
+#define _WTABLE_H
+
+#include <stdbool.h>		/* for bool */
+
+typedef struct wtable wtable_t;
+
+wtable_t *wtable_create(void (*destructor)(void *));
+void wtable_free(wtable_t *t);
+
+void *wtable_get(wtable_t *t, const char *key);
+bool wtable_set(wtable_t *t, const char *key, void *value);
+bool wtable_del(wtable_t *t, const char *key);
+
+#endif
+