Does SCO own read-copy-update? [LWN.net]

Thanks to Con Zymaris for pointing us to this interview in The Age with Laura Didio, the Yankee Group analyst who signed SCO's NDA and looked at the company's evidence. Says Laura:

SCO claims there are multiple instances of copyright violations. SCO said these include: NUMA (Non Uniform Memory access) a mechanism for enabling large multiprocessing systems, RCU (Read Copy Update) (and) SMP.

Now, it's hard to point at a particular spot in the kernel and say "this is the NUMA (or SMP) implementation;" that code tends to be widely distributed. But read-copy-update is a different story. RCU is a complex locking technique that is well suited to data structures that are read often and modified relatively rarely; LWN covered RCU on the Kernel Page almost one year ago. The RCU patches did indeed come from IBM, with early patches showing up in the first part of 2001. IBM also presented RCU at the 2001 Ottawa Linux Symposium. SCO could conceivably have a case here.

The origins of RCU are described in this paper by Paul McKenney and John Slingwine. In the acknowledgements there you'll find:

This work was done with the aid of Macsyma, a large symbolic manipulation program developed at the MIT Laboratory for Computer Science and supported from 1975 to 1983 by the National Aeronautics and Space Administration under grant NSG 1323, by the Office of Naval Research under grant N00014-77-C-0641, by the U. S. Department of Energy under grant ET-78-C-02-4687, and by the U. S. Air Force under grant F49620-79-C-020, between 1982 and 1992 by Symbolics, Inc. of Burlington Mass., and since 1992 by Macsyma, Inc. of Arlington, Mass. Macsyma is a registered trademark of Macsyma, Inc.

The paper is intense and detailed - if its authors copied the technique from Unix, they went to unusual lengths to track down earlier work, perform benchmarking, and apply complicated mathematics to the question of which locking scheme is best. The real proof of origin will be in the reports the authors sent back to various funding agencies over a period of almost thirty years. It would appear, however, that SCO is going to have a hard time establishing ownership of this technique.

The code, however, could be a different story. The original Linux RCU patch was taken out of Sequent's old Dynix/ptx operating system. Information on Dynix/ptx is a little hard to come by now, but the Internet Archive has its uses... here's a copy of a Sequent.com page from 2000 describing the system. Among other things, this page says:

In 1998 Sequent (now merged with IBM) joined IBM and Intel in Project Monterey to develop an industry standard, high volume, enterprise Unix. As a member of the Project Monterey product line, NUMA-Q's high-end operating system, DYNIX/ptx, is being enhanced to provide increased commonality of technologies with AIX and Project Monterey for IA-64 and a common application development environment.

So, work from project Monterey did go into Dynix, and code from Dynix went (after some significant transformations) into Linux. So it is truly possible that SCO is sitting on a code base which contains an RCU implementation that is remarkably similar to the one found in the Linux 2.5 kernel. Who owns that code, however, will depend entirely on the history of contracts between SCO and IBM. It seems unlikely that RCU was part of the original Unix code base; more likely it was added to Monterey by Sequent/IBM. Depending on what contracts IBM signed, it may well have given up the right to release the RCU code under the GPL. Or maybe not.

RCU is used in several places in the 2.5 kernel. It has, in general, been retrofitted into existing areas of code as a performance improvement. If need be, those patches could certainly be reversed and RCU removed from the kernel. It would slow down 2.6, and have a small performance impact, but it would not be that big of a problem. But that is an issue for the future; SCO first must prove its rights to the code.

to post comments

Does SCO own read-copy-update?

Posted Jun 13, 2003 14:40 UTC (Fri) by StevenCole (guest, #3068) [Link] (3 responses)

Read-copy-update technology is covered by US Patent 5,442,758 "Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring".

This patent lists the
Inventors: Slingwine; John D. (Beaverton, OR); McKenney; Paul E. (Beaverton, OR)
Assignee: Sequent Computer Systems, Inc. (Beaverton, OR)

Evidently, on 08/15/1999, that patent expired due to non-payment of a maintenance fee, but on 05/31/2000 a petition to accept late payment of the fee was filed, and on 06/14/2000 that petition was granted.

For additional information on this patent, go to the USPTO Patent Full-Text and Image Database. Select Patent Number in Field 1 and enter 5442758 in Term 1.

If SCO's code is using RCU, they may be infringing on that patent.

Does SCO own read-copy-update?

Posted Jun 13, 2003 15:08 UTC (Fri) by freeio (guest, #9622) [Link] (1 responses)

Sequent is now part of IBM, is it not? One has to assume that the Monterey agreements included cross-licensing of patents between SCO and IBM, and so SCO is probably covered in its use of the technique described in the patent.

But then again, since IBM is supporting Linux, there is no problem with Linux using the technique (as opposed to the actual code) either. If IBM contibuted code that used the technique (under GPL) then the technique is OK for that use even if the exact implementation were not.

Marty

Does SCO own read-copy-update?

Posted Jun 13, 2003 15:25 UTC (Fri) by shahms (guest, #8877) [Link]

Of course, even if the Monterey agreements included cross-licensing agreements suing for breach of contract certainly puts them in a dubious position wrt those other agreements. Assuming the Linux RCU code in question was copied from SCO, doesn't the existance of this patent mean that, either way, SCO loses? (I'd pretty much assumed that anyway, even if SCO wins the lawsuit it means they exist as a viable entity for what, another two years?)

If SCO wins the lawsuit on copyright infringement, the RCU code has to be removed from Linux, whoo, it can be rewritten (the GPL doesn't prevent patented algorithms from being used, it just states that the GPL implementation of that algorithm must be "freely redistributable"). But SCO is SOL, given that I don't think IBM is going to say "we just lost a lawsuit to you, so we're feeling inclined to just let you use an algorithm we have a patent on without paying for it" more likely they'll say: "you're free to use the GPL implementation, but if you do, you'd better GPL UnixWare or we'll sue *you* for copyright and patent infringement"

IBM owns Sequent (and the patent), employs one of two inventors

Posted Jun 13, 2003 15:43 UTC (Fri) by emk (subscriber, #1128) [Link]

IBM apparently bought Sequent for $810 million dollars. Therefore, if Sequent is the assignee for the RCU patent, IBM owns the patent.

IBM also employed McKenny, one of the two inventors of RCU.

Since RCU was published and patented, SCO can hardly claim RCU is a trade secret. And since IBM appears to control the RCU patent, SCO doesn't have any obvious way to claim patent infringement.

This leaves charges of copyright infringement. For IBM to have infringed on SCO copyrights, SCO would need to have implemented a technique patented by Sequent, and given the code to Sequent. This is possible, but hard to believe. It's certainly more plausible that Sequent wrote the RCU code themselves and later contributed it to Project Monterey, from where it migrated into SCO's code base. But there's no way to tell.

It's also possible that every Project Monterey participant signed a contract with SCO, handing over control of any patents and copyrights for work they developed independently. But again, this is hard to believe.

In any event, the original RCU diffs added only 1,811 lines to the kernel, including copyright notices and documentation. A top-notch C hacker working in user space can average 250 lines/day on tricky algorithms (I've seen it done), so we're looking at a few engineer-months, maximum.

This first concrete allegation of wrongdoing looks pretty marginal. I was expecting something less ambiguous; perhaps a few hundred lines of random subroutines from the SVR4 code, contributed by somebody who didn't understand the responsibilities of a SVR4 license. If SCO wants to claim they own the RCU code, they'd better be prepared to show they actually wrote it, and didn't just misplace the copyright notices when borrowing some of Sequent's code.

Does SCO own read-copy-update?

Posted Jun 13, 2003 14:57 UTC (Fri) by keithw (guest, #3127) [Link]

Or linux is infringing on it, or both...

Does SCO own read-copy-update?

Posted Jun 13, 2003 15:27 UTC (Fri) by southey (guest, #9466) [Link] (1 responses)

This seems to show that IBM has been very careful by going back to original code that predates this project or was unused (JFS came via OS2). Second, the terms of the Project Monterey contract needs to be made public, especially if exclusive rights of code were made. Otherwise there is nothing stopping Sequent and/or IBM from providing the code to two different places under two different licenses. This would mean that SCO doesn't have a case with this code and only can show that IBM may have used knowledge gained to improve this code. But, as pointed out by the NZheretic article, IBM can also claim the same.

Does SCO own read-copy-update?

Posted Jun 13, 2003 18:52 UTC (Fri) by torsten (guest, #4137) [Link]

Second, the terms of the Project Monterey contract needs to be made public, especially if exclusive rights of code were made.

SCO has, from the beginning, stated that IBM violated their mutual contract by breaking off from the Monterrey project to develop Linux. I think the interpretation of the contract from the Monterrey project will be the defining factor of infringement.

The only real problem for IBM is if they already agreed not to share Monterrey code outside of that project, and are still bound by that agreement. We'll see.

Bach?

Posted Jun 13, 2003 15:48 UTC (Fri) by eru (subscriber, #2753) [Link]

A quote from The Age interview: The Yankee Group as well as the other analyst firms and members of the press, were only shown small portions of a few pieces of code. In my case, I saw Unix System V, version 4.1. Incidentally, this particular code is from the early 1980s, and hence predates Linus Torvalds' first Linux code.

I wonder if she was seeing code snippets that might appear (as C-like pseudocode) in Maurice J. Bach's The Design of the Unix Operating System, a widely read text book? I could imagine some algorithms adapted from it appearing in the kernel, but would that be illegal copying of Unix code?

Does SCO own read-copy-update?

Posted Jun 13, 2003 15:51 UTC (Fri) by ssharkey (guest, #4451) [Link] (2 responses)

If you look at the patch, there are several places where the following
copyright occurs:

+ *
+ * Copyright (c) International Business Machines Corp., 2001
+ *

And this comment also stands out:

+ * Author: Dipankar Sarma <dipankar@sequent.com>
+ * (Based on a Dynix/ptx implementation by
+ * Paul Mckenney <paul.mckenney@us.ibm.com>)
+ *

No SCO copyrights occur anywhere that I could find in the patch.

*ASSUMING* that IBM did not assign the copyrights to SCO at some
point in it's relationship, HOW, exactly, does SCO claim any
ownership rights?

The original author was from Sequent, based on code from an
IBM employee (who also happens to be the author of the paper
cited in LWN, and apparently contributed to IBM's patenting the
technique). Unless SCO somehow obtained all the *exclusive*
copyrights (and rights to the associated patents) to all code
from Project Monterey, it's difficult to see where they have a
claim. In fact, IBM may certainly have patent infringment claims
vs SCO, and/or copyright violations if this code is indeed in
SCO Unix.

All this "proves" is that there is code from IBM in the kernel.
It does NOT prove that SCO ever had any rights to that code.

-Scott

Does SCO own read-copy-update?

Posted Jun 13, 2003 16:23 UTC (Fri) by iabervon (subscriber, #722) [Link] (1 responses)

It's possible that the Monterey contract gives each participant the right to use the code developed in it, but not the right to transfer the license to this code to outsiders without the permission of the other participants. This would make sense for a partnership agreement between proprietary software vendors, as it would prohibit commoditization of the results if one of the participants lost interest while letting each of the participants get their money's worth.

Does SCO own read-copy-update?

Posted Jun 13, 2003 16:50 UTC (Fri) by emk (subscriber, #1128) [Link]

Possibly. But I get the impression that the consortium members frequently donated their own, in-house code to Monterey. And if some code was written for Dynix/ptx (on behalf of Sequent), it seems likely the Sequent would retain rights to use the code independently. Would IBM or Sequent really sign a contract which said, "SCO can veto how you use code that you wrote?" Maybe they would, but I'd expect IBM's lawyers to be a bit more cautious than that.

The RCU code appears to have been written by one of the original RCU researchers for use in Dynix. IBM apparently now owns Dynix, and the RCU patent.

What about NUMA? That's Sequent-related, too.

Posted Jun 13, 2003 17:15 UTC (Fri) by emk (subscriber, #1128) [Link] (1 responses)

SCO has complained several times about SCO-owned NUMA code winding up in Unix. This claim has always struck me as odd, because SCO doesn't even support NUMA (link, link).

On the other hand, Sequent had deep expertise in NUMA. And Sequent was also the source of the Linux RCU implementation.

Since Sequent participated in Project Monetery (along with SCO and IBM), and appears to have been bought by IBM, it looks like Sequent may be a major focus of this case.

Perhaps SCO is suggesting that since Sequent's Dynix was a version of Unix, any technology developed by Sequent--no matter how far advanced beyond the ancient SVR4 code SCO owns--is therefore inevitably contaiminated with SCO's copyrighted code? Or are they suggesting that no Project Monterey-related technologies--even if they were largely developed by Sequent or IBM--can be included in Linux?

Either claim would be pretty aggressive. Any advanced techniques developed internally at Sequent would probably contain only miniscule traces of SVR4 code, if they contained anything at all. (Similar things could be said about IBM's OS/2 version of JFS, also mentioned in the SCO complaint.)

Of course, SCO started seriously looking at the GPL very recently--despite the enormous implications of the GPL for this case--so we have to assume that their lawyers aren't necessarily on the ball. And their initial complaint included lots of dumb errors, too. So maybe SCO is a bit confused, here. It's hard to say.

Bingo

Posted Jun 24, 2003 17:10 UTC (Tue) by booch (guest, #1416) [Link]

Perhaps SCO is suggesting that since Sequent's Dynix was a version of Unix, any technology developed by Sequent--no matter how far advanced beyond the ancient SVR4 code SCO owns--is therefore inevitably contaiminated with SCO's copyrighted code?

Give that man a cigar. SCO's amended complaint seems to make it clear that this is what SCO is basing pretty much their whole case on. As Cringely and a few other have pointed out, it's a pretty hard argument to win. The UNIX license does say that added code becomes part of UNIX. But if the code existed before it became a part of UNIX, then the author obviously must have a right to create unencumbered derivative works from the original source.

Let's assume IBM agreed not to release such code that later got added to UNIX. And assume that they lose the case on the grounds that they divulged information that by contract SCO did not allow. (The language in the contract is a little vague, so it's theoretically possible.) That still doesn't effect Linux. Because even though IBM contributed the code in violation of their contract, they did own the copyright. So after they pay for the violation of their contract, there's no more dispute.

Linux users/distributors are not a party to the contract, so they can't be held liable for anything to do with the contract (with the exception of intentionally disrupting a contract). There's no copyright infringement, since the code was contributed by the copyright owner. There's no patent infringement, since IBM owns the patents. SCO doesn't own the trademark to the word UNIX. So the only thing left they could use against Linux users is trade secret law. That's typically only used against the person who leaked the info, not everyone who distributes it. (The DeCSS case being a good counter-example.) And since IBM intentionnally gave away their copyrighted code, I think the copyright would override the trade secret in such a case. Especially if IBM has already paid for releasing such info to the public.

RCU, IBM, Sequent, and Paul McKenney

Posted Jun 13, 2003 17:18 UTC (Fri) by ncm (guest, #165) [Link]

I went to school with Paul McKenney.

He went off to work at Sequent a long time ago. While there, he and Slingwine invented RCU. (Somebody else at IBM invented it independently, later.) When IBM bought Sequent, they got Dynix, and Paul, and the patent.

Paul started working on getting RCU usage incorporated into Linux a few years back. The mailing list archives reveal that for way too long, several of the kernel maintainers were unconscionably rude over what turned out to be differences of macro naming style. Now the RCU technique is used in a half dozen places in the kernel, and its use will probably continue to grow. It's a brilliant technique, and remarkably underreported.

IBM has published a license allowing RCU to be used freely in GPLed code, but retains all other rights. The BSDs can't use it. One thing is certain, though: SCO doesn't own it. Interestingly, the patent implicitly forbids use of RCU in proprietary drivers. That is, the driver vendor would need a separate license from IBM. It's not clear whether proprietary drivers can even use the regular kernel header macros without a license.

Incidentally, while at Sequent, Paul also did seminal work on SMP/NUMA memory allocators, and some of the principles he identified are about to be folded into GNU libstdc++ memory management. I think the kernel memory allocator has yet to be blessed with McKenney goodness.

It doesn't matter whether is is right or wrong

Posted Jun 13, 2003 17:22 UTC (Fri) by xorbe (guest, #3165) [Link] (1 responses)

The company behavior has been completely unacceptable
concerning this matter, and they should be fined for,
uh, causing terror and financial disruption in the
marketplace for advancing their own agenda.

Prior art - maybe?

Posted Jun 15, 2003 13:38 UTC (Sun) by edt (guest, #842) [Link]

IBM's DMS product from the 70s-80s used something that could be called read
copy update. To avoid locking records being updated it would get the record,
save a copy let the user do his or her thing with it, get the record a second time,
this time locking it, compare the originals. If they were the same the update
would proceed, but the time the record was locked would be quite short.
They called this Save Compare mode. Could this be prior art?

Ed Tomlinson

ps. if my memory serves me correctly the product number was 5746-xc4

Does SCO own NUMA?

Posted Jun 17, 2003 16:31 UTC (Tue) by angdraug (subscriber, #7487) [Link] (1 responses)

Wasn't NUMA code in Linux introduced by SGI, not IBM?

SGI and NUMA

Posted Jun 19, 2003 20:24 UTC (Thu) by lovelace (guest, #278) [Link]

Yes, the NUMA code was first done by SGI. The question there is what licenses does SGI have with respect to the System V code? IRIX is a descendent of System V but what were the terms of their contract?

Does SCO own read-copy-update?

Posted Jun 20, 2003 13:35 UTC (Fri) by LenZ (subscriber, #1051) [Link]

Seems like Cringely has been reading this article too:

http://www.pbs.org/cringely/pulpit/pulpit20030619.html