trust: Refactor to include concept of the index

 * The index holds PKCS#11 objects whether for the token or for the session.
 * The index provides hook for a builder to expand or validate objects
   being added to the index.
 * In addition theres a change hook so that a builder can maintain state
   between objects, such as the compat NSS trust objects.

https://bugs.freedesktop.org/show_bug.cgi?id=62329

14 files changed, 2097 insertions, 384 deletions

diff --git a/trust/Makefile.am b/trust/Makefile.am
index 86bbab4..af4d327 100644
--- a/trust/Makefile.am
+++ b/trust/Makefile.am
@@ -12,6 +12,7 @@ INCLUDES = \
 
 MODULE_SRCS = \
 	adapter.c adapter.h \
+	index.c index.h \
 	parser.c parser.h \
 	module.c module.h \
 	session.c session.h \
diff --git a/trust/index.c b/trust/index.c
new file mode 100644
index 0000000..eb6ca7f
--- /dev/null
+++ b/trust/index.c
@@ -0,0 +1,566 @@
+/*
+ * 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 "compat.h"
+
+#define P11_DEBUG_FLAG P11_DEBUG_TRUST
+
+#include "attrs.h"
+#include "debug.h"
+#include "dict.h"
+#include "index.h"
+#include "module.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+/*
+ * TODO: Eventually we want to be using a bloom filter to optimize and
+ * actually implement the index.
+ */
+
+struct _p11_index {
+	/* The list of objects */
+	p11_dict *objects;
+
+	/* Data passed to callbacks */
+	void *data;
+
+	/* Called to build an new/modified object */
+	p11_index_build_cb build;
+
+	/* Called after objects change */
+	p11_index_changed_cb changed;
+
+	/* Used for queueing changes, when in a batch */
+	p11_dict *changes;
+	bool changing;
+};
+
+struct object {
+	CK_OBJECT_HANDLE handle;
+	CK_ATTRIBUTE *attrs;
+};
+
+static void
+free_object (void *data)
+{
+	struct 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,
+               void *data)
+{
+	p11_index *index;
+
+	index = calloc (1, sizeof (p11_index));
+	return_val_if_fail (index != NULL, NULL);
+
+	index->build = build;
+	index->changed = changed;
+	index->data = data;
+
+	index->objects = p11_dict_new (p11_dict_ulongptr_hash,
+	                               p11_dict_ulongptr_equal,
+	                               NULL, free_object);
+	return_val_if_fail (index->objects != NULL, NULL);
+
+	return index;
+}
+
+void
+p11_index_free (p11_index *index)
+{
+	return_if_fail (index != NULL);
+
+	p11_dict_free (index->objects);
+	p11_dict_free (index->changes);
+	free (index);
+}
+
+int
+p11_index_size (p11_index *index)
+{
+	return_val_if_fail (index != NULL, -1);
+	return p11_dict_size (index->objects);
+}
+
+static CK_RV
+index_build (p11_index *index,
+             CK_ATTRIBUTE **attrs,
+             CK_ATTRIBUTE *merge)
+{
+	if (index->build) {
+		return index->build (index->data, index, attrs, merge);
+	} else {
+		*attrs = p11_attrs_merge (*attrs, merge, true);
+		return CKR_OK;
+	}
+}
+
+static void
+call_change (p11_index *index,
+             CK_OBJECT_HANDLE handle,
+             CK_ATTRIBUTE *attrs)
+{
+	assert (index->changed);
+
+	/* When attrs is NULL, means this is a modify */
+	if (attrs == NULL) {
+		attrs = p11_index_lookup (index, handle);
+		if (attrs == NULL)
+			return;
+
+	/* Otherwise a remove operation, handle not valid anymore */
+	} else {
+		handle = 0;
+	}
+
+	index->changing = true;
+	index->changed (index->data, index, handle, attrs);
+	index->changing = false;
+}
+
+static void
+index_change (p11_index *index,
+              CK_OBJECT_HANDLE handle,
+              CK_ATTRIBUTE *removed)
+{
+	struct object *obj;
+
+	if (!index->changed || index->changing)
+		return;
+
+	if (!index->changes) {
+		call_change (index, handle, removed);
+		p11_attrs_free (removed);
+
+	} else {
+		obj = calloc (1, sizeof (struct object));
+		return_if_fail (obj != NULL);
+
+		obj->handle = handle;
+		obj->attrs = removed;
+		if (!p11_dict_set (index->changes, &obj->handle, obj))
+			return_if_reached ();
+	}
+}
+
+void
+p11_index_batch (p11_index *index)
+{
+	return_if_fail (index != NULL);
+
+	if (index->changes)
+		return;
+
+	index->changes = p11_dict_new (p11_dict_ulongptr_hash,
+	                               p11_dict_ulongptr_equal,
+	                               NULL, free_object);
+	return_if_fail (index->changes != NULL);
+}
+
+void
+p11_index_finish (p11_index *index)
+{
+	p11_dict *changes;
+	struct object *obj;
+	p11_dictiter iter;
+
+	return_if_fail (index != NULL);
+
+	if (!index->changes)
+		return;
+
+	changes = index->changes;
+	index->changes = NULL;
+
+	p11_dict_iterate (changes, &iter);
+	while (p11_dict_next (&iter, NULL, (void **)&obj))
+		call_change (index, obj->handle, obj->attrs);
+
+	p11_dict_free (changes);
+}
+
+bool
+p11_index_in_batch (p11_index *index)
+{
+	return_val_if_fail (index != NULL, false);
+	return index->changes ? true : false;
+}
+
+CK_RV
+p11_index_take (p11_index *index,
+                CK_ATTRIBUTE *attrs,
+                CK_OBJECT_HANDLE *handle)
+{
+	struct 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));
+	return_val_if_fail (obj != NULL, CKR_HOST_MEMORY);
+
+	rv = index_build (index, &obj->attrs, attrs);
+	if (rv != CKR_OK) {
+		p11_attrs_free (attrs);
+		return rv;
+	}
+
+	return_val_if_fail (obj->attrs != NULL, CKR_GENERAL_ERROR);
+	obj->handle = p11_module_next_id ();
+
+	if (!p11_dict_set (index->objects, &obj->handle, obj))
+		return_val_if_reached (CKR_HOST_MEMORY);
+
+	if (handle)
+		*handle = obj->handle;
+
+	index_change (index, obj->handle, NULL);
+	return CKR_OK;
+}
+
+CK_RV
+p11_index_add (p11_index *index,
+               CK_ATTRIBUTE *attrs,
+               CK_ULONG count,
+               CK_OBJECT_HANDLE *handle)
+{
+	CK_ATTRIBUTE *copy;
+
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+	return_val_if_fail (attrs == NULL || count > 0, CKR_ARGUMENTS_BAD);
+
+	copy = p11_attrs_buildn (NULL, attrs, count);
+	return_val_if_fail (copy != NULL, CKR_HOST_MEMORY);
+
+	return p11_index_take (index, copy, handle);
+}
+
+CK_RV
+p11_index_update (p11_index *index,
+                  CK_OBJECT_HANDLE handle,
+                  CK_ATTRIBUTE *update)
+{
+	struct object *obj;
+	CK_RV rv;
+
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+	return_val_if_fail (update != NULL, CKR_GENERAL_ERROR);
+
+	obj = p11_dict_get (index->objects, &handle);
+	if (obj == NULL) {
+		p11_attrs_free (update);
+		return CKR_OBJECT_HANDLE_INVALID;
+	}
+
+	rv = index_build (index, &obj->attrs, update);
+	if (rv != CKR_OK) {
+		p11_attrs_free (update);
+		return rv;
+	}
+
+	index_change (index, obj->handle, NULL);
+	return CKR_OK;
+}
+
+CK_RV
+p11_index_set (p11_index *index,
+               CK_OBJECT_HANDLE handle,
+               CK_ATTRIBUTE *attrs,
+               CK_ULONG count)
+{
+	CK_ATTRIBUTE *update;
+	struct object *obj;
+
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+
+	obj = p11_dict_get (index->objects, &handle);
+	if (obj == NULL)
+		return CKR_OBJECT_HANDLE_INVALID;
+
+	update = p11_attrs_buildn (NULL, attrs, count);
+	return_val_if_fail (update != NULL, CKR_HOST_MEMORY);
+
+	return p11_index_update (index, handle, update);
+}
+
+CK_RV
+p11_index_remove (p11_index *index,
+                  CK_OBJECT_HANDLE handle)
+{
+	struct object *obj;
+
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+
+	if (!p11_dict_steal (index->objects, &handle, NULL, (void **)&obj))
+		return CKR_OBJECT_HANDLE_INVALID;
+
+	/* This takes ownership of the attributes */
+	index_change (index, handle, obj->attrs);
+	obj->attrs = NULL;
+	free_object (obj);
+
+	return CKR_OK;
+}
+
+static CK_RV
+index_replacev (p11_index *index,
+                CK_ATTRIBUTE *match,
+                CK_ATTRIBUTE_TYPE key,
+                CK_ATTRIBUTE **replace,
+                CK_ULONG replacen)
+{
+	CK_OBJECT_HANDLE *handles;
+	struct 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)
+			continue;
+
+		handled = false;
+		attr = p11_attrs_find_valid (obj->attrs, key);
+
+		/* The match doesn't have the key, so remove it */
+		if (attr != NULL) {
+			for (j = 0; j < replacen; j++) {
+				if (!replace[j])
+					continue;
+				if (p11_attrs_matchn (replace[j], attr, 1)) {
+					attrs = NULL;
+					rv = index_build (index, &attrs, replace[j]);
+					if (rv != CKR_OK)
+						return rv;
+					p11_attrs_free (obj->attrs);
+					obj->attrs = attrs;
+					replace[j] = NULL;
+					handled = true;
+					break;
+				}
+			}
+		}
+
+		if (!handled) {
+			rv = p11_index_remove (index, handles[i]);
+			if (rv != CKR_OK)
+				return rv;
+		}
+	}
+
+	for (j = 0; j < replacen; j++) {
+		if (!replace[j])
+			continue;
+		rv = p11_index_take (index, replace[j], NULL);
+		if (rv != CKR_OK)
+			return rv;
+		replace[j] = NULL;
+	}
+
+	free (handles);
+	return CKR_OK;
+}
+
+CK_RV
+p11_index_replace (p11_index *index,
+                   CK_ATTRIBUTE *match,
+                   CK_ATTRIBUTE_TYPE key,
+                   CK_ATTRIBUTE *replace)
+{
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+	return index_replacev (index, match, key, &replace, 1);
+}
+
+CK_RV
+p11_index_replace_all (p11_index *index,
+                       CK_ATTRIBUTE *match,
+                       CK_ATTRIBUTE_TYPE key,
+                       p11_array *replace)
+{
+	CK_RV rv;
+	int i;
+
+	return_val_if_fail (index != NULL, CKR_GENERAL_ERROR);
+
+	rv = index_replacev (index, match, key,
+	                     (CK_ATTRIBUTE **)replace->elem,
+	                     replace->num);
+
+	for (i = 0; i < replace->num; i++) {
+		if (!replace->elem[i]) {
+			p11_array_remove (replace, i);
+			i--;
+		}
+	}
+
+	return rv;
+}
+
+CK_ATTRIBUTE *
+p11_index_lookup (p11_index *index,
+                  CK_OBJECT_HANDLE handle)
+{
+	struct object *obj;
+
+	return_val_if_fail (index != NULL, NULL);
+
+	if (handle == CK_INVALID_HANDLE)
+		return NULL;
+
+	obj = p11_dict_get (index->objects, &handle);
+	return obj ? obj->attrs : NULL;
+}
+
+CK_OBJECT_HANDLE
+p11_index_find (p11_index *index,
+                CK_ATTRIBUTE *match)
+{
+	struct object *obj;
+	p11_dictiter iter;
+
+	p11_dict_iterate (index->objects, &iter);
+	while (p11_dict_next (&iter, NULL, (void *)&obj)) {
+		if (p11_attrs_match (obj->attrs, match))
+			return obj->handle;
+	}
+
+	return 0;
+}
+
+CK_OBJECT_HANDLE
+p11_index_findn (p11_index *index,
+                 CK_ATTRIBUTE *match,
+                 CK_ULONG count)
+{
+	struct object *obj;
+	p11_dictiter iter;
+
+	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 0;
+}
+
+CK_OBJECT_HANDLE *
+p11_index_find_all (p11_index *index,
+                    CK_ATTRIBUTE *match)
+{
+	CK_OBJECT_HANDLE *handles = NULL;
+	struct object *obj;
+	p11_dictiter iter;
+	int nhandles;
+	int at = 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;
+		}
+	}
+
+	handles[at++] = 0UL;
+	return handles;
+}
+
+CK_OBJECT_HANDLE *
+p11_index_snapshot (p11_index *index,
+                    p11_index *base,
+                    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.
+	 */
+
+	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 (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);
+
+	return snapshot;
+}
diff --git a/trust/index.h b/trust/index.h
new file mode 100644
index 0000000..67d0746
--- /dev/null
+++ b/trust/index.h
@@ -0,0 +1,126 @@
+/*
+ * 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>
+ */
+
+#ifndef P11_INDEX_H_
+#define P11_INDEX_H_
+
+#include "array.h"
+#include "compat.h"
+#include "pkcs11.h"
+
+/*
+ * A boolean value which denotes whether we auto generated
+ * this object, as opposed to coming from outside the builder.
+ *
+ * We set this on all objects. It will always be either CK_TRUE
+ * or CK_FALSE for all objects built by this builder.
+ */
+#define CKA_X_GENERATED (CKA_X_VENDOR + 8000)
+
+typedef struct _p11_index p11_index;
+
+typedef CK_RV   (* p11_index_build_cb)   (void *data,
+                                          p11_index *index,
+                                          CK_ATTRIBUTE **attrs,
+                                          CK_ATTRIBUTE *merge);
+
+typedef void    (* p11_index_changed_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,
+                                          void *data);
+
+void               p11_index_free        (p11_index *index);
+
+int                p11_index_size        (p11_index *index);
+
+void               p11_index_batch       (p11_index *index);
+
+void               p11_index_finish      (p11_index *index);
+
+bool               p11_index_in_batch    (p11_index *index);
+
+CK_RV              p11_index_take        (p11_index *index,
+                                          CK_ATTRIBUTE *attrs,
+                                          CK_OBJECT_HANDLE *handle);
+
+CK_RV              p11_index_add         (p11_index *index,
+                                          CK_ATTRIBUTE *attrs,
+                                          CK_ULONG count,
+                                          CK_OBJECT_HANDLE *handle);
+
+CK_RV              p11_index_set         (p11_index *index,
+                                          CK_OBJECT_HANDLE handle,
+                                          CK_ATTRIBUTE *attrs,
+                                          CK_ULONG count);
+
+CK_RV              p11_index_update      (p11_index *index,
+                                          CK_OBJECT_HANDLE handle,
+                                          CK_ATTRIBUTE *attrs);
+
+CK_RV              p11_index_replace     (p11_index *index,
+                                          CK_ATTRIBUTE *match,
+                                          CK_ATTRIBUTE_TYPE key,
+                                          CK_ATTRIBUTE *replace);
+
+CK_RV              p11_index_replace_all (p11_index *index,
+                                          CK_ATTRIBUTE *match,
+                                          CK_ATTRIBUTE_TYPE key,
+                                          p11_array *replace);
+
+CK_RV              p11_index_remove      (p11_index *index,
+                                          CK_OBJECT_HANDLE handle);
+
+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);
+
+CK_OBJECT_HANDLE * p11_index_find_all    (p11_index *index,
+                                          CK_ATTRIBUTE *match);
+
+CK_OBJECT_HANDLE * p11_index_snapshot    (p11_index *index,
+                                          p11_index *base,
+                                          CK_ATTRIBUTE *attrs,
+                                          CK_ULONG count);
+
+#endif /* P11_INDEX_H_ */
diff --git a/trust/module.c b/trust/module.c
index a39c204..dcf4e8f 100644
--- a/trust/module.c
+++ b/trust/module.c
@@ -104,6 +104,33 @@ lookup_session (CK_SESSION_HANDLE handle,
 	return CKR_OK;
 }
 
+static CK_ATTRIBUTE *
+lookup_object_inlock (p11_session *session,
+                      CK_OBJECT_HANDLE handle,
+                      p11_index **index)
+{
+	CK_ATTRIBUTE *attrs;
+
+	assert (session != NULL);
+
+	attrs = p11_index_lookup (session->index, handle);
+	if (attrs) {
+		if (index)
+			*index = session->index;
+		return attrs;
+	}
+
+	attrs = p11_index_lookup (p11_token_index (session->token), handle);
+	if (attrs) {
+		if (index)
+			*index = p11_token_index (session->token);
+		return attrs;
+	}
+
+	return NULL;
+}
+
+
 static CK_RV
 lookup_slot_inlock (CK_SLOT_ID id,
                     p11_token **token)
@@ -803,7 +830,6 @@ sys_C_CreateObject (CK_SESSION_HANDLE handle,
                     CK_ULONG count,
                     CK_OBJECT_HANDLE_PTR new_object)
 {
-	CK_ATTRIBUTE *attrs;
 	p11_session *session;
 	CK_BBOOL token;
 	CK_RV rv;
@@ -820,10 +846,8 @@ sys_C_CreateObject (CK_SESSION_HANDLE handle,
 				rv = CKR_TOKEN_WRITE_PROTECTED;
 		}
 
-		if (rv == CKR_OK) {
-			attrs = p11_attrs_buildn (NULL, template, count);
-			rv = p11_session_add_object (session, attrs, new_object);
-		}
+		if (rv == CKR_OK)
+			rv = p11_index_add (session->index, template, count, new_object);
 
 	p11_unlock ();
 
@@ -855,7 +879,7 @@ sys_C_CopyObject (CK_SESSION_HANDLE handle,
 
 		rv = lookup_session (handle, &session);
 		if (rv == CKR_OK) {
-			original = p11_session_get_object (session, object, NULL);
+			original = lookup_object_inlock (session, object, NULL);
 			if (original == NULL)
 				rv = CKR_OBJECT_HANDLE_INVALID;
 		}
@@ -869,7 +893,7 @@ sys_C_CopyObject (CK_SESSION_HANDLE handle,
 			attrs = p11_attrs_dup (original);
 			attrs = p11_attrs_buildn (attrs, template, count);
 			attrs = p11_attrs_build (attrs, &token, NULL);
-			rv = p11_session_add_object (session, attrs, new_object);
+			rv = p11_index_take (session->index, attrs, new_object);
 		}
 
 	p11_unlock ();
@@ -891,8 +915,13 @@ sys_C_DestroyObject (CK_SESSION_HANDLE handle,
 	p11_lock ();
 
 		rv = lookup_session (handle, &session);
-		if (rv == CKR_OK)
-			rv = p11_session_del_object (session, object);
+		if (rv == CKR_OK) {
+			rv = p11_index_remove (session->index, object);
+			if (rv == CKR_OBJECT_HANDLE_INVALID) {
+				if (p11_index_lookup (p11_token_index (session->token), object))
+					rv = CKR_TOKEN_WRITE_PROTECTED;
+			}
+		}
 
 	p11_unlock ();
 
@@ -917,7 +946,7 @@ sys_C_GetObjectSize (CK_SESSION_HANDLE handle,
 
 		rv = lookup_session (handle, &session);
 		if (rv == CKR_OK) {
-			if (p11_session_get_object (session, object, NULL)) {
+			if (lookup_object_inlock (session, object, NULL)) {
 				*size = CK_UNAVAILABLE_INFORMATION;
 				rv = CKR_OK;
 			} else {
@@ -951,7 +980,7 @@ sys_C_GetAttributeValue (CK_SESSION_HANDLE handle,
 
 		rv = lookup_session (handle, &session);
 		if (rv == CKR_OK) {
-			attrs = p11_session_get_object (session, object, NULL);
+			attrs = lookup_object_inlock (session, object, NULL);
 			if (attrs == NULL)
 				rv = CKR_OBJECT_HANDLE_INVALID;
 		}
@@ -1003,8 +1032,13 @@ sys_C_SetAttributeValue (CK_SESSION_HANDLE handle,
 	p11_lock ();
 
 		rv = lookup_session (handle, &session);
-		if (rv == CKR_OK)
-			rv = p11_session_set_object (session, object, template, count);
+		if (rv == CKR_OK) {
+			rv = p11_index_set (session->index, object, template, count);
+			if (rv == CKR_OBJECT_HANDLE_INVALID) {
+				if (p11_index_lookup (p11_token_index (session->token), object))
+					rv = CKR_TOKEN_WRITE_PROTECTED;
+			}
+		}
 
 	p11_unlock ();
 
@@ -1018,16 +1052,14 @@ sys_C_FindObjectsInit (CK_SESSION_HANDLE handle,
                        CK_ATTRIBUTE_PTR template,
                        CK_ULONG count)
 {
-	CK_OBJECT_HANDLE *handle_ptr;
+	p11_index *indices[2] = { NULL, NULL };
 	CK_BBOOL want_token_objects;
 	CK_BBOOL want_session_objects;
 	CK_BBOOL token;
-	p11_dict *objects;
 	FindObjects *find;
 	p11_session *session;
-	p11_dictiter iter;
-	CK_ULONG i;
 	CK_RV rv;
+	int n = 0;
 
 	p11_debug ("in");
 
@@ -1045,52 +1077,30 @@ sys_C_FindObjectsInit (CK_SESSION_HANDLE handle,
 		rv = lookup_session (handle, &session);
 
 		/* Refresh from disk if this session hasn't yet */
-		if (rv == CKR_OK && want_token_objects && !session->loaded) {
-			session->loaded = CK_TRUE;
-			p11_token_load (session->token);
-		}
-
 		if (rv == CKR_OK) {
-			objects = p11_token_objects (session->token);
+			if (want_session_objects)
+				indices[n++] = session->index;
+			if (want_token_objects) {
+				if (!session->loaded)
+					p11_token_load (session->token);
+				session->loaded = CK_TRUE;
+				indices[n++] = p11_token_index (session->token);
+			}
 
 			find = calloc (1, sizeof (FindObjects));
 			warn_if_fail (find != NULL);
 
-			/* Make a copy of what we're matching */
+			/* Make a snapshot of what we're matching */
 			if (find) {
 				find->match = p11_attrs_buildn (NULL, template, count);
 				warn_if_fail (find->match != NULL);
 
 				/* Build a session snapshot of all objects */
 				find->iterator = 0;
-				count = p11_dict_size (objects) + p11_dict_size (session->objects) + 1;
-				find->snapshot = calloc (count, sizeof (CK_OBJECT_HANDLE));
+				find->snapshot = p11_index_snapshot (indices[0], indices[1], template, count);
 				warn_if_fail (find->snapshot != NULL);
 			}
 
-			if (find && find->snapshot) {
-				i = 0;
-
-				if (want_token_objects) {
-					p11_dict_iterate (objects, &iter);
-					for ( ; p11_dict_next (&iter, (void *)&handle_ptr, NULL); i++) {
-						assert (i < count);
-						find->snapshot[i] = *handle_ptr;
-					}
-				}
-
-				if (want_session_objects) {
-					p11_dict_iterate (session->objects, &iter);
-					for ( ; p11_dict_next (&iter, (void *)&handle_ptr, NULL); i++) {
-						assert (i < count);
-						find->snapshot[i] = *handle_ptr;
-					}
-				}
-
-				assert (i < count);
-				assert (find->snapshot[i] == 0UL);
-			}
-
 			if (!find || !find->snapshot || !find->match)
 				rv = CKR_HOST_MEMORY;
 			else
@@ -1115,6 +1125,7 @@ sys_C_FindObjects (CK_SESSION_HANDLE handle,
 	FindObjects *find = NULL;
 	p11_session *session;
 	CK_ULONG matched;
+	p11_index *index;
 	CK_RV rv;
 
 	return_val_if_fail (count != NULL, CKR_ARGUMENTS_BAD);
@@ -1139,7 +1150,7 @@ sys_C_FindObjects (CK_SESSION_HANDLE handle,
 
 				find->iterator++;
 
-				attrs = p11_session_get_object (session, object, NULL);
+				attrs = lookup_object_inlock (session, object, &index);
 				if (attrs == NULL)
 					continue;
 
diff --git a/trust/session.c b/trust/session.c
index 070364e..30928ed 100644
--- a/trust/session.c
+++ b/trust/session.c
@@ -48,19 +48,6 @@
 #include <stdlib.h>
 #include <string.h>
 
-typedef struct {
-	CK_OBJECT_HANDLE handle;
-	CK_ATTRIBUTE *attrs;
-} Object;
-
-static void
-object_free (void *data)
-{
-	Object *object = data;
-	p11_attrs_free (object->attrs);
-	free (object);
-}
-
 p11_session *
 p11_session_new (p11_token *token)
 {
@@ -71,10 +58,8 @@ p11_session_new (p11_token *token)
 
 	session->handle = p11_module_next_id ();
 
-	session->objects =  p11_dict_new (p11_dict_ulongptr_hash,
-	                                  p11_dict_ulongptr_equal,
-	                                  NULL, object_free);
-	return_val_if_fail (session->objects != NULL, NULL);
+	session->index = p11_index_new (NULL, NULL, NULL);
+	return_val_if_fail (session->index != NULL, NULL);
 
 	session->token = token;
 
@@ -87,111 +72,11 @@ p11_session_free (void *data)
 	p11_session *session = data;
 
 	p11_session_set_operation (session, NULL, NULL);
-	p11_dict_free (session->objects);
+	p11_index_free (session->index);
 
 	free (session);
 }
 
-CK_RV
-p11_session_add_object (p11_session *session,
-                        CK_ATTRIBUTE *attrs,
-                        CK_OBJECT_HANDLE *handle)
-{
-	Object *object;
-
-	assert (handle != NULL);
-	assert (session != NULL);
-
-	return_val_if_fail (attrs != NULL, CKR_GENERAL_ERROR);
-
-	object = malloc (sizeof (Object));
-	return_val_if_fail (object != NULL, CKR_HOST_MEMORY);
-
-	object->handle = p11_module_next_id ();
-	object->attrs = attrs;
-
-	if (!p11_dict_set (session->objects, &object->handle, object))
-		return_val_if_reached (CKR_HOST_MEMORY);
-
-	*handle = object->handle;
-	return CKR_OK;
-}
-
-CK_RV
-p11_session_del_object (p11_session *session,
-                        CK_OBJECT_HANDLE handle)
-{
-	p11_dict *objects;
-
-	assert (session != NULL);
-
-	if (p11_dict_remove (session->objects, &handle))
-		return CKR_OK;
-
-	/* Look for in the global objects */
-	objects = p11_token_objects (session->token);
-	if (p11_dict_get (objects, &handle))
-		return CKR_TOKEN_WRITE_PROTECTED;
-
-	return CKR_OBJECT_HANDLE_INVALID;
-}
-
-CK_ATTRIBUTE *
-p11_session_get_object (p11_session *session,
-                        CK_OBJECT_HANDLE handle,
-                        CK_BBOOL *token)
-{
-	CK_ATTRIBUTE *attrs;
-	p11_dict *objects;
-	Object *object;
-
-	assert (session != NULL);
-
-	object = p11_dict_get (session->objects, &handle);
-	if (object) {
-		if (token)
-			*token = CK_FALSE;
-		return object->attrs;
-	}
-
-	objects = p11_token_objects (session->token);
-	attrs = p11_dict_get (objects, &handle);
-	if (attrs) {
-		if (token)
-			*token = CK_TRUE;
-		return attrs;
-	}
-
-	return NULL;
-}
-
-CK_RV
-p11_session_set_object (p11_session *session,
-                        CK_OBJECT_HANDLE handle,
-                        CK_ATTRIBUTE *template,
-                        CK_ULONG count)
-{
-	CK_BBOOL token;
-	p11_dict *objects;
-	Object *object;
-
-	assert (session != NULL);
-
-	object = p11_dict_get (session->objects, &handle);
-	if (object == NULL) {
-		objects = p11_token_objects (session->token);
-		if (p11_dict_get (objects, &handle))
-			return CKR_TOKEN_WRITE_PROTECTED;
-		return CKR_OBJECT_HANDLE_INVALID;
-	}
-
-	if (!p11_attrs_findn_bool (template, count, CKA_TOKEN, &token) && token)
-		return CKR_TEMPLATE_INCONSISTENT;
-
-	object->attrs = p11_attrs_buildn (object->attrs, template, count);
-	return CKR_OK;
-}
-
 void
 p11_session_set_operation (p11_session *session,
                            p11_session_cleanup cleanup,
diff --git a/trust/session.h b/trust/session.h
index 97aedb1..c2626d0 100644
--- a/trust/session.h
+++ b/trust/session.h
@@ -32,6 +32,7 @@
  * Author: Stef Walter <stefw@redhat.com>
  */
 
+#include "index.h"
 #include "pkcs11.h"
 #include "token.h"
 
@@ -42,7 +43,7 @@ typedef void (* p11_session_cleanup) (void *data);
 
 typedef struct {
 	CK_SESSION_HANDLE handle;
-	p11_dict *objects;
+	p11_index *index;
 	p11_token *token;
 	CK_BBOOL loaded;
 
@@ -55,22 +56,6 @@ p11_session *     p11_session_new           (p11_token *token);
 
 void              p11_session_free          (void *data);
 
-CK_RV             p11_session_add_object    (p11_session *session,
-                                             CK_ATTRIBUTE *attrs,
-                                             CK_OBJECT_HANDLE *handle);
-
-CK_RV             p11_session_del_object    (p11_session *session,
-                                             CK_OBJECT_HANDLE handle);
-
-CK_ATTRIBUTE *    p11_session_get_object    (p11_session *session,
-                                             CK_OBJECT_HANDLE handle,
-                                             CK_BBOOL *token);
-
-CK_RV             p11_session_set_object    (p11_session *session,
-                                             CK_OBJECT_HANDLE handle,
-                                             CK_ATTRIBUTE *template,
-                                             CK_ULONG count);
-
 void              p11_session_set_operation (p11_session *session,
                                              p11_session_cleanup cleanup,
                                              void *operation);
diff --git a/trust/tests/Makefile.am b/trust/tests/Makefile.am
index 4e9d75a..cdab991 100644
--- a/trust/tests/Makefile.am
+++ b/trust/tests/Makefile.am
@@ -27,8 +27,8 @@ LDADD = \
 
 CHECK_PROGS = \
 	test-parser \
+	test-index \
 	test-token \
-	test-session \
 	test-module \
 	$(NULL)
 
diff --git a/trust/tests/frob-token.c b/trust/tests/frob-token.c
index 976fb2b..622dad4 100644
--- a/trust/tests/frob-token.c
+++ b/trust/tests/frob-token.c
@@ -44,7 +44,7 @@ main (int argc,
       char *argv[])
 {
 	p11_token *token;
-	p11_dict *objects;
+	p11_index *index;
 	int count;
 
 	if (argc != 2) {
@@ -56,8 +56,8 @@ main (int argc,
 	count = p11_token_load (token);
 
 	printf ("%d files loaded\n", count);
-	objects = p11_token_objects (token);
-	printf ("%d objects loaded\n", p11_dict_size (objects));
+	index = p11_token_index (token);
+	printf ("%d objects loaded\n", p11_index_size (index));
 
 	p11_token_free (token);
 	return 0;
diff --git a/trust/tests/test-index.c b/trust/tests/test-index.c
new file mode 100644
index 0000000..34e5842
--- /dev/null
+++ b/trust/tests/test-index.c
@@ -0,0 +1,1063 @@
+/*
+ * Copyright (c) 2012 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@gnome.org>
+ */
+
+#include "config.h"
+#include "CuTest.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "attrs.h"
+#include "debug.h"
+#include "library.h"
+#include "index.h"
+
+#include "test-data.h"
+
+struct {
+	p11_index *index;
+} test;
+
+static void
+setup (CuTest *cu)
+{
+	test.index = p11_index_new (NULL, NULL, NULL);
+	CuAssertPtrNotNull (cu, test.index);
+}
+
+static void
+teardown (CuTest *cu)
+{
+	p11_index_free (test.index);
+	memset (&test, 0, sizeof (test));
+}
+
+static void
+test_take_lookup (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE *attrs;
+	CK_ATTRIBUTE *check;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	attrs = p11_attrs_dup (original);
+	rv = p11_index_take (test.index, attrs, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, original, check);
+
+	check = p11_index_lookup (test.index, 1UL);
+	CuAssertPtrEquals (cu, NULL, check);
+
+	check = p11_index_lookup (test.index, 0UL);
+	CuAssertPtrEquals (cu, NULL, check);
+
+	teardown (cu);
+}
+
+static void
+test_add_lookup (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE *check;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = p11_index_add (test.index, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, original, check);
+
+	teardown (cu);
+}
+
+static void
+test_size (CuTest *cu)
+{
+	static CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = p11_index_add (test.index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = p11_index_add (test.index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = p11_index_add (test.index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 3, p11_index_size (test.index));
+
+	teardown (cu);
+}
+
+static int
+compar_ulong (const void *one,
+              const void *two)
+{
+	const CK_ULONG *u1 = one;
+	const CK_ULONG *u2 = two;
+
+	if (*u1 == *u2)
+		return 0;
+	if (*u1 < *u2)
+		return -1;
+	return 1;
+}
+
+static void
+test_snapshot (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	static const int NUM = 16;
+	CK_OBJECT_HANDLE expected[NUM];
+	CK_OBJECT_HANDLE *snapshot;
+	int i;
+
+	setup (cu);
+
+	for (i = 0; i < NUM; i++)
+		p11_index_add (test.index, original, 2, expected + i);
+
+	snapshot = p11_index_snapshot (test.index, NULL, NULL, 0);
+	CuAssertPtrNotNull (cu, snapshot);
+
+	for (i = 0; i < NUM; i++)
+		CuAssertTrue (cu, snapshot[i] != 0);
+	CuAssertTrue (cu, snapshot[NUM] == 0);
+
+	qsort (snapshot, NUM, sizeof (CK_OBJECT_HANDLE), compar_ulong);
+
+	for (i = 0; i < NUM; i++)
+		CuAssertIntEquals (cu, expected[i], snapshot[i]);
+
+	teardown (cu);
+}
+
+static void
+test_snapshot_base (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	static const int NUM = 16;
+	CK_OBJECT_HANDLE expected[NUM];
+	CK_OBJECT_HANDLE *snapshot;
+	CK_RV rv;
+	int i;
+
+	setup (cu);
+
+	for (i = 0; i < NUM; i++) {
+		rv = p11_index_add (test.index, original, 2, expected + i);
+		CuAssertTrue (cu, rv == CKR_OK);
+	}
+
+	snapshot = p11_index_snapshot (test.index, test.index, NULL, 0);
+	CuAssertPtrNotNull (cu, snapshot);
+
+	for (i = 0; i < NUM * 2; i++)
+		CuAssertTrue (cu, snapshot[i] != 0);
+	CuAssertTrue (cu, snapshot[NUM * 2] == 0);
+
+	qsort (snapshot, NUM * 2, sizeof (CK_OBJECT_HANDLE), compar_ulong);
+
+	for (i = 0; i < NUM * 2; i++)
+		CuAssertIntEquals (cu, expected[i / 2], snapshot[i]);
+
+	teardown (cu);
+}
+
+static void
+test_remove (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE *attrs;
+	CK_ATTRIBUTE *check;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	attrs = p11_attrs_dup (original);
+	rv = p11_index_take (test.index, attrs, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	CuAssertPtrEquals (cu, attrs, check);
+
+	rv = p11_index_remove (test.index, 1UL);
+	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
+
+	rv = p11_index_remove (test.index, handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	CuAssertPtrEquals (cu, NULL, check);
+
+	teardown (cu);
+}
+
+static void
+test_set (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE change = { CKA_LABEL, "naay", 4 };
+
+	CK_ATTRIBUTE changed[] = {
+		{ CKA_LABEL, "naay", 4 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE *attrs;
+	CK_ATTRIBUTE *check;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	attrs = p11_attrs_dup (original);
+	rv = p11_index_take (test.index, attrs, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, original, check);
+
+	rv = p11_index_set (test.index, handle, &change, 1);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, changed, check);
+
+	rv = p11_index_set (test.index, 1UL, &change, 1);
+	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
+
+	teardown (cu);
+}
+
+static void
+test_update (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE change = { CKA_LABEL, "naay", 4 };
+
+	CK_ATTRIBUTE changed[] = {
+		{ CKA_LABEL, "naay", 4 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE *attrs;
+	CK_ATTRIBUTE *check;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	attrs = p11_attrs_dup (original);
+	rv = p11_index_take (test.index, attrs, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, original, check);
+
+	attrs = p11_attrs_build (NULL, &change, NULL);
+	rv = p11_index_update (test.index, handle, attrs);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (test.index, handle);
+	test_check_attrs (cu, changed, check);
+
+	attrs = p11_attrs_build (NULL, &change, NULL);
+	rv = p11_index_update (test.index, 1L, attrs);
+	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
+
+	teardown (cu);
+}
+
+static void
+test_find (CuTest *tc)
+{
+	CK_ATTRIBUTE first[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "one", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE second[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "two", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE third[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "three", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match3[] = {
+		{ CKA_VALUE, "three", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_any[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_none[] = {
+		{ CKA_VALUE, "blonononon", 10 },
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE check;
+	CK_OBJECT_HANDLE one;
+	CK_OBJECT_HANDLE two;
+	CK_OBJECT_HANDLE three;
+
+	setup (tc);
+
+	p11_index_add (test.index, first, 2, &one);
+	p11_index_add (test.index, second, 2, &two);
+	p11_index_add (test.index, third, 2, &three);
+
+	check = p11_index_find (test.index, match3);
+	CuAssertIntEquals (tc, three, check);
+
+	check = p11_index_findn (test.index, match3, 1);
+	CuAssertIntEquals (tc, three, check);
+
+	check = p11_index_find (test.index, match_any);
+	CuAssertTrue (tc, check == one || check == two || check == three);
+
+	check = p11_index_findn (test.index, match_any, 1);
+	CuAssertTrue (tc, check == one || check == two || check == three);
+
+	check = p11_index_find (test.index, match_none);
+	CuAssertIntEquals (tc, 0, check);
+
+	check = p11_index_findn (test.index, match_none, 2);
+	CuAssertIntEquals (tc, 0, check);
+
+	teardown (tc);
+}
+
+static bool
+handles_are (CK_OBJECT_HANDLE *handles,
+             ...)
+{
+	CK_OBJECT_HANDLE handle;
+	int count;
+	int num;
+	va_list va;
+	int i;
+
+	if (!handles)
+		return false;
+
+	/* Count number of handles */
+	for (num = 0; handles[num]; num++);
+
+	va_start (va, handles);
+
+	for (count = 0; true; count++) {
+		handle = va_arg (va, CK_OBJECT_HANDLE);
+		if (handle == 0)
+			break;
+
+		for (i = 0; handles[i]; i++) {
+			if (handle == handles[i])
+				break;
+		}
+
+		if (handles[i] != handle)
+			return false;
+	}
+
+	va_end (va);
+
+	return (count == num);
+}
+
+static void
+test_find_all (CuTest *tc)
+{
+	CK_ATTRIBUTE first[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "one", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE second[] = {
+		{ CKA_LABEL, "even", 4 },
+		{ CKA_VALUE, "two", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE third[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "three", 5 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_odd[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_3[] = {
+		{ CKA_VALUE, "three", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_any[] = {
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match_none[] = {
+		{ CKA_VALUE, "blonononon", 10 },
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE *check;
+	CK_OBJECT_HANDLE one;
+	CK_OBJECT_HANDLE two;
+	CK_OBJECT_HANDLE three;
+
+	setup (tc);
+
+	p11_index_add (test.index, first, 3, &one);
+	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);
+	CuAssertTrue (tc, handles_are (check, three, 0UL));
+	free (check);
+
+	check = p11_index_find_all (test.index, match_none);
+	CuAssertTrue (tc, handles_are (check, 0UL));
+	free (check);
+
+	check = p11_index_find_all (test.index, match_odd);
+	CuAssertTrue (tc, handles_are (check, one, three, 0UL));
+	free (check);
+
+	check = p11_index_find_all (test.index, match_any);
+	CuAssertTrue (tc, handles_are (check, one, two, three, 0UL));
+	free (check);
+
+	check = p11_index_find_all (test.index, match_none);
+	CuAssertPtrNotNull (tc, check);
+	CuAssertIntEquals (tc, 0, check[0]);
+	free (check);
+
+	/* A double check of this method */
+	CuAssertTrue (tc, !handles_are (check, 29292929, 0UL));
+	CuAssertTrue (tc, !handles_are (NULL, 0UL));
+
+	teardown (tc);
+}
+
+static void
+test_find_realloc (CuTest *tc)
+{
+	CK_ATTRIBUTE attrs[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "one", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match[] = {
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE *check;
+	int i;
+
+	setup (tc);
+
+	for (i = 0; i < 1000; i++)
+		p11_index_add (test.index, attrs, 3, NULL);
+
+	check = p11_index_find_all (test.index, match);
+	CuAssertPtrNotNull (tc, check);
+
+	for (i = 0; i < 1000; i++)
+		CuAssertTrue (tc, check[i] != 0);
+	CuAssertIntEquals (tc, 0, check[1000]);
+
+	free (check);
+	teardown (tc);
+}
+
+static void
+test_replace_all (CuTest *tc)
+{
+	CK_ATTRIBUTE first[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "one", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE second[] = {
+		{ CKA_LABEL, "even", 4 },
+		{ CKA_VALUE, "two", 3 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE third[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "three", 5 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE fifth[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "five", 4 },
+		{ CKA_APPLICATION, "test", 4 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE match[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE eins[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "one", 3 },
+		{ CKA_APPLICATION, "replace", 7 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE sieben[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "seven", 5 },
+		{ CKA_APPLICATION, "replace", 7 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE neun[] = {
+		{ CKA_LABEL, "odd", 3 },
+		{ CKA_VALUE, "nine", 4 },
+		{ CKA_APPLICATION, "replace", 7 },
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE check;
+	CK_OBJECT_HANDLE one;
+	CK_OBJECT_HANDLE two;
+	CK_OBJECT_HANDLE three;
+	CK_OBJECT_HANDLE five;
+	p11_array *array;
+	CK_RV rv;
+
+	setup (tc);
+
+	p11_index_add (test.index, first, 3, &one);
+	CuAssertTrue (tc, one != 0);
+	p11_index_add (test.index, second, 3, &two);
+	CuAssertTrue (tc, two != 0);
+	p11_index_add (test.index, third, 3, &three);
+	CuAssertTrue (tc, three != 0);
+	p11_index_add (test.index, fifth, 3, &five);
+	CuAssertTrue (tc, five != 0);
+
+	array = p11_array_new (p11_attrs_free);
+	p11_array_push (array, p11_attrs_buildn (NULL, eins, 3));
+	p11_array_push (array, p11_attrs_buildn (NULL, sieben, 3));
+	p11_array_push (array, p11_attrs_buildn (NULL, neun, 3));
+
+	rv = p11_index_replace_all (test.index, match, CKA_VALUE, array);
+	CuAssertTrue (tc, rv == CKR_OK);
+
+	CuAssertIntEquals (tc, 0, array->num);
+
+	/* eins should have replaced one */
+	check = p11_index_find (test.index, eins);
+	CuAssertIntEquals (tc, one, check);
+
+	/* two should still be around */
+	check = p11_index_find (test.index, second);
+	CuAssertIntEquals (tc, two, check);
+
+	/* three should have been removed */
+	check = p11_index_find (test.index, third);
+	CuAssertIntEquals (tc, 0, check);
+
+	/* five should have been removed */
+	check = p11_index_find (test.index, fifth);
+	CuAssertIntEquals (tc, 0, check);
+
+	/* sieben should have been added */
+	check = p11_index_find (test.index, sieben);
+	CuAssertTrue (tc, check != one && check != two && check != three && check != five);
+
+	/* neun should have been added */
+	check = p11_index_find (test.index, neun);
+	CuAssertTrue (tc, check != one && check != two && check != three && check != five);
+
+	CuAssertIntEquals (tc, 4, p11_index_size (test.index));
+
+	teardown (tc);
+}
+
+
+static CK_RV
+on_build_populate (void *data,
+                   p11_index *index,
+                   CK_ATTRIBUTE **attrs,
+                   CK_ATTRIBUTE *merge)
+{
+	CuTest *cu = data;
+
+	CK_ATTRIBUTE override[] = {
+		{ CKA_APPLICATION, "vigorous", 8 },
+		{ CKA_LABEL, "naay", 4 },
+		{ CKA_INVALID },
+	};
+
+	CuAssertPtrNotNull (cu, index);
+	CuAssertPtrNotNull (cu, attrs);
+	CuAssertPtrNotNull (cu, merge);
+
+	*attrs = p11_attrs_merge (*attrs, merge, true);
+	*attrs = p11_attrs_merge (*attrs, p11_attrs_dup (override), true);
+	return CKR_OK;
+}
+
+static void
+test_build_populate (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	CK_ATTRIBUTE after[] = {
+		{ CKA_LABEL, "naay", 4 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_APPLICATION, "vigorous", 8 },
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE handle;
+	CK_ATTRIBUTE *check;
+	p11_index *index;
+	CK_RV rv;
+
+	index = p11_index_new (on_build_populate, NULL, cu);
+	CuAssertPtrNotNull (cu, index);
+
+	rv = p11_index_add (index, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (index, handle);
+	CuAssertPtrNotNull (cu, check);
+
+	test_check_attrs (cu, after, check);
+
+	rv = p11_index_set (index, handle, original, 2);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	check = p11_index_lookup (index, handle);
+	CuAssertPtrNotNull (cu, check);
+
+	test_check_attrs (cu, after, check);
+
+	p11_index_free (index);
+}
+
+static CK_RV
+on_build_fail (void *data,
+               p11_index *index,
+               CK_ATTRIBUTE **attrs,
+               CK_ATTRIBUTE *merge)
+{
+	CuTest *cu = data;
+
+	CK_ATTRIBUTE check[] = {
+		{ CKA_LABEL, "nay", 3 },
+		{ CKA_INVALID }
+	};
+
+	CuAssertPtrNotNull (cu, merge);
+
+	if (p11_attrs_match (merge, check))
+		return CKR_DEVICE_ERROR;
+
+	*attrs = p11_attrs_merge (*attrs, merge, true);
+	return CKR_OK;
+}
+
+
+static void
+test_build_fail (CuTest *cu)
+{
+	CK_ATTRIBUTE okay[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_ATTRIBUTE fails[] = {
+		{ CKA_LABEL, "nay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_OBJECT_HANDLE handle;
+	p11_index *index;
+	CK_RV rv;
+
+	index = p11_index_new (on_build_fail, NULL, cu);
+	CuAssertPtrNotNull (cu, index);
+
+	rv = p11_index_add (index, okay, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = p11_index_add (index, fails, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_DEVICE_ERROR);
+
+	rv = p11_index_set (index, handle, fails, 2);
+	CuAssertTrue (cu, rv == CKR_DEVICE_ERROR);
+
+	rv = p11_index_set (index, handle, okay, 2);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	p11_index_free (index);
+}
+
+static int on_change_called = 0;
+static bool on_change_removing = false;
+static bool on_change_batching = false;
+
+static void
+on_change_check (void *data,
+                 p11_index *index,
+                 CK_OBJECT_HANDLE handle,
+                 CK_ATTRIBUTE *attrs)
+{
+	CuTest *cu = data;
+
+	CK_ATTRIBUTE check[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	CuAssertPtrNotNull (cu, index);
+	CuAssertPtrNotNull (cu, attrs);
+
+	if (!on_change_batching) {
+		if (on_change_removing)
+			CuAssertIntEquals (cu, 0, handle);
+		else
+			CuAssertTrue (cu, handle != 0);
+	}
+
+	test_check_attrs (cu, check, attrs);
+	on_change_called++;
+}
+
+static void
+test_change_called (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	CK_OBJECT_HANDLE handle;
+	p11_index *index;
+	CK_RV rv;
+
+	index = p11_index_new (NULL, on_change_check, cu);
+	CuAssertPtrNotNull (cu, index);
+
+	on_change_removing = false;
+	on_change_called = 0;
+
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 1, on_change_called);
+
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 2, on_change_called);
+
+	rv = p11_index_add (index, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 3, on_change_called);
+
+	on_change_removing = true;
+
+	rv = p11_index_remove (index, handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 4, on_change_called);
+
+	p11_index_free (index);
+}
+
+static void
+test_change_batch (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	CK_OBJECT_HANDLE handle;
+	p11_index *index;
+	CK_RV rv;
+
+	index = p11_index_new (NULL, on_change_check, cu);
+	CuAssertPtrNotNull (cu, index);
+
+	on_change_batching = true;
+	on_change_called = 0;
+
+	p11_index_batch (index);
+
+	CuAssertTrue (cu, p11_index_in_batch (index));
+
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 0, on_change_called);
+
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 0, on_change_called);
+
+	rv = p11_index_add (index, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 0, on_change_called);
+
+	/* Nested batch is a noop */
+	p11_index_batch (index);
+
+	rv = p11_index_remove (index, handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	CuAssertIntEquals (cu, 0, on_change_called);
+
+	/*
+	 * Batch finishes when first finish call is called,
+	 * even when batches are nested
+	 */
+	p11_index_finish (index);
+
+	CuAssertTrue (cu, !p11_index_in_batch (index));
+
+	/*
+	 * Only three calls, because later operations on the
+	 * same handle override the earlier one.
+	 */
+	CuAssertIntEquals (cu, 3, on_change_called);
+
+	/* This is a noop */
+	p11_index_finish (index);
+
+	CuAssertTrue (cu, !p11_index_in_batch (index));
+
+	p11_index_free (index);
+}
+
+static void
+on_change_nested (void *data,
+                  p11_index *index,
+                  CK_OBJECT_HANDLE handle,
+                  CK_ATTRIBUTE *attrs)
+{
+	CuTest *cu = data;
+	CK_RV rv;
+
+	CK_ATTRIBUTE second[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	on_change_called++;
+
+	/* A nested call */
+	rv = p11_index_add (index, second, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+}
+
+static void
+test_change_nested (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+
+	};
+
+	p11_index *index;
+	CK_RV rv;
+
+	index = p11_index_new (NULL, on_change_nested, cu);
+	CuAssertPtrNotNull (cu, index);
+
+	on_change_called = 0;
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+	CuAssertIntEquals (cu, 1, on_change_called);
+
+
+	on_change_called = 0;
+	p11_index_batch (index);
+	rv = p11_index_add (index, original, 2, NULL);
+	CuAssertTrue (cu, rv == CKR_OK);
+	p11_index_finish (index);
+	CuAssertIntEquals (cu, 1, on_change_called);
+}
+
+int
+main (void)
+{
+	CuString *output = CuStringNew ();
+	CuSuite* suite = CuSuiteNew ();
+	int ret;
+
+	putenv ("P11_KIT_STRICT=1");
+	p11_library_init ();
+	p11_debug_init ();
+	p11_message_quiet ();
+
+	SUITE_ADD_TEST (suite, test_add_lookup);
+	SUITE_ADD_TEST (suite, test_take_lookup);
+	SUITE_ADD_TEST (suite, test_size);
+	SUITE_ADD_TEST (suite, test_remove);
+	SUITE_ADD_TEST (suite, test_snapshot);
+	SUITE_ADD_TEST (suite, test_snapshot_base);
+	SUITE_ADD_TEST (suite, test_set);
+	SUITE_ADD_TEST (suite, test_update);
+	SUITE_ADD_TEST (suite, test_find);
+	SUITE_ADD_TEST (suite, test_find_all);
+	SUITE_ADD_TEST (suite, test_find_realloc);
+	SUITE_ADD_TEST (suite, test_replace_all);
+	SUITE_ADD_TEST (suite, test_build_populate);
+	SUITE_ADD_TEST (suite, test_build_fail);
+	SUITE_ADD_TEST (suite, test_change_called);
+	SUITE_ADD_TEST (suite, test_change_batch);
+	SUITE_ADD_TEST (suite, test_change_nested);
+
+	CuSuiteRun (suite);
+	CuSuiteSummary (suite, output);
+	CuSuiteDetails (suite, output);
+	printf ("%s\n", output->buffer);
+	ret = suite->failCount;
+	CuSuiteDelete (suite);
+	CuStringDelete (output);
+
+	return ret;
+}
diff --git a/trust/tests/test-module.c b/trust/tests/test-module.c
index d811f1d..ddc31df 100644
--- a/trust/tests/test-module.c
+++ b/trust/tests/test-module.c
@@ -547,6 +547,236 @@ test_find_builtin (CuTest *cu)
 	teardown (cu);
 }
 
+static void
+test_session_object (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_ULONG size;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CreateObject (session, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_GetObjectSize (session, handle, &size);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	teardown (cu);
+}
+
+static void
+test_session_find (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_OBJECT_HANDLE check;
+	CK_ULONG count;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CreateObject (session, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjectsInit (session, original, 2);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjects (session, &check, 1, &count);
+	CuAssertTrue (cu, rv == CKR_OK);
+	CuAssertIntEquals (cu, 1, count);
+	CuAssertIntEquals (cu, handle, check);
+
+	rv = test.module->C_FindObjectsFinal (session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	teardown (cu);
+}
+
+static void
+test_lookup_invalid (CuTest *cu)
+{
+	CK_SESSION_HANDLE session;
+	CK_ULONG size;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_GetObjectSize (session, 88888, &size);
+	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
+
+	teardown (cu);
+}
+
+static void
+test_remove_token (CuTest *cu)
+{
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_ULONG count;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjectsInit (session, NULL, 0);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjects (session, &handle, 1, &count);
+	CuAssertTrue (cu, rv == CKR_OK);
+	CuAssertIntEquals (cu, 1, count);
+
+	rv = test.module->C_DestroyObject (session, handle);
+	CuAssertTrue (cu, rv == CKR_TOKEN_WRITE_PROTECTED);
+
+	teardown (cu);
+}
+
+static void
+test_setattr_token (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_ULONG count;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjectsInit (session, NULL, 0);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_FindObjects (session, &handle, 1, &count);
+	CuAssertTrue (cu, rv == CKR_OK);
+	CuAssertIntEquals (cu, 1, count);
+
+	rv = test.module->C_SetAttributeValue (session, handle, original, 2);
+	CuAssertTrue (cu, rv == CKR_TOKEN_WRITE_PROTECTED);
+
+	teardown (cu);
+}
+
+static void
+test_session_copy (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_OBJECT_HANDLE copy;
+	CK_ULONG size;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CreateObject (session, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CopyObject (session, handle, original, 2, &copy);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_GetObjectSize (session, copy, &size);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	teardown (cu);
+}
+
+static void
+test_session_setattr (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CreateObject (session, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_SetAttributeValue (session, handle, original, 2);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	teardown (cu);
+}
+
+static void
+test_session_remove (CuTest *cu)
+{
+	CK_ATTRIBUTE original[] = {
+		{ CKA_LABEL, "yay", 3 },
+		{ CKA_VALUE, "eight", 5 },
+		{ CKA_INVALID }
+	};
+
+	CK_SESSION_HANDLE session;
+	CK_OBJECT_HANDLE handle;
+	CK_RV rv;
+
+	setup (cu);
+
+	rv = test.module->C_OpenSession (test.slots[0], CKF_SERIAL_SESSION, NULL, NULL, &session);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_CreateObject (session, original, 2, &handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_DestroyObject (session, handle);
+	CuAssertTrue (cu, rv == CKR_OK);
+
+	rv = test.module->C_DestroyObject (session, handle);
+	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
+
+	teardown (cu);
+}
+
 int
 main (void)
 {
@@ -565,6 +795,14 @@ main (void)
 	SUITE_ADD_TEST (suite, test_close_all_sessions);
 	SUITE_ADD_TEST (suite, test_find_certificates);
 	SUITE_ADD_TEST (suite, test_find_builtin);
+	SUITE_ADD_TEST (suite, test_lookup_invalid);
+	SUITE_ADD_TEST (suite, test_remove_token);
+	SUITE_ADD_TEST (suite, test_setattr_token);
+	SUITE_ADD_TEST (suite, test_session_object);
+	SUITE_ADD_TEST (suite, test_session_find);
+	SUITE_ADD_TEST (suite, test_session_copy);
+	SUITE_ADD_TEST (suite, test_session_remove);
+	SUITE_ADD_TEST (suite, test_session_setattr);
 
 	CuSuiteRun (suite);
 	CuSuiteSummary (suite, output);
diff --git a/trust/tests/test-session.c b/trust/tests/test-session.c
deleted file mode 100644
index 6183e7c..0000000
--- a/trust/tests/test-session.c
+++ /dev/null
@@ -1,161 +0,0 @@
-/*
- * Copyright (c) 2012 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@gnome.org>
- */
-
-#include "config.h"
-#include "CuTest.h"
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-
-#include "attrs.h"
-#include "debug.h"
-#include "library.h"
-#include "session.h"
-#include "token.h"
-
-struct {
-	p11_token *token;
-	p11_session *session;
-} test;
-
-static void
-setup (CuTest *cu)
-{
-	test.token = p11_token_new (1, "/nonexistant");
-	CuAssertPtrNotNull (cu, test.token);
-
-	test.session = p11_session_new (test.token);
-	CuAssertPtrNotNull (cu, test.session);
-}
-
-static void
-teardown (CuTest *cu)
-{
-	p11_session_free (test.session);
-	p11_token_free (test.token);
-	memset (&test, 0, sizeof (test));
-}
-
-static void
-test_session_add_get (CuTest *cu)
-{
-	CK_ATTRIBUTE original[] = {
-		{ CKA_LABEL, "yay", 3 },
-		{ CKA_VALUE, "eight", 5 },
-		{ CKA_INVALID }
-	};
-
-	CK_ATTRIBUTE *attrs;
-	CK_ATTRIBUTE *check;
-	CK_OBJECT_HANDLE handle;
-	CK_BBOOL token;
-
-	setup (cu);
-
-	attrs = p11_attrs_dup (original);
-	p11_session_add_object (test.session, attrs, &handle);
-
-	check = p11_session_get_object (test.session, handle, &token);
-
-	CuAssertPtrEquals (cu, attrs, check);
-	CuAssertTrue (cu, token == CK_FALSE);
-
-	check = p11_session_get_object (test.session, 1UL, &token);
-	CuAssertPtrEquals (cu, NULL, check);
-
-	teardown (cu);
-}
-
-static void
-test_session_del (CuTest *cu)
-{
-	CK_ATTRIBUTE original[] = {
-		{ CKA_LABEL, "yay", 3 },
-		{ CKA_VALUE, "eight", 5 },
-		{ CKA_INVALID }
-	};
-
-	CK_ATTRIBUTE *attrs;
-	CK_ATTRIBUTE *check;
-	CK_OBJECT_HANDLE handle;
-	CK_BBOOL token;
-	CK_RV rv;
-
-	setup (cu);
-
-	attrs = p11_attrs_dup (original);
-	p11_session_add_object (test.session, attrs, &handle);
-
-	check = p11_session_get_object (test.session, handle, &token);
-	CuAssertPtrEquals (cu, attrs, check);
-	CuAssertTrue (cu, token == CK_FALSE);
-
-	rv = p11_session_del_object (test.session, 1UL);
-	CuAssertTrue (cu, rv == CKR_OBJECT_HANDLE_INVALID);
-
-	rv = p11_session_del_object (test.session, handle);
-	CuAssertTrue (cu, rv == CKR_OK);
-
-	check = p11_session_get_object (test.session, handle, &token);
-	CuAssertPtrEquals (cu, NULL, check);
-
-	teardown (cu);
-}
-
-int
-main (void)
-{
-	CuString *output = CuStringNew ();
-	CuSuite* suite = CuSuiteNew ();
-	int ret;
-
-	putenv ("P11_KIT_STRICT=1");
-	p11_library_init ();
-	p11_debug_init ();
-	p11_message_quiet ();
-
-	SUITE_ADD_TEST (suite, test_session_add_get);
-	SUITE_ADD_TEST (suite, test_session_del);
-
-	CuSuiteRun (suite);
-	CuSuiteSummary (suite, output);
-	CuSuiteDetails (suite, output);
-	printf ("%s\n", output->buffer);
-	ret = suite->failCount;
-	CuSuiteDelete (suite);
-	CuStringDelete (output);
-
-	return ret;
-}
diff --git a/trust/tests/test-token.c b/trust/tests/test-token.c
index 96f7a6c..ad25da0 100644
--- a/trust/tests/test-token.c
+++ b/trust/tests/test-token.c
@@ -68,7 +68,7 @@ teardown (CuTest *cu)
 static void
 test_token_load (CuTest *cu)
 {
-	p11_dict *objects;
+	p11_index *index;
 	int count;
 
 	setup (cu, SRCDIR "/input");
@@ -77,8 +77,8 @@ test_token_load (CuTest *cu)
 	CuAssertIntEquals (cu, 6, count);
 
 	/* A certificate and trust object for each parsed object + builtin */
-	objects = p11_token_objects (test.token);
-	CuAssertTrue (cu, ((count - 1) * 2) + 1 <= p11_dict_size (objects));
+	index = p11_token_index (test.token);
+	CuAssertTrue (cu, ((count - 1) * 2) + 1 <= p11_index_size (index));
 
 	teardown (cu);
 }
@@ -86,19 +86,25 @@ test_token_load (CuTest *cu)
 static bool
 check_object (CK_ATTRIBUTE *match)
 {
+	CK_OBJECT_HANDLE *handles;
 	CK_ATTRIBUTE *attrs;
-	p11_dict *objects;
-	p11_dictiter iter;
-
-	objects = p11_token_objects (test.token);
-
-	p11_dict_iterate (objects, &iter);
-	while (p11_dict_next (&iter, NULL, (void **)&attrs)) {
-		if (p11_attrs_match (attrs, match))
-			return true;
+	p11_index *index;
+	bool ret = false;
+	int i;
+
+	index = p11_token_index (test.token);
+	handles = p11_index_snapshot (index, NULL, match, p11_attrs_count (match));
+
+	for (i = 0; handles[i] != 0; i++) {
+		attrs = p11_index_lookup (index, handles[i]);
+		if (p11_attrs_match (attrs, match)) {
+			ret = true;
+			break;
+		}
 	}
 
-	return false;
+	free (handles);
+	return ret;
 }
 
 static void
diff --git a/trust/token.c b/trust/token.c
index 39bca04..558f374 100644
--- a/trust/token.c
+++ b/trust/token.c
@@ -58,7 +58,7 @@
 
 struct _p11_token {
 	p11_parser *parser;
-	p11_dict *objects;
+	p11_index *index;
 	const char *path;
 	CK_SLOT_ID slot;
 	int loaded;
@@ -68,18 +68,11 @@ static void
 on_parser_object (CK_ATTRIBUTE *attrs,
                   void *user_data)
 {
-	CK_OBJECT_HANDLE object;
-	CK_OBJECT_HANDLE *key;
 	p11_token *token = user_data;
 
 	return_if_fail (attrs != NULL);
 
-	object = p11_module_next_id ();
-
-	key = memdup (&object, sizeof (object));
-	return_if_fail (key != NULL);
-
-	if (!p11_dict_set (token->objects, key, attrs))
+	if (p11_index_take (token->index, attrs, NULL) != CKR_OK)
 		return_if_reached ();
 }
 
@@ -395,19 +388,13 @@ p11_token_load (p11_token *token)
 	return count + builtins;
 }
 
-p11_dict *
-p11_token_objects (p11_token *token)
-{
-	return token->objects;
-}
-
 void
 p11_token_free (p11_token *token)
 {
 	if (!token)
 		return;
 
-	p11_dict_free (token->objects);
+	p11_index_free (token->index);
 	p11_parser_free (token->parser);
 	free (token);
 }
@@ -424,10 +411,8 @@ p11_token_new (CK_SLOT_ID slot,
 	token->parser = p11_parser_new ();
 	return_val_if_fail (token->parser != NULL, NULL);
 
-	token->objects = p11_dict_new (p11_dict_ulongptr_hash,
-	                               p11_dict_ulongptr_equal,
-	                               free, p11_attrs_free);
-	return_val_if_fail (token->objects != NULL, NULL);
+	token->index = p11_index_new (NULL, NULL, NULL);
+	return_val_if_fail (token->index != NULL, NULL);
 
 	token->path = strdup (path);
 	return_val_if_fail (token->path != NULL, NULL);
@@ -451,3 +436,10 @@ p11_token_get_slot (p11_token *token)
 	return_val_if_fail (token != NULL, 0);
 	return token->slot;
 }
+
+p11_index *
+p11_token_index (p11_token *token)
+{
+	return_val_if_fail (token != NULL, NULL);
+	return token->index;
+}
diff --git a/trust/token.h b/trust/token.h
index 599e982..43cebaa 100644
--- a/trust/token.h
+++ b/trust/token.h
@@ -36,6 +36,7 @@
 #define P11_TOKEN_H_
 
 #include "dict.h"
+#include "index.h"
 #include "pkcs11.h"
 
 typedef struct _p11_token p11_token;
@@ -47,7 +48,7 @@ void            p11_token_free        (p11_token *token);
 
 int             p11_token_load        (p11_token *token);
 
-p11_dict *      p11_token_objects     (p11_token *token);
+p11_index *     p11_token_index       (p11_token *token);
 
 const char *    p11_token_get_path    (p11_token *token);