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_lshift(struct tnum a, u8 shift)
  21 {
  22         return TNUM(a.value << shift, a.mask << shift);
  23 }
  24
  25 struct tnum tnum_rshift(struct tnum a, u8 shift)
  26 {
  27         return TNUM(a.value >> shift, a.mask >> shift);
  28 }
  29
  30 struct tnum tnum_add(struct tnum a, struct tnum b)
  31 {
  32         u64 sm, sv, sigma, chi, mu;
  33
  34         sm = a.mask + b.mask;
  35         sv = a.value + b.value;
  36         sigma = sm + sv;
  37         chi = sigma ^ sv;
  38         mu = chi | a.mask | b.mask;
  39         return TNUM(sv & ~mu, mu);
  40 }
  41
  42 struct tnum tnum_sub(struct tnum a, struct tnum b)
  43 {
  44         u64 dv, alpha, beta, chi, mu;
  45
  46         dv = a.value - b.value;
  47         alpha = dv + a.mask;
  48         beta = dv - b.mask;
  49         chi = alpha ^ beta;
  50         mu = chi | a.mask | b.mask;
  51         return TNUM(dv & ~mu, mu);
  52 }
  53
  54 struct tnum tnum_and(struct tnum a, struct tnum b)
  55 {
  56         u64 alpha, beta, v;
  57
  58         alpha = a.value | a.mask;
  59         beta = b.value | b.mask;
  60         v = a.value & b.value;
  61         return TNUM(v, alpha & beta & ~v);
  62 }
  63
  64 struct tnum tnum_or(struct tnum a, struct tnum b)
  65 {
  66         u64 v, mu;
  67
  68         v = a.value | b.value;
  69         mu = a.mask | b.mask;
  70         return TNUM(v, mu & ~v);
  71 }
  72
  73 struct tnum tnum_xor(struct tnum a, struct tnum b)
  74 {
  75         u64 v, mu;
  76
  77         v = a.value ^ b.value;
  78         mu = a.mask | b.mask;
  79         return TNUM(v & ~mu, mu);
  80 }
  81
  82 /* half-multiply add: acc += (unknown * mask * value).
  83  * An intermediate step in the multiply algorithm.
  84  */
  85 static struct tnum hma(struct tnum acc, u64 value, u64 mask)
  86 {
  87         while (mask) {
  88                 if (mask & 1)
  89                         acc = tnum_add(acc, TNUM(0, value));
  90                 mask >>= 1;
  91                 value <<= 1;
  92         }
  93         return acc;
  94 }
  95
  96 struct tnum tnum_mul(struct tnum a, struct tnum b)
  97 {
  98         struct tnum acc;
  99         u64 pi;
 100
 101         pi = a.value * b.value;
 102         acc = hma(TNUM(pi, 0), a.mask, b.mask | b.value);
 103         return hma(acc, b.mask, a.value);
 104 }
 105
 106 /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
 107  * a 'known 0' - this will return a 'known 1' for that bit.
 108  */
 109 struct tnum tnum_intersect(struct tnum a, struct tnum b)
 110 {
 111         u64 v, mu;
 112
 113         v = a.value | b.value;
 114         mu = a.mask & b.mask;
 115         return TNUM(v & ~mu, mu);
 116 }
 117
 118 struct tnum tnum_cast(struct tnum a, u8 size)
 119 {
 120         a.value &= (1ULL << (size * 8)) - 1;
 121         a.mask &= (1ULL << (size * 8)) - 1;
 122         return a;
 123 }
 124
 125 bool tnum_is_aligned(struct tnum a, u64 size)
 126 {
 127         if (!size)
 128                 return true;
 129         return !((a.value | a.mask) & (size - 1));
 130 }
 131
 132 bool tnum_in(struct tnum a, struct tnum b)
 133 {
 134         if (b.mask & ~a.mask)
 135                 return false;
 136         b.value &= ~a.mask;
 137         return a.value == b.value;
 138 }
 139
 140 int tnum_strn(char *str, size_t size, struct tnum a)
 141 {
 142         return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
 143 }
 144 EXPORT_SYMBOL_GPL(tnum_strn);
 145
 146 int tnum_sbin(char *str, size_t size, struct tnum a)
 147 {
 148         size_t n;
 149
 150         for (n = 64; n; n--) {
 151                 if (n < size) {
 152                         if (a.mask & 1)
 153                                 str[n - 1] = 'x';
 154                         else if (a.value & 1)
 155                                 str[n - 1] = '1';
 156                         else
 157                                 str[n - 1] = '0';
 158                 }
 159                 a.mask >>= 1;
 160                 a.value >>= 1;
 161         }
 162         str[min(size - 1, (size_t)64)] = 0;
 163         return 64;
 164 }