[PATCH] Fix CK_BAD propagation for --odr

[PATCH] Fix CK_BAD propagation for --odr

[Tom de Vries]

Hi,

With the reproducer from PR26252 we get:
...
$ dwz -m 3 --odr 1 2
dwz: 1: DWARF compression not beneficial - old size 317760 new size 317760
dwz: dwz.c:12431: write_die: \
  Assertion `value && refdcu->cu_kind != CU_ALT' failed.
Aborted (core dumped)
...

The assertion fails when writing out the contribution of file 2 to the
multifile.

It's trying to write out a copy of this DIE:
...
 <3><9f3e>: Abbrev Number: 149 (DW_TAG_subprogram)
    <9f40>   DW_AT_name        :
             _M_access<ydotool::Tool::ToolManager::ScanPath(const string&)::\
	       <lambda(const string&, dirent*)> >
    <9f44>   DW_AT_decl_file   : 11
    <9f45>   DW_AT_decl_line   : 92
    <9f46>   DW_AT_decl_column : 7
    <9f47>   DW_AT_type        : <0x1a2a5>
    <9f4b>   DW_AT_declaration : 1
    <9f4b>   DW_AT_object_pointer: <0x9f5c>
    <9f4f>   DW_AT_sibling     : <0x9f62>
...
and specifically, for the DW_AT_type attribute it attempts to write out the
reference to the copy of the DIE at 0x1a2a5:
...
 <1><1a2a5>: Abbrev Number: 9 (DW_TAG_reference_type)
    <1a2a6>   DW_AT_byte_size   : 8
    <1a2a7>   DW_AT_type        : <0x27cd9>
...

There is no copy of that DIE, because it has a bad checksum:
...
  1a2a5 X d27b2f2a d27b2f2a  reference_type (type: 27cd9 structure_type)
...
which means that its toplevel DIE 0x9edc:
...
<2><9edc>: Abbrev Number: 182 (DW_TAG_union_type)
    <9ede>   DW_AT_name        : _Any_data
...
should also have a bad checksum, but it doesn't:
...
   9edc O 9d6524b4 9d6524b4 _Any_data union_type
...
while without --odr, it does:
...
   9edc X d8f947f3 5100c9e1 _Any_data union_type
...

We can catch the problem of the checksum much earlier, with an assert:
...
 static void
 partition_found_dups (dw_die_ref die, struct obstack *vec)
 {
+  assert (die->die_ck_state == CK_KNOWN);
...
which means we can reproduce with just one file:
...
$ dwz 2 --odr
dwz: dwz.c:7372: partition_found_dups: \
  Assertion `die->die_ck_state == CK_KNOWN' failed.
Aborted (core dumped)
...

The problem is caused by the odr code in checksum_ref_die, which skips
checksum calculation for the children of odr types, with as unintended
side-effect that it break the CK_BAD propagation to toplevel DIEs.

Fix this by making the skipping of the checksum calculation less intrusive.

Also, add the assert in partition_found_dups to catch this earlier and
easier.

Unfortunately, the fix also means that the earlier reported performance
improvement of odr on cc1, of 42.30%:
...
$ ./dwz.master cc1 -o 1 -lnone
$ ./diff.sh cc1 1
.debug_info      red: 44.84%    111527248  61527733
.debug_abbrev    red: 40.28%    1722726  1028968
.debug_str       red: 0%        6609355  6609355
total            red: 42.30%    119859329 69166056
...
to 54.55%:
...
$ ./dwz.master cc1 -o 2 -lnone --odr
$ ./diff.sh cc1 2
.debug_info      red: 57.46%    111527248  47449258
.debug_abbrev    red: 75.08%    1722726  429434
.debug_str       red: 0%        6609355  6609355
total            red: 54.55%    119859329 54488047
...
pretty much disappears:
...
$ ./dwz.fix cc1 -o 3 -lnone --odr
$ ./diff.sh cc1 3
.debug_info      red: 45.44%    111527248  60858640
.debug_abbrev    red: 42.88%    1722726  984084
.debug_str       red: 0%        6609355  6609355
total            red: 42.89%    119859329 68452079
...

Any comments?

Thanks,
- Tom

Fix CK_BAD propagation for --odr

2021-02-16  Tom de Vries  <tdevries@suse.de>

	PR dwz/26252
	* dwz.c (checksum_ref_die): Fix CK_BAD propagation for --odr.
	(partition_found_dups): Add assert.

---
 dwz.c | 44 ++++++++++++++++++++++++++------------------
 1 file changed, 26 insertions(+), 18 deletions(-)

diff --git a/dwz.c b/dwz.c
index 17921f0..faf00d1 100644
--- a/dwz.c
+++ b/dwz.c
@@ -4187,24 +4187,31 @@ checksum_ref_die (dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die,
 	}
     }
 
-  if (!only_hash_name_p
-      && (top_die == NULL || top_die->die_ck_state != CK_BAD))
-    for (child = die->die_child; child; child = child->die_sib)
-      {
-	unsigned int r
-	  = checksum_ref_die (cu,
-			      top_die ? top_die
-			      : child->die_named_namespace
-			      ? NULL : child, child,
-			      second_idx, second_hash);
-	if (top_die == NULL)
-	  assert (r == 0 && obstack_object_size (&ob) == 0);
-
-	if (ret == 0 || (r && r < ret))
-	  ret = r;
-	if (top_die && top_die->die_ck_state == CK_BAD)
-	  break;
-      }
+  if (top_die == NULL || top_die->die_ck_state != CK_BAD)
+    {
+      hashval_t save_checksum = 0;
+      if (top_die)
+	save_checksum = top_die->u.p1.die_ref_hash;
+      for (child = die->die_child; child; child = child->die_sib)
+	{
+	  unsigned int r
+	    = checksum_ref_die (cu,
+				top_die ? top_die
+				: child->die_named_namespace
+				? NULL : child, child,
+				second_idx, second_hash);
+	  if (top_die == NULL)
+	    assert (r == 0 && obstack_object_size (&ob) == 0);
+
+	  if (ret == 0 || (r && r < ret))
+	    ret = r;
+	  if (top_die && top_die->die_ck_state == CK_BAD)
+	    break;
+	}
+      if (top_die
+	  && top_die->die_ck_state != CK_BAD && only_hash_name_p)
+	top_die->u.p1.die_ref_hash = save_checksum;
+    }
 
   if (top_die == die)
     {
@@ -7369,6 +7376,7 @@ partition_cmp (const void *p, const void *q)
 static void
 partition_found_dups (dw_die_ref die, struct obstack *vec)
 {
+  assert (die->die_ck_state == CK_KNOWN);
   obstack_ptr_grow (vec, die);
   if (unlikely (verify_dups_p))
     verify_dups (die, true);

[committed] Add assert in partition_found_dups

[Tom de Vries]

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

[ was: Re: [PATCH] Fix CK_BAD propagation for --odr ]
On 2/16/21 10:11 AM, Tom de Vries wrote:
> We can catch the problem of the checksum much earlier, with an assert:
> ...
>  static void
>  partition_found_dups (dw_die_ref die, struct obstack *vec)
>  {
> +  assert (die->die_ck_state == CK_KNOWN);
> ...

Committed assert for now.

Thanks,
- Tom


[-- Attachment #2: 0001-Add-assert-in-partition_found_dups.patch --]
[-- Type: text/x-patch, Size: 2597 bytes --]

Add assert in partition_found_dups

With the reproducer from PR26252 we get:
...
$ dwz -m 3 --odr 1 2
dwz: 1: DWARF compression not beneficial - old size 317760 new size 317760
dwz: dwz.c:12431: write_die: \
  Assertion `value && refdcu->cu_kind != CU_ALT' failed.
Aborted (core dumped)
...

The assertion fails when writing out the contribution of file 2 to the
multifile.

It's trying to write out a copy of this DIE:
...
 <3><9f3e>: Abbrev Number: 149 (DW_TAG_subprogram)
    <9f40>   DW_AT_name        :
             _M_access<ydotool::Tool::ToolManager::ScanPath(const string&)::\
	       <lambda(const string&, dirent*)> >
    <9f44>   DW_AT_decl_file   : 11
    <9f45>   DW_AT_decl_line   : 92
    <9f46>   DW_AT_decl_column : 7
    <9f47>   DW_AT_type        : <0x1a2a5>
    <9f4b>   DW_AT_declaration : 1
    <9f4b>   DW_AT_object_pointer: <0x9f5c>
    <9f4f>   DW_AT_sibling     : <0x9f62>
...
and specifically, for the DW_AT_type attribute it attempts to write out the
reference to the copy of the DIE at 0x1a2a5:
...
 <1><1a2a5>: Abbrev Number: 9 (DW_TAG_reference_type)
    <1a2a6>   DW_AT_byte_size   : 8
    <1a2a7>   DW_AT_type        : <0x27cd9>
...

There is no copy of that DIE, because it has a bad checksum:
...
  1a2a5 X d27b2f2a d27b2f2a  reference_type (type: 27cd9 structure_type)
...
which means that its toplevel DIE 0x9edc:
...
<2><9edc>: Abbrev Number: 182 (DW_TAG_union_type)
    <9ede>   DW_AT_name        : _Any_data
...
should also have a bad checksum, but it doesn't:
...
   9edc O 9d6524b4 9d6524b4 _Any_data union_type
...
while without --odr, it does:
...
   9edc X d8f947f3 5100c9e1 _Any_data union_type
...

Add an assert partition_found_dups such that we can catch the problem of the
checksum much earlier:
...
 static void
 partition_found_dups (dw_die_ref die, struct obstack *vec)
 {
+  assert (die->die_ck_state == CK_KNOWN);
...
which means we can reproduce with just one file:
...
$ dwz 2 --odr
dwz: dwz.c:7372: partition_found_dups: \
  Assertion `die->die_ck_state == CK_KNOWN' failed.
Aborted (core dumped)
...

2021-02-18  Tom de Vries  <tdevries@suse.de>

	* dwz.c (partition_found_dups): Assert that
	die->die_ck_state == CK_KNOWN.

---
 dwz.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/dwz.c b/dwz.c
index d037e1e..0b751fc 100644
--- a/dwz.c
+++ b/dwz.c
@@ -7393,6 +7393,7 @@ partition_cmp (const void *p, const void *q)
 static void
 partition_found_dups (dw_die_ref die, struct obstack *vec)
 {
+  assert (die->die_ck_state == CK_KNOWN);
   obstack_ptr_grow (vec, die);
   if (unlikely (verify_dups_p))
     verify_dups (die, true);

Re: [PATCH] Fix CK_BAD propagation for --odr

[Tom de Vries]

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

On 2/16/21 10:11 AM, Tom de Vries wrote:
> The problem is caused by the odr code in checksum_ref_die, which skips
> checksum calculation for the children of odr types, with as unintended
> side-effect that it break the CK_BAD propagation to toplevel DIEs.
> 
> Fix this by making the skipping of the checksum calculation less intrusive.
> 
> Also, add the assert in partition_found_dups to catch this earlier and
> easier.
> 
> Unfortunately, the fix also means that the earlier reported performance
> improvement of odr on cc1, of 42.30%:
> ...
> $ ./dwz.master cc1 -o 1 -lnone
> $ ./diff.sh cc1 1
> .debug_info      red: 44.84%    111527248  61527733
> .debug_abbrev    red: 40.28%    1722726  1028968
> .debug_str       red: 0%        6609355  6609355
> total            red: 42.30%    119859329 69166056
> ...
> to 54.55%:
> ...
> $ ./dwz.master cc1 -o 2 -lnone --odr
> $ ./diff.sh cc1 2
> .debug_info      red: 57.46%    111527248  47449258
> .debug_abbrev    red: 75.08%    1722726  429434
> .debug_str       red: 0%        6609355  6609355
> total            red: 54.55%    119859329 54488047
> ...
> pretty much disappears:
> ...
> $ ./dwz.fix cc1 -o 3 -lnone --odr
> $ ./diff.sh cc1 3
> .debug_info      red: 45.44%    111527248  60858640
> .debug_abbrev    red: 42.88%    1722726  984084
> .debug_str       red: 0%        6609355  6609355
> total            red: 42.89%    119859329 68452079
> ...
> 

I managed to come up with a fix that doesn't suffer from this
performance regression.

Any comments?

Thanks,
- Tom


[-- Attachment #2: 0001-Fix-CK_BAD-propagation-for-odr.patch --]
[-- Type: text/x-patch, Size: 6141 bytes --]

Fix CK_BAD propagation for --odr

With the reproducer from PR26252 we get:
...
$ dwz 2 -o 2.z --odr -lnone
dwz: dwz.c:7396: partition_found_dups: \
  Assertion `die->die_ck_state == CK_KNOWN' failed.
Aborted (core dumped)
...

The problem is caused by the odr code in checksum_ref_die, which skips
checksum calculation for the children of odr types, with as unintended
side-effect that it break the CK_BAD propagation to toplevel DIEs.

Fix this by making the skipping of the checksum calculation less intrusive.
Specially:
- undo all modifications related to odr in checksum_ref_die
- After calling checksum_ref_die in read_debug_info:
  - override die_ref_hash for odr DIEs, and
  - recalculate die_ref_hash for all other DIEs.

We still have the same amount of compression with cc1, that is: without odr
we have 42.30% reduction:
...
$ dwz cc1 -o cc1.z -lnone --no-odr
$ diff.sh cc1 cc1.z
.debug_info      red: 44.84%    111527248  61527733
.debug_abbrev    red: 40.28%    1722726  1028968
.debug_str       red: 0%        6609355  6609355
total            red: 42.30%    119859329 69166056
...
and with odr but without the bug fix we have 54.55%:
...
$ dwz cc1 -o cc1.z -lnone --odr
$ diff.sh cc1 cc1.z
.debug_info      red: 57.46%    111527248  47449258
.debug_abbrev    red: 75.08%    1722726  429434
.debug_str       red: 0%        6609355  6609355
total            red: 54.55%    119859329 54488047
...
and with odr and the bug fix still 54.55%:
...
$ dwz cc1 -o cc1.z -lnone --odr
$ ../measure/diff.sh cc1 cc1.z
.debug_info      red: 57.46%    111527248  47446501
.debug_abbrev    red: 75.51%    1722726  422027
.debug_str       red: 0%        6609355  6609355
total            red: 54.55%    119859329 54477883
...

2021-02-18  Tom de Vries  <tdevries@suse.de>

	PR dwz/26252
	* dwz.c (checksum_ref_die): Undo modifications related to odr.
	(read_debug_info): After calling checksum_ref_die, override
	die_ref_hash for odr DIEs, and recalculate die_ref_hash for all
	other DIEs.

---
 dwz.c | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 69 insertions(+), 20 deletions(-)

diff --git a/dwz.c b/dwz.c
index 0b751fc..62ebe97 100644
--- a/dwz.c
+++ b/dwz.c
@@ -3994,7 +3994,6 @@ checksum_ref_die (dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die,
   unsigned int i, ret = 0;
   unsigned char *ptr;
   dw_die_ref child;
-  bool only_hash_name_p;
 
   if (top_die == die)
     {
@@ -4025,7 +4024,6 @@ checksum_ref_die (dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die,
   else
     assert (top_die == NULL || die->die_ck_state == CK_KNOWN);
   t = die->die_abbrev;
-  only_hash_name_p = odr && die_odr_state (die_cu (die), die) != ODR_NONE;
   for (i = 0; i < t->nattr; ++i)
     if (t->attr[i].attr != DW_AT_sibling)
       switch (t->attr[i].form)
@@ -4209,24 +4207,25 @@ checksum_ref_die (dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die,
 	}
     }
 
-  if (!only_hash_name_p
-      && (top_die == NULL || top_die->die_ck_state != CK_BAD))
-    for (child = die->die_child; child; child = child->die_sib)
-      {
-	unsigned int r
-	  = checksum_ref_die (cu,
-			      top_die ? top_die
-			      : child->die_named_namespace
-			      ? NULL : child, child,
-			      second_idx, second_hash);
-	if (top_die == NULL)
-	  assert (r == 0 && obstack_object_size (&ob) == 0);
-
-	if (ret == 0 || (r && r < ret))
-	  ret = r;
-	if (top_die && top_die->die_ck_state == CK_BAD)
-	  break;
-      }
+  if (top_die == NULL || top_die->die_ck_state != CK_BAD)
+    {
+      for (child = die->die_child; child; child = child->die_sib)
+	{
+	  unsigned int r
+	    = checksum_ref_die (cu,
+				top_die ? top_die
+				: child->die_named_namespace
+				? NULL : child, child,
+				second_idx, second_hash);
+	  if (top_die == NULL)
+	    assert (r == 0 && obstack_object_size (&ob) == 0);
+
+	  if (ret == 0 || (r && r < ret))
+	    ret = r;
+	  if (top_die && top_die->die_ck_state == CK_BAD)
+	    break;
+	}
+     }
 
   if (top_die == die)
     {
@@ -6742,6 +6741,24 @@ read_debug_info (DSO *dso, int kind, unsigned int *die_count)
 
 	      for (cu = cuf; cu; cu = cu->cu_next)
 		checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+	      if (odr)
+		{
+		  for (cu = cuf; cu; cu = cu->cu_next)
+		    {
+		      dw_die_ref die;
+		      FOREACH_LOW_TOPLEVEL_DIE_IN_CU (die, cu)
+			{
+			  if (die->die_ck_state != CK_KNOWN)
+			    continue;
+			  if (die_odr_state (die_cu (die), die) != ODR_NONE)
+			    die->u.p1.die_ref_hash = die->u.p1.die_hash;
+			  else
+			    die->die_ref_hash_computed = 0;
+			}
+		    }
+		  for (cu = cuf; cu; cu = cu->cu_next)
+		    checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+		}
 
 	      if (dump_dies_p)
 		for (cu = cuf; cu; cu = cu->cu_next)
@@ -7220,6 +7237,20 @@ read_debug_info (DSO *dso, int kind, unsigned int *die_count)
 	  if (checksum_die (dso, cu, NULL, cu->cu_die))
 	    goto fail;
 	  checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+	  if (odr)
+	    {
+	      dw_die_ref die;
+	      FOREACH_LOW_TOPLEVEL_DIE_IN_CU (die, cu)
+		{
+		  if (die->die_ck_state != CK_KNOWN)
+		    continue;
+		  if (die_odr_state (die_cu (die), die) != ODR_NONE)
+		    die->u.p1.die_ref_hash = die->u.p1.die_hash;
+		  else
+		    die->die_ref_hash_computed = 0;
+		}
+	      checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+	    }
 
 	  if (dump_dies_p)
 	    dump_dies (0, cu->cu_die);
@@ -7292,6 +7323,24 @@ read_debug_info (DSO *dso, int kind, unsigned int *die_count)
 
       for (cu = first_cu; cu; cu = cu->cu_next)
 	checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+      if (odr)
+	{
+	  for (cu = first_cu; cu; cu = cu->cu_next)
+	    {
+	      dw_die_ref die;
+	      FOREACH_LOW_TOPLEVEL_DIE_IN_CU (die, cu)
+		{
+		  if (die->die_ck_state != CK_KNOWN)
+		    continue;
+		  if (die_odr_state (die_cu (die), die) != ODR_NONE)
+		    die->u.p1.die_ref_hash = die->u.p1.die_hash;
+		  else
+		    die->die_ref_hash_computed = 0;
+		}
+	    }
+	  for (cu = first_cu; cu; cu = cu->cu_next)
+	    checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
+	}
 
       if (dump_dies_p)
 	for (cu = first_cu; cu; cu = cu->cu_next)

Re: [PATCH] Fix CK_BAD propagation for --odr

[Tom de Vries]

On 2/18/21 3:20 PM, Tom de Vries wrote:

> The problem is caused by the odr code in checksum_ref_die, which skips
> checksum calculation for the children of odr types, with as unintended
> side-effect that it break the CK_BAD propagation to toplevel DIEs.
> 
> Fix this by making the skipping of the checksum calculation less intrusive.
> Specially:
> - undo all modifications related to odr in checksum_ref_die
> - After calling checksum_ref_die in read_debug_info:
>   - override die_ref_hash for odr DIEs, and
>   - recalculate die_ref_hash for all other DIEs.


> @@ -6742,6 +6741,24 @@ read_debug_info (DSO *dso, int kind, unsigned int *die_count)
>  
>  	      for (cu = cuf; cu; cu = cu->cu_next)
>  		checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
> +	      if (odr)
> +		{
> +		  for (cu = cuf; cu; cu = cu->cu_next)
> +		    {
> +		      dw_die_ref die;
> +		      FOREACH_LOW_TOPLEVEL_DIE_IN_CU (die, cu)
> +			{
> +			  if (die->die_ck_state != CK_KNOWN)
> +			    continue;
> +			  if (die_odr_state (die_cu (die), die) != ODR_NONE)
> +			    die->u.p1.die_ref_hash = die->u.p1.die_hash;
> +			  else
> +			    die->die_ref_hash_computed = 0;
> +			}
> +		    }
> +		  for (cu = cuf; cu; cu = cu->cu_next)
> +		    checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
> +		}
>  
>  	      if (dump_dies_p)
>  		for (cu = cuf; cu; cu = cu->cu_next)
> @@ -7292,6 +7323,24 @@ read_debug_info (DSO *dso, int kind, unsigned int *die_count)
>  
>        for (cu = first_cu; cu; cu = cu->cu_next)
>  	checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
> +      if (odr)
> +	{
> +	  for (cu = first_cu; cu; cu = cu->cu_next)
> +	    {
> +	      dw_die_ref die;
> +	      FOREACH_LOW_TOPLEVEL_DIE_IN_CU (die, cu)
> +		{
> +		  if (die->die_ck_state != CK_KNOWN)
> +		    continue;
> +		  if (die_odr_state (die_cu (die), die) != ODR_NONE)
> +		    die->u.p1.die_ref_hash = die->u.p1.die_hash;
> +		  else
> +		    die->die_ref_hash_computed = 0;
> +		}
> +	    }
> +	  for (cu = first_cu; cu; cu = cu->cu_next)
> +	    checksum_ref_die (cu, NULL, cu->cu_die, NULL, NULL);
> +	}
>  
>        if (dump_dies_p)
>  	for (cu = first_cu; cu; cu = cu->cu_next)
> 

I've realized that these two bits (for op_multifile, and rd_multifile ||
fi_multifile) are not useful, because odr is not a multi-file
optimization, so the die_odr_state (die_cu (die), die) != ODR_NONE would
always return false.

Committed with these bits dropped.

Thanks,
- Tom