libpmemobj-cpp icon indicating copy to clipboard operation
libpmemobj-cpp copied to clipboard

operator-- may fail in concurrent radix_tree

Open lukaszstolarczuk opened this issue 4 years ago • 1 comments

operator-- may fail (when MtMode is enabled) in some specific cases, e.g.:

  • try_decrement fails due to concurrent erase (it can be the element pointed to by the iterator)
  • operator-- calls lower_bound which returns end() (the tree is now empty)
  • try_decrement crashes because we decrement beyond begin()

ref. #1156

lukaszstolarczuk avatar Jul 15 '21 08:07 lukaszstolarczuk

There are two problems for this version: https://github.com/pmem/libpmemobj-cpp/commit/63009805933a643208af47624b3ec7be3d56b57e

  1. If iterator points to end() and try_decrement fails, we will call key() on nullptr (leaf_ == nullptr for end())
  2. Problem mentioned by lukaszstolarczuk is caused by a lack of special value for begin(). When we use operator++ and encounter end() we know it's time to stop. For operator-- be cannot rely on comparison with begin() since its value can change. We could introduce a special past-begin iterator for this purpose.

igchor avatar Jul 15 '21 09:07 igchor