[PATCH 4/6] [Linux] Optimize PID -> struct lwp_info lookup

Pedro Alves
2016-05-19T14:57:08Z

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 <palves@redhat.com>

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) <prev>: 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;
+}
+
\f

/* 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