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