| Message ID | 1341492709-13897-7-git-send-email-owasserm@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 07/05/2012 06:51 AM, Orit Wasserman wrote: This commit message is a bit sparse. I'd document at least the fact that our nzrun detection code in xbzrle_encode_buffer borrows long-word-at-a-time NUL-detection tricks from strcmp(), as it is not an intuitive trick known by all developers. > 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> I think I touched this one heavily enough that it warrants adding: Signed-off-by: Eric Blake <eblake@redhat.com> Other than the commit message, I'm happy with this patch contents now. Still some nits, though: > + > + /* not aligned to sizeof(long) */ > + res = (slen - i) % sizeof(long); Comment indentation is off. > + while (res && old_buf[i] == new_buf[i]) { > + zrun_len++; > + i++; > + res--; > + } > + > + if (!res) { A comment here might help: /* word at a time for speed */ > + while (i < slen && > + (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { On re-reading this, I'm worried whether it violates strict C99 aliasing rules; I'm hoping the compiler doesn't mis-optimize it based on a loophole of us using questionable semantics. In practice, I'm confident that we are only doing aligned reads (otherwise I wouldn't have suggested this line in the first place), which is why I'm personally okay with it even if it technically violates C99. However, I'm open to suggestions from anyone else on the list on how to better express the notion of intentionally accessing a long at a time from an aligned offset into a byte array, if that will help us avoid even theoretical problems. > + nzrun_len++; > + res--; > + } > + > + if (!res) { > + /* truncation to 32-bit long okay */ Again, a longer comment might help: /* word at a time for speed, use of 32-bit long okay */ > + long mask = 0x0101010101010101ULL; > + while (i < slen) { > + xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i); Same potential strict aliasing problems as for zrun detection.
On 07/05/2012 04:55 PM, Eric Blake wrote: > On 07/05/2012 06:51 AM, Orit Wasserman wrote: > > This commit message is a bit sparse. I'd document at least the fact > that our nzrun detection code in xbzrle_encode_buffer borrows > long-word-at-a-time NUL-detection tricks from strcmp(), as it is not an > intuitive trick known by all developers. > >> 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> > > I think I touched this one heavily enough that it warrants adding: > > Signed-off-by: Eric Blake <eblake@redhat.com> > Of course Orit > Other than the commit message, I'm happy with this patch contents now. > Still some nits, though: > >> + >> + /* not aligned to sizeof(long) */ >> + res = (slen - i) % sizeof(long); > > Comment indentation is off. > >> + while (res && old_buf[i] == new_buf[i]) { >> + zrun_len++; >> + i++; >> + res--; >> + } >> + >> + if (!res) { > > A comment here might help: > > /* word at a time for speed */ > >> + while (i < slen && >> + (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { > > On re-reading this, I'm worried whether it violates strict C99 aliasing > rules; I'm hoping the compiler doesn't mis-optimize it based on a > loophole of us using questionable semantics. In practice, I'm confident > that we are only doing aligned reads (otherwise I wouldn't have > suggested this line in the first place), which is why I'm personally > okay with it even if it technically violates C99. However, I'm open to > suggestions from anyone else on the list on how to better express the > notion of intentionally accessing a long at a time from an aligned > offset into a byte array, if that will help us avoid even theoretical > problems. This is a very interesting question .... Orit > >> + nzrun_len++; >> + res--; >> + } >> + >> + if (!res) { >> + /* truncation to 32-bit long okay */ > > Again, a longer comment might help: > > /* word at a time for speed, use of 32-bit long okay */ > >> + long mask = 0x0101010101010101ULL; >> + while (i < slen) { >> + xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i); > > Same potential strict aliasing problems as for zrun detection. >
diff --git a/migration.h b/migration.h index acc0b94..c46af82 100644 --- a/migration.h +++ b/migration.h @@ -100,4 +100,8 @@ void migrate_add_blocker(Error *reason); */ void migrate_del_blocker(Error *reason); +int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen, + uint8_t *dst, int dlen); +int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen); + #endif diff --git a/savevm.c b/savevm.c index a15c163..1534cbd 100644 --- a/savevm.c +++ b/savevm.c @@ -2385,3 +2385,160 @@ void vmstate_register_ram_global(MemoryRegion *mr) { vmstate_register_ram(mr, NULL); } + +/* + page = zrun nzrun + | zrun nzrun page + + zrun = length + + nzrun = length byte... + + length = uleb128 encoded integer + */ +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; + long res, xor; + uint8_t *nzrun_start = NULL; + + g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) % + sizeof(long))); + + while (i < slen) { + /* overflow */ + if (d + 2 > dlen) { + return -1; + } + + /* not aligned to sizeof(long) */ + res = (slen - i) % sizeof(long); + while (res && old_buf[i] == new_buf[i]) { + zrun_len++; + i++; + res--; + } + + if (!res) { + while (i < slen && + (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { + i += sizeof(long); + zrun_len += sizeof(long); + } + + /* go over the rest */ + while (i < slen && old_buf[i] == new_buf[i]) { + zrun_len++; + i++; + } + } + + /* buffer unchanged */ + if (zrun_len == slen) { + return 0; + } + + /* skip last zero run */ + if (i == slen) { + return d; + } + + d += uleb128_encode_small(dst + d, zrun_len); + + zrun_len = 0; + nzrun_start = new_buf + i; + + /* overflow */ + if (d + 2 > dlen) { + return -1; + } + /* not aligned to sizeof(long) */ + res = (slen - i) % sizeof(long); + while (res && old_buf[i] != new_buf[i]) { + i++; + nzrun_len++; + res--; + } + + if (!res) { + /* truncation to 32-bit long okay */ + long mask = 0x0101010101010101ULL; + while (i < slen) { + xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i); + if ((xor - mask) & ~xor & (mask << 7)) { + /* found the end of an nzrun within the current long */ + while (old_buf[i] != new_buf[i]) { + nzrun_len++; + i++; + } + break; + } else { + i += sizeof(long); + nzrun_len += sizeof(long); + } + } + } + + d += uleb128_encode_small(dst + d, nzrun_len); + /* overflow */ + if (d + nzrun_len > dlen) { + return -1; + } + memcpy(dst + d, nzrun_start, nzrun_len); + d += nzrun_len; + nzrun_len = 0; + } + + return d; +} + +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) { + return -1; + } + + ret = uleb128_decode_small(src + i, &count); + if (ret < 0 || (i && !count)) { + return -1; + } + i += ret; + d += count; + + /* overflow */ + if (d > dlen) { + return -1; + } + + /* nzrun */ + if ((slen - i) < 2) { + return -1; + } + + ret = uleb128_decode_small(src + i, &count); + if (ret < 0 || !count) { + return -1; + } + i += ret; + + /* overflow */ + if (d + count > dlen || i + count > slen) { + return -1; + } + + memcpy(dst + d , src + i, count); + d += count; + i += count; + } + + return d; +}