java - stealing bits from references

Question

How do I steal 2 MSBs from an address to do an atomic operation? I'm trying to do a single word CAS

An example

public class Node
{
    long key;
    long value;
    Node lchild; // format is flag1,flag2,address
    Node rchild; // format is flag1,flag2,address
}

public void createNode()
{
    Node n1 = new Node(); //this should create a node with format 0,0,address1
}

public void setFlag1(Node n1)
{
    Now the new address should be in format 1,0,address1
}

public void setFlag2(Node n1)
{
    Now the new address should be in format 0,1,address1
}

AtomicReference could be used if I needed only one extra flag. AtomicStampedReference could be used but it is not efficient as it creates an extra box containing timeStamp and a reference.

A similar problem in C is discussed in stealing bits from a pointer

Answer 1

You can probably implement this using sun.misc.Unsafe

• http://www.docjar.com/docs/api/sun/misc/Unsafe.html

Among other things, this has a number of compareAndSwap methods that can work with arbitrary binary data within any Object.

Having said that, if you are implementing a binary search tree I'd suggest looking at immutable persistent data structures. Advantages of these include:

• They are thread safe by definition because of immutability
• They require no locks
• The ability to do structural sharing will be a big performance win once you start doing more complicated stuff (e.g. snapshotting of subtrees) - basically you avoid the need to take defensive copies.

Answer 2

This is impossible without implementing your own JVM which supports this kind of operations and deals with the flag bits properly, e.g. when doing GC (all references need to be identified at this point and moving collectors will need to change them). Even then, this is against the design principles of Java which do not include explicit dereferencing or pointer arithmetic (which I would count changing bits in a reference and masking them for dereferencing towards).

Instead, I would recommend you to create a new composite Edge type of the flags and the Node:

public class Node {
    long key;
    long value;
    Child lchild; // child = node reference + flags
    Child rchild;
}

// this is the edge type which should also be used to reference the root node with flags
public class Child {
    Node child;
    BitSet flags;

    public Child(Node node) {
        this.child = node;
        this.flags = new BitSet(2); // we initialize the flags with 00
    }
    public void setFlag(int index) {
        this.flags.set(index); // index would be 0 or 1 here for the two flags
    }
    public boolean isFlagSet(int index) {
        return this.flags.get(index); // index would be 0 or 1 here for the two flags
    }
}

Answer 3

Copying an extract from the book "The art of multiprocessor programming" p.215 by Maurice Herlihy and Nir Shavit:

As described in detail in Pragma 9.8.1, an AtomicMarkableReference object encapsulates both a reference to an object of type T and a Boolean mark. These fields can be atomically updated, either together or individually. We make each node’s next field an AtomicMarkableReference. Thread A logically removes currA by setting the mark bit in the node’s next field, and shares the physical removal with other threads performing add() or remove(): as each thread traverses the list, it cleans up the list by physically removing (using compareAndSet()) any marked nodes it encounters. In other words, threads performing add() and remove() do not traverse marked nodes, they remove them before continuing. The contains() method remains the same as in the LazyList algorithm, traversing all nodes whether they are marked or not, and testing if an item is in the list based on its key and mark.