Concurrency models for Squeak-E (was: squeak-e and ANSI
Mark S. Miller
markm at caplet.com
Sat Feb 1 16:56:44 CET 2003
At 02:02 PM 2/1/2003 Saturday, Robert Withers wrote:
>I don't know how important eventual sending is in providing a system supporting capabilities.
>I suppose the broader question is do we need to do this to support capabilities?
There's no direct coupling between these two, but there's some indirect
coupling explained below. The Ode
http://erights.org/elib/capability/ode/index.html explains E's security
model well, but uses only the sequential subset of E to do so. Of course, a
purely sequential model of computation is as vulnerable as can be to denial
of service -- a single infinite loop blocks the universe. The inset bug
description on http://erights.org/elib/capability/ode/ode-bearer.html is a
subtler form of this same issue. But a purely sequential call-return
Squeak-E language with capabilities, no event loops, no eventual sends, no
promises, and no communication would still be a valid capability system,
since capability systems don't generally claim resistance to denial of
service. (KeyKOS and EROS are notable exceptions.)
The real issue is how to add concurrency to sequential capability
computation, in order to get concurrent and/or distributed capability
computation. (Since we're starting with Squeak, we should ignore purely
concurrent capability systems, like Actors, FCP, and Joule.)
I know that E's model of concurrency does work well with capabilities, and
can be added to sequential Squeak as Rob has been doing.
The very different KeyKOS/EROS model also works well with capabilities, but
cannot be added to sequential Squeak without a rather violent refactoring of
lots of code. (In the KeyKOS/EROS model, recursive entry must cause a
deadlock, even when it's recursive sequential entry. In their context, this
is indeed the right design choice for reasons I won't go into.
Java's concurrency is incompatible with capability security. As one example,
two objects sharing the same immutable string should not thereby be able to
communicate with each other. After all, the string says its immutable.
However, this string has an implicit lock and can be synchronized on.
Further, two separately loaded classes that have never been given access to
any common objects can still obtain shared access to such a string for
communications, since Java literal strings are interned at class-loading
time. The collaborators need only name the same literal string in their
source code. By naming three strings, they can use a simple bus protocol to
communicate arbitrary bit sequences reliably.
But the above Java problem is just stupid. One can do a Java-like
concurrency model without any problems that egregious. As I recall, PPS2.5
had a similar model, but less preemptive. (Where is Squeak's model
documented?) Let's call this class of models "Threads & Locks", where the
same object may be accessed by different threads (shared memory
multi-threading) leading to monitors or semaphores or some kind of
fine-grained locking to try to keep these threads from stepping on each
others toes. Security aside, I think this model has been an unmitigated
disaster for correctness and reliability
I know that David Reed has proposed an interesting concurrency and
distributed computing model for Croquet. I'd love to see a description of it.
I don't yet know enough to comment.
A language for writing secure programs must first of all be a language for
writing reliable programs. E's event-loop concurrency preserves most of the
reliability of sequential programs. I recommend reading
, the section "Non-security Elements that Simplified Review" in the Darpa
Security Review of E and the DarpaBrowser (written in E), where David Wagner
and Dean Tribble write:
>As a result, objects in E never deal with synchronization. Consequently,
>all potential time-of-check-to- time-of-use (TOCTTOU) vulnerabilities could
>be evaluated within a single flow of control, and thus took little time to
>check for. By contrast, in systems in which multiple threads interact within
>objects, such determinations can be extremely difficult or infeasible to
Since proving substantial programs either correct or secure (for complex
security goals) is not yet feasible, and probably won't be any time soon,
such reductions in efforts for manual inspection and review processes are
quite important. I also believe they are a good predictor of the
programmer's ability to write it correctly with higher confidence and lower
effort in the first place.
Finally, Smalltalk isn't just a system. It stand for a philosophy named
"object-oriented programming". From my sense of what this philosophy is,
capabilities could be termed "object-oriented security". (This coinage by
Dean Tribble.) The virtues of capabilities are an extension of the virtues
of oo. Likewise, I believe E's event-loop concurrency control model is the
extension of the oo philosophy into the concurrency realm, which we try to
make clear especially at http://erights.org/elib/concurrency/event-loop.html
and http://erights.org/elib/concurrency/turns.html . In these three cases --
objects, security, concurrency -- the issues can be seen in the terms the
economist F.A. Hayek explained: How do plans come to be coordinated with
each other (message passing) without disrupting each other (encapsulation)?
For an object-oriented view of Hayekian economics, see
So I hope we make Squeak-E a system that not only works, but one that's also
a purer expression of the philosophy that Smalltalk has always stood for.
Text by me above is hereby placed in the public domain
More information about the Squeak-e