Valgrind possible leak

[tmpgnh]

Hi, Valgrind is reporting a possible loss when I'm using a H-M map. Is this known, or a false positive, or I'm using it in the wrong way? Thanks, /g

% cat x.cc
#include <xenium/harris_michael_hash_map.hpp>
#include <xenium/reclamation/lock_free_ref_count.hpp>
using map =
    xenium::harris_michael_hash_map<int, int,
        xenium::policy::reclaimer<
            xenium::reclamation::lock_free_ref_count<>
        >
    >;
main(){
    map m;
    m.get_or_emplace(1, 2);
    m.erase(1);
    assert(m.begin() == m.end());
}
% c++ -std=c++17 -I.. x.cc -ggdb3 -O0
% valgrind --leak-check=full a.out   
==2067304== Memcheck, a memory error detector
==2067304== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2067304== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==2067304== Command: a.out
==2067304== 
==2067304== 
==2067304== HEAP SUMMARY:
==2067304==     in use at exit: 40 bytes in 1 blocks
==2067304==   total heap usage: 2 allocs, 1 frees, 72,744 bytes allocated
==2067304== 
==2067304== 40 bytes in 1 blocks are possibly lost in loss record 1 of 1
==2067304==    at 0x4836DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2067304==    by 0x109DFE: xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> >::enable_concurrent_ptr<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::node, 1ul, std::default_delete<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::node> >::operator new(unsigned long) (lock_free_ref_count.hpp:132)
==2067304==    by 0x1096F2: std::pair<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::iterator, bool> xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::get_or_emplace<int>(int, int&&)::{lambda(unsigned long, int)#1}::operator()(unsigned long, int) const (harris_michael_hash_map.hpp:583)
==2067304==    by 0x10A131: std::pair<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::iterator, bool> xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::do_get_or_emplace_lazy<std::pair<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::iterator, bool> xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::get_or_emplace<int>(int, int&&)::{lambda(unsigned long, int)#1}>(int, std::pair<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::iterator, bool> xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::get_or_emplace<int>(int, int&&)::{lambda(unsigned long, int)#1}) (harris_michael_hash_map.hpp:619)
==2067304==    by 0x109776: std::pair<xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::iterator, bool> xenium::harris_michael_hash_map<int, int, xenium::policy::reclaimer<xenium::reclamation::lock_free_ref_count<xenium::reclamation::lock_free_ref_count_traits<false, 0ul> > > >::get_or_emplace<int>(int, int&&) (harris_michael_hash_map.hpp:586)
==2067304==    by 0x109198: main (x.cc:11)
==2067304== 
==2067304== LEAK SUMMARY:
==2067304==    definitely lost: 0 bytes in 0 blocks
==2067304==    indirectly lost: 0 bytes in 0 blocks
==2067304==      possibly lost: 40 bytes in 1 blocks
==2067304==    still reachable: 0 bytes in 0 blocks
==2067304==         suppressed: 0 bytes in 0 blocks
==2067304== 
==2067304== For lists of detected and suppressed errors, rerun with: -s
==2067304== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

[mpoeter]

Lock-free reference counting cannot return the memory to the memory manager, instead the nodes are kept in a free-list and reused. So yes, these are false positives. I will update the documentation to clearly communicate this.

Just a side note: in many cases it is sub-optimal to use LFRC for the harris_michael_hash_map, since this map uses a linked list for each bucket. When iterating such a list with LFRC, the reference counter of each node has to be updated twice (increment/decrement), which can cause significant contention/overhead. Consider using a epoch_based variation or the quiescent_state_based reclaimer.

[tmpgnh]

Thanks for the tip. I'm currently experimenting with the various reclaimers (and actually got the same valgrind blah with all the others too).

[mpoeter]

Reclamation of the objects is delayed until it is safe. In case the thread terminates but cannot yet reclaim some objects, they are "abandoned" so some other thread can "adopt" and reclaim them. So all reclaimers (except LFRC) should eventuelly return all memory to the memory manager. Thanks for the Info - I will run some valgrind tests myself.

Let me know if you have any other questions!

[tmpgnh]

2020-02-06 18:35 időpontban Manuel Pöter ezt írta:

Reclamation of the objects is delayed until it is safe. In case the thread terminates but cannot yet reclaim some objects, they are "abandoned" so some other thread can "adopt" and reclaim them. So all reclaimers (except LFRC) should eventuelly return all memory to the memory manager. Thanks for the Info - I will run some valgrind tests myself.

Let me know if you have any other questions!

Hi, Thanks for the explanation. Do I get it right that in a Harris-Michael map the number of buckets never changes, an therefore an iterator started with begin() will visit every element already present in the map at time of begin(), even in face of any combination of adding and deleting elements during the iteration (i.e., in an other thread)? Thanks, G.

[mpoeter]

Yes, the Harris-Michael hashmap has a fixed number of buckets, but that does not mean that an iterator will visit each element present at the time begin() is called. Iterators do not operate on a snapshot.

Suppose thread 1 starts to iterate the map; at that time some item X is present in the map. Before the thread 1's iterator visits X, thread 2 marks X as deleted. It could be that thread 2 already fully removed X from its bucket before thread 1 would reach it - in this case thread 1 would never know that X was in the map at some point. However, it could also be that thread 1 reaches X before it is fully removed. In this case, thread 1 would help to fully remove X. So even though thread 1 would logically visit X, it would be implicitly removed and the iterator would move on to the next entry.

[tmpgnh]

2020-03-24 15:03 időpontban Manuel Pöter ezt írta:

Yes, the Harris-Michael hashmap has a fixed number of buckets, but that does not mean that an iterator will visit each element present at the time begin() is called. Iterators do not operate on a snapshot.

Yes thank you for pointing this out. Actually, now that I think of it, for my use case a less strict guarantee would be sufficient. Namely, that thread 1 is guaranteed to not skip any item Y that was present in the map at begin() time and which no other thread did remove during the iteration. (So basically I don't care about not visiting X in your example, only about visiting all those that thread 2 left in the map.) Do you think it is true for HM (or at least your implementation)?

[mpoeter]

Yes, this is guaranteed. Think of it this way - begin() gives you a reference to the first item. Incrementing the iterator moves it to the next item. This item either was already present in the map when the iterator was first created (and has not been marked for removal since then), or it has been inserted in the meantime. Either way, it is guaranteed that all remaining items are visited, i.e., no items that have not been marked for removal are skipped.