Skip to contentSkip to conversation

image-fuzzer: Support refcount structures in the qcow2 image generator

PATCH Superseded Maria Kustova 3 participants 9 messages Aug 11, 2014 – Aug 19, 2014

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover image-fuzzer: Support refcount structures in the qcow2 image generator

This patch series adds support of refcount tables and blocks to the qcow2 image generator.

This patch series was created for the 'block-next' branch and based on the next series:
[PATCH V3] layout: Reduce number of generator functions in __init__

Maria Kustova (3):
docs: List all image elements currently supported by the fuzzer
fuzz: Add fuzzing functions for entries of refcount table and blocks
layout: Add generators for refcount tbles and blocks

 docs/image-fuzzer.txt              |   3 +-
 tests/image-fuzzer/qcow2/fuzz.py   |  16 ++++-
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 3 files changed, 152 insertions(+), 3 deletions(-)
Signature · 1 line
1.9.3
#1 lore raw

PATCH 1/3 docs: List all image elements currently supported by the fuzzer

---
 docs/image-fuzzer.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
docs/image-fuzzer.txt +2 -1
index 0d0005d..f707269 100644
@@ -125,7 +125,8 @@ 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, header extensions and L1/L2 tables are generated.
+The generator can create header fields, header extensions, L1/L2 tables and
+refcount blocks and table.
 
 Module interfaces
 -----------------
Signature · 1 line
1.9.3
Reviewed-by on v1 1/3
#2 lore raw

Re: [Qemu-devel] [PATCH 1/3] docs: List all image elements currently supported by the fuzzer

Quoted 10 lines · Maria Kustova
---
 docs/image-fuzzer.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
docs/image-fuzzer.txt +0 -0
index 0d0005d..f707269 100644

docs/image-fuzzer.txt If a fuzzer configuration is specified, then it has the next interpretation: · line 129

Quoted 6 lines
docs/image-fuzzer.txt +2 -1
@@ -125,7 +125,8 @@ 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, header extensions and L1/L2 tables are generated.
+The generator can create header fields, header extensions, L1/L2 tables and
+refcount blocks and table.

"refcount table and blocks" might read better, but it doesn't hurt.

Quoted 6 lines
docs/image-fuzzer.txt +0 -0
 Module interfaces
 -----------------
Signature · 1 line
1.9.3
#3 lore raw

PATCH 2/3 fuzz: Add fuzzing functions for entries of refcount table and blocks

In reply to Maria Kustova
---
 tests/image-fuzzer/qcow2/fuzz.py | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)
tests/image-fuzzer/qcow2/fuzz.py +15 -1
index 57527f9..5852b4d 100644
@@ -18,8 +18,8 @@
 
 import random
 
-
 UINT8 = 0xff
+UINT16 = 0xffff
 UINT32 = 0xffffffff
 UINT64 = 0xffffffffffffffff
 # Most significant bit orders
@@ -28,6 +28,8 @@ 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,
@@ -353,3 +355,15 @@ def l2_entry(current):
     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)
Signature · 1 line
1.9.3
Reviewed-by on v1 2/3
#4 lore raw

Re: [Qemu-devel] [PATCH 2/3] fuzz: Add fuzzing functions for entries of refcount table and blocks

Quoted 20 lines · Maria Kustova
---
 tests/image-fuzzer/qcow2/fuzz.py | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)
tests/image-fuzzer/qcow2/fuzz.py +1 -1
index 57527f9..5852b4d 100644
@@ -18,8 +18,8 @@
 
 import random
 
-
 UINT8 = 0xff
+UINT16 = 0xffff
 UINT32 = 0xffffffff
 UINT64 = 0xffffffffffffffff
 # Most significant bit orders

tests/image-fuzzer/qcow2/fuzz.py UINT64_M = 63 · line 35

Quoted 8 lines
tests/image-fuzzer/qcow2/fuzz.py +2 -0
@@ -28,6 +28,8 @@ 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,

Seeing some pattern in the vectors, but since the types are very few, we can just construct it like this for now.

Quoted 19 lines
tests/image-fuzzer/qcow2/fuzz.py +12 -0
@@ -353,3 +355,15 @@ def l2_entry(current):
     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)
Signature · 1 line
1.9.3
#5 lore raw

PATCH 3/3 layout: Add generators for refcount tbles and blocks

In reply to Maria Kustova

Refcount structures are placed in clusters randomly selected from all not allocated host clusters.

---
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 135 insertions(+), 1 deletion(-)
tests/image-fuzzer/qcow2/layout.py +135 -1
index 730c771..2239789 100644
@@ -102,6 +102,8 @@ class Image(object):
         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)
@@ -113,7 +115,8 @@ class Image(object):
     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.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."""
@@ -330,6 +333,136 @@ class Image(object):
                                                 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 recount 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']
+
+        # Number of refcount entries per refcount block
+        block_size = self.cluster_size / \
+                     (1 << self.header['refcount_order'][0].value - 3)
+        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.
 
@@ -471,6 +604,7 @@ def create_image(test_img_path, backing_file_name=None, backing_file_fmt=None,
     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
Signature · 1 line
1.9.3
#6 lore raw

Re: [Qemu-devel] [PATCH 3/3] layout: Add generators for refcount tbles and blocks

Quoted 2 lines · Maria Kustova

Refcount structures are placed in clusters randomly selected from all not allocated host clusters.

s/not allocated/unallocated/

Quoted 30 lines
---
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 135 insertions(+), 1 deletion(-)
tests/image-fuzzer/qcow2/layout.py +4 -1
index 730c771..2239789 100644
@@ -102,6 +102,8 @@ class Image(object):
         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)
@@ -113,7 +115,8 @@ class Image(object):
     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.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."""

tests/image-fuzzer/qcow2/layout.py class Image(object): · line 339

Quoted 7 lines
tests/image-fuzzer/qcow2/layout.py +4 -0
@@ -330,6 +333,136 @@ class Image(object):
                                                 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 recount blocks."""

s/recount/refcount/

Quoted 66 lines
tests/image-fuzzer/qcow2/layout.py +66 -0
+            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):

tests/image-fuzzer/qcow2/layout.py class Image(object): · line 415

Quoted 10 lines
tests/image-fuzzer/qcow2/layout.py +10 -0
+            """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']
+
+        # Number of refcount entries per refcount block
+        block_size = self.cluster_size / \
+                     (1 << self.header['refcount_order'][0].value - 3)

Why minus 3? Could you use a named constant or a comment?

Fam

Quoted 64 lines
tests/image-fuzzer/qcow2/layout.py +51 -0
+        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.
 
@@ -471,6 +604,7 @@ def create_image(test_img_path, backing_file_name=None, backing_file_fmt=None,
     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
Signature · 1 line
1.9.3
author
#7 lore raw

Re: [Qemu-devel] [PATCH 3/3] layout: Add generators for refcount tbles and blocks

Quoted 116 lines · Fam Zheng
Quoted 2 lines · Maria Kustova

Refcount structures are placed in clusters randomly selected from all not allocated host clusters.

s/not allocated/unallocated/

Quoted 30 lines
---
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 135 insertions(+), 1 deletion(-)
tests/image-fuzzer/qcow2/layout.py +4 -1
index 730c771..2239789 100644
@@ -102,6 +102,8 @@ class Image(object):
         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)
@@ -113,7 +115,8 @@ class Image(object):
     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.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."""

tests/image-fuzzer/qcow2/layout.py class Image(object): · line 339

Quoted 7 lines
tests/image-fuzzer/qcow2/layout.py +4 -0
@@ -330,6 +333,136 @@ class Image(object):
                                                 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 recount blocks."""

s/recount/refcount/

Quoted 70 lines
tests/image-fuzzer/qcow2/layout.py +70 -0
+            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)
Quoted 8 lines

tests/image-fuzzer/qcow2/layout.py class Image(object): · line 415

Quoted 6 lines
tests/image-fuzzer/qcow2/layout.py +6 -0
+            # While snapshots are not supported all refcounts are set to 1
+            return ['>H',entry_offset, 1, 'refcount_block_entry']
+
+        # Number of refcount entries per refcount block
+        block_size = self.cluster_size / \
+                     (1 << self.header['refcount_order'][0].value - 3)

Why minus 3? Could you use a named constant or a comment?

Conversion to bytes. I will make it more descriptive.

Reviewed-by on the v1 series
#8 lore raw
In reply to Maria Kustova
Quoted 12 lines · Maria Kustova

This patch series adds support of refcount tables and blocks to the qcow2 image generator.

This patch series was created for the 'block-next' branch and based on the next series:
[PATCH V3] layout: Reduce number of generator functions in __init__

Maria Kustova (3):
docs: List all image elements currently supported by the fuzzer
fuzz: Add fuzzing functions for entries of refcount table and blocks
layout: Add generators for refcount tbles and blocks

Quoted 8 lines
 docs/image-fuzzer.txt              |   3 +-
 tests/image-fuzzer/qcow2/fuzz.py   |  16 ++++-
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 3 files changed, 152 insertions(+), 3 deletions(-)
Signature · 1 line
1.9.3