[lxc-devel] [PATCH] lxc-ls: tweak algorithm for ls_has_all_grps()
Stéphane Graber
stgraber at stgraber.org
Thu Jan 28 11:06:27 UTC 2016
On Wed, Jan 20, 2016 at 02:08:31PM +0100, Christian Brauner wrote:
> - With the -g/--groups argument the user can give a comma-separated list of
> groups MUST a container must have in order to be displayed. We receive
> this list as a single string. ls_has_all_grps() is called to check if a
> container has all the groups of MUST in its current list of groups HAS. I.e.
> we determine whether MUST ⊆ HAS and only then do we record the container.
> The original implementation was dumb in that it split the string MUST
> everytime it needed to check whether MUST ⊆ HAS for a given container. That's
> pointless work. Instead we split the string MUST only once in main() and pass
> it to ls_get() which passes it along to ls_has_all_grps().
> - Before doing any costly checking make sure that #MUST <= #HAS. If not bail
> immediately.
> - The linear search algorithm ls_has_all_grps() currently uses stays for now.
> Binary search et al. do not seem to make sense since sorting the array HAS
> for each container is probably too costly. Especially, since it seems
> unlikely that a users specifies 50+ or so groups on the command line a
> container must have to be displayed. If however there are a lot of use-cases
> where users have a lot of containers each with 50-100 groups and regularly use
> lxc-ls with -g/--groups to only show containers that have 50 specified groups
> among their 50-100 groups we can revisit this issue and implement e.g. binary
> search or a ternary search tree.
>
> Signed-off-by: Christian Brauner <christian.brauner at mailbox.org>
Hi,
This doesn't apply to git master right now, can you send a version which does?
Thanks!
> ---
> src/lxc/arguments.h | 3 +--
> src/lxc/lxc_ls.c | 69 ++++++++++++++++++++++++++++-------------------------
> 2 files changed, 38 insertions(+), 34 deletions(-)
>
> diff --git a/src/lxc/arguments.h b/src/lxc/arguments.h
> index 46fecbf..861437e 100644
> --- a/src/lxc/arguments.h
> +++ b/src/lxc/arguments.h
> @@ -100,7 +100,7 @@ struct lxc_arguments {
> int all;
> int ignore_auto;
> int list;
> - char *groups;
> + char *groups; /* also used by lxc-ls */
>
> /* lxc-snapshot and lxc-clone */
> enum task {
> @@ -122,7 +122,6 @@ struct lxc_arguments {
>
> /* lxc-ls */
> char *ls_fancy_format;
> - char *ls_groups;
> char *ls_filter;
> unsigned int ls_nesting; /* maximum allowed nesting level */
> bool ls_active;
> diff --git a/src/lxc/lxc_ls.c b/src/lxc/lxc_ls.c
> index 5bbff1e..b7034dc 100644
> --- a/src/lxc/lxc_ls.c
> +++ b/src/lxc/lxc_ls.c
> @@ -95,7 +95,8 @@ static void ls_free_arr(char **arr, size_t size);
> */
> static int ls_get(struct ls **m, size_t *size, const struct lxc_arguments *args,
> const char *basepath, const char *parent, unsigned int lvl,
> - char **lockpath, size_t len_lockpath);
> + char **lockpath, size_t len_lockpath, char **grps_must,
> + size_t grps_must_len);
> static char *ls_get_cgroup_item(struct lxc_container *c, const char *item);
> static char *ls_get_config_item(struct lxc_container *c, const char *item,
> bool running);
> @@ -103,6 +104,8 @@ static char *ls_get_groups(struct lxc_container *c, bool running);
> static char *ls_get_ips(struct lxc_container *c, const char *inet);
> struct wrapargs {
> const struct lxc_arguments *args;
> + char **grps_must;
> + size_t grps_must_len;
> int pipefd[2];
> size_t *size;
> const char *parent;
> @@ -122,7 +125,7 @@ static int ls_get_wrapper(void *wrap);
> static double ls_get_swap(struct lxc_container *c);
> static unsigned int ls_get_term_width(void);
> static char *ls_get_interface(struct lxc_container *c);
> -static bool ls_has_all_grps(const char *has, const char *must);
> +static bool ls_has_all_grps(const char *has, char **must, size_t must_len);
> static struct ls *ls_new(struct ls **ls, size_t *size);
> /*
> * Print user-specified fancy format.
> @@ -228,12 +231,19 @@ int main(int argc, char *argv[])
> .autostart_length = 9, /* AUTOSTART */
> };
>
> + char **grps = NULL;
> + size_t ngrps = 0;
> + if (my_args.groups) {
> + grps = lxc_string_split_and_trim(my_args.groups, ',');
> + ngrps = lxc_array_len((void **)grps);
> + }
> +
> struct ls *ls_arr = NULL;
> size_t ls_size = 0;
> /* &(char *){NULL} is no magic. It's just a compound literal which
> * avoids having a pointless variable in main() that serves no purpose
> * here. */
> - int status = ls_get(&ls_arr, &ls_size, &my_args, "", NULL, 0, &(char *){NULL}, 0);
> + int status = ls_get(&ls_arr, &ls_size, &my_args, "", NULL, 0, &(char *){NULL}, 0, grps, ngrps);
> if (!ls_arr && status == 0)
> /* We did not fail. There was just nothing to do. */
> exit(EXIT_SUCCESS);
> @@ -256,6 +266,7 @@ int main(int argc, char *argv[])
>
> out:
> ls_free(ls_arr, ls_size);
> + lxc_free_array((void **)grps, free);
>
> exit(ret);
> }
> @@ -308,7 +319,8 @@ static void ls_free_arr(char **arr, size_t size)
>
> static int ls_get(struct ls **m, size_t *size, const struct lxc_arguments *args,
> const char *basepath, const char *parent, unsigned int lvl,
> - char **lockpath, size_t len_lockpath)
> + char **lockpath, size_t len_lockpath, char **grps_must,
> + size_t grps_must_len)
> {
> /* As ls_get() is non-tail recursive we face the inherent danger of
> * blowing up the stack at some level of nesting. To have at least some
> @@ -397,7 +409,7 @@ static int ls_get(struct ls **m, size_t *size, const struct lxc_arguments *args,
> bool running = c->is_running(c);
>
> char *grp_tmp = ls_get_groups(c, running);
> - if (!ls_has_all_grps(grp_tmp, args->groups)) {
> + if (!ls_has_all_grps(grp_tmp, grps_must, grps_must_len)) {
> free(grp_tmp);
> goto put_and_next;
> }
> @@ -477,6 +489,8 @@ static int ls_get(struct ls **m, size_t *size, const struct lxc_arguments *args,
> /* Send in the parent for the next nesting level. */
> wargs.parent = l->name;
> wargs.args = args;
> + wargs.grps_must = grps_must;
> + wargs.grps_must_len = grps_must_len;
>
> pid_t out;
>
> @@ -528,7 +542,7 @@ static int ls_get(struct ls **m, size_t *size, const struct lxc_arguments *args,
> if (ls_remove_lock(path, name, lockpath, &len_lockpath, true) == -1)
> goto put_and_next;
>
> - ls_get(m, size, args, newpath, l->name, lvl + 1, lockpath, len_lockpath);
> + ls_get(m, size, args, newpath, l->name, lvl + 1, lockpath, len_lockpath, grps_must, grps_must_len);
> free(newpath);
>
> /* Remove the lock. No need to check for failure here. */
> @@ -672,8 +686,10 @@ static unsigned int ls_get_term_width(void)
> return ws.ws_col;
> }
>
> -static bool ls_has_all_grps(const char *has, const char *must)
> +static bool ls_has_all_grps(const char *has, char **must, size_t must_len)
> {
> + bool bret = false;
> +
> if (!has && must)
> return false;
> else if (!must)
> @@ -682,36 +698,25 @@ static bool ls_has_all_grps(const char *has, const char *must)
> char **tmp_has = lxc_string_split_and_trim(has, ',');
> size_t tmp_has_len = lxc_array_len((void **)tmp_has);
>
> - char **tmp_must = lxc_string_split_and_trim(must, ',');
> - size_t tmp_must_len = lxc_array_len((void **)tmp_must);
> -
> - if (tmp_must_len > tmp_has_len)
> - tmp_must_len = tmp_has_len = 0;
> + /* Don't do any unnecessary work. */
> + if (must_len > tmp_has_len)
> + goto out;
>
> - bool broke_out = false, ran_once = false;
> - char **s, **t;
> - /* Check if container has all relevant groups. */
> - for (s = tmp_must; (tmp_must_len > 0) && (tmp_has_len > 0) && s && *s; s++) {
> - if (broke_out)
> - broke_out = false;
> - else if (!broke_out && ran_once)
> - break;
> - for (t = tmp_has; t && *t; t++) {
> - ran_once = true;
> - if (strcmp(*s, *t) == 0) {
> - broke_out = true;
> + size_t i, j;
> + for (i = 0; i < must_len; i++) {
> + for (j = 0; j < tmp_has_len; j++)
> + if (strcmp(must[i], tmp_has[j]) == 0)
> break;
> - }
> - }
> + if (j == tmp_has_len)
> + break;
> }
> + if (i == must_len)
> + bret = true;
>
> +out:
> lxc_free_array((void **)tmp_has, free);
> - lxc_free_array((void **)tmp_must, free);
> -
> - if (!broke_out)
> - return false;
>
> - return true;
> + return bret;
> }
>
> static struct ls *ls_new(struct ls **ls, size_t *size)
> @@ -949,7 +954,7 @@ static int ls_get_wrapper(void *wrap)
> /* &(char *){NULL} is no magic. It's just a compound literal which
> * avoids having a pointless variable in main() that serves no purpose
> * here. */
> - ls_get(&m, &len, wargs->args, "", wargs->parent, wargs->nestlvl, &(char *){NULL}, 0);
> + ls_get(&m, &len, wargs->args, "", wargs->parent, wargs->nestlvl, &(char *){NULL}, 0, wargs->grps_must, wargs->grps_must_len);
> if (!m)
> goto out;
>
> --
> 2.7.0
>
> _______________________________________________
> lxc-devel mailing list
> lxc-devel at lists.linuxcontainers.org
> http://lists.linuxcontainers.org/listinfo/lxc-devel
--
Stéphane
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL: <http://lists.linuxcontainers.org/pipermail/lxc-devel/attachments/20160128/00e52c0e/attachment-0001.sig>
More information about the lxc-devel
mailing list