From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12on2082.outbound.protection.outlook.com [40.107.237.82]) by sourceware.org (Postfix) with ESMTPS id 4E8A13858C2F for ; Mon, 7 Nov 2022 18:48:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4E8A13858C2F Authentication-Results: sourceware.org; dmarc=fail (p=quarantine dis=none) header.from=amd.com Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=amd.com ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=IsHMYvco+1EK1JuzMoHM4cfguddrFk3BuOym1xEaYVy6exbZIG1v7tXkRFgA4Yd3rJqYLEfmuhGJ7DsXnJoFyVDLi88u74+fQJvaL14d9lEIAxYhrBWP78ZH5fVkDPyg/dsYRsRF+xfZbp+h0SgD7c2unJghCCRarUTJRPMmCtchszBzRkOGc8PDyeD5r8BVOPbswKeDhwupH7WdQeSyyRc/3cSBrzBCFcc/NfD7m0VmTljbomiJFPnQCMjuMh47EOc9EKPj/4fjTo24g6GDM1fIsNH923vtv7jBMIc3qh4SABq1gxE/iLdjoWJrB++kfTER4OKylPKHBfHSYW6jDQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=tdeVMy8I7wUOLdMAHOs2rKEkGLGkYrvovEklJCZr6hM=; b=n1vEJNC23i1oPOSk/vLen6L5jWurKzCl3XyS4eQ0GTSzW2itQ1xnTf5pjHHRoREm96Y4m2OSQxKbHRaoP97WnGBpLHHVROUFo78PwWiWITH27G2YxPaMOhszCJR/Byk6UVsv+Pj6wlOHpcuxQD6Lw+UJ65cKms9n1PxSG+bQOPJK3JCvpxrhoRfHXGgb6EXpsYiMCRyU/BsIzEn8BqSc7NqtpfIyx0u2VEPTnmVRShj9v8cVAM/KQ0yxOMw15b37+Vbmxtg7G+lUnK7Cb9MmYW8lm6hZ/wWRgM3RlSORdUrQOTs3W8rB0hgCsJmijTqzpgrF70uF02GXxiW0x4KvIw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none (sender ip is 165.204.84.17) smtp.rcpttodomain=sourceware.org smtp.mailfrom=amd.com; dmarc=fail (p=quarantine sp=quarantine pct=100) action=quarantine header.from=amd.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amd.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=tdeVMy8I7wUOLdMAHOs2rKEkGLGkYrvovEklJCZr6hM=; b=XmjDRpYuuXbmRgYcF2rYMv8kOhUa5/P7Bju4l4SL4DiYFO2sLxYyK0PzmLYW5adPLHJC1NnZG1M/juCEWqjSuhvA2yw4VQqwVUqw5uE8GPeEuQ/IFuF9RUSEarhTHIHcukCj/+R9crtfjtkqS4IEWg6EhcpSQlildBQLGJIuBFQ= Received: from DS7PR06CA0050.namprd06.prod.outlook.com (2603:10b6:8:54::32) by BY5PR12MB4116.namprd12.prod.outlook.com (2603:10b6:a03:210::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5791.26; Mon, 7 Nov 2022 18:48:23 +0000 Received: from CY4PEPF0000B8EE.namprd05.prod.outlook.com (2603:10b6:8:54:cafe::fa) by DS7PR06CA0050.outlook.office365.com (2603:10b6:8:54::32) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5791.26 via Frontend Transport; Mon, 7 Nov 2022 18:48:22 +0000 X-MS-Exchange-Authentication-Results: spf=none (sender IP is 165.204.84.17) smtp.mailfrom=amd.com; dkim=none (message not signed) header.d=none;dmarc=fail action=quarantine header.from=amd.com; Received-SPF: None (protection.outlook.com: amd.com does not designate permitted sender hosts) Received: from SATLEXMB04.amd.com (165.204.84.17) by CY4PEPF0000B8EE.mail.protection.outlook.com (10.167.241.10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.20.5813.11 via Frontend Transport; Mon, 7 Nov 2022 18:48:21 +0000 Received: from khazad-dum.amd.com (10.180.168.240) by SATLEXMB04.amd.com (10.181.40.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Mon, 7 Nov 2022 12:48:19 -0600 From: Lancelot SIX To: CC: , Lancelot SIX Subject: [PATCH] gdb/py-inferior: Keep inferior threads in a map Date: Mon, 7 Nov 2022 18:47:27 +0000 Message-ID: <20221107184727.2228056-1-lancelot.six@amd.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Originating-IP: [10.180.168.240] X-ClientProxiedBy: SATLEXMB03.amd.com (10.181.40.144) To SATLEXMB04.amd.com (10.181.40.145) X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: CY4PEPF0000B8EE:EE_|BY5PR12MB4116:EE_ X-MS-Office365-Filtering-Correlation-Id: a3146bfc-5e0c-4eea-3374-08dac0f0a514 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: LGH38qsVoN3WIqFcc+nWOn0bQLn4CKEZ8ituUd35D/gilVxFHyuqIWH1LDs3k7Z3Xyhn7GLmWsjdHgSOduDfWpVcRDYWTU9bbpm9gYL9o8TS7W6x89E8AJV3QmuJDVLm/aDeyFly/BJ5P3JOYlvPmvmdoV5mwA0dPKM56wy31wvNhPNSSfNus166w3wnfv87G/RA2l1/FKSlmJiJI44fygcpytYfBMZCU2OWPRJvBfEfmeh05QehaixscBtZcWUa7xz2gaFNCwSxj0PiBFeSbBrI3Bbx+IKWTrAtaSx2kLhqvc8EsqBWk2wfkjVicULnfU7YvRxdrsaA82enYYRhttSZUCmM8e80PtN8JsXpwRj8K4EFRnZQeOhRz8kaqMj7fZC56v03S1+DouZmhMh/I/wz8p8nmUTbf5O7zDZilazMQ1CJYQ1s32o6sLKSQRtsPMHfLUTmtFCB+itDw7vs4rrxAQCsaVTiuEQwyVPyzgkieVzolubx9nwFIkvPzygaf+hFubM/8Q4uTi4EuWB7JwjoUN5MCr/l6UOWGI7An+x6CoLNp2NIiVIFHpH9VWmlGxD8FLhLLXKfdnmeretHPe4nzBsAPv5sqACHQ0/YufdCc/I3A5Aw1pTQciBH4r7S8Xevvp6IbgqjSsUUXSy8O6fQ2GgqnZc4vH2ZWOWNvdCiCxs14L5ITJxemt/7B6Me1btehf4uOnbtzv5rCL8mYfHMjhcnE8zP05yvWDjFeD2n7l5mdDQqIBWuQBAxN1hMaPVvjrQT7kbp0J5p8tQlUGdhrM2rIobqJsemuEDUQTtlFpaU+BwyRX/VAde1XWPB0kn/SIjnQVzed+pp2gA6FQ== X-Forefront-Antispam-Report: CIP:165.204.84.17;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:SATLEXMB04.amd.com;PTR:InfoDomainNonexistent;CAT:NONE;SFS:(13230022)(4636009)(376002)(39860400002)(396003)(136003)(346002)(451199015)(36840700001)(46966006)(40470700004)(36756003)(86362001)(82740400003)(356005)(81166007)(40460700003)(40480700001)(2906002)(5660300002)(26005)(7696005)(2616005)(6666004)(186003)(1076003)(16526019)(426003)(47076005)(336012)(83380400001)(36860700001)(66899015)(70586007)(70206006)(478600001)(6916009)(54906003)(82310400005)(966005)(41300700001)(8676002)(8936002)(316002)(4326008)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Nov 2022 18:48:21.9657 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: a3146bfc-5e0c-4eea-3374-08dac0f0a514 X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d;Ip=[165.204.84.17];Helo=[SATLEXMB04.amd.com] X-MS-Exchange-CrossTenant-AuthSource: CY4PEPF0000B8EE.namprd05.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR12MB4116 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: The python code maintains a list of threads for each inferior. This list is implemented as a linked list. When the number of threads grows high, this implementation can begin to be a performance bottleneck as finding a particular thread_object in the list has a complexity of O(N). We see this in ROCgdb[1], a downstream port of GDB for AMDGUP. On AMDGPU devices, the number of threads can get significantly higher than on usual GDB workloads. In some situations, we can reach the end of the inferior process with GDB still having a substantial list of known threads. While running target_mourn_inferior, we end up in inferior::clear_thread_list which iterates over all remaining threads and marks each thread exited. This fires the gdb::observers::thread_exit observer and eventually py-inferior.c:set_thread_exited gets called. This function searches in the linked list with poor performances. This patch proposes to change the linked list that keeps the per inferior_object list of thread_objects into a std::map. This allows to have the search operation complexity be O(log(N)) instead of O(N). With this patch, we can complete clear_thread_list in about 2.5 seconds compared to 10 minutes without it, while not seeing a significant negative impact on the insertion performance (which goes from O(1) to O(log(N))). Except for the performance change, no user visible change is expected. Regression tested on Ubuntu-22.04 x86_64. [1] https://github.com/ROCm-Developer-Tools/ROCgdb --- gdb/python/py-inferior.c | 95 ++++++++++++---------------------------- 1 file changed, 29 insertions(+), 66 deletions(-) diff --git a/gdb/python/py-inferior.c b/gdb/python/py-inferior.c index 8847a6d9308..9fd5f30fcdb 100644 --- a/gdb/python/py-inferior.c +++ b/gdb/python/py-inferior.c @@ -30,17 +30,9 @@ #include "gdbsupport/gdb_signals.h" #include "py-event.h" #include "py-stopevent.h" +#include -struct threadlist_entry -{ - threadlist_entry (gdbpy_ref &&ref) - : thread_obj (std::move (ref)) - { - } - - gdbpy_ref thread_obj; - struct threadlist_entry *next; -}; +using thread_map_t = std::map>; struct inferior_object { @@ -49,12 +41,9 @@ struct inferior_object /* The inferior we represent. */ struct inferior *inferior; - /* thread_object instances under this inferior. This list owns a + /* thread_object instances under this inferior. This owns a reference to each object it contains. */ - struct threadlist_entry *threads; - - /* Number of threads in the list. */ - int nthreads; + thread_map_t *threads; }; extern PyTypeObject inferior_object_type @@ -65,8 +54,6 @@ struct infpy_deleter { void operator() (inferior_object *obj) { - struct threadlist_entry *th_entry, *th_tmp; - if (!gdb_python_initialized) return; @@ -75,15 +62,7 @@ struct infpy_deleter inf_obj->inferior = NULL; - /* Deallocate threads list. */ - for (th_entry = inf_obj->threads; th_entry != NULL;) - { - th_tmp = th_entry; - th_entry = th_entry->next; - delete th_tmp; - } - - inf_obj->nthreads = 0; + delete inf_obj->threads; } }; @@ -257,8 +236,7 @@ inferior_to_inferior_object (struct inferior *inferior) return NULL; inf_obj->inferior = inferior; - inf_obj->threads = NULL; - inf_obj->nthreads = 0; + inf_obj->threads = new thread_map_t (); /* PyObject_New initializes the new object with a refcount of 1. This counts for the reference we are keeping in the inferior data. */ @@ -333,11 +311,10 @@ thread_to_thread_object (thread_info *thr) if (inf_obj == NULL) return NULL; - for (threadlist_entry *thread = inf_obj->threads; - thread != NULL; - thread = thread->next) - if (thread->thread_obj->thread == thr) - return gdbpy_ref<>::new_reference ((PyObject *) thread->thread_obj.get ()); + auto thread_it = inf_obj->threads->find (thr); + if (thread_it != inf_obj->threads->end ()) + return gdbpy_ref<>::new_reference + ((PyObject *) (thread_it->second.get ())); PyErr_SetString (PyExc_SystemError, _("could not find gdb thread object")); @@ -348,7 +325,6 @@ static void add_thread_object (struct thread_info *tp) { inferior_object *inf_obj; - struct threadlist_entry *entry; if (!gdb_python_initialized) return; @@ -364,18 +340,19 @@ add_thread_object (struct thread_info *tp) inf_obj = (inferior_object *) thread_obj->inf_obj; - entry = new threadlist_entry (std::move (thread_obj)); - entry->next = inf_obj->threads; + auto ins_result = inf_obj->threads->emplace + (thread_map_t::value_type (tp, std::move (thread_obj))); - inf_obj->threads = entry; - inf_obj->nthreads++; + if (!ins_result.second) + return; if (evregpy_no_listeners_p (gdb_py_events.new_thread)) return; - gdbpy_ref<> event = create_thread_event_object (&new_thread_event_object_type, - (PyObject *) - entry->thread_obj.get ()); + gdbpy_ref<> event = create_thread_event_object + (&new_thread_event_object_type, + (PyObject *) ins_result.first->second.get ()); + if (event == NULL || evpy_emit_event (event.get (), gdb_py_events.new_thread) < 0) gdbpy_print_stack (); @@ -384,8 +361,6 @@ add_thread_object (struct thread_info *tp) static void delete_thread_object (struct thread_info *tp, int ignore) { - struct threadlist_entry **entry, *tmp; - if (!gdb_python_initialized) return; @@ -395,29 +370,18 @@ delete_thread_object (struct thread_info *tp, int ignore) if (inf_obj == NULL) return; - /* Find thread entry in its inferior's thread_list. */ - for (entry = &inf_obj->threads; *entry != NULL; entry = - &(*entry)->next) - if ((*entry)->thread_obj->thread == tp) - break; - - if (!*entry) - return; - - tmp = *entry; - tmp->thread_obj->thread = NULL; - - *entry = (*entry)->next; - inf_obj->nthreads--; - - delete tmp; + auto it = inf_obj->threads->find (tp); + if (it != inf_obj->threads->end ()) + { + it->second->thread = nullptr; + inf_obj->threads->erase (it); + } } static PyObject * infpy_threads (PyObject *self, PyObject *args) { - int i; - struct threadlist_entry *entry; + int i = 0; inferior_object *inf_obj = (inferior_object *) self; PyObject *tuple; @@ -432,16 +396,15 @@ infpy_threads (PyObject *self, PyObject *args) GDB_PY_HANDLE_EXCEPTION (except); } - tuple = PyTuple_New (inf_obj->nthreads); + tuple = PyTuple_New (inf_obj->threads->size ()); if (!tuple) return NULL; - for (i = 0, entry = inf_obj->threads; i < inf_obj->nthreads; - i++, entry = entry->next) + for (const thread_map_t::value_type &entry : *inf_obj->threads) { - PyObject *thr = (PyObject *) entry->thread_obj.get (); + PyObject *thr = (PyObject *) entry.second.get (); Py_INCREF (thr); - PyTuple_SET_ITEM (tuple, i, thr); + PyTuple_SET_ITEM (tuple, i++, thr); } return tuple; base-commit: 91836f41e209a60a8a836faef2e7889e144df297 -- 2.34.1