linux-kernel - Re: [RFC][PATCH 00/18] Increase resolution of load weights

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 for Android: free password hash cracker in your pocket

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

Date:	Thu, 28 Apr 2011 17:18:27 +0530
From:	"Nikunj A. Dadhania" <nikunj@...ux.vnet.ibm.com>
To:	Nikhil Rao <ncrao@...gle.com>, Ingo Molnar <mingo@...e.hu>,
	Peter Zijlstra <peterz@...radead.org>
Cc:	Paul Turner <pjt@...gle.com>, Mike Galbraith <efault@....de>,
	linux-kernel@...r.kernel.org, Nikhil Rao <ncrao@...gle.com>,
	Srivatsa Vaddagiri <vatsa@...ux.vnet.ibm.com>,
	Bharata B Rao <bharata@...ux.vnet.ibm.com>
Subject: Re: [RFC][PATCH 00/18] Increase resolution of load weights

On Thu, 28 Apr 2011 12:37:27 +0530, "Nikunj A. Dadhania" <nikunj@...ux.vnet.ibm.com> wrote:
> On Wed, 20 Apr 2011 13:51:19 -0700, Nikhil Rao <ncrao@...gle.com> wrote:
> > Hi All,
> > 
> > I have attached an early version of a RFC patchset to increase resolution of
> > sched entity load weights. This RFC introduces SCHED_LOAD_RESOLUTION which
> > scales NICE_0_LOAD by a factor of 1024. The scaling is done internally and should
> > be completely invisible to the user.
> > 
> > Why do we need this?
> > This extra resolution allows us to scale on two dimensions - number of cpus and
> > the depth of hierarchies. It also allows for proper load balancing of low weight
> > task groups (for eg., nice+19 on autogroup).
> > 
> > One of the big roadblocks for increasing resolution is the use of unsigned long
> > for load.weight, which on 32-bit architectures can overflow with ~48 max-weight
> > sched entities. In this RFC we convert all uses of load.weight to u64. This is
> > still a work-in-progress and I have listed some of the issues I am still
> > investigating below.
> > 
> > I would like to get some feedback on the direction of this patchset. Please let
> > me know if there are alternative ways of doing this, and I'll be happy to
> > explore them as well.
> > 
> > The patchset applies cleanly to v2.6.39-rc4. It compiles for i386 and boots on
> > x86_64. Beyond the basic checks, it has not been well tested yet.
> > 
> > Major TODOs:
> > - Detect overflow in update shares calculations (time * load), and set load_avg
> >   to maximum possible value (~0ULL).
> > - tg->task_weight uses an atomic which needs to be updates to 64-bit on 32-bit
> >   machines. Might need to add a lock to protect this instead of atomic ops.
> > - Check wake-affine math and effective load calculations for overflows.
> > - Needs more testing and need to ensure fairness/balancing is not broken.
> > 
> Hi Nikhil,
> 
> I did a quick test for creating 600 cpu hog tasks with and without this
> patches on a 16cpu machine(x86_64) and I am seeing some mis-behaviour:
> 
> Base kernel - 2.6.39-rc4
> 
> [root@...1 ~]# time -p ./test
> real 43.54
> user 0.12
> sys 1.05
> [root@...1 ~]# 
> 
> Base + patches
> 
> [root@...1 ~]# time -p ./test
> 
> Takes almost infinity, after 2 minutes I see only 16 tasks created
> viewed from another ssh session to the machine:
> 
I could get this working using following patch, not sure if it has other
implications though. With this, I am back to saner time values for
creating 600 cpu hog tasks:

[root@ ~]# time -p ./test
real 45.02
user 0.13
sys 1.07
[root@ ~]# 

===================================================================
    From: Nikunj A. Dadhania <nikunj@...ux.vnet.ibm.com>

    sched: calc_delta_mine - fix calculation
 
    All the calculations of inv_weight takes scaled down weight, while
    calculating the tmp, weight is not scaled down by
    SCHED_LOAD_RESOLUTION, which then will return big values because of
    which the sched_slice thinks that its not time to preempt the
    current running task
    
    Signed-off-by: Nikunj A. Dadhania <nikunj@...ux.vnet.ibm.com>

Index: kernel/sched.c
===================================================================
--- kernel/sched.c.orig	2011-04-28 16:34:24.000000000 +0530
+++ kernel/sched.c	2011-04-28 16:36:29.000000000 +0530
@@ -1336,7 +1336,7 @@ calc_delta_mine(unsigned long delta_exec
 			lw->inv_weight = 1 + (WMULT_CONST - w/2) / (w + 1);
 	}
 
-	tmp = (u64)delta_exec * weight;
+	tmp = (u64)delta_exec * (weight >> SCHED_LOAD_RESOLUTION);
 	/*
 	 * Check whether we'd overflow the 64-bit multiplication:
 	 */

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/