KSM runs into patent trouble [LWN.net]

By Jake Edge
December 3, 2008

On the kernel page a few weeks ago, we took a look at KSM, a technique to reduce memory usage by sharing identical pages. Currently proposed for inclusion in the mainline kernel, KSM implements a potentially useful—but not particularly new—mechanism. Unfortunately, before it can be examined on its technical merits, it may run afoul of what is essentially a political problem: software patents.

The basic idea behind KSM is to find memory pages that have the same contents, then arrange for one copy to be shared amongst the various users. The kernel does some of this already for things like shared libraries, but there are numerous ways for identical pages to get created that the kernel does not know about directly, thus cannot coalesce. Examples include initialized memory (at startup or in caches) from multiple copies of the same program and virtualized guests that are running the same operating system and application programs.

Unfortunately, as Dmitri Monakhov points out, the KSM technique appears to be patented by VMware. A patent for "Content-based, transparent sharing of memory units" was filed in July 2001 and granted in September 2004. The abstract seems to clearly cover the ideas behind KSM:

[...] The context, as opposed to merely the addresses or page numbers, of virtual memory pages that [are] accessible to one or more contexts are examined. If two or more context pages are identical, then their memory mappings are changed to point to a single, shared copy of the page in the hardware memory, thereby freeing the memory space taken up by the redundant copies. The shared copy is ten preferable [sic] marked copy-on-write. Sharing is preferably dynamic, whereby the presence of redundant copies of pages is preferably determined by hashing page contents and performing full content comparisons only when two or more pages hash to the same key.

It should be noted that the abstract has no legal bearing, that comes from the—always tortuously worded—claims, which can be seen at the link above. In this case, as far as can be determined, the claims and abstract are in close agreement.

The dates above are rather important because there is some "prior art" to consider, namely the mergemem patch first announced in March of 1998. It is substantially the same as the patented idea: it looks for identical "context pages", then changes the memory mappings to point to a single copy-on-write page. This would seem to be a clear example of the idea being implemented well before the patent was filed, so it should invalidate the patent. As with everything surrounding software patents, though, it isn't as easy as that.

In order to invalidate a patent, either a court must rule that way or the patent office must be convinced to re-examine it, then find that the prior art makes it invalid. Both of these methods take time and usually money and lawyers as well. Free software projects may have time, but the other two are typically out of reach. Alan Cox suggests that "perhaps the Linux Foundation and some of the patent busters could take a look at mergemem and re-examination". While that might eventually resolve the problem, it is a multi-year process at best.

The folks behind the KSM project are some of the kvm hackers from Qumranet—which is now part of Red Hat. It is certainly conceivable that VMware might consider kvm a competitor and try to use this patent as a "competitive" weapon. That concern is probably enough to keep KSM out of the mainline until the issue is resolved.

There is a much quicker resolution available should VMware wish to do so. Like IBM has done with the RCU patent, VMware could license its patent for use in GPL-licensed code. There is much to be gained by doing that, at least in terms of positive community relations, and there is little to be lost—unless VMware truly believes that the patent will stand up to scrutiny. Both VMware and its parent, EMC, are members of the Linux Foundation, so one could see a role for the foundation in helping to put that kind of agreement together.

The original mergemem idea did not make into the kernel, but the code is still available for those running Linux 2.2.9. It appears that it was not pushed very hard in the face of some security concerns—which will need to be addressed by KSM as well. Processes could create a page of memory with known contents then, after waiting for the checker process (or kernel thread) to run, see if memory usage has increased. Based on that information, one can determine if other processes have a page with identical values. It would seem rather difficult to exploit, but clearly does allow some information to leak.

It will come as no surprise to most LWN readers that software patents are an increasingly dense minefield that can derail free software projects. Unfortunately, it is the kind of problem that has no solution in the technical domain where such projects excel. The political arena is where any solution will have to come from, though there seems to be some hope that judicial opinions (like the Bilski decision) may limit the scope of the damage. It is a problem that we are likely to see more frequently until there is some kind of resolution.

to post comments

KSM runs into patent trouble

Posted Dec 3, 2008 17:13 UTC (Wed) by flewellyn (subscriber, #5047) [Link] (16 responses)

I really hope VMWare does the right thing here, and licenses the patent royalty-free to GPLed software. It's not the real right thing, which is to not have software patents in the first place, but it would be at least a gesture of good faith, and a step in the right direction.

Good gamesmanship, too

Posted Dec 3, 2008 19:05 UTC (Wed) by dmarti (subscriber, #11625) [Link] (15 responses)

If they license for GPL implementation right away, it sidelines some important stakeholders who would otherwise have an incentive for patent-busting. Then they're free to use the patent as a bargaining chip for cross-licensing with proprietary vendors, or as a revenue tool.

Don't cut packing tape with your good kitchen knife if you want to keep it good.

Good gamesmanship, too

Posted Dec 3, 2008 19:38 UTC (Wed) by flewellyn (subscriber, #5047) [Link] (14 responses)

That's a good point. Unfortunately, I don't see a good way to work this one out without either busting the patent (expensive) or getting an exemption (legitimizes the patent). We really need patent reform.

Kill software patents

Posted Dec 3, 2008 19:54 UTC (Wed) by dwheeler (guest, #1216) [Link] (13 responses)

We need patent reform, in particular, we need to eliminate software patents. Here's a URL with pointers to more information on eliminating software patents: http://www.dwheeler.com/essays/software-patents.html.

Kill software patents

Posted Dec 3, 2008 19:55 UTC (Wed) by flewellyn (subscriber, #5047) [Link]

I think I've read that article of yours before. Still worth another look.

Kill software patents

Posted Dec 4, 2008 16:15 UTC (Thu) by felixfix (subscriber, #242) [Link] (8 responses)

It seems to me that the problem isn't software patents per se, but obviousness. Almost all the software patents I have seen ARE obvious to someone skilled in the arts, and that applies to a lot of hardware patents too. I have seen hardware patents which add rounded corners, or face hardened steel, or some other trivial tweak which any self-respecting hardware junkie would know about.

What we really need is an emphasis on originality, not a ban on one particular type of patents.

Kill software patents

Posted Dec 4, 2008 17:31 UTC (Thu) by lysse (guest, #3190) [Link] (7 responses)

Whilst obviousness is an additional problem, it's not the whole problem. Software patents do whole swathes of damage because software is the transliteration of mathematical algorithms. It's the difference between patenting a particular machine that multiplies by the operation of a series of switches and patenting the concept of multiplication itself.

Consider the motivation for introducing patents. The argument usually put is that patents protect the inventor of a machine, who might have invested considerable sums in the development of that machine, from being unable to recoup his costs because someone else has duplicated that machine exactly and can now sell it for only the costs of manufacture, without the need to recoup development costs. Well - the costs of manufacture in the case of software are precisely zero, but so are the costs of development; someone else who develops a broadly functionally similar program is still likely to end up spending just as much (or as little) writing it as the original developer, even if they end up slavishly duplicating every single technique and algorithm of the original. (Moreover, that duplication becomes necessary in cases like file format compatibility, as we've seen... extensively.) In any case, the duplication of software is already adequately protected by copyright law - which, of course, does not extend to mechanisms, which is why patents were seen as required in the first place; copyright law only covers form, not function - but software is form; the function is provided by the machine on which the software runs.

Kill software patents

Posted Dec 4, 2008 17:56 UTC (Thu) by dlang (guest, #313) [Link] (1 responses)

manufacturing cost is not zero (unless you do online distribution).

it's also a very uneven playing field for a well established software company (with extensive distribution, advertising, and name recognition in place) compared to a startup.

as such it's still pretty easy for a large software company to reverse engineer and duplicate the functionality of a small companies product and then wipe out the small company (look what microsoft has done several times)

unlike other industries 'trade secrets' don't work in software because you have to distribute the exact instructions. you can obfuscate things to make it hard to figure out, but a determined person can just look at the instructions that you give to the CPU and see what you are doing.

in physical devices trade secrets can sometimes work because the secret can be in how the device was made.

now I am not arguing that software patents are a good thing, I'm just saying that you arguments for why they aren't are invalid.

Kill software patents

Posted Dec 14, 2008 2:01 UTC (Sun) by lysse (guest, #3190) [Link]

Guess which phrase I intentionally didn't use in my arguments...?

Still, well done; that strawman never saw it coming.

Prose analogy patents

Posted Dec 4, 2008 18:59 UTC (Thu) by dmarti (subscriber, #11625) [Link] (4 responses)

I haven't seen an argument in favor of software patents that doesn't also apply to prose analogy patents. For example, should Steve Oualline's thorough mailbox analogy to explain pointers in Practical C Programming be patentable? If it helps people get pointers and start programming in C sooner, it has immense value--but another author could reimplement it in different words and using newly-drawn pictures without licensing it from the patent department at O'Reilly and Associates. The lack of a patent here means that Steve lacks an incentive to create more prose analogies of value.

Prose analogy patents

Posted Dec 4, 2008 23:23 UTC (Thu) by tialaramex (subscriber, #21167) [Link] (3 responses)

This falls into the trap that got us software patents and a dozen other types of silly "intellectual property" in the first place.

Who says Steve lacks an incentive? It takes a profoundly narrow mind to look out into the world and conclude that (to pick some famous names from the shelves near me somewhat at random) Lewis Carroll, Ambrose Bierce and William Goldman were coldly calculating individuals, writing whatever would generate the maximum income. No, each of them had his reasons for writing, whether a pittance or a fortune was the reward, and in no case is their best work that which an accountant or a lawyer would have said was most certain to be profitable.

When we look historically, we find that the incentive granted by these new monopolies was always an incentive to people who were already rich, to screw people and get richer. The reality of software patents is patent trolls, just as the reality of US prohibition was organised crime and massive corruption in the police and judiciary. When you find yourself making a law to "fix" a problem that didn't exist and the law causes you problems you never had before, it's a bad law and ought to be repealed. And if the courts or the patent officials make bad law by practice where there was no law by statute, drive it out with better laws.

Prose analogy patents

Posted Dec 4, 2008 23:43 UTC (Thu) by felixfix (subscriber, #242) [Link] (2 responses)

I wish I knew how to second this properly. I have never understood why so many people think copyright is a necessity, but I have gotten so used to others thinking it necessary that my brain retreats into thinking of ways to fine tune it, when what it really needs is to disappear altogether. People wrote and painted and sang long before there was any copyright, and people still get together in garage bands and write blogs and create websites and youtube parodies without any renumeration.

I know it would eliminate the GPL, but I also believe that the GPL is only necessary in a world of copyright lawyers. The core idea behind GPL is that it is in everyone best interests to share work, such as the linux kernel, rather than hoard your own copy and struggle to keep up to date with continual merges to keep up with public changes. I have done that too often to think it a viable development method.

Thank you for reminding me again how much I detest the very idea of copyright.

Prose analogy patents

Posted Dec 5, 2008 1:20 UTC (Fri) by bojan (subscriber, #14302) [Link] (1 responses)

> when what it really needs is to disappear altogether

This really is a political problem. A powerful and influential minority convinced governments around the world that keeping their monopolies is a good idea. Well, if people are complaining when the price of petrol goes up, so should they when the price of music, books, films and software does the same. Otherwise, we've go nobody to blame but ourselves.

Prose analogy patents

Posted Dec 5, 2008 1:43 UTC (Fri) by felixfix (subscriber, #242) [Link]

The big money interests are digging their own grave as far as I'm concerned. They build these big life + 95 year fences around their factory work and forget that fences work both ways; not only have they kept their factory work safe from the public, but they have given the public every incentive to do their own work and ignore the factory work. Sooner or later, as Britney has shown, factory work will be so blandized and homogenized that it will only be used for elevators and dentists' offices. All the real popular culture has long since moved beyond their fences and out of their control. I don't know how much is under Creative Commons licenses, but I suspect it will only increase, and the entertainment factories have locked themselves out of that with their copyright fences.

Kill software patents

Posted Dec 5, 2008 0:38 UTC (Fri) by bojan (subscriber, #14302) [Link] (2 responses)

My favourite piece of anti-patent text is published on IP Australia web site (our equivalent of USPTO):

http://www.ipaustralia.gov.au/strategies/case_kambrk.shtml

Quite obviously:

- the inventor invented without patent protection
- many competitors entered the market, making the product cheap
- the inventor's company is still alive and well

I swear, if I didn't know better, I'd say that it was written by a disgruntled employee. There are overtones of sarcasm too - it completely reverts the logic as to why the patents are supposed to be a good idea (i.e. they tout "maximum profits for the inventor" rather than "public good"). It ends with "the inventor discovered our legally sanctined monopolies and is a happy monopolist these days". Hilarious!

Kill software patents

Posted Dec 5, 2008 23:49 UTC (Fri) by bignose (subscriber, #40) [Link] (1 responses)

I'm not confident, as you seem to be, that the author of the cited article had any awareness of the irony. It seems more a straightforward promotion of the mission of the site: to encourage treating ideas as property.

I find all too little indication they have any awareness of a motivation for getting good ideas into the public domain. Instead, the *entire site* appears to buy into the idea that artificial, legally-enforced restriction of natural usage of information is a good thing because it's a motive for the gatekeepers to profit.

Kill software patents

Posted Dec 7, 2008 1:01 UTC (Sun) by bojan (subscriber, #14302) [Link]

Oh, no! Quite the opposite - I'm quite sure they aren't aware of it (I had a private e-mail exchange with them and they indicated that they are completely unaware of the true purpose of the patent system). That's what makes it so hilarious. And sad.

Wouldn't Common Subexpression Elimination be considered prior art?

Posted Dec 3, 2008 18:03 UTC (Wed) by shapr (subscriber, #9077) [Link] (1 responses)

http://en.wikipedia.org/wiki/Common_subexpression_elimina... has been around for a few years already, the oldest citation on the wikipedia page is from 1970, even older than me!

Wouldn't Common Subexpression Elimination be considered prior art?

Posted Dec 3, 2008 19:03 UTC (Wed) by flewellyn (subscriber, #5047) [Link]

No, that's a compiler optimization of code expressions. This is a runtime optimization of memory access.

KSM runs into patent trouble

Posted Dec 3, 2008 20:05 UTC (Wed) by jordanb (guest, #45668) [Link] (9 responses)

I think Mr. Monakhov would do well to quit looking at patent applications.

Without the publicity he's created this may never have become an issue. Certainly if you wanted to render just about any software unusable you could do so by researching all the potential patent conflicts and bring them to the attention of the programmers, forcing them to neuter their software to avoid "willful infringement."

As far as I'm concerned VMWare is the biggest pile of scumballs this side of NVIDIA so I have no doubt that they'll use this to maximize their own benefit. The biggest issue here (beyond the fact that the patent system is broken) is that well intentioned people should *not* be researching and advertising potential patent conflicts. Let the patent holders do their own homework, for Christ's sake!

KSM runs into patent trouble

Posted Dec 3, 2008 22:57 UTC (Wed) by tialaramex (subscriber, #21167) [Link]

As a special case it's worth doing the research if you have some confidence you'll find nothing, and if you expect "We looked and found nothing" to be a major "selling point" for your software. See GNU zip (gzip) IIRC.

KSM runs into patent trouble

Posted Dec 3, 2008 23:02 UTC (Wed) by mlankhorst (subscriber, #52260) [Link] (3 responses)

Sadly this is true, when I worked at a software company the first thing
they said was: Don't look at patents. If you however still believe that
you infringe on one, only contact a lawyer, because the client attorney
conversations are confidential. Looking for software patents is just
asking for troubles. It's better to stay completely ignorant.

To the best of my knowledge, my current debian system infringes on zero
patents. :) .. and I'm not even going to look for anything that might
possibly infringe ..

KSM runs into patent trouble

Posted Dec 3, 2008 23:22 UTC (Wed) by drag (guest, #31333) [Link] (2 responses)

Plus if you have a record of going around and looking for patents then you could be shooting yourself in the foot.

Willful violation of patents, if proven, triples the damages awarded to the patent holder. It's much better to ignore patents and accidentally violate them then be a position were the judge can be convinced that you probably knew about the patent.

KSM runs into patent trouble

Posted Dec 4, 2008 0:46 UTC (Thu) by kev009 (guest, #43906) [Link] (1 responses)

If you are in the business of Linux like Redhat, then letting this get into the kernel with your name on it is a bad idea to begin with. For the hackers out there doing things on their own, I'm inclined to agree but it would be downright stupid for a business not to perform some CYA (Check Your Ass) - especially if they are considering providing patent indemnification.

KSM runs into patent trouble

Posted Dec 4, 2008 4:26 UTC (Thu) by drag (guest, #31333) [Link]

Well the deal with software patents is that you _can't_ check your ass.

It would require having a team of people who are experts in patent law and programming following all your developers around and checking on projects your using in order to try to link against patents.

Even then your not going to avoid lawsuits from patent trolls.

Since there is no practical defense against patents then there isn't much you can do. Sure if your notified, like in this case, then you are forced to act, but it's definitely not something you want to volunteer for, especially when your in business. No benefit for you, all pain, no profits.

Patents and LWN

Posted Dec 4, 2008 0:47 UTC (Thu) by dmarti (subscriber, #11625) [Link] (2 responses)

Attention corporate development managers! Now you can subscribe to the special no-patent-stories edition of LWN, only $1000 per seat!

Patents and LWN

Posted Dec 4, 2008 2:16 UTC (Thu) by corbet (editor, #1) [Link] (1 responses)

Hey, man, didn't you see the embargo date on the press release? We weren't going to announce that until next week!

Patents and LWN

Posted Dec 4, 2008 16:17 UTC (Thu) by felixfix (subscriber, #242) [Link]

That's ok; this is subscriber-only content until then anyway, right?

KSM runs into patent trouble

Posted Dec 4, 2008 0:59 UTC (Thu) by kbee (subscriber, #4468) [Link]

I like Tim Bray's story of how he realized software patents are ubiquitous: http://www.tbray.org/ongoing/When/200x/2004/08/05/LinuxPa...

What security issue?

Posted Dec 4, 2008 1:45 UTC (Thu) by NCunningham (guest, #6457) [Link] (3 responses)

> Processes could create a page of memory with known contents then, after
> waiting for the checker process (or kernel thread) to run, see if memory
> usage has increased.

I don't believe that's a real security issue at all. Absolutely anything could run in the meantime, with memory being both freed and allocated by completely unrelated causes. At best, such processes would be able to say it was possible that the page was shared, which really says nothing.

What security issue?

Posted Dec 4, 2008 3:12 UTC (Thu) by mjg59 (subscriber, #23239) [Link] (1 responses)

Anything could run, but it's possible that nothing will. And that means that a sufficient number of repetitions may show a significant deviation from what you'd expect from chance alone, which is an information leak.

What security issue?

Posted Dec 5, 2008 0:11 UTC (Fri) by nix (subscriber, #2304) [Link]

TBH preventing information leaks on any single system is a hopeless task:
there are far too many potential avenues, and when you get right down to
it they *are* one single system, so one process consuming a shareable
resource will always be observable by another process attempting to get
access to the same resource. (Crude example: time. Busywait, watching the
time: if it skips, you know someone else is using the same core.)

If you want to avoid information leaks, run the high-sensitivity no-leak
stuff on a different physical machine. Nothing else is safe enough for the
paranoid, and only the paranoid will really care about this anyway.

What security issue?

Posted Dec 11, 2008 14:49 UTC (Thu) by anton (subscriber, #25547) [Link]

I think a more reliable leak is to then write in the page, and see if the write takes a long time (due to copy-on-write). There were other potential information leaks discussed, but IMO they were all pretty far-fetched and can be defended against (e.g., don't make it predictable when pages will be merged; on the application side, when inputting passwords, initialize the buffer with random data).

KSM runs into patent trouble

Posted Dec 4, 2008 8:10 UTC (Thu) by Felix.Braun (guest, #3032) [Link] (4 responses)

Why does US-law dictate what gets into the kernel and what doesn't? If I remember correctly, while the US had hissy-fits about encryption software, there used to be an international fork of the kernel that included strong encryption. If KSM doesn't get included into mainline because of this, it might be time for distributors to create special feature-stripped versions of their distributions for the US, while the rest of the world can profit from new developments in software engineering.

KSM runs into patent trouble

Posted Dec 4, 2008 8:13 UTC (Thu) by Felix.Braun (guest, #3032) [Link] (1 responses)

Not to single out the US, there are probably numerous other jurisdictions that recognise software patents (the EU might just get there). So this feature-stripped distribution should be directed towards all jurisdictions hampered by software patent laws.

KSM runs into patent trouble

Posted Dec 4, 2008 22:51 UTC (Thu) by adegeus (guest, #22055) [Link]

The turnaround of the EU to the dark side of US software
patent style has not worked out quite as succesful for
the IP lords so far.

Perhaps dragging this issue for another few years in the EU
is just enough before the whole patent system will collapse all
together. Remember that by 2013 there will be a stock
of 1 million stupid patent applications be waiting for
analysis by the USPTO, and the patent database will be
a black hole infringing itself from one side to the other.

Patents don't warrant a fork

Posted Dec 4, 2008 8:45 UTC (Thu) by khim (subscriber, #9252) [Link] (1 responses)

Other projects had such issues for years. GIF patend, IDEA (ecryption algorythm) patent, etc. They all just had switches to enable them (default is "disabled", of course). Remember: kernel source can not infringe the patent - it's just a bunch of text. If you want to create binary - it's up to you to prove taht you are not infringing. The one who'll bring compiled binary of KSM to US will be infringer, not kernel developers...

Patents don't warrant a fork

Posted Dec 5, 2008 13:21 UTC (Fri) by cortana (subscriber, #24596) [Link]

I've seen the assertion that source does not infringe several times... but can anyone back it up? Otherwise, we could just implement our MPEG encoders in Python and not have to worry about this patent nonsense... :)

KSM runs into patent trouble

Posted Dec 4, 2008 8:17 UTC (Thu) by hltbdivl (guest, #39740) [Link] (1 responses)

Just wanted to point out that "VMware" is spelled with a lower-case 'w'. The upper-case 'W' name was replaced quite a few years back, I believe.

KSM runs into patent trouble

Posted Dec 4, 2008 14:52 UTC (Thu) by jake (editor, #205) [Link]

> Just wanted to point out that "VMware" is spelled with a lower-case 'w'.
> The upper-case 'W' name was replaced quite a few years back, I believe.

Ahhh, so it is. Fixed, thanks!

jake

KSM runs into patent trouble

Posted Dec 4, 2008 10:54 UTC (Thu) by berndp (guest, #52035) [Link]

VMware can simply drop that patent because of the clear prior art. Everything else is sponsoring of the patent system.

KSM runs into patent trouble

Posted Dec 4, 2008 11:39 UTC (Thu) by etienne_lorrain@yahoo.fr (guest, #38022) [Link]

GPL v2.1 : Your rights under this license are automatically terminated if you are looking for patents, have threaten to use, or used patents against a software copyrighted by this license.
To at least have the same protection as non open-source software...

KSM runs into patent trouble

Posted Dec 11, 2008 18:10 UTC (Thu) by xorbe (guest, #3165) [Link]

How can one patent what the hardware was designed to do? By another company no less. It's the CPU companies that should be upset that others are trying to take away what the CPU Designers giveth.