kernel/bpf/tnum.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /* tnum: tracked (or tristate) numbers
   3  *
   4  * A tnum tracks knowledge about the bits of a value.  Each bit can be either
   5  * known (0 or 1), or unknown (x).  Arithmetic operations on tnums will
   6  * propagate the unknown bits such that the tnum result represents all the
   7  * possible results for possible values of the operands.
   8  */
   9 #include <linux/kernel.h>
  10 #include <linux/tnum.h>
  11
  12 #define TNUM(_v, _m)    (struct tnum){.value = _v, .mask = _m}
  13 /* A completely unknown value */
  14 const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
  15
  16 struct tnum tnum_const(u64 value)
  17 {
  18         return TNUM(value, 0);
  19 }
  20
  21 struct tnum tnum_range(u64 min, u64 max)
  22 {
  23         u64 chi = min ^ max, delta;
  24         u8 bits = fls64(chi);
  25
  26         /* special case, needed because 1ULL << 64 is undefined */
  27         if (bits > 63)
  28                 return tnum_unknown;
  29         /* e.g. if chi = 4, bits = 3, delta = (1<<3) - 1 = 7.
  30          * if chi = 0, bits = 0, delta = (1<<0) - 1 = 0, so we return
  31          *  constant min (since min == max).
  32          */
  33         delta = (1ULL << bits) - 1;
  34         return TNUM(min & ~delta, delta);
  35 }
  36
  37 struct tnum tnum_lshift(struct tnum a, u8 shift)
  38 {
  39         return TNUM(a.value << shift, a.mask << shift);
  40 }
  41
  42 struct tnum tnum_rshift(struct tnum a, u8 shift)
  43 {
  44         return TNUM(a.value >> shift, a.mask >> shift);
  45 }
  46
  47 struct tnum tnum_arshift(struct tnum a, u8 min_shift)
  48 {
  49         /* if a.value is negative, arithmetic shifting by minimum shift
  50          * will have larger negative offset compared to more shifting.
  51          * If a.value is nonnegative, arithmetic shifting by minimum shift
  52          * will have larger positive offset compare to more shifting.
  53          */
  54         return TNUM((s64)a.value >> min_shift, (s64)a.mask >> min_shift);
  55 }
  56
  57 struct tnum tnum_add(struct tnum a, struct tnum b)
  58 {
  59         u64 sm, sv, sigma, chi, mu;
  60
  61         sm = a.mask + b.mask;
  62         sv = a.value + b.value;
  63         sigma = sm + sv;
  64         chi = sigma ^ sv;
  65         mu = chi | a.mask | b.mask;
  66         return TNUM(sv & ~mu, mu);
  67 }
  68
  69 struct tnum tnum_sub(struct tnum a, struct tnum b)
  70 {
  71         u64 dv, alpha, beta, chi, mu;
  72
  73         dv = a.value - b.value;
  74         alpha = dv + a.mask;
  75         beta = dv - b.mask;
  76         chi = alpha ^ beta;
  77         mu = chi | a.mask | b.mask;
  78         return TNUM(dv & ~mu, mu);
  79 }
  80
  81 struct tnum tnum_and(struct tnum a, struct tnum b)
  82 {
  83         u64 alpha, beta, v;
  84
  85         alpha = a.value | a.mask;
  86         beta = b.value | b.mask;
  87         v = a.value & b.value;
  88         return TNUM(v, alpha & beta & ~v);
  89 }
  90
  91 struct tnum tnum_or(struct tnum a, struct tnum b)
  92 {
  93         u64 v, mu;
  94
  95         v = a.value | b.value;
  96         mu = a.mask | b.mask;
  97         return TNUM(v, mu & ~v);
  98 }
  99
 100 struct tnum tnum_xor(struct tnum a, struct tnum b)
 101 {
 102         u64 v, mu;
 103
 104         v = a.value ^ b.value;
 105         mu = a.mask | b.mask;
 106         return TNUM(v & ~mu, mu);
 107 }
 108
 109 /* half-multiply add: acc += (unknown * mask * value).
 110  * An intermediate step in the multiply algorithm.
 111  */
 112 static struct tnum hma(struct tnum acc, u64 value, u64 mask)
 113 {
 114         while (mask) {
 115                 if (mask & 1)
 116                         acc = tnum_add(acc, TNUM(0, value));
 117                 mask >>= 1;
 118                 value <<= 1;
 119         }
 120         return acc;
 121 }
 122
 123 struct tnum tnum_mul(struct tnum a, struct tnum b)
 124 {
 125         struct tnum acc;
 126         u64 pi;
 127
 128         pi = a.value * b.value;
 129         acc = hma(TNUM(pi, 0), a.mask, b.mask | b.value);
 130         return hma(acc, b.mask, a.value);
 131 }
 132
 133 /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
 134  * a 'known 0' - this will return a 'known 1' for that bit.
 135  */
 136 struct tnum tnum_intersect(struct tnum a, struct tnum b)
 137 {
 138         u64 v, mu;
 139
 140         v = a.value | b.value;
 141         mu = a.mask & b.mask;
 142         return TNUM(v & ~mu, mu);
 143 }
 144
 145 struct tnum tnum_cast(struct tnum a, u8 size)
 146 {
 147         a.value &= (1ULL << (size * 8)) - 1;
 148         a.mask &= (1ULL << (size * 8)) - 1;
 149         return a;
 150 }
 151
 152 bool tnum_is_aligned(struct tnum a, u64 size)
 153 {
 154         if (!size)
 155                 return true;
 156         return !((a.value | a.mask) & (size - 1));
 157 }
 158
 159 bool tnum_in(struct tnum a, struct tnum b)
 160 {
 161         if (b.mask & ~a.mask)
 162                 return false;
 163         b.value &= ~a.mask;
 164         return a.value == b.value;
 165 }
 166
 167 int tnum_strn(char *str, size_t size, struct tnum a)
 168 {
 169         return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
 170 }
 171 EXPORT_SYMBOL_GPL(tnum_strn);
 172
 173 int tnum_sbin(char *str, size_t size, struct tnum a)
 174 {
 175         size_t n;
 176
 177         for (n = 64; n; n--) {
 178                 if (n < size) {
 179                         if (a.mask & 1)
 180                                 str[n - 1] = 'x';
 181                         else if (a.value & 1)
 182                                 str[n - 1] = '1';
 183                         else
 184                                 str[n - 1] = '0';
 185                 }
 186                 a.mask >>= 1;
 187                 a.value >>= 1;
 188         }
 189         str[min(size - 1, (size_t)64)] = 0;
 190         return 64;
 191 }