Skip to content
Snippets Groups Projects
  • Konstantin Osipov's avatar
    52a25610
    A fix and a test case for Bug#1051006 · 52a25610
    Konstantin Osipov authored
    A fix and a test case for Bug#1051006
    "Tree iterators return garbage if an index is modified between calls"
    
    Mark in a deleted node in sptree.h that it's been  put into the
    garbage heap. When iterting over a garbage collected node, skip it,
    and go up the stack until we find the first valid node.
    
    This breaks the "sorted" quality of tree iterators in case there
    are modifications between invocations of an iterator:
    it is possible that a node is deleted and recycled, and we don't see
    it in the iterator. When we go up the stack, we can jump to a different
    part of the range than the one the recycled node belongs to.
    . With this fix, it is also possible, that the iteration goes more
    than once over entire tree range. But it's a good enough quick fix for a
    crashing expire loop, which uses the tree iterator over the primary key to
    scan the entire range and deletes expired keys on the go (additionally,
    deletions may occur between invocations of the expire loop).
    52a25610
    History
    A fix and a test case for Bug#1051006
    Konstantin Osipov authored
    A fix and a test case for Bug#1051006
    "Tree iterators return garbage if an index is modified between calls"
    
    Mark in a deleted node in sptree.h that it's been  put into the
    garbage heap. When iterting over a garbage collected node, skip it,
    and go up the stack until we find the first valid node.
    
    This breaks the "sorted" quality of tree iterators in case there
    are modifications between invocations of an iterator:
    it is possible that a node is deleted and recycled, and we don't see
    it in the iterator. When we go up the stack, we can jump to a different
    part of the range than the one the recycled node belongs to.
    . With this fix, it is also possible, that the iteration goes more
    than once over entire tree range. But it's a good enough quick fix for a
    crashing expire loop, which uses the tree iterator over the primary key to
    scan the entire range and deletes expired keys on the go (additionally,
    deletions may occur between invocations of the expire loop).