netdev - [PATCH bpf-next] bpf/lpm_trie: inline longest_prefix

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <171025648415.2098287.4441181253947701605.stgit@firesoul>
Date: Tue, 12 Mar 2024 16:17:00 +0100
From: Jesper Dangaard Brouer <hawk@...nel.org>
To: bpf@...r.kernel.org
Cc: Jesper Dangaard Brouer <hawk@...nel.org>,
 Alexei Starovoitov <ast@...nel.org>,
 Daniel Borkmann <borkmann@...earbox.net>, martin.lau@...nel.org,
 netdev@...r.kernel.org, kernel-team@...udflare.com
Subject: [PATCH bpf-next] bpf/lpm_trie: inline longest_prefix_match for
 fastpath

The BPF map type LPM (Longest Prefix Match) is used heavily
in production by multiple products that have BPF components.
Perf data shows trie_lookup_elem() and longest_prefix_match()
being part of kernels perf top.

For every level in the LPM tree trie_lookup_elem() calls out
to longest_prefix_match().  The compiler is free to inline this
call, but chooses not to inline, because other slowpath callers
(that can be invoked via syscall) exists like trie_update_elem(),
trie_delete_elem() or trie_get_next_key().

 bcc/tools/funccount -Ti 1 'trie_lookup_elem|longest_prefix_match.isra.0'
 FUNC                                    COUNT
 trie_lookup_elem                       664945
 longest_prefix_match.isra.0           8101507

Observation on a single random metal shows a factor 12 between
the two functions. Given an average of 12 levels in the trie being
searched.

This patch force inlining longest_prefix_match(), but only for
the lookup fastpath to balance object instruction size.

 $ bloat-o-meter kernel/bpf/lpm_trie.o.orig-noinline kernel/bpf/lpm_trie.o
 add/remove: 1/1 grow/shrink: 1/0 up/down: 335/-4 (331)
 Function                                     old     new   delta
 trie_lookup_elem                             179     510    +331
 __BTF_ID__struct__lpm_trie__706741             -       4      +4
 __BTF_ID__struct__lpm_trie__706733             4       -      -4
 Total: Before=3056, After=3387, chg +10.83%

Details: Due to AMD mitigation for SRSO (Speculative Return Stack Overflow)
these function calls have additional overhead. On newer kernels this shows
up under srso_safe_ret() + srso_return_thunk(), and on older kernels (6.1)
under __x86_return_thunk(). Thus, for production workloads the biggest gain
comes from avoiding this mitigation overhead.

Signed-off-by: Jesper Dangaard Brouer <hawk@...nel.org>
---
I do know net-next is closed
 https://netdev.bots.linux.dev/net-next.html

Hoping BPF maintainers can queue this patch anyhow.
If not feel free to drop and I will try to remember to resubmit.

 kernel/bpf/lpm_trie.c |   16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 050fe1ebf0f7..7a6f39425e14 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -162,9 +162,10 @@ static inline int extract_bit(const u8 *data, size_t index)
  *
  * Determine the longest prefix of @node that matches the bits in @key.
  */
-static size_t longest_prefix_match(const struct lpm_trie *trie,
-				   const struct lpm_trie_node *node,
-				   const struct bpf_lpm_trie_key_u8 *key)
+static __always_inline
+size_t __longest_prefix_match(const struct lpm_trie *trie,
+			      const struct lpm_trie_node *node,
+			      const struct bpf_lpm_trie_key_u8 *key)
 {
 	u32 limit = min(node->prefixlen, key->prefixlen);
 	u32 prefixlen = 0, i = 0;
@@ -224,6 +225,13 @@ static size_t longest_prefix_match(const struct lpm_trie *trie,
 	return prefixlen;
 }
 
+static size_t longest_prefix_match(const struct lpm_trie *trie,
+				   const struct lpm_trie_node *node,
+				   const struct bpf_lpm_trie_key_u8 *key)
+{
+	return __longest_prefix_match(trie, node, key);
+}
+
 /* Called from syscall or from eBPF program */
 static void *trie_lookup_elem(struct bpf_map *map, void *_key)
 {
@@ -245,7 +253,7 @@ static void *trie_lookup_elem(struct bpf_map *map, void *_key)
 		 * If it's the maximum possible prefix for this trie, we have
 		 * an exact match and can return it directly.
 		 */
-		matchlen = longest_prefix_match(trie, node, key);
+		matchlen = __longest_prefix_match(trie, node, key);
 		if (matchlen == trie->max_prefixlen) {
 			found = node;
 			break;