From patchwork Wed Aug 6 15:08:26 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maria Kustova X-Patchwork-Id: 377053 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4CF96140095 for ; Thu, 7 Aug 2014 01:09:27 +1000 (EST) Received: from localhost ([::1]:39512 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XF2qD-0005pW-Br for incoming@patchwork.ozlabs.org; Wed, 06 Aug 2014 11:09:25 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:40532) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XF2pa-0004tD-9A for qemu-devel@nongnu.org; Wed, 06 Aug 2014 11:08:52 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XF2pU-0007YR-Fi for qemu-devel@nongnu.org; Wed, 06 Aug 2014 11:08:46 -0400 Received: from mail-la0-f43.google.com ([209.85.215.43]:36984) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XF2pU-0007YA-3a for qemu-devel@nongnu.org; Wed, 06 Aug 2014 11:08:40 -0400 Received: by mail-la0-f43.google.com with SMTP id hr17so2168114lab.2 for ; Wed, 06 Aug 2014 08:08:39 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:in-reply-to:references; bh=8uQkDa7yZ7AzyNvc9Voee7LUNIhPn/m7c6j6cf/45yw=; b=bfEg+MFLwfHmdGVD0mvp/3LulwdQTE94C2Apuun1VJSOZ+w2tuodsqof1Ft3aNSeD/ AlMe6JBZxD07khXfNeugCIcxDKEz6vlvVeZ/9DZTFaS33kVX8RNJl8ZTPRHsH3vzNseA wmw2C4K9CaO4mWmOEQw7+Ji4+FC+8xw03bt8QocZGoCjU895KfNpV1A+bTg2NnqYDFUF By3l3vgcZwds87Pi7Txh1AzcqdWAsbYp1NvCwIG+v6o0Ui2iXMjADSKB8O1zB6Sup6NV YE/0hsHOZxSS40xmy8OwMN7q+K+1BhrCL+ka4CBZcX9xluennIRC515H+tQ8/sfrEJsD K2lA== X-Gm-Message-State: ALoCoQmkOchRvbaocs7Jvi/2JwBxdCbSX3S4hjjJwx2gQzypag5v7PLKsUUJaZixv9Np2sMrHZK2 X-Received: by 10.112.221.37 with SMTP id qb5mr10892331lbc.69.1407337719131; Wed, 06 Aug 2014 08:08:39 -0700 (PDT) Received: from m0.base.vohkarts.com ([31.134.130.233]) by mx.google.com with ESMTPSA id z8sm618401laa.28.2014.08.06.08.08.37 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Aug 2014 08:08:38 -0700 (PDT) From: Maria Kustova X-Google-Original-From: Maria Kustova To: qemu-devel@nongnu.org Date: Wed, 6 Aug 2014 19:08:26 +0400 Message-Id: <33597f4538bfa88239af08a3ae836c0bafd63b4e.1407336637.git.maria.k@catit.be> X-Mailer: git-send-email 1.9.3 In-Reply-To: References: In-Reply-To: References: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 209.85.215.43 Cc: kwolf@redhat.com, famz@redhat.com, Maria Kustova , stefanha@redhat.com Subject: [Qemu-devel] [PATCH V2 3/3] layout: Add generators of L1/L2 tables X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Valid L2 entries contain offsets to image clusters filled with random data. L2 entries have random positions inside L2 tables. L1 entries contain offsets to generated L2 tables and also have random positions inside the L1 table. Clusters for L1/L2 tables and guest data are selected randomly. Signed-off-by: Maria Kustova --- tests/image-fuzzer/qcow2/layout.py | 273 ++++++++++++++++++++++++++++--------- 1 file changed, 211 insertions(+), 62 deletions(-) diff --git a/tests/image-fuzzer/qcow2/layout.py b/tests/image-fuzzer/qcow2/layout.py index 4c08202..7839d2c 100644 --- a/tests/image-fuzzer/qcow2/layout.py +++ b/tests/image-fuzzer/qcow2/layout.py @@ -19,6 +19,8 @@ import random import struct import fuzz +from math import ceil +from os import urandom MAX_IMAGE_SIZE = 10 * (1 << 20) # Standard sizes @@ -102,7 +104,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 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 create_header(self, cluster_bits, backing_file_name=None): """Generate a random valid header.""" meta_header = [ ['>4s', 0, "QFI\xfb", 'magic'], @@ -110,7 +171,7 @@ class Image(object): ['>Q', 8, 0, 'backing_file_offset'], ['>I', 16, 0, 'backing_file_size'], ['>I', 20, cluster_bits, 'cluster_bits'], - ['>Q', 24, img_size, 'size'], + ['>Q', 24, self.image_size, 'size'], ['>I', 32, 0, 'crypt_method'], ['>I', 36, 0, 'l1_size'], ['>Q', 40, 0, 'l1_table_offset'], @@ -126,63 +187,59 @@ 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 - - max_header_len = struct.calcsize(v_header['header_length'][0].fmt) + \ - v_header['header_length'][0].offset + 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( + 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) + free_space = self.cluster_size - max_header_len - \ + 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)): - 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) - - return v_header + 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) - @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() - - return data_field + self.backing_file_name = FieldsList() - @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. """ - ext = FieldsList() - offset = struct.calcsize(header['header_length'][0].fmt) + \ - header['header_length'][0].offset + self.backing_file_format = FieldsList() + offset = struct.calcsize(self.header['header_length'][0].fmt) + \ + self.header['header_length'][0].offset 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 = (header['backing_file_offset'][0].value or - ((1 << header['cluster_bits'][0].value) - 1)) - \ + high_border = (self.header['backing_file_offset'][0].value or + (self.cluster_size - 1)) - \ end_of_extension_area_len free_space = high_border - offset ext_size = 2 * UINT32_S + ((len(backing_file_fmt) + 7) & ~7) @@ -191,19 +248,19 @@ 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 - return (ext, offset) + offset = self.backing_file_format['bf_format'][0].offset + \ + struct.calcsize(self.backing_file_format[ + 'bf_format'][0].fmt) + ext_padding_len - @staticmethod - def _feature_name_table(header, offset): + return offset + + def create_feature_name_table(self, offset): """Generate a random header extension for names of features used in the image. """ @@ -212,8 +269,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 + (self.cluster_size - 1)) - \ end_of_extension_area_len free_space = high_border - offset # Sum of sizes of 'magic' and 'length' header extension fields @@ -243,7 +300,7 @@ 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'], # One feature table contains 3 fields and takes 48 bytes ['>I', offset + UINT32_S, len(feature_tables) / 3 * 48, @@ -251,39 +308,123 @@ class Image(object): ] + 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 one 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 len(self.data_clusters) == 0: + self.l2_tables = FieldsList() + else: + 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 + # Number of L2 tables having entries for all guest image clusters + max_l2_size = ceil(UINT64_S * self.image_size / + float(self.cluster_size**2)) + low_lim = int(ceil(len(temp) / max_l2_size)) + # Binding of data clusters to L2 tables + # Each table contains from low_lim to l2_size active entries + while len(temp) > 0: + num_of_entries = random.randint(low_lim, 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**2))) + + 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) + 1) / + 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 and allowable values. """ - # Image size is saved as an attribute for the runner needs 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, 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 @@ -294,7 +435,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 @@ -351,6 +494,12 @@ 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() rounded = (size + self.cluster_size - 1) & ~(self.cluster_size - 1)