[03/21] lustre: obdclass: use list_sort() to sort a list.
diff mbox series

Message ID 154949781252.10620.13626213918115345779.stgit@noble.brown
State New
Headers show
Series
  • lustre: Assorted cleanups for obdclass
Related show

Commit Message

NeilBrown Feb. 7, 2019, 12:03 a.m. UTC
Rather than a bespoke bubble-sort, use list_sort() to
sort this linked list.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 drivers/staging/lustre/lustre/obdclass/cl_io.c |   51 +++++-------------------
 1 file changed, 10 insertions(+), 41 deletions(-)

Comments

Andreas Dilger Feb. 8, 2019, 12:13 a.m. UTC | #1
On Feb 6, 2019, at 17:03, NeilBrown <neilb@suse.com> wrote:
> 
> Rather than a bespoke bubble-sort, use list_sort() to
> sort this linked list.
> 
> Signed-off-by: NeilBrown <neilb@suse.com>

Probably a performance win as well, since it looks like list_sort() uses merge sort
instead of bubble sort.

Reviewed-by: Andreas Dilger <adilger@whamcloud.com>

> ---
> drivers/staging/lustre/lustre/obdclass/cl_io.c |   51 +++++-------------------
> 1 file changed, 10 insertions(+), 41 deletions(-)
> 
> diff --git a/drivers/staging/lustre/lustre/obdclass/cl_io.c b/drivers/staging/lustre/lustre/obdclass/cl_io.c
> index beac7e8bc92a..7bf02350f19d 100644
> --- a/drivers/staging/lustre/lustre/obdclass/cl_io.c
> +++ b/drivers/staging/lustre/lustre/obdclass/cl_io.c
> @@ -42,6 +42,7 @@
> #include <obd_support.h>
> #include <lustre_fid.h>
> #include <linux/list.h>
> +#include <linux/list_sort.h>
> #include <linux/sched.h>
> #include <cl_object.h>
> #include "cl_internal.h"
> @@ -213,9 +214,15 @@ int cl_io_rw_init(const struct lu_env *env, struct cl_io *io,
> }
> EXPORT_SYMBOL(cl_io_rw_init);
> 
> -static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
> -			      const struct cl_lock_descr *d1)
> +static int cl_lock_descr_cmp(void *priv,
> +			     struct list_head *a, struct list_head *b)
> {
> +	const struct cl_io_lock_link *l0 = list_entry(a, struct cl_io_lock_link, cill_linkage);
> +	const struct cl_io_lock_link *l1 = list_entry(b, struct cl_io_lock_link, cill_linkage);
> +
> +	const struct cl_lock_descr *d0 = &l0->cill_descr;
> +	const struct cl_lock_descr *d1 = &l1->cill_descr;
> +
> 	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
> 			  lu_object_fid(&d1->cld_obj->co_lu));
> }
> @@ -225,45 +232,7 @@ static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
>  */
> static void cl_io_locks_sort(struct cl_io *io)
> {
> -	int done = 0;
> -
> -	/* hidden treasure: bubble sort for now. */
> -	do {
> -		struct cl_io_lock_link *curr;
> -		struct cl_io_lock_link *prev;
> -		struct cl_io_lock_link *temp;
> -
> -		done = 1;
> -		prev = NULL;
> -
> -		list_for_each_entry_safe(curr, temp,
> -					 &io->ci_lockset.cls_todo,
> -					 cill_linkage) {
> -			if (prev) {
> -				switch (cl_lock_descr_sort(&prev->cill_descr,
> -							   &curr->cill_descr)) {
> -				case 0:
> -					/*
> -					 * IMPOSSIBLE: Identical locks are
> -					 *	     already removed at
> -					 *	     this point.
> -					 */
> -				default:
> -					LBUG();
> -				case 1:
> -					list_move_tail(&curr->cill_linkage,
> -						       &prev->cill_linkage);
> -					done = 0;
> -					continue; /* don't change prev: it's
> -						   * still "previous"
> -						   */
> -				case -1: /* already in order */
> -					break;
> -				}
> -			}
> -			prev = curr;
> -		}
> -	} while (!done);
> +	list_sort(NULL, &io->ci_lockset.cls_todo, cl_lock_descr_cmp);
> }
> 
> static void cl_lock_descr_merge(struct cl_lock_descr *d0,
> 
> 

Cheers, Andreas
---
Andreas Dilger
Principal Lustre Architect
Whamcloud
James Simmons Feb. 11, 2019, 12:39 a.m. UTC | #2
> Rather than a bespoke bubble-sort, use list_sort() to
> sort this linked list.

Reviewed-by: James Simmons <jsimmons@infradead.org>
 
> Signed-off-by: NeilBrown <neilb@suse.com>
> ---
>  drivers/staging/lustre/lustre/obdclass/cl_io.c |   51 +++++-------------------
>  1 file changed, 10 insertions(+), 41 deletions(-)
> 
> diff --git a/drivers/staging/lustre/lustre/obdclass/cl_io.c b/drivers/staging/lustre/lustre/obdclass/cl_io.c
> index beac7e8bc92a..7bf02350f19d 100644
> --- a/drivers/staging/lustre/lustre/obdclass/cl_io.c
> +++ b/drivers/staging/lustre/lustre/obdclass/cl_io.c
> @@ -42,6 +42,7 @@
>  #include <obd_support.h>
>  #include <lustre_fid.h>
>  #include <linux/list.h>
> +#include <linux/list_sort.h>
>  #include <linux/sched.h>
>  #include <cl_object.h>
>  #include "cl_internal.h"
> @@ -213,9 +214,15 @@ int cl_io_rw_init(const struct lu_env *env, struct cl_io *io,
>  }
>  EXPORT_SYMBOL(cl_io_rw_init);
>  
> -static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
> -			      const struct cl_lock_descr *d1)
> +static int cl_lock_descr_cmp(void *priv,
> +			     struct list_head *a, struct list_head *b)
>  {
> +	const struct cl_io_lock_link *l0 = list_entry(a, struct cl_io_lock_link, cill_linkage);
> +	const struct cl_io_lock_link *l1 = list_entry(b, struct cl_io_lock_link, cill_linkage);
> +
> +	const struct cl_lock_descr *d0 = &l0->cill_descr;
> +	const struct cl_lock_descr *d1 = &l1->cill_descr;
> +
>  	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
>  			  lu_object_fid(&d1->cld_obj->co_lu));
>  }
> @@ -225,45 +232,7 @@ static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
>   */
>  static void cl_io_locks_sort(struct cl_io *io)
>  {
> -	int done = 0;
> -
> -	/* hidden treasure: bubble sort for now. */
> -	do {
> -		struct cl_io_lock_link *curr;
> -		struct cl_io_lock_link *prev;
> -		struct cl_io_lock_link *temp;
> -
> -		done = 1;
> -		prev = NULL;
> -
> -		list_for_each_entry_safe(curr, temp,
> -					 &io->ci_lockset.cls_todo,
> -					 cill_linkage) {
> -			if (prev) {
> -				switch (cl_lock_descr_sort(&prev->cill_descr,
> -							   &curr->cill_descr)) {
> -				case 0:
> -					/*
> -					 * IMPOSSIBLE: Identical locks are
> -					 *	     already removed at
> -					 *	     this point.
> -					 */
> -				default:
> -					LBUG();
> -				case 1:
> -					list_move_tail(&curr->cill_linkage,
> -						       &prev->cill_linkage);
> -					done = 0;
> -					continue; /* don't change prev: it's
> -						   * still "previous"
> -						   */
> -				case -1: /* already in order */
> -					break;
> -				}
> -			}
> -			prev = curr;
> -		}
> -	} while (!done);
> +	list_sort(NULL, &io->ci_lockset.cls_todo, cl_lock_descr_cmp);
>  }

While this fine cl_io_locks_sort() is discussed in one comment in 
cl_object.h and used once in cl_io.c. We could remove this one line
function completely and update the comment in cl_object.h.

>  static void cl_lock_descr_merge(struct cl_lock_descr *d0,
> 
> 
>
NeilBrown Feb. 11, 2019, 1:05 a.m. UTC | #3
On Mon, Feb 11 2019, James Simmons wrote:

>> Rather than a bespoke bubble-sort, use list_sort() to
>> sort this linked list.
>
> Reviewed-by: James Simmons <jsimmons@infradead.org>
>  
>> Signed-off-by: NeilBrown <neilb@suse.com>
>> ---
>>  drivers/staging/lustre/lustre/obdclass/cl_io.c |   51 +++++-------------------
>>  1 file changed, 10 insertions(+), 41 deletions(-)
>> 
>> diff --git a/drivers/staging/lustre/lustre/obdclass/cl_io.c b/drivers/staging/lustre/lustre/obdclass/cl_io.c
>> index beac7e8bc92a..7bf02350f19d 100644
>> --- a/drivers/staging/lustre/lustre/obdclass/cl_io.c
>> +++ b/drivers/staging/lustre/lustre/obdclass/cl_io.c
>> @@ -42,6 +42,7 @@
>>  #include <obd_support.h>
>>  #include <lustre_fid.h>
>>  #include <linux/list.h>
>> +#include <linux/list_sort.h>
>>  #include <linux/sched.h>
>>  #include <cl_object.h>
>>  #include "cl_internal.h"
>> @@ -213,9 +214,15 @@ int cl_io_rw_init(const struct lu_env *env, struct cl_io *io,
>>  }
>>  EXPORT_SYMBOL(cl_io_rw_init);
>>  
>> -static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
>> -			      const struct cl_lock_descr *d1)
>> +static int cl_lock_descr_cmp(void *priv,
>> +			     struct list_head *a, struct list_head *b)
>>  {
>> +	const struct cl_io_lock_link *l0 = list_entry(a, struct cl_io_lock_link, cill_linkage);
>> +	const struct cl_io_lock_link *l1 = list_entry(b, struct cl_io_lock_link, cill_linkage);
>> +
>> +	const struct cl_lock_descr *d0 = &l0->cill_descr;
>> +	const struct cl_lock_descr *d1 = &l1->cill_descr;
>> +
>>  	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
>>  			  lu_object_fid(&d1->cld_obj->co_lu));
>>  }
>> @@ -225,45 +232,7 @@ static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
>>   */
>>  static void cl_io_locks_sort(struct cl_io *io)
>>  {
>> -	int done = 0;
>> -
>> -	/* hidden treasure: bubble sort for now. */
>> -	do {
>> -		struct cl_io_lock_link *curr;
>> -		struct cl_io_lock_link *prev;
>> -		struct cl_io_lock_link *temp;
>> -
>> -		done = 1;
>> -		prev = NULL;
>> -
>> -		list_for_each_entry_safe(curr, temp,
>> -					 &io->ci_lockset.cls_todo,
>> -					 cill_linkage) {
>> -			if (prev) {
>> -				switch (cl_lock_descr_sort(&prev->cill_descr,
>> -							   &curr->cill_descr)) {
>> -				case 0:
>> -					/*
>> -					 * IMPOSSIBLE: Identical locks are
>> -					 *	     already removed at
>> -					 *	     this point.
>> -					 */
>> -				default:
>> -					LBUG();
>> -				case 1:
>> -					list_move_tail(&curr->cill_linkage,
>> -						       &prev->cill_linkage);
>> -					done = 0;
>> -					continue; /* don't change prev: it's
>> -						   * still "previous"
>> -						   */
>> -				case -1: /* already in order */
>> -					break;
>> -				}
>> -			}
>> -			prev = curr;
>> -		}
>> -	} while (!done);
>> +	list_sort(NULL, &io->ci_lockset.cls_todo, cl_lock_descr_cmp);
>>  }
>
> While this fine cl_io_locks_sort() is discussed in one comment in 
> cl_object.h and used once in cl_io.c. We could remove this one line
> function completely and update the comment in cl_object.h.
>

Excellent idea.  New patch is below.
Thanks,
NeilBrown

From: NeilBrown <neilb@suse.com>
Subject: [PATCH] lustre: obdclass: use list_sort() to sort a list.

Rather than a bespoke bubble-sort, use list_sort() to
sort this linked list.

As this would become a 1-line function that is only called once,
call list_sort() directly from the one call site.

Reviewed-by: Andreas Dilger <adilger@whamcloud.com>
Reviewed-by: James Simmons <jsimmons@infradead.org>
Signed-off-by: NeilBrown <neilb@suse.com>
---
 drivers/staging/lustre/lustre/obdclass/cl_io.c | 63 ++++++--------------------
 1 file changed, 14 insertions(+), 49 deletions(-)

diff --git a/drivers/staging/lustre/lustre/obdclass/cl_io.c b/drivers/staging/lustre/lustre/obdclass/cl_io.c
index 5191fba8bbc0..c8a99b61ecd2 100644
--- a/drivers/staging/lustre/lustre/obdclass/cl_io.c
+++ b/drivers/staging/lustre/lustre/obdclass/cl_io.c
@@ -42,6 +42,7 @@
 #include <obd_support.h>
 #include <lustre_fid.h>
 #include <linux/list.h>
+#include <linux/list_sort.h>
 #include <linux/sched.h>
 #include <cl_object.h>
 #include "cl_internal.h"
@@ -213,57 +214,17 @@ int cl_io_rw_init(const struct lu_env *env, struct cl_io *io,
 }
 EXPORT_SYMBOL(cl_io_rw_init);
 
-static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
-			      const struct cl_lock_descr *d1)
+static int cl_lock_descr_cmp(void *priv,
+			     struct list_head *a, struct list_head *b)
 {
-	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
-			  lu_object_fid(&d1->cld_obj->co_lu));
-}
+	const struct cl_io_lock_link *l0 = list_entry(a, struct cl_io_lock_link, cill_linkage);
+	const struct cl_io_lock_link *l1 = list_entry(b, struct cl_io_lock_link, cill_linkage);
 
-/*
- * Sort locks in lexicographical order of their (fid, start-offset) pairs.
- */
-static void cl_io_locks_sort(struct cl_io *io)
-{
-	int done = 0;
+	const struct cl_lock_descr *d0 = &l0->cill_descr;
+	const struct cl_lock_descr *d1 = &l1->cill_descr;
 
-	/* hidden treasure: bubble sort for now. */
-	do {
-		struct cl_io_lock_link *curr;
-		struct cl_io_lock_link *prev;
-		struct cl_io_lock_link *temp;
-
-		done = 1;
-		prev = NULL;
-
-		list_for_each_entry_safe(curr, temp,
-					 &io->ci_lockset.cls_todo,
-					 cill_linkage) {
-			if (prev) {
-				switch (cl_lock_descr_sort(&prev->cill_descr,
-							   &curr->cill_descr)) {
-				case 0:
-					/*
-					 * IMPOSSIBLE: Identical locks are
-					 *	     already removed at
-					 *	     this point.
-					 */
-				default:
-					LBUG();
-				case 1:
-					list_move_tail(&curr->cill_linkage,
-						       &prev->cill_linkage);
-					done = 0;
-					continue; /* don't change prev: it's
-						   * still "previous"
-						   */
-				case -1: /* already in order */
-					break;
-				}
-			}
-			prev = curr;
-		}
-	} while (!done);
+	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
+			  lu_object_fid(&d1->cld_obj->co_lu));
 }
 
 static void cl_lock_descr_merge(struct cl_lock_descr *d0,
@@ -347,7 +308,11 @@ int cl_io_lock(const struct lu_env *env, struct cl_io *io)
 	}
 
 	if (result == 0) {
-		cl_io_locks_sort(io);
+		/*
+		 * Sort locks in lexicographical order of their (fid,
+		 * start-offset) pairs to avoid deadlocks.
+		 */
+		list_sort(NULL, &io->ci_lockset.cls_todo, cl_lock_descr_cmp);
 		result = cl_lockset_lock(env, io, &io->ci_lockset);
 	}
 	if (result != 0)

Patch
diff mbox series

diff --git a/drivers/staging/lustre/lustre/obdclass/cl_io.c b/drivers/staging/lustre/lustre/obdclass/cl_io.c
index beac7e8bc92a..7bf02350f19d 100644
--- a/drivers/staging/lustre/lustre/obdclass/cl_io.c
+++ b/drivers/staging/lustre/lustre/obdclass/cl_io.c
@@ -42,6 +42,7 @@ 
 #include <obd_support.h>
 #include <lustre_fid.h>
 #include <linux/list.h>
+#include <linux/list_sort.h>
 #include <linux/sched.h>
 #include <cl_object.h>
 #include "cl_internal.h"
@@ -213,9 +214,15 @@  int cl_io_rw_init(const struct lu_env *env, struct cl_io *io,
 }
 EXPORT_SYMBOL(cl_io_rw_init);
 
-static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
-			      const struct cl_lock_descr *d1)
+static int cl_lock_descr_cmp(void *priv,
+			     struct list_head *a, struct list_head *b)
 {
+	const struct cl_io_lock_link *l0 = list_entry(a, struct cl_io_lock_link, cill_linkage);
+	const struct cl_io_lock_link *l1 = list_entry(b, struct cl_io_lock_link, cill_linkage);
+
+	const struct cl_lock_descr *d0 = &l0->cill_descr;
+	const struct cl_lock_descr *d1 = &l1->cill_descr;
+
 	return lu_fid_cmp(lu_object_fid(&d0->cld_obj->co_lu),
 			  lu_object_fid(&d1->cld_obj->co_lu));
 }
@@ -225,45 +232,7 @@  static int cl_lock_descr_sort(const struct cl_lock_descr *d0,
  */
 static void cl_io_locks_sort(struct cl_io *io)
 {
-	int done = 0;
-
-	/* hidden treasure: bubble sort for now. */
-	do {
-		struct cl_io_lock_link *curr;
-		struct cl_io_lock_link *prev;
-		struct cl_io_lock_link *temp;
-
-		done = 1;
-		prev = NULL;
-
-		list_for_each_entry_safe(curr, temp,
-					 &io->ci_lockset.cls_todo,
-					 cill_linkage) {
-			if (prev) {
-				switch (cl_lock_descr_sort(&prev->cill_descr,
-							   &curr->cill_descr)) {
-				case 0:
-					/*
-					 * IMPOSSIBLE: Identical locks are
-					 *	     already removed at
-					 *	     this point.
-					 */
-				default:
-					LBUG();
-				case 1:
-					list_move_tail(&curr->cill_linkage,
-						       &prev->cill_linkage);
-					done = 0;
-					continue; /* don't change prev: it's
-						   * still "previous"
-						   */
-				case -1: /* already in order */
-					break;
-				}
-			}
-			prev = curr;
-		}
-	} while (!done);
+	list_sort(NULL, &io->ci_lockset.cls_todo, cl_lock_descr_cmp);
 }
 
 static void cl_lock_descr_merge(struct cl_lock_descr *d0,