Skip to content

Commit 4d44175

Browse files
Florian Westphalummakynes
Florian Westphal
authored and
ummakynes
committed
netfilter: nf_tables: handle nft_object lookups via rhltable
Instead of linear search, use rhlist interface to look up the objects. This fixes rulesets with thousands of named objects (quota, counters and the like). We only use a single table for this and consider the address of the table we're doing the lookup in as a part of the key. This reduces restore time of a sample ruleset with ~20k named counters from 37 seconds to 0.8 seconds. Signed-off-by: Florian Westphal <fw@strlen.de> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
1 parent d152159 commit 4d44175

File tree

3 files changed

+98
-15
lines changed

3 files changed

+98
-15
lines changed

‎include/net/netfilter/nf_tables.h

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1027,14 +1027,16 @@ struct nft_object_hash_key {
10271027
*
10281028
* @list: table stateful object list node
10291029
* @key: keys that identify this object
1030+
* @rhlhead: nft_objname_ht node
10301031
* @genmask: generation mask
10311032
* @use: number of references to this stateful object
10321033
* @handle: unique object handle
10331034
* @ops: object operations
1034-
* @data: object data, layout depends on type
1035+
* @data: object data, layout depends on type
10351036
*/
10361037
struct nft_object {
10371038
struct list_head list;
1039+
struct rhlist_head rhlhead;
10381040
struct nft_object_hash_key key;
10391041
u32 genmask:2,
10401042
use:30;
@@ -1052,7 +1054,8 @@ static inline void *nft_obj_data(const struct nft_object *obj)
10521054

10531055
#define nft_expr_obj(expr) *((struct nft_object **)nft_expr_priv(expr))
10541056

1055-
struct nft_object *nft_obj_lookup(const struct nft_table *table,
1057+
struct nft_object *nft_obj_lookup(const struct net *net,
1058+
const struct nft_table *table,
10561059
const struct nlattr *nla, u32 objtype,
10571060
u8 genmask);
10581061

‎net/netfilter/nf_tables_api.c

Lines changed: 91 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -37,10 +37,16 @@ enum {
3737
NFT_VALIDATE_DO,
3838
};
3939

40+
static struct rhltable nft_objname_ht;
41+
4042
static u32 nft_chain_hash(const void *data, u32 len, u32 seed);
4143
static u32 nft_chain_hash_obj(const void *data, u32 len, u32 seed);
4244
static int nft_chain_hash_cmp(struct rhashtable_compare_arg *, const void *);
4345

46+
static u32 nft_objname_hash(const void *data, u32 len, u32 seed);
47+
static u32 nft_objname_hash_obj(const void *data, u32 len, u32 seed);
48+
static int nft_objname_hash_cmp(struct rhashtable_compare_arg *, const void *);
49+
4450
static const struct rhashtable_params nft_chain_ht_params = {
4551
.head_offset = offsetof(struct nft_chain, rhlhead),
4652
.key_offset = offsetof(struct nft_chain, name),
@@ -51,6 +57,15 @@ static const struct rhashtable_params nft_chain_ht_params = {
5157
.automatic_shrinking = true,
5258
};
5359

60+
static const struct rhashtable_params nft_objname_ht_params = {
61+
.head_offset = offsetof(struct nft_object, rhlhead),
62+
.key_offset = offsetof(struct nft_object, key),
63+
.hashfn = nft_objname_hash,
64+
.obj_hashfn = nft_objname_hash_obj,
65+
.obj_cmpfn = nft_objname_hash_cmp,
66+
.automatic_shrinking = true,
67+
};
68+
5469
static void nft_validate_state_update(struct net *net, u8 new_validate_state)
5570
{
5671
switch (net->nft.validate_state) {
@@ -814,6 +829,34 @@ static int nft_chain_hash_cmp(struct rhashtable_compare_arg *arg,
814829
return strcmp(chain->name, name);
815830
}
816831

832+
static u32 nft_objname_hash(const void *data, u32 len, u32 seed)
833+
{
834+
const struct nft_object_hash_key *k = data;
835+
836+
seed ^= hash_ptr(k->table, 32);
837+
838+
return jhash(k->name, strlen(k->name), seed);
839+
}
840+
841+
static u32 nft_objname_hash_obj(const void *data, u32 len, u32 seed)
842+
{
843+
const struct nft_object *obj = data;
844+
845+
return nft_objname_hash(&obj->key, 0, seed);
846+
}
847+
848+
static int nft_objname_hash_cmp(struct rhashtable_compare_arg *arg,
849+
const void *ptr)
850+
{
851+
const struct nft_object_hash_key *k = arg->key;
852+
const struct nft_object *obj = ptr;
853+
854+
if (obj->key.table != k->table)
855+
return -1;
856+
857+
return strcmp(obj->key.name, k->name);
858+
}
859+
817860
static int nf_tables_newtable(struct net *net, struct sock *nlsk,
818861
struct sk_buff *skb, const struct nlmsghdr *nlh,
819862
const struct nlattr * const nla[],
@@ -1070,7 +1113,7 @@ nft_chain_lookup_byhandle(const struct nft_table *table, u64 handle, u8 genmask)
10701113
return ERR_PTR(-ENOENT);
10711114
}
10721115

1073-
static bool lockdep_commit_lock_is_held(struct net *net)
1116+
static bool lockdep_commit_lock_is_held(const struct net *net)
10741117
{
10751118
#ifdef CONFIG_PROVE_LOCKING
10761119
return lockdep_is_held(&net->nft.commit_mutex);
@@ -4386,7 +4429,8 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
43864429
err = -EINVAL;
43874430
goto err2;
43884431
}
4389-
obj = nft_obj_lookup(ctx->table, nla[NFTA_SET_ELEM_OBJREF],
4432+
obj = nft_obj_lookup(ctx->net, ctx->table,
4433+
nla[NFTA_SET_ELEM_OBJREF],
43904434
set->objtype, genmask);
43914435
if (IS_ERR(obj)) {
43924436
err = PTR_ERR(obj);
@@ -4819,18 +4863,36 @@ void nft_unregister_obj(struct nft_object_type *obj_type)
48194863
}
48204864
EXPORT_SYMBOL_GPL(nft_unregister_obj);
48214865

4822-
struct nft_object *nft_obj_lookup(const struct nft_table *table,
4866+
struct nft_object *nft_obj_lookup(const struct net *net,
4867+
const struct nft_table *table,
48234868
const struct nlattr *nla, u32 objtype,
48244869
u8 genmask)
48254870
{
4871+
struct nft_object_hash_key k = { .table = table };
4872+
char search[NFT_OBJ_MAXNAMELEN];
4873+
struct rhlist_head *tmp, *list;
48264874
struct nft_object *obj;
48274875

4828-
list_for_each_entry_rcu(obj, &table->objects, list) {
4829-
if (!nla_strcmp(nla, obj->key.name) &&
4830-
objtype == obj->ops->type->type &&
4831-
nft_active_genmask(obj, genmask))
4876+
nla_strlcpy(search, nla, sizeof(search));
4877+
k.name = search;
4878+
4879+
WARN_ON_ONCE(!rcu_read_lock_held() &&
4880+
!lockdep_commit_lock_is_held(net));
4881+
4882+
rcu_read_lock();
4883+
list = rhltable_lookup(&nft_objname_ht, &k, nft_objname_ht_params);
4884+
if (!list)
4885+
goto out;
4886+
4887+
rhl_for_each_entry_rcu(obj, tmp, list, rhlhead) {
4888+
if (objtype == obj->ops->type->type &&
4889+
nft_active_genmask(obj, genmask)) {
4890+
rcu_read_unlock();
48324891
return obj;
4892+
}
48334893
}
4894+
out:
4895+
rcu_read_unlock();
48344896
return ERR_PTR(-ENOENT);
48354897
}
48364898
EXPORT_SYMBOL_GPL(nft_obj_lookup);
@@ -4988,7 +5050,7 @@ static int nf_tables_newobj(struct net *net, struct sock *nlsk,
49885050
}
49895051

49905052
objtype = ntohl(nla_get_be32(nla[NFTA_OBJ_TYPE]));
4991-
obj = nft_obj_lookup(table, nla[NFTA_OBJ_NAME], objtype, genmask);
5053+
obj = nft_obj_lookup(net, table, nla[NFTA_OBJ_NAME], objtype, genmask);
49925054
if (IS_ERR(obj)) {
49935055
err = PTR_ERR(obj);
49945056
if (err != -ENOENT) {
@@ -5027,9 +5089,18 @@ static int nf_tables_newobj(struct net *net, struct sock *nlsk,
50275089
if (err < 0)
50285090
goto err3;
50295091

5092+
err = rhltable_insert(&nft_objname_ht, &obj->rhlhead,
5093+
nft_objname_ht_params);
5094+
if (err < 0)
5095+
goto err4;
5096+
50305097
list_add_tail_rcu(&obj->list, &table->objects);
50315098
table->use++;
50325099
return 0;
5100+
err4:
5101+
/* queued in transaction log */
5102+
INIT_LIST_HEAD(&obj->list);
5103+
return err;
50335104
err3:
50345105
kfree(obj->key.name);
50355106
err2:
@@ -5215,7 +5286,7 @@ static int nf_tables_getobj(struct net *net, struct sock *nlsk,
52155286
}
52165287

52175288
objtype = ntohl(nla_get_be32(nla[NFTA_OBJ_TYPE]));
5218-
obj = nft_obj_lookup(table, nla[NFTA_OBJ_NAME], objtype, genmask);
5289+
obj = nft_obj_lookup(net, table, nla[NFTA_OBJ_NAME], objtype, genmask);
52195290
if (IS_ERR(obj)) {
52205291
NL_SET_BAD_ATTR(extack, nla[NFTA_OBJ_NAME]);
52215292
return PTR_ERR(obj);
@@ -5280,7 +5351,7 @@ static int nf_tables_delobj(struct net *net, struct sock *nlsk,
52805351
obj = nft_obj_lookup_byhandle(table, attr, objtype, genmask);
52815352
} else {
52825353
attr = nla[NFTA_OBJ_NAME];
5283-
obj = nft_obj_lookup(table, attr, objtype, genmask);
5354+
obj = nft_obj_lookup(net, table, attr, objtype, genmask);
52845355
}
52855356

52865357
if (IS_ERR(obj)) {
@@ -6406,6 +6477,7 @@ static void nf_tables_commit_chain(struct net *net, struct nft_chain *chain)
64066477

64076478
static void nft_obj_del(struct nft_object *obj)
64086479
{
6480+
rhltable_remove(&nft_objname_ht, &obj->rhlhead, nft_objname_ht_params);
64096481
list_del_rcu(&obj->list);
64106482
}
64116483

@@ -6721,7 +6793,7 @@ static int __nf_tables_abort(struct net *net)
67216793
break;
67226794
case NFT_MSG_NEWOBJ:
67236795
trans->ctx.table->use--;
6724-
list_del_rcu(&nft_trans_obj(trans)->list);
6796+
nft_obj_del(nft_trans_obj(trans));
67256797
break;
67266798
case NFT_MSG_DELOBJ:
67276799
trans->ctx.table->use++;
@@ -7397,12 +7469,18 @@ static int __init nf_tables_module_init(void)
73977469
if (err < 0)
73987470
goto err3;
73997471

7472+
err = rhltable_init(&nft_objname_ht, &nft_objname_ht_params);
7473+
if (err < 0)
7474+
goto err4;
7475+
74007476
/* must be last */
74017477
err = nfnetlink_subsys_register(&nf_tables_subsys);
74027478
if (err < 0)
7403-
goto err4;
7479+
goto err5;
74047480

74057481
return err;
7482+
err5:
7483+
rhltable_destroy(&nft_objname_ht);
74067484
err4:
74077485
unregister_netdevice_notifier(&nf_tables_flowtable_notifier);
74087486
err3:
@@ -7422,6 +7500,7 @@ static void __exit nf_tables_module_exit(void)
74227500
unregister_pernet_subsys(&nf_tables_net_ops);
74237501
cancel_work_sync(&trans_destroy_work);
74247502
rcu_barrier();
7503+
rhltable_destroy(&nft_objname_ht);
74257504
nf_tables_core_module_exit();
74267505
}
74277506

‎net/netfilter/nft_objref.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,8 @@ static int nft_objref_init(const struct nft_ctx *ctx,
3838
return -EINVAL;
3939

4040
objtype = ntohl(nla_get_be32(tb[NFTA_OBJREF_IMM_TYPE]));
41-
obj = nft_obj_lookup(ctx->table, tb[NFTA_OBJREF_IMM_NAME], objtype,
41+
obj = nft_obj_lookup(ctx->net, ctx->table,
42+
tb[NFTA_OBJREF_IMM_NAME], objtype,
4243
genmask);
4344
if (IS_ERR(obj))
4445
return -ENOENT;

0 commit comments

Comments
 (0)