Jump to content
  • Advertisement
Sign in to follow this  
Catafriggm

Lock-Free List

This topic is 4837 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for a method of creating a lock-free, thread-safe linked list in C++. It needs to work using compare-and-store operations no larger than the pointer size (thus no sequence counts), and without a garbage collector (thus tag before unlink is not sufficient). Anybody have anything to recommend?

Share this post


Link to post
Share on other sites
Advertisement
Why only pointer size CAS? amd64 has restricted address space to 40 bits for the explicit purpose of allowing an ABA/tag count field, and ia32 has cmpxchg8b.

For the memory management question, you have to know 1) can you just afford to leak it? 2) must it actually be freed, or can it go on a LF stack "freelist"?

Without more information and the intended purpose, no meaningful information can be given.

Actually, this sounds like a forlorn hope anyway. You will need assembly to implement CAS (on each platform!), for memory barriers (heh, P4s actually reorder reads) and to make sure compiler optimizations don't screw with your very sensitive algorithm.
Recommendation: use an existing library - lock-free stuff is a minefield (spoken as one who is specializing in this at Uni).

Share this post


Link to post
Share on other sites
Quote:
Original post by Jan Wassenberg
amd64 has restricted address space to 40 bits for the explicit purpose of allowing an ABA/tag count field

Where did you hear that? I'm looking in the x86-64 manual 1; in section 2.1.4 it states that 64-bit virtual addresses are translated to 52-bit physical addresses, but I don't see any limits on virtual address sizes. And in volume 2 (section 1.1.2) it says that x86-64 supports 16 exabytes of virtual address space (that's 2^64).

Anyway, I'm attempting to add a lock-free list to my class library (already have stuff like atomic functions implemented for multiple archetectures). Since it's part of a library, I can't guarantee what the user will do with a list item after they delete it from a list (but presumably they'll free the memory).

[Edited by - Catafriggm on August 21, 2005 4:01:27 PM]

Share this post


Link to post
Share on other sites
Quote:
Where did you hear that? I'm looking in the x86-64 manual 1; in section 2.1.4 it states that 64-bit virtual addresses are translated to 52-bit physical addresses, but I don't see any limits on virtual address sizes. And in volume 2 (section 1.1.2) it says that x86-64 supports 16 exabytes of virtual address space (that's 2^64).
Give it a shot.. :)
In short: 4 page tables yield 48 bits, there are only 40 address lines and the OS (Windows) gives you this much per process.

Quote:
Anyway, I'm attempting to add a lock-free list to my class library (already have stuff like atomic functions implemented for multiple archetectures).

OK.

Quote:
Since it's part of a library, I can't guarantee what the user will do with a list item after they delete it from a list (but presumably they'll free the memory).

I mean differently - what is your free() call to guarantee? Should it allow infinite alloc/free pairs, or effectively leak the memory?
For general usage, you will need some sort of garbage collection after all - this allows arbitrary reuse of memory rather than requiring it to remain valid as with refcounts (because someone may still be waiting to access it). Linux uses RCU because it knows when all processes have gone through a quiescent state (and are therefore no longer holding refs). Hazard pointers are a good alternative: see M. Michael's "High Performance Dynamic Lock-Free Hash Tables and List-Based Sets".

One major bummer is that you need a membar after setting each hazard pointer, which slows things down considerably. Oh well.

// edit: fix typo

[Edited by - Jan Wassenberg on August 22, 2005 7:47:41 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!