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

Subversion Repositories or1k

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

Details | Compare with Previous | View Log


/*
 * net/sched/cls_route.c        ROUTE4 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>
 */
 
#include <linux/module.h>
#include <linux/config.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>
 
/*
   1. For now we assume that route tags < 256.
      It allows to use direct table lookups, instead of hash tables.
   2. For now we assume that "from TAG" and "fromdev DEV" statements
      are mutually  exclusive.
   3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
 */
 
struct route4_fastmap
{
        struct route4_filter    *filter;
        u32                     id;
        int                     iif;
};
 
struct route4_head
{
        struct route4_fastmap   fastmap[16];
        struct route4_bucket    *table[256+1];
};
 
struct route4_bucket
{
        struct route4_filter    *ht[16+16+1];
};
 
struct route4_filter
{
        struct route4_filter    *next;
        u32                     id;
        int                     iif;
 
        struct tcf_result       res;
#ifdef CONFIG_NET_CLS_POLICE
        struct tcf_police       *police;
#endif
 
        u32                     handle;
        struct route4_bucket    *bkt;
};
 
#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
 
static __inline__ int route4_fastmap_hash(u32 id, int iif)
{
        return id&0xF;
}
 
static void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id)
{
        spin_lock_bh(&dev->queue_lock);
        memset(head->fastmap, 0, sizeof(head->fastmap));
        spin_unlock_bh(&dev->queue_lock);
}
 
static void __inline__
route4_set_fastmap(struct route4_head *head, u32 id, int iif,
                   struct route4_filter *f)
{
        int h = route4_fastmap_hash(id, iif);
        head->fastmap[h].id = id;
        head->fastmap[h].iif = iif;
        head->fastmap[h].filter = f;
}
 
static __inline__ int route4_hash_to(u32 id)
{
        return id&0xFF;
}
 
static __inline__ int route4_hash_from(u32 id)
{
        return (id>>16)&0xF;
}
 
static __inline__ int route4_hash_iif(int iif)
{
        return 16 + ((iif>>16)&0xF);
}
 
static __inline__ int route4_hash_wild(void)
{
        return 32;
}
 
#ifdef CONFIG_NET_CLS_POLICE
#define IF_ROUTE_POLICE \
if (f->police) { \
        int pol_res = tcf_police(skb, f->police); \
        if (pol_res >= 0) return pol_res; \
        dont_cache = 1; \
        continue; \
} \
if (!dont_cache)
#else
#define IF_ROUTE_POLICE
#endif
 
 
static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
                           struct tcf_result *res)
{
        struct route4_head *head = (struct route4_head*)tp->root;
        struct dst_entry *dst;
        struct route4_bucket *b;
        struct route4_filter *f;
#ifdef CONFIG_NET_CLS_POLICE
        int dont_cache = 0;
#endif
        u32 id, h;
        int iif;
 
        if ((dst = skb->dst) == NULL)
                goto failure;
 
        id = dst->tclassid;
        if (head == NULL)
                goto old_method;
 
        iif = ((struct rtable*)dst)->key.iif;
 
        h = route4_fastmap_hash(id, iif);
        if (id == head->fastmap[h].id &&
            iif == head->fastmap[h].iif &&
            (f = head->fastmap[h].filter) != NULL) {
                if (f == ROUTE4_FAILURE)
                        goto failure;
 
                *res = f->res;
                return 0;
        }
 
        h = route4_hash_to(id);
 
restart:
        if ((b = head->table[h]) != NULL) {
                f = b->ht[route4_hash_from(id)];
 
                for ( ; f; f = f->next) {
                        if (f->id == id) {
                                *res = f->res;
                                IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
                                return 0;
                        }
                }
 
                for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next) {
                        if (f->iif == iif) {
                                *res = f->res;
                                IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
                                return 0;
                        }
                }
 
                for (f = b->ht[route4_hash_wild()]; f; f = f->next) {
                        *res = f->res;
                        IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
                        return 0;
                }
 
        }
        if (h < 256) {
                h = 256;
                id &= ~0xFFFF;
                goto restart;
        }
 
#ifdef CONFIG_NET_CLS_POLICE
        if (!dont_cache)
#endif
                route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
failure:
        return -1;
 
old_method:
        if (id && (TC_H_MAJ(id) == 0 ||
                   !(TC_H_MAJ(id^tp->q->handle)))) {
                res->classid = id;
                res->class = 0;
                return 0;
        }
        return -1;
}
 
static u32 to_hash(u32 id)
{
        u32 h = id&0xFF;
        if (id&0x8000)
                h += 256;
        return h;
}
 
static u32 from_hash(u32 id)
{
        id &= 0xFFFF;
        if (id == 0xFFFF)
                return 32;
        if (!(id & 0x8000)) {
                if (id > 255)
                        return 256;
                return id&0xF;
        }
        return 16 + (id&0xF);
}
 
static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
{
        struct route4_head *head = (struct route4_head*)tp->root;
        struct route4_bucket *b;
        struct route4_filter *f;
        unsigned h1, h2;
 
        if (!head)
                return 0;
 
        h1 = to_hash(handle);
        if (h1 > 256)
                return 0;
 
        h2 = from_hash(handle>>16);
        if (h2 > 32)
                return 0;
 
        if ((b = head->table[h1]) != NULL) {
                for (f = b->ht[h2]; f; f = f->next)
                        if (f->handle == handle)
                                return (unsigned long)f;
        }
        return 0;
}
 
static void route4_put(struct tcf_proto *tp, unsigned long f)
{
}
 
static int route4_init(struct tcf_proto *tp)
{
        MOD_INC_USE_COUNT;
        return 0;
}
 
static void route4_destroy(struct tcf_proto *tp)
{
        struct route4_head *head = xchg(&tp->root, NULL);
        int h1, h2;
 
        if (head == NULL) {
                MOD_DEC_USE_COUNT;
                return;
        }
 
        for (h1=0; h1<=256; h1++) {
                struct route4_bucket *b;
 
                if ((b = head->table[h1]) != NULL) {
                        for (h2=0; h2<=32; h2++) {
                                struct route4_filter *f;
 
                                while ((f = b->ht[h2]) != NULL) {
                                        unsigned long cl;
 
                                        b->ht[h2] = f->next;
                                        if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
                                                tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
#ifdef CONFIG_NET_CLS_POLICE
                                        tcf_police_release(f->police);
#endif
                                        kfree(f);
                                }
                        }
                        kfree(b);
                }
        }
        kfree(head);
        MOD_DEC_USE_COUNT;
}
 
static int route4_delete(struct tcf_proto *tp, unsigned long arg)
{
        struct route4_head *head = (struct route4_head*)tp->root;
        struct route4_filter **fp, *f = (struct route4_filter*)arg;
        unsigned h = 0;
        struct route4_bucket *b;
        int i;
 
        if (!head || !f)
                return -EINVAL;
 
        h = f->handle;
        b = f->bkt;
 
        for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
                if (*fp == f) {
                        unsigned long cl;
 
                        tcf_tree_lock(tp);
                        *fp = f->next;
                        tcf_tree_unlock(tp);
 
                        route4_reset_fastmap(tp->q->dev, head, f->id);
 
                        if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
                                tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
 
#ifdef CONFIG_NET_CLS_POLICE
                        tcf_police_release(f->police);
#endif
                        kfree(f);
 
                        /* Strip tree */
 
                        for (i=0; i<=32; i++)
                                if (b->ht[i])
                                        return 0;
 
                        /* OK, session has no flows */
                        tcf_tree_lock(tp);
                        head->table[to_hash(h)] = NULL;
                        tcf_tree_unlock(tp);
 
                        kfree(b);
                        return 0;
                }
        }
        return 0;
}
 
static int route4_change(struct tcf_proto *tp, unsigned long base,
                       u32 handle,
                       struct rtattr **tca,
                       unsigned long *arg)
{
        struct route4_head *head = tp->root;
        struct route4_filter *f, *f1, **ins_f;
        struct route4_bucket *b;
        struct rtattr *opt = tca[TCA_OPTIONS-1];
        struct rtattr *tb[TCA_ROUTE4_MAX];
        unsigned h1, h2;
        int err;
 
        if (opt == NULL)
                return handle ? -EINVAL : 0;
 
        if (rtattr_parse(tb, TCA_ROUTE4_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
                return -EINVAL;
 
        if ((f = (struct route4_filter*)*arg) != NULL) {
                /* Node exists: adjust only classid */
 
                if (f->handle != handle && handle)
                        return -EINVAL;
                if (tb[TCA_ROUTE4_CLASSID-1]) {
                        unsigned long cl;
 
                        f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
                        cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
                        if (cl)
                                tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
                }
#ifdef CONFIG_NET_CLS_POLICE
                if (tb[TCA_ROUTE4_POLICE-1]) {
                        struct tcf_police *police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
 
                        tcf_tree_lock(tp);
                        police = xchg(&f->police, police);
                        tcf_tree_unlock(tp);
 
                        tcf_police_release(police);
                }
#endif
                return 0;
        }
 
        /* Now more serious part... */
 
        if (head == NULL) {
                head = kmalloc(sizeof(struct route4_head), GFP_KERNEL);
                if (head == NULL)
                        return -ENOBUFS;
                memset(head, 0, sizeof(struct route4_head));
 
                tcf_tree_lock(tp);
                tp->root = head;
                tcf_tree_unlock(tp);
        }
 
        f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);
        if (f == NULL)
                return -ENOBUFS;
 
        memset(f, 0, sizeof(*f));
 
        err = -EINVAL;
        f->handle = 0x8000;
        if (tb[TCA_ROUTE4_TO-1]) {
                if (handle&0x8000)
                        goto errout;
                if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < 4)
                        goto errout;
                f->id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
                if (f->id > 0xFF)
                        goto errout;
                f->handle = f->id;
        }
        if (tb[TCA_ROUTE4_FROM-1]) {
                u32 sid;
                if (tb[TCA_ROUTE4_IIF-1])
                        goto errout;
                if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < 4)
                        goto errout;
                sid = (*(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]));
                if (sid > 0xFF)
                        goto errout;
                f->handle |= sid<<16;
                f->id |= sid<<16;
        } else if (tb[TCA_ROUTE4_IIF-1]) {
                if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < 4)
                        goto errout;
                f->iif = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
                if (f->iif > 0x7FFF)
                        goto errout;
                f->handle |= (f->iif|0x8000)<<16;
        } else
                f->handle |= 0xFFFF<<16;
 
        if (handle) {
                f->handle |= handle&0x7F00;
                if (f->handle != handle)
                        goto errout;
        }
 
        if (tb[TCA_ROUTE4_CLASSID-1]) {
                if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < 4)
                        goto errout;
                f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
        }
 
        h1 = to_hash(f->handle);
        if ((b = head->table[h1]) == NULL) {
                err = -ENOBUFS;
                b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL);
                if (b == NULL)
                        goto errout;
                memset(b, 0, sizeof(*b));
 
                tcf_tree_lock(tp);
                head->table[h1] = b;
                tcf_tree_unlock(tp);
        }
        f->bkt = b;
 
        err = -EEXIST;
        h2 = from_hash(f->handle>>16);
        for (ins_f = &b->ht[h2]; (f1=*ins_f) != NULL; ins_f = &f1->next) {
                if (f->handle < f1->handle)
                        break;
                if (f1->handle == f->handle)
                        goto errout;
        }
 
        cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
#ifdef CONFIG_NET_CLS_POLICE
        if (tb[TCA_ROUTE4_POLICE-1])
                f->police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
#endif
 
        f->next = f1;
        tcf_tree_lock(tp);
        *ins_f = f;
        tcf_tree_unlock(tp);
 
        route4_reset_fastmap(tp->q->dev, head, f->id);
        *arg = (unsigned long)f;
        return 0;
 
errout:
        if (f)
                kfree(f);
        return err;
}
 
static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
        struct route4_head *head = tp->root;
        unsigned h, h1;
 
        if (head == NULL)
                arg->stop = 1;
 
        if (arg->stop)
                return;
 
        for (h = 0; h <= 256; h++) {
                struct route4_bucket *b = head->table[h];
 
                if (b) {
                        for (h1 = 0; h1 <= 32; h1++) {
                                struct route4_filter *f;
 
                                for (f = b->ht[h1]; f; f = f->next) {
                                        if (arg->count < arg->skip) {
                                                arg->count++;
                                                continue;
                                        }
                                        if (arg->fn(tp, (unsigned long)f, arg) < 0) {
                                                arg->stop = 1;
                                                break;
                                        }
                                        arg->count++;
                                }
                        }
                }
        }
}
 
static int route4_dump(struct tcf_proto *tp, unsigned long fh,
                       struct sk_buff *skb, struct tcmsg *t)
{
        struct route4_filter *f = (struct route4_filter*)fh;
        unsigned char    *b = skb->tail;
        struct rtattr *rta;
        u32 id;
 
        if (f == NULL)
                return skb->len;
 
        t->tcm_handle = f->handle;
 
        rta = (struct rtattr*)b;
        RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 
        if (!(f->handle&0x8000)) {
                id = f->id&0xFF;
                RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
        }
        if (f->handle&0x80000000) {
                if ((f->handle>>16) != 0xFFFF)
                        RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
        } else {
                id = f->id>>16;
                RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
        }
        if (f->res.classid)
                RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
#ifdef CONFIG_NET_CLS_POLICE
        if (f->police) {
                struct rtattr * p_rta = (struct rtattr*)skb->tail;
 
                RTA_PUT(skb, TCA_ROUTE4_POLICE, 0, NULL);
 
                if (tcf_police_dump(skb, f->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 (f->police) {
                if (qdisc_copy_stats(skb, &f->police->stats))
                        goto rtattr_failure;
        }
#endif
        return skb->len;
 
rtattr_failure:
        skb_trim(skb, b - skb->data);
        return -1;
}
 
struct tcf_proto_ops cls_route4_ops = {
        NULL,
        "route",
        route4_classify,
        route4_init,
        route4_destroy,
 
        route4_get,
        route4_put,
        route4_change,
        route4_delete,
        route4_walk,
        route4_dump
};
 
#ifdef MODULE
int init_module(void)
{
        return register_tcf_proto_ops(&cls_route4_ops);
}
 
void cleanup_module(void)
{
        unregister_tcf_proto_ops(&cls_route4_ops);
}
#endif
MODULE_LICENSE("GPL");

Browse

Tools

Subversion Repositories or1k

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

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
2			`* net/sched/cls_route.c ROUTE4 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
12			`#include <linux/module.h>`
13			`#include <linux/config.h>`
14			`#include <asm/uaccess.h>`
15			`#include <asm/system.h>`
16			`#include <asm/bitops.h>`
17			`#include <linux/types.h>`
18			`#include <linux/kernel.h>`
19			`#include <linux/sched.h>`
20			`#include <linux/string.h>`
21			`#include <linux/mm.h>`
22			`#include <linux/socket.h>`
23			`#include <linux/sockios.h>`
24			`#include <linux/in.h>`
25			`#include <linux/errno.h>`
26			`#include <linux/interrupt.h>`
27			`#include <linux/if_ether.h>`
28			`#include <linux/inet.h>`
29			`#include <linux/netdevice.h>`
30			`#include <linux/etherdevice.h>`
31			`#include <linux/notifier.h>`
32			`#include <net/ip.h>`
33			`#include <net/route.h>`
34			`#include <linux/skbuff.h>`
35			`#include <net/sock.h>`
36			`#include <net/pkt_sched.h>`
37
38			`/*`
39			`1. For now we assume that route tags < 256.`
40			`It allows to use direct table lookups, instead of hash tables.`
41			`2. For now we assume that "from TAG" and "fromdev DEV" statements`
42			`are mutually exclusive.`
43			`3. "to TAG from ANY" has higher priority, than "to ANY from XXX"`
44			`*/`
45
46			`struct route4_fastmap`
47			`{`
48			`struct route4_filter *filter;`
49			`u32 id;`
50			`int iif;`
51			`};`
52
53			`struct route4_head`
54			`{`
55			`struct route4_fastmap fastmap[16];`
56			`struct route4_bucket *table[256+1];`
57			`};`
58
59			`struct route4_bucket`
60			`{`
61			`struct route4_filter *ht[16+16+1];`
62			`};`
63
64			`struct route4_filter`
65			`{`
66			`struct route4_filter *next;`
67			`u32 id;`
68			`int iif;`
69
70			`struct tcf_result res;`
71			`#ifdef CONFIG_NET_CLS_POLICE`
72			`struct tcf_police *police;`
73			`#endif`
74
75			`u32 handle;`
76			`struct route4_bucket *bkt;`
77			`};`
78
79			`#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))`
80
81			`static __inline__ int route4_fastmap_hash(u32 id, int iif)`
82			`{`
83			`return id&0xF;`
84			`}`
85
86			`static void route4_reset_fastmap(struct net_device dev, struct route4_head head, u32 id)`
87			`{`
88			`spin_lock_bh(&dev->queue_lock);`
89			`memset(head->fastmap, 0, sizeof(head->fastmap));`
90			`spin_unlock_bh(&dev->queue_lock);`
91			`}`
92
93			`static void __inline__`
94			`route4_set_fastmap(struct route4_head *head, u32 id, int iif,`
95			`struct route4_filter *f)`
96			`{`
97			`int h = route4_fastmap_hash(id, iif);`
98			`head->fastmap[h].id = id;`
99			`head->fastmap[h].iif = iif;`
100			`head->fastmap[h].filter = f;`
101			`}`
102
103			`static __inline__ int route4_hash_to(u32 id)`
104			`{`
105			`return id&0xFF;`
106			`}`
107
108			`static __inline__ int route4_hash_from(u32 id)`
109			`{`
110			`return (id>>16)&0xF;`
111			`}`
112
113			`static __inline__ int route4_hash_iif(int iif)`
114			`{`
115			`return 16 + ((iif>>16)&0xF);`
116			`}`
117
118			`static __inline__ int route4_hash_wild(void)`
119			`{`
120			`return 32;`
121			`}`
122
123			`#ifdef CONFIG_NET_CLS_POLICE`
124			`#define IF_ROUTE_POLICE \`
125			`if (f->police) { \`
126			`int pol_res = tcf_police(skb, f->police); \`
127			`if (pol_res >= 0) return pol_res; \`
128			`dont_cache = 1; \`
129			`continue; \`
130			`} \`
131			`if (!dont_cache)`
132			`#else`
133			`#define IF_ROUTE_POLICE`
134			`#endif`
135
136
137			`static int route4_classify(struct sk_buff skb, struct tcf_proto tp,`
138			`struct tcf_result *res)`
139			`{`
140			`struct route4_head head = (struct route4_head)tp->root;`
141			`struct dst_entry *dst;`
142			`struct route4_bucket *b;`
143			`struct route4_filter *f;`
144			`#ifdef CONFIG_NET_CLS_POLICE`
145			`int dont_cache = 0;`
146			`#endif`
147			`u32 id, h;`
148			`int iif;`
149
150			`if ((dst = skb->dst) == NULL)`
151			`goto failure;`
152
153			`id = dst->tclassid;`
154			`if (head == NULL)`
155			`goto old_method;`
156
157			`iif = ((struct rtable*)dst)->key.iif;`
158
159			`h = route4_fastmap_hash(id, iif);`
160			`if (id == head->fastmap[h].id &&`
161			`iif == head->fastmap[h].iif &&`
162			`(f = head->fastmap[h].filter) != NULL) {`
163			`if (f == ROUTE4_FAILURE)`
164			`goto failure;`
165
166			`*res = f->res;`
167			`return 0;`
168			`}`
169
170			`h = route4_hash_to(id);`
171
172			`restart:`
173			`if ((b = head->table[h]) != NULL) {`
174			`f = b->ht[route4_hash_from(id)];`
175
176			`for ( ; f; f = f->next) {`
177			`if (f->id == id) {`
178			`*res = f->res;`
179			`IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);`
180			`return 0;`
181			`}`
182			`}`
183
184			`for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next) {`
185			`if (f->iif == iif) {`
186			`*res = f->res;`
187			`IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);`
188			`return 0;`
189			`}`
190			`}`
191
192			`for (f = b->ht[route4_hash_wild()]; f; f = f->next) {`
193			`*res = f->res;`
194			`IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);`
195			`return 0;`
196			`}`
197
198			`}`
199			`if (h < 256) {`
200			`h = 256;`
201			`id &= ~0xFFFF;`
202			`goto restart;`
203			`}`
204
205			`#ifdef CONFIG_NET_CLS_POLICE`
206			`if (!dont_cache)`
207			`#endif`
208			`route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);`
209			`failure:`
210			`return -1;`
211
212			`old_method:`
213			`if (id && (TC_H_MAJ(id) == 0 \|\|`
214			`!(TC_H_MAJ(id^tp->q->handle)))) {`
215			`res->classid = id;`
216			`res->class = 0;`
217			`return 0;`
218			`}`
219			`return -1;`
220			`}`
221
222			`static u32 to_hash(u32 id)`
223			`{`
224			`u32 h = id&0xFF;`
225			`if (id&0x8000)`
226			`h += 256;`
227			`return h;`
228			`}`
229
230			`static u32 from_hash(u32 id)`
231			`{`
232			`id &= 0xFFFF;`
233			`if (id == 0xFFFF)`
234			`return 32;`
235			`if (!(id & 0x8000)) {`
236			`if (id > 255)`
237			`return 256;`
238			`return id&0xF;`
239			`}`
240			`return 16 + (id&0xF);`
241			`}`
242
243			`static unsigned long route4_get(struct tcf_proto *tp, u32 handle)`
244			`{`
245			`struct route4_head head = (struct route4_head)tp->root;`
246			`struct route4_bucket *b;`
247			`struct route4_filter *f;`
248			`unsigned h1, h2;`
249
250			`if (!head)`
251			`return 0;`
252
253			`h1 = to_hash(handle);`
254			`if (h1 > 256)`
255			`return 0;`
256
257			`h2 = from_hash(handle>>16);`
258			`if (h2 > 32)`
259			`return 0;`
260
261			`if ((b = head->table[h1]) != NULL) {`
262			`for (f = b->ht[h2]; f; f = f->next)`
263			`if (f->handle == handle)`
264			`return (unsigned long)f;`
265			`}`
266			`return 0;`
267			`}`
268
269			`static void route4_put(struct tcf_proto *tp, unsigned long f)`
270			`{`
271			`}`
272
273			`static int route4_init(struct tcf_proto *tp)`
274			`{`
275			`MOD_INC_USE_COUNT;`
276			`return 0;`
277			`}`
278
279			`static void route4_destroy(struct tcf_proto *tp)`
280			`{`
281			`struct route4_head *head = xchg(&tp->root, NULL);`
282			`int h1, h2;`
283
284			`if (head == NULL) {`
285			`MOD_DEC_USE_COUNT;`
286			`return;`
287			`}`
288
289			`for (h1=0; h1<=256; h1++) {`
290			`struct route4_bucket *b;`
291
292			`if ((b = head->table[h1]) != NULL) {`
293			`for (h2=0; h2<=32; h2++) {`
294			`struct route4_filter *f;`
295
296			`while ((f = b->ht[h2]) != NULL) {`
297			`unsigned long cl;`
298
299			`b->ht[h2] = f->next;`
300			`if ((cl = __cls_set_class(&f->res.class, 0)) != 0)`
301			`tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);`
302			`#ifdef CONFIG_NET_CLS_POLICE`
303			`tcf_police_release(f->police);`
304			`#endif`
305			`kfree(f);`
306			`}`
307			`}`
308			`kfree(b);`
309			`}`
310			`}`
311			`kfree(head);`
312			`MOD_DEC_USE_COUNT;`
313			`}`
314
315			`static int route4_delete(struct tcf_proto *tp, unsigned long arg)`
316			`{`
317			`struct route4_head head = (struct route4_head)tp->root;`
318			`struct route4_filter *fp, f = (struct route4_filter*)arg;`
319			`unsigned h = 0;`
320			`struct route4_bucket *b;`
321			`int i;`
322
323			`if (!head \|\| !f)`
324			`return -EINVAL;`
325
326			`h = f->handle;`
327			`b = f->bkt;`
328
329			`for (fp = &b->ht[from_hash(h>>16)]; fp; fp = &(fp)->next) {`
330			`if (*fp == f) {`
331			`unsigned long cl;`
332
333			`tcf_tree_lock(tp);`
334			`*fp = f->next;`
335			`tcf_tree_unlock(tp);`
336
337			`route4_reset_fastmap(tp->q->dev, head, f->id);`
338
339			`if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)`
340			`tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);`
341
342			`#ifdef CONFIG_NET_CLS_POLICE`
343			`tcf_police_release(f->police);`
344			`#endif`
345			`kfree(f);`
346
347			`/* Strip tree */`
348
349			`for (i=0; i<=32; i++)`
350			`if (b->ht[i])`
351			`return 0;`
352
353			`/* OK, session has no flows */`
354			`tcf_tree_lock(tp);`
355			`head->table[to_hash(h)] = NULL;`
356			`tcf_tree_unlock(tp);`
357
358			`kfree(b);`
359			`return 0;`
360			`}`
361			`}`
362			`return 0;`
363			`}`
364
365			`static int route4_change(struct tcf_proto *tp, unsigned long base,`
366			`u32 handle,`
367			`struct rtattr **tca,`
368			`unsigned long *arg)`
369			`{`
370			`struct route4_head *head = tp->root;`
371			`struct route4_filter f, f1, **ins_f;`
372			`struct route4_bucket *b;`
373			`struct rtattr *opt = tca[TCA_OPTIONS-1];`
374			`struct rtattr *tb[TCA_ROUTE4_MAX];`
375			`unsigned h1, h2;`
376			`int err;`
377
378			`if (opt == NULL)`
379			`return handle ? -EINVAL : 0;`
380
381			`if (rtattr_parse(tb, TCA_ROUTE4_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)`
382			`return -EINVAL;`
383
384			`if ((f = (struct route4_filter)arg) != NULL) {`
385			`/* Node exists: adjust only classid */`
386
387			`if (f->handle != handle && handle)`
388			`return -EINVAL;`
389			`if (tb[TCA_ROUTE4_CLASSID-1]) {`
390			`unsigned long cl;`
391
392			`f->res.classid = (u32)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);`
393			`cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));`
394			`if (cl)`
395			`tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);`
396			`}`
397			`#ifdef CONFIG_NET_CLS_POLICE`
398			`if (tb[TCA_ROUTE4_POLICE-1]) {`
399			`struct tcf_police *police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);`
400
401			`tcf_tree_lock(tp);`
402			`police = xchg(&f->police, police);`
403			`tcf_tree_unlock(tp);`
404
405			`tcf_police_release(police);`
406			`}`
407			`#endif`
408			`return 0;`
409			`}`
410
411			`/* Now more serious part... */`
412
413			`if (head == NULL) {`
414			`head = kmalloc(sizeof(struct route4_head), GFP_KERNEL);`
415			`if (head == NULL)`
416			`return -ENOBUFS;`
417			`memset(head, 0, sizeof(struct route4_head));`
418
419			`tcf_tree_lock(tp);`
420			`tp->root = head;`
421			`tcf_tree_unlock(tp);`
422			`}`
423
424			`f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);`
425			`if (f == NULL)`
426			`return -ENOBUFS;`
427
428			`memset(f, 0, sizeof(*f));`
429
430			`err = -EINVAL;`
431			`f->handle = 0x8000;`
432			`if (tb[TCA_ROUTE4_TO-1]) {`
433			`if (handle&0x8000)`
434			`goto errout;`
435			`if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < 4)`
436			`goto errout;`
437			`f->id = (u32)RTA_DATA(tb[TCA_ROUTE4_TO-1]);`
438			`if (f->id > 0xFF)`
439			`goto errout;`
440			`f->handle = f->id;`
441			`}`
442			`if (tb[TCA_ROUTE4_FROM-1]) {`
443			`u32 sid;`
444			`if (tb[TCA_ROUTE4_IIF-1])`
445			`goto errout;`
446			`if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < 4)`
447			`goto errout;`
448			`sid = ((u32)RTA_DATA(tb[TCA_ROUTE4_FROM-1]));`
449			`if (sid > 0xFF)`
450			`goto errout;`
451			`f->handle \|= sid<<16;`
452			`f->id \|= sid<<16;`
453			`} else if (tb[TCA_ROUTE4_IIF-1]) {`
454			`if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < 4)`
455			`goto errout;`
456			`f->iif = (u32)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);`
457			`if (f->iif > 0x7FFF)`
458			`goto errout;`
459			`f->handle \|= (f->iif\|0x8000)<<16;`
460			`} else`
461			`f->handle \|= 0xFFFF<<16;`
462
463			`if (handle) {`
464			`f->handle \|= handle&0x7F00;`
465			`if (f->handle != handle)`
466			`goto errout;`
467			`}`
468
469			`if (tb[TCA_ROUTE4_CLASSID-1]) {`
470			`if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < 4)`
471			`goto errout;`
472			`f->res.classid = (u32)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);`
473			`}`
474
475			`h1 = to_hash(f->handle);`
476			`if ((b = head->table[h1]) == NULL) {`
477			`err = -ENOBUFS;`
478			`b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL);`
479			`if (b == NULL)`
480			`goto errout;`
481			`memset(b, 0, sizeof(*b));`
482
483			`tcf_tree_lock(tp);`
484			`head->table[h1] = b;`
485			`tcf_tree_unlock(tp);`
486			`}`
487			`f->bkt = b;`
488
489			`err = -EEXIST;`
490			`h2 = from_hash(f->handle>>16);`
491			`for (ins_f = &b->ht[h2]; (f1=*ins_f) != NULL; ins_f = &f1->next) {`
492			`if (f->handle < f1->handle)`
493			`break;`
494			`if (f1->handle == f->handle)`
495			`goto errout;`
496			`}`
497
498			`cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));`
499			`#ifdef CONFIG_NET_CLS_POLICE`
500			`if (tb[TCA_ROUTE4_POLICE-1])`
501			`f->police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);`
502			`#endif`
503
504			`f->next = f1;`
505			`tcf_tree_lock(tp);`
506			`*ins_f = f;`
507			`tcf_tree_unlock(tp);`
508
509			`route4_reset_fastmap(tp->q->dev, head, f->id);`
510			`*arg = (unsigned long)f;`
511			`return 0;`
512
513			`errout:`
514			`if (f)`
515			`kfree(f);`
516			`return err;`
517			`}`
518
519			`static void route4_walk(struct tcf_proto tp, struct tcf_walker arg)`
520			`{`
521			`struct route4_head *head = tp->root;`
522			`unsigned h, h1;`
523
524			`if (head == NULL)`
525			`arg->stop = 1;`
526
527			`if (arg->stop)`
528			`return;`
529
530			`for (h = 0; h <= 256; h++) {`
531			`struct route4_bucket *b = head->table[h];`
532
533			`if (b) {`
534			`for (h1 = 0; h1 <= 32; h1++) {`
535			`struct route4_filter *f;`
536
537			`for (f = b->ht[h1]; f; f = f->next) {`
538			`if (arg->count < arg->skip) {`
539			`arg->count++;`
540			`continue;`
541			`}`
542			`if (arg->fn(tp, (unsigned long)f, arg) < 0) {`
543			`arg->stop = 1;`
544			`break;`
545			`}`
546			`arg->count++;`
547			`}`
548			`}`
549			`}`
550			`}`
551			`}`
552
553			`static int route4_dump(struct tcf_proto *tp, unsigned long fh,`
554			`struct sk_buff skb, struct tcmsg t)`
555			`{`
556			`struct route4_filter f = (struct route4_filter)fh;`
557			`unsigned char *b = skb->tail;`
558			`struct rtattr *rta;`
559			`u32 id;`
560
561			`if (f == NULL)`
562			`return skb->len;`
563
564			`t->tcm_handle = f->handle;`
565
566			`rta = (struct rtattr*)b;`
567			`RTA_PUT(skb, TCA_OPTIONS, 0, NULL);`
568
569			`if (!(f->handle&0x8000)) {`
570			`id = f->id&0xFF;`
571			`RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);`
572			`}`
573			`if (f->handle&0x80000000) {`
574			`if ((f->handle>>16) != 0xFFFF)`
575			`RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);`
576			`} else {`
577			`id = f->id>>16;`
578			`RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);`
579			`}`
580			`if (f->res.classid)`
581			`RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);`
582			`#ifdef CONFIG_NET_CLS_POLICE`
583			`if (f->police) {`
584			`struct rtattr * p_rta = (struct rtattr*)skb->tail;`
585
586			`RTA_PUT(skb, TCA_ROUTE4_POLICE, 0, NULL);`
587
588			`if (tcf_police_dump(skb, f->police) < 0)`
589			`goto rtattr_failure;`
590
591			`p_rta->rta_len = skb->tail - (u8*)p_rta;`
592			`}`
593			`#endif`
594
595			`rta->rta_len = skb->tail - b;`
596			`#ifdef CONFIG_NET_CLS_POLICE`
597			`if (f->police) {`
598			`if (qdisc_copy_stats(skb, &f->police->stats))`
599			`goto rtattr_failure;`
600			`}`
601			`#endif`
602			`return skb->len;`
603
604			`rtattr_failure:`
605			`skb_trim(skb, b - skb->data);`
606			`return -1;`
607			`}`
608
609			`struct tcf_proto_ops cls_route4_ops = {`
610			`NULL,`
611			`"route",`
612			`route4_classify,`
613			`route4_init,`
614			`route4_destroy,`
615
616			`route4_get,`
617			`route4_put,`
618			`route4_change,`
619			`route4_delete,`
620			`route4_walk,`
621			`route4_dump`
622			`};`
623
624			`#ifdef MODULE`
625			`int init_module(void)`
626			`{`
627			`return register_tcf_proto_ops(&cls_route4_ops);`
628			`}`
629
630			`void cleanup_module(void)`
631			`{`
632			`unregister_tcf_proto_ops(&cls_route4_ops);`
633			`}`
634			`#endif`
635			`MODULE_LICENSE("GPL");`