From 774113b02f41ded4d9ba4d18571ee5024312ad1b Mon Sep 17 00:00:00 2001 From: Pedro Alves Date: Tue, 24 May 2016 14:47:57 +0100 Subject: [Linux] Optimize PID -> struct lwp_info lookup 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 adding a hash table keyed by LWP PID, for fast 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: 2016-05-24 Pedro Alves PR gdb/19828 * linux-nat.c (lwp_lwpid_htab): New htab. (lwp_info_hash, lwp_lwpid_htab_eq, lwp_lwpid_htab_create) (lwp_lwpid_htab_add_lwp): New functions. (lwp_list): Tweak comment. (lwp_list_add, lwp_list_remove, lwp_lwpid_htab_remove_pid): New functions. (purge_lwp_list): Rewrite, using htab_traverse_noresize. (add_initial_lwp): Add lwp to htab too. Use lwp_list_add. (delete_lwp): Use lwp_list_remove. Remove htab too. (find_lwp_pid): Search in htab. (_initialize_linux_nat): Call lwp_lwpid_htab_create. * linux-nat.h (struct lwp_info) : New field. --- gdb/linux-nat.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'gdb/linux-nat.h') diff --git a/gdb/linux-nat.h b/gdb/linux-nat.h index 73888e5..f6102f7 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 doubly-linked list of known LWPs, + sorted by reverse creation order. */ + struct lwp_info *prev; struct lwp_info *next; }; -- cgit v1.1