Flash chips are a form of EEPROM (electrically-eraseable, programmable +
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 @@ -337,30 +324,93 @@ or that it be in relatively large units (e.g., 256B).
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: -- NOR AT45DB NAND - -Erase : Slow (seconds) Fast (ms) Fast (ms) -Erase unit : Large (64KB-128KB) Small (256B) Medium (8K-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 : Fast* Slow+I/O bus Fast (but limited by - I/O bus) -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 - -* Intel Mote2 NOR 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 -+
+++
++ + ++ + + + + + + X +NOR +(ex: ST M25P40, +Intel PXA27x) +AT45DB +NAND +(ex: Samsung +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 a Samsung datasheet). Energy/byte for reads appears +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 @@ -372,7 +422,7 @@ access to per-page read, write and erase operations.
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 @@ -385,6 +435,9 @@ This is not readily implementable on a flash chip with large erase units. reimplemented for these other chips, in part because it does not support some applications (e.g., network reprogramming) very well. +
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, @@ -397,22 +450,36 @@ 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. -
Another approach to supporting multiple flash chips is to build a -file system (like Matchbox) which can be implemented for multiple -flash chips. However, 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, and may come at the expense of implementation -and runtime complexity.
-Instead, 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). So far there are three -such abstractions: large objects written in a single session, -small objects with arbitrary reads and writes, and logs. This approach -has two advantages:
+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:
New abstractions (including a filing system) can easily be added to this -framework, or can be built on top of these abstractions.
+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 2), then describes the flash volumes and -storage abstractions in detail (Section 3).
+flash chips (Section 3), then describes the flash volumes and +storage abstractions in detail (Section 4).The flash chip architecture dollows the three-layer Hardware +
The flash chip architecture follows the three-layer Hardware Abstraction Architecture (HAA), with each chip providing a presentation -layer (HPL, Section 2.1), adaptation layer (HAL, Section 2.2) and -platform-independent interface layer (the storage abstractions described in -Section 3) [2]. The implementation of these layers SHOULD be found in the +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.
The flash HPL has a chip-dependent, system-independent interface. The -implementation of this HPL is system-dependent. The flash HPL SHOULD be +
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 @@ -454,8 +521,8 @@ flash chips, this directory MAY also contain a file describing the particular flash chip found on the platform.
The flash HAL has a chip-dependent, system-independent interface and +
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 @@ -463,14 +530,28 @@ 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.
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.
+The HIL implementations are system-independent, but chip (family) +
The HIL implementations are platform-independent, but chip (family) dependent. They implement the three storage abstractions and volume structure discussed in the introduction.
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:
@@ -490,11 +571,12 @@ 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 may give any suitable physical -location to a volume. If there is any reason that the physical allocation +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. +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.
@@ -508,23 +590,20 @@ compile-time error since the symbol will be undefined.A volume MUST NOT be used with more than one storage abstraction instance.
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 two interesting characteristics: each byte in the object is -written at most once, and a full object is written in a single "session" -(i.e., without the mote rebooting).
+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:
+large objects or other "write-once" objects:Large objects are accessed by instantiating a BlockStorageC component which takes a volume id argument:
@@ -536,17 +615,17 @@ generic configuration BlockStorageC(volume_id_t volid) { } } ... -The BlockRead and BlockWrite interfaces contain the following -operations (all split-phase, except BlockRead.getSize):
+The BlockRead and BlockWrite interfaces (briefly presented in +Appendix B) contain the following operations (all split-phase, except +BlockRead.getSize):
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.
Event and reuslt logging is a common requirement in sensor +
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 is guaranteed to only lose -whole records from the end of the log. Additionally, once a circular log -wraps around, calls to LogWrite.append only lose whole records from the -beginning of the log. These guarantees mean that applications do not to -have worry about incomplete or inconsistent log entries.
+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:
@@ -583,29 +665,39 @@ generic configuration LogStorageC(volume_id_t volid, bool circular) {
If the circular argument is TRUE, the log is circular; otherwise it is linear.
-The LogRead and LogWrite interfaces contain the following -operations (all split-phase except LogWrite.currentOffset, -LogRead.currentOffset and LogRead.getSize):
+The LogRead and LogWrite interfaces (briefly presented in +Appendix B) contain the following operations (all split-phase except +LogWrite.currentOffset, LogRead.currentOffset and +LogRead.getSize):
LogWrite.erase: erase the log.
+LogWrite.erase: erase the log. A log MUST be erased (possibly in +some previous session) before any other operation can be used.
LogWrite.append: append some bytes to the log. In a circular log, this may overwrite the current read position. In this case, the -read position is implicitly advanced to the log's current beginning -(i.e., as if LogRead.seek had been called with SEEK_BEGINNING).
+read position MUST be advanced to the log's current beginning +(i.e., as if LogRead.seek had been called with SEEK_BEGINNING). +Additionally, the LogWrite.appendDone event reports whenever, in a +circular log, an append MAY have erased old records.Each append creates a separate record. Log implementations may have a maximum record size; all implementations MUST support records of up to 255 bytes.
LogWrite.sync: guarantee that data written so far will not be lost to a crash or reboot (it can still be overwritten when a circular log wraps -around). Using sync may waste some space in the log.
+around). Using sync MAY waste some space in the log.LogWrite.currentOffset: return cookie representing current append position (for use with LogRead.seek).
LogRead.read: read some bytes from the current read position in the log and advance the read position.
+LogStorageC implementations MUST include error detection codes +to increase the likelihood of detection of corrupted or invalid log +data. Data returned by a successful read MUST have passed this +error detection check. The behaviour on failure of this check is +unspecified (e.g., the at45db believes as if the end of the log has +been reached; other implementations may behave differently).
LogRead.currentOffset: return cookie representing current read position (for use with LogRead.seek).
@@ -617,18 +709,28 @@ the specified position has been overwritten, behave as if SEEK_BEGINNING was requested.SEEK_BEGINNING positions the read position at the beginning of the oldest record still present in the log.
+After reboot, the current read position is SEEK_BEGINNING.
LogRead.getSize: return an approximation of the log's capacity. -Uses of sync and other overhead may reduce this number.
+LogRead.getSize: return an approximation of the log's capacity +in bytes. Uses of sync and other overhead may reduce this number.
For full details on arguments, etc, see the comments in the interface definitions.
+Note that while each call to append logically creates a separate +record, the LogStorageC API does not report record +boundaries. Additionally, crashes, reboots, and appends after +wrap-around in a circular log can cause the loss of multiple consecutive +records. Taken together, these restrictions mean that a LogStorageC +implementation MAY internally aggregate several consecutive appends into +a single record. However, the guarantee that only whole records are lost +is sufficient to ensure that applications do not to have worry about +incomplete or inconsistent log entries.
Sensor network applications may need to store configuration data, e.g., -mote id, radio frequency, sample rates, etc. Such data is not large, but +
Sensor network applications need to store configuration data, e.g., +mote identity, radio frequency, sample rates, etc. Such data is not large, but losing it may lead to a mote misbehaving or losing contact with the network.
The ConfigStorageC abstraction stores a single small object in a volume. It:
@@ -653,9 +755,9 @@ generic configuration ConfigStorageC(volume_id_t volid) {A small object MUST be mounted (via the Mount interface) before the first use.
-The Mount and ConfigStorage interfaces contain the following -operations (all split-phase except ConfigStorage.getSize and -ConfigStorage.valid):
+The Mount and ConfigStorage interfaces (briefly presented in +Appendix B) contain the following operations (all split-phase except +ConfigStorage.getSize and ConfigStorage.valid):
An AT45DB implementation can be found in tinyos-2.x/tos/chips/at45db.
An ST M25P implementation can be found in tinyos-2.x/tos/chips/stm25p.
| [1] | David Gay. "Design of Matchbox, the simple filing system for + |
| [1] | David Gay. "Design of Matchbox, the simple filing system for motes. (version 1.0)." |
| [2] | TEP 2: Hardware Abstraction Architecture. |
| [2] | TEP 2: Hardware Abstraction Architecture. |
These interfaces are presented briefly here for reference; please refer +to the TinyOS documentation for a full description of the commands, +events and their parameters.
+The BlockStorage interfaces are:
+
+interface BlockRead {
+ command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
+ event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
+ error_t error);
+
+ command error_t computeCrc(storage_addr_t addr, storage_len_t len,
+ uint16_t crc);
+ event void computeCrcDone(storage_addr_t addr, storage_len_t len,
+ uint16_t crc, error_t error);
+
+ command storage_len_t getSize();
+}
+
+interface BlockWrite {
+ command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
+ event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
+ error_t error);
+
+ command error_t erase();
+ event void eraseDone(error_t error);
+
+ command error_t sync();
+ event void syncDone(error_t error);
+}
+
+The ConfigStorage interfaces are:
+
+interface Mount {
+ command error_t mount();
+ event void mountDone(error_t error);
+}
+
+interface ConfigStorage {
+ command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
+ event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
+ error_t error);
+
+ command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
+ event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
+ error_t error);
+
+ command error_t commit();
+ event void commitDone(error_t error);
+
+ command storage_len_t getSize();
+ command bool valid();
+}
+
+The LogStorage interfaces are:
+
+interface LogRead {
+ command error_t read(void* buf, storage_len_t len);
+ event void readDone(void* buf, storage_len_t len, error_t error);
+
+ command storage_cookie_t currentOffset();
+
+ command error_t seek(storage_cookie_t offset);
+ event void seekDone(error_t error);
+
+ command storage_len_t getSize();
+}
+
+interface LogWrite {
+ command error_t append(void* buf, storage_len_t len);
+ event void appendDone(void* buf, storage_len_t len, bool recordsLost,
+ error_t error);
+
+ command storage_cookie_t currentOffset();
+
+ command error_t erase();
+ event void eraseDone(error_t error);
+
+ command error_t sync();
+ event void syncDone(error_t error);
+}
+
+