public inbox for dwz@sourceware.org
 help / color / mirror / Atom feed
* Re: [PATCH] Handle unsorted section header table
  2019-01-01  0:00 [PATCH] Handle unsorted section header table Tom de Vries
  2019-01-01  0:00 ` [committed][PATCH] " Tom de Vries
@ 2019-01-01  0:00 ` Tom de Vries
  1 sibling, 0 replies; 3+ messages in thread
From: Tom de Vries @ 2019-01-01  0:00 UTC (permalink / raw)
  To: dwz, jakub

On 12-03-19 18:07, Tom de Vries wrote:
> Hi,
> Handle unsorted section header table in write_dso by:
> - rewriting loop (*) in sh_offset updating code to handle unsorted section
>   header table

> (*) Specifically, this one:
> ...
>     for (j = dso->ehdr.e_shstrndx + 1; j < dso->ehdr.e_shnum; ++j)
>       dso->shdr[j].sh_offset += len;
> ...
> 

I realized that this in itself is a potential wrong-code issue,
submitted patch for it here (
https://sourceware.org/ml/dwz/2019-q1/msg00127.html ).

Thanks,
- Tom

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [PATCH] Handle unsorted section header table
@ 2019-01-01  0:00 Tom de Vries
  2019-01-01  0:00 ` [committed][PATCH] " Tom de Vries
  2019-01-01  0:00 ` [PATCH] " Tom de Vries
  0 siblings, 2 replies; 3+ messages in thread
From: Tom de Vries @ 2019-01-01  0:00 UTC (permalink / raw)
  To: dwz, jakub

Hi,

Consider a hello world, with .gdb_index added by the gold linker.  When
running dwz, we run into this error:
...
$ gcc hello.c -g -fuse-ld=gold -Wl,--gdb-index
$ dwz a.out
dwz: Section offsets in a.out not monotonically increasing
...

Inspecting the section offsets around .gdb_index:
...
$ readelf -S a.out | grep '[[]' | egrep -C1  'Offset|\.gdb_index'
  [Nr] Name              Type             Address           Offset
  [ 0]                   NULL             0000000000000000  00000000
--
  [31] .debug_str        PROGBITS         0000000000000000  00001b2f
  [32] .gdb_index        PROGBITS         0000000000000000  000034b0
  [33] .debug_ranges     PROGBITS         0000000000000000  000021f0
...
indeed shows that the offsets are not monotonically increasing.

Handle unsorted section header table in write_dso by:
- rewriting loop (*) in sh_offset updating code to handle unsorted section
  header table
- rewriting sh_offset comparisons using before/after relation
  arrays after_sht and sorted_section_pos, to make the sh_offset updating
  code more robust.
- rewriting the sh_offset alignment updating loops to loop in
  sh_offset order.

(*) Specifically, this one:
...
    for (j = dso->ehdr.e_shstrndx + 1; j < dso->ehdr.e_shnum; ++j)
      dso->shdr[j].sh_offset += len;
...

OK for trunk?

Thanks,
- Tom

Handle unsorted section header table

2019-03-12  Tom de Vries  <tdevries@suse.de>

	PR dwz/24249
	* dwz.c (compare_section_numbers, sort_dso): New function.
	(write_dso): Handle unsorted section header table.
	* Makefile (TEST_EXECS): Add hello-gold-gdb-index.
	(hello-gold-gdb-index): New target.
	* testsuite/dwz.tests/dwz-tests.exp: Require hello-gold-gdb-index for
	gold-gdb-index.sh.
	* testsuite/dwz.tests/gold-gdb-index.sh: New test.

---
 Makefile                              |   5 +-
 dwz.c                                 | 144 +++++++++++++++++++++++++++++++---
 testsuite/dwz.tests/dwz-tests.exp     |  22 +++++-
 testsuite/dwz.tests/gold-gdb-index.sh |  13 +++
 4 files changed, 169 insertions(+), 15 deletions(-)

diff --git a/Makefile b/Makefile
index b318fd7..643ce0a 100644
--- a/Makefile
+++ b/Makefile
@@ -17,11 +17,14 @@ clean:
 
 PWD:=$(shell pwd -P)
 
-TEST_EXECS = hello
+TEST_EXECS = hello hello-gold-gdb-index
 
 hello:
 	$(CC) hello.c -o $@ -g
 
+hello-gold-gdb-index:
+	$(CC) hello.c -g -fuse-ld=gold -Wl,--gdb-index -o $@ || touch $@
+
 check: dwz $(TEST_EXECS)
 	mkdir -p testsuite-bin
 	cd testsuite-bin; ln -sf $(PWD)/dwz .
diff --git a/dwz.c b/dwz.c
index 476807a..45d5041 100644
--- a/dwz.c
+++ b/dwz.c
@@ -10041,6 +10041,99 @@ error_out:
   return NULL;
 }
 
+/* Array of section numbers sorted by sh_offset.  So, this holds:
+     (sorted_section_numbers[i].sh_offset
+      < sorted_section_numbers[i + 1].sh_offset).
+   It can be used to iterate over sections in sh_offset order:
+     for (i = 1, j = sorted_section_numbers[i];
+	  i < n;
+	  ++i, j = sorted_section_numbers[i]).	*/
+static unsigned int *sorted_section_numbers;
+
+/* Array of positions of section numbers in sorted_section_numbers array.
+   So, this holds:
+     (sorted_section_pos[sorted_section_numbers[i]] == i).
+   It can be used to safely test before/after relationship in terms of sh_offset
+   in loops where sh_offset is modified, replacing:
+     if (dso->shdr[i].sh_offset < dso->shdr[i].sh_offset)
+   with:
+     if (sorted_section_pos[i] < sorted_section_pos[j]).  */
+static unsigned int *sorted_section_pos;
+
+/* Array for use in compare_section_numbers.  Could be passed in as arg when
+   using qsort_r instead.  */
+static GElf_Shdr *section_headers;
+
+static int
+compare_section_numbers (const void *p1, const void *p2)
+{
+  const int i1 = *(const int *)p1;
+  const int i2 = *(const int *)p2;
+
+  /* Keep element 0 at 0.  */
+  if (i1 == 0 || i2 == 0)
+    {
+      if (i1 == i2)
+	return 0;
+      if (i1 == 0)
+	return -1;
+      if (i2 == 0)
+	return 1;
+    }
+
+  if (section_headers[i1].sh_offset
+      < section_headers[i2].sh_offset)
+    return -1;
+
+  if (section_headers[i1].sh_offset
+      > section_headers[i2].sh_offset)
+    return 1;
+
+  /* In case sh_offset is the same, keep the original relative order.  */
+  if (i1 < i2)
+    return -1;
+  if (i1 > i2)
+    return 1;
+
+  return 0;
+}
+
+static int
+sort_dso (DSO *dso)
+{
+  unsigned int i;
+
+  sorted_section_numbers
+    = (unsigned int *)malloc (dso->ehdr.e_shnum * sizeof (unsigned int));
+  if (sorted_section_numbers == NULL)
+    {
+      error (0, ENOMEM, "Could not sort DSO");
+      return 1;
+    }
+
+  sorted_section_pos
+    = (unsigned int *)malloc (dso->ehdr.e_shnum * sizeof (unsigned int));
+  if (sorted_section_pos == NULL)
+    {
+      error (0, ENOMEM, "Could not sort DSO");
+      return 1;
+    }
+
+  for (i = 0; i < dso->ehdr.e_shnum; ++i)
+    sorted_section_numbers[i] = i;
+
+  section_headers = dso->shdr;
+  qsort (sorted_section_numbers, dso->ehdr.e_shnum,
+	 sizeof (sorted_section_numbers[0]), compare_section_numbers);
+  section_headers = NULL;
+  assert (sorted_section_numbers[0] == 0);
+
+  for (i = 0; i < dso->ehdr.e_shnum; ++i)
+    sorted_section_pos[sorted_section_numbers[i]] = i;
+
+  return 0;
+}
+
 /* Store new ELF into FILE.  debug_sections array contains
    new_data/new_size pairs where needed.  */
 static int
@@ -10056,15 +10149,33 @@ write_dso (DSO *dso, const char *file, struct stat *st)
   GElf_Word shstrtabadd = 0;
   char *shstrtab = NULL;
   bool remove_sections[SECTION_COUNT];
+  bool after_sht[dso->ehdr.e_shnum];
+
+  if (sort_dso (dso))
+    return 1;
 
   memset (remove_sections, '\0', sizeof (remove_sections));
+  memset (after_sht, '\0', sizeof (after_sht));
+
   ehdr = dso->ehdr;
   if (multi_ehdr.e_ident[0] == '\0')
     multi_ehdr = ehdr;
 
+  /* The after_sht array records the position of the section header table
+     relative to the sections.  It can be used to safely test before/after
+     relationship in terms of sh_offset in loops where sh_offset is modified,
+     replacing:
+       dso->shdr[i].sh_offset > dso->ehdr.e_shoff
+     with
+       after_sht[i].  */
+  for (i = 1; i < dso->ehdr.e_shnum; ++i)
+    if (dso->shdr[i].sh_offset > dso->ehdr.e_shoff)
+      after_sht[i] = true;
+
   for (i = 0; debug_sections[i].name; i++)
     if (debug_sections[i].new_size != debug_sections[i].size)
       {
+	unsigned int off_index;
 	if (debug_sections[i].size == 0
 	    && debug_sections[i].sec == 0)
 	  {
@@ -10080,7 +10191,7 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	      min_shoff = ehdr.e_shoff;
 	    for (j = 1; j < dso->ehdr.e_shnum; ++j)
 	      {
-		if (dso->shdr[j].sh_offset > ehdr.e_shoff)
+		if (after_sht[j])
 		  dso->shdr[j].sh_offset += ehdr.e_shentsize;
 		if (dso->shdr[j].sh_link > (unsigned int) addsec)
 		  dso->shdr[j].sh_link++;
@@ -10097,27 +10208,31 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	    dso->shdr[dso->ehdr.e_shstrndx].sh_size += len;
 	    if (dso->shdr[dso->ehdr.e_shstrndx].sh_offset < min_shoff)
 	      min_shoff = dso->shdr[dso->ehdr.e_shstrndx].sh_offset;
-	    for (j = dso->ehdr.e_shstrndx + 1; j < dso->ehdr.e_shnum; ++j)
-	      dso->shdr[j].sh_offset += len;
-	    if (ehdr.e_shoff > dso->shdr[dso->ehdr.e_shstrndx].sh_offset)
+	    for (j = 1; j < dso->ehdr.e_shnum; ++j)
+	      if (sorted_section_pos[j]
+		  > sorted_section_pos[dso->ehdr.e_shstrndx])
+		dso->shdr[j].sh_offset += len;
+	    if (!after_sht[dso->ehdr.e_shstrndx])
 	      ehdr.e_shoff += len;
 	    shstrtabadd += len;
 	    diff = debug_sections[i].new_size;
 	    addsize += diff;
 	    off = dso->shdr[addsec].sh_offset;
+	    off_index = addsec;
 	  }
 	else
 	  {
 	    diff = (GElf_Off) debug_sections[i].new_size
 		   - (GElf_Off) dso->shdr[debug_sections[i].sec].sh_size;
 	    off = dso->shdr[debug_sections[i].sec].sh_offset;
+	    off_index = debug_sections[i].sec;
 	  }
 	if (off < min_shoff)
 	  min_shoff = off;
 	for (j = 1; j < dso->ehdr.e_shnum; ++j)
-	  if (dso->shdr[j].sh_offset > off)
+	  if (sorted_section_pos[j] > sorted_section_pos[off_index])
 	    dso->shdr[j].sh_offset += diff;
-	if (ehdr.e_shoff > off)
+	if (!after_sht[off_index])
 	  ehdr.e_shoff += diff;
 	dso->shdr[debug_sections[i].sec].sh_size
 	  = debug_sections[i].new_size;
@@ -10129,7 +10244,7 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	      min_shoff = ehdr.e_shoff;
 	    for (j = 1; j < dso->ehdr.e_shnum; ++j)
 	      {
-		if (dso->shdr[j].sh_offset > ehdr.e_shoff)
+		if (after_sht[j])
 		  dso->shdr[j].sh_offset -= ehdr.e_shentsize;
 		if (dso->shdr[j].sh_link
 		    > (unsigned int) debug_sections[i].sec)
@@ -10163,7 +10278,9 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	  GElf_Off last_shoff = 0;
 	  int k = -1;
 	  bool shdr_placed = false;
-	  for (j = 1; j < dso->ehdr.e_shnum; ++j)
+	  int l;
+	  for (l = 1, j = sorted_section_numbers[l]; l < dso->ehdr.e_shnum;
+	       ++l, j = sorted_section_numbers[l])
 	    if (dso->shdr[j].sh_offset < min_shoff && !last_shoff)
 	      continue;
 	    else if ((dso->shdr[j].sh_flags & SHF_ALLOC) != 0)
@@ -10181,15 +10298,18 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	    else
 	      {
 		if (k == -1)
-		  k = j;
+		  k = l;
 		last_shoff = dso->shdr[j].sh_offset + dso->shdr[j].sh_size;
 	      }
 	  last_shoff = min_shoff;
-	  for (j = k; j <= dso->ehdr.e_shnum; ++j)
+	  for (l = k; l <= dso->ehdr.e_shnum; ++l)
 	    {
+	      j = (l == dso->ehdr.e_shnum
+		   ? -1
+		   : (int)sorted_section_numbers[l]);
 	      if (!shdr_placed
 		  && ehdr.e_shoff >= min_shoff
-		  && (j == dso->ehdr.e_shnum
+		  && (l == dso->ehdr.e_shnum
 		      || ehdr.e_shoff < dso->shdr[j].sh_offset))
 		{
 		  if (ehdr.e_ident[EI_CLASS] == ELFCLASS64)
@@ -10199,7 +10319,7 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 		  last_shoff = ehdr.e_shoff + ehdr.e_shnum * ehdr.e_shentsize;
 		  shdr_placed = true;
 		}
-	      if (j == dso->ehdr.e_shnum)
+	      if (l == dso->ehdr.e_shnum)
 		break;
 	      dso->shdr[j].sh_offset = last_shoff;
 	      if (dso->shdr[j].sh_addralign > 1)
diff --git a/testsuite/dwz.tests/dwz-tests.exp b/testsuite/dwz.tests/dwz-tests.exp
index bea18fb..39eb661 100644
--- a/testsuite/dwz.tests/dwz-tests.exp
+++ b/testsuite/dwz.tests/dwz-tests.exp
@@ -5,8 +5,26 @@ set pwd [pwd]
 set env(PATH) $pwd/$srcdir/scripts:$::env(PATH)
 
 foreach test $tests {
-    set dir [exec basename $test]
-    set dir $pwd/tmp.$dir
+    set basename [exec basename $test]
+
+    set required_execs []
+    if { $basename == "gold-gdb-index.sh" } {
+	lappend required_execs "hello-gold-gdb-index"
+    }
+
+    set unsupported 0
+    foreach required_exec $required_execs {
+	set size [file size $required_exec]
+	if { $size == 0 } {
+	    set unsupported 1
+	}
+    }
+    if { $unsupported == 1 } {
+	unsupported "$test"
+	continue
+    }
+
+    set dir $pwd/tmp.$basename
     exec rm -Rf $dir
     exec mkdir $dir
 
diff --git a/testsuite/dwz.tests/gold-gdb-index.sh b/testsuite/dwz.tests/gold-gdb-index.sh
new file mode 100755
index 0000000..cacc2b7
--- /dev/null
+++ b/testsuite/dwz.tests/gold-gdb-index.sh
@@ -0,0 +1,13 @@
+#!/bin/sh
+
+set -e
+
+cp ../hello-gold-gdb-index 1
+
+dwz 1
+
+smaller-than.sh 1 ../hello-gold-gdb-index
+
+[ $(ls) = "1" ]
+
+rm -f 1

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [committed][PATCH] Handle unsorted section header table
  2019-01-01  0:00 [PATCH] Handle unsorted section header table Tom de Vries
@ 2019-01-01  0:00 ` Tom de Vries
  2019-01-01  0:00 ` [PATCH] " Tom de Vries
  1 sibling, 0 replies; 3+ messages in thread
From: Tom de Vries @ 2019-01-01  0:00 UTC (permalink / raw)
  To: dwz, jakub

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

Hi,

Committed as attached.

Thanks,
- Tom

[-- Attachment #2: 0001-Handle-unsorted-section-header-table.patch --]
[-- Type: text/x-patch, Size: 5284 bytes --]

Handle unsorted section header table

Consider a hello world, with .gdb_index added by the gold linker.  When
running dwz, we run into this error:
...
$ gcc hello.c -g -fuse-ld=gold -Wl,--gdb-index
$ dwz a.out
dwz: Section offsets in a.out not monotonically increasing
...

Inspecting the section offsets around .gdb_index:
...
$ readelf -S a.out | grep '[[]' | egrep -C1  'Offset|\.gdb_index'
  [Nr] Name              Type             Address           Offset
  [ 0]                   NULL             0000000000000000  00000000
--
  [31] .debug_str        PROGBITS         0000000000000000  00001b2f
  [32] .gdb_index        PROGBITS         0000000000000000  000034b0
  [33] .debug_ranges     PROGBITS         0000000000000000  000021f0
...
indeed shows that the offsets are not monotonically increasing.

Handle unsorted section header table in write_dso by rewriting the file
offfset alignment updating loops to loop in file offset order.

2019-03-23  Tom de Vries  <tdevries@suse.de>

	PR dwz/24249
	* Makefile (TEST_EXECS): Add hello-gold-gdb-index.
	(hello-gold-gdb-index): New target.
	* dwz.c (write_dso): Handle aligning file offsets of unordered section
	header table.
	* testsuite/dwz.tests/dwz-tests.exp: Require hello-gold-gdb-index for
	gold-gdb-index.sh.
	* testsuite/dwz.tests/gold-gdb-index.sh: New test.

---
 Makefile                              |  6 +++++-
 dwz.c                                 | 31 +++++++++++++------------------
 testsuite/dwz.tests/dwz-tests.exp     |  3 +++
 testsuite/dwz.tests/gold-gdb-index.sh |  7 +++++++
 4 files changed, 28 insertions(+), 19 deletions(-)

diff --git a/Makefile b/Makefile
index 2d9ba4e..1193283 100644
--- a/Makefile
+++ b/Makefile
@@ -24,7 +24,7 @@ PWD:=$(shell pwd -P)
 
 TEST_SRC = $(srcdir)/testsuite/dwz.tests
 TEST_EXECS = hello dw2-restrict py-section-script dwz-for-test min two-typedef \
-	dw2-skip-prologue start implptr-64bit-d2o4a8r8t0
+	dw2-skip-prologue start implptr-64bit-d2o4a8r8t0 hello-gold-gdb-index
 
 hello:
 	$(CC) $(TEST_SRC)/hello.c -o $@ -g
@@ -62,6 +62,10 @@ implptr-64bit-d2o4a8r8t0:
 	$(CC) $(TEST_SRC)/implptr-64bit-d2o4a8r8t0.S $(TEST_SRC)/main.c -o $@ \
 	  -g || touch $@
 
+hello-gold-gdb-index:
+	$(CC) $(TEST_SRC)/hello.c -g -fuse-ld=gold -Wl,--gdb-index -o $@ \
+	    || touch $@
+
 # On some systems we need to set and export DEJAGNU to suppress
 # WARNING: Couldn't find the global config file.
 DEJAGNU ?= /dev/null
diff --git a/dwz.c b/dwz.c
index 3389ff0..a73fe38 100644
--- a/dwz.c
+++ b/dwz.c
@@ -10667,9 +10667,12 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 	     >= min_shoff aren't non-ALLOC.  */
 	  GElf_Off last_shoff = 0;
 	  int k = -1;
-	  bool shdr_placed = false;
-	  for (j = 1; j < dso->ehdr.e_shnum; ++j)
-	    if (dso->shdr[j].sh_offset < min_shoff && !last_shoff)
+	  int l;
+	  for (l = 1, j = sorted_section_numbers[l]; l <= dso->ehdr.e_shnum;
+	       ++l, j = sorted_section_numbers[l])
+	    if (j == dso->ehdr.e_shnum)
+	      continue;
+	    else if (dso->shdr[j].sh_offset < min_shoff && !last_shoff)
 	      continue;
 	    else if ((dso->shdr[j].sh_flags & SHF_ALLOC) != 0)
 	      {
@@ -10677,35 +10680,27 @@ write_dso (DSO *dso, const char *file, struct stat *st)
 			     "ones", dso->filename);
 		return 1;
 	      }
-	    else if (dso->shdr[j].sh_offset < last_shoff)
-	      {
-		error (0, 0, "Section offsets in %s not monotonically "
-			     "increasing", dso->filename);
-		return 1;
-	      }
 	    else
 	      {
+		assert (dso->shdr[j].sh_offset >= last_shoff);
+
 		if (k == -1)
-		  k = j;
+		  k = l;
 		last_shoff = dso->shdr[j].sh_offset + dso->shdr[j].sh_size;
 	      }
 	  last_shoff = min_shoff;
-	  for (j = k; j <= dso->ehdr.e_shnum; ++j)
+	  for (l = k, j = sorted_section_numbers[l]; l <= dso->ehdr.e_shnum;
+	       ++l, j = sorted_section_numbers[l])
 	    {
-	      if (!shdr_placed
-		  && ehdr.e_shoff >= min_shoff
-		  && (j == dso->ehdr.e_shnum
-		      || ehdr.e_shoff < dso->shdr[j].sh_offset))
+	      if (j == dso->ehdr.e_shnum)
 		{
 		  if (ehdr.e_ident[EI_CLASS] == ELFCLASS64)
 		    ehdr.e_shoff = (last_shoff + 7) & -8;
 		  else
 		    ehdr.e_shoff = (last_shoff + 3) & -4;
 		  last_shoff = ehdr.e_shoff + ehdr.e_shnum * ehdr.e_shentsize;
-		  shdr_placed = true;
+		  continue;
 		}
-	      if (j == dso->ehdr.e_shnum)
-		break;
 	      dso->shdr[j].sh_offset = last_shoff;
 	      if (dso->shdr[j].sh_addralign > 1)
 		dso->shdr[j].sh_offset
diff --git a/testsuite/dwz.tests/dwz-tests.exp b/testsuite/dwz.tests/dwz-tests.exp
index c1f913a..108b167 100644
--- a/testsuite/dwz.tests/dwz-tests.exp
+++ b/testsuite/dwz.tests/dwz-tests.exp
@@ -42,6 +42,9 @@ foreach test $tests {
     if { $basename == "pr24170.sh" } {
 	lappend required_execs "implptr-64bit-d2o4a8r8t0"
     }
+    if { $basename == "gold-gdb-index.sh" } {
+	lappend required_execs "hello-gold-gdb-index"
+    }
     if { ![istarget x86_64-*-*] } {
 	if { $basename == "pr24468.sh" } {
 	    unsupported "$test"
diff --git a/testsuite/dwz.tests/gold-gdb-index.sh b/testsuite/dwz.tests/gold-gdb-index.sh
new file mode 100644
index 0000000..eb2a164
--- /dev/null
+++ b/testsuite/dwz.tests/gold-gdb-index.sh
@@ -0,0 +1,7 @@
+cp ../hello-gold-gdb-index 1
+
+dwz 1
+
+smaller-than.sh 1 ../hello-gold-gdb-index
+
+rm -f 1

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2019-06-25 15:19 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-01-01  0:00 [PATCH] Handle unsorted section header table Tom de Vries
2019-01-01  0:00 ` [committed][PATCH] " Tom de Vries
2019-01-01  0:00 ` [PATCH] " Tom de Vries

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).