caetanosauer
commented
8 years ago Below is what I think is causing the bug -- will attempt fix later.
In order to join a CArray slot at log insertion, the inserting thread must first find an available slot at random. This search, together with all slot management functions, is performed without concurrency control under the assumption that all races are resolved with atomic operations on the slot values themselves. However, the following race condition has been overlooked.
Finding a random slot for joining happens in a nested loop (method ConsolidationArray::join_slot), where the outer loop grabs an available slot (counter >= 0) and the inner loop attempts to increment the counter and fetch the old value with a CAS. If the inner loop fails on the CAS, two outcomes are possible:
(1) the new value is negative, which means slot is not available anymore -- break to outer loop to find a new slot; or (2) the new value is still positive, which means the slot is still available but another thread incremented before us -- continue in the inner loop
In case 2 above, it may happen that the slot is available but it has actually gone through a whole grab-release cycle, so that despite the slot being valid, the index on the slot array has changed. This is similar to the classical ABA problem. The bug happens because we return the index to the caller, which uses it in replace_active_slot instead of the pointer to the slot.
Possible solutions I can think of are:
- Break to the outer loop in case 2 above
- Do not rely on the index value and use the slot pointer exclusively
- Update the index when case 2 happens -- although that may still leave some unpredicted bug.
Following assertion fails under high contention:
(In method ConsolidationArray::replace_active_slot) assertion failure: _active_slots[active_index]->vthis()->count > SLOT_AVAILABLE
[I've encountered this bug a long time ago -- adding issue now because I'm about to fix it and I would like to document it]