Index: uspace/dist/src/bithenge/test.sh
===================================================================
--- uspace/dist/src/bithenge/test.sh	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/dist/src/bithenge/test.sh	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -7,5 +7,5 @@
 if type valgrind >/dev/null 2>&1
 then
-	BITHENGE="valgrind -q --show-reachable=yes ${BITHENGE}"
+	BITHENGE="valgrind -q --show-reachable=yes --error-exitcode=64 ${BITHENGE}"
 else
 	echo "Valgrind not found."
Index: uspace/lib/bithenge/blob.c
===================================================================
--- uspace/lib/bithenge/blob.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/blob.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -58,4 +58,7 @@
 	assert(ops->size);
 
+	if (bithenge_should_fail())
+		return ENOMEM;
+
 	blob->base.type = BITHENGE_NODE_BLOB;
 	blob->base.refs = 1;
@@ -195,4 +198,6 @@
 {
 	memory_blob_t *blob = blob_as_memory(base);
+	if (bithenge_should_fail())
+		return EIO;
 	*size = blob->size;
 	return EOK;
@@ -223,42 +228,4 @@
 	.destroy = memory_destroy,
 };
-
-/** Create a blob node from data. Unlike with @a
- * bithenge_blob_t::bithenge_new_blob_from_buffer, the data is copied into a
- * new buffer and the original data can be changed after this call. The blob
- * must be freed with @a bithenge_node_t::bithenge_node_destroy after it is
- * used.
- * @memberof bithenge_blob_t
- * @param[out] out Stores the created blob node.
- * @param[in] data The data.
- * @param len The length of the data.
- * @return EOK on success or an error code from errno.h. */
-int bithenge_new_blob_from_data(bithenge_node_t **out, const void *data,
-    size_t len)
-{
-	int rc;
-	assert(data || !len);
-
-	memory_blob_t *blob = malloc(sizeof(*blob));
-	if (!blob)
-		return ENOMEM;
-	rc = bithenge_init_random_access_blob(memory_as_blob(blob),
-	    &memory_ops);
-	if (rc != EOK) {
-		free(blob);
-		return rc;
-	}
-	char *buffer = malloc(len);
-	if (!buffer) {
-		free(blob);
-		return rc;
-	}
-	memcpy(buffer, data, len);
-	blob->buffer = buffer;
-	blob->size = len;
-	blob->needs_free = true;
-	*out = bithenge_blob_as_node(memory_as_blob(blob));
-	return EOK;
-}
 
 /** Create a blob node from a buffer. The buffer must exist as long as the blob
@@ -280,12 +247,12 @@
 
 	memory_blob_t *blob = malloc(sizeof(*blob));
-	if (!blob)
-		return ENOMEM;
+	if (!blob) {
+		rc = ENOMEM;
+		goto error;
+	}
 	rc = bithenge_init_random_access_blob(memory_as_blob(blob),
 	    &memory_ops);
-	if (rc != EOK) {
-		free(blob);
-		return rc;
-	}
+	if (rc != EOK)
+		goto error;
 	blob->buffer = buffer;
 	blob->size = len;
@@ -293,5 +260,34 @@
 	*out = bithenge_blob_as_node(memory_as_blob(blob));
 	return EOK;
-}
+	
+error:
+	if (needs_free)
+		free((void *)buffer);
+	free(blob);
+	return rc;
+}
+
+/** Create a blob node from data. Unlike with @a
+ * bithenge_blob_t::bithenge_new_blob_from_buffer, the data is copied into a
+ * new buffer and the original data can be changed after this call. The blob
+ * must be freed with @a bithenge_node_t::bithenge_node_destroy after it is
+ * used.
+ * @memberof bithenge_blob_t
+ * @param[out] out Stores the created blob node.
+ * @param[in] data The data.
+ * @param len The length of the data.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_new_blob_from_data(bithenge_node_t **out, const void *data,
+    size_t len)
+{
+	char *buffer = malloc(len);
+	if (!buffer)
+		return ENOMEM;
+	memcpy(buffer, data, len);
+
+	return bithenge_new_blob_from_buffer(out, buffer, len, true);
+}
+
+
 
 typedef struct {
Index: uspace/lib/bithenge/compound.c
===================================================================
--- uspace/lib/bithenge/compound.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/compound.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -38,4 +38,5 @@
 #include "compound.h"
 #include "expression.h"
+#include "os.h"
 #include "transform.h"
 #include "tree.h"
Index: uspace/lib/bithenge/expression.c
===================================================================
--- uspace/lib/bithenge/expression.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/expression.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -40,4 +40,5 @@
 #include "blob.h"
 #include "expression.h"
+#include "os.h"
 #include "transform.h"
 #include "tree.h"
@@ -53,4 +54,6 @@
 	assert(ops->evaluate);
 	assert(ops->destroy);
+	if (bithenge_should_fail())
+		return ENOMEM;
 	self->ops = ops;
 	self->refs = 1;
@@ -304,4 +307,6 @@
 int bithenge_in_node_expression(bithenge_expression_t **out)
 {
+	if (bithenge_should_fail())
+		return ENOMEM;
 	bithenge_expression_inc_ref(&in_node_expression);
 	*out = &in_node_expression;
Index: uspace/lib/bithenge/failure.c
===================================================================
--- uspace/lib/bithenge/failure.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/failure.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -36,4 +36,5 @@
 
 #include <errno.h>
+#include <execinfo.h>
 #include <fcntl.h>
 #include <stdio.h>
@@ -45,4 +46,5 @@
 #define BITHENGE_FAILURE_DECLS_ONLY 1
 #include "failure.h"
+#include "os.h"
 
 /* This file raises fake errors from system calls, to test that Bithenge
@@ -54,6 +56,6 @@
  * correctly (exit code is 1), the main process continues without errors. If
  * the child process has a problem, the main process raises the fake error
- * again and shows all stdout and stderr output. For speed, failures only occur
- * for some system calls after the first 128.
+ * again and shows all stdout and stderr output. For speed, errors are only
+ * raised when part of the backtrace has not been seen before.
  *
  * BITHENGE_FAILURE_INDEX set: the program runs normally until system call
@@ -61,19 +63,70 @@
  * call. */
 
+static int g_initialized = 0;
 static int g_failure_index = -1;
-static int g_failure_index_selected = -2;
-
-static int should_fail(void)
+static int g_failure_index_selected = -1;
+
+typedef struct backtrace_item {
+	struct backtrace_item *next;
+	void *backtrace_item;
+} backtrace_item_t;
+
+static backtrace_item_t *g_backtrace_items = NULL;
+
+static void atexit_handler(void)
+{
+	while (g_backtrace_items) {
+		backtrace_item_t *first = g_backtrace_items;
+		g_backtrace_items = first->next;
+		free(first);
+	}
+}
+
+static inline void initialize(void)
+{
+	g_initialized = 1;
+	int rc = atexit(atexit_handler);
+	if (rc)
+		exit(127);
+
+	char *sel_str = getenv("BITHENGE_FAILURE_INDEX");
+	if (sel_str)
+		g_failure_index_selected = strtol(sel_str, NULL, 10);
+}
+
+/* Record a hit for a backtrace address and return whether this is the first
+ * hit. */
+static inline int backtrace_item_hit(void *addr)
+{
+	backtrace_item_t **bip;
+	for (bip = &g_backtrace_items; *bip; bip = &(*bip)->next) {
+		backtrace_item_t *bi = *bip;
+		if (bi->backtrace_item == addr) {
+			/* Keep frequently accessed items near the front. */
+			*bip = bi->next;
+			bi->next = g_backtrace_items;
+			g_backtrace_items = bi;
+			return 0;
+		}
+	}
+
+	/* No item found; create one. */
+	backtrace_item_t *i = malloc(sizeof(*i));
+	if (!i)
+		exit(127);
+	i->next = g_backtrace_items;
+	i->backtrace_item = addr;
+	g_backtrace_items = i;
+	return 1;
+}
+
+int bithenge_should_fail(void)
 {
 	g_failure_index++;
 
-	if (g_failure_index_selected == -2) {
-		char *sel_str = getenv("BITHENGE_FAILURE_INDEX");
-		if (sel_str) {
-			g_failure_index_selected = strtol(sel_str, NULL, 10);
-		} else {
-			g_failure_index_selected = -1;
-		}
-	} else if (g_failure_index_selected != -1) {
+	if (!g_initialized)
+		initialize();
+
+	if (g_failure_index_selected != -1) {
 		if (g_failure_index == g_failure_index_selected)
 			return 1; /* breakpoint here */
@@ -81,16 +134,18 @@
 	}
 
-	/* Only fail half the time after 128 failures, 1/4 the time after 256
-	 * failures, 1/8 the time after 512 failures... */
-	int index = g_failure_index;
-	while (index >= 128) {
-		int test = (index & (64 | 1));
-		if (test == (64 | 1) || test == 0)
-			return 0;
-		index >>= 1;
-	}
+	/* If all backtrace items have been seen already, there's no need to
+	 * try raising an error. */
+	void *trace[256];
+	int size = backtrace(trace, 256);
+	int raise_error = 0;
+	for (int i = 0; i < size; i++) {
+		if (backtrace_item_hit(trace[i]))
+			raise_error = 1;
+	}
+	if (!raise_error)
+		return 0;
 
 	if (!fork()) {
-		/* Child */
+		/* Child silently fails. */
 		int null = open("/dev/null", O_WRONLY);
 		if (null == -1)
@@ -102,5 +157,5 @@
 	}
 
-	/* Parent */
+	/* Parent checks whether child failed correctly. */
 	int status;
 	wait(&status);
@@ -108,7 +163,7 @@
 		return 0;
 
-	/* The child had an error! We couldn't see it because stdout and stderr
-	 * were redirected, and we couldn't debug it easily because it was a
-	 * separate process. Do it again without redirecting or forking. */
+	/* The child had an error! We couldn't easily debug it because it was
+	 * in a separate process with redirected stdout and stderr. Do it again
+	 * without redirecting or forking. */
 	fprintf(stderr, "** Fake error raised here (BITHENGE_FAILURE_INDEX=%d)\n",
 	    g_failure_index);
@@ -118,5 +173,5 @@
 void *bithenge_failure_malloc(size_t size)
 {
-	if (should_fail())
+	if (bithenge_should_fail())
 		return NULL;
 	return malloc(size);
@@ -125,5 +180,5 @@
 void *bithenge_failure_realloc(void *ptr, size_t size)
 {
-	if (should_fail())
+	if (bithenge_should_fail())
 		return NULL;
 	return realloc(ptr, size);
@@ -132,5 +187,5 @@
 ssize_t bithenge_failure_read(int fd, void *buf, size_t count)
 {
-	if (should_fail()) {
+	if (bithenge_should_fail()) {
 		errno = EIO;
 		return -1;
@@ -141,5 +196,5 @@
 off_t bithenge_failure_lseek(int fd, off_t offset, int whither)
 {
-	if (should_fail()) {
+	if (bithenge_should_fail()) {
 		errno = EINVAL;
 		return (off_t) -1;
@@ -148,4 +203,36 @@
 }
 
+int bithenge_failure_ferror(FILE *stream)
+{
+	if (bithenge_should_fail())
+		return 1;
+	return ferror(stream);
+}
+
+char *bithenge_failure_str_ndup(const char *s, size_t max_len)
+{
+	if (bithenge_should_fail())
+		return NULL;
+	return str_ndup(s, max_len);
+}
+
+int bithenge_failure_open(const char *pathname, int flags)
+{
+	if (bithenge_should_fail()) {
+		errno = EACCES;
+		return -1;
+	}
+	return open(pathname, flags);
+}
+
+int bithenge_failure_fstat(int fd, struct stat *buf)
+{
+	if (bithenge_should_fail()) {
+		errno = EIO;
+		return -1;
+	}
+	return fstat(fd, buf);
+}
+
 /** @}
  */
Index: uspace/lib/bithenge/failure.h
===================================================================
--- uspace/lib/bithenge/failure.h	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/failure.h	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -38,12 +38,21 @@
 #define BITHENGE_FAILURE_H_
 
+#include <fcntl.h>
+#include <stdio.h>
 #include <stdlib.h>
+#include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
+#include "os.h"
 
+int bithenge_should_fail(void);
 void *bithenge_failure_malloc(size_t);
 void *bithenge_failure_realloc(void *, size_t);
 ssize_t bithenge_failure_read(int, void *, size_t);
 off_t bithenge_failure_lseek(int, off_t, int);
+int bithenge_failure_ferror(FILE *);
+char *bithenge_failure_str_ndup(const char *, size_t);
+int bithenge_failure_open(const char *, int);
+int bithenge_failure_fstat(int, struct stat *);
 
 #ifndef BITHENGE_FAILURE_DECLS_ONLY
@@ -52,4 +61,8 @@
 #define read bithenge_failure_read
 #define lseek bithenge_failure_lseek
+#define ferror bithenge_failure_ferror
+#define str_ndup bithenge_failure_str_ndup
+#define open bithenge_failure_open
+#define fstat bithenge_failure_fstat
 #endif
 
Index: uspace/lib/bithenge/file.c
===================================================================
--- uspace/lib/bithenge/file.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/file.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -79,5 +79,5 @@
 		return ELIMIT;
 	if (lseek(blob->fd, offset, SEEK_SET) < 0)
-		return errno == EINVAL ? EIO : EINVAL;
+		return errno == EINVAL ? EIO : errno;
 
 	ssize_t amount_read;
Index: uspace/lib/bithenge/os.h
===================================================================
--- uspace/lib/bithenge/os.h	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/os.h	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -35,3 +35,8 @@
 #ifdef BITHENGE_FAILURE_ENABLE
 #include "failure.h"
+#else
+static inline int bithenge_should_fail(void)
+{
+	return 0;
+}
 #endif
Index: uspace/lib/bithenge/transform.c
===================================================================
--- uspace/lib/bithenge/transform.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/transform.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -40,4 +40,5 @@
 #include <stdlib.h>
 #include "blob.h"
+#include "os.h"
 #include "print.h"
 #include "transform.h"
@@ -62,4 +63,6 @@
 	assert(ops->apply || ops->prefix_apply);
 	assert(ops->destroy);
+	if (bithenge_should_fail())
+		return ENOMEM;
 	self->ops = ops;
 	self->refs = 1;
@@ -371,4 +374,8 @@
 	assert(scope);
 	assert(i >= 0 && i < scope->num_params);
+	if (bithenge_should_fail()) {
+		bithenge_node_dec_ref(node);
+		return ENOMEM;
+	}
 	scope->params[i] = node;
 	return EOK;
@@ -487,4 +494,9 @@
 	assert(transform);
 	assert(bithenge_transform_num_params(transform) == 0);
+
+	if (bithenge_should_fail()) {
+		bithenge_transform_dec_ref(transform);
+		return ENOMEM;
+	}
 
 	barrier_transform_t *self = transform_as_barrier(base);
Index: uspace/lib/bithenge/tree.c
===================================================================
--- uspace/lib/bithenge/tree.c	(revision 5e514c04ed7eb8e5f96e666ab752bb67cf5aaa23)
+++ uspace/lib/bithenge/tree.c	(revision 1a3b95351a712b3761df716b5b170b2587e8b763)
@@ -198,4 +198,6 @@
 int bithenge_new_empty_internal_node(bithenge_node_t **out)
 {
+	if (bithenge_should_fail())
+		return ENOMEM;
 	bithenge_node_inc_ref(&empty_internal_node);
 	*out = &empty_internal_node;
@@ -301,4 +303,6 @@
 {
 	assert(out);
+	if (bithenge_should_fail())
+		return ENOMEM;
 	*out = value ? &true_node : &false_node;
 	(*out)->refs++;