This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH 4/6] [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 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;
+}
+
 
 
 /* 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]