[binutils-gdb] Get pending events in random

[Yao Qi <qiyao at sourceware dot org>]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=89342618773b64db3e67701c0cd9dd89cdbbc18a

commit 89342618773b64db3e67701c0cd9dd89cdbbc18a
Author: Yao Qi <yao.qi@linaro.org>
Date:   Thu Oct 27 16:05:06 2016 +0100

    Get pending events in random
    
    Nowadays, we select events to be reported to GDB in random, however
    that is not enough when many GDBserver internal events (not reported
    to GDB) are generated.
    
    GDBserver pulls all events out of kernel via waitpid, and leave them
    pending.  When goes through threads which have pending events,
    GDBserver uses find_inferior to find the first thread which has
    pending event, and consumes it.  Note that find_inferior always
    iterate threads in a fixed order.  If multiple threads keep hitting
    GDBserver breakpoints, range stepping with single-step breakpoint for
    example, threads in the head of the thread list are more likely to be
    processed and threads in the tail are starved.  This causes some timeout
    fails in gdb.threads/non-stop-fair-events.exp when range stepping is
    enabled on arm-linux.
    
    This patch fixes this issue by randomly selecting pending events.  It
    adds a new function find_inferior_in_random, which iterates threads
    which have pending events randomly.
    
    gdb/gdbserver:
    
    2016-10-27  Yao Qi  <yao.qi@linaro.org>
    
    	* inferiors.c (find_inferior_in_random): New function.
    	* inferiors.h (find_inferior_in_random): Declare.
    	* linux-low.c (linux_wait_for_event_filtered): Call
    	find_inferior_in_random instead of find_inferior.

Diff:
---
 gdb/gdbserver/ChangeLog   |  7 +++++++
 gdb/gdbserver/inferiors.c | 45 +++++++++++++++++++++++++++++++++++++++++++++
 gdb/gdbserver/inferiors.h |  5 +++++
 gdb/gdbserver/linux-low.c |  6 ++++--
 4 files changed, 61 insertions(+), 2 deletions(-)

diff --git a/gdb/gdbserver/ChangeLog b/gdb/gdbserver/ChangeLog
index d43a96a..c6bc016 100644
--- a/gdb/gdbserver/ChangeLog
+++ b/gdb/gdbserver/ChangeLog
@@ -1,5 +1,12 @@
 2016-10-27  Yao Qi  <yao.qi@linaro.org>
 
+	* inferiors.c (find_inferior_in_random): New function.
+	* inferiors.h (find_inferior_in_random): Declare.
+	* linux-low.c (linux_wait_for_event_filtered): Call
+	find_inferior_in_random instead of find_inferior.
+
+2016-10-27  Yao Qi  <yao.qi@linaro.org>
+
 	* linux-low.c (linux_wait_1): If single-step breakpoints are
 	inserted, remove them.
 
diff --git a/gdb/gdbserver/inferiors.c b/gdb/gdbserver/inferiors.c
index 7888f3c..574a7ba 100644
--- a/gdb/gdbserver/inferiors.c
+++ b/gdb/gdbserver/inferiors.c
@@ -248,6 +248,51 @@ find_inferior (struct inferior_list *list,
   return NULL;
 }
 
+/* Find the random inferior_list_entry E in LIST for which FUNC (E, ARG)
+   returns non-zero.  If no entry is found then return NULL.  */
+
+struct inferior_list_entry *
+find_inferior_in_random (struct inferior_list *list,
+			 int (*func) (struct inferior_list_entry *, void *),
+			 void *arg)
+{
+  struct inferior_list_entry *inf = list->head;
+  int count = 0;
+  int random_selector;
+
+  /* First count how many interesting entries we have.  */
+  while (inf != NULL)
+    {
+      struct inferior_list_entry *next;
+
+      next = inf->next;
+      if ((*func) (inf, arg))
+	count++;
+      inf = next;
+    }
+
+  if (count == 0)
+    return NULL;
+
+  /* Now randomly pick an entry out of those.  */
+  random_selector = (int)
+    ((count * (double) rand ()) / (RAND_MAX + 1.0));
+
+  inf = list->head;
+  while (inf != NULL)
+    {
+      struct inferior_list_entry *next;
+
+      next = inf->next;
+      if ((*func) (inf, arg) && (random_selector-- == 0))
+	return inf;
+      inf = next;
+    }
+
+  gdb_assert_not_reached ("failed to find an inferior in random.");
+  return NULL;
+}
+
 struct inferior_list_entry *
 find_inferior_id (struct inferior_list *list, ptid_t id)
 {
diff --git a/gdb/gdbserver/inferiors.h b/gdb/gdbserver/inferiors.h
index 65ab1c6..6ea7a99 100644
--- a/gdb/gdbserver/inferiors.h
+++ b/gdb/gdbserver/inferiors.h
@@ -154,6 +154,11 @@ struct inferior_list_entry *find_inferior
       void *arg);
 struct inferior_list_entry *find_inferior_id (struct inferior_list *list,
 					      ptid_t id);
+struct inferior_list_entry *
+  find_inferior_in_random (struct inferior_list *,
+			   int (*func) (struct inferior_list_entry *,
+					void *),
+			   void *arg);
 
 void *inferior_target_data (struct thread_info *);
 void set_inferior_target_data (struct thread_info *, void *);
diff --git a/gdb/gdbserver/linux-low.c b/gdb/gdbserver/linux-low.c
index a463774..5dcf376 100644
--- a/gdb/gdbserver/linux-low.c
+++ b/gdb/gdbserver/linux-low.c
@@ -2700,7 +2700,8 @@ linux_wait_for_event_filtered (ptid_t wait_ptid, ptid_t filter_ptid,
   if (ptid_equal (filter_ptid, minus_one_ptid) || ptid_is_pid (filter_ptid))
     {
       event_thread = (struct thread_info *)
-	find_inferior (&all_threads, status_pending_p_callback, &filter_ptid);
+	find_inferior_in_random (&all_threads, status_pending_p_callback,
+				 &filter_ptid);
       if (event_thread != NULL)
 	event_child = get_thread_lwp (event_thread);
       if (debug_threads && event_thread)
@@ -2811,7 +2812,8 @@ linux_wait_for_event_filtered (ptid_t wait_ptid, ptid_t filter_ptid,
       /* ... and find an LWP with a status to report to the core, if
 	 any.  */
       event_thread = (struct thread_info *)
-	find_inferior (&all_threads, status_pending_p_callback, &filter_ptid);
+	find_inferior_in_random (&all_threads, status_pending_p_callback,
+				 &filter_ptid);
       if (event_thread != NULL)
 	{
 	  event_child = get_thread_lwp (event_thread);