[ovs-dev] util: Generalize rightmost_1bit_idx(), leftmost_1bit_idx().
diff mbox

Message ID 1442615188-23637-1-git-send-email-blp@nicira.com
State Accepted
Headers show

Commit Message

Ben Pfaff Sept. 18, 2015, 10:26 p.m. UTC
These functions could only work with 32-bit integers because of their
special cases for an argument of value 0.  However, none of the existing
users depended on this special case, and some of the users did try to use
these functions with 64-bit integer arguments.  Thus, this commit changes
them to support 64-bit integer arguments and drops the special cases for
zero.

This fixes a latent bug that applied rightmost_1bit_idx() to an ofpact
bitmap, which only becomes visible when an OFPACT_* with value greater than
32 is included in the bitmap.

Reported-by: Kyle Upton <kupton@baymicrosystems.com>
Reported-at: http://openvswitch.org/pipermail/dev/2015-September/060128.html
Signed-off-by: Ben Pfaff <blp@nicira.com>
---
 lib/util.h | 21 ++++++++-------------
 1 file changed, 8 insertions(+), 13 deletions(-)

Comments

Andy Zhou Sept. 23, 2015, 9:25 p.m. UTC | #1
On Fri, Sep 18, 2015 at 3:26 PM, Ben Pfaff <blp@nicira.com> wrote:
> These functions could only work with 32-bit integers because of their
> special cases for an argument of value 0.  However, none of the existing
> users depended on this special case, and some of the users did try to use
> these functions with 64-bit integer arguments.  Thus, this commit changes
> them to support 64-bit integer arguments and drops the special cases for
> zero.
>
I wonder what would be the down side of returning 64 for zeros?
Ben Pfaff Sept. 29, 2015, 11:46 p.m. UTC | #2
On Wed, Sep 23, 2015 at 02:25:47PM -0700, Andy Zhou wrote:
> On Fri, Sep 18, 2015 at 3:26 PM, Ben Pfaff <blp@nicira.com> wrote:
> > These functions could only work with 32-bit integers because of their
> > special cases for an argument of value 0.  However, none of the existing
> > users depended on this special case, and some of the users did try to use
> > these functions with 64-bit integer arguments.  Thus, this commit changes
> > them to support 64-bit integer arguments and drops the special cases for
> > zero.
> >
> I wonder what would be the down side of returning 64 for zeros?

Probably just an extra branch.  It's conceptually a little weird though.
Ben Pfaff Sept. 30, 2015, 6:11 a.m. UTC | #3
On Tue, Sep 29, 2015 at 04:46:37PM -0700, Ben Pfaff wrote:
> On Wed, Sep 23, 2015 at 02:25:47PM -0700, Andy Zhou wrote:
> > On Fri, Sep 18, 2015 at 3:26 PM, Ben Pfaff <blp@nicira.com> wrote:
> > > These functions could only work with 32-bit integers because of their
> > > special cases for an argument of value 0.  However, none of the existing
> > > users depended on this special case, and some of the users did try to use
> > > these functions with 64-bit integer arguments.  Thus, this commit changes
> > > them to support 64-bit integer arguments and drops the special cases for
> > > zero.
> > >
> > I wonder what would be the down side of returning 64 for zeros?
> 
> Probably just an extra branch.  It's conceptually a little weird though.

I decided to apply this to master on the basis of Kyle's review.

Returning 64 would be marginally safer though, even if it's slightly
more expensive.  That might be the right trade-off, I'm not sure.
Kyle Upton Sept. 30, 2015, 4:21 p.m. UTC | #4
On 09/30/2015 02:11 AM, Ben Pfaff wrote:
> On Tue, Sep 29, 2015 at 04:46:37PM -0700, Ben Pfaff wrote:
>> On Wed, Sep 23, 2015 at 02:25:47PM -0700, Andy Zhou wrote:
>>> On Fri, Sep 18, 2015 at 3:26 PM, Ben Pfaff <blp@nicira.com> wrote:
>>>> These functions could only work with 32-bit integers because of their
>>>> special cases for an argument of value 0.  However, none of the existing
>>>> users depended on this special case, and some of the users did try to use
>>>> these functions with 64-bit integer arguments.  Thus, this commit changes
>>>> them to support 64-bit integer arguments and drops the special cases for
>>>> zero.
>>>>
>>> I wonder what would be the down side of returning 64 for zeros?
>>
>> Probably just an extra branch.  It's conceptually a little weird though.
>
> I decided to apply this to master on the basis of Kyle's review.
>
> Returning 64 would be marginally safer though, even if it's slightly
> more expensive.  That might be the right trade-off, I'm not sure.
>

I'm not 100% sure either. Returning 64 is still unsafe if unchecked, and
if checked, why not just insure a non-zero precondition.  Anyway, thanks
for the fix, Ben.

-Kyle

This correspondence, and any attachments or files transmitted with this correspondence, contains information which may be confidential and privileged and is intended solely for the use of the addressee. Unless you are the addressee or are authorized to receive messages for the addressee, you may not use, copy, disseminate, or disclose this correspondence or any information contained in this correspondence to any third party. If you have received this correspondence in error, please notify the sender immediately and delete this correspondence and any attachments or files transmitted with this correspondence from your system, and destroy any and all copies thereof, electronic or otherwise. Your cooperation and understanding are greatly appreciated.
Andy Zhou Sept. 30, 2015, 5:09 p.m. UTC | #5
On Tue, Sep 29, 2015 at 11:11 PM, Ben Pfaff <blp@nicira.com> wrote:
> On Tue, Sep 29, 2015 at 04:46:37PM -0700, Ben Pfaff wrote:
>> On Wed, Sep 23, 2015 at 02:25:47PM -0700, Andy Zhou wrote:
>> > On Fri, Sep 18, 2015 at 3:26 PM, Ben Pfaff <blp@nicira.com> wrote:
>> > > These functions could only work with 32-bit integers because of their
>> > > special cases for an argument of value 0.  However, none of the existing
>> > > users depended on this special case, and some of the users did try to use
>> > > these functions with 64-bit integer arguments.  Thus, this commit changes
>> > > them to support 64-bit integer arguments and drops the special cases for
>> > > zero.
>> > >
>> > I wonder what would be the down side of returning 64 for zeros?
>>
>> Probably just an extra branch.  It's conceptually a little weird though.
>
> I decided to apply this to master on the basis of Kyle's review.
>
> Returning 64 would be marginally safer though, even if it's slightly
> more expensive.  That might be the right trade-off, I'm not sure.
Since the value is only marginal, it may not be worthwhile to add the
extra check.
At any rate, the comment makes it clear that zero is not expected.

Patch
diff mbox

diff --git a/lib/util.h b/lib/util.h
index 7080a0c..4186d49 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -506,25 +506,20 @@  zero_rightmost_1bit(uintmax_t x)
     return x & (x - 1);
 }
 
-/* Returns the index of the rightmost 1-bit in 'x' (e.g. 01011000 => 3), or 32
- * if 'x' is 0.
- *
- * Unlike the other functions for rightmost 1-bits, this function only works
- * with 32-bit integers. */
+/* Returns the index of the rightmost 1-bit in 'x' (e.g. 01011000 => 3), or an
+ * undefined value if 'x' is 0. */
 static inline int
-rightmost_1bit_idx(uint32_t x)
+rightmost_1bit_idx(uint64_t x)
 {
-    return ctz32(x);
+    return ctz64(x);
 }
 
-/* Returns the index of the leftmost 1-bit in 'x' (e.g. 01011000 => 6), or 32
- * if 'x' is 0.
- *
- * This function only works with 32-bit integers. */
+/* Returns the index of the leftmost 1-bit in 'x' (e.g. 01011000 => 6), or an
+ * undefined value if 'x' is 0. */
 static inline uint32_t
-leftmost_1bit_idx(uint32_t x)
+leftmost_1bit_idx(uint64_t x)
 {
-    return x ? log_2_floor(x) : 32;
+    return log_2_floor(x);
 }
 
 /* Return a ovs_be32 prefix in network byte order with 'plen' highest bits set.