[PATCH] ld.so: Fix local scopes for prelink conflicts

[Alexander Miller <alex dot miller at gmx dot de>]

Hello folks,

I've been investigating failures to start a KDE session on a prelinked
system after updating glibc to version 2.22 [1]. I could track down
the issue to a bug in the dynamic loader: the local scope for comparing
symbol lookup in global scope vs. library scope when computing conflicts
is not in the correct order.

When we have the following situation:
  program
  +-- libA
  `-- libB
      +-- libC
      |   `-- libA
      `-- libA2
where a symbol is provided by both libA and libA2, the symbol should
be resolved to that of libA. When prelinking libB, there is no main
program and libA2 precedes libA in the search scope; therefore libB
gets prelinked to use libA2's symbol. That means the program needs a
conflict fixup. But ld.so erroneously uses depth first search to compute
libB's local scope; it sees libA before libA2 and doesn't report a
conflict - bummer.

I wrote a small example program that demonstrates the problem; it
can be found here: <https://bugs.gentoo.org/attachment.cgi?id=432494>
The prelinked copy of the program and the original print different
messages. (You can make a test case out of this.)

Note that the bug has been present in glibc since prelink support was
initially added in 2001 or so; the recent failures have been triggered
by the conversion of conflicting symbols to IFUNCs. In my case it was
fork from libpthread vs. libc. In the prelinked libkdeui, fork was
resolved to libpthread's fork_resolve [2] and the fixup was missing
for the affected KDE programs due to the bug. Before fork was converted
to an IFUNC in libpthread the bug was not noticed.

The patch below fixes the issues for me (and a few other people).
It has been created against 2.22 but should work for current sources.
I've attached it at [1] first and have been asked to post it here for
discussion.

Cheers,
Alex

Oh, for the legal stuff: you don't have a copyright assignment from
me and I don't think you need one since the code itself is pretty small
and trivial. To make it explicit: the patch below and the demo linked
above can be used under the terms of CC0 [3].

[1] <https://bugs.gentoo.org/show_bug.cgi?id=579374>
[2] I don't understand (yet) why this would make sense anyway.
[3] <https://creativecommons.org/publicdomain/zero/1.0/>

-- >8 --
When computing conflict fixups for prelink, ld.so needs to be able to
look up symbols in the local scopes of loaded libraries and compare
them with the result in the global scope. The old implementation
erroneously used depth first search to compute the local scopes. This
could lead to conflicts being missed and therefore prelinked binaries
malfunctioning.

The new code builds the local scopes with breadth first search as
required to get the same order that is used when prelinking the dependent
libraries themselves.

Changelog:
	* elf/dl-deps.c (_dl_build_local_scope): Use breadth first search
	to build list, in order to get the same search order that was used
	to prelink the library.

--- glibc-2.22/elf/dl-deps.c
+++ glibc-2.22/elf/dl-deps.c
@@ -70,18 +70,23 @@ openaux (void *a)
 static ptrdiff_t
 internal_function
 _dl_build_local_scope (struct link_map **list, struct link_map *map)
 {
-  struct link_map **p = list;
+  size_t n = 0;
+  size_t m;
   struct link_map **q;
 
-  *p++ = map;
+  list[n++] = map;
   map->l_reserved = 1;
-  if (map->l_initfini)
-    for (q = map->l_initfini + 1; *q; ++q)
-      if (! (*q)->l_reserved)
-	p += _dl_build_local_scope (p, *q);
-  return p - list;
+  for (m = 0; m < n; ++m)
+    if (list[m]->l_initfini)
+      for (q = list[m]->l_initfini + 1; *q; ++q)
+	if (! (*q)->l_reserved)
+	  {
+	    list[n++] = *q;
+	    (*q)->l_reserved = 1;
+	  }
+  return n;
 }
 
 
 /* We use a very special kind of list to track the path