[v1,2/2] depmod: ignore related modules in depmod_report_cycles
diff mbox

Message ID 1478623550-18716-2-git-send-email-yousaf.kaukab@suse.com
State Accepted
Headers show

Commit Message

Mian Yousaf Kaukab Nov. 8, 2016, 4:45 p.m. UTC
Only print actual cyclic dependencies. Print count of all the modules
in cyclic dependency at the end of the function so that dependent
modules which are not in cyclic chain can be ignored.

Printing dependent modules which are not in cyclic chain causes buffer
overflow as m->modnamesz is not included in buffer size calculations
(loop == m is never true). This buffer overflow causes kmod to crash.

Update depmod test to reflect the change as well.

Reported-by: Andreas Färber <afaerber@suse.de>
Signed-off-by: Mian Yousaf Kaukab <yousaf.kaukab@suse.com>
---
Change-log:
 v1: Keep the old output stings. Only change their order
     Add test case to reproduce the problem

 .../rootfs-pristine/test-depmod/detect-loop/correct.txt     |  2 +-
 tools/depmod.c                                              | 13 ++++++++++++-
 2 files changed, 13 insertions(+), 2 deletions(-)

Comments

Lucas De Marchi Nov. 9, 2016, 12:40 a.m. UTC | #1
On Tue, Nov 8, 2016 at 2:45 PM, Mian Yousaf Kaukab
<yousaf.kaukab@suse.com> wrote:
> Only print actual cyclic dependencies. Print count of all the modules
> in cyclic dependency at the end of the function so that dependent
> modules which are not in cyclic chain can be ignored.
>
> Printing dependent modules which are not in cyclic chain causes buffer
> overflow as m->modnamesz is not included in buffer size calculations
> (loop == m is never true). This buffer overflow causes kmod to crash.
>
> Update depmod test to reflect the change as well.
>
> Reported-by: Andreas Färber <afaerber@suse.de>
> Signed-off-by: Mian Yousaf Kaukab <yousaf.kaukab@suse.com>
> ---
> Change-log:
>  v1: Keep the old output stings. Only change their order
>      Add test case to reproduce the problem
>
>  .../rootfs-pristine/test-depmod/detect-loop/correct.txt     |  2 +-
>  tools/depmod.c                                              | 13 ++++++++++++-
>  2 files changed, 13 insertions(+), 2 deletions(-)
>
> diff --git a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
> index 4eb26df..01ecb89 100644
> --- a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
> +++ b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
> @@ -1,3 +1,3 @@
> -depmod: ERROR: Found 5 modules in dependency cycles!
>  depmod: ERROR: Cycle detected: mod_loop_d -> mod_loop_e -> mod_loop_d
>  depmod: ERROR: Cycle detected: mod_loop_b -> mod_loop_c -> mod_loop_a -> mod_loop_b
> +depmod: ERROR: Found 5 modules in dependency cycles!
> diff --git a/tools/depmod.c b/tools/depmod.c
> index ad01f66..f2b370f 100644
> --- a/tools/depmod.c
> +++ b/tools/depmod.c
> @@ -1456,7 +1456,7 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
>  {
>         const char sep[] = " -> ";
>         int ir = 0;
> -       ERR("Found %u modules in dependency cycles!\n", n_roots);
> +       int num_cyclic = 0;
>
>         while (n_roots > 0) {
>                 int is, ie;
> @@ -1491,6 +1491,7 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
>                         if (m->visited) {
>                                 int i, n = 0, sz = 0;
>                                 char *buf;
> +                               bool is_cyclic = false;
>
>                                 for (i = ie - 1; i >= 0; i--) {
>                                         struct mod *loop = depmod->modules.array[edges[i]];
> @@ -1498,9 +1499,17 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
>                                         n++;
>                                         if (loop == m) {
>                                                 sz += loop->modnamesz - 1;
> +                                               is_cyclic = true;
>                                                 break;
>                                         }
>                                 }
> +                               /* Current module not found in dependency list.
> +                                * Must be a related module. Ignore it.
> +                                */
> +                               if (!is_cyclic)
> +                                       continue;
> +
> +                               num_cyclic += n;
>
>                                 buf = malloc(sz + n * strlen(sep) + 1);
>                                 sz = 0;
> @@ -1538,6 +1547,8 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
>                         }
>                 }
>         }
> +
> +       ERR("Found %d modules in dependency cycles!\n", num_cyclic);
>  }

thanks, much better now.

Applied.

Lucas De Marchi
--
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
Yauheni Kaliuta Nov. 9, 2016, 2:59 a.m. UTC | #2
Hi!

It may require more serious refactoring, since there is a problem with the
approach of path recording. I can get wrong output, for example, for the
following graph:

/*
  mod6 -> mod7 -> mod8 -> mod9
   ^               |       |
    ---------------        |
   |                       |
    -----------------------
*/

depmod: ERROR: Cycle detected: mod7 -> mod8 -> mod9 -> mod6 -> mod7
depmod: ERROR: Cycle detected: mod6 -> mod6
depmod: ERROR: Found 5 modules in dependency cycles!


The problem is that the path is recorded "globally", not per vertex, and
"wrong" mod6 is compared in "loop == m".


>>>>> On Tue, 8 Nov 2016 22:40:20 -0200, Lucas De Marchi  wrote:

 > On Tue, Nov 8, 2016 at 2:45 PM, Mian Yousaf Kaukab
 > <yousaf.kaukab@suse.com> wrote:
 >> Only print actual cyclic dependencies. Print count of all the modules
 >> in cyclic dependency at the end of the function so that dependent
 >> modules which are not in cyclic chain can be ignored.
 >> 
 >> Printing dependent modules which are not in cyclic chain causes buffer
 >> overflow as m->modnamesz is not included in buffer size calculations
 >> (loop == m is never true). This buffer overflow causes kmod to crash.
 >> 
 >> Update depmod test to reflect the change as well.
 >> 
 >> Reported-by: Andreas Färber <afaerber@suse.de>
 >> Signed-off-by: Mian Yousaf Kaukab <yousaf.kaukab@suse.com>
 >> ---
 >> Change-log:
 >> v1: Keep the old output stings. Only change their order
 >> Add test case to reproduce the problem
 >> 
 >> .../rootfs-pristine/test-depmod/detect-loop/correct.txt     |  2 +-
 >> tools/depmod.c                                              | 13 ++++++++++++-
 >> 2 files changed, 13 insertions(+), 2 deletions(-)
 >> 
 >> diff --git a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
 >> index 4eb26df..01ecb89 100644
 >> --- a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
 >> +++ b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
 >> @@ -1,3 +1,3 @@
 >> -depmod: ERROR: Found 5 modules in dependency cycles!
 >> depmod: ERROR: Cycle detected: mod_loop_d -> mod_loop_e -> mod_loop_d
 >> depmod: ERROR: Cycle detected: mod_loop_b -> mod_loop_c -> mod_loop_a -> mod_loop_b
 >> +depmod: ERROR: Found 5 modules in dependency cycles!
 >> diff --git a/tools/depmod.c b/tools/depmod.c
 >> index ad01f66..f2b370f 100644
 >> --- a/tools/depmod.c
 >> +++ b/tools/depmod.c
 >> @@ -1456,7 +1456,7 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 >> {
 >> const char sep[] = " -> ";
 >> int ir = 0;
 >> -       ERR("Found %u modules in dependency cycles!\n", n_roots);
 >> +       int num_cyclic = 0;
 >> 
 >> while (n_roots > 0) {
 >> int is, ie;
 >> @@ -1491,6 +1491,7 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 >> if (m->visited) {
 >> int i, n = 0, sz = 0;
 >> char *buf;
 >> +                               bool is_cyclic = false;
 >> 
 >> for (i = ie - 1; i >= 0; i--) {
 >> struct mod *loop = depmod->modules.array[edges[i]];
 >> @@ -1498,9 +1499,17 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 >> n++;
 >> if (loop == m) {
 >> sz += loop->modnamesz - 1;
 >> +                                               is_cyclic = true;
 >> break;
 >> }
 >> }
 >> +                               /* Current module not found in dependency list.
 >> +                                * Must be a related module. Ignore it.
 >> +                                */
 >> +                               if (!is_cyclic)
 >> +                                       continue;
 >> +
 >> +                               num_cyclic += n;
 >> 
 >> buf = malloc(sz + n * strlen(sep) + 1);
 >> sz = 0;
 >> @@ -1538,6 +1547,8 @@ static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 >> }
 >> }
 >> }
 >> +
 >> +       ERR("Found %d modules in dependency cycles!\n", num_cyclic);
 >> }

 > thanks, much better now.

 > Applied.
Mian Yousaf Kaukab Nov. 9, 2016, 9:17 a.m. UTC | #3
On Wed, 2016-11-09 at 04:59 +0200, Yauheni Kaliuta wrote:
> Hi!
> 
> It may require more serious refactoring, since there is a problem
> with the
> approach of path recording. I can get wrong output, for example, for
> the
> following graph:
> 
> /*
>   mod6 -> mod7 -> mod8 -> mod9
>    ^               |       |
>     ---------------        |
>    |                       |
>     -----------------------
> */
> 
> depmod: ERROR: Cycle detected: mod7 -> mod8 -> mod9 -> mod6 -> mod7
> depmod: ERROR: Cycle detected: mod6 -> mod6
> depmod: ERROR: Found 5 modules in dependency cycles!
> 
> 
> The problem is that the path is recorded "globally", not per vertex,
> and
> "wrong" mod6 is compared in "loop == m".

I agree and in the other thread Bjorn is mentioning kind of the same.

BR,
Yousaf
--
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
Yauheni Kaliuta Nov. 9, 2016, 11:23 a.m. UTC | #4
Hi, Mian!

>>>>> On Wed, 09 Nov 2016 10:17:33 +0100, Mian Yousaf Kaukab  wrote:
 > On Wed, 2016-11-09 at 04:59 +0200, Yauheni Kaliuta wrote:

[...]

 >> The problem is that the path is recorded "globally", not per vertex,
 >> and "wrong" mod6 is compared in "loop == m".

 > I agree and in the other thread Bjorn is mentioning kind of the same.

Ah, sorry, my bad: I just subscribed to the actual mailing list and Gmane
has the latest message from July.
Yauheni Kaliuta Nov. 11, 2016, 11:43 a.m. UTC | #5
Back to the discussion, does it make any sense?

This is an RFC proposal of dependency loops reporting.

Yauheni Kaliuta (3):
  testsuite: depmod: check netsted loops reporting
  libkmod: list: export list handling functions
  depmod: handle nested loops

 Makefile.am                                        |   4 +
 libkmod/libkmod-internal.h                         |   4 -
 libkmod/libkmod-list.c                             |  36 ++-
 libkmod/libkmod.h                                  |   5 +
 testsuite/module-playground/Makefile               |   7 +
 testsuite/module-playground/cache/mod-loop-h.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/cache/mod-loop-i.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/cache/mod-loop-j.ko    | Bin 0 -> 197968 bytes
 testsuite/module-playground/cache/mod-loop-k.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/mod-loop-h.c           |  25 ++
 testsuite/module-playground/mod-loop-i.c           |  25 ++
 testsuite/module-playground/mod-loop-j.c           |  26 ++
 testsuite/module-playground/mod-loop-k.c           |  25 ++
 testsuite/module-playground/mod-loop.h             |   4 +
 testsuite/populate-modules.sh                      |   4 +
 .../test-depmod/detect-loop/correct.txt            |   6 +-
 tools/depmod.c                                     | 287 +++++++++++++++------
 17 files changed, 367 insertions(+), 91 deletions(-)
 create mode 100644 testsuite/module-playground/cache/mod-loop-h.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-i.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-j.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-k.ko
 create mode 100644 testsuite/module-playground/mod-loop-h.c
 create mode 100644 testsuite/module-playground/mod-loop-i.c
 create mode 100644 testsuite/module-playground/mod-loop-j.c
 create mode 100644 testsuite/module-playground/mod-loop-k.c
Lucas De Marchi Feb. 13, 2017, 8:16 a.m. UTC | #6
On Fri, Nov 11, 2016 at 3:43 AM, Yauheni Kaliuta
<yauheni.kaliuta@redhat.com> wrote:
> Back to the discussion, does it make any sense?
>
> This is an RFC proposal of dependency loops reporting.
>
> Yauheni Kaliuta (3):
>   testsuite: depmod: check netsted loops reporting

This patch didn't arrive to the mailing list probably due to its size.
Do you have a git repo I can pull it from?

Lucas De Marchi
--
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
Lucas De Marchi Feb. 13, 2017, 8:32 a.m. UTC | #7
On Fri, Nov 11, 2016 at 3:43 AM, Yauheni Kaliuta
<yauheni.kaliuta@redhat.com> wrote:
> Back to the discussion, does it make any sense?
>
> This is an RFC proposal of dependency loops reporting.
>
> Yauheni Kaliuta (3):
>   testsuite: depmod: check netsted loops reporting
>   libkmod: list: export list handling functions
>   depmod: handle nested loops

I added some comments. It's looking good and I'd like to get this in
to do a release this week.

thanks for fixing this.

Lucas De Marchi
--
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
Yauheni Kaliuta Feb. 13, 2017, 9:56 a.m. UTC | #8
Hi, Lucas!

>>>>> On Mon, 13 Feb 2017 00:16:44 -0800, Lucas De Marchi  wrote:

 > On Fri, Nov 11, 2016 at 3:43 AM, Yauheni Kaliuta
 > <yauheni.kaliuta@redhat.com> wrote:
 >> Back to the discussion, does it make any sense?
 >> 
 >> This is an RFC proposal of dependency loops reporting.
 >> 
 >> Yauheni Kaliuta (3):
 >> testsuite: depmod: check netsted loops reporting

 > This patch didn't arrive to the mailing list probably due to its size.
 > Do you have a git repo I can pull it from?

I've put it to github (the sent version),
https://github.com/ykaliuta/kmod/commit/96c987e287262c63a9e268f0e3b48aea98700a0f

Thank you a lot for the review!
Yauheni Kaliuta Feb. 20, 2017, 2:18 p.m. UTC | #9
This is an RFC proposal of dependency loops reporting.

V1->V2:

- use libkmod-internal.h and access list value directly;
- initially create reverse array with 3 elements;
- use memcpy() instead of strcpy() in depmod_report_one_cycle();
- replace "because" with "since" in comment about single branch.

Yauheni Kaliuta (2):
  testsuite: depmod: check netsted loops reporting
  depmod: handle nested loops

 Makefile.am                                        |   4 +
 testsuite/module-playground/Makefile               |   7 +
 testsuite/module-playground/cache/mod-loop-h.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/cache/mod-loop-i.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/cache/mod-loop-j.ko    | Bin 0 -> 197968 bytes
 testsuite/module-playground/cache/mod-loop-k.ko    | Bin 0 -> 197808 bytes
 testsuite/module-playground/mod-loop-h.c           |  25 ++
 testsuite/module-playground/mod-loop-i.c           |  25 ++
 testsuite/module-playground/mod-loop-j.c           |  26 ++
 testsuite/module-playground/mod-loop-k.c           |  25 ++
 testsuite/module-playground/mod-loop.h             |   4 +
 testsuite/populate-modules.sh                      |   4 +
 .../test-depmod/detect-loop/correct.txt            |   6 +-
 tools/depmod.c                                     | 292 +++++++++++++++------
 14 files changed, 332 insertions(+), 86 deletions(-)
 create mode 100644 testsuite/module-playground/cache/mod-loop-h.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-i.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-j.ko
 create mode 100644 testsuite/module-playground/cache/mod-loop-k.ko
 create mode 100644 testsuite/module-playground/mod-loop-h.c
 create mode 100644 testsuite/module-playground/mod-loop-i.c
 create mode 100644 testsuite/module-playground/mod-loop-j.c
 create mode 100644 testsuite/module-playground/mod-loop-k.c

Patch
diff mbox

diff --git a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
index 4eb26df..01ecb89 100644
--- a/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
+++ b/testsuite/rootfs-pristine/test-depmod/detect-loop/correct.txt
@@ -1,3 +1,3 @@ 
-depmod: ERROR: Found 5 modules in dependency cycles!
 depmod: ERROR: Cycle detected: mod_loop_d -> mod_loop_e -> mod_loop_d
 depmod: ERROR: Cycle detected: mod_loop_b -> mod_loop_c -> mod_loop_a -> mod_loop_b
+depmod: ERROR: Found 5 modules in dependency cycles!
diff --git a/tools/depmod.c b/tools/depmod.c
index ad01f66..f2b370f 100644
--- a/tools/depmod.c
+++ b/tools/depmod.c
@@ -1456,7 +1456,7 @@  static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 {
 	const char sep[] = " -> ";
 	int ir = 0;
-	ERR("Found %u modules in dependency cycles!\n", n_roots);
+	int num_cyclic = 0;
 
 	while (n_roots > 0) {
 		int is, ie;
@@ -1491,6 +1491,7 @@  static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 			if (m->visited) {
 				int i, n = 0, sz = 0;
 				char *buf;
+				bool is_cyclic = false;
 
 				for (i = ie - 1; i >= 0; i--) {
 					struct mod *loop = depmod->modules.array[edges[i]];
@@ -1498,9 +1499,17 @@  static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 					n++;
 					if (loop == m) {
 						sz += loop->modnamesz - 1;
+						is_cyclic = true;
 						break;
 					}
 				}
+				/* Current module not found in dependency list.
+				 * Must be a related module. Ignore it.
+				 */
+				if (!is_cyclic)
+					continue;
+
+				num_cyclic += n;
 
 				buf = malloc(sz + n * strlen(sep) + 1);
 				sz = 0;
@@ -1538,6 +1547,8 @@  static void depmod_report_cycles(struct depmod *depmod, uint16_t n_mods,
 			}
 		}
 	}
+
+	ERR("Found %d modules in dependency cycles!\n", num_cyclic);
 }
 
 static int depmod_calculate_dependencies(struct depmod *depmod)