Dealing with ABA

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Dealing with ABA

Chris Vest
... when just allocating objects and letting the GC take care of it is not an option.

I have a concurrent data structure that is implemented in terms of volatile reads, getAndSet and compareAndSet. Currently I'm allocating objects to avoid any ABA problems, but due to the scale of the data I would like to work with, I'm working on moving it off-heap: tighter layout & packing, and not having object headers, means that I can cut the memory usage in half this way. However, this also means that some of the fields - pointers to other parts of memory - become susceptible to the ABA problem.

What options do I have for coping with that? I'm still writing Java (or JVMese?) so if C++ have something clever built in, then that won't be immediately applicable :)

Thanks,
Chris
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Dealing with ABA

Doug Lea
On 01/02/2017 03:27 PM, Chris Vest wrote:

> I have a concurrent data structure that is implemented in terms of
> volatile reads, getAndSet and compareAndSet. Currently I'm allocating
> objects to avoid any ABA problems, but due to the scale of the data I
> would like to work with, I'm working on moving it off-heap: tighter
> layout & packing, and not having object headers, means that I can cut
> the memory usage in half this way. However, this also means that some
> of the fields - pointers to other parts of memory - become
> susceptible to the ABA problem.
>
> What options do I have for coping with that? I'm still writing Java
> (or JVMese?) so if C++ have something clever built in, then that
> won't be immediately applicable :)
>

There's no magic solution. To use CAS, you need enough version bits
to cover the maximum gap in overwritten versions that a caller
can see. Which is equivalent to determining the maximum gap before
a GC would be sure to collect if it were a regular reference.
When you can bound this below an approximation of infinity
(as in 64bit refs), you can use fewer version bits, but they
still need to be atomically CAS-able, so even then you generally
end up using 64bits total (and ignore version bits on deref).

Without all this, the best you can do is to use locks,
other lock-like constructions, or techniques like hazard
pointers that require per-thread and per-use bookkeeping.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest