• Paolo Valente's avatar
    block, bfq: guarantee update_next_in_service always returns an eligible entity · 24d90bb2
    Paolo Valente authored
    If the function bfq_update_next_in_service is invoked as a consequence
    of the activation or requeueing of an entity, say E, then it doesn't
    invoke bfq_lookup_next_entity to get the next-in-service entity. In
    contrast, it follows a shorter path: if E happens to be eligible (see
    commit "bfq-sq-mq: make lookup_next_entity push up vtime on
    expirations" for details on eligibility) and to have a lower virtual
    finish time than the current candidate as next-in-service entity, then
    E directly becomes the next-in-service entity. Unfortunately, there is
    a corner case for which this shorter path makes
    bfq_update_next_in_service choose a non eligible entity: it occurs if
    both E and the current next-in-service entity happen to be non
    eligible when bfq_update_next_in_service is invoked. In this case, E
    is not set as next-in-service, and, since bfq_lookup_next_entity is
    not invoked, the state of the parent entity is not updated so as to
    end up with an eligible entity as the proper next-in-service entity.
    
    In this respect, next-in-service is actually allowed to be non
    eligible while some queue is in service: since no system-virtual-time
    push-up can be performed in that case (see again commit "bfq-sq-mq:
    make lookup_next_entity push up vtime on expirations" for details),
    next-in-service is chosen, speculatively, as a function of the
    possible value that the system virtual time may get after a push
    up. But the correctness of the schedule breaks if next-in-service is
    still a non eligible entity when it is time to set in service the next
    entity. Unfortunately, this may happen in the above corner case.
    
    This commit fixes this problem by making bfq_update_next_in_service
    invoke bfq_lookup_next_entity not only if the above shorter path
    cannot be taken, but also if the shorter path is taken but fails to
    yield an eligible next-in-service entity.
    Signed-off-by: 's avatarPaolo Valente <paolo.valente@linaro.org>
    Tested-by: 's avatarLee Tibbert <lee.tibbert@gmail.com>
    Tested-by: 's avatarOleksandr Natalenko <oleksandr@natalenko.name>
    Signed-off-by: 's avatarJens Axboe <axboe@kernel.dk>
    24d90bb2