Bitfield fix minor bug by sunheehnus · Pull Request #3114 · redis/redis

sunheehnus · 2016-02-29T11:43:46Z

No description provided.

sunheehnus · 2016-02-29T11:56:18Z

bitfield's length

For example, if we use bitfield mykey1 set i4 7 1, the sdslen should be 2, but actually it is 1.
We can see this by

diff --git a/src/bitops.c b/src/bitops.c
index 51f9cc0..44e9d54 100644
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -964,6 +964,7 @@ void bitfieldCommand(client *c) {
              * we need fetch & store as well. */

             if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;
+            printf("%d\n", sdslen(o->ptr));

             /* We need two different but very similar code paths for signed
              * and unsigned operations, since the set of functions to get/set

incr overflow

For example, if we use

bitfield mykey2  set i4 7 -1
bitfield mykey2 incrby i4 7 128

it should actually overflow, but the overflow is not detected, we can see it by

diff --git a/src/bitops.c b/src/bitops.c
index 51f9cc0..b2131a9 100644
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -1010,6 +1010,7 @@ void bitfieldCommand(client *c) {
                     overflow = checkUnsignedBitfieldOverflow(oldval,
                             thisop->i64,thisop->bits,thisop->owtype,&wrapped);
                     if (overflow) newval = wrapped;
+                    if (overflow) printf("INCR OVERFLOW!\n");
                     retval = newval;
                 } else {
                     newval = thisop->i64;

:-)

antirez · 2016-02-29T12:08:53Z

Hey, thanks @sunheehnus!

I think you spotted a bug indeed! Thanks :-) About the fix, I'm not sure if it's correct.
The bug basically originated from the fact I wanted to write a function that takes the farest bit the operation could touch, that is what I use for SETBIT command, but later I forgot to add the bitfield length to the offset, when calling the function that performs the lookup.

So I think the condition of calculating the max byte touched as offset/8 should work as expected,
the problem is that I should call the function using offset+bitfield_size. Makes sense?

antirez · 2016-02-29T12:12:32Z

In the example you made: i4 7, we'll get 7+4 = 11, 11/8 = 1, so byte = 1. Then we set the length of the string to byte+1, and is 2.

sunheehnus · 2016-02-29T15:14:41Z

Hi @antirez , make sense :-)
The approach I write is very similar to the round up to a multiple of a known power of 2 of <Hacker's Delight> Chapter 3 , just a trick :-)

What about the other incr overflow? I think maybe we should remove some of the check condition. :-)

antirez · 2016-02-29T16:11:52Z

Yep there is also the overflow bug :-( But the conditions are useful in order to avoid the undefined signed overflow (which is a C undefined behavior) to happen with large numbers. News ASAP. Thanks!

antirez · 2016-02-29T16:14:06Z

So to recap, I think the following should fix both issues, but avoiding the overflow that happens if we remove certain checks with 64 bit numbers:

diff --git a/src/bitops.c b/src/bitops.c
index 51f9cc0..505b9cb 100644
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -318,7 +318,8 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
     int64_t maxincr = max-value;
     int64_t minincr = min-value;

-    if (value > max || (value >= 0 && incr > 0 && incr > maxincr)) {
+    if (value > max || incr > max || (value >= 0 && incr > 0 && incr > maxincr))
+    {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -327,7 +328,7 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
             }
         }
         return 1;
-    } else if (value < min || (value < 0 && incr < 0 && incr < minincr)) {
+    } else if (value < min || incr < min || (value < 0 && incr < 0 && incr < minincr)) {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -963,7 +964,8 @@ void bitfieldCommand(client *c) {
              * for simplicity. SET return value is the previous value so
              * we need fetch & store as well. */

-            if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;
+            if ((o = lookupStringForBitCommand(c,thisop->offset + thisop->bits))
+                 == NULL) return;

             /* We need two different but very similar code paths for signed
              * and unsigned operations, since the set of functions to get/set

Makes sense to you as well? Thanks.

antirez · 2016-02-29T16:36:59Z

p.s. updated the comment above with a patch fixing both the issues hopefully.

sunheehnus · 2016-02-29T16:47:19Z

LGTM :)

sunheehnus · 2016-02-29T16:53:25Z

Finally we fix it :)

antirez · 2016-02-29T16:55:46Z

Thanks @sunheehnus! Please could you commit it yourself? 99% of work was your!

sunheehnus · 2016-02-29T17:10:58Z

Hi @antirez , sorry, a little sleepy just now, but I have a question...
Given that: we have an i4, and initialized as -4, and the max for i4 is 7, why cannot we increase the -4 by 8(>max), and the result will not overflow?

antirez · 2016-03-01T06:49:01Z

@sunheehnus the problem is that the maxincr / minincr variables could overflow when computed, so thanks to the extra check, we only use those variables when we are sure they did not overflow.

antirez · 2016-03-01T06:49:33Z

This happens with i64 types only so if you reason with smaller types everything looks ok...

sunheehnus · 2016-03-01T07:50:10Z

Make sense, I overlook this edge case >.<

sunheehnus · 2016-03-01T07:55:52Z

Maybe the right way is we add the edge case condition for i64 type?

sunheehnus · 2016-03-01T15:17:15Z

Hi @antirez , what about this patch, it takes i64 type as an edge case condition :-)

diff --git a/src/bitops.c b/src/bitops.c
index 51f9cc0..28405a3 100644
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -318,7 +318,8 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
     int64_t maxincr = max-value;
     int64_t minincr = min-value;

-    if (value > max || (value >= 0 && incr > 0 && incr > maxincr)) {
+    if (value > max || (bits == 64 && value >= 0 && incr > 0 && incr > maxincr)
+            || (bits < 64 && incr > 0 && incr > maxincr)) {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -327,7 +328,8 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
             }
         }
         return 1;
-    } else if (value < min || (value < 0 && incr < 0 && incr < minincr)) {
+    } else if (value < min || (bits == 64 && value < 0 && incr < 0 && incr < minincr)
+            || (bits < 64 && incr < 0 && incr < minincr)) {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -445,8 +447,8 @@ int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) {

     if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 ||
         llbits < 1 ||
-        (*sign == 1 && llbits > 63) ||
-        (*sign == 0 && llbits > 64))
+        (*sign == 1 && llbits > 64) ||
+        (*sign == 0 && llbits > 63))
     {
         addReplyError(c,err);
         return C_ERR;
@@ -963,7 +965,8 @@ void bitfieldCommand(client *c) {
              * for simplicity. SET return value is the previous value so
              * we need fetch & store as well. */

-            if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;
+            if ((o = lookupStringForBitCommand(c,thisop->offset + thisop->bits))
+                    == NULL) return;

             /* We need two different but very similar code paths for signed
              * and unsigned operations, since the set of functions to get/set

antirez · 2016-03-01T18:17:18Z

@sunheehnus what's the advantage of explicitly checking for the 64 bit operation? If it's for performances, the difference will be impossible to measure practically or may be even slower, very hard to tell. On the other hand, the code with the explicit 64 bit conditional looks more complex in some way. Or does this change fixes something? Thank you.

sunheehnus · 2016-03-01T23:47:22Z

Hi @antirez ,
as you said

the problem is that the maxincr / minincr variables could overflow when computed
this happens with i64 types only so if you reason with smaller types everything looks ok...

so I take i64 case as a special condition,

the condition after bits == 64 && is your former check condition which will avoid the undefined signed overflow for i64
the condition after bits < 64 && is the check condition for smaller types because maxincr/minincr will not overflow under this condition, so we can simply compare it with incr

What this fix is the smaller types(such as the i4) behavior. :-)

Example:

without the condition for i64

127.0.0.1:6379> flushall
OK
127.0.0.1:6379> bitfield s overflow sat set i4 7 -3
1) (integer) 0
127.0.0.1:6379> bitfield s overflow sat incrby i4 7 8
1) (integer) 7

with the condition for i64

127.0.0.1:6379> flushall
OK
127.0.0.1:6379> bitfield s overflow sat set i4 7 -3
1) (integer) 0
127.0.0.1:6379> bitfield s overflow sat incrby i4 7 8
1) (integer) 5

The new bitfield command is an extension to the Redis bit operations, where not just single bit operations are performed, but the array of bits composing a string, can be addressed at random, not aligned offsets, with any width unsigned and signed integers like u8, s5, u10 (up to 64 bit signed integers and 63 bit unsigned integers). The BITFIELD command supports subcommands that can SET, GET, or INCRBY those arbitrary bit counters, with multiple overflow semantics. Trivial and credits: A similar command was imagined a few times in the past, but for some reason looked a bit far fetched or not well specified. Finally the command was proposed again in a clear form by Yoav Steinberg from Redis Labs, that proposed a set of commands on arbitrary sized integers stored at bit offsets. Starting from this proposal I wrote an initial specification of a single command with sub-commands similar to what Yoav envisioned, using short names for types definitions, and adding control on the overflow. This commit is the resulting implementation. Examples: BITFIELD mykey OVERFLOW wrap INCRBY i2 10 -1 GET i2 10

antirez · 2016-03-02T08:53:14Z

Yes you are right, and also thanks for the *sign fix. Checking a bit better the whole issue...

sunheehnus · 2016-03-02T10:18:20Z

Hi, @antirez, already squash the changes into one commit and push -f, maybe because I close this PR, the commit didn't appear here, so I open another PR. :-)

antirez · 2016-03-02T10:55:59Z

Ok, I just wrote a fuzzer and I'm experimenting with your patch and a modification that may be simpler. News ASAP. Thanks!

antirez · 2016-03-02T14:06:24Z

Ok so... this is hopefully the end of the story:

The conditional you provided can be simplified (see the patch) while retaining a correct behavior, by adding a test for an increment greater than the allowed increment.
There was one more bug that created a lot of issues with singned/unsigned integers > 32 bits. This is now fixed.

So the final patch to commit should be the following, hopefully!
The following patch passes an extensive fuzzy testing, so we should be safe :-)

diff --git a/src/bitops.c b/src/bitops.c
index 51f9cc0..753db53 100644
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -203,7 +203,7 @@ void setUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, uint6
     uint64_t byte, bit, byteval, bitval, j;

     for (j = 0; j < bits; j++) {
-        bitval = (value & (1<<(bits-1-j))) != 0;
+        bitval = (value & ((uint64_t)1<<(bits-1-j))) != 0;
         byte = offset >> 3;
         bit = 7 - (offset & 0x7);
         byteval = p[byte];
@@ -243,7 +243,7 @@ int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
     /* If the top significant bit is 1, propagate it to all the
      * higher bits for two complement representation of signed
      * integers. */
-    if (value & (1 << (bits-1)))
+    if (value & ((uint64_t)1 << (bits-1)))
         value |= ((uint64_t)-1) << bits;
     return value;
 }
@@ -272,7 +272,7 @@ int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
 #define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */

 int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) {
-    uint64_t max = (bits == 64) ? UINT64_MAX : ((1<<bits)-1);
+    uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1);
     int64_t maxincr = max-value;
     int64_t minincr = -value;

@@ -309,7 +309,7 @@ handle_wrap:
 }

 int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) {
-    int64_t max = (bits == 64) ? INT64_MAX : ((1<<(bits-1))-1);
+    int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1);
     int64_t min = (-max)-1;

     /* Note that maxincr and minincr could overflow, but we use the values
@@ -318,7 +318,8 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
     int64_t maxincr = max-value;
     int64_t minincr = min-value;

-    if (value > max || (value >= 0 && incr > 0 && incr > maxincr)) {
+    if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr))
+    {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -327,7 +328,7 @@ int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int
             }
         }
         return 1;
-    } else if (value < min || (value < 0 && incr < 0 && incr < minincr)) {
+    } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) {
         if (limit) {
             if (owtype == BFOVERFLOW_WRAP) {
                 goto handle_wrap;
@@ -445,8 +446,8 @@ int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) {

     if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 ||
         llbits < 1 ||
-        (*sign == 1 && llbits > 63) ||
-        (*sign == 0 && llbits > 64))
+        (*sign == 1 && llbits > 64) ||
+        (*sign == 0 && llbits > 63))
     {
         addReplyError(c,err);
         return C_ERR;
@@ -963,7 +964,8 @@ void bitfieldCommand(client *c) {
              * for simplicity. SET return value is the previous value so
              * we need fetch & store as well. */

-            if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;
+            if ((o = lookupStringForBitCommand(c,thisop->offset + thisop->bits))
+                 == NULL) return;

             /* We need two different but very similar code paths for signed
              * and unsigned operations, since the set of functions to get/set

See issue #3114.

sunheehnus · 2016-03-06T14:16:59Z

Looks more correct and clean :-)

See issue #3114.

See issue redis#3114.

sunheehnus added 2 commits February 29, 2016 19:35

bitops: correct bitfield's length

79da1fe

bitops: correct incr overflow condition

74f9928

sunheehnus closed this Feb 29, 2016

sunheehnus mentioned this pull request Mar 2, 2016

bitops/bitfield: fix length, overflow condition and *sign #3118

Merged

antirez added a commit that referenced this pull request Mar 2, 2016

More BITFIELD fixes. Overflow conditional simplified.

fe64960

See issue #3114.

antirez added a commit that referenced this pull request May 2, 2016

More BITFIELD fixes. Overflow conditional simplified.

5f3ef73

See issue #3114.

JackieXie168 pushed a commit to JackieXie168/redis that referenced this pull request Aug 29, 2016

More BITFIELD fixes. Overflow conditional simplified.

0aa4678

See issue redis#3114.

Conversation

sunheehnus commented Feb 29, 2016

Uh oh!

sunheehnus commented Feb 29, 2016

bitfield's length

incr overflow

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

sunheehnus commented Feb 29, 2016

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

sunheehnus commented Feb 29, 2016

Uh oh!

sunheehnus commented Feb 29, 2016

Uh oh!

antirez commented Feb 29, 2016

Uh oh!

sunheehnus commented Feb 29, 2016

Uh oh!

antirez commented Mar 1, 2016

Uh oh!

antirez commented Mar 1, 2016

Uh oh!

sunheehnus commented Mar 1, 2016

Uh oh!

sunheehnus commented Mar 1, 2016

Uh oh!

sunheehnus commented Mar 1, 2016

Uh oh!

antirez commented Mar 1, 2016

Uh oh!

sunheehnus commented Mar 1, 2016

Example:

without the condition for i64

with the condition for i64

Uh oh!

antirez commented Mar 2, 2016

Uh oh!

sunheehnus commented Mar 2, 2016

Uh oh!

antirez commented Mar 2, 2016

Uh oh!

antirez commented Mar 2, 2016

Uh oh!

sunheehnus commented Mar 6, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants