From: rincon <rincon>
Date: Fri, 20 Apr 2007 17:14:35 +0000 (+0000)
Subject: Creation.  First drafts of Storage Working Group TEP's.
X-Git-Tag: tinyos/2.0.1~15
X-Git-Url: https://oss.titaniummirror.com/gitweb/?p=tinyos-2.x.git;a=commitdiff_plain;h=1c69c2534b1513e782e73dfb8af7d8914dad24c2

Creation.  First drafts of Storage Working Group TEP's.
---

diff --git a/doc/txt/tep128.txt b/doc/txt/tep128.txt
new file mode 100644
index 00000000..16fd52e5
--- /dev/null
+++ b/doc/txt/tep128.txt
@@ -0,0 +1,496 @@
+===================================
+Platform Independent Non-Volatile Storage Abstractions
+===================================
+
+:TEP: 128
+: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 a layer of abstraction to reside between a chip-dependent
+flash chip implementation and platform-independent storage 
+implementations.  This abstraction layer should provide methods
+to perform basic flash operations (read, write, erase, flush, crc),
+as well as provide information about the physical properties of the
+flash chip.  Efficiency concerns are mitigated by the fact that each
+platform-independent abstraction is implemented in a platform-dependent
+manner, allowing it to exist on different types of memory such as
+NAND flash, NOR flash, and EEPROM.  This abstraction layer should
+allow one implementation of each storage solution to operate across
+many different platforms.
+
+
+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.  A true abstraction layer would
+exhibit the same set of interfaces and no differences in behavior when
+implemented across various types of non-volatile memory.
+
+A well defined non-volatile memory abstraction layer should allow core 
+functionality to work on a variety of platforms without modification.
+Some flash chips may provide extra functionality.  If a particular 
+applications on a specific platform wants to take advantage of
+extra functionality provided by a flash chip, it still has the opportunity
+to access those features directly with the understanding that its
+implementation is no longer considered platform-independent.
+
+
+1.1 Platform-dependent volume settings
+--------------------------------------------------------------------
+Differences exist between the TEP 103 storage implementations 
+on the AT45DB, ST M25P80, and PXA27X P30 flash chips.  
+
+First, volume information is defined using two distinct methods. As
+was discussed in TEP 103, an XML file is responsible for the 
+allocation of flash memory into volumes at compile time.  Individual
+storage layers can then mount to the defined volumes, which 
+allows those layers to share the flash memory resource amongst
+each other.
+
+The AT45DB implementation running on mica* platforms converts the 
+information presented in the application's volumes XML file into
+information accessible through macros:::
+
+  #ifndef STORAGE_VOLUMES_H
+  #define STORAGE_VOLUMES_H
+
+  enum {
+    VOLUME_BLOCKTEST, 
+  };
+
+  #endif
+  #if defined(VS)
+  VS(VOLUME_BLOCKTEST, 1024)
+  #undef VS
+  #endif
+  #if defined(VB)
+  VB(VOLUME_BLOCKTEST, 0)
+  #undef VB
+  #endif
+
+
+The ST M25P80 implementation running on TelosB/Tmote platforms,
+on the other hand, converts the information in the volumes XML 
+file into an array of constants:::
+
+  #ifndef __STORAGE_VOLUME_H__
+  #define __STORAGE_VOLUME_H__
+
+  #include "Stm25p.h"
+
+  #define VOLUME_BLOCKTEST 0
+
+  static const stm25p_volume_info_t STM25P_VMAP[ 1 ] = {
+      { base : 0, size : 4 },
+  };
+
+  #endif
+
+Furthermore, the two implementations defined incompatible interfaces for 
+accessing information about volumes.  For example, the AT45DB interface 
+provides the following:::
+
+  interface At45dbVolume {
+    command at45page_t remap(at45page_t volumePage);
+    command at45page_t volumeSize();
+  }
+
+The ST M25P80 interface defines a different interface, which allows
+applications to access the volume settings directly through the 
+stm25p_volume_info_t array:::
+
+  interface Stm25pVolume {
+    async event volume_id_t getVolumeId();
+  }
+
+Accessing volume information is very platform-dependent.
+A single method should be integrated to access volume 
+settings and non-volatile memory properties across any platform.
+
+Another issue exists with the previous concept of volumes.  Any storage 
+solution that wishes to retain valid data while erasing invalid data 
+MUST have access to at least two erase units.  Circular logging, 
+configuration storage, variable storage, dictionary storage, file 
+systems, and more all require a minimum of two erase units to be 
+implemented effectively.  One erase unit can be used to erase 
+all the invalid data while other erase unit(s) retains any valid data.
+
+Therefore, the minimum allowable volume size should be twice the size
+of a single erase unit to effectively support the majority of
+storage applications.  The XML tools that process and allocate
+volumes should prevent a user from defining a volume too small:::
+
+  +------------+--------+------------+-----------+------------+
+  |            | AT45DB |   ST M25P  |   PXA27x  | K9K1G08R0B |
+  +------------+--------+------------+-----------+------------+
+  | Min.Volume |  512B  | 512B-128kB | 128-256kB | 16kB-64kB  |
+  +------------+--------+------------+-----------+------------+
+
+
+
+1.2 Platform-dependent component signatures
+--------------------------------------------------------------------
+The storage components' signatures differ across implementations.  
+For example, the PXA27X P30 flash defines "P30BlockC", "P30ConfigC",
+and "P30LogC" in place of "BlockStorageC", "ConfigStorageC", and
+"LogStorageC".  Furthermore, the BlockStorageC configuration in the 
+AT45DB implementation takes the following form:::
+
+  generic configuration BlockStorageC(volume_id_t volid) {
+    provides {
+      interface BlockWrite;
+      interface BlockRead;
+    }
+  }
+
+
+while the ST M25P80 implementation adds another interface:::
+
+  generic configuration BlockStorageC( volume_id_t volume_id ) {
+    provides interface BlockRead;
+    provides interface BlockWrite;
+    provides interface StorageMap;
+  }
+
+The StorageMap interface on the M25P80 flash chip simply allows
+an application to convert a volume-based virtual address into
+a physical address on flash.  Although it is a good idea, it
+is not consistent with other platforms' defined interfaces.
+
+
+2. DirectStorage
+====================================================================
+
+3.1 Differences and advantages
+--------------------------------------------------------------------
+The core current BlockStorage, ConfigStorage, and LogStorage 
+layers can all be implemented on a platform-independent abstraction 
+layer.  Providing an interface that allows direct, unimpeded
+access to the memory below while offering information about
+the properties of that memory is the first step in doing so.
+
+The DirectStorage interface was created to as part of the answer to this
+issue.  DirectStorage resembles the BlockStorage interface in many ways, 
+with two significant exceptions:
+
+1. Erase operation
+BlockStorage's behavior erases the entire volume at a time, which may 
+consist of multiple erase units.  DirectStorage allows erases to occur 
+on per-erase unit basis.  Therefore, if only a portion of the volume
+needs to be erased, it can.
+
+2. Organization
+BlockStorage defines two different interfaces for interacting with the
+flash:  BlockRead and BlockWrite.  These two interfaces are combined
+into one interface.  The getSize() command provided by the BlockRead
+interface is removed and replaced with VolumeSettings, which will be
+discussed later.  Also, sync()/syncDone() is replaced with 
+flush/flushDone(), which is responsible for writing any data that 
+has not already been written to non-volatile memory.  Although
+the crc() command can technically exist above BlockStorage as
+well as DirectStorage, it remains in DirectStorage for its ease
+of use.
+
+Finally, layers should have the ability to be added beneath DirectStorage
+to further optimize and enable memory operation.  For example, the
+ST M25P80 flash does not have any on-board RAM buffers, so it
+is up to the microcontroller to buffer and flush out data to write units.
+This functionality may not be desirable on all applications because
+it uses valuable microcontroller resources; therefore, it should 
+be removable as layers can be added and removed from radio stack
+architecture.
+
+Other memory types may require extra support in and underneath
+the hood of DirectStorage as well. NAND flash, for example, 
+requires bad block management and error correction. This functionality
+can be implemented without changing the behavior of the DirectStorage
+interface above.
+
+
+3.2 DirectStorage Interface
+--------------------------------------------------------------------
+The DirectStorage interface is described below.  Each "addr" variable
+is a virtual address, with 0x0 relative to the base address of the 
+volume.  This base address may actually be physically located 
+somewhere else on the non-volatile memory:::
+
+  interface DirectStorage {
+  
+    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(uint16_t eraseUnitIndex);
+    
+    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(uint16_t eraseUnitIndex, 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 volume is already in use
+ - 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 volume is already in use
+ - Signals writeDone(...) when complete.
+
+erase(uint16_t eraseUnitIndex);
+ - Erase a single 0-indexed erase unit
+ - Returns FAIL if the volume is already in use
+ - 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 volume is already in use
+ - Signals crcDone(...) when complete.
+
+
+3.3 DirectModify Interface
+--------------------------------------------------------------------
+Some memory types have the ability to modify their contents without
+destroying surrounding data.  
+
+The AT45DB NOR-flash, for example, is able to do this because 
+it has built in RAM buffers coupled with small erase unit sizes. 
+The physical RAM buffers perform a read-modify-write operation to 
+effectively change the contents of flash, allowing it to emulate
+the behavior of an EEPROM with the speed and efficiency of NOR-flash.
+
+The ATmega128 microcontroller has 4kB of internal EEPROM memory which 
+can be directly modified.  Also, the MSP430 has 256 bytes of internal
+NOR-flash memory which is divided into two segments of 128 bytes each.  
+When implemented properly, this NOR-flash memory can be modified in a 
+fault-tolerant manner. 
+
+The ST M25P80 NOR-flash cannot support modification without sacrificing 
+significant overhead.  It has 16 erase units that are 64kB each,
+which is too large to effectively modify bytes.
+
+While not all memories support modification, a unified interface
+should exist to interact with memories that do.  This interface
+should be access with the understanding that applications built
+on top may not be portable to all memory types. Also, DirectStorage 
+and DirectModify are mounted to their own individual volumes, so 
+DirectModify cannot share its allocated memory resources with 
+a DirectStorage interface:::
+
+
+  interface DirectModify {
+  
+    command error_t modify(uint32_t addr, void *buf, uint32_t len);
+  
+    command error_t read(uint32_t addr, void *buf, uint32_t len);
+  
+    command error_t erase(uint16_t eraseUnitIndex);
+  
+    command error_t flush();
+  
+    command error_t crc(uint32_t addr, uint32_t len, uint16_t baseCrc);
+  
+    command bool isSupported();
+    
+    
+    event void modified(uint32_t addr, void *buf, uint32_t len, error_t error);
+  
+    event void readDone(uint32_t addr, void *buf, uint32_t len, error_t error);
+    
+    event void eraseDone(uint16_t eraseUnitIndex, error_t error);
+    
+    event void flushDone(error_t error);
+    
+    event void crcDone(uint16_t calculatedCrc, uint32_t addr, uint32_t len, error_t error);
+    
+  }
+
+
+modify(uint32_t addr, void *buf, uint32_t len)
+ - Modify 'len' bytes located on non-volatile memory at the given address,
+   replacing them with data from the given buffer
+ - Returns FAIL if the volume is already in use
+ - Signals modified(...) when the operation is complete
+
+read(uint32_t addr, void *buf, uint32_t len)
+ - Read 'len' bytes into '*buf' from the given address
+ - Same as DirectStorage.read(...)
+ - Returns FAIL if the volume is already in use
+ - Signals readDone(...) when complete.
+
+erase(uint16_t eraseUnitIndex);
+ - Erase a single 0-indexed erase unit
+ - Returns FAIL if the volume is already in use
+ - 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.
+ - Same behavior as flush() methods found in Java
+ - 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 volume is already in use
+ - Signals crcDone(...) when complete.
+
+isSupported()
+ - Returns TRUE if DirectModify is available on the current memory type
+
+
+
+3.4 VolumeSettings Interface
+--------------------------------------------------------------------
+As was shown in Section 1.1, finding information about the current
+volume required platform-dependent methods of access.  VolumeSettings
+provides a unified method of accessing information about the underlying 
+memory chip and volume settings.  
+
+VolumeSettings MUST be implemented separately for DirectStorage and
+DirectModify, not only because those abstractions will exist on
+separate volumes, but also because the DirectModify interface may 
+change the available size of the volume to support certain memory 
+types such as NAND- and NOR-flash:::
+
+
+  interface VolumeSettings {
+
+    command uint32_t getVolumeSize();
+
+    command uint32_t getTotalEraseUnits();
+  
+    command uint32_t getEraseUnitSize();
+  
+    command uint32_t getTotalWriteUnits();
+
+    command uint32_t getWriteUnitSize();
+  
+    command uint8_t getFillByte();
+
+    command uint8_t getEraseUnitSizeLog2();
+  
+    command uint8_t getWriteUnitSizeLog2();
+
+  }
+
+
+getVolumeSize()
+  - Returns the size of the volume the DirectStorage layer 
+    is mounted to, in bytes
+
+getTotalEraseUnits()
+  - Returns the total number of erase units on the mounted volume
+
+getEraseUnitSize()
+  - Returns the size of an individual erase unit, in bytes
+
+getTotalWriteUnits()
+  - Returns the total number of write units on the mounted volume
+
+getWriteUnitSize()
+  - Returns the size of an individual write unit, in bytes
+
+getFillByte()
+  - Returns the default byte value found on the memory after an erase,
+    which is typically 0xFF
+
+getEraseUnitSizeLog2()
+  - Returns the size of an erase unit in Log2 format for ease of
+    calculations
+
+getWriteUnitSizeLog2()
+  - Returns the size of a write unit in Log2 format for ease of
+    calculations
+
+  
+
+4. Author's Address
+====================================================================
+
+| David Moss
+| Rincon Research Corporation
+| 101 N. Wilmot, Suite 101
+| Tucson, AZ  85750
+|
+| phone - +1 520 519 3138
+| phone - +1 520 519 3146
+| email ? dmm@rincon.com
+|
+| Junzhao Du
+| Contact -
+|
+| Prabal Dutta
+| Contact -
+| 
+| Deepak Ganesan
+| Contact -
+| 
+| Kevin Klues 
+| Contact -
+| 
+| Manju
+| Contact -
+|
+| Ajay Martin
+| Contact -
+|
+| Gaurav Mathur
+| Contact -
+
+
+5. Citations
+====================================================================
+.. [1] TEP 103: Permanent Data Storage (Flash). http://tinyos.cvs.sourceforge.net/*checkout*/tinyos/tinyos-2.x/doc/html/tep103.html
+.. [2] Atmel AT45DB041B datasheet. http://www.atmel.com/dyn/resources/prod_documents/DOC1432.PDF
+.. [3] ST M25P80 datasheet. http://www.st.com/stonline/products/literature/ds/8495/m25p80.pdf
+.. [4] K9K1G08R0B datasheet. http://www.samsung.com/Products/Semiconductor/NANDFlash/SLC_SmallBlock/1Gbit/K9K1G08R0B/ds_k9k1g08x0b_rev10.pdf
diff --git a/doc/txt/tep129.txt b/doc/txt/tep129.txt
new file mode 100644
index 00000000..c582f1f1
--- /dev/null
+++ b/doc/txt/tep129.txt
@@ -0,0 +1,451 @@
+===================================
+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 {
+    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 - +1 520 519 3138
+| phone - +1 520 519 3146
+| email ? dmm@rincon.com
+|
+| 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