bombilla.tex

tinyos中文手册,是根据tinyos系统自带手册翻译过来的,虽然质量不好,但是对英文不强的人还是有用的

\subsection{Capsule Injector}

\begin{figure}
\begin{center}
\includegraphics[width=2in]{fig/CapsuleInjector.jpg}
\caption{CapsuleInjector GUI}
\label{fig:capsuleinject}
\end{center}
\end{figure}

A tool is included in the TinyOS release to aid in the writing of

\bomb programs: {\tt net.tinyos.vm\_asm.CapsuleInjector}. {\tt

CapsuleInjector} provides an interface for writing assembly programs
and sending them to a mote connected to a PC; if the capsule is marked
self-forwarding, it will then start propagating into the network.

One must set the destination mote ID of the capsule packet (important
when using a GenericBase) and the version number of the
capsule. Version numbers are explained in Section \ref{sec:viral};
\bomb only installs a capsule if its version number is higher than
the one it currently has.


If the program has an error (e.g. an unknown instruction), {\tt
CapsuleInjector} does not send out a packet.


\subsection{Synchronization}

\bomb interleaves the execution of its contexts at instruction
granularity. The presence of a 16-word shared heap means that if
different contexts communicate or share variables (e.g. an aggregated
sensor reading), race conditions can easily occur. As the program
running on a mote is the combination of possibly forwarding capsules,
applications can go through transient states of partial installation,
making programmer efforts (e.g. a spin loop) ineffectual.

\bomb therefore uses an implicit locking scheme, so that
programmers are assured that there will be no race conditions in their
programs. Experienced programmers can relax the locking requirements
to improve parallelism.

\subsubsection{Model}

The \bomb sychronization model is based on five abstractions:
\emph{handlers, invocations, resources, scheduling points} and
\emph{sequences}. We describe how we discover the resources used by an
invocation, and how invocation communicate their resource requirements
to the runtime system.

A \emph{handler} is a function that is executed in response to some
event. An \emph{invocation} represents a particular execution of a
handler in response to an event. At any time, invocations are in one
of four states: \emph{waiting} (for resources), \emph{suspended}
(waiting for an operation to complete), \emph{ready} (can execute),
\emph{running} (executing). We say that an invocation that is ready or
running is \emph{active}.

A \emph{resource} is a shared piece of state that a handler requires
access to -- examples are a variable, a disk arm, or a sensor.
Resources can only be held by invocations.

A handler contains a number of \emph{scheduling points} at which it can be
suspended and gain or lose resources (and resources cannot be acquired
anywhere but at scheduling points). Scheduling points are the handler's
entry and exit points, and some subset of its operations which we call
\emph{scheduled operations}. An invocation goes through two states during
execution of a scheduled operation: first, the invocation is suspended
awaiting the completion of the operation; second, the invocation is
waiting for the resources it wishes to gain to become
available. Either of these two phases may be trivial: a {\tt yield}
operation completes immediately but may wait for some resources, a
message send does not complete immediately but, if it is not waiting
for any resources, will not wait. A \emph{sequence} is any code path
between two scheduling points which does not include another
scheduling point.

The model for resource acquisition and release is as follows: before
an invocation can start execution, it must acquire all resources it
will need during its lifetime. At each subsequent scheduling point,
the invocation can release a set $R$ of resources before suspending
execution, and acquire a set $A$ of resources before resuming. To
prevent deadlock, we require $A
\subseteq R$ (we prove below that this condition is sufficient for building
deadlock-free schedulers). Finally, when an invocation exits it must
release all held resources. Note that we do not guarantee any atomicity
between two invocations of the same handler.

To preserve safety, the static analysis of a handler's resource usage
and the runtime system must guarantee that an invocation holds all
resources at the time(s) at which they are accessed and that the
intersection of the resources held by any two invocations is empty. We
restrict our invocation model to considering a static number of
resources, and require operations to explicitly name the resources
they use so that we can easily analyse handlers at compile (or load)
time. Resource discovery must be conservative to preserve correctness.


\subsubsection{\bomb Implementation}


We implemented this syncronization model in \bomb. Each
\bomb context is an invocation, and capsules are implicitly
broken up into sequences. \bomb maintains two queues of
invocations: ready and waiting. Whenever \bomb installs a new
capsule, it performs a static full-program analysis to generate the
acquire sets of its invocation start points. Without requiring any
annotation from a programmer, \bomb runs invocations atomically
while allowing parallelism. Programmers can improve the degree of
parallelism by yielding resources at scheduling points.

\bomb invocations are broken into sequences by scheduling point
instructions. When a context executes one of these instructions, the
\bomb runtime examines the current release set of the issuing
context and releases the locks on the indicated resources. \bomb
then checks the waiting queue to see if any contexts have been made
runnable by the release of these locks. When the scheduling point
instruction completes, \bomb checks the acquire set of the
context to see if it can be made active; if so, the context acquires
its locks and \bomb places it on the ready queue. If the context
cannot be made active, \bomb places it on the waiting queue.

\begin{figure}
\centering
\tiny
\begin{tabular}{|l|l|}\hline
\verb;pushc 3  #                   ;&\verb; pushc 3 ;\\
\verb;unlock   # Add lock 3 to R,A ;&\verb; unlockb   # Add locks 0,1 to R,A;\\
\verb;pushc 2  #                   ;&\verb; pushc 12 ;\\
\verb;punlock  # Add lock 2 to R   ;&\verb; punlockb  # Add locks 2,3 to R;\\
\verb;sense    # Yield             ;&\verb; sense     # Yield;\\ \hline

\end{tabular}

\caption{Sample \bomb Unlocking}

\label{fig:locks}

\end{figure}

\bomb defines its scheduling point instructions to be those that
trigger split-phase operations in TinyOS. This includes acquiring
sensor data ({\tt sense}), sending packets ({\tt send, sendr, uart}),
and accessing non-volatile flash memory storage ({\tt logr, logw,
logwl}). Additionally, there is a {\tt yield} instruction, which is
effectively a split-phase operation that immediately completes. Locks
are added to a context's release set with the {\tt unlock} instruction
-- by default, the set is empty. {\tt unlock} also adds the lock to
the context's acquire set. For a lock to be released, but not
re-acquired, a context much use the {\tt punlock} (unlock permanent)
instruction. The {\tt unlock} and {\tt punlock} instructions affect
individual locks, enumerated by an operand; the {\tt unlockb} and {\tt
punlockb} instructions use the operand as a bitmask for locks to be
released. Locks are not released until a scheduling-point instruction
is executed. Figure \ref{fig:locks} contains two sample \bomb
instruction sequences that demonstrate resource unlocking.

Release and acquire sets are atomically handled by \bomb. A
context does not acquire any locks in its acquire set unless it can
acquire all of them, and acquires them atomically. Similarly, release
sets are released atomically. This, combined with monotonically
decreasing lock sets, ensures the system is deadlock free.

\subsection{Viral Programming}
\label{sec:viral}


\bomb code capsules can be marked ``forwarding.'' Capsules marked
forwarding are automatically forwarded by the viral propagation
subsystem (BVirus) of the VM.


The first implementation of the VM had an explicit caspule forwarding
system (the {\tt forw} instruction); experimental results showed this
to be a terrible idea, as programs could very easily saturate the
network unknowingly. We therefore adopted this simple probabilistic
model. It is by no means perfect; for example, even if every mote in
the network is running the same capsule, they will continue to forward
it indefinitely.

Every capsule has a version number. When \bomb hears a capsule
broadcast, it checks if the capsule is newer than the one currently
installed; if so, \bomb halts execution of that context and
installs the new capsule.

Our first implementation of the VM had an explicit caspule forwarding
system (the {\tt forw} instruction); experimental results showed this
to be a terrible idea, as programs could very easily saturate the
network unknowingly. We therefore adopted this simple probabilistic
model. It is by no means perfect; for example, even if every mote in
the network is running the same capsule, they will continue to forward
it indefinitely.

Currently, \bomb uses a density-adjusting algorithm; every mote
maintains a time interval of length $\tau$, and picks a random
point $t$ in $tau$ in which to transmit a summary of capsule
versions. If the mote hears an identical version summary before
$t$, it suppresses its transmission. This mechanism controls the
number of version summaries sent within a cell during any time period
$tau$, keeping it to a small constant. The algorithm also scales
$tau$ to achieve low overhead when the network is stable and high
reprogramming rates when there is new code. When a node hears a
version summary with older capsules than it has, it broadcasts the
needed capsules.

\subsection{Error State}


\bomb has an error state, which can help users debug their
programs. If a program triggers an error (for example, by trying to
add incompatible sensor readings, or by overflowing the operand
stack), \bomb halts execution on all contexts. Then, every second, it
blinks all of the LEDs and sends a packet containing debugging
information over the UART. The packet contains the offending context
identifier, the capsule it was executing, the instruction that caused
the error, and the error code. Error codes can be found in
{\tt \bomb.h}. They are:


\begin{verbatim}
typedef enum {
  BOMB_ERROR_TRIGGERED                =  0,
  BOMB_ERROR_INVALID_RUNNABLE         =  1,
  BOMB_ERROR_STACK_OVERFLOW           =  2,
  BOMB_ERROR_STACK_UNDERFLOW          =  3, 
  BOMB_ERROR_BUFFER_OVERFLOW          =  4,
  BOMB_ERROR_BUFFER_UNDERFLOW         =  5,
  BOMB_ERROR_INDEX_OUT_OF_BOUNDS      =  6,
  BOMB_ERROR_INSTRUCTION_RUNOFF       =  7,
  BOMB_ERROR_LOCK_INVALID             =  8,
  BOMB_ERROR_LOCK_STEAL               =  9,
  BOMB_ERROR_UNLOCK_INVALID           = 10,
  BOMB_ERROR_QUEUE_ENQUEUE            = 11,
  BOMB_ERROR_QUEUE_DEQUEUE            = 12,
  BOMB_ERROR_QUEUE_REMOVE             = 13,
  BOMB_ERROR_QUEUE_INVALID            = 14,
  BOMB_ERROR_RSTACK_OVERFLOW          = 15,
  BOMB_ERROR_RSTACK_UNDERFLOW         = 16, 
  BOMB_ERROR_INVALID_ACCESS           = 17,
  BOMB_ERROR_TYPE_CHECK               = 18,
  BOMB_ERROR_INVALID_TYPE             = 19,
  BOMB_ERROR_INVALID_LOCK             = 20,
  BOMB_ERROR_INVALID_INSTRUCTION      = 21
} BombillaErrorCode;
\end{verbatim}


The \bomb error packet has the following payload:


\begin{verbatim}
typedef struct BombillaErrorMsg {
  uint8_t context;
  uint8_t reason;
  uint8_t capsule;
  uint8_t instruction;
} BombillaErrorMsg;
\end{verbatim}

\section{\mate}

\bomb is an instance of the \mate virtual machine. \mate's architecture
has many similarities to TinyOS; the core of the VM is a simple
component that schedules contexts to execute. nesC wiring allows
developers to easily customize and change the VM contexts,
instructions, and subsystems.

\subsection{Component Architecture}

The core \mate component, {\tt BombillaEngine}, receives requests from
contexts to be scheduled and executes them at a granularity of up to a
single \mate instruction. The contexts themselves, the instruction
set, and the VM services are all separate from the VM scheduler.

A TinyOS component provides every \mate instruction. While most
instruction components implement only one instruction, some implement
several related instructions. For example, the shared memory access
instructions, {\tt getvar} and {\tt setvar}, are both provided by a
single component; it's unlikely that only one of the two would ever be
needed. Instruction components provide the {\tt BombillaBytecode}
interface, and {\tt BombillaEngine} uses that interface with an 8-bit
parameter: each instruction is a single byte. The set of instruction
components wired to {\tt BombillaEngine} specifies the instruction
set.

To be specific, this is the interface signature of {\tt BombillaEngine}:

\begin{verbatim}
configuration BombillaEngine {
  provides {
    interface StdControl;
    command result_t computeInstruction(BombillaContext* context);
    command result_t executeContext(BombillaContext* context);
    
    interface BombillaContextComm;
  }
  uses interface BombillaBytecode as Bytecode[uint8_t bytecode];
}
\end{verbatim}

and this is a snippet of \bomb's configuration:

\begin{verbatim}
configuration AbstractMate {}
implementation {
  components BombillaEngine as VM;
  components OPhalt, OPputled, OPcopy, OPadd, OPland, OPlor, OPlnot;

  ...

  VM.Bytecode[OPhalt] -> OPhalt;
  VM.Bytecode[OPputled] -> OPputled;
  VM.Bytecode[OPadd] -> OPadd;
  VM.Bytecode[OPcopy] -> OPcopy;
  VM.Bytecode[OPland] -> OPland;
  VM.Bytecode[OPlor] -> OPlor;
  VM.Bytecode[OPlnot] -> OPlnot;

  ...
}
\end{verbatim}

The bytecode wirings use the name of a bytecode twice, as a component
and as a constant from an enum. For example, {\tt VM.Bytecode[OPadd]}
$->$ {\tt OPadd;} means ``wire the OPadd {\bf component} to the
instance of Bytecode specified by the enum {\bf constant} OPadd.'' The
constant is specified in {\tt Bombilla.h}.

{\Large something similar is done for contexts}

By encapsulating instructions into components, TinyOS allocates
storage only for used systems. For example, the {\tt sense}
instruction keeps some state on the sensor being sampled and maintains
a wait queue of contexts. Similarly, subroutine capsules are part of
the {\tt call} instruction; if a VM can't call the subroutines,
there's no need to waste RAM on them.

\subsection{Service Proxies}

Instructions often need to use several VM subsystems; for example,
almost every instruction manipulates the operand stack, requiring a
component that provides the {\tt BombillaStacks} interface. This
raises the issue of where these wirings are made. On one hand, wiring
at the top-level configuration is laborious: up to 256 instructions,
with 2-3 used interfaces each, leads to a very large file. On the
other, wiring at the instruction component level makes consistency
difficult: it's possible that two instructions wire in two different
implementations of a VM service.

To solve this problem, every instruction is a configuration, but
instead of wiring used interfaces to a specific component, they're
wired to proxy configurations, such as {\tt BStacksProxy}. Every
instruction has a module, e.g. {\tt OPhaltM}, and a configuration,
e.g. {\tt OPhalt}. The configuration wires all of the module's used
interfaces to these proxies. For example, every instruction modules
that uses the {\tt BombillaStacks} interface has a configuration that
has something like:

\begin{verbatim}
  Instr.BombillaStacks -> BStacksProxy;
\end{verbatim}

These proxy configurations are simple ``pass-through''
configurations. For example:

\begin{verbatim}
configuration BStacksProxy {
  provides {