develooper Front page | perl.perl5.porters | Postings from October 2011

Towards Threadsafe Modification of Optrees

Thread Next
From:
Steffen Mueller
Date:
October 7, 2011 00:28
Subject:
Towards Threadsafe Modification of Optrees
Message ID:
4E8EA9FA.8000005@cpan.org
Context
=======
In memory, Perl subroutines are represented by a tree[1] of OP
structures ("optree"). Note that it's one optree per subroutine. These 
data structures are then walked during execution. They are shared 
between ithreads.

Problem
=======
Modifying the optree at run-time is not thread-safe due to being
shared between ithreads, see below. Doing that, however, could
possibly open an opportunity for various optimizations and experiments.
A rather trivial case is implemented today, for example, in the
Class::XSAccessor module[2], which is used in production all over the
world[3].

Even when explicitly preventing concurrent *modification* using locks,
changes can have catastrophic results.
Consider (t$i is thread $i, o$j is optree $j):

a) t1 and t2 executing o1

     o1 -----
        \  <--- t1 wants to make modification here
         \--
          \
           \---t2 is executing here

b) t1 replaces the fragment of the optree which t2 currently executes.

      o1 -----
       X new bit of optree replaces the old
        \----
         ...

       X <--- old op tree fragment
        \
         \--
          \
           \---t2 is executing here

c) Segfault when t2 finishes executing the now dangling optree fragment

Even less drastic cases like replacing a single op at a time might be
subject to this class of hard crash[citation needed].


Hand-waving sketch of a solution
================================
I discussed this general issue with various people at the previous
YAPC::EU, including Nicholas and Hugo. The ideas here aren't all mine.
The thinkos likely are, though.

Even if we were able to do sufficiently safe locking for optree
modifications, thus preventing the above example failure mode, the
manipulated optree would still leak from one ithread to another. If you
consider manipulations that may change behaviour (instead of just
optimizing[4]), this is very bad.  Clearly, there needs to be some
degree of separation between at least the modified optrees of multiple
ithreads.

The trivial way to make optree manipulation thread-safe would be to
clone the optrees on ithread creation. This is undesireable due to the
high memory and ithread-startup cost. Possibly, if optree munging ever
becomes common, cloning the optrees may become a more reasonable
default, but for the time being, this is out.

The next obvious approach would be some form of copy-on-write. An
attempt to pull this off would be something like:

1) Make optrees refcounted. That is, the whole of an optree, not each
    OP.
2) When creating ithreads, increment all optrees' refcounts for the
    new ithread.
3) When about to modify any given optree, clone it for the thread that
    wants to modify it.

Unfortunately, this has some subtle issues bits that need careful
consideration. I doubt that I have them all worked out:

With this CoW scheme, each "child" ithread would have a "parent"
ithread whose optree the child points to before any modification.
The following simple case:

   Two threads t1, t2.
   t2 was created from t1.
   => o1 referenced by t1, t2

Scenario 1)
- t2 wants to modify the optree of a sub.
   a) t2 lones o1 to o2.
   b) o1 refcount decremented. (=1)
   c) t2 modifies o2.

Scenario 2), same starting point:
- t1 wants to modify the optree of a sub.
   a) t1 clones o1 to o1'.
   b) o1 refcount decremented. (=1)
   c) t1 modifies o1', t2 continues to use o1.

Scenario 3),
- t2 wants to modify the optree of a sub. => Scenario 1)
- Now t1 wants to modify the optree of the same sub.
   a) t1 sees that the refcount of o1 is 1 and does NOT
      clone it.[5]
   b) t1 modifies o1.

If thought-experimented with various more complicated cases involving
more threads. What needs to be thought throught is some of the nasty
concurrency: t1, t2, t3 all want to modify the same o1, so the refcount
check and the clone may have to be done in a transactional/locked way.

The technical steps that would have to be taken for this to work could,
as I see it, be broken down as follows:

1) Refcounted optrees. (Including appropriate refcount changes during
    thread creation and destruction)
2) A function to clone an entire optree. (Is this even possible? Who
    can have pointers to optrees? Only CVs?)
3) An API to assert a (currently) exclusive copy of an optree for
    manipulation. This would have to support automatically walking to
    the root of the optree from any OP so that the manipulating-user
    does not have to re-code that every time he wants to replace a
    single random OP.

Is this feasible? Is it useful? Is it worthwhile? How is it flawed?

Best regards,
Steffen


[1] In comp. sci. terms, this is not strictly a tree, but rather just
a graph.

[2] It replaces a single entersub OP. Due to the dynamic nature of the
language, however, it may have to do so multiple times: Once for
optimization and once possibly for pessimization of the callsite turns
out to occasionally call different CVs, see the comments in
http://cpansearch.perl.org/src/SMUELLER/Class-XSAccessor-1.12/XSAccessor.xs
for more details.

[3] Sorry, my fault. I promise to fix it when it breaks.

[4] Even optimizations might have to be thread-local: Consider a JIT
     that uses run-time info to optimize. One ithread's optimization
     may be another's pessimization.

[5] This optimization is both safe and important. It is safe because
     the refcount will never grow unless the same thread is spawning
     a new ithread and we know that's not currently the case. It is
     important because otherwise, we incur a full optree clone for every
     modification.

Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About