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