Flash and small modifications [LWN.net]

Flash and small modifications

Posted Apr 6, 2012 21:08 UTC (Fri) by jzbiciak (guest, #5246)
In reply to: Flash and small modifications by dlang
Parent article: 2012 Linux Storage, Filesystem, and Memory Management Summit - Day 2

Now, bear in mind my direct experience is mainly with writing low-level flash code on microcontrollers with on-chip flash. But, I can't imagine it's terribly different than the much higher density mass storage flash.

I'll use "set" and "erase" to describe the operations on bits below. In typical flash, "erase" clears the bit to 1, and "set" deposits a charge and causes it to read as 0. Or, you can flip those around with "erase" leaving a 0 and "set" leaving a 1. Either way, the principle holds, and is the same principle you were highlighting.

The flash I've worked with puts an upper bound on the number of times you can set the same bit without an intervening erase cycle. This makes a certain amount of sense to me. The process of flipping a bit from erased to set deposits electrons onto an otherwise-floating transistor gate. Setting the same bit more than once could threaten to break down that gate prematurely by depositing too much charge. At least, I guess that's the reason behind the admonition to not re-program a given word more than once.

That said, write blocks tend to be much smaller than erase blocks, so that does give you some flexibility. So, while a given bit can only be "set" a certain number of times, the hardware generally gives you some granularity to avoid setting it too often.

Anyway, that constraint can limit the number of times you can "modify in place" a given block, and limit the ways in which that modification could be carried out. To me, the most interesting scenario is the "append to log" scenario. This one seems most compatible with the underlying physics. It does require the filesystem to pad sectors beyond EOF with an appropriate value for rewriting later. For example, if flash needs 1s, then the portion of a sector beyond EOF written by the filesystem needs to be 0xFF.

As far as checksums go, if you go with CRCs, they have a really nice property: They're fully linear codes. The CRC for a given block of data is equal to the XOR of the CRCs for each of the 1 bits in that block if you were to assume the other bits were zero. (Assuming no pre/post inversions.) That is, suppose you wanted to CRC this string: 10010001. Then: CRC(10010001) = CRC(10000000) ^ CRC(00010000) ^ CRC(00000001).

So, you could protect a block of data that's updated in this way by just appending the CRC of the delta to the "CRC list". The reader would then need to XOR all of the provided CRCs. Now, if your flash erases to 1 and sets to 0, then you could store CRCs inverted, with the unused CRCs reading as 0xFFFFFFFF. The reader wouldn't even have to know how many CRCs are valid at that point -- it could just read them all in and XOR them. If there's an even number of potential CRCs (as seems likely), the reader wouldn't even need to apply any inversions.

to post comments

Flash and small modifications

Posted Apr 6, 2012 22:08 UTC (Fri) by dlang (guest, #313) [Link] (2 responses)

I was thinking of taking the easy way out and just saying "use the most recent checksum" rather than doing any fancy chaining of the checksums togeather.

But overall I think that we are talking basically the same thing.

I first ran into this sort of concept many years ago when the digital recording first hit the consumer market (if you can remember when the first music Christmas cards and similar appeared, that timeframe). The way those recorders worked was that they used a EEPROM chip and recorded an analog value (~8 bits worth) in each bit of the EEPROM by hitting it with a smaller than spec programming charge repeatedly until the stored value matched the desired analog value. When doing this program you would 'program' the chip with 00000001 until the first bit got to the desired value, then program it with 00000010 until the second bit got to the desired value, etc. you would never be sending a programming signal to a bit that you already had set.

multi-level flash uses a similar trick to store 4 levels of signal per cell, it calls these '00' '01' '10' '11' in the digital world, so the 'partial modification' that I am talking about would require support from the flash chipset to allow it to not try to reprogram a cell that's already been set, but that is a pretty trivial thing to do.

Flash and small modifications

Posted Apr 6, 2012 22:46 UTC (Fri) by jzbiciak (guest, #5246) [Link] (1 responses)

Where I think the overlaid CRCs might become more interesting is when the CRC is supposed to cover a fairly large block (say 64K) but you're rewriting a much smaller piece (say 4K) with a minor update. If you don't have the other pieces handy, you can compute your CRC update on just the piece you have, rather than having to go read them.

Flash and small modifications

Posted Apr 6, 2012 23:02 UTC (Fri) by dlang (guest, #313) [Link]

true, but if you think of the fact that it's only the on-device controller that would have to re-read the data, I don't think it really matters, the speed that it can re-read the raw data is fast enough that I really don't expect it to be a bottleneck.