Re: [PATCH 1/8] Add block range data structure for blocks with non-contiguous address ranges

Kevin Buettner
2018-08-01T23:57:52Z

On Tue, 31 Jul 2018 21:35:50 -0400
Simon Marchi <simon.marchi@ericsson.com> wrote:

> On 2018-06-26 02:42 AM, Kevin Buettner wrote:
> > This patch does the following:
> >
> > - Introduces a block range data structure which is accessed via
> > a new field in struct block.
> > - Defines several macros for accessing block ranges.
> > - Defines a new function, make_blockrange, which is responsible for
> > creating the new data structure.
> > - Defines a predicate (function) which checks to see if an address
> > is present in a block.
> >
> > It should be noted that some support for non-contiguous ranges already
> > existed in GDB in the form of blockvector addrmaps. This support
> > allowed GDB to quickly find a block containing a particular address
> > even when the block consists of non-contiguous addresses. See
> > find_block_in_blockvector() in block.c, dwarf2_record_block_ranges()
> > in dwarf2read.c, and record_block_range() in buildsym.c.
> >
> > Addrmaps do not provide a convenient way to examine address ranges
> > associated with a particular block. This data structure (and its
> > interface) is set up for quickly finding the value (which in this case
> > is a block) associated with a particular address. The interface
> > does not include a method for doing a reverse mapping from blocks to
> > addresses. A linear time mapping might be attempted via use of the
> > addrmap's foreach method, but this is not as straightforward as it
> > might first appear due to the fact that blocks corresponding to inline
> > function instances and lexical blocks w/ variables end up getting
> > interspersed in in the set of transitions.
> >
> > Note: If this approach is deemed to be too expensive in terms of
> > space, an alternate approach might be to attempt the linear time
> > mapping noted above. find_pc_partial_function() needs to be able to
> > quickly know whether there are discontiguous ranges (for determining
> > cache validity), so a flag for this property would have to be added to
> > struct block. Also integral to this set of changes is the concept of
> > an "entry pc" which might be different than the block's start address.
> > An entry_pc field would also need to be added to struct block. This
> > does not result in any space savings in struct block though since the
> > space for the flag and entry_pc use more space than the blockranges
> > struct pointer that I've added. There would, however, be some space
> > savings due to the fact that the new data structures that I've added
> > for this patch would not need to be allocated. (I happen to like the
> > approach I've come up with, but I wanted to mention another possibility
> > just in case someone does not.)
>
> I assume the impact won't be too big (there probably isn't a ton of ranges
> per block), but some actual data would be interesting.

In real code, I've seen at most two ranges per block. At the moment,
I don't think that GCC is overly aggressive at splitting functions into
multiple ranges. Most functions occupy just one range.

Jakub's test case called abort(). The function in which abort() appeared
was split into two ranges. One range contained the call to abort; the other
had the rest of the function.

I've also seen C++ functions with try/catch broken up into more than one
range. The less frequently used case is placed within a "cold" range.

Kevin