From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:48676) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yj87S-0001CE-3m for qemu-devel@nongnu.org; Fri, 17 Apr 2015 11:23:51 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yj87Q-0000dX-N5 for qemu-devel@nongnu.org; Fri, 17 Apr 2015 11:23:50 -0400 Message-ID: <5531257E.6090809@redhat.com> Date: Fri, 17 Apr 2015 09:23:42 -0600 From: Eric Blake MIME-Version: 1.0 References: <1428531604-9428-1-git-send-email-jsnow@redhat.com> <1428531604-9428-8-git-send-email-jsnow@redhat.com> In-Reply-To: <1428531604-9428-8-git-send-email-jsnow@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="5SDGhPfrgQHqW2p2KL9HiuPwAkWPRgwDc" Subject: Re: [Qemu-devel] [PATCH v5 07/21] hbitmap: add hbitmap_merge List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: John Snow , qemu-block@nongnu.org Cc: kwolf@redhat.com, famz@redhat.com, qemu-devel@nongnu.org, armbru@redhat.com, vsementsov@parallels.com, stefanha@redhat.com, mreitz@redhat.com This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --5SDGhPfrgQHqW2p2KL9HiuPwAkWPRgwDc Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 04/08/2015 04:19 PM, John Snow wrote: > We add a bitmap merge operation to assist in error cases > where we wish to combine two bitmaps together. >=20 > This is algorithmically O(bits) provided HBITMAP_LEVELS remains > constant. For a full bitmap on a 64bit machine: > sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~=3D 1.01587 * bits >=20 > We may be able to improve running speed for particularly sparse > bitmaps by using iterators, but the running time for dense maps > will be worse. >=20 > We present the simpler solution first, and we can refine it later > if needed. >=20 > Signed-off-by: John Snow > Reviewed-by: Max Reitz > Reviewed-by: Stefan Hajnoczi > --- > /** > + * hbitmap_merge: > + * @a: The bitmap to store the result in. > + * @b: The bitmap to merge into @a. > + * > + * Merge two bitmaps together. > + * A :=3D A (BITOR) B. > + * B is left unmodified. > + */ > +bool hbitmap_merge(HBitmap *a, const HBitmap *b); No mention of what the return value means. > +bool hbitmap_merge(HBitmap *a, const HBitmap *b) > +{ > + int i, j; > + > + if ((a->size !=3D b->size) || (a->granularity !=3D b->granularity)= ) { > + return false; > + } > + > + if (hbitmap_count(b) =3D=3D 0) { > + return true; > + } > + > + /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are = constant. > + * It may be possible to improve running times for sparsely popula= ted maps > + * by using hbitmap_iter_next, but this is suboptimal for dense ma= ps. > + */ > + for (i =3D HBITMAP_LEVELS - 1; i >=3D 0; i--) { > + for (j =3D 0; j < a->sizes[i]; j++) { j is 'int', but a->sizes[i] is uint64_t. If we can ever have a bitmap large enough that its size exceeds 2G at the largest level, then we have an inf-loop due to overflow problem. I'd feel safer if you make j be uint64_t here; but it might also be possible to fix 6/21 to store sizes in a smaller data type along with appropriate assertions that our bitmaps are never big enough to need a level with more than 2G size. --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --5SDGhPfrgQHqW2p2KL9HiuPwAkWPRgwDc Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJVMSV+AAoJEKeha0olJ0NqRlYH/RqDTM62yI74ReBbRj7sJIw3 6eDniGRfgUPkT+eiWU5Oik8lzMrfQzO0dbtUZk1YotkrpncSjI+NqgwRz0T0d83p U4iJb1Ga3tcD5KFA8gIFwNfUz9mEdulqQoCbsnMpAhOeECXIgv6vB1WAIC0pBGBq 6qnbZXSvRVN8Bv6uHg/8zngbwgWGcIoir+2q3aMqdfTAc14X1XvM5CNONu1wixm0 B14Dp90CXE+1rpFx+EO2CDtoAS0on3yBtYTtQGTFVXssBDsx3kwTncWJzHeXsSUB e6DTPn8NoCc3DxWyOaDPoYc/jLzmY5rq6H96YSBve40+q2QgvMyeIp/xM+O0muU= =u/cv -----END PGP SIGNATURE----- --5SDGhPfrgQHqW2p2KL9HiuPwAkWPRgwDc--