sch_gred.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609
  1. /*
  2. * net/sched/sch_gred.c Generic Random Early Detection queue.
  3. *
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License
  7. * as published by the Free Software Foundation; either version
  8. * 2 of the License, or (at your option) any later version.
  9. *
  10. * Authors: J Hadi Salim (hadi@cyberus.ca) 1998-2002
  11. *
  12. * 991129: - Bug fix with grio mode
  13. * - a better sing. AvgQ mode with Grio(WRED)
  14. * - A finer grained VQ dequeue based on sugestion
  15. * from Ren Liu
  16. * - More error checks
  17. *
  18. * For all the glorious comments look at include/net/red.h
  19. */
  20. #include <linux/module.h>
  21. #include <linux/types.h>
  22. #include <linux/kernel.h>
  23. #include <linux/netdevice.h>
  24. #include <linux/skbuff.h>
  25. #include <net/pkt_sched.h>
  26. #include <net/red.h>
  27. #define GRED_DEF_PRIO (MAX_DPs / 2)
  28. #define GRED_VQ_MASK (MAX_DPs - 1)
  29. struct gred_sched_data;
  30. struct gred_sched;
  31. struct gred_sched_data
  32. {
  33. u32 limit; /* HARD maximal queue length */
  34. u32 DP; /* the drop pramaters */
  35. u32 bytesin; /* bytes seen on virtualQ so far*/
  36. u32 packetsin; /* packets seen on virtualQ so far*/
  37. u32 backlog; /* bytes on the virtualQ */
  38. u8 prio; /* the prio of this vq */
  39. struct red_parms parms;
  40. struct red_stats stats;
  41. };
  42. enum {
  43. GRED_WRED_MODE = 1,
  44. GRED_RIO_MODE,
  45. };
  46. struct gred_sched
  47. {
  48. struct gred_sched_data *tab[MAX_DPs];
  49. unsigned long flags;
  50. u32 red_flags;
  51. u32 DPs;
  52. u32 def;
  53. struct red_parms wred_set;
  54. };
  55. static inline int gred_wred_mode(struct gred_sched *table)
  56. {
  57. return test_bit(GRED_WRED_MODE, &table->flags);
  58. }
  59. static inline void gred_enable_wred_mode(struct gred_sched *table)
  60. {
  61. __set_bit(GRED_WRED_MODE, &table->flags);
  62. }
  63. static inline void gred_disable_wred_mode(struct gred_sched *table)
  64. {
  65. __clear_bit(GRED_WRED_MODE, &table->flags);
  66. }
  67. static inline int gred_rio_mode(struct gred_sched *table)
  68. {
  69. return test_bit(GRED_RIO_MODE, &table->flags);
  70. }
  71. static inline void gred_enable_rio_mode(struct gred_sched *table)
  72. {
  73. __set_bit(GRED_RIO_MODE, &table->flags);
  74. }
  75. static inline void gred_disable_rio_mode(struct gred_sched *table)
  76. {
  77. __clear_bit(GRED_RIO_MODE, &table->flags);
  78. }
  79. static inline int gred_wred_mode_check(struct Qdisc *sch)
  80. {
  81. struct gred_sched *table = qdisc_priv(sch);
  82. int i;
  83. /* Really ugly O(n^2) but shouldn't be necessary too frequent. */
  84. for (i = 0; i < table->DPs; i++) {
  85. struct gred_sched_data *q = table->tab[i];
  86. int n;
  87. if (q == NULL)
  88. continue;
  89. for (n = 0; n < table->DPs; n++)
  90. if (table->tab[n] && table->tab[n] != q &&
  91. table->tab[n]->prio == q->prio)
  92. return 1;
  93. }
  94. return 0;
  95. }
  96. static inline unsigned int gred_backlog(struct gred_sched *table,
  97. struct gred_sched_data *q,
  98. struct Qdisc *sch)
  99. {
  100. if (gred_wred_mode(table))
  101. return sch->qstats.backlog;
  102. else
  103. return q->backlog;
  104. }
  105. static inline u16 tc_index_to_dp(struct sk_buff *skb)
  106. {
  107. return skb->tc_index & GRED_VQ_MASK;
  108. }
  109. static inline void gred_load_wred_set(struct gred_sched *table,
  110. struct gred_sched_data *q)
  111. {
  112. q->parms.qavg = table->wred_set.qavg;
  113. q->parms.qidlestart = table->wred_set.qidlestart;
  114. }
  115. static inline void gred_store_wred_set(struct gred_sched *table,
  116. struct gred_sched_data *q)
  117. {
  118. table->wred_set.qavg = q->parms.qavg;
  119. }
  120. static inline int gred_use_ecn(struct gred_sched *t)
  121. {
  122. return t->red_flags & TC_RED_ECN;
  123. }
  124. static inline int gred_use_harddrop(struct gred_sched *t)
  125. {
  126. return t->red_flags & TC_RED_HARDDROP;
  127. }
  128. static int gred_enqueue(struct sk_buff *skb, struct Qdisc* sch)
  129. {
  130. struct gred_sched_data *q=NULL;
  131. struct gred_sched *t= qdisc_priv(sch);
  132. unsigned long qavg = 0;
  133. u16 dp = tc_index_to_dp(skb);
  134. if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
  135. dp = t->def;
  136. if ((q = t->tab[dp]) == NULL) {
  137. /* Pass through packets not assigned to a DP
  138. * if no default DP has been configured. This
  139. * allows for DP flows to be left untouched.
  140. */
  141. if (skb_queue_len(&sch->q) < sch->dev->tx_queue_len)
  142. return qdisc_enqueue_tail(skb, sch);
  143. else
  144. goto drop;
  145. }
  146. /* fix tc_index? --could be controvesial but needed for
  147. requeueing */
  148. skb->tc_index = (skb->tc_index & ~GRED_VQ_MASK) | dp;
  149. }
  150. /* sum up all the qaves of prios <= to ours to get the new qave */
  151. if (!gred_wred_mode(t) && gred_rio_mode(t)) {
  152. int i;
  153. for (i = 0; i < t->DPs; i++) {
  154. if (t->tab[i] && t->tab[i]->prio < q->prio &&
  155. !red_is_idling(&t->tab[i]->parms))
  156. qavg +=t->tab[i]->parms.qavg;
  157. }
  158. }
  159. q->packetsin++;
  160. q->bytesin += skb->len;
  161. if (gred_wred_mode(t))
  162. gred_load_wred_set(t, q);
  163. q->parms.qavg = red_calc_qavg(&q->parms, gred_backlog(t, q, sch));
  164. if (red_is_idling(&q->parms))
  165. red_end_of_idle_period(&q->parms);
  166. if (gred_wred_mode(t))
  167. gred_store_wred_set(t, q);
  168. switch (red_action(&q->parms, q->parms.qavg + qavg)) {
  169. case RED_DONT_MARK:
  170. break;
  171. case RED_PROB_MARK:
  172. sch->qstats.overlimits++;
  173. if (!gred_use_ecn(t) || !INET_ECN_set_ce(skb)) {
  174. q->stats.prob_drop++;
  175. goto congestion_drop;
  176. }
  177. q->stats.prob_mark++;
  178. break;
  179. case RED_HARD_MARK:
  180. sch->qstats.overlimits++;
  181. if (gred_use_harddrop(t) || !gred_use_ecn(t) ||
  182. !INET_ECN_set_ce(skb)) {
  183. q->stats.forced_drop++;
  184. goto congestion_drop;
  185. }
  186. q->stats.forced_mark++;
  187. break;
  188. }
  189. if (q->backlog + skb->len <= q->limit) {
  190. q->backlog += skb->len;
  191. return qdisc_enqueue_tail(skb, sch);
  192. }
  193. q->stats.pdrop++;
  194. drop:
  195. return qdisc_drop(skb, sch);
  196. congestion_drop:
  197. qdisc_drop(skb, sch);
  198. return NET_XMIT_CN;
  199. }
  200. static int gred_requeue(struct sk_buff *skb, struct Qdisc* sch)
  201. {
  202. struct gred_sched *t = qdisc_priv(sch);
  203. struct gred_sched_data *q;
  204. u16 dp = tc_index_to_dp(skb);
  205. if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
  206. if (net_ratelimit())
  207. printk(KERN_WARNING "GRED: Unable to relocate VQ 0x%x "
  208. "for requeue, screwing up backlog.\n",
  209. tc_index_to_dp(skb));
  210. } else {
  211. if (red_is_idling(&q->parms))
  212. red_end_of_idle_period(&q->parms);
  213. q->backlog += skb->len;
  214. }
  215. return qdisc_requeue(skb, sch);
  216. }
  217. static struct sk_buff *gred_dequeue(struct Qdisc* sch)
  218. {
  219. struct sk_buff *skb;
  220. struct gred_sched *t = qdisc_priv(sch);
  221. skb = qdisc_dequeue_head(sch);
  222. if (skb) {
  223. struct gred_sched_data *q;
  224. u16 dp = tc_index_to_dp(skb);
  225. if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
  226. if (net_ratelimit())
  227. printk(KERN_WARNING "GRED: Unable to relocate "
  228. "VQ 0x%x after dequeue, screwing up "
  229. "backlog.\n", tc_index_to_dp(skb));
  230. } else {
  231. q->backlog -= skb->len;
  232. if (!q->backlog && !gred_wred_mode(t))
  233. red_start_of_idle_period(&q->parms);
  234. }
  235. return skb;
  236. }
  237. if (gred_wred_mode(t) && !red_is_idling(&t->wred_set))
  238. red_start_of_idle_period(&t->wred_set);
  239. return NULL;
  240. }
  241. static unsigned int gred_drop(struct Qdisc* sch)
  242. {
  243. struct sk_buff *skb;
  244. struct gred_sched *t = qdisc_priv(sch);
  245. skb = qdisc_dequeue_tail(sch);
  246. if (skb) {
  247. unsigned int len = skb->len;
  248. struct gred_sched_data *q;
  249. u16 dp = tc_index_to_dp(skb);
  250. if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
  251. if (net_ratelimit())
  252. printk(KERN_WARNING "GRED: Unable to relocate "
  253. "VQ 0x%x while dropping, screwing up "
  254. "backlog.\n", tc_index_to_dp(skb));
  255. } else {
  256. q->backlog -= len;
  257. q->stats.other++;
  258. if (!q->backlog && !gred_wred_mode(t))
  259. red_start_of_idle_period(&q->parms);
  260. }
  261. qdisc_drop(skb, sch);
  262. return len;
  263. }
  264. if (gred_wred_mode(t) && !red_is_idling(&t->wred_set))
  265. red_start_of_idle_period(&t->wred_set);
  266. return 0;
  267. }
  268. static void gred_reset(struct Qdisc* sch)
  269. {
  270. int i;
  271. struct gred_sched *t = qdisc_priv(sch);
  272. qdisc_reset_queue(sch);
  273. for (i = 0; i < t->DPs; i++) {
  274. struct gred_sched_data *q = t->tab[i];
  275. if (!q)
  276. continue;
  277. red_restart(&q->parms);
  278. q->backlog = 0;
  279. }
  280. }
  281. static inline void gred_destroy_vq(struct gred_sched_data *q)
  282. {
  283. kfree(q);
  284. }
  285. static inline int gred_change_table_def(struct Qdisc *sch, struct rtattr *dps)
  286. {
  287. struct gred_sched *table = qdisc_priv(sch);
  288. struct tc_gred_sopt *sopt;
  289. int i;
  290. if (dps == NULL || RTA_PAYLOAD(dps) < sizeof(*sopt))
  291. return -EINVAL;
  292. sopt = RTA_DATA(dps);
  293. if (sopt->DPs > MAX_DPs || sopt->DPs == 0 || sopt->def_DP >= sopt->DPs)
  294. return -EINVAL;
  295. sch_tree_lock(sch);
  296. table->DPs = sopt->DPs;
  297. table->def = sopt->def_DP;
  298. table->red_flags = sopt->flags;
  299. /*
  300. * Every entry point to GRED is synchronized with the above code
  301. * and the DP is checked against DPs, i.e. shadowed VQs can no
  302. * longer be found so we can unlock right here.
  303. */
  304. sch_tree_unlock(sch);
  305. if (sopt->grio) {
  306. gred_enable_rio_mode(table);
  307. gred_disable_wred_mode(table);
  308. if (gred_wred_mode_check(sch))
  309. gred_enable_wred_mode(table);
  310. } else {
  311. gred_disable_rio_mode(table);
  312. gred_disable_wred_mode(table);
  313. }
  314. for (i = table->DPs; i < MAX_DPs; i++) {
  315. if (table->tab[i]) {
  316. printk(KERN_WARNING "GRED: Warning: Destroying "
  317. "shadowed VQ 0x%x\n", i);
  318. gred_destroy_vq(table->tab[i]);
  319. table->tab[i] = NULL;
  320. }
  321. }
  322. return 0;
  323. }
  324. static inline int gred_change_vq(struct Qdisc *sch, int dp,
  325. struct tc_gred_qopt *ctl, int prio, u8 *stab)
  326. {
  327. struct gred_sched *table = qdisc_priv(sch);
  328. struct gred_sched_data *q;
  329. if (table->tab[dp] == NULL) {
  330. table->tab[dp] = kzalloc(sizeof(*q), GFP_KERNEL);
  331. if (table->tab[dp] == NULL)
  332. return -ENOMEM;
  333. }
  334. q = table->tab[dp];
  335. q->DP = dp;
  336. q->prio = prio;
  337. q->limit = ctl->limit;
  338. if (q->backlog == 0)
  339. red_end_of_idle_period(&q->parms);
  340. red_set_parms(&q->parms,
  341. ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog,
  342. ctl->Scell_log, stab);
  343. return 0;
  344. }
  345. static int gred_change(struct Qdisc *sch, struct rtattr *opt)
  346. {
  347. struct gred_sched *table = qdisc_priv(sch);
  348. struct tc_gred_qopt *ctl;
  349. struct rtattr *tb[TCA_GRED_MAX];
  350. int err = -EINVAL, prio = GRED_DEF_PRIO;
  351. u8 *stab;
  352. if (opt == NULL || rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
  353. return -EINVAL;
  354. if (tb[TCA_GRED_PARMS-1] == NULL && tb[TCA_GRED_STAB-1] == NULL)
  355. return gred_change_table_def(sch, opt);
  356. if (tb[TCA_GRED_PARMS-1] == NULL ||
  357. RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) ||
  358. tb[TCA_GRED_STAB-1] == NULL ||
  359. RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
  360. return -EINVAL;
  361. ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
  362. stab = RTA_DATA(tb[TCA_GRED_STAB-1]);
  363. if (ctl->DP >= table->DPs)
  364. goto errout;
  365. if (gred_rio_mode(table)) {
  366. if (ctl->prio == 0) {
  367. int def_prio = GRED_DEF_PRIO;
  368. if (table->tab[table->def])
  369. def_prio = table->tab[table->def]->prio;
  370. printk(KERN_DEBUG "GRED: DP %u does not have a prio "
  371. "setting default to %d\n", ctl->DP, def_prio);
  372. prio = def_prio;
  373. } else
  374. prio = ctl->prio;
  375. }
  376. sch_tree_lock(sch);
  377. err = gred_change_vq(sch, ctl->DP, ctl, prio, stab);
  378. if (err < 0)
  379. goto errout_locked;
  380. if (gred_rio_mode(table)) {
  381. gred_disable_wred_mode(table);
  382. if (gred_wred_mode_check(sch))
  383. gred_enable_wred_mode(table);
  384. }
  385. err = 0;
  386. errout_locked:
  387. sch_tree_unlock(sch);
  388. errout:
  389. return err;
  390. }
  391. static int gred_init(struct Qdisc *sch, struct rtattr *opt)
  392. {
  393. struct rtattr *tb[TCA_GRED_MAX];
  394. if (opt == NULL || rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
  395. return -EINVAL;
  396. if (tb[TCA_GRED_PARMS-1] || tb[TCA_GRED_STAB-1])
  397. return -EINVAL;
  398. return gred_change_table_def(sch, tb[TCA_GRED_DPS-1]);
  399. }
  400. static int gred_dump(struct Qdisc *sch, struct sk_buff *skb)
  401. {
  402. struct gred_sched *table = qdisc_priv(sch);
  403. struct rtattr *parms, *opts = NULL;
  404. int i;
  405. struct tc_gred_sopt sopt = {
  406. .DPs = table->DPs,
  407. .def_DP = table->def,
  408. .grio = gred_rio_mode(table),
  409. .flags = table->red_flags,
  410. };
  411. opts = RTA_NEST(skb, TCA_OPTIONS);
  412. RTA_PUT(skb, TCA_GRED_DPS, sizeof(sopt), &sopt);
  413. parms = RTA_NEST(skb, TCA_GRED_PARMS);
  414. for (i = 0; i < MAX_DPs; i++) {
  415. struct gred_sched_data *q = table->tab[i];
  416. struct tc_gred_qopt opt;
  417. memset(&opt, 0, sizeof(opt));
  418. if (!q) {
  419. /* hack -- fix at some point with proper message
  420. This is how we indicate to tc that there is no VQ
  421. at this DP */
  422. opt.DP = MAX_DPs + i;
  423. goto append_opt;
  424. }
  425. opt.limit = q->limit;
  426. opt.DP = q->DP;
  427. opt.backlog = q->backlog;
  428. opt.prio = q->prio;
  429. opt.qth_min = q->parms.qth_min >> q->parms.Wlog;
  430. opt.qth_max = q->parms.qth_max >> q->parms.Wlog;
  431. opt.Wlog = q->parms.Wlog;
  432. opt.Plog = q->parms.Plog;
  433. opt.Scell_log = q->parms.Scell_log;
  434. opt.other = q->stats.other;
  435. opt.early = q->stats.prob_drop;
  436. opt.forced = q->stats.forced_drop;
  437. opt.pdrop = q->stats.pdrop;
  438. opt.packets = q->packetsin;
  439. opt.bytesin = q->bytesin;
  440. if (gred_wred_mode(table)) {
  441. q->parms.qidlestart =
  442. table->tab[table->def]->parms.qidlestart;
  443. q->parms.qavg = table->tab[table->def]->parms.qavg;
  444. }
  445. opt.qave = red_calc_qavg(&q->parms, q->parms.qavg);
  446. append_opt:
  447. RTA_APPEND(skb, sizeof(opt), &opt);
  448. }
  449. RTA_NEST_END(skb, parms);
  450. return RTA_NEST_END(skb, opts);
  451. rtattr_failure:
  452. return RTA_NEST_CANCEL(skb, opts);
  453. }
  454. static void gred_destroy(struct Qdisc *sch)
  455. {
  456. struct gred_sched *table = qdisc_priv(sch);
  457. int i;
  458. for (i = 0; i < table->DPs; i++) {
  459. if (table->tab[i])
  460. gred_destroy_vq(table->tab[i]);
  461. }
  462. }
  463. static struct Qdisc_ops gred_qdisc_ops = {
  464. .id = "gred",
  465. .priv_size = sizeof(struct gred_sched),
  466. .enqueue = gred_enqueue,
  467. .dequeue = gred_dequeue,
  468. .requeue = gred_requeue,
  469. .drop = gred_drop,
  470. .init = gred_init,
  471. .reset = gred_reset,
  472. .destroy = gred_destroy,
  473. .change = gred_change,
  474. .dump = gred_dump,
  475. .owner = THIS_MODULE,
  476. };
  477. static int __init gred_module_init(void)
  478. {
  479. return register_qdisc(&gred_qdisc_ops);
  480. }
  481. static void __exit gred_module_exit(void)
  482. {
  483. unregister_qdisc(&gred_qdisc_ops);
  484. }
  485. module_init(gred_module_init)
  486. module_exit(gred_module_exit)
  487. MODULE_LICENSE("GPL");