[PATCH] Fix recursion loop in mod_count_all_dependencies()

[PATCH] Fix recursion loop in mod_count_all_dependencies()

[matwey.kornilov]

>From 48d4d7ba1acbb5c0955f75c6bdda9cf0935240fd Mon Sep 17 00:00:00 2001
From: "Matwey V. Kornilov" <matwey.kornilov@gmail.com>
Date: Fri, 11 Apr 2014 19:43:18 +0400
Subject: [PATCH] Fix recursion loop in mod_count_all_dependencies() when
 subgraph has a cycle.

When cycle is detected in mod_count_all_dependencies, use total count of
modules as an upper bound of needed memory. Correct number of nodes is determined by
subsequent call of mod_fill_all_unique_dependencies().
---
 tools/depmod.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/tools/depmod.c b/tools/depmod.c
index 1aedaaf..c83dee1 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -1682,12 +1682,20 @@ static int depmod_load(struct depmod *depmod)
 	return 0;
 }
 
-static size_t mod_count_all_dependencies(const struct mod *mod)
+static size_t mod_count_all_dependencies(const struct mod *mod, size_t upper_bound)
 {
 	size_t i, count = 0;
+	/* cycle is detected */
+	if (mod->dep_loop)
+		return upper_bound;
+
 	for (i = 0; i < mod->deps.count; i++) {
 		const struct mod *d = mod->deps.array[i];
-		count += 1 + mod_count_all_dependencies(d);
+		const size_t child = mod_count_all_dependencies(d, upper_bound);
+		if(child == upper_bound)
+			return child;
+
+		count += 1 + child;
 	}
 	return count;
 }
@@ -1722,12 +1730,12 @@ static int mod_fill_all_unique_dependencies(const struct mod *mod, const struct
 	return err;
 }
 
-static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps)
+static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps, size_t count)
 {
 	const struct mod **deps;
 	size_t last = 0;
 
-	*n_deps = mod_count_all_dependencies(mod);
+	*n_deps = mod_count_all_dependencies(mod, count);
 	if (*n_deps == 0)
 		return NULL;
 
@@ -1771,7 +1779,7 @@ static int output_deps(struct depmod *depmod, FILE *out)
 		if (mod->deps.count == 0)
 			goto end;
 
-		deps = mod_get_all_sorted_dependencies(mod, &n_deps);
+		deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
 		if (deps == NULL) {
 			ERR("could not get all sorted dependencies of %s\n", p);
 			goto end;
@@ -1819,7 +1827,7 @@ static int output_deps_bin(struct depmod *depmod, FILE *out)
 			continue;
 		}
 
-		deps = mod_get_all_sorted_dependencies(mod, &n_deps);
+		deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
 		if (deps == NULL && n_deps > 0) {
 			ERR("could not get all sorted dependencies of %s\n", p);
 			continue;
-- 
1.8.1.4

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

Hi

On Fri, Apr 11, 2014 at 4:31 PM,  <matwey.kornilov@gmail.com> wrote:
> From 48d4d7ba1acbb5c0955f75c6bdda9cf0935240fd Mon Sep 17 00:00:00 2001
> From: "Matwey V. Kornilov" <matwey.kornilov@gmail.com>
> Date: Fri, 11 Apr 2014 19:43:18 +0400
> Subject: [PATCH] Fix recursion loop in mod_count_all_dependencies() when
>  subgraph has a cycle.
>
> When cycle is detected in mod_count_all_dependencies, use total count of
> modules as an upper bound of needed memory. Correct number of nodes is determined by
> subsequent call of mod_fill_all_unique_dependencies().

We should deal with this already in depmod_calculate_dependencies(),
otherwise I'd say it would be a bug there. How did you reproduce it?


Gustavo, could you take a look on the patch below?

--
Lucas De Marchi

> ---
>  tools/depmod.c | 20 ++++++++++++++------
>  1 file changed, 14 insertions(+), 6 deletions(-)
>
> diff --git a/tools/depmod.c b/tools/depmod.c
> index 1aedaaf..c83dee1 100644
> --- a/tools/depmod.c
> +++ b/tools/depmod.c
> @@ -1682,12 +1682,20 @@ static int depmod_load(struct depmod *depmod)
>         return 0;
>  }
>
> -static size_t mod_count_all_dependencies(const struct mod *mod)
> +static size_t mod_count_all_dependencies(const struct mod *mod, size_t upper_bound)
>  {
>         size_t i, count = 0;
> +       /* cycle is detected */
> +       if (mod->dep_loop)
> +               return upper_bound;
> +
>         for (i = 0; i < mod->deps.count; i++) {
>                 const struct mod *d = mod->deps.array[i];
> -               count += 1 + mod_count_all_dependencies(d);
> +               const size_t child = mod_count_all_dependencies(d, upper_bound);
> +               if(child == upper_bound)
> +                       return child;
> +
> +               count += 1 + child;
>         }
>         return count;
>  }
> @@ -1722,12 +1730,12 @@ static int mod_fill_all_unique_dependencies(const struct mod *mod, const struct
>         return err;
>  }
>
> -static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps)
> +static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps, size_t count)
>  {
>         const struct mod **deps;
>         size_t last = 0;
>
> -       *n_deps = mod_count_all_dependencies(mod);
> +       *n_deps = mod_count_all_dependencies(mod, count);
>         if (*n_deps == 0)
>                 return NULL;
>
> @@ -1771,7 +1779,7 @@ static int output_deps(struct depmod *depmod, FILE *out)
>                 if (mod->deps.count == 0)
>                         goto end;
>
> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
>                 if (deps == NULL) {
>                         ERR("could not get all sorted dependencies of %s\n", p);
>                         goto end;
> @@ -1819,7 +1827,7 @@ static int output_deps_bin(struct depmod *depmod, FILE *out)
>                         continue;
>                 }
>
> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
>                 if (deps == NULL && n_deps > 0) {
>                         ERR("could not get all sorted dependencies of %s\n", p);
>                         continue;
> --
> 1.8.1.4
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-modules" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Gustavo Sverzut Barbieri]

patch itself is okay, (one minor syntax issue with lack of space
between "if" and "(").

But I wonder why just fail if we find loops, are those valid? If not,
couldn't we fail earlier and ask people to fix it?

On Fri, Apr 25, 2014 at 12:46 AM, Lucas De Marchi
<lucas.de.marchi@gmail.com> wrote:
> Hi
>
> On Fri, Apr 11, 2014 at 4:31 PM,  <matwey.kornilov@gmail.com> wrote:
>> From 48d4d7ba1acbb5c0955f75c6bdda9cf0935240fd Mon Sep 17 00:00:00 2001
>> From: "Matwey V. Kornilov" <matwey.kornilov@gmail.com>
>> Date: Fri, 11 Apr 2014 19:43:18 +0400
>> Subject: [PATCH] Fix recursion loop in mod_count_all_dependencies() when
>>  subgraph has a cycle.
>>
>> When cycle is detected in mod_count_all_dependencies, use total count of
>> modules as an upper bound of needed memory. Correct number of nodes is determined by
>> subsequent call of mod_fill_all_unique_dependencies().
>
> We should deal with this already in depmod_calculate_dependencies(),
> otherwise I'd say it would be a bug there. How did you reproduce it?
>
>
> Gustavo, could you take a look on the patch below?
>
> --
> Lucas De Marchi
>
>> ---
>>  tools/depmod.c | 20 ++++++++++++++------
>>  1 file changed, 14 insertions(+), 6 deletions(-)
>>
>> diff --git a/tools/depmod.c b/tools/depmod.c
>> index 1aedaaf..c83dee1 100644
>> --- a/tools/depmod.c
>> +++ b/tools/depmod.c
>> @@ -1682,12 +1682,20 @@ static int depmod_load(struct depmod *depmod)
>>         return 0;
>>  }
>>
>> -static size_t mod_count_all_dependencies(const struct mod *mod)
>> +static size_t mod_count_all_dependencies(const struct mod *mod, size_t upper_bound)
>>  {
>>         size_t i, count = 0;
>> +       /* cycle is detected */
>> +       if (mod->dep_loop)
>> +               return upper_bound;
>> +
>>         for (i = 0; i < mod->deps.count; i++) {
>>                 const struct mod *d = mod->deps.array[i];
>> -               count += 1 + mod_count_all_dependencies(d);
>> +               const size_t child = mod_count_all_dependencies(d, upper_bound);
>> +               if(child == upper_bound)
>> +                       return child;
>> +
>> +               count += 1 + child;
>>         }
>>         return count;
>>  }
>> @@ -1722,12 +1730,12 @@ static int mod_fill_all_unique_dependencies(const struct mod *mod, const struct
>>         return err;
>>  }
>>
>> -static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps)
>> +static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod, size_t *n_deps, size_t count)
>>  {
>>         const struct mod **deps;
>>         size_t last = 0;
>>
>> -       *n_deps = mod_count_all_dependencies(mod);
>> +       *n_deps = mod_count_all_dependencies(mod, count);
>>         if (*n_deps == 0)
>>                 return NULL;
>>
>> @@ -1771,7 +1779,7 @@ static int output_deps(struct depmod *depmod, FILE *out)
>>                 if (mod->deps.count == 0)
>>                         goto end;
>>
>> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
>> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
>>                 if (deps == NULL) {
>>                         ERR("could not get all sorted dependencies of %s\n", p);
>>                         goto end;
>> @@ -1819,7 +1827,7 @@ static int output_deps_bin(struct depmod *depmod, FILE *out)
>>                         continue;
>>                 }
>>
>> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
>> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps, depmod->modules.count);
>>                 if (deps == NULL && n_deps > 0) {
>>                         ERR("could not get all sorted dependencies of %s\n", p);
>>                         continue;
>> --
>> 1.8.1.4
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-modules" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Gustavo Sverzut Barbieri
--------------------------------------
Mobile: +55 (19) 99225-2202
Contact: http://www.gustavobarbieri.com.br/contact

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Matwey V. Kornilov]

[-- Attachment #1: Type: text/plain, Size: 4850 bytes --]

Can't answer the question. Looking the code, mod_count_all_dependencies has
to be fixed in that way. The code, running before and after, is
loop-tolerant.

However, I am not sure whether loops make sense. Can we load whole the loop
at once?
27.04.2014 19:30 пользователь "Gustavo Sverzut Barbieri" <barbieri@gmail.com>
написал:

> patch itself is okay, (one minor syntax issue with lack of space
> between "if" and "(").
>
> But I wonder why just fail if we find loops, are those valid? If not,
> couldn't we fail earlier and ask people to fix it?
>
> On Fri, Apr 25, 2014 at 12:46 AM, Lucas De Marchi
> <lucas.de.marchi@gmail.com> wrote:
> > Hi
> >
> > On Fri, Apr 11, 2014 at 4:31 PM,  <matwey.kornilov@gmail.com> wrote:
> >> From 48d4d7ba1acbb5c0955f75c6bdda9cf0935240fd Mon Sep 17 00:00:00 2001
> >> From: "Matwey V. Kornilov" <matwey.kornilov@gmail.com>
> >> Date: Fri, 11 Apr 2014 19:43:18 +0400
> >> Subject: [PATCH] Fix recursion loop in mod_count_all_dependencies() when
> >>  subgraph has a cycle.
> >>
> >> When cycle is detected in mod_count_all_dependencies, use total count of
> >> modules as an upper bound of needed memory. Correct number of nodes is
> determined by
> >> subsequent call of mod_fill_all_unique_dependencies().
> >
> > We should deal with this already in depmod_calculate_dependencies(),
> > otherwise I'd say it would be a bug there. How did you reproduce it?
> >
> >
> > Gustavo, could you take a look on the patch below?
> >
> > --
> > Lucas De Marchi
> >
> >> ---
> >>  tools/depmod.c | 20 ++++++++++++++------
> >>  1 file changed, 14 insertions(+), 6 deletions(-)
> >>
> >> diff --git a/tools/depmod.c b/tools/depmod.c
> >> index 1aedaaf..c83dee1 100644
> >> --- a/tools/depmod.c
> >> +++ b/tools/depmod.c
> >> @@ -1682,12 +1682,20 @@ static int depmod_load(struct depmod *depmod)
> >>         return 0;
> >>  }
> >>
> >> -static size_t mod_count_all_dependencies(const struct mod *mod)
> >> +static size_t mod_count_all_dependencies(const struct mod *mod, size_t
> upper_bound)
> >>  {
> >>         size_t i, count = 0;
> >> +       /* cycle is detected */
> >> +       if (mod->dep_loop)
> >> +               return upper_bound;
> >> +
> >>         for (i = 0; i < mod->deps.count; i++) {
> >>                 const struct mod *d = mod->deps.array[i];
> >> -               count += 1 + mod_count_all_dependencies(d);
> >> +               const size_t child = mod_count_all_dependencies(d,
> upper_bound);
> >> +               if(child == upper_bound)
> >> +                       return child;
> >> +
> >> +               count += 1 + child;
> >>         }
> >>         return count;
> >>  }
> >> @@ -1722,12 +1730,12 @@ static int
> mod_fill_all_unique_dependencies(const struct mod *mod, const struct
> >>         return err;
> >>  }
> >>
> >> -static const struct mod **mod_get_all_sorted_dependencies(const struct
> mod *mod, size_t *n_deps)
> >> +static const struct mod **mod_get_all_sorted_dependencies(const struct
> mod *mod, size_t *n_deps, size_t count)
> >>  {
> >>         const struct mod **deps;
> >>         size_t last = 0;
> >>
> >> -       *n_deps = mod_count_all_dependencies(mod);
> >> +       *n_deps = mod_count_all_dependencies(mod, count);
> >>         if (*n_deps == 0)
> >>                 return NULL;
> >>
> >> @@ -1771,7 +1779,7 @@ static int output_deps(struct depmod *depmod,
> FILE *out)
> >>                 if (mod->deps.count == 0)
> >>                         goto end;
> >>
> >> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> >> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps,
> depmod->modules.count);
> >>                 if (deps == NULL) {
> >>                         ERR("could not get all sorted dependencies of
> %s\n", p);
> >>                         goto end;
> >> @@ -1819,7 +1827,7 @@ static int output_deps_bin(struct depmod *depmod,
> FILE *out)
> >>                         continue;
> >>                 }
> >>
> >> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> >> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps,
> depmod->modules.count);
> >>                 if (deps == NULL && n_deps > 0) {
> >>                         ERR("could not get all sorted dependencies of
> %s\n", p);
> >>                         continue;
> >> --
> >> 1.8.1.4
> >>
> >> --
> >> To unsubscribe from this list: send the line "unsubscribe
> linux-modules" in
> >> the body of a message to majordomo@vger.kernel.org
> >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>
>
> --
> Gustavo Sverzut Barbieri
> --------------------------------------
> Mobile: +55 (19) 99225-2202
> Contact: http://www.gustavobarbieri.com.br/contact
>

[-- Attachment #2: Type: text/html, Size: 6274 bytes --]

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

[ CC'ing Rusty ]

Rusty, when facing module loops, shouldn't we let depmod fail? kmod and
module-init-tools since always just warned about them, but it's really a
bug in the module if they exist. See below.

On Sun, Apr 27, 2014 at 11:44:54PM +0400, Matwey V. Kornilov wrote:
> Can't answer the question. Looking the code, mod_count_all_dependencies has
> to be fixed in that way. The code, running before and after, is
> loop-tolerant.
> 
> However, I am not sure whether loops make sense. Can we load whole the loop
> at once?

nops, this is not possible.


The difference from the code before is that with your approach it would
output the partial dependencies of a module that depends on a loop. So
if we have a module A with these dependencies:

A -> B -> C -> B

modules.dep would contain:

A: B C

Which is wrong and shouldn't be there.

We could fix your patch so we don't output anything until the
dependencies are counted, however we would need to do the same thing
while outputting modules.dep.bin. IMO fixing it in these functions is
already too late... they should only be executed if we are in fact
writing out the index.

So if there are loops, I think we should either (1) fail depmod entirely
or (2) add proper support to depmod_calculate_dependencies() to mark the
loop's dependents.

(1) would be very straightforward
(2) would be like below.

---------8<--------------------
From: Lucas De Marchi <lucas.demarchi@intel.com>
Subject: [PATCH] depmod: Fix not marking dependencies of a loop

Currently we are marking as modules with dep_loop only the modules that
are part of a loop. However we also need to skip the modules that depend
on any module that is part of a loop.

So, before this patch this loop we got right:

	A -> B -> C -
	^           |
	'------------

A, B and C will be ignored due to dependency loops. But this loop we got
wrong:

	A -> B -> C -
	     ^      |
	     '-------

B and C will be ignored due to dependency loops, since they are part of
it, but we will try to output the A's dependencies, leading to an
infinite recursion loop in mod_count_all_dependencies() as pointed out
by Matwey V. Kornilov <matwey.kornilov@gmail.com> in the mailing list.
This is based on his patch, but instead of fixing it by detecting the
loop dependency while outputing A's dependency, this adds the proper
support to depmod_calculate_dependencies() to do the right thing.
---
 tools/depmod.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 85 insertions(+), 20 deletions(-)

diff --git a/tools/depmod.c b/tools/depmod.c
index 1aedaaf..5eea498 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -927,6 +927,7 @@ struct mod {
 	int dep_sort_idx; /* topological sort index */
 	uint16_t idx; /* index in depmod->modules.array */
 	uint16_t users; /* how many modules depend on this one */
+	bool visited; /* helper field to search for loops */
 	uint8_t dep_loop : 1;
 	char modname[];
 };
@@ -1587,6 +1588,86 @@ static void depmod_sort_dependencies(struct depmod *depmod)
 	}
 }
 
+static inline const char *mod_get_compressed_path(const struct mod *mod)
+{
+	if (mod->relpath != NULL)
+		return mod->relpath;
+	return mod->path;
+}
+
+/*
+ * Traverse the tree marking with dep_loop = 1 any module which depends
+ * directly or indirectly in a module with dep_loop = 1. The loops must have
+ * alread been marked.
+ *
+ * We use a depth-first search using @stack to backtrack and @edges to
+ * mark the current visiting modules
+ */
+static void depmod_mark_loop_dependencies(struct depmod *depmod,
+					  uint16_t *stack, uint16_t *edges)
+{
+	const struct mod **itrm;
+	unsigned int i, n_mods = depmod->modules.count;
+	int j, k;
+
+	itrm = (const struct mod **)depmod->modules.array;
+	for (i = 0; i < n_mods; i++, itrm++) {
+		const struct mod *root = *itrm;
+		if (root->visited || root->dep_loop == 1)
+			continue;
+
+		DBG("root = %s\n", mod_get_compressed_path(root));
+
+		/* new DFS with i as root */
+		stack[0] = i;
+		j = 0;
+		k = -1;
+		while (j >= 0) {
+			uint16_t idx = stack[j--];
+			struct mod *m = depmod->modules.array[idx];
+			struct mod **itr_child, **itr_child_end;
+			bool leaf = true;
+
+			DBG("node = %s loop=%d visited=%d\n",
+			    mod_get_compressed_path(m), m->dep_loop,
+			    m->visited);
+
+			if (m->dep_loop == 1) {
+				m->visited = true;
+				while (k >= 0) {
+					struct mod *parent =
+						depmod->modules.array[edges[k--]];
+					parent->dep_loop = 1;
+					parent->dep_sort_idx = INT32_MAX;
+				}
+				break;
+			}
+
+			if (m->visited)
+				continue;
+
+			m->visited = true;
+			edges[++k] = idx;
+
+			itr_child = (struct mod **) m->deps.array;
+			itr_child_end = itr_child + m->deps.count;
+			for (; itr_child < itr_child_end; itr_child++) {
+				struct mod *child = *itr_child;
+
+				if (child->dep_loop == 0 && child->visited)
+					continue;
+
+				stack[++j] = child->idx;
+				leaf = false;
+			}
+
+			if (leaf)
+				k--;
+		}
+	}
+
+}
+
 static int depmod_calculate_dependencies(struct depmod *depmod)
 {
 	const struct mod **itrm;
@@ -1652,6 +1733,9 @@ static int depmod_calculate_dependencies(struct depmod *depmod)
 			m->dep_sort_idx = INT32_MAX;
 			depmod->dep_loops++;
 		}
+
+		/* Re-purpose our buffers for tree traversal */
+		depmod_mark_loop_dependencies(depmod, users, roots);
 	}
 
 	depmod_sort_dependencies(depmod);
@@ -1745,13 +1829,6 @@ static const struct mod **mod_get_all_sorted_dependencies(const struct mod *mod,
 	return deps;
 }
 
-static inline const char *mod_get_compressed_path(const struct mod *mod)
-{
-	if (mod->relpath != NULL)
-		return mod->relpath;
-	return mod->path;
-}
-
 static int output_deps(struct depmod *depmod, FILE *out)
 {
 	size_t i;
@@ -1762,7 +1839,7 @@ static int output_deps(struct depmod *depmod, FILE *out)
 		size_t j, n_deps;
 
 		if (mod->dep_loop) {
-			DBG("Ignored %s due dependency loops\n", p);
+			WRN("Ignored %s due dependency loops\n", p);
 			continue;
 		}
 
@@ -1779,12 +1856,6 @@ static int output_deps(struct depmod *depmod, FILE *out)
 
 		for (j = 0; j < n_deps; j++) {
 			const struct mod *d = deps[j];
-			if (d->dep_loop) {
-				DBG("Ignored %s (dependency of %s) "
-				    "due dependency loops\n",
-				    mod_get_compressed_path(d), p);
-				continue;
-			}
 			fprintf(out, " %s", mod_get_compressed_path(d));
 		}
 		free(deps);
@@ -1828,12 +1899,6 @@ static int output_deps_bin(struct depmod *depmod, FILE *out)
 		linelen = strlen(p) + 1;
 		for (j = 0; j < n_deps; j++) {
 			const struct mod *d = deps[j];
-			if (d->dep_loop) {
-				DBG("Ignored %s (dependency of %s) "
-				    "due dependency loops\n",
-				    mod_get_compressed_path(d), p);
-				continue;
-			}
 			linelen += 1 + strlen(mod_get_compressed_path(d));
 		}
 
-- 
1.9.2
------------------->8---------------------------

I'm letting the rest of the thread below since it never reached the mailing
list.


Lucas De Marchi


> 27.04.2014 19:30 пользователь "Gustavo Sverzut Barbieri" <barbieri@gmail.com>
> написал:
> 
> > patch itself is okay, (one minor syntax issue with lack of space
> > between "if" and "(").
> >
> > But I wonder why just fail if we find loops, are those valid? If not,
> > couldn't we fail earlier and ask people to fix it?
> >
> > On Fri, Apr 25, 2014 at 12:46 AM, Lucas De Marchi
> > <lucas.de.marchi@gmail.com> wrote:
> > > Hi
> > >
> > > On Fri, Apr 11, 2014 at 4:31 PM,  <matwey.kornilov@gmail.com> wrote:
> > >> From 48d4d7ba1acbb5c0955f75c6bdda9cf0935240fd Mon Sep 17 00:00:00 2001
> > >> From: "Matwey V. Kornilov" <matwey.kornilov@gmail.com>
> > >> Date: Fri, 11 Apr 2014 19:43:18 +0400
> > >> Subject: [PATCH] Fix recursion loop in mod_count_all_dependencies() when
> > >>  subgraph has a cycle.
> > >>
> > >> When cycle is detected in mod_count_all_dependencies, use total count of
> > >> modules as an upper bound of needed memory. Correct number of nodes is
> > determined by
> > >> subsequent call of mod_fill_all_unique_dependencies().
> > >
> > > We should deal with this already in depmod_calculate_dependencies(),
> > > otherwise I'd say it would be a bug there. How did you reproduce it?
> > >
> > >
> > > Gustavo, could you take a look on the patch below?
> > >
> > > --
> > > Lucas De Marchi
> > >
> > >> ---
> > >>  tools/depmod.c | 20 ++++++++++++++------
> > >>  1 file changed, 14 insertions(+), 6 deletions(-)
> > >>
> > >> diff --git a/tools/depmod.c b/tools/depmod.c
> > >> index 1aedaaf..c83dee1 100644
> > >> --- a/tools/depmod.c
> > >> +++ b/tools/depmod.c
> > >> @@ -1682,12 +1682,20 @@ static int depmod_load(struct depmod *depmod)
> > >>         return 0;
> > >>  }
> > >>
> > >> -static size_t mod_count_all_dependencies(const struct mod *mod)
> > >> +static size_t mod_count_all_dependencies(const struct mod *mod, size_t
> > upper_bound)
> > >>  {
> > >>         size_t i, count = 0;
> > >> +       /* cycle is detected */
> > >> +       if (mod->dep_loop)
> > >> +               return upper_bound;
> > >> +
> > >>         for (i = 0; i < mod->deps.count; i++) {
> > >>                 const struct mod *d = mod->deps.array[i];
> > >> -               count += 1 + mod_count_all_dependencies(d);
> > >> +               const size_t child = mod_count_all_dependencies(d,
> > upper_bound);
> > >> +               if(child == upper_bound)
> > >> +                       return child;
> > >> +
> > >> +               count += 1 + child;
> > >>         }
> > >>         return count;
> > >>  }
> > >> @@ -1722,12 +1730,12 @@ static int
> > mod_fill_all_unique_dependencies(const struct mod *mod, const struct
> > >>         return err;
> > >>  }
> > >>
> > >> -static const struct mod **mod_get_all_sorted_dependencies(const struct
> > mod *mod, size_t *n_deps)
> > >> +static const struct mod **mod_get_all_sorted_dependencies(const struct
> > mod *mod, size_t *n_deps, size_t count)
> > >>  {
> > >>         const struct mod **deps;
> > >>         size_t last = 0;
> > >>
> > >> -       *n_deps = mod_count_all_dependencies(mod);
> > >> +       *n_deps = mod_count_all_dependencies(mod, count);
> > >>         if (*n_deps == 0)
> > >>                 return NULL;
> > >>
> > >> @@ -1771,7 +1779,7 @@ static int output_deps(struct depmod *depmod,
> > FILE *out)
> > >>                 if (mod->deps.count == 0)
> > >>                         goto end;
> > >>
> > >> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> > >> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps,
> > depmod->modules.count);
> > >>                 if (deps == NULL) {
> > >>                         ERR("could not get all sorted dependencies of
> > %s\n", p);
> > >>                         goto end;
> > >> @@ -1819,7 +1827,7 @@ static int output_deps_bin(struct depmod *depmod,
> > FILE *out)
> > >>                         continue;
> > >>                 }
> > >>
> > >> -               deps = mod_get_all_sorted_dependencies(mod, &n_deps);
> > >> +               deps = mod_get_all_sorted_dependencies(mod, &n_deps,
> > depmod->modules.count);
> > >>                 if (deps == NULL && n_deps > 0) {
> > >>                         ERR("could not get all sorted dependencies of
> > %s\n", p);
> > >>                         continue;
> > >> --
> > >> 1.8.1.4
> > >>
> > >> --
> > >> To unsubscribe from this list: send the line "unsubscribe
> > linux-modules" in
> > >> the body of a message to majordomo@vger.kernel.org
> > >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >
> >
> >
> > --
> > Gustavo Sverzut Barbieri
> > --------------------------------------
> > Mobile: +55 (19) 99225-2202
> > Contact: http://www.gustavobarbieri.com.br/contact
> >

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Matwey V. Kornilov]

2014-05-02 18:13 GMT+04:00 Lucas De Marchi <lucas.de.marchi@gmail.com>:
> leading to an
> infinite recursion loop in mod_count_all_dependencies() as pointed out
> by Matwey V. Kornilov <matwey.kornilov@gmail.com> in the mailing list.

Yes, my patch was intended mostly to highlight the issue. As a
'proper' solution I would prefer more informative output, i.e all the
elements of the single loop are printed out.


-- 
With best regards,
Matwey V. Kornilov
http://blog.matwey.name
xmpp:0x2207@jabber.ru

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Rusty Russell]

Lucas De Marchi <lucas.de.marchi@gmail.com> writes:
> [ CC'ing Rusty ]
>
> Rusty, when facing module loops, shouldn't we let depmod fail? kmod and
> module-init-tools since always just warned about them, but it's really a
> bug in the module if they exist. See below.

Yes.  Soft dependencies can loop, but hard dependencies should barf.
Note that in the case where two modules could satisfy a dependencies,
it may not be a real loop?

Cheers,
Rusty.

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

On Sun, May 4, 2014 at 10:45 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> Lucas De Marchi <lucas.de.marchi@gmail.com> writes:
>> [ CC'ing Rusty ]
>>
>> Rusty, when facing module loops, shouldn't we let depmod fail? kmod and
>> module-init-tools since always just warned about them, but it's really a
>> bug in the module if they exist. See below.
>
> Yes.  Soft dependencies can loop, but hard dependencies should barf.

Ok, then we shouldn't need to fix anything here. Just make depmod die
early and maybe add a better error message (like saying A -> B -> C ->
A, instead of only saying that A, B and C are in a loop like we do
today)

> Note that in the case where two modules could satisfy a dependencies,
> it may not be a real loop?

What do you mean here? How could that be the case for *depmod*?


Lucas De Marchi

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Rusty Russell]

Lucas De Marchi <lucas.de.marchi@gmail.com> writes:
> On Sun, May 4, 2014 at 10:45 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
>> Note that in the case where two modules could satisfy a dependencies,
>> it may not be a real loop?
>
> What do you mean here? How could that be the case for *depmod*?

Sorry, it's a theoretical case; no one does anything this crazy:

 A provides symbol S1.
 B provides symbol S1, needs S2.
 C needs S1, provides S2.
 D provides S2.

Cheers,
Rusty.

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Matwey V. Kornilov]

2014-05-05 14:11 GMT+04:00 Rusty Russell <rusty@rustcorp.com.au>:
>  A provides symbol S1.
>  B provides symbol S1, needs S2.

I think this should be reported too. This case is the most probably a
bug in the kernel or/and in its configuration. Can depmod detect two
modules providing the same symbol?

-- 
With best regards,
Matwey V. Kornilov
http://blog.matwey.name
xmpp:0x2207@jabber.ru

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

On Mon, May 5, 2014 at 7:16 AM, Matwey V. Kornilov
<matwey.kornilov@gmail.com> wrote:
> 2014-05-05 14:11 GMT+04:00 Rusty Russell <rusty@rustcorp.com.au>:
>>  A provides symbol S1.
>>  B provides symbol S1, needs S2.
>
> I think this should be reported too. This case is the most probably a
> bug in the kernel or/and in its configuration. Can depmod detect two
> modules providing the same symbol?

Currently it doesn't because the kernel modpost already warned about
it. However it's very easy to add. Just replacing hash_add() with
hash_add_unique() while adding the symbol and treating the return
would do the job.

Lucas De Marchi

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

On Mon, May 05, 2014 at 07:41:33PM +0930, Rusty Russell wrote:
> Lucas De Marchi <lucas.de.marchi@gmail.com> writes:
> > On Sun, May 4, 2014 at 10:45 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> >> Note that in the case where two modules could satisfy a dependencies,
> >> it may not be a real loop?
> >
> > What do you mean here? How could that be the case for *depmod*?
> 
> Sorry, it's a theoretical case; no one does anything this crazy:
> 
>  A provides symbol S1.
>  B provides symbol S1, needs S2.
>  C needs S1, provides S2.
>  D provides S2.

This never worked. While calculating the dependencies one module will simply
override the previous module providing the symbol... and this will depend on
the path walking order.

However the kernel's modpost already warned about 2 modules providing the same
symbol:

	WARNING: /home/lucas/p/kmod/testsuite/module-playground/moduleC: 'printB' exported twice. Previous export was in /home/lucas/p/kmod/testsuite/module-playground/moduleB.ko

And if we try to load it anyway in the kernel, it fails as it should:

	[  618.643592] moduleC: exports duplicate symbol printB (owned by moduleB)


In the case of duplicate symbols, we could make depmod fail as well, just like if there are loops.

For my tests I used the diff below.

----8<---------------
diff --git a/testsuite/module-playground/moduleC.c b/testsuite/module-playground/moduleC.c
index b74cb07..bf5b5aa 100644
--- a/testsuite/module-playground/moduleC.c
+++ b/testsuite/module-playground/moduleC.c
@@ -8,17 +8,16 @@
 
 static int __init test_module_init(void)
 {
-	printC();
 	printB();
 	return 0;
 }
 module_init(test_module_init);
 
-void printC(void)
+void printB(void)
 {
-	pr_warn("Hello, world C\n");
+	pr_warn("Hello, world C, faking module B\n");
 }
-EXPORT_SYMBOL(printC);
+EXPORT_SYMBOL(printB);
 
 MODULE_AUTHOR("Lucas De Marchi <lucas.demarchi@intel.com>");
 MODULE_LICENSE("GPL");
---->8---------------


Lucas De Marchi

Re: [PATCH] Fix recursion loop in mod_count_all_dependencies()

[Lucas De Marchi]

[-- Attachment #1: Type: text/plain, Size: 600 bytes --]

Adding back CC I forgot.
 Em 27/04/2014 12:40, "Lucas De Marchi" <lucas.de.marchi@gmail.com>
escreveu:

>
> Em 27/04/2014 12:30, "Gustavo Sverzut Barbieri" <barbieri@gmail.com>
> escreveu:
> >
> > patch itself is okay, (one minor syntax issue with lack of space
> > between "if" and "(").
> >
> > But I wonder why just fail if we find loops, are those valid? If not,
> > couldn't we fail earlier and ask people to fix it?
>
> I think it would be better to fail early indeed. Just breaking the loop
> and continuing to output the dependencies won't make it work at runtime.
>
> --
> Lucas De Marchi
>

[-- Attachment #2: Type: text/html, Size: 1038 bytes --]