[PATCH] Make elf section sorting more deterministic

[PATCH] Make elf section sorting more deterministic

[Ulf Hermann]

At least one test (dwfl-addr-sect) depends on the order of elf sections
with equal addresses. This is not guaranteed by the code. Compare also
by end address and name to tell entries apart.

Signed-off-by: Ulf Hermann <ulf.hermann@qt.io>
---
 libdwfl/ChangeLog           |  5 +++++
 libdwfl/derelocate.c        | 17 +++++++++++------
 tests/ChangeLog             |  6 ++++++
 tests/run-dwfl-addr-sect.sh |  2 +-
 4 files changed, 23 insertions(+), 7 deletions(-)

diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index f605f46..a1ed675 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,5 +1,10 @@
 2017-04-20  Ulf Hermann  <ulf.hermann@qt.io>
 
+	* derelocate.c (compare_secrefs): Compare by end address and then by
+	name if start addresses are equal.
+
+2017-04-20  Ulf Hermann  <ulf.hermann@qt.io>
+
 	* elf-from-memory.c: Explicitly cast phnum to size_t.
 
 2017-04-20  Ulf Hermann  <ulf.hermann@qt.io>
diff --git a/libdwfl/derelocate.c b/libdwfl/derelocate.c
index e5c3e12..8d965af 100644
--- a/libdwfl/derelocate.c
+++ b/libdwfl/derelocate.c
@@ -57,17 +57,22 @@ struct secref
 static int
 compare_secrefs (const void *a, const void *b)
 {
-  struct secref *const *p1 = a;
-  struct secref *const *p2 = b;
+  struct secref const *p1 = *(struct secref *const *)a;
+  struct secref const *p2 = *(struct secref *const *)b;
 
   /* No signed difference calculation is correct here, since the
      terms are unsigned and could be more than INT64_MAX apart.  */
-  if ((*p1)->start < (*p2)->start)
+  if (p1->start < p2->start)
     return -1;
-  if ((*p1)->start > (*p2)->start)
+  if (p1->start > p2->start)
     return 1;
-
-  return 0;
+  if (p1->end < p2->end)
+    return -1;
+  if (p1->end > p2->end)
+    return 1;
+  if (p1->name == NULL)
+    return p2->name == NULL ? 0 : -1;
+  return p2->name == NULL ? 1 : strcmp(p1->name, p2->name);
 }
 
 static int
diff --git a/tests/ChangeLog b/tests/ChangeLog
index c4e76d1..4da049b 100644
--- a/tests/ChangeLog
+++ b/tests/ChangeLog
@@ -1,5 +1,11 @@
 2017-04-20  Ulf Hermann <ulf.hermann@qt.io>
 
+	* run-dwfl-addr-sect.sh: Expect section with alphabetically smaller
+	name when requesting the start address of two otherwise equal
+	zero-sized sections.
+
+2017-04-20  Ulf Hermann <ulf.hermann@qt.io>
+
 	* run-readelf-dwz-multi.sh: Expect readelf to output "yes" for flags
 	that are set.
 	* run-readelf-zdebug-rel.sh: Likewise.
diff --git a/tests/run-dwfl-addr-sect.sh b/tests/run-dwfl-addr-sect.sh
index 80da008..e257bfc 100755
--- a/tests/run-dwfl-addr-sect.sh
+++ b/tests/run-dwfl-addr-sect.sh
@@ -20,7 +20,7 @@
 testfiles testfile43 testfile50
 
 testrun_compare ${abs_builddir}/dwfl-addr-sect -e testfile43 0x64 0x8 0x98 <<\EOF
-address 0x64 => module "" section 4 + 0
+address 0x64 => module "" section 3 + 0
 address 0x8 => module "" section 1 + 0x8
 address 0x98 => module "" section 7 + 0
 EOF
-- 
2.1.4

Re: [PATCH] Make elf section sorting more deterministic

[Mark Wielaard]

On Thu, Apr 20, 2017 at 04:54:26PM +0200, Ulf Hermann wrote:
> At least one test (dwfl-addr-sect) depends on the order of elf sections
> with equal addresses. This is not guaranteed by the code. Compare also
> by end address and name to tell entries apart.

O, interesting find. If the start addresses match the order depends on
the specific qsort algorithm. So you need a real tie breaker.

I think it is simpler and more predictable if we just take the section
number into account. It seem to have the added benefit that it provide
the same ordering as before with the glibc qsort, so no testcases need
to be adjusted. Does the following work for you?

diff --git a/libdwfl/derelocate.c b/libdwfl/derelocate.c
index 439a24e..0d10672 100644
--- a/libdwfl/derelocate.c
+++ b/libdwfl/derelocate.c
@@ -63,7 +63,10 @@ compare_secrefs (const void *a, const void *b)
   if ((*p1)->start > (*p2)->start)
     return 1;
 
-  return 0;
+  /* Same start address, then just compare which section came first.  */
+  size_t n1 = elf_ndxscn ((*p1)->scn);
+  size_t n2 = elf_ndxscn ((*p2)->scn);
+  return n1 - n2;
 }
 
 static int

Re: [PATCH] Make elf section sorting more deterministic

[Ulf Hermann]

On 04/27/2017 09:41 PM, Mark Wielaard wrote:
> On Thu, Apr 20, 2017 at 04:54:26PM +0200, Ulf Hermann wrote:
>> At least one test (dwfl-addr-sect) depends on the order of elf sections
>> with equal addresses. This is not guaranteed by the code. Compare also
>> by end address and name to tell entries apart.
> 
> O, interesting find. If the start addresses match the order depends on
> the specific qsort algorithm. So you need a real tie breaker.
> 
> I think it is simpler and more predictable if we just take the section
> number into account. It seem to have the added benefit that it provide
> the same ordering as before with the glibc qsort, so no testcases need
> to be adjusted. Does the following work for you?
> 
> diff --git a/libdwfl/derelocate.c b/libdwfl/derelocate.c
> index 439a24e..0d10672 100644
> --- a/libdwfl/derelocate.c
> +++ b/libdwfl/derelocate.c
> @@ -63,7 +63,10 @@ compare_secrefs (const void *a, const void *b)
>    if ((*p1)->start > (*p2)->start)
>      return 1;
>  
> -  return 0;
> +  /* Same start address, then just compare which section came first.  */
> +  size_t n1 = elf_ndxscn ((*p1)->scn);
> +  size_t n2 = elf_ndxscn ((*p2)->scn);
> +  return n1 - n2;

I would inline the whole thing to

return elf_ndxscn (p1->scn) - elf_ndxscn (p2->scn);

There is no point in forcing the compiler to keep the intermediate numbers as (signed) size_t. Also, I would still keep the check for p1->end and p2->end before this. If we have a section of size 0, and another one of size > 0 starting at the same place, we want them to be sorted by end address. The zero-sized section should be squeezed in before the one that actually has a size, not after it.

Ulf

Re: [PATCH] Make elf section sorting more deterministic

[Mark Wielaard]

[-- Attachment #1: Type: text/plain, Size: 2334 bytes --]

On Fri, Apr 28, 2017 at 12:35:26PM +0200, Ulf Hermann wrote:
> On 04/27/2017 09:41 PM, Mark Wielaard wrote:
> > On Thu, Apr 20, 2017 at 04:54:26PM +0200, Ulf Hermann wrote:
> >> At least one test (dwfl-addr-sect) depends on the order of elf sections
> >> with equal addresses. This is not guaranteed by the code. Compare also
> >> by end address and name to tell entries apart.
> > 
> > O, interesting find. If the start addresses match the order depends on
> > the specific qsort algorithm. So you need a real tie breaker.
> > 
> > I think it is simpler and more predictable if we just take the section
> > number into account. It seem to have the added benefit that it provide
> > the same ordering as before with the glibc qsort, so no testcases need
> > to be adjusted. Does the following work for you?
> > 
> > diff --git a/libdwfl/derelocate.c b/libdwfl/derelocate.c
> > index 439a24e..0d10672 100644
> > --- a/libdwfl/derelocate.c
> > +++ b/libdwfl/derelocate.c
> > @@ -63,7 +63,10 @@ compare_secrefs (const void *a, const void *b)
> >    if ((*p1)->start > (*p2)->start)
> >      return 1;
> >  
> > -  return 0;
> > +  /* Same start address, then just compare which section came first.  */
> > +  size_t n1 = elf_ndxscn ((*p1)->scn);
> > +  size_t n2 = elf_ndxscn ((*p2)->scn);
> > +  return n1 - n2;
> 
> I would inline the whole thing to
> 
> return elf_ndxscn (p1->scn) - elf_ndxscn (p2->scn);
> 
> There is no point in forcing the compiler to keep the intermediate
> numbers as (signed) size_t.

OK.

> Also, I would still keep the check for p1->end and p2->end before this.
> If we have a section of size 0, and another one of size > 0 starting at
> the same place, we want them to be sorted by end address. The zero-sized
> section should be squeezed in before the one that actually has a size,
> not after it.

Aha. I see that we treat the end special in find_section ()

          /* Consider the limit of a section to be inside it, unless it's
             inside the next one.  A section limit address can appear in
             line records.  */
          if (*addr == sections->refs[idx].end
              && idx + 1 < sections->count
              && *addr == sections->refs[idx + 1].start)
            ++idx;

So we do indeed want the zero sized section to be the first.

How about the attached?

Cheers,

Mark

[-- Attachment #2: 0001-Make-elf-section-sorting-more-deterministic.patch --]
[-- Type: text/plain, Size: 1706 bytes --]

From d7e1e08f68afd6c3363231e3100fa0124a2d5cb6 Mon Sep 17 00:00:00 2001
From: Ulf Hermann <ulf.hermann@qt.io>
Date: Thu, 20 Apr 2017 16:54:26 +0200
Subject: [PATCH] Make elf section sorting more deterministic

At least one test (dwfl-addr-sect) depends on the order of elf sections
with equal addresses. This is not guaranteed by the code. Compare also
by end address and section index to tell entries apart.

Signed-off-by: Ulf Hermann <ulf.hermann@qt.io>
Signed-off-by: Mark Wielaard <mark@klomp.org>
---
 libdwfl/ChangeLog    | 6 ++++++
 libdwfl/derelocate.c | 8 +++++++-
 2 files changed, 13 insertions(+), 1 deletion(-)

diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index 859b2ff..9bce6b1 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,6 +1,12 @@
 2017-04-20  Ulf Hermann  <ulf.hermann@qt.io>
 	    Mark Wielaard  <mark@klomp.org>
 
+	* derelocate.c (compare_secrefs): Compare by end address and then by
+	section number if addresses are equal.
+
+2017-04-20  Ulf Hermann  <ulf.hermann@qt.io>
+	    Mark Wielaard  <mark@klomp.org>
+
 	* linux-kernel-modules.c: Always return NULL from kernel_release() on
 	non-linux systems and set errno to ENOTSUP.
 
diff --git a/libdwfl/derelocate.c b/libdwfl/derelocate.c
index e5c3e12..2f80b20 100644
--- a/libdwfl/derelocate.c
+++ b/libdwfl/derelocate.c
@@ -67,7 +67,13 @@ compare_secrefs (const void *a, const void *b)
   if ((*p1)->start > (*p2)->start)
     return 1;
 
-  return 0;
+  if ((*p1)->end < (*p2)->end)
+    return -1;
+  if ((*p1)->end > (*p2)->end)
+    return 1;
+
+  /* Same start/end, then just compare which section came first.  */
+  return elf_ndxscn ((*p1)->scn) - elf_ndxscn ((*p2)->scn);
 }
 
 static int
-- 
2.9.3

Re: [PATCH] Make elf section sorting more deterministic

[Ulf Hermann]

> [...] How about the attached?

Looks good to me.

Ulf