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

[Pablo Neira Ayuso <pablo@netfilter.org>]

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.