[Tinyos-host-mote-wg] [Tinyos-2.0wg] Packet formats, Radio vs. UART

[Philip Levis]

This is the not-quite-consensus we reached last telecon. I think that  
this issue is important and central enough that we shouldn't rush  
through it; I'd rather that people mull on it a bit and raise  
concerns. Otherwise, we will pay dearly in the long term. There's  
also a copying wrinkle I hadn't foreseen, which is troubling.

The basic issue is determining is what the format of a message_t, the  
2.x message buffer, is. message_t has three important design  
considerations:

1) Communication layers MUST be able to use message_t without buffer  
copying. That is, if a radio is passed a message_t with data in it,  
the radio MUST be able to send a packet containing the data without  
copying the data out of the buffer.

2) If possible, communication layers MUST be able to exchange  
message_t buffers at the allocation level. That is, if a program  
receives a message_t* from communication layer X, then it MUST be  
able to pass that message_t* to communication layer Y. There are some  
cases when this is not possible, e.g., if a layer requires that all  
of its buffers originate from a certain area of memory. There are  
three possible solutions in this case: institute a single copy at the  
lowest layer, removing the restrictive addressing, keep the pools of  
buffers separate at the program level, or allocate all of them to  
satisfy the restrictive layer. Note that unless this third approach  
is used, moving buffers between two layers may, at some point,  
require a copy (unrestricted address -> restricted address).

3) message_t structures should be as small as possible.

Generally, a radio chip implementation specifies a packet format. For  
example, the CC1000 defines a basic AM packet, something along the  
lines of:

   uint16_t addr;
   uint8_t type;
   uint8_t group;
   uint8_t length;
   int8_t data[TOSH_DATA_LENGTH];
   uint16_t crc;

while the CC2420 specifies a format determined by 802.15.4:

   uint8_t length;
   uint8_t fcfhi;
   uint8_t fcflo;
   uint8_t dsn;
   uint16_t destpan;
   uint16_t addr;
   uint8_t type;
   uint8_t group;
   int8_t data[TOSH_DATA_LENGTH];

Let's suppose we have a platform that has a CC2420 and a CC1K radio,  
and wants both stacks. How do we get TinyOS to support both? The  
first problem is structure definition: you can't let a chip define  
message_t, as then you have to live with either
the CC1K or the CC2420 structure, and the decision of which will be  
based on include path order (ick!). The logical conclusion is that a  
*platform* is responsible for defining message_t; radio chips define  
their packet structures, and a platform then maps those onto  
message_t. In this case, for example, our hypothetical platform could  
define message_t to be a union of the two packet formats.

Since it's a union, this means that you can freely pass message_t  
structures between the two stacks; as the CC2420 packet header is  
larger, the CC1K stack will just not use the end of the memory region.

This does, however, raise one tricky issue: the data regions of the  
two layers are different. This means that, doing something like this  
will completely break:

message_t* CC1KReceive.receive(message_t* m) {
   message_t* freeBuf = allocFromQueue();
   if (freeBuf == NULL) {
     return m;
   }
   else if (call CC2420Send.send(m, call CC1KPacket.length(m)) ==  
FAIL) {
     putOnQueue(freeBuf);
     return m;
   }
   else {
     return freeBuf;
   }
}


I know the above code isn't completely right, but it'll do. The issue  
above is in the call to CC2420Send.send. In the union model, the CC1K  
data region starts in the header of a CC2420 packet. This means that  
just blindly calling send() will corrupt your data. You have to do a  
payload shift, something like:

   uint8_t len;
   void* p1 = call CC1000Packet.getPayload(m, &len);
   void* p2 = call CC2420Packet.getPayload(m, NULL);

   if (p1 > p2) {  // Never true, but let's be safe and not make  
assumptions
     memcpy(p2, p1, len); // copies from 0... len-1
   }
   else {
     reversememcpy(p2, p1, len); // copies from len-1 ... 0
   }

This means that you have to, in the end, copy. The only way to avoid  
this is if you can align the payload fields of many link layers (so  
you have header as well as footer padding), OR if you institute a  
single-copy approach at the lowest layer and pass around application- 
sized buffers.

However, this copy is necessary ONLY when you have two radios that  
have different packet structures. This is the uncommon case.  
Instituting single copy at the bottom layer can make this problem go  
away, but it imposes a cost on all systems.


The UART
------------

 From what we talked about, the UART does not follow the message_t  
model. First, it is almost always a byte-level interface, which  
provides much greater flexibility. Additionally, often the UART is  
needs to completely encapsulate radio packets (e.g., for a TOSBase).  
If it adds additional fields, then it can't be part of message_t  
(there would be a recursive definition of infinite size). This means  
that the UART takes a message_t* for sending/receiving, but it can  
add some additional data to the packet (e.g., a type for packet  
contents identification).

For example, a UART packet could be on the lines of

type byte | message_t

Where the type byte states what kind of message_t it is. For example,  
0 could mean cc1000/tr1000, while 1 means cc2420. This is  
encapsulated in the UART framing protocol.
It allows transmission of metadata as well as data, which is very  
useful for packet logging.

Phil

-------

"We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time."

- T. S. Eliot,  'Little Gidding'

_______________________________________________
Tinyos-2.0wg mailing list
Tinyos-2.0wg at Mail.Millennium.Berkeley.EDU
https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-2.0wg