Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Eric Blake]

On 11/20/2014 06:48 AM, Max Reitz wrote:
> Sounds good, the only problem is that I'd have to hand-craft the image
> myself, because qemu generally uses self-references for refblocks (when
> allocating new refblocks, they will contain their own refcount).
> 
> I think this already would be too much effort (I'll reply to your second
> email right away ;-)). There is no fundamental difference in how new
> allocations for the new reftable and for the new refblocks are treated:
> If there's a new allocation, respin. If that works for the new reftable,
> that's enough to convince me it will work for new refblocks as well.

Agreed - one test of needing a third pass is sufficient to prove we
handle allocations until convergence.


-- 
Eric Blake   eblake redhat com+1-919-301-3266
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Eric Blake]

On 11/20/2014 07:03 AM, Max Reitz wrote:
> Some people may ask why the walks are performed in a loop without a
> fixed limit (because they can't find cases where allocations haven't
> settled at the third pass). But I doubt that'll be a serious problem.
> It's much easier to have such a basically unlimited loop with the
> reasoning "We don't know exactly how many loops it'll take, but it will
> definitely settle at some point in time" than limiting the loop and then
> having to explain why we know exactly that it won't take more than X
> passes. The only problem with not limiting is that we need one walk to
> verify that all allocations have settled. But we need that for the
> common case (two passes) anyway, so that's not an issue.
> 
> The code from this version does not care whether it takes one, two,
> three, four or 42 passes. It's all the same. It will never take one and
> it will probably never take 42 passes; but if it does, well, it will
> work. Therefore, I think testing one non-standard number of passes
> (three) is enough. I'd like to test more, but the effort's just not
> worth it. I think.

Yep, I agree.  I've pretty much convinced myself that the REASON we are
guaranteed that things converge is that each successive iteration
allocates fewer clusters than the one before, and that in later
iterations, refblocks are not fully populated by these fewer allocations
(that is, on recursion, we are allocating geometrically less).

I think I may have found a case that needs four passes.  What if between
the first and second pass, we have enough refblocks to require
allocating 2752 or more contiguous clusters for the new reftable (again
continuing with my 64-bit from 32-bit example, this means at least 1376
contiguous clusters in the old reftable).  That's a huge image already
(176128 refblocks, 11,272,192 clusters, or 5,771,362,304 bytes).  If we
time things so that the first pass ends without spilling the old
reftable (which by now seems fairly tractable to compute how many spare
clusters to start with), then allocating the new reftable will also
spill the old reftable, and based on the reftables alone, will result in
more than 4096 newly-referenced clusters on the second pass (or more
than 64 new refblocks).  This in turn is enough to require another full
refblock just to describe the reftable, but that spills the size of the
new reftable, so between the second and third iteration we now have to
allocate 2753 instead of 2752 contiguous clusters.  And _that_
reallocation is enough for the third pass to have to allocate yet more
clusters.  But like you say, testing this is going to be prohibitively
slow (it's not worth a 5 gigabyte test).

-- 
Eric Blake   eblake redhat com+1-919-301-3266
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-19 at 06:52, Eric Blake wrote:

On 11/18/2014 01:26 PM, Eric Blake wrote:


Now, in response to your question about some other 3-pass inducing
pattern, let's think back to v1, where you questioned what would happen
if a hole in the reftable gets turned into data due to a later
allocation.  Let's see if I can come up with a scenario for that...

Let's stick with a cluster size of 512, and use 32-bit and 64-bit widths
as our two sizes.  If we downsize from 64 to 32 bits, then every two
refblock clusters in the old table results in one call to operation()
for the new table; conversely, if we upsize, then every refblock cluster
in the old table gives two calls to operation() in the new table.  The
trick at hand is to come up with some image where we punch a hole so
that on the first pass, we call operation() with refblock_empty true for
one iteration (necessarily a call later than the first, since the image
header guarantees the first refblock is not empty), but where we have
data after the hole, where it is the later data that triggers the
allocation that will finally start to fill the hole.

How about starting with an image that occupies between 1.5 and 2
refblocks worth of 32-width clusters (so an image anywhere between 193
and 256 clusters, or between 98816 and 131072 bytes).  You should be
able to figure out how many clusters this consumes for L1, L2, plus 1
for header, reftable, and 2 for refblocks, in order to figure out how
many remaining clusters are dedicated to data; ideally, the data
clusters are contiguous, and occupy a swath that covers at least
clusters 126 through 192.  Widening to 64-bit width will require 4
refblocks instead of 2, if all refblocks are needed.  But the whole idea
of punching a hole is that we don't need a refblock if it will be
all-zero entries.  So take this original image, and discard the data
clusters from physical index 126 through 192, (this is NOT the data
visible at guest offset 31744, but whatever actual offset of guest data
that maps to physical offset 31744).  The old reftable now looks like {
refblock_o1 [0-125 occupied, 126 and 127 empty], refblock_o2 [128-191
empty, 192-whatever occupied, tail empty] }.  With no allocations
required, this would in turn would map to the following new refblocks: {
refblock_n1 [0-64 occupied], refblock_n2 [65-125 occupied, 126-127
empty], NULL, refblock_n4 [192-whatever occupied] }.  Note that we do
not need to allocate refblock_n3 because of the hole in the old
refblock; we DO end up allocating three refblocks, but in the sequence
of things, refblock_n1 and refblock_n2 are allocated while we are
visiting refblock_o1 and still fit in refblock_o1, while refblock_n4 is
not allocated until after we have already passed over the first half of
refblock_o2.

Thus, the second walk over the image will see that we need to allocate
refblock_n3 because it now contains entries (in particular, the entry
for refblock_n4, but also the 1-cluster entry for the proposed reftable
that is allocated between the walks).  So, while your test used the
allocation of the reftable as the spillover point, my scenario here uses
the allocation of later refblocks as the spillover point that got missed
during the first iteration.


Oops,...


which means the reftable now looks like { refblock1, NULL, refblock3,
NULL... }; and where refblock1 now has at least two free entries
(possibly three, if the just-freed refblock2 happened to live before
cluster 62).  is we can also free refblock2


...forgot to delete these random thoughts that I typed up but no longer
needed after reworking the above text.

At any rate, I'm not certain we can come up with a four-pass scenario;
if it is even possible, it would be quite complex.


[snip] (But rest assured, I read it all ;-))


At this point, I've spent far too long writing this email.  I haven't
completely ruled out the possibility of a corner case needing four
passes through the do loop, but the image sizes required to get there
are starting to be quite large compared to your simpler test of needing
three passes through the do loop.


Right, see test 026. Without an SSD, it takes more than ten minutes, not 
least because it tests resizing the reftable which means writing a lot 
of data to an image with 512 byte clusters.



I won't be bothered if we call it
good, and quit trying to come up with any other "interesting" allocation
sequencing.


The problem is, in my opinion, that we won't gain a whole lot from 
proving that there are cases where you need a fourth pass and test these 
cases. Fundamentally, they are not different from cases with three 
passes (technically, not even different from two pass cases). You scan 
through the refcounts, you detect that you need refblocks which you have 
not yet allocated, you allocate them, then you respin until all 
allocations are done. The only problem would be whether it'd be possible 
to run into an infinite loop: Can allocating new refblocks lead to a 
case where we have

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-18 at 21:26, Eric Blake wrote:

On 11/17/2014 05:06 AM, Max Reitz wrote:


Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.  It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.

I'm currently thinking about a way to test the old reftable reallocation
issue, and I can't find any. So, for the old reftable to require a
reallocation it must grow. For it to grow we need some allocation beyond
what it can currently represent. For this to happen during the refblock
allocation walk, this allocation must be the allocation of a new refblock.

If the refblock is allocated beyond the current reftable's limit, this
means that either all clusters between free_cluster_index and that point
are already taken. If the reftable is then reallocated, it will
therefore *always* be allocated behind that refblock, which is beyond
its old limit. Therefore, that walk through the old reftable will never
miss that new allocation.

So the issue can only occur if the old reftable is resized after the
walk through it, that is, when allocating the new reftable. That is
indeed an issue but I think it manifests itself basically like the issue
I'm testing here: There is now an area in the old refcount structures
which was free before but has is used now, and the allocation causing
that was the allocation of the new reftable. The only difference is
whether the it's the old or the new reftable that resides in the
previously free area. Thus, I think I'll leave it at this test – but if
you can describe to me how to create an image for a different "rewalk"
path, I'm all ears.

=
The test you wrote does:

original image, pre-walk:
reftable is one cluster; with one refblock and 63 zero entries
  that refblock holds 4096 width-1 refcounts; of those, the first 63 are
non-zero, the remaining are zero. Image is 32256 bytes long

During the first walk, we call operation() 64 times - the first time
with refblock_empty false, the remaining 63 times with refblock_empty true.

after first walk but before reftable allocation, we have allocated one
refblock that holds 64 width-64 refcounts (all zero, because we don't
populate them until the final walk); and the old table now has 64
refcounts populated. Image is 32768 bytes long.

Then we allocating a new reftable; so far, we only created one refblock
for it to hold, so one cluster is sufficient. The allocation causes the
old table to now have 65 refcounts populated. Image is now 33280 bytes long.

On the second pass, we call operation() 64 times; now the first two
walks have refblock_empty as false, which means we allocate a new
refblock.  This allocation causes the old table to now have 66 refcounts
populated. Image is now 33792 bytes long.

So we free our first attempt at a new reftable, and allocate another (a
single cluster is still sufficient to hold two refblocks); I'm not sure
whether this free/realloc will reuse cluster 65 or if it will pick up
cluster 67 and leave a hole in 65.  [I guess it depends on whether
cluster allocation is done by first-fit analysis or whether it blindly
favors allocating at the end of the image].


There is a free_cluster_index to speed up finding the first fit. It's 
reset when freeing clusters before that index, therefore cluster 65 
should be reused.



Either way, we have to do a
third iteration, because the second iteration allocated a refblock and
"reallocated" a reftable.

On the third pass, operation() is still called 64 times, but because the
only two calls with refblock_empty as false already have an allocated
refblock, no further allocations are needed, and we are done with the do
loop; the fourth walk can set refcounts.

=
The test I thought you were writing would start

original image, pre-walk:
reftable is one cluster; with one refblock and 63 zero entries
  that refblock holds 64 width-64 refcounts; of those, the first 63 are
non-zero, the remaining are zero. Image is 32256 bytes long

During the first walk, we call operation() 1 time, with refblock_empty
false.

after first walk but before reftable allocation, we have allocated one
refblock that holds 4096 width-1 refcounts (all zero, because we don't
populate them until the final walk); and the old table now has 64
refcounts populated. Image is 32768 bytes long.

Then we allocating a new reftable; so far, we only created one refblock
for it to hold, so one cluster is sufficient. The allocation causes the
old table to now have 66 refcounts populated (one for the new refblock,
but also one for an additional refblock in th

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Eric Blake]

On 11/18/2014 01:26 PM, Eric Blake wrote:

> Now, in response to your question about some other 3-pass inducing
> pattern, let's think back to v1, where you questioned what would happen
> if a hole in the reftable gets turned into data due to a later
> allocation.  Let's see if I can come up with a scenario for that...
> 
> Let's stick with a cluster size of 512, and use 32-bit and 64-bit widths
> as our two sizes.  If we downsize from 64 to 32 bits, then every two
> refblock clusters in the old table results in one call to operation()
> for the new table; conversely, if we upsize, then every refblock cluster
> in the old table gives two calls to operation() in the new table.  The
> trick at hand is to come up with some image where we punch a hole so
> that on the first pass, we call operation() with refblock_empty true for
> one iteration (necessarily a call later than the first, since the image
> header guarantees the first refblock is not empty), but where we have
> data after the hole, where it is the later data that triggers the
> allocation that will finally start to fill the hole.
> 
> How about starting with an image that occupies between 1.5 and 2
> refblocks worth of 32-width clusters (so an image anywhere between 193
> and 256 clusters, or between 98816 and 131072 bytes).  You should be
> able to figure out how many clusters this consumes for L1, L2, plus 1
> for header, reftable, and 2 for refblocks, in order to figure out how
> many remaining clusters are dedicated to data; ideally, the data
> clusters are contiguous, and occupy a swath that covers at least
> clusters 126 through 192.  Widening to 64-bit width will require 4
> refblocks instead of 2, if all refblocks are needed.  But the whole idea
> of punching a hole is that we don't need a refblock if it will be
> all-zero entries.  So take this original image, and discard the data
> clusters from physical index 126 through 192, (this is NOT the data
> visible at guest offset 31744, but whatever actual offset of guest data
> that maps to physical offset 31744).  The old reftable now looks like {
> refblock_o1 [0-125 occupied, 126 and 127 empty], refblock_o2 [128-191
> empty, 192-whatever occupied, tail empty] }.  With no allocations
> required, this would in turn would map to the following new refblocks: {
> refblock_n1 [0-64 occupied], refblock_n2 [65-125 occupied, 126-127
> empty], NULL, refblock_n4 [192-whatever occupied] }.  Note that we do
> not need to allocate refblock_n3 because of the hole in the old
> refblock; we DO end up allocating three refblocks, but in the sequence
> of things, refblock_n1 and refblock_n2 are allocated while we are
> visiting refblock_o1 and still fit in refblock_o1, while refblock_n4 is
> not allocated until after we have already passed over the first half of
> refblock_o2.
> 
> Thus, the second walk over the image will see that we need to allocate
> refblock_n3 because it now contains entries (in particular, the entry
> for refblock_n4, but also the 1-cluster entry for the proposed reftable
> that is allocated between the walks).  So, while your test used the
> allocation of the reftable as the spillover point, my scenario here uses
> the allocation of later refblocks as the spillover point that got missed
> during the first iteration.
> 

Oops,...

> 
> which means the reftable now looks like { refblock1, NULL, refblock3,
> NULL... }; and where refblock1 now has at least two free entries
> (possibly three, if the just-freed refblock2 happened to live before
> cluster 62).  is we can also free refblock2
> 

...forgot to delete these random thoughts that I typed up but no longer
needed after reworking the above text.

At any rate, I'm not certain we can come up with a four-pass scenario;
if it is even possible, it would be quite complex.  Back in v1, I
questioned what would happen with a completely full reftable, where the
mere allocation of the new reftable causes a spillover not only in the
size of the new reftable, but also to the old.  Let's try to find a
scenario where the reftable does NOT spill on the first pass, but DOES
spill on the second.  A 32-bit width image spills from 1 to 2 clusters
for the reftable at the boundary of 64->65 refblocks (8192->8193
clusters); at that same cluster boundary, the reftable for a 64-bit
width table spills from 2 to 3 clusters.  Furthermore, a 64-bit width
refblock misses an allocation on the first pass if there is a hole of 64
aligned clusters.

First try:

We want an image that has roughly 128 free clusters on the first pass,
including a hole of at least 64 aligned clusters, to where a second pass
is needed to cover the refblock that was treated as a hole on the first
pass.  Furthermore, we want the second pass to completely fill the
image, so that the reftable allocation of 2 clusters after the walk is
the trigger of the spill, then the third pass will allocate another
refblock because of the spill, and a fourth pass is required to ensure
no allocations before th

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Eric Blake]

On 11/17/2014 05:06 AM, Max Reitz wrote:

>> Umm, that sounds backwards from what you document.  It's a good test of
>> the _new_ reftable needing a second round of allocations.  So keep it
>> with corrected comments.  But I think you _intended_ to write a test
>> that starts with a refcount_width=64 image and resize to a
>> refcount_width=1, where the _old_ reftable then suffers a reallocation
>> as part of allocating refblocks for the new table.  It may even help if
>> you add a tracepoint for every iteration through the walk function
>> callback, to prove we are indeed executing it 3 times instead of the
>> usual 2, for these test cases.
> 
> I'm currently thinking about a way to test the old reftable reallocation
> issue, and I can't find any. So, for the old reftable to require a
> reallocation it must grow. For it to grow we need some allocation beyond
> what it can currently represent. For this to happen during the refblock
> allocation walk, this allocation must be the allocation of a new refblock.
> 
> If the refblock is allocated beyond the current reftable's limit, this
> means that either all clusters between free_cluster_index and that point
> are already taken. If the reftable is then reallocated, it will
> therefore *always* be allocated behind that refblock, which is beyond
> its old limit. Therefore, that walk through the old reftable will never
> miss that new allocation.
> 
> So the issue can only occur if the old reftable is resized after the
> walk through it, that is, when allocating the new reftable. That is
> indeed an issue but I think it manifests itself basically like the issue
> I'm testing here: There is now an area in the old refcount structures
> which was free before but has is used now, and the allocation causing
> that was the allocation of the new reftable. The only difference is
> whether the it's the old or the new reftable that resides in the
> previously free area. Thus, I think I'll leave it at this test – but if
> you can describe to me how to create an image for a different "rewalk"
> path, I'm all ears.

=
The test you wrote does:

original image, pre-walk:
reftable is one cluster; with one refblock and 63 zero entries
 that refblock holds 4096 width-1 refcounts; of those, the first 63 are
non-zero, the remaining are zero. Image is 32256 bytes long

During the first walk, we call operation() 64 times - the first time
with refblock_empty false, the remaining 63 times with refblock_empty true.

after first walk but before reftable allocation, we have allocated one
refblock that holds 64 width-64 refcounts (all zero, because we don't
populate them until the final walk); and the old table now has 64
refcounts populated. Image is 32768 bytes long.

Then we allocating a new reftable; so far, we only created one refblock
for it to hold, so one cluster is sufficient. The allocation causes the
old table to now have 65 refcounts populated. Image is now 33280 bytes long.

On the second pass, we call operation() 64 times; now the first two
walks have refblock_empty as false, which means we allocate a new
refblock.  This allocation causes the old table to now have 66 refcounts
populated. Image is now 33792 bytes long.

So we free our first attempt at a new reftable, and allocate another (a
single cluster is still sufficient to hold two refblocks); I'm not sure
whether this free/realloc will reuse cluster 65 or if it will pick up
cluster 67 and leave a hole in 65.  [I guess it depends on whether
cluster allocation is done by first-fit analysis or whether it blindly
favors allocating at the end of the image].  Either way, we have to do a
third iteration, because the second iteration allocated a refblock and
"reallocated" a reftable.

On the third pass, operation() is still called 64 times, but because the
only two calls with refblock_empty as false already have an allocated
refblock, no further allocations are needed, and we are done with the do
loop; the fourth walk can set refcounts.

=
The test I thought you were writing would start

original image, pre-walk:
reftable is one cluster; with one refblock and 63 zero entries
 that refblock holds 64 width-64 refcounts; of those, the first 63 are
non-zero, the remaining are zero. Image is 32256 bytes long

During the first walk, we call operation() 1 time, with refblock_empty
false.

after first walk but before reftable allocation, we have allocated one
refblock that holds 4096 width-1 refcounts (all zero, because we don't
populate them until the final walk); and the old table now has 64
refcounts populated. Image is 32768 bytes long.

Then we allocating a new reftable; so far, we only created one refblock
for it to hold, so one cluster is sufficient. The allocation causes the
old table to now have 66 refcounts populated (one for the new refblock,
but also one for an additional refblock in the old table because the
first refblock was full). Image is now 33792 bytes long.

On the second pass, we call operation() 1 time with 

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-15 at 15:50, Eric Blake wrote:

On 11/14/2014 06:06 AM, Max Reitz wrote:

Add a test for conversion between different refcount widths and errors
specific to certain widths (i.e. snapshots with refcount_width=1).

Signed-off-by: Max Reitz 
---
  tests/qemu-iotests/112 | 252 +
  tests/qemu-iotests/112.out | 131 +++
  tests/qemu-iotests/group   |   1 +
  3 files changed, 384 insertions(+)
  create mode 100755 tests/qemu-iotests/112
  create mode 100644 tests/qemu-iotests/112.out

+echo
+echo '=== Testing too many references for check ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# This cluster should be created at 0x5
+$QEMU_IO -c 'write 0 64k' "$TEST_IMG" | _filter_qemu_io
+# Now make the second L2 entry (the L2 table should be at 0x4) point to 
that
+# cluster, so we have two references
+poke_file "$TEST_IMG" $((0x40008)) "\x80\x00\x00\x00\x00\x05\x00\x00"
+
+# This should say "please use amend"
+_check_test_img -r all
+
+# So we do that
+$QEMU_IMG amend -o refcount_width=2 "$TEST_IMG"
+print_refcount_width
+
+# And try again
+_check_test_img -r all

I think this section also deserves a test that fuzzes an image with
width=64 to intentionally set the most significant bit of one of the
refcounts, and make sure that we gracefully diagnose it as invalid.


+
+echo
+echo '=== Multiple walks necessary during amend ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1,cluster_size=512" _make_test_img 64k
+
+# Cluster 0 is the image header, clusters 1 to 4 are used by the L1 table, a
+# single L2 table, the reftable and a single refblock. This creates 58 data
+# clusters (actually, the L2 table is created here, too), so in total there are
+# then 63 used clusters in the image. With a refcount width of 64, one refblock
+# describes 64 clusters (512 bytes / 64 bits/entry = 64 entries), so this will
+# make the first target refblock have exactly one free entry.
+$QEMU_IO -c "write 0 $((58 * 512))" "$TEST_IMG" | _filter_qemu_io
+
+# Now change the refcount width; since the first target refblock has exactly 
one
+# free entry, that entry will be used to store its own reference. No other
+# refblocks are needed, so then the new reftable will be allocated; since the
+# first target refblock is completely filled up, this will require a new
+# refblock which is why the refcount width changing function will need to run
+# through everything one more time until the allocations are stable.
+$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
+print_refcount_width

Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.  It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.


I'm currently thinking about a way to test the old reftable reallocation 
issue, and I can't find any. So, for the old reftable to require a 
reallocation it must grow. For it to grow we need some allocation beyond 
what it can currently represent. For this to happen during the refblock 
allocation walk, this allocation must be the allocation of a new refblock.


If the refblock is allocated beyond the current reftable's limit, this 
means that either all clusters between free_cluster_index and that point 
are already taken. If the reftable is then reallocated, it will 
therefore *always* be allocated behind that refblock, which is beyond 
its old limit. Therefore, that walk through the old reftable will never 
miss that new allocation.


So the issue can only occur if the old reftable is resized after the 
walk through it, that is, when allocating the new reftable. That is 
indeed an issue but I think it manifests itself basically like the issue 
I'm testing here: There is now an area in the old refcount structures 
which was free before but has is used now, and the allocation causing 
that was the allocation of the new reftable. The only difference is 
whether the it's the old or the new reftable that resides in the 
previously free area. Thus, I think I'll leave it at this test – but if 
you can describe to me how to create an image for a different "rewalk" 
path, I'm all ears.


Max

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-17 at 11:38, Max Reitz wrote:

On 2014-11-17 at 09:34, Max Reitz wrote:

On 2014-11-15 at 15:50, Eric Blake wrote:

On 11/14/2014 06:06 AM, Max Reitz wrote:

Add a test for conversion between different refcount widths and errors
specific to certain widths (i.e. snapshots with refcount_width=1).

Signed-off-by: Max Reitz 
---
  tests/qemu-iotests/112 | 252 
+

  tests/qemu-iotests/112.out | 131 +++
  tests/qemu-iotests/group   |   1 +
  3 files changed, 384 insertions(+)
  create mode 100755 tests/qemu-iotests/112
  create mode 100644 tests/qemu-iotests/112.out

+echo
+echo '=== Testing too many references for check ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# This cluster should be created at 0x5
+$QEMU_IO -c 'write 0 64k' "$TEST_IMG" | _filter_qemu_io
+# Now make the second L2 entry (the L2 table should be at 0x4) 
point to that

+# cluster, so we have two references
+poke_file "$TEST_IMG" $((0x40008)) "\x80\x00\x00\x00\x00\x05\x00\x00"
+
+# This should say "please use amend"
+_check_test_img -r all
+
+# So we do that
+$QEMU_IMG amend -o refcount_width=2 "$TEST_IMG"
+print_refcount_width
+
+# And try again
+_check_test_img -r all

I think this section also deserves a test that fuzzes an image with
width=64 to intentionally set the most significant bit of one of the
refcounts, and make sure that we gracefully diagnose it as invalid.


+
+echo
+echo '=== Multiple walks necessary during amend ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1,cluster_size=512" 
_make_test_img 64k

+
+# Cluster 0 is the image header, clusters 1 to 4 are used by the 
L1 table, a
+# single L2 table, the reftable and a single refblock. This 
creates 58 data
+# clusters (actually, the L2 table is created here, too), so in 
total there are
+# then 63 used clusters in the image. With a refcount width of 64, 
one refblock
+# describes 64 clusters (512 bytes / 64 bits/entry = 64 entries), 
so this will

+# make the first target refblock have exactly one free entry.
+$QEMU_IO -c "write 0 $((58 * 512))" "$TEST_IMG" | _filter_qemu_io
+
+# Now change the refcount width; since the first target refblock 
has exactly one
+# free entry, that entry will be used to store its own reference. 
No other
+# refblocks are needed, so then the new reftable will be 
allocated; since the
+# first target refblock is completely filled up, this will require 
a new
+# refblock which is why the refcount width changing function will 
need to run

+# through everything one more time until the allocations are stable.
+$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
+print_refcount_width

Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.


That's what you intended, but that's harder to test, so I settled for 
this (and the comments are appropriate (note that "target refblock" 
refers to the refblocks after amendment); note that this does indeed 
fail with v1 of this series.



It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.


That's a good idea! I thought about adding some info, but totally 
forgot about trace points.


...On second thought, trace doesn't work so well with qemu-img. My 
best bet would be blkdebug, but that seems kind of ugly to me...


Problem "solved": If there will be more walks than originally thought 
(3+1 instead of 2+1), progress will regress at one point. I'll just grep 
for that point and that should be enough (progress jumping from 66.67 % 
to 50.00 %).


Max

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-17 at 09:34, Max Reitz wrote:

On 2014-11-15 at 15:50, Eric Blake wrote:

On 11/14/2014 06:06 AM, Max Reitz wrote:

Add a test for conversion between different refcount widths and errors
specific to certain widths (i.e. snapshots with refcount_width=1).

Signed-off-by: Max Reitz 
---
  tests/qemu-iotests/112 | 252 
+

  tests/qemu-iotests/112.out | 131 +++
  tests/qemu-iotests/group   |   1 +
  3 files changed, 384 insertions(+)
  create mode 100755 tests/qemu-iotests/112
  create mode 100644 tests/qemu-iotests/112.out

+echo
+echo '=== Testing too many references for check ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# This cluster should be created at 0x5
+$QEMU_IO -c 'write 0 64k' "$TEST_IMG" | _filter_qemu_io
+# Now make the second L2 entry (the L2 table should be at 0x4) 
point to that

+# cluster, so we have two references
+poke_file "$TEST_IMG" $((0x40008)) "\x80\x00\x00\x00\x00\x05\x00\x00"
+
+# This should say "please use amend"
+_check_test_img -r all
+
+# So we do that
+$QEMU_IMG amend -o refcount_width=2 "$TEST_IMG"
+print_refcount_width
+
+# And try again
+_check_test_img -r all

I think this section also deserves a test that fuzzes an image with
width=64 to intentionally set the most significant bit of one of the
refcounts, and make sure that we gracefully diagnose it as invalid.


+
+echo
+echo '=== Multiple walks necessary during amend ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1,cluster_size=512" _make_test_img 
64k

+
+# Cluster 0 is the image header, clusters 1 to 4 are used by the L1 
table, a
+# single L2 table, the reftable and a single refblock. This creates 
58 data
+# clusters (actually, the L2 table is created here, too), so in 
total there are
+# then 63 used clusters in the image. With a refcount width of 64, 
one refblock
+# describes 64 clusters (512 bytes / 64 bits/entry = 64 entries), 
so this will

+# make the first target refblock have exactly one free entry.
+$QEMU_IO -c "write 0 $((58 * 512))" "$TEST_IMG" | _filter_qemu_io
+
+# Now change the refcount width; since the first target refblock 
has exactly one
+# free entry, that entry will be used to store its own reference. 
No other
+# refblocks are needed, so then the new reftable will be allocated; 
since the
+# first target refblock is completely filled up, this will require 
a new
+# refblock which is why the refcount width changing function will 
need to run

+# through everything one more time until the allocations are stable.
+$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
+print_refcount_width

Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.


That's what you intended, but that's harder to test, so I settled for 
this (and the comments are appropriate (note that "target refblock" 
refers to the refblocks after amendment); note that this does indeed 
fail with v1 of this series.



It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.


That's a good idea! I thought about adding some info, but totally 
forgot about trace points.


...On second thought, trace doesn't work so well with qemu-img. My best 
bet would be blkdebug, but that seems kind of ugly to me...


Max

I'll see whether I can add a test for increasing the size of the 
original reftable during amendment, too.


Max

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

On 2014-11-15 at 15:50, Eric Blake wrote:

On 11/14/2014 06:06 AM, Max Reitz wrote:

Add a test for conversion between different refcount widths and errors
specific to certain widths (i.e. snapshots with refcount_width=1).

Signed-off-by: Max Reitz 
---
  tests/qemu-iotests/112 | 252 +
  tests/qemu-iotests/112.out | 131 +++
  tests/qemu-iotests/group   |   1 +
  3 files changed, 384 insertions(+)
  create mode 100755 tests/qemu-iotests/112
  create mode 100644 tests/qemu-iotests/112.out

+echo
+echo '=== Testing too many references for check ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# This cluster should be created at 0x5
+$QEMU_IO -c 'write 0 64k' "$TEST_IMG" | _filter_qemu_io
+# Now make the second L2 entry (the L2 table should be at 0x4) point to 
that
+# cluster, so we have two references
+poke_file "$TEST_IMG" $((0x40008)) "\x80\x00\x00\x00\x00\x05\x00\x00"
+
+# This should say "please use amend"
+_check_test_img -r all
+
+# So we do that
+$QEMU_IMG amend -o refcount_width=2 "$TEST_IMG"
+print_refcount_width
+
+# And try again
+_check_test_img -r all

I think this section also deserves a test that fuzzes an image with
width=64 to intentionally set the most significant bit of one of the
refcounts, and make sure that we gracefully diagnose it as invalid.


+
+echo
+echo '=== Multiple walks necessary during amend ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1,cluster_size=512" _make_test_img 64k
+
+# Cluster 0 is the image header, clusters 1 to 4 are used by the L1 table, a
+# single L2 table, the reftable and a single refblock. This creates 58 data
+# clusters (actually, the L2 table is created here, too), so in total there are
+# then 63 used clusters in the image. With a refcount width of 64, one refblock
+# describes 64 clusters (512 bytes / 64 bits/entry = 64 entries), so this will
+# make the first target refblock have exactly one free entry.
+$QEMU_IO -c "write 0 $((58 * 512))" "$TEST_IMG" | _filter_qemu_io
+
+# Now change the refcount width; since the first target refblock has exactly 
one
+# free entry, that entry will be used to store its own reference. No other
+# refblocks are needed, so then the new reftable will be allocated; since the
+# first target refblock is completely filled up, this will require a new
+# refblock which is why the refcount width changing function will need to run
+# through everything one more time until the allocations are stable.
+$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
+print_refcount_width

Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.


That's what you intended, but that's harder to test, so I settled for 
this (and the comments are appropriate (note that "target refblock" 
refers to the refblocks after amendment); note that this does indeed 
fail with v1 of this series.



It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.


That's a good idea! I thought about adding some info, but totally forgot 
about trace points.


I'll see whether I can add a test for increasing the size of the 
original reftable during amendment, too.


Max

Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Eric Blake]

On 11/14/2014 06:06 AM, Max Reitz wrote:
> Add a test for conversion between different refcount widths and errors
> specific to certain widths (i.e. snapshots with refcount_width=1).
> 
> Signed-off-by: Max Reitz 
> ---
>  tests/qemu-iotests/112 | 252 
> +
>  tests/qemu-iotests/112.out | 131 +++
>  tests/qemu-iotests/group   |   1 +
>  3 files changed, 384 insertions(+)
>  create mode 100755 tests/qemu-iotests/112
>  create mode 100644 tests/qemu-iotests/112.out
> 
> +echo
> +echo '=== Testing too many references for check ==='
> +echo
> +
> +IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
> +print_refcount_width
> +
> +# This cluster should be created at 0x5
> +$QEMU_IO -c 'write 0 64k' "$TEST_IMG" | _filter_qemu_io
> +# Now make the second L2 entry (the L2 table should be at 0x4) point to 
> that
> +# cluster, so we have two references
> +poke_file "$TEST_IMG" $((0x40008)) "\x80\x00\x00\x00\x00\x05\x00\x00"
> +
> +# This should say "please use amend"
> +_check_test_img -r all
> +
> +# So we do that
> +$QEMU_IMG amend -o refcount_width=2 "$TEST_IMG"
> +print_refcount_width
> +
> +# And try again
> +_check_test_img -r all

I think this section also deserves a test that fuzzes an image with
width=64 to intentionally set the most significant bit of one of the
refcounts, and make sure that we gracefully diagnose it as invalid.

> +
> +echo
> +echo '=== Multiple walks necessary during amend ==='
> +echo
> +
> +IMGOPTS="$IMGOPTS,refcount_width=1,cluster_size=512" _make_test_img 64k
> +
> +# Cluster 0 is the image header, clusters 1 to 4 are used by the L1 table, a
> +# single L2 table, the reftable and a single refblock. This creates 58 data
> +# clusters (actually, the L2 table is created here, too), so in total there 
> are
> +# then 63 used clusters in the image. With a refcount width of 64, one 
> refblock
> +# describes 64 clusters (512 bytes / 64 bits/entry = 64 entries), so this 
> will
> +# make the first target refblock have exactly one free entry.
> +$QEMU_IO -c "write 0 $((58 * 512))" "$TEST_IMG" | _filter_qemu_io
> +
> +# Now change the refcount width; since the first target refblock has exactly 
> one
> +# free entry, that entry will be used to store its own reference. No other
> +# refblocks are needed, so then the new reftable will be allocated; since the
> +# first target refblock is completely filled up, this will require a new
> +# refblock which is why the refcount width changing function will need to run
> +# through everything one more time until the allocations are stable.
> +$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
> +print_refcount_width

Umm, that sounds backwards from what you document.  It's a good test of
the _new_ reftable needing a second round of allocations.  So keep it
with corrected comments.  But I think you _intended_ to write a test
that starts with a refcount_width=64 image and resize to a
refcount_width=1, where the _old_ reftable then suffers a reallocation
as part of allocating refblocks for the new table.  It may even help if
you add a tracepoint for every iteration through the walk function
callback, to prove we are indeed executing it 3 times instead of the
usual 2, for these test cases.

-- 
Eric Blake   eblake redhat com+1-919-301-3266
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature

[Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths

[Max Reitz]

Add a test for conversion between different refcount widths and errors
specific to certain widths (i.e. snapshots with refcount_width=1).

Signed-off-by: Max Reitz 
---
 tests/qemu-iotests/112 | 252 +
 tests/qemu-iotests/112.out | 131 +++
 tests/qemu-iotests/group   |   1 +
 3 files changed, 384 insertions(+)
 create mode 100755 tests/qemu-iotests/112
 create mode 100644 tests/qemu-iotests/112.out

diff --git a/tests/qemu-iotests/112 b/tests/qemu-iotests/112
new file mode 100755
index 000..e824d8a
--- /dev/null
+++ b/tests/qemu-iotests/112
@@ -0,0 +1,252 @@
+#!/bin/bash
+#
+# Test cases for different refcount_widths
+#
+# Copyright (C) 2014 Red Hat, Inc.
+#
+# 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 .
+#
+
+# creator
+owner=mre...@redhat.com
+
+seq="$(basename $0)"
+echo "QA output created by $seq"
+
+here="$PWD"
+tmp=/tmp/$$
+status=1   # failure is the default!
+
+_cleanup()
+{
+   _cleanup_test_img
+}
+trap "_cleanup; exit \$status" 0 1 2 3 15
+
+# get standard environment, filters and checks
+. ./common.rc
+. ./common.filter
+
+# This tests qcow2-specific low-level functionality
+_supported_fmt qcow2
+_supported_proto file
+_supported_os Linux
+# This test will set refcount_width on its own which would conflict with the
+# manual setting; compat will be overridden as well
+_unsupported_imgopts refcount_width 'compat=0.10'
+
+function print_refcount_width()
+{
+$QEMU_IMG info "$TEST_IMG" | sed -n '/refcount width:/ s/^ *//p'
+}
+
+echo
+echo '=== refcount_width limits ==='
+echo
+
+# Must be positive (non-zero)
+IMGOPTS="$IMGOPTS,refcount_width=0" _make_test_img 64M
+# Must be positive (non-negative)
+IMGOPTS="$IMGOPTS,refcount_width=-1" _make_test_img 64M
+# May not exceed 64
+IMGOPTS="$IMGOPTS,refcount_width=128" _make_test_img 64M
+# Must be a power of two
+IMGOPTS="$IMGOPTS,refcount_width=42" _make_test_img 64M
+
+# 1 is the minimum
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# 64 is the maximum
+IMGOPTS="$IMGOPTS,refcount_width=64" _make_test_img 64M
+print_refcount_width
+
+# 16 is the default
+_make_test_img 64M
+print_refcount_width
+
+echo
+echo '=== refcount_width and compat=0.10 ==='
+echo
+
+# Should work
+IMGOPTS="$IMGOPTS,compat=0.10,refcount_width=16" _make_test_img 64M
+print_refcount_width
+
+# Should not work
+IMGOPTS="$IMGOPTS,compat=0.10,refcount_width=1" _make_test_img 64M
+IMGOPTS="$IMGOPTS,compat=0.10,refcount_width=64" _make_test_img 64M
+
+
+echo
+echo '=== Snapshot limit on refcount_width=1 ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+$QEMU_IO -c 'write 0 512' "$TEST_IMG" | _filter_qemu_io
+
+# Should fail for now; in the future, this might be supported by automatically
+# copying all clusters with overflowing refcount
+$QEMU_IMG snapshot -c foo "$TEST_IMG"
+
+# The new L1 table could/should be leaked
+_check_test_img
+
+echo
+echo '=== Snapshot limit on refcount_width=2 ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=2" _make_test_img 64M
+print_refcount_width
+
+$QEMU_IO -c 'write 0 512' "$TEST_IMG" | _filter_qemu_io
+
+# Should succeed
+$QEMU_IMG snapshot -c foo "$TEST_IMG"
+$QEMU_IMG snapshot -c bar "$TEST_IMG"
+# Should fail (4th reference)
+$QEMU_IMG snapshot -c baz "$TEST_IMG"
+
+# The new L1 table could/should be leaked
+_check_test_img
+
+echo
+echo '=== Compressed clusters with refcount_width=1 ==='
+echo
+
+IMGOPTS="$IMGOPTS,refcount_width=1" _make_test_img 64M
+print_refcount_width
+
+# Both should fit into a single host cluster; instead of failing to increase 
the
+# refcount of that cluster, qemu should just allocate a new cluster and make
+# this operation succeed
+$QEMU_IO -c 'write -P 0 -c  0  64k' \
+ -c 'write -P 1 -c 64k 64k' \
+ "$TEST_IMG" | _filter_qemu_io
+
+_check_test_img
+
+echo
+echo '=== Amend from refcount_width=16 to refcount_width=1 ==='
+echo
+
+_make_test_img 64M
+print_refcount_width
+
+$QEMU_IO -c 'write 16M 32M' "$TEST_IMG" | _filter_qemu_io
+$QEMU_IMG amend -o refcount_width=1 "$TEST_IMG"
+_check_test_img
+print_refcount_width
+
+echo
+echo '=== Amend from refcount_width=1 to refcount_width=64 ==='
+echo
+
+$QEMU_IMG amend -o refcount_width=64 "$TEST_IMG"
+_check_test_img
+print_refcount_width
+
+echo
+echo '=== Amend to compat=0.10 ==='
+echo
+
+# Should not work becau