linux/kernel/bpf/tnum.c

// SPDX-License-Identifier: GPL-2.0-only
/* tnum: tracked (or tristate) numbers
 *
 * A tnum tracks knowledge about the bits of a value.  Each bit can be either
 * known (0 or 1), or unknown (x).  Arithmetic operations on tnums will
 * propagate the unknown bits such that the tnum result represents all the
 * possible results for possible values of the operands.
 */
#include <linux/kernel.h>
#include <linux/tnum.h>

#define TNUM(_v, _m) …
/* A completely unknown value */
const struct tnum tnum_unknown = …;

struct tnum tnum_const(u64 value)
{ … }

struct tnum tnum_range(u64 min, u64 max)
{ … }

struct tnum tnum_lshift(struct tnum a, u8 shift)
{ … }

struct tnum tnum_rshift(struct tnum a, u8 shift)
{ … }

struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness)
{ … }

struct tnum tnum_add(struct tnum a, struct tnum b)
{ … }

struct tnum tnum_sub(struct tnum a, struct tnum b)
{ … }

struct tnum tnum_and(struct tnum a, struct tnum b)
{ … }

struct tnum tnum_or(struct tnum a, struct tnum b)
{ … }

struct tnum tnum_xor(struct tnum a, struct tnum b)
{ … }

/* Generate partial products by multiplying each bit in the multiplier (tnum a)
 * with the multiplicand (tnum b), and add the partial products after
 * appropriately bit-shifting them. Instead of directly performing tnum addition
 * on the generated partial products, equivalenty, decompose each partial
 * product into two tnums, consisting of the value-sum (acc_v) and the
 * mask-sum (acc_m) and then perform tnum addition on them. The following paper
 * explains the algorithm in more detail: https://arxiv.org/abs/2105.05398.
 */
struct tnum tnum_mul(struct tnum a, struct tnum b)
{ … }

/* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
 * a 'known 0' - this will return a 'known 1' for that bit.
 */
struct tnum tnum_intersect(struct tnum a, struct tnum b)
{ … }

struct tnum tnum_cast(struct tnum a, u8 size)
{ … }

bool tnum_is_aligned(struct tnum a, u64 size)
{ … }

bool tnum_in(struct tnum a, struct tnum b)
{ … }

int tnum_sbin(char *str, size_t size, struct tnum a)
{ … }

struct tnum tnum_subreg(struct tnum a)
{ … }

struct tnum tnum_clear_subreg(struct tnum a)
{ … }

struct tnum tnum_with_subreg(struct tnum reg, struct tnum subreg)
{ … }

struct tnum tnum_const_subreg(struct tnum a, u32 value)
{ … }