On Fri, Jun 19, 2015 at 12:43 AM, Eugene Zatepyakin
<zatepya...@gmail.com> wrote:
> Hello,
>
> there are several ways to solve ABA problem. Most commonly used are Hazard
> Pointers and Versioned/Tagged pointers.
>
> Hazards are quite tricky implement especially targeting multiple platforms
> desktop/mobiles.
> So i was thinking about trying Tagged pointers approach.
> Here i see 2 ways: use hack with tagged pointer: single 64bit atomic or use
> full versioned pointer 2x64Bit values.
>
> I wonder what are the concerns when implementing hack-ish version:
> struct head_t final {
> node_t *node;
> // 64 bit pointer uses 48 bit addressing
> // the unused 16 bits are going to hold an identification number
> #if X64_PLATFORM
> using stack_id = uint16_t;
>
> inline head_t() noexcept : node{ nullptr } { }
> inline head_t(node_t* n) noexcept : node{ n } { }
> inline void create_id(const head_t& nid) { ((stack_id*)this)[3] =
> ((const stack_id*)&nid)[3] + 1; }
> inline node_t* next_pointer() { return
> (node_t*)((uint64_t)node & 0x0000ffffffffffff); }
>
> // 32 bit pointers are "full", so I use another 32bit piece of data for the
> counter
> // on 32bit x86, we can swap the entire 64 bits without a lock
> #else
> using stack_id = uint32_t;
> stack_id t_;
>
> inline head_t() noexcept : node{ nullptr }, t_{ 0 } { }
> inline head_t(node_t* n) noexcept : node{ n }, t_{ 0 } { }
> inline void create_id(const head_t& nid) { t_ = nid.t_ + 1; }
> inline node_t* next_pointer() { return node; }
> #endif
> inline void set(node_t* n, const head_t& nid) { node = n; if (node)
> create_id(nid); else create_id(*this); }
> };
>
> is it safe to assume this will alway work? or its not official and better go
> with full DCAS version:
> struct head_t final {
> uintptr_t aba_conter;
> node_t *node;
> };
>
> but this will most likely be problematic to implement on mobile
> platforms....
Hi Eugene,
In my practice 16-bit ABA counters work reasonably well.
AFAICT, Microsoft lock-free stack uses only 9-bit counters:
https://msdn.microsoft.com/en-us/library/windows/desktop/ms683482(v=vs.85).aspx
(at least in early days of 64-bit platforms, and that was the reason
to restrict address space to 44 bits)
There are several tricks to make counters more reliable:
- 48-th bit is user/kernel marker, so you can use it as well
- usually low 3 or 4 bits are zeros (or you can specifically make them
zero), so you can use them as well
- also you can use per-node counters, rather than single per-head counter
As for mobile platforms, it is dependent on characteristics of a
particular platform. Some mobile platforms has double-word CAS.
Generally you end up with platform-specific code for such components.
For example, see what we do in Go runtime in lfstack* files:
https://github.com/golang/go/tree/master/src/runtime
It does work on a variety of platforms, including mobile.
--
---
You received this message because you are subscribed to the Google Groups
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to lock-free+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/CAEeQi3u79goxQ3Dy2P1_dnMWdmZ0otEFT%2BM-XEOH2eHq-oomSw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
