[lustre-devel] [PATCH 03/21] lustre: obdclass: use list_sort() to sort a list.
NeilBrown
neilb at suse.com
Sun Feb 10 17:05:16 PST 2019
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 at infradead.org>
>
>> Signed-off-by: NeilBrown <neilb at 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 at 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 at whamcloud.com>
Reviewed-by: James Simmons <jsimmons at infradead.org>
Signed-off-by: NeilBrown <neilb at 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)
--
2.14.0.rc0.dirty
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: not available
URL: <http://lists.lustre.org/pipermail/lustre-devel-lustre.org/attachments/20190211/b7a2ccca/attachment-0001.sig>
More information about the lustre-devel
mailing list