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....
--
---
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/455ca478-0c29-4d8f-b46e-fac9e4385671%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
