Java - How to implement bit stealing from references

Question

When it comes to algorithms for lock free / wait free data structures, Some algorithms will steal the 2 least significant bits from a pointer since they aren't used, and use them as status bits (like if a node is logically deleted or something). I figured that in java, I'd just use the AtomicStampedReference instead of bit stealing. However, I realized that the only way to solve the ABA problem in java is to use the AtomicStampedReference to keep track of whether a node was changed or not.

NOTE: If your'e not sure what the ABA problem is, wikipedia's gives a wonderful example explaining how badly things gets screwed up by it: https://en.wikipedia.org/wiki/ABA_problem

NOTE: The reason I say the ONLY way to solve the ABA problem is to use the AtomicStampedReference is based on this post: http://tutorials.jenkov.com/java-util-concurrent/atomicstampedreference.html#atomicstampedreference-and-the-a-b-a-problem

So, since I can't use the integer in the atomic stamped reference to keep track of things like logical deletion anymore, is there a way I can steal the unused bits in the reference itself? I tried to access the "unsafe" package to do this task by calling:

import sun.misc.Unsafe;

But when I do that, I get the following error from Eclipse:

Access restriction: The type Unsafe is not accessible due to restriction on required library C:\Program Files\Java\jre1.8.0_40\lib\rt.jar

Anyone have any ideas? If you're curious what I'm trying to do, I'm trying to implement a thread safe lock free hashmap in java as a school project. And I need to use the 2 LSB bits to differentiate between 3 different node types: a data node (00), a marked data node (01), or an array node (10)

EDIT: I should mention, I need the 2 status bits to be inside the atomic reference. The reason I need this is because I'm going to be doing compare and swap operations, and I need to Compare And Swap to fail if a data node (00) gets marked (01), or turned into an arrayNode(10). I originally used the integer in the AtomicStampedReference for this, but I can't do that anymore as the AtomicStampedReference should be reserved to prevent problems caused by ABA.

Answer 1

Okay, so it's impossible to steal bits from references in Java, but I ended up stealing bits from the atomic stamped reference. I stole the 2 MSB bits from the integer stamp to be used as status bits, and I used the remaining 30 bits in the integer as a counter. I can do this since java lets you do bit operations on integers:

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

I implemented and tested this in my java concurrent hashmap code. This solves the ABA problem, and still allows me to keep track of whether the reference is pointing to a node, marked node, or an arraynode.

Thanks you type_outcast for making the suggestion of stealing bits from the integer of the AtomicStampedReference!

EDIT I think I'll post the functions I wrote, to use the lower 30 bits of the integer as a counter, and the upper 2 bits as flags. The functions take in the integer of the AtomicStampedReference as the input, and the output depends on the function. I hope it helps anyone who might have a similar situation.

//get the incremented counter without messing up the mask bits
//if already at highest value (2^30 - 1, or 1073741823, reset to 0)
private int custInc(int rawStamp){
    int markedBits = 0xC0000000 & rawStamp;
    if (getUnmarkedStamp(rawStamp) == 1073741823)
        return (0 | markedBits);
    else 
        return ((rawStamp + 1) | markedBits);
}

//get the stamp value without the marked bits
private int getUnmarkedStamp(int rawStamp){
    int stampMask = 0x3FFFFFFF;
    return stampMask & rawStamp;
}


//call this to determine if the AtomicStampedReference is pointing to an array node
//10XXXXX... indicates arrayNode;
//01XXXXX... indicates marked data node
//00XXXXX... indicates a normal data node
private boolean isStampArrayNode(int rawStamp){
    int isArrayNodeMask = 0xC0000000;
    if ((isArrayNodeMask & rawStamp) == 0x80000000)
        return true;
    else 
        return false;               
}

//call this to determine if the AtomicStampedReference is pointing to an marked data node
//10XXXXX... indicates arrayNode;
//01XXXXX... indicates marked data node
//00XXXXX... indicates a normal data node
private boolean isStampMarkedDataNode(int rawStamp){
    int isArrayNodeMask = 0xC0000000;
    if ((isArrayNodeMask & rawStamp) == 0x40000000)
        return true;
    else 
        return false;               
}

//call this to get what the raw stamp value if you are to mark it as a marked data node
//01XXXXX... indicates marked data node.ensure that this is returned
private int getStampMarkedAsDataNode(int rawStamp){
    return (rawStamp | 0x40000000) & 0x7FFFFFFF;
}

//call this to get what the raw stamp value if you are to mark it as an array node
//10XXXXX... indicates arrayNode;
private int getStampMarkedAsArrayNode(int rawStamp){
    return (rawStamp | 0x80000000) & 0xBFFFFFFF;
}