From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca by simark.ca with LMTP id +K+2GZkX0mAtYAAAWB0awg (envelope-from ) for ; Tue, 22 Jun 2021 13:02:17 -0400 Received: by simark.ca (Postfix, from userid 112) id 676821F1F2; Tue, 22 Jun 2021 13:02:17 -0400 (EDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on simark.ca X-Spam-Level: X-Spam-Status: No, score=-0.7 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,MAILING_LIST_MULTI,RDNS_DYNAMIC,URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.2 Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPS id 0C3481E54D for ; Tue, 22 Jun 2021 13:02:17 -0400 (EDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C2CD43838017 for ; Tue, 22 Jun 2021 17:02:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C2CD43838017 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624381336; bh=kVAxEXIT/fn9px/Of/Fx8VfsYlNEenWSZezo4QbPGkY=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=cEVZ6kldqqqu6P7IN8nBG9CZeo7o/qU8oFrvIyS0yGB1hQxsTyu7jGjFjdGhxpMjD dex216TcovlHVmAMzX78F29fqb69bYQHqDyObMwa/56OQZyfr3CoqGOQ0DnbYPJ1ex D0msgWlnlNBcL4HNIg7iu4x6TUTG7PzQrTWn4obg= Received: from barracuda.ebox.ca (barracuda.ebox.ca [96.127.255.19]) by sourceware.org (Postfix) with ESMTPS id F20F53851C19 for ; Tue, 22 Jun 2021 16:59:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F20F53851C19 X-ASG-Debug-ID: 1624381146-0c856e6cd5194fb90001-fS2M51 Received: from smtp.ebox.ca (smtp.ebox.ca [96.127.255.82]) by barracuda.ebox.ca with ESMTP id 5ziua1pgqNCsH0Hm (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 22 Jun 2021 12:59:07 -0400 (EDT) X-Barracuda-Envelope-From: simon.marchi@polymtl.ca X-Barracuda-RBL-Trusted-Forwarder: 96.127.255.82 Received: from simark.localdomain (192-222-157-6.qc.cable.ebox.net [192.222.157.6]) by smtp.ebox.ca (Postfix) with ESMTP id EE008441D64; Tue, 22 Jun 2021 12:59:06 -0400 (EDT) X-Barracuda-RBL-IP: 192.222.157.6 X-Barracuda-Effective-Source-IP: 192-222-157-6.qc.cable.ebox.net[192.222.157.6] X-Barracuda-Apparent-Source-IP: 192.222.157.6 To: gdb-patches@sourceware.org Subject: [PATCH 09/11] gdb: optimize selection of resumed thread with pending event Date: Tue, 22 Jun 2021 12:57:02 -0400 X-ASG-Orig-Subj: [PATCH 09/11] gdb: optimize selection of resumed thread with pending event Message-Id: <20210622165704.2404007-10-simon.marchi@polymtl.ca> X-Mailer: git-send-email 2.32.0 In-Reply-To: <20210622165704.2404007-1-simon.marchi@polymtl.ca> References: <20210622165704.2404007-1-simon.marchi@polymtl.ca> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Barracuda-Connect: smtp.ebox.ca[96.127.255.82] X-Barracuda-Start-Time: 1624381147 X-Barracuda-Encrypted: DHE-RSA-AES256-SHA X-Barracuda-URL: https://96.127.255.19:443/cgi-mod/mark.cgi X-Barracuda-BRTS-Status: 1 X-Virus-Scanned: by bsmtpd at ebox.ca X-Barracuda-Scan-Msg-Size: 6947 X-Barracuda-Spam-Score: 0.00 X-Barracuda-Spam-Status: No, SCORE=0.00 using global scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=8.0 tests= X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.90826 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 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: , From: Simon Marchi via Gdb-patches Reply-To: Simon Marchi Errors-To: gdb-patches-bounces+public-inbox=simark.ca@sourceware.org Sender: "Gdb-patches" Consider a case where many threads (thousands) keep hitting a breakpoint whose condition evaluates to false. random_pending_event_thread is responsible for selecting a thread from an inferior among all that are resumed with a pending wait status. It is currently implemented by walking the inferior's thread list twice: once to count the number of candidates and once to select a random one. Since we now maintain a per target list of resumed threads with pending event, we can implement this more efficiently by walking that list and selecting the first thread that matches the criteria (random_pending_event_thread looks for an thread from a specific inferior, and possibly a filter ptid). It will be faster especially in the common case where there isn't any resumed thread with pending event. Currently, we have to iterate the thread list to figure this out. With this patch, the list of resumed threads with pending event will be empty, so it's quick to figure out. The random selection is kept, but is moved to process_stratum_target::random_resumed_with_pending_wait_status. The same technique is used: do a first pass to count the number of candidates, and do a second pass to select a random one. But given that the list of resumed threads with pending wait statuses will generally be short, or at least shorter than the full thread list, it should be quicker. Note that this isn't completely true, in case there are multiple inferiors on the same target. Imagine that inferior A has 10k resumed threads with pending wait statuses, and random_pending_event_thread is called with inferior B. We'll need to go through the list that contains inferior A's threads to realize that inferior B has no resumed threads with pending wait status. But I think that this is a corner / pathological case. And a possible fix for this situation would be to make random_pending_event_thread work per-process-target, rather than per-inferior. gdb/ChangeLog: * process-stratum-target.h (class process_stratum_target) : New. * process-stratum-target.c (process_stratum_target::random_resumed_with_pending_wait_status): New. * infrun.c (random_pending_event_thread): Use random_resumed_with_pending_wait_status. Change-Id: I1b71d01beaa500a148b5b9797745103e13917325 --- gdb/infrun.c | 40 +++++++++------------------------ gdb/process-stratum-target.c | 43 ++++++++++++++++++++++++++++++++++++ gdb/process-stratum-target.h | 5 +++++ 3 files changed, 59 insertions(+), 29 deletions(-) diff --git a/gdb/infrun.c b/gdb/infrun.c index 657f97e23fbb..80834fed1e3b 100644 --- a/gdb/infrun.c +++ b/gdb/infrun.c @@ -3493,39 +3493,21 @@ print_target_wait_results (ptid_t waiton_ptid, ptid_t result_ptid, static struct thread_info * random_pending_event_thread (inferior *inf, ptid_t waiton_ptid) { - int num_events = 0; + process_stratum_target *proc_target = inf->process_target (); + thread_info *thread + = proc_target->random_resumed_with_pending_wait_status (inf, waiton_ptid); - auto has_event = [&] (thread_info *tp) + if (thread == nullptr) { - return (tp->ptid.matches (waiton_ptid) - && tp->resumed () - && tp->has_pending_waitstatus ()); - }; - - /* First see how many events we have. Count only resumed threads - that have an event pending. */ - for (thread_info *tp : inf->non_exited_threads ()) - if (has_event (tp)) - num_events++; - - if (num_events == 0) - return NULL; - - /* Now randomly pick a thread out of those that have had events. */ - int random_selector = (int) ((num_events * (double) rand ()) - / (RAND_MAX + 1.0)); - - if (num_events > 1) - infrun_debug_printf ("Found %d events, selecting #%d", - num_events, random_selector); + infrun_debug_printf ("None found."); + return nullptr; + } - /* Select the Nth thread that has had an event. */ - for (thread_info *tp : inf->non_exited_threads ()) - if (has_event (tp)) - if (random_selector-- == 0) - return tp; + infrun_debug_printf ("Found %s.", target_pid_to_str (thread->ptid).c_str ()); + gdb_assert (thread->resumed ()); + gdb_assert (thread->has_pending_waitstatus ()); - gdb_assert_not_reached ("event thread not found"); + return thread; } /* Wrapper for target_wait that first checks whether threads have diff --git a/gdb/process-stratum-target.c b/gdb/process-stratum-target.c index 44e138273b2f..c828da0f3bca 100644 --- a/gdb/process-stratum-target.c +++ b/gdb/process-stratum-target.c @@ -20,6 +20,7 @@ #include "defs.h" #include "process-stratum-target.h" #include "inferior.h" +#include process_stratum_target::~process_stratum_target () { @@ -140,6 +141,48 @@ process_stratum_target::maybe_remove_resumed_with_pending_wait_status /* See process-stratum-target.h. */ +thread_info * +process_stratum_target::random_resumed_with_pending_wait_status + (inferior *inf, ptid_t filter_ptid) +{ + auto matches = [inf, filter_ptid] (const thread_info &thread) + { + return thread.inf == inf && thread.ptid.matches (filter_ptid); + }; + + /* First see how many matching events we have. */ + const auto &l = m_resumed_with_pending_wait_status; + unsigned int count = std::count_if (l.begin (), l.end (), matches); + + if (count == 0) + return nullptr; + + /* Now randomly pick a thread out of those that match the criteria. */ + int random_selector + = (int) ((count * (double) rand ()) / (RAND_MAX + 1.0)); + + if (count > 1) + infrun_debug_printf ("Found %u events, selecting #%d", + count, random_selector); + + /* Select the Nth thread that matches. */ + auto it = std::find_if (l.begin (), l.end (), + [&random_selector, &matches] + (const thread_info &thread) + { + if (!matches (thread)) + return false; + + return random_selector-- == 0; + }); + + gdb_assert (it != l.end ()); + + return &*it; +} + +/* See process-stratum-target.h. */ + std::set all_non_exited_process_targets () { diff --git a/gdb/process-stratum-target.h b/gdb/process-stratum-target.h index c73207e0531e..4d1d14f7a94f 100644 --- a/gdb/process-stratum-target.h +++ b/gdb/process-stratum-target.h @@ -93,6 +93,11 @@ class process_stratum_target : public target_ops bool has_resumed_with_pending_wait_status () const { return !m_resumed_with_pending_wait_status.empty (); } + /* Return a random resumed thread with pending wait status belonging to INF + and matching FILTER_PTID. */ + thread_info *random_resumed_with_pending_wait_status + (inferior *inf, ptid_t filter_ptid); + /* The connection number. Visible in "info connections". */ int connection_number = 0; -- 2.32.0