From 02a76abb8b3cfd27b4481ad6aadfac8550dcca57 Mon Sep 17 00:00:00 2001
From: Ivan Grokhotkov <ivan@espressif.com>
Date: Fri, 22 Feb 2019 17:28:43 +0800
Subject: [PATCH] nvs: do eager cleanup of HashListBlocks

Previously when HashList was removing items, HashListBlocks were
removed lazily. This resulted in empty HashListBlocks dangling around
in full pages, even when all items have been erased. These blocks
would only be deleted when NVS was re-initialized
(nvs_flash_deinit/nvs_flash_init).

This change does eager cleanup instead, based on the code from
@negativekelvin offered in
https://github.com/espressif/esp-idf/issues/1642#issuecomment-367227994.

Closes https://github.com/espressif/esp-idf/issues/1642.
---
 .../nvs_flash/src/nvs_item_hash_list.cpp      | 13 +++++-
 .../nvs_flash/test_nvs_host/test_nvs.cpp      | 41 +++++++++++++++++++
 2 files changed, 53 insertions(+), 1 deletion(-)

diff --git a/components/nvs_flash/src/nvs_item_hash_list.cpp b/components/nvs_flash/src/nvs_item_hash_list.cpp
index 845dd09106..a6cfdac1e2 100644
--- a/components/nvs_flash/src/nvs_item_hash_list.cpp
+++ b/components/nvs_flash/src/nvs_item_hash_list.cpp
@@ -64,15 +64,22 @@ void HashList::erase(size_t index, bool itemShouldExist)
 {
     for (auto it = mBlockList.begin(); it != mBlockList.end();) {
         bool haveEntries = false;
+        bool foundIndex = false;
         for (size_t i = 0; i < it->mCount; ++i) {
             if (it->mNodes[i].mIndex == index) {
                 it->mNodes[i].mIndex = 0xff;
-                return;
+                foundIndex = true;
+                /* found the item and removed it */
             }
             if (it->mNodes[i].mIndex != 0xff) {
                 haveEntries = true;
             }
+            if (haveEntries && foundIndex) {
+                /* item was found, and HashListBlock still has some items */
+                return;
+            }
         }
+        /* no items left in HashListBlock, can remove */
         if (!haveEntries) {
             auto tmp = it;
             ++it;
@@ -81,6 +88,10 @@ void HashList::erase(size_t index, bool itemShouldExist)
         } else {
             ++it;
         }
+        if (foundIndex) {
+            /* item was found and empty HashListBlock was removed */
+            return;
+        }
     }
     if (itemShouldExist) {
         assert(false && "item should have been present in cache");
diff --git a/components/nvs_flash/test_nvs_host/test_nvs.cpp b/components/nvs_flash/test_nvs_host/test_nvs.cpp
index 7203ef733c..06b3effc06 100644
--- a/components/nvs_flash/test_nvs_host/test_nvs.cpp
+++ b/components/nvs_flash/test_nvs_host/test_nvs.cpp
@@ -284,6 +284,47 @@ TEST_CASE("Page handles invalid CRC of variable length items", "[nvs][cur]")
     }
 }
 
+class HashListTestHelper : public HashList
+{
+    public:
+        size_t getBlockCount()
+        {
+            return mBlockList.size();
+        }
+};
+
+TEST_CASE("HashList is cleaned up as soon as items are erased", "[nvs]")
+{
+    HashListTestHelper hashlist;
+    // Add items
+    const size_t count = 128;
+    for (size_t i = 0; i < count; ++i) {
+        char key[16];
+        snprintf(key, sizeof(key), "i%ld", (long int)i);
+        Item item(1, ItemType::U32, 1, key);
+        hashlist.insert(item, i);
+    }
+    INFO("Added " << count << " items, " << hashlist.getBlockCount() << " blocks");
+    // Remove them in reverse order
+    for (size_t i = count; i > 0; --i) {
+        hashlist.erase(i - 1, true);
+    }
+    CHECK(hashlist.getBlockCount() == 0);
+    // Add again
+    for (size_t i = 0; i < count; ++i) {
+        char key[16];
+        snprintf(key, sizeof(key), "i%ld", (long int)i);
+        Item item(1, ItemType::U32, 1, key);
+        hashlist.insert(item, i);
+    }
+    INFO("Added " << count << " items, " << hashlist.getBlockCount() << " blocks");
+    // Remove them in the same order
+    for (size_t i = 0; i < count; ++i) {
+        hashlist.erase(i, true);
+    }
+    CHECK(hashlist.getBlockCount() == 0);
+}
+
 TEST_CASE("can init PageManager in empty flash", "[nvs]")
 {
     SpiFlashEmulator emu(4);
-- 
2.50.1