Re: [PATCHSET v6] sched: Implement BPF extensible scheduler class

[Tejun Heo]

Hello, Peter.

On Mon, May 13, 2024 at 10:03:59AM +0200, Peter Zijlstra wrote:
> On Sun, May 05, 2024 at 01:31:26PM -1000, Tejun Heo wrote:
> > The hierarchical scheduling overhead isn't the main motivation for us. We
> > can't use the CPU controller for all workloads and while it'd be nice to
> > improve that,
> 
> Hurmph, I had the impression from the earlier threads that this ~5%
> cgroup overhead was most definitely a problem and a motivator for all
> this.
>
> The overhead was prohibitive, it was claimed, and you needed a solution.
> Did not previous versions use this very argument in order to push for
> all this?

Being able to experiment with potential solutions for problems like
hierarchical scheduling overhead is important and something we wanted to
demonstrate for sched_ext. It's true that the current hierarchical
scheduling is too expensive to deploy on certain workloads but as I wrote
before it's also not that difficult to work around and isn't a high priority
problem for us.

> By improving the cgroup mess -- I very much agree that the cgroup thing
> is not very nice. This whole argument goes away and we all get a better
> cgroup implementation.

Improving the cgroup CPU controller performance would be great. However, I
don't see how that'd be an argument against sched_ext. Sure, with sched_ext,
we can easily test out potential ideas which can lower the hierarchical
scheduling overhead but, if anything, that should make us want it more. Why
wouldn't we want to have such ability for other problems too?

> > This view works only if you assume that the entire world contains only a
> > handful of developers who can work on schedulers. The only way that would be
> > the case is if the barrier of entry is raised unreasonably high. Sometimes a
> > high barrier of entry can't be avoided or is beneficial. However, if it's
> > pushed up high enough to leave only a handful of people to work on an area
> > as large as scheduling, something probably is wrong.
> 
> I've never really felt there were too few sched patches to stare at on
> any one day (quite the opposite on many days in fact).
> 
> There have also always been plenty out of tree scheduler patches --
> although I rarely if ever have time to look at them.
..
> > I believe we agree that we want more people contributing to the scheduling
> > area. 
> 
> I think therein lies the rub -- contribution. If we were to do this
> thing, random loadable BPF schedulers, then how do we ensure people will
> contribute back?

Everything has cost and benefits. Forcing potential contributors into a
single narrow funnel has the benefit of concentrating the effort as you're
pointing out. However, the cost is that it's a single funnel. In addition to
the inherent downsides of having only one of anything, it can handle only so
much, and pushes people away from even considering contributing.

There are multiple types of contributions. Getting concrete patches into the
main scheduler is one. Trying out wildly different ideas and exploring the
problem space is another. Providing a viable competing implementation can be
an important contribution too by keeping everyone on their toes. If we
concentrate just on direct code contributions, we can lose the sight of the
bigger picture costing us in other areas.

During the short period of time that we've been experimenting with
sched_ext, we've already found multiple fairly generic approaches that show
significant gains. That's not because people who have been playing with
sched_ext have special abilities, but rather because there are plenty of
sometimes obvious things which have been difficult to try with the in-kernel
scheduler. Sure, anyone can modify the kernel, but, without a practical way
to publish, deploy and maintain such modifications, it’s really difficult to
justify such effort when the chance of landing upstream is really low. If
our experience up to this point is any indication, capable engineers who are
interested in the area don't seem to be in particularly short supply. What
is in short supply is an environment in which they can participate, develop
and refine their ideas.

Opportunity cost is often more difficult to appreciate but it is as real as
any cost. While there may be more than enough patches for you to review, we
are leaving a lot of opportunities unpursued and potential contributors
outside the fence because the funnel is too narrow and the barrier of entry
too high. Yes, there are benefits to the current setup where we tell
everyone to contribute to a single code base but at this point I believe
it's costing us more than benefiting.

> That is, from where I am sitting I see $vendor mandate their $enterprise
> product needs their $BPF scheduler. At which point $vendor will have no
> incentive to ever contribute back.
> 
> And customers of $vendor that want to run additional workloads on
> their machine are then stuck with that scheduler, irrespective of it
> being suitable for them or not. This is not a good experience.

The above scenario sounds contrived to me. The situation is already like
this with vendor patched kernels. Just like for patched kernels, the vendor
has to share the code for sched_ext schedulers due to GPL. After all, the
BPF verifier will flat out reject loading any non-GPL programs. In addition,
sched_ext has benefits in terms of user experience. Because sched_ext is
designed to be supplemental to the default scheduler, its users have an easy
out - falling back to CFS/EEVDF by simply unloading the sched_ext scheduler.
With patched kernels, they'd have to reboot and a stock kernel might not
even be available.

> So I don't at all mind people playing around with schedulers -- they can
> do so today, there are a ton of out of tree patches to start or learn
> from, or like I said, it really isn't all that hard to just rip out fair
> and write something new.
> 
> Open source, you get to do your own thing. Have at.
> 
> But part of what made Linux work so well, is in my opinion the GPL. GPL
> forces people to contribute back -- to work on the shared project. And I
> see the whole BPF thing as a run-around on that.
> 
> Even the large cloud vendors and service providers (Amazon, Google,
> Facebook etc.) contribute back because of rebase pain -- as you well
> know. The rebase pain offsets the 'TIVO hole'.

Two things are being conflated here. What GPL gives us is that ideas and
code don't get locked up behind a paywall. If someone based their work on a
GPL project, others get to take a look at what they did to learn and copy
from them. The upstream pressure is a separate mechanism which nudges people
towards upstream because the overhead of rebase is painful regardless of the
license requirements.

The upstream pressure works well but as I wrote above it also can be pushed
too far to the point where it costs rather than benefits long term
development. Controlling too tight runs the risk of pushing changes and
proposals worth considering under the ground and potential contributors
away. It may be difficult to judge and agree on where the current situation
exactly is but it is not difficult to see signs of stress. Even just for us,
scheduling is one of the common pain points for both server workloads and
Oculus. Talking to other organizations, we hear similar concerns.

You said two conflicting things - that people can have at it as it's open
source but at the same time that even large organizations are forced to the
funnel due to the rebase pain. It's true that even for large organizations,
deviating from upstream is expensive. However, big orgs can still do it
because the benefit usually scales with the number of machines allowing them
to cross the break-even point and thus pay for it.

But the same pain applies to smaller organizations, researchers and
individuals. Imagine how big a deterrence the current situation would be for
them. It's extremely challenging for them to build a user base and community
as it's very awkward to deploy and painful to maintain custom kernels. Some
still persevere but most would be discouraged even from starting if the
prospect of their work being useful is so slim. This limits potential
contributions from a lot of organizations.

CFS / EEVDF is an excellent general purpose scheduler. It obviously is the
most used and most important scheduler in the whole world. It's difficult to
believe that the only way to get enough people to contribute to it is by
suppressing alternatives. The current approach of funneling potential
contributors to a single code base with a very high bar creates a lot of
pain for those potential contributors, and probably feels unnecessarily
punitive to anyone new to the space. If we have to really worry about losing
contributors to the main Linux scheduler just because sched_ext creates an
additional space that interested engineers can work in, something has gone
really wrong and I don't believe that matches the reality.

> But with the BPF muck; where is the motivation to help improve things?
> 
> Keeping a rando github repo with BPF schedulers is not contributing.
> That's just a repo with multiple out of tree schedulers to be ignored.
> Who will put in the effort of upsteaming things if they can hack up a
> BPF and throw it over the wall?

I wouldn't be so dismissive about development happening outside the kernel
tree. We already see strong community and collaborations in the SCX repo
which is serving as an umbrella project for the sched_ext schedulers.
Different schedulers are chasing different directions but they actively
learn and borrow from each other. It can definitely serve as an incubator to
prove and refine new ideas which can be adopted widely and to grow
scheduling engineers.

For an example, it's still early but Changwoo's work on interactivity in
scx_lavd seems generally useful and has already been adopted by scx_rusty.
It's something which can easily be applied to EEVDF too. Changwoo may or may
not work on EEVDF directly (he says he wants to) but the code change
necessary is neither big nor difficult. Figuring out what actually works was
the hard part, not the implementation. Not all ideas would be like this but
this serves as a good example of how contribution is not just directly
writing patches and how work outside the tree can benefit the kernel.

> So yeah, I'm very much NOT supportive of this effort. From where I'm
> sitting there is simply not a single benefit. You're not making my life
> better, so why would I care?
> 
> How does this BPF muck translate into better quality patches for me?

I'm not sure whether it would make your life better but I firmly believe
that it will benefit overall Linux scheduling in the long term. You don't
necessarily have to care. We'll do our best to ensure that it bothers you as
little as possible.

Maybe I'm mistaken and we won't find much that'd be useful enough for EEVDF
but also maybe there are enough things that we haven't tried that will make
things better for everyone. I believe in the latter and the indications till
now seem to agree. You don't have to share my optimism but wouldn’t it at
least be worthwhile to find out?

Thanks.

-- 
tejun