Avoid Revocation list overflow

When revocation list is full we remove two oldest entries and replace them with
single entry that block all IDs older or equal to the second oldest entry.

BUG: 27558454
Change-Id: I6b1a6c8f37fb3883605fb91f48beca7e60d71165
Reviewed-on: https://weave-review.googlesource.com/2881
Reviewed-by: Vitaly Buka <vitalybuka@google.com>

3 files changed, 65 insertions, 30 deletions

diff --git a/src/access_revocation_manager_impl.cc b/src/access_revocation_manager_impl.cc
index f039114..035e1ad 100644
--- a/src/access_revocation_manager_impl.cc
+++ b/src/access_revocation_manager_impl.cc
@@ -83,12 +83,37 @@ void AccessRevocationManagerImpl::Save(const DoneCallback& callback) {
   store_->SaveSettings(kConfigFileName, json, callback);
 }
 
-void AccessRevocationManagerImpl::RemoveExpired() {
+void AccessRevocationManagerImpl::Shrink() {
+  base::Time oldest[2] = {base::Time::Max(), base::Time::Max()};
   for (auto i = begin(entries_); i != end(entries_);) {
     if (i->expiration <= clock_->Now())
       i = entries_.erase(i);
-    else
+    else {
+      // Non-strict comparison to ensure counting same timestamps as different.
+      if (i->revocation <= oldest[0]) {
+        oldest[1] = oldest[0];
+        oldest[0] = i->revocation;
+      } else {
+        oldest[1] = std::min(oldest[1], i->revocation);
+      }
       ++i;
+    }
+  }
+  CHECK_GT(capacity_, 1u);
+  if (entries_.size() >= capacity_) {
+    // List is full so we are going to remove oldest entries from the list.
+    for (auto i = begin(entries_); i != end(entries_);) {
+      if (i->revocation <= oldest[1])
+        i = entries_.erase(i);
+      else {
+        ++i;
+      }
+    }
+    // And replace with a single rule to block everything older.
+    Entry all_blocking_entry;
+    all_blocking_entry.expiration = base::Time::Max();
+    all_blocking_entry.revocation = oldest[1];
+    entries_.insert(all_blocking_entry);
   }
 }
 
@@ -99,8 +124,6 @@ void AccessRevocationManagerImpl::AddEntryAddedCallback(
 
 void AccessRevocationManagerImpl::Block(const Entry& entry,
                                         const DoneCallback& callback) {
-  // Iterating is OK as Save below is more expensive.
-  RemoveExpired();
   if (entry.expiration <= clock_->Now()) {
     if (!callback.is_null()) {
       ErrorPtr error;
@@ -110,15 +133,10 @@ void AccessRevocationManagerImpl::Block(const Entry& entry,
     }
     return;
   }
-  if (entries_.size() >= capacity_) {
-    if (!callback.is_null()) {
-      ErrorPtr error;
-      Error::AddTo(&error, FROM_HERE, "blacklist_is_full",
-                   "Unable to store more entries");
-      callback.Run(std::move(error));
-    }
-    return;
-  }
+
+  // Iterating is OK as Save below is more expensive.
+  Shrink();
+  CHECK_LT(entries_.size(), capacity_);
 
   auto existing = entries_.find(entry);
   if (existing != entries_.end()) {
diff --git a/src/access_revocation_manager_impl.h b/src/access_revocation_manager_impl.h
index 0ee253e..9aed36a 100644
--- a/src/access_revocation_manager_impl.h
+++ b/src/access_revocation_manager_impl.h
@@ -36,7 +36,7 @@ class AccessRevocationManagerImpl : public AccessRevocationManager {
  private:
   void Load();
   void Save(const DoneCallback& callback);
-  void RemoveExpired();
+  void Shrink();
 
   struct EntryIdsLess {
     bool operator()(const Entry& l, const Entry& r) const {
diff --git a/src/access_revocation_manager_impl_unittest.cc b/src/access_revocation_manager_impl_unittest.cc
index b0b774b..afc63fe 100644
--- a/src/access_revocation_manager_impl_unittest.cc
+++ b/src/access_revocation_manager_impl_unittest.cc
@@ -112,29 +112,46 @@ TEST_F(AccessRevocationManagerImplTest, BlockExpired) {
                   }));
 }
 
-TEST_F(AccessRevocationManagerImplTest, BlockListIsFull) {
+TEST_F(AccessRevocationManagerImplTest, BlockListOverflow) {
+  EXPECT_CALL(config_store_, LoadSettings("black_list")).WillOnce(Return(""));
+  manager_.reset(new AccessRevocationManagerImpl{&config_store_, 10, &clock_});
+
   EXPECT_CALL(config_store_, SaveSettings("black_list", _, _))
       .WillRepeatedly(testing::WithArgs<1, 2>(testing::Invoke(
           [](const std::string& json, const DoneCallback& callback) {
             if (!callback.is_null())
               callback.Run(nullptr);
           })));
-  for (size_t i = manager_->GetSize(); i < manager_->GetCapacity(); ++i) {
-    manager_->Block(
-        {{99, static_cast<uint8_t>(i / 256), static_cast<uint8_t>(i % 256)},
-         {8, 8, 8},
-         base::Time::FromTimeT(1419970000),
-         base::Time::FromTimeT(1419990000)},
-        {});
-    EXPECT_EQ(i + 1, manager_->GetSize());
+
+  EXPECT_EQ(0u, manager_->GetSize());
+
+  // Trigger overflow several times.
+  for (size_t i = 0; i < manager_->GetCapacity() + 3; ++i) {
+    bool callback_called = false;
+    manager_->Block({{99, static_cast<uint8_t>(i), static_cast<uint8_t>(i)},
+                     {8, 8, 8},
+                     base::Time::FromTimeT(1419970000 + i),
+                     base::Time::FromTimeT(1419990000)},
+                    base::Bind([&callback_called](ErrorPtr error) {
+                      callback_called = true;
+                      EXPECT_FALSE(error);
+                    }));
+    EXPECT_TRUE(callback_called);
+  }
+  EXPECT_EQ(manager_->GetCapacity(), manager_->GetSize());
+
+  // We didn't block these ids, so we can use this to check if all_blocking
+  // issue is set for correct revocation time.
+  EXPECT_TRUE(manager_->IsBlocked({1}, {2}, base::Time::FromTimeT(1419970003)));
+  EXPECT_FALSE(
+      manager_->IsBlocked({1}, {2}, base::Time::FromTimeT(1419970004)));
+
+  // Check if all blocking rules still work.
+  for (size_t i = 0; i < manager_->GetCapacity() + 3; ++i) {
+    EXPECT_TRUE(manager_->IsBlocked(
+        {99, static_cast<uint8_t>(i), static_cast<uint8_t>(i)}, {8, 8, 8},
+        base::Time::FromTimeT(1419970000 + i)));
   }
-  manager_->Block({{99},
-                   {8, 8, 8},
-                   base::Time::FromTimeT(1419970000),
-                   base::Time::FromTimeT(1419990000)},
-                  base::Bind([](ErrorPtr error) {
-                    EXPECT_TRUE(error->HasError("blacklist_is_full"));
-                  }));
 }
 
 TEST_F(AccessRevocationManagerImplTest, IsBlockedIdsNotMacth) {