[cross-post] nand flash bad blocks management

Op Mon, 12 Jan 2015 10:23:24 +0100 schreef alb :

The second strategy is required when the total logical storage capacity must be constant. I can imagine the existence of 'bad sectors' degrading performance on some filesystems.

Sounds like you're re-inventing eMMC.

Indeed regular reading (and IIRC also writing) can increase the longevity of the device. But it is up to you whether that is needed at all.

AFAIK, (e)MMC devices all have a small microcontroller inside.>

--
(Remove the obvious prefix to reply privately.) 
Gemaakt met Opera's e-mailprogramma: http://www.opera.com/mail/

Hi Boudewijn,

In comp.arch.embedded Boudewijn Dijkstra wrote: []

Ok, that's a valid point, meaning that since I declare the user space only the total minus the reserved, the user may rely on that information.

But in terms of total amount of bad blocks for the quoted endurance will be exactly with the same number. None of the strategies mentioned wear less the device.

I didn't know there was a name for that. Well if that's so yes, but it's not for storing your birthday's picture, rather for space application.

Even if there are several 'experiments' running in low orbit with nand flash components, I do not know any operational satellite (like for meteo or similar) to have anything like this.

I'm not aiming to increase longevity. I'm aiming to guarantee that the system will cope with the expected bit flip and still guarantee mission objectives throughout the intended lifecycle (7.5 years on orbit).

Scrubbing is not so complicated, you read, correct and write back. But doing so when you hit a bad block during the rewrite and you have tons of other things to do in the meanwhile may have some side effects...to be evaluated and handled.

It does not surprise me, I have the requirement not to include *any* software onboard! I may let an embedded microcontroller with a hardcoded list of instruction slip through, but I'm not so sure.

Al

Um, *reading* also causes fatigue in the array -- just not as quickly as

*writing*/erase. In most implementations, this isn't a problem because you're reading the block *into* RAM and then accessing it from RAM. But, if you just keep reading blocks repeatedly, you'll discover your ECC becoming increasingly more active/aggressive in "fixing" the degrading NAD cells.

So, either KNOW that your access patterns (read and write) *won't* disturb the array. *Or*, actively manage it by "refreshing" content after "lots of" accesses (e.g., 100K-ish) PER PAGE/BANK.

I can't see an *economical* way of doing this (in anything less than huge volumes) with dedicated hardware (e.g., FPGA).

Indeed; my apologies. Performing many reads before an erase, will indeed cause bit errors that can be repaired by reprogramming. What I wanted to say, but misremembered, is that *not* reading over extended periods may also cause bit errors, due to charge leak. This can also be repaired by reprogramming. (ref: Micron TN2917)

Space exploration is not economical (yet). ;)

--
(Remove the obvious prefix to reply privately.) 
Gemaakt met Opera's e-mailprogramma: http://www.opera.com/mail/

Hi Don,

In comp.arch.embedded Don Y wrote: []

reading does not cause *fatigue* in the sense that does not wear the device. The effect has been referred to 'read disturb' which may cause errors in pages other than the one read. With multiple readings of the same page you may end up inducing so many errors that your ECC would not be able to cope with when you try to access the *other* pages.

These sorts of problems though are showing up when we talk about a number of reading cycles in the hundreds of thousands if not million (google: The Inconvenient Truths of NAND Flash Memory).

We have to cope with bit flips anyway (low earth orbit), so we are obliged to scrub the memory, in order to avoid errors' accumulation we move the entire block, update the LBA and erase the one affected, so it becomes again available.

Well according to our latest estimates we are about at 30% of cell usage on an AX2000 (2MGates), without including any scrubbing (yet), but including the bad block management.

Al

Yes, sorry -- I was being imprecise. My point was that it alters the data in the device in a manner that will eventually cause data LOSS. Of course, the effects are even more pronounced on MLC where the number of electrons is smaller for any given 'state'.

The numbers are only half the story. I can use a device for YEARS that exhibits problems after just *hundreds* of cycles -- if I don't burn those hundreds of cycles in those "years"! OTOH, something that will ONLY manifest after a million cycles can plague a design in *minutes* if the application hammers away at it.

That's why:

Bit flips can be handled probabilistically -- you can model how often you *expect* to encounter them on an OTHERWISE GOOD data image. OTOH, complicate that with a *dubious* data image and the reliability and predictability falls markedly.

Remember, if you are too naive in your implementation, you can increase

*wear*. I think to get a good algorithm, you probably want to track knowledge of the entire *device* -- not just the RECENT history of this block/page. (i.e., where did the page that *was* here go? and, why? if it had an unusually high error rate, you might not be so keen on bringing it back into the rotation -- ever!)

I.e., it seems like a lot of "state" to manage in a dedicated piece of hardware (that you can't *service*!)

Yes, its amazing how many of the issues that were troublesome in OLD technologies have modern day equivalents! E.g., "print through" for tape; write-restore-after-read for core; etc.

Wise ass! :>

Yes, I meant "economical" in terms of device complexity. The more complex the device required for a given functionality, the less reliable (in an environment where you don't get second-chances)

How are you going to configure your FPGA - is that going to be FLASH-based as well and, if so, could the configuration memory for the FPGA suffer from corruption?

--------------------------------------- Posted through

Hi,

srl100 wrote: []

In the current project we are using antifuse based technology so no concern for configuring the FPGA.

Even in the event of Flash based technology (ex. RT ProAsic) the flash cell is radically different from the one used for high density memories. First there's no need for high density and cell size is 0.25 um, not

16nm! Secondly there's no need to 'read' a flash cell in an flash based fpga, certainly there are limitation in the writing/erasure process which may cause wear due to tunneling of charge across the isolator.

Comning back to the point, NAND flash topologies have multiple nasty radiation effects that may increase the handling complexity (SEFI, SEU, SEL, to mention a few).

Considering the criticality of the function (we will store critical configuration to operate the mission successfully), I'd say it would be much more reliable to dedicate a software stack like a Flash Tranlation Layer (FTL) rather than do it with a - rather complex - state machine...but that is only guts feeling and making the call is not going to be an easy task.

Al

Correct. Since we will need to continuously scan for 'errors' (either induced by SEE or by 'Read Disturb' effects), is going to be unlikely that we will read 100K times before erasing.

Main issue to handle is a bad block when writing on a scrubbed area. We have lots of things to do and in the meantime we need to deal with a 'task' that is going to take a lot of push/pull activities on various busses.

[]

The advice is sound and we already assessed this in our feasibility analysis. There's not only the handling of the bad blocks that need to be done, but also the continuous correction of errors popping up here and there due to specific read patterns.

We foresee to retrieve few pages, or maybe few blocks each ~10 sec...I'm already around 3M/year readings, for a 7.5 year mission is a big number. Certainly impossible to avoid handling these effects.

Bit flips are handled by the ECC. The probability of events will only tell me how often they will occur and how often I should scrub the cells. If it is too often for the system to cope with I would need to employ an ECC that gives me the possibility to correct *multiple* bit flips, so that I can allow the recovery to take *more* time and still be protected.

[]

If I understand you correctly you're talking about wear-leveling. This is another aspect that needs to be addressed and can only come out of our radiation analysis. If the error rate we need to cope with will require a mean number of erase/program cycles that is larger than the allowed one, we are obliged to have some sort of mechanism to spread usage throughout the whole pool of available blocks and not just adjacent ones.

That said I'm start to wonder whether it would be more reliable to include a small footprint microcontroller (like an mb-lite) to handle the flash and provide a virtual device to the user(s).

Indeed the question could be made broader: what is more appropriate for the fpga to do and for the software to do in this specific use case? Considering the scenarios and the multiple decision points to implement, would a state machine be more appropriate than a software routine (procedure/function/algorithm/....)?

I could potentially delegate the fpga to routine tasks like moving/erasing/reading/writing blocks, while keeping the whole 'intelligence' (or stupidity!) in a more easy to handle software stack.

I think the customer should be involved in this reasoning and we should share the risk of the technical choice. Including a software stack would make the budget skyrocket but it should be put on the table somehow.

Al

--
A: Because it messes up the order in which people normally read text. 
Q: Why is top-posting such a bad thing? 
A: Top-posting. 
Q: What is the most annoying thing on usenet and in e-mail?

Hi Al,

[much elided; I've got a deadl>>> We have to cope with bit flips anyway (low earth orbit), so we are

My point was, you can design your ECC to deal with the sorts of error rates you expect from *functional* devices. If the integrity of the device is already suspect (because of usage patterns that lead to disturb and fatigue events), then the calculus gets more "interesting"... now you have to factor in the reduced reliability of the basic device *plus* any information you have as to how those additional errors are likely to manifest.

E.g., decades ago, we would design memory tests with the actual device geometry in mind -- so we could deliberately tickle the aspects of the memory (devices and array) that were most likely to give us trouble.

Wear leveling is a different issue. It *hopes* to "spread the pain" around the device.

But, consider this scenario:

A block gives you an excessive number of read errors (deal with the "write/erase" issue later). So, you schedule it to be "refreshed" (erased and rewritten). Note that this might also involve *replacement* depending on implementation. But, regardless, you (as an omnipotent human) can remember that it was *that* (physical) block that gave you the "problem".

Eventually, you reuse that block (again, depends on your algorithm; it might get reused for *this* "refreshed" data -- or, some other purpose). When it "gives you a problem" (again, we're just looking at READ errors to simplify the discussion), do you repeat the same handling practice that you did the *first* time you encountered a problem with the block? E.g., what if the *second* read from the block trips lost of ECC activity in that block? Do you use your knowledge of the fact that this block had previously "caused problems" to *bias* your decision to replace it *earlier* than you would some "less error prone" block? Do you ever mark the block as "bad" and take it out of service (because experience has taught? you that it's just going to end up being replaced *quickly*, AGAIN, when put back into service).

I.e., how much state can you afford to track AND BASE YOUR CONTROL ALGORITHMS ON before it becomes too complex for a "dedicated bit of control logic" (FPGA)?

I don't know the answer to this. I'm sure a lot of similar thinking goes into the design of flash controllers in SSD's, etc. But, they have an "out" that you don't -- the customer can replace an SSD that isn't living up to expectations "for very little money". You, OTOH, have a potential *asset* that they don't -- you *know* how you will be using YOUR memory and also know "what's important" therein. So, if pushed to the wall, can take steps to ensure what's important is preserved, regardless.

Well, anything that you could do with a microcontroller can also be done with logic (just design one and an instruction store! :> ) You might, however, find it easier (and more economical) to implement a "sequential machine" to make it easier for folks to implement these sorts of things (people think much better serially than in parallel; and, there probably is no real need for parallelism, here!)

The *first* thing I would do is get some big (technical) muck-a-mucks from the memory supplier in and hammer them with what-if's. Depending on how much of your design you can freely "share", they may be able to offer you some simple guidelines that make a world of difference in the performance you can expect *and* the methods by which you manage (and measure) that performance. They may even have some IP that they can share with you. Or, put you in touch with some *other* customer that might be able to assist you better (e.g., an SSD manufacturer).

The first part of the journey is KNOWING the problem...

your follow-up is much appreciated.

[]

Correct. The device shows nominally some sorts of 'failures' that I need to deal with, plus some of them which are A. difficult to categorize because radiation tests on a *black box* don't provide details on the mechanism (manufacturers have the /tendency/ to keep secrets on what's inside) and B. there's no much data available yet (therefore we might need to perform additional radiation testing and analysis).

IMO there are two aspects: the memory test and the memory controller test. Testing the memory and see if it can handle memory usage patterns is a different matter and is out of the context of this thread. We want to test the controller, because the component itself is qualified by the manufacturer. Moreover we want to test the controller when the memory is showing all possible scenarios we have anticipated (and designed to handle) and maybe more.

While injecting errors in the memory content is achieved simply bypassing the ECC, simulating a bad block is not trivial unless a 'crash test' is foreseen and behavior is recorded and analyzed.

I'd be interested to read some articles/opinions on the matter if anyone here has some experience.

[]

Uhm, wear leveling algorithms do not *hope* anything, actually they spread the maximum allowed number of E/P cycles all over the device instead of a single block, since endurance is defined _per block_.

You count the number of E/P cycles each block has accumulated and you choose to write data in available blocks with the least lived E/P cycles (for example). The E/P cycles available become effectively multiplied by the number of available blocks.

Another simple wear leveling approach would be to select randomly among the pool of empty blocks. This technique does not require any 'counting' and is simple enough to implement (seeding the pseudo-random generator with a monotonic parameter like time, in order to avoid to repeat the same 'pseudo-random' sequence).

[]

Depending on your ECC there might be a limited choice, i.e. assume your ECC recovers only one bit flip and report multiple ones. Whenever I detect (and correct) *one* single error, I have no other choice but to act otherwise, if I wait too long my ECC won't help me anymore.

What to do then? Well here as well there are not so many possible actions:

1. move the content somewhere else (contributes to wear leveling)
2. refresh the data in place

OTOH if the ECC allows you to recover multiple bits, you may still end up with the same logic, but instead of acting on the first error detected *and* corrected, you would act on the 27th!

There are attempts to show some sort of error patterns that are more likely to show up and hence can be managed accordingly, but I'm a fond of the K.I.S.S. principle and I'm not so much interested in building a read/write patterns aware wear leveling algorithm :-).

Remember also that commercial use cases are far different from HiRel ones. Even though your usb flash is rated for 30K cycles we go way beyond that limit and nothing happen until something is really not working.

We have the part stress analysis which verifies if we are using the device beyond the manufacturer's maximum limits.

That is exactly why we want to clearly define the scope and the capabilities that we are able to implement in an FPGA and let the customer mitigate the risk of failure at his level (FDIR at system level).

[]

The advantage of the microcontroller is not the hardware it represents but the languages that can be used to instruct it. I see easily how moving a buffer from one point to another is a perfect task for an FPGA, dealing with low level protocol with the Flash Interface, but taking the decision about what to do on a failure is where the software has an added value and can be 'economical' and possibly more reliable given that the complexity it can handle is certainly superior (I doubt I'd be able to write a journalized flash file system with bad block management, wear leveling, scrubbing and garbage collection within an FPGA!).

But it's easy to reason in terms of extremes, where it's obvious what to do. What I find difficult is to find the right level of complexity where it'd be better to split the task in two subsystems, the sw and the fpga.

[]

That is indeed an extremely good idea. Not sure though how much *they* are willing to share...but definitely worth asking.

Al

In an ideal world (process), all blocks would be identical in terms of performance, durability, etc. In that case, you can trivially cycle locks through the algorithm in any "fair" order and never see any difference in performance (i.e., durability/error resistance).

However, processes aren't ideal. And, data "patterns" only add to the uncertainty. You can't *know* that each block -- having ALL been "recycled" exactly N times -- will exhibit the same sorts of "read failures" (again, just talking about reads to simplify the discussion) when asked to store a particular data pattern (in the context of the *other* data patterns located "around" it).

You should be able to test this by deliberately exhausting some sample devices and/or partial writes (cut the write timer short, deliberately) to *some* blocks but not others. I.e., don't let entropy average all of that out across the device. *Then*, try to use the device with a "fair" block swapping algorithm and track how long each *actual* (physical) block "survives" (provides reliable data below ECC threshold that suggests a need to rescrub) before your controller decides that it needs to be "recycled" -- erased and rewritten (or, reused to replace another block).

If you can associate a metric with each physical block that represents its historical performance, you can "level" based on *performance* instead of

*use*.

I.e., one leveling algorithm just moves recycled blocks to the end of the queue and always picks the first block in the queue for use when some existing block needs to be recycled out of service. This ensures each block gets *erased* the same number of times -- regardless of how long a particular physical block "survived" IN ITS MOST RECENT (or sum of all preceding) USE.

You could, instead, track the number of *reads*-before-error-limit for each block and arrange for those with the highest "durability" to be reused *first*. Over time, their performance will degrade (i.e., they will start to exhibit more errors, sooner) so that some other block that had previously been considered "less durable" is regarded as MORE durable than this "worn" block.

[Sorry, I'm being verbose but I don't feel I'm being *clear*. :< ]

I'm oversimplifying this as there are other issues related to geometry that play a part. My point is to show that *how* you choose to reuse blocks can be implemented in different ways with different criteria. The point being that you want to minimize the number of "recycle events" that you take on -- especially if the block you *pick* as a replacement block may not write properly... so, you end up with a "double fault" of sorts.

That's the "each block gets erased the same number of times" approach I described above. Wouldn't you rather find a set of blocks that *needs* to be erased the least number of times??

This depends on the nature of the source of your errors. E.g., do you replace the RAM in your PC when it reports *any* CORRECTED errors? (I've asked this question before and its fun to watch people try to rationalize how they use that "feature" -- do they even *know* when there are error events being corrected? when do they decide there are "too many"?)

I.e., if you are looking for *any* error to indicate a lack of trust in your data, then you might want an ECC that could correct one and *detect* ANY NUMBER (many polynomials will only reliably detect a certain number of errors; beyond that, the data "looks" OK -- even if it is rife with errors!)

"In place" is essentially preselecting the *same* block for use with the "new" (which is actually "old"!) data.

The resource that you can't exhaust is write-erase cycles. So, you really want to come up with an algorithm that minimizes the number of times you "give up" on a written block -- in favor of refreshing it here or elsewhere. That's why I was saying (earlier) to rethink your algorithm to track "measured durability" (i.e., how *long* before errors detected) and use that to govern the selection of replacement blocks -- instead of just a FIFO (or even random) algorithm.

Exactly. As I said, hardware is great for parallel operations. But, when the algorithm being implemented is thought of in a serial fashion, it is often easier to resort to a sequencer -- a microcontroller. WHEN this happens, do that... UNLESS this other thing happens, in which case...

Good luck! I've got to bring another server on-line tonight so I can dispose of its predecessor this weekend!

I'm curious: is random selection better than a simple increase (with wrap-around)?

--
(Remove the obvious prefix to reply privately.) 
Gemaakt met Opera's e-mailprogramma: http://www.opera.com/mail/

I would suspect *not*.

First, what constitutes "random"? How do you ensure that the results truly

*are* "random"? Over what interval?

And, what are the consequences of "random but unfortunate" picks. E.g.,

587111111111111111110345... can be random digits. OTOH, if the selection indicated by each digit were applied to something that had a life expectancy of "10 invocations", that string of 17's ones could prove problematic!

I think Al is better served by a more deterministic algorithm. Esp in light of the fact that he doesn't really get a second chance at this!

[Randomness is an interesting concept. In gam[bl]ing devices, there's always the issue of "how random is random". If a video poker game dealt four successive royal flushes, you'd be hard pressed convincing ANYONE that this was a "random" event! OTOH, if the player was going to be seated there for another 1,000,000 hands (in which he NEVER sees another royal flush), this might be acceptable!]

Clear or not, the message is getting through. :)

If I get it: instead of assuming all the blocks are created equal, assume blocks are different and have the algorithm treat different blocks differently.

Perhaps, instead of tracking block history (for every block - with info stored where?), an algorithm can be made that uses a "descriptor" of sorts to inform its thinking about blocks. So, instead of the algorithm making notes about unreliable blocks, it gets them hardcoded from the programmer.

I'm absolutely not sure how would you generate that descriptor. Especially if you assume every device is different.

>

Well, all blocks are *never* completely "equal". There are always variations. My point is to monitor performance (with metric) and use that to bias block selection to favor those that (have) "perform(ed) best" -- from among those available for use.

I don't think it can be as simple as that. It's not like you know that "this block is BAD". Rather, this block is *better* (than those others).

Furthermore, it isn't a static quality.

The data *in* the block will determine how likely it is to create a particular error (again, looking just at read operations). And, how "worn" the individual cells within that block are -- how well they can hold/isolate charge on their respective gates.

But, also, the access patterns of blocks "electrically adjacent" (poorly defined concept) will determine the likelihood for a read disturb event to corrupt the data in *this* block.

As those read patterns may change over time, *one* (actually identical in terms of reliability!) block may appear worse than another *now*, yet, when the access pattern changes, the "other" may appear worse. Despite the fact that both are actually "equally reliable".

Likewise, the number of write-erase cycles fatigues the cells in the block. I.e., there are lots of factors that influence how well a given set of cells can hold data.

You would need to know a *lot* about your application's access patterns

*AND* couple that with knowledge of your block replacement algorithm to be able to determine "at design time" where the "most vulnerable" blocks were (physically) located.

Instead, I'm suggesting you simply measure how well this block is performing with *these* contents, some previous number of write-erase cycles as well as the "neighboring data access patterns", happening

*now*. Assuming failures *slowly* creep into the data, then just *wait* until you get your first (Nth?) ECC event before recycling the block. But, recall how well it performed (how many read cycles before it's contents were noticeably disturbed -- to the point where the ECC had to step in!).

Use this information to adjust your "block selection" algorithm when you need to recycle/refresh a block -- later.

As conditions (local to each particular block) change over time, the "performance" of individual blocks will also change. They will rise and fall in the list of "best performing blocks" to reflect that performance.

I've no idea how well this would perform in any *particular* application. You can bet the folks who build SSD's try hard to refine these sorts of algorithms so they can keep their margins high, costs low and performance up! (and, hopefully, without the complexity of the housekeeping leading to lots of errors in the implelmentation!)

Another approach is simply to over-provision the hell out of things and hope for the best! :>

In terms of spreading usage across the device the main difference between a simple increase and wrap-around and a random choice is across power off/on cycles.

In the first case you would need to store somewhere in your flash memory where was the last pointer for your 'increase and wrap-around' algorithm, while in the second case you simply don't.

The reduced amount of metadata management can simplify the task and reduce complexity.

Moreover, while in a perfect world power outages are maybe not considered, the simple fact that power is cut while you want to store your metadata may screw your 'increase and wrap-around' algorithm and you'll have uneven usage, while a random approach would simply not care.

Al

The "wear" (from the "read disturb") comes because those blocks eventually get recycled and incur write-erase cycles.

You can't claim that the "preferred" blocks will see more wear -- there are other blocks IN USE that are "less preferred". Presumably, they are less preferred because they trip the ECC *EARLIER*. As such, they will experience a recycle event *sooner* than the "more preferred" blocks (because the more preferred blocks trip the ECC less often).

Think of it this way: you have N blocks in the device. You need M (M> [Sorry, I'm being verbose but I don't feel I'm being *clear*. :< ]

All I'm changing in the algorithm is the "block selection algorithm" -- how you pick *which* block to use from your overprovisioning store to handle the *next* "recycle" event. If *it* fails the write, then you pick another block -- using the same criteria. I.e., how you handle an ECC event *or* a write-fault doesn't change -- just how you *pick* which block to use for your recovery attempt after such an event.

You're not "wearing" them faster (see above).

Given: You are going to perform N reads in some unit of time/effort. The goal is to minimize the number of read errors that you encounter. Read errors lead to write-erase cycles (recycle events) which cost resources (time/performance) AND reduce the overall durability of the device. Wouldn't you *naturally* want to pick the blocks that give you the least number of read errors AND, thus, recycle events?

The point of my parenthetical comment was: "How do you decide when the ECC is *too* active? What criteria do you use to determine that errors may be slipping through undetected? How do you (PC user) even KNOW that this is happening??

When you run out of write-erase cycles, your "recycle" events (or, write events) start failing. The point of my "read history" metric is to keep blocks from going *through* write-erase cycles needlessly (i.e., if a particular block isn't giving you ECC errors, why rewrite it? Why incur that "wear event" if not needed? Similarly, why not pick blocks that don't need to be rewritten as frequently if you have such a metric?

[The point of my initial comment was to suggest that these algorithms are too complex to implement in dedicated logic. Esp if you are trying to get the best (most reliable) performance from the array.]

Each write-erase cycle alters the characteristics of the cells in the block. I.e., "wear" is nonreversible. As a cell wears, it is less capable of preserving the correct state of charge (i.e., storing the desired "data") This manifests as a greater susceptibility to disturb events (read/write) and an earlier ECC event. I.e., "time til ECC event gives you a practical way of measuring how "reliable" a particular block is GIVEN YOUR USAGE PATTERNS.

This should be easy for you to test. Pick a block and run a bunch of write-erase cycles on it. I.e., pre-wear THAT block so it is expected to have less useful life than other blocks in the array. Now, apply an algorithm and watch to see how well *it* performs compared to other "unworn" blocks (accelerated wear testing). See which blocks get marked as permanently bad, *first* using a "fair" algorithm. Similarly, track the number of recycle events that you incur.

Then, tweek the algorithm to alter the recycled block selection choice and see how the performance changes (do you get more use from the array? fewer recycle events? more total life before blocks are considered "bad"?)

[snipped line length]

The difference that I am highlighting is the range of algorithms that are EFFECTIVELY available to each type of implementation (software FTL vs. dedicated hardware). Duality ensures you can implement any in

*each* approach. But, getting it *correct* is a different matter...