[v5,1/2] gdbsupport: allow to specify dependencies between observers

Message ID 20210426145340.493597-2-simon.marchi@polymtl.ca
State New
Headers show
Series
  • Make sure autoload happens before notifying Python side in new_objfile event
Related show

Commit Message

Hannes Domani via Gdb-patches April 26, 2021, 2:53 p.m.
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.

Change-Id: I5399def1eeb69ca99e28c9f1fdf321d78b530bdb
---
 gdb/unittests/observable-selftests.c | 112 +++++++++++++++++++++++++++
 gdbsupport/observable.h              | 111 ++++++++++++++++++++++----
 2 files changed, 207 insertions(+), 16 deletions(-)

-- 
2.30.1

Comments

Hannes Domani via Gdb-patches April 26, 2021, 7:56 p.m. | #1
On 26/04/2021 16.53, Simon Marchi wrote:
> 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.


Just a nit-pick, should that read "functions, WHICH 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).


Michael
Hannes Domani via Gdb-patches April 26, 2021, 10:18 p.m. | #2
On 2021-04-26 3:56 p.m., Michael Weghorn wrote:
> On 26/04/2021 16.53, Simon Marchi wrote:

>> 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.

> 

> Just a nit-pick, should that read "functions, WHICH are called in an undefined order."?


Yes, thanks for spotting that.

Simon
Andrew Burgess April 27, 2021, 8:30 a.m. | #3
* 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

>
Hannes Domani via Gdb-patches April 27, 2021, 1:34 p.m. | #4
>> +/* 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." ?


Indeed.  I ended up doing a bit more changes:

120 /* Function for each observer to run when being notified during the dependency
121    tests.  Verify that the observer's dependencies have been notified before the
122    observer itself by checking their counters, then increase the observer's own
123    counter.  */

>> @@ -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.


Indeed, I ended up re-wording see 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.


I ended up using this in both comments:

 96      DEPENDENCIES is a list of tokens of observers to be notified before this
 97      one.

> Otherwise looks good.


Thanks for the review!

Simon

Patch

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.  */
+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.
 
      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.
 
      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 */