Undefined Code in .../include/linux.bitops.h

Undefined Code in .../include/linux.bitops.h

[Jeffrey Walton]

Hi All,

My apologies if this is the wrong list. http://www.tux.org/lkml/ is a
tough read, and Item 4, "I think I found a bug, how do I report it?"
does not tell me how to report this.

>From .../include/linux.bitops.h:

/**
 * rol64 - rotate a 64-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 rol64(__u64 word, unsigned int shift)
{
    return (word << shift) | (word >> (64 - shift));
}

/**
 * ror64 - rotate a 64-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 ror64(__u64 word, unsigned int shift)
{
    return (word >> shift) | (word << (64 - shift));
}

/**
 * rol32 - rotate a 32-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 rol32(__u32 word, unsigned int shift)
{
    return (word << shift) | (word >> (32 - shift));
}

/**
 * ror32 - rotate a 32-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 ror32(__u32 word, unsigned int shift)
{
    return (word >> shift) | (word << (32 - shift));
}
...

According to Section 5.8, "Shift Operators" of
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf:

"The operands shall be of integral or enumeration type and integral
promotions are performed. The type of the result is that of the
promoted left operand. The behavior is undefined if the right operand
is negative, or greater than or equal to the length in bits of the
promoted left operand."

If I ask for a shift of 0 (legal C/C++), the various ops will perform
`32 - shift` (or `64 - shift`, etc). That means the right operand *IS*
equal to the length in bits of the operand, so the code is undefined.

The problem may affect other versions of bitops.h (and not just
.../include/linux/bitops.h).

Jeff

Re: Undefined Code in .../include/linux.bitops.h

[Clemens Ladisch]

Jeffrey Walton wrote:
> http://www.tux.org/lkml/ is a tough read, and Item 4, "I think I found
> a bug, how do I report it?" does not tell me how to report this.

>From that page:
| A bug is when something (in the kernel, presumably) doesn't behave the
| way it should

So just tell us what it is that doesn't behave the way it should.

> According to Section 5.8, "Shift Operators" of
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf:

The kernel doesn't try to be fully standard conformant.

>     return (word >> shift) | (word << (32 - shift));

> "The behavior is undefined if the right operand is ... equal to the
> length in bits of the promoted left operand."
>
> If I ask for a shift of 0

Does the kernel ever do this?

> the various ops will perform `32 - shift` (or `64 - shift`, etc). That
> means the right operand *IS* equal to the length in bits of the
> operand, so the code is undefined.

In practice, what CPUs actually do is to shift either by zero or by the
full 32/64 bits.  Both implementations give the correct result.


Regards,
Clemens

Re: Undefined Code in .../include/linux.bitops.h

[Jeffrey Walton]

On Wed, Feb 20, 2013 at 11:10 AM, Clemens Ladisch <clemens@ladisch.de> wrote:
> Jeffrey Walton wrote:
>> http://www.tux.org/lkml/ is a tough read, and Item 4, "I think I found
>> a bug, how do I report it?" does not tell me how to report this.
>
> From that page:
> | A bug is when something (in the kernel, presumably) doesn't behave the
> | way it should
>
> So just tell us what it is that doesn't behave the way it should.
>
>> According to Section 5.8, "Shift Operators" of
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf:
>
> The kernel doesn't try to be fully standard conformant.
>
>>     return (word >> shift) | (word << (32 - shift));
>
>> "The behavior is undefined if the right operand is ... equal to the
>> length in bits of the promoted left operand."
>>
>> If I ask for a shift of 0
>
> Does the kernel ever do this?
>
>> the various ops will perform `32 - shift` (or `64 - shift`, etc). That
>> means the right operand *IS* equal to the length in bits of the
>> operand, so the code is undefined.
>
> In practice, what CPUs actually do is to shift either by zero or by the
> full 32/64 bits.  Both implementations give the correct result.
Well, a few things come to mind.

First, the language is C and the kernel needs a compiler. The compiler
might try hard to be C conforming. I could be wrong, but all that
would be needed to break exiting code in some cases is better
analysis. So the kernel is betting on a component it clearly does not
control.

Second, I know that code will not work on some older processors that
do not mask in its barrel shift as expected. I doubt they will be
encountered today, but you never know. In addition, future processors
may not offer the same [tolerant] behavior of current processors.

Third, depending on non-standard behavior is a usually bad choice over
the long run (not withstanding the comment on being non-conforming).
Fedora/Adobe/Flash and glibc/memmove comes to mind
(https://fedorahosted.org/fesco/ticket/501).

Fourth, user land programs use the header too. This is expected
because programmers are taught to reuse existing code. Unfortunately,
many user land programmers lack the knowledge and experience of a
kernel hacker, so they won't realize a potential minefield exists or
how to navigate the minefield.

Finally, I think its poor mentoring. Many junior programmers look up
to experienced kernel programmers, and I think its poor leadership to
provide them with bad habits. Obviously, this is just my opinion, and
does not warrant a response.

Jeff