tep129.txt

tinyos-2.x.rar

======================================================
Basic Platform Independent Non-Volatile Storage Layers
======================================================

:TEP: 129
:Group: Storage Working Group 
:Type: Documentary
:Status: DRAFT
:TinyOS-Version: 2.x
:Authors: David Moss, Junzhao Du, Prabal Dutta, Deepak Ganesan,
          Kevin Klues, Manju, Ajay Martin, and Gaurav Mathur

.. 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 storage abstractions proposed by TEP 103 are implemented on a
platform-dependent basis.  A version of BlockStorage, ConfigStorage,
and LogStorage were created from the ground up for both the
AT45DB and ST M25P80 flash chips.  Looking forward into the further 
growth and development of hardware, rebuilding each of these storage 
layers for every new flash chip will be time consuming and cause
compatibility issues.

We propose versions of BlockStorage, ConfigStorage, and LogStorage
be built on top of a platform-independent interface.  This would 
allow one version of each to exist on multiple platforms. 
Platform-independent implementation concepts are discussed
along with recommended solutions, and changes are proposed to the
interfaces defined by TEP 103.

1. Introduction
====================================================================

The implementations of the BlockStorage, ConfigStorage, and LogStorage
layers described in TEP 103 [1]_ are platform-dependent.  Platform-
dependent implementations can cause behavioral and usage differences
as well as compiling problems when attempting to port an application 
written on one platform to another.  

Building upon the DirectStorage, DirectModify, and VolumeSettings
abstraction layers defined in TEP128 [2]_, the three basic storage
solutions can be implemented in a platform-independent manner.
This requires combining all properties of various memory types, 
which aids in the creation of platform-independent storage solutions.
Behavioral differences are minimized, and applications using 
the platform-independent storage layers can expect to work the
same way on different types of non-volatile memory.


2. Implementing a platform-independent BlockStorage
====================================================================

The DirectStorage interface initially stemmed from the BlockStorage 
interface with differences in interfaces, organization, and
erase behavior, as well as the additional VolumeSettings interface.  
To implement BlockStorage on DirectStorage, the erase behavior must 
be extended to erase the entire volume instead of an individual erase unit.  

VolumeSettings can first be accessed to determine the total number of erase
units in the currently mounted volume.  Looping through these erase units,
DirectStorage is accessed to erase() each one.  At the end of the erase
operation, the entire volume is set back to fill bytes (0xFF).


2.1 Improved BlockStorage interface
--------------------------------------------------------------------
Previous BlockStorage interfaces were divided into BlockRead and
BlockWrite.  This was found to be cumbersome because applications
typically required access to both interfaces.  The getSize() is
unnecessary due to the addition of the VolumeSettings interface.
All other BlockStorage commands can simply pass through to their
respective DirectStorage functions. This TEP proposes the following 
unified BlockStorage interface:::

  interface BlockStorage {
  
    command error_t read(uint32_t addr, void *buf, uint32_t len);
    
    command error_t write(uint32_t addr, void *buf, uint32_t len);
    
    command error_t erase();
    
    command error_t flush();
    
    command error_t crc(uint32_t addr, uint32_t len, uint16_t baseCrc);
    
    
  
    event void readDone(uint32_t addr, void *buf, uint32_t len, error_t error);
    
    event void writeDone(uint32_t addr, void *buf, uint32_t len, error_t error);  
    
    event void eraseDone(error_t error);
    
    event void flushDone(error_t error);
    
    event void crcDone(uint16_t calculatedCrc, uint32_t addr, uint32_t len, error_t error);
  
  }


``read(uint32_t addr, void *buf, uint32_t len);``
 - Read 'len' bytes into ``*buf`` from the given address
 - Returns FAIL if the request cannot be handled
 - Signals readDone(...) when complete.

``write(uint32_t addr, void *buf, uint32_t len);``
 - Write 'len' bytes from ``*buf`` starting at the given address
 - Returns FAIL if the request cannot be handled
 - Signals writeDone(...) when complete.

erase();
 - Erase the entire volume
 - Returns FAIL if the request cannot be handled
 - Signals eraseDone(...) when complete.

flush()
 - All data that has been previously written and is not yet located on 
   non-volatile memory should be immediately stored to non-volatile memory.
 - Returns FAIL if the operation cannot be completed at this time
 - Signals flushDone(...) when complete.

crc(uint32_t addr, uint32_t len, uint16_t baseCrc);
 - Calculate the CRC of 'len' bytes starting at the given address, using
   the given baseCrc as a seed.
 - Returns FAIL if the request cannot be handled
 - Signals crcDone(...) when complete.



3. Implementing a platform-independent LogStorage
====================================================================

As described in TEP 103, logging can be implemented using two 
different methods: linear and circular.  A linear log fills up
its volume and stops when it comes to the end.  A circular log allows
at least half of its volume to remain valid while continuing to write
the other half.  As previously described, this requires at least
two erase units to be effective.

Both logging behaviors can be implemented using the same code.
A flag for linear log behavior prevents the logger from
freeing up an erase unit in which to continue writing. 

It should also be noted that the use of a circular log mandates
the use of at least two erase units on the volume.  As discussed
in TEP128 [2]_, forcing volumes to contain at least two erase 
units solves this issue.


3.1 LogStorage Boot Behavior
--------------------------------------------------------------------
In the previous LogStorage implementations, reboots cause data to be
lost or overwritten because the beginning and ends of the log were
never located. Preventing previously stored data from being lost 
or overwritten after reboot is critical for the successful use and
integration of logging storage components within a practical,
deployable system.  

A method is required on boot to locate the first memory location to
read from as well as the next available memory location to write to. 
Although one method is to use microcontroller user memory 
to store the information, the goal is to avoid relying on external
support due to cross-platform compatibility reasons. Luckily, storing
and updating this information on the volume itself is easier than
it seems.  

Flash cannot overwrite areas of memory it has already written without
performing a read-modify-write operation, and this operation is
not supported on many flash types.  Regardless of whether the memory
type can support modifications, all types of memory - including EEPROM -
should take wear-leveling into account.  Combining these properties, 
it is possible to design a method of maintaining and updating logging 
start and stop information in a cross-platform compatible manner. 

The method of locating logging properties on boot is simplified by making 
entries aligned to erase unit boundaries, never allowing a single
entry to bridge erase units.  This also prevents invalid entries
from being created as a result of erasing an erase unit.

To find the first available write address to add new log entries, 
the first header entry on each erase unit is evaluated to find the 
greatest 32-bit "cookie" value that is not fill-bytes (0xFFFFFFFF). 
The erase unit with the largest value contains the newest data. 
Next, each entry in that erase unit can be iterated through by reading 
each header and skipping the length of the header + data, until a 
header with the value 0xFFFFFFFF is located.  The address of this 
location is the first available address to write.

Finding the first available address for reading involves the same process.
The first header entry on each erase unit is evaluated to find the lowest
32-bit "cookie" value.  The entry with the lowest value is the beginning
of the log.

The first entry to read from and last address to write to MUST be 
located on platform boot.


3.2 Appending log entries
--------------------------------------------------------------------
The previous M25P80 log storage implementation is a good place to start.
In it, each write consists of a 32-bit header "cookie" and the data to 
be appended to the log.  Locating the beginning of the log is therefore 
a matter of finding the lowest header cookie value.  If this were to be 
implemented so entries align with erase unit boundaries, only the
first header of each erase unit needs to be checked for the lowest value.

32-bits leaves plenty of space to increment log entry values for.
If the log were to append one chunk of data every second, it would
take 136.1 years before the 32-bit header recycles to 0 and causes
an issue in properly locating the first and last log entries.  
This is well beyond the expected lifetime of a deployed system.

Each header entry can provide additional support for every
data entry by allowing it to track the amount of appended data as well 
as an optional 8-bit CRC to verify the data is valid:::

  typedef struct log_header_t {