raw: use bmap creation code from bmap-tools

This patch copies the bmap creation code from the bmap-tools project to mic.
Hopefully, at some point we can just make mic package depend on bmap-tools and
directly invoke bmap creation functions from bmap-tools. However, mid
maintainers have issues with this at this point, so we just copy the code.

Unlike the old mic implementation which uses FIBMAP ioctl, bmap-tools use the
FIEMAP ioctl, which is better and also works on btrfs.

Change-Id: I8807ac32d3fcb31e9d410250348318fd04a63275
Signed-off-by: Artem Bityutskiy <artem.bityutskiy@intel.com>

3 files changed, 559 insertions, 128 deletions

diff --git a/mic/imager/raw.py b/mic/imager/raw.py
index 19efe0d..8535d66 100644
--- a/mic/imager/raw.py
+++ b/mic/imager/raw.py
@@ -18,9 +18,6 @@
 import os
 import stat
 import shutil
-from fcntl import ioctl
-from struct import pack, unpack
-from itertools import groupby
 
 from mic import kickstart, msger
 from mic.utils import fs_related, runner, misc
@@ -451,98 +448,8 @@ class RawImageCreator(BaseImageCreator):
         cfg.write(xml)
         cfg.close()
 
-    def _bmap_file_start(self, block_size, image_size, blocks_cnt):
-        """ A helper function which generates the starting contents of the
-        block map file: the header comment, image size, block size, etc. """
-
-        xml = "<?xml version=\"1.0\" ?>\n\n"
-        xml += "<!-- This file contains block map for an image file. The block map\n"
-        xml += "     is basically a list of block numbers in the image file. It lists\n"
-        xml += "     only those blocks which contain data (boot sector, partition\n"
-        xml += "     table, file-system metadata, files, directories, extents, etc).\n"
-        xml += "     These blocks have to be copied to the target device. The other\n"
-        xml += "     blocks do not contain any useful data and do not have to be\n"
-        xml += "     copied to the target device. Thus, using the block map users can\n"
-        xml += "     flash the image fast. So the block map is just an optimization.\n"
-        xml += "     It is OK to ignore this file and just flash the entire image to\n"
-        xml += "     the target device if the flashing speed is not important.\n\n"
-
-        xml += "     Note, this file contains commentaries with useful information\n"
-        xml += "     like image size in gigabytes, percentage of mapped data, etc.\n"
-        xml += "     This data is there merely to make the XML file human-readable.\n\n"
-
-        xml += "     The 'version' attribute is the block map file format version in\n"
-        xml += "     the 'major.minor' format. The version major number is increased\n"
-        xml += "     whenever we make incompatible changes to the block map format,\n"
-        xml += "     meaning that the bmap-aware flasher would have to be modified in\n"
-        xml += "     order to support the new format. The minor version is increased\n"
-        xml += "     in case of compatible changes. For example, if we add an attribute\n"
-        xml += "     which is optional for the bmap-aware flasher. -->\n"
-        xml += "<bmap version=\"1.1\">\n"
-        xml += "\t<!-- Image size in bytes (%s) -->\n" \
-                % misc.human_size(image_size)
-        xml += "\t<ImageSize> %u </ImageSize>\n\n" % image_size
-
-        xml += "\t<!-- Size of a block in bytes -->\n"
-        xml += "\t<BlockSize> %u </BlockSize>\n\n" % block_size
-
-        xml += "\t<!-- Count of blocks in the image file -->\n"
-        xml += "\t<BlocksCount> %u </BlocksCount>\n\n" % blocks_cnt
-
-        xml += "\t<!-- The block map which consists of elements which may either\n"
-        xml += "\t     be a range of blocks or a single block. The 'sha1' attribute\n"
-        xml += "\t     is the SHA1 checksum of the this range of blocks. -->\n"
-        xml += "\t<BlockMap>\n"
-
-        return xml
-
-    def _bmap_file_end(self, mapped_cnt, block_size, blocks_cnt):
-        """ A helper funstion which generates the final parts of the block map
-        file: the ending tags and the information about the amount of mapped
-        blocks. """
-
-        xml = "\t</BlockMap>\n\n"
-
-        size = misc.human_size(mapped_cnt * block_size)
-        percent = (mapped_cnt * 100.0) / blocks_cnt
-        xml += "\t<!-- Count of mapped blocks (%s or %.1f%% mapped) -->\n" \
-                % (size, percent)
-        xml += "\t<MappedBlocksCount> %u </MappedBlocksCount>\n" % mapped_cnt
-        xml += "</bmap>"
-
-        return xml
-
-    def _get_ranges(self, f_image, blocks_cnt):
-        """ A helper for 'generate_bmap()' which generates ranges of mapped
-        blocks. It uses the FIBMAP ioctl to check which blocks are mapped. Of
-        course, the image file must have been created as a sparse file
-        originally, otherwise all blocks will be mapped. And it is also
-        essential to generate the block map before the file had been copied
-        anywhere or compressed, because othewise we lose the information about
-        unmapped blocks. """
-
-        def is_mapped(block):
-            """ Returns True if block 'block' of the image file is mapped and
-            False otherwise.
-
-            Implementation details: this function uses the FIBMAP ioctl (number
-            1) to get detect whether 'block' is mapped to a disk block. The ioctl
-            returns zero if 'block' is not mapped and non-zero disk block number
-            if it is mapped. """
-
-            return unpack('I', ioctl(f_image, 1, pack('I', block)))[0] != 0
-
-        for key, group in groupby(xrange(blocks_cnt), is_mapped):
-            if key:
-                # Find the first and the last elements of the group
-                first = group.next()
-                last = first
-                for last in group:
-                    pass
-                yield first, last
-
     def generate_bmap(self):
-        """ Generate block map file for an image. The idea is that while disk
+        """ Generate block map file for the image. The idea is that while disk
         images we generate may be large (e.g., 4GiB), they may actually contain
         only little real data, e.g., 512MiB. This data are files, directories,
         file-system meta-data, partition table, etc. In other words, when
@@ -552,14 +459,12 @@ class RawImageCreator(BaseImageCreator):
         This function generates the block map file for an arbitrary image that
         mic has generated. The block map file is basically an XML file which
         contains a list of blocks which have to be copied to the target device.
-        The other blocks are not used and there is no need to copy them.
-
-        This function assumes the image file was originally created as a sparse
-        file. To generate the block map we use the FIBMAP ioctl. """
+        The other blocks are not used and there is no need to copy them. """
 
         if self.bmap_needed is None:
             return
 
+        from mic.utils import BmapCreate
         msger.info("Generating the map file(s)")
 
         for name in self.__disks.keys():
@@ -568,33 +473,9 @@ class RawImageCreator(BaseImageCreator):
 
             msger.debug("Generating block map file '%s'" % bmap_file)
 
-            image_size = os.path.getsize(image)
-
-            with open(bmap_file, "w") as f_bmap:
-                with open(image, "rb") as f_image:
-                    # Get the block size of the host file-system for the image
-                    # file by calling the FIGETBSZ ioctl (number 2).
-                    block_size = unpack('I', ioctl(f_image, 2, pack('I', 0)))[0]
-                    blocks_cnt = (image_size + block_size - 1) / block_size
-
-                    # Write general information to the block map file, without
-                    # block map itself, which will be written next.
-                    xml = self._bmap_file_start(block_size, image_size,
-                                                blocks_cnt)
-                    f_bmap.write(xml)
-
-                    # Generate the block map and write it to the XML block map
-                    # file as we go.
-                    mapped_cnt = 0
-                    for first, last in self._get_ranges(f_image, blocks_cnt):
-                        mapped_cnt += last - first + 1
-                        sha1 = misc.calc_hashes(image, ('sha1', ),
-                                                first * block_size,
-                                                (last + 1) * block_size)
-                        f_bmap.write("\t\t<Range sha1=\"%s\"> %s-%s " \
-                                     "</Range>\n" % (sha1[0], first, last))
-
-                    # Finish the block map file
-                    xml = self._bmap_file_end(mapped_cnt, block_size,
-                                              blocks_cnt)
-                    f_bmap.write(xml)
+            try:
+                creator = BmapCreate.BmapCreate(image, bmap_file)
+                creator.generate()
+                del creator
+            except BmapCreate.Error as err:
+                raise CreatorError("Failed to create bmap file: %s" % str(err))
diff --git a/mic/utils/BmapCreate.py b/mic/utils/BmapCreate.py
new file mode 100644
index 0000000..65b19a5
--- /dev/null
+++ b/mic/utils/BmapCreate.py
@@ -0,0 +1,298 @@
+""" This module implements the block map (bmap) creation functionality and
+provides the corresponding API in form of the 'BmapCreate' class.
+
+The idea is that while images files may generally be very large (e.g., 4GiB),
+they may nevertheless contain only little real data, e.g., 512MiB. This data
+are files, directories, file-system meta-data, partition table, etc. When
+copying the image to the target device, you do not have to copy all the 4GiB of
+data, you can copy only 512MiB of it, which is 4 times less, so copying should
+presumably be 4 times faster.
+
+The block map file is an XML file which contains a list of blocks which have to
+be copied to the target device. The other blocks are not used and there is no
+need to copy them. The XML file also contains some additional information like
+block size, image size, count of mapped blocks, etc. There are also many
+commentaries, so it is human-readable.
+
+The image has to be a sparse file. Generally, this means that when you generate
+this image file, you should start with a huge sparse file which contains a
+single hole spanning the entire file. Then you should partition it, write all
+the data (probably by means of loop-back mounting the image or parts of it),
+etc. The end result should be a sparse file where mapped areas represent useful
+parts of the image and holes represent useless parts of the image, which do not
+have to be copied when copying the image to the target device.
+
+This module uses the FIBMAP ioctl to detect holes. """
+
+# Disable the following pylint recommendations:
+#   *  Too many instance attributes - R0902
+#   *  Too few public methods - R0903
+# pylint: disable=R0902,R0903
+
+import hashlib
+from mic.utils.misc import human_size
+from mic.utils import Fiemap
+
+# The bmap format version we generate
+SUPPORTED_BMAP_VERSION = "1.3"
+
+_BMAP_START_TEMPLATE = \
+"""<?xml version="1.0" ?>
+<!-- This file contains the block map for an image file, which is basically
+     a list of useful (mapped) block numbers in the image file. In other words,
+     it lists only those blocks which contain data (boot sector, partition
+     table, file-system metadata, files, directories, extents, etc). These
+     blocks have to be copied to the target device. The other blocks do not
+     contain any useful data and do not have to be copied to the target
+     device.
+
+     The block map an optimization which allows to copy or flash the image to
+     the image quicker than copying of flashing the entire image. This is
+     because with bmap less data is copied: <MappedBlocksCount> blocks instead
+     of <BlocksCount> blocks.
+
+     Besides the machine-readable data, this file contains useful commentaries
+     which contain human-readable information like image size, percentage of
+     mapped data, etc.
+
+     The 'version' attribute is the block map file format version in the
+     'major.minor' format. The version major number is increased whenever an
+     incompatible block map format change is made. The minor number changes
+     in case of minor backward-compatible changes. -->
+
+<bmap version="%s">
+    <!-- Image size in bytes: %s -->
+    <ImageSize> %u </ImageSize>
+
+    <!-- Size of a block in bytes -->
+    <BlockSize> %u </BlockSize>
+
+    <!-- Count of blocks in the image file -->
+    <BlocksCount> %u </BlocksCount>
+
+"""
+
+class Error(Exception):
+    """ A class for exceptions generated by this module. We currently support
+    only one type of exceptions, and we basically throw human-readable problem
+    description in case of errors. """
+    pass
+
+class BmapCreate:
+    """ This class implements the bmap creation functionality. To generate a
+    bmap for an image (which is supposedly a sparse file), you should first
+    create an instance of 'BmapCreate' and provide:
+
+    * full path or a file-like object of the image to create bmap for
+    * full path or a file object to use for writing the results to
+
+    Then you should invoke the 'generate()' method of this class. It will use
+    the FIEMAP ioctl to generate the bmap. """
+
+    def _open_image_file(self):
+        """ Open the image file. """
+
+        try:
+            self._f_image = open(self._image_path, 'rb')
+        except IOError as err:
+            raise Error("cannot open image file '%s': %s" \
+                        % (self._image_path, err))
+
+        self._f_image_needs_close = True
+
+    def _open_bmap_file(self):
+        """ Open the bmap file. """
+
+        try:
+            self._f_bmap = open(self._bmap_path, 'w+')
+        except IOError as err:
+            raise Error("cannot open bmap file '%s': %s" \
+                        % (self._bmap_path, err))
+
+        self._f_bmap_needs_close = True
+
+    def __init__(self, image, bmap):
+        """ Initialize a class instance:
+        * image - full path or a file-like object of the image to create bmap
+                  for
+        * bmap  - full path or a file object to use for writing the resulting
+                  bmap to """
+
+        self.image_size = None
+        self.image_size_human = None
+        self.block_size = None
+        self.blocks_cnt = None
+        self.mapped_cnt = None
+        self.mapped_size = None
+        self.mapped_size_human = None
+        self.mapped_percent = None
+
+        self._mapped_count_pos1 = None
+        self._mapped_count_pos2 = None
+        self._sha1_pos = None
+
+        self._f_image_needs_close = False
+        self._f_bmap_needs_close = False
+
+        if hasattr(image, "read"):
+            self._f_image = image
+            self._image_path = image.name
+        else:
+            self._image_path = image
+            self._open_image_file()
+
+        if hasattr(bmap, "read"):
+            self._f_bmap = bmap
+            self._bmap_path = bmap.name
+        else:
+            self._bmap_path = bmap
+            self._open_bmap_file()
+
+        self.fiemap = Fiemap.Fiemap(self._f_image)
+
+        self.image_size = self.fiemap.image_size
+        self.image_size_human = human_size(self.image_size)
+        if self.image_size == 0:
+            raise Error("cannot generate bmap for zero-sized image file '%s'" \
+                        % self._image_path)
+
+        self.block_size = self.fiemap.block_size
+        self.blocks_cnt = self.fiemap.blocks_cnt
+
+    def _bmap_file_start(self):
+        """ A helper function which generates the starting contents of the
+        block map file: the header comment, image size, block size, etc. """
+
+        # We do not know the amount of mapped blocks at the moment, so just put
+        # whitespaces instead of real numbers. Assume the longest possible
+        # numbers.
+        mapped_count = ' ' * len(str(self.image_size))
+        mapped_size_human = ' ' * len(self.image_size_human)
+
+        xml = _BMAP_START_TEMPLATE \
+               % (SUPPORTED_BMAP_VERSION, self.image_size_human,
+                  self.image_size, self.block_size, self.blocks_cnt)
+        xml += "    <!-- Count of mapped blocks: "
+
+        self._f_bmap.write(xml)
+        self._mapped_count_pos1 = self._f_bmap.tell()
+
+        # Just put white-spaces instead of real information about mapped blocks
+        xml  = "%s or %.1f    -->\n" % (mapped_size_human, 100.0)
+        xml += "    <MappedBlocksCount> "
+
+        self._f_bmap.write(xml)
+        self._mapped_count_pos2 = self._f_bmap.tell()
+
+        xml  = "%s </MappedBlocksCount>\n\n" % mapped_count
+
+        # pylint: disable=C0301
+        xml += "    <!-- The checksum of this bmap file. When it is calculated, the value of\n"
+        xml += "         the SHA1 checksum has be zeoro (40 ASCII \"0\" symbols). -->\n"
+        xml += "    <BmapFileSHA1> "
+
+        self._f_bmap.write(xml)
+        self._sha1_pos = self._f_bmap.tell()
+
+        xml = "0" * 40 + " </BmapFileSHA1>\n\n"
+        xml += "    <!-- The block map which consists of elements which may either be a\n"
+        xml += "         range of blocks or a single block. The 'sha1' attribute (if present)\n"
+        xml += "         is the SHA1 checksum of this blocks range. -->\n"
+        xml += "    <BlockMap>\n"
+        # pylint: enable=C0301
+
+        self._f_bmap.write(xml)
+
+    def _bmap_file_end(self):
+        """ A helper function which generates the final parts of the block map
+        file: the ending tags and the information about the amount of mapped
+        blocks. """
+
+        xml =  "    </BlockMap>\n"
+        xml += "</bmap>\n"
+
+        self._f_bmap.write(xml)
+
+        self._f_bmap.seek(self._mapped_count_pos1)
+        self._f_bmap.write("%s or %.1f%%" % \
+                           (self.mapped_size_human, self.mapped_percent))
+
+        self._f_bmap.seek(self._mapped_count_pos2)
+        self._f_bmap.write("%u" % self.mapped_cnt)
+
+        self._f_bmap.seek(0)
+        sha1 = hashlib.sha1(self._f_bmap.read()).hexdigest()
+        self._f_bmap.seek(self._sha1_pos)
+        self._f_bmap.write("%s" % sha1)
+
+    def _calculate_sha1(self, first, last):
+        """ A helper function which calculates SHA1 checksum for the range of
+        blocks of the image file: from block 'first' to block 'last'. """
+
+        start = first * self.block_size
+        end = (last + 1) * self.block_size
+
+        self._f_image.seek(start)
+        hash_obj = hashlib.new("sha1")
+
+        chunk_size = 1024*1024
+        to_read = end - start
+        read = 0
+
+        while read < to_read:
+            if read + chunk_size > to_read:
+                chunk_size = to_read - read
+            chunk = self._f_image.read(chunk_size)
+            hash_obj.update(chunk)
+            read += chunk_size
+
+        return hash_obj.hexdigest()
+
+    def generate(self, include_checksums = True):
+        """ Generate bmap for the image file. If 'include_checksums' is 'True',
+        also generate SHA1 checksums for block ranges. """
+
+        # Save image file position in order to restore it at the end
+        image_pos = self._f_image.tell()
+
+        self._bmap_file_start()
+
+        # Generate the block map and write it to the XML block map
+        # file as we go.
+        self.mapped_cnt = 0
+        for first, last in self.fiemap.get_mapped_ranges(0, self.blocks_cnt):
+            self.mapped_cnt += last - first + 1
+            if include_checksums:
+                sha1 = self._calculate_sha1(first, last)
+                sha1 = " sha1=\"%s\"" % sha1
+            else:
+                sha1 = ""
+
+            if first != last:
+                self._f_bmap.write("        <Range%s> %s-%s </Range>\n" \
+                                   % (sha1, first, last))
+            else:
+                self._f_bmap.write("        <Range%s> %s </Range>\n" \
+                                   % (sha1, first))
+
+        self.mapped_size = self.mapped_cnt * self.block_size
+        self.mapped_size_human = human_size(self.mapped_size)
+        self.mapped_percent = (self.mapped_cnt * 100.0) /  self.blocks_cnt
+
+        self._bmap_file_end()
+
+        try:
+            self._f_bmap.flush()
+        except IOError as err:
+            raise Error("cannot flush the bmap file '%s': %s" \
+                        % (self._bmap_path, err))
+
+        self._f_image.seek(image_pos)
+
+    def __del__(self):
+        """ The class destructor which closes the opened files. """
+
+        if self._f_image_needs_close:
+            self._f_image.close()
+        if self._f_bmap_needs_close:
+            self._f_bmap.close()
diff --git a/mic/utils/Fiemap.py b/mic/utils/Fiemap.py
new file mode 100644
index 0000000..f2db6ff
--- /dev/null
+++ b/mic/utils/Fiemap.py
@@ -0,0 +1,252 @@
+""" This module implements python API for the FIEMAP ioctl. The FIEMAP ioctl
+allows to find holes and mapped areas in a file. """
+
+# Note, a lot of code in this module is not very readable, because it deals
+# with the rather complex FIEMAP ioctl. To understand the code, you need to
+# know the FIEMAP interface, which is documented in the
+# Documentation/filesystems/fiemap.txt file in the Linux kernel sources.
+
+# Disable the following pylint recommendations:
+#   * Too many instance attributes (R0902)
+# pylint: disable=R0902
+
+import os
+import struct
+import array
+import fcntl
+from mic.utils.misc import get_block_size
+
+# Format string for 'struct fiemap'
+_FIEMAP_FORMAT = "=QQLLLL"
+# sizeof(struct fiemap)
+_FIEMAP_SIZE = struct.calcsize(_FIEMAP_FORMAT)
+# Format string for 'struct fiemap_extent'
+_FIEMAP_EXTENT_FORMAT = "=QQQQQLLLL"
+# sizeof(struct fiemap_extent)
+_FIEMAP_EXTENT_SIZE = struct.calcsize(_FIEMAP_EXTENT_FORMAT)
+# The FIEMAP ioctl number
+_FIEMAP_IOCTL = 0xC020660B
+
+# Minimum buffer which is required for 'class Fiemap' to operate
+MIN_BUFFER_SIZE = _FIEMAP_SIZE + _FIEMAP_EXTENT_SIZE
+# The default buffer size for 'class Fiemap'
+DEFAULT_BUFFER_SIZE = 256 * 1024
+
+class Error(Exception):
+    """ A class for exceptions generated by this module. We currently support
+    only one type of exceptions, and we basically throw human-readable problem
+    description in case of errors. """
+    pass
+
+class Fiemap:
+    """ This class provides API to the FIEMAP ioctl. Namely, it allows to
+    iterate over all mapped blocks and over all holes. """
+
+    def _open_image_file(self):
+        """ Open the image file. """
+
+        try:
+            self._f_image = open(self._image_path, 'rb')
+        except IOError as err:
+            raise Error("cannot open image file '%s': %s" \
+                        % (self._image_path, err))
+
+        self._f_image_needs_close = True
+
+    def __init__(self, image, buf_size = DEFAULT_BUFFER_SIZE):
+        """ Initialize a class instance. The 'image' argument is full path to
+        the file to operate on, or a file object to operate on.
+
+        The 'buf_size' argument is the size of the buffer for 'struct
+        fiemap_extent' elements which will be used when invoking the FIEMAP
+        ioctl. The larger is the buffer, the less times the FIEMAP ioctl will
+        be invoked. """
+
+        self._f_image_needs_close = False
+
+        if hasattr(image, "fileno"):
+            self._f_image = image
+            self._image_path = image.name
+        else:
+            self._image_path = image
+            self._open_image_file()
+
+        # Validate 'buf_size'
+        if buf_size < MIN_BUFFER_SIZE:
+            raise Error("too small buffer (%d bytes), minimum is %d bytes" \
+                    % (buf_size, MIN_BUFFER_SIZE))
+
+        # How many 'struct fiemap_extent' elements fit the buffer
+        buf_size -= _FIEMAP_SIZE
+        self._fiemap_extent_cnt = buf_size / _FIEMAP_EXTENT_SIZE
+        self._buf_size = self._fiemap_extent_cnt * _FIEMAP_EXTENT_SIZE
+        self._buf_size += _FIEMAP_SIZE
+
+        # Allocate a mutable buffer for the FIEMAP ioctl
+        self._buf = array.array('B', [0] * self._buf_size)
+
+        self.image_size = os.fstat(self._f_image.fileno()).st_size
+
+        try:
+            self.block_size = get_block_size(self._f_image)
+        except IOError as err:
+            raise Error("cannot get block size for '%s': %s" \
+                        % (self._image_path, err))
+
+        self.blocks_cnt = self.image_size + self.block_size - 1
+        self.blocks_cnt /= self.block_size
+
+        # Synchronize the image file to make sure FIEMAP returns correct values
+        try:
+            self._f_image.flush()
+        except IOError as err:
+            raise Error("cannot flush image file '%s': %s" \
+                        % (self._image_path, err))
+        try:
+            os.fsync(self._f_image.fileno()),
+        except OSError as err:
+            raise Error("cannot synchronize image file '%s': %s " \
+                        % (self._image_path, err.strerror))
+
+        # Check if the FIEMAP ioctl is supported
+        self.block_is_mapped(0)
+
+    def __del__(self):
+        """ The class destructor which closes the opened files. """
+
+        if self._f_image_needs_close:
+            self._f_image.close()
+
+    def _invoke_fiemap(self, block, count):
+        """ Invoke the FIEMAP ioctl for 'count' blocks of the file starting from
+        block number 'block'.
+
+        The full result of the operation is stored in 'self._buf' on exit.
+        Returns the unpacked 'struct fiemap' data structure in form of a python
+        list (just like 'struct.upack()'). """
+
+        if block < 0 or block >= self.blocks_cnt:
+            raise Error("bad block number %d, should be within [0, %d]" \
+                        % (block, self.blocks_cnt))
+
+        # Initialize the 'struct fiemap' part of the buffer
+        struct.pack_into(_FIEMAP_FORMAT, self._buf, 0, block * self.block_size,
+                         count * self.block_size, 0, 0,
+                         self._fiemap_extent_cnt, 0)
+
+        try:
+            fcntl.ioctl(self._f_image, _FIEMAP_IOCTL, self._buf, 1)
+        except IOError as err:
+            error_msg = "the FIEMAP ioctl failed for '%s': %s" \
+                        % (self._image_path, err)
+            if err.errno == os.errno.EPERM or err.errno == os.errno.EACCES:
+                # The FIEMAP ioctl was added in kernel version 2.6.28 in 2008
+                error_msg += " (looks like your kernel does not support FIEMAP)"
+
+            raise Error(error_msg)
+
+        return struct.unpack(_FIEMAP_FORMAT, self._buf[:_FIEMAP_SIZE])
+
+    def block_is_mapped(self, block):
+        """ This function returns 'True' if block number 'block' of the image
+        file is mapped and 'False' otherwise. """
+
+        struct_fiemap = self._invoke_fiemap(block, 1)
+
+        # The 3rd element of 'struct_fiemap' is the 'fm_mapped_extents' field.
+        # If it contains zero, the block is not mapped, otherwise it is
+        # mapped.
+        return bool(struct_fiemap[3])
+
+    def block_is_unmapped(self, block):
+        """ This function returns 'True' if block number 'block' of the image
+        file is not mapped (hole) and 'False' otherwise. """
+
+        return not self.block_is_mapped(block)
+
+    def _unpack_fiemap_extent(self, index):
+        """ Unpack a 'struct fiemap_extent' structure object number 'index'
+        from the internal 'self._buf' buffer. """
+
+        offset = _FIEMAP_SIZE + _FIEMAP_EXTENT_SIZE * index
+        return struct.unpack(_FIEMAP_EXTENT_FORMAT,
+                             self._buf[offset : offset + _FIEMAP_EXTENT_SIZE])
+
+    def _do_get_mapped_ranges(self, start, count):
+        """ Implements most the functionality for the  'get_mapped_ranges()'
+        generator: invokes the FIEMAP ioctl, walks through the mapped
+        extents and yields mapped block ranges. However, the ranges may be
+        consecutive (e.g., (1, 100), (100, 200)) and 'get_mapped_ranges()'
+        simply merges them. """
+
+        block = start
+        while block < start + count:
+            struct_fiemap = self._invoke_fiemap(block, count)
+
+            mapped_extents = struct_fiemap[3]
+            if mapped_extents == 0:
+                # No more mapped blocks
+                return
+
+            extent = 0
+            while extent < mapped_extents:
+                fiemap_extent = self._unpack_fiemap_extent(extent)
+
+                # Start of the extent
+                extent_start = fiemap_extent[0]
+                # Starting block number of the extent
+                extent_block = extent_start / self.block_size
+                # Length of the extent
+                extent_len = fiemap_extent[2]
+                # Count of blocks in the extent
+                extent_count = extent_len / self.block_size
+
+                # Extent length and offset have to be block-aligned
+                assert extent_start % self.block_size == 0
+                assert extent_len % self.block_size == 0
+
+                if extent_block > start + count - 1:
+                    return
+
+                first = max(extent_block, block)
+                last = min(extent_block + extent_count, start + count) - 1
+                yield (first, last)
+
+                extent += 1
+
+            block = extent_block + extent_count
+
+    def get_mapped_ranges(self, start, count):
+        """ A generator which yields ranges of mapped blocks in the file. The
+        ranges are tuples of 2 elements: [first, last], where 'first' is the
+        first mapped block and 'last' is the last mapped block.
+
+        The ranges are yielded for the area of the file of size 'count' blocks,
+        starting from block 'start'. """
+
+        iterator = self._do_get_mapped_ranges(start, count)
+
+        first_prev, last_prev = iterator.next()
+
+        for first, last in iterator:
+            if last_prev == first - 1:
+                last_prev = last
+            else:
+                yield (first_prev, last_prev)
+                first_prev, last_prev = first, last
+
+        yield (first_prev, last_prev)
+
+    def get_unmapped_ranges(self, start, count):
+        """ Just like 'get_mapped_ranges()', but yields unmapped block ranges
+        instead (holes). """
+
+        hole_first = start
+        for first, last in self._do_get_mapped_ranges(start, count):
+            if first > hole_first:
+                yield (hole_first, first - 1)
+
+            hole_first = last + 1
+
+        if hole_first < start + count:
+            yield (hole_first, start + count - 1)