Add qemu 2.4.0

Change-Id: Ic99cbad4b61f8b127b7dc74d04576c0bcbaaf4f5
Signed-off-by: Yang Zhang <yang.z.zhang@intel.com>

3 files changed, 980 insertions, 0 deletions

diff --git a/qemu/tests/image-fuzzer/qcow2/__init__.py b/qemu/tests/image-fuzzer/qcow2/__init__.py
new file mode 100644
index 000000000..e2ebe1931
--- /dev/null
+++ b/qemu/tests/image-fuzzer/qcow2/__init__.py
@@ -0,0 +1 @@
+from layout import create_image
diff --git a/qemu/tests/image-fuzzer/qcow2/fuzz.py b/qemu/tests/image-fuzzer/qcow2/fuzz.py
new file mode 100644
index 000000000..20eba6bc1
--- /dev/null
+++ b/qemu/tests/image-fuzzer/qcow2/fuzz.py
@@ -0,0 +1,367 @@
+# Fuzzing functions for qcow2 fields
+#
+# Copyright (C) 2014 Maria Kustova <maria.k@catit.be>
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# 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 random
+
+UINT8 = 0xff
+UINT16 = 0xffff
+UINT32 = 0xffffffff
+UINT64 = 0xffffffffffffffff
+# Most significant bit orders
+UINT32_M = 31
+UINT64_M = 63
+# Fuzz vectors
+UINT8_V = [0, 0x10, UINT8/4, UINT8/2 - 1, UINT8/2, UINT8/2 + 1, UINT8 - 1,
+           UINT8]
+UINT16_V = [0, 0x100, 0x1000, UINT16/4, UINT16/2 - 1, UINT16/2, UINT16/2 + 1,
+            UINT16 - 1, UINT16]
+UINT32_V = [0, 0x100, 0x1000, 0x10000, 0x100000, UINT32/4, UINT32/2 - 1,
+            UINT32/2, UINT32/2 + 1, UINT32 - 1, UINT32]
+UINT64_V = UINT32_V + [0x1000000, 0x10000000, 0x100000000, UINT64/4,
+                       UINT64/2 - 1, UINT64/2, UINT64/2 + 1, UINT64 - 1,
+                       UINT64]
+STRING_V = ['%s%p%x%d', '.1024d', '%.2049d', '%p%p%p%p', '%x%x%x%x',
+            '%d%d%d%d', '%s%s%s%s', '%99999999999s', '%08x', '%%20d', '%%20n',
+            '%%20x', '%%20s', '%s%s%s%s%s%s%s%s%s%s', '%p%p%p%p%p%p%p%p%p%p',
+            '%#0123456x%08x%x%s%p%d%n%o%u%c%h%l%q%j%z%Z%t%i%e%g%f%a%C%S%08x%%',
+            '%s x 129', '%x x 257']
+
+
+def random_from_intervals(intervals):
+    """Select a random integer number from the list of specified intervals.
+
+    Each interval is a tuple of lower and upper limits of the interval. The
+    limits are included. Intervals in a list should not overlap.
+    """
+    total = reduce(lambda x, y: x + y[1] - y[0] + 1, intervals, 0)
+    r = random.randint(0, total - 1) + intervals[0][0]
+    for x in zip(intervals, intervals[1:]):
+        r = r + (r > x[0][1]) * (x[1][0] - x[0][1] - 1)
+    return r
+
+
+def random_bits(bit_ranges):
+    """Generate random binary mask with ones in the specified bit ranges.
+
+    Each bit_ranges is a list of tuples of lower and upper limits of bit
+    positions will be fuzzed. The limits are included. Random amount of bits
+    in range limits will be set to ones. The mask is returned in decimal
+    integer format.
+    """
+    bit_numbers = []
+    # Select random amount of random positions in bit_ranges
+    for rng in bit_ranges:
+        bit_numbers += random.sample(range(rng[0], rng[1] + 1),
+                                     random.randint(0, rng[1] - rng[0] + 1))
+    val = 0
+    # Set bits on selected positions to ones
+    for bit in bit_numbers:
+        val |= 1 << bit
+    return val
+
+
+def truncate_string(strings, length):
+    """Return strings truncated to specified length."""
+    if type(strings) == list:
+        return [s[:length] for s in strings]
+    else:
+        return strings[:length]
+
+
+def validator(current, pick, choices):
+    """Return a value not equal to the current selected by the pick
+    function from choices.
+    """
+    while True:
+        val = pick(choices)
+        if not val == current:
+            return val
+
+
+def int_validator(current, intervals):
+    """Return a random value from intervals not equal to the current.
+
+    This function is useful for selection from valid values except current one.
+    """
+    return validator(current, random_from_intervals, intervals)
+
+
+def bit_validator(current, bit_ranges):
+    """Return a random bit mask not equal to the current.
+
+    This function is useful for selection from valid values except current one.
+    """
+    return validator(current, random_bits, bit_ranges)
+
+
+def string_validator(current, strings):
+    """Return a random string value from the list not equal to the current.
+
+    This function is useful for selection from valid values except current one.
+    """
+    return validator(current, random.choice, strings)
+
+
+def selector(current, constraints, validate=int_validator):
+    """Select one value from all defined by constraints.
+
+    Each constraint produces one random value satisfying to it. The function
+    randomly selects one value satisfying at least one constraint (depending on
+    constraints overlaps).
+    """
+    def iter_validate(c):
+        """Apply validate() only to constraints represented as lists.
+
+        This auxiliary function replaces short circuit conditions not supported
+        in Python 2.4
+        """
+        if type(c) == list:
+            return validate(current, c)
+        else:
+            return c
+
+    fuzz_values = [iter_validate(c) for c in constraints]
+    # Remove current for cases it's implicitly specified in constraints
+    # Duplicate validator functionality to prevent decreasing of probability
+    # to get one of allowable values
+    # TODO: remove validators after implementation of intelligent selection
+    # of fields will be fuzzed
+    try:
+        fuzz_values.remove(current)
+    except ValueError:
+        pass
+    return random.choice(fuzz_values)
+
+
+def magic(current):
+    """Fuzz magic header field.
+
+    The function just returns the current magic value and provides uniformity
+    of calls for all fuzzing functions.
+    """
+    return current
+
+
+def version(current):
+    """Fuzz version header field."""
+    constraints = UINT32_V + [
+        [(2, 3)],  # correct values
+        [(0, 1), (4, UINT32)]
+    ]
+    return selector(current, constraints)
+
+
+def backing_file_offset(current):
+    """Fuzz backing file offset header field."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def backing_file_size(current):
+    """Fuzz backing file size header field."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def cluster_bits(current):
+    """Fuzz cluster bits header field."""
+    constraints = UINT32_V + [
+        [(9, 20)],  # correct values
+        [(0, 9), (20, UINT32)]
+    ]
+    return selector(current, constraints)
+
+
+def size(current):
+    """Fuzz image size header field."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def crypt_method(current):
+    """Fuzz crypt method header field."""
+    constraints = UINT32_V + [
+        1,
+        [(2, UINT32)]
+    ]
+    return selector(current, constraints)
+
+
+def l1_size(current):
+    """Fuzz L1 table size header field."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def l1_table_offset(current):
+    """Fuzz L1 table offset header field."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def refcount_table_offset(current):
+    """Fuzz refcount table offset header field."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def refcount_table_clusters(current):
+    """Fuzz refcount table clusters header field."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def nb_snapshots(current):
+    """Fuzz number of snapshots header field."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def snapshots_offset(current):
+    """Fuzz snapshots offset header field."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def incompatible_features(current):
+    """Fuzz incompatible features header field."""
+    constraints = [
+        [(0, 1)],  # allowable values
+        [(0, UINT64_M)]
+    ]
+    return selector(current, constraints, bit_validator)
+
+
+def compatible_features(current):
+    """Fuzz compatible features header field."""
+    constraints = [
+        [(0, UINT64_M)]
+    ]
+    return selector(current, constraints, bit_validator)
+
+
+def autoclear_features(current):
+    """Fuzz autoclear features header field."""
+    constraints = [
+        [(0, UINT64_M)]
+    ]
+    return selector(current, constraints, bit_validator)
+
+
+def refcount_order(current):
+    """Fuzz number of refcount order header field."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def header_length(current):
+    """Fuzz number of refcount order header field."""
+    constraints = UINT32_V + [
+        72,
+        104,
+        [(0, UINT32)]
+    ]
+    return selector(current, constraints)
+
+
+def bf_name(current):
+    """Fuzz the backing file name."""
+    constraints = [
+        truncate_string(STRING_V, len(current))
+    ]
+    return selector(current, constraints, string_validator)
+
+
+def ext_magic(current):
+    """Fuzz magic field of a header extension."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def ext_length(current):
+    """Fuzz length field of a header extension."""
+    constraints = UINT32_V
+    return selector(current, constraints)
+
+
+def bf_format(current):
+    """Fuzz backing file format in the corresponding header extension."""
+    constraints = [
+        truncate_string(STRING_V, len(current)),
+        truncate_string(STRING_V, (len(current) + 7) & ~7)  # Fuzz padding
+    ]
+    return selector(current, constraints, string_validator)
+
+
+def feature_type(current):
+    """Fuzz feature type field of a feature name table header extension."""
+    constraints = UINT8_V
+    return selector(current, constraints)
+
+
+def feature_bit_number(current):
+    """Fuzz bit number field of a feature name table header extension."""
+    constraints = UINT8_V
+    return selector(current, constraints)
+
+
+def feature_name(current):
+    """Fuzz feature name field of a feature name table header extension."""
+    constraints = [
+        truncate_string(STRING_V, len(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
+    # Add 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
+
+
+def refcount_table_entry(current):
+    """Fuzz an entry of the refcount table."""
+    constraints = UINT64_V
+    return selector(current, constraints)
+
+
+def refcount_block_entry(current):
+    """Fuzz an entry of a refcount block."""
+    constraints = UINT16_V
+    return selector(current, constraints)
diff --git a/qemu/tests/image-fuzzer/qcow2/layout.py b/qemu/tests/image-fuzzer/qcow2/layout.py
new file mode 100644
index 000000000..63e801f4e
--- /dev/null
+++ b/qemu/tests/image-fuzzer/qcow2/layout.py
@@ -0,0 +1,612 @@
+# Generator of fuzzed qcow2 images
+#
+# Copyright (C) 2014 Maria Kustova <maria.k@catit.be>
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# 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 random
+import struct
+import fuzz
+from math import ceil
+from os import urandom
+from itertools import chain
+
+MAX_IMAGE_SIZE = 10 * (1 << 20)
+# Standard sizes
+UINT32_S = 4
+UINT64_S = 8
+
+
+class Field(object):
+
+    """Atomic image element (field).
+
+    The class represents an image field as quadruple of a data format
+    of value necessary for its packing to binary form, an offset from
+    the beginning of the image, a value and a name.
+
+    The field can be iterated as a list [format, offset, value, name].
+    """
+
+    __slots__ = ('fmt', 'offset', 'value', 'name')
+
+    def __init__(self, fmt, offset, val, name):
+        self.fmt = fmt
+        self.offset = offset
+        self.value = val
+        self.name = name
+
+    def __iter__(self):
+        return iter([self.fmt, self.offset, self.value, self.name])
+
+    def __repr__(self):
+        return "Field(fmt='%s', offset=%d, value=%s, name=%s)" % \
+            (self.fmt, self.offset, str(self.value), self.name)
+
+
+class FieldsList(object):
+
+    """List of fields.
+
+    The class allows access to a field in the list by its name.
+    """
+
+    def __init__(self, meta_data=None):
+        if meta_data is None:
+            self.data = []
+        else:
+            self.data = [Field(*f)
+                         for f in meta_data]
+
+    def __getitem__(self, name):
+        return [x for x in self.data if x.name == name]
+
+    def __iter__(self):
+        return iter(self.data)
+
+    def __len__(self):
+        return len(self.data)
+
+
+class Image(object):
+
+    """ Qcow2 image object.
+
+    This class allows to create qcow2 images with random valid structures and
+    values, fuzz them via external qcow2.fuzz module and write the result to
+    a file.
+    """
+
+    def __init__(self, backing_file_name=None):
+        """Create a random valid qcow2 image with the correct header and stored
+        backing file name.
+        """
+        cluster_bits, self.image_size = self._size_params()
+        self.cluster_size = 1 << cluster_bits
+        self.header = FieldsList()
+        self.backing_file_name = FieldsList()
+        self.backing_file_format = FieldsList()
+        self.feature_name_table = FieldsList()
+        self.end_of_extension_area = FieldsList()
+        self.l2_tables = FieldsList()
+        self.l1_table = FieldsList()
+        self.refcount_table = FieldsList()
+        self.refcount_blocks = FieldsList()
+        self.ext_offset = 0
+        self.create_header(cluster_bits, backing_file_name)
+        self.set_backing_file_name(backing_file_name)
+        self.data_clusters = self._alloc_data(self.image_size,
+                                              self.cluster_size)
+        # Percentage of fields will be fuzzed
+        self.bias = random.uniform(0.2, 0.5)
+
+    def __iter__(self):
+        return chain(self.header, self.backing_file_format,
+                     self.feature_name_table, self.end_of_extension_area,
+                     self.backing_file_name, self.l1_table, self.l2_tables,
+                     self.refcount_table, self.refcount_blocks)
+
+    def create_header(self, cluster_bits, backing_file_name=None):
+        """Generate a random valid header."""
+        meta_header = [
+            ['>4s', 0, "QFI\xfb", 'magic'],
+            ['>I', 4, random.randint(2, 3), 'version'],
+            ['>Q', 8, 0, 'backing_file_offset'],
+            ['>I', 16, 0, 'backing_file_size'],
+            ['>I', 20, cluster_bits, 'cluster_bits'],
+            ['>Q', 24, self.image_size, 'size'],
+            ['>I', 32, 0, 'crypt_method'],
+            ['>I', 36, 0, 'l1_size'],
+            ['>Q', 40, 0, 'l1_table_offset'],
+            ['>Q', 48, 0, 'refcount_table_offset'],
+            ['>I', 56, 0, 'refcount_table_clusters'],
+            ['>I', 60, 0, 'nb_snapshots'],
+            ['>Q', 64, 0, 'snapshots_offset'],
+            ['>Q', 72, 0, 'incompatible_features'],
+            ['>Q', 80, 0, 'compatible_features'],
+            ['>Q', 88, 0, 'autoclear_features'],
+            # Only refcount_order = 4 is supported by current (07.2014)
+            # implementation of QEMU
+            ['>I', 96, 4, 'refcount_order'],
+            ['>I', 100, 0, 'header_length']
+        ]
+        self.header = FieldsList(meta_header)
+
+        if self.header['version'][0].value == 2:
+            self.header['header_length'][0].value = 72
+        else:
+            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
+        # Extensions start at the header last field offset and the field size
+        self.ext_offset = struct.calcsize(
+            self.header['header_length'][0].fmt) + \
+            self.header['header_length'][0].offset
+        end_of_extension_area_len = 2 * UINT32_S
+        free_space = self.cluster_size - self.ext_offset - \
+                     end_of_extension_area_len
+        # If the backing file name specified and there is enough space for it
+        # in the first cluster, then it's placed in the very end of the first
+        # cluster.
+        if (backing_file_name is not None) and \
+           (free_space >= len(backing_file_name)):
+            self.header['backing_file_size'][0].value = len(backing_file_name)
+            self.header['backing_file_offset'][0].value = \
+                                    self.cluster_size - len(backing_file_name)
+
+    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 self.header['backing_file_offset'][0].value == 0):
+            data_len = len(backing_file_name)
+            data_fmt = '>' + str(data_len) + 's'
+            self.backing_file_name = FieldsList([
+                [data_fmt, self.header['backing_file_offset'][0].value,
+                 backing_file_name, 'bf_name']
+            ])
+
+    def set_backing_file_format(self, backing_file_fmt=None):
+        """Generate the header extension for the backing file format."""
+        if backing_file_fmt is not None:
+            # Calculation of the free space available in the first cluster
+            end_of_extension_area_len = 2 * UINT32_S
+            high_border = (self.header['backing_file_offset'][0].value or
+                           (self.cluster_size - 1)) - \
+                end_of_extension_area_len
+            free_space = high_border - self.ext_offset
+            ext_size = 2 * UINT32_S + ((len(backing_file_fmt) + 7) & ~7)
+
+            if free_space >= ext_size:
+                ext_data_len = len(backing_file_fmt)
+                ext_data_fmt = '>' + str(ext_data_len) + 's'
+                ext_padding_len = 7 - (ext_data_len - 1) % 8
+                self.backing_file_format = FieldsList([
+                    ['>I', self.ext_offset, 0xE2792ACA, 'ext_magic'],
+                    ['>I', self.ext_offset + UINT32_S, ext_data_len,
+                     'ext_length'],
+                    [ext_data_fmt, self.ext_offset + UINT32_S * 2,
+                     backing_file_fmt, 'bf_format']
+                ])
+                self.ext_offset = \
+                        struct.calcsize(
+                            self.backing_file_format['bf_format'][0].fmt) + \
+                        ext_padding_len + \
+                        self.backing_file_format['bf_format'][0].offset
+
+    def create_feature_name_table(self):
+        """Generate a random header extension for names of features used in
+        the image.
+        """
+        def gen_feat_ids():
+            """Return random feature type and feature bit."""
+            return (random.randint(0, 2), random.randint(0, 63))
+
+        end_of_extension_area_len = 2 * UINT32_S
+        high_border = (self.header['backing_file_offset'][0].value or
+                       (self.cluster_size - 1)) - \
+            end_of_extension_area_len
+        free_space = high_border - self.ext_offset
+        # Sum of sizes of 'magic' and 'length' header extension fields
+        ext_header_len = 2 * UINT32_S
+        fnt_entry_size = 6 * UINT64_S
+        num_fnt_entries = min(10, (free_space - ext_header_len) /
+                              fnt_entry_size)
+        if not num_fnt_entries == 0:
+            feature_tables = []
+            feature_ids = []
+            inner_offset = self.ext_offset + ext_header_len
+            feat_name = 'some cool feature'
+            while len(feature_tables) < num_fnt_entries * 3:
+                feat_type, feat_bit = gen_feat_ids()
+                # Remove duplicates
+                while (feat_type, feat_bit) in feature_ids:
+                    feat_type, feat_bit = gen_feat_ids()
+                feature_ids.append((feat_type, feat_bit))
+                feat_fmt = '>' + str(len(feat_name)) + 's'
+                feature_tables += [['B', inner_offset,
+                                    feat_type, 'feature_type'],
+                                   ['B', inner_offset + 1, feat_bit,
+                                    'feature_bit_number'],
+                                   [feat_fmt, inner_offset + 2,
+                                    feat_name, 'feature_name']
+                ]
+                inner_offset += fnt_entry_size
+            # No padding for the extension is necessary, because
+            # the extension length is multiple of 8
+            self.feature_name_table = FieldsList([
+                ['>I', self.ext_offset, 0x6803f857, 'ext_magic'],
+                # One feature table contains 3 fields and takes 48 bytes
+                ['>I', self.ext_offset + UINT32_S,
+                 len(feature_tables) / 3 * 48, 'ext_length']
+            ] + feature_tables)
+            self.ext_offset = inner_offset
+
+    def set_end_of_extension_area(self):
+        """Generate a mandatory header extension marking end of header
+        extensions.
+        """
+        self.end_of_extension_area = FieldsList([
+            ['>I', self.ext_offset, 0, 'ext_magic'],
+            ['>I', self.ext_offset + UINT32_S, 0, 'ext_length']
+        ])
+
+    def create_l_structures(self):
+        """Generate random valid L1 and L2 tables."""
+        def create_l2_entry(host, guest, l2_cluster):
+            """Generate one L2 entry."""
+            offset = l2_cluster * self.cluster_size
+            l2_size = self.cluster_size / UINT64_S
+            entry_offset = offset + UINT64_S * (guest % l2_size)
+            cluster_descriptor = host * 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
+            return ['>Q', entry_offset, entry_val, 'l2_entry']
+
+        def create_l1_entry(l2_cluster, l1_offset, guest):
+            """Generate one L1 entry."""
+            l2_size = self.cluster_size / UINT64_S
+            entry_offset = l1_offset + UINT64_S * (guest / l2_size)
+            # While snapshots are not supported bit #63 = 1
+            entry_val = (1 << 63) + l2_cluster * self.cluster_size
+            return ['>Q', entry_offset, entry_val, 'l1_entry']
+
+        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']]
+            l2 = []
+        else:
+            meta_data = self._get_metadata()
+            guest_clusters = random.sample(range(self.image_size /
+                                                 self.cluster_size),
+                                           len(self.data_clusters))
+            # Number of entries in a L1/L2 table
+            l_size = self.cluster_size / UINT64_S
+            # Number of clusters necessary for L1 table
+            l1_size = int(ceil((max(guest_clusters) + 1) / float(l_size**2)))
+            l1_start = self._get_adjacent_clusters(self.data_clusters |
+                                                   meta_data, l1_size)
+            meta_data |= set(range(l1_start, l1_start + l1_size))
+            l1_offset = l1_start * self.cluster_size
+            # Indices of L2 tables
+            l2_ids = []
+            # Host clusters allocated for L2 tables
+            l2_clusters = []
+            # L1 entries
+            l1 = []
+            # L2 entries
+            l2 = []
+            for host, guest in zip(self.data_clusters, guest_clusters):
+                l2_id = guest / l_size
+                if l2_id not in l2_ids:
+                    l2_ids.append(l2_id)
+                    l2_clusters.append(self._get_adjacent_clusters(
+                        self.data_clusters | meta_data | set(l2_clusters),
+                        1))
+                    l1.append(create_l1_entry(l2_clusters[-1], l1_offset,
+                                              guest))
+                l2.append(create_l2_entry(host, guest,
+                                          l2_clusters[l2_ids.index(l2_id)]))
+        self.l2_tables = FieldsList(l2)
+        self.l1_table = FieldsList(l1)
+        self.header['l1_size'][0].value = int(ceil(UINT64_S * self.image_size /
+                                                float(self.cluster_size**2)))
+        self.header['l1_table_offset'][0].value = l1_offset
+
+    def create_refcount_structures(self):
+        """Generate random refcount blocks and refcount table."""
+        def allocate_rfc_blocks(data, size):
+            """Return indices of clusters allocated for refcount blocks."""
+            cluster_ids = set()
+            diff = block_ids = set([x / size for x in data])
+            while len(diff) != 0:
+                # Allocate all yet not allocated clusters
+                new = self._get_available_clusters(data | cluster_ids,
+                                                   len(diff))
+                # Indices of new refcount blocks necessary to cover clusters
+                # in 'new'
+                diff = set([x / size for x in new]) - block_ids
+                cluster_ids |= new
+                block_ids |= diff
+            return cluster_ids, block_ids
+
+        def allocate_rfc_table(data, init_blocks, block_size):
+            """Return indices of clusters allocated for the refcount table
+            and updated indices of clusters allocated for blocks and indices
+            of blocks.
+            """
+            blocks = set(init_blocks)
+            clusters = set()
+            # Number of entries in one cluster of the refcount table
+            size = self.cluster_size / UINT64_S
+            # Number of clusters necessary for the refcount table based on
+            # the current number of refcount blocks
+            table_size = int(ceil((max(blocks) + 1) / float(size)))
+            # Index of the first cluster of the refcount table
+            table_start = self._get_adjacent_clusters(data, table_size + 1)
+            # Clusters allocated for the current length of the refcount table
+            table_clusters = set(range(table_start, table_start + table_size))
+            # Clusters allocated for the refcount table including
+            # last optional one for potential l1 growth
+            table_clusters_allocated = set(range(table_start, table_start +
+                                                 table_size + 1))
+            # New refcount blocks necessary for clusters occupied by the
+            # refcount table
+            diff = set([c / block_size for c in table_clusters]) - blocks
+            blocks |= diff
+            while len(diff) != 0:
+                # Allocate clusters for new refcount blocks
+                new = self._get_available_clusters((data | clusters) |
+                                                   table_clusters_allocated,
+                                                   len(diff))
+                # Indices of new refcount blocks necessary to cover
+                # clusters in 'new'
+                diff = set([x / block_size for x in new]) - blocks
+                clusters |= new
+                blocks |= diff
+                # Check if the refcount table needs one more cluster
+                if int(ceil((max(blocks) + 1) / float(size))) > table_size:
+                    new_block_id = (table_start + table_size) / block_size
+                    # Check if the additional table cluster needs
+                    # one more refcount block
+                    if new_block_id not in blocks:
+                        diff.add(new_block_id)
+                    table_clusters.add(table_start + table_size)
+                    table_size += 1
+            return table_clusters, blocks, clusters
+
+        def create_table_entry(table_offset, block_cluster, block_size,
+                               cluster):
+            """Generate a refcount table entry."""
+            offset = table_offset + UINT64_S * (cluster / block_size)
+            return ['>Q', offset, block_cluster * self.cluster_size,
+                    'refcount_table_entry']
+
+        def create_block_entry(block_cluster, block_size, cluster):
+            """Generate a list of entries for the current block."""
+            entry_size = self.cluster_size / block_size
+            offset = block_cluster * self.cluster_size
+            entry_offset = offset + entry_size * (cluster % block_size)
+            # While snapshots are not supported all refcounts are set to 1
+            return ['>H', entry_offset, 1, 'refcount_block_entry']
+        # Size of a block entry in bits
+        refcount_bits = 1 << self.header['refcount_order'][0].value
+        # Number of refcount entries per refcount block
+        # Convert self.cluster_size from bytes to bits to have the same
+        # base for the numerator and denominator
+        block_size = self.cluster_size * 8 / refcount_bits
+        meta_data = self._get_metadata()
+        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
+            block_clusters = set([random.choice(list(set(range(1, 4)) -
+                                                     meta_data))])
+            block_ids = set([0])
+            table_clusters = set([random.choice(list(set(range(1, 4)) -
+                                                     meta_data -
+                                                     block_clusters))])
+        else:
+            block_clusters, block_ids = \
+                                allocate_rfc_blocks(self.data_clusters |
+                                                    meta_data, block_size)
+            table_clusters, block_ids, new_clusters = \
+                                    allocate_rfc_table(self.data_clusters |
+                                                       meta_data |
+                                                       block_clusters,
+                                                       block_ids,
+                                                       block_size)
+            block_clusters |= new_clusters
+
+        meta_data |= block_clusters | table_clusters
+        table_offset = min(table_clusters) * self.cluster_size
+        block_id = None
+        # Clusters allocated for refcount blocks
+        block_clusters = list(block_clusters)
+        # Indices of refcount blocks
+        block_ids = list(block_ids)
+        # Refcount table entries
+        rfc_table = []
+        # Refcount entries
+        rfc_blocks = []
+
+        for cluster in sorted(self.data_clusters | meta_data):
+            if cluster / block_size != block_id:
+                block_id = cluster / block_size
+                block_cluster = block_clusters[block_ids.index(block_id)]
+                rfc_table.append(create_table_entry(table_offset,
+                                                    block_cluster,
+                                                    block_size, cluster))
+            rfc_blocks.append(create_block_entry(block_cluster, block_size,
+                                                 cluster))
+        self.refcount_table = FieldsList(rfc_table)
+        self.refcount_blocks = FieldsList(rfc_blocks)
+
+        self.header['refcount_table_offset'][0].value = table_offset
+        self.header['refcount_table_clusters'][0].value = len(table_clusters)
+
+    def fuzz(self, fields_to_fuzz=None):
+        """Fuzz an image by corrupting values of a random subset of its fields.
+
+        Without parameters the method fuzzes an entire image.
+
+        If 'fields_to_fuzz' is specified then only fields in this list will be
+        fuzzed. 'fields_to_fuzz' can contain both individual fields and more
+        general image elements as a header or tables.
+
+        In the first case the field will be fuzzed always.
+        In the second a random subset of fields will be selected and fuzzed.
+        """
+        def coin():
+            """Return boolean value proportional to a portion of fields to be
+            fuzzed.
+            """
+            return random.random() < self.bias
+
+        if fields_to_fuzz is None:
+            for field in self:
+                if coin():
+                    field.value = getattr(fuzz, field.name)(field.value)
+        else:
+            for item in fields_to_fuzz:
+                if len(item) == 1:
+                    for field in getattr(self, item[0]):
+                        if coin():
+                            field.value = getattr(fuzz,
+                                                  field.name)(field.value)
+                else:
+                    # If fields with the requested name were not generated
+                    # getattr(self, item[0])[item[1]] returns an empty list
+                    for field in getattr(self, item[0])[item[1]]:
+                        field.value = getattr(fuzz, field.name)(field.value)
+
+    def write(self, filename):
+        """Write an entire image to the file."""
+        image_file = open(filename, 'w')
+        for field in self:
+            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()
+        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()
+
+    @staticmethod
+    def _size_params():
+        """Generate a random image size aligned to a random correct
+        cluster size.
+        """
+        cluster_bits = random.randrange(9, 21)
+        cluster_size = 1 << cluster_bits
+        img_size = random.randrange(0, MAX_IMAGE_SIZE + 1, cluster_size)
+        return (cluster_bits, img_size)
+
+    @staticmethod
+    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 None 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 None
+
+        append_id = max(used) + 1
+        free = list(set(range(1, append_id)) - used)
+        idx = get_cluster_id(free, size)
+        if idx is None:
+            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 _get_metadata(self):
+        """Return indices of clusters allocated for image metadata."""
+        ids = set()
+        for x in self:
+            ids.add(x.offset/self.cluster_size)
+        return ids
+
+
+def create_image(test_img_path, backing_file_name=None, backing_file_fmt=None,
+                 fields_to_fuzz=None):
+    """Create a fuzzed image and write it to the specified file."""
+    image = Image(backing_file_name)
+    image.set_backing_file_format(backing_file_fmt)
+    image.create_feature_name_table()
+    image.set_end_of_extension_area()
+    image.create_l_structures()
+    image.create_refcount_structures()
+    image.fuzz(fields_to_fuzz)
+    image.write(test_img_path)
+    return image.image_size