[libvirt] [PATCH 2/4] fixup? util: Optimize virBitmapUnion()

[Ján Tomko]

On Fri, May 31, 2019 at 05:22:00PM +0200, Andrea Bolognani wrote:
>The original implementation is extremely straightforward but
>not too efficient, because it uses the public API instead of
>poking the innards directly. This second implementation does
>the latter, and as a consequence can afford to make @b const,
>which is nice even though most existing virBitmap APIs use
>non-const pointers even for read-only bitmaps.
>

>That said, I'm not entirely sure I got it quite right, so a
>review from someone who's well versed in the virBitmap
>internals (*cough* Peter *cough*) would be appreciated, and
>if my implementation passes muster or can be amended through
>review comments I'll gladly squash this commit into the
>previous one.

Yes please. Also drop this paragraph. History is written by the winners
;)

>
>Signed-off-by: Andrea Bolognani <abologna at redhat.com>
>---
> src/util/virbitmap.c | 18 ++++++++++++------
> src/util/virbitmap.h |  2 +-
> 2 files changed, 13 insertions(+), 7 deletions(-)
>
>diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
>index 1f0db563ab..f2127c053d 100644
>--- a/src/util/virbitmap.c
>+++ b/src/util/virbitmap.c
>@@ -1271,17 +1271,23 @@ virBitmapIntersect(virBitmapPtr a,
>  */
> int
> virBitmapUnion(virBitmapPtr a,
>-               virBitmapPtr b)
>+               const virBitmap *b)
> {
>     size_t i;
>+    size_t max;
>
>-    for (i = 0; i < b->nbits; i++) {
>-        if (virBitmapIsBitSet(b, i)) {
>-            if (virBitmapSetBitExpand(a, i) < 0)
>-                return -1;
>-        }
>+    if (a->nbits < b->nbits &&
>+        virBitmapExpand(a, b->nbits) < 0) {

After this, 'b' can hold b->nbits and 'a' can hold b->nbits+1.

if (b->nbits &&
    a->nbits < b->nbits &&
    virBitmapExpand(a, b->nbits -1) < 0) {

>+        return -1;
>     }
>
>+    max = a->map_len;
>+    if (max > b->map_len)
>+        max = b->map_len;

You expanded the 'a' bitmap just a few lines above.
So if you can safely go up to b->map_len without accessing
invalid memory in a or missing any set bits in b.

>+
>+    for (i = 0; i < max; i++)
>+        a->map[i] |= b->map[i];
>+
>     return 0;
> }
>

Reviewed-by: Ján Tomko <jtomko at redhat.com>

Jano
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20190603/951c475d/attachment-0001.sig>