From patchwork Mon Feb 24 19:36:38 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Simon Marchi X-Patchwork-Id: 38292 Received: (qmail 92167 invoked by alias); 24 Feb 2020 19:36:59 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Delivered-To: mailing list gdb-patches@sourceware.org Received: (qmail 92159 invoked by uid 89); 24 Feb 2020 19:36:59 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.1 spammy=collects, laurent, Laurent, measurement X-HELO: mail.efficios.com Received: from mail.efficios.com (HELO mail.efficios.com) (167.114.26.124) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 24 Feb 2020 19:36:57 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 4D7B325CBDF; Mon, 24 Feb 2020 14:36:55 -0500 (EST) Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id kz0wjx8rEjBW; Mon, 24 Feb 2020 14:36:54 -0500 (EST) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id C8A1A25CBDE; Mon, 24 Feb 2020 14:36:54 -0500 (EST) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com C8A1A25CBDE DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1582573014; bh=dsSPf03XfqPSmBLrJRmCE2HI5SK8Zy8SFMI6MnJR9Ek=; h=From:To:Date:Message-Id:MIME-Version; b=P/noavvHJ+YTXBVxngKV5drD4KASyax5ZgPX6sRu+y1CSMPV3imPLA6twNzN3syNd gd4YNe+kDaxiHE2N8BiGVMgTi9lmm3mLs/n2rgrfd2Gz4q1OVNILmZIXrYyXKglm6J RcwtDjRKN+cSa+/ZMYYwlN3J6ztTRx8CiC/a2Rt4yzS+wAhtLpHS2Ltp0Yg+WOSLSr Oujji1SQhkktsnY3bekFzqkEkBMETde+255e/h03BGaS5bzyIGZhB4KXOUUco5Cj8b w/KQnKnTxMHlY9XASiCF/ollNsH+boYyIccZxrP9Veddbd6f8tLWPjy1OI6vWCuMDv WPMv0BHnmA/rA== Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id aeLiFQQADcFI; Mon, 24 Feb 2020 14:36:54 -0500 (EST) Received: from smarchi-efficios.internal.efficios.com (192-222-181-218.qc.cable.ebox.net [192.222.181.218]) by mail.efficios.com (Postfix) with ESMTPSA id AE2A025CBDD; Mon, 24 Feb 2020 14:36:54 -0500 (EST) From: Simon Marchi To: gdb-patches@sourceware.org Cc: Laurent Morichetti Subject: [PATCH] gdb: infrun: consume multiple events at each pass in stop_all_threads Date: Mon, 24 Feb 2020 14:36:38 -0500 Message-Id: <20200224193638.29578-1-simon.marchi@efficios.com> MIME-Version: 1.0 From: Laurent Morichetti [Simon: I send this patch on behalf of Laurent Morichetti, I added the commit message and performance measurement stuff. Also, this patch is better viewed with "git show -w".] stop_all_threads, in infrun.c, is used to stop all running threads on targets that are always non-stop. It's used, for example, when the program hits a breakpoint while GDB is set to "non-stop off". It sends a stop request for each running thread, then collects one wait event for each. Since new threads can spawn while we are stopping the threads, it's written in a way where it makes multiple such "send stop requests to running threads & collect wait events" passes. The function completes when it has made two passes where it hasn't seen any running threads. With the way it's written right now is, it iterates on the thread list, sending a stop request for each running thread. It then waits for a single event, after which it iterates through the thread list again. It sends stop requests for any running threads that's been created since the last iteration. It then consumes another single wait event. This makes it so we iterate on O(n^2) threads in total, where n is the number of threads. This patch changes the function to reduce it to O(n). This starts to have an impact when dealing with multiple thousands of threads (see numbers below). At each pass, we know the number of outstanding stop requests we have sent, for which we need to collect a stop event. We can therefore loop to collect this many stop events before proceeding to the next pass and iterate on the thread list again. To check the performance improvements with this patch, I made an x86/Linux program with a large number of idle threads (varying from 1000 to 10000). The program's main thread hits a breakpoint once all these threads have started, which causes stop_all_threads to be called to stop all these threads. I measured (by patching stop_all_threads): - the execution time of stop_all_threads - the total number of threads we iterate on during the complete execution of the function (the total number of times we execute the "for (thread_info *t : all_non_exited_threads ())" loop) These are the execution times, in milliseconds: # threads before after 1000 226 106 2000 997 919 3000 3461 2323 4000 4330 3570 5000 8642 6600 6000 9918 8039 7000 12662 10930 8000 16652 11222 9000 21561 15875 10000 26613 20019 Note that I very unscientifically executed each case only once. These are the number of loop executions: # threads before after 1000 1003002 3003 2000 4006002 6003 3000 9009002 9003 4000 16012002 12003 5000 25015002 15003 6000 36018002 18003 7000 49021002 21003 8000 64024002 24003 9000 81027002 27003 10000 100030002 30003 This last table shows pretty well the O(n^2) vs O(n) behaviors. Reg-tested on x86 GNU/Linux (Ubuntu 16.04). gdb/ChangeLog: YYYY-MM-DD Laurent Morichetti YYYY-MM-DD Simon Marchi * infrun.c (stop_all_threads): Collect multiple wait events at each pass. --- gdb/infrun.c | 184 ++++++++++++++++++++++++++------------------------- 1 file changed, 94 insertions(+), 90 deletions(-) diff --git a/gdb/infrun.c b/gdb/infrun.c index d9a6f7335194..326678fe6fe2 100644 --- a/gdb/infrun.c +++ b/gdb/infrun.c @@ -4701,7 +4701,7 @@ stop_all_threads (void) "iterations=%d\n", pass, iterations); while (1) { - int need_wait = 0; + int waits_needed = 0; update_thread_list (); @@ -4734,7 +4734,7 @@ stop_all_threads (void) } if (t->stop_requested) - need_wait = 1; + waits_needed++; } else { @@ -4749,7 +4749,7 @@ stop_all_threads (void) } } - if (!need_wait) + if (waits_needed == 0) break; /* If we find new threads on the second iteration, restart @@ -4758,110 +4758,114 @@ stop_all_threads (void) if (pass > 0) pass = -1; - wait_one_event event = wait_one (); - - if (debug_infrun) + for (int i = 0; i < waits_needed; i++) { - fprintf_unfiltered (gdb_stdlog, - "infrun: stop_all_threads %s %s\n", - target_waitstatus_to_string (&event.ws).c_str (), - target_pid_to_str (event.ptid).c_str ()); - } + wait_one_event event = wait_one (); - if (event.ws.kind == TARGET_WAITKIND_NO_RESUMED - || event.ws.kind == TARGET_WAITKIND_THREAD_EXITED - || event.ws.kind == TARGET_WAITKIND_EXITED - || event.ws.kind == TARGET_WAITKIND_SIGNALLED) - { - /* All resumed threads exited - or one thread/process exited/signalled. */ - } - else - { - thread_info *t = find_thread_ptid (event.target, event.ptid); - if (t == NULL) - t = add_thread (event.target, event.ptid); - - t->stop_requested = 0; - t->executing = 0; - t->resumed = false; - t->control.may_range_step = 0; - - /* This may be the first time we see the inferior report - a stop. */ - inferior *inf = find_inferior_ptid (event.target, event.ptid); - if (inf->needs_setup) + if (debug_infrun) { - switch_to_thread_no_regs (t); - setup_inferior (0); + fprintf_unfiltered (gdb_stdlog, + "infrun: stop_all_threads %s %s\n", + target_waitstatus_to_string (&event.ws).c_str (), + target_pid_to_str (event.ptid).c_str ()); } - if (event.ws.kind == TARGET_WAITKIND_STOPPED - && event.ws.value.sig == GDB_SIGNAL_0) + if (event.ws.kind == TARGET_WAITKIND_NO_RESUMED + || event.ws.kind == TARGET_WAITKIND_THREAD_EXITED + || event.ws.kind == TARGET_WAITKIND_EXITED + || event.ws.kind == TARGET_WAITKIND_SIGNALLED) { - /* We caught the event that we intended to catch, so - there's no event pending. */ - t->suspend.waitstatus.kind = TARGET_WAITKIND_IGNORE; - t->suspend.waitstatus_pending_p = 0; - - if (displaced_step_fixup (t, GDB_SIGNAL_0) < 0) - { - /* Add it back to the step-over queue. */ - if (debug_infrun) - { - fprintf_unfiltered (gdb_stdlog, - "infrun: displaced-step of %s " - "canceled: adding back to the " - "step-over queue\n", - target_pid_to_str (t->ptid).c_str ()); - } - t->control.trap_expected = 0; - thread_step_over_chain_enqueue (t); - } + /* All resumed threads exited + or one thread/process exited/signalled. */ + break; } else { - enum gdb_signal sig; - struct regcache *regcache; + thread_info *t = find_thread_ptid (event.target, event.ptid); + if (t == NULL) + t = add_thread (event.target, event.ptid); - if (debug_infrun) + t->stop_requested = 0; + t->executing = 0; + t->resumed = false; + t->control.may_range_step = 0; + + /* This may be the first time we see the inferior report + a stop. */ + inferior *inf = find_inferior_ptid (event.target, event.ptid); + if (inf->needs_setup) { - std::string statstr = target_waitstatus_to_string (&event.ws); - - fprintf_unfiltered (gdb_stdlog, - "infrun: target_wait %s, saving " - "status for %d.%ld.%ld\n", - statstr.c_str (), - t->ptid.pid (), - t->ptid.lwp (), - t->ptid.tid ()); + switch_to_thread_no_regs (t); + setup_inferior (0); } - /* Record for later. */ - save_waitstatus (t, &event.ws); - - sig = (event.ws.kind == TARGET_WAITKIND_STOPPED - ? event.ws.value.sig : GDB_SIGNAL_0); - - if (displaced_step_fixup (t, sig) < 0) + if (event.ws.kind == TARGET_WAITKIND_STOPPED + && event.ws.value.sig == GDB_SIGNAL_0) { - /* Add it back to the step-over queue. */ - t->control.trap_expected = 0; - thread_step_over_chain_enqueue (t); + /* We caught the event that we intended to catch, so + there's no event pending. */ + t->suspend.waitstatus.kind = TARGET_WAITKIND_IGNORE; + t->suspend.waitstatus_pending_p = 0; + + if (displaced_step_fixup (t, GDB_SIGNAL_0) < 0) + { + /* Add it back to the step-over queue. */ + if (debug_infrun) + { + fprintf_unfiltered (gdb_stdlog, + "infrun: displaced-step of %s " + "canceled: adding back to the " + "step-over queue\n", + target_pid_to_str (t->ptid).c_str ()); + } + t->control.trap_expected = 0; + thread_step_over_chain_enqueue (t); + } } + else + { + enum gdb_signal sig; + struct regcache *regcache; - regcache = get_thread_regcache (t); - t->suspend.stop_pc = regcache_read_pc (regcache); + if (debug_infrun) + { + std::string statstr = target_waitstatus_to_string (&event.ws); - if (debug_infrun) - { - fprintf_unfiltered (gdb_stdlog, - "infrun: saved stop_pc=%s for %s " - "(currently_stepping=%d)\n", - paddress (target_gdbarch (), - t->suspend.stop_pc), - target_pid_to_str (t->ptid).c_str (), - currently_stepping (t)); + fprintf_unfiltered (gdb_stdlog, + "infrun: target_wait %s, saving " + "status for %d.%ld.%ld\n", + statstr.c_str (), + t->ptid.pid (), + t->ptid.lwp (), + t->ptid.tid ()); + } + + /* Record for later. */ + save_waitstatus (t, &event.ws); + + sig = (event.ws.kind == TARGET_WAITKIND_STOPPED + ? event.ws.value.sig : GDB_SIGNAL_0); + + if (displaced_step_fixup (t, sig) < 0) + { + /* Add it back to the step-over queue. */ + t->control.trap_expected = 0; + thread_step_over_chain_enqueue (t); + } + + regcache = get_thread_regcache (t); + t->suspend.stop_pc = regcache_read_pc (regcache); + + if (debug_infrun) + { + fprintf_unfiltered (gdb_stdlog, + "infrun: saved stop_pc=%s for %s " + "(currently_stepping=%d)\n", + paddress (target_gdbarch (), + t->suspend.stop_pc), + target_pid_to_str (t->ptid).c_str (), + currently_stepping (t)); + } } } }