[Tinyos-devel] message_t
Jan Hauer
hauer at tkn.tu-berlin.de
Wed Mar 11 12:36:48 PDT 2009
Attached is a proposal for an alternative message buffer abstraction
that allows variable-sized protocol headers/footers, but still uses
static allocation of the message buffer. We have not discussed this in
detail, so ... go on and take it apart :)
Jan
On Wed, Mar 11, 2009 at 6:53 PM, Philip Levis <pal at cs.stanford.edu> wrote:
> As developers have started implementing standards on TinyOS, message_t
> has started to show some limitations. The goal of message_t was to
> allow software to pass messages between different AM link layers
> without copying, and this involved several simplifying assumptions. As
> systems need more complex link layers (e.g., more than one 15.4
> addressing mode, security support, IPv6 on top of 15.4), some of the
> design decisions have started to become problematic.
>
> For example, message_t requires that the header, data, and footer be
> allocated separately. Depending on your 15.4 addressing and other
> options, the header can be anywhere from 3 to 30 bytes or so.
> Correspondingly, the payload can be anywhere from 120 to 95 bytes or
> so. While the two of them have, in combination, a maximum length
> (125), you have to allocate the maximum of each of them separately,
> leading to about a 20% waste (150 bytes).
>
> This has led core to start looking at other message abstractions. It's
> important to note that changing the underlying buffer abstraction used
> by radio drivers does not mean we have to break AM-based software
> compatibility: many of these issues are arising exactly because TinyOS
> needs more than just AM. At the worst case, you just make a single
> copy between the AM layer (message_t) and other buffer abstraction
> that drivers and other stacks use.
>
> Jan (TU Berlin) is going to send out one proposal he's come up with.
> Stephen (Berkeley) also has some thoughts, and I encourage everyone to
> examine the proposals. This is hopefully something that will change
> for 2.1.1, or if more involved than anticipated, maybe a later version.
>
> Thanks,
>
> Phil
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>
-------------- next part --------------
====================================================================
Proposal for an Alternative Message Buffer Abstraction in TinyOS 2
====================================================================
:Author: Jan-Hinrich Hauer
Motivation
====================================================================
The current message buffer abstraction, message_t [tep111], is
structured into a fixed-sized link layer header, data, footer and
metadata section. This is suboptimal when used with protocols that
have variable-sized headers or footers, such as the IEEE 802.15.4 MAC.
For example, the 802.15.4 MAC header size can vary between 3 and 23
byte (+ 14 byte for the optional security header) and the maximum MSDU
(aMaxMACPayloadSize) is 118 byte. Using message_t one would have to
allocate for the worst case, respectively: 23 + (14) byte for the
link-layer header and 118 byte for the data section, resulting in a
total of 155 byte. Since the maximum 802.15.4 MPDU size is 127 byte,
28 byte of memory would never be used in every such message_t.
Protocols on top of the link layer currently also have to use
fixed-sized headers and footers due to the way the message_t data
section is accessed: the Packet.getPayload() commands propagates
through the entire protocol stack allowing every involved protocol
to reserve a fixed-sized portion in the data section. This is
impractical with more dynamic approaches (e.g. 6loWPAN header
compression), because at the time Packet.getPayload() is called the
size of the header/footer may still be unknown.
This document proposes an alternative message buffer abstractions that
allows variable-sized headers and footers on every layer of the
protocol stack.
Proposal Overview
====================================================================
The send and receive paths use different message buffer abstractions:
txmsg_t and rxmsg_t.
(Note: in the following explanation the MAC layer is assumed to be the
lowest layer implemented in software; the MPDU is passed to the radio
hardware, which may then transparently add its PHY header/footer)
txmsg_t
--------------------------------------------------------------------
On the send path a packet is represented by a txmsg_t, which includes
a buffer of the maximum MDPU size (e.g. 127 byte for 802.15.4). Like
message_t, txmsg_t is statically allocated by the initial caller of
the PacketSend.send() command. This initial caller may reserve a
"data" field inside the txmsg_t buffer and put its data there.
The initial callee (e.g. a protocol component) may allocate space
for a variable-sized header and/or footer inside the txmsg_t buffer,
put its header/footer there and pass it on via PacketSend.send() to
another (protocol) component, which may then do the same, and so on.
When a txmsg_t arrives at the bottom of the protocol stack the MPDU is
constructed and transmitted. While the PacketSend.sendDone() event
propagates back every involved component deallocates any header(s) or
footer(s) that it previously allocated inside the txmsg_t.
This is the layout of the buffer inside txmsg_t:
+--------+-----------+------------+-----------+
| data | footer(s) | unused | header(s) |
+--------+-----------+------------+-----------+
The size of the four regions inside the buffer is variable. A new
footer will always be allocated *after* the existing footer(s) field
(or after the "data" region, if it is the first footer) and a new
header will always be allocated *before* the existing header(s) field
(or at the end of the buffer, if it is the first header). Thus the
footers field will grow "upwards" into the unused region and the
header(s) field will grow "downwards" into the unused region. When the
footer field overlaps with the header field then the packet is bigger
than the maximum PDU size, cannot be sent, and an error is returned.
For example, if the protocol stack consists of a MAC, a routing and a
transport protocol then at the bottom of stack the layout of the
buffer could be as follows (assuming MAC added a header (MHR) and
footer (MFR), routing added a header only (RHR) and transport added
only a footer (TFR)):
+--------+-----+-----+------------+-----+-----+
| data | TFR | MFR | unused | MHR | RHR |
+--------+-----+-----+------------+-----+-----+
At the bottom of the protocol stack the entire MPDU can be constructed
by concatenating the header(s) with the payload and the footer(s).
While the txmsg_t propagates back up the protocol stack via the
PacketSend.sendDone() event the headers and footers are deallocated in
the reverse order in which they were allocated. The footer(s) and
header(s) field will shrink and the initial caller will be signalled a
buffer that (conceptually) only includes its payload.
rxmsg_t
--------------------------------------------------------------------
On the receive path a packet is represented by rxmsg_t, which includes
a buffer of the maximum MPDU size (e.g. 127 byte for 802.15.4). The
component at the bottom of the protocol stack will allocate the
rxmsg_t and fill its buffer with the incoming MPDU starting with the
first byte of the MAC header and ending with the last byte of the MAC
footer.
This is the layout of the buffer inside rxmsg_t:
+-----------+-------+----------+--------------+
| header(s) | data |footer(s) | unused |
+-----------+-------+----------+--------------+
While the rxmsg_t is signalled upwards in the protocol stack, every
component MUST deallocate any headers or footers that it is
reponsible for before it passes the rxmsg_t to the next higher layer.
The footer(s) and header(s) field will shrink and the final callee
will be signalled a buffer that (conceptually) only includes its
payload.
Metadata
--------------------------------------------------------------------
Every txmsg_t includes a fixed-sized metadata buffer. The size of this
buffer depends on the components on the send path which may reserve a
certain fixed region inside the buffer at compile time. Such a
component may then use the memory region exclusively to store
information associated with the packet (timestamp, rssi, etc.) or for
temporary information on the component state, etc.
The same is true for an rxmsg_t (but here the metadata buffer size
depends on the reservations made by the components on the receive
path).
Definitions
====================================================================
typedef uint8_t tx_metadata_t[uniqueCount(TX_METADATA_BYTE)];
typedef uint8_t rx_metadata_t[uniqueCount(RX_METADATA_BYTE)];
typedef struct txmsg {
uint8_t *fhs; // first header start
uint8_t *lfe; // last footer end
uint8_t data[MAX_PPDU_SIZE]; // e.g. for 802.15.4 MAX_PPDU_SIZE is 127
tx_metadata_t metadata;
// invariant: fhs and lfe are either NULL or point into the data buffer
} txmsg_t;
typedef struct rxmsg {
void *pdu; // "current" PDU
uint8_t pdulen; // "current" PDU length
uint8_t data[MAX_PPDU_SIZE]; // e.g. for 802.15.4 MAX_PPDU_SIZE is 127
rx_metadata_t metadata;
// invariant: pdu is either NULL or points into the data buffer
} rxmsg_t;
interface PacketSend
{
/**
* Sends a packet. The caller can use the <tt>TxMsg</tt> interface
* to allocate a payload region or protocol headers/footers inside
* the packet before calling this command.
*
* @param msg the packet to send
* @return SUCCESS if the request was accepted and will issue
* a sendDone event, EBUSY if the component cannot accept
* the request now but will be able to later, FAIL
* if the stack is in a state that cannot accept requests
* (e.g., it's off).
*/
command error_t send(txmsg_t *msg);
/**
* Signalled in response to a successful call to <tt>send()</tt> and
* completing the transmission of a packet. If the component
* implementing the event handler allocated a header inside this
* packet before calling the <tt>send()</tt> command, then the
* header MUST be deallocated, before propagating the
* <tt>sendDone()</tt> event further. The same MUST be done for a
* footer.
*
* @param msg The packet that was requested to be sent
* @param error SUCCESS if it was transmitted successfully, FAIL if
* it was not
*/
event void sendDone(txmsg_t *msg, error_t error);
/**
* Returns a pointer to a component's metadata region in a packet.
*
* @param msg The packet
* @return a pointer to the packet's metadata region in the packet,
* or NULL if the (content of the) packet is invalid
*/
command void *getMetadata(txmsg_t *msg);
// comments:
// - add a cancel() command?
// - deputy annotations
}
interface PacketReceive
{
/**
* Receive a packet. Use the <tt>RxMsg</tt> interface to access the
* content of the packet. Any header or footer belonging to the
* component implementing the event handler MUST be deallocated
* before signalling the <tt>receive()</tt> event further. The same
* MUST be done for a footer. The packet MUST NOT be accessed after
* the event handler returns.
*
* @param pdu Points to the start of the PDU belonging to the
* component implementing the event handler
* @param pdulen Length of the PDU
* @param msg The received packet
*/
event void receive(const uint8_t *pdu, uint8_t pdulen, rxmsg_t *msg);
/**
* Returns a pointer to a component's metadata region in a packet.
*
* @param msg The packet
* @return a pointer to the packet's metadata region in the packet,
* or NULL if the (content of the) packet is invalid
*/
command void *getMetadata(rxmsg_t *msg);
}
interface TxMsg
{
command void clear(txmsg_t *packet);
command void *getPayload(rxmsg_t *packet, uint8_t *len);
command const void *getHeader(rxmsg_t *packet);
command const void *getFooter(rxmsg_t *packet, uint8_t footerLen);
command uint8_t *allocPayload(txmsg_t *packet, uint8_t len);
command uint8_t *allocHeader(txmsg_t *packet, uint8_t len);
command uint8_t *allocFooter(txmsg_t *packet, uint8_t len);
command error_t freeHeader(txmsg_t *packet, uint8_t len);
command error_t freeFooter(txmsg_t *packet, uint8_t len);
command uint8_t pdulen(txmsg_t *packet);
command error_t pducpy(uint8_t *buffer, txmsg_t *packet, uint8_t *buflen);
command error_t setPayloadLength(txmsg_t *packet, uint8_t len);
}
interface RxMsg
{
command const void *getPayload(rxmsg_t *packet, uint8_t *len);
command const void *getHeader(rxmsg_t *packet);
command const void *getFooter(rxmsg_t *packet, uint8_t footerLen);
command error_t freeHeader(rxmsg_t *packet, uint8_t len);
command error_t freeFooter(rxmsg_t *packet, uint8_t len);
command uint8_t pdulen(rxmsg_t *packet);
}
Example
====================================================================
The following code probably includes mistakes (I haven't tried
to compile it) but the idea should become clear.
Application Implementation
--------------------------------------------------------------------
txmsg_t m_packet;
event void Boot.booted()
{
uint8_t *payload;
call TxMsg.clear(&m_packet);
payload = call TxMsg.allocPayload(&m_packet, x); // x (payload size) is variable
// fill payload[0 .. x-1] with our data
call PacketSend.send(&m_packet);
}
event void PacketSend.sendDone(txmsg_t *packet, error_t error)
{
uint8_t payloadLen, *payload;
// ... might want to access the payload that we sent ...
payload = call TxMsg.getPayload(packet, &payloadLen);
// get metadata via "some" interfaces provided by "some" component
// that has processed the packet on its way up the stack:
uint32_t timestamp = call TxTimestamp.get(packet);
// ... could re-send the packet ...
}
event void PacketReceive.receive(const uint8_t *payload,
uint8_t payloadLen, rxmsg_t *packet);
{
// ... inspect/copy payload ...
// get metadata via "some" interfaces provided by "some" component
// that has processed the packet on its way up the stack:
uint32_t timestamp = call RxTimestamp.get(packet);
return; // MUST NOT keep reference to packet/payload
}
Protocol Implementation
--------------------------------------------------------------------
enum {
// this reserves us a certain number of bytes in the
// metadata portion of *every* txmsg_t / rxmsg_t
// (there is probably a better way of doing this)
dontCare1 = unique(TX_METADATA_BYTE) + unique(TX_METADATA_BYTE) + ...,
dontCare2 = unique(RX_METADATA_BYTE) + unique(RX_METADATA_BYTE) + ...,
};
command error_t PacketSend.send(txmsg_t *packet)
{
error_t result;
uint8_t *myHeader, *myFooter;
my_metadata_t *myMetadata = (my_metadata_t *) call SubPacketSend.getMetadata(packet);
// ... fill myMetadata with some data ...
myHeader = call TxMsg.allocHeader(packet, hlen); // hlen is variable
myFooter = call TxMsg.allocFooter(packet, flen); // flen is variable
// ... fill myHeader/myFooter buffer with our data ...
if ((result = call SubPacketSend.send(packet)) != SUCCESS) {
call TxMsg.freeHeader(packet, hlen);
call TxMsg.freeFooter(packet, flen);
}
return result;
}
event void SubPacketSend.sendDone(txmsg_t *packet, error_t error);
{
// we must know our header and footer length (hlen and flen) ourselves,
// e.g. by looking at the header content or via metadata...
const uint8_t *myHeader = call TxMsg.getHeader(packet, hlen);
const uint8_t *myFooter = call TxMsg.getFooter(packet, flen);
my_metadata_t *myMetadata = (my_metadata_t *) call SubPacketSend.getMetadata(packet);
// ... inspect / fill myMetadata with some data ...
call TxMsg.freeHeader(packet, hlen);
call TxMsg.freeFooter(packet, flen);
signal PacketSend.sendDone(packet, error);
}
event void SubPacketReceive.receive(const uint8_t *myHeader, uint8_t pdulen, rxmsg_t *packet);
{
// we must know our header and footer length (hlen and flen) ourselves,
// e.g. by looking at the header content or via metadata...
const uint8_t *myFooter = call RxMsg.getFooter(packet, flen);
my_metadata_t *myMetadata = (my_metadata_t *) call SubPacketReceive.getMetadata(packet);
call RxMsg.freeHeader(packet, hlen);
call RxMsg.freeFooter(packet, flen);
signal PacketReceive.receive(call RxMsg.getHeader(msg), call RxMsg.pdulen(msg), packet);
}
command void *PacketSend.getMetadata(txmsg_t *packet)
{
return (uint8_t*) call SubPacketSend.getMetadata(packet) + sizeof(my_metadata_t);
}
command void *PacketReceive.getMetadata(rxmsg_t *packet)
{
return (uint8_t*) call SubPacketReceive.getMetadata(packet) + sizeof(my_metadata_t);
}
command val_t SomePublicTxMetadataAttrib.get(txmsg_t *packet)
{
return ((my_metadata_t*) call SubPacketSend.getMetadata(packet))->val;
}
Radio Driver (Lowest Protocol Layer) Implementation
--------------------------------------------------------------------
uint8_t m_txppdu[MAX_PPDU_SIZE];
rxmsg_t m_rxsmg;
enum {
dontCare1 = unique(TX_METADATA_BYTE) + ...; // analog to (b)
dontCare2 = unique(RX_METADATA_BYTE) + ...; // analog to (b)
};
command error_t PacketSend.send(txmsg_t *packet) {
uint8_t *myHeader, *myFooter, len = MAX_PPDU_SIZE;
my_metadata_t *myMetadata = (my_metadata_t *) packet->metadata;
// fill myMetadata with some data
myHeader = call TxMsg.allocHeader(packet, hlen); // hlen is variable
myFooter = call TxMsg.allocFooter(packet, flen); // flen is variable
// ... fill myHeader/myFooter buffer with our data ...
// with most radio's (e.g. CC2420) we wouldn't have to do the next
// step (copy), because the packet can be transferred in the radio
// memory in two separate steps (first the headers, then the data
// and footers)
call TxMsg.pducpy(&m_txppdu, packet, len);
call Radio.transmit(m_txppdu, len); // conceptually ...
call TxMsg.freeHeader(packet, hlen);
call TxMsg.freeFooter(packet, flen);
myMetadata->timestamp = radio_timestamp;
signal PacketSend.sendDone(packet, error);
}
event void Radio.receive(uint8_t ppdulen, uint32_t timestamp, ...)
{
// let's assume that the packet was written into our m_rxsmg buffer
m_rxsmg.pdu = &m_rxsmg.data;
m_rxsmg.pdulen = ppdulen;
// here we use the same metadata for rx and tx path
// (but they could be different)
my_metadata_t *myMetadata = (my_metadata_t *) &m_rxsmg.metadata;
myMetadata->timestamp = timestamp;
call RxMsg.freeHeader(&m_rxsmg, hlen);
call RxMsg.freeFooter(&m_rxsmg, flen);
signal PacketReceive.receive(call RxMsg.getHeader(msg), call RxMsg.pdulen(msg), &m_rxsmg);
}
command void *PacketSend.getMetadata(txmsg_t *packet)
{
return (uint8_t *) packet->metadata + sizeof(my_metadata_t);
}
command void *PacketReceive.getMetadata(rxmsg_t *packet)
{
return (uint8_t *) packet->metadata + sizeof(my_metadata_t);
}
command uint32_t TxTimestamp.get(txmsg_t *packet)
{
return ((my_metadata_t*) packet->metadata)->timestamp;
}
command uint32_t RxTimestamp.get(rxmsg_t *packet)
{
return ((my_metadata_t*) packet->metadata)->timestamp;
}
The System Component Providing the TxMsg/RxMsg Interfaces
--------------------------------------------------------------------
command void TxMsg.clear(txmsg_t *packet) {
packet->fhs = packet->lfe = NULL;
}
command void *TxMsg.getPayload(rxmsg_t *packet, uint8_t *len) {
if (packet == NULL || packet->lfe == NULL) { *len=0; return NULL; }
*len = packet->lfe - packet->data;
return packet->data;
}
command const void *TxMsg.getHeader(rxmsg_t *packet) {
if (packet == NULL) return NULL;
if (packet->fhs == NULL) {
if (packet->lfe == NULL)
return NULL;
else
return packet->data;
}
return packet->fhs;
}
command const void *TxMsg.getFooter(rxmsg_t *packet, uint8_t flen) {
if (packet == NULL || packet->lfe == NULL) return NULL;
if (packet->lfe - packet->data < flen) return NULL;
return packet->data + packet->lfe - flen;
}
command uint8_t *TxMsg.allocPayload(txmsg_t *packet, uint8_t len) {
if (packet == NULL || packet->fhs != NULL ||
packet->lfe != NULL || len > MAX_PPDU_SIZE)
return NULL;
packet->lfe = packet->data + len;
return packet->data;
}
command uint8_t *TxMsg.allocHeader(txmsg_t *packet, uint8_t len) {
uint8_t *dst;
if (packet == NULL) return NULL;
if (packet->fhs == NULL)
dst = packet->data + MAX_PPDU_SIZE - len;
else
dst = packet->fhs - len;
if (dst > packet->lfe)
packet->fhs = dst;
else
dst = NULL;
return dst;
}
command uint8_t *TxMsg.allocFooter(txmsg_t *packet, uint8_t len) {
uint8_t *dst;
if (packet == NULL) return NULL;
if (packet->lfe == NULL)
dst = packet->data;
else
dst = packet->lfe;
if (dst + len < packet->fhs) {
packet->lfe = dst + len;
return dst + 1;
} else
return NULL;
}
command error_t TxMsg.freeHeader(txmsg_t *packet, uint8_t len) {
uint8_t *dst, max;
if (packet == NULL || packet->fhs == NULL) return EINVAL;
max = (packet->data + MAX_PPDU_SIZE) - packet->fhs;
if (len > max) return ESIZE;
packet->fhs += len;
return SUCCESS;
}
command error_t TxMsg.freeFooter(txmsg_t *packet, uint8_t len) {
uint8_t *dst, max;
if (packet == NULL || packet->lfe == NULL) return EINVAL;
max = packet->lfe - packet->data;
if (len > max) return ESIZE;
packet->lfe -= len;
return SUCCESS;
}
command uint8_t TxMsg.pdulen(txmsg_t *packet) {
if (packet == NULL || packet->lfe == NULL) return 0;
if (packet->fhs == NULL) return packet->lfe - packet->data;
return MAX_PPDU_SIZE - (packet->fhs - packet->lfe);
}
command error_t TxMsg.pducpy(uint8_t *buffer, txmsg_t *packet, uint8_t *buflen){
uint8_t i = 0;
if (packet == NULL || packet->lfe == NULL) return EINVAL;
if (packet->fhs != NULL) {
i = (packet->data + MAX_PPDU_SIZE) - packet->fhs;
memcpy(buffer, packet->fhs, i);
}
memcpy(buffer+i, packet->data, packet->lfe - packet->data);
return SUCCESS;
}
command error_t TxMsg.setPayloadLength(txmsg_t *packet, uint8_t len) {
if (len > MAX_PPDU_SIZE) return ESIZE;
packet->lfe = packet->data + len;
return SUCCESS;
}
command const void *RxMsg.getPayload(rxmsg_t *packet, uint8_t *len) {
if (packet == NULL || len == NULL) return NULL;
*len = packet->pdulen;
return packet->pdu;
}
command const void *RxMsg.getHeader(rxmsg_t *packet) {
return packet->pdu;
}
command const void *RxMsg.getFooter(rxmsg_t *packet, uint8_t footerlen) {
if (packet == NULL || packet->pdu == NULL) return NULL;
return packet->pdu + packet->pdulen - footerlen;
}
command error_t RxMsg.freeHeader(rxmsg_t *packet, uint8_t len) {
if (packet == NULL || packet->pdu == NULL) return EINVAL;
if (len > packet->pdulen) return ESIZE;
packet->pdu += len;
packet->pdulen -= len;
return SUCCESS;
}
command error_t RxMsg.freeFooter(rxmsg_t *packet, uint8_t len) {
if (packet == NULL || packet->pdu == NULL) return EINVAL;
if (len > packet->pdulen) return ESIZE;
packet->pdulen -= len;
return SUCCESS;
}
More information about the Tinyos-devel
mailing list