/* * linkstat.{cc,hh} -- track per-link delivery rates. * Douglas S. J. De Couto * * Copyright (c) 1999-2003 Massachusetts Institute of Technology * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the "Software"), * to deal in the Software without restriction, subject to the conditions * listed in the Click LICENSE file. These conditions include: you must * preserve this copyright notice, and you cannot mention the copyright * holders in advertising related to the Software without their permission. * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This * notice is a summary of the Click LICENSE file; the license in that file is * legally binding. */#include <click/config.h>#include <click/confparse.hh>#include <clicknet/ether.h>#include <click/error.hh>#include <click/glue.hh>#include <click/timer.hh>#include <click/straccum.hh>#include <elements/grid/grid.hh>#include <elements/grid/linkstat.hh>#include <elements/grid/timeutils.hh>CLICK_DECLSLinkStat::LinkStat()  : _window(100), _tau(10000), _period(1000),   _probe_size(1000), _seq(0), _send_timer(0),   _use_proto2(false){  add_input();}LinkStat::~LinkStat(){}voidLinkStat::notify_noutputs(int n) {  set_noutputs(n > 0 ? 1 : 0);  }intLinkStat::configure(Vector<String> &conf, ErrorHandler *errh){  int res = cp_va_parse(conf, this, errh,			cpKeywords,			"WINDOW", cpUnsigned, "Broadcast loss rate window", &_window,			"ETH", cpEtherAddress, "Source Ethernet address", &_eth,			"PERIOD", cpUnsigned, "Probe broadcast period (msecs)", &_period,			"TAU", cpUnsigned, "Loss-rate averaging period (msecs)", &_tau,			"SIZE", cpUnsigned, "Probe size (bytes)", &_probe_size,			"USE_SECOND_PROTO", cpBool, "Use alternate protocol number?", &_use_proto2,			cpEnd);  if (res < 0)    return res;    unsigned min_sz = sizeof(click_ether) + link_probe::size;  if (_probe_size < min_sz)    return errh->error("Specified packet size is less than the minimum probe size of %u",		       min_sz);  return res;}voidLinkStat::send_hook() {  WritablePacket *p = Packet::make(_probe_size + 2); // +2 for alignment  if (p == 0) {    click_chatter("LinkStat %s: cannot make packet!", id().cc());    return;  }  ASSERT_ALIGNED(p->data());  p->pull(2);  memset(p->data(), 0, p->length());  p->set_timestamp_anno(Timestamp::now());    // fill in ethernet header   click_ether *eh = (click_ether *) p->data();  memset(eh->ether_dhost, 0xff, 6); // broadcast  eh->ether_type = htons(_use_proto2 ? ETHERTYPE_LINKSTAT2 : ETHERTYPE_LINKSTAT);  memcpy(eh->ether_shost, _eth.data(), 6);  // calculate number of entries  unsigned min_packet_sz = sizeof(click_ether) + link_probe::size;  unsigned max_entries = (_probe_size - min_packet_sz) / link_entry::size;  static bool size_warning = false;  if (!size_warning && max_entries < (unsigned) _bcast_stats.size()) {    size_warning = true;    click_chatter("LinkStat %s: WARNING, probe packet is too small to contain all link stats", id().cc());  }  unsigned num_entries = max_entries < (unsigned) _bcast_stats.size() ? max_entries : _bcast_stats.size();  // build packet  link_probe lp(_seq, _period, num_entries, _tau, _probe_size);  _seq++;  unsigned char *d = p->data() + sizeof(click_ether);  d += lp.write(d);    for (ProbeMap::const_iterator i = _bcast_stats.begin();        i && num_entries > 0;        num_entries--, i++) {    const probe_list_t &val = i.value();    if (val.probes.size() == 0) {      num_entries++;      continue;    }    unsigned n = count_rx(&val);    if (n > 0xFFff)       click_chatter("LinkStat %s: WARNING, overflow in number of probes received from %s", id().cc(), val.eth.s().cc());    link_entry le(val.eth, n & 0xFFff);    d += le.write(d);  }  link_probe::update_cksum(p->data() + sizeof(click_ether));    unsigned max_jitter = _period / 10;  long r2 = random();  unsigned j = (unsigned) ((r2 >> 1) % (max_jitter + 1));  _next_bcast += Timestamp::make_usec(1000 * ((r2 & 1) ? _period - j : _period + j));  _send_timer->schedule_at(_next_bcast);  checked_output_push(0, p);}unsigned intLinkStat::count_rx(const probe_list_t *pl){  if (!pl)    return 0;  struct timeval now;  click_gettimeofday(&now);  struct timeval period = { _tau / 1000, 1000 * (_tau % 1000) };  struct timeval earliest = now - period;  int num = 0;  for (int i = pl->probes.size() - 1; i >= 0; i--) {    if (pl->probes[i].when >= earliest)      num++;    else      break;  }  return num;}unsigned intLinkStat::count_rx(const EtherAddress &eth) {  probe_list_t *pl = _bcast_stats.findp(eth);  if (pl)    return count_rx(pl);  else    return 0;}intLinkStat::initialize(ErrorHandler *errh){  if (noutputs() > 0) {    if (!_eth)       return errh->error("Source Ethernet address must be specified to send probes");    _send_timer = new Timer(static_send_hook, this);    _send_timer->initialize(this);    _next_bcast = Timestamp::now() + Timestamp(1, 0);    _send_timer->schedule_at(_next_bcast);  }  return 0;}Packet *LinkStat::simple_action(Packet *p){  unsigned min_sz = sizeof(click_ether) + link_probe::size;  if (p->length() < min_sz) {    click_chatter("LinkStat %s: packet is too small", id().cc());    p->kill();     return 0;  }  click_ether *eh = (click_ether *) p->data();  if (ntohs(eh->ether_type) != (_use_proto2 ? ETHERTYPE_LINKSTAT2 : ETHERTYPE_LINKSTAT)) {    click_chatter("LinkStat %s: got non-LinkStat packet type", id().cc());    p->kill();    return 0;  }  link_probe lp(p->data() + sizeof(click_ether));  if (link_probe::calc_cksum(p->data() + sizeof(click_ether)) != 0) {    click_chatter("LinkStat %s: bad checksum from %s", id().cc(), EtherAddress(eh->ether_shost).s().cc());    p->kill();    return 0;  }  if (p->length() < lp.psz)     click_chatter("LinkStat %s: packet is smaller (%d) than it claims (%u)",		  id().cc(), p->length(), lp.psz);    add_bcast_stat(EtherAddress(eh->ether_shost), lp);  // look in received packet for info about our outgoing link  struct timeval now;  click_gettimeofday(&now);  unsigned int max_entries = (p->length() - sizeof(*eh) - link_probe::size) / link_entry::size;  unsigned int num_entries = lp.num_links;  if (num_entries > max_entries) {    click_chatter("LinkStat %s: WARNING, probe packet from %s contains fewer link entries (at most %u) than claimed (%u)", 		  id().cc(), EtherAddress(eh->ether_shost).s().cc(), max_entries, num_entries);    num_entries = max_entries;  }  const unsigned char *d = p->data() + sizeof(click_ether) + link_probe::size;  for (unsigned i = 0; i < num_entries; i++, d += link_entry::size) {    link_entry le(d);    if (le.eth == _eth) {      _rev_bcast_stats.insert(EtherAddress(eh->ether_shost), outgoing_link_entry_t(le, now, lp.tau));      break;    }  }  p->kill();  return 0;}boolLinkStat::get_forward_rate(const EtherAddress &eth, unsigned int *r, 			   unsigned int *tau, struct timeval *t){  outgoing_link_entry_t *ol = _rev_bcast_stats.findp(eth);  if (!ol)    return false;  if (_period == 0)    return false;  unsigned num_expected = ol->tau / _period;  unsigned num_received = ol->num_rx;  // will happen if our send period is greater than the the remote  // host's averaging period  if (num_expected == 0)    return false;  unsigned pct = 100 * num_received / num_expected;  if (pct > 100)    pct = 100;  *r = pct;  *tau = ol->tau;  *t = ol->received_at;  return true;}boolLinkStat::get_reverse_rate(const EtherAddress &eth, unsigned int *r, 			   unsigned int *tau){  probe_list_t *pl = _bcast_stats.findp(eth);  if (!pl)    return false;  if (pl->period == 0)    return false;  unsigned num_expected = _tau / pl->period;  unsigned num_received = count_rx(eth);  // will happen if our averaging period is less than the remote  // host's sending rate.  if (num_expected == 0)    return false;  unsigned pct = 100 * num_received / num_expected;  if (pct > 100)    pct = 100;  *r = pct;  *tau = _tau;  return true;}voidLinkStat::add_bcast_stat(const EtherAddress &eth, const link_probe &lp){  struct timeval now;  click_gettimeofday(&now);  probe_t probe(now, lp.seq_no);    unsigned int new_period = lp.period;    probe_list_t *l = _bcast_stats.findp(eth);  if (!l) {    probe_list_t l2(eth, new_period, lp.tau);    _bcast_stats.insert(eth, l2);    l = _bcast_stats.findp(eth);  }  else if (l->period != new_period) {    click_chatter("LinkStat %s: %s has changed its link probe period from %u to %u; clearing probe info\n",		  id().cc(), eth.s().cc(), l->period, new_period);    l->probes.clear();    l->period = new_period;    return;  }    l->probes.push_back(probe);  /* only keep stats for last _window *unique* sequence numbers */  while ((unsigned) l->probes.size() > _window)     l->probes.pop_front();}StringLinkStat::read_window(Element *xf, void *){  LinkStat *f = (LinkStat *) xf;  return String(f->_window) + "\n";}StringLinkStat::read_period(Element *xf, void *){  LinkStat *f = (LinkStat *) xf;  return String(f->_period) + "\n";}StringLinkStat::read_tau(Element *xf, void *){  LinkStat *f = (LinkStat *) xf;  return String(f->_tau) + "\n";}StringLinkStat::read_bcast_stats(Element *xf, void *){  LinkStat *e = (LinkStat *) xf;  typedef HashMap<EtherAddress, bool> EthMap;  EthMap eth_addrs;    for (ProbeMap::const_iterator i = e->_bcast_stats.begin(); i; i++)     eth_addrs.insert(i.key(), true);  for (ReverseProbeMap::const_iterator i = e->_rev_bcast_stats.begin(); i; i++)    eth_addrs.insert(i.key(), true);  struct timeval now;  click_gettimeofday(&now);  StringAccum sa;  for (EthMap::const_iterator i = eth_addrs.begin(); i; i++) {    const EtherAddress &eth = i.key();        probe_list_t *pl = e->_bcast_stats.findp(eth);    outgoing_link_entry_t *ol = e->_rev_bcast_stats.findp(eth);        sa << eth << ' ';        sa << "fwd ";    if (ol) {      struct timeval age = now - ol->received_at;      sa << "age=" << age << " tau=" << ol->tau << " num_rx=" << (unsigned) ol->num_rx 	 << " period=" << e->_period << " pct=" << calc_pct(ol->tau, e->_period, ol->num_rx);    }    else      sa << "age=-1 tau=-1 num_rx=-1 period=-1 pct=-1";    sa << " -- rev ";    if (pl) {      unsigned num_rx = e->count_rx(pl);      sa << "tau=" << e->_tau << " num_rx=" << num_rx << " period=" << pl->period 	 << " pct=" << calc_pct(e->_tau, pl->period, num_rx);    }    else       sa << "tau=-1 num_rx=-1 period=-1 pct=-1";    sa << '\n';  }  return sa.take_string();}unsigned intLinkStat::calc_pct(unsigned tau, unsigned period, unsigned num_rx){  if (period == 0)    return 0;  unsigned num_expected = tau / period;  if (num_expected == 0)    return 0;  return 100 * num_rx / num_expected;}intLinkStat::write_window(const String &arg, Element *el, 		       void *, ErrorHandler *errh){  LinkStat *e = (LinkStat *) el;  if (!cp_unsigned(arg, &e->_window))    return errh->error("window must be >= 0");  return 0;}intLinkStat::write_period(const String &arg, Element *el, 		       void *, ErrorHandler *errh){  LinkStat *e = (LinkStat *) el;  if (!cp_unsigned(arg, &e->_period))    return errh->error("period must be >= 0");  return 0;}intLinkStat::write_tau(const String &arg, Element *el, 		       void *, ErrorHandler *errh){  LinkStat *e = (LinkStat *) el;  if (!cp_unsigned(arg, &e->_tau))    return errh->error("tau must be >= 0");  return 0;}voidLinkStat::add_handlers(){  add_read_handler("bcast_stats", read_bcast_stats, 0);  add_read_handler("window", read_window, 0);  add_read_handler("tau", read_tau, 0);  add_read_handler("period", read_period, 0);  add_write_handler("window", write_window, 0);  add_write_handler("tau", write_tau, 0);  add_write_handler("period", write_period, 0);}LinkStat::link_probe::link_probe(const unsigned char *d)  : seq_no(uint_at(d + 0)), period(uint_at(d + 4)), num_links(uint_at(d + 8)),   tau(uint_at(d + 12)), cksum(ushort_at(d + 16)), psz(ushort_at(d + 18)){}intLinkStat::link_probe::write(unsigned char *d) const{  write_uint_at(d + 0, seq_no);  write_uint_at(d + 4, period);  write_uint_at(d + 8, num_links);  write_uint_at(d + 12, tau);  write_ushort_at(d + 16, 0); // cksum will be filled in later -- we don't know what the link_entry data is yet  write_ushort_at(d + 18, psz); // cksum will be filled in later -- we don't know what the link_entry data is yet  return size;}voidLinkStat::link_probe::update_cksum(unsigned char *d) {  unsigned short cksum = calc_cksum(d);  unsigned char *c = (unsigned char *) &cksum;  d[cksum_offset] = c[0];  d[cksum_offset + 1] = c[1];}unsigned shortLinkStat::link_probe::calc_cksum(const unsigned char *d) {  link_probe lp(d);  int nbytes = link_probe::size + lp.num_links * link_entry::size;  return click_in_cksum(d, nbytes);  }LinkStat::link_entry::link_entry(const unsigned char *d)  : eth(d), num_rx(ushort_at(d + 6)){}intLinkStat::link_entry::write(unsigned char *d) const{  memcpy(d, eth.data(), 6);  write_ushort_at(d + 6, num_rx);  return size;}EXPORT_ELEMENT(LinkStat)#include <click/bighashmap.cc>#include <click/dequeue.cc>template class DEQueue<LinkStat::probe_t>;template class HashMap<EtherAddress, LinkStat::probe_list_t>;CLICK_ENDDECLS