Bug 106631
| Summary: | rbtree_postorder_for_each_entry_safe() miss some nodes if call rb_erase() inside a loop | ||
|---|---|---|---|
| Product: | Other | Reporter: | Oleksandr Suvorov (cryosay) |
| Component: | Other | Assignee: | other_other |
| Status: | NEW --- | ||
| Severity: | normal | CC: | 4eppelin, cryosay |
| Priority: | P1 | Keywords: | trivial |
| Hardware: | All | ||
| OS: | Linux | ||
| Kernel Version: | >= 3.12 | Subsystem: | |
| Regression: | No | Bisected commit-id: | |
| Attachments: | A simple patch that adds correct "func", but w/o replacing an old one | ||
s/keys 8/8 keys/ :) |
Created attachment 191171 [details] A simple patch that adds correct "func", but w/o replacing an old one How to reproduce (minimum configuration to get partially-balanced sub-tree): 1. create an rbtree with keys 8 (0, 1, 2, 3, 4, 5, 6, 7) 2. run rbtree_postorder_for_each_entry_safe() and erase all even-key nodes inside loop. 3. rbtree_postorder_for_each_entry_safe() miss a node with key 5. I created a patch that adds a "func" rbtree_foreach_entry_safe() that really does what rbtree_postorder_for_each_entry_safe() should. This variant passed my tests and even test from lib/rbtree_test.c when I added some suddenly erase() inside test loop. May be there are some situations I don't know and simple rb_first/rb_next could cause troubles, but the fact the original algo of rbtree_postorder_for_each_entry_safe() has trouble too :)