From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7918 invoked by alias); 19 May 2016 14:57:08 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 7869 invoked by uid 89); 19 May 2016 14:57:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.3 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=010, 0.10, Previous, spending X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Thu, 19 May 2016 14:57:02 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id E6B197AE82 for ; Thu, 19 May 2016 14:48:15 +0000 (UTC) Received: from cascais.lan (ovpn01.gateway.prod.ext.ams2.redhat.com [10.39.146.11]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u4JEmBLr009731 for ; Thu, 19 May 2016 10:48:15 -0400 From: Pedro Alves To: gdb-patches@sourceware.org Subject: [PATCH 4/6] [Linux] Optimize PID -> struct lwp_info lookup Date: Thu, 19 May 2016 14:57:00 -0000 Message-Id: <1463669290-30415-5-git-send-email-palves@redhat.com> In-Reply-To: <1463669290-30415-1-git-send-email-palves@redhat.com> References: <1463669290-30415-1-git-send-email-palves@redhat.com> X-SW-Source: 2016-05/txt/msg00334.txt.bz2 Hacking the gdb.threads/attach-many-short-lived-threads.exp test to spawn thousands of threads instead of dozens, and running gdb under perf, I saw that GDB was spending most of the time in find_lwp_pid: - captured_main - 93.61% catch_command_errors - 87.41% attach_command - 87.40% linux_nat_attach - 87.40% linux_proc_attach_tgid_threads - 82.38% attach_proc_task_lwp_callback - 81.01% find_lwp_pid 5.30% ptid_get_lwp + 0.10% ptid_lwp_p + 0.64% add_thread + 0.26% set_running + 0.24% set_executing 0.12% ptid_get_lwp + 0.01% ptrace + 0.01% add_lwp attach_proc_task_lwp_callback is called once for each LWP that we attach to, found by listing the /proc/PID/task/ directory. In turn, attach_proc_task_lwp_callback calls find_lwp_pid to check whether the LWP we're about to try to attach to is already known. Since find_lwp_pid does a linear walk over the whole LWP list, this becomes quadratic. We do the /proc/PID/task/ listing until we get two iterations in a row where we found no new threads. So the second and following times we walk the /proc/PID/task/ dir, we're going to take an even worse find_lwp_pid hit. Fix this by keeping a list of LWPs sorted by PID, so we can use binary searches for lookup. The linked list embedded in the LWP structure itself is kept, and made a double-linked list, so that removals from that list are O(1). An earlier version of this patch got rid of this list altogether, but that revealed hidden dependencies / assumptions on how the list is sorted. For example, killing a process and then waiting for all the LWPs status using iterate_over_lwps only works as is because the leader LWP is always last in the list. So I thought it better to take an incremental approach and make this patch concern itself _only_ with the PID lookup optimization. gdb/ChangeLog: yyyy-mm-dd Pedro Alves PR gdb/19828 * linux-nat.c (lwp_info_p): New typedef. (lwp_list_by_lwpid): New VEC. (lwp_list): Tweak comment. (lwp_list_add, lwp_list_remove): New functions. (purge_lwp_list): Rewrite, walk the sorted-by-lwpid list instead. (lp_lwpid_lessthan): New. (add_initial_lwp): Add lwp to sorted-by-lwpid list too. Use lwp_list_add. (lwp_lwpid_cmp, find_lwp_by_lwpid_index): New functions. (delete_lwp): Use lwp_list_remove. Remove lwp from sorted-by-lwpid list too. (find_lwp_pid): Search in the sorted-by-lwpid list. * linux-nat.h (struct lwp_info) : New field. --- gdb/linux-nat.c | 159 ++++++++++++++++++++++++++++++++++++++++++++------------ gdb/linux-nat.h | 4 +- 2 files changed, 128 insertions(+), 35 deletions(-) diff --git a/gdb/linux-nat.c b/gdb/linux-nat.c index 509212e..ea2e4dc 100644 --- a/gdb/linux-nat.c +++ b/gdb/linux-nat.c @@ -677,8 +677,46 @@ linux_child_set_syscall_catchpoint (struct target_ops *self, return 0; } -/* List of known LWPs. */ +typedef struct lwp_info *lwp_info_p; + +DEF_VEC_P(lwp_info_p); + +/* List of known LWPs, sorted by LWP PID. This speeds up the common + case of mapping a PID returned from the kernel to our corresponding + lwp_info data structure. */ +static VEC(lwp_info_p) *lwp_list_by_lwpid; + +/* Head of double-linked list of known LWPs. Sorted by reverse + creation order. This order is assumed in some cases. E.g., + reaping status after killing alls lwps of a process: the leader LWP + must be reaped last. */ struct lwp_info *lwp_list; + +/* Add LP to sorted-by-creation-order double-linked list. */ + +static void +lwp_list_add (struct lwp_info *lp) +{ + lp->next = lwp_list; + if (lwp_list != NULL) + lwp_list->prev = lp; + lwp_list = lp; +} + +/* Remove LP from sorted-by-creation-order double-linked list. */ + +static void +lwp_list_remove (struct lwp_info *lp) +{ + /* Remove from sorted-by-creation-order list. */ + if (lp->next != NULL) + lp->next->prev = lp->prev; + if (lp->prev != NULL) + lp->prev->next = lp->next; + if (lp == lwp_list) + lwp_list = lp->next; +} + /* Original signal mask. */ @@ -759,26 +797,36 @@ lwp_free (struct lwp_info *lp) static void purge_lwp_list (int pid) { - struct lwp_info *lp, *lpprev, *lpnext; - - lpprev = NULL; + struct lwp_info **base = VEC_address (lwp_info_p, lwp_list_by_lwpid); + struct lwp_info **lp_out_p; + struct lwp_info *lp_in; + int ix; - for (lp = lwp_list; lp; lp = lpnext) + lp_out_p = base; + for (ix = 0; VEC_iterate (lwp_info_p, lwp_list_by_lwpid, ix, lp_in); ix++) { - lpnext = lp->next; - - if (ptid_get_pid (lp->ptid) == pid) + if (ptid_get_pid (lp_in->ptid) == pid) { - if (lp == lwp_list) - lwp_list = lp->next; - else - lpprev->next = lp->next; - - lwp_free (lp); + lwp_list_remove (lp_in); + lwp_free (lp_in); } else - lpprev = lp; + { + *lp_out_p = lp_in; + lp_out_p++; + } } + + VEC_truncate (lwp_info_p, lwp_list_by_lwpid, lp_out_p - base); +} + +/* Predicate function which returns true if LHS should sort before RHS + in a list of memory regions, useful for VEC_lower_bound. */ + +static int +lp_lwpid_lessthan (struct lwp_info *lhs, struct lwp_info *rhs) +{ + return ptid_get_lwp (lhs->ptid) < ptid_get_lwp (rhs->ptid); } /* Add the LWP specified by PTID to the list. PTID is the first LWP @@ -799,6 +847,7 @@ static struct lwp_info * add_initial_lwp (ptid_t ptid) { struct lwp_info *lp; + int ix; gdb_assert (ptid_lwp_p (ptid)); @@ -812,8 +861,13 @@ add_initial_lwp (ptid_t ptid) lp->ptid = ptid; lp->core = -1; - lp->next = lwp_list; - lwp_list = lp; + /* Add to sorted-by-creation-order list. */ + lwp_list_add (lp); + + /* Add to sorted-by-lwpid list too. */ + ix = VEC_lower_bound (lwp_info_p, lwp_list_by_lwpid, lp, + lp_lwpid_lessthan); + VEC_safe_insert (lwp_info_p, lwp_list_by_lwpid, ix, lp); return lp; } @@ -839,27 +893,65 @@ add_lwp (ptid_t ptid) return lp; } +/* Bsearch comparison function for lwp_list_by_lwpid. */ + +static int +lwp_lwpid_cmp (const void *key, const void *elt) +{ + const long lwpid_key = *(long *) key; + const struct lwp_info *lp = *(const struct lwp_info **) elt; + const long lwpid_lp = ptid_get_lwp (lp->ptid); + + if (lwpid_key < lwpid_lp) + return -1; + if (lwpid_key > lwpid_lp) + return 1; + return 0; +} + +/* Find an LWP in the sorted-by-lwpid LWP vector. Returns vector + index if found, or -1 if not found. */ + +static int +find_lwp_by_lwpid_index (long lwpid) +{ + struct lwp_info **found_p; + struct lwp_info **base; + size_t nmemb; + size_t size; + + base = VEC_address (lwp_info_p, lwp_list_by_lwpid); + nmemb = VEC_length (lwp_info_p, lwp_list_by_lwpid); + size = sizeof (struct lwp_info **); + found_p = (struct lwp_info **) bsearch (&lwpid, base, nmemb, + size, lwp_lwpid_cmp); + if (found_p != NULL) + return found_p - base; + + return -1; +} + /* Remove the LWP specified by PID from the list. */ static void delete_lwp (ptid_t ptid) { - struct lwp_info *lp, *lpprev; + struct lwp_info *lp; + int ix; - lpprev = NULL; + ix = find_lwp_by_lwpid_index (ptid_get_lwp (ptid)); + if (ix == -1) + return; - for (lp = lwp_list; lp; lpprev = lp, lp = lp->next) - if (ptid_equal (lp->ptid, ptid)) - break; + lp = VEC_index (lwp_info_p, lwp_list_by_lwpid, ix); - if (!lp) - return; + /* Remove from sorted-by-lwpid list. */ + VEC_ordered_remove (lwp_info_p, lwp_list_by_lwpid, ix); - if (lpprev) - lpprev->next = lp->next; - else - lwp_list = lp->next; + /* Remove from sorted-by-creation-order list. */ + lwp_list_remove (lp); + /* Release. */ lwp_free (lp); } @@ -870,18 +962,17 @@ static struct lwp_info * find_lwp_pid (ptid_t ptid) { struct lwp_info *lp; - int lwp; + int lwp, ix; if (ptid_lwp_p (ptid)) lwp = ptid_get_lwp (ptid); else lwp = ptid_get_pid (ptid); - for (lp = lwp_list; lp; lp = lp->next) - if (lwp == ptid_get_lwp (lp->ptid)) - return lp; - - return NULL; + ix = find_lwp_by_lwpid_index (lwp); + if (ix == -1) + return NULL; + return VEC_index (lwp_info_p, lwp_list_by_lwpid, ix); } /* See nat/linux-nat.h. */ diff --git a/gdb/linux-nat.h b/gdb/linux-nat.h index 73888e5..94fc5ed 100644 --- a/gdb/linux-nat.h +++ b/gdb/linux-nat.h @@ -101,7 +101,9 @@ struct lwp_info /* Arch-specific additions. */ struct arch_lwp_info *arch_private; - /* Next LWP in list. */ + /* Previous and next pointers in double-linked list of known LWPs, + sorted by reverse creation order. */ + struct lwp_info *prev; struct lwp_info *next; }; -- 2.5.5