Thread safety issues in free_list_heap

[goedderz]

Hi! We've started using immer and are very happy with it, thank you for your awesome work!

Along the way we stumbled upon the following problems when running concurrency tests with the ThreadSanitizer.

Currently, free_list_heap is not thread-safe. I'll describe here what can go wrong.

In free_list_heap::allocate, at https://github.com/arximboldi/immer/blob/master/immer/heap/free_list_heap.hpp#L41, a free_list_node* is read.

n = head().data;

A few lines later, n->next is read in the attempt to pop it from the free list:

head().data.compare_exchange_weak(n, n->next)

However, the free_list_node pointed to by n can, in between reading head().data in line 41 and dereferencing it in line 46, already be taken by another thread, passed to deallocate, and possibly actually be freed by base_t::deallocate. Thus rendering the n->next access a possible heap-use-after-free. The memory reclamation problem is ignored here.

Additionally, the same place suffers from the https://en.wikipedia.org/wiki/ABA_problem. In line 46, namely the expression head().data.compare_exchange_weak(n, n->next), n->next is read first. After that, the compare_exchange replaces head().data as long as its value is n. However, in between other threads could have taken nodes from the list. If one of those has taken the free_list_node pointed to by n, and put it back again, the compare exchange succeeds: But it is no longer the same object, and the value we got by reading n->next is now wrong.

[arximboldi]

Thank you a lot @goedderz for the report! I'm actually not unfamiliar with the ABA problem and I'm finding this a little bit embarrassing 😕 🙂

I'm very busy over the next couple of weeks, so if this is urgent for you, I'd appreciate it if you could submit a patch yourself.

Otherwise, I'd like to do a few sprints of work on the library over the late summer, and I will probably tackle it then, together with #82 and something along the lines of #120. I'm looking for sponsors also to be able to spend more time in dev and research in the library!

[goedderz]

Hi, thanks for your response! It's gladly not urgent, as it's so easy to plug in another heap policy for now. :) I sadly don't have the time to write a patch either, at least in the moment, but if that changes I'll get back to you.

[arximboldi]

Cool. In any case I'm grateful for the thorough investigation of the issue.

[maierlars]

Any updates on this? 🙂 @arximboldi

[arximboldi]

Haven't found time to work on this. If this is an issue for you, you can disable the free_list_heap in the memory_policy, or globally by doing:

#define IMMER_NO_FREE_LIST 1