Write only image diff to reduce flash memory wear

[joelpurra]

Instead of bmaptool copy writing every block of the (sparse/block-mapped) image onto the SD card/USB stick each time, would it not be an improvement to only flash/write the differing blocks?

My use-case is iteratively working on developing system images (embedded systems, headless servers, desktop systems) where changes often are small (bytes/kilobytes/megabytes) and entire partitions may be left untouched. Sparse images and bmaptool helps, but all image data is still repeatedly written even if there was no change. Writing only the diff would reduce writes by hundreds of megabytes each iteration.

• Could perform an "offline" binary image-to-image file diff as a preparation step before writing to the SD card, and only write mismatching blocks. This assumes that the previous image perfectly matches the SD card contents, which would require that the SD card is used in a completely immutable manor.
• Could perform an "online" block-by-block diff, by reading (batches) from the SD card before deciding what to write. This assumes that the additional reads are long-term "healthier" than writes in terms of SD card wear. The end result is that the SD card contents matches the image file, apart from the sparse holes which would be skipped anyhow. This approach also supports interchangeably using multiple SD cards.

Perhaps writing diffs could be implemented as an argument: bmaptool copy --diff=online.

---

I don't claim to understand the inner workings of flash memory, but it seems to me that reads are relatively cheap and that reducing writes should generally be beneficial.

• https://en.wikipedia.org/wiki/Flash_memory
• https://en.wikipedia.org/wiki/Write_amplification
• https://en.wikipedia.org/wiki/Wear_leveling
• https://en.wikipedia.org/wiki/SD_card

---

It would be nice to estimate how effective (in blocks, percent, bytes) a diff write could be. Any tool suggestions for counting the number of differing blocks between image files and/or block devices?

A diff between two image files using diffoscope looks quite promising, although it's on a file (system) level instead of block level.

Details

# NOTE: terminal output.
sudo diffoscope aaa.img bbb.img

# NOTE: split html file output.
sudo diffoscope --html-dir='html' aaa.img bbb.img

Unfortunately false "file rename"-looking mismatches clutter the file list diff, making it harder to spot metadata differences.

[josch]

Hi, I am creating bootable SD-card images for the MNT Reform open hardware laptop and am also interested in this. The image itself is 10.5 GiB large, with 5.3 GiB or 50.4% of actual data on it so using standard bmaptool helps a lot with flashing these disk images, cutting the time it takes in half. Flashing the image normally on one of my SD-cards takes:

bmaptool: info: copying time: 6m 0.1s, copying speed 15.0 MiB/sec

My first POC reads in full block ranges from the target device and if the checksum is the same, then it does not copy that range. So using bmaptool again right after flashing an image with the same options will mean that no bytes get written to the SD-card and since reading speed is usually greater than writing speed we get:

bmaptool: info: copying time: 4m 2.6s, copying speed 22.3 MiB/sec

That's nice! But what happens if we now start using the image? I booted the system and shut it down without changing any files myself. Of course files and their metadata are getting changed during the boot process. But does this really effect all block ranges from the bmap file? Turns out, most of the block ranges referenced by my bmap file got changed by this. Only 24.0 KiB were not copied. This means we get the worse from both worlds because now the read time and the write time is added together:

bmaptool: info: copying time: 11m 23.8s, copying speed 7.9 MiB/sec

Just doing a mount and fsck on the partitions left more things intact and I got:

bmaptool: info: Avoided writing 1.2 GiB of 5.3 GiB (22.4%) which were already present on the target
bmaptool: info: copying time: 8m 43.2s, copying speed 10.4 MiB/sec

Here is the diff of my POC patch using the approach of checking the checksum of full block ranges:

diff --git a/src/bmaptool/BmapCopy.py b/src/bmaptool/BmapCopy.py
index f8f0a2f..d86762b 100644
--- a/src/bmaptool/BmapCopy.py
+++ b/src/bmaptool/BmapCopy.py
@@ -624,6 +624,34 @@ class BmapCopy(object):
         _log.debug("the reader thread has started")
         try:
             for first, last, chksum in self._get_block_ranges():
+                # If requested, first read in the current block range from the
+                # destination fd -- if the checksum matches, we can skip
+                # writing it out.
+                if chksum and True:
+                    hash_obj = hashlib.new(self._cs_type)
+                    iterator = self._get_batches(first, last)
+
+                    sizes = []
+                    for start, end, length in iterator:
+                        self._f_dest.seek(start * self.block_size)
+                        try:
+                            buf = self._f_dest.read(length * self.block_size)
+                        except IOError as err:
+                            raise Error(
+                                "error while reading blocks %d-%d of %s: %s"
+                                % (start, end, self._dest_path, err)
+                            )
+                        hash_obj.update(buf)
+                        sizes.append((end - start + 1, len(buf)))
+
+                    if hash_obj.hexdigest() == chksum:
+                        # the target device already contains the correct data
+                        # nothing to do for this block range
+                        for cur_blocks, cur_bytes in sizes:
+                            self._batch_queue.put(("null", cur_blocks, cur_bytes))
+
+                        continue
+
                 if verify and chksum:
                     hash_obj = hashlib.new(self._cs_type)
 
@@ -689,6 +717,7 @@ class BmapCopy(object):
         blocks_written = 0
         bytes_written = 0
         fsync_last = 0
+        bytes_not_written = 0
 
         self._progress_started = False
         self._progress_index = 0
@@ -714,31 +743,37 @@ class BmapCopy(object):
                 # exception.
                 exc_info = batch[1]
                 raise exc_info[1]
+            elif batch[0] == "range":
+                (start, end, buf) = batch[1:4]
 
-            (start, end, buf) = batch[1:4]
+                assert len(buf) <= (end - start + 1) * self.block_size
+                assert len(buf) > (end - start) * self.block_size
 
-            assert len(buf) <= (end - start + 1) * self.block_size
-            assert len(buf) > (end - start) * self.block_size
+                self._f_dest.seek(start * self.block_size)
 
-            self._f_dest.seek(start * self.block_size)
+                # Synchronize the destination file if we reached the watermark
+                if self._dest_fsync_watermark:
+                    if blocks_written >= fsync_last + self._dest_fsync_watermark:
+                        fsync_last = blocks_written
+                        self.sync()
 
-            # Synchronize the destination file if we reached the watermark
-            if self._dest_fsync_watermark:
-                if blocks_written >= fsync_last + self._dest_fsync_watermark:
-                    fsync_last = blocks_written
-                    self.sync()
+                try:
+                    self._f_dest.write(buf)
+                except IOError as err:
+                    raise Error(
+                        "error while writing blocks %d-%d of '%s': %s"
+                        % (start, end, self._dest_path, err)
+                    )
 
-            try:
-                self._f_dest.write(buf)
-            except IOError as err:
-                raise Error(
-                    "error while writing blocks %d-%d of '%s': %s"
-                    % (start, end, self._dest_path, err)
-                )
+                cur_blocks = end - start + 1
+                cur_bytes = len(buf)
+            elif batch[0] == "null":
+                cur_blocks, cur_bytes = batch[1:3]
+                bytes_not_written += cur_bytes
 
             self._batch_queue.task_done()
-            blocks_written += end - start + 1
-            bytes_written += len(buf)
+            blocks_written += cur_blocks
+            bytes_written += cur_bytes
 
             self._update_progress(blocks_written)
 
@@ -777,6 +812,16 @@ class BmapCopy(object):
         if sync:
             self.sync()
 
+        if bytes_not_written > 0:
+            _log.info(
+                "Avoided writing %s of %s (%.01f%%) which were already present on the target"
+                % (
+                    human_size(bytes_not_written),
+                    human_size(bytes_written),
+                    bytes_not_written * 100 / bytes_written,
+                )
+            )
+
     def sync(self):
         """
         Synchronize the destination file to make sure all the data are actually
diff --git a/src/bmaptool/CLI.py b/src/bmaptool/CLI.py
index 40acf31..2ea3c48 100644
--- a/src/bmaptool/CLI.py
+++ b/src/bmaptool/CLI.py
@@ -119,13 +119,13 @@ def open_block_device(path):
     """
 
     try:
-        descriptor = os.open(path, os.O_WRONLY | os.O_EXCL)
+        descriptor = os.open(path, os.O_RDWR | os.O_EXCL)
     except OSError as err:
         error_out("cannot open block device '%s' in exclusive mode: %s", path, err)
 
     # Turn the block device file descriptor into a file object
     try:
-        file_obj = os.fdopen(descriptor, "wb")
+        file_obj = os.fdopen(descriptor, "r+b")
     except OSError as err:
         os.close(descriptor)
         error_out("cannot open block device '%s':\n%s", path, err)

So instead of computing the checksum of full block ranges and comparing them to the one stored in the bmap file, lets read individual blocks just before they would be written and compare them with the buffer content that is supposed to be written to the target device and avoid the write if they are equal. Checking each block instead of block-ranges gives much better results. For example, flashing an image and then doing a mount and a fsck and then flashing the same image again gives us:

bmaptool: info: Avoided writing 5.3 GiB of 5.3 GiB (100.0%) which were already present on the target
bmaptool: info: copying time: 4m 46.9s, copying speed 18.9 MiB/sec

Notice though that even though nearly 100% of the data was equivalent (there are some rounding errors which only become apparent when looking at the raw byte values instead of converting them into human-readable strings), the copying speed is only 85% of using the block-range approach. My CPU might be the bottleneck here as comparing Python strings is much more computationally intensive than computing checksums. Lets do another comparison. Here is copying an image after changing nothing:

bmaptool: info: Avoided writing 5.3 GiB of 5.3 GiB (100.0%) which were already present on the target
bmaptool: info: copying time: 4m 27.2s, copying speed 20.3 MiB/sec

Indeed it is slower than with the block-range based approach. Now lets boot up the image (the test where no block range was identical) and then write the image again:

bmaptool: info: Avoided writing 5.0 GiB of 5.3 GiB (95.4%) which were already present on the target
bmaptool: info: copying time: 4m 31.7s, copying speed 19.9 MiB/sec

I think we can conclude that the per-block reading and comparing beats the (I think more elegant) checksum comparison. The result is a bit slower but I think the main motivation of this feature is not to increase speed (even though that's a nice byproduct) but to reduce wear on the SD-card for blocks which already contain the same bytes which are about to be written. My second POC patch is this:

diff --git a/src/bmaptool/BmapCopy.py b/src/bmaptool/BmapCopy.py
index f8f0a2f..19cbf72 100644
--- a/src/bmaptool/BmapCopy.py
+++ b/src/bmaptool/BmapCopy.py
@@ -689,6 +689,7 @@ class BmapCopy(object):
         blocks_written = 0
         bytes_written = 0
         fsync_last = 0
+        bytes_not_written = 0
 
         self._progress_started = False
         self._progress_index = 0
@@ -729,7 +730,12 @@ class BmapCopy(object):
                     self.sync()
 
             try:
-                self._f_dest.write(buf)
+                test = self._f_dest.read(len(buf))
+                self._f_dest.seek(start * self.block_size)
+                if buf == test:
+                    bytes_not_written += len(buf)
+                else:
+                    self._f_dest.write(buf)
             except IOError as err:
                 raise Error(
                     "error while writing blocks %d-%d of '%s': %s"
@@ -777,6 +783,16 @@ class BmapCopy(object):
         if sync:
             self.sync()
 
+        if bytes_not_written > 0:
+            _log.info(
+                "Avoided writing %s of %s (%.01f%%) which were already present on the target"
+                % (
+                    human_size(bytes_not_written),
+                    human_size(bytes_written),
+                    bytes_not_written * 100 / bytes_written,
+                )
+            )
+
     def sync(self):
         """
         Synchronize the destination file to make sure all the data are actually
diff --git a/src/bmaptool/CLI.py b/src/bmaptool/CLI.py
index 40acf31..2ea3c48 100644
--- a/src/bmaptool/CLI.py
+++ b/src/bmaptool/CLI.py
@@ -119,13 +119,13 @@ def open_block_device(path):
     """
 
     try:
-        descriptor = os.open(path, os.O_WRONLY | os.O_EXCL)
+        descriptor = os.open(path, os.O_RDWR | os.O_EXCL)
     except OSError as err:
         error_out("cannot open block device '%s' in exclusive mode: %s", path, err)
 
     # Turn the block device file descriptor into a file object
     try:
-        file_obj = os.fdopen(descriptor, "wb")
+        file_obj = os.fdopen(descriptor, "r+b")
     except OSError as err:
         os.close(descriptor)
         error_out("cannot open block device '%s':\n%s", path, err)

I prefer the second one also because it is far less invasive compared to the first.

Does anybody have a good idea for how to name the command line flag for this feature? Maybe something like:

• --read-before-write
• --compare-before-write
• --write-what-you-need
• --avoid-useless-writes

Ideas? 😄