Disclaimer
This ticket describes a theoretical scenario (currently not reproducible) that can occur with reverse tree iterators — its purpose is to serve as a reference.
Description
|
if (iterator_type_is_reverse(type)) { |
|
/* |
|
* Because of limitations of tree search API we use use |
|
* lower_bound for LT search and upper_bound for LE |
|
* and REQ searches. Thus we found position to the |
|
* right of the target one. Let's make a step to the |
|
* left to reach target position. |
|
* If we found an invalid iterator all the elements in |
|
* the tree are less (less or equal) to the key, and |
|
* iterator_next call will convert the iterator to the |
|
* last position in the tree, that's what we need. |
|
*/ |
|
memtx_tree_iterator_prev(tree, &it->tree_iterator); |
|
} |
|
|
|
if (!equals && (type == ITER_EQ || type == ITER_REQ)) { |
|
/* |
|
* Found nothing, iteration will be stopped now. That is the |
|
* last chance to record that the transaction have read the key. |
|
*/ |
|
if (key_is_full) { |
|
memtx_tx_track_point(txn, space, idx, it->key_data.key); |
|
return 0; |
|
} |
|
/* it->tree_iterator is positioned on successor of a key! */ |
|
struct memtx_tree_data<USE_HINT> *res = |
|
memtx_tree_iterator_get_elem(tree, &it->tree_iterator); |
|
struct tuple *successor = res == NULL ? NULL : res->tuple; |
|
memtx_tx_track_gap(txn, space, idx, successor, type, |
|
it->key_data.key, it->key_data.part_count); |
|
return 0; |
|
} |
|
|
|
struct memtx_tree_data<USE_HINT> *res = |
|
memtx_tree_iterator_get_elem(tree, &it->tree_iterator); |
Consider the following scenario for reverse type iterators.
Inside the call to memtx_track_gap, memtx_tx_story_gc gets invoked and garbage collects the res tuple's story: res becomes clean (i.e., res->is_dirty == true).
After that instead of getting NULL from memtx_tx_tuple_clarify and calling iterator->next_raw we will get the same tuple, as if it is in the primary index:
|
*ret = memtx_tx_tuple_clarify(txn, space, *ret, idx, mk_index); |
|
if (*ret == NULL) { |
|
return iterator->next_raw(iterator, ret); |
|
} else { |
|
tree_iterator_set_current_tuple(it, *ret); |
|
} |
|
return 0; |
Only reverse iterators are subject to this behaviour, as forward iterator do not require this extra shift:
|
if (iterator_type_is_reverse(type)) { |
|
/* |
|
* Because of limitations of tree search API we use use |
|
* lower_bound for LT search and upper_bound for LE |
|
* and REQ searches. Thus we found position to the |
|
* right of the target one. Let's make a step to the |
|
* left to reach target position. |
|
* If we found an invalid iterator all the elements in |
|
* the tree are less (less or equal) to the key, and |
|
* iterator_next call will convert the iterator to the |
|
* last position in the tree, that's what we need. |
|
*/ |
|
memtx_tree_iterator_prev(tree, &it->tree_iterator); |
|
} |
In the case of forward iterators the res tuple is equal to the successor tuple, which is used in tracking and hence cannot get garbage collected:
|
if ((!key_is_full || (type != ITER_EQ && type != ITER_REQ)) && |
|
memtx_tx_manager_use_mvcc_engine) { |
|
/* it->tree_iterator is positioned on successor of a key! */ |
|
struct tuple *successor = res == NULL ? NULL : res->tuple; |
|
|
|
/********MVCC TRANSACTION MANAGER STORY GARBAGE COLLECTION BOUND START*********/ |
|
memtx_tx_track_gap(in_txn(), space, idx, successor, type, |
|
it->key_data.key, it->key_data.part_count); |
|
/*********MVCC TRANSACTION MANAGER STORY GARBAGE COLLECTION BOUND END**********/ |
|
} |
Currently, because of