linux-kernel - Re: [PATCH] sched: fix/optimise calculation of weight-inverse

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: <4DCAC8FC.5060505@tu-ilmenau.de>
Date:	Wed, 11 May 2011 19:35:56 +0200
From:	Stephan Bärwolf 
	<stephan.baerwolf@...ilmenau.de>
To:	Peter Zijlstra <peterz@...radead.org>
CC:	Ingo Molnar <mingo@...e.hu>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Nikhil Rao <ncrao@...gle.com>, Mike Galbraith <efault@....de>,
	"Nikunj A. Dadhania" <nikunj@...ux.vnet.ibm.com>,
	Srivatsa Vaddagiri <vatsa@...ux.vnet.ibm.com>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] sched: fix/optimise calculation of weight-inverse

>I think what we wanted to do was minimize the error:
>  err = weight - inv*WMULT_CONST

Hi all,
thanks for your fast response.
I think what you mean is:

err = | WMULT_CONST - inv*weight |  --> min

right?

But the following table(s) shows the difference in the inverses:
(assuming WMULT_CONST = 2**32 as on x64)

weight                                    oldway
inv_weigth                 new inv_weight

1                                             2147483649 (=1+2**31)    
4294967295 [=(2**32)-1]    
2                                            
1431655766                         2147483647
3 (= WEIGHT_IDLEPRIO)        1073741824                         1431655765
15 (= nice 19)                        
268435456                           286331153
1024 (=nice 0)                       
4190212                               4194304
...
...
88761 (=nice -20)                  
48387                                   48388

----

weight                                    err
oldway                             err newway

1                                             2147483647 (=2**31 - 1)   
1     
2                                             1431655764
                        2
3 (= WEIGHT_IDLEPRIO)        1073741824                         1
15 (= nice 19)                         268435456                           1
1024 (=nice 0)                       
4190208                               0
...
...
88761 (=nice -20)                   88789
                                  28



Thus the "err" of the old way can become very large (up to about  2^31 ).
And of course the new error increases with increasing weight, it is
still alway
smaller than the oldway err (because oldway inv converts to newway inv)...


regards Stephan

--
Dipl.-Inf. Stephan Bärwolf
Ilmenau University of Technology, Integrated Communication Systems Group
Phone: +49 (0)3677 69 2821,  FAX: +49 (0)3677 69 1614
Email: stephan.baerwolf@...ilmenau.de,
Web: http://www.tu-ilmenau.de/iks


--
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/