Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <CAK7LNATrFbr7kT9HEFgYO6ZstaSx1FB+Q4SQrAX+D8VwG5K0dQ@mail.gmail.com>
 <ZF3mJlMuH2HbNxWp@rli9-mobl> <7403dd164cff7d9217999cddb66135db47564c4b.camel@intel.com>
In-Reply-To: <7403dd164cff7d9217999cddb66135db47564c4b.camel@intel.com>
From:   Masahiro Yamada <masahiroy@kernel.org>
Date:   Sat, 10 Jun 2023 00:59:36 +0900
Message-ID: <CAK7LNAT5+NkRa6LyXmFR=Dibfn4G98oBv4MAeQ6m=kP8vcTCeg@mail.gmail.com>
Subject: Re: [RFC] [kbuild test robot] random-order parallel building
To:     "Liu, Yujie" <yujie.liu@intel.com>
Cc:     "Li, Philip" <philip.li@intel.com>,
        "linux-kbuild@vger.kernel.org" <linux-kbuild@vger.kernel.org>,
        lkp <lkp@intel.com>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Fri, Jun 9, 2023 at 5:41=E2=80=AFPM Liu, Yujie <yujie.liu@intel.com> wro=
te:
>
> Hi Masahiro,
>
> On Fri, 2023-05-12 at 15:09 +0800, Philip Li wrote:
> > On Fri, May 12, 2023 at 12:25:13PM +0900, Masahiro Yamada wrote:
> > > Hello, maintainers of the kbuild test robot.
> > >
> > > I have a proposal for the 0day tests.
> >
> > Thanks a lot for the proposal for the shuffle make, we will do some
> > investigation to try this random order parallel build. The gnu make
> > we currently use is 4.3, we will try the 4.4 to see any problem.
> >
> > For the timeline, we may provide update later this month.
>
> We've upgraded to make v4.4.1 in kernel test robot and enabled random-
> order parallel compiling in our randconfig build tests. The shuffle
> seed is generated by hashing the randconfig, so it changes overtime and
> can cover various random orders. We are still doing some internal
> testing and will put it online once everything is done.
>
> > >
> > >
> > > GNU Make traditionally processes the dependency from left to right.
> > >
> > > For example, if you have dependency like this:
> > >
> > >      all: foo bar baz
> > >
> > > GNU Make builds foo, bar, baz, in this order.
> > >
> > >
> > > Some projects that are not capable of parallel builds
> > > rely on that behavior implicitly.
> > >
> > > Kbuild, however, is intended to work well in parallel.
> > > (As the maintainer, I really care about it.)
> > >
> > >
> > > From time to time, people add "just worked for me" code,
> > > but apparently that lacks proper dependency.
> > > Sometimes it requires an expensive CPU to reproduce
> > > parallel build issues.
> > >
> > >
> > > For example, see this report,
> > >   https://lkml.org/lkml/2016/11/30/587
> > >
> > > The report says 'make -j112' reproduces the broken parallel build.
> > > Most people do not have such a build machine that comes with 112
> > > cores.
> > > It is difficult to reproduce it (or even notice it).
> > >
> > > (Some time later, it was root-caused by 07a422bb213a)
>
> Thanks a lot for sharing this case. We tried to reproduce it, but looks
> it dates back to v4.9-rc7 and throws some other errors when compiling
> in our kbuild env, so we are not able to reproduce it yet. Not sure if
> it is related with toolchain/compiler version or the kernel config.
>
> This case mentioned that 'make -j112' can reproduce the breakage. We
> assume this is under traditional serial order build. Does it imply that
> it is likely to take much less parallel jobs to reproduce the breakage
> when shuffle is set, say 'make --shuffle=3DSEED -j32', so developers are
> able to reproduce it on an ordinary CPU with less cores?


I think --shuffle will help a build machine with fewer cores
catch issues, but it is not a full randomization.

In my understanding, --shuffle still traverses depth-first.


Consider this example.


all: foo bar

foo: foo-sub

bar: bar-sub


Only either [1] or [2] happens.

[1] foo-sub -> foo -> bar-sub -> bar -> all
[2] bar-sub -> bar -> foo-sub -> foo -> all


foo-sub -> bar-sub -> bar -> foo -> all

is a possible order, but --shuffle never schedules like that.


> Not sure if there are other known cases of parallel build breakage
> (especially in recent kernels). If any, it would be very kind if you
> could also share them. We can first try reproducing them in the bot to
> confirm our test flow works well.

I do not remember any other real breakage.

>
> Another question is about bisection. Say the bot catches a breakage on
> commit1 which root-caused to a previous commit2. If we keep the options
> "--shuffle=3D<seed> -j<jobs>" consistent during the whole process of
> bisection, will the breakage 100% show up on all the commits between
> commit2 and commit1, or it is kind of possible to reproduce the
> breakage, but not 100% reproducible on every commit during bisection?


I am not sure, but I _guess_ git-bisect may not point to commit 2
if there is a Makefile change in between.


commit2 (root cause)
 -> commitA (add Makefile change)
   -> commit1 (0 day bot noticed an issue here)


Even if the same --shuffle=3DSEED is given, the issue may not be
reproducible on commit2..commitA if commitA changes a Makefile.


Thanks for considering this.


> Thanks a lot for this parallel building proposal, and we will keep
> updating the status.
>
> --
> Best Regards,
> Yujie Liu
>
> > >
> > >
> > > GNU Make 4.4 got this option.
> > >
> > >   --shuffle[=3D{SEED|random|reverse|none}]
> > >        Perform shuffle of prerequisites and goals.
> > >
> > >
> > >
> > > 'make --shuffle=3Dreverse' will build in reverse order.
> > > In the example above, baz, bar, foo.
> > >
> > > 'make --shuffle' will randomize the build order.
> > >
> > >
> > > If there exists a missing dependency among foo, bar, baz,
> > > it will fail to build.
> > >
> > >
> > >
> > > We already perform the randconfig daily basis.
> > > So, random-order parallel building is a similar idea.
> > >
> > > Perhaps, it makes sense to add the "--shuffle=3DSEED" option
> > > but it requires GNU Make 4.4.  (or GNU Make 4.4.1)
> > > Is this too new?
> >
> > Our production environment is 4.3 right now. It will take extra
> > time for us to upgrade the environment but it's doable for us.
> >
> > >
> > >
> > >
> > > --
> > > Best Regards
> > > Masahiro Yamada
> >
>


--=20
Best Regards
Masahiro Yamada