Multi-block object support in keystore.

The main reason for supporting multi-block objects is to allow the
PKCS #11 code to attach more attributes than will fit comfortably in a
single flash block.  This may turn out to be unnecessary once we've
fleshed out the attribute storage and retrieval code; if so, we can
simplify the code, but this way the keystore won't impose arbitrary
(and somewhat inscrutable) size limits on PKCS #11 attributes for
large keys.

This snapshot passes light testing (PKCS #11 "make test" runs), but
the tombstone recovery code in ks_init() is a bit involved, and needs
more testing with simulated failures (probably induced under GDB).

5 files changed, 350 insertions, 143 deletions

diff --git a/hal.h b/hal.h
index 4e69981..e94f3b8 100644
--- a/hal.h
+++ b/hal.h
@@ -146,6 +146,7 @@
   DEFINE_HAL_ERROR(HAL_ERROR_KS_DRIVER_NOT_FOUND,       "Keystore driver not found")                    \
   DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_BAD_CRC,          "Bad CRC in keystore")                          \
   DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE,   "Unsupported keystore block type")              \
+  DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_LOST_DATA,        "Keystore appears to have lost data")           \
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
diff --git a/hal_internal.h b/hal_internal.h
index ef0d763..11f9898 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -584,32 +584,34 @@ static inline hal_error_t hal_ks_list(hal_ks_t *ks,
  * support a simplistic form of wear leveling in flash-based keystores.
  *
  * Key names are kept in a separate array, indexed by block number.
+ * Key names here are a composite of the key's UUID and a "chunk"
+ * number; the latter allows storage of keys whose total size exceeds
+ * one block (whatever a block is).  For the moment we keep the UUID
+ * and the chunk number in a single array, which may provide (very)
+ * slightly better performance due to reference locality in SDRAM, but
+ * this may change if we need to reclaim the space wasted by structure
+ * size rounding.
  *
- * The all-ones UUID, which (by definition) cannot be a valid key
+ * The all-zeros 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 {
+  hal_uuid_t name;              /* Key name */
+  uint8_t chunk;                /* Key chunk number */
+} hal_ks_name_t;
+
+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_name_t *names;         /* Keyname array */
 } hal_ks_index_t;
 
 /*
@@ -629,21 +631,37 @@ extern hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi);
  */
 extern hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
                                      const hal_uuid_t * const name,
-                                     unsigned *blockno);
+                                     const unsigned chunk,
+                                     unsigned *blockno,
+                                     int *hint);
+
+/*
+ * Find all the blocks in a key, return the block numbers.
+ */
+extern hal_error_t hal_ks_index_find_range(hal_ks_index_t *ksi,
+                                           const hal_uuid_t * const name,
+                                           const unsigned max_blocks,
+                                           unsigned *n_blocks,
+                                           unsigned *blocknos,
+                                           int *hint);
 
 /*
  * 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);
+                                    const unsigned chunk,
+                                    unsigned *blockno,
+                                    int *hint);
 
 /*
  * 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);
+                                       const unsigned chunk,
+                                       unsigned *blockno,
+                                       int *hint);
 
 /*
  * Replace a key block with a new one, return new block number.
@@ -653,7 +671,9 @@ extern hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
 
 extern hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
                                         const hal_uuid_t * const name,
-                                        unsigned *blockno);
+                                        const unsigned chunk,
+                                        unsigned *blockno,
+                                        int *hint);
 
 /*
  * RPC lowest-level send and receive routines. These are blocking, and
diff --git a/ks_flash.c b/ks_flash.c
index df3b89b..475dcde 100644
--- a/ks_flash.c
+++ b/ks_flash.c
@@ -60,8 +60,8 @@
 typedef enum {
   BLOCK_TYPE_ERASED  = 0xFF, /* Pristine erased block (candidate for reuse) */
   BLOCK_TYPE_ZEROED  = 0x00, /* Zeroed block (recently used) */
-  BLOCK_TYPE_KEYBLK  = 0x55, /* Block contains key material */
-  BLOCK_TYPE_PINBLK  = 0xAA, /* Block contains PINs */
+  BLOCK_TYPE_KEY     = 0x55, /* Block contains key material */
+  BLOCK_TYPE_PIN     = 0xAA, /* Block contains PINs */
   BLOCK_TYPE_UNKNOWN = -1,   /* Internal code for "I have no clue what this is" */
 } flash_block_type_t;
 
@@ -325,8 +325,8 @@ static hal_error_t block_read(const unsigned blockno, flash_block_t *block)
   case BLOCK_TYPE_ERASED:
   case BLOCK_TYPE_ZEROED:
     return HAL_OK;
-  case BLOCK_TYPE_KEYBLK:
-  case BLOCK_TYPE_PINBLK:
+  case BLOCK_TYPE_KEY:
+  case BLOCK_TYPE_PIN:
     break;
   default:
     return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
@@ -474,8 +474,8 @@ static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
     return err;
 
   switch (block_get_type(block)) {
-  case BLOCK_TYPE_KEYBLK:
-  case BLOCK_TYPE_PINBLK:
+  case BLOCK_TYPE_KEY:
+  case BLOCK_TYPE_PIN:
     block->header.crc = calculate_block_crc(block);
     break;
   default:
@@ -490,9 +490,16 @@ static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
 }
 
 /*
- * Initialize keystore.  This includes some tricky bits that attempt
- * to preserve the free list ordering across reboots, to improve our
- * simplistic attempt at wear leveling.
+ * Forward reference.
+ */
+
+static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block);
+
+/*
+ * 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 hal_error_t ks_init(const hal_ks_driver_t * const driver)
@@ -531,7 +538,6 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
   flash_block_status_t block_status[NUM_FLASH_BLOCKS];
   flash_block_t *block = cache_pick_lru();
   int first_erased = -1;
-  int saw_pins = 0;
   hal_error_t err;
   uint16_t n = 0;
 
@@ -558,7 +564,7 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
     else
       return err;
 
-    if (block_types[i] == BLOCK_TYPE_KEYBLK || block_types[i] == BLOCK_TYPE_PINBLK)
+    if (block_types[i] == BLOCK_TYPE_KEY || block_types[i] == BLOCK_TYPE_PIN)
       block_status[i] = block_get_status(block);
     else
       block_status[i] = BLOCK_STATUS_UNKNOWN;
@@ -571,32 +577,17 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
       first_erased = i;
 
     /*
-     * If it is or was a key block, remember its name.
-     * PIN blocks get the all-zeros UUID for ks_index purposes.
-     */
-
-    if (block_types[i] == BLOCK_TYPE_KEYBLK)
-      db.ksi.names[i] = block->key.name;
-
-    /*
-     * If it is or was a PIN block, remember the PINs, but don't
-     * overwrite PINs from a current PIN block with PINs from a
-     * deprecated PIN block.
+     * 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.
      */
 
-    if (block_types[i] == BLOCK_TYPE_PINBLK && (!saw_pins || block_status[i] == BLOCK_STATUS_LIVE)) {
-      db.wheel_pin = block->pin.wheel_pin;
-      db.so_pin    = block->pin.so_pin;
-      db.user_pin  = block->pin.user_pin;
-      saw_pins = 1;
+    if (block_types[i] == BLOCK_TYPE_KEY || block_types[i] == BLOCK_TYPE_PIN) {
+      db.ksi.names[i].name = block_types[i] == BLOCK_TYPE_KEY ? block->key.name : pin_uuid;
+      db.ksi.names[i].chunk = block->header.this_chunk;
+      db.ksi.index[n++] = i;
     }
 
-    /*
-     * If it's a current block, include it in the index.
-     */
-
-    if (block_status[i] == BLOCK_STATUS_LIVE)
-      db.ksi.index[n++] = i;
   }
 
   db.ksi.used = n;
@@ -604,12 +595,12 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
   assert(db.ksi.used <= db.ksi.size);
 
   /*
-   * At this point we've built the (unsorted) index from all the
-   * current blocks.  Now we need to insert free, deprecated, and
-   * unrecognized blocks into the free list in our preferred order.
-   * There's probably a more efficient way to do this, but this is
-   * just integer comparisons in a fairly small data set, so all of
-   * these loops should be pretty fast.
+   * 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 < db.ksi.size)
@@ -629,29 +620,45 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
 
   if (n < db.ksi.size)
     for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
-      if (block_status[i] == BLOCK_STATUS_TOMBSTONE)
-        db.ksi.index[n++] = i;
-
-  if (n < db.ksi.size)
-    for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
       if (block_types[i] == BLOCK_TYPE_UNKNOWN)
         db.ksi.index[n++] = i;
 
   assert(n == db.ksi.size);
 
   /*
-   * Initialize the ks_index stuff.
+   * Initialize the index.
    */
 
   if ((err = hal_ks_index_setup(&db.ksi)) != HAL_OK)
     return err;
 
   /*
-   * Deal with deprecated blocks.  These are tombstones left behind
-   * when something bad happened while we updating a block.  If write
-   * of the updated block completed, we have nothing to do other than
-   * cleaning up the tombstone, but if the write didn't complete, we
-   * need to resurrect the data from the tombstone.
+   * Deal with tombstones.  These are blocks left behind when
+   * something bad (like a power failure) happened while we updating.
+   * The sequence of operations while updating is designed so that,
+   * barring a bug or a hardware failure, we should never lose data.
+   *
+   * For any tombstone we find, we start by looking for all the blocks
+   * with a matching UUID, then see what valid sequences we can
+   * construct from what we found.
+   *
+   * If we can construct a valid sequence of live blocks, the complete
+   * update was written out, and we just need to zero the tombstones.
+   *
+   * Otherwise, if we can construct a complete sequence of tombstone
+   * blocks, the update failed before it was completely written, so we
+   * have to zero the incomplete sequence of live blocks then restore
+   * from the tombstones.
+   *
+   * Otherwise, if the live and tombstone blocks taken together form a
+   * valid sequence, the update failed while deprecating the old live
+   * blocks, and the update itself was not written, so we need to
+   * restore the tombstones and leave the live blocks alone.
+   *
+   * If none of the above applies, we don't understand what happened,
+   * which is a symptom of either a bug or a hardware failure more
+   * serious than simple loss of power or reboot at an inconvenient
+   * time, so we error out to avoid accidental loss of data.
    */
 
   for (int i = 0; i < NUM_FLASH_BLOCKS; i++) {
@@ -659,56 +666,138 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
     if (block_status[i] != BLOCK_STATUS_TOMBSTONE)
       continue;
 
-    err = hal_ks_index_find(&db.ksi, &db.ksi.names[i], NULL);
+    hal_uuid_t name = db.ksi.names[i].name;
+    unsigned n_blocks;
+    int where = -1;
 
-    if (err != HAL_OK && err != HAL_ERROR_KEY_NOT_FOUND)
+    if ((err = hal_ks_index_find_range(&db.ksi, &name, 0, &n_blocks, NULL, &where)) != HAL_OK)
       return err;
 
-    unsigned b = ~0;
+    while (where > 0 && !hal_uuid_cmp(&name, &db.ksi.names[db.ksi.index[where - 1]].name)) {
+      where--;
+      n_blocks++;
+    }
 
-    if (err == HAL_ERROR_KEY_NOT_FOUND) {
+    int live_ok = 1, tomb_ok = 1, join_ok = 1;
+    unsigned n_live = 0, n_tomb = 0;
+    unsigned i_live = 0, i_tomb = 0;
+
+    for (int j = 0; j < n_blocks; j++) {
+      unsigned b = db.ksi.index[where + j];
+      switch (block_status[b]) {
+      case BLOCK_STATUS_LIVE:           n_live++;       break;
+      case BLOCK_STATUS_TOMBSTONE:      n_tomb++;       break;
+      default:                          return HAL_ERROR_IMPOSSIBLE;
+      }
+    }
 
-      /*
-       * Block did not exist, need to resurrect it.
-       */
+    uint16_t live_blocks[n_live], tomb_blocks[n_tomb];
 
-      hal_uuid_t name = db.ksi.names[i]; /* Paranoia */
+    for (int j = 0; j < n_blocks; j++) {
+      unsigned b = db.ksi.index[where + j];
 
-      if ((err = block_read(i, block)) != HAL_OK)
+      if ((err = block_read(b, block)) != HAL_OK)
         return err;
 
-      block->header.block_status = BLOCK_STATUS_LIVE;
+      join_ok &= block->header.this_chunk == j && block->header.total_chunks == n_blocks;
+
+      switch (block_status[b]) {
+      case BLOCK_STATUS_LIVE:
+        live_blocks[i_live] = b;
+        live_ok &= block->header.this_chunk == i_live++ && block->header.total_chunks == n_live;
+        break;
+      case BLOCK_STATUS_TOMBSTONE:
+        tomb_blocks[i_tomb] = b;
+        tomb_ok &= block->header.this_chunk == i_tomb++ && block->header.total_chunks == n_tomb;
+        break;
+      default:
+        return HAL_ERROR_IMPOSSIBLE;
+      }
+    }
 
-      if ((err = hal_ks_index_add(&db.ksi, &name, &b)) != HAL_OK ||
-          (err = block_write(b, block))                != HAL_OK)
-        return err;
+    if (!live_ok && !tomb_ok && !join_ok)
+      return HAL_ERROR_KEYSTORE_LOST_DATA;
+
+    if (live_ok) {
+      for (int j = 0; j < n_tomb; j++) {
+        const unsigned b = tomb_blocks[j];
+        if ((err = block_zero(b)) != HAL_OK)
+          return err;
+        block_types[b]  = BLOCK_TYPE_ZEROED;
+        block_status[b] = BLOCK_STATUS_UNKNOWN;
+      }
+    }
 
-      if (block_types[i] == BLOCK_TYPE_PINBLK)
-        saw_pins = 1;
+    else if (tomb_ok) {
+      for (int j = 0; j < n_live; j++) {
+        const unsigned b = live_blocks[j];
+        if ((err = block_zero(b)) != HAL_OK)
+          return err;
+        block_types[b]  = BLOCK_TYPE_ZEROED;
+        block_status[b] = BLOCK_STATUS_UNKNOWN;
+      }
     }
 
-    /*
-     * Done with the tombstone, zero it.
-     */
+    if (live_ok) {
+      memcpy(&db.ksi.index[where], live_blocks, n_live * sizeof(*db.ksi.index));
+      memmove(&db.ksi.index[where + n_live], &db.ksi.index[where + n_blocks],
+              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
+      memcpy(&db.ksi.index[db.ksi.size - n_tomb], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
+      db.ksi.used -= n_tomb;
+      n_blocks = n_live;
+    }
 
-    if ((unsigned) i != b && (err = block_zero(i)) != HAL_OK)
-      return err;
+    else if (tomb_ok) {
+      memcpy(&db.ksi.index[where], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
+      memmove(&db.ksi.index[where + n_tomb], &db.ksi.index[where + n_blocks],
+              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
+      memcpy(&db.ksi.index[db.ksi.size - n_live], live_blocks, n_live * sizeof(*db.ksi.index));
+      db.ksi.used -= n_live;
+      n_blocks = n_tomb;
+    }
+
+    for (int j = 0; j < n_blocks; j++) {
+      unsigned b1 = db.ksi.index[where + j];
+      if (block_status[b1] != BLOCK_STATUS_TOMBSTONE)
+        continue;
+      if ((err = block_read(b1, block)) != HAL_OK)
+        return err;
+      block->header.block_status = BLOCK_STATUS_LIVE;
+      int hint = where + j;
+      unsigned b2;
+      if ((err = hal_ks_index_replace(&db.ksi, &name, j, &b2, &hint)) != HAL_OK ||
+          (err = block_write(b2, block)) != HAL_OK)
+        return err;
+      block_status[b2] = BLOCK_STATUS_LIVE;
+      block_types[b1] = BLOCK_TYPE_ZEROED;
+    }
   }
 
-  /*
-   * If we didn't see a PIN block, create one, with the user and so
-   * PINs cleared and the wheel PIN set to the last-gasp value.  The
-   * last-gasp WHEEL PIN is a terrible answer, but we need some kind
-   * of bootstrapping mechanism when all else fails.  If you have a
-   * better suggestion, we'd love to hear it.
-   */
+  err = fetch_pin_block(NULL, &block);
+
+  if (err == HAL_OK) {
+    db.wheel_pin = block->pin.wheel_pin;
+    db.so_pin    = block->pin.so_pin;
+    db.user_pin  = block->pin.user_pin;
+  }
+
+  else if (err != HAL_ERROR_KEY_NOT_FOUND)
+    return err;
+
+  else {
+    /*
+     * We found no PIN block, so create one, with the user and so PINs
+     * cleared and the wheel PIN set to the last-gasp value.  The
+     * last-gasp WHEEL PIN is a terrible answer, but we need some kind
+     * of bootstrapping mechanism when all else fails.  If you have a
+     * better suggestion, we'd love to hear it.
+     */
 
-  if (!saw_pins) {
     unsigned b;
 
     memset(block, 0xFF, sizeof(*block));
 
-    block->header.block_type   = BLOCK_TYPE_PINBLK;
+    block->header.block_type   = BLOCK_TYPE_PIN;
     block->header.block_status = BLOCK_STATUS_LIVE;
     block->header.total_chunks = 1;
     block->header.this_chunk   = 0;
@@ -717,7 +806,7 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
     block->pin.so_pin    = db.so_pin;
     block->pin.user_pin  = db.user_pin;
 
-    if ((err = hal_ks_index_add(&db.ksi, &pin_uuid, &b)) != HAL_OK)
+    if ((err = hal_ks_index_add(&db.ksi, &pin_uuid, 0, &b, NULL)) != HAL_OK)
       return err;
 
     cache_mark_used(block, b);
@@ -802,14 +891,14 @@ static hal_error_t ks_store(hal_ks_t *ks,
   if (block == NULL)
     return HAL_ERROR_IMPOSSIBLE;
 
-  if ((err = hal_ks_index_add(&db.ksi, &slot->name, &b)) != HAL_OK)
+  if ((err = hal_ks_index_add(&db.ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
     return err;
 
   cache_mark_used(block, b);
 
   memset(block, 0xFF, sizeof(*block));
 
-  block->header.block_type   = BLOCK_TYPE_KEYBLK;
+  block->header.block_type   = BLOCK_TYPE_KEY;
   block->header.block_status = BLOCK_STATUS_LIVE;
   block->header.total_chunks = 1;
   block->header.this_chunk   = 0;
@@ -831,7 +920,7 @@ static hal_error_t ks_store(hal_ks_t *ks,
 
   memset(block, 0, sizeof(*block));
   cache_release(block);
-  (void) hal_ks_index_delete(&db.ksi, &slot->name, NULL);
+  (void) hal_ks_index_delete(&db.ksi, &slot->name, 0, NULL, NULL);
   return err;
 }
 
@@ -846,11 +935,11 @@ static hal_error_t ks_fetch(hal_ks_t *ks,
   hal_error_t err;
   unsigned b;
 
-  if ((err = hal_ks_index_find(&db.ksi, &slot->name, &b)) != HAL_OK ||
-      (err = block_read_cached(b, &block)) != HAL_OK)
+  if ((err = hal_ks_index_find(&db.ksi, &slot->name, 0, &b, NULL)) != HAL_OK ||
+      (err = block_read_cached(b, &block))                         != HAL_OK)
     return err;
 
-  if (block_get_type(block) != BLOCK_TYPE_KEYBLK)
+  if (block_get_type(block) != BLOCK_TYPE_KEY)
     return HAL_ERROR_KEY_NOT_FOUND;
 
   cache_mark_used(block, b);
@@ -896,7 +985,7 @@ static hal_error_t ks_delete(hal_ks_t *ks,
   hal_error_t err;
   unsigned b;
 
-  if ((err = hal_ks_index_delete(&db.ksi, &slot->name, &b)) != HAL_OK)
+  if ((err = hal_ks_index_delete(&db.ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
     return err;
 
   cache_release(cache_find_block(b));
@@ -931,7 +1020,7 @@ static hal_error_t ks_list(hal_ks_t *ks,
     if ((err = block_read_cached(b, &block)) != HAL_OK)
       return err;
 
-    if (block_get_type(block) != BLOCK_TYPE_KEYBLK)
+    if (block_get_type(block) != BLOCK_TYPE_KEY || block->header.this_chunk > 0)
       continue;
 
     result[*result_len].type  = block->key.type;
@@ -982,23 +1071,29 @@ hal_error_t hal_get_pin(const hal_user_t user,
 }
 
 /*
- * Fetch PIN block.
+ * Fetch PIN block.  hint = 0 because we know that the all-zeros UUID
+ * should always sort to first slot in the index.
  */
 
 static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block)
 {
-  if (b == NULL || block == NULL)
+  if (block == NULL)
     return HAL_ERROR_IMPOSSIBLE;
 
   hal_error_t err;
+  int hint = 0;
+  unsigned b_;
 
-  if ((err = hal_ks_index_find(&db.ksi, &pin_uuid, b)) != HAL_OK ||
-      (err = block_read_cached(*b, block))             != HAL_OK)
+  if (b == NULL)
+    b = &b_;
+
+  if ((err = hal_ks_index_find(&db.ksi, &pin_uuid, 0, b, &hint)) != HAL_OK ||
+      (err = block_read_cached(*b, block))                       != HAL_OK)
     return err;
 
   cache_mark_used(*block, *b);
 
-  if (block_get_type(*block) != BLOCK_TYPE_PINBLK)
+  if (block_get_type(*block) != BLOCK_TYPE_PIN)
     return HAL_ERROR_IMPOSSIBLE;
 
   return HAL_OK;
@@ -1007,22 +1102,19 @@ static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block)
 /*
  * Update the PIN block.  This block should always be present, but we
  * have to dance a bit to make sure we write the new PIN block before
- * destroying the old one.
- *
- * In theory we could simplify and speed this up a bit by taking
- * advantage of knowing that the PIN block is always db.ksi.index[0]
- * (because of the all-zeros UUID).  Maybe later.
+ * destroying the old one.  hint = 0 because we know that the all-zeros
+ * UUID should always sort to first slot in the index.
  *
- * More generally, most of what happens here is part of updating any
- * block, not just a PIN block, so we'll probably want to refactor
- * once we get to the point where we need to update key blocks too.
+ * Most of what happens here is part of updating any block, not just a
+ * PIN block, so we'll probably want to refactor once we get to the
+ * point where we need to update key blocks too.
  */
 
 static hal_error_t update_pin_block(const unsigned b1,
                                     flash_block_t *block,
                                     const flash_pin_block_t * const new_data)
 {
-  if (block == NULL || new_data == NULL || block_get_type(block) != BLOCK_TYPE_PINBLK)
+  if (block == NULL || new_data == NULL || block_get_type(block) != BLOCK_TYPE_PIN)
     return HAL_ERROR_IMPOSSIBLE;
 
   if (db.ksi.used == db.ksi.size)
@@ -1052,9 +1144,10 @@ static hal_error_t update_pin_block(const unsigned b1,
   if ((err = block_write(b2, block)) != HAL_OK)
     return err;
 
+  int hint = 0;
   unsigned b3;
 
-  if ((err = hal_ks_index_replace(&db.ksi, &pin_uuid, &b3)) != HAL_OK)
+  if ((err = hal_ks_index_replace(&db.ksi, &pin_uuid, 0, &b3, &hint)) != HAL_OK)
     return err;
 
   if (b2 != b3)
diff --git a/ks_index.c b/ks_index.c
index 5aae516..c25f791 100644
--- a/ks_index.c
+++ b/ks_index.c
@@ -39,18 +39,44 @@
 #include "hal_internal.h"
 
 /*
+ * Compare two hal_ks_name_t objects.
+ */
+
+static inline int ks_name_cmp(const hal_ks_name_t * const name1, const hal_ks_name_t * const name2)
+{
+  assert(name1 != NULL && name2 != NULL);
+
+  int cmp = hal_uuid_cmp(&name1->name, &name2->name);
+
+  if (cmp == 0)
+    cmp = ((int) name2->chunk) - ((int) name1->chunk);
+
+  return cmp;
+}
+
+/*
  * 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
+ * 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,
+		   const hal_uuid_t * const uuid,
+                   const uint8_t chunk,
+                   const int * const hint,
 		   int *where)
 {
-  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL && name != NULL && where != NULL);
+  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL && uuid != NULL && where != NULL);
+
+  const hal_ks_name_t name = { *uuid, chunk };
+
+  if (hint != NULL && *hint >= 0 && *hint < ksi->used &&
+      ks_name_cmp(&name, &ksi->names[ksi->index[*hint]]) == 0) {
+    *where = *hint;
+    return 1;
+  }
 
   int lo = -1;
   int hi = ksi->used;
@@ -61,7 +87,7 @@ static int ks_find(const hal_ks_index_t * const ksi,
       *where = hi;
       return 0;
     }
-    const int cmp = hal_uuid_cmp(name, &ksi->names[ksi->index[m]]);
+    const int cmp = ks_name_cmp(&name, &ksi->names[ksi->index[m]]);
     if (cmp < 0)
       hi = m;
     else if (cmp > 0)
@@ -89,11 +115,11 @@ static inline void ks_heapsift(hal_ks_index_t *ksi, int parent, const int end)
     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)
+    if (left_child  <= end && ks_name_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)
+    if (right_child <= end && ks_name_cmp(&ksi->names[ksi->index[biggest]],
+                                          &ksi->names[ksi->index[right_child]]) < 0)
       biggest = right_child;
     if (biggest == parent)
       return;
@@ -135,7 +161,9 @@ hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
 
 hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
 			      const hal_uuid_t * const name,
-			      unsigned *blockno)
+                              const unsigned chunk,
+			      unsigned *blockno,
+                              int *hint)
 {
   if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
       ksi->size == 0 || ksi->used > ksi->size || name == NULL)
@@ -143,18 +171,59 @@ hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
 
   int where;
 
-  if (!ks_find(ksi, name, &where))
+  if (!ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   if (blockno != NULL)
     *blockno = ksi->index[where];
 
+  if (hint != NULL)
+    *hint = where;
+
+  return HAL_OK;
+}
+
+hal_error_t hal_ks_index_find_range(hal_ks_index_t *ksi,
+                                    const hal_uuid_t * const name,
+                                    const unsigned max_blocks,
+                                    unsigned *n_blocks,
+                                    unsigned *blocknos,
+                                    int *hint)
+{
+  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, 0, hint, &where))
+    return HAL_ERROR_KEY_NOT_FOUND;
+
+  int n = 0;
+
+  for (int i = where; i < ksi->used && !hal_uuid_cmp(name, &ksi->names[ksi->index[i]].name); i++) {
+    if (blocknos != NULL && n < max_blocks)
+      blocknos[n] = ksi->index[i];
+    n++;
+  }
+
+  if (n_blocks != NULL)
+    *n_blocks = n;
+
+  if (hint != NULL)
+    *hint = where;
+
+  if (blocknos != NULL && n > max_blocks)
+    return HAL_ERROR_RESULT_TOO_LONG;
+
   return HAL_OK;
 }
 
 hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
 			     const hal_uuid_t * const name,
-			     unsigned *blockno)
+                             const unsigned chunk,
+			     unsigned *blockno,
+                             int *hint)
 {
   if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
       ksi->size == 0 || ksi->used > ksi->size || name == NULL)
@@ -165,7 +234,7 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
 
   int where;
 
-  if (ks_find(ksi, name, &where))
+  if (ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NAME_IN_USE;
 
   /*
@@ -177,17 +246,31 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
   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;
+  ksi->names[b].name = *name;
+  ksi->names[b].chunk = chunk;
 
   if (blockno != NULL)
     *blockno = b;
 
+  if (hint != NULL)
+    *hint = where;
+
   return HAL_OK;
 }
 
+/*
+ * Should this be deleting the whole object instead of just one chunk?
+ * Deferred for the moment as this is just an optimization.  blockno
+ * would need to become an array, adding complexity.
+ *
+ * See how we end up using it, I guess.
+ */
+
 hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
 				const hal_uuid_t * const name,
-				unsigned *blockno)
+                                const unsigned chunk,
+				unsigned *blockno,
+                                int *hint)
 {
   if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
       ksi->size == 0 || ksi->used > ksi->size || name == NULL)
@@ -195,7 +278,7 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
 
   int where;
 
-  if (ksi->used == 0 || !ks_find(ksi, name, &where))
+  if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   /*
@@ -212,12 +295,17 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
   if (blockno != NULL)
     *blockno = b;
 
+  if (hint != NULL)
+    *hint = where;
+
   return HAL_OK;
 }
 
 hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
                                  const hal_uuid_t * const name,
-                                 unsigned *blockno)
+                                 const unsigned chunk,
+                                 unsigned *blockno,
+                                 int *hint)
 {
   if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
       ksi->size == 0 || ksi->used > ksi->size || name == NULL)
@@ -228,7 +316,7 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
 
   int where;
 
-  if (ksi->used == 0 || !ks_find(ksi, name, &where))
+  if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   /*
@@ -245,6 +333,9 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
   if (blockno != NULL)
     *blockno = b;
 
+  if (hint != NULL)
+    *hint = where;
+
   return HAL_OK;
 }
 
diff --git a/ks_volatile.c b/ks_volatile.c
index 72ee1cb..29793a4 100644
--- a/ks_volatile.c
+++ b/ks_volatile.c
@@ -71,7 +71,7 @@ typedef struct {
 typedef struct {
   hal_ks_index_t        ksi;
   uint16_t              _index[HAL_STATIC_KS_VOLATILE_SLOTS];
-  hal_uuid_t            _names[HAL_STATIC_KS_VOLATILE_SLOTS];
+  hal_ks_name_t         _names[HAL_STATIC_KS_VOLATILE_SLOTS];
   ks_key_t              keys[HAL_STATIC_KS_VOLATILE_SLOTS];
 } db_t;
 
@@ -176,7 +176,7 @@ static hal_error_t ks_store(hal_ks_t *ks,
   if (ksv->db == NULL)
     return HAL_ERROR_KEYSTORE_ACCESS;
 
-  if ((err = hal_ks_index_add(&ksv->db->ksi, &slot->name, &b)) != HAL_OK)
+  if ((err = hal_ks_index_add(&ksv->db->ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
     return err;
 
   uint8_t kek[KEK_LENGTH];
@@ -197,7 +197,7 @@ static hal_error_t ks_store(hal_ks_t *ks,
   if (err == HAL_OK)
     ksv->db->keys[b] = k;
   else
-    (void) hal_ks_index_delete(&ksv->db->ksi, &slot->name, NULL);
+    (void) hal_ks_index_delete(&ksv->db->ksi, &slot->name, 0, NULL, NULL);
 
   return err;
 }
@@ -216,7 +216,7 @@ static hal_error_t ks_fetch(hal_ks_t *ks,
   if (ksv->db == NULL)
     return HAL_ERROR_KEYSTORE_ACCESS;
 
-  if ((err = hal_ks_index_find(&ksv->db->ksi, &slot->name, &b)) != HAL_OK)
+  if ((err = hal_ks_index_find(&ksv->db->ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
     return err;
 
   const ks_key_t * const k = &ksv->db->keys[b];
@@ -264,7 +264,7 @@ static hal_error_t ks_delete(hal_ks_t *ks,
   if (ksv->db == NULL)
     return HAL_ERROR_KEYSTORE_ACCESS;
 
-  if ((err = hal_ks_index_delete(&ksv->db->ksi, &slot->name, &b)) != HAL_OK)
+  if ((err = hal_ks_index_delete(&ksv->db->ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
     return err;
 
   memset(&ksv->db->keys[b], 0, sizeof(ksv->db->keys[b]));
@@ -289,8 +289,10 @@ static hal_error_t ks_list(hal_ks_t *ks,
     return HAL_ERROR_RESULT_TOO_LONG;
 
   for (int i = 0; i < ksv->db->ksi.used; i++) {
-    unsigned b      = ksv->db->ksi.index[i];
-    result[i].name  = ksv->db->ksi.names[b];
+    unsigned b = ksv->db->ksi.index[i];
+    if (ksv->db->ksi.names[b].chunk > 0)
+      continue;
+    result[i].name  = ksv->db->ksi.names[b].name;
     result[i].type  = ksv->db->keys[b].type;
     result[i].curve = ksv->db->keys[b].curve;
     result[i].flags = ksv->db->keys[b].flags;