• Valentin Schneider's avatar
    sched/fair: Align rq->avg_idle and rq->avg_scan_cost · d76343c6
    Valentin Schneider authored
    sched/core.c uses update_avg() for rq->avg_idle and sched/fair.c uses an
    open-coded version (with the exact same decay factor) for
    rq->avg_scan_cost. On top of that, select_idle_cpu() expects to be able to
    compare these two fields.
    
    The only difference between the two is that rq->avg_scan_cost is computed
    using a pure division rather than a shift. Turns out it actually matters,
    first of all because the shifted value can be negative, and the standard
    has this to say about it:
    
      """
      The result of E1 >> E2 is E1 right-shifted E2 bit positions. [...] If E1
      has a signed type and a negative value, the resulting value is
      implementation-defined.
      """
    
    Not only this, but (arithmetic) right shifting a negative value (using 2's
    complement) is *not* equivalent to dividing it by the corresponding power
    of 2. Let's look at a few examples:
    
      -4      -> 0xF..FC
      -4 >> 3 -> 0xF..FF == -1 != -4 / 8
    
      -8      -> 0xF..F8
      -8 >> 3 -> 0xF..FF == -1 == -8 / 8
    
      -9      -> 0xF..F7
      -9 >> 3 -> 0xF..FE == -2 != -9 / 8
    
    Make update_avg() use a division, and export it to the private scheduler
    header to reuse it where relevant. Note that this still lets compilers use
    a shift here, but should prevent any unwanted surprise. The disassembly of
    select_idle_cpu() remains unchanged on arm64, and ttwu_do_wakeup() gains 2
    instructions; the diff sort of looks like this:
    
      - sub x1, x1, x0
      + subs x1, x1, x0 // set condition codes
      + add x0, x1, #0x7
      + csel x0, x0, x1, mi // x0 = x1 < 0 ? x0 : x1
        add x0, x3, x0, asr #3
    
    which does the right thing (i.e. gives us the expected result while still
    using an arithmetic shift)
    Signed-off-by: default avatarValentin Schneider <valentin.schneider@arm.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
    Link: https://lkml.kernel.org/r/20200330090127.16294-1-valentin.schneider@arm.com
    d76343c6
core.c 198 KB