From f7c3a151c7b0a3f040ab9aa8d81c562684d3f2e8 Mon Sep 17 00:00:00 2001
From: Rob Austein <sra@hactrn.net>
Date: Tue, 1 Nov 2016 12:09:41 -0400
Subject: 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.
---
 ks_index.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)

(limited to 'ks_index.c')

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;
 }
 
-- 
cgit v1.2.3