[Tinyos-devel] message_t
Jan Hauer
hauer at tkn.tu-berlin.de
Thu Mar 12 12:34:11 PDT 2009
I have updated the proposal, it now uses the same message buffer
abstraction for the send and receive path and supports buffer swapping
on receive. It's based on a circular buffer and forwarding typically
doesn't require copying, but on the send-path protocols would have to
access the buffer via special accessor functions. To be compatible
with AM we *would* have to copy the PDU. The metadata approach has not
changed. I've not included any examples yet.
Jan
On Thu, Mar 12, 2009 at 4:41 PM, Andreas Köpke
<andreas.koepke at tu-berlin.de> wrote:
> One should not overemphasize the "do not copy" mantra. BaseStation for example
> makes an explicit copy, although in a strange fashion. In addition, we can
> copy a packet of 128 bytes length in about 64us -- switching from rx to tx, or
> computing the CRC takes longer than that.
>
> Best, Andreas
>
>
> On Donnerstag 12 März 2009 Jan Hauer wrote:
>> This proposal didn't support buffer swapping, so you'd have to copy
>> the payload before forwarding. To be compatible with AM you'd also
>> have to copy into message_t (we always thought a single copy would be
>> ok). But if the proposal was adapted to use a ring buffer instead of
>> the (still) fixed message buffer layout then copying might not be
>> necessary... I'll adapt the proposal and distribute an updated version
>> in the next email.
>>
>> Jan
>>
>>
>> On Wed, Mar 11, 2009 at 9:00 PM, Janos Sallai
>>
>> <sallai at isis.vanderbilt.edu> wrote:
>> > Jan,
>> >
>> > I just quickly skimmed through the writeup. I have two questions:
>> >
>> > 1. If there are different message structures on the transmit and
>> > receive paths, how can we do bridging without buffer copying?
>> >
>> > 2. How would it be possible, with the proposed message abstraction, to
>> > provide an AM compatibility layer?
>> >
>> > Janos
>> >
>> > On Wed, Mar 11, 2009 at 2:36 PM, Jan Hauer <hauer at tkn.tu-berlin.de> wrote:
>> >> 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-dev
>> >>>el
>> >>
>> >> _______________________________________________
>> >> Tinyos-devel mailing list
>> >> Tinyos-devel at millennium.berkeley.edu
>> >> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-deve
>> >>l
>> >
>> > _______________________________________________
>> > Tinyos-devel mailing list
>> > Tinyos-devel at millennium.berkeley.edu
>> > https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>>
>> _______________________________________________
>> 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
:Version: 2
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
====================================================================
In contrast to message_t the proposed message buffer abstraction
(called ``packet_t`` hereafter) has no fixed boundaries between the
header, data and footer section. The main data structure inside
packet_t is a circular buffer (ring buffer) that contains the entire
PDU. packet_t is used for both, the send and receive path, and
supports buffer swapping on receive. Like message_t it is treated as
an abstract data type (ADT), but the accessor functions are different
from those used in the standard ``Packet`` interface.
packet_t includes a ring buffer of the maximum MDPU size, e.g. 127
byte for 802.15.4 (assuming that the MAC layer is the lowest protocol
layer implemented in software). Like message_t, packet_t is statically
allocated by the initial caller of the send() command. The initial
caller may reserve a "data" field inside the packet_t buffer and put
its payload there. The "data" field would start at the beginning of
the memory region used for the ring buffer and the layout of the
buffer inside packet_t would be as follows:
+-----------+---------------------------------------+
| data | unused |
+-----------+---------------------------------------+
^ ^
| |
start end
"start" and "end" are two indices included in packet_t to denote the
start and the end of the PDU that is currently stored inside the
packet_t buffer. The initial callee (e.g. a protocol component) of
the send() command may attach a variable-sized header and/or footer to
the packet and pass it on via send() to another component, which may
do the same. A header is always attached before the current PDU and a
footer is always attached after the current PDU. Because packet_t
uses a ring buffer there can a wrap around at the beginning or end of
the underlying memory region. 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 |
+-----------+-----+-----+---------------+-----+-----+
^ ^
| |
end start
When a packet_t arrives at the bottom of the protocol stack the MPDU
is constructed and transmitted. While the sendDone() event propagates
back every involved component removes any header(s) or footer(s) that
it previously allocated inside the packet_t (by adjusting the "start"
and "end" indices).
On the receive path the component at the bottom of the protocol stack
will allocate a packet_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. Thus, the layout of the buffer would be
as follows:
+-----------+-------+-----------+--------------------+
| header(s) | data | footer(s) | unused |
+-----------+-------+-----------+--------------------+
^ ^
| |
start end
When forwarding a received packet the header(s) and footers(s) section
may grow, shrink or stay the same size. For example, assuming that the
header section increased then at the bottom of the protocol stack the
packet buffer of a packet that is being forwarded might look like
this:
+-----------+-------+-----------+--------+-----------+
| header(s) | data | footer(s) | unused | header(s) |
+-----------+-------+-----------+--------+-----------+
^ ^
| |
end start
One consequence of the ring buffer property is that components cannot
always allocate a consecutive memory region to write their
headers/footers to, because of the wrap arounds at the beginning or
end of the underlying memory region. Treating packet_t as abstract
data type allows to hide these wrap arounds from the client
components. As a consequence, whenever wrap arounds are possible
components SHOULD access packet_t through accessor functions provided
by a system library.
Wrap arounds are possible only on the send path and then only in
intermediate protocol layers (they never affect the first caller of
the send() command, i.e. never the application, because the data
section cannot wrap around). Consequently these components SHOULD
attach their protocol headers/footers to packet_t via a system library
providing (e.g. typed) interfaces for assembling a header/footer from
basic data types (nx_uint8_t, nx_uint16_t, etc.). For example, a
protocol component could assemble its header/footer by calls like the
following:
call Header.attach_nx_uint8(sequenceNumber);
call Header.attach_nx_uint16(shortAddress);
call Footer.attach_nx_uint32(timestamp);
If this cannot be done, then clients would have to use an interfaces
that would copy their header/footer buffer into packet_t. A second
case when packet_t would require copying is for compatibility with AM:
the PDU inside packet_t would have to be copied to the data section
inside a message_t.
Metadata
--------------------------------------------------------------------
Every packet_t includes a fixed-sized metadata buffer. The size of
this buffer is determined by the components on the send/receive path
which may reserve a certain fixed memory region inside the metadata
buffer at compile time. A memory regions inside the metadata buffer is
accessed exclusively by the component that has reserved it. In its
portion of the metadata buffer a component could to store information
associated with the packet (timestamp, RSSI, etc.) or temporary
information on the component state, etc. To make this information
accessible to other components a component would provide
metadata-specific interfaces (GetTimestamp, etc.).
Definitions
====================================================================
// for every byte a component wants to reserve in the
// metadata buffer it would use a unique(METADATA_BYTE)
typedef uint8_t metadata_t[uniqueCount(METADATA_BYTE)];
typedef struct packet {
uint8_t start; // start of PDU, offset into data buffer
uint8_t end; // end of PDU, offset into data buffer
uint8_t data[MAX_PPDU_SIZE]; // e.g. for 802.15.4 MAX_PPDU_SIZE is 127
metadata_t metadata;
} packet_t;
interface PacketSend
{
/**
* NOTE: this interface is meant as one example of an address free protocol
* interface, but there would be other interfaces that use protocol specific
* parameters, e.g.
*
* send(packet_t *packet, address_t destAdress, bool ackRequest, ...)
*
* ... and a callee could use the parameter to assemble its header.
* An interface could also provide two separate commands, one for setting the
* addresses and another one for sending the packet.
*/
/**
* Sends a packet. The caller can use the <tt>X</tt> interface
* to allocate a payload region or protocol headers/footers inside
* the packet before calling this command.
*
* @param packet 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(packet_t *packet);
/**
* 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 attached a header to this packet
* before calling the <tt>send()</tt> command, then the header MUST
* be removed (through the <tt>X</tt> interface) before propagating
* the <tt>sendDone()</tt> event further. The same MUST be done for
* a footer.
*
* @param packet The packet that was requested to be sent
* @param error SUCCESS if it was transmitted successfully, FAIL if
* it was not
*/
event void sendDone(packet_t *packet, error_t error);
/**
* Returns a pointer to a component's metadata region in a packet.
* Like Packet.getPayload() this call propagates down the protocol
* stack and every component adds an offset corresponding to the
* number of metadata bytes it has reserved to a pointer that
* initially points to the start of the packet's metadata buffer.
*
* @param packet 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(packet_t *packet);
}
interface PacketReceive
{
/**
* Receive a packet. A component signalling this event MUST
* make sure that <tt>pdu</tt> points to the start of the PDU
* belonging to the component implementing the event handler
* (i.e. to the SDU of the signalling component).
* It SHOULD use the <tt>X.X</tt> command to do this.
* For example, assuming that it used a header of 5 byte and the
* footer of 3 byte a component could implement the following event
* handler:
*
* command PacketReceive.receive(uint8_t *pdu, packet_t *packet)
* {
* signal PacketReceive.receive(call X.X(5,3), packet);
* }
*
* @param pdu Points to the start of the PDU belonging to the
* component implementing the event handler
* @param packet The received packet
* @return a packet buffer for the stack to use for the next
* received packet.
*/
event packet_t *receive(uint8_t *pdu, packet_t *packet);
/**
* Returns a pointer to a component's metadata region in a packet.
* Like Packet.getPayload() this call propagates down the protocol
* stack and every component adds an offset corresponding to the
* number of metadata bytes it has reserved to a pointer that
* initially points to the start of the packet's metadata buffer.
*
* @param packet 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(packet_t *packet);
}
More information about the Tinyos-devel
mailing list