[Bug libc/11724] New: ld.so - Initialization and Termination Functions incorrectly ordered

[Bug libc/11724] New: ld.so - Initialization and Termination Functions incorrectly ordered

[werkt0 at gmail dot com]

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.

-- 
           Summary: ld.so - Initialization and Termination Functions
                    incorrectly ordered
           Product: glibc
           Version: 2.11
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: drepper at redhat dot com
        ReportedBy: werkt0 at gmail dot com
                CC: glibc-bugs at sources dot redhat dot com
 GCC build triplet: i686-linux-gnu
  GCC host triplet: i686-linux-gnu
GCC target triplet: i686-linux-gnu


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[werkt0 at gmail dot com]

------- Additional Comments From werkt0 at gmail dot com  2010-06-18 18:40 -------
Created an attachment (id=4851)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4851&action=view)
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.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[werkt0 at gmail dot com]

------- Additional Comments From werkt0 at gmail dot com  2010-06-18 20:16 -------
Created an attachment (id=4852)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4852&action=view)
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.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[drepper at redhat dot com]

------- Additional Comments From drepper at redhat dot com  2010-06-19 19:17 -------
You'll have to provide a complete small, self-contained test case.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[werkt0 at gmail dot com]

------- Additional Comments From werkt0 at gmail dot com  2010-06-21 20:12 -------
Created an attachment (id=4855)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4855&action=view)
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #4852 is|0                           |1
           obsolete|                            |


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[schwab at linux-m68k dot org]

------- Additional Comments From schwab at linux-m68k dot org  2010-06-22 11:28 -------
(In reply to comment #2)
> there's a better portable pointer equiv integer type

int a = (l > p->l) - (l < p->l);

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/11724] ld.so - Initialization and Termination Functions incorrectly ordered

[werkt0 at gmail dot com]

------- Additional Comments From werkt0 at gmail dot com  2010-06-22 16:55 -------
(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?

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=11724

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.