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