(couchdb) branch do-not-allow-an-inconsistent-cache created (now ef843b919)

[va...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

vatamane pushed a change to branch do-not-allow-an-inconsistent-cache
in repository https://gitbox.apache.org/repos/asf/couchdb.git


      at ef843b919 Make sure we never get an inconsistent couch_lru cache

This branch includes the following new commits:

     new ef843b919 Make sure we never get an inconsistent couch_lru cache

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.

(couchdb) 01/01: Make sure we never get an inconsistent couch_lru cache

[va...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

vatamane pushed a commit to branch do-not-allow-an-inconsistent-cache
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit ef843b919a6bc33b21010f782519b9e878b225b2
Author: Nick Vatamaniuc <va...@gmail.com>
AuthorDate: Sun Aug 4 23:56:08 2024 -0400

    Make sure we never get an inconsistent couch_lru cache
    
    Previously, calling insert multiple times for the same db, created multiple tree
    entries and only one map entry. Fix this but ensuring the cache can never be
    inconsistent as a result of performing any number of inserts or updates.
    
    This should fix the function clause described in #5168. A detailed example on
    how this double insert leads to the function clause follows:
    
     * Calling insert twice for database `Db` might make the cache look something
     like this:
    ```
    {gb_tree([{100, Db}, ..., {200, Db}, ...]), #{..., Db => 200, ...}}
    ```
    
     * During traversal when closing, if the first entry (100) is idle, we'd try to update
    it (bump it). But when bumping, we'd pick out `200` as the key to delete from
    the `Tree`, instead of 100! So we'd delete 200 and may bump to some higher
    number like `300`.
    
     * To recap, at this point the iterator would be stopped at `{100, Db}` with
     the rest of iterator tree looking like `[..., {200, Db}, ...]` and the `Tree`
     accumulator will look something like `[{100, Db}, ..., {300, Db}, ...]`.
    
     * The iterator continues traversing and reaches the `{200, Db}` entry. If it's
     idle, it will try to delete it from the `Tree`. But the tree, doesn't have a
     `200` entry any longer, it has a `300` which leads to a function clause error
     as seen in #5168.
    
    While at it, make sure we get complete 100% test coverage, add a previously
    failing test case, even though it doesn't really apply after the the fix, it's
    mostly for historical reasons.
---
 src/couch/src/couch_lru.erl | 71 ++++++++++++++++++++++++++++++---------------
 1 file changed, 48 insertions(+), 23 deletions(-)

diff --git a/src/couch/src/couch_lru.erl b/src/couch/src/couch_lru.erl
index 437e82d55..8a795cad9 100644
--- a/src/couch/src/couch_lru.erl
+++ b/src/couch/src/couch_lru.erl
@@ -21,26 +21,33 @@
 new() ->
     {gb_trees:empty(), #{}}.
 
+%% Inserting an dbname will check that that we
 -spec insert(binary(), cache()) -> cache().
-insert(DbName, {Tree0, #{} = Map0}) ->
-    Lru = couch_util:unique_monotonic_integer(),
-    {gb_trees:insert(Lru, DbName, Tree0), Map0#{DbName => Lru}}.
+insert(DbName, {Tree, #{} = Map} = Cache) ->
+    case Map of
+        #{DbName := Old} ->
+            update_int(Old, DbName, Cache);
+        #{} ->
+            New = couch_util:unique_monotonic_integer(),
+            {gb_trees:insert(New, DbName, Tree), Map#{DbName => New}}
+    end.
+
+%% Update bumps the entry but only if it already exists. If it doesn't exist,
+%% it won't be inserted.
 
 -spec update(binary(), cache()) -> cache().
-update(DbName, {Tree0, #{} = Map0}) ->
-    case Map0 of
+update(DbName, {Tree, #{} = Map} = Cache) ->
+    case Map of
         #{DbName := Old} ->
-            New = couch_util:unique_monotonic_integer(),
-            Tree = gb_trees:insert(New, DbName, gb_trees:delete(Old, Tree0)),
-            {Tree, Map0#{DbName := New}};
+            update_int(Old, DbName, Cache);
         #{} ->
             % We closed this database before processing the update.  Ignore
-            {Tree0, Map0}
+            {Tree, Map}
     end.
 
 %% Attempt to close the oldest idle database. This function also cleans deleted
 %% and locked entries from the Lru and also bumps busy entries until the first
-%% idle entry is found. If not entry is found it returns `false`. In that case
+%% idle entry is found. If no entry is found, it returns `false`. In that case
 %% all bumped entries are lost as heap garbage.
 
 -spec close(cache()) -> {true, cache()} | false.
@@ -49,6 +56,11 @@ close({Tree, _} = Cache) ->
 
 %% internals
 
+update_int(Old, DbName, {Tree, #{} = Map}) ->
+    New = couch_util:unique_monotonic_integer(),
+    Tree1 = gb_trees:insert(New, DbName, gb_trees:delete(Old, Tree)),
+    {Tree1, Map#{DbName := New}}.
+
 close_int(none, {_Tree, #{}}) ->
     false;
 close_int({Lru, DbName, Iter}, {Tree, #{} = Map} = Cache) ->
@@ -91,11 +103,13 @@ couch_lru_test_() ->
             ?TDEF_FE(t_insert),
             ?TDEF_FE(t_insert_duplicate),
             ?TDEF_FE(t_update),
+            ?TDEF_FE(t_update_non_existent),
             ?TDEF_FE(t_close_empty),
             ?TDEF_FE(t_close_unlocked_idle),
             ?TDEF_FE(t_close_bump_busy_all),
             ?TDEF_FE(t_close_bump_busy_one),
-            ?TDEF_FE(t_close_entry_one_is_missing)
+            ?TDEF_FE(t_close_entry_one_is_missing),
+            ?TDEF_FE(t_multiple_inserts_and_close)
         ]
     }.
 
@@ -121,10 +135,10 @@ t_insert_duplicate(_) ->
     % instead which would reap the old LRU entry
     %
     {Tree, Map} = insert(?DB1, insert(?DB1, new())),
-    ?assertEqual(2, gb_trees:size(Tree)),
+    ?assertEqual(1, gb_trees:size(Tree)),
     ?assertEqual(1, map_size(Map)),
     ?assertMatch(#{?DB1 := _}, Map),
-    ?assertMatch([{_, ?DB1}, {_, ?DB1}], gb_trees:to_list(Tree)).
+    ?assertMatch([{_, ?DB1}], gb_trees:to_list(Tree)).
 
 t_update(_) ->
     % Insert followed by update.
@@ -135,6 +149,15 @@ t_update(_) ->
     #{?DB1 := Int} = Map,
     ?assertEqual([{Int, ?DB1}], gb_trees:to_list(Tree)).
 
+t_update_non_existent(_) ->
+    % Updating a non-existent item is a no-op
+    {Tree, Map} = update(?DB2, insert(?DB1, new())),
+    ?assertEqual(1, gb_trees:size(Tree)),
+    ?assertEqual(1, map_size(Map)),
+    ?assertMatch(#{?DB1 := _}, Map),
+    #{?DB1 := Int} = Map,
+    ?assertEqual([{Int, ?DB1}], gb_trees:to_list(Tree)).
+
 t_close_empty(_) ->
     ?assertEqual(false, close(new())).
 
@@ -197,17 +220,19 @@ t_close_entry_one_is_missing({Dbs, _, [_Pid1, Pid2]}) ->
     ?assertEqual(0, map_size(Map1)),
     ?assertNot(is_process_alive(Pid2)).
 
+t_multiple_inserts_and_close(_) ->
+    % Insert same entry twice, then close. Previously insert had a bug where a
+    % double insert would add two tree entries for a single map entry. Then,
+    % during the close traversal, if one instances was busy and the other idle,
+    % we'd crash with function clause in a function clause in gb_trees:delete/2
+    % (See issue #5166 for details)
+    {_, Map} = Cache = insert(?DB1, insert(?DB1, new())),
+    meck:expect(couch_db, is_idle, 1, meck:seq([meck:val(false), meck:val(true)])),
+    ?assertEqual(false, close(Cache)).
+
 setup() ->
-    Pid1 = spawn(fun() ->
-        receive
-            something -> ok
-        end
-    end),
-    Pid2 = spawn(fun() ->
-        receive
-            something -> ok
-        end
-    end),
+    Pid1 = spawn(fun() -> timer:sleep(9999999) end),
+    Pid2 = spawn(fun() -> timer:sleep(9999999) end),
     Dbs = ets:new(unique_name(), [named_table, public, {keypos, #entry.name}]),
     DbsPids = ets:new(unique_name(), [named_table, public]),
     ets:insert(Dbs, #entry{name = ?DB1, db = ?DB1, pid = Pid1, lock = unlocked}),