[Tinyos-devel] Request for comments on TEP 103, due August 10th

[David Moss]

My team's deployment applications rely heavily on the use of flash for
permanent data storage.  In fact, the use of flash makes or breaks our
ability to meet product requirements.  

First, the permanent data storage solutions described in TEP 103 are good
ideas.  Having the ability to partition the flash and use different volumes
for different purposes is great.  Being able to log data linearly or
circularly, store configuration data as well as large objects of data is
what people need for useable, deployable systems. 

I attempted to use the lib/Flash components (BlockStorage) early on to meet
our storage requirements, but ended up writing my own interfaces to flash
because BlockStorage was found not to be the best general solution.  We had
to start with rewriting a basic flash interface all the way up to a full
blown cross-platform compatible file system - kind of a pain, when all I
wanted to do is write the application.

There were three aspects of the storage solution that prevented us from
using it in deployment applications.  These are described below, each with a
small book that follows, detailing the issues.  A summary can be found at
the end.  I wrote a lot because I think that having a robust permanent
storage solution is absolutely necessary for TinyOS.



1. There are considerable differences in software behavior across different
flash types.
Yes, the AT45DB and the STM25P and every other flash type is inherently
different, but that shouldn't prevent us from being able to write interfaces
and implementations that allow a single application to run on both a mica2
and a tmote without having to rewrite the app for each flash type.  Correct
me if I'm wrong, but the BlockWrite on the AT45DB uses the first page of
flash to store meta/CRC information - so this first page is off limits to my
app and not well documented.  Also, only the first page is erasable. On the
STM25P, however, the last page of each sector is used for volume
information, and no CRC's are stored like the AT45DB implementation. So now
my app can't write to the last page of each sector either.  Therefore, in
order to write an application that uses BlockRead/BlockWrite, I have to know
a lot of detail about the intricate behavioral differences between the two
implementations.  If I wrote an app for a mica2 that uses the
BlockRead/BlockWrite interface and now want that app to work as is on a
tmote, forget about it.  The reason for this is....



2. These storage abstractions are not the lowest common denominator when it
comes to an interface for flash.
The most direct, abstract interfaces to any flash chip are: 
  * read(addr, *buf, len);
  * write(addr, *buf, len);
  * erase(eraseUnitIndex);
  * crc(addr, len);
  * flush();

All other flash abstractions can sit on top of these five commands, and they
should be implemented without any behavioral differences for all flash
types.  The concept of volumes would exist above this level as well.
BlockStorage looks like it attempted to fulfill this type of general
interface, but verify() and commit() got in the way.  If I want to ever
interact directly with flash I should be able to access this HAL interface
for all flash types and let my app do its thing - without having to worry
about where CRC's and volume information are being kept and what areas of
flash are off limits for each flash type.

I completely disagree with the statement "Flash families with a common HPL
SHOULD have a common HAL."  Instead, this should read "All flash types
SHOULD have a common interface to the HAL with parallel underlying
behavior."  If all flash types don't have a common hardware abstraction
interface with similar, expected behaviors, then the abstraction is
undeniably broken - there is no abstraction.

BlockStorage, ConfigStorage, LogStorage, custom file systems, and any other
flash component implementation can sit nicely on top of this type of HAL
interface without having to rewrite each storage implementation for each
flash type.  Preventing each storage implementation from being rewritten for
each flash type saves both the implementers and the end-user developers time
and headaches.

Let's talk about flash differences. The AT45DB041's erase size is at the
page level, with varying sector sizes in sectors 0-2, and similar sector
sizes in sectors 3-5.  ST's M25P80 has erase sizes at the sector level, with
similar sector sizes throughout.  The AT45DB has RAM buffers, the M25P80
does not.  The AT45DB has the ability to do a read-modify-write operation
because of the RAM buffers, while the M25P80 does not.  The difference in
behavior between these two flash chips usually kills anyone's ability to
think that a common, behavior neutral abstraction can be formed between the
two chips.  But it can.  The FlashBridge interface and implementations I
wrote (/contrib/rincon/apps/flashbridge) proves this by providing the
interfaces described above with neutral behavior.  Although I had to change
the minimum erase unit on the AT45DB flash to the size of a sector in my
implementation (because I didn't care about small erase sizes), it's
possible to compile an app that uses FlashBridge onto both mica's and
tmote's without modifications to the application layer.

In order to adjust for the difference in erase sizes and make for a better
abstraction, the solution is to provide a second interface for flash
properties that allows an application to adjust itself based on the flash
erase sizes - similar, in a way, to how the Packet interface allows higher
layers in an application to adjust themselves according to what's
underneath.  The Logger component, for example, would be able to access this
flash properties interface for the STM25P80 and know it needs at least 2
erase units (2 sectors = 0x20000 bytes) to be able to implement a circular
log.  Similarly, it could look at the flash properties interface for the
AT45DB and know it needs at least 2 erase units (2 pages = 0x200 bytes) to
be able to implement a circular log.  Because it would have access to the
properties of the flash, the application knows exactly which addresses are
on erase unit boundaries, and respond accordingly without writing data to an
area where it may be lost on the next erase.  In my Blackbook file system,
the set of properties I needed to correctly handle each flash type turned
out to be: page length, erase unit length, total erase units - and could
calculate the number of pages/erase unit.  This was used by the file system
to know where to locate boundaries and place data so it wouldn't get cut in
half from an erase.  So maybe it needs to be thought out a little more, but
start out with a basic flash properties interface would look like:

  * getEraseUnitLength();
  * getPageLength();
  * getTotalEraseUnits();
  * getPagesPerEraseUnit();
  * etc.
As far as the RAM buffer differences in the flash types - flush() should
store what's in the RAM to flash on the AT45DB, and flush() should not do
anything on the M25P80.  When the application needs to ensure data is
written to flash, calling flush() on either flash type guarantees your data
is on flash.

NAND flash would be able to implement this type of interface and hide the
bad block management functionality within - still providing a common,
behavior neutral HAL interface.



3. Implementation problems and application layer demands...
BlockStorage and ConfigStorage both have very similar interfaces that allow
you to read and write seemingly arbitrary addresses on flash.  If you've
written something to flash and reboot the mote, it appears as though the
application layer has to take care of finding the next write location on
flash.  It would be nice if, at least in ConfigStorage, you didn't have to
worry about finding and writing to the correct location - or worry about any
address for that matter.  Addresses should be dealt with internally by
ConfigStorage interface - not in the application layer.

For reference and to plant a seed, the Blackbook file system's equivalent to
ConfigStorage is the Dictionary, which allows your application to write
key-value pairs to flash.  The keys are uint32_t, and the values are
arbitrary lengths.  Of course, this was on a file system, so Dictionary
files were actually being written - but the same concept could apply here.
This was a very sleek way to store and retrieve information:  for example,
if you have a struct that contains the security settings of your application
and want it to be reloaded from flash on boot, just save the struct in an
open Dictionary file, providing a corresponding look up key.  No need to
worry about what address it's being written to in flash, whether or not it's
valid, or how to retrieve it.  On the next reboot, just open up the
Dictionary file and tell it to retrieve the value from the given key, and
your struct in RAM is automatically loaded with the latest information if it
exists.  Managing configuration data can't get much easier than that from an
application standpoint.  Multiple key-value pairs are allowed, and
Dictionary files in Blackbook are also circular: you can write to the file
infinitely and it should never run out of space, only erasing sectors
("volumes") once the entire flash is filled.

On the implementation side of these storage components, random typedefs
should be done away with.  It's time consuming to sift through .h files
looking for the definition of "storage_addr_t" and "storage_len_t" and other
such typedefs.  Both implementations have the same issues, like
"storage_addr_t" maps to "stm25p_addr_t" in one .h file which maps to
"uint32_t" in a separate .h file, and similarly "storage_len_t" maps to
"stm25p_len_t" which maps to "uint32_t".  And "storage_cookie_t" is just a
"uint32_t" as well.  So why not just do away with all of these and simply
use "uint32_t" in the first place, saving everybody some trouble?  Typedef's
are useful for structs - but not useful for giving a basic variable type
several different names.



SUMMARY
* The HAL is broken as is and needs to be thought out some more to provide
one set of basic flash interfaces that works on each flash type with no
behavior inconsistencies.  Abstracting flash by providing direct access
through a common interface with predictable behavior is the key.  Volume
abstractions can further be provided on top of that, but should not be the
basic means of accessing flash.

* Above the HAL layer, the HIL should not be chip dependant.  If the HAL is
designed and built correctly (it's the Abstraction Layer after all), the
implementation layer should be written once, used everywhere.  The AT45DB
should look like a smaller M25P80 from the application standpoint.  Chip
Dependant HIL == Chip Dependant Application.  And that breaks the model for
TinyOS.

* The LogStorage looks great - provided the user defining volumes and
software knows that a circular log can't be implemented in less than 2 erase
units.

* The ConfigStorage component should stop looking like the BlockStorage
component by getting rid of addresses in the arguments, taking a load off
the application layer.  If multiple structs are to be stored in
ConfigStorage, key-value look ups should be considered as a simple,
alternative implementation. 

* BlockStorage looks just like the basic flash interfaces previously
described, but with some data verifying functionality. This functionality
should be well documented, and its implementation and behavior should be
identical on any flash chip to allow an application to port to any platform.
It would be nice to be able to find where the next writable address is
located.

* The address ranges an application is able to read/write should be enforced
- i.e. to prevent the app from using BlockStorage to overwrite an area where
the CRC's are kept.

* Remove the confusing web of typedef's that translate back into basic
variable types.

* Remove the differences and references to commit, sync, and flush.  Choose
one.  They all basically mean the same thing.

* Keep in mind that it's easy to define a volume simply as the size of a
sector, and enforce full volume-sized erases when you go to erase something.
This would help make flash access more chip-independent by removing the
erase unit size inconsistencies.


Hope my comments were useful, and keep in mind I'm only trying to help.
-David




-----Original Message-----
From: tinyos-devel-bounces at Millennium.Berkeley.EDU
[mailto:tinyos-devel-bounces at Millennium.Berkeley.EDU] On Behalf Of Ramesh
Govindan
Sent: Friday, July 21, 2006 8:34 AM
To: tinyos-help at Millennium.Berkeley.EDU
Cc: tinyos-devel at Millennium.Berkeley.EDU
Subject: [Tinyos-devel] Request for comments on TEP 103, due August 10th


Hi folks,

TEP 103 is ready to move from draft to final. As part of this process,
I'd like to invite those of you who might have comments about this
TEP, available at:

http://www.tinyos.net/tinyos-2.x/doc/html/tep103.html

to send them to me before *August 10th*. I will collate the comments,
discuss the required revisions with the authors, and shepherd the TEP
to final.

Please let me know if you have any questions.

Regards.
-- 
Ramesh
http://cs.usc.edu/~ramesh/

_______________________________________________
Tinyos-devel mailing list
Tinyos-devel at Millennium.Berkeley.EDU
https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel