A report from LWN.net suggests that there could be a patent problem with a technique called KSM, a memory management technology that is a candidate for inclusion in a future version of Linux.

KSM attempts to extend the idea of sharing memory pages between processes from just managing shared libraries, to any identical memory pages, such as running multiple copies of the same program, or virtualized guest operating systems.

The problem is that there appears to be a software patent held by VMware which seems to, at least in abstract, cover the operation of KSM. The patent, filed in 2001 and granted in 2004, still needs to be evaluated in detail, especially in the light of potential prior art in a previously abandoned Linux feature from 1998, called Mergemem.

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.

 

...

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.

Read the entire article from LWN.net.