1. 29 Jul, 2017 1 commit
    • Paolo Valente's avatar
      block, bfq: reset in_service_entity if it becomes idle · 6ab1d8da
      Paolo Valente authored
      BFQ implements hierarchical scheduling by representing each group of
      queues with a generic parent entity. For each parent entity, BFQ
      maintains an in_service_entity pointer: if one of the child entities
      happens to be in service, in_service_entity points to it.  The
      resetting of these pointers happens only on queue expirations: when
      the in-service queue is expired, i.e., stops to be the queue in
      service, BFQ resets all in_service_entity pointers along the
      parent-entity path from this queue to the root entity.
      
      Functions handling the scheduling of entities assume, naturally, that
      in-service entities are active, i.e., have pending I/O requests (or,
      as a special case, even if they have no pending requests, they are
      expected to receive a new request very soon, with the scheduler idling
      the storage device while waiting for such an event). Unfortunately,
      the above resetting scheme of the in_service_entity pointers may cause
      this assumption to be violated.  For example, the in-service queue may
      happen to remain without requests because of a request merge. In this
      case the queue does become idle, and all related data structures are
      updated accordingly. But in_service_entity still points to the queue
      in the parent entity. This inconsistency may even propagate to
      higher-level parent entities, if they happen to become idle as well,
      as a consequence of the leaf queue becoming idle. For this queue and
      parent entities, scheduling functions have an undefined behaviour,
      and, as reported, may easily lead to kernel crashes or hangs.
      
      This commit addresses this issue by simply resetting the
      in_service_entity field also when it is detected to point to an entity
      becoming idle (regardless of why the entity becomes idle).
      Reported-by: default avatarLaurentiu Nicola <lnicola@dend.ro>
      Signed-off-by: default avatarPaolo Valente <paolo.valente@linaro.org>
      Tested-by: default avatarLaurentiu Nicola <lnicola@dend.ro>
      Signed-off-by: default avatarJens Axboe <axboe@kernel.dk>
      6ab1d8da
  2. 12 Jul, 2017 1 commit
  3. 03 Jul, 2017 1 commit
    • Paolo Valente's avatar
      block, bfq: don't change ioprio class for a bfq_queue on a service tree · 431b17f9
      Paolo Valente authored
      On each deactivation or re-scheduling (after being served) of a
      bfq_queue, BFQ invokes the function __bfq_entity_update_weight_prio(),
      to perform pending updates of ioprio, weight and ioprio class for the
      bfq_queue. BFQ also invokes this function on I/O-request dispatches,
      to raise or lower weights more quickly when needed, thereby improving
      latency. However, the entity representing the bfq_queue may be on the
      active (sub)tree of a service tree when this happens, and, although
      with a very low probability, the bfq_queue may happen to also have a
      pending change of its ioprio class. If both conditions hold when
      __bfq_entity_update_weight_prio() is invoked, then the entity moves to
      a sort of hybrid state: the new service tree for the entity, as
      returned by bfq_entity_service_tree(), differs from service tree on
      which the entity still is. The functions that handle activations and
      deactivations of entities do not cope with such a hybrid state (and
      would need to become more complex to cope).
      
      This commit addresses this issue by just making
      __bfq_entity_update_weight_prio() not perform also a possible pending
      change of ioprio class, when invoked on an I/O-request dispatch for a
      bfq_queue. Such a change is thus postponed to when
      __bfq_entity_update_weight_prio() is invoked on deactivation or
      re-scheduling of the bfq_queue.
      Reported-by: default avatarMarco Piazza <mpiazza@gmail.com>
      Reported-by: default avatarLaurentiu Nicola <lnicola@dend.ro>
      Signed-off-by: default avatarPaolo Valente <paolo.valente@linaro.org>
      Tested-by: default avatarMarco Piazza <mpiazza@gmail.com>
      Signed-off-by: default avatarJens Axboe <axboe@kernel.dk>
      431b17f9
  4. 10 May, 2017 1 commit
  5. 19 Apr, 2017 1 commit
    • Paolo Valente's avatar
      block, bfq: split bfq-iosched.c into multiple source files · ea25da48
      Paolo Valente authored
      The BFQ I/O scheduler features an optimal fair-queuing
      (proportional-share) scheduling algorithm, enriched with several
      mechanisms to boost throughput and reduce latency for interactive and
      real-time applications. This makes BFQ a large and complex piece of
      code. This commit addresses this issue by splitting BFQ into three
      main, independent components, and by moving each component into a
      separate source file:
      1. Main algorithm: handles the interaction with the kernel, and
      decides which requests to dispatch; it uses the following two further
      components to achieve its goals.
      2. Scheduling engine (Hierarchical B-WF2Q+ scheduling algorithm):
      computes the schedule, using weights and budgets provided by the above
      component.
      3. cgroups support: handles group operations (creation, destruction,
      move, ...).
      Signed-off-by: default avatarPaolo Valente <paolo.valente@linaro.org>
      Signed-off-by: default avatarJens Axboe <axboe@fb.com>
      ea25da48