\documentclass[12pt]{article}\usepackage{graphicx}\usepackage{graphics}\usepackage{multicol}\usepackage{epsfig,amsmath,amsfonts}\usepackage{xspace}\usepackage{subfigure}\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.2}              % 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} Manual}\author{Philip Levis\\pal@cs.berkeley.edu}\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 2.19a\\November 30, 2004\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 framework for building accessible programminginterfaces to TinyOS sensor networks. The core of \mate is a bytecodeinterpreter template. A user can customize the interpeter'sinstruction set and execution events to match the abstractions neededby a particular deployment, and programs a network with high-levelscripts. Given the right set of abstractions, a user script canexpress complex behavior concisely and simply. Conciseness allowsprograms to compile to a small number of instructions, so codepropagation can be rapid and inexpensive. Simplicity makes bugs lesslikely.Once introduced, \mate programs self-propagate through a network usingan epidemic broadcast protocol. Reprogramming only requiresintroducing a single copy of a new program: this copy will theninstall itself across the entire network.This document describes the \mate architecture and how to use it. Itoutlines the major TinyOS components that comprise a \mate template,the interfaces they use to interact, describes the algorithms \mateuses for services such as code propagation and synchronization, andcovers how the VMBuilder tool builds a virtual machine from userspecifications. It assumes you have already read the \mate tutorials,and provides details beyond them, such as how to implement a newlanguage.\section{\mate Interfaces}The nesC components that comprise \mate have a wide range ofinterfaces. This section contains a brief description of eachinterface. Detailed information on the individual commands and eventscan be found in the standard nesdoc documentation.\subsection{MateAnalysis}MateAnalysis is for invoking resource utilization analysis. When new ahandler arrives, the \mate's viral propagation subsystem callsMateAnalysis to compute what shared resources the code uses. \mateuses this information to determine which handlers can safely runconcurrently, and which cannot.\subsection{MateBuffer}MateBuffer is for accessing buffer data structres as an abstract datatype. MateBuffer has commands for inserting, removing, sorting, andtypechecking.\subsection{MateBytecodeLock}MateBytecodeLock is how \mate's code analysis determines what sharedresource an instruction uses, so it can determine what handlers cansafely run concurrently. If an instruction encapsulates a sharedresource, then it must implement this interface.\subsection{MateBytecode}MateBytecode is the bytecode execution interface. When the interpreterexecutes a bytecode, it executes an instance of this interface. Theinterface also has a command that returns the byte width of theinstruction, so the scheduler knows how much to increment a context'sprogram counter by.\subsection{MateContextLocks}MateContextLocks has commands for acquiring and releasing locks on acontext basis, and determinig whether a context can acquire all of thelocks it needs. These commands are rarely called by externalcomponents; they are used by implementations of MateContextSynch tohalt and resume contexts.\subsection{MateContextStatus}MateContextStatus has a single event, which fires when a contexthalts. Among other things, this allows a context that has queuedexecution requests to know when it can handle the next one.\subsection{MateContextSynch}MateContextSynch is how components interact with the \mate concurrencymanager. Components can submit contexts to the \mate concurrencymanager for execution. The concurrency manager decides which contextscan safely run concurrently and forwards them to thescheduler. MateContextSynch has commands for resuming, halting, andyielding contexts.\subsection{MateEngineControl}MateEngineControl has events for signalling the VM to reboot, halt, orresume. Telling the VM to reboot will make it signal its own rebootevent to interested components through the MateEngineStatus interface.\subsection{MateEngineStatus}MateEngineStatus is how the VM engine notifies interested componentswhen it reboots. For example, when the VM reboots, context componentsreset their contexts and split-phase instructions clear their queues.\subsection{MateError}MateError is for indicating an error has occured, that should haltexecution. When invoked, this causes the VM to enter an error state,blinking the LEDs and broadcasting the cause of the error.\subsection{MateHandlerStore}MateHandlerStore is how components interact with the underlying codestore and propagation subsystem. It presents code handlers as anabstract data type, with accessor commands and an event for notifyingwhen code has changed.\subsection{MateLocks}MateLocks presents shared resources locks as an abstract datatype. The \mate concurrency manager uses MateLocks to manageutilization of shared resources.\subsection{MateQueue}MateQueue is for manipulating context queues as an abstract datatype. It supports enqueueing, dequeueing, removal, andinitialization. Several \mate components use context queues, includingthe scheduler, concurrency manager, and blocking operations.\subsection{MateScheduler}MateScheduler is the interface the core VM interpreter provides forsubmitting contexts to the run queue. The \mate concurrency manageruses this interface to submit contexts it has determined to be safe torun.\subsection{MateStacks}MateStacks presents the operand stack of a \mate execution context asan abstract data type. It has commands for initializing a stack,pushing various types of operands, and popping operands.\subsection{MateTypes}MateTypes provides commands for operand typechecking. Generally, acommand has two forms, query and check. Queries merely return whetheran operand passes a type requirement; checks return whether theoperand passes, and automatically trigger an error condition if thecheck fails.\subsection{MateVirus}MateVirus is the interface to \mate's viral code propagationsubsystem. Generally, a component that provides MateHandlerStore sitson top of a component that provides MateVirus. MateHandlerStoresignals arrival in terms of units of execution, while MateVirussignals arrivals in terms of code propagation (a single propagationunit, for example, may contain two handlers).\subsection{MateType}Language-independent functions cannot make assumptions about alanguage's data model. When data is internal to a mote, thisis not a problem: a VM controls access to data structures, sotheir internal representation is separated from a program. WhenVMs communicate (over the radio, for example), however, they mustagree on a data format, which can be different than the in-memoryrepresentation a VM uses. For example, a VM may represent a listas a linked list in memory, but needs to compact it to a vector totransmit it. The MateType interface is for packing and unpackingnetwork data type representations, so functions can handle data typeswithout knowing their internal structure.\section{\mate Template}A \mate VM's components fall into two classes: the components every VMincludes (the basic template), and the components that define theparticular \mate instance. The basic VM template includes scheduling,concurrency managment, and code storage/propagation. Adding aninstruction set and execution contexts to the template makes aapplication-specific virtual machine. This section describes the threemajor template components, {\tt MateEngine}, {\tt MContextSynchProxy},and {\tt MHandlerStoreProxy}.Many \mate subsystems have ``Proxy'' components. These proxycomponents separate the interface of the subsystem from itsimplementation. If every \mate component wires to the proxy, insteadof the component itself, then a user can change what implementationthe VM uses by only changing the proxy component. For example, tochange the {\tt MateLocks} implementation from {\tt MLocks} to {\ttMLockSafe} (the latter performs many checks the former does not), auser only has to change the {\tt MLocksProxy} component to refer to{\tt MLocksSafe}. In contrast, if a proxy were not used, then everyfile which wires to {\tt MLocks} would have to be changed to {\ttMLocksProxy}.\subsection{Scheduling: {\tt MateEngine}}{\tt MateEngine} is a configuration that wires {\tt MateEngineM}, thecore \mate scheduler, to all of its needed subsystems. It has thefollowing signature:\newpage\begin{figure}\centering\includegraphics[width=6in]{fig/MateEngine.jpg}\caption{{\tt MateEngine} wiring diagram.}\label{fig:mate-engine}\end{figure}{\scriptsize\begin{verbatim}configuration MateEngine {  provides {    interface StdControl;        interface MateError as Error;    interface MateEngineStatus as EngineStatus;    interface MateScheduler as Scheduler;    interface MateBytecode as Functions[uint8_t functionID];  }  uses {    interface MateEngineControl as EngineControl;    interface MateBytecode as Bytecode[uint8_t bytecode];    interface MateBytecode as FunctionImpls[uint8_t fnID];    interface StdControl as SubControl;  }}\end{verbatim}}Figure~\ref{fig:mate-engine} shows how {\tt MateEngine} wires {\ttMateEngineM}. {\tt TimerC}, {\tt LedsC}, and {\tt QueuedSend} are allfor when an error condition occurs (triggered by {\tt MateError}):{\tt MateEngine} starts a periodic timer, blinking the LEDs andbroadcasting the source of the error. {\tt MQueueProxy} is formanipulating the run queue and {\tt MHandlerStoreProxy} is forfetching opcodes from handlers.The set of components that are wired to {\tt MateEngine}'sparameterized {\tt Bytecode} implement a VM's instruction set. Themain execution loop fetches the next bytecode from a handler (throughthe HandlerStore), then dispatches on this interface based on theopcode value. For example, if the bytecode {\tt halt} has value {\tt0x2a}, then the {\tt OPhalt} component is wired to {\ttMateEngine.Bytecode[0x2a]}. Generally, functions included in a VM(such as {\tt send}) exist as bytecodes.The {\tt Functions} and {\tt FunctionImpls} are a bit morecomplex. First order language (such as motlle) need to be able torefer to functions by values, which can be stored and passed. Thelanguage then needs a way to take this value and execute the functionit refers to. If a VM supports a first-class language, then all of thefunctions must be wired to {\tt FunctionImpls}: the parameters forthis interface are distinct from those for the {\tt Bytecode}interface. {\tt Functions} is a simple pass-through to {\ttFunctionImpls}. An instruction component can wire to {\ttFunctionImpls} to dispatch to a function based on a value.Any stand-alone component that has to provide {\tt StdControl} shouldwire it to {\tt MateEngine}'s {\tt SubControl}. This will allow the VMto support power management in the future.{\tt MateEngineM} follows a round-robin FIFO policy. {\tt MateEngineM}has two configuration constants for timeslicing, {\ttMATE\_CPU\_QUANTUM} and {\tt MATE\_CPU\_SLICE}. {\tt MateEngineM}executes instructions in a task. {\tt QUANTUM} is the maximum numberof instructions it interprets in each task execution; {\tt SLICE} isthe number of quanta it gives to a context before switching to a newone. By default, {\tt MATE\_CPU\_SLICE} is 5 and {\ttMATE\_CPU\_QUANTUM} is 4. Unless a context halts or blocks, {\ttMateEngine} timeslices them at the granularity of 20 instructions.\subsection{Data Model: {\tt MStacks} and {\tt MTypeManager}}\mate VMs follow a stack architecture. Each thread (execution context)has an operand stack.  For example, to perform arithmetic addition, aprogram pushes two numbers onto the stack, then executes the addinstruction. The add instruction pops the two elements off the stack,adds them and pushes the result onto the stack. The {\tt MStacks}component presents the operand stack as an abstract data type.Operands (and more generally, variables) have an associated type. Sometypes, such as integers, are simple. Variables can be more complextypes, such as vectors, lists, or strings. When \mate motescommunicate, they need to take the in-memory representation of a typeand transform it into something that can be sent over a network. Forexample, a linked list needs to be compacted into a linear sequence(i.e., array); the receiver can then unpack the serialized form intoits desired in-memory representation.{\tt MTypeManager} provides interfaces to the set ofnetwork-compatible types. Specifically, it provides a parameterizedinterface (the parameter is the type ID) of type {\tt MateType} (which