1158 lines
21 KiB
C
1158 lines
21 KiB
C
#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 */
|
|
static Route* v4freelist;
|
|
static Route* v6freelist;
|
|
static RWlock routelock;
|
|
static ulong v4routegeneration, v6routegeneration;
|
|
|
|
static void
|
|
freeroute(Route *r)
|
|
{
|
|
Route **l;
|
|
|
|
r->ref = 0;
|
|
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, **l;
|
|
int n;
|
|
|
|
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->left = r;
|
|
l->mid = *q;
|
|
*q = l;
|
|
}
|
|
|
|
/*
|
|
* 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, /* a left of b */
|
|
Rfollows, /* a right of b */
|
|
Requals, /* a equals b */
|
|
Rcontains, /* a contians b */
|
|
Roverlaps, /* a overlaps b */
|
|
};
|
|
|
|
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){
|
|
if(a->v4.source <= b->v4.source
|
|
&& a->v4.endsource >= b->v4.endsource){
|
|
if(a->v4.source == b->v4.source
|
|
&& a->v4.endsource == b->v4.endsource)
|
|
return Requals;
|
|
return Rcontains;
|
|
}
|
|
return Roverlaps;
|
|
}
|
|
return Rcontains;
|
|
}
|
|
return Roverlaps;
|
|
}
|
|
|
|
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){
|
|
if(lcmp(a->v6.source, b->v6.source) <= 0
|
|
&& lcmp(a->v6.endsource, b->v6.endsource) >= 0){
|
|
if(lcmp(a->v6.source, b->v6.source) == 0
|
|
&& lcmp(a->v6.endsource, b->v6.endsource) == 0)
|
|
return Requals;
|
|
return Rcontains;
|
|
}
|
|
return Roverlaps;
|
|
}
|
|
return Rcontains;
|
|
}
|
|
return Roverlaps;
|
|
}
|
|
|
|
/* return 1 if a matches b, otherwise 0 */
|
|
static int
|
|
matchroute(Route *a, Route *b)
|
|
{
|
|
if(a == b)
|
|
return 1;
|
|
|
|
if((a->type^b->type) & (Rifc|Runi|Rmulti|Rbcast))
|
|
return 0;
|
|
|
|
if(a->type & Rv4){
|
|
if(memcmp(a->v4.gate, IPnoaddr+IPv4off, IPv4addrlen) != 0
|
|
&& memcmp(a->v4.gate, b->v4.gate, IPv4addrlen) != 0)
|
|
return 0;
|
|
} else {
|
|
if(ipcmp(a->v6.gate, IPnoaddr) != 0
|
|
&& ipcmp(a->v6.gate, b->v6.gate) != 0)
|
|
return 0;
|
|
}
|
|
|
|
if(a->ifc != nil && b->ifc != nil && (a->ifc != b->ifc || a->ifcid != b->ifcid))
|
|
return 0;
|
|
|
|
if(*a->tag != 0 && strncmp(a->tag, b->tag, sizeof(a->tag)) != 0)
|
|
return 0;
|
|
|
|
return 1;
|
|
}
|
|
|
|
static void
|
|
copygate(Route *old, Route *new)
|
|
{
|
|
old->type = new->type;
|
|
old->ifc = new->ifc;
|
|
old->ifcid = new->ifcid;
|
|
if(new->type & Rv4)
|
|
memmove(old->v4.gate, new->v4.gate, IPv4addrlen);
|
|
else
|
|
ipmove(old->v6.gate, new->v6.gate);
|
|
strncpy(old->tag, new->tag, sizeof(new->tag));
|
|
}
|
|
|
|
/*
|
|
* 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 = nil;
|
|
p->right = nil;
|
|
addnode(f, root, p);
|
|
if(l != nil)
|
|
walkadd(f, root, l);
|
|
if(r != nil)
|
|
walkadd(f, root, r);
|
|
}
|
|
|
|
/*
|
|
* calculate depth
|
|
*/
|
|
static void
|
|
calcd(Route *p)
|
|
{
|
|
Route *q;
|
|
int d;
|
|
|
|
if(p != nil) {
|
|
d = 0;
|
|
q = p->left;
|
|
if(q != nil)
|
|
d = q->depth;
|
|
q = p->right;
|
|
if(q != nil && q->depth > d)
|
|
d = q->depth;
|
|
q = p->mid;
|
|
if(q != nil && 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 == nil) {
|
|
*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)
|
|
copygate(p, new);
|
|
else if(new->type & Rifc)
|
|
p->ref++;
|
|
freeroute(new);
|
|
break;
|
|
case Roverlaps:
|
|
addnode(f, &p->mid, new);
|
|
break;
|
|
}
|
|
|
|
balancetree(cur);
|
|
}
|
|
|
|
/*
|
|
* find node matching r
|
|
*/
|
|
static Route**
|
|
looknode(Route **cur, Route *r)
|
|
{
|
|
Route *p;
|
|
|
|
for(;;){
|
|
p = *cur;
|
|
if(p == nil)
|
|
return nil;
|
|
switch(rangecompare(r, p)){
|
|
case Rcontains:
|
|
return nil;
|
|
case Rpreceeds:
|
|
cur = &p->left;
|
|
break;
|
|
case Rfollows:
|
|
cur = &p->right;
|
|
break;
|
|
case Roverlaps:
|
|
cur = &p->mid;
|
|
break;
|
|
case Requals:
|
|
if((p->type & Rifc) == 0 && !matchroute(r, p))
|
|
return nil;
|
|
return cur;
|
|
}
|
|
}
|
|
}
|
|
|
|
static Route*
|
|
looknodetag(Route *r, char *tag)
|
|
{
|
|
Route *x;
|
|
|
|
if(r == nil)
|
|
return nil;
|
|
|
|
if((x = looknodetag(r->mid, tag)) != nil)
|
|
return x;
|
|
if((x = looknodetag(r->left, tag)) != nil)
|
|
return x;
|
|
if((x = looknodetag(r->right, tag)) != nil)
|
|
return x;
|
|
|
|
if((r->type & Rifc) == 0){
|
|
if(tag == nil || strncmp(tag, r->tag, sizeof(r->tag)) == 0)
|
|
return r;
|
|
}
|
|
|
|
return nil;
|
|
}
|
|
|
|
#define V4H(a) ((a&0x07ffffff)>>(32-Lroot-5))
|
|
#define V6H(a) (((a)[IPllen-1]&0x07ffffff)>>(32-Lroot-5))
|
|
|
|
static void
|
|
routeadd(Fs *f, Route *r)
|
|
{
|
|
Route **h, **e, *p;
|
|
|
|
if(r->type & Rv4){
|
|
h = &f->v4root[V4H(r->v4.address)];
|
|
e = &f->v4root[V4H(r->v4.endaddress)];
|
|
} else {
|
|
h = &f->v6root[V6H(r->v6.address)];
|
|
e = &f->v6root[V6H(r->v6.endaddress)];
|
|
}
|
|
|
|
for(; h <= e; h++) {
|
|
p = allocroute(r->type);
|
|
|
|
p->ifc = r->ifc;
|
|
p->ifcid = r->ifcid;
|
|
|
|
if(r->type & Rv4)
|
|
memmove(&p->v4, &r->v4, sizeof(r->v4));
|
|
else
|
|
memmove(&p->v6, &r->v6, sizeof(r->v6));
|
|
|
|
memmove(p->tag, r->tag, sizeof(r->tag));
|
|
|
|
addnode(f, h, p);
|
|
while((p = f->queue) != nil) {
|
|
f->queue = p->mid;
|
|
walkadd(f, h, p->left);
|
|
freeroute(p);
|
|
}
|
|
}
|
|
|
|
if(r->type & Rv4)
|
|
v4routegeneration++;
|
|
else
|
|
v6routegeneration++;
|
|
}
|
|
|
|
static void
|
|
routerem(Fs *f, Route *r)
|
|
{
|
|
Route **h, **e, **l, *p;
|
|
|
|
if(r->type & Rv4){
|
|
h = &f->v4root[V4H(r->v4.address)];
|
|
e = &f->v4root[V4H(r->v4.endaddress)];
|
|
} else {
|
|
h = &f->v6root[V6H(r->v6.address)];
|
|
e = &f->v6root[V6H(r->v6.endaddress)];
|
|
}
|
|
|
|
for(; h <= e; h++) {
|
|
if((l = looknode(h, r)) == nil)
|
|
continue;
|
|
p = *l;
|
|
if(--(p->ref) != 0)
|
|
continue;
|
|
*l = nil;
|
|
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, h, p->left);
|
|
freeroute(p);
|
|
}
|
|
}
|
|
|
|
if(r->type & Rv4)
|
|
v4routegeneration++;
|
|
else
|
|
v6routegeneration++;
|
|
}
|
|
|
|
static Route
|
|
mkroute(uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int type, Ipifc *ifc, char *tag)
|
|
{
|
|
ulong x, y;
|
|
Route r;
|
|
int h;
|
|
|
|
memset(&r, 0, sizeof(r));
|
|
|
|
r.type = type;
|
|
|
|
if(type & Rv4){
|
|
x = nhgetl(a+IPv4off);
|
|
y = nhgetl(mask+IPv4off);
|
|
r.v4.address = x & y;
|
|
r.v4.endaddress = x | ~y;
|
|
|
|
x = nhgetl(s+IPv4off);
|
|
y = nhgetl(smask+IPv4off);
|
|
if(y != 0)
|
|
r.type |= Rsrc;
|
|
r.v4.source = x & y;
|
|
r.v4.endsource = x | ~y;
|
|
|
|
memmove(r.v4.gate, gate+IPv4off, IPv4addrlen);
|
|
} else {
|
|
for(h = 0; h < IPllen; h++){
|
|
x = nhgetl(a+4*h);
|
|
y = nhgetl(mask+4*h);
|
|
r.v6.address[h] = x & y;
|
|
r.v6.endaddress[h] = x | ~y;
|
|
|
|
x = nhgetl(s+4*h);
|
|
y = nhgetl(smask+4*h);
|
|
if(y != 0)
|
|
r.type |= Rsrc;
|
|
r.v6.source[h] = x & y;
|
|
r.v6.endsource[h] = x | ~y;
|
|
}
|
|
|
|
memmove(r.v6.gate, gate, IPaddrlen);
|
|
}
|
|
|
|
if(ifc != nil){
|
|
r.ifc = ifc;
|
|
r.ifcid = ifc->ifcid;
|
|
}
|
|
|
|
if(tag != nil)
|
|
strncpy(r.tag, tag, sizeof(r.tag));
|
|
|
|
return r;
|
|
}
|
|
|
|
void
|
|
addroute(Fs *f, uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int type, Ipifc *ifc, char *tag)
|
|
{
|
|
Route r = mkroute(a, mask, s, smask, gate, type, ifc, tag);
|
|
wlock(&routelock);
|
|
routeadd(f, &r);
|
|
wunlock(&routelock);
|
|
}
|
|
|
|
void
|
|
remroute(Fs *f, uchar *a, uchar *mask, uchar *s, uchar *smask, uchar *gate, int type, Ipifc *ifc, char *tag)
|
|
{
|
|
Route r = mkroute(a, mask, s, smask, gate, type, ifc, tag);
|
|
wlock(&routelock);
|
|
routerem(f, &r);
|
|
wunlock(&routelock);
|
|
}
|
|
|
|
/* get the outgoing interface for route r */
|
|
static Ipifc*
|
|
routefindipifc(Route *r, Fs *f)
|
|
{
|
|
uchar local[IPaddrlen], gate[IPaddrlen];
|
|
Ipifc *ifc;
|
|
int i;
|
|
|
|
ifc = r->ifc;
|
|
if(ifc != nil && ifc->ifcid == r->ifcid)
|
|
return ifc;
|
|
|
|
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]);
|
|
}
|
|
} 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]);
|
|
}
|
|
} else {
|
|
if(r->type & Rv4)
|
|
v4tov6(gate, r->v4.gate);
|
|
else
|
|
ipmove(gate, r->v6.gate);
|
|
}
|
|
|
|
if((ifc = findipifc(f, local, gate, r->type)) == nil)
|
|
return nil;
|
|
|
|
r->ifc = ifc;
|
|
r->ifcid = ifc->ifcid;
|
|
return ifc;
|
|
}
|
|
|
|
/*
|
|
* v4lookup, v6lookup:
|
|
* lookup a route to destination address a from source address s
|
|
* and return the route. returns nil if no route was found.
|
|
* an optional Routehint can be passed in rh to cache the lookup.
|
|
*
|
|
* for v4lookup, addresses are in 4 byte format.
|
|
*/
|
|
Route*
|
|
v4lookup(Fs *f, uchar *a, uchar *s, Routehint *rh)
|
|
{
|
|
ulong la, ls;
|
|
Route *p, *q;
|
|
Ipifc *ifc;
|
|
|
|
if(rh != nil
|
|
&& rh->rgen == v4routegeneration
|
|
&& (q = rh->r) != nil
|
|
&& (ifc = q->ifc) != nil
|
|
&& q->ifcid == ifc->ifcid
|
|
&& q->ref > 0)
|
|
return q;
|
|
|
|
la = nhgetl(a);
|
|
ls = nhgetl(s);
|
|
q = nil;
|
|
for(p = f->v4root[V4H(la)]; p != nil;){
|
|
if(la < p->v4.address){
|
|
p = p->left;
|
|
continue;
|
|
}
|
|
if(la > p->v4.endaddress){
|
|
p = p->right;
|
|
continue;
|
|
}
|
|
if(p->type & Rsrc){
|
|
if(ls < p->v4.source){
|
|
p = p->mid;
|
|
continue;
|
|
}
|
|
if(ls > p->v4.endsource){
|
|
p = p->mid;
|
|
continue;
|
|
}
|
|
}
|
|
q = p;
|
|
p = p->mid;
|
|
}
|
|
|
|
if(q == nil || q->ref == 0 || routefindipifc(q, f) == nil)
|
|
return nil;
|
|
|
|
if(rh != nil){
|
|
rh->r = q;
|
|
rh->rgen = v4routegeneration;
|
|
}
|
|
|
|
return q;
|
|
}
|
|
|
|
Route*
|
|
v6lookup(Fs *f, uchar *a, uchar *s, Routehint *rh)
|
|
{
|
|
ulong la[IPllen], ls[IPllen];
|
|
ulong x, y;
|
|
Route *p, *q;
|
|
Ipifc *ifc;
|
|
int h;
|
|
|
|
if(isv4(s)){
|
|
if(isv4(a))
|
|
return v4lookup(f, a+IPv4off, s+IPv4off, rh);
|
|
return nil;
|
|
}
|
|
|
|
if(rh != nil
|
|
&& rh->rgen == v6routegeneration
|
|
&& (q = rh->r) != nil
|
|
&& (ifc = q->ifc) != nil
|
|
&& q->ifcid == ifc->ifcid
|
|
&& q->ref > 0)
|
|
return q;
|
|
|
|
for(h = 0; h < IPllen; h++){
|
|
la[h] = nhgetl(a+4*h);
|
|
ls[h] = nhgetl(s+4*h);
|
|
}
|
|
|
|
q = nil;
|
|
for(p = f->v6root[V6H(la)]; p != nil;){
|
|
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;
|
|
}
|
|
if(p->type & Rsrc){
|
|
for(h = 0; h < IPllen; h++){
|
|
x = ls[h];
|
|
y = p->v6.source[h];
|
|
if(x == y)
|
|
continue;
|
|
if(x < y){
|
|
p = p->mid;
|
|
goto next;
|
|
}
|
|
break;
|
|
}
|
|
for(h = 0; h < IPllen; h++){
|
|
x = ls[h];
|
|
y = p->v6.endsource[h];
|
|
if(x == y)
|
|
continue;
|
|
if(x > y){
|
|
p = p->mid;
|
|
goto next;
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
q = p;
|
|
p = p->mid;
|
|
next: ;
|
|
}
|
|
|
|
if(q == nil || q->ref == 0 || routefindipifc(q, f) == nil)
|
|
return nil;
|
|
|
|
if(rh != nil){
|
|
rh->r = q;
|
|
rh->rgen = v6routegeneration;
|
|
}
|
|
|
|
return q;
|
|
}
|
|
|
|
/*
|
|
* v4source, v6source:
|
|
* lookup a route to destination address a and also find
|
|
* a suitable source address s on the outgoing interface.
|
|
* return the route on success or nil when no route
|
|
* was found.
|
|
*
|
|
* for v4source, addresses are in 4 byte format.
|
|
*/
|
|
Route*
|
|
v4source(Fs *f, uchar *a, uchar *s)
|
|
{
|
|
uchar src[IPv4addrlen];
|
|
int splen;
|
|
ulong x, la;
|
|
Route *p, *q;
|
|
Ipifc *ifc;
|
|
|
|
q = nil;
|
|
la = nhgetl(a);
|
|
rlock(&routelock);
|
|
for(p = f->v4root[V4H(la)]; p != nil;){
|
|
if(la < p->v4.address){
|
|
p = p->left;
|
|
continue;
|
|
}
|
|
if(la > p->v4.endaddress){
|
|
p = p->right;
|
|
continue;
|
|
}
|
|
splen = 0;
|
|
if(p->type & Rsrc){
|
|
/* calculate local prefix length for source specific routes */
|
|
for(x = ~(p->v4.endsource ^ p->v4.source); x & 0x80000000UL; x <<= 1)
|
|
splen++;
|
|
hnputl(src, p->v4.source);
|
|
}
|
|
if((ifc = routefindipifc(p, f)) == nil
|
|
|| !ipv4local(ifc, src, splen, (p->type & (Rifc|Rbcast|Rmulti|Rv4))==Rv4? p->v4.gate: a)){
|
|
p = p->mid;
|
|
continue;
|
|
}
|
|
memmove(s, src, IPv4addrlen);
|
|
q = p;
|
|
p = p->mid;
|
|
}
|
|
runlock(&routelock);
|
|
return q;
|
|
}
|
|
|
|
Route*
|
|
v6source(Fs *f, uchar *a, uchar *s)
|
|
{
|
|
uchar src[IPaddrlen];
|
|
int splen, h;
|
|
ulong x, y, la[IPllen];
|
|
Route *p, *q;
|
|
Ipifc *ifc;
|
|
|
|
q = nil;
|
|
for(h = 0; h < IPllen; h++)
|
|
la[h] = nhgetl(a+4*h);
|
|
rlock(&routelock);
|
|
for(p = f->v6root[V6H(la)]; p != nil;){
|
|
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;
|
|
}
|
|
splen = 0;
|
|
if(p->type & Rsrc){
|
|
/* calculate local prefix length for source specific routes */
|
|
for(h = 0; h < IPllen; h++){
|
|
hnputl(src+4*h, p->v6.source[h]);
|
|
if((x = ~(p->v6.endsource[h] ^ p->v6.source[h])) != ~0UL){
|
|
for(; x & 0x80000000UL; x <<= 1)
|
|
splen++;
|
|
break;
|
|
}
|
|
splen += 32;
|
|
}
|
|
}
|
|
if((ifc = routefindipifc(p, f)) == nil
|
|
|| !ipv6local(ifc, src, splen, a)){
|
|
p = p->mid;
|
|
continue;
|
|
}
|
|
ipmove(s, src);
|
|
q = p;
|
|
p = p->mid;
|
|
next: ;
|
|
}
|
|
runlock(&routelock);
|
|
return q;
|
|
}
|
|
|
|
static int
|
|
parseroutetype(char *p)
|
|
{
|
|
int type = 0;
|
|
switch(*p++){
|
|
default: return -1;
|
|
case '4': type |= Rv4;
|
|
case '6': break;
|
|
}
|
|
for(;;) switch(*p++){
|
|
default:
|
|
return -1;
|
|
case 'i':
|
|
if(((type ^= Rifc) & Rifc) != Rifc) return -1;
|
|
break;
|
|
case 'u':
|
|
if(((type ^= Runi) & (Runi|Rbcast|Rmulti)) != Runi) return -1;
|
|
break;
|
|
case 'b':
|
|
if(((type ^= Rbcast) & (Runi|Rbcast|Rmulti)) != Rbcast) return -1;
|
|
break;
|
|
case 'm':
|
|
if(((type ^= Rmulti) & (Runi|Rbcast|Rmulti)) != Rmulti) return -1;
|
|
break;
|
|
case 'p':
|
|
if(((type ^= Rptpt) & Rptpt) != Rptpt) return -1;
|
|
break;
|
|
case '\0':
|
|
return type;
|
|
}
|
|
}
|
|
|
|
void
|
|
routetype(int type, char p[8])
|
|
{
|
|
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';
|
|
*p = 0;
|
|
}
|
|
|
|
static void
|
|
convroute(Route *r, uchar *addr, uchar *mask, uchar *src, uchar *smask, uchar *gate)
|
|
{
|
|
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(src, v4prefix, IPv4off);
|
|
hnputl(src+IPv4off, r->v4.source);
|
|
|
|
memset(smask, 0xff, IPv4off);
|
|
hnputl(smask+IPv4off, ~(r->v4.endsource ^ r->v4.source));
|
|
|
|
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]));
|
|
hnputl(src + 4*i, r->v6.source[i]);
|
|
hnputl(smask + 4*i, ~(r->v6.endsource[i] ^ r->v6.source[i]));
|
|
}
|
|
memmove(gate, r->v6.gate, IPaddrlen);
|
|
}
|
|
}
|
|
|
|
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;
|
|
|
|
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 = "-";
|
|
return seprint(p, e, "%-15I %-4M %-15I %-4s %4.4s %3s %-15I %-4M\n",
|
|
addr, mask, gate, type, r->tag, iname, src, smask);
|
|
}
|
|
|
|
typedef struct Routewalk Routewalk;
|
|
struct Routewalk
|
|
{
|
|
int o;
|
|
int h;
|
|
char* p;
|
|
char* e;
|
|
};
|
|
|
|
static int
|
|
rr1(Routewalk *rw, Route *r)
|
|
{
|
|
int n = seprintroute(rw->p, rw->e, r) - rw->p;
|
|
if(rw->o < 0){
|
|
if(n > -rw->o){
|
|
memmove(rw->p, rw->p - rw->o, n + rw->o);
|
|
rw->p += n + rw->o;
|
|
}
|
|
rw->o += n;
|
|
} else
|
|
rw->p += n;
|
|
return rw->p < rw->e;
|
|
}
|
|
|
|
static int
|
|
rr(Route *r, Routewalk *rw)
|
|
{
|
|
int h;
|
|
|
|
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){
|
|
if(rr1(rw, r) == 0)
|
|
return 0;
|
|
}
|
|
if(rr(r->mid, rw) == 0)
|
|
return 0;
|
|
return rr(r->right, rw);
|
|
}
|
|
|
|
long
|
|
routeread(Fs *f, char *p, ulong offset, int n)
|
|
{
|
|
Routewalk rw[1];
|
|
|
|
rw->p = p;
|
|
rw->e = p+n;
|
|
rw->o = -offset;
|
|
if(rw->o > 0)
|
|
return 0;
|
|
|
|
rlock(&routelock);
|
|
if(rw->p < rw->e) {
|
|
for(rw->h = 0; rw->h < nelem(f->v4root); rw->h++)
|
|
if(rr(f->v4root[rw->h], rw) == 0)
|
|
break;
|
|
}
|
|
if(rw->p < rw->e) {
|
|
for(rw->h = 0; rw->h < nelem(f->v6root); rw->h++)
|
|
if(rr(f->v6root[rw->h], rw) == 0)
|
|
break;
|
|
}
|
|
runlock(&routelock);
|
|
|
|
return rw->p - p;
|
|
}
|
|
|
|
/*
|
|
* 4 add addr mask gate
|
|
* 5 add addr mask gate ifc
|
|
* 6 add addr mask gate src smask
|
|
* 7 add addr mask gate ifc src smask
|
|
* 8 add addr mask gate tag ifc src smask
|
|
* 9 add addr mask gate type tag ifc src smask
|
|
* 3 remove addr mask
|
|
* 4 remove addr mask gate
|
|
* 5 remove addr mask src smask
|
|
* 6 remove addr mask gate src smask
|
|
* 7 remove addr mask gate ifc src smask
|
|
* 8 remove addr mask gate tag ifc src smask
|
|
* 9 remove addr mask gate type tag ifc src smask
|
|
*/
|
|
static Route
|
|
parseroute(Fs *f, char **argv, int argc)
|
|
{
|
|
uchar addr[IPaddrlen], mask[IPaddrlen];
|
|
uchar src[IPaddrlen], smask[IPaddrlen];
|
|
uchar gate[IPaddrlen];
|
|
Ipifc *ifc;
|
|
char *tag;
|
|
int type;
|
|
|
|
type = 0;
|
|
tag = nil;
|
|
ifc = nil;
|
|
ipmove(gate, IPnoaddr);
|
|
ipmove(src, IPnoaddr);
|
|
ipmove(smask, IPnoaddr);
|
|
|
|
if(argc < 3)
|
|
error(Ebadctl);
|
|
if(parseipandmask(addr, mask, argv[1], argv[2]) == -1)
|
|
error(Ebadip);
|
|
|
|
if(strcmp(argv[0], "add") == 0 || (argc > 3 && argc != 5)){
|
|
if(argc < 4)
|
|
error(Ebadctl);
|
|
if(parseip(gate, argv[3]) == -1)
|
|
error(Ebadip);
|
|
}
|
|
if(argc > 4 && (strcmp(argv[0], "add") != 0 || argc != 5)){
|
|
if(parseipandmask(src, smask, argv[argc-2], argv[argc-1]) == -1)
|
|
error(Ebadip);
|
|
}
|
|
if(argc == 5 && strcmp(argv[0], "add") == 0)
|
|
ifc = findipifcstr(f, argv[4]);
|
|
if(argc > 6)
|
|
ifc = findipifcstr(f, argv[argc-3]);
|
|
if(argc > 7)
|
|
tag = argv[argc-4];
|
|
if(argc > 8){
|
|
if((type = parseroutetype(argv[argc-5])) < 0)
|
|
error(Ebadctl);
|
|
} else {
|
|
if(isv4(addr))
|
|
type |= Rv4;
|
|
}
|
|
if(argc > 9)
|
|
error(Ebadctl);
|
|
|
|
if(type & Rv4){
|
|
if(!isv4(addr))
|
|
error(Ebadip);
|
|
if(ipcmp(smask, IPnoaddr) != 0 && !isv4(src))
|
|
error(Ebadip);
|
|
if(ipcmp(gate, IPnoaddr) != 0 && !isv4(gate))
|
|
error(Ebadip);
|
|
} else {
|
|
if(isv4(addr))
|
|
error(Ebadip);
|
|
}
|
|
|
|
return mkroute(addr, mask, src, smask, gate, type, ifc, tag);
|
|
}
|
|
|
|
long
|
|
routewrite(Fs *f, Chan *c, char *p, int n)
|
|
{
|
|
Cmdbuf *cb;
|
|
IPaux *a;
|
|
Route *x, r;
|
|
|
|
cb = parsecmd(p, n);
|
|
if(waserror()){
|
|
free(cb);
|
|
nexterror();
|
|
}
|
|
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));
|
|
routerem(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));
|
|
routerem(f, &r);
|
|
}
|
|
wunlock(&routelock);
|
|
} else if(strcmp(cb->f[0], "add") == 0 || strcmp(cb->f[0], "remove") == 0){
|
|
r = parseroute(f, cb->f, cb->nf);
|
|
if(*r.tag == 0){
|
|
a = c->aux;
|
|
strncpy(r.tag, a->tag, sizeof(r.tag));
|
|
}
|
|
wlock(&routelock);
|
|
if(strcmp(cb->f[0], "add") == 0)
|
|
routeadd(f, &r);
|
|
else
|
|
routerem(f, &r);
|
|
wunlock(&routelock);
|
|
} else if(strcmp(cb->f[0], "tag") == 0) {
|
|
if(cb->nf < 2)
|
|
error(Ebadarg);
|
|
a = c->aux;
|
|
c->aux = newipaux(a->owner, cb->f[1]);
|
|
free(a);
|
|
} else
|
|
error(Ebadctl);
|
|
|
|
poperror();
|
|
free(cb);
|
|
return n;
|
|
}
|