Description of problem: Constructing grub.cfg at the end of an install takes a long time. The OS probe of my 40-partition box (4 commodity SATA drives) took more than half a minute. This is too long by a factor of 6 or 7. Version-Release number of selected component (if applicable): grub2-2.00-12.fc18.x86_64 How reproducible: always Steps to Reproduce: 1. Install Fedora on a box with many [other] root partitions. 2. 3. Actual results: Constructing boot/grub2/grub.cfg takes a major fraction of one second per root partition. If you listen, you can recognize the pattern of seeks. Expected results: Process many partitions per second. Additional info: At least: parallelize by spindle. Perhaps: batch processing of all partitions on the same drive.
This seems fast compared to last I remember installing *buntu on a system with upwards of 12 distro / partitions and multiple kernels on most or all of them. IMO there needs to be a way to disable OS Prober right up front, possibly from installation kernel cmdline if nothing else, but preferably an option to choose between making it boot only Fedora as a slave from another bootloader (e.g. chainloaded), or a global/master (MBR installation).
See also http://www.gnu.org/software/grub/manual/grub.html#Multi_002dboot-manual-config
I wonder if os-prober is CPU bound. AFAIK, it doesn't do much "processing" so I'm not sure if parallel processing of partitions will really improve its performance. However, I'll try to investigate as soon as possible, but it probably needs a significant change in the behaviour of os-prober and should be integrated upstream. Anyway, any patches are reallt welcome since it is certainly not in top of my TODO list specially if it needs significant changes (which brings a number of risks too). Also, I don't have a system with so many installations so I'd probably unable to test and benchmark possible solutions.
[os-prober-1.55-1.fc18.x86_64] Reducing total latency (wall-clock time) is possible precisely because os-prober is _not_ CPU bound. Parallelizing per spindle should achieve a factor that is near the number of spindles, because I/O to one spindle is nearly independent of I/O to any other spindle. Nevertheless, there are some CPU time wasters: # time strace -o strace.out -f -e trace=file os-prober >os-prober.out 2>os-prober-stderr.out real 0m27.761s user 0m3.556s sys 0m12.392s $ wc strace.out os-prober.out os-prober-stderr.out 80744 592291 5812321 strace.out 33 153 1868 os-prober.out 1 4 25 os-prober-stderr.out $ grep '<unfinished' strace.out | wc 1368 7167 83059 So there were (80744 - 1368) = 79376 filename lookups for 33 output lines, or 2405 lookups per eligible filesystem. Ouch! The head of the histogram of filenames: $ sed -n -e '/"/s/[^"]*"\([^"]*\).*/\1/p' <strace.out | sort | uniq -c | sort -rn | sed 26q 6692 /usr/bin/logger 2992 /usr/bin/basename 2521 /etc/ld.so.preload # 2521 processes for 33 partitions 2505 /lib64/libc.so.6 2505 /etc/ld.so.cache 2461 . 2413 /usr/lib/locale/locale-archive 1869 /usr/bin/grep 1806 /usr/sbin/blockdev 1489 /proc/mounts 1328 /dev/sdd 1324 /dev/sdc 1324 /dev/sdb 1310 /dev/sda 1248 /usr/sbin/dmraid 1118 /usr/sbin/blkid 1113 /sys/fs/selinux 1001 /usr/bin/sed 934 /dev/null 828 /etc/localtime # once ought to be enough 819 /lib64/libdl.so.2 810 /usr/lib64/gconv/gconv-modules.cache 618 /usr/bin/mount 605 /lib64/libpcre.so.1 561 /usr/bin/readlink 543 /usr/share/locale/locale.alias The head of the histogram of subprocesses: $ sed -n -e '/execve(/s/[^"]*"\([^"]*\).*/\1/p' <strace.out | sort | uniq -c | sort -rn | sed 20q 842 /usr/bin/logger 272 /usr/bin/basename 234 /usr/bin/grep 126 /usr/sbin/blockdev 91 /usr/bin/sed 68 /usr/bin/mount 51 /usr/bin/readlink 49 /usr/bin/ls 48 /usr/sbin/dmraid 43 /usr/sbin/blkid 43 /usr/libexec/os-probes/50mounted-tests 42 /usr/bin/rmdir 42 /usr/bin/mkdir 40 /usr/libexec/os-probes/mounted/20microsoft 40 /usr/libexec/os-probes/mounted/20macosx 40 /usr/libexec/os-probes/mounted/10qnx 40 /usr/libexec/os-probes/mounted/10freedos 40 /usr/bin/umount 39 /usr/libexec/os-probes/mounted/90linux-distro 39 /usr/libexec/os-probes/mounted/83haiku Obviously /usr/bin/logger should be a single parallel process to which other processes re-direct output (implicitly via inherited open file descriptor [such as stderr], or by a shell variable which expands to the number of a file descriptor, or perhaps to the name of a fifo.) 'basename' never should be invoked so often. Either use the string processing of bash, or use the string processing similar to the source of libtool. Most appearances of 'grep' and 'sed' also should be replaced by shell string handling. os-prober must state explicitly its assumptions about features in the shell. 'bash' really is a _lot_ better, but even for shells that are more primitive different coding can reduce the number of processes. Then many uses of "for <var> in $(...)" should be replaced by a pipeline: $(...) | while read <var> because a pipeline enables parallelism. Using 'for' means that all of the "$(...)" must complete before any further work can begin.
The file os-prober already has [grep '##' os-prober]: local device="/dev/${parent##*/}" name="$(echo "${part##*/}" | sed 's,[!.],/,g')" and "${var##*/}" is the 'bash' string-processing idiom for "basename var". So all the execve() of 'basename' should disappear. The file os-prober also has: for partition in $(partitions); do which should become: partitions | while read partition; do to enable parallelism by pipeline. The function 'partitions' has: for part in /sys/block/*/*[0-9]; do ... done which should become: for drive in /sys/block/*; do (for part in $drive/*[0-9]; do ... done ) & done to enable parallelism by spindle.
Thanks for your investigation. About the shell, I'm not sure which shell os-prober assumes (specially since it is used in debian installer) but you should be able to use the features it already uses. And, could you please see how much the changes you mentioned affect os-prober's speed? (As I said, I don't have a good test bed).
Created attachment 652201 [details] patch against os-prober-1.56 Here's a patch. The elapsed wall-clock times in seconds are: os-prober linux-boot-prober os-prober-1.56 12.9 3.6 patched 5.9 0.4 where os-prober analyzes all 43 partitions, but linux-boot-prober only 1. So that is a factor of 9X for linux-boot-prober, but only 2.2X for os-prober. During os-prober, "vmstat 2" shows CPU time about: 10% user 9% system 20% idle 60% wait and indeed the hardware LED for "disk active" is ON almost all the time. I do not understand why the idle and wait times are not close to zero. The internal documentation is lacking. I had to deduce the strategies. Depending on usage, linux-boot-prober could be added to the os-prober pipeline. (I changed linux-boot-prober to read stdin instead of using $1.) The overlap should be enough to hide the entire time for linux-boot-prober. (That would give 7X faster for the whole task as seen by user of anaconda.) Also, there is no comment about the reason for using "blockdev --setro" when "mount -ro" is used already. My box has 3GHz dual CPU, fedora-18-Beta-RC1, and these disks: 4 7200rpm SATA II drives; 2 GPT, 2 MSDOS 32 linux root partitions 5 data (non-root) partitions 3 swap partitions (one per drive except Windows) 2 not-formatted partitions 1 Windows partition Overview of significant changes in the patch: 1. Factor out thouands of invocations of 'loggger' into a single process which reads stdin. 2. Change strategy from serial tests to a shell pipeline where success goes "out the side" while failure "falls through" to next stage in pipeline. 3. Avoid 'grep' and 'sed' in favor of shell string processing, "set --" under appropriate "IFS=", and 'eval'. 4. Avoid logging the whole contents of grub.cfg. Mine has 1955 lines, and anyway the patched logging would suffer rate-limiting by syslog. 5. Use the -a (AND) operator to '[' (test) instead of multiple tests with '&&'. Because of its use by debian-installer, os-prober wants 'dash' as shell, and not 'bash', This is unfortunate because bash has '=~' for string maching, "$(<" instead of "$(cat", and arrays. Dash can use "case "$param" in; pattern) ... ;; ... esac" for most simple uses of " [[ "$param" =~ pattern ]] ", but somehow I find 'case' cumbersome. So I use "_tmp="${param##pattern}"; if [ ${#_tmp} -ne ${#param} ]" (etc.) to detect a match by difference in length.
Thank you for the patch and benchmarks. I'll review & test the patch and push a new packet to rawhide and F18 testing.
The patch won't be considered by upstream for now, since it is a big patch. It is also a big patch to be maintained in Fedora packages. I'll try to break down the patch to a number of separate, single-purpose patches and apply them to packages and also send them separately upstream which will make it more likely to happen; but it'll be gradual.
Created attachment 688069 [details] further patch to parallelize by spindle Here is a further patch which actually parallelizes by spindle. On my 4-spindle system it reduces elapsed time by a further factor of 2.2 to 2.3, giving a total factor of about 5 against original os-prober-1.56. Elapsed time is down to 2.65 seconds for os-prober. The changes: When a pipe stage is a shell script then use "source" instead of execve, and in the child inherit common functions from parent process instead of re-reading them. Replace 'cat' by 'read' where possible. Parallelize by spindle. About the only remaining unimplemented major feature would be a settable limit on the parallelism. Each spindle uses about 15 simultaneous processes (one for each filter, plus a few), and by default linux has a limit of 1024 processes per UID. So in theory there may be trouble with more than 50 or 60 spindles, although the limit is somewhat soft because the pipeline for some spindles usually finishes before the last spindles start. The way to limit parallelism is to implement a queue of the PIDs of the per-spindle async pipelines (shell variable "$!" after each '&') and when the queue becomes long enough then 'wait' for the oldest one before starting work on a new spindle. The 'dash' shell lacks arrays, so probably use something like set -- $queue $newest; oldest="$1"; shift; queue="$@" to advance the queue.
Thanks for the additional patch. However, to make things going more smoothly, a number of single-purpose patches is much more appreciated than a single patch containing many different kinds of changes. This is actually what I've started to do, but since you are the one who did all this it should be easier for you. Therefore, while single patches are still welcome, it would be great if you can break them to multiple patches, specially for new patches you post. Thanks anyway
I consider that dogmatic reliance on fine-grained patches as a driver of development/maintenance is a significant contributing factor to the slowness of os-prober and the slowness of its maintenance. Looking at the source repository git://git.debian.org/d-i/os-prober.git shows another significant contributing factor: 361 straight-line commits (57+14 tagged releases) in about 8.7 years with no branching at all! That documents the straight-jacket which constricts os-prober to slowness. Radically diverging implementation could be accepted on a branch. Multiple developer/maintainers could look at it, adapt it, cross-pollinate using merges (both from and to the mainline), even refine it in parallel (more than one developer at a time) as much as desired. Hiding new implementations by banishing them from the official repository until they are fully polished is strangulation. In following comments to this bugzilla report I will attach individual patches from "git format-patch" for the latest batch. They may even be close-to-suitable for eventual use upstream, but that is not how my thinking works, so refinement may be required. [Complete history from my first batch also is available, but that is more likely to require work before being upstream-suitable. Please advise.]
Created attachment 689262 [details] 0001-source-and-inherit-when-pipe-stage-is-a-shell-script.patch
Created attachment 689263 [details] 0002-Avoid-cat-.-Shorten-filenames-after-cd.patch
Created attachment 689264 [details] 0003-Parallelize-by-spindle.patch
Created attachment 689265 [details] 0004-Use-one-set-of-counters-for-all-spindles.patch
Actually I asked for fine grained patches since this is what I can manage as a package maintainer. You'd agree that maintaining huge patches over upstream is not easy, specially if you are not written them yourself! Also, upstream is very slow in adopting even small patches, so I thought that small patches are likely to be considered faster. Unfortunately, upstream development is really slow. Most of the patches I've sent upstream are not merged yet (and they are very small!), and a few of them has been merged after a long time. Another problem with upstream is that it is tied to Debian releases, so they prevent most changes when a release is coming (you can see their comment on the upstream bug!). Apparently, there is nothing as 'trunk' or development HEAD. Sometimes I think that os-prober needs a fork! :P Anyway, thank you for the patches, I will try to review them as soon as I can. About the first patch: it is great to hear that you have the history. I don't know how your commits are organized, but I wonder if you can send a number of patches which have these minimum requirements: 1. does not break the code if later patches are not applied (does not depend on patches). 2. does not do many multiple-unrelated things. It might does a few ones though.
(In reply to comment #17) > I wonder if you can send a > number of patches which have these minimum requirements: 1. does not break > the code if later patches are not applied (does not depend on patches). Are you asking for patches such that the resulting tree is as "bushy" as possible when displayed by gitk? In other words, the old tip now has many direct successors, and the new patches have no other predecessors, so that the new patches are as independent as possible? I'll consider that only if you clone the "official" repository into a shared repository (say on fedorapeople or fedorahosted, etc.) and give me commit privileges. Why? I don't believe that the Debian maintainers will depart from their "linear only" style of commits. Therefore most of the work in creating bushy patches will be discarded, even if the patches are accepted in some linear order. Instead, I want the cloned repository to be the basis for forking os-prober. If needed, then we can import their changes at their glacial pace. If they change their mind, then they can clone our repository. I have had previous run-ins with Debian Installer over poor performance, such as many minutes for a portion of an install on NSLU2 that should take less than one minute. My detailed suggestions [not quite actual code] for changes in shell usage were dismissed, partly out of fear that future maintainers [even some current ones] would not grok shell usage of 'eval' etc. Debian Installer is stuck in a low-performance, low-quality corner; unfortunately the code "works".
I think I didn't clarify what I wanted (and also the parenthesis should have been removed). It is OK if patches depend on previous patches, I just wanted them to be independent of later patches. In other words, I prefer that a patch does not break the code (which is fixed in later patches). I really do not want to create a lot of work for you, just wanted more easily maintainable patches. BTW, if having a git repo makes life easier for you (and probably myself), I'll create one. I'll try to not fork, and use it primarily for managing Fedora patches. But, some day, it might lead to a fork...
Created attachment 692170 [details] 0001-Allow-relocation-of-tree-of-scripts.patch Here are three patches which get the biggest bang for a "small, simple" change: they factor out all invocations of 'logger' by using a pipe. This is enabled by a pipeline with more than one output stream, which is an important concept. The starting point for the patches is Debian release 1.57 of os-prober. The first patch allows relocating the tree of scripts, and the second patch allows executing "in place" on x86 without install. Combined, the first two patches allow A-B comparison of two implementations without requiring tedious uninstall+install or the use of a virtual machine. Finally, the third patch factors out 'logger'.
Created attachment 692171 [details] 0002-Allow-testing-without-install.patch
Created attachment 692172 [details] 0003-Factor-out-logger.patch
Thank you for the patches. I'm preparing a new build and I'll use these patches (I've already replaced use of basename in the latest build too). However, the first two patches are actually more appropriate to be applied in an official tarball rather than patches in a distro since they are actually 'development' rather than bug fixes (which is what generally applied as patches in a package) (In other words, they are not so urgent to be applied as a patch). Specially, the second patch really is useless in an rpm package (which is supposed to be used when installed). I really hope that they will merge upstream where they actually belong.
This update includes two patches related to this bug: https://admin.fedoraproject.org/updates/os-prober-1.57-2.fc18 https://admin.fedoraproject.org/updates/os-prober-1.57-2.fc17
This message is a reminder that Fedora 18 is nearing its end of life. Approximately 4 (four) weeks from now Fedora will stop maintaining and issuing updates for Fedora 18. It is Fedora's policy to close all bug reports from releases that are no longer maintained. At that time this bug will be closed as WONTFIX if it remains open with a Fedora 'version' of '18'. Package Maintainer: If you wish for this bug to remain open because you plan to fix it in a currently maintained version, simply change the 'version' to a later Fedora version prior to Fedora 18's end of life. Thank you for reporting this issue and we are sorry that we may not be able to fix it before Fedora 18 is end of life. If you would still like to see this bug fixed and are able to reproduce it against a later version of Fedora, you are encouraged change the 'version' to a later Fedora version prior to Fedora 18's end of life. Although we aim to fix as many bugs as possible during every release's lifetime, sometimes those efforts are overtaken by events. Often a more recent Fedora release includes newer upstream software that fixes bugs or makes them obsolete.
Fedora 18 changed to end-of-life (EOL) status on 2014-01-14. Fedora 18 is no longer maintained, which means that it will not receive any further security or bug fix updates. As a result we are closing this bug. If you can reproduce this bug against a currently maintained version of Fedora please feel free to reopen this bug against that version. If you are unable to reopen this bug, please file a new report against the current release. If you experience problems, please add a comment to this bug. Thank you for reporting this bug and we are sorry it could not be fixed.
This bug appears to have been reported against 'rawhide' during the Fedora 23 development cycle. Changing version to '23'. (As we did not run this process for some time, it could affect also pre-Fedora 23 development cycle bugs. We are very sorry. It will help us with cleanup during Fedora 23 End Of Life. Thank you.) More information and reason for this action is here: https://fedoraproject.org/wiki/BugZappers/HouseKeeping/Fedora23
John, could you rebase your patches over latest release of os-prober?
(In reply to Thierry Vignaud from comment #28) > John, could you rebase your patches over latest release of os-prober? Of the smaller, broken-out patches: 0001-Allow-relocation-of-tree-of-scripts.patch 0002-Allow-testing-without-install.patch are a convenience for developers, and have no effect on end users. 0003-Factor-out-logger.patch corresponds to Patch10: os-prober-factor-out-logger.patch in os-prober-1.70-1.fc24.src.rpm. Already this has been sent upstream. This is a "simple" "mechanical" patch with large speedup. 0002-Avoid-cat-.-Shorten-filenames-after-cd.patch This is a "small" "mechanical" patch with not much impact except code style. 0001-source-and-inherit-when-pipe-stage-is-a-shell-script.patch 0003-Parallelize-by-spindle.patch These are coupled "large" "significant idea" patches which affect many files and require care to verify (and extend to new source files that were created after the patches were uploaded.) So far my time is unavailable to do this work. 0004-Use-one-set-of-counters-for-all-spindles.patch This is a "medium" improvement which depends on the "significant idea" above. Bottom line: factor-out-logger has picked the low-hanging fruit already. Parallelize-by-spindle will take some work.
This message is a reminder that Fedora 23 is nearing its end of life. Approximately 4 (four) weeks from now Fedora will stop maintaining and issuing updates for Fedora 23. It is Fedora's policy to close all bug reports from releases that are no longer maintained. At that time this bug will be closed as EOL if it remains open with a Fedora 'version' of '23'. Package Maintainer: If you wish for this bug to remain open because you plan to fix it in a currently maintained version, simply change the 'version' to a later Fedora version. Thank you for reporting this issue and we are sorry that we were not able to fix it before Fedora 23 is end of life. If you would still like to see this bug fixed and are able to reproduce it against a later version of Fedora, you are encouraged change the 'version' to a later Fedora version prior this bug is closed as described in the policy above. Although we aim to fix as many bugs as possible during every release's lifetime, sometimes those efforts are overtaken by events. Often a more recent Fedora release includes newer upstream software that fixes bugs or makes them obsolete.
Fedora 23 changed to end-of-life (EOL) status on 2016-12-20. Fedora 23 is no longer maintained, which means that it will not receive any further security or bug fix updates. As a result we are closing this bug. If you can reproduce this bug against a currently maintained version of Fedora please feel free to reopen this bug against that version. If you are unable to reopen this bug, please file a new report against the current release. If you experience problems, please add a comment to this bug. Thank you for reporting this bug and we are sorry it could not be fixed.
AFAIK os-prober is still slow in some cases...
This bug appears to have been reported against 'rawhide' during the Fedora 26 development cycle. Changing version to '26'.
This message is a reminder that Fedora 26 is nearing its end of life. Approximately 4 (four) weeks from now Fedora will stop maintaining and issuing updates for Fedora 26. It is Fedora's policy to close all bug reports from releases that are no longer maintained. At that time this bug will be closed as EOL if it remains open with a Fedora 'version' of '26'. Package Maintainer: If you wish for this bug to remain open because you plan to fix it in a currently maintained version, simply change the 'version' to a later Fedora version. Thank you for reporting this issue and we are sorry that we were not able to fix it before Fedora 26 is end of life. If you would still like to see this bug fixed and are able to reproduce it against a later version of Fedora, you are encouraged change the 'version' to a later Fedora version prior this bug is closed as described in the policy above. Although we aim to fix as many bugs as possible during every release's lifetime, sometimes those efforts are overtaken by events. Often a more recent Fedora release includes newer upstream software that fixes bugs or makes them obsolete.
Fedora 26 changed to end-of-life (EOL) status on 2018-05-29. Fedora 26 is no longer maintained, which means that it will not receive any further security or bug fix updates. As a result we are closing this bug. If you can reproduce this bug against a currently maintained version of Fedora please feel free to reopen this bug against that version. If you are unable to reopen this bug, please file a new report against the current release. If you experience problems, please add a comment to this bug. Thank you for reporting this bug and we are sorry it could not be fixed.