From c50b960ccc5981627628302701e93e6aceccdb1c Mon Sep 17 00:00:00 2001 From: Patrick McHardy Date: Fri, 28 Mar 2014 10:19:47 +0000 Subject: netfilter: nf_tables: implement proper set selection The current set selection simply choses the first set type that provides the requested features, which always results in the rbtree being chosen by virtue of being the first set in the list. What we actually want to do is choose the implementation that can provide the requested features and is optimal from either a performance or memory perspective depending on the characteristics of the elements and the preferences specified by the user. The elements are not known when creating a set. Even if we would provide them for anonymous (literal) sets, we'd still have standalone sets where the elements are not known in advance. We therefore need an abstract description of the data charcteristics. The kernel already knows the size of the key, this patch starts by introducing a nested set description which so far contains only the maximum amount of elements. Based on this the set implementations are changed to provide an estimate of the required amount of memory and the lookup complexity class. The set ops have a new callback ->estimate() that is invoked during set selection. It receives a structure containing the attributes known to the kernel and is supposed to populate a struct nft_set_estimate with the complexity class and, in case the size is known, the complete amount of memory required, or the amount of memory required per element otherwise. Based on the policy specified by the user (performance/memory, defaulting to performance) the kernel will then select the best suited implementation. Even if the set implementation would allow to add more than the specified maximum amount of elements, they are enforced since new implementations might not be able to add more than maximum based on which they were selected. Signed-off-by: Patrick McHardy Signed-off-by: Pablo Neira Ayuso --- include/net/netfilter/nf_tables.h | 46 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) (limited to 'include/net/netfilter') diff --git a/include/net/netfilter/nf_tables.h b/include/net/netfilter/nf_tables.h index e6bc14d8fa9a..29ff1dc41ef3 100644 --- a/include/net/netfilter/nf_tables.h +++ b/include/net/netfilter/nf_tables.h @@ -145,6 +145,44 @@ struct nft_set_iter { const struct nft_set_elem *elem); }; +/** + * struct nft_set_desc - description of set elements + * + * @klen: key length + * @dlen: data length + * @size: number of set elements + */ +struct nft_set_desc { + unsigned int klen; + unsigned int dlen; + unsigned int size; +}; + +/** + * enum nft_set_class - performance class + * + * @NFT_LOOKUP_O_1: constant, O(1) + * @NFT_LOOKUP_O_LOG_N: logarithmic, O(log N) + * @NFT_LOOKUP_O_N: linear, O(N) + */ +enum nft_set_class { + NFT_SET_CLASS_O_1, + NFT_SET_CLASS_O_LOG_N, + NFT_SET_CLASS_O_N, +}; + +/** + * struct nft_set_estimate - estimation of memory and performance + * characteristics + * + * @size: required memory + * @class: lookup performance class + */ +struct nft_set_estimate { + unsigned int size; + enum nft_set_class class; +}; + /** * struct nft_set_ops - nf_tables set operations * @@ -174,7 +212,11 @@ struct nft_set_ops { struct nft_set_iter *iter); unsigned int (*privsize)(const struct nlattr * const nla[]); + bool (*estimate)(const struct nft_set_desc *desc, + u32 features, + struct nft_set_estimate *est); int (*init)(const struct nft_set *set, + const struct nft_set_desc *desc, const struct nlattr * const nla[]); void (*destroy)(const struct nft_set *set); @@ -194,6 +236,8 @@ void nft_unregister_set(struct nft_set_ops *ops); * @name: name of the set * @ktype: key type (numeric type defined by userspace, not used in the kernel) * @dtype: data type (verdict or numeric type defined by userspace) + * @size: maximum set size + * @nelems: number of elements * @ops: set ops * @flags: set flags * @klen: key length @@ -206,6 +250,8 @@ struct nft_set { char name[IFNAMSIZ]; u32 ktype; u32 dtype; + u32 size; + u32 nelems; /* runtime data below here */ const struct nft_set_ops *ops ____cacheline_aligned; u16 flags; -- cgit v1.2.3-58-ga151