From mboxrd@z Thu Jan 1 00:00:00 1970 From: NeilBrown Date: Mon, 11 Feb 2019 12:05:16 +1100 Subject: [lustre-devel] [PATCH 03/21] lustre: obdclass: use list_sort() to sort a list. In-Reply-To: References: <154949776249.10620.1215070753973826063.stgit@noble.brown> <154949781252.10620.13626213918115345779.stgit@noble.brown> Message-ID: <87ef8fgmnn.fsf@notabene.neil.brown.name> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: lustre-devel@lists.lustre.org 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 > >> Signed-off-by: NeilBrown >> --- >> 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 >> #include >> #include >> +#include >> #include >> #include >> #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 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 Reviewed-by: James Simmons Signed-off-by: NeilBrown --- 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 #include #include +#include #include #include #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: