trust: Rework index to be faster and more usable

The index now uses a sort of cross between a hash table and a bloom
filter internally to select matching items. This is needed for the
massive amount of lookups we want to do during loading.

In addition make p11_index_find() and p11_index_replace() easier
to use.

9 files changed, 437 insertions, 179 deletions

diff --git a/trust/builder.c b/trust/builder.c
index f4ababa..93c5f3e 100644
--- a/trust/builder.c
+++ b/trust/builder.c
@@ -127,7 +127,7 @@ lookup_extension (p11_builder *builder,
 	if (match[0].pValue != NULL) {
 		match[0].ulValueLen = length;
 
-		obj = p11_index_find (index, match);
+		obj = p11_index_find (index, match, -1);
 		attrs = p11_index_lookup (index, obj);
 		if (attrs != NULL) {
 			value = p11_attrs_find_value (attrs, CKA_VALUE, ext_len);
@@ -166,7 +166,7 @@ lookup_related  (p11_index *index,
 	match[0].pValue = id->pValue;
 	match[0].ulValueLen = id->ulValueLen;
 
-	return p11_index_find_all (index, match);
+	return p11_index_find_all (index, match, -1);
 }
 
 p11_builder *
@@ -1078,6 +1078,7 @@ replace_nss_trust_object (p11_builder *builder,
 	CK_ATTRIBUTE_PTR issuer;
 	CK_ATTRIBUTE_PTR serial_number;
 
+	p11_array *array;
 	void *value;
 	size_t length;
 
@@ -1107,7 +1108,7 @@ replace_nss_trust_object (p11_builder *builder,
 	return_if_fail (match != NULL);
 
 	/* If we find a non-generated object, then don't generate */
-	if (p11_index_find (index, match)) {
+	if (p11_index_find (index, match, -1)) {
 		p11_debug ("not generating nss trust object because one already exists");
 		attrs = NULL;
 
@@ -1153,8 +1154,11 @@ replace_nss_trust_object (p11_builder *builder,
 	}
 
 	/* Replace related generated object with this new one */
-	rv = p11_index_replace (index, match, CKA_INVALID, attrs);
+	array = p11_array_new (NULL);
+	p11_array_push (array, attrs);
+	rv = p11_index_replace_all (index, match, CKA_INVALID, array);
 	return_if_fail (rv == CKR_OK);
+	p11_array_free (array);
 }
 
 static void
@@ -1450,7 +1454,7 @@ replace_compat_for_cert (p11_builder *builder,
 		if (value != NULL) {
 			match[0].pValue = value->pValue;
 			match[0].ulValueLen = value->ulValueLen;
-			handle = p11_index_find (index, match);
+			handle = p11_index_find (index, match, -1);
 		}
 		if (handle != 0)
 			attrs = p11_index_lookup (index, handle);
diff --git a/trust/index.c b/trust/index.c
index 17370bc..6e9a46c 100644
--- a/trust/index.c
+++ b/trust/index.c
@@ -44,16 +44,33 @@
 
 #include <assert.h>
 #include <stdlib.h>
+#include <string.h>
 
 /*
- * TODO: Eventually we want to be using a bloom filter to optimize and
- * actually implement the index.
+ * The number of buckets we use for indexing, should end up as roughly
+ * equal to the expected number of unique attribute values * 0.75,
+ * prime if possible. Currently we don't expand the index, so this is
+ * just a good guess for general usage.
  */
+#define NUM_BUCKETS 7919
+
+/*
+ * The number of indexes to use when trying to find a matching object.
+ */
+#define MAX_SELECT 3
+
+typedef struct {
+	CK_OBJECT_HANDLE *elem;
+	int num;
+} index_bucket;
 
 struct _p11_index {
-	/* The list of objects */
+	/* The list of objects by handle */
 	p11_dict *objects;
 
+	/* Used for indexing */
+	index_bucket *buckets;
+
 	/* Data passed to callbacks */
 	void *data;
 
@@ -61,29 +78,29 @@ struct _p11_index {
 	p11_index_build_cb build;
 
 	/* Called after objects change */
-	p11_index_changed_cb changed;
+	p11_index_notify_cb notify;
 
 	/* Used for queueing changes, when in a batch */
 	p11_dict *changes;
-	bool changing;
+	bool notifying;
 };
 
-struct object {
+typedef struct {
 	CK_OBJECT_HANDLE handle;
 	CK_ATTRIBUTE *attrs;
-};
+} index_object;
 
 static void
 free_object (void *data)
 {
-	struct object *obj = data;
+	index_object *obj = data;
 	p11_attrs_free (obj->attrs);
 	free (obj);
 }
 
 p11_index *
 p11_index_new (p11_index_build_cb build,
-               p11_index_changed_cb changed,
+               p11_index_notify_cb notify,
                void *data)
 {
 	p11_index *index;
@@ -92,7 +109,7 @@ p11_index_new (p11_index_build_cb build,
 	return_val_if_fail (index != NULL, NULL);
 
 	index->build = build;
-	index->changed = changed;
+	index->notify = notify;
 	index->data = data;
 
 	index->objects = p11_dict_new (p11_dict_ulongptr_hash,
@@ -100,16 +117,24 @@ p11_index_new (p11_index_build_cb build,
 	                               NULL, free_object);
 	return_val_if_fail (index->objects != NULL, NULL);
 
+	index->buckets = calloc (NUM_BUCKETS, sizeof (index_bucket));
+	return_val_if_fail (index->buckets != NULL, NULL);
+
 	return index;
 }
 
 void
 p11_index_free (p11_index *index)
 {
+	int i;
+
 	return_if_fail (index != NULL);
 
 	p11_dict_free (index->objects);
 	p11_dict_free (index->changes);
+	for (i = 0; i < NUM_BUCKETS; i++)
+		free (index->buckets[i].elem);
+	free (index->buckets);
 	free (index);
 }
 
@@ -120,6 +145,111 @@ p11_index_size (p11_index *index)
 	return p11_dict_size (index->objects);
 }
 
+static bool
+is_indexable (p11_index *index,
+              CK_ATTRIBUTE_TYPE type)
+{
+	switch (type) {
+	case CKA_CLASS:
+	case CKA_VALUE:
+	case CKA_OBJECT_ID:
+	case CKA_ID:
+		return true;
+	}
+
+	return false;
+}
+
+static unsigned int
+alloc_size (int num)
+{
+	unsigned int n = num ? 1 : 0;
+	while (n < num && n > 0)
+		n <<= 1;
+	return n;
+}
+
+static int
+binary_search (CK_OBJECT_HANDLE *elem,
+               int low,
+               int high,
+               CK_OBJECT_HANDLE handle)
+{
+	int mid;
+
+	if (low == high)
+		return low;
+
+	mid = low + ((high - low) / 2);
+	if (handle > elem[mid])
+		return binary_search (elem, mid + 1, high, handle);
+	else if (handle < elem[mid])
+		return binary_search (elem, low, mid, handle);
+
+	return mid;
+}
+
+
+static void
+bucket_insert (index_bucket *bucket,
+               CK_OBJECT_HANDLE handle)
+{
+	unsigned int alloc;
+	int at = 0;
+
+	if (bucket->elem) {
+		at = binary_search (bucket->elem, 0, bucket->num, handle);
+		if (at < bucket->num && bucket->elem[at] == handle)
+			return;
+	}
+
+	alloc = alloc_size (bucket->num);
+	if (bucket->num + 1 > alloc) {
+		alloc = alloc ? alloc * 2 : 1;
+		return_if_fail (alloc != 0);
+		bucket->elem = realloc (bucket->elem, alloc * sizeof (CK_OBJECT_HANDLE));
+		return_if_fail (bucket->elem != NULL);
+	}
+
+	memmove (bucket->elem + at + 1, bucket->elem + at,
+	         (bucket->num - at) * sizeof (CK_OBJECT_HANDLE));
+	bucket->elem[at] = handle;
+	bucket->num++;
+}
+
+static bool
+bucket_push (index_bucket *bucket,
+             CK_OBJECT_HANDLE handle)
+{
+	unsigned int alloc;
+
+	alloc = alloc_size (bucket->num);
+	if (bucket->num + 1 > alloc) {
+		alloc = alloc ? alloc * 2 : 1;
+		return_val_if_fail (alloc != 0, false);
+		bucket->elem = realloc (bucket->elem, alloc * sizeof (CK_OBJECT_HANDLE));
+		return_val_if_fail (bucket->elem != NULL, false);
+	}
+
+	bucket->elem[bucket->num++] = handle;
+	return true;
+}
+
+static void
+index_hash (p11_index *index,
+            index_object *obj)
+{
+	unsigned int hash;
+	int i;
+
+	for (i = 0; !p11_attrs_terminator (obj->attrs + i); i++) {
+		if (is_indexable (index, obj->attrs[i].type)) {
+			hash = p11_attr_hash (obj->attrs + i);
+			bucket_insert (index->buckets + (hash % NUM_BUCKETS), obj->handle);
+		}
+	}
+}
+
 static CK_RV
 index_build (p11_index *index,
              CK_ATTRIBUTE **attrs,
@@ -134,11 +264,11 @@ index_build (p11_index *index,
 }
 
 static void
-call_change (p11_index *index,
+call_notify (p11_index *index,
              CK_OBJECT_HANDLE handle,
              CK_ATTRIBUTE *attrs)
 {
-	assert (index->changed);
+	assert (index->notify);
 
 	/* When attrs is NULL, means this is a modify */
 	if (attrs == NULL) {
@@ -151,27 +281,27 @@ call_change (p11_index *index,
 		handle = 0;
 	}
 
-	index->changing = true;
-	index->changed (index->data, index, handle, attrs);
-	index->changing = false;
+	index->notifying = true;
+	index->notify (index->data, index, handle, attrs);
+	index->notifying = false;
 }
 
 static void
-index_change (p11_index *index,
+index_notify (p11_index *index,
               CK_OBJECT_HANDLE handle,
               CK_ATTRIBUTE *removed)
 {
-	struct object *obj;
+	index_object *obj;
 
-	if (!index->changed || index->changing)
+	if (!index->notify || index->notifying)
 		return;
 
 	if (!index->changes) {
-		call_change (index, handle, removed);
+		call_notify (index, handle, removed);
 		p11_attrs_free (removed);
 
 	} else {
-		obj = calloc (1, sizeof (struct object));
+		obj = calloc (1, sizeof (index_object));
 		return_if_fail (obj != NULL);
 
 		obj->handle = handle;
@@ -199,7 +329,7 @@ void
 p11_index_finish (p11_index *index)
 {
 	p11_dict *changes;
-	struct object *obj;
+	index_object *obj;
 	p11_dictiter iter;
 
 	return_if_fail (index != NULL);
@@ -211,8 +341,10 @@ p11_index_finish (p11_index *index)
 	index->changes = NULL;
 
 	p11_dict_iterate (changes, &iter);
-	while (p11_dict_next (&iter, NULL, (void **)&obj))
-		call_change (index, obj->handle, obj->attrs);
+	while (p11_dict_next (&iter, NULL, (void **)&obj)) {
+		index_notify (index, obj->handle, obj->attrs);
+		obj->attrs = NULL;
+	}
 
 	p11_dict_free (changes);
 }
@@ -229,13 +361,13 @@ p11_index_take (p11_index *index,
                 CK_ATTRIBUTE *attrs,
                 CK_OBJECT_HANDLE *handle)
 {
-	struct object *obj;
+	index_object *obj;
 	CK_RV rv;
 
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
 	return_val_if_fail (attrs != NULL, CKR_GENERAL_ERROR);
 
-	obj = calloc (1, sizeof (struct object));
+	obj = calloc (1, sizeof (index_object));
 	return_val_if_fail (obj != NULL, CKR_HOST_MEMORY);
 
 	rv = index_build (index, &obj->attrs, attrs);
@@ -250,10 +382,12 @@ p11_index_take (p11_index *index,
 	if (!p11_dict_set (index->objects, &obj->handle, obj))
 		return_val_if_reached (CKR_HOST_MEMORY);
 
+	index_hash (index, obj);
+
 	if (handle)
 		*handle = obj->handle;
 
-	index_change (index, obj->handle, NULL);
+	index_notify (index, obj->handle, NULL);
 	return CKR_OK;
 }
 
@@ -279,7 +413,7 @@ p11_index_update (p11_index *index,
                   CK_OBJECT_HANDLE handle,
                   CK_ATTRIBUTE *update)
 {
-	struct object *obj;
+	index_object *obj;
 	CK_RV rv;
 
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
@@ -297,7 +431,9 @@ p11_index_update (p11_index *index,
 		return rv;
 	}
 
-	index_change (index, obj->handle, NULL);
+	index_hash (index, obj);
+	index_notify (index, obj->handle, NULL);
+
 	return CKR_OK;
 }
 
@@ -308,7 +444,7 @@ p11_index_set (p11_index *index,
                CK_ULONG count)
 {
 	CK_ATTRIBUTE *update;
-	struct object *obj;
+	index_object *obj;
 
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
 
@@ -326,7 +462,7 @@ CK_RV
 p11_index_remove (p11_index *index,
                   CK_OBJECT_HANDLE handle)
 {
-	struct object *obj;
+	index_object *obj;
 
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
 
@@ -334,7 +470,7 @@ p11_index_remove (p11_index *index,
 		return CKR_OBJECT_HANDLE_INVALID;
 
 	/* This takes ownership of the attributes */
-	index_change (index, handle, obj->attrs);
+	index_notify (index, handle, obj->attrs);
 	obj->attrs = NULL;
 	free_object (obj);
 
@@ -343,21 +479,18 @@ p11_index_remove (p11_index *index,
 
 static CK_RV
 index_replacev (p11_index *index,
-                CK_ATTRIBUTE *match,
+                CK_OBJECT_HANDLE *handles,
                 CK_ATTRIBUTE_TYPE key,
                 CK_ATTRIBUTE **replace,
                 CK_ULONG replacen)
 {
-	CK_OBJECT_HANDLE *handles;
-	struct object *obj;
+	index_object *obj;
 	CK_ATTRIBUTE *attrs;
 	CK_ATTRIBUTE *attr;
 	bool handled = false;
 	CK_RV rv;
 	int i, j;
 
-	handles = p11_index_find_all (index, match);
-
 	for (i = 0; handles && handles[i] != 0; i++) {
 		obj = p11_dict_get (index->objects, handles + i);
 		if (obj == NULL)
@@ -380,6 +513,8 @@ index_replacev (p11_index *index,
 					obj->attrs = attrs;
 					replace[j] = NULL;
 					handled = true;
+					index_hash (index, obj);
+					index_notify (index, obj->handle, NULL);
 					break;
 				}
 			}
@@ -401,19 +536,18 @@ index_replacev (p11_index *index,
 		replace[j] = NULL;
 	}
 
-	free (handles);
 	return CKR_OK;
 }
 
 CK_RV
 p11_index_replace (p11_index *index,
-                   CK_ATTRIBUTE *match,
-                   CK_ATTRIBUTE_TYPE key,
+                   CK_OBJECT_HANDLE handle,
                    CK_ATTRIBUTE *replace)
 {
+	CK_OBJECT_HANDLE handles[] = { handle, 0 };
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
-	return index_replacev (index, match, key, &replace,
-	                       replace ? 1 : 0);
+	return index_replacev (index, handles, CKA_INVALID,
+	                       &replace, replace ? 1 : 0);
 }
 
 CK_RV
@@ -422,12 +556,15 @@ p11_index_replace_all (p11_index *index,
                        CK_ATTRIBUTE_TYPE key,
                        p11_array *replace)
 {
+	CK_OBJECT_HANDLE *handles;
 	CK_RV rv;
 	int i;
 
 	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
 
-	rv = index_replacev (index, match, key,
+	handles = p11_index_find_all (index, match, -1);
+
+	rv = index_replacev (index, handles, key,
 	                     (CK_ATTRIBUTE **)replace->elem,
 	                     replace->num);
 
@@ -438,6 +575,7 @@ p11_index_replace_all (p11_index *index,
 		}
 	}
 
+	free (handles);
 	return rv;
 }
 
@@ -445,7 +583,7 @@ CK_ATTRIBUTE *
 p11_index_lookup (p11_index *index,
                   CK_OBJECT_HANDLE handle)
 {
-	struct object *obj;
+	index_object *obj;
 
 	return_val_if_fail (index != NULL, NULL);
 
@@ -456,67 +594,153 @@ p11_index_lookup (p11_index *index,
 	return obj ? obj->attrs : NULL;
 }
 
-CK_OBJECT_HANDLE
-p11_index_find (p11_index *index,
-                CK_ATTRIBUTE *match)
+typedef bool (* index_sink) (p11_index *index,
+                             index_object *obj,
+                             CK_ATTRIBUTE *match,
+                             CK_ULONG count,
+                             void *data);
+
+static void
+index_select (p11_index *index,
+              CK_ATTRIBUTE *match,
+              CK_ULONG count,
+              index_sink sink,
+              void *data)
 {
-	struct object *obj;
+	index_bucket *buckets[NUM_BUCKETS];
+	CK_OBJECT_HANDLE handle;
+	index_object *obj;
+	unsigned int hash;
 	p11_dictiter iter;
+	CK_ULONG n;
+	int num, at;
+	int i, j;
+
+	/* First look for any matching buckets */
+	for (n = 0, num = 0; n < count && num < MAX_SELECT; n++) {
+		if (is_indexable (index, match[n].type)) {
+			hash = p11_attr_hash (match + n);
+			buckets[num] = index->buckets + (hash % NUM_BUCKETS);
+
+			/* If any index is empty, then obviously no match */
+			if (!buckets[num]->num)
+				return;
+
+			num++;
+		}
+	}
+
+	/* Fall back on selecting all the items, if no index */
+	if (num == 0) {
+		p11_dict_iterate (index->objects, &iter);
+		while (p11_dict_next (&iter, NULL, (void *)&obj)) {
+			if (!sink (index, obj, match, count, data))
+				return;
+		}
+		return;
+	}
+
+	for (i = 0; i < buckets[0]->num; i++) {
+		/* A candidate match from first bucket */
+		handle = buckets[0]->elem[i];
+
+		/* Check if the candidate is in other buckets */
+		for (j = 1; j < num; j++) {
+			assert (buckets[j]->elem); /* checked above */
+			at = binary_search (buckets[j]->elem, 0, buckets[j]->num, handle);
+			if (buckets[j]->elem[at] != handle) {
+				handle = 0;
+				break;
+			}
+		}
 
-	p11_dict_iterate (index->objects, &iter);
-	while (p11_dict_next (&iter, NULL, (void *)&obj)) {
-		if (p11_attrs_match (obj->attrs, match))
-			return obj->handle;
+		/* Matched all the buckets, now actually match attrs */
+		if (handle != 0) {
+			obj = p11_dict_get (index->objects, &handle);
+			if (obj != NULL) {
+				if (!sink (index, obj, match, count, data))
+					return;
+			}
+		}
 	}
+}
+
+static bool
+sink_one_match (p11_index *index,
+                index_object *obj,
+                CK_ATTRIBUTE *match,
+                CK_ULONG count,
+                void *data)
+{
+	CK_OBJECT_HANDLE *result = data;
 
-	return 0;
+	if (p11_attrs_matchn (obj->attrs, match, count)) {
+		*result = obj->handle;
+		return false;
+	}
+
+	return true;
 }
 
 CK_OBJECT_HANDLE
-p11_index_findn (p11_index *index,
-                 CK_ATTRIBUTE *match,
-                 CK_ULONG count)
+p11_index_find (p11_index *index,
+                CK_ATTRIBUTE *match,
+                int count)
 {
-	struct object *obj;
-	p11_dictiter iter;
+	CK_OBJECT_HANDLE handle = 0UL;
 
-	p11_dict_iterate (index->objects, &iter);
-	while (p11_dict_next (&iter, NULL, (void *)&obj)) {
-		if (p11_attrs_matchn (obj->attrs, match, count))
-			return obj->handle;
-	}
+	return_val_if_fail (index != NULL, 0UL);
+
+	if (count < 0)
+		count = p11_attrs_count (match);
 
-	return 0;
+	index_select (index, match, count, sink_one_match, &handle);
+	return handle;
+}
+
+static bool
+sink_if_match (p11_index *index,
+               index_object *obj,
+               CK_ATTRIBUTE *match,
+               CK_ULONG count,
+               void *data)
+{
+	index_bucket *handles = data;
+
+	if (p11_attrs_matchn (obj->attrs, match, count))
+		bucket_push (handles, obj->handle);
+	return true;
 }
 
 CK_OBJECT_HANDLE *
 p11_index_find_all (p11_index *index,
-                    CK_ATTRIBUTE *match)
+                    CK_ATTRIBUTE *match,
+                    int count)
 {
-	CK_OBJECT_HANDLE *handles = NULL;
-	struct object *obj;
-	p11_dictiter iter;
-	int nhandles;
-	int at = 0;
+	index_bucket handles = { NULL, 0 };
 
-	nhandles = 16;
-	handles = malloc (nhandles * sizeof (CK_OBJECT_HANDLE));
-	return_val_if_fail (handles != NULL, NULL);
-
-	p11_dict_iterate (index->objects, &iter);
-	while (p11_dict_next (&iter, NULL, (void *)&obj)) {
-		if (p11_attrs_match (obj->attrs, match)) {
-			if (at + 2 > nhandles) {
-				nhandles += 16;
-				handles = realloc (handles, nhandles * sizeof (CK_OBJECT_HANDLE));
-				return_val_if_fail (handles != NULL, NULL);
-			}
-			handles[at++] = obj->handle;
-		}
-	}
+	return_val_if_fail (index != NULL, NULL);
 
-	handles[at++] = 0UL;
-	return handles;
+	if (count < 0)
+		count = p11_attrs_count (match);
+
+	index_select (index, match, count, sink_if_match, &handles);
+
+	/* Null terminate */
+	bucket_push (&handles, 0UL);
+	return handles.elem;
+}
+
+static bool
+sink_any (p11_index *index,
+          index_object *obj,
+          CK_ATTRIBUTE *match,
+          CK_ULONG count,
+          void *data)
+{
+	index_bucket *handles = data;
+	bucket_push (handles, obj->handle);
+	return true;
 }
 
 CK_OBJECT_HANDLE *
@@ -525,43 +749,18 @@ p11_index_snapshot (p11_index *index,
                     CK_ATTRIBUTE *attrs,
                     CK_ULONG count)
 {
-	CK_OBJECT_HANDLE *snapshot;
-	CK_OBJECT_HANDLE *handle;
-	p11_dictiter iter;
-	int num;
-	int i;
-
-	/*
-	 * TODO: The concept is that we use our bloom filter to provide
-	 * an initial rough snapshot here of which objects match, but for
-	 * now just include everything in the snapshot.
-	 */
+	index_bucket handles = { NULL, 0 };
 
 	return_val_if_fail (index != NULL, NULL);
 
-	num = p11_index_size (index) + 1;
-	if (base)
-		num += p11_index_size (base);
-
-	snapshot = calloc (num, sizeof (CK_OBJECT_HANDLE));
-	return_val_if_fail (snapshot != NULL, NULL);
-
-	p11_dict_iterate (index->objects, &iter);
-	for (i = 0 ; p11_dict_next (&iter, (void *)&handle, NULL); i++) {
-		assert (i < num);
-		snapshot[i] = *handle;
-	}
+	if (count < 0)
+		count = p11_attrs_count (attrs);
 
-	if (base) {
-		p11_dict_iterate (base->objects, &iter);
-		for ( ; p11_dict_next (&iter, (void *)&handle, NULL); i++) {
-			assert (i < num);
-			snapshot[i] = *handle;
-		}
-	}
-
-	assert (i < num);
-	assert (snapshot[i] == 0UL);
+	index_select (index, attrs, count, sink_any, &handles);
+	if (base)
+		index_select (base, attrs, count, sink_any, &handles);
 
-	return snapshot;
+	/* Null terminate */
+	bucket_push (&handles, 0UL);
+	return handles.elem;
 }
diff --git a/trust/index.h b/trust/index.h
index 67d0746..a221178 100644
--- a/trust/index.h
+++ b/trust/index.h
@@ -55,13 +55,13 @@ typedef CK_RV   (* p11_index_build_cb)   (void *data,
                                           CK_ATTRIBUTE **attrs,
                                           CK_ATTRIBUTE *merge);
 
-typedef void    (* p11_index_changed_cb) (void *data,
+typedef void    (* p11_index_notify_cb)  (void *data,
                                           p11_index *index,
                                           CK_OBJECT_HANDLE handle,
                                           CK_ATTRIBUTE *attrs);
 
 p11_index *        p11_index_new         (p11_index_build_cb build,
-                                          p11_index_changed_cb change,
+                                          p11_index_notify_cb notify,
                                           void *data);
 
 void               p11_index_free        (p11_index *index);
@@ -93,8 +93,7 @@ CK_RV              p11_index_update      (p11_index *index,
                                           CK_ATTRIBUTE *attrs);
 
 CK_RV              p11_index_replace     (p11_index *index,
-                                          CK_ATTRIBUTE *match,
-                                          CK_ATTRIBUTE_TYPE key,
+                                          CK_OBJECT_HANDLE handle,
                                           CK_ATTRIBUTE *replace);
 
 CK_RV              p11_index_replace_all (p11_index *index,
@@ -109,14 +108,12 @@ CK_ATTRIBUTE *     p11_index_lookup      (p11_index *index,
                                           CK_OBJECT_HANDLE handle);
 
 CK_OBJECT_HANDLE   p11_index_find        (p11_index *index,
-                                          CK_ATTRIBUTE *match);
-
-CK_OBJECT_HANDLE   p11_index_findn       (p11_index *index,
                                           CK_ATTRIBUTE *match,
-                                          CK_ULONG count);
+                                          int count);
 
 CK_OBJECT_HANDLE * p11_index_find_all    (p11_index *index,
-                                          CK_ATTRIBUTE *match);
+                                          CK_ATTRIBUTE *match,
+                                          int count);
 
 CK_OBJECT_HANDLE * p11_index_snapshot    (p11_index *index,
                                           p11_index *base,
diff --git a/trust/tests/Makefile.am b/trust/tests/Makefile.am
index aedc6f3..4617546 100644
--- a/trust/tests/Makefile.am
+++ b/trust/tests/Makefile.am
@@ -29,14 +29,15 @@ LDADD = \
 
 CHECK_PROGS = \
 	test-persist \
-	test-parser \
 	test-index \
+	test-parser \
 	test-builder \
 	test-token \
 	test-module \
 	$(NULL)
 
 noinst_PROGRAMS = \
+	frob-pow \
 	frob-token \
 	frob-nss-trust \
 	$(CHECK_PROGS)
diff --git a/trust/tests/frob-pow.c b/trust/tests/frob-pow.c
new file mode 100644
index 0000000..f029b2a
--- /dev/null
+++ b/trust/tests/frob-pow.c
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2013 Red Hat Inc.
+ *
+ * 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.
+ *     * The names of contributors to this software may not 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 OWNER 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.
+ *
+ * Author: Stef Walter <stefw@redhat.com>
+ */
+
+#include "config.h"
+
+#include <stdio.h>
+
+static unsigned int
+nearest_pow_2 (int num)
+{
+	unsigned int n = num ? 1 : 0;
+	while (n < num && n > 0)
+		n <<= 1;
+	return n;
+}
+
+int
+main (void)
+{
+	int i;
+
+	for (i = 0; i < 40; i++)
+		printf ("nearest_pow_2 (%d) == %u\n", i, nearest_pow_2 (i));
+
+	return 0;
+}
diff --git a/trust/tests/test-builder.c b/trust/tests/test-builder.c
index bbc731a..be5390e 100644
--- a/trust/tests/test-builder.c
+++ b/trust/tests/test-builder.c
@@ -1102,7 +1102,7 @@ test_changed_trusted_certificate (CuTest *cu)
 
 	/* The other objects */
 	for (i = 0; expected[i]; i++) {
-		handle = p11_index_findn (test.index, expected[i], 2);
+		handle = p11_index_find (test.index, expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 
 		attrs = p11_index_lookup (test.index, handle);
@@ -1215,7 +1215,7 @@ test_changed_distrust_value (CuTest *cu)
 
 	/* The other objects */
 	for (i = 0; expected[i]; i++) {
-		handle = p11_index_findn (test.index, expected[i], 2);
+		handle = p11_index_find (test.index, expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 
 		attrs = p11_index_lookup (test.index, handle);
@@ -1299,7 +1299,7 @@ test_changed_distrust_serial (CuTest *cu)
 	p11_index_finish (test.index);
 
 	for (i = 0; expected[i]; i++) {
-		handle = p11_index_findn (test.index, expected[i], 2);
+		handle = p11_index_find (test.index, expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 		attrs = p11_index_lookup (test.index, handle);
 		CuAssertPtrNotNull (cu, attrs);
@@ -1403,13 +1403,13 @@ test_changed_dup_certificates (CuTest *cu)
 	CuAssertIntEquals (cu, CKR_OK, rv);
 	p11_index_finish (test.index);
 
-	handle = p11_index_find (test.index, match_nss);
+	handle = p11_index_find (test.index, match_nss, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, match_assertion);
+	handle = p11_index_find (test.index, match_assertion, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, trusted_nss);
+	handle = p11_index_find (test.index, trusted_nss, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, anchor_assertion);
+	handle = p11_index_find (test.index, anchor_assertion, -1);
 	CuAssertTrue (cu, handle != 0);
 
 	/* Now we add a distrusted certificate, should update the objects */
@@ -1418,35 +1418,35 @@ test_changed_dup_certificates (CuTest *cu)
 	CuAssertIntEquals (cu, CKR_OK, rv);
 	p11_index_finish (test.index);
 
-	handle = p11_index_find (test.index, trusted_nss);
+	handle = p11_index_find (test.index, trusted_nss, -1);
 	CuAssertTrue (cu, handle == 0);
-	handle = p11_index_find (test.index, distrust_nss);
+	handle = p11_index_find (test.index, distrust_nss, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, anchor_assertion);
+	handle = p11_index_find (test.index, anchor_assertion, -1);
 	CuAssertTrue (cu, handle == 0);
-	handle = p11_index_find (test.index, distrust_assertion);
+	handle = p11_index_find (test.index, distrust_assertion, -1);
 	CuAssertTrue (cu, handle != 0);
 
 	/* Now remove the trusted cetrificate, should update again */
 	rv = p11_index_remove (test.index, handle2);
 	CuAssertIntEquals (cu, CKR_OK, rv);
 
-	handle = p11_index_find (test.index, trusted_nss);
+	handle = p11_index_find (test.index, trusted_nss, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, distrust_nss);
+	handle = p11_index_find (test.index, distrust_nss, -1);
 	CuAssertTrue (cu, handle == 0);
-	handle = p11_index_find (test.index, anchor_assertion);
+	handle = p11_index_find (test.index, anchor_assertion, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, distrust_assertion);
+	handle = p11_index_find (test.index, distrust_assertion, -1);
 	CuAssertTrue (cu, handle == 0);
 
 	/* Now remove the original certificate, unknown nss and no assertions */
 	rv = p11_index_remove (test.index, handle1);
 	CuAssertIntEquals (cu, CKR_OK, rv);
 
-	handle = p11_index_find (test.index, unknown_nss);
+	handle = p11_index_find (test.index, unknown_nss, -1);
 	CuAssertTrue (cu, handle != 0);
-	handle = p11_index_find (test.index, match_assertion);
+	handle = p11_index_find (test.index, match_assertion, -1);
 	CuAssertTrue (cu, handle == 0);
 
 	teardown (cu);
@@ -1487,11 +1487,11 @@ test_changed_without_id (CuTest *cu)
 	p11_index_finish (test.index);
 
 	klass = CKO_NSS_TRUST;
-	handle = p11_index_find (test.index, match);
+	handle = p11_index_find (test.index, match, -1);
 	CuAssertTrue (cu, handle != 0);
 
 	klass = CKO_X_TRUST_ASSERTION;
-	handle = p11_index_find (test.index, match);
+	handle = p11_index_find (test.index, match, -1);
 	CuAssertTrue (cu, handle != 0);
 
 	teardown (cu);
@@ -1535,7 +1535,7 @@ test_changed_staple_ca (CuTest *cu)
 
 	/* Not a CA at this point, until we staple */
 	category = 0;
-	CuAssertTrue (cu, p11_index_find (test.index, match) == 0);
+	CuAssertTrue (cu, p11_index_find (test.index, match, -1) == 0);
 
 	/* Add a stapled basic constraint */
 	rv = p11_index_add (test.index, stapled, 4, NULL);
@@ -1543,7 +1543,7 @@ test_changed_staple_ca (CuTest *cu)
 
 	/* Now should be a CA */
 	category = 2;
-	CuAssertTrue (cu, p11_index_find (test.index, match) != 0);
+	CuAssertTrue (cu, p11_index_find (test.index, match, -1) != 0);
 
 	p11_attrs_free (attrs);
 
@@ -1604,7 +1604,7 @@ test_changed_staple_ku (CuTest *cu)
 	CuAssertIntEquals (cu, CKR_OK, rv);
 	p11_index_finish (test.index);
 
-	handle = p11_index_findn (test.index, nss_trust_ds_and_np, 2);
+	handle = p11_index_find (test.index, nss_trust_ds_and_np, 2);
 	CuAssertTrue (cu, handle != 0);
 
 	attrs = p11_index_lookup (test.index, handle);
diff --git a/trust/tests/test-index.c b/trust/tests/test-index.c
index 34e5842..3cda272 100644
--- a/trust/tests/test-index.c
+++ b/trust/tests/test-index.c
@@ -403,22 +403,22 @@ test_find (CuTest *tc)
 	p11_index_add (test.index, second, 2, &two);
 	p11_index_add (test.index, third, 2, &three);
 
-	check = p11_index_find (test.index, match3);
+	check = p11_index_find (test.index, match3, -1);
 	CuAssertIntEquals (tc, three, check);
 
-	check = p11_index_findn (test.index, match3, 1);
+	check = p11_index_find (test.index, match3, 1);
 	CuAssertIntEquals (tc, three, check);
 
-	check = p11_index_find (test.index, match_any);
+	check = p11_index_find (test.index, match_any, -1);
 	CuAssertTrue (tc, check == one || check == two || check == three);
 
-	check = p11_index_findn (test.index, match_any, 1);
+	check = p11_index_find (test.index, match_any, 1);
 	CuAssertTrue (tc, check == one || check == two || check == three);
 
-	check = p11_index_find (test.index, match_none);
+	check = p11_index_find (test.index, match_none, -1);
 	CuAssertIntEquals (tc, 0, check);
 
-	check = p11_index_findn (test.index, match_none, 2);
+	check = p11_index_find (test.index, match_none, 2);
 	CuAssertIntEquals (tc, 0, check);
 
 	teardown (tc);
@@ -517,23 +517,23 @@ test_find_all (CuTest *tc)
 	p11_index_add (test.index, second, 3, &two);
 	p11_index_add (test.index, third, 3, &three);
 
-	check = p11_index_find_all (test.index, match_3);
+	check = p11_index_find_all (test.index, match_3, -1);
 	CuAssertTrue (tc, handles_are (check, three, 0UL));
 	free (check);
 
-	check = p11_index_find_all (test.index, match_none);
+	check = p11_index_find_all (test.index, match_none, -1);
 	CuAssertTrue (tc, handles_are (check, 0UL));
 	free (check);
 
-	check = p11_index_find_all (test.index, match_odd);
+	check = p11_index_find_all (test.index, match_odd, -1);
 	CuAssertTrue (tc, handles_are (check, one, three, 0UL));
 	free (check);
 
-	check = p11_index_find_all (test.index, match_any);
+	check = p11_index_find_all (test.index, match_any, -1);
 	CuAssertTrue (tc, handles_are (check, one, two, three, 0UL));
 	free (check);
 
-	check = p11_index_find_all (test.index, match_none);
+	check = p11_index_find_all (test.index, match_none, -1);
 	CuAssertPtrNotNull (tc, check);
 	CuAssertIntEquals (tc, 0, check[0]);
 	free (check);
@@ -567,7 +567,7 @@ test_find_realloc (CuTest *tc)
 	for (i = 0; i < 1000; i++)
 		p11_index_add (test.index, attrs, 3, NULL);
 
-	check = p11_index_find_all (test.index, match);
+	check = p11_index_find_all (test.index, match, -1);
 	CuAssertPtrNotNull (tc, check);
 
 	for (i = 0; i < 1000; i++)
@@ -665,27 +665,27 @@ test_replace_all (CuTest *tc)
 	CuAssertIntEquals (tc, 0, array->num);
 
 	/* eins should have replaced one */
-	check = p11_index_find (test.index, eins);
+	check = p11_index_find (test.index, eins, -1);
 	CuAssertIntEquals (tc, one, check);
 
 	/* two should still be around */
-	check = p11_index_find (test.index, second);
+	check = p11_index_find (test.index, second, -1);
 	CuAssertIntEquals (tc, two, check);
 
 	/* three should have been removed */
-	check = p11_index_find (test.index, third);
+	check = p11_index_find (test.index, third, -1);
 	CuAssertIntEquals (tc, 0, check);
 
 	/* five should have been removed */
-	check = p11_index_find (test.index, fifth);
+	check = p11_index_find (test.index, fifth, -1);
 	CuAssertIntEquals (tc, 0, check);
 
 	/* sieben should have been added */
-	check = p11_index_find (test.index, sieben);
+	check = p11_index_find (test.index, sieben, -1);
 	CuAssertTrue (tc, check != one && check != two && check != three && check != five);
 
 	/* neun should have been added */
-	check = p11_index_find (test.index, neun);
+	check = p11_index_find (test.index, neun, -1);
 	CuAssertTrue (tc, check != one && check != two && check != three && check != five);
 
 	CuAssertIntEquals (tc, 4, p11_index_size (test.index));
diff --git a/trust/tests/test-parser.c b/trust/tests/test-parser.c
index 7998d97..4c182a0 100644
--- a/trust/tests/test-parser.c
+++ b/trust/tests/test-parser.c
@@ -88,7 +88,7 @@ static CK_ATTRIBUTE *
 parsed_attrs (CK_ATTRIBUTE *match)
 {
 	CK_OBJECT_HANDLE handle;
-	handle = p11_index_find (test.index, certificate_match);
+	handle = p11_index_find (test.index, certificate_match, -1);
 	return p11_index_lookup (test.index, handle);
 
 }
@@ -247,7 +247,7 @@ test_parse_openssl_trusted (CuTest *cu)
 
 	/* The other objects */
 	for (i = 1; expected[i]; i++) {
-		handle = p11_index_findn (test.index, expected[i], 2);
+		handle = p11_index_find (test.index, expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 
 		object = p11_index_lookup (test.index, handle);
@@ -322,7 +322,7 @@ test_parse_openssl_distrusted (CuTest *cu)
 
 	/* The other objects */
 	for (i = 1; expected[i]; i++) {
-		handle = p11_index_findn (test.index, expected[i], 2);
+		handle = p11_index_find (test.index, expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 
 		object = p11_index_lookup (test.index, handle);
diff --git a/trust/tests/test-token.c b/trust/tests/test-token.c
index ebe434d..6cf687b 100644
--- a/trust/tests/test-token.c
+++ b/trust/tests/test-token.c
@@ -185,7 +185,7 @@ test_token_flags (CuTest *cu)
 
 	/* The other objects */
 	for (i = 0; expected[i]; i++) {
-		handle = p11_index_findn (p11_token_index (test.token), expected[i], 2);
+		handle = p11_index_find (p11_token_index (test.token), expected[i], 2);
 		CuAssertTrue (cu, handle != 0);
 
 		object = p11_index_lookup (p11_token_index (test.token), handle);