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

Subversion Repositories or1k

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

Details | Compare with Previous | View Log


/*
 * net/sched/cls_u32.c  Ugly (or Universal) 32bit key Packet Classifier.
 *
 *              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:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 *      The filters are packed to hash tables of key nodes
 *      with a set of 32bit key/mask pairs at every node.
 *      Nodes reference next level hash tables etc.
 *
 *      This scheme is the best universal classifier I managed to
 *      invent; it is not super-fast, but it is not slow (provided you
 *      program it correctly), and general enough.  And its relative
 *      speed grows as the number of rules becomes larger.
 *
 *      It seems that it represents the best middle point between
 *      speed and manageability both by human and by machine.
 *
 *      It is especially useful for link sharing combined with QoS;
 *      pure RSVP doesn't need such a general approach and can use
 *      much simpler (and faster) schemes, sort of cls_rsvp.c.
 */
 
#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#include <linux/config.h>
#include <linux/module.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 <linux/rtnetlink.h>
#include <net/ip.h>
#include <net/route.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <net/pkt_sched.h>
 
 
struct tc_u_knode
{
        struct tc_u_knode       *next;
        u32                     handle;
        struct tc_u_hnode       *ht_up;
#ifdef CONFIG_NET_CLS_POLICE
        struct tcf_police       *police;
#endif
        struct tcf_result       res;
        struct tc_u_hnode       *ht_down;
        struct tc_u32_sel       sel;
};
 
struct tc_u_hnode
{
        struct tc_u_hnode       *next;
        u32                     handle;
        struct tc_u_common      *tp_c;
        int                     refcnt;
        unsigned                divisor;
        u32                     hgenerator;
        struct tc_u_knode       *ht[1];
};
 
struct tc_u_common
{
        struct tc_u_common      *next;
        struct tc_u_hnode       *hlist;
        struct Qdisc            *q;
        int                     refcnt;
        u32                     hgenerator;
};
 
static struct tc_u_common *u32_list;
 
static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel)
{
        unsigned h = key & sel->hmask;
 
        h ^= h>>16;
        h ^= h>>8;
        return h;
}
 
static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res)
{
        struct {
                struct tc_u_knode *knode;
                u8                *ptr;
        } stack[TC_U32_MAXDEPTH];
 
        struct tc_u_hnode *ht = (struct tc_u_hnode*)tp->root;
        u8 *ptr = skb->nh.raw;
        struct tc_u_knode *n;
        int sdepth = 0;
        int off2 = 0;
        int sel = 0;
        int i;
 
next_ht:
        n = ht->ht[sel];
 
next_knode:
        if (n) {
                struct tc_u32_key *key = n->sel.keys;
 
                for (i = n->sel.nkeys; i>0; i--, key++) {
                        if ((*(u32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {
                                n = n->next;
                                goto next_knode;
                        }
                }
                if (n->ht_down == NULL) {
check_terminal:
                        if (n->sel.flags&TC_U32_TERMINAL) {
                                *res = n->res;
#ifdef CONFIG_NET_CLS_POLICE
                                if (n->police) {
                                        int pol_res = tcf_police(skb, n->police);
                                        if (pol_res >= 0)
                                                return pol_res;
                                } else
#endif
                                        return 0;
                        }
                        n = n->next;
                        goto next_knode;
                }
 
                /* PUSH */
                if (sdepth >= TC_U32_MAXDEPTH)
                        goto deadloop;
                stack[sdepth].knode = n;
                stack[sdepth].ptr = ptr;
                sdepth++;
 
                ht = n->ht_down;
                sel = 0;
                if (ht->divisor)
                        sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel);
 
                if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
                        goto next_ht;
 
                if (n->sel.flags&(TC_U32_OFFSET|TC_U32_VAROFFSET)) {
                        off2 = n->sel.off + 3;
                        if (n->sel.flags&TC_U32_VAROFFSET)
                                off2 += ntohs(n->sel.offmask & *(u16*)(ptr+n->sel.offoff)) >>n->sel.offshift;
                        off2 &= ~3;
                }
                if (n->sel.flags&TC_U32_EAT) {
                        ptr += off2;
                        off2 = 0;
                }
 
                if (ptr < skb->tail)
                        goto next_ht;
        }
 
        /* POP */
        if (sdepth--) {
                n = stack[sdepth].knode;
                ht = n->ht_up;
                ptr = stack[sdepth].ptr;
                goto check_terminal;
        }
        return -1;
 
deadloop:
        if (net_ratelimit())
                printk("cls_u32: dead loop\n");
        return -1;
}
 
static __inline__ struct tc_u_hnode *
u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)
{
        struct tc_u_hnode *ht;
 
        for (ht = tp_c->hlist; ht; ht = ht->next)
                if (ht->handle == handle)
                        break;
 
        return ht;
}
 
static __inline__ struct tc_u_knode *
u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
{
        unsigned sel;
        struct tc_u_knode *n;
 
        sel = TC_U32_HASH(handle);
        if (sel > ht->divisor)
                return 0;
 
        for (n = ht->ht[sel]; n; n = n->next)
                if (n->handle == handle)
                        return n;
 
        return NULL;
}
 
 
static unsigned long u32_get(struct tcf_proto *tp, u32 handle)
{
        struct tc_u_hnode *ht;
        struct tc_u_common *tp_c = tp->data;
 
        if (TC_U32_HTID(handle) == TC_U32_ROOT)
                ht = tp->root;
        else
                ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle));
 
        if (!ht)
                return 0;
 
        if (TC_U32_KEY(handle) == 0)
                return (unsigned long)ht;
 
        return (unsigned long)u32_lookup_key(ht, handle);
}
 
static void u32_put(struct tcf_proto *tp, unsigned long f)
{
}
 
static u32 gen_new_htid(struct tc_u_common *tp_c)
{
        int i = 0x800;
 
        do {
                if (++tp_c->hgenerator == 0x7FF)
                        tp_c->hgenerator = 1;
        } while (--i>0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
 
        return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
}
 
static int u32_init(struct tcf_proto *tp)
{
        struct tc_u_hnode *root_ht;
        struct tc_u_common *tp_c;
 
        MOD_INC_USE_COUNT;
 
        for (tp_c = u32_list; tp_c; tp_c = tp_c->next)
                if (tp_c->q == tp->q)
                        break;
 
        root_ht = kmalloc(sizeof(*root_ht), GFP_KERNEL);
        if (root_ht == NULL) {
                MOD_DEC_USE_COUNT;
                return -ENOBUFS;
        }
        memset(root_ht, 0, sizeof(*root_ht));
        root_ht->divisor = 0;
        root_ht->refcnt++;
        root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;
 
        if (tp_c == NULL) {
                tp_c = kmalloc(sizeof(*tp_c), GFP_KERNEL);
                if (tp_c == NULL) {
                        kfree(root_ht);
                        MOD_DEC_USE_COUNT;
                        return -ENOBUFS;
                }
                memset(tp_c, 0, sizeof(*tp_c));
                tp_c->q = tp->q;
                tp_c->next = u32_list;
                u32_list = tp_c;
        }
 
        tp_c->refcnt++;
        root_ht->next = tp_c->hlist;
        tp_c->hlist = root_ht;
        root_ht->tp_c = tp_c;
 
        tp->root = root_ht;
        tp->data = tp_c;
        return 0;
}
 
static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n)
{
        unsigned long cl;
 
        if ((cl = __cls_set_class(&n->res.class, 0)) != 0)
                tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
#ifdef CONFIG_NET_CLS_POLICE
        tcf_police_release(n->police);
#endif
        if (n->ht_down)
                n->ht_down->refcnt--;
        kfree(n);
        return 0;
}
 
static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode* key)
{
        struct tc_u_knode **kp;
        struct tc_u_hnode *ht = key->ht_up;
 
        if (ht) {
                for (kp = &ht->ht[TC_U32_HASH(key->handle)]; *kp; kp = &(*kp)->next) {
                        if (*kp == key) {
                                tcf_tree_lock(tp);
                                *kp = key->next;
                                tcf_tree_unlock(tp);
 
                                u32_destroy_key(tp, key);
                                return 0;
                        }
                }
        }
        BUG_TRAP(0);
        return 0;
}
 
static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
{
        struct tc_u_knode *n;
        unsigned h;
 
        for (h=0; h<=ht->divisor; h++) {
                while ((n = ht->ht[h]) != NULL) {
                        ht->ht[h] = n->next;
 
                        u32_destroy_key(tp, n);
                }
        }
}
 
static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
{
        struct tc_u_common *tp_c = tp->data;
        struct tc_u_hnode **hn;
 
        BUG_TRAP(!ht->refcnt);
 
        u32_clear_hnode(tp, ht);
 
        for (hn = &tp_c->hlist; *hn; hn = &(*hn)->next) {
                if (*hn == ht) {
                        *hn = ht->next;
                        kfree(ht);
                        return 0;
                }
        }
 
        BUG_TRAP(0);
        return -ENOENT;
}
 
static void u32_destroy(struct tcf_proto *tp)
{
        struct tc_u_common *tp_c = tp->data;
        struct tc_u_hnode *root_ht = xchg(&tp->root, NULL);
 
        BUG_TRAP(root_ht != NULL);
 
        if (root_ht && --root_ht->refcnt == 0)
                u32_destroy_hnode(tp, root_ht);
 
        if (--tp_c->refcnt == 0) {
                struct tc_u_hnode *ht;
                struct tc_u_common **tp_cp;
 
                for (tp_cp = &u32_list; *tp_cp; tp_cp = &(*tp_cp)->next) {
                        if (*tp_cp == tp_c) {
                                *tp_cp = tp_c->next;
                                break;
                        }
                }
 
                for (ht=tp_c->hlist; ht; ht = ht->next)
                        u32_clear_hnode(tp, ht);
 
                while ((ht = tp_c->hlist) != NULL) {
                        tp_c->hlist = ht->next;
 
                        BUG_TRAP(ht->refcnt == 0);
 
                        kfree(ht);
                };
 
                kfree(tp_c);
        }
 
        MOD_DEC_USE_COUNT;
        tp->data = NULL;
}
 
static int u32_delete(struct tcf_proto *tp, unsigned long arg)
{
        struct tc_u_hnode *ht = (struct tc_u_hnode*)arg;
 
        if (ht == NULL)
                return 0;
 
        if (TC_U32_KEY(ht->handle))
                return u32_delete_key(tp, (struct tc_u_knode*)ht);
 
        if (tp->root == ht)
                return -EINVAL;
 
        if (--ht->refcnt == 0)
                u32_destroy_hnode(tp, ht);
 
        return 0;
}
 
static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
{
        struct tc_u_knode *n;
        unsigned i = 0x7FF;
 
        for (n=ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
                if (i < TC_U32_NODE(n->handle))
                        i = TC_U32_NODE(n->handle);
        i++;
 
        return handle|(i>0xFFF ? 0xFFF : i);
}
 
static int u32_set_parms(struct Qdisc *q, unsigned long base,
                         struct tc_u_hnode *ht,
                         struct tc_u_knode *n, struct rtattr **tb,
                         struct rtattr *est)
{
        if (tb[TCA_U32_LINK-1]) {
                u32 handle = *(u32*)RTA_DATA(tb[TCA_U32_LINK-1]);
                struct tc_u_hnode *ht_down = NULL;
 
                if (TC_U32_KEY(handle))
                        return -EINVAL;
 
                if (handle) {
                        ht_down = u32_lookup_ht(ht->tp_c, handle);
 
                        if (ht_down == NULL)
                                return -EINVAL;
                        ht_down->refcnt++;
                }
 
                sch_tree_lock(q);
                ht_down = xchg(&n->ht_down, ht_down);
                sch_tree_unlock(q);
 
                if (ht_down)
                        ht_down->refcnt--;
        }
        if (tb[TCA_U32_CLASSID-1]) {
                unsigned long cl;
 
                n->res.classid = *(u32*)RTA_DATA(tb[TCA_U32_CLASSID-1]);
                sch_tree_lock(q);
                cl = __cls_set_class(&n->res.class, q->ops->cl_ops->bind_tcf(q, base, n->res.classid));
                sch_tree_unlock(q);
                if (cl)
                        q->ops->cl_ops->unbind_tcf(q, cl);
        }
#ifdef CONFIG_NET_CLS_POLICE
        if (tb[TCA_U32_POLICE-1]) {
                struct tcf_police *police = tcf_police_locate(tb[TCA_U32_POLICE-1], est);
 
                sch_tree_lock(q);
                police = xchg(&n->police, police);
                sch_tree_unlock(q);
 
                tcf_police_release(police);
        }
#endif
        return 0;
}
 
static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
                      struct rtattr **tca,
                      unsigned long *arg)
{
        struct tc_u_common *tp_c = tp->data;
        struct tc_u_hnode *ht;
        struct tc_u_knode *n;
        struct tc_u32_sel *s;
        struct rtattr *opt = tca[TCA_OPTIONS-1];
        struct rtattr *tb[TCA_U32_MAX];
        u32 htid;
        int err;
 
        if (opt == NULL)
                return handle ? -EINVAL : 0;
 
        if (rtattr_parse(tb, TCA_U32_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
                return -EINVAL;
 
        if ((n = (struct tc_u_knode*)*arg) != NULL) {
                if (TC_U32_KEY(n->handle) == 0)
                        return -EINVAL;
 
                return u32_set_parms(tp->q, base, n->ht_up, n, tb, tca[TCA_RATE-1]);
        }
 
        if (tb[TCA_U32_DIVISOR-1]) {
                unsigned divisor = *(unsigned*)RTA_DATA(tb[TCA_U32_DIVISOR-1]);
 
                if (--divisor > 0x100)
                        return -EINVAL;
                if (TC_U32_KEY(handle))
                        return -EINVAL;
                if (handle == 0) {
                        handle = gen_new_htid(tp->data);
                        if (handle == 0)
                                return -ENOMEM;
                }
                ht = kmalloc(sizeof(*ht) + divisor*sizeof(void*), GFP_KERNEL);
                if (ht == NULL)
                        return -ENOBUFS;
                memset(ht, 0, sizeof(*ht) + divisor*sizeof(void*));
                ht->tp_c = tp_c;
                ht->refcnt = 0;
                ht->divisor = divisor;
                ht->handle = handle;
                ht->next = tp_c->hlist;
                tp_c->hlist = ht;
                *arg = (unsigned long)ht;
                return 0;
        }
 
        if (tb[TCA_U32_HASH-1]) {
                htid = *(unsigned*)RTA_DATA(tb[TCA_U32_HASH-1]);
                if (TC_U32_HTID(htid) == TC_U32_ROOT) {
                        ht = tp->root;
                        htid = ht->handle;
                } else {
                        ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));
                        if (ht == NULL)
                                return -EINVAL;
                }
        } else {
                ht = tp->root;
                htid = ht->handle;
        }
 
        if (ht->divisor < TC_U32_HASH(htid))
                return -EINVAL;
 
        if (handle) {
                if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
                        return -EINVAL;
                handle = htid | TC_U32_NODE(handle);
        } else
                handle = gen_new_kid(ht, htid);
 
        if (tb[TCA_U32_SEL-1] == 0 ||
            RTA_PAYLOAD(tb[TCA_U32_SEL-1]) < sizeof(struct tc_u32_sel))
                return -EINVAL;
 
        s = RTA_DATA(tb[TCA_U32_SEL-1]);
        n = kmalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
        if (n == NULL)
                return -ENOBUFS;
        memset(n, 0, sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key));
        memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
        n->ht_up = ht;
        n->handle = handle;
        err = u32_set_parms(tp->q, base, ht, n, tb, tca[TCA_RATE-1]);
        if (err == 0) {
                struct tc_u_knode **ins;
                for (ins = &ht->ht[TC_U32_HASH(handle)]; *ins; ins = &(*ins)->next)
                        if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle))
                                break;
 
                n->next = *ins;
                wmb();
                *ins = n;
 
                *arg = (unsigned long)n;
                return 0;
        }
        kfree(n);
        return err;
}
 
static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
        struct tc_u_common *tp_c = tp->data;
        struct tc_u_hnode *ht;
        struct tc_u_knode *n;
        unsigned h;
 
        if (arg->stop)
                return;
 
        for (ht = tp_c->hlist; ht; ht = ht->next) {
                if (arg->count >= arg->skip) {
                        if (arg->fn(tp, (unsigned long)ht, arg) < 0) {
                                arg->stop = 1;
                                return;
                        }
                }
                arg->count++;
                for (h = 0; h <= ht->divisor; h++) {
                        for (n = ht->ht[h]; n; n = n->next) {
                                if (arg->count < arg->skip) {
                                        arg->count++;
                                        continue;
                                }
                                if (arg->fn(tp, (unsigned long)n, arg) < 0) {
                                        arg->stop = 1;
                                        return;
                                }
                                arg->count++;
                        }
                }
        }
}
 
static int u32_dump(struct tcf_proto *tp, unsigned long fh,
                     struct sk_buff *skb, struct tcmsg *t)
{
        struct tc_u_knode *n = (struct tc_u_knode*)fh;
        unsigned char    *b = skb->tail;
        struct rtattr *rta;
 
        if (n == NULL)
                return skb->len;
 
        t->tcm_handle = n->handle;
 
        rta = (struct rtattr*)b;
        RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 
        if (TC_U32_KEY(n->handle) == 0) {
                struct tc_u_hnode *ht = (struct tc_u_hnode*)fh;
                u32 divisor = ht->divisor+1;
                RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);
        } else {
                RTA_PUT(skb, TCA_U32_SEL,
                        sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
                        &n->sel);
                if (n->ht_up) {
                        u32 htid = n->handle & 0xFFFFF000;
                        RTA_PUT(skb, TCA_U32_HASH, 4, &htid);
                }
                if (n->res.classid)
                        RTA_PUT(skb, TCA_U32_CLASSID, 4, &n->res.classid);
                if (n->ht_down)
                        RTA_PUT(skb, TCA_U32_LINK, 4, &n->ht_down->handle);
#ifdef CONFIG_NET_CLS_POLICE
                if (n->police) {
                        struct rtattr * p_rta = (struct rtattr*)skb->tail;
 
                        RTA_PUT(skb, TCA_U32_POLICE, 0, NULL);
 
                        if (tcf_police_dump(skb, n->police) < 0)
                                goto rtattr_failure;
 
                        p_rta->rta_len = skb->tail - (u8*)p_rta;
                }
#endif
        }
 
        rta->rta_len = skb->tail - b;
#ifdef CONFIG_NET_CLS_POLICE
        if (TC_U32_KEY(n->handle) && n->police) {
                if (qdisc_copy_stats(skb, &n->police->stats))
                        goto rtattr_failure;
        }
#endif
        return skb->len;
 
rtattr_failure:
        skb_trim(skb, b - skb->data);
        return -1;
}
 
struct tcf_proto_ops cls_u32_ops = {
        NULL,
        "u32",
        u32_classify,
        u32_init,
        u32_destroy,
 
        u32_get,
        u32_put,
        u32_change,
        u32_delete,
        u32_walk,
        u32_dump
};
 
#ifdef MODULE
int init_module(void)
{
        return register_tcf_proto_ops(&cls_u32_ops);
}
 
void cleanup_module(void)
{
        unregister_tcf_proto_ops(&cls_u32_ops);
}
#endif
MODULE_LICENSE("GPL");

Browse

Tools

Subversion Repositories or1k

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

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
2			`* net/sched/cls_u32.c Ugly (or Universal) 32bit key Packet Classifier.`
3			`*`
4			`* This program is free software; you can redistribute it and/or`
5			`* modify it under the terms of the GNU General Public License`
6			`* as published by the Free Software Foundation; either version`
7			`* 2 of the License, or (at your option) any later version.`
8			`*`
9			`* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>`
10			`*`
11			`* The filters are packed to hash tables of key nodes`
12			`* with a set of 32bit key/mask pairs at every node.`
13			`* Nodes reference next level hash tables etc.`
14			`*`
15			`* This scheme is the best universal classifier I managed to`
16			`* invent; it is not super-fast, but it is not slow (provided you`
17			`* program it correctly), and general enough. And its relative`
18			`* speed grows as the number of rules becomes larger.`
19			`*`
20			`* It seems that it represents the best middle point between`
21			`* speed and manageability both by human and by machine.`
22			`*`
23			`* It is especially useful for link sharing combined with QoS;`
24			`* pure RSVP doesn't need such a general approach and can use`
25			`* much simpler (and faster) schemes, sort of cls_rsvp.c.`
26			`*/`
27
28			`#include <asm/uaccess.h>`
29			`#include <asm/system.h>`
30			`#include <asm/bitops.h>`
31			`#include <linux/config.h>`
32			`#include <linux/module.h>`
33			`#include <linux/types.h>`
34			`#include <linux/kernel.h>`
35			`#include <linux/sched.h>`
36			`#include <linux/string.h>`
37			`#include <linux/mm.h>`
38			`#include <linux/socket.h>`
39			`#include <linux/sockios.h>`
40			`#include <linux/in.h>`
41			`#include <linux/errno.h>`
42			`#include <linux/interrupt.h>`
43			`#include <linux/if_ether.h>`
44			`#include <linux/inet.h>`
45			`#include <linux/netdevice.h>`
46			`#include <linux/etherdevice.h>`
47			`#include <linux/notifier.h>`
48			`#include <linux/rtnetlink.h>`
49			`#include <net/ip.h>`
50			`#include <net/route.h>`
51			`#include <linux/skbuff.h>`
52			`#include <net/sock.h>`
53			`#include <net/pkt_sched.h>`
54
55
56			`struct tc_u_knode`
57			`{`
58			`struct tc_u_knode *next;`
59			`u32 handle;`
60			`struct tc_u_hnode *ht_up;`
61			`#ifdef CONFIG_NET_CLS_POLICE`
62			`struct tcf_police *police;`
63			`#endif`
64			`struct tcf_result res;`
65			`struct tc_u_hnode *ht_down;`
66			`struct tc_u32_sel sel;`
67			`};`
68
69			`struct tc_u_hnode`
70			`{`
71			`struct tc_u_hnode *next;`
72			`u32 handle;`
73			`struct tc_u_common *tp_c;`
74			`int refcnt;`
75			`unsigned divisor;`
76			`u32 hgenerator;`
77			`struct tc_u_knode *ht[1];`
78			`};`
79
80			`struct tc_u_common`
81			`{`
82			`struct tc_u_common *next;`
83			`struct tc_u_hnode *hlist;`
84			`struct Qdisc *q;`
85			`int refcnt;`
86			`u32 hgenerator;`
87			`};`
88
89			`static struct tc_u_common *u32_list;`
90
91			`static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel)`
92			`{`
93			`unsigned h = key & sel->hmask;`
94
95			`h ^= h>>16;`
96			`h ^= h>>8;`
97			`return h;`
98			`}`
99
100			`static int u32_classify(struct sk_buff skb, struct tcf_proto tp, struct tcf_result *res)`
101			`{`
102			`struct {`
103			`struct tc_u_knode *knode;`
104			`u8 *ptr;`
105			`} stack[TC_U32_MAXDEPTH];`
106
107			`struct tc_u_hnode ht = (struct tc_u_hnode)tp->root;`
108			`u8 *ptr = skb->nh.raw;`
109			`struct tc_u_knode *n;`
110			`int sdepth = 0;`
111			`int off2 = 0;`
112			`int sel = 0;`
113			`int i;`
114
115			`next_ht:`
116			`n = ht->ht[sel];`
117
118			`next_knode:`
119			`if (n) {`
120			`struct tc_u32_key *key = n->sel.keys;`
121
122			`for (i = n->sel.nkeys; i>0; i--, key++) {`
123			`if (((u32)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {`
124			`n = n->next;`
125			`goto next_knode;`
126			`}`
127			`}`
128			`if (n->ht_down == NULL) {`
129			`check_terminal:`
130			`if (n->sel.flags&TC_U32_TERMINAL) {`
131			`*res = n->res;`
132			`#ifdef CONFIG_NET_CLS_POLICE`
133			`if (n->police) {`
134			`int pol_res = tcf_police(skb, n->police);`
135			`if (pol_res >= 0)`
136			`return pol_res;`
137			`} else`
138			`#endif`
139			`return 0;`
140			`}`
141			`n = n->next;`
142			`goto next_knode;`
143			`}`
144
145			`/* PUSH */`
146			`if (sdepth >= TC_U32_MAXDEPTH)`
147			`goto deadloop;`
148			`stack[sdepth].knode = n;`
149			`stack[sdepth].ptr = ptr;`
150			`sdepth++;`
151
152			`ht = n->ht_down;`
153			`sel = 0;`
154			`if (ht->divisor)`
155			`sel = ht->divisor&u32_hash_fold((u32)(ptr+n->sel.hoff), &n->sel);`
156
157			`if (!(n->sel.flags&(TC_U32_VAROFFSET\|TC_U32_OFFSET\|TC_U32_EAT)))`
158			`goto next_ht;`
159
160			`if (n->sel.flags&(TC_U32_OFFSET\|TC_U32_VAROFFSET)) {`
161			`off2 = n->sel.off + 3;`
162			`if (n->sel.flags&TC_U32_VAROFFSET)`
163			`off2 += ntohs(n->sel.offmask & (u16)(ptr+n->sel.offoff)) >>n->sel.offshift;`
164			`off2 &= ~3;`
165			`}`
166			`if (n->sel.flags&TC_U32_EAT) {`
167			`ptr += off2;`
168			`off2 = 0;`
169			`}`
170
171			`if (ptr < skb->tail)`
172			`goto next_ht;`
173			`}`
174
175			`/* POP */`
176			`if (sdepth--) {`
177			`n = stack[sdepth].knode;`
178			`ht = n->ht_up;`
179			`ptr = stack[sdepth].ptr;`
180			`goto check_terminal;`
181			`}`
182			`return -1;`
183
184			`deadloop:`
185			`if (net_ratelimit())`
186			`printk("cls_u32: dead loop\n");`
187			`return -1;`
188			`}`
189
190			`static __inline__ struct tc_u_hnode *`
191			`u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)`
192			`{`
193			`struct tc_u_hnode *ht;`
194
195			`for (ht = tp_c->hlist; ht; ht = ht->next)`
196			`if (ht->handle == handle)`
197			`break;`
198
199			`return ht;`
200			`}`
201
202			`static __inline__ struct tc_u_knode *`
203			`u32_lookup_key(struct tc_u_hnode *ht, u32 handle)`
204			`{`
205			`unsigned sel;`
206			`struct tc_u_knode *n;`
207
208			`sel = TC_U32_HASH(handle);`
209			`if (sel > ht->divisor)`
210			`return 0;`
211
212			`for (n = ht->ht[sel]; n; n = n->next)`
213			`if (n->handle == handle)`
214			`return n;`
215
216			`return NULL;`
217			`}`
218
219
220			`static unsigned long u32_get(struct tcf_proto *tp, u32 handle)`
221			`{`
222			`struct tc_u_hnode *ht;`
223			`struct tc_u_common *tp_c = tp->data;`
224
225			`if (TC_U32_HTID(handle) == TC_U32_ROOT)`
226			`ht = tp->root;`
227			`else`
228			`ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle));`
229
230			`if (!ht)`
231			`return 0;`
232
233			`if (TC_U32_KEY(handle) == 0)`
234			`return (unsigned long)ht;`
235
236			`return (unsigned long)u32_lookup_key(ht, handle);`
237			`}`
238
239			`static void u32_put(struct tcf_proto *tp, unsigned long f)`
240			`{`
241			`}`
242
243			`static u32 gen_new_htid(struct tc_u_common *tp_c)`
244			`{`
245			`int i = 0x800;`
246
247			`do {`
248			`if (++tp_c->hgenerator == 0x7FF)`
249			`tp_c->hgenerator = 1;`
250			`} while (--i>0 && u32_lookup_ht(tp_c, (tp_c->hgenerator\|0x800)<<20));`
251
252			`return i > 0 ? (tp_c->hgenerator\|0x800)<<20 : 0;`
253			`}`
254
255			`static int u32_init(struct tcf_proto *tp)`
256			`{`
257			`struct tc_u_hnode *root_ht;`
258			`struct tc_u_common *tp_c;`
259
260			`MOD_INC_USE_COUNT;`
261
262			`for (tp_c = u32_list; tp_c; tp_c = tp_c->next)`
263			`if (tp_c->q == tp->q)`
264			`break;`
265
266			`root_ht = kmalloc(sizeof(*root_ht), GFP_KERNEL);`
267			`if (root_ht == NULL) {`
268			`MOD_DEC_USE_COUNT;`
269			`return -ENOBUFS;`
270			`}`
271			`memset(root_ht, 0, sizeof(*root_ht));`
272			`root_ht->divisor = 0;`
273			`root_ht->refcnt++;`
274			`root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;`
275
276			`if (tp_c == NULL) {`
277			`tp_c = kmalloc(sizeof(*tp_c), GFP_KERNEL);`
278			`if (tp_c == NULL) {`
279			`kfree(root_ht);`
280			`MOD_DEC_USE_COUNT;`
281			`return -ENOBUFS;`
282			`}`
283			`memset(tp_c, 0, sizeof(*tp_c));`
284			`tp_c->q = tp->q;`
285			`tp_c->next = u32_list;`
286			`u32_list = tp_c;`
287			`}`
288
289			`tp_c->refcnt++;`
290			`root_ht->next = tp_c->hlist;`
291			`tp_c->hlist = root_ht;`
292			`root_ht->tp_c = tp_c;`
293
294			`tp->root = root_ht;`
295			`tp->data = tp_c;`
296			`return 0;`
297			`}`
298
299			`static int u32_destroy_key(struct tcf_proto tp, struct tc_u_knode n)`
300			`{`
301			`unsigned long cl;`
302
303			`if ((cl = __cls_set_class(&n->res.class, 0)) != 0)`
304			`tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);`
305			`#ifdef CONFIG_NET_CLS_POLICE`
306			`tcf_police_release(n->police);`
307			`#endif`
308			`if (n->ht_down)`
309			`n->ht_down->refcnt--;`
310			`kfree(n);`
311			`return 0;`
312			`}`
313
314			`static int u32_delete_key(struct tcf_proto tp, struct tc_u_knode key)`
315			`{`
316			`struct tc_u_knode **kp;`
317			`struct tc_u_hnode *ht = key->ht_up;`
318
319			`if (ht) {`
320			`for (kp = &ht->ht[TC_U32_HASH(key->handle)]; kp; kp = &(kp)->next) {`
321			`if (*kp == key) {`
322			`tcf_tree_lock(tp);`
323			`*kp = key->next;`
324			`tcf_tree_unlock(tp);`
325
326			`u32_destroy_key(tp, key);`
327			`return 0;`
328			`}`
329			`}`
330			`}`
331			`BUG_TRAP(0);`
332			`return 0;`
333			`}`
334
335			`static void u32_clear_hnode(struct tcf_proto tp, struct tc_u_hnode ht)`
336			`{`
337			`struct tc_u_knode *n;`
338			`unsigned h;`
339
340			`for (h=0; h<=ht->divisor; h++) {`
341			`while ((n = ht->ht[h]) != NULL) {`
342			`ht->ht[h] = n->next;`
343
344			`u32_destroy_key(tp, n);`
345			`}`
346			`}`
347			`}`
348
349			`static int u32_destroy_hnode(struct tcf_proto tp, struct tc_u_hnode ht)`
350			`{`
351			`struct tc_u_common *tp_c = tp->data;`
352			`struct tc_u_hnode **hn;`
353
354			`BUG_TRAP(!ht->refcnt);`
355
356			`u32_clear_hnode(tp, ht);`
357
358			`for (hn = &tp_c->hlist; hn; hn = &(hn)->next) {`
359			`if (*hn == ht) {`
360			`*hn = ht->next;`
361			`kfree(ht);`
362			`return 0;`
363			`}`
364			`}`
365
366			`BUG_TRAP(0);`
367			`return -ENOENT;`
368			`}`
369
370			`static void u32_destroy(struct tcf_proto *tp)`
371			`{`
372			`struct tc_u_common *tp_c = tp->data;`
373			`struct tc_u_hnode *root_ht = xchg(&tp->root, NULL);`
374
375			`BUG_TRAP(root_ht != NULL);`
376
377			`if (root_ht && --root_ht->refcnt == 0)`
378			`u32_destroy_hnode(tp, root_ht);`
379
380			`if (--tp_c->refcnt == 0) {`
381			`struct tc_u_hnode *ht;`
382			`struct tc_u_common **tp_cp;`
383
384			`for (tp_cp = &u32_list; tp_cp; tp_cp = &(tp_cp)->next) {`
385			`if (*tp_cp == tp_c) {`
386			`*tp_cp = tp_c->next;`
387			`break;`
388			`}`
389			`}`
390
391			`for (ht=tp_c->hlist; ht; ht = ht->next)`
392			`u32_clear_hnode(tp, ht);`
393
394			`while ((ht = tp_c->hlist) != NULL) {`
395			`tp_c->hlist = ht->next;`
396
397			`BUG_TRAP(ht->refcnt == 0);`
398
399			`kfree(ht);`
400			`};`
401
402			`kfree(tp_c);`
403			`}`
404
405			`MOD_DEC_USE_COUNT;`
406			`tp->data = NULL;`
407			`}`
408
409			`static int u32_delete(struct tcf_proto *tp, unsigned long arg)`
410			`{`
411			`struct tc_u_hnode ht = (struct tc_u_hnode)arg;`
412
413			`if (ht == NULL)`
414			`return 0;`
415
416			`if (TC_U32_KEY(ht->handle))`
417			`return u32_delete_key(tp, (struct tc_u_knode*)ht);`
418
419			`if (tp->root == ht)`
420			`return -EINVAL;`
421
422			`if (--ht->refcnt == 0)`
423			`u32_destroy_hnode(tp, ht);`
424
425			`return 0;`
426			`}`
427
428			`static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)`
429			`{`
430			`struct tc_u_knode *n;`
431			`unsigned i = 0x7FF;`
432
433			`for (n=ht->ht[TC_U32_HASH(handle)]; n; n = n->next)`
434			`if (i < TC_U32_NODE(n->handle))`
435			`i = TC_U32_NODE(n->handle);`
436			`i++;`
437
438			`return handle\|(i>0xFFF ? 0xFFF : i);`
439			`}`
440
441			`static int u32_set_parms(struct Qdisc *q, unsigned long base,`
442			`struct tc_u_hnode *ht,`
443			`struct tc_u_knode n, struct rtattr *tb,`
444			`struct rtattr *est)`
445			`{`
446			`if (tb[TCA_U32_LINK-1]) {`
447			`u32 handle = (u32)RTA_DATA(tb[TCA_U32_LINK-1]);`
448			`struct tc_u_hnode *ht_down = NULL;`
449
450			`if (TC_U32_KEY(handle))`
451			`return -EINVAL;`
452
453			`if (handle) {`
454			`ht_down = u32_lookup_ht(ht->tp_c, handle);`
455
456			`if (ht_down == NULL)`
457			`return -EINVAL;`
458			`ht_down->refcnt++;`
459			`}`
460
461			`sch_tree_lock(q);`
462			`ht_down = xchg(&n->ht_down, ht_down);`
463			`sch_tree_unlock(q);`
464
465			`if (ht_down)`
466			`ht_down->refcnt--;`
467			`}`
468			`if (tb[TCA_U32_CLASSID-1]) {`
469			`unsigned long cl;`
470
471			`n->res.classid = (u32)RTA_DATA(tb[TCA_U32_CLASSID-1]);`
472			`sch_tree_lock(q);`
473			`cl = __cls_set_class(&n->res.class, q->ops->cl_ops->bind_tcf(q, base, n->res.classid));`
474			`sch_tree_unlock(q);`
475			`if (cl)`
476			`q->ops->cl_ops->unbind_tcf(q, cl);`
477			`}`
478			`#ifdef CONFIG_NET_CLS_POLICE`
479			`if (tb[TCA_U32_POLICE-1]) {`
480			`struct tcf_police *police = tcf_police_locate(tb[TCA_U32_POLICE-1], est);`
481
482			`sch_tree_lock(q);`
483			`police = xchg(&n->police, police);`
484			`sch_tree_unlock(q);`
485
486			`tcf_police_release(police);`
487			`}`
488			`#endif`
489			`return 0;`
490			`}`
491
492			`static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,`
493			`struct rtattr **tca,`
494			`unsigned long *arg)`
495			`{`
496			`struct tc_u_common *tp_c = tp->data;`
497			`struct tc_u_hnode *ht;`
498			`struct tc_u_knode *n;`
499			`struct tc_u32_sel *s;`
500			`struct rtattr *opt = tca[TCA_OPTIONS-1];`
501			`struct rtattr *tb[TCA_U32_MAX];`
502			`u32 htid;`
503			`int err;`
504
505			`if (opt == NULL)`
506			`return handle ? -EINVAL : 0;`
507
508			`if (rtattr_parse(tb, TCA_U32_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)`
509			`return -EINVAL;`
510
511			`if ((n = (struct tc_u_knode)arg) != NULL) {`
512			`if (TC_U32_KEY(n->handle) == 0)`
513			`return -EINVAL;`
514
515			`return u32_set_parms(tp->q, base, n->ht_up, n, tb, tca[TCA_RATE-1]);`
516			`}`
517
518			`if (tb[TCA_U32_DIVISOR-1]) {`
519			`unsigned divisor = (unsigned)RTA_DATA(tb[TCA_U32_DIVISOR-1]);`
520
521			`if (--divisor > 0x100)`
522			`return -EINVAL;`
523			`if (TC_U32_KEY(handle))`
524			`return -EINVAL;`
525			`if (handle == 0) {`
526			`handle = gen_new_htid(tp->data);`
527			`if (handle == 0)`
528			`return -ENOMEM;`
529			`}`
530			`ht = kmalloc(sizeof(ht) + divisorsizeof(void*), GFP_KERNEL);`
531			`if (ht == NULL)`
532			`return -ENOBUFS;`
533			`memset(ht, 0, sizeof(ht) + divisorsizeof(void*));`
534			`ht->tp_c = tp_c;`
535			`ht->refcnt = 0;`
536			`ht->divisor = divisor;`
537			`ht->handle = handle;`
538			`ht->next = tp_c->hlist;`
539			`tp_c->hlist = ht;`
540			`*arg = (unsigned long)ht;`
541			`return 0;`
542			`}`
543
544			`if (tb[TCA_U32_HASH-1]) {`
545			`htid = (unsigned)RTA_DATA(tb[TCA_U32_HASH-1]);`
546			`if (TC_U32_HTID(htid) == TC_U32_ROOT) {`
547			`ht = tp->root;`
548			`htid = ht->handle;`
549			`} else {`
550			`ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));`
551			`if (ht == NULL)`
552			`return -EINVAL;`
553			`}`
554			`} else {`
555			`ht = tp->root;`
556			`htid = ht->handle;`
557			`}`
558
559			`if (ht->divisor < TC_U32_HASH(htid))`
560			`return -EINVAL;`
561
562			`if (handle) {`
563			`if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))`
564			`return -EINVAL;`
565			`handle = htid \| TC_U32_NODE(handle);`
566			`} else`
567			`handle = gen_new_kid(ht, htid);`
568
569			`if (tb[TCA_U32_SEL-1] == 0 \|\|`
570			`RTA_PAYLOAD(tb[TCA_U32_SEL-1]) < sizeof(struct tc_u32_sel))`
571			`return -EINVAL;`
572
573			`s = RTA_DATA(tb[TCA_U32_SEL-1]);`
574			`n = kmalloc(sizeof(n) + s->nkeyssizeof(struct tc_u32_key), GFP_KERNEL);`
575			`if (n == NULL)`
576			`return -ENOBUFS;`
577			`memset(n, 0, sizeof(n) + s->nkeyssizeof(struct tc_u32_key));`
578			`memcpy(&n->sel, s, sizeof(s) + s->nkeyssizeof(struct tc_u32_key));`
579			`n->ht_up = ht;`
580			`n->handle = handle;`
581			`err = u32_set_parms(tp->q, base, ht, n, tb, tca[TCA_RATE-1]);`
582			`if (err == 0) {`
583			`struct tc_u_knode **ins;`
584			`for (ins = &ht->ht[TC_U32_HASH(handle)]; ins; ins = &(ins)->next)`
585			`if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle))`
586			`break;`
587
588			`n->next = *ins;`
589			`wmb();`
590			`*ins = n;`
591
592			`*arg = (unsigned long)n;`
593			`return 0;`
594			`}`
595			`kfree(n);`
596			`return err;`
597			`}`
598
599			`static void u32_walk(struct tcf_proto tp, struct tcf_walker arg)`
600			`{`
601			`struct tc_u_common *tp_c = tp->data;`
602			`struct tc_u_hnode *ht;`
603			`struct tc_u_knode *n;`
604			`unsigned h;`
605
606			`if (arg->stop)`
607			`return;`
608
609			`for (ht = tp_c->hlist; ht; ht = ht->next) {`
610			`if (arg->count >= arg->skip) {`
611			`if (arg->fn(tp, (unsigned long)ht, arg) < 0) {`
612			`arg->stop = 1;`
613			`return;`
614			`}`
615			`}`
616			`arg->count++;`
617			`for (h = 0; h <= ht->divisor; h++) {`
618			`for (n = ht->ht[h]; n; n = n->next) {`
619			`if (arg->count < arg->skip) {`
620			`arg->count++;`
621			`continue;`
622			`}`
623			`if (arg->fn(tp, (unsigned long)n, arg) < 0) {`
624			`arg->stop = 1;`
625			`return;`
626			`}`
627			`arg->count++;`
628			`}`
629			`}`
630			`}`
631			`}`
632
633			`static int u32_dump(struct tcf_proto *tp, unsigned long fh,`
634			`struct sk_buff skb, struct tcmsg t)`
635			`{`
636			`struct tc_u_knode n = (struct tc_u_knode)fh;`
637			`unsigned char *b = skb->tail;`
638			`struct rtattr *rta;`
639
640			`if (n == NULL)`
641			`return skb->len;`
642
643			`t->tcm_handle = n->handle;`
644
645			`rta = (struct rtattr*)b;`
646			`RTA_PUT(skb, TCA_OPTIONS, 0, NULL);`
647
648			`if (TC_U32_KEY(n->handle) == 0) {`
649			`struct tc_u_hnode ht = (struct tc_u_hnode)fh;`
650			`u32 divisor = ht->divisor+1;`
651			`RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);`
652			`} else {`
653			`RTA_PUT(skb, TCA_U32_SEL,`
654			`sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),`
655			`&n->sel);`
656			`if (n->ht_up) {`
657			`u32 htid = n->handle & 0xFFFFF000;`
658			`RTA_PUT(skb, TCA_U32_HASH, 4, &htid);`
659			`}`
660			`if (n->res.classid)`
661			`RTA_PUT(skb, TCA_U32_CLASSID, 4, &n->res.classid);`
662			`if (n->ht_down)`
663			`RTA_PUT(skb, TCA_U32_LINK, 4, &n->ht_down->handle);`
664			`#ifdef CONFIG_NET_CLS_POLICE`
665			`if (n->police) {`
666			`struct rtattr * p_rta = (struct rtattr*)skb->tail;`
667
668			`RTA_PUT(skb, TCA_U32_POLICE, 0, NULL);`
669
670			`if (tcf_police_dump(skb, n->police) < 0)`
671			`goto rtattr_failure;`
672
673			`p_rta->rta_len = skb->tail - (u8*)p_rta;`
674			`}`
675			`#endif`
676			`}`
677
678			`rta->rta_len = skb->tail - b;`
679			`#ifdef CONFIG_NET_CLS_POLICE`
680			`if (TC_U32_KEY(n->handle) && n->police) {`
681			`if (qdisc_copy_stats(skb, &n->police->stats))`
682			`goto rtattr_failure;`
683			`}`
684			`#endif`
685			`return skb->len;`
686
687			`rtattr_failure:`
688			`skb_trim(skb, b - skb->data);`
689			`return -1;`
690			`}`
691
692			`struct tcf_proto_ops cls_u32_ops = {`
693			`NULL,`
694			`"u32",`
695			`u32_classify,`
696			`u32_init,`
697			`u32_destroy,`
698
699			`u32_get,`
700			`u32_put,`
701			`u32_change,`
702			`u32_delete,`
703			`u32_walk,`
704			`u32_dump`
705			`};`
706
707			`#ifdef MODULE`
708			`int init_module(void)`
709			`{`
710			`return register_tcf_proto_ops(&cls_u32_ops);`
711			`}`
712
713			`void cleanup_module(void)`
714			`{`
715			`unregister_tcf_proto_ops(&cls_u32_ops);`
716			`}`
717			`#endif`
718			`MODULE_LICENSE("GPL");`