From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7833) id 91C413836651; Fri, 11 Nov 2022 13:55:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 91C413836651 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1668174911; bh=2pHigAVseLN6DymYZkVEqvACu2R5d9IF4kJIjGHwGU0=; h=From:To:Subject:Date:From; b=axtAq/84rt9zcooHfewDWWIfIw+R7/mQGjKui6jD0b8cCjZc+GSVs5lix9HePpT+K 6ra5D1qURWgxstWoMi1lbKghpJt0w15nmqYBfq6skafIzBbO1ZobZZwWUsznQhdbmB Yy82ML5Rb2kRRk7bPSce19tYBJisylFZXh9Ued9I= Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Lancelot SIX To: gdb-cvs@sourceware.org Subject: [binutils-gdb] gdb/py-inferior: Keep inferior threads in a map X-Act-Checkin: binutils-gdb X-Git-Author: Lancelot SIX X-Git-Refname: refs/heads/master X-Git-Oldrev: 1e5ccb9c5ff4fd8ade4a8694676f99f4abf2d679 X-Git-Newrev: 40b355f24ec288c29bc9d3dd569758b5e80b51e3 Message-Id: <20221111135511.91C413836651@sourceware.org> Date: Fri, 11 Nov 2022 13:55:11 +0000 (GMT) List-Id: https://sourceware.org/git/gitweb.cgi?p=3Dbinutils-gdb.git;h=3D40b355f24ec2= 88c29bc9d3dd569758b5e80b51e3 commit 40b355f24ec288c29bc9d3dd569758b5e80b51e3 Author: Lancelot SIX Date: Mon Nov 7 14:10:58 2022 +0000 gdb/py-inferior: Keep inferior threads in a map =20 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). =20 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. =20 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. =20 This patch proposes to change the linked list that keeps the per inferior_object list of thread_objects into a std::unordered_map. This allows to have the search operation complexity be O(1) on average instead of O(N). =20 With this patch, we can complete clear_thread_list in about 2.5 seconds compared to 10 minutes without it. =20 Except for the performance change, no user visible change is expected. =20 Regression tested on Ubuntu-22.04 x86_64. =20 [1] https://github.com/ROCm-Developer-Tools/ROCgdb Diff: --- gdb/python/py-inferior.c | 99 +++++++++++++++++---------------------------= ---- 1 file changed, 34 insertions(+), 65 deletions(-) diff --git a/gdb/python/py-inferior.c b/gdb/python/py-inferior.c index 8847a6d9308..4d5e09db680 100644 --- a/gdb/python/py-inferior.c +++ b/gdb/python/py-inferior.c @@ -30,17 +30,10 @@ #include "gdbsupport/gdb_signals.h" #include "py-event.h" #include "py-stopevent.h" +#include =20 -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 + =3D std::unordered_map>; =20 struct inferior_object { @@ -49,12 +42,9 @@ struct inferior_object /* The inferior we represent. */ struct inferior *inferior; =20 - /* 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; }; =20 extern PyTypeObject inferior_object_type @@ -65,8 +55,6 @@ struct infpy_deleter { void operator() (inferior_object *obj) { - struct threadlist_entry *th_entry, *th_tmp; - if (!gdb_python_initialized) return; =20 @@ -75,15 +63,7 @@ struct infpy_deleter =20 inf_obj->inferior =3D NULL; =20 - /* Deallocate threads list. */ - for (th_entry =3D inf_obj->threads; th_entry !=3D NULL;) - { - th_tmp =3D th_entry; - th_entry =3D th_entry->next; - delete th_tmp; - } - - inf_obj->nthreads =3D 0; + delete inf_obj->threads; } }; =20 @@ -257,8 +237,7 @@ inferior_to_inferior_object (struct inferior *inferior) return NULL; =20 inf_obj->inferior =3D inferior; - inf_obj->threads =3D NULL; - inf_obj->nthreads =3D 0; + inf_obj->threads =3D new thread_map_t (); =20 /* PyObject_New initializes the new object with a refcount of 1. Th= is counts for the reference we are keeping in the inferior data. */ @@ -333,11 +312,10 @@ thread_to_thread_object (thread_info *thr) if (inf_obj =3D=3D NULL) return NULL; =20 - for (threadlist_entry *thread =3D inf_obj->threads; - thread !=3D NULL; - thread =3D thread->next) - if (thread->thread_obj->thread =3D=3D thr) - return gdbpy_ref<>::new_reference ((PyObject *) thread->thread_obj.g= et ()); + auto thread_it =3D inf_obj->threads->find (thr); + if (thread_it !=3D inf_obj->threads->end ()) + return gdbpy_ref<>::new_reference + ((PyObject *) (thread_it->second.get ())); =20 PyErr_SetString (PyExc_SystemError, _("could not find gdb thread object")); @@ -348,7 +326,6 @@ static void add_thread_object (struct thread_info *tp) { inferior_object *inf_obj; - struct threadlist_entry *entry; =20 if (!gdb_python_initialized) return; @@ -364,18 +341,19 @@ add_thread_object (struct thread_info *tp) =20 inf_obj =3D (inferior_object *) thread_obj->inf_obj; =20 - entry =3D new threadlist_entry (std::move (thread_obj)); - entry->next =3D inf_obj->threads; + auto ins_result =3D inf_obj->threads->emplace + (thread_map_t::value_type (tp, std::move (thread_obj))); =20 - inf_obj->threads =3D entry; - inf_obj->nthreads++; + if (!ins_result.second) + return; =20 if (evregpy_no_listeners_p (gdb_py_events.new_thread)) return; =20 - gdbpy_ref<> event =3D create_thread_event_object (&new_thread_event_obje= ct_type, - (PyObject *) - entry->thread_obj.get ()); + gdbpy_ref<> event =3D create_thread_event_object + (&new_thread_event_object_type, + (PyObject *) ins_result.first->second.get ()); + if (event =3D=3D NULL || evpy_emit_event (event.get (), gdb_py_events.new_thread) < 0) gdbpy_print_stack (); @@ -384,8 +362,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; =20 @@ -395,29 +371,22 @@ delete_thread_object (struct thread_info *tp, int ign= ore) if (inf_obj =3D=3D NULL) return; =20 - /* Find thread entry in its inferior's thread_list. */ - for (entry =3D &inf_obj->threads; *entry !=3D NULL; entry =3D - &(*entry)->next) - if ((*entry)->thread_obj->thread =3D=3D tp) - break; - - if (!*entry) - return; - - tmp =3D *entry; - tmp->thread_obj->thread =3D NULL; - - *entry =3D (*entry)->next; - inf_obj->nthreads--; - - delete tmp; + auto it =3D inf_obj->threads->find (tp); + if (it !=3D inf_obj->threads->end ()) + { + /* Some python code can still hold a reference to the thread_object + instance. Make sure to remove the link to the associated + thread_info object as it will be freed soon. This makes the python + object invalid (i.e. gdb.InfThread.is_valid returns False). */ + it->second->thread =3D nullptr; + inf_obj->threads->erase (it); + } } =20 static PyObject * infpy_threads (PyObject *self, PyObject *args) { - int i; - struct threadlist_entry *entry; + int i =3D 0; inferior_object *inf_obj =3D (inferior_object *) self; PyObject *tuple; =20 @@ -432,16 +401,16 @@ infpy_threads (PyObject *self, PyObject *args) GDB_PY_HANDLE_EXCEPTION (except); } =20 - tuple =3D PyTuple_New (inf_obj->nthreads); + tuple =3D PyTuple_New (inf_obj->threads->size ()); if (!tuple) return NULL; =20 - for (i =3D 0, entry =3D inf_obj->threads; i < inf_obj->nthreads; - i++, entry =3D entry->next) + for (const thread_map_t::value_type &entry : *inf_obj->threads) { - PyObject *thr =3D (PyObject *) entry->thread_obj.get (); + PyObject *thr =3D (PyObject *) entry.second.get (); Py_INCREF (thr); PyTuple_SET_ITEM (tuple, i, thr); + i =3D i + 1; } =20 return tuple;