sch_fq_codel.c 19 KB
Newer Older
1 2 3 4 5 6 7 8
/*
 * Fair Queue CoDel discipline
 *
 *	This program is free software; you can redistribute it and/or
 *	modify it under the terms of the GNU General Public License
 *	as published by the Free Software Foundation; either version
 *	2 of the License, or (at your option) any later version.
 *
9
 *  Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com>
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/jiffies.h>
#include <linux/string.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <net/netlink.h>
#include <net/pkt_sched.h>
#include <net/codel.h>
27 28
#include <net/codel_impl.h>
#include <net/codel_qdisc.h>
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

/*	Fair Queue CoDel.
 *
 * Principles :
 * Packets are classified (internal classifier or external) on flows.
 * This is a Stochastic model (as we use a hash, several flows
 *			       might be hashed on same slot)
 * Each flow has a CoDel managed queue.
 * Flows are linked onto two (Round Robin) lists,
 * so that new flows have priority on old ones.
 *
 * For a given flow, packets are not reordered (CoDel uses a FIFO)
 * head drops only.
 * ECN capability is on by default.
 * Low memory footprint (64 bytes per flow)
 */

struct fq_codel_flow {
	struct sk_buff	  *head;
	struct sk_buff	  *tail;
	struct list_head  flowchain;
	int		  deficit;
	u32		  dropped; /* number of drops (or ECN marks) on this flow */
	struct codel_vars cvars;
}; /* please try to keep this structure <= 64 bytes */

struct fq_codel_sched_data {
John Fastabend's avatar
John Fastabend committed
56
	struct tcf_proto __rcu *filter_list; /* optional external classifier */
57 58 59 60 61
	struct fq_codel_flow *flows;	/* Flows table [flows_cnt] */
	u32		*backlogs;	/* backlog table [flows_cnt] */
	u32		flows_cnt;	/* number of flows */
	u32		perturbation;	/* hash perturbation */
	u32		quantum;	/* psched_mtu(qdisc_dev(sch)); */
62
	u32		drop_batch_size;
63
	u32		memory_limit;
64 65
	struct codel_params cparams;
	struct codel_stats cstats;
66 67
	u32		memory_usage;
	u32		drop_overmemory;
68 69 70 71 72 73 74 75
	u32		drop_overlimit;
	u32		new_flow_count;

	struct list_head new_flows;	/* list of new flows */
	struct list_head old_flows;	/* list of old flows */
};

static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
76
				  struct sk_buff *skb)
77
{
78
	u32 hash = skb_get_hash_perturb(skb, q->perturbation);
79 80

	return reciprocal_scale(hash, q->flows_cnt);
81 82 83 84 85 86
}

static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
				      int *qerr)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
John Fastabend's avatar
John Fastabend committed
87
	struct tcf_proto *filter;
88 89 90 91 92 93 94 95
	struct tcf_result res;
	int result;

	if (TC_H_MAJ(skb->priority) == sch->handle &&
	    TC_H_MIN(skb->priority) > 0 &&
	    TC_H_MIN(skb->priority) <= q->flows_cnt)
		return TC_H_MIN(skb->priority);

96
	filter = rcu_dereference_bh(q->filter_list);
John Fastabend's avatar
John Fastabend committed
97
	if (!filter)
98 99 100
		return fq_codel_hash(q, skb) + 1;

	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
101
	result = tc_classify(skb, filter, &res, false);
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
	if (result >= 0) {
#ifdef CONFIG_NET_CLS_ACT
		switch (result) {
		case TC_ACT_STOLEN:
		case TC_ACT_QUEUED:
			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
		case TC_ACT_SHOT:
			return 0;
		}
#endif
		if (TC_H_MIN(res.classid) <= q->flows_cnt)
			return TC_H_MIN(res.classid);
	}
	return 0;
}

/* helper functions : might be changed when/if skb use a standard list_head */

/* remove one skb from head of slot queue */
static inline struct sk_buff *dequeue_head(struct fq_codel_flow *flow)
{
	struct sk_buff *skb = flow->head;

	flow->head = skb->next;
	skb->next = NULL;
	return skb;
}

/* add skb to flow queue (tail add) */
static inline void flow_queue_add(struct fq_codel_flow *flow,
				  struct sk_buff *skb)
{
	if (flow->head == NULL)
		flow->head = skb;
	else
		flow->tail->next = skb;
	flow->tail = skb;
	skb->next = NULL;
}

142
static unsigned int fq_codel_drop(struct Qdisc *sch, unsigned int max_packets)
143 144 145 146 147
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	struct sk_buff *skb;
	unsigned int maxbacklog = 0, idx = 0, i, len;
	struct fq_codel_flow *flow;
148
	unsigned int threshold;
149
	unsigned int mem = 0;
150

151
	/* Queue is full! Find the fat flow and drop packet(s) from it.
152 153 154
	 * This might sound expensive, but with 1024 flows, we scan
	 * 4KB of memory, and we dont need to handle a complex tree
	 * in fast path (packet queue/enqueue) with many cache misses.
155 156
	 * In stress mode, we'll try to drop 64 packets from the flow,
	 * amortizing this linear lookup to one cache line per drop.
157 158 159 160 161 162 163
	 */
	for (i = 0; i < q->flows_cnt; i++) {
		if (q->backlogs[i] > maxbacklog) {
			maxbacklog = q->backlogs[i];
			idx = i;
		}
	}
164 165 166 167

	/* Our goal is to drop half of this fat flow backlog */
	threshold = maxbacklog >> 1;

168
	flow = &q->flows[idx];
169 170 171 172 173
	len = 0;
	i = 0;
	do {
		skb = dequeue_head(flow);
		len += qdisc_pkt_len(skb);
174
		mem += skb->truesize;
175 176 177 178
		kfree_skb(skb);
	} while (++i < max_packets && len < threshold);

	flow->dropped += i;
179
	q->backlogs[idx] -= len;
180
	q->memory_usage -= mem;
181 182 183
	sch->qstats.drops += i;
	sch->qstats.backlog -= len;
	sch->q.qlen -= i;
184 185 186
	return idx;
}

187 188 189 190 191
static unsigned int fq_codel_qdisc_drop(struct Qdisc *sch)
{
	unsigned int prev_backlog;

	prev_backlog = sch->qstats.backlog;
192
	fq_codel_drop(sch, 1U);
193 194 195
	return prev_backlog - sch->qstats.backlog;
}

196 197 198
static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
199
	unsigned int idx, prev_backlog, prev_qlen;
200 201
	struct fq_codel_flow *flow;
	int uninitialized_var(ret);
202
	unsigned int pkt_len;
203
	bool memory_limited;
204 205 206 207

	idx = fq_codel_classify(skb, sch, &ret);
	if (idx == 0) {
		if (ret & __NET_XMIT_BYPASS)
208
			qdisc_qstats_drop(sch);
209 210 211 212 213 214 215 216 217
		kfree_skb(skb);
		return ret;
	}
	idx--;

	codel_set_enqueue_time(skb);
	flow = &q->flows[idx];
	flow_queue_add(flow, skb);
	q->backlogs[idx] += qdisc_pkt_len(skb);
218
	qdisc_qstats_backlog_inc(sch, skb);
219 220 221 222 223 224 225

	if (list_empty(&flow->flowchain)) {
		list_add_tail(&flow->flowchain, &q->new_flows);
		q->new_flow_count++;
		flow->deficit = q->quantum;
		flow->dropped = 0;
	}
226 227 228
	q->memory_usage += skb->truesize;
	memory_limited = q->memory_usage > q->memory_limit;
	if (++sch->q.qlen <= sch->limit && !memory_limited)
229 230
		return NET_XMIT_SUCCESS;

231
	prev_backlog = sch->qstats.backlog;
232 233
	prev_qlen = sch->q.qlen;

234 235
	/* save this packet length as it might be dropped by fq_codel_drop() */
	pkt_len = qdisc_pkt_len(skb);
236 237 238 239
	/* fq_codel_drop() is quite expensive, as it performs a linear search
	 * in q->backlogs[] to find a fat flow.
	 * So instead of dropping a single packet, drop half of its backlog
	 * with a 64 packets limit to not add a too big cpu spike here.
240
	 */
241 242
	ret = fq_codel_drop(sch, q->drop_batch_size);

243 244 245
	prev_qlen -= sch->q.qlen;
	prev_backlog -= sch->qstats.backlog;
	q->drop_overlimit += prev_qlen;
246
	if (memory_limited)
247
		q->drop_overmemory += prev_qlen;
248

249 250 251 252 253 254 255 256 257 258 259
	/* As we dropped packet(s), better let upper stack know this.
	 * If we dropped a packet for this flow, return NET_XMIT_CN,
	 * but in this case, our parents wont increase their backlogs.
	 */
	if (ret == idx) {
		qdisc_tree_reduce_backlog(sch, prev_qlen - 1,
					  prev_backlog - pkt_len);
		return NET_XMIT_CN;
	}
	qdisc_tree_reduce_backlog(sch, prev_qlen, prev_backlog);
	return NET_XMIT_SUCCESS;
260 261 262 263 264 265
}

/* This is the specific function called from codel_dequeue()
 * to dequeue a packet from queue. Note: backlog is handled in
 * codel, we dont need to reduce it here.
 */
266
static struct sk_buff *dequeue_func(struct codel_vars *vars, void *ctx)
267
{
268
	struct Qdisc *sch = ctx;
269
	struct fq_codel_sched_data *q = qdisc_priv(sch);
270 271 272 273 274 275
	struct fq_codel_flow *flow;
	struct sk_buff *skb = NULL;

	flow = container_of(vars, struct fq_codel_flow, cvars);
	if (flow->head) {
		skb = dequeue_head(flow);
276
		q->backlogs[flow - q->flows] -= qdisc_pkt_len(skb);
277
		q->memory_usage -= skb->truesize;
278
		sch->q.qlen--;
279
		sch->qstats.backlog -= qdisc_pkt_len(skb);
280 281 282 283
	}
	return skb;
}

284 285 286 287 288 289 290
static void drop_func(struct sk_buff *skb, void *ctx)
{
	struct Qdisc *sch = ctx;

	qdisc_drop(skb, sch);
}

291 292 293 294 295 296 297
static struct sk_buff *fq_codel_dequeue(struct Qdisc *sch)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	struct sk_buff *skb;
	struct fq_codel_flow *flow;
	struct list_head *head;
	u32 prev_drop_count, prev_ecn_mark;
298
	unsigned int prev_backlog;
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

begin:
	head = &q->new_flows;
	if (list_empty(head)) {
		head = &q->old_flows;
		if (list_empty(head))
			return NULL;
	}
	flow = list_first_entry(head, struct fq_codel_flow, flowchain);

	if (flow->deficit <= 0) {
		flow->deficit += q->quantum;
		list_move_tail(&flow->flowchain, &q->old_flows);
		goto begin;
	}

	prev_drop_count = q->cstats.drop_count;
	prev_ecn_mark = q->cstats.ecn_mark;
317
	prev_backlog = sch->qstats.backlog;
318

319 320 321
	skb = codel_dequeue(sch, &sch->qstats.backlog, &q->cparams,
			    &flow->cvars, &q->cstats, qdisc_pkt_len,
			    codel_get_enqueue_time, drop_func, dequeue_func);
322 323 324 325 326 327 328 329 330 331 332 333 334 335

	flow->dropped += q->cstats.drop_count - prev_drop_count;
	flow->dropped += q->cstats.ecn_mark - prev_ecn_mark;

	if (!skb) {
		/* force a pass through old_flows to prevent starvation */
		if ((head == &q->new_flows) && !list_empty(&q->old_flows))
			list_move_tail(&flow->flowchain, &q->old_flows);
		else
			list_del_init(&flow->flowchain);
		goto begin;
	}
	qdisc_bstats_update(sch, skb);
	flow->deficit -= qdisc_pkt_len(skb);
336
	/* We cant call qdisc_tree_reduce_backlog() if our qlen is 0,
337 338 339
	 * or HTB crashes. Defer it for next round.
	 */
	if (q->cstats.drop_count && sch->q.qlen) {
340 341
		qdisc_tree_reduce_backlog(sch, q->cstats.drop_count,
					  q->cstats.drop_len);
342
		q->cstats.drop_count = 0;
343
		q->cstats.drop_len = 0;
344 345 346 347 348 349
	}
	return skb;
}

static void fq_codel_reset(struct Qdisc *sch)
{
350 351
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	int i;
352

353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
	INIT_LIST_HEAD(&q->new_flows);
	INIT_LIST_HEAD(&q->old_flows);
	for (i = 0; i < q->flows_cnt; i++) {
		struct fq_codel_flow *flow = q->flows + i;

		while (flow->head) {
			struct sk_buff *skb = dequeue_head(flow);

			qdisc_qstats_backlog_dec(sch, skb);
			kfree_skb(skb);
		}

		INIT_LIST_HEAD(&flow->flowchain);
		codel_vars_init(&flow->cvars);
	}
	memset(q->backlogs, 0, q->flows_cnt * sizeof(u32));
	sch->q.qlen = 0;
370
	q->memory_usage = 0;
371 372 373 374 375 376 377 378 379
}

static const struct nla_policy fq_codel_policy[TCA_FQ_CODEL_MAX + 1] = {
	[TCA_FQ_CODEL_TARGET]	= { .type = NLA_U32 },
	[TCA_FQ_CODEL_LIMIT]	= { .type = NLA_U32 },
	[TCA_FQ_CODEL_INTERVAL]	= { .type = NLA_U32 },
	[TCA_FQ_CODEL_ECN]	= { .type = NLA_U32 },
	[TCA_FQ_CODEL_FLOWS]	= { .type = NLA_U32 },
	[TCA_FQ_CODEL_QUANTUM]	= { .type = NLA_U32 },
380
	[TCA_FQ_CODEL_CE_THRESHOLD] = { .type = NLA_U32 },
381
	[TCA_FQ_CODEL_DROP_BATCH_SIZE] = { .type = NLA_U32 },
382
	[TCA_FQ_CODEL_MEMORY_LIMIT] = { .type = NLA_U32 },
383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412
};

static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	struct nlattr *tb[TCA_FQ_CODEL_MAX + 1];
	int err;

	if (!opt)
		return -EINVAL;

	err = nla_parse_nested(tb, TCA_FQ_CODEL_MAX, opt, fq_codel_policy);
	if (err < 0)
		return err;
	if (tb[TCA_FQ_CODEL_FLOWS]) {
		if (q->flows)
			return -EINVAL;
		q->flows_cnt = nla_get_u32(tb[TCA_FQ_CODEL_FLOWS]);
		if (!q->flows_cnt ||
		    q->flows_cnt > 65536)
			return -EINVAL;
	}
	sch_tree_lock(sch);

	if (tb[TCA_FQ_CODEL_TARGET]) {
		u64 target = nla_get_u32(tb[TCA_FQ_CODEL_TARGET]);

		q->cparams.target = (target * NSEC_PER_USEC) >> CODEL_SHIFT;
	}

413 414 415 416 417 418
	if (tb[TCA_FQ_CODEL_CE_THRESHOLD]) {
		u64 val = nla_get_u32(tb[TCA_FQ_CODEL_CE_THRESHOLD]);

		q->cparams.ce_threshold = (val * NSEC_PER_USEC) >> CODEL_SHIFT;
	}

419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
	if (tb[TCA_FQ_CODEL_INTERVAL]) {
		u64 interval = nla_get_u32(tb[TCA_FQ_CODEL_INTERVAL]);

		q->cparams.interval = (interval * NSEC_PER_USEC) >> CODEL_SHIFT;
	}

	if (tb[TCA_FQ_CODEL_LIMIT])
		sch->limit = nla_get_u32(tb[TCA_FQ_CODEL_LIMIT]);

	if (tb[TCA_FQ_CODEL_ECN])
		q->cparams.ecn = !!nla_get_u32(tb[TCA_FQ_CODEL_ECN]);

	if (tb[TCA_FQ_CODEL_QUANTUM])
		q->quantum = max(256U, nla_get_u32(tb[TCA_FQ_CODEL_QUANTUM]));

434 435 436
	if (tb[TCA_FQ_CODEL_DROP_BATCH_SIZE])
		q->drop_batch_size = min(1U, nla_get_u32(tb[TCA_FQ_CODEL_DROP_BATCH_SIZE]));

437 438 439 440 441
	if (tb[TCA_FQ_CODEL_MEMORY_LIMIT])
		q->memory_limit = min(1U << 31, nla_get_u32(tb[TCA_FQ_CODEL_MEMORY_LIMIT]));

	while (sch->q.qlen > sch->limit ||
	       q->memory_usage > q->memory_limit) {
442 443
		struct sk_buff *skb = fq_codel_dequeue(sch);

444
		q->cstats.drop_len += qdisc_pkt_len(skb);
445 446 447
		kfree_skb(skb);
		q->cstats.drop_count++;
	}
448
	qdisc_tree_reduce_backlog(sch, q->cstats.drop_count, q->cstats.drop_len);
449
	q->cstats.drop_count = 0;
450
	q->cstats.drop_len = 0;
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466

	sch_tree_unlock(sch);
	return 0;
}

static void *fq_codel_zalloc(size_t sz)
{
	void *ptr = kzalloc(sz, GFP_KERNEL | __GFP_NOWARN);

	if (!ptr)
		ptr = vzalloc(sz);
	return ptr;
}

static void fq_codel_free(void *addr)
{
WANG Cong's avatar
WANG Cong committed
467
	kvfree(addr);
468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
}

static void fq_codel_destroy(struct Qdisc *sch)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);

	tcf_destroy_chain(&q->filter_list);
	fq_codel_free(q->backlogs);
	fq_codel_free(q->flows);
}

static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	int i;

	sch->limit = 10*1024;
	q->flows_cnt = 1024;
486
	q->memory_limit = 32 << 20; /* 32 MBytes */
487
	q->drop_batch_size = 64;
488
	q->quantum = psched_mtu(qdisc_dev(sch));
489
	q->perturbation = prandom_u32();
490 491
	INIT_LIST_HEAD(&q->new_flows);
	INIT_LIST_HEAD(&q->old_flows);
492
	codel_params_init(&q->cparams);
493 494
	codel_stats_init(&q->cstats);
	q->cparams.ecn = true;
495
	q->cparams.mtu = psched_mtu(qdisc_dev(sch));
496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516

	if (opt) {
		int err = fq_codel_change(sch, opt);
		if (err)
			return err;
	}

	if (!q->flows) {
		q->flows = fq_codel_zalloc(q->flows_cnt *
					   sizeof(struct fq_codel_flow));
		if (!q->flows)
			return -ENOMEM;
		q->backlogs = fq_codel_zalloc(q->flows_cnt * sizeof(u32));
		if (!q->backlogs) {
			fq_codel_free(q->flows);
			return -ENOMEM;
		}
		for (i = 0; i < q->flows_cnt; i++) {
			struct fq_codel_flow *flow = q->flows + i;

			INIT_LIST_HEAD(&flow->flowchain);
517
			codel_vars_init(&flow->cvars);
518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
		}
	}
	if (sch->limit >= 1)
		sch->flags |= TCQ_F_CAN_BYPASS;
	else
		sch->flags &= ~TCQ_F_CAN_BYPASS;
	return 0;
}

static int fq_codel_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	struct nlattr *opts;

	opts = nla_nest_start(skb, TCA_OPTIONS);
	if (opts == NULL)
		goto nla_put_failure;

	if (nla_put_u32(skb, TCA_FQ_CODEL_TARGET,
			codel_time_to_us(q->cparams.target)) ||
	    nla_put_u32(skb, TCA_FQ_CODEL_LIMIT,
			sch->limit) ||
	    nla_put_u32(skb, TCA_FQ_CODEL_INTERVAL,
			codel_time_to_us(q->cparams.interval)) ||
	    nla_put_u32(skb, TCA_FQ_CODEL_ECN,
			q->cparams.ecn) ||
	    nla_put_u32(skb, TCA_FQ_CODEL_QUANTUM,
			q->quantum) ||
546 547
	    nla_put_u32(skb, TCA_FQ_CODEL_DROP_BATCH_SIZE,
			q->drop_batch_size) ||
548 549
	    nla_put_u32(skb, TCA_FQ_CODEL_MEMORY_LIMIT,
			q->memory_limit) ||
550 551 552 553
	    nla_put_u32(skb, TCA_FQ_CODEL_FLOWS,
			q->flows_cnt))
		goto nla_put_failure;

554 555 556 557 558
	if (q->cparams.ce_threshold != CODEL_DISABLED_THRESHOLD &&
	    nla_put_u32(skb, TCA_FQ_CODEL_CE_THRESHOLD,
			codel_time_to_us(q->cparams.ce_threshold)))
		goto nla_put_failure;

559
	return nla_nest_end(skb, opts);
560 561 562 563 564 565 566 567 568 569 570 571 572

nla_put_failure:
	return -1;
}

static int fq_codel_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	struct tc_fq_codel_xstats st = {
		.type				= TCA_FQ_CODEL_XSTATS_QDISC,
	};
	struct list_head *pos;

Sasha Levin's avatar
Sasha Levin committed
573 574 575 576
	st.qdisc_stats.maxpacket = q->cstats.maxpacket;
	st.qdisc_stats.drop_overlimit = q->drop_overlimit;
	st.qdisc_stats.ecn_mark = q->cstats.ecn_mark;
	st.qdisc_stats.new_flow_count = q->new_flow_count;
577
	st.qdisc_stats.ce_mark = q->cstats.ce_mark;
578 579
	st.qdisc_stats.memory_usage  = q->memory_usage;
	st.qdisc_stats.drop_overmemory = q->drop_overmemory;
Sasha Levin's avatar
Sasha Levin committed
580

581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611
	list_for_each(pos, &q->new_flows)
		st.qdisc_stats.new_flows_len++;

	list_for_each(pos, &q->old_flows)
		st.qdisc_stats.old_flows_len++;

	return gnet_stats_copy_app(d, &st, sizeof(st));
}

static struct Qdisc *fq_codel_leaf(struct Qdisc *sch, unsigned long arg)
{
	return NULL;
}

static unsigned long fq_codel_get(struct Qdisc *sch, u32 classid)
{
	return 0;
}

static unsigned long fq_codel_bind(struct Qdisc *sch, unsigned long parent,
			      u32 classid)
{
	/* we cannot bypass queue discipline anymore */
	sch->flags &= ~TCQ_F_CAN_BYPASS;
	return 0;
}

static void fq_codel_put(struct Qdisc *q, unsigned long cl)
{
}

John Fastabend's avatar
John Fastabend committed
612 613
static struct tcf_proto __rcu **fq_codel_find_tcf(struct Qdisc *sch,
						  unsigned long cl)
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);

	if (cl)
		return NULL;
	return &q->filter_list;
}

static int fq_codel_dump_class(struct Qdisc *sch, unsigned long cl,
			  struct sk_buff *skb, struct tcmsg *tcm)
{
	tcm->tcm_handle |= TC_H_MIN(cl);
	return 0;
}

static int fq_codel_dump_class_stats(struct Qdisc *sch, unsigned long cl,
				     struct gnet_dump *d)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	u32 idx = cl - 1;
	struct gnet_stats_queue qs = { 0 };
	struct tc_fq_codel_xstats xstats;

	if (idx < q->flows_cnt) {
		const struct fq_codel_flow *flow = &q->flows[idx];
		const struct sk_buff *skb = flow->head;

		memset(&xstats, 0, sizeof(xstats));
		xstats.type = TCA_FQ_CODEL_XSTATS_CLASS;
		xstats.class_stats.deficit = flow->deficit;
		xstats.class_stats.ldelay =
			codel_time_to_us(flow->cvars.ldelay);
		xstats.class_stats.count = flow->cvars.count;
		xstats.class_stats.lastcount = flow->cvars.lastcount;
		xstats.class_stats.dropping = flow->cvars.dropping;
		if (flow->cvars.dropping) {
			codel_tdiff_t delta = flow->cvars.drop_next -
					      codel_get_time();

			xstats.class_stats.drop_next = (delta >= 0) ?
				codel_time_to_us(delta) :
				-codel_time_to_us(-delta);
		}
		while (skb) {
			qs.qlen++;
			skb = skb->next;
		}
		qs.backlog = q->backlogs[idx];
		qs.drops = flow->dropped;
	}
664
	if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
		return -1;
	if (idx < q->flows_cnt)
		return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
	return 0;
}

static void fq_codel_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
	struct fq_codel_sched_data *q = qdisc_priv(sch);
	unsigned int i;

	if (arg->stop)
		return;

	for (i = 0; i < q->flows_cnt; i++) {
		if (list_empty(&q->flows[i].flowchain) ||
		    arg->count < arg->skip) {
			arg->count++;
			continue;
		}
		if (arg->fn(sch, i + 1, arg) < 0) {
			arg->stop = 1;
			break;
		}
		arg->count++;
	}
}

static const struct Qdisc_class_ops fq_codel_class_ops = {
	.leaf		=	fq_codel_leaf,
	.get		=	fq_codel_get,
	.put		=	fq_codel_put,
	.tcf_chain	=	fq_codel_find_tcf,
	.bind_tcf	=	fq_codel_bind,
	.unbind_tcf	=	fq_codel_put,
	.dump		=	fq_codel_dump_class,
	.dump_stats	=	fq_codel_dump_class_stats,
	.walk		=	fq_codel_walk,
};

static struct Qdisc_ops fq_codel_qdisc_ops __read_mostly = {
	.cl_ops		=	&fq_codel_class_ops,
	.id		=	"fq_codel",
	.priv_size	=	sizeof(struct fq_codel_sched_data),
	.enqueue	=	fq_codel_enqueue,
	.dequeue	=	fq_codel_dequeue,
	.peek		=	qdisc_peek_dequeued,
712
	.drop		=	fq_codel_qdisc_drop,
713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735
	.init		=	fq_codel_init,
	.reset		=	fq_codel_reset,
	.destroy	=	fq_codel_destroy,
	.change		=	fq_codel_change,
	.dump		=	fq_codel_dump,
	.dump_stats =	fq_codel_dump_stats,
	.owner		=	THIS_MODULE,
};

static int __init fq_codel_module_init(void)
{
	return register_qdisc(&fq_codel_qdisc_ops);
}

static void __exit fq_codel_module_exit(void)
{
	unregister_qdisc(&fq_codel_qdisc_ops);
}

module_init(fq_codel_module_init)
module_exit(fq_codel_module_exit)
MODULE_AUTHOR("Eric Dumazet");
MODULE_LICENSE("GPL");