On Fri, May 15, 2020 at 12:47:06PM +0000, Lai Jiangshan wrote: > lib/rbtree.c has ensured that there is not possible to > inadvertently cause (temporary) loops in the tree structure > as seen in program order of the modifier. But loop is still > possible to be seen in searcher due to CPU's reordering. > > for example: > modifier searcher > > left rotate at parent > parent->rb_right is node > search to parent > parent->rb_right is node > +->see node->rb_left changed > WRITE_ONCE(parent->rb_right, tmp);-+ | node->rb_left is parennt > no smp_wmb(), some arch can | | > reorder these two writes | | loop long between > WRITE_ONCE(node->rb_left, parent);-+-+ parent and node > | > +--->finally see > parent->rb_right > > The long loop won't stop until the modifer's CPU flushes > its writes. Too avoid it, we should limit the searching depth.
Cute, have you actually observed this? Did you have performance issues? > There are no more than (1<<BITS_PER_LONG)-1 nodes in the tree. > And the max_depth of a tree is no more than 2*lg(node_count+1), > which is no mare than 2*BITS_PER_LONG. > > So the serarch should stop when diving down up to > 2*BITS_PER_LONG depth. Arguably you can have a larger key space, but I think due to memory constraints this limit still isn't wrong. But I do feel you need a comment with that.
