If the running tasks for a service are not well balanced across the
placement-preference tree, the task scheduler could enter an infinite
loop when scaling the service up. The scheduleNTasksOnSubtree loop
terminates when either all tasks have been scheduled onto nodes, or the
nodes in all subtrees are out of room to accept new tasks. The trouble
is that the algorithm only considers a subtree to be out of room if an
attempt was made to schedule tasks onto its nodes but not all tasks were
scheduled. Subtrees with more tasks already running than the desired
number of tasks for a balanced tree are skipped over without attempting
to assign any tasks, so do not have a chance to be considered out of
room. The scheduler will therefore enter a tight infinite loop when
there exists a node of the placement-preferences tree in which at least
one subtree has more tasks running than desired, and all other subtrees
are out of room for more tasks.

It would be incorrect to consider a subtree as out of room just because
there are more tasks running than desired at a particular iteration of
the scheduling loop. The desired number of tasks to assign changes as
the scheduler iteratively schedules tasks and other subtrees run out of
room, so it is possible for a subtree to become eligible in a future
iteration.

Add a third condition to the task scheduler loop. Make it so the loop
exits if there are no subtrees which are eligible for task scheduling,
whether due to being out of room or have more tasks running than
desired.

Co-authored-by: Xinfeng Liu <[email protected]>
Signed-off-by: Cory Snider <[email protected]>

…inite-loop

manager: fix task scheduler infinite loop