[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_d
From: |
Eric Blake |
Subject: |
Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions |
Date: |
Tue, 03 Jul 2012 15:32:08 -0600 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 |
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.
> + 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 address@hidden +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
- Re: [Qemu-devel] [PATCH v14 07/13] Add debugging infrastructure, (continued)
- [Qemu-devel] [PATCH v14 06/13] Add save_block_hdr function, Orit Wasserman, 2012/07/03
- [Qemu-devel] [PATCH v14 01/13] Add MigrationParams structure, Orit Wasserman, 2012/07/03
- [Qemu-devel] [PATCH v14 08/13] Change ram_save_block to return -1 if there are no more changes, Orit Wasserman, 2012/07/03
- [Qemu-devel] [PATCH v14 04/13] Add cache handling functions, Orit Wasserman, 2012/07/03
- Re: [Qemu-devel] [PATCH v14 04/13] Add cache handling functions, Eric Blake, 2012/07/03
- [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions, Orit Wasserman, 2012/07/03
- Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions,
Eric Blake <=
- Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions, Orit Wasserman, 2012/07/04
- Re: [Qemu-devel] [PATCH v14 10/13] Add xbzrle_encode_buffer and xbzrle_decode_buffer functions, Eric Blake, 2012/07/04
[Qemu-devel] [PATCH v14 05/13] Add uleb encoding/decoding functions, Orit Wasserman, 2012/07/03
[Qemu-devel] [PATCH v14 11/13] Add XBZRLE to ram_save_block and ram_save_live, Orit Wasserman, 2012/07/03
[Qemu-devel] [PATCH v14 02/13] Add migration capabilities, Orit Wasserman, 2012/07/03