Difference between revisions of "Portal:DeveloperDocs/set internals"

From nftables wiki
Jump to navigation Jump to search
(Added intro and (stub) algorithm sections.)
Line 1: Line 1:
The nftables generalized set infrastructure includes multiple set implementations. ''nft_select_set_ops()'' in [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nf_tables_api.c 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''). 


== NFT_SET_FEATURES of available nft_set_types ==
== NFT_SET_FEATURES of available nft_set_types ==
Line 86: Line 87:


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[]''.
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 ==
[https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_hash.c nft_set_hash.c]
== Bitmap implementation ==
[https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_bitmap.c nft_set_bitmap.c] - '''contains good documentation'''
== [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-black tree] implementation ==
[https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_rbtree.c nft_set_rbtree.c]
== PIPAPO implementations ==
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_pipapo.c nft_set_pipapo.c] - '''contains excellent documentation'''
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_pipapo_avx2.c nft_set_pipapo_avx2.c]
PIPAPO is loosely inspired by the [https://www.cse.usf.edu/~ligatti/projects/grouper/ Grouper] network packet classification algorithm.

Revision as of 00:36, 4 March 2021

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).

NFT_SET_FEATURES of available nft_set_types

nft_set_type nft_set_types[] order NFT_SET_INTERVAL NFT_SET_MAP NFT_SET_TIMEOUT NFT_SET_OBJECT NFT_SET_EVAL Notes
nft_set_hash_fast_type 0 No Yes No Yes No
nft_set_hash_type 1 No Yes No Yes No
nft_set_rhash_type 2 No Yes Yes Yes Yes
nft_set_bitmap_type 3 No No No No No
nft_set_rbtree_type 4 Yes Yes Yes Yes No
nft_set_pipapo_avx2_type 5 Yes Yes Yes Yes No
nft_set_pipapo_type 6 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

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