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 <[email protected]>
> ---
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 *
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
