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<[email protected]> -- 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 */ _______________________________________________ click mailing list [email protected] https://amsterdam.lcs.mit.edu/mailman/listinfo/click
