Re: [PATCH 02/11] gdb: introduce intrusive_list, make thread_info use it

[Simon Marchi via Gdb-patches <gdb-patches@sourceware.org>]

On 2021-07-05 11:44 a.m., Pedro Alves wrote:
> Hi!
> 
> This looks mostly good to me, though I'm biased...
> 
> On 2021-06-22 5:56 p.m., Simon Marchi wrote:
>> From: Pedro Alves <pedro@palves.net>
>>
>> GDB currently has several objects that are put in a singly linked list,
>> by having the object's type have a "next" pointer directly.  For
>> example, struct thread_info and struct inferior.  Because these are
>> simply-linked lists, and we don't keep track of a "tail" pointer, when
>> we want to append a new element on the list, we need to walk the whole
>> list to find the current tail.  It would be nice to get rid of that
>> walk.  Removing elements from such lists also requires a walk, to find
>> the "previous" position relative to the element being removed.  To
>> eliminate the need for that walk, we could make those lists
>> doubly-linked, by adding a "prev" pointer alongside "next".  It would be
>> nice to avoid the boilerplace associated with maintaining such a list
> 
> boilerplace -> boilerplate

Fixed.

>> Unlike Boost's implementation, ours is not a circular list.  An earlier
>> version of the patch was circular: the instrusive_list type included an
> 
> instrusive_list -> intrusive_list

Fixed.

>> Add a Python pretty-printer, to help inspecting intrusive lists when
>> debugging GDB with GDB.  Here's an example of the output:
>>
>>     (top-gdb) p current_inferior_.m_obj.thread_list
>>     $1 = intrusive list of thread_info = {0x61700002c000, 0x617000069080, 0x617000069400, 0x61700006d680, 0x61700006eb80}
>>
> 
> Did you find this output helpful in practice?  Printing the whole object is
> for sure too much, but I wonder whether printing the thread id, and ptid and
> perhaps the thread state wouldn't be more helpful, like:

I didn't use it extensively, so I can't say if I find it really useful
or not.

>  $1 = intrusive list of thread_info = {
>    {id = 1.1, ptid = 1000.1000.0, state = THREAD_RUNNING}, 
>    {id = 1.3, ptid = 1000.1002.0, state = THREAD_STOPPED},
>    {id = 1.5, ptid = 1000.3672.0, state = THREAD_STOPPED}
>  }

How would you accomplish this, with a struct thread_info
pretty-printer?  This means that printing a single thread like this:

  (gdb) print *tp

would also produce the short output, I don't think we want that.  When
we print a single thread_info structure, I think it's good to have all
the fields shown.

Perhaps by defining a more specialized pretty-printer for
intrusive_list<thread_info>?  But then I'm not sure what kind of value
the children method would return.

Or can we define a pretty printer on the `struct thread_info *` type,
such that when a thread_info pointer is printed, we can print some extra
information next to the pointer value?  Like:

  (gdb) print tp
  $1 = (thread_info *) 0x61700002c000 { id=1.1, ptid=1000.1000.0, state=THREAD_RUNNING }

So presumably, when printing the list, that would give:

  $1 = intrusive list of thread_info = {
    0x61700002c000 {id = 1.1, ptid = 1000.1000.0, state = THREAD_RUNNING},
    0x617000069080 {id = 1.3, ptid = 1000.1002.0, state = THREAD_STOPPED},
    0x617000069400 {id = 1.5, ptid = 1000.3672.0, state = THREAD_STOPPED}
  }

But I don't even know if that is possible.  I'll give it a try and report back.

>> It's not possible with current master, but with this patch [1] that I
>> hope will be merged eventually, it's possible to index the list and
>> access the pretty-printed value's children:
>>
>>     (top-gdb) p current_inferior_.m_obj.thread_list[1]
>>     $2 = (thread_info *) 0x617000069080
>>     (top-gdb) p current_inferior_.m_obj.thread_list[1].ptid
>>     $3 = {
>>       m_pid = 406499,
>>       m_lwp = 406503,
>>       m_tid = 0
>>     }
> 
> I guess in practice I'd always want to print the list
> with "set print array-indexes on".  Otherwise, how would you know
> which index to pass to []?  And still, with just pointers/addresses
> in the output, I'm not sure I'd easily know which index to pass:
> 
>  $1 = intrusive list of struct thread_info = {[0] = 0x5555564d0f60, [1] = 0x5555572ad640, [2] = 0x5555572ad9f0}
> 
> ?
> 
> I mean, one can eyeball for the right entry based on thread_info
> pointer/address, but if one already has the pointer/address handy, then
> one wouldn't need to search for the entry in the thread list in the first
> place, right?
> 
> It does seem to make it a bit easier to iterate over the whole list
> printing each element, easier than following the next->next->next
> pointers.  Was that the use case you had in mind?

I agree with you that for a long list it can be difficult to know which
index to use.  I've tried it only with lists of 4-5 elements, in which
case it's easy.

It is indeed easier when iterating "by hand", especially when using a
node as a field.  Because then it's not `.next.next.next` but
`.node.nextnode.next.node.next`.

I think that in any case it's more useful to have the possibility to do
it than not having it, we don't lose anything by having it.  But
printing indices sounds useful indeed.

> With the alternative output suggested above, we'd have:
> 
>  $1 = intrusive list of thread_info = {
>    [0] = {id = 1.1, ptid = 1000.1000.0, state = THREAD_RUNNING}, 
>    [1] = {id = 1.3, ptid = 1000.1002.0, state = THREAD_STOPPED},
>    [2] = {id = 1.5, ptid = 1000.3672.0, state = THREAD_STOPPED}
>  }
> 
> Off hand, I think I'd find this more useful.  I'm assuming that
> using [] with Andrew's patch would still work the same way.
> 
> I guess this would be implemented by passing some customization
> object or function to the pretty printer, that it would call to
> print each element.  If no such customization is passed, then
> it would just print what you have.  So I guess this could always
> be done separately...

Perhaps that could be done by pretending intrusive_list is a map, making
the display_hint method return 'map' instead of 'array':

  https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing-API.html#Pretty-Printing-API

>> @@ -0,0 +1,734 @@
>> +/* Tests fpr intrusive double linked list for GDB, the GNU debugger.
>> +   Copyright (C) 2021 Free Software Foundation, Inc.
>> +
>> +   This file is part of GDB.
>> +
>> +   This program is free software; you can redistribute it and/or modify
>> +   it under the terms of the GNU General Public License as published by
>> +   the Free Software Foundation; either version 3 of the License, or
>> +   (at your option) any later version.
>> +
>> +   This program is distributed in the hope that it will be useful,
>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>> +   GNU General Public License for more details.
>> +
>> +   You should have received a copy of the GNU General Public License
>> +   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
>> +
>> +#include "defs.h"
>> +
>> +#include "gdbsupport/intrusive_list.h"
>> +#include "gdbsupport/selftest.h"
>> +#include <unordered_set>
>> +
>> +/* An item type using intrusive_list_node by inheriting from it and its
>> +   corresponding list type.  Put another base before intrusive_list_node
>> +   so that a pointer to the node != a pointer to the item.  */
>> +
>> +struct other_base
>> +{
>> +  int n = 1;
>> +};
>> +
>> +struct item_with_base : public other_base,
>> +			public intrusive_list_node<item_with_base>
>> +{
>> +  item_with_base (const char *name)
> 
> explicit

Done.

>> +    : name (name)
>> +  {}
>> +
>> +  const char *const name;
>> +};
>> +
>> +using item_with_base_list = intrusive_list<item_with_base>;
>> +
>> +/* An item type using intrusive_list_node as a field and its corresponding
>> +   list type.  Put the other field before the node, so that a pointer to the
>> +   node != a pointer to the item.  */
>> +
>> +struct item_with_member
>> +{
>> +  item_with_member (const char *name)
> 
> explicit

Done.

>> diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h
>> new file mode 100644
>> index 000000000000..8e98e5b2c1a5
>> --- /dev/null
>> +++ b/gdbsupport/intrusive_list.h
>> @@ -0,0 +1,559 @@
>> +/* Intrusive double linked list for GDB, the GNU debugger.
>> +   Copyright (C) 2021 Free Software Foundation, Inc.
>> +
>> +   This file is part of GDB.
>> +
>> +   This program is free software; you can redistribute it and/or modify
>> +   it under the terms of the GNU General Public License as published by
>> +   the Free Software Foundation; either version 3 of the License, or
>> +   (at your option) any later version.
>> +
>> +   This program is distributed in the hope that it will be useful,
>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>> +   GNU General Public License for more details.
>> +
>> +   You should have received a copy of the GNU General Public License
>> +   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
>> +
>> +#ifndef GDBSUPPORT_INTRUSIVE_LIST_H
>> +#define GDBSUPPORT_INTRUSIVE_LIST_H
>> +
>> +#define UNLINKED_VALUE ((T *) -1)
> 
> UNLINKED_VALUE seems like a too-generic name for a macro.
> I think it'd be better to add some prefix to minimize
> potential for conflict.  INTR_LIST_UNLINKED_VALUE
> or some such.

Agreed, I'm always the one who usually asks for better naming /
scoping.  I'll use INTRUSIVE_LIST_UNLINKED_VALUE since I don't like
unnecessary abbreviations :).

Thanks,

Simon