Skip to contentSkip to conversation

Lifetime of flash memory

DISCUSSION [email protected] 8 participants 20 messages Mar 23, 2006 – Mar 30, 2006

lore
Share & tools
lore
#0 lore raw
Quoted 2 lines

I thought that journaling filesystems happen to overwrite exactly the same place (where the journal is) many times... Am I mistaken?

Sort of. The journal is much larger than a signle block, and used circularly, but it does get on average more traffic than the rest of the disk.

Quoted 6 lines

So the effect is what we had for floppies (some many years ago) where sector 0 and others where FAT structure was kept were overused and start giving errors - so the only solution was to throw away that floppy.

Hard disks had the same problem, but they have algorithms to relocate bad clusters.

Actually, hard drives shouldn't have the same problem. The key difference is that, on a floppy, the head touches the media, causing wear wherever it hangs out. The head is very smooth, so it's minor, but it happens.

On a hard drive, the head never touches the media. There is no wear. The magnetic writing happens across a very small air gap, and nobody's ever found a wearout mechanism for the magnetizing part of things, so you should be able to overwrite a single sector every rotation of the drive (120 times a second) for the lifetime of the drive (years).

Quoted 2 lines

So do these "leveling algorithms" refer to the same? Relocating bad cells? If not, you can see how a journaling system can fry a CF card quickly.

They do that, but they're also cleverer. Since flash media have no seek time, there's no reason that the sector number as specified by the computer needs to have anything to do with the physical location of the bits on the flash, and they don't. If you write to the same sector over and over, a flash memory device will do the write to different parts of the memory chip every time.

This is called "wear leveling" - trying to use all of the chip an equal amount. You'll see in high-density NAND flash systems there are actually 528 bytes per "sector". The extra 16 bytes are used to record:
- Whether this sector is still good or not
- The number of times this sector has been written
- The logical sector number of the data here

On startup, the first thing a thumb drive or CompactFlash card does is read the extra 16 bytes from every sector and build a translation map, so when a request for a given logical sector comes in, it knows where to find it. Note that there are more sectors on the ROM than on the hard drive it emulates, so there's always some spare space.

Further, when writing, occasionally a sector that's just sitting there not bothering anyone is copied, so that the flash it occupied can be used by faster-changing data.

(This is all complicated by the fact that, while you can *write* one 528-byte sector at a time, you can only write to an erased sector, and erases operate in bigger chunks, often about 8K. Thus, it's not physically possible to overwrite a 512-byte sector in place, even if you wanted to! So the controller is continuously picking an 8K chunk to re-use, copying any live data to a new chunk, and erasing it so it's available. For highest speed, you want to pick chunks to recycle that are mostly dead stale data, but for wear-leveling, you want to pick chunks that have a low cycle count. So you do a mix.)

See http://www.st.com/stonline/products/literature/ds/10058.htm and the various pages and papers linked to it for more detailed info. (Not necessarily the best-written or easiest to understand, but it's straight from a ROM manufacturer.)

As for the average lifetime, typical specs are either 10K, 100K or 1 million writes per sector. Basically, low-, normal- and high-endurance. Low-endurance is used for program memory, where you might reflash it a few times in the field, but aren't going to be using it continuously. 100K writes is the standard for data memory.

The denser the memory is, the lower the numbers tend to be. But you also have a bigger pool to spread the writes across. Some folks use multi-level cell memories, where instead of writing just 0 or 1, they add 1/3 and 2/3 values. That fits twice as many bits in, but wears out faster as it takes less degradation of the cell to read back the wrong value.

With perfect wear leveling, a 1 GB flash memory can thus have 100 TB written to it before bad sectors start becoming a problem. (And if you allowed more spare sectors to start with, you would have more time. One reason to integrate this into the file system and not emulate a fixed-size disk.)

Assuming 10 MB/sec write speed (typical for a USB thumb drive) that would require 10^7 seconds (115 days) of continuous full-speed writing.

So yes, a thumb drive isn't the best choice for on-line transaction processing. But with less than 24x7 usage, it'll last many years.

Note that, assuming a decent wear-leveling algorithm (admittedly, a big IF for some of the cheaper stuff out there!) it doesn't matter which sectors you write that 100 TB to. It could be all the boot sector, or sequential overwrites of the whole drive.

#1 lore raw
Quoted 5 lines · [email protected] wrote:

On startup, the first thing a thumb drive or CompactFlash card does is read the extra 16 bytes from every sector and build a translation map, so when a request for a given logical sector comes in, it knows where to find it. Note that there are more sectors on the ROM than on the hard drive it emulates, so there's always some spare space.

Hello,

some time ago I tried to find any documentation about CF internals, but failed. It seems like you may hint me where to find it, may you?

Signature · 3 lines
Best Regards,
Artem B. Bityutskiy,
St.-Petersburg, Russia.
#2 lore raw
Quoted 2 lines

some time ago I tried to find any documentation about CF internals, but failed. It seems like you may hint me where to find it, may you?

Sorry, I don't have anything in particular, just bits I've picked up talking to CF manufacturers.

Basically, a CF card is a flash ROM array attached to a little microcontroller with an IDE interface. The large manufacturers generally have custom controllers.

A basic block diagram is on page 3 (physical page 19) of the CompactFlash spec, available from
http://www.compactflash.org/cfspc3_0.pdf

#3 lore raw
Quoted 7 lines · [email protected] wrote:

Sorry, I don't have anything in particular, just bits I've picked up talking to CF manufacturers.

Basically, a CF card is a flash ROM array attached to a little microcontroller with an IDE interface. The large manufacturers generally have custom controllers.

I'm actually interested in:

1. CF wear-levelling algorithms: how good or bad is it?
2. How does CF implement block mapping, does it store the mapping table on-flash or in memory, does it build it by scanning, how scalable are those algorithms.
3. Does CF perform bad erasable blocks hadling transparently when new bad eraseblocks appear.
4. How tolerant CF to powrer-offs.
5. Is there a Garbage Collector in CF and how clever/stupid is it.

etc.

I've heard CF does not have good characteristics in the above mentioned aspects, but still, it would be interesting to know details. I'm not going to use CFs, but as I'm working with flashes, I'm just interested. It'd help me explaining people why it is bad to use CF for more serious applications then those just storing pictures.

Signature · 3 lines
Best Regards,
Artem B. Bityutskiy,
St.-Petersburg, Russia.
#4 lore raw
Quoted 3 lines · Artem B. Bityutskiy

I'm actually interested in:

1. CF wear-levelling algorithms: how good or bad is it?

Depends on the maker.

Quoted 3 lines

2. How does CF implement block mapping, does it store the mapping table on-flash or in memory, does it build it by scanning, how scalable are those algorithms.

Well the map has to be stored in flash or other non volatile memory.

Quoted 2 lines

3. Does CF perform bad erasable blocks hadling transparently when new bad eraseblocks appear.

No idea, but it is almost certainly also vendor specific.

Quoted 1 line

4. How tolerant CF to powrer-offs.

I have seen some that a power off in the middle of a write would leave the card dead (it left it with a partially updated block map). On others nothing happened (well you loose the write in progress of course just as a harddisk would).

Quoted 1 line

5. Is there a Garbage Collector in CF and how clever/stupid is it.

That is vendor specific. Depends how they did it. Different generations from a given company may also be different in behaviour. I imagine some parts of it are patented by some of the comapnies involed in flash card making.

Quoted 5 lines

I've heard CF does not have good characteristics in the above mentioned aspects, but still, it would be interesting to know details. I'm not going to use CFs, but as I'm working with flashes, I'm just interested. It'd help me explaining people why it is bad to use CF for more serious applications then those just storing pictures.

The wearleveling is not a part of the CF spec. So saying anything about CF in general just doesn't make much sense. It all depends on the controller in the CF you are using.

Len Sorensen

#5 lore raw
Quoted 38 lines · Lennart Sorensen
Quoted 3 lines · Artem B. Bityutskiy

I'm actually interested in:

1. CF wear-levelling algorithms: how good or bad is it?

Depends on the maker.

Quoted 3 lines

2. How does CF implement block mapping, does it store the mapping table on-flash or in memory, does it build it by scanning, how scalable are those algorithms.

Well the map has to be stored in flash or other non volatile memory.

Quoted 2 lines

3. Does CF perform bad erasable blocks hadling transparently when new bad eraseblocks appear.

No idea, but it is almost certainly also vendor specific.

Quoted 1 line

4. How tolerant CF to powrer-offs.

I have seen some that a power off in the middle of a write would leave the card dead (it left it with a partially updated block map). On others nothing happened (well you loose the write in progress of course just as a harddisk would).

Quoted 1 line

5. Is there a Garbage Collector in CF and how clever/stupid is it.

That is vendor specific. Depends how they did it. Different generations from a given company may also be different in behaviour. I imagine some parts of it are patented by some of the comapnies involed in flash card making.

Quoted 5 lines

I've heard CF does not have good characteristics in the above mentioned aspects, but still, it would be interesting to know details. I'm not going to use CFs, but as I'm working with flashes, I'm just interested. It'd help me explaining people why it is bad to use CF for more serious applications then those just storing pictures.

Quoted 5 lines

The wearleveling is not a part of the CF spec. So saying anything about CF in general just doesn't make much sense. It all depends on the controller in the CF you are using.

Len Sorensen

CompactFlash(tm) like SanDisk(tm) has very good R/W characteristics. It consists of a connector that exactly emulates an IDE drive connector in miniature, an interface controller that emulates and responds to most IDE commands, plus a method of performing reads and writes using static RAM buffers and permanent storage in NVRAM.

The algorithms used are proprietary. However, the techniques used are designed to put all new data into permanent storage before updating a block location table in static RAM. This table is built when a reset is sent to the device and dynamically as long as there is power to the chip. Destruction of this table will not lose any data, because it is built upon power-up from block relocation information saved in NVRAM. Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Experimental data show that it is not possible to 'destroy' the chip by interrupting a write as previously reported by others. In fact, one of the destroyed devices was recovered by writing all the sectors in the device as in:
dd if=/dev/zero of=/dev/hdb bs=1M count=122.

Note that there __is__ a problem that may become a "gotcha" if you intend to RAW copy devices, one to another, for production. The reported size (number of sectors) is different between devices of the same type and manufacturer! Apparently, the size gets set when the device is tested.

If you intend to make a bootable disk out of one of these, you need to make a partition that is smaller than the smallest size you are likely to encounter, on a 63-sector (virtual head) boundary. Otherwise, at least with FAT file-systems, the device will boot but file-system software won't be able to find the directory!

I have had very good results with these devices. My embedded software mounts the root file-system R/O with a ram-disk mounted on /tmp and /var. However, any parameter changes made by the customer require a mount change to R/W, then a change back to R/O. We thought that this was necessary. However, we have a two year old system that writes hourly data to R/W logs without any problems whatsoever. Basically, finite life is a fact, but you are unlikely to encounter it as a problem with real-world systems.

There are some 'Camera only' CompactFlash devices out there such as "RITZ BIG PRINT DIGITAL FILM" made by Lexar Media. The problem with this is that it's not 5-volt tollerant. I've found that if you plug this into an IDE converter/connector, it gets very hot and hangs the whole IDE I/O subsystem. It didn't burn out anything, however, and I was able to use it subsequently in my camera which uses only about 3 volts. So, before you actually purchase something for production stock, make sure that it works in your hardware.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.15.4 on an i686 machine (5589.42 BogoMips). Warning : 98.36% of all statistics are fiction, book release in April. _


****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

#6 lore raw
Quoted 5 lines · linux-os (Dick Johnson)

Experimental data show that it is not possible to 'destroy' the chip by interrupting a write as previously reported by others. In fact, one of the destroyed devices was recovered by writing all the sectors in the device as in:
dd if=/dev/zero of=/dev/hdb bs=1M count=122.

I have a destroyed card here. And I tried doing that. A rep from sandisk told me, that yes that model/generation of sandisk could encounter that situation where the device was simply impossible to access because of corruption during a write. He also said the card would have to be sent back to the factory to have the table reset. Newer generations were going to fix that so it didn't happen again.

Quoted 5 lines

Note that there __is__ a problem that may become a "gotcha" if you intend to RAW copy devices, one to another, for production. The reported size (number of sectors) is different between devices of the same type and manufacturer! Apparently, the size gets set when the device is tested.

Yeah, I load cards by partitioning, mkfs'ing, and extracting data. Different manufacturers almost never have the same excact size.

Len Sorensen

#7 lore raw
In reply to linux-os (Dick Johnson)

"linux-os \(Dick Johnson\)" <[email protected]> writes:
[...]

Quoted 1 line

CompactFlash(tm) like SanDisk(tm) has very good R/W characteristics.

Try to write 512-byte sectors in random order, and I'm sure write characteristics won't be that good.

Quoted 4 lines

It consists of a connector that exactly emulates an IDE drive connector in miniature, an interface controller that emulates and responds to most IDE commands, plus a method of performing reads and writes using static RAM buffers and permanent storage in NVRAM.

Are you sure they do have NVRAM? What kind of NVRAM? Do they have backup battery inside to keep NVRAM alive?

[...]

Quoted 3 lines

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Due to FLASH properties, it's a must to have ECC protection of the data on FLASH, and AFAIK 22-bits ECC is stored for every 256 bytes of data, so part of that extra memory on each page is apparently used for ECC storage taking about 24 bytes out of those 64. I have no idea how the rest of extra memory is used though.

BTW, the actual block size could be rather easily found from outside, -- just compare random access write speed against sequential write speed using different number of 512b sectors as a write unit. Increase number of sectors in a write unit until you get a jump in random access write performance, -- that will give you the number of sectors in the block.

[1] By application here I mean the code that works inside the CF card and deals with the FLASH directly. This memory is invisible from outside of CF card.

-- Sergei.

#8 lore raw
Quoted 5 lines · Sergei Organov
Quoted 3 lines · linux-os \(Dick Johnson\)

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Quoted 8 lines

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Doesn't this depend on if we are talking about NOR or NAND memory? It looks like you are describing some kind of NAND memory. Also I guess it varies with manufacturer.

When it comes to CF the internal block size doesn't really matter because the CF controller will hide it for you. The controller will perform some kind of mapping between the 512 byte based IDE-interface and it's internal sector size. This together with wear levelling.

The quality of the wear levelling will probably vary, but I guess even the most primitive brands have something to cope with the fact that the blocks containing the FAT are often rewritten on FAT filesystems.

/ magnus

#9 lore raw
Quoted 15 lines · Magnus Damm
Quoted 5 lines · Sergei Organov
Quoted 3 lines · linux-os \(Dick Johnson\)

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Quoted 8 lines

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Quoted 3 lines

Doesn't this depend on if we are talking about NOR or NAND memory? It looks like you are describing some kind of NAND memory. Also I guess it varies with manufacturer.

Yes, I talk about NAND FLASH as I've never seen CF cards based on NOR FLASH, -- NOR FLASH write times and capacities are just too poor, I think.

Quoted 4 lines

When it comes to CF the internal block size doesn't really matter because the CF controller will hide it for you. The controller will perform some kind of mapping between the 512 byte based IDE-interface and it's internal sector size. This together with wear levelling.

Yes, it will, but it can't entirely hide internal block size from you, -- just compare write times for random access against write times for sequential access. Old SanDisk CF cards based on NAND FLASH with 512b blocks had these times roughly the same, and all recent CF cards that I've tested have very big difference.

-- Sergei.

#10 lore raw
In reply to Sergei Organov
Quoted 7 lines · Sergei Organov

"linux-os \(Dick Johnson\)" <[email protected]> writes:
[...]

Quoted 1 line

CompactFlash(tm) like SanDisk(tm) has very good R/W characteristics.

Try to write 512-byte sectors in random order, and I'm sure write characteristics won't be that good.

Quoted 8 lines
Quoted 4 lines

It consists of a connector that exactly emulates an IDE drive connector in miniature, an interface controller that emulates and responds to most IDE commands, plus a method of performing reads and writes using static RAM buffers and permanent storage in NVRAM.

Are you sure they do have NVRAM? What kind of NVRAM? Do they have backup battery inside to keep NVRAM alive?

NVRAM means [N]on-[V]olatile-[RAM]. Any of many types, currently NAND flash. No battery required.

Quoted 15 lines

[...]

Quoted 3 lines

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Quoted 6 lines

Due to FLASH properties, it's a must to have ECC protection of the data on FLASH, and AFAIK 22-bits ECC is stored for every 256 bytes of data, so part of that extra memory on each page is apparently used for ECC storage taking about 24 bytes out of those 64. I have no idea how the rest of extra memory is used though.

Huh? There is no ECC anywhere nor is it required. The flash RAM is the same kind of flash used in re-writable BIOS, etc. It requires that an entire page be erased (all bits set high) because the write only writes zeros. The write-procedure is a byte-at-a-time and results in a perfect copy being written for each byte. This procedure is hidden in devices that emulate hard-disks. The immediate read/writes are cached in internal static RAM and an ASIC manages everything so that the device looks like an IDE drive.

Quoted 6 lines

BTW, the actual block size could be rather easily found from outside, -- just compare random access write speed against sequential write speed using different number of 512b sectors as a write unit. Increase number of sectors in a write unit until you get a jump in random access write performance, -- that will give you the number of sectors in the block.

Huh? The major time is the erase before the physical write, the entire physical page needs to be erased. That's why there is static-RAM buffering. It is quite unlikely that you will find a page size using any such method.

Quoted 6 lines

[1] By application here I mean the code that works inside the CF card and deals with the FLASH directly. This memory is invisible from outside of CF card.

-- Sergei.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.15.4 on an i686 machine (5589.42 BogoMips). Warning : 98.36% of all statistics are fiction, book release in April. _


****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

#11 lore raw
Quoted 14 lines · linux-os \(Dick Johnson\)
Quoted 12 lines · Sergei Organov

"linux-os \(Dick Johnson\)" <[email protected]> writes:
[...]

Quoted 1 line

CompactFlash(tm) like SanDisk(tm) has very good R/W characteristics.

Try to write 512-byte sectors in random order, and I'm sure write characteristics won't be that good.

Quoted 4 lines

It consists of a connector that exactly emulates an IDE drive connector in miniature, an interface controller that emulates and responds to most IDE commands, plus a method of performing reads and writes using static RAM buffers and permanent storage in NVRAM.

Quoted 6 lines
Quoted 3 lines

Are you sure they do have NVRAM? What kind of NVRAM? Do they have backup battery inside to keep NVRAM alive?

NVRAM means [N]on-[V]olatile-[RAM]. Any of many types, currently NAND flash. No battery required.

But NAND FLASH, while it is NV(Non-Volatile) *is not* RAM (Random Access Memory), sorry. So it seems there is no NVRAM inside CFs, right?

-- Sergei.

#12 lore raw
In reply to linux-os (Dick Johnson)
Quoted 1 line · linux-os \(Dick Johnson\)

On Mon, 27 Mar 2006, Sergei Organov wrote:

[...]

Quoted 1 line

Huh? There is no ECC anywhere nor is it required.

Really?! Read *any* specification of NAND FLASH then.

Quoted 1 line

The flash RAM is the same kind of flash used in re-writable BIOS, etc.

No, it is not. NAND FLASH is used in CFs while NOR FLASH is used in BIOSes.

Quoted 6 lines

It requires that an entire page be erased (all bits set high) because the write only writes zeros. The write-procedure is a byte-at-a-time and results in a perfect copy being written for each byte. This procedure is hidden in devices that emulate hard-disks. The immediate read/writes are cached in internal static RAM and an ASIC manages everything so that the device looks like an IDE drive.

What FLASH technology do you think CF cards are based on? It seems you think it's NOR FLASH, right? I believe you are wrong.

Quoted 11 lines
Quoted 6 lines

BTW, the actual block size could be rather easily found from outside, -- just compare random access write speed against sequential write speed using different number of 512b sectors as a write unit. Increase number of sectors in a write unit until you get a jump in random access write performance, -- that will give you the number of sectors in the block.

Huh? The major time is the erase before the physical write, the entire physical page needs to be erased. That's why there is static-RAM buffering. It is quite unlikely that you will find a page size using any such method.

Once again, you seem to assume NOR FLASH, and AFAIK that's not the case. For NAND FLASH block (128Kb) erase time is in order of 2ms, and write time is about 20ms.

-- Sergei.

#13 lore raw
In reply to Sergei Organov
Quoted 4 lines
Quoted 3 lines

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Quoted 8 lines

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Er, I think you know what you're talking about, but some people reading this might be confused by the Flash-ROM-specific meaning of the word "block" here.

In NAND Flash terminology, a PAGE is the unit of write. Thus was originaly 256+8 bytes, which quickly got bumped to 512+16 bytes. This is called a "small page" device.

"large page" devices have 2048+64 byte pages.
E.g. the 2 Gbyte device at
http://www.samsung.com/Products/Semiconductor/NANDFlash/SLC_LargeBlock/16Gbit/K9WAG08U1M/K9WAG08U1M.htm

Now, in a flash device, "writing" is changing selected bits from 1 to 0. "Erasing" is changing a large chunk of bits to 1.

In some NOR devices, you can perform an almost unlimited number of writes, limited only by the fact that each one has to change at least one 1 bit to a 0 or there's no point.

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Now, erasing is done in larger units called BLOCKs. This is more variable, but a power of two multiple of the page size. 32 to 64 pages (16 k for small page/32-page blocks to 128K for large page with 64-page blocks) is a typical quantity. You can only erase a block at a time.

So you really only need to keep track of wear levaling at the erase block level.

But any file system (or disk emulation layer) consists of having a free block at all times, picking a block to re-use, copying the still-needed data to the free block, and then erasing the new block. This leaves you with one completely free block, and hopefully a bit extra as the chosen block was not completely in use.

How you choose the blocks to re-use is the heart of wear leveling. For best efficiency, you want to re-use blocks that have the last still-needed (non-garbage) contents, but sometimes you have to copy a completely full block that's been sitting there not bothering anyone just because it has been sitting there and it's less worn out that the "busy" blocks.

In fact, such data should be copied to the most-worn blocks, since it will "give them a rest", while the least-worn blocks available should be used for new data. Since "most data dies young", it's likely that the new data block will have to be copied for garbage collection purposes. It can get very complex.

Oh, and just for the curious, let me explain the terms NAND and NOR flash.

The classic N-channel MOS transistor has three terminals: a source, a drain, and a gate. When the gate is raised to a positive voltage, it attracts electrons to the opposite side of the oxide insulator, and forms a conductive channel connecting the source and drain. Since they're negatively charged electrons, it's an N channel.

A positive voltage relative to what? Relative to the source and the drain, of course, since that's where the electrons have to be attracted from!

In many discrete transistors, there's a difference between the source and the drain, but the standard MOS IC process makes them completely symmetrical.

So an N-channel MOS transistor is good for connecting things to low voltages, but as the voltage gets closer to the gate voltage, the resistance increases until it cuts off. (Complementary MOS, or CMOS, technology combines this with a P-channel transistor with exactly the opposite properties to build devices that pass high and low voltages well.)

But still, you can build a good inverter out of an N-channel transistor by pulling the output up through a resistor or current source, and then, if the input to the transistor's gate goes high, the transistor (with its other end connected to ground) pulls the output low.

Now, if you connect multiple transistors to the same output line in parallel, any one of them turning on can pull it low. This is a NOR gate. NOR memory is built of rows and columns, and each column is a thousand-input NOR gate. Each input is a row, and then you select the column to find the

There are two ways to turn this into memory.

In dynamic RAM, each transistor is connected not to ground, but to a capacitor. When you turn it on, the capacitor might or might not pull the output low.

In programmable "read-only" memory, each transistor is connected to ground, but is made with a special "floating gate" that holds a small charge. This charge has the effect of altering the threshold voltage for the transistor. If the bit is programmed, the floating gate has a positive sharge on it, and it "helps" the main gate, so the voltage on the main gate needed to pull the output low is reduced. If the bit is erased, there's no charge, and the voltage needed on the main gate to pull the output low is higher.

To read a bit from the ROM, you feed a carefully chosen intermediate voltage down the row line, and the column line is pulled low (or not) depending on the programmed value.

Now, when you have an itty-bitty transistor trying to pull down a great big long (high-capacitance) column line, the actual effect it has is quite small. It'll get there eventually, but like pushing a car, it takes a quile to get started. There's a special circuit known as a "sense amplifier" that senses the very small effect it has and amplifies it to get the data out in a reasonable number of nanoseconds.

Okay, so that's NOR memory. Note that you have to connect three wires to each transistor: a row line, a column line, and ground. That takes a certain amount of space.

Now, go back to our original NMOS inverter circuit, with a pull-up resistor and a pull-down transistor. Suppose you added a second transistor, not in parallel with the first, but in series.

Then you'd have to turn on (supply a high gate voltage to) BOTH transistors to pull the output low. This is a NAND gate.

You can put a long chain of transistors together, and they all have to be on to pull the output low. You can't quite put thousands together, because a transistor isn't as good a conductor as a wire, but you can hook 16 together easily enough.

Now, take those 16, add a 17th transistor to hook the group up to a column line, and NOR together a pile of those groups.

You can read any transistor in a group by turning the other 15 (and the 17th) on all the way, and giving the selected transistor the halfway voltage to see how it's programmed.

Each group needs a single column line and a single ground, and each transistor needs a row line to drive its gate, but the sources and drains are simply connected to adjacent transistors.

This reduction of the wires per transistor from 3 to 1 + 3/16, and the fact that the 1 is the gate, which is already a metal wire in a MOS (metal-oxide-semiconductor) transistor allows a REALLY DENSE packing of the transistors, which is how NAND flash can fir more storage cells in than NOR flash.

BUT... even though you have to program the groups all together you can't read them all at once. Reading a group is a 16-step operation. You have to assign them adjacent addresses or programming would make no sense, but you can't read them all at the same time.

Thus, NAND flash is slower to read, but denser than NOR flash. The fact that manufacturing defects are allowed in NAND flash allows further density increases.

Quoted 5 lines

Due to FLASH properties, it's a must to have ECC protection of the data on FLASH, and AFAIK 22-bits ECC is stored for every 256 bytes of data, so part of that extra memory on each page is apparently used for ECC storage taking about 24 bytes out of those 64. I have no idea how the rest of extra memory is used though.

The "classic" ECC design is a simple Hamming code over 256 bytes = 2^11 bits. Assign each bit an 11-bit address, and for each of those 11 bits, compute two parity bits - one over the 1024 who have that address bit zero, and one over the 1024 who have that address bit 1.

If you have a single-bit error, one of each pair of parity bits will be wrong, with the combination giving the location of the erroneous bit. A double-bit error will leave some parity bit pairs both right or both wrong.

But more recent designs use 4-byte-correcting Reed-Solomon codes. For an example, see the ST72681 data sheet at
http://www.st.com/stonline/books/ascii/docs/11352.htm
This computes 10 ECC bytes per 512 bytes of data and can correct up to 4 errors, or correct 3 and detect up to 5, or any other combination where detect >= correct and correct + detect adds up to 8.

#14 lore raw
Quoted 13 lines · [email protected] writes:
Quoted 4 lines
Quoted 3 lines

Note that the actual block size is usually 64k, not the 512 bytes of a 'sector'. Apparently, some of the data-space on each block is used for relocation and logical-to-physical mapping.

Quoted 8 lines

Wrong. AFAIK, first disks had FLASH with 512b blocks, then next generation had 16K blocks, and currently most of cards have 128K blocks. Besides, each page of a block (64 pages * 2K for 128K block) has additional "system" area of 64 bytes. One thing that is in the system area is bad block indicator (2 bytes) to mark some blocks as bad on factory, and the rest could be used by application[1] the same way the rest of the page is used. So physical block size is in fact 64 * (2048 +
64) = 135168 bytes.

Quoted 3 lines

Er, I think you know what you're talking about, but some people reading this might be confused by the Flash-ROM-specific meaning of the word "block" here.

Yes, it's NAND-FLASH specific indeed, and block here means the unit of erasure, while page is a unit of write, as you carefully describe below.

Quoted 2 lines

In NAND Flash terminology, a PAGE is the unit of write. Thus was originaly 256+8 bytes,

Yes, with 2 pages per block, AFAIK, thus the block was 512 bytes and was equal to the sector size that is used in the interface of CF card. I indeed used a few of them and while their average write time was much worse than those with current technology, it was *much* more predictable due to the block size not exceeding interface sector size.

Quoted 1 line

which quickly got bumped to 512+16 bytes.

Yes, with 32 pages per block, thus the block became 16K.

Quoted 2 lines

This is called a "small page" device. "large page" devices have 2048+64 byte pages.

Yes, with 64 pages per block (typically?), thus the block became 128K.

BTW, it's a pity the information about physical block size is not accessible anywhere in CF interface.

Quoted 11 lines

E.g. the 2 Gbyte device
at
http://www.samsung.com/Products/Semiconductor/NANDFlash/SLC_LargeBlock/16Gbit/K9WAG08U1M/K9WAG08U1M.htm

Now, in a flash device, "writing" is changing selected bits from 1 to 0. "Erasing" is changing a large chunk of bits to 1.

In some NOR devices, you can perform an almost unlimited number of writes, limited only by the fact that each one has to change at least one 1 bit to a 0 or there's no point.

Quoted 6 lines

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Well, I'm not sure. The Toshiba and Samsung NANDs I've read manuals for seem to limit number of writes to a single page before block erase, -- is 512-byte portion some implementation detail I'm not aware of?

Quoted 4 lines

Now, erasing is done in larger units called BLOCKs. This is more variable, but a power of two multiple of the page size. 32 to 64 pages (16 k for small page/32-page blocks to 128K for large page with 64-page blocks) is a typical quantity. You can only erase a block at a time.

Typical? Are you aware of a "large page" NAND FLASH with different number of pages per block? It's not just curiosity, it's indeed important for me to know if there are CF cards in the market with physical block size != 128K.

[... skip interesting and nicely put details of NAND technology ...]

-- Sergei.

#15 lore raw
Quoted 10 lines
Quoted 6 lines

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Well, I'm not sure. The Toshiba and Samsung NANDs I've read manuals for seem to limit number of writes to a single page before block erase, -- is 512-byte portion some implementation detail I'm not aware of?

No. I just meant that I generally see "you may program each 2K page a maximum of 4 times before performing an erase cycle", and I assume the spec came from 2048/512 = 4, so you can program each 512-byte sector separately. I would assume if the page size were changed again, they'd try to keep that property.

E.g. from the Samsung K9K8G08U1A/K9F4G08U0A data sheet (p. 34):

PAGE PROGRAM

The device is programmed basically on a page basis, but it does allow multiple partial page programming of a word or consecutive bytes up to 2,112, in a single page program cycle. The number of consecutive partial page programming operations within the same page without an intervening erase operation must not exceed 4 times for a single page. The addressing should be done in sequential order in a block.
[...]
The internal write verify detects only errors for "1"s that are not successfully programmed to "0"s."

Quoted 9 lines
Quoted 4 lines

Now, erasing is done in larger units called BLOCKs. This is more variable, but a power of two multiple of the page size. 32 to 64 pages (16 k for small page/32-page blocks to 128K for large page with 64-page blocks) is a typical quantity. You can only erase a block at a time.

Typical? Are you aware of a "large page" NAND FLASH with different number of pages per block? It's not just curiosity, it's indeed important for me to know if there are CF cards in the market with physical block size != 128K.

No, I'm not aware of any violations of that rule; I just hadn't looked hard enough to verify that it was a rule, but I had seen the device ID bits that allow a wide range to be specified.

The "more variable" statement is really based on NOR flash experience, where it truly does vary all over the map.

Quoted 1 line

[... skip interesting and nicely put details of NAND technology ...]

Hopefully this makes descriptions like the start of the Samsung data sheet more comprehensible:

Product Information

The K9F4G08U0A is a 4,224 Mbit (4,429,185,024 bit) memory organized as 262,144 rows (pages) by 1,112x8 columns. Spare 64x8 columns are located from column address of 2,048-2,111. A 2,112-byte data register is connected to memory cell arrays accomodating data transfer between the I/O buffers and memory during page read and page program operations. The memory array is made up of 32 cells that are serially connected to form a NAND structure. Each of the 32 cells resides in a different page. A block consists of two NAND structured strings. A NAND structure consists of 32 cells. Total 1,081,244 NAND cells reside in a block. The program and read operations are executed on a page basis, while the erase operation is executed on a block basis. The memory array consists of 4,086 separately erasable 128K-byte blocks. It indicates that the bit-by-bit erase operation is prohibited on the K9F4G08U0A.

#16 lore raw
Quoted 7 lines · [email protected] writes:
Quoted 6 lines
Quoted 6 lines

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Quoted 8 lines
Quoted 3 lines

Well, I'm not sure. The Toshiba and Samsung NANDs I've read manuals for seem to limit number of writes to a single page before block erase, -- is 512-byte portion some implementation detail I'm not aware of?

No. I just meant that I generally see "you may program each 2K page a maximum of 4 times before performing an erase cycle", and I assume the spec came from 2048/512 = 4, so you can program each 512-byte sector separately.

I've a file system implementation that writes up to 3 times to the first 3 bytes of the first page of a block (clearing more and more bits every time), and it seems to work in practice, so maybe this number (4) came from another source? Alternatively, it works by accident and then I need to reconsider the design.

-- Sergei.

#17 lore raw
Quoted 16 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Quoted 8 lines
Quoted 3 lines

Well, I'm not sure. The Toshiba and Samsung NANDs I've read manuals for seem to limit number of writes to a single page before block erase, -- is 512-byte portion some implementation detail I'm not aware of?

No. I just meant that I generally see "you may program each 2K page a maximum of 4 times before performing an erase cycle", and I assume the spec came from 2048/512 = 4, so you can program each 512-byte sector separately.

Quoted 5 lines

I've a file system implementation that writes up to 3 times to the first 3 bytes of the first page of a block (clearing more and more bits every time), and it seems to work in practice, so maybe this number (4) came from another source? Alternatively, it works by accident and then I need to reconsider the design.

No, I'm sorry, I was still unclear. The spec is 4 writes per page. I believe that the REASON for this spec was so that people could write 512+16 bytes at a time just like they did with small-block devices and it would work.

But I do not believe there is any limitation on the pattern you may use, so your system should work fine.

What confuses me is that I thought I said (quoted above; paraphrasing here) "there is a very low limit on the number of times you may write to a page. That limit is large enough that you can do pagesize/512 = 2048/512 = 4 separate 512-byte writes." I didn't intend to imply that that was the ONLY legal pattern.

But from your comments, I'm getting the impression that you think I did say that was the only legal pattern. If that impression is correct, I'm not sure how you read that into my statements.

(I wonder if the actual limit is the number of writes per BLOCK, and they just expressed it as writes per page. I don't know enough about the programming circuitry to know what's exposed to what voltages. If the physics implied it, it would be useful flexibility for file system design.)

#18 lore raw
Quoted 22 lines · [email protected] writes:
Quoted 16 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Due to the multiplexing scheme used in high-density NAND flash devices, even the non-programmed cells are exposed to a fraction of the programming voltage and there are very low limits on the number of write cycles to a page before it has to be erased again. Exceeding that can cause some unwanted bits to change from 1 to 0. Typically, however, it is enough to write each 512-byte portion of a page independently.

Quoted 8 lines
Quoted 3 lines

Well, I'm not sure. The Toshiba and Samsung NANDs I've read manuals for seem to limit number of writes to a single page before block erase, -- is 512-byte portion some implementation detail I'm not aware of?

No. I just meant that I generally see "you may program each 2K page a maximum of 4 times before performing an erase cycle", and I assume the spec came from 2048/512 = 4, so you can program each 512-byte sector separately.

Quoted 5 lines

I've a file system implementation that writes up to 3 times to the first 3 bytes of the first page of a block (clearing more and more bits every time), and it seems to work in practice, so maybe this number (4) came from another source? Alternatively, it works by accident and then I need to reconsider the design.

Quoted 4 lines

No, I'm sorry, I was still unclear. The spec is 4 writes per page. I believe that the REASON for this spec was so that people could write 512+16 bytes at a time just like they did with small-block devices and it would work.

Ah, now (due to your explanation below) I see! But then how do you explain that those old "small page" devices do support multiple writes to a single page?

Quoted 9 lines

But I do not believe there is any limitation on the pattern you may use, so your system should work fine.

What confuses me is that I thought I said (quoted above; paraphrasing here) "there is a very low limit on the number of times you may write to a page. That limit is large enough that you can do pagesize/512 = 2048/512 = 4 separate 512-byte writes." I didn't intend to imply that that was the ONLY legal pattern.

Quoted 3 lines

But from your comments, I'm getting the impression that you think I did say that was the only legal pattern. If that impression is correct, I'm not sure how you read that into my statements.

Well, after your last explanation I'm not sure myself how I've read that into your statements ;)

Quoted 5 lines

(I wonder if the actual limit is the number of writes per BLOCK, and they just expressed it as writes per page. I don't know enough about the programming circuitry to know what's exposed to what voltages. If the physics implied it, it would be useful flexibility for file system design.)

I doubt block is relevant here, otherwise there seems to be no reason to introduce "page" as a write unit in the first place. It seems that write voltage is applied to entire page, and bit 1 in the data indeed leaks some charge (less than 1/4 of those bit 0 leaks). I think block in this context is mentioned only because it's impossible to erase single page.

-- Sergei.

#19 lore raw
In reply to [email protected]
Quoted 5 lines · [email protected] wrote:

On a hard drive, the head never touches the media. There is no wear. The magnetic writing happens across a very small air gap, and nobody's ever found a wearout mechanism for the magnetizing part of things, so you should be able to overwrite a single sector every rotation of the drive (120 times a second) for the lifetime of the drive (years).

Not for disk. When we were running early MULTICS on the mighty GE-645, paging was to a "firehose drum" which wrote either mainly or exclusively into one part of core memory, creating enough heat (according to the FEs) to cause very low MTBF on that box of memory.

Signature · 5 lines
Bill Davidsen <[email protected]>
  Obscure bug of 2004: BASH BUFFER OVERFLOW - if bash is being run by a
normal user and is setuid root, with the "vi" line edit mode selected,
and the character set is "big5," an off-by-one errors occurs during
wildcard (glob) expansion.