lkml.org 
[lkml]   [2011]   [Feb]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [PATCH 1/5] sysctl: faster reimplementation of sysctl_check_table
    Lucian Adrian Grijincu <lucian.grijincu@gmail.com> writes:

    > Determining the parent of a node at depth d
    > - previous implementation: O(d)
    > - current implementation: O(1)
    >
    > Printing the path to a node at depth d
    > - previous implementation: O(d^2)
    > - current implementation: O(d)
    >
    > This comes to a cost: we use an array ('parents') holding as many
    > pointers as there can be sysctl levels (currently CTL_MAXNAME=10).
    >
    > The 'parents' array of pointers holds the same values as the
    > ctl_table->parents field because the function that updates ->parents
    > (sysctl_set_parent) is called with either NULL (for root nodes) or
    > with sysctl_set_parent(table, table->child).

    Overall this looks reasonable.

    Can you include a check for going down too deeply, and overflowing your
    array. Otherwise I expect overflowing the array will be a nasty failure
    mode that will be hard to discover.

    Eric



    > Signed-off-by: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
    > ---
    > kernel/sysctl_check.c | 121 ++++++++++++++++++++++++-------------------------
    > 1 files changed, 60 insertions(+), 61 deletions(-)
    >
    > diff --git a/kernel/sysctl_check.c b/kernel/sysctl_check.c
    > index 10b90d8..9b4fecd 100644
    > --- a/kernel/sysctl_check.c
    > +++ b/kernel/sysctl_check.c
    > @@ -6,58 +6,34 @@
    > #include <net/ip_vs.h>
    >
    >
    > -static int sysctl_depth(struct ctl_table *table)
    > -{
    > - struct ctl_table *tmp;
    > - int depth;
    > -
    > - depth = 0;
    > - for (tmp = table; tmp->parent; tmp = tmp->parent)
    > - depth++;
    > -
    > - return depth;
    > -}
    > -
    > -static struct ctl_table *sysctl_parent(struct ctl_table *table, int n)
    > +static void sysctl_print_path(struct ctl_table *table,
    > + struct ctl_table **parents, int depth)
    > {
    > + struct ctl_table *p;
    > int i;
    > -
    > - for (i = 0; table && i < n; i++)
    > - table = table->parent;
    > -
    > - return table;
    > -}
    > -
    > -
    > -static void sysctl_print_path(struct ctl_table *table)
    > -{
    > - struct ctl_table *tmp;
    > - int depth, i;
    > - depth = sysctl_depth(table);
    > if (table->procname) {
    > - for (i = depth; i >= 0; i--) {
    > - tmp = sysctl_parent(table, i);
    > - printk("/%s", tmp->procname?tmp->procname:"");
    > + for (i = 0; i < depth; i++) {
    > + p = parents[i];
    > + printk("/%s", p->procname ? p->procname : "");
    > }
    > + printk("/%s", table->procname);
    > }
    > printk(" ");
    > }
    >
    > static struct ctl_table *sysctl_check_lookup(struct nsproxy *namespaces,
    > - struct ctl_table *table)
    > + struct ctl_table *table, struct ctl_table **parents, int depth)
    > {
    > struct ctl_table_header *head;
    > struct ctl_table *ref, *test;
    > - int depth, cur_depth;
    > -
    > - depth = sysctl_depth(table);
    > + int cur_depth;
    >
    > for (head = __sysctl_head_next(namespaces, NULL); head;
    > head = __sysctl_head_next(namespaces, head)) {
    > cur_depth = depth;
    > ref = head->ctl_table;
    > repeat:
    > - test = sysctl_parent(table, cur_depth);
    > + test = parents[depth - cur_depth];
    > for (; ref->procname; ref++) {
    > int match = 0;
    > if (cur_depth && !ref->child)
    > @@ -83,11 +59,12 @@ out:
    > return ref;
    > }
    >
    > -static void set_fail(const char **fail, struct ctl_table *table, const char *str)
    > +static void set_fail(const char **fail, struct ctl_table *table,
    > + const char *str, struct ctl_table **parents, int depth)
    > {
    > if (*fail) {
    > printk(KERN_ERR "sysctl table check failed: ");
    > - sysctl_print_path(table);
    > + sysctl_print_path(table, parents, depth);
    > printk(" %s\n", *fail);
    > dump_stack();
    > }
    > @@ -95,16 +72,24 @@ static void set_fail(const char **fail, struct ctl_table *table, const char *str
    > }
    >
    > static void sysctl_check_leaf(struct nsproxy *namespaces,
    > - struct ctl_table *table, const char **fail)
    > + struct ctl_table *table, const char **fail,
    > + struct ctl_table **parents, int depth)
    > {
    > struct ctl_table *ref;
    >
    > - ref = sysctl_check_lookup(namespaces, table);
    > - if (ref && (ref != table))
    > - set_fail(fail, table, "Sysctl already exists");
    > + ref = sysctl_check_lookup(namespaces, table, parents, depth);
    > + if (ref && (ref != table)) {
    > + printk(KERN_ALERT "sysctl_check_leaf ref[%s], table[%s]\n", ref->procname, table->procname);
    > + set_fail(fail, table, "Sysctl already exists", parents, depth);
    > + }
    > }
    >
    > -int sysctl_check_table(struct nsproxy *namespaces, struct ctl_table *table)
    > +
    > +
    > +#define SET_FAIL(str) set_fail(&fail, table, str, parents, depth)
    > +
    > +static int __sysctl_check_table(struct nsproxy *namespaces,
    > + struct ctl_table *table, struct ctl_table **parents, int depth)
    > {
    > int error = 0;
    > for (; table->procname; table++) {
    > @@ -112,23 +97,23 @@ int sysctl_check_table(struct nsproxy *namespaces, struct ctl_table *table)
    >
    > if (table->parent) {
    > if (table->procname && !table->parent->procname)
    > - set_fail(&fail, table, "Parent without procname");
    > + SET_FAIL("Parent without procname");
    > }
    > if (!table->procname)
    > - set_fail(&fail, table, "No procname");
    > + SET_FAIL("No procname");
    > if (table->child) {
    > if (table->data)
    > - set_fail(&fail, table, "Directory with data?");
    > + SET_FAIL("Directory with data?");
    > if (table->maxlen)
    > - set_fail(&fail, table, "Directory with maxlen?");
    > + SET_FAIL("Directory with maxlen?");
    > if ((table->mode & (S_IRUGO|S_IXUGO)) != table->mode)
    > - set_fail(&fail, table, "Writable sysctl directory");
    > + SET_FAIL("Writable sysctl directory");
    > if (table->proc_handler)
    > - set_fail(&fail, table, "Directory with proc_handler");
    > + SET_FAIL("Directory with proc_handler");
    > if (table->extra1)
    > - set_fail(&fail, table, "Directory with extra1");
    > + SET_FAIL("Directory with extra1");
    > if (table->extra2)
    > - set_fail(&fail, table, "Directory with extra2");
    > + SET_FAIL("Directory with extra2");
    > } else {
    > if ((table->proc_handler == proc_dostring) ||
    > (table->proc_handler == proc_dointvec) ||
    > @@ -139,28 +124,42 @@ int sysctl_check_table(struct nsproxy *namespaces, struct ctl_table *table)
    > (table->proc_handler == proc_doulongvec_minmax) ||
    > (table->proc_handler == proc_doulongvec_ms_jiffies_minmax)) {
    > if (!table->data)
    > - set_fail(&fail, table, "No data");
    > + SET_FAIL("No data");
    > if (!table->maxlen)
    > - set_fail(&fail, table, "No maxlen");
    > + SET_FAIL("No maxlen");
    > }
    > #ifdef CONFIG_PROC_SYSCTL
    > if (table->procname && !table->proc_handler)
    > - set_fail(&fail, table, "No proc_handler");
    > -#endif
    > -#if 0
    > - if (!table->procname && table->proc_handler)
    > - set_fail(&fail, table, "proc_handler without procname");
    > + SET_FAIL("No proc_handler");
    > #endif
    > - sysctl_check_leaf(namespaces, table, &fail);
    > + parents[depth] = table;
    > + sysctl_check_leaf(namespaces, table, &fail,
    > + parents, depth);
    > }
    > if (table->mode > 0777)
    > - set_fail(&fail, table, "bogus .mode");
    > + SET_FAIL("bogus .mode");
    > if (fail) {
    > - set_fail(&fail, table, NULL);
    > + SET_FAIL(NULL);
    > error = -EINVAL;
    > }
    > - if (table->child)
    > - error |= sysctl_check_table(namespaces, table->child);
    > + if (table->child) {
    > + parents[depth] = table;
    > + error |= __sysctl_check_table(namespaces, table->child,
    > + parents, depth + 1);
    > + }
    > }
    > return error;
    > }
    > +
    > +
    > +int sysctl_check_table(struct nsproxy *namespaces, struct ctl_table *table)
    > +{
    > + struct ctl_table *parents[CTL_MAXNAME];
    > + /* Keep track of parents as we go down into the tree.
    > + *
    > + * parents[i-1] will be the parent for parents[i].
    > + * The node at depth 'd' will have the parent at parents[d-1].
    > + * The root node (depth=0) has no parent in this array.
    > + */
    > + return __sysctl_check_table(namespaces, table, parents, 0);
    > +}


    \
     
     \ /
      Last update: 2011-02-04 20:43    [W:0.051 / U:0.028 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site