From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C1AB518B0A; Wed, 25 Feb 2026 01:34:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771983275; cv=none; b=ebfpeN+kWH6DTYDLwL6k5tNi/YfjsqOAaE/Vj8vr28DDekjPUvzZeCgh1scoOlB2KN1wgXZIs282Fo8/K0PyuefMR1tJywfnuvTzulIVk0Gp1RVbhHQ5T694pdVfbCSbFauFMr+Dd5mVPTH/xMB2/xm8g2w3/FK8QAvfeycD3Lc= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771983275; c=relaxed/simple; bh=Q77OxJAjrnqYU/e2aV8iIbiKjIwtKJvjsxNyl8kDhIo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=ufFXZdfU7sUa2rSDFs40z4nu+bnJAPWk/ra1la7oLyJICWOZZUvL0daDsP2ciAI4vUt4vigCKcXmwHt7kow06lisaTGoPo44QZeznHcsROT+JrDs6nOipy0Lvx+vq+WVrCemTc5X905azJYNu1OiFe2PXYPP+BSeC7PcgAcZem8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linuxfoundation.org header.i=@linuxfoundation.org header.b=jesPt021; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linuxfoundation.org header.i=@linuxfoundation.org header.b="jesPt021" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 82D0DC116D0; Wed, 25 Feb 2026 01:34:35 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linuxfoundation.org; s=korg; t=1771983275; bh=Q77OxJAjrnqYU/e2aV8iIbiKjIwtKJvjsxNyl8kDhIo=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=jesPt021vRl18rXdNzj9538lrbcvEMEsP7CR05HilDhbEjW+wzuTxnMMEAImFNH92 2SN9GbwCbwuXqY09yAOt8ldkKLAC57RKu7XpbhwVXUGeKJV4Ky4TJoHalyZQY84MYv 27HdyL+4IXE5QlDro+jxXV+4aCola8lttAdzBscA= From: Greg Kroah-Hartman To: stable@vger.kernel.org Cc: Greg Kroah-Hartman , patches@lists.linux.dev, Pablo Neira Ayuso , Florian Westphal , Sasha Levin Subject: [PATCH 6.19 415/781] netfilter: nft_set_rbtree: use binary search array in get command Date: Tue, 24 Feb 2026 17:18:44 -0800 Message-ID: <20260225012409.877958913@linuxfoundation.org> X-Mailer: git-send-email 2.53.0 In-Reply-To: <20260225012359.695468795@linuxfoundation.org> References: <20260225012359.695468795@linuxfoundation.org> User-Agent: quilt/0.69 X-stable: review X-Patchwork-Hint: ignore Precedence: bulk X-Mailing-List: stable@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 6.19-stable review patch. If anyone has any objections, please let me know. ------------------ From: Pablo Neira Ayuso [ Upstream commit 2aa34191f06fc5af4f70241518a8554370d86054 ] Rework .get interface to use the binary search array, this needs a specific lookup function to match on end intervals (<=). Packet path lookup is slight different because match is on lesser value, not equal (ie. <). After this patch, seqcount can be removed in a follow up patch. Signed-off-by: Pablo Neira Ayuso Signed-off-by: Florian Westphal Stable-dep-of: 782f2688128e ("netfilter: nft_set_rbtree: validate element belonging to interval") Signed-off-by: Sasha Levin --- net/netfilter/nft_set_rbtree.c | 154 ++++++++++++++------------------- 1 file changed, 64 insertions(+), 90 deletions(-) diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c index 04e696c87f4a0..1b0502cc87301 100644 --- a/net/netfilter/nft_set_rbtree.c +++ b/net/netfilter/nft_set_rbtree.c @@ -69,96 +69,6 @@ static int nft_rbtree_cmp(const struct nft_set *set, set->klen); } -static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set, - const u32 *key, struct nft_rbtree_elem **elem, - unsigned int seq, unsigned int flags, u8 genmask) -{ - struct nft_rbtree_elem *rbe, *interval = NULL; - struct nft_rbtree *priv = nft_set_priv(set); - const struct rb_node *parent; - const void *this; - int d; - - parent = rcu_dereference_raw(priv->root.rb_node); - while (parent != NULL) { - if (read_seqcount_retry(&priv->count, seq)) - return false; - - rbe = rb_entry(parent, struct nft_rbtree_elem, node); - - this = nft_set_ext_key(&rbe->ext); - d = memcmp(this, key, set->klen); - if (d < 0) { - parent = rcu_dereference_raw(parent->rb_left); - if (!(flags & NFT_SET_ELEM_INTERVAL_END)) - interval = rbe; - } else if (d > 0) { - parent = rcu_dereference_raw(parent->rb_right); - if (flags & NFT_SET_ELEM_INTERVAL_END) - interval = rbe; - } else { - if (!nft_set_elem_active(&rbe->ext, genmask)) { - parent = rcu_dereference_raw(parent->rb_left); - continue; - } - - if (nft_set_elem_expired(&rbe->ext)) - return false; - - if (!nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) || - (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END) == - (flags & NFT_SET_ELEM_INTERVAL_END)) { - *elem = rbe; - return true; - } - - if (nft_rbtree_interval_end(rbe)) - interval = NULL; - - parent = rcu_dereference_raw(parent->rb_left); - } - } - - if (set->flags & NFT_SET_INTERVAL && interval != NULL && - nft_set_elem_active(&interval->ext, genmask) && - !nft_set_elem_expired(&interval->ext) && - ((!nft_rbtree_interval_end(interval) && - !(flags & NFT_SET_ELEM_INTERVAL_END)) || - (nft_rbtree_interval_end(interval) && - (flags & NFT_SET_ELEM_INTERVAL_END)))) { - *elem = interval; - return true; - } - - return false; -} - -static struct nft_elem_priv * -nft_rbtree_get(const struct net *net, const struct nft_set *set, - const struct nft_set_elem *elem, unsigned int flags) -{ - struct nft_rbtree *priv = nft_set_priv(set); - unsigned int seq = read_seqcount_begin(&priv->count); - struct nft_rbtree_elem *rbe = ERR_PTR(-ENOENT); - const u32 *key = (const u32 *)&elem->key.val; - u8 genmask = nft_genmask_cur(net); - bool ret; - - ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); - if (ret || !read_seqcount_retry(&priv->count, seq)) - return &rbe->priv; - - read_lock_bh(&priv->lock); - seq = read_seqcount_begin(&priv->count); - ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); - read_unlock_bh(&priv->lock); - - if (!ret) - return ERR_PTR(-ENOENT); - - return &rbe->priv; -} - struct nft_array_lookup_ctx { const u32 *key; u32 klen; @@ -213,6 +123,70 @@ nft_rbtree_lookup(const struct net *net, const struct nft_set *set, return interval->from; } +struct nft_array_get_ctx { + const u32 *key; + unsigned int flags; + u32 klen; +}; + +static int nft_array_get_cmp(const void *pkey, const void *entry) +{ + const struct nft_array_interval *interval = entry; + const struct nft_array_get_ctx *ctx = pkey; + int a, b; + + if (!interval->from) + return 1; + + a = memcmp(ctx->key, nft_set_ext_key(interval->from), ctx->klen); + if (!interval->to) + b = -1; + else + b = memcmp(ctx->key, nft_set_ext_key(interval->to), ctx->klen); + + if (a >= 0) { + if (ctx->flags & NFT_SET_ELEM_INTERVAL_END && b <= 0) + return 0; + else if (b < 0) + return 0; + } + + if (a < 0) + return -1; + + return 1; +} + +static struct nft_elem_priv * +nft_rbtree_get(const struct net *net, const struct nft_set *set, + const struct nft_set_elem *elem, unsigned int flags) +{ + struct nft_rbtree *priv = nft_set_priv(set); + struct nft_array *array = rcu_dereference(priv->array); + const struct nft_array_interval *interval; + struct nft_array_get_ctx ctx = { + .key = (const u32 *)&elem->key.val, + .flags = flags, + .klen = set->klen, + }; + struct nft_rbtree_elem *rbe; + + if (!array) + return ERR_PTR(-ENOENT); + + interval = bsearch(&ctx, array->intervals, array->num_intervals, + sizeof(struct nft_array_interval), nft_array_get_cmp); + if (!interval || nft_set_elem_expired(interval->from)) + return ERR_PTR(-ENOENT); + + if (flags & NFT_SET_ELEM_INTERVAL_END) + rbe = container_of(interval->to, struct nft_rbtree_elem, ext); + else + rbe = container_of(interval->from, struct nft_rbtree_elem, ext); + + return &rbe->priv; +} + static void nft_rbtree_gc_elem_remove(struct net *net, struct nft_set *set, struct nft_rbtree *priv, struct nft_rbtree_elem *rbe) -- 2.51.0