lib: packing: fix shift wrapping in bit_reverse()
Subsystems (5)
PATCH 1/1 lib: packing: fix shift wrapping in bit_reverse()
The bit_reverse() function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.
--- lib/packing.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)
lib/packing.c +2 -3
@@ -32,12 +32,11 @@ static int get_reverse_lsw32_offset(int offset, size_t len)static u64 bit_reverse (u64 val,unsigned int width) {u64 new_val =0 ; -unsigned int bit;unsigned int i;for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 )) + new_val |=BIT_ULL (width - i -1 ); }return new_val; }
Signature · 1 line
2.35.1
Vladimir Oltean
maintainerQuoted 15 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.Fixes 554aae35007e ("lib: Add support for generic packing operations")Signed-off-by Dan Carpenter <[email protected]>--- lib/packing.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)lib/packing.c +0
-0
lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 10 lines
lib/packing.c +1
-3@@ -32,12 +32,11 @@ static int get_reverse_lsw32_offset(int offset, size_t len)static u64 bit_reverse (u64 val,unsigned int width) {u64 new_val =0 ; -unsigned int bit;unsigned int i;for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))
hmm, why 1 and not i?
Quoted 7 lines
lib/packing.c +1
-0+ new_val |=BIT_ULL (width - i -1 ); }return new_val; }Signature · 1 line
2.35.1
Quoted 22 lines · Vladimir Oltean
Quoted 21 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.Fixes 554aae35007e ("lib: Add support for generic packing operations")Signed-off-by Dan Carpenter <[email protected]>--- lib/packing.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)lib/packing.c +0
-1@@ -32,12 +32,11 @@ static int get_reverse_lsw32_offset(int offset, size_t len)static u64 bit_reverse (u64 val,unsigned int width) {u64 new_val =0 ; -unsigned int bit;unsigned int i;
Quoted 6 lines
lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 4 lines
lib/packing.c +1
-2for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))hmm, why 1 and not i?
Because I'm a moron. Let me resend.
regards,
dan carpenter
Vladimir Oltean
maintainerQuoted 23 lines · Dan Carpenter
Quoted 22 lines · Vladimir Oltean
Quoted 21 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.Fixes 554aae35007e ("lib: Add support for generic packing operations")Signed-off-by Dan Carpenter <[email protected]>--- lib/packing.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)lib/packing.c +0
-1@@ -32,12 +32,11 @@ static int get_reverse_lsw32_offset(int offset, size_t len)static u64 bit_reverse (u64 val,unsigned int width) {u64 new_val =0 ; -unsigned int bit;unsigned int i;
Quoted 8 lines
Quoted 6 lines
lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 4 lines
lib/packing.c +1
-2for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))hmm, why 1 and not i?
Because I'm a moron. Let me resend.
Wait a second, I deliberately wrote the code without conditionals. Let me look at the code disassembly before and after the patch and see what they look like.
Quoted 31 lines · Vladimir Oltean
Quoted 30 lines · Dan Carpenter
Quoted 28 lines · Vladimir Oltean
Quoted 15 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.Fixes 554aae35007e ("lib: Add support for generic packing operations")Signed-off-by Dan Carpenter <[email protected]>--- lib/packing.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)lib/packing.c +0
-0lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 10 lines
lib/packing.c +1
-3@@ -32,12 +32,11 @@ static int get_reverse_lsw32_offset(int offset, size_t len)static u64 bit_reverse (u64 val,unsigned int width) {u64 new_val =0 ; -unsigned int bit;unsigned int i;for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))hmm, why 1 and not i?
Quoted 5 lines
Quoted 1 line
Because I'm a moron. Let me resend.
Wait a second, I deliberately wrote the code without conditionals. Let me look at the code disassembly before and after the patch and see what they look like.
My crappy benchmark says that the if statement is faster. 22 vs 26 seconds.
regards,
dan carpenter
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>
#define BIT(n) (1 << (n))
#define BIT_ULL(n) (1ULL << (n))
#define u64 unsigned long long
#define u32 unsigned int
#define u16 unsigned short
#define u8 unsigned char
static u64 bit_reverse1(u64 val, unsigned int width)
{
u64 new_val = 0;
unsigned int i;
for (i = 0; i < width; i++) {
if (val & BIT_ULL(i))
new_val |= BIT_ULL(width - i - 1);
}
return new_val;
}static u64 bit_reverse2(u64 val, unsigned int width)
{
u64 new_val = 0;
u64 bit;
unsigned int i;
for (i = 0; i < width; i++) {
bit = (val & BIT_ULL(i)) != 0;
new_val |= (bit << (width - i - 1));
}
return new_val;
}int main(void)
{
unsigned long long val;
for (val = ULLONG_MAX - INT_MAX; val; val++)
bit_reverse1(val, 2);
return 0;
}Vladimir Oltean
maintainerQuoted 2 lines · Dan Carpenter
My crappy benchmark says that the if statement is faster. 22 vs 26 seconds.
Sure that's not just noise in the measurements? :)
Vladimir Oltean
maintainerQuoted 3 lines · Vladimir Oltean
Wait a second, I deliberately wrote the code without conditionals. Let me look at the code disassembly before and after the patch and see what they look like.
Before (make lib/packing.lst on arm64):
for (i = 0; i < width; i++) {
1c: 310004ec adds w12, w7, #0x1
20: 540001c0 b.eq 58 <adjust_for_msb_right_quirk+0x58> // b.none
24: 52800004 mov w4, #0x0 // #0
bit = (val & (1 << i)) != 0;
28: 5280002b mov w11, #0x1 // #1
2c: d503201f nop
30: 1ac42166 lsl w6, w11, w4
new_val |= (bit << (width - i - 1));
34: 4b0400e9 sub w9, w7, w4
bit = (val & (1 << i)) != 0;
38: 93407cc6 sxtw x6, w6 /* We don't want sign extension */
3c: ea0a00df tst x6, x10
40: 1a9f07e6 cset w6, ne // ne = any
for (i = 0; i < width; i++) {
44: 6b07009f cmp w4, w7
48: 11000484 add w4, w4, #0x1
new_val |= (bit << (width - i - 1));
4c: 1ac920c6 lsl w6, w6, w9
50: aa060108 orr x8, x8, x6
for (i = 0; i < width; i++) { 54: 54fffee1 b.ne 30 <adjust_for_msb_right_quirk+0x30> // b.any
Then this modified code:
static u64 bit_reverse(u64 val, unsigned int width)
{
u64 new_val = 0;
unsigned int i;
for (i = 0; i < width; i++)
if (val & BIT_ULL(i))
new_val |= BIT_ULL(width - i - 1);
return new_val;
}compiles to this:
for (i = 0; i < width; i++) {
1c: 310004eb adds w11, w7, #0x1
20: 540001c0 b.eq 58 <adjust_for_msb_right_quirk+0x58> // b.none
24: 52800005 mov w5, #0x0 // #0
new_val |= BIT_ULL(width - i - 1);
28: d280002a mov x10, #0x1 // #1
2c: 14000002 b 34 <adjust_for_msb_right_quirk+0x34> /* this is an unconditional jump to "sub w4, w7, w5", skipping the assignment to w5 */
30: 2a0803e5 mov w5, w8 /* this is only hit by the backwards jump b.ne 30 at the end */
34: 4b0500e4 sub w4, w7, w5
if (val & BIT_ULL(i))
38: 9ac52528 lsr x8, x9, x5
new_val |= BIT_ULL(width - i - 1);
3c: f240011f tst x8, #0x1
for (i = 0; i < width; i++) {
40: 110004a8 add w8, w5, #0x1
new_val |= BIT_ULL(width - i - 1);
44: 9ac42144 lsl x4, x10, x4
48: aa0400c4 orr x4, x6, x4
4c: 9a861086 csel x6, x4, x6, ne // ne = any
for (i = 0; i < width; i++) { 50: 6b0700bf cmp w5, w7
54: 54fffee1 b.ne 30 <adjust_for_msb_right_quirk+0x30> // b.any
which indeed has no branch in the main loop (between 0x30 and 0x54), because as I explained, the "b 34" doesn't count - it's not in the loop.
Additionally, this rewritten code which is considerably more obscure in C:
static u64 bit_reverse(u64 val, unsigned int width)
{
u64 new_val = 0;
unsigned int i;
for (i = 0; i < width; i++)
new_val |= !!(val & BIT_ULL(i)) ?
BIT_ULL(width - i - 1) : 0;
return new_val;
}compiles to the exact same assembly code as the variant with "if":
for (i = 0; i < width; i++) 1c: 310004eb adds w11, w7, #0x1 20: 540001c0 b.eq 58 <adjust_for_msb_right_quirk+0x58> // b.none 24: 52800005 mov w5, #0x0 // #0 new_val |= !!(val & BIT_ULL(i)) ? 28: d280002a mov x10, #0x1 // #1 2c: 14000002 b 34 <adjust_for_msb_right_quirk+0x34> 30: 2a0803e5 mov w5, w8 34: 4b0500e4 sub w4, w7, w5 38: 9ac52528 lsr x8, x9, x5 3c: f240011f tst x8, #0x1 for (i = 0; i < width; i++) 40: 110004a8 add w8, w5, #0x1 new_val |= !!(val & BIT_ULL(i)) ? 44: 9ac42144 lsl x4, x10, x4 48: aa0400c4 orr x4, x6, x4 4c: 9a861086 csel x6, x4, x6, ne // ne = any for (i = 0; i < width; i++)
50: 6b0700bf cmp w5, w7
54: 54fffee1 b.ne 30 <adjust_for_msb_right_quirk+0x30> // b.any
So this is good with the "if".
From: Dan Carpenter
Quoted 1 line
Sent: 07 December 2022 12:21
....
Quoted 6 lines
Quoted 4 lines
lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 2 lines
lib/packing.c +1
-1- new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))hmm, why 1 and not i?
Because I'm a moron. Let me resend.
Since we're not writing FORTRAN-IV why not use a variable name that is harder to confuse with 1?
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Vladimir Oltean
maintainerQuoted 8 lines · David Laight
From: Dan Carpenter
Quoted 1 line
Sent: 07 December 2022 12:21
....
Quoted 5 lines
Quoted 4 lines
lib/packing.c static int get_reverse_lsw32_offset(int offset, size_t len) · line 38
Quoted 2 lines
lib/packing.c +1
-1- new_val |= (bit << (width - i -1 )); +if (val &BIT_ULL (1 ))hmm, why 1 and not i?
Quoted 4 lines
Quoted 1 line
Because I'm a moron. Let me resend.
Since we're not writing FORTRAN-IV why not use a variable name that is harder to confuse with 1?
How about 'k'?
Quoted 4 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.
It seems from the surrounding code that this function is only called for width of up to a byte (but correct me if I'm wrong). There are fast implementations of bit-reverse in include/linux/bitrev.h. It's better to just remove this function entirely and call bitrev8, which is just a precalc-table lookup. While at it, also sort includes.
lib/packing.c | 20 ++++---------------- 1 file changed, 4 insertions(+), 16 deletions(-)
lib/packing.c +3 -15
@@ -2,10 +2,11 @@/* Copyright 2016-2018 NXP * Copyright (c) 2018-2019, Vladimir Oltean <[email protected]> */ -#include <linux/packing.h> -#include <linux/module.h> #include <linux/bitops.h> +#include <linux/bitrev.h> #include <linux/errno.h> +#include <linux/module.h> +#include <linux/packing.h> #include <linux/types.h> static int get_le_offset (int offset)
@@ -29,19 +30,6 @@ static int get_reverse_lsw32_offset(int offset, size_t len)return word_index *4 + offset; } -static u64 bit_reverse (u64 val,unsigned int width) -{ -u64 new_val =0 ; -unsigned int bit; -unsigned int i; - -for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); - } -return new_val; -} -static void adjust_for_msb_right_quirk (u64 *to_write,int *box_start_bit,int *box_end_bit,u8 *box_mask) {
@@ -49,7 +37,7 @@ static void adjust_for_msb_right_quirk(u64
*to_write, int *box_start_bit,
int new_box_start_bit, new_box_end_bit;
*to_write >>= *box_end_bit;
- *to_write = bit_reverse(*to_write, box_bit_width);
+ *to_write = bitrev8(*to_write) >> (8 - box_bit_width);
*to_write <<= *box_end_bit;
new_box_end_bit = box_bit_width - *box_start_bit - 1;Vladimir Oltean
maintainerHi Uladzislau,
Quoted 8 lines · Uladzislau Koshchanka
Quoted 4 lines · Dan Carpenter
The
bit_reverse()function is clearly supposed to be able to handle 64 bit values, but the types for "(1 << i)" and "bit << (width - i - 1)" are not enough to handle more than 32 bits.It seems from the surrounding code that this function is only called for width of up to a byte (but correct me if I'm wrong).
This observation is quite true. I was quite lazy to look and remember whether this is the case, but the comment says it quite clearly:
/* Bit indices into the currently accessed 8-bit box */ int box_start_bit, box_end_bit, box_addr;
Quoted 3 lines
There are fast implementations of bit-reverse in
include/linux/bitrev.h. It's better to just remove this function entirely and call bitrev8, which is just a precalc-table lookup. While at it, also sort includes.
The problem I see with bitrev8 is that the byte_rev_table[] can seemingly be built as a module (the BITREVERSE Kconfig knob is tristate, and btw your patch doesn't make PACKING select BITREVERSE). But PACKING is bool. IIRC, I got comments during review that it's not worth making packing a module, but I may remember wrong.
Quoted 10 lines
(quoted diff) +1
-1@@ -49,7 +37,7 @@ static void adjust_for_msb_right_quirk(u64 *to_write, int *box_start_bit, int new_box_start_bit, new_box_end_bit; *to_write >>= *box_end_bit; - *to_write = bit_reverse(*to_write, box_bit_width); + *to_write = bitrev8(*to_write) >> (8 - box_bit_width); *to_write <<= *box_end_bit;new_box_end_bit = box_bit_width - *box_start_bit - 1;
Anyway, the patch works in principle. I know this because I wrote the following patch to check:
From 17099a86291713d2bcf8137473daea5f390a2ef4 Mon Sep 17 00:00:00 2001
From: Vladimir Oltean <[email protected]>
Date: Fri, 9 Dec 2022 16:23:35 +0200
Subject: [PATCH] lib: packing: add boot-time selftests
In case people want to make changes to the packing() implementation but they aren't sure it's going to keep working, provide 16 boot-time calls to packing() which exercise all combinations of quirks plus PACK | UNPACK.
--- lib/Kconfig | 9 +++ lib/packing.c | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 195 insertions(+)
lib/Kconfig +9 -0
@@ -39,6 +39,15 @@ config PACKING When in doubt, say N. +config PACKING_SELFTESTS + bool "Selftests for packing library" + depends on PACKING + help + Boot-time selftests to make sure that the packing and unpacking + functions work properly. + + When in doubt, say N. + config BITREVERSE tristate
lib/packing.c +186 -0
191 lines not on this page · raw message
Signature · 5 lines
2.34.1 I've been meaning to do this for a while, but I'm not sure what is the best way to integrate such a thing. Does anyone have any idea?
Hi Vladimir,
Quoted 5 lines
The problem I see with bitrev8 is that the byte_rev_table[] can seemingly be built as a module (the BITREVERSE
Kconfigknob is tristate, and btw your patch doesn't make PACKING select BITREVERSE). But PACKING is bool. IIRC, I got comments during review that it's not worth making packing a module, but I may remember wrong.
Do you really think it's a problem? I personally would just select BITREVERSE with/without making PACKING tristate. BITREVERSE is already selected by CRC32 which defaults to y, so just adding a select isn't a change in the default. Can't think of a practical point in avoiding linking against 256 bytes here.
In any case, it just doesn't look right to have multiple bit-reverse implementations only because of Kconfig relations.
Vladimir Oltean
maintainerQuoted 8 lines · Uladzislau Koshchanka
Hi Vladimir,
Quoted 5 lines
The problem I see with bitrev8 is that the byte_rev_table[] can seemingly be built as a module (the BITREVERSE
Kconfigknob is tristate, and btw your patch doesn't make PACKING select BITREVERSE). But PACKING is bool. IIRC, I got comments during review that it's not worth making packing a module, but I may remember wrong.
Quoted 8 lines
Do you really think it's a problem? I personally would just select BITREVERSE with/without making PACKING tristate. BITREVERSE is already selected by CRC32 which defaults to y, so just adding a select isn't a change in the default. Can't think of a practical point in avoiding linking against 256 bytes here.
In any case, it just doesn't look right to have multiple bit-reverse implementations only because of
Kconfigrelations.
Ok, let's use BITREVERSE then. Could you submit your patch formally please?
Vladimir Oltean
maintainerQuoted 15 lines · Vladimir Oltean
Quoted 14 lines · Uladzislau Koshchanka
Hi Vladimir,
Quoted 5 lines
The problem I see with bitrev8 is that the byte_rev_table[] can seemingly be built as a module (the BITREVERSE
Kconfigknob is tristate, and btw your patch doesn't make PACKING select BITREVERSE). But PACKING is bool. IIRC, I got comments during review that it's not worth making packing a module, but I may remember wrong.Do you really think it's a problem? I personally would just select BITREVERSE with/without making PACKING tristate. BITREVERSE is already selected by CRC32 which defaults to y, so just adding a select isn't a change in the default. Can't think of a practical point in avoiding linking against 256 bytes here.
Quoted 4 lines
Quoted 2 lines
In any case, it just doesn't look right to have multiple bit-reverse implementations only because of
Kconfigrelations.Ok, let's use BITREVERSE then. Could you submit your patch formally please?
Also, none of that 'while at it, do XYZ unrelated stuff'. One patch per logical change please.
PATCH 1/1 lib: packing: replace bit_reverse() with bitrev8()
In reply to Vladimir OlteanRemove bit_reverse() function. Instead use bitrev8() from linux/bitrev.h + bitshift. Reduces code-repetition.
--- lib/Kconfig | 1 + lib/packing.c | 16 ++-------------- 2 files changed, 3 insertions(+), 14 deletions(-)
lib/Kconfig +1 -0
@@ -24,6 +24,7 @@ config LINEAR_RANGES config PACKING bool "Generic bitfield packing and unpacking" + select BITREVERSE default n help This option provides the packing() helper function, which permits
lib/packing.c +2 -14
@@ -7,6 +7,7 @@#include <linux/bitops.h> #include <linux/errno.h> #include <linux/types.h> +#include <linux/bitrev.h> static int get_le_offset (int offset) {
@@ -29,19 +30,6 @@ static int get_reverse_lsw32_offset(int offset, size_t len)return word_index *4 + offset; } -static u64 bit_reverse (u64 val,unsigned int width) -{ -u64 new_val =0 ; -unsigned int bit; -unsigned int i; - -for (i =0 ; i < width; i++) { - bit = (val & (1 << i)) !=0 ; - new_val |= (bit << (width - i -1 )); - } -return new_val; -} -static void adjust_for_msb_right_quirk (u64 *to_write,int *box_start_bit,int *box_end_bit,u8 *box_mask) {
@@ -49,7 +37,7 @@ static void adjust_for_msb_right_quirk(u64 *to_write, int *box_start_bit,int new_box_start_bit, new_box_end_bit; *to_write >>= *box_end_bit; - *to_write =bit_reverse (*to_write, box_bit_width); + *to_write =bitrev8 (*to_write) >> (8 - box_bit_width); *to_write <<= *box_end_bit; new_box_end_bit = box_bit_width - *box_start_bit -1 ;
Signature · 1 line
2.34.1
Re: [PATCH] lib: packing: replace bit_reverse() with bitrev8()
Quoted 6 lines · Uladzislau Koshchanka
Remove
bit_reverse()function. Instead usebitrev8()fromlinux/bitrev.h+ bitshift. Reduces code-repetition.Signed-off-by Uladzislau Koshchanka <[email protected]>---
Re: [PATCH] lib: packing: replace bit_reverse() with bitrev8()
In reply to Uladzislau KoshchankaThis patch was applied to netdev/net-next.git (master) by Jakub Kicinski <[email protected]>:
Hello:
This patch was applied to netdev/net-next.git (master) by Jakub Kicinski <[email protected]>:
Quoted 8 lines · On Sat, 10 Dec 2022 03:44:23 +0300 you wrote:
Remove
bit_reverse()function. Instead usebitrev8()fromlinux/bitrev.h+ bitshift. Reduces code-repetition.Signed-off-by Uladzislau Koshchanka <[email protected]>--- lib/Kconfig | 1 + lib/packing.c | 16 ++-------------- 2 files changed, 3 insertions(+), 14 deletions(-)
Here is the summary with links:
- lib: packing: replace bit_reverse() with bitrev8()
https://git.kernel.org/netdev/net-next/c/1280d4b76f34
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html