From: Phil Sutter <phil@nwl.cc>
To: Pablo Neira Ayuso <pablo@netfilter.org>
Cc: netfilter-devel@vger.kernel.org
Subject: [nft PATCH v2 2/5] mergesort: Avoid accidental set element reordering
Date: Fri, 22 Mar 2024 17:06:42 +0100 [thread overview]
Message-ID: <20240322160645.18331-3-phil@nwl.cc> (raw)
In-Reply-To: <20240322160645.18331-1-phil@nwl.cc>
In corner cases, expr_msort_cmp() may return 0 for two non-identical
elements. An example are ORed tcp flags: 'syn' and 'syn | ack' are
considered the same value since expr_msort_value() reduces the latter to
its LHS.
Keeping the above in mind and looking at how list_expr_sort() works: The
list in 'head' is cut in half, the first half put into the temporary
list 'list' and finally 'list' is merged back into 'head' considering
each element's position. Shall expr_msort_cmp() return 0 for two
elements, the one from 'list' ends up after the one in 'head', thus
reverting their previous ordering.
The practical implication is that output never matches input for the
sample set '{ syn, syn | ack }' as the sorting after delinearization in
netlink_list_setelems() keeps swapping the elements. Out of coincidence,
the commit this fixes itself illustrates the use-case this breaks,
namely tracking a ruleset in git: Each ruleset reload will trigger an
update to the stored dump.
This change breaks interval set element deletion because __set_delete()
implicitly relies upon this reordering of duplicate entries by inserting
a clone of the one to delete into the start (via list_move()) and after
sorting assumes the clone will end up right behind the original. Fix
this by calling list_move_tail() instead.
Fixes: 14ee0a979b622 ("src: sort set elements in netlink_get_setelems()")
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
src/intervals.c | 2 +-
src/mergesort.c | 2 +-
.../sets/dumps/0055tcpflags_0.json-nft | 32 +++++++++----------
.../testcases/sets/dumps/0055tcpflags_0.nft | 8 ++---
4 files changed, 22 insertions(+), 22 deletions(-)
diff --git a/src/intervals.c b/src/intervals.c
index 68728349e999c..6c3f36fec02aa 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -466,7 +466,7 @@ static int __set_delete(struct list_head *msgs, struct expr *i, struct set *set,
unsigned int debug_mask)
{
i->flags |= EXPR_F_REMOVE;
- list_move(&i->list, &existing_set->init->expressions);
+ list_move_tail(&i->list, &existing_set->init->expressions);
list_expr_sort(&existing_set->init->expressions);
return setelem_delete(msgs, set, init, existing_set->init, debug_mask);
diff --git a/src/mergesort.c b/src/mergesort.c
index 4d0e280fdc5e2..5e676be16369b 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -78,7 +78,7 @@ void list_splice_sorted(struct list_head *list, struct list_head *head)
while (l != list) {
if (h == head ||
expr_msort_cmp(list_entry(l, typeof(struct expr), list),
- list_entry(h, typeof(struct expr), list)) < 0) {
+ list_entry(h, typeof(struct expr), list)) <= 0) {
l = l->next;
list_add_tail(l->prev, h);
continue;
diff --git a/tests/shell/testcases/sets/dumps/0055tcpflags_0.json-nft b/tests/shell/testcases/sets/dumps/0055tcpflags_0.json-nft
index 6a3511515f785..e37139f334466 100644
--- a/tests/shell/testcases/sets/dumps/0055tcpflags_0.json-nft
+++ b/tests/shell/testcases/sets/dumps/0055tcpflags_0.json-nft
@@ -28,15 +28,6 @@
{
"|": [
"fin",
- "psh",
- "ack",
- "urg"
- ]
- },
- {
- "|": [
- "fin",
- "psh",
"ack"
]
},
@@ -50,21 +41,22 @@
{
"|": [
"fin",
+ "psh",
"ack"
]
},
{
"|": [
- "syn",
+ "fin",
"psh",
"ack",
"urg"
]
},
+ "syn",
{
"|": [
"syn",
- "psh",
"ack"
]
},
@@ -78,22 +70,22 @@
{
"|": [
"syn",
+ "psh",
"ack"
]
},
- "syn",
{
"|": [
- "rst",
+ "syn",
"psh",
"ack",
"urg"
]
},
+ "rst",
{
"|": [
"rst",
- "psh",
"ack"
]
},
@@ -107,12 +99,13 @@
{
"|": [
"rst",
+ "psh",
"ack"
]
},
- "rst",
{
"|": [
+ "rst",
"psh",
"ack",
"urg"
@@ -126,11 +119,18 @@
},
{
"|": [
+ "psh",
"ack",
"urg"
]
},
- "ack"
+ "ack",
+ {
+ "|": [
+ "ack",
+ "urg"
+ ]
+ }
]
}
}
diff --git a/tests/shell/testcases/sets/dumps/0055tcpflags_0.nft b/tests/shell/testcases/sets/dumps/0055tcpflags_0.nft
index ffed5426577e4..22bf5c461b877 100644
--- a/tests/shell/testcases/sets/dumps/0055tcpflags_0.nft
+++ b/tests/shell/testcases/sets/dumps/0055tcpflags_0.nft
@@ -2,9 +2,9 @@ table ip test {
set tcp_good_flags {
type tcp_flag
flags constant
- elements = { fin | psh | ack | urg, fin | psh | ack, fin | ack | urg, fin | ack, syn | psh | ack | urg,
- syn | psh | ack, syn | ack | urg, syn | ack, syn, rst | psh | ack | urg,
- rst | psh | ack, rst | ack | urg, rst | ack, rst, psh | ack | urg,
- psh | ack, ack | urg, ack }
+ elements = { fin | ack, fin | ack | urg, fin | psh | ack, fin | psh | ack | urg, syn,
+ syn | ack, syn | ack | urg, syn | psh | ack, syn | psh | ack | urg, rst,
+ rst | ack, rst | ack | urg, rst | psh | ack, rst | psh | ack | urg, psh | ack,
+ psh | ack | urg, ack, ack | urg }
}
}
--
2.43.0
next prev parent reply other threads:[~2024-03-22 16:06 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-22 16:06 [nft PATCH v2 0/5] json: Accept more than two operands in binary expressions Phil Sutter
2024-03-22 16:06 ` [nft PATCH v2 1/5] " Phil Sutter
2024-03-22 16:06 ` Phil Sutter [this message]
2024-03-22 16:06 ` [nft PATCH v2 3/5] tests: py: Fix some JSON equivalents Phil Sutter
2024-03-22 16:06 ` [nft PATCH v2 4/5] tests: py: Warn if recorded JSON output matches the input Phil Sutter
2024-03-22 16:06 ` [nft PATCH v2 5/5] tests: py: Drop needless recorded JSON outputs Phil Sutter
2024-04-12 12:35 ` [nft PATCH v2 0/5] json: Accept more than two operands in binary expressions Phil Sutter
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240322160645.18331-3-phil@nwl.cc \
--to=phil@nwl.cc \
--cc=netfilter-devel@vger.kernel.org \
--cc=pablo@netfilter.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).