add in the inferno stack.
[akaros.git] / kern / src / net / iproute.c
1 #include        "u.h"
2 #include        "../port/lib.h"
3 #include        "mem.h"
4 #include        "dat.h"
5 #include        "fns.h"
6 #include        "../port/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 Route*  v4freelist;
16 Route*  v6freelist;
17 RWlock  routelock;
18 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) dl = l->depth;
214         dr = 0; if(r = p->right) 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) {
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) {
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) {
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) {
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 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                 parseip(addr, cb->f[1]);
819                 parseipmask(mask, cb->f[2]);
820                 if(memcmp(addr, v4prefix, IPv4off) == 0)
821                         v4delroute(f, addr+IPv4off, mask+IPv4off, 1);
822                 else
823                         v6delroute(f, addr, mask, 1);
824         } else if(strcmp(cb->f[0], "add") == 0){
825                 if(cb->nf < 4)
826                         error(Ebadarg);
827                 parseip(addr, cb->f[1]);
828                 parseipmask(mask, cb->f[2]);
829                 parseip(gate, cb->f[3]);
830                 tag = "none";
831                 if(c != nil){
832                         a = c->aux;
833                         tag = a->tag;
834                 }
835                 if(memcmp(addr, v4prefix, IPv4off) == 0)
836                         v4addroute(f, tag, addr+IPv4off, mask+IPv4off, gate+IPv4off, 0);
837                 else
838                         v6addroute(f, tag, addr, mask, gate, 0);
839         } else if(strcmp(cb->f[0], "tag") == 0) {
840                 if(cb->nf < 2)
841                         error(Ebadarg);
842
843                 a = c->aux;
844                 na = newipaux(a->owner, cb->f[1]);
845                 c->aux = na;
846                 free(a);
847         }
848
849         poperror();
850         free(cb);
851         return n;
852 }