| Message ID | 154949781252.10620.13626213918115345779.stgit@noble.brown (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | lustre: Assorted cleanups for obdclass | expand |
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
> 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, > > >
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)
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,
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(-)