net/netfilter/nft_set_pipapo_avx2.c

Source file repositories/reference/linux-study-clean/net/netfilter/nft_set_pipapo_avx2.c

File Facts

System
Linux kernel
Corpus path
net/netfilter/nft_set_pipapo_avx2.c
Extension
.c
Size
42269 bytes
Lines
1282
Domain
Networking Core
Bucket
Sockets, Protocols, Packet Path, And Network Policy
Inferred role
Networking Core: implementation source
Status
source implementation candidate

Why This File Exists

Networking stack implementation surface: socket APIs, protocol dispatch, packet flow, routing, filtering, and network namespaces.

Dependency Surface

Detected Declarations

Annotated Snippet

if (likely(len + offset <= BITS_PER_LONG)) {
			*data |= GENMASK(len - 1 + offset, offset);
			return;
		}

		*data |= ~0UL << offset;
		len -= BITS_PER_LONG - offset;
		data++;

		if (len <= BITS_PER_LONG) {
			mask = ~0UL >> (BITS_PER_LONG - len);
			*data |= mask;
			return;
		}
	}

	memset(data, 0xff, len / BITS_PER_BYTE);
	data += len / BITS_PER_LONG;

	len %= BITS_PER_LONG;
	if (len)
		*data |= ~0UL >> (BITS_PER_LONG - len);
}

/**
 * nft_pipapo_avx2_refill() - Scan bitmap, select mapping table item, set bits
 * @offset:	Start from given bitmap (equivalent to bucket) offset, in longs
 * @map:	Bitmap to be scanned for set bits
 * @dst:	Destination bitmap
 * @mt:		Mapping table containing bit set specifiers
 * @last:	Return index of first set bit, if this is the last field
 *
 * This is an alternative implementation of pipapo_refill() suitable for usage
 * with AVX2 lookup routines: we know there are four words to be scanned, at
 * a given offset inside the map, for each matching iteration.
 * The caller must ensure at least one bit in the four words is set.
 *
 * This function doesn't actually use any AVX2 instruction.
 *
 * Return: first set bit index if @last, index of first filled word otherwise.
 */
static int nft_pipapo_avx2_refill(int offset, unsigned long *map,
				  unsigned long *dst,
				  union nft_pipapo_map_bucket *mt, bool last)
{
	int ret = -1;

#define NFT_PIPAPO_AVX2_REFILL_ONE_WORD(x)				\
	do {								\
		while (map[(x)]) {					\
			int r = __builtin_ctzl(map[(x)]);		\
			int i = (offset + (x)) * BITS_PER_LONG + r;	\
									\
			if (last)					\
				return i;				\
									\
			nft_pipapo_avx2_fill(dst, mt[i].to, mt[i].n);	\
									\
			if (ret == -1)					\
				ret = mt[i].to;				\
									\
			map[(x)] &= ~(1UL << r);			\
		}							\
	} while (0)

	NFT_PIPAPO_AVX2_REFILL_ONE_WORD(0);
	NFT_PIPAPO_AVX2_REFILL_ONE_WORD(1);
	NFT_PIPAPO_AVX2_REFILL_ONE_WORD(2);
	NFT_PIPAPO_AVX2_REFILL_ONE_WORD(3);
#undef NFT_PIPAPO_AVX2_REFILL_ONE_WORD

	DEBUG_NET_WARN_ON_ONCE(ret < 0);
	return ret;
}

/**
 * nft_pipapo_avx2_lookup_4b_2() - AVX2-based lookup for 2 four-bit groups
 * @map:	Previous match result, used as initial bitmap
 * @fill:	Destination bitmap to be filled with current match result
 * @f:		Field, containing lookup and mapping tables
 * @offset:	Ignore buckets before the given index, no bits are filled there
 * @pkt:	Packet data, pointer to input nftables register
 * @first:	If this is the first field, don't source previous result
 * @last:	Last field: stop at the first match and return bit index
 *
 * Load buckets from lookup table corresponding to the values of each 4-bit
 * group of packet bytes, and perform a bitwise intersection between them. If
 * this is the first field in the set, simply AND the buckets together
 * (equivalent to using an all-ones starting bitmap), use the provided starting
 * bitmap otherwise. Then call nft_pipapo_avx2_refill() to generate the next

Annotation

Implementation Notes