iproute.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
iproute.c (14918B)
---
1 #include "u.h"
2 #include "lib.h"
3 #include "mem.h"
4 #include "dat.h"
5 #include "fns.h"
6 #include "error.h"
7
8 #include "ip.h"
9
10 static void walkadd(Fs*, Route**, Route*);
11 static void addnode(Fs*, Route**, Route*);
12 static void calcd(Route*);
13
14 /* these are used for all instances of IP */
15 static Route* v4freelist;
16 static Route* v6freelist;
17 static RWlock routelock;
18 static ulong v4routegeneration, v6routegeneration;
19
20 static void
21 freeroute(Route *r)
22 {
23 Route **l;
24
25 r->left = nil;
26 r->right = nil;
27 if(r->type & Rv4)
28 l = &v4freelist;
29 else
30 l = &v6freelist;
31 r->mid = *l;
32 *l = r;
33 }
34
35 static Route*
36 allocroute(int type)
37 {
38 Route *r;
39 int n;
40 Route **l;
41
42 if(type & Rv4){
43 n = sizeof(RouteTree) + sizeof(V4route);
44 l = &v4freelist;
45 } else {
46 n = sizeof(RouteTree) + sizeof(V6route);
47 l = &v6freelist;
48 }
49
50 r = *l;
51 if(r != nil){
52 *l = r->mid;
53 } else {
54 r = malloc(n);
55 if(r == nil)
56 panic("out of routing nodes");
57 }
58 memset(r, 0, n);
59 r->type = type;
60 r->ifc = nil;
61 r->ref = 1;
62
63 return r;
64 }
65
66 static void
67 addqueue(Route **q, Route *r)
68 {
69 Route *l;
70
71 if(r == nil)
72 return;
73
74 l = allocroute(r->type);
75 l->mid = *q;
76 *q = l;
77 l->left = r;
78 }
79
80 /*
81 * compare 2 v6 addresses
82 */
83 static int
84 lcmp(ulong *a, ulong *b)
85 {
86 int i;
87
88 for(i = 0; i < IPllen; i++){
89 if(a[i] > b[i])
90 return 1;
91 if(a[i] < b[i])
92 return -1;
93 }
94 return 0;
95 }
96
97 /*
98 * compare 2 v4 or v6 ranges
99 */
100 enum
101 {
102 Rpreceeds,
103 Rfollows,
104 Requals,
105 Rcontains,
106 Rcontained,
107 };
108
109 static int
110 rangecompare(Route *a, Route *b)
111 {
112 if(a->type & Rv4){
113 if(a->v4.endaddress < b->v4.address)
114 return Rpreceeds;
115
116 if(a->v4.address > b->v4.endaddress)
117 return Rfollows;
118
119 if(a->v4.address <= b->v4.address
120 && a->v4.endaddress >= b->v4.endaddress){
121 if(a->v4.address == b->v4.address
122 && a->v4.endaddress == b->v4.endaddress)
123 return Requals;
124 return Rcontains;
125 }
126 return Rcontained;
127 }
128
129 if(lcmp(a->v6.endaddress, b->v6.address) < 0)
130 return Rpreceeds;
131
132 if(lcmp(a->v6.address, b->v6.endaddress) > 0)
133 return Rfollows;
134
135 if(lcmp(a->v6.address, b->v6.address) <= 0
136 && lcmp(a->v6.endaddress, b->v6.endaddress) >= 0){
137 if(lcmp(a->v6.address, b->v6.address) == 0
138 && lcmp(a->v6.endaddress, b->v6.endaddress) == 0)
139 return Requals;
140 return Rcontains;
141 }
142
143 return Rcontained;
144 }
145
146 static void
147 copygate(Route *old, Route *new)
148 {
149 if(new->type & Rv4)
150 memmove(old->v4.gate, new->v4.gate, IPv4addrlen);
151 else
152 memmove(old->v6.gate, new->v6.gate, IPaddrlen);
153 }
154
155 /*
156 * walk down a tree adding nodes back in
157 */
158 static void
159 walkadd(Fs *f, Route **root, Route *p)
160 {
161 Route *l, *r;
162
163 l = p->left;
164 r = p->right;
165 p->left = 0;
166 p->right = 0;
167 addnode(f, root, p);
168 if(l)
169 walkadd(f, root, l);
170 if(r)
171 walkadd(f, root, r);
172 }
173
174 /*
175 * calculate depth
176 */
177 static void
178 calcd(Route *p)
179 {
180 Route *q;
181 int d;
182
183 if(p) {
184 d = 0;
185 q = p->left;
186 if(q)
187 d = q->depth;
188 q = p->right;
189 if(q && q->depth > d)
190 d = q->depth;
191 q = p->mid;
192 if(q && q->depth > d)
193 d = q->depth;
194 p->depth = d+1;
195 }
196 }
197
198 /*
199 * balance the tree at the current node
200 */
201 static void
202 balancetree(Route **cur)
203 {
204 Route *p, *l, *r;
205 int dl, dr;
206
207 /*
208 * if left and right are
209 * too out of balance,
210 * rotate tree node
211 */
212 p = *cur;
213 dl = 0; if((l = p->left) != nil) dl = l->depth;
214 dr = 0; if((r = p->right) != nil) dr = r->depth;
215
216 if(dl > dr+1) {
217 p->left = l->right;
218 l->right = p;
219 *cur = l;
220 calcd(p);
221 calcd(l);
222 } else
223 if(dr > dl+1) {
224 p->right = r->left;
225 r->left = p;
226 *cur = r;
227 calcd(p);
228 calcd(r);
229 } else
230 calcd(p);
231 }
232
233 /*
234 * add a new node to the tree
235 */
236 static void
237 addnode(Fs *f, Route **cur, Route *new)
238 {
239 Route *p;
240
241 p = *cur;
242 if(p == 0) {
243 *cur = new;
244 new->depth = 1;
245 return;
246 }
247
248 switch(rangecompare(new, p)){
249 case Rpreceeds:
250 addnode(f, &p->left, new);
251 break;
252 case Rfollows:
253 addnode(f, &p->right, new);
254 break;
255 case Rcontains:
256 /*
257 * if new node is superset
258 * of tree node,
259 * replace tree node and
260 * queue tree node to be
261 * merged into root.
262 */
263 *cur = new;
264 new->depth = 1;
265 addqueue(&f->queue, p);
266 break;
267 case Requals:
268 /*
269 * supercede the old entry if the old one isn't
270 * a local interface.
271 */
272 if((p->type & Rifc) == 0){
273 p->type = new->type;
274 p->ifcid = -1;
275 copygate(p, new);
276 } else if(new->type & Rifc)
277 p->ref++;
278 freeroute(new);
279 break;
280 case Rcontained:
281 addnode(f, &p->mid, new);
282 break;
283 }
284
285 balancetree(cur);
286 }
287
288 #define V4H(a) ((a&0x07ffffff)>>(32-Lroot-5))
289
290 void
291 v4addroute(Fs *f, char *tag, uchar *a, uchar *mask, uchar *gate, int type)
292 {
293 Route *p;
294 ulong sa;
295 ulong m;
296 ulong ea;
297 int h, eh;
298
299 m = nhgetl(mask);
300 sa = nhgetl(a) & m;
301 ea = sa | ~m;
302
303 eh = V4H(ea);
304 for(h=V4H(sa); h<=eh; h++) {
305 p = allocroute(Rv4 | type);
306 p->v4.address = sa;
307 p->v4.endaddress = ea;
308 memmove(p->v4.gate, gate, sizeof(p->v4.gate));
309 memmove(p->tag, tag, sizeof(p->tag));
310
311 wlock(&routelock);
312 addnode(f, &f->v4root[h], p);
313 while((p = f->queue) != nil) {
314 f->queue = p->mid;
315 walkadd(f, &f->v4root[h], p->left);
316 freeroute(p);
317 }
318 wunlock(&routelock);
319 }
320 v4routegeneration++;
321
322 ipifcaddroute(f, Rv4, a, mask, gate, type);
323 }
324
325 #define V6H(a) (((a)[IPllen-1] & 0x07ffffff)>>(32-Lroot-5))
326 #define ISDFLT(a, mask, tag) ((ipcmp((a),v6Unspecified)==0) && (ipcmp((mask),v6Unspecified)==0) && (strcmp((tag), "ra")!=0))
327
328 void
329 v6addroute(Fs *f, char *tag, uchar *a, uchar *mask, uchar *gate, int type)
330 {
331 Route *p;
332 ulong sa[IPllen], ea[IPllen];
333 ulong x, y;
334 int h, eh;
335
336 /*
337 if(ISDFLT(a, mask, tag))
338 f->v6p->cdrouter = -1;
339 */
340
341
342 for(h = 0; h < IPllen; h++){
343 x = nhgetl(a+4*h);
344 y = nhgetl(mask+4*h);
345 sa[h] = x & y;
346 ea[h] = x | ~y;
347 }
348
349 eh = V6H(ea);
350 for(h = V6H(sa); h <= eh; h++) {
351 p = allocroute(type);
352 memmove(p->v6.address, sa, IPaddrlen);
353 memmove(p->v6.endaddress, ea, IPaddrlen);
354 memmove(p->v6.gate, gate, IPaddrlen);
355 memmove(p->tag, tag, sizeof(p->tag));
356
357 wlock(&routelock);
358 addnode(f, &f->v6root[h], p);
359 while((p = f->queue) != nil) {
360 f->queue = p->mid;
361 walkadd(f, &f->v6root[h], p->left);
362 freeroute(p);
363 }
364 wunlock(&routelock);
365 }
366 v6routegeneration++;
367
368 ipifcaddroute(f, 0, a, mask, gate, type);
369 }
370
371 Route**
372 looknode(Route **cur, Route *r)
373 {
374 Route *p;
375
376 for(;;){
377 p = *cur;
378 if(p == 0)
379 return 0;
380
381 switch(rangecompare(r, p)){
382 case Rcontains:
383 return 0;
384 case Rpreceeds:
385 cur = &p->left;
386 break;
387 case Rfollows:
388 cur = &p->right;
389 break;
390 case Rcontained:
391 cur = &p->mid;
392 break;
393 case Requals:
394 return cur;
395 }
396 }
397 }
398
399 void
400 v4delroute(Fs *f, uchar *a, uchar *mask, int dolock)
401 {
402 Route **r, *p;
403 Route rt;
404 int h, eh;
405 ulong m;
406
407 m = nhgetl(mask);
408 rt.v4.address = nhgetl(a) & m;
409 rt.v4.endaddress = rt.v4.address | ~m;
410 rt.type = Rv4;
411
412 eh = V4H(rt.v4.endaddress);
413 for(h=V4H(rt.v4.address); h<=eh; h++) {
414 if(dolock)
415 wlock(&routelock);
416 r = looknode(&f->v4root[h], &rt);
417 if(r) {
418 p = *r;
419 if(--(p->ref) == 0){
420 *r = 0;
421 addqueue(&f->queue, p->left);
422 addqueue(&f->queue, p->mid);
423 addqueue(&f->queue, p->right);
424 freeroute(p);
425 while((p = f->queue) != nil) {
426 f->queue = p->mid;
427 walkadd(f, &f->v4root[h], p->left);
428 freeroute(p);
429 }
430 }
431 }
432 if(dolock)
433 wunlock(&routelock);
434 }
435 v4routegeneration++;
436
437 ipifcremroute(f, Rv4, a, mask);
438 }
439
440 void
441 v6delroute(Fs *f, uchar *a, uchar *mask, int dolock)
442 {
443 Route **r, *p;
444 Route rt;
445 int h, eh;
446 ulong x, y;
447
448 for(h = 0; h < IPllen; h++){
449 x = nhgetl(a+4*h);
450 y = nhgetl(mask+4*h);
451 rt.v6.address[h] = x & y;
452 rt.v6.endaddress[h] = x | ~y;
453 }
454 rt.type = 0;
455
456 eh = V6H(rt.v6.endaddress);
457 for(h=V6H(rt.v6.address); h<=eh; h++) {
458 if(dolock)
459 wlock(&routelock);
460 r = looknode(&f->v6root[h], &rt);
461 if(r) {
462 p = *r;
463 if(--(p->ref) == 0){
464 *r = 0;
465 addqueue(&f->queue, p->left);
466 addqueue(&f->queue, p->mid);
467 addqueue(&f->queue, p->right);
468 freeroute(p);
469 while((p = f->queue) != nil) {
470 f->queue = p->mid;
471 walkadd(f, &f->v6root[h], p->left);
472 freeroute(p);
473 }
474 }
475 }
476 if(dolock)
477 wunlock(&routelock);
478 }
479 v6routegeneration++;
480
481 ipifcremroute(f, 0, a, mask);
482 }
483
484 Route*
485 v4lookup(Fs *f, uchar *a, Conv *c)
486 {
487 Route *p, *q;
488 ulong la;
489 uchar gate[IPaddrlen];
490 Ipifc *ifc;
491
492 if(c != nil && c->r != nil && c->r->ifc != nil && c->rgen == v4routegeneration)
493 return c->r;
494
495 la = nhgetl(a);
496 q = nil;
497 for(p=f->v4root[V4H(la)]; p;)
498 if(la >= p->v4.address) {
499 if(la <= p->v4.endaddress) {
500 q = p;
501 p = p->mid;
502 } else
503 p = p->right;
504 } else
505 p = p->left;
506
507 if(q && (q->ifc == nil || q->ifcid != q->ifc->ifcid)){
508 if(q->type & Rifc) {
509 hnputl(gate+IPv4off, q->v4.address);
510 memmove(gate, v4prefix, IPv4off);
511 } else
512 v4tov6(gate, q->v4.gate);
513 ifc = findipifc(f, gate, q->type);
514 if(ifc == nil)
515 return nil;
516 q->ifc = ifc;
517 q->ifcid = ifc->ifcid;
518 }
519
520 if(c != nil){
521 c->r = q;
522 c->rgen = v4routegeneration;
523 }
524
525 return q;
526 }
527
528 Route*
529 v6lookup(Fs *f, uchar *a, Conv *c)
530 {
531 Route *p, *q;
532 ulong la[IPllen];
533 int h;
534 ulong x, y;
535 uchar gate[IPaddrlen];
536 Ipifc *ifc;
537
538 if(memcmp(a, v4prefix, IPv4off) == 0){
539 q = v4lookup(f, a+IPv4off, c);
540 if(q != nil)
541 return q;
542 }
543
544 if(c != nil && c->r != nil && c->r->ifc != nil && c->rgen == v6routegeneration)
545 return c->r;
546
547 for(h = 0; h < IPllen; h++)
548 la[h] = nhgetl(a+4*h);
549
550 q = 0;
551 for(p=f->v6root[V6H(la)]; p;){
552 for(h = 0; h < IPllen; h++){
553 x = la[h];
554 y = p->v6.address[h];
555 if(x == y)
556 continue;
557 if(x < y){
558 p = p->left;
559 goto next;
560 }
561 break;
562 }
563 for(h = 0; h < IPllen; h++){
564 x = la[h];
565 y = p->v6.endaddress[h];
566 if(x == y)
567 continue;
568 if(x > y){
569 p = p->right;
570 goto next;
571 }
572 break;
573 }
574 q = p;
575 p = p->mid;
576 next: ;
577 }
578
579 if(q && (q->ifc == nil || q->ifcid != q->ifc->ifcid)){
580 if(q->type & Rifc) {
581 for(h = 0; h < IPllen; h++)
582 hnputl(gate+4*h, q->v6.address[h]);
583 ifc = findipifc(f, gate, q->type);
584 } else
585 ifc = findipifc(f, q->v6.gate, q->type);
586 if(ifc == nil)
587 return nil;
588 q->ifc = ifc;
589 q->ifcid = ifc->ifcid;
590 }
591 if(c != nil){
592 c->r = q;
593 c->rgen = v6routegeneration;
594 }
595
596 return q;
597 }
598
599 void
600 routetype(int type, char *p)
601 {
602 memset(p, ' ', 4);
603 p[4] = 0;
604 if(type & Rv4)
605 *p++ = '4';
606 else
607 *p++ = '6';
608 if(type & Rifc)
609 *p++ = 'i';
610 if(type & Runi)
611 *p++ = 'u';
612 else if(type & Rbcast)
613 *p++ = 'b';
614 else if(type & Rmulti)
615 *p++ = 'm';
616 if(type & Rptpt)
617 *p = 'p';
618 }
619
620 static char *rformat = "%-15I %-4M %-15I %4.4s %4.4s %3s\n";
621
622 void
623 convroute(Route *r, uchar *addr, uchar *mask, uchar *gate, char *t, int *nifc)
624 {
625 int i;
626
627 if(r->type & Rv4){
628 memmove(addr, v4prefix, IPv4off);
629 hnputl(addr+IPv4off, r->v4.address);
630 memset(mask, 0xff, IPv4off);
631 hnputl(mask+IPv4off, ~(r->v4.endaddress ^ r->v4.address));
632 memmove(gate, v4prefix, IPv4off);
633 memmove(gate+IPv4off, r->v4.gate, IPv4addrlen);
634 } else {
635 for(i = 0; i < IPllen; i++){
636 hnputl(addr + 4*i, r->v6.address[i]);
637 hnputl(mask + 4*i, ~(r->v6.endaddress[i] ^ r->v6.address[i]));
638 }
639 memmove(gate, r->v6.gate, IPaddrlen);
640 }
641
642 routetype(r->type, t);
643
644 if(r->ifc)
645 *nifc = r->ifc->conv->x;
646 else
647 *nifc = -1;
648 }
649
650 /*
651 * this code is not in rr to reduce stack size
652 */
653 static void
654 sprintroute(Route *r, Routewalk *rw)
655 {
656 int nifc, n;
657 char t[5], *iname, ifbuf[5];
658 uchar addr[IPaddrlen], mask[IPaddrlen], gate[IPaddrlen];
659 char *p;
660
661 convroute(r, addr, mask, gate, t, &nifc);
662 iname = "-";
663 if(nifc != -1) {
664 iname = ifbuf;
665 snprint(ifbuf, sizeof ifbuf, "%d", nifc);
666 }
667 p = seprint(rw->p, rw->e, rformat, addr, mask, gate, t, r->tag, iname);
668 if(rw->o < 0){
669 n = p - rw->p;
670 if(n > -rw->o){
671 memmove(rw->p, rw->p-rw->o, n+rw->o);
672 rw->p = p + rw->o;
673 }
674 rw->o += n;
675 } else
676 rw->p = p;
677 }
678
679 /*
680 * recurse descending tree, applying the function in Routewalk
681 */
682 static int
683 rr(Route *r, Routewalk *rw)
684 {
685 int h;
686
687 if(rw->e <= rw->p)
688 return 0;
689 if(r == nil)
690 return 1;
691
692 if(rr(r->left, rw) == 0)
693 return 0;
694
695 if(r->type & Rv4)
696 h = V4H(r->v4.address);
697 else
698 h = V6H(r->v6.address);
699
700 if(h == rw->h)
701 rw->walk(r, rw);
702
703 if(rr(r->mid, rw) == 0)
704 return 0;
705
706 return rr(r->right, rw);
707 }
708
709 void
710 ipwalkroutes(Fs *f, Routewalk *rw)
711 {
712 rlock(&routelock);
713 if(rw->e > rw->p) {
714 for(rw->h = 0; rw->h < nelem(f->v4root); rw->h++)
715 if(rr(f->v4root[rw->h], rw) == 0)
716 break;
717 }
718 if(rw->e > rw->p) {
719 for(rw->h = 0; rw->h < nelem(f->v6root); rw->h++)
720 if(rr(f->v6root[rw->h], rw) == 0)
721 break;
722 }
723 runlock(&routelock);
724 }
725
726 long
727 routeread(Fs *f, char *p, ulong offset, int n)
728 {
729 Routewalk rw;
730
731 rw.p = p;
732 rw.e = p+n;
733 rw.o = -offset;
734 rw.walk = sprintroute;
735
736 ipwalkroutes(f, &rw);
737
738 return rw.p - p;
739 }
740
741 /*
742 * this code is not in routeflush to reduce stack size
743 */
744 void
745 delroute(Fs *f, Route *r, int dolock)
746 {
747 uchar addr[IPaddrlen];
748 uchar mask[IPaddrlen];
749 uchar gate[IPaddrlen];
750 char t[5];
751 int nifc;
752
753 convroute(r, addr, mask, gate, t, &nifc);
754 if(r->type & Rv4)
755 v4delroute(f, addr+IPv4off, mask+IPv4off, dolock);
756 else
757 v6delroute(f, addr, mask, dolock);
758 }
759
760 /*
761 * recurse until one route is deleted
762 * returns 0 if nothing is deleted, 1 otherwise
763 */
764 int
765 routeflush(Fs *f, Route *r, char *tag)
766 {
767 if(r == nil)
768 return 0;
769 if(routeflush(f, r->mid, tag))
770 return 1;
771 if(routeflush(f, r->left, tag))
772 return 1;
773 if(routeflush(f, r->right, tag))
774 return 1;
775 if((r->type & Rifc) == 0){
776 if(tag == nil || strncmp(tag, r->tag, sizeof(r->tag)) == 0){
777 delroute(f, r, 0);
778 return 1;
779 }
780 }
781 return 0;
782 }
783
784 long
785 routewrite(Fs *f, Chan *c, char *p, int n)
786 {
787 int h, changed;
788 char *tag;
789 Cmdbuf *cb;
790 uchar addr[IPaddrlen];
791 uchar mask[IPaddrlen];
792 uchar gate[IPaddrlen];
793 IPaux *a, *na;
794
795 cb = parsecmd(p, n);
796 if(waserror()){
797 free(cb);
798 nexterror();
799 }
800
801 if(strcmp(cb->f[0], "flush") == 0){
802 tag = cb->f[1];
803 for(h = 0; h < nelem(f->v4root); h++)
804 for(changed = 1; changed;){
805 wlock(&routelock);
806 changed = routeflush(f, f->v4root[h], tag);
807 wunlock(&routelock);
808 }
809 for(h = 0; h < nelem(f->v6root); h++)
810 for(changed = 1; changed;){
811 wlock(&routelock);
812 changed = routeflush(f, f->v6root[h], tag);
813 wunlock(&routelock);
814 }
815 } else if(strcmp(cb->f[0], "remove") == 0){
816 if(cb->nf < 3)
817 error(Ebadarg);
818 if (parseip(addr, cb->f[1]) == -1)
819 error(Ebadip);
820 parseipmask(mask, cb->f[2]);
821 if(memcmp(addr, v4prefix, IPv4off) == 0)
822 v4delroute(f, addr+IPv4off, mask+IPv4off, 1);
823 else
824 v6delroute(f, addr, mask, 1);
825 } else if(strcmp(cb->f[0], "add") == 0){
826 if(cb->nf < 4)
827 error(Ebadarg);
828 if(parseip(addr, cb->f[1]) == -1 ||
829 parseip(gate, cb->f[3]) == -1)
830 error(Ebadip);
831 parseipmask(mask, cb->f[2]);
832 tag = "none";
833 if(c != nil){
834 a = c->aux;
835 tag = a->tag;
836 }
837 if(memcmp(addr, v4prefix, IPv4off) == 0)
838 v4addroute(f, tag, addr+IPv4off, mask+IPv4off, gate+IPv4off, 0);
839 else
840 v6addroute(f, tag, addr, mask, gate, 0);
841 } else if(strcmp(cb->f[0], "tag") == 0) {
842 if(cb->nf < 2)
843 error(Ebadarg);
844
845 a = c->aux;
846 na = newipaux(a->owner, cb->f[1]);
847 c->aux = na;
848 free(a);
849 }
850
851 poperror();
852 free(cb);
853 return n;
854 }