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.

6 files changed, 103 insertions, 45 deletions

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);