Add to del.icio.us     Digg this

December 15, 2008

KSM is defined as a normal action of the Linux kernel reducing memory usage by simply sharing identical memory pages between various processes.

For example, program text is always shared, but writable pages will also be shared between various Linux processes when the kernel knows that the contents of the memory are the same for all processes involved.

When a process calls fork(), all writable pages are turned into copy-on-write (COW) pages and shared between the parent and child. As long as neither Linux process modified the contents of any given page, that sharing can continue, with a corresponding reduction in memory utilization.

Copy-on-write with fork works simply because the kernel knows that each process expects to find the same contents in those specific pages. However, when the Linux kernel lacks that knowledge, it will generally be unable to arrange sharing of identical pages.

Of course, this would ordinarily be a problem, but the KSM developers have come up with a couple of situations where this kind of sharing opportunity might come about.

Currently proposed for inclusion in the main Linux kernel, KSM fully implements a potentially useful, but not particularly new mechanism. But 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 Linux kernel doesn't know about directly, thus cannot coalesce.

Various 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, the KSM technique appears to be patented by VM-Ware. 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.

As opposed to merely the addresses or page numbers of virtual memory pages that are accessible to one or more contexts, they are carefully examined one-by-one. 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. Windows dosen't have that feature.

The shared copy is then 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, 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.

This is important because there is some prior art to consider, namely the merged patch first announced in March of 1998.

Basically, it's essentially the same as the patented idea. It looks for identical context pages, then changes the memory states and their various 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 always 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.

Overall, free software projects may have time, but the other two are typically out of reach. Alan Cox suggests that perhaps the Linux Foundation could take a look at merged memory and its management. While that might eventually resolve the problem, it is a multi-year process at best.

There is a much quicker resolution available should VM-Ware wish to tackle this case. Like IBM has done with the RCU patent, VM-Ware could license its patent for use in GPL-licensed code.

Source: LWN.

Add to del.icio.us     Digg this

All logos, trade marks or service marks on this website are the property of their respective companies or owners.

ADVERTISERS:
Linux News Today.org is read by over 450,000 people involved in the field of Linux application development, professional Web hosting services, Linux security, Linux Web development, etc. Inquire about our reasonable advertising rates on our news website. One of our advertising representatives will be in touch with you. Simply email us to learn about our ad rates and how we can help drive relevant traffic to your website. Advertising space is limited.