kernel/bpf/tnum.c

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