click-undead.cc

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

/*
 * click-undead.cc -- remove dead code from Click
 * Eddie Kohler
 *
 * Copyright (c) 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 <click/pathvars.h>

#include "routert.hh"
#include "lexert.hh"
#include "processingt.hh"
#include "elementmap.hh"
#include <click/error.hh>
#include <click/confparse.hh>
#include <click/straccum.hh>
#include <click/driver.hh>
#include <click/clp.h>
#include "toolutils.hh"
#include <click/bitvector.hh>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <time.h>
#include <unistd.h>
#include <sys/stat.h>
#include <stdarg.h>

#define HELP_OPT		300
#define VERSION_OPT		301
#define CLICKPATH_OPT		302
#define ROUTER_OPT		303
#define EXPRESSION_OPT		304
#define OUTPUT_OPT		305
#define KERNEL_OPT		306
#define USERLEVEL_OPT		307
#define CONFIG_OPT		308
#define VERBOSE_OPT		310

static Clp_Option options[] = {
  { "clickpath", 'C', CLICKPATH_OPT, Clp_ArgString, 0 },
  { "config", 'c', CONFIG_OPT, 0, Clp_Negate },
  { "expression", 'e', EXPRESSION_OPT, Clp_ArgString, 0 },
  { "file", 'f', ROUTER_OPT, Clp_ArgString, 0 },
  { "help", 0, HELP_OPT, 0, 0 },
  { "kernel", 'k', KERNEL_OPT, 0, Clp_Negate },
  { "output", 'o', OUTPUT_OPT, Clp_ArgString, 0 },
  { "user", 'u', USERLEVEL_OPT, 0, Clp_Negate },
  { "verbose", 'V', VERBOSE_OPT, 0, Clp_Negate },
  { "version", 'v', VERSION_OPT, 0, 0 },
};

static const char *program_name;
static String::Initializer string_initializer;
static bool verbose;

static HashMap<String, int> element_ninputs(-1);
static HashMap<String, int> element_noutputs(-1);

static ElementClassT *idlet;

void
short_usage()
{
  fprintf(stderr, "Usage: %s [OPTION]... [ROUTERFILE]\n\
Try '%s --help' for more information.\n",
	  program_name, program_name);
}

void
usage()
{
  printf("\
'Click-undead' transforms a router configuration by removing dead code. This\n\
includes any elements that are not connected both to a packet source and to a\n\
packet sink. It also removes redundant elements, such as Null and StaticSwitch.\n\
\n\
Usage: %s [OPTION]... [ROUTERFILE]\n\
\n\
Options:\n\
  -f, --file FILE               Read router configuration from FILE.\n\
  -e, --expression EXPR         Use EXPR as router configuration.\n\
  -o, --output FILE             Write output to FILE.\n\
  -k, --kernel                  Configuration is for Linux kernel driver.\n\
  -u, --user                    Configuration is for user-level driver.\n\
  -c, --config                  Write new configuration only.\n\
  -V, --verbose                 Print debugging information.\n\
  -C, --clickpath PATH          Use PATH for CLICKPATH.\n\
      --help                    Print this message and exit.\n\
  -v, --version                 Print version number and exit.\n\
\n\
Report bugs to <[e-mail]>.\n", program_name);
}


static void
save_element_nports(RouterT *r)
{
  for (RouterT::iterator x = r->begin_elements(); x; x++) {
    element_ninputs.insert(x->name(), x->ninputs());
    element_noutputs.insert(x->name(), x->noutputs());
  }
}

static void
remove_static_switches(RouterT *r, ErrorHandler *errh)
{
  ElementClassT *t = ElementClassT::base_type("StaticSwitch");

  for (RouterT::type_iterator x = r->begin_elements(t); x; x++) {
    assert(x->type() == t);
    
    String config = cp_uncomment(x->configuration());
    int val;
    if (!cp_integer(config, &val)) {
      errh->lerror(x->landmark(), "%s: bad configuration 'StaticSwitch(%s)'", x->name_c_str(), config.cc());
      val = -1;
    }

    Vector<int> connv_out;
    r->find_connection_vector_from(x, connv_out);
    for (int i = 0; i < connv_out.size(); i++)
      if (connv_out[i] < 0) {
	errh->lerror(x->landmark(), "odd connections from '%s'", x->declaration().cc());
	break;
      }
    
    ElementT *idle = r->add_anon_element(idlet, "", "<click-undead>");
    int idle_in = 0, idle_out = 0;
    
    PortT jump_hook;
    if (val < 0 || val >= x->noutputs() || connv_out[val] < 0)
      jump_hook = PortT(idle, idle_in++);
    else
      jump_hook = r->connection(connv_out[val]).to();
    
    Vector<PortT> conns_to;
    r->find_connections_to(PortT(x, 0), conns_to);
    for (int j = 0; j < conns_to.size(); j++) {
      int k = r->find_connection(conns_to[j], PortT(x, 0));
      r->change_connection_to(k, jump_hook);
    }

    for (int j = 0; j < connv_out.size(); j++)
      if (j != val)
	r->change_connection_from(connv_out[j], PortT(idle, idle_out++));

    x->kill();
  }
}

static void
remove_static_pull_switches(RouterT *r, ErrorHandler *errh)
{
  ElementClassT *t = ElementClassT::base_type("StaticPullSwitch");

  for (RouterT::type_iterator x = r->begin_elements(t); x; x++) {
    assert(x->type() == t);
    
    String config = cp_uncomment(x->configuration());
    int val;
    if (!cp_integer(config, &val)) {
      errh->lerror(x->landmark(), "%s: bad configuration 'StaticSwitch(%s)'", x->name_c_str(), config.cc());
      val = -1;
    }

    Vector<int> connv_in;
    r->find_connection_vector_to(x, connv_in);
    for (int i = 0; i < connv_in.size(); i++)
      if (connv_in[i] < 0) {
	errh->lerror(x->landmark(), "odd connections to '%s'", x->declaration().cc());
	break;
      }
    
    ElementT *idle = r->add_anon_element(idlet, "", "<click-undead>");
    int idle_in = 0, idle_out = 0;
    
    PortT jump_hook;
    if (val < 0 || val >= x->ninputs() || connv_in[val] < 0)
      jump_hook = PortT(idle, idle_out++);
    else
      jump_hook = r->connection(connv_in[val]).from();
    
    Vector<PortT> conns_from;
    r->find_connections_from(PortT(x, 0), conns_from);
    for (int j = 0; j < conns_from.size(); j++) {
      int k = r->find_connection(PortT(x, 0), conns_from[j]);
      r->change_connection_from(k, jump_hook);
    }

    for (int j = 0; j < connv_in.size(); j++)
      if (j != val)
	r->change_connection_to(connv_in[j], PortT(idle, idle_in++));

    x->kill();
  }
}

static void
skip_over_push(RouterT *r, const PortT &old_to, const PortT &new_to)
{
  Vector<int> connv;
  r->find_connections_to(old_to, connv);
  for (int i = 0; i < connv.size(); i++)
    r->change_connection_to(connv[i], new_to);
}

static void
skip_over_pull(RouterT *r, const PortT &old_from, const PortT &new_from)
{
  Vector<int> connv;
  r->find_connections_from(old_from, connv);
  for (int i = 0; i < connv.size(); i++)
    r->change_connection_from(connv[i], new_from);
}

static void
remove_nulls(RouterT *r, ElementClassT *t, ErrorHandler *errh)
{
  if (!t)
    return;

  for (RouterT::type_iterator x = r->begin_elements(t); x; x++) {
    assert(x->type() == t);
    if (x->ninputs() != 1 || x->noutputs() != 1) {
      errh->lwarning(x->landmark(), "odd connections to '%s'", x->declaration().cc());
      continue;
    }
    
    Vector<int> hprev, hnext;
    r->find_connections_to(PortT(x, 0), hprev);
    r->find_connections_from(PortT(x, 0), hnext);
    if (hprev.size() > 1 && hnext.size() > 1)
      errh->lwarning(x->landmark(), "odd connections to '%s'", x->declaration().cc());
    else if (hprev.size() == 1)
      skip_over_pull(r, PortT(x, 0), r->connection(hprev[0]).from());
    else if (hnext.size() == 1)
      skip_over_push(r, PortT(x, 0), r->connection(hnext[0]).to());

    x->kill();
  }
}

static bool
remove_redundant_schedulers(RouterT *r, ElementClassT *t,
			    bool config_eq_ninputs, ErrorHandler *errh)
{
  if (!t)
    return false;

  bool changed = false;
  for (RouterT::type_iterator x = r->begin_elements(t); x; x++) {
    assert(x->type() == t);
    if (x->noutputs() != 1) {
      errh->lwarning(x->landmark(), "odd connections to '%s'", x->declaration().cc());
      continue;
    }
    
    Vector<int> hprev;
    Vector<String> args;
    r->find_connection_vector_to(x, hprev);
    // check configuration string if we need to
    if (config_eq_ninputs) {
      cp_argvec(x->configuration(), args);
      if (args.size() != hprev.size())
	continue;
    }
    
    for (int p = 0; p < hprev.size(); p++)
      if (hprev[p] == -1 || (hprev[p] >= 0 && r->connection(hprev[p]).from_element()->type() == idlet)) {
	// remove that scheduler port
	// check configuration first
	if (config_eq_ninputs) {
	  for (int pp = p + 1; pp < hprev.size(); pp++)
	    args[pp-1] = args[pp];
	  args.pop_back();
	  x->configuration() = cp_unargvec(args);
	}

	// now do connections
	int bad_connection = hprev[p];
	for (int pp = p + 1; pp < hprev.size(); pp++) {
	  r->change_connection_to(hprev[pp], PortT(x, pp - 1));
	  hprev[pp - 1] = hprev[pp];
	}
	if (bad_connection >= 0)
	  r->kill_connection(bad_connection);
	hprev.pop_back();
	p--;
      }
    
    if (hprev.size() == 1) {
      if (verbose)
	errh->lerror(x->landmark(), "removing redundant scheduler '%s'", x->declaration().cc());
      skip_over_pull(r, PortT(x, 0), r->connection(hprev[0]).from());
      x->kill();
      changed = true;
    }

    // save number of inputs so we don't attach new Idles
    element_ninputs.insert(x->name(), hprev.size());
  }

  return changed;
}

static bool
remove_redundant_tee_ports(RouterT *r, ElementClassT *t, bool is_pull_tee,
			   ErrorHandler *errh)
{
  if (!t)
    return false;

  bool changed = false;
  for (RouterT::type_iterator x = r->begin_elements(t); x; x++) {
    assert(x->type() == t);
    if (x->ninputs() != 1) {
      errh->lwarning(x->landmark(), "odd connections to '%s'", x->declaration().cc());
      continue;
    }
    
    Vector<int> hnext;
    Vector<String> args;
    r->find_connection_vector_from(x, hnext);
    
    for (int p = hnext.size() - 1; p >= (is_pull_tee ? 1 : 0); p--)
      if (hnext[p] == -1 || (hnext[p] >= 0 && r->connection(hnext[p]).from_element()->type() == idlet)) {
	// remove that tee port
	int bad_connection = hnext[p];
	for (int pp = p + 1; pp < hnext.size(); pp++) {
	  r->change_connection_from(hnext[pp], PortT(x, pp - 1));
	  hnext[pp - 1] = hnext[pp];
	}
	if (bad_connection >= 0)
	  r->kill_connection(bad_connection);
	hnext.pop_back();
      }
    
    if (hnext.size() == 1) {
      if (verbose)
	errh->lerror(x->landmark(), "removing redundant tee '%s'", x->declaration().cc());
      if (is_pull_tee) {
	Vector<int> hprev;
	r->find_connection_vector_to(x, hprev);
	skip_over_pull(r, PortT(x, 0), r->connection(hprev[0]).from());
      } else