hal_ks_index_fsck() and a pile of debugging code.

The debugging code was for tracking down what turned out to be a race
condition in the Alpha's flash driver code (see sw/stm32); much of
this was temporary, and will be removed in a (near) future commit, but
some of the techniques were useful and belong in the repository in
case we need to pull them back for something similar in the future.

hal_ks_index_fsck() attempts to diagnose all the things I found wrong
in the ks_flash index after one long series of errors.  As presently
written, it doesn't attempt to fix anything, just diagnose errors: the
intent is that we can call this, before and after every modification
if necessary, to poinpoint exactly which calls introduce errors.  Once
things stablize a bit, we may want to crank down the number of calls
to this (it's a bit expensive, since it checks the entire index), and
perhaps add the ability to clean up whatever errors it might find; the
latter might be a good candidate for a CLI command.

8 files changed, 212 insertions, 29 deletions

diff --git a/Makefile b/Makefile
index afde6c4..08aaea2 100644
--- a/Makefile
+++ b/Makefile
@@ -33,7 +33,8 @@
 STATIC_CORE_STATE_BLOCKS = 32
 STATIC_HASH_STATE_BLOCKS = 10
 STATIC_HMAC_STATE_BLOCKS = 4
-STATIC_PKEY_STATE_BLOCKS = 6
+STATIC_PKEY_STATE_BLOCKS = 32
+STATIC_KS_VOLATILE_SLOTS = 128
 
 INC		= hal.h hal_internal.h
 LIB		= libhal.a
diff --git a/hal.h b/hal.h
index 10a78ed..d68a67b 100644
--- a/hal.h
+++ b/hal.h
@@ -150,6 +150,11 @@
   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")                 \
+  DEFINE_HAL_ERROR(HAL_ERROR_KSI_INDEX_UUID_MISORDERED, "Key index UUID misordered")                    \
+  DEFINE_HAL_ERROR(HAL_ERROR_KSI_INDEX_CHUNK_ORPHANED,  "Key index chunk orphaned")                     \
+  DEFINE_HAL_ERROR(HAL_ERROR_KSI_INDEX_CHUNK_MISSING,   "Key index chunk missing")                      \
+  DEFINE_HAL_ERROR(HAL_ERROR_KSI_INDEX_CHUNK_OVERLAPS,  "Key index chunk overlaps")                     \
+  DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE, "Wrong block type in keystore")                 \
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
diff --git a/hal_internal.h b/hal_internal.h
index 44deaf6..ee6c7d6 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -792,6 +792,13 @@ extern hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
                                         int *hint);
 
 /*
+ * Check the index for errors.  At least for the moment, this just
+ * reports errors, it doesn't attempt to fix them.
+ */
+
+extern hal_error_t hal_ks_index_fsck(hal_ks_index_t *ksi);
+
+/*
  * Keystore attribute utilities, for use by keystore drivers.
  *
  * Basic model here is probably to replace the "der" block in a key
diff --git a/ks_flash.c b/ks_flash.c
index 10df54b..c12aad4 100644
--- a/ks_flash.c
+++ b/ks_flash.c
@@ -46,6 +46,34 @@
 #include "stm-keystore.h"
 #undef HAL_OK
 
+#if 1 /* XXX Begin temporary debugging kludge */
+#warning Temporary debugging kludge, remove this
+
+/*
+ * Chasing what might be a race condition, except it's a bit too
+ * predictable.  Debugger breakpoint or 0.1 second delay is enough to
+ * hide it, so need something simple.  So try a simple ring buffer
+ * logging block numbers and actions.
+ */
+
+static unsigned debug_ring_counter = 0;
+
+static struct {
+  char code;                    /* One letter code describing action */
+  unsigned blockno;             /* Block number */
+  unsigned counter;             /* value of debug_ring_counter when logged */
+} debug_ring_log_buffer[64];
+
+static inline void debug_ring_log_event(const char code, const unsigned blockno)
+{
+  const unsigned i = debug_ring_counter % (sizeof(debug_ring_log_buffer)/sizeof(*debug_ring_log_buffer));
+  debug_ring_log_buffer[i].code    = code;
+  debug_ring_log_buffer[i].blockno = blockno;
+  debug_ring_log_buffer[i].counter = debug_ring_counter++;
+}
+
+#endif /* XXX End temporary debugging kludge */
+
 /*
  * Known block states.
  *
@@ -332,6 +360,8 @@ static hal_error_t block_read(const unsigned blockno, flash_block_t *block)
   if (block == NULL || blockno >= NUM_FLASH_BLOCKS || sizeof(*block) != KEYSTORE_SUBSECTOR_SIZE)
     return HAL_ERROR_IMPOSSIBLE;
 
+  debug_ring_log_event('r', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_read_data(block_offset(blockno),
                          block->bytes,
@@ -358,6 +388,8 @@ static hal_error_t block_read(const unsigned blockno, flash_block_t *block)
     return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
   }
 
+  debug_ring_log_event('R', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_read_data(block_offset(blockno) + KEYSTORE_PAGE_SIZE,
                          block->bytes + KEYSTORE_PAGE_SIZE,
@@ -381,6 +413,8 @@ static hal_error_t block_read_cached(const unsigned blockno, flash_block_t **blo
   if (block == NULL)
     return HAL_ERROR_IMPOSSIBLE;
 
+  debug_ring_log_event('c', blockno); /* XXX */
+
   if ((*block = cache_find_block(blockno)) != NULL)
     return HAL_OK;
 
@@ -405,12 +439,16 @@ static hal_error_t block_deprecate(const unsigned blockno)
   flash_block_header_t *header = (void *) page;
   uint32_t offset = block_offset(blockno);
 
+  debug_ring_log_event('d', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_read_data(offset, page, sizeof(page)) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
 
   header->block_status = BLOCK_STATUS_TOMBSTONE;
 
+  debug_ring_log_event('D', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_write_data(offset, page, sizeof(page)) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
@@ -429,6 +467,8 @@ static hal_error_t block_zero(const unsigned blockno)
 
   uint8_t page[KEYSTORE_PAGE_SIZE] = {0};
 
+  debug_ring_log_event('z', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_write_data(block_offset(blockno), page, sizeof(page)) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
@@ -445,6 +485,8 @@ static hal_error_t block_erase(const unsigned blockno)
   if (blockno >= NUM_FLASH_BLOCKS)
     return HAL_ERROR_IMPOSSIBLE;
 
+  debug_ring_log_event('e', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_erase_subsectors(blockno, blockno) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
@@ -467,6 +509,8 @@ static hal_error_t block_erase_maybe(const unsigned blockno)
   if (blockno >= NUM_FLASH_BLOCKS)
     return HAL_ERROR_IMPOSSIBLE;
 
+  debug_ring_log_event('m', blockno); /* XXX */
+
   uint8_t mask = 0xFF;
 
   for (uint32_t a = block_offset(blockno); a < block_offset(blockno + 1); a += KEYSTORE_PAGE_SIZE) {
@@ -504,6 +548,8 @@ static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
     break;
   }
 
+  debug_ring_log_event('w', blockno); /* XXX */
+
   /* Sigh, magic numeric return codes */
   if (keystore_write_data(block_offset(blockno), block->bytes, sizeof(*block)) != 1)
     return HAL_ERROR_KEYSTORE_ACCESS;
@@ -524,6 +570,8 @@ static hal_error_t block_update(const unsigned b1, flash_block_t *block,
   if (db.ksi.used == db.ksi.size)
     return HAL_ERROR_NO_KEY_INDEX_SLOTS;
 
+  debug_ring_log_event('u', b1); /* XXX */
+
   cache_release(block);
 
   hal_error_t err;
@@ -711,6 +759,11 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver)
     return err;
 
   /*
+   * We might want to call hal_ks_index_fsck() here, if we can figure
+   * out some safe set of recovery actions we can take.
+   */
+
+  /*
    * 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,
@@ -1019,7 +1072,7 @@ static hal_error_t ks_fetch(hal_ks_t *ks,
     return err;
 
   if (block_get_type(block) != BLOCK_TYPE_KEY)
-    return HAL_ERROR_KEY_NOT_FOUND;
+    return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
 
   cache_mark_used(block, b);
 
@@ -1072,11 +1125,12 @@ static hal_error_t ks_delete(hal_ks_t *ks,
   if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, n, NULL, b, &slot->hint)) != HAL_OK)
     return err;
 
-  for (int i = 0; i < n; i++) {
+  for (int i = 0; i < n; i++)
     cache_release(cache_find_block(b[i]));
+
+  for (int i = 0; i < n; i++)
     if ((err = block_zero(b[i])) != HAL_OK)
       return err;
-  }
 
   return block_erase_maybe(db.ksi.index[db.ksi.used]);
 }
@@ -1128,7 +1182,7 @@ static inline hal_error_t locate_attributes(flash_block_t *block, const unsigned
 
   if (chunk == 0) {
     if (block_get_type(block) != BLOCK_TYPE_KEY)
-      return HAL_ERROR_KEY_NOT_FOUND;
+      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* 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;
@@ -1136,7 +1190,7 @@ static inline hal_error_t locate_attributes(flash_block_t *block, const unsigned
 
   else {
     if (block_get_type(block) != BLOCK_TYPE_ATTR)
-      return HAL_ERROR_KEY_NOT_FOUND;
+      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
     *attrs_len = &block->attr.attributes_len;
     *bytes = block->attr.attributes;
     *bytes_len = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
diff --git a/ks_index.c b/ks_index.c
index 23ba8c1..4f08e5e 100644
--- a/ks_index.c
+++ b/ks_index.c
@@ -145,6 +145,43 @@ static inline void ks_heapsort(hal_ks_index_t *ksi)
   }
 }
 
+#define fsck(_ksi) \
+  do { hal_error_t _err = hal_ks_index_fsck(_ksi); if (_err != HAL_OK) return _err; } while (0)
+
+
+hal_error_t hal_ks_index_fsck(hal_ks_index_t *ksi)
+{
+  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
+      ksi->size == 0 || ksi->used > ksi->size)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  int cur, prev = -1;
+
+  for (cur = 0; cur < ksi->used; cur++) {
+
+    const int cmp = (prev < 0 ? -1 : hal_uuid_cmp(&ksi->names[ksi->index[prev]].name,
+                                                  &ksi->names[ksi->index[cur]].name));
+
+    const uint8_t cur_chunk = ksi->names[ksi->index[cur]].chunk;
+
+    const uint8_t prev_chunk = (prev < 0 ? 0 : ksi->names[ksi->index[prev]].chunk);
+
+    if (cmp > 0)
+      return HAL_ERROR_KSI_INDEX_UUID_MISORDERED;
+
+    if (cur_chunk > 0 && cmp != 0)
+      return HAL_ERROR_KSI_INDEX_CHUNK_ORPHANED;
+
+    if (cur_chunk > 0 && prev_chunk + 1 < cur_chunk)
+      return HAL_ERROR_KSI_INDEX_CHUNK_MISSING;
+
+    if (cur_chunk > 0 && prev_chunk + 1 > cur_chunk)
+      return HAL_ERROR_KSI_INDEX_CHUNK_OVERLAPS;
+  }
+
+  return HAL_OK;
+}
+
 hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
 {
   if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
@@ -156,6 +193,13 @@ hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
    */
 
   ks_heapsort(ksi);
+
+  /*
+   * One might think we should fsck here, but errors in the index
+   * at this point probably relate to errors in the supplied data,
+   * which only the driver knows how to clean up.
+   */
+
   return HAL_OK;
 }
 
@@ -171,6 +215,8 @@ hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   int ok = ks_find(ksi, name, chunk, hint, &where);
 
   if (blockno != NULL)
@@ -195,6 +241,8 @@ hal_error_t hal_ks_index_find_range(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   if (!ks_find(ksi, name, 0, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
@@ -235,6 +283,8 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   if (ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NAME_IN_USE;
 
@@ -256,6 +306,8 @@ hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
+  fsck(ksi);
+
   return HAL_OK;
 }
 
@@ -271,6 +323,8 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
@@ -291,6 +345,8 @@ hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
+  fsck(ksi);
+
   return HAL_OK;
 }
 
@@ -307,6 +363,8 @@ hal_error_t hal_ks_index_delete_range(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   if (ksi->used == 0 || !ks_find(ksi, name, 0, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
@@ -343,6 +401,8 @@ hal_error_t hal_ks_index_delete_range(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
+  fsck(ksi);
+
   return HAL_OK;
 }
 
@@ -361,6 +421,8 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
 
   int where;
 
+  fsck(ksi);
+
   if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
     return HAL_ERROR_KEY_NOT_FOUND;
 
@@ -385,6 +447,8 @@ hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
   if (hint != NULL)
     *hint = where;
 
+  fsck(ksi);
+
   return HAL_OK;
 }
 
diff --git a/ks_volatile.c b/ks_volatile.c
index 0f53c11..2e6ea3e 100644
--- a/ks_volatile.c
+++ b/ks_volatile.c
@@ -44,16 +44,12 @@
 
 #define KEK_LENGTH (bitsToBytes(256))
 
-#ifndef HAL_STATIC_PKEY_STATE_BLOCKS
-#define HAL_STATIC_PKEY_STATE_BLOCKS 0
+#ifndef STATIC_KS_VOLATILE_SLOTS
+#define STATIC_KS_VOLATILE_SLOTS HAL_STATIC_PKEY_STATE_BLOCKS
 #endif
 
-#ifndef HAL_KS_VOLATILE_SLOTS
-#define HAL_KS_VOLATILE_SLOTS HAL_STATIC_PKEY_STATE_BLOCKS
-#endif
-
-#ifndef HAL_KS_VOLATILE_ATTRIBUTE_SPACE
-#define HAL_KS_VOLATILE_ATTRIBUTE_SPACE 4096
+#ifndef STATIC_KS_VOLATILE_ATTRIBUTE_SPACE
+#define STATIC_KS_VOLATILE_ATTRIBUTE_SPACE 4096
 #endif
 
 /*
@@ -70,7 +66,7 @@ typedef struct {
   hal_session_handle_t  session;
   size_t                der_len;
   unsigned              attributes_len;
-  uint8_t               der[HAL_KS_WRAPPED_KEYSIZE + HAL_KS_VOLATILE_ATTRIBUTE_SPACE];
+  uint8_t               der[HAL_KS_WRAPPED_KEYSIZE + STATIC_KS_VOLATILE_ATTRIBUTE_SPACE];
 } ks_key_t;
 
 typedef struct {
@@ -97,7 +93,7 @@ typedef struct {
  * conditional testing whether either HAL_KS_*_SLOTS were nonzero.
  */
 
-#if HAL_KS_VOLATILE_SLOTS > 0
+#if STATIC_KS_VOLATILE_SLOTS > 0
 
 static ks_t volatile_ks;
 
@@ -156,10 +152,10 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver,
   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.index = gnaw(&mem, &len, sizeof(*ksv->db->ksi.index) * STATIC_KS_VOLATILE_SLOTS);
+  ksv->db->ksi.names = gnaw(&mem, &len, sizeof(*ksv->db->ksi.names) * STATIC_KS_VOLATILE_SLOTS);
+  ksv->db->keys      = gnaw(&mem, &len, sizeof(*ksv->db->keys)      * STATIC_KS_VOLATILE_SLOTS);
+  ksv->db->ksi.size  = STATIC_KS_VOLATILE_SLOTS;
   ksv->db->ksi.used  = 0;
 
   if (ksv->db            == NULL ||
@@ -174,7 +170,7 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver,
    * just populate the free list in block numerical order.
    */
 
-  for (int i = 0; i < HAL_KS_VOLATILE_SLOTS; i++)
+  for (int i = 0; i < STATIC_KS_VOLATILE_SLOTS; i++)
     ksv->db->ksi.index[i] = i;
 
   return hal_ks_index_setup(&ksv->db->ksi);
@@ -183,9 +179,9 @@ static hal_error_t ks_init(const hal_ks_driver_t * const driver,
 static hal_error_t ks_volatile_init(const hal_ks_driver_t * const driver)
 {
   const size_t len = (sizeof(*volatile_ks.db) +
-                      sizeof(*volatile_ks.db->ksi.index) * HAL_KS_VOLATILE_SLOTS +
-                      sizeof(*volatile_ks.db->ksi.names) * HAL_KS_VOLATILE_SLOTS +
-                      sizeof(*volatile_ks.db->keys)      * HAL_KS_VOLATILE_SLOTS);
+                      sizeof(*volatile_ks.db->ksi.index) * STATIC_KS_VOLATILE_SLOTS +
+                      sizeof(*volatile_ks.db->ksi.names) * STATIC_KS_VOLATILE_SLOTS +
+                      sizeof(*volatile_ks.db->keys)      * STATIC_KS_VOLATILE_SLOTS);
 
   uint8_t *mem = hal_allocate_static_memory(len);
 
@@ -613,7 +609,7 @@ const hal_ks_driver_t hal_ks_volatile_driver[1] = {{
   ks_delete_attribute
 }};
 
-#endif /* HAL_KS_VOLATILE_SLOTS > 0 */
+#endif /* STATIC_KS_VOLATILE_SLOTS > 0 */
 
 /*
  * Local variables:
diff --git a/libhal.py b/libhal.py
index 50209f9..0a79ce9 100644
--- a/libhal.py
+++ b/libhal.py
@@ -107,6 +107,11 @@ HALError.define(HAL_ERROR_KEYSTORE_LOST_DATA        = "Keystore appears to have
 HALError.define(HAL_ERROR_BAD_ATTRIBUTE_LENGTH      = "Bad attribute length")
 HALError.define(HAL_ERROR_ATTRIBUTE_NOT_FOUND       = "Attribute not found")
 HALError.define(HAL_ERROR_NO_KEY_INDEX_SLOTS        = "No key index slots available")
+HALError.define(HAL_ERROR_KSI_INDEX_UUID_MISORDERED = "Key index UUID misordered")
+HALError.define(HAL_ERROR_KSI_INDEX_CHUNK_ORPHANED  = "Key index chunk orphaned")
+HALError.define(HAL_ERROR_KSI_INDEX_CHUNK_MISSING   = "Key index chunk missing")
+HALError.define(HAL_ERROR_KSI_INDEX_CHUNK_OVERLAPS  = "Key index chunk overlaps")
+HALError.define(HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE = "Wrong block type in keystore")
 
 
 class Enum(int):
diff --git a/unit-tests.py b/unit-tests.py
index 5646add..d460a26 100644
--- a/unit-tests.py
+++ b/unit-tests.py
@@ -96,13 +96,13 @@ hsm  = None
 
 pin_map = { HAL_USER_NORMAL : "user_pin", HAL_USER_SO : "so_pin", HAL_USER_WHEEL : "wheel_pin" }
 
+
 def setUpModule():
     global hsm
     hsm = HSM()
 
-
 def tearDownModule():
-    hsm.logout_all()
+    hsm.logout()
     #hsm.close()
 
 
@@ -158,12 +158,12 @@ class TestPIN(TestCase):
     """
 
     def setUp(self):
-        hsm.logout_all()
+        hsm.logout()
         super(TestPIN, self).setUp()
 
     def tearDown(self):
         super(TestPIN, self).tearDown()
-        hsm.logout_all()
+        hsm.logout()
 
     def test_is_logged_in(self):
         "Test whether is_logged_in() returns correct exception when not logged in"
@@ -505,6 +505,55 @@ class TestPKeyECDSAInterop(TestCaseLoggedIn):
         self.load_sign_verify_ecdsa(HAL_DIGEST_ALGORITHM_SHA512, HAL_CURVE_P521)
 
 
+class TestPKeyList(TestCaseLoggedIn):
+    """
+    Tests involving PKey list and match functions.
+    """
+
+    # Some kind of race condition, don't understand it yet, but
+    # without the sleep, the flash keystore code occasionally reads
+    # zeroed pages immediately after a deletion (which itself zeros
+    # pages, which is suspicious, but I haven't spotted a problem
+    # there yet), with the sleep it doesn't.  Worrisome.
+
+    kludge_around_race_condition = False
+
+    def cleanup(self):
+        for uuid, flags in self.keys:
+            if self.kludge_around_race_condition and (flags & HAL_KEY_FLAG_TOKEN) != 0:
+                from time import sleep
+                sleep(0.1)
+            hsm.pkey_find(uuid, flags = flags).delete()
+
+    def load_keys(self, flags):
+        self.keys = []
+        self.addCleanup(self.cleanup)
+
+        for keytype, curve in static_keys:
+            obj = static_keys[keytype, curve]
+            if keytype in (HAL_KEY_TYPE_RSA_PRIVATE, HAL_KEY_TYPE_RSA_PUBLIC):
+                curve = HAL_CURVE_NONE
+                der   = obj.exportKey("DER")
+            elif keytype in (HAL_KEY_TYPE_EC_PRIVATE, HAL_KEY_TYPE_EC_PUBLIC):
+                der   = obj.to_der()
+            else:
+                raise ValueError
+            k = hsm.pkey_load(keytype, curve, der, flags)
+            self.keys.append((k.uuid, flags))
+            k.close()
+
+    def ks_list(self, flags):
+        self.load_keys(flags)
+        hsm.pkey_list(flags = flags)
+        hsm.pkey_match(flags = flags)
+
+    def test_ks_list_volatile(self):
+        self.ks_list(0)
+
+    def test_ks_list_token(self):
+        self.ks_list(HAL_KEY_FLAG_TOKEN)
+
+
 class TestPkeyECDSAVerificationNIST(TestCaseLoggedIn):
     """
     ECDSA verification tests based on Suite B Implementer's Guide to FIPS 186-3.
@@ -541,6 +590,8 @@ class TestPkeyECDSAVerificationNIST(TestCaseLoggedIn):
 #
 # * pkey list and match functions
 #
+# * token vs session key tests
+#
 # Preloaded keys should suffice for all of these.
 
 if False: