Bug 106631 - rbtree_postorder_for_each_entry_safe() miss some nodes if call rb_erase() inside a loop
Summary: rbtree_postorder_for_each_entry_safe() miss some nodes if call rb_erase() ins...
Status: NEW
Alias: None
Product: Other
Classification: Unclassified
Component: Other (show other bugs)
Hardware: All Linux
: P1 normal
Assignee: other_other
URL:
Keywords: trivial
Depends on:
Blocks:
 
Reported: 2015-10-26 20:42 UTC by Oleksandr Suvorov
Modified: 2015-10-27 10:09 UTC (History)
2 users (show)

See Also:
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 (792 bytes, patch)
2015-10-26 20:42 UTC, Oleksandr Suvorov 		Details | Diff
Add an attachment (proposed patch, testcase, etc.)

Description Oleksandr Suvorov 2015-10-26 20:42:23 UTC 
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 :)
Comment 1 Oleksandr Suvorov 2015-10-27 10:09:56 UTC 
s/keys 8/8 keys/ :)
Note You need to log in before you can comment on or make changes to this bug.