Portal:DeveloperDocs/set internals

From nftables wiki
Jump to navigation Jump to search

Disclaimer! This page is incomplete and likely to contain mistakes. Please make corrections directly, and/or send them to netfilter list. Thanks!

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] # Concatenated fields # klen restrictions Must specify size NFT_SET_INTERVAL NFT_SET_MAP NFT_SET_TIMEOUT NFT_SET_OBJECT NFT_SET_EVAL Expression support Notes
.lookup .space
nft_set_hash_fast_type 0 O_1 O_N != 4 Yes No Yes No Yes No Yes
nft_set_hash_type 1 O_1 O_N != 4 Yes No Yes No Yes No Yes
nft_set_rhash_type 2 O_1 O_N <= 255 If eval path updates No Yes Yes Yes Yes Yes
nft_set_bitmap_type 3 O_1 O_1 <= 2 No No No No No No No
nft_set_rbtree_type 4 O_LOG_N O_N <= 1 <= 255 No Yes Yes Yes Yes No Yes
nft_set_pipapo_avx2_type 5 O_LOG_N O_N >= 2 <= 255 No Mandatory Yes Yes Yes No Yes
nft_set_pipapo_type 6 O_LOG_N O_N >= 2 <= 255 No Mandatory Yes Yes Yes No Yes
  • klen is key length in bytes.
  • 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

Bitmap implementation

nft_set_bitmap.c - contains good documentation

Red-black tree implementation

nft_set_rbtree.c

PIPAPO implementations

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