URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [net/] [sched/] [sch_gred.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*
 * net/sched/sch_gred.c Generic Random Early Detection queue.
 *
 *
 *              This program is free software; you can redistribute it and/or
 *              modify it under the terms of the GNU General Public License
 *              as published by the Free Software Foundation; either version
 *              2 of the License, or (at your option) any later version.
 *
 * Authors:    J Hadi Salim (hadi@cyberus.ca) 1998-2002
 *
 *             991129: -  Bug fix with grio mode
 *                     - a better sing. AvgQ mode with Grio(WRED)
 *                     - A finer grained VQ dequeue based on sugestion
 *                       from Ren Liu
 *                     - More error checks
 *
 *
 *
 *  For all the glorious comments look at Alexey's sch_red.c
 */
 
#include <linux/config.h>
#include <linux/module.h>
#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/interrupt.h>
#include <linux/if_ether.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/etherdevice.h>
#include <linux/notifier.h>
#include <net/ip.h>
#include <net/route.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <net/pkt_sched.h>
 
#if 1 /* control */
#define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
#else
#define DPRINTK(format,args...)
#endif
 
#if 0 /* data */
#define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
#else
#define D2PRINTK(format,args...)
#endif
 
struct gred_sched_data;
struct gred_sched;
 
struct gred_sched_data
{
/* Parameters */
        u32             limit;          /* HARD maximal queue length    */
        u32             qth_min;        /* Min average length threshold: A scaled */
        u32             qth_max;        /* Max average length threshold: A scaled */
        u32             DP;             /* the drop pramaters */
        char            Wlog;           /* log(W)               */
        char            Plog;           /* random number bits   */
        u32             Scell_max;
        u32             Rmask;
        u32             bytesin;        /* bytes seen on virtualQ so far*/
        u32             packetsin;      /* packets seen on virtualQ so far*/
        u32             backlog;        /* bytes on the virtualQ */
        u32             forced; /* packets dropped for exceeding limits */
        u32             early;  /* packets dropped as a warning */
        u32             other;  /* packets dropped by invoking drop() */
        u32             pdrop;  /* packets dropped because we exceeded physical queue limits */
        char            Scell_log;
        u8              Stab[256];
        u8              prio;        /* the prio of this vq */
 
/* Variables */
        unsigned long   qave;           /* Average queue length: A scaled */
        int             qcount;         /* Packets since last random number generation */
        u32             qR;             /* Cached random number */
 
        psched_time_t   qidlestart;     /* Start of idle period */
};
 
struct gred_sched
{
        struct gred_sched_data *tab[MAX_DPs];
        u32             DPs;
        u32             def;
        u8              initd;
        u8              grio;
        u8              eqp;
};
 
static int
gred_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
        psched_time_t now;
        struct gred_sched_data *q=NULL;
        struct gred_sched *t= (struct gred_sched *)sch->data;
        unsigned long   qave=0;
        int i=0;
 
        if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {
                D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
                goto do_enqueue;
        }
 
 
        if ( ((skb->tc_index&0xf) > (t->DPs -1)) || !(q=t->tab[skb->tc_index&0xf])) {
                printk("GRED: setting to default (%d)\n ",t->def);
                if (!(q=t->tab[t->def])) {
                        DPRINTK("GRED: setting to default FAILED! dropping!! "
                            "(%d)\n ", t->def);
                        goto drop;
                }
                /* fix tc_index? --could be controvesial but needed for
                   requeueing */
                skb->tc_index=(skb->tc_index&0xfffffff0) | t->def;
        }
 
        D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
            "general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,
            sch->stats.backlog);
        /* sum up all the qaves of prios <= to ours to get the new qave*/
        if (!t->eqp && t->grio) {
                for (i=0;i<t->DPs;i++) {
                        if ((!t->tab[i]) || (i==q->DP))
                                continue;
 
                        if ((t->tab[i]->prio < q->prio) && (PSCHED_IS_PASTPERFECT(t->tab[i]->qidlestart)))
                                qave +=t->tab[i]->qave;
                }
 
        }
 
        q->packetsin++;
        q->bytesin+=skb->len;
 
        if (t->eqp && t->grio) {
                qave=0;
                q->qave=t->tab[t->def]->qave;
                q->qidlestart=t->tab[t->def]->qidlestart;
        }
 
        if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
                long us_idle;
                PSCHED_GET_TIME(now);
                us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max, 0);
                PSCHED_SET_PASTPERFECT(q->qidlestart);
 
                q->qave >>= q->Stab[(us_idle>>q->Scell_log)&0xFF];
        } else {
                if (t->eqp) {
                        q->qave += sch->stats.backlog - (q->qave >> q->Wlog);
                } else {
                        q->qave += q->backlog - (q->qave >> q->Wlog);
                }
 
        }
 
 
        if (t->eqp && t->grio)
                t->tab[t->def]->qave=q->qave;
 
        if ((q->qave+qave) < q->qth_min) {
                q->qcount = -1;
enqueue:
                if (q->backlog + skb->len <= q->limit) {
                        q->backlog += skb->len;
do_enqueue:
                        __skb_queue_tail(&sch->q, skb);
                        sch->stats.backlog += skb->len;
                        sch->stats.bytes += skb->len;
                        sch->stats.packets++;
                        return 0;
                } else {
                        q->pdrop++;
                }
 
drop:
                kfree_skb(skb);
                sch->stats.drops++;
                return NET_XMIT_DROP;
        }
        if ((q->qave+qave) >= q->qth_max) {
                q->qcount = -1;
                sch->stats.overlimits++;
                q->forced++;
                goto drop;
        }
        if (++q->qcount) {
                if ((((qave+q->qave) - q->qth_min)>>q->Wlog)*q->qcount < q->qR)
                        goto enqueue;
                q->qcount = 0;
                q->qR = net_random()&q->Rmask;
                sch->stats.overlimits++;
                q->early++;
                goto drop;
        }
        q->qR = net_random()&q->Rmask;
        goto enqueue;
}
 
static int
gred_requeue(struct sk_buff *skb, struct Qdisc* sch)
{
        struct gred_sched_data *q;
        struct gred_sched *t= (struct gred_sched *)sch->data;
        q= t->tab[(skb->tc_index&0xf)];
/* error checking here -- probably unnecessary */
        PSCHED_SET_PASTPERFECT(q->qidlestart);
 
        __skb_queue_head(&sch->q, skb);
        sch->stats.backlog += skb->len;
        q->backlog += skb->len;
        return 0;
}
 
static struct sk_buff *
gred_dequeue(struct Qdisc* sch)
{
        struct sk_buff *skb;
        struct gred_sched_data *q;
        struct gred_sched *t= (struct gred_sched *)sch->data;
 
        skb = __skb_dequeue(&sch->q);
        if (skb) {
                sch->stats.backlog -= skb->len;
                q= t->tab[(skb->tc_index&0xf)];
                if (q) {
                        q->backlog -= skb->len;
                        if (!q->backlog && !t->eqp)
                                PSCHED_GET_TIME(q->qidlestart);
                } else {
                        D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
                }
                return skb;
        }
 
        if (t->eqp) {
                        q= t->tab[t->def];
                        if (!q)
                                D2PRINTK("no default VQ set: Results will be "
                                       "screwed up\n");
                        else
                                PSCHED_GET_TIME(q->qidlestart);
        }
 
        return NULL;
}
 
static unsigned int gred_drop(struct Qdisc* sch)
{
        struct sk_buff *skb;
 
        struct gred_sched_data *q;
        struct gred_sched *t= (struct gred_sched *)sch->data;
 
        skb = __skb_dequeue_tail(&sch->q);
        if (skb) {
                unsigned int len = skb->len;
                sch->stats.backlog -= len;
                sch->stats.drops++;
                q= t->tab[(skb->tc_index&0xf)];
                if (q) {
                        q->backlog -= len;
                        q->other++;
                        if (!q->backlog && !t->eqp)
                                PSCHED_GET_TIME(q->qidlestart);
                } else {
                        D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
                }
 
                kfree_skb(skb);
                return len;
        }
 
        q=t->tab[t->def];
        if (!q) {
                D2PRINTK("no default VQ set: Results might be screwed up\n");
                return 0;
        }
 
        PSCHED_GET_TIME(q->qidlestart);
        return 0;
 
}
 
static void gred_reset(struct Qdisc* sch)
{
        int i;
        struct gred_sched_data *q;
        struct gred_sched *t= (struct gred_sched *)sch->data;
 
        __skb_queue_purge(&sch->q);
 
        sch->stats.backlog = 0;
 
        for (i=0;i<t->DPs;i++) {
                q= t->tab[i];
                if (!q)
                        continue;
                PSCHED_SET_PASTPERFECT(q->qidlestart);
                q->qave = 0;
                q->qcount = -1;
                q->backlog = 0;
                q->other=0;
                q->forced=0;
                q->pdrop=0;
                q->early=0;
        }
}
 
static int gred_change(struct Qdisc *sch, struct rtattr *opt)
{
        struct gred_sched *table = (struct gred_sched *)sch->data;
        struct gred_sched_data *q;
        struct tc_gred_qopt *ctl;
        struct tc_gred_sopt *sopt;
        struct rtattr *tb[TCA_GRED_STAB];
        struct rtattr *tb2[TCA_GRED_DPS];
        int i;
 
        if (opt == NULL ||
                rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )
                        return -EINVAL;
 
        if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0) {
                rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),
                    RTA_PAYLOAD(opt));
 
                if (tb2[TCA_GRED_DPS-1] == 0)
                        return -EINVAL;
 
                sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);
                table->DPs=sopt->DPs;
                table->def=sopt->def_DP;
                table->grio=sopt->grio;
                table->initd=0;
                /* probably need to clear all the table DP entries as well */
                MOD_INC_USE_COUNT;
                return 0;
            }
 
 
        if (!table->DPs || tb[TCA_GRED_PARMS-1] == 0 || tb[TCA_GRED_STAB-1] == 0 ||
                RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) ||
                RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
                        return -EINVAL;
 
        ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
        if (ctl->DP > MAX_DPs-1 ) {
                /* misbehaving is punished! Put in the default drop probability */
                DPRINTK("\nGRED: DP %u not in  the proper range fixed. New DP "
                        "set to default at %d\n",ctl->DP,table->def);
                ctl->DP=table->def;
        }
 
        if (table->tab[ctl->DP] == NULL) {
                table->tab[ctl->DP]=kmalloc(sizeof(struct gred_sched_data),
                                            GFP_KERNEL);
                if (NULL == table->tab[ctl->DP])
                        return -ENOMEM;
                memset(table->tab[ctl->DP], 0, (sizeof(struct gred_sched_data)));
        }
        q= table->tab[ctl->DP];
 
        if (table->grio) {
                if (ctl->prio <=0) {
                        if (table->def && table->tab[table->def]) {
                                DPRINTK("\nGRED: DP %u does not have a prio"
                                        "setting default to %d\n",ctl->DP,
                                        table->tab[table->def]->prio);
                                q->prio=table->tab[table->def]->prio;
                        } else {
                                DPRINTK("\nGRED: DP %u does not have a prio"
                                        " setting default to 8\n",ctl->DP);
                                q->prio=8;
                        }
                } else {
                        q->prio=ctl->prio;
                }
        } else {
                q->prio=8;
        }
 
 
        q->DP=ctl->DP;
        q->Wlog = ctl->Wlog;
        q->Plog = ctl->Plog;
        q->limit = ctl->limit;
        q->Scell_log = ctl->Scell_log;
        q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
        q->Scell_max = (255<<q->Scell_log);
        q->qth_min = ctl->qth_min<<ctl->Wlog;
        q->qth_max = ctl->qth_max<<ctl->Wlog;
        q->qave=0;
        q->backlog=0;
        q->qcount = -1;
        q->other=0;
        q->forced=0;
        q->pdrop=0;
        q->early=0;
 
        PSCHED_SET_PASTPERFECT(q->qidlestart);
        memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);
 
        if ( table->initd && table->grio) {
        /* this looks ugly but its not in the fast path */
                for (i=0;i<table->DPs;i++) {
                        if ((!table->tab[i]) || (i==q->DP) )
                                continue;
                        if (table->tab[i]->prio == q->prio ){
                                /* WRED mode detected */
                                table->eqp=1;
                                break;
                        }
                }
        }
 
        if (!table->initd) {
                table->initd=1;
                /*
                the first entry also goes into the default until
                over-written
                */
 
                if (table->tab[table->def] == NULL) {
                        table->tab[table->def]=
                                kmalloc(sizeof(struct gred_sched_data), GFP_KERNEL);
                        if (NULL == table->tab[table->def])
                                return -ENOMEM;
 
                        memset(table->tab[table->def], 0,
                               (sizeof(struct gred_sched_data)));
                }
                q= table->tab[table->def];
                q->DP=table->def;
                q->Wlog = ctl->Wlog;
                q->Plog = ctl->Plog;
                q->limit = ctl->limit;
                q->Scell_log = ctl->Scell_log;
                q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
                q->Scell_max = (255<<q->Scell_log);
                q->qth_min = ctl->qth_min<<ctl->Wlog;
                q->qth_max = ctl->qth_max<<ctl->Wlog;
 
                if (table->grio)
                        q->prio=table->tab[ctl->DP]->prio;
                else
                        q->prio=8;
 
                q->qcount = -1;
                PSCHED_SET_PASTPERFECT(q->qidlestart);
                memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);
        }
        return 0;
 
}
 
static int gred_init(struct Qdisc *sch, struct rtattr *opt)
{
        struct gred_sched *table = (struct gred_sched *)sch->data;
        struct tc_gred_sopt *sopt;
        struct rtattr *tb[TCA_GRED_STAB];
        struct rtattr *tb2[TCA_GRED_DPS];
 
        if (opt == NULL ||
                rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )
                        return -EINVAL;
 
        if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0 ) {
                rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),RTA_PAYLOAD(opt));
 
                if (tb2[TCA_GRED_DPS-1] == 0)
                        return -EINVAL;
 
                sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);
                table->DPs=sopt->DPs;
                table->def=sopt->def_DP;
                table->grio=sopt->grio;
                table->initd=0;
                MOD_INC_USE_COUNT;
                return 0;
        }
 
        DPRINTK("\n GRED_INIT error!\n");
        return -EINVAL;
}
 
static int gred_dump(struct Qdisc *sch, struct sk_buff *skb)
{
        unsigned long qave;
        struct rtattr *rta;
        struct tc_gred_qopt *opt = NULL ;
        struct tc_gred_qopt *dst;
        struct gred_sched *table = (struct gred_sched *)sch->data;
        struct gred_sched_data *q;
        int i;
        unsigned char    *b = skb->tail;
 
        rta = (struct rtattr*)b;
        RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 
        opt=kmalloc(sizeof(struct tc_gred_qopt)*MAX_DPs, GFP_KERNEL);
 
        if (opt  == NULL) {
                DPRINTK("gred_dump:failed to malloc for %Zd\n",
                    sizeof(struct tc_gred_qopt)*MAX_DPs);
                goto rtattr_failure;
        }
 
        memset(opt, 0, (sizeof(struct tc_gred_qopt))*table->DPs);
 
        if (!table->initd) {
                DPRINTK("NO GRED Queues setup!\n");
        }
 
        for (i=0;i<MAX_DPs;i++) {
                dst= &opt[i];
                q= table->tab[i];
 
                if (!q) {
                        /* hack -- fix at some point with proper message
                           This is how we indicate to tc that there is no VQ
                           at this DP */
 
                        dst->DP=MAX_DPs+i;
                        continue;
                }
 
                dst->limit=q->limit;
                dst->qth_min=q->qth_min>>q->Wlog;
                dst->qth_max=q->qth_max>>q->Wlog;
                dst->DP=q->DP;
                dst->backlog=q->backlog;
                if (q->qave) {
                        if (table->eqp && table->grio) {
                                q->qidlestart=table->tab[table->def]->qidlestart;
                                q->qave=table->tab[table->def]->qave;
                        }
                        if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
                                long idle;
                                psched_time_t now;
                                PSCHED_GET_TIME(now);
                                idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max, 0);
                                qave  = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];
                                dst->qave = qave >> q->Wlog;
 
                        } else {
                                dst->qave = q->qave >> q->Wlog;
                        }
                } else {
                        dst->qave = 0;
                }
 
 
                dst->Wlog = q->Wlog;
                dst->Plog = q->Plog;
                dst->Scell_log = q->Scell_log;
                dst->other = q->other;
                dst->forced = q->forced;
                dst->early = q->early;
                dst->pdrop = q->pdrop;
                dst->prio = q->prio;
                dst->packets=q->packetsin;
                dst->bytesin=q->bytesin;
        }
 
        RTA_PUT(skb, TCA_GRED_PARMS, sizeof(struct tc_gred_qopt)*MAX_DPs, opt);
        rta->rta_len = skb->tail - b;
 
        kfree(opt);
        return skb->len;
 
rtattr_failure:
        if (opt)
                kfree(opt);
        DPRINTK("gred_dump: FAILURE!!!!\n");
 
/* also free the opt struct here */
        skb_trim(skb, b - skb->data);
        return -1;
}
 
static void gred_destroy(struct Qdisc *sch)
{
        struct gred_sched *table = (struct gred_sched *)sch->data;
        int i;
 
        for (i = 0;i < table->DPs; i++) {
                if (table->tab[i])
                        kfree(table->tab[i]);
        }
        MOD_DEC_USE_COUNT;
}
 
struct Qdisc_ops gred_qdisc_ops =
{
        NULL,
        NULL,
        "gred",
        sizeof(struct gred_sched),
        gred_enqueue,
        gred_dequeue,
        gred_requeue,
        gred_drop,
        gred_init,
        gred_reset,
        gred_destroy,
        gred_change, /* change */
        gred_dump,
};
 
 
#ifdef MODULE
int init_module(void)
{
        return register_qdisc(&gred_qdisc_ops);
}
 
void cleanup_module(void)
{
        unregister_qdisc(&gred_qdisc_ops);
}
#endif
MODULE_LICENSE("GPL");

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [net/] [sched/] [sch_gred.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
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			`*`
19			`*`
20			`* For all the glorious comments look at Alexey's sch_red.c`
21			`*/`
22
23			`#include <linux/config.h>`
24			`#include <linux/module.h>`
25			`#include <asm/uaccess.h>`
26			`#include <asm/system.h>`
27			`#include <asm/bitops.h>`
28			`#include <linux/types.h>`
29			`#include <linux/kernel.h>`
30			`#include <linux/sched.h>`
31			`#include <linux/string.h>`
32			`#include <linux/mm.h>`
33			`#include <linux/socket.h>`
34			`#include <linux/sockios.h>`
35			`#include <linux/in.h>`
36			`#include <linux/errno.h>`
37			`#include <linux/interrupt.h>`
38			`#include <linux/if_ether.h>`
39			`#include <linux/inet.h>`
40			`#include <linux/netdevice.h>`
41			`#include <linux/etherdevice.h>`
42			`#include <linux/notifier.h>`
43			`#include <net/ip.h>`
44			`#include <net/route.h>`
45			`#include <linux/skbuff.h>`
46			`#include <net/sock.h>`
47			`#include <net/pkt_sched.h>`
48
49			`#if 1 /* control */`
50			`#define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)`
51			`#else`
52			`#define DPRINTK(format,args...)`
53			`#endif`
54
55			`#if 0 /* data */`
56			`#define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)`
57			`#else`
58			`#define D2PRINTK(format,args...)`
59			`#endif`
60
61			`struct gred_sched_data;`
62			`struct gred_sched;`
63
64			`struct gred_sched_data`
65			`{`
66			`/* Parameters */`
67			`u32 limit; /* HARD maximal queue length */`
68			`u32 qth_min; /* Min average length threshold: A scaled */`
69			`u32 qth_max; /* Max average length threshold: A scaled */`
70			`u32 DP; /* the drop pramaters */`
71			`char Wlog; /* log(W) */`
72			`char Plog; /* random number bits */`
73			`u32 Scell_max;`
74			`u32 Rmask;`
75			`u32 bytesin; /* bytes seen on virtualQ so far*/`
76			`u32 packetsin; /* packets seen on virtualQ so far*/`
77			`u32 backlog; /* bytes on the virtualQ */`
78			`u32 forced; /* packets dropped for exceeding limits */`
79			`u32 early; /* packets dropped as a warning */`
80			`u32 other; /* packets dropped by invoking drop() */`
81			`u32 pdrop; /* packets dropped because we exceeded physical queue limits */`
82			`char Scell_log;`
83			`u8 Stab[256];`
84			`u8 prio; /* the prio of this vq */`
85
86			`/* Variables */`
87			`unsigned long qave; /* Average queue length: A scaled */`
88			`int qcount; /* Packets since last random number generation */`
89			`u32 qR; /* Cached random number */`
90
91			`psched_time_t qidlestart; /* Start of idle period */`
92			`};`
93
94			`struct gred_sched`
95			`{`
96			`struct gred_sched_data *tab[MAX_DPs];`
97			`u32 DPs;`
98			`u32 def;`
99			`u8 initd;`
100			`u8 grio;`
101			`u8 eqp;`
102			`};`
103
104			`static int`
105			`gred_enqueue(struct sk_buff skb, struct Qdisc sch)`
106			`{`
107			`psched_time_t now;`
108			`struct gred_sched_data *q=NULL;`
109			`struct gred_sched t= (struct gred_sched )sch->data;`
110			`unsigned long qave=0;`
111			`int i=0;`
112
113			`if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {`
114			`D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");`
115			`goto do_enqueue;`
116			`}`
117
118
119			`if ( ((skb->tc_index&0xf) > (t->DPs -1)) \|\| !(q=t->tab[skb->tc_index&0xf])) {`
120			`printk("GRED: setting to default (%d)\n ",t->def);`
121			`if (!(q=t->tab[t->def])) {`
122			`DPRINTK("GRED: setting to default FAILED! dropping!! "`
123			`"(%d)\n ", t->def);`
124			`goto drop;`
125			`}`
126			`/* fix tc_index? --could be controvesial but needed for`
127			`requeueing */`
128			`skb->tc_index=(skb->tc_index&0xfffffff0) \| t->def;`
129			`}`
130
131			`D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "`
132			`"general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,`
133			`sch->stats.backlog);`
134			`/* sum up all the qaves of prios <= to ours to get the new qave*/`
135			`if (!t->eqp && t->grio) {`
136			`for (i=0;i<t->DPs;i++) {`
137			`if ((!t->tab[i]) \|\| (i==q->DP))`
138			`continue;`
139
140			`if ((t->tab[i]->prio < q->prio) && (PSCHED_IS_PASTPERFECT(t->tab[i]->qidlestart)))`
141			`qave +=t->tab[i]->qave;`
142			`}`
143
144			`}`
145
146			`q->packetsin++;`
147			`q->bytesin+=skb->len;`
148
149			`if (t->eqp && t->grio) {`
150			`qave=0;`
151			`q->qave=t->tab[t->def]->qave;`
152			`q->qidlestart=t->tab[t->def]->qidlestart;`
153			`}`
154
155			`if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {`
156			`long us_idle;`
157			`PSCHED_GET_TIME(now);`
158			`us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max, 0);`
159			`PSCHED_SET_PASTPERFECT(q->qidlestart);`
160
161			`q->qave >>= q->Stab[(us_idle>>q->Scell_log)&0xFF];`
162			`} else {`
163			`if (t->eqp) {`
164			`q->qave += sch->stats.backlog - (q->qave >> q->Wlog);`
165			`} else {`
166			`q->qave += q->backlog - (q->qave >> q->Wlog);`
167			`}`
168
169			`}`
170
171
172			`if (t->eqp && t->grio)`
173			`t->tab[t->def]->qave=q->qave;`
174
175			`if ((q->qave+qave) < q->qth_min) {`
176			`q->qcount = -1;`
177			`enqueue:`
178			`if (q->backlog + skb->len <= q->limit) {`
179			`q->backlog += skb->len;`
180			`do_enqueue:`
181			`__skb_queue_tail(&sch->q, skb);`
182			`sch->stats.backlog += skb->len;`
183			`sch->stats.bytes += skb->len;`
184			`sch->stats.packets++;`
185			`return 0;`
186			`} else {`
187			`q->pdrop++;`
188			`}`
189
190			`drop:`
191			`kfree_skb(skb);`
192			`sch->stats.drops++;`
193			`return NET_XMIT_DROP;`
194			`}`
195			`if ((q->qave+qave) >= q->qth_max) {`
196			`q->qcount = -1;`
197			`sch->stats.overlimits++;`
198			`q->forced++;`
199			`goto drop;`
200			`}`
201			`if (++q->qcount) {`
202			`if ((((qave+q->qave) - q->qth_min)>>q->Wlog)*q->qcount < q->qR)`
203			`goto enqueue;`
204			`q->qcount = 0;`
205			`q->qR = net_random()&q->Rmask;`
206			`sch->stats.overlimits++;`
207			`q->early++;`
208			`goto drop;`
209			`}`
210			`q->qR = net_random()&q->Rmask;`
211			`goto enqueue;`
212			`}`
213
214			`static int`
215			`gred_requeue(struct sk_buff skb, struct Qdisc sch)`
216			`{`
217			`struct gred_sched_data *q;`
218			`struct gred_sched t= (struct gred_sched )sch->data;`
219			`q= t->tab[(skb->tc_index&0xf)];`
220			`/* error checking here -- probably unnecessary */`
221			`PSCHED_SET_PASTPERFECT(q->qidlestart);`
222
223			`__skb_queue_head(&sch->q, skb);`
224			`sch->stats.backlog += skb->len;`
225			`q->backlog += skb->len;`
226			`return 0;`
227			`}`
228
229			`static struct sk_buff *`
230			`gred_dequeue(struct Qdisc* sch)`
231			`{`
232			`struct sk_buff *skb;`
233			`struct gred_sched_data *q;`
234			`struct gred_sched t= (struct gred_sched )sch->data;`
235
236			`skb = __skb_dequeue(&sch->q);`
237			`if (skb) {`
238			`sch->stats.backlog -= skb->len;`
239			`q= t->tab[(skb->tc_index&0xf)];`
240			`if (q) {`
241			`q->backlog -= skb->len;`
242			`if (!q->backlog && !t->eqp)`
243			`PSCHED_GET_TIME(q->qidlestart);`
244			`} else {`
245			`D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);`
246			`}`
247			`return skb;`
248			`}`
249
250			`if (t->eqp) {`
251			`q= t->tab[t->def];`
252			`if (!q)`
253			`D2PRINTK("no default VQ set: Results will be "`
254			`"screwed up\n");`
255			`else`
256			`PSCHED_GET_TIME(q->qidlestart);`
257			`}`
258
259			`return NULL;`
260			`}`
261
262			`static unsigned int gred_drop(struct Qdisc* sch)`
263			`{`
264			`struct sk_buff *skb;`
265
266			`struct gred_sched_data *q;`
267			`struct gred_sched t= (struct gred_sched )sch->data;`
268
269			`skb = __skb_dequeue_tail(&sch->q);`
270			`if (skb) {`
271			`unsigned int len = skb->len;`
272			`sch->stats.backlog -= len;`
273			`sch->stats.drops++;`
274			`q= t->tab[(skb->tc_index&0xf)];`
275			`if (q) {`
276			`q->backlog -= len;`
277			`q->other++;`
278			`if (!q->backlog && !t->eqp)`
279			`PSCHED_GET_TIME(q->qidlestart);`
280			`} else {`
281			`D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);`
282			`}`
283
284			`kfree_skb(skb);`
285			`return len;`
286			`}`
287
288			`q=t->tab[t->def];`
289			`if (!q) {`
290			`D2PRINTK("no default VQ set: Results might be screwed up\n");`
291			`return 0;`
292			`}`
293
294			`PSCHED_GET_TIME(q->qidlestart);`
295			`return 0;`
296
297			`}`
298
299			`static void gred_reset(struct Qdisc* sch)`
300			`{`
301			`int i;`
302			`struct gred_sched_data *q;`
303			`struct gred_sched t= (struct gred_sched )sch->data;`
304
305			`__skb_queue_purge(&sch->q);`
306
307			`sch->stats.backlog = 0;`
308
309			`for (i=0;i<t->DPs;i++) {`
310			`q= t->tab[i];`
311			`if (!q)`
312			`continue;`
313			`PSCHED_SET_PASTPERFECT(q->qidlestart);`
314			`q->qave = 0;`
315			`q->qcount = -1;`
316			`q->backlog = 0;`
317			`q->other=0;`
318			`q->forced=0;`
319			`q->pdrop=0;`
320			`q->early=0;`
321			`}`
322			`}`
323
324			`static int gred_change(struct Qdisc sch, struct rtattr opt)`
325			`{`
326			`struct gred_sched table = (struct gred_sched )sch->data;`
327			`struct gred_sched_data *q;`
328			`struct tc_gred_qopt *ctl;`
329			`struct tc_gred_sopt *sopt;`
330			`struct rtattr *tb[TCA_GRED_STAB];`
331			`struct rtattr *tb2[TCA_GRED_DPS];`
332			`int i;`
333
334			`if (opt == NULL \|\|`
335			`rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )`
336			`return -EINVAL;`
337
338			`if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0) {`
339			`rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),`
340			`RTA_PAYLOAD(opt));`
341
342			`if (tb2[TCA_GRED_DPS-1] == 0)`
343			`return -EINVAL;`
344
345			`sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);`
346			`table->DPs=sopt->DPs;`
347			`table->def=sopt->def_DP;`
348			`table->grio=sopt->grio;`
349			`table->initd=0;`
350			`/* probably need to clear all the table DP entries as well */`
351			`MOD_INC_USE_COUNT;`
352			`return 0;`
353			`}`
354
355
356			`if (!table->DPs \|\| tb[TCA_GRED_PARMS-1] == 0 \|\| tb[TCA_GRED_STAB-1] == 0 \|\|`
357			`RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) \|\|`
358			`RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)`
359			`return -EINVAL;`
360
361			`ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);`
362			`if (ctl->DP > MAX_DPs-1 ) {`
363			`/* misbehaving is punished! Put in the default drop probability */`
364			`DPRINTK("\nGRED: DP %u not in the proper range fixed. New DP "`
365			`"set to default at %d\n",ctl->DP,table->def);`
366			`ctl->DP=table->def;`
367			`}`
368
369			`if (table->tab[ctl->DP] == NULL) {`
370			`table->tab[ctl->DP]=kmalloc(sizeof(struct gred_sched_data),`
371			`GFP_KERNEL);`
372			`if (NULL == table->tab[ctl->DP])`
373			`return -ENOMEM;`
374			`memset(table->tab[ctl->DP], 0, (sizeof(struct gred_sched_data)));`
375			`}`
376			`q= table->tab[ctl->DP];`
377
378			`if (table->grio) {`
379			`if (ctl->prio <=0) {`
380			`if (table->def && table->tab[table->def]) {`
381			`DPRINTK("\nGRED: DP %u does not have a prio"`
382			`"setting default to %d\n",ctl->DP,`
383			`table->tab[table->def]->prio);`
384			`q->prio=table->tab[table->def]->prio;`
385			`} else {`
386			`DPRINTK("\nGRED: DP %u does not have a prio"`
387			`" setting default to 8\n",ctl->DP);`
388			`q->prio=8;`
389			`}`
390			`} else {`
391			`q->prio=ctl->prio;`
392			`}`
393			`} else {`
394			`q->prio=8;`
395			`}`
396
397
398			`q->DP=ctl->DP;`
399			`q->Wlog = ctl->Wlog;`
400			`q->Plog = ctl->Plog;`
401			`q->limit = ctl->limit;`
402			`q->Scell_log = ctl->Scell_log;`
403			`q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;`
404			`q->Scell_max = (255<<q->Scell_log);`
405			`q->qth_min = ctl->qth_min<<ctl->Wlog;`
406			`q->qth_max = ctl->qth_max<<ctl->Wlog;`
407			`q->qave=0;`
408			`q->backlog=0;`
409			`q->qcount = -1;`
410			`q->other=0;`
411			`q->forced=0;`
412			`q->pdrop=0;`
413			`q->early=0;`
414
415			`PSCHED_SET_PASTPERFECT(q->qidlestart);`
416			`memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);`
417
418			`if ( table->initd && table->grio) {`
419			`/* this looks ugly but its not in the fast path */`
420			`for (i=0;i<table->DPs;i++) {`
421			`if ((!table->tab[i]) \|\| (i==q->DP) )`
422			`continue;`
423			`if (table->tab[i]->prio == q->prio ){`
424			`/* WRED mode detected */`
425			`table->eqp=1;`
426			`break;`
427			`}`
428			`}`
429			`}`
430
431			`if (!table->initd) {`
432			`table->initd=1;`
433			`/*`
434			`the first entry also goes into the default until`
435			`over-written`
436			`*/`
437
438			`if (table->tab[table->def] == NULL) {`
439			`table->tab[table->def]=`
440			`kmalloc(sizeof(struct gred_sched_data), GFP_KERNEL);`
441			`if (NULL == table->tab[table->def])`
442			`return -ENOMEM;`
443
444			`memset(table->tab[table->def], 0,`
445			`(sizeof(struct gred_sched_data)));`
446			`}`
447			`q= table->tab[table->def];`
448			`q->DP=table->def;`
449			`q->Wlog = ctl->Wlog;`
450			`q->Plog = ctl->Plog;`
451			`q->limit = ctl->limit;`
452			`q->Scell_log = ctl->Scell_log;`
453			`q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;`
454			`q->Scell_max = (255<<q->Scell_log);`
455			`q->qth_min = ctl->qth_min<<ctl->Wlog;`
456			`q->qth_max = ctl->qth_max<<ctl->Wlog;`
457
458			`if (table->grio)`
459			`q->prio=table->tab[ctl->DP]->prio;`
460			`else`
461			`q->prio=8;`
462
463			`q->qcount = -1;`
464			`PSCHED_SET_PASTPERFECT(q->qidlestart);`
465			`memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);`
466			`}`
467			`return 0;`
468
469			`}`
470
471			`static int gred_init(struct Qdisc sch, struct rtattr opt)`
472			`{`
473			`struct gred_sched table = (struct gred_sched )sch->data;`
474			`struct tc_gred_sopt *sopt;`
475			`struct rtattr *tb[TCA_GRED_STAB];`
476			`struct rtattr *tb2[TCA_GRED_DPS];`
477
478			`if (opt == NULL \|\|`
479			`rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )`
480			`return -EINVAL;`
481
482			`if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0 ) {`
483			`rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),RTA_PAYLOAD(opt));`
484
485			`if (tb2[TCA_GRED_DPS-1] == 0)`
486			`return -EINVAL;`
487
488			`sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);`
489			`table->DPs=sopt->DPs;`
490			`table->def=sopt->def_DP;`
491			`table->grio=sopt->grio;`
492			`table->initd=0;`
493			`MOD_INC_USE_COUNT;`
494			`return 0;`
495			`}`
496
497			`DPRINTK("\n GRED_INIT error!\n");`
498			`return -EINVAL;`
499			`}`
500
501			`static int gred_dump(struct Qdisc sch, struct sk_buff skb)`
502			`{`
503			`unsigned long qave;`
504			`struct rtattr *rta;`
505			`struct tc_gred_qopt *opt = NULL ;`
506			`struct tc_gred_qopt *dst;`
507			`struct gred_sched table = (struct gred_sched )sch->data;`
508			`struct gred_sched_data *q;`
509			`int i;`
510			`unsigned char *b = skb->tail;`
511
512			`rta = (struct rtattr*)b;`
513			`RTA_PUT(skb, TCA_OPTIONS, 0, NULL);`
514
515			`opt=kmalloc(sizeof(struct tc_gred_qopt)*MAX_DPs, GFP_KERNEL);`
516
517			`if (opt == NULL) {`
518			`DPRINTK("gred_dump:failed to malloc for %Zd\n",`
519			`sizeof(struct tc_gred_qopt)*MAX_DPs);`
520			`goto rtattr_failure;`
521			`}`
522
523			`memset(opt, 0, (sizeof(struct tc_gred_qopt))*table->DPs);`
524
525			`if (!table->initd) {`
526			`DPRINTK("NO GRED Queues setup!\n");`
527			`}`
528
529			`for (i=0;i<MAX_DPs;i++) {`
530			`dst= &opt[i];`
531			`q= table->tab[i];`
532
533			`if (!q) {`
534			`/* hack -- fix at some point with proper message`
535			`This is how we indicate to tc that there is no VQ`
536			`at this DP */`
537
538			`dst->DP=MAX_DPs+i;`
539			`continue;`
540			`}`
541
542			`dst->limit=q->limit;`
543			`dst->qth_min=q->qth_min>>q->Wlog;`
544			`dst->qth_max=q->qth_max>>q->Wlog;`
545			`dst->DP=q->DP;`
546			`dst->backlog=q->backlog;`
547			`if (q->qave) {`
548			`if (table->eqp && table->grio) {`
549			`q->qidlestart=table->tab[table->def]->qidlestart;`
550			`q->qave=table->tab[table->def]->qave;`
551			`}`
552			`if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {`
553			`long idle;`
554			`psched_time_t now;`
555			`PSCHED_GET_TIME(now);`
556			`idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max, 0);`
557			`qave = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];`
558			`dst->qave = qave >> q->Wlog;`
559
560			`} else {`
561			`dst->qave = q->qave >> q->Wlog;`
562			`}`
563			`} else {`
564			`dst->qave = 0;`
565			`}`
566
567
568			`dst->Wlog = q->Wlog;`
569			`dst->Plog = q->Plog;`
570			`dst->Scell_log = q->Scell_log;`
571			`dst->other = q->other;`
572			`dst->forced = q->forced;`
573			`dst->early = q->early;`
574			`dst->pdrop = q->pdrop;`
575			`dst->prio = q->prio;`
576			`dst->packets=q->packetsin;`
577			`dst->bytesin=q->bytesin;`
578			`}`
579
580			`RTA_PUT(skb, TCA_GRED_PARMS, sizeof(struct tc_gred_qopt)*MAX_DPs, opt);`
581			`rta->rta_len = skb->tail - b;`
582
583			`kfree(opt);`
584			`return skb->len;`
585
586			`rtattr_failure:`
587			`if (opt)`
588			`kfree(opt);`
589			`DPRINTK("gred_dump: FAILURE!!!!\n");`
590
591			`/* also free the opt struct here */`
592			`skb_trim(skb, b - skb->data);`
593			`return -1;`
594			`}`
595
596			`static void gred_destroy(struct Qdisc *sch)`
597			`{`
598			`struct gred_sched table = (struct gred_sched )sch->data;`
599			`int i;`
600
601			`for (i = 0;i < table->DPs; i++) {`
602			`if (table->tab[i])`
603			`kfree(table->tab[i]);`
604			`}`
605			`MOD_DEC_USE_COUNT;`
606			`}`
607
608			`struct Qdisc_ops gred_qdisc_ops =`
609			`{`
610			`NULL,`
611			`NULL,`
612			`"gred",`
613			`sizeof(struct gred_sched),`
614			`gred_enqueue,`
615			`gred_dequeue,`
616			`gred_requeue,`
617			`gred_drop,`
618			`gred_init,`
619			`gred_reset,`
620			`gred_destroy,`
621			`gred_change, /* change */`
622			`gred_dump,`
623			`};`
624
625
626			`#ifdef MODULE`
627			`int init_module(void)`
628			`{`
629			`return register_qdisc(&gred_qdisc_ops);`
630			`}`
631
632			`void cleanup_module(void)`
633			`{`
634			`unregister_qdisc(&gred_qdisc_ops);`
635			`}`
636			`#endif`
637			`MODULE_LICENSE("GPL");`