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

[Pedro Alves <pedro@palves.net>]

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

> manually, though.  That is what the new intrusive_list type addresses.

...

> 
> 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

> intrusive_list_node "head".  In this design, a node contained pointers
> to the previous and next nodes, not the previous and next elements.
> This wasn't great for when debugging GDB with GDB, as it was difficult
> to get from a pointer to the node to a pointer to the element.  With the
> design proposed in this patch, nodes contain pointers to the previous
> and next elements, making it easy to traverse the list by hand and
> inspect each element.
> 

...

> 
> 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:

 $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}
 }

> 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?

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...

> +++ b/gdb/unittests/intrusive_list-selftests.c

Yay, unit tests!  Thanks a lot for writing them.

> @@ -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

> +    : 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

> 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.