[PATCH] Fix a bug of addrmap

[PATCH] Fix a bug of addrmap

[Jie Zhang]

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

Hi,

I encountered a problem when trying CVS HEAD gdb with gcc-4.1, which has
no .debug_ranges support. Below is the test case:

$ cat main.c
int main ()
{
    return 0;
}

extern void __attribute__ ((__section__ (".init.text"))) foo_init (void);
void foo_init ()
{
    return;
}

$ cat foo.c
int foo ()
{
    return 0;
}

$ gcc-4.1 -o test main.c foo.c -g

CVS HEAD gdb cannot show the source line of foo.
$ gdb test
GNU gdb (GDB) 6.8.50.20081020-cvs
[snip]
(gdb) b foo
Breakpoint 1 at 0x400458

while gdb-6.8 can
$ gdb test
GNU gdb 6.8
[snip]
(gdb) b foo
Breakpoint 1 at 0x400458: file foo.c, line 3.

Since gcc-4.1 does not generate .debug_ranges, gdb tries to create
addrmap from low_pc and high_pc. When creating mutable addrmap, the
address range of main.c is treated as contiguous, e.g. [0x400448,
0x40053e], while foo.c is e.g. [0x400454, 0x40045f], which is embedded
in the former. In current gdb, the value of the start and end
transitions for foo.c are initialized as same as the value of the start
one for main.c. Then later in addrmap_mutable_set_empty, those
transitions are removed.

This patch should fix this case. Is it OK?


Regards,
Jie


[-- Attachment #2: gdb-addrmap-embedded-range.diff --]
[-- Type: text/x-patch, Size: 2480 bytes --]


	* addrmap.c (force_transition): Add new argument start.
	(addrmap_mutable_set_empty): Establish the end transition
	before the start transition.

Index: addrmap.c
===================================================================
RCS file: /cvs/src/src/gdb/addrmap.c,v
retrieving revision 1.4
diff -u -p -r1.4 addrmap.c
--- addrmap.c	1 Jan 2008 22:53:09 -0000	1.4
+++ addrmap.c	21 Oct 2008 03:42:19 -0000
@@ -291,18 +291,27 @@ addrmap_splay_tree_insert (struct addrma
 
 /* Without changing the mapping of any address, ensure that there is a
    tree node at ADDR, even if it would represent a "transition" from
-   one value to the same value.  */
+   one value to the same value.  If START is non-zero, this is the
+   start transition of the address range.  Otherwise, it's the end
+   transition.  */
 static void
-force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
+force_transition (struct addrmap_mutable *this, CORE_ADDR addr, int start)
 {
   splay_tree_node n
     = addrmap_splay_tree_lookup (this, addr);
 
   if (! n)
     {
-      n = addrmap_splay_tree_predecessor (this, addr);
-      addrmap_splay_tree_insert (this, addr,
-                                 n ? addrmap_node_value (n) : NULL);
+      void *value;
+
+      if (start)
+	value = NULL;
+      else
+	{
+	  n = addrmap_splay_tree_predecessor (this, addr);
+	  value = n ? addrmap_node_value (n) : NULL;
+	}
+      addrmap_splay_tree_insert (this, addr, value);
     }
 }
 
@@ -328,10 +337,16 @@ addrmap_mutable_set_empty (struct addrma
      - First pass: change all NULL regions to OBJ.
      - Second pass: remove any unnecessary transitions.  */
 
-  /* Establish transitions at the start and end.  */
-  force_transition (map, start);
+  /* Establish transitions at the start and end.  The end transition
+     is established first such that its value will be initialized as
+     same as the value of its predecessor.  The value of the start
+     transition will always be initialized to NULL.  With this
+     establishing order, the value of these transitions will be set
+     properly later even if the given address range is embedded in
+     another address range.  */
   if (end_inclusive < CORE_ADDR_MAX)
-    force_transition (map, end_inclusive + 1);
+    force_transition (map, end_inclusive + 1, 0);
+  force_transition (map, start, 1);
 
   /* Walk the area, changing all NULL regions to OBJ.  */
   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);

PING: [PATCH] Fix a bug of addrmap

[Jie Zhang]

Hi,

Could someone give a review on this patch:

http://sourceware.org/ml/gdb-patches/2008-10/msg00503.html


Thanks,
Jie

Re: PING: [PATCH] Fix a bug of addrmap

[Tom Tromey]

>>>>> "Jie" == Jie Zhang <jie.zhang@analog.com> writes:

Jie> Could someone give a review on this patch:
Jie> http://sourceware.org/ml/gdb-patches/2008-10/msg00503.html

I was curious about this patch so I took a look.

Since addrmap is a relatively self-contained data structure, I figured
it was a good candidate for a unit test.  So, I wrote a test case
based on your original report.

I think the test case is pretty clear.  And sure enough, it fails
before your patch and it passes after your pass.  So, on that basis I
would support checking in your patch.  However, please note I cannot
approve it.

I think it also worth checking in the appended.  If we ever find
another addrmap bug, we could extend the unit test.  Please review
this, thanks.

Tom

2008-11-25  Tom Tromey  <tromey@redhat.com>

	* Makefile.in (test-addrmap.o): New target.
	(test-addrmap): Likewise.
	(clean mostlyclean): Remove test-addrmap.
	* addrmap.c (xfree): New function.
	(internal_error): Likewise.
	(test_inclusion): Likewise.
	(main): Likewise.

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 5432c88..8d947d2 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -968,6 +968,15 @@ test-cp-name-parser$(EXEEXT): test-cp-name-parser.o $(LIBIBERTY)
 	$(CC_LD) $(INTERNAL_LDFLAGS) -o test-cp-name-parser$(EXEEXT) \
 		test-cp-name-parser.o $(LIBIBERTY)
 
+# Addrmap has unit tests which can be run standalone.
+test-addrmap.o: addrmap.c
+	$(COMPILE) -DADDRMAP_UNIT_TEST $(srcdir)/addrmap.c
+	$(POSTCOMPILE)
+
+test-addrmap: test-addrmap.o $(LIBIBERTY)
+	$(CC_LD) $(INTERNAL_LDFLAGS) -o test-addrmap$(EXEEXT) \
+		test-addrmap.o $(LIBIBERTY)
+
 # We do this by grepping through sources.  If that turns out to be too slow,
 # maybe we could just require every .o file to have an initialization routine
 # of a given name (top.o -> _initialize_top, etc.).
@@ -1117,7 +1126,7 @@ clean mostlyclean: $(CONFIG_CLEAN)
 	rm -f init.c version.c
 	rm -f gdb$(EXEEXT) core make.log
 	rm -f gdb[0-9]$(EXEEXT)
-	rm -f test-cp-name-parser$(EXEEXT)
+	rm -f test-cp-name-parser$(EXEEXT) test-addrmap$(EXEEXT)
 	rm -f xml-builtin.c stamp-xml
 
 .PHONY: clean-tui
diff --git a/gdb/addrmap.c b/gdb/addrmap.c
index 68832e9..a73a945 100644
--- a/gdb/addrmap.c
+++ b/gdb/addrmap.c
@@ -541,3 +541,67 @@ _initialize_addrmap (void)
   gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
   gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
 }
+
+\f
+/* Unit testing.  */
+
+#ifdef ADDRMAP_UNIT_TEST
+
+/* When this file is built as a standalone program, xmalloc comes from
+   libiberty --- in which case we have to provide xfree ourselves.  */
+
+void
+xfree (void *ptr)
+{
+  free (ptr);
+}
+
+/* Likewise for internal_error.  */
+NORETURN void
+internal_error (const char *file, int line, const char *string, ...)
+{
+  /* The user will have to debug this anyway.  */
+  exit (1);
+}
+
+/* A test case reported to the list.  Return 1 if ok, 0 on
+   failure.  */
+static int
+test_inclusion (void)
+{
+  struct obstack alloc;
+  struct addrmap *map;
+  char *fooc = "foo.c";
+  char *mainc = "main.c";
+  int result;
+
+  obstack_init (&alloc);
+  map = addrmap_create_mutable (&alloc);
+
+  addrmap_set_empty (map, 0x400448, 0x40053e, mainc);
+  addrmap_set_empty (map, 0x400454, 0x40045f, fooc);
+
+  map = addrmap_create_fixed (map, &alloc);
+
+  result = (addrmap_find (map, 0x0) == NULL
+	    && addrmap_find (map, 0x400447) == NULL
+	    && addrmap_find (map, 0x400448) == mainc
+	    && addrmap_find (map, 0x400453) == mainc
+	    && addrmap_find (map, 0x400454) == fooc
+	    && addrmap_find (map, 0x40045f) == fooc
+	    && addrmap_find (map, 0x400460) == mainc
+	    && addrmap_find (map, 0x40053e) == mainc
+	    && addrmap_find (map, 0x40053f) == NULL);
+
+  obstack_free (&alloc, 0);
+
+  return result;
+}
+
+int
+main (int argc, char **argv)
+{
+  return !test_inclusion ();
+}
+
+#endif /* ADDRMAP_UNIT_TEST */

Re: PING: [PATCH] Fix a bug of addrmap

[Joel Brobecker]

> Jie> Could someone give a review on this patch:
> Jie> http://sourceware.org/ml/gdb-patches/2008-10/msg00503.html
> 
> I was curious about this patch so I took a look.

I took a quick look too, but not being familiar with this part
of the code, I had to postpone the review until I find enough
time to familiarize myself with the code.

Did you familiarize yourself with the code that you'd say that
the patch sounds good to you? If this is the case, I'm quite
happy to trust your judgement.

> Since addrmap is a relatively self-contained data structure, I figured
> it was a good candidate for a unit test.  So, I wrote a test case
> based on your original report.

Yay! :)

> 2008-11-25  Tom Tromey  <tromey@redhat.com>
> 
> 	* Makefile.in (test-addrmap.o): New target.
> 	(test-addrmap): Likewise.
> 	(clean mostlyclean): Remove test-addrmap.
> 	* addrmap.c (xfree): New function.
> 	(internal_error): Likewise.
> 	(test_inclusion): Likewise.
> 	(main): Likewise.

The one comment that I have about this is that it's not automatically
run when we run the testsuite. It would be really nice if they were.

It's not the first time that we have unit-testing like this.
For instance, check we have unit tests for observers, or xfullpath.
Traditionally, they have been implemented inside testsuite/gdb.gdb.
The current solution is not very elegant, in my opinion, as what we
did was debugging GDB and call some functions inside GDB.

How about, we add a testcase that "debugs" test-addrmap by simply
running it to completion and checking its output (including the
fact that it exited normally (meaning error code returned is zero)?

> +void
> +xfree (void *ptr)
> +{
> +  free (ptr);
> +}
> +
> +/* Likewise for internal_error.  */
> +NORETURN void
> +internal_error (const char *file, int line, const char *string, ...)
> +{
> +  /* The user will have to debug this anyway.  */
> +  exit (1);
> +}

I really like the idea of compiling this file as a standalone program,
and I hope that we'll be able to extend the use of this approach in
the future.  If we do, it might be worth putting these in a unit-testing
archive... (just thinking aloud, let's not act on it until it becomes
useful).

-- 
Joel

Re: PING: [PATCH] Fix a bug of addrmap

[Tom Tromey]

>>>>> "Joel" == Joel Brobecker <brobecker@adacore.com> writes:

Joel> Did you familiarize yourself with the code that you'd say that
Joel> the patch sounds good to you? If this is the case, I'm quite
Joel> happy to trust your judgement.

Not really, I'm afraid.  I just wanted to make sure I understood the
bug report.

I still don't understand why the fix is to modify force_transition and
not addrmap_mutable_set_empty.

Joel> The one comment that I have about this is that it's not automatically
Joel> run when we run the testsuite. It would be really nice if they were.

Joel> It's not the first time that we have unit-testing like this.
Joel> For instance, check we have unit tests for observers, or xfullpath.
Joel> Traditionally, they have been implemented inside testsuite/gdb.gdb.
Joel> The current solution is not very elegant, in my opinion, as what we
Joel> did was debugging GDB and call some functions inside GDB.

Ugh.  I definitely don't want to do that.

FWIW, in this case I was just following test-cp-name-parser.

Joel> How about, we add a testcase that "debugs" test-addrmap by simply
Joel> running it to completion and checking its output (including the
Joel> fact that it exited normally (meaning error code returned is zero)?

I will look into it.

Tom

Re: PING: [PATCH] Fix a bug of addrmap

[Daniel Jacobowitz]

On Tue, Nov 25, 2008 at 09:46:13AM -0800, Joel Brobecker wrote:
> The one comment that I have about this is that it's not automatically
> run when we run the testsuite. It would be really nice if they were.
> 
> It's not the first time that we have unit-testing like this.
> For instance, check we have unit tests for observers, or xfullpath.
> Traditionally, they have been implemented inside testsuite/gdb.gdb.
> The current solution is not very elegant, in my opinion, as what we
> did was debugging GDB and call some functions inside GDB.
> 
> How about, we add a testcase that "debugs" test-addrmap by simply
> running it to completion and checking its output (including the
> fact that it exited normally (meaning error code returned is zero)?

Could we move this test into a separate file, in gdb.gdb/, and arrange
for it to be linked with libgdb.a?

-- 
Daniel Jacobowitz
CodeSourcery

Re: PING: [PATCH] Fix a bug of addrmap

[Daniel Jacobowitz]

On Tue, Nov 25, 2008 at 12:59:55PM -0500, Daniel Jacobowitz wrote:
> Could we move this test into a separate file, in gdb.gdb/, and arrange
> for it to be linked with libgdb.a?

... which would work for test-cp-name-parser, too.

-- 
Daniel Jacobowitz
CodeSourcery

Re: PING: [PATCH] Fix a bug of addrmap

[Tom Tromey]

>>>>> "Joel" == Joel Brobecker <brobecker@adacore.com> writes:

Joel> Did you familiarize yourself with the code that you'd say that
Joel> the patch sounds good to you?

I looked at it again today.

I re-read the contract for this function, and it seems pretty clear
that the current behavior is intended:

/* In the mutable address map MAP, associate the addresses from START
   to END_INCLUSIVE that are currently associated with NULL with OBJ
   instead.  Addresses mapped to an object other than NULL are left
   unchanged.

In particular, "currently associated with NULL" is the key.

My understanding now is that this data structure is designed to be
built bottom-up.  So, I think that this is a bug in the caller, and
that the test I wrote is actually not correct.

Of course, it would be ok to change addrmap's contract.  But, if we
want to do this then I think we would need more tests covering other
corner cases.

BTW, addrmap is nice code.  It has all the hallmarks of the Blandy
style.

Tom

Re: PING: [PATCH] Fix a bug of addrmap

[Joel Brobecker]

> Joel> Did you familiarize yourself with the code that you'd say that
> Joel> the patch sounds good to you?
> 
> I looked at it again today.

Me too (finally!!! woohoo!)

> I re-read the contract for this function, and it seems pretty clear
> that the current behavior is intended:
> 
> /* In the mutable address map MAP, associate the addresses from START
>    to END_INCLUSIVE that are currently associated with NULL with OBJ
>    instead.  Addresses mapped to an object other than NULL are left
>    unchanged.
> 
> In particular, "currently associated with NULL" is the key.
> 
> My understanding now is that this data structure is designed to be
> built bottom-up.

Right, and the comment explains why just below. Also, I found this,
which I think confirms your understanding:

/* Record that the range of addresses from START to END_INCLUSIVE
   (inclusive, like it says) belongs to BLOCK.  BLOCK's start and end
   addresses must be set already.  You must apply this function to all
   BLOCK's children before applying it to BLOCK.

(buildsym.c:record_block_range)

> So, I think that this is a bug in the caller, and
> that the test I wrote is actually not correct.

It very much looks like it, yes. But it also looks like it wasn't
designed to handle the case of overlapping or nested sym files
address ranges :-(.

I've been thinking about this for the last hour now, and I'm not sure
how to store the information in the addrmap in a way that would solve
the problem.

I don't think that the solution provided here is satisfactory, because
it leads to different solutions depending on the order the psymtabs
are read. Consider for instance:

  file a.c is [0x10 .. 0x30]
  file b.c is [0x20 .. 0x40]

If a.c is processed first, then we get an addrmap that says:
  [0x10 .. 0x20[ = a.c
  [0x20 .. 0x30] = b.c

On the other hand, if b.c is processed first, we get:
  [0x10 .. 0x20[ = a.c
  [0x20 .. 0x40] = b.c

(I might have screwed up the inclusion/exclusion for the bounds,
it's getting really late here). I suspect the above would happen
if we had added a function inside foo.c also pushed to the .text.init
section.

Before using addrmaps, I think we were getting it right by scanning all
psymtabs and trying to get the "best" one, with some heuristic as to what
the best one was, but that was causing us other source of problems.
But this isn't possible in this case since we don't have enough info
in the objfile addrmap.

With all this being said, I think this is as far as I am willing to go
by myself for now. I don't have the feeling that the described problem
is problematic enough to mandate a non-trivial effort. Perhaps I'm
wrong? In any case, it seems easy enough to work around the problem
in the particular example, by putting the routine forced to a different
section into a different file.

> BTW, addrmap is nice code.  It has all the hallmarks of the Blandy
> style.

Very nice indeed...

-- 
Joel