ipratemon.cc

COPE the first practical network coding scheme which is developped on click

/*
 * ipratemon.{cc,hh} -- measures packet rates clustered by src/dst addr.
 * Thomer M. Gil
 * Benjie Chen, Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2000 Mazu Networks, Inc.
 *
 * 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 "ipratemon.hh"
#include <click/confparse.hh>
#include <click/straccum.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <click/sync.hh>
#include <click/llrpc.h>
CLICK_DECLS

IPRateMonitor::IPRateMonitor()
  : _count_packets(true), _anno_packets(true),
    _thresh(1), _memmax(0), _ratio(1),
    _lock(0), _base(0), _alloced_mem(0), _first(0), 
    _last(0), _prev_deleted(0)
{
}

IPRateMonitor::~IPRateMonitor()
{
}

void
IPRateMonitor::notify_ninputs(int n)
{
  set_ninputs(n == 1 ? 1 : 2);
  set_noutputs(n == 1 ? 1 : 2);
}

int
IPRateMonitor::configure(Vector<String> &conf, ErrorHandler *errh)
{
  String count_what;
  _memmax = 0;
  _anno_packets = true;
  if (cp_va_parse(conf, this, errh,
		  cpWord, "monitor type", &count_what,
		  cpUnsignedReal2, "ratio", 16, &_ratio,
		  cpUnsigned, "threshold", &_thresh,
		  cpOptional, 
		  cpUnsigned, "memmax", &_memmax,
		  cpBool, "annotate", &_anno_packets,
		  cpEnd) < 0)
    return -1;
  if (count_what.upper() == "PACKETS")
    _count_packets = true;
  else if (count_what.upper() == "BYTES")
    _count_packets = false;
  else
    return errh->error("monitor type should be \"PACKETS\" or \"BYTES\"");

  if (_memmax && _memmax < MEMMAX_MIN)
    _memmax = MEMMAX_MIN;
  _memmax *= 1024;      // now bytes

  if (_ratio > 0x10000)
    return errh->error("ratio must be between 0 and 1");

  // Set zoom-threshold as if ratio were 1.
  _thresh = (_thresh * _ratio) >> 16;

  return 0;
}

int
IPRateMonitor::initialize(ErrorHandler *errh)
{
  set_resettime();

  _lock = new Spinlock();
  if (!_lock)
    return errh->error("cannot create spinlock.");

  // Make _base
  _base = new Stats(this);
  if (!_base)
    return errh->error("cannot allocate data structure.");
  _first = _last = _base;
  return 0;
}

void
IPRateMonitor::cleanup(CleanupStage)
{ 
  delete _base;
  delete _lock;
  _base = 0;
  _lock = 0;
}

void
IPRateMonitor::push(int port, Packet *p)
{
  // Only inspect 1 in RATIO packets
  bool ewma = ((unsigned) ((random() >> 5) & 0xffff) <= _ratio);
  _lock->acquire();
  update_rates(p, port == 0, ewma);
  _lock->release();
  output(port).push(p);
}

Packet *
IPRateMonitor::pull(int port)
{
  Packet *p = input(port).pull();
  if (p) {
    bool ewma = ((unsigned) ((random() >> 5) & 0xffff) <= _ratio);
    _lock->acquire();
    update_rates(p, port == 0, ewma);
    _lock->release();
  }
  return p;
}


IPRateMonitor::Counter*
IPRateMonitor::make_counter(Stats *s, unsigned char index, MyEWMA *rate)
{
  Counter *c = NULL;

  // Return NULL if
  // 1. This allocation would violate memory limit
  // 2. Allocation did not succeed
  if ((_memmax && (_alloced_mem + sizeof(Counter) > _memmax)) ||
      !(c = s->counter[index] = new Counter))
    return NULL;
  _alloced_mem += sizeof(Counter);

  if (!rate)
    c->fwd_and_rev_rate.initialize();
  else
    c->fwd_and_rev_rate = *rate;

  c->next_level = 0;
  c->anno_this = 0;

  return c;
}

void
IPRateMonitor::forced_fold()
{
#define FOLD_INCREASE_FACTOR    5.0 // percent

  int perc = (int) (((float) _thresh) / FOLD_INCREASE_FACTOR);
  for (int thresh = _thresh; _alloced_mem > _memmax; thresh += perc)
    fold(thresh);
}


//
// Folds branches if threshhold is lower than thresh.
//
// List is unordered and we stop folding as soon as we have freed enough memory.
// This means that a cleanup always starting at _first and proceeding forwards
// is unfair to those in front of the list. It might cause starvation-like
// phenomena. Therefore, choose randomly to traverse forwards or backwards
// through list. 
//
// If there is no memory limitation, then don't fold more than FOLD_FACTOR.
// Otherwise it takes too long.
//
#define FOLD_FACTOR     0.9
void
IPRateMonitor::fold(int thresh)
{
  char forward = ((char) random()) & 0x01;
  _prev_deleted = _next_deleted = 0;
  Stats *s = (forward ? _first : _last);

  // Don't free to 0 if no memmax defined. Would take too long.
  unsigned memmax;
  if (!(memmax = _memmax))
    memmax = (unsigned) (((float) _alloced_mem) * FOLD_FACTOR);

  do {
start:
    // Don't touch _base. Take next in list.
    if (!s->_parent)
      continue;

    // Shitty code, but avoids an update() and average() call if one of both
    // rates is not below thresh.
    s->_parent->fwd_and_rev_rate.update_time();
    if (s->_parent->fwd_and_rev_rate.average(0) < thresh) {
      if (s->_parent->fwd_and_rev_rate.average(1) < thresh) {
        delete s;
        if ((_alloced_mem < memmax) ||
           !(s = (forward ? _next_deleted : _prev_deleted))) // set by ~Stats().
            break;
        goto start;
      }
    }
  } while((s = (forward ? s->_next : s->_prev)));
}


void
IPRateMonitor::show_agelist(void)
{
  click_chatter("\n----------------");
  click_chatter("_base = %p, _first: %p, _last = %p\n", _base, _first, _last);
  for (Stats *r = _first; r; r = r->_next)
    click_chatter("r = %p, r->_prev = %p, r->_next = %p", r, r->_prev, r->_next);
}


//
// Recursively destroys tables.
//
IPRateMonitor::Stats::Stats(IPRateMonitor *m)
{
  _rm = m;
  _rm->update_alloced_mem(sizeof(*this));
  _parent = 0;
  _next = _prev = 0;

  for (int i = 0; i < MAX_COUNTERS; i++)
    counter[i] = 0;
}



//
// Deletes stats structure cleanly.
//
// Removes all children.
// Removes itself from linked list.
// Tells IPRateMonitor where preceding element in age-list is (set_prev).
//
IPRateMonitor::Stats::~Stats()
{
  for (int i = 0; i < MAX_COUNTERS; i++) {
    if (counter[i]) {
      delete counter[i]->next_level;    // recursive call
      delete counter[i];
      _rm->update_alloced_mem(-sizeof(Counter));
      counter[i] = 0;
      // counter[i]->next_level = 0 is done 1 recursive step deeper.
    }
  }

  // Untangle _prev
  if (this->_prev) {
    this->_prev->_next = this->_next;
    _rm->set_prev(this->_prev);
  } else {
    _rm->set_first(this->_next);
    if(this->_next)
      this->_next->_prev = 0;
    _rm->set_prev(0);
  }

  // Untangle _next
  if (this->_next) {
    this->_next->_prev = this->_prev;
    _rm->set_next(this->_next);
  } else {
    _rm->set_last(this->_prev);
    if(this->_prev)
      this->_prev->_next = 0;
    _rm->set_next(0);
  }

  // Clear pointer to this in parent
  if (this->_parent)
    this->_parent->next_level = 0;

  _rm->update_alloced_mem(-sizeof(*this));
}

//
// Prints out nice data.
//
String
IPRateMonitor::print(Stats *s, String ip)
{
  String ret = "";
  for (int i = 0; i < Stats::MAX_COUNTERS; i++) {
    Counter *c;
    if (!(c = s->counter[i]))
      continue;

    if (c->fwd_and_rev_rate.average(1) > 0 || 
	c->fwd_and_rev_rate.average(0) > 0) {
      String this_ip;
      if (ip)
        this_ip = ip + "." + String(i);
      else
        this_ip = String(i);
      ret += this_ip;

      c->fwd_and_rev_rate.update_time();
      ret += "\t"; 
      ret += cp_unparse_real2(c->fwd_and_rev_rate.average(0) *