Deadlock when using Iterator

[AdrianEddy]

I found out that this example deadlocks in insert():

uint32_t random(uint32_t min, uint32_t max) {
    return min + (((double) rand() / (double(RAND_MAX) + 1)) * (max - min));
}
int main() {
    struct Data {
        Data(uint64_t id) : Id(id) { }
        uint64_t Id;
    };

    junction::ConcurrentMap_Leapfrog<uint64_t, Data *> map;
    std::mutex mut;

    std::vector<std::thread> threads;
    for (int i = 0; i < 16; ++i) {
        threads.push_back(std::thread([&] {
            auto qsbrCtx = junction::DefaultQSBR.createContext();
            while (true) {
                auto type = random(0, 5);
                switch (type) {
                    case 0: {
                        auto item = new Data(random(0, 1000));
                        std::lock_guard<std::mutex> lock(mut);
                        map.assign(item->Id, item);
                    } break;
                    case 1: {
                        if (auto *item = map.get(random(0, 1000))) {
                            // std::lock_guard<std::mutex> lock(mut);
                            map.erase(item->Id);
                        }
                    } break;
                    case 2: {
                        std::lock_guard<std::mutex> lock(mut);
                        junction::ConcurrentMap_Leapfrog<uint64_t, Data *>::Iterator it(map);
                        while (it.isValid()) {
                            if (it.getValue()->Id < 2) putchar('a');
                            it.next();
                        }
                    } break;
                    default: {
                        if (random(0, 10000) < 2)
                            printf("Thread %lx is running\n", std::hash<std::thread::id>()(std::this_thread::get_id()));  
                    } break;
                }
                junction::DefaultQSBR.update(qsbrCtx);
            }
        }));
    }
    threads.push_back(std::thread([&] {
        auto qsbrCtx = junction::DefaultQSBR.createContext();
        auto j = 0u;
        while (j++ < 10000000u) {
            if (auto *item = map.get(random(0, 1000))) {
                if (item->Id > 998) {
                    putchar('b');
                }
            }
            junction::DefaultQSBR.update(qsbrCtx);
        }
    }));
    for (auto &t : threads) {
        t.join();
    }

    return 0;
}

After running this deadlocks in junction/details/Leapfrog.h:235:

do {
    probeHash = cell->hash.load(turf::Acquire);
} while (probeHash == KeyTraits::NullHash);

If I remove case 2: from the example, there is no deadlock, so it appears that the iterator is causing some race condition. I used mutex on insert and iterator since comment for Iterator says

// The easiest way to implement an Iterator is to prevent all Redirects.
// The currrent Iterator does that by forbidding concurrent inserts.

In my case I insert and erase values very frequently from different threads, but occasionally I need to be able to iterate through all items (and inserts and erases may happen and that time too, hence the mutex).

Could you investigate and see if this is a bug in Junction or my mistake?

I'm attaching my complete example with makefile: junction-deadlock.zip

[preshing]

I haven't checked your example, but what happens if you enable the lock around erase()? Does the deadlock go away?

[AdrianEddy]

If I enable the lock around erase, the deadlock is still there. It doesn't happen every time but it happens sometimes (usually within a few seconds). Please play with the example (the attached project is ready to build, just run make), there's something wrong there and it deadlocks in multiple configurations. In my real-world application it was locking after few hours of heavy work in 8 threads and the problem went away when I replaced junction with another concurrent hash map

[preshing]

Hi Adrian,

The problem is that you are manipulating entries using the Null key (0). Looks like I didn't mention this important detail in the README, only the blog post. If you build and run your sample with TURF_WITH_ASSERTS=1 (as the CMake-based projects do in the Debug/RelWithAsserts configurations) you will hit an assert pointing this out.

When I change random(0, 1000) to random(1, 1000) in your code (to avoid using the Null key), the deadlock goes away on my machine.

Thanks for raising the possible issue nonetheless. Given that you are forced to use a mutex due to Junction's current restriction on using iterators, I'd actually suggest sticking with another concurrent map that doesn't have that restriction!