]> git.kernelconcepts.de Git - karo-tx-linux.git/blob - net/sched/cls_u32.c
Merge branches 'pm-qos' and 'pm-devfreq'
[karo-tx-linux.git] / net / sched / cls_u32.c
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  *      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
33 #include <linux/module.h>
34 #include <linux/slab.h>
35 #include <linux/types.h>
36 #include <linux/kernel.h>
37 #include <linux/string.h>
38 #include <linux/errno.h>
39 #include <linux/percpu.h>
40 #include <linux/rtnetlink.h>
41 #include <linux/skbuff.h>
42 #include <linux/bitmap.h>
43 #include <net/netlink.h>
44 #include <net/act_api.h>
45 #include <net/pkt_cls.h>
46 #include <linux/netdevice.h>
47
48 struct tc_u_knode {
49         struct tc_u_knode __rcu *next;
50         u32                     handle;
51         struct tc_u_hnode __rcu *ht_up;
52         struct tcf_exts         exts;
53 #ifdef CONFIG_NET_CLS_IND
54         int                     ifindex;
55 #endif
56         u8                      fshift;
57         struct tcf_result       res;
58         struct tc_u_hnode __rcu *ht_down;
59 #ifdef CONFIG_CLS_U32_PERF
60         struct tc_u32_pcnt __percpu *pf;
61 #endif
62         u32                     flags;
63 #ifdef CONFIG_CLS_U32_MARK
64         u32                     val;
65         u32                     mask;
66         u32 __percpu            *pcpu_success;
67 #endif
68         struct tcf_proto        *tp;
69         struct rcu_head         rcu;
70         /* 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;
74 };
75
76 struct tc_u_hnode {
77         struct tc_u_hnode __rcu *next;
78         u32                     handle;
79         u32                     prio;
80         struct tc_u_common      *tp_c;
81         int                     refcnt;
82         unsigned int            divisor;
83         struct rcu_head         rcu;
84         /* 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];
88 };
89
90 struct tc_u_common {
91         struct tc_u_hnode __rcu *hlist;
92         struct Qdisc            *q;
93         int                     refcnt;
94         u32                     hgenerator;
95         struct rcu_head         rcu;
96 };
97
98 static inline unsigned int u32_hash_fold(__be32 key,
99                                          const struct tc_u32_sel *sel,
100                                          u8 fshift)
101 {
102         unsigned int h = ntohl(key & sel->hmask) >> fshift;
103
104         return h;
105 }
106
107 static int u32_classify(struct sk_buff *skb, const struct tcf_proto *tp,
108                         struct tcf_result *res)
109 {
110         struct {
111                 struct tc_u_knode *knode;
112                 unsigned int      off;
113         } stack[TC_U32_MAXDEPTH];
114
115         struct tc_u_hnode *ht = rcu_dereference_bh(tp->root);
116         unsigned int off = skb_network_offset(skb);
117         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
126 next_ht:
127         n = rcu_dereference_bh(ht->ht[sel]);
128
129 next_knode:
130         if (n) {
131                 struct tc_u32_key *key = n->sel.keys;
132
133 #ifdef CONFIG_CLS_U32_PERF
134                 __this_cpu_inc(n->pf->rcnt);
135                 j = 0;
136 #endif
137
138                 if (tc_skip_sw(n->flags)) {
139                         n = rcu_dereference_bh(n->next);
140                         goto next_knode;
141                 }
142
143 #ifdef CONFIG_CLS_U32_MARK
144                 if ((skb->mark & n->mask) != n->val) {
145                         n = rcu_dereference_bh(n->next);
146                         goto next_knode;
147                 } else {
148                         __this_cpu_inc(*n->pcpu_success);
149                 }
150 #endif
151
152                 for (i = n->sel.nkeys; i > 0; i--, key++) {
153                         int toff = off + key->off + (off2 & key->offmask);
154                         __be32 *data, hdata;
155
156                         if (skb_headroom(skb) + toff > INT_MAX)
157                                 goto out;
158
159                         data = skb_header_pointer(skb, toff, 4, &hdata);
160                         if (!data)
161                                 goto out;
162                         if ((*data ^ key->val) & key->mask) {
163                                 n = rcu_dereference_bh(n->next);
164                                 goto next_knode;
165                         }
166 #ifdef CONFIG_CLS_U32_PERF
167                         __this_cpu_inc(n->pf->kcnts[j]);
168                         j++;
169 #endif
170                 }
171
172                 ht = rcu_dereference_bh(n->ht_down);
173                 if (!ht) {
174 check_terminal:
175                         if (n->sel.flags & TC_U32_TERMINAL) {
176
177                                 *res = n->res;
178 #ifdef CONFIG_NET_CLS_IND
179                                 if (!tcf_match_indev(skb, n->ifindex)) {
180                                         n = rcu_dereference_bh(n->next);
181                                         goto next_knode;
182                                 }
183 #endif
184 #ifdef CONFIG_CLS_U32_PERF
185                                 __this_cpu_inc(n->pf->rhit);
186 #endif
187                                 r = tcf_exts_exec(skb, &n->exts, res);
188                                 if (r < 0) {
189                                         n = rcu_dereference_bh(n->next);
190                                         goto next_knode;
191                                 }
192
193                                 return r;
194                         }
195                         n = rcu_dereference_bh(n->next);
196                         goto next_knode;
197                 }
198
199                 /* PUSH */
200                 if (sdepth >= TC_U32_MAXDEPTH)
201                         goto deadloop;
202                 stack[sdepth].knode = n;
203                 stack[sdepth].off = off;
204                 sdepth++;
205
206                 ht = rcu_dereference_bh(n->ht_down);
207                 sel = 0;
208                 if (ht->divisor) {
209                         __be32 *data, hdata;
210
211                         data = skb_header_pointer(skb, off + n->sel.hoff, 4,
212                                                   &hdata);
213                         if (!data)
214                                 goto out;
215                         sel = ht->divisor & u32_hash_fold(*data, &n->sel,
216                                                           n->fshift);
217                 }
218                 if (!(n->sel.flags & (TC_U32_VAROFFSET | TC_U32_OFFSET | TC_U32_EAT)))
219                         goto next_ht;
220
221                 if (n->sel.flags & (TC_U32_OFFSET | TC_U32_VAROFFSET)) {
222                         off2 = n->sel.off + 3;
223                         if (n->sel.flags & TC_U32_VAROFFSET) {
224                                 __be16 *data, hdata;
225
226                                 data = skb_header_pointer(skb,
227                                                           off + n->sel.offoff,
228                                                           2, &hdata);
229                                 if (!data)
230                                         goto out;
231                                 off2 += ntohs(n->sel.offmask & *data) >>
232                                         n->sel.offshift;
233                         }
234                         off2 &= ~3;
235                 }
236                 if (n->sel.flags & TC_U32_EAT) {
237                         off += off2;
238                         off2 = 0;
239                 }
240
241                 if (off < skb->len)
242                         goto next_ht;
243         }
244
245         /* POP */
246         if (sdepth--) {
247                 n = stack[sdepth].knode;
248                 ht = rcu_dereference_bh(n->ht_up);
249                 off = stack[sdepth].off;
250                 goto check_terminal;
251         }
252 out:
253         return -1;
254
255 deadloop:
256         net_warn_ratelimited("cls_u32: dead loop\n");
257         return -1;
258 }
259
260 static struct tc_u_hnode *u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)
261 {
262         struct tc_u_hnode *ht;
263
264         for (ht = rtnl_dereference(tp_c->hlist);
265              ht;
266              ht = rtnl_dereference(ht->next))
267                 if (ht->handle == handle)
268                         break;
269
270         return ht;
271 }
272
273 static struct tc_u_knode *u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
274 {
275         unsigned int sel;
276         struct tc_u_knode *n = NULL;
277
278         sel = TC_U32_HASH(handle);
279         if (sel > ht->divisor)
280                 goto out;
281
282         for (n = rtnl_dereference(ht->ht[sel]);
283              n;
284              n = rtnl_dereference(n->next))
285                 if (n->handle == handle)
286                         break;
287 out:
288         return n;
289 }
290
291
292 static 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)
298                 ht = rtnl_dereference(tp->root);
299         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
311 static u32 gen_new_htid(struct tc_u_common *tp_c)
312 {
313         int i = 0x800;
314
315         /* hgenerator only used inside rtnl lock it is safe to increment
316          * without read _copy_ update semantics
317          */
318         do {
319                 if (++tp_c->hgenerator == 0x7FF)
320                         tp_c->hgenerator = 1;
321         } while (--i > 0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
322
323         return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
324 }
325
326 static int u32_init(struct tcf_proto *tp)
327 {
328         struct tc_u_hnode *root_ht;
329         struct tc_u_common *tp_c;
330
331         tp_c = tp->q->u32_node;
332
333         root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL);
334         if (root_ht == NULL)
335                 return -ENOBUFS;
336
337         root_ht->refcnt++;
338         root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;
339         root_ht->prio = tp->prio;
340
341         if (tp_c == NULL) {
342                 tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
343                 if (tp_c == NULL) {
344                         kfree(root_ht);
345                         return -ENOBUFS;
346                 }
347                 tp_c->q = tp->q;
348                 tp->q->u32_node = tp_c;
349         }
350
351         tp_c->refcnt++;
352         RCU_INIT_POINTER(root_ht->next, tp_c->hlist);
353         rcu_assign_pointer(tp_c->hlist, root_ht);
354         root_ht->tp_c = tp_c;
355
356         rcu_assign_pointer(tp->root, root_ht);
357         tp->data = tp_c;
358         return 0;
359 }
360
361 static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n,
362                            bool free_pf)
363 {
364         tcf_exts_destroy(&n->exts);
365         if (n->ht_down)
366                 n->ht_down->refcnt--;
367 #ifdef CONFIG_CLS_U32_PERF
368         if (free_pf)
369                 free_percpu(n->pf);
370 #endif
371 #ifdef CONFIG_CLS_U32_MARK
372         if (free_pf)
373                 free_percpu(n->pcpu_success);
374 #endif
375         kfree(n);
376         return 0;
377 }
378
379 /* u32_delete_key_rcu should be called when free'ing a copied
380  * version of a tc_u_knode obtained from u32_init_knode(). When
381  * copies are obtained from u32_init_knode() the statistics are
382  * shared between the old and new copies to allow readers to
383  * continue to update the statistics during the copy. To support
384  * this the u32_delete_key_rcu variant does not free the percpu
385  * statistics.
386  */
387 static void u32_delete_key_rcu(struct rcu_head *rcu)
388 {
389         struct tc_u_knode *key = container_of(rcu, struct tc_u_knode, rcu);
390
391         u32_destroy_key(key->tp, key, false);
392 }
393
394 /* u32_delete_key_freepf_rcu is the rcu callback variant
395  * that free's the entire structure including the statistics
396  * percpu variables. Only use this if the key is not a copy
397  * returned by u32_init_knode(). See u32_delete_key_rcu()
398  * for the variant that should be used with keys return from
399  * u32_init_knode()
400  */
401 static void u32_delete_key_freepf_rcu(struct rcu_head *rcu)
402 {
403         struct tc_u_knode *key = container_of(rcu, struct tc_u_knode, rcu);
404
405         u32_destroy_key(key->tp, key, true);
406 }
407
408 static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode *key)
409 {
410         struct tc_u_knode __rcu **kp;
411         struct tc_u_knode *pkp;
412         struct tc_u_hnode *ht = rtnl_dereference(key->ht_up);
413
414         if (ht) {
415                 kp = &ht->ht[TC_U32_HASH(key->handle)];
416                 for (pkp = rtnl_dereference(*kp); pkp;
417                      kp = &pkp->next, pkp = rtnl_dereference(*kp)) {
418                         if (pkp == key) {
419                                 RCU_INIT_POINTER(*kp, key->next);
420
421                                 tcf_unbind_filter(tp, &key->res);
422                                 call_rcu(&key->rcu, u32_delete_key_freepf_rcu);
423                                 return 0;
424                         }
425                 }
426         }
427         WARN_ON(1);
428         return 0;
429 }
430
431 static void u32_remove_hw_knode(struct tcf_proto *tp, u32 handle)
432 {
433         struct net_device *dev = tp->q->dev_queue->dev;
434         struct tc_cls_u32_offload u32_offload = {0};
435         struct tc_to_netdev offload;
436
437         offload.type = TC_SETUP_CLSU32;
438         offload.cls_u32 = &u32_offload;
439
440         if (tc_should_offload(dev, tp, 0)) {
441                 offload.cls_u32->command = TC_CLSU32_DELETE_KNODE;
442                 offload.cls_u32->knode.handle = handle;
443                 dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
444                                               tp->chain->index, tp->protocol,
445                                               &offload);
446         }
447 }
448
449 static int u32_replace_hw_hnode(struct tcf_proto *tp, struct tc_u_hnode *h,
450                                 u32 flags)
451 {
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;
455         int err;
456
457         if (!tc_should_offload(dev, tp, flags))
458                 return tc_skip_sw(flags) ? -EINVAL : 0;
459
460         offload.type = TC_SETUP_CLSU32;
461         offload.cls_u32 = &u32_offload;
462
463         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;
467
468         err = dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
469                                             tp->chain->index, tp->protocol,
470                                             &offload);
471         if (tc_skip_sw(flags))
472                 return err;
473
474         return 0;
475 }
476
477 static void u32_clear_hw_hnode(struct tcf_proto *tp, struct tc_u_hnode *h)
478 {
479         struct net_device *dev = tp->q->dev_queue->dev;
480         struct tc_cls_u32_offload u32_offload = {0};
481         struct tc_to_netdev offload;
482
483         offload.type = TC_SETUP_CLSU32;
484         offload.cls_u32 = &u32_offload;
485
486         if (tc_should_offload(dev, tp, 0)) {
487                 offload.cls_u32->command = TC_CLSU32_DELETE_HNODE;
488                 offload.cls_u32->hnode.divisor = h->divisor;
489                 offload.cls_u32->hnode.handle = h->handle;
490                 offload.cls_u32->hnode.prio = h->prio;
491
492                 dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
493                                               tp->chain->index, tp->protocol,
494                                               &offload);
495         }
496 }
497
498 static int u32_replace_hw_knode(struct tcf_proto *tp, struct tc_u_knode *n,
499                                 u32 flags)
500 {
501         struct net_device *dev = tp->q->dev_queue->dev;
502         struct tc_cls_u32_offload u32_offload = {0};
503         struct tc_to_netdev offload;
504         int err;
505
506         offload.type = TC_SETUP_CLSU32;
507         offload.cls_u32 = &u32_offload;
508
509         if (!tc_should_offload(dev, tp, flags))
510                 return tc_skip_sw(flags) ? -EINVAL : 0;
511
512         offload.cls_u32->command = TC_CLSU32_REPLACE_KNODE;
513         offload.cls_u32->knode.handle = n->handle;
514         offload.cls_u32->knode.fshift = n->fshift;
515 #ifdef CONFIG_CLS_U32_MARK
516         offload.cls_u32->knode.val = n->val;
517         offload.cls_u32->knode.mask = n->mask;
518 #else
519         offload.cls_u32->knode.val = 0;
520         offload.cls_u32->knode.mask = 0;
521 #endif
522         offload.cls_u32->knode.sel = &n->sel;
523         offload.cls_u32->knode.exts = &n->exts;
524         if (n->ht_down)
525                 offload.cls_u32->knode.link_handle = n->ht_down->handle;
526
527         err = dev->netdev_ops->ndo_setup_tc(dev, tp->q->handle,
528                                             tp->chain->index, tp->protocol,
529                                             &offload);
530
531         if (!err)
532                 n->flags |= TCA_CLS_FLAGS_IN_HW;
533
534         if (tc_skip_sw(flags))
535                 return err;
536
537         return 0;
538 }
539
540 static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
541 {
542         struct tc_u_knode *n;
543         unsigned int h;
544
545         for (h = 0; h <= ht->divisor; h++) {
546                 while ((n = rtnl_dereference(ht->ht[h])) != NULL) {
547                         RCU_INIT_POINTER(ht->ht[h],
548                                          rtnl_dereference(n->next));
549                         tcf_unbind_filter(tp, &n->res);
550                         u32_remove_hw_knode(tp, n->handle);
551                         call_rcu(&n->rcu, u32_delete_key_freepf_rcu);
552                 }
553         }
554 }
555
556 static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
557 {
558         struct tc_u_common *tp_c = tp->data;
559         struct tc_u_hnode __rcu **hn;
560         struct tc_u_hnode *phn;
561
562         WARN_ON(ht->refcnt);
563
564         u32_clear_hnode(tp, ht);
565
566         hn = &tp_c->hlist;
567         for (phn = rtnl_dereference(*hn);
568              phn;
569              hn = &phn->next, phn = rtnl_dereference(*hn)) {
570                 if (phn == ht) {
571                         u32_clear_hw_hnode(tp, ht);
572                         RCU_INIT_POINTER(*hn, ht->next);
573                         kfree_rcu(ht, rcu);
574                         return 0;
575                 }
576         }
577
578         return -ENOENT;
579 }
580
581 static bool ht_empty(struct tc_u_hnode *ht)
582 {
583         unsigned int h;
584
585         for (h = 0; h <= ht->divisor; h++)
586                 if (rcu_access_pointer(ht->ht[h]))
587                         return false;
588
589         return true;
590 }
591
592 static void u32_destroy(struct tcf_proto *tp)
593 {
594         struct tc_u_common *tp_c = tp->data;
595         struct tc_u_hnode *root_ht = rtnl_dereference(tp->root);
596
597         WARN_ON(root_ht == NULL);
598
599         if (root_ht && --root_ht->refcnt == 0)
600                 u32_destroy_hnode(tp, root_ht);
601
602         if (--tp_c->refcnt == 0) {
603                 struct tc_u_hnode *ht;
604
605                 tp->q->u32_node = NULL;
606
607                 for (ht = rtnl_dereference(tp_c->hlist);
608                      ht;
609                      ht = rtnl_dereference(ht->next)) {
610                         ht->refcnt--;
611                         u32_clear_hnode(tp, ht);
612                 }
613
614                 while ((ht = rtnl_dereference(tp_c->hlist)) != NULL) {
615                         RCU_INIT_POINTER(tp_c->hlist, ht->next);
616                         kfree_rcu(ht, rcu);
617                 }
618
619                 kfree(tp_c);
620         }
621
622         tp->data = NULL;
623 }
624
625 static int u32_delete(struct tcf_proto *tp, unsigned long arg, bool *last)
626 {
627         struct tc_u_hnode *ht = (struct tc_u_hnode *)arg;
628         struct tc_u_hnode *root_ht = rtnl_dereference(tp->root);
629         struct tc_u_common *tp_c = tp->data;
630         int ret = 0;
631
632         if (ht == NULL)
633                 goto out;
634
635         if (TC_U32_KEY(ht->handle)) {
636                 u32_remove_hw_knode(tp, ht->handle);
637                 ret = u32_delete_key(tp, (struct tc_u_knode *)ht);
638                 goto out;
639         }
640
641         if (root_ht == ht)
642                 return -EINVAL;
643
644         if (ht->refcnt == 1) {
645                 ht->refcnt--;
646                 u32_destroy_hnode(tp, ht);
647         } else {
648                 return -EBUSY;
649         }
650
651 out:
652         *last = true;
653         if (root_ht) {
654                 if (root_ht->refcnt > 1) {
655                         *last = false;
656                         goto ret;
657                 }
658                 if (root_ht->refcnt == 1) {
659                         if (!ht_empty(root_ht)) {
660                                 *last = false;
661                                 goto ret;
662                         }
663                 }
664         }
665
666         if (tp_c->refcnt > 1) {
667                 *last = false;
668                 goto ret;
669         }
670
671         if (tp_c->refcnt == 1) {
672                 struct tc_u_hnode *ht;
673
674                 for (ht = rtnl_dereference(tp_c->hlist);
675                      ht;
676                      ht = rtnl_dereference(ht->next))
677                         if (!ht_empty(ht)) {
678                                 *last = false;
679                                 break;
680                         }
681         }
682
683 ret:
684         return ret;
685 }
686
687 #define NR_U32_NODE (1<<12)
688 static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
689 {
690         struct tc_u_knode *n;
691         unsigned long i;
692         unsigned long *bitmap = kzalloc(BITS_TO_LONGS(NR_U32_NODE) * sizeof(unsigned long),
693                                         GFP_KERNEL);
694         if (!bitmap)
695                 return handle | 0xFFF;
696
697         for (n = rtnl_dereference(ht->ht[TC_U32_HASH(handle)]);
698              n;
699              n = rtnl_dereference(n->next))
700                 set_bit(TC_U32_NODE(n->handle), bitmap);
701
702         i = find_next_zero_bit(bitmap, NR_U32_NODE, 0x800);
703         if (i >= NR_U32_NODE)
704                 i = find_next_zero_bit(bitmap, NR_U32_NODE, 1);
705
706         kfree(bitmap);
707         return handle | (i >= NR_U32_NODE ? 0xFFF : i);
708 }
709
710 static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
711         [TCA_U32_CLASSID]       = { .type = NLA_U32 },
712         [TCA_U32_HASH]          = { .type = NLA_U32 },
713         [TCA_U32_LINK]          = { .type = NLA_U32 },
714         [TCA_U32_DIVISOR]       = { .type = NLA_U32 },
715         [TCA_U32_SEL]           = { .len = sizeof(struct tc_u32_sel) },
716         [TCA_U32_INDEV]         = { .type = NLA_STRING, .len = IFNAMSIZ },
717         [TCA_U32_MARK]          = { .len = sizeof(struct tc_u32_mark) },
718         [TCA_U32_FLAGS]         = { .type = NLA_U32 },
719 };
720
721 static int u32_set_parms(struct net *net, struct tcf_proto *tp,
722                          unsigned long base, struct tc_u_hnode *ht,
723                          struct tc_u_knode *n, struct nlattr **tb,
724                          struct nlattr *est, bool ovr)
725 {
726         struct tcf_exts e;
727         int err;
728
729         err = tcf_exts_init(&e, TCA_U32_ACT, TCA_U32_POLICE);
730         if (err < 0)
731                 return err;
732         err = tcf_exts_validate(net, tp, tb, est, &e, ovr);
733         if (err < 0)
734                 goto errout;
735
736         err = -EINVAL;
737         if (tb[TCA_U32_LINK]) {
738                 u32 handle = nla_get_u32(tb[TCA_U32_LINK]);
739                 struct tc_u_hnode *ht_down = NULL, *ht_old;
740
741                 if (TC_U32_KEY(handle))
742                         goto errout;
743
744                 if (handle) {
745                         ht_down = u32_lookup_ht(ht->tp_c, handle);
746
747                         if (ht_down == NULL)
748                                 goto errout;
749                         ht_down->refcnt++;
750                 }
751
752                 ht_old = rtnl_dereference(n->ht_down);
753                 rcu_assign_pointer(n->ht_down, ht_down);
754
755                 if (ht_old)
756                         ht_old->refcnt--;
757         }
758         if (tb[TCA_U32_CLASSID]) {
759                 n->res.classid = nla_get_u32(tb[TCA_U32_CLASSID]);
760                 tcf_bind_filter(tp, &n->res, base);
761         }
762
763 #ifdef CONFIG_NET_CLS_IND
764         if (tb[TCA_U32_INDEV]) {
765                 int ret;
766                 ret = tcf_change_indev(net, tb[TCA_U32_INDEV]);
767                 if (ret < 0)
768                         goto errout;
769                 n->ifindex = ret;
770         }
771 #endif
772         tcf_exts_change(tp, &n->exts, &e);
773
774         return 0;
775 errout:
776         tcf_exts_destroy(&e);
777         return err;
778 }
779
780 static void u32_replace_knode(struct tcf_proto *tp, struct tc_u_common *tp_c,
781                               struct tc_u_knode *n)
782 {
783         struct tc_u_knode __rcu **ins;
784         struct tc_u_knode *pins;
785         struct tc_u_hnode *ht;
786
787         if (TC_U32_HTID(n->handle) == TC_U32_ROOT)
788                 ht = rtnl_dereference(tp->root);
789         else
790                 ht = u32_lookup_ht(tp_c, TC_U32_HTID(n->handle));
791
792         ins = &ht->ht[TC_U32_HASH(n->handle)];
793
794         /* The node must always exist for it to be replaced if this is not the
795          * case then something went very wrong elsewhere.
796          */
797         for (pins = rtnl_dereference(*ins); ;
798              ins = &pins->next, pins = rtnl_dereference(*ins))
799                 if (pins->handle == n->handle)
800                         break;
801
802         RCU_INIT_POINTER(n->next, pins->next);
803         rcu_assign_pointer(*ins, n);
804 }
805
806 static struct tc_u_knode *u32_init_knode(struct tcf_proto *tp,
807                                          struct tc_u_knode *n)
808 {
809         struct tc_u_knode *new;
810         struct tc_u32_sel *s = &n->sel;
811
812         new = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key),
813                       GFP_KERNEL);
814
815         if (!new)
816                 return NULL;
817
818         RCU_INIT_POINTER(new->next, n->next);
819         new->handle = n->handle;
820         RCU_INIT_POINTER(new->ht_up, n->ht_up);
821
822 #ifdef CONFIG_NET_CLS_IND
823         new->ifindex = n->ifindex;
824 #endif
825         new->fshift = n->fshift;
826         new->res = n->res;
827         new->flags = n->flags;
828         RCU_INIT_POINTER(new->ht_down, n->ht_down);
829
830         /* bump reference count as long as we hold pointer to structure */
831         if (new->ht_down)
832                 new->ht_down->refcnt++;
833
834 #ifdef CONFIG_CLS_U32_PERF
835         /* Statistics may be incremented by readers during update
836          * so we must keep them in tact. When the node is later destroyed
837          * a special destroy call must be made to not free the pf memory.
838          */
839         new->pf = n->pf;
840 #endif
841
842 #ifdef CONFIG_CLS_U32_MARK
843         new->val = n->val;
844         new->mask = n->mask;
845         /* Similarly success statistics must be moved as pointers */
846         new->pcpu_success = n->pcpu_success;
847 #endif
848         new->tp = tp;
849         memcpy(&new->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
850
851         if (tcf_exts_init(&new->exts, TCA_U32_ACT, TCA_U32_POLICE)) {
852                 kfree(new);
853                 return NULL;
854         }
855
856         return new;
857 }
858
859 static int u32_change(struct net *net, struct sk_buff *in_skb,
860                       struct tcf_proto *tp, unsigned long base, u32 handle,
861                       struct nlattr **tca, unsigned long *arg, bool ovr)
862 {
863         struct tc_u_common *tp_c = tp->data;
864         struct tc_u_hnode *ht;
865         struct tc_u_knode *n;
866         struct tc_u32_sel *s;
867         struct nlattr *opt = tca[TCA_OPTIONS];
868         struct nlattr *tb[TCA_U32_MAX + 1];
869         u32 htid, flags = 0;
870         int err;
871 #ifdef CONFIG_CLS_U32_PERF
872         size_t size;
873 #endif
874
875         if (opt == NULL)
876                 return handle ? -EINVAL : 0;
877
878         err = nla_parse_nested(tb, TCA_U32_MAX, opt, u32_policy, NULL);
879         if (err < 0)
880                 return err;
881
882         if (tb[TCA_U32_FLAGS]) {
883                 flags = nla_get_u32(tb[TCA_U32_FLAGS]);
884                 if (!tc_flags_valid(flags))
885                         return -EINVAL;
886         }
887
888         n = (struct tc_u_knode *)*arg;
889         if (n) {
890                 struct tc_u_knode *new;
891
892                 if (TC_U32_KEY(n->handle) == 0)
893                         return -EINVAL;
894
895                 if (n->flags != flags)
896                         return -EINVAL;
897
898                 new = u32_init_knode(tp, n);
899                 if (!new)
900                         return -ENOMEM;
901
902                 err = u32_set_parms(net, tp, base,
903                                     rtnl_dereference(n->ht_up), new, tb,
904                                     tca[TCA_RATE], ovr);
905
906                 if (err) {
907                         u32_destroy_key(tp, new, false);
908                         return err;
909                 }
910
911                 err = u32_replace_hw_knode(tp, new, flags);
912                 if (err) {
913                         u32_destroy_key(tp, new, false);
914                         return err;
915                 }
916
917                 if (!tc_in_hw(new->flags))
918                         new->flags |= TCA_CLS_FLAGS_NOT_IN_HW;
919
920                 u32_replace_knode(tp, tp_c, new);
921                 tcf_unbind_filter(tp, &n->res);
922                 call_rcu(&n->rcu, u32_delete_key_rcu);
923                 return 0;
924         }
925
926         if (tb[TCA_U32_DIVISOR]) {
927                 unsigned int divisor = nla_get_u32(tb[TCA_U32_DIVISOR]);
928
929                 if (--divisor > 0x100)
930                         return -EINVAL;
931                 if (TC_U32_KEY(handle))
932                         return -EINVAL;
933                 if (handle == 0) {
934                         handle = gen_new_htid(tp->data);
935                         if (handle == 0)
936                                 return -ENOMEM;
937                 }
938                 ht = kzalloc(sizeof(*ht) + divisor*sizeof(void *), GFP_KERNEL);
939                 if (ht == NULL)
940                         return -ENOBUFS;
941                 ht->tp_c = tp_c;
942                 ht->refcnt = 1;
943                 ht->divisor = divisor;
944                 ht->handle = handle;
945                 ht->prio = tp->prio;
946
947                 err = u32_replace_hw_hnode(tp, ht, flags);
948                 if (err) {
949                         kfree(ht);
950                         return err;
951                 }
952
953                 RCU_INIT_POINTER(ht->next, tp_c->hlist);
954                 rcu_assign_pointer(tp_c->hlist, ht);
955                 *arg = (unsigned long)ht;
956
957                 return 0;
958         }
959
960         if (tb[TCA_U32_HASH]) {
961                 htid = nla_get_u32(tb[TCA_U32_HASH]);
962                 if (TC_U32_HTID(htid) == TC_U32_ROOT) {
963                         ht = rtnl_dereference(tp->root);
964                         htid = ht->handle;
965                 } else {
966                         ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));
967                         if (ht == NULL)
968                                 return -EINVAL;
969                 }
970         } else {
971                 ht = rtnl_dereference(tp->root);
972                 htid = ht->handle;
973         }
974
975         if (ht->divisor < TC_U32_HASH(htid))
976                 return -EINVAL;
977
978         if (handle) {
979                 if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
980                         return -EINVAL;
981                 handle = htid | TC_U32_NODE(handle);
982         } else
983                 handle = gen_new_kid(ht, htid);
984
985         if (tb[TCA_U32_SEL] == NULL)
986                 return -EINVAL;
987
988         s = nla_data(tb[TCA_U32_SEL]);
989
990         n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
991         if (n == NULL)
992                 return -ENOBUFS;
993
994 #ifdef CONFIG_CLS_U32_PERF
995         size = sizeof(struct tc_u32_pcnt) + s->nkeys * sizeof(u64);
996         n->pf = __alloc_percpu(size, __alignof__(struct tc_u32_pcnt));
997         if (!n->pf) {
998                 kfree(n);
999                 return -ENOBUFS;
1000         }
1001 #endif
1002
1003         memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
1004         RCU_INIT_POINTER(n->ht_up, ht);
1005         n->handle = handle;
1006         n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
1007         n->flags = flags;
1008         n->tp = tp;
1009
1010         err = tcf_exts_init(&n->exts, TCA_U32_ACT, TCA_U32_POLICE);
1011         if (err < 0)
1012                 goto errout;
1013
1014 #ifdef CONFIG_CLS_U32_MARK
1015         n->pcpu_success = alloc_percpu(u32);
1016         if (!n->pcpu_success) {
1017                 err = -ENOMEM;
1018                 goto errout;
1019         }
1020
1021         if (tb[TCA_U32_MARK]) {
1022                 struct tc_u32_mark *mark;
1023
1024                 mark = nla_data(tb[TCA_U32_MARK]);
1025                 n->val = mark->val;
1026                 n->mask = mark->mask;
1027         }
1028 #endif
1029
1030         err = u32_set_parms(net, tp, base, ht, n, tb, tca[TCA_RATE], ovr);
1031         if (err == 0) {
1032                 struct tc_u_knode __rcu **ins;
1033                 struct tc_u_knode *pins;
1034
1035                 err = u32_replace_hw_knode(tp, n, flags);
1036                 if (err)
1037                         goto errhw;
1038
1039                 if (!tc_in_hw(n->flags))
1040                         n->flags |= TCA_CLS_FLAGS_NOT_IN_HW;
1041
1042                 ins = &ht->ht[TC_U32_HASH(handle)];
1043                 for (pins = rtnl_dereference(*ins); pins;
1044                      ins = &pins->next, pins = rtnl_dereference(*ins))
1045                         if (TC_U32_NODE(handle) < TC_U32_NODE(pins->handle))
1046                                 break;
1047
1048                 RCU_INIT_POINTER(n->next, pins);
1049                 rcu_assign_pointer(*ins, n);
1050                 *arg = (unsigned long)n;
1051                 return 0;
1052         }
1053
1054 errhw:
1055 #ifdef CONFIG_CLS_U32_MARK
1056         free_percpu(n->pcpu_success);
1057 #endif
1058
1059 errout:
1060         tcf_exts_destroy(&n->exts);
1061 #ifdef CONFIG_CLS_U32_PERF
1062         free_percpu(n->pf);
1063 #endif
1064         kfree(n);
1065         return err;
1066 }
1067
1068 static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg)
1069 {
1070         struct tc_u_common *tp_c = tp->data;
1071         struct tc_u_hnode *ht;
1072         struct tc_u_knode *n;
1073         unsigned int h;
1074
1075         if (arg->stop)
1076                 return;
1077
1078         for (ht = rtnl_dereference(tp_c->hlist);
1079              ht;
1080              ht = rtnl_dereference(ht->next)) {
1081                 if (ht->prio != tp->prio)
1082                         continue;
1083                 if (arg->count >= arg->skip) {
1084                         if (arg->fn(tp, (unsigned long)ht, arg) < 0) {
1085                                 arg->stop = 1;
1086                                 return;
1087                         }
1088                 }
1089                 arg->count++;
1090                 for (h = 0; h <= ht->divisor; h++) {
1091                         for (n = rtnl_dereference(ht->ht[h]);
1092                              n;
1093                              n = rtnl_dereference(n->next)) {
1094                                 if (arg->count < arg->skip) {
1095                                         arg->count++;
1096                                         continue;
1097                                 }
1098                                 if (arg->fn(tp, (unsigned long)n, arg) < 0) {
1099                                         arg->stop = 1;
1100                                         return;
1101                                 }
1102                                 arg->count++;
1103                         }
1104                 }
1105         }
1106 }
1107
1108 static int u32_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
1109                     struct sk_buff *skb, struct tcmsg *t)
1110 {
1111         struct tc_u_knode *n = (struct tc_u_knode *)fh;
1112         struct tc_u_hnode *ht_up, *ht_down;
1113         struct nlattr *nest;
1114
1115         if (n == NULL)
1116                 return skb->len;
1117
1118         t->tcm_handle = n->handle;
1119
1120         nest = nla_nest_start(skb, TCA_OPTIONS);
1121         if (nest == NULL)
1122                 goto nla_put_failure;
1123
1124         if (TC_U32_KEY(n->handle) == 0) {
1125                 struct tc_u_hnode *ht = (struct tc_u_hnode *)fh;
1126                 u32 divisor = ht->divisor + 1;
1127
1128                 if (nla_put_u32(skb, TCA_U32_DIVISOR, divisor))
1129                         goto nla_put_failure;
1130         } else {
1131 #ifdef CONFIG_CLS_U32_PERF
1132                 struct tc_u32_pcnt *gpf;
1133                 int cpu;
1134 #endif
1135
1136                 if (nla_put(skb, TCA_U32_SEL,
1137                             sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
1138                             &n->sel))
1139                         goto nla_put_failure;
1140
1141                 ht_up = rtnl_dereference(n->ht_up);
1142                 if (ht_up) {
1143                         u32 htid = n->handle & 0xFFFFF000;
1144                         if (nla_put_u32(skb, TCA_U32_HASH, htid))
1145                                 goto nla_put_failure;
1146                 }
1147                 if (n->res.classid &&
1148                     nla_put_u32(skb, TCA_U32_CLASSID, n->res.classid))
1149                         goto nla_put_failure;
1150
1151                 ht_down = rtnl_dereference(n->ht_down);
1152                 if (ht_down &&
1153                     nla_put_u32(skb, TCA_U32_LINK, ht_down->handle))
1154                         goto nla_put_failure;
1155
1156                 if (n->flags && nla_put_u32(skb, TCA_U32_FLAGS, n->flags))
1157                         goto nla_put_failure;
1158
1159 #ifdef CONFIG_CLS_U32_MARK
1160                 if ((n->val || n->mask)) {
1161                         struct tc_u32_mark mark = {.val = n->val,
1162                                                    .mask = n->mask,
1163                                                    .success = 0};
1164                         int cpum;
1165
1166                         for_each_possible_cpu(cpum) {
1167                                 __u32 cnt = *per_cpu_ptr(n->pcpu_success, cpum);
1168
1169                                 mark.success += cnt;
1170                         }
1171
1172                         if (nla_put(skb, TCA_U32_MARK, sizeof(mark), &mark))
1173                                 goto nla_put_failure;
1174                 }
1175 #endif
1176
1177                 if (tcf_exts_dump(skb, &n->exts) < 0)
1178                         goto nla_put_failure;
1179
1180 #ifdef CONFIG_NET_CLS_IND
1181                 if (n->ifindex) {
1182                         struct net_device *dev;
1183                         dev = __dev_get_by_index(net, n->ifindex);
1184                         if (dev && nla_put_string(skb, TCA_U32_INDEV, dev->name))
1185                                 goto nla_put_failure;
1186                 }
1187 #endif
1188 #ifdef CONFIG_CLS_U32_PERF
1189                 gpf = kzalloc(sizeof(struct tc_u32_pcnt) +
1190                               n->sel.nkeys * sizeof(u64),
1191                               GFP_KERNEL);
1192                 if (!gpf)
1193                         goto nla_put_failure;
1194
1195                 for_each_possible_cpu(cpu) {
1196                         int i;
1197                         struct tc_u32_pcnt *pf = per_cpu_ptr(n->pf, cpu);
1198
1199                         gpf->rcnt += pf->rcnt;
1200                         gpf->rhit += pf->rhit;
1201                         for (i = 0; i < n->sel.nkeys; i++)
1202                                 gpf->kcnts[i] += pf->kcnts[i];
1203                 }
1204
1205                 if (nla_put_64bit(skb, TCA_U32_PCNT,
1206                                   sizeof(struct tc_u32_pcnt) +
1207                                   n->sel.nkeys * sizeof(u64),
1208                                   gpf, TCA_U32_PAD)) {
1209                         kfree(gpf);
1210                         goto nla_put_failure;
1211                 }
1212                 kfree(gpf);
1213 #endif
1214         }
1215
1216         nla_nest_end(skb, nest);
1217
1218         if (TC_U32_KEY(n->handle))
1219                 if (tcf_exts_dump_stats(skb, &n->exts) < 0)
1220                         goto nla_put_failure;
1221         return skb->len;
1222
1223 nla_put_failure:
1224         nla_nest_cancel(skb, nest);
1225         return -1;
1226 }
1227
1228 static struct tcf_proto_ops cls_u32_ops __read_mostly = {
1229         .kind           =       "u32",
1230         .classify       =       u32_classify,
1231         .init           =       u32_init,
1232         .destroy        =       u32_destroy,
1233         .get            =       u32_get,
1234         .change         =       u32_change,
1235         .delete         =       u32_delete,
1236         .walk           =       u32_walk,
1237         .dump           =       u32_dump,
1238         .owner          =       THIS_MODULE,
1239 };
1240
1241 static int __init init_u32(void)
1242 {
1243         pr_info("u32 classifier\n");
1244 #ifdef CONFIG_CLS_U32_PERF
1245         pr_info("    Performance counters on\n");
1246 #endif
1247 #ifdef CONFIG_NET_CLS_IND
1248         pr_info("    input device check on\n");
1249 #endif
1250 #ifdef CONFIG_NET_CLS_ACT
1251         pr_info("    Actions configured\n");
1252 #endif
1253         return register_tcf_proto_ops(&cls_u32_ops);
1254 }
1255
1256 static void __exit exit_u32(void)
1257 {
1258         unregister_tcf_proto_ops(&cls_u32_ops);
1259 }
1260
1261 module_init(init_u32)
1262 module_exit(exit_u32)
1263 MODULE_LICENSE("GPL");