[Tinyos Core WG] Meeting: September 27
Philip Levis
pal at cs.stanford.edu
Tue Sep 26 21:48:23 PDT 2006
Please note the different tel# and times; hope to return to standard
telecon service next week.
Wednesday, 9:30-10:30 AM US Pacific Time
USA: 1-888-830-6260
USA (international): +1 505 242 2420
Code: 200580
Agenda:
TEP references
CC2420 Low Power Listening
TEP 117 (attached)
TEP 103 (attached)
TEP 111 (attached)
-------------- next part --------------
==============================================
Permanent Data Storage (Flash)
==============================================
:TEP: 103
:Group: Core Working Group
:Type: Documentary
:Status: Draft
:TinyOS-Version: 2.x
:Author: David Gay, Jonathan Hui
:Draft-Created: 27-Sep-2004
:Draft-Version: $Revision: 1.1.2.14 $
:Draft-Modified: $Date: 2006/09/22 22:35:08 $
:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
.. Note::
This memo documents a part of TinyOS for the TinyOS Community, and
requests discussion and suggestions for improvements. Distribution
of this memo is unlimited. This memo is in full compliance with
TEP 1.
Abstract
====================================================================
This memo documents a set of hardware-independent interfaces to non-volatile
storage for TinyOS 2.x. It describes some design principles for the HPL and
HAL layers of various flash chips.
1. Introduction
====================================================================
Flash chips are a form of EEPROM (electrically-eraseable, programmable
read-only memory), distinguished by a fast erase capability. However,
erases can only be done in large units (from 256B to 128kB depending on the
flash chip). Erases are the only way to switch bits from 0 to 1, and
programming operations can only switch 1's to 0's. Additionally, some
chips require that programming only happen once between each erase,
or that it be in relatively large units (e.g., 256B).
In the table below, we summarise these differences by categorising
flash chips by their underlying technology (NOR vs NAND). We also
include a column for Atmel's AT45DB flash chip family, as it has
significantly different tradeoffs than other flash chips:
============= ================== ================= ===================
X NOR AT45DB NAND
(ex: ST M25P40, (ex: Samsung
Intel PXA27x) K9K1G08R0B)
============= ================== ================= ===================
Erase Slow (seconds) Fast (ms) Fast (ms)
Erase unit Large (64KB-128KB) Small (256B) Medium (8KB-32KB)
Writes Slow (100s kB/s) Slow (60kB/s) Fast (MBs/s)
Write unit 1 bit 256B 100's of bytes
Bit-errors Low Low High (requires ECC,
bad-block mapping)
Read Bus limited [*]_ Slow+Bus limited Bus limited
Erase cycles 10^4 - 10^5 10^4 [*]_ 10^5 - 10^7
Intended use Code storage Data storage Data storage
Energy/byte 1uJ 1uJ .01uJ
============= ================== ================= ===================
.. [*] M25P40 reads are limited by the use of a 25MHz SPI bus. The PXA27x flash
is memory mapped (reads are very fast and can directly execute code).
.. [*] Or infinite? Data sheet just says that every page within a sector
must be written every 10^4 writes within that sector
The energy/byte is the per-byte cost of erasing plus programming. It is
derived from the timing and power consumption of erase and write operations
(for NOR flash, values are for the STMicroelectronics M25P family, for NAND
flash, values are from the Samsung datasheet). Energy/byte for reads appears
to depend mostly on how long the read takes (the power consumptions are
comparable), i.e., on the efficiency of the bus + processor.
Early TinyOS platforms all used a flash chip from the AT45DB
family. In TinyOS 1.x, this chip could be accessed through three
different components:
- Using a low-level interface (``PageEEPROMC``) which gave direct
access to per-page read, write and erase operations.
- Using a high-level memory-like interface (``ByteEEPROMC``) with
read, write and logging operations.
- Using a simple file system (``Matchbox``) with sequential-only
files [1_].
Some more recent platforms use different flash chips: the ST M25P family (Telos
rev. B, eyes) and the Intel Strataflash (Intel Mote2). None of the
three components listed above are supported on these chips:
- The ``PageEEPROMC`` component is (and was intended to be) AT45DB-specific
- ``ByteEEPROMC`` allows arbitrary rewrites of sections of the flash.
This is not readily implementable on a flash chip with large erase units.
- The ``Matchbox`` implementation was AT45DB-specific. It was not
reimplemented for these other chips, in part because it does not
support some applications (e.g., network reprogramming) very well.
2. Storage in TinyOS 2.x
====================================================================
One approach to hiding the differences between different flash chips is to
provide a disk-like, block interface (with, e.g., 512B blocks). This is the
approach taken by compact flash cards. However, in the context of TinyOS,
this approach has several drawbacks:
- This approach is protected by patents, making it difficult to provide
in a free, open-source operating system.
- To support arbitrary block writes where blocks are smaller than the
erase unit, and to deal with the limited number of erase cycles/block
requires remapping blocks. We believe that maintaining this remapping
table is too expensive on many mote-class devices.
A second approach is to provide a generic low-level interface providing
operations (read, write, erase) corresponding to the basic flash
operations, along with information describing the flash chip's layout
(minimum write and erase unit, timing information, etc). However,
we believe that the large differences between NAND and NOR flash (see the
table above), in particular the differences in reliability, write and
erase units, make the design of a useful generic low-level interface
tricky at best.
We thus believe it is best, for now at least, to define high-level
storage abstractions that are useful for sensor network applications,
and leave their implementation up to each flash chip - such abstractions
will be necessary anyway. We leave open the possibility that a future
TEP may define portable lower-level flash interfaces (either for all
flash chips, or, e.g., for NOR-family flashes). Such low-level
interfaces would allow implementations of the storage abstractions
defined in this TEP to be used for multiple flash chips.
This TEP describes three high-level storage abstractions: large objects
written in a single session, small objects with arbitrary reads and
writes, and logs. TinyOS 2.x, divides flash chips into separate volumes
(with sizes fixed at compile-time). Each volume provides a single
storage abstraction (the abstraction defines the format).
We prefer the use of single abstractions over fixed-size volumes over
the use of a more general filing system (like Matchbox) for several
reasons:
- TinyOS is currently targeted at running a single application, and many
applications know their storage needs in advance: for instance, a
little space for configuration data, and everything else for a log of
all sampled data. In such cases, the flexibility offered by a filing
system (e.g., arbitrary numbers of files) is overkill,
- Each abstraction is relatively easy to implement on a new flash chip, and
has relatively little overhead.
- The problem of dealing with the limited number of erase cycles/block
is simplified: it is unlikely that user applications will need to
rewrite the same small object 100'000 times, or cycle 100'000 times
through their log. Thus the abstractions can mostly ignore the need for
"wear levelling" (ensuring that each block of the flash is erased
the same number of time, to maximise flash chip lifetime).
New abstractions (including a filing system...) can easily be added to
this framework.
The rest of this TEP covers some principles for the organisation of
flash chips (Section 3), then describes the flash volumes and
storage abstractions in detail (Section 4).
3. HPL/HAL/HIL Architecture
====================================================================
The flash chip architecture follows the three-layer Hardware
Abstraction Architecture (HAA), with each chip providing a presentation
layer (HPL, Section 3.1), adaptation layer (HAL, Section 3.2) and
platform-independent interface layer (HIL, Section 3.3) [2_].
The implementation of these layers SHOULD be found in the
``tos/chips/CHIPNAME`` directory. If a flash chip is part of a larger
family with a similar interface, the HAA SHOULD support all family members
by relying, e.g., on platform-provided configuration information.
Appendix A shows example HPL and HAL specifications for the AT45DB
and ST M25P chip families.
3.1 Hardware Presentation Layer (HPL)
--------------------------------------------------------------------
The flash HPL has a chip-dependent, platform-independent interface. The
implementation of this HPL is platform-dependent. The flash HPL SHOULD be
stateless.
To remain platform independent, a flash chip's HPL SHOULD connect to
platform-specific components
providing access to the flash chip; these components
SHOULD be placed in the ``tos/platforms/PLATFORM/chips/CHIPNAME``
directory. If the flash chip implementation supports a family of
flash chips, this directory MAY also contain a file describing the
particular flash chip found on the platform.
3.2 Hardware Adaptation Layer (HAL)
--------------------------------------------------------------------
The flash HAL has a chip-dependent, platform-independent interface and
implementation. Flash families with a common HPL SHOULD have a common
HAL. Flash HAL's SHOULD expose a ``Resource`` interface and automatically
power-manage the underlying flash chip. Finally, the flash HAL MUST
provide a way to access the volume information specified by the
programmer (see Section 3). This allows users to build new flash
abstractions that interact cleanly with the rest of the flash system.
3.3 Hardware Interface Layer (HIL)
--------------------------------------------------------------------
Each flash chip MUST support at least one of the storage abstractions
described in Section 4. These abstractions SHOULD be presented in
components named ``ChipAbstractionC``, e.g., ``At45dbLogStorageC``.
Additionally, a flash chip implementation MAY support platforms
with multiple instances of the same storage chip. The way in which
this is achieved is not specified further in this TEP.
Each platform MUST have ``AbstractionC`` components (e.g.,
``LogStorageC``) implementing the storage abstractions of Section 4
supported by its flash chip(s). On platforms with multiple storage chips
SHOULD redirect uses of ``AbstractionC`` to the appropriate storage
chip, based on the requested volume.
4. Non-Volatile Storage Abstractions
===================================================================
The HIL implementations are platform-independent, but chip (family)
dependent. They implement the three storage abstractions and
volume structure discussed in the introduction.
4.1. Volumes
-------------------------------------------------------------------
The division of the flash chip into fixed-size volumes is specified by
an XML file that is placed in the application's directory (where one
types 'make'). The XML file specifies the allocation as follows: ::
<volume_table>
<volume name="DELUGE0" size="65536" />
<volume name="CONFIGLOG" size="65536" />
<volume name="DATALOG" size="131072" />
<volume name="GOLDENIMAGE" size="65536" base="983040" />
</volume_table>
The name and size parameters are required, while base is optional. The name
is a string containing one or more characters in [a-zA-Z0-9\_], while size
and base are in bytes. Each storage chip MUST provide a compile-time tool
that translates the allocation specification to chip-specific nesC
code. There is no constraint on how this is done or what code is produced,
except that the specification to physical allocation MUST be one-to-one
(i.e. a given specification should always have the same resulting physical
allocation on a given chip) and the result MUST be placed in the build
directory. When not specified, the tool picks a suitable physical
location for a volume. If there is any reason that the physical allocation
cannot be satisfied, an error should be given at compile time. The tool
SHOULD be named ``tos-storage-CHIPNAME`` and be distributed with the other
tools supporting a platform. The XML file SHOULD be named
``volumes-CHIPNAME.xml``.
The compile-time tool MUST prepend 'VOLUME\_' to each volume name in
the XML file and '#define' each resulting name to map to a unique
integer.
The storage abstractions are accessed by instantiating generic
components that take the volume macro as argument: ::
components new BlockStorageC(VOLUME_DELUGE0);
If the named volume is not in the specification, nesC will give a
compile-time error since the symbol will be undefined.
A volume MUST NOT be used with more than one storage abstraction instance.
4.2 Large objects
------------------------------------------------------------------
The motivating example for large objects is the transmission or
long-term storage of large pieces of data. For instance, programs in a
network-reprogramming system, or large data-packets in a reliable
data-transmission system. Such objects have an interesting
characteristic: each byte in the object is written at most once.
This leads to the definition of the ``BlockStorageC`` abstraction for storing
large objects or other "write-once" objects:
- A large object ranges from a few kilobytes upwards.
- A large object is erased before the first write.
- A sync ensures that a large object survives a reboot or crash
- Reads are unrestricted
- Each byte can only be written once between two erases
Large objects are accessed by instantiating a BlockStorageC component
which takes a volume id argument: ::
generic configuration BlockStorageC(volume_id_t volid) {
provides {
interface BlockWrite;
interface BlockRead;
}
} ...
The ``BlockRead`` and ``BlockWrite`` interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase, except
``BlockRead.getSize``):
- ``BlockWrite.erase``: erase the volume. After a reboot or a commit, a
volume MUST be erased before it can be written to.
- ``BlockWrite.write``: write some bytes starting at a given
offset. Each byte MUST NOT be written more than once between two erases.
- ``BlockWrite.sync``: ensure all previous writes are present on a given
volume. Sync MUST be called to ensure written data survives a reboot
or crash.
- ``BlockRead.read``: read some bytes starting at a given offset.
- ``BlockRead.computeCrc``: compute the CRC of some bytes starting at a
given offset.
- ``BlockRead.getSize``: return bytes available for large object storage in
volume.
For full details on arguments and other considerations, see the comments in
the interface definitions.
Note that these interfaces contain no direct support for verifying the
integrity of the BlockStorage data, but such support can easily be built
bu using the ``computeCrc`` command and storing the result in a
well-defined location, and checking this CRC when desired.
4.3 Logging
------------------------------------------------------------------
Event and result logging is a common requirement in sensor
networks. Such logging should be reliable (a mote crash should not
lose data). It should also be easy to extract data from the log,
either partially or fully. Some logs are *linear* (stop logging when
the volume is full), others are *circular* (the oldest data is
overwritten when the volume is full).
The ``LogStorageC`` abstraction supports these requirements. The log is
record based: each call to ``LogWrite.append`` (see below) creates a new
record. On failure (crash or reboot), the log MUST only lose whole
records from the end of the log. Additionally, once a circular log wraps
around, calls to ``LogWrite.append`` MUST only lose whole records from
the beginning of the log.
Logs are accessed by instantiating a LogStorageC component which takes a
volume id and a boolean argument: ::
generic configuration LogStorageC(volume_id_t volid, bool circular) {
provides {
interface LogWrite;
interface LogRead;
}
} ...
If the ``circular`` argument is TRUE, the log is circular; otherwise
it is linear.
The ``LogRead`` and ``LogWrite`` interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase except
``LogWrite.currentOffset``, ``LogRead.currentOffset`` and
``LogRead.getSize``):
- ``LogWrite.erase``: erase the log. A log MUST be erased (possibly in
some previous session) before any other operation can be used.
- ``LogWrite.append``: append some bytes to the log. In a circular log,
this may overwrite the current read position. In this case, the
read position MUST be advanced to the log's current beginning
(i.e., as if ``LogRead.seek`` had been called with ``SEEK_BEGINNING``).
Additionally, the ``LogWrite.appendDone`` event reports whenever, in a
circular log, an append MAY have erased old records.
Each append creates a separate record. Log implementations may have a
maximum record size; all implementations MUST support records of up
to 255 bytes.
- ``LogWrite.sync``: guarantee that data written so far will not be lost to
a crash or reboot (it can still be overwritten when a circular log wraps
around). Using ``sync`` MAY waste some space in the log.
- ``LogWrite.currentOffset``: return cookie representing current
append position (for use with ``LogRead.seek``).
- ``LogRead.read``: read some bytes from the current read position in
the log and advance the read position.
``LogStorageC`` implementations MUST include error detection codes
to increase the likelihood of detection of corrupted or invalid log
data. Data returned by a successful read MUST have passed this
error detection check. The behaviour on failure of this check is
unspecified (e.g., the at45db believes as if the end of the log has
been reached; other implementations may behave differently).
- ``LogRead.currentOffset``: return cookie representing current
read position (for use with ``LogRead.seek``).
- ``LogRead.seek``: set the read position to a value returned by
a prior call to ``LogWrite.currentOffset`` or ``LogRead.currentOffset``,
or to the special ``SEEK_BEGINNING`` value. In a circular log, if
the specified position has been overwritten, behave as if
``SEEK_BEGINNING`` was requested.
``SEEK_BEGINNING`` positions the read position at the beginning of
the oldest record still present in the log.
After reboot, the current read position is ``SEEK_BEGINNING``.
- ``LogRead.getSize``: return an approximation of the log's capacity
in bytes. Uses of ``sync`` and other overhead may reduce this number.
For full details on arguments, etc, see the comments in the interface
definitions.
Note that while each call to ``append`` logically creates a separate
record, the ``LogStorageC`` API does not report record
boundaries. Additionally, crashes, reboots, and appends after
wrap-around in a circular log can cause the loss of multiple consecutive
records. Taken together, these restrictions mean that a ``LogStorageC``
implementation MAY internally aggregate several consecutive appends into
a single record. However, the guarantee that only whole records are lost
is sufficient to ensure that applications do not to have worry about
incomplete or inconsistent log entries.
4.4 Small objects:
------------------------------------------------------------------
Sensor network applications need to store configuration data, e.g.,
mote identity, radio frequency, sample rates, etc. Such data is not large, but
losing it may lead to a mote misbehaving or losing contact with the
network.
The ``ConfigStorageC`` abstraction stores a single small object in a volume. It:
- Assumes that configuration data is relatively small (a few
hundred bytes).
- Allows random reads and writes.
- Has simple transactional behaviour: each read is a separate transaction,
all writes up to a commit form a single transaction.
- At reboot, the volume contains the data as of the most recent successful
commit.
Small objects are accessed by instantiating a ConfigStorageC component
which takes a volume id argument: ::
generic configuration ConfigStorageC(volume_id_t volid) {
provides {
interface Mount;
interface ConfigStorage;
}
} ...
A small object MUST be mounted (via the ``Mount`` interface) before
the first use.
The ``Mount`` and ``ConfigStorage`` interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase except
``ConfigStorage.getSize`` and ``ConfigStorage.valid``):
- ``Mount.mount``: mount the volume.
- ``ConfigStorage.valid``: return TRUE if the volume contains a
valid small object.
- ``ConfigStorage.read``: read some bytes starting at a given offset.
Fails if the small object is not valid. Note that this reads the
data as of the last successful commit.
- ``ConfigStorage.write``: write some bytes to a given offset.
- ``ConfigStorage.commit``: make the small object contents reflect all the
writes since the last commit.
- ``ConfigStorage.getSize``: return the number of bytes that can be stored
in the small object.
For full details on arguments, etc, see the comments in the interface
definitions.
5. Implementations
====================================================================
An AT45DB implementation can be found in tinyos-2.x/tos/chips/at45db.
An ST M25P implementation can be found in tinyos-2.x/tos/chips/stm25p.
6. Authors' Addresses
====================================================================
| David Gay
| 2150 Shattuck Ave, Suite 1300
| Intel Research
| Berkeley, CA 94704
|
| phone - +1 510 495 3055
| email - david.e.gay at intel.com
|
|
| Jonathan Hui
| 657 Mission St. Ste. 600
| Arched Rock Corporation
| San Francisco, CA 94105-4120
|
| phone - +1 415 692 0828
| email - jhui at archedrock.com
7. Citations
====================================================================
.. [1] David Gay. "Design of Matchbox, the simple filing system for
motes. (version 1.0)."
.. [2] TEP 2: Hardware Abstraction Architecture.
Appendix A. HAA for some existing flash chips
====================================================================
A.1 AT45DB
------------------------------------------------------------------
The Atmel AT45DB family HPL is: ::
configuration HplAt45dbC {
provides interface HplAt45db;
} ...
The ``HplAt45db`` interface has flash->buffer, buffer->flash, compare
buffer to flash, erase page, read, compute CRC, and write operations. Most
of these operations are asynchronous, i.e., their completion is signaled
before the flash chip has completed the operation. The HPL also includes
operations to wait for asynchronous operations to complete.
A generic, system-independent implementation of the HPL
(``HplAt45dbByteC``) is included allowing platforms to just provide SPI and
chip selection interfaces.
Different members of the AT45DB family are supported by specifying a few
constants (number of pages, page size).
The AT45DB HAL has two components, one for chip access and the other
providing volume information: ::
component At45dbC
{
provides {
interface At45db;
interface Resource[uint8_t client];
interface ResourceController;
interface ArbiterInfo;
}
} ...
configuration At45dbStorageManagerC {
provides interface At45dbVolume[volume_id_t volid];
} ...
Note that the AT45DB HAL resource management is independent of the
underlying HPL's power management. The motivation for this is that
individual flash operations may take a long time, so it may be desirable to
release the flash's bus during long-running operations.
The ``At45db`` interface abstracts from the low-level HPL operations by:
- using the flash's 2 RAM buffers as a cache to allow faster reads and
writes
- hiding the asynchronous nature of the HPL operations
- verifying that all writes were successful
It provides cached read, write and CRC computation, and page erase and
copy. It also includes flush and sync operations to manage the cache.
The ``At45dbVolume`` interface has operations to report volume size and
map volume-relative pages to absolute pages.
A.2 ST M25P
------------------------------------------------------------------
The ST M25P family HPL is: ::
configuration Stm25pSpiC {
provides interface Init;
provides interface Resource;
provides interface Stm25pSpi;
}
The ``Stm25pSpi`` interface has read, write, compute CRC, sector erase
and block erase operations. The implementation of this HPL is
system-independent, built over a few system-dependent components
providing SPI and chip selection interfaces.
Note that these two examples have different resource management policies:
the AT45DB encapsulates resource acquisition and release within each
operation, while the M25P family requires that HPL users acquire and
release the resource itself.
The ST M25P HAL is: ::
configuration Stm25pSectorC {
provides interface Resource as ClientResource[storage_volume_t volume];
provides interface Stm25pSector as Sector[storage_volume_t volume];
provides interface Stm25pVolume as Volume[storage_volume_t volume];
}
The ``Stm25pSector`` interface provides volume-relative operations similar
to those from the HPL interface: read, write, compute CRC and
erase. Additionally, it has operations to report volume size and remap
volume-relative addresses. Clients of the ST M25P HAL must implement the
``getVolumeId`` event of the ``Stm25pVolume`` interface so that the HAL can
obtain the volume id of each of its clients.
Appendix B. Storage interfaces
====================================================================
These interfaces are presented briefly here for reference; please refer
to the TinyOS documentation for a full description of the commands,
events and their parameters.
B.1 BlockStorage interfaces
------------------------------------------------------------------
The BlockStorage interfaces are: ::
interface BlockRead {
command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
error_t error);
command error_t computeCrc(storage_addr_t addr, storage_len_t len,
uint16_t crc);
event void computeCrcDone(storage_addr_t addr, storage_len_t len,
uint16_t crc, error_t error);
command storage_len_t getSize();
}
interface BlockWrite {
command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
error_t error);
command error_t erase();
event void eraseDone(error_t error);
command error_t sync();
event void syncDone(error_t error);
}
B.2 ConfigStorage interfaces
------------------------------------------------------------------
The ConfigStorage interfaces are: ::
interface Mount {
command error_t mount();
event void mountDone(error_t error);
}
interface ConfigStorage {
command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
error_t error);
command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
error_t error);
command error_t commit();
event void commitDone(error_t error);
command storage_len_t getSize();
command bool valid();
}
B.3 LogStorage interfaces
------------------------------------------------------------------
The LogStorage interfaces are: ::
interface LogRead {
command error_t read(void* buf, storage_len_t len);
event void readDone(void* buf, storage_len_t len, error_t error);
command storage_cookie_t currentOffset();
command error_t seek(storage_cookie_t offset);
event void seekDone(error_t error);
command storage_len_t getSize();
}
interface LogWrite {
command error_t append(void* buf, storage_len_t len);
event void appendDone(void* buf, storage_len_t len, bool recordsLost,
error_t error);
command storage_cookie_t currentOffset();
command error_t erase();
event void eraseDone(error_t error);
command error_t sync();
event void syncDone(error_t error);
}
-------------- next part --------------
============================
message_t
============================
:TEP: 111
:Group: Core Working Group
:Type: Documentary
:Status: Draft
:TinyOS-Version: 2.x
:Author: Philip Levis
:Draft-Created: 11-Jul-2005
:Draft-Version: $Revision: 1.1.2.12 $
:Draft-Modified: $Date: 2006/06/13 16:44:17 $
:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
.. Note::
This memo documents a part of TinyOS for the TinyOS Community, and
requests discussion and suggestions for improvements. Distribution
of this memo is unlimited. This memo is in full compliance with
TEP 1.
Abstract
====================================================================
This memo covers the TinyOS 2.x message buffer abstraction, ``message_t``.
It describes the message buffer design considerations, how and where
``message_t`` is specified, and how data link layers should access it.
1. Introduction
====================================================================
In TinyOS 1.x, a message buffer is a ``TOS_Msg``. A buffer contains an
active message (AM) packet as well as packet metadata, such as timestamps,
acknowledgement bits, and signal strength if the packet was received.
``TOS_Msg`` is a fixed size structure whose size is defined by the maximum
AM payload length (the default is 29 bytes). Fixed sized buffers allows
TinyOS 1.x to have zero-copy semantics: when a component receives a
buffer, rather than copy out the contents it can return a pointer
to a new buffer for the underlying layer to use for the next received
packet.
One issue that arises is what defines the ``TOS_Msg`` structure, as different
link layers may require different layouts. For example, 802.15.4 radio
hardware (such as the CC2420, used in the Telos and micaZ platforms)
may require 802.15.4 headers, while a software stack built on top of
byte radios (such as the CC1000, used in the mica2 platform) can specify
its own packet format. This means that ``TOS_Msg`` may be different on
different platforms.
The solution to this problem in TinyOS 1.x is for there to be a standard
definition of ``TOS_Msg``, which a platform (e.g., the micaZ) can
redefine to match its radio. For example, a mica2 mote uses the standard
definition, which is::
typedef struct TOS_Msg {
// The following fields are transmitted/received on the radio.
uint16_t addr;
uint8_t type;
uint8_t group;
uint8_t length;
int8_t data[TOSH_DATA_LENGTH];
uint16_t crc;
// The following fields are not actually transmitted or received
// on the radio! They are used for internal accounting only.
// The reason they are in this structure is that the AM interface
// requires them to be part of the TOS_Msg that is passed to
// send/receive operations.
uint16_t strength;
uint8_t ack;
uint16_t time;
uint8_t sendSecurityMode;
uint8_t receiveSecurityMode;
} TOS_Msg;
while on a mote with a CC420 radio (e.g., micaZ), ``TOS_Msg`` is defined as::
typedef struct TOS_Msg {
// The following fields are transmitted/received on the radio.
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];
// The following fields are not actually transmitted or received
// on the radio! They are used for internal accounting only.
// The reason they are in this structure is that the AM interface
// requires them to be part of the TOS_Msg that is passed to
// send/receive operations.
uint8_t strength;
uint8_t lqi;
bool crc;
uint8_t ack;
uint16_t time;
} TOS_Msg;
There are two basic problems with this approach. First, exposing all of
the link layer fields leads components to directly access the packet
structure. This introduces dependencies between higher level components
and the structure layout. For example, many network services built on
top of data link layers care whether sent packets are acknowledged. They
therefore check the ``ack`` field of ``TOS_Msg``. If a link layer does not
provide acknowledgements, it must still include the ``ack`` field
and always set it to 0, wasting a byte of RAM per buffer.
Second, this model does not easily support multiple data link layers.
Radio chip implementations assume that the fields they require are
defined in the structure and directly access them. If a platform
has two different link layers (e.g., a CC1000 *and* a CC2420 radio),
then a ``TOS_Msg`` needs to allocate the right amount of space for both
of their headers while allowing implementations to directly access
header fields. This is very difficult to do in C.
The ``data`` payload is especially problematic. Many
components refer to this field, so it must be at a fixed offset.
Depending on the underlying link layer, the header fields
preceding it might have different lengths, and packet-level radios
often require packets to be contiguous memory regions. Overall, these
complexities make specifying the format of ``TOS_Msg`` very difficult.
2. message_t
====================================================================
In TinyOS 2.x, the standard message buffer is ``message_t``. The
message_t structure is defined in ``tos/types/message.h``::
typedef nx_struct message_t {
nx_uint8_t header[sizeof(message_header_t)];
nx_uint8_t data[TOSH_DATA_LENGTH];
nx_uint8_t footer[sizeof(message_footer_t)];
nx_uint8_t metadata[sizeof(message_metadata_t)];
} message_t;
This format keeps data at a fixed offset, which is important when
passing a message buffer between two different link layers. If the
data payload were at different offsets for different link layers, then
passing a packet between two link layers would require a ``memmove(3)``
operation (essentially, a copy).
The header, footer, and metadata formats are all opaque. Source code
cannot access fields directly. Instead, data-link layers provide access
to fields through nesC interfaces. Section 3 discusses this in
greater depth.
Every link layer defines its header, footer, and metadata
structures. These structures MUST be external structs (``nx_struct``),
and all of their fields MUST be external types (``nx_*``), for two
reasons. First, external types ensure cross-platform compatibility.
Second, it forces structures to be aligned on byte boundaries,
circumventing issues with the
alignment of packet buffers and field offsets within them.
For example, the CC1000 radio implementation defines
its structures in ``CC1000Msg.h``::
typedef nx_struct cc1000_header {
nx_am_addr_t addr;
nx_uint8_t length;
nx_am_group_t group;
nx_am_id_t type;
} cc1000_header_t;
typedef nx_struct cc1000_footer {
nxle_uint16_t crc;
} cc1000_footer_t;
typedef nx_struct cc1000_metadata {
nx_uint16_t strength;
nx_uint8_t ack;
nx_uint16_t time;
nx_uint8_t sendSecurityMode;
nx_uint8_t receiveSecurityMode;
} cc1000_metadata_t;
Each link layer defines its structures, but a **platform** is
responsible for defining ``message_header_t``, ``message_footer_t``,
and ``message_metadata_t``. This is because a platform may have
multiple link layers, and so only it can resolve which structures are
needed. These definitions MUST be in a file in a platform directory
named ``platform_message.h``. The mica2 platform, for example, has
two data link layers: the CC1000 radio and the TinyOS serial
stack [1]_. The serial packet format does not have a footer
or metadata section. The ``platform_message.h`` of the mica2
looks like this::
typedef union message_header {
cc1000_header_t cc1k;
serial_header_t serial;
} message_header_t;
typedef union message_footer {
cc1000_footer_t cc1k;
} message_footer_t;
typedef union message_metadata {
cc1000_metadata cc1k;
} message_metadata_t;
For a more complex example, consider a fictional platform named
'megamica' that has both a CC1000 and a CC2420 radio. Its
``platform_message.h`` would look like this::
typedef union mega_mica_header {
cc1000_header_t cc1k;
cc2420_header_t cc2420;
serial_header_t serial;
} message_header_t;
typedef union mega_mica_footer {
cc1000_footer_t cc1k;
cc2420_footer_t cc2420;
} message_footer_t;
typedef union mega_mica_metadata {
cc1000_metadata_t cc1k;
cc2420_metadata_t cc2420;
} message__metadata_t;
If a platform has more than one link layer, it SHOULD define each of the
message_t fields to be a union of the underlying link layer structures.
This ensures that enough space is allocated for all underlying link layers.
3. The message_t fields
====================================================================
TinyOS 2.x components treat packets as abstract data types (ADTs),
rather than C structures, obtaining all of the traditional benefits
of this approach. First and foremost, clients of a packet layer
do not depend on particular field names or locations, allowing the
implementations to choose packet formats and make a variety of
optimizations.
Components above the basic data-link layer MUST always access
packet fields through interfaces. A component that introduces
new packet fields SHOULD provide an interface to those that
are of interest to other components.
For example, active messages have an interface named ``AMPacket``
which provides access commands to AM fields. In TinyOS 1.x, a
component would directly access ``TOS_Msg.addr``; in TinyOS 2.x,
a component calls ``AMPacket.getAddress(msg)``.
The most basic of these interfaces is Packet, which provides
access to a packet payload. TEP 116 describes common TinyOS
packet ADT interfaces [2]_.
Link layer components MAY access packet fields differently than other
components, as they are aware of the actual packet format. They can
therefore implement the interfaces that provide access to the fields
for other components.
3.1 Headers
----------------------------------------------------------------
The message_t header field is an array of bytes whose size is
the size of a platform's union of data-link headers.
Because packets are stored contiguously, the layout of a packet
in memory is not the same as the layout of its nesC structure.
A packet header does not necessarily start at the beginning of
the message_t. For example, consider the Telos platform::
typedef union message_header {
cc2420_header_t cc2420;
serial_header_t serial;
} message_header_t;
The CC2420 header is 11 bytes long, while the serial header is
5 bytes long. The serial header ends at the beginning of the
data payload, and so six padding bytes precede it. This figure
shows the layout of message_t, a 12-byte CC2420 packet, and
a 12-byte serial packet on the Telos platform::
11 bytes TOSH_DATA_LENGTH 7 bytes
+-----------+-----------------------------+-------+
message_t | header | data | meta |
+-----------+-----------------------------+-------+
+-----------+------------+ +-------+
CC2420 | header | data | | meta |
+-----------+------------+ +-------+
+-----+------------+
Serial | hdr | data |
+-----+------------+
Neither the CC2420 nor the serial stack has packet footers, and
the serial stack does not have any metadata.
The packet for a link layer does not necessarily start at the beginning
of the message_t. Instead, it starts at a negative offset from the
data field. When a link layer component needs to read or write protocol
header fields, it MUST compute the location of the header as a negative
offset from the data field. For example, the serial stack header has
active message fields, such as the AM type. The command that returns
the AM type, ``AMPacket.type()``, looks like this::
serial_header_t* getHeader(message_t* msg) {
return (serial_header_t*)(msg->data - sizeof(serial_header_t));
}
command am_id_t AMPacket.type(message_t* msg) {
serial_header_t* hdr = getheader(msg);
return hdr->type;
}
Because calculating the negative offset is a little bit unwieldy, the
serial stack uses the internal helper function getHeader(). Many
single-hop stacks follow this approach, as it is very likely
that nesC will inline the function, eliminating the possible overhead.
In most cases, the C compiler also compiles the call into a simple
memory offset load.
The following code is incorrect, as it directly casts the header field.
It is an example of what components MUST NOT do::
serial_header_t* getHeader(message_t* msg) {
return (serial_header_t*)(msg->header);
}
In the case of Telos, for example, this would result in a packet
layout that looks like this::
11 bytes TOSH_DATA_LENGTH 7 bytes
+-----------+-----------------------------+-------+
message_t | header | data | meta |
+-----------+-----------------------------+-------+
+-----+ +------------+
Serial | hdr | | data |
+-----+ +------------+
3.2 Data
----------------------------------------------------------------
The data field of message_t stores the single-hop packet payload.
It is TOSH_DATA_LENGTH bytes long. The default size is 28 bytes.
A TinyOS application can redefine TOSH_DATA_LENGTH at compile time
with a command-line option to ncc: ``-DTOSH_DATA_LENGTH=x``.
Because this value can be reconfigured, it is possible that two
different versions of an application can have different MTU sizes.
If a packet layer receives a packet whose payload size is
longer than TOSH_DATA_LENGTH, it MUST discard the packet.
3.3 Footer
----------------------------------------------------------------
The message_footer_t field ensures that message_t has enough space to
store the footers for all underlying link layers when there are
MTU-sized packets. Like headers, footers are not necessarily stored
where the C structs indicate they are: instead, their placement is
implementation dependent. A single-hop layer MAY store the footer
contiguously with the data region. For short packets, this can mean
that the footer will actually be stored in the data field.
3.4 Metadata
----------------------------------------------------------------
The metadata field of message_t stores data that
a single-hop stack uses or collects does not transmit.
This mechanism allows packet layers to store per-packet
information such as RSSI or timestamps. For example, this is
the CC2420 metadata structure::
typedef nx_struct cc2420_metadata_t {
nx_uint8_t tx_power;
nx_uint8_t rssi;
nx_uint8_t lqi;
nx_bool crc;
nx_bool ack;
nx_uint16_t time;
} cc2420_metadata_t;
5. Implementation
====================================================================
The definition of message_t can be found in
``tinyos-2.x/tos/types/message.h``. The definition of the CC2420
message format can be found in ``tinyos-2.x/tos/chips/cc2420/CC2420.h``.
The defintion of the CC1000 message format can be found in
``tinyos-2.x/tos/chips/cc1000/CC1000Msg.h``. The definition
of the standard serial stack packet format can be found in
``tinyos-2.x/tos/lib/serial/Serial.h''. The definition of
the telosb packet format can be found in
``tinyos-2.x/tos/platform/telosa/platform_message.h`` and the micaz format can be found in
``tinyos-2.x/tos/platforms/micaz/platform_message.h``.
6. Author's Address
====================================================================
| Philip Levis
| 358 Gates Hall
| Computer Science Laboratory
| Stanford University
| Stanford, CA 94305
|
| phone - +1 650 725 9046
| email - pal at cs.stanford.edu
6. Citations
====================================================================
.. [1] TEP 113: Serial Communication.
.. [2] TEP 116: Packet Protocols.
-------------- next part --------------
============================
Pins and Buses
============================
:TEP: 117
:Group: Core Working Group
:Type: Documentary
:Status: Draft
:TinyOS-Version: 2.x
:Author: Phil Buonadonna
:Draft-Created: 23-Jan-2006
:Draft-Version: $Revision: 1.1.2.5 $
:Draft-Modified: $Date: 2006/09/26 21:46:16 $
:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
.. Note::
This memo documents a part of TinyOS for the TinyOS Community, and
requests discussion and suggestions for improvements. Distribution
of this memo is unlimited. This memo is in full compliance with
TEP 1.
Abstract
====================================================================
The memo documents the TinyOS 2.x interfaces used for controlling
digital IO functionality and digital interfaces other than serial
communication covered in [tep113].
1. Introduction
====================================================================
The canonical TinyOS device is likely to have a variety of digital
interfaces. These interfaces may be divided into two broad
categories. The first are general purpose digital I/O lines (pins)
for individual digital signals at physical pins on a chip or
platform. The second are digital I/O interfaces that have predefined
communication protocol formats. The two buses covered in this
document are the Serial Peripheral Interface (SPI) and the
Inter-Integrated Circuit (I2c) or Two-Wire interface. While there are
likely other bus formats, we presume SPI and I2C to have the largest
coverage. While the UART interface is also in this category, it is
covered separately in [tep113].
This memo documents the interfaces used for pins and the two buses.
2. Pins
====================================================================
General Purpose I/O (GPIO) pins are single, versatile digital I/O signals
individually controllable on a particular chip or platform. Each GPIO
can be placed into either an input mode or an output mode. On
some platforms a third 'tri-state' mode may exist, but this
functionality is platform specific and will not be covered in this
document.
On many platforms, a physical pin may function as either a digital GPIO
or another special function I/O such. Examples include ADC I/O or a bus
I/O. Interfaces to configure the specific function of a pin are
platform specific.
The objective of the interfaces described here is not to attempt to
cover all possibilities of GPIO functionality and features, but to
distill down to a basis that may be expected on most platforms.
In input mode, we assume the following capabilities:
* The ability to arbitrarily sample the pin
* The ability to generate an interrupt/event from either a rising edge or falling edge digital signal.
In output mode, we assume the following capabilities:
* An I/O may be individually cleared (low) or set (hi)
Platform that provide GPIO capabilities MUST provide the following HIL
interfaces:
* GeneralIO
* GpioInterrupt
Platforms MAY provide the following capture interface.
* GpioCapture
2.1 GeneralIO
--------------------------------------------------------------------
The GeneralIO HIL interface is the fundamental mechanism for controlling a
GPIO pin. The interface provides a mechanism for setting the pin mode
and reading/setting the pin value. The toggle function switches the
output state to the opposite of what it currently is.
Platforms with GPIO functionality MUST provide this interface. It
SHOULD be provided in a component named GeneralIOC, but MAY be
provided in other components as needed. ::
interface GeneralIO
{
async command void set();
async command void clr();
async command void toggle();
async command bool get();
async command void makeInput();
async command void makeOutput();
}
2.2 GpioInterrupt
--------------------------------------------------------------------
The GPIO Interrupt HIL interface provides baseline event control for a
GPIO pin. It provides a mechanism to detect a rising edge OR a falling
edge. Note that calls to enableRisingEdge and enableFallingEdge are
NOT cumulative and only one edge may be detected at a time. There may
be other edge events supported by the platform which MAY be exported
through a platform specific HAL interface. ::
interface GpioInterrupt {
async command error_t enableRisingEdge();
async command error_t enableFallingEdge();
async command error_t disable();
async event void fired();
}
2.3 GpioCapture
--------------------------------------------------------------------
The GpioCapture interface provides a means of associating a timestamp
with a GPIO event. Platforms MAY provide this interface.
Some platforms may have hardware support for such a feature. Other
platforms may emulate this capability using the SoftCaptureC
component. The interface makes not declaration of the precision or
accuracy of the timestamp with respect to the associated GPIO event. ::
interface GpioCapture {
async command error_t captureRisingEdge();
async command error_t captureFallingEdge();
async event void captured(uint16_t time);
async command void disable();
}
3. Buses
====================================================================
Bus operations may be divided into two categories: data and
control. The control operations of a particular bus controller are
platform specific and not covered here. Instead, we focus on the data
interfaces at the HIL level that are expected to be provided.
3.1 Serial Peripheral Interface
--------------------------------------------------------------------
The Serial Peripheral Interface (SPI) is part of a larger class of
Synchronous Serial Protocols. The term SPI typically refers to the
Motorola SPI protocols. Other protocols include the National
Semiconductor Microwire, the TI Synchronous Serial Protocol and the
Programmable Serial Protocol. The dataside interfaces here were
developed for the Motorola SPI format, but may work for others.
Platforms supporting SPI MUST provide these interfaces.
Of note, the interfaces DO NOT define the behavior of any chip select
or framing signals. These SHOULD determined by platform specific HAL
interfaces and implementations.
The interface is split into a synchronous byte level and an
asynchronous packet level interface. The byte level interface is
intended for short transactions (3-4 bytes) on the SPI bus. ::
interface SPIByte {
async command void write( uint8_t tx, uint8_t* rx );
}
The packet level interface is for larger bus transactions. The
pointer/length interface permits use of hardware assist such as DMA. ::
interface SPIPacket {
async command error_t send( uint8_t* txBuf, uint8_t* rxBuf, uint16_t len );
async event void sendDone( uint8_t* txBuf, uint8_t* rxBuf, uint16_t len,
error_t error );
}
3.2 I2C
--------------------------------------------------------------------
The Inter-Integrated Circuit (I2C) interface is another type of
digital bus that is often used for chip-to-chip communication. It is
also known as a two-wire interface.
The I2CPacket interface provides for asynchronous Master mode
communication on an I2C with application framed packets. Individual
I2C START-STOP events are controllable which allows the using
component to do multiple calls within a single I2C transaction and
permits multiple START sequences
Platforms providing I2C capability MUST provide this interface. ::
interface I2CPacket<addr_size> {
async command error_t read(i2c_flags_t flags, uint16_t _addr, uint8_t _length, uint8_t* _data);
async command error_t write(i2c_flags_t flags, uint16_t _addr, uint8_t _length, uint8_t* _data);
async event void readDone(error_t error, uint16_t addr, uint8_t length, uint8_t* data);
async event void writeDone(error_t error, uint8_t length, uint8_t* data);
}
The interface is typed according to the addressing space the underlying implementation supports.
Valid type values are below. ::
TI2CExtdAddr - Interfaces uses the extended (10-bit) addressing mode.
TI2CBasicAddr - Interfaces uses the basic (7-bit) addressing mode.
The i2c_flags_t values are defined below. The flags define the behavior of the operation for
the call being made. These values may be ORed together. ::
I2C_START - Transmit an I2C STOP at the beginning of the operation.
I2C_STOP - Transmit an I2C STOP at the end of the operation. Cannot be used
with the I2C_ACK_END flag.
I2C_ACK_END - ACK the last byte sent from the buffer. This flags is only valid
a write operation. Cannot be used with the I2C_STOP flag.
4. Author's Address
====================================================================
| Phil Buonadonna
| Arch Rock Corporation
| 657 Mission St. Ste 600
| San Francisco, CA 94105-4120
|
| phone - +1 415 692-0828 x2833
5. Citations
====================================================================
.. [tep113] TEP 113: Serial Communication.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.millennium.berkeley.edu/pipermail/tinyos-2.0wg/attachments/20060926/05d3cb15/tep103-0001.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.millennium.berkeley.edu/pipermail/tinyos-2.0wg/attachments/20060926/05d3cb15/tep111-0001.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.millennium.berkeley.edu/pipermail/tinyos-2.0wg/attachments/20060926/05d3cb15/tep117-0001.html
-------------- next part --------------
Phil
More information about the Tinyos-2.0wg
mailing list