reciprocal_divide: update/correction of the algorithm

[mirror_ubuntu-artful-kernel.git] / net / sched / sch_netem.c

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index bccd52b36e97be79d446e233dedc960fe65d5f16..de1059af6da14c563115147852c4f52b80a9387d 100644 (file)
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -88,10 +88,10 @@ struct netem_sched_data {
        u32 duplicate;
        u32 reorder;
        u32 corrupt;
-       u32 rate;
+       u64 rate;
        s32 packet_overhead;
        u32 cell_size;
-       u32 cell_size_reciprocal;
+       struct reciprocal_value cell_size_reciprocal;
        s32 cell_overhead;
 
        struct crndstate {
@@ -110,6 +110,13 @@ struct netem_sched_data {
                CLG_GILB_ELL,
        } loss_model;
 
+       enum {
+               TX_IN_GAP_PERIOD = 1,
+               TX_IN_BURST_PERIOD,
+               LOST_IN_GAP_PERIOD,
+               LOST_IN_BURST_PERIOD,
+       } _4_state_model;
+
        /* Correlated Loss Generation models */
        struct clgstate {
                /* state of the Markov chain */
@@ -169,7 +176,7 @@ static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
 static void init_crandom(struct crndstate *state, unsigned long rho)
 {
        state->rho = rho;
-       state->last = net_random();
+       state->last = prandom_u32();
 }
 
 /* get_crandom - correlated random number generator
@@ -182,9 +189,9 @@ static u32 get_crandom(struct crndstate *state)
        unsigned long answer;
 
        if (state->rho == 0)    /* no correlation */
-               return net_random();
+               return prandom_u32();
 
-       value = net_random();
+       value = prandom_u32();
        rho = (u64)state->rho + 1;
        answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
        state->last = answer;
@@ -198,50 +205,52 @@ static u32 get_crandom(struct crndstate *state)
 static bool loss_4state(struct netem_sched_data *q)
 {
        struct clgstate *clg = &q->clg;
-       u32 rnd = net_random();
+       u32 rnd = prandom_u32();
 
        /*
         * Makes a comparison between rnd and the transition
         * probabilities outgoing from the current state, then decides the
         * next state and if the next packet has to be transmitted or lost.
         * The four states correspond to:
-        *   1 => successfully transmitted packets within a gap period
-        *   4 => isolated losses within a gap period
-        *   3 => lost packets within a burst period
-        *   2 => successfully transmitted packets within a burst period
+        *   TX_IN_GAP_PERIOD => successfully transmitted packets within a gap period
+        *   LOST_IN_BURST_PERIOD => isolated losses within a gap period
+        *   LOST_IN_GAP_PERIOD => lost packets within a burst period
+        *   TX_IN_GAP_PERIOD => successfully transmitted packets within a burst period
         */
        switch (clg->state) {
-       case 1:
+       case TX_IN_GAP_PERIOD:
                if (rnd < clg->a4) {
-                       clg->state = 4;
+                       clg->state = LOST_IN_BURST_PERIOD;
                        return true;
                } else if (clg->a4 < rnd && rnd < clg->a1 + clg->a4) {
-                       clg->state = 3;
+                       clg->state = LOST_IN_GAP_PERIOD;
                        return true;
-               } else if (clg->a1 + clg->a4 < rnd)
-                       clg->state = 1;
+               } else if (clg->a1 + clg->a4 < rnd) {
+                       clg->state = TX_IN_GAP_PERIOD;
+               }
 
                break;
-       case 2:
+       case TX_IN_BURST_PERIOD:
                if (rnd < clg->a5) {
-                       clg->state = 3;
+                       clg->state = LOST_IN_GAP_PERIOD;
                        return true;
-               } else
-                       clg->state = 2;
+               } else {
+                       clg->state = TX_IN_BURST_PERIOD;
+               }
 
                break;
-       case 3:
+       case LOST_IN_GAP_PERIOD:
                if (rnd < clg->a3)
-                       clg->state = 2;
+                       clg->state = TX_IN_BURST_PERIOD;
                else if (clg->a3 < rnd && rnd < clg->a2 + clg->a3) {
-                       clg->state = 1;
+                       clg->state = TX_IN_GAP_PERIOD;
                } else if (clg->a2 + clg->a3 < rnd) {
-                       clg->state = 3;
+                       clg->state = LOST_IN_GAP_PERIOD;
                        return true;
                }
                break;
-       case 4:
-               clg->state = 1;
+       case LOST_IN_BURST_PERIOD:
+               clg->state = TX_IN_GAP_PERIOD;
                break;
        }
 
@@ -264,15 +273,15 @@ static bool loss_gilb_ell(struct netem_sched_data *q)
 
        switch (clg->state) {
        case 1:
-               if (net_random() < clg->a1)
+               if (prandom_u32() < clg->a1)
                        clg->state = 2;
-               if (net_random() < clg->a4)
+               if (prandom_u32() < clg->a4)
                        return true;
                break;
        case 2:
-               if (net_random() < clg->a2)
+               if (prandom_u32() < clg->a2)
                        clg->state = 1;
-               if (net_random() > clg->a3)
+               if (prandom_u32() > clg->a3)
                        return true;
        }
 
@@ -457,7 +466,8 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
                     skb_checksum_help(skb)))
                        return qdisc_drop(skb, sch);
 
-               skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
+               skb->data[prandom_u32() % skb_headlen(skb)] ^=
+                       1<<(prandom_u32() % 8);
        }
 
        if (unlikely(skb_queue_len(&sch->q) >= sch->limit))
@@ -495,7 +505,7 @@ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
                                now = netem_skb_cb(last)->time_to_send;
                        }
 
-                       delay += packet_len_2_sched_time(skb->len, q);
+                       delay += packet_len_2_sched_time(qdisc_pkt_len(skb), q);
                }
 
                cb->time_to_send = now + delay;
@@ -715,9 +725,11 @@ static void get_rate(struct Qdisc *sch, const struct nlattr *attr)
        q->rate = r->rate;
        q->packet_overhead = r->packet_overhead;
        q->cell_size = r->cell_size;
+       q->cell_overhead = r->cell_overhead;
        if (q->cell_size)
                q->cell_size_reciprocal = reciprocal_value(q->cell_size);
-       q->cell_overhead = r->cell_overhead;
+       else
+               q->cell_size_reciprocal = (struct reciprocal_value) { 0 };
 }
 
 static int get_loss_clg(struct Qdisc *sch, const struct nlattr *attr)
@@ -729,7 +741,7 @@ static int get_loss_clg(struct Qdisc *sch, const struct nlattr *attr)
        nla_for_each_nested(la, attr, rem) {
                u16 type = nla_type(la);
 
-               switch(type) {
+               switch (type) {
                case NETEM_LOSS_GI: {
                        const struct tc_netem_gimodel *gi = nla_data(la);
 
@@ -782,6 +794,7 @@ static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
        [TCA_NETEM_RATE]        = { .len = sizeof(struct tc_netem_rate) },
        [TCA_NETEM_LOSS]        = { .type = NLA_NESTED },
        [TCA_NETEM_ECN]         = { .type = NLA_U32 },
+       [TCA_NETEM_RATE64]      = { .type = NLA_U64 },
 };
 
 static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla,
@@ -852,6 +865,10 @@ static int netem_change(struct Qdisc *sch, struct nlattr *opt)
        if (tb[TCA_NETEM_RATE])
                get_rate(sch, tb[TCA_NETEM_RATE]);
 
+       if (tb[TCA_NETEM_RATE64])
+               q->rate = max_t(u64, q->rate,
+                               nla_get_u64(tb[TCA_NETEM_RATE64]));
+
        if (tb[TCA_NETEM_ECN])
                q->ecn = nla_get_u32(tb[TCA_NETEM_ECN]);
 
@@ -974,7 +991,13 @@ static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
        if (nla_put(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt))
                goto nla_put_failure;
 
-       rate.rate = q->rate;
+       if (q->rate >= (1ULL << 32)) {
+               if (nla_put_u64(skb, TCA_NETEM_RATE64, q->rate))
+                       goto nla_put_failure;
+               rate.rate = ~0U;
+       } else {
+               rate.rate = q->rate;
+       }
        rate.packet_overhead = q->packet_overhead;
        rate.cell_size = q->cell_size;
        rate.cell_overhead = q->cell_overhead;