Repository: borgbackup/borg

Issue:
check empty segments lists in shadow_index
while doing #5263, i tried to remove empty segments lists from the shadow_index, but then tests failed.

as they maybe shouldn't remain in there forever, this needs checking again

Discussion:
ThomasWaldmann: @enkore can you please try & review?
timmc: I notice that `Repository.put` doesn't add to `shadow_index` -- is that intentional? Not sure if there's an impact on this PR.
codecov-io: # [Codecov](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=h1) Report
> Merging [#5614](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=desc) (6f184df) into [master](https://codecov.io/gh/borgbackup/borg/commit/699256edbd072c60b995c493c2146aabe27905bb?el=desc) (699256e) will **decrease** coverage by `0.08%`.
> The diff coverage is `50.00%`.

[![Impacted file tree graph](https://codecov.io/gh/borgbackup/borg/pull/5614/graphs/tree.svg?width=650&height=150&src=pr&token=LssEpmW3o4)](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #5614      +/-   ##
==========================================
- Coverage   83.16%   83.07%   -0.09%     
==========================================
  Files          38       38              
  Lines       10139    10121      -18     
  Branches     1680     1679       -1     
==========================================
- Hits         8432     8408      -24     
- Misses       1209     1212       +3     
- Partials      498      501       +3     
```


| [Impacted Files](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/borg/repository.py](https://codecov.io/gh/borgbackup/borg/pull/5614/diff?src=pr&el=tree#diff-c3JjL2JvcmcvcmVwb3NpdG9yeS5weQ==) | `83.96% <50.00%> (-0.07%)` | :arrow_down: |
| [src/borg/archive.py](https://codecov.io/gh/borgbackup/borg/pull/5614/diff?src=pr&el=tree#diff-c3JjL2JvcmcvYXJjaGl2ZS5weQ==) | `81.10% <0.00%> (-0.41%)` | :arrow_down: |
| [src/borg/archiver.py](https://codecov.io/gh/borgbackup/borg/pull/5614/diff?src=pr&el=tree#diff-c3JjL2JvcmcvYXJjaGl2ZXIucHk=) | `79.91% <0.00%> (-0.12%)` | :arrow_down: |
| [src/borg/constants.py](https://codecov.io/gh/borgbackup/borg/pull/5614/diff?src=pr&el=tree#diff-c3JjL2JvcmcvY29uc3RhbnRzLnB5) | `100.00% <0.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=footer). Last update [699256e...c3a3f34](https://codecov.io/gh/borgbackup/borg/pull/5614?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

ThomasWaldmann: rebased on current master.
ThomasWaldmann: @timmc good catch! i did a little refactor and added a comment (see 41800bc).

we will have to check whether there is a bug or that has to be like that, not sure yet.
ThomasWaldmann: @timmc @enkore see discussion above and commits 41800bc and c7f0aac .
ThomasWaldmann: I'll merge this soon, but it would be good if there was some more independent review.

Patch:
diff --git a/src/borg/repository.py b/src/borg/repository.py
index 41dbe36f..091f2852 100644
--- a/src/borg/repository.py
+++ b/src/borg/repository.py
@@ -794,6 +794,8 @@ def complete_xfer(intermediate=True):
                     try:
                         self.shadow_index[key].remove(segment)
                     except (KeyError, ValueError):
+                        # do not remove entry with empty shadowed_segments list here,
+                        # it is needed for shadowed_put_exists code (see below)!
                         pass
                 elif tag == TAG_DELETE and not in_index:
                     # If the shadow index doesn't contain this key, then we can't say if there's a shadowed older tag,
@@ -845,6 +847,11 @@ def complete_xfer(intermediate=True):
                             new_segment, size = self.io.write_delete(key)
                         self.compact[new_segment] += size
                         segments.setdefault(new_segment, 0)
+                    else:
+                        # we did not keep the delete tag for key (see if-branch)
+                        if not self.shadow_index[key]:
+                            # shadowed segments list is empty -> remove it
+                            del self.shadow_index[key]
             assert segments[segment] == 0, 'Corrupted segment reference count - corrupted index or hints'
             unused.append(segment)
             pi.show()


Test patch:
diff --git a/src/borg/testsuite/repository.py b/src/borg/testsuite/repository.py
index 3a2d9236..ef142a8b 100644
--- a/src/borg/testsuite/repository.py
+++ b/src/borg/testsuite/repository.py
@@ -14,7 +14,7 @@
 from ..helpers import msgpack
 from ..locking import Lock, LockFailed
 from ..remote import RemoteRepository, InvalidRPCMethod, PathNotAllowed, ConnectionClosedWithHint, handle_remote_line
-from ..repository import Repository, LoggedIO, MAGIC, MAX_DATA_SIZE, TAG_DELETE
+from ..repository import Repository, LoggedIO, MAGIC, MAX_DATA_SIZE, TAG_DELETE, TAG_PUT, TAG_COMMIT
 from . import BaseTestCase
 from .hashindex import H
 
@@ -54,6 +54,16 @@ def add_keys(self):
         self.repository.put(H(2), b'boo')
         self.repository.delete(H(3))
 
+    def repo_dump(self, label=None):
+        label = label + ': ' if label is not None else ''
+        H_trans = {H(i): i for i in range(10)}
+        H_trans[None] = -1  # key == None appears in commits
+        tag_trans = {TAG_PUT: 'put', TAG_DELETE: 'del', TAG_COMMIT: 'comm'}
+        for segment, fn in self.repository.io.segment_iterator():
+            for tag, key, offset, size in self.repository.io.iter_objects(segment):
+                print("%s%s H(%d) -> %s[%d..+%d]" % (label, tag_trans[tag], H_trans[key], fn, offset, size))
+        print()
+
 
 class RepositoryTestCase(RepositoryTestCaseBase):
 
@@ -315,8 +325,10 @@ def test_moved_deletes_are_tracked(self):
         self.repository.put(H(1), b'1')
         self.repository.put(H(2), b'2')
         self.repository.commit(compact=False)
+        self.repo_dump('p1 p2 c')
         self.repository.delete(H(1))
         self.repository.commit(compact=True)
+        self.repo_dump('d1 cc')
         last_segment = self.repository.io.get_latest_segment() - 1
         num_deletes = 0
         for tag, key, offset, size in self.repository.io.iter_objects(last_segment):
@@ -327,11 +339,16 @@ def test_moved_deletes_are_tracked(self):
         assert last_segment in self.repository.compact
         self.repository.put(H(3), b'3')
         self.repository.commit(compact=True)
+        self.repo_dump('p3 cc')
         assert last_segment not in self.repository.compact
         assert not self.repository.io.segment_exists(last_segment)
         for segment, _ in self.repository.io.segment_iterator():
             for tag, key, offset, size in self.repository.io.iter_objects(segment):
                 assert tag != TAG_DELETE
+                assert key != H(1)
+        # after compaction, there should be no empty shadowed_segments lists left over.
+        # we have no put or del any more for H(1), so we lost knowledge about H(1).
+        assert H(1) not in self.repository.shadow_index
 
     def test_shadowed_entries_are_preserved(self):
         get_latest_segment = self.repository.io.get_latest_segment
@@ -372,16 +389,19 @@ def test_shadow_index_rollback(self):
         self.repository.delete(H(1))
         assert self.repository.shadow_index[H(1)] == [0]
         self.repository.commit(compact=True)
+        self.repo_dump('p1 d1 cc')
         # note how an empty list means that nothing is shadowed for sure
-        assert self.repository.shadow_index[H(1)] == []
+        assert self.repository.shadow_index[H(1)] == []  # because the delete is considered unstable
         self.repository.put(H(1), b'1')
         self.repository.delete(H(1))
+        self.repo_dump('p1 d1')
         # 0 put/delete; 1 commit; 2 compacted; 3 commit; 4 put/delete
         assert self.repository.shadow_index[H(1)] == [4]
         self.repository.rollback()
+        self.repo_dump('r')
         self.repository.put(H(2), b'1')
         # After the rollback segment 4 shouldn't be considered anymore
-        assert self.repository.shadow_index[H(1)] == []
+        assert self.repository.shadow_index[H(1)] == []  # because the delete is considered unstable
 
 
 class RepositoryAppendOnlyTestCase(RepositoryTestCaseBase):
@@ -826,7 +846,7 @@ def test_hints_behaviour(self):
         self.repository.put(H(42), b'foobar')  # see also do_compact()
         self.repository.commit(compact=True, threshold=0.0)  # compact completely!
         # nothing to compact any more! no info left about stuff that does not exist any more:
-        self.assert_equal(self.repository.shadow_index[H(0)], [])
+        self.assert_not_in(H(0), self.repository.shadow_index)
         # segment 0 was compacted away, no info about it left:
         self.assert_not_in(0, self.repository.compact)
         self.assert_not_in(0, self.repository.segments)