Portal:DeveloperDocs/set internals

The nftables generalized set infrastructure includes multiple set implementations. The implementation chosen for a given set depends on required set features and operations, and on estimated element lookup time and set memory requirements.

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

• nft_set_estimate .lookup and .space are in terms of enum nft_set_class, defined in nf_tables.h:

enum nft_set_class {
	NFT_SET_CLASS_O_1,
	NFT_SET_CLASS_O_LOG_N,
	NFT_SET_CLASS_O_N,
};

• nft_select_set_ops() in nf_tables_api.c: chooses which nft_set_type to use. For sets with default performance policy it chooses lower .lookup; for sets with memory policy it chooses lower .space.
• When choosing between two nft_set_types with the same .lookup and .space, 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.