From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-f47.google.com (mail-wm1-f47.google.com [209.85.128.47]) by sourceware.org (Postfix) with ESMTPS id 4479E385781D for ; Mon, 5 Jul 2021 15:44:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4479E385781D Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=palves.net Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-wm1-f47.google.com with SMTP id h18-20020a05600c3512b029020e4ceb9588so1112272wmq.5 for ; Mon, 05 Jul 2021 08:44:51 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:references:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=FSyjX1NrntVpzeF7L2q8TW6thZxna3WY01nvg+SWmgE=; b=NdsxgDtQOiofT7YDqLO8twkSKsKpfL6nEZPSVHGCxpYJhUJ9MdZQXo0y1kuA2eVxmE +HK2/V/8eth4JDUAFDc7NpItuEp00XltNebCZDZkyyVFD8Ewqhwkbbi/UJfJgkcNV0rW JkClf0Y8E3kd5e2E3cA2bCrNWJtXMwM9Ti3AahNJwjfWVsZqwfqwP+/1QmaV8iw4fUND GYv7kpDrldZ2Q9F5ouqcrF8crq8oK9ZtKstsQbeUw7Knfy6rECX8HyKFiGbcM6IOa0iX wveQd2O8MPkzKIb3nzrmYd4ULKvlKO7XLUgirPeDKakgDvkLluEUQUQG05TOr3U6BLdJ tJAg== X-Gm-Message-State: AOAM533SVwNbWAvskpt4VPLHggfMQEvBITQnCKWuIl1D3XyHiisaxjxs dbgAm92w5ERL5H9zsfQ7oAo= X-Google-Smtp-Source: ABdhPJyp0CHuwHTKHO3pWSafEU9BDM/4v4GMlIRd34K2WIM5K2/mEOWuYYkzlwc6tNDd4rEgHo1fJA== X-Received: by 2002:a05:600c:b48:: with SMTP id k8mr15355195wmr.127.1625499890292; Mon, 05 Jul 2021 08:44:50 -0700 (PDT) Received: from ?IPv6:2001:8a0:f932:6a00:46bc:d03b:7b3a:2227? ([2001:8a0:f932:6a00:46bc:d03b:7b3a:2227]) by smtp.gmail.com with ESMTPSA id h8sm13603372wrt.85.2021.07.05.08.44.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 05 Jul 2021 08:44:49 -0700 (PDT) Subject: Re: [PATCH 02/11] gdb: introduce intrusive_list, make thread_info use it From: Pedro Alves To: Simon Marchi , gdb-patches@sourceware.org Cc: Simon Marchi References: <20210622165704.2404007-1-simon.marchi@polymtl.ca> <20210622165704.2404007-3-simon.marchi@polymtl.ca> Message-ID: <2466c5e0-36f4-ce47-f05f-022cda04bb04@palves.net> Date: Mon, 5 Jul 2021 16:44:48 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 MIME-Version: 1.0 In-Reply-To: <20210622165704.2404007-3-simon.marchi@polymtl.ca> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 05 Jul 2021 15:44:53 -0000 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 > > 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 . */ > + > +#include "defs.h" > + > +#include "gdbsupport/intrusive_list.h" > +#include "gdbsupport/selftest.h" > +#include > + > +/* 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 (const char *name) explicit > + : name (name) > + {} > + > + const char *const name; > +}; > + > +using item_with_base_list = intrusive_list; > + > +/* 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 . */ > + > +#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.