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

Simon Marchi
2019-12-13T16:02:13Z

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