diff options
Diffstat (limited to 'trust/index.c')
| -rw-r--r-- | trust/index.c | 912 |
1 files changed, 0 insertions, 912 deletions
diff --git a/trust/index.c b/trust/index.c deleted file mode 100644 index f4b6b4b..0000000 --- a/trust/index.c +++ /dev/null @@ -1,912 +0,0 @@ -/* - * 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> -#include <string.h> - -/* - * 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 by handle */ - p11_dict *objects; - - /* Used for indexing */ - index_bucket *buckets; - - /* Data passed to callbacks */ - void *data; - - /* Called to build an new/modified object */ - p11_index_build_cb build; - - /* Called after each object ready to be stored */ - p11_index_store_cb store; - - /* Called after an object has been removed */ - p11_index_remove_cb remove; - - /* Called after objects change */ - p11_index_notify_cb notify; - - /* Used for queueing changes, when in a batch */ - p11_dict *changes; - bool notifying; -}; - -typedef struct { - CK_OBJECT_HANDLE handle; - CK_ATTRIBUTE *attrs; -} index_object; - -static void -free_object (void *data) -{ - index_object *obj = data; - p11_attrs_free (obj->attrs); - free (obj); -} - -static CK_RV -default_build (void *data, - p11_index *index, - CK_ATTRIBUTE *attrs, - CK_ATTRIBUTE *merge, - CK_ATTRIBUTE **populate) -{ - return CKR_OK; -} - -static CK_RV -default_store (void *data, - p11_index *index, - CK_OBJECT_HANDLE handle, - CK_ATTRIBUTE **attrs) -{ - return CKR_OK; -} - -static void -default_notify (void *data, - p11_index *index, - CK_OBJECT_HANDLE handle, - CK_ATTRIBUTE *attrs) -{ - -} - -static CK_RV -default_remove (void *data, - p11_index *index, - CK_ATTRIBUTE *attrs) -{ - return CKR_OK; -} - -p11_index * -p11_index_new (p11_index_build_cb build, - p11_index_store_cb store, - p11_index_remove_cb remove, - p11_index_notify_cb notify, - void *data) -{ - p11_index *index; - - index = calloc (1, sizeof (p11_index)); - return_val_if_fail (index != NULL, NULL); - - if (build == NULL) - build = default_build; - if (store == NULL) - store = default_store; - if (notify == NULL) - notify = default_notify; - if (remove == NULL) - remove = default_remove; - - index->build = build; - index->store = store; - index->notify = notify; - index->remove = remove; - 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); - - 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); -} - -int -p11_index_size (p11_index *index) -{ - return_val_if_fail (index != NULL, -1); - 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: - case CKA_X_ORIGIN: - 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 void -merge_attrs (CK_ATTRIBUTE *output, - CK_ULONG *noutput, - CK_ATTRIBUTE *merge, - CK_ULONG nmerge, - p11_array *to_free) -{ - CK_ULONG i; - - for (i = 0; i < nmerge; i++) { - /* Already have this attribute? */ - if (p11_attrs_findn (output, *noutput, merge[i].type)) { - p11_array_push (to_free, merge[i].pValue); - - } else { - memcpy (output + *noutput, merge + i, sizeof (CK_ATTRIBUTE)); - (*noutput)++; - } - } - - /* Freeing the array itself */ - p11_array_push (to_free, merge); -} - -static CK_RV -index_build (p11_index *index, - CK_OBJECT_HANDLE handle, - CK_ATTRIBUTE **attrs, - CK_ATTRIBUTE *merge) -{ - CK_ATTRIBUTE *extra = NULL; - CK_ATTRIBUTE *built; - p11_array *stack = NULL; - CK_ULONG count; - CK_ULONG nattrs; - CK_ULONG nmerge; - CK_ULONG nextra; - CK_RV rv; - int i; - - rv = index->build (index->data, index, *attrs, merge, &extra); - if (rv != CKR_OK) - return rv; - - /* Short circuit when nothing to merge */ - if (*attrs == NULL && extra == NULL) { - built = merge; - stack = NULL; - - } else { - stack = p11_array_new (NULL); - nattrs = p11_attrs_count (*attrs); - nmerge = p11_attrs_count (merge); - nextra = p11_attrs_count (extra); - - /* Make a shallow copy of the combined attributes for validation */ - built = calloc (nmerge + nattrs + nextra + 1, sizeof (CK_ATTRIBUTE)); - return_val_if_fail (built != NULL, CKR_GENERAL_ERROR); - - count = nmerge; - memcpy (built, merge, sizeof (CK_ATTRIBUTE) * nmerge); - p11_array_push (stack, merge); - merge_attrs (built, &count, *attrs, nattrs, stack); - merge_attrs (built, &count, extra, nextra, stack); - - /* The terminator attribute */ - built[count].type = CKA_INVALID; - assert (p11_attrs_terminator (built + count)); - } - - rv = index->store (index->data, index, handle, &built); - - if (rv == CKR_OK) { - for (i = 0; stack && i < stack->num; i++) - free (stack->elem[i]); - *attrs = built; - } else { - p11_attrs_free (extra); - free (built); - } - - p11_array_free (stack); - return rv; -} - -static void -call_notify (p11_index *index, - CK_OBJECT_HANDLE handle, - CK_ATTRIBUTE *attrs) -{ - assert (index->notify); - - /* 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->notifying = true; - index->notify (index->data, index, handle, attrs); - index->notifying = false; -} - -static void -index_notify (p11_index *index, - CK_OBJECT_HANDLE handle, - CK_ATTRIBUTE *removed) -{ - index_object *obj; - - if (!index->notify || index->notifying) { - p11_attrs_free (removed); - - } else if (!index->changes) { - call_notify (index, handle, removed); - p11_attrs_free (removed); - - } else { - obj = calloc (1, sizeof (index_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_load (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; - index_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)) { - index_notify (index, obj->handle, obj->attrs); - obj->attrs = NULL; - } - - p11_dict_free (changes); -} - -bool -p11_index_loading (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) -{ - 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 (index_object)); - return_val_if_fail (obj != NULL, CKR_HOST_MEMORY); - - obj->handle = p11_module_next_id (); - - rv = index_build (index, obj->handle, &obj->attrs, attrs); - if (rv != CKR_OK) { - p11_attrs_free (attrs); - free (obj); - return rv; - } - - return_val_if_fail (obj->attrs != NULL, CKR_GENERAL_ERROR); - - 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_notify (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) -{ - index_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->handle, &obj->attrs, update); - if (rv != CKR_OK) { - p11_attrs_free (update); - return rv; - } - - index_hash (index, obj); - index_notify (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; - index_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) -{ - index_object *obj; - CK_RV rv; - - return_val_if_fail (index != NULL, CKR_GENERAL_ERROR); - - if (!p11_dict_steal (index->objects, &handle, NULL, (void **)&obj)) - return CKR_OBJECT_HANDLE_INVALID; - - rv = (index->remove) (index->data, index, obj->attrs); - - /* If the writer failed the remove, then add it back */ - if (rv != CKR_OK) { - if (!p11_dict_set (index->objects, &obj->handle, obj)) - return_val_if_reached (CKR_HOST_MEMORY); - return rv; - } - - /* This takes ownership of the attributes */ - index_notify (index, handle, obj->attrs); - obj->attrs = NULL; - free_object (obj); - - return CKR_OK; -} - -static CK_RV -index_replacev (p11_index *index, - CK_OBJECT_HANDLE *handles, - CK_ATTRIBUTE_TYPE key, - CK_ATTRIBUTE **replace, - CK_ULONG replacen) -{ - index_object *obj; - CK_ATTRIBUTE *attrs; - CK_ATTRIBUTE *attr; - bool handled = false; - CK_RV rv; - int i, j; - - 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 (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, obj->handle, &attrs, replace[j]); - if (rv != CKR_OK) - return rv; - p11_attrs_free (obj->attrs); - obj->attrs = attrs; - replace[j] = NULL; - handled = true; - index_hash (index, obj); - index_notify (index, obj->handle, NULL); - 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; - attrs = replace[j]; - replace[j] = NULL; - rv = p11_index_take (index, attrs, NULL); - if (rv != CKR_OK) - return rv; - } - - return CKR_OK; -} - -CK_RV -p11_index_replace (p11_index *index, - 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, handles, CKA_INVALID, - &replace, replace ? 1 : 0); -} - -CK_RV -p11_index_replace_all (p11_index *index, - CK_ATTRIBUTE *match, - 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); - - handles = p11_index_find_all (index, match, -1); - - rv = index_replacev (index, handles, key, - replace ? (CK_ATTRIBUTE **)replace->elem : NULL, - replace ? replace->num : 0); - - if (rv == CKR_OK) { - if (replace) - p11_array_clear (replace); - } else { - for (i = 0; replace && i < replace->num; i++) { - if (!replace->elem[i]) { - p11_array_remove (replace, i); - i--; - } - } - } - - free (handles); - return rv; -} - -CK_ATTRIBUTE * -p11_index_lookup (p11_index *index, - CK_OBJECT_HANDLE handle) -{ - index_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; -} - -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) -{ - index_bucket *selected[MAX_SELECT]; - 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); - selected[num] = index->buckets + (hash % NUM_BUCKETS); - - /* If any index is empty, then obviously no match */ - if (!selected[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 < selected[0]->num; i++) { - /* A candidate match from first bucket */ - handle = selected[0]->elem[i]; - - /* Check if the candidate is in other buckets */ - for (j = 1; j < num; j++) { - assert (selected[j]->elem); /* checked above */ - at = binary_search (selected[j]->elem, 0, selected[j]->num, handle); - if (at >= selected[j]->num || selected[j]->elem[at] != handle) { - handle = 0; - break; - } - } - - /* 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; - - if (p11_attrs_matchn (obj->attrs, match, count)) { - *result = obj->handle; - return false; - } - - return true; -} - -CK_OBJECT_HANDLE -p11_index_find (p11_index *index, - CK_ATTRIBUTE *match, - int count) -{ - CK_OBJECT_HANDLE handle = 0UL; - - return_val_if_fail (index != NULL, 0UL); - - if (count < 0) - count = p11_attrs_count (match); - - 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, - int count) -{ - index_bucket handles = { NULL, 0 }; - - return_val_if_fail (index != NULL, NULL); - - 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 * -p11_index_snapshot (p11_index *index, - p11_index *base, - CK_ATTRIBUTE *attrs, - CK_ULONG count) -{ - index_bucket handles = { NULL, 0 }; - - return_val_if_fail (index != NULL, NULL); - - if (count < (CK_ULONG)0UL) - count = p11_attrs_count (attrs); - - index_select (index, attrs, count, sink_any, &handles); - if (base) - index_select (base, attrs, count, sink_any, &handles); - - /* Null terminate */ - bucket_push (&handles, 0UL); - return handles.elem; -} |