nft_set_pipapo.h 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. #ifndef _NFT_SET_PIPAPO_H
  3. #include <linux/log2.h>
  4. #include <net/ipv6.h> /* For the maximum length of a field */
  5. /* Count of concatenated fields depends on count of 32-bit nftables registers */
  6. #define NFT_PIPAPO_MAX_FIELDS NFT_REG32_COUNT
  7. /* Restrict usage to multiple fields, make sure rbtree is used otherwise */
  8. #define NFT_PIPAPO_MIN_FIELDS 2
  9. /* Largest supported field size */
  10. #define NFT_PIPAPO_MAX_BYTES (sizeof(struct in6_addr))
  11. #define NFT_PIPAPO_MAX_BITS (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
  12. /* Bits to be grouped together in table buckets depending on set size */
  13. #define NFT_PIPAPO_GROUP_BITS_INIT NFT_PIPAPO_GROUP_BITS_SMALL_SET
  14. #define NFT_PIPAPO_GROUP_BITS_SMALL_SET 8
  15. #define NFT_PIPAPO_GROUP_BITS_LARGE_SET 4
  16. #define NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4 \
  17. BUILD_BUG_ON((NFT_PIPAPO_GROUP_BITS_SMALL_SET != 8) || \
  18. (NFT_PIPAPO_GROUP_BITS_LARGE_SET != 4))
  19. #define NFT_PIPAPO_GROUPS_PER_BYTE(f) (BITS_PER_BYTE / (f)->bb)
  20. /* If a lookup table gets bigger than NFT_PIPAPO_LT_SIZE_HIGH, switch to the
  21. * small group width, and switch to the big group width if the table gets
  22. * smaller than NFT_PIPAPO_LT_SIZE_LOW.
  23. *
  24. * Picking 2MiB as threshold (for a single table) avoids as much as possible
  25. * crossing page boundaries on most architectures (x86-64 and MIPS huge pages,
  26. * ARMv7 supersections, POWER "large" pages, SPARC Level 1 regions, etc.), which
  27. * keeps performance nice in case kvmalloc() gives us non-contiguous areas.
  28. */
  29. #define NFT_PIPAPO_LT_SIZE_THRESHOLD (1 << 21)
  30. #define NFT_PIPAPO_LT_SIZE_HYSTERESIS (1 << 16)
  31. #define NFT_PIPAPO_LT_SIZE_HIGH NFT_PIPAPO_LT_SIZE_THRESHOLD
  32. #define NFT_PIPAPO_LT_SIZE_LOW NFT_PIPAPO_LT_SIZE_THRESHOLD - \
  33. NFT_PIPAPO_LT_SIZE_HYSTERESIS
  34. /* Fields are padded to 32 bits in input registers */
  35. #define NFT_PIPAPO_GROUPS_PADDED_SIZE(f) \
  36. (round_up((f)->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f), sizeof(u32)))
  37. #define NFT_PIPAPO_GROUPS_PADDING(f) \
  38. (NFT_PIPAPO_GROUPS_PADDED_SIZE(f) - (f)->groups / \
  39. NFT_PIPAPO_GROUPS_PER_BYTE(f))
  40. /* Number of buckets given by 2 ^ n, with n bucket bits */
  41. #define NFT_PIPAPO_BUCKETS(bb) (1 << (bb))
  42. /* Each n-bit range maps to up to n * 2 rules */
  43. #define NFT_PIPAPO_MAP_NBITS (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
  44. /* Use the rest of mapping table buckets for rule indices, but it makes no sense
  45. * to exceed 32 bits
  46. */
  47. #if BITS_PER_LONG == 64
  48. #define NFT_PIPAPO_MAP_TOBITS 32
  49. #else
  50. #define NFT_PIPAPO_MAP_TOBITS (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
  51. #endif
  52. /* ...which gives us the highest allowed index for a rule */
  53. #define NFT_PIPAPO_RULE0_MAX ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
  54. - (1UL << NFT_PIPAPO_MAP_NBITS))
  55. /* Definitions for vectorised implementations */
  56. #ifdef NFT_PIPAPO_ALIGN
  57. #define NFT_PIPAPO_ALIGN_HEADROOM \
  58. (NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
  59. #define NFT_PIPAPO_LT_ALIGN(lt) (PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
  60. #define NFT_PIPAPO_LT_ASSIGN(field, x) \
  61. do { \
  62. (field)->lt_aligned = NFT_PIPAPO_LT_ALIGN(x); \
  63. (field)->lt = (x); \
  64. } while (0)
  65. #else
  66. #define NFT_PIPAPO_ALIGN_HEADROOM 0
  67. #define NFT_PIPAPO_LT_ALIGN(lt) (lt)
  68. #define NFT_PIPAPO_LT_ASSIGN(field, x) ((field)->lt = (x))
  69. #endif /* NFT_PIPAPO_ALIGN */
  70. #define nft_pipapo_for_each_field(field, index, match) \
  71. for ((field) = (match)->f, (index) = 0; \
  72. (index) < (match)->field_count; \
  73. (index)++, (field)++)
  74. /**
  75. * union nft_pipapo_map_bucket - Bucket of mapping table
  76. * @to: First rule number (in next field) this rule maps to
  77. * @n: Number of rules (in next field) this rule maps to
  78. * @e: If there's no next field, pointer to element this rule maps to
  79. */
  80. union nft_pipapo_map_bucket {
  81. struct {
  82. #if BITS_PER_LONG == 64
  83. static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
  84. u32 to;
  85. static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
  86. u32 n;
  87. #else
  88. unsigned long to:NFT_PIPAPO_MAP_TOBITS;
  89. unsigned long n:NFT_PIPAPO_MAP_NBITS;
  90. #endif
  91. };
  92. struct nft_pipapo_elem *e;
  93. };
  94. /**
  95. * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
  96. * @groups: Amount of bit groups
  97. * @rules: Number of inserted rules
  98. * @bsize: Size of each bucket in lookup table, in longs
  99. * @bb: Number of bits grouped together in lookup table buckets
  100. * @lt: Lookup table: 'groups' rows of buckets
  101. * @lt_aligned: Version of @lt aligned to NFT_PIPAPO_ALIGN bytes
  102. * @mt: Mapping table: one bucket per rule
  103. */
  104. struct nft_pipapo_field {
  105. int groups;
  106. unsigned long rules;
  107. size_t bsize;
  108. int bb;
  109. #ifdef NFT_PIPAPO_ALIGN
  110. unsigned long *lt_aligned;
  111. #endif
  112. unsigned long *lt;
  113. union nft_pipapo_map_bucket *mt;
  114. };
  115. /**
  116. * struct nft_pipapo_match - Data used for lookup and matching
  117. * @field_count Amount of fields in set
  118. * @scratch: Preallocated per-CPU maps for partial matching results
  119. * @scratch_aligned: Version of @scratch aligned to NFT_PIPAPO_ALIGN bytes
  120. * @bsize_max: Maximum lookup table bucket size of all fields, in longs
  121. * @rcu Matching data is swapped on commits
  122. * @f: Fields, with lookup and mapping tables
  123. */
  124. struct nft_pipapo_match {
  125. int field_count;
  126. #ifdef NFT_PIPAPO_ALIGN
  127. unsigned long * __percpu *scratch_aligned;
  128. #endif
  129. unsigned long * __percpu *scratch;
  130. size_t bsize_max;
  131. struct rcu_head rcu;
  132. struct nft_pipapo_field f[];
  133. };
  134. /**
  135. * struct nft_pipapo - Representation of a set
  136. * @match: Currently in-use matching data
  137. * @clone: Copy where pending insertions and deletions are kept
  138. * @width: Total bytes to be matched for one packet, including padding
  139. * @dirty: Working copy has pending insertions or deletions
  140. * @last_gc: Timestamp of last garbage collection run, jiffies
  141. */
  142. struct nft_pipapo {
  143. struct nft_pipapo_match __rcu *match;
  144. struct nft_pipapo_match *clone;
  145. int width;
  146. bool dirty;
  147. unsigned long last_gc;
  148. };
  149. struct nft_pipapo_elem;
  150. /**
  151. * struct nft_pipapo_elem - API-facing representation of single set element
  152. * @ext: nftables API extensions
  153. */
  154. struct nft_pipapo_elem {
  155. struct nft_set_ext ext;
  156. };
  157. int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
  158. union nft_pipapo_map_bucket *mt, bool match_only);
  159. bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
  160. const u32 *key, const struct nft_set_ext **ext);
  161. /**
  162. * pipapo_and_field_buckets_4bit() - Intersect 4-bit buckets
  163. * @f: Field including lookup table
  164. * @dst: Area to store result
  165. * @data: Input data selecting table buckets
  166. */
  167. static inline void pipapo_and_field_buckets_4bit(struct nft_pipapo_field *f,
  168. unsigned long *dst,
  169. const u8 *data)
  170. {
  171. unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
  172. int group;
  173. for (group = 0; group < f->groups; group += BITS_PER_BYTE / 4, data++) {
  174. u8 v;
  175. v = *data >> 4;
  176. __bitmap_and(dst, dst, lt + v * f->bsize,
  177. f->bsize * BITS_PER_LONG);
  178. lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
  179. v = *data & 0x0f;
  180. __bitmap_and(dst, dst, lt + v * f->bsize,
  181. f->bsize * BITS_PER_LONG);
  182. lt += f->bsize * NFT_PIPAPO_BUCKETS(4);
  183. }
  184. }
  185. /**
  186. * pipapo_and_field_buckets_8bit() - Intersect 8-bit buckets
  187. * @f: Field including lookup table
  188. * @dst: Area to store result
  189. * @data: Input data selecting table buckets
  190. */
  191. static inline void pipapo_and_field_buckets_8bit(struct nft_pipapo_field *f,
  192. unsigned long *dst,
  193. const u8 *data)
  194. {
  195. unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
  196. int group;
  197. for (group = 0; group < f->groups; group++, data++) {
  198. __bitmap_and(dst, dst, lt + *data * f->bsize,
  199. f->bsize * BITS_PER_LONG);
  200. lt += f->bsize * NFT_PIPAPO_BUCKETS(8);
  201. }
  202. }
  203. /**
  204. * pipapo_estimate_size() - Estimate worst-case for set size
  205. * @desc: Set description, element count and field description used here
  206. *
  207. * The size for this set type can vary dramatically, as it depends on the number
  208. * of rules (composing netmasks) the entries expand to. We compute the worst
  209. * case here.
  210. *
  211. * In general, for a non-ranged entry or a single composing netmask, we need
  212. * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
  213. * is, each input bit needs four bits of matching data), plus a bucket in the
  214. * mapping table for each field.
  215. *
  216. * Return: worst-case set size in bytes, 0 on any overflow
  217. */
  218. static u64 pipapo_estimate_size(const struct nft_set_desc *desc)
  219. {
  220. unsigned long entry_size;
  221. u64 size;
  222. int i;
  223. for (i = 0, entry_size = 0; i < desc->field_count; i++) {
  224. unsigned long rules;
  225. if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
  226. return 0;
  227. /* Worst-case ranges for each concatenated field: each n-bit
  228. * field can expand to up to n * 2 rules in each bucket, and
  229. * each rule also needs a mapping bucket.
  230. */
  231. rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
  232. entry_size += rules *
  233. NFT_PIPAPO_BUCKETS(NFT_PIPAPO_GROUP_BITS_INIT) /
  234. BITS_PER_BYTE;
  235. entry_size += rules * sizeof(union nft_pipapo_map_bucket);
  236. }
  237. /* Rules in lookup and mapping tables are needed for each entry */
  238. size = desc->size * entry_size;
  239. if (size && div_u64(size, desc->size) != entry_size)
  240. return 0;
  241. size += sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match) * 2;
  242. size += sizeof(struct nft_pipapo_field) * desc->field_count;
  243. return size;
  244. }
  245. #endif /* _NFT_SET_PIPAPO_H */