[cap-talk] Recursive Reentrant Invocation

[Matej Kosik]

Toby Murray wrote:
> On Wed, 2009-03-04 at 19:10 +0100, Matej Kosik wrote:
>> Toby Murray wrote:
>>> I need to think harder to work out whether Pict's derived forms for
>>> recursive functions allow you to write recursively reentrant code (see
>>> http://mail.eros-os.org/pipermail/e-lang/2009-February/013002.html for
>>> more on what I mean here).
>> I cannot give you sure answer because I do not exactly understand what
>> problem you discussed there. In this paragraph:
>>
>> "The thing that both of these attacks had in common was that they
>> exploited reentrancy-via-recursion. In both cases, an object, o,
>> implementing some abstraction must maintain some invariant. o must also
>> call some untrusted code. While calling the untrusted code, o can be
>> invoked recursively. This reentrant invocation of o causes its internal
>> invariants to be broken."
>>
>> What do you mean by "While calling the untrusted code, o can be
>> invoked recursively." ? What do you mean by "recursively"? Who could
>> invoke object o "recursively"?
> 
> Thinking just in terms of E (although hopefully it will translate easily
> to other languages too), let's say have an object o defined as follows.
> 
> def o {
> 
>    to foo(obj) {
>        obj.bar()
>    }
>    to baz() {
>         return null
>    }
> }
> o has two methods: foo(obj) and baz(). Calling o.foo(obj) causes o to
> call obj.bar(). Calling o.baz() causes o to return null.
> 
> Now suppose we have another object, weird:
> 
> def weird {
>     to go() {
>         o.foo(weird)
>     }
>     to bar() {
>         o.baz()
>     }
> }
> 
> And suppose we run
> weird.go()
> 
> What happens (view the following in a fixed-width font)?
> weird.go() calls o.foo(weird),
>                  o.foo(weird) calls weird.bar(),
>                                     weird.bar() calls o.baz(),
>                                                       o.baz() returns,
>                                     weird.bar() returns,
>                   o.foo(weird) returns,
> weird.go() returns,
> 
> The call-stack for the single thread that is executing all of the above
> grows from left-to-right.
> 
> We can see that object o gets recursively invoked.
> 
> This recursive invocation can cause problems because it might change
> local variables that o doesn't expect to change.

I think I understand what you mean. A program with such an error can be
written also in Pict. While the above scheme is artificial, in various
forms it can occur in practice.

Consider for example a simple kernel whose structure is shown
in Figure 6.2 in this document

    http://altair.sk/mediawiki/upload/2/2b/Backwater.pdf

There are various concurrent subsystems. Let us constrain only to the
following two:
- ClockMorph
- Timer
There, ClockMorph subsystem asks Timer subsystem to periodically call
(i.e. each 1000 milliseconds; i.e. each second) the renderTime procedure
defined within the scope of ClockMorph.

The renderTime procedure reads and updates local variable (which holds
the number of seconds) and converts it to time in HH:MM:SS format and
prints it.

Without any precaution, there is a risk of interference if that
procedure were invoked multiple times concurrently. In this case, I
resorted to usage of a semaphore which surrounds the critical section
where I:
- read the value of the local mutable variable
- update the value of the local mutable variable

Without that semaphore, there would be a similar kind of bug as I
indicated by the example you gave above.