public inbox for glibc-bugs@sourceware.org help / color / mirror / Atom feed
From: "dhatch at ilm dot com" <sourceware-bugzilla@sourceware.org> To: glibc-bugs@sourceware.org Subject: [Bug dynamic-link/15329] New: _dl_sort_fini and _dl_sort_init don't keep SCCs contiguous Date: Tue, 02 Apr 2013 09:09:00 -0000 [thread overview] Message-ID: <bug-15329-131@http.sourceware.org/bugzilla/> (raw) http://sourceware.org/bugzilla/show_bug.cgi?id=15329 Bug #: 15329 Summary: _dl_sort_fini and _dl_sort_init don't keep SCCs contiguous Product: glibc Version: unspecified Status: NEW Severity: minor Priority: P2 Component: dynamic-link AssignedTo: unassigned@sourceware.org ReportedBy: dhatch@ilm.com Classification: Unclassified Found this by surprise while unit/stress testing _dl_sort_fini and the corresponding init sorting code (specifically, testing the init code on all graphs of up to 4 nodes). Previously, it wasn't clear to me whether the existing topsorting algorithm keeps SCCs (strongly connected components) contiguous-- it seemed to, for the most part, but I didn't have a proof that it did, nor a counterexample showing it didn't. Here's a small counterexample showing it doesn't. The static dependency graph has 4 nodes 0,1,2,3, and 5 edges: 0 depends on 1,2,3 1 depends on 0 2 doesn't depend on anything 3 depends on 0 In this case the dag of SCCs has two nodes and one edge: {0,1,3} depends on {2}. So it would be good if the sort would put 2 last. But it doesn't-- it produces [0 3 2 1]. To put it another way, 1 depends (transitively) on 2, but 2 doesn't depend (transitively) on 1, so it's desireable for 1 to come before 2 in the output order. The following probably isn't very interesting, but here are the steps the sorting code takes: initial order: [0 1 2 3] move 0 after 3 -> [1 2 3 0], 0 has been seen once move 1 after 0 -> [2 3 0 1], 1 has been seen once move 2 after 0 -> [3 0 2 1], 2 has been seen once move 3 after 0 -> [0 3 2 1], 3 has been seen once move 0 after 1 -> [3 2 1 0], 0 has been seen twice move 3 after 0 -> [2 1 0 3], 3 has been seen twice move 2 after 0 -> [1 0 2 3], 2 has been seen twice move 1 after 0 -> [0 1 2 3], 1 has been seen twice (original order!) move 0 after 3 -> [1 2 3 0], 0 has been seen 3 times move 1 after 0 -> [2 3 0 1], 1 has been seen 3 times move 2 after 0 -> [3 0 2 1], 2 has been seen 3 times move 3 after 0 -> [0 3 2 1], 3 has been seen 3 times move 0 after 1 -> [3 2 1 0], 0 has been seen 4 times move 3 after 0 -> [2 1 0 3], 3 has been seen 4 times move 2 after 0 -> [1 0 2 3], 2 has been seen 4 times move 1 after 0 -> [0 1 2 3], 1 has been seen 4 times (original order!) move 0 after 3 -> [1 2 3 0], 0 has been seen 5 times move 1 after 0 -> [2 3 0 1], 1 has been seen 5 times move 2 after 0 -> [3 0 2 1], 2 has been seen 5 times move 3 after 0 -> [0 3 2 1], 3 has been seen 5 times Now object 3 has been seen 5 times which exceeds its limit, so 0 gets locked in place, all seen counts get cleared, and we go on to sort the last three items, which have no order conflicts within themselves and so the output order is [0 3 2 1]. This is something to keep in mind when overhauling the sorting code, which already needs to be done for bug 15310 (sorting is O(n^3)) and bug 15311 (static deps can be violated by dynamic ones). It should be possible to make a fast, robust, easier-to-analyze implementation that keeps SCCs contiguous. -- Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug.
next reply other threads:[~2013-04-02 9:09 UTC|newest] Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top 2013-04-02 9:09 dhatch at ilm dot com [this message] 2013-04-02 9:12 ` [Bug dynamic-link/15329] " dhatch at ilm dot com 2014-06-13 18:33 ` fweimer at redhat dot com 2021-10-27 14:59 ` adhemerval.zanella at linaro dot org 2021-10-27 14:59 ` adhemerval.zanella at linaro dot org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-15329-131@http.sourceware.org/bugzilla/ \ --to=sourceware-bugzilla@sourceware.org \ --cc=glibc-bugs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).