Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions

[Eric Blake <eblake@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 8585 bytes --]

On 07/03/2012 07:52 AM, Orit Wasserman wrote:
> Signed-off-by: Benoit Hudzia <benoit.hudzia@sap.com>
> Signed-off-by: Petter Svard <petters@cs.umu.se>
> Signed-off-by: Aidan Shribman <aidan.shribman@sap.com>
> Signed-off-by: Orit Wasserman <owasserm@redhat.com>

> +int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
> +                         uint8_t *dst, int dlen)
> +{
> +    uint32_t zrun_len = 0, nzrun_len = 0;
> +    int d = 0, i = 0, start;
> +    long res, xor;
> +    uint8_t *nzrun_start = NULL;
> +
> +    g_assert(!((uintptr_t)old_buf & (sizeof(long) - 1)) &&
> +             !((uintptr_t)new_buf & (sizeof(long) - 1)) &&
> +             !(slen & (sizeof(long) - 1)));

I know I suggested this in v13, so now I'm bike-shedding my own review,
but I think it might be a bit more legible as:

g_assert(!(((uintptr_t)old_buf) | ((uintptr_t)new_buf) | slen) &
           (sizeof(long) - 1)));

> +
> +    while (i < slen) {
> +        /* overflow */
> +        if (d + 2 > dlen) {
> +            return -1;
> +        }
> +
> +        /* not aligned to sizeof(long) */
> +        res = (slen - i) % sizeof(long);
> +        if (res) {
> +            start = i;
> +            while (!(old_buf[i] ^ new_buf[i]) && (i - start) <= res) {
> +                zrun_len++;
> +                i++;
> +            }
> +        }

I'm not sure why you need 'start'; this same block will do the same
amount of computation with less typing and register pressure:

res = (slen - i) % sizeof(long);
while (res && old_buf[i] == new_buf[i]) {
    zrun_len++;
    i++;
    res--;
}

> +
> +        if (zrun_len == res) {

If you use my above rewrite, then this condition changes to:

if (!res) {

> +            while (i <= (slen - sizeof(long)) &&

I'd shorten this to:

while (i < slen &&

> +                   (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
> +                i += sizeof(long);
> +                zrun_len += sizeof(long);
> +            }
> +
> +            /* go over the rest */
> +            while (old_buf[i] == new_buf[i] && ++i <= slen) {

Buffer overrun: if the page ends on a zrun, then at this point, i ==
slen, and old_buf[i] is now pointing one past the end of the array.  You
need to swap the conditions, and only increment 'i' inside the {}, as in:

while (i < slen && old_buf[i] == new_buf[i]) {
    i++;

> +                zrun_len++;
> +            }
> +        }
> +
> +        /* buffer unchanged */
> +        if (zrun_len == slen) {
> +            return 0;
> +        }
> +
> +        /* skip last zero run */
> +        if (i == slen + 1) {

Buffer overrun.  The loop should terminate at 'i == slen', not at 'i ==
slen + 1', since old_buf[slen - 1] is the last addressable byte.

> +            return d;
> +        }
> +
> +        d += uleb128_encode_small(dst + d, zrun_len);
> +
> +        /* no nzrun */
> +        if (i == slen) {
> +            return d;
> +        }

This is the correct code but repeats the intent of what you were trying
just before the uleb128_encode_small().

> +
> +        zrun_len = 0;
> +        nzrun_start = new_buf + i;

Missing an overflow check here.  If there are fewer than 2 bytes before
we hit dlen, then there is no way that we can fit in an nzrun, so we
might as well quit here.

> +
> +        /* not aligned to sizeof(long) */
> +        res = (slen - i) % sizeof(long);
> +        if (res) {
> +            start = i;
> +            while (old_buf[i] != new_buf[i] && i - start < res) {
> +                i++;
> +                nzrun_len++;
> +            }
> +        }

Again, you can exploit the fact that slen is aligned, and shorten to:

res = (slen - i) % sizeof(long);
while (res && old_bf[i] != new_buf[i]) {
    i++;
    nzrun_len++;
    res--;
}

> +
> +        if (nzrun_len == res) {

and this would change to:

if (!res) {

> +            /* truncation to 32-bit long okay */
> +            long mask = 0x0101010101010101ULL;
> +            xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);
> +            printf("cont\n");

Stray debugging comment.

> +            while (i <= (slen - sizeof(long))) {

shorter to write as:

while (i < slen) {

> +                if ((xor - mask) & ~xor & (mask << 7)) {
> +                    /* found the end of an nzrun within the current long */
> +                    while (old_buf[i] != new_buf[i] && ++i <= slen) {

No need to compare against slen here, since the outer while guarantees
that.  You can simplify to:

while (old_buf[i] != new_buf[i]) {
    i++;

> +                        nzrun_len++;
> +                    }
> +                    break;
> +                } else {
> +                    i += sizeof(long);
> +                    nzrun_len += sizeof(long);
> +                    xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);
> +                }
> +            }
> +

At this point, you are guaranteed to have found the end of the nzrun
(either you found two equal bytes, or you hit slen), which means...

> +            while (old_buf[i] != new_buf[i] && ++i <= slen) {
> +                nzrun_len++;
> +            }

this while loop is dead code.  Furthermore, this while loop is a
potential out-of-bounds-read (remember, old_buf[slen] is not valid
memory), so nuking it is the way to go.

> +        }
> +
> +        /* overflow */
> +        if (d + nzrun_len + 2 > dlen) {
> +            return -1;

There is a corner case where this reports overflow even when there was
none - that is when the old_buf ends in an nzrun of 0x7f bytes or less,
so the encoding occupies only 1 byte, and the encoded version would
still fit in dlen.  I think you want to defer your overflow checking
until after...

> +        }
> +
> +        d += uleb128_encode_small(dst + d, nzrun_len);

...you know the encoded size.  But that only works if you made sure
earlier that there was room to encode nzrun_len (up to 2 bytes) in the
first place.

> +        memcpy(dst + d, nzrun_start, nzrun_len);
> +        d += nzrun_len;
> +        nzrun_len = 0;
> +    }
> +
> +    return d;
> +}
> +

Do you have any unit tests that pass in various inputs and compare
against expected outputs?

> +int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
> +{
> +    int i = 0, d = 0;
> +    int ret;
> +    uint32_t count = 0;
> +
> +    while (i < slen) {
> +
> +        /* zrun */
> +        if ((slen - i) < 2 && *(src + i) & 0x80) {
> +            return -1;
> +        }

You can simplify this - the protocol demands an nzrun after every zrun,
which means at this point in the decode, there must be at least 3 bytes
to be valid.  It's simpler to write:

if (slen - i < 2) {
    return -1;
}

> +
> +        ret = uleb128_decode_small(src + i, &count);
> +        if (ret < 0) {
> +            return -1;
> +        }

I'd also add a check that we only ever get a zero-length zrun at the
start of a buffer (anywhere else, a zero-length zrun is invalid); as in:

if (!count && i) {
    return -1;
}

> +        i += ret;
> +        d += count;
> +
> +        /* overflow */
> +        if (d > dlen) {
> +            return -1;
> +        }
> +
> +        /* completed decoding */

No, if we got here, then we were handed an invalid stream.  Remember,
the protocol says that every zrun must be followed by an nzrun.

> +        if (i == slen - 1) {
> +            return d;
> +        }
> +
> +        /* nzrun */
> +        if ((slen - i) < 2 && *(src + i) & 0x80) {
> +            return -1;
> +        }

Again, a valid nzrun is at least 2 bytes, so no need to worry about the
contents of *src, it is sufficient to check:

if (slen - i < 2) {
    return -1;
}

> +        ret = uleb128_decode_small(src + i, &count);
> +        if (ret < 0) {

An nzrun should be a non-zero value; I'd write this as (ret <= 0) to
rule out an attempt to pass a zero-length nzrun.

> +            return -1;
> +        }
> +        i += ret;
> +
> +        /* overflow */
> +        if (d + count > dlen) {
> +            return -1;
> +        }
> +
> +        memcpy(dst + d , src + i, count);
> +        d += count;
> +        i += count;
> +    }
> +
> +    return d;
> +}
> 

-- 
Eric Blake   eblake@redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org




[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 620 bytes --]