diff options
| -rw-r--r-- | gdb/Makefile.in | 1 | ||||
| -rw-r--r-- | gdb/gdb-gdb.py.in | 98 | ||||
| -rw-r--r-- | gdb/gdbthread.h | 13 | ||||
| -rw-r--r-- | gdb/inferior.c | 24 | ||||
| -rw-r--r-- | gdb/inferior.h | 14 | ||||
| -rw-r--r-- | gdb/scoped-mock-context.h | 4 | ||||
| -rw-r--r-- | gdb/thread-iter.c | 53 | ||||
| -rw-r--r-- | gdb/thread-iter.h | 5 | ||||
| -rw-r--r-- | gdb/thread.c | 61 | ||||
| -rw-r--r-- | gdb/unittests/intrusive_list-selftests.c | 734 | ||||
| -rw-r--r-- | gdbsupport/intrusive_list.h | 559 | ||||
| -rw-r--r-- | gdbsupport/reference-to-pointer-iterator.h | 79 |
12 files changed, 1561 insertions, 84 deletions
diff --git a/gdb/Makefile.in b/gdb/Makefile.in index 53beb3a..2274b9b 100644 --- a/gdb/Makefile.in +++ b/gdb/Makefile.in @@ -449,6 +449,7 @@ SELFTESTS_SRCS = \ unittests/function-view-selftests.c \ unittests/gdb_tilde_expand-selftests.c \ unittests/gmp-utils-selftests.c \ + unittests/intrusive_list-selftests.c \ unittests/lookup_name_info-selftests.c \ unittests/memory-map-selftests.c \ unittests/memrange-selftests.c \ diff --git a/gdb/gdb-gdb.py.in b/gdb/gdb-gdb.py.in index af9fcfe..15dbf38 100644 --- a/gdb/gdb-gdb.py.in +++ b/gdb/gdb-gdb.py.in @@ -276,16 +276,108 @@ class CoreAddrPrettyPrinter: return hex(int(self._val)) +class IntrusiveListPrinter: + """Print a struct intrusive_list.""" + + def __init__(self, val): + self._val = val + + # Type of linked items. + self._item_type = self._val.type.template_argument(0) + self._node_ptr_type = gdb.lookup_type( + "intrusive_list_node<{}>".format(self._item_type.tag) + ).pointer() + + # Type of value -> node converter. + self._conv_type = self._val.type.template_argument(1) + + if self._uses_member_node(): + # The second template argument of intrusive_member_node is a member + # pointer value. Its value is the offset of the node member in the + # enclosing type. + member_node_ptr = self._conv_type.template_argument(1) + member_node_ptr = member_node_ptr.cast(gdb.lookup_type("int")) + self._member_node_offset = int(member_node_ptr) + + # This is only needed in _as_node_ptr if using a member node. Look it + # up here so we only do it once. + self._char_ptr_type = gdb.lookup_type("char").pointer() + + def display_hint(self): + return "array" + + def _uses_member_node(self): + """Return True if the list items use a node as a member, False if + they use a node as a base class. + """ + + if self._conv_type.name.startswith("intrusive_member_node<"): + return True + elif self._conv_type.name.startswith("intrusive_base_node<"): + return False + else: + raise RuntimeError( + "Unexpected intrusive_list value -> node converter type: {}".format( + self._conv_type.name + ) + ) + + def to_string(self): + s = "intrusive list of {}".format(self._item_type) + + if self._uses_member_node(): + node_member = self._conv_type.template_argument(1) + s += ", linked through {}".format(node_member) + + return s + + def _as_node_ptr(self, elem_ptr): + """Given ELEM_PTR, a pointer to a list element, return a pointer to the + corresponding intrusive_list_node. + """ + + assert elem_ptr.type.code == gdb.TYPE_CODE_PTR + + if self._uses_member_node(): + # Node as a member: add the member node offset from to the element's + # address to get the member node's address. + elem_char_ptr = elem_ptr.cast(self._char_ptr_type) + node_char_ptr = elem_char_ptr + self._member_node_offset + return node_char_ptr.cast(self._node_ptr_type) + else: + # Node as a base: just casting from node pointer to item pointer + # will adjust the pointer value. + return elem_ptr.cast(self._node_ptr_type) + + def _children_generator(self): + """Generator that yields one tuple per list item.""" + + elem_ptr = self._val["m_front"] + idx = 0 + while elem_ptr != 0: + yield (str(idx), elem_ptr.dereference()) + node_ptr = self._as_node_ptr(elem_ptr) + elem_ptr = node_ptr["next"] + idx += 1 + + def children(self): + return self._children_generator() + + def type_lookup_function(val): """A routine that returns the correct pretty printer for VAL if appropriate. Returns None otherwise. """ - if val.type.tag == "type": + tag = val.type.tag + name = val.type.name + if tag == "type": return StructTypePrettyPrinter(val) - elif val.type.tag == "main_type": + elif tag == "main_type": return StructMainTypePrettyPrinter(val) - elif val.type.name == "CORE_ADDR": + elif name == "CORE_ADDR": return CoreAddrPrettyPrinter(val) + elif tag is not None and tag.startswith("intrusive_list<"): + return IntrusiveListPrinter(val) return None diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h index cb3dcc3..1305b20 100644 --- a/gdb/gdbthread.h +++ b/gdb/gdbthread.h @@ -33,6 +33,7 @@ struct symtab; #include "gdbsupport/common-gdbthread.h" #include "gdbsupport/forward-scope-exit.h" #include "displaced-stepping.h" +#include "gdbsupport/intrusive_list.h" struct inferior; struct process_stratum_target; @@ -222,9 +223,12 @@ struct private_thread_info delete_thread). All other thread references are considered weak references. Placing a thread in the thread list is an implicit strong reference, and is thus not accounted for in the thread's - refcount. */ + refcount. -class thread_info : public refcounted_object + The intrusive_list_node base links threads in a per-inferior list. */ + +class thread_info : public refcounted_object, + public intrusive_list_node<thread_info> { public: explicit thread_info (inferior *inf, ptid_t ptid); @@ -235,7 +239,6 @@ public: /* Mark this thread as running and notify observers. */ void set_running (bool running); - struct thread_info *next = NULL; ptid_t ptid; /* "Actual process id"; In fact, this may be overloaded with kernel thread id, etc. */ @@ -435,6 +438,10 @@ extern void delete_thread (struct thread_info *thread); this thread belonged to has already exited, for example. */ extern void delete_thread_silent (struct thread_info *thread); +/* Mark the thread exited, but don't delete it or remove it from the + inferior thread list. */ +extern void set_thread_exited (thread_info *tp, bool silent); + /* Delete a step_resume_breakpoint from the thread database. */ extern void delete_step_resume_breakpoint (struct thread_info *); diff --git a/gdb/inferior.c b/gdb/inferior.c index e1c70d5..3accf97 100644 --- a/gdb/inferior.c +++ b/gdb/inferior.c @@ -163,6 +163,19 @@ add_inferior (int pid) return inf; } +/* See inferior.h. */ + +void +inferior::clear_thread_list (bool silent) +{ + thread_list.clear_and_dispose ([=] (thread_info *thr) + { + set_thread_exited (thr, silent); + if (thr->deletable ()) + delete thr; + }); +} + void delete_inferior (struct inferior *todel) { @@ -177,8 +190,7 @@ delete_inferior (struct inferior *todel) if (!inf) return; - for (thread_info *tp : inf->threads_safe ()) - delete_thread_silent (tp); + inf->clear_thread_list (true); if (infprev) infprev->next = inf->next; @@ -209,13 +221,7 @@ exit_inferior_1 (struct inferior *inftoex, int silent) if (!inf) return; - for (thread_info *tp : inf->threads_safe ()) - { - if (silent) - delete_thread_silent (tp); - else - delete_thread (tp); - } + inf->clear_thread_list (silent); gdb::observers::inferior_exit.notify (inf); diff --git a/gdb/inferior.h b/gdb/inferior.h index c63990a..2ae9f9a 100644 --- a/gdb/inferior.h +++ b/gdb/inferior.h @@ -390,8 +390,8 @@ public: /* Pointer to next inferior in singly-linked list of inferiors. */ struct inferior *next = NULL; - /* This inferior's thread list. */ - thread_info *thread_list = nullptr; + /* This inferior's thread list, sorted by creation order. */ + intrusive_list<thread_info> thread_list; /* Returns a range adapter covering the inferior's threads, including exited threads. Used like this: @@ -400,7 +400,7 @@ public: { .... } */ inf_threads_range threads () - { return inf_threads_range (this->thread_list); } + { return inf_threads_range (this->thread_list.begin ()); } /* Returns a range adapter covering the inferior's non-exited threads. Used like this: @@ -409,7 +409,7 @@ public: { .... } */ inf_non_exited_threads_range non_exited_threads () - { return inf_non_exited_threads_range (this->thread_list); } + { return inf_non_exited_threads_range (this->thread_list.begin ()); } /* Like inferior::threads(), but returns a range adapter that can be used with range-for, safely. I.e., it is safe to delete the @@ -420,7 +420,11 @@ public: delete f; */ inline safe_inf_threads_range threads_safe () - { return safe_inf_threads_range (this->thread_list); } + { return safe_inf_threads_range (this->thread_list.begin ()); } + + /* Delete all threads in the thread list. If SILENT, exit threads + silently. */ + void clear_thread_list (bool silent); /* Continuations-related methods. A continuation is an std::function to be called to finish the execution of a command when running diff --git a/gdb/scoped-mock-context.h b/gdb/scoped-mock-context.h index 8d295ba..37ffe51 100644 --- a/gdb/scoped-mock-context.h +++ b/gdb/scoped-mock-context.h @@ -44,9 +44,6 @@ struct scoped_mock_context scoped_restore_current_pspace_and_thread restore_pspace_thread; - scoped_restore_tmpl<thread_info *> restore_thread_list - {&mock_inferior.thread_list, &mock_thread}; - /* Add the mock inferior to the inferior list so that look ups by target+ptid can find it. */ scoped_restore_tmpl<inferior *> restore_inferior_list @@ -54,6 +51,7 @@ struct scoped_mock_context explicit scoped_mock_context (gdbarch *gdbarch) { + mock_inferior.thread_list.push_back (mock_thread); mock_inferior.gdbarch = gdbarch; mock_inferior.aspace = mock_pspace.aspace; mock_inferior.pspace = &mock_pspace; diff --git a/gdb/thread-iter.c b/gdb/thread-iter.c index 012ca5f..a1cdd02 100644 --- a/gdb/thread-iter.c +++ b/gdb/thread-iter.c @@ -27,8 +27,15 @@ all_threads_iterator::all_threads_iterator (begin_t) { /* Advance M_INF/M_THR to the first thread's position. */ for (m_inf = inferior_list; m_inf != NULL; m_inf = m_inf->next) - if ((m_thr = m_inf->thread_list) != NULL) - return; + { + auto thr_iter = m_inf->thread_list.begin (); + if (thr_iter != m_inf->thread_list.end ()) + { + m_thr = &*thr_iter; + return; + } + } + m_thr = nullptr; } /* See thread-iter.h. */ @@ -36,6 +43,8 @@ all_threads_iterator::all_threads_iterator (begin_t) void all_threads_iterator::advance () { + intrusive_list<thread_info>::iterator thr_iter (m_thr); + /* The loop below is written in the natural way as-if we'd always start at the beginning of the inferior list. This fast forwards the algorithm to the actual current position. */ @@ -43,14 +52,17 @@ all_threads_iterator::advance () for (; m_inf != NULL; m_inf = m_inf->next) { - m_thr = m_inf->thread_list; - while (m_thr != NULL) + thr_iter = m_inf->thread_list.begin (); + while (thr_iter != m_inf->thread_list.end ()) { + m_thr = &*thr_iter; return; start: - m_thr = m_thr->next; + ++thr_iter; } } + + m_thr = nullptr; } /* See thread-iter.h. */ @@ -74,12 +86,18 @@ all_matching_threads_iterator::all_matching_threads_iterator gdb_assert ((filter_target == nullptr && filter_ptid == minus_one_ptid) || filter_target->stratum () == process_stratum); - m_thr = nullptr; for (m_inf = inferior_list; m_inf != NULL; m_inf = m_inf->next) if (m_inf_matches ()) - for (m_thr = m_inf->thread_list; m_thr != NULL; m_thr = m_thr->next) - if (m_thr->ptid.matches (m_filter_ptid)) - return; + for (auto thr_iter = m_inf->thread_list.begin (); + thr_iter != m_inf->thread_list.end (); + ++thr_iter) + if (thr_iter->ptid.matches (m_filter_ptid)) + { + m_thr = &*thr_iter; + return; + } + + m_thr = nullptr; } /* See thread-iter.h. */ @@ -87,6 +105,8 @@ all_matching_threads_iterator::all_matching_threads_iterator void all_matching_threads_iterator::advance () { + intrusive_list<thread_info>::iterator thr_iter (m_thr); + /* The loop below is written in the natural way as-if we'd always start at the beginning of the inferior list. This fast forwards the algorithm to the actual current position. */ @@ -95,13 +115,18 @@ all_matching_threads_iterator::advance () for (; m_inf != NULL; m_inf = m_inf->next) if (m_inf_matches ()) { - m_thr = m_inf->thread_list; - while (m_thr != NULL) + thr_iter = m_inf->thread_list.begin (); + while (thr_iter != m_inf->thread_list.end ()) { - if (m_thr->ptid.matches (m_filter_ptid)) - return; + if (thr_iter->ptid.matches (m_filter_ptid)) + { + m_thr = &*thr_iter; + return; + } start: - m_thr = m_thr->next; + ++thr_iter; } } + + m_thr = nullptr; } diff --git a/gdb/thread-iter.h b/gdb/thread-iter.h index 098af0f..2e43034 100644 --- a/gdb/thread-iter.h +++ b/gdb/thread-iter.h @@ -20,13 +20,16 @@ #define THREAD_ITER_H #include "gdbsupport/filtered-iterator.h" +#include "gdbsupport/iterator-range.h" #include "gdbsupport/next-iterator.h" +#include "gdbsupport/reference-to-pointer-iterator.h" #include "gdbsupport/safe-iterator.h" /* A forward iterator that iterates over a given inferior's threads. */ -using inf_threads_iterator = next_iterator<thread_info>; +using inf_threads_iterator + = reference_to_pointer_iterator<intrusive_list<thread_info>::iterator>; /* A forward iterator that iterates over all threads of all inferiors. */ diff --git a/gdb/thread.c b/gdb/thread.c index f850f05..89f51c0 100644 --- a/gdb/thread.c +++ b/gdb/thread.c @@ -177,9 +177,9 @@ clear_thread_inferior_resources (struct thread_info *tp) clear_inline_frame_state (tp); } -/* Set the TP's state as exited. */ +/* See gdbthread.h. */ -static void +void set_thread_exited (thread_info *tp, bool silent) { /* Dead threads don't need to step-over. Remove from chain. */ @@ -203,17 +203,8 @@ init_thread_list (void) { highest_thread_num = 0; - for (thread_info *tp : all_threads_safe ()) - { - inferior *inf = tp->inf; - - if (tp->deletable ()) - delete tp; - else - set_thread_exited (tp, 1); - - inf->thread_list = NULL; - } + for (inferior *inf : all_inferiors ()) + inf->clear_thread_list (true); } /* Allocate a new thread of inferior INF with target id PTID and add @@ -224,21 +215,7 @@ new_thread (struct inferior *inf, ptid_t ptid) { thread_info *tp = new thread_info (inf, ptid); - if (inf->thread_list == NULL) - inf->thread_list = tp; - else - { - struct thread_info *last; - - for (last = inf->thread_list; last->next != NULL; last = last->next) - gdb_assert (ptid != last->ptid - || last->state == THREAD_EXITED); - - gdb_assert (ptid != last->ptid - || last->state == THREAD_EXITED); - - last->next = tp; - } + inf->thread_list.push_back (*tp); return tp; } @@ -462,29 +439,18 @@ delete_thread_1 (thread_info *thr, bool silent) { gdb_assert (thr != nullptr); - struct thread_info *tp, *tpprev = NULL; - - for (tp = thr->inf->thread_list; tp; tpprev = tp, tp = tp->next) - if (tp == thr) - break; + set_thread_exited (thr, silent); - if (!tp) - return; - - set_thread_exited (tp, silent); - - if (!tp->deletable ()) + if (!thr->deletable ()) { /* Will be really deleted some other time. */ return; } - if (tpprev) - tpprev->next = tp->next; - else - tp->inf->thread_list = tp->next; + auto it = thr->inf->thread_list.iterator_to (*thr); + thr->inf->thread_list.erase (it); - delete tp; + delete thr; } /* See gdbthread.h. */ @@ -629,7 +595,10 @@ in_thread_list (process_stratum_target *targ, ptid_t ptid) thread_info * first_thread_of_inferior (inferior *inf) { - return inf->thread_list; + if (inf->thread_list.empty ()) + return nullptr; + + return &inf->thread_list.front (); } thread_info * @@ -2018,7 +1987,7 @@ update_threads_executing (void) /* If the process has no threads, then it must be we have a process-exit event pending. */ - if (inf->thread_list == NULL) + if (inf->thread_list.empty ()) { targ->threads_executing = true; return; diff --git a/gdb/unittests/intrusive_list-selftests.c b/gdb/unittests/intrusive_list-selftests.c new file mode 100644 index 0000000..5497a01 --- /dev/null +++ b/gdb/unittests/intrusive_list-selftests.c @@ -0,0 +1,734 @@ +/* Tests fpr intrusive double linked list for GDB, the GNU debugger. + Copyright (C) 2021 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include "defs.h" + +#include "gdbsupport/intrusive_list.h" +#include "gdbsupport/selftest.h" +#include <unordered_set> + +/* An item type using intrusive_list_node by inheriting from it and its + corresponding list type. Put another base before intrusive_list_node + so that a pointer to the node != a pointer to the item. */ + +struct other_base +{ + int n = 1; +}; + +struct item_with_base : public other_base, + public intrusive_list_node<item_with_base> +{ + explicit item_with_base (const char *name) + : name (name) + {} + + const char *const name; +}; + +using item_with_base_list = intrusive_list<item_with_base>; + +/* An item type using intrusive_list_node as a field and its corresponding + list type. Put the other field before the node, so that a pointer to the + node != a pointer to the item. */ + +struct item_with_member +{ + explicit item_with_member (const char *name) + : name (name) + {} + + const char *const name; + intrusive_list_node<item_with_member> node; +}; + +using item_with_member_node + = intrusive_member_node<item_with_member, &item_with_member::node>; +using item_with_member_list + = intrusive_list<item_with_member, item_with_member_node>; + +/* To run all tests using both the base and member methods, all tests are + declared in this templated class, which is instantiated once for each + list type. */ + +template <typename ListType> +struct intrusive_list_test +{ + using item_type = typename ListType::value_type; + + /* Verify that LIST contains exactly the items in EXPECTED. + + Traverse the list forward and backwards to exercise all links. */ + + static void + verify_items (const ListType &list, + gdb::array_view<const typename ListType::value_type *> expected) + { + int i = 0; + + for (typename ListType::iterator it = list.begin (); + it != list.end (); + ++it) + { + const item_type &item = *it; + + gdb_assert (i < expected.size ()); + gdb_assert (&item == expected[i]); + + ++i; + } + + gdb_assert (i == expected.size ()); + + for (typename ListType::reverse_iterator it = list.rbegin (); + it != list.rend (); + ++it) + { + const item_type &item = *it; + + --i; + + gdb_assert (i >= 0); + gdb_assert (&item == expected[i]); + } + + gdb_assert (i == 0); + } + + static void + test_move_constructor () + { + { + /* Other list is not empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + std::vector<const item_type *> expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + ListType list2 (std::move (list1)); + + expected = {}; + verify_items (list1, expected); + + expected = {&a, &b, &c}; + verify_items (list2, expected); + } + + { + /* Other list contains 1 element. */ + item_type a ("a"); + ListType list1; + std::vector<const item_type *> expected; + + list1.push_back (a); + + ListType list2 (std::move (list1)); + + expected = {}; + verify_items (list1, expected); + + expected = {&a}; + verify_items (list2, expected); + } + + { + /* Other list is empty. */ + ListType list1; + std::vector<const item_type *> expected; + + ListType list2 (std::move (list1)); + + expected = {}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + } + + static void + test_move_assignment () + { + { + /* Both lists are not empty. */ + item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + list2.push_back (d); + list2.push_back (e); + + list2 = std::move (list1); + + expected = {}; + verify_items (list1, expected); + + expected = {&a, &b, &c}; + verify_items (list2, expected); + } + + { + /* rhs list is empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list2.push_back (a); + list2.push_back (b); + list2.push_back (c); + + list2 = std::move (list1); + + expected = {}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* lhs list is empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + list2 = std::move (list1); + + expected = {}; + verify_items (list1, expected); + + expected = {&a, &b, &c}; + verify_items (list2, expected); + } + + { + /* Both lists contain 1 item. */ + item_type a ("a"), b ("b"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + list2.push_back (b); + + list2 = std::move (list1); + + expected = {}; + verify_items (list1, expected); + + expected = {&a}; + verify_items (list2, expected); + } + + { + /* Both lists are empty. */ + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list2 = std::move (list1); + + expected = {}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + } + + static void + test_swap () + { + { + /* Two non-empty lists. */ + item_type a ("a"), b ("b"), c ("c"), d ("d"), e ("e"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + list2.push_back (d); + list2.push_back (e); + + std::swap (list1, list2); + + expected = {&d, &e}; + verify_items (list1, expected); + + expected = {&a, &b, &c}; + verify_items (list2, expected); + } + + { + /* Other is empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + list1.push_back (b); + list1.push_back (c); + + std::swap (list1, list2); + + expected = {}; + verify_items (list1, expected); + + expected = {&a, &b, &c}; + verify_items (list2, expected); + } + + { + /* *this is empty. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list2.push_back (a); + list2.push_back (b); + list2.push_back (c); + + std::swap (list1, list2); + + expected = {&a, &b, &c}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* Both lists empty. */ + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + std::swap (list1, list2); + + expected = {}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + + { + /* Swap one element twice. */ + item_type a ("a"); + ListType list1; + ListType list2; + std::vector<const item_type *> expected; + + list1.push_back (a); + + std::swap (list1, list2); + + expected = {}; + verify_items (list1, expected); + + expected = {&a}; + verify_items (list2, expected); + + std::swap (list1, list2); + + expected = {&a}; + verify_items (list1, expected); + + expected = {}; + verify_items (list2, expected); + } + } + + static void + test_front_back () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + const ListType &clist = list; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + gdb_assert (&list.front () == &a); + gdb_assert (&clist.front () == &a); + gdb_assert (&list.back () == &c); + gdb_assert (&clist.back () == &c); + } + + static void + test_push_front () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + expected = {}; + verify_items (list, expected); + + list.push_front (a); + expected = {&a}; + verify_items (list, expected); + + list.push_front (b); + expected = {&b, &a}; + verify_items (list, expected); + + list.push_front (c); + expected = {&c, &b, &a}; + verify_items (list, expected); + } + + static void + test_push_back () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + expected = {}; + verify_items (list, expected); + + list.push_back (a); + expected = {&a}; + verify_items (list, expected); + + list.push_back (b); + expected = {&a, &b}; + verify_items (list, expected); + + list.push_back (c); + expected = {&a, &b, &c}; + verify_items (list, expected); + } + + static void + test_insert () + { + std::vector<const item_type *> expected; + + { + /* Insert at beginning. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list; + + + list.insert (list.begin (), a); + expected = {&a}; + verify_items (list, expected); + + list.insert (list.begin (), b); + expected = {&b, &a}; + verify_items (list, expected); + + list.insert (list.begin (), c); + expected = {&c, &b, &a}; + verify_items (list, expected); + } + + { + /* Insert at end. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list; + + + list.insert (list.end (), a); + expected = {&a}; + verify_items (list, expected); + + list.insert (list.end (), b); + expected = {&a, &b}; + verify_items (list, expected); + + list.insert (list.end (), c); + expected = {&a, &b, &c}; + verify_items (list, expected); + } + + { + /* Insert in the middle. */ + item_type a ("a"), b ("b"), c ("c"); + ListType list; + + list.push_back (a); + list.push_back (b); + + list.insert (list.iterator_to (b), c); + expected = {&a, &c, &b}; + verify_items (list, expected); + } + + { + /* Insert in empty list. */ + item_type a ("a"); + ListType list; + + list.insert (list.end (), a); + expected = {&a}; + verify_items (list, expected); + } + } + + static void + test_pop_front () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + list.pop_front (); + expected = {&b, &c}; + verify_items (list, expected); + + list.pop_front (); + expected = {&c}; + verify_items (list, expected); + + list.pop_front (); + expected = {}; + verify_items (list, expected); + } + + static void + test_pop_back () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + list.pop_back(); + expected = {&a, &b}; + verify_items (list, expected); + + list.pop_back (); + expected = {&a}; + verify_items (list, expected); + + list.pop_back (); + expected = {}; + verify_items (list, expected); + } + + static void + test_erase () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + list.erase (list.iterator_to (b)); + expected = {&a, &c}; + verify_items (list, expected); + + list.erase (list.iterator_to (c)); + expected = {&a}; + verify_items (list, expected); + + list.erase (list.iterator_to (a)); + expected = {}; + verify_items (list, expected); + } + + static void + test_clear () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + list.clear (); + expected = {}; + verify_items (list, expected); + + /* Verify idempotency. */ + list.clear (); + expected = {}; + verify_items (list, expected); + } + + static void + test_clear_and_dispose () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + std::vector<const item_type *> expected; + std::unordered_set<const item_type *> disposer_seen; + int disposer_calls = 0; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + auto disposer = [&] (const item_type *item) + { + disposer_seen.insert (item); + disposer_calls++; + }; + list.clear_and_dispose (disposer); + + expected = {}; + verify_items (list, expected); + gdb_assert (disposer_calls == 3); + gdb_assert (disposer_seen.find (&a) != disposer_seen.end ()); + gdb_assert (disposer_seen.find (&b) != disposer_seen.end ()); + gdb_assert (disposer_seen.find (&c) != disposer_seen.end ()); + + /* Verify idempotency. */ + list.clear_and_dispose (disposer); + gdb_assert (disposer_calls == 3); + } + + static void + test_empty () + { + item_type a ("a"); + ListType list; + + gdb_assert (list.empty ()); + list.push_back (a); + gdb_assert (!list.empty ()); + list.erase (list.iterator_to (a)); + gdb_assert (list.empty ()); + } + + static void + test_begin_end () + { + item_type a ("a"), b ("b"), c ("c"); + ListType list; + const ListType &clist = list; + + list.push_back (a); + list.push_back (b); + list.push_back (c); + + gdb_assert (&*list.begin () == &a); + gdb_assert (&*list.cbegin () == &a); + gdb_assert (&*clist.begin () == &a); + gdb_assert (&*list.rbegin () == &c); + gdb_assert (&*list.crbegin () == &c); + gdb_assert (&*clist.rbegin () == &c); + + /* At least check that they compile. */ + list.end (); + list.cend (); + clist.end (); + list.rend (); + list.crend (); + clist.end (); + } +}; + +template <typename ListType> +static void +test_intrusive_list () +{ + intrusive_list_test<ListType> tests; + + tests.test_move_constructor (); + tests.test_move_assignment (); + tests.test_swap (); + tests.test_front_back (); + tests.test_push_front (); + tests.test_push_back (); + tests.test_insert (); + tests.test_pop_front (); + tests.test_pop_back (); + tests.test_erase (); + tests.test_clear (); + tests.test_clear_and_dispose (); + tests.test_empty (); + tests.test_begin_end (); +} + +static void +test_node_is_linked () +{ + { + item_with_base a ("a"); + item_with_base_list list; + + gdb_assert (!a.is_linked ()); + list.push_back (a); + gdb_assert (a.is_linked ()); + list.pop_back (); + gdb_assert (!a.is_linked ()); + } + + { + item_with_member a ("a"); + item_with_member_list list; + + gdb_assert (!a.node.is_linked ()); + list.push_back (a); + gdb_assert (a.node.is_linked ()); + list.pop_back (); + gdb_assert (!a.node.is_linked ()); + } +} + +static void +test_intrusive_list () +{ + test_intrusive_list<item_with_base_list> (); + test_intrusive_list<item_with_member_list> (); + test_node_is_linked (); +} + +void _initialize_intrusive_list_selftests (); +void +_initialize_intrusive_list_selftests () +{ + selftests::register_test + ("intrusive_list", test_intrusive_list); +} diff --git a/gdbsupport/intrusive_list.h b/gdbsupport/intrusive_list.h new file mode 100644 index 0000000..8d49ce4 --- /dev/null +++ b/gdbsupport/intrusive_list.h @@ -0,0 +1,559 @@ +/* Intrusive double linked list for GDB, the GNU debugger. + Copyright (C) 2021 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef GDBSUPPORT_INTRUSIVE_LIST_H +#define GDBSUPPORT_INTRUSIVE_LIST_H + +#define INTRUSIVE_LIST_UNLINKED_VALUE ((T *) -1) + +/* A list node. The elements put in an intrusive_list either inherit + from this, or have a field of this type. */ +template<typename T> +struct intrusive_list_node +{ + bool is_linked () const + { + return next != INTRUSIVE_LIST_UNLINKED_VALUE; + } + + T *next = INTRUSIVE_LIST_UNLINKED_VALUE; + T *prev = INTRUSIVE_LIST_UNLINKED_VALUE; +}; + +/* Follows a couple types used by intrusive_list as template parameter to find + the intrusive_list_node for a given element. One for lists where the + elements inherit intrusive_list_node, and another for elements that keep the + node as member field. */ + +/* For element types that inherit from intrusive_list_node. */ + +template<typename T> +struct intrusive_base_node +{ + static intrusive_list_node<T> *as_node (T *elem) + { return elem; } +}; + +/* For element types that keep the node as member field. */ + +template<typename T, intrusive_list_node<T> T::*MemberNode> +struct intrusive_member_node +{ + static intrusive_list_node<T> *as_node (T *elem) + { return &(elem->*MemberNode); } +}; + +/* Common code for forward and reverse iterators. */ + +template<typename T, typename AsNode, typename SelfType> +struct intrusive_list_base_iterator +{ + using self_type = SelfType; + using iterator_category = std::bidirectional_iterator_tag; + using value_type = T; + using pointer = T *; + using const_pointer = const T *; + using reference = T &; + using const_reference = const T &; + using difference_type = ptrdiff_t; + using size_type = size_t; + using node_type = intrusive_list_node<T>; + + /* Create an iterator pointing to ELEM. */ + explicit intrusive_list_base_iterator (T *elem) + : m_elem (elem) + {} + + /* Create a past-the-end iterator. */ + intrusive_list_base_iterator () + : m_elem (nullptr) + {} + + reference operator* () const + { return *m_elem; } + + pointer operator-> () const + { return m_elem; } + + bool operator== (const self_type &other) const + { return m_elem == other.m_elem; } + + bool operator!= (const self_type &other) const + { return m_elem != other.m_elem; } + +protected: + static node_type *as_node (T *elem) + { return AsNode::as_node (elem); } + + /* A past-end-the iterator points to the list's head. */ + pointer m_elem; +}; + +/* Forward iterator for an intrusive_list. */ + +template<typename T, typename AsNode = intrusive_base_node<T>> +struct intrusive_list_iterator + : public intrusive_list_base_iterator + <T, AsNode, intrusive_list_iterator<T, AsNode>> +{ + using base = intrusive_list_base_iterator + <T, AsNode, intrusive_list_iterator<T, AsNode>>; + using self_type = typename base::self_type; + using node_type = typename base::node_type; + + /* Inherit constructor and M_NODE visibility from base. */ + using base::base; + using base::m_elem; + + self_type &operator++ () + { + node_type *node = this->as_node (m_elem); + m_elem = node->next; + return *this; + } + + self_type operator++ (int) + { + self_type temp = *this; + node_type *node = this->as_node (m_elem); + m_elem = node->next; + return temp; + } + + self_type &operator-- () + { + node_type *node = this->as_node (m_elem); + m_elem = node->prev; + return *this; + } + + self_type operator-- (int) + { + self_type temp = *this; + node_type *node = this->as_node (m_elem); + m_elem = node->prev; + return temp; + } +}; + +/* Reverse iterator for an intrusive_list. */ + +template<typename T, typename AsNode = intrusive_base_node<T>> +struct intrusive_list_reverse_iterator + : public intrusive_list_base_iterator + <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>> +{ + using base = intrusive_list_base_iterator + <T, AsNode, intrusive_list_reverse_iterator<T, AsNode>>; + using self_type = typename base::self_type; + + /* Inherit constructor and M_NODE visibility from base. */ + using base::base; + using base::m_elem; + using node_type = typename base::node_type; + + self_type &operator++ () + { + node_type *node = this->as_node (m_elem); + m_elem = node->prev; + return *this; + } + + self_type operator++ (int) + { + self_type temp = *this; + node_type *node = this->as_node (m_elem); + m_elem = node->prev; + return temp; + } + + self_type &operator-- () + { + node_type *node = this->as_node (m_elem); + m_elem = node->next; + return *this; + } + + self_type operator-- (int) + { + self_type temp = *this; + node_type *node = this->as_node (m_elem); + m_elem = node->next; + return temp; + } +}; + +/* An intrusive double-linked list. + + T is the type of the elements to link. The type T must either: + + - inherit from intrusive_list_node<T> + - have an intrusive_list_node<T> member + + AsNode is a type with an as_node static method used to get a node from an + element. If elements inherit from intrusive_list_node<T>, use the default + intrusive_base_node<T>. If elements have an intrusive_list_node<T> member, + use: + + intrusive_member_node<T, &T::member> + + where `member` is the name of the member. */ + +template <typename T, typename AsNode = intrusive_base_node<T>> +class intrusive_list +{ +public: + using value_type = T; + using pointer = T *; + using const_pointer = const T *; + using reference = T &; + using const_reference = const T &; + using difference_type = ptrdiff_t; + using size_type = size_t; + using iterator = intrusive_list_iterator<T, AsNode>; + using reverse_iterator = intrusive_list_reverse_iterator<T, AsNode>; + using const_iterator = const intrusive_list_iterator<T, AsNode>; + using const_reverse_iterator + = const intrusive_list_reverse_iterator<T, AsNode>; + using node_type = intrusive_list_node<T>; + + intrusive_list () = default; + + ~intrusive_list () + { + clear (); + } + + intrusive_list (intrusive_list &&other) + : m_front (other.m_front), + m_back (other.m_back) + { + other.m_front = nullptr; + other.m_back = nullptr; + } + + intrusive_list &operator= (intrusive_list &&other) + { + m_front = other.m_front; + m_back = other.m_back; + other.m_front = nullptr; + other.m_back = nullptr; + + return *this; + } + + void swap (intrusive_list &other) + { + std::swap (m_front, other.m_front); + std::swap (m_back, other.m_back); + } + + iterator iterator_to (reference value) + { + return iterator (&value); + } + + const_iterator iterator_to (const_reference value) + { + return const_iterator (&value); + } + + reference front () + { + gdb_assert (!this->empty ()); + return *m_front; + } + + const_reference front () const + { + gdb_assert (!this->empty ()); + return *m_front; + } + + reference back () + { + gdb_assert (!this->empty ()); + return *m_back; + } + + const_reference back () const + { + gdb_assert (!this->empty ()); + return *m_back; + } + + void push_front (reference elem) + { + intrusive_list_node<T> *elem_node = as_node (&elem); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + if (this->empty ()) + this->push_empty (elem); + else + this->push_front_non_empty (elem); + } + + void push_back (reference elem) + { + intrusive_list_node<T> *elem_node = as_node (&elem); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + if (this->empty ()) + this->push_empty (elem); + else + this->push_back_non_empty (elem); + } + + /* Inserts ELEM before POS. */ + void insert (const_iterator pos, reference elem) + { + if (this->empty ()) + return this->push_empty (elem); + + if (pos == this->begin ()) + return this->push_front_non_empty (elem); + + if (pos == this->end ()) + return this->push_back_non_empty (elem); + + intrusive_list_node<T> *elem_node = as_node (&elem); + T *pos_elem = &*pos; + intrusive_list_node<T> *pos_node = as_node (pos_elem); + T *prev_elem = pos_node->prev; + intrusive_list_node<T> *prev_node = as_node (prev_elem); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + elem_node->prev = prev_elem; + prev_node->next = &elem; + elem_node->next = pos_elem; + pos_node->prev = &elem; + } + + void pop_front () + { + gdb_assert (!this->empty ()); + erase_element (*m_front); + } + + void pop_back () + { + gdb_assert (!this->empty ()); + erase_element (*m_back); + } + +private: + /* Push ELEM in the list, knowing the list is empty. */ + void push_empty (T &elem) + { + gdb_assert (this->empty ()); + + intrusive_list_node<T> *elem_node = as_node (&elem); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + m_front = &elem; + m_back = &elem; + elem_node->prev = nullptr; + elem_node->next = nullptr; + } + + /* Push ELEM at the front of the list, knowing the list is not empty. */ + void push_front_non_empty (T &elem) + { + gdb_assert (!this->empty ()); + + intrusive_list_node<T> *elem_node = as_node (&elem); + intrusive_list_node<T> *front_node = as_node (m_front); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + elem_node->next = m_front; + front_node->prev = &elem; + elem_node->prev = nullptr; + m_front = &elem; + } + + /* Push ELEM at the back of the list, knowing the list is not empty. */ + void push_back_non_empty (T &elem) + { + gdb_assert (!this->empty ()); + + intrusive_list_node<T> *elem_node = as_node (&elem); + intrusive_list_node<T> *back_node = as_node (m_back); + + gdb_assert (elem_node->next == INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->prev == INTRUSIVE_LIST_UNLINKED_VALUE); + + elem_node->prev = m_back; + back_node->next = &elem; + elem_node->next = nullptr; + m_back = &elem; + } + + void erase_element (T &elem) + { + intrusive_list_node<T> *elem_node = as_node (&elem); + + gdb_assert (elem_node->prev != INTRUSIVE_LIST_UNLINKED_VALUE); + gdb_assert (elem_node->next != INTRUSIVE_LIST_UNLINKED_VALUE); + + if (m_front == &elem) + { + gdb_assert (elem_node->prev == nullptr); + m_front = elem_node->next; + } + else + { + gdb_assert (elem_node->prev != nullptr); + intrusive_list_node<T> *prev_node = as_node (elem_node->prev); + prev_node->next = elem_node->next; + } + + if (m_back == &elem) + { + gdb_assert (elem_node->next == nullptr); + m_back = elem_node->prev; + } + else + { + gdb_assert (elem_node->next != nullptr); + intrusive_list_node<T> *next_node = as_node (elem_node->next); + next_node->prev = elem_node->prev; + } + + elem_node->next = INTRUSIVE_LIST_UNLINKED_VALUE; + elem_node->prev = INTRUSIVE_LIST_UNLINKED_VALUE; + } + +public: + /* Remove the element pointed by I from the list. The element + pointed by I is not destroyed. */ + iterator erase (const_iterator i) + { + iterator ret = i; + ++ret; + + erase_element (*i); + + return ret; + } + + /* Erase all the elements. The elements are not destroyed. */ + void clear () + { + while (!this->empty ()) + pop_front (); + } + + /* Erase all the elements. Disposer::operator()(pointer) is called + for each of the removed elements. */ + template<typename Disposer> + void clear_and_dispose (Disposer disposer) + { + while (!this->empty ()) + { + pointer p = &front (); + pop_front (); + disposer (p); + } + } + + bool empty () const + { + return m_front == nullptr; + } + + iterator begin () noexcept + { + return iterator (m_front); + } + + const_iterator begin () const noexcept + { + return const_iterator (m_front); + } + + const_iterator cbegin () const noexcept + { + return const_iterator (m_front); + } + + iterator end () noexcept + { + return {}; + } + + const_iterator end () const noexcept + { + return {}; + } + + const_iterator cend () const noexcept + { + return {}; + } + + reverse_iterator rbegin () noexcept + { + return reverse_iterator (m_back); + } + + const_reverse_iterator rbegin () const noexcept + { + return const_reverse_iterator (m_back); + } + + const_reverse_iterator crbegin () const noexcept + { + return const_reverse_iterator (m_back); + } + + reverse_iterator rend () noexcept + { + return {}; + } + + const_reverse_iterator rend () const noexcept + { + return {}; + } + + const_reverse_iterator crend () const noexcept + { + return {}; + } + +private: + static node_type *as_node (T *elem) + { + return AsNode::as_node (elem); + } + + T *m_front = nullptr; + T *m_back = nullptr; +}; + +#endif /* GDBSUPPORT_INTRUSIVE_LIST_H */ diff --git a/gdbsupport/reference-to-pointer-iterator.h b/gdbsupport/reference-to-pointer-iterator.h new file mode 100644 index 0000000..7303fa4 --- /dev/null +++ b/gdbsupport/reference-to-pointer-iterator.h @@ -0,0 +1,79 @@ +/* An iterator wrapper that yields pointers instead of references. + Copyright (C) 2021 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H +#define GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H + +/* Wrap an iterator that yields references to objects so that it yields + pointers to objects instead. + + This is useful for example to bridge the gap between iterators on intrusive + lists, which yield references, and the rest of GDB, which for legacy reasons + expects to iterate on pointers. */ + +template <typename IteratorType> +struct reference_to_pointer_iterator +{ + using self_type = reference_to_pointer_iterator; + using value_type = typename IteratorType::value_type *; + using reference = typename IteratorType::value_type *&; + using pointer = typename IteratorType::value_type **; + using iterator_category = typename IteratorType::iterator_category; + using difference_type = typename IteratorType::difference_type; + + /* Construct a reference_to_pointer_iterator, passing args to the underyling + iterator. */ + template <typename... Args> + reference_to_pointer_iterator (Args &&...args) + : m_it (std::forward<Args> (args)...) + {} + + /* Create a past-the-end iterator. + + Assumes that default-constructing an underlying iterator creates a + past-the-end iterator. */ + reference_to_pointer_iterator () + {} + + /* Need these as the variadic constructor would be a better match + otherwise. */ + reference_to_pointer_iterator (reference_to_pointer_iterator &) = default; + reference_to_pointer_iterator (const reference_to_pointer_iterator &) = default; + reference_to_pointer_iterator (reference_to_pointer_iterator &&) = default; + + value_type operator* () const + { return &*m_it; } + + self_type &operator++ () + { + ++m_it; + return *this; + } + + bool operator== (const self_type &other) const + { return m_it == other.m_it; } + + bool operator!= (const self_type &other) const + { return m_it != other.m_it; } + +private: + /* The underlying iterator. */ + IteratorType m_it; +}; + +#endif /* GDBSUPPORT_REFERENCE_TO_POINTER_ITERATOR_H */ |