image-fuzzer: Support L1/L2 tables in the qcow2 image generator

index 2c4f346..08960ee 100644
@@ -125,7 +125,7 @@ If a fuzzer configuration is specified, then it has the next interpretation:
     will be always fuzzed for every test. This case is useful for regression
     testing.
 
-For now only header fields and header extensions are generated.
+For now only header fields, header extensions and L1/L2 tables are generated.
 
 
 Module interfaces

index 3e9e65d..6ec40a4 100755
@@ -21,8 +21,8 @@
 import sys, os, signal
 import subprocess
 import random
+import shutil
 from itertools import count
-from shutil import rmtree
 import getopt
 try:
     import json

@@ -107,7 +107,9 @@ class TestEnv(object):
                           'discard $off $len'],
                          ['qemu-io', '$test_img', '-c',
                           'truncate $off']]
-        for fmt in ['raw', 'vmdk', 'vdi', 'cow', 'qcow2', 'file',
+        # VMDK format is skipped because such conversion requires
+        # a pregenerated vmdk file
+        for fmt in ['raw', 'vdi', 'cow', 'qcow2', 'file',
                     'qed', 'vpc']:
             self.commands.append(
                          ['qemu-img', 'convert', '-f', 'qcow2', '-O', fmt,

@@ -146,7 +148,7 @@ class TestEnv(object):
                                           'file', 'qed', 'vpc'])
         backing_file_name = 'backing_img.' + backing_file_fmt
         # Size of the backing file varies from 1 to 10 MB
-        backing_file_size = random.randint(1, 10)*(1 << 20)
+        backing_file_size = random.randint(1, 10) * (1 << 20)
         cmd = self.qemu_img + ['create', '-f', backing_file_fmt,
                                backing_file_name, str(backing_file_size)]
         devnull = open('/dev/null', 'r+')

@@ -170,17 +172,18 @@ class TestEnv(object):
             commands = input_commands
         os.chdir(self.current_dir)
         backing_file_name, backing_file_fmt = self._create_backing_file()
-        img_size = image_generator.create_image('test_image',
+        img_size = image_generator.create_image('test.img',
                                                 backing_file_name,
                                                 backing_file_fmt,
                                                 fuzz_config)
         for item in commands:
+            shutil.copy('test.img', 'copy.img')
             start = random.randint(0, img_size)
             end = random.randint(start, img_size)
             current_cmd = list(self.__dict__[item[0].replace('-', '_')])
             # Replace all placeholders with their real values
             for v in item[1:]:
-                c = v.replace('$test_img', 'test_image').\
+                c = v.replace('$test_img', 'copy.img').\
                     replace('$off', str(start)).\
                     replace('$len', str(end - start))
                 current_cmd.append(c)

@@ -208,6 +211,7 @@ class TestEnv(object):
                     multilog(test_summary + "PASS: Application exited with" + \
                              " the code '%d'\n\n" % retcode, sys.stdout,
                              self.log, self.parent_log)
+            os.remove('copy.img')
 
     def finish(self):
         """ Restore environment after a test execution. Remove folders of

@@ -217,7 +221,7 @@ class TestEnv(object):
         self.parent_log.close()
         os.chdir(self.init_path)
         if self.cleanup and not self.failed:
-            rmtree(self.current_dir)
+            shutil.rmtree(self.current_dir)
 
 if __name__ == '__main__':
 

index ef9198f..178fef8 100644
@@ -327,3 +327,31 @@ def feature_name(current):
         truncate_string(STRING_V, 46)  # Fuzz padding (field length = 46)
     ]
     return selector(current, constraints, string_validator)
+
+
+def l1_entry(current):
+    """Fuzz an entry of the L1 table"""
+    constraints = UINT64_V
+    # Reserved bits are ignored
+    # Added a possibility when only flags are fuzzed
+    offset = 0x7fffffffffffffff & random.choice([selector(current,
+                                                          constraints),
+                                                 current])
+    is_cow = random.randint(0, 1)
+    return offset + (is_cow << UINT64_M)
+
+
+def l2_entry(current):
+    """Fuzz an entry of an L2 table"""
+    constraints = UINT64_V
+    # Reserved bits are ignored
+    # Added a possibility when only flags are fuzzed
+    offset = 0x3ffffffffffffffe & random.choice([selector(current,
+                                                          constraints),
+                                                 current])
+    is_compressed = random.randint(0, 1)
+    is_cow = random.randint(0, 1)
+    is_zero = random.randint(0, 1)
+    value = offset + (is_cow << UINT64_M) + \
+            (is_compressed << UINT64_M - 1) + is_zero
+    return value

index 2bad223..5f759e6 100644
@@ -19,6 +19,8 @@
 import random
 import struct
 import fuzz
+from math import ceil
+from os import urandom
 
 MAX_IMAGE_SIZE = 10*2**20
 # Standard sizes

@@ -97,7 +99,66 @@ class Image(object):
         return [cluster_bits, img_size]
 
     @staticmethod
-    def _header(cluster_bits, img_size, backing_file_name=None):
+    def _get_available_clusters(used, number):
+        """Return a set of indices of not allocated clusters
+
+        'used' contains indices of currently allocated clusters.
+        All clusters that cannot be allocated between 'used' clusters will have
+        indices appended to the end of 'used'.
+        """
+        append_id = max(used) + 1
+        free = set(range(1, append_id)) - used
+        if len(free) >= number:
+            return set(random.sample(free, number))
+        else:
+            return free | set(range(append_id, append_id + number - len(free)))
+
+    @staticmethod
+    def _get_adjacent_clusters(used, size):
+        """Return an index of the first cluster in the sequence of free ones
+
+        'used' contains indices of currently allocated clusters. 'size' is the
+        length of the sequence of free clusters.
+        If the sequence of 'size' is not available between 'used' clusters, its
+        first index will be append to the end of 'used'.
+        """
+        def get_cluster_id(lst, length):
+            """Return the first index of the sequence of the specified length
+            or -1 if the sequence cannot be inserted in the list
+        """
+            if len(lst) != 0:
+                pairs = []
+                pair = (lst[0], 1)
+                for i in range(1, len(lst)):
+                    if lst[i] == lst[i-1] + 1:
+                        pair = (lst[i], pair[1] + 1)
+                    else:
+                        pairs.append(pair)
+                        pair = (lst[i], 1)
+                pairs.append(pair)
+                random.shuffle(pairs)
+                for x, s in pairs:
+                    if s >= length:
+                        return x - length + 1
+            return -1
+
+        append_id = max(used) + 1
+        free = list(set(range(1, append_id)) - used)
+        idx = get_cluster_id(free, size)
+        if idx == -1:
+            return append_id
+        else:
+            return idx
+
+    @staticmethod
+    def _alloc_data(img_size, cluster_size):
+        """Return a set of random indices of clusters allocated for guest data
+        """
+        num_of_cls = img_size/cluster_size
+        return set(random.sample(range(1, num_of_cls + 1),
+                                 random.randint(0, num_of_cls)))
+
+    def create_header(self, cluster_bits, img_size, backing_file_name=None):
         """Generate a random valid header"""
         meta_header = [
             ['>4s', 0, "QFI\xfb", 'magic'],

@@ -121,17 +182,18 @@ class Image(object):
             ['>I', 96, 4, 'refcount_order'],
             ['>I', 100, 0, 'header_length']
         ]
-        v_header = FieldsList(meta_header)
+        self.header = FieldsList(meta_header)
 
-        if v_header['version'][0].value == 2:
-            v_header['header_length'][0].value = 72
+        if self.header['version'][0].value == 2:
+            self.header['header_length'][0].value = 72
         else:
-            v_header['incompatible_features'][0].value = random.getrandbits(2)
-            v_header['compatible_features'][0].value = random.getrandbits(1)
-            v_header['header_length'][0].value = 104
+            self.header['incompatible_features'][0].value = random\
+                                                                .getrandbits(2)
+            self.header['compatible_features'][0].value = random.getrandbits(1)
+            self.header['header_length'][0].value = 104
 
-        max_header_len = struct.calcsize(v_header['header_length'][0].fmt) + \
-                         v_header['header_length'][0].offset
+        max_header_len = struct.calcsize(self.header['header_length'][0].fmt)+\
+                         self.header['header_length'][0].offset
         end_of_extension_area_len = 2*UINT32_S
         free_space = (1 << cluster_bits) - (max_header_len +
                                             end_of_extension_area_len)

@@ -140,41 +202,35 @@ class Image(object):
         # cluster.
         if (backing_file_name is not None) and \
            (free_space >= len(backing_file_name)):
-            v_header['backing_file_size'][0].value = len(backing_file_name)
-            v_header['backing_file_offset'][0].value = (1 << cluster_bits) - \
-                                                       len(backing_file_name)
+            self.header['backing_file_size'][0].value = len(backing_file_name)
+            self.header['backing_file_offset'][0]\
+                .value = (1 << cluster_bits) - len(backing_file_name)
 
-        return v_header
-
-    @staticmethod
-    def _backing_file_name(header, backing_file_name=None):
+    def set_backing_file_name(self, backing_file_name=None):
         """Add the name of the backing file at the offset specified
         in the header
         """
         if (backing_file_name is not None) and \
-           (not header['backing_file_offset'][0].value == 0):
+           (not self.header['backing_file_offset'][0].value == 0):
             data_len = len(backing_file_name)
             data_fmt = '>' + str(data_len) + 's'
-            data_field = FieldsList([
-                [data_fmt, header['backing_file_offset'][0].value,
+            self.backing_file_name = FieldsList([
+                [data_fmt, self.header['backing_file_offset'][0].value,
                  backing_file_name, 'bf_name']
             ])
         else:
-            data_field = FieldsList()
+            self.backing_file_name = FieldsList()
 
-        return data_field
-
-    @staticmethod
-    def _backing_file_format(header, backing_file_fmt=None):
+    def set_backing_file_format(self, backing_file_fmt=None):
         """Generate the header extension for the backing file
         format
         """
         # Calculation of the free space available in the first cluster
-        offset = struct.calcsize(header['header_length'][0].fmt) + \
-                 header['header_length'][0].offset
+        offset = struct.calcsize(self.header['header_length'][0].fmt) + \
+                 self.header['header_length'][0].offset
         end_of_extension_area_len = 2*UINT32_S
-        high_border = (header['backing_file_offset'][0].value or
-                       ((1 << header['cluster_bits'][0].value) - 1)) - \
+        high_border = (self.header['backing_file_offset'][0].value or
+                       ((1 << self.header['cluster_bits'][0].value) - 1)) - \
             end_of_extension_area_len
         free_space = high_border - offset
         ext_size = 2*UINT32_S + ((len(backing_file_fmt) + 7) & ~7)

@@ -183,20 +239,20 @@ class Image(object):
             ext_data_len = len(backing_file_fmt)
             ext_data_fmt = '>' + str(ext_data_len) + 's'
             ext_padding_len = 7 - (ext_data_len - 1) % 8
-            ext = FieldsList([
+            self.backing_file_format = FieldsList([
                 ['>I', offset, 0xE2792ACA, 'ext_magic'],
                 ['>I', offset + UINT32_S, ext_data_len, 'ext_length'],
                 [ext_data_fmt, offset + UINT32_S*2, backing_file_fmt,
                  'bf_format']
             ])
-            offset = ext['bf_format'][0].offset + \
-                     struct.calcsize(ext['bf_format'][0].fmt) + ext_padding_len
+            offset = self.backing_file_format['bf_format'][0].offset + \
+                     struct.calcsize(self.backing_file_format[
+                         'bf_format'][0].fmt) + ext_padding_len
         else:
-            ext = FieldsList()
-        return (ext, offset)
+            self.backing_file_format = FieldsList()
+        return offset
 
-    @staticmethod
-    def _feature_name_table(header, offset):
+    def create_feature_name_table(self, offset):
         """Generate a random header extension for names of features used in
         the image
         """

@@ -205,8 +261,8 @@ class Image(object):
             return (random.randint(0, 2), random.randint(0, 63))
 
         end_of_extension_area_len = 2*UINT32_S
-        high_border = (header['backing_file_offset'][0].value or
-                       (1 << header['cluster_bits'][0].value) - 1) - \
+        high_border = (self.header['backing_file_offset'][0].value or
+                       (1 << self.header['cluster_bits'][0].value) - 1) - \
             end_of_extension_area_len
         free_space = high_border - offset
         # Sum of sizes of 'magic' and 'length' header extension fields

@@ -235,26 +291,110 @@ class Image(object):
                 inner_offset += fnt_entry_size
             # No padding for the extension is necessary, because
             # the extension length is multiple of 8
-            ext = FieldsList([
+            self.feature_name_table = FieldsList([
                 ['>I', offset, 0x6803f857, 'ext_magic'],
-                ['>I', offset + UINT32_S, len(feature_tables)*48, 'ext_length']
+                # Length of one feature table equals to 3 fields and 48 bytes
+                ['>I', offset + UINT32_S, len(feature_tables)/3*48,
+                 'ext_length']
             ] + feature_tables)
             offset = inner_offset
         else:
-            ext = FieldsList()
+            self.feature_name_table = FieldsList()
 
-        return (ext, offset)
+        return offset
 
-    @staticmethod
-    def _end_of_extension_area(offset):
+    def set_end_of_extension_area(self, offset):
         """Generate a mandatory header extension marking end of header
         extensions
         """
-        ext = FieldsList([
+        self.end_of_extension_area = FieldsList([
             ['>I', offset, 0, 'ext_magic'],
             ['>I', offset + UINT32_S, 0, 'ext_length']
         ])
-        return ext
+
+    def create_l2_tables(self, meta_data=None):
+        """Generate random valid L2 tables"""
+
+        def create_entry(accum, item):
+            """Generate an L2 entry"""
+            offset = item[0]*self.cluster_size
+            for field in item[1]:
+                entry_offset = offset + field[0]*UINT64_S
+                cluster_descriptor = field[1]*self.cluster_size
+                if not self.header['version'][0].value == 2:
+                    cluster_descriptor += random.randint(0, 1)
+                # While snapshots are not supported, bit #63 = 1
+                # Compressed clusters are not supported => bit #62 = 0
+                entry_val = (1 << 63) + cluster_descriptor
+                accum.append(['>Q', entry_offset, entry_val, 'l2_entry'])
+            return accum
+
+        if meta_data is None:
+            v_meta_data = set([0])
+        else:
+            v_meta_data = set(meta_data)
+        temp = list(self.data_clusters)
+        random.shuffle(temp)
+        l2_content = []
+        # Number of entries in an L2 table
+        l2_size = self.cluster_size/UINT64_S
+        # Binding of data clusters to L2 tables
+        # Each table contains from 1 to l2_size active entries
+        while len(temp) > 0:
+            num_of_entries = random.randint(1, l2_size)
+            if num_of_entries > len(temp):
+                num_of_entries = len(temp)
+            entries, temp = temp[:num_of_entries], temp[num_of_entries:]
+            entry_ids = random.sample(range(l2_size), num_of_entries)
+            l2_content.append(zip(entry_ids, entries))
+
+        l2_clusters = self._get_available_clusters(self.data_clusters |
+                                                   v_meta_data,
+                                                   len(l2_content))
+        l2 = reduce(create_entry, zip(l2_clusters, l2_content), [])
+        self.l2_tables = FieldsList(l2)
+
+    def create_l1_table(self, meta_data=None):
+        """Generate a random valid L1 table"""
+        # Number of clusters used by L2 tables having entries for all
+        # guest image clusters
+        max_l2_size = int(ceil(UINT64_S*self.image_size /
+                               float(self.cluster_size)))
+
+        if len(self.data_clusters) == 0:
+            # All metadata for an empty guest image needs 4 clusters:
+            # header, rfc table, rfc block, L1 table.
+            # Header takes cluster #0, other clusters ##1-3 can be used
+            l1_offset = random.randint(1, 3)*self.cluster_size
+            l1 = [['>Q', l1_offset, 0, 'l1_entry']]
+        else:
+            if meta_data is None:
+                v_meta_data = set([0])
+            else:
+                v_meta_data = set(meta_data)
+            l2_cluster_ids = set()
+            for x in self.l2_tables:
+                l2_cluster_ids.add(x.offset/self.cluster_size)
+            v_meta_data |= l2_cluster_ids
+            # Numbers of active L1 entries
+            l1_entries_ids = random.sample(range(max_l2_size),
+                                           len(l2_cluster_ids))
+            # Number of clusters allocated by L1 table
+            l1_size = int(ceil(UINT64_S*max(l1_entries_ids) /
+                               float(self.cluster_size)))
+            l1_first_cluster_id = self._get_adjacent_clusters(
+                self.data_clusters | v_meta_data, l1_size)
+            l1_offset = l1_first_cluster_id*self.cluster_size
+            l1 = []
+            for f in zip(l1_entries_ids, l2_cluster_ids):
+                entry_offset = l1_offset + UINT64_S*f[0]
+                # While snapshots are not supported bit #63 = 1
+                entry_val = (1 << 63) + f[1]*self.cluster_size
+                l1.append(['>Q', entry_offset, entry_val, 'l1_entry'])
+
+        self.l1_table = FieldsList(l1)
+        self.header['l1_size'][0].value = max_l2_size
+        self.header['l1_table_offset'][0].value = l1_offset
 
     def __init__(self, backing_file_name=None, backing_file_fmt=None):
         """Create a random valid qcow2 image with the correct inner structure

@@ -264,16 +404,15 @@ class Image(object):
         cluster_bits, self.image_size = self._size_params()
         # Saved as an attribute, because it's necessary for writing
         self.cluster_size = 1 << cluster_bits
-        self.header = self._header(cluster_bits, self.image_size,
-                                   backing_file_name)
-        self.backing_file_name = self._backing_file_name(self.header,
-                                                         backing_file_name)
-        self.backing_file_format, \
-            offset = self._backing_file_format(self.header,
-                                               backing_file_fmt)
-        self.feature_name_table, \
-            offset = self._feature_name_table(self.header, offset)
-        self.end_of_extension_area = self._end_of_extension_area(offset)
+        self.create_header(cluster_bits, self.image_size, backing_file_name)
+        self.set_backing_file_name(backing_file_name)
+        offset = self.set_backing_file_format(backing_file_fmt)
+        offset = self.create_feature_name_table(offset)
+        self.set_end_of_extension_area(offset)
+        self.data_clusters = self._alloc_data(self.image_size,
+                                              self.cluster_size)
+        self.create_l2_tables()
+        self.create_l1_table()
         # Container for entire image
         self.data = FieldsList()
         # Percentage of fields will be fuzzed

@@ -284,7 +423,9 @@ class Image(object):
                             self.backing_file_format,
                             self.feature_name_table,
                             self.end_of_extension_area,
-                            self.backing_file_name])
+                            self.backing_file_name,
+                            self.l1_table,
+                            self.l2_tables])
 
     def _join(self):
         """Join all image structure elements as header, tables, etc in one

@@ -341,11 +482,17 @@ class Image(object):
         for field in self.data:
             image_file.seek(field.offset)
             image_file.write(struct.pack(field.fmt, field.value))
+
+        for cluster in sorted(self.data_clusters):
+            image_file.seek(cluster*self.cluster_size)
+            image_file.write(urandom(self.cluster_size))
+
+        # Align the real image size to the cluster size
         image_file.seek(0, 2)
         size = image_file.tell()
-        roundup = (size + self.cluster_size - 1) & ~(self.cluster_size - 1)
-        if roundup > size:
-            image_file.seek(roundup - 1)
+        rounded = (size + self.cluster_size - 1) & ~(self.cluster_size - 1)
+        if rounded > size:
+            image_file.seek(rounded - 1)
             image_file.write("\0")
         image_file.close()