[L2Ork-dev] Delayed pd_unbind

[Albert Graef]

On Thu, Nov 14, 2013 at 12:09 PM, Ivica Bukvic <ico at vt.edu> wrote:
> Great! I will definitely commit this patch.

Thanks, that's much appreciated. :)

> That said, are the memory leaks
> a result of a delayed unbind or are these also apparent in vanilla?

The former. It's somewhat hard to come up with a minimal example, but
let me try to explain once more how this happens in terms of a simple
example. I've actually implemented this, albeit in Pure (using the
pd-pure plugin), so you'll need that plugin along with an installation
of the Pure interpreter to run the example (there are pure and
pdl2ork-pure packages for most recent Ubuntu releases on my Launchpad
page if you don't want to compile this stuff yourself). The example is
attached to this post in case you want to give it a try.

Suppose you have an object `foo` which binds two receivers `foo` and
`bar` in its initialization. In addition, when the `foo` object
receives a message via the `foo` receiver, it unbinds the `bar`
receiver. (It doesn't really matter what the `bar` receiver does, in
my example I simply let it output a string value on the outlet of the
`foo` object so that I can verify whether the `bar` receiver is still
bound or not.)

Now, when a message is sent to the `foo` receiver (a `bang` in the
example), it gets delivered through the appropriate bindlist function
(bindlist_bang in the example, which gets invoked with x = the
bindlist of the `foo` symbol), so the change_bindlist_via_graph flag
is set. The `foo` object receives the message and unbinds the `bar`
receiver. Note that this modifies the bindlist for the `bar` symbol
and increments the change_bindlist_via_graph flag. Thus, once
execution returns to bindlist_bang, the bindlist_cleanup function will
be invoked all right, but note that it is invoked on x = the bindlist
of the `foo` symbol. But the bindlist which was actually modified is
the list for `bang`, not the one for `foo`, so nothing happens in
bindlist_cleanup.

This isn't a problem if there's just a single `bar` receiver, because
in this case the receiver object is stored inside the symbol itself
and there's no memory for a bindlist allocated. But in the example I
actually have two instances of the `foo` object which each initialize
their own instance of the `bar` receiver, so there are now two `bar`
receivers, and thus the s_thing member of the `bar` symbol is a proper
bindlist with two entries. So when the first of these bindings gets
removed, pd_unbind takes code path "B" and, since the
change_bindlist_via_graph flag is set, will defer the deallocation of
the corresponding bindlist entry, assuming that bindlist_cleanup will
take care of that later. But the subsequent invocation
bindlist_cleanup never sees the `bar` bindlist since it just traverses
the `foo` bindlist. Et voila, we leak memory on the `bar` bindlist.

Here's the log I get on stdout that I get when running the attached
example and clicking on the `bang`->`s foo` on the right. Note that I
uncommented a few of the debugging printfs that you have in m_pd.c to
see what's going on; I also added some information so that I can see
which bindlists the functions operate on.

pd_unbind bar (s->s_thing = 0x27d77c0, change_bindlist_via_graph = 1)
pd_unbind option B 36fb550
success B1a
success B2
pd_unbind bar (s->s_thing = 0x2d485c0, change_bindlist_via_graph = 2)
pd_unbind option A 2d485c0
bindlist_cleanup (t_bindlist *x = 0x250b370)

As you can see, the first `pd_unbind bar` gets invoked on the bindlist
0x27d77c0, which then gets shrunk to size 1 (and thus the bindlist is
eliminated at this point). The second `pd_unbind bar` call then gets
rid of that single remaining entry as well. But the bindlist 0x27d77c0
for `bar` never really gets deallocated, since that's supposed to be
handled by bindlist_cleanup, which however gets invoked on the
bindlist 0x250b370 for `foo` which doesn't have any entries to be
deleted, so nothing happens there and the bindlist for `bar` keeps
sticking around, leaking memory.

Note that in this case we only get a memory leak, since the `bar`
symbol data structure was updated properly in the end, so everything
works as expected. But I can imagine more complicated cases (with
bindlists of size three or more), where those leaked bindlist entries
stick around in the data structure and thus cause problems later. So
we really must get rid of those leaks for a proper solution.

> Knowing more about your
> implementation of the newly proposed deallocation method will help me
> potentially contribute to the fix. Many thanks!

We would need to keep track of all affected bindlists, so that the
deleted entries can all be deallocated by bindlist_cleanup, no matter
which bindlist they come from. I'm still thinking about an efficient
way to do this. There's no a priori limit on the number of bindlist
entries which could be deleted during a bindlist traversal, so simply
storing the affected bindlists in a static array is not guaranteed to
work. But we could add an extra field to the symbol data structure
which would allow us to create a singly linked list of all affected
symbols which could then be traversed by bindlist_cleanup. That would
cost an extra pointer per symbol (a 33% increase), which might be
acceptable.

However, I'm still not quite convinced that this is the best way to
go. The root issue here seems to be that the traversal of the bindlist
in the bindlist functions segfaults because bindlist entries may
suddenly disappear if pd_unbind deletes them right away, right? Then
we might also go about hardening the bindlist functions so that they
are able to traverse a bindlist even if it gets modified during the
traversal. If we can make that work then it would be a cleaner
solution IMHO.

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  aggraef at gmail.com
WWW:    https://plus.google.com/+AlbertGraef
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.tar.bz2
Type: application/x-bzip2
Size: 702 bytes
Desc: not available
URL: <http://disis.music.vt.edu/pipermail/l2ork-dev/attachments/20131114/8f8e387c/attachment.bin>