tep103.txt

tinyos-2.x.rar

==============================================
Permanent Data Storage (Flash)
==============================================

:TEP: 103
:Group: Core Working Group
:Type: Documentary
:Status: Final
:TinyOS-Version: 2.x
:Author: David Gay, Jonathan Hui

.. 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-erasable, 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
by 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;
    }
  } ...