Re: [PATCH 2/3] libdwfl: Search for the last matching address in lines

Re: [PATCH 2/3] libdwfl: Search for the last matching address in lines

[Mark Wielaard]

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

On Thu, Dec 11, 2014 at 05:23:36PM -0800, Josh Stone wrote:
> Now that libdw's srclines use a stable sort, we can reliably choose the
> *last* matching line record for a given address, which should be the
> innermost where inlines are concerned.
>
> +2014-12-11  Josh Stone  <jistone@redhat.com>
> +
> +	* dwfl_module_getsrc.c (dwfl_module_getsrc): Return the *last* line
> +	record <= addr, rather than returning immediately on matches.
> [...]
> +	  size_t l = 0, u = nlines - 1;
> +	  while (l < u)
> +	    {
> +	      size_t idx = u - (u - l) / 2;
> +	      Dwarf_Line *line = &lines->info[idx];
> +	      if (addr < line->addr)
> +		u = idx - 1;
> +	      else if (addr >= line->addr)
> +		l = idx;
> +	    }

That second check (addr >= line->addr) is redundent isn't it?
The compiler probably sees the same and will remove it, but it might be
cleaner if it is just not there. Unless it is needed for some reason
I am missing.

This is fine, with or without that change (but please explain it then).

Thanks,

Mark

Re: [PATCH 2/3] libdwfl: Search for the last matching address in lines

[Josh Stone]

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

On 12/13/2014 11:42 AM, Mark Wielaard wrote:
> On Thu, Dec 11, 2014 at 05:23:36PM -0800, Josh Stone wrote:
>> Now that libdw's srclines use a stable sort, we can reliably choose the
>> *last* matching line record for a given address, which should be the
>> innermost where inlines are concerned.
>>
>> +2014-12-11  Josh Stone  <jistone@redhat.com>
>> +
>> +	* dwfl_module_getsrc.c (dwfl_module_getsrc): Return the *last* line
>> +	record <= addr, rather than returning immediately on matches.
>> [...]
>> +	  size_t l = 0, u = nlines - 1;
>> +	  while (l < u)
>> +	    {
>> +	      size_t idx = u - (u - l) / 2;
>> +	      Dwarf_Line *line = &lines->info[idx];
>> +	      if (addr < line->addr)
>> +		u = idx - 1;
>> +	      else if (addr >= line->addr)
>> +		l = idx;
>> +	    }
> 
> That second check (addr >= line->addr) is redundent isn't it?
> The compiler probably sees the same and will remove it, but it might be
> cleaner if it is just not there. Unless it is needed for some reason
> I am missing.

Ah, yes, of course.  I squashed the old else (==) into that branch, but
somehow didn't think about that becoming a plain else itself. :)

> This is fine, with or without that change (but please explain it then).

I'll simplify it as you suggest.

Thanks,
Josh

[PATCH 2/3] libdwfl: Search for the last matching address in lines

[Josh Stone]

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

Now that libdw's srclines use a stable sort, we can reliably choose the
*last* matching line record for a given address, which should be the
innermost where inlines are concerned.

Signed-off-by: Josh Stone <jistone@redhat.com>
---
 libdwfl/ChangeLog            |  5 +++++
 libdwfl/dwfl_module_getsrc.c | 51 +++++++++++++++++++++++---------------------
 2 files changed, 32 insertions(+), 24 deletions(-)

diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index b882f2049ca0..7b0ea15f013f 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,3 +1,8 @@
+2014-12-11  Josh Stone  <jistone@redhat.com>
+
+	* dwfl_module_getsrc.c (dwfl_module_getsrc): Return the *last* line
+	record <= addr, rather than returning immediately on matches.
+
 2014-12-07  Mark Wielaard  <mjw@redhat.com>
 
 	* relocate.c (relocate_section): Sanity check section overlap against
diff --git a/libdwfl/dwfl_module_getsrc.c b/libdwfl/dwfl_module_getsrc.c
index cf8dc0fc2d0a..41cf9753313e 100644
--- a/libdwfl/dwfl_module_getsrc.c
+++ b/libdwfl/dwfl_module_getsrc.c
@@ -1,5 +1,5 @@
 /* Find source location for PC address in module.
-   Copyright (C) 2005, 2008 Red Hat, Inc.
+   Copyright (C) 2005, 2008, 2014 Red Hat, Inc.
    This file is part of elfutils.
 
    This file is free software; you can redistribute it and/or modify
@@ -42,32 +42,35 @@ dwfl_module_getsrc (Dwfl_Module *mod, Dwarf_Addr addr)
     error = __libdwfl_cu_getsrclines (cu);
   if (likely (error == DWFL_E_NOERROR))
     {
-      /* Now we look at the module-relative address.  */
-      addr -= bias;
-
-      /* The lines are sorted by address, so we can use binary search.  */
-      size_t l = 0, u = cu->die.cu->lines->nlines;
-      while (l < u)
+      Dwarf_Lines *lines = cu->die.cu->lines;
+      size_t nlines = lines->nlines;
+      if (nlines > 0)
 	{
-	  size_t idx = (l + u) / 2;
-	  if (addr < cu->die.cu->lines->info[idx].addr)
-	    u = idx;
-	  else if (addr > cu->die.cu->lines->info[idx].addr)
-	    l = idx + 1;
-	  else
-	    return &cu->lines->idx[idx];
-	}
+	  /* This is guaranteed for us by libdw read_srclines.  */
+	  assert(lines->info[nlines - 1].end_sequence);
 
-      if (cu->die.cu->lines->nlines > 0)
-	assert (cu->die.cu->lines->info
-		[cu->die.cu->lines->nlines - 1].end_sequence);
+	  /* Now we look at the module-relative address.  */
+	  addr -= bias;
 
-      /* If none were equal, the closest one below is what we want.
-	 We never want the last one, because it's the end-sequence
-	 marker with an address at the high bound of the CU's code.  */
-      if (u > 0 && u < cu->die.cu->lines->nlines
-	  && addr > cu->die.cu->lines->info[u - 1].addr)
-	return &cu->lines->idx[u - 1];
+	  /* The lines are sorted by address, so we can use binary search.  */
+	  size_t l = 0, u = nlines - 1;
+	  while (l < u)
+	    {
+	      size_t idx = u - (u - l) / 2;
+	      Dwarf_Line *line = &lines->info[idx];
+	      if (addr < line->addr)
+		u = idx - 1;
+	      else if (addr >= line->addr)
+		l = idx;
+	    }
+
+	  /* The last line which is less than or equal to addr is what we want,
+	     except with an end_sequence which can only be strictly equal.  */
+	  Dwarf_Line *line = &lines->info[l];
+	  if (line->addr == addr
+	      || (! line->end_sequence && line->addr < addr))
+	    return &cu->lines->idx[l];
+	}
 
       error = DWFL_E_ADDR_OUTOFRANGE;
     }
-- 
2.1.0