1 /*
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 #if !defined(__i386__) && !defined(__mc68000__)
116 if ((unsigned long)ptr & 3)
117 return -1;
118 #endif
119
120 next_ht:
121 n = ht->ht[sel];
122
123 next_knode:
124 if (n) {
125 struct tc_u32_key *key = n->sel.keys;
126
127 for (i = n->sel.nkeys; i>0; i--, key++) {
128 if ((*(u32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {
129 n = n->next;
130 goto next_knode;
131 }
132 }
133 if (n->ht_down == NULL) {
134 check_terminal:
135 if (n->sel.flags&TC_U32_TERMINAL) {
136 *res = n->res;
137 #ifdef CONFIG_NET_CLS_POLICE
138 if (n->police) {
139 int pol_res = tcf_police(skb, n->police);
140 if (pol_res >= 0)
141 return pol_res;
142 } else
143 #endif
144 return 0;
145 }
146 n = n->next;
147 goto next_knode;
148 }
149
150 /* PUSH */
151 if (sdepth >= TC_U32_MAXDEPTH)
152 goto deadloop;
153 stack[sdepth].knode = n;
154 stack[sdepth].ptr = ptr;
155 sdepth++;
156
157 ht = n->ht_down;
158 sel = 0;
159 if (ht->divisor)
160 sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel);
161
162 if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
163 goto next_ht;
164
165 if (n->sel.flags&(TC_U32_EAT|TC_U32_VAROFFSET)) {
166 off2 = n->sel.off + 3;
167 if (n->sel.flags&TC_U32_VAROFFSET)
168 off2 += ntohs(n->sel.offmask & *(u16*)(ptr+n->sel.offoff)) >>n->sel.offshift;
169 off2 &= ~3;
170 }
171 if (n->sel.flags&TC_U32_EAT) {
172 ptr += off2;
173 off2 = 0;
174 }
175
176 if (ptr < skb->tail)
177 goto next_ht;
178 }
179
180 /* POP */
181 if (sdepth--) {
182 n = stack[sdepth].knode;
183 ht = n->ht_up;
184 ptr = stack[sdepth].ptr;
185 goto check_terminal;
186 }
187 return -1;
188
189 deadloop:
190 if (net_ratelimit())
191 printk("cls_u32: dead loop\n"