Re: [PATCH] credit2: make sure we pick a runnable unit from the runq if there is one

[Dario Faggioli <dfaggioli@suse.com>]

[-- Attachment #1: Type: text/plain, Size: 3542 bytes --]

Hi George (and sorry for the delay in replying),

On Mon, 2021-06-07 at 12:10 +0000, George Dunlap wrote:
> > On May 28, 2021, at 4:12 PM, Dario Faggioli <dfaggioli@suse.com>
> > wrote:
> > Reported-by: Michał Leszczyński <michal.leszczynski@cert.pl>
> > Reported-by: Dion Kant <g.w.kant@hunenet.nl>
> > Signed-off-by: Dario Faggioli <dfaggioli@suse.com>
> 
> Thanks for tracking this down, Dario!
> 
Hehe, this was a nasty one indeed! :-P

> Reviewed-by: George Dunlap <george.dunlap@citrix.com>
> 
> Just one comment:
> > @@ -3496,8 +3500,7 @@ runq_candidate(struct csched2_runqueue_data
> > *rqd,
> >          * some budget, then choose it.
> >          */
> >         if ( (yield || svc->credit > snext->credit) &&
> > -             (!has_cap(svc) || unit_grab_budget(svc)) &&
> > -             unit_runnable_state(svc->unit) )
> > +             (!has_cap(svc) || unit_grab_budget(svc)) )
> >             snext = svc;
> 
> By the same logic, shouldn’t we also move the `(!has_cap() …)` clause
> into a separate `if(x) continue` clause?  There may be runnable units
> further down the queue which aren’t capped / haven’t exhausted their
> budget yet.
> 
That's actually a very good point. I think, however, that it's even
more complicated than this.

In fact, if I move the cap+budget check in its own if above this one,
it can happen that some budget is grabbed by the unit. If, however, we
then don't pick it up (because of priority) we then need to have it
return the budget right away, which it's tricky.

So, I came up with the solution of turning the above `if` into this:

        /*
         * If the one in the runqueue has more credit than current (or idle,
         * if current was not runnable) or if current is yielding, we can try
         * to actually pick it.
         */
        if ( (yield || svc->credit > snext->credit) )
        {
            /*
             * The last thing we need to check, is whether the unit has enough
             * budget, in case it is capped. We need to do it now, when we are
             * otherwise sure that we want to pick it already (rather than in
             * its own independent 'if'), to avoid the hassle of needing to
             * return the budget (which we'd have to if we checked and grabbed
             * it but then decide to run someone else).
             */
            if ( has_cap(svc) && !unit_grab_budget(svc) )
                continue;

            /* And if we have go this far, we are done. */
            snext = svc;
            break;
        }

Of course, something else that we can do is to pull the
`if (yield || svc->credit > snext->credit))` "out" of all the other
checks, i.e., doing all the checks we do only either if we're yielding
or if the unit in the runq actually has higher priority.

Efficiency wise, I don't think there will be much difference. The
latter solution is more code-churn (we're basically re-indenting one
level to the right almost the entire `list_for_each_safe` body), but it
might be more readable and easy to understand and follow in the long
run.

So, any preference? :-)

Thanks and Regards
-- 
Dario Faggioli, Ph.D
http://about.me/dario.faggioli
Virtualization Software Engineer
SUSE Labs, SUSE https://www.suse.com/
-------------------------------------------------------------------
<<This happens because _I_ choose it to happen!>> (Raistlin Majere)

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 833 bytes --]