@@ -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);
@@ -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;
@@ -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"
+ ]
+ }
]
}
}
@@ -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 }
}
}
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(-)