vx32

iproute.c (14918B)

---

 #include	"u.h"
 #include	"lib.h"
 #include	"mem.h"
 #include	"dat.h"
 #include	"fns.h"
 #include	"error.h"
 
 #include	"ip.h"
 
 static void	walkadd(Fs*, Route**, Route*);
 static void	addnode(Fs*, Route**, Route*);
 static void	calcd(Route*);
 
 /* these are used for all instances of IP */
 static Route*	v4freelist;
 static Route*	v6freelist;
 static RWlock	routelock;
 static ulong	v4routegeneration, v6routegeneration;
 
 static void
 freeroute(Route *r)
 {
 	Route **l;
 
 	r->left = nil;
 	r->right = nil;
 	if(r->type & Rv4)
 		l = &v4freelist;
 	else
 		l = &v6freelist;
 	r->mid = *l;
 	*l = r;
 }
 
 static Route*
 allocroute(int type)
 {
 	Route *r;
 	int n;
 	Route **l;
 
 	if(type & Rv4){
 		n = sizeof(RouteTree) + sizeof(V4route);
 		l = &v4freelist;
 	} else {
 		n = sizeof(RouteTree) + sizeof(V6route);
 		l = &v6freelist;
 	}
 
 	r = *l;
 	if(r != nil){
 		*l = r->mid;
 	} else {
 		r = malloc(n);
 		if(r == nil)
 			panic("out of routing nodes");
 	}
 	memset(r, 0, n);
 	r->type = type;
 	r->ifc = nil;
 	r->ref = 1;
 
 	return r;
 }
 
 static void
 addqueue(Route **q, Route *r)
 {
 	Route *l;
 
 	if(r == nil)
 		return;
 
 	l = allocroute(r->type);
 	l->mid = *q;
 	*q = l;
 	l->left = r;
 }
 
 /*
  *   compare 2 v6 addresses
  */
 static int
 lcmp(ulong *a, ulong *b)
 {
 	int i;
 
 	for(i = 0; i < IPllen; i++){
 		if(a[i] > b[i])
 			return 1;
 		if(a[i] < b[i])
 			return -1;
 	}
 	return 0;
 }
 
 /*
  *  compare 2 v4 or v6 ranges
  */
 enum
 {
 	Rpreceeds,
 	Rfollows,
 	Requals,
 	Rcontains,
 	Rcontained,
 };
 
 static int
 rangecompare(Route *a, Route *b)
 {
 	if(a->type & Rv4){
 		if(a->v4.endaddress < b->v4.address)
 			return Rpreceeds;
 
 		if(a->v4.address > b->v4.endaddress)
 			return Rfollows;
 
 		if(a->v4.address <= b->v4.address
 		&& a->v4.endaddress >= b->v4.endaddress){
 			if(a->v4.address == b->v4.address
 			&& a->v4.endaddress == b->v4.endaddress)
 				return Requals;
 			return Rcontains;
 		}
 		return Rcontained;
 	}
 
 	if(lcmp(a->v6.endaddress, b->v6.address) < 0)
 		return Rpreceeds;
 
 	if(lcmp(a->v6.address, b->v6.endaddress) > 0)
 		return Rfollows;
 
 	if(lcmp(a->v6.address, b->v6.address) <= 0
 	&& lcmp(a->v6.endaddress, b->v6.endaddress) >= 0){
 		if(lcmp(a->v6.address, b->v6.address) == 0
 		&& lcmp(a->v6.endaddress, b->v6.endaddress) == 0)
 				return Requals;
 		return Rcontains;
 	}
 
 	return Rcontained;
 }
 
 static void
 copygate(Route *old, Route *new)
 {
 	if(new->type & Rv4)
 		memmove(old->v4.gate, new->v4.gate, IPv4addrlen);
 	else
 		memmove(old->v6.gate, new->v6.gate, IPaddrlen);
 }
 
 /*
  *  walk down a tree adding nodes back in
  */
 static void
 walkadd(Fs *f, Route **root, Route *p)
 {
 	Route *l, *r;
 
 	l = p->left;
 	r = p->right;
 	p->left = 0;
 	p->right = 0;
 	addnode(f, root, p);
 	if(l)
 		walkadd(f, root, l);
 	if(r)
 		walkadd(f, root, r);
 }
 
 /*
  *  calculate depth
  */
 static void
 calcd(Route *p)
 {
 	Route *q;
 	int d;
 
 	if(p) {
 		d = 0;
 		q = p->left;
 		if(q)
 			d = q->depth;
 		q = p->right;
 		if(q && q->depth > d)
 			d = q->depth;
 		q = p->mid;
 		if(q && q->depth > d)
 			d = q->depth;
 		p->depth = d+1;
 	}
 }
 
 /*
  *  balance the tree at the current node
  */
 static void
 balancetree(Route **cur)
 {
 	Route *p, *l, *r;
 	int dl, dr;
 
 	/*
 	 * if left and right are
 	 * too out of balance,
 	 * rotate tree node
 	 */
 	p = *cur;
 	dl = 0; if((l = p->left) != nil) dl = l->depth;
 	dr = 0; if((r = p->right) != nil) dr = r->depth;
 
 	if(dl > dr+1) {
 		p->left = l->right;
 		l->right = p;
 		*cur = l;
 		calcd(p);
 		calcd(l);
 	} else
 	if(dr > dl+1) {
 		p->right = r->left;
 		r->left = p;
 		*cur = r;
 		calcd(p);
 		calcd(r);
 	} else
 		calcd(p);
 }
 
 /*
  *  add a new node to the tree
  */
 static void
 addnode(Fs *f, Route **cur, Route *new)
 {
 	Route *p;
 
 	p = *cur;
 	if(p == 0) {
 		*cur = new;
 		new->depth = 1;
 		return;
 	}
 
 	switch(rangecompare(new, p)){
 	case Rpreceeds:
 		addnode(f, &p->left, new);
 		break;
 	case Rfollows:
 		addnode(f, &p->right, new);
 		break;
 	case Rcontains:
 		/*
 		 *  if new node is superset
 		 *  of tree node,
 		 *  replace tree node and
 		 *  queue tree node to be
 		 *  merged into root.
 		 */
 		*cur = new;
 		new->depth = 1;
 		addqueue(&f->queue, p);
 		break;
 	case Requals:
 		/*
 		 *  supercede the old entry if the old one isn't
 		 *  a local interface.
 		 */
 		if((p->type & Rifc) == 0){
 			p->type = new->type;
 			p->ifcid = -1;
 			copygate(p, new);
 		} else if(new->type & Rifc)
 			p->ref++;
 		freeroute(new);
 		break;
 	case Rcontained:
 		addnode(f, &p->mid, new);
 		break;
 	}
 	
 	balancetree(cur);
 }
 
 #define	V4H(a)	((a&0x07ffffff)>>(32-Lroot-5))
 
 void
 v4addroute(Fs *f, char *tag, uchar *a, uchar *mask, uchar *gate, int type)
 {
 	Route *p;
 	ulong sa;
 	ulong m;
 	ulong ea;
 	int h, eh;
 
 	m = nhgetl(mask);
 	sa = nhgetl(a) & m;
 	ea = sa | ~m;
 
 	eh = V4H(ea);
 	for(h=V4H(sa); h<=eh; h++) {
 		p = allocroute(Rv4 | type);
 		p->v4.address = sa;
 		p->v4.endaddress = ea;
 		memmove(p->v4.gate, gate, sizeof(p->v4.gate));
 		memmove(p->tag, tag, sizeof(p->tag));
 
 		wlock(&routelock);
 		addnode(f, &f->v4root[h], p);
 		while((p = f->queue) != nil) {
 			f->queue = p->mid;
 			walkadd(f, &f->v4root[h], p->left);
 			freeroute(p);
 		}
 		wunlock(&routelock);
 	}
 	v4routegeneration++;
 
 	ipifcaddroute(f, Rv4, a, mask, gate, type);
 }
 
 #define	V6H(a)	(((a)[IPllen-1] & 0x07ffffff)>>(32-Lroot-5))
 #define ISDFLT(a, mask, tag) ((ipcmp((a),v6Unspecified)==0) && (ipcmp((mask),v6Unspecified)==0) && (strcmp((tag), "ra")!=0))
 
 void
 v6addroute(Fs *f, char *tag, uchar *a, uchar *mask, uchar *gate, int type)
 {
 	Route *p;
 	ulong sa[IPllen], ea[IPllen];
 	ulong x, y;
 	int h, eh;
 
 	/*
 	if(ISDFLT(a, mask, tag))
 		f->v6p->cdrouter = -1;
 	*/
 
 
 	for(h = 0; h < IPllen; h++){
 		x = nhgetl(a+4*h);
 		y = nhgetl(mask+4*h);
 		sa[h] = x & y;
 		ea[h] = x | ~y;
 	}
 
 	eh = V6H(ea);
 	for(h = V6H(sa); h <= eh; h++) {
 		p = allocroute(type);
 		memmove(p->v6.address, sa, IPaddrlen);
 		memmove(p->v6.endaddress, ea, IPaddrlen);
 		memmove(p->v6.gate, gate, IPaddrlen);
 		memmove(p->tag, tag, sizeof(p->tag));
 
 		wlock(&routelock);
 		addnode(f, &f->v6root[h], p);
 		while((p = f->queue) != nil) {
 			f->queue = p->mid;
 			walkadd(f, &f->v6root[h], p->left);
 			freeroute(p);
 		}
 		wunlock(&routelock);
 	}
 	v6routegeneration++;
 
 	ipifcaddroute(f, 0, a, mask, gate, type);
 }
 
 Route**
 looknode(Route **cur, Route *r)
 {
 	Route *p;
 
 	for(;;){
 		p = *cur;
 		if(p == 0)
 			return 0;
 	
 		switch(rangecompare(r, p)){
 		case Rcontains:
 			return 0;
 		case Rpreceeds:
 			cur = &p->left;
 			break;
 		case Rfollows:
 			cur = &p->right;
 			break;
 		case Rcontained:
 			cur = &p->mid;
 			break;
 		case Requals:
 			return cur;
 		}
 	}
 }
 
 void
 v4delroute(Fs *f, uchar *a, uchar *mask, int dolock)
 {
 	Route **r, *p;
 	Route rt;
 	int h, eh;
 	ulong m;
 
 	m = nhgetl(mask);
 	rt.v4.address = nhgetl(a) & m;
 	rt.v4.endaddress = rt.v4.address | ~m;
 	rt.type = Rv4;
 
 	eh = V4H(rt.v4.endaddress);
 	for(h=V4H(rt.v4.address); h<=eh; h++) {
 		if(dolock)
 			wlock(&routelock);
 		r = looknode(&f->v4root[h], &rt);
 		if(r) {
 			p = *r;
 			if(--(p->ref) == 0){
 				*r = 0;
 				addqueue(&f->queue, p->left);
 				addqueue(&f->queue, p->mid);
 				addqueue(&f->queue, p->right);
 				freeroute(p);
 				while((p = f->queue) != nil) {
 					f->queue = p->mid;
 					walkadd(f, &f->v4root[h], p->left);
 					freeroute(p);
 				}
 			}
 		}
 		if(dolock)
 			wunlock(&routelock);
 	}
 	v4routegeneration++;
 
 	ipifcremroute(f, Rv4, a, mask);
 }
 
 void
 v6delroute(Fs *f, uchar *a, uchar *mask, int dolock)
 {
 	Route **r, *p;
 	Route rt;
 	int h, eh;
 	ulong x, y;
 
 	for(h = 0; h < IPllen; h++){
 		x = nhgetl(a+4*h);
 		y = nhgetl(mask+4*h);
 		rt.v6.address[h] = x & y;
 		rt.v6.endaddress[h] = x | ~y;
 	}
 	rt.type = 0;
 
 	eh = V6H(rt.v6.endaddress);
 	for(h=V6H(rt.v6.address); h<=eh; h++) {
 		if(dolock)
 			wlock(&routelock);
 		r = looknode(&f->v6root[h], &rt);
 		if(r) {
 			p = *r;
 			if(--(p->ref) == 0){
 				*r = 0;
 				addqueue(&f->queue, p->left);
 				addqueue(&f->queue, p->mid);
 				addqueue(&f->queue, p->right);
 				freeroute(p);
 				while((p = f->queue) != nil) {
 					f->queue = p->mid;
 					walkadd(f, &f->v6root[h], p->left);
 					freeroute(p);
 				}
 			}
 		}
 		if(dolock)
 			wunlock(&routelock);
 	}
 	v6routegeneration++;
 
 	ipifcremroute(f, 0, a, mask);
 }
 
 Route*
 v4lookup(Fs *f, uchar *a, Conv *c)
 {
 	Route *p, *q;
 	ulong la;
 	uchar gate[IPaddrlen];
 	Ipifc *ifc;
 
 	if(c != nil && c->r != nil && c->r->ifc != nil && c->rgen == v4routegeneration)
 		return c->r;
 
 	la = nhgetl(a);
 	q = nil;
 	for(p=f->v4root[V4H(la)]; p;)
 		if(la >= p->v4.address) {
 			if(la <= p->v4.endaddress) {
 				q = p;
 				p = p->mid;
 			} else
 				p = p->right;
 		} else
 			p = p->left;
 
 	if(q && (q->ifc == nil || q->ifcid != q->ifc->ifcid)){
 		if(q->type & Rifc) {
 			hnputl(gate+IPv4off, q->v4.address);
 			memmove(gate, v4prefix, IPv4off);
 		} else
 			v4tov6(gate, q->v4.gate);
 		ifc = findipifc(f, gate, q->type);
 		if(ifc == nil)
 			return nil;
 		q->ifc = ifc;
 		q->ifcid = ifc->ifcid;
 	}
 
 	if(c != nil){
 		c->r = q;
 		c->rgen = v4routegeneration;
 	}
 
 	return q;
 }
 
 Route*
 v6lookup(Fs *f, uchar *a, Conv *c)
 {
 	Route *p, *q;
 	ulong la[IPllen];
 	int h;
 	ulong x, y;
 	uchar gate[IPaddrlen];
 	Ipifc *ifc;
 
 	if(memcmp(a, v4prefix, IPv4off) == 0){
 		q = v4lookup(f, a+IPv4off, c);
 		if(q != nil)
 			return q;
 	}
 
 	if(c != nil && c->r != nil && c->r->ifc != nil && c->rgen == v6routegeneration)
 		return c->r;
 
 	for(h = 0; h < IPllen; h++)
 		la[h] = nhgetl(a+4*h);
 
 	q = 0;
 	for(p=f->v6root[V6H(la)]; p;){
 		for(h = 0; h < IPllen; h++){
 			x = la[h];
 			y = p->v6.address[h];
 			if(x == y)
 				continue;
 			if(x < y){
 				p = p->left;
 				goto next;
 			}
 			break;
 		}
 		for(h = 0; h < IPllen; h++){
 			x = la[h];
 			y = p->v6.endaddress[h];
 			if(x == y)
 				continue;
 			if(x > y){
 				p = p->right;
 				goto next;
 			}
 			break;
 		}
 		q = p;
 		p = p->mid;
 next:		;
 	}
 
 	if(q && (q->ifc == nil || q->ifcid != q->ifc->ifcid)){
 		if(q->type & Rifc) {
 			for(h = 0; h < IPllen; h++)
 				hnputl(gate+4*h, q->v6.address[h]);
 			ifc = findipifc(f, gate, q->type);
 		} else
 			ifc = findipifc(f, q->v6.gate, q->type);
 		if(ifc == nil)
 			return nil;
 		q->ifc = ifc;
 		q->ifcid = ifc->ifcid;
 	}
 	if(c != nil){
 		c->r = q;
 		c->rgen = v6routegeneration;
 	}
 	
 	return q;
 }
 
 void
 routetype(int type, char *p)
 {
 	memset(p, ' ', 4);
 	p[4] = 0;
 	if(type & Rv4)
 		*p++ = '4';
 	else
 		*p++ = '6';
 	if(type & Rifc)
 		*p++ = 'i';
 	if(type & Runi)
 		*p++ = 'u';
 	else if(type & Rbcast)
 		*p++ = 'b';
 	else if(type & Rmulti)
 		*p++ = 'm';
 	if(type & Rptpt)
 		*p = 'p';
 }
 
 static char *rformat = "%-15I %-4M %-15I %4.4s %4.4s %3s\n";
 
 void
 convroute(Route *r, uchar *addr, uchar *mask, uchar *gate, char *t, int *nifc)
 {
 	int i;
 
 	if(r->type & Rv4){
 		memmove(addr, v4prefix, IPv4off);
 		hnputl(addr+IPv4off, r->v4.address);
 		memset(mask, 0xff, IPv4off);
 		hnputl(mask+IPv4off, ~(r->v4.endaddress ^ r->v4.address));
 		memmove(gate, v4prefix, IPv4off);
 		memmove(gate+IPv4off, r->v4.gate, IPv4addrlen);
 	} else {
 		for(i = 0; i < IPllen; i++){
 			hnputl(addr + 4*i, r->v6.address[i]);
 			hnputl(mask + 4*i, ~(r->v6.endaddress[i] ^ r->v6.address[i]));
 		}
 		memmove(gate, r->v6.gate, IPaddrlen);
 	}
 
 	routetype(r->type, t);
 
 	if(r->ifc)
 		*nifc = r->ifc->conv->x;
 	else
 		*nifc = -1;
 }
 
 /*
  *  this code is not in rr to reduce stack size
  */
 static void
 sprintroute(Route *r, Routewalk *rw)
 {
 	int nifc, n;
 	char t[5], *iname, ifbuf[5];
 	uchar addr[IPaddrlen], mask[IPaddrlen], gate[IPaddrlen];
 	char *p;
 
 	convroute(r, addr, mask, gate, t, &nifc);
 	iname = "-";
 	if(nifc != -1) {
 		iname = ifbuf;
 		snprint(ifbuf, sizeof ifbuf, "%d", nifc);
 	}
 	p = seprint(rw->p, rw->e, rformat, addr, mask, gate, t, r->tag, iname);
 	if(rw->o < 0){
 		n = p - rw->p;
 		if(n > -rw->o){
 			memmove(rw->p, rw->p-rw->o, n+rw->o);
 			rw->p = p + rw->o;
 		}
 		rw->o += n;
 	} else
 		rw->p = p;
 }
 
 /*
  *  recurse descending tree, applying the function in Routewalk
  */
 static int
 rr(Route *r, Routewalk *rw)
 {
 	int h;
 
 	if(rw->e <= rw->p)
 		return 0;
 	if(r == nil)
 		return 1;
 
 	if(rr(r->left, rw) == 0)
 		return 0;
 
 	if(r->type & Rv4)
 		h = V4H(r->v4.address);
 	else
 		h = V6H(r->v6.address);
 
 	if(h == rw->h)
 		rw->walk(r, rw);
 
 	if(rr(r->mid, rw) == 0)
 		return 0;
 
 	return rr(r->right, rw);
 }
 
 void
 ipwalkroutes(Fs *f, Routewalk *rw)
 {
 	rlock(&routelock);
 	if(rw->e > rw->p) {
 		for(rw->h = 0; rw->h < nelem(f->v4root); rw->h++)
 			if(rr(f->v4root[rw->h], rw) == 0)
 				break;
 	}
 	if(rw->e > rw->p) {
 		for(rw->h = 0; rw->h < nelem(f->v6root); rw->h++)
 			if(rr(f->v6root[rw->h], rw) == 0)
 				break;
 	}
 	runlock(&routelock);
 }
 
 long
 routeread(Fs *f, char *p, ulong offset, int n)
 {
 	Routewalk rw;
 
 	rw.p = p;
 	rw.e = p+n;
 	rw.o = -offset;
 	rw.walk = sprintroute;
 
 	ipwalkroutes(f, &rw);
 
 	return rw.p - p;
 }
 
 /*
  *  this code is not in routeflush to reduce stack size
  */
 void
 delroute(Fs *f, Route *r, int dolock)
 {
 	uchar addr[IPaddrlen];
 	uchar mask[IPaddrlen];
 	uchar gate[IPaddrlen];
 	char t[5];
 	int nifc;
 
 	convroute(r, addr, mask, gate, t, &nifc);
 	if(r->type & Rv4)
 		v4delroute(f, addr+IPv4off, mask+IPv4off, dolock);
 	else
 		v6delroute(f, addr, mask, dolock);
 }
 
 /*
  *  recurse until one route is deleted
  *    returns 0 if nothing is deleted, 1 otherwise
  */
 int
 routeflush(Fs *f, Route *r, char *tag)
 {
 	if(r == nil)
 		return 0;
 	if(routeflush(f, r->mid, tag))
 		return 1;
 	if(routeflush(f, r->left, tag))
 		return 1;
 	if(routeflush(f, r->right, tag))
 		return 1;
 	if((r->type & Rifc) == 0){
 		if(tag == nil || strncmp(tag, r->tag, sizeof(r->tag)) == 0){
 			delroute(f, r, 0);
 			return 1;
 		}
 	}
 	return 0;
 }
 
 long
 routewrite(Fs *f, Chan *c, char *p, int n)
 {
 	int h, changed;
 	char *tag;
 	Cmdbuf *cb;
 	uchar addr[IPaddrlen];
 	uchar mask[IPaddrlen];
 	uchar gate[IPaddrlen];
 	IPaux *a, *na;
 
 	cb = parsecmd(p, n);
 	if(waserror()){
 		free(cb);
 		nexterror();
 	}
 
 	if(strcmp(cb->f[0], "flush") == 0){
 		tag = cb->f[1];
 		for(h = 0; h < nelem(f->v4root); h++)
 			for(changed = 1; changed;){
 				wlock(&routelock);
 				changed = routeflush(f, f->v4root[h], tag);
 				wunlock(&routelock);
 			}
 		for(h = 0; h < nelem(f->v6root); h++)
 			for(changed = 1; changed;){
 				wlock(&routelock);
 				changed = routeflush(f, f->v6root[h], tag);
 				wunlock(&routelock);
 			}
 	} else if(strcmp(cb->f[0], "remove") == 0){
 		if(cb->nf < 3)
 			error(Ebadarg);
 		if (parseip(addr, cb->f[1]) == -1)
 			error(Ebadip);
 		parseipmask(mask, cb->f[2]);
 		if(memcmp(addr, v4prefix, IPv4off) == 0)
 			v4delroute(f, addr+IPv4off, mask+IPv4off, 1);
 		else
 			v6delroute(f, addr, mask, 1);
 	} else if(strcmp(cb->f[0], "add") == 0){
 		if(cb->nf < 4)
 			error(Ebadarg);
 		if(parseip(addr, cb->f[1]) == -1 ||
 		    parseip(gate, cb->f[3]) == -1)
 			error(Ebadip);
 		parseipmask(mask, cb->f[2]);
 		tag = "none";
 		if(c != nil){
 			a = c->aux;
 			tag = a->tag;
 		}
 		if(memcmp(addr, v4prefix, IPv4off) == 0)
 			v4addroute(f, tag, addr+IPv4off, mask+IPv4off, gate+IPv4off, 0);
 		else
 			v6addroute(f, tag, addr, mask, gate, 0);
 	} else if(strcmp(cb->f[0], "tag") == 0) {
 		if(cb->nf < 2)
 			error(Ebadarg);
 
 		a = c->aux;
 		na = newipaux(a->owner, cb->f[1]);
 		c->aux = na;
 		free(a);
 	}
 
 	poperror();
 	free(cb);
 	return n;
 }