/*
 * 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()
{
}

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) *
			      c->fwd_and_rev_rate.freq(),
			      c->fwd_and_rev_rate.scale);
      ret += "\t"; 
      ret += cp_unparse_real2(c->fwd_and_rev_rate.average(1) *
			      c->fwd_and_rev_rate.freq(),
			      c->fwd_and_rev_rate.scale);
      
      ret += "\n";
      if (c->next_level) 
        ret += print(c->next_level, "\t" + this_ip);
    }
  }
  return ret;
}


String
IPRateMonitor::look_read_handler(Element *e, void *)
{
  IPRateMonitor *me = (IPRateMonitor*) e;

  String ret = String(MyEWMA::now() - me->_resettime) + "\n";

  if (me->_lock->attempt()) {
    ret = ret + me->print(me->_base);
    me->_lock->release();
    return ret;
  } else {
    return ret + "unavailable\n";
  }
}

String
IPRateMonitor::thresh_read_handler(Element *e, void *)
{
  IPRateMonitor *me = (IPRateMonitor *) e;
  return String(me->_thresh);
}

String
IPRateMonitor::mem_read_handler(Element *e, void *)
{
  IPRateMonitor *me = (IPRateMonitor *) e;
  return String(me->_alloced_mem);
}

String
IPRateMonitor::memmax_read_handler(Element *e, void *)
{
  IPRateMonitor *me = (IPRateMonitor *) e;
  return String(me->_memmax);
}

int
IPRateMonitor::reset_write_handler
(const String &, Element *e, void *, ErrorHandler *)
{
  IPRateMonitor* me = (IPRateMonitor *) e;

  me->_lock->acquire();
  for (int i = 0; i < Stats::MAX_COUNTERS; i++) {
    if (me->_base->counter[i]) {
      if (me->_base->counter[i]->next_level)
        delete me->_base->counter[i]->next_level;
      delete me->_base->counter[i];
      me->_base->counter[i] = 0;
    }
  }
  me->set_resettime();
  me->_lock->release();

  return 0;
}


int
IPRateMonitor::memmax_write_handler
(const String &conf, Element *e, void *, ErrorHandler *errh)
{
  Vector<String> args;
  cp_argvec(conf, args);
  IPRateMonitor* me = (IPRateMonitor *) e;

  if (args.size() != 1) {
    errh->error("expecting 1 integer");
    return -1;
  }
  int memmax;
  if (!cp_integer(args[0], &memmax)) {
    errh->error("not an integer");
    return -1;
  }

  if (memmax && memmax < (int)MEMMAX_MIN)
    memmax = MEMMAX_MIN;
  
  me->_lock->acquire();
  me->_memmax = memmax * 1024; // count bytes, not kbytes

  // Fold if necessary
  if (me->_memmax && me->_alloced_mem > me->_memmax)
    me->forced_fold();
  me->_lock->release();

  return 0;
}


int
IPRateMonitor::anno_level_write_handler
(const String &conf, Element *e, void *, ErrorHandler *errh)
{
  Vector<String> args;
  cp_argvec(conf, args);
  IPRateMonitor* me = (IPRateMonitor *) e;
  IPAddress a;
  int level, when;

  if (args.size() != 3) {
    errh->error("expecting 3 arguments");
    return -1;
  }
  
  if (!cp_ip_address(args[0], &a)) {
    errh->error("not an IP address");
    return -1;
  }
  if (!cp_integer(args[1], &level) || !(level >= 0 && level < 4)) {
    errh->error("2nd argument specifies a level, between 0 and 3, to annotate");
    return -1;
  }
  if (!cp_integer(args[2], &when) || when < 1) {
    errh->error("3rd argument specifies when this rule expires, must be > 0");
    return -1;
  }

  when *= MyEWMA::freq();
  when += MyEWMA::now();

  me->_lock->acquire();
  unsigned addr = a.addr();
  me->set_anno_level(addr, static_cast<unsigned>(level), 
                     static_cast<unsigned>(when));
  me->_lock->release();
  return 0;
}


void
IPRateMonitor::add_handlers()
{
  add_read_handler("thresh", thresh_read_handler, 0);
  add_read_handler("look", look_read_handler, 0);
  add_read_handler("mem", mem_read_handler, 0);
  add_read_handler("memmax", memmax_read_handler, 0);

  add_write_handler("anno_level", anno_level_write_handler, 0);
  add_write_handler("reset", reset_write_handler, 0);
  add_write_handler("memmax", memmax_write_handler, 0);
}

int
IPRateMonitor::llrpc(unsigned command, void *data)
{
  if (command == CLICK_LLRPC_IPRATEMON_LEVEL_FWD_AVG
      || command == CLICK_LLRPC_IPRATEMON_LEVEL_REV_AVG) {

    // Data	: int data[256]
    // Incoming : data[0] is the level to drill down; 0 is top level,
    //		  values between 0 and 3 inclusive are valid
    //		  data[1] is the network-byte-order IP address to drill down
    //		  on; it is irrelevant if data[0] == 0
    //		  data[2..255] are ignored
    // Outgoing : If there is no data at that level, returns -EAGAIN.
    //		  If there is data at that level, then puts the forward
    //		  or reverse rate for each of the 256 buckets at that level
    //		  into data[]. If a bucket has no rate, puts -1 into that
    //		  element of data[].
    
    int which = (command == CLICK_LLRPC_IPRATEMON_LEVEL_FWD_AVG ? 0 : 1);
    unsigned *udata = (unsigned *)data;
    unsigned level, ipaddr;
    if (CLICK_LLRPC_GET(level, udata) < 0)
      return -EFAULT;
    if (CLICK_LLRPC_GET(ipaddr, udata + 1) < 0)
      return -EFAULT;
    if (level > 3)
      return -EINVAL;
    
    int averages[256];
    
    _lock->acquire();
    
    // ipaddr is in network order
    Stats *s = _base;
    ipaddr = ntohl(ipaddr);
    for (int bitshift = 24; bitshift > 0 && level > 0; bitshift -= 8, level--) {
      unsigned char b = (ipaddr >> bitshift) & 255;
      if (!s->counter[b] || !s->counter[b]->next_level) {
        _lock->release();
	return -EAGAIN;
      }
      s = s->counter[b]->next_level;
    }

    unsigned freq = MyEWMA::freq();
    unsigned scale = MyEWMA::scale;

    for (int i = 0; i < 256; i++) {
      if (s->counter[i]) {
        s->counter[i]->fwd_and_rev_rate.update_time();
	averages[i] = 
	  (s->counter[i]->fwd_and_rev_rate.average(which) * freq) >> scale;
      }
      else
	averages[i] = -1;
    }
    
    _lock->release();

    return CLICK_LLRPC_PUT_DATA(data, averages, sizeof(averages));
    
  }

  else if (command == CLICK_LLRPC_IPRATEMON_FWD_N_REV_AVG) {
    
    // Data	: int data[9]
    // Incoming : data[0] is the network-byte-order IP address to drill down
    //            on. data[1...8] are ignored.
    // Outgoing : data[0] specifies how many level of rates are returned. for
    //            example, if user request data for 18.26.4.10, and only rates
    //            upto 18.26.4 is available, returns 3. data[1...9] contain
    //            rates, starting with the highest order byte (e.g. 18).

    unsigned *udata = (unsigned *)data;
    unsigned ipaddr;
    if (CLICK_LLRPC_GET(ipaddr, udata) < 0)
      return -EFAULT;
    
    int averages[9];
    int n = 0;
    
    _lock->acquire();

    // ipaddr is in network order
    Stats *s = _base;
    ipaddr = ntohl(ipaddr);
    for (int bitshift = 24; bitshift >= 0; bitshift -= 8) {
      unsigned char b = (ipaddr >> bitshift) & 255;
      if (!s->counter[b]) 
	break;
      
      unsigned freq = s->counter[b]->fwd_and_rev_rate.freq();
      unsigned scale = s->counter[b]->fwd_and_rev_rate.scale;
      s->counter[b]->fwd_and_rev_rate.update_time();
      averages[n*2+1] = 
	(s->counter[b]->fwd_and_rev_rate.average(0) * freq) >> scale;
      averages[n*2+2] = 
	(s->counter[b]->fwd_and_rev_rate.average(1) * freq) >> scale;
      n++;

      if (!s->counter[b]->next_level)
	break;
      s = s->counter[b]->next_level;
    }
    
    _lock->release();

    averages[0] = n;
    return CLICK_LLRPC_PUT_DATA(data, averages, sizeof(averages));
  }

  else if (command == CLICK_LLRPC_IPRATEMON_SET_ANNO_LEVEL) {
    
    // Data	: int data[3]
    // Incoming : data[0] is the network-byte-order IP address. data[1] is the
    //            level at which annotations and expansion should stop.
    //            data[2] is the duration of this rule.
    // Outgoing : nada.

    unsigned *udata = (unsigned *)data;
    unsigned ipaddr, level, when;
    
    if (CLICK_LLRPC_GET(ipaddr, udata) < 0)
      return -EFAULT;
    
    if (CLICK_LLRPC_GET(level, udata+1) < 0 || level > 3)
      return -EFAULT;
    
    if (CLICK_LLRPC_GET(when, udata+2) < 0 || when < 1)
      return -EFAULT;
  
    when *= MyEWMA::freq(); 
    when += MyEWMA::now();

    _lock->acquire();
    set_anno_level(ipaddr, static_cast<unsigned>(level), 
	           static_cast<unsigned>(when));
    _lock->release();
    return 0;
  }
  
  else
    return Element::llrpc(command, data);
}

EXPORT_ELEMENT(IPRateMonitor)
ELEMENT_REQUIRES(userlevel)

// template instances
#include <click/ewma.cc>
CLICK_ENDDECLS