Commit 07b0eb5d0ef0 ("credit2: make sure we pick a runnable unit from the
runq if there is one") did not fix completely the problem of potentially
selecting a scheduling unit that will then not be able to run.

In fact, in case caps are used and the unit we are currently looking
at, during the runqueue scan, does not have enough budget for being run,
we should continue looking instead than giving up and picking the idle
unit.

Suggested-by: George Dunlap <george.dunlap@citrix.com>
Signed-off-by: Dario Faggioli <dfaggioli@suse.com>
Cc: George Dunlap <george.dunlap@citrix.com>
Cc: Jan Beulich <jbeulich@suse.com>
---
Changes from v1:
* fixed the patch tags and some style issues
* reworked the patch so that it is both easier to backport and also
  more efficient (basing on suggestions received during v1 review)
---
This is necessary to completely fix the bug that was described in and
addressed by 07b0eb5d0ef0 ("credit2: make sure we pick a runnable unit
from the runq if there is one").

It should, therefore, be backported and applied to all the branches to
which that commit has been. Such backporting should be straigthforward
to do, at least until 4.13.

I will provide the backports myself in a email that I'll send as a
reply to this one.

For 4.12 and earlier, it's slightly trickier, but the fix is still necessary.
Actually, both 07b0eb5d0ef0 and this patch should be backported to that
branch(es).

Of course, there's no official support (except for security fixes) any longer
for 4.12 and earlier, so no one should expect that the patch will be applied
by Xen's stable maintainers. Nevertheless, I'll provide at least the backports
to 4.12, in my email, so that if there are users or, in general, downstreams
that are still using these codebases, they can pick them up and apply them
by themselves.

Regards,
Dario
---
 xen/common/sched/credit2.c |   32 +++++++++++++++++++++++++-------
 1 file changed, 25 insertions(+), 7 deletions(-)

diff --git a/xen/common/sched/credit2.c b/xen/common/sched/credit2.c
index ebb09ea43a..46c4f6a251 100644
--- a/xen/common/sched/credit2.c
+++ b/xen/common/sched/credit2.c
@@ -3463,6 +3463,15 @@ runq_candidate(struct csched2_runqueue_data *rqd,
                         (unsigned char *)&d);
         }
 
+        /*
+         * If the unit in the runqueue has more credits than current (or than
+         * idle, if current is not runnable) or if current is yielding, we may
+         * want to pick it up. Otherwise, there's no need to keep scanning the
+         * runqueue any further.
+         */
+        if ( !yield && svc->credit <= snext->credit )
+            break;
+
         /* Skip non runnable units that we (temporarily) have in the runq */
         if ( unlikely(!unit_runnable_state(svc->unit)) )
             continue;
@@ -3494,16 +3503,25 @@ runq_candidate(struct csched2_runqueue_data *rqd,
         }
 
         /*
-         * If the one in the runqueue has more credit than current (or idle,
-         * if current is not runnable), or if current is yielding, and also
-         * if the one in runqueue either is not capped, or is capped but has
-         * some budget, then choose it.
+         * If we are here, we are almost sure we want to pick the unit in
+         * the runqueue. Last thing we need to check is that it either is
+         * not capped or, if it is, it has some budget.
+         *
+         * Note that budget availability must be the very last check that
+         * we, in this loop, due to the side effects that unit_grab_budget().
+         * causes.
+         *
+         * In fact, if there is budget available in the unit's domain's
+         * budget pool, the function will pick some for running this unit.
+         * And we clearly want to do that only if we're otherwise sure that
+         * the unit will actually run, consume it, and return the leftover
+         * (if any) in the usual way.
          */
-        if ( (yield || svc->credit > snext->credit) &&
-             (!has_cap(svc) || unit_grab_budget(svc)) )
-            snext = svc;
+        if ( has_cap(svc) && !unit_grab_budget(svc) )
+            continue;
 
         /* In any case, if we got this far, break. */
+        snext = svc;
         break;
     }
 

On 04.08.2021 19:55, Dario Faggioli wrote:
> Commit 07b0eb5d0ef0 ("credit2: make sure we pick a runnable unit from the
> runq if there is one") did not fix completely the problem of potentially
> selecting a scheduling unit that will then not be able to run.
> 
> In fact, in case caps are used and the unit we are currently looking
> at, during the runqueue scan, does not have enough budget for being run,
> we should continue looking instead than giving up and picking the idle
> unit.
> 
> Suggested-by: George Dunlap <george.dunlap@citrix.com>
> Signed-off-by: Dario Faggioli <dfaggioli@suse.com>

In part based on your explanation in response to my v1 comments:
Reviewed-by: Jan Beulich <jbeulich@suse.com>
with one nit:

> @@ -3494,16 +3503,25 @@ runq_candidate(struct csched2_runqueue_data *rqd,
>          }
>  
>          /*
> -         * If the one in the runqueue has more credit than current (or idle,
> -         * if current is not runnable), or if current is yielding, and also
> -         * if the one in runqueue either is not capped, or is capped but has
> -         * some budget, then choose it.
> +         * If we are here, we are almost sure we want to pick the unit in
> +         * the runqueue. Last thing we need to check is that it either is
> +         * not capped or, if it is, it has some budget.
> +         *
> +         * Note that budget availability must be the very last check that
> +         * we, in this loop, due to the side effects that unit_grab_budget().
> +         * causes.

The sentence looks broken to me: I think you either want to delete "that
we," or add "do" before the 1st or after the 2nd comma. If you agree, or
if you have another suggestion, I'd be happy to apply the adjustment
(let me know of your preference, if any) while committing.

Jan

On Thu, 2021-08-05 at 08:31 +0200, Jan Beulich wrote:
> On 04.08.2021 19:55, Dario Faggioli wrote:
> > 
> > Suggested-by: George Dunlap <george.dunlap@citrix.com>
> > Signed-off-by: Dario Faggioli <dfaggioli@suse.com>
> 
> In part based on your explanation in response to my v1 comments:
> Reviewed-by: Jan Beulich <jbeulich@suse.com>
>
Cool! Thank you very much again.

> > @@ -3494,16 +3503,25 @@ runq_candidate(struct csched2_runqueue_data
> > *rqd,
> > 
> > +         * Note that budget availability must be the very last
> > check that
> > +         * we, in this loop, due to the side effects that
> > unit_grab_budget().
> > +         * causes.
> 
> The sentence looks broken to me: I think you either want to delete
> "that
> we," or add "do" before the 1st or after the 2nd comma. If you agree,
> or
> if you have another suggestion, I'd be happy to apply the adjustment
> (let me know of your preference, if any) while committing.
> 
Yes, absolutely!

Also, I am fine with either of the two variants you propose (adding a
"do" is what I slightly prefer, but it really is the same), and I am
fine with this being done when committing.

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)