net/sched/sch_qfq.c

27     http://algo.ing.unimo.it/people/paolo/agg-sched/agg-sched.pdf
138 	struct qfq_aggregate *agg;	/* Parent aggregate. */
257 static void qfq_init_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
260 	INIT_LIST_HEAD(&agg->active);
261 	hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);
263 	agg->lmax = lmax;
264 	agg->class_weight = weight;
270 	struct qfq_aggregate *agg;
272 	hlist_for_each_entry(agg, &q->nonfull_aggs, nonfull_next)
273 		if (agg->lmax == lmax && agg->class_weight == weight)
274 			return agg;
281 static void qfq_update_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
287 		hlist_del_init(&agg->nonfull_next);
289 	if (agg->num_classes > new_num_classes &&
290 	    new_num_classes == q->max_agg_classes - 1) /* agg no more full */
291 		hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);
294 	 * agg->initial_budget > agg->budgetmax
297 	agg->budgetmax = new_num_classes * agg->lmax;
298 	new_agg_weight = agg->class_weight * new_num_classes;
299 	agg->inv_w = ONE_FP/new_agg_weight;
301 	if (agg->grp == NULL) {
302 		int i = qfq_calc_index(agg->inv_w, agg->budgetmax,
304 		agg->grp = &q->groups[i];
308 		(int) agg->class_weight * (new_num_classes - agg->num_classes);
311 	agg->num_classes = new_num_classes;
316 			   struct qfq_aggregate *agg,
319 	cl->agg = agg;
321 	qfq_update_agg(q, agg, agg->num_classes+1);
323 		list_add_tail(&cl->alist, &agg->active);
324 		if (list_first_entry(&agg->active, struct qfq_class, alist) ==
325 		    cl && q->in_serv_agg != agg) /* agg was inactive */
326 			qfq_activate_agg(q, agg, enqueue); /* schedule agg */
332 static void qfq_destroy_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
334 	hlist_del_init(&agg->nonfull_next);
335 	q->wsum -= agg->class_weight;
339 	if (q->in_serv_agg == agg)
341 	kfree(agg);
347 	struct qfq_aggregate *agg = cl->agg;
351 	if (list_empty(&agg->active)) /* agg is now inactive */
352 		qfq_deactivate_agg(q, agg);
358 	struct qfq_aggregate *agg = cl->agg;
360 	cl->agg = NULL;
361 	if (agg->num_classes == 1) { /* agg being emptied, destroy it */
362 		qfq_destroy_agg(q, agg);
365 	qfq_update_agg(q, agg, agg->num_classes-1);
445 	    lmax == cl->agg->lmax &&
446 	    weight == cl->agg->class_weight)
449 	delta_w = weight - (cl ? cl->agg->class_weight : 0);
633 	if (nla_put_u32(skb, TCA_QFQ_WEIGHT, cl->agg->class_weight) ||
634 	    nla_put_u32(skb, TCA_QFQ_LMAX, cl->agg->lmax))
651 	xstats.weight = cl->agg->class_weight;
652 	xstats.lmax = cl->agg->lmax;
825  * The index of the slot in which the input aggregate agg is to be
834  * happens to postpone the service of agg unjustly, i.e., it never
838  * the timestamps of agg are low enough that the slot index is never
840  * guarantee if it happens to unjustly postpone the service of agg, or
850  * the timestamps of agg, if needed, so as to guarantee that the slot
854  * fact, in case of no out-of-order service, the timestamps of agg
859  * however waited for the service of agg before being served.
862  * for agg is a recent change of the parameters of some class. If the
879 static void qfq_slot_insert(struct qfq_group *grp, struct qfq_aggregate *agg,
888 		agg->S -= deltaS;
889 		agg->F -= deltaS;
895 	hlist_add_head(&agg->next, &grp->slots[i]);
911 	struct qfq_aggregate *agg = qfq_slot_head(grp);
913 	BUG_ON(!agg);
914 	hlist_del(&agg->next);
977 static struct sk_buff *agg_dequeue(struct qfq_aggregate *agg,
990 		cl->deficit += agg->lmax;
991 		list_move_tail(&cl->alist, &agg->active);
997 static inline struct sk_buff *qfq_peek_skb(struct qfq_aggregate *agg,
1003 	*cl = list_first_entry(&agg->active, struct qfq_class, alist);
1014 static inline void charge_actual_service(struct qfq_aggregate *agg)
1018 	 * agg, it may happen that
1019 	 * agg->initial_budget - agg->budget > agg->bugdetmax
1021 	u32 service_received = min(agg->budgetmax,
1022 				   agg->initial_budget - agg->budget);
1024 	agg->F = agg->S + (u64)service_received * agg->inv_w;
1039 static void qfq_update_start(struct qfq_sched *q, struct qfq_aggregate *agg)
1043 	int slot_shift = agg->grp->slot_shift;
1045 	roundedF = qfq_round_down(agg->F, slot_shift);
1048 	if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) {
1050 		mask = mask_from(q->bitmaps[ER], agg->grp->index);
1055 					agg->S = next->F;
1057 					agg->S = limit;
1061 		agg->S = q->V;
1063 		agg->S = agg->F;
1066 /* Update the timestamps of agg before scheduling/rescheduling it for
1067  * service.  In particular, assign to agg->F its maximum possible
1073 		    struct qfq_aggregate *agg, enum update_reason reason)
1076 		qfq_update_start(q, agg);
1077 	else /* just charge agg for the service received */
1078 		agg->S = agg->F;
1080 	agg->F = agg->S + (u64)agg->budgetmax * agg->inv_w;
1083 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg);
1091 	/* next-packet len, 0 means no more active classes in in-service agg */
1172 	struct qfq_aggregate *agg, *new_front_agg;
1184 	agg = qfq_slot_head(grp);
1186 	/* agg starts to be served, remove it from schedule */
1199 			return agg;
1209 	return agg;
1218 	struct qfq_aggregate *agg;
1231 	if (unlikely(cl->agg->lmax < len)) {
1233 			 cl->agg->lmax, len, cl->common.classid);
1234 		err = qfq_change_agg(sch, cl, cl->agg->class_weight, len);
1257 	agg = cl->agg;
1261 		    list_first_entry(&agg->active, struct qfq_class, alist)
1263 			list_move_tail(&cl->alist, &agg->active);
1269 	cl->deficit = agg->lmax;
1270 	list_add_tail(&cl->alist, &agg->active);
1272 	if (list_first_entry(&agg->active, struct qfq_class, alist) != cl ||
1273 	    q->in_serv_agg == agg)
1276 	qfq_activate_agg(q, agg, enqueue);
1284 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
1286 	struct qfq_group *grp = agg->grp;
1290 	roundedS = qfq_round_down(agg->S, grp->slot_shift);
1293 	 * Insert agg in the correct bucket.
1294 	 * If agg->S >= grp->S we don't need to adjust the
1302 		if (!qfq_gt(grp->S, agg->S))
1305 		/* create a slot for this agg->S */
1321 		 (unsigned long long) agg->S,
1322 		 (unsigned long long) agg->F,
1326 	qfq_slot_insert(grp, agg, roundedS);
1330 /* Update agg ts and schedule agg for service */
1331 static void qfq_activate_agg(struct qfq_sched *q, struct qfq_aggregate *agg,
1334 	agg->initial_budget = agg->budget = agg->budgetmax; /* recharge budg. */
1336 	qfq_update_agg_ts(q, agg, reason);
1338 		q->in_serv_agg = agg; /* start serving this aggregate */
1339 		 /* update V: to be in service, agg must be eligible */
1340 		q->oldV = q->V = agg->S;
1341 	} else if (agg != q->in_serv_agg)
1342 		qfq_schedule_agg(q, agg);
1346 			    struct qfq_aggregate *agg)
1351 	roundedS = qfq_round_down(agg->S, grp->slot_shift);
1356 	hlist_del(&agg->next);
1368 static void qfq_deactivate_agg(struct qfq_sched *q, struct qfq_aggregate *agg)
1370 	struct qfq_group *grp = agg->grp;
1375 	if (agg == q->in_serv_agg) {
1376 		charge_actual_service(agg);
1381 	agg->F = agg->S;
1382 	qfq_slot_remove(q, grp, agg);
1401 		agg = qfq_slot_scan(grp);
1402 		roundedS = qfq_round_down(agg->S, grp->slot_shift);