1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#define VERSION "0.409"
52
53#include <asm/uaccess.h>
54#include <linux/bitops.h>
55#include <linux/types.h>
56#include <linux/kernel.h>
57#include <linux/mm.h>
58#include <linux/string.h>
59#include <linux/socket.h>
60#include <linux/sockios.h>
61#include <linux/errno.h>
62#include <linux/in.h>
63#include <linux/inet.h>
64#include <linux/inetdevice.h>
65#include <linux/netdevice.h>
66#include <linux/if_arp.h>
67#include <linux/proc_fs.h>
68#include <linux/rcupdate.h>
69#include <linux/skbuff.h>
70#include <linux/netlink.h>
71#include <linux/init.h>
72#include <linux/list.h>
73#include <linux/slab.h>
74#include <linux/export.h>
75#include <linux/vmalloc.h>
76#include <net/net_namespace.h>
77#include <net/ip.h>
78#include <net/protocol.h>
79#include <net/route.h>
80#include <net/tcp.h>
81#include <net/sock.h>
82#include <net/ip_fib.h>
83#include <net/switchdev.h>
84#include <trace/events/fib.h>
85#include "fib_lookup.h"
86
87#define MAX_STAT_DEPTH 32
88
89#define KEYLENGTH (8*sizeof(t_key))
90#define KEY_MAX ((t_key)~0)
91
92typedef unsigned int t_key;
93
94#define IS_TRIE(n) ((n)->pos >= KEYLENGTH)
95#define IS_TNODE(n) ((n)->bits)
96#define IS_LEAF(n) (!(n)->bits)
97
98struct key_vector {
99 t_key key;
100 unsigned char pos;
101 unsigned char bits;
102 unsigned char slen;
103 union {
104
105 struct hlist_head leaf;
106
107 struct key_vector __rcu *tnode[0];
108 };
109};
110
111struct tnode {
112 struct rcu_head rcu;
113 t_key empty_children;
114 t_key full_children;
115 struct key_vector __rcu *parent;
116 struct key_vector kv[1];
117#define tn_bits kv[0].bits
118};
119
120#define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n])
121#define LEAF_SIZE TNODE_SIZE(1)
122
123#ifdef CONFIG_IP_FIB_TRIE_STATS
124struct trie_use_stats {
125 unsigned int gets;
126 unsigned int backtrack;
127 unsigned int semantic_match_passed;
128 unsigned int semantic_match_miss;
129 unsigned int null_node_hit;
130 unsigned int resize_node_skipped;
131};
132#endif
133
134struct trie_stat {
135 unsigned int totdepth;
136 unsigned int maxdepth;
137 unsigned int tnodes;
138 unsigned int leaves;
139 unsigned int nullpointers;
140 unsigned int prefixes;
141 unsigned int nodesizes[MAX_STAT_DEPTH];
142};
143
144struct trie {
145 struct key_vector kv[1];
146#ifdef CONFIG_IP_FIB_TRIE_STATS
147 struct trie_use_stats __percpu *stats;
148#endif
149};
150
151static struct key_vector *resize(struct trie *t, struct key_vector *tn);
152static size_t tnode_free_size;
153
154
155
156
157
158
159static const int sync_pages = 128;
160
161static struct kmem_cache *fn_alias_kmem __read_mostly;
162static struct kmem_cache *trie_leaf_kmem __read_mostly;
163
164static inline struct tnode *tn_info(struct key_vector *kv)
165{
166 return container_of(kv, struct tnode, kv[0]);
167}
168
169
170#define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
171#define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
172
173
174#define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
175#define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
176
177
178static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
179{
180 if (n)
181 rcu_assign_pointer(tn_info(n)->parent, tp);
182}
183
184#define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)
185
186
187
188
189static inline unsigned long child_length(const struct key_vector *tn)
190{
191 return (1ul << tn->bits) & ~(1ul);
192}
193
194#define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
195
196static inline unsigned long get_index(t_key key, struct key_vector *kv)
197{
198 unsigned long index = key ^ kv->key;
199
200 if ((BITS_PER_LONG <= KEYLENGTH) && (KEYLENGTH == kv->pos))
201 return 0;
202
203 return index >> kv->pos;
204}
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265static const int halve_threshold = 25;
266static const int inflate_threshold = 50;
267static const int halve_threshold_root = 15;
268static const int inflate_threshold_root = 30;
269
270static void __alias_free_mem(struct rcu_head *head)
271{
272 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
273 kmem_cache_free(fn_alias_kmem, fa);
274}
275
276static inline void alias_free_mem_rcu(struct fib_alias *fa)
277{
278 call_rcu(&fa->rcu, __alias_free_mem);
279}
280
281#define TNODE_KMALLOC_MAX \
282 ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
283#define TNODE_VMALLOC_MAX \
284 ilog2((SIZE_MAX - TNODE_SIZE(0)) / sizeof(struct key_vector *))
285
286static void __node_free_rcu(struct rcu_head *head)
287{
288 struct tnode *n = container_of(head, struct tnode, rcu);
289
290 if (!n->tn_bits)
291 kmem_cache_free(trie_leaf_kmem, n);
292 else
293 kvfree(n);
294}
295
296#define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)
297
298static struct tnode *tnode_alloc(int bits)
299{
300 size_t size;
301
302
303 if (bits > TNODE_VMALLOC_MAX)
304 return NULL;
305
306
307 size = TNODE_SIZE(1ul << bits);
308
309 if (size <= PAGE_SIZE)
310 return kzalloc(size, GFP_KERNEL);
311 else
312 return vzalloc(size);
313}
314
315static inline void empty_child_inc(struct key_vector *n)
316{
317 ++tn_info(n)->empty_children ? : ++tn_info(n)->full_children;
318}
319
320static inline void empty_child_dec(struct key_vector *n)
321{
322 tn_info(n)->empty_children-- ? : tn_info(n)->full_children--;
323}
324
325static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
326{
327 struct key_vector *l;
328 struct tnode *kv;
329
330 kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
331 if (!kv)
332 return NULL;
333
334
335 l = kv->kv;
336 l->key = key;
337 l->pos = 0;
338 l->bits = 0;
339 l->slen = fa->fa_slen;
340
341
342 INIT_HLIST_HEAD(&l->leaf);
343 hlist_add_head(&fa->fa_list, &l->leaf);
344
345 return l;
346}
347
348static struct key_vector *tnode_new(t_key key, int pos, int bits)
349{
350 unsigned int shift = pos + bits;
351 struct key_vector *tn;
352 struct tnode *tnode;
353
354
355 BUG_ON(!bits || (shift > KEYLENGTH));
356
357 tnode = tnode_alloc(bits);
358 if (!tnode)
359 return NULL;
360
361 pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
362 sizeof(struct key_vector *) << bits);
363
364 if (bits == KEYLENGTH)
365 tnode->full_children = 1;
366 else
367 tnode->empty_children = 1ul << bits;
368
369 tn = tnode->kv;
370 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
371 tn->pos = pos;
372 tn->bits = bits;
373 tn->slen = pos;
374
375 return tn;
376}
377
378
379
380
381static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
382{
383 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
384}
385
386
387
388
389static void put_child(struct key_vector *tn, unsigned long i,
390 struct key_vector *n)
391{
392 struct key_vector *chi = get_child(tn, i);
393 int isfull, wasfull;
394
395 BUG_ON(i >= child_length(tn));
396
397
398 if (!n && chi)
399 empty_child_inc(tn);
400 if (n && !chi)
401 empty_child_dec(tn);
402
403
404 wasfull = tnode_full(tn, chi);
405 isfull = tnode_full(tn, n);
406
407 if (wasfull && !isfull)
408 tn_info(tn)->full_children--;
409 else if (!wasfull && isfull)
410 tn_info(tn)->full_children++;
411
412 if (n && (tn->slen < n->slen))
413 tn->slen = n->slen;
414
415 rcu_assign_pointer(tn->tnode[i], n);
416}
417
418static void update_children(struct key_vector *tn)
419{
420 unsigned long i;
421
422
423 for (i = child_length(tn); i;) {
424 struct key_vector *inode = get_child(tn, --i);
425
426 if (!inode)
427 continue;
428
429
430
431
432
433 if (node_parent(inode) == tn)
434 update_children(inode);
435 else
436 node_set_parent(inode, tn);
437 }
438}
439
440static inline void put_child_root(struct key_vector *tp, t_key key,
441 struct key_vector *n)
442{
443 if (IS_TRIE(tp))
444 rcu_assign_pointer(tp->tnode[0], n);
445 else
446 put_child(tp, get_index(key, tp), n);
447}
448
449static inline void tnode_free_init(struct key_vector *tn)
450{
451 tn_info(tn)->rcu.next = NULL;
452}
453
454static inline void tnode_free_append(struct key_vector *tn,
455 struct key_vector *n)
456{
457 tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
458 tn_info(tn)->rcu.next = &tn_info(n)->rcu;
459}
460
461static void tnode_free(struct key_vector *tn)
462{
463 struct callback_head *head = &tn_info(tn)->rcu;
464
465 while (head) {
466 head = head->next;
467 tnode_free_size += TNODE_SIZE(1ul << tn->bits);
468 node_free(tn);
469
470 tn = container_of(head, struct tnode, rcu)->kv;
471 }
472
473 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
474 tnode_free_size = 0;
475 synchronize_rcu();
476 }
477}
478
479static struct key_vector *replace(struct trie *t,
480 struct key_vector *oldtnode,
481 struct key_vector *tn)
482{
483 struct key_vector *tp = node_parent(oldtnode);
484 unsigned long i;
485
486
487 NODE_INIT_PARENT(tn, tp);
488 put_child_root(tp, tn->key, tn);
489
490
491 update_children(tn);
492
493
494 tnode_free(oldtnode);
495
496
497 for (i = child_length(tn); i;) {
498 struct key_vector *inode = get_child(tn, --i);
499
500
501 if (tnode_full(tn, inode))
502 tn = resize(t, inode);
503 }
504
505 return tp;
506}
507
508static struct key_vector *inflate(struct trie *t,
509 struct key_vector *oldtnode)
510{
511 struct key_vector *tn;
512 unsigned long i;
513 t_key m;
514
515 pr_debug("In inflate\n");
516
517 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
518 if (!tn)
519 goto notnode;
520
521
522 tnode_free_init(oldtnode);
523
524
525
526
527
528
529 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
530 struct key_vector *inode = get_child(oldtnode, --i);
531 struct key_vector *node0, *node1;
532 unsigned long j, k;
533
534
535 if (!inode)
536 continue;
537
538
539 if (!tnode_full(oldtnode, inode)) {
540 put_child(tn, get_index(inode->key, tn), inode);
541 continue;
542 }
543
544
545 tnode_free_append(oldtnode, inode);
546
547
548 if (inode->bits == 1) {
549 put_child(tn, 2 * i + 1, get_child(inode, 1));
550 put_child(tn, 2 * i, get_child(inode, 0));
551 continue;
552 }
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568 node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
569 if (!node1)
570 goto nomem;
571 node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
572
573 tnode_free_append(tn, node1);
574 if (!node0)
575 goto nomem;
576 tnode_free_append(tn, node0);
577
578
579 for (k = child_length(inode), j = k / 2; j;) {
580 put_child(node1, --j, get_child(inode, --k));
581 put_child(node0, j, get_child(inode, j));
582 put_child(node1, --j, get_child(inode, --k));
583 put_child(node0, j, get_child(inode, j));
584 }
585
586
587 NODE_INIT_PARENT(node1, tn);
588 NODE_INIT_PARENT(node0, tn);
589
590
591 put_child(tn, 2 * i + 1, node1);
592 put_child(tn, 2 * i, node0);
593 }
594
595
596 return replace(t, oldtnode, tn);
597nomem:
598
599 tnode_free(tn);
600notnode:
601 return NULL;
602}
603
604static struct key_vector *halve(struct trie *t,
605 struct key_vector *oldtnode)
606{
607 struct key_vector *tn;
608 unsigned long i;
609
610 pr_debug("In halve\n");
611
612 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
613 if (!tn)
614 goto notnode;
615
616
617 tnode_free_init(oldtnode);
618
619
620
621
622
623
624 for (i = child_length(oldtnode); i;) {
625 struct key_vector *node1 = get_child(oldtnode, --i);
626 struct key_vector *node0 = get_child(oldtnode, --i);
627 struct key_vector *inode;
628
629
630 if (!node1 || !node0) {
631 put_child(tn, i / 2, node1 ? : node0);
632 continue;
633 }
634
635
636 inode = tnode_new(node0->key, oldtnode->pos, 1);
637 if (!inode)
638 goto nomem;
639 tnode_free_append(tn, inode);
640
641
642 put_child(inode, 1, node1);
643 put_child(inode, 0, node0);
644 NODE_INIT_PARENT(inode, tn);
645
646
647 put_child(tn, i / 2, inode);
648 }
649
650
651 return replace(t, oldtnode, tn);
652nomem:
653
654 tnode_free(tn);
655notnode:
656 return NULL;
657}
658
659static struct key_vector *collapse(struct trie *t,
660 struct key_vector *oldtnode)
661{
662 struct key_vector *n, *tp;
663 unsigned long i;
664
665
666 for (n = NULL, i = child_length(oldtnode); !n && i;)
667 n = get_child(oldtnode, --i);
668
669
670 tp = node_parent(oldtnode);
671 put_child_root(tp, oldtnode->key, n);
672 node_set_parent(n, tp);
673
674
675 node_free(oldtnode);
676
677 return tp;
678}
679
680static unsigned char update_suffix(struct key_vector *tn)
681{
682 unsigned char slen = tn->pos;
683 unsigned long stride, i;
684
685
686
687
688
689
690 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
691 struct key_vector *n = get_child(tn, i);
692
693 if (!n || (n->slen <= slen))
694 continue;
695
696
697 stride <<= (n->slen - slen);
698 slen = n->slen;
699 i &= ~(stride - 1);
700
701
702
703
704
705
706 if ((slen + 1) >= (tn->pos + tn->bits))
707 break;
708 }
709
710 tn->slen = slen;
711
712 return slen;
713}
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
773{
774 unsigned long used = child_length(tn);
775 unsigned long threshold = used;
776
777
778 threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold;
779 used -= tn_info(tn)->empty_children;
780 used += tn_info(tn)->full_children;
781
782
783
784 return (used > 1) && tn->pos && ((50 * used) >= threshold);
785}
786
787static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
788{
789 unsigned long used = child_length(tn);
790 unsigned long threshold = used;
791
792
793 threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold;
794 used -= tn_info(tn)->empty_children;
795
796
797
798 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
799}
800
801static inline bool should_collapse(struct key_vector *tn)
802{
803 unsigned long used = child_length(tn);
804
805 used -= tn_info(tn)->empty_children;
806
807
808 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
809 used -= KEY_MAX;
810
811
812 return used < 2;
813}
814
815#define MAX_WORK 10
816static struct key_vector *resize(struct trie *t, struct key_vector *tn)
817{
818#ifdef CONFIG_IP_FIB_TRIE_STATS
819 struct trie_use_stats __percpu *stats = t->stats;
820#endif
821 struct key_vector *tp = node_parent(tn);
822 unsigned long cindex = get_index(tn->key, tp);
823 int max_work = MAX_WORK;
824
825 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
826 tn, inflate_threshold, halve_threshold);
827
828
829
830
831
832 BUG_ON(tn != get_child(tp, cindex));
833
834
835
836
837 while (should_inflate(tp, tn) && max_work) {
838 tp = inflate(t, tn);
839 if (!tp) {
840#ifdef CONFIG_IP_FIB_TRIE_STATS
841 this_cpu_inc(stats->resize_node_skipped);
842#endif
843 break;
844 }
845
846 max_work--;
847 tn = get_child(tp, cindex);
848 }
849
850
851 tp = node_parent(tn);
852
853
854 if (max_work != MAX_WORK)
855 return tp;
856
857
858
859
860 while (should_halve(tp, tn) && max_work) {
861 tp = halve(t, tn);
862 if (!tp) {
863#ifdef CONFIG_IP_FIB_TRIE_STATS
864 this_cpu_inc(stats->resize_node_skipped);
865#endif
866 break;
867 }
868
869 max_work--;
870 tn = get_child(tp, cindex);
871 }
872
873
874 if (should_collapse(tn))
875 return collapse(t, tn);
876
877
878 tp = node_parent(tn);
879
880
881 if (max_work != MAX_WORK)
882 return tp;
883
884
885 if (tn->slen > tn->pos) {
886 unsigned char slen = update_suffix(tn);
887
888 if (slen > tp->slen)
889 tp->slen = slen;
890 }
891
892 return tp;
893}
894
895static void leaf_pull_suffix(struct key_vector *tp, struct key_vector *l)
896{
897 while ((tp->slen > tp->pos) && (tp->slen > l->slen)) {
898 if (update_suffix(tp) > l->slen)
899 break;
900 tp = node_parent(tp);
901 }
902}
903
904static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)
905{
906
907
908
909 while (tn->slen < l->slen) {
910 tn->slen = l->slen;
911 tn = node_parent(tn);
912 }
913}
914
915
916static struct key_vector *fib_find_node(struct trie *t,
917 struct key_vector **tp, u32 key)
918{
919 struct key_vector *pn, *n = t->kv;
920 unsigned long index = 0;
921
922 do {
923 pn = n;
924 n = get_child_rcu(n, index);
925
926 if (!n)
927 break;
928
929 index = get_cindex(key, n);
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945 if (index >= (1ul << n->bits)) {
946 n = NULL;
947 break;
948 }
949
950
951 } while (IS_TNODE(n));
952
953 *tp = pn;
954
955 return n;
956}
957
958
959
960
961static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
962 u8 tos, u32 prio, u32 tb_id)
963{
964 struct fib_alias *fa;
965
966 if (!fah)
967 return NULL;
968
969 hlist_for_each_entry(fa, fah, fa_list) {
970 if (fa->fa_slen < slen)
971 continue;
972 if (fa->fa_slen != slen)
973 break;
974 if (fa->tb_id > tb_id)
975 continue;
976 if (fa->tb_id != tb_id)
977 break;
978 if (fa->fa_tos > tos)
979 continue;
980 if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos)
981 return fa;
982 }
983
984 return NULL;
985}
986
987static void trie_rebalance(struct trie *t, struct key_vector *tn)
988{
989 while (!IS_TRIE(tn))
990 tn = resize(t, tn);
991}
992
993static int fib_insert_node(struct trie *t, struct key_vector *tp,
994 struct fib_alias *new, t_key key)
995{
996 struct key_vector *n, *l;
997
998 l = leaf_new(key, new);
999 if (!l)
1000 goto noleaf;
1001
1002
1003 n = get_child(tp, get_index(key, tp));
1004
1005
1006
1007
1008
1009
1010
1011 if (n) {
1012 struct key_vector *tn;
1013
1014 tn = tnode_new(key, __fls(key ^ n->key), 1);
1015 if (!tn)
1016 goto notnode;
1017
1018
1019 NODE_INIT_PARENT(tn, tp);
1020 put_child(tn, get_index(key, tn) ^ 1, n);
1021
1022
1023 put_child_root(tp, key, tn);
1024 node_set_parent(n, tn);
1025
1026
1027 tp = tn;
1028 }
1029
1030
1031 NODE_INIT_PARENT(l, tp);
1032 put_child_root(tp, key, l);
1033 trie_rebalance(t, tp);
1034
1035 return 0;
1036notnode:
1037 node_free(l);
1038noleaf:
1039 return -ENOMEM;
1040}
1041
1042static int fib_insert_alias(struct trie *t, struct key_vector *tp,
1043 struct key_vector *l, struct fib_alias *new,
1044 struct fib_alias *fa, t_key key)
1045{
1046 if (!l)
1047 return fib_insert_node(t, tp, new, key);
1048
1049 if (fa) {
1050 hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
1051 } else {
1052 struct fib_alias *last;
1053
1054 hlist_for_each_entry(last, &l->leaf, fa_list) {
1055 if (new->fa_slen < last->fa_slen)
1056 break;
1057 if ((new->fa_slen == last->fa_slen) &&
1058 (new->tb_id > last->tb_id))
1059 break;
1060 fa = last;
1061 }
1062
1063 if (fa)
1064 hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
1065 else
1066 hlist_add_head_rcu(&new->fa_list, &l->leaf);
1067 }
1068
1069
1070 if (l->slen < new->fa_slen) {
1071 l->slen = new->fa_slen;
1072 leaf_push_suffix(tp, l);
1073 }
1074
1075 return 0;
1076}
1077
1078
1079int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1080{
1081 struct trie *t = (struct trie *)tb->tb_data;
1082 struct fib_alias *fa, *new_fa;
1083 struct key_vector *l, *tp;
1084 unsigned int nlflags = 0;
1085 struct fib_info *fi;
1086 u8 plen = cfg->fc_dst_len;
1087 u8 slen = KEYLENGTH - plen;
1088 u8 tos = cfg->fc_tos;
1089 u32 key;
1090 int err;
1091
1092 if (plen > KEYLENGTH)
1093 return -EINVAL;
1094
1095 key = ntohl(cfg->fc_dst);
1096
1097 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1098
1099 if ((plen < KEYLENGTH) && (key << plen))
1100 return -EINVAL;
1101
1102 fi = fib_create_info(cfg);
1103 if (IS_ERR(fi)) {
1104 err = PTR_ERR(fi);
1105 goto err;
1106 }
1107
1108 l = fib_find_node(t, &tp, key);
1109 fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,
1110 tb->tb_id) : NULL;
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121 if (fa && fa->fa_tos == tos &&
1122 fa->fa_info->fib_priority == fi->fib_priority) {
1123 struct fib_alias *fa_first, *fa_match;
1124
1125 err = -EEXIST;
1126 if (cfg->fc_nlflags & NLM_F_EXCL)
1127 goto out;
1128
1129
1130
1131
1132
1133
1134 fa_match = NULL;
1135 fa_first = fa;
1136 hlist_for_each_entry_from(fa, fa_list) {
1137 if ((fa->fa_slen != slen) ||
1138 (fa->tb_id != tb->tb_id) ||
1139 (fa->fa_tos != tos))
1140 break;
1141 if (fa->fa_info->fib_priority != fi->fib_priority)
1142 break;
1143 if (fa->fa_type == cfg->fc_type &&
1144 fa->fa_info == fi) {
1145 fa_match = fa;
1146 break;
1147 }
1148 }
1149
1150 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1151 struct fib_info *fi_drop;
1152 u8 state;
1153
1154 fa = fa_first;
1155 if (fa_match) {
1156 if (fa == fa_match)
1157 err = 0;
1158 goto out;
1159 }
1160 err = -ENOBUFS;
1161 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1162 if (!new_fa)
1163 goto out;
1164
1165 fi_drop = fa->fa_info;
1166 new_fa->fa_tos = fa->fa_tos;
1167 new_fa->fa_info = fi;
1168 new_fa->fa_type = cfg->fc_type;
1169 state = fa->fa_state;
1170 new_fa->fa_state = state & ~FA_S_ACCESSED;
1171 new_fa->fa_slen = fa->fa_slen;
1172 new_fa->tb_id = tb->tb_id;
1173 new_fa->fa_default = -1;
1174
1175 err = switchdev_fib_ipv4_add(key, plen, fi,
1176 new_fa->fa_tos,
1177 cfg->fc_type,
1178 cfg->fc_nlflags,
1179 tb->tb_id);
1180 if (err) {
1181 switchdev_fib_ipv4_abort(fi);
1182 kmem_cache_free(fn_alias_kmem, new_fa);
1183 goto out;
1184 }
1185
1186 hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1187
1188 alias_free_mem_rcu(fa);
1189
1190 fib_release_info(fi_drop);
1191 if (state & FA_S_ACCESSED)
1192 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1193 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1194 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1195
1196 goto succeeded;
1197 }
1198
1199
1200
1201
1202 if (fa_match)
1203 goto out;
1204
1205 if (cfg->fc_nlflags & NLM_F_APPEND)
1206 nlflags = NLM_F_APPEND;
1207 else
1208 fa = fa_first;
1209 }
1210 err = -ENOENT;
1211 if (!(cfg->fc_nlflags & NLM_F_CREATE))
1212 goto out;
1213
1214 err = -ENOBUFS;
1215 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1216 if (!new_fa)
1217 goto out;
1218
1219 new_fa->fa_info = fi;
1220 new_fa->fa_tos = tos;
1221 new_fa->fa_type = cfg->fc_type;
1222 new_fa->fa_state = 0;
1223 new_fa->fa_slen = slen;
1224 new_fa->tb_id = tb->tb_id;
1225 new_fa->fa_default = -1;
1226
1227
1228 err = switchdev_fib_ipv4_add(key, plen, fi, tos, cfg->fc_type,
1229 cfg->fc_nlflags, tb->tb_id);
1230 if (err) {
1231 switchdev_fib_ipv4_abort(fi);
1232 goto out_free_new_fa;
1233 }
1234
1235
1236 err = fib_insert_alias(t, tp, l, new_fa, fa, key);
1237 if (err)
1238 goto out_sw_fib_del;
1239
1240 if (!plen)
1241 tb->tb_num_default++;
1242
1243 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1244 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,
1245 &cfg->fc_nlinfo, nlflags);
1246succeeded:
1247 return 0;
1248
1249out_sw_fib_del:
1250 switchdev_fib_ipv4_del(key, plen, fi, tos, cfg->fc_type, tb->tb_id);
1251out_free_new_fa:
1252 kmem_cache_free(fn_alias_kmem, new_fa);
1253out:
1254 fib_release_info(fi);
1255err:
1256 return err;
1257}
1258
1259static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
1260{
1261 t_key prefix = n->key;
1262
1263 return (key ^ prefix) & (prefix | -prefix);
1264}
1265
1266
1267int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1268 struct fib_result *res, int fib_flags)
1269{
1270 struct trie *t = (struct trie *) tb->tb_data;
1271#ifdef CONFIG_IP_FIB_TRIE_STATS
1272 struct trie_use_stats __percpu *stats = t->stats;
1273#endif
1274 const t_key key = ntohl(flp->daddr);
1275 struct key_vector *n, *pn;
1276 struct fib_alias *fa;
1277 unsigned long index;
1278 t_key cindex;
1279
1280 trace_fib_table_lookup(tb->tb_id, flp);
1281
1282 pn = t->kv;
1283 cindex = 0;
1284
1285 n = get_child_rcu(pn, cindex);
1286 if (!n)
1287 return -EAGAIN;
1288
1289#ifdef CONFIG_IP_FIB_TRIE_STATS
1290 this_cpu_inc(stats->gets);
1291#endif
1292
1293
1294 for (;;) {
1295 index = get_cindex(key, n);
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311 if (index >= (1ul << n->bits))
1312 break;
1313
1314
1315 if (IS_LEAF(n))
1316 goto found;
1317
1318
1319
1320
1321 if (n->slen > n->pos) {
1322 pn = n;
1323 cindex = index;
1324 }
1325
1326 n = get_child_rcu(n, index);
1327 if (unlikely(!n))
1328 goto backtrace;
1329 }
1330
1331
1332 for (;;) {
1333
1334 struct key_vector __rcu **cptr = n->tnode;
1335
1336
1337
1338
1339
1340 if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
1341 goto backtrace;
1342
1343
1344 if (unlikely(IS_LEAF(n)))
1345 break;
1346
1347
1348
1349
1350
1351
1352 while ((n = rcu_dereference(*cptr)) == NULL) {
1353backtrace:
1354#ifdef CONFIG_IP_FIB_TRIE_STATS
1355 if (!n)
1356 this_cpu_inc(stats->null_node_hit);
1357#endif
1358
1359
1360
1361
1362
1363 while (!cindex) {
1364 t_key pkey = pn->key;
1365
1366
1367
1368
1369
1370 if (IS_TRIE(pn))
1371 return -EAGAIN;
1372#ifdef CONFIG_IP_FIB_TRIE_STATS
1373 this_cpu_inc(stats->backtrack);
1374#endif
1375
1376 pn = node_parent_rcu(pn);
1377 cindex = get_index(pkey, pn);
1378 }
1379
1380
1381 cindex &= cindex - 1;
1382
1383
1384 cptr = &pn->tnode[cindex];
1385 }
1386 }
1387
1388found:
1389
1390 index = key ^ n->key;
1391
1392
1393 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
1394 struct fib_info *fi = fa->fa_info;
1395 int nhsel, err;
1396
1397 if ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen < KEYLENGTH)) {
1398 if (index >= (1ul << fa->fa_slen))
1399 continue;
1400 }
1401 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1402 continue;
1403 if (fi->fib_dead)
1404 continue;
1405 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1406 continue;
1407 fib_alias_accessed(fa);
1408 err = fib_props[fa->fa_type].error;
1409 if (unlikely(err < 0)) {
1410#ifdef CONFIG_IP_FIB_TRIE_STATS
1411 this_cpu_inc(stats->semantic_match_passed);
1412#endif
1413 return err;
1414 }
1415 if (fi->fib_flags & RTNH_F_DEAD)
1416 continue;
1417 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1418 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1419 struct in_device *in_dev = __in_dev_get_rcu(nh->nh_dev);
1420
1421 if (nh->nh_flags & RTNH_F_DEAD)
1422 continue;
1423 if (in_dev &&
1424 IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&
1425 nh->nh_flags & RTNH_F_LINKDOWN &&
1426 !(fib_flags & FIB_LOOKUP_IGNORE_LINKSTATE))
1427 continue;
1428 if (!(flp->flowi4_flags & FLOWI_FLAG_SKIP_NH_OIF)) {
1429 if (flp->flowi4_oif &&
1430 flp->flowi4_oif != nh->nh_oif)
1431 continue;
1432 }
1433
1434 if (!(fib_flags & FIB_LOOKUP_NOREF))
1435 atomic_inc(&fi->fib_clntref);
1436
1437 res->prefixlen = KEYLENGTH - fa->fa_slen;
1438 res->nh_sel = nhsel;
1439 res->type = fa->fa_type;
1440 res->scope = fi->fib_scope;
1441 res->fi = fi;
1442 res->table = tb;
1443 res->fa_head = &n->leaf;
1444#ifdef CONFIG_IP_FIB_TRIE_STATS
1445 this_cpu_inc(stats->semantic_match_passed);
1446#endif
1447 trace_fib_table_lookup_nh(nh);
1448
1449 return err;
1450 }
1451 }
1452#ifdef CONFIG_IP_FIB_TRIE_STATS
1453 this_cpu_inc(stats->semantic_match_miss);
1454#endif
1455 goto backtrace;
1456}
1457EXPORT_SYMBOL_GPL(fib_table_lookup);
1458
1459static void fib_remove_alias(struct trie *t, struct key_vector *tp,
1460 struct key_vector *l, struct fib_alias *old)
1461{
1462
1463 struct hlist_node **pprev = old->fa_list.pprev;
1464 struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next);
1465
1466
1467 hlist_del_rcu(&old->fa_list);
1468
1469
1470
1471
1472 if (hlist_empty(&l->leaf)) {
1473 put_child_root(tp, l->key, NULL);
1474 node_free(l);
1475 trie_rebalance(t, tp);
1476 return;
1477 }
1478
1479
1480 if (*pprev)
1481 return;
1482
1483
1484 l->slen = fa->fa_slen;
1485 leaf_pull_suffix(tp, l);
1486}
1487
1488
1489int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1490{
1491 struct trie *t = (struct trie *) tb->tb_data;
1492 struct fib_alias *fa, *fa_to_delete;
1493 struct key_vector *l, *tp;
1494 u8 plen = cfg->fc_dst_len;
1495 u8 slen = KEYLENGTH - plen;
1496 u8 tos = cfg->fc_tos;
1497 u32 key;
1498
1499 if (plen > KEYLENGTH)
1500 return -EINVAL;
1501
1502 key = ntohl(cfg->fc_dst);
1503
1504 if ((plen < KEYLENGTH) && (key << plen))
1505 return -EINVAL;
1506
1507 l = fib_find_node(t, &tp, key);
1508 if (!l)
1509 return -ESRCH;
1510
1511 fa = fib_find_alias(&l->leaf, slen, tos, 0, tb->tb_id);
1512 if (!fa)
1513 return -ESRCH;
1514
1515 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1516
1517 fa_to_delete = NULL;
1518 hlist_for_each_entry_from(fa, fa_list) {
1519 struct fib_info *fi = fa->fa_info;
1520
1521 if ((fa->fa_slen != slen) ||
1522 (fa->tb_id != tb->tb_id) ||
1523 (fa->fa_tos != tos))
1524 break;
1525
1526 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1527 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1528 fa->fa_info->fib_scope == cfg->fc_scope) &&
1529 (!cfg->fc_prefsrc ||
1530 fi->fib_prefsrc == cfg->fc_prefsrc) &&
1531 (!cfg->fc_protocol ||
1532 fi->fib_protocol == cfg->fc_protocol) &&
1533 fib_nh_match(cfg, fi) == 0) {
1534 fa_to_delete = fa;
1535 break;
1536 }
1537 }
1538
1539 if (!fa_to_delete)
1540 return -ESRCH;
1541
1542 switchdev_fib_ipv4_del(key, plen, fa_to_delete->fa_info, tos,
1543 cfg->fc_type, tb->tb_id);
1544
1545 rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,
1546 &cfg->fc_nlinfo, 0);
1547
1548 if (!plen)
1549 tb->tb_num_default--;
1550
1551 fib_remove_alias(t, tp, l, fa_to_delete);
1552
1553 if (fa_to_delete->fa_state & FA_S_ACCESSED)
1554 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1555
1556 fib_release_info(fa_to_delete->fa_info);
1557 alias_free_mem_rcu(fa_to_delete);
1558 return 0;
1559}
1560
1561
1562static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
1563{
1564 struct key_vector *pn, *n = *tn;
1565 unsigned long cindex;
1566
1567
1568 do {
1569
1570 pn = n;
1571 cindex = (key > pn->key) ? get_index(key, pn) : 0;
1572
1573 if (cindex >> pn->bits)
1574 break;
1575
1576
1577 n = get_child_rcu(pn, cindex++);
1578 if (!n)
1579 break;
1580
1581
1582 if (IS_LEAF(n) && (n->key >= key))
1583 goto found;
1584 } while (IS_TNODE(n));
1585
1586
1587 while (!IS_TRIE(pn)) {
1588
1589 if (cindex >= (1ul << pn->bits)) {
1590 t_key pkey = pn->key;
1591
1592 pn = node_parent_rcu(pn);
1593 cindex = get_index(pkey, pn) + 1;
1594 continue;
1595 }
1596
1597
1598 n = get_child_rcu(pn, cindex++);
1599 if (!n)
1600 continue;
1601
1602
1603 if (IS_LEAF(n))
1604 goto found;
1605
1606
1607 pn = n;
1608 cindex = 0;
1609 }
1610
1611 *tn = pn;
1612 return NULL;
1613found:
1614
1615 *tn = pn;
1616 return n;
1617}
1618
1619static void fib_trie_free(struct fib_table *tb)
1620{
1621 struct trie *t = (struct trie *)tb->tb_data;
1622 struct key_vector *pn = t->kv;
1623 unsigned long cindex = 1;
1624 struct hlist_node *tmp;
1625 struct fib_alias *fa;
1626
1627
1628 for (;;) {
1629 struct key_vector *n;
1630
1631 if (!(cindex--)) {
1632 t_key pkey = pn->key;
1633
1634 if (IS_TRIE(pn))
1635 break;
1636
1637 n = pn;
1638 pn = node_parent(pn);
1639
1640
1641 put_child_root(pn, n->key, NULL);
1642 node_free(n);
1643
1644 cindex = get_index(pkey, pn);
1645
1646 continue;
1647 }
1648
1649
1650 n = get_child(pn, cindex);
1651 if (!n)
1652 continue;
1653
1654 if (IS_TNODE(n)) {
1655
1656 pn = n;
1657 cindex = 1ul << n->bits;
1658
1659 continue;
1660 }
1661
1662 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1663 hlist_del_rcu(&fa->fa_list);
1664 alias_free_mem_rcu(fa);
1665 }
1666
1667 put_child_root(pn, n->key, NULL);
1668 node_free(n);
1669 }
1670
1671#ifdef CONFIG_IP_FIB_TRIE_STATS
1672 free_percpu(t->stats);
1673#endif
1674 kfree(tb);
1675}
1676
1677struct fib_table *fib_trie_unmerge(struct fib_table *oldtb)
1678{
1679 struct trie *ot = (struct trie *)oldtb->tb_data;
1680 struct key_vector *l, *tp = ot->kv;
1681 struct fib_table *local_tb;
1682 struct fib_alias *fa;
1683 struct trie *lt;
1684 t_key key = 0;
1685
1686 if (oldtb->tb_data == oldtb->__data)
1687 return oldtb;
1688
1689 local_tb = fib_trie_table(RT_TABLE_LOCAL, NULL);
1690 if (!local_tb)
1691 return NULL;
1692
1693 lt = (struct trie *)local_tb->tb_data;
1694
1695 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
1696 struct key_vector *local_l = NULL, *local_tp;
1697
1698 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
1699 struct fib_alias *new_fa;
1700
1701 if (local_tb->tb_id != fa->tb_id)
1702 continue;
1703
1704
1705 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1706 if (!new_fa)
1707 goto out;
1708
1709 memcpy(new_fa, fa, sizeof(*fa));
1710
1711
1712 if (!local_l)
1713 local_l = fib_find_node(lt, &local_tp, l->key);
1714
1715 if (fib_insert_alias(lt, local_tp, local_l, new_fa,
1716 NULL, l->key))
1717 goto out;
1718 }
1719
1720
1721 key = l->key + 1;
1722 if (key < l->key)
1723 break;
1724 }
1725
1726 return local_tb;
1727out:
1728 fib_trie_free(local_tb);
1729
1730 return NULL;
1731}
1732
1733
1734void fib_table_flush_external(struct fib_table *tb)
1735{
1736 struct trie *t = (struct trie *)tb->tb_data;
1737 struct key_vector *pn = t->kv;
1738 unsigned long cindex = 1;
1739 struct hlist_node *tmp;
1740 struct fib_alias *fa;
1741
1742
1743 for (;;) {
1744 unsigned char slen = 0;
1745 struct key_vector *n;
1746
1747 if (!(cindex--)) {
1748 t_key pkey = pn->key;
1749
1750
1751 if (IS_TRIE(pn))
1752 break;
1753
1754
1755 pn = resize(t, pn);
1756 cindex = get_index(pkey, pn);
1757
1758 continue;
1759 }
1760
1761
1762 n = get_child(pn, cindex);
1763 if (!n)
1764 continue;
1765
1766 if (IS_TNODE(n)) {
1767
1768 pn = n;
1769 cindex = 1ul << n->bits;
1770
1771 continue;
1772 }
1773
1774 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1775 struct fib_info *fi = fa->fa_info;
1776
1777
1778
1779
1780 if (tb->tb_id != fa->tb_id) {
1781 hlist_del_rcu(&fa->fa_list);
1782 alias_free_mem_rcu(fa);
1783 continue;
1784 }
1785
1786
1787 slen = fa->fa_slen;
1788
1789 if (!fi || !(fi->fib_flags & RTNH_F_OFFLOAD))
1790 continue;
1791
1792 switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,
1793 fi, fa->fa_tos, fa->fa_type,
1794 tb->tb_id);
1795 }
1796
1797
1798 n->slen = slen;
1799
1800 if (hlist_empty(&n->leaf)) {
1801 put_child_root(pn, n->key, NULL);
1802 node_free(n);
1803 }
1804 }
1805}
1806
1807
1808int fib_table_flush(struct fib_table *tb)
1809{
1810 struct trie *t = (struct trie *)tb->tb_data;
1811 struct key_vector *pn = t->kv;
1812 unsigned long cindex = 1;
1813 struct hlist_node *tmp;
1814 struct fib_alias *fa;
1815 int found = 0;
1816
1817
1818 for (;;) {
1819 unsigned char slen = 0;
1820 struct key_vector *n;
1821
1822 if (!(cindex--)) {
1823 t_key pkey = pn->key;
1824
1825
1826 if (IS_TRIE(pn))
1827 break;
1828
1829
1830 pn = resize(t, pn);
1831 cindex = get_index(pkey, pn);
1832
1833 continue;
1834 }
1835
1836
1837 n = get_child(pn, cindex);
1838 if (!n)
1839 continue;
1840
1841 if (IS_TNODE(n)) {
1842
1843 pn = n;
1844 cindex = 1ul << n->bits;
1845
1846 continue;
1847 }
1848
1849 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1850 struct fib_info *fi = fa->fa_info;
1851
1852 if (!fi || !(fi->fib_flags & RTNH_F_DEAD)) {
1853 slen = fa->fa_slen;
1854 continue;
1855 }
1856
1857 switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,
1858 fi, fa->fa_tos, fa->fa_type,
1859 tb->tb_id);
1860 hlist_del_rcu(&fa->fa_list);
1861 fib_release_info(fa->fa_info);
1862 alias_free_mem_rcu(fa);
1863 found++;
1864 }
1865
1866
1867 n->slen = slen;
1868
1869 if (hlist_empty(&n->leaf)) {
1870 put_child_root(pn, n->key, NULL);
1871 node_free(n);
1872 }
1873 }
1874
1875 pr_debug("trie_flush found=%d\n", found);
1876 return found;
1877}
1878
1879static void __trie_free_rcu(struct rcu_head *head)
1880{
1881 struct fib_table *tb = container_of(head, struct fib_table, rcu);
1882#ifdef CONFIG_IP_FIB_TRIE_STATS
1883 struct trie *t = (struct trie *)tb->tb_data;
1884
1885 if (tb->tb_data == tb->__data)
1886 free_percpu(t->stats);
1887#endif
1888 kfree(tb);
1889}
1890
1891void fib_free_table(struct fib_table *tb)
1892{
1893 call_rcu(&tb->rcu, __trie_free_rcu);
1894}
1895
1896static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,
1897 struct sk_buff *skb, struct netlink_callback *cb)
1898{
1899 __be32 xkey = htonl(l->key);
1900 struct fib_alias *fa;
1901 int i, s_i;
1902
1903 s_i = cb->args[4];
1904 i = 0;
1905
1906
1907 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
1908 if (i < s_i) {
1909 i++;
1910 continue;
1911 }
1912
1913 if (tb->tb_id != fa->tb_id) {
1914 i++;
1915 continue;
1916 }
1917
1918 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1919 cb->nlh->nlmsg_seq,
1920 RTM_NEWROUTE,
1921 tb->tb_id,
1922 fa->fa_type,
1923 xkey,
1924 KEYLENGTH - fa->fa_slen,
1925 fa->fa_tos,
1926 fa->fa_info, NLM_F_MULTI) < 0) {
1927 cb->args[4] = i;
1928 return -1;
1929 }
1930 i++;
1931 }
1932
1933 cb->args[4] = i;
1934 return skb->len;
1935}
1936
1937
1938int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1939 struct netlink_callback *cb)
1940{
1941 struct trie *t = (struct trie *)tb->tb_data;
1942 struct key_vector *l, *tp = t->kv;
1943
1944
1945
1946 int count = cb->args[2];
1947 t_key key = cb->args[3];
1948
1949 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
1950 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1951 cb->args[3] = key;
1952 cb->args[2] = count;
1953 return -1;
1954 }
1955
1956 ++count;
1957 key = l->key + 1;
1958
1959 memset(&cb->args[4], 0,
1960 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1961
1962
1963 if (key < l->key)
1964 break;
1965 }
1966
1967 cb->args[3] = key;
1968 cb->args[2] = count;
1969
1970 return skb->len;
1971}
1972
1973void __init fib_trie_init(void)
1974{
1975 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1976 sizeof(struct fib_alias),
1977 0, SLAB_PANIC, NULL);
1978
1979 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1980 LEAF_SIZE,
1981 0, SLAB_PANIC, NULL);
1982}
1983
1984struct fib_table *fib_trie_table(u32 id, struct fib_table *alias)
1985{
1986 struct fib_table *tb;
1987 struct trie *t;
1988 size_t sz = sizeof(*tb);
1989
1990 if (!alias)
1991 sz += sizeof(struct trie);
1992
1993 tb = kzalloc(sz, GFP_KERNEL);
1994 if (!tb)
1995 return NULL;
1996
1997 tb->tb_id = id;
1998 tb->tb_num_default = 0;
1999 tb->tb_data = (alias ? alias->__data : tb->__data);
2000
2001 if (alias)
2002 return tb;
2003
2004 t = (struct trie *) tb->tb_data;
2005 t->kv[0].pos = KEYLENGTH;
2006 t->kv[0].slen = KEYLENGTH;
2007#ifdef CONFIG_IP_FIB_TRIE_STATS
2008 t->stats = alloc_percpu(struct trie_use_stats);
2009 if (!t->stats) {
2010 kfree(tb);
2011 tb = NULL;
2012 }
2013#endif
2014
2015 return tb;
2016}
2017
2018#ifdef CONFIG_PROC_FS
2019
2020struct fib_trie_iter {
2021 struct seq_net_private p;
2022 struct fib_table *tb;
2023 struct key_vector *tnode;
2024 unsigned int index;
2025 unsigned int depth;
2026};
2027
2028static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
2029{
2030 unsigned long cindex = iter->index;
2031 struct key_vector *pn = iter->tnode;
2032 t_key pkey;
2033
2034 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2035 iter->tnode, iter->index, iter->depth);
2036
2037 while (!IS_TRIE(pn)) {
2038 while (cindex < child_length(pn)) {
2039 struct key_vector *n = get_child_rcu(pn, cindex++);
2040
2041 if (!n)
2042 continue;
2043
2044 if (IS_LEAF(n)) {
2045 iter->tnode = pn;
2046 iter->index = cindex;
2047 } else {
2048
2049 iter->tnode = n;
2050 iter->index = 0;
2051 ++iter->depth;
2052 }
2053
2054 return n;
2055 }
2056
2057
2058 pkey = pn->key;
2059 pn = node_parent_rcu(pn);
2060 cindex = get_index(pkey, pn) + 1;
2061 --iter->depth;
2062 }
2063
2064
2065 iter->tnode = pn;
2066 iter->index = 0;
2067
2068 return NULL;
2069}
2070
2071static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
2072 struct trie *t)
2073{
2074 struct key_vector *n, *pn;
2075
2076 if (!t)
2077 return NULL;
2078
2079 pn = t->kv;
2080 n = rcu_dereference(pn->tnode[0]);
2081 if (!n)
2082 return NULL;
2083
2084 if (IS_TNODE(n)) {
2085 iter->tnode = n;
2086 iter->index = 0;
2087 iter->depth = 1;
2088 } else {
2089 iter->tnode = pn;
2090 iter->index = 0;
2091 iter->depth = 0;
2092 }
2093
2094 return n;
2095}
2096
2097static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2098{
2099 struct key_vector *n;
2100 struct fib_trie_iter iter;
2101
2102 memset(s, 0, sizeof(*s));
2103
2104 rcu_read_lock();
2105 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2106 if (IS_LEAF(n)) {
2107 struct fib_alias *fa;
2108
2109 s->leaves++;
2110 s->totdepth += iter.depth;
2111 if (iter.depth > s->maxdepth)
2112 s->maxdepth = iter.depth;
2113
2114 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)
2115 ++s->prefixes;
2116 } else {
2117 s->tnodes++;
2118 if (n->bits < MAX_STAT_DEPTH)
2119 s->nodesizes[n->bits]++;
2120 s->nullpointers += tn_info(n)->empty_children;
2121 }
2122 }
2123 rcu_read_unlock();
2124}
2125
2126
2127
2128
2129static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2130{
2131 unsigned int i, max, pointers, bytes, avdepth;
2132
2133 if (stat->leaves)
2134 avdepth = stat->totdepth*100 / stat->leaves;
2135 else
2136 avdepth = 0;
2137
2138 seq_printf(seq, "\tAver depth: %u.%02d\n",
2139 avdepth / 100, avdepth % 100);
2140 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
2141
2142 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
2143 bytes = LEAF_SIZE * stat->leaves;
2144
2145 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2146 bytes += sizeof(struct fib_alias) * stat->prefixes;
2147
2148 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2149 bytes += TNODE_SIZE(0) * stat->tnodes;
2150
2151 max = MAX_STAT_DEPTH;
2152 while (max > 0 && stat->nodesizes[max-1] == 0)
2153 max--;
2154
2155 pointers = 0;
2156 for (i = 1; i < max; i++)
2157 if (stat->nodesizes[i] != 0) {
2158 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
2159 pointers += (1<<i) * stat->nodesizes[i];
2160 }
2161 seq_putc(seq, '\n');
2162 seq_printf(seq, "\tPointers: %u\n", pointers);
2163
2164 bytes += sizeof(struct key_vector *) * pointers;
2165 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2166 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
2167}
2168
2169#ifdef CONFIG_IP_FIB_TRIE_STATS
2170static void trie_show_usage(struct seq_file *seq,
2171 const struct trie_use_stats __percpu *stats)
2172{
2173 struct trie_use_stats s = { 0 };
2174 int cpu;
2175
2176
2177 for_each_possible_cpu(cpu) {
2178 const struct trie_use_stats *pcpu = per_cpu_ptr(stats, cpu);
2179
2180 s.gets += pcpu->gets;
2181 s.backtrack += pcpu->backtrack;
2182 s.semantic_match_passed += pcpu->semantic_match_passed;
2183 s.semantic_match_miss += pcpu->semantic_match_miss;
2184 s.null_node_hit += pcpu->null_node_hit;
2185 s.resize_node_skipped += pcpu->resize_node_skipped;
2186 }
2187
2188 seq_printf(seq, "\nCounters:\n---------\n");
2189 seq_printf(seq, "gets = %u\n", s.gets);
2190 seq_printf(seq, "backtracks = %u\n", s.backtrack);
2191 seq_printf(seq, "semantic match passed = %u\n",
2192 s.semantic_match_passed);
2193 seq_printf(seq, "semantic match miss = %u\n", s.semantic_match_miss);
2194 seq_printf(seq, "null node hit= %u\n", s.null_node_hit);
2195 seq_printf(seq, "skipped node resize = %u\n\n", s.resize_node_skipped);
2196}
2197#endif
2198
2199static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2200{
2201 if (tb->tb_id == RT_TABLE_LOCAL)
2202 seq_puts(seq, "Local:\n");
2203 else if (tb->tb_id == RT_TABLE_MAIN)
2204 seq_puts(seq, "Main:\n");
2205 else
2206 seq_printf(seq, "Id %d:\n", tb->tb_id);
2207}
2208
2209
2210static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2211{
2212 struct net *net = (struct net *)seq->private;
2213 unsigned int h;
2214
2215 seq_printf(seq,
2216 "Basic info: size of leaf:"
2217 " %Zd bytes, size of tnode: %Zd bytes.\n",
2218 LEAF_SIZE, TNODE_SIZE(0));
2219
2220 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2221 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2222 struct fib_table *tb;
2223
2224 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2225 struct trie *t = (struct trie *) tb->tb_data;
2226 struct trie_stat stat;
2227
2228 if (!t)
2229 continue;
2230
2231 fib_table_print(seq, tb);
2232
2233 trie_collect_stats(t, &stat);
2234 trie_show_stats(seq, &stat);
2235#ifdef CONFIG_IP_FIB_TRIE_STATS
2236 trie_show_usage(seq, t->stats);
2237#endif
2238 }
2239 }
2240
2241 return 0;
2242}
2243
2244static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2245{
2246 return single_open_net(inode, file, fib_triestat_seq_show);
2247}
2248
2249static const struct file_operations fib_triestat_fops = {
2250 .owner = THIS_MODULE,
2251 .open = fib_triestat_seq_open,
2252 .read = seq_read,
2253 .llseek = seq_lseek,
2254 .release = single_release_net,
2255};
2256
2257static struct key_vector *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2258{
2259 struct fib_trie_iter *iter = seq->private;
2260 struct net *net = seq_file_net(seq);
2261 loff_t idx = 0;
2262 unsigned int h;
2263
2264 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2265 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2266 struct fib_table *tb;
2267
2268 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2269 struct key_vector *n;
2270
2271 for (n = fib_trie_get_first(iter,
2272 (struct trie *) tb->tb_data);
2273 n; n = fib_trie_get_next(iter))
2274 if (pos == idx++) {
2275 iter->tb = tb;
2276 return n;
2277 }
2278 }
2279 }
2280
2281 return NULL;
2282}
2283
2284static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2285 __acquires(RCU)
2286{
2287 rcu_read_lock();
2288 return fib_trie_get_idx(seq, *pos);
2289}
2290
2291static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2292{
2293 struct fib_trie_iter *iter = seq->private;
2294 struct net *net = seq_file_net(seq);
2295 struct fib_table *tb = iter->tb;
2296 struct hlist_node *tb_node;
2297 unsigned int h;
2298 struct key_vector *n;
2299
2300 ++*pos;
2301
2302 n = fib_trie_get_next(iter);
2303 if (n)
2304 return n;
2305
2306
2307 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2308 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2309 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2310 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2311 if (n)
2312 goto found;
2313 }
2314
2315
2316 while (++h < FIB_TABLE_HASHSZ) {
2317 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2318 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2319 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2320 if (n)
2321 goto found;
2322 }
2323 }
2324 return NULL;
2325
2326found:
2327 iter->tb = tb;
2328 return n;
2329}
2330
2331static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2332 __releases(RCU)
2333{
2334 rcu_read_unlock();
2335}
2336
2337static void seq_indent(struct seq_file *seq, int n)
2338{
2339 while (n-- > 0)
2340 seq_puts(seq, " ");
2341}
2342
2343static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2344{
2345 switch (s) {
2346 case RT_SCOPE_UNIVERSE: return "universe";
2347 case RT_SCOPE_SITE: return "site";
2348 case RT_SCOPE_LINK: return "link";
2349 case RT_SCOPE_HOST: return "host";
2350 case RT_SCOPE_NOWHERE: return "nowhere";
2351 default:
2352 snprintf(buf, len, "scope=%d", s);
2353 return buf;
2354 }
2355}
2356
2357static const char *const rtn_type_names[__RTN_MAX] = {
2358 [RTN_UNSPEC] = "UNSPEC",
2359 [RTN_UNICAST] = "UNICAST",
2360 [RTN_LOCAL] = "LOCAL",
2361 [RTN_BROADCAST] = "BROADCAST",
2362 [RTN_ANYCAST] = "ANYCAST",
2363 [RTN_MULTICAST] = "MULTICAST",
2364 [RTN_BLACKHOLE] = "BLACKHOLE",
2365 [RTN_UNREACHABLE] = "UNREACHABLE",
2366 [RTN_PROHIBIT] = "PROHIBIT",
2367 [RTN_THROW] = "THROW",
2368 [RTN_NAT] = "NAT",
2369 [RTN_XRESOLVE] = "XRESOLVE",
2370};
2371
2372static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2373{
2374 if (t < __RTN_MAX && rtn_type_names[t])
2375 return rtn_type_names[t];
2376 snprintf(buf, len, "type %u", t);
2377 return buf;
2378}
2379
2380
2381static int fib_trie_seq_show(struct seq_file *seq, void *v)
2382{
2383 const struct fib_trie_iter *iter = seq->private;
2384 struct key_vector *n = v;
2385
2386 if (IS_TRIE(node_parent_rcu(n)))
2387 fib_table_print(seq, iter->tb);
2388
2389 if (IS_TNODE(n)) {
2390 __be32 prf = htonl(n->key);
2391
2392 seq_indent(seq, iter->depth-1);
2393 seq_printf(seq, " +-- %pI4/%zu %u %u %u\n",
2394 &prf, KEYLENGTH - n->pos - n->bits, n->bits,
2395 tn_info(n)->full_children,
2396 tn_info(n)->empty_children);
2397 } else {
2398 __be32 val = htonl(n->key);
2399 struct fib_alias *fa;
2400
2401 seq_indent(seq, iter->depth);
2402 seq_printf(seq, " |-- %pI4\n", &val);
2403
2404 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
2405 char buf1[32], buf2[32];
2406
2407 seq_indent(seq, iter->depth + 1);
2408 seq_printf(seq, " /%zu %s %s",
2409 KEYLENGTH - fa->fa_slen,
2410 rtn_scope(buf1, sizeof(buf1),
2411 fa->fa_info->fib_scope),
2412 rtn_type(buf2, sizeof(buf2),
2413 fa->fa_type));
2414 if (fa->fa_tos)
2415 seq_printf(seq, " tos=%d", fa->fa_tos);
2416 seq_putc(seq, '\n');
2417 }
2418 }
2419
2420 return 0;
2421}
2422
2423static const struct seq_operations fib_trie_seq_ops = {
2424 .start = fib_trie_seq_start,
2425 .next = fib_trie_seq_next,
2426 .stop = fib_trie_seq_stop,
2427 .show = fib_trie_seq_show,
2428};
2429
2430static int fib_trie_seq_open(struct inode *inode, struct file *file)
2431{
2432 return seq_open_net(inode, file, &fib_trie_seq_ops,
2433 sizeof(struct fib_trie_iter));
2434}
2435
2436static const struct file_operations fib_trie_fops = {
2437 .owner = THIS_MODULE,
2438 .open = fib_trie_seq_open,
2439 .read = seq_read,
2440 .llseek = seq_lseek,
2441 .release = seq_release_net,
2442};
2443
2444struct fib_route_iter {
2445 struct seq_net_private p;
2446 struct fib_table *main_tb;
2447 struct key_vector *tnode;
2448 loff_t pos;
2449 t_key key;
2450};
2451
2452static struct key_vector *fib_route_get_idx(struct fib_route_iter *iter,
2453 loff_t pos)
2454{
2455 struct fib_table *tb = iter->main_tb;
2456 struct key_vector *l, **tp = &iter->tnode;
2457 struct trie *t;
2458 t_key key;
2459
2460
2461 if (iter->pos > 0 && pos >= iter->pos) {
2462 pos -= iter->pos;
2463 key = iter->key;
2464 } else {
2465 t = (struct trie *)tb->tb_data;
2466 iter->tnode = t->kv;
2467 iter->pos = 0;
2468 key = 0;
2469 }
2470
2471 while ((l = leaf_walk_rcu(tp, key)) != NULL) {
2472 key = l->key + 1;
2473 iter->pos++;
2474
2475 if (--pos <= 0)
2476 break;
2477
2478 l = NULL;
2479
2480
2481 if (!key)
2482 break;
2483 }
2484
2485 if (l)
2486 iter->key = key;
2487 else
2488 iter->pos = 0;
2489
2490 return l;
2491}
2492
2493static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2494 __acquires(RCU)
2495{
2496 struct fib_route_iter *iter = seq->private;
2497 struct fib_table *tb;
2498 struct trie *t;
2499
2500 rcu_read_lock();
2501
2502 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2503 if (!tb)
2504 return NULL;
2505
2506 iter->main_tb = tb;
2507
2508 if (*pos != 0)
2509 return fib_route_get_idx(iter, *pos);
2510
2511 t = (struct trie *)tb->tb_data;
2512 iter->tnode = t->kv;
2513 iter->pos = 0;
2514 iter->key = 0;
2515
2516 return SEQ_START_TOKEN;
2517}
2518
2519static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2520{
2521 struct fib_route_iter *iter = seq->private;
2522 struct key_vector *l = NULL;
2523 t_key key = iter->key;
2524
2525 ++*pos;
2526
2527
2528 if ((v == SEQ_START_TOKEN) || key)
2529 l = leaf_walk_rcu(&iter->tnode, key);
2530
2531 if (l) {
2532 iter->key = l->key + 1;
2533 iter->pos++;
2534 } else {
2535 iter->pos = 0;
2536 }
2537
2538 return l;
2539}
2540
2541static void fib_route_seq_stop(struct seq_file *seq, void *v)
2542 __releases(RCU)
2543{
2544 rcu_read_unlock();
2545}
2546
2547static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2548{
2549 unsigned int flags = 0;
2550
2551 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2552 flags = RTF_REJECT;
2553 if (fi && fi->fib_nh->nh_gw)
2554 flags |= RTF_GATEWAY;
2555 if (mask == htonl(0xFFFFFFFF))
2556 flags |= RTF_HOST;
2557 flags |= RTF_UP;
2558 return flags;
2559}
2560
2561
2562
2563
2564
2565
2566
2567static int fib_route_seq_show(struct seq_file *seq, void *v)
2568{
2569 struct fib_route_iter *iter = seq->private;
2570 struct fib_table *tb = iter->main_tb;
2571 struct fib_alias *fa;
2572 struct key_vector *l = v;
2573 __be32 prefix;
2574
2575 if (v == SEQ_START_TOKEN) {
2576 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2577 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2578 "\tWindow\tIRTT");
2579 return 0;
2580 }
2581
2582 prefix = htonl(l->key);
2583
2584 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
2585 const struct fib_info *fi = fa->fa_info;
2586 __be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen);
2587 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2588
2589 if ((fa->fa_type == RTN_BROADCAST) ||
2590 (fa->fa_type == RTN_MULTICAST))
2591 continue;
2592
2593 if (fa->tb_id != tb->tb_id)
2594 continue;
2595
2596 seq_setwidth(seq, 127);
2597
2598 if (fi)
2599 seq_printf(seq,
2600 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2601 "%d\t%08X\t%d\t%u\t%u",
2602 fi->fib_dev ? fi->fib_dev->name : "*",
2603 prefix,
2604 fi->fib_nh->nh_gw, flags, 0, 0,
2605 fi->fib_priority,
2606 mask,
2607 (fi->fib_advmss ?
2608 fi->fib_advmss + 40 : 0),
2609 fi->fib_window,
2610 fi->fib_rtt >> 3);
2611 else
2612 seq_printf(seq,
2613 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2614 "%d\t%08X\t%d\t%u\t%u",
2615 prefix, 0, flags, 0, 0, 0,
2616 mask, 0, 0, 0);
2617
2618 seq_pad(seq, '\n');
2619 }
2620
2621 return 0;
2622}
2623
2624static const struct seq_operations fib_route_seq_ops = {
2625 .start = fib_route_seq_start,
2626 .next = fib_route_seq_next,
2627 .stop = fib_route_seq_stop,
2628 .show = fib_route_seq_show,
2629};
2630
2631static int fib_route_seq_open(struct inode *inode, struct file *file)
2632{
2633 return seq_open_net(inode, file, &fib_route_seq_ops,
2634 sizeof(struct fib_route_iter));
2635}
2636
2637static const struct file_operations fib_route_fops = {
2638 .owner = THIS_MODULE,
2639 .open = fib_route_seq_open,
2640 .read = seq_read,
2641 .llseek = seq_lseek,
2642 .release = seq_release_net,
2643};
2644
2645int __net_init fib_proc_init(struct net *net)
2646{
2647 if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2648 goto out1;
2649
2650 if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2651 &fib_triestat_fops))
2652 goto out2;
2653
2654 if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2655 goto out3;
2656
2657 return 0;
2658
2659out3:
2660 remove_proc_entry("fib_triestat", net->proc_net);
2661out2:
2662 remove_proc_entry("fib_trie", net->proc_net);
2663out1:
2664 return -ENOMEM;
2665}
2666
2667void __net_exit fib_proc_exit(struct net *net)
2668{
2669 remove_proc_entry("fib_trie", net->proc_net);
2670 remove_proc_entry("fib_triestat", net->proc_net);
2671 remove_proc_entry("route", net->proc_net);
2672}
2673
2674#endif
2675