[Tinyos-devel] reentrancy

[David Gay]

On 6/15/07, John Regehr <regehr at cs.utah.edu> wrote:
> I'm trying to figure out what sort of reentrant calls a correct nesC component
> needs to defend against.

I'm going to answer this by explaining how I think about these things,
with some new terminology to avoid confusion with the existing
command/event/component concepts.

Let me propose the following categories of commands and events:
- "internal call": a call between two components implementing the same
service - these are fully under the programmer's control.
- "service requests": these are functions (typically commands, but
occasionally events) that form the logical specification of the
service
- "service indications": these are the functions called by the service
to signify that something relevant has happened; it's worth
distinguishing "spontaneous" indications over which the service user
has no control (ex: message reception) from the more deterministic
ones (e.g., a readDone following a read)
- "external requests": these are the calls the service makes to other
services, to request the execution of some functionality
- "external indications": these are the indications from the other
services, again "spontaneous" if not directly caused by some request

Given these categories, when you:
  * call one of your service indications (typically signal an event)
  * return from one of your service requests (typically finish a
command you implement)
  * finish handling some external indication or task (typically finish
an event you implement)
you should be prepared to handle:
  * your own service requests
  * any spontaneous external indications
  * any "pending" external indications (i.e., caused by one of your
earlier requests)

What's maybe less clear is what you should also expect these when
calling a service request of some other service: the
command-shall-not-signal-event rule prevents the reception of
indications, but not of your own service requests...

Offhand, people definitely rely on the fact that when you call "read"
you don't get "readDone" before the "read" call returns, but I'm not
sure if they rely so much on not receiving other indications. See
further comment below.

> Just to be totally clear, what I mean here is: when a component calls a command
> or signals an event, the flow of control may next enter the component (1) when
> the call returns or (2) through a new command/event invocation.  I am interested
> in case 2.  Interrupts do not enter the picture, this is all about sequential code.
>
> The first hint in Phil's book is "It's dangerous to signal events from commands,
> as you might cause a very long call loop, corrupt memory and crash your
> program."  This implies that commands should return directly whereas events may
> reenter through one or more commands before the event call itself returns.

Not really - a command may call another command, and so on. Beyond
delaying indications until after the request completes, the
command-shall-not-call-event prohibition prevents recursive loops: if
you assume your component graph forms a DAG (arrows directed from
uses->provides) and no command signals an event, then there can be no
recursion across components. Presumably programmers can avoid writing
recursive loops within a single module...

The component graph is usually (or at least nearly) a DAG because
components tend to map to services, which have a natural hierarchy
from high-level to low-level to hardware services.

To get back to the first half of this e-mail: if the component (well,
service really) graph is not a DAG, then:
  * when making an external request, you should be prepared to handle
any of your own requests
  * recursive cross-component loops are again a possibility

Recursive loops are bad because you'll likely overflow the stack. And
if you somehow had lots of stack space then you'ld probably run for
too long...

> Does
> this correspond with current practice and with the mental model that TinyOS 2.0
> hackers have of their components?
>
> I vaguely remember that an old version of TinyOS came with a tool that actually
> checked for violations of Phil's suggestion.  Is there any interest in reviving
> such a thing, or do people prefer to be able to violate this suggestion under
> controlled circumstances?

TinyOS 1 definitely had a violation or two of the
command-signaling-event policy, and good reasons not to fix them. Not
sure if this is true of T2.

I wouldn't be horribly surprised to learn that our components (or even
services) don't form a DAG, e.g., opX of service A requests op1 from
service B, which requests opY from service A.

Reporting loops in the callgraph seems worthwhile, especially if we
add an attribute so that we can break false-or-intended cycles.

David