sch_sfq.c 13.7 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 24
#include <net/ip.h>
#include <net/netlink.h>
L
Linus Torvalds 已提交
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
#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.


44
	This is not the thing that is usually called (W)FQ nowadays.
L
Linus Torvalds 已提交
45 46 47 48 49 50 51 52 53
	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:

54
	- "Stochastic" -> It is not 100% fair.
L
Linus Torvalds 已提交
55 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
	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 */
98
	struct tcf_proto *filter_list;
L
Linus Torvalds 已提交
99
	struct timer_list perturb_timer;
100
	u32		perturbation;
L
Linus Torvalds 已提交
101 102 103 104 105 106 107 108 109 110 111 112 113
	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)
{
114
	return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
L
Linus Torvalds 已提交
115 116 117 118 119 120 121 122 123
}

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

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

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

159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
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;

	*qerr = NET_XMIT_BYPASS;
	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:
			*qerr = NET_XMIT_SUCCESS;
		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 已提交
192 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
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) {
246
		sfq_index x = q->dep[d + SFQ_DEPTH].next;
L
Linus Torvalds 已提交
247 248 249 250 251 252 253
		skb = q->qs[x].prev;
		len = skb->len;
		__skb_unlink(skb, &q->qs[x]);
		kfree_skb(skb);
		sfq_dec(q, x);
		sch->q.qlen--;
		sch->qstats.drops++;
254
		sch->qstats.backlog -= len;
L
Linus Torvalds 已提交
255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
		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;
		len = skb->len;
		__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++;
271
		sch->qstats.backlog -= len;
L
Linus Torvalds 已提交
272 273 274 275 276 277 278
		return len;
	}

	return 0;
}

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

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

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

301 302 303 304 305 306 307
	/* 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);

308
	sch->qstats.backlog += skb->len;
L
Linus Torvalds 已提交
309 310 311 312 313 314 315 316 317 318 319 320 321
	__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;
		}
	}
322
	if (++sch->q.qlen <= q->limit) {
L
Linus Torvalds 已提交
323 324 325 326 327 328 329 330 331 332
		sch->bstats.bytes += skb->len;
		sch->bstats.packets++;
		return 0;
	}

	sfq_drop(sch);
	return NET_XMIT_CN;
}

static int
333
sfq_requeue(struct sk_buff *skb, struct Qdisc *sch)
L
Linus Torvalds 已提交
334 335
{
	struct sfq_sched_data *q = qdisc_priv(sch);
336
	unsigned int hash;
L
Linus Torvalds 已提交
337
	sfq_index x;
338 339 340 341 342 343 344 345 346 347
	int ret;

	hash = sfq_classify(skb, sch, &ret);
	if (hash == 0) {
		if (ret == NET_XMIT_BYPASS)
			sch->qstats.drops++;
		kfree_skb(skb);
		return ret;
	}
	hash--;
L
Linus Torvalds 已提交
348 349 350 351 352 353

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

355
	sch->qstats.backlog += skb->len;
L
Linus Torvalds 已提交
356
	__skb_queue_head(&q->qs[x], skb);
357 358 359 360 361 362 363 364 365 366 367 368 369
	/* If selected queue has length q->limit+1, this means that
	 * all another queues are empty and we do simple tail drop.
	 * This packet is still requeued at head of queue, tail packet
	 * is dropped.
	 */
	if (q->qs[x].qlen > q->limit) {
		skb = q->qs[x].prev;
		__skb_unlink(skb, &q->qs[x]);
		sch->qstats.drops++;
		sch->qstats.backlog -= skb->len;
		kfree_skb(skb);
		return NET_XMIT_CN;
	}
370

L
Linus Torvalds 已提交
371 372 373 374 375 376 377 378 379 380 381 382
	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;
		}
	}
383

384
	if (++sch->q.qlen <= q->limit) {
L
Linus Torvalds 已提交
385 386 387 388 389 390 391 392 393 394 395 396 397
		sch->qstats.requeues++;
		return 0;
	}

	sch->qstats.drops++;
	sfq_drop(sch);
	return NET_XMIT_CN;
}




static struct sk_buff *
398
sfq_dequeue(struct Qdisc *sch)
L
Linus Torvalds 已提交
399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
{
	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--;
414
	sch->qstats.backlog -= skb->len;
L
Linus Torvalds 已提交
415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434

	/* 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;
	} else if ((q->allot[a] -= skb->len) <= 0) {
		q->tail = a;
		a = q->next[a];
		q->allot[a] += q->quantum;
	}
	return skb;
}

static void
435
sfq_reset(struct Qdisc *sch)
L
Linus Torvalds 已提交
436 437 438 439 440 441 442 443 444
{
	struct sk_buff *skb;

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

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

448
	q->perturbation = net_random();
L
Linus Torvalds 已提交
449

450 451
	if (q->perturb_period)
		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
L
Linus Torvalds 已提交
452 453
}

454
static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
L
Linus Torvalds 已提交
455 456
{
	struct sfq_sched_data *q = qdisc_priv(sch);
457
	struct tc_sfq_qopt *ctl = nla_data(opt);
458
	unsigned int qlen;
L
Linus Torvalds 已提交
459

460
	if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
L
Linus Torvalds 已提交
461 462 463 464
		return -EINVAL;

	sch_tree_lock(sch);
	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
465
	q->perturb_period = ctl->perturb_period * HZ;
L
Linus Torvalds 已提交
466
	if (ctl->limit)
467
		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
L
Linus Torvalds 已提交
468

469
	qlen = sch->q.qlen;
470
	while (sch->q.qlen > q->limit)
L
Linus Torvalds 已提交
471
		sfq_drop(sch);
472
	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
L
Linus Torvalds 已提交
473 474 475

	del_timer(&q->perturb_timer);
	if (q->perturb_period) {
476
		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
477
		q->perturbation = net_random();
L
Linus Torvalds 已提交
478 479 480 481 482
	}
	sch_tree_unlock(sch);
	return 0;
}

483
static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
L
Linus Torvalds 已提交
484 485 486 487
{
	struct sfq_sched_data *q = qdisc_priv(sch);
	int i;

488 489 490
	q->perturb_timer.function = sfq_perturbation;
	q->perturb_timer.data = (unsigned long)sch;;
	init_timer_deferrable(&q->perturb_timer);
L
Linus Torvalds 已提交
491

492
	for (i = 0; i < SFQ_HASH_DIVISOR; i++)
L
Linus Torvalds 已提交
493
		q->ht[i] = SFQ_DEPTH;
494 495

	for (i = 0; i < SFQ_DEPTH; i++) {
L
Linus Torvalds 已提交
496
		skb_queue_head_init(&q->qs[i]);
497 498
		q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
		q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
L
Linus Torvalds 已提交
499
	}
500

501
	q->limit = SFQ_DEPTH - 1;
L
Linus Torvalds 已提交
502 503 504 505 506
	q->max_depth = 0;
	q->tail = SFQ_DEPTH;
	if (opt == NULL) {
		q->quantum = psched_mtu(sch->dev);
		q->perturb_period = 0;
507
		q->perturbation = net_random();
L
Linus Torvalds 已提交
508 509 510 511 512
	} else {
		int err = sfq_change(sch, opt);
		if (err)
			return err;
	}
513 514

	for (i = 0; i < SFQ_DEPTH; i++)
L
Linus Torvalds 已提交
515 516 517 518 519 520 521
		sfq_link(q, i);
	return 0;
}

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

	tcf_destroy_chain(q->filter_list);
L
Linus Torvalds 已提交
524 525 526 527 528 529
	del_timer(&q->perturb_timer);
}

static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct sfq_sched_data *q = qdisc_priv(sch);
530
	unsigned char *b = skb_tail_pointer(skb);
L
Linus Torvalds 已提交
531 532 533
	struct tc_sfq_qopt opt;

	opt.quantum = q->quantum;
534
	opt.perturb_period = q->perturb_period / HZ;
L
Linus Torvalds 已提交
535 536 537 538 539

	opt.limit = q->limit;
	opt.divisor = SFQ_HASH_DIVISOR;
	opt.flows = q->limit;

540
	NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
L
Linus Torvalds 已提交
541 542 543

	return skb->len;

544
nla_put_failure:
545
	nlmsg_trim(skb, b);
L
Linus Torvalds 已提交
546 547 548
	return -1;
}

549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
static int sfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
			    struct nlattr **tca, unsigned long *arg)
{
	return -EOPNOTSUPP;
}

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;
}

static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
	return;
}

static const struct Qdisc_class_ops sfq_class_ops = {
	.get		=	sfq_get,
	.change		=	sfq_change_class,
	.tcf_chain	=	sfq_find_tcf,
	.walk		=	sfq_walk,
};

581
static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
582
	.cl_ops		=	&sfq_class_ops,
L
Linus Torvalds 已提交
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
	.id		=	"sfq",
	.priv_size	=	sizeof(struct sfq_sched_data),
	.enqueue	=	sfq_enqueue,
	.dequeue	=	sfq_dequeue,
	.requeue	=	sfq_requeue,
	.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);
}
601
static void __exit sfq_module_exit(void)
L
Linus Torvalds 已提交
602 603 604 605 606 607
{
	unregister_qdisc(&sfq_qdisc_ops);
}
module_init(sfq_module_init)
module_exit(sfq_module_exit)
MODULE_LICENSE("GPL");