Skip to contentSkip to conversation

json: echo: Speedup seqnum_to_json()

PATCH In review Phil Sutter 3 participants 5 messages Nov 20, 2020 – Dec 2, 2020 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

PATCH 1/1 json: echo: Speedup seqnum_to_json()

Derek Dai reports:
"If there are a lot of command in JSON node, seqnum_to_json() will slow down application (eg: firewalld) dramatically since it iterate whole command list every time."

He sent a patch implementing a lookup table, but we can do better: Speed this up by introducing a hash table to store the struct json_cmd_assoc objects in, taking their netlink sequence number as key.

Quickly tested restoring a ruleset containing about 19k rules:

| # time ./before/nft -jeaf large_ruleset.json >/dev/null
| 4.85user 0.47system 0:05.48elapsed 97%CPU (0avgtext+0avgdata 69732maxresident)k
| 0inputs+0outputs (15major+16937minor)pagefaults 0swaps
| # time ./after/nft -jeaf large_ruleset.json >/dev/null
| 0.18user 0.44system 0:00.70elapsed 89%CPU (0avgtext+0avgdata 68484maxresident)k
| 0inputs+0outputs (15major+16645minor)pagefaults 0swaps

Bugzilla: https://bugzilla.netfilter.org/show_bug.cgi?id=1479

---
 src/parser_json.c | 28 ++++++++++++++++++----------
 1 file changed, 18 insertions(+), 10 deletions(-)
src/parser_json.c +18 -10
index b1de56a4a0d27..6ebbb408d6839 100644
@@ -3762,42 +3762,50 @@ static int json_verify_metainfo(struct json_ctx *ctx, json_t *root)
 }
 
 struct json_cmd_assoc {
-	struct json_cmd_assoc *next;
+	struct hlist_node hnode;
 	const struct cmd *cmd;
 	json_t *json;
 };
 
-static struct json_cmd_assoc *json_cmd_list = NULL;
+#define CMD_ASSOC_HSIZE		512
+static struct hlist_head json_cmd_assoc_hash[CMD_ASSOC_HSIZE];
 
 static void json_cmd_assoc_free(void)
 {
 	struct json_cmd_assoc *cur;
+	struct hlist_node *pos, *n;
+	int i;
 
-	while (json_cmd_list) {
-		cur = json_cmd_list;
-		json_cmd_list = cur->next;
-		free(cur);
+	for (i = 0; i < CMD_ASSOC_HSIZE; i++) {
+		hlist_for_each_entry_safe(cur, pos, n,
+					  &json_cmd_assoc_hash[i], hnode)
+			free(cur);
 	}
 }
 
 static void json_cmd_assoc_add(json_t *json, const struct cmd *cmd)
 {
 	struct json_cmd_assoc *new = xzalloc(sizeof *new);
+	int key = cmd->seqnum % CMD_ASSOC_HSIZE;
 
-	new->next	= json_cmd_list;
 	new->json	= json;
 	new->cmd	= cmd;
-	json_cmd_list	= new;
+
+	hlist_add_head(&new->hnode, &json_cmd_assoc_hash[key]);
 }
 
 static json_t *seqnum_to_json(const uint32_t seqnum)
 {
-	const struct json_cmd_assoc *cur;
+	int key = seqnum % CMD_ASSOC_HSIZE;
+	struct json_cmd_assoc *cur;
+	struct hlist_node *n;
 
-	for (cur = json_cmd_list; cur; cur = cur->next) {
+
+	hlist_for_each_entry(cur, n, &json_cmd_assoc_hash[key], hnode) {
 		if (cur->cmd->seqnum == seqnum)
 			return cur->json;
 	}
+
 	return NULL;
 }
 
Signature · 1 line
2.28.0
#1 lore raw
Quoted 11 lines · Phil Sutter

Derek Dai reports:
"If there are a lot of command in JSON node, seqnum_to_json() will slow down application (eg: firewalld) dramatically since it iterate whole command list every time."

He sent a patch implementing a lookup table, but we can do better: Speed this up by introducing a hash table to store the struct json_cmd_assoc objects in, taking their netlink sequence number as key.

Quickly tested restoring a ruleset containing about 19k rules:

Quoted 7 lines
| # time ./before/nft -jeaf large_ruleset.json >/dev/null
| 4.85user 0.47system 0:05.48elapsed 97%CPU (0avgtext+0avgdata 69732maxresident)k
| 0inputs+0outputs (15major+16937minor)pagefaults 0swaps
| # time ./after/nft -jeaf large_ruleset.json >/dev/null
| 0.18user 0.44system 0:00.70elapsed 89%CPU (0avgtext+0avgdata 68484maxresident)k
| 0inputs+0outputs (15major+16645minor)pagefaults 0swaps

LGTM.

BTW, Jose (he's on Cc) should rewrite his patch to exercise the monitor path when --echo and --json are combined _and_ input is _not_ json.

Hence, leaving --echo and --json where input is json in the way you need (using the sequence number to reuse the json input representation).

OK?

author reviewer
#2 lore raw

Hi,

Quoted 26 lines · Pablo Neira Ayuso
Quoted 11 lines · Phil Sutter

Derek Dai reports:
"If there are a lot of command in JSON node, seqnum_to_json() will slow down application (eg: firewalld) dramatically since it iterate whole command list every time."

He sent a patch implementing a lookup table, but we can do better: Speed this up by introducing a hash table to store the struct json_cmd_assoc objects in, taking their netlink sequence number as key.

Quickly tested restoring a ruleset containing about 19k rules:

Quoted 7 lines
| # time ./before/nft -jeaf large_ruleset.json >/dev/null
| 4.85user 0.47system 0:05.48elapsed 97%CPU (0avgtext+0avgdata 69732maxresident)k
| 0inputs+0outputs (15major+16937minor)pagefaults 0swaps
| # time ./after/nft -jeaf large_ruleset.json >/dev/null
| 0.18user 0.44system 0:00.70elapsed 89%CPU (0avgtext+0avgdata 68484maxresident)k
| 0inputs+0outputs (15major+16645minor)pagefaults 0swaps

LGTM.

BTW, Jose (he's on Cc) should rewrite his patch to exercise the monitor path when --echo and --json are combined _and_ input is _not_ json.

Quoted 5 lines

Hence, leaving --echo and --json where input is json in the way you need (using the sequence number to reuse the json input representation).

OK?

Yes, that's fine with me!

Thanks, Phil

#3 lore raw
Quoted 28 lines · Phil Sutter

Hi,

Quoted 25 lines · Pablo Neira Ayuso
Quoted 11 lines · Phil Sutter

Derek Dai reports:
"If there are a lot of command in JSON node, seqnum_to_json() will slow down application (eg: firewalld) dramatically since it iterate whole command list every time."

He sent a patch implementing a lookup table, but we can do better: Speed this up by introducing a hash table to store the struct json_cmd_assoc objects in, taking their netlink sequence number as key.

Quickly tested restoring a ruleset containing about 19k rules:

Quoted 7 lines
| # time ./before/nft -jeaf large_ruleset.json >/dev/null
| 4.85user 0.47system 0:05.48elapsed 97%CPU (0avgtext+0avgdata 69732maxresident)k
| 0inputs+0outputs (15major+16937minor)pagefaults 0swaps
| # time ./after/nft -jeaf large_ruleset.json >/dev/null
| 0.18user 0.44system 0:00.70elapsed 89%CPU (0avgtext+0avgdata 68484maxresident)k
| 0inputs+0outputs (15major+16645minor)pagefaults 0swaps

LGTM.

BTW, Jose (he's on Cc) should rewrite his patch to exercise the monitor path when --echo and --json are combined _and_ input is _not_ json.

IIRC v4 of the patch already takes into account this situation. Specifically this piece of code inside netlink_echo_callback. Returning the json_events_cb (the path leading to the seqnum_to_json call) when input is json.

- if (nft_output_json(&ctx->nft->output))
- return json_events_cb(nlh, &echo_monh);
+ if (nft_output_json(&nft->output)) {
+ if (!nft->json_root) {
+ nft->json_echo = json_array();
+ if (!nft->json_echo)
+ memory_allocation_error();
+ echo_monh.format = NFTNL_OUTPUT_JSON;
+ } else
+ return json_events_cb(nlh, &echo_monh);
+ }

return netlink_events_cb(nlh, &echo_monh);
}

I also remember Eric Garver ran firewalld tests with this patch.

https://patchwork.ozlabs.org/project/netfilter-devel/patch/[email protected]/#2499299

Quoted 7 lines
Quoted 5 lines

Hence, leaving --echo and --json where input is json in the way you need (using the sequence number to reuse the json input representation).

OK?

Yes, that's fine with me!

It's been some time, but I think this patch was ready to be merged back then and that does not interfere with the json_events_cb path. Just adding echo+json capability when reading native syntax.

Regards!

#4 lore raw
Quoted 26 lines · Jose M. Guisado
Quoted 25 lines · Phil Sutter

Hi,

Quoted 22 lines · Pablo Neira Ayuso
Quoted 11 lines · Phil Sutter

Derek Dai reports:
"If there are a lot of command in JSON node, seqnum_to_json() will slow down application (eg: firewalld) dramatically since it iterate whole command list every time."

He sent a patch implementing a lookup table, but we can do better: Speed this up by introducing a hash table to store the struct json_cmd_assoc objects in, taking their netlink sequence number as key.

Quickly tested restoring a ruleset containing about 19k rules:

Quoted 7 lines
| # time ./before/nft -jeaf large_ruleset.json >/dev/null
| 4.85user 0.47system 0:05.48elapsed 97%CPU (0avgtext+0avgdata 69732maxresident)k
| 0inputs+0outputs (15major+16937minor)pagefaults 0swaps
| # time ./after/nft -jeaf large_ruleset.json >/dev/null
| 0.18user 0.44system 0:00.70elapsed 89%CPU (0avgtext+0avgdata 68484maxresident)k
| 0inputs+0outputs (15major+16645minor)pagefaults 0swaps

LGTM.

Quoted 8 lines
Quoted 3 lines
Quoted 3 lines

BTW, Jose (he's on Cc) should rewrite his patch to exercise the monitor path when --echo and --json are combined _and_ input is _not_ json.

IIRC v4 of the patch already takes into account this situation. Specifically this piece of code inside netlink_echo_callback. Returning the json_events_cb (the path leading to the seqnum_to_json call) when input is json.

OK, I have pushed out this patch. Thanks for clarifying.