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

[Jonathan Hui]

Thanks for all the comments/feedback. I've inlined my comments to give
you a better idea of why we  went down the path that we did.

On 7/25/06, David Moss <dmm at rincon.com> wrote:
> 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....

Actually, we addressed this issue indirectly in the latest tinyos-2.x
implementations. The volume tables are generated at compile time, so
there is no need for them to be stored on the flash chip itself.

> 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.

One behavioral difference you'll never be able to match between flash
chips is the erase time. The STM25P takes significantly longer to
erase a sector than the AT45DB does to erase a page. Also, you will
loose efficiency if you try to unify the HAL. For example, the AT45DB
implementation utilizes the metadata section of each page, while the
STM25P has no luxury. So methods for supporting fault tolerance,
improving seek performance, etc. would best be implemented above the
HAL layer where better knowledge of the data and its storage semantics
are known.

> 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.

This is nearly impossible unless you want to sacrifice efficiency at
the HAL layer. One example is the AT45DB's 264 byte pages/erase size
vs the STM25P 256 byte pages/64K erase size. What does an address
mean? What page does it map to? Should address X always map to the
same page, meaning the extra 8 bytes per page on the AT45DB are
unaddressable?

Another nice feature about the AT45DB compared to the STM25P is that
it allows you to write the same byte over and over again without first
have to do an erase. This feature alone would cause me to use
different mechanisms on the AT45DB than the STM25P.

> 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.

In many cases, its best to have different implementations for Block,
Config, and Log. There already are very different implementations
between the AT45DB and STM25P because of their performance and feature
differences. For Logs, the AT45DB keeps information in the metadata
section of each page to indicate where the end of the log is. For
Config storage, the STM25P implementation uses a log-based approach,
while config storage does not and simply swaps between two areas of
flash since erase/write cycles are small and quick. Clearly, a
log-based approach on the AT45DB would have been less efficient and
require more resources.

> 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.

Your approach is definitely one approach. We also feel that its
possible to provide a common abstraction for both the AT45DB and the
STM25P. However, we felt that it is better provided at a higher layer
(Block/Log/Config) rather than at the HAL layer for the reasons I gave
above.

> 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.

This is definitely an interesting approach. Erase sizes are not the
only thing to be concerned about, but erase latencies are also very
important. I would argue that implementations specific to each chip
can and should provide much better performance since it can take into
account the full features of each chip. This is what an HAL is
designed to do and is by no means intended to be uniform across
different chips.

Futhermore, you mentioned ways to adapt between the two chips by
having run-time knowledge of the erase size and how to deal with flash
buffers. What if you're trying to support a different flash chip that
provides a different set of features? Should you add another interface
that is stubbed out on the AT45DB and STM25P? I'd argue if you're
trying to do that, then you're effectively trying to write different
implementations for different flash chips already but limiting
yourself to it's full features. You've already limited yourself to
explicitly managing the AT45DB's RAM buffers. What if you wanted to
use a MRU policy rather than LRU? What if you want to prefetch data?
You can't do that in your proposed interfaces.

> 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

The interfaces are similar, but have very different semantics. One
provides fault-tolerance and the other doesn't.

> 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.

I guess we differ in where the HIL abstraction should be. You are
arguing that it be below BlockStorage/LogStorage/ConfigStorage. I
would argue that that is too low level if you want efficient
implementations for especially Log and Config.

> * 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.

I think this is where part of the confusion lies. The 'A' in 'HAL'
actually stands for Adaptation. I suggest you take a look at TEP2:
http://www.tinyos.net/tinyos-2.x/doc/html/tep2.html for a better
explanation of the HAA. While the HIL abstraction is chip independent,
by no means does the implementation of the HIL have to be chip
independent.

> * 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.

A circular log can easily be implemented on a single AT45DB page. The
fact that it requires 2 erase units is chip dependent.

> * 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.

Key-value lookups are interesting but do require additional overhead.

> * 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.

We do not plan to strive for "identical" performance between chips as
this is not possible when considering timing differences alone.

> * 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.

They don't really mean the same thing. BlockWrite.commit() means you
shouldn't write any more data until the next erase. A LogWrite.sync()
really means to make all recently written log data persistent, but you
can continue appending if you wish.

> * 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.

I haven't look much into Blackbook, but it does satisfy a different
set of requirements by allowing key-value pairs. Though it probably
uses more resources than the current ConfigStorage implementations do
(correct me if I'm wrong).

We certainly do not mean for BlockStorage/LogStorage/ConfigStorage to
be the only HIL for storage chips. I would love to see additional HILs
added to that list, including (possibly) a more general file system.
While I'm sure that it's possible to write Blackbook such that its
implementation is chip independent, I feel that making it chip
dependent would allow you to utilize chip-specific features and
increase performance considerably. Blackbook can still provide the
same interfaces on top. Sure, it will require you to maintain a
version for each flash chip, but that is the tradeoff. I guess I'm
more inclined to strive for greater performance when operating on
already resource constrained devices.

-- 
Jonathan W. Hui
jwhui at cs.berkeley.edu
http://www.cs.berkeley.edu/~jwhui/