Weekly edition	Kernel	Security	Distributions	Contact Us	Search
Archives	Calendar	Subscribe	Write for LWN	LWN.net FAQ	Sponsors

What about the flash patent?

Posted Mar 3, 2009 8:35 UTC (Tue) by njs (guest, #40338)
Parent article: Third time is the charm?

All the discussion of the vfat patents is interesting, but I was hoping on LWN we might hear more about 6,256,642 too... because among all the copious discussion of this case, the only real mention I've seen of it is Greg K-H saying it's the one that worries him most:
http://thread.gmane.org/gmane.linux.elitists/12758/focus=...

I have no idea, for instance, whether there is prior art; were people even using flash filesystems in 1992? (Note also that while filed in 1992, it wasn't granted until 2001, so IIUC that means prior art has to be found very early, but the expiration still isn't until 2018.)

(Log in to post comments)

Posted Mar 3, 2009 9:46 UTC (Tue) by dlang (✭ supporter ✭, #313) [Link]

that isn't a problem directly for linux today because linux today doesn't have access to the raw eraseblocks, it's accessing the flash through a layer that hides this from the OS (at least on commodity hardware, there are probably some special cases where the raw flash is exposed, but not very many of them)

this isn't saying that it won't impact linux, but it will do so by making all the hardware that implements the translation layers more expensive, not by putting a price on the linux software.

it may have an impact for some future filesystems that are aiming at directly managing the flash (implementing wear leveling, etc), but I don't know of anything currently in the kernel that manipulates eraseblocks.

David Lang

What about the flash patent?

Posted Mar 3, 2009 11:39 UTC (Tue) by leromarinvit (guest, #56850) [Link]

Huh? Why wouldn't jffs(2) and ubifs count? Just about any embedded device talks directly to the flash chips, translation layers are only used for USB/SATA/IDE flash drives and memory cards. Or do you mean something else?

What about the flash patent?

Posted Mar 3, 2009 12:09 UTC (Tue) by dlang (✭ supporter ✭, #313) [Link]

I forgot about jffs, and I didn't think that ubifs was in the kernel yet.

What about the flash patent?

Posted Mar 3, 2009 15:08 UTC (Tue) by corbet (editor, #1) [Link]

The flash patent is problematic, and I did kind of gloss over it. Any flash array that comes with a translation layer is not an issue - or, more to the point, it's an issue for the people who shipped the FTL. But embedded systems, in particular, do deal with flash without a translation layer using filesystems like yaffs, jffs2, and UBI (UBI being, essentially, a flash translation layer).

My immediate sense is that this patent fails the obviousness test. You have an operating system working with one block size, and a storage system which forces a much larger block size. Of course you need an impedance-matching layer in the middle. This was inherent in the medium from the release of the first array. But, of course, I'm not the person you want to get that sort of advice from...

What about the flash patent?

Posted Mar 6, 2009 0:43 UTC (Fri) by wookey (subscriber, #5501) [Link]

I've just read 6,256,642, and so far as I can tell it doesn't cover YAFFS (the flash FS with which I am most familiar), because it talks about a block being an erase block and there being one allocation table per block. YAFFS doesn't have an allocation table as such, nor does it have on-flash per-erase-block structures. Each flash page (512bytes or 2K, an erase block is more like 32-128K) has associated tags in the OOB area describing which bit of the filesystem it is in (file ID, chunk ID). It is truly log-structured: There is no allocation table on the flash. I don't think JFFS2 has such a thing either, but I've never looked in detail. LOGFS is different from other flash FSes in that it does have on-flash tables, so it _might_ be at risk, but only if there is one allocation table per erase block. It is designed to work where the erase-block size is not known, so this may well not be the case.

TomTom had their own flash fs NGFFS (or some similar name, written by Koen Martens) for small amounts of (config/boot) data in internal flash. For bulk (map and OSimage) data they used an internal CFcard/drive or external MMC. CF/IDE devices dont give access to flash blocks directly, and I don't think MMC does either (only Smartmedia and xD work that way), so normal block FSs are used (see FAT patent).

I know Koen was part of the 2004/5 EU swpat fight so no doubt he'll be taking a look at this. Of course TomTom have had several generations of kit since then and could easily be using other flash FSs by now (JFFS2, YAFFS2, UBIFS, LOGFS are the candidates), if they have significant amounts of raw internal flash. The last two are too new (ubifs arrived in mainline in 2.6.27, and logfs isn't there yet) to be in many shipping devices. (YAFFS isn't in mainline either yet, but it has been shipping in devices since 2002).

There are plenty of other patents on flash filesystems, including several on FTL-type systems owned by the Israeli outfit M-systems (acquired by Sandisk in 2006), and many more at Samsung and Intel.

People were publishing papers on flash filesystems in 1992: (see references in http://epos.lisha.ufsc.br/wpkg/trier.html ), but Microsoft did have one of the first flash filesystems (FFS2) around that time, which I guess is where this patent came from.