diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | hal_internal.h | 96 | ||||
| -rw-r--r-- | ks.c | 4 | ||||
| -rw-r--r-- | ks_flash.c | 8 | ||||
| -rw-r--r-- | ks_index.c | 222 | ||||
| -rw-r--r-- | ks_mmap.c | 4 | ||||
| -rw-r--r-- | rpc_misc.c | 6 |
7 files changed, 326 insertions, 16 deletions
@@ -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 @@ -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; @@ -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: + */ @@ -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; @@ -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; |