Keystore attribute code. Not really tested.

Passes PKCS #11 "make test" but nothing uses the new attribute code yet.

Refactored some of the flash block update code.

Attribute code is annoyingly verbose, might be possible to refactor
some of that.

6 files changed, 543 insertions, 131 deletions

diff --git a/hal.h b/hal.h
index 6bb2f67..21104c3 100644
--- a/hal.h
+++ b/hal.h
@@ -149,6 +149,7 @@
   DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_LOST_DATA,        "Keystore appears to have lost data")           \
   DEFINE_HAL_ERROR(HAL_ERROR_BAD_ATTRIBUTE_LENGTH,      "Bad attribute length")                         \
   DEFINE_HAL_ERROR(HAL_ERROR_ATTRIBUTE_NOT_FOUND,       "Attribute not found")                          \
+  DEFINE_HAL_ERROR(HAL_ERROR_NO_KEY_INDEX_SLOTS,        "No key index slots available")                 \
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
diff --git a/hal_internal.h b/hal_internal.h
index 61d8489..3e6cf29 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -769,6 +769,17 @@ extern hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
                                        int *hint);
 
 /*
+ * Delete all of blocks in a key, returning the block numbers.
+ */
+
+extern hal_error_t hal_ks_index_delete_range(hal_ks_index_t *ksi,
+                                             const hal_uuid_t * const name,
+                                             const unsigned max_blocks,
+                                             unsigned *n_blocks,
+                                             unsigned *blocknos,
+                                             int *hint);
+
+/*
  * Replace a key block with a new one, return new block number.
  * Name of block does not change.  This is an optimization of
  * a delete immediately followed by an add for the same name.
diff --git a/ks_attribute.c b/ks_attribute.c
index 248f98d..0c71345 100644
--- a/ks_attribute.c
+++ b/ks_attribute.c
@@ -111,18 +111,6 @@ hal_error_t hal_ks_attribute_scan(const uint8_t * const bytes, const size_t byte
   return HAL_OK;
 }
 
-/*
- * Given scan(), delete() and insert() should be relatively simple.
- *
- * delete() does a scan to find the attribute it wants to delete, and,
- * if found, uses memmove() to copy the rest down.
- *
- * insert() does a delete to get rid of old value, if any, then does
- * another scan, checks length what we want to insert against
- * total_len returned by the scan, and either appends the new
- * attribute or returns error code saying it couldn't.
- */
-
 hal_error_t hal_ks_attribute_delete(uint8_t *bytes, const size_t bytes_len,
                                     hal_rpc_pkey_attribute_t *attributes, unsigned *attributes_len,
                                     size_t *total_len,
diff --git a/ks_flash.c b/ks_flash.c
index 300c7c4..9278aed 100644
--- a/ks_flash.c
+++ b/ks_flash.c
@@ -396,19 +396,23 @@ static hal_error_t block_read_cached(const unsigned blockno, flash_block_t **blo
  * need to update the CRC for this, we just modify the first page.
  */
 
-static hal_error_t block_deprecate(const unsigned blockno, const flash_block_t * const block)
+static hal_error_t block_deprecate(const unsigned blockno)
 {
-  if (block == NULL || blockno >= NUM_FLASH_BLOCKS)
+  if (blockno >= NUM_FLASH_BLOCKS)
     return HAL_ERROR_IMPOSSIBLE;
 
   uint8_t page[KEYSTORE_PAGE_SIZE];
   flash_block_header_t *header = (void *) page;
+  uint32_t offset = block_offset(blockno);
+
+  /* Sigh, magic numeric return codes */
+  if (keystore_read_data(offset, page, sizeof(page)) != 1)
+    return HAL_ERROR_KEYSTORE_ACCESS;
 
-  memcpy(page, block->bytes, sizeof(page));
   header->block_status = BLOCK_STATUS_TOMBSTONE;
 
   /* Sigh, magic numeric return codes */
-  if (keystore_write_data(block_offset(blockno), page, sizeof(page)) != 1)
+  if (keystore_write_data(offset, page, sizeof(page)) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
 
   return HAL_OK;
@@ -508,6 +512,35 @@ static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
 }
 
 /*
+ * Update one flash block, including zombie jamboree.
+ */
+
+static hal_error_t block_update(const unsigned b1, flash_block_t *block,
+                                const hal_uuid_t * const uuid, const unsigned chunk, int *hint)
+{
+  if (block == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  if (db.ksi.used == db.ksi.size)
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+  cache_release(block);
+
+  hal_error_t err;
+  unsigned b2;
+
+  if ((err = block_deprecate(b1))                                       != HAL_OK ||
+      (err = hal_ks_index_replace(&db.ksi, uuid, chunk, &b2, hint))     != HAL_OK ||
+      (err = block_write(b2, block))                                    != HAL_OK ||
+      (err = block_zero(b1))                                            != HAL_OK)
+    return err;
+
+  cache_mark_used(block, b2);
+
+  return block_erase_maybe(db.ksi.index[db.ksi.used]);
+}
+
+/*
  * Forward reference.
  */
 
@@ -520,15 +553,25 @@ static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block);
  * 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;
+}
+
 static hal_error_t ks_init(const hal_ks_driver_t * const driver)
 {
   /*
    * Initialize the in-memory database.
    */
 
-  const size_t len = (sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS +
-                      sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS +
-                      sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);
+  size_t len = (sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS +
+                sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS +
+                sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);
 
   uint8_t *mem = hal_allocate_static_memory(len);
 
@@ -538,10 +581,14 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
   memset(&db, 0, sizeof(db));
   memset(mem, 0, len);
 
+  db.ksi.index = gnaw(&mem, &len, sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS);
+  db.ksi.names = gnaw(&mem, &len, sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS);
+  db.cache     = gnaw(&mem, &len, sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);
   db.ksi.size  = NUM_FLASH_BLOCKS;
-  db.ksi.index = (void *) mem; mem += sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS;
-  db.ksi.names = (void *) mem; mem += sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS;
-  db.cache     = (void *) mem;
+  db.ksi.used  = 0;
+
+  if (db.ksi.index == NULL || db.ksi.names == NULL || db.cache == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
 
   for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++)
     db.cache[i].blockno = ~0;
@@ -788,19 +835,19 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
     }
 
     for (int j = 0; j < n_blocks; j++) {
-      unsigned b1 = db.ksi.index[where + j];
+      int hint = where + j;
+      unsigned b1 = db.ksi.index[hint], b2;
       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_types[b1]  = BLOCK_TYPE_ZEROED;
+      block_status[b1] = BLOCK_STATUS_UNKNOWN;
       block_status[b2] = BLOCK_STATUS_LIVE;
-      block_types[b1] = BLOCK_TYPE_ZEROED;
     }
   }
 
@@ -922,7 +969,7 @@ 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, 0, &b, NULL)) != HAL_OK)
+  if ((err = hal_ks_index_add(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK)
     return err;
 
   cache_mark_used(block, b);
@@ -951,7 +998,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, 0, NULL, NULL);
+  (void) hal_ks_index_delete(&db.ksi, &slot->name, 0, NULL, &slot->hint);
   return err;
 }
 
@@ -966,8 +1013,8 @@ 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, 0, &b, NULL)) != HAL_OK ||
-      (err = block_read_cached(b, &block))                         != HAL_OK)
+  if ((err = hal_ks_index_find(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK ||
+      (err = block_read_cached(b, &block))                                != HAL_OK)
     return err;
 
   if (block_get_type(block) != BLOCK_TYPE_KEY)
@@ -1014,18 +1061,23 @@ static hal_error_t ks_delete(hal_ks_t *ks,
     return HAL_ERROR_BAD_ARGUMENTS;
 
   hal_error_t err;
-  unsigned b;
+  unsigned n;
 
-  if ((err = hal_ks_index_delete(&db.ksi, &slot->name, 0, &b, NULL)) != HAL_OK)
+  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, 0, &n, NULL, &slot->hint)) != HAL_OK)
     return err;
 
-  cache_release(cache_find_block(b));
+  unsigned b[n];
 
-  if ((err = block_zero(b)) != HAL_OK ||
-      (err = block_erase_maybe(db.ksi.index[db.ksi.used])) != HAL_OK)
+  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, n, NULL, b, &slot->hint)) != HAL_OK)
     return err;
 
-  return HAL_OK;
+  for (int i = 0; i < n; i++) {
+    cache_release(cache_find_block(b[i]));
+    if ((err = block_zero(b[i])) != HAL_OK)
+      return err;
+  }
+
+  return block_erase_maybe(db.ksi.index[db.ksi.used]);
 }
 
 static hal_error_t ks_list(hal_ks_t *ks,
@@ -1066,6 +1118,32 @@ static hal_error_t ks_list(hal_ks_t *ks,
   return HAL_OK;
 }
 
+static inline hal_error_t locate_attributes(flash_block_t *block, const unsigned chunk,
+                                            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 (chunk == 0) {
+    if (block_get_type(block) != BLOCK_TYPE_KEY)
+      return HAL_ERROR_KEY_NOT_FOUND;
+    *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;
+  }
+
+  else {
+    if (block_get_type(block) != BLOCK_TYPE_ATTR)
+      return HAL_ERROR_KEY_NOT_FOUND;
+    *attrs_len = block->attr.attributes_len;
+    *bytes = block->attr.attributes;
+    *bytes_len = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
+  }
+
+  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,
@@ -1079,8 +1157,88 @@ static hal_error_t ks_match(hal_ks_t *ks,
                             const unsigned result_max,
                             hal_uuid_t *previous_uuid)
 {
-#warning NIY
-  return HAL_ERROR_IMPOSSIBLE;
+  if (ks == NULL || attributes == NULL ||
+      result == NULL || result_len == NULL || previous_uuid == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  uint8_t need_attr[attributes_len > 0 ? attributes_len : 1];
+  flash_block_t *block;
+  int possible = 0;
+  hal_error_t err;
+  int i = -1;
+
+  *result_len = 0;
+
+  if ((err = hal_ks_index_find(&db.ksi, previous_uuid, 0, NULL, &i)) != HAL_OK)
+    return err;
+
+  while (*result_len < result_max) {
+
+    if (++i >= db.ksi.used)
+      return HAL_OK;
+
+    unsigned b = db.ksi.index[i];
+
+    if (db.ksi.names[b].chunk == 0)
+      possible = 1;
+
+    if (!possible)
+      continue;
+
+    if ((err = block_read_cached(b, &block)) != HAL_OK)
+      return err;
+
+    if (db.ksi.names[b].chunk == 0) {
+      memset(need_attr, 1, sizeof(need_attr));
+      possible = ((type == HAL_KEY_TYPE_NONE || type  == block->key.type) &&
+                  (curve == HAL_CURVE_NONE   || curve == block->key.curve));
+    }
+
+    if (!possible)
+      continue;
+
+    if (attributes_len > 0) {
+      uint8_t *bytes = NULL;
+      size_t bytes_len = 0;
+      unsigned attrs_len;
+
+      if ((err = locate_attributes(block, db.ksi.names[b].chunk,
+                                   &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+        return err;
+
+      hal_rpc_pkey_attribute_t attrs[attrs_len];
+
+      if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, attrs_len, NULL)) != HAL_OK)
+        return err;
+
+      for (int j = 0; possible && j < attributes_len; j++) {
+
+        if (!need_attr[j])
+          continue;
+
+        for (hal_rpc_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)
+      continue;
+
+    if (attributes_len > 0 && memchr(need_attr, 1, sizeof(need_attr)) != NULL)
+      continue;
+
+    *previous_uuid = result[*result_len] = db.ksi.names[b].name;
+    ++*result_len;
+    possible = 0;
+  }
+
+  return HAL_ERROR_RESULT_TOO_LONG;
 }
 
 static  hal_error_t ks_set_attribute(hal_ks_t *ks,
@@ -1089,8 +1247,148 @@ static  hal_error_t ks_set_attribute(hal_ks_t *ks,
                                      const uint8_t * const value,
                                      const size_t value_len)
 {
-#warning NIY
-  return HAL_ERROR_IMPOSSIBLE;
+  if (ks != &db.ks || slot == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  /*
+   * Try to add new attribute as a single-block update.
+   */
+
+  flash_block_t *block;
+  unsigned chunk = 0;
+  hal_error_t err;
+
+  do {
+    int hint = slot->hint + chunk;
+    unsigned b;
+
+    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
+        (err = block_read_cached(b, &block))                              != HAL_OK)
+      return err;
+
+    if (block->header.this_chunk != chunk)
+      return HAL_ERROR_IMPOSSIBLE;
+
+    if (chunk == 0)
+      slot->hint = hint;
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned attrs_len;
+
+    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+      return err;
+
+    cache_mark_used(block, b);
+
+    if (attrs_len == 0)
+      continue;
+
+    hal_rpc_pkey_attribute_t attrs[attrs_len + 1];
+    const unsigned old_attrs_len = attrs_len;
+    size_t total;
+
+    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, attrs_len, &total)) != HAL_OK)
+      return err;
+
+    err = hal_ks_attribute_insert(bytes, bytes_len, attrs, &attrs_len, &total, type, value, value_len);
+
+    if (attrs_len != old_attrs_len && err != HAL_OK)
+      cache_release(block);
+
+    if (err == HAL_ERROR_RESULT_TOO_LONG)
+      continue;
+
+    if (err != HAL_OK)
+      return err;
+
+    return block_update(b, block, &slot->name, chunk, &hint);
+
+  } while (++chunk < block->header.total_chunks);
+
+  /*
+   * If we get here, we have to add a new block, which requires
+   * rewriting all the others to bump the total_blocks count.  We need
+   * to keep track of all the old chunks so we can zero them at the
+   * end, and because we can't zero them until we've written out the
+   * new chunks, we need enough free blocks for the entire new object.
+   */
+
+  const unsigned total_chunks = block->header.total_chunks;
+  unsigned b, blocks[total_chunks];
+
+  if (db.ksi.used + total_chunks + 1 > db.ksi.size)
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+  for (chunk = 0; chunk < total_chunks; chunk++) {
+    int hint = slot->hint + chunk;
+    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &blocks[chunk], &hint)) != HAL_OK ||
+        (err = block_deprecate(blocks[chunk]))                                        != HAL_OK)
+      return err;
+  }
+
+  {
+    block = cache_pick_lru();
+
+    memset(block, 0xFF, sizeof(*block));
+
+    block->header.block_type   = BLOCK_TYPE_ATTR;
+    block->header.block_status = BLOCK_STATUS_LIVE;
+    block->header.total_chunks = total_chunks + 1;
+    block->header.this_chunk   = total_chunks;
+    block->attr.name = slot->name;
+    block->attr.attributes_len = 0;
+
+    hal_rpc_pkey_attribute_t attrs[1];
+    size_t total = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
+
+    if ((err = hal_ks_attribute_insert(block->attr.attributes,
+                                       SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES,
+                                       attrs, &block->attr.attributes_len, &total,
+                                       type, value, value_len))                         != HAL_OK ||
+        (err = hal_ks_index_add(&db.ksi, &slot->name, total_chunks, &b, NULL))          != HAL_OK ||
+        (err = block_write(b, block))                                                   != HAL_OK)
+      return err;
+
+    cache_mark_used(block, b);
+  }
+
+  for (chunk = 0; chunk < total_chunks; chunk++) {
+    int hint = slot->hint + chunk;
+    if ((err = block_read_cached(blocks[chunk], &block)) != HAL_OK)
+      return err;
+    if (block->header.this_chunk != chunk)
+      return HAL_ERROR_IMPOSSIBLE;
+    block->header.block_status = BLOCK_STATUS_LIVE;
+    block->header.total_chunks = total_chunks + 1;
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned attrs_len;
+    size_t total;
+
+    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+      return err;
+
+    if (attrs_len > 0) {
+      hal_rpc_pkey_attribute_t attrs[attrs_len];
+      if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, attrs_len, &total)) != HAL_OK ||
+          (err = hal_ks_attribute_delete(bytes, bytes_len, attrs, &attrs_len, &total, type)) != HAL_OK)
+        return err;
+    }
+
+    unsigned b;
+
+    if ((err = hal_ks_index_replace(&db.ksi, &slot->name, chunk, &b, &hint))    != HAL_OK ||
+        (err = block_write(b, block))                                           != HAL_OK)
+      return err;
+  }
+
+  for (chunk = 0; chunk < total_chunks; chunk++)
+    if ((err = block_zero(blocks[chunk])) != HAL_OK)
+      return err;
+
+  return HAL_OK;
 }
 
 static  hal_error_t ks_get_attribute(hal_ks_t *ks,
@@ -1100,16 +1398,125 @@ static  hal_error_t ks_get_attribute(hal_ks_t *ks,
                                      size_t *value_len,
                                      const size_t value_max)
 {
-#warning NIY
-  return HAL_ERROR_IMPOSSIBLE;
+  if (ks != &db.ks || slot == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  flash_block_t *block;
+  hal_error_t err;
+  unsigned b;
+
+  hal_rpc_pkey_attribute_t a = {0, 0, NULL};
+  unsigned chunk = 0;
+
+  do {
+    int hint = slot->hint + chunk;
+
+    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
+        (err = block_read_cached(b, &block))                              != HAL_OK)
+      return err;
+
+    if (block->header.this_chunk != chunk)
+      return HAL_ERROR_IMPOSSIBLE;
+
+    if (chunk == 0)
+      slot->hint = hint;
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned attributes_len;
+
+    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attributes_len)) != HAL_OK)
+      return err;
+
+    cache_mark_used(block, b);
+
+    hal_rpc_pkey_attribute_t attributes[attributes_len];
+
+    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attributes, attributes_len, NULL)) != HAL_OK)
+      return err;
+
+    for (int i = 0; a.value == NULL && i < attributes_len; ++i)
+      if (attributes[i].type == type)
+        a = attributes[i];
+
+  } while (a.value == NULL && ++chunk < block->header.total_chunks);
+
+  if (a.value == NULL)
+    return HAL_ERROR_ATTRIBUTE_NOT_FOUND;
+
+  if (a.length > value_max && value != NULL)
+    return HAL_ERROR_RESULT_TOO_LONG;
+
+  if (value != NULL)
+    memcpy(value, a.value, a.length);
+
+  if (value_len != NULL)
+    *value_len = a.length;
+
+  return HAL_OK;
 }
 
 static hal_error_t ks_delete_attribute(hal_ks_t *ks,
                                        hal_pkey_slot_t *slot,
                                        const uint32_t type)
 {
-#warning NIY
-  return HAL_ERROR_IMPOSSIBLE;
+  /*
+   * For extra credit, we could handle attribute compaction here, but
+   * in practice we expect attribute deletion without deleting the
+   * entire object to be a rare enough event that it may not be worth
+   * it.  Certainly it's not a high priority, so later, if ever.
+   */
+
+  if (ks != &db.ks || slot == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  flash_block_t *block;
+  unsigned chunk = 0;
+
+  do {
+    int hint = slot->hint + chunk;
+    hal_error_t err;
+    unsigned b;
+
+    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
+        (err = block_read_cached(b, &block))                              != HAL_OK)
+      return err;
+
+    if (block->header.this_chunk != chunk)
+      return HAL_ERROR_IMPOSSIBLE;
+
+    if (chunk == 0)
+      slot->hint = hint;
+
+    uint8_t *bytes = NULL;
+    size_t bytes_len = 0;
+    unsigned attrs_len;
+
+    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
+      return err;
+
+    cache_mark_used(block, b);
+
+    if (attrs_len == 0)
+      continue;
+
+    hal_rpc_pkey_attribute_t attrs[attrs_len];
+    const unsigned old_attrs_len = attrs_len;
+    size_t total;
+
+    if ((err = hal_ks_attribute_scan(  bytes, bytes_len, attrs,  attrs_len, &total))       != HAL_OK ||
+        (err = hal_ks_attribute_delete(bytes, bytes_len, attrs, &attrs_len, &total, type)) != HAL_OK)
+      return err;
+
+    if (attrs_len == old_attrs_len)
+      continue;
+
+    if ((err = block_update(b, block, &slot->name, chunk, &hint)) != HAL_OK)
+      return err;
+
+  } while (++chunk < block->header.total_chunks);
+
+  return HAL_OK;
 }
 
 const hal_ks_driver_t hal_ks_token_driver[1] = {{
@@ -1184,65 +1591,23 @@ 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.  hint = 0 because we know that the all-zeros
- * UUID should always sort to first slot in the index.
- *
- * 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.
+ * have to do the zombie jamboree to make sure we write the new PIN
+ * block before destroying the old one.  hint = 0 because we know that
+ * the all-zeros UUID should always sort to first slot in the index.
  */
 
-static hal_error_t update_pin_block(const unsigned b1,
+static hal_error_t update_pin_block(const unsigned b,
                                     flash_block_t *block,
                                     const flash_pin_block_t * const new_data)
 {
   if (block == NULL || new_data == NULL || block_get_type(block) != BLOCK_TYPE_PIN)
     return HAL_ERROR_IMPOSSIBLE;
 
-  if (db.ksi.used == db.ksi.size)
-    return HAL_ERROR_NO_KEY_SLOTS_AVAILABLE;
-
-  hal_error_t err = block_deprecate(b1, block);
-
-  cache_release(block);
-
-  if (err != HAL_OK)
-    return err;
-
-  /*
-   * At this point we're committed to an update, because the old flash
-   * block is now a tombstone and can't be reverted in place without
-   * risking data loss.  So the rest of this dance is to make sure
-   * that we don't destroy the tombstone unless we succeeed in writing
-   * the new block, so that we can attempt recovery on reboot.
-   */
-
-  unsigned b2 = db.ksi.index[db.ksi.used];
-
-  cache_mark_used(block, b2);
-
-  block->pin = *new_data;
-
-  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, 0, &b3, &hint)) != HAL_OK)
-    return err;
-
-  if (b2 != b3)
-    return HAL_ERROR_IMPOSSIBLE;
-
-  if ((err = block_zero(b1)) != HAL_OK)
-    return err;
-
-  if (db.ksi.used < db.ksi.size)
-    err = block_erase_maybe(db.ksi.index[db.ksi.used]);
+  block->pin = *new_data;
 
-  return err;
+  return block_update(b, block, &pin_uuid, 0, &hint);
 }
 
 /*
diff --git a/ks_index.c b/ks_index.c
index c25f791..edfc7fa 100644
--- a/ks_index.c
+++ b/ks_index.c
@@ -202,6 +202,8 @@ hal_error_t hal_ks_index_find_range(hal_ks_index_t *ksi,
   int n = 0;
 
   for (int i = where; i < ksi->used && !hal_uuid_cmp(name, &ksi->names[ksi->index[i]].name); i++) {
+    if (n != ksi->names[ksi->index[i]].chunk)
+      return HAL_ERROR_IMPOSSIBLE;
     if (blocknos != NULL && n < max_blocks)
       blocknos[n] = ksi->index[i];
     n++;
@@ -230,7 +232,7 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
     return HAL_ERROR_BAD_ARGUMENTS;
 
   if (ksi->used == ksi->size)
-    return HAL_ERROR_NO_KEY_SLOTS_AVAILABLE;
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
 
   int where;
 
@@ -258,14 +260,6 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
   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,
                                 const unsigned chunk,
@@ -301,6 +295,58 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
   return HAL_OK;
 }
 
+hal_error_t hal_ks_index_delete_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 (ksi->used == 0 || !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 (n != ksi->names[ksi->index[i]].chunk)
+      return HAL_ERROR_IMPOSSIBLE;
+    if (blocknos != NULL && n < max_blocks)
+      blocknos[n] = ksi->index[i];
+    n++;
+  }
+
+  if (n_blocks != NULL)
+    *n_blocks = n;
+
+  /*
+   * Free the blocks and stuff them at the end of the free list.
+   */
+
+  if (blocknos != NULL) {
+    if (n > max_blocks)
+      return HAL_ERROR_RESULT_TOO_LONG;
+    const size_t len = (ksi->size - where - n) * sizeof(*ksi->index);
+    memmove(&ksi->index[where], &ksi->index[where + n], len);
+    ksi->used -= n;
+    for (int i = 0; i < n; i++) {
+      ksi->index[ksi->size - n + i] = blocknos[i];
+      memset(&ksi->names[blocknos[i]], 0, sizeof(ksi->names[blocknos[i]]));
+    }
+    where = -1;
+  }
+
+  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,
                                  const unsigned chunk,
@@ -312,7 +358,7 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
     return HAL_ERROR_BAD_ARGUMENTS;
 
   if (ksi->used == ksi->size)
-    return HAL_ERROR_NO_KEY_SLOTS_AVAILABLE;
+    return HAL_ERROR_NO_KEY_INDEX_SLOTS;
 
   int where;
 
diff --git a/ks_volatile.c b/ks_volatile.c
index 35f1e38..df26471 100644
--- a/ks_volatile.c
+++ b/ks_volatile.c
@@ -106,6 +106,16 @@ static inline ks_t *ks_to_ksv(hal_ks_t *ks)
   return (ks_t *) ks;
 }
 
+static inline int key_visible_to_session(const ks_t * const ksv,
+                                         const hal_client_handle_t client,
+                                         const hal_session_handle_t session,
+                                         const ks_key_t * const k)
+{
+  return (!ksv->per_session || client.handle == HAL_HANDLE_NONE ||
+          (k->client.handle  == client.handle &&
+           k->session.handle == session.handle));
+}
+
 static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size)
 {
   if (mem == NULL || *mem == NULL || len == NULL || size > *len)
@@ -128,20 +138,21 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver,
   memset(ksv, 0, sizeof(*ksv));
   memset(mem, 0, len);
 
-  if ((ksv->db = gnaw(&mem, &len, sizeof(*ksv->db))) == NULL ||
-      (ksv->db->ksi.index = gnaw(&mem, &len,
-                                 sizeof(*ksv->db->ksi.index) * HAL_KS_VOLATILE_SLOTS)) == NULL ||
-      (ksv->db->ksi.names = gnaw(&mem, &len,
-                                 sizeof(*ksv->db->ksi.names) * HAL_KS_VOLATILE_SLOTS)) == NULL ||
-      (ksv->db->keys      = gnaw(&mem, &len,
-                                 sizeof(*ksv->db->keys)      * HAL_KS_VOLATILE_SLOTS)) == NULL)
-    return HAL_ERROR_IMPOSSIBLE;
-
   ksv->ks.driver     = driver;
   ksv->per_session   = per_session;
+  ksv->db            = gnaw(&mem, &len, sizeof(*ksv->db));
+  ksv->db->ksi.index = gnaw(&mem, &len, sizeof(*ksv->db->ksi.index) * HAL_KS_VOLATILE_SLOTS);
+  ksv->db->ksi.names = gnaw(&mem, &len, sizeof(*ksv->db->ksi.names) * HAL_KS_VOLATILE_SLOTS);
+  ksv->db->keys      = gnaw(&mem, &len, sizeof(*ksv->db->keys)      * HAL_KS_VOLATILE_SLOTS);
   ksv->db->ksi.size  = HAL_KS_VOLATILE_SLOTS;
   ksv->db->ksi.used  = 0;
 
+  if (ksv->db            == NULL ||
+      ksv->db->ksi.index == NULL ||
+      ksv->db->ksi.names == NULL ||
+      ksv->db->keys      == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
   /*
    * Set up keystore with empty index and full free list.
    * Since this driver doesn't care about wear leveling,
@@ -228,11 +239,8 @@ static hal_error_t ks_store(hal_ks_t *ks,
   k.type    = slot->type;
   k.curve   = slot->curve;
   k.flags   = slot->flags;
-
-  if (ksv->per_session) {
-    k.client  = slot->client_handle;
-    k.session = slot->session_handle;
-  }
+  k.client  = slot->client_handle;
+  k.session = slot->session_handle;
 
   if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
     err = hal_aes_keywrap(NULL, kek, kek_len, der, der_len, k.der, &k.der_len);
@@ -266,8 +274,7 @@ static hal_error_t ks_fetch(hal_ks_t *ks,
 
   const ks_key_t * const k = &ksv->db->keys[b];
 
-  if (ksv->per_session && (k->client.handle  != slot->client_handle.handle ||
-                           k->session.handle != slot->session_handle.handle))
+  if (!key_visible_to_session(ksv, slot->client_handle, slot->session_handle, k))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   slot->type  = k->type;
@@ -316,8 +323,7 @@ static hal_error_t ks_delete(hal_ks_t *ks,
   if ((err = hal_ks_index_find(&ksv->db->ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK)
     return err;
 
-  if (ksv->per_session && (ksv->db->keys[b].client.handle  != slot->client_handle.handle ||
-                           ksv->db->keys[b].session.handle != slot->session_handle.handle))
+  if (!key_visible_to_session(ksv, slot->client_handle, slot->session_handle, &ksv->db->keys[b]))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   if ((err = hal_ks_index_delete(&ksv->db->ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK)
@@ -350,8 +356,7 @@ static hal_error_t ks_list(hal_ks_t *ks,
     unsigned b = ksv->db->ksi.index[i];
     if (ksv->db->ksi.names[b].chunk > 0)
       continue;
-    if (ksv->per_session && (ksv->db->keys[b].client.handle  != client.handle ||
-                             ksv->db->keys[b].session.handle != session.handle))
+    if (!key_visible_to_session(ksv, client, session, &ksv->db->keys[b]))
       continue;
     result[i].name  = ksv->db->ksi.names[b].name;
     result[i].type  = ksv->db->keys[b].type;
@@ -410,8 +415,7 @@ static hal_error_t ks_match(hal_ks_t *ks,
     if (curve != HAL_CURVE_NONE && curve != ksv->db->keys[b].curve)
       continue;
 
-    if (ksv->per_session && (ksv->db->keys[b].client.handle  != client.handle ||
-                             ksv->db->keys[b].session.handle != session.handle))
+    if (!key_visible_to_session(ksv, client, session, &ksv->db->keys[b]))
       continue;
 
     if (attributes_len > 0) {
@@ -443,7 +447,7 @@ static hal_error_t ks_match(hal_ks_t *ks,
         continue;
     }
 
-    result[*result_len] = ksv->db->ksi.names[b].name;
+    *previous_uuid = result[*result_len] = ksv->db->ksi.names[b].name;
     ++*result_len;
   }
 
@@ -471,8 +475,7 @@ static  hal_error_t ks_set_attribute(hal_ks_t *ks,
 
   ks_key_t * const k = &ksv->db->keys[b];
 
-  if (ksv->per_session && (k->client.handle  != slot->client_handle.handle ||
-                           k->session.handle != slot->session_handle.handle))
+  if (!key_visible_to_session(ksv, slot->client_handle, slot->session_handle, k))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   hal_rpc_pkey_attribute_t attributes[k->attributes_len + 1];
@@ -511,8 +514,7 @@ static  hal_error_t ks_get_attribute(hal_ks_t *ks,
 
   const ks_key_t * const k = &ksv->db->keys[b];
 
-  if (ksv->per_session && (k->client.handle  != slot->client_handle.handle ||
-                           k->session.handle != slot->session_handle.handle))
+  if (!key_visible_to_session(ksv, slot->client_handle, slot->session_handle, k))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   if (k->attributes_len == 0)
@@ -561,8 +563,7 @@ static hal_error_t ks_delete_attribute(hal_ks_t *ks,
 
   ks_key_t * const k = &ksv->db->keys[b];
 
-  if (ksv->per_session && (k->client.handle  != slot->client_handle.handle ||
-                           k->session.handle != slot->session_handle.handle))
+  if (!key_visible_to_session(ksv, slot->client_handle, slot->session_handle, k))
     return HAL_ERROR_KEY_NOT_FOUND;
 
   hal_rpc_pkey_attribute_t attributes[k->attributes_len + 1];