[v0,1/3] bpf: Introduce tnum_scast as a tnum native sign extension helper

Commit Message

Dimitar Kanaliev Jan. 30, 2025, 11:23 a.m. UTC

This patch introduces a new helper function - tnum_scast(), which
sign-extends a tnum from a smaller integer size to the full 64-bit bpf
register range.

This is achieved by:

Given a tnum (v, m) and target size S bytes:
  1) Mask value/mask to S bytes: val = v & mask, msk = m & mask
  2) If sign bit (bit S*8-1) is unknown (msk has bit set):
    - Extended bits become unknown (mask |= ~value_mask)
    - Sign possibilities constrain value (if sign could be 1, upper bits
     must allow both 0s and 1s)
   3) If sign bit is known:
    - Upper bits follow sign extension of val
    - Mask upper bits then follow sign extension of msk

a) When the sign bit is known:
Assume a tnum with value = 0xFF, mask = 0x00, size = 1, which corresponds
to an 8-bit subregister of value 0xFF. We extract the sign bit position,
compute the value mask, apply it to the lower bits and check the sign bit
at said position.

  s = size * 8 - 1 // 1 * 8 - 1 = 7.
  value_mask = (1ULL << (s + 1)) - 1; // (1 << (7 + 1)) - 1 = 0xFF
  new_value = a.value & value_mask; // 0xFF & 0xFF = 0xFF
  new_mask = a.mask & value_mask; // 0x00 & 0xFF = 0x00
  sign_bit_unknown = (0x00 >> 7) & 1 = 0;  // sign bit is known
  sign_bit_value   = (0xFF >> 7) & 1 = 1;  // with value 1

Because the sign bit is known to be 1, we sign-extend with 1s above bit 7,
so all upper bits [63,8] become 1, new_value in 64 bits is
0xFFFFFFFFFFFFFFFF and new_mask for those bits is 0 (since we know
for sure they are all 1). So after the tnum_scast call and the sign
extension, the tnum is (0xFFFFFFFFFFFFFFFF, 0x0000000000000000),
which corresponds to the 64-bit value -1.

b) When the sign bit is unknown:
Assume a tnum wih value = 0x7F, mask = 0x80, size = 1. In this case the
lower 8 bits [6,0] are known to be 0x7F or b(0111 1111). Bit 7 is
unknown (mask = 0x80), so it could be 0 or 1. This means the subregister
could be 0x7F (+127) or 0xFF (-1), or otherwise anythnig that differs in
bit 7. Following the same operations as the previous example, we get s = 7
and value_mask = 0xFF. Then:

  new_value = a.value & value_mask; // 0x7F & 0xFF = 0x7F
  new_mask = a.mask & value_mask; // 0x80 & 0xFF = 0x80
  sign_bit_unknown = (0x80 >> 7) & 1 = 1; // bit 7 is unknown
  // sign bit is unkown, so we treat upper bits [63,8] as unknown
  new_mask |= ~value_mask;

This leads to a new tnum with value=0x7F, mask=0xFFFFFFFFFFFFFF80
The lower 8 bits can be 0x7F or 0xFF, and the higher 56 bits are fully
unknown. In 64-bit form, this tnum can represent anything from:
0x000000000000007F (+127) if the sign bit is 0 and all higher bits are 0,
up to 0xFFFFFFFFFFFFFFFF (-1) if the sign bit and all higher bits are 1.

Signed-off-by: Dimitar Kanaliev <[e-mail]>
---
 include/linux/tnum.h |  3 +++
 kernel/bpf/tnum.c    | 29 +++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

Comments

Eduard Zingerman Jan. 30, 2025, 9:59 p.m. UTC | #1

On Thu, 2025-01-30 at 13:23 +0200, Dimitar Kanaliev wrote:

Hi Dimitar,

[...]

> +struct tnum tnum_scast(struct tnum a, u8 size)
> +{
> +	u64 s = size * 8 - 1;
> +	u64 sign_mask;
> +	u64 value_mask;
> +	u64 new_value, new_mask;
> +	u64 sign_bit_unknown, sign_bit_value;
> +	u64 mask;
> +
> +	if (size >= 8) {
> +		return a;
> +	}
> +
> +	sign_mask = 1ULL << s;
> +	value_mask = (1ULL << (s + 1)) - 1;
> +
> +	new_value = a.value & value_mask;
> +	new_mask = a.mask & value_mask;
> +
> +	sign_bit_unknown = (a.mask >> s) & 1;
> +	sign_bit_value = (a.value >> s) & 1;
> +
> +	mask = ~value_mask;
> +	new_mask |= mask & (0 - sign_bit_unknown);
> +	new_value |= mask & (0 - ((sign_bit_unknown ^ 1) & sign_bit_value));
> +
> +	return TNUM(new_value, new_mask);
> +}

So, effectively what you want to achieve here:
- pick a sign bit SM from mask and set signed extended bits of mask to SM
- pick a sign bit SV from value and set signed extended bits of value to SV
right?

I think this could be done a bit simpler, e.g.:

struct tnum tnum_scast(struct tnum a, u8 size)
{
	u8 s = 64 - size * 8;
	u64 value, mask;

	if (size >= 8)
		return a;

	value = ((s64)a.value << s) >> s;
	mask = ((s64)a.mask << s) >> s;
	return TNUM(value, mask);
}

wdyt?

Patch

diff --git a/include/linux/tnum.h b/include/linux/tnum.h
index 3c13240077b8..6933db04c9ee 100644
--- a/include/linux/tnum.h
+++ b/include/linux/tnum.h
@@ -55,6 +55,9 @@  struct tnum tnum_intersect(struct tnum a, struct tnum b);
 /* Return @a with all but the lowest @size bytes cleared */
 struct tnum tnum_cast(struct tnum a, u8 size);
 
+/* Return @a sign-extended from @size bytes */
+struct tnum tnum_scast(struct tnum a, u8 size);
+
 /* Returns true if @a is a known constant */
 static inline bool tnum_is_const(struct tnum a)
 {
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 9dbc31b25e3d..cb29dbc793d4 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -157,6 +157,35 @@  struct tnum tnum_cast(struct tnum a, u8 size)
 	return a;
 }
 
+struct tnum tnum_scast(struct tnum a, u8 size)
+{
+	u64 s = size * 8 - 1;
+	u64 sign_mask;
+	u64 value_mask;
+	u64 new_value, new_mask;
+	u64 sign_bit_unknown, sign_bit_value;
+	u64 mask;
+
+	if (size >= 8) {
+		return a;
+	}
+
+	sign_mask = 1ULL << s;
+	value_mask = (1ULL << (s + 1)) - 1;
+
+	new_value = a.value & value_mask;
+	new_mask = a.mask & value_mask;
+
+	sign_bit_unknown = (a.mask >> s) & 1;
+	sign_bit_value = (a.value >> s) & 1;
+
+	mask = ~value_mask;
+	new_mask |= mask & (0 - sign_bit_unknown);
+	new_value |= mask & (0 - ((sign_bit_unknown ^ 1) & sign_bit_value));
+
+	return TNUM(new_value, new_mask);
+}
+
 bool tnum_is_aligned(struct tnum a, u64 size)
 {
 	if (!size)