]> git.baikalelectronics.ru Git - kernel.git/commit
dm snapshot: improve performance by switching out_of_order_list to rbtree
authorDavid Jeffery <djeffery@redhat.com>
Tue, 7 Aug 2018 20:56:00 +0000 (16:56 -0400)
committerMike Snitzer <snitzer@redhat.com>
Wed, 8 Aug 2018 14:41:49 +0000 (10:41 -0400)
commitd2e8d05cc6caa2702b450de410315e12149eb476
treef88276f29b02ad50a15e72ffcf9c67e395262db0
parentad8607575b242bf2f239a5fef2adb32c3cc243a5
dm snapshot: improve performance by switching out_of_order_list to rbtree

copy_complete()'s processing of out_of_order_list can result in
quadratic complexity in the worst case.  As such it was the source of
consuming too much cpu and the source of significant loss in
performance.

Fix this by converting out_of_order_list to an rbtree.  This improved
a dm-snapshot test copy workload from 32 seconds to 4 seconds.

Signed-off-by: David Jeffery <djeffery@redhat.com>
Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
Tested-by: Brett Hull <bhull@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
drivers/md/dm-snap.c