NAND "FIS" in RedBoot proposal

NAND "FIS" in RedBoot proposal

[Ross Younger]

Hi all,

I've been working on a proposal for how we might allow RedBoot to use a NAND
array to provide the FIS.

I've include the current version of my proposed design, although following
the conversation with Simon this week it has occurred to me that it might
well be reasonable to fillet out the core idea and make it available as a
simple proto-filesystem. (Essentially it would be a block device with very
large blocks. The high-level operations provided would be reading and
writing up to a blockful, and erasing a whole block; this doesn't seem to
fit well with the eCos block device model, so I suspect it would be better
off as its own interface.) Please do speak up if that would be a useful
development, and if so I'll happily rework this proposal into two parts as
time allows.


Ross


============================================================================

NOR-in-NAND design (3/7/09)

1. Scenario and assumptions:

We want RedBoot to be able to use NAND flash as if it was NOR flash,
for FIS and fconfig.

We don't care about supporting non-RB apps, so can rely on RB's behaviour.

Analysis:
* fconfig-in-FIS always calls FIS code.
* fconfig not in FIS always erases before programming.
* FIS always erases before it programs, only deals with block-aligned
regions, and never rewrites within such a region. [+]

Design goals:
* Clean and simple, in keeping with the eCos philosophy.
* Robust: copes with blocks going bad and indulges in some sort of
wear-levelling.
* No use of malloc. (As we're targetting only RB, we can use the workspace.)

[+] This isn't 100% true; if CYGOPT_REDBOOT_REDUNDANT_FIS option is
enabled, it rewrites two bytes (its status flag) in the redundant copy
of the FIS block after writing out the data. We can provide suitable
redundant-write logic in the NOR-in-NAND driver; we can get this project
going initially by not allowing its combination with REDUNDANT_FIS. Later,
if desired, we could nobble the REDUNDANT_FIS code to not do its
page-rewrite and to drive the NAND-to-NOR layer so as to take advantage
of its redundancy if the NOR-in-NAND option was set. (Or, more flexibly,
it could do so if the flash driver were to set an as-yet-unspecified bit
of its as-yet-nonexistent flags word to say that it did redundant writes;
but this is perhaps wishful thinking.)

2. High level design

The NAND will present as a NOR device with block_size the same as the
NAND eraseblock size[#]. We will use a log-like storage mechanism with
block-level granularity.

[#] Nick pointed out that this could be souped up with an option to
combine multiple NAND blocks into a single logical block.

The logical blocks that RedBoot thinks it is using will be be internally
numbered from zero and mapped to a cyg_flash_addr:
	flash_addr := logical_block_number * block_size + flash_base
where flash_base is a suitable hex-round number defined by the platform
HAL to keep it away from any existing NOR devices.

The number of blocks available - i.e. (1 + maximum valid logical block
number) - will be computed as:
	* Number of physical blocks in the chip or partition,
	* minus the number of factory bad blocks,
	* minus one (to allow for robust block rewrites),
	* minus an allowance for bad blocks to develop during the life
	of the device.

The allowance for blocks going bad will be computed as four blocks,
plus a configurable % of the number of blocks in the NAND partition
(default 1%; rounded up).

The NAND library will require to be enhanced to cope with part-page
writes and reads, in particular getting the ECC right on them. (While
we're at it, we could also enhance it to get the ECC right on multiple
non-overlapping writes to a page, but this is harder, and seems
unnecessary in this case. Whatever we do, we need to document the precise
cases which are expected to work and to not work.)

The NOR-in-NAND layer will be making multiple-page reads and writes;
it may be worthwhile to put code to do this into the NAND layer, as
opposed to forcing all users to reinvent the wheel.

2.1. Physical block storage

NAND blocks are used as a dumb datastore, with their physical addresses
bearing no relation to their logical addresses. In-use blocks are tagged
in the OOB area with the logical block number they refer to (see below).

Physical storage blocks are used sequentially from the beginning of
the device, then cycling back to the start to reuse erased blocks. This
is managed by maintaining a next-write "pointer". At runtime, this is
the next vacant block after the last written block; at boot time, it
is initialised by scanning the filesystem to find the block with the
highest serial number, which is taken to be the latest-written block.

This scheme is much better than a simple block mapping due to its
robustness: it intrinsically provides reasonable wear-levelling, and is
very robust against physical blocks going bad. Provided no more than 1%
of the array goes bad in the field, no operation should ever fail from
the point of view of the caller, even with a full FIS.

In essence this is a nod towards log-structured filesystems, but with
very simple addressing.

2.1.1 OOB tag format

The tag is written into the OOB area of the first page of each block
(as "application" OOB data, from the NAND library's point of view).

The tag is a packed byte array, in processor-local endian, with the
following contents:

	* Magic number - 2 bytes, 0xEF15. (This is a compile-time constant
	and demonstrates that the block is one of ours. It's a corruption
	of "eCos FIS".)
	* Logical block number - 2 bytes.
	* Master serial number - 4 bytes (see below).

We deliberately keep the tag size to eight packed bytes so as to
conveniently support devices with 512-byte pages, which have 16 OOB bytes
per page, of which 8 are available for application use. (If desired,
256-byte page devices could be supported by spreading the tag over the
first two pages of the block. This adds complexity, IMHO needlessly as
those devices are firmly obsolete.)

2.1.2 Master serial number

This is a 4 byte counter which increments on every write. At boot time,
the array is scanned and the serial number is initialised to be one
greater than the largest serial number found in the array.

We assume that 2^32 writes are sufficient and that we will never have
to worry about overflow. (Justification: The typical 1Gbit chip on my
desk has 1024 blocks and is rated for 100,000 write/erase cycles. 1.024e8
max serials versus 4.295e9 capacity represents a safety margin of approx
41x. This will have to be rethought should chips with significantly longer
lifespans and more blocks appear.  To be safe, we should impose an upper
limit on the number of physical NAND blocks that this system will use,
and hence cap the number of logical NOR blocks the system will support. I
suggest 1024, which ought to be enough for anybody; it's more than many
(most?) NOR chips.)

2.2 Flash operations

All operations which read NAND blocks must check the data tags.

A magic number of all-0xFF means the block is empty; if it is anything
else other than the expected magic number, something Odd is going on
and we will report and ignore the block.

2.2.1 Query flash
This simply sets up the flash_info struct in the standard way.

2.2.2 Read from flash
Convert the flash address to a logical block number, call this B.
Find blocks containing data for block B. Switch on how many there were:
*	if 0: Synthesise an all-FFs return.
*	if 1: Return data from the pages of that block as appropriate
*	if 2: The block with higher serial number was probably
	incompletely written, so erase it. Proceed as for case 1.
*	if >2: Something strange has happened. Erase the block(s) with
	lowest serial numbers until two remain, then proceed as for
	case 2.

Iterate the above as necessary given the size of the write and the NAND
page/block size.

Read errors (i.e. NAND layer reported ECC uncorrectable) are not expected;
if one does occur, we do our best and report back.

2.2.3 Program flash
Convert the flash address to a logical block number, call this B.
Find blocks containing data for block B. Switch on how many there were:
*	if 0: write and tag the programmed data into the physical
	block pointed to by the next-write pointer, then increment that
	pointer until it points to an empty block, and increment the
	serial number counter.
*	if 1: we are doing a redundant write. Write and tag the programmed
	data - as for case 0 - then erase the older block.
*	if >1: Something strange has happened. Erase all existing blocks
	for block B except for the one with the second-highest serial
	number, then treat as case 1.

For robustness, by default we will perform a read-back of all pages as
we write then, but this can be switched off with a CDL option.

If a write fails, or fails to read-back correctly: mark the physical
block as bad, increment the next-write pointer until it points to an
empty block, then retry.

Iterate the above as necessary given the size of the write and the NAND
page/block size.

2.2.4 Erase flash region (given base address and erase size).
Convert the flash address to a logical block number, call this B.
Seek and erase all physical blocks bearing data for block B.  If the
eraselength was larger than the block size, repeat as necessary for
subsequent logical blocks.

If the NAND layer reports an erase failure, the block will already have
been marked as bad (by the NAND layer), so we need do nothing (except
perhaps whingeing about it).

To improve robustness, we will check that the tags area of a physical
block we've just erased is all-0xFF; if not, we shall retry the erase
once, and if that fails, mark the block as bad.

2.2.5 Block locking
These operations are not supported; they are provided as no-ops, and
CYG_FLASH_FUNS does the right thing.

2.3 Handling of bad blocks

When choosing where to write, marked-bad blocks are skipped over.
When scanning the array for a block, marked-bad blocks are similarly ignored.

The number of logical blocks in the array must never be changed after
its first use. Therefore it is essential that nothing, other than the
one-shot initial setup of the bad block table, ever marks a block used
for this scheme as factory-bad. This should be a safe assumption, as to
do so would require "forbidden" use of nand internals.

2.4 Runtime considerations

If a runtime performance boost was required, the system could on startup
scan the NAND partition and build up a cached mapping in-RAM of the
physical addresses of each (non-zeroed) logical block. However, we don't
expect this code will be used on gigantic NAND arrays [partitions],
and it should only see light duty via RedBoot. Therefore it won't take
long to linear-scan for blocks during operations, so this optimisation
may not be worth its complexity.

(Bart suggested that a scan at startup could also take care of the cases
above where more than one physical block is tagged with the same logical
block number, hence reducing the time and complexity of the block access
code. There's a startup time vs access time vs memory trade-off here,
though we haven't fully analysed it. Nick agreed that we ought to think
this through very carefully.)

============================================================================


-- 
Embedded Software Engineer, eCosCentric Limited.
Barnwell House, Barnwell Drive, Cambridge CB5 8UU, UK.
Registered in England no. 4422071.                  www.ecoscentric.com

Re: NAND "FIS" in RedBoot proposal

[Jonathan Larmour]

Ross Younger wrote:
> I've include the current version of my proposed design, although following
> the conversation with Simon this week it has occurred to me that it might
> well be reasonable to fillet out the core idea and make it available as a
> simple proto-filesystem. (Essentially it would be a block device with very
> large blocks. The high-level operations provided would be reading and
> writing up to a blockful, and erasing a whole block; this doesn't seem to
> fit well with the eCos block device model, so I suspect it would be better
> off as its own interface.) Please do speak up if that would be a useful
> development, and if so I'll happily rework this proposal into two parts as
> time allows.

I think there would be merit in doing something like that. I agree a block 
device interface wouldn't be appropriate.

> ============================================================================
> 
> NOR-in-NAND design (3/7/09)
> 
> 1. Scenario and assumptions:
> 
> We want RedBoot to be able to use NAND flash as if it was NOR flash,
> for FIS and fconfig.
> 
> We don't care about supporting non-RB apps, so can rely on RB's behaviour.

Not sure that is wise. And I'm not sure what specific behaviour you would 
wish to rely on. I wouldn't make the code itself dependent on RedBoot in 
any case. That's what got us into a mess with the v1 flash drivers. 
Ultimately the RedBoot FIS approach is not something we'd like to continue 
with - it was designed for the common case of the late '90s/early '00s of 
single NOR flash parts (and in some aspects, isn't so great even for then, 
such as not being able to support bootblocks properly). That code has 
limited lifespan, and many flaws. It's better to do something that can 
last beyond that.

I can certainly see this layer being used for a non-RedBoot boot loader. 
Lots of people may use RedBoot during development, but this sort of layer 
is useful for any boot loader. Far fewer people want to use RedBoot for 
their final product (outside of development) - they just want to load 
their apps and go. I'm not suggesting writing a boot loader to do this 
now, but I do believe it would be a mistake to think that people won't 
want to.

> Analysis:
> * fconfig-in-FIS always calls FIS code.
> * fconfig not in FIS always erases before programming.
> * FIS always erases before it programs, only deals with block-aligned
> regions, and never rewrites within such a region. [+]
> 
> Design goals:
> * Clean and simple, in keeping with the eCos philosophy.
> * Robust: copes with blocks going bad and indulges in some sort of
> wear-levelling.
> * No use of malloc. (As we're targetting only RB, we can use the workspace.)

The workspace is a very crude way to allocate memory, but if you can 
constrain yourself to it, so much the better.

> The number of blocks available - i.e. (1 + maximum valid logical block
> number) - will be computed as:
> 	* Number of physical blocks in the chip or partition,
> 	* minus the number of factory bad blocks,
> 	* minus one (to allow for robust block rewrites),
> 	* minus an allowance for bad blocks to develop during the life
> 	of the device.

Of course a (NOR) flash driver has to specify a constant device size, 
whereas the bad blocks are board specific, so really you have to have an 
allowance for bad blocks full stop.

> The NOR-in-NAND layer will be making multiple-page reads and writes;
> it may be worthwhile to put code to do this into the NAND layer, as
> opposed to forcing all users to reinvent the wheel.

Sounds like a better approach.

> NAND blocks are used as a dumb datastore, with their physical addresses
> bearing no relation to their logical addresses. In-use blocks are tagged
> in the OOB area with the logical block number they refer to (see below).
> 
> Physical storage blocks are used sequentially from the beginning of
> the device,  then cycling back to the start to reuse erased blocks. This
> is managed by maintaining a next-write "pointer". At runtime, this is
> the next vacant block after the last written block; at boot time, it
> is initialised by scanning the filesystem to find the block with the
> highest serial number, which is taken to be the latest-written block.

That sounds potentially painful for non-trivial numbers of blocks, unless 
you are going to use a large logical block size. More below.

> This scheme is much better than a simple block mapping due to its
> robustness: it intrinsically provides reasonable wear-levelling,

Not much if most/all blocks are used. I suspect with the normal usage 
pattern of flash under RedBoot, you wouldn't get much wear-levelling. 
You'd need to start occasionally reallocating used blocks too to 
wear-level properly, which admittedly probably wouldn't be /that/ 
difficult. That said, I think we should indeed probably just put up with 
theoretically inadequate wear-levelling for now.

Conversely, note that MLC NAND may start to become more common, but it is 
(I think) rated for ~10K cycles which may increase the need for more 
thorough wear-levelling.

> 2.1.1 OOB tag format
> 
> The tag is written into the OOB area of the first page of each block
> (as "application" OOB data, from the NAND library's point of view).
> 
> The tag is a packed byte array, in processor-local endian, with the
> following contents:
> 
> 	* Magic number - 2 bytes, 0xEF15. (This is a compile-time constant
> 	and demonstrates that the block is one of ours. It's a corruption
> 	of "eCos FIS".)
> 	* Logical block number - 2 bytes.
> 	* Master serial number - 4 bytes (see below).

Given you say processor-local endian, I assume you mean there are two 
16-bit words and a 32-bit word here.

Given you are assuming partial-page writes, I think you can do something 
more intelligent here to handle the seeking through NAND space that your 
proposal entails for every read/write:

- For a start, the serial number seems potentially overkill unless I'm 
missing something. All you need to know is whether a discovered logical 
block number is the most recent version of it. The serial only needs to 
reflect that block. When you write a new revision of a block, you mark the 
previous one dead by overwriting it with a partial write (without 
erasure). Thus you only have one valid version of a block at one time. 
Duplicates are dealt with solely at initial device scan time (stomping on 
the old one at that point). This way you only need 2 bits to represent the 
serial, theoretically (as the difference between serials can only be 1, so 
you can always tell which is older).

- That frees up space which we can use for potential optimisations. In 
particular, the common use-case we are envisaging is wholly sequential 
reads of fairly large images. So we could use 2 bytes to point to the next 
block in the logical block chain. This is very useful if most use is 
sequential. If that block turns out not to be the correct block number, we 
lose very little and just revert to scanning the medium. Most times it 
should be correct. (We could make this behaviour a CDL option anyway). 
This does mean knowing what the next block to be used next will be at the 
time you are writing the current block, but that doesn't seem to be much 
of an issue - it's primarily just bringing forward a determination you'd 
have to make anyway. This all doesn't seem a particularly 
hard-to-implement optimisation.

I should note though that multiple writes are not supported on newer MLC 
NAND flash. This could be an issue as this class of NAND may become more 
common. Perhaps in that case an obsoleted block can just be erased 
immediately.

Also, if scanning the medium for each block isn't as slow as I fear it may 
be, then the above may be unnecessary (although there's still a good 
argument for freeing up the OOB bits for later use, if they can be freed).

>  To be safe, we should impose an upper
> limit on the number of physical NAND blocks that this system will use,
> and hence cap the number of logical NOR blocks the system will support. I
> suggest 1024, which ought to be enough for anybody; it's more than many
> (most?) NOR chips.)

The number of blocks should be configurable anyway, so I don't think we 
need go beyond that surely? Setting a default of 1024 for such an option 
should be adequate.

> 2.4 Runtime considerations
> 
> If a runtime performance boost was required, the system could on startup
> scan the NAND partition and build up a cached mapping in-RAM of the
> physical addresses of each (non-zeroed) logical block. However, we don't
> expect this code will be used on gigantic NAND arrays [partitions],

Hmm. I'm not as certain about that. People like having lots of space to 
play in, with e.g. multiple app versions or linux kernel images or root 
fs's or initrd's to load etc. A linear scan will work ok on a brand new 
board for a while - starting the scan for the next block from the current 
block of course - but in due course, performance would deteriorate, mostly 
irreversibly.

> and it should only see light duty via RedBoot.

For a production system sure, but less so on a developer's board, with 
apps frequently getting written/rewritten. In particular the FIS directory 
updates will get interspersed frequently as a result which will cause 
increasing fragmentation. Put it like this - if you're considering 
something where wear-levelling is a concern (and for the mooted proto-fs, 
that's certainly valid), then you'd definitely need to consider the length 
of time scanning every block read as the block mappings will drift further 
away from 1:1 logical to virtual, and stop being linear.

> Therefore it won't take
> long to linear-scan for blocks during operations, so this optimisation
> may not be worth its complexity.

And 4Kbytes RAM (for, say, 1024 blocks).

> (Bart suggested that a scan at startup could also take care of the cases
> above where more than one physical block is tagged with the same logical
> block number, hence reducing the time and complexity of the block access
> code. There's a startup time vs access time vs memory trade-off here,
> though we haven't fully analysed it. Nick agreed that we ought to think
> this through very carefully.)

I think that being forced as a matter of course to scan the whole medium 
_every_ block read is a bad thing and should be avoided.


Something you may want to think about is that there are problems that 
RedBoot's FIS and config code have with multiple flash devices in a 
system. This may happen, whether with multiple NANDs or a mixture of flash 
types - possibly increasingly so these days. Work by myself and IIRC to 
some extent Bart at eCosCentric has ameliorated problems somewhat, but not 
fixed them. RedBoot's FIS code orients itself around a single flash 
device, with a single fixed block size for the entirety of that device. 
You may stumble across problems here as NAND may not be the only flash 
device on many boards, so it's something to bear in mind.

Jifl
-- 
--["No sense being pessimistic, it wouldn't work anyway"]-- Opinions==mine

Re: NAND "FIS" in RedBoot proposal

[Ross Younger]

Jonathan Larmour wrote:
>> The tag is a packed byte array, in processor-local endian, with the
>> following contents:
>>
>>     * Magic number - 2 bytes, 0xEF15. (This is a compile-time constant
>>     and demonstrates that the block is one of ours. It's a corruption
>>     of "eCos FIS".)
>>     * Logical block number - 2 bytes.
>>     * Master serial number - 4 bytes (see below).
> 
> Given you say processor-local endian, I assume you mean there are two 
> 16-bit words and a 32-bit word here.

Yes.


> Given you are assuming partial-page writes, I think you can do something 
> more intelligent here [...]
> When you write a new revision of a block, you mark 
> the previous one dead by overwriting it with a partial write (without 
> erasure).

I think there are too many overwrite-forbidding chips around for this to be 
a goer (including, inter alia, the one on my desk).

When I talked about partial-page reads and writes, I meant only that the 
NAND library would cope with being asked to read or write a non-integral 
number of pages; that it would do the right thing in terms of how many bytes 
it actually sent to the chip and computing/checking ECC.

 > I should note though that multiple writes are not supported on newer MLC
 > NAND flash. This could be an issue as this class of NAND may become more
 > common. Perhaps in that case an obsoleted block can just be erased
 > immediately.

We could indeed have a two-bit serial number per logical block and use that 
as a distinguisher, erasing the old copy immediately (hence the older serial 
number wins). However, dropping the master serial number means we can no 
longer detect which was the last block to be written (to the device as a 
whole), which I was relying on in order to set up my next-write-here pointer.

> - That frees up space which we can use for potential optimisations. In 
> particular, the common use-case we are envisaging is wholly sequential 
> reads of fairly large images. So we could use 2 bytes to point to the 
> next block in the logical block chain. This is very useful if most use 
> is sequential.

I'm not sure whether this gets us much. NAND blocks are commonly so large 
that I think that many applications will only ever be using a small number 
at a time?


Ross

-- 
eCosCentric Ltd, Barnwell House, Barnwell Drive, Cambridge CB5 8UU, UK
Registered in England no. 4422071.                 www.ecoscentric.com

Re: NAND "FIS" in RedBoot proposal

[Jonathan Larmour]

Ross Younger wrote:
> Jonathan Larmour wrote:
> 
>> Given you are assuming partial-page writes, I think you can do 
>> something more intelligent here [...]
>> When you write a new revision of a block, you mark the previous one 
>> dead by overwriting it with a partial write (without erasure).
> 
> 
> I think there are too many overwrite-forbidding chips around for this to 
> be a goer (including, inter alia, the one on my desk).

MLC?

> When I talked about partial-page reads and writes, I meant only that the 
> NAND library would cope with being asked to read or write a non-integral 
> number of pages; that it would do the right thing in terms of how many 
> bytes it actually sent to the chip and computing/checking ECC.

Ah. I thought you meant a separate write for the ECC (although it's true 
that I half-wondered why).

>  > I should note though that multiple writes are not supported on newer MLC
>  > NAND flash. This could be an issue as this class of NAND may become more
>  > common. Perhaps in that case an obsoleted block can just be erased
>  > immediately.
> 
> We could indeed have a two-bit serial number per logical block and use 
> that as a distinguisher, erasing the old copy immediately (hence the 
> older serial number wins). However, dropping the master serial number 
> means we can no longer detect which was the last block to be written (to 
> the device as a whole), which I was relying on in order to set up my 
> next-write-here pointer.

You could choose one randomly (the seed being the current usage pattern, 
to prevent repetition).

>> - That frees up space which we can use for potential optimisations. In 
>> particular, the common use-case we are envisaging is wholly sequential 
>> reads of fairly large images. So we could use 2 bytes to point to the 
>> next block in the logical block chain. This is very useful if most use 
>> is sequential.
> 
> 
> I'm not sure whether this gets us much. NAND blocks are commonly so 
> large that I think that many applications will only ever be using a 
> small number at a time?

Hmm, I think I was getting things a bit mixed up, since you had been 
talking about OOB data for each block, and that made me sometimes think 
about pages instead of blocks. But on rereading more carefully you do say 
about using the OOB data of the first page of each block. Since blocks are 
of the order of 256Kbytes then indeed the majority of the time we'd only 
need to consider up to say 8 blocks. So I think my concerns about scanning 
the medium diminish markedly.

Jifl
-- 
------["The best things in life aren't things."]------      Opinions==mine

Re: NAND "FIS" in RedBoot proposal

[Ross Younger]

>> I think there are too many overwrite-forbidding chips around for this
>> to be a goer (including, inter alia, the one on my desk).

Jonathan Larmour wrote:
> MLC?

Strangely enough, no... according to Samsung's own part number decoder, the
K9F1G08U0A in the EA LPC 2468 is SLC. Funny, I could have sworn it did
explicitly prohibit overwrites, but the datasheet - which I've just gone
back and checked - doesn't explicitly permit or prohibit overwrites.
Nevertheless I stand by my point - I think it would be foolish to design a
system targetting NAND that could never work with MLC chips.


Ross

-- 
Embedded Software Engineer, eCosCentric Limited.
Barnwell House, Barnwell Drive, Cambridge CB5 8UU, UK.
Registered in England no. 4422071.                  www.ecoscentric.com