Re:Re:[PATCH-RT sched v4 1/2] RT SCHED: Optimize the enqueue and dequeue operations for rt_se
From: Xavier
Date: Thu Aug 08 2024 - 08:08:47 EST
Just a reminder, does anyone have any comments or feedback on the patch?
--
Best Regards,
Xavier
At 2024-07-25 14:21:03, "Xavier" <xavier_qy@xxxxxxx> wrote:
>
>Hi all,
>
>I would like to ask everyone for your opinions or thoughts on the RT group scheduling
>optimization. At this stage, is it ready to be merged into the corresponding branch?
>Thanks.
>
>--
>Best Regards,
>Xavier
>
>
>
>
>
>At 2024-07-17 11:00:32, "Xavier" <xavier_qy@xxxxxxx> wrote:
>>This patch optimizes the enqueue and dequeue of rt_se, the strategy employs
>>a bottom-up removal approach. Specifically, when removing an rt_se at a
>>certain level, if it is determined that the highest priority of the rq
>>associated with that rt_se has not changed, there is no need to continue
>>removing rt_se at higher levels. At this point, only the total number
>>of removed rt_se needs to be recorded, and the rt_nr_running count of
>>higher-level rq should be removed accordingly.
>>
>>Signed-off-by: Xavier <xavier_qy@xxxxxxx>
>>---
>> kernel/sched/debug.c | 48 ++++++++
>> kernel/sched/rt.c | 287 +++++++++++++++++++++++++++++++++++++------
>> kernel/sched/sched.h | 1 +
>> 3 files changed, 298 insertions(+), 38 deletions(-)
>>
>>diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
>>index c1eb9a1afd13..352ee55da25e 100644
>>--- a/kernel/sched/debug.c
>>+++ b/kernel/sched/debug.c
>>@@ -712,6 +712,54 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
>> #endif
>> }
>>
>>+static void print_rt_se(struct seq_file *m, struct sched_rt_entity *rt_se)
>>+{
>>+ struct task_struct *task;
>>+
>>+#ifdef CONFIG_RT_GROUP_SCHED
>>+ if (rt_se->my_q) {
>>+ SEQ_printf_task_group_path(m, rt_se->my_q->tg, "%s\n");
>>+ return;
>>+ }
>>+#endif
>>+ task = container_of(rt_se, struct task_struct, rt);
>>+ SEQ_printf(m, " prio-%d, pid-%d, %s\n", task->prio, task->pid, task->comm);
>>+}
>>+
>>+/*shall be called in rq lock*/
>>+void print_rt_rq_task(struct seq_file *m, struct rt_rq *rt_rq)
>>+{
>>+ struct rt_prio_array *array = &rt_rq->active;
>>+ struct sched_rt_entity *rt_se;
>>+ struct list_head *queue, *head;
>>+ unsigned long bitmap[2];
>>+ int idx;
>>+ int count = 0;
>>+
>>+ if (!rt_rq->rt_nr_running)
>>+ return;
>>+
>>+ memcpy(bitmap, array->bitmap, sizeof(unsigned long) * 2);
>>+ idx = sched_find_first_bit(bitmap);
>>+ WARN_ON_ONCE(idx >= MAX_RT_PRIO);
>>+
>>+ while (1) {
>>+ clear_bit(idx, bitmap);
>>+ queue = array->queue + idx;
>>+ head = queue;
>>+ queue = queue->next;
>>+ do {
>>+ rt_se = list_entry(queue, struct sched_rt_entity, run_list);
>>+ print_rt_se(m, rt_se);
>>+ queue = queue->next;
>>+ count++;
>>+ } while (queue != head);
>>+ idx = sched_find_first_bit(bitmap);
>>+ if (idx >= MAX_RT_PRIO)
>>+ break;
>>+ }
>>+}
>>+
>> void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq)
>> {
>> #ifdef CONFIG_RT_GROUP_SCHED
>>diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
>>index aa4c1c874fa4..b18c424a50d2 100644
>>--- a/kernel/sched/rt.c
>>+++ b/kernel/sched/rt.c
>>@@ -1113,7 +1113,7 @@ void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
>> #endif /* CONFIG_SMP */
>>
>> #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
>>-static void
>>+static int
>> inc_rt_prio(struct rt_rq *rt_rq, int prio)
>> {
>> int prev_prio = rt_rq->highest_prio.curr;
>>@@ -1122,9 +1122,11 @@ inc_rt_prio(struct rt_rq *rt_rq, int prio)
>> rt_rq->highest_prio.curr = prio;
>>
>> inc_rt_prio_smp(rt_rq, prio, prev_prio);
>>+
>>+ return prev_prio > prio;
>> }
>>
>>-static void
>>+static int
>> dec_rt_prio(struct rt_rq *rt_rq, int prio)
>> {
>> int prev_prio = rt_rq->highest_prio.curr;
>>@@ -1149,12 +1151,22 @@ dec_rt_prio(struct rt_rq *rt_rq, int prio)
>> }
>>
>> dec_rt_prio_smp(rt_rq, prio, prev_prio);
>>+ if (rt_rq->highest_prio.curr > prio)
>>+ return prio;
>>+ else
>>+ return MAX_RT_PRIO;
>> }
>>
>> #else
>>
>>-static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {}
>>-static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {}
>>+static inline int inc_rt_prio(struct rt_rq *rt_rq, int prio)
>>+{
>>+ return 0;
>>+}
>>+static inline int dec_rt_prio(struct rt_rq *rt_rq, int prio)
>>+{
>>+ return 0;
>>+}
>>
>> #endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */
>>
>>@@ -1218,28 +1230,31 @@ unsigned int rt_se_rr_nr_running(struct sched_rt_entity *rt_se)
>> }
>>
>> static inline
>>-void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>>+int inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>> {
>> int prio = rt_se_prio(rt_se);
>>+ int prio_change;
>>
>> WARN_ON(!rt_prio(prio));
>> rt_rq->rt_nr_running += rt_se_nr_running(rt_se);
>> rt_rq->rr_nr_running += rt_se_rr_nr_running(rt_se);
>>
>>- inc_rt_prio(rt_rq, prio);
>>+ prio_change = inc_rt_prio(rt_rq, prio);
>> inc_rt_group(rt_se, rt_rq);
>>+ return prio_change;
>> }
>>
>> static inline
>>-void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>>+int dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq, int prio)
>> {
>>+ int prio_changed;
>> WARN_ON(!rt_prio(rt_se_prio(rt_se)));
>>- WARN_ON(!rt_rq->rt_nr_running);
>> rt_rq->rt_nr_running -= rt_se_nr_running(rt_se);
>> rt_rq->rr_nr_running -= rt_se_rr_nr_running(rt_se);
>>
>>- dec_rt_prio(rt_rq, rt_se_prio(rt_se));
>>+ prio_changed = dec_rt_prio(rt_rq, prio);
>> dec_rt_group(rt_se, rt_rq);
>>+ return prio_changed;
>> }
>>
>> /*
>>@@ -1255,12 +1270,13 @@ static inline bool move_entity(unsigned int flags)
>> return true;
>> }
>>
>>-static void __delist_rt_entity(struct sched_rt_entity *rt_se, struct rt_prio_array *array)
>>+static void __delist_rt_entity(struct sched_rt_entity *rt_se,
>>+ struct rt_prio_array *array, int last_prio)
>> {
>> list_del_init(&rt_se->run_list);
>>
>>- if (list_empty(array->queue + rt_se_prio(rt_se)))
>>- __clear_bit(rt_se_prio(rt_se), array->bitmap);
>>+ if (list_empty(array->queue + last_prio))
>>+ __clear_bit(last_prio, array->bitmap);
>>
>> rt_se->on_list = 0;
>> }
>>@@ -1371,7 +1387,12 @@ update_stats_dequeue_rt(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se,
>> }
>> }
>>
>>-static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
>>+/*
>>+ * Returns: -1 indicates that rt_se was not enqueued, 0 indicates that the highest
>>+ * priority of the rq did not change after enqueue, and 1 indicates that the highest
>>+ * priority of the rq changed after enqueue.
>>+ */
>>+static int __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
>> {
>> struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
>> struct rt_prio_array *array = &rt_rq->active;
>>@@ -1386,8 +1407,8 @@ static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flag
>> */
>> if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running)) {
>> if (rt_se->on_list)
>>- __delist_rt_entity(rt_se, array);
>>- return;
>>+ __delist_rt_entity(rt_se, array, rt_se_prio(rt_se));
>>+ return -1;
>> }
>>
>> if (move_entity(flags)) {
>>@@ -1402,73 +1423,263 @@ static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flag
>> }
>> rt_se->on_rq = 1;
>>
>>- inc_rt_tasks(rt_se, rt_rq);
>>+ return inc_rt_tasks(rt_se, rt_rq);
>> }
>>
>>-static void __dequeue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
>>+/**
>>+ * delete rt_se from rt_rq
>>+ *
>>+ * @rt_se Nodes to be deleted
>>+ * @last_prio The highest priority of this rt_se before the previous round
>>+ * of deletion
>>+ * @flags operation flags
>>+ *
>>+ * Returns: =0 indicates that the highest priority of the current rq did not
>>+ * change during this deletion. >0 indicates it changed, and it returns the
>>+ * previous highest priority to use in the next round of deletion.
>>+ */
>>+static int __dequeue_rt_entity(struct sched_rt_entity *rt_se, int last_prio,
>>+ unsigned int flags)
>> {
>> struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
>> struct rt_prio_array *array = &rt_rq->active;
>>
>> if (move_entity(flags)) {
>> WARN_ON_ONCE(!rt_se->on_list);
>>- __delist_rt_entity(rt_se, array);
>>+ __delist_rt_entity(rt_se, array, last_prio);
>> }
>> rt_se->on_rq = 0;
>>
>>- dec_rt_tasks(rt_se, rt_rq);
>>+ return dec_rt_tasks(rt_se, rt_rq, last_prio);
>>+}
>>+
>>+static inline void dec_rq_nr_running(struct sched_rt_entity *rt_se,
>>+ unsigned int rt, unsigned int rr)
>>+{
>>+ struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
>>+
>>+ rt_rq->rt_nr_running -= rt;
>>+ rt_rq->rr_nr_running -= rr;
>>+}
>>+
>>+static inline void add_rq_nr_running(struct sched_rt_entity *rt_se,
>>+ unsigned int rt, unsigned int rr)
>>+{
>>+ struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
>>+
>>+ rt_rq->rt_nr_running += rt;
>>+ rt_rq->rr_nr_running += rr;
>>+}
>>+
>>+static inline bool on_top_rt_rq(struct sched_rt_entity *rt_se)
>>+{
>>+#ifdef CONFIG_RT_GROUP_SCHED
>>+ if (rt_se->parent)
>>+ return false;
>>+#endif
>>+ return true;
>> }
>>
>> /*
>>- * Because the prio of an upper entry depends on the lower
>>- * entries, we must remove entries top - down.
>>+ * To optimize the enqueue and dequeue of rt_se, this strategy employs a
>>+ * bottom-up removal approach. Specifically, when removing an rt_se at a
>>+ * certain level, if it is determined that the highest priority of the rq
>>+ * associated with that rt_se has not changed, there is no need to continue
>>+ * removing rt_se at higher levels. At this point, only the total number
>>+ * of removed rt_se needs to be recorded, and the rt_nr_running count of
>>+ * higher-level rq should be removed accordingly.
>>+ *
>>+ * For enqueue operations, if an rt_se at a certain level is in the rq,
>>+ * it is still necessary to check the priority of the higher-level rq.
>>+ * If the priority of the higher-level rq is found to be lower than that
>>+ * of the rt_se to be added, it should be removed, as updating the highest
>>+ * priority of the rq during addition will cause the rq to be repositioned
>>+ * in the parent rq.
>>+ *
>>+ * Conversely, for dequeue operations, if an rt_se at a certain level is
>>+ * not in the rq, the operation can be exited immediately to reduce
>>+ * unnecessary checks and handling.
>>+ *
>>+ * The return value refers to the last rt_se that was removed for enqueue
>>+ * operations. And for dequeue operations, it refers to the last rt_se
>>+ * that was either removed or had its rt_nr_running updated.
>> */
>>-static void dequeue_rt_stack(struct sched_rt_entity *rt_se, unsigned int flags)
>>+static struct sched_rt_entity *dequeue_rt_stack(struct sched_rt_entity *rt_se,
>>+ unsigned int flags, int for_enqueue)
>> {
>>- struct sched_rt_entity *back = NULL;
>>- unsigned int rt_nr_running;
>>+ struct sched_rt_entity *last = rt_se;
>>+ struct sched_rt_entity *origin = rt_se;
>>+ unsigned int del_rt_nr = 0;
>>+ unsigned int del_rr_nr = 0;
>>+ int prio_changed = rt_se_prio(rt_se);
>>+ int sub_on_rq = 1;
>>
>> for_each_sched_rt_entity(rt_se) {
>>- rt_se->back = back;
>>- back = rt_se;
>>- }
>>+ if (on_rt_rq(rt_se)) {
>>+ if (sub_on_rq) {
>>+ /*
>>+ * The number of tasks removed from the sub-level rt_se also needs
>>+ * to be subtracted from the rq of the current rt_se, as the current
>>+ * rt_se's rq no longer includes the number of removed tasks.
>>+ */
>>+ dec_rq_nr_running(rt_se, del_rt_nr, del_rr_nr);
>>+ if ((prio_changed != MAX_RT_PRIO) ||
>>+ (rt_se_prio(rt_se) > rt_se_prio(origin))) {
>>+ /*
>>+ * If the removal of the lower-level rt_se causes the
>>+ * highest priority of the current rq to change, or if the
>>+ * priority of current rq is lower than the rt_se to be
>>+ * added, then the current rt_se also needs to be removed
>>+ * from its parent rq, and the number of deleted tasks
>>+ * should be accumulated.
>>+ */
>>+ if (prio_changed == MAX_RT_PRIO)
>>+ prio_changed = rt_se_prio(rt_se);
>>+ del_rt_nr += rt_se_nr_running(rt_se);
>>+ del_rr_nr += rt_se_rr_nr_running(rt_se);
>>+ prio_changed = __dequeue_rt_entity(rt_se,
>>+ prio_changed, flags);
>>+ last = rt_se;
>>+ } else if (!for_enqueue) {
>>+ /* For dequeue, last may only rt_nr_running was modified.*/
>>+ last = rt_se;
>>+ }
>>+ } else {
>>+ /*
>>+ * Entering this branch must be for enqueue, as dequeue would break
>>+ * if an rt_se is not online.
>>+ * If the sub-level node is not online, and the current rt_se's
>>+ * priority is lower than the one being added, current rt_se need
>>+ * to be removed.
>>+ */
>>+ prio_changed = rt_se_prio(rt_se);
>>+ if (prio_changed > rt_se_prio(origin)) {
>>+ del_rt_nr += rt_se_nr_running(rt_se);
>>+ del_rr_nr += rt_se_rr_nr_running(rt_se);
>>+ prio_changed = __dequeue_rt_entity(rt_se,
>>+ prio_changed, flags);
>>+ last = rt_se;
>>+ } else {
>>+ prio_changed = MAX_RT_PRIO;
>>+ }
>>+ }
>>
>>- rt_nr_running = rt_rq_of_se(back)->rt_nr_running;
>>+ /*
>>+ * If the current rt_se is on the top rt_rq, then the already deleted
>>+ * nodes, plus the count of the rt_rq where current rt_se located,
>>+ * need to be removed from the top_rt_rq.
>>+ */
>>+ if (on_top_rt_rq(rt_se)) {
>>+ dequeue_top_rt_rq(rt_rq_of_se(rt_se),
>>+ del_rt_nr + rt_rq_of_se(rt_se)->rt_nr_running);
>>+ }
>>+ sub_on_rq = 1;
>>+ } else if (for_enqueue) {
>>+ struct rt_rq *group_rq = group_rt_rq(rt_se);
>>
>>- for (rt_se = back; rt_se; rt_se = rt_se->back) {
>>- if (on_rt_rq(rt_se))
>>- __dequeue_rt_entity(rt_se, flags);
>>+ /*
>>+ * In the case of an enqueue operation, if a certain level is found to be
>>+ * not online, then the previous counts need to be reset to zero.
>>+ */
>>+ prio_changed = MAX_RT_PRIO;
>>+ sub_on_rq = 0;
>>+ del_rt_nr = 0;
>>+ del_rr_nr = 0;
>>+
>>+ /*
>>+ * If the current group is being throttled, then there is no need to check
>>+ * higher levels since enqueueing will not affect higher-level nodes.
>>+ */
>>+ if (group_rq && rt_rq_throttled(group_rq))
>>+ break;
>>+
>>+ if (on_top_rt_rq(rt_se))
>>+ dequeue_top_rt_rq(rt_rq_of_se(rt_se),
>>+ rt_rq_of_se(rt_se)->rt_nr_running);
>>+ } else {
>>+ last = rt_se;
>>+ break;
>>+ }
>> }
>>
>>- dequeue_top_rt_rq(rt_rq_of_se(back), rt_nr_running);
>>+ return last;
>> }
>>
>> static void enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
>> {
>> struct rq *rq = rq_of_rt_se(rt_se);
>>+ struct sched_rt_entity *last;
>>+ unsigned int add_rt_nr = 0;
>>+ unsigned int add_rr_nr = 0;
>>+ int enqueue = 1;
>>+ int prio_change = 1;
>>
>> update_stats_enqueue_rt(rt_rq_of_se(rt_se), rt_se, flags);
>>
>>- dequeue_rt_stack(rt_se, flags);
>>- for_each_sched_rt_entity(rt_se)
>>- __enqueue_rt_entity(rt_se, flags);
>>+ last = dequeue_rt_stack(rt_se, flags, 1);
>>+
>>+ for_each_sched_rt_entity(rt_se) {
>>+ if (enqueue || !on_rt_rq(rt_se) || (prio_change == 1)) {
>>+ prio_change = __enqueue_rt_entity(rt_se, flags);
>>+ if (prio_change >= 0) {
>>+ add_rt_nr = rt_se_nr_running(rt_se);
>>+ add_rr_nr = rt_se_rr_nr_running(rt_se);
>>+ } else {
>>+ add_rt_nr = add_rr_nr = 0;
>>+ }
>>+ } else {
>>+ add_rq_nr_running(rt_se, add_rt_nr, add_rr_nr);
>>+ }
>>+
>>+ if (rt_se == last)
>>+ enqueue = 0;
>>+ }
>>+
>> enqueue_top_rt_rq(&rq->rt);
>> }
>>
>> static void dequeue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
>> {
>> struct rq *rq = rq_of_rt_se(rt_se);
>>+ struct sched_rt_entity *last;
>>+ unsigned int add_rt_nr = 0;
>>+ unsigned int add_rr_nr = 0;
>>+ int prio_change = 1;
>>
>> update_stats_dequeue_rt(rt_rq_of_se(rt_se), rt_se, flags);
>>
>>- dequeue_rt_stack(rt_se, flags);
>>+ last = dequeue_rt_stack(rt_se, flags, 0);
>>
>> for_each_sched_rt_entity(rt_se) {
>> struct rt_rq *rt_rq = group_rt_rq(rt_se);
>>+ if (rt_rq && rt_rq->rt_nr_running) {
>>+ if (on_rt_rq(rt_se)) {
>>+ add_rq_nr_running(rt_se, add_rt_nr, add_rr_nr);
>>+ } else {
>>+ prio_change = __enqueue_rt_entity(rt_se, flags);
>>+ if (prio_change == 0) {
>>+ /*
>>+ * If enqueue is successful and the priority of the rq has
>>+ * not changed, then the parent node only needs to add the
>>+ * count of the current rt_se. Otherwise, the parent node
>>+ * will also need to enqueue.
>>+ */
>>+ add_rt_nr = rt_se_nr_running(rt_se);
>>+ add_rr_nr = rt_se_rr_nr_running(rt_se);
>>+ }
>>+ }
>>+ } else {
>>+ add_rt_nr = add_rr_nr = 0;
>>+ }
>>
>>- if (rt_rq && rt_rq->rt_nr_running)
>>- __enqueue_rt_entity(rt_se, flags);
>>+ /*
>>+ * last is the rt_se of the last deletion or modification of the
>>+ * count, so the subsequent rt_se does not need to be updated.
>>+ */
>>+ if (rt_se == last)
>>+ break;
>> }
>>+
>> enqueue_top_rt_rq(&rq->rt);
>> }
>>
>>diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
>>index ef20c61004eb..821d65106d13 100644
>>--- a/kernel/sched/sched.h
>>+++ b/kernel/sched/sched.h
>>@@ -2879,6 +2879,7 @@ extern void print_rt_stats(struct seq_file *m, int cpu);
>> extern void print_dl_stats(struct seq_file *m, int cpu);
>> extern void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
>> extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
>>+extern void print_rt_rq_task(struct seq_file *m, struct rt_rq *rt_rq);
>> extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
>>
>> extern void resched_latency_warn(int cpu, u64 latency);
>>--
>>2.45.2