From 8b6a69b2f37fd1370aa823320f9dc3fd482e1e78 Mon Sep 17 00:00:00 2001 From: Simon Marchi Date: Tue, 15 Jun 2021 14:49:32 -0400 Subject: gdb: use intrusive list for step-over chain The threads that need a step-over are currently linked using an hand-written intrusive doubly-linked list, so that seems a very good candidate for intrusive_list, convert it. For this, we have a use case of appending a list to another one (in start_step_over). Based on the std::list and Boost APIs, add a splice method. However, only support splicing the other list at the end of the `this` list, since that's all we need. Add explicit default assignment operators to reference_to_pointer_iterator, which are otherwise implicitly deleted. This is needed because to define thread_step_over_list_safe_iterator, we wrap reference_to_pointer_iterator inside a basic_safe_iterator, and basic_safe_iterator needs to be able to copy-assign the wrapped iterator. The move-assignment operator is therefore not needed, only the copy-assignment operator is. But for completeness, add both. Change-Id: I31b2ff67c7b78251314646b31887ef1dfebe510c --- gdb/gdbthread.h | 52 +++++++------- gdb/infrun.c | 39 +++++------ gdb/infrun.h | 4 +- gdb/thread.c | 106 ++++------------------------- gdb/unittests/intrusive_list-selftests.c | 84 +++++++++++++++++++++++ gdbsupport/intrusive_list.h | 27 ++++++++ gdbsupport/reference-to-pointer-iterator.h | 3 + 7 files changed, 177 insertions(+), 138 deletions(-) diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h index 1305b20ca49..35044383069 100644 --- a/gdb/gdbthread.h +++ b/gdb/gdbthread.h @@ -387,11 +387,9 @@ public: expressions. */ std::vector stack_temporaries; - /* Step-over chain. A thread is in the step-over queue if these are - non-NULL. If only a single thread is in the chain, then these - fields point to self. */ - struct thread_info *step_over_prev = NULL; - struct thread_info *step_over_next = NULL; + /* Step-over chain. A thread is in the step-over queue if this node is + linked. */ + intrusive_list_node step_over_list_node; /* Displaced-step state for this thread. */ displaced_step_thread_state displaced_step_state; @@ -742,36 +740,42 @@ extern value *get_last_thread_stack_temporary (struct thread_info *tp); extern bool value_in_thread_stack_temporaries (struct value *, struct thread_info *thr); +/* Thread step-over list type. */ +using thread_step_over_list_node + = intrusive_member_node; +using thread_step_over_list + = intrusive_list; +using thread_step_over_list_iterator + = reference_to_pointer_iterator; +using thread_step_over_list_safe_iterator + = basic_safe_iterator; +using thread_step_over_list_safe_range + = iterator_range; + +static inline thread_step_over_list_safe_range +make_thread_step_over_list_safe_range (thread_step_over_list &list) +{ + return thread_step_over_list_safe_range + (thread_step_over_list_safe_iterator (list.begin (), + list.end ()), + thread_step_over_list_safe_iterator (list.end (), + list.end ())); +} + /* Add TP to the end of the global pending step-over chain. */ extern void global_thread_step_over_chain_enqueue (thread_info *tp); -/* Append the thread step over chain CHAIN_HEAD to the global thread step over +/* Append the thread step over list LIST to the global thread step over chain. */ extern void global_thread_step_over_chain_enqueue_chain - (thread_info *chain_head); - -/* Remove TP from step-over chain LIST_P. */ - -extern void thread_step_over_chain_remove (thread_info **list_p, - thread_info *tp); + (thread_step_over_list &&list); /* Remove TP from the global pending step-over chain. */ extern void global_thread_step_over_chain_remove (thread_info *tp); -/* Return the thread following TP in the step-over chain whose head is - CHAIN_HEAD. Return NULL if TP is the last entry in the chain. */ - -extern thread_info *thread_step_over_chain_next (thread_info *chain_head, - thread_info *tp); - -/* Return the thread following TP in the global step-over chain, or NULL if TP - is the last entry in the chain. */ - -extern thread_info *global_thread_step_over_chain_next (thread_info *tp); - /* Return true if TP is in any step-over chain. */ extern int thread_is_in_step_over_chain (struct thread_info *tp); @@ -782,7 +786,7 @@ extern int thread_is_in_step_over_chain (struct thread_info *tp); TP may be nullptr, in which case it denotes an empty list, so a length of 0. */ -extern int thread_step_over_chain_length (thread_info *tp); +extern int thread_step_over_chain_length (const thread_step_over_list &l); /* Cancel any ongoing execution command. */ diff --git a/gdb/infrun.c b/gdb/infrun.c index 300d6273670..6a478ef0966 100644 --- a/gdb/infrun.c +++ b/gdb/infrun.c @@ -1245,7 +1245,7 @@ follow_exec (ptid_t ptid, const char *exec_file_target) to avoid starvation, otherwise, we could e.g., find ourselves constantly stepping the same couple threads past their breakpoints over and over, if the single-step finish fast enough. */ -struct thread_info *global_thread_step_over_chain_head; +thread_step_over_list global_thread_step_over_list; /* Bit flags indicating what the thread needs to step over. */ @@ -1843,8 +1843,6 @@ start_step_over (void) { INFRUN_SCOPED_DEBUG_ENTER_EXIT; - thread_info *next; - /* Don't start a new step-over if we already have an in-line step-over operation ongoing. */ if (step_over_info_valid_p ()) @@ -1854,8 +1852,8 @@ start_step_over (void) steps, threads will be enqueued in the global chain if no buffers are available. If we iterated on the global chain directly, we might iterate indefinitely. */ - thread_info *threads_to_step = global_thread_step_over_chain_head; - global_thread_step_over_chain_head = NULL; + thread_step_over_list threads_to_step + = std::move (global_thread_step_over_list); infrun_debug_printf ("stealing global queue of threads to step, length = %d", thread_step_over_chain_length (threads_to_step)); @@ -1867,18 +1865,22 @@ start_step_over (void) global list. */ SCOPE_EXIT { - if (threads_to_step == nullptr) + if (threads_to_step.empty ()) infrun_debug_printf ("step-over queue now empty"); else { infrun_debug_printf ("putting back %d threads to step in global queue", thread_step_over_chain_length (threads_to_step)); - global_thread_step_over_chain_enqueue_chain (threads_to_step); + global_thread_step_over_chain_enqueue_chain + (std::move (threads_to_step)); } }; - for (thread_info *tp = threads_to_step; tp != NULL; tp = next) + thread_step_over_list_safe_range range + = make_thread_step_over_list_safe_range (threads_to_step); + + for (thread_info *tp : range) { struct execution_control_state ecss; struct execution_control_state *ecs = &ecss; @@ -1887,8 +1889,6 @@ start_step_over (void) gdb_assert (!tp->stop_requested); - next = thread_step_over_chain_next (threads_to_step, tp); - if (tp->inf->displaced_step_state.unavailable) { /* The arch told us to not even try preparing another displaced step @@ -1903,7 +1903,7 @@ start_step_over (void) step over chain indefinitely if something goes wrong when resuming it If the error is intermittent and it still needs a step over, it will get enqueued again when we try to resume it normally. */ - thread_step_over_chain_remove (&threads_to_step, tp); + threads_to_step.erase (threads_to_step.iterator_to (*tp)); step_what = thread_still_needs_step_over (tp); must_be_in_line = ((step_what & STEP_OVER_WATCHPOINT) @@ -3790,15 +3790,16 @@ prepare_for_detach (void) /* Remove all threads of INF from the global step-over chain. We want to stop any ongoing step-over, not start any new one. */ - thread_info *next; - for (thread_info *tp = global_thread_step_over_chain_head; - tp != nullptr; - tp = next) - { - next = global_thread_step_over_chain_next (tp); - if (tp->inf == inf) + thread_step_over_list_safe_range range + = make_thread_step_over_list_safe_range (global_thread_step_over_list); + + for (thread_info *tp : range) + if (tp->inf == inf) + { + infrun_debug_printf ("removing thread %s from global step over chain", + target_pid_to_str (tp->ptid).c_str ()); global_thread_step_over_chain_remove (tp); - } + } /* If we were already in the middle of an inline step-over, and the thread stepping belongs to the inferior we're detaching, we need diff --git a/gdb/infrun.h b/gdb/infrun.h index 7ebb9fc9f4e..5a577365f94 100644 --- a/gdb/infrun.h +++ b/gdb/infrun.h @@ -18,8 +18,10 @@ #ifndef INFRUN_H #define INFRUN_H 1 +#include "gdbthread.h" #include "symtab.h" #include "gdbsupport/byte-vector.h" +#include "gdbsupport/intrusive_list.h" struct target_waitstatus; struct frame_info; @@ -253,7 +255,7 @@ extern void mark_infrun_async_event_handler (void); /* The global chain of threads that need to do a step-over operation to get past e.g., a breakpoint. */ -extern struct thread_info *global_thread_step_over_chain_head; +extern thread_step_over_list global_thread_step_over_list; /* Remove breakpoints if possible (usually that means, if everything is stopped). On failure, print a message. */ diff --git a/gdb/thread.c b/gdb/thread.c index 506e93cf401..925ed96c3d8 100644 --- a/gdb/thread.c +++ b/gdb/thread.c @@ -183,7 +183,7 @@ void set_thread_exited (thread_info *tp, bool silent) { /* Dead threads don't need to step-over. Remove from chain. */ - if (tp->step_over_next != NULL) + if (thread_is_in_step_over_chain (tp)) global_thread_step_over_chain_remove (tp); if (tp->state != THREAD_EXITED) @@ -293,93 +293,22 @@ thread_info::deletable () const return refcount () == 0 && !is_current_thread (this); } -/* Add TP to the end of the step-over chain LIST_P. */ - -static void -step_over_chain_enqueue (struct thread_info **list_p, struct thread_info *tp) -{ - gdb_assert (tp->step_over_next == NULL); - gdb_assert (tp->step_over_prev == NULL); - - if (*list_p == NULL) - { - *list_p = tp; - tp->step_over_prev = tp->step_over_next = tp; - } - else - { - struct thread_info *head = *list_p; - struct thread_info *tail = head->step_over_prev; - - tp->step_over_prev = tail; - tp->step_over_next = head; - head->step_over_prev = tp; - tail->step_over_next = tp; - } -} - -/* See gdbthread.h. */ - -void -thread_step_over_chain_remove (thread_info **list_p, thread_info *tp) -{ - gdb_assert (tp->step_over_next != NULL); - gdb_assert (tp->step_over_prev != NULL); - - if (*list_p == tp) - { - if (tp == tp->step_over_next) - *list_p = NULL; - else - *list_p = tp->step_over_next; - } - - tp->step_over_prev->step_over_next = tp->step_over_next; - tp->step_over_next->step_over_prev = tp->step_over_prev; - tp->step_over_prev = tp->step_over_next = NULL; -} - -/* See gdbthread.h. */ - -thread_info * -thread_step_over_chain_next (thread_info *chain_head, thread_info *tp) -{ - thread_info *next = tp->step_over_next; - - return next == chain_head ? NULL : next; -} - -/* See gdbthread.h. */ - -struct thread_info * -global_thread_step_over_chain_next (struct thread_info *tp) -{ - return thread_step_over_chain_next (global_thread_step_over_chain_head, tp); -} - /* See gdbthread.h. */ int thread_is_in_step_over_chain (struct thread_info *tp) { - return (tp->step_over_next != NULL); + return tp->step_over_list_node.is_linked (); } /* See gdbthread.h. */ int -thread_step_over_chain_length (thread_info *tp) +thread_step_over_chain_length (const thread_step_over_list &l) { - if (tp == nullptr) - return 0; - - gdb_assert (thread_is_in_step_over_chain (tp)); - int num = 1; - for (thread_info *iter = tp->step_over_next; - iter != tp; - iter = iter->step_over_next) + for (const thread_info &thread ATTRIBUTE_UNUSED : l) ++num; return num; @@ -393,29 +322,16 @@ global_thread_step_over_chain_enqueue (struct thread_info *tp) infrun_debug_printf ("enqueueing thread %s in global step over chain", target_pid_to_str (tp->ptid).c_str ()); - step_over_chain_enqueue (&global_thread_step_over_chain_head, tp); + gdb_assert (!thread_is_in_step_over_chain (tp)); + global_thread_step_over_list.push_back (*tp); } /* See gdbthread.h. */ void -global_thread_step_over_chain_enqueue_chain (thread_info *chain_head) +global_thread_step_over_chain_enqueue_chain (thread_step_over_list &&list) { - gdb_assert (chain_head->step_over_next != nullptr); - gdb_assert (chain_head->step_over_prev != nullptr); - - if (global_thread_step_over_chain_head == nullptr) - global_thread_step_over_chain_head = chain_head; - else - { - thread_info *global_last = global_thread_step_over_chain_head->step_over_prev; - thread_info *chain_last = chain_head->step_over_prev; - - chain_last->step_over_next = global_thread_step_over_chain_head; - global_last->step_over_next = chain_head; - global_thread_step_over_chain_head->step_over_prev = chain_last; - chain_head->step_over_prev = global_last; - } + global_thread_step_over_list.splice (std::move (list)); } /* See gdbthread.h. */ @@ -426,7 +342,9 @@ global_thread_step_over_chain_remove (struct thread_info *tp) infrun_debug_printf ("removing thread %s from global step over chain", target_pid_to_str (tp->ptid).c_str ()); - thread_step_over_chain_remove (&global_thread_step_over_chain_head, tp); + gdb_assert (thread_is_in_step_over_chain (tp)); + auto it = global_thread_step_over_list.iterator_to (*tp); + global_thread_step_over_list.erase (it); } /* Delete the thread referenced by THR. If SILENT, don't notify @@ -810,7 +728,7 @@ set_running_thread (struct thread_info *tp, bool running) /* If the thread is now marked stopped, remove it from the step-over queue, so that we don't try to resume it until the user wants it to. */ - if (tp->step_over_next != NULL) + if (thread_is_in_step_over_chain (tp)) global_thread_step_over_chain_remove (tp); } diff --git a/gdb/unittests/intrusive_list-selftests.c b/gdb/unittests/intrusive_list-selftests.c index 5497a012dd9..8b2b2d1391e 100644 --- a/gdb/unittests/intrusive_list-selftests.c +++ b/gdb/unittests/intrusive_list-selftests.c @@ -503,6 +503,89 @@ struct intrusive_list_test } } + static void + test_splice () + { + { + /* Two non-empty lists. */ + item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e"); + ListType list1; + ListType list2; + std::vector expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + list2.push_back (d); + list2.push_back (e); + + list1.splice (std::move (list2)); + + expected = {&a, &b, &c, &d, &e}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* Receiving list empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector expected; + + list2.push_back (a); + list2.push_back (b); + list2.push_back (c); + + list1.splice (std::move (list2)); + + expected = {&a, &b, &c}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* Giving list empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + list1.splice (std::move (list2)); + + expected = {&a, &b, &c}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* Both lists empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector expected; + + list1.splice (std::move (list2)); + + expected = {}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + } + static void test_pop_front () { @@ -682,6 +765,7 @@ test_intrusive_list () tests.test_push_front (); tests.test_push_back (); tests.test_insert (); + tests.test_splice (); tests.test_pop_front (); tests.test_pop_back (); tests.test_erase (); diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h index 8d49ce45517..58aa68f1ab8 100644 --- a/gdbsupport/intrusive_list.h +++ b/gdbsupport/intrusive_list.h @@ -350,6 +350,33 @@ public: pos_node->prev = &elem; } + /* Move elements from LIST at the end of the current list. */ + void splice (intrusive_list &&other) + { + if (other.empty ()) + return; + + if (this->empty ()) + { + *this = std::move (other); + return; + } + + /* [A ... B] + [C ... D] */ + T *b_elem = m_back; + node_type *b_node = as_node (b_elem); + T *c_elem = other.m_front; + node_type *c_node = as_node (c_elem); + T *d_elem = other.m_back; + + b_node->next = c_elem; + c_node->prev = b_elem; + m_back = d_elem; + + other.m_front = nullptr; + other.m_back = nullptr; + } + void pop_front () { gdb_assert (!this->empty ()); diff --git a/gdbsupport/reference-to-pointer-iterator.h b/gdbsupport/reference-to-pointer-iterator.h index 7303fa4a04a..9210426adcc 100644 --- a/gdbsupport/reference-to-pointer-iterator.h +++ b/gdbsupport/reference-to-pointer-iterator.h @@ -56,6 +56,9 @@ struct reference_to_pointer_iterator reference_to_pointer_iterator (const reference_to_pointer_iterator &) = default; reference_to_pointer_iterator (reference_to_pointer_iterator &&) = default; + reference_to_pointer_iterator &operator= (const reference_to_pointer_iterator &) = default; + reference_to_pointer_iterator &operator= (reference_to_pointer_iterator &&) = default; + value_type operator* () const { return &*m_it; } -- cgit v1.2.1