Skip to content

RFC Hierarchical Constant Bandwidth Server

Yuri Andriaccio cgroups lkml 10 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v7 RFC Latest29 patches 15 repliesIn review
  2. v6 RFC25 patches 9 repliesSuperseded
  3. v5 RFC29 patches 39 repliesApplied
Earlier versions · 7
VersionPostedPatchesRepliesStatus
v4 RFC posting 2/228 patches18 repliesSuperseded
v3 RFC posting 2/224 patches22 repliesSuperseded
v4 posting 1/21 patch1 replySuperseded
v3 posting 1/21 patch1 replySuperseded
v2 RFC posting 2/225 patches12 repliesSuperseded
v2 posting 1/21 patch4 repliesSuperseded
v11 patch3 repliesSuperseded

Patches in v7 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/29sched/deadline: Introduce dl_freq_invariant flag for fair/ext serversinclude/linux/sched.h kernel/sched/deadline.c+8 -10 replies
2/29sched/deadline: Do not access dl_se->rq directlykernel/sched/deadline.c+23 -230 replies
3/29sched/deadline: Distinguish between dl_rq and my_qinclude/linux/sched.h kernel/sched/deadline.c kernel/sched/ext/ext.c +2 more+22 -120 replies
4/29sched/rt: Pass an rt_rq instead of an rq where neededkernel/sched/rt.c+104 -700 replies
5/29sched/rt: Move functions from rt.c to sched.hkernel/sched/rt.c kernel/sched/sched.h+58 -560 replies
6/29sched/rt: Disable RT_GROUP_SCHEDkernel/sched/core.c kernel/sched/deadline.c kernel/sched/debug.c +3 more+35 -9130 replies
7/29sched/rt: Remove unnecessary runqueue pointer in struct rt_rqkernel/sched/rt.c kernel/sched/sched.h+21 -160 replies
8/29sched/rt: Introduce HCBS specific structs in task_groupkernel/sched/sched.h+22 -00 replies
9/29sched/core: Initialize HCBS specific structures.kernel/sched/autogroup.c kernel/sched/core.c kernel/sched/deadline.c +2 more+89 -200 replies
10/29sched/deadline: Add dl_init_tgkernel/sched/deadline.c kernel/sched/sched.h+32 -00 replies
11/29sched/rt: Add {alloc/unregister/free}_rt_sched_groupkernel/sched/rt.c+154 -20 replies
12/29sched/deadline: Account rt-cgroups bandwidth in deadline tasks schedulability tests.kernel/sched/deadline.c+41 -170 replies
13/29sched/rt: Implement dl-server operations for rt-cgroups.include/linux/sched.h kernel/sched/deadline.c kernel/sched/rt.c +1 more+80 -160 replies
14/29sched/rt: Update task event callbacks for HCBS schedulingkernel/sched/core.c kernel/sched/rt.c kernel/sched/sched.h +1 more+115 -90 replies
15/29sched/rt: Remove support for cgroups-v1kernel/sched/core.c kernel/sched/rt.c kernel/sched/sched.h+1 -1020 replies
16/29sched/rt: Update rt-cgroup schedulability checksinclude/linux/rcupdate.h include/linux/sched.h kernel/sched/core.c +4 more+447 -860 replies
17/29sched/rt: Update task's RT runqueue when switching scheduling classkernel/sched/rt.c+22 -00 replies
18/29sched/rt: Remove old RT_GROUP_SCHED data structuresinclude/linux/sched.h kernel/sched/sched.h+0 -360 replies
19/29sched/rt: Add HCBS migration code to related functionskernel/sched/rt.c kernel/sched/sched.h+248 -680 replies
20/29sched/rt: Hook HCBS migration functionskernel/sched/rt.c+33 -90 replies
21/29sched/core: Execute enqueued balance callbacks when changing allowed CPUskernel/sched/core.c+13 -00 replies
22/29sched/rt: Try pull task on empty server pick.kernel/sched/deadline.c kernel/sched/rt.c+19 -20 replies
23/29sched/core: Execute enqueued balance callbacks after migrate_disable_switchkernel/sched/core.c+10 -20 replies
24/29sched/syscalls: Allow unpriviledged tasks to set RT priority inside cgroups.kernel/sched/syscalls.c+19 -70 replies
25/29sched/rt: Enable HRTICK_DL for HCBS servers.kernel/sched/deadline.c kernel/sched/rt.c kernel/sched/sched.h+42 -20 replies
26/29Documentation: Update documentation for real-time cgroupsDocumentation/scheduler/sched-rt-group.rst+394 -770 replies
27/29sched/rt: Integrate cpuset and cpu controllersinclude/linux/cpuset.h kernel/cgroup/cpuset.c kernel/sched/core.c +3 more+237 -890 replies
28/29sched/rt: Prevent CPU offline operation on active rt-cgroups.kernel/sched/core.c kernel/sched/rt.c kernel/sched/sched.h+31 -00 replies
29/29sched/rt: Introduce multi-cpu supportkernel/sched/core.c kernel/sched/deadline.c kernel/sched/rt.c +1 more+331 -250 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v7 yet.

Read the v7 thread

Cover letter [RFC PATCH v7 00/29] Hierarchical Constant Bandwidth Server

Hello,

This is the seventh RFC for Hierarchical Constant Bandwidth Server, aiming at replacing the current RT_GROUP_SCHED mechanism with something more robust and theoretically sound. The patchset has been presented at OSPM25 and OSPM26
(https://retis.sssup.it/ospm-summit/), and a summary of its inner workings can be found at https://lwn.net/Articles/1021332/ and the latest updates and discussions at https://lwn.net/Articles/1078696/. You can find the previous versions of this patchset at the bottom of the page, in particular version 1 which talks in more detail what this patchset is all about and how it is implemented.

Version v7 introduces a lot of changes since v6. First off there have been a lot of bug fixes from the comments by the reviewers and the automated AI tool Sashiko, which surprisingly caught a lot of issues. Later, we've finally had time to add features which were planned a long time ago. The following are the most meaningful updates since v6 (the complete changelog can be found on the github readme):
- Rebase to kernel version 7.4-rc1.
- Address (most of) bugs as reported in the v6 reviews.
- Introduce dl_freq_invariant flag for dl_servers.
+ Force fair/ext servers to be frequency/capacity invariant, while allow HCBS servers to scale their consumed runtime.
+ This enables capacity-aware bandwidth reservation also for HCBS.
- Rework cgroup-v2 interface:
+ Rename cpu.rt.internal to cpu.rt.effective.local
+ Fix internal runtime rounding errors.
- Update cgroup balance callbacks to allow balancing operation of multiple cgroups at the same time.
- Allow unprivileged FIFO/RR tasks inside cgroups.
- Allow HRTICK_DL for HCBS servers.
- Integrate cpu and cpuset controllers.
- Integrate HCBS with hotplug/hotunplug operations.
- Introduce dl_server overrides (previously known as multi-runtime/multi-CPU).

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Unprivileged FIFO/RR tasks in cgroups:
Version v7 adds a simple patch to the sched_setattr syscall which allows non-root processes to execute FIFO/RR tasks in already configured HCBS cgroups. The reasoning follows from the fact that only the administrator is capable of creating and managing the real-time bandwidth, and, given the isolation properties of SCHED_DEADLINE, regular users, tied in that specific bandwidth, cannot cause starvation or steal time to other processes/users.
A non-root user cannot migrate its FIFO/RR task anywhere else in the cgroup hierarchy due to permissions, thus it is also impossible to move a user-created HCBS-FIFO task in the root cgroup and steal more bandwidth than the admin allowed.

cpu and cpuset controllers integration:
It has been requested by the maintainers to integrate HCBS with the cpuset cgroup controller, and it made a lot of sense since this enables easier integration with the rest of the scheduler classes in the class-switch code paths. The integration forces the rt-cgroup to have as active the same CPUs as those that cpuset.effective.local allows, while all the other dl_servers are by construction never activated. To simplify the code, the administrator must first setup the cpuset cpus and later setup the HCBS bandwidth. The current integration disallows changing allowed cpus while the HCBS bandwidth is reserved (thus the admin must first remove the HCBS reservation, change the cpuset, and re-request real-time bandwidth).

dl_server override feature:
Following the cpuset integration, we integrated the multi-runtime/multi-CPU
feature: the admin can request the override of the default runtime/period pair for a specific set of CPUs. The user interface works still by writing onto the cpu.rt.max file with a new format, which follows the nested-keyed standard. The original <runtime>|max <period> format is still supported, while the new nested-keyed format is default runtime=<value_us> period=<value_us> or default runtime=max for the default config values as in the original, <cpuset> runtime=<value_us> period=<value_us> to set a specific override and <cpuset> default to reset it. Note that the cpusets must be subsets of the allowed cpus in cpuset.effective.local, and that overrides with runtime zero are disallowed. These strict rules enforce that the active CPUs are exactly those allowed by the cpuset controller, no more no less. The only exception is a cgroup with zero runtime, which allows execution only if all CPUs are overridden, i.e. the same restriction as above (zero runtime cgroups simplifies setup in some cases).
A final note is about max cgroups, which are disallowed to have overrides, i.e. a cgroup is either delegating its FIFO/RR to its nearest active parent or it is managing these itself, but cannot have a mixed behaviour.

hotplug/hotunplug:
We've also fixed the hotplug/hotunplug failures. Hotunplug is allowed only if there are no active HCBS cgroups on the specific core that is going offline. Hotplug does not cause issues but HCBS reservations will need to be updated to make use of the newly enabled core (the cgroups' HCBS specific cpumask is only updated when setting the cgroups' bandwidth).

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Summary of the patches:
1) Introduce dl_freq_invariant flag.
2-7) Preparation patches, so that the RT classes' code can be used both
for normal and cgroup scheduling.
8-18) Implementation of HCBS, no migration.
The old RT_GROUP_SCHED code is removed.
15) Remove support for cgroup-v1.
16) Implement cgroup-v2 cpu.rt.max interface.
19-23) Add support for tasks migration.
24) Allow unprivileged FIFO/RR in rt-cgroups.
25) Enable HRTICK_DL for HCBS.
26) Documentation for HCBS (no cpuset integration yet).
27) Integrate cpuset and cpu controllers.
28) Fix CPU hotplug/hotunplug operations for rt-cgroups.
29) Introduce multi-cpu (dl_server override) support.

Updates from v6:
- Update to kernel version 7.1.
- Refactorings and general cleanups.
- Removal of substantial duplicated code.
- Express more locking constraints in code.
- New cpu.rt.max interface.
- Refactoring of migration code to reduce code duplication.

Updates from v5:
- Rebase to latest master.
- General rebasing/cleanup.
- More locking contraints expressed in code.
- New cpu.rt.max interface.
- Refactoring of migration code.

Updates from v4:
- Rebase to latest tip/master.
- General rebasing/cleanup.
- Update default sysctl_sched_rt_runtime to 1s, same as the period.
- Fix non-deferred deadline server replenishment logic.
- Add missing RCU read sections.
- Account HCBS servers along with their tasks when the servers are active.
- Release bandwidth resources early in unregister_rt_sched_group.
- Drop server_try_pull_task as it is now redundant.
- Remove dl_server_stop call in dequeue_task_rt.
- Update to reuse __checkparam_dl for deadline servers.

Updates from v3:
- Rebase to latest tip/master.
- General rebasing/cleanup.
- Add Documentation.
- Define **live** and **active** groups.
- Introduce server_try_pull_task in place of the removed server_has_task.
- Introduce RELEASE_LOCK helper macro for guard-based locking.
- Update inc/dec_dl_tasks to account for served runqueues regardless of the server type.
- Fix computing of new bandwidth values in dl_init_tg.
- Fix check in dl_check_tg to use capacity scaling.
- Fix wakeup_preempt_rt to check if curr is a DEADLINE task.

Updates from v2:
- Rebase to latest tip/master.
- Remove fair-servers' bw reclaiming.
- Fix a check which prevented execution of wakeup_preempt code.
- Fix a priority check in group_pull_rt_task between tasks of different groups.
- Rework allocation/deallocation code for rt-cgroups.
- Update signatures for some group related migration functions.
- Add documentation for wakeup_preempt preemption rules.

Updates from v1:
- Rebase to latest tip/master.
- Add migration code.
- Split big patches for more readability.
- Refactor code to use guarded locks where applicable.
- Remove unnecessary patches from v1 which have been addressed differently by mainline updates.
- Remove unnecessary checks and general code cleanup.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Testing v7:

The patchset has been tested with a suite of tests tailored to stress all the implemented functionalities.
The tests are available at https://github.com/Yurand2000/HCBS-Test-Suite . Refer to the README of the repository for more details.

Follow these steps to test HCBS v7:
- Get the HCBS patch up and running. Any kernel/disto should work effortlessly.
- Get, compile and _install_ the tests.
- Run the go_rt.sh script to set the frequency of the CPUs to a fixed value and disable hyperthreading and power saving features.
- Run the run_tests.sh full script, to run the whole test suite.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Future Work:

This latest RFC, along with all the new features, is stable on our limited hardware. The patchset is nonetheless potentially lacking testing of some specific code paths and features.

We surely expect comments on the cpuset integration and the dl_server override feature, in the hope to find a better solution for the current limitations.

There is still some pending issues to solve and work to do:
- PI-boosting will cause starvation if cgroups have zero (internal) runtime. There are many solutions, such as bandwidth inheritance or forcing cgroups to not have zero runtime, but this has yet to be investigated. We are open for advice on the matter.
- As Tejun Heo pointed out, it maybe be possible to remove the forceful global reservation of cgroup bandwidth in the root cgroup, while still being compliant with real-time schedulability theory and related SCHED_DEADLINE admission tests.
- There are some potential performance improvements in the migration code that are yet to be implemented (rto_masks).
- Integration with the old v1 cgroup? Maybe disallow HCBS/RT_GROUP_SCHED in cgroups-v1 entirely? There has also been ongoing discussion at
https://lore.kernel.org/all/[email protected]/

Have a nice day,
Yuri

v1: https://lore.kernel.org/all/[email protected]/
v2: https://lore.kernel.org/all/[email protected]/
v3: https://lore.kernel.org/all/[email protected]/
v4: https://lore.kernel.org/all/[email protected]/
v5: https://lore.kernel.org/all/[email protected]/
v6: https://lore.kernel.org/all/[email protected]/

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Yuri Andriaccio (18):
sched/deadline: Introduce dl_freq_invariant flag for fair/ext servers sched/rt: Disable RT_GROUP_SCHED
sched/rt: Remove unnecessary runqueue pointer in struct rt_rq sched/rt: Add {alloc/unregister/free}_rt_sched_group sched/rt: Implement dl-server operations for rt-cgroups. sched/rt: Update task event callbacks for HCBS scheduling sched/rt: Remove support for cgroups-v1
sched/rt: Update task's RT runqueue when switching scheduling class sched/rt: Add HCBS migration code to related functions sched/rt: Hook HCBS migration functions
sched/rt: Try pull task on empty server pick.
sched/core: Execute enqueued balance callbacks after
migrate_disable_switch
sched/syscalls: Allow unpriviledged tasks to set RT priority inside
cgroups.
sched/rt: Enable HRTICK_DL for HCBS servers.
Documentation: Update documentation for real-time cgroups sched/rt: Integrate cpuset and cpu controllers
sched/rt: Prevent CPU offline operation on active rt-cgroups. sched/rt: Introduce multi-cpu support

luca abeni (11):
sched/deadline: Do not access dl_se->rq directly sched/deadline: Distinguish between dl_rq and my_q sched/rt: Pass an rt_rq instead of an rq where needed sched/rt: Move functions from rt.c to sched.h
sched/rt: Introduce HCBS specific structs in task_group sched/core: Initialize HCBS specific structures. sched/deadline: Add dl_init_tg
sched/deadline: Account rt-cgroups bandwidth in deadline tasks
schedulability tests.
sched/rt: Update rt-cgroup schedulability checks sched/rt: Remove old RT_GROUP_SCHED data structures sched/core: Execute enqueued balance callbacks when changing allowed
CPUs

 Documentation/scheduler/sched-rt-group.rst |  471 +++-
 include/linux/cpuset.h                     |    2 +
 include/linux/rcupdate.h                   |    1 +
 include/linux/sched.h                      |   16 +-
 kernel/cgroup/cpuset.c                     |   31 +
 kernel/sched/autogroup.c                   |    4 +-
 kernel/sched/core.c                        |  239 +-
 kernel/sched/deadline.c                    |  324 ++-
 kernel/sched/debug.c                       |    6 -
 kernel/sched/ext/ext.c                     |    4 +-
 kernel/sched/fair.c                        |    4 +-
 kernel/sched/rt.c                          | 2725 +++++++++++---------
 kernel/sched/sched.h                       |  225 +-
 kernel/sched/syscalls.c                    |   37 +-
 14 files changed, 2540 insertions(+), 1549 deletions(-)

base-commit: 6628e7d4c6b25c8d18f1345e3a20d21829aae7e4 --
2.56.0