Skip to contentSkip to conversation

tools/sched_ext: Add example C schedulers

PATCH Superseded Emil Tsalapatis 3 participants 8 messages Jan 12 – Jan 13 Scheduler - sched_ext

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover tools/sched_ext: Add example C schedulers

Add to the tree several C sched-ext schedulers developed and maintained out-of-tree by the sched-ext project over the years. These schedulers demonstrate sched-ext's feature set and provide a starting point for scheduler development. Place the schedulers together with the existing examples in tools/sched_ext.

Emil Tsalapatis (4):
tools/sched_ext: add scx_nest scheduler
tools/sched_ext: add scx_userland scheduler
tools/sched_ext: add scx_pair scheduler
tools/sched_ext: add arena based scheduler

 tools/sched_ext/Makefile               |   2 +-
 tools/sched_ext/scx_nest.bpf.c         | 652 +++++++++++++++++++++++
 tools/sched_ext/scx_nest.c             | 240 +++++++++
 tools/sched_ext/scx_nest.h             |  18 +
 tools/sched_ext/scx_nest_stats_table.h |  20 +
 tools/sched_ext/scx_pair.bpf.c         | 610 +++++++++++++++++++++
 tools/sched_ext/scx_pair.c             | 180 +++++++
 tools/sched_ext/scx_pair.h             |   9 +
 tools/sched_ext/scx_sdt.bpf.c          | 710 +++++++++++++++++++++++++
 tools/sched_ext/scx_sdt.c              | 101 ++++
 tools/sched_ext/scx_sdt.h              | 113 ++++
 tools/sched_ext/scx_userland.bpf.c     | 344 ++++++++++++
 tools/sched_ext/scx_userland.c         | 437 +++++++++++++++
 tools/sched_ext/scx_userland.h         |  17 +
 14 files changed, 3452 insertions(+), 1 deletion(-)
 create mode 100644 tools/sched_ext/scx_nest.bpf.c
 create mode 100644 tools/sched_ext/scx_nest.c
 create mode 100644 tools/sched_ext/scx_nest.h
 create mode 100644 tools/sched_ext/scx_nest_stats_table.h
 create mode 100644 tools/sched_ext/scx_pair.bpf.c
 create mode 100644 tools/sched_ext/scx_pair.c
 create mode 100644 tools/sched_ext/scx_pair.h
 create mode 100644 tools/sched_ext/scx_sdt.bpf.c
 create mode 100644 tools/sched_ext/scx_sdt.c
 create mode 100644 tools/sched_ext/scx_sdt.h
 create mode 100644 tools/sched_ext/scx_userland.bpf.c
 create mode 100644 tools/sched_ext/scx_userland.c
 create mode 100644 tools/sched_ext/scx_userland.h
Signature · 1 line
2.49.0
#1 lore raw

PATCH 1/4 tools/sched_ext: add scx_nest scheduler

Add the Nest C scheduler that tries to keep tasks compacted into a few warm (frequency-wise) CPUs.

---
 tools/sched_ext/Makefile               |   2 +-
 tools/sched_ext/scx_nest.bpf.c         | 652 +++++++++++++++++++++++++
 tools/sched_ext/scx_nest.c             | 240 +++++++++
 tools/sched_ext/scx_nest.h             |  18 +
 tools/sched_ext/scx_nest_stats_table.h |  20 +
 5 files changed, 931 insertions(+), 1 deletion(-)
 create mode 100644 tools/sched_ext/scx_nest.bpf.c
 create mode 100644 tools/sched_ext/scx_nest.c
 create mode 100644 tools/sched_ext/scx_nest.h
 create mode 100644 tools/sched_ext/scx_nest_stats_table.h
tools/sched_ext/Makefile +1 -1
index e4bda2474060..2439a311723c 100644
@@ -189,7 +189,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP
 
 SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR)
 
-c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg
+c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest
 
 $(addprefix $(BINDIR)/,$(c-sched-targets)): \
 	$(BINDIR)/%: \
tools/sched_ext/scx_nest.bpf.c new file +652 -0

652 lines not on this page · raw message

tools/sched_ext/scx_nest.c new file +240 -0

240 lines not on this page · raw message

tools/sched_ext/scx_nest.h new file +18 -0
new file mode 100644
index 000000000000..060444f81b88
@@ -0,0 +1,18 @@
+#ifndef __SCX_NEST_H
+#define __SCX_NEST_H
+
+enum nest_stat_group {
+	STAT_GRP_WAKEUP,
+	STAT_GRP_NEST,
+	STAT_GRP_CONSUME,
+};
+
+#define NEST_STAT(__stat) BPFSTAT_##__stat
+#define NEST_ST(__stat, __grp, __desc) NEST_STAT(__stat),
+enum nest_stat_idx {
+#include "scx_nest_stats_table.h"
+	NEST_ST(NR, 0, 0)
+};
+#undef NEST_ST
+
+#endif /* __SCX_NEST_H */
tools/sched_ext/scx_nest_stats_table.h new file +20 -0
new file mode 100644
index 000000000000..6625f705448a
@@ -0,0 +1,20 @@
+NEST_ST(WAKEUP_ATTACHED, STAT_GRP_WAKEUP, "Attached CPU was idle, and in primary nest")
+NEST_ST(WAKEUP_PREV_PRIMARY, STAT_GRP_WAKEUP, "Previous CPU was idle, and in primary nest")
+NEST_ST(WAKEUP_FULLY_IDLE_PRIMARY, STAT_GRP_WAKEUP, "Woken up to fully idle primary nest core")
+NEST_ST(WAKEUP_ANY_IDLE_PRIMARY, STAT_GRP_WAKEUP, "Woken up to idle logical primary nest core")
+NEST_ST(WAKEUP_FULLY_IDLE_RESERVE, STAT_GRP_WAKEUP, "Woken up to fully idle reserve nest core")
+NEST_ST(WAKEUP_ANY_IDLE_RESERVE, STAT_GRP_WAKEUP, "Woken up to idle logical reserve nest core")
+NEST_ST(WAKEUP_IDLE_OTHER, STAT_GRP_WAKEUP, "Woken to any idle logical core in p->cpus_ptr")
+
+NEST_ST(TASK_IMPATIENT, STAT_GRP_NEST, "A task was found to be impatient")
+NEST_ST(PROMOTED_TO_PRIMARY, STAT_GRP_NEST, "A core was promoted into the primary nest")
+NEST_ST(PROMOTED_TO_RESERVED, STAT_GRP_NEST, "A core was promoted into the reserve nest")
+NEST_ST(DEMOTED_TO_RESERVED, STAT_GRP_NEST, "A core was demoted into the reserve nest")
+NEST_ST(RESERVED_AT_CAPACITY, STAT_GRP_NEST, "Reserved nest was at capacity")
+NEST_ST(SCHEDULED_COMPACTION, STAT_GRP_NEST, "Scheduled a primary core to be compacted")
+NEST_ST(CANCELLED_COMPACTION, STAT_GRP_NEST, "Cancelled a primary core from being compacted at task wakeup time")
+NEST_ST(EAGERLY_COMPACTED, STAT_GRP_NEST, "A core was compacted in ops.dispatch()")
+NEST_ST(CALLBACK_COMPACTED, STAT_GRP_NEST, "A core was compacted in the scheduled timer callback")
+
+NEST_ST(CONSUMED, STAT_GRP_CONSUME, "A task was consumed from the global DSQ")
+NEST_ST(NOT_CONSUMED, STAT_GRP_CONSUME, "There was no task in the global DSQ")
Signature · 1 line
2.49.0
#2 lore raw

PATCH 2/4 tools/sched_ext: add scx_userland scheduler

In reply to Emil Tsalapatis

Add in the scx_userland scheduler that does vruntime-based scheduling in userspace code and communicates scheduling decisions to BPF by accessing and modifying globals through the skeleton.

---
 tools/sched_ext/Makefile           |   2 +-
 tools/sched_ext/scx_userland.bpf.c | 344 +++++++++++++++++++++++
 tools/sched_ext/scx_userland.c     | 437 +++++++++++++++++++++++++++++
 tools/sched_ext/scx_userland.h     |  17 ++
 4 files changed, 799 insertions(+), 1 deletion(-)
 create mode 100644 tools/sched_ext/scx_userland.bpf.c
 create mode 100644 tools/sched_ext/scx_userland.c
 create mode 100644 tools/sched_ext/scx_userland.h
tools/sched_ext/Makefile +1 -1
index 2439a311723c..2f06e0587fbb 100644
@@ -189,7 +189,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP
 
 SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR)
 
-c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest
+c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest scx_userland
 
 $(addprefix $(BINDIR)/,$(c-sched-targets)): \
 	$(BINDIR)/%: \
tools/sched_ext/scx_userland.bpf.c new file +344 -0

344 lines not on this page · raw message

tools/sched_ext/scx_userland.c new file +437 -0

437 lines not on this page · raw message

tools/sched_ext/scx_userland.h new file +17 -0
new file mode 100644
index 000000000000..684fb2dd5de9
@@ -0,0 +1,17 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2022 Meta, Inc */
+
+#ifndef __SCX_USERLAND_COMMON_H
+#define __SCX_USERLAND_COMMON_H
+
+/*
+ * An instance of a task that has been enqueued by the kernel for consumption
+ * by a user space global scheduler thread.
+ */
+struct scx_userland_enqueued_task {
+	__s32 pid;
+	u64 sum_exec_runtime;
+	u64 weight;
+};
+
+#endif  // __SCX_USERLAND_COMMON_H
Signature · 1 line
2.49.0
#3 lore raw

PATCH 3/4 tools/sched_ext: add scx_pair scheduler

In reply to Emil Tsalapatis

Add the scx_pair cgroup-based core scheduler.

---
 tools/sched_ext/Makefile       |   2 +-
 tools/sched_ext/scx_pair.bpf.c | 610 +++++++++++++++++++++++++++++++++
 tools/sched_ext/scx_pair.c     | 180 ++++++++++
 tools/sched_ext/scx_pair.h     |   9 +
 4 files changed, 800 insertions(+), 1 deletion(-)
 create mode 100644 tools/sched_ext/scx_pair.bpf.c
 create mode 100644 tools/sched_ext/scx_pair.c
 create mode 100644 tools/sched_ext/scx_pair.h
tools/sched_ext/Makefile +1 -1
index 2f06e0587fbb..32867f468db2 100644
@@ -189,7 +189,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP
 
 SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR)
 
-c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest scx_userland
+c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest scx_userland scx_pair
 
 $(addprefix $(BINDIR)/,$(c-sched-targets)): \
 	$(BINDIR)/%: \
tools/sched_ext/scx_pair.bpf.c new file +610 -0

610 lines not on this page · raw message

tools/sched_ext/scx_pair.c new file +180 -0

180 lines not on this page · raw message

tools/sched_ext/scx_pair.h new file +9 -0
new file mode 100644
index 000000000000..d9666a447d3f
@@ -0,0 +1,9 @@
+#ifndef __SCX_EXAMPLE_PAIR_H
+#define __SCX_EXAMPLE_PAIR_H
+
+enum {
+	MAX_QUEUED		= 4096,
+	MAX_CGRPS		= 4096,
+};
+
+#endif /* __SCX_EXAMPLE_PAIR_H */
Signature · 1 line
2.49.0
#4 lore raw

PATCH 4/4 tools/sched_ext: add arena based scheduler

In reply to Emil Tsalapatis

Add a scheduler that uses BPF arenas to manage task context data.

---
 tools/sched_ext/Makefile      |   2 +-
 tools/sched_ext/scx_sdt.bpf.c | 710 ++++++++++++++++++++++++++++++++++
 tools/sched_ext/scx_sdt.c     | 101 +++++
 tools/sched_ext/scx_sdt.h     | 113 ++++++
 4 files changed, 925 insertions(+), 1 deletion(-)
 create mode 100644 tools/sched_ext/scx_sdt.bpf.c
 create mode 100644 tools/sched_ext/scx_sdt.c
 create mode 100644 tools/sched_ext/scx_sdt.h
tools/sched_ext/Makefile +1 -1
index 32867f468db2..c8cfe326c556 100644
@@ -189,7 +189,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP
 
 SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR)
 
-c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest scx_userland scx_pair
+c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_nest scx_userland scx_pair scx_sdt
 
 $(addprefix $(BINDIR)/,$(c-sched-targets)): \
 	$(BINDIR)/%: \
tools/sched_ext/scx_sdt.bpf.c new file +710 -0

710 lines not on this page · raw message

tools/sched_ext/scx_sdt.c new file +101 -0

101 lines not on this page · raw message

tools/sched_ext/scx_sdt.h new file +113 -0

113 lines not on this page · raw message

Signature · 1 line
2.49.0
reviewer
#5 lore raw
In reply to Emil Tsalapatis

Hi Emil,

Quoted 5 lines · Emil Tsalapatis

Add to the tree several C sched-ext schedulers developed and maintained out-of-tree by the sched-ext project over the years. These schedulers demonstrate sched-ext's feature set and provide a starting point for scheduler development. Place the schedulers together with the existing examples in tools/sched_ext.

In general, I am okay to include more examples of C schedulers in the kernel tree. However, I am doubtful whether it is worth including the nest scheduler, as it has been barely maintained in recent times.

Regards,
Changwoo Min

Quoted 38 lines

Emil Tsalapatis (4):
tools/sched_ext: add scx_nest scheduler
tools/sched_ext: add scx_userland scheduler
tools/sched_ext: add scx_pair scheduler
tools/sched_ext: add arena based scheduler

  tools/sched_ext/Makefile               |   2 +-
  tools/sched_ext/scx_nest.bpf.c         | 652 +++++++++++++++++++++++
  tools/sched_ext/scx_nest.c             | 240 +++++++++
  tools/sched_ext/scx_nest.h             |  18 +
  tools/sched_ext/scx_nest_stats_table.h |  20 +
  tools/sched_ext/scx_pair.bpf.c         | 610 +++++++++++++++++++++
  tools/sched_ext/scx_pair.c             | 180 +++++++
  tools/sched_ext/scx_pair.h             |   9 +
  tools/sched_ext/scx_sdt.bpf.c          | 710 +++++++++++++++++++++++++
  tools/sched_ext/scx_sdt.c              | 101 ++++
  tools/sched_ext/scx_sdt.h              | 113 ++++
  tools/sched_ext/scx_userland.bpf.c     | 344 ++++++++++++
  tools/sched_ext/scx_userland.c         | 437 +++++++++++++++
  tools/sched_ext/scx_userland.h         |  17 +
  14 files changed, 3452 insertions(+), 1 deletion(-)

create mode 100644 tools/sched_ext/scx_nest.bpf.c create mode 100644 tools/sched_ext/scx_nest.c create mode 100644 tools/sched_ext/scx_nest.h create mode 100644 tools/sched_ext/scx_nest_stats_table.h create mode 100644 tools/sched_ext/scx_pair.bpf.c create mode 100644 tools/sched_ext/scx_pair.c create mode 100644 tools/sched_ext/scx_pair.h create mode 100644 tools/sched_ext/scx_sdt.bpf.c create mode 100644 tools/sched_ext/scx_sdt.c create mode 100644 tools/sched_ext/scx_sdt.h create mode 100644 tools/sched_ext/scx_userland.bpf.c create mode 100644 tools/sched_ext/scx_userland.c create mode 100644 tools/sched_ext/scx_userland.h

reviewer
#6 lore raw
Quoted 9 lines · Changwoo Min

Hi Emil,

Quoted 5 lines · Emil Tsalapatis

Add to the tree several C sched-ext schedulers developed and maintained out-of-tree by the sched-ext project over the years. These schedulers demonstrate sched-ext's feature set and provide a starting point for scheduler development. Place the schedulers together with the existing examples in tools/sched_ext.

Quoted 3 lines

In general, I am okay to include more examples of C schedulers in the kernel tree. However, I am doubtful whether it is worth including the nest scheduler, as it has been barely maintained in recent times.

+1 on that, even if it's a good example, it's still unmaintained code. Maybe we should just move it in a separate github repo.

For the rest of the schedulers I'm ok to include them in-tree (still under the assumption that they should be considered examples).

Thanks,
-Andrea

Quoted 43 lines

Regards,
Changwoo Min

Quoted 38 lines

Emil Tsalapatis (4):
tools/sched_ext: add scx_nest scheduler
tools/sched_ext: add scx_userland scheduler
tools/sched_ext: add scx_pair scheduler
tools/sched_ext: add arena based scheduler

  tools/sched_ext/Makefile               |   2 +-
  tools/sched_ext/scx_nest.bpf.c         | 652 +++++++++++++++++++++++
  tools/sched_ext/scx_nest.c             | 240 +++++++++
  tools/sched_ext/scx_nest.h             |  18 +
  tools/sched_ext/scx_nest_stats_table.h |  20 +
  tools/sched_ext/scx_pair.bpf.c         | 610 +++++++++++++++++++++
  tools/sched_ext/scx_pair.c             | 180 +++++++
  tools/sched_ext/scx_pair.h             |   9 +
  tools/sched_ext/scx_sdt.bpf.c          | 710 +++++++++++++++++++++++++
  tools/sched_ext/scx_sdt.c              | 101 ++++
  tools/sched_ext/scx_sdt.h              | 113 ++++
  tools/sched_ext/scx_userland.bpf.c     | 344 ++++++++++++
  tools/sched_ext/scx_userland.c         | 437 +++++++++++++++
  tools/sched_ext/scx_userland.h         |  17 +
  14 files changed, 3452 insertions(+), 1 deletion(-)

create mode 100644 tools/sched_ext/scx_nest.bpf.c create mode 100644 tools/sched_ext/scx_nest.c create mode 100644 tools/sched_ext/scx_nest.h create mode 100644 tools/sched_ext/scx_nest_stats_table.h create mode 100644 tools/sched_ext/scx_pair.bpf.c create mode 100644 tools/sched_ext/scx_pair.c create mode 100644 tools/sched_ext/scx_pair.h create mode 100644 tools/sched_ext/scx_sdt.bpf.c create mode 100644 tools/sched_ext/scx_sdt.c create mode 100644 tools/sched_ext/scx_sdt.h create mode 100644 tools/sched_ext/scx_userland.bpf.c create mode 100644 tools/sched_ext/scx_userland.c create mode 100644 tools/sched_ext/scx_userland.h

#7 lore raw
Quoted 14 lines · Andrea Righi
Quoted 9 lines · Changwoo Min

Hi Emil,

Quoted 5 lines · Emil Tsalapatis

Add to the tree several C sched-ext schedulers developed and maintained out-of-tree by the sched-ext project over the years. These schedulers demonstrate sched-ext's feature set and provide a starting point for scheduler development. Place the schedulers together with the existing examples in tools/sched_ext.

Quoted 3 lines

In general, I am okay to include more examples of C schedulers in the kernel tree. However, I am doubtful whether it is worth including the nest scheduler, as it has been barely maintained in recent times.

Quoted 9 lines

+1 on that, even if it's a good example, it's still unmaintained code. Maybe we should just move it in a separate github repo.

For the rest of the schedulers I'm ok to include them in-tree (still under the assumption that they should be considered examples).

Thanks,
-Andrea

Makes sense, I will remove the nest schedulers and resubmit. Also wrt testing, I'd like to note scx_sdt depends on changes in the current bpf-next to verify, so it should be fine by the end of the merge window.

Quoted 43 lines
Quoted 43 lines

Regards,
Changwoo Min

Quoted 38 lines

Emil Tsalapatis (4):
tools/sched_ext: add scx_nest scheduler
tools/sched_ext: add scx_userland scheduler
tools/sched_ext: add scx_pair scheduler
tools/sched_ext: add arena based scheduler

  tools/sched_ext/Makefile               |   2 +-
  tools/sched_ext/scx_nest.bpf.c         | 652 +++++++++++++++++++++++
  tools/sched_ext/scx_nest.c             | 240 +++++++++
  tools/sched_ext/scx_nest.h             |  18 +
  tools/sched_ext/scx_nest_stats_table.h |  20 +
  tools/sched_ext/scx_pair.bpf.c         | 610 +++++++++++++++++++++
  tools/sched_ext/scx_pair.c             | 180 +++++++
  tools/sched_ext/scx_pair.h             |   9 +
  tools/sched_ext/scx_sdt.bpf.c          | 710 +++++++++++++++++++++++++
  tools/sched_ext/scx_sdt.c              | 101 ++++
  tools/sched_ext/scx_sdt.h              | 113 ++++
  tools/sched_ext/scx_userland.bpf.c     | 344 ++++++++++++
  tools/sched_ext/scx_userland.c         | 437 +++++++++++++++
  tools/sched_ext/scx_userland.h         |  17 +
  14 files changed, 3452 insertions(+), 1 deletion(-)

create mode 100644 tools/sched_ext/scx_nest.bpf.c create mode 100644 tools/sched_ext/scx_nest.c create mode 100644 tools/sched_ext/scx_nest.h create mode 100644 tools/sched_ext/scx_nest_stats_table.h create mode 100644 tools/sched_ext/scx_pair.bpf.c create mode 100644 tools/sched_ext/scx_pair.c create mode 100644 tools/sched_ext/scx_pair.h create mode 100644 tools/sched_ext/scx_sdt.bpf.c create mode 100644 tools/sched_ext/scx_sdt.c create mode 100644 tools/sched_ext/scx_sdt.h create mode 100644 tools/sched_ext/scx_userland.bpf.c create mode 100644 tools/sched_ext/scx_userland.c create mode 100644 tools/sched_ext/scx_userland.h