Bug 21266 - Unstable qsort in bfd/elf64-ppc.c results in difference in ld's TLS opt 3 test on Windows
Summary: Unstable qsort in bfd/elf64-ppc.c results in difference in ld's TLS opt 3 tes...
Status: RESOLVED FIXED
Alias: None
Product: binutils
Classification: Unclassified
Component: binutils (show other bugs)
Version: unspecified
: P2 minor
Target Milestone: 2.29
Assignee: Alan Modra
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-03-17 17:27 UTC by Paul Carroll
Modified: 2017-03-20 00:21 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed: 2017-03-19 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Paul Carroll 2017-03-17 17:27:26 UTC
The qsort() routine is noted to be unpredictable if 2 compared objects are considered equal.  The 'compare_symbols' function in the bfd/elf64-ppc.c file compares attributes of various symbols up to a point.  Where there can be a problem is if there are 2 symbols with different names, but identical attributes.  In this case, the current definition of 'compare_symbols' just does a:
     return 0;
at the end of the function.  This, however, results in different behavior in the TLS opt 3 testcase of the linker when the test suite is run on different OSes.  A standard was created for that test case on Linux.  When this is run on a Windows system, however, the test fails:

regexp_diff match failure
regexp "^00000000100000e8 <\.__tls_get_addr>:$"
line   "00000000100000e8 <.__tls_get_addr_opt>:"
regexp_diff match failure
regexp "^.*:    (4b ff ff ed|ed ff ff 4b)       bl      100000e8 <\.__tls_get_addr>$"
line   "    100000fc:   4b ff ff ed     bl      100000e8 <.__tls_get_addr_opt>" regexp_diff match failure
regexp "^.*:    (4b ff ff e1|e1 ff ff 4b)       bl      100000e8 <\.__tls_get_addr>$"
line   "    10000108:   4b ff ff e1     bl      100000e8 <.__tls_get_addr_opt>"

To get predictable results between Linux and Windows, the last line of 'compare_symbols' should be changed to be:
     return strcmp(a->name,b->name);
With that change, if symbols have different attributes, then they continue to be handled as before.
If, however, symbols are identical except for having different names (i.e., 2 symbols referring to the same location), then that will allow qsort() to produce identical output for different OSes.
Comment 1 Alexander Fedotov 2017-03-18 14:48:56 UTC
Paul,
You can try to add qsort.c (from glibc for instance) into libiberty to get the same behaviour on different OSes.
Comment 2 Alan Modra 2017-03-19 21:46:51 UTC
This one is easy to fix in elf64-ppc.c, because we are sorting an array of pointers.  The value of the pointer can be the final key.
Comment 3 Sourceware Commits 2017-03-20 00:00:21 UTC
The master branch has been updated by Alan Modra <amodra@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=aaed6f5be3a41a88cc13c744e88af78f5a42dd5b

commit aaed6f5be3a41a88cc13c744e88af78f5a42dd5b
Author: Alan Modra <amodra@gmail.com>
Date:   Mon Mar 20 08:25:50 2017 +1030

    PR 21266, unstable qsort in bfd/elf64-ppc.c
    
    	PR 21266
    	* elf64-ppc.c (compare_symbols): Stabilize sort.
Comment 4 Alan Modra 2017-03-20 00:21:39 UTC
Fixed.