211 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_find_class()  local
214 	clc = qdisc_class_find(&q->clhash, classid);  in qfq_find_class()
222 	unsigned int len = cl->qdisc->q.qlen;  in qfq_purge_queue()
265 static void qfq_init_agg(struct qfq_sched *q, struct qfq_aggregate *agg,  in qfq_init_agg()  argument
269 	hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);  in qfq_init_agg()
275 static struct qfq_aggregate *qfq_find_agg(struct qfq_sched *q,  in qfq_find_agg()  argument
280 	hlist_for_each_entry(agg, &q->nonfull_aggs, nonfull_next)  in qfq_find_agg()
289 static void qfq_update_agg(struct qfq_sched *q, struct qfq_aggregate *agg,  in qfq_update_agg()  argument
294 	if (new_num_classes == q->max_agg_classes)  in qfq_update_agg()
298 	    new_num_classes == q->max_agg_classes - 1) /* agg no more full */  in qfq_update_agg()
299 		hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);  in qfq_update_agg()
311 				       q->min_slot_shift);  in qfq_update_agg()
312 		agg->grp = &q->groups[i];  in qfq_update_agg()
315 	q->wsum +=  in qfq_update_agg()
317 	q->iwsum = ONE_FP / q->wsum;  in qfq_update_agg()
323 static void qfq_add_to_agg(struct qfq_sched *q,  in qfq_add_to_agg()  argument
329 	qfq_update_agg(q, agg, agg->num_classes+1);  in qfq_add_to_agg()
330 	if (cl->qdisc->q.qlen > 0) { /* adding an active class */  in qfq_add_to_agg()
333 		    cl && q->in_serv_agg != agg) /* agg was inactive */  in qfq_add_to_agg()
334 			qfq_activate_agg(q, agg, enqueue); /* schedule agg */  in qfq_add_to_agg()
340 static void qfq_destroy_agg(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_destroy_agg()  argument
343 	q->wsum -= agg->class_weight;  in qfq_destroy_agg()
344 	if (q->wsum != 0)  in qfq_destroy_agg()
345 		q->iwsum = ONE_FP / q->wsum;  in qfq_destroy_agg()
347 	if (q->in_serv_agg == agg)  in qfq_destroy_agg()
348 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_destroy_agg()
353 static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl)  in qfq_deactivate_class()  argument
360 		qfq_deactivate_agg(q, agg);  in qfq_deactivate_class()
364 static void qfq_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)  in qfq_rm_from_agg()  argument
370 		qfq_destroy_agg(q, agg);  in qfq_rm_from_agg()
373 	qfq_update_agg(q, agg, agg->num_classes-1);  in qfq_rm_from_agg()
377 static void qfq_deact_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)  in qfq_deact_rm_from_agg()  argument
379 	if (cl->qdisc->q.qlen > 0) /* class is active */  in qfq_deact_rm_from_agg()
380 		qfq_deactivate_class(q, cl);  in qfq_deact_rm_from_agg()
382 	qfq_rm_from_agg(q, cl);  in qfq_deact_rm_from_agg()
389 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_change_agg()  local
390 	struct qfq_aggregate *new_agg = qfq_find_agg(q, lmax, weight);  in qfq_change_agg()
396 		qfq_init_agg(q, new_agg, lmax, weight);  in qfq_change_agg()
398 	qfq_deact_rm_from_agg(q, cl);  in qfq_change_agg()
399 	qfq_add_to_agg(q, new_agg, cl);  in qfq_change_agg()
407 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_change_class()  local
453 	if (q->wsum + delta_w > QFQ_MAX_WSUM) {  in qfq_change_class()
455 			  delta_w, q->wsum);  in qfq_change_class()
496 	qdisc_class_hash_insert(&q->clhash, &cl->common);  in qfq_change_class()
499 	qdisc_class_hash_grow(sch, &q->clhash);  in qfq_change_class()
503 	new_agg = qfq_find_agg(q, lmax, weight);  in qfq_change_class()
513 		qfq_init_agg(q, new_agg, lmax, weight);  in qfq_change_class()
516 		qfq_deact_rm_from_agg(q, cl);  in qfq_change_class()
517 	qfq_add_to_agg(q, new_agg, cl);  in qfq_change_class()
531 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_destroy_class()  local
533 	qfq_rm_from_agg(q, cl);  in qfq_destroy_class()
541 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_delete_class()  local
550 	qdisc_class_hash_remove(&q->clhash, &cl->common);  in qfq_delete_class()
583 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_tcf_chain()  local
588 	return &q->filter_list;  in qfq_tcf_chain()
669 				  &cl->qdisc->qstats, cl->qdisc->q.qlen) < 0)  in qfq_dump_class_stats()
677 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_walk()  local
684 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_walk()
685 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_walk()
702 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_classify()  local
716 	fl = rcu_dereference_bh(q->filter_list);  in qfq_classify()
750 static inline struct qfq_group *qfq_ffs(struct qfq_sched *q,  in qfq_ffs()  argument
754 	return &q->groups[index];  in qfq_ffs()
767 static int qfq_calc_state(struct qfq_sched *q, const struct qfq_group *grp)  in qfq_calc_state()  argument
770 	unsigned int state = qfq_gt(grp->S, q->V);  in qfq_calc_state()
771 	unsigned long mask = mask_from(q->bitmaps[ER], grp->index);  in qfq_calc_state()
775 		next = qfq_ffs(q, mask);  in qfq_calc_state()
790 static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask,  in qfq_move_groups()  argument
793 	q->bitmaps[dst] |= q->bitmaps[src] & mask;  in qfq_move_groups()
794 	q->bitmaps[src] &= ~mask;  in qfq_move_groups()
797 static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)  in qfq_unblock_groups()  argument
799 	unsigned long mask = mask_from(q->bitmaps[ER], index + 1);  in qfq_unblock_groups()
803 		next = qfq_ffs(q, mask);  in qfq_unblock_groups()
809 	qfq_move_groups(q, mask, EB, ER);  in qfq_unblock_groups()
810 	qfq_move_groups(q, mask, IB, IR);  in qfq_unblock_groups()
823 static void qfq_make_eligible(struct qfq_sched *q)  in qfq_make_eligible()  argument
825 	unsigned long vslot = q->V >> q->min_slot_shift;  in qfq_make_eligible()
826 	unsigned long old_vslot = q->oldV >> q->min_slot_shift;  in qfq_make_eligible()
837 		qfq_move_groups(q, mask, IR, ER);  in qfq_make_eligible()
838 		qfq_move_groups(q, mask, IB, EB);  in qfq_make_eligible()
978 static void qfq_update_eligible(struct qfq_sched *q)  in qfq_update_eligible()  argument
983 	ineligible = q->bitmaps[IR] | q->bitmaps[IB];  in qfq_update_eligible()
985 		if (!q->bitmaps[ER]) {  in qfq_update_eligible()
986 			grp = qfq_ffs(q, ineligible);  in qfq_update_eligible()
987 			if (qfq_gt(grp->S, q->V))  in qfq_update_eligible()
988 				q->V = grp->S;  in qfq_update_eligible()
990 		qfq_make_eligible(q);  in qfq_update_eligible()
1002 	if (cl->qdisc->q.qlen == 0) /* no more packets, remove from list */  in agg_dequeue()
1052 static void qfq_update_start(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_update_start()  argument
1059 	limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift);  in qfq_update_start()
1061 	if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) {  in qfq_update_start()
1063 		mask = mask_from(q->bitmaps[ER], agg->grp->index);  in qfq_update_start()
1065 			struct qfq_group *next = qfq_ffs(q, mask);  in qfq_update_start()
1074 		agg->S = q->V;  in qfq_update_start()
1085 qfq_update_agg_ts(struct qfq_sched *q,  in qfq_update_agg_ts()  argument
1089 		qfq_update_start(q, agg);  in qfq_update_agg_ts()
1096 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg);
1100 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_dequeue()  local
1101 	struct qfq_aggregate *in_serv_agg = q->in_serv_agg;  in qfq_dequeue()
1136 			qfq_update_agg_ts(q, in_serv_agg, requeue);  in qfq_dequeue()
1137 			qfq_schedule_agg(q, in_serv_agg);  in qfq_dequeue()
1138 		} else if (sch->q.qlen == 0) { /* no aggregate to serve */  in qfq_dequeue()
1139 			q->in_serv_agg = NULL;  in qfq_dequeue()
1147 		in_serv_agg = q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_dequeue()
1153 	sch->q.qlen--;  in qfq_dequeue()
1166 	q->V += (u64)len * q->iwsum;  in qfq_dequeue()
1169 		 (unsigned long long) q->V);  in qfq_dequeue()
1174 static struct qfq_aggregate *qfq_choose_next_agg(struct qfq_sched *q)  in qfq_choose_next_agg()  argument
1180 	qfq_update_eligible(q);  in qfq_choose_next_agg()
1181 	q->oldV = q->V;  in qfq_choose_next_agg()
1183 	if (!q->bitmaps[ER])  in qfq_choose_next_agg()
1186 	grp = qfq_ffs(q, q->bitmaps[ER]);  in qfq_choose_next_agg()
1197 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1207 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1208 		s = qfq_calc_state(q, grp);  in qfq_choose_next_agg()
1209 		__set_bit(grp->index, &q->bitmaps[s]);  in qfq_choose_next_agg()
1212 	qfq_unblock_groups(q, grp->index, old_F);  in qfq_choose_next_agg()
1219 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_enqueue()  local
1253 	++sch->q.qlen;  in qfq_enqueue()
1257 	if (cl->qdisc->q.qlen != 1) {  in qfq_enqueue()
1271 	    q->in_serv_agg == agg)  in qfq_enqueue()
1274 	qfq_activate_agg(q, agg, enqueue);  in qfq_enqueue()
1282 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_schedule_agg()  argument
1306 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_schedule_agg()
1307 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_schedule_agg()
1308 	} else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V) &&  in qfq_schedule_agg()
1309 		   q->in_serv_agg == NULL)  in qfq_schedule_agg()
1310 		q->V = roundedS;  in qfq_schedule_agg()
1314 	s = qfq_calc_state(q, grp);  in qfq_schedule_agg()
1315 	__set_bit(grp->index, &q->bitmaps[s]);  in qfq_schedule_agg()
1318 		 s, q->bitmaps[s],  in qfq_schedule_agg()
1321 		 (unsigned long long) q->V);  in qfq_schedule_agg()
1329 static void qfq_activate_agg(struct qfq_sched *q, struct qfq_aggregate *agg,  in qfq_activate_agg()  argument
1334 	qfq_update_agg_ts(q, agg, reason);  in qfq_activate_agg()
1335 	if (q->in_serv_agg == NULL) { /* no aggr. in service or scheduled */  in qfq_activate_agg()
1336 		q->in_serv_agg = agg; /* start serving this aggregate */  in qfq_activate_agg()
1338 		q->oldV = q->V = agg->S;  in qfq_activate_agg()
1339 	} else if (agg != q->in_serv_agg)  in qfq_activate_agg()
1340 		qfq_schedule_agg(q, agg);  in qfq_activate_agg()
1343 static void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,  in qfq_slot_remove()  argument
1366 static void qfq_deactivate_agg(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_deactivate_agg()  argument
1373 	if (agg == q->in_serv_agg) {  in qfq_deactivate_agg()
1375 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_deactivate_agg()
1380 	qfq_slot_remove(q, grp, agg);  in qfq_deactivate_agg()
1383 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1384 		__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1385 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1387 		if (test_bit(grp->index, &q->bitmaps[ER]) &&  in qfq_deactivate_agg()
1388 		    !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {  in qfq_deactivate_agg()
1389 			mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);  in qfq_deactivate_agg()
1394 			qfq_move_groups(q, mask, EB, ER);  in qfq_deactivate_agg()
1395 			qfq_move_groups(q, mask, IB, IR);  in qfq_deactivate_agg()
1397 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1402 			__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1403 			__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1404 			__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1405 			__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1408 			s = qfq_calc_state(q, grp);  in qfq_deactivate_agg()
1409 			__set_bit(grp->index, &q->bitmaps[s]);  in qfq_deactivate_agg()
1416 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_qlen_notify()  local
1419 	if (cl->qdisc->q.qlen == 0)  in qfq_qlen_notify()
1420 		qfq_deactivate_class(q, cl);  in qfq_qlen_notify()
1423 static unsigned int qfq_drop_from_slot(struct qfq_sched *q,  in qfq_drop_from_slot()  argument
1438 				if (cl->qdisc->q.qlen == 0)  in qfq_drop_from_slot()
1439 					qfq_deactivate_class(q, cl);  in qfq_drop_from_slot()
1450 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_drop()  local
1455 		grp = &q->groups[i];  in qfq_drop()
1457 			len = qfq_drop_from_slot(q, &grp->slots[j]);  in qfq_drop()
1459 				sch->q.qlen--;  in qfq_drop()
1471 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_init_qdisc()  local
1476 	err = qdisc_class_hash_init(&q->clhash);  in qfq_init_qdisc()
1486 	q->max_agg_classes = 1<<max_cl_shift;  in qfq_init_qdisc()
1490 	q->min_slot_shift = FRAC_BITS + maxbudg_shift - QFQ_MAX_INDEX;  in qfq_init_qdisc()
1493 		grp = &q->groups[i];  in qfq_init_qdisc()
1495 		grp->slot_shift = q->min_slot_shift + i;  in qfq_init_qdisc()
1500 	INIT_HLIST_HEAD(&q->nonfull_aggs);  in qfq_init_qdisc()
1507 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_reset_qdisc()  local
1511 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_reset_qdisc()
1512 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_reset_qdisc()
1513 			if (cl->qdisc->q.qlen > 0)  in qfq_reset_qdisc()
1514 				qfq_deactivate_class(q, cl);  in qfq_reset_qdisc()
1519 	sch->q.qlen = 0;  in qfq_reset_qdisc()
1524 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_destroy_qdisc()  local
1529 	tcf_destroy_chain(&q->filter_list);  in qfq_destroy_qdisc()
1531 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_destroy_qdisc()
1532 		hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],  in qfq_destroy_qdisc()
1537 	qdisc_class_hash_destroy(&q->clhash);  in qfq_destroy_qdisc()