212 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_find_class()  local
215 	clc = qdisc_class_find(&q->clhash, classid);  in qfq_find_class()
223 	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
344 	q->wsum -= agg->class_weight;  in qfq_destroy_agg()
345 	if (q->wsum != 0)  in qfq_destroy_agg()
346 		q->iwsum = ONE_FP / q->wsum;  in qfq_destroy_agg()
348 	if (q->in_serv_agg == agg)  in qfq_destroy_agg()
349 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_destroy_agg()
354 static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl)  in qfq_deactivate_class()  argument
361 		qfq_deactivate_agg(q, agg);  in qfq_deactivate_class()
365 static void qfq_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)  in qfq_rm_from_agg()  argument
371 		qfq_destroy_agg(q, agg);  in qfq_rm_from_agg()
374 	qfq_update_agg(q, agg, agg->num_classes-1);  in qfq_rm_from_agg()
378 static void qfq_deact_rm_from_agg(struct qfq_sched *q, struct qfq_class *cl)  in qfq_deact_rm_from_agg()  argument
380 	if (cl->qdisc->q.qlen > 0) /* class is active */  in qfq_deact_rm_from_agg()
381 		qfq_deactivate_class(q, cl);  in qfq_deact_rm_from_agg()
383 	qfq_rm_from_agg(q, cl);  in qfq_deact_rm_from_agg()
390 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_change_agg()  local
391 	struct qfq_aggregate *new_agg = qfq_find_agg(q, lmax, weight);  in qfq_change_agg()
397 		qfq_init_agg(q, new_agg, lmax, weight);  in qfq_change_agg()
399 	qfq_deact_rm_from_agg(q, cl);  in qfq_change_agg()
400 	qfq_add_to_agg(q, new_agg, cl);  in qfq_change_agg()
408 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_change_class()  local
454 	if (q->wsum + delta_w > QFQ_MAX_WSUM) {  in qfq_change_class()
456 			  delta_w, q->wsum);  in qfq_change_class()
497 	qdisc_class_hash_insert(&q->clhash, &cl->common);  in qfq_change_class()
500 	qdisc_class_hash_grow(sch, &q->clhash);  in qfq_change_class()
504 	new_agg = qfq_find_agg(q, lmax, weight);  in qfq_change_class()
514 		qfq_init_agg(q, new_agg, lmax, weight);  in qfq_change_class()
517 		qfq_deact_rm_from_agg(q, cl);  in qfq_change_class()
518 	qfq_add_to_agg(q, new_agg, cl);  in qfq_change_class()
532 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_destroy_class()  local
534 	qfq_rm_from_agg(q, cl);  in qfq_destroy_class()
542 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_delete_class()  local
551 	qdisc_class_hash_remove(&q->clhash, &cl->common);  in qfq_delete_class()
584 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_tcf_chain()  local
589 	return &q->filter_list;  in qfq_tcf_chain()
674 				  &cl->qdisc->qstats, cl->qdisc->q.qlen) < 0)  in qfq_dump_class_stats()
682 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_walk()  local
689 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_walk()
690 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_walk()
707 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_classify()  local
721 	fl = rcu_dereference_bh(q->filter_list);  in qfq_classify()
755 static inline struct qfq_group *qfq_ffs(struct qfq_sched *q,  in qfq_ffs()  argument
759 	return &q->groups[index];  in qfq_ffs()
772 static int qfq_calc_state(struct qfq_sched *q, const struct qfq_group *grp)  in qfq_calc_state()  argument
775 	unsigned int state = qfq_gt(grp->S, q->V);  in qfq_calc_state()
776 	unsigned long mask = mask_from(q->bitmaps[ER], grp->index);  in qfq_calc_state()
780 		next = qfq_ffs(q, mask);  in qfq_calc_state()
795 static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask,  in qfq_move_groups()  argument
798 	q->bitmaps[dst] |= q->bitmaps[src] & mask;  in qfq_move_groups()
799 	q->bitmaps[src] &= ~mask;  in qfq_move_groups()
802 static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)  in qfq_unblock_groups()  argument
804 	unsigned long mask = mask_from(q->bitmaps[ER], index + 1);  in qfq_unblock_groups()
808 		next = qfq_ffs(q, mask);  in qfq_unblock_groups()
814 	qfq_move_groups(q, mask, EB, ER);  in qfq_unblock_groups()
815 	qfq_move_groups(q, mask, IB, IR);  in qfq_unblock_groups()
828 static void qfq_make_eligible(struct qfq_sched *q)  in qfq_make_eligible()  argument
830 	unsigned long vslot = q->V >> q->min_slot_shift;  in qfq_make_eligible()
831 	unsigned long old_vslot = q->oldV >> q->min_slot_shift;  in qfq_make_eligible()
842 		qfq_move_groups(q, mask, IR, ER);  in qfq_make_eligible()
843 		qfq_move_groups(q, mask, IB, EB);  in qfq_make_eligible()
983 static void qfq_update_eligible(struct qfq_sched *q)  in qfq_update_eligible()  argument
988 	ineligible = q->bitmaps[IR] | q->bitmaps[IB];  in qfq_update_eligible()
990 		if (!q->bitmaps[ER]) {  in qfq_update_eligible()
991 			grp = qfq_ffs(q, ineligible);  in qfq_update_eligible()
992 			if (qfq_gt(grp->S, q->V))  in qfq_update_eligible()
993 				q->V = grp->S;  in qfq_update_eligible()
995 		qfq_make_eligible(q);  in qfq_update_eligible()
1007 	if (cl->qdisc->q.qlen == 0) /* no more packets, remove from list */  in agg_dequeue()
1057 static void qfq_update_start(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_update_start()  argument
1064 	limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift);  in qfq_update_start()
1066 	if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) {  in qfq_update_start()
1068 		mask = mask_from(q->bitmaps[ER], agg->grp->index);  in qfq_update_start()
1070 			struct qfq_group *next = qfq_ffs(q, mask);  in qfq_update_start()
1079 		agg->S = q->V;  in qfq_update_start()
1090 qfq_update_agg_ts(struct qfq_sched *q,  in qfq_update_agg_ts()  argument
1094 		qfq_update_start(q, agg);  in qfq_update_agg_ts()
1101 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg);
1105 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_dequeue()  local
1106 	struct qfq_aggregate *in_serv_agg = q->in_serv_agg;  in qfq_dequeue()
1141 			qfq_update_agg_ts(q, in_serv_agg, requeue);  in qfq_dequeue()
1142 			qfq_schedule_agg(q, in_serv_agg);  in qfq_dequeue()
1143 		} else if (sch->q.qlen == 0) { /* no aggregate to serve */  in qfq_dequeue()
1144 			q->in_serv_agg = NULL;  in qfq_dequeue()
1152 		in_serv_agg = q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_dequeue()
1158 	sch->q.qlen--;  in qfq_dequeue()
1171 	q->V += (u64)len * q->iwsum;  in qfq_dequeue()
1174 		 (unsigned long long) q->V);  in qfq_dequeue()
1179 static struct qfq_aggregate *qfq_choose_next_agg(struct qfq_sched *q)  in qfq_choose_next_agg()  argument
1185 	qfq_update_eligible(q);  in qfq_choose_next_agg()
1186 	q->oldV = q->V;  in qfq_choose_next_agg()
1188 	if (!q->bitmaps[ER])  in qfq_choose_next_agg()
1191 	grp = qfq_ffs(q, q->bitmaps[ER]);  in qfq_choose_next_agg()
1202 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1212 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1213 		s = qfq_calc_state(q, grp);  in qfq_choose_next_agg()
1214 		__set_bit(grp->index, &q->bitmaps[s]);  in qfq_choose_next_agg()
1217 	qfq_unblock_groups(q, grp->index, old_F);  in qfq_choose_next_agg()
1224 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_enqueue()  local
1258 	++sch->q.qlen;  in qfq_enqueue()
1262 	if (cl->qdisc->q.qlen != 1) {  in qfq_enqueue()
1276 	    q->in_serv_agg == agg)  in qfq_enqueue()
1279 	qfq_activate_agg(q, agg, enqueue);  in qfq_enqueue()
1287 static void qfq_schedule_agg(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_schedule_agg()  argument
1311 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_schedule_agg()
1312 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_schedule_agg()
1313 	} else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V) &&  in qfq_schedule_agg()
1314 		   q->in_serv_agg == NULL)  in qfq_schedule_agg()
1315 		q->V = roundedS;  in qfq_schedule_agg()
1319 	s = qfq_calc_state(q, grp);  in qfq_schedule_agg()
1320 	__set_bit(grp->index, &q->bitmaps[s]);  in qfq_schedule_agg()
1323 		 s, q->bitmaps[s],  in qfq_schedule_agg()
1326 		 (unsigned long long) q->V);  in qfq_schedule_agg()
1334 static void qfq_activate_agg(struct qfq_sched *q, struct qfq_aggregate *agg,  in qfq_activate_agg()  argument
1339 	qfq_update_agg_ts(q, agg, reason);  in qfq_activate_agg()
1340 	if (q->in_serv_agg == NULL) { /* no aggr. in service or scheduled */  in qfq_activate_agg()
1341 		q->in_serv_agg = agg; /* start serving this aggregate */  in qfq_activate_agg()
1343 		q->oldV = q->V = agg->S;  in qfq_activate_agg()
1344 	} else if (agg != q->in_serv_agg)  in qfq_activate_agg()
1345 		qfq_schedule_agg(q, agg);  in qfq_activate_agg()
1348 static void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,  in qfq_slot_remove()  argument
1371 static void qfq_deactivate_agg(struct qfq_sched *q, struct qfq_aggregate *agg)  in qfq_deactivate_agg()  argument
1378 	if (agg == q->in_serv_agg) {  in qfq_deactivate_agg()
1380 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_deactivate_agg()
1385 	qfq_slot_remove(q, grp, agg);  in qfq_deactivate_agg()
1388 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1389 		__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1390 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1392 		if (test_bit(grp->index, &q->bitmaps[ER]) &&  in qfq_deactivate_agg()
1393 		    !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {  in qfq_deactivate_agg()
1394 			mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);  in qfq_deactivate_agg()
1399 			qfq_move_groups(q, mask, EB, ER);  in qfq_deactivate_agg()
1400 			qfq_move_groups(q, mask, IB, IR);  in qfq_deactivate_agg()
1402 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1407 			__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1408 			__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1409 			__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1410 			__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1413 			s = qfq_calc_state(q, grp);  in qfq_deactivate_agg()
1414 			__set_bit(grp->index, &q->bitmaps[s]);  in qfq_deactivate_agg()
1421 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_qlen_notify()  local
1424 	if (cl->qdisc->q.qlen == 0)  in qfq_qlen_notify()
1425 		qfq_deactivate_class(q, cl);  in qfq_qlen_notify()
1428 static unsigned int qfq_drop_from_slot(struct qfq_sched *q,  in qfq_drop_from_slot()  argument
1443 				if (cl->qdisc->q.qlen == 0)  in qfq_drop_from_slot()
1444 					qfq_deactivate_class(q, cl);  in qfq_drop_from_slot()
1455 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_drop()  local
1460 		grp = &q->groups[i];  in qfq_drop()
1462 			len = qfq_drop_from_slot(q, &grp->slots[j]);  in qfq_drop()
1464 				sch->q.qlen--;  in qfq_drop()
1476 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_init_qdisc()  local
1481 	err = qdisc_class_hash_init(&q->clhash);  in qfq_init_qdisc()
1491 	q->max_agg_classes = 1<<max_cl_shift;  in qfq_init_qdisc()
1495 	q->min_slot_shift = FRAC_BITS + maxbudg_shift - QFQ_MAX_INDEX;  in qfq_init_qdisc()
1498 		grp = &q->groups[i];  in qfq_init_qdisc()
1500 		grp->slot_shift = q->min_slot_shift + i;  in qfq_init_qdisc()
1505 	INIT_HLIST_HEAD(&q->nonfull_aggs);  in qfq_init_qdisc()
1512 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_reset_qdisc()  local
1516 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_reset_qdisc()
1517 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_reset_qdisc()
1518 			if (cl->qdisc->q.qlen > 0)  in qfq_reset_qdisc()
1519 				qfq_deactivate_class(q, cl);  in qfq_reset_qdisc()
1524 	sch->q.qlen = 0;  in qfq_reset_qdisc()
1529 	struct qfq_sched *q = qdisc_priv(sch);  in qfq_destroy_qdisc()  local
1534 	tcf_destroy_chain(&q->filter_list);  in qfq_destroy_qdisc()
1536 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_destroy_qdisc()
1537 		hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],  in qfq_destroy_qdisc()
1542 	qdisc_class_hash_destroy(&q->clhash);  in qfq_destroy_qdisc()