[iptables PATCH 0/3] libxtables: Fix for pointless socket() calls

[iptables PATCH 0/3] libxtables: Fix for pointless socket() calls

[Phil Sutter]

The motivation for this series was a bug report claiming a near 100%
slowdown of iptables-restore when passed a large number of rules
containing conntrack match between two kernel versions. Turns out the
curlprit kernel change was within SELinux and in fact a performance
optimization, namely an introduced hash table mapping from security
context string to SID. This hash table insert, which happened for each
new socket, slowed iptables-restore down considerably.

The actual problem exposed by the above was that iptables-restore opens
a surprisingly large number of sockets when restoring said ruleset. This
stems from bugs in extension compatibility checks done during extension
registration (actually, "full registration").

One of the problems was that incompatible older revsions of an extension
never were never dropped from the pending list, and thus retried for
each rule using the extension. Coincidently, conntrack revision 0
matches this criteria.

Another problem was a (likely) accidental recursion of
xtables_fully_register_pending_*() via xtables_find_*(). In combination
with incompatible match revisions stuck in pending list, this caused
even more extra compatibility checks.

Solve all these problems by making pending extension lists sorted by
(descending) revision number. If at least one revision was compatible
with the kernel, any following incompatible ones may safely be dropped.
This should on one hand get rid of the repeated compatibility checks
while on the other maintain the presumptions stated in commit
3b2530ce7a0d6 ("xtables: Do not register matches/targets with
incompatible revision").

Patch 1 establishes the needed sorting in pending extension lists,
patch 2 then simplifies xtables_fully_register_pending_*() functions.
Patch 3 is strictly speaking not necessary but nice to have as it
streamlines array-based extension registrators with the extension
sorting.

Phil Sutter (3):
  libxtables: Make sure extensions register in revision order
  libxtables: Simplify pending extension registration
  libxtables: Register multiple extensions in ascending order

 libxtables/xtables.c | 206 +++++++++++++++++++++----------------------
 1 file changed, 99 insertions(+), 107 deletions(-)

-- 
2.28.0

[iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Phil Sutter]

Insert extensions into pending lists in ordered fashion: Group by
extension name (and, for matches, family) and order groups by descending
revision number.

This allows to simplify the later full registration considerably. Since
that involves kernel compatibility checks, the extra cycles here pay off
eventually.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 58 insertions(+), 6 deletions(-)

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 8907ba2069be7..63d0ea5def2d5 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
 		}
 }
 
+static int xtables_match_prefer(const struct xtables_match *a,
+				const struct xtables_match *b);
+
 void xtables_register_match(struct xtables_match *me)
 {
+	struct xtables_match **pos;
+	bool seen_myself = false;
+
 	if (me->next) {
 		fprintf(stderr, "%s: match \"%s\" already registered\n",
 			xt_params->program_name, me->name);
@@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
 	if (me->extra_opts != NULL)
 		xtables_check_options(me->name, me->extra_opts);
 
+	/* order into linked list of matches pending full registration */
+	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
+		/* NOTE: No extension_cmp() here as we accept all families */
+		if (strcmp(me->name, (*pos)->name) ||
+		    me->family != (*pos)->family) {
+			if (seen_myself)
+				break;
+			continue;
+		}
+		seen_myself = true;
+		if (xtables_match_prefer(me, *pos) >= 0)
+			break;
+	}
+	if (!*pos)
+		pos = &xtables_pending_matches;
 
-	/* place on linked list of matches pending full registration */
-	me->next = xtables_pending_matches;
-	xtables_pending_matches = me;
+	me->next = *pos;
+	*pos = me;
+#ifdef DEBUG
+	printf("%s: inserted match %s (family %d, revision %d):\n",
+			__func__, me->name, me->family, me->revision);
+	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
+		printf("%s:\tmatch %s (family %d, revision %d)\n", __func__,
+		       (*pos)->name, (*pos)->family, (*pos)->revision);
+	}
+#endif
 }
 
 /**
@@ -1143,6 +1171,9 @@ void xtables_register_matches(struct xtables_match *match, unsigned int n)
 
 void xtables_register_target(struct xtables_target *me)
 {
+	struct xtables_target **pos;
+	bool seen_myself = false;
+
 	if (me->next) {
 		fprintf(stderr, "%s: target \"%s\" already registered\n",
 			xt_params->program_name, me->name);
@@ -1198,9 +1229,30 @@ void xtables_register_target(struct xtables_target *me)
 	if (me->family != afinfo->family && me->family != AF_UNSPEC)
 		return;
 
-	/* place on linked list of targets pending full registration */
-	me->next = xtables_pending_targets;
-	xtables_pending_targets = me;
+	/* order into linked list of targets pending full registration */
+	for (pos = &xtables_pending_targets; *pos; pos = &(*pos)->next) {
+		if (!extension_cmp(me->name, (*pos)->name, (*pos)->family)) {
+			if (seen_myself)
+				break;
+			continue;
+		}
+		seen_myself = true;
+		if (xtables_target_prefer(me, *pos) >= 0)
+			break;
+	}
+	if (!*pos)
+		pos = &xtables_pending_targets;
+
+	me->next = *pos;
+	*pos = me;
+#ifdef DEBUG
+	printf("%s: inserted target %s (family %d, revision %d):\n",
+			__func__, me->name, me->family, me->revision);
+	for (pos = &xtables_pending_targets; *pos; pos = &(*pos)->next) {
+		printf("%s:\ttarget %s (family %d, revision %d)\n", __func__,
+		       (*pos)->name, (*pos)->family, (*pos)->revision);
+	}
+#endif
 }
 
 static bool xtables_fully_register_pending_target(struct xtables_target *me)
-- 
2.28.0

[iptables PATCH 2/3] libxtables: Simplify pending extension registration

[Phil Sutter]

Assuming that pending extensions are sorted by first name and family,
then descending revision, the decision where to insert a newly
registered extension may be simplified by memorizing the previous
registration (which obviously is of same name and family and higher
revision).

As a side-effect, fix for unsupported old extension revisions lingering
in pending extension list forever and being retried with every use of
the given extension. Any revision being rejected by the kernel may
safely be dropped iff a previous (read: higher) revision was accepted
already.

Yet another side-effect of this change is the removal of an unwanted
recursion by xtables_fully_register_pending_*() into itself via
xtables_find_*().

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 libxtables/xtables.c | 128 +++++++++++--------------------------------
 1 file changed, 33 insertions(+), 95 deletions(-)

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 63d0ea5def2d5..de74d361a53af 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -203,8 +203,10 @@ struct xtables_match *xtables_matches;
 struct xtables_target *xtables_targets;
 
 /* Fully register a match/target which was previously partially registered. */
-static bool xtables_fully_register_pending_match(struct xtables_match *me);
-static bool xtables_fully_register_pending_target(struct xtables_target *me);
+static bool xtables_fully_register_pending_match(struct xtables_match *me,
+						 struct xtables_match *prev);
+static bool xtables_fully_register_pending_target(struct xtables_target *me,
+						  struct xtables_target *prev);
 
 #ifndef NO_SHARED_LIBS
 /* registry for loaded shared objects to close later */
@@ -662,6 +664,7 @@ struct xtables_match *
 xtables_find_match(const char *name, enum xtables_tryload tryload,
 		   struct xtables_rule_match **matches)
 {
+	struct xtables_match *prev = NULL;
 	struct xtables_match **dptr;
 	struct xtables_match *ptr;
 	const char *icmp6 = "icmp6";
@@ -683,8 +686,12 @@ xtables_find_match(const char *name, enum xtables_tryload tryload,
 		if (extension_cmp(name, (*dptr)->name, (*dptr)->family)) {
 			ptr = *dptr;
 			*dptr = (*dptr)->next;
-			if (xtables_fully_register_pending_match(ptr))
+			if (xtables_fully_register_pending_match(ptr, prev)) {
+				prev = ptr;
 				continue;
+			} else if (prev) {
+				continue;
+			}
 			*dptr = ptr;
 		}
 		dptr = &((*dptr)->next);
@@ -778,6 +785,7 @@ xtables_find_match_revision(const char *name, enum xtables_tryload tryload,
 struct xtables_target *
 xtables_find_target(const char *name, enum xtables_tryload tryload)
 {
+	struct xtables_target *prev = NULL;
 	struct xtables_target **dptr;
 	struct xtables_target *ptr;
 
@@ -794,8 +802,12 @@ xtables_find_target(const char *name, enum xtables_tryload tryload)
 		if (extension_cmp(name, (*dptr)->name, (*dptr)->family)) {
 			ptr = *dptr;
 			*dptr = (*dptr)->next;
-			if (xtables_fully_register_pending_target(ptr))
+			if (xtables_fully_register_pending_target(ptr, prev)) {
+				prev = ptr;
 				continue;
+			} else if (prev) {
+				continue;
+			}
 			*dptr = ptr;
 		}
 		dptr = &((*dptr)->next);
@@ -1096,64 +1108,27 @@ static int xtables_target_prefer(const struct xtables_target *a,
 				 b->revision, b->family);
 }
 
-static bool xtables_fully_register_pending_match(struct xtables_match *me)
+static bool xtables_fully_register_pending_match(struct xtables_match *me,
+						 struct xtables_match *prev)
 {
-	struct xtables_match **i, *old, *pos = NULL;
+	struct xtables_match **i;
 	const char *rn;
-	int compare;
 
 	/* See if new match can be used. */
 	rn = (me->real_name != NULL) ? me->real_name : me->name;
 	if (!compatible_match_revision(rn, me->revision))
 		return false;
 
-	old = xtables_find_match(me->name, XTF_DURING_LOAD, NULL);
-	while (old) {
-		compare = xtables_match_prefer(old, me);
-		if (compare == 0) {
-			fprintf(stderr,
-				"%s: match `%s' already registered.\n",
-				xt_params->program_name, me->name);
-			exit(1);
-		}
-
-		/* Now we have two (or more) options, check compatibility. */
-		rn = (old->real_name != NULL) ? old->real_name : old->name;
-		if (compare > 0) {
-			/* Kernel tells old isn't compatible anymore??? */
-			if (!compatible_match_revision(rn, old->revision)) {
-				/* Delete old one. */
-				for (i = &xtables_matches; *i != old;)
-				     i = &(*i)->next;
-				*i = old->next;
-			}
-			pos = old;
-			old = old->next;
-			if (!old)
-				break;
-			if (!extension_cmp(me->name, old->name, old->family))
-				break;
-			continue;
-		}
-
-		/* Found right old */
-		pos = old;
-		break;
-	}
-
-	if (!pos) {
+	if (!prev) {
 		/* Append to list. */
 		for (i = &xtables_matches; *i; i = &(*i)->next);
-	} else if (compare < 0) {
-		/* Prepend it */
-		for (i = &xtables_matches; *i != pos; i = &(*i)->next);
-	} else if (compare > 0) {
+	} else {
 		/* Append it */
-		i = &pos->next;
-		pos = pos->next;
+		i = &prev->next;
+		prev = prev->next;
 	}
 
-	me->next = pos;
+	me->next = prev;
 	*i = me;
 
 	me->m = NULL;
@@ -1255,11 +1230,11 @@ void xtables_register_target(struct xtables_target *me)
 #endif
 }
 
-static bool xtables_fully_register_pending_target(struct xtables_target *me)
+static bool xtables_fully_register_pending_target(struct xtables_target *me,
+						  struct xtables_target *prev)
 {
-	struct xtables_target **i, *old, *pos = NULL;
+	struct xtables_target **i;
 	const char *rn;
-	int compare;
 
 	if (strcmp(me->name, "standard") != 0) {
 		/* See if new target can be used. */
@@ -1268,54 +1243,17 @@ static bool xtables_fully_register_pending_target(struct xtables_target *me)
 			return false;
 	}
 
-	old = xtables_find_target(me->name, XTF_DURING_LOAD);
-	while (old) {
-		compare = xtables_target_prefer(old, me);
-		if (compare == 0) {
-			fprintf(stderr,
-				"%s: target `%s' already registered.\n",
-				xt_params->program_name, me->name);
-			exit(1);
-		}
-
-		/* Now we have two (or more) options, check compatibility. */
-		rn = (old->real_name != NULL) ? old->real_name : old->name;
-		if (compare > 0) {
-			/* Kernel tells old isn't compatible anymore??? */
-			if (!compatible_target_revision(rn, old->revision)) {
-				/* Delete old one. */
-				for (i = &xtables_targets; *i != old;)
-				     i = &(*i)->next;
-				*i = old->next;
-			}
-			pos = old;
-			old = old->next;
-			if (!old)
-				break;
-			if (!extension_cmp(me->name, old->name, old->family))
-				break;
-			continue;
-		}
-
-		/* Found right old */
-		pos = old;
-		break;
-	}
-
-	if (!pos) {
+	if (!prev) {
 		/* Prepend to list. */
 		i = &xtables_targets;
-		pos = xtables_targets;
-	} else if (compare < 0) {
-		/* Prepend it */
-		for (i = &xtables_targets; *i != pos; i = &(*i)->next);
-	} else if (compare > 0) {
+		prev = xtables_targets;
+	} else {
 		/* Append it */
-		i = &pos->next;
-		pos = pos->next;
+		i = &prev->next;
+		prev = prev->next;
 	}
 
-	me->next = pos;
+	me->next = prev;
 	*i = me;
 
 	me->t = NULL;
-- 
2.28.0

[iptables PATCH 3/3] libxtables: Register multiple extensions in ascending order

[Phil Sutter]

The newly introduced ordered insert algorithm in
xtables_register_{match,target}() works best if extensions of same name
are passed in ascending revisions. Since this is the case in about all
extensions' arrays, iterate over them from beginning to end.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 libxtables/xtables.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index de74d361a53af..90b1195c45a58 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -1139,9 +1139,10 @@ static bool xtables_fully_register_pending_match(struct xtables_match *me,
 
 void xtables_register_matches(struct xtables_match *match, unsigned int n)
 {
-	do {
-		xtables_register_match(&match[--n]);
-	} while (n > 0);
+	int i;
+
+	for (i = 0; i < n; i++)
+		xtables_register_match(&match[i]);
 }
 
 void xtables_register_target(struct xtables_target *me)
@@ -1264,9 +1265,10 @@ static bool xtables_fully_register_pending_target(struct xtables_target *me,
 
 void xtables_register_targets(struct xtables_target *target, unsigned int n)
 {
-	do {
-		xtables_register_target(&target[--n]);
-	} while (n > 0);
+	int i;
+
+	for (i = 0; i < n; i++)
+		xtables_register_target(&target[i]);
 }
 
 /* receives a list of xtables_rule_match, release them */
-- 
2.28.0

Re: [iptables PATCH 0/3] libxtables: Fix for pointless socket() calls

[Pablo Neira Ayuso]

Hi Phil,

On Wed, Sep 23, 2020 at 12:53:38AM +0200, Phil Sutter wrote:
> The motivation for this series was a bug report claiming a near 100%
> slowdown of iptables-restore when passed a large number of rules
> containing conntrack match between two kernel versions. Turns out the
> curlprit kernel change was within SELinux and in fact a performance
> optimization, namely an introduced hash table mapping from security
> context string to SID. This hash table insert, which happened for each
> new socket, slowed iptables-restore down considerably.
> 
> The actual problem exposed by the above was that iptables-restore opens
> a surprisingly large number of sockets when restoring said ruleset. This
> stems from bugs in extension compatibility checks done during extension
> registration (actually, "full registration").
> 
> One of the problems was that incompatible older revsions of an extension
> never were never dropped from the pending list, and thus retried for
> each rule using the extension. Coincidently, conntrack revision 0
> matches this criteria.
> 
> Another problem was a (likely) accidental recursion of
> xtables_fully_register_pending_*() via xtables_find_*(). In combination
> with incompatible match revisions stuck in pending list, this caused
> even more extra compatibility checks.
> 
> Solve all these problems by making pending extension lists sorted by
> (descending) revision number. If at least one revision was compatible
> with the kernel, any following incompatible ones may safely be dropped.
> This should on one hand get rid of the repeated compatibility checks
> while on the other maintain the presumptions stated in commit
> 3b2530ce7a0d6 ("xtables: Do not register matches/targets with
> incompatible revision").
> 
> Patch 1 establishes the needed sorting in pending extension lists,
> patch 2 then simplifies xtables_fully_register_pending_*() functions.
> Patch 3 is strictly speaking not necessary but nice to have as it
> streamlines array-based extension registrators with the extension
> sorting.

Did you run iptables-tests.py with older kernel?

Thanks.

Re: [iptables PATCH 0/3] libxtables: Fix for pointless socket() calls

[Phil Sutter]

Hi Pablo,

On Wed, Sep 23, 2020 at 01:45:49PM +0200, Pablo Neira Ayuso wrote:
> On Wed, Sep 23, 2020 at 12:53:38AM +0200, Phil Sutter wrote:
> > The motivation for this series was a bug report claiming a near 100%
> > slowdown of iptables-restore when passed a large number of rules
> > containing conntrack match between two kernel versions. Turns out the
> > curlprit kernel change was within SELinux and in fact a performance
> > optimization, namely an introduced hash table mapping from security
> > context string to SID. This hash table insert, which happened for each
> > new socket, slowed iptables-restore down considerably.
> > 
> > The actual problem exposed by the above was that iptables-restore opens
> > a surprisingly large number of sockets when restoring said ruleset. This
> > stems from bugs in extension compatibility checks done during extension
> > registration (actually, "full registration").
> > 
> > One of the problems was that incompatible older revsions of an extension
> > never were never dropped from the pending list, and thus retried for
> > each rule using the extension. Coincidently, conntrack revision 0
> > matches this criteria.
> > 
> > Another problem was a (likely) accidental recursion of
> > xtables_fully_register_pending_*() via xtables_find_*(). In combination
> > with incompatible match revisions stuck in pending list, this caused
> > even more extra compatibility checks.
> > 
> > Solve all these problems by making pending extension lists sorted by
> > (descending) revision number. If at least one revision was compatible
> > with the kernel, any following incompatible ones may safely be dropped.
> > This should on one hand get rid of the repeated compatibility checks
> > while on the other maintain the presumptions stated in commit
> > 3b2530ce7a0d6 ("xtables: Do not register matches/targets with
> > incompatible revision").
> > 
> > Patch 1 establishes the needed sorting in pending extension lists,
> > patch 2 then simplifies xtables_fully_register_pending_*() functions.
> > Patch 3 is strictly speaking not necessary but nice to have as it
> > streamlines array-based extension registrators with the extension
> > sorting.
> 
> Did you run iptables-tests.py with older kernel?

Yes, I did. As expected, some tests fail - e.g. in the old kernel
IDLETIMER rev 1 is not available, so xt_IDLETIMER.t fails partially:

| % sudo ip netns exec test ./iptables-test.py extensions/libxt_IDLETIMER.t
| extensions/libxt_IDLETIMER.t: ERROR: line 5 (cannot load: iptables -A INPUT -j IDLETIMER --timeout 42 --label foo --alarm)
| 1 test files, 4 unit tests, 3 passed
| 
| % sudo ip netns exec test ./iptables-test.py -n extensions/libxt_IDLETIMER.t
| extensions/libxt_IDLETIMER.t: ERROR: line 5 (cannot load: iptables -A
| INPUT -j IDLETIMER --timeout 42 --label foo --alarm)
| 1 test files, 4 unit tests, 3 passed

Obviously, IDLETIMER rev 1 will stay lingering in pending target list
and retried for each parsed rule:

| % sudo ./install/sbin/iptables-nft-save
| # Generated by iptables-nft-save v1.8.5 on Wed Sep 23 16:37:09 2020
| *filter
| :INPUT ACCEPT [0:0]
| :FORWARD ACCEPT [0:0]
| :OUTPUT ACCEPT [0:0]
| xtables_register_target: inserted target IDLETIMER (family 0, revision
| 0):
| xtables_register_target:	target IDLETIMER (family 0, revision 0)
| xtables_register_target: inserted target IDLETIMER (family 0, revision
| 1):
| xtables_register_target:	target IDLETIMER (family 0, revision 1)
| xtables_register_target:	target IDLETIMER (family 0, revision 0)
| requesting `IDLETIMER' rev=1 type=1 via nft_compat
| requesting `IDLETIMER' rev=0 type=1 via nft_compat
| -A FORWARD -j IDLETIMER --timeout 3600 --label foo
| requesting `IDLETIMER' rev=1 type=1 via nft_compat
| -A FORWARD -j IDLETIMER --timeout 3600 --label bar
| COMMIT
| # Completed on Wed Sep 23 16:37:09 2020

But this is per design, assuming that Serhey fixed a real issue in
3b2530ce7a0d6 ("xtables: Do not register matches/targets with
incompatible revision").

Do you have something else in mind I should watch out for?

Thanks, Phil

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Pablo Neira Ayuso]

Hi Phil,

On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> Insert extensions into pending lists in ordered fashion: Group by
> extension name (and, for matches, family) and order groups by descending
> revision number.
>
> This allows to simplify the later full registration considerably. Since
> that involves kernel compatibility checks, the extra cycles here pay off
> eventually.
> 
> Signed-off-by: Phil Sutter <phil@nwl.cc>
> ---
>  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 58 insertions(+), 6 deletions(-)
> 
> diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> index 8907ba2069be7..63d0ea5def2d5 100644
> --- a/libxtables/xtables.c
> +++ b/libxtables/xtables.c
> @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
>  		}
>  }
>  
> +static int xtables_match_prefer(const struct xtables_match *a,
> +				const struct xtables_match *b);
> +
>  void xtables_register_match(struct xtables_match *me)
>  {
> +	struct xtables_match **pos;
> +	bool seen_myself = false;
> +
>  	if (me->next) {
>  		fprintf(stderr, "%s: match \"%s\" already registered\n",
>  			xt_params->program_name, me->name);
> @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
>  	if (me->extra_opts != NULL)
>  		xtables_check_options(me->name, me->extra_opts);
>  
> +	/* order into linked list of matches pending full registration */
> +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> +		/* NOTE: No extension_cmp() here as we accept all families */
> +		if (strcmp(me->name, (*pos)->name) ||
> +		    me->family != (*pos)->family) {
> +			if (seen_myself)
> +				break;
> +			continue;
> +		}
> +		seen_myself = true;
> +		if (xtables_match_prefer(me, *pos) >= 0)

xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
number than *pos. So list order is: higher revision first.

> +			break;
> +	}
> +	if (!*pos)
> +		pos = &xtables_pending_matches;
>  
> -	/* place on linked list of matches pending full registration */
> -	me->next = xtables_pending_matches;
> -	xtables_pending_matches = me;
> +	me->next = *pos;

This line above is placing 'me' right before the existing match in the list.

> +	*pos = me;

This line above only works if *pos is &xtables_pending_matches?

Looking at the in-tree extensions, they are always ordered from lower
to higher (in array definitions).

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Phil Sutter]

Hi Pablo,

On Sat, Oct 03, 2020 at 01:17:41PM +0200, Pablo Neira Ayuso wrote:
> On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> > Insert extensions into pending lists in ordered fashion: Group by
> > extension name (and, for matches, family) and order groups by descending
> > revision number.
> >
> > This allows to simplify the later full registration considerably. Since
> > that involves kernel compatibility checks, the extra cycles here pay off
> > eventually.
> > 
> > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > ---
> >  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
> >  1 file changed, 58 insertions(+), 6 deletions(-)
> > 
> > diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> > index 8907ba2069be7..63d0ea5def2d5 100644
> > --- a/libxtables/xtables.c
> > +++ b/libxtables/xtables.c
> > @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
> >  		}
> >  }
> >  
> > +static int xtables_match_prefer(const struct xtables_match *a,
> > +				const struct xtables_match *b);
> > +
> >  void xtables_register_match(struct xtables_match *me)
> >  {
> > +	struct xtables_match **pos;
> > +	bool seen_myself = false;
> > +
> >  	if (me->next) {
> >  		fprintf(stderr, "%s: match \"%s\" already registered\n",
> >  			xt_params->program_name, me->name);
> > @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
> >  	if (me->extra_opts != NULL)
> >  		xtables_check_options(me->name, me->extra_opts);
> >  
> > +	/* order into linked list of matches pending full registration */
> > +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > +		/* NOTE: No extension_cmp() here as we accept all families */
> > +		if (strcmp(me->name, (*pos)->name) ||
> > +		    me->family != (*pos)->family) {
> > +			if (seen_myself)
> > +				break;
> > +			continue;
> > +		}
> > +		seen_myself = true;
> > +		if (xtables_match_prefer(me, *pos) >= 0)
> 
> xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
> number than *pos. So list order is: higher revision first.

Correct.

> > +			break;
> > +	}
> > +	if (!*pos)
> > +		pos = &xtables_pending_matches;
> >  
> > -	/* place on linked list of matches pending full registration */
> > -	me->next = xtables_pending_matches;
> > -	xtables_pending_matches = me;
> > +	me->next = *pos;
> 
> This line above is placing 'me' right before the existing match in the list.

Also correct. As stated in the description, xtables_pending_matches
should be grouped by name and family and within those groups ordered by
descending revision.

> > +	*pos = me;
> 
> This line above only works if *pos is &xtables_pending_matches?

This piece of code confused me at first, too. I even wrote a quick test
to make sure the pointer stuff works as intended. :D

In fact, *pos can't be &xtables_pending_matches: pos is type 'struct
xtables_match **' (note the double pointer). pos is either
&xtables_pending_matches or the address of the right position's previous
element's 'next' pointer. Still confusing, but the for-loop is clear:

| for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {

So by doing '*pos = me', the 'next' pointer value is changed (or the
value of xtables_pending_matches.

> Looking at the in-tree extensions, they are always ordered from lower
> to higher (in array definitions).

This is in favor of the sorting algorithm: Inserting revision N+1 will
find revision N first in its group if revisions 0..N were inserted
before. So having extension revisions ordered ascending in their array
is optimal.

Cheers, Phil

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Pablo Neira Ayuso]

On Sun, Oct 04, 2020 at 04:53:39PM +0200, Phil Sutter wrote:
> Hi Pablo,
> 
> On Sat, Oct 03, 2020 at 01:17:41PM +0200, Pablo Neira Ayuso wrote:
> > On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> > > Insert extensions into pending lists in ordered fashion: Group by
> > > extension name (and, for matches, family) and order groups by descending
> > > revision number.
> > >
> > > This allows to simplify the later full registration considerably. Since
> > > that involves kernel compatibility checks, the extra cycles here pay off
> > > eventually.
> > > 
> > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > ---
> > >  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
> > >  1 file changed, 58 insertions(+), 6 deletions(-)
> > > 
> > > diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> > > index 8907ba2069be7..63d0ea5def2d5 100644
> > > --- a/libxtables/xtables.c
> > > +++ b/libxtables/xtables.c
> > > @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
> > >  		}
> > >  }
> > >  
> > > +static int xtables_match_prefer(const struct xtables_match *a,
> > > +				const struct xtables_match *b);
> > > +
> > >  void xtables_register_match(struct xtables_match *me)
> > >  {
> > > +	struct xtables_match **pos;
> > > +	bool seen_myself = false;
> > > +
> > >  	if (me->next) {
> > >  		fprintf(stderr, "%s: match \"%s\" already registered\n",
> > >  			xt_params->program_name, me->name);
> > > @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
> > >  	if (me->extra_opts != NULL)
> > >  		xtables_check_options(me->name, me->extra_opts);
> > >  
> > > +	/* order into linked list of matches pending full registration */
> > > +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > +		/* NOTE: No extension_cmp() here as we accept all families */
> > > +		if (strcmp(me->name, (*pos)->name) ||
> > > +		    me->family != (*pos)->family) {
> > > +			if (seen_myself)
> > > +				break;
> > > +			continue;
> > > +		}
> > > +		seen_myself = true;
> > > +		if (xtables_match_prefer(me, *pos) >= 0)
> > 
> > xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
> > number than *pos. So list order is: higher revision first.
> 
> Correct.
> 
> > > +			break;
> > > +	}
> > > +	if (!*pos)
> > > +		pos = &xtables_pending_matches;
> > >  
> > > -	/* place on linked list of matches pending full registration */
> > > -	me->next = xtables_pending_matches;
> > > -	xtables_pending_matches = me;
> > > +	me->next = *pos;
> > 
> > This line above is placing 'me' right before the existing match in the list.
> 
> Also correct. As stated in the description, xtables_pending_matches
> should be grouped by name and family and within those groups ordered by
> descending revision.
> 
> > > +	*pos = me;
> > 
> > This line above only works if *pos is &xtables_pending_matches?
> 
> This piece of code confused me at first, too. I even wrote a quick test
> to make sure the pointer stuff works as intended. :D
> 
> In fact, *pos can't be &xtables_pending_matches: pos is type 'struct
> xtables_match **' (note the double pointer). pos is either
> &xtables_pending_matches or the address of the right position's previous
> element's 'next' pointer. Still confusing, but the for-loop is clear:
> 
> | for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> 
> So by doing '*pos = me', the 'next' pointer value is changed (or the
> value of xtables_pending_matches.

pos is always &xtables_pending_matches:

- The first element in the array finds no matching, then:

        if (!*pos)
               pos = &xtables_pending_matches;

  kicks in and and pos is set to &xtables_pending_matches, so this is
  inserted in the first position of the xtables_pending_matches.

- The follow up element in the array (higher revision) finds itself at
  the very beginning of the iteration, so pos here is
  &xtables_pending_matches too.

So *pos = me; is always updating the next pointer in the
xtables_pending_matches.

Same picture you're describing? I just found a bit confusing that this
is using *pos = me to refresh xtables_pending_matches, probably you
can just use

xtables_pending_matches = me;

I would add a bug check somewhere too in case that an extension is
not inserted in the first position, *pos = me won't work in that case.

May I suggest you please extend the commit message a bit to describe
this logic?

> > Looking at the in-tree extensions, they are always ordered from lower
> > to higher (in array definitions).
> 
> This is in favor of the sorting algorithm: Inserting revision N+1 will
> find revision N first in its group if revisions 0..N were inserted
> before. So having extension revisions ordered ascending in their array
> is optimal.

This is optimizing userspace for more recent kernels, that sounds
reasonable.

Re: [iptables PATCH 2/3] libxtables: Simplify pending extension registration

[Pablo Neira Ayuso]

On Wed, Sep 23, 2020 at 12:53:40AM +0200, Phil Sutter wrote:
> Assuming that pending extensions are sorted by first name and family,
> then descending revision, the decision where to insert a newly
> registered extension may be simplified by memorizing the previous
> registration (which obviously is of same name and family and higher
> revision).
> 
> As a side-effect, fix for unsupported old extension revisions lingering
> in pending extension list forever and being retried with every use of
> the given extension. Any revision being rejected by the kernel may
> safely be dropped iff a previous (read: higher) revision was accepted
> already.
> 
> Yet another side-effect of this change is the removal of an unwanted
> recursion by xtables_fully_register_pending_*() into itself via
> xtables_find_*().

LGTM.

Re: [iptables PATCH 3/3] libxtables: Register multiple extensions in ascending order

[Pablo Neira Ayuso]

On Wed, Sep 23, 2020 at 12:53:41AM +0200, Phil Sutter wrote:
> The newly introduced ordered insert algorithm in
> xtables_register_{match,target}() works best if extensions of same name
> are passed in ascending revisions. Since this is the case in about all
> extensions' arrays, iterate over them from beginning to end.

This patch should come first in the series, my understanding is that
1/3 assumes that extensions are registered from lower to higher
revision number.

> Signed-off-by: Phil Sutter <phil@nwl.cc>
> ---
>  libxtables/xtables.c | 14 ++++++++------
>  1 file changed, 8 insertions(+), 6 deletions(-)
> 
> diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> index de74d361a53af..90b1195c45a58 100644
> --- a/libxtables/xtables.c
> +++ b/libxtables/xtables.c
> @@ -1139,9 +1139,10 @@ static bool xtables_fully_register_pending_match(struct xtables_match *me,
>  
>  void xtables_register_matches(struct xtables_match *match, unsigned int n)
>  {
> -	do {
> -		xtables_register_match(&match[--n]);
> -	} while (n > 0);
> +	int i;
> +
> +	for (i = 0; i < n; i++)
> +		xtables_register_match(&match[i]);
>  }
>  
>  void xtables_register_target(struct xtables_target *me)
> @@ -1264,9 +1265,10 @@ static bool xtables_fully_register_pending_target(struct xtables_target *me,
>  
>  void xtables_register_targets(struct xtables_target *target, unsigned int n)
>  {
> -	do {
> -		xtables_register_target(&target[--n]);
> -	} while (n > 0);
> +	int i;
> +
> +	for (i = 0; i < n; i++)
> +		xtables_register_target(&target[i]);
>  }
>  
>  /* receives a list of xtables_rule_match, release them */
> -- 
> 2.28.0
> 

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Phil Sutter]

Hi Pablo,

On Tue, Oct 06, 2020 at 12:42:55AM +0200, Pablo Neira Ayuso wrote:
> On Sun, Oct 04, 2020 at 04:53:39PM +0200, Phil Sutter wrote:
> > On Sat, Oct 03, 2020 at 01:17:41PM +0200, Pablo Neira Ayuso wrote:
> > > On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> > > > Insert extensions into pending lists in ordered fashion: Group by
> > > > extension name (and, for matches, family) and order groups by descending
> > > > revision number.
> > > >
> > > > This allows to simplify the later full registration considerably. Since
> > > > that involves kernel compatibility checks, the extra cycles here pay off
> > > > eventually.
> > > > 
> > > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > > ---
> > > >  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
> > > >  1 file changed, 58 insertions(+), 6 deletions(-)
> > > > 
> > > > diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> > > > index 8907ba2069be7..63d0ea5def2d5 100644
> > > > --- a/libxtables/xtables.c
> > > > +++ b/libxtables/xtables.c
> > > > @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
> > > >  		}
> > > >  }
> > > >  
> > > > +static int xtables_match_prefer(const struct xtables_match *a,
> > > > +				const struct xtables_match *b);
> > > > +
> > > >  void xtables_register_match(struct xtables_match *me)
> > > >  {
> > > > +	struct xtables_match **pos;
> > > > +	bool seen_myself = false;
> > > > +
> > > >  	if (me->next) {
> > > >  		fprintf(stderr, "%s: match \"%s\" already registered\n",
> > > >  			xt_params->program_name, me->name);
> > > > @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
> > > >  	if (me->extra_opts != NULL)
> > > >  		xtables_check_options(me->name, me->extra_opts);
> > > >  
> > > > +	/* order into linked list of matches pending full registration */
> > > > +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > > +		/* NOTE: No extension_cmp() here as we accept all families */
> > > > +		if (strcmp(me->name, (*pos)->name) ||
> > > > +		    me->family != (*pos)->family) {
> > > > +			if (seen_myself)
> > > > +				break;
> > > > +			continue;
> > > > +		}
> > > > +		seen_myself = true;
> > > > +		if (xtables_match_prefer(me, *pos) >= 0)
> > > 
> > > xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
> > > number than *pos. So list order is: higher revision first.
> > 
> > Correct.
> > 
> > > > +			break;
> > > > +	}
> > > > +	if (!*pos)
> > > > +		pos = &xtables_pending_matches;
> > > >  
> > > > -	/* place on linked list of matches pending full registration */
> > > > -	me->next = xtables_pending_matches;
> > > > -	xtables_pending_matches = me;
> > > > +	me->next = *pos;
> > > 
> > > This line above is placing 'me' right before the existing match in the list.
> > 
> > Also correct. As stated in the description, xtables_pending_matches
> > should be grouped by name and family and within those groups ordered by
> > descending revision.
> > 
> > > > +	*pos = me;
> > > 
> > > This line above only works if *pos is &xtables_pending_matches?
> > 
> > This piece of code confused me at first, too. I even wrote a quick test
> > to make sure the pointer stuff works as intended. :D
> > 
> > In fact, *pos can't be &xtables_pending_matches: pos is type 'struct
> > xtables_match **' (note the double pointer). pos is either
> > &xtables_pending_matches or the address of the right position's previous
> > element's 'next' pointer. Still confusing, but the for-loop is clear:
> > 
> > | for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > 
> > So by doing '*pos = me', the 'next' pointer value is changed (or the
> > value of xtables_pending_matches.
> 
> pos is always &xtables_pending_matches:
> 
> - The first element in the array finds no matching, then:
> 
>         if (!*pos)
>                pos = &xtables_pending_matches;
> 
>   kicks in and and pos is set to &xtables_pending_matches, so this is
>   inserted in the first position of the xtables_pending_matches.
> 
> - The follow up element in the array (higher revision) finds itself at
>   the very beginning of the iteration, so pos here is
>   &xtables_pending_matches too.
> 
> So *pos = me; is always updating the next pointer in the
> xtables_pending_matches.

This is true only if you assume the ordering of arrays passed to the
function. But you can't since it's an exported library function. Also,
there are already cases where the above does not hold due to the
grouping by name *and* family value. Apply the patch, build with
-DDEBUG, add a rule with connlimit match and you'll see.

I found a bug, though: When inserting same name and family extensions in
descending revision order, for all consecutive extensions the for-loop
never breaks and the 'if (!*pos)' clause inserts the new (lowest)
revision into the beginning. The fix is trivial though.

[...]
> May I suggest you please extend the commit message a bit to describe
> this logic?

Yes, I will do that.

Cheers, Phil

Re: [iptables PATCH 3/3] libxtables: Register multiple extensions in ascending order

[Phil Sutter]

On Tue, Oct 06, 2020 at 01:41:21AM +0200, Pablo Neira Ayuso wrote:
> On Wed, Sep 23, 2020 at 12:53:41AM +0200, Phil Sutter wrote:
> > The newly introduced ordered insert algorithm in
> > xtables_register_{match,target}() works best if extensions of same name
> > are passed in ascending revisions. Since this is the case in about all
> > extensions' arrays, iterate over them from beginning to end.
> 
> This patch should come first in the series, my understanding is that
> 1/3 assumes that extensions are registered from lower to higher
> revision number.

No, the algorithm is supposed to work with arbitrary input. This is
merely an optimization given how extension arrays are typically ordered.

Cheers, Phil

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Pablo Neira Ayuso]

On Tue, Oct 06, 2020 at 11:27:23AM +0200, Phil Sutter wrote:
> Hi Pablo,
> 
> On Tue, Oct 06, 2020 at 12:42:55AM +0200, Pablo Neira Ayuso wrote:
> > On Sun, Oct 04, 2020 at 04:53:39PM +0200, Phil Sutter wrote:
> > > On Sat, Oct 03, 2020 at 01:17:41PM +0200, Pablo Neira Ayuso wrote:
> > > > On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> > > > > Insert extensions into pending lists in ordered fashion: Group by
> > > > > extension name (and, for matches, family) and order groups by descending
> > > > > revision number.
> > > > >
> > > > > This allows to simplify the later full registration considerably. Since
> > > > > that involves kernel compatibility checks, the extra cycles here pay off
> > > > > eventually.
> > > > > 
> > > > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > > > ---
> > > > >  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
> > > > >  1 file changed, 58 insertions(+), 6 deletions(-)
> > > > > 
> > > > > diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> > > > > index 8907ba2069be7..63d0ea5def2d5 100644
> > > > > --- a/libxtables/xtables.c
> > > > > +++ b/libxtables/xtables.c
> > > > > @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
> > > > >  		}
> > > > >  }
> > > > >  
> > > > > +static int xtables_match_prefer(const struct xtables_match *a,
> > > > > +				const struct xtables_match *b);
> > > > > +
> > > > >  void xtables_register_match(struct xtables_match *me)
> > > > >  {
> > > > > +	struct xtables_match **pos;
> > > > > +	bool seen_myself = false;
> > > > > +
> > > > >  	if (me->next) {
> > > > >  		fprintf(stderr, "%s: match \"%s\" already registered\n",
> > > > >  			xt_params->program_name, me->name);
> > > > > @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
> > > > >  	if (me->extra_opts != NULL)
> > > > >  		xtables_check_options(me->name, me->extra_opts);
> > > > >  
> > > > > +	/* order into linked list of matches pending full registration */
> > > > > +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > > > +		/* NOTE: No extension_cmp() here as we accept all families */
> > > > > +		if (strcmp(me->name, (*pos)->name) ||
> > > > > +		    me->family != (*pos)->family) {
> > > > > +			if (seen_myself)
> > > > > +				break;
> > > > > +			continue;
> > > > > +		}
> > > > > +		seen_myself = true;
> > > > > +		if (xtables_match_prefer(me, *pos) >= 0)
> > > > 
> > > > xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
> > > > number than *pos. So list order is: higher revision first.
> > > 
> > > Correct.
> > > 
> > > > > +			break;
> > > > > +	}
> > > > > +	if (!*pos)
> > > > > +		pos = &xtables_pending_matches;
> > > > >  
> > > > > -	/* place on linked list of matches pending full registration */
> > > > > -	me->next = xtables_pending_matches;
> > > > > -	xtables_pending_matches = me;
> > > > > +	me->next = *pos;
> > > > 
> > > > This line above is placing 'me' right before the existing match in the list.
> > > 
> > > Also correct. As stated in the description, xtables_pending_matches
> > > should be grouped by name and family and within those groups ordered by
> > > descending revision.
> > > 
> > > > > +	*pos = me;
> > > > 
> > > > This line above only works if *pos is &xtables_pending_matches?
> > > 
> > > This piece of code confused me at first, too. I even wrote a quick test
> > > to make sure the pointer stuff works as intended. :D
> > > 
> > > In fact, *pos can't be &xtables_pending_matches: pos is type 'struct
> > > xtables_match **' (note the double pointer). pos is either
> > > &xtables_pending_matches or the address of the right position's previous
> > > element's 'next' pointer. Still confusing, but the for-loop is clear:
> > > 
> > > | for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > 
> > > So by doing '*pos = me', the 'next' pointer value is changed (or the
> > > value of xtables_pending_matches.
> > 
> > pos is always &xtables_pending_matches:
> > 
> > - The first element in the array finds no matching, then:
> > 
> >         if (!*pos)
> >                pos = &xtables_pending_matches;
> > 
> >   kicks in and and pos is set to &xtables_pending_matches, so this is
> >   inserted in the first position of the xtables_pending_matches.
> > 
> > - The follow up element in the array (higher revision) finds itself at
> >   the very beginning of the iteration, so pos here is
> >   &xtables_pending_matches too.
> > 
> > So *pos = me; is always updating the next pointer in the
> > xtables_pending_matches.
> 
> This is true only if you assume the ordering of arrays passed to the
> function. But you can't since it's an exported library function. Also,
> there are already cases where the above does not hold due to the
> grouping by name *and* family value. Apply the patch, build with
> -DDEBUG, add a rule with connlimit match and you'll see.

If you can insert entries in the middle of the list, before an
existing node, assuming

        pos = &(*pos)->next

then

        *pos = me;

is updating the ->next pointer of the existing entry in the list to
'me' (appending).

But the existing entry is actually placed after the new one (inserting).

        me->next = *pos;

do I need more coffee here?

> I found a bug, though: When inserting same name and family extensions in
> descending revision order, for all consecutive extensions the for-loop
> never breaks and the 'if (!*pos)' clause inserts the new (lowest)
> revision into the beginning. The fix is trivial though.

Just to clarify: You assume that input array does _not_ need to be
sorted from lower to higher, correct? This was not obvious to me.

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Phil Sutter]

On Tue, Oct 06, 2020 at 11:50:47AM +0200, Pablo Neira Ayuso wrote:
> On Tue, Oct 06, 2020 at 11:27:23AM +0200, Phil Sutter wrote:
> > Hi Pablo,
> > 
> > On Tue, Oct 06, 2020 at 12:42:55AM +0200, Pablo Neira Ayuso wrote:
> > > On Sun, Oct 04, 2020 at 04:53:39PM +0200, Phil Sutter wrote:
> > > > On Sat, Oct 03, 2020 at 01:17:41PM +0200, Pablo Neira Ayuso wrote:
> > > > > On Wed, Sep 23, 2020 at 12:53:39AM +0200, Phil Sutter wrote:
> > > > > > Insert extensions into pending lists in ordered fashion: Group by
> > > > > > extension name (and, for matches, family) and order groups by descending
> > > > > > revision number.
> > > > > >
> > > > > > This allows to simplify the later full registration considerably. Since
> > > > > > that involves kernel compatibility checks, the extra cycles here pay off
> > > > > > eventually.
> > > > > > 
> > > > > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > > > > ---
> > > > > >  libxtables/xtables.c | 64 +++++++++++++++++++++++++++++++++++++++-----
> > > > > >  1 file changed, 58 insertions(+), 6 deletions(-)
> > > > > > 
> > > > > > diff --git a/libxtables/xtables.c b/libxtables/xtables.c
> > > > > > index 8907ba2069be7..63d0ea5def2d5 100644
> > > > > > --- a/libxtables/xtables.c
> > > > > > +++ b/libxtables/xtables.c
> > > > > > @@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
> > > > > >  		}
> > > > > >  }
> > > > > >  
> > > > > > +static int xtables_match_prefer(const struct xtables_match *a,
> > > > > > +				const struct xtables_match *b);
> > > > > > +
> > > > > >  void xtables_register_match(struct xtables_match *me)
> > > > > >  {
> > > > > > +	struct xtables_match **pos;
> > > > > > +	bool seen_myself = false;
> > > > > > +
> > > > > >  	if (me->next) {
> > > > > >  		fprintf(stderr, "%s: match \"%s\" already registered\n",
> > > > > >  			xt_params->program_name, me->name);
> > > > > > @@ -1001,10 +1007,32 @@ void xtables_register_match(struct xtables_match *me)
> > > > > >  	if (me->extra_opts != NULL)
> > > > > >  		xtables_check_options(me->name, me->extra_opts);
> > > > > >  
> > > > > > +	/* order into linked list of matches pending full registration */
> > > > > > +	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > > > > +		/* NOTE: No extension_cmp() here as we accept all families */
> > > > > > +		if (strcmp(me->name, (*pos)->name) ||
> > > > > > +		    me->family != (*pos)->family) {
> > > > > > +			if (seen_myself)
> > > > > > +				break;
> > > > > > +			continue;
> > > > > > +		}
> > > > > > +		seen_myself = true;
> > > > > > +		if (xtables_match_prefer(me, *pos) >= 0)
> > > > > 
> > > > > xtables_match_prefer() evaluates >= 0 if 'me' has higher revision
> > > > > number than *pos. So list order is: higher revision first.
> > > > 
> > > > Correct.
> > > > 
> > > > > > +			break;
> > > > > > +	}
> > > > > > +	if (!*pos)
> > > > > > +		pos = &xtables_pending_matches;
> > > > > >  
> > > > > > -	/* place on linked list of matches pending full registration */
> > > > > > -	me->next = xtables_pending_matches;
> > > > > > -	xtables_pending_matches = me;
> > > > > > +	me->next = *pos;
> > > > > 
> > > > > This line above is placing 'me' right before the existing match in the list.
> > > > 
> > > > Also correct. As stated in the description, xtables_pending_matches
> > > > should be grouped by name and family and within those groups ordered by
> > > > descending revision.
> > > > 
> > > > > > +	*pos = me;
> > > > > 
> > > > > This line above only works if *pos is &xtables_pending_matches?
> > > > 
> > > > This piece of code confused me at first, too. I even wrote a quick test
> > > > to make sure the pointer stuff works as intended. :D
> > > > 
> > > > In fact, *pos can't be &xtables_pending_matches: pos is type 'struct
> > > > xtables_match **' (note the double pointer). pos is either
> > > > &xtables_pending_matches or the address of the right position's previous
> > > > element's 'next' pointer. Still confusing, but the for-loop is clear:
> > > > 
> > > > | for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
> > > > 
> > > > So by doing '*pos = me', the 'next' pointer value is changed (or the
> > > > value of xtables_pending_matches.
> > > 
> > > pos is always &xtables_pending_matches:
> > > 
> > > - The first element in the array finds no matching, then:
> > > 
> > >         if (!*pos)
> > >                pos = &xtables_pending_matches;
> > > 
> > >   kicks in and and pos is set to &xtables_pending_matches, so this is
> > >   inserted in the first position of the xtables_pending_matches.
> > > 
> > > - The follow up element in the array (higher revision) finds itself at
> > >   the very beginning of the iteration, so pos here is
> > >   &xtables_pending_matches too.
> > > 
> > > So *pos = me; is always updating the next pointer in the
> > > xtables_pending_matches.
> > 
> > This is true only if you assume the ordering of arrays passed to the
> > function. But you can't since it's an exported library function. Also,
> > there are already cases where the above does not hold due to the
> > grouping by name *and* family value. Apply the patch, build with
> > -DDEBUG, add a rule with connlimit match and you'll see.
> 
> If you can insert entries in the middle of the list, before an
> existing node, assuming
> 
>         pos = &(*pos)->next
> 
> then
> 
>         *pos = me;
> 
> is updating the ->next pointer of the existing entry in the list to
> 'me' (appending).
> 
> But the existing entry is actually placed after the new one (inserting).
> 
>         me->next = *pos;
> 
> do I need more coffee here?

Seems so! :D

I am always inserting me before *pos. The for-loop searches the relevant
group first (by comparing name and family). If found, 'seen_myself' is
set to true. Within that group, xtables_match_prefer() serves in finding
the first element which is less preferred than 'me'. At that point we
break and insert. If no less preferred one is found, due to
'seen_myself' the loop breaks at the first item no longer belonging to
the own group. If the own group is not found at all (i.e., we insert the
first item in that group), the insert is done up front (replacing
xtables_pending_matches value) because we assume more group members to
come and so the for-loop does not have to iterate over all other groups.

> > I found a bug, though: When inserting same name and family extensions in
> > descending revision order, for all consecutive extensions the for-loop
> > never breaks and the 'if (!*pos)' clause inserts the new (lowest)
> > revision into the beginning. The fix is trivial though.
> 
> Just to clarify: You assume that input array does _not_ need to be
> sorted from lower to higher, correct? This was not obvious to me.

Put more simply: I'm not assuming *any* ordering in input, not even
grouped input by name. But I chose the algorithm to optimize for input
which is grouped by name and family and sorted by ascending revision
within groups, as that is mostly the case in in-tree extensions.

Cheers, Phil

Re: [iptables PATCH 1/3] libxtables: Make sure extensions register in revision order

[Pablo Neira Ayuso]

On Tue, Oct 06, 2020 at 12:13:03PM +0200, Phil Sutter wrote:
[...]
> Put more simply: I'm not assuming *any* ordering in input, not even
> grouped input by name. But I chose the algorithm to optimize for input
> which is grouped by name and family and sorted by ascending revision
> within groups, as that is mostly the case in in-tree extensions.

Looks good, thanks for explaining.

[iptables PATCH v2] libxtables: Make sure extensions register in revision order

[Phil Sutter]

Insert extensions into pending lists in ordered fashion: Group by
extension name (and, for matches, family) and order groups by descending
revision number.

This allows to simplify the later full registration considerably. Since
that involves kernel compatibility checks, the extra cycles here pay off
eventually.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
Changes since v1:
- Fix wrong insertion order for arrays with ascending revision: If
  pending extension list was empty, new lowest revision items were
  always inserted first.
- Add some comments explaining the algorithm.
---
 libxtables/xtables.c | 71 +++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 64 insertions(+), 7 deletions(-)

diff --git a/libxtables/xtables.c b/libxtables/xtables.c
index 8907ba2069be7..de52e3e2bbc15 100644
--- a/libxtables/xtables.c
+++ b/libxtables/xtables.c
@@ -948,8 +948,14 @@ static void xtables_check_options(const char *name, const struct option *opt)
 		}
 }
 
+static int xtables_match_prefer(const struct xtables_match *a,
+				const struct xtables_match *b);
+
 void xtables_register_match(struct xtables_match *me)
 {
+	struct xtables_match **pos;
+	bool seen_myself = false;
+
 	if (me->next) {
 		fprintf(stderr, "%s: match \"%s\" already registered\n",
 			xt_params->program_name, me->name);
@@ -1001,10 +1007,34 @@ void xtables_register_match(struct xtables_match *me)
 	if (me->extra_opts != NULL)
 		xtables_check_options(me->name, me->extra_opts);
 
-
-	/* place on linked list of matches pending full registration */
-	me->next = xtables_pending_matches;
-	xtables_pending_matches = me;
+	/* order into linked list of matches pending full registration */
+	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
+		/* group by name and family */
+		if (strcmp(me->name, (*pos)->name) ||
+		    me->family != (*pos)->family) {
+			if (seen_myself)
+				break; /* end of own group, append to it */
+			continue;
+		}
+		/* found own group */
+		seen_myself = true;
+		if (xtables_match_prefer(me, *pos) >= 0)
+			break; /* put preferred items first in group */
+	}
+	/* if own group was not found, prepend item */
+	if (!*pos && !seen_myself)
+		pos = &xtables_pending_matches;
+
+	me->next = *pos;
+	*pos = me;
+#ifdef DEBUG
+	printf("%s: inserted match %s (family %d, revision %d):\n",
+			__func__, me->name, me->family, me->revision);
+	for (pos = &xtables_pending_matches; *pos; pos = &(*pos)->next) {
+		printf("%s:\tmatch %s (family %d, revision %d)\n", __func__,
+		       (*pos)->name, (*pos)->family, (*pos)->revision);
+	}
+#endif
 }
 
 /**
@@ -1143,6 +1173,9 @@ void xtables_register_matches(struct xtables_match *match, unsigned int n)
 
 void xtables_register_target(struct xtables_target *me)
 {
+	struct xtables_target **pos;
+	bool seen_myself = false;
+
 	if (me->next) {
 		fprintf(stderr, "%s: target \"%s\" already registered\n",
 			xt_params->program_name, me->name);
@@ -1198,9 +1231,33 @@ void xtables_register_target(struct xtables_target *me)
 	if (me->family != afinfo->family && me->family != AF_UNSPEC)
 		return;
 
-	/* place on linked list of targets pending full registration */
-	me->next = xtables_pending_targets;
-	xtables_pending_targets = me;
+	/* order into linked list of targets pending full registration */
+	for (pos = &xtables_pending_targets; *pos; pos = &(*pos)->next) {
+		/* group by name */
+		if (!extension_cmp(me->name, (*pos)->name, (*pos)->family)) {
+			if (seen_myself)
+				break; /* end of own group, append to it */
+			continue;
+		}
+		/* found own group */
+		seen_myself = true;
+		if (xtables_target_prefer(me, *pos) >= 0)
+			break; /* put preferred items first in group */
+	}
+	/* if own group was not found, prepend item */
+	if (!*pos && !seen_myself)
+		pos = &xtables_pending_targets;
+
+	me->next = *pos;
+	*pos = me;
+#ifdef DEBUG
+	printf("%s: inserted target %s (family %d, revision %d):\n",
+			__func__, me->name, me->family, me->revision);
+	for (pos = &xtables_pending_targets; *pos; pos = &(*pos)->next) {
+		printf("%s:\ttarget %s (family %d, revision %d)\n", __func__,
+		       (*pos)->name, (*pos)->family, (*pos)->revision);
+	}
+#endif
 }
 
 static bool xtables_fully_register_pending_target(struct xtables_target *me)
-- 
2.28.0

Re: [iptables PATCH v2] libxtables: Make sure extensions register in revision order

[Pablo Neira Ayuso]

On Tue, Oct 06, 2020 at 02:07:48PM +0200, Phil Sutter wrote:
> Insert extensions into pending lists in ordered fashion: Group by
> extension name (and, for matches, family) and order groups by descending
> revision number.
> 
> This allows to simplify the later full registration considerably. Since
> that involves kernel compatibility checks, the extra cycles here pay off
> eventually.

LGTM.

Re: [iptables PATCH 0/3] libxtables: Fix for pointless socket() calls

[Pablo Neira Ayuso]

On Wed, Sep 23, 2020 at 12:53:38AM +0200, Phil Sutter wrote:
> Patch 1 establishes the needed sorting in pending extension lists,
> patch 2 then simplifies xtables_fully_register_pending_*() functions.
> Patch 3 is strictly speaking not necessary but nice to have as it
> streamlines array-based extension registrators with the extension
> sorting.

Series with patch 1 (v2) LGTM.