Google Linux servers hit with $5m patent infringement verdict (The Register) [LWN.net]

Google Linux servers hit with $5m patent infringement verdict (The Register)

Posted Apr 22, 2011 9:35 UTC (Fri) by oldtomas (guest, #72579)
In reply to: Google Linux servers hit with $5m patent infringement verdict (The Register) by orcmid
Parent article: Google Linux servers hit with $5m patent infringement verdict (The Register)

"The Nemes patents (all filed in the last century) all involve hash-indexed records becoming obsolete in some way but not being deleted at once for some reason [...]"

"As far as I can tell, that is the novelty that is not dealt with in any of the extensive, existing work on hash-based searching of records"

Still not *that* surprising. I haven't my Knuth around, but I wouldn't be surprised to see that covered in one of the exercises. Especially when not doing linked lists but secondary hashing: then it's really problematic to "disappear" something from the collission chain (aka hash bucket).

Heck, I'm sure I've seen reordering of the chains on search (on the theory that you are going to search some entries more often than others, so bringing those to the front amortizes itself). I even think I've seen that in Knuth's classic.

How far is that patent nonsense going to take us?

to post comments

Google Linux servers hit with $5m patent infringement verdict (The Register)

Posted Apr 22, 2011 17:14 UTC (Fri) by orcmid (guest, #74478) [Link] (1 responses)

Knuth addresses the case of a delete operation by key not actually deleting the record on the linked-list but marking it deleted, with the record storage and list slot available for reclaiming at a later time, possibly by a new insertion having the same hash.

Knuth also raises (in my 2d edition copy) a case where there might be pointers to records from other than the hash-table index and some sort of reference counting might be needed to avoid deleting or reusing the actual record until the record actually becomes unreachable. This is the closest I have found that is a kind of "expiration." I don't know if that was in the 1973 edition cited in the patent itself. I obsserve that this is a situation that can arise in operating-system work, of course, and then race-condition avoidance, locking, and such come into the picture as well.

None of the other discussion of this kind of hash-table indexing, including in the exercises, touch any further on that nor the very specific claim of the patent.

The patent deals with removals where the expiration of a record is not by an effort to delete it by key but by virtue of some other condition that arises independent of use of the hash-table index. As I said, what the patent applies to is methods of removal that discover such expired records on the linked-list while it is being traversed on behalf of some other operation involving a record with the same hash code. The patent is quite specific about that, with some additional claims around details for limiting the number of such deletions done at one time.

An earlier comment mentioned a network application where some connections or network probes might time out. Another case might be indexes to the active records for running processes, or shared libraries and their stickiness, or something like that. I don't see this method being essential to any of those, but if it has been so used in Linux (or in some other way), an alternative is called for.

Places to make a hash of it

Posted Apr 22, 2011 18:11 UTC (Fri) by orcmid (guest, #74478) [Link]

As long as we're speculating on what sort of things might be handled with a hash-table mechanism that is covered by the patent we're concerned about, I should add the case of UUIDs. UIIDs (GUIDs to some of us) are quite heavily used these days and hashed-table lookups for them are not uncommon.

Whether and how that might figure in Linux use of the patented method is not anything I have a clue about. And without knowing what the actual cases are, it is difficult to speculate further about what would be a suitable work-around.

I presume that the Linux kernel developers are doing what they can to figure that out.