[lxc-devel] [PATCH 3/3] lxc-ls: tweak algorithm for ls_has_all_grps()
Christian Brauner
christian.brauner at mailbox.org
Thu Jan 28 11:21:30 UTC 2016
- 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>
---
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
More information about the lxc-devel
mailing list