From patchwork Fri Nov 20 19:16:40 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Phil Sutter X-Patchwork-Id: 1404076 X-Patchwork-Delegate: pablo@netfilter.org Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=vger.kernel.org (client-ip=23.128.96.18; helo=vger.kernel.org; envelope-from=netfilter-devel-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=nwl.cc Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by ozlabs.org (Postfix) with ESMTP id 4Cd5sM11zXz9sVK for ; Sat, 21 Nov 2020 06:17:27 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732296AbgKTTQv (ORCPT ); Fri, 20 Nov 2020 14:16:51 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:48586 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732258AbgKTTQv (ORCPT ); Fri, 20 Nov 2020 14:16:51 -0500 Received: from orbyte.nwl.cc (orbyte.nwl.cc [IPv6:2001:41d0:e:133a::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0144AC0613CF for ; Fri, 20 Nov 2020 11:16:50 -0800 (PST) Received: from localhost ([::1]:50718 helo=tatos) by orbyte.nwl.cc with esmtp (Exim 4.94) (envelope-from ) id 1kgBto-0008ED-Sh; Fri, 20 Nov 2020 20:16:48 +0100 From: Phil Sutter To: Pablo Neira Ayuso Cc: netfilter-devel@vger.kernel.org, Derek Dai Subject: [nft PATCH] json: echo: Speedup seqnum_to_json() Date: Fri, 20 Nov 2020 20:16:40 +0100 Message-Id: <20201120191640.21243-1-phil@nwl.cc> X-Mailer: git-send-email 2.28.0 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netfilter-devel@vger.kernel.org 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 Reported-by: Derek Dai Signed-off-by: Phil Sutter --- src/parser_json.c | 28 ++++++++++++++++++---------- 1 file changed, 18 insertions(+), 10 deletions(-) diff --git a/src/parser_json.c b/src/parser_json.c index b1de56a4a0d27..6ebbb408d6839 100644 --- a/src/parser_json.c +++ b/src/parser_json.c @@ -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; }