qemu-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Qemu-devel] [PATCH v5 07/21] hbitmap: add hbitmap_merge


From: John Snow
Subject: Re: [Qemu-devel] [PATCH v5 07/21] hbitmap: add hbitmap_merge
Date: Fri, 17 Apr 2015 17:30:46 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0



On 04/17/2015 11:23 AM, Eric Blake wrote:
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.

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) ~= 1.01587 * bits

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.

We present the simpler solution first, and we can refine it later
if needed.

Signed-off-by: John Snow <address@hidden>
Reviewed-by: Max Reitz <address@hidden>
Reviewed-by: Stefan Hajnoczi <address@hidden>
---

  /**
+ * hbitmap_merge:
+ * @a: The bitmap to store the result in.
+ * @b: The bitmap to merge into @a.
+ *
+ * Merge two bitmaps together.
+ * A := 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 != b->size) || (a->granularity != b->granularity)) {
+        return false;
+    }
+
+    if (hbitmap_count(b) == 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 populated maps
+     * by using hbitmap_iter_next, but this is suboptimal for dense maps.
+     */
+    for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
+        for (j = 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.


Unfortunately, our bitmaps may indeed be colossal. uint32_t would suffice for 32bit, but 64bit bitmaps tolerate up to 2^41 bits, which is still a ULL size of 2^35, so just a little bit too big for us.

We will never hit this in practice (for this usage, anyway) but I'd rather not nerf the base class unnecessarily, so I'll just expand out the index here.

Thanks for the good catch.

--js



reply via email to

[Prev in Thread] Current Thread [Next in Thread]