Portal:DeveloperDocs/set internals: Difference between revisions
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 23:36, 3 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
Bitmap implementation
nft_set_bitmap.c - contains good documentation
Red-black tree implementation
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.