What about the flash patent?

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.