[Click] [PATCH] Templify LinkTable element
Roberto Riggio
roberto.riggio at create-net.org
Thu Feb 24 04:05:58 EST 2011
This patch introduces a LinkTableBase template element. The old LinkTable
is then defined as:
class LinkTable : public LinkTableBase<IPAddress, Path>
Where IPAddress is the vertex and Path is the edge. In this way you can use
the linktable element also for situation where a node has multiple
interfaces.
Signed-off-by: Roberto Riggio<roberto.riggio at create-net.org>
--
diff -urN '--exclude=.git' click.upstream/elements/wifi/linktable.cc click/elements/wifi/linktable.cc
--- click.upstream/elements/wifi/linktable.cc 2011-02-24 09:15:16.991988001 +0100
+++ click/elements/wifi/linktable.cc 2011-02-04 11:22:26.506339000 +0100
@@ -21,269 +21,19 @@
#include<click/confparse.hh>
#include<click/error.hh>
#include<click/glue.hh>
-#include<elements/wifi/path.hh>
#include<click/straccum.hh>
CLICK_DECLS
LinkTable::LinkTable()
- : _timer(this)
{
}
-
-
LinkTable::~LinkTable()
{
}
-
-int
-LinkTable::initialize (ErrorHandler *)
-{
- _timer.initialize(this);
- _timer.schedule_now();
- return 0;
-}
-
-void
-LinkTable::run_timer(Timer *)
-{
- clear_stale();
- dijkstra(true);
- dijkstra(false);
- _timer.schedule_after_msec(5000);
-}
-void *
-LinkTable::cast(const char *n)
-{
- if (strcmp(n, "LinkTable") == 0)
- return (LinkTable *) this;
- else
- return 0;
-}
-int
-LinkTable::configure (Vector<String> &conf, ErrorHandler *errh)
-{
- int ret;
- int stale_period = 120;
- ret = cp_va_kparse(conf, this, errh,
- "IP", 0, cpIPAddress,&_ip,
- "STALE", 0, cpUnsigned,&stale_period,
- cpEnd);
-
- if (!_ip)
- return errh->error("IP not specified");
-
- _stale_timeout.assign(stale_period, 0);
-
- _hosts.insert(_ip, HostInfo(_ip));
- return ret;
-}
-
-
-void
-LinkTable::take_state(Element *e, ErrorHandler *) {
- LinkTable *q = (LinkTable *)e->cast("LinkTable");
- if (!q) return;
-
- _hosts = q->_hosts;
- _links = q->_links;
- dijkstra(true);
- dijkstra(false);
-}
-
-int
-LinkTable::static_update_link(const String&arg, Element *e,
- void *, ErrorHandler *errh)
-{
- LinkTable *n = (LinkTable *) e;
- Vector<String> args;
- IPAddress from;
- IPAddress to;
- uint32_t seq;
- uint32_t age;
- uint32_t metric;
- cp_spacevec(arg, args);
-
- if (args.size() != 5) {
- return errh->error("Must have three arguments: currently has %d: %s", args.size(), args[0].c_str());
- }
-
-
- if (!cp_ip_address(args[0],&from)) {
- return errh->error("Couldn't read IPAddress out of from");
- }
-
- if (!cp_ip_address(args[1],&to)) {
- return errh->error("Couldn't read IPAddress out of to");
- }
- if (!cp_unsigned(args[2],&metric)) {
- return errh->error("Couldn't read metric");
- }
-
- if (!cp_unsigned(args[3],&seq)) {
- return errh->error("Couldn't read seq");
- }
-
- if (!cp_unsigned(args[4],&age)) {
- return errh->error("Couldn't read age");
- }
-
- n->update_link(from, to, seq, age, metric);
- return 0;
-
-}
-void
-LinkTable::clear()
-{
- _hosts.clear();
- _links.clear();
-
-}
-bool
-LinkTable::update_link(IPAddress from, IPAddress to,
- uint32_t seq, uint32_t age, uint32_t metric)
-{
- if (!from || !to || !metric) {
- return false;
- }
- if (_stale_timeout.sec()< (int) age) {
- return true;
- }
-
- /* make sure both the hosts exist */
- HostInfo *nfrom = _hosts.findp(from);
- if (!nfrom) {
- HostInfo foo = HostInfo(from);
- _hosts.insert(from, foo);
- nfrom = _hosts.findp(from);
- }
- HostInfo *nto = _hosts.findp(to);
- if (!nto) {
- _hosts.insert(to, HostInfo(to));
- nto = _hosts.findp(to);
- }
-
- assert(nfrom);
- assert(nto);
-
- IPPair p = IPPair(from, to);
- LinkInfo *lnfo = _links.findp(p);
- if (!lnfo) {
- _links.insert(p, LinkInfo(from, to, seq, age, metric));
- } else {
- lnfo->update(seq, age, metric);
- }
- return true;
-}
-
-
-LinkTable::Link
-LinkTable::random_link()
-{
- int ndx = click_random(0, _links.size() - 1);
- int current_ndx = 0;
- for (LTIter iter = _links.begin(); iter.live(); iter++, current_ndx++) {
- if (current_ndx == ndx) {
- LinkInfo n = iter.value();
- return Link(n._from, n._to, n._seq, n._metric);
- }
- }
- click_chatter("LinkTable %s: random_link overestimated number of elements\n",
- name().c_str());
- return Link();
-
-}
-Vector<IPAddress>
-LinkTable::get_hosts()
-{
- Vector<IPAddress> v;
- for (HTIter iter = _hosts.begin(); iter.live(); iter++) {
- HostInfo n = iter.value();
- v.push_back(n._ip);
- }
- return v;
-}
-
uint32_t
-LinkTable::get_host_metric_to_me(IPAddress s)
-{
- if (!s) {
- return 0;
- }
- HostInfo *nfo = _hosts.findp(s);
- if (!nfo) {
- return 0;
- }
- return nfo->_metric_to_me;
-}
-
-uint32_t
-LinkTable::get_host_metric_from_me(IPAddress s)
-{
- if (!s) {
- return 0;
- }
- HostInfo *nfo = _hosts.findp(s);
- if (!nfo) {
- return 0;
- }
- return nfo->_metric_from_me;
-}
-
-uint32_t
-LinkTable::get_link_metric(IPAddress from, IPAddress to)
-{
- if (!from || !to) {
- return 0;
- }
- if (_blacklist.findp(from) || _blacklist.findp(to)) {
- return 0;
- }
- IPPair p = IPPair(from, to);
- LinkInfo *nfo = _links.findp(p);
- if (!nfo) {
- return 0;
- }
- return nfo->_metric;
-}
-uint32_t
-LinkTable::get_link_seq(IPAddress from, IPAddress to)
-{
- if (!from || !to) {
- return 0;
- }
- if (_blacklist.findp(from) || _blacklist.findp(to)) {
- return 0;
- }
- IPPair p = IPPair(from, to);
- LinkInfo *nfo = _links.findp(p);
- if (!nfo) {
- return 0;
- }
- return nfo->_seq;
-}
-uint32_t
-LinkTable::get_link_age(IPAddress from, IPAddress to)
-{
- if (!from || !to) {
- return 0;
- }
- if (_blacklist.findp(from) || _blacklist.findp(to)) {
- return 0;
- }
- IPPair p = IPPair(from, to);
- LinkInfo *nfo = _links.findp(p);
- if (!nfo) {
- return 0;
- }
- return nfo->age();
-}
-
-
-
-unsigned
-LinkTable::get_route_metric(const Vector<IPAddress> &route)
+LinkTable::get_route_metric(const Path&route)
{
unsigned metric = 0;
for (int i = 0; i< route.size() - 1; i++) {
@@ -294,54 +44,12 @@
metric += m;
}
return metric;
-
}
-String
-LinkTable::route_to_string(Path p) {
- StringAccum sa;
- int hops = p.size()-1;
- int metric = 0;
- StringAccum sa2;
- for (int i = 0; i< p.size(); i++) {
- sa2<< p[i];
- if (i != p.size()-1) {
- int m = get_link_metric(p[i], p[i+1]);
- sa2<< " ("<< m<< ") ";
- metric += m;
- }
- }
- sa<< p[p.size()-1]<< " hops "<< hops<< " metric "<< metric<< " "<< sa2;
- return sa.take_string();
-}
-bool
-LinkTable::valid_route(const Vector<IPAddress> &route)
-{
- if (route.size()< 1) {
- return false;
- }
- /* ensure the metrics are all valid */
- unsigned metric = get_route_metric(route);
- if (metric == 0 ||
- metric>= 777777){
- return false;
- }
-
- /* ensure that a node appears no more than once */
- for (int x = 0; x< route.size(); x++) {
- for (int y = x + 1; y< route.size(); y++) {
- if (route[x] == route[y]) {
- return false;
- }
- }
- }
-
- return true;
-}
-Vector<IPAddress>
+Path
LinkTable::best_route(IPAddress dst, bool from_me)
{
- Vector<IPAddress> reverse_route;
+ Path reverse_route;
if (!dst) {
return reverse_route;
}
@@ -349,72 +57,65 @@
if (from_me) {
while (nfo&& nfo->_metric_from_me != 0) {
- reverse_route.push_back(nfo->_ip);
+ reverse_route.push_back(nfo->_address);
nfo = _hosts.findp(nfo->_prev_from_me);
}
if (nfo&& nfo->_metric_from_me == 0) {
- reverse_route.push_back(nfo->_ip);
+ reverse_route.push_back(nfo->_address);
}
} else {
while (nfo&& nfo->_metric_to_me != 0) {
- reverse_route.push_back(nfo->_ip);
+ reverse_route.push_back(nfo->_address);
nfo = _hosts.findp(nfo->_prev_to_me);
}
if (nfo&& nfo->_metric_to_me == 0) {
- reverse_route.push_back(nfo->_ip);
+ reverse_route.push_back(nfo->_address);
}
}
-
-
if (from_me) {
- Vector<IPAddress> route;
+ Path route;
/* why isn't there just push? */
for (int i=reverse_route.size() - 1; i>= 0; i--) {
route.push_back(reverse_route[i]);
}
return route;
}
-
return reverse_route;
}
String
-LinkTable::print_links()
-{
- StringAccum sa;
- for (LTIter iter = _links.begin(); iter.live(); iter++) {
- LinkInfo n = iter.value();
- sa<< n._from.unparse()<< " "<< n._to.unparse();
- sa<< " "<< n._metric;
- sa<< " "<< n._seq<< " "<< n.age()<< "\n";
- }
- return sa.take_string();
-}
-
-static int ipaddr_sorter(const void *va, const void *vb, void *) {
- IPAddress *a = (IPAddress *)va, *b = (IPAddress *)vb;
- if (a->addr() == b->addr()) {
- return 0;
- }
- return (ntohl(a->addr())< ntohl(b->addr())) ? -1 : 1;
+LinkTable::route_to_string(Path p) {
+ StringAccum sa;
+ int hops = p.size()-1;
+ int metric = 0;
+ StringAccum sa2;
+ for (int i = 0; i< p.size(); i++) {
+ sa2<< p[i];
+ if (i != p.size()-1) {
+ int m = get_link_metric(p[i], p[i+1]);
+ sa2<< " ("<< m<< ") ";
+ metric += m;
+ }
+ }
+ sa<< p[p.size()-1]<< " hops "<< hops<< " metric "<< metric<< " "<< sa2;
+ return sa.take_string();
}
-
String
LinkTable::print_routes(bool from_me, bool pretty)
{
StringAccum sa;
- Vector<IPAddress> ip_addrs;
+ Vector<IPAddress> addrs;
for (HTIter iter = _hosts.begin(); iter.live(); iter++)
- ip_addrs.push_back(iter.key());
+ addrs.push_back(iter.key());
- click_qsort(ip_addrs.begin(), ip_addrs.size(), sizeof(IPAddress), ipaddr_sorter);
+ click_qsort(addrs.begin(), addrs.size(), sizeof(IPAddress), addr_sorter<IPAddress>);
- for (int x = 0; x< ip_addrs.size(); x++) {
- IPAddress ip = ip_addrs[x];
- Vector<IPAddress> r = best_route(ip, from_me);
+ for (int x = 0; x< addrs.size(); x++) {
+ IPAddress address = addrs[x];
+ Path r = best_route(address, from_me);
if (valid_route(r)) {
if (pretty) {
sa<< route_to_string(r)<< "\n";
@@ -436,117 +137,41 @@
return sa.take_string();
}
-
-String
-LinkTable::print_hosts()
-{
- StringAccum sa;
- Vector<IPAddress> ip_addrs;
-
- for (HTIter iter = _hosts.begin(); iter.live(); iter++)
- ip_addrs.push_back(iter.key());
-
- click_qsort(ip_addrs.begin(), ip_addrs.size(), sizeof(IPAddress), ipaddr_sorter);
-
- for (int x = 0; x< ip_addrs.size(); x++)
- sa<< ip_addrs[x]<< "\n";
-
- return sa.take_string();
-}
-
-
-
-void
-LinkTable::clear_stale() {
-
- LTable links;
- for (LTIter iter = _links.begin(); iter.live(); iter++) {
- LinkInfo nfo = iter.value();
- if ((unsigned) _stale_timeout.sec()>= nfo.age()) {
- links.insert(IPPair(nfo._from, nfo._to), nfo);
- } else {
- if (0) {
- click_chatter("%{element} :: %s removing link %s -> %s metric %d seq %d age %d\n",
- this,
- __func__,
- nfo._from.unparse().c_str(),
- nfo._to.unparse().c_str(),
- nfo._metric,
- nfo._seq,
- nfo.age());
- }
- }
- }
- _links.clear();
-
- for (LTIter iter = links.begin(); iter.live(); iter++) {
- LinkInfo nfo = iter.value();
- _links.insert(IPPair(nfo._from, nfo._to), nfo);
- }
-
-}
-
-Vector<IPAddress>
-LinkTable::get_neighbors(IPAddress ip)
-{
- Vector<IPAddress> neighbors;
-
- typedef HashMap<IPAddress, bool> IPMap;
- IPMap ip_addrs;
-
- for (HTIter iter = _hosts.begin(); iter.live(); iter++) {
- ip_addrs.insert(iter.value()._ip, true);
- }
-
- for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); i++) {
- HostInfo *neighbor = _hosts.findp(i.key());
- assert(neighbor);
- if (ip != neighbor->_ip) {
- LinkInfo *lnfo = _links.findp(IPPair(ip, neighbor->_ip));
- if (lnfo) {
- neighbors.push_back(neighbor->_ip);
- }
- }
-
- }
-
- return neighbors;
-}
void
LinkTable::dijkstra(bool from_me)
{
Timestamp start = Timestamp::now();
- IPAddress src = _ip;
- typedef HashMap<IPAddress, bool> IPMap;
- IPMap ip_addrs;
+ typedef HashMap<IPAddress, bool> AddressMap;
+ typedef AddressMap::const_iterator AMIter;
+
+ AddressMap addrs;
for (HTIter iter = _hosts.begin(); iter.live(); iter++) {
- ip_addrs.insert(iter.value()._ip, true);
+ addrs.insert(iter.value()._address, true);
}
- for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); i++) {
+ for (AMIter i = addrs.begin(); i.live(); i++) {
/* clear them all initially */
HostInfo *n = _hosts.findp(i.key());
n->clear(from_me);
}
- HostInfo *root_info = _hosts.findp(src);
-
+ HostInfo *root_info = _hosts.findp(_ip);
assert(root_info);
if (from_me) {
- root_info->_prev_from_me = root_info->_ip;
+ root_info->_prev_from_me = root_info->_address;
root_info->_metric_from_me = 0;
} else {
- root_info->_prev_to_me = root_info->_ip;
+ root_info->_prev_to_me = root_info->_address;
root_info->_metric_to_me = 0;
}
- IPAddress current_min_ip = root_info->_ip;
+ IPAddress current_min_address = root_info->_address;
- while (current_min_ip) {
- HostInfo *current_min = _hosts.findp(current_min_ip);
+ while (current_min_address) {
+ HostInfo *current_min = _hosts.findp(current_min_address);
assert(current_min);
if (from_me) {
current_min->_marked_from_me = true;
@@ -555,7 +180,7 @@
}
- for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); i++) {
+ for (AMIter i = addrs.begin(); i.live(); i++) {
HostInfo *neighbor = _hosts.findp(i.key());
assert(neighbor);
bool marked = neighbor->_marked_to_me;
@@ -567,9 +192,9 @@
continue;
}
- IPPair pair = IPPair(neighbor->_ip, current_min_ip);
+ AddressPair pair = AddressPair(neighbor->_address, current_min_address);
if (from_me) {
- pair = IPPair(current_min_ip, neighbor->_ip);
+ pair = AddressPair(current_min_address, neighbor->_address);
}
LinkInfo *lnfo = _links.findp(pair);
if (!lnfo || !lnfo->_metric) {
@@ -589,18 +214,18 @@
adjusted_metric< neighbor_metric) {
if (from_me) {
neighbor->_metric_from_me = adjusted_metric;
- neighbor->_prev_from_me = current_min_ip;
+ neighbor->_prev_from_me = current_min_address;
} else {
neighbor->_metric_to_me = adjusted_metric;
- neighbor->_prev_to_me = current_min_ip;
+ neighbor->_prev_to_me = current_min_address;
}
}
}
- current_min_ip = IPAddress();
+ current_min_address = IPAddress();
uint32_t min_metric = ~0;
- for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); i++) {
+ for (AMIter i = addrs.begin(); i.live(); i++) {
HostInfo *nfo = _hosts.findp(i.key());
uint32_t metric = nfo->_metric_to_me;
bool marked = nfo->_marked_to_me;
@@ -610,116 +235,14 @@
}
if (!marked&& metric&&
metric< min_metric) {
- current_min_ip = nfo->_ip;
+ current_min_address = nfo->_address;
min_metric = metric;
}
}
-
- }
-
- dijkstra_time = Timestamp::now() - start;
- //StringAccum sa;
- //sa<< "dijstra took "<< finish - start;
- //click_chatter("%s: %s\n", name().c_str(), sa.take_string().c_str());
-}
-
-
-enum {H_BLACKLIST,
- H_BLACKLIST_CLEAR,
- H_BLACKLIST_ADD,
- H_BLACKLIST_REMOVE,
- H_LINKS,
- H_ROUTES_OLD,
- H_ROUTES_FROM,
- H_ROUTES_TO,
- H_HOSTS,
- H_CLEAR,
- H_DIJKSTRA,
- H_DIJKSTRA_TIME};
-
-static String
-LinkTable_read_param(Element *e, void *thunk)
-{
- LinkTable *td = (LinkTable *)e;
- switch ((uintptr_t) thunk) {
- case H_BLACKLIST: {
- StringAccum sa;
- typedef HashMap<IPAddress, IPAddress> IPTable;
- typedef IPTable::const_iterator IPIter;
-
-
- for (IPIter iter = td->_blacklist.begin(); iter.live(); iter++) {
- sa<< iter.value()<< " ";
- }
- return sa.take_string() + "\n";
- }
- case H_LINKS: return td->print_links();
- case H_ROUTES_TO: return td->print_routes(false, true);
- case H_ROUTES_FROM: return td->print_routes(true, true);
- case H_ROUTES_OLD: return td->print_routes(true, false);
- case H_HOSTS: return td->print_hosts();
- case H_DIJKSTRA_TIME: {
- StringAccum sa;
- sa<< td->dijkstra_time<< "\n";
- return sa.take_string();
- }
- default:
- return String();
- }
-}
-static int
-LinkTable_write_param(const String&in_s, Element *e, void *vparam,
- ErrorHandler *errh)
-{
- LinkTable *f = (LinkTable *)e;
- String s = cp_uncomment(in_s);
- switch((intptr_t)vparam) {
- case H_BLACKLIST_CLEAR: {
- f->_blacklist.clear();
- break;
- }
- case H_BLACKLIST_ADD: {
- IPAddress m;
- if (!cp_ip_address(s,&m))
- return errh->error("blacklist_add parameter must be ipaddress");
- f->_blacklist.insert(m, m);
- break;
- }
- case H_BLACKLIST_REMOVE: {
- IPAddress m;
- if (!cp_ip_address(s,&m))
- return errh->error("blacklist_add parameter must be ipaddress");
- f->_blacklist.erase(m);
- break;
- }
- case H_CLEAR: f->clear(); break;
- case H_DIJKSTRA: f->dijkstra(true); f->dijkstra(false); break;
}
- return 0;
-}
-
-
-void
-LinkTable::add_handlers() {
- add_read_handler("routes", LinkTable_read_param, (void *)H_ROUTES_FROM);
- add_read_handler("routes_old", LinkTable_read_param, (void *)H_ROUTES_OLD);
- add_read_handler("routes_from", LinkTable_read_param, (void *)H_ROUTES_FROM);
- add_read_handler("routes_to", LinkTable_read_param, (void *)H_ROUTES_TO);
- add_read_handler("links", LinkTable_read_param, (void *)H_LINKS);
- add_read_handler("hosts", LinkTable_read_param, (void *)H_HOSTS);
- add_read_handler("blacklist", LinkTable_read_param, (void *)H_BLACKLIST);
- add_read_handler("dijkstra_time", LinkTable_read_param, (void *)H_DIJKSTRA_TIME);
-
- add_write_handler("clear", LinkTable_write_param, (void *)H_CLEAR);
- add_write_handler("blacklist_clear", LinkTable_write_param, (void *)H_BLACKLIST_CLEAR);
- add_write_handler("blacklist_add", LinkTable_write_param, (void *)H_BLACKLIST_ADD);
- add_write_handler("blacklist_remove", LinkTable_write_param, (void *)H_BLACKLIST_REMOVE);
- add_write_handler("dijkstra", LinkTable_write_param, (void *)H_DIJKSTRA);
-
-
- add_write_handler("update_link", static_update_link, 0);
+ _dijkstra_time = Timestamp::now() - start;
}
diff -urN '--exclude=.git' click.upstream/elements/wifi/linktable.hh click/elements/wifi/linktable.hh
--- click.upstream/elements/wifi/linktable.hh 2011-02-24 09:15:16.991988001 +0100
+++ click/elements/wifi/linktable.hh 2011-02-04 11:22:26.506339000 +0100
@@ -6,6 +6,10 @@
#include<click/element.hh>
#include<click/bighashmap.hh>
#include<click/hashmap.hh>
+#include<click/confparse.hh>
+#include<click/error.hh>
+#include<click/glue.hh>
+#include<click/straccum.hh>
#include "path.hh"
CLICK_DECLS
@@ -20,143 +24,117 @@
* =a ARPTable
*
*/
-class IPPair {
- public:
-
- IPAddress _to;
- IPAddress _from;
-
- IPPair()
- : _to(), _from() {
- }
-
- IPPair(IPAddress from, IPAddress to)
- : _to(to), _from(from) {
- }
-
- bool contains(IPAddress foo) const {
- return (foo == _to) || (foo == _from);
- }
-
- bool other(IPAddress foo) const {
- return (_to == foo) ? _from : _to;
- }
-
- inline hashcode_t hashcode() const {
- return CLICK_NAME(hashcode)(_to) + CLICK_NAME(hashcode)(_from);
- }
-
- inline bool operator==(IPPair other) const {
- return (other._to == _to&& other._from == _from);
- }
-};
-
-
-class LinkTable: public Element{
+template<typename T, typename U>
+class LinkTableBase: public Element{
public:
/* generic click-mandated stuff*/
- LinkTable();
- ~LinkTable();
+ LinkTableBase();
+ ~LinkTableBase();
void add_handlers();
- const char* class_name() const { return "LinkTable"; }
+ const char* class_name() const { return "LinkTableBase"; }
+ int configure (Vector<String> &, ErrorHandler *);
int initialize(ErrorHandler *);
void run_timer(Timer *);
- int configure(Vector<String> &conf, ErrorHandler *errh);
void take_state(Element *, ErrorHandler *);
void *cast(const char *n);
/* read/write handlers */
- String print_routes(bool, bool);
+ virtual String print_routes(bool, bool) = 0;
String print_links();
String print_hosts();
- static int static_update_link(const String&arg, Element *e,
- void *, ErrorHandler *errh);
void clear();
/* other public functions */
- String route_to_string(Path p);
- bool update_link(IPAddress from, IPAddress to,
- uint32_t seq, uint32_t age, uint32_t metric);
- bool update_both_links(IPAddress a, IPAddress b,
- uint32_t seq, uint32_t age, uint32_t metric) {
+ virtual String route_to_string(U) = 0;
+ bool update_link(T from, T to, uint32_t seq, uint32_t age, uint32_t metric, uint16_t channel);
+ bool update_both_links(T a, T b, uint32_t seq, uint32_t age, uint32_t metric, uint16_t channel) {
if (update_link(a,b,seq,age, metric)) {
return update_link(b,a,seq,age, metric);
}
return false;
}
+ virtual U best_route(T, bool) = 0;
- uint32_t get_link_metric(IPAddress from, IPAddress to);
- uint32_t get_link_seq(IPAddress from, IPAddress to);
- uint32_t get_link_age(IPAddress from, IPAddress to);
- bool valid_route(const Vector<IPAddress> &route);
- unsigned get_route_metric(const Vector<IPAddress> &route);
- Vector<IPAddress> get_neighbors(IPAddress ip);
- void dijkstra(bool);
- void clear_stale();
- Vector<IPAddress> best_route(IPAddress dst, bool from_me);
-
- Vector< Vector<IPAddress> > top_n_routes(IPAddress dst, int n);
- uint32_t get_host_metric_to_me(IPAddress s);
- uint32_t get_host_metric_from_me(IPAddress s);
- Vector<IPAddress> get_hosts();
+ virtual uint32_t get_route_metric(const U&) = 0;
- class Link {
- public:
- IPAddress _from;
- IPAddress _to;
- uint32_t _seq;
- uint32_t _metric;
- Link() : _from(), _to(), _seq(0), _metric(0) { }
- Link(IPAddress from, IPAddress to, uint32_t seq, uint32_t metric) {
- _from = from;
- _to = to;
- _seq = seq;
- _metric = metric;
- }
- };
+ uint16_t get_link_channel(T from, T to);
+ uint32_t get_link_metric(T from, T to);
+ uint32_t get_link_seq(T from, T to);
+ uint32_t get_link_age(T from, T to);
- Link random_link();
+ bool valid_route(const U&);
+ virtual void dijkstra(bool) = 0;
+ void clear_stale();
+ uint32_t get_host_metric_to_me(T s);
+ uint32_t get_host_metric_from_me(T s);
+ Vector<T> get_hosts();
- typedef HashMap<IPAddress, IPAddress> IPTable;
- typedef IPTable::const_iterator IPIter;
+ typedef HashMap<T, T> AddressTable;
+ typedef typename HashMap<T, T>::const_iterator ATIter;
- IPTable _blacklist;
+ HashMap<T, T> _blacklist;
- Timestamp dijkstra_time;
protected:
+
+ class AddressPair {
+ public:
+ T _to;
+ T _from;
+ AddressPair()
+ : _to(), _from() {
+ }
+ AddressPair(T from, T to)
+ : _to(to), _from(from) {
+ }
+ bool contains(T foo) const {
+ return (foo == _to) || (foo == _from);
+ }
+ bool other(T foo) const {
+ return (_to == foo) ? _from : _to;
+ }
+ inline hashcode_t hashcode() const {
+ return CLICK_NAME(hashcode)(_to) + CLICK_NAME(hashcode)(_from);
+ }
+ inline bool operator==(AddressPair other) const {
+ return (other._to == _to&& other._from == _from);
+ }
+ };
+
class LinkInfo {
public:
- IPAddress _from;
- IPAddress _to;
- unsigned _metric;
+ T _from;
+ T _to;
+ uint32_t _metric;
uint32_t _seq;
uint32_t _age;
+ uint32_t _channel;
Timestamp _last_updated;
LinkInfo() {
- _from = IPAddress();
- _to = IPAddress();
+ _from = T();
+ _to = T();
_metric = 0;
_seq = 0;
_age = 0;
}
- LinkInfo(IPAddress from, IPAddress to,
- uint32_t seq, uint32_t age, unsigned metric) {
+ LinkInfo(T from, T to,
+ uint32_t seq, uint32_t age, uint32_t metric, uint32_t channel) {
_from = from;
_to = to;
_metric = metric;
_seq = seq;
_age = age;
+ _channel = channel;
_last_updated.assign_now();
}
LinkInfo(const LinkInfo&p) :
_from(p._from), _to(p._to),
_metric(p._metric), _seq(p._seq),
- _age(p._age),
+ _age(p._age), _channel(p._channel),
_last_updated(p._last_updated)
{ }
@@ -164,45 +142,52 @@
Timestamp now = Timestamp::now();
return _age + (now.sec() - _last_updated.sec());
}
- void update(uint32_t seq, uint32_t age, unsigned metric) {
+ void update(uint32_t seq, uint32_t age, uint32_t metric, uint32_t channel) {
if (seq<= _seq) {
return;
}
_metric = metric;
_seq = seq;
_age = age;
+ _channel = channel;
_last_updated.assign_now();
}
-
};
class HostInfo {
public:
- IPAddress _ip;
+ T _address;
uint32_t _metric_from_me;
uint32_t _metric_to_me;
- IPAddress _prev_from_me;
- IPAddress _prev_to_me;
+ T _prev_from_me;
+ T _prev_to_me;
bool _marked_from_me;
bool _marked_to_me;
- HostInfo(IPAddress p) {
- _ip = p;
+ HostInfo() {
+ _address = T();
_metric_from_me = 0;
_metric_to_me = 0;
- _prev_from_me = IPAddress();
- _prev_to_me = IPAddress();
+ _prev_from_me = T();
+ _prev_to_me = T();
_marked_from_me = false;
_marked_to_me = false;
}
- HostInfo() {
- HostInfo(IPAddress());
+
+ HostInfo(T address) {
+ _address = address;
+ _metric_from_me = 0;
+ _metric_to_me = 0;
+ _prev_from_me = T();
+ _prev_to_me = T();
+ _marked_from_me = false;
+ _marked_to_me = false;
}
HostInfo(const HostInfo&p) :
- _ip(p._ip),
+ _address(p._address),
_metric_from_me(p._metric_from_me),
_metric_to_me(p._metric_to_me),
_prev_from_me(p._prev_from_me),
@@ -213,35 +198,509 @@
void clear(bool from_me) {
if (from_me ) {
- _prev_from_me = IPAddress();
+ _prev_from_me = T();
_metric_from_me = 0;
_marked_from_me = false;
} else {
- _prev_to_me = IPAddress();
+ _prev_to_me = T();
_metric_to_me = 0;
_marked_to_me = false;
}
}
-
};
- typedef HashMap<IPAddress, HostInfo> HTable;
- typedef HTable::const_iterator HTIter;
+ typedef HashMap<T, HostInfo> HTable;
+ typedef typename HTable::const_iterator HTIter;
-
- typedef HashMap<IPPair, LinkInfo> LTable;
- typedef LTable::const_iterator LTIter;
+ typedef HashMap<AddressPair, LinkInfo> LTable;
+ typedef typename LTable::const_iterator LTIter;
HTable _hosts;
LTable _links;
-
- IPAddress _ip;
+ T _ip;
Timestamp _stale_timeout;
Timer _timer;
+ Timestamp _dijkstra_time;
+
+ static int write_handler(const String&, Element *, void *, ErrorHandler *);
+ static String read_handler(Element *, void *);
+
};
+template<typename T, typename U>
+LinkTableBase<T,U>::LinkTableBase()
+ : _timer(this)
+{
+}
+
+template<typename T, typename U>
+LinkTableBase<T,U>::~LinkTableBase()
+{
+}
+
+template<typename T, typename U>
+int
+LinkTableBase<T,U>::configure (Vector<String> &conf, ErrorHandler *errh)
+{
+ int ret;
+ int stale_period = 120;
+ ret = cp_va_kparse(conf, this, errh,
+ "IP", cpkM, cpIPAddress,&_ip,
+ "STALE", 0, cpUnsigned,&stale_period,
+ cpEnd);
+
+ _stale_timeout.assign(stale_period, 0);
+ _hosts.insert(_ip, HostInfo(_ip));
+ return ret;
+}
+
+template<typename T, typename U>
+int
+LinkTableBase<T,U>::initialize (ErrorHandler *)
+{
+ _timer.initialize(this);
+ _timer.schedule_now();
+ return 0;
+}
+
+template<typename T, typename U>
+void *
+LinkTableBase<T,U>::cast(const char *n)
+{
+ if (strcmp(n, "LinkTableBase") == 0)
+ return (LinkTableBase *) this;
+ else
+ return 0;
+}
+
+template<typename T, typename U>
+void
+LinkTableBase<T,U>::run_timer(Timer *)
+{
+ clear_stale();
+ dijkstra(true);
+ dijkstra(false);
+ _timer.schedule_after_msec(5000);
+}
+
+template<typename T, typename U>
+void
+LinkTableBase<T,U>::take_state(Element *e, ErrorHandler *) {
+ LinkTableBase *q = (LinkTableBase *)e->cast("LinkTableBase");
+ if (!q) return;
+
+ _hosts = q->_hosts;
+ _links = q->_links;
+ dijkstra(true);
+ dijkstra(false);
+}
+
+template<typename T, typename U>
+void
+LinkTableBase<T,U>::clear()
+{
+ _hosts.clear();
+ _links.clear();
+
+}
+
+template<typename T, typename U>
+bool
+LinkTableBase<T,U>::update_link(T from, T to, uint32_t seq, uint32_t age, uint32_t metric, uint16_t channel)
+{
+ if (!from || !to || !metric) {
+ return false;
+ }
+ if (_stale_timeout.sec()< (int) age) {
+ return true;
+ }
+
+ /* make sure both the hosts exist */
+ HostInfo *nfrom = _hosts.findp(from);
+ if (!nfrom) {
+ _hosts.insert(from, HostInfo(from));
+ nfrom = _hosts.findp(from);
+ }
+ HostInfo *nto = _hosts.findp(to);
+ if (!nto) {
+ _hosts.insert(to, HostInfo(to));
+ nto = _hosts.findp(to);
+ }
+
+ assert(nfrom);
+ assert(nto);
+
+ AddressPair p = AddressPair(from, to);
+ LinkInfo *lnfo = _links.findp(p);
+ if (!lnfo) {
+ _links.insert(p, LinkInfo(from, to, seq, age, metric, channel));
+ } else {
+ lnfo->update(seq, age, metric, channel);
+ }
+ return true;
+}
+
+template<typename T, typename U>
+Vector<T>
+LinkTableBase<T,U>::get_hosts()
+{
+ Vector<T> addrs;
+ for (HTIter iter = _hosts.begin(); iter.live(); iter++) {
+ addrs.push_back(iter.key());
+ }
+ return addrs;
+}
+
+template<typename T, typename U>
+uint32_t
+LinkTableBase<T,U>::get_host_metric_to_me(T s)
+{
+ if (!s) {
+ return 0;
+ }
+ HostInfo *nfo = _hosts.findp(s);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->_metric_to_me;
+}
+
+template<typename T, typename U>
+uint32_t
+LinkTableBase<T,U>::get_host_metric_from_me(T s)
+{
+ if (!s) {
+ return 0;
+ }
+ HostInfo *nfo = _hosts.findp(s);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->_metric_from_me;
+}
+
+template<typename T, typename U>
+uint16_t
+LinkTableBase<T,U>::get_link_channel(T from, T to)
+{
+ if (!from || !to) {
+ return 0;
+ }
+ if (_blacklist.findp(from) || _blacklist.findp(to)) {
+ return 0;
+ }
+ AddressPair p = AddressPair(from, to);
+ LinkInfo *nfo = _links.findp(p);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->_channel;
+}
+
+template<typename T, typename U>
+uint32_t
+LinkTableBase<T,U>::get_link_metric(T from, T to)
+{
+ if (!from || !to) {
+ return 0;
+ }
+ if (_blacklist.findp(from) || _blacklist.findp(to)) {
+ return 0;
+ }
+ AddressPair p = AddressPair(from, to);
+ LinkInfo *nfo = _links.findp(p);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->_metric;
+}
+
+template<typename T, typename U>
+uint32_t
+LinkTableBase<T,U>::get_link_seq(T from, T to)
+{
+ if (!from || !to) {
+ return 0;
+ }
+ if (_blacklist.findp(from) || _blacklist.findp(to)) {
+ return 0;
+ }
+ AddressPair p = AddressPair(from, to);
+ LinkInfo *nfo = _links.findp(p);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->_seq;
+}
+
+template<typename T, typename U>
+uint32_t
+LinkTableBase<T,U>::get_link_age(T from, T to)
+{
+ if (!from || !to) {
+ return 0;
+ }
+ if (_blacklist.findp(from) || _blacklist.findp(to)) {
+ return 0;
+ }
+ AddressPair p = AddressPair(from, to);
+ LinkInfo *nfo = _links.findp(p);
+ if (!nfo) {
+ return 0;
+ }
+ return nfo->age();
+}
+
+template<typename T, typename U>
+bool
+LinkTableBase<T,U>::valid_route(const U&route)
+{
+ if (route.size()< 1) {
+ return false;
+ }
+ /* ensure the metrics are all valid */
+ unsigned metric = get_route_metric(route);
+ if (metric == 0 ||
+ metric>= 999999){
+ return false;
+ }
+
+ /* ensure that a node appears no more than once */
+ for (int x = 0; x< route.size(); x++) {
+ for (int y = x + 1; y< route.size(); y++) {
+ if (route[x] == route[y]) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+template<typename T, typename U>
+String
+LinkTableBase<T,U>::print_links()
+{
+ StringAccum sa;
+ for (LTIter iter = _links.begin(); iter.live(); iter++) {
+ LinkInfo n = iter.value();
+ sa<< n._from.unparse()<< " "<< n._to.unparse();
+ sa<< " "<< n._metric;
+ sa<< " "<< n._channel;
+ sa<< " "<< n._seq<< " "<< n.age()<< "\n";
+ }
+ return sa.take_string();
+}
+
+template<typename T>
+static int addr_sorter(const void *va, const void *vb, void *) {
+ T *a = (T *)va, *b = (T *)vb;
+ if (a->addr() == b->addr()) {
+ return 0;
+ }
+ return (ntohl(a->addr())< ntohl(b->addr())) ? -1 : 1;
+}
+
+template<typename T, typename U>
+String
+LinkTableBase<T,U>::print_hosts()
+{
+ StringAccum sa;
+ Vector<T> addrs;
+ for (HTIter iter = _hosts.begin(); iter.live(); iter++) {
+ addrs.push_back(iter.key());
+ }
+
+ click_qsort(addrs.begin(), addrs.size(), sizeof(T), addr_sorter<T>);
+
+ for (int x = 0; x< addrs.size(); x++) {
+ sa<< addrs[x]<< "\n";
+ }
+
+ return sa.take_string();
+}
+
+template<typename T, typename U>
+void
+LinkTableBase<T,U>::clear_stale() {
+
+ LTable links;
+ for (LTIter iter = _links.begin(); iter.live(); iter++) {
+ LinkInfo nfo = iter.value();
+ if ((unsigned) _stale_timeout.sec()>= nfo.age()) {
+ links.insert(AddressPair(nfo._from, nfo._to), nfo);
+ } else {
+ if (0) {
+ click_chatter("%{element} :: %s removing link %s -> %s metric %d seq %d age %d\n",
+ this,
+ __func__,
+ nfo._from.unparse().c_str(),
+ nfo._to.unparse().c_str(),
+ nfo._metric,
+ nfo._seq,
+ nfo.age());
+ }
+ }
+ }
+ _links.clear();
+
+ for (LTIter iter = links.begin(); iter.live(); iter++) {
+ LinkInfo nfo = iter.value();
+ _links.insert(AddressPair(nfo._from, nfo._to), nfo);
+ }
+
+}
+
+enum {H_BLACKLIST,
+ H_BLACKLIST_CLEAR,
+ H_BLACKLIST_ADD,
+ H_BLACKLIST_REMOVE,
+ H_LINKS,
+ H_ROUTES_OLD,
+ H_ROUTES_FROM,
+ H_ROUTES_TO,
+ H_HOSTS,
+ H_CLEAR,
+ H_DIJKSTRA,
+ H_UPDATE_LINK,
+ H_DIJKSTRA_TIME};
+
+template<typename T, typename U>
+String
+LinkTableBase<T,U>::read_handler(Element *e, void *thunk) {
+ LinkTableBase *td = (LinkTableBase *) e;
+ switch ((uintptr_t) thunk) {
+ case H_BLACKLIST: {
+ StringAccum sa;
+ for (ATIter iter = td->_blacklist.begin(); iter.live(); iter++) {
+ sa<< iter.value()<< " ";
+ }
+ return sa.take_string() + "\n";
+ }
+ case H_LINKS: return td->print_links();
+ case H_ROUTES_TO: return td->print_routes(false, true);
+ case H_ROUTES_FROM: return td->print_routes(true, true);
+ case H_ROUTES_OLD: return td->print_routes(true, false);
+ case H_HOSTS: return td->print_hosts();
+ case H_DIJKSTRA_TIME: {
+ StringAccum sa;
+ sa<< td->_dijkstra_time<< "\n";
+ return sa.take_string();
+ }
+ default:
+ return String();
+ }
+}
+
+template<typename T, typename U>
+int
+LinkTableBase<T,U>::write_handler(const String&in_s, Element *e, void *vparam, ErrorHandler * errh) {
+
+ LinkTableBase *f = (LinkTableBase *) e;
+ String s = cp_uncomment(in_s);
+ switch ((intptr_t) vparam) {
+ case H_UPDATE_LINK: {
+
+ Vector<String> args;
+ IPAddress from;
+ IPAddress to;
+ uint32_t seq;
+ uint32_t age;
+ uint32_t metric;
+ uint32_t channel;
+ cp_spacevec(in_s, args);
+
+ if (args.size() != 6) {
+ return errh->error("Must have six arguments: currently has %d: %s", args.size(), args[0].c_str());
+ }
+
+ if (!cp_ip_address(args[0],&from)) {
+ return errh->error("Couldn't read IPAddress out of from");
+ }
+
+ if (!cp_ip_address(args[1],&to)) {
+ return errh->error("Couldn't read IPAddress out of to");
+ }
+
+ if (!cp_unsigned(args[2],&metric)) {
+ return errh->error("Couldn't read metric");
+ }
+
+ if (!cp_unsigned(args[3],&seq)) {
+ return errh->error("Couldn't read seq");
+ }
+
+ if (!cp_unsigned(args[4],&age)) {
+ return errh->error("Couldn't read age");
+ }
+
+ if (!cp_unsigned(args[5],&channel)) {
+ return errh->error("Couldn't read channel");
+ }
+
+ f->update_link(from, to, seq, age, metric, channel);
+ break;
+
+ }
+ case H_BLACKLIST_CLEAR: {
+ f->_blacklist.clear();
+ break;
+ }
+ case H_BLACKLIST_ADD: {
+ IPAddress m;
+ if (!cp_ip_address(s,&m))
+ return errh->error("blacklist_add parameter must be ipaddress");
+ f->_blacklist.insert(m, m);
+ break;
+ }
+ case H_BLACKLIST_REMOVE: {
+ IPAddress m;
+ if (!cp_ip_address(s,&m))
+ return errh->error("blacklist_add parameter must be ipaddress");
+ f->_blacklist.erase(m);
+ break;
+ }
+ case H_CLEAR: f->clear(); break;
+ case H_DIJKSTRA: f->dijkstra(true); f->dijkstra(false); break;
+ }
+ return 0;
+}
+
+template<typename T, typename U>
+void
+LinkTableBase<T,U>::add_handlers() {
+ add_read_handler("routes", read_handler, H_ROUTES_FROM);
+ add_read_handler("routes_old", read_handler, H_ROUTES_OLD);
+ add_read_handler("routes_from", read_handler, H_ROUTES_FROM);
+ add_read_handler("routes_to", read_handler, H_ROUTES_TO);
+ add_read_handler("links", read_handler, H_LINKS);
+ add_read_handler("hosts", read_handler, H_HOSTS);
+ add_read_handler("blacklist", read_handler, H_BLACKLIST);
+ add_read_handler("dijkstra_time", read_handler, H_DIJKSTRA_TIME);
+ add_write_handler("clear", write_handler, H_CLEAR);
+ add_write_handler("blacklist_clear", write_handler, H_BLACKLIST_CLEAR);
+ add_write_handler("blacklist_add", write_handler, H_BLACKLIST_ADD);
+ add_write_handler("blacklist_remove", write_handler, H_BLACKLIST_REMOVE);
+ add_write_handler("dijkstra", write_handler, H_DIJKSTRA);
+ add_write_handler("update_link", write_handler, H_UPDATE_LINK);
+}
+
+class LinkTable : public LinkTableBase<IPAddress, Path> { public:
+
+ LinkTable();
+ ~LinkTable();
+
+ const char *class_name() const { return "LinkTable"; }
+
+ Path best_route(IPAddress, bool);
+ String print_routes(bool, bool);
+ String route_to_string(Path);
+ uint32_t get_route_metric(const Path&);
+ void dijkstra(bool);
+
+};
CLICK_ENDDECLS
#endif /* CLICK_LINKTABLE_HH */
More information about the click
mailing list