Subject: Observers, collections and multiple threads

From: Alan Griffiths <[email-masked]>
Date: Fri, 27 Jun 2014 12:30:28 +0100

We've had a number of proposals recently that ran into issues with when
and what to lock in collections of observers and what actions on the
observed object (and its collection of observers) are possible while in
a notification callback. (Some links at bottom)

I don't know of a good approach that addresses all concerns (and a quick
internet search didn't find a good answer) but I thought I'd first write
out a list of the  concerns that have crawled out of our discussions.
And mention what we've discovered so far.

We've generally taken an approach that implies that the "observer"
objects making observations generally outlive the objects being
observed. Indeed the simplest case is that the observer is part of the
application infrastructure and not part of the dynamic state. For this
case it is simplest to create a "listener" object (that calls
notification methods on the observer) and pass its ownership to the
"subject". The observer can then forget about everything except handling
the notifications.

The naive approach is for the collection of listeners to be locked when
being updated and when sending notifications.

This works well until we hit one of two cases:
1. the observer takes some action that generates a new notification,
2. the observer is destroyed and needs to prevent further notifications
to a dead object.

In case 2 we expect the observer to remove the listener from the
subject's collection *after* which notifications cease. Note that
"after" implies we need a synchronization mechanism as multiple threads
can be involved.

In case 1, if we have hold exclusive lock during notifications then
we'll get a deadlock.

One solution that has been tried is to copy the collection and release
the lock. That doesn't work with the above solution to case 2: after
releasing the lock nothing prevents listeners being "removed" on another
thread *before* being invoked through the copy.

Another solution that has been tried is to hold a recursive lock during
notifications and updates to the collection. That allows other
notifications to take place *and changes to the collection*. So we still
take a copy of the collection and traverse that (to avoid iterators
invalidating), but before invoking them also check that objects exist in
the "true" collection. (There's an example in
MirEventDistributor::handle_event()).

Thank you for listening!

Alan

https://code.launchpad.net/~albaguirre/mir/avoid-surf-observer-deadlocks/+merge/224733/comments/539885
https://code.launchpad.net/~andreas-pokorny/mir/synchronous-cancel-of-alarms
https://code.launchpad.net/~alan-griffiths/mir/fix-1334287/+merge/224457/comments/538936
https://code.launchpad.net/~mir-team/mir/trusted_sessions/+merge/221191/comments/532580
https://code.launchpad.net/~mir-team/mir/introduce-scene-observer/+merge/216957

---

From: Andreas Pokorny <[email-masked]>
Date: Fri, 27 Jun 2014 14:54:25 +0200

Hi,
In the project I worked on before joining mir we made a few decisions early
that simplified those cases.
We declared that all the things that control the content of an output would
run inside a single thread and all operations on it are scheduled from a
single event loop.
Where output means a layer/overlay or an offscreen buffer integrated into
another scene.
So the processing of state machines, animation, scene processing like focus
handling, layout updates and rendering happens single threaded and entirely
lock free.

We allowed temporary observing individual widget properties and here we had
those issue:
1. An object decides to no longer observe a property, but it is currently
being called or will soon be called.
2. The object which is called within a change callback of a property causes
changes to other properties or the same property and hence further change
callbacks to the same or other objects.

We solved that like this:
1 ~ Since multi threading was defined to not exist - we simply marked those
in the observer list that have to be removed after calling each observer
that has not been marked to be disabled.
2 ~ Changes to values are applied immediately but we only notified
observers when the new value differs. In that case the observers are not
informed directly. Instead the object registers itself at the event loop
for the next "step". The event loop had a concept of steps. Each step
represents an intermediate step of the changes inside the scene. When no
step provokes a new step we are done and rendering may start. So at each of
those steps we dispatched the registered change notifications that were
accumulated in the previous step. After the first "empty" step the scene
was considered stable and rendering could start.

So with that decision thread safety was a convention every user had to
follow. If a component got triggered by some sort of external event and had
to manipulate the scene it either made sure that this external event source
was handled by the event loop of the scene or injected a task to the event
loop which then manipulates the scene.

I think especially problem (2) might become relevant for mir, as soon as
the scene model becomes more elaborate.

We stumbled across a problem rather late in the project, partially caused
by (2), the functor size and having to subscribe to each property
individually. That consumed a lot of memory, and tracking subscriptions -
i.e. subscribing to properties when objects enter the scene and undoing
that, took a measurable amount of time. There was a plan to circumvent that
by providing grouped subscription - as in subscribe to "each property <x>
of widgets derived from a certain type <y>".

regards
Andreas

On Fri, Jun 27, 2014 at 1:30 PM, Alan Griffiths <
[email-masked]> wrote:

> --
> Mir-devel mailing list
> [email-masked]
> Modify settings or unsubscribe at:
> https://lists.ubuntu.com/mailman/listinfo/mir-devel
>

---

From: Alberto Aguirre <[email-masked]>
Date: Fri, 27 Jun 2014 10:07:14 -0500

The problem with a recursive lock is that it may still lead to
subtle deadlocks if the observer generates new notifications on a different
thread - which may not be readily apparent to the person implementing the
observer ,
either because of complicated flow of events, or an external library may be
called which indirectly causes a new notification.

Note that for SurfaceObserver and Scene observer specifically, the
observers are stored in shared_ptr's so calling dead objects is not an
issue there.
But receiving at least an extra callback after registration is - which in
this case, I would say it's the burden of the observer.

---

From: Alberto Aguirre <[email-masked]>
Date: Fri, 27 Jun 2014 12:26:11 -0500

As Alan has pointed out the extra levels of indirection in an Observer
implemention does makes lifetime an issue
or rather it requires that observer removal should guarantee the observer
will not receive any more callbacks.

It definitely needs more pondering time...

On Fri, Jun 27, 2014 at 10:07 AM, Alberto Aguirre <
[email-masked]> wrote:

> either because of complicated flow of events, or an external library may
> be called which indirectly causes a new notification.
>