This source file includes following definitions.
- rt_logmask
- rt_mask
- fz_hash_code
- fib_free_node
- fib_lookup_gateway
- fib_lookup_local
- fib_lookup
- get_gw_dev
- default_mask
- guess_mask
- bad_mask
- fib_del_list
- fib_del_1
- fib_create_info
- fib_add_1
- rt_flush_list
- fib_flush_1
- rt_get_info
- rt_cache_get_info
- rt_free
- rt_kick_free_queue
- ip_rt_run_bh
- ip_rt_check_expire
- rt_redirect_1
- rt_cache_flush
- rt_garbage_collect_1
- rt_req_enqueue
- rt_req_dequeue
- rt_kick_backlog
- rt_del
- rt_add
- ip_rt_flush
- ip_rt_redirect
- rt_garbage_collect
- rt_cache_add
- ip_rt_slow_route
- ip_rt_put
- ip_rt_route
- ip_rt_new
- rt_kill
- ip_rt_ioctl
- ip_rt_advice
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 #include <linux/config.h>
48 #include <asm/segment.h>
49 #include <asm/system.h>
50 #include <asm/bitops.h>
51 #include <linux/types.h>
52 #include <linux/kernel.h>
53 #include <linux/sched.h>
54 #include <linux/mm.h>
55 #include <linux/string.h>
56 #include <linux/socket.h>
57 #include <linux/sockios.h>
58 #include <linux/errno.h>
59 #include <linux/in.h>
60 #include <linux/inet.h>
61 #include <linux/netdevice.h>
62 #include <net/ip.h>
63 #include <net/protocol.h>
64 #include <net/route.h>
65 #include <net/tcp.h>
66 #include <linux/skbuff.h>
67 #include <net/sock.h>
68 #include <net/icmp.h>
69 #include <net/netlink.h>
70
71
72
73
74
75 struct fib_node
76 {
77 struct fib_node *fib_next;
78 __u32 fib_dst;
79 unsigned long fib_use;
80 struct fib_info *fib_info;
81 short fib_metric;
82 unsigned char fib_tos;
83 };
84
85
86
87
88
89 struct fib_info
90 {
91 struct fib_info *fib_next;
92 struct fib_info *fib_prev;
93 __u32 fib_gateway;
94 struct device *fib_dev;
95 int fib_refcnt;
96 unsigned long fib_window;
97 unsigned short fib_flags;
98 unsigned short fib_mtu;
99 unsigned short fib_irtt;
100 };
101
102 struct fib_zone
103 {
104 struct fib_zone *fz_next;
105 struct fib_node **fz_hash_table;
106 struct fib_node *fz_list;
107 int fz_nent;
108 int fz_logmask;
109 __u32 fz_mask;
110 };
111
112 static struct fib_zone *fib_zones[33];
113 static struct fib_zone *fib_zone_list;
114 static struct fib_node *fib_loopback = NULL;
115 static struct fib_info *fib_info_list;
116
117
118
119
120
121 #define RT_BH_REDIRECT 0
122 #define RT_BH_GARBAGE_COLLECT 1
123 #define RT_BH_FREE 2
124
125 struct rt_req
126 {
127 struct rt_req * rtr_next;
128 struct device *dev;
129 __u32 dst;
130 __u32 gw;
131 unsigned char tos;
132 };
133
134 int ip_rt_lock;
135 unsigned ip_rt_bh_mask;
136 static struct rt_req *rt_backlog;
137
138
139
140
141
142 struct rtable *ip_rt_hash_table[RT_HASH_DIVISOR];
143 static int rt_cache_size;
144 static struct rtable *rt_free_queue;
145 struct wait_queue *rt_wait;
146
147 static void rt_kick_backlog(void);
148 static void rt_cache_add(unsigned hash, struct rtable * rth);
149 static void rt_cache_flush(void);
150 static void rt_garbage_collect_1(void);
151
152
153
154
155
156 static __inline__ int rt_logmask(__u32 mask)
157 {
158 if (!(mask = ntohl(mask)))
159 return 32;
160 return ffz(~mask);
161 }
162
163
164
165
166
167 static __inline__ __u32 rt_mask(int logmask)
168 {
169 if (logmask >= 32)
170 return 0;
171 return htonl(~((1<<logmask)-1));
172 }
173
174 static __inline__ unsigned fz_hash_code(__u32 dst, int logmask)
175 {
176 return ip_rt_hash_code(ntohl(dst)>>logmask);
177 }
178
179
180
181
182
183 static void fib_free_node(struct fib_node * f)
184 {
185 struct fib_info * fi = f->fib_info;
186 if (!--fi->fib_refcnt)
187 {
188 #if RT_CACHE_DEBUG >= 2
189 printk("fib_free_node: fi %08x/%s is free\n", fi->fib_gateway, fi->fib_dev->name);
190 #endif
191 if (fi->fib_next)
192 fi->fib_next->fib_prev = fi->fib_prev;
193 if (fi->fib_prev)
194 fi->fib_prev->fib_next = fi->fib_next;
195 if (fi == fib_info_list)
196 fib_info_list = fi->fib_next;
197 }
198 kfree_s(f, sizeof(struct fib_node));
199 }
200
201
202
203
204
205 static struct fib_node * fib_lookup_gateway(__u32 dst)
206 {
207 struct fib_zone * fz;
208 struct fib_node * f;
209
210 for (fz = fib_zone_list; fz; fz = fz->fz_next)
211 {
212 if (fz->fz_hash_table)
213 f = fz->fz_hash_table[fz_hash_code(dst, fz->fz_logmask)];
214 else
215 f = fz->fz_list;
216
217 for ( ; f; f = f->fib_next)
218 {
219 if ((dst ^ f->fib_dst) & fz->fz_mask)
220 continue;
221 if (f->fib_info->fib_flags & RTF_GATEWAY)
222 return NULL;
223 return f;
224 }
225 }
226 return NULL;
227 }
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243 static struct fib_node * fib_lookup_local(__u32 dst)
244 {
245 struct fib_zone * fz;
246 struct fib_node * f;
247
248 for (fz = fib_zone_list; fz; fz = fz->fz_next)
249 {
250 int longest_match_found = 0;
251
252 if (fz->fz_hash_table)
253 f = fz->fz_hash_table[fz_hash_code(dst, fz->fz_logmask)];
254 else
255 f = fz->fz_list;
256
257 for ( ; f; f = f->fib_next)
258 {
259 if ((dst ^ f->fib_dst) & fz->fz_mask)
260 continue;
261 if (!(f->fib_info->fib_flags & RTF_GATEWAY))
262 return f;
263 longest_match_found = 1;
264 }
265 if (longest_match_found)
266 return NULL;
267 }
268 return NULL;
269 }
270
271
272
273
274
275
276
277
278
279
280
281
282
283 static struct fib_node * fib_lookup(__u32 dst)
284 {
285 struct fib_zone * fz;
286 struct fib_node * f;
287
288 for (fz = fib_zone_list; fz; fz = fz->fz_next)
289 {
290 if (fz->fz_hash_table)
291 f = fz->fz_hash_table[fz_hash_code(dst, fz->fz_logmask)];
292 else
293 f = fz->fz_list;
294
295 for ( ; f; f = f->fib_next)
296 {
297 if ((dst ^ f->fib_dst) & fz->fz_mask)
298 continue;
299 return f;
300 }
301 }
302 return NULL;
303 }
304
305 static __inline__ struct device * get_gw_dev(__u32 gw)
306 {
307 struct fib_node * f;
308 f = fib_lookup_gateway(gw);
309 if (f)
310 return f->fib_info->fib_dev;
311 return NULL;
312 }
313
314
315
316
317
318
319
320
321
322 static __u32 unsigned long default_mask(__u32 dst)
323 {
324 dst = ntohl(dst);
325 if (IN_CLASSA(dst))
326 return htonl(IN_CLASSA_NET);
327 if (IN_CLASSB(dst))
328 return htonl(IN_CLASSB_NET);
329 return htonl(IN_CLASSC_NET);
330 }
331
332
333
334
335
336
337 static __u32 guess_mask(__u32 dst, struct device * dev)
338 {
339 __u32 mask;
340
341 if (!dst)
342 return 0;
343 mask = default_mask(dst);
344 if ((dst ^ dev->pa_addr) & mask)
345 return mask;
346 return dev->pa_mask;
347 }
348
349
350
351
352
353
354 static inline int bad_mask(__u32 mask, __u32 addr)
355 {
356 if (addr & (mask = ~mask))
357 return 1;
358 mask = ntohl(mask);
359 if (mask & (mask+1))
360 return 1;
361 return 0;
362 }
363
364
365 static int fib_del_list(struct fib_node **fp, __u32 dst,
366 struct device * dev, __u32 gtw, short flags, short metric, __u32 mask)
367 {
368 struct fib_node *f;
369 int found=0;
370
371 while((f = *fp) != NULL)
372 {
373 struct fib_info * fi = f->fib_info;
374
375
376
377
378
379
380 if (f->fib_dst != dst ||
381 (gtw && fi->fib_gateway != gtw) ||
382 (metric >= 0 && f->fib_metric != metric) ||
383 (dev && fi->fib_dev != dev) )
384 {
385 fp = &f->fib_next;
386 continue;
387 }
388 cli();
389 *fp = f->fib_next;
390 if (fib_loopback == f)
391 fib_loopback = NULL;
392 sti();
393 ip_netlink_msg(RTMSG_DELROUTE, dst, gtw, mask, flags, metric, fi->fib_dev->name);
394 fib_free_node(f);
395 found++;
396 }
397 return found;
398 }
399
400 static __inline__ int fib_del_1(__u32 dst, __u32 mask,
401 struct device * dev, __u32 gtw, short flags, short metric)
402 {
403 struct fib_node **fp;
404 struct fib_zone *fz;
405 int found=0;
406
407 if (!mask)
408 {
409 for (fz=fib_zone_list; fz; fz = fz->fz_next)
410 {
411 int tmp;
412 if (fz->fz_hash_table)
413 fp = &fz->fz_hash_table[fz_hash_code(dst, fz->fz_logmask)];
414 else
415 fp = &fz->fz_list;
416
417 tmp = fib_del_list(fp, dst, dev, gtw, flags, metric, mask);
418 fz->fz_nent -= tmp;
419 found += tmp;
420 }
421 }
422 else
423 {
424 if ((fz = fib_zones[rt_logmask(mask)]) != NULL)
425 {
426 if (fz->fz_hash_table)
427 fp = &fz->fz_hash_table[fz_hash_code(dst, fz->fz_logmask)];
428 else
429 fp = &fz->fz_list;
430
431 found = fib_del_list(fp, dst, dev, gtw, flags, metric, mask);
432 fz->fz_nent -= found;
433 }
434 }
435
436 if (found)
437 {
438 rt_cache_flush();
439 return 0;
440 }
441 return -ESRCH;
442 }
443
444
445 static struct fib_info * fib_create_info(__u32 gw, struct device * dev,
446 unsigned short flags, unsigned short mss,
447 unsigned long window, unsigned short irtt)
448 {
449 struct fib_info * fi;
450
451 if (!(flags & RTF_MSS))
452 {
453 mss = dev->mtu;
454 #ifdef CONFIG_NO_PATH_MTU_DISCOVERY
455
456
457
458
459
460
461
462
463 if ((flags & RTF_GATEWAY) && mss > 576)
464 mss = 576;
465 #endif
466 }
467 if (!(flags & RTF_WINDOW))
468 window = 0;
469 if (!(flags & RTF_IRTT))
470 irtt = 0;
471
472 for (fi=fib_info_list; fi; fi = fi->fib_next)
473 {
474 if (fi->fib_gateway != gw ||
475 fi->fib_dev != dev ||
476 fi->fib_flags != flags ||
477 fi->fib_mtu != mss ||
478 fi->fib_window != window ||
479 fi->fib_irtt != irtt)
480 continue;
481 fi->fib_refcnt++;
482 #if RT_CACHE_DEBUG >= 2
483 printk("fib_create_info: fi %08x/%s is duplicate\n", fi->fib_gateway, fi->fib_dev->name);
484 #endif
485 return fi;
486 }
487 fi = (struct fib_info*)kmalloc(sizeof(struct fib_info), GFP_KERNEL);
488 if (!fi)
489 return NULL;
490 memset(fi, 0, sizeof(struct fib_info));
491 fi->fib_flags = flags;
492 fi->fib_dev = dev;
493 fi->fib_gateway = gw;
494 fi->fib_mtu = mss;
495 fi->fib_window = window;
496 fi->fib_refcnt++;
497 fi->fib_next = fib_info_list;
498 fi->fib_prev = NULL;
499 if (fib_info_list)
500 fib_info_list->fib_prev = fi;
501 fib_info_list = fi;
502 #if RT_CACHE_DEBUG >= 2
503 printk("fib_create_info: fi %08x/%s is created\n", fi->fib_gateway, fi->fib_dev->name);
504 #endif
505 return fi;
506 }
507
508
509 static __inline__ void fib_add_1(short flags, __u32 dst, __u32 mask,
510 __u32 gw, struct device *dev, unsigned short mss,
511 unsigned long window, unsigned short irtt, short metric)
512 {
513 struct fib_node *f, *f1;
514 struct fib_node **fp;
515 struct fib_node **dup_fp = NULL;
516 struct fib_zone * fz;
517 struct fib_info * fi;
518 int logmask;
519
520 if (flags & RTF_HOST)
521 mask = 0xffffffff;
522
523
524
525 else if (!mask)
526 {
527 if (!((dst ^ dev->pa_addr) & dev->pa_mask))
528 {
529 mask = dev->pa_mask;
530 flags &= ~RTF_GATEWAY;
531 if (flags & RTF_DYNAMIC)
532 {
533 printk("Dynamic route to my own net rejected\n");
534 return;
535 }
536 }
537 else
538 mask = guess_mask(dst, dev);
539 dst &= mask;
540 }
541
542
543
544
545
546 if (gw == dev->pa_addr)
547 flags &= ~RTF_GATEWAY;
548
549 if (flags & RTF_GATEWAY)
550 {
551
552
553
554
555 if (dev != get_gw_dev(gw))
556 return;
557
558 flags |= RTF_GATEWAY;
559 }
560 else
561 gw = 0;
562
563
564
565
566
567 f = (struct fib_node *) kmalloc(sizeof(struct fib_node), GFP_KERNEL);
568 if (f == NULL)
569 return;
570
571 memset(f, 0, sizeof(struct fib_node));
572 f->fib_dst = dst;
573 f->fib_metric = metric;
574 f->fib_tos = 0;
575
576 if ((fi = fib_create_info(gw, dev, flags, mss, window, irtt)) == NULL)
577 {
578 kfree_s(f, sizeof(struct fib_node));
579 return;
580 }
581 f->fib_info = fi;
582
583 logmask = rt_logmask(mask);
584 fz = fib_zones[logmask];
585
586
587 if (!fz)
588 {
589 int i;
590 fz = kmalloc(sizeof(struct fib_zone), GFP_KERNEL);
591 if (!fz)
592 {
593 fib_free_node(f);
594 return;
595 }
596 memset(fz, 0, sizeof(struct fib_zone));
597 fz->fz_logmask = logmask;
598 fz->fz_mask = mask;
599 for (i=logmask-1; i>=0; i--)
600 if (fib_zones[i])
601 break;
602 cli();
603 if (i<0)
604 {
605 fz->fz_next = fib_zone_list;
606 fib_zone_list = fz;
607 }
608 else
609 {
610 fz->fz_next = fib_zones[i]->fz_next;
611 fib_zones[i]->fz_next = fz;
612 }
613 fib_zones[logmask] = fz;
614 sti();
615 }
616
617
618
619
620
621 if (fz->fz_nent >= RTZ_HASHING_LIMIT && !fz->fz_hash_table && logmask<32)
622 {
623 struct fib_node ** ht;
624 #if RT_CACHE_DEBUG
625 printk("fib_add_1: hashing for zone %d started\n", logmask);
626 #endif
627 ht = kmalloc(RTZ_HASH_DIVISOR*sizeof(struct rtable*), GFP_KERNEL);
628
629 if (ht)
630 {
631 memset(ht, 0, RTZ_HASH_DIVISOR*sizeof(struct fib_node*));
632 cli();
633 f1 = fz->fz_list;
634 while (f1)
635 {
636 struct fib_node * next;
637 unsigned hash = fz_hash_code(f1->fib_dst, logmask);
638 next = f1->fib_next;
639 f1->fib_next = ht[hash];
640 ht[hash] = f1;
641 f1 = next;
642 }
643 fz->fz_list = NULL;
644 fz->fz_hash_table = ht;
645 sti();
646 }
647 }
648
649 if (fz->fz_hash_table)
650 fp = &fz->fz_hash_table[fz_hash_code(dst, logmask)];
651 else
652 fp = &fz->fz_list;
653
654
655
656
657 while ((f1 = *fp) != NULL)
658 {
659 if (f1->fib_dst == dst)
660 break;
661 fp = &f1->fib_next;
662 }
663
664
665
666
667 while ((f1 = *fp) != NULL && f1->fib_dst == dst)
668 {
669 if (f1->fib_metric >= metric)
670 break;
671
672
673
674
675
676 if (f1->fib_info->fib_gateway == gw)
677 dup_fp = fp;
678 fp = &f1->fib_next;
679 }
680
681
682
683
684
685 if (f1 && f1->fib_metric == metric && f1->fib_info == fi)
686 {
687 fib_free_node(f);
688 return;
689 }
690
691
692
693
694
695 cli();
696 f->fib_next = f1;
697 *fp = f;
698 if (!fib_loopback && (fi->fib_dev->flags & IFF_LOOPBACK))
699 fib_loopback = f;
700 sti();
701 fz->fz_nent++;
702 ip_netlink_msg(RTMSG_NEWROUTE, dst, gw, mask, flags, metric, fi->fib_dev->name);
703
704
705
706
707
708 if (dup_fp)
709 fp = dup_fp;
710 else
711 fp = &f->fib_next;
712
713 while ((f1 = *fp) != NULL && f1->fib_dst == dst)
714 {
715 if (f1->fib_info->fib_gateway == gw)
716 {
717 cli();
718 *fp = f1->fib_next;
719 if (fib_loopback == f1)
720 fib_loopback = NULL;
721 sti();
722 ip_netlink_msg(RTMSG_DELROUTE, dst, gw, mask, flags, metric, f1->fib_info->fib_dev->name);
723 fib_free_node(f1);
724 fz->fz_nent--;
725 break;
726 }
727 fp = &f1->fib_next;
728 }
729 rt_cache_flush();
730 return;
731 }
732
733 static int rt_flush_list(struct fib_node ** fp, struct device *dev)
734 {
735 int found = 0;
736 struct fib_node *f;
737
738 while ((f = *fp) != NULL) {
739 if (f->fib_info->fib_dev != dev) {
740 fp = &f->fib_next;
741 continue;
742 }
743 cli();
744 *fp = f->fib_next;
745 if (fib_loopback == f)
746 fib_loopback = NULL;
747 sti();
748 fib_free_node(f);
749 found++;
750 }
751 return found;
752 }
753
754 static __inline__ void fib_flush_1(struct device *dev)
755 {
756 struct fib_zone *fz;
757 int found = 0;
758
759 for (fz = fib_zone_list; fz; fz = fz->fz_next)
760 {
761 if (fz->fz_hash_table)
762 {
763 int i;
764 int tmp = 0;
765 for (i=0; i<RTZ_HASH_DIVISOR; i++)
766 tmp += rt_flush_list(&fz->fz_hash_table[i], dev);
767 fz->fz_nent -= tmp;
768 found += tmp;
769 }
770 else
771 {
772 int tmp;
773 tmp = rt_flush_list(&fz->fz_list, dev);
774 fz->fz_nent -= tmp;
775 found += tmp;
776 }
777 }
778
779 if (found)
780 rt_cache_flush();
781 }
782
783
784
785
786
787
788
789
790
791
792
793
794
795 int rt_get_info(char *buffer, char **start, off_t offset, int length, int dummy)
796 {
797 struct fib_zone *fz;
798 struct fib_node *f;
799 int len=0;
800 off_t pos=0;
801 char temp[129];
802 int i;
803
804 pos = 128;
805
806 if (offset<128)
807 {
808 sprintf(buffer,"%-127s\n","Iface\tDestination\tGateway \tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU\tWindow\tIRTT");
809 len = 128;
810 }
811
812 while (ip_rt_lock)
813 sleep_on(&rt_wait);
814 ip_rt_fast_lock();
815
816 for (fz=fib_zone_list; fz; fz = fz->fz_next)
817 {
818 int maxslot;
819 struct fib_node ** fp;
820
821 if (fz->fz_nent == 0)
822 continue;
823
824 if (pos + 128*fz->fz_nent <= offset)
825 {
826 pos += 128*fz->fz_nent;
827 len = 0;
828 continue;
829 }
830
831 if (fz->fz_hash_table)
832 {
833 maxslot = RTZ_HASH_DIVISOR;
834 fp = fz->fz_hash_table;
835 }
836 else
837 {
838 maxslot = 1;
839 fp = &fz->fz_list;
840 }
841
842 for (i=0; i < maxslot; i++, fp++)
843 {
844
845 for (f = *fp; f; f = f->fib_next)
846 {
847 struct fib_info * fi;
848
849
850
851 pos += 128;
852
853 if (pos <= offset)
854 {
855 len=0;
856 continue;
857 }
858
859 fi = f->fib_info;
860 sprintf(temp, "%s\t%08lX\t%08lX\t%02X\t%d\t%lu\t%d\t%08lX\t%d\t%lu\t%u",
861 fi->fib_dev->name, (unsigned long)f->fib_dst, (unsigned long)fi->fib_gateway,
862 fi->fib_flags, 0, f->fib_use, f->fib_metric,
863 (unsigned long)fz->fz_mask, (int)fi->fib_mtu, fi->fib_window, (int)fi->fib_irtt);
864 sprintf(buffer+len,"%-127s\n",temp);
865
866 len += 128;
867 if (pos >= offset+length)
868 goto done;
869 }
870 }
871 }
872
873 done:
874 ip_rt_unlock();
875 wake_up(&rt_wait);
876
877 *start = buffer+len-(pos-offset);
878 len = pos - offset;
879 if (len>length)
880 len = length;
881 return len;
882 }
883
884 int rt_cache_get_info(char *buffer, char **start, off_t offset, int length, int dummy)
885 {
886 int len=0;
887 off_t pos=0;
888 char temp[129];
889 struct rtable *r;
890 int i;
891
892 pos = 128;
893
894 if (offset<128)
895 {
896 sprintf(buffer,"%-127s\n","Iface\tDestination\tGateway \tFlags\tRefCnt\tUse\tMetric\tSource\t\tMTU\tWindow\tIRTT\tHH\tARP\n");
897 len = 128;
898 }
899
900
901 while (ip_rt_lock)
902 sleep_on(&rt_wait);
903 ip_rt_fast_lock();
904
905 for (i = 0; i<RT_HASH_DIVISOR; i++)
906 {
907 for (r = ip_rt_hash_table[i]; r; r = r->rt_next)
908 {
909
910
911
912 pos += 128;
913
914 if (pos <= offset)
915 {
916 len = 0;
917 continue;
918 }
919
920 sprintf(temp, "%s\t%08lX\t%08lX\t%02X\t%ld\t%lu\t%d\t%08lX\t%d\t%lu\t%u\t%ld\t%1d",
921 r->rt_dev->name, (unsigned long)r->rt_dst, (unsigned long)r->rt_gateway,
922 r->rt_flags, r->rt_refcnt, r->rt_use, 0,
923 (unsigned long)r->rt_src, (int)r->rt_mtu, r->rt_window, (int)r->rt_irtt, r->rt_hh ? r->rt_hh->hh_refcnt : -1, r->rt_hh ? r->rt_hh->hh_uptodate : 0);
924 sprintf(buffer+len,"%-127s\n",temp);
925 len += 128;
926 if (pos >= offset+length)
927 goto done;
928 }
929 }
930
931 done:
932 ip_rt_unlock();
933 wake_up(&rt_wait);
934
935 *start = buffer+len-(pos-offset);
936 len = pos-offset;
937 if (len>length)
938 len = length;
939 return len;
940 }
941
942
943 static void rt_free(struct rtable * rt)
944 {
945 unsigned long flags;
946
947 save_flags(flags);
948 cli();
949 if (!rt->rt_refcnt)
950 {
951 struct hh_cache * hh = rt->rt_hh;
952 rt->rt_hh = NULL;
953 if (hh && !--hh->hh_refcnt)
954 {
955 restore_flags(flags);
956 kfree_s(hh, sizeof(struct hh_cache));
957 }
958 restore_flags(flags);
959 kfree_s(rt, sizeof(struct rt_table));
960 return;
961 }
962 rt->rt_next = rt_free_queue;
963 rt->rt_flags &= ~RTF_UP;
964 rt_free_queue = rt;
965 ip_rt_bh_mask |= RT_BH_FREE;
966 #if RT_CACHE_DEBUG >= 2
967 printk("rt_free: %08x\n", rt->rt_dst);
968 #endif
969 restore_flags(flags);
970 }
971
972
973
974
975
976 static __inline__ void rt_kick_free_queue(void)
977 {
978 struct rtable *rt, **rtp;
979
980 rtp = &rt_free_queue;
981
982 while ((rt = *rtp) != NULL)
983 {
984 if (!rt->rt_refcnt)
985 {
986 struct hh_cache * hh = rt->rt_hh;
987 #if RT_CACHE_DEBUG >= 2
988 __u32 daddr = rt->rt_dst;
989 #endif
990 *rtp = rt->rt_next;
991 rt->rt_hh = NULL;
992 if (hh && !--hh->hh_refcnt)
993 {
994 sti();
995 kfree_s(hh, sizeof(struct hh_cache));
996 }
997 sti();
998 kfree_s(rt, sizeof(struct rt_table));
999 #if RT_CACHE_DEBUG >= 2
1000 printk("rt_kick_free_queue: %08x is free\n", daddr);
1001 #endif
1002 cli();
1003 continue;
1004 }
1005 rtp = &rt->rt_next;
1006 }
1007 }
1008
1009 void ip_rt_run_bh() {
1010 unsigned long flags;
1011 save_flags(flags);
1012 cli();
1013 if (ip_rt_bh_mask && !ip_rt_lock)
1014 {
1015 if (ip_rt_bh_mask & RT_BH_REDIRECT)
1016 rt_kick_backlog();
1017
1018 if (ip_rt_bh_mask & RT_BH_GARBAGE_COLLECT)
1019 {
1020 ip_rt_fast_lock();
1021 ip_rt_bh_mask &= ~RT_BH_GARBAGE_COLLECT;
1022 sti();
1023 rt_garbage_collect_1();
1024 cli();
1025 ip_rt_fast_unlock();
1026 }
1027
1028 if (ip_rt_bh_mask & RT_BH_FREE)
1029 rt_kick_free_queue();
1030 }
1031 restore_flags(flags);
1032 }
1033
1034
1035 void ip_rt_check_expire()
1036 {
1037 ip_rt_fast_lock();
1038 if (ip_rt_lock == 1)
1039 {
1040 int i;
1041 struct rtable *rth, **rthp;
1042 unsigned long flags;
1043 unsigned long now = jiffies;
1044
1045 save_flags(flags);
1046 for (i=0; i<RT_HASH_DIVISOR; i++)
1047 {
1048 rthp = &ip_rt_hash_table[i];
1049
1050 while ((rth = *rthp) != NULL)
1051 {
1052 struct rtable * rth_next = rth->rt_next;
1053
1054
1055
1056
1057
1058 cli();
1059 if (!rth->rt_refcnt && rth->rt_lastuse + RT_CACHE_TIMEOUT < now)
1060 {
1061 *rthp = rth_next;
1062 sti();
1063 rt_cache_size--;
1064 #if RT_CACHE_DEBUG >= 2
1065 printk("rt_check_expire clean %02x@%08x\n", i, rth->rt_dst);
1066 #endif
1067 rt_free(rth);
1068 continue;
1069 }
1070 sti();
1071
1072 if (!rth_next)
1073 break;
1074
1075
1076
1077
1078
1079 if (rth->rt_lastuse + RT_CACHE_BUBBLE_THRESHOULD < rth_next->rt_lastuse ||
1080 (rth->rt_lastuse < rth_next->rt_lastuse &&
1081 rth->rt_use < rth_next->rt_use))
1082 {
1083 #if RT_CACHE_DEBUG >= 2
1084 printk("rt_check_expire bubbled %02x@%08x<->%08x\n", i, rth->rt_dst, rth_next->rt_dst);
1085 #endif
1086 cli();
1087 *rthp = rth_next;
1088 rth->rt_next = rth_next->rt_next;
1089 rth_next->rt_next = rth;
1090 sti();
1091 rthp = &rth_next->rt_next;
1092 continue;
1093 }
1094 rthp = &rth->rt_next;
1095 }
1096 }
1097 restore_flags(flags);
1098 rt_kick_free_queue();
1099 }
1100 ip_rt_unlock();
1101 }
1102
1103 static void rt_redirect_1(__u32 dst, __u32 gw, struct device *dev)
1104 {
1105 struct rtable *rt;
1106 unsigned long hash = ip_rt_hash_code(dst);
1107
1108 if (gw == dev->pa_addr)
1109 return;
1110 if (dev != get_gw_dev(gw))
1111 return;
1112 rt = (struct rtable *) kmalloc(sizeof(struct rtable), GFP_ATOMIC);
1113 if (rt == NULL)
1114 return;
1115 memset(rt, 0, sizeof(struct rtable));
1116 rt->rt_flags = RTF_DYNAMIC | RTF_MODIFIED | RTF_HOST | RTF_GATEWAY | RTF_UP;
1117 rt->rt_dst = dst;
1118 rt->rt_dev = dev;
1119 rt->rt_gateway = gw;
1120 rt->rt_src = dev->pa_addr;
1121 rt->rt_mtu = dev->mtu;
1122 #ifdef CONFIG_NO_PATH_MTU_DISCOVERY
1123 if (dev->mtu > 576)
1124 rt->rt_mtu = 576;
1125 #endif
1126 rt->rt_lastuse = jiffies;
1127 rt->rt_refcnt = 1;
1128 rt_cache_add(hash, rt);
1129 ip_rt_put(rt);
1130 return;
1131 }
1132
1133 static void rt_cache_flush(void)
1134 {
1135 int i;
1136 struct rtable * rth, * next;
1137
1138 for (i=0; i<RT_HASH_DIVISOR; i++)
1139 {
1140 int nr=0;
1141
1142 cli();
1143 if (!(rth = ip_rt_hash_table[i]))
1144 {
1145 sti();
1146 continue;
1147 }
1148
1149 ip_rt_hash_table[i] = NULL;
1150 sti();
1151
1152 for (; rth; rth=next)
1153 {
1154 next = rth->rt_next;
1155 rt_cache_size--;
1156 nr++;
1157 rth->rt_next = NULL;
1158 rt_free(rth);
1159 }
1160 #if RT_CACHE_DEBUG >= 2
1161 if (nr > 0)
1162 printk("rt_cache_flush: %d@%02x\n", nr, i);
1163 #endif
1164 }
1165 #if RT_CACHE_DEBUG >= 1
1166 if (rt_cache_size)
1167 {
1168 printk("rt_cache_flush: bug rt_cache_size=%d\n", rt_cache_size);
1169 rt_cache_size = 0;
1170 }
1171 #endif
1172 }
1173
1174 static void rt_garbage_collect_1(void)
1175 {
1176 int i;
1177 unsigned expire = RT_CACHE_TIMEOUT>>1;
1178 struct rtable * rth, **rthp;
1179 unsigned long now = jiffies;
1180
1181 for (;;)
1182 {
1183 for (i=0; i<RT_HASH_DIVISOR; i++)
1184 {
1185 if (!ip_rt_hash_table[i])
1186 continue;
1187 for (rthp=&ip_rt_hash_table[i]; (rth=*rthp); rthp=&rth->rt_next)
1188 {
1189 if (rth->rt_lastuse + expire*(rth->rt_refcnt+1) > now)
1190 continue;
1191 rt_cache_size--;
1192 cli();
1193 *rthp=rth->rt_next;
1194 rth->rt_next = NULL;
1195 sti();
1196 rt_free(rth);
1197 break;
1198 }
1199 }
1200 if (rt_cache_size < RT_CACHE_SIZE_MAX)
1201 return;
1202 expire >>= 1;
1203 }
1204 }
1205
1206 static __inline__ void rt_req_enqueue(struct rt_req **q, struct rt_req *rtr)
1207 {
1208 unsigned long flags;
1209 struct rt_req * tail;
1210
1211 save_flags(flags);
1212 cli();
1213 tail = *q;
1214 if (!tail)
1215 rtr->rtr_next = rtr;
1216 else
1217 {
1218 rtr->rtr_next = tail->rtr_next;
1219 tail->rtr_next = rtr;
1220 }
1221 *q = rtr;
1222 restore_flags(flags);
1223 return;
1224 }
1225
1226
1227
1228
1229
1230 static __inline__ struct rt_req * rt_req_dequeue(struct rt_req **q)
1231 {
1232 struct rt_req * rtr;
1233
1234 if (*q)
1235 {
1236 rtr = (*q)->rtr_next;
1237 (*q)->rtr_next = rtr->rtr_next;
1238 if (rtr->rtr_next == rtr)
1239 *q = NULL;
1240 rtr->rtr_next = NULL;
1241 return rtr;
1242 }
1243 return NULL;
1244 }
1245
1246
1247
1248
1249
1250 static void rt_kick_backlog()
1251 {
1252 if (!ip_rt_lock)
1253 {
1254 struct rt_req * rtr;
1255
1256 ip_rt_fast_lock();
1257
1258 while ((rtr = rt_req_dequeue(&rt_backlog)) != NULL)
1259 {
1260 sti();
1261 rt_redirect_1(rtr->dst, rtr->gw, rtr->dev);
1262 kfree_s(rtr, sizeof(struct rt_req));
1263 cli();
1264 }
1265
1266 ip_rt_bh_mask &= ~RT_BH_REDIRECT;
1267
1268 ip_rt_fast_unlock();
1269 }
1270 }
1271
1272
1273
1274
1275
1276 static int rt_del(__u32 dst, __u32 mask,
1277 struct device * dev, __u32 gtw, short rt_flags, short metric)
1278 {
1279 int retval;
1280
1281 while (ip_rt_lock)
1282 sleep_on(&rt_wait);
1283 ip_rt_fast_lock();
1284 retval = fib_del_1(dst, mask, dev, gtw, rt_flags, metric);
1285 ip_rt_unlock();
1286 wake_up(&rt_wait);
1287 return retval;
1288 }
1289
1290 static void rt_add(short flags, __u32 dst, __u32 mask,
1291 __u32 gw, struct device *dev, unsigned short mss,
1292 unsigned long window, unsigned short irtt, short metric)
1293 {
1294 while (ip_rt_lock)
1295 sleep_on(&rt_wait);
1296 ip_rt_fast_lock();
1297 fib_add_1(flags, dst, mask, gw, dev, mss, window, irtt, metric);
1298 ip_rt_unlock();
1299 wake_up(&rt_wait);
1300 }
1301
1302 void ip_rt_flush(struct device *dev)
1303 {
1304 while (ip_rt_lock)
1305 sleep_on(&rt_wait);
1306 ip_rt_fast_lock();
1307 fib_flush_1(dev);
1308 ip_rt_unlock();
1309 wake_up(&rt_wait);
1310 }
1311
1312
1313
1314
1315
1316 void ip_rt_redirect(__u32 src, __u32 dst, __u32 gw, struct device *dev)
1317 {
1318 struct rt_req * rtr;
1319 struct rtable * rt;
1320
1321 rt = ip_rt_route(dst, 0);
1322 if (!rt)
1323 return;
1324
1325 if (rt->rt_gateway != src ||
1326 rt->rt_dev != dev ||
1327 ((gw^dev->pa_addr)&dev->pa_mask) ||
1328 ip_chk_addr(gw))
1329 {
1330 ip_rt_put(rt);
1331 return;
1332 }
1333 ip_rt_put(rt);
1334
1335 ip_rt_fast_lock();
1336 if (ip_rt_lock == 1)
1337 {
1338 rt_redirect_1(dst, gw, dev);
1339 ip_rt_unlock();
1340 return;
1341 }
1342
1343 rtr = kmalloc(sizeof(struct rt_req), GFP_ATOMIC);
1344 if (rtr)
1345 {
1346 rtr->dst = dst;
1347 rtr->gw = gw;
1348 rtr->dev = dev;
1349 rt_req_enqueue(&rt_backlog, rtr);
1350 ip_rt_bh_mask |= RT_BH_REDIRECT;
1351 }
1352 ip_rt_unlock();
1353 }
1354
1355
1356 static __inline__ void rt_garbage_collect(void)
1357 {
1358 if (ip_rt_lock == 1)
1359 {
1360 rt_garbage_collect_1();
1361 return;
1362 }
1363 ip_rt_bh_mask |= RT_BH_GARBAGE_COLLECT;
1364 }
1365
1366 static void rt_cache_add(unsigned hash, struct rtable * rth)
1367 {
1368 unsigned long flags;
1369 struct rtable **rthp;
1370 __u32 daddr = rth->rt_dst;
1371 unsigned long now = jiffies;
1372
1373 #if RT_CACHE_DEBUG >= 2
1374 if (ip_rt_lock != 1)
1375 {
1376 printk("rt_cache_add: ip_rt_lock==%d\n", ip_rt_lock);
1377 return;
1378 }
1379 #endif
1380
1381 save_flags(flags);
1382
1383 if (rth->rt_dev->header_cache_bind)
1384 {
1385 struct rtable * rtg = rth;
1386
1387 if (rth->rt_gateway != daddr)
1388 {
1389 ip_rt_fast_unlock();
1390 rtg = ip_rt_route(rth->rt_gateway, 0);
1391 ip_rt_fast_lock();
1392 }
1393
1394 if (rtg)
1395 {
1396 if (rtg == rth)
1397 rtg->rt_dev->header_cache_bind(&rtg->rt_hh, rtg->rt_dev, ETH_P_IP, rtg->rt_dst);
1398 else
1399 {
1400 if (rtg->rt_hh)
1401 ATOMIC_INCR(&rtg->rt_hh->hh_refcnt);
1402 rth->rt_hh = rtg->rt_hh;
1403 ip_rt_put(rtg);
1404 }
1405 }
1406 }
1407
1408 if (rt_cache_size >= RT_CACHE_SIZE_MAX)
1409 rt_garbage_collect();
1410
1411 cli();
1412 rth->rt_next = ip_rt_hash_table[hash];
1413 #if RT_CACHE_DEBUG >= 2
1414 if (rth->rt_next)
1415 {
1416 struct rtable * trth;
1417 printk("rt_cache @%02x: %08x", hash, daddr);
1418 for (trth=rth->rt_next; trth; trth=trth->rt_next)
1419 printk(" . %08x", trth->rt_dst);
1420 printk("\n");
1421 }
1422 #endif
1423 ip_rt_hash_table[hash] = rth;
1424 rthp = &rth->rt_next;
1425 sti();
1426 rt_cache_size++;
1427
1428
1429
1430
1431
1432 while ((rth = *rthp) != NULL)
1433 {
1434
1435 cli();
1436 if ((!rth->rt_refcnt && rth->rt_lastuse + RT_CACHE_TIMEOUT < now)
1437 || rth->rt_dst == daddr)
1438 {
1439 *rthp = rth->rt_next;
1440 rt_cache_size--;
1441 sti();
1442 #if RT_CACHE_DEBUG >= 2
1443 printk("rt_cache clean %02x@%08x\n", hash, rth->rt_dst);
1444 #endif
1445 rt_free(rth);
1446 continue;
1447 }
1448 sti();
1449 rthp = &rth->rt_next;
1450 }
1451 restore_flags(flags);
1452 }
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462 struct rtable * ip_rt_slow_route (__u32 daddr, int local)
1463 {
1464 unsigned hash = ip_rt_hash_code(daddr)^local;
1465 struct rtable * rth;
1466 struct fib_node * f;
1467 struct fib_info * fi;
1468 __u32 saddr;
1469
1470 #if RT_CACHE_DEBUG >= 2
1471 printk("rt_cache miss @%08x\n", daddr);
1472 #endif
1473
1474 rth = kmalloc(sizeof(struct rtable), GFP_ATOMIC);
1475 if (!rth)
1476 {
1477 ip_rt_unlock();
1478 return NULL;
1479 }
1480
1481 if (local)
1482 f = fib_lookup_local(daddr);
1483 else
1484 f = fib_lookup (daddr);
1485
1486 if (f)
1487 {
1488 fi = f->fib_info;
1489 f->fib_use++;
1490 }
1491
1492 if (!f || (fi->fib_flags & RTF_REJECT))
1493 {
1494 #if RT_CACHE_DEBUG >= 2
1495 printk("rt_route failed @%08x\n", daddr);
1496 #endif
1497 ip_rt_unlock();
1498 kfree_s(rth, sizeof(struct rtable));
1499 return NULL;
1500 }
1501
1502 saddr = fi->fib_dev->pa_addr;
1503
1504 if (daddr == fi->fib_dev->pa_addr)
1505 {
1506 f->fib_use--;
1507 if ((f = fib_loopback) != NULL)
1508 {
1509 f->fib_use++;
1510 fi = f->fib_info;
1511 }
1512 }
1513
1514 if (!f)
1515 {
1516 ip_rt_unlock();
1517 kfree_s(rth, sizeof(struct rtable));
1518 return NULL;
1519 }
1520
1521 rth->rt_dst = daddr;
1522 rth->rt_src = saddr;
1523 rth->rt_lastuse = jiffies;
1524 rth->rt_refcnt = 1;
1525 rth->rt_use = 1;
1526 rth->rt_next = NULL;
1527 rth->rt_hh = NULL;
1528 rth->rt_gateway = fi->fib_gateway;
1529 rth->rt_dev = fi->fib_dev;
1530 rth->rt_mtu = fi->fib_mtu;
1531 rth->rt_window = fi->fib_window;
1532 rth->rt_irtt = fi->fib_irtt;
1533 rth->rt_tos = f->fib_tos;
1534 rth->rt_flags = fi->fib_flags | RTF_HOST;
1535 if (local)
1536 rth->rt_flags |= RTF_LOCAL;
1537
1538 if (!(rth->rt_flags & RTF_GATEWAY))
1539 rth->rt_gateway = rth->rt_dst;
1540
1541 if (ip_rt_lock == 1)
1542 rt_cache_add(hash, rth);
1543 else
1544 {
1545 rt_free(rth);
1546 #if RT_CACHE_DEBUG >= 1
1547 printk("rt_cache: route to %08x was born dead\n", daddr);
1548 #endif
1549 }
1550
1551 ip_rt_unlock();
1552 return rth;
1553 }
1554
1555 void ip_rt_put(struct rtable * rt)
1556 {
1557 if (rt)
1558 ATOMIC_DECR(&rt->rt_refcnt);
1559 }
1560
1561 struct rtable * ip_rt_route(__u32 daddr, int local)
1562 {
1563 struct rtable * rth;
1564
1565 ip_rt_fast_lock();
1566
1567 for (rth=ip_rt_hash_table[ip_rt_hash_code(daddr)^local]; rth; rth=rth->rt_next)
1568 {
1569 if (rth->rt_dst == daddr)
1570 {
1571 rth->rt_lastuse = jiffies;
1572 ATOMIC_INCR(&rth->rt_use);
1573 ATOMIC_INCR(&rth->rt_refcnt);
1574 ip_rt_unlock();
1575 return rth;
1576 }
1577 }
1578 return ip_rt_slow_route (daddr, local);
1579 }
1580
1581
1582
1583
1584
1585
1586
1587 int ip_rt_new(struct rtentry *r)
1588 {
1589 int err;
1590 char * devname;
1591 struct device * dev = NULL;
1592 unsigned long flags;
1593 __u32 daddr, mask, gw;
1594 short metric;
1595
1596
1597
1598
1599
1600 if ((devname = r->rt_dev) != NULL)
1601 {
1602 err = getname(devname, &devname);
1603 if (err)
1604 return err;
1605 dev = dev_get(devname);
1606 putname(devname);
1607 if (!dev)
1608 return -ENODEV;
1609 }
1610
1611
1612
1613
1614
1615 if (r->rt_dst.sa_family != AF_INET)
1616 return -EAFNOSUPPORT;
1617
1618
1619
1620
1621
1622
1623 flags = r->rt_flags;
1624 daddr = (__u32) ((struct sockaddr_in *) &r->rt_dst)->sin_addr.s_addr;
1625 mask = (__u32) ((struct sockaddr_in *) &r->rt_genmask)->sin_addr.s_addr;
1626 gw = (__u32) ((struct sockaddr_in *) &r->rt_gateway)->sin_addr.s_addr;
1627 metric = r->rt_metric > 0 ? r->rt_metric - 1 : 0;
1628
1629
1630
1631
1632
1633
1634
1635 if (!dev && (flags & RTF_GATEWAY))
1636 {
1637 struct device *dev2;
1638 for (dev2 = dev_base ; dev2 != NULL ; dev2 = dev2->next)
1639 {
1640 if ((dev2->flags & IFF_UP) && dev2->pa_addr == gw)
1641 {
1642 flags &= ~RTF_GATEWAY;
1643 dev = dev2;
1644 break;
1645 }
1646 }
1647 }
1648
1649
1650
1651
1652
1653 if (bad_mask(mask, daddr))
1654 mask=0;
1655
1656
1657
1658
1659
1660 if (flags & RTF_HOST)
1661 mask = 0xffffffff;
1662 else if (mask && r->rt_genmask.sa_family != AF_INET)
1663 return -EAFNOSUPPORT;
1664
1665
1666
1667
1668
1669 if (flags & RTF_GATEWAY)
1670 {
1671 if (r->rt_gateway.sa_family != AF_INET)
1672 return -EAFNOSUPPORT;
1673 if (!dev)
1674 dev = get_gw_dev(gw);
1675 }
1676 else if (!dev)
1677 dev = ip_dev_check(daddr);
1678
1679
1680
1681
1682
1683 if (dev == NULL)
1684 return -ENETUNREACH;
1685
1686
1687
1688
1689
1690 rt_add(flags, daddr, mask, gw, dev, r->rt_mss, r->rt_window, r->rt_irtt, metric);
1691 return 0;
1692 }
1693
1694
1695
1696
1697
1698
1699 static int rt_kill(struct rtentry *r)
1700 {
1701 struct sockaddr_in *trg;
1702 struct sockaddr_in *msk;
1703 struct sockaddr_in *gtw;
1704 char *devname;
1705 int err;
1706 struct device * dev = NULL;
1707
1708 trg = (struct sockaddr_in *) &r->rt_dst;
1709 msk = (struct sockaddr_in *) &r->rt_genmask;
1710 gtw = (struct sockaddr_in *) &r->rt_gateway;
1711 if ((devname = r->rt_dev) != NULL)
1712 {
1713 err = getname(devname, &devname);
1714 if (err)
1715 return err;
1716 dev = dev_get(devname);
1717 putname(devname);
1718 if (!dev)
1719 return -ENODEV;
1720 }
1721
1722
1723
1724
1725 err=rt_del((__u32)trg->sin_addr.s_addr, (__u32)msk->sin_addr.s_addr, dev,
1726 (__u32)gtw->sin_addr.s_addr, r->rt_flags, r->rt_metric - 1);
1727 return err;
1728 }
1729
1730
1731
1732
1733
1734 int ip_rt_ioctl(unsigned int cmd, void *arg)
1735 {
1736 int err;
1737 struct rtentry rt;
1738
1739 switch(cmd)
1740 {
1741 case SIOCADDRT:
1742 case SIOCDELRT:
1743 if (!suser())
1744 return -EPERM;
1745 err=verify_area(VERIFY_READ, arg, sizeof(struct rtentry));
1746 if (err)
1747 return err;
1748 memcpy_fromfs(&rt, arg, sizeof(struct rtentry));
1749 return (cmd == SIOCDELRT) ? rt_kill(&rt) : ip_rt_new(&rt);
1750 }
1751
1752 return -EINVAL;
1753 }
1754
1755 void ip_rt_advice(struct rtable **rp, int advice)
1756 {
1757
1758 return;
1759 }
1760