From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:39308) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SffXQ-0004MW-DI for qemu-devel@nongnu.org; Fri, 15 Jun 2012 19:02:45 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SffXO-0006Hp-5I for qemu-devel@nongnu.org; Fri, 15 Jun 2012 19:02:43 -0400 Received: from mx1.redhat.com ([209.132.183.28]:1026) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SffXN-0006Hk-TY for qemu-devel@nongnu.org; Fri, 15 Jun 2012 19:02:42 -0400 Message-ID: <4FDBBF0D.5090607@redhat.com> Date: Fri, 15 Jun 2012 17:02:37 -0600 From: Eric Blake MIME-Version: 1.0 References: <1339772759-31004-1-git-send-email-pbonzini@redhat.com> <1339772759-31004-31-git-send-email-pbonzini@redhat.com> In-Reply-To: <1339772759-31004-31-git-send-email-pbonzini@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="------------enig7F8433E2E5CF01C85A62EBA7" Subject: Re: [Qemu-devel] [RFC PATCH 30/36] add hierarchical bitmap data type and test cases List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Paolo Bonzini Cc: kwolf@redhat.com, lcapitulino@redhat.com, qemu-devel@nongnu.org, stefanha@linux.vnet.ibm.com This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig7F8433E2E5CF01C85A62EBA7 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 06/15/2012 09:05 AM, Paolo Bonzini wrote: > HBitmaps provides an array of bits. The bits are stored as usual in an= > array of unsigned longs, but HBitmap is also optimized to provide fast > iteration over set bits; going from one bit to the next is O(log log n)= > worst case, which is low enough that the number of levels is in fact fi= xed. >=20 >=20 > Setting or clearing a range of m bits on all levels, the work to perfor= m > is O(m + m/W + m/W^2 + ...), which in O(m) like on a regular bitmap. s/in/is/ (in commit message and code comment) I made the mistake of starting on the .c before the .h, and my first comments were: > +struct HBitmap { > + uint64_t size; Number of total bits in the bottom level? > + uint64_t count; Number of set bits in the bottom level? > + int granularity; A scaling factor, so that you can iterate over addresses of a sector (512 bytes at a time) instead of having to scale the bit result? [Hint - these names are not self-obvious, so a short comment might help the reader] > + unsigned long *levels[HBITMAP_LEVELS]; and at this point, I decided reading the .h first makes more sense. Also, this is a high-level first-impressions review, not a line-by-line algorithmic accuracy review. Did you invent this yourself, or copy from the ideas from a published work? > +}; > + > +static int64_t hbi_next_internal(HBitmapIter *hbi) > +{ > + > + /* Check for end of iteration. We only use up to > + * BITS_PER_LEVEL bits (actually less) in the level 0 bitmap, > + * and a sentinel is placed in hbitmap_alloc that ends the > + * above loop. Level 0 being the coursest (top, each bit represents that at least one page of level 1 has a set bit), and level n being the finest (each bit representing the actual bitmap? > + */ > + > + if (i =3D=3D 0 && (cur & (BITS_PER_LONG - 1)) =3D=3D 0) { > + return -1; > + } > + for (; i < HBITMAP_LEVELS - 1; i++) { > + /* Find least significant set bit in the word, use them > + * to add back shifted out bits to pos. > + */ > + pos =3D (pos << BITS_PER_LEVEL) + ffsl(cur) - 1; ffsl() is a glibc extension. Do we have a fallback for other platforms? (Only ffs() is POSIX). > + > +/* The recursive workhorse... */ > +static void hb_set_between(HBitmap *hb, int level, uint64_t start, uin= t64_t end) And the recursion is bounded by HBITMAP_LEVELS, which is relatively small, right? > + > +HBitmap *hbitmap_alloc(uint64_t size, int granularity) > +{ > + HBitmap *hb =3D g_malloc0(sizeof (struct HBitmap)); > + int i; > + > + size =3D (size + (1 << granularity) - 1) >> granularity; Doesn't this mean that granularity > 31 or < 0 gives undefined behavior? Should you be validating it for being in range? > + > +/* For 32-bit, the largest that fits in a 4 GiB address space. > + * For 64-bit, the number of sectors in 1 PiB. Good luck, in > + * either case... :) > + */ > +#define HBITMAP_LOG_MAX_SIZE (BITS_PER_LONG =3D=3D 32 ? 34 : 41) Indeed :) --=20 Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --------------enig7F8433E2E5CF01C85A62EBA7 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.4.12 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBCAAGBQJP278NAAoJEKeha0olJ0Nq8IkH/3xLz5L6EB2cmv+2TsQeZLUA 202GXrgDYaY0z3p66QFbo4VJp617Xvxo5WT6Ldweg6Yav9l5dlx/WbcDkELuKCXK TNP2syv+3dKLWhtIl0UVeo+aSBhuXfMqxf/QHQ/WqAw2btW+WplV5lRqmQEMNNaN uXoK0GvtBysM/MYW3nezx7p45jz0DC2L5C4GFQGLM881fM9Aw+wTnF2nDpr8h9xB jrqAFSPyOZ2kn6ici8M6CxZYgBXkR2HDPxs/4+Fg9Caztbs80H/6n5UP9HCPySN+ YGzCV3jp3jpdY0+J/nFlUN1E7KUCSy11BUIn2oax0bN8I5skRj9WeGuyTu27UeE= =JOm2 -----END PGP SIGNATURE----- --------------enig7F8433E2E5CF01C85A62EBA7--