• Paolo Valente's avatar
    pkt_sched: sch_qfq: properly cap timestamps in charge_actual_service · 9b99b7e9
    Paolo Valente authored
    QFQ+ schedules the active aggregates in a group using a bucket list
    (one list per group). The bucket in which each aggregate is inserted
    depends on the aggregate's timestamps, and the number
    of buckets in a group is enough to accomodate the possible (range of)
    values of the timestamps of all the aggregates in the group. For this
    property to hold, timestamps must however be computed correctly.  One
    necessary condition for computing timestamps correctly is that the
    number of bits dequeued for each aggregate, while the aggregate is in
    service, does not exceed the maximum budget budgetmax assigned to the
    aggregate.
    
    For each aggregate, budgetmax is proportional to the number of classes
    in the aggregate. If the number of classes of the aggregate is
    decreased through qfq_change_class(), then budgetmax is decreased
    automatically as well.  Problems may occur if the aggregate is in
    service when budgetmax is decreased, because the current remaining
    budget of the aggregate and/or the service already received by the
    aggregate may happen to be larger than the new value of budgetmax.  In
    this case, when the aggregate is eventually deselected and its
    timestamps are updated, the aggregate may happen to have received an
    amount of service larger than budgetmax.  This may cause the aggregate
    to be assigned a higher virtual finish time than the maximum
    acceptable value for the last bucket in the bucket list of the group.
    
    This fix introduces a cap that addresses this issue.
    Signed-off-by: default avatarPaolo Valente <paolo.valente@unimore.it>
    Reviewed-by: default avatarFabio Checconi <fchecconi@gmail.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    9b99b7e9
sch_qfq.c 40.6 KB