sch_dtht.c

   1 /*
   2  * sch_dtht: Deep Thought Scheduler
   3  * Copyright (C) 2011 Daniel Borkmann <borkmann@iogearbox.net>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * A simple, stupid drop, dup, corrupt, hi-jitter and just for fun
  16  * network scheduler! Probably he won't give you the answer to the
  17  * ultimate question of life, the universe, and everything, but he will
  18  * take his time thinking about it. ;-)
  19  *
  20  *  enable on egress: tc qdisc add dev eth10 root dtht
  21  * disable on egress: tc qdisc del dev eth10 root dtht
  22  */
  23
  24 #include <linux/kernel.h>
  25 #include <linux/module.h>
  26 #include <linux/types.h>
  27 #include <linux/skbuff.h>
  28 #include <linux/net.h>
  29 #include <net/pkt_sched.h>
  30 #include <net/sch_generic.h>
  31
  32 #define MODULE_NAME "sch_dtht"
  33 #define MODULE_DESC "Deep Thought Scheduler"
  34
  35 struct sock_time_inf {
  36         psched_time_t depart;
  37 };
  38
  39 #define SKB_DT_INF(skb) ((struct sock_time_inf *) (qdisc_skb_cb(skb)->data))
  40
  41 static int deepthought_enqueue(struct sk_buff *skb, struct Qdisc *sch)
  42 {
  43         int drop = 0, dup = 0, corr = 0;
  44         struct sk_buff *skb2 = NULL;
  45
  46         if (likely(sch->qstats.backlog + qdisc_pkt_len(skb) <= sch->limit)) {
  47                 if ((net_random() & 0x7) == 1)
  48                         drop = 1;
  49                 if ((net_random() & 0xf) == 1)
  50                         corr = 1;
  51                 if ((net_random() & 0xf) == 1 &&
  52                     sch->qstats.backlog + qdisc_pkt_len(skb) * 2 <=
  53                     sch->limit)
  54                         dup = 1;
  55         } else {
  56                 drop = 1;
  57         }
  58         if (drop) {
  59                 kfree_skb(skb);
  60 drop_nofree:
  61                 sch->qstats.drops++;
  62                 return NET_XMIT_DROP;
  63         }
  64         if (dup) {
  65                 skb2 = skb_clone(skb, GFP_ATOMIC);
  66                 SKB_DT_INF(skb2)->depart = psched_get_time() +
  67                                            (net_random() & 0xffff);
  68                 qdisc_enqueue_tail(skb2, sch);
  69         }
  70         if (corr) {
  71                 if (!(skb = skb_unshare(skb, GFP_ATOMIC)) ||
  72                     (skb->ip_summed == CHECKSUM_PARTIAL &&
  73                      skb_checksum_help(skb)))
  74                         goto drop_nofree;
  75                 skb->data[net_random() % skb_headlen(skb)] ^= 1 << (net_random() % 8);
  76         }
  77         SKB_DT_INF(skb)->depart = psched_get_time() + (net_random() & 0xffff);
  78         return qdisc_enqueue_tail(skb, sch);
  79 }
  80
  81 static struct sk_buff *deepthought_dequeue(struct Qdisc *sch)
  82 {
  83         struct sk_buff *skb = qdisc_dequeue_head(sch);
  84         if (skb) {
  85                 if (psched_get_time() >= SKB_DT_INF(skb)->depart)
  86                         return skb;
  87                 else
  88                         qdisc_enqueue_tail(skb, sch);
  89         }
  90         return NULL;
  91 }
  92
  93 static int deepthought_qinit(struct Qdisc *sch, struct nlattr *opt)
  94 {
  95         u32 limit = qdisc_dev(sch)->tx_queue_len ? : 1;
  96         limit *= psched_mtu(qdisc_dev(sch));
  97         sch->limit = limit;
  98         return 0;
  99 }
 100
 101 static int deepthought_dump(struct Qdisc *sch, struct sk_buff *skb)
 102 {
 103         struct tc_fifo_qopt opt = {
 104                 .limit = sch->limit
 105         };
 106         NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 107         return skb->len;
 108 nla_put_failure:
 109         return -1;
 110 }
 111
 112 static struct Qdisc_ops deepthought_qdisc_ops __read_mostly = {
 113         .id             = "dtht",
 114         .priv_size      = 0,
 115         .enqueue        = deepthought_enqueue,
 116         .dequeue        = deepthought_dequeue,
 117         .peek           = qdisc_peek_head,
 118         .drop           = qdisc_queue_drop,
 119         .init           = deepthought_qinit,
 120         .reset          = qdisc_reset_queue,
 121         .change         = deepthought_qinit,
 122         .dump           = deepthought_dump,
 123         .owner          = THIS_MODULE,
 124 };
 125
 126 static int __init deepthought_init(void)
 127 {
 128         printk(KERN_INFO "%s: %s loaded!\n", MODULE_NAME, MODULE_DESC);
 129         return register_qdisc(&deepthought_qdisc_ops);
 130 }
 131
 132 static void __exit deepthought_exit(void)
 133 {
 134         unregister_qdisc(&deepthought_qdisc_ops);
 135         printk(KERN_INFO "%s: removed!\n", MODULE_NAME);
 136 }
 137
 138 module_init(deepthought_init);
 139 module_exit(deepthought_exit);
 140
 141 MODULE_LICENSE("GPL");
 142 MODULE_DESCRIPTION(MODULE_DESC);
 143 MODULE_AUTHOR("Daniel Borkmann <borkmann@iogearbox.net>");
 144