11da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* 21da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * net/sched/sch_fifo.c The simplest FIFO queue. 31da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 41da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * This program is free software; you can redistribute it and/or 51da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * modify it under the terms of the GNU General Public License 61da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * as published by the Free Software Foundation; either version 71da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 2 of the License, or (at your option) any later version. 81da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 91da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/module.h> 135a0e3ad6af8660be21ca98a971cd00f331318c05Tejun Heo#include <linux/slab.h> 141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/types.h> 151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/kernel.h> 161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/errno.h> 171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/skbuff.h> 181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/pkt_sched.h> 191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* 1 band FIFO pseudo-"scheduler" */ 211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 22cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic int bfifo_enqueue(struct sk_buff *skb, struct Qdisc *sch) 231da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 24d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet if (likely(sch->qstats.backlog + qdisc_pkt_len(skb) <= sch->limit)) 25aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf return qdisc_enqueue_tail(skb, sch); 261da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 27aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf return qdisc_reshape_fail(skb, sch); 281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 291da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 30cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic int pfifo_enqueue(struct sk_buff *skb, struct Qdisc *sch) 311da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 32d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet if (likely(skb_queue_len(&sch->q) < sch->limit)) 33aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf return qdisc_enqueue_tail(skb, sch); 341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 35aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf return qdisc_reshape_fail(skb, sch); 361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 38cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic int pfifo_tail_enqueue(struct sk_buff *skb, struct Qdisc *sch) 3957dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer{ 40d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet if (likely(skb_queue_len(&sch->q) < sch->limit)) 4157dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer return qdisc_enqueue_tail(skb, sch); 4257dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer 4357dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer /* queue full, remove one skb to fulfill the limit */ 449190b3b3208d052d98cb601fcc192f3f71a5658bEric Dumazet __qdisc_queue_drop_head(sch, &sch->q); 4525331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_drop(sch); 4657dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer qdisc_enqueue_tail(skb, sch); 4757dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer 4857dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer return NET_XMIT_CN; 4957dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer} 5057dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer 511e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardystatic int fifo_init(struct Qdisc *sch, struct nlattr *opt) 521da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 5323624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet bool bypass; 5423624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet bool is_bfifo = sch->ops == &bfifo_qdisc_ops; 551da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 561da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (opt == NULL) { 575ce2d488fe039ddd86a638496cf704df86c74eebDavid S. Miller u32 limit = qdisc_dev(sch)->tx_queue_len ? : 1; 581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 5923624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet if (is_bfifo) 606473990c7f0565fca2007f8662395d122e30f0d8Patrick McHardy limit *= psched_mtu(qdisc_dev(sch)); 616fc8e84f4cf8d623f98aebfd6996dc3848bcf964Thomas Graf 62d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet sch->limit = limit; 631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } else { 641e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy struct tc_fifo_qopt *ctl = nla_data(opt); 656fc8e84f4cf8d623f98aebfd6996dc3848bcf964Thomas Graf 661e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy if (nla_len(opt) < sizeof(*ctl)) 671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return -EINVAL; 686fc8e84f4cf8d623f98aebfd6996dc3848bcf964Thomas Graf 69d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet sch->limit = ctl->limit; 701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 716fc8e84f4cf8d623f98aebfd6996dc3848bcf964Thomas Graf 7223624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet if (is_bfifo) 73d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet bypass = sch->limit >= psched_mtu(qdisc_dev(sch)); 7423624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet else 75d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet bypass = sch->limit >= 1; 7623624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet 7723624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet if (bypass) 7823624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet sch->flags |= TCQ_F_CAN_BYPASS; 7923624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet else 8023624935e0c4b04730ed8d7d21f0cd25b2c2cda1Eric Dumazet sch->flags &= ~TCQ_F_CAN_BYPASS; 811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 821da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int fifo_dump(struct Qdisc *sch, struct sk_buff *skb) 851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 86d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet struct tc_fifo_qopt opt = { .limit = sch->limit }; 871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 881b34ec43c9b3de44a5420841ab293d1b2035a94cDavid S. Miller if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt)) 891b34ec43c9b3de44a5420841ab293d1b2035a94cDavid S. Miller goto nla_put_failure; 901da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return skb->len; 911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 921e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardynla_put_failure: 931da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return -1; 941da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 951da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 9620fea08b5fb639c4c175b5c74a2bb346c5c5bc2eEric Dumazetstruct Qdisc_ops pfifo_qdisc_ops __read_mostly = { 971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .id = "pfifo", 98d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet .priv_size = 0, 991da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .enqueue = pfifo_enqueue, 100aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .dequeue = qdisc_dequeue_head, 10148a8f519e0fe22a5c98523286b2a120841a11dd5Patrick McHardy .peek = qdisc_peek_head, 102aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .drop = qdisc_queue_drop, 1031da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .init = fifo_init, 104aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .reset = qdisc_reset_queue, 1051da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .change = fifo_init, 1061da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .dump = fifo_dump, 1071da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .owner = THIS_MODULE, 1081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 10962e3ba1b558e5f393ef746880613fb8222e64d03Patrick McHardyEXPORT_SYMBOL(pfifo_qdisc_ops); 1101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 11120fea08b5fb639c4c175b5c74a2bb346c5c5bc2eEric Dumazetstruct Qdisc_ops bfifo_qdisc_ops __read_mostly = { 1121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .id = "bfifo", 113d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet .priv_size = 0, 1141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .enqueue = bfifo_enqueue, 115aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .dequeue = qdisc_dequeue_head, 11648a8f519e0fe22a5c98523286b2a120841a11dd5Patrick McHardy .peek = qdisc_peek_head, 117aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .drop = qdisc_queue_drop, 1181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .init = fifo_init, 119aaae3013d186d71a01e1059c9633c4ec8729d891Thomas Graf .reset = qdisc_reset_queue, 1201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .change = fifo_init, 1211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .dump = fifo_dump, 1221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .owner = THIS_MODULE, 1231da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 1241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus TorvaldsEXPORT_SYMBOL(bfifo_qdisc_ops); 125fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 12657dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeiferstruct Qdisc_ops pfifo_head_drop_qdisc_ops __read_mostly = { 12757dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .id = "pfifo_head_drop", 128d276055c4e90a7278cd5167ba9755c9b214bcff7Eric Dumazet .priv_size = 0, 12957dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .enqueue = pfifo_tail_enqueue, 13057dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .dequeue = qdisc_dequeue_head, 13157dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .peek = qdisc_peek_head, 13257dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .drop = qdisc_queue_drop_head, 13357dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .init = fifo_init, 13457dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .reset = qdisc_reset_queue, 13557dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .change = fifo_init, 13657dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .dump = fifo_dump, 13757dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer .owner = THIS_MODULE, 13857dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer}; 13957dbb2d83d100ea601c54fe129bfde0678db5deeHagen Paul Pfeifer 140fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy/* Pass size change message down to embedded FIFO */ 141fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardyint fifo_set_limit(struct Qdisc *q, unsigned int limit) 142fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy{ 143fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy struct nlattr *nla; 144fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy int ret = -ENOMEM; 145fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 146fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy /* Hack to avoid sending change message to non-FIFO */ 147fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy if (strncmp(q->ops->id + 1, "fifo", 4) != 0) 148fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy return 0; 149fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 150fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy nla = kmalloc(nla_attr_size(sizeof(struct tc_fifo_qopt)), GFP_KERNEL); 151fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy if (nla) { 152fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy nla->nla_type = RTM_NEWQDISC; 153fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy nla->nla_len = nla_attr_size(sizeof(struct tc_fifo_qopt)); 154fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy ((struct tc_fifo_qopt *)nla_data(nla))->limit = limit; 155fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 156fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy ret = q->ops->change(q, nla); 157fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy kfree(nla); 158fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy } 159fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy return ret; 160fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy} 161fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardyEXPORT_SYMBOL(fifo_set_limit); 162fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 163fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardystruct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops, 164fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy unsigned int limit) 165fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy{ 166fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy struct Qdisc *q; 167fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy int err = -ENOMEM; 168fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 1693511c9132f8b1e1b5634e41a3331c44b0c13be70Changli Gao q = qdisc_create_dflt(sch->dev_queue, ops, TC_H_MAKE(sch->handle, 1)); 170fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy if (q) { 171fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy err = fifo_set_limit(q, limit); 172fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy if (err < 0) { 173fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy qdisc_destroy(q); 174fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy q = NULL; 175fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy } 176fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy } 177fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy 178fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy return q ? : ERR_PTR(err); 179fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy} 180fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardyEXPORT_SYMBOL(fifo_create_dflt); 181