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