_dl_build_local_scope - BZ #20488

[Mark Hatle]

This is somewhat a followup to Alexander Miller's email for a few months back:

https://sourceware.org/ml/libc-alpha/2016-05/msg00034.html

Independently we identify a similar problem with the emulated rtld in the cross
prelinker.  The ELF spec indicates that the symbol resolution is breadth first,
not depth first.  Without doing this a failure can occur.

The current prelinker (git://git.yoctoproject.org/prelink-cross) has a specific
test case for the ordering issue.  See 'order' test case.

The patch below fixes the issue in glibc and was developed independently.  My
employer (Wind River) has a copyright assigned with the FSF if the change is
substantial enough to require one.

The patch is attached to BZ 20488, as well as included below.


>From 6e4ec5a3c5fe63b6458036f18d43124de4a7e724 Mon Sep 17 00:00:00 2001
From: Mark Hatle <mark.hatle@windriver.com>
Date: Thu, 18 Aug 2016 14:07:58 -0500
Subject: [PATCH] elf/dl-deps.c: Make _dl_build_local_scope breadth first

According to the ELF specification:

When resolving symbolic references, the dynamic linker examines the symbol
tables with a breadth-first search.

This function was using a depth first search.  By doing so the conflict
resolution reported to the prelinker (when LD_TRACE_PRELINKING=1 is set)
was incorrect.  This caused problems when their were various circular
dependencies between libraries.  The problem usually manifested itself by
the wrong IFUNC being executed.

Signed-off-by: Mark Hatle <mark.hatle@windriver.com>
---
 elf/dl-deps.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index 6a82987..fc37c87 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -73,13 +73,19 @@ _dl_build_local_scope (struct link_map **list, struct
link_map *map)
 {
   struct link_map **p = list;
   struct link_map **q;
+  struct link_map **r;

   *p++ = 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);
+
+  for (r = list; r < p; ++r)
+    if ((*r)->l_initfini)
+      for (q = (*r)->l_initfini + 1; *q; ++q)
+	if (! (*q)->l_reserved)
+	  {
+	    *p++ = *q;
+	    (*q)->l_reserved = 1;
+	  }
   return p - list;
 }

-- 
2.5.5