From: Bjorn Andersson <bjorn.andersson@linaro.org>
To: Mian Yousaf Kaukab <yousaf.kaukab@suse.com>
Cc: Lucas De Marchi <lucas.de.marchi@gmail.com>,
linux-modules <linux-modules@vger.kernel.org>,
afaerber@suse.de
Subject: Re: [PATCH] depmod: ignore related modules in depmod_report_cycles
Date: Tue, 8 Nov 2016 09:03:32 -0800 [thread overview]
Message-ID: <20161108170332.GM25787@tuxbot> (raw)
In-Reply-To: <1478597819.6418.13.camel@suse.com>
On Tue 08 Nov 01:36 PST 2016, Mian Yousaf Kaukab wrote:
> On Mon, 2016-11-07 at 12:23 -0800, Bjorn Andersson wrote:
> > On Mon 07 Nov 09:27 PST 2016, Mian Yousaf Kaukab wrote:
[..]
> >
> > I added some debugging prints to track the stack management in
> > depmod_report_cycles().
> >
> > remoteproc, mdt_loader, wcnss_iris and wcnss_pil are all roots and we
> > have dependencies like this.
> >
> > �������/---(rproc)
> > �������|�����^
> > �������|�����|
> > (pil) -+-> (mdt)
> > � ^����|
> > � |����v
> > � +- (iris)
> AFAICT this is not correct. Dependencies are like following:
>
> pil -> rproc
> pil -> mtd -> rproc
> pil -> iris -> pil
All dependencies are:
pil -> rproc
pil -> mdt
mdt -> rproc
pil -> iris
iris -> pil
The last two forming a cyclic subgraph in a dependency graph including
all of them.
>
> >
> > 1) We pick rproc as first root, mark that as visited and see that
> > we're
> > ���done.
> >
> > 2) We pick mdt_loader as second root, we push remoteproc to the stack
> > ���and find that it's already visited, so we found a loop!
> >
> > �����mdt_loader -> remoteproc
> This is not cyclic.
>
Exactly my point. But the DFS will find this cycle, as we don't reset
"visited" between the iterations in the loop.
> >
> > 3) We pick iris as third root, we push wcnss which pushes remoteproc,
> > ���mdt_loader and iris. All three have already been visited from root
> > #1
> > ���and #2, so we find that there's a loop in:
> >
> > �����iris -> wcnss -> iris
> > �����iris -> wcnss -> mdt
> > �����iris -> wcnss -> remoteproc
> >
> > Only one of these cases are actually a cycle, but as we don't reset
> > visited between the searches we can't tell. Further more, if there
> > was a
> > dependency from iris -> remoteproc that would have shown up earlier
> > and
> > marked iris->visited and when we get to step #3 we would just have
> > bailed directly - completely missing the cycle.
> In case we have more than one cyclic dependencies around same modules?
Well in this case we have a mixture of cyclic and non-cyclic subgraphs
that the DFS hits due to the "visited" issue above, the non-cyclic ones
are what triggers the buffer overflow.
> May be we should add a testcase for such a scenario so that its easy to
> understand and reproduce.
>
+1
Thanks for looking at this!
Regards,
Bjorn
prev parent reply other threads:[~2016-11-08 17:03 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-11-04 9:33 [PATCH] depmod: ignore related modules in depmod_report_cycles Mian Yousaf Kaukab
2016-11-05 23:50 ` Lucas De Marchi
2016-11-07 17:27 ` Mian Yousaf Kaukab
2016-11-07 20:23 ` Bjorn Andersson
2016-11-08 9:36 ` Mian Yousaf Kaukab
2016-11-08 17:03 ` Bjorn Andersson [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161108170332.GM25787@tuxbot \
--to=bjorn.andersson@linaro.org \
--cc=afaerber@suse.de \
--cc=linux-modules@vger.kernel.org \
--cc=lucas.de.marchi@gmail.com \
--cc=yousaf.kaukab@suse.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).