1 files changed, 54 insertions, 29 deletions

diff --git a/drivers/md/persistent-data/dm-transaction-manager.c b/drivers/md/persistent-data/dm-transaction-manager.c
index 16643fc974e8..98c745d90f48 100644
--- a/drivers/md/persistent-data/dm-transaction-manager.c
+++ b/drivers/md/persistent-data/dm-transaction-manager.c
@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0-only
 /*
  * Copyright (C) 2011 Red Hat, Inc.
  *
@@ -12,6 +13,7 @@
 #include <linux/export.h>
 #include <linux/mutex.h>
 #include <linux/hash.h>
+#include <linux/rbtree.h>
 #include <linux/slab.h>
 #include <linux/device-mapper.h>
 
@@ -28,14 +30,15 @@ struct prefetch_set {
 	dm_block_t blocks[PREFETCH_SIZE];
 };
 
-static unsigned prefetch_hash(dm_block_t b)
+static unsigned int prefetch_hash(dm_block_t b)
 {
 	return hash_64(b, PREFETCH_BITS);
 }
 
 static void prefetch_wipe(struct prefetch_set *p)
 {
-	unsigned i;
+	unsigned int i;
+
 	for (i = 0; i < PREFETCH_SIZE; i++)
 		p->blocks[i] = PREFETCH_SENTINEL;
 }
@@ -48,7 +51,7 @@ static void prefetch_init(struct prefetch_set *p)
 
 static void prefetch_add(struct prefetch_set *p, dm_block_t b)
 {
-	unsigned h = prefetch_hash(b);
+	unsigned int h = prefetch_hash(b);
 
 	mutex_lock(&p->lock);
 	if (p->blocks[h] == PREFETCH_SENTINEL)
@@ -59,7 +62,7 @@ static void prefetch_add(struct prefetch_set *p, dm_block_t b)
 
 static void prefetch_issue(struct prefetch_set *p, struct dm_block_manager *bm)
 {
-	unsigned i;
+	unsigned int i;
 
 	mutex_lock(&p->lock);
 
@@ -75,7 +78,7 @@ static void prefetch_issue(struct prefetch_set *p, struct dm_block_manager *bm)
 /*----------------------------------------------------------------*/
 
 struct shadow_info {
-	struct hlist_node hlist;
+	struct rb_node node;
 	dm_block_t where;
 };
 
@@ -93,7 +96,7 @@ struct dm_transaction_manager {
 	struct dm_space_map *sm;
 
 	spinlock_t lock;
-	struct hlist_head buckets[DM_HASH_SIZE];
+	struct rb_root buckets[DM_HASH_SIZE];
 
 	struct prefetch_set prefetches;
 };
@@ -103,15 +106,23 @@ struct dm_transaction_manager {
 static int is_shadow(struct dm_transaction_manager *tm, dm_block_t b)
 {
 	int r = 0;
-	unsigned bucket = dm_hash_block(b, DM_HASH_MASK);
-	struct shadow_info *si;
+	unsigned int bucket = dm_hash_block(b, DM_HASH_MASK);
+	struct rb_node **node;
 
 	spin_lock(&tm->lock);
-	hlist_for_each_entry(si, tm->buckets + bucket, hlist)
-		if (si->where == b) {
+	node = &tm->buckets[bucket].rb_node;
+	while (*node) {
+		struct shadow_info *si =
+			rb_entry(*node, struct shadow_info, node);
+		if (b == si->where) {
 			r = 1;
 			break;
 		}
+		if (b < si->where)
+			node = &si->node.rb_left;
+		else
+			node = &si->node.rb_right;
+	}
 	spin_unlock(&tm->lock);
 
 	return r;
@@ -123,35 +134,46 @@ static int is_shadow(struct dm_transaction_manager *tm, dm_block_t b)
  */
 static void insert_shadow(struct dm_transaction_manager *tm, dm_block_t b)
 {
-	unsigned bucket;
+	unsigned int bucket;
 	struct shadow_info *si;
 
 	si = kmalloc(sizeof(*si), GFP_NOIO);
 	if (si) {
+		struct rb_node **node, *parent;
 		si->where = b;
 		bucket = dm_hash_block(b, DM_HASH_MASK);
+
 		spin_lock(&tm->lock);
-		hlist_add_head(&si->hlist, tm->buckets + bucket);
+		node = &tm->buckets[bucket].rb_node;
+		parent = NULL;
+		while (*node) {
+			struct shadow_info *si =
+				rb_entry(*node, struct shadow_info, node);
+			parent = *node;
+			if (b < si->where)
+				node = &si->node.rb_left;
+			else
+				node = &si->node.rb_right;
+		}
+		rb_link_node(&si->node, parent, node);
+		rb_insert_color(&si->node, &tm->buckets[bucket]);
 		spin_unlock(&tm->lock);
 	}
 }
 
 static void wipe_shadow_table(struct dm_transaction_manager *tm)
 {
-	struct shadow_info *si;
-	struct hlist_node *tmp;
-	struct hlist_head *bucket;
-	int i;
+	unsigned int i;
 
 	spin_lock(&tm->lock);
 	for (i = 0; i < DM_HASH_SIZE; i++) {
-		bucket = tm->buckets + i;
-		hlist_for_each_entry_safe(si, tmp, bucket, hlist)
+		while (!RB_EMPTY_ROOT(&tm->buckets[i])) {
+			struct shadow_info *si =
+				rb_entry(tm->buckets[i].rb_node, struct shadow_info, node);
+			rb_erase(&si->node, &tm->buckets[i]);
 			kfree(si);
-
-		INIT_HLIST_HEAD(bucket);
+		}
 	}
-
 	spin_unlock(&tm->lock);
 }
 
@@ -160,7 +182,7 @@ static void wipe_shadow_table(struct dm_transaction_manager *tm)
 static struct dm_transaction_manager *dm_tm_create(struct dm_block_manager *bm,
 						   struct dm_space_map *sm)
 {
-	int i;
+	unsigned int i;
 	struct dm_transaction_manager *tm;
 
 	tm = kmalloc(sizeof(*tm), GFP_KERNEL);
@@ -174,7 +196,7 @@ static struct dm_transaction_manager *dm_tm_create(struct dm_block_manager *bm,
 
 	spin_lock_init(&tm->lock);
 	for (i = 0; i < DM_HASH_SIZE; i++)
-		INIT_HLIST_HEAD(tm->buckets + i);
+		tm->buckets[i] = RB_ROOT;
 
 	prefetch_init(&tm->prefetches);
 
@@ -197,6 +219,9 @@ EXPORT_SYMBOL_GPL(dm_tm_create_non_blocking_clone);
 
 void dm_tm_destroy(struct dm_transaction_manager *tm)
 {
+	if (!tm)
+		return;
+
 	if (!tm->is_clone)
 		wipe_shadow_table(tm);
 
@@ -232,7 +257,7 @@ int dm_tm_commit(struct dm_transaction_manager *tm, struct dm_block *root)
 EXPORT_SYMBOL_GPL(dm_tm_commit);
 
 int dm_tm_new_block(struct dm_transaction_manager *tm,
-		    struct dm_block_validator *v,
+		    const struct dm_block_validator *v,
 		    struct dm_block **result)
 {
 	int r;
@@ -261,7 +286,7 @@ int dm_tm_new_block(struct dm_transaction_manager *tm,
 }
 
 static int __shadow_block(struct dm_transaction_manager *tm, dm_block_t orig,
-			  struct dm_block_validator *v,
+			  const struct dm_block_validator *v,
 			  struct dm_block **result)
 {
 	int r;
@@ -301,7 +326,7 @@ static int __shadow_block(struct dm_transaction_manager *tm, dm_block_t orig,
 }
 
 int dm_tm_shadow_block(struct dm_transaction_manager *tm, dm_block_t orig,
-		       struct dm_block_validator *v, struct dm_block **result,
+		       const struct dm_block_validator *v, struct dm_block **result,
 		       int *inc_children)
 {
 	int r;
@@ -326,7 +351,7 @@ int dm_tm_shadow_block(struct dm_transaction_manager *tm, dm_block_t orig,
 EXPORT_SYMBOL_GPL(dm_tm_shadow_block);
 
 int dm_tm_read_lock(struct dm_transaction_manager *tm, dm_block_t b,
-		    struct dm_block_validator *v,
+		    const struct dm_block_validator *v,
 		    struct dm_block **blk)
 {
 	if (tm->is_clone) {
@@ -393,11 +418,11 @@ void dm_tm_dec_range(struct dm_transaction_manager *tm, dm_block_t b, dm_block_t
 EXPORT_SYMBOL_GPL(dm_tm_dec_range);
 
 void dm_tm_with_runs(struct dm_transaction_manager *tm,
-		     const __le64 *value_le, unsigned count, dm_tm_run_fn fn)
+		     const __le64 *value_le, unsigned int count, dm_tm_run_fn fn)
 {
 	uint64_t b, begin, end;
 	bool in_run = false;
-	unsigned i;
+	unsigned int i;
 
 	for (i = 0; i < count; i++, value_le++) {
 		b = le64_to_cpu(*value_le);