mic/utils/Fiemap.py

   1 """ This module implements python API for the FIEMAP ioctl. The FIEMAP ioctl
   2 allows to find holes and mapped areas in a file. """
   3
   4 # Note, a lot of code in this module is not very readable, because it deals
   5 # with the rather complex FIEMAP ioctl. To understand the code, you need to
   6 # know the FIEMAP interface, which is documented in the
   7 # Documentation/filesystems/fiemap.txt file in the Linux kernel sources.
   8
   9 # Disable the following pylint recommendations:
  10 #   * Too many instance attributes (R0902)
  11 # pylint: disable=R0902
  12
  13 import os
  14 import struct
  15 import array
  16 import fcntl
  17 from mic.utils.misc import get_block_size
  18
  19 # Format string for 'struct fiemap'
  20 _FIEMAP_FORMAT = "=QQLLLL"
  21 # sizeof(struct fiemap)
  22 _FIEMAP_SIZE = struct.calcsize(_FIEMAP_FORMAT)
  23 # Format string for 'struct fiemap_extent'
  24 _FIEMAP_EXTENT_FORMAT = "=QQQQQLLLL"
  25 # sizeof(struct fiemap_extent)
  26 _FIEMAP_EXTENT_SIZE = struct.calcsize(_FIEMAP_EXTENT_FORMAT)
  27 # The FIEMAP ioctl number
  28 _FIEMAP_IOCTL = 0xC020660B
  29
  30 # Minimum buffer which is required for 'class Fiemap' to operate
  31 MIN_BUFFER_SIZE = _FIEMAP_SIZE + _FIEMAP_EXTENT_SIZE
  32 # The default buffer size for 'class Fiemap'
  33 DEFAULT_BUFFER_SIZE = 256 * 1024
  34
  35 class Error(Exception):
  36     """ A class for exceptions generated by this module. We currently support
  37     only one type of exceptions, and we basically throw human-readable problem
  38     description in case of errors. """
  39     pass
  40
  41 class Fiemap:
  42     """ This class provides API to the FIEMAP ioctl. Namely, it allows to
  43     iterate over all mapped blocks and over all holes. """
  44
  45     def _open_image_file(self):
  46         """ Open the image file. """
  47
  48         try:
  49             self._f_image = open(self._image_path, 'rb')
  50         except IOError as err:
  51             raise Error("cannot open image file '%s': %s" \
  52                         % (self._image_path, err))
  53
  54         self._f_image_needs_close = True
  55
  56     def __init__(self, image, buf_size = DEFAULT_BUFFER_SIZE):
  57         """ Initialize a class instance. The 'image' argument is full path to
  58         the file to operate on, or a file object to operate on.
  59
  60         The 'buf_size' argument is the size of the buffer for 'struct
  61         fiemap_extent' elements which will be used when invoking the FIEMAP
  62         ioctl. The larger is the buffer, the less times the FIEMAP ioctl will
  63         be invoked. """
  64
  65         self._f_image_needs_close = False
  66
  67         if hasattr(image, "fileno"):
  68             self._f_image = image
  69             self._image_path = image.name
  70         else:
  71             self._image_path = image
  72             self._open_image_file()
  73
  74         # Validate 'buf_size'
  75         if buf_size < MIN_BUFFER_SIZE:
  76             raise Error("too small buffer (%d bytes), minimum is %d bytes" \
  77                     % (buf_size, MIN_BUFFER_SIZE))
  78
  79         # How many 'struct fiemap_extent' elements fit the buffer
  80         buf_size -= _FIEMAP_SIZE
  81         self._fiemap_extent_cnt = buf_size / _FIEMAP_EXTENT_SIZE
  82         self._buf_size = self._fiemap_extent_cnt * _FIEMAP_EXTENT_SIZE
  83         self._buf_size += _FIEMAP_SIZE
  84
  85         # Allocate a mutable buffer for the FIEMAP ioctl
  86         self._buf = array.array('B', [0] * self._buf_size)
  87
  88         self.image_size = os.fstat(self._f_image.fileno()).st_size
  89
  90         try:
  91             self.block_size = get_block_size(self._f_image)
  92         except IOError as err:
  93             raise Error("cannot get block size for '%s': %s" \
  94                         % (self._image_path, err))
  95
  96         self.blocks_cnt = self.image_size + self.block_size - 1
  97         self.blocks_cnt /= self.block_size
  98
  99         # Synchronize the image file to make sure FIEMAP returns correct values
 100         try:
 101             self._f_image.flush()
 102         except IOError as err:
 103             raise Error("cannot flush image file '%s': %s" \
 104                         % (self._image_path, err))
 105         try:
 106             os.fsync(self._f_image.fileno()),
 107         except OSError as err:
 108             raise Error("cannot synchronize image file '%s': %s " \
 109                         % (self._image_path, err.strerror))
 110
 111         # Check if the FIEMAP ioctl is supported
 112         self.block_is_mapped(0)
 113
 114     def __del__(self):
 115         """ The class destructor which closes the opened files. """
 116
 117         if self._f_image_needs_close:
 118             self._f_image.close()
 119
 120     def _invoke_fiemap(self, block, count):
 121         """ Invoke the FIEMAP ioctl for 'count' blocks of the file starting from
 122         block number 'block'.
 123
 124         The full result of the operation is stored in 'self._buf' on exit.
 125         Returns the unpacked 'struct fiemap' data structure in form of a python
 126         list (just like 'struct.upack()'). """
 127
 128         if block < 0 or block >= self.blocks_cnt:
 129             raise Error("bad block number %d, should be within [0, %d]" \
 130                         % (block, self.blocks_cnt))
 131
 132         # Initialize the 'struct fiemap' part of the buffer
 133         struct.pack_into(_FIEMAP_FORMAT, self._buf, 0, block * self.block_size,
 134                          count * self.block_size, 0, 0,
 135                          self._fiemap_extent_cnt, 0)
 136
 137         try:
 138             fcntl.ioctl(self._f_image, _FIEMAP_IOCTL, self._buf, 1)
 139         except IOError as err:
 140             error_msg = "the FIEMAP ioctl failed for '%s': %s" \
 141                         % (self._image_path, err)
 142             if err.errno == os.errno.EPERM or err.errno == os.errno.EACCES:
 143                 # The FIEMAP ioctl was added in kernel version 2.6.28 in 2008
 144                 error_msg += " (looks like your kernel does not support FIEMAP)"
 145
 146             raise Error(error_msg)
 147
 148         return struct.unpack(_FIEMAP_FORMAT, self._buf[:_FIEMAP_SIZE])
 149
 150     def block_is_mapped(self, block):
 151         """ This function returns 'True' if block number 'block' of the image
 152         file is mapped and 'False' otherwise. """
 153
 154         struct_fiemap = self._invoke_fiemap(block, 1)
 155
 156         # The 3rd element of 'struct_fiemap' is the 'fm_mapped_extents' field.
 157         # If it contains zero, the block is not mapped, otherwise it is
 158         # mapped.
 159         return bool(struct_fiemap[3])
 160
 161     def block_is_unmapped(self, block):
 162         """ This function returns 'True' if block number 'block' of the image
 163         file is not mapped (hole) and 'False' otherwise. """
 164
 165         return not self.block_is_mapped(block)
 166
 167     def _unpack_fiemap_extent(self, index):
 168         """ Unpack a 'struct fiemap_extent' structure object number 'index'
 169         from the internal 'self._buf' buffer. """
 170
 171         offset = _FIEMAP_SIZE + _FIEMAP_EXTENT_SIZE * index
 172         return struct.unpack(_FIEMAP_EXTENT_FORMAT,
 173                              self._buf[offset : offset + _FIEMAP_EXTENT_SIZE])
 174
 175     def _do_get_mapped_ranges(self, start, count):
 176         """ Implements most the functionality for the  'get_mapped_ranges()'
 177         generator: invokes the FIEMAP ioctl, walks through the mapped
 178         extents and yields mapped block ranges. However, the ranges may be
 179         consecutive (e.g., (1, 100), (100, 200)) and 'get_mapped_ranges()'
 180         simply merges them. """
 181
 182         block = start
 183         while block < start + count:
 184             struct_fiemap = self._invoke_fiemap(block, count)
 185
 186             mapped_extents = struct_fiemap[3]
 187             if mapped_extents == 0:
 188                 # No more mapped blocks
 189                 return
 190
 191             extent = 0
 192             while extent < mapped_extents:
 193                 fiemap_extent = self._unpack_fiemap_extent(extent)
 194
 195                 # Start of the extent
 196                 extent_start = fiemap_extent[0]
 197                 # Starting block number of the extent
 198                 extent_block = extent_start / self.block_size
 199                 # Length of the extent
 200                 extent_len = fiemap_extent[2]
 201                 # Count of blocks in the extent
 202                 extent_count = extent_len / self.block_size
 203
 204                 # Extent length and offset have to be block-aligned
 205                 assert extent_start % self.block_size == 0
 206                 assert extent_len % self.block_size == 0
 207
 208                 if extent_block > start + count - 1:
 209                     return
 210
 211                 first = max(extent_block, block)
 212                 last = min(extent_block + extent_count, start + count) - 1
 213                 yield (first, last)
 214
 215                 extent += 1
 216
 217             block = extent_block + extent_count
 218
 219     def get_mapped_ranges(self, start, count):
 220         """ A generator which yields ranges of mapped blocks in the file. The
 221         ranges are tuples of 2 elements: [first, last], where 'first' is the
 222         first mapped block and 'last' is the last mapped block.
 223
 224         The ranges are yielded for the area of the file of size 'count' blocks,
 225         starting from block 'start'. """
 226
 227         iterator = self._do_get_mapped_ranges(start, count)
 228
 229         first_prev, last_prev = iterator.next()
 230
 231         for first, last in iterator:
 232             if last_prev == first - 1:
 233                 last_prev = last
 234             else:
 235                 yield (first_prev, last_prev)
 236                 first_prev, last_prev = first, last
 237
 238         yield (first_prev, last_prev)
 239
 240     def get_unmapped_ranges(self, start, count):
 241         """ Just like 'get_mapped_ranges()', but yields unmapped block ranges
 242         instead (holes). """
 243
 244         hole_first = start
 245         for first, last in self._do_get_mapped_ranges(start, count):
 246             if first > hole_first:
 247                 yield (hole_first, first - 1)
 248
 249             hole_first = last + 1
 250
 251         if hole_first < start + count:
 252             yield (hole_first, start + count - 1)