Re: [PATCHv3 5/7] gdb: create address map after parsing all DIE

[Andrew Burgess <aburgess@redhat.com>]

Hi Tom,

Thanks for taking a look at these patches.  I wanted to follow up on
some of your thoughts...

Tom Tromey <tom@tromey.com> writes:

>>>>>> "Andrew" == Andrew Burgess <aburgess@redhat.com> writes:
>
> Andrew> Continuing the work done in the last two commits, this commit defers
> Andrew> building the addrmap for a blockvector until after all the DIE have
> Andrew> been read, and the line table processed.
>
> Andrew> The benefit of this is that any changes to a block's ranges done
> Andrew> during line table processing (see the next commit) will be reflected
> Andrew> in the blockvector's addrmap.
>
> Andrew> The alternative to this is to build the addrmap as we initially see
> Andrew> each block, but then adjust the addrmap if we later decide to modify a
> Andrew> block.  I think defering the addrmap creation is cleaner, and is less
> Andrew> work overall.
>
> Andrew> The addrmap requires that we add the most inner blocks first.  I
> Andrew> achieve this by walking the blockvector backward, as we always add
> Andrew> parent blocks before their more inner child blocks.
>
> I wonder if this is guaranteed to be correct.  Like, does gdb cope
> properly if a compiler happens to emit multiple lexical scopes that each
> have non-contiguous ranges, and then where the ranges happen to overlap.

I had a play with some examples using DW_TAG_lexical_block to see how
things change.

If things are laid out in what I'd consider a "sane" way, with nested
blocks being nested within the DWARF, then you'll end up with the same
block structure before and after this patch, e.g.:

                DW_TAG_lexical_block {
                    ...
                } {
                    DW_TAG_variable {
                        DW_AT_name "var_a"
                        ...
                    }

		    DW_TAG_lexical_block {
                        ...
		    } {
			DW_TAG_variable {
			    DW_AT_name "var_b"
                            ...
			}
		    }
                }

In this example the block containing 'var_a' is added to the blockvector
before the block holding 'var_b', so when we walk the blockvector
backwards, we see the 'var_b' block first, and everything is fine.

If we change the test to be structured like this instead:

                DW_TAG_lexical_block {
                    ...
                } {
                    DW_TAG_variable {
                        DW_AT_name "var_a"
                        ....
                    }
                }

                DW_TAG_lexical_block {
                    ...
                } {
                    DW_TAG_variable {
                        DW_AT_name "var_b"
                        ...
                    }
                }

Now the two lexical blocks are siblings, but if we make the second block
overlap the first then this patch does cause problems.

Current GDB will see the 'var_a' block first and add this to the map,
then when GDB sees the 'var_b' block, only the addresses not claimed by
the 'var_a' block will be allocated to the second lexical block.

With this patch blocks are now processed in reverse order, so we see the
'var_b' block first and assign addresses to this, then any unassigned
addresses are assigned to the 'var_a' block.

This DOES change GDB's behaviour.

> However I think your patch probably does not make gdb worse in this
> regard.

This is what I think.  In the sibling block case it's not clear what the
expected behaviour would actually be?  In current GDB you'll only see
'var_b' at those addresses not covered by the 'var_a' block.  While in
patched GDB the situation is reveresed, it's 'var_a' that's missing in
some cases.

In both cases there are addresses where we can only see one of the
variables.  But it isn't 100% clear too me if this is really fixable at
all with our current block hierarchy approach.

Is this sibling case the type of case you were thinking of?  Or have I
got the wrong end of the stick here?

>
> Andrew> @@ -410,8 +410,6 @@ buildsym_compunit::record_block_range (struct block *block,
> Andrew>    if (start != block->start ()
> Andrew>        || end_inclusive + 1 != block->end ())
> Andrew>      m_pending_addrmap_interesting = true;
> Andrew> -
> Andrew> -  m_pending_addrmap.set_empty (start, end_inclusive, block);
> Andrew>  }
>
> I think the comment before this method and the comment in the method
> both need to be updated, as this doesn't actually record the range any
> more.

Yeah.  But reading this code again I think I can drop record_block_range
completely now.  Blocks are basically interesting if they are
non-contiguous, and buildsym_compunit::make_blockvector, which is the
only place that checks m_pending_addrmap_interesting already has this
code:

  /* Count the length of the list of blocks.  */
  
  for (next = m_pending_blocks, i = 0; next; next = next->next, i++)
    {
    }

Where we could check for any non-contiguous blocks.  This would mean GDB
starts using the map instead of the vector for the case where a block
uses DW_AT_ranges, but only has a single range.  This shouldn't be a
user visible change, but I guess would increase memory use a little.
Still, I expect this would not be a common case as most compilers seem
to optimise to low/high pc attributes for contiguous blocks.

> I wonder why buildsym even tries to see if the pending addrmap might be
> interesting.  It seems to me that a fixed addrmap is basically the same
> data structure as the blockvector: it maps addresses to blocks and uses
> a binary search to find the correct entry.

Sure, but I wonder if this is a memory use thing?  The addrmap must use
more memory than the vector, so maybe for large programs this would be a
noticable hit.

>
> So I'm wondering if, in the longer term -- you definitely don't need to
> to this here -- if we should just switch to a single representation.
>
> Furthermore I was wondering if it makes sense for blocks to even track
> their ranges.  That is, for a block with multiple ranges, could we just
> have multiple entries in the blockvector and get rid of block::m_ranges?

There are a few places where we use the block's ranges for useful work,
these would all need to be rewritten to get the same information from
the blockvector (really the addrmap within the blockvector).

>
> FWIW I've been looking into this area a bit while experimenting with
> lazy CU expansion.  There I think I want to make it so blockvectors are
> always expandable, so no fixed addrmap at least -- and mutable addrmaps
> have some issues with updating, so probably moving to just having a
> vector.

Wouldn't that cause problems for non-contiguous blocks?  Isn't that the
problem that the addrmap was added to solve?

I'm going to look at updating to remove record_block_range completely,
and test that.  But I'd love to hear back about the lexical block
testing I did.

thanks,
Andrew

>
> Anyway this seems fine with the comment cleanup.
> Approved-By: Tom Tromey <tom@tromey.com>
>
> Tom