Subject: [bug#52940] [PATCH] gremlin: Mimic ld.so NEEDED deduplication behavior.

From: Chris Marusich <[email-masked]>
Date: Sat, 01 Jan 2022 15:13:43 -0800

Hi Guix,

I've noticed that test file-needed/recursive in tests/gremlin.scm fails
on master branch on powerpc64le-linux.  It does not fail on
x86_64-linux.  I've attached a patch that attempts to fix the issue.
The primary issue is that it does not deduplicate entries in the same
way as ld.so when there are multiple entries referring to the same
shared object.  The patch changes file-needed/recursive to behave more
like ld.so.

Here is the failing test output, including the test source:

--8<---------------cut here---------------start------------->8---
;;; (truth ("linux-vdso64.so.1" "/gnu/store/gahs2sx5snbfkr9vlcjj5c2kvnlhr0zs-guile-3.0.7/lib/libguile-3.0.so.1" "/gnu/store/7x2cjqbmpgwrgmnb234gsxkmsqs5pj09-libgc-8.0.4/lib/libgc.so.1" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libpthread.so.0" "/gnu/store/521riv2sgv0b0s4j0kzz6i52rf9rarh8-libffi-3.3/lib/../lib/libffi.so.7" "/gnu/store/xj20v8lk2wal0z1rla0yx3bjkasbx6mq-libunistring-0.9.10/lib/libunistring.so.2" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libcrypt.so.1" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libdl.so.2" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libm.so.6" "/gnu/store/ys7b4gr5nbq8sfnff9ry5blb4bhpx6mq-gcc-7.5.0-lib/lib/libgcc_s.so.1" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libc.so.6" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/ld64.so.2"))

;;; (needed ("/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libc.so.6" "/gnu/store/ys7b4gr5nbq8sfnff9ry5blb4bhpx6mq-gcc-7.5.0-lib/lib/libgcc_s.so.1" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libm.so.6" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libdl.so.2" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libcrypt.so.1" "/gnu/store/xj20v8lk2wal0z1rla0yx3bjkasbx6mq-libunistring-0.9.10/lib/libunistring.so.2" "/gnu/store/521riv2sgv0b0s4j0kzz6i52rf9rarh8-libffi-3.3/lib/../lib/libffi.so.7" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libpthread.so.0" "/gnu/store/7x2cjqbmpgwrgmnb234gsxkmsqs5pj09-libgc-8.0.4/lib/libgc.so.1" "/gnu/store/gahs2sx5snbfkr9vlcjj5c2kvnlhr0zs-guile-3.0.7/lib/libguile-3.0.so.1" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/ld64.so.2" "/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/../lib/libc.so.6"))
test-name: file-needed/recursive
location: /home/marusich/guix-master/tests/gremlin.scm:70
source:
+ (test-assert
+   "file-needed/recursive"
+   (let* ((needed
+            (file-needed/recursive %guile-executable))
+          (pipe (dynamic-wind
+                  (lambda ()
+                    (setenv "LD_TRACE_LOADED_OBJECTS" "yup"))
+                  (lambda ()
+                    (open-pipe* OPEN_READ %guile-executable))
+                  (lambda () (unsetenv "LD_TRACE_LOADED_OBJECTS")))))
+     (define ldd-rx
+       (make-regexp
+         "^[[:blank:]]+([[:graph:]]+ => )?([[:graph:]]+) .*$"))
+     (define (read-ldd-output port)
+       (let loop ((result '()))
+         (match (read-line port)
+                ((? eof-object?) (reverse result))
+                ((= (cut regexp-exec ldd-rx <>) m)
+                 (if m
+                   (loop (cons (match:substring m 2) result))
+                   (loop result))))))
+     (define ground-truth
+       (remove
+         (cut string-prefix? "linux-vdso.so" <>)
+         (read-ldd-output pipe)))
+     (and (zero? (close-pipe pipe))
+          (lset= string=?
+                 (pk 'truth ground-truth)
+                 (pk 'needed needed)))))
actual-value: #f
result: FAIL
--8<---------------cut here---------------end--------------->8---

For reference, here is the actual dynamic section of of
%guile-executable on this system, as reported by readelf:

--8<---------------cut here---------------start------------->8---
$ readelf -d /gnu/store/gahs2sx5snbfkr9vlcjj5c2kvnlhr0zs-guile-3.0.7/bin/guile

Dynamic section at offset 0xfc60 contains 37 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libguile-3.0.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libgc.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libpthread.so.0]
 0x0000000000000001 (NEEDED)             Shared library: [libffi.so.7]
 0x0000000000000001 (NEEDED)             Shared library: [libunistring.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libcrypt.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libdl.so.2]
 0x0000000000000001 (NEEDED)             Shared library: [libm.so.6]
 0x0000000000000001 (NEEDED)             Shared library: [libgcc_s.so.1]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
 0x000000000000001d (RUNPATH)            Library runpath: [/gnu/store/gahs2sx5snbfkr9vlcjj5c2kvnlhr0zs-guile-3.0.7/lib:/gnu/store/7x2cjqbmpgwrgmnb234gsxkmsqs5pj09-libgc-8.0.4/lib:/gnu/store/521riv2sgv0b0s4j0kzz6i52rf9rarh8-libffi-3.3/lib/../lib:/gnu/store/xj20v8lk2wal0z1rla0yx3bjkasbx6mq-libunistring-0.9.10/lib:/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib:/gnu/store/ys7b4gr5nbq8sfnff9ry5blb4bhpx6mq-gcc-7.5.0-lib/lib:/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/../lib:/gnu/store/ys7b4gr5nbq8sfnff9ry5blb4bhpx6mq-gcc-7.5.0-lib/lib/gcc/powerpc64le-unknown-linux-gnu/7.5.0/../../../../lib]
 0x000000000000000c (INIT)               0x10000980
 0x000000000000000d (FINI)               0x10000ef4
 0x0000000000000019 (INIT_ARRAY)         0x1001fc50
 0x000000000000001b (INIT_ARRAYSZ)       8 (bytes)
 0x000000000000001a (FINI_ARRAY)         0x1001fc58
 0x000000000000001c (FINI_ARRAYSZ)       8 (bytes)
 0x0000000000000004 (HASH)               0x10000268
 0x000000006ffffef5 (GNU_HASH)           0x100002c0
 0x0000000000000005 (STRTAB)             0x10000470
 0x0000000000000006 (SYMTAB)             0x100002f0
 0x000000000000000a (STRSZ)              891 (bytes)
 0x000000000000000b (SYMENT)             24 (bytes)
 0x0000000000000015 (DEBUG)              0x0
 0x0000000000000003 (PLTGOT)             0x10020000
 0x0000000000000002 (PLTRELSZ)           216 (bytes)
 0x0000000000000014 (PLTREL)             RELA
 0x0000000000000017 (JMPREL)             0x10000880
 0x0000000070000000 (PPC64_GLINK)        0x10000eb0
 0x0000000070000003 (PPC64_OPT)          0x0
 0x0000000000000007 (RELA)               0x10000850
 0x0000000000000008 (RELASZ)             48 (bytes)
 0x0000000000000009 (RELAENT)            24 (bytes)
 0x000000006ffffffe (VERNEED)            0x10000810
 0x000000006fffffff (VERNEEDNUM)         2
 0x000000006ffffff0 (VERSYM)             0x100007ec
 0x0000000000000000 (NULL)               0x0
--8<---------------cut here---------------end--------------->8---

Note that the RUNPATH above contains an entry for
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib" followed
later by
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/../lib".  It seems
that ld.so's tracing mechanism is smart enough to avoid printing the
second entry.

So, the test fails because the "needed" list is not set-equivalent to
the "truth" list.  There are two reasons why they are not
set-equivalent:

A) "truth" contains "linux-vdso64.so.1", but "needed" does not.

B) "needed" contains
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/../lib/libc.so.6",
but "truth" does not.  However, both contain
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/libc.so.6",
which refers to the same file.

Regarding (A), it seems to be an error in the test logic.  The test code
already filters out strings beginning with "linux-vdso.so" from the
"truth" list.:

  (define ground-truth
    (remove (cut string-prefix? "linux-vdso.so" <>)
            (read-ldd-output pipe)))

The intent seems to be to filter out the vdso shared object from the
"truth" list.  However, it fails to do so in this case, since the name
of the vdso shared object is actually "linux-vdso64.so.1".  My patch
fixes this by filtering out strings that begin with "linux-vdso64.so",
too.

Regarding (B), it seems to occur because ld.so deduplicates entries.  I
checked the glibc source code, but I had a hard time figuring out
exactly how exactly the deduplication works.  In any case, based on
ld.so's actual behavior, it seems that ld.so does in fact deduplicate
entries, and file-needed/recursive does not.  This explains the
difference.

What is a good solution for (B)?  I can think of the following potential
solutions:

1) Try to avoid introducing multiple entries referring to the same thing
in the first place.  Somehow, somewhere, something is adding the second
entry to the dynamic section of Guile's ELF file.  It happens on
powerpc64le-linux but not on x86_64-linux.  What code or tool is doing
this?  I don't know, but I guess I would start by looking at the
gnu-build-system code.  I'm not sure if it's a really problem, though,
so I'm not eager to jump down this rabbit hole just yet.

2) Change the test so that it passes even if file-needed/recursive
returns multiple entries referring to the same file.  In other words,
accept that the current behavior is OK, even if it means that the
results returned by file-needed/recursive are not always exactly the
same as the results returned by ld.so.

3) Try to change file-needed/recursive so that it does not return
multiple entries referring to the same file.  In other words, make it
behave more like ld.so.

I can't think of a reason why the current behavior of
file-needed/recursive is bad, but it was simple enough to make it
deduplicate entries similarly to ld.so.  So, my patch implements
solution (3).  Hopefully it's good enough!

--
Chris

PGP: https://savannah.gnu.org/people/viewgpg.php?user_id=106836
From 67365d79afc7182aefbacf360941f338aea712b6 Mon Sep 17 00:00:00 2001
From: Chris Marusich <[email-masked]>
Date: Sat, 1 Jan 2022 14:17:38 -0800
Subject: [PATCH] gremlin: Mimic ld.so NEEDED deduplication behavior.

Together, these two changes fix the file-needed/recursive test, which was
failing on powerpc64le-linux.  It was not failing on x86_64-linux.

The test failure on powerpc64le-linux was caused by two issues.  First,
file-needed/recursive did not deduplicate entries in the same way as ld.so.
The %guile-executable ELF file contains in its RUNPATH both
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib" and
"/gnu/store/sipyfs2540b48b2sb9j8ypmybja1dvqb-glibc-2.31/lib/../lib".  Although
ld.so deduplicates the second entry, file-needed/recursive did not.  Second,
the vdso shared library name is "linux-vdso64.so.1", but the test incorrectly
assumed that the vdso shared library would always begin with "linux-vdso.so".

* guix/build/gremlin.scm (file-needed/recursive)[contains-canonical-file?]:
New procedure.  Use it to deduplicate entries that refer to the same file.
* tests/gremlin.scm (file-needed/recursive)[ground-truth]: In addition to
strings that begin with "linux-vdso.so", remove strings that begin with
"linux-vdso64.so".
---
 guix/build/gremlin.scm | 12 +++++++++++-
 tests/gremlin.scm      |  5 ++++-
 2 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/guix/build/gremlin.scm b/guix/build/gremlin.scm
index 2a74d51dd9..e90e59679b 100644
--- a/guix/build/gremlin.scm
+++ b/guix/build/gremlin.scm
@@ -1,5 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2015, 2018, 2020 Ludovic Courtès <[email-masked]>
+;;; Copyright © 2022 Chris Marusich <[email-masked]>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -268,6 +269,10 @@ recursively, and the list of .so file names that could not be found.  File
 names are resolved by searching the RUNPATH of the file that NEEDs them.
 
 This is similar to the info returned by the 'ldd' command."
+  (define (contains-canonical-file? file files)
+    (any (lambda (entry)
+           (string=? (canonicalize-path entry) (canonicalize-path file)))
+         files))
   (let loop ((files  (list file))
              (result '())
              (not-found '()))
@@ -292,10 +297,15 @@ This is similar to the info returned by the 'ldd' command."
                                                     (not (libc-library? needed))
                                                     needed))
                                              needed resolved))
+                       ;; Deduplicate entries that refer to the same file.
+                       ;; The actual ld.so tracing behavior is similar and
+                       ;; will de-duplicate entries even if they have
+                       ;; different names but refer to the same file.
                        (needed   (remove (lambda (value)
                                            (or (not value)
                                                ;; XXX: quadratic
-                                               (member value result)))
+                                               (contains-canonical-file?
+                                                value result)))
                                          resolved)))
                   (loop (append rest needed)
                         (append needed result)
diff --git a/tests/gremlin.scm b/tests/gremlin.scm
index 9af899c89a..86757e62b4 100644
--- a/tests/gremlin.scm
+++ b/tests/gremlin.scm
@@ -1,5 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2015, 2018, 2020 Ludovic Courtès <[email-masked]>
+;;; Copyright © 2022 Chris Marusich <[email-masked]>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -92,7 +93,9 @@
                (loop result))))))
 
     (define ground-truth
-      (remove (cut string-prefix? "linux-vdso.so" <>)
+      (remove (lambda (entry)
+                (or (string-prefix? "linux-vdso.so" entry)
+                    (string-prefix? "linux-vdso64.so" entry)))
               (read-ldd-output pipe)))
 
     (and (zero? (close-pipe pipe))
-- 
2.26.3