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

[Orit Wasserman]

On 07/04/2012 12:32 AM, Eric Blake wrote:
> On 07/03/2012 07:52 AM, Orit Wasserman wrote:
>> Signed-off-by: Benoit Hudzia <address@hidden>
>> Signed-off-by: Petter Svard <address@hidden>
>> Signed-off-by: Aidan Shribman <address@hidden>
>> Signed-off-by: Orit Wasserman <address@hidden>
> 
>> +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.
decode can only return -1 (invalid) or the decoded len 1 or 2
so maybe you meant I should check that count is bigger than zero?

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