Portal:DeveloperDocs/set internals: Difference between revisions
Jump to navigation
Jump to search
(Added nft_set_types[] order. (Still just a stub.)) |
(→Hash implementations: Added jhash, rhashtable links.) |
||
(15 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
'''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 == | |||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
|- | |- | ||
! nft_set_type | ! rowspan="2" | ''nft_set_type'' | ||
! nft_set_types[] order | ! rowspan="2" | ''nft_set_types[]'' order | ||
! NFT_SET_INTERVAL | ! colspan="2" | ''nft_set_estimate NFT_SET_CLASS_[order]'' | ||
! NFT_SET_MAP | ! rowspan="2" | # Concatenated fields | ||
! NFT_SET_TIMEOUT | ! rowspan="2" | # ''klen'' restrictions | ||
! NFT_SET_OBJECT | ! rowspan="2" | Must specify size | ||
! NFT_SET_EVAL | ! rowspan="2" | ''NFT_SET_INTERVAL'' | ||
! Notes | ! rowspan="2" | ''NFT_SET_MAP'' | ||
! rowspan="2" | ''NFT_SET_TIMEOUT'' | |||
! rowspan="2" | ''NFT_SET_OBJECT'' | |||
! rowspan="2" | ''NFT_SET_EVAL'' | |||
! rowspan="2" | Expression support | |||
! rowspan="2" | Notes | |||
|- | |||
! ''.lookup'' | |||
! ''.space'' | |||
|- | |- | ||
! {{rh}} | nft_set_hash_fast_type | ! {{rh}} | ''nft_set_hash_fast_type'' | ||
| 0 | | 0 | ||
| ''O_1'' | |||
| ''O_N'' | |||
| | |||
| {{partial|!= 4}} | |||
| {{no|Yes}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | | {{yes}} | ||
Line 19: | Line 38: | ||
| {{yes}} | | {{yes}} | ||
| {{no}} | | {{no}} | ||
| {{yes}} | |||
| | | | ||
|- | |- | ||
! {{rh}} | nft_set_hash_type | ! {{rh}} | ''nft_set_hash_type'' | ||
| 1 | | 1 | ||
| ''O_1'' | |||
| ''O_N'' | |||
| | |||
| {{partial|!= 4}} | |||
| {{no|Yes}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | | {{yes}} | ||
Line 29: | Line 54: | ||
| {{yes}} | | {{yes}} | ||
| {{no}} | | {{no}} | ||
| {{yes}} | |||
| | | | ||
|- | |- | ||
! {{rh}} | nft_set_rhash_type | ! {{rh}} | ''nft_set_rhash_type'' | ||
| 2 | | 2 | ||
| ''O_1'' | |||
| ''O_N'' | |||
| | |||
| {{yes|<= 255}} | |||
| {{partial|If eval path updates}} | |||
| {{no}} | | {{no}} | ||
| {{yes}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
Line 42: | Line 74: | ||
|- | |- | ||
! {{rh}} | nft_set_bitmap_type | ! {{rh}} | ''nft_set_bitmap_type'' | ||
| 3 | | 3 | ||
| ''O_1'' | |||
| ''O_1'' | |||
| | |||
| {{no|<= 2}} | |||
| {{yes|No}} | |||
| {{no}} | |||
| {{no}} | | {{no}} | ||
| {{no}} | | {{no}} | ||
Line 52: | Line 90: | ||
|- | |- | ||
! {{rh}} | nft_set_rbtree_type | ! {{rh}} | ''nft_set_rbtree_type'' | ||
| 4 | | 4 | ||
| ''O_LOG_N'' | |||
| ''O_N'' | |||
| {{partial|<= 1}} | |||
| {{yes|<= 255}} | |||
| {{yes|No}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
Line 59: | Line 102: | ||
| {{yes}} | | {{yes}} | ||
| {{no}} | | {{no}} | ||
| | | {{yes}} | ||
| | |||
|- | |- | ||
! {{rh}} | nft_set_pipapo_avx2_type | ! {{rh}} | ''nft_set_pipapo_avx2_type'' | ||
| 5 | | 5 | ||
| ''O_LOG_N'' | |||
| ''O_N'' | |||
| {{yes|>= 2}} | |||
| {{yes|<= 255}} | |||
| {{yes|No}} | |||
| {{partial|Mandatory}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
| {{no}} | |||
| {{yes}} | | {{yes}} | ||
| | | | ||
|- | |- | ||
! {{rh}} | nft_set_pipapo_type | ! {{rh}} | ''nft_set_pipapo_type'' | ||
| 6 | | 6 | ||
| ''O_LOG_N'' | |||
| ''O_N'' | |||
| {{yes|>= 2}} | |||
| {{yes|<= 255}} | |||
| {{yes|No}} | |||
| {{partial|Mandatory}} | |||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
| {{yes}} | | {{yes}} | ||
| {{no}} | |||
| {{yes}} | | {{yes}} | ||
| | | | ||
|} | |} | ||
* ''klen'' is key length in bytes. | |||
* ''nft_set_estimate'' ''.lookup'' and ''.space'' are in terms of enum ''nft_set_class'', defined in [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/include/net/netfilter/nf_tables.h nf_tables.h]: | |||
<source> | |||
enum nft_set_class { | |||
NFT_SET_CLASS_O_1, | |||
NFT_SET_CLASS_O_LOG_N, | |||
NFT_SET_CLASS_O_N, | |||
}; | |||
</source> | |||
* ''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 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 == | |||
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/net/netfilter/nft_set_hash.c nft_set_hash.c] | |||
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/include/linux/jhash.h jhash.h] | |||
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/include/linux/rhashtable-types.h rhashtable-types.h] | |||
* [https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git/tree/include/linux/rhashtable.h rhashtable.h] | |||
== 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. |
Latest revision as of 03:30, 8 March 2021
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
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.