linux-kernel - [RFC][PATCH]: sched/fair: search a task from the tail of the queue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20170824104445.16827-2-urezki@gmail.com>
Date:   Thu, 24 Aug 2017 12:44:45 +0200
From:   "Uladzislau Rezki (Sony)" <urezki@...il.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     LKML <linux-kernel@...r.kernel.org>,
        Ingo Molnar <mingo@...hat.com>, Mike Galbraith <efault@....de>,
        Oleksiy Avramchenko <oleksiy.avramchenko@...ymobile.com>,
        Paul Turner <pjt@...gle.com>, Oleg Nesterov <oleg@...hat.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Mike Galbraith <umgwanakikbuti@...il.com>,
        Kirill Tkhai <tkhai@...dex.ru>,
        Tim Chen <tim.c.chen@...ux.intel.com>,
        Nicolas Pitre <nicolas.pitre@...aro.org>,
        Uladzislau Rezki <urezki@...il.com>
Subject: [RFC][PATCH]: sched/fair: search a task from the tail of the queue

From: Uladzislau Rezki <urezki@...il.com>

When a task is enqueued back from a physical CPU to the running
list it is placed in the beginning of the queue. Thus, the cfs_tasks
list is more or less sorted (except woken tasks) starting from recently
given CPU time tasks toward tasks with max wait time in a run-queue.

As part of the load balance operation, this approach starts
detach_tasks()/detach_one_task() from the tail of the queue
instead of the head, giving some advantages:

- tends to pick a task with highest wait time;
- tasks located in the tail are less likely cache-hot,
  therefore the can_migrate_task() decision is higher.

hackbench illustrates slightly better performance. For example
doing 1000 samples and 40 groups on i5-3320M CPU, it shows below
figures:

default: 0.672 avg / 0.674 median
patched: 0.665 avg / 0.667 median

Signed-off-by: Uladzislau Rezki (Sony) <urezki@...il.com>
---
 kernel/sched/fair.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c77e4b1d51c0..028f5e8bc830 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6806,11 +6806,12 @@ static void detach_task(struct task_struct *p, struct lb_env *env)
  */
 static struct task_struct *detach_one_task(struct lb_env *env)
 {
-	struct task_struct *p, *n;
+	struct task_struct *p;
 
 	lockdep_assert_held(&env->src_rq->lock);
 
-	list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
+	list_for_each_entry_reverse(p,
+			&env->src_rq->cfs_tasks, se.group_node) {
 		if (!can_migrate_task(p, env))
 			continue;
 
@@ -6856,7 +6857,7 @@ static int detach_tasks(struct lb_env *env)
 		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
 			break;
 
-		p = list_first_entry(tasks, struct task_struct, se.group_node);
+		p = list_last_entry(tasks, struct task_struct, se.group_node);
 
 		env->loop++;
 		/* We've more or less seen every task there is, call it quits */
@@ -6906,7 +6907,7 @@ static int detach_tasks(struct lb_env *env)
 
 		continue;
 next:
-		list_move_tail(&p->se.group_node, tasks);
+		list_move(&p->se.group_node, tasks);
 	}
 
 	/*
-- 
2.11.0