The order of initialization and termination functions called when loading or exiting via the loader is being sorted incorrectly in particular cases (described below) according to the TIS ELF 1.2 standard: "Before the initialization code for any object A is called, the initialization code for any other objects that object A depends on are called." The partial sorting algorithm used in elf/dl-deps.c and elf/dl-fini.c is incorrect when the sorting section is reached with a particular (order dependent) dependency hierarchy. I have not been able to boil down to a canonical example, but have anonymized it, and will attach following submission. Additionally, the partial sort is not input-order independent, as multiple runs of the existing sort on the failure set, repeating if dependencies are found out of order, is convergent. The partial sort is not sufficient to perform the dependency analysis on all inputs given the requirements of the standards doc, and I have drafted a patch which uses the tsort implementation from coreutils. This new sorting has been tested on all cases where the current ld.so initializes things in the incorrect order, and on a number of other programs. The inability to reliably initialize objects in the correct order is a major issue for me, particularly when working with C++ and globally initialized variables dependent on linked objects' initializations.
Created attachment 4851 [details] Dependency hierarchy which breaks existing deps sorting (apologies for the complexity) This is the list of l_initfini in dl-deps.c when the initialization order is determined which produces incorrect output. I have left in the leader dependency for each library which points back to itself.
Created attachment 4852 [details] topological sort implementation for dependency resolution I've used the implementation of tsort from coreutils here almost verbatim. One point of contention might be the (long) cast for comparison in dl-tsort.c - if there's a better portable pointer equiv integer type that will give a negative value for subtraction (since pointers won't), that will be fine. Obviously this introduces some recursion into ld.so, and I saw in a comment that that is not desirable. This implementation works to provide correct init and fini ordering for everything I've thrown at it.
You'll have to provide a complete small, self-contained test case.
Created attachment 4855 [details] Revised fix including test case (case fails independently in the previous implementation of ld.so) Test case added to elf/ as tst-initorder, with a comparison test to make sure that the initialization occurs in order. This is a failure set for the previous implementation. I've also done a couple of tweaks to the existing patch, returning instead of trying to sort if we run out of memory during fini. Technically the previous implementation could be used if memory allocation fails, since it does not use any new allocations.
(In reply to comment #2) > there's a better portable pointer equiv integer type int a = (l > p->l) - (l < p->l);
(In reply to comment #5) > int a = (l > p->l) - (l < p->l); Fine by me. Do you want an update of the diff for this?
I check in your test and a patch I wrote.
Created attachment 5872 [details] Example of post-patch initialization order failure. Your patch is not sufficient. You corrected the given case, but opened up another failure case. I have attached a reproducer for the failure case. I recommend again that my previous patch be accepted as it was, since it worked for both of these cases. The failure condition now, which did not break under the previous implementation, is described as follows: main => deps1, deps4, deps3 deps1 => deps2 deps2 => deps3 deps3 => deps4
THis has long since been handled.