[Qemu-devel] [PATCH 0/3] image-fuzzer: Support refcount structures in the qcow2 image generator

[Qemu-devel] [PATCH 0/3] image-fuzzer: Support refcount structures in the qcow2 image generator

[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

 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(-)

-- 
1.9.3

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

[Maria Kustova]

Signed-off-by: Maria Kustova <maria.k@catit.be>
---
 docs/image-fuzzer.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/docs/image-fuzzer.txt b/docs/image-fuzzer.txt
index 0d0005d..f707269 100644
--- a/docs/image-fuzzer.txt
+++ b/docs/image-fuzzer.txt
@@ -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
 -----------------
-- 
1.9.3

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

[Maria Kustova]

Signed-off-by: Maria Kustova <maria.k@catit.be>
---
 tests/image-fuzzer/qcow2/fuzz.py | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/tests/image-fuzzer/qcow2/fuzz.py b/tests/image-fuzzer/qcow2/fuzz.py
index 57527f9..5852b4d 100644
--- a/tests/image-fuzzer/qcow2/fuzz.py
+++ b/tests/image-fuzzer/qcow2/fuzz.py
@@ -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)
-- 
1.9.3

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

[Maria Kustova]

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

Signed-off-by: Maria Kustova <maria.k@catit.be>
---
 tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 135 insertions(+), 1 deletion(-)

diff --git a/tests/image-fuzzer/qcow2/layout.py b/tests/image-fuzzer/qcow2/layout.py
index 730c771..2239789 100644
--- a/tests/image-fuzzer/qcow2/layout.py
+++ b/tests/image-fuzzer/qcow2/layout.py
@@ -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
-- 
1.9.3

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

[Fam Zheng]

On Mon, 08/11 15:55, Maria Kustova wrote:
> Signed-off-by: Maria Kustova <maria.k@catit.be>
> ---
>  docs/image-fuzzer.txt | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/docs/image-fuzzer.txt b/docs/image-fuzzer.txt
> index 0d0005d..f707269 100644
> --- a/docs/image-fuzzer.txt
> +++ b/docs/image-fuzzer.txt
> @@ -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.

Reviewed-by: Fam Zheng <famz@redhat.com>

>  
>  Module interfaces
>  -----------------
> -- 
> 1.9.3
> 

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

[Fam Zheng]

On Mon, 08/11 15:55, Maria Kustova wrote:
> Signed-off-by: Maria Kustova <maria.k@catit.be>
> ---
>  tests/image-fuzzer/qcow2/fuzz.py | 16 +++++++++++++++-
>  1 file changed, 15 insertions(+), 1 deletion(-)
> 
> diff --git a/tests/image-fuzzer/qcow2/fuzz.py b/tests/image-fuzzer/qcow2/fuzz.py
> index 57527f9..5852b4d 100644
> --- a/tests/image-fuzzer/qcow2/fuzz.py
> +++ b/tests/image-fuzzer/qcow2/fuzz.py
> @@ -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,

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

> @@ -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)
> -- 
> 1.9.3
> 

Reviewed-by: Fam Zheng <famz@redhat.com>

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

[Fam Zheng]

On Mon, 08/11 15:55, Maria Kustova wrote:
> Refcount structures are placed in clusters randomly selected from all not
> allocated host clusters.

s/not allocated/unallocated/

> 
> Signed-off-by: Maria Kustova <maria.k@catit.be>
> ---
>  tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
>  1 file changed, 135 insertions(+), 1 deletion(-)
> 
> diff --git a/tests/image-fuzzer/qcow2/layout.py b/tests/image-fuzzer/qcow2/layout.py
> index 730c771..2239789 100644
> --- a/tests/image-fuzzer/qcow2/layout.py
> +++ b/tests/image-fuzzer/qcow2/layout.py
> @@ -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."""

s/recount/refcount/

> +            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)

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

Fam

> +        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
> -- 
> 1.9.3
> 

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

[M.Kustova]

On Tue, Aug 19, 2014 at 1:36 PM, Fam Zheng <famz@redhat.com> wrote:
> On Mon, 08/11 15:55, Maria Kustova wrote:
>> Refcount structures are placed in clusters randomly selected from all not
>> allocated host clusters.
>
> s/not allocated/unallocated/
>
>>
>> Signed-off-by: Maria Kustova <maria.k@catit.be>
>> ---
>>  tests/image-fuzzer/qcow2/layout.py | 136 ++++++++++++++++++++++++++++++++++++-
>>  1 file changed, 135 insertions(+), 1 deletion(-)
>>
>> diff --git a/tests/image-fuzzer/qcow2/layout.py b/tests/image-fuzzer/qcow2/layout.py
>> index 730c771..2239789 100644
>> --- a/tests/image-fuzzer/qcow2/layout.py
>> +++ b/tests/image-fuzzer/qcow2/layout.py
>> @@ -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."""
>
> s/recount/refcount/
>
>> +            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)
>
> Why minus 3? Could you use a named constant or a comment?
   Conversion to bytes. I will make it more descriptive.

Re: [Qemu-devel] [PATCH 0/3] image-fuzzer: Support refcount structures in the qcow2 image generator

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 885 bytes --]

On Mon, Aug 11, 2014 at 03:55:03PM +0400, Maria Kustova wrote:
> 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(-)
> 
> -- 
> 1.9.3
> 

Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]