sch_sfq.c 13.6 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/*
 * net/sched/sch_sfq.c	Stochastic Fairness Queueing 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.
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 */

#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/ipv6.h>
#include <linux/skbuff.h>
22
#include <linux/jhash.h>
23
#include <linux/slab.h>
24 25
#include <net/ip.h>
#include <net/netlink.h>
L
Linus Torvalds 已提交
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#include <net/pkt_sched.h>


/*	Stochastic Fairness Queuing algorithm.
	=======================================

	Source:
	Paul E. McKenney "Stochastic Fairness Queuing",
	IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.

	Paul E. McKenney "Stochastic Fairness Queuing",
	"Interworking: Research and Experience", v.2, 1991, p.113-131.


	See also:
	M. Shreedhar and George Varghese "Efficient Fair
	Queuing using Deficit Round Robin", Proc. SIGCOMM 95.


45
	This is not the thing that is usually called (W)FQ nowadays.
L
Linus Torvalds 已提交
46 47 48 49 50 51 52 53 54
	It does not use any timestamp mechanism, but instead
	processes queues in round-robin order.

	ADVANTAGE:

	- It is very cheap. Both CPU and memory requirements are minimal.

	DRAWBACKS:

55
	- "Stochastic" -> It is not 100% fair.
L
Linus Torvalds 已提交
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
	When hash collisions occur, several flows are considered as one.

	- "Round-robin" -> It introduces larger delays than virtual clock
	based schemes, and should not be used for isolating interactive
	traffic	from non-interactive. It means, that this scheduler
	should be used as leaf of CBQ or P3, which put interactive traffic
	to higher priority band.

	We still need true WFQ for top level CSZ, but using WFQ
	for the best effort traffic is absolutely pointless:
	SFQ is superior for this purpose.

	IMPLEMENTATION:
	This implementation limits maximal queue length to 128;
	maximal mtu to 2^15-1; number of hash buckets to 1024.
	The only goal of this restrictions was that all data
	fit into one 4K page :-). Struct sfq_sched_data is
	organized in anti-cache manner: all the data for a bucket
	are scattered over different locations. This is not good,
	but it allowed me to put it into 4K.

	It is easy to increase these values, but not in flight.  */

#define SFQ_DEPTH		128
#define SFQ_HASH_DIVISOR	1024

/* This type should contain at least SFQ_DEPTH*2 values */
typedef unsigned char sfq_index;

struct sfq_head
{
	sfq_index	next;
	sfq_index	prev;
};

struct sfq_sched_data
{
/* Parameters */
	int		perturb_period;
	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
	int		limit;

/* Variables */
99
	struct tcf_proto *filter_list;
L
Linus Torvalds 已提交
100
	struct timer_list perturb_timer;
101
	u32		perturbation;
L
Linus Torvalds 已提交
102 103 104 105 106 107 108 109 110 111 112 113 114
	sfq_index	tail;		/* Index of current slot in round */
	sfq_index	max_depth;	/* Maximal depth */

	sfq_index	ht[SFQ_HASH_DIVISOR];	/* Hash table */
	sfq_index	next[SFQ_DEPTH];	/* Active slots link */
	short		allot[SFQ_DEPTH];	/* Current allotment per slot */
	unsigned short	hash[SFQ_DEPTH];	/* Hash value indexed by slots */
	struct sk_buff_head	qs[SFQ_DEPTH];		/* Slot queue */
	struct sfq_head	dep[SFQ_DEPTH*2];	/* Linked list of slots, indexed by depth */
};

static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
{
115
	return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
L
Linus Torvalds 已提交
116 117 118 119 120 121 122
}

static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
{
	u32 h, h2;

	switch (skb->protocol) {
123
	case htons(ETH_P_IP):
L
Linus Torvalds 已提交
124
	{
125
		const struct iphdr *iph = ip_hdr(skb);
126 127
		h = (__force u32)iph->daddr;
		h2 = (__force u32)iph->saddr ^ iph->protocol;
L
Linus Torvalds 已提交
128 129 130
		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
		    (iph->protocol == IPPROTO_TCP ||
		     iph->protocol == IPPROTO_UDP ||
131
		     iph->protocol == IPPROTO_UDPLITE ||
132 133
		     iph->protocol == IPPROTO_SCTP ||
		     iph->protocol == IPPROTO_DCCP ||
L
Linus Torvalds 已提交
134 135 136 137
		     iph->protocol == IPPROTO_ESP))
			h2 ^= *(((u32*)iph) + iph->ihl);
		break;
	}
138
	case htons(ETH_P_IPV6):
L
Linus Torvalds 已提交
139
	{
140
		struct ipv6hdr *iph = ipv6_hdr(skb);
141 142
		h = (__force u32)iph->daddr.s6_addr32[3];
		h2 = (__force u32)iph->saddr.s6_addr32[3] ^ iph->nexthdr;
L
Linus Torvalds 已提交
143 144
		if (iph->nexthdr == IPPROTO_TCP ||
		    iph->nexthdr == IPPROTO_UDP ||
145
		    iph->nexthdr == IPPROTO_UDPLITE ||
146 147
		    iph->nexthdr == IPPROTO_SCTP ||
		    iph->nexthdr == IPPROTO_DCCP ||
L
Linus Torvalds 已提交
148 149 150 151 152
		    iph->nexthdr == IPPROTO_ESP)
			h2 ^= *(u32*)&iph[1];
		break;
	}
	default:
153
		h = (unsigned long)skb_dst(skb) ^ (__force u32)skb->protocol;
154
		h2 = (unsigned long)skb->sk;
L
Linus Torvalds 已提交
155
	}
156

L
Linus Torvalds 已提交
157 158 159
	return sfq_fold_hash(q, h, h2);
}

160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
				 int *qerr)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	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) <= SFQ_HASH_DIVISOR)
		return TC_H_MIN(skb->priority);

	if (!q->filter_list)
		return sfq_hash(q, skb) + 1;

175
	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
176 177 178 179 180 181
	result = tc_classify(skb, q->filter_list, &res);
	if (result >= 0) {
#ifdef CONFIG_NET_CLS_ACT
		switch (result) {
		case TC_ACT_STOLEN:
		case TC_ACT_QUEUED:
182
			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
183 184 185 186 187 188 189 190 191 192
		case TC_ACT_SHOT:
			return 0;
		}
#endif
		if (TC_H_MIN(res.classid) <= SFQ_HASH_DIVISOR)
			return TC_H_MIN(res.classid);
	}
	return 0;
}

L
Linus Torvalds 已提交
193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
{
	sfq_index p, n;
	int d = q->qs[x].qlen + SFQ_DEPTH;

	p = d;
	n = q->dep[d].next;
	q->dep[x].next = n;
	q->dep[x].prev = p;
	q->dep[p].next = q->dep[n].prev = x;
}

static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
{
	sfq_index p, n;

	n = q->dep[x].next;
	p = q->dep[x].prev;
	q->dep[p].next = n;
	q->dep[n].prev = p;

	if (n == p && q->max_depth == q->qs[x].qlen + 1)
		q->max_depth--;

	sfq_link(q, x);
}

static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
{
	sfq_index p, n;
	int d;

	n = q->dep[x].next;
	p = q->dep[x].prev;
	q->dep[p].next = n;
	q->dep[n].prev = p;
	d = q->qs[x].qlen;
	if (q->max_depth < d)
		q->max_depth = d;

	sfq_link(q, x);
}

static unsigned int sfq_drop(struct Qdisc *sch)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	sfq_index d = q->max_depth;
	struct sk_buff *skb;
	unsigned int len;

	/* Queue is full! Find the longest slot and
	   drop a packet from it */

	if (d > 1) {
247
		sfq_index x = q->dep[d + SFQ_DEPTH].next;
L
Linus Torvalds 已提交
248
		skb = q->qs[x].prev;
249
		len = qdisc_pkt_len(skb);
L
Linus Torvalds 已提交
250 251 252 253 254
		__skb_unlink(skb, &q->qs[x]);
		kfree_skb(skb);
		sfq_dec(q, x);
		sch->q.qlen--;
		sch->qstats.drops++;
255
		sch->qstats.backlog -= len;
L
Linus Torvalds 已提交
256 257 258 259 260 261 262 263 264
		return len;
	}

	if (d == 1) {
		/* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
		d = q->next[q->tail];
		q->next[q->tail] = q->next[d];
		q->allot[q->next[d]] += q->quantum;
		skb = q->qs[d].prev;
265
		len = qdisc_pkt_len(skb);
L
Linus Torvalds 已提交
266 267 268 269 270 271
		__skb_unlink(skb, &q->qs[d]);
		kfree_skb(skb);
		sfq_dec(q, d);
		sch->q.qlen--;
		q->ht[q->hash[d]] = SFQ_DEPTH;
		sch->qstats.drops++;
272
		sch->qstats.backlog -= len;
L
Linus Torvalds 已提交
273 274 275 276 277 278 279
		return len;
	}

	return 0;
}

static int
280
sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
L
Linus Torvalds 已提交
281 282
{
	struct sfq_sched_data *q = qdisc_priv(sch);
283
	unsigned int hash;
L
Linus Torvalds 已提交
284
	sfq_index x;
285
	int uninitialized_var(ret);
286 287 288

	hash = sfq_classify(skb, sch, &ret);
	if (hash == 0) {
289
		if (ret & __NET_XMIT_BYPASS)
290 291 292 293 294
			sch->qstats.drops++;
		kfree_skb(skb);
		return ret;
	}
	hash--;
L
Linus Torvalds 已提交
295 296 297 298 299 300

	x = q->ht[hash];
	if (x == SFQ_DEPTH) {
		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
		q->hash[x] = hash;
	}
301

302 303 304 305 306 307 308
	/* If selected queue has length q->limit, this means that
	 * all another queues are empty and that we do simple tail drop,
	 * i.e. drop _this_ packet.
	 */
	if (q->qs[x].qlen >= q->limit)
		return qdisc_drop(skb, sch);

309
	sch->qstats.backlog += qdisc_pkt_len(skb);
L
Linus Torvalds 已提交
310 311 312 313 314 315 316 317 318 319 320 321 322
	__skb_queue_tail(&q->qs[x], skb);
	sfq_inc(q, x);
	if (q->qs[x].qlen == 1) {		/* The flow is new */
		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
			q->tail = x;
			q->next[x] = x;
			q->allot[x] = q->quantum;
		} else {
			q->next[x] = q->next[q->tail];
			q->next[q->tail] = x;
			q->tail = x;
		}
	}
323
	if (++sch->q.qlen <= q->limit) {
324
		sch->bstats.bytes += qdisc_pkt_len(skb);
L
Linus Torvalds 已提交
325 326 327 328 329 330 331 332
		sch->bstats.packets++;
		return 0;
	}

	sfq_drop(sch);
	return NET_XMIT_CN;
}

333 334 335 336 337
static struct sk_buff *
sfq_peek(struct Qdisc *sch)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	sfq_index a;
L
Linus Torvalds 已提交
338

339 340 341
	/* No active slots */
	if (q->tail == SFQ_DEPTH)
		return NULL;
L
Linus Torvalds 已提交
342

343 344 345
	a = q->next[q->tail];
	return skb_peek(&q->qs[a]);
}
L
Linus Torvalds 已提交
346 347

static struct sk_buff *
348
sfq_dequeue(struct Qdisc *sch)
L
Linus Torvalds 已提交
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	struct sk_buff *skb;
	sfq_index a, old_a;

	/* No active slots */
	if (q->tail == SFQ_DEPTH)
		return NULL;

	a = old_a = q->next[q->tail];

	/* Grab packet */
	skb = __skb_dequeue(&q->qs[a]);
	sfq_dec(q, a);
	sch->q.qlen--;
364
	sch->qstats.backlog -= qdisc_pkt_len(skb);
L
Linus Torvalds 已提交
365 366 367 368 369 370 371 372 373 374 375

	/* Is the slot empty? */
	if (q->qs[a].qlen == 0) {
		q->ht[q->hash[a]] = SFQ_DEPTH;
		a = q->next[a];
		if (a == old_a) {
			q->tail = SFQ_DEPTH;
			return skb;
		}
		q->next[q->tail] = a;
		q->allot[a] += q->quantum;
376
	} else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
L
Linus Torvalds 已提交
377 378 379 380 381 382 383 384
		q->tail = a;
		a = q->next[a];
		q->allot[a] += q->quantum;
	}
	return skb;
}

static void
385
sfq_reset(struct Qdisc *sch)
L
Linus Torvalds 已提交
386 387 388 389 390 391 392 393 394
{
	struct sk_buff *skb;

	while ((skb = sfq_dequeue(sch)) != NULL)
		kfree_skb(skb);
}

static void sfq_perturbation(unsigned long arg)
{
395
	struct Qdisc *sch = (struct Qdisc *)arg;
L
Linus Torvalds 已提交
396 397
	struct sfq_sched_data *q = qdisc_priv(sch);

398
	q->perturbation = net_random();
L
Linus Torvalds 已提交
399

400 401
	if (q->perturb_period)
		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
L
Linus Torvalds 已提交
402 403
}

404
static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
L
Linus Torvalds 已提交
405 406
{
	struct sfq_sched_data *q = qdisc_priv(sch);
407
	struct tc_sfq_qopt *ctl = nla_data(opt);
408
	unsigned int qlen;
L
Linus Torvalds 已提交
409

410
	if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
L
Linus Torvalds 已提交
411 412 413
		return -EINVAL;

	sch_tree_lock(sch);
414
	q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
415
	q->perturb_period = ctl->perturb_period * HZ;
L
Linus Torvalds 已提交
416
	if (ctl->limit)
417
		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
L
Linus Torvalds 已提交
418

419
	qlen = sch->q.qlen;
420
	while (sch->q.qlen > q->limit)
L
Linus Torvalds 已提交
421
		sfq_drop(sch);
422
	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
L
Linus Torvalds 已提交
423 424 425

	del_timer(&q->perturb_timer);
	if (q->perturb_period) {
426
		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
427
		q->perturbation = net_random();
L
Linus Torvalds 已提交
428 429 430 431 432
	}
	sch_tree_unlock(sch);
	return 0;
}

433
static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
L
Linus Torvalds 已提交
434 435 436 437
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	int i;

438
	q->perturb_timer.function = sfq_perturbation;
439
	q->perturb_timer.data = (unsigned long)sch;
440
	init_timer_deferrable(&q->perturb_timer);
L
Linus Torvalds 已提交
441

442
	for (i = 0; i < SFQ_HASH_DIVISOR; i++)
L
Linus Torvalds 已提交
443
		q->ht[i] = SFQ_DEPTH;
444 445

	for (i = 0; i < SFQ_DEPTH; i++) {
L
Linus Torvalds 已提交
446
		skb_queue_head_init(&q->qs[i]);
447 448
		q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
		q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
L
Linus Torvalds 已提交
449
	}
450

451
	q->limit = SFQ_DEPTH - 1;
L
Linus Torvalds 已提交
452 453 454
	q->max_depth = 0;
	q->tail = SFQ_DEPTH;
	if (opt == NULL) {
455
		q->quantum = psched_mtu(qdisc_dev(sch));
L
Linus Torvalds 已提交
456
		q->perturb_period = 0;
457
		q->perturbation = net_random();
L
Linus Torvalds 已提交
458 459 460 461 462
	} else {
		int err = sfq_change(sch, opt);
		if (err)
			return err;
	}
463 464

	for (i = 0; i < SFQ_DEPTH; i++)
L
Linus Torvalds 已提交
465 466 467 468 469 470 471
		sfq_link(q, i);
	return 0;
}

static void sfq_destroy(struct Qdisc *sch)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
472

473
	tcf_destroy_chain(&q->filter_list);
474 475
	q->perturb_period = 0;
	del_timer_sync(&q->perturb_timer);
L
Linus Torvalds 已提交
476 477 478 479 480
}

static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
481
	unsigned char *b = skb_tail_pointer(skb);
L
Linus Torvalds 已提交
482 483 484
	struct tc_sfq_qopt opt;

	opt.quantum = q->quantum;
485
	opt.perturb_period = q->perturb_period / HZ;
L
Linus Torvalds 已提交
486 487 488

	opt.limit = q->limit;
	opt.divisor = SFQ_HASH_DIVISOR;
489
	opt.flows = q->limit;
L
Linus Torvalds 已提交
490

491
	NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
L
Linus Torvalds 已提交
492 493 494

	return skb->len;

495
nla_put_failure:
496
	nlmsg_trim(skb, b);
L
Linus Torvalds 已提交
497 498 499
	return -1;
}

500 501 502 503 504 505 506 507 508 509 510 511 512 513
static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
{
	return 0;
}

static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
{
	struct sfq_sched_data *q = qdisc_priv(sch);

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

514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533
static int sfq_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 sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
				struct gnet_dump *d)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	sfq_index idx = q->ht[cl-1];
	struct gnet_stats_queue qs = { .qlen = q->qs[idx].qlen };
	struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };

	if (gnet_stats_copy_queue(d, &qs) < 0)
		return -1;
	return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
}

534 535
static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553
	struct sfq_sched_data *q = qdisc_priv(sch);
	unsigned int i;

	if (arg->stop)
		return;

	for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
		if (q->ht[i] == SFQ_DEPTH ||
		    arg->count < arg->skip) {
			arg->count++;
			continue;
		}
		if (arg->fn(sch, i + 1, arg) < 0) {
			arg->stop = 1;
			break;
		}
		arg->count++;
	}
554 555 556 557 558
}

static const struct Qdisc_class_ops sfq_class_ops = {
	.get		=	sfq_get,
	.tcf_chain	=	sfq_find_tcf,
559 560
	.dump		=	sfq_dump_class,
	.dump_stats	=	sfq_dump_class_stats,
561 562 563
	.walk		=	sfq_walk,
};

564
static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
565
	.cl_ops		=	&sfq_class_ops,
L
Linus Torvalds 已提交
566 567 568 569
	.id		=	"sfq",
	.priv_size	=	sizeof(struct sfq_sched_data),
	.enqueue	=	sfq_enqueue,
	.dequeue	=	sfq_dequeue,
570
	.peek		=	sfq_peek,
L
Linus Torvalds 已提交
571 572 573 574 575 576 577 578 579 580 581 582 583
	.drop		=	sfq_drop,
	.init		=	sfq_init,
	.reset		=	sfq_reset,
	.destroy	=	sfq_destroy,
	.change		=	NULL,
	.dump		=	sfq_dump,
	.owner		=	THIS_MODULE,
};

static int __init sfq_module_init(void)
{
	return register_qdisc(&sfq_qdisc_ops);
}
584
static void __exit sfq_module_exit(void)
L
Linus Torvalds 已提交
585 586 587 588 589 590
{
	unregister_qdisc(&sfq_qdisc_ops);
}
module_init(sfq_module_init)
module_exit(sfq_module_exit)
MODULE_LICENSE("GPL");