#include	"u.h"#include	"../port/lib.h"#include	"mem.h"#include	"dat.h"#include	"fns.h"#include	"../port/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 */Route*	v4freelist;Route*	v6freelist;RWlock	routelock;ulong	v4routegeneration, v6routegeneration; static voidfreeroute(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 voidaddqueue(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 intlcmp(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 intrangecompare(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 voidcopygate(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 voidwalkadd(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 voidcalcd(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 voidbalancetree(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) dl = l->depth;	dr = 0; if(r = p->right) 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 voidaddnode(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)) voidv4addroute(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) {			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)) voidv6addroute(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) {			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;		}	}} voidv4delroute(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) {					f->queue = p->mid;					walkadd(f, &f->v4root[h], p->left);					freeroute(p);				}			}		}		if(dolock)			wunlock(&routelock);	}	v4routegeneration++; 	ipifcremroute(f, Rv4, a, mask);} voidv6delroute(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) {					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;

Lines 1–500 of 852. Load more