|
|
Subscribe / Log in / New account

Third time is the charm?

Please consider subscribing to LWN

Subscriptions are the lifeblood of LWN.net. If you appreciate this content and would like to see more of it, your subscription will help to ensure that LWN continues to thrive. Please visit this page to join up and keep LWN on the net.

By Jonathan Corbet
March 2, 2009
Almost two years ago, your editor sat on an Open Source Business Conference panel with Microsoft's Sam Ramji, who made the point that Microsoft had only launched patent infringement lawsuits twice in its existence. Given that, worries about the Microsoft/Novell patent deal were, in his opinion, misplaced. Last week, it was revealed that the count has gone up to three: Microsoft has filed a lawsuit against TomTom, a maker of Linux-based navigation devices. There is much speculation and uncertainty on the net as to just what this action means. Your editor means to add to it by saying that Microsoft's intentions would appear to be relatively clear.

The patents which TomTom is alleged to be infringing are:

  • 6,175,789 (Vehicle computer system with open platform). This patent, filed in 1999, covers the innovative concept of mounting a computer in a vehicle dashboard. Literally, that is all there is to it.

  • 6,202,008 (Vehicle computer system with wireless internet, 1999). This one extends the previous patent by adding an Internet connection to the dashboard-mounted computer.

  • 7,054,745 (Method and system for generating driving directions, 2003), appears to cover the basic turn-by-turn instructions provided by just about any navigation unit on the market.

  • 6,704,032 (Methods and Arrangements for Interacting with Controllable Objects within a Graphical User Interface Environment Using Various Input Mechanisms, 2000). This patent is relatively impenetrable, but appears to cover a framework for binding responses to user interface events.

  • 7,117,286 (Portable computing device-integrated appliance, 2005). The deep concept here appears to be recognizing a docking station and causing the user interface to configure itself accordingly.

  • 5,579,517 (Common name space for long and short filenames, 1995) and 5,758,352 (Common name space for long and short filenames, 1996). These are the infamous patents on the long filename hacks embedded in the VFAT filesystem.

  • 6,256,642 (Method and System for File System Management Using a Flash-Erasable, Programmable, Read-only Memory, 1992). This one covers a fairly straightforward mechanism for managing flash memory by dividing large erase blocks into filesystem-sized blocks and allocating them independently.

The first two patents in this list appear to be laughable indeed; it is hard to see how they can pass the obviousness test. This is especially true in light of the KSR v. Teleflex ruling, wherein it was decided (also in the automotive setting) that the idea of connecting a floor pedal to an electronic throttle control was too obvious to patent. The navigation patent would appear to be infringed by anybody who sits in the passenger seat and helps the driver find a destination. The docking station and GUI patents seem less clear, but it doesn't seem like it should be all that hard to find suitable prior art.

That leaves the final three patents, all of which are relevant to the Linux platform. Like almost every other system on the planet, Linux supports the VFAT filesystem, and, thus, could be argued to infringe upon the relevant patents. The flash patent looks much like the technique used by any system which manages flash memory in anything but the stupidest of ways. It would appear that Microsoft has finally decided to follow through on its longstanding patent threats against Linux.

Of course, not all agree. The 451 Group posted this fairly impressive apology for Microsoft, claiming:

The key phrase, which is repeated, is the suit involves 'the Linux kernel as implemented by TomTom,' which is very different from 'the Linux kernel' when we're talking software code and patent infringement suits....

For those looking for signs that Microsoft has changed, I would hope this might serve as the proverbial coffee to wake up and smell. Microsoft is acknowledging the contributions and IP value of open source software and is going out of its way to make sure people don't think it is making patent infringement claims over the actual Linux kernel.

Your editor wishes to politely dismiss this talk as dangerous nonsense. There is nothing special about TomTom's kernel with regard to these patents. One would think that it would make little sense for TomTom to go into the kernel source and create its own special version of VFAT which infringes on Microsoft's patents. Of course, embedded systems developers have been known to do some very strange things, so one cannot take TomTom's good sense for granted in this situation. So, for the definitive word, we will refer to Harald Welte's take on TomTom's kernel:

I have actually reviewed the TomTom kernel sources a number of times during the last couple of years as part of gpl-compliance reviews. I can tell you, there is nothing "TomTom specific" in their FAT FS code. It is the plain fat/msdos/vfat file system like in every kernel.org kernel.

If TomTom is infringing Microsoft's patents, then everybody who is running Linux is infringing those patents. This is an attack against Linux; TomTom has just been given the honor of being the first defendant.

Microsoft's motivation would seem to be clear. The company has tried for years to sell versions of Windows into the embedded systems market, with success best described as "modest." Linux is hard to compete against in these systems; it is highly portable, can be customized to an arbitrary degree, offers support from multiple vendors, and can be shipped with no royalty charges. Microsoft would like to take away some of those advantages by imposing a patent tax on embedded Linux deployments. Embedded systems vendors cannot miss this message: they can pay licensing fees, or they can pay legal fees.

The obvious question at this point is: what now? The VFAT patents may appear to fail the obviousness test; they could also run into difficulties stemming from the Bilski decision. These patents are problematic, though: the Public Patent Foundation tried hard to invalidate these patents in 2004, only to have them reinstated by the US patent office in 2006. As a result, there will be a certain presumption of validity which could prove hard to overcome in court. It has often been said that attempts to invalidate patents carry risks; what doesn't kill a patent may well make it stronger.

Your editor would certainly not advise anybody to give up on efforts to defeat these patents, but the possibility that they could stand must be considered. The loss of the VFAT filesystem would be painful. It is a poor filesystem, but it has become a sort of de facto interchange format for storage-oriented devices. Without VFAT, Linux users would encounter difficulties working with their digital cameras, cellular telephones, and music players. Sharing storage devices with Windows systems would become harder. VFAT would become a technology like MP3: unavailable on many Linux systems until installed from some third-party repository on the net.

Avoiding this outcome seems desirable. One way would be to defeat these patents in court. To that end, one can only hope that TomTom will stand up to this attack and defend its rights. The rest of the industry would be well advised to consider helping TomTom in this fight. This case, if fought to its conclusion, will certainly be expensive. But the cost of not fighting it seems certain to be much higher.

Another way to deal with the VFAT patents would be to start a serious look for workarounds - a technique which the free software community does not, yet, make enough use of. Patents tend to be tightly written, meaning that workarounds are often possible with relatively small changes. It may well be possible to make changes to the VFAT filesystem which pass the patent-lawyer test while maintaining interoperability with other systems.

Indeed, a suitably clever lawyer might be able to argue that Linux already operates outside the patent; the claims require that the long filename include "more than the maximum number of characters that is permissible by the operating system," something which is clearly not the case on Linux. Your editor, however, is neither a lawyer nor suitably clever; this kind of determination will need to be made by others.

At the upcoming Linux Foundation Collaboration Summit, your editor will be running a panel on kernel development. Sam Ramji, alas, will be in the other room at that time, sitting on a panel entitled "Why Can't We All Just Get Along: Linux, Microsoft & Sun." One can imagine the course this discussion is going to take; Sun is likely to get off easy. Parts of Microsoft (especially those represented by Mr. Ramji) have been making friendly noises toward open source for some time. But actions speak louder than friendly noises, and this particular action speaks loudly indeed. Parts of Microsoft are almost certainly sincere about wanting to get along with the Linux community, but the stronger forces within the company, it seems, are not.


(Log in to post comments)

prior art: Knight Rider

Posted Mar 2, 2009 22:00 UTC (Mon) by coriordan (guest, #7544) [Link]

Didn't KITT do many of these things in the early 80s?

prior art: Knight Rider

Posted Mar 2, 2009 22:23 UTC (Mon) by mgedmin (subscriber, #34497) [Link]

Store long filenames in a FAT filesystem?

prior art: Knight Rider

Posted Mar 7, 2009 13:15 UTC (Sat) by rwmj (subscriber, #5474) [Link]

LOL ... Wouldn't surprise me if KITT used 8.3 filenames though :-)

prior art: Knight Rider

Posted Mar 3, 2009 16:56 UTC (Tue) by jamesh (guest, #1159) [Link]

Was KITT an open platform?

prior art: Knight Rider

Posted Mar 5, 2009 11:43 UTC (Thu) by addw (guest, #1771) [Link]

Exactly what I thought. Are we, perhaps, overlooking a great source of prior art: science fiction ? Should patent busters be looking at old episodes of Star Treck & Dr Who and rereading Asimov & al ?

prior art: Knight Rider

Posted Mar 6, 2009 19:16 UTC (Fri) by giraffedata (guest, #1954) [Link]

Are we, perhaps, overlooking a great source of prior art: science fiction? Should patent busters be looking at old episodes of Star Treck & Dr Who and rereading Asimov & al ?

One of the few things I remember from my one patent law class is that you patent an invention, not an idea. An invention is "an idea reduced to practice." Or, in Thomas Edison's words, "invention is 1% inspiration and 99% perspiration." Sci Fi takes care of the inspiration, but unless Asimov also filled in all the details needed to implement it and did the testing to show that it works, it's not an invention.

That's how we come to the obviousness test: once you've realized having a computer in a car is a good way to do something (the inspiration), it's obvious that it should and could go in the dashboard, so there's presumably nothing to perspire over and nothing to patent here.

Third time is the charm?

Posted Mar 2, 2009 22:02 UTC (Mon) by dberkholz (guest, #23346) [Link]

Has anyone from SFLC, LF, or something along those lines gotten in touch with TomTom? I don't know how much attention they pay to the community, and it would be a shame for them to miss out on this discussion.

Third time is the charm?

Posted Mar 3, 2009 7:21 UTC (Tue) by jimbo (subscriber, #6689) [Link]

They might be interested, but I doubt that they're going to say anything in reply.
--
J

Workaround - read but not create long file names

Posted Mar 2, 2009 22:11 UTC (Mon) by tridge (subscriber, #26906) [Link]

I agree that we should try the approach of working around the patent. For embedded use such as in a device like the TomTom, I think it is most important for the device to be able to read long filenames on VFAT filesystems, but I don't see any need to be able to create files with long file names. On my TomTom, I don't know of any way that a user could create a file with a long file name anyway, except when the device is docked, in which case the manipulation of the VFAT filesystem is done by the host computer, not the device (it just exports a USB storage device).

So this suggests a simple solution:

  • add a new kernel option for VFAT, "read only long file names (patent avoidance)"
  • embedded vendors such as TomTom could enable this option, and be fully compatible with existing memory cards.
When this option is enabled, the kernel code that creates long file names in VFAT would be disabled. The code that understands long file names would still work.

This argument relies on the fact that all of the claims of the VFAT patent talk about "storing" the directory entries. If you don't ever store a directory entry in the VFAT format then you can't infringe this patent.

This doesn't solve the problem for all users, but it is much less drastic than dropping support for VFAT, as existing filesystems will still work. I think it would also work as a complete solution for many embedded Linux vendors.

Cheers, Tridge

That would appear to work

Posted Mar 2, 2009 22:37 UTC (Mon) by JoeBuck (subscriber, #2330) [Link]

I checked the two patents, and every single claim appears to require that something be stored; it does not appear that any claim is infringed by just reading, though it would be nice if someone with legal expertise could confirm this.

It also seems that the patent is very broad, covering any possible way of encoding long names while still allowing the filesystem to look like a valid filesystem to older O/Ses that don't understand the long filename encoding (any table you could come up with would be a "second directory entry"). But this might mean it's so broad that someone has done something similar before. Any kind of database where items have both a short and a long name, and the short name has a length restriction, and you can do lookups with either name, might infringe.

That would appear to work

Posted Mar 2, 2009 22:52 UTC (Mon) by jmorris42 (guest, #2203) [Link]

> Any kind of database where items have both a short and a long name,
> and the short name has a length restriction, and you can do lookups
> with either name, might infringe.

The RockRidge extensions to ISO9660 sound like a good candidate. All of us oldtimers know RR CD-ROMS predate Win95. The question is whether the RR spec predates the patent on VFAT?

That would appear to work

Posted Mar 3, 2009 16:56 UTC (Tue) by jamesh (guest, #1159) [Link]

With Rock Ridge CDs, don't you have separate name spaces for the long and short names? That is, you either use the full file names or the legacy short names, but not both.

The patent talks of a "common name space", so RR might not apply.

That would appear to work

Posted Mar 5, 2009 1:14 UTC (Thu) by JoeBuck (subscriber, #2330) [Link]

With VFAT you also use either one or the other. Non-VFAT-aware systems see only the short names; VFAT-aware systems see the long names. It would appear that Rock Ridge works the same way.

That would appear to work

Posted Mar 5, 2009 2:39 UTC (Thu) by jamesh (guest, #1159) [Link]

On Windows, both the long and short path names are available concurrently for VFAT. You can even mix the long and short names in a single path (e.g. "c:\Progra~1\Microsoft Office"). It really is exposed as a single name space for both types of file names.

That would appear to work

Posted Mar 5, 2009 2:51 UTC (Thu) by jmorris42 (guest, #2203) [Link]

> It really is exposed as a single name space for both types of file names.

It is in the Windows implementation but there isn't a requirement that other implementations follow their example. I don't think the Linux vfat does, haven't used fat volumes much lately to really say. Matters not though since if doing that would work around the patent it wouldn't be a loss of usability for vfat under linux to only show/accept the long file names.

That would appear to work

Posted Mar 12, 2009 9:21 UTC (Thu) by forthy (guest, #1525) [Link]

RR predates VFAT, and a German court has invalidated the VFAT patent in 2007, using Rock Ridge as prior art example. See Bundespatentgericht erklärt FAT-Patent von Microsoft für nichtig (on Heise.de). Note that the patent was not only invalidated through prior art, but also did not pass the non-obviousness test. Furthermore, the patent even lacks the proper teaching.

I wonder what the people at USPTO are smoking to grant patents like this. Must be some strong stuff, where they see bright new inventions on dull gray paper. The funny stuff is that on the list of these patents, the FAT patent is apparently the strongest.

UMSDOS?

Posted Mar 3, 2009 4:05 UTC (Tue) by eru (subscriber, #2753) [Link]

(any table you could come up with would be a "second directory entry").

Doesn't the old UMSDOS extension in Linux FAT implementation then qualify as prior art? If Wikipedia is correct, it was started in 1992 and first appeared on the net in 1994 (http://en.wikipedia.org/wiki/Umsdos).

UMSDOS?

Posted Mar 4, 2009 6:29 UTC (Wed) by hawk (subscriber, #3195) [Link]

Now, THAT would be something...

...If the very system they are attacking contains the prior art, and in the form of an extension for that very same file system.

Workaround - read but not create long file names

Posted Mar 2, 2009 23:10 UTC (Mon) by tridge (subscriber, #26906) [Link]

I've just realised there is a corollary to this workaround. If a embedded device vendor doesn't currently have any interface that allows the user to create files with long file names then they are not infringing the VFAT patents, even without patching the kernel to remove the code that allows long file names to be created on VFAT. This is because there is no way that anyone can demonstrate infringement of a claim about "storing" when there is no way to make the device store names in the way that is described.

I think this applies to TomTom, and also to all the camera vendors and similar devices. They all create files with short file names. Many of them will happily read files that have long file names, but they tend not to have an interface to create them.

In part we are saved by the common way that these devices are accessed over USB. The devices present themselves as USB storage devices, so the Linux kernel is just presenting a block interface. The creation of VFAT directory entries when done on a device that is docked is done by the host computer, not by the device, so the device vendor is off the hook.

We should still consider having a kernel option that disables the creation of long file names in VFAT for all those vendors that do have an interface to creating arbitrary file names, but I think the above argument may help to reduce the impact of the VFAT patents on the embedded space quite a bit.

Cheers, Tridge

Workaround - read but not create long file names

Posted Mar 3, 2009 16:29 UTC (Tue) by holstein (guest, #6122) [Link]

This would cover embedded uses, but not desktop use, no?

Timing?

Posted Mar 2, 2009 22:13 UTC (Mon) by pjhacnau (subscriber, #4223) [Link]

You didn't reference the recent MS-RedHat deal, and it's explicit exclusion of any patent protection. The timing seems a bit more than coincidental to me . . .

Timing?

Posted Mar 2, 2009 22:42 UTC (Mon) by dowdle (subscriber, #659) [Link]

Red Hat would not accept any deal in the first place that included "patent protection"... because such presumes there exists some patent issues where protection is needed... or at least that is my understanding from their previous statements and actions...so I don't see how that is coincidental. I guess you'll have to spell it out.

Timing?

Posted Mar 2, 2009 23:41 UTC (Mon) by pjhacnau (subscriber, #4223) [Link]

"because such presumes there exists some patent issues where protection is needed"

How better to demonstrate the need for protection than by successfuly suing someone?

There's another reason

Posted Mar 3, 2009 1:13 UTC (Tue) by JoeBuck (subscriber, #2330) [Link]

The GPL doesn't allow Red Hat to make a deal to protect itself from patents, unless it is allowed to pass that protection downstream to anyone who obtains there code or makes changes to it.

Novell got around this by some questionable legal trickery, of a kind that GPLv3/LGPLv3 does not permit.

Third time is the charm?

Posted Mar 2, 2009 22:19 UTC (Mon) by JoeBuck (subscriber, #2330) [Link]

Even without VFAT, any filenames that fit in the old 8.3 format show up correctly when mounted as FAT (which isn't patented), and the remaining names get tildes in them. But it would be much better to beat the patent. Antitrust is another possible route: the only purpose of these patents is to block interoperability.

Antitrust vs. patents

Posted Mar 3, 2009 2:34 UTC (Tue) by ncm (guest, #165) [Link]

As I understand it, patents trump antitrust. The whole point of patents is to establish or maintain a monopoly. But I'm no lawyer.

I would welcome education on the topic.

Antitrust vs. patents

Posted Mar 3, 2009 4:12 UTC (Tue) by dlang (guest, #313) [Link]

antitrust isn't having a monopoly, it's abusing having a monopoly.

as such antitrust could still be involved with patents if the company with the pantents is abusing it's monopoly status.

Antitrust vs. patents

Posted Mar 3, 2009 9:39 UTC (Tue) by nim-nim (subscriber, #34454) [Link]

Antitrust is basically « you're so big you've escaped normal market forces so either you play nice and self-regulate or we'll have to regulate you ourselves to keep competition (and market) alive ». It can trump pretty much everything else when there's an actual political will behind.

Antitrust vs. patents

Posted Mar 6, 2009 18:50 UTC (Fri) by giraffedata (guest, #1954) [Link]

We're looking at two different monopolies here: the monopoly over selling of VFAT, which is what the patent creates, and the monopoly over selling computers with removable storage, which results if VFAT has somehow become the only practical way to do removable storage.

In cases where companies have lost antitrust lawsuits because they used a patent to control interoperability like this, the redress was not that the invention became public domain, but that the patent holder was forced to license the patent for royalties the court determined were fair -- basically, what the patent holder would be able to get if he hadn't been able to corner the market.

Antitrust vs. patents

Posted Mar 17, 2009 4:05 UTC (Tue) by yuhong (guest, #57183) [Link]

And as it turns out, MS is already making these FAT patents available for licensing, though I doubt it is compatible with open source software.

Third time is the charm?

Posted Mar 3, 2009 3:17 UTC (Tue) by jordanb (guest, #45668) [Link]

> Antitrust is another possible route: the only purpose of these patents is > to block interoperability.

This is a good point. But it'd be up to the AG to take the case. In the past there would have been little chance of that happening (recall that one of the earliest actions of Ashcroft after Bush was sworn in was to terminate the US vs. Microsoft suit). But Now that there's a new sheriff in town, this could turn up being an incredibly stupid move for Microsoft by demonstrating that they are still unrepentant monopolists.

Third time is the charm?

Posted Mar 3, 2009 6:42 UTC (Tue) by Trelane (subscriber, #56877) [Link]

http://www.vnunet.com/vnunet/news/2236785/google-face-monopoly-probe
“For me, Microsoft is so last century. They are not the problem,” Varney said at a panel discussion sponsored by the American Antitrust Institute. The US economy will “continually see a problem – potentially with Google” because it already “has acquired a monopoly in internet online advertising", she said, according to Bloomberg.
http://www.opensecrets.org/orgs/toprecips.php?id=D000000115

Third time is the charm?

Posted Mar 3, 2009 15:06 UTC (Tue) by jordanb (guest, #45668) [Link]

Yes. I expect we've all seen that quote.

The point is that the previous Department of Justice was *uninterested* in enforcing antitrust laws. The new one presumably will not be.

Ms. Varney is probably right to be focused more on Google than Microsoft as the latter's monopoly is certianly waining.

But the only earthly reason why someone would want to do what's covered in in the VFAT patent is to be compatible with a (bad) Microsoft technology that has become a standard due to the omnipresence of Windows.

Microsoft is now attacking their most credible a competitor with a patent purely to prevent us from using VFAT. That demonstrates very clearly that Microsoft is still capable and willing to illegally leverage its monopoly.

Before last month, such actions would have been ignored by the Federal government. Now I think that is less likely.

Third time is the charm?

Posted Mar 3, 2009 15:46 UTC (Tue) by Trelane (subscriber, #56877) [Link]

Now I think that is less likely.
Given the statement of the DoJ official in charge of anti-trust and the campaign contributions I linked to, I think your position is naiive. Only time will tell, however.

Third time is the charm?

Posted Mar 2, 2009 23:20 UTC (Mon) by qg6te2 (guest, #52587) [Link]

Parts of Microsoft (especially those represented by Mr. Ramji) have been making friendly noises toward open source for some time. But actions speak louder than friendly noises, and this particular action speaks loudly indeed. Parts of Microsoft are almost certainly sincere about wanting to get along with the Linux community, but the stronger forces within the company, it seems, are not.

While I almost always enjoy articles written by our great editor, this is a rare instance where the case is otherwise. The above-quoted diplomacy tries to paint Microsoft as a "half-friendly" company, which it never was and almost certainly never will be. The "stronger forces" are the people that matter within Microsoft: the upper management, where all the decisions and final steering is made.

It is entirely possible that certain parts of Microsoft are cozing up with the Open Source community simply to soften Microsoft's overall image. However, this is nothing more than a marketing exercise -- it's the final actions of Microsfot that matter. A tiger never loses its stripes: Microsoft is an extremely aggressive beast which will do anything to maintain and extend its market share, including copping big fines and actions which cross the boundary of legality.

If we're going to pick nits ...

Posted Mar 3, 2009 1:44 UTC (Tue) by felixfix (subscriber, #242) [Link]

Nowhere does our editor say "half-friendly"; that is your paraphrasing of our editor's "part of the company".

He also makes it quite clear that the stronger parts are not friendly, and you add nothing to the discussion when you repeat that as if he had not said any such thing.

Our editor is famous for his choice of words, and they work quite nicely here.

Choice of words

Posted Mar 3, 2009 12:28 UTC (Tue) by man_ls (guest, #15091) [Link]

Like qg6te2, our editor might have said "Microsoft isn't fooling anyone", "Open source friendliness is a pose", "Acts speak louder than words" and the like; but there was no need for those stronger statements.

As it stands our editor's words clearly state that those friendly parts of Microsoft are probably sincere and to be encouraged. However in situations such as these the Master's voice is going to be heard, and revenue is going to trump common sense. As our editor also makes clear, with these stupid patents Microsoft is joining patent bullies -- and leaving a huge exposed flank for patent trolls. Now it can hardly ask for sympathy from other software houses and organizations. Their patents are not defensive but another arrow in the quiver.

Navigation systems of the 90s

Posted Mar 2, 2009 23:28 UTC (Mon) by rvfh (guest, #31018) [Link]

Philips NV, the Dutch company, had navigation systems working long before these patents about navigation. I am sure a lot of prior art is to be found in CARiN/Carminat.

Navigation systems of the 90s (... no 80s, ... no 70s!)

Posted Mar 3, 2009 14:34 UTC (Tue) by mcatkins (guest, #4270) [Link]

I saw a demonstration of a system that calculated left/right directions
to follow a route sometime around 1978 (definitely before 1980!). This
was at an open day at the Transport and Road Research Establishment
(as was - a UK government research establishment).

The Teletype was not easily car-mountable (the computer was worse :-), and
the map data was somewhat limited, but the principle was the same.

Now, did they publish? Or was it "too obvious"?

Martin

Navigation systems of the 90s (... no 80s, ... no 70s!)

Posted Mar 4, 2009 11:13 UTC (Wed) by eru (subscriber, #2753) [Link]

Provided that the establishment you describe worked like similar ones in my country at the time, it probably had been published in some obscure governement research report series that almost nobody ever read. And it almost certainly is not online, but might well be in the collection of some university library. If it was even theoretically available to the public, it would count as prior art.

Third time is the charm?

Posted Mar 3, 2009 6:05 UTC (Tue) by PaulWay (guest, #45600) [Link]

BTW, patent 6,175,789 (in-dash computer) is invalidated by the empeg car (http://en.wikipedia.org/wiki/Empeg_Car). Microsoft patented the in-dash computer on September 10, 1999, and the EE Times article (linked on the Wikipedia page) shows Hugo holding a completed Mark I empeg car in May 2, 1999. Since the development had been quite public and going on for years earlier, I would say that at the very least Microsoft's patent is dead by more than four months.

Third time is the charm?

Posted Mar 3, 2009 6:49 UTC (Tue) by dlang (guest, #313) [Link]

the filing can happen up to two years after the invention. to qualify as prior art you would need to find something published dated prior to Sept 10 1997 for a patent filed Sept 10 1999 (which shouldn't be that hard to do)

Third time is the charm?

Posted Mar 5, 2009 11:54 UTC (Thu) by nye (guest, #51576) [Link]

How about the system shown in this advert from 1993?

http://www.youtube.com/watch?v=TZb0avfQme8

What about the flash patent?

Posted Mar 3, 2009 8:35 UTC (Tue) by njs (guest, #40338) [Link]

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.)

What about the flash patent?

Posted Mar 3, 2009 9:46 UTC (Tue) by dlang (guest, #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 (subscriber, #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 (guest, #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 (guest, #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.

Third time is the charm?

Posted Mar 3, 2009 10:10 UTC (Tue) by mjthayer (guest, #39183) [Link]

How much does it really cost to submit a piece of prior art to the patent office for consideration? Since they are trying to encourage people to submit prior art on patent applications which have not yet been granted, they ought, for completeness, to have a similar system for submitting it after the fact. Perhaps charging a fee for it which was high enough to stop them being inundated by silly submissions (and perhaps even high enough to make it financially interesting for the patent office), but low enough not to discourage any serious submitter.

Microsoft's Perspective

Posted Mar 3, 2009 10:50 UTC (Tue) by kripkenstein (guest, #43281) [Link]

Excellent article. This sort of thing is why I subscribe to LWN.

And now, I'll do something I've probably never done before, try to write how things might look from Microsoft's perspective.

Microsoft licenses its FAT patents to probably pretty much all corporations that want FAT compatibility, which (sadly) is a quite a large group due to FAT being commonplace.

So, to Microsoft, TomTom is the odd company out, a strange corporation that won't license its FAT patents. It's possible the Microsoft lawyers couldn't care less what OS TomTom runs (or perhaps don't even understand much about OSes) - to them, TomTom is just another company, that 'should' license the patents just like everyone else. Or, perhaps the Microsoft lawyers are aware of Linux being in the picture here, but think, why should we give a free pass to TomTom just because they happen to run Linux?

So, I'm not terribly surprised Microsoft decided to sue. The problem is the US patent system, and corporations that support and utilize it, like Microsoft.

Overall, I think the lawsuit shows Microsoft is not willing to give Linux a pass, which is a bad sign - but not as bad as a direct and all-out attack. Or, if this is an all-out attack, and FAT patents are the worst Microsoft has to hold over our heads, then I'm pretty relieved, all things considered.

Microsoft's Perspective

Posted Mar 3, 2009 11:37 UTC (Tue) by man_ls (guest, #15091) [Link]

There is a point that I would have liked to see in the article, and which relates to your post. It can be summarized by the following questions. Is Microsoft risking a countersuit by OIN at all? Is TomTom a member of OIN, or can it become one? Is there a generic provision for software covered by OIN, even if it is used by non-members? I'm thinking something like SCO frightening Red Hat users, and Red Hat retaliating with a suit. Can there be something like that for generic Linux kernel developers / distributors / users, but from OIN? Are there other similar organizations which could enter the picture to help TomTom defend against these stupid patents?

I gather the question to all of them is 'no', but there probably should be something along these lines. Otherwise thousands of companies are open to stupid lawsuits from patent-bullies (of which Microsoft has definitely become one).

Microsoft's Perspective

Posted Mar 3, 2009 18:15 UTC (Tue) by iabervon (subscriber, #722) [Link]

Does Microsoft actually license their VFAT patents to all that many small embedded device manufacturers? Most pairs of large companies license each other all their patents in bulk without regard for any specific patent (because caring about specific patents would lead quickly to lengthy and expensive negotiations). For companies that Microsoft doesn't have a cross-licensing agreement with, I'd guess that a lot of them either don't write to VFAT at all or don't write to files with long filenames, because it costs an extra sector write against your file creation performance and you don't generally have useful names to give files anyway. (As far as I can tell, my camera's only able to set up a particular fixed empty directory layout if it doesn't already exist and create files of the form "dscnXXXX.jpg", and I would guess that they have a cross-licensing agreement and still avoid the VFAT hack.) So I wouldn't be surprised if there isn't anybody who's specifically licensed this patent.

Third time is the charm?

Posted Mar 3, 2009 16:01 UTC (Tue) by mtk77 (guest, #6040) [Link]

"The navigation patent would appear to be infringed by anybody who sits in the passenger seat and helps the driver find a destination."

At least my wife will be safe!

Third time is the charm?

Posted Mar 4, 2009 4:22 UTC (Wed) by landley (guest, #6789) [Link]

I'm told we don't need VFAT, we can format our memory sticks UDF instead:
http://en.wikipedia.org/wiki/Universal_Disk_Format

Yes, it turns out the DVD file format is read/write, and should be recognized by windows and macintosh just fine. (I haven't been able to personally test this yet, though.)

Third time is the charm?

Posted Mar 4, 2009 4:42 UTC (Wed) by eru (subscriber, #2753) [Link]

Yes, it turns out the DVD file format is read/write

A familiar fact to anyone who has used DVD-RAM disks. They are formatted as UDF by standalone DVD recorders, and Linux has long had R/W support for such disks.

Third time is the charm?

Posted Mar 4, 2009 21:35 UTC (Wed) by bangert (subscriber, #28342) [Link]

pretty cool - now where is the source to the firmware of my digital camera?

Third time is the charm?

Posted Mar 5, 2009 15:28 UTC (Thu) by cry_regarder (subscriber, #50545) [Link]

The source for your camera is here:

http://chdk.wikia.com/wiki/Compiling_CHDK_under_Linux

As long as your camera is a canon...

Cry

Third time is the charm?

Posted Mar 5, 2009 15:54 UTC (Thu) by job (guest, #670) [Link]

That's .. sick! :)

Third time is the charm?

Posted Mar 5, 2009 13:57 UTC (Thu) by smorovic (guest, #52892) [Link]

I hope TomTom will try to defend these patents. VFAT is one of the most dangerous patents that Linux potentially infringes on, while it's needed for interoperability with many devices. Samba (precisely CIFS) could be another such minefield.

I hope it will be enough to convince the court that VFAT is actually obsolete filesystem with many modern (and free to use) replacements available, and the only reason to use it on devices is to have a readable/writable Windows drive (which means to support a 90%-market-share OS).

Also, maybe TomTom's device doesn't _create_ anly long filenames, in that case they are not even guilty for infringing the VFAT patent.

Third time is the charm?

Posted Mar 12, 2009 10:05 UTC (Thu) by PLee (guest, #56686) [Link]

An excellent article!

Is it really about these particular patents? MS may have got away with licensing / bulk cross-licensing in the past, but surely MS don't really believe all these will stand scrutiny!

It seems much more likely that this is about the legal fight. Its MS saying, license Windows or there is a good chance we'll dig up some patent which we can use to take you to court. You might win, but in the meantime it might affect your stock price to be sued by us. Are your lawyers so cheap you can afford the fight? What if your legal team isn't as good as ours and loses? Its so much easier, safer and cheaper just to pay a small sum as insurance against all that nastiness.

MS can afford to lose all of these patents and they still "have x hundred infringed patents" they could use to come at you.

I can't imagine a vfat patent license (or even all of them together) is going to make a whole heap of difference to MS' bottom line. It makes sense to try to get it invalidated though, to squelch the FUD and give others confidence.

Third time is the charm?

Posted Mar 26, 2009 14:30 UTC (Thu) by rich3800 (guest, #57566) [Link]

Whiiirrrrrrrr! (Sound of gunship turret rotating). Aiming at Microsoft warship... Fire at will!! Booooom! Booooom! Boooom! Microsoft boat sinking helplessly... Microsofties trying to escape...


Copyright © 2009, Eklektix, Inc.
This article may be redistributed under the terms of the Creative Commons CC BY-SA 4.0 license
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds