AFAIK there are two known lock-free methods for implementing a lock-free linked list; Valois’ from 1995 using dummy nodes between objects (with bugs later corrected by M&S of the queue fame; it’s a problematic solution) and Harris from 2000, with the delete bit, which is the viable solution.
Harris (I phoned him – this is from him) invented the method while an intern at Sun. (Pretty bloody impressive :-) it means Sun owns the patent – which means Oracle now own the patent.
Interestingly, the patent was filed for in Nov 2000 but only granted in 2006. A friend of mine, a retired British patent agent, tells me that’s a long time; that they may have had trouble getting it past the examiner.
Now, important fact; the patent for this method exists and only exists in the USA. Patents have not been applied for (and remember – the original was filed twelve years ago now) in other domains.
The reason for this almost certainly is because only the USA permits software patents. The rest of the world wouldn’t allow this as a patent. (I made no comment on whether this is right or wrong; it is an observation).
So the first thing to consider is this; if you’re not using the method in the USA, you’re legally free to use it.
Now the biggie; I may be wrong – I may WELL be wrong (but let us see) – but I think there is a way to avoid the patent – so you can use the basic method (two stage delete, logical then physical) even in the USA.
(Note : I have written a British patent, with proof reading assistance from my retired patent agent friend. It’s only one, but it took bloody ages and was a LOT of work and it means I have some idea of what patents are about, how they’re structured internally and the legal significance of each section and what you have to do to avoid a patent).
The drawback is you need contigious double-word CAS, so this approach only works for x86/x64 and ARM.
Now, I’m assuming you’re familiar with the method described in Tim’s patent.
First, I will describe the technical alternative and then second I will explain why I think this avoids the patent.
So, the technical details;
The patented method uses single-word CAS and so steals a low-order bit from the pointer as the logical delete flag and must use CAS to raise that flag, since the pointer could change at any time.
Instead, with contigious double-word CAS, we can use the second word to hold the delete bit (wasteful, but hey :-) and as such we can use an atomic swap to raise the delete flag.
We can always blindly write, because it doesn’t matter if the delete flag is already raised.
Note I’m using garbage collection (RCU/epoch based) so I know the node won’t go away.
Now, the legal details;
To avoid a patent you basically have to avoid the claims. Claims are typically (as they are in this case) formed in chains – there is a root claim and then a series of claims which depend on that root. Avoid the root and you avoid the chain. In this patent, there are three roots, claims #1, #16 and #25.
The key issue that I see is the use throughout the claims, of the phrase “the update being conditional on the examination”.
Claim 1 : A non-blocking concurrent shared object representation encoded in a computer-readable medium, comprising: a linked-list of nodes encoding of a group of zero or more values; and linearizable operations defined to implement semantics of at least insert and remove operations on the group, wherein concurrent execution of the linearizable operations is mediated using a first synchronization primitive to encode a marked node indication signifying logical deletion of a corresponding one of the values from the group, wherein the first synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination.
So – we have a linked list, it’s linearizable, we have a two stage delete – logical then physical – where first synchronization primitive atomically examines and updates a single target, the updating being
conditional on the examination.
The patent uses single-word CAS and steals a low-order bit, so it has to use CAS to raise the logical delete flag.
Using contiguous double-word CAS means we can hold the logical delete bit in the second word and use a swap to raise the logical delete flag; the updating is not conditional on the examination. Claim 1 is avoided.
Claim 16 : A method of managing access to a linked-list of nodes susceptible to concurrent operations on a group encoded therein, the method comprising: separating deletion of a value from the group into at least two functional sequences; the first functional sequence performing a logical deletion of the value using a synchronization primitive to mark a corresponding one of the nodes; and the second functional sequence excising the marked node from the linked-list, wherein the synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination.
Same here; for the first stage, the logical delete, there is no update conditional on examination. There is for the second, the physical excising, but it doesn’t matter – the claim requires update conditional on examination for both.
Claim 25 : A computer program product encoded in at least one computer readable medium, the computer program product comprising: at least two functional sequences providing non-blocking access to a concurrent shared object, the concurrent shared object instantiable as a linked-list of nodes
encoding of a group of zero or more values; a first of the functional sequences defined to implement semantics of an insert operation on the group; and a second of the functional sequences defined to implement semantics of a remove operation on the group, wherein instances of the functional sequences are linearizable and concurrent execution thereof by plural processors of a multiprocessor is mediated using a synchronization primitive to encode a marked node indication signifying logical deletion of a corresponding one of the values from the group with separate physical excision of the corresponding node, wherein the synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination.
And exactly the same here. The claim requires the use of CAS (update being conditional on examination) for both stages and we avoid it for the first stage.