From nobody Wed Jan 25 16:47:07 2023 X-Original-To: bugs@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4P28rW3464z3bt5K for ; Wed, 25 Jan 2023 16:47:07 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4P28rW1cZsz3Cd6 for ; Wed, 25 Jan 2023 16:47:07 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1674665227; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=NvWFQpkqXi/E8uhrU1FUmsrIbQO+UDPJs51tNiUHaL0=; b=w2umfMSVC0weQXwZJXe8V7oB/dlf3Kk98bvNf8sKSQd2LMgeJQlMF4BBN5F3hSE7FQWteT C3dLj7Z7MLc5RfOdqeHq5l1vzHVNz19y0RFxZKwXHxr1kvdj/CAc9GPE7DRnnVJJFFjYWX 6bvopgYrttsNMt6EKVMmTmOpbyH3QkImS7LunT7JZgaqRiaJVZFDdtRUFfXJuybhoP0lln gn/rJEtBmi+zt6o8TCByycBEaw1mbPo0RWdp3Oq0sgyWMdTDo1o0I9q8nZL4iE3xIqSpmg Po+j0WBMKdTkpTaiktivq4O084wIntL82T/cEKdQWT++ngF+NoTftTTf6oNcfA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1674665227; a=rsa-sha256; cv=none; b=osS2vqglf+tC++i1FSirHUoM+/qrKm6GPF8pNsUg1CVN6AroHdBxep8twh2TP4Wc6ITRh1 Il0fe2NyUT8Yy7680mP6v0Q/D23wJ1LayCWLBjuxOpZNYJkkkPD9N/+Br97mBU9BeRxY7m sVm1QrpnQSoZYRLWCjrGJfQY3mtQy349bOI/t/erXpIkFs5f8C+YyD5NcKN1n1VNqYFlnr iednYyxKZH6aosgCbGjVR/byexW4vTp6rRF3MrnyEaJoooc/20iOE58z9Y1qc0kMWABFOi z5PXOBPXLoPDZbU6Ja/OtBsfUi11WIVMNF8OTVKI81eqClWK7gICTu65CRJGFg== Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2610:1c1:1:606c::50:1d]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4P28rW0ZG1zwNJ for ; Wed, 25 Jan 2023 16:47:07 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org ([127.0.1.5]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id 30PGl7fD038254 for ; Wed, 25 Jan 2023 16:47:07 GMT (envelope-from bugzilla-noreply@freebsd.org) Received: (from www@localhost) by kenobi.freebsd.org (8.15.2/8.15.2/Submit) id 30PGl70f038253 for bugs@FreeBSD.org; Wed, 25 Jan 2023 16:47:07 GMT (envelope-from bugzilla-noreply@freebsd.org) X-Authentication-Warning: kenobi.freebsd.org: www set sender to bugzilla-noreply@freebsd.org using -f From: bugzilla-noreply@freebsd.org To: bugs@FreeBSD.org Subject: [Bug 269150] bsdconfig: O(n^2) performance in f_device_get_all Date: Wed, 25 Jan 2023 16:47:07 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: bin X-Bugzilla-Version: CURRENT X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Some People X-Bugzilla-Who: asomers@FreeBSD.org X-Bugzilla-Status: New X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: bugs@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated List-Id: Bug reports List-Archive: https://lists.freebsd.org/archives/freebsd-bugs List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-freebsd-bugs@freebsd.org MIME-Version: 1.0 X-ThisMailContainsUnwantedMimeParts: N https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D269150 Bug ID: 269150 Summary: bsdconfig: O(n^2) performance in f_device_get_all Product: Base System Version: CURRENT Hardware: Any OS: Any Status: New Severity: Affects Some People Priority: --- Component: bin Assignee: bugs@FreeBSD.org Reporter: asomers@FreeBSD.org bsdconfig can take a very long time on systems with a large number of disks= .=20 I've seen it take 30 minutes at "Probing devices". top shows that the slow= down is entirely due to CPU usage of sh, not subprocesses. Inspection shows that the `f_device_get_all` function calls `f_device_probe_geom` for every geom, which then calls `f_geom_find`, which again loops over every geom. It's a classic O(n^2) problem. We need to refactor that code to remove the extra loops. --=20 You are receiving this mail because: You are the assignee for the bug.=