kernel/bpf/tnum.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /* tnum: tracked (or tristate) numbers
0003  *
0004  * A tnum tracks knowledge about the bits of a value.  Each bit can be either
0005  * known (0 or 1), or unknown (x).  Arithmetic operations on tnums will
0006  * propagate the unknown bits such that the tnum result represents all the
0007  * possible results for possible values of the operands.
0008  */
0009 #include <linux/kernel.h>
0010 #include <linux/tnum.h>
0011
0012 #define TNUM(_v, _m)    (struct tnum){.value = _v, .mask = _m}
0013 /* A completely unknown value */
0014 const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
0015
0016 struct tnum tnum_const(u64 value)
0017 {
0018     return TNUM(value, 0);
0019 }
0020
0021 struct tnum tnum_range(u64 min, u64 max)
0022 {
0023     u64 chi = min ^ max, delta;
0024     u8 bits = fls64(chi);
0025
0026     /* special case, needed because 1ULL << 64 is undefined */
0027     if (bits > 63)
0028         return tnum_unknown;
0029     /* e.g. if chi = 4, bits = 3, delta = (1<<3) - 1 = 7.
0030      * if chi = 0, bits = 0, delta = (1<<0) - 1 = 0, so we return
0031      *  constant min (since min == max).
0032      */
0033     delta = (1ULL << bits) - 1;
0034     return TNUM(min & ~delta, delta);
0035 }
0036
0037 struct tnum tnum_lshift(struct tnum a, u8 shift)
0038 {
0039     return TNUM(a.value << shift, a.mask << shift);
0040 }
0041
0042 struct tnum tnum_rshift(struct tnum a, u8 shift)
0043 {
0044     return TNUM(a.value >> shift, a.mask >> shift);
0045 }
0046
0047 struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness)
0048 {
0049     /* if a.value is negative, arithmetic shifting by minimum shift
0050      * will have larger negative offset compared to more shifting.
0051      * If a.value is nonnegative, arithmetic shifting by minimum shift
0052      * will have larger positive offset compare to more shifting.
0053      */
0054     if (insn_bitness == 32)
0055         return TNUM((u32)(((s32)a.value) >> min_shift),
0056                 (u32)(((s32)a.mask)  >> min_shift));
0057     else
0058         return TNUM((s64)a.value >> min_shift,
0059                 (s64)a.mask  >> min_shift);
0060 }
0061
0062 struct tnum tnum_add(struct tnum a, struct tnum b)
0063 {
0064     u64 sm, sv, sigma, chi, mu;
0065
0066     sm = a.mask + b.mask;
0067     sv = a.value + b.value;
0068     sigma = sm + sv;
0069     chi = sigma ^ sv;
0070     mu = chi | a.mask | b.mask;
0071     return TNUM(sv & ~mu, mu);
0072 }
0073
0074 struct tnum tnum_sub(struct tnum a, struct tnum b)
0075 {
0076     u64 dv, alpha, beta, chi, mu;
0077
0078     dv = a.value - b.value;
0079     alpha = dv + a.mask;
0080     beta = dv - b.mask;
0081     chi = alpha ^ beta;
0082     mu = chi | a.mask | b.mask;
0083     return TNUM(dv & ~mu, mu);
0084 }
0085
0086 struct tnum tnum_and(struct tnum a, struct tnum b)
0087 {
0088     u64 alpha, beta, v;
0089
0090     alpha = a.value | a.mask;
0091     beta = b.value | b.mask;
0092     v = a.value & b.value;
0093     return TNUM(v, alpha & beta & ~v);
0094 }
0095
0096 struct tnum tnum_or(struct tnum a, struct tnum b)
0097 {
0098     u64 v, mu;
0099
0100     v = a.value | b.value;
0101     mu = a.mask | b.mask;
0102     return TNUM(v, mu & ~v);
0103 }
0104
0105 struct tnum tnum_xor(struct tnum a, struct tnum b)
0106 {
0107     u64 v, mu;
0108
0109     v = a.value ^ b.value;
0110     mu = a.mask | b.mask;
0111     return TNUM(v & ~mu, mu);
0112 }
0113
0114 /* Generate partial products by multiplying each bit in the multiplier (tnum a)
0115  * with the multiplicand (tnum b), and add the partial products after
0116  * appropriately bit-shifting them. Instead of directly performing tnum addition
0117  * on the generated partial products, equivalenty, decompose each partial
0118  * product into two tnums, consisting of the value-sum (acc_v) and the
0119  * mask-sum (acc_m) and then perform tnum addition on them. The following paper
0120  * explains the algorithm in more detail: https://arxiv.org/abs/2105.05398.
0121  */
0122 struct tnum tnum_mul(struct tnum a, struct tnum b)
0123 {
0124     u64 acc_v = a.value * b.value;
0125     struct tnum acc_m = TNUM(0, 0);
0126
0127     while (a.value || a.mask) {
0128         /* LSB of tnum a is a certain 1 */
0129         if (a.value & 1)
0130             acc_m = tnum_add(acc_m, TNUM(0, b.mask));
0131         /* LSB of tnum a is uncertain */
0132         else if (a.mask & 1)
0133             acc_m = tnum_add(acc_m, TNUM(0, b.value | b.mask));
0134         /* Note: no case for LSB is certain 0 */
0135         a = tnum_rshift(a, 1);
0136         b = tnum_lshift(b, 1);
0137     }
0138     return tnum_add(TNUM(acc_v, 0), acc_m);
0139 }
0140
0141 /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
0142  * a 'known 0' - this will return a 'known 1' for that bit.
0143  */
0144 struct tnum tnum_intersect(struct tnum a, struct tnum b)
0145 {
0146     u64 v, mu;
0147
0148     v = a.value | b.value;
0149     mu = a.mask & b.mask;
0150     return TNUM(v & ~mu, mu);
0151 }
0152
0153 struct tnum tnum_cast(struct tnum a, u8 size)
0154 {
0155     a.value &= (1ULL << (size * 8)) - 1;
0156     a.mask &= (1ULL << (size * 8)) - 1;
0157     return a;
0158 }
0159
0160 bool tnum_is_aligned(struct tnum a, u64 size)
0161 {
0162     if (!size)
0163         return true;
0164     return !((a.value | a.mask) & (size - 1));
0165 }
0166
0167 bool tnum_in(struct tnum a, struct tnum b)
0168 {
0169     if (b.mask & ~a.mask)
0170         return false;
0171     b.value &= ~a.mask;
0172     return a.value == b.value;
0173 }
0174
0175 int tnum_strn(char *str, size_t size, struct tnum a)
0176 {
0177     return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
0178 }
0179 EXPORT_SYMBOL_GPL(tnum_strn);
0180
0181 int tnum_sbin(char *str, size_t size, struct tnum a)
0182 {
0183     size_t n;
0184
0185     for (n = 64; n; n--) {
0186         if (n < size) {
0187             if (a.mask & 1)
0188                 str[n - 1] = 'x';
0189             else if (a.value & 1)
0190                 str[n - 1] = '1';
0191             else
0192                 str[n - 1] = '0';
0193         }
0194         a.mask >>= 1;
0195         a.value >>= 1;
0196     }
0197     str[min(size - 1, (size_t)64)] = 0;
0198     return 64;
0199 }
0200
0201 struct tnum tnum_subreg(struct tnum a)
0202 {
0203     return tnum_cast(a, 4);
0204 }
0205
0206 struct tnum tnum_clear_subreg(struct tnum a)
0207 {
0208     return tnum_lshift(tnum_rshift(a, 32), 32);
0209 }
0210
0211 struct tnum tnum_const_subreg(struct tnum a, u32 value)
0212 {
0213     return tnum_or(tnum_clear_subreg(a), tnum_const(value));
0214 }