Bug 269150 - bsdconfig: O(n^2) performance in f_device_get_all
Summary: bsdconfig: O(n^2) performance in f_device_get_all
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Some People
Assignee: freebsd-bugs (Nobody)
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2023-01-25 16:47 UTC by Alan Somers
Modified: 2023-02-05 14:36 UTC (History)
3 users (show)

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Alan Somers freebsd_committer freebsd_triage 2023-01-25 16:47:07 UTC 
bsdconfig can take a very long time on systems with a large number of disks.  I've seen it take 30 minutes at "Probing devices".  top shows that the slowdown 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.