[Squeak-e] Concurrency models for Squeak-E (was: squeak-e and ANSI Smalltalk)

[Mark S. Miller]

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, 
<rant>
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.
</rant>

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 
http://erights.org/elib/concurrency/event-loop.html .

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 
http://www.combex.com/papers/darpa-review/security-review.html#non-security 
, 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 
>determine.

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 
http://www.erights.org/talks/categories/index.html .

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

        Cheers,
        --MarkM