aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--hal_internal.h96
-rw-r--r--ks.c4
-rw-r--r--ks_flash.c8
-rw-r--r--ks_index.c222
-rw-r--r--ks_mmap.c4
-rw-r--r--rpc_misc.c6
7 files changed, 326 insertions, 16 deletions
diff --git a/Makefile b/Makefile
index 26030db..a246828 100644
--- a/Makefile
+++ b/Makefile
@@ -118,7 +118,7 @@ endif
#
# The mmap keystore hasn't been rewritten for the new API yet.
-KS_OBJ = ks_volatile.o
+KS_OBJ = ks_index.o ks_volatile.o
ifeq "${KS}" "mmap"
KS_OBJ += ks_mmap.o
diff --git a/hal_internal.h b/hal_internal.h
index ef00328..dcf532f 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -304,6 +304,12 @@ extern hal_error_t hal_uuid_format(const hal_uuid_t * const uuid, char *buffer,
#define HAL_KS_WRAPPED_KEYSIZE ((4655 + 15) & ~7)
/*
+ * hal_ks_key_t probably should not be here, or perhaps even exist at
+ * all, since it's really a relic of an older design from before we
+ * understood how the keystore flash fit into this picture. Leaving
+ * it in place for now, but expect it to go away once the new ks_index
+ * stuff is ready to use.
+ *
* This struct is ordered such that all metadata appears before the
* big buffers, in order for all metadata to be loaded with a single
* page read from e.g. the ks_flash module.
@@ -488,17 +494,99 @@ static inline hal_error_t hal_ks_list(hal_ks_t *ks,
}
/*
+ * Keystore index. This is intended to be usable by both memory-based
+ * (in-memory, mmap(), ...) keystores and keystores based on raw flash.
+ * Some of the features aren't really necessary for memory-based keystores,
+ * but should be harmless.
+ *
+ * General approach is multiple arrays, all but one of which are
+ * indexed by "block" numbers, where a block number might be a slot in
+ * yet another static array, the number of a flash sub-sector, or
+ * whatever is the appropriate unit for holding one keystore record.
+ *
+ * The index array contains nothing but flags and block numbers, and
+ * is deliberately a small data structure so that moving data around
+ * within it is relatively cheap.
+ *
+ * The index array is divided into two portions: the index proper, and
+ * the free queue. The index proper is ordered according to the names
+ * (UUIDs) of the corresponding blocks; the free queue is a FIFO, to
+ * support a simplistic form of wear leveling in flash-based keystores.
+ *
+ * Key names are kept in a separate array, indexed by block number.
+ *
+ * The all-ones UUID, which (by definition) cannot be a valid key
+ * UUID, is reserved for the (non-key) block used to stash PINs and
+ * other small data which aren't really part of the keystore proper
+ * but are kept with it because the keystore is the flash we have.
+ *
+ * At the moment, this design leaves no room for "continuation" blocks
+ * (additional blocks for keys so large that they won't fit in a
+ * single flash sub-sector, or whatever). Not sure we need that, but
+ * if we do, adding it would be fairly simple: change the keyname
+ * array to be an array of two-element structures, the first of which
+ * is the name UUID, the second of which is the offset within the
+ * series of blocks sharing that name (usually just one block, so the
+ * offset would usually just be zero). Implement that if and when we
+ * need it.
+ *
+ * Note that this API deliberately says nothing about how the keys
+ * themselves are stored, that's up to the keystore driver. This
+ * portion of the API is only concerned with allocation and naming.
+ */
+
+typedef struct {
+ unsigned size; /* Array length */
+ unsigned used; /* How many blocks are in use */
+ uint16_t *index; /* Index/freelist array */
+ hal_uuid_t *names; /* Keyname array */
+} hal_ks_index_t;
+
+/*
+ * Finish setting up key index. Caller must populate index, free
+ * list, and name array.
+ *
+ * This function checks a few things then sorts the index proper.
+ *
+ * If driver cares about wear leveling, driver must supply the free
+ * list in the desired order (FIFO); figuring out what that order is a
+ * problem for the keystore driver.
+ */
+extern hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi);
+
+/*
+ * Find a key block, return its block number.
+ */
+extern hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno);
+
+/*
+ * Add a key block, return its block number.
+ */
+extern hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno);
+
+/*
+ * Delete a key block, returns its block number (driver may need it).
+ */
+extern hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno);
+
+/*
* This stuff might want renaming, eg, to hal_pin_*().
*/
extern hal_error_t hal_set_pin_default_iterations(const hal_client_handle_t client,
const uint32_t iterations);
-extern hal_error_t hal_ks_get_pin(const hal_user_t user,
- const hal_ks_pin_t **pin);
+extern hal_error_t hal_get_pin(const hal_user_t user,
+ const hal_ks_pin_t **pin);
-extern hal_error_t hal_ks_set_pin(const hal_user_t user,
- const hal_ks_pin_t * const pin);
+extern hal_error_t hal_set_pin(const hal_user_t user,
+ const hal_ks_pin_t * const pin);
/*
* RPC lowest-level send and receive routines. These are blocking, and
diff --git a/ks.c b/ks.c
index 8510dc3..a2c0f3c 100644
--- a/ks.c
+++ b/ks.c
@@ -353,8 +353,8 @@ hal_error_t hal_ks_list(hal_pkey_info_t *result,
return HAL_OK;
}
-hal_error_t hal_ks_get_pin(const hal_user_t user,
- const hal_ks_pin_t **pin)
+hal_error_t hal_get_pin(const hal_user_t user,
+ const hal_ks_pin_t **pin)
{
if (pin == NULL)
return HAL_ERROR_BAD_ARGUMENTS;
diff --git a/ks_flash.c b/ks_flash.c
index 5d0baaf..c3d12aa 100644
--- a/ks_flash.c
+++ b/ks_flash.c
@@ -519,8 +519,8 @@ const hal_ks_driver_t hal_ks_token_driver[1] = {{
* because it's the flash we've got.
*/
-hal_error_t hal_ks_get_pin(const hal_user_t user,
- const hal_ks_pin_t **pin)
+hal_error_t hal_get_pin(const hal_user_t user,
+ const hal_ks_pin_t **pin)
{
if (pin == NULL)
return HAL_ERROR_BAD_ARGUMENTS;
@@ -560,8 +560,8 @@ hal_error_t hal_ks_get_pin(const hal_user_t user,
return LIBHAL_OK;
}
-hal_error_t hal_ks_set_pin(const hal_user_t user,
- const hal_ks_pin_t * const pin)
+hal_error_t hal_set_pin(const hal_user_t user,
+ const hal_ks_pin_t * const pin)
{
uint32_t active_sector_offset;
diff --git a/ks_index.c b/ks_index.c
new file mode 100644
index 0000000..eb6ff10
--- /dev/null
+++ b/ks_index.c
@@ -0,0 +1,222 @@
+/*
+ * ks_index.c
+ * ----------
+ * Keystore index API. This is internal within libhal.
+ *
+ * Copyright (c) 2016, NORDUnet A/S All rights reserved.
+ *
+ * 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.
+ *
+ * - Neither the name of the NORDUnet nor the names of its contributors may
+ * 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
+ * HOLDER 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.
+ */
+
+#include <string.h>
+#include <assert.h>
+
+#include "hal.h"
+#include "hal_internal.h"
+
+/*
+ * Return value indicates whether the name is present in the index.
+ * "where" indicates the name's position whether present or not.
+ *
+ * NB: this does NOT return a block number, it returns an index into
+ * ksi->index[].
+ */
+
+static int ks_find(const hal_ks_index_t * const ksi,
+ const hal_uuid_t * const name,
+ int *where)
+{
+ assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL && name != NULL && where != NULL);
+
+ int lo = -1;
+ int hi = ksi->used;
+
+ for (;;) {
+ int m = (lo + hi) / 2;
+ if (m == lo) {
+ *where = hi;
+ return 0;
+ }
+ const int cmp = hal_uuid_cmp(name, &ksi->names[ksi->index[m]]);
+ if (cmp < 0)
+ hi = m;
+ else if (cmp > 0)
+ lo = m;
+ else {
+ *where = m;
+ return 1;
+ }
+ }
+}
+
+/*
+ * Heapsort the index. We only need to do this on setup, for other
+ * operations we're just inserting or deleting a single entry in an
+ * already-ordered array, which is just a search problem. If we were
+ * really crunched for space, we could use an insertion sort here, but
+ * heapsort is easy and works well with data already in place.
+ */
+
+static inline void ks_heapsift(hal_ks_index_t *ksi, int parent, const int end)
+{
+ assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL &&
+ parent >= 0 && end >= parent);
+ for (;;) {
+ const int left_child = parent * 2 + 1;
+ const int right_child = parent * 2 + 2;
+ int biggest = parent;
+ if (left_child <= end && hal_uuid_cmp(&ksi->names[ksi->index[biggest]],
+ &ksi->names[ksi->index[left_child]]) < 0)
+ biggest = left_child;
+ if (right_child <= end && hal_uuid_cmp(&ksi->names[ksi->index[biggest]],
+ &ksi->names[ksi->index[right_child]]) < 0)
+ biggest = right_child;
+ if (biggest == parent)
+ return;
+ const uint16_t tmp = ksi->index[biggest];
+ ksi->index[biggest] = ksi->index[parent];
+ ksi->index[parent] = tmp;
+ parent = biggest;
+ }
+}
+
+static inline void ks_heapsort(hal_ks_index_t *ksi)
+{
+ assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL);
+ if (ksi->used < 2)
+ return;
+ for (int i = (ksi->used - 2) / 2; i >= 0; i--)
+ ks_heapsift(ksi, i, ksi->used - 1);
+ for (int i = ksi->used - 1; i > 0; i--) {
+ const uint16_t tmp = ksi->index[i];
+ ksi->index[i] = ksi->index[0];
+ ksi->index[0] = tmp;
+ ks_heapsift(ksi, 0, i);
+ }
+}
+
+hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
+{
+ if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
+ ksi->size == 0 || ksi->used > ksi->size)
+ return HAL_ERROR_BAD_ARGUMENTS;
+
+ /*
+ * Only setup task we have at the moment is sorting the index.
+ */
+
+ ks_heapsort(ksi);
+ return HAL_OK;
+}
+
+hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno)
+{
+ if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
+ ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+ return HAL_ERROR_BAD_ARGUMENTS;
+
+ int where;
+
+ if (!ks_find(ksi, name, &where))
+ return HAL_ERROR_KEY_NOT_FOUND;
+
+ if (blockno != NULL)
+ *blockno = ksi->index[where];
+
+ return HAL_OK;
+}
+
+hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno)
+{
+ if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
+ ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+ return HAL_ERROR_BAD_ARGUMENTS;
+
+ if (ksi->used == ksi->size)
+ return HAL_ERROR_NO_KEY_SLOTS_AVAILABLE;
+
+ int where;
+
+ if (ks_find(ksi, name, &where))
+ return HAL_ERROR_KEY_NAME_IN_USE;
+
+ /*
+ * Grab first block on free list, which makes room to slide the
+ * index down by one slot so we can insert the new block number.
+ */
+
+ const size_t len = (ksi->used - where) * sizeof(*ksi->index);
+ const uint16_t b = ksi->index[ksi->used++];
+ memmove(&ksi->index[where + 1], &ksi->index[where], len);
+ ksi->index[where] = b;
+ ksi->names[b] = *name;
+
+ if (blockno != NULL)
+ *blockno = b;
+
+ return HAL_OK;
+}
+
+hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
+ const hal_uuid_t * const name,
+ unsigned *blockno)
+{
+ if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
+ ksi->size == 0 || ksi->used > ksi->size || name == NULL)
+ return HAL_ERROR_BAD_ARGUMENTS;
+
+ int where;
+
+ if (ksi->used == 0 || !ks_find(ksi, name, &where))
+ return HAL_ERROR_KEY_NOT_FOUND;
+
+ /*
+ * Free the block and stuff it at the end of the free list.
+ */
+
+ const size_t len = (ksi->size - where - 1) * sizeof(*ksi->index);
+ const uint16_t b = ksi->index[where];
+ memmove(&ksi->index[where], &ksi->index[where + 1], len);
+ ksi->index[ksi->size - 1] = b;
+ ksi->used--;
+ memset(&ksi->names[b], 0, sizeof(ksi->names[b]));
+
+ if (blockno != NULL)
+ *blockno = b;
+
+ return HAL_OK;
+}
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/ks_mmap.c b/ks_mmap.c
index e158e13..6d9ac6f 100644
--- a/ks_mmap.c
+++ b/ks_mmap.c
@@ -125,8 +125,8 @@ hal_error_t hal_ks_del_keydb(const int loc)
return HAL_OK;
}
-hal_error_t hal_ks_set_pin(const hal_user_t user,
- const hal_ks_pin_t * const pin)
+hal_error_t hal_set_pin(const hal_user_t user,
+ const hal_ks_pin_t * const pin)
{
if (pin == NULL)
return HAL_ERROR_BAD_ARGUMENTS;
diff --git a/rpc_misc.c b/rpc_misc.c
index 1902b71..c3ff44c 100644
--- a/rpc_misc.c
+++ b/rpc_misc.c
@@ -133,7 +133,7 @@ static hal_error_t login(const hal_client_handle_t client,
const hal_ks_pin_t *p;
hal_error_t err;
- if ((err = hal_ks_get_pin(user, &p)) != HAL_OK)
+ if ((err = hal_get_pin(user, &p)) != HAL_OK)
return err;
uint8_t buf[sizeof(p->pin)];
@@ -207,7 +207,7 @@ static hal_error_t set_pin(const hal_client_handle_t client,
const hal_ks_pin_t *pp;
hal_error_t err;
- if ((err = hal_ks_get_pin(user, &pp)) != HAL_OK)
+ if ((err = hal_get_pin(user, &pp)) != HAL_OK)
return err;
hal_ks_pin_t p = *pp;
@@ -219,7 +219,7 @@ static hal_error_t set_pin(const hal_client_handle_t client,
(const uint8_t *) newpin, newpin_len,
p.salt, sizeof(p.salt),
p.pin, sizeof(p.pin), p.iterations)) != HAL_OK ||
- (err = hal_ks_set_pin(user, &p)) != HAL_OK)
+ (err = hal_set_pin(user, &p)) != HAL_OK)
return err;
return HAL_OK;