Portal:DeveloperDocs/set internals: Difference between revisions
Jump to navigation
Jump to search
(→Available nft_set_types: Add definition of klen.) |
(→Available nft_set_types: Added klen column.) |
||
Line 9: | Line 9: | ||
! colspan="2" | ''nft_set_estimate NFT_SET_CLASS_[order]'' | ! colspan="2" | ''nft_set_estimate NFT_SET_CLASS_[order]'' | ||
! rowspan="2" | # Concatenated fields | ! rowspan="2" | # Concatenated fields | ||
! rowspan="2" | | ! rowspan="2" | # ''klen'' restrictions | ||
! rowspan="2" | Must specify size | |||
! rowspan="2" | ''NFT_SET_INTERVAL'' | ! rowspan="2" | ''NFT_SET_INTERVAL'' | ||
! rowspan="2" | ''NFT_SET_MAP'' | ! rowspan="2" | ''NFT_SET_MAP'' | ||
Line 28: | Line 29: | ||
| ''O_N'' | | ''O_N'' | ||
| | | | ||
| {{no}} | | {{partial|!= 4}} | ||
| {{no|Yes}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | | {{yes}} | ||
Line 35: | Line 37: | ||
| {{no}} | | {{no}} | ||
| | | | ||
| | | | ||
|- | |- | ||
Line 43: | Line 45: | ||
| ''O_N'' | | ''O_N'' | ||
| | | | ||
| {{no}} | | {{partial|!= 4}} | ||
| {{no|Yes}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | | {{yes}} | ||
Line 50: | Line 53: | ||
| {{no}} | | {{no}} | ||
| | | | ||
| | | | ||
|- | |- | ||
Line 58: | Line 61: | ||
| ''O_N'' | | ''O_N'' | ||
| | | | ||
| {{yes}} | | {{yes|<= 255}} | ||
| {{yes|No}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | | {{yes}} | ||
Line 73: | Line 77: | ||
| ''O_1'' | | ''O_1'' | ||
| | | | ||
| {{yes}} | | {{no|<= 2}} | ||
| {{yes|No}} | |||
| {{no}} | | {{no}} | ||
| {{no}} | | {{no}} | ||
Line 80: | Line 85: | ||
| {{no}} | | {{no}} | ||
| {{no}} | | {{no}} | ||
| | | | ||
|- | |- | ||
Line 88: | Line 93: | ||
| ''O_N'' | | ''O_N'' | ||
| <= 1 | | <= 1 | ||
| {{yes}} | | {{yes|<= 255}} | ||
| {{yes|No}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
Line 103: | Line 109: | ||
| ''O_N'' | | ''O_N'' | ||
| >= 2 | | >= 2 | ||
| {{yes}} | | {{yes|<= 255}} | ||
| {{yes}} | | {{yes|No}} | ||
| {{partial|Mandatory}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
Line 118: | Line 125: | ||
| ''O_N'' | | ''O_N'' | ||
| >= 2 | | >= 2 | ||
| {{yes}} | | {{yes|<= 255}} | ||
| {{yes}} | | {{yes|No}} | ||
| {{partial|Mandatory}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} |
Revision as of 23:43, 5 March 2021
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 | |||
nft_set_hash_type | 1 | O_1 | O_N | != 4 | Yes | No | Yes | No | Yes | No | |||
nft_set_rhash_type | 2 | O_1 | O_N | <= 255 | No | No | 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 | ||
nft_set_pipapo_avx2_type | 5 | O_LOG_N | O_N | >= 2 | <= 255 | No | Mandatory | Yes | Yes | Yes | No | ||
nft_set_pipapo_type | 6 | O_LOG_N | O_N | >= 2 | <= 255 | No | Mandatory | Yes | Yes | Yes | No |
- 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
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.