[PATCH v5 1/2] gdbsupport: allow to specify dependencies between observers
Andrew Burgess
andrew.burgess@embecosm.com
Tue Apr 27 08:30:25 GMT 2021
* Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> [2021-04-26 10:53:39 -0400]:
> From: Michael Weghorn <m.weghorn@posteo.de>
>
> Previously, the observers attached to an observable were always notified
> in the order in which they had been attached. That order is not easily
> controlled, because observers are typically attached in _initialize_*
> functions, we are called in an undefined order.
>
> However, an observer may require that another observer attached only
> later is called before itself is.
>
> Therefore, extend the 'observable' class to allow explicitly specifying
> dependencies when attaching observers, by adding the possibility to
> specify tokens for observers that it depends on.
>
> To make sure dependencies are notified before observers depending on
> them, the vector holding the observers is sorted in a way that
> dependencies come before observers depending on them. The current
> implementation for sorting uses the depth-first search algorithm for
> topological sorting as described at [1].
>
> Extend the observable unit tests to cover this case as well. Check that
> this works for a few different orders in which the observers are
> attached.
>
> This newly introduced mechanism to explicitly specify dependencies will
> be used in a follow-up commit.
>
> [1] https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
>
> Tested on x86_64-linux (Debian testing).
>
> gdb/ChangeLog:
>
> * unittests/observable-selftests.c (dependency_test_counters):
> New.
> (observer_token0, observer_token1, observer_token2,
> observer_token3, observer_token4, observer_token5): New.
> (struct dependency_observer_data): New struct.
> (observer_dependency_test_callback): New function.
> (test_observers): New.
> (run_dependency_test): New function.
> (test_dependency): New.
> (_initialize_observer_selftest): Register dependency test.
>
> gdbsupport/ChangeLog:
>
> * observable.h (class observable): Extend to allow specifying
> dependencies between observers, keep vector holding observers
> sorted so that dependencies are notified before observers
> depending on them.
I had some really minor feedback on some comments, otherwise looks
good.
>
> Change-Id: I5399def1eeb69ca99e28c9f1fdf321d78b530bdb
> ---
> gdb/unittests/observable-selftests.c | 112 +++++++++++++++++++++++++++
> gdbsupport/observable.h | 111 ++++++++++++++++++++++----
> 2 files changed, 207 insertions(+), 16 deletions(-)
>
> diff --git a/gdb/unittests/observable-selftests.c b/gdb/unittests/observable-selftests.c
> index 0e3b53f555b0..88b009f1188d 100644
> --- a/gdb/unittests/observable-selftests.c
> +++ b/gdb/unittests/observable-selftests.c
> @@ -30,6 +30,60 @@ static int test_first_observer = 0;
> static int test_second_observer = 0;
> static int test_third_observer = 0;
>
> +/* Counters for observers used for dependency tests. */
> +static std::vector<int> dependency_test_counters;
> +
> +/* Tokens for observers used for dependency tests. */
> +static gdb::observers::token observer_token0;
> +static gdb::observers::token observer_token1;
> +static gdb::observers::token observer_token2;
> +static gdb::observers::token observer_token3;
> +static gdb::observers::token observer_token4;
> +static gdb::observers::token observer_token5;
> +
> +/* Data for one observer used for checking that dependencies work as expected;
> + dependencies are specified using their indices into the 'test_observers'
> + vector here for simplicity and mapped to corresponding tokens later. */
> +struct dependency_observer_data
> +{
> + gdb::observers::token *token;
> +
> + /* Name of the observer to use on attach. */
> + const char *name;
> +
> + /* Indices of observers that this one directly depends on. */
> + std::vector<int> direct_dependencies;
> +
> + /* Indices for all dependencies, including transitive ones. */
> + std::vector<int> all_dependencies;
> +
> + /* Function to attach to the observable for this observer. */
> + std::function<void (int)> callback;
> +};
> +
> +static void observer_dependency_test_callback (size_t index);
> +
> +/* Data for observers to use for dependency tests, using some sample
> + dependencies between the observers. */
> +static std::vector<dependency_observer_data> test_observers = {
> + {&observer_token0, "test0", {}, {},
> + [] (int) { observer_dependency_test_callback (0); }},
> + {&observer_token1, "test1", {0}, {0},
> + [] (int) { observer_dependency_test_callback (1); }},
> + {&observer_token2, "test2", {1}, {0, 1},
> + [] (int) { observer_dependency_test_callback (2); }},
> + {&observer_token3, "test3", {1}, {0, 1},
> + [] (int) { observer_dependency_test_callback (3); }},
> + {&observer_token4, "test4", {2, 3, 5}, {0, 1, 2, 3, 5},
> + [] (int) { observer_dependency_test_callback (4); }},
> + {&observer_token5, "test5", {0}, {0},
> + [] (int) { observer_dependency_test_callback (5); }},
> + {nullptr, "test6", {4}, {0, 1, 2, 3, 4, 5},
> + [] (int) { observer_dependency_test_callback (6); }},
> + {nullptr, "test7", {0}, {0},
> + [] (int) { observer_dependency_test_callback (7); }},
> +};
> +
> static void
> test_first_notification_function (int arg)
> {
> @@ -63,6 +117,62 @@ notify_check_counters (int one, int two, int three)
> SELF_CHECK (three == test_third_observer);
> }
>
> +/* Function for each observer to run when being notified during the
> + dependency tests. Verifies that dependencies have been notified earlier
> + by checking their counters, then increases the own counter. */
I don't think this sentence is quite correct, maybe ", then increases
the observer's counter." ?
> +static void
> +observer_dependency_test_callback (size_t index)
> +{
> + /* Check that dependencies have already been notified. */
> + for (int i : test_observers[index].all_dependencies)
> + SELF_CHECK (dependency_test_counters[i] == 1);
> +
> + /* Increase own counter. */
> + dependency_test_counters[index]++;
> +}
> +
> +/* Run a dependency test by attaching the observers in the specified order
> + then notifying them. */
> +static void
> +run_dependency_test (std::vector<int> insertion_order)
> +{
> + gdb::observers::observable<int> dependency_test_notification
> + ("dependency_test_notification");
> +
> + /* Reset counters. */
> + dependency_test_counters = std::vector<int> (test_observers.size (), 0);
> +
> + /* Attach all observers in the given order, specifying dependencies. */
> + for (int i : insertion_order)
> + {
> + const dependency_observer_data &o = test_observers[i];
> +
> + /* Get tokens for dependencies using their indices. */
> + std::vector<const gdb::observers::token *> dependency_tokens;
> + for (int index : o.all_dependencies)
> + dependency_tokens.emplace_back (test_observers[index].token);
> +
> + if (o.token != nullptr)
> + dependency_test_notification.attach
> + (o.callback, *o.token, o.name, dependency_tokens);
> + else
> + dependency_test_notification.attach (o.callback, o.name,
> + dependency_tokens);
> + }
> +
> + /* Notify observers, they check that their dependencies were notified. */
> + dependency_test_notification.notify (1);
> +}
> +
> +static void
> +test_dependency ()
> +{
> + /* Run dependency tests with different insertion orders. */
> + run_dependency_test ({0, 1, 2, 3, 4, 5, 6, 7});
> + run_dependency_test ({7, 6, 5, 4, 3, 2, 1, 0});
> + run_dependency_test ({0, 3, 2, 1, 7, 6, 4, 5});
> +}
> +
> static void
> run_tests ()
> {
> @@ -133,4 +243,6 @@ _initialize_observer_selftest ()
> {
> selftests::register_test ("gdb::observers",
> selftests::observers::run_tests);
> + selftests::register_test ("gdb::observers dependency",
> + selftests::observers::test_dependency);
> }
> diff --git a/gdbsupport/observable.h b/gdbsupport/observable.h
> index 4ba47bb988f4..648158c8ca23 100644
> --- a/gdbsupport/observable.h
> +++ b/gdbsupport/observable.h
> @@ -71,13 +71,15 @@ class observable
> private:
> struct observer
> {
> - observer (const struct token *token, func_type func, const char *name)
> - : token (token), func (func), name (name)
> + observer (const struct token *token, func_type func, const char *name,
> + const std::vector<const struct token *> &dependencies)
> + : token (token), func (func), name (name), dependencies (dependencies)
> {}
>
> const struct token *token;
> func_type func;
> const char *name;
> + std::vector<const struct token *> dependencies;
> };
>
> public:
> @@ -88,30 +90,29 @@ class observable
>
> DISABLE_COPY_AND_ASSIGN (observable);
>
> - /* Attach F as an observer to this observable. F cannot be
> - detached.
> + /* Attach F as an observer to this observable. F cannot be detached or
> + specified as a dependency.
We should probably document DEPENDENCIES here too, like you do for the
alternative attach below.
>
> NAME is the name of the observer, used for debug output purposes. Its
> lifetime must be at least as long as the observer is attached. */
> - void attach (const func_type &f, const char *name)
> + void attach (const func_type &f, const char *name,
> + const std::vector<const struct token *> &dependencies = {})
> {
> - observer_debug_printf ("Attaching observable %s to observer %s",
> - name, m_name);
> -
> - m_observers.emplace_back (nullptr, f, name);
> + attach (f, nullptr, name, dependencies);
> }
>
> - /* Attach F as an observer to this observable. T is a reference to
> - a token that can be used to later remove F.
> + /* Attach F as an observer to this observable.
> +
> + T is a reference to a token that can be used to later remove F or specify F
> + as a dependency of another observer. Dependencies are notified before the
> + observer depending on them.
The wording here, though completely accurate, confused me at first.
How about:
"DEPENDENCIES are notified before this observer."
It confused me because attach is attaching an observer, but you talk
about "the observer depending on them", which (for a moment) made we
wonder if there was some other observer being referenced.
Otherwise looks good.
Thanks,
Andrew
>
> NAME is the name of the observer, used for debug output purposes. Its
> lifetime must be at least as long as the observer is attached. */
> - void attach (const func_type &f, const token &t, const char *name)
> + void attach (const func_type &f, const token &t, const char *name,
> + const std::vector<const struct token *> &dependencies = {})
> {
> - observer_debug_printf ("Attaching observable %s to observer %s",
> - name, m_name);
> -
> - m_observers.emplace_back (&t, f, name);
> + attach (f, &t, name, dependencies);
> }
>
> /* Remove observers associated with T from this observable. T is
> @@ -149,6 +150,84 @@ class observable
>
> std::vector<observer> m_observers;
> const char *m_name;
> +
> + /* Use for sorting algorithm, to indicate which observer we have visited. */
> + enum class visit_state
> + {
> + NOT_VISITED,
> + VISITING,
> + VISITED,
> + };
> +
> + /* Helper method for topological sort using depth-first search algorithm.
> +
> + Visit all dependencies of observer at INDEX in M_OBSERVERS (later referred
> + to as "the observer"). Then append the observer to SORTED_OBSERVERS.
> +
> + If the observer is already visited, do nothing. */
> + void visit_for_sorting (std::vector<observer> &sorted_observers,
> + std::vector<visit_state> &visit_states, int index)
> + {
> + if (visit_states[index] == visit_state::VISITED)
> + return;
> +
> + /* If we are already visiting this observer, it means there's a cycle. */
> + gdb_assert (visit_states[index] != visit_state::VISITING);
> +
> + visit_states[index] = visit_state::VISITING;
> +
> + /* For each dependency of this observer... */
> + for (const token *dep : m_observers[index].dependencies)
> + {
> + /* ... find the observer that has token DEP. If found, visit it. */
> + auto it_dep
> + = std::find_if (m_observers.begin (), m_observers.end (),
> + [&] (observer o) { return o.token == dep; });
> + if (it_dep != m_observers.end ())
> + {
> + int i = std::distance (m_observers.begin (), it_dep);
> + visit_for_sorting (sorted_observers, visit_states, i);
> + }
> + }
> +
> + visit_states[index] = visit_state::VISITED;
> + sorted_observers.push_back (m_observers[index]);
> + }
> +
> + /* Sort the observers, so that dependencies come before observers
> + depending on them.
> +
> + Uses depth-first search algorithm for topological sorting, see
> + https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search . */
> + void sort_observers ()
> + {
> + std::vector<observer> sorted_observers;
> + std::vector<visit_state> visit_states (m_observers.size (),
> + visit_state::NOT_VISITED);
> +
> + for (size_t i = 0; i < m_observers.size (); i++)
> + visit_for_sorting (sorted_observers, visit_states, i);
> +
> + m_observers = std::move (sorted_observers);
> + }
> +
> + void attach (const func_type &f, const token *t, const char *name,
> + const std::vector<const struct token *> &dependencies)
> + {
> +
> + observer_debug_printf ("Attaching observable %s to observer %s",
> + name, m_name);
> +
> + m_observers.emplace_back (t, f, name, dependencies);
> +
> + /* The observer has been inserted at the end of the vector, so it will be
> + after any of its potential dependencies attached earlier. If the
> + observer has a token, it means that other observers can specify it as
> + a dependency, so sorting is necessary to ensure those will be after the
> + newly inserted observer afterwards. */
> + if (t != nullptr)
> + sort_observers ();
> + };
> };
>
> } /* namespace observers */
> --
> 2.30.1
>
More information about the Gdb-patches
mailing list