Re: [PATCH 1/3] libdw: Make srclines use a stable sort

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Mark Wielaard]

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

On Mon, 2014-12-15 at 13:48 -0800, Josh Stone wrote:
> On 12/13/2014 03:18 PM, Mark Wielaard wrote:
> > On Thu, Dec 11, 2014 at 05:34:06PM -0800, Josh Stone wrote:
> >> It might be worth auditing other qsort/tsearch comparison functions for
> >> similar wrapping possibilities.
> > 
> > I think you are right. I looked over all compare functions and two didn't
> > do as you suggest. The attached patch fixes those. Do that look correct?
> 
> Those look good.

Thanks, pushed.

> I think src/elfcmp.c compare_Elf32_Word() is also wrong, as big u32
> values could wrap int subtraction.  I didn't find any others.

Ah, missed that Elf32_Word is unsigned. There is an assert that makes
sure it is at least as wide as an int, but that isn't enough indeed.

Proposed fix attached.

Thanks,

Mark

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-elfcmp-Make-sure-Elf32_Word-difference-doesn-t-wrap-.patch --]
[-- Type: text/x-patch, Size: 1246 bytes --]

From 6c8781d9175900e321a8afe2c5073db68872e8e0 Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mjw@redhat.com>
Date: Tue, 16 Dec 2014 11:04:55 +0100
Subject: [PATCH] elfcmp: Make sure Elf32_Word difference doesn't wrap around
 in int compare.

Signed-off-by: Mark Wielaard <mjw@redhat.com>
---
 src/ChangeLog | 5 +++++
 src/elfcmp.c  | 3 +--
 2 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/src/ChangeLog b/src/ChangeLog
index 141b31f..1e612bf 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,8 @@
+2014-12-16  Mark Wielaard  <mjw@redhat.com>
+
+	* elfcmp.c (compare_Elf32_Word): Make sure (unsigned) Elf32_Word
+	difference doesn't wrap around before returning as int.
+
 2014-12-11  Mark Wielaard  <mjw@redhat.com>
 
 	* readelf.c (print_debug_exception_table): Check TType base offset
diff --git a/src/elfcmp.c b/src/elfcmp.c
index c420019..d1008b3 100644
--- a/src/elfcmp.c
+++ b/src/elfcmp.c
@@ -811,8 +811,7 @@ compare_Elf32_Word (const void *p1, const void *p2)
 {
   const Elf32_Word *w1 = p1;
   const Elf32_Word *w2 = p2;
-  assert (sizeof (int) >= sizeof (*w1));
-  return (int) *w1 - (int) *w2;
+  return *w1 < *w2 ? -1 : *w1 > *w2 ? 1 : 0;
 }
 
 static int
-- 
1.8.3.1

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Mark Wielaard]

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

On Tue, 2014-12-16 at 09:15 -0800, Josh Stone wrote:
> > Proposed fix attached.
> 
> Looks good.

Thanks. Pushed to master.

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Josh Stone]

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

On 12/16/2014 02:10 AM, Mark Wielaard wrote:
>> I think src/elfcmp.c compare_Elf32_Word() is also wrong, as big u32
>> values could wrap int subtraction.  I didn't find any others.
> 
> Ah, missed that Elf32_Word is unsigned. There is an assert that makes
> sure it is at least as wide as an int, but that isn't enough indeed.

Oh actually, unsigned is a red herring.  Even cmp(INT_MIN, 1) will get
the wrong answer if you use subtraction.  Or cmp(0, INT_MIN), or many
more.  Any time the span can be more than INT_MAX, it's a problem.
Maybe even more so with signed, since overflow is undefined!

> Proposed fix attached.

Looks good.

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Josh Stone]

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

On 12/13/2014 03:18 PM, Mark Wielaard wrote:
> On Thu, Dec 11, 2014 at 05:34:06PM -0800, Josh Stone wrote:
>> BTW, I want to point out this change in compare_lines:
>>
>>> -  return (*p1)->addr - (*p2)->addr;
>> [...]
>>> +  if (line1->addr != line2->addr)
>>> +    return (line1->addr < line2->addr) ? -1 : 1;
>>
>> Since addr is 64-bit unsigned, and comparison functions return int, it
>> is possible for the difference to be so large that it wraps around.  You
>> only need INT_MAX or more -- which probably doesn't happen often in ELF
>> files, but it's plausible.
>>
>> It might be worth auditing other qsort/tsearch comparison functions for
>> similar wrapping possibilities.
> 
> I think you are right. I looked over all compare functions and two didn't
> do as you suggest. The attached patch fixes those. Do that look correct?

Those look good.

I think src/elfcmp.c compare_Elf32_Word() is also wrong, as big u32
values could wrap int subtraction.  I didn't find any others.

Josh

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Mark Wielaard]

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

On Thu, Dec 11, 2014 at 05:34:06PM -0800, Josh Stone wrote:
> BTW, I want to point out this change in compare_lines:
> 
> > -  return (*p1)->addr - (*p2)->addr;
> [...]
> > +  if (line1->addr != line2->addr)
> > +    return (line1->addr < line2->addr) ? -1 : 1;
> 
> Since addr is 64-bit unsigned, and comparison functions return int, it
> is possible for the difference to be so large that it wraps around.  You
> only need INT_MAX or more -- which probably doesn't happen often in ELF
> files, but it's plausible.
> 
> It might be worth auditing other qsort/tsearch comparison functions for
> similar wrapping possibilities.

I think you are right. I looked over all compare functions and two didn't
do as you suggest. The attached patch fixes those. Do that look correct?

Thanks,

Mark

[-- Attachment #2: 0001-Guard-against-64bit-unsigned-wrap-around-in-int-comp.patch --]
[-- Type: text/plain, Size: 2547 bytes --]

>From 2c5e072b193572838cb3bbbc1f0ca7663d088c4a Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mjw@redhat.com>
Date: Sun, 14 Dec 2014 00:09:29 +0100
Subject: [PATCH] Guard against 64bit unsigned wrap around in (int) compare
 functions.

Dwarf_Adrr and Dwarf_Off are 64-bit unsigned, and comparison functions
used in qsort or tfind return int, it is possible for the difference to
be so large that it wraps around. Make sure to just return -1, 0 or 1
in compare_aranges and compare_cukey.

Signed-off-by: Mark Wielaard <mjw@redhat.com>
---
 libdw/ChangeLog          | 5 +++++
 libdw/dwarf_getaranges.c | 4 +++-
 libdwfl/ChangeLog        | 5 +++++
 libdwfl/cu.c             | 4 +++-
 4 files changed, 16 insertions(+), 2 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 2fe5454..bae50a3 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,8 @@
+2014-12-13  Mark Wielaard  <mjw@redhat.com>
+
+	* dwarf_getaranges.c (compare_aranges): Make sure Dwarf_Addr
+	difference doesn't wrap around before returning as int.
+
 2014-12-12  Mark Wielaard  <mjw@redhat.com>
 
 	* libdwP.h (struct Dwarf): Add fake_loc_cu.
diff --git a/libdw/dwarf_getaranges.c b/libdw/dwarf_getaranges.c
index 20ac7ec..4953af5 100644
--- a/libdw/dwarf_getaranges.c
+++ b/libdw/dwarf_getaranges.c
@@ -48,7 +48,9 @@ compare_aranges (const void *a, const void *b)
 {
   struct arangelist *const *p1 = a, *const *p2 = b;
   struct arangelist *l1 = *p1, *l2 = *p2;
-  return l1->arange.addr - l2->arange.addr;
+  if (l1->arange.addr != l2->arange.addr)
+    return (l1->arange.addr < l2->arange.addr) ? -1 : 1;
+  return 0;
 }
 
 int
diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index 99d555f..aa188a7 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,5 +1,10 @@
 2014-12-13  Mark Wielaard  <mjw@redhat.com>
 
+	* cu.c (cudie_offset): Make sure Dwarf_Off difference doesn't
+	wrap around before returning as int.
+
+2014-12-13  Mark Wielaard  <mjw@redhat.com>
+
 	* dwfl_module_getdwarf.c (find_dynsym): elf_getdata_rawchunk takes
 	a size_t, make sure it doesn't overflow.
 
diff --git a/libdwfl/cu.c b/libdwfl/cu.c
index 40b0201..5ce531b 100644
--- a/libdwfl/cu.c
+++ b/libdwfl/cu.c
@@ -162,7 +162,9 @@ cudie_offset (const struct dwfl_cu *cu)
 static int
 compare_cukey (const void *a, const void *b)
 {
-  return cudie_offset (a) - cudie_offset (b);
+  Dwarf_Off a_off = cudie_offset (a);
+  Dwarf_Off b_off = cudie_offset (b);
+  return (a_off < b_off) ? -1 : ((a_off > b_off) ? 1 : 0);
 }
 
 /* Intern the CU if necessary.  */
-- 
2.1.0

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Mark Wielaard]

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

On Thu, Dec 11, 2014 at 05:23:35PM -0800, Josh Stone wrote:
> This adds a sequence number to the linked-list entries, so the original
> order can break ties in sorting, making this a stable sort.
> 
> +2014-12-11  Josh Stone  <jistone@redhat.com>
> +
> +	* dwarf_getsrclines.c (struct linelist): Add sequence.
> +	(compare_lines): Take linelists, and break ties by sequence.
> +	(read_srclines): Use linelists for sorting.
> +	(read_srclines::add_new_line): Set sequence.

Looks good.

Thanks,

Mark

Re: [PATCH 1/3] libdw: Make srclines use a stable sort

[Josh Stone]

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

BTW, I want to point out this change in compare_lines:

> -  return (*p1)->addr - (*p2)->addr;
[...]
> +  if (line1->addr != line2->addr)
> +    return (line1->addr < line2->addr) ? -1 : 1;

Since addr is 64-bit unsigned, and comparison functions return int, it
is possible for the difference to be so large that it wraps around.  You
only need INT_MAX or more -- which probably doesn't happen often in ELF
files, but it's plausible.

It might be worth auditing other qsort/tsearch comparison functions for
similar wrapping possibilities.

[PATCH 1/3] libdw: Make srclines use a stable sort

[Josh Stone]

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

This adds a sequence number to the linked-list entries, so the original
order can break ties in sorting, making this a stable sort.

Signed-off-by: Josh Stone <jistone@redhat.com>
---
 libdw/ChangeLog           |  7 +++++++
 libdw/dwarf_getsrclines.c | 52 ++++++++++++++++++++++++++++-------------------
 2 files changed, 38 insertions(+), 21 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 69592a71df89..5bf1ebc03e33 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,10 @@
+2014-12-11  Josh Stone  <jistone@redhat.com>
+
+	* dwarf_getsrclines.c (struct linelist): Add sequence.
+	(compare_lines): Take linelists, and break ties by sequence.
+	(read_srclines): Use linelists for sorting.
+	(read_srclines::add_new_line): Set sequence.
+
 2014-12-10  Josh Stone  <jistone@redhat.com>
 
 	* libdwP.h (Dwarf_CU): Add startp and endp boundaries.
diff --git a/libdw/dwarf_getsrclines.c b/libdw/dwarf_getsrclines.c
index d503748523e3..3e3ee5582193 100644
--- a/libdw/dwarf_getsrclines.c
+++ b/libdw/dwarf_getsrclines.c
@@ -50,6 +50,7 @@ struct linelist
 {
   Dwarf_Line line;
   struct linelist *next;
+  size_t sequence;
 };
 
 
@@ -57,14 +58,24 @@ struct linelist
 static int
 compare_lines (const void *a, const void *b)
 {
-  Dwarf_Line *const *p1 = a;
-  Dwarf_Line *const *p2 = b;
-
-  if ((*p1)->addr == (*p2)->addr)
-    /* An end_sequence marker precedes a normal record at the same address.  */
-    return (*p2)->end_sequence - (*p1)->end_sequence;
-
-  return (*p1)->addr - (*p2)->addr;
+  struct linelist *const *p1 = a;
+  struct linelist *const *p2 = b;
+  struct linelist *list1 = *p1;
+  struct linelist *list2 = *p2;
+  Dwarf_Line *line1 = &list1->line;
+  Dwarf_Line *line2 = &list2->line;
+
+  if (line1->addr != line2->addr)
+    return (line1->addr < line2->addr) ? -1 : 1;
+
+  /* An end_sequence marker precedes a normal record at the same address.  */
+  if (line1->end_sequence != line2->end_sequence)
+    return line2->end_sequence - line1->end_sequence;
+
+  /* Otherwise, the linelist sequence maintains a stable sort.  */
+  return (list1->sequence < list2->sequence) ? -1
+    : (list1->sequence > list2->sequence) ? 1
+    : 0;
 }
 
 static int
@@ -76,7 +87,7 @@ read_srclines (Dwarf *dbg,
   int res = -1;
 
   struct linelist *linelist = NULL;
-  unsigned int nlinelist = 0;
+  size_t nlinelist = 0;
 
   /* If there are a large number of lines don't blow up the stack.
      Keep track of the last malloced linelist record and free them
@@ -321,6 +332,7 @@ read_srclines (Dwarf *dbg,
   inline bool add_new_line (struct linelist *new_line, bool end_sequence)
   {
     new_line->next = linelist;
+    new_line->sequence = nlinelist;
     linelist = new_line;
     ++nlinelist;
 
@@ -660,24 +672,22 @@ read_srclines (Dwarf *dbg,
   if (filesp != NULL)
     *filesp = files;
 
-  void *buf = libdw_alloc (dbg, Dwarf_Lines, (sizeof (Dwarf_Lines)
-					      + (sizeof (Dwarf_Line)
-						 * nlinelist)), 1);
+  size_t buf_size = (sizeof (Dwarf_Lines) + (sizeof (Dwarf_Line) * nlinelist));
+  void *buf = libdw_alloc (dbg, Dwarf_Lines, buf_size, 1);
 
   /* First use the buffer for the pointers, and sort the entries.
      We'll write the pointers in the end of the buffer, and then
      copy into the buffer from the beginning so the overlap works.  */
-  assert (sizeof (Dwarf_Line) >= sizeof (Dwarf_Line *));
-  Dwarf_Line **sortlines = (buf + sizeof (Dwarf_Lines)
-			    + ((sizeof (Dwarf_Line)
-				- sizeof (Dwarf_Line *)) * nlinelist));
+  assert (sizeof (Dwarf_Line) >= sizeof (struct linelist *));
+  struct linelist **sortlines = (buf + buf_size
+				 - sizeof (struct linelist **) * nlinelist);
 
   /* The list is in LIFO order and usually they come in clumps with
      ascending addresses.  So fill from the back to probably start with
      runs already in order before we sort.  */
-  for (unsigned int i = nlinelist; i-- > 0; )
+  for (size_t i = nlinelist; i-- > 0; )
     {
-      sortlines[i] = &linelist->line;
+      sortlines[i] = linelist;
       linelist = linelist->next;
     }
   assert (linelist == NULL);
@@ -690,9 +700,9 @@ read_srclines (Dwarf *dbg,
      of SORTLINES by the time we're reading the later ones.  */
   Dwarf_Lines *lines = buf;
   lines->nlines = nlinelist;
-  for (unsigned int i = 0; i < nlinelist; ++i)
+  for (size_t i = 0; i < nlinelist; ++i)
     {
-      lines->info[i] = *sortlines[i];
+      lines->info[i] = sortlines[i]->line;
       lines->info[i].files = files;
     }
 
@@ -711,7 +721,7 @@ read_srclines (Dwarf *dbg,
 
  out:
   /* Free malloced line records, if any.  */
-  for (unsigned int i = MAX_STACK_ALLOC; i < nlinelist; i++)
+  for (size_t i = MAX_STACK_ALLOC; i < nlinelist; i++)
     {
       struct linelist *ll = malloc_linelist->next;
       free (malloc_linelist);
-- 
2.1.0