--- /dev/null
+===================================
+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
--- /dev/null
+===================================
+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
projects / tinyos-2.x.git / commitdiff