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/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 +-
6 files changed, 103 insertions(+), 45 deletions(-)
create mode 100644 trust/tests/frob-pow.c
(limited to 'trust/tests')
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