sch_generic.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570
  1. #ifndef __NET_SCHED_GENERIC_H
  2. #define __NET_SCHED_GENERIC_H
  3. #include <linux/netdevice.h>
  4. #include <linux/types.h>
  5. #include <linux/rcupdate.h>
  6. #include <linux/module.h>
  7. #include <linux/pkt_sched.h>
  8. #include <linux/pkt_cls.h>
  9. #include <net/gen_stats.h>
  10. #include <net/rtnetlink.h>
  11. struct Qdisc_ops;
  12. struct qdisc_walker;
  13. struct tcf_walker;
  14. struct module;
  15. struct qdisc_rate_table
  16. {
  17. struct tc_ratespec rate;
  18. u32 data[256];
  19. struct qdisc_rate_table *next;
  20. int refcnt;
  21. };
  22. enum qdisc_state_t
  23. {
  24. __QDISC_STATE_RUNNING,
  25. __QDISC_STATE_SCHED,
  26. __QDISC_STATE_DEACTIVATED,
  27. };
  28. struct qdisc_size_table {
  29. struct list_head list;
  30. struct tc_sizespec szopts;
  31. int refcnt;
  32. u16 data[];
  33. };
  34. struct Qdisc
  35. {
  36. int (*enqueue)(struct sk_buff *skb, struct Qdisc *dev);
  37. struct sk_buff * (*dequeue)(struct Qdisc *dev);
  38. unsigned flags;
  39. #define TCQ_F_BUILTIN 1
  40. #define TCQ_F_THROTTLED 2
  41. #define TCQ_F_INGRESS 4
  42. #define TCQ_F_CAN_BYPASS 8
  43. #define TCQ_F_WARN_NONWC (1 << 16)
  44. int padded;
  45. struct Qdisc_ops *ops;
  46. struct qdisc_size_table *stab;
  47. struct list_head list;
  48. u32 handle;
  49. u32 parent;
  50. atomic_t refcnt;
  51. struct gnet_stats_rate_est rate_est;
  52. int (*reshape_fail)(struct sk_buff *skb,
  53. struct Qdisc *q);
  54. void *u32_node;
  55. /* This field is deprecated, but it is still used by CBQ
  56. * and it will live until better solution will be invented.
  57. */
  58. struct Qdisc *__parent;
  59. struct netdev_queue *dev_queue;
  60. struct Qdisc *next_sched;
  61. struct sk_buff *gso_skb;
  62. /*
  63. * For performance sake on SMP, we put highly modified fields at the end
  64. */
  65. unsigned long state;
  66. struct sk_buff_head q;
  67. struct gnet_stats_basic bstats;
  68. struct gnet_stats_queue qstats;
  69. };
  70. struct Qdisc_class_ops
  71. {
  72. /* Child qdisc manipulation */
  73. int (*graft)(struct Qdisc *, unsigned long cl,
  74. struct Qdisc *, struct Qdisc **);
  75. struct Qdisc * (*leaf)(struct Qdisc *, unsigned long cl);
  76. void (*qlen_notify)(struct Qdisc *, unsigned long);
  77. /* Class manipulation routines */
  78. unsigned long (*get)(struct Qdisc *, u32 classid);
  79. void (*put)(struct Qdisc *, unsigned long);
  80. int (*change)(struct Qdisc *, u32, u32,
  81. struct nlattr **, unsigned long *);
  82. int (*delete)(struct Qdisc *, unsigned long);
  83. void (*walk)(struct Qdisc *, struct qdisc_walker * arg);
  84. /* Filter manipulation */
  85. struct tcf_proto ** (*tcf_chain)(struct Qdisc *, unsigned long);
  86. unsigned long (*bind_tcf)(struct Qdisc *, unsigned long,
  87. u32 classid);
  88. void (*unbind_tcf)(struct Qdisc *, unsigned long);
  89. /* rtnetlink specific */
  90. int (*dump)(struct Qdisc *, unsigned long,
  91. struct sk_buff *skb, struct tcmsg*);
  92. int (*dump_stats)(struct Qdisc *, unsigned long,
  93. struct gnet_dump *);
  94. };
  95. struct Qdisc_ops
  96. {
  97. struct Qdisc_ops *next;
  98. const struct Qdisc_class_ops *cl_ops;
  99. char id[IFNAMSIZ];
  100. int priv_size;
  101. int (*enqueue)(struct sk_buff *, struct Qdisc *);
  102. struct sk_buff * (*dequeue)(struct Qdisc *);
  103. struct sk_buff * (*peek)(struct Qdisc *);
  104. unsigned int (*drop)(struct Qdisc *);
  105. int (*init)(struct Qdisc *, struct nlattr *arg);
  106. void (*reset)(struct Qdisc *);
  107. void (*destroy)(struct Qdisc *);
  108. int (*change)(struct Qdisc *, struct nlattr *arg);
  109. int (*dump)(struct Qdisc *, struct sk_buff *);
  110. int (*dump_stats)(struct Qdisc *, struct gnet_dump *);
  111. struct module *owner;
  112. };
  113. struct tcf_result
  114. {
  115. unsigned long class;
  116. u32 classid;
  117. };
  118. struct tcf_proto_ops
  119. {
  120. struct tcf_proto_ops *next;
  121. char kind[IFNAMSIZ];
  122. int (*classify)(struct sk_buff*, struct tcf_proto*,
  123. struct tcf_result *);
  124. int (*init)(struct tcf_proto*);
  125. void (*destroy)(struct tcf_proto*);
  126. unsigned long (*get)(struct tcf_proto*, u32 handle);
  127. void (*put)(struct tcf_proto*, unsigned long);
  128. int (*change)(struct tcf_proto*, unsigned long,
  129. u32 handle, struct nlattr **,
  130. unsigned long *);
  131. int (*delete)(struct tcf_proto*, unsigned long);
  132. void (*walk)(struct tcf_proto*, struct tcf_walker *arg);
  133. /* rtnetlink specific */
  134. int (*dump)(struct tcf_proto*, unsigned long,
  135. struct sk_buff *skb, struct tcmsg*);
  136. struct module *owner;
  137. };
  138. struct tcf_proto
  139. {
  140. /* Fast access part */
  141. struct tcf_proto *next;
  142. void *root;
  143. int (*classify)(struct sk_buff*, struct tcf_proto*,
  144. struct tcf_result *);
  145. __be16 protocol;
  146. /* All the rest */
  147. u32 prio;
  148. u32 classid;
  149. struct Qdisc *q;
  150. void *data;
  151. struct tcf_proto_ops *ops;
  152. };
  153. struct qdisc_skb_cb {
  154. unsigned int pkt_len;
  155. char data[];
  156. };
  157. static inline int qdisc_qlen(struct Qdisc *q)
  158. {
  159. return q->q.qlen;
  160. }
  161. static inline struct qdisc_skb_cb *qdisc_skb_cb(struct sk_buff *skb)
  162. {
  163. return (struct qdisc_skb_cb *)skb->cb;
  164. }
  165. static inline spinlock_t *qdisc_lock(struct Qdisc *qdisc)
  166. {
  167. return &qdisc->q.lock;
  168. }
  169. static inline struct Qdisc *qdisc_root(struct Qdisc *qdisc)
  170. {
  171. return qdisc->dev_queue->qdisc;
  172. }
  173. static inline struct Qdisc *qdisc_root_sleeping(struct Qdisc *qdisc)
  174. {
  175. return qdisc->dev_queue->qdisc_sleeping;
  176. }
  177. /* The qdisc root lock is a mechanism by which to top level
  178. * of a qdisc tree can be locked from any qdisc node in the
  179. * forest. This allows changing the configuration of some
  180. * aspect of the qdisc tree while blocking out asynchronous
  181. * qdisc access in the packet processing paths.
  182. *
  183. * It is only legal to do this when the root will not change
  184. * on us. Otherwise we'll potentially lock the wrong qdisc
  185. * root. This is enforced by holding the RTNL semaphore, which
  186. * all users of this lock accessor must do.
  187. */
  188. static inline spinlock_t *qdisc_root_lock(struct Qdisc *qdisc)
  189. {
  190. struct Qdisc *root = qdisc_root(qdisc);
  191. ASSERT_RTNL();
  192. return qdisc_lock(root);
  193. }
  194. static inline spinlock_t *qdisc_root_sleeping_lock(struct Qdisc *qdisc)
  195. {
  196. struct Qdisc *root = qdisc_root_sleeping(qdisc);
  197. ASSERT_RTNL();
  198. return qdisc_lock(root);
  199. }
  200. static inline struct net_device *qdisc_dev(struct Qdisc *qdisc)
  201. {
  202. return qdisc->dev_queue->dev;
  203. }
  204. static inline void sch_tree_lock(struct Qdisc *q)
  205. {
  206. spin_lock_bh(qdisc_root_sleeping_lock(q));
  207. }
  208. static inline void sch_tree_unlock(struct Qdisc *q)
  209. {
  210. spin_unlock_bh(qdisc_root_sleeping_lock(q));
  211. }
  212. #define tcf_tree_lock(tp) sch_tree_lock((tp)->q)
  213. #define tcf_tree_unlock(tp) sch_tree_unlock((tp)->q)
  214. extern struct Qdisc noop_qdisc;
  215. extern struct Qdisc_ops noop_qdisc_ops;
  216. struct Qdisc_class_common
  217. {
  218. u32 classid;
  219. struct hlist_node hnode;
  220. };
  221. struct Qdisc_class_hash
  222. {
  223. struct hlist_head *hash;
  224. unsigned int hashsize;
  225. unsigned int hashmask;
  226. unsigned int hashelems;
  227. };
  228. static inline unsigned int qdisc_class_hash(u32 id, u32 mask)
  229. {
  230. id ^= id >> 8;
  231. id ^= id >> 4;
  232. return id & mask;
  233. }
  234. static inline struct Qdisc_class_common *
  235. qdisc_class_find(struct Qdisc_class_hash *hash, u32 id)
  236. {
  237. struct Qdisc_class_common *cl;
  238. struct hlist_node *n;
  239. unsigned int h;
  240. h = qdisc_class_hash(id, hash->hashmask);
  241. hlist_for_each_entry(cl, n, &hash->hash[h], hnode) {
  242. if (cl->classid == id)
  243. return cl;
  244. }
  245. return NULL;
  246. }
  247. extern int qdisc_class_hash_init(struct Qdisc_class_hash *);
  248. extern void qdisc_class_hash_insert(struct Qdisc_class_hash *, struct Qdisc_class_common *);
  249. extern void qdisc_class_hash_remove(struct Qdisc_class_hash *, struct Qdisc_class_common *);
  250. extern void qdisc_class_hash_grow(struct Qdisc *, struct Qdisc_class_hash *);
  251. extern void qdisc_class_hash_destroy(struct Qdisc_class_hash *);
  252. extern void dev_init_scheduler(struct net_device *dev);
  253. extern void dev_shutdown(struct net_device *dev);
  254. extern void dev_activate(struct net_device *dev);
  255. extern void dev_deactivate(struct net_device *dev);
  256. extern void qdisc_reset(struct Qdisc *qdisc);
  257. extern void qdisc_destroy(struct Qdisc *qdisc);
  258. extern void qdisc_tree_decrease_qlen(struct Qdisc *qdisc, unsigned int n);
  259. extern struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
  260. struct Qdisc_ops *ops);
  261. extern struct Qdisc *qdisc_create_dflt(struct net_device *dev,
  262. struct netdev_queue *dev_queue,
  263. struct Qdisc_ops *ops, u32 parentid);
  264. extern void qdisc_calculate_pkt_len(struct sk_buff *skb,
  265. struct qdisc_size_table *stab);
  266. extern void tcf_destroy(struct tcf_proto *tp);
  267. extern void tcf_destroy_chain(struct tcf_proto **fl);
  268. /* Reset all TX qdiscs of a device. */
  269. static inline void qdisc_reset_all_tx(struct net_device *dev)
  270. {
  271. unsigned int i;
  272. for (i = 0; i < dev->num_tx_queues; i++)
  273. qdisc_reset(netdev_get_tx_queue(dev, i)->qdisc);
  274. }
  275. /* Are all TX queues of the device empty? */
  276. static inline bool qdisc_all_tx_empty(const struct net_device *dev)
  277. {
  278. unsigned int i;
  279. for (i = 0; i < dev->num_tx_queues; i++) {
  280. struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
  281. const struct Qdisc *q = txq->qdisc;
  282. if (q->q.qlen)
  283. return false;
  284. }
  285. return true;
  286. }
  287. /* Are any of the TX qdiscs changing? */
  288. static inline bool qdisc_tx_changing(struct net_device *dev)
  289. {
  290. unsigned int i;
  291. for (i = 0; i < dev->num_tx_queues; i++) {
  292. struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
  293. if (txq->qdisc != txq->qdisc_sleeping)
  294. return true;
  295. }
  296. return false;
  297. }
  298. /* Is the device using the noop qdisc on all queues? */
  299. static inline bool qdisc_tx_is_noop(const struct net_device *dev)
  300. {
  301. unsigned int i;
  302. for (i = 0; i < dev->num_tx_queues; i++) {
  303. struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
  304. if (txq->qdisc != &noop_qdisc)
  305. return false;
  306. }
  307. return true;
  308. }
  309. static inline unsigned int qdisc_pkt_len(struct sk_buff *skb)
  310. {
  311. return qdisc_skb_cb(skb)->pkt_len;
  312. }
  313. /* additional qdisc xmit flags (NET_XMIT_MASK in linux/netdevice.h) */
  314. enum net_xmit_qdisc_t {
  315. __NET_XMIT_STOLEN = 0x00010000,
  316. __NET_XMIT_BYPASS = 0x00020000,
  317. };
  318. #ifdef CONFIG_NET_CLS_ACT
  319. #define net_xmit_drop_count(e) ((e) & __NET_XMIT_STOLEN ? 0 : 1)
  320. #else
  321. #define net_xmit_drop_count(e) (1)
  322. #endif
  323. static inline int qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  324. {
  325. #ifdef CONFIG_NET_SCHED
  326. if (sch->stab)
  327. qdisc_calculate_pkt_len(skb, sch->stab);
  328. #endif
  329. return sch->enqueue(skb, sch);
  330. }
  331. static inline int qdisc_enqueue_root(struct sk_buff *skb, struct Qdisc *sch)
  332. {
  333. qdisc_skb_cb(skb)->pkt_len = skb->len;
  334. return qdisc_enqueue(skb, sch) & NET_XMIT_MASK;
  335. }
  336. static inline void __qdisc_update_bstats(struct Qdisc *sch, unsigned int len)
  337. {
  338. sch->bstats.bytes += len;
  339. sch->bstats.packets++;
  340. }
  341. static inline int __qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch,
  342. struct sk_buff_head *list)
  343. {
  344. __skb_queue_tail(list, skb);
  345. sch->qstats.backlog += qdisc_pkt_len(skb);
  346. __qdisc_update_bstats(sch, qdisc_pkt_len(skb));
  347. return NET_XMIT_SUCCESS;
  348. }
  349. static inline int qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch)
  350. {
  351. return __qdisc_enqueue_tail(skb, sch, &sch->q);
  352. }
  353. static inline struct sk_buff *__qdisc_dequeue_head(struct Qdisc *sch,
  354. struct sk_buff_head *list)
  355. {
  356. struct sk_buff *skb = __skb_dequeue(list);
  357. if (likely(skb != NULL))
  358. sch->qstats.backlog -= qdisc_pkt_len(skb);
  359. return skb;
  360. }
  361. static inline struct sk_buff *qdisc_dequeue_head(struct Qdisc *sch)
  362. {
  363. return __qdisc_dequeue_head(sch, &sch->q);
  364. }
  365. static inline struct sk_buff *__qdisc_dequeue_tail(struct Qdisc *sch,
  366. struct sk_buff_head *list)
  367. {
  368. struct sk_buff *skb = __skb_dequeue_tail(list);
  369. if (likely(skb != NULL))
  370. sch->qstats.backlog -= qdisc_pkt_len(skb);
  371. return skb;
  372. }
  373. static inline struct sk_buff *qdisc_dequeue_tail(struct Qdisc *sch)
  374. {
  375. return __qdisc_dequeue_tail(sch, &sch->q);
  376. }
  377. static inline struct sk_buff *qdisc_peek_head(struct Qdisc *sch)
  378. {
  379. return skb_peek(&sch->q);
  380. }
  381. /* generic pseudo peek method for non-work-conserving qdisc */
  382. static inline struct sk_buff *qdisc_peek_dequeued(struct Qdisc *sch)
  383. {
  384. /* we can reuse ->gso_skb because peek isn't called for root qdiscs */
  385. if (!sch->gso_skb) {
  386. sch->gso_skb = sch->dequeue(sch);
  387. if (sch->gso_skb)
  388. /* it's still part of the queue */
  389. sch->q.qlen++;
  390. }
  391. return sch->gso_skb;
  392. }
  393. /* use instead of qdisc->dequeue() for all qdiscs queried with ->peek() */
  394. static inline struct sk_buff *qdisc_dequeue_peeked(struct Qdisc *sch)
  395. {
  396. struct sk_buff *skb = sch->gso_skb;
  397. if (skb) {
  398. sch->gso_skb = NULL;
  399. sch->q.qlen--;
  400. } else {
  401. skb = sch->dequeue(sch);
  402. }
  403. return skb;
  404. }
  405. static inline void __qdisc_reset_queue(struct Qdisc *sch,
  406. struct sk_buff_head *list)
  407. {
  408. /*
  409. * We do not know the backlog in bytes of this list, it
  410. * is up to the caller to correct it
  411. */
  412. __skb_queue_purge(list);
  413. }
  414. static inline void qdisc_reset_queue(struct Qdisc *sch)
  415. {
  416. __qdisc_reset_queue(sch, &sch->q);
  417. sch->qstats.backlog = 0;
  418. }
  419. static inline unsigned int __qdisc_queue_drop(struct Qdisc *sch,
  420. struct sk_buff_head *list)
  421. {
  422. struct sk_buff *skb = __qdisc_dequeue_tail(sch, list);
  423. if (likely(skb != NULL)) {
  424. unsigned int len = qdisc_pkt_len(skb);
  425. kfree_skb(skb);
  426. return len;
  427. }
  428. return 0;
  429. }
  430. static inline unsigned int qdisc_queue_drop(struct Qdisc *sch)
  431. {
  432. return __qdisc_queue_drop(sch, &sch->q);
  433. }
  434. static inline int qdisc_drop(struct sk_buff *skb, struct Qdisc *sch)
  435. {
  436. kfree_skb(skb);
  437. sch->qstats.drops++;
  438. return NET_XMIT_DROP;
  439. }
  440. static inline int qdisc_reshape_fail(struct sk_buff *skb, struct Qdisc *sch)
  441. {
  442. sch->qstats.drops++;
  443. #ifdef CONFIG_NET_CLS_ACT
  444. if (sch->reshape_fail == NULL || sch->reshape_fail(skb, sch))
  445. goto drop;
  446. return NET_XMIT_SUCCESS;
  447. drop:
  448. #endif
  449. kfree_skb(skb);
  450. return NET_XMIT_DROP;
  451. }
  452. /* Length to Time (L2T) lookup in a qdisc_rate_table, to determine how
  453. long it will take to send a packet given its size.
  454. */
  455. static inline u32 qdisc_l2t(struct qdisc_rate_table* rtab, unsigned int pktlen)
  456. {
  457. int slot = pktlen + rtab->rate.cell_align + rtab->rate.overhead;
  458. if (slot < 0)
  459. slot = 0;
  460. slot >>= rtab->rate.cell_log;
  461. if (slot > 255)
  462. return (rtab->data[255]*(slot >> 8) + rtab->data[slot & 0xFF]);
  463. return rtab->data[slot];
  464. }
  465. #ifdef CONFIG_NET_CLS_ACT
  466. static inline struct sk_buff *skb_act_clone(struct sk_buff *skb, gfp_t gfp_mask)
  467. {
  468. struct sk_buff *n = skb_clone(skb, gfp_mask);
  469. if (n) {
  470. n->tc_verd = SET_TC_VERD(n->tc_verd, 0);
  471. n->tc_verd = CLR_TC_OK2MUNGE(n->tc_verd);
  472. n->tc_verd = CLR_TC_MUNGED(n->tc_verd);
  473. }
  474. return n;
  475. }
  476. #endif
  477. #endif