Portal:DeveloperDocs/set internals

The nftables generalized set infrastructure includes multiple set implementations. nft_select_set_ops() in nf_tables_api.c chooses the implementation depending on required set features and operations, and on estimated lookup time and memory requirements in combination with user-specified set policy (performance or memory).

Available nft_set_types

nft_set_type	nft_set_types[] order	nft_set_estimate NFT_SET_CLASS_[order]		NFT_SET_INTERVAL	NFT_SET_MAP	NFT_SET_TIMEOUT	NFT_SET_OBJECT	NFT_SET_EVAL	Notes
		.lookup	.space
nft_set_hash_fast_type	0	O_1	O_N	No	Yes	No	Yes	No
nft_set_hash_type	1	O_1	O_N	No	Yes	No	Yes	No
nft_set_rhash_type	2	O_1	O_N	No	Yes	Yes	Yes	Yes
nft_set_bitmap_type	3	O_1	O_1	No	No	No	No	No
nft_set_rbtree_type	4	O_LOG_N	O_N	Yes	Yes	Yes	Yes	No
nft_set_pipapo_avx2_type	5	O_LOG_N	O_N	Yes	Yes	Yes	Yes	No
nft_set_pipapo_type	6	O_LOG_N	O_N	Yes	Yes	Yes	Yes	No

If two nft_set_types have the same estimated lookup time and same estimated space requirement, nft_select_set_ops() chooses the type that appears first in nft_set_types[].

Hash implementations

nft_set_hash.c

Bitmap implementation

nft_set_bitmap.c - contains good documentation

Red-black tree implementation

nft_set_rbtree.c

PIPAPO implementations

• nft_set_pipapo.c - contains excellent documentation
• nft_set_pipapo_avx2.c

PIPAPO is loosely inspired by the Grouper network packet classification algorithm.