Re: [PATCH 4/7] jit: make gdb_symtab::blocks a vector

[Simon Marchi <simon.marchi@polymtl.ca>]

On 2019-12-13 10:16 a.m., Christian Biesinger via gdb-patches wrote:
> On Fri, Dec 13, 2019, 01:18 Simon Marchi <simon.marchi@polymtl.ca> wrote:
> 
>> This patch changes the gdb_symtab::blocks linked list to be an
>> std::vector, simplifying memory management.
>>
>> Currently, the list is sorted as blocks are created.  It is easier (and
>> probably a bit more efficient) to sort them once at the end, so this is
>> what I did.
>>
>> A note about the comment on the "next" field:
>>
>>   /* gdb_blocks are linked into a tree structure.  Next points to the
>>      next node at the same depth as this block and parent to the
>>      parent gdb_block.  */
>>
>> I don't think it's true that "next" points to the next node at the same
>> depth.  It might happen to be true for some nodes, but it can't be true
>> in general, as this is a simple linked list containing all the created
>> blocks.
>>
>> gdb/ChangeLog:
>>
>>         * jit.c (struct gdb_block) <next>: Remove field.
>>         (struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
>>         <blocks>: Change type to std::vector<gdb_block *>.
>>         <nblocks>: Remove.
>>         (compare_block): Remove.
>>         (jit_block_open_impl): Adjust to std::vector.  Place the new
>>         block at the end, don't mind about sorting.
>>         (finalize_symtab): Adjust to std::vector, sort the blocks vector
>>         before using it.
>> ---
>>  gdb/jit.c | 111 +++++++++++++++---------------------------------------
>>  1 file changed, 31 insertions(+), 80 deletions(-)
>>
>> diff --git a/gdb/jit.c b/gdb/jit.c
>> index eace83e583d3..bb855e09f59b 100644
>> --- a/gdb/jit.c
>> +++ b/gdb/jit.c
>> @@ -428,10 +428,8 @@ jit_read_code_entry (struct gdbarch *gdbarch,
>>
>>  struct gdb_block
>>  {
>> -  /* gdb_blocks are linked into a tree structure.  Next points to the
>> -     next node at the same depth as this block and parent to the
>> -     parent gdb_block.  */
>> -  struct gdb_block *next, *parent;
>> +  /* The parent of this block.  */
>> +  struct gdb_block *parent;
>>
>>    /* Points to the "real" block that is being built out of this
>>       instance.  This block will be added to a blockvector, which will
>> @@ -456,14 +454,8 @@ struct gdb_symtab
>>
>>    ~gdb_symtab ()
>>    {
>> -    gdb_block *gdb_block_iter, *gdb_block_iter_tmp;
>> -
>> -    for ((gdb_block_iter = this->blocks,
>> -         gdb_block_iter_tmp = gdb_block_iter->next);
>> -         gdb_block_iter;
>> -         gdb_block_iter = gdb_block_iter_tmp)
>> +    for (gdb_block *gdb_block_iter : this->blocks)
>>        {
>> -        gdb_block_iter_tmp = gdb_block_iter->next;
>>          xfree ((void *) gdb_block_iter->name);
>>          xfree (gdb_block_iter);
>>        }
>> @@ -471,10 +463,7 @@ struct gdb_symtab
>>
>>    /* The list of blocks in this symtab.  These will eventually be
>>       converted to real blocks.  */
>> -  struct gdb_block *blocks = nullptr;
>> -
>> -  /* The number of blocks inserted.  */
>> -  int nblocks = 0;
>> +  std::vector<gdb_block *> blocks;
>>
>>    /* A mapping between line numbers to PC.  */
>>    gdb::unique_xmalloc_ptr<struct linetable> linetable;
>> @@ -537,28 +526,6 @@ jit_symtab_open_impl (struct gdb_symbol_callbacks *cb,
>>    return symtab;
>>  }
>>
>> -/* Returns true if the block corresponding to old should be placed
>> -   before the block corresponding to new in the final blockvector.  */
>> -
>> -static int
>> -compare_block (const struct gdb_block *const old,
>> -               const struct gdb_block *const newobj)
>> -{
>> -  if (old == NULL)
>> -    return 1;
>> -  if (old->begin < newobj->begin)
>> -    return 1;
>> -  else if (old->begin == newobj->begin)
>> -    {
>> -      if (old->end > newobj->end)
>> -        return 1;
>> -      else
>> -        return 0;
>> -    }
>> -  else
>> -    return 0;
>> -}
>> -
>>  /* Called by readers to open a new gdb_block.  This function also
>>     inserts the new gdb_block in the correct place in the corresponding
>>     gdb_symtab.  */
>> @@ -570,37 +537,15 @@ jit_block_open_impl (struct gdb_symbol_callbacks *cb,
>>  {
>>    struct gdb_block *block = XCNEW (struct gdb_block);
>>
>> -  block->next = symtab->blocks;
>>    block->begin = (CORE_ADDR) begin;
>>    block->end = (CORE_ADDR) end;
>>    block->name = name ? xstrdup (name) : NULL;
>>    block->parent = parent;
>>
>> -  /* Ensure that the blocks are inserted in the correct (reverse of
>> -     the order expected by blockvector).  */
>> -  if (compare_block (symtab->blocks, block))
>> -    {
>> -      symtab->blocks = block;
>> -    }
>> -  else
>> -    {
>> -      struct gdb_block *i = symtab->blocks;
>> -
>> -      for (;; i = i->next)
>> -        {
>> -          /* Guaranteed to terminate, since compare_block (NULL, _)
>> -             returns 1.  */
>> -          if (compare_block (i->next, block))
>> -            {
>> -              block->next = i->next;
>> -              i->next = block;
>> -              break;
>> -            }
>> -        }
>> -    }
>> -  symtab->nblocks++;
>> -
>> -  return block;
>> +  /* Place the block at the end of the vector, it will be sorted when the
>> +     symtab is finalized.  */
>> +  symtab->blocks.push_back (block);
>> +  return symtab->blocks.back ();
>>  }
>>
>>  /* Readers call this to add a line mapping (from PC to line number) to
>> @@ -646,14 +591,21 @@ static void
>>  finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
>>  {
>>    struct compunit_symtab *cust;
>> -  struct gdb_block *gdb_block_iter;
>> -  struct block *block_iter;
>> -  int actual_nblocks, i;
>>    size_t blockvector_size;
>>    CORE_ADDR begin, end;
>>    struct blockvector *bv;
>>
>> -  actual_nblocks = FIRST_LOCAL_BLOCK + stab->nblocks;
>> +  int actual_nblocks = FIRST_LOCAL_BLOCK + stab->blocks.size ();
>> +
>> +  /* Sort the blocks in the order they should appear in the blockvector.
>> */
>> +  std::sort (stab->blocks.begin (), stab->blocks.end (),
>> +            [] (const gdb_block *a, const gdb_block *b)
>> +              {
>> +                if (a->begin != b->begin)
>> +                  return a->begin < b->begin;
>> +
>> +                return b->begin < a->begin;
>>
> 
> This doesn't look right? Should this look at end or something?

Oh my, indeed, thank you so much for spotting this.  I meant this, of course:

  std::sort (stab->blocks.begin (), stab->blocks.end (),
	     [] (const gdb_block *a, const gdb_block *b)
	       {
		 if (a->begin != b->begin)
		   return a->begin < b->begin;

		 return b->end < a->end;
	       });

Or do you find it more readable this way below instead?  It's a bit subtle that "a"
and "b" are reversed, otherwise

  std::sort (stab->blocks.begin (), stab->blocks.end (),
	     [] (const gdb_block *a, const gdb_block *b)
	       {
		 if (a->begin != b->begin)
		   return a->begin < b->begin;

		 return a->end > b->end;
	       });

Simon