bombilla.tex

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

\documentclass[10pt]{article}

\usepackage{graphicx}
\usepackage{graphics}
\usepackage{multicol}
\usepackage{epsfig,amsmath,amsfonts}
\usepackage{xspace}

\makeatletter                                   % Make '@' accessible. 
\oddsidemargin=0in                              % Left margin minus 1 inch.
\evensidemargin=0in                             % Same for even-numbered pages.
\marginparsep=0pt                               % Space between margin & text

\renewcommand{\baselinestretch}{1}              % Double spacing

\textwidth=6.5in                                % Text width (8.5in - margins).
\textheight=9in                                 % Body height (incl. footnotes)

\topmargin=0in                                  % Top margin minus 1 inch.
\headsep=0.0in                                  % Distance from header to body.
\skip\footins=4ex                               % Space above first footnote.
\hbadness=10000                                 % No "underfull hbox" messages.
\makeatother                                    % Make '@' special again.

\newcommand{\mate}{Mat\'{e}\xspace}
\newcommand{\bomb}{Bombilla\xspace}

\title{Mat\'{e}: A Tiny Virtual Machine for TinyOS}
\author{Philip Levis and Neil Patel\\[e-mail]}
\date{}

\begin{document}

%\fontfamily{cmss}                               % Make text sans serif.
%\fontseries{m}                                  % Medium spacing.
%\fontshape{n}                                   % Normal: not bold, etc.
%\fontsize{10}{10}                               % 10pt font, 10pt line spacing 

\maketitle
\vspace{2in}
\begin{center}
Version 1.1\\
August 21, 2003
\end{center}

\fontfamily{cmr}                                % Make text Roman (serif).
\fontseries{m}                                  % Medium spacing.
\fontshape{n}                                   % Normal: not bold, etc.
\fontsize{10}{10}                               % 10pt font, 10pt line spacing


\thispagestyle{empty}
\newpage
\tableofcontents
\newpage

\section{Introduction}

\mate is a tiny bytecode interpreter that runs on top of
TinyOS. Because it presents a high-level communication-centric
interface, \mate's programs are very short; combined with a safe
execution environment, this makes mote reprogramming rapid and
error-free. Programs can self-propagate through a network; this makes
reprogramming mostly autonomous, as once a self-propagating capsule is
introduced, it will eventually install itself over the entire network.


\mate has multiple execution contexts; each runs in response to an
event, and they can interleave at instruction granularity. \mate
prevents race conditions by implicitly locking all shared state that
is used; as every resource is statically named and \mate programs
are short, the set of required locks can be quickly determined with a
full program analysis. Program writers can explicitly yield or release
locks to improve parallelism.


One goal of \mate is to provide a programming interface to motes
that is much simpler than TinyOS; a sense-and-send program can be as
few as six instructions in \mate, and \mate's error detection
mechanisms can help novice programmers find the bugs in their
programs.

\mate is a architecture for constructing application specific virtual
machines. Using the architecture, developers can easily change
instruction sets, execution events, and VM subsystems. The first half
of this document presents \bomb, a specific instance of a \mate VM
that is part of the standard TinyOS distribution, explaining it as a
complete system. The second half explains the \mate architecture,
shows how \bomb is an instance of \mate, and gives examples on how
\bomb can be used as a template to build other virtual machines.


\section{\bomb}

\bomb is a set of TinyOS components that sit on top of several
system components, including sensors, the network stack, and
non-volatile storage (the ``logger'')\footnote{Support for the logger
is currently not implemented, due to the pending addition of a new
logger interface in TinyOS.}. Code is broken in {\bf capsules} of 24
instructions, each of which is a single byte long; larger programs can
be composed of multiple capsules. In addition to bytecodes, capsules
contain identifying and version information. Each \bomb context has
two stacks: an operand stack and a return address stack. Most
instructions operate solely on the operand stack, but a few
instructions control program flow and several have embedded
operands. There are three execution contexts that can run concurrently
at instruction granularity. \bomb provides both a built-in ad-hoc
routing algorithm (the {\tt send} instruction) as well as mechanisms
for writing new ones (the {\tt sendr} instruction).


\begin{figure}
\centering
\includegraphics[scale=0.4]{fig/bombillamodel.jpg}

\caption{\bomb Architecture and Execution Model: Capsules, Contexts, and Stacks}

\label{fig:exec}
\end{figure}


\begin{figure}
\begin{center}
\def\W{3.25in}

\begin{tabular}{|l|l|l|}\hline
basic   &{\tt 00iiiiii} & {\tt i} = instruction\\ \hline
m-class &{\tt 010iixxx} & {\tt i} = instruction, {\tt x} = argument \\ \hline
v-class &{\tt 011ixxxx} & {\tt i} = instruction, {\tt x} = argument \\ \hline
j-class &{\tt 10ixxxxx} & {\tt i} = instruction, {\tt x} = argument \\ \hline
x-class &{\tt 11xxxxxx} & {\tt i} = instruction, {\tt x} = argument\\ \hline
\end{tabular}


\caption{\bomb Instruction Formats}

\label{fig:instr}
\end{center}
\end{figure}

\subsection{Architecture, Instruction Set, and Data Types}


\bomb instructions hide the asynchrony (and oft-resulting race
conditions) of TinyOS programming. For example, when the {\tt send}
instruction is issued, \bomb calls a command in the ad-hoc routing
component to send a packet. \bomb suspends the context until a
message send complete event is received, at which point it resumes
execution. By doing this, \bomb does not need to manage message
buffers -- the capsule will not resume until the network component is
done with the buffer. Similarly, when the {\tt sense} instruction is
issued, \bomb requests data from the sensor TinyOS component and
suspends the context until the component returns data with an
event. This synchronous model makes application level programming much
simpler and far less prone to bugs than dealing with asynchronous
event notifications. Additionally, \bomb efficiently uses the
resources provided by TinyOS; during a split-phase operation, \bomb
does nothing on behalf of the calling context, allowing TinyOS to put
the CPU to sleep or use it freely.


\bomb is a stack-based architecture. This allows a concise
instruction set; most instructions do not have to specify operands, as
they exist on the operand stack. There are five classes of \bomb
instructions: basic, m-class, j-class, v-class, and x-class. Figure
\ref{fig:instr} shows the instruction formats for each class. Basic
instructions include such operations as arithmetic, halting, and
activating the LEDs on a mote. m-class instructions access message
headers; they can only be executed within the message send and receive
contexts. v-class instructions access the 16 word \bomb
heap. j-class instructions are the two jump instructions, for loops
and conditionals. The one x-class instructions is {\tt pushc} (push
constant). All instruction classes except basic have embedded operands..


\bomb's three principal execution contexts, illustrated in Figure

\ref{fig:exec}, correspond to three events: clock timers, message
receptions and message send requests.  Inheriting from languages such
as FORTH, each context has two stacks, an operand stack and a return
address stack. The former is used for all instructions handling data,
while the latter is used for subroutine calls. The operand stack has a
maximum depth of 16 while the call stack has a maximum depth of 8. We
have found this more than adequate for programs we have written.

There is an additional context, the ``once'' context. Unlike other
contexts, which run their capsules many times, this context only runs
its capsule once, when it is installed; this allows a user to
initialize state, adjust constants, or perform other operations that
only need a single execution.

There are three operands types: values, sensor readings, and
buffers. Some instructions can only operate on certain types. For
example, the {\tt putled} instruction expects a value on the top of
the operand stack. However, many instructions are polymorphic. For
example, the {\tt add} instruction can be used to add any combination
of the types, with different results. Adding buffers results in
appending the data in the second operand onto the first
operand. Adding a value to a message appends the value to the message
data payload. Sensor readings can be turned into values with the {\tt
cast} instruction.

Sensor readings are typed, and cannot be modified. For example, in
order to take an average over a set of readings, each reading must be
first be converted to a value; these values can then be averaged. Many
instructions (e.g. {\tt inv}) automatically cast sensor readings to
values. This ensures that a sensor reading variable has some meaning;
otherwise, it could express some arbitrary quantity. Adding two sensor
readings of the same type (e.g. magnetometer X-axis) produces a value,
and adding two sensor readings of different values is an error.

Buffers are also typed, and can hold up to ten values. A buffer can
only hold elements of one type, whether they be values or a certain
sensor type. An empty buffer has no type; the first element added will
set the type of the buffer. Buffers have several access instructions,
including {\tt bhead} (copy of the first element of the buffer onto
the operand stack), {\tt byank} (pull the nth element out of the
buffer and push it into the operand stack), and {\tt bsorta} (sort the
elements in ascending order.

There is a 16 word heap shared among the context. It can be accessed
with the {\tt setvar} and {\tt getvar} instructions, which have a
4-bit embedded operand.. This allows the separate contexts to
communicate shared state (e.g. sensor readings).

\subsection{Capsules and Execution}


\bomb programs are broken up into capsules of up to 24
instructions. This limit allows a capsule to fit into a single TinyOS
packet. By making capsule reception atomic, \bomb does not need to
buffer partial capsules, which conserves RAM. Every code capsule
includes type and version information. \bomb defines two types of code
capsules: context capsules, which are the root execution of a context,
and subroutine capsules, which can be called from context capsules or
other subroutine capsule. Subroutine capsules allow programs to be
more complex than what fits in a single capsule. Applications invoke
and return from subroutines using the {\tt call} and {\tt return}
instructions. There are names for up to $2^{15}$ subroutines; to keep
\bomb's RAM requirements small, its current implementation has only
four.



\bomb begins execution in response to an event -- a timer going

off, a packet being received, or a packet being sent. Each of these
events has a capsule and an execution context. Control jumps to the
first instruction of the capsule and executes until it reaches the
{\tt halt} instruction. These three contexts can run
concurrently. Each instruction is executed as a TinyOS task, which
allows execution interleaving at an instruction
granularity. Additionally, underlying TinyOS components can operate
concurrently with \bomb instruction processing. When a subroutine is
called, the return address (capsule, instruction number) is pushed
onto a return address stack and control jumps to the first instruction
of the subroutine. When a subroutine returns, it pops an address off
the return stack and jumps to the appropriate instruction.

\begin{figure}
\begin{center}
\scriptsize
\begin{tabular}{l}
\verb;getvar 0    # Get heap variable 0;\\
\verb;pushc 1     # Push one onto operand stack;\\
\verb;add         # Add the one to the stored counter;\\     
\verb;copy        # Copy the new counter value;\\
\verb;setvar 0    # Set heap variable 0;\\
\verb;pushc 7 ;\\     
\verb;and         # Take bottom three bits of counter;\\
\verb;putled      # Set the LEDs to these three bits;\\
\verb;halt;\\
\end{tabular}
\normalsize


\caption{\bomb {\tt cnt\_to\_leds} -- Shows the bottom 3 bits of a counter on mote LEDs}

\label{fig:cnt}
\end{center}
\end{figure}


\begin{figure}
\begin{center}
\scriptsize
\begin{tabular}{l}
\verb;pushc 1     # Push one on the operand stack;\\
\verb;sense       # Read sensor 1 (light);\\
\verb;copy        # Copy the sensor reading;\\
\verb;getvar 0    # Get previous sent reading;\\
\verb;;\\
\verb;inv         # Invert previous reading ;\\
\verb;add         # Current - previous sent value;\\
\verb;copy        # 2 copies of difference on top of stack;\\
\verb;pushc 32    #;\\
\verb;;\\
\verb;gt          # Is current 32 greater than previous?;\\
\verb;swap        # Swap result with copy ;\\
\verb;pushc 32    #;\\
\verb;inv         #;\\
\verb;;\\
\verb;lt          # Is current 32 less than previous?;\\
\verb;or          # Either  32> or 32<;\\
\verb;jumps 15    # Jump to send;\\
\verb;halt;\\
\verb;;\\
\verb;copy        # Copy new value;\\
\verb;setvar 0    # Set current;\\
\verb;bpush0      # Push buffer 0 onto stack;\\
\verb;bclear      # Clear its contents;\\
\verb;;\\
\verb;add         # Add current reading to buffer;\\
\verb;send        # Send buffer;\\
\verb;halt;\\

\end{tabular}
\normalsize

\caption{\bomb Program to Read Light Data and Send a Packet on Reading Change}

\label{fig:sense}
\end{center}
\end{figure}

The packet receive and clock capsules execute in response to external
events; in contrast, the packet send capsule executes in response to
the {\tt sendr} instruction. As {\tt sendr} will probably execute a
number of \bomb instructions in addition to sending a packet, it can
be a lengthy operation. Therefore, when {\tt sendr} is issued, \bomb
copies the message buffer onto the send context operand stack and
schedules the send context to run. Once the message has been copied,
the calling context can resume execution. The send context executes
concurrently to the calling context, preparing a packet and later
sending it. This frees up the calling context to handle subsequent
events -- in the case of the receive context, this is very important.


The constrained addressing modes of \bomb instructions ensure a
context cannot access the state of a separate context. Every push and
pop on the operand and return value stack has bound checks to prevent
overrun and underrun. As there is only a single shared variable, heap
addressing is not a problem. Unrecognized instructions result in
simple no-ops. All bounds are always checked -- the only way two
contexts can share state is through {\tt gets} and {\tt
sets}. Nefarious capsules can at worst clog a network with packets --
even in this case, a newer capsule will inevitably be heard. By
providing such a constrained execution environment and providing
high-level abstractions to services such as the network layer, \bomb
ensures that it is resilient to buggy or malicious capsules.

\subsection{Simple Programs}
\label{sec:sub:simple}


The \bomb program in Figure \ref{fig:cnt} maintains a counter that
increments on each clock tick. The bottom three bits of the counter
are displayed on the three mote LEDs. The counter is kept as a value
which persists at the top of the stack across invocations. This
program could alternatively been implemented by using {\tt gets} and
{\tt sets} to modify the shared variable.  This code recreates one of
the simplest TinyOS applications, {\tt cnt\_to\_leds}, implemented in
seven bytes.


The \bomb program in Figure \ref{fig:sense} reads the light sensor
on every clock tick. If the sensor value differs from the last sent
value by more than a given amount (32 in this example), the program
sends the data using \bomb's built-in ad-hoc routing system. This
program is 24 bytes long, fitting in a single capsule.