Merge lp:~barry/ubuntu-system-image/lp1444347 into lp:ubuntu-system-image/server

[Barry Warsaw]

Addresses LP: #1444347 by ensuring that any hardlinks which at first appear not to change between the source and target, but which their underlying link target *does* change, gets properly modified in the diff. This handles the following cases (among others):

source:
a (regular file)
b -> a (via hardlink)

target
a (regular file, modified)
b -> a (via hardlink)

If the diff doesn't not also include b then after application of the diff, b will point to a's *old* inode, but not the "new" a. This branch ensures that in this case, b also gets modified by the diff so that it will point to a's new inode.

Coincidentally, this also fixes a related previously broken case:

source:
a (regular file)
b -> a (via hardlink)

target:
b (regular file)
a -> b (via hardlink)

In this case, both a and b need to be modified in the diff.

This branch includes a few other drive-by improvements.

* Rather than use hard to read nested indexes to get at the bits of information, we use a namedtuple for the internal data structures, which allow us to use easy to read attribute access to ensure we're getting at the bits and pieces we intend to get to.

* Along those lines, this actually fixes some broken indexing in the big "switched hardlinks" conditional. E.g. devminor wasn't being checked previously, nor was gid. Those are now being checked.

* Lots of comments :)

* A few minor code style improvements.

One more important note as you're reviewing this branch. There is a change in an existing test, but I believe it is legitimate. In the original test, the hardlink c/h -> d did not get modified, but this is exactly the case we're trying to fix above. In the test, d does change but the hardlink to d (i.e. c/h) wasn't being changed. That means that after the delta, c/h would point to the old d inode, and we want it to point to the new d.

[Caio Begotti (caio1982)]

Looks alright given the bug info, even though I can't reproduce or test it in a device myself :-)

review: Approve

[Steve Langasek (vorlon)]

Applying the changes to the test suite without the changes to the code, I see only the following set of test failures:

test_generate_tarball (systemimage.tests.test_diff.DiffTests) ... FAIL
test_print_changes (systemimage.tests.test_diff.DiffTests) ... FAIL
test_link_count_2_order_ab (systemimage.tests.test_diff.TestHardLinkTargetIsModified) ... FAIL

Crucially, the two unpack tests did *not* fail:

test_unpack_ab (systemimage.tests.test_diff.TestHardLinkTargetIsModified) ... ok
test_unpack_ab_swap_roles (systemimage.tests.test_diff.TestHardLinkTargetIsModified) ... ok

This indicates that the unpack tests have not succeeded in modeling the failure that was seen in the wild (see further comments inline).

Without that, I don't think we can be confident in the correctness of this fix.

I've posted a follow-up comment on the bug with some analysis of the original failed delta. I believe the processing of the 'removed' file is key - in the original scenario, system/usr/bin/python3.4m is removed and then re-unpacked, and system/usr/bin/python3.4 is unchanged as a result (because the removal breaks the relationship between the two hardlinks).

The unpack tests need to accurately replicate the behavior of the upgrader.

review: Needs Fixing

[lp:~barry/ubuntu-system-image/lp1444347]

274. By Barry Warsaw on 2015-06-01

A more accurate test of the unpack case.

[Barry Warsaw (barry)]

Good catch, thanks! I've merged your branch into mine, so this should be ready to go. I'm running the full tox suite locally, but I expect it to pass.

=== modified file 'lib/systemimage/diff.py'
--- lib/systemimage/diff.py	2015-04-27 20:04:09 +0000
+++ lib/systemimage/diff.py	2015-06-01 16:00:55 +0000
@@ -20,6 +20,7 @@
 import tarfile
 import time
 
+from collections import namedtuple
 from io import BytesIO
 
 
@@ -41,6 +42,14 @@
     return fd_source.read() == fd_target.read()
 
 
+# For the data portion of the set and dict contents.
+FHash = namedtuple('FHash', 'mode devmajor devminor type uid gid size mtime')
+# The set contents record.
+SContent = namedtuple('SContent', 'path filetype data')
+# The dict contents record.
+DContent = namedtuple('DContent', 'filetype data')
+
+
 def list_tarfile(tarfile):
     """
         Walk through a tarfile and generate a list of the content.
@@ -55,22 +64,23 @@
 
     for entry in tarfile:
         if entry.isdir():
-            set_content.add((entry.path, "dir", None))
-            dict_content[entry.path] = ("dir", None)
+            set_content.add(SContent(entry.path, "dir", None))
+            dict_content[entry.path] = DContent("dir", None)
         else:
-            fhash = ("%s" % entry.mode,
-                     "%s" % entry.devmajor,
-                     "%s" % entry.devminor,
-                     "%s" % entry.type.decode("utf-8"),
-                     "%s" % entry.uid,
-                     "%s" % entry.gid,
-                     "%s" % entry.size,
-                     "%s" % entry.mtime)
-
-            set_content.add((entry.path, "file", fhash))
-            dict_content[entry.path] = ("file", fhash)
-
-    return (set_content, dict_content)
+            fhash = FHash(
+                "%s" % entry.mode,
+                "%s" % entry.devmajor,
+                "%s" % entry.devminor,
+                "%s" % entry.type.decode("utf-8"),
+                "%s" % entry.uid,
+                "%s" % entry.gid,
+                "%s" % entry.size,
+                "%s" % entry.mtime)
+
+            set_content.add(SContent(entry.path, "file", fhash))
+            dict_content[entry.path] = DContent("file", fhash)
+
+    return set_content, dict_content
 
 
 class ImageDiff:
@@ -87,15 +97,12 @@
             Scan the content of an image and return the image tuple.
             This also caches the content for further use.
         """
-
-        if image not in ("source", "target"):
+        image_file = getattr(self, image + "_file", None)
+        if image_file is None:
             raise KeyError("Invalid image '%s'." % image)
 
-        image_file = getattr(self, "%s_file" % image)
-
         content = list_tarfile(image_file)
-
-        setattr(self, "%s_content" % image, content)
+        setattr(self, image + "_content", content)
         return content
 
     def compare_images(self):
@@ -105,63 +112,94 @@
 
             The set contains tuples of (path, changetype).
         """
-        if not self.source_content:
+        if self.source_content is None:
             self.scan_content("source")
 
-        if not self.target_content:
+        if self.target_content is None:
             self.scan_content("target")
 
+        source_set, source_dict = self.source_content
+        target_set, target_dict = self.target_content
+
         # Find the changes in the two trees
         changes = set()
-        for change in self.source_content[0] \
-                .symmetric_difference(self.target_content[0]):
-            if change[0] not in self.source_content[1]:
-                changetype = "add"
-            elif change[0] not in self.target_content[1]:
-                changetype = "del"
+        for change in source_set.symmetric_difference(target_set):
+            if change.path not in source_dict:
+                change_type = "add"
+            elif change.path not in target_dict:
+                change_type = "del"
             else:
-                changetype = "mod"
-            changes.add((change[0], changetype))
+                change_type = "mod"
+            changes.add((change.path, change_type))
+
+        # Do a second pass through the source and target sets, looking for any
+        # hardlinks that point to a file that's being modified in the target.
+        # These links must get also get modified or they'll end up pointing to
+        # the old inode.
+        for no_change in source_set.intersection(target_set):
+            if no_change.filetype == "file" and no_change.data.type == "1":
+                # This is a hardlink which exists in both the source and
+                # target, *and* points to the same link target (by virtue of
+                # the set intersection).
+                changes.add((no_change.path, "mod"))
 
         # Ignore files that only vary in mtime
         # (separate loop to run after de-dupe)
         for change in sorted(changes):
-            if change[1] == "mod":
-                fstat_source = self.source_content[1][change[0]][1]
-                fstat_target = self.target_content[1][change[0]][1]
+            change_path, change_type = change
+            if change_type == "mod":
+                fstat_source = source_dict[change_path].data
+                fstat_target = target_dict[change_path].data
 
                 # Skip differences between directories and files
                 if not fstat_source or not fstat_target:  # pragma: no cover
                     continue
 
-                # Deal with switched hardlinks
-                if (fstat_source[0:2] == fstat_target[0:2] and
-                        fstat_source[3] != fstat_target[3] and
-                        (fstat_source[3] == "1" or fstat_target[3] == "1") and
-                        fstat_source[4:5] == fstat_target[4:5] and
-                        fstat_source[7] == fstat_target[7]):
-                    source_file = self.source_file.getmember(change[0])
-                    target_file = self.target_file.getmember(change[0])
+                # Deal with switched hardlinks.
+                #
+                # stgraber says on 2015-05-27: this was trying to solve the
+                # case where the hardlink target would be placed *after* the
+                # hardlink in the tar archive, leading to a hardlink being
+                # created to the wrong file at unpack.  barry thinks: ???
+                if (
+                        fstat_source.mode == fstat_target.mode
+                        and fstat_source.devmajor == fstat_target.devmajor
+                        and fstat_source.devminor == fstat_target.devminor
+                        # "1" is the LNKTYPE, i.e. hard link.
+                        and (fstat_source.type == "1" or
+                             fstat_target.type == "1")
+                        and fstat_source.uid == fstat_target.uid
+                        and fstat_source.gid == fstat_target.gid
+                        # size is ignored since it is always 0 for hardlinks.
+                        and fstat_source.mtime == fstat_target.mtime):
+                    source_file = self.source_file.getmember(change_path)
+                    target_file = self.target_file.getmember(change_path)
                     if compare_files(
-                            self.source_file.extractfile(change[0]),
-                            self.target_file.extractfile(change[0])):
+                            self.source_file.extractfile(change_path),
+                            self.target_file.extractfile(change_path)):
                         changes.remove(change)
                         continue
 
-                # Deal with regular files
+                # Deal with regular files.  Compare all attributes of the file
+                # except the mtime.
                 if fstat_source[0:7] == fstat_target[0:7]:
-                    source_file = self.source_file.getmember(change[0])
-                    target_file = self.target_file.getmember(change[0])
-
-                    if (source_file.linkpath
+                    source_file = self.source_file.getmember(change_path)
+                    target_file = self.target_file.getmember(change_path)
+                    # Symlinks that point to the same file in both the source
+                    # and target can be ignored, however *hardlinks* cannot,
+                    # since the inode they point to may change out from
+                    # underneath them.
+                    if (
+                            source_file.type == "2"
+                            and target_file.type == "2"
                             and source_file.linkpath == target_file.linkpath):
                         changes.remove(change)
                         continue
 
                     if (source_file.isfile() and target_file.isfile()
                             and compare_files(
-                                self.source_file.extractfile(change[0]),
-                                self.target_file.extractfile(change[0]))):
+                                self.source_file.extractfile(change_path),
+                                self.target_file.extractfile(change_path))):
                         changes.remove(change)
                         continue
 

=== modified file 'lib/systemimage/tests/test_diff.py'
--- lib/systemimage/tests/test_diff.py	2015-04-27 20:04:09 +0000
+++ lib/systemimage/tests/test_diff.py	2015-06-01 16:00:55 +0000
@@ -15,6 +15,7 @@
 # You should have received a copy of the GNU General Public License
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
+import os
 import shutil
 import sys
 import tarfile
@@ -26,11 +27,14 @@
 
 
 class DiffTests(unittest.TestCase):
+    maxDiff = None
+
     def setUp(self):
-        temp_directory = tempfile.mkdtemp()
+        self.temp_directory = temp_directory = tempfile.mkdtemp()
+        self.addCleanup(shutil.rmtree, temp_directory)
 
-        source_tarball_path = "%s/source.tar" % temp_directory
-        target_tarball_path = "%s/target.tar" % temp_directory
+        source_tarball_path = os.path.join(temp_directory, "source.tar")
+        target_tarball_path = os.path.join(temp_directory, "target.tar")
 
         source_tarball = tarfile.open(
             source_tarball_path, "w", encoding="utf-8")
@@ -205,10 +209,6 @@
         self.imagediff = ImageDiff(source_tarball_path, target_tarball_path)
         self.source_tarball_path = source_tarball_path
         self.target_tarball_path = target_tarball_path
-        self.temp_directory = temp_directory
-
-    def tearDown(self):
-        shutil.rmtree(self.temp_directory)
 
     def test_content(self):
         content_set, content_dict = self.imagediff.scan_content("source")
@@ -249,10 +249,11 @@
         output = sys.stdout.getvalue()
         sys.stdout = old_stdout
 
-        self.assertEqual(output, """ - b (del)
+        self.assertMultiLineEqual(output, """ - b (del)
  - c/a_i (add)
  - c/c (add)
  - c/d (mod)
+ - c/h (mod)
  - c/j (add)
  - dir (mod)
  - e (add)
@@ -269,13 +270,165 @@
         tarball = tarfile.open(output_tarball, "r")
 
         files_list = [entry.name for entry in tarball]
-        self.assertEqual(files_list, ['removed', 'c/c', 'c/a_i', 'c/d', 'c/j',
-                                      'dir', 'e', 'f', 'system/o',
-                                      'system/o.1'])
-
+        self.assertEqual(files_list, [
+            'removed',
+            'c/c',
+            'c/a_i',
+            'c/d',
+            'c/h',
+            'c/j',
+            'dir',
+            'e',
+            'f',
+            'system/o',
+            'system/o.1',
+            ])
         removed_list = tarball.extractfile("removed")
         self.assertEqual(removed_list.read().decode("utf-8"), u"""b
 c/d
+c/h
 dir
 system/中文中文中文
 """)
+
+
+class TestHardLinkTargetIsModified(unittest.TestCase):
+    def setUp(self):
+        self.temp_directory = tempfile.mkdtemp()
+        self.addCleanup(shutil.rmtree, self.temp_directory)
+
+    def _make_tarballs(self, order):
+        source_tarball_path = os.path.join(self.temp_directory, "source.tar")
+        target_tarball_path = os.path.join(self.temp_directory, "target.tar")
+
+        # Use an ExitStack() when we drop Python 2.7 compatibility.
+        source_tarball = tarfile.open(
+            source_tarball_path, "w", encoding="utf-8")
+        target_tarball = tarfile.open(
+            target_tarball_path, "w", encoding="utf-8")
+
+        if order == "a->b":
+            # Add a regular file to the source.
+            a_source = tarfile.TarInfo()
+            a_source.name = "a"
+            a_source.size = 4
+            source_tarball.addfile(a_source, BytesIO(b"XXXX"))
+
+            # Add a hardlink to this file.
+            b = tarfile.TarInfo()
+            b.name = "b"
+            b.type = tarfile.LNKTYPE
+            b.linkname = "a"
+            source_tarball.addfile(b)
+
+            # Change the content of link's target, i.e. the "a" file in the
+            # target tarball, but keep the hardlink pointing at it.
+            a_target = tarfile.TarInfo()
+            a_target.name = "a"
+            a_target.size = 5
+
+            target_tarball.addfile(a_target, BytesIO(b"YYYYY"))
+            target_tarball.addfile(b)
+        else:
+            assert order == "b->a", "Bad order: {}".format(order)
+            # Add a regular file to the source.
+            a_source = tarfile.TarInfo()
+            a_source.name = "a"
+            a_source.size = 4
+            source_tarball.addfile(a_source, BytesIO(b"XXXX"))
+
+            # Add a hardlink to this file.
+            b_source = tarfile.TarInfo()
+            b_source.name = "b"
+            b_source.type = tarfile.LNKTYPE
+            b_source.linkname = "a"
+            source_tarball.addfile(b_source)
+
+            # Swap things around in the target such that 'b' is the regular
+            # file and 'a' is the hardlink to b.
+            b_target = tarfile.TarInfo()
+            b_target.name = "b"
+            b_target.size = 5
+            target_tarball.addfile(b_target, BytesIO(b"YYYYY"))
+
+            a_target = tarfile.TarInfo()
+            a_target.name = "a"
+            a_target.type = tarfile.LNKTYPE
+            a_target.linkname = "b"
+            target_tarball.addfile(a_target)
+
+        source_tarball.close()
+        target_tarball.close()
+
+        return source_tarball_path, target_tarball_path
+
+    def test_link_count_2_order_ab(self):
+        # LP: #1444347 - a file with link count 2 (i.e. two hardlinks to the
+        # same inode) doesn't get both sources updated.
+        diff = ImageDiff(*self._make_tarballs("a->b"))
+        change_set = diff.compare_images()
+        self.assertEqual(change_set, {("a", "mod"), ("b", "mod")})
+
+    def test_unpack_ab(self):
+        # Ensure that the unpacked target tarball has a correct hardlink.
+        source_path, target_path = self._make_tarballs("a->b")
+        diff = ImageDiff(source_path, target_path)
+        diff_path = os.path.join(self.temp_directory, "diff.tar")
+        diff.generate_diff_tarball(diff_path)
+        # Unpack the source, then unpack the target over that.
+        unpack_path = os.path.join(self.temp_directory, "unpack")
+        os.mkdir(unpack_path)
+        with tarfile.open(source_path, "r:", encoding="utf-8") as tf:
+            tf.extractall(unpack_path)
+        # Before applying the diff, "b" contains the old "a" file's contents.
+        with open(os.path.join(unpack_path, "b"), "rb") as fp:
+            contents = fp.read()
+        self.assertEqual(contents, b"XXXX")
+        # Unpack the diff, which changes both the contents of 'a' and the
+        # hardlink 'b'.
+        with tarfile.open(diff_path, "r:", encoding="utf-8") as tf:
+            # Process any file removals first.
+            removed_list = tf.extractfile("removed")
+            for line in removed_list:
+                os.unlink(os.path.join(unpack_path,
+                                       line.decode("utf-8").rstrip()))
+            tf.extractall(unpack_path)
+        with open(os.path.join(unpack_path, "b"), "rb") as fp:
+            contents = fp.read()
+        self.assertEqual(contents, b"YYYYY")
+
+    def test_link_count_2_swap_roles(self):
+        # Like above but the source has regular file 'a' with hardlink 'b'
+        # pointing to it, while the target has regular file 'b' with the
+        # hardlink 'a' pointing to it.  Both must be properly updated.
+        diff = ImageDiff(*self._make_tarballs("b->a"))
+        change_set = diff.compare_images()
+        self.assertEqual(change_set, {("a", "mod"), ("b", "mod")})
+
+    def test_unpack_ab_swap_roles(self):
+        # Ensure that the unpacked target tarball has a correct hardlink.
+        source_path, target_path = self._make_tarballs("b->a")
+        diff = ImageDiff(source_path, target_path)
+        diff_path = os.path.join(self.temp_directory, "diff.tar")
+        diff.generate_diff_tarball(diff_path)
+        # Unpack the source, then unpack the target over that.
+        unpack_path = os.path.join(self.temp_directory, "unpack")
+        os.mkdir(unpack_path)
+        with tarfile.open(source_path, "r:", encoding="utf-8") as tf:
+            tf.extractall(unpack_path)
+        # Before applying the diff, "b" contains the old "a" file's contents.
+        with open(os.path.join(unpack_path, "b"), "rb") as fp:
+            contents = fp.read()
+        self.assertEqual(contents, b"XXXX")
+        # Unpack the diff, which changes both the contents of 'a' and the
+        # hardlink 'b'.
+        with tarfile.open(diff_path, "r:", encoding="utf-8") as tf:
+            # Process any file removals first.
+            removed_list = tf.extractfile("removed")
+            for line in removed_list:
+                os.unlink(os.path.join(unpack_path,
+                                       line.decode("utf-8").rstrip()))
+            tf.extractall(unpack_path)
+        with open(os.path.join(unpack_path, "b"), "rb") as fp:
+            contents = fp.read()
+        self.assertEqual(contents, b"YYYYY")