[Tinyos Core WG] Meeting: September 27
Jonathan Hui
jhui at archrock.com
Tue Sep 26 21:54:29 PDT 2006
Updated TEP117.
- added UART
- updated interfaces to match tinyos-2.x (though SpiByte still returns
error_t in the code).
- added isInput() to GeneralIO.
Is there something else that we agreed to update before looking at it again?
--
Jonathan Hui
jhui at archrock.com
Philip Levis wrote:
> 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)
>
>
> ------------------------------------------------------------------------
>
> ==============================================
> 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);
> }
>
>
> ------------------------------------------------------------------------
>
> ============================
> 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.
>
>
>
>
> ------------------------------------------------------------------------
>
> ============================
> 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.
>
>
> ------------------------------------------------------------------------
>
>
> 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: 1.1.2.14
> Draft-Modified: 2006-09-22
> 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 (ex: ST M25P40, Intel PXA27x) AT45DB
>
> NAND
> (ex: Samsung 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 [*] <#id3> Slow+Bus limited Bus limited
> Erase cycles 10^4 - 10^5 10^4 [†] <#id4> 10^5 - 10^7
> Intended use Code storage Data storage Data storage
> Energy/byte 1uJ 1uJ .01uJ
>
> [*] <#id1> 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).
>
> [†] <#id2> 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 <#id5>].
>
> 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 <#id6>]. 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 <mailto: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 <mailto: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);
> }
>
>
> ------------------------------------------------------------------------
>
>
> 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: 1.1.2.12
> Draft-Modified: 2006-06-13
> 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] <#id4>. 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] <#id5>.
>
> 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 <mailto:pal at cs.stanford.edu>
>
>
> 6. Citations
>
> [1] <#id2> TEP 113: Serial Communication.
>
> [2] <#id3> TEP 116: Packet Protocols.
>
>
> ------------------------------------------------------------------------
>
>
> 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: 1.1.2.5
> Draft-Modified: 2006-09-26
> 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.