From e075585ef1cffc988894b4efbf3d14d5e55dcdcc Mon Sep 17 00:00:00 2001
From: Stef Walter <stefw@gnome.org>
Date: Wed, 20 Mar 2013 14:35:27 +0100
Subject: 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.
---
trust/builder.c | 14 +-
trust/index.c | 439 ++++++++++++++++++++++++++++++++-------------
trust/index.h | 15 +-
trust/tests/Makefile.am | 3 +-
trust/tests/frob-pow.c | 57 ++++++
trust/tests/test-builder.c | 44 ++---
trust/tests/test-index.c | 36 ++--
trust/tests/test-parser.c | 6 +-
trust/tests/test-token.c | 2 +-
9 files changed, 437 insertions(+), 179 deletions(-)
create mode 100644 trust/tests/frob-pow.c
(limited to 'trust')
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);
--
cgit v1.1