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

["Christian Biesinger via gdb-patches" <gdb-patches@sourceware.org>]

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?

+              });


>    cust = allocate_compunit_symtab (objfile, stab->file_name.c_str ());
>    allocate_symtab (cust, stab->file_name.c_str ());
> @@ -680,19 +632,18 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>                                              blockvector_size);
>    COMPUNIT_BLOCKVECTOR (cust) = bv;
>
> -  /* (begin, end) will contain the PC range this entire blockvector
> -     spans.  */
> +  /* At the end of this function, (begin, end) will contain the PC range
> this
> +     entire blockvector spans.  */
>    BLOCKVECTOR_MAP (bv) = NULL;
> -  begin = stab->blocks->begin;
> -  end = stab->blocks->end;
> +  begin = stab->blocks.front ()->begin;
> +  end = stab->blocks.front ()->end;
>    BLOCKVECTOR_NBLOCKS (bv) = actual_nblocks;
>
>    /* First run over all the gdb_block objects, creating a real block
>       object for each.  Simultaneously, keep setting the real_block
>       fields.  */
> -  for (i = (actual_nblocks - 1), gdb_block_iter = stab->blocks;
> -       i >= FIRST_LOCAL_BLOCK;
> -       i--, gdb_block_iter = gdb_block_iter->next)
> +  int block_idx = FIRST_LOCAL_BLOCK;
> +  for (gdb_block *gdb_block_iter : stab->blocks)
>      {
>        struct block *new_block = allocate_block
> (&objfile->objfile_obstack);
>        struct symbol *block_name = allocate_symbol (objfile);
> @@ -719,18 +670,20 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>
>        BLOCK_FUNCTION (new_block) = block_name;
>
> -      BLOCKVECTOR_BLOCK (bv, i) = new_block;
> +      BLOCKVECTOR_BLOCK (bv, block_idx) = new_block;
>        if (begin > BLOCK_START (new_block))
>          begin = BLOCK_START (new_block);
>        if (end < BLOCK_END (new_block))
>          end = BLOCK_END (new_block);
>
>        gdb_block_iter->real_block = new_block;
> +
> +      block_idx++;
>      }
>
>    /* Now add the special blocks.  */
> -  block_iter = NULL;
> -  for (i = 0; i < FIRST_LOCAL_BLOCK; i++)
> +  struct block *block_iter = NULL;
> +  for (enum block_enum i : { GLOBAL_BLOCK, STATIC_BLOCK })
>      {
>        struct block *new_block;
>
> @@ -753,9 +706,7 @@ finalize_symtab (struct gdb_symtab *stab, struct
> objfile *objfile)
>
>    /* Fill up the superblock fields for the real blocks, using the
>       real_block fields populated earlier.  */
> -  for (gdb_block_iter = stab->blocks;
> -       gdb_block_iter;
> -       gdb_block_iter = gdb_block_iter->next)
> +  for (gdb_block *gdb_block_iter : stab->blocks)
>      {
>        if (gdb_block_iter->parent != NULL)
>         {
> --
> 2.24.1
>
>