Blame view

net/sched/sch_sfb.c 16.8 KB
d2912cb15   Thomas Gleixner   treewide: Replace...
1
  // SPDX-License-Identifier: GPL-2.0-only
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
2
3
4
5
6
7
  /*
   * net/sched/sch_sfb.c	  Stochastic Fair Blue
   *
   * Copyright (c) 2008-2011 Juliusz Chroboczek <jch@pps.jussieu.fr>
   * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com>
   *
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
8
9
10
11
12
   * W. Feng, D. Kandlur, D. Saha, K. Shin. Blue:
   * A New Class of Active Queue Management Algorithms.
   * U. Michigan CSE-TR-387-99, April 1999.
   *
   * http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
13
14
15
16
17
18
19
20
   */
  
  #include <linux/module.h>
  #include <linux/types.h>
  #include <linux/kernel.h>
  #include <linux/errno.h>
  #include <linux/skbuff.h>
  #include <linux/random.h>
55667441c   Eric Dumazet   net/flow_dissecto...
21
  #include <linux/siphash.h>
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
22
23
  #include <net/ip.h>
  #include <net/pkt_sched.h>
cf1facda2   Jiri Pirko   sched: move tcf_p...
24
  #include <net/pkt_cls.h>
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
  #include <net/inet_ecn.h>
  
  /*
   * SFB uses two B[l][n] : L x N arrays of bins (L levels, N bins per level)
   * This implementation uses L = 8 and N = 16
   * This permits us to split one 32bit hash (provided per packet by rxhash or
   * external classifier) into 8 subhashes of 4 bits.
   */
  #define SFB_BUCKET_SHIFT 4
  #define SFB_NUMBUCKETS	(1 << SFB_BUCKET_SHIFT) /* N bins per Level */
  #define SFB_BUCKET_MASK (SFB_NUMBUCKETS - 1)
  #define SFB_LEVELS	(32 / SFB_BUCKET_SHIFT) /* L */
  
  /* SFB algo uses a virtual queue, named "bin" */
  struct sfb_bucket {
  	u16		qlen; /* length of virtual queue */
  	u16		p_mark; /* marking probability */
  };
  
  /* We use a double buffering right before hash change
   * (Section 4.4 of SFB reference : moving hash functions)
   */
  struct sfb_bins {
55667441c   Eric Dumazet   net/flow_dissecto...
48
  	siphash_key_t	  perturbation; /* siphash key */
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
49
50
51
52
53
  	struct sfb_bucket bins[SFB_LEVELS][SFB_NUMBUCKETS];
  };
  
  struct sfb_sched_data {
  	struct Qdisc	*qdisc;
25d8c0d55   John Fastabend   net: rcu-ify tcf_...
54
  	struct tcf_proto __rcu *filter_list;
6529eaba3   Jiri Pirko   net: sched: intro...
55
  	struct tcf_block *block;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
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
  	unsigned long	rehash_interval;
  	unsigned long	warmup_time;	/* double buffering warmup time in jiffies */
  	u32		max;
  	u32		bin_size;	/* maximum queue length per bin */
  	u32		increment;	/* d1 */
  	u32		decrement;	/* d2 */
  	u32		limit;		/* HARD maximal queue length */
  	u32		penalty_rate;
  	u32		penalty_burst;
  	u32		tokens_avail;
  	unsigned long	rehash_time;
  	unsigned long	token_time;
  
  	u8		slot;		/* current active bins (0 or 1) */
  	bool		double_buffering;
  	struct sfb_bins bins[2];
  
  	struct {
  		u32	earlydrop;
  		u32	penaltydrop;
  		u32	bucketdrop;
  		u32	queuedrop;
  		u32	childdrop;	/* drops in child qdisc */
  		u32	marked;		/* ECN mark */
  	} stats;
  };
  
  /*
   * Each queued skb might be hashed on one or two bins
   * We store in skb_cb the two hash values.
   * (A zero value means double buffering was not used)
   */
  struct sfb_skb_cb {
  	u32 hashes[2];
  };
  
  static inline struct sfb_skb_cb *sfb_skb_cb(const struct sk_buff *skb)
  {
16bda13d9   David S. Miller   net: Make qdisc_s...
94
  	qdisc_cb_private_validate(skb, sizeof(struct sfb_skb_cb));
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
95
96
97
98
99
100
101
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
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
  	return (struct sfb_skb_cb *)qdisc_skb_cb(skb)->data;
  }
  
  /*
   * If using 'internal' SFB flow classifier, hash comes from skb rxhash
   * If using external classifier, hash comes from the classid.
   */
  static u32 sfb_hash(const struct sk_buff *skb, u32 slot)
  {
  	return sfb_skb_cb(skb)->hashes[slot];
  }
  
  /* Probabilities are coded as Q0.16 fixed-point values,
   * with 0xFFFF representing 65535/65536 (almost 1.0)
   * Addition and subtraction are saturating in [0, 65535]
   */
  static u32 prob_plus(u32 p1, u32 p2)
  {
  	u32 res = p1 + p2;
  
  	return min_t(u32, res, SFB_MAX_PROB);
  }
  
  static u32 prob_minus(u32 p1, u32 p2)
  {
  	return p1 > p2 ? p1 - p2 : 0;
  }
  
  static void increment_one_qlen(u32 sfbhash, u32 slot, struct sfb_sched_data *q)
  {
  	int i;
  	struct sfb_bucket *b = &q->bins[slot].bins[0][0];
  
  	for (i = 0; i < SFB_LEVELS; i++) {
  		u32 hash = sfbhash & SFB_BUCKET_MASK;
  
  		sfbhash >>= SFB_BUCKET_SHIFT;
  		if (b[hash].qlen < 0xFFFF)
  			b[hash].qlen++;
  		b += SFB_NUMBUCKETS; /* next level */
  	}
  }
  
  static void increment_qlen(const struct sk_buff *skb, struct sfb_sched_data *q)
  {
  	u32 sfbhash;
  
  	sfbhash = sfb_hash(skb, 0);
  	if (sfbhash)
  		increment_one_qlen(sfbhash, 0, q);
  
  	sfbhash = sfb_hash(skb, 1);
  	if (sfbhash)
  		increment_one_qlen(sfbhash, 1, q);
  }
  
  static void decrement_one_qlen(u32 sfbhash, u32 slot,
  			       struct sfb_sched_data *q)
  {
  	int i;
  	struct sfb_bucket *b = &q->bins[slot].bins[0][0];
  
  	for (i = 0; i < SFB_LEVELS; i++) {
  		u32 hash = sfbhash & SFB_BUCKET_MASK;
  
  		sfbhash >>= SFB_BUCKET_SHIFT;
  		if (b[hash].qlen > 0)
  			b[hash].qlen--;
  		b += SFB_NUMBUCKETS; /* next level */
  	}
  }
  
  static void decrement_qlen(const struct sk_buff *skb, struct sfb_sched_data *q)
  {
  	u32 sfbhash;
  
  	sfbhash = sfb_hash(skb, 0);
  	if (sfbhash)
  		decrement_one_qlen(sfbhash, 0, q);
  
  	sfbhash = sfb_hash(skb, 1);
  	if (sfbhash)
  		decrement_one_qlen(sfbhash, 1, q);
  }
  
  static void decrement_prob(struct sfb_bucket *b, struct sfb_sched_data *q)
  {
  	b->p_mark = prob_minus(b->p_mark, q->decrement);
  }
  
  static void increment_prob(struct sfb_bucket *b, struct sfb_sched_data *q)
  {
  	b->p_mark = prob_plus(b->p_mark, q->increment);
  }
  
  static void sfb_zero_all_buckets(struct sfb_sched_data *q)
  {
  	memset(&q->bins, 0, sizeof(q->bins));
  }
  
  /*
   * compute max qlen, max p_mark, and avg p_mark
   */
  static u32 sfb_compute_qlen(u32 *prob_r, u32 *avgpm_r, const struct sfb_sched_data *q)
  {
  	int i;
  	u32 qlen = 0, prob = 0, totalpm = 0;
  	const struct sfb_bucket *b = &q->bins[q->slot].bins[0][0];
  
  	for (i = 0; i < SFB_LEVELS * SFB_NUMBUCKETS; i++) {
  		if (qlen < b->qlen)
  			qlen = b->qlen;
  		totalpm += b->p_mark;
  		if (prob < b->p_mark)
  			prob = b->p_mark;
  		b++;
  	}
  	*prob_r = prob;
  	*avgpm_r = totalpm / (SFB_LEVELS * SFB_NUMBUCKETS);
  	return qlen;
  }
  
  
  static void sfb_init_perturbation(u32 slot, struct sfb_sched_data *q)
  {
55667441c   Eric Dumazet   net/flow_dissecto...
220
221
  	get_random_bytes(&q->bins[slot].perturbation,
  			 sizeof(q->bins[slot].perturbation));
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
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
247
248
249
250
251
252
  }
  
  static void sfb_swap_slot(struct sfb_sched_data *q)
  {
  	sfb_init_perturbation(q->slot, q);
  	q->slot ^= 1;
  	q->double_buffering = false;
  }
  
  /* Non elastic flows are allowed to use part of the bandwidth, expressed
   * in "penalty_rate" packets per second, with "penalty_burst" burst
   */
  static bool sfb_rate_limit(struct sk_buff *skb, struct sfb_sched_data *q)
  {
  	if (q->penalty_rate == 0 || q->penalty_burst == 0)
  		return true;
  
  	if (q->tokens_avail < 1) {
  		unsigned long age = min(10UL * HZ, jiffies - q->token_time);
  
  		q->tokens_avail = (age * q->penalty_rate) / HZ;
  		if (q->tokens_avail > q->penalty_burst)
  			q->tokens_avail = q->penalty_burst;
  		q->token_time = jiffies;
  		if (q->tokens_avail < 1)
  			return true;
  	}
  
  	q->tokens_avail--;
  	return false;
  }
25d8c0d55   John Fastabend   net: rcu-ify tcf_...
253
  static bool sfb_classify(struct sk_buff *skb, struct tcf_proto *fl,
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
254
255
256
257
  			 int *qerr, u32 *salt)
  {
  	struct tcf_result res;
  	int result;
87d83093b   Jiri Pirko   net: sched: move ...
258
  	result = tcf_classify(skb, fl, &res, false);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
259
260
261
262
263
  	if (result >= 0) {
  #ifdef CONFIG_NET_CLS_ACT
  		switch (result) {
  		case TC_ACT_STOLEN:
  		case TC_ACT_QUEUED:
e25ea21ff   Jiri Pirko   net: sched: intro...
264
  		case TC_ACT_TRAP:
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
265
  			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
f3ae608ed   Gustavo A. R. Silva   net: sched: mark ...
266
  			/* fall through */
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
267
268
269
270
271
272
273
274
275
  		case TC_ACT_SHOT:
  			return false;
  		}
  #endif
  		*salt = TC_H_MIN(res.classid);
  		return true;
  	}
  	return false;
  }
520ac30f4   Eric Dumazet   net_sched: drop p...
276
277
  static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch,
  		       struct sk_buff **to_free)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
278
279
280
281
  {
  
  	struct sfb_sched_data *q = qdisc_priv(sch);
  	struct Qdisc *child = q->qdisc;
25d8c0d55   John Fastabend   net: rcu-ify tcf_...
282
  	struct tcf_proto *fl;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
283
284
285
  	int i;
  	u32 p_min = ~0;
  	u32 minqlen = ~0;
63c0ad4d4   Tom Herbert   sched: Call skb_g...
286
287
  	u32 r, sfbhash;
  	u32 slot = q->slot;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
288
  	int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
363437f40   Eric Dumazet   net_sched: sfb: o...
289
  	if (unlikely(sch->q.qlen >= q->limit)) {
25331d6ce   John Fastabend   net: sched: imple...
290
  		qdisc_qstats_overlimit(sch);
363437f40   Eric Dumazet   net_sched: sfb: o...
291
292
293
  		q->stats.queuedrop++;
  		goto drop;
  	}
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
294
295
296
297
298
299
300
301
302
303
304
  	if (q->rehash_interval > 0) {
  		unsigned long limit = q->rehash_time + q->rehash_interval;
  
  		if (unlikely(time_after(jiffies, limit))) {
  			sfb_swap_slot(q);
  			q->rehash_time = jiffies;
  		} else if (unlikely(!q->double_buffering && q->warmup_time > 0 &&
  				    time_after(jiffies, limit - q->warmup_time))) {
  			q->double_buffering = true;
  		}
  	}
25d8c0d55   John Fastabend   net: rcu-ify tcf_...
305
306
  	fl = rcu_dereference_bh(q->filter_list);
  	if (fl) {
63c0ad4d4   Tom Herbert   sched: Call skb_g...
307
  		u32 salt;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
308
  		/* If using external classifiers, get result and record it. */
25d8c0d55   John Fastabend   net: rcu-ify tcf_...
309
  		if (!sfb_classify(skb, fl, &ret, &salt))
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
310
  			goto other_drop;
55667441c   Eric Dumazet   net/flow_dissecto...
311
  		sfbhash = siphash_1u32(salt, &q->bins[slot].perturbation);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
312
  	} else {
55667441c   Eric Dumazet   net/flow_dissecto...
313
  		sfbhash = skb_get_hash_perturb(skb, &q->bins[slot].perturbation);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
314
  	}
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
315

e13e02a3c   Eric Dumazet   net_sched: SFB fl...
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
  	if (!sfbhash)
  		sfbhash = 1;
  	sfb_skb_cb(skb)->hashes[slot] = sfbhash;
  
  	for (i = 0; i < SFB_LEVELS; i++) {
  		u32 hash = sfbhash & SFB_BUCKET_MASK;
  		struct sfb_bucket *b = &q->bins[slot].bins[i][hash];
  
  		sfbhash >>= SFB_BUCKET_SHIFT;
  		if (b->qlen == 0)
  			decrement_prob(b, q);
  		else if (b->qlen >= q->bin_size)
  			increment_prob(b, q);
  		if (minqlen > b->qlen)
  			minqlen = b->qlen;
  		if (p_min > b->p_mark)
  			p_min = b->p_mark;
  	}
  
  	slot ^= 1;
  	sfb_skb_cb(skb)->hashes[slot] = 0;
363437f40   Eric Dumazet   net_sched: sfb: o...
337
  	if (unlikely(minqlen >= q->max)) {
25331d6ce   John Fastabend   net: sched: imple...
338
  		qdisc_qstats_overlimit(sch);
363437f40   Eric Dumazet   net_sched: sfb: o...
339
  		q->stats.bucketdrop++;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
340
341
342
343
344
345
  		goto drop;
  	}
  
  	if (unlikely(p_min >= SFB_MAX_PROB)) {
  		/* Inelastic flow */
  		if (q->double_buffering) {
63c0ad4d4   Tom Herbert   sched: Call skb_g...
346
  			sfbhash = skb_get_hash_perturb(skb,
55667441c   Eric Dumazet   net/flow_dissecto...
347
  			    &q->bins[slot].perturbation);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
  			if (!sfbhash)
  				sfbhash = 1;
  			sfb_skb_cb(skb)->hashes[slot] = sfbhash;
  
  			for (i = 0; i < SFB_LEVELS; i++) {
  				u32 hash = sfbhash & SFB_BUCKET_MASK;
  				struct sfb_bucket *b = &q->bins[slot].bins[i][hash];
  
  				sfbhash >>= SFB_BUCKET_SHIFT;
  				if (b->qlen == 0)
  					decrement_prob(b, q);
  				else if (b->qlen >= q->bin_size)
  					increment_prob(b, q);
  			}
  		}
  		if (sfb_rate_limit(skb, q)) {
25331d6ce   John Fastabend   net: sched: imple...
364
  			qdisc_qstats_overlimit(sch);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
365
366
367
368
369
  			q->stats.penaltydrop++;
  			goto drop;
  		}
  		goto enqueue;
  	}
63862b5be   Aruna-Hewapathirane   net: replace macr...
370
  	r = prandom_u32() & SFB_MAX_PROB;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
  
  	if (unlikely(r < p_min)) {
  		if (unlikely(p_min > SFB_MAX_PROB / 2)) {
  			/* If we're marking that many packets, then either
  			 * this flow is unresponsive, or we're badly congested.
  			 * In either case, we want to start dropping packets.
  			 */
  			if (r < (p_min - SFB_MAX_PROB / 2) * 2) {
  				q->stats.earlydrop++;
  				goto drop;
  			}
  		}
  		if (INET_ECN_set_ce(skb)) {
  			q->stats.marked++;
  		} else {
  			q->stats.earlydrop++;
  			goto drop;
  		}
  	}
  
  enqueue:
520ac30f4   Eric Dumazet   net_sched: drop p...
392
  	ret = qdisc_enqueue(skb, child, to_free);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
393
  	if (likely(ret == NET_XMIT_SUCCESS)) {
3d4357fba   WANG Cong   sch_sfb: keep bac...
394
  		qdisc_qstats_backlog_inc(sch, skb);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
395
396
397
398
  		sch->q.qlen++;
  		increment_qlen(skb, q);
  	} else if (net_xmit_drop_count(ret)) {
  		q->stats.childdrop++;
25331d6ce   John Fastabend   net: sched: imple...
399
  		qdisc_qstats_drop(sch);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
400
401
402
403
  	}
  	return ret;
  
  drop:
520ac30f4   Eric Dumazet   net_sched: drop p...
404
  	qdisc_drop(skb, sch, to_free);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
405
406
407
  	return NET_XMIT_CN;
  other_drop:
  	if (ret & __NET_XMIT_BYPASS)
25331d6ce   John Fastabend   net: sched: imple...
408
  		qdisc_qstats_drop(sch);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
409
410
411
412
413
414
415
416
417
418
419
420
421
422
  	kfree_skb(skb);
  	return ret;
  }
  
  static struct sk_buff *sfb_dequeue(struct Qdisc *sch)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  	struct Qdisc *child = q->qdisc;
  	struct sk_buff *skb;
  
  	skb = child->dequeue(q->qdisc);
  
  	if (skb) {
  		qdisc_bstats_update(sch, skb);
3d4357fba   WANG Cong   sch_sfb: keep bac...
423
  		qdisc_qstats_backlog_dec(sch, skb);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
  		sch->q.qlen--;
  		decrement_qlen(skb, q);
  	}
  
  	return skb;
  }
  
  static struct sk_buff *sfb_peek(struct Qdisc *sch)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  	struct Qdisc *child = q->qdisc;
  
  	return child->ops->peek(child);
  }
  
  /* No sfb_drop -- impossible since the child doesn't return the dropped skb. */
  
  static void sfb_reset(struct Qdisc *sch)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  
  	qdisc_reset(q->qdisc);
3d4357fba   WANG Cong   sch_sfb: keep bac...
446
  	sch->qstats.backlog = 0;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
447
448
449
450
451
452
453
454
455
456
  	sch->q.qlen = 0;
  	q->slot = 0;
  	q->double_buffering = false;
  	sfb_zero_all_buckets(q);
  	sfb_init_perturbation(0, q);
  }
  
  static void sfb_destroy(struct Qdisc *sch)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
6529eaba3   Jiri Pirko   net: sched: intro...
457
  	tcf_block_put(q->block);
86bd446b5   Vlad Buslov   net: sched: renam...
458
  	qdisc_put(q->qdisc);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
  }
  
  static const struct nla_policy sfb_policy[TCA_SFB_MAX + 1] = {
  	[TCA_SFB_PARMS]	= { .len = sizeof(struct tc_sfb_qopt) },
  };
  
  static const struct tc_sfb_qopt sfb_default_ops = {
  	.rehash_interval = 600 * MSEC_PER_SEC,
  	.warmup_time = 60 * MSEC_PER_SEC,
  	.limit = 0,
  	.max = 25,
  	.bin_size = 20,
  	.increment = (SFB_MAX_PROB + 500) / 1000, /* 0.1 % */
  	.decrement = (SFB_MAX_PROB + 3000) / 6000,
  	.penalty_rate = 10,
  	.penalty_burst = 20,
  };
2030721cc   Alexander Aring   net: sched: sch: ...
476
477
  static int sfb_change(struct Qdisc *sch, struct nlattr *opt,
  		      struct netlink_ext_ack *extack)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
478
479
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
e3ae1f96a   Vlad Buslov   net: sched: sch_s...
480
  	struct Qdisc *child, *old;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
481
482
483
484
485
486
  	struct nlattr *tb[TCA_SFB_MAX + 1];
  	const struct tc_sfb_qopt *ctl = &sfb_default_ops;
  	u32 limit;
  	int err;
  
  	if (opt) {
8cb081746   Johannes Berg   netlink: make val...
487
488
  		err = nla_parse_nested_deprecated(tb, TCA_SFB_MAX, opt,
  						  sfb_policy, NULL);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
489
490
491
492
493
494
495
496
497
498
499
  		if (err < 0)
  			return -EINVAL;
  
  		if (tb[TCA_SFB_PARMS] == NULL)
  			return -EINVAL;
  
  		ctl = nla_data(tb[TCA_SFB_PARMS]);
  	}
  
  	limit = ctl->limit;
  	if (limit == 0)
348e3435c   Phil Sutter   net: sched: drop ...
500
  		limit = qdisc_dev(sch)->tx_queue_len;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
501

a38a98821   Alexander Aring   net: sch: api: ad...
502
  	child = fifo_create_dflt(sch, &pfifo_qdisc_ops, limit, extack);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
503
504
  	if (IS_ERR(child))
  		return PTR_ERR(child);
49b499718   Jiri Kosina   net: sched: make ...
505
506
  	if (child != &noop_qdisc)
  		qdisc_hash_add(child, true);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
507
  	sch_tree_lock(sch);
e3ae1f96a   Vlad Buslov   net: sched: sch_s...
508
509
  	qdisc_purge_queue(q->qdisc);
  	old = q->qdisc;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
  	q->qdisc = child;
  
  	q->rehash_interval = msecs_to_jiffies(ctl->rehash_interval);
  	q->warmup_time = msecs_to_jiffies(ctl->warmup_time);
  	q->rehash_time = jiffies;
  	q->limit = limit;
  	q->increment = ctl->increment;
  	q->decrement = ctl->decrement;
  	q->max = ctl->max;
  	q->bin_size = ctl->bin_size;
  	q->penalty_rate = ctl->penalty_rate;
  	q->penalty_burst = ctl->penalty_burst;
  	q->tokens_avail = ctl->penalty_burst;
  	q->token_time = jiffies;
  
  	q->slot = 0;
  	q->double_buffering = false;
  	sfb_zero_all_buckets(q);
  	sfb_init_perturbation(0, q);
  	sfb_init_perturbation(1, q);
  
  	sch_tree_unlock(sch);
e3ae1f96a   Vlad Buslov   net: sched: sch_s...
532
  	qdisc_put(old);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
533
534
535
  
  	return 0;
  }
e63d7dfd2   Alexander Aring   net: sched: sch: ...
536
537
  static int sfb_init(struct Qdisc *sch, struct nlattr *opt,
  		    struct netlink_ext_ack *extack)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
538
539
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
6529eaba3   Jiri Pirko   net: sched: intro...
540
  	int err;
8d1a77f97   Alexander Aring   net: sch: api: ad...
541
  	err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
6529eaba3   Jiri Pirko   net: sched: intro...
542
543
  	if (err)
  		return err;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
544
545
  
  	q->qdisc = &noop_qdisc;
2030721cc   Alexander Aring   net: sched: sch: ...
546
  	return sfb_change(sch, opt, extack);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
  }
  
  static int sfb_dump(struct Qdisc *sch, struct sk_buff *skb)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  	struct nlattr *opts;
  	struct tc_sfb_qopt opt = {
  		.rehash_interval = jiffies_to_msecs(q->rehash_interval),
  		.warmup_time = jiffies_to_msecs(q->warmup_time),
  		.limit = q->limit,
  		.max = q->max,
  		.bin_size = q->bin_size,
  		.increment = q->increment,
  		.decrement = q->decrement,
  		.penalty_rate = q->penalty_rate,
  		.penalty_burst = q->penalty_burst,
  	};
  
  	sch->qstats.backlog = q->qdisc->qstats.backlog;
ae0be8de9   Michal Kubecek   netlink: make nla...
566
  	opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
7ac2908e4   Alan Cox   sch_sfb: Fix miss...
567
568
  	if (opts == NULL)
  		goto nla_put_failure;
1b34ec43c   David S. Miller   pkt_sched: Stop u...
569
570
  	if (nla_put(skb, TCA_SFB_PARMS, sizeof(opt), &opt))
  		goto nla_put_failure;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
  	return nla_nest_end(skb, opts);
  
  nla_put_failure:
  	nla_nest_cancel(skb, opts);
  	return -EMSGSIZE;
  }
  
  static int sfb_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  	struct tc_sfb_xstats st = {
  		.earlydrop = q->stats.earlydrop,
  		.penaltydrop = q->stats.penaltydrop,
  		.bucketdrop = q->stats.bucketdrop,
  		.queuedrop = q->stats.queuedrop,
  		.childdrop = q->stats.childdrop,
  		.marked = q->stats.marked,
  	};
  
  	st.maxqlen = sfb_compute_qlen(&st.maxprob, &st.avgprob, q);
  
  	return gnet_stats_copy_app(d, &st, sizeof(st));
  }
  
  static int sfb_dump_class(struct Qdisc *sch, unsigned long cl,
  			  struct sk_buff *skb, struct tcmsg *tcm)
  {
  	return -ENOSYS;
  }
  
  static int sfb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
653d6fd68   Alexander Aring   net: sched: sch: ...
602
  		     struct Qdisc **old, struct netlink_ext_ack *extack)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
603
604
605
606
607
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  
  	if (new == NULL)
  		new = &noop_qdisc;
86a7996cc   WANG Cong   net_sched: introd...
608
  	*old = qdisc_replace(sch, new, &q->qdisc);
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
609
610
611
612
613
614
615
616
617
  	return 0;
  }
  
  static struct Qdisc *sfb_leaf(struct Qdisc *sch, unsigned long arg)
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  
  	return q->qdisc;
  }
143976ce9   WANG Cong   net_sched: remove...
618
  static unsigned long sfb_find(struct Qdisc *sch, u32 classid)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
619
620
621
  {
  	return 1;
  }
143976ce9   WANG Cong   net_sched: remove...
622
  static void sfb_unbind(struct Qdisc *sch, unsigned long arg)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
623
624
625
626
  {
  }
  
  static int sfb_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
793d81d6a   Alexander Aring   net: sched: sch: ...
627
628
  			    struct nlattr **tca, unsigned long *arg,
  			    struct netlink_ext_ack *extack)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
  {
  	return -ENOSYS;
  }
  
  static int sfb_delete(struct Qdisc *sch, unsigned long cl)
  {
  	return -ENOSYS;
  }
  
  static void sfb_walk(struct Qdisc *sch, struct qdisc_walker *walker)
  {
  	if (!walker->stop) {
  		if (walker->count >= walker->skip)
  			if (walker->fn(sch, 1, walker) < 0) {
  				walker->stop = 1;
  				return;
  			}
  		walker->count++;
  	}
  }
cbaacc4e8   Alexander Aring   net: sched: sch: ...
649
650
  static struct tcf_block *sfb_tcf_block(struct Qdisc *sch, unsigned long cl,
  				       struct netlink_ext_ack *extack)
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
651
652
653
654
655
  {
  	struct sfb_sched_data *q = qdisc_priv(sch);
  
  	if (cl)
  		return NULL;
6529eaba3   Jiri Pirko   net: sched: intro...
656
  	return q->block;
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
657
658
659
660
661
662
663
664
665
666
667
668
  }
  
  static unsigned long sfb_bind(struct Qdisc *sch, unsigned long parent,
  			      u32 classid)
  {
  	return 0;
  }
  
  
  static const struct Qdisc_class_ops sfb_class_ops = {
  	.graft		=	sfb_graft,
  	.leaf		=	sfb_leaf,
143976ce9   WANG Cong   net_sched: remove...
669
  	.find		=	sfb_find,
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
670
671
672
  	.change		=	sfb_change_class,
  	.delete		=	sfb_delete,
  	.walk		=	sfb_walk,
6529eaba3   Jiri Pirko   net: sched: intro...
673
  	.tcf_block	=	sfb_tcf_block,
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
674
  	.bind_tcf	=	sfb_bind,
143976ce9   WANG Cong   net_sched: remove...
675
  	.unbind_tcf	=	sfb_unbind,
e13e02a3c   Eric Dumazet   net_sched: SFB fl...
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
  	.dump		=	sfb_dump_class,
  };
  
  static struct Qdisc_ops sfb_qdisc_ops __read_mostly = {
  	.id		=	"sfb",
  	.priv_size	=	sizeof(struct sfb_sched_data),
  	.cl_ops		=	&sfb_class_ops,
  	.enqueue	=	sfb_enqueue,
  	.dequeue	=	sfb_dequeue,
  	.peek		=	sfb_peek,
  	.init		=	sfb_init,
  	.reset		=	sfb_reset,
  	.destroy	=	sfb_destroy,
  	.change		=	sfb_change,
  	.dump		=	sfb_dump,
  	.dump_stats	=	sfb_dump_stats,
  	.owner		=	THIS_MODULE,
  };
  
  static int __init sfb_module_init(void)
  {
  	return register_qdisc(&sfb_qdisc_ops);
  }
  
  static void __exit sfb_module_exit(void)
  {
  	unregister_qdisc(&sfb_qdisc_ops);
  }
  
  module_init(sfb_module_init)
  module_exit(sfb_module_exit)
  
  MODULE_DESCRIPTION("Stochastic Fair Blue queue discipline");
  MODULE_AUTHOR("Juliusz Chroboczek");
  MODULE_AUTHOR("Eric Dumazet");
  MODULE_LICENSE("GPL");