I've got a data structure which consists of linked nodes. You can think of it as of a simple LinkedList. Each node of the list consists of some value and a next field pointing the other node or null if it is the last node. The first node works as a root, it has no value it only points to the next node. All the other nodes are practically immutable that is once they are created neither their value nor their next field change during lifetime, unless the structure is being disposed which relates to a specific situation.
One (only one) thread adds new nodes to the front of the list. It is accomplished by constructing a new object, setting its fields and setting the next field to the object pointed by the root, then setting the root's next field to this new node.
The other nodes browse through the structure only performing reads. They have a reference to the root node, then they go through the other nodes until they find what are looking for or reach the end of the list.
My question is: is it sufficient to make the next field volatile? From my understanding of java memory model, if the main thread (the one that adds new nodes) will perform a volatile write when adding a new node then everything will be synchronized just fine and no inconsistencies will occur.
Also is it right to assume that on x86 architecture reads of a volatile variable won't incur any performance degradation? As the other threads will frequently browse through the structure reading the next field it is important that this can be done freely without any memory barriers etc.
I also have one more concern. The threads that are going to browse the structure are also going to hold some additional nodes. These nodes will be completely thread-local that is they are going to be used by only the thread that created them and are not going to be shared at all. For these additional nodes it is unnecessary for the next field to be volatile. Moreover setting the volatile next field will issue a memory barrier which will cause an undesirable performance loss. I wonder is there a way to avoid this. Ideally it would be just perfect if the next field would work sometimes as a volatile field and sometimes as a normal field ;) or if I had a full control and could issue memory barriers on my own, whenever I need.
I also wondered would it be possible to somehow synchronize all these writes on a different volatile variable? For example some other completely unrelated static variable? Since volatile write flushes all the pending writes, wouldn't it be possible for the next field not to be volatile and instead a different volatile variable would be written after the updating thread does all the work?
It does not look very safe to me since there is no happens before relation and the previous writes might get reordered. Next field assignments could be reoredered with the value fields assignments leading to iterating threads observing inconsistent object state.
But maybe it is possible to come up with such a scheme that would be safe? How about this one:
updating thread first constructs a new object, initializes its value fields, sets its next field to node pointed by the root node, performs a volatile write on some static variable, sets the next field of the root node to the newly created node