[ovs-dev,RFC] expr: Use sset for nested expr instead of list

To speed up search of possible recursive symbols
use sset. This also prevents the dangling pointer
warning wtih GCC 12 [0].

[0] https://bugzilla.redhat.com/2145107
Signed-off-by: Ales Musil <amusil@redhat.com>
---
 lib/expr.c | 71 ++++++++++++++++++++++++------------------------------
 1 file changed, 32 insertions(+), 39 deletions(-)

On 11/28/22 15:25, Ales Musil wrote:
> To speed up search of possible recursive symbols
> use sset. This also prevents the dangling pointer
> warning wtih GCC 12 [0].
> 
> [0] https://bugzilla.redhat.com/2145107
> Signed-off-by: Ales Musil <amusil@redhat.com>
> ---

Hi Ales,

I think this makes sense but I have a few comments below.

>  lib/expr.c | 71 ++++++++++++++++++++++++------------------------------
>  1 file changed, 32 insertions(+), 39 deletions(-)
> 
> diff --git a/lib/expr.c b/lib/expr.c
> index d1f9d28ca..f581c29dc 100644
> --- a/lib/expr.c
> +++ b/lib/expr.c
> @@ -35,7 +35,7 @@ VLOG_DEFINE_THIS_MODULE(expr);
>  
>  static struct expr *parse_and_annotate(const char *s,
>                                         const struct shash *symtab,
> -                                       struct ovs_list *nesting,
> +                                       struct sset *nesting,
>                                         char **errorp);
>  
>  /* Returns the name of measurement level 'level'. */
> @@ -1572,9 +1572,10 @@ expr_field_parse(struct lexer *lexer, const struct shash *symtab,
>          while (symbol) {
>              if (symbol->prereqs) {
>                  char *error;
> -                struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> +                struct sset nesting = SSET_INITIALIZER(&nesting);
>                  struct expr *e = parse_and_annotate(symbol->prereqs, symtab,
>                                                      &nesting, &error);
> +                sset_destroy(&nesting);
>                  if (error) {
>                      lexer_error(lexer, "%s", error);
>                      free(error);
> @@ -1930,21 +1931,12 @@ expr_destroy(struct expr *expr)
>  
>  /* Annotation. */
>  
> -/* An element in a linked list of symbols.
> - *
> - * Used to detect when a symbol is being expanded recursively, to allow
> - * flagging an error. */
> -struct annotation_nesting {
> -    struct ovs_list node;
> -    const struct expr_symbol *symbol;
> -};
> -
>  static struct expr *expr_annotate_(struct expr *, const struct shash *symtab,
> -                                   struct ovs_list *nesting, char **errorp);
> +                                   struct sset *nesting, char **errorp);
>  
>  static struct expr *
>  parse_and_annotate(const char *s, const struct shash *symtab,
> -                   struct ovs_list *nesting, char **errorp)
> +                   struct sset *nesting, char **errorp)
>  {
>      char *error;
>      struct expr *expr;
> @@ -1966,28 +1958,24 @@ parse_and_annotate(const char *s, const struct shash *symtab,
>  
>  static struct expr *
>  expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> -                  bool append_prereqs, struct ovs_list *nesting, char **errorp)
> +                  bool append_prereqs, struct sset *nesting, char **errorp)
>  {
>      const struct expr_symbol *symbol = expr->cmp.symbol;
> -    const struct annotation_nesting *iter;
> -    LIST_FOR_EACH (iter, node, nesting) {
> -        if (iter->symbol == symbol) {
> -            *errorp = xasprintf("Recursive expansion of symbol `%s'.",
> -                                symbol->name);
> -            expr_destroy(expr);
> -            return NULL;
> -        }
> +
> +    if (sset_find_and_delete(nesting, symbol->name)) {

Why _and_delete?  The recursive call that inserted it should also delete it.

> +        *errorp = xasprintf("Recursive expansion of symbol `%s'.",
> +                            symbol->name);
> +        expr_destroy(expr);
> +        return NULL;
>      }
>  
> -    struct annotation_nesting an;
> -    an.symbol = symbol;
> -    ovs_list_push_back(nesting, &an.node);
> +    sset_add(nesting, symbol->name);

We can actually skip the sset_find..() above because sset_add() returns
NULL if the name already existed.

>  
>      struct expr *prereqs = NULL;
>      if (append_prereqs && symbol->prereqs) {
>          prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
>          if (!prereqs) {
> -            goto error;
> +            goto out;
>          }
>      }
>  
> @@ -2001,7 +1989,7 @@ expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
>          predicate = parse_and_annotate(symbol->predicate, symtab,
>                                         nesting, errorp);
>          if (!predicate) {
> -            goto error;
> +            goto out;
>          }
>  
>          bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
> @@ -2015,20 +2003,22 @@ expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
>      }
>  
>      *errorp = NULL;
> -    ovs_list_remove(&an.node);
> -    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
>  
> -error:
> -    expr_destroy(expr);
> -    expr_destroy(prereqs);
> -    ovs_list_remove(&an.node);
> -    return NULL;
> +out:
> +    sset_find_and_delete(nesting, symbol->name);

To avoid the lookup and to be more efficient I think we could just store
the symbol sset_node when we insert it and use pass it here to
sset_delete() instead.

Thanks,
Dumitru

> +    if (*errorp) {
> +        expr_destroy(expr);
> +        expr_destroy(prereqs);
> +        return NULL;
> +    }
> +
> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
>  }
>  
>  /* Append (logical AND) prerequisites for given symbol to the expression. */
>  static struct expr *
>  expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
> -                    const struct shash *symtab, struct ovs_list *nesting,
> +                    const struct shash *symtab, struct sset *nesting,
>                      char **errorp)
>  {
>      struct expr *prereqs = NULL;
> @@ -2053,7 +2043,7 @@ static const struct expr_symbol *expr_get_unique_symbol(
>   * have arranged to deal with them). */
>  static struct expr *
>  expr_annotate__(struct expr *expr, const struct shash *symtab,
> -                bool append_prereqs, struct ovs_list *nesting, char **errorp)
> +                bool append_prereqs, struct sset *nesting, char **errorp)
>  {
>      switch (expr->type) {
>      case EXPR_T_CMP:
> @@ -2112,7 +2102,7 @@ expr_annotate__(struct expr *expr, const struct shash *symtab,
>   * Uses 'nesting' to ensure that a given symbol is not recursively expanded. */
>  static struct expr *
>  expr_annotate_(struct expr *expr, const struct shash *symtab,
> -               struct ovs_list *nesting, char **errorp)
> +               struct sset *nesting, char **errorp)
>  {
>      return expr_annotate__(expr, symtab, true, nesting, errorp);
>  }
> @@ -2138,8 +2128,11 @@ expr_annotate_(struct expr *expr, const struct shash *symtab,
>  struct expr *
>  expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
>  {
> -    struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> -    return expr_annotate_(expr, symtab, &nesting, errorp);
> +    struct sset nesting = SSET_INITIALIZER(&nesting);
> +    struct expr *result = expr_annotate_(expr, symtab, &nesting, errorp);
> +    sset_destroy(&nesting);
> +
> +    return result;
>  }
>  
>  static struct expr *

On Tue, Nov 29, 2022 at 2:46 PM Dumitru Ceara <dceara@redhat.com> wrote:

> On 11/28/22 15:25, Ales Musil wrote:
> > To speed up search of possible recursive symbols
> > use sset. This also prevents the dangling pointer
> > warning wtih GCC 12 [0].
> >
> > [0] https://bugzilla.redhat.com/2145107
> > Signed-off-by: Ales Musil <amusil@redhat.com>
> > ---
>
> Hi Ales,
>
> I think this makes sense but I have a few comments below.
>

Hi Dumitru,

thanks for the review. Let's see if others agree with this approach, if so
I'll post v2 that will address your comments.

Thanks,
Ales


>
> >  lib/expr.c | 71 ++++++++++++++++++++++++------------------------------
> >  1 file changed, 32 insertions(+), 39 deletions(-)
> >
> > diff --git a/lib/expr.c b/lib/expr.c
> > index d1f9d28ca..f581c29dc 100644
> > --- a/lib/expr.c
> > +++ b/lib/expr.c
> > @@ -35,7 +35,7 @@ VLOG_DEFINE_THIS_MODULE(expr);
> >
> >  static struct expr *parse_and_annotate(const char *s,
> >                                         const struct shash *symtab,
> > -                                       struct ovs_list *nesting,
> > +                                       struct sset *nesting,
> >                                         char **errorp);
> >
> >  /* Returns the name of measurement level 'level'. */
> > @@ -1572,9 +1572,10 @@ expr_field_parse(struct lexer *lexer, const
> struct shash *symtab,
> >          while (symbol) {
> >              if (symbol->prereqs) {
> >                  char *error;
> > -                struct ovs_list nesting =
> OVS_LIST_INITIALIZER(&nesting);
> > +                struct sset nesting = SSET_INITIALIZER(&nesting);
> >                  struct expr *e = parse_and_annotate(symbol->prereqs,
> symtab,
> >                                                      &nesting, &error);
> > +                sset_destroy(&nesting);
> >                  if (error) {
> >                      lexer_error(lexer, "%s", error);
> >                      free(error);
> > @@ -1930,21 +1931,12 @@ expr_destroy(struct expr *expr)
> >
> >  /* Annotation. */
> >
> > -/* An element in a linked list of symbols.
> > - *
> > - * Used to detect when a symbol is being expanded recursively, to allow
> > - * flagging an error. */
> > -struct annotation_nesting {
> > -    struct ovs_list node;
> > -    const struct expr_symbol *symbol;
> > -};
> > -
> >  static struct expr *expr_annotate_(struct expr *, const struct shash
> *symtab,
> > -                                   struct ovs_list *nesting, char
> **errorp);
> > +                                   struct sset *nesting, char **errorp);
> >
> >  static struct expr *
> >  parse_and_annotate(const char *s, const struct shash *symtab,
> > -                   struct ovs_list *nesting, char **errorp)
> > +                   struct sset *nesting, char **errorp)
> >  {
> >      char *error;
> >      struct expr *expr;
> > @@ -1966,28 +1958,24 @@ parse_and_annotate(const char *s, const struct
> shash *symtab,
> >
> >  static struct expr *
> >  expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> > -                  bool append_prereqs, struct ovs_list *nesting, char
> **errorp)
> > +                  bool append_prereqs, struct sset *nesting, char
> **errorp)
> >  {
> >      const struct expr_symbol *symbol = expr->cmp.symbol;
> > -    const struct annotation_nesting *iter;
> > -    LIST_FOR_EACH (iter, node, nesting) {
> > -        if (iter->symbol == symbol) {
> > -            *errorp = xasprintf("Recursive expansion of symbol `%s'.",
> > -                                symbol->name);
> > -            expr_destroy(expr);
> > -            return NULL;
> > -        }
> > +
> > +    if (sset_find_and_delete(nesting, symbol->name)) {
>
> Why _and_delete?  The recursive call that inserted it should also delete
> it.
>
> > +        *errorp = xasprintf("Recursive expansion of symbol `%s'.",
> > +                            symbol->name);
> > +        expr_destroy(expr);
> > +        return NULL;
> >      }
> >
> > -    struct annotation_nesting an;
> > -    an.symbol = symbol;
> > -    ovs_list_push_back(nesting, &an.node);
> > +    sset_add(nesting, symbol->name);
>
> We can actually skip the sset_find..() above because sset_add() returns
> NULL if the name already existed.
>
> >
> >      struct expr *prereqs = NULL;
> >      if (append_prereqs && symbol->prereqs) {
> >          prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting,
> errorp);
> >          if (!prereqs) {
> > -            goto error;
> > +            goto out;
> >          }
> >      }
> >
> > @@ -2001,7 +1989,7 @@ expr_annotate_cmp(struct expr *expr, const struct
> shash *symtab,
> >          predicate = parse_and_annotate(symbol->predicate, symtab,
> >                                         nesting, errorp);
> >          if (!predicate) {
> > -            goto error;
> > +            goto out;
> >          }
> >
> >          bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
> > @@ -2015,20 +2003,22 @@ expr_annotate_cmp(struct expr *expr, const
> struct shash *symtab,
> >      }
> >
> >      *errorp = NULL;
> > -    ovs_list_remove(&an.node);
> > -    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> >
> > -error:
> > -    expr_destroy(expr);
> > -    expr_destroy(prereqs);
> > -    ovs_list_remove(&an.node);
> > -    return NULL;
> > +out:
> > +    sset_find_and_delete(nesting, symbol->name);
>
> To avoid the lookup and to be more efficient I think we could just store
> the symbol sset_node when we insert it and use pass it here to
> sset_delete() instead.
>
> Thanks,
> Dumitru
>
> > +    if (*errorp) {
> > +        expr_destroy(expr);
> > +        expr_destroy(prereqs);
> > +        return NULL;
> > +    }
> > +
> > +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> >  }
> >
> >  /* Append (logical AND) prerequisites for given symbol to the
> expression. */
> >  static struct expr *
> >  expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
> > -                    const struct shash *symtab, struct ovs_list
> *nesting,
> > +                    const struct shash *symtab, struct sset *nesting,
> >                      char **errorp)
> >  {
> >      struct expr *prereqs = NULL;
> > @@ -2053,7 +2043,7 @@ static const struct expr_symbol
> *expr_get_unique_symbol(
> >   * have arranged to deal with them). */
> >  static struct expr *
> >  expr_annotate__(struct expr *expr, const struct shash *symtab,
> > -                bool append_prereqs, struct ovs_list *nesting, char
> **errorp)
> > +                bool append_prereqs, struct sset *nesting, char
> **errorp)
> >  {
> >      switch (expr->type) {
> >      case EXPR_T_CMP:
> > @@ -2112,7 +2102,7 @@ expr_annotate__(struct expr *expr, const struct
> shash *symtab,
> >   * Uses 'nesting' to ensure that a given symbol is not recursively
> expanded. */
> >  static struct expr *
> >  expr_annotate_(struct expr *expr, const struct shash *symtab,
> > -               struct ovs_list *nesting, char **errorp)
> > +               struct sset *nesting, char **errorp)
> >  {
> >      return expr_annotate__(expr, symtab, true, nesting, errorp);
> >  }
> > @@ -2138,8 +2128,11 @@ expr_annotate_(struct expr *expr, const struct
> shash *symtab,
> >  struct expr *
> >  expr_annotate(struct expr *expr, const struct shash *symtab, char
> **errorp)
> >  {
> > -    struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> > -    return expr_annotate_(expr, symtab, &nesting, errorp);
> > +    struct sset nesting = SSET_INITIALIZER(&nesting);
> > +    struct expr *result = expr_annotate_(expr, symtab, &nesting,
> errorp);
> > +    sset_destroy(&nesting);
> > +
> > +    return result;
> >  }
> >
> >  static struct expr *
>
>