[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [RFC PATCH 30/36] add hierarchical bitmap data type and
From: |
Eric Blake |
Subject: |
Re: [Qemu-devel] [RFC PATCH 30/36] add hierarchical bitmap data type and test cases |
Date: |
Fri, 15 Jun 2012 17:02:37 -0600 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 |
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 fixed.
>
>
> Setting or clearing a range of m bits on all levels, the work to perform
> 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 == 0 && (cur & (BITS_PER_LONG - 1)) == 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 = (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, uint64_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 = g_malloc0(sizeof (struct HBitmap));
> + int i;
> +
> + size = (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 == 32 ? 34 : 41)
Indeed :)
--
Eric Blake address@hidden +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
- [Qemu-devel] [RFC PATCH 29/36] mirror: implement completion, (continued)
- [Qemu-devel] [RFC PATCH 29/36] mirror: implement completion, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 34/36] block: return count of dirty sectors, not chunks, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 33/36] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 26/36] block: live snapshot documentation tweaks, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 35/36] block: allow customizing the granularity of the dirty bitmap, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 36/36] mirror: allow customizing the granularity, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 17/36] block: add bdrv_query_stats, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 30/36] add hierarchical bitmap data type and test cases, Paolo Bonzini, 2012/06/15
- Re: [Qemu-devel] [RFC PATCH 30/36] add hierarchical bitmap data type and test cases,
Eric Blake <=
- [Qemu-devel] [RFC PATCH 18/36] block: make device optional in BlockInfo, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 16/36] block: add bdrv_query_info, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 31/36] block: implement dirty bitmap using HBitmap, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 27/36] block: add bdrv_ensure_backing_file, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 28/36] block: add block-job-complete, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 32/36] block: make round_to_clusters public, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 23/36] qmp: add drive-mirror command, Paolo Bonzini, 2012/06/15
- [Qemu-devel] [RFC PATCH 14/36] stream: add on_error argument, Paolo Bonzini, 2012/06/15