From patchwork Fri Mar 15 20:34:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bethany Jamison X-Patchwork-Id: 1912700 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=lists.ubuntu.com (client-ip=185.125.189.65; helo=lists.ubuntu.com; envelope-from=kernel-team-bounces@lists.ubuntu.com; receiver=patchwork.ozlabs.org) Received: from lists.ubuntu.com (lists.ubuntu.com [185.125.189.65]) (using TLSv1.2 with cipher ECDHE-ECDSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TxGGQ0Zh9z23s6 for ; Sat, 16 Mar 2024 07:35:25 +1100 (AEDT) Received: from localhost ([127.0.0.1] helo=lists.ubuntu.com) by lists.ubuntu.com with esmtp (Exim 4.86_2) (envelope-from ) id 1rlEGl-0006Y7-DH; Fri, 15 Mar 2024 20:35:11 +0000 Received: from smtp-relay-internal-1.internal ([10.131.114.114] helo=smtp-relay-internal-1.canonical.com) by lists.ubuntu.com with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2) (envelope-from ) id 1rlEGZ-0006WJ-K1 for kernel-team@lists.ubuntu.com; Fri, 15 Mar 2024 20:34:59 +0000 Received: from mail-io1-f69.google.com (mail-io1-f69.google.com [209.85.166.69]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by smtp-relay-internal-1.canonical.com (Postfix) with ESMTPS id 5BC273F630 for ; Fri, 15 Mar 2024 20:34:59 +0000 (UTC) Received: by mail-io1-f69.google.com with SMTP id ca18e2360f4ac-7c8a87a58e5so257858739f.3 for ; Fri, 15 Mar 2024 13:34:59 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710534897; x=1711139697; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=phtQ0PJCdsxoPk+MQsUNTbWQhkNbXKT5siZX3r94E2Q=; b=gcyVYRsxZ69bP0qZTtSgERalmZkb04ZXvBNklB5Mq4ReElmbD3WruNLonG0PLkTJLx J+3Z6KCr5rOTKbKg1li2O26MGLnTVLX6TDoJQJd07L/kTIw/pq2oIxvWMPu+0ZRllM7w OPDL/rh3JCXkPAgn8gyyzg9eUuEBqGcveJwjhx5V99f7ykesHZfs9Dfg0h+Cn57FvmPT VmQnJURi9yV41gaU3FHVAGqDQWM5wcvh+DI7F84yQtmfYcKi8znlPJkVIcBl9H5RCB7L 0kPnDw3xNYTiMwA7oPVwJE4K6xYt/i8+jvaSYXblmTogEry4T8mCCeJsGVqzrVEBpwgK 808w== X-Gm-Message-State: AOJu0YwrMS0TDTfZWc/ItZB/Kczjfk+JMAVqJd1yJYw8dqPtCXWXUa3l ghdNOZVhf8Jgfe+L4Q0eYNQA00X6jY3pwyYUmxBtMr9nZPxqE975Qr/wUFde+xuUWL+mdHoH8Uo oPUOj9TCeitgzXZ1O3XnYkIspUe2OCIwbNgCYv9qsM7Ks+EiY9oWmLbmqF5opFg99hnMiY49L4U Ch/860e/tbCA== X-Received: by 2002:a6b:c844:0:b0:7cc:56a:2157 with SMTP id y65-20020a6bc844000000b007cc056a2157mr163675iof.20.1710534897405; Fri, 15 Mar 2024 13:34:57 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFmEJiRy1uih4RV1cpwYgjvlAvocEcUI1R5oIj5fy3k3fpH5hynFGyciCSGda6JNGOhr/2Xww== X-Received: by 2002:a6b:c844:0:b0:7cc:56a:2157 with SMTP id y65-20020a6bc844000000b007cc056a2157mr163669iof.20.1710534897132; Fri, 15 Mar 2024 13:34:57 -0700 (PDT) Received: from smtp.gmail.com (104-218-69-129.dynamic.lnk.ne.allofiber.net. [104.218.69.129]) by smtp.gmail.com with ESMTPSA id w14-20020a056638138e00b00474d1b1590dsm935801jad.133.2024.03.15.13.34.56 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 15 Mar 2024 13:34:56 -0700 (PDT) From: Bethany Jamison To: kernel-team@lists.ubuntu.com Subject: [SRU][F][PATCH 1/2] netfilter: nf_tables: nft_set_rbtree: fix spurious insertion failure Date: Fri, 15 Mar 2024 15:34:53 -0500 Message-Id: <20240315203454.47348-3-bethany.jamison@canonical.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240315203454.47348-1-bethany.jamison@canonical.com> References: <20240315203454.47348-1-bethany.jamison@canonical.com> MIME-Version: 1.0 X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.20 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: "kernel-team" From: Florian Westphal nft_rbtree_gc_elem() walks back and removes the end interval element that comes before the expired element. There is a small chance that we've cached this element as 'rbe_ge'. If this happens, we hold and test a pointer that has been queued for freeing. It also causes spurious insertion failures: $ cat test-testcases-sets-0044interval_overlap_0.1/testout.log Error: Could not process rule: File exists add element t s { 0 - 2 } ^^^^^^ Failed to insert 0 - 2 given: table ip t { set s { type inet_service flags interval,timeout timeout 2s gc-interval 2s } } The set (rbtree) is empty. The 'failure' doesn't happen on next attempt. Reason is that when we try to insert, the tree may hold an expired element that collides with the range we're adding. While we do evict/erase this element, we can trip over this check: if (rbe_ge && nft_rbtree_interval_end(rbe_ge) && nft_rbtree_interval_end(new)) return -ENOTEMPTY; rbe_ge was erased by the synchronous gc, we should not have done this check. Next attempt won't find it, so retry results in successful insertion. Restart in-kernel to avoid such spurious errors. Such restart are rare, unless userspace intentionally adds very large numbers of elements with very short timeouts while setting a huge gc interval. Even in this case, this cannot loop forever, on each retry an existing element has been removed. As the caller is holding the transaction mutex, its impossible for a second entity to add more expiring elements to the tree. After this it also becomes feasible to remove the async gc worker and perform all garbage collection from the commit path. Fixes: c9e6978e2725 ("netfilter: nft_set_rbtree: Switch to node list walk for overlap detection") Signed-off-by: Florian Westphal (cherry picked from commit 087388278e0f301f4c61ddffb1911d3a180f84b8) CVE-2024-26581 Signed-off-by: Bethany Jamison --- net/netfilter/nft_set_rbtree.c | 46 +++++++++++++++++++++------------- 1 file changed, 29 insertions(+), 17 deletions(-) diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c index d9c436fa91b51..eed0e4cc01ef1 100644 --- a/net/netfilter/nft_set_rbtree.c +++ b/net/netfilter/nft_set_rbtree.c @@ -235,10 +235,9 @@ static void nft_rbtree_gc_remove(struct net *net, struct nft_set *set, rb_erase(&rbe->node, &priv->root); } -static int nft_rbtree_gc_elem(const struct nft_set *__set, - struct nft_rbtree *priv, - struct nft_rbtree_elem *rbe, - u8 genmask) +static const struct nft_rbtree_elem * +nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv, + struct nft_rbtree_elem *rbe, u8 genmask) { struct nft_set *set = (struct nft_set *)__set; struct rb_node *prev = rb_prev(&rbe->node); @@ -248,7 +247,7 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set, gc = nft_trans_gc_alloc(set, 0, GFP_ATOMIC); if (!gc) - return -ENOMEM; + return ERR_PTR(-ENOMEM); /* search for end interval coming before this element. * end intervals don't carry a timeout extension, they @@ -263,6 +262,7 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set, prev = rb_prev(prev); } + rbe_prev = NULL; if (prev) { rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node); nft_rbtree_gc_remove(net, set, priv, rbe_prev); @@ -274,7 +274,7 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set, */ gc = nft_trans_gc_queue_sync(gc, GFP_ATOMIC); if (WARN_ON_ONCE(!gc)) - return -ENOMEM; + return ERR_PTR(-ENOMEM); nft_trans_gc_elem_add(gc, rbe_prev); } @@ -282,13 +282,13 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set, nft_rbtree_gc_remove(net, set, priv, rbe); gc = nft_trans_gc_queue_sync(gc, GFP_ATOMIC); if (WARN_ON_ONCE(!gc)) - return -ENOMEM; + return ERR_PTR(-ENOMEM); nft_trans_gc_elem_add(gc, rbe); nft_trans_gc_queue_sync_done(gc); - return 0; + return rbe_prev; } static bool nft_rbtree_update_first(const struct nft_set *set, @@ -316,7 +316,7 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, struct nft_rbtree *priv = nft_set_priv(set); u8 cur_genmask = nft_genmask_cur(net); u8 genmask = nft_genmask_next(net); - int d, err; + int d; /* Descend the tree to search for an existing element greater than the * key value to insert that is greater than the new element. This is the @@ -365,9 +365,14 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, */ if (nft_set_elem_expired(&rbe->ext) && nft_set_elem_active(&rbe->ext, cur_genmask)) { - err = nft_rbtree_gc_elem(set, priv, rbe, genmask); - if (err < 0) - return err; + const struct nft_rbtree_elem *removed_end; + + removed_end = nft_rbtree_gc_elem(set, priv, rbe, genmask); + if (IS_ERR(removed_end)) + return PTR_ERR(removed_end); + + if (removed_end == rbe_le || removed_end == rbe_ge) + return -EAGAIN; continue; } @@ -488,11 +493,18 @@ static int nft_rbtree_insert(const struct net *net, const struct nft_set *set, struct nft_rbtree_elem *rbe = elem->priv; int err; - write_lock_bh(&priv->lock); - write_seqcount_begin(&priv->count); - err = __nft_rbtree_insert(net, set, rbe, ext); - write_seqcount_end(&priv->count); - write_unlock_bh(&priv->lock); + do { + if (fatal_signal_pending(current)) + return -EINTR; + + cond_resched(); + + write_lock_bh(&priv->lock); + write_seqcount_begin(&priv->count); + err = __nft_rbtree_insert(net, set, rbe, ext); + write_seqcount_end(&priv->count); + write_unlock_bh(&priv->lock); + } while (err == -EAGAIN); return err; } From patchwork Fri Mar 15 20:34:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bethany Jamison X-Patchwork-Id: 1912701 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=lists.ubuntu.com (client-ip=185.125.189.65; helo=lists.ubuntu.com; envelope-from=kernel-team-bounces@lists.ubuntu.com; receiver=patchwork.ozlabs.org) Received: from lists.ubuntu.com (lists.ubuntu.com [185.125.189.65]) (using TLSv1.2 with cipher ECDHE-ECDSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TxGGV0QwWz23qp for ; Sat, 16 Mar 2024 07:35:30 +1100 (AEDT) Received: from localhost ([127.0.0.1] helo=lists.ubuntu.com) by lists.ubuntu.com with esmtp (Exim 4.86_2) (envelope-from ) id 1rlEGs-0006b6-QT; Fri, 15 Mar 2024 20:35:18 +0000 Received: from smtp-relay-internal-1.internal ([10.131.114.114] helo=smtp-relay-internal-1.canonical.com) by lists.ubuntu.com with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2) (envelope-from ) id 1rlEGa-0006WQ-9q for kernel-team@lists.ubuntu.com; Fri, 15 Mar 2024 20:35:00 +0000 Received: from mail-il1-f198.google.com (mail-il1-f198.google.com [209.85.166.198]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by smtp-relay-internal-1.canonical.com (Postfix) with ESMTPS id B037E3F2E2 for ; Fri, 15 Mar 2024 20:34:59 +0000 (UTC) Received: by mail-il1-f198.google.com with SMTP id e9e14a558f8ab-3655fa1722bso25674125ab.1 for ; Fri, 15 Mar 2024 13:34:59 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710534898; x=1711139698; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=t8ax9I0mwvn2t/h8NGdZG8pUhRcviBeYBqgoIOhR9EE=; b=Kt9s02zfJd6ULx6S9ccy+QByl/kgqelWM2jTYzYhSIFsXKGjjpVGlOcs68cBclvhmh kTt9sV3q0U9uPIQiepAzStg0Q5A1bqkpwF+0cpBegCqLNWrMKTZ/IcM8Cw0EEYztgNLo Qhfc+KzP2Zv88oCc6geQ6dF1F/h+NI7aAojsh4Fh+SRSDblT5anyRtxJ3yebTB92iQ8M FfQDX2/l3M1w83Cj/k3hq6Wp1uPWuqRY5pZiVnmicXWRmTSXAlUXH5LN8zHQg6/G4R5Y 3e4/QjE0YE9845HAPx4PK6rwkzpO6tQ7LHhHnvWmepQbgL6VA+WXzFIZa3GfKdu7LrWi jnpw== X-Gm-Message-State: AOJu0Yxohic1mG6HFmepmKf+xDy7NFVLzBFp2oPBx7YKH0A3FEW4HvVU WzLufKe9yd1PDczR7MN15DbXaaBmGofW3+jfeUHvoL/k4SR7JHC+wDl/DS80VddXR2xuIgHgaSX +Q3UYzgDZioR0yEG1/dXSQXgcdIO+tiuR8Ienna/nJJQopcv5rXT8qx3/cngRpl2f/KQBc/LEQa 9ZLQ4hsnXfsQ== X-Received: by 2002:a05:6e02:2166:b0:366:4cc4:29e8 with SMTP id s6-20020a056e02216600b003664cc429e8mr6133409ilv.11.1710534897990; Fri, 15 Mar 2024 13:34:57 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFh6Lda0SnGh8R6oAnj5UT3ED30niVXVXerO13mhA9OFcXrNpo070a1N3AOM+qwGKpqA+l3NQ== X-Received: by 2002:a05:6e02:2166:b0:366:4cc4:29e8 with SMTP id s6-20020a056e02216600b003664cc429e8mr6133401ilv.11.1710534897625; Fri, 15 Mar 2024 13:34:57 -0700 (PDT) Received: from smtp.gmail.com (104-218-69-129.dynamic.lnk.ne.allofiber.net. [104.218.69.129]) by smtp.gmail.com with ESMTPSA id w14-20020a056638138e00b00474d1b1590dsm935801jad.133.2024.03.15.13.34.57 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 15 Mar 2024 13:34:57 -0700 (PDT) From: Bethany Jamison To: kernel-team@lists.ubuntu.com Subject: [SRU][F][PATCH 2/2] netfilter: nft_set_rbtree: skip end interval element from gc Date: Fri, 15 Mar 2024 15:34:54 -0500 Message-Id: <20240315203454.47348-4-bethany.jamison@canonical.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240315203454.47348-1-bethany.jamison@canonical.com> References: <20240315203454.47348-1-bethany.jamison@canonical.com> MIME-Version: 1.0 X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.20 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: "kernel-team" From: Pablo Neira Ayuso rbtree lazy gc on insert might collect an end interval element that has been just added in this transactions, skip end interval elements that are not yet active. Fixes: f718863aca46 ("netfilter: nft_set_rbtree: fix overlap expiration walk") Cc: stable@vger.kernel.org Reported-by: lonial con Signed-off-by: Pablo Neira Ayuso (cherry picked from commit 60c0c230c6f046da536d3df8b39a20b9a9fd6af0) CVE-2024-26581 Signed-off-by: Bethany Jamison --- net/netfilter/nft_set_rbtree.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c index eed0e4cc01ef1..f444732870794 100644 --- a/net/netfilter/nft_set_rbtree.c +++ b/net/netfilter/nft_set_rbtree.c @@ -237,7 +237,7 @@ static void nft_rbtree_gc_remove(struct net *net, struct nft_set *set, static const struct nft_rbtree_elem * nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv, - struct nft_rbtree_elem *rbe, u8 genmask) + struct nft_rbtree_elem *rbe) { struct nft_set *set = (struct nft_set *)__set; struct rb_node *prev = rb_prev(&rbe->node); @@ -256,7 +256,7 @@ nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv, while (prev) { rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node); if (nft_rbtree_interval_end(rbe_prev) && - nft_set_elem_active(&rbe_prev->ext, genmask)) + nft_set_elem_active(&rbe_prev->ext, NFT_GENMASK_ANY)) break; prev = rb_prev(prev); @@ -367,7 +367,7 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, nft_set_elem_active(&rbe->ext, cur_genmask)) { const struct nft_rbtree_elem *removed_end; - removed_end = nft_rbtree_gc_elem(set, priv, rbe, genmask); + removed_end = nft_rbtree_gc_elem(set, priv, rbe); if (IS_ERR(removed_end)) return PTR_ERR(removed_end);