/*
* Copyright (c) 2002, 2003 Niels Provos <provos@citi.umich.edu>
* All rights reserved.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include <sys/types.h>
#include <sys/param.h>
#include "config.h"
#include <sys/queue.h>
#include <sys/tree.h>
#include <pcap.h>
#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <ctype.h>
#include <dnet.h>
#undef timeout_pending
#undef timeout_initialized
#include <event.h>
#include "network.h"
#include "router.h"
#include "pool.h"
#include "interface.h"
/* Structure for routers */
static SPLAY_HEAD(routetree, router) routers;
int
routercompare(struct router *a, struct router *b)
{
return (addr_cmp(&a->addr, &b->addr));
}
SPLAY_PROTOTYPE(routetree, router, node, routercompare);
SPLAY_GENERATE(routetree, router, node, routercompare);
/* Structure for links */
int
linkcompare(struct link_entry *a, struct link_entry *b)
{
return (addr_cmp(&a->dst, &b->dst));
}
SPLAY_PROTOTYPE(linktree, link_entry, node, linkcompare);
SPLAY_GENERATE(linktree, link_entry, node, linkcompare);
/* Structure for tunnels */
static SPLAY_HEAD(tunneltree, router_entry) tunnels;
int
tunnelcompare(struct router_entry *a, struct router_entry *b)
{
int res;
if ((res = addr_cmp(&a->tunnel_src, &b->tunnel_src)) != 0)
return (res);
else
return (addr_cmp(&a->tunnel_dst, &b->tunnel_dst));
}
SPLAY_PROTOTYPE(tunneltree, router_entry, node, tunnelcompare);
SPLAY_GENERATE(tunneltree, router_entry, node, tunnelcompare);
/* Exported */
int router_used = 0;
struct network *entry_routers = NULL;
struct network *reverse = NULL;
/* Internal */
static struct pool *pool_network;
/* Network trinary tree code by Bill Cheswick; stylified and munged by NP */
static void network_addnode(struct network **, struct network *,
struct network **);
static void
network_copydata(struct network *dst, struct network *src)
{
memmove(&dst->data, &src->data, sizeof(dst->data));
}
/*
* walk down a tree adding nodes back in
*/
static void
network_walkadd(struct network **root, struct network *net,
struct network **netqueue)
{
struct network *left, *right;
left = net->left;
right = net->right;
net->left = NULL;
net->right = NULL;
network_addnode(root, net, netqueue);
if (left != NULL)
network_walkadd(root, left, netqueue);
if (right != NULL)
network_walkadd(root, right, netqueue);
}
/*
* calculate depth
*/
static void
network_calcd(struct network *net)
{
struct network *tmp;
int depth;
if (net == NULL)
return;
depth = 0;
if ((tmp = net->left) != NULL)
depth = tmp->depth;
tmp = net->right;
if (tmp != NULL && tmp->depth > depth)
depth = tmp->depth;
tmp = net->mid;
if (tmp != NULL && tmp->depth > depth)
depth = tmp->depth;
net->depth = depth + 1;
}
/*
* balance the tree at the current node
*/
static void
network_balancetree(struct network **cur)
{
struct network *net, *left, *right;
int dl, dr;
/*
* if left and right are too out of balance, rotate tree node
*/
net = *cur;
dl = dr = 0;
if ((left = net->left) != NULL)
dl = left->depth;
if ((right = net->right)!= NULL)
dr = right->depth;
if (dl > dr + 1) {
/* Rotate left */
net->left = left->right;
left->right = net;
*cur = left;
network_calcd(net);
network_calcd(left);
} else if (dr > dl + 1) {
/* Rotate right */
net->right = right->left;
right->left = net;
*cur = right;
network_calcd(net);
network_calcd(right);
} else
network_calcd(net);
}
/*
* add a new node to the tree
*/
static void
network_addnode(struct network **root, struct network *new,
struct network **netqueue)
{
struct network *net, *left;
if ((net = *root) == NULL) {
*root = new;
new->depth = 1;
return;
}
switch(network_compare(new, net)){
case NET_PRECEEDS:
network_addnode(&net->left, new, netqueue);
break;
case NET_FOLLOWS:
network_addnode(&net->right, new, netqueue);
break;
case NET_CONTAINS:
/*
* if new node is superset of tree node, replace tree
* node and queue tree node to be merged into root.
*/
*root = new;
new->depth = 1;
left = pool_alloc(pool_network);
memset(left, 0, sizeof(struct network));
left->mid = *netqueue;
*netqueue = left;
left->left = net;
break;
case NET_EQUALS:
network_copydata(net, new);
pool_free(pool_network, new);
break;
case NET_CONTAINED:
network_addnode(&net->mid, new, netqueue);
break;
}
network_balancetree(root);
}
/*
* Add a route to the structure. a and mask must be in host byte order.
*/
void
network_add(struct network **root, struct addr *addr, void *data)
{
struct network *netqueue = NULL;
struct network *p;
p = pool_alloc(pool_network);
memset(p, 0, sizeof(struct network));
p->net = *addr;
p->data = data;
network_addnode(root, p, &netqueue);
while ((p = netqueue) != NULL) {
netqueue = p->mid;
network_walkadd(root, p->left, &netqueue);
pool_free(pool_network, p);
}
}
/*
* Find address la. Must be in host byte order.
*/
void *
network_lookup(struct network *root, struct addr *addr)
{
struct network *net, *last;
last = NULL;
for (net = root; net != NULL; ) {
struct addr tmp;
tmp = net->net;
tmp.addr_bits = IP_ADDR_BITS;
if (addr_cmp(addr, &tmp) >= 0) {
addr_bcast(&net->net, &tmp);
tmp.addr_bits = IP_ADDR_BITS;
if (addr_cmp(addr, &tmp) <= 0) {
last = net;
net = net->mid;
} else {
net = net->right;
}
} else {
net = net->left;
}
}
return (last != NULL ? last->data : NULL);
}
void
network_cleanup(struct network *net, int needfree)
{
if (net->mid != NULL)
network_cleanup(net->mid, needfree);
if (net->left != NULL)
network_cleanup(net->left, needfree);
if (net->right != NULL)
network_cleanup(net->right, needfree);
if (needfree && net->data != NULL)
free(net->data);
pool_free(pool_network, net);
}
/* Functions to deal with Honeyd virtual routers */
void
router_init(void)
{
SPLAY_INIT(&routers);
SPLAY_INIT(&tunnels);
pool_network = pool_init(sizeof(struct network));
}
struct router *
router_find(struct addr *addr)
{
struct router tmp;
tmp.addr = *addr;
return (SPLAY_FIND(routetree, &routers, &tmp));
}
struct router *
router_new(struct addr *addr)
{
struct router *new;
if (router_find(addr))
return (NULL);
if ((new = calloc(1, sizeof(struct router))) == NULL)
err(1, "%s: calloc", __FUNCTION__);
new->routes = NULL;
new->addr = *addr;
SPLAY_INIT(&new->links);
SPLAY_INSERT(routetree, &routers, new);
return (new);
}
/* Frees the whole routing table */
void
router_end(void)
{
struct router *router;
struct router_entry *tunnel;
/*
* Clean up configured tunnels:
* Not really necessary as we do not need to deallocate anything.
*/
while ((tunnel = SPLAY_ROOT(&tunnels)) != NULL)
SPLAY_REMOVE(tunneltree, &tunnels, tunnel);
while ((router = SPLAY_ROOT(&routers)) != NULL) {
SPLAY_REMOVE(routetree, &routers, router);
if (router->routes != NULL)
network_cleanup(router->routes, 1);
free(router);
}
if (reverse != NULL)
network_cleanup(reverse, 0);
if (entry_routers != NULL)
network_cleanup(entry_routers, 0);
router_used = 0;
}
/*
* Defines multiple entry points into the routing topology.
* The entry is determined by the destination IP address.
*/
int
router_start(struct addr *addr, struct addr *pnetwork)
{
struct router *entry;
struct addr tmp, network;
addr_pton("0.0.0.0/0", &network);
network.addr_bits = 0; /* libdnet bug */
if (pnetwork != NULL)
network = *pnetwork;
/* Check for overlap */
tmp = network;
tmp.addr_bits = IP_ADDR_BITS;
if (network_lookup(entry_routers, &tmp) != NULL)
return (-1);
addr_bcast(&network, &tmp);
tmp.addr_bits = IP_ADDR_BITS;
if (network_lookup(entry_routers, &tmp) != NULL)
return (-1);
if (!router_used)
router_used = 1;
if ((entry = router_new(addr)) == NULL)
return (-1);
entry->network = network;
entry->flags |= ROUTER_ISENTRY;
network_add(&entry_routers, &entry->network, entry);
return (0);
}
struct link_entry *
link_entry_find(struct linktree *root, struct addr *dst)
{
struct link_entry tmp;
tmp.dst = *dst;
return (SPLAY_FIND(linktree, root, &tmp));
}
struct link_entry *
link_entry_new(struct addr *dst)
{
struct link_entry *link;
if ((link = calloc(1, sizeof(struct link_entry))) == NULL)
err(1, "%s: calloc", __func__);
link->dst = *dst;
return (link);
}
struct router_entry *
router_entry_new(struct addr *net, struct router *parent,
struct router *gw, enum route_type type)
{
struct router_entry *rte;
if ((rte = calloc(1, sizeof(struct router_entry))) == NULL)
err(1, "%s: calloc", __func__);
rte->net = *net;
rte->parent = parent;
rte->type = type;
if (type == ROUTE_NET)
rte->gw = gw;
return (rte);
}
int
router_add_link(struct router *r, struct addr *addr)
{
struct router_entry *rte;
rte = router_entry_new(addr, r, NULL, ROUTE_LINK);
network_add(&r->routes, addr, rte);
/* Add this router in the reverse lookup */
network_add(&reverse, addr, r);
return (0);
}
int
router_add_unreach(struct router *r, struct addr *addr)
{
struct router_entry *rte;
rte = router_entry_new(addr, r, NULL, ROUTE_UNREACH);
network_add(&r->routes, addr, rte);
return (0);
}
int
router_add_net(struct router *r, struct addr *net, struct router *gw,
int latency, int packetloss, int bandwidth, struct link_drop *drop)
{
struct link_entry *link;
struct router_entry *rte;
int mbw = 0, mdiv = 0;
/* The link is where packets get queued */
link = link_entry_find(&r->links, &gw->addr);
if (link == NULL) {
link = link_entry_new(&gw->addr);
SPLAY_INSERT(linktree, &r->links, link);
}
if (bandwidth) {
/* Get an estimate for the multiplier and divider */
mbw = (8 * 1000000) / bandwidth;
mdiv = 1000;
if (!mbw) {
mbw = (8 * 100000000) / bandwidth;
mdiv = 100000;
}
}
rte = router_entry_new(net, r, gw, ROUTE_NET);
/* Keep track of attributes */
rte->link = link;
/* Only update attributes that have not been set yet */
if (!link->latency)
link->latency = latency;
if (!link->packetloss)
link->packetloss = packetloss;
if (!link->bandwidth) {
link->bandwidth = mbw;
link->divider = mdiv;
link->red = *drop;
}
network_add(&r->routes, net, rte);
return (0);
}
int
router_add_tunnel(struct router *r, struct addr *net,
struct addr *tunnel_src, struct addr *tunnel_dst)
{
struct router_entry *rte;
/* Match the IP address against an interface */
if (interface_find_addr(tunnel_src) == NULL)
return (-1);
if (router_find_tunnel(tunnel_src, tunnel_dst) != NULL)
return (-1);
rte = router_entry_new(net, r, NULL, ROUTE_TUNNEL);
rte->tunnel_src = *tunnel_src;
rte->tunnel_dst = *tunnel_dst;
network_add(&r->routes, net, rte);
SPLAY_INSERT(tunneltree, &tunnels, rte);
return (0);
}
struct router_entry *
router_find_tunnel(struct addr *src, struct addr *dst)
{
struct router_entry tmp;
tmp.tunnel_src = *src;
tmp.tunnel_dst = *dst;
return (SPLAY_FIND(tunneltree, &tunnels, &tmp));
}
syntax highlighted by Code2HTML, v. 0.9.1