linux-kernel - Re: Question about sched_prio_to

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]
Date:   Mon, 7 Oct 2019 22:41:43 +0200
From:   Francesco Poli <invernomuto@...anoici.org>
To:     linux-kernel@...r.kernel.org
Subject: Re: Question about sched_prio_to_weight values

On Mon, 7 Oct 2019 10:13:23 +0100 Valentin Schneider wrote:

[...]
> Following the blame rabbit hole I found this:
> 
> 254753dc321e ("sched: make the multiplication table more accurate")
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=254753dc321ea2b753ca9bc58ac329557a20efac
> 
> which sounds like it would explain some small deltas if compared to a 
> formula that is set in stone.
> 
> Hope that helps.

It helps a lot, thank you so much for your kind reply!

I am now able to reproduce the numbers (almost), with the following
calc(1) script:

  $ cat prio_to_weight.cal 
  #!/usr/bin/calc -f
  
  oldtilde = config("tilde", "off")
  
  
  printf('nice       mult *   inv_mult   error\n')
  printf('------------------------------------------\n')
  for (nice = -20; nice < 20; ++nice) {
      w = 1024/(1.25)^(nice);
      weight = round(w);
      invmul = round(2^32 / weight);
      error = weight*invmul / 2^32 - 1;
      printf('%3d:%11d *%11d%15.10f\n', nice, weight, invmul, error);
  }
  
  printf('\nnice       mult *   inv_mult   error\n')
  printf('------------------------------------------\n')
  for (nice = -20; nice < 20; ++nice) {
      w = 1024/(1.25)^(nice);
      for (delta = 0; delta < 1000; ++delta) {
          weight = round(w) - delta;
          invmul = round(2^32 / weight);
          error = weight*invmul / 2^32 - 1;
          if (abs(error) < 1e-8) { break; }
          weight = round(w) + delta;
          invmul = round(2^32 / weight);
          error = weight*invmul / 2^32 - 1;
          if (abs(error) < 1e-8) { break; }
      }
      printf('%3d:%11d *%11d%15.10f\n', nice, weight, invmul, error);
  }


After running the script:

  $ ./prio_to_weight.cal | tail -n 42 | tee prio_to_weight.out
  nice       mult *   inv_mult   error
  ------------------------------------------
  -20:      88761 *      48388  -0.0000000065
  -19:      71755 *      59856  -0.0000000037
  -18:      56483 *      76040   0.0000000056
  -17:      46273 *      92818   0.0000000042
  -16:      36291 *     118348  -0.0000000065
  -15:      29154 *     147320  -0.0000000037
  -14:      23254 *     184698  -0.0000000009
  -13:      18705 *     229616  -0.0000000037
  -12:      14949 *     287308  -0.0000000009
  -11:      11916 *     360437  -0.0000000009
  -10:       9548 *     449829  -0.0000000009
   -9:       7620 *     563644  -0.0000000037
   -8:       6100 *     704093   0.0000000009
   -7:       4904 *     875809   0.0000000093
   -6:       3906 *    1099582  -0.0000000009
   -5:       3121 *    1376151  -0.0000000058
   -4:       2501 *    1717300   0.0000000009
   -3:       1991 *    2157191  -0.0000000035
   -2:       1586 *    2708050   0.0000000009
   -1:       1277 *    3363326   0.0000000014
    0:       1024 *    4194304              0
    1:        820 *    5237765   0.0000000009
    2:        655 *    6557202   0.0000000033
    3:        526 *    8165337  -0.0000000079
    4:        423 *   10153587   0.0000000012
    5:        335 *   12820798   0.0000000079
    6:        272 *   15790321   0.0000000037
    7:        215 *   19976592  -0.0000000037
    8:        172 *   24970740  -0.0000000037
    9:        137 *   31350126  -0.0000000079
   10:        110 *   39045157  -0.0000000061
   11:         88 *   48806447   0.0000000093
   12:         70 *   61356676   0.0000000056
   13:         56 *   76695845   0.0000000056
   14:         45 *   95443718   0.0000000033
   15:         36 *  119304647  -0.0000000009
   16:         29 *  148102321   0.0000000030
   17:         23 *  186737709   0.0000000026
   18:         18 *  238609294  -0.0000000009
   19:         15 *  286331153  -0.0000000002

I get an output which is almost identical to the one copied from
the commit message (target.out):

  $ diff target.out prio_to_weight.out
  34c34
  <  11:         87 *   49367440  -0.0000000037
  ---
  >  11:         88 *   48806447   0.0000000093
  36,37c36,37
  <  13:         56 *   76695844  -0.0000000075
  <  14:         45 *   95443717  -0.0000000072
  ---
  >  13:         56 *   76695845   0.0000000056
  >  14:         45 *   95443718   0.0000000033
  39,40c39,40
  <  16:         29 *  148102320  -0.0000000037
  <  17:         23 *  186737708  -0.0000000028
  ---
  >  16:         29 *  148102321   0.0000000030
  >  17:         23 *  186737709   0.0000000026

The differences are probably due to the different precision
of the computations: I don't know the precision of those originally
carried out by Ingo Molnar (single precision? double?), but calc(1)
is an arbitrary precision calculator and, by default, performs
calculations with epsilon = 1e-20 !

Please note that, except for the first one, all the differing
values obtained with the calc(1) script have slightly better
errors than the ones found in kernel/sched/core.c ...


Thanks again for the clarification!
Bye.

-- 
 http://www.inventati.org/frx/
 There's not a second to spare! To the laboratory!
..................................................... Francesco Poli .
 GnuPG key fpr == CA01 1147 9CD2 EFDF FB82  3925 3E1C 27E1 1F69 BFFE

Content of type "application/pgp-signature" skipped