From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:33189) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XrZAA-0005Db-Jq for qemu-devel@nongnu.org; Thu, 20 Nov 2014 16:21:19 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XrZA5-0004Px-Lz for qemu-devel@nongnu.org; Thu, 20 Nov 2014 16:21:14 -0500 Received: from mx1.redhat.com ([209.132.183.28]:58192) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XrZA5-0004Pi-Eh for qemu-devel@nongnu.org; Thu, 20 Nov 2014 16:21:09 -0500 Message-ID: <546E5B3C.20407@redhat.com> Date: Thu, 20 Nov 2014 14:21:00 -0700 From: Eric Blake MIME-Version: 1.0 References: <1415970374-16811-1-git-send-email-mreitz@redhat.com> <1415970374-16811-22-git-send-email-mreitz@redhat.com> <5467682E.1030604@redhat.com> <5469E4C0.8040509@redhat.com> <546BAB8E.3090200@redhat.com> <546C3022.9070701@redhat.com> <546DF4BB.9040302@redhat.com> In-Reply-To: <546DF4BB.9040302@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="sluiixW4hWDs2K57gaX9jBEc30KWxoMON" Subject: Re: [Qemu-devel] [PATCH v2 21/21] iotests: Add test for different refcount widths List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Max Reitz , qemu-devel@nongnu.org Cc: Kevin Wolf , Peter Lieven , Stefan Hajnoczi This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --sluiixW4hWDs2K57gaX9jBEc30KWxoMON Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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 the= n > 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. >=20 > 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). --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --sluiixW4hWDs2K57gaX9jBEc30KWxoMON Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg iQEcBAEBCAAGBQJUbls8AAoJEKeha0olJ0NqmwAH/2+iBkYTjpcGSvszlHav1suR yBVZzDBE9fdpwBLO9NQLkx0SyJlMgiBajjE6SUjjNCbHYlkqNVhZdNdUiWudrOdZ 1ULtqvUQph8chSNE34KrEciqTnzG8K2D0eNfEP+/LtuYgPYbRwq3pURMAYSuJUWy +ey+T6zPkltQP3TWCbTkyMTe5YMthJUul2LqeNaXrjI3V0uuLbo+ec+oojYB72B+ gAKTwqsstXiYe14SkeKVKQQf0uEJpD1GiZpd3egNjJDz+dUSh86TxTi71ub7qs29 lgJRm2jL1diSGGqj00j6/h3AYvnbGjnBkEG6iIkogXgPHaLhKs1Yy2PRQmH/0pM= =fwoF -----END PGP SIGNATURE----- --sluiixW4hWDs2K57gaX9jBEc30KWxoMON--