devip: no more wandering routes

Before, it was possible to add routes before
the interface existed.

The routes would look for their interface lazily
as the route was looked up, but this leads to
all kinds of hard to explain behaviour when
a interface goes away and the routes start
wandering to a different interface on their
own which they will stick to when a new
interface comes up that would match the route
better.

Instead, we have routes always associated
to their desination interface and remove
the routes when the interface gets unbound.

It is no longer possible to add routes for
interfaces that do not exist.

This is easier to reason about behaviour as
well as allows us to get rid of canrlock(ifc)
in findipifc().

All routes inside the routing tree are now
by definition up-to-date (as long as we
hold the routelock).

Callers of v4lookup()/v6lookup() still should
check if the ifcid of the interface still
matches the route once they have acquired
the interface lock.

6 files changed, 124 insertions, 145 deletions

diff --git a/sys/src/9/ip/arp.c b/sys/src/9/ip/arp.c
index 9c51a48a1..a030e75a4 100644
--- a/sys/src/9/ip/arp.c
+++ b/sys/src/9/ip/arp.c
@@ -672,7 +672,7 @@ drop(Fs *f, Block *bp)
 		else
 			r = v6lookup(f, ((Ip6hdr*)bp->rp)->src, ((Ip6hdr*)bp->rp)->dst, &rh);
 		if(r != nil && (ifc = r->ifc) != nil && canrlock(ifc)){
-			if(!waserror()){
+			if(ifc->ifcid == r->ifcid && !waserror()){
 				if((bp->rp[0]&0xF0) == IP_VER4)
 					icmpnohost(f, ifc, bp, &rh);
 				else
diff --git a/sys/src/9/ip/ip.c b/sys/src/9/ip/ip.c
index a8d2e3836..4d65265e8 100644
--- a/sys/src/9/ip/ip.c
+++ b/sys/src/9/ip/ip.c
@@ -131,7 +131,7 @@ ipoput4(Fs *f, Block *bp, Ipifc *gating, int ttl, int tos, Routehint *rh)
 		runlock(ifc);
 		nexterror();
 	}
-	if(ifc->m == nil)
+	if(ifc->m == nil || ifc->ifcid != r->ifcid)
 		goto raise;
 
 	medialen = ifc->maxtu - ifc->m->hsize;
diff --git a/sys/src/9/ip/ip.h b/sys/src/9/ip/ip.h
index 5a6820f7d..110bc725b 100644
--- a/sys/src/9/ip/ip.h
+++ b/sys/src/9/ip/ip.h
@@ -630,6 +630,7 @@ extern Route*	v4source(Fs *f, uchar *a, uchar *s);
 extern Route*	v6source(Fs *f, uchar *a, uchar *s);
 extern long	routeread(Fs *f, char*, ulong, int);
 extern long	routewrite(Fs *f, Chan*, char*, int);
+extern void	flushrouteifc(Fs *f, Ipifc *ifc);
 extern void	routetype(int type, char p[8]);
 
 /*
diff --git a/sys/src/9/ip/ipifc.c b/sys/src/9/ip/ipifc.c
index c16e0a660..ce095b52b 100644
--- a/sys/src/9/ip/ipifc.c
+++ b/sys/src/9/ip/ipifc.c
@@ -183,7 +183,7 @@ ipifcbind(Conv *c, char **argv, int argc)
 		c->inuse++;
 
 	/* any ancillary structures (like routes) no longer pertain */
-	ifc->ifcid++;
+	flushrouteifc(c->p->f, ifc);
 
 	/* reopen all the queues closed by a previous unbind */
 	qreopen(c->rq);
@@ -201,6 +201,8 @@ ipifcbind(Conv *c, char **argv, int argc)
 static char*
 ipifcunbindmedium(Ipifc *ifc, Medium *m)
 {
+	Conv *c = ifc->conv;
+
 	if(m == nil || m == &unboundmedium)
 		return Eunbound;
 
@@ -212,12 +214,12 @@ ipifcunbindmedium(Ipifc *ifc, Medium *m)
 	if(m->unbind != nil){
 		ifc->m = &unboundmedium;	/* fake until unbound */
 		wunlock(ifc);
-		qunlock(ifc->conv);
+		qunlock(c);
 		if(!waserror()){
 			(*m->unbind)(ifc);
 			poperror();
 		}
-		qlock(ifc->conv);
+		qlock(c);
 		wlock(ifc);
 	}
 
@@ -227,17 +229,17 @@ ipifcunbindmedium(Ipifc *ifc, Medium *m)
 	ifc->reassemble = 0;
 
 	/* close queues to stop queuing of packets */
-	qclose(ifc->conv->rq);
-	qclose(ifc->conv->wq);
-	qclose(ifc->conv->sq);
+	qclose(c->rq);
+	qclose(c->wq);
+	qclose(c->sq);
 
 	/* dissociate routes */
-	ifc->ifcid++;
+	flushrouteifc(c->p->f, ifc);
 	ifc->m = nil;
 	ifc->arg = nil;
 
 	if(m->unbindonclose == 0)
-		ifc->conv->inuse--;
+		c->inuse--;
 
 	return nil;
 }
@@ -1246,8 +1248,7 @@ findipifc(Fs *f, uchar *local, uchar *remote, int type)
 	xspec = 0;
 	for(cp = f->ipifc->conv; *cp != nil; cp++){
 		ifc = (Ipifc*)(*cp)->ptcl;
-		if(!canrlock(ifc))
-			continue;
+		rlock(ifc);
 		for(lifc = ifc->lifc; lifc != nil; lifc = lifc->next){
 			if(type & Runi){
 				if(ipcmp(remote, lifc->local) == 0)
@@ -1258,7 +1259,8 @@ findipifc(Fs *f, uchar *local, uchar *remote, int type)
 			}
 			maskip(remote, lifc->mask, gnet);
 			if(ipcmp(gnet, lifc->net) == 0){
-				spec = comprefixlen(remote, lifc->local, IPaddrlen);
+				spec = comprefixlen(remote, lifc->local, IPaddrlen)<<8;
+				spec += comprefixlen(local, lifc->local, IPaddrlen);
 				if(spec > xspec){
 					x = ifc;
 					xifcid = ifc->ifcid;
@@ -1268,7 +1270,8 @@ findipifc(Fs *f, uchar *local, uchar *remote, int type)
 		}
 		runlock(ifc);
 	}
-	if(x != nil && canrlock(x)){
+	if(x != nil){
+		rlock(x);
 		if(x->ifcid == xifcid)
 			return x;
 		runlock(x);
diff --git a/sys/src/9/ip/iproute.c b/sys/src/9/ip/iproute.c
index 1efd806e2..57a5ce5de 100644
--- a/sys/src/9/ip/iproute.c
+++ b/sys/src/9/ip/iproute.c
@@ -170,7 +170,7 @@ matchroute(Route *a, Route *b)
 			return 0;
 	}
 
-	if(a->ifc != nil && b->ifc != nil && (a->ifc != b->ifc || a->ifcid != b->ifcid))
+	if(a->ifc != b->ifc)
 		return 0;
 
 	if(*a->tag != 0 && strncmp(a->tag, b->tag, sizeof(a->tag)) != 0)
@@ -358,28 +358,42 @@ looknode(Route **cur, Route *r)
 }
 
 static Route*
-looknodetag(Route *r, char *tag)
+looknodematch(Route *r, int (*match)(Route*, void*), void *arg)
 {
 	Route *x;
 
 	if(r == nil)
 		return nil;
-
-	if((x = looknodetag(r->mid, tag)) != nil)
+	if((x = looknodematch(r->mid, match, arg)) != nil)
 		return x;
-	if((x = looknodetag(r->left, tag)) != nil)
+	if((x = looknodematch(r->left, match, arg)) != nil)
 		return x;
-	if((x = looknodetag(r->right, tag)) != nil)
+	if((x = looknodematch(r->right, match, arg)) != nil)
 		return x;
+	if((*match)(r, arg))
+		return r;
+	return nil;
+}
 
-	if((r->type & Rifc) == 0){
-		if(tag == nil || strncmp(tag, r->tag, sizeof(r->tag)) == 0)
-			return r;
-	}
+static int
+matchtag(Route *r, void *arg)
+{
+	char *tag = (char*)arg;
 
-	return nil;
+	if(r->type & Rifc)
+		return 0;
+	return tag == nil || strncmp(tag, r->tag, sizeof(r->tag)) == 0;
+}
+
+static int
+matchifc(Route *r, void *arg)
+{
+	Ipifc *ifc = (Ipifc*)arg;
+
+	return r->ifc == ifc;
 }
 
+
 #define	V4H(a)	((a&0x07ffffff)>>(32-Lroot-5))
 #define	V6H(a)	(((a)[0]&0x80000000)>>(32-Lroot) | ((a)[(IPllen/2)-1]&(0xffff>>(16-Lroot))))
 
@@ -470,9 +484,13 @@ mkroute(uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int type, Ip
 	Route r;
 	int h;
 
+	assert(ifc != nil);
+
 	memset(&r, 0, sizeof(r));
 
 	r.type = type;
+	r.ifc = ifc;
+	r.ifcid = ifcid;
 
 	if(type & Rv4){
 		x = nhgetl(a+IPv4off);
@@ -506,11 +524,6 @@ mkroute(uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int type, Ip
 		memmove(r.v6.gate, gate, IPaddrlen);
 	}
 
-	if(ifc != nil){
-		r.ifc = ifc;
-		r.ifcid = ifcid;
-	}
-
 	if(tag != nil)
 		strncpy(r.tag, tag, sizeof(r.tag));
 
@@ -535,58 +548,35 @@ delroute(Fs *f, uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int
 	wunlock(&routelock);
 }
 
-/*
- * get the outgoing interface for route r,
- * interface is returned rlock'd.
- */
-static Ipifc*
-routefindipifc(Route *r, Fs *f)
+static void
+flushroutematch(Fs *f, int (*match)(Route*, void*), void *arg)
 {
-	uchar local[IPaddrlen], gate[IPaddrlen];
-	Ipifc *ifc;
-	int i;
-
-	ifc = r->ifc;
-	if(ifc != nil && canrlock(ifc)){
-		if(ifc->ifcid == r->ifcid)
-			return ifc;
-		runlock(ifc);
-		r->ifc = nil;
-	}
+	Route r, *x;
+	int h;
 
-	if(r->type & Rsrc) {
-		if(r->type & Rv4) {
-			hnputl(local+IPv4off, r->v4.source);
-			memmove(local, v4prefix, IPv4off);
-		} else {
-			for(i = 0; i < IPllen; i++)
-				hnputl(local+4*i, r->v6.source[i]);
+	wlock(&routelock);
+	for(h = 0; h < nelem(f->v4root); h++)
+		while((x = looknodematch(f->v4root[h], match, arg)) != nil){
+			memmove(&r, x, sizeof(RouteTree) + sizeof(V4route));
+			routedel(f, &r);
 		}
-	} else {
-		ipmove(local, IPnoaddr);
-	}
-
-	if(r->type & Rifc) {
-		if(r->type & Rv4) {
-			hnputl(gate+IPv4off, r->v4.address);
-			memmove(gate, v4prefix, IPv4off);
-		} else {
-			for(i = 0; i < IPllen; i++)
-				hnputl(gate+4*i, r->v6.address[i]);
+	for(h = 0; h < nelem(f->v6root); h++)
+		while((x = looknodematch(f->v6root[h], match, arg)) != nil){
+			memmove(&r, x, sizeof(RouteTree) + sizeof(V6route));
+			routedel(f, &r);
 		}
-	} else {
-		if(r->type & Rv4)
-			v4tov6(gate, r->v4.gate);
-		else
-			ipmove(gate, r->v6.gate);
-	}
+	wunlock(&routelock);
+}
 
-	ifc = findipifc(f, local, gate, r->type);
-	if(ifc != nil) {
-		r->ifc = ifc;
-		r->ifcid = ifc->ifcid;
-	}
-	return ifc;
+/*
+ * flushrouteifc:
+ *   remove all routes associated with ifc (wlock()'ed).
+ */
+void
+flushrouteifc(Fs *f, Ipifc *ifc)
+{
+	flushroutematch(f, matchifc, ifc);
+	ifc->ifcid++;	/* invalidate all routes */
 }
 
 /*
@@ -639,17 +629,9 @@ v4lookup(Fs *f, uchar *a, uchar *s, Routehint *rh)
 		q = p;
 		p = p->mid;
 	}
-	if(q != nil){
-		ifc = routefindipifc(q, f);
-		if(ifc == nil)
-			q = nil;
-		else {
-			if(rh != nil){
-				rh->r = q;
-				rh->rgen = v4routegeneration;
-			}
-			runlock(ifc);
-		}
+	if(rh != nil){
+		rh->r = q;
+		rh->rgen = v4routegeneration;
 	}
 	runlock(&routelock);
 	return q;
@@ -736,17 +718,9 @@ v6lookup(Fs *f, uchar *a, uchar *s, Routehint *rh)
 		p = p->mid;
 next:		;
 	}
-	if(q != nil){
-		ifc = routefindipifc(q, f);
-		if(ifc == nil)
-			q = nil;
-		else {
-			if(rh != nil){
-				rh->r = q;
-				rh->rgen = v6routegeneration;
-			}
-			runlock(ifc);
-		}
+	if(rh != nil){
+		rh->r = q;
+		rh->rgen = v6routegeneration;
 	}
 	runlock(&routelock);
 	return q;
@@ -770,8 +744,9 @@ v4source(Fs *f, uchar *a, uchar *s)
 	Route *p, *q;
 	Ipifc *ifc;
 
-	q = nil;
 	la = nhgetl(a);
+again:
+	q = nil;
 	rlock(&routelock);
 	for(p = f->v4root[V4H(la)]; p != nil;){
 		if(la < p->v4.address){
@@ -782,11 +757,17 @@ v4source(Fs *f, uchar *a, uchar *s)
 			p = p->right;
 			continue;
 		}
-
-		ifc = routefindipifc(p, f);
-		if(ifc == nil){
-			p = p->mid;
-			continue;
+		ifc = p->ifc;
+		if(!canrlock(ifc)){
+			int gen = v4routegeneration;
+			runlock(&routelock);
+			rlock(ifc);
+			rlock(&routelock);
+			if(v4routegeneration != gen){
+				runlock(&routelock);
+				runlock(ifc);
+				goto again;
+			}
 		}
 		splen = 0;
 		if(p->type & Rsrc){
@@ -818,9 +799,10 @@ v6source(Fs *f, uchar *a, uchar *s)
 	Route *p, *q;
 	Ipifc *ifc;
 
-	q = nil;
 	for(h = 0; h < IPllen; h++)
 		la[h] = nhgetl(a+4*h);
+again:
+	q = nil;
 	rlock(&routelock);
 	for(p = f->v6root[V6H(la)]; p != nil;){
 		for(h = 0; h < IPllen; h++){
@@ -845,11 +827,17 @@ v6source(Fs *f, uchar *a, uchar *s)
 			}
 			break;
 		}
-
-		ifc = routefindipifc(p, f);
-		if(ifc == nil){
-			p = p->mid;
-			continue;
+		ifc = p->ifc;
+		if(!canrlock(ifc)){
+			int gen = v6routegeneration;
+			runlock(&routelock);
+			rlock(ifc);
+			rlock(&routelock);
+			if(v6routegeneration != gen){
+				runlock(&routelock);
+				runlock(ifc);
+				goto again;
+			}
 		}
 		splen = 0;
 		if(p->type & Rsrc){
@@ -982,16 +970,13 @@ static char*
 seprintroute(char *p, char *e, Route *r)
 {
 	uchar addr[IPaddrlen], mask[IPaddrlen], src[IPaddrlen], smask[IPaddrlen], gate[IPaddrlen];
-	char type[8], ifbuf[4], *iname;
+	char type[8], ifbuf[4];
 
 	convroute(r, addr, mask, src, smask, gate);
 	routetype(r->type, type);
-	if(r->ifc != nil && r->ifcid == r->ifc->ifcid)
-		snprint(iname = ifbuf, sizeof ifbuf, "%d", r->ifc->conv->x);
-	else
-		iname = "-";
+	snprint(ifbuf, sizeof ifbuf, "%d", r->ifc->conv->x);
 	return seprint(p, e, "%-15I %-4M %-15I %-4s %4.4s %3s %-15I %-4M\n",
-		addr, mask, gate, type, r->tag, iname, src, smask);
+		addr, mask, gate, type, r->tag, ifbuf, src, smask);
 }
 
 typedef struct Routewalk Routewalk;
@@ -1074,6 +1059,7 @@ routeread(Fs *f, char *p, ulong offset, int n)
  *	7	add	addr	mask	gate			ifc	src	smask
  *	8	add	addr	mask	gate	type		ifc	src	smask
  *	9	add	addr	mask	gate	type	tag	ifc	src	smask
+ *
  *	3	del	addr	mask
  *	4	del	addr	mask	gate
  *	5	del	addr	mask					src	smask
@@ -1088,15 +1074,14 @@ parseroute(Fs *f, char **argv, int argc)
 	uchar addr[IPaddrlen], mask[IPaddrlen];
 	uchar src[IPaddrlen], smask[IPaddrlen];
 	uchar gate[IPaddrlen];
+	char *ifcstr, *tag;
 	Ipifc *ifc;
 	uchar ifcid;
-	char *tag;
 	int type;
 
 	type = 0;
 	tag = nil;
-	ifc = nil;
-	ifcid = 0;
+	ifcstr = nil;
 	ipmove(gate, IPnoaddr);
 	ipmove(src, IPnoaddr);
 	ipmove(smask, IPnoaddr);
@@ -1120,13 +1105,9 @@ parseroute(Fs *f, char **argv, int argc)
 	}
 
 	if(argc == 5 && strcmp(argv[0], "add") == 0)
-		ifc = findipifcstr(f, argv[4]);
-	if(argc > 6)
-		ifc = findipifcstr(f, argv[argc-3]);
-	if(ifc != nil){
-		ifcid = ifc->ifcid;
-		runlock(ifc);
-	}
+		ifcstr = argv[4];
+	else if(argc > 6)
+		ifcstr = argv[argc-3];
 
 	if(argc > 7 && (type = parseroutetype(argv[4])) < 0)
 		error(Ebadctl);
@@ -1148,6 +1129,15 @@ parseroute(Fs *f, char **argv, int argc)
 			error(Ebadip);
 	}
 
+	if(ifcstr != nil)
+		ifc = findipifcstr(f, ifcstr);
+	else
+		ifc = findipifc(f, src, gate, type);
+	if(ifc == nil)
+		error("interface not found");
+	ifcid = ifc->ifcid;
+	runlock(ifc);
+
 	return mkroute(addr, mask, src, smask, gate, type, ifc, ifcid, tag);	
 }
 
@@ -1156,7 +1146,6 @@ routewrite(Fs *f, Chan *c, char *p, int n)
 {
 	Cmdbuf *cb;
 	IPaux *a;
-	Route *x, r;
 
 	cb = parsecmd(p, n);
 	if(waserror()){
@@ -1166,25 +1155,11 @@ routewrite(Fs *f, Chan *c, char *p, int n)
 	if(cb->nf < 1)
 		error("short control request");
 	if(strcmp(cb->f[0], "flush") == 0){
-		char *tag = cb->nf < 2 ? nil : cb->f[1];
-		int h;
-
-		wlock(&routelock);
-		for(h = 0; h < nelem(f->v4root); h++)
-			while((x = looknodetag(f->v4root[h], tag)) != nil){
-				memmove(&r, x, sizeof(RouteTree) + sizeof(V4route));
-				routedel(f, &r);
-			}
-		for(h = 0; h < nelem(f->v6root); h++)
-			while((x = looknodetag(f->v6root[h], tag)) != nil){
-				memmove(&r, x, sizeof(RouteTree) + sizeof(V6route));
-				routedel(f, &r);
-			}
-		wunlock(&routelock);
+		flushroutematch(f, matchtag, cb->nf < 2 ? nil : cb->f[1]);
 	} else if(strcmp(cb->f[0], "add") == 0
 		||strcmp(cb->f[0], "del") == 0
 		||strcmp(cb->f[0], "remove") == 0){
-		r = parseroute(f, cb->f, cb->nf);
+		Route r = parseroute(f, cb->f, cb->nf);
 		if(*r.tag == 0){
 			a = c->aux;
 			strncpy(r.tag, a->tag, sizeof(r.tag));
diff --git a/sys/src/9/ip/ipv6.c b/sys/src/9/ip/ipv6.c
index a47b520e6..5d2d43ef1 100644
--- a/sys/src/9/ip/ipv6.c
+++ b/sys/src/9/ip/ipv6.c
@@ -85,7 +85,7 @@ ipoput6(Fs *f, Block *bp, Ipifc *gating, int ttl, int tos, Routehint *rh)
 		nexterror();
 	}
 
-	if(ifc->m == nil)
+	if(ifc->m == nil || r->ifcid != ifc->ifcid)
 		goto raise;
 
 	medialen = ifc->maxtu - ifc->m->hsize;