From patchwork Mon Nov 28 14:25:06 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ales Musil X-Patchwork-Id: 1709765 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=P+lYWEXN; dkim-atps=neutral Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4NLSRd3KTNz23nB for ; Tue, 29 Nov 2022 01:25:17 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 5710C40352; Mon, 28 Nov 2022 14:25:15 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 5710C40352 Authentication-Results: smtp4.osuosl.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=P+lYWEXN X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id O25D-bYWGfuU; Mon, 28 Nov 2022 14:25:14 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp4.osuosl.org (Postfix) with ESMTPS id E11DE40211; Mon, 28 Nov 2022 14:25:12 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org E11DE40211 Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9595EC0033; Mon, 28 Nov 2022 14:25:12 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id A6908C002D for ; Mon, 28 Nov 2022 14:25:11 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 6E3CC605DB for ; Mon, 28 Nov 2022 14:25:11 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6E3CC605DB Authentication-Results: smtp3.osuosl.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=P+lYWEXN X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZShPvlWWwqVe for ; Mon, 28 Nov 2022 14:25:10 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 7E1A460593 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by smtp3.osuosl.org (Postfix) with ESMTPS id 7E1A460593 for ; Mon, 28 Nov 2022 14:25:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1669645509; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=obKZLnpbNLBJX3Ge0z4FiMGjb6KnKZ7eg1A+JdNb8n8=; b=P+lYWEXNxmBGSANt7PDiJhU/qO6zHFoeKXzz0FZaingbl0Irnp0RWLxW9GU3SU2/VnKxDs KDIwch6Rwiwtt2ZyhKlIZ+4Hmx0Quu+GARgbZi+jldpcbP9BeJ5Tpbk3grsObBxkOe0TR7 dyCyvEWtqyBCODf8D+ZaFcaqXhLbFSs= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-453-Yf4MmUjGOK6aRInIJVXNmw-1; Mon, 28 Nov 2022 09:25:08 -0500 X-MC-Unique: Yf4MmUjGOK6aRInIJVXNmw-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.rdu2.redhat.com [10.11.54.7]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id D4422833AEE for ; Mon, 28 Nov 2022 14:25:07 +0000 (UTC) Received: from amusil.redhat.com (ovpn-193-48.brq.redhat.com [10.40.193.48]) by smtp.corp.redhat.com (Postfix) with ESMTP id 0A49D1415122; Mon, 28 Nov 2022 14:25:06 +0000 (UTC) From: Ales Musil To: dev@openvswitch.org Date: Mon, 28 Nov 2022 15:25:06 +0100 Message-Id: <20221128142506.300009-1-amusil@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.7 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Subject: [ovs-dev] [RFC PATCH ovn] expr: Use sset for nested expr instead of list X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" 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 --- 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)) { + *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); 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); + 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 *