This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
No worries.
I apologize that my review took so long.
Thanks. I didn't test this explicitly, but it was pretty easy to reason that the seen[someobj] would eventually hit the high limit and force termination of the loop. As you note later, that could be rather expensive for that undefined case.(b) I have verified that the sort works in the event of cycles.
Thanks for the double-check. I did this search as well and was even lucky enough to catch the instance Uli added about the same time I was working on the patch.
(c) I verified that I could find no other places where this incorrect sort algorithm was used.
Thanks. Clearly I'm still getting used to some differences between glibc & gcc submission guidelines.
(d) Pointed out some "bureaucracy" bugs.
Yup. Presumably it doesn't use recursion due to environmental restrictions at this point in process startup. I pondered rewriting it to use recursion with forced inlining to make the code clearer.
It would appear that the original code tries to implement a non-recursive depth-first topological sort with cycle detection, but gets it wrong in several respects.
Realistically I don't think we can completely avoid the cycle problem.There are performance implications for the undefined case of cycles, and I'll mention them here, but it really doesn't matter since good performance would only be achieved by rewriting this code to use a sensibly studied and proven algorithm (or avoid the undefined case of libraries with circular dependencies).
Thanks. Changes made and patch installed.
OK with the changes below:
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |