pkt_sched: sch_qfq: properly cap timestamps in charge_actual_service
authorPaolo Valente <paolo.valente@unimore.it>
Tue, 5 Mar 2013 08:04:57 +0000 (08:04 +0000)
committerDavid S. Miller <davem@davemloft.net>
Wed, 6 Mar 2013 07:47:05 +0000 (02:47 -0500)
commit9b99b7e90bf5cd9a88823c49574ba80d92a98262
tree8ec812a0bd4a5848722470d5ec21b784c127ee75
parentf74861ca87264e594e0134e8ac14db06be77fe6f
pkt_sched: sch_qfq: properly cap timestamps in charge_actual_service

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: Paolo Valente <paolo.valente@unimore.it>
Reviewed-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/sched/sch_qfq.c