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]

Re: [Patch] Fix cycle detection and initialization order in dynamicloader


On 06/20/2012 05:24 PM, Carlos O'Donell wrote:

I apologize that my review took so long.
No worries.

(b) I have verified that the sort works in the
     event of cycles.
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.


(c) I verified that I could find no other places where this incorrect sort algorithm was used.
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.


(d) Pointed out some "bureaucracy" bugs.
Thanks. Clearly I'm still getting used to some differences between glibc & gcc submission guidelines.


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.
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.


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).
Realistically I don't think we can completely avoid the cycle problem.


OK with the changes below:
Thanks. Changes made and patch installed.

jeff


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]