From nobody Mon Feb 9 13:58:51 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1665566067; cv=none; d=zohomail.com; s=zohoarc; b=jX3ddVC2mYu7p5ovI2GtLJ9AEdzHlTgGFvvcRJoX4gV9RHZHhmcIyZHRLgCivWMguawcclj2QsFmx82lFH65GHNsPmebTqox7AY8LOObwX3Gr0j9Goyuwzrt8IbIqEw0JelBcgI7g8EzHQ93V4TtM6hCgsk2Tqij2nInbMO5h9Q= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1665566067; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Sender:Subject:To; bh=EVxpKTNee62t5SKdMs1YcNhNJkpVpWYDm3dWA8552i8=; b=hAX2RcWXL4JAZqw5aw6fTVqHsWHfI91znRHP41278sA8bq/p7sEh4YZQVhos3aieHTt+gRcG49jGgjV6mkmXu25Jeh7jsNNr6aKWIRtJsgNaT3Aa56h3fIfZ7xQtLlIx+iT6hACy0VSCCoYHOw3vHlbBzF9c3Q2cXMlDGF9E2kc= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1665566067120147.58678520818842; Wed, 12 Oct 2022 02:14:27 -0700 (PDT) Received: from localhost ([::1]:60464 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oiXol-0001y2-Dk for importer@patchew.org; Wed, 12 Oct 2022 05:14:23 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:34300) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiXjb-0007vh-Ea for qemu-devel@nongnu.org; Wed, 12 Oct 2022 05:09:03 -0400 Received: from us-smtp-delivery-124.mimecast.com ([170.10.129.124]:44315) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oiXjZ-0001BH-6h for qemu-devel@nongnu.org; Wed, 12 Oct 2022 05:09:02 -0400 Received: from mail-ej1-f69.google.com (mail-ej1-f69.google.com [209.85.218.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-373-xUHcPwPUM4uPJA-y1IriEg-1; Wed, 12 Oct 2022 05:08:53 -0400 Received: by mail-ej1-f69.google.com with SMTP id nb9-20020a1709071c8900b0078d858f15c1so4909235ejc.1 for ; Wed, 12 Oct 2022 02:08:52 -0700 (PDT) Received: from avogadro.local ([2001:b07:6468:f312:2f4b:62da:3159:e077]) by smtp.gmail.com with ESMTPSA id g16-20020a50d0d0000000b00458a243df3esm10827260edf.65.2022.10.12.02.08.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 12 Oct 2022 02:08:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1665565740; 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=EVxpKTNee62t5SKdMs1YcNhNJkpVpWYDm3dWA8552i8=; b=HZxcitbCyP5/McSi+j3gcm/b4QC8QDwcGWgNZTBSTksk6/QbEbJ8riTJ0yzzQZSr9ltMIT ESy22IrqLK9oVvVxO3mIaIV2yLS1Y1eHbtLoaO9bJtOkNCr7tTsPvIBSix9XjCU7CevENn x5iEErcFyG5vPO1lqFT1lmi1Jqh/rG4= X-MC-Unique: xUHcPwPUM4uPJA-y1IriEg-1 X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=EVxpKTNee62t5SKdMs1YcNhNJkpVpWYDm3dWA8552i8=; b=vOj0dQIrdqENLzxQDQcbBuwv/qcN2NDUrU3kUhf5xfEhAr5RKCF1yAadRpbl2+8mvE /FvrcSqL1BqxJkuTSBVM0VJpvb8F4gDJXgfmBWd/f+k9onkCyBOjomjIHQ5NHXgNe1gB tIt0YrU7bpvKw0e2aGFH3Bz4F1mQiu9N2YH3kyK7h1fZ69+TRJGPXae8IbXPEaiwz1Qe T2zsIbSBOuoDgOriRcti2aFWix3Yr2KyMtsFKOJaLoJMaEWhq7jgoKqY8X1bZgZ4eOtc 1Otk687WKrmpVWYZO1aGEEgJ5hJVFjiImzzC6jwjfpH1vXBxhUptNWJUfes+I8oWw1XN ozpw== X-Gm-Message-State: ACrzQf3IdBvok2wfHOEQNhOFDEP4L3c3SGOacm8yENVl0UNzc3jreYCc KFLM8HQICcmnrXx4AbUmc4JhTPY85n9TjDxFk96JbJLZRqrOtpYa/9PYU43xDnzcUGLUqEkZb3/ EqRLnLRVsaal6cGGWL7gCOD/y2yUg047rKSqmob33qK67O2IJdQd/Z2iHEEBcqs4H7pY= X-Received: by 2002:a05:6402:5510:b0:459:5ea:9bc0 with SMTP id fi16-20020a056402551000b0045905ea9bc0mr25617807edb.152.1665565731562; Wed, 12 Oct 2022 02:08:51 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7EpjGjXahO9uwBu9cA4wa1qanD8XgNxvIc8s7TlFZok8R47j/Iqf+vbLm18bxG/DDGIW1Czw== X-Received: by 2002:a05:6402:5510:b0:459:5ea:9bc0 with SMTP id fi16-20020a056402551000b0045905ea9bc0mr25617782edb.152.1665565731248; Wed, 12 Oct 2022 02:08:51 -0700 (PDT) From: Paolo Bonzini To: qemu-devel@nongnu.org Cc: Richard Henderson Subject: [PATCH] qgraph: implement stack as a linked list Date: Wed, 12 Oct 2022 11:08:48 +0200 Message-Id: <20221012090848.359764-1-pbonzini@redhat.com> X-Mailer: git-send-email 2.37.3 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=170.10.129.124; envelope-from=pbonzini@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: pass (identity @redhat.com) X-ZM-MESSAGEID: 1665566067813100001 Content-Type: text/plain; charset="utf-8" The stack used to visit the graph is implemented as a fixed-size array, and the array is sized according to the maximum anticipated length of a path on the graph. However, the worst case for a depth-first search is to push all nodes on the graph, and in fact stack overflows have been observed in the past depending on the ordering of the constructors. To fix the problem once and for all, use a QSLIST instead of the array, allocating QOSStackElements from the heap. Reviewed-by: Richard Henderson Signed-off-by: Paolo Bonzini --- tests/qtest/libqos/qgraph.c | 35 +++++++++++------------------------ 1 file changed, 11 insertions(+), 24 deletions(-) diff --git a/tests/qtest/libqos/qgraph.c b/tests/qtest/libqos/qgraph.c index 0a2dddfafa..ff9d389f12 100644 --- a/tests/qtest/libqos/qgraph.c +++ b/tests/qtest/libqos/qgraph.c @@ -52,6 +52,7 @@ struct QOSStackElement { QOSStackElement *parent; QOSGraphEdge *parent_edge; int length; + QSLIST_ENTRY(QOSStackElement) next; }; =20 /* Each enty in these hash table will consist of pair.= */ @@ -59,8 +60,7 @@ static GHashTable *edge_table; static GHashTable *node_table; =20 /* stack used by the DFS algorithm to store the path from machine to test = */ -static QOSStackElement qos_node_stack[QOS_PATH_MAX_ELEMENT_SIZE]; -static int qos_node_tos; +static QSLIST_HEAD(, QOSStackElement) qos_node_stack; =20 /** * add_edge(): creates an edge of type @type @@ -325,40 +325,27 @@ static void qos_print_cb(QOSGraphNode *path, int leng= th) static void qos_push(QOSGraphNode *el, QOSStackElement *parent, QOSGraphEdge *e) { + QOSStackElement *elem =3D g_new(QOSStackElement, 1); int len =3D 0; /* root is not counted */ - if (qos_node_tos =3D=3D QOS_PATH_MAX_ELEMENT_SIZE) { - g_printerr("QOSStack: full stack, cannot push"); - abort(); - } - if (parent) { len =3D parent->length + 1; } - qos_node_stack[qos_node_tos++] =3D (QOSStackElement) { + *elem =3D (QOSStackElement) { .node =3D el, .parent =3D parent, .parent_edge =3D e, .length =3D len, }; -} - -/* qos_tos(): returns the top of stack, without popping */ -static QOSStackElement *qos_tos(void) -{ - return &qos_node_stack[qos_node_tos - 1]; + QSLIST_INSERT_HEAD(qos_node_stack, elem, next); } =20 /* qos_pop(): pops an element from the tos, setting it unvisited*/ -static QOSStackElement *qos_pop(void) +static void qos_pop(void) { - if (qos_node_tos =3D=3D 0) { - g_printerr("QOSStack: empty stack, cannot pop"); - abort(); - } - QOSStackElement *e =3D qos_tos(); + QOSStackElement *e =3D QSLIST_FIRST(qos_node_stack); e->node->visited =3D false; - qos_node_tos--; - return e; + QSLIST_REMOVE_HEAD(qos_node_stack, next); + g_free(e); } =20 /** @@ -400,8 +387,8 @@ static void qos_traverse_graph(QOSGraphNode *root, QOST= estCallback callback) =20 qos_push(root, NULL, NULL); =20 - while (qos_node_tos > 0) { - s_el =3D qos_tos(); + while (!QSLIST_EMPTY(qos_node_stack)) { + s_el =3D QSLIST_HEAD(qos_node_stack); v =3D s_el->node; if (v->visited) { qos_pop(); --=20 2.37.3