I am currently reading "Linux Kernel Development" by Robert Love, and I got a few questions about the CFS. My question is how calc_delta_mine calculates :

delta_exec_weighted= (delta_exec * weight)/lw->weight

I guess it is done by two steps :

  1. calculation the (delta_exec * 1024) :

     if (likely(weight > (1UL << SCHED_LOAD_RESOLUTION)))
     tmp = (u64)delta_exec * scale_load_down(weight);
       else
     tmp = (u64)delta_exec;
    
  2. calculate the /lw->weight ( or * lw->inv_weight ) :

      if (!lw->inv_weight) {
      unsigned long w = scale_load_down(lw->weight);
      if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
                lw->inv_weight = 1;
        else if (unlikely(!w))
                lw->inv_weight = WMULT_CONST;
        else
                lw->inv_weight = WMULT_CONST / w;
     }
    
     /*
      * Check whether we'd overflow the 64-bit multiplication:
      */
     if (unlikely(tmp > WMULT_CONST))
             tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,
                     WMULT_SHIFT/2);
     else
             tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);
    
     return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
    

The SRR (Shift right and round) macro is defined via :

    #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))

And the other MACROS are defined :

    #if BITS_PER_LONG == 32
    # define WMULT_CONST    (~0UL)
    #else
    # define WMULT_CONST    (1UL << 32)
    #endif
    #define WMULT_SHIFT     32

Can someone please explain how exactly the SRR works and how does this check the 64-bit multiplication overflow? And please explain the definition of the MACROS in this function((~0UL) ,(1UL << 32))?

share|improve this question
up vote 4 down vote accepted

The code you posted is basically doing calculations using 32.32 fixed-point arithmetic, where a single 64-bit quantity holds the integer part of the number in the high 32 bits, and the decimal part of the number in the low 32 bits (so, for example, 1.5 is 0x0000000180000000 in this system). WMULT_CONST is thus an approximation of 1.0 (using a value that can fit in a long for platform efficiency considerations), and so dividing WMULT_CONST by w computes 1/w as a 32.32 value.

Note that multiplying two 32.32 values together as integers produces a result that is 232 times too large; thus, WMULT_SHIFT (=32) is the right shift value needed to normalize the result of multiplying two 32.32 values together back down to 32.32.

The necessity of using this improved precision for scheduling purposes is explained in a comment in sched/sched.h:

/*
 * Increase resolution of nice-level calculations for 64-bit architectures.
 * The extra resolution improves shares distribution and load balancing of
 * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup
 * hierarchies, especially on larger systems. This is not a user-visible change
 * and does not change the user-interface for setting shares/weights.
 *
 * We increase resolution only if we have enough bits to allow this increased
 * resolution (i.e. BITS_PER_LONG > 32). The costs for increasing resolution
 * when BITS_PER_LONG <= 32 are pretty high and the returns do not justify the
 * increased costs.
 */

As for SRR, mathematically, it computes the rounded result of x / 2y.

To round the result of a division x/q you can calculate x + q/2 floor-divided by q; this is what SRR does by calculating x + 2y-1 floor-divided by 2y.

share|improve this answer
    
thank you. so if I look again at the SRR macro i understand that (1UL << ((y) - 1)) is the 2^(y-1) , and ((x) + (1UL << ((y) - 1))) is x + 2^(y-1). So The last part is taking the result and shift it >> (y) to get it back from 32.32 to original representation ? – arkadish Jul 22 '13 at 20:21
    
>> (y) is the floor division by 2^y. SRR just works on integers; it doesn't care if the results are 32.32 or not. calc_delta_mine uses it to perform calculations on 32.32 numbers. – nneonneo Jul 22 '13 at 20:33
    
It seems tmp is in integer form : tmp = (u64)delta_exec * scale_load_down(weight); when lw->inv_weight = WMULT_CONST / w is in 32.32 form. I think by shifting there multiplication by >>32 I get it again into integer form , this kind of make more sense cause vruntime is an integer and shouldnt be represented as 32.32 . – arkadish Jul 24 '13 at 17:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.