[1/5] sysctl: faster reimplementation of sysctl_check_table

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).

Signed-off-by: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
---
 kernel/sysctl_check.c |  121 ++++++++++++++++++++++++-------------------------
 1 files changed, 60 insertions(+), 61 deletions(-)

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);
> +}
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html