Checkpoint, not expected to work yet, includes a lot of notes.

2 files changed, 1372 insertions, 0 deletions

diff --git a/ks.c b/ks.c
new file mode 100644
index 0000000..c107eb6
--- /dev/null
+++ b/ks.c
@@ -0,0 +1,1131 @@
+/*
+ * ks.c
+ * ----
+ * Keystore, generic parts anyway.  This is internal within libhal.
+ *
+ * Copyright (c) 2015-2017, 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 <stddef.h>
+#include <string.h>
+
+#include "hal.h"
+#include "hal_internal.h"
+#include "ks.h"
+
+/*
+ * Find a block in the index, return true (found) or false (not found).
+ * "where" indicates the name's position, or the position of the first free block.
+ *
+ * NB: This does NOT return a block number, it returns an index into
+ * ks->index[].
+ */
+
+static int ks_find(const hal_ks_t * const ks,
+                   const hal_uuid_t * const uuid,
+                   const int * const hint,
+                   int *where)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL || uuid == NULL || where == NULL)
+    return 0;
+
+  if (hint != NULL && *hint >= 0 && *hint < ks->used &&
+      hal_uuid_cmp(uuid, &ks->names[ks->index[*hint]]) == 0) {
+    *where = *hint;
+    return 1;
+  }
+
+  int lo = -1;
+  int hi = ks->used;
+
+  for (;;) {
+    int m = (lo + hi) / 2;
+    if (hi == 0 || m == lo) {
+      *where = hi;
+      return 0;
+    }
+    const int cmp = hal_uuid_cmp(uuid, &ks->names[ks->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_t *ks, int parent, const int end)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL || parent < 0 || end < parent)
+    return;
+  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(&ks->names[ks->index[biggest]],
+                                           &ks->names[ks->index[left_child]])  < 0)
+      biggest = left_child;
+    if (right_child <= end && hal_uuid_cmp(&ks->names[ks->index[biggest]],
+                                           &ks->names[ks->index[right_child]]) < 0)
+      biggest = right_child;
+    if (biggest == parent)
+      return;
+    const uint16_t tmp = ks->index[biggest];
+    ks->index[biggest] = ks->index[parent];
+    ks->index[parent]  = tmp;
+    parent = biggest;
+  }
+}
+
+static inline void ks_heapsort(hal_ks_t *ks)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL)
+    return;
+  if (ks->used < 2)
+    return;
+  for (int i = (ks->used - 2) / 2; i >= 0; i--)
+    ks_heapsift(ks, i, ks->used - 1);
+  for (int i = ks->used - 1; i > 0; i--) {
+    const uint16_t tmp = ks->index[i];
+    ks->index[i]       = ks->index[0];
+    ks->index[0]       = tmp;
+    ks_heapsift(ks, 0, i - 1);
+  }
+}
+
+/*
+ * Perform a consistency check on the index.
+ */
+
+#define fsck(_ks) \
+  do { hal_error_t _err = hal_ks_index_fsck(_ks); if (_err != HAL_OK) return _err; } while (0)
+
+
+hal_error_t hal_ks_index_fsck(hal_ks_t *ks)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  for (int i = 1; i < ks->used; i++)
+    if (hal_uuid_cmp(&ks->names[ks->index[i - 1]], &ks->names[ks->index[i]]) >= 0)
+      return HAL_ERROR_KS_INDEX_UUID_MISORDERED;
+
+  return HAL_OK;
+}
+
+/*
+ * Find a single block by name.
+ */
+
+hal_error_t hal_ks_index_find(hal_ks_t *ks,
+                              const hal_uuid_t * const name,
+                              unsigned *blockno,
+                              int *hint)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  int where;
+
+  fsck(ks);
+
+  int ok = ks_find(ks, name, hint, &where);
+
+  if (blockno != NULL)
+    *blockno = ks->index[where];
+
+  if (hint != NULL)
+    *hint = where;
+
+  return ok ? HAL_OK : HAL_ERROR_KEY_NOT_FOUND;
+}
+
+/*
+ * Add a single block to the index.
+ */
+
+hal_error_t hal_ks_index_add(hal_ks_t *ks,
+                             const hal_uuid_t * const name,
+                             unsigned *blockno,
+                             int *hint)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  if (ks->used == ks->size)
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+  int where;
+
+  fsck(ks);
+
+  if (ks_find(ks, name, hint, &where))
+    return HAL_ERROR_KEY_NAME_IN_USE;
+
+  /*
+   * Grab first block on free list, which makes room to slide the
+   * index up by one slot so we can insert the new block number.
+   */
+
+  const size_t len = (ks->used - where) * sizeof(*ks->index);
+  const uint16_t b = ks->index[ks->used++];
+  memmove(&ks->index[where + 1], &ks->index[where], len);
+  ks->index[where] = b;
+  ks->names[b] = *name;
+
+  if (blockno != NULL)
+    *blockno = b;
+
+  if (hint != NULL)
+    *hint = where;
+
+  fsck(ks);
+
+  return HAL_OK;
+}
+
+/*
+ * Delete a single block from the index.
+ */
+
+hal_error_t hal_ks_index_delete(hal_ks_t *ks,
+                                const hal_uuid_t * const name,
+                                unsigned *blockno,
+                                int *hint)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  int where;
+
+  fsck(ks);
+
+  if (ks->used == 0 || !ks_find(ks, name, hint, &where))
+    return HAL_ERROR_KEY_NOT_FOUND;
+
+  /*
+   * Free the block and stuff it at the end of the free list.
+   */
+
+  const size_t len = (ks->size - where - 1) * sizeof(*ks->index);
+  const uint16_t b = ks->index[where];
+  memmove(&ks->index[where], &ks->index[where + 1], len);
+  ks->index[ks->size - 1] = b;
+  ks->used--;
+  memset(&ks->names[b], 0, sizeof(ks->names[b]));
+
+  if (blockno != NULL)
+    *blockno = b;
+
+  if (hint != NULL)
+    *hint = where;
+
+  fsck(ks);
+
+  return HAL_OK;
+}
+
+/*
+ * Replace a single block in the index.
+ */
+
+hal_error_t hal_ks_index_replace(hal_ks_t *ks,
+                                 const hal_uuid_t * const name,
+                                 unsigned *blockno,
+                                 int *hint)
+{
+  if (ks == NULL || ks->index == NULL || ks->names == NULL ||
+      ks->size == 0 || ks->used > ks->size || name == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  if (ks->used == ks->size)
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+  int where;
+
+  fsck(ks);
+
+  if (ks->used == 0 || !ks_find(ks, name, hint, &where))
+    return HAL_ERROR_KEY_NOT_FOUND;
+
+  /*
+   * Grab first block from free list, slide free list down, put old
+   * block at end of free list and replace old block with new block.
+   */
+
+  const size_t len = (ks->size - ks->used - 1) * sizeof(*ks->index);
+  const uint16_t b1 = ks->index[where];
+  const uint16_t b2 = ks->index[ks->used];
+  memmove(&ks->index[ks->used], &ks->index[ks->used + 1], len);
+  ks->index[ks->size - 1] = b1;
+  ks->index[where] = b2;
+  ks->names[b2] = *name;
+  memset(&ks->names[b1], 0, sizeof(ks->names[b1]));
+
+  if (blockno != NULL)
+    *blockno = b2;
+
+  if (hint != NULL)
+    *hint = where;
+
+  fsck(ks);
+
+  return HAL_OK;
+}
+
+/*
+ * Pick unused or least-recently-used slot in our in-memory cache.
+ *
+ * Updating lru values is caller's problem: if caller is using a cache
+ * slot as a temporary buffer and there's no point in caching the
+ * result, leave the lru values alone and the right thing will happen.
+ */
+
+static inline ks_block_t *cache_pick_lru(hal_ks_t *ks)
+{
+  uint32_t best_delta = 0;
+  int      best_index = 0;
+
+  for (int i = 0; i < ks->cache_size; i++) {
+
+    if (ks->cache[i].blockno == ~0)
+      return &ks->cache[i].block;
+
+    const unsigned delta = ks->cache_lru - ks->cache[i].lru;
+    if (delta > best_delta) {
+      best_delta = delta;
+      best_index = i;
+    }
+
+  }
+
+  ks->cache[best_index].blockno = ~0;
+  return &ks->cache[best_index].block;
+}
+
+/*
+ * Find a block in our in-memory cache; return block or NULL if not present.
+ */
+
+static inline ks_block_t *cache_find_block(const hal_ks_t * const ks, const unsigned blockno)
+{
+  for (int i = 0; i < ks->cache_size; i++)
+    if (ks->cache[i].blockno == blockno)
+      return &ks->cache[i].block;
+  return NULL;
+}
+
+/*
+ * Mark a block in our in-memory cache as being in current use.
+ */
+
+static inline void cache_mark_used(hal_ks_t *ks, const ks_block_t * const block, const unsigned blockno)
+{
+  for (int i = 0; i < ks->cache_size; i++) {
+    if (&ks->cache[i].block == block) {
+      ks->cache[i].blockno = blockno;
+      ks->cache[i].lru = ++ks->cache_lru;
+      return;
+    }
+  }
+}
+
+/*
+ * Release a block from the in-memory cache.
+ */
+
+static inline void cache_release(hal_ks_t *ks, const ks_block_t * const block)
+{
+  if (block != NULL)
+    cache_mark_used(block, ~0);
+}
+
+/*
+ * Generate CRC-32 for a block.
+ *
+ * This function needs to understand the structure of
+ * ks_block_header_t, so that it can skip over fields that
+ * shouldn't be included in the CRC.
+ */
+
+static hal_crc32_t calculate_block_crc(const ks_block_t * const block)
+{
+  hal_crc32_t crc = hal_crc32_init();
+
+  if (block != NULL) {
+
+    crc = hal_crc32_update(crc,  &block->header.block_type,
+                           sizeof(block->header.block_type));
+
+    crc = hal_crc32_update(crc,
+                           block->bytes   + sizeof(ks_block_header_t),
+                           sizeof(*block) - sizeof(ks_block_header_t));
+  }
+
+  return hal_crc32_finalize(crc);
+}
+
+/*
+ * Read a block using the cache.  Marking the block as used is left
+ * for the caller, so we can avoid blowing out the cache when we
+ * perform a ks_match() operation.
+ */
+
+static hal_error_t block_read_cached(hal_ks_t *ks, const unsigned blockno, ks_block_t **block)
+{
+  if (block == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  if ((*block = cache_find_block(ks, blockno)) != NULL)
+    return HAL_OK;
+
+  if ((*block = cache_pick_lru(ks)) == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  return block_read(ks, blockno, *block);
+}
+
+/*
+ * Update one block, including zombie jamboree.
+ */
+
+static hal_error_t block_update(hal_ks_t *ks,
+                                const unsigned b1,
+                                ks_block_t *block,
+                                const hal_uuid_t * const uuid,
+                                int *hint)
+{
+  if (block == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  if (ks->used == ks->size)
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+  cache_release(block);
+
+  hal_error_t err;
+  unsigned b2;
+
+  if ((err = block_deprecate(ks, b1))                   != HAL_OK ||
+      (err = hal_ks_index_replace(ks, uuid, &b2, hint)) != HAL_OK ||
+      (err = block_write(ks, b2, block))                != HAL_OK ||
+      (err = block_zero(ks, b1))                        != HAL_OK)
+    return err;
+
+  cache_mark_used(ks, block, b2);
+
+  /*
+   * Erase the first block in the free list. In case of restart, this
+   * puts the block back at the head of the free list.
+   */
+
+  return block_erase_maybe(ks, ks->index[ks->used]);
+}
+
+/*
+ * Initialize keystore.  This includes various tricky bits, some of
+ * which attempt to preserve the free list ordering across reboots, to
+ * improve our simplistic attempt at wear leveling, others attempt to
+ * recover from unclean shutdown.
+ */
+
+static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size)
+{
+  if (mem == NULL || *mem == NULL || len == NULL || size > *len)
+    return NULL;
+  void *ret = *mem;
+  *mem += size;
+  *len -= size;
+  return ret;
+}
+
+#warning Call ks_alloc_common() and ks_init_common() while holding hal_ks_lock(); !
+
+hal_error_t ks_alloc_common(hal_ks_t *ks, const unsigned ks_blocks, const unsigned cache_blocks)
+{
+  /*
+   * We allocate a single big chunk of memory rather than three
+   * smaller chunks to make it atomic.  We need all three, so this way
+   * either all succeed or all fail.
+   */
+
+  size_t len = (sizeof(*ks->index) * ks_blocks +
+                sizeof(*ks->names) * ks_blocks +
+                sizeof(*ks->cache) * cache_blocks);
+
+  uint8_t *mem = hal_allocate_static_memory(len);
+
+  if (mem == NULL)
+    return HAL_ERROR_ALLOCATION_FAILURE;
+
+  memset(ks,  0, sizeof(*ks));
+  memset(mem, 0, len);
+
+  ks->index = gnaw(&mem, &len, sizeof(*ks->index) * ks_blocks);
+  ks->names = gnaw(&mem, &len, sizeof(*ks->names) * ks_blocks);
+  ks->cache = gnaw(&mem, &len, sizeof(*ks->cache) * cache_blocks);
+
+  ks->size       = ks_blocks;
+  ks->cache_size = cache_blocks;
+
+  return HAL_OK;
+}
+
+hal_error_t ks_init_common(hal_ks_t *ks, const hal_ks_driver_t * const driver)
+{
+  if (ks->index == NULL || ks->names == NULL || ks->cache == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  ks->used = 0;
+
+  for (int i = 0; i < ks->cache_size; i++)
+    ks->cache[i].blockno = ~0;
+
+  /*
+   * Scan existing content of keystore to figure out what we've got.
+   * This gets a bit involved due to the need to recover from things
+   * like power failures at inconvenient times.
+   */
+
+  ks_block_type_t   block_types[ks->size];
+  ks_block_status_t block_status[ks->size];
+  ks_block_t *block = cache_pick_lru(ks);
+  int first_erased = -1;
+  hal_error_t err;
+  uint16_t n = 0;
+
+  if (block == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  for (int i = 0; i < ks->size; i++) {
+
+    /*
+     * Read one block.  If the CRC is bad or the block type is
+     * unknown, it's old data we don't understand, something we were
+     * writing when we crashed, or bad flash; in any of these cases,
+     * we want the block to end up near the end of the free list.
+     */
+
+    err = block_read(ks, i, block);
+
+    if (err == HAL_ERROR_KEYSTORE_BAD_CRC || err == HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE)
+      block_types[i] = BLOCK_TYPE_UNKNOWN;
+
+    else if (err == HAL_OK)
+      block_types[i] = block_get_type(block);
+
+    else
+      return err;
+
+    switch (block_types[i]) {
+    case BLOCK_TYPE_KEY:
+    case BLOCK_TYPE_PIN:
+      block_status[i] = block_get_status(block);
+      break;
+    default:
+      block_status[i] = BLOCK_STATUS_UNKNOWN;
+    }
+
+    /*
+     * First erased block we see is head of the free list.
+     */
+
+    if (block_types[i] == BLOCK_TYPE_ERASED && first_erased < 0)
+      first_erased = i;
+
+    /*
+     * If it's a valid data block, include it in the index.  We remove
+     * tombstones (if any) below, for now it's easiest to include them
+     * in the index, so we can look them up by name if we must.
+     */
+
+    const hal_uuid_t *uuid = NULL;
+
+    switch (block_types[i]) {
+    case BLOCK_TYPE_KEY:        uuid = &block->key.name;        break;
+    case BLOCK_TYPE_PIN:        uuid = &pin_uuid;               break;
+    default:                    /* Keep GCC happy */            break;
+    }
+
+    if (uuid != NULL) {
+      ks->names[i] = *uuid;
+      ks->index[n++] = i;
+    }
+  }
+
+  ks->used = n;
+
+  if (ks->used > ks->size)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  /*
+   * At this point we've built the (unsorted) index from all the valid
+   * blocks.  Now we need to insert free and unrecognized blocks into
+   * the free list in our preferred order.  It's possible that there's
+   * a better way to do this than linear scan, but this is just
+   * integer comparisons in a fairly small data set, so it's probably
+   * not worth trying to optimize.
+   */
+
+  if (n < ks->size)
+    for (int i = 0; i < ks->size; i++)
+      if (block_types[i] == BLOCK_TYPE_ERASED)
+        ks->index[n++] = i;
+
+  if (n < ks->size)
+    for (int i = first_erased; i < ks->size; i++)
+      if (block_types[i] == BLOCK_TYPE_ZEROED)
+        ks->index[n++] = i;
+
+  if (n < ks->size)
+    for (int i = 0; i < first_erased; i++)
+      if (block_types[i] == BLOCK_TYPE_ZEROED)
+        ks->index[n++] = i;
+
+  if (n < ks->size)
+    for (int i = 0; i < ks->size; i++)
+      if (block_types[i] == BLOCK_TYPE_UNKNOWN)
+        ks->index[n++] = i;
+
+  if (ks->used > ks->size)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  /*
+   * Sort the index, then deal with tombstones.  Tombstones are blocks
+   * left behind when something bad (like a power failure) happened
+   * while we updating.  There can be at most one tombstone and one
+   * live block for a given UUID.  If we find no live block, we need
+   * to restore it from the tombstone, after which we need to zero the
+   * tombstone in either case.  The sequence of operations while
+   * updating is designed so that, barring a bug or a hardware
+   * failure, we should never lose data.
+   */
+
+  ks_heapsort(ks);
+
+  for (unsigned b_tomb = 0; b_tomb < ks->size; b_tomb++) {
+
+    if (block_status[b_tomb] != BLOCK_STATUS_TOMBSTONE)
+      continue;
+
+    hal_uuid_t name = ks->names[b_tomb];
+
+    int where = -1;
+
+    if ((err = hal_ks_index_find(ks, &name, NULL, &where)) != HAL_OK)
+      return err;
+
+    if (b_tomb != ks->index[where]) {
+      if (ks->used > where + 1 && b_tomb == ks->index[where + 1])
+        where = where + 1;
+      else if (0     <= where - 1 && b_tomb == ks->index[where - 1])
+        where = where - 1;
+      else
+        return HAL_ERROR_IMPOSSIBLE;
+    }
+
+    const int matches_next = where + 1 < ks->used && !hal_uuid_cmp(&name, &ks->names[ks->index[where + 1]]);
+    const int matches_prev = where - 1 >= 0       && !hal_uuid_cmp(&name, &ks->names[ks->index[where - 1]]);
+    
+    if ((matches_prev && matches_next) ||
+        (matches_prev && block_status[ks->index[b_tomb - 1]] != BLOCK_STATUS_LIVE) ||
+        (matches_next && block_status[ks->index[b_tomb + 1]] != BLOCK_STATUS_LIVE))
+      return HAL_ERROR_IMPOSSIBLE;
+
+    if (matches_prev || matches_next)  {
+      memmove(&ks->index[where], &ks->index[where + 1], (ks->size - where - 1) * sizeof(*ks->index));
+      ks->index[ks->size - 1] = b_tomb;
+    }
+
+    else {
+      unsigned b_live;
+      if ((err = block_read(ks, b_tomb, block)) != HAL_OK)
+        return err;
+      block->header.block_status = BLOCK_STATUS_LIVE;
+      if ((err = hal_ks_index_replace(ks, &name, &b_live, &where)) != HAL_OK ||
+          (err = block_write(ks, b_live, block)) != HAL_OK)
+        return err;
+      block_status[b_live] = BLOCK_STATUS_LIVE;
+    }
+
+    if ((err = block_zero(ks, b_tomb)) != HAL_OK)
+      return err;
+    block_types[ b_tomb] = BLOCK_TYPE_ZEROED;
+    block_status[b_tomb] = BLOCK_STATUS_UNKNOWN;
+  }
+
+  /*
+   * Erase first block on free list if it's not already erased.
+   */
+
+  if (ks->used < ks->size &&
+      (err = block_erase_maybe(ks, ks->index[ks->used])) != HAL_OK)
+    return err;
+
+  /*
+   * And we're finally done.
+   */
+
+  ks->driver = driver;
+
+  return HAL_OK;
+}
+
+static inline int acceptable_key_type(const hal_key_type_t type)
+{
+  switch (type) {
+  case HAL_KEY_TYPE_RSA_PRIVATE:
+  case HAL_KEY_TYPE_EC_PRIVATE:
+  case HAL_KEY_TYPE_RSA_PUBLIC:
+  case HAL_KEY_TYPE_EC_PUBLIC:
+    return 1;
+  default:
+    return 0;
+  }
+}
+
+hal_error_t ks_store(hal_ks_t *ks,
+                     hal_pkey_slot_t *slot,
+                     const uint8_t * const der, const size_t der_len)
+{
+  if (ks == NULL || slot == NULL || der == NULL || der_len == 0 || !acceptable_key_type(slot->type))
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err = HAL_OK;
+  ks_block_t *block;
+  flash_key_block_t *k;
+  uint8_t kek[KEK_LENGTH];
+  size_t kek_len;
+  unsigned b;
+
+  hal_ks_lock();
+
+  if ((block = cache_pick_lru(ks)) == NULL) {
+    err = HAL_ERROR_IMPOSSIBLE;
+    goto done;
+  }
+
+  k = &block->key;
+
+  if ((err = hal_ks_index_add(ks, &slot->name, &b, &slot->hint)) != HAL_OK)
+    goto done;
+
+  cache_mark_used(ks, block, b);
+
+  memset(block, 0xFF, sizeof(*block));
+
+  block->header.block_type   = BLOCK_TYPE_KEY;
+  block->header.block_status = BLOCK_STATUS_LIVE;
+
+  k->name    = slot->name;
+  k->type    = slot->type;
+  k->curve   = slot->curve;
+  k->flags   = slot->flags;
+  k->der_len = SIZEOF_FLASH_KEY_BLOCK_DER;
+  k->attributes_len = 0;
+
+  if (ks->used < ks->size)
+    err = block_erase_maybe(ks, ks->index[ks->used]);
+
+  if (err == HAL_OK)
+    err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek));
+
+  if (err == HAL_OK)
+    err = hal_aes_keywrap(NULL, kek, kek_len, der, der_len, k->der, &k->der_len);
+
+  memset(kek, 0, sizeof(kek));
+
+  if (err == HAL_OK)
+    err = block_write(ks, b, block);
+
+  if (err == HAL_OK)
+    goto done;
+
+  memset(block, 0, sizeof(*block));
+  cache_release(ks, block);
+  (void) hal_ks_index_delete(ks, &slot->name, NULL, &slot->hint);
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+static hal_error_t ks_fetch(hal_ks_t *ks,
+                            hal_pkey_slot_t *slot,
+                            uint8_t *der, size_t *der_len, const size_t der_max)
+{
+  if (ks == NULL || slot == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err = HAL_OK;
+  ks_block_t *block;
+  unsigned b;
+
+  hal_ks_lock();
+
+  if ((err = hal_ks_index_find(ks, &slot->name, &b, &slot->hint)) != HAL_OK ||
+      (err = block_read_cached(ks, b, &block))                    != HAL_OK)
+    goto done;
+
+  if (block_get_type(block) != BLOCK_TYPE_KEY) {
+    err = HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
+    goto done;
+  }
+
+  cache_mark_used(ks, block, b);
+
+  flash_key_block_t *k = &block->key;
+
+  slot->type  = k->type;
+  slot->curve = k->curve;
+  slot->flags = k->flags;
+
+  if (der == NULL && der_len != NULL)
+    *der_len = k->der_len;
+
+  if (der != NULL) {
+
+    uint8_t kek[KEK_LENGTH];
+    size_t kek_len, der_len_;
+    hal_error_t err;
+
+    if (der_len == NULL)
+      der_len = &der_len_;
+
+    *der_len = der_max;
+
+    if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
+      err = hal_aes_keyunwrap(NULL, kek, kek_len, k->der, k->der_len, der, der_len);
+
+    memset(kek, 0, sizeof(kek));
+  }
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+static hal_error_t ks_delete(hal_ks_t *ks,
+                             hal_pkey_slot_t *slot)
+{
+  if (ks == NULL || slot == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err = HAL_OK;
+  unsigned b;
+
+  hal_ks_lock();
+
+  if ((err = hal_ks_index_delete(ks, &slot->name, &b, &slot->hint)) != HAL_OK)
+    goto done;
+
+  cache_release(ks, cache_find_block(ks, b));
+
+  if ((err = block_zero(ks, b)) != HAL_OK)
+    goto done;
+
+  err = block_erase_maybe(ks, ks->index[ks->used]);
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+static inline hal_error_t locate_attributes(ks_block_t *block,
+                                            uint8_t **bytes, size_t *bytes_len,
+                                            unsigned **attrs_len)
+{
+  if (block == NULL || bytes == NULL || bytes_len == NULL || attrs_len == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+
+  if (block_get_type(block) != BLOCK_TYPE_KEY)
+    return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE;
+  *attrs_len = &block->key.attributes_len;
+  *bytes = block->key.der + block->key.der_len;
+  *bytes_len = SIZEOF_FLASH_KEY_BLOCK_DER - block->key.der_len;
+
+  return HAL_OK;
+}
+
+static hal_error_t ks_match(hal_ks_t *ks,
+                            const hal_client_handle_t client,
+                            const hal_session_handle_t session,
+                            const hal_key_type_t type,
+                            const hal_curve_name_t curve,
+                            const hal_key_flags_t mask,
+                            const hal_key_flags_t flags,
+                            const hal_pkey_attribute_t *attributes,
+                            const unsigned attributes_len,
+                            hal_uuid_t *result,
+                            unsigned *result_len,
+                            const unsigned result_max,
+                            const hal_uuid_t * const previous_uuid)
+{
+  if (ks == NULL || (attributes == NULL && attributes_len > 0) ||
+      result == NULL || result_len == NULL || previous_uuid == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err = HAL_OK;
+  ks_block_t *block;
+  int i = -1;
+
+  hal_ks_lock();
+
+  *result_len = 0;
+
+  err = hal_ks_index_find(ks, previous_uuid, NULL, &i);
+
+  if (err == HAL_ERROR_KEY_NOT_FOUND)
+    i--;
+  else if (err != HAL_OK)
+    goto done;
+
+  while (*result_len < result_max && ++i < ks->used) {
+
+    unsigned b = ks->index[i];
+
+    if ((err = block_read_cached(ks, b, &block)) != HAL_OK)
+      goto done;
+
+    if ((type  != HAL_KEY_TYPE_NONE && type  != block->key.type)  ||
+        (curve != HAL_CURVE_NONE    && curve != block->key.curve) ||
+        ((flags ^ block->key.flags) & mask)  != 0)
+      continue;
+
+    if (attributes_len > 0) {
+      uint8_t need_attr[attributes_len];
+      uint8_t *bytes = NULL;
+      size_t bytes_len = 0;
+      unsigned *attrs_len;
+      int possible = 1;
+
+      memset(need_attr, 1, sizeof(need_attr));
+
+      if ((err = locate_attributes(block, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+        goto done;
+
+      if (*attrs_len > 0) {
+        hal_pkey_attribute_t attrs[*attrs_len];
+
+        if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
+          goto done;
+
+        for (int j = 0; possible && j < attributes_len; j++) {
+
+          if (!need_attr[j])
+            continue;
+
+          for (hal_pkey_attribute_t *a = attrs; a < attrs + *attrs_len; a++) {
+            if (a->type != attributes[j].type)
+              continue;
+            need_attr[j] = 0;
+            possible = (a->length == attributes[j].length &&
+                        !memcmp(a->value, attributes[j].value, a->length));
+            break;
+          }
+        }
+      }
+
+      if (!possible || memchr(need_attr, 1, sizeof(need_attr)) != NULL)
+        continue;
+    }
+
+    result[*result_len] = ks->names[b];
+    ++*result_len;
+  }
+
+  err = HAL_OK;
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+static  hal_error_t ks_set_attributes(hal_ks_t *ks,
+                                      hal_pkey_slot_t *slot,
+                                      const hal_pkey_attribute_t *attributes,
+                                      const unsigned attributes_len)
+{
+  if (ks == NULL || slot == NULL || attributes == NULL || attributes_len == 0)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err = HAL_OK;
+  ks_block_t *block;
+  unsigned b;
+
+  hal_ks_lock();
+
+  {
+    if ((err = hal_ks_index_find(ks, &slot->name, &b, &slot->hint)) != HAL_OK ||
+        (err = block_read_cached(ks, b, &block))                    != HAL_OK)
+      goto done;
+
+    cache_mark_used(ks, block, b);
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned *attrs_len;
+
+    if ((err = locate_attributes(block, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+      goto done;
+
+    hal_pkey_attribute_t attrs[*attrs_len + attributes_len];
+    size_t total;
+
+    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
+      goto done;
+
+    for (int i = 0; err == HAL_OK && i < attributes_len; i++)
+      if (attributes[i].length == HAL_PKEY_ATTRIBUTE_NIL)
+        err = hal_ks_attribute_delete(bytes, bytes_len, attrs, attrs_len, &total,
+                                      attributes[i].type);
+      else
+        err = hal_ks_attribute_insert(bytes, bytes_len, attrs, attrs_len, &total,
+                                      attributes[i].type,
+                                      attributes[i].value,
+                                      attributes[i].length);
+
+    if (err == HAL_OK)
+      err = block_update(ks, b, block, &slot->name, &slot->hint);
+    else
+      cache_release(ks, block);
+  }
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+static  hal_error_t ks_get_attributes(hal_ks_t *ks,
+                                      hal_pkey_slot_t *slot,
+                                      hal_pkey_attribute_t *attributes,
+                                      const unsigned attributes_len,
+                                      uint8_t *attributes_buffer,
+                                      const size_t attributes_buffer_len)
+{
+  if (ks == NULL || slot == NULL || attributes == NULL || attributes_len == 0 ||
+      attributes_buffer == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  for (int i = 0; i < attributes_len; i++) {
+    attributes[i].length = 0;
+    attributes[i].value  = NULL;
+  }
+
+  uint8_t *abuf = attributes_buffer;
+  ks_block_t *block = NULL;
+  hal_error_t err = HAL_OK;
+  unsigned found = 0;
+  unsigned b;
+
+  hal_ks_lock();
+
+  {
+    if ((err = hal_ks_index_find(ks, &slot->name, &b, &slot->hint)) != HAL_OK ||
+        (err = block_read_cached(ks, b, &block))                    != HAL_OK)
+      goto done;
+
+    cache_mark_used(ks, block, b);
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned *attrs_len;
+
+    if ((err = locate_attributes(block, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+      goto done;
+
+    if (*attrs_len == 0) {
+      err = HAL_ERROR_ATTRIBUTE_NOT_FOUND;
+      goto done;
+    }
+
+    hal_pkey_attribute_t attrs[*attrs_len];
+
+    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
+      goto done;
+
+    for (int i = 0; i < attributes_len; i++) {
+
+      if (attributes[i].length > 0)
+        continue;
+
+      int j = 0;
+      while (j < *attrs_len && attrs[j].type != attributes[i].type)
+        j++;
+      if (j >= *attrs_len)
+        continue;
+      found++;
+
+      attributes[i].length = attrs[j].length;
+
+      if (attributes_buffer_len == 0)
+        continue;
+
+      if (attrs[j].length > attributes_buffer + attributes_buffer_len - abuf) {
+        err = HAL_ERROR_RESULT_TOO_LONG;
+        goto done;
+      }
+
+      memcpy(abuf, attrs[j].value, attrs[j].length);
+      attributes[i].value  = abuf;
+      abuf += attrs[j].length;
+    }
+
+  };
+
+  if (found < attributes_len && attributes_buffer_len > 0)
+    err = HAL_ERROR_ATTRIBUTE_NOT_FOUND;
+  else
+    err = HAL_OK;
+
+ done:
+  hal_ks_unlock();
+  return err;
+}
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/ks.h b/ks.h
new file mode 100644
index 0000000..ff6d382
--- /dev/null
+++ b/ks.h
@@ -0,0 +1,241 @@
+// Notes towards unified keystore code (drivers become just low-level
+// "disk" I/O and perhaps a bit of local init/shutdown).
+//
+// Most of the structure definitions in ks_flash.c and ks_volatile.c
+// become common and go in ks.h (or wherever, but probably be enough
+// stuff that separate .h file might be easier to read).
+//
+// We already have
+//
+//     typedef struct hal_ks hal_ks_t;
+//
+// which we "subclass" to get ks_t (ks_volatile) and db_t (ks_flash).
+// We can move more common stuff there.
+//
+// flash_block_t (etc) becomes ks_block_t (etc) as these data
+// structures will be used by all keystores, not just flash.
+//
+// We might want to fold hal_ks_index_t into hal_ks_t as everything
+// will be using it.  Then again, it's relatively harmless as it is, a
+// bit more verbose trading for a bit more isolation.  Probably go for
+// less verbose, for readability.
+//
+// Each keystore will still have some weird private stuff, like the
+// RAM for the keys themselves in the volatile case and the PIN stuff
+// in the flash case.
+//
+// The ks_flash cache, however, probably wants to become common code.
+// Yes we could get a bit more efficient if we skipped caching in the
+// volatile case, but that's not our bottleneck and there are some
+// cases where the code relies on knowing that mucking with the cache
+// copy is harmless until we write the block to "disk", don't want to
+// mess with that, so keep the flash model for volatile.  Cache size
+// will need to become another hal_ks_t field.
+//
+// Don't remember exactly where we're doing the "subclassing" casts,
+// should be easy enough to find...except that ks_flash is mostly
+// ignoring that argument and using the static db variable directly.
+// ks_volatile may be closer to write on this point, as it already had
+// ks_to_ksv().  But most of the code will be in a driver-agnostic
+// ks.c (or whatever) and will be calling functions that care through
+// the driver, maybe this doesn't matter very much.
+//
+// Tedious though it sounds, might be simplest just to check each
+// function in ks_*.c to see whether it moves to ks.[ch] or becomes
+// something called by the new lower-level driver API.  Need a sketch
+// of the lower-level driver API, chicken and egg there but probably
+// is init(), shutdown(), block_read(), block_deprecate(),
+// block_zero(), block_erase(), block_erase_maybe(), block-write().
+// Possible that some of these don't really need to be driver, was
+// mostly basing this on which things in ks_flash touch flash
+// directly-ish via the keystore_*() functions.
+//
+// Would be nice if we can make the API regular enough (inline
+// functions?) that user need not really care which functions are
+// driver-specific and which are layered on top, but that may be
+// impractical (or silly).
+//
+// Hmm, hal_ks_open() and hal_ks_close() don't quite fit new model,
+// what was I thinking there?  Not much, existing implementations just
+// use that to get back a (hal_ks_t*), so really just checking the
+// binding between driver and keystore object.
+//
+// I think this boils down to another instance of the confusion
+// between what in Python would be Keystore.__new__() and
+// Keystore.__init__().  This even sort of fits with the weird `alloc`
+// parameter in ks_init().
+//
+// Maybe we can trust C memory initialization enough to use a zeroed
+// static variable as test for whether a keystore has been
+// initialized, and just have the low-level (driver) methods check
+// that and fail if trying to use an uninitialized keystore?
+//
+// Pythonesque view might be the right way to handle ks_init(0 and
+// ks_shutdown() too: in most cases we have inline functions which
+// call the driver function, but for these methods the subclass needs
+// to extend the abstract method, which translates, in C, to the
+// generic method calling the driver method of the same name at the
+// right time.  Not quite what Python does but close enough.
+
+
+#ifndef _KS_H_
+#define _KS_H_
+
+#include "hal.h"
+#include "hal_internal.h"
+
+/*
+ * Size of a keystore "block".
+ *
+ * This must be an integer multiple of the flash subsector size, among
+ * other reasons because that's the minimum erasable unit.
+ */
+
+#ifndef HAL_KS_BLOCK_SIZE
+#define HAL_KS_BLOCK_SIZE       (KEYSTORE_SUBSECTOR_SIZE * 1)
+#endif
+
+/*
+ * Known block states.
+ *
+ * C does not guarantee any particular representation for enums, so
+ * including enums directly in the block header isn't safe.  Instead,
+ * we use an access method which casts when reading from the header.
+ * Writing to the header isn't a problem, because C does guarantee
+ * that enum is compatible with *some* integer type, it just doesn't
+ * specify which one.
+ */
+
+typedef enum {
+  KS_BLOCK_TYPE_ERASED  = 0xFF, /* Pristine erased block (candidate for reuse) */
+  KS_BLOCK_TYPE_ZEROED  = 0x00, /* Zeroed block (recently used) */
+  KS_BLOCK_TYPE_KEY     = 0x55, /* Block contains key material */
+  KS_BLOCK_TYPE_PIN     = 0xAA, /* Block contains PINs */
+  KS_BLOCK_TYPE_UNKNOWN = -1,   /* Internal code for "I have no clue what this is" */
+} ks_block_type_t;
+
+/*
+ * Block status.
+ */
+
+typedef enum {
+  KS_BLOCK_STATUS_LIVE      = 0x66, /* This is a live block */
+  KS_BLOCK_STATUS_TOMBSTONE = 0x44, /* This is a tombstone left behind during an update  */
+  KS_BLOCK_STATUS_UNKNOWN   = -1,   /* Internal code for "I have no clue what this is" */
+} ks_block_status_t;
+
+/*
+ * Common header for all keystore block types.
+ * A few of these fields are deliberately omitted from the CRC.
+ */
+
+typedef struct {
+  uint8_t               block_type;
+  uint8_t               block_status;
+  hal_crc32_t           crc;
+} ks_block_header_t;
+
+/*
+ * Key block.  Tail end of "der" field (after der_len) used for attributes.
+ */
+
+typedef struct {
+  ks_block_header_t     header;
+  hal_uuid_t            name;
+  hal_key_type_t        type;
+  hal_curve_name_t      curve;
+  hal_key_flags_t       flags;
+  size_t                der_len;
+  unsigned              attributes_len;
+  uint8_t               der[];  /* Must be last field -- C99 "flexible array member" */
+} ks_blockkey_block_t;
+
+#define SIZEOF_KS_BLOCKKEY_BLOCK_DER \
+  (HAL_KS_BLOCK_SIZE - offsetof(ks_blockkey_block_t, der))
+
+/*
+ * PIN block.  Also includes space for backing up the KEK when
+ * HAL_MKM_FLASH_BACKUP_KLUDGE is enabled.
+ */
+
+typedef struct {
+  ks_block_header_t     header;
+  hal_ks_pin_t          wheel_pin;
+  hal_ks_pin_t          so_pin;
+  hal_ks_pin_t          user_pin;
+#if HAL_MKM_FLASH_BACKUP_KLUDGE
+  uint32_t              kek_set;
+  uint8_t               kek[KEK_LENGTH];
+#endif
+} ks_blockpin_block_t;
+
+#define FLASH_KEK_SET   0x33333333
+
+/*
+ * One keystore block.
+ */
+
+typedef union {
+  uint8_t               bytes[HAL_KS_BLOCK_SIZE];
+  ks_block_header_t     header;
+  ks_blockkey_block_t   key;
+  ks_blockpin_block_t   pin;
+} ks_block_t;
+
+/*
+ * In-memory cache.
+ */
+
+typedef struct {
+  unsigned              blockno;
+  unsigned              lru;
+  ks_block_t            block;
+} ks_cache_block_t;
+
+/*
+ * Medium-specific driver and in-memory database.
+ *
+ * The top-level structure is a static variable; the arrays are
+ * allocated at runtime using hal_allocate_static_memory() because
+ * they can get kind of large.
+ *
+ * Driver-specific stuff is handled by a form of subclassing: the
+ * driver embeds the hal_ks_t structure at the head of whatever else
+ * it needs, and performs (controlled, type-safe) casts as needed.
+ */
+
+typedef struct hal_ks_driver    hal_ks_driver_t;
+typedef struct hal_ks           hal_ks_t;
+
+struct hal_ks {
+  const hal_ks_driver_t *driver;
+  unsigned size;                /* Blocks in keystore */
+  unsigned used;                /* How many blocks are in use */
+  uint16_t *index;              /* Index/freelist array */
+  hal_uuid_t *names;            /* Keyname array */
+  unsigned cache_lru;           /* Cache LRU counter */
+  unsigned cache_size;          /* Size (how many blocks) in cache */
+  ks_cache_block_t *cache;      /* Cache */
+  int per_session;              /* Whether objects have per-session semantics (PKCS #11, sigh) */
+};
+
+struct hal_ks_driver {
+  hal_error_t (*init)           (hal_ks_t *, const int alloc);
+  hal_error_t (*shutdown)       (hal_ks_t *);
+  hal_error_t (*read)           (hal_ks_t *, const unsigned blockno, ks_block_t *);
+  hal_error_t (*write)          (hal_ks_t *, const unsigned blockno, ks_block_t *)
+  hal_error_t (*deprecate)      (hal_ks_t *, const unsigned blockno);
+  hal_error_t (*zero)           (hal_ks_t *, const unsigned blockno);
+  hal_error_t (*erase)          (hal_ks_t *, const unsigned blockno);
+  hal_error_t (*erase_maybe)    (hal_ks_t *, const unsigned blockno);
+  hal_error_t (*get_owner)      (hal_ks_t *, const unsigned blockno,       hal_client_handle_t *,       hal_session_handle_t *);
+  hal_error_t (*set_owner)      (hal_ks_t *, const unsigned blockno, const hal_client_handle_t,   const hal_session_handle_t);
+};
+
+#endif /* _KS_H_ */
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */