blob: ae83c3aec3082d3c4a1714c909f817835925a546 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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 * JHS: We should remove the CONFIG_NET_CLS_IND from here
28 * eventually when the meta match extension is made available
29 *
30 * nfmark match added by Catalin(ux aka Dino) BOIE <catab at umbrella.ro>
31 */
32
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include <linux/module.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090034#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include <linux/types.h>
36#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070038#include <linux/errno.h>
John Fastabend1ce87722014-09-12 20:09:16 -070039#include <linux/percpu.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070040#include <linux/rtnetlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070041#include <linux/skbuff.h>
Cong Wang7801db82014-07-17 17:34:53 -070042#include <linux/bitmap.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070043#include <net/netlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070044#include <net/act_api.h>
45#include <net/pkt_cls.h>
John Fastabenda1b7c5f2016-02-16 21:17:09 -080046#include <linux/netdevice.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070047
Eric Dumazetcc7ec452011-01-19 19:26:56 +000048struct tc_u_knode {
John Fastabend1ce87722014-09-12 20:09:16 -070049 struct tc_u_knode __rcu *next;
Linus Torvalds1da177e2005-04-16 15:20:36 -070050 u32 handle;
John Fastabend1ce87722014-09-12 20:09:16 -070051 struct tc_u_hnode __rcu *ht_up;
Linus Torvalds1da177e2005-04-16 15:20:36 -070052 struct tcf_exts exts;
53#ifdef CONFIG_NET_CLS_IND
WANG Cong2519a602014-01-09 16:14:02 -080054 int ifindex;
Linus Torvalds1da177e2005-04-16 15:20:36 -070055#endif
56 u8 fshift;
57 struct tcf_result res;
John Fastabend1ce87722014-09-12 20:09:16 -070058 struct tc_u_hnode __rcu *ht_down;
Linus Torvalds1da177e2005-04-16 15:20:36 -070059#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -070060 struct tc_u32_pcnt __percpu *pf;
Linus Torvalds1da177e2005-04-16 15:20:36 -070061#endif
John Fastabend9e8ce792016-02-26 07:54:39 -080062 u32 flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -070063#ifdef CONFIG_CLS_U32_MARK
John Fastabend459d5f62014-09-12 20:08:47 -070064 u32 val;
65 u32 mask;
66 u32 __percpu *pcpu_success;
Linus Torvalds1da177e2005-04-16 15:20:36 -070067#endif
John Fastabend1ce87722014-09-12 20:09:16 -070068 struct tcf_proto *tp;
John Fastabend1ce87722014-09-12 20:09:16 -070069 struct rcu_head rcu;
John Fastabend4e2840e2014-09-17 11:11:46 -070070 /* The 'sel' field MUST be the last field in structure to allow for
71 * tc_u32_keys allocated at end of structure.
72 */
73 struct tc_u32_sel sel;
Linus Torvalds1da177e2005-04-16 15:20:36 -070074};
75
Eric Dumazetcc7ec452011-01-19 19:26:56 +000076struct tc_u_hnode {
John Fastabend1ce87722014-09-12 20:09:16 -070077 struct tc_u_hnode __rcu *next;
Linus Torvalds1da177e2005-04-16 15:20:36 -070078 u32 handle;
79 u32 prio;
80 struct tc_u_common *tp_c;
81 int refcnt;
Eric Dumazetcc7ec452011-01-19 19:26:56 +000082 unsigned int divisor;
John Fastabend1ce87722014-09-12 20:09:16 -070083 struct rcu_head rcu;
WANG Cong5778d392015-03-09 17:03:40 -070084 /* The 'ht' field MUST be the last field in structure to allow for
85 * more entries allocated at end of structure.
86 */
87 struct tc_u_knode __rcu *ht[1];
Linus Torvalds1da177e2005-04-16 15:20:36 -070088};
89
Eric Dumazetcc7ec452011-01-19 19:26:56 +000090struct tc_u_common {
John Fastabend1ce87722014-09-12 20:09:16 -070091 struct tc_u_hnode __rcu *hlist;
Linus Torvalds1da177e2005-04-16 15:20:36 -070092 struct Qdisc *q;
93 int refcnt;
94 u32 hgenerator;
John Fastabend1ce87722014-09-12 20:09:16 -070095 struct rcu_head rcu;
Linus Torvalds1da177e2005-04-16 15:20:36 -070096};
97
Eric Dumazetcc7ec452011-01-19 19:26:56 +000098static inline unsigned int u32_hash_fold(__be32 key,
99 const struct tc_u32_sel *sel,
100 u8 fshift)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101{
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000102 unsigned int h = ntohl(key & sel->hmask) >> fshift;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103
104 return h;
105}
106
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400107static int u32_classify(struct sk_buff *skb, const struct tcf_proto *tp,
108 struct tcf_result *res)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109{
110 struct {
111 struct tc_u_knode *knode;
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700112 unsigned int off;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113 } stack[TC_U32_MAXDEPTH];
114
John Fastabend1ce87722014-09-12 20:09:16 -0700115 struct tc_u_hnode *ht = rcu_dereference_bh(tp->root);
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700116 unsigned int off = skb_network_offset(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700117 struct tc_u_knode *n;
118 int sdepth = 0;
119 int off2 = 0;
120 int sel = 0;
121#ifdef CONFIG_CLS_U32_PERF
122 int j;
123#endif
124 int i, r;
125
126next_ht:
John Fastabend1ce87722014-09-12 20:09:16 -0700127 n = rcu_dereference_bh(ht->ht[sel]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128
129next_knode:
130 if (n) {
131 struct tc_u32_key *key = n->sel.keys;
132
133#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -0700134 __this_cpu_inc(n->pf->rcnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700135 j = 0;
136#endif
137
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700138 if (tc_skip_sw(n->flags)) {
139 n = rcu_dereference_bh(n->next);
140 goto next_knode;
141 }
142
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143#ifdef CONFIG_CLS_U32_MARK
John Fastabend459d5f62014-09-12 20:08:47 -0700144 if ((skb->mark & n->mask) != n->val) {
John Fastabend1ce87722014-09-12 20:09:16 -0700145 n = rcu_dereference_bh(n->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146 goto next_knode;
147 } else {
John Fastabend459d5f62014-09-12 20:08:47 -0700148 __this_cpu_inc(*n->pcpu_success);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149 }
150#endif
151
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000152 for (i = n->sel.nkeys; i > 0; i--, key++) {
stephen hemminger66d50d22010-08-02 13:44:13 +0000153 int toff = off + key->off + (off2 & key->offmask);
stephen hemminger86fce3b2011-02-20 16:14:23 +0000154 __be32 *data, hdata;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155
Dan Carpenter4e18b3e2010-10-04 02:28:36 +0000156 if (skb_headroom(skb) + toff > INT_MAX)
stephen hemminger66d50d22010-08-02 13:44:13 +0000157 goto out;
158
stephen hemminger86fce3b2011-02-20 16:14:23 +0000159 data = skb_header_pointer(skb, toff, 4, &hdata);
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700160 if (!data)
161 goto out;
162 if ((*data ^ key->val) & key->mask) {
John Fastabend1ce87722014-09-12 20:09:16 -0700163 n = rcu_dereference_bh(n->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 goto next_knode;
165 }
166#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -0700167 __this_cpu_inc(n->pf->kcnts[j]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168 j++;
169#endif
170 }
John Fastabend1ce87722014-09-12 20:09:16 -0700171
172 ht = rcu_dereference_bh(n->ht_down);
173 if (!ht) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174check_terminal:
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000175 if (n->sel.flags & TC_U32_TERMINAL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700176
177 *res = n->res;
178#ifdef CONFIG_NET_CLS_IND
WANG Cong2519a602014-01-09 16:14:02 -0800179 if (!tcf_match_indev(skb, n->ifindex)) {
John Fastabend1ce87722014-09-12 20:09:16 -0700180 n = rcu_dereference_bh(n->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181 goto next_knode;
182 }
183#endif
184#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -0700185 __this_cpu_inc(n->pf->rhit);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186#endif
187 r = tcf_exts_exec(skb, &n->exts, res);
188 if (r < 0) {
John Fastabend1ce87722014-09-12 20:09:16 -0700189 n = rcu_dereference_bh(n->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190 goto next_knode;
191 }
192
193 return r;
194 }
John Fastabend1ce87722014-09-12 20:09:16 -0700195 n = rcu_dereference_bh(n->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196 goto next_knode;
197 }
198
199 /* PUSH */
200 if (sdepth >= TC_U32_MAXDEPTH)
201 goto deadloop;
202 stack[sdepth].knode = n;
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700203 stack[sdepth].off = off;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204 sdepth++;
205
John Fastabend1ce87722014-09-12 20:09:16 -0700206 ht = rcu_dereference_bh(n->ht_down);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207 sel = 0;
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700208 if (ht->divisor) {
stephen hemminger86fce3b2011-02-20 16:14:23 +0000209 __be32 *data, hdata;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700211 data = skb_header_pointer(skb, off + n->sel.hoff, 4,
stephen hemminger86fce3b2011-02-20 16:14:23 +0000212 &hdata);
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700213 if (!data)
214 goto out;
215 sel = ht->divisor & u32_hash_fold(*data, &n->sel,
216 n->fshift);
217 }
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000218 if (!(n->sel.flags & (TC_U32_VAROFFSET | TC_U32_OFFSET | TC_U32_EAT)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219 goto next_ht;
220
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000221 if (n->sel.flags & (TC_U32_OFFSET | TC_U32_VAROFFSET)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222 off2 = n->sel.off + 3;
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700223 if (n->sel.flags & TC_U32_VAROFFSET) {
stephen hemminger86fce3b2011-02-20 16:14:23 +0000224 __be16 *data, hdata;
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700225
226 data = skb_header_pointer(skb,
227 off + n->sel.offoff,
stephen hemminger86fce3b2011-02-20 16:14:23 +0000228 2, &hdata);
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700229 if (!data)
230 goto out;
231 off2 += ntohs(n->sel.offmask & *data) >>
232 n->sel.offshift;
233 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234 off2 &= ~3;
235 }
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000236 if (n->sel.flags & TC_U32_EAT) {
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700237 off += off2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238 off2 = 0;
239 }
240
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700241 if (off < skb->len)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700242 goto next_ht;
243 }
244
245 /* POP */
246 if (sdepth--) {
247 n = stack[sdepth].knode;
John Fastabend1ce87722014-09-12 20:09:16 -0700248 ht = rcu_dereference_bh(n->ht_up);
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700249 off = stack[sdepth].off;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250 goto check_terminal;
251 }
Changli Gaofbc2e7d2010-06-02 07:32:42 -0700252out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700253 return -1;
254
255deadloop:
Joe Perchese87cc472012-05-13 21:56:26 +0000256 net_warn_ratelimited("cls_u32: dead loop\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257 return -1;
258}
259
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400260static struct tc_u_hnode *u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261{
262 struct tc_u_hnode *ht;
263
John Fastabend1ce87722014-09-12 20:09:16 -0700264 for (ht = rtnl_dereference(tp_c->hlist);
265 ht;
266 ht = rtnl_dereference(ht->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267 if (ht->handle == handle)
268 break;
269
270 return ht;
271}
272
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400273static struct tc_u_knode *u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274{
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000275 unsigned int sel;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276 struct tc_u_knode *n = NULL;
277
278 sel = TC_U32_HASH(handle);
279 if (sel > ht->divisor)
280 goto out;
281
John Fastabend1ce87722014-09-12 20:09:16 -0700282 for (n = rtnl_dereference(ht->ht[sel]);
283 n;
284 n = rtnl_dereference(n->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285 if (n->handle == handle)
286 break;
287out:
288 return n;
289}
290
291
292static unsigned long u32_get(struct tcf_proto *tp, u32 handle)
293{
294 struct tc_u_hnode *ht;
295 struct tc_u_common *tp_c = tp->data;
296
297 if (TC_U32_HTID(handle) == TC_U32_ROOT)
John Fastabend1ce87722014-09-12 20:09:16 -0700298 ht = rtnl_dereference(tp->root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299 else
300 ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle));
301
302 if (!ht)
303 return 0;
304
305 if (TC_U32_KEY(handle) == 0)
306 return (unsigned long)ht;
307
308 return (unsigned long)u32_lookup_key(ht, handle);
309}
310
Linus Torvalds1da177e2005-04-16 15:20:36 -0700311static u32 gen_new_htid(struct tc_u_common *tp_c)
312{
313 int i = 0x800;
314
John Fastabend1ce87722014-09-12 20:09:16 -0700315 /* hgenerator only used inside rtnl lock it is safe to increment
316 * without read _copy_ update semantics
317 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700318 do {
319 if (++tp_c->hgenerator == 0x7FF)
320 tp_c->hgenerator = 1;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000321 } while (--i > 0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322
323 return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
324}
325
326static int u32_init(struct tcf_proto *tp)
327{
328 struct tc_u_hnode *root_ht;
329 struct tc_u_common *tp_c;
330
David S. Miller72b25a92008-07-18 20:54:17 -0700331 tp_c = tp->q->u32_node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700332
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700333 root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 if (root_ht == NULL)
335 return -ENOBUFS;
336
Linus Torvalds1da177e2005-04-16 15:20:36 -0700337 root_ht->divisor = 0;
338 root_ht->refcnt++;
339 root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;
340 root_ht->prio = tp->prio;
341
342 if (tp_c == NULL) {
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700343 tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 if (tp_c == NULL) {
345 kfree(root_ht);
346 return -ENOBUFS;
347 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348 tp_c->q = tp->q;
David S. Miller72b25a92008-07-18 20:54:17 -0700349 tp->q->u32_node = tp_c;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 }
351
352 tp_c->refcnt++;
John Fastabend1ce87722014-09-12 20:09:16 -0700353 RCU_INIT_POINTER(root_ht->next, tp_c->hlist);
354 rcu_assign_pointer(tp_c->hlist, root_ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355 root_ht->tp_c = tp_c;
356
John Fastabend1ce87722014-09-12 20:09:16 -0700357 rcu_assign_pointer(tp->root, root_ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358 tp->data = tp_c;
359 return 0;
360}
361
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400362static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n,
John Fastabendde5df632014-09-19 21:50:34 -0700363 bool free_pf)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364{
WANG Cong18d02642014-09-25 10:26:37 -0700365 tcf_exts_destroy(&n->exts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366 if (n->ht_down)
367 n->ht_down->refcnt--;
368#ifdef CONFIG_CLS_U32_PERF
John Fastabendde5df632014-09-19 21:50:34 -0700369 if (free_pf)
370 free_percpu(n->pf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371#endif
John Fastabenda1ddcfe2014-09-19 21:50:04 -0700372#ifdef CONFIG_CLS_U32_MARK
John Fastabendde5df632014-09-19 21:50:34 -0700373 if (free_pf)
374 free_percpu(n->pcpu_success);
John Fastabenda1ddcfe2014-09-19 21:50:04 -0700375#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 kfree(n);
377 return 0;
378}
379
John Fastabendde5df632014-09-19 21:50:34 -0700380/* u32_delete_key_rcu should be called when free'ing a copied
381 * version of a tc_u_knode obtained from u32_init_knode(). When
382 * copies are obtained from u32_init_knode() the statistics are
383 * shared between the old and new copies to allow readers to
384 * continue to update the statistics during the copy. To support
385 * this the u32_delete_key_rcu variant does not free the percpu
386 * statistics.
387 */
John Fastabend1ce87722014-09-12 20:09:16 -0700388static void u32_delete_key_rcu(struct rcu_head *rcu)
389{
390 struct tc_u_knode *key = container_of(rcu, struct tc_u_knode, rcu);
391
John Fastabendde5df632014-09-19 21:50:34 -0700392 u32_destroy_key(key->tp, key, false);
393}
394
395/* u32_delete_key_freepf_rcu is the rcu callback variant
396 * that free's the entire structure including the statistics
397 * percpu variables. Only use this if the key is not a copy
398 * returned by u32_init_knode(). See u32_delete_key_rcu()
399 * for the variant that should be used with keys return from
400 * u32_init_knode()
401 */
402static void u32_delete_key_freepf_rcu(struct rcu_head *rcu)
403{
404 struct tc_u_knode *key = container_of(rcu, struct tc_u_knode, rcu);
405
406 u32_destroy_key(key->tp, key, true);
John Fastabend1ce87722014-09-12 20:09:16 -0700407}
408
Yang Yingliang82d567c2013-12-10 20:55:31 +0800409static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410{
John Fastabend1ce87722014-09-12 20:09:16 -0700411 struct tc_u_knode __rcu **kp;
412 struct tc_u_knode *pkp;
John Fastabenda96366bf2014-09-15 23:30:49 -0700413 struct tc_u_hnode *ht = rtnl_dereference(key->ht_up);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414
415 if (ht) {
John Fastabend1ce87722014-09-12 20:09:16 -0700416 kp = &ht->ht[TC_U32_HASH(key->handle)];
417 for (pkp = rtnl_dereference(*kp); pkp;
418 kp = &pkp->next, pkp = rtnl_dereference(*kp)) {
419 if (pkp == key) {
420 RCU_INIT_POINTER(*kp, key->next);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421
WANG Conga0efb802014-09-30 16:07:24 -0700422 tcf_unbind_filter(tp, &key->res);
John Fastabendde5df632014-09-19 21:50:34 -0700423 call_rcu(&key->rcu, u32_delete_key_freepf_rcu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700424 return 0;
425 }
426 }
427 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700428 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429 return 0;
430}
431
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800432static void u32_remove_hw_knode(struct tcf_proto *tp, u32 handle)
433{
434 struct net_device *dev = tp->q->dev_queue->dev;
435 struct tc_cls_u32_offload u32_offload = {0};
436 struct tc_to_netdev offload;
437
438 offload.type = TC_SETUP_CLSU32;
439 offload.cls_u32 = &u32_offload;
440
Daniel Borkmann92c075d2016-06-06 22:50:39 +0200441 if (tc_should_offload(dev, tp, 0)) {
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800442 offload.cls_u32->command = TC_CLSU32_DELETE_KNODE;
443 offload.cls_u32->knode.handle = handle;
444 dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
445 tp->protocol, &offload);
446 }
447}
448
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400449static int u32_replace_hw_hnode(struct tcf_proto *tp, struct tc_u_hnode *h,
450 u32 flags)
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800451{
452 struct net_device *dev = tp->q->dev_queue->dev;
453 struct tc_cls_u32_offload u32_offload = {0};
454 struct tc_to_netdev offload;
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700455 int err;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800456
Daniel Borkmann92c075d2016-06-06 22:50:39 +0200457 if (!tc_should_offload(dev, tp, flags))
Jakub Kicinskid47a0f32016-06-06 16:16:48 +0100458 return tc_skip_sw(flags) ? -EINVAL : 0;
459
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800460 offload.type = TC_SETUP_CLSU32;
461 offload.cls_u32 = &u32_offload;
462
Jakub Kicinskid47a0f32016-06-06 16:16:48 +0100463 offload.cls_u32->command = TC_CLSU32_NEW_HNODE;
464 offload.cls_u32->hnode.divisor = h->divisor;
465 offload.cls_u32->hnode.handle = h->handle;
466 offload.cls_u32->hnode.prio = h->prio;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800467
Jakub Kicinskid47a0f32016-06-06 16:16:48 +0100468 err = dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
469 tp->protocol, &offload);
470 if (tc_skip_sw(flags))
471 return err;
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700472
473 return 0;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800474}
475
476static void u32_clear_hw_hnode(struct tcf_proto *tp, struct tc_u_hnode *h)
477{
478 struct net_device *dev = tp->q->dev_queue->dev;
479 struct tc_cls_u32_offload u32_offload = {0};
480 struct tc_to_netdev offload;
481
482 offload.type = TC_SETUP_CLSU32;
483 offload.cls_u32 = &u32_offload;
484
Daniel Borkmann92c075d2016-06-06 22:50:39 +0200485 if (tc_should_offload(dev, tp, 0)) {
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800486 offload.cls_u32->command = TC_CLSU32_DELETE_HNODE;
487 offload.cls_u32->hnode.divisor = h->divisor;
488 offload.cls_u32->hnode.handle = h->handle;
489 offload.cls_u32->hnode.prio = h->prio;
490
491 dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
492 tp->protocol, &offload);
493 }
494}
495
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400496static int u32_replace_hw_knode(struct tcf_proto *tp, struct tc_u_knode *n,
497 u32 flags)
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800498{
499 struct net_device *dev = tp->q->dev_queue->dev;
500 struct tc_cls_u32_offload u32_offload = {0};
501 struct tc_to_netdev offload;
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700502 int err;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800503
504 offload.type = TC_SETUP_CLSU32;
505 offload.cls_u32 = &u32_offload;
506
Jakub Kicinski201c44b2016-06-08 20:11:04 +0100507 if (!tc_should_offload(dev, tp, flags))
508 return tc_skip_sw(flags) ? -EINVAL : 0;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800509
Jakub Kicinski201c44b2016-06-08 20:11:04 +0100510 offload.cls_u32->command = TC_CLSU32_REPLACE_KNODE;
511 offload.cls_u32->knode.handle = n->handle;
512 offload.cls_u32->knode.fshift = n->fshift;
513#ifdef CONFIG_CLS_U32_MARK
514 offload.cls_u32->knode.val = n->val;
515 offload.cls_u32->knode.mask = n->mask;
516#else
517 offload.cls_u32->knode.val = 0;
518 offload.cls_u32->knode.mask = 0;
519#endif
520 offload.cls_u32->knode.sel = &n->sel;
521 offload.cls_u32->knode.exts = &n->exts;
522 if (n->ht_down)
523 offload.cls_u32->knode.link_handle = n->ht_down->handle;
524
525 err = dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
526 tp->protocol, &offload);
527 if (tc_skip_sw(flags))
528 return err;
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700529
530 return 0;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800531}
532
WANG Conga0efb802014-09-30 16:07:24 -0700533static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534{
535 struct tc_u_knode *n;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000536 unsigned int h;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700537
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000538 for (h = 0; h <= ht->divisor; h++) {
John Fastabend1ce87722014-09-12 20:09:16 -0700539 while ((n = rtnl_dereference(ht->ht[h])) != NULL) {
540 RCU_INIT_POINTER(ht->ht[h],
541 rtnl_dereference(n->next));
WANG Conga0efb802014-09-30 16:07:24 -0700542 tcf_unbind_filter(tp, &n->res);
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800543 u32_remove_hw_knode(tp, n->handle);
John Fastabendde5df632014-09-19 21:50:34 -0700544 call_rcu(&n->rcu, u32_delete_key_freepf_rcu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700545 }
546 }
547}
548
549static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
550{
551 struct tc_u_common *tp_c = tp->data;
John Fastabend1ce87722014-09-12 20:09:16 -0700552 struct tc_u_hnode __rcu **hn;
553 struct tc_u_hnode *phn;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700555 WARN_ON(ht->refcnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556
WANG Conga0efb802014-09-30 16:07:24 -0700557 u32_clear_hnode(tp, ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558
John Fastabend1ce87722014-09-12 20:09:16 -0700559 hn = &tp_c->hlist;
560 for (phn = rtnl_dereference(*hn);
561 phn;
562 hn = &phn->next, phn = rtnl_dereference(*hn)) {
563 if (phn == ht) {
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800564 u32_clear_hw_hnode(tp, ht);
John Fastabend1ce87722014-09-12 20:09:16 -0700565 RCU_INIT_POINTER(*hn, ht->next);
566 kfree_rcu(ht, rcu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 return 0;
568 }
569 }
570
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571 return -ENOENT;
572}
573
Cong Wang1e052be2015-03-06 11:47:59 -0800574static bool ht_empty(struct tc_u_hnode *ht)
575{
576 unsigned int h;
577
578 for (h = 0; h <= ht->divisor; h++)
579 if (rcu_access_pointer(ht->ht[h]))
580 return false;
581
582 return true;
583}
584
585static bool u32_destroy(struct tcf_proto *tp, bool force)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586{
587 struct tc_u_common *tp_c = tp->data;
John Fastabend1ce87722014-09-12 20:09:16 -0700588 struct tc_u_hnode *root_ht = rtnl_dereference(tp->root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700590 WARN_ON(root_ht == NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591
Cong Wang1e052be2015-03-06 11:47:59 -0800592 if (!force) {
593 if (root_ht) {
594 if (root_ht->refcnt > 1)
595 return false;
596 if (root_ht->refcnt == 1) {
597 if (!ht_empty(root_ht))
598 return false;
599 }
600 }
WANG Conga6c1aea2015-08-25 16:38:12 -0700601
602 if (tp_c->refcnt > 1)
603 return false;
604
605 if (tp_c->refcnt == 1) {
606 struct tc_u_hnode *ht;
607
608 for (ht = rtnl_dereference(tp_c->hlist);
609 ht;
610 ht = rtnl_dereference(ht->next))
611 if (!ht_empty(ht))
612 return false;
613 }
Cong Wang1e052be2015-03-06 11:47:59 -0800614 }
615
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616 if (root_ht && --root_ht->refcnt == 0)
617 u32_destroy_hnode(tp, root_ht);
618
619 if (--tp_c->refcnt == 0) {
620 struct tc_u_hnode *ht;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621
David S. Miller72b25a92008-07-18 20:54:17 -0700622 tp->q->u32_node = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623
John Fastabend1ce87722014-09-12 20:09:16 -0700624 for (ht = rtnl_dereference(tp_c->hlist);
625 ht;
626 ht = rtnl_dereference(ht->next)) {
Jarek Poplawskie56cfad2008-04-12 18:37:13 -0700627 ht->refcnt--;
WANG Conga0efb802014-09-30 16:07:24 -0700628 u32_clear_hnode(tp, ht);
Jarek Poplawskie56cfad2008-04-12 18:37:13 -0700629 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630
John Fastabend1ce87722014-09-12 20:09:16 -0700631 while ((ht = rtnl_dereference(tp_c->hlist)) != NULL) {
632 RCU_INIT_POINTER(tp_c->hlist, ht->next);
633 kfree_rcu(ht, rcu);
Stephen Hemminger3ff50b72007-04-20 17:09:22 -0700634 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635
636 kfree(tp_c);
637 }
638
639 tp->data = NULL;
Cong Wang1e052be2015-03-06 11:47:59 -0800640 return true;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700641}
642
643static int u32_delete(struct tcf_proto *tp, unsigned long arg)
644{
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000645 struct tc_u_hnode *ht = (struct tc_u_hnode *)arg;
John Fastabend1ce87722014-09-12 20:09:16 -0700646 struct tc_u_hnode *root_ht = rtnl_dereference(tp->root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647
648 if (ht == NULL)
649 return 0;
650
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800651 if (TC_U32_KEY(ht->handle)) {
652 u32_remove_hw_knode(tp, ht->handle);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000653 return u32_delete_key(tp, (struct tc_u_knode *)ht);
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800654 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655
John Fastabend1ce87722014-09-12 20:09:16 -0700656 if (root_ht == ht)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657 return -EINVAL;
658
Jarek Poplawskie56cfad2008-04-12 18:37:13 -0700659 if (ht->refcnt == 1) {
660 ht->refcnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661 u32_destroy_hnode(tp, ht);
Jarek Poplawskie56cfad2008-04-12 18:37:13 -0700662 } else {
663 return -EBUSY;
664 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665
666 return 0;
667}
668
Cong Wang7801db82014-07-17 17:34:53 -0700669#define NR_U32_NODE (1<<12)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
671{
672 struct tc_u_knode *n;
Cong Wang7801db82014-07-17 17:34:53 -0700673 unsigned long i;
674 unsigned long *bitmap = kzalloc(BITS_TO_LONGS(NR_U32_NODE) * sizeof(unsigned long),
675 GFP_KERNEL);
676 if (!bitmap)
677 return handle | 0xFFF;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678
John Fastabend1ce87722014-09-12 20:09:16 -0700679 for (n = rtnl_dereference(ht->ht[TC_U32_HASH(handle)]);
680 n;
681 n = rtnl_dereference(n->next))
Cong Wang7801db82014-07-17 17:34:53 -0700682 set_bit(TC_U32_NODE(n->handle), bitmap);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683
Cong Wang7801db82014-07-17 17:34:53 -0700684 i = find_next_zero_bit(bitmap, NR_U32_NODE, 0x800);
685 if (i >= NR_U32_NODE)
686 i = find_next_zero_bit(bitmap, NR_U32_NODE, 1);
687
688 kfree(bitmap);
689 return handle | (i >= NR_U32_NODE ? 0xFFF : i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700690}
691
Patrick McHardy6fa8c012008-01-23 20:36:12 -0800692static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
693 [TCA_U32_CLASSID] = { .type = NLA_U32 },
694 [TCA_U32_HASH] = { .type = NLA_U32 },
695 [TCA_U32_LINK] = { .type = NLA_U32 },
696 [TCA_U32_DIVISOR] = { .type = NLA_U32 },
697 [TCA_U32_SEL] = { .len = sizeof(struct tc_u32_sel) },
698 [TCA_U32_INDEV] = { .type = NLA_STRING, .len = IFNAMSIZ },
699 [TCA_U32_MARK] = { .len = sizeof(struct tc_u32_mark) },
John Fastabend9e8ce792016-02-26 07:54:39 -0800700 [TCA_U32_FLAGS] = { .type = NLA_U32 },
Patrick McHardy6fa8c012008-01-23 20:36:12 -0800701};
702
Benjamin LaHaisec1b52732013-01-14 05:15:39 +0000703static int u32_set_parms(struct net *net, struct tcf_proto *tp,
704 unsigned long base, struct tc_u_hnode *ht,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800705 struct tc_u_knode *n, struct nlattr **tb,
Cong Wang2f7ef2f2014-04-25 13:54:06 -0700706 struct nlattr *est, bool ovr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700707{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708 struct tcf_exts e;
WANG Congb9a24bb2016-08-19 12:36:54 -0700709 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710
WANG Congb9a24bb2016-08-19 12:36:54 -0700711 err = tcf_exts_init(&e, TCA_U32_ACT, TCA_U32_POLICE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712 if (err < 0)
713 return err;
WANG Congb9a24bb2016-08-19 12:36:54 -0700714 err = tcf_exts_validate(net, tp, tb, est, &e, ovr);
715 if (err < 0)
716 goto errout;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717
718 err = -EINVAL;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800719 if (tb[TCA_U32_LINK]) {
Patrick McHardy1587bac2008-01-23 20:35:03 -0800720 u32 handle = nla_get_u32(tb[TCA_U32_LINK]);
Patrick McHardy47a1a1d2008-11-19 08:03:09 +0000721 struct tc_u_hnode *ht_down = NULL, *ht_old;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700722
723 if (TC_U32_KEY(handle))
724 goto errout;
725
726 if (handle) {
727 ht_down = u32_lookup_ht(ht->tp_c, handle);
728
729 if (ht_down == NULL)
730 goto errout;
731 ht_down->refcnt++;
732 }
733
John Fastabend1ce87722014-09-12 20:09:16 -0700734 ht_old = rtnl_dereference(n->ht_down);
735 rcu_assign_pointer(n->ht_down, ht_down);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736
Patrick McHardy47a1a1d2008-11-19 08:03:09 +0000737 if (ht_old)
738 ht_old->refcnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700739 }
Patrick McHardyadd93b62008-01-22 22:11:33 -0800740 if (tb[TCA_U32_CLASSID]) {
Patrick McHardy1587bac2008-01-23 20:35:03 -0800741 n->res.classid = nla_get_u32(tb[TCA_U32_CLASSID]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700742 tcf_bind_filter(tp, &n->res, base);
743 }
744
745#ifdef CONFIG_NET_CLS_IND
Patrick McHardyadd93b62008-01-22 22:11:33 -0800746 if (tb[TCA_U32_INDEV]) {
WANG Cong2519a602014-01-09 16:14:02 -0800747 int ret;
748 ret = tcf_change_indev(net, tb[TCA_U32_INDEV]);
749 if (ret < 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700750 goto errout;
WANG Cong2519a602014-01-09 16:14:02 -0800751 n->ifindex = ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752 }
753#endif
754 tcf_exts_change(tp, &n->exts, &e);
755
756 return 0;
757errout:
WANG Cong18d02642014-09-25 10:26:37 -0700758 tcf_exts_destroy(&e);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759 return err;
760}
761
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400762static void u32_replace_knode(struct tcf_proto *tp, struct tc_u_common *tp_c,
John Fastabendde5df632014-09-19 21:50:34 -0700763 struct tc_u_knode *n)
764{
765 struct tc_u_knode __rcu **ins;
766 struct tc_u_knode *pins;
767 struct tc_u_hnode *ht;
768
769 if (TC_U32_HTID(n->handle) == TC_U32_ROOT)
770 ht = rtnl_dereference(tp->root);
771 else
772 ht = u32_lookup_ht(tp_c, TC_U32_HTID(n->handle));
773
774 ins = &ht->ht[TC_U32_HASH(n->handle)];
775
776 /* The node must always exist for it to be replaced if this is not the
777 * case then something went very wrong elsewhere.
778 */
779 for (pins = rtnl_dereference(*ins); ;
780 ins = &pins->next, pins = rtnl_dereference(*ins))
781 if (pins->handle == n->handle)
782 break;
783
784 RCU_INIT_POINTER(n->next, pins->next);
785 rcu_assign_pointer(*ins, n);
786}
787
788static struct tc_u_knode *u32_init_knode(struct tcf_proto *tp,
789 struct tc_u_knode *n)
790{
791 struct tc_u_knode *new;
792 struct tc_u32_sel *s = &n->sel;
793
794 new = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key),
795 GFP_KERNEL);
796
797 if (!new)
798 return NULL;
799
800 RCU_INIT_POINTER(new->next, n->next);
801 new->handle = n->handle;
802 RCU_INIT_POINTER(new->ht_up, n->ht_up);
803
804#ifdef CONFIG_NET_CLS_IND
805 new->ifindex = n->ifindex;
806#endif
807 new->fshift = n->fshift;
808 new->res = n->res;
John Fastabend9e8ce792016-02-26 07:54:39 -0800809 new->flags = n->flags;
John Fastabendde5df632014-09-19 21:50:34 -0700810 RCU_INIT_POINTER(new->ht_down, n->ht_down);
811
812 /* bump reference count as long as we hold pointer to structure */
813 if (new->ht_down)
814 new->ht_down->refcnt++;
815
816#ifdef CONFIG_CLS_U32_PERF
817 /* Statistics may be incremented by readers during update
818 * so we must keep them in tact. When the node is later destroyed
819 * a special destroy call must be made to not free the pf memory.
820 */
821 new->pf = n->pf;
822#endif
823
824#ifdef CONFIG_CLS_U32_MARK
825 new->val = n->val;
826 new->mask = n->mask;
827 /* Similarly success statistics must be moved as pointers */
828 new->pcpu_success = n->pcpu_success;
829#endif
830 new->tp = tp;
831 memcpy(&new->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
832
WANG Congb9a24bb2016-08-19 12:36:54 -0700833 if (tcf_exts_init(&new->exts, TCA_U32_ACT, TCA_U32_POLICE)) {
834 kfree(new);
835 return NULL;
836 }
John Fastabendde5df632014-09-19 21:50:34 -0700837
838 return new;
839}
840
Benjamin LaHaisec1b52732013-01-14 05:15:39 +0000841static int u32_change(struct net *net, struct sk_buff *in_skb,
Eric W. Biedermanaf4c6642012-05-25 13:42:45 -0600842 struct tcf_proto *tp, unsigned long base, u32 handle,
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -0400843 struct nlattr **tca, unsigned long *arg, bool ovr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844{
845 struct tc_u_common *tp_c = tp->data;
846 struct tc_u_hnode *ht;
847 struct tc_u_knode *n;
848 struct tc_u32_sel *s;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800849 struct nlattr *opt = tca[TCA_OPTIONS];
850 struct nlattr *tb[TCA_U32_MAX + 1];
John Fastabend9e8ce792016-02-26 07:54:39 -0800851 u32 htid, flags = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852 int err;
John Fastabend459d5f62014-09-12 20:08:47 -0700853#ifdef CONFIG_CLS_U32_PERF
854 size_t size;
855#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856
857 if (opt == NULL)
858 return handle ? -EINVAL : 0;
859
Patrick McHardy6fa8c012008-01-23 20:36:12 -0800860 err = nla_parse_nested(tb, TCA_U32_MAX, opt, u32_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800861 if (err < 0)
862 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700864 if (tb[TCA_U32_FLAGS]) {
John Fastabend9e8ce792016-02-26 07:54:39 -0800865 flags = nla_get_u32(tb[TCA_U32_FLAGS]);
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700866 if (!tc_flags_valid(flags))
Jakub Kicinski1a0f7d22016-06-06 16:16:47 +0100867 return -EINVAL;
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700868 }
John Fastabend9e8ce792016-02-26 07:54:39 -0800869
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000870 n = (struct tc_u_knode *)*arg;
871 if (n) {
John Fastabendde5df632014-09-19 21:50:34 -0700872 struct tc_u_knode *new;
873
Linus Torvalds1da177e2005-04-16 15:20:36 -0700874 if (TC_U32_KEY(n->handle) == 0)
875 return -EINVAL;
876
John Fastabend9e8ce792016-02-26 07:54:39 -0800877 if (n->flags != flags)
878 return -EINVAL;
879
John Fastabendde5df632014-09-19 21:50:34 -0700880 new = u32_init_knode(tp, n);
881 if (!new)
882 return -ENOMEM;
883
884 err = u32_set_parms(net, tp, base,
885 rtnl_dereference(n->ht_up), new, tb,
886 tca[TCA_RATE], ovr);
887
888 if (err) {
889 u32_destroy_key(tp, new, false);
890 return err;
891 }
892
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -0700893 err = u32_replace_hw_knode(tp, new, flags);
894 if (err) {
895 u32_destroy_key(tp, new, false);
896 return err;
897 }
898
John Fastabendde5df632014-09-19 21:50:34 -0700899 u32_replace_knode(tp, tp_c, new);
WANG Conga0efb802014-09-30 16:07:24 -0700900 tcf_unbind_filter(tp, &n->res);
John Fastabendde5df632014-09-19 21:50:34 -0700901 call_rcu(&n->rcu, u32_delete_key_rcu);
902 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903 }
904
Patrick McHardyadd93b62008-01-22 22:11:33 -0800905 if (tb[TCA_U32_DIVISOR]) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000906 unsigned int divisor = nla_get_u32(tb[TCA_U32_DIVISOR]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907
908 if (--divisor > 0x100)
909 return -EINVAL;
910 if (TC_U32_KEY(handle))
911 return -EINVAL;
912 if (handle == 0) {
913 handle = gen_new_htid(tp->data);
914 if (handle == 0)
915 return -ENOMEM;
916 }
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000917 ht = kzalloc(sizeof(*ht) + divisor*sizeof(void *), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918 if (ht == NULL)
919 return -ENOBUFS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700920 ht->tp_c = tp_c;
Jarek Poplawskie56cfad2008-04-12 18:37:13 -0700921 ht->refcnt = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922 ht->divisor = divisor;
923 ht->handle = handle;
924 ht->prio = tp->prio;
Jakub Kicinski6eef3802016-06-08 20:11:03 +0100925
926 err = u32_replace_hw_hnode(tp, ht, flags);
927 if (err) {
928 kfree(ht);
929 return err;
930 }
931
John Fastabend1ce87722014-09-12 20:09:16 -0700932 RCU_INIT_POINTER(ht->next, tp_c->hlist);
933 rcu_assign_pointer(tp_c->hlist, ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934 *arg = (unsigned long)ht;
John Fastabenda1b7c5f2016-02-16 21:17:09 -0800935
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936 return 0;
937 }
938
Patrick McHardyadd93b62008-01-22 22:11:33 -0800939 if (tb[TCA_U32_HASH]) {
Patrick McHardy1587bac2008-01-23 20:35:03 -0800940 htid = nla_get_u32(tb[TCA_U32_HASH]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941 if (TC_U32_HTID(htid) == TC_U32_ROOT) {
John Fastabend1ce87722014-09-12 20:09:16 -0700942 ht = rtnl_dereference(tp->root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700943 htid = ht->handle;
944 } else {
945 ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));
946 if (ht == NULL)
947 return -EINVAL;
948 }
949 } else {
John Fastabend1ce87722014-09-12 20:09:16 -0700950 ht = rtnl_dereference(tp->root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700951 htid = ht->handle;
952 }
953
954 if (ht->divisor < TC_U32_HASH(htid))
955 return -EINVAL;
956
957 if (handle) {
958 if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
959 return -EINVAL;
960 handle = htid | TC_U32_NODE(handle);
961 } else
962 handle = gen_new_kid(ht, htid);
963
Patrick McHardy6fa8c012008-01-23 20:36:12 -0800964 if (tb[TCA_U32_SEL] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700965 return -EINVAL;
966
Patrick McHardyadd93b62008-01-22 22:11:33 -0800967 s = nla_data(tb[TCA_U32_SEL]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700969 n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970 if (n == NULL)
971 return -ENOBUFS;
972
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -0700974 size = sizeof(struct tc_u32_pcnt) + s->nkeys * sizeof(u64);
975 n->pf = __alloc_percpu(size, __alignof__(struct tc_u32_pcnt));
976 if (!n->pf) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700977 kfree(n);
978 return -ENOBUFS;
979 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980#endif
981
982 memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
John Fastabenda96366bf2014-09-15 23:30:49 -0700983 RCU_INIT_POINTER(n->ht_up, ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700984 n->handle = handle;
Radu Rendecb2268012007-11-10 21:54:50 -0800985 n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
John Fastabend9e8ce792016-02-26 07:54:39 -0800986 n->flags = flags;
John Fastabend1ce87722014-09-12 20:09:16 -0700987 n->tp = tp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988
WANG Congb9a24bb2016-08-19 12:36:54 -0700989 err = tcf_exts_init(&n->exts, TCA_U32_ACT, TCA_U32_POLICE);
990 if (err < 0)
991 goto errout;
992
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993#ifdef CONFIG_CLS_U32_MARK
John Fastabend459d5f62014-09-12 20:08:47 -0700994 n->pcpu_success = alloc_percpu(u32);
John Fastabenda1ddcfe2014-09-19 21:50:04 -0700995 if (!n->pcpu_success) {
996 err = -ENOMEM;
997 goto errout;
998 }
John Fastabend459d5f62014-09-12 20:08:47 -0700999
Patrick McHardyadd93b62008-01-22 22:11:33 -08001000 if (tb[TCA_U32_MARK]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001001 struct tc_u32_mark *mark;
1002
Patrick McHardyadd93b62008-01-22 22:11:33 -08001003 mark = nla_data(tb[TCA_U32_MARK]);
John Fastabend459d5f62014-09-12 20:08:47 -07001004 n->val = mark->val;
1005 n->mask = mark->mask;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001006 }
1007#endif
1008
Cong Wang2f7ef2f2014-04-25 13:54:06 -07001009 err = u32_set_parms(net, tp, base, ht, n, tb, tca[TCA_RATE], ovr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010 if (err == 0) {
John Fastabend1ce87722014-09-12 20:09:16 -07001011 struct tc_u_knode __rcu **ins;
1012 struct tc_u_knode *pins;
1013
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -07001014 err = u32_replace_hw_knode(tp, n, flags);
1015 if (err)
1016 goto errhw;
1017
John Fastabend1ce87722014-09-12 20:09:16 -07001018 ins = &ht->ht[TC_U32_HASH(handle)];
1019 for (pins = rtnl_dereference(*ins); pins;
1020 ins = &pins->next, pins = rtnl_dereference(*ins))
1021 if (TC_U32_NODE(handle) < TC_U32_NODE(pins->handle))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022 break;
1023
John Fastabend1ce87722014-09-12 20:09:16 -07001024 RCU_INIT_POINTER(n->next, pins);
1025 rcu_assign_pointer(*ins, n);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026 *arg = (unsigned long)n;
1027 return 0;
1028 }
John Fastabenda1ddcfe2014-09-19 21:50:04 -07001029
Samudrala, Sridhard34e3e12016-05-12 17:08:23 -07001030errhw:
John Fastabenda1ddcfe2014-09-19 21:50:04 -07001031#ifdef CONFIG_CLS_U32_MARK
1032 free_percpu(n->pcpu_success);
1033#endif
1034
WANG Congb9a24bb2016-08-19 12:36:54 -07001035errout:
1036 tcf_exts_destroy(&n->exts);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001037#ifdef CONFIG_CLS_U32_PERF
John Fastabend1ce87722014-09-12 20:09:16 -07001038 free_percpu(n->pf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039#endif
1040 kfree(n);
1041 return err;
1042}
1043
1044static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg)
1045{
1046 struct tc_u_common *tp_c = tp->data;
1047 struct tc_u_hnode *ht;
1048 struct tc_u_knode *n;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001049 unsigned int h;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001050
1051 if (arg->stop)
1052 return;
1053
John Fastabend1ce87722014-09-12 20:09:16 -07001054 for (ht = rtnl_dereference(tp_c->hlist);
1055 ht;
1056 ht = rtnl_dereference(ht->next)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057 if (ht->prio != tp->prio)
1058 continue;
1059 if (arg->count >= arg->skip) {
1060 if (arg->fn(tp, (unsigned long)ht, arg) < 0) {
1061 arg->stop = 1;
1062 return;
1063 }
1064 }
1065 arg->count++;
1066 for (h = 0; h <= ht->divisor; h++) {
John Fastabend1ce87722014-09-12 20:09:16 -07001067 for (n = rtnl_dereference(ht->ht[h]);
1068 n;
1069 n = rtnl_dereference(n->next)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070 if (arg->count < arg->skip) {
1071 arg->count++;
1072 continue;
1073 }
1074 if (arg->fn(tp, (unsigned long)n, arg) < 0) {
1075 arg->stop = 1;
1076 return;
1077 }
1078 arg->count++;
1079 }
1080 }
1081 }
1082}
1083
WANG Cong832d1d52014-01-09 16:14:01 -08001084static int u32_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
Jamal Hadi Salim5a7a5552016-09-18 08:45:33 -04001085 struct sk_buff *skb, struct tcmsg *t)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001086{
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001087 struct tc_u_knode *n = (struct tc_u_knode *)fh;
John Fastabend1ce87722014-09-12 20:09:16 -07001088 struct tc_u_hnode *ht_up, *ht_down;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001089 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090
1091 if (n == NULL)
1092 return skb->len;
1093
1094 t->tcm_handle = n->handle;
1095
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001096 nest = nla_nest_start(skb, TCA_OPTIONS);
1097 if (nest == NULL)
1098 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099
1100 if (TC_U32_KEY(n->handle) == 0) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001101 struct tc_u_hnode *ht = (struct tc_u_hnode *)fh;
1102 u32 divisor = ht->divisor + 1;
1103
David S. Miller1b34ec42012-03-29 05:11:39 -04001104 if (nla_put_u32(skb, TCA_U32_DIVISOR, divisor))
1105 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106 } else {
John Fastabend459d5f62014-09-12 20:08:47 -07001107#ifdef CONFIG_CLS_U32_PERF
1108 struct tc_u32_pcnt *gpf;
John Fastabend459d5f62014-09-12 20:08:47 -07001109 int cpu;
John Fastabend80aab732014-09-15 23:30:26 -07001110#endif
John Fastabend459d5f62014-09-12 20:08:47 -07001111
David S. Miller1b34ec42012-03-29 05:11:39 -04001112 if (nla_put(skb, TCA_U32_SEL,
1113 sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
1114 &n->sel))
1115 goto nla_put_failure;
John Fastabend1ce87722014-09-12 20:09:16 -07001116
1117 ht_up = rtnl_dereference(n->ht_up);
1118 if (ht_up) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001119 u32 htid = n->handle & 0xFFFFF000;
David S. Miller1b34ec42012-03-29 05:11:39 -04001120 if (nla_put_u32(skb, TCA_U32_HASH, htid))
1121 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122 }
David S. Miller1b34ec42012-03-29 05:11:39 -04001123 if (n->res.classid &&
1124 nla_put_u32(skb, TCA_U32_CLASSID, n->res.classid))
1125 goto nla_put_failure;
John Fastabend1ce87722014-09-12 20:09:16 -07001126
1127 ht_down = rtnl_dereference(n->ht_down);
1128 if (ht_down &&
1129 nla_put_u32(skb, TCA_U32_LINK, ht_down->handle))
David S. Miller1b34ec42012-03-29 05:11:39 -04001130 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001131
John Fastabend9e8ce792016-02-26 07:54:39 -08001132 if (n->flags && nla_put_u32(skb, TCA_U32_FLAGS, n->flags))
1133 goto nla_put_failure;
1134
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135#ifdef CONFIG_CLS_U32_MARK
John Fastabend459d5f62014-09-12 20:08:47 -07001136 if ((n->val || n->mask)) {
1137 struct tc_u32_mark mark = {.val = n->val,
1138 .mask = n->mask,
1139 .success = 0};
John Fastabend80aab732014-09-15 23:30:26 -07001140 int cpum;
John Fastabend459d5f62014-09-12 20:08:47 -07001141
John Fastabend80aab732014-09-15 23:30:26 -07001142 for_each_possible_cpu(cpum) {
1143 __u32 cnt = *per_cpu_ptr(n->pcpu_success, cpum);
John Fastabend459d5f62014-09-12 20:08:47 -07001144
1145 mark.success += cnt;
1146 }
1147
1148 if (nla_put(skb, TCA_U32_MARK, sizeof(mark), &mark))
1149 goto nla_put_failure;
1150 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151#endif
1152
WANG Cong5da57f42013-12-15 20:15:07 -08001153 if (tcf_exts_dump(skb, &n->exts) < 0)
Patrick McHardyadd93b62008-01-22 22:11:33 -08001154 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001155
1156#ifdef CONFIG_NET_CLS_IND
WANG Cong2519a602014-01-09 16:14:02 -08001157 if (n->ifindex) {
1158 struct net_device *dev;
1159 dev = __dev_get_by_index(net, n->ifindex);
1160 if (dev && nla_put_string(skb, TCA_U32_INDEV, dev->name))
1161 goto nla_put_failure;
1162 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163#endif
1164#ifdef CONFIG_CLS_U32_PERF
John Fastabend459d5f62014-09-12 20:08:47 -07001165 gpf = kzalloc(sizeof(struct tc_u32_pcnt) +
1166 n->sel.nkeys * sizeof(u64),
1167 GFP_KERNEL);
1168 if (!gpf)
1169 goto nla_put_failure;
1170
1171 for_each_possible_cpu(cpu) {
1172 int i;
1173 struct tc_u32_pcnt *pf = per_cpu_ptr(n->pf, cpu);
1174
1175 gpf->rcnt += pf->rcnt;
1176 gpf->rhit += pf->rhit;
1177 for (i = 0; i < n->sel.nkeys; i++)
1178 gpf->kcnts[i] += pf->kcnts[i];
1179 }
1180
Nicolas Dichtel98545182016-04-26 10:06:18 +02001181 if (nla_put_64bit(skb, TCA_U32_PCNT,
1182 sizeof(struct tc_u32_pcnt) +
1183 n->sel.nkeys * sizeof(u64),
1184 gpf, TCA_U32_PAD)) {
John Fastabend459d5f62014-09-12 20:08:47 -07001185 kfree(gpf);
David S. Miller1b34ec42012-03-29 05:11:39 -04001186 goto nla_put_failure;
John Fastabend459d5f62014-09-12 20:08:47 -07001187 }
1188 kfree(gpf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001189#endif
1190 }
1191
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001192 nla_nest_end(skb, nest);
1193
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194 if (TC_U32_KEY(n->handle))
WANG Cong5da57f42013-12-15 20:15:07 -08001195 if (tcf_exts_dump_stats(skb, &n->exts) < 0)
Patrick McHardyadd93b62008-01-22 22:11:33 -08001196 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001197 return skb->len;
1198
Patrick McHardyadd93b62008-01-22 22:11:33 -08001199nla_put_failure:
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001200 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201 return -1;
1202}
1203
Patrick McHardy2eb9d752008-01-22 22:10:42 -08001204static struct tcf_proto_ops cls_u32_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205 .kind = "u32",
1206 .classify = u32_classify,
1207 .init = u32_init,
1208 .destroy = u32_destroy,
1209 .get = u32_get,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001210 .change = u32_change,
1211 .delete = u32_delete,
1212 .walk = u32_walk,
1213 .dump = u32_dump,
1214 .owner = THIS_MODULE,
1215};
1216
1217static int __init init_u32(void)
1218{
stephen hemminger6ff9c362010-05-12 06:37:05 +00001219 pr_info("u32 classifier\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001220#ifdef CONFIG_CLS_U32_PERF
stephen hemminger6ff9c362010-05-12 06:37:05 +00001221 pr_info(" Performance counters on\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001223#ifdef CONFIG_NET_CLS_IND
stephen hemminger6ff9c362010-05-12 06:37:05 +00001224 pr_info(" input device check on\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001225#endif
1226#ifdef CONFIG_NET_CLS_ACT
stephen hemminger6ff9c362010-05-12 06:37:05 +00001227 pr_info(" Actions configured\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001228#endif
1229 return register_tcf_proto_ops(&cls_u32_ops);
1230}
1231
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +09001232static void __exit exit_u32(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001233{
1234 unregister_tcf_proto_ops(&cls_u32_ops);
1235}
1236
1237module_init(init_u32)
1238module_exit(exit_u32)
1239MODULE_LICENSE("GPL");