[Tinyos Core WG] Fwd: [Tinyos-devel] message_t
Jan Hauer
jan.hauer at gmail.com
Wed May 6 06:32:53 PDT 2009
You attached an old proposal, it was replaced by
T2_packet_proposal_v2.txt. I just re-read this version and there is
yet another detail that I want to change (in my previous proposal a
protocol had to access the content of its header/footer through
special accessor functions, in the newest version it does not, because
a header/footer is never split into disconnected memory regions). You
find the latest version attached to this email.
Jan
On Wed, May 6, 2009 at 8:11 AM, Philip Levis <pal at cs.stanford.edu> wrote:
> Apologies: Jan should also have been on the message_t list of discussants.
>
> Phil
>
> Begin forwarded message:
>
>> From: Jan Hauer <hauer at tkn.tu-berlin.de>
>> Date: March 11, 2009 12:36:48 PM PDT
>> To: TinyOS Development <tinyos-devel at millennium.berkeley.edu>
>> Subject: Re: [Tinyos-devel] message_t
>>
>> 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
>>>
>
>> _______________________________________________
>> Tinyos-devel mailing list
>> Tinyos-devel at millennium.berkeley.edu
>> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>
>
> _______________________________________________
> Tinyos-2.0wg mailing list
> Tinyos-2.0wg at millennium.berkeley.edu
> https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-2.0wg
>
-------------- next part --------------
====================================================================
Proposal for an Alternative Message Buffer Abstraction in TinyOS 2
====================================================================
:Author: Jan-Hinrich Hauer
:Version: 3
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: when a protocol component calls
Packet.getPayload() to determine the offset of its payload region
inside a message_t, the call propagates through the entire protocol
stack forcing every involved protocol to specify the amount of memory
it requires for its header/footer.
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
consists of two disconnected memory regions: the first N bytes of the
MPDU (here N = sizeof(MHR) + sizeof(RHR)) commence at the "start"
index and the remaining bytes commence at the start of the ring
buffer's underlying memory region. A radio driver will typically be
able to assemble the MPDU on-the-fly by concatenating the first region
with the second as the packet is moved to the radio buffer
(packet-based radio) or while the individual bytes are sent out
(byte-based radio).
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
While the packet propagates upwards in the protocol stack, all
involved protocols MUST remove (deallocate) their headers/footers
before they pass the packet_t upwards. The allocation/deallocation is
done with the help of a T2 library component. For example, when the
packet from the previous example arrives at the application the layout
of the buffer would be as follows:
+-----------+-------+--------------------------------+
| unused | data | 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, because a 16-bit 802.15.4 short address was
replaced by a 64-bit extended address, then at the bottom of the
protocol stack the packet buffer might look like this:
+-----------+-------+-----------+--------+-----------+
| header(s) | data | footer(s) | unused | header(s) |
+-----------+-------+-----------+--------+-----------+
^ ^
| |
end start
One consequence of the ring buffer property is that when the header(s)
or footers(s) section changes in size then there can be a wrap around
at the beginning or end of the underlying memory region such that a
single protocol header/footer would need to be split into two
disconnected memory regions. This is inconvenient for a protocol
implementation and must be avoided. The proposed solution is to, in
this case, shift (memmove) the ring buffer content such that the start
of the ring buffer's underlying memory region is always aligned with
the start of a header or the data section.
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 region inside the metadata buffer is
accessed exclusively by the component that has reserved it and it is
opaque for all others. This is analog to how the current ``Packet``
interface treats the data portion in a message_t. Consequently every
protocol has to provide a ``Metadata`` interface that returns a
fixed-sized offset into the packet_t metadata portion and just like
the Packet.getPayload() command the Metadata.getMetadata() command
would propagate through the entire protocol stack before it returns.
In its portion of the metadata buffer a component could to store
information associated with the packet (timestamp, RSSI, etc.) or even
temporary information about the component/packet state, etc. To make
metadata information accessible to other components a component would
provide metadata-specific interfaces (GetTimestamp, etc.).
Differences between packet_t and message_t from a User Perspective
--------------------------------------------------------------------
In contrast to message_t, with packet_t a protocol component allocates
a variable-sized header/footer inside the packet *after* the next
higher layer has passed it the packet on the send path (e.g. through
Send.send()). It will then populate its header/footer and eventually
pass it on to the next lower layer. In the sendDone() event handler it
MUST deallocate any previously allocated header/footer before it
propagates the sendDone() event further upwards. A protocol component
does not provide any packet accessor interfaces (like the current
``Packet`` interface). Instead, the interface for
allocating/deallocating memory inside a packet_t is provided by a T2
system library component, which also guarantees that the "start" and
"end" indices of the ring buffer are always correct. On the receive
path, before a component passes the packet_t to the next higher layer,
it MUST deallocate all of its headers/footers. The content of the
metadata buffer is not defined by the platform or radio driver, but by
the involved protocols components. A memory region inside the
metadata buffer is accessed exclusively by the component that has
reserved it and it is opaque for all others. The definition of
packet_t could be as follows:
typedef struct packet {
uint8_t start; // start of PDU, offset into ring buffer
uint8_t end; // end of PDU, offset into ring buffer
// the ring buffer memory, e.g. for 802.15.4 MAX_MPDU_SIZE is 127
uint8_t buffer[MAX_MPDU_SIZE];
// for every byte a component wants to reserve in the
// metadata buffer it would declare a unique(METADATA_BYTE)
uint8_t metadata[uniqueCount(METADATA_BYTE)];
} packet_t;
More information about the Tinyos-2.0wg
mailing list