Software Patents on Memory Allocators?

Emery Berger asks: "I'm a PhD. student at the University of Texas and the author of Hoard, an open source memory allocator for multiprocessors. After posting information about the latest pre-release to the Hoard mailing list, I received a cease-and-desist letter from Microquill, Inc., which markets memory management software, calling for me to stop distributing Hoard. They are claiming that my latest version of Hoard, which does DLL patching when running on Windows, infringes on their patent (which actually dynamically rewrites arbitrary executables). Because DLL patching is prior art and my technique is quite different from theirs, I think I'm in the clear. However, if anyone knows of systems from 1996 or earlier based on DLL patching (or any dynamic rewriting of a running executable), especially to change the memory allocator, that would really help."

Comments

Purify

[V. Mole]

Purify (now a Rational product) worked (On HP-UX, at least) by rewriting the system libraries with a new allocator, etc. I'm 90% sure that this was before '96. Hmmm, don't remember if it was the shared libraries or just the static ones. But it might be a starting point.

The Game Genie for the Nintendo.

[His name cannot be s]

The Game Genie I had for my 8 bit NES did that. It dynamically patched the running game to keep me from running out of lives.

In addition I had a SuperSnapshot cartridge for my Commodore64 that did the same thing, and that was back in ... 1988ish?

I'd say you are quite in the clear on that one.

SetFunction() from AmigaOS

[Gadzinka]

It is a quote from AmigaOS exec.library autodocs:

NAME

SetFunction -- change a function vector in a library

SYNOPSIS

oldFunc = SetFunction(library, funcOffset, funcEntry)

APTR SetFunction(struct Library *,LONG,APTR);

FUNCTION

SetFunction is a functional way of changing where vectors in a library point. They are changed in such a way that the checksumming process will never falsely declare a library to be invalid.

WARNING

If you use SetFunction on a function that can be called from interrupts, you are obligated to provide your own arbitration.

NOTE

SetFunction cannot be used on non-standard libraries like pre-V36 dos.library. Here you must manually Forbid(), preserve all 6 original bytes, set the new vector, SumLibrary(), then Permit().

This function was heavily used and abused by the system programmers on AmigaOS (e.g. for transparent decompression of data) since its erlieast days, which is mid-eighties AFAIR.

I believe it counts as prior art.

Robert

They're called overlays.

[Wojtek]

Yeah, they're called overlays. We've used'em for a while. Apart from that many people use function
pointers to load code into an executable at runtime.

show me the claims

[josepha48]

I didn't see what he is claiming. In order to actually know what his patent covers show us the claims of the patent.

I'm kinda supprised that a program got patented too. I would have thought that in 96 that would not have gotton patented as it IS software. Maybe you can just invalidate it that way. As a nonepatentable item.

Still can you show us the claims?

Re:show me the claims

[Ristretto]

This is a reply from Emery Berger. I've added links to the relevant patents in the text of the first letter from MicroQuill.

Re:show me the claims

[nerdlyone]

The fact that the letter writer (1) is not a lawyer and (2) quotes from the abstract rather than from the claims of the patent bodes well for you. They might just be trying to bully you into stopping.

You must look at the claims. That is what determines the scope of a patent. The abstract cannot even be referred to in court for interpreting the claims--it is legally meaningless, and the fact that the letter writer pointed you to the abstract as evidence you are infringing indicates he/she has no legal patent knowledge, or else maybe that their claims are not that good and they are just trying to scare you. Look at the claims.

Try GClist

[Yumpee]

Have you considered asking the GC mailing list? http://lists.tunes.org/mailman/listinfo/gclist

Coincidentally, there have been a couple of recent queries on gclist asking about patents on GC and memory management algorithms ...

Y.

What a shame

[ScroP]

HOARD is really a great library.

Its too bad buisnesses have to hold back the advancement of research in some area that could help improve things overall for everyone in the future just to make a few bucks.

FX32?

[ChiefArcher]

Didn't FX32 do this?
The Code that let you run x86 binaries on an Alpha Windows NT box..

I could be wrong.... but hey... whatever

ChiefArcher

Novell's Netware

[itwerx]

Netware 3.x (way prior to '96!) had several patches which loaded at run-time. Some of them fixed problems with memory allocation. Not sure where you'd get good evidence but an email to their tech-support might yield some results.
Novell is one of the few companies who actually has their programmers do tech-support on a rotating basis. Just ask that the email be forwarded to one of the OS programmers and they'd probably be willing to at least make a statement to that effect.

Re:Novell's Netware

[alanshot]

Dont count on it. Unless you manage to get buddy-buddy with the support engineer, you will probably get the same response everyone else does... "You are running Novell 3.x? and you want support? sorry, I am not even allowed to discuss it since it is no longer a currently supported product. Do you have a question on a current product? NO? sorry, cant help you then... goodbye. *click*" Last I heard, they would actually hang up on you (politely as possible) so that they didnt have to argue over support for an unsupported product.

How about Copliens book as prior art ?

[MeerCat]

In James Coplien's famous book of 1992, chapter 9 is all about patching running code with new code at run-time:

Chapter 9 also presents idioms supporting incremental run-time update. Implementations of this idiom are necessarily dependent on many details of the target platform. The gist of this material is to familiarize the reader with the level of technology at which incremental loading issues must be worked.

Might be worth seeing if any of that is useful as prior art, or the bibliography or uses he describes can illustrate that the problems and techniques were alreayd well known at the time.

T

lots of patching in the past

[mj6798]

It used to be very common to patch "vectors" in the BIOS and other parts of the operating system in order to replace system-supplied functions with user-supplied ones. A patent claim on this is, of course, ridiculous--it's a standard technique, widely used for just these kinds purposes. However, that might not keep the patent from causing lots of problems.

It may be easier to work around this claim. You may be able to implement roughly the same thing using the analogue of LD_PRELOAD--instead of patching the existing DLL, arrange for the linker to preload a DLL that overrides some functions. That may work even on Windows.

(The link you gave isn't working. Did the company give you the patent number?)

Re:lots of patching in the past

[Ristretto]

Emery Berger:

Here are the patent numbers: 5949972 and 6035426.

You can look these up by going to the US Patent Office search page.

prior art

[RonBurk]

There is plenty of prior art on the general subject of dynamic patching to intercept functions, though I'm not sure that's of any use to you.

The first patent you listed points to one example, from a magazine I once edited. Dynamically intercepting code was a popular topic around that time. A little poking also turned up Windows/DOS Developer's Journal May 1993 and August 1993, p. 35, where Paul Bonneau offers reusable code for "hooking" Windows functions on the fly.

Not being a lawyer, I naively assume you would want to try to get the aggressor to point out explicitly what aspect of their patent they feel is infringed by your code before doing anything else. Tom's ("Hi Tom!") assertion that the patent "covers the concept of patching the memory management library in a given process." is at the very least an overstatement, since the first patent itself provides prior art examples that patch the memory management library.

Finally, I have to wonder if there's any chance that you could use something like Microsoft's Patch-o-Rama to do the dirty work. That places some of the patching work out of your hands, but if the patent holder's main aim is to be anti-competitive rather than to enforce the actual limits of their patent, then it seems like there's not much to stop them from pressing forward with legal action.

It's a shame that patents are granted for things like this that are clearly techniques and not inventions at all. If this is an invention, then my dog is Edison reincarnate, as she has "invented" all manner of egress from the yard (and should be able to sue other dogs the world 'round).