Introduction

Bombilla is a bytecode interpreter that runs on TinyOS. The conciseness of a high-level instruction set allows users to write programs and dynamically install them in a network much more quickly than possible with binary images. Additionally, Bombilla can automatically forward programs through a network; a new forwarding Bombilla program installed on a single mote will eventually run on every mote in the network.

Bombilla simplifies programming by providing a synchronous interface to TinyOS operations. For example, the send instruction blocks until the underlying sendDone event is handled by TinyOS. This makes code much less complex, especially for novice programmers. Currently, Bombilla programs are written in a high-level assembly language (e.g. sending a packet is a single instruction).

As Bombilla is a virtual machine, it also provides a form of execution protection. Unlike TinyOS applications, which has no user/kernel boundary, Bombilla programs cannot crash a mote or render it unresponsive. Bombilla catches errors at run time (e.g. accessing an invalid heap variable) and has a mechanism for alerting a user to them, including simple debugging information on the instruction that caused the error.

Bombilla has an event-based execution model; pieces of code are run in response to events, such as a timer or a packet reception. The presence of blocking operations requires that event handlers be able to run in parallel; the presence of shared variables could make race conditions a significant problem. Bombilla handles this issue by having handlers implicitly lock all shared resources they use; the set of shared resources used is computed with a full program analysis when code is installed. Therefore, a programmer can write several Bombilla event handlers that share variables and be sure there will be no race conditions without having to consider the necessary synchronization.

Installing Bombilla and Capsules

A Bombilla-enabled mote application exists in the TinyOS applications directory: Bombilla. Build and install this application on a mote. By default, Bombilla runs a simple program, similar to CntToLedsAndRfm, except that it sends the packet over the UART instead of the radio. Once the application installs, you should see the LEDs blink and a packet containing a counter being sent to your PCs serial port; the packet format is different from that used by IntToRfm.

Bombilla programs are broken into capsules of 24 instructions. There are two kinds of capsules: event handlers and subroutines. Event handler capsules are executed in response to an event; subroutines are called from other capsules. For example, there is a clock capsule, that runs in response to Bombilla's 1Hz timer.

Let's install a new clock capsule. Run net.tinyos.vm_asm.CapsuleInjector; a GUI like this should appear:

Select the capsule type to be "Clock." Set the mote ID to be ffff or the ID you installed on the mote. Bombilla only installs capsules that have a higher version number than the currently installed capsule; the default clock capsule is version 0, so set the capsule version to 1.

Next, we need to type in a program. Type this program into the Program Text window:

pushc 1
inv
getvar 0
add
copy
setvar 0
pushc 7
land
putled
halt	      

This program is a simpler and slightly different version of the default capsule. Instead of incrementing the counter, it decrements it, and it does not send the counter over the UART. Press the Inject button in the GUI; you should shortly see the LEDs blinking in a decrementing (instead of incrementing) fashion. If all 3 LEDs begin blinking in unison, then Bombilla has encountered a runtime error in your program; make sure that you typed it in correctly. If you need to install a new capsule, be sure to increment the Capsule Version field.

How This Capsule Works

Bombilla is a stack based architecture; instructions push and pop operands on a stack. This results in more condense code, as no embedded addresses are required; there are, however, instructions with embedded operands (such as pushc, push constant). Bombilla has a 16 variable heap, however, which is accessed with the getvar and setvar instructions, which have embedded operands.

In addition to capsules, Bombilla has contexts; contexts are the execution contexts (e.g. program counter, operand stack, etc.) that run capsules. Every context is associated with a capsule that it runs when triggered. For example, the clock context runs the clock capsule. There is not a 1-to-1 mapping between capsules and contexts, as subroutine capsules do not have associated contexts.

Let's look at the program you just installed and step through each instruction.

pushc 1: This instruction pushes a 1 onto the operand stack, which is empty when the capsule starts execution. The operand stack now has one variable, 1.

inv: This instruction inverts the value on top of the operand stack, making the 1 a -1. The operand stack now has one variable, -1.

getvar 0: This instruction fetches the counter from the 0th shared variable (they are numbered 0-15). The shared variables are initialized to all be 0 when Bombilla boots; as the default capsule was using this to store its counter, it has some small positive value (depending on how long you let the default capsule run). The operand stack now has two variables; the top of the stack is the counter, and below it is -1.

add: This instruction takes the top two variables on the operand stack and adds them, pushing the result onto the operand stack. In this case, it takes the counter and adds -1 to it, decrementing it. The operand stack now has one variable, the new decremented counter.

copy: This instruction copies the top of the operand stack. The operand stack now has two variables, both of which are separate copies of the decremented counter.

setvar 0: This instruction takes the top of the operand stack and stores it in shared variable 0, updating the stored value of the counter to the new decremented value. The operand stack now has one variable, a single copy of the decremented counter.

pushc 7: This instruction pushes the number 7 onto the operand stack. The operand stack now has two variables; the top of the stack is 7, and below it is the decremented counter.

land: This instruction pops two variables off the operand stack and computes their logical and. As 7 is 00000111 in binary, the result of this operation is the lowest three bits of the decremented counter; this is pushed onto the operand stack. The operand stack now has one variable, a value between 0 and 7 composed of the three least significant bits of the new counter value.

putled: This instruction sets the mote's LEDs. It pops the variable on top of the operand stack and uses it as an operand. putled takes a five bit operand. The lowest three bits specify which LEDs to operate on, and the fourth and fifth bits specify which LED operation. For us, these two bits are both zero; this specifies the "set" LED operation. This means that, for each LED bit, putled will turn the LED on if the bit is 1 and off if it is 0. This behavior is similar to the component IntToLeds. This results in the bottom three bit of the new counter value being displayed on the LEDs. The operand stack is now empty.

halt: Halt execution. One can always omit the trailing halt; CapsuleInjector will automatically add one. Bombilla will stop running the capsule until the next clock event (one second later).

This clock capsule keeps a stored counter in shared variable 0, decrements it by one on each clock event, and displays the bottom three bits of the new counter on the mote LEDs. Except for sending the data over the UART (discussed in a later section), this capsule's only distinction from the default one is the presence of the inv instruction.

Bombilla Errors

When Bombilla encounters an error in a program (e.g. trying to pop off an empty operand stack), it enters an error state. In this error state, it stops running capsules. Instead, on each clock event, it toggles all of the LEDs (all of them blinking on and off is an indication something has gone wrong) and sends a packet over the UART. The packet is a BombillaErrorMsg and contains information on the cause of the error.

The format of a BombillaErrorMsg is as follows:

typedef struct BombillaErrorMsg {
  uint8_t context;
  uint8_t reason;
  uint8_t capsule;
  uint8_t instruction;
} BombillaErrorMsg;
      

The context field indicates which context triggered the error. The reason field indicates the cause of the error. The capsule field indicates which capsule the context was running when it triggered the error, and the instruction field indicates which instruction in the capsule. A list of reason codes can be found in Bombilla.h:

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;	      

For example, if the error message packet were Currently broken need to fix

7e 00 1d 7d 04 40 03 40 04	      

this would mean that context 64 (0x40, the clock context) failed on capsule 64 (0x40, the clock capsule) on instruction 4 because of an operand stack underflow (reason 3). Here's an example program that would do this; try installing it to see what happens:

pushc 1
getvar 0
add
setvar 0
setvar 0 

Sensing, Types and Shifting

Twiddling with counters shows that Bombilla works, but is of limited use. Bombilla can also read sensors with the sense instruction. sense takes one operand, which indicates which sensor to read. Currently, Bombilla supports two sensors, the temperature and light sensors. Light is sensor 1, and temperature is sensor 2.

An issue arises with the fact that sensor readings have types; for example, what does it mean to add a light reading to a temperature reading? Bombilla handles this problem by having a simple type system. Every variable has one of three types: a value, a sensor reading (of a certain kind), or a buffer. We'll talk more about buffers later; right now, we're concerned with values and readings.

The counter maintained in the previous programs was a value, a 16-bit signed integer. Sensor readings are distinct from values in that they have a sensor type (e.g. light) and are immutable; any operation that modifies a reading produces a value. For example, adding two light readings produces a value. A sensor reading variable represents only a raw reading; otherwise, it could have any value and a light reading shifted three bits to the right would be the same as a raw reading.

Let's recreate the TinyOS application SenseToLeds; this application reads the light sensor and displays the three most significant digits of the ten bit reading on the LEDs:

pushc 1
sense
cast
pushc 7
shiftr
putled	      

Let's step through each instruction and explain what's happening.

pushc 1: Push the value 1 onto the operand stack. The operand stack now has one variable, 1.

sense: Take a reading from a sensor board; the sensor is specified by the variable on top of the stack. Sensor 1 is the light sensor (sensor 2 is the temperature sensor), so this instruction will pop the 1 off the stack and push a light sensor reading. The operand stack now has one variable, a 10 bit light reading.

cast: Pop the sensor reading on top of the stack and push the equal value.

pushc 7: Push the value 7 onto the operand stack. The operand stack now has two variables; the top of the stack is 7 and below it is the 10 bit value of the cast light reading.

shiftr: Bitshift a value to the right; this instruction takes the variable below the top of the operand stack and shifts it right a number of bits specified by the top of the operand stack. In this case, it takes the cast sensor reading and shifts it right seven bits, producing a value; as the sensor value was ten bits, this is the three most significant bits of the reading.

putled: Display these top three bits on the mote LEDs.

Buffers

Storing and dealing with individual values is useful, but often being able to handle sets of data is needed. Bombilla provides buffers, which can hold up to ten variables. Buffers are typed. An empty buffer has no type, and takes on the type of the first variable put in it. For example, if the first variable is a light reading, then the buffer will become a light reading buffer. Attempting to put a variable of another type (e.g. a value) into the buffer will result in an error.

Bombilla provides two buffers, which can be pushed onto the operand stack with bpush0 and bpush1. Variables can be placed in the buffers with the add instruction; this polymorphism of the add instruction leads to a more concise instruction set.

In an add, if the buffer is on top of the stack (with the variable below it), the variable will be prepended. If the variable is on top of the stack (with the buffer below it), the variable will be appended. Appending takes O(1) time, while prepending takes O(n) time. In both cases, the buffer will remain on the stack. For example, the first sequence of instructions will prepend 6 to buffer 0, while the second will append it:

pushc 6
bpush0
add

-------

bpush0
pushc 6
add      

Variables can be extracted from buffers with the bhead, btail, bget and byank instructions. Their semantics are:

bhead: Remove the first variable in the buffer and push it onto the operand stack. Triggers an error if the buffer is empty.

btail: Remove the last variable in the buffer and push it onto the operand stack. Triggers an error if the buffer was empty.

bget: Copy the nth variable of the buffer onto the operand stack; do not remove it. Consumes two operands; the first (on top of the stack) is the index in the buffer, the second is the buffer. Triggers an error if the index is out of bounds.

byank: Remove the nth variable of the buffer and push it onto the operand stack. Consumes two operands; the first (on top of the stack) is the index in the buffer, the second is the buffer. Triggers an error if the index is out of bounds.

There are two instructions for querying the status of a buffer: bsize and bfull. Additionally, buffers can be cleared (set to size 0 with no type) with the bclear instruction. Last of all, the variables in a buffer can be sorted with a single instruction; bsorta sorts them into ascending order, while bsortd sorts them into descending order.

All buffer instructions keep the buffer variable on the operand stack. For example bfull takes one operand, a buffer, and after it completes, the top of the stack is whether the buffer was full, beneath which is the buffer.

Branches

There are two branch instructions in Bombilla: jumps and jumpc; we'll only discuss the first, jumps (which stands for "jump stack" ... jumpc is "jump condition"). Both instructions have an embedded 5-bit operand, the absolute instruction to jump to. jumps consumes a single value operand from the operand stack; if the top of the stack is not a value, this triggers an error. If the value is nonzero, control jumps to the instruction specified by embedded operand. For example, the first code snippet below always jumps (infinite loop) to instruction 8, while the second jumps to instruction 14 if shared variable 3 is equal to 8 (tested with the eq instruction).

pushc 1
jumps 8

-------

getvar 3
pushc 8
eq
jumps 14     

Sample Data Filter

Bringing all of these concepts together, below is a simple data filtering clock capsule. This capsule reads the light sensor and stores it in a buffer. When the buffer is full, it sorts the elements and displays the median value on the LEDs. Comments alongside the instructions briefly explain each step.

bpush0         # Push buffer 0 onto stack
pushc 1        # 
sense          # Sense light (sensor type 1)
add            # Append the reading to the buffer

bfull          # If the buffer was full, push 1, otherwise push 0; buffer off operand stack
jumps 7        # If the buffer was full, jump past the pop and halt
pop            # Pop buffer off stack so stack is empty for next exec
halt         

bsorta         # Sort its elements (stays on the stack)
bsize          # Take its size     (stays on the stack)
pushc 1        
shiftr         # Divide size by 2

byank          # Pull out middle element (size/2)
cast           # Cast sensor reading to a value
pushc 7
shiftr         # Take top 3 bits

putled
bclear         # Clear out the buffer
halt
	      

Communication

Blinking the three LEDs demonstrates you're collecting data, but communicating it is better; these are sensor networks, after all. Bombilla has three communication mechanisms. The first is a built in ad-hoc routing layer; sent using this mechanism is automatically routed to a base station (it uses the Narpro component, so one must have a Narpro base station)). The second is sending to the uart. The third is to trigger Bombilla's routing capsules, which can format headers before sending a packet; this allows ad-hoc routing algorithms to be implemented in Bombilla. This final mechanism is rather complex, and is not covered in this tutorial.

uart: The uart instruction consumes a single operand, a buffer. uart sends that buffer to the mote UART.

send: The send instruction consumes a single operand, a buffer. send passes that buffer to the Narpro component, which sends the packet using a simple beaconless ad-hoc routing algorithm.

Buffers have the following layout in a packet:

typedef struct {
  uint8_t type;
  uint8_t size;
  int16_t entries[BOMB_BUF_LEN];
} BombillaDataBuffer;

where type is one of

typedef enum {
  BOMB_DATA_NONE    = 255,
  BOMB_DATA_VALUE   = 0,
  BOMB_DATA_PHOTO   = 1,
  BOMB_DATA_TEMP    = 2,  
  BOMB_DATA_MIC     = 3,
  BOMB_DATA_MAGX    = 4,
  BOMB_DATA_MAGY    = 5,
  BOMB_DATA_ACCELX  = 6,
  BOMB_DATA_ACCELY  = 7,
  BOMB_DATA_END     = 8
} BombillaSensorType;
      

For example, the packet

00 7e 1f 7d 0 4 05 00 08 00 0c 00 15 00 <crc> <crc>
     

contains a buffer of four values: 5, 8, 13, and 21.

Here's a variation of the previous filtering program; instead of displaying the median value on the LEDs, this capsule sends a sorted buffer over the radio.

bpush0         # Push buffer 0 onto stack
pushc 1        # 
sense          # Sense light (sensor type 1)
add            # Append the reading to the buffer

bfull          # If the buffer was full, push 1, otherwise push 0
jumps 7        # If the buffer was full, jump past the pop and halt
pop            # Pop buffer off stack so stack is empty for next exec
halt         

bsorta         # Sort its elements (stays on the stack)
send           # Send over the radio
bpush0         #
bclear         # Clear out buffer 0

pop            # Pop buffer off operand stack     

Install this capsule and see. Having your Bombilla mote on the programming board can be a problem; on one hand, it has to be plugged in to install the capsule, but it can't have a sensor board on when plugged in (e.g. when it boots), which means that the board will. not be initialized propely. The way to handle this is to transmit the capsule to the mote with a GenericBase; you can then see the packets the mote sends.

Capsule Forwarding

So far, we've been installing capsules on individual motes. This is inherently difficult on large sensor networks, especially multihop networks. Bombilla capsules can therefore virally propagate through a network. One copy of a capsule set "forwarding" will slowly duplicate itself through the network; version numbers are used to determine which capsules to install and which to not.

Install Bombilla on two motes. Using a GenericBase, send a new program to both motes; barring packets being dropped, both should receive and start running the new capsule. Reset the motes and replace the GenericBase with one of the motes, then install the new program over the UART. The second Bombilla mote (not plugged into the UART) will continue to run the old program.

The CapsuleInjector GUI has a radio button for setting whether the generated capsule is forwarding or not. Set your new program to be forwarding, increment the version number, and install it on the mote plugged into the UART. After a little while (within a minute or so), the second mote should start running the new program; the first mote broadcast the new capsule out over the radio and the second mote installed it.

Capsule forwarding uses a very simple heuristic to try to not saturate a network; it takes a rough measure of network activity and decides whether to forward a capsule based on this measure. In a very, very busy network, Bombilla will try forwarding a capsule every minute or so; in an idle one, it forwards every other second or so. However, it randomly selects which capsule to forward; this means that, with 8 capsules, it will actually forward any given capsule every 16 seconds or so.

Other Goodies

Bombilla has several other pieces of functionality, such as the receive and send contexts for message processing. These are, however, outside of the scope of this tutorial.

Complete Instruction Set

Data Consistency in the Presence of Capsule Installation

While Bombilla automatically handles context atomicity (with regards to shared variables, but not buffers) through implicit locking, this can fail due to capsule installation. Notably, as capsules are installed immediately upon reception, a context can be in the midst of a computation when it is halted due to new code being installed.

This means that to ensure perfect data consistency, the values of shared variables cannot be transferred from one version of a capsule to the next. For example, before installing a new version of the clock capsule, one could install a clock capsule that clears out the shared variables, restoring them to a consistent state.

We are currently working on a capsule installation mechanism that will preserve execution atomicity; this understandably becomes difficult in the presence of buggy capsules that do not halt.