tep129.txt

tinyos-2.x.rar

    uint32_t cookie;
    uint8_t length;
    uint8_t crc;
  } log_header_t;

When the logger appends to the next erase unit boundary, it can first erase
it to ensure future appends are not corrupted by existing bytes. At the 
point where it reaches the end of its volume, the 'circular' logging 
flag can be used to determine if the logger should go back to the 
beginning of the volume and continue writing.  Again, this is performed 
in conjunction with the VolumeStorage interface to determine erase unit
properties.


3.3 Reading log entries
--------------------------------------------------------------------
After the first log entry is located, entries are extracted by first 
reading the header of a single entry, and using the information from 
the header to pull out the subsequent log information.  After each read, 
the read pointer is updated to point to the read location of the next header.

If the header ID is fill bytes (0xFFFFFFFF), then the entry is
invalid and the read process has reached the end of the log. As with
the ST M25P80 implementation, entries may be randomly seeked by 
providing the 32-bit "cookie" identifier to locate.


3.5 Logging conclusions
--------------------------------------------------------------------
This proposed logging storage solution will provide the
ability to maintain and locate previously logged data as well as 
support truly circular logs by mandating more than one erase unit per
volume.  Behavioral differences between flash chip implementations
are eliminated so one application can access logging storage across 
all platforms.  Furthermore, reboots will not cause logged information
to be lost or overwritten.

Existing LogRead and LogWrite interfaces defined in TEP 103 [2]_ are
sufficient to implement cross-platform logging abilities.



4. Implementing a platform-independent ConfigStorage
====================================================================

The previous interface to ConfigStorage looks very similar to that
of BlockStorage.  The ConfigStorage interface allows reads and
writes to arbitrary addresses, which is not optimal.  One critical 
concept behind the storage of configuration data is the ability to
modify and overwrite existing parameters while preventing surrounding
data from being corrupted.  The former ConfigStorage definition did
not support this, so a new solution should be explored and developed.  

This new solution should prevent an application from specifying 
addresses to read and write to on the volume.  Instead, it should dictate
addresses underneath, not allowing applications to see those addresses.
In essence, the solution should handle the allocation of memory and 
take the burden of determining valid addresses off of the application 
layer.  This will allow it to support multiple components written by 
different authors on the same system.


4.1 Hash-based configuration storage
--------------------------------------------------------------------
Several practical deployments have demonstrated the effectiveness of 
a hash-based configuration storage solution.  In it, any module
in a system can store and update any type of data of any size without 
destroying other modules' information.

The implementation is similar to that of ConfigStorage in that each
entry contains a header followed by a variable amount of data.  
The header is different than ConfigStorage headers in that instead 
of containing a 32-bit cookie, it contains a 32-bit hash key and
a magic number to keep track of state:::

  typedef struct config_header_t {
    uint32_t hashId;
    uint8_t magic;
    uint8_t length;
    uint8_t crc;
  } config_header_t;


The magic number allows Configuration storage to determine if the 
entry is valid or has been deleted.  Because non-volatile memory typically 
writes from 1's to 0's, the magic number can take on a finite number of
values before it is filled with 0's.  For example:::

  enum {
    ENTRY_EMPTY = 0xFF,
    ENTRY_VALID = 0xEE,
    ENTRY_INVALID = 0xDD,
  };

Configuration data can be stored and retrieved by indexing it with 
a hash key. Like AM types in the radio stack [3]_, each key is uniquely 
defined by the developer.

Each new update to the configuration storage should create an entirely
new entry while invalidating any previous entry containing the same hash key.
Optionally, a small cache in RAM can be used to maintain information about
where existing hash ID's are located in memory, so non-volatile memory
does not need to be traversed each time.

When space runs out on one erase unit, the next erase unit can be used
to copy in all valid data from the first.  The first erase unit can 
then be erased.  This allows parameters and configuration data to be 
infinitely updated so long as the amount of valid data plus supporting
headers is less than half the volume's total erase unit size.


4.2 Improved ConfigStorage interface
--------------------------------------------------------------------
The interface to access the configuration storage mechanism is proposed
as follows, allowing the application layer to continually update
previously stored parameters while preventing it from accessing
memory addresses directly:::

  interface ConfigStorage {

    command error_t getTotalKeys();
    
    command error_t insert(uint32_t key, void *value, uint16_t valueSize);
    
    command error_t retrieve(uint32_t key, void *valueHolder, uint16_t maxValueSize);
    
    command error_t remove(uint32_t key);
    
    command error_t getFirstKey();
  
    command uint32_t getLastKey();
  
    command error_t getNextKey(uint32_t presentKey);


    event void inserted(uint32_t key, void *value, uint16_t valueSize, error_t error);
    
    event void retrieved(uint32_t key, void *valueHolder, uint16_t valueSize, error_t error);
    
    event void removed(uint32_t key, error_t error);
  
    event void nextKey(uint32_t nextKey, error_t error);

    event void totalKeys(uint16_t totalKeys);

  }

getTotalKeys()
 - Determine the total number of valid keys stored on non-volatile memory
 - Signals totalKeys(...) when complete

``insert(uint32_t key, void *value, uint16_t valueSize)``
 - Insert some data into the configuration storage associated with the
   given key
 - Signals inserted(...) when complete

``retrieve(uint32_t key, void *valueHolder, uint16_t maxValueSize)``
 - Retrieve the value associated with the given key.  The maximum value
   size is the maximum amount of data that can be loaded into the 
   ``*valueHolder`` location, to avoid overflow
 - Signals retrieved(...) when complete

remove(uint32_t key)
 - Removes the given key and its associated values from non-volatile memory
 - Signals removed(...) when complete

getFirstKey()
 - Determines the first key available for reading on non-volatile memory
 - Signals nextKey(...) when complete

getNextKey(uint32_t presentKey)
 - Obtain the next available key on non-volatile memory based on the 
   current key.  Allows the application to traverse through all stored
   keys.
 - Signals nextKey(...) when complete

getLastKey()
 - Returns last key available for reading on non-volatile memory.
 - This value is assumed to be located in cache, so it can
   return immediately

  

5. Author's Address
====================================================================

| David Moss
| Rincon Research Corporation
| 101 N. Wilmot, Suite 101
| Tucson, AZ  85750
|
| phone - [phone]
| phone - [phone]
| email ? [e-mail]
|
| Junzhao Du
| Contact -
|
| Prabal Dutta
| Contact -
| 
| Deepak Ganesan
| Contact -
| 
| Kevin Klues 
| Contact -
| 
| Manju
| Contact -
|
| Ajay Martin
| Contact -
|
| Gaurav Mathur
| Contact -


6. Citations
====================================================================
.. [1] TEP 103: Permanent Data Storage (Flash).
.. [2] TEP 128: Platform independent Non-Volatile Storage Abstraction Layers
.. [3] TEP 116: Packet Protocols
.. [4] Atmel AT45DB041B datasheet. http://www.atmel.com/dyn/resources/prod_documents/DOC1432.PDF
.. [5] ST M25P80 datasheet. http://www.st.com/stonline/products/literature/ds/8495/m25p80.pdf
.. [6] K9K1G08R0B datasheet. http://www.samsung.com/Products/Semiconductor/NANDFlash/SLC_SmallBlock/1Gbit/K9K1G08R0B/ds_k9k1g08x0b_rev10.pdf