nft_set_pipapo_avx2.c 39 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /* PIPAPO: PIle PAcket POlicies: AVX2 packet lookup routines
  3. *
  4. * Copyright (c) 2019-2020 Red Hat GmbH
  5. *
  6. * Author: Stefano Brivio <sbrivio@redhat.com>
  7. */
  8. #include <linux/kernel.h>
  9. #include <linux/init.h>
  10. #include <linux/module.h>
  11. #include <linux/netlink.h>
  12. #include <linux/netfilter.h>
  13. #include <linux/netfilter/nf_tables.h>
  14. #include <net/netfilter/nf_tables_core.h>
  15. #include <uapi/linux/netfilter/nf_tables.h>
  16. #include <linux/bitmap.h>
  17. #include <linux/bitops.h>
  18. #include <linux/compiler.h>
  19. #include <asm/fpu/api.h>
  20. #include "nft_set_pipapo_avx2.h"
  21. #include "nft_set_pipapo.h"
  22. #define NFT_PIPAPO_LONGS_PER_M256 (XSAVE_YMM_SIZE / BITS_PER_LONG)
  23. /* Load from memory into YMM register with non-temporal hint ("stream load"),
  24. * that is, don't fetch lines from memory into the cache. This avoids pushing
  25. * precious packet data out of the cache hierarchy, and is appropriate when:
  26. *
  27. * - loading buckets from lookup tables, as they are not going to be used
  28. * again before packets are entirely classified
  29. *
  30. * - loading the result bitmap from the previous field, as it's never used
  31. * again
  32. */
  33. #define NFT_PIPAPO_AVX2_LOAD(reg, loc) \
  34. asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc))
  35. /* Stream a single lookup table bucket into YMM register given lookup table,
  36. * group index, value of packet bits, bucket size.
  37. */
  38. #define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize) \
  39. NFT_PIPAPO_AVX2_LOAD(reg, \
  40. lt[((group) * NFT_PIPAPO_BUCKETS(4) + \
  41. (v)) * (bsize)])
  42. #define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize) \
  43. NFT_PIPAPO_AVX2_LOAD(reg, \
  44. lt[((group) * NFT_PIPAPO_BUCKETS(8) + \
  45. (v)) * (bsize)])
  46. /* Bitwise AND: the staple operation of this algorithm */
  47. #define NFT_PIPAPO_AVX2_AND(dst, a, b) \
  48. asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst)
  49. /* Jump to label if @reg is zero */
  50. #define NFT_PIPAPO_AVX2_NOMATCH_GOTO(reg, label) \
  51. asm_volatile_goto("vptest %%ymm" #reg ", %%ymm" #reg ";" \
  52. "je %l[" #label "]" : : : : label)
  53. /* Store 256 bits from YMM register into memory. Contrary to bucket load
  54. * operation, we don't bypass the cache here, as stored matching results
  55. * are always used shortly after.
  56. */
  57. #define NFT_PIPAPO_AVX2_STORE(loc, reg) \
  58. asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc))
  59. /* Zero out a complete YMM register, @reg */
  60. #define NFT_PIPAPO_AVX2_ZERO(reg) \
  61. asm volatile("vpxor %ymm" #reg ", %ymm" #reg ", %ymm" #reg)
  62. /* Current working bitmap index, toggled between field matches */
  63. static DEFINE_PER_CPU(bool, nft_pipapo_avx2_scratch_index);
  64. /**
  65. * nft_pipapo_avx2_prepare() - Prepare before main algorithm body
  66. *
  67. * This zeroes out ymm15, which is later used whenever we need to clear a
  68. * memory location, by storing its content into memory.
  69. */
  70. static void nft_pipapo_avx2_prepare(void)
  71. {
  72. NFT_PIPAPO_AVX2_ZERO(15);
  73. }
  74. /**
  75. * nft_pipapo_avx2_fill() - Fill a bitmap region with ones
  76. * @data: Base memory area
  77. * @start: First bit to set
  78. * @len: Count of bits to fill
  79. *
  80. * This is nothing else than a version of bitmap_set(), as used e.g. by
  81. * pipapo_refill(), tailored for the microarchitectures using it and better
  82. * suited for the specific usage: it's very likely that we'll set a small number
  83. * of bits, not crossing a word boundary, and correct branch prediction is
  84. * critical here.
  85. *
  86. * This function doesn't actually use any AVX2 instruction.
  87. */
  88. static void nft_pipapo_avx2_fill(unsigned long *data, int start, int len)
  89. {
  90. int offset = start % BITS_PER_LONG;
  91. unsigned long mask;
  92. data += start / BITS_PER_LONG;
  93. if (likely(len == 1)) {
  94. *data |= BIT(offset);
  95. return;
  96. }
  97. if (likely(len < BITS_PER_LONG || offset)) {
  98. if (likely(len + offset <= BITS_PER_LONG)) {
  99. *data |= GENMASK(len - 1 + offset, offset);
  100. return;
  101. }
  102. *data |= ~0UL << offset;
  103. len -= BITS_PER_LONG - offset;
  104. data++;
  105. if (len <= BITS_PER_LONG) {
  106. mask = ~0UL >> (BITS_PER_LONG - len);
  107. *data |= mask;
  108. return;
  109. }
  110. }
  111. memset(data, 0xff, len / BITS_PER_BYTE);
  112. data += len / BITS_PER_LONG;
  113. len %= BITS_PER_LONG;
  114. if (len)
  115. *data |= ~0UL >> (BITS_PER_LONG - len);
  116. }
  117. /**
  118. * nft_pipapo_avx2_refill() - Scan bitmap, select mapping table item, set bits
  119. * @offset: Start from given bitmap (equivalent to bucket) offset, in longs
  120. * @map: Bitmap to be scanned for set bits
  121. * @dst: Destination bitmap
  122. * @mt: Mapping table containing bit set specifiers
  123. * @len: Length of bitmap in longs
  124. * @last: Return index of first set bit, if this is the last field
  125. *
  126. * This is an alternative implementation of pipapo_refill() suitable for usage
  127. * with AVX2 lookup routines: we know there are four words to be scanned, at
  128. * a given offset inside the map, for each matching iteration.
  129. *
  130. * This function doesn't actually use any AVX2 instruction.
  131. *
  132. * Return: first set bit index if @last, index of first filled word otherwise.
  133. */
  134. static int nft_pipapo_avx2_refill(int offset, unsigned long *map,
  135. unsigned long *dst,
  136. union nft_pipapo_map_bucket *mt, bool last)
  137. {
  138. int ret = -1;
  139. #define NFT_PIPAPO_AVX2_REFILL_ONE_WORD(x) \
  140. do { \
  141. while (map[(x)]) { \
  142. int r = __builtin_ctzl(map[(x)]); \
  143. int i = (offset + (x)) * BITS_PER_LONG + r; \
  144. \
  145. if (last) \
  146. return i; \
  147. \
  148. nft_pipapo_avx2_fill(dst, mt[i].to, mt[i].n); \
  149. \
  150. if (ret == -1) \
  151. ret = mt[i].to; \
  152. \
  153. map[(x)] &= ~(1UL << r); \
  154. } \
  155. } while (0)
  156. NFT_PIPAPO_AVX2_REFILL_ONE_WORD(0);
  157. NFT_PIPAPO_AVX2_REFILL_ONE_WORD(1);
  158. NFT_PIPAPO_AVX2_REFILL_ONE_WORD(2);
  159. NFT_PIPAPO_AVX2_REFILL_ONE_WORD(3);
  160. #undef NFT_PIPAPO_AVX2_REFILL_ONE_WORD
  161. return ret;
  162. }
  163. /**
  164. * nft_pipapo_avx2_lookup_4b_2() - AVX2-based lookup for 2 four-bit groups
  165. * @map: Previous match result, used as initial bitmap
  166. * @fill: Destination bitmap to be filled with current match result
  167. * @f: Field, containing lookup and mapping tables
  168. * @offset: Ignore buckets before the given index, no bits are filled there
  169. * @pkt: Packet data, pointer to input nftables register
  170. * @first: If this is the first field, don't source previous result
  171. * @last: Last field: stop at the first match and return bit index
  172. *
  173. * Load buckets from lookup table corresponding to the values of each 4-bit
  174. * group of packet bytes, and perform a bitwise intersection between them. If
  175. * this is the first field in the set, simply AND the buckets together
  176. * (equivalent to using an all-ones starting bitmap), use the provided starting
  177. * bitmap otherwise. Then call nft_pipapo_avx2_refill() to generate the next
  178. * working bitmap, @fill.
  179. *
  180. * This is used for 8-bit fields (i.e. protocol numbers).
  181. *
  182. * Out-of-order (and superscalar) execution is vital here, so it's critical to
  183. * avoid false data dependencies. CPU and compiler could (mostly) take care of
  184. * this on their own, but the operation ordering is explicitly given here with
  185. * a likely execution order in mind, to highlight possible stalls. That's why
  186. * a number of logically distinct operations (i.e. loading buckets, intersecting
  187. * buckets) are interleaved.
  188. *
  189. * Return: -1 on no match, rule index of match if @last, otherwise first long
  190. * word index to be checked next (i.e. first filled word).
  191. */
  192. static int nft_pipapo_avx2_lookup_4b_2(unsigned long *map, unsigned long *fill,
  193. struct nft_pipapo_field *f, int offset,
  194. const u8 *pkt, bool first, bool last)
  195. {
  196. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  197. u8 pg[2] = { pkt[0] >> 4, pkt[0] & 0xf };
  198. unsigned long *lt = f->lt, bsize = f->bsize;
  199. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  200. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  201. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  202. if (first) {
  203. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  204. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize);
  205. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  206. } else {
  207. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  208. NFT_PIPAPO_AVX2_LOAD(2, map[i_ul]);
  209. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize);
  210. NFT_PIPAPO_AVX2_NOMATCH_GOTO(2, nothing);
  211. NFT_PIPAPO_AVX2_AND(3, 0, 1);
  212. NFT_PIPAPO_AVX2_AND(4, 2, 3);
  213. }
  214. NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch);
  215. NFT_PIPAPO_AVX2_STORE(map[i_ul], 4);
  216. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  217. if (last)
  218. return b;
  219. if (unlikely(ret == -1))
  220. ret = b / XSAVE_YMM_SIZE;
  221. continue;
  222. nomatch:
  223. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  224. nothing:
  225. ;
  226. }
  227. return ret;
  228. }
  229. /**
  230. * nft_pipapo_avx2_lookup_4b_4() - AVX2-based lookup for 4 four-bit groups
  231. * @map: Previous match result, used as initial bitmap
  232. * @fill: Destination bitmap to be filled with current match result
  233. * @f: Field, containing lookup and mapping tables
  234. * @offset: Ignore buckets before the given index, no bits are filled there
  235. * @pkt: Packet data, pointer to input nftables register
  236. * @first: If this is the first field, don't source previous result
  237. * @last: Last field: stop at the first match and return bit index
  238. *
  239. * See nft_pipapo_avx2_lookup_4b_2().
  240. *
  241. * This is used for 16-bit fields (i.e. ports).
  242. *
  243. * Return: -1 on no match, rule index of match if @last, otherwise first long
  244. * word index to be checked next (i.e. first filled word).
  245. */
  246. static int nft_pipapo_avx2_lookup_4b_4(unsigned long *map, unsigned long *fill,
  247. struct nft_pipapo_field *f, int offset,
  248. const u8 *pkt, bool first, bool last)
  249. {
  250. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  251. u8 pg[4] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf };
  252. unsigned long *lt = f->lt, bsize = f->bsize;
  253. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  254. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  255. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  256. if (first) {
  257. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  258. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize);
  259. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 2, pg[2], bsize);
  260. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 3, pg[3], bsize);
  261. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  262. NFT_PIPAPO_AVX2_AND(5, 2, 3);
  263. NFT_PIPAPO_AVX2_AND(7, 4, 5);
  264. } else {
  265. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  266. NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
  267. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize);
  268. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize);
  269. NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize);
  270. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  271. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing);
  272. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  273. NFT_PIPAPO_AVX2_AND(7, 4, 5);
  274. /* Stall */
  275. NFT_PIPAPO_AVX2_AND(7, 6, 7);
  276. }
  277. /* Stall */
  278. NFT_PIPAPO_AVX2_NOMATCH_GOTO(7, nomatch);
  279. NFT_PIPAPO_AVX2_STORE(map[i_ul], 7);
  280. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  281. if (last)
  282. return b;
  283. if (unlikely(ret == -1))
  284. ret = b / XSAVE_YMM_SIZE;
  285. continue;
  286. nomatch:
  287. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  288. nothing:
  289. ;
  290. }
  291. return ret;
  292. }
  293. /**
  294. * nft_pipapo_avx2_lookup_4b_8() - AVX2-based lookup for 8 four-bit groups
  295. * @map: Previous match result, used as initial bitmap
  296. * @fill: Destination bitmap to be filled with current match result
  297. * @f: Field, containing lookup and mapping tables
  298. * @offset: Ignore buckets before the given index, no bits are filled there
  299. * @pkt: Packet data, pointer to input nftables register
  300. * @first: If this is the first field, don't source previous result
  301. * @last: Last field: stop at the first match and return bit index
  302. *
  303. * See nft_pipapo_avx2_lookup_4b_2().
  304. *
  305. * This is used for 32-bit fields (i.e. IPv4 addresses).
  306. *
  307. * Return: -1 on no match, rule index of match if @last, otherwise first long
  308. * word index to be checked next (i.e. first filled word).
  309. */
  310. static int nft_pipapo_avx2_lookup_4b_8(unsigned long *map, unsigned long *fill,
  311. struct nft_pipapo_field *f, int offset,
  312. const u8 *pkt, bool first, bool last)
  313. {
  314. u8 pg[8] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf,
  315. pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf,
  316. };
  317. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  318. unsigned long *lt = f->lt, bsize = f->bsize;
  319. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  320. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  321. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  322. if (first) {
  323. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  324. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 1, pg[1], bsize);
  325. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 2, pg[2], bsize);
  326. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 3, pg[3], bsize);
  327. NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 4, pg[4], bsize);
  328. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  329. NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 5, pg[5], bsize);
  330. NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 6, pg[6], bsize);
  331. NFT_PIPAPO_AVX2_AND(8, 2, 3);
  332. NFT_PIPAPO_AVX2_AND(9, 4, 5);
  333. NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 7, pg[7], bsize);
  334. NFT_PIPAPO_AVX2_AND(11, 6, 7);
  335. NFT_PIPAPO_AVX2_AND(12, 8, 9);
  336. NFT_PIPAPO_AVX2_AND(13, 10, 11);
  337. /* Stall */
  338. NFT_PIPAPO_AVX2_AND(1, 12, 13);
  339. } else {
  340. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 0, pg[0], bsize);
  341. NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
  342. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize);
  343. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize);
  344. NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize);
  345. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing);
  346. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  347. NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 4, pg[4], bsize);
  348. NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize);
  349. NFT_PIPAPO_AVX2_AND(8, 2, 3);
  350. NFT_PIPAPO_AVX2_BUCKET_LOAD4(9, lt, 6, pg[6], bsize);
  351. NFT_PIPAPO_AVX2_AND(10, 4, 5);
  352. NFT_PIPAPO_AVX2_BUCKET_LOAD4(11, lt, 7, pg[7], bsize);
  353. NFT_PIPAPO_AVX2_AND(12, 6, 7);
  354. NFT_PIPAPO_AVX2_AND(13, 8, 9);
  355. NFT_PIPAPO_AVX2_AND(14, 10, 11);
  356. /* Stall */
  357. NFT_PIPAPO_AVX2_AND(1, 12, 13);
  358. NFT_PIPAPO_AVX2_AND(1, 1, 14);
  359. }
  360. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nomatch);
  361. NFT_PIPAPO_AVX2_STORE(map[i_ul], 1);
  362. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  363. if (last)
  364. return b;
  365. if (unlikely(ret == -1))
  366. ret = b / XSAVE_YMM_SIZE;
  367. continue;
  368. nomatch:
  369. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  370. nothing:
  371. ;
  372. }
  373. return ret;
  374. }
  375. /**
  376. * nft_pipapo_avx2_lookup_4b_12() - AVX2-based lookup for 12 four-bit groups
  377. * @map: Previous match result, used as initial bitmap
  378. * @fill: Destination bitmap to be filled with current match result
  379. * @f: Field, containing lookup and mapping tables
  380. * @offset: Ignore buckets before the given index, no bits are filled there
  381. * @pkt: Packet data, pointer to input nftables register
  382. * @first: If this is the first field, don't source previous result
  383. * @last: Last field: stop at the first match and return bit index
  384. *
  385. * See nft_pipapo_avx2_lookup_4b_2().
  386. *
  387. * This is used for 48-bit fields (i.e. MAC addresses/EUI-48).
  388. *
  389. * Return: -1 on no match, rule index of match if @last, otherwise first long
  390. * word index to be checked next (i.e. first filled word).
  391. */
  392. static int nft_pipapo_avx2_lookup_4b_12(unsigned long *map, unsigned long *fill,
  393. struct nft_pipapo_field *f, int offset,
  394. const u8 *pkt, bool first, bool last)
  395. {
  396. u8 pg[12] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf,
  397. pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf,
  398. pkt[4] >> 4, pkt[4] & 0xf, pkt[5] >> 4, pkt[5] & 0xf,
  399. };
  400. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  401. unsigned long *lt = f->lt, bsize = f->bsize;
  402. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  403. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  404. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  405. if (!first)
  406. NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]);
  407. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 0, pg[0], bsize);
  408. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize);
  409. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize);
  410. if (!first) {
  411. NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing);
  412. NFT_PIPAPO_AVX2_AND(1, 1, 0);
  413. }
  414. NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize);
  415. NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 4, pg[4], bsize);
  416. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  417. NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize);
  418. NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 6, pg[6], bsize);
  419. NFT_PIPAPO_AVX2_AND(9, 1, 4);
  420. NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 7, pg[7], bsize);
  421. NFT_PIPAPO_AVX2_AND(11, 5, 6);
  422. NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 8, pg[8], bsize);
  423. NFT_PIPAPO_AVX2_AND(13, 7, 8);
  424. NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 9, pg[9], bsize);
  425. NFT_PIPAPO_AVX2_AND(0, 9, 10);
  426. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 10, pg[10], bsize);
  427. NFT_PIPAPO_AVX2_AND(2, 11, 12);
  428. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 11, pg[11], bsize);
  429. NFT_PIPAPO_AVX2_AND(4, 13, 14);
  430. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  431. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  432. /* Stalls */
  433. NFT_PIPAPO_AVX2_AND(7, 4, 5);
  434. NFT_PIPAPO_AVX2_AND(8, 6, 7);
  435. NFT_PIPAPO_AVX2_NOMATCH_GOTO(8, nomatch);
  436. NFT_PIPAPO_AVX2_STORE(map[i_ul], 8);
  437. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  438. if (last)
  439. return b;
  440. if (unlikely(ret == -1))
  441. ret = b / XSAVE_YMM_SIZE;
  442. continue;
  443. nomatch:
  444. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  445. nothing:
  446. ;
  447. }
  448. return ret;
  449. }
  450. /**
  451. * nft_pipapo_avx2_lookup_4b_32() - AVX2-based lookup for 32 four-bit groups
  452. * @map: Previous match result, used as initial bitmap
  453. * @fill: Destination bitmap to be filled with current match result
  454. * @f: Field, containing lookup and mapping tables
  455. * @offset: Ignore buckets before the given index, no bits are filled there
  456. * @pkt: Packet data, pointer to input nftables register
  457. * @first: If this is the first field, don't source previous result
  458. * @last: Last field: stop at the first match and return bit index
  459. *
  460. * See nft_pipapo_avx2_lookup_4b_2().
  461. *
  462. * This is used for 128-bit fields (i.e. IPv6 addresses).
  463. *
  464. * Return: -1 on no match, rule index of match if @last, otherwise first long
  465. * word index to be checked next (i.e. first filled word).
  466. */
  467. static int nft_pipapo_avx2_lookup_4b_32(unsigned long *map, unsigned long *fill,
  468. struct nft_pipapo_field *f, int offset,
  469. const u8 *pkt, bool first, bool last)
  470. {
  471. u8 pg[32] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf,
  472. pkt[2] >> 4, pkt[2] & 0xf, pkt[3] >> 4, pkt[3] & 0xf,
  473. pkt[4] >> 4, pkt[4] & 0xf, pkt[5] >> 4, pkt[5] & 0xf,
  474. pkt[6] >> 4, pkt[6] & 0xf, pkt[7] >> 4, pkt[7] & 0xf,
  475. pkt[8] >> 4, pkt[8] & 0xf, pkt[9] >> 4, pkt[9] & 0xf,
  476. pkt[10] >> 4, pkt[10] & 0xf, pkt[11] >> 4, pkt[11] & 0xf,
  477. pkt[12] >> 4, pkt[12] & 0xf, pkt[13] >> 4, pkt[13] & 0xf,
  478. pkt[14] >> 4, pkt[14] & 0xf, pkt[15] >> 4, pkt[15] & 0xf,
  479. };
  480. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  481. unsigned long *lt = f->lt, bsize = f->bsize;
  482. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  483. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  484. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  485. if (!first)
  486. NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]);
  487. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 0, pg[0], bsize);
  488. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 1, pg[1], bsize);
  489. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 2, pg[2], bsize);
  490. NFT_PIPAPO_AVX2_BUCKET_LOAD4(4, lt, 3, pg[3], bsize);
  491. if (!first) {
  492. NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing);
  493. NFT_PIPAPO_AVX2_AND(1, 1, 0);
  494. }
  495. NFT_PIPAPO_AVX2_AND(5, 2, 3);
  496. NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 4, pg[4], bsize);
  497. NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 5, pg[5], bsize);
  498. NFT_PIPAPO_AVX2_AND(8, 1, 4);
  499. NFT_PIPAPO_AVX2_BUCKET_LOAD4(9, lt, 6, pg[6], bsize);
  500. NFT_PIPAPO_AVX2_AND(10, 5, 6);
  501. NFT_PIPAPO_AVX2_BUCKET_LOAD4(11, lt, 7, pg[7], bsize);
  502. NFT_PIPAPO_AVX2_AND(12, 7, 8);
  503. NFT_PIPAPO_AVX2_BUCKET_LOAD4(13, lt, 8, pg[8], bsize);
  504. NFT_PIPAPO_AVX2_AND(14, 9, 10);
  505. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 9, pg[9], bsize);
  506. NFT_PIPAPO_AVX2_AND(1, 11, 12);
  507. NFT_PIPAPO_AVX2_BUCKET_LOAD4(2, lt, 10, pg[10], bsize);
  508. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 11, pg[11], bsize);
  509. NFT_PIPAPO_AVX2_AND(4, 13, 14);
  510. NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 12, pg[12], bsize);
  511. NFT_PIPAPO_AVX2_BUCKET_LOAD4(6, lt, 13, pg[13], bsize);
  512. NFT_PIPAPO_AVX2_AND(7, 0, 1);
  513. NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 14, pg[14], bsize);
  514. NFT_PIPAPO_AVX2_AND(9, 2, 3);
  515. NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 15, pg[15], bsize);
  516. NFT_PIPAPO_AVX2_AND(11, 4, 5);
  517. NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 16, pg[16], bsize);
  518. NFT_PIPAPO_AVX2_AND(13, 6, 7);
  519. NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 17, pg[17], bsize);
  520. NFT_PIPAPO_AVX2_AND(0, 8, 9);
  521. NFT_PIPAPO_AVX2_BUCKET_LOAD4(1, lt, 18, pg[18], bsize);
  522. NFT_PIPAPO_AVX2_AND(2, 10, 11);
  523. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 19, pg[19], bsize);
  524. NFT_PIPAPO_AVX2_AND(4, 12, 13);
  525. NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 20, pg[20], bsize);
  526. NFT_PIPAPO_AVX2_AND(6, 14, 0);
  527. NFT_PIPAPO_AVX2_AND(7, 1, 2);
  528. NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 21, pg[21], bsize);
  529. NFT_PIPAPO_AVX2_AND(9, 3, 4);
  530. NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 22, pg[22], bsize);
  531. NFT_PIPAPO_AVX2_AND(11, 5, 6);
  532. NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 23, pg[23], bsize);
  533. NFT_PIPAPO_AVX2_AND(13, 7, 8);
  534. NFT_PIPAPO_AVX2_BUCKET_LOAD4(14, lt, 24, pg[24], bsize);
  535. NFT_PIPAPO_AVX2_BUCKET_LOAD4(0, lt, 25, pg[25], bsize);
  536. NFT_PIPAPO_AVX2_AND(1, 9, 10);
  537. NFT_PIPAPO_AVX2_AND(2, 11, 12);
  538. NFT_PIPAPO_AVX2_BUCKET_LOAD4(3, lt, 26, pg[26], bsize);
  539. NFT_PIPAPO_AVX2_AND(4, 13, 14);
  540. NFT_PIPAPO_AVX2_BUCKET_LOAD4(5, lt, 27, pg[27], bsize);
  541. NFT_PIPAPO_AVX2_AND(6, 0, 1);
  542. NFT_PIPAPO_AVX2_BUCKET_LOAD4(7, lt, 28, pg[28], bsize);
  543. NFT_PIPAPO_AVX2_BUCKET_LOAD4(8, lt, 29, pg[29], bsize);
  544. NFT_PIPAPO_AVX2_AND(9, 2, 3);
  545. NFT_PIPAPO_AVX2_BUCKET_LOAD4(10, lt, 30, pg[30], bsize);
  546. NFT_PIPAPO_AVX2_AND(11, 4, 5);
  547. NFT_PIPAPO_AVX2_BUCKET_LOAD4(12, lt, 31, pg[31], bsize);
  548. NFT_PIPAPO_AVX2_AND(0, 6, 7);
  549. NFT_PIPAPO_AVX2_AND(1, 8, 9);
  550. NFT_PIPAPO_AVX2_AND(2, 10, 11);
  551. NFT_PIPAPO_AVX2_AND(3, 12, 0);
  552. /* Stalls */
  553. NFT_PIPAPO_AVX2_AND(4, 1, 2);
  554. NFT_PIPAPO_AVX2_AND(5, 3, 4);
  555. NFT_PIPAPO_AVX2_NOMATCH_GOTO(5, nomatch);
  556. NFT_PIPAPO_AVX2_STORE(map[i_ul], 5);
  557. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  558. if (last)
  559. return b;
  560. if (unlikely(ret == -1))
  561. ret = b / XSAVE_YMM_SIZE;
  562. continue;
  563. nomatch:
  564. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  565. nothing:
  566. ;
  567. }
  568. return ret;
  569. }
  570. /**
  571. * nft_pipapo_avx2_lookup_8b_1() - AVX2-based lookup for one eight-bit group
  572. * @map: Previous match result, used as initial bitmap
  573. * @fill: Destination bitmap to be filled with current match result
  574. * @f: Field, containing lookup and mapping tables
  575. * @offset: Ignore buckets before the given index, no bits are filled there
  576. * @pkt: Packet data, pointer to input nftables register
  577. * @first: If this is the first field, don't source previous result
  578. * @last: Last field: stop at the first match and return bit index
  579. *
  580. * See nft_pipapo_avx2_lookup_4b_2().
  581. *
  582. * This is used for 8-bit fields (i.e. protocol numbers).
  583. *
  584. * Return: -1 on no match, rule index of match if @last, otherwise first long
  585. * word index to be checked next (i.e. first filled word).
  586. */
  587. static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
  588. struct nft_pipapo_field *f, int offset,
  589. const u8 *pkt, bool first, bool last)
  590. {
  591. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  592. unsigned long *lt = f->lt, bsize = f->bsize;
  593. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  594. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  595. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  596. if (first) {
  597. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 0, pkt[0], bsize);
  598. } else {
  599. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  600. NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
  601. NFT_PIPAPO_AVX2_AND(2, 0, 1);
  602. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing);
  603. }
  604. NFT_PIPAPO_AVX2_NOMATCH_GOTO(2, nomatch);
  605. NFT_PIPAPO_AVX2_STORE(map[i_ul], 2);
  606. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  607. if (last)
  608. return b;
  609. if (unlikely(ret == -1))
  610. ret = b / XSAVE_YMM_SIZE;
  611. continue;
  612. nomatch:
  613. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  614. nothing:
  615. ;
  616. }
  617. return ret;
  618. }
  619. /**
  620. * nft_pipapo_avx2_lookup_8b_2() - AVX2-based lookup for 2 eight-bit groups
  621. * @map: Previous match result, used as initial bitmap
  622. * @fill: Destination bitmap to be filled with current match result
  623. * @f: Field, containing lookup and mapping tables
  624. * @offset: Ignore buckets before the given index, no bits are filled there
  625. * @pkt: Packet data, pointer to input nftables register
  626. * @first: If this is the first field, don't source previous result
  627. * @last: Last field: stop at the first match and return bit index
  628. *
  629. * See nft_pipapo_avx2_lookup_4b_2().
  630. *
  631. * This is used for 16-bit fields (i.e. ports).
  632. *
  633. * Return: -1 on no match, rule index of match if @last, otherwise first long
  634. * word index to be checked next (i.e. first filled word).
  635. */
  636. static int nft_pipapo_avx2_lookup_8b_2(unsigned long *map, unsigned long *fill,
  637. struct nft_pipapo_field *f, int offset,
  638. const u8 *pkt, bool first, bool last)
  639. {
  640. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  641. unsigned long *lt = f->lt, bsize = f->bsize;
  642. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  643. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  644. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  645. if (first) {
  646. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  647. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize);
  648. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  649. } else {
  650. NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]);
  651. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 0, pkt[0], bsize);
  652. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize);
  653. /* Stall */
  654. NFT_PIPAPO_AVX2_AND(3, 0, 1);
  655. NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing);
  656. NFT_PIPAPO_AVX2_AND(4, 3, 2);
  657. }
  658. /* Stall */
  659. NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch);
  660. NFT_PIPAPO_AVX2_STORE(map[i_ul], 4);
  661. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  662. if (last)
  663. return b;
  664. if (unlikely(ret == -1))
  665. ret = b / XSAVE_YMM_SIZE;
  666. continue;
  667. nomatch:
  668. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  669. nothing:
  670. ;
  671. }
  672. return ret;
  673. }
  674. /**
  675. * nft_pipapo_avx2_lookup_8b_4() - AVX2-based lookup for 4 eight-bit groups
  676. * @map: Previous match result, used as initial bitmap
  677. * @fill: Destination bitmap to be filled with current match result
  678. * @f: Field, containing lookup and mapping tables
  679. * @offset: Ignore buckets before the given index, no bits are filled there
  680. * @pkt: Packet data, pointer to input nftables register
  681. * @first: If this is the first field, don't source previous result
  682. * @last: Last field: stop at the first match and return bit index
  683. *
  684. * See nft_pipapo_avx2_lookup_4b_2().
  685. *
  686. * This is used for 32-bit fields (i.e. IPv4 addresses).
  687. *
  688. * Return: -1 on no match, rule index of match if @last, otherwise first long
  689. * word index to be checked next (i.e. first filled word).
  690. */
  691. static int nft_pipapo_avx2_lookup_8b_4(unsigned long *map, unsigned long *fill,
  692. struct nft_pipapo_field *f, int offset,
  693. const u8 *pkt, bool first, bool last)
  694. {
  695. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  696. unsigned long *lt = f->lt, bsize = f->bsize;
  697. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  698. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  699. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  700. if (first) {
  701. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  702. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize);
  703. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 2, pkt[2], bsize);
  704. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 3, pkt[3], bsize);
  705. /* Stall */
  706. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  707. NFT_PIPAPO_AVX2_AND(5, 2, 3);
  708. NFT_PIPAPO_AVX2_AND(0, 4, 5);
  709. } else {
  710. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  711. NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
  712. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize);
  713. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize);
  714. NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize);
  715. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  716. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing);
  717. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  718. /* Stall */
  719. NFT_PIPAPO_AVX2_AND(7, 4, 5);
  720. NFT_PIPAPO_AVX2_AND(0, 6, 7);
  721. }
  722. NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nomatch);
  723. NFT_PIPAPO_AVX2_STORE(map[i_ul], 0);
  724. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  725. if (last)
  726. return b;
  727. if (unlikely(ret == -1))
  728. ret = b / XSAVE_YMM_SIZE;
  729. continue;
  730. nomatch:
  731. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  732. nothing:
  733. ;
  734. }
  735. return ret;
  736. }
  737. /**
  738. * nft_pipapo_avx2_lookup_8b_6() - AVX2-based lookup for 6 eight-bit groups
  739. * @map: Previous match result, used as initial bitmap
  740. * @fill: Destination bitmap to be filled with current match result
  741. * @f: Field, containing lookup and mapping tables
  742. * @offset: Ignore buckets before the given index, no bits are filled there
  743. * @pkt: Packet data, pointer to input nftables register
  744. * @first: If this is the first field, don't source previous result
  745. * @last: Last field: stop at the first match and return bit index
  746. *
  747. * See nft_pipapo_avx2_lookup_4b_2().
  748. *
  749. * This is used for 48-bit fields (i.e. MAC addresses/EUI-48).
  750. *
  751. * Return: -1 on no match, rule index of match if @last, otherwise first long
  752. * word index to be checked next (i.e. first filled word).
  753. */
  754. static int nft_pipapo_avx2_lookup_8b_6(unsigned long *map, unsigned long *fill,
  755. struct nft_pipapo_field *f, int offset,
  756. const u8 *pkt, bool first, bool last)
  757. {
  758. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  759. unsigned long *lt = f->lt, bsize = f->bsize;
  760. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  761. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  762. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  763. if (first) {
  764. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  765. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 1, pkt[1], bsize);
  766. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 2, pkt[2], bsize);
  767. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 3, pkt[3], bsize);
  768. NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 4, pkt[4], bsize);
  769. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  770. NFT_PIPAPO_AVX2_BUCKET_LOAD8(6, lt, 5, pkt[5], bsize);
  771. NFT_PIPAPO_AVX2_AND(7, 2, 3);
  772. /* Stall */
  773. NFT_PIPAPO_AVX2_AND(0, 4, 5);
  774. NFT_PIPAPO_AVX2_AND(1, 6, 7);
  775. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  776. } else {
  777. NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
  778. NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
  779. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize);
  780. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize);
  781. NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize);
  782. NFT_PIPAPO_AVX2_AND(5, 0, 1);
  783. NFT_PIPAPO_AVX2_NOMATCH_GOTO(1, nothing);
  784. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  785. NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 4, pkt[4], bsize);
  786. NFT_PIPAPO_AVX2_AND(0, 4, 5);
  787. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 5, pkt[5], bsize);
  788. NFT_PIPAPO_AVX2_AND(2, 6, 7);
  789. /* Stall */
  790. NFT_PIPAPO_AVX2_AND(3, 0, 1);
  791. NFT_PIPAPO_AVX2_AND(4, 2, 3);
  792. }
  793. NFT_PIPAPO_AVX2_NOMATCH_GOTO(4, nomatch);
  794. NFT_PIPAPO_AVX2_STORE(map[i_ul], 4);
  795. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  796. if (last)
  797. return b;
  798. if (unlikely(ret == -1))
  799. ret = b / XSAVE_YMM_SIZE;
  800. continue;
  801. nomatch:
  802. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  803. nothing:
  804. ;
  805. }
  806. return ret;
  807. }
  808. /**
  809. * nft_pipapo_avx2_lookup_8b_16() - AVX2-based lookup for 16 eight-bit groups
  810. * @map: Previous match result, used as initial bitmap
  811. * @fill: Destination bitmap to be filled with current match result
  812. * @f: Field, containing lookup and mapping tables
  813. * @offset: Ignore buckets before the given index, no bits are filled there
  814. * @pkt: Packet data, pointer to input nftables register
  815. * @first: If this is the first field, don't source previous result
  816. * @last: Last field: stop at the first match and return bit index
  817. *
  818. * See nft_pipapo_avx2_lookup_4b_2().
  819. *
  820. * This is used for 128-bit fields (i.e. IPv6 addresses).
  821. *
  822. * Return: -1 on no match, rule index of match if @last, otherwise first long
  823. * word index to be checked next (i.e. first filled word).
  824. */
  825. static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill,
  826. struct nft_pipapo_field *f, int offset,
  827. const u8 *pkt, bool first, bool last)
  828. {
  829. int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
  830. unsigned long *lt = f->lt, bsize = f->bsize;
  831. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  832. for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
  833. int i_ul = i * NFT_PIPAPO_LONGS_PER_M256;
  834. if (!first)
  835. NFT_PIPAPO_AVX2_LOAD(0, map[i_ul]);
  836. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 0, pkt[0], bsize);
  837. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 1, pkt[1], bsize);
  838. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 2, pkt[2], bsize);
  839. if (!first) {
  840. NFT_PIPAPO_AVX2_NOMATCH_GOTO(0, nothing);
  841. NFT_PIPAPO_AVX2_AND(1, 1, 0);
  842. }
  843. NFT_PIPAPO_AVX2_BUCKET_LOAD8(4, lt, 3, pkt[3], bsize);
  844. NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 4, pkt[4], bsize);
  845. NFT_PIPAPO_AVX2_AND(6, 1, 2);
  846. NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 5, pkt[5], bsize);
  847. NFT_PIPAPO_AVX2_AND(0, 3, 4);
  848. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 6, pkt[6], bsize);
  849. NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 7, pkt[7], bsize);
  850. NFT_PIPAPO_AVX2_AND(3, 5, 6);
  851. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  852. NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 8, pkt[8], bsize);
  853. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  854. NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 9, pkt[9], bsize);
  855. NFT_PIPAPO_AVX2_AND(0, 4, 5);
  856. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 10, pkt[10], bsize);
  857. NFT_PIPAPO_AVX2_AND(2, 6, 7);
  858. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 11, pkt[11], bsize);
  859. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  860. NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt, 12, pkt[12], bsize);
  861. NFT_PIPAPO_AVX2_AND(6, 2, 3);
  862. NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt, 13, pkt[13], bsize);
  863. NFT_PIPAPO_AVX2_AND(0, 4, 5);
  864. NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 14, pkt[14], bsize);
  865. NFT_PIPAPO_AVX2_AND(2, 6, 7);
  866. NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 15, pkt[15], bsize);
  867. NFT_PIPAPO_AVX2_AND(4, 0, 1);
  868. /* Stall */
  869. NFT_PIPAPO_AVX2_AND(5, 2, 3);
  870. NFT_PIPAPO_AVX2_AND(6, 4, 5);
  871. NFT_PIPAPO_AVX2_NOMATCH_GOTO(6, nomatch);
  872. NFT_PIPAPO_AVX2_STORE(map[i_ul], 6);
  873. b = nft_pipapo_avx2_refill(i_ul, &map[i_ul], fill, f->mt, last);
  874. if (last)
  875. return b;
  876. if (unlikely(ret == -1))
  877. ret = b / XSAVE_YMM_SIZE;
  878. continue;
  879. nomatch:
  880. NFT_PIPAPO_AVX2_STORE(map[i_ul], 15);
  881. nothing:
  882. ;
  883. }
  884. return ret;
  885. }
  886. /**
  887. * nft_pipapo_avx2_lookup_slow() - Fallback function for uncommon field sizes
  888. * @map: Previous match result, used as initial bitmap
  889. * @fill: Destination bitmap to be filled with current match result
  890. * @f: Field, containing lookup and mapping tables
  891. * @offset: Ignore buckets before the given index, no bits are filled there
  892. * @pkt: Packet data, pointer to input nftables register
  893. * @first: If this is the first field, don't source previous result
  894. * @last: Last field: stop at the first match and return bit index
  895. *
  896. * This function should never be called, but is provided for the case the field
  897. * size doesn't match any of the known data types. Matching rate is
  898. * substantially lower than AVX2 routines.
  899. *
  900. * Return: -1 on no match, rule index of match if @last, otherwise first long
  901. * word index to be checked next (i.e. first filled word).
  902. */
  903. static int nft_pipapo_avx2_lookup_slow(unsigned long *map, unsigned long *fill,
  904. struct nft_pipapo_field *f, int offset,
  905. const u8 *pkt, bool first, bool last)
  906. {
  907. unsigned long *lt = f->lt, bsize = f->bsize;
  908. int i, ret = -1, b;
  909. lt += offset * NFT_PIPAPO_LONGS_PER_M256;
  910. if (first)
  911. memset(map, 0xff, bsize * sizeof(*map));
  912. for (i = offset; i < bsize; i++) {
  913. if (f->bb == 8)
  914. pipapo_and_field_buckets_8bit(f, map, pkt);
  915. else
  916. pipapo_and_field_buckets_4bit(f, map, pkt);
  917. NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
  918. b = pipapo_refill(map, bsize, f->rules, fill, f->mt, last);
  919. if (last)
  920. return b;
  921. if (ret == -1)
  922. ret = b / XSAVE_YMM_SIZE;
  923. }
  924. return ret;
  925. }
  926. /**
  927. * nft_pipapo_avx2_estimate() - Set size, space and lookup complexity
  928. * @desc: Set description, element count and field description used
  929. * @features: Flags: NFT_SET_INTERVAL needs to be there
  930. * @est: Storage for estimation data
  931. *
  932. * Return: true if set is compatible and AVX2 available, false otherwise.
  933. */
  934. bool nft_pipapo_avx2_estimate(const struct nft_set_desc *desc, u32 features,
  935. struct nft_set_estimate *est)
  936. {
  937. if (!(features & NFT_SET_INTERVAL) ||
  938. desc->field_count < NFT_PIPAPO_MIN_FIELDS)
  939. return false;
  940. if (!boot_cpu_has(X86_FEATURE_AVX2) || !boot_cpu_has(X86_FEATURE_AVX))
  941. return false;
  942. est->size = pipapo_estimate_size(desc);
  943. if (!est->size)
  944. return false;
  945. est->lookup = NFT_SET_CLASS_O_LOG_N;
  946. est->space = NFT_SET_CLASS_O_N;
  947. return true;
  948. }
  949. /**
  950. * nft_pipapo_avx2_lookup() - Lookup function for AVX2 implementation
  951. * @net: Network namespace
  952. * @set: nftables API set representation
  953. * @elem: nftables API element representation containing key data
  954. * @ext: nftables API extension pointer, filled with matching reference
  955. *
  956. * For more details, see DOC: Theory of Operation in nft_set_pipapo.c.
  957. *
  958. * This implementation exploits the repetitive characteristic of the algorithm
  959. * to provide a fast, vectorised version using the AVX2 SIMD instruction set.
  960. *
  961. * Return: true on match, false otherwise.
  962. */
  963. bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
  964. const u32 *key, const struct nft_set_ext **ext)
  965. {
  966. struct nft_pipapo *priv = nft_set_priv(set);
  967. unsigned long *res, *fill, *scratch;
  968. u8 genmask = nft_genmask_cur(net);
  969. const u8 *rp = (const u8 *)key;
  970. struct nft_pipapo_match *m;
  971. struct nft_pipapo_field *f;
  972. bool map_index;
  973. int i, ret = 0;
  974. if (unlikely(!irq_fpu_usable()))
  975. return nft_pipapo_lookup(net, set, key, ext);
  976. m = rcu_dereference(priv->match);
  977. /* This also protects access to all data related to scratch maps */
  978. kernel_fpu_begin();
  979. scratch = *raw_cpu_ptr(m->scratch_aligned);
  980. if (unlikely(!scratch)) {
  981. kernel_fpu_end();
  982. return false;
  983. }
  984. map_index = raw_cpu_read(nft_pipapo_avx2_scratch_index);
  985. res = scratch + (map_index ? m->bsize_max : 0);
  986. fill = scratch + (map_index ? 0 : m->bsize_max);
  987. /* Starting map doesn't need to be set for this implementation */
  988. nft_pipapo_avx2_prepare();
  989. next_match:
  990. nft_pipapo_for_each_field(f, i, m) {
  991. bool last = i == m->field_count - 1, first = !i;
  992. #define NFT_SET_PIPAPO_AVX2_LOOKUP(b, n) \
  993. (ret = nft_pipapo_avx2_lookup_##b##b_##n(res, fill, f, \
  994. ret, rp, \
  995. first, last))
  996. if (likely(f->bb == 8)) {
  997. if (f->groups == 1) {
  998. NFT_SET_PIPAPO_AVX2_LOOKUP(8, 1);
  999. } else if (f->groups == 2) {
  1000. NFT_SET_PIPAPO_AVX2_LOOKUP(8, 2);
  1001. } else if (f->groups == 4) {
  1002. NFT_SET_PIPAPO_AVX2_LOOKUP(8, 4);
  1003. } else if (f->groups == 6) {
  1004. NFT_SET_PIPAPO_AVX2_LOOKUP(8, 6);
  1005. } else if (f->groups == 16) {
  1006. NFT_SET_PIPAPO_AVX2_LOOKUP(8, 16);
  1007. } else {
  1008. ret = nft_pipapo_avx2_lookup_slow(res, fill, f,
  1009. ret, rp,
  1010. first, last);
  1011. }
  1012. } else {
  1013. if (f->groups == 2) {
  1014. NFT_SET_PIPAPO_AVX2_LOOKUP(4, 2);
  1015. } else if (f->groups == 4) {
  1016. NFT_SET_PIPAPO_AVX2_LOOKUP(4, 4);
  1017. } else if (f->groups == 8) {
  1018. NFT_SET_PIPAPO_AVX2_LOOKUP(4, 8);
  1019. } else if (f->groups == 12) {
  1020. NFT_SET_PIPAPO_AVX2_LOOKUP(4, 12);
  1021. } else if (f->groups == 32) {
  1022. NFT_SET_PIPAPO_AVX2_LOOKUP(4, 32);
  1023. } else {
  1024. ret = nft_pipapo_avx2_lookup_slow(res, fill, f,
  1025. ret, rp,
  1026. first, last);
  1027. }
  1028. }
  1029. NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
  1030. #undef NFT_SET_PIPAPO_AVX2_LOOKUP
  1031. if (ret < 0)
  1032. goto out;
  1033. if (last) {
  1034. *ext = &f->mt[ret].e->ext;
  1035. if (unlikely(nft_set_elem_expired(*ext) ||
  1036. !nft_set_elem_active(*ext, genmask))) {
  1037. ret = 0;
  1038. goto next_match;
  1039. }
  1040. goto out;
  1041. }
  1042. swap(res, fill);
  1043. rp += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
  1044. }
  1045. out:
  1046. if (i % 2)
  1047. raw_cpu_write(nft_pipapo_avx2_scratch_index, !map_index);
  1048. kernel_fpu_end();
  1049. return ret >= 0;
  1050. }