click-undead.cc

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

	skip_over_push(r, PortT(x, 0), r->connection(hnext[0]).to());
      x->kill();
      changed = true;
    }

    // save number of outputs so we don't attach new Idles
    element_noutputs.insert(x->name(), hnext.size());
    x->configuration() = String(hnext.size());
  }

  return changed;
}

static void
find_live_elements(/*const*/ RouterT *r, const char *filename,
		   ElementMap &full_elementmap, int driver,
		   bool indifferent,
		   Bitvector &live_elements, ErrorHandler *errh)
{
  if (!indifferent && !full_elementmap.driver_compatible(r, driver)) {
    errh->error("%s: configuration incompatible with %s driver", filename, Driver::name(driver));
    return;
  }

  full_elementmap.set_driver(driver);

  // get processing
  ProcessingT processing(r, &full_elementmap, errh);
  // ... it will report errors as required

  Bitvector sources(r->nelements(), false);
  Bitvector sinks(r->nelements(), false);
  Bitvector dead(r->nelements(), false);

  // find initial sources and sinks
  for (RouterT::iterator x = r->begin_elements(); x; x++) {
    int nin = x->ninputs();
    int nout = x->noutputs();
    int source_flag = x->type()->traits().flag_value('S');
    int ei = x->eindex();

    if (source_flag == 0) {	// neither source nor sink
      dead[ei] = true;
      continue;
    } else if (source_flag == 1) { // source
      sources[ei] = true;
      if (verbose)
	errh->lmessage(x->landmark(), "'%s' is source", x->declaration().cc());
      continue;
    } else if (source_flag == 2) { // sink
      sinks[ei] = true;
      if (verbose)
	errh->lmessage(x->landmark(), "'%s' is sink", x->declaration().cc());
      continue;
    } else if (source_flag == 3) { // source and sink
      sources[ei] = sinks[ei] = true;
      if (verbose)
	errh->lmessage(x->landmark(), "'%s' is source and sink", x->declaration().cc());
      continue;
    } else if (source_flag > 0)
      errh->lwarning(x->landmark(), "'%s' has strange source/sink flag value %d", x->declaration().cc(), source_flag);

    // if no source/sink flags, make an educated guess
    if (nin == 0) {
      for (int p = 0; p < nout; p++)
	if (processing.output_is_push(ei, p)) {
	  sources[ei] = true;
	  if (verbose)
	    errh->lmessage(x->landmark(), "assuming '%s' is source", x->declaration().cc());
	  break;
	}
    }
    if (nout == 0) {
      for (int p = 0; p < nin; p++)
	if (processing.input_is_pull(ei, p)) {
	  sinks[ei] = true;
	  if (verbose)
	    errh->lmessage(x->landmark(), "assuming '%s' is sink", x->declaration().cc());
	  break;
	}
    }
  }

  int nh = r->nconnections();
  const Vector<ConnectionT> &conn = r->connections();
  
  // spread sources
  bool changed = true;
  while (changed) {
    changed = false;
    for (int i = 0; i < nh; i++) {
      int f = conn[i].from_eindex(), t = conn[i].to_eindex();
      if (f >= 0 && !sources[t] && sources[f] && !dead[t])
	sources[t] = changed = true;
    }
  }
  
  // spread sinks
  changed = true;
  while (changed) {
    changed = false;
    for (int i = 0; i < nh; i++) {
      int f = conn[i].from_eindex(), t = conn[i].to_eindex();
      if (f >= 0 && !sinks[f] && sinks[t] && !dead[f])
	sinks[f] = changed = true;
    }
  }

  // live = (sources & sinks) | independently_live
  live_elements = sources & sinks;

  // find independently live elements
  for (RouterT::iterator x = r->begin_elements(); x; x++)
    if (!live_elements[x->eindex()]) {
      int ei = x->eindex();
      int live_flag = x->type()->traits().flag_value('L');
      if (live_flag == 0)	// not live
	continue;
      else if (live_flag == 1) { // live
	live_elements[ei] = true;
	continue;
      } else if (live_flag > 0)
	errh->lwarning(x->landmark(), "'%s' has strange live flag value %d", x->declaration().cc(), live_flag);

      // if no live flag, make an educated guess
      if (x->ninputs() == 0 && x->noutputs() == 0) {
	live_elements[ei] = true;
	if (verbose)
	  errh->lmessage(x->landmark(), "assuming '%s' is live", x->declaration().cc());
      }
    }
}

static void
replace_blank_ports(RouterT *r)
{
  ElementT *idle = 0;
  int idle_next_in = 0, idle_next_out = 0;
  for (RouterT::iterator x = r->begin_elements(); x; x++) {
    Vector<int> connv;

    r->find_connection_vector_to(x, connv);
    connv.resize(element_ninputs[x->name()], -1);
    for (int p = 0; p < connv.size(); p++)
      if (connv[p] == -1) {	// unconnected port
	if (!idle)
	  idle = r->add_anon_element(idlet, "", "<click-undead>");
	r->add_connection(idle, idle_next_out++, x, p);
      }

    r->find_connection_vector_from(x, connv);
    connv.resize(element_noutputs[x->name()], -1);
    for (int p = 0; p < connv.size(); p++)
      if (connv[p] == -1) {	// unconnected port
	if (!idle)
	  idle = r->add_anon_element(idlet, "", "<click-undead>");
	r->add_connection(x, p, idle, idle_next_in++);
      }
  }
}


int
main(int argc, char **argv)
{
  click_static_initialize();
  CLICK_DEFAULT_PROVIDES;
  ErrorHandler *default_errh = ErrorHandler::default_handler();
  ErrorHandler *p_errh = new PrefixErrorHandler(default_errh, "click-undead: ");

  // read command line arguments
  Clp_Parser *clp =
    Clp_NewParser(argc, argv, sizeof(options) / sizeof(options[0]), options);
  Clp_SetOptionChar(clp, '+', Clp_ShortNegated);
  program_name = Clp_ProgramName(clp);

  const char *router_file = 0;
  bool file_is_expr = false;
  const char *output_file = 0;
  bool config_only = false;
  int check_kernel = -1;
  int check_userlevel = -1;
  
  while (1) {
    int opt = Clp_Next(clp);
    switch (opt) {
      
     case HELP_OPT:
      usage();
      exit(0);
      break;
      
     case VERSION_OPT:
      printf("click-undead (Click) %s\n", CLICK_VERSION);
      printf("Copyright (c) 2000 Massachusetts Institute of Technology\n\
Copyright (c) 2000 Mazu Networks, Inc.\n\
This is free software; see the source for copying conditions.\n\
There is NO warranty, not even for merchantability or fitness for a\n\
particular purpose.\n");
      exit(0);
      break;

     case CLICKPATH_OPT:
      set_clickpath(clp->arg);
      break;
      
     case ROUTER_OPT:
     case EXPRESSION_OPT:
     case Clp_NotOption:
      if (router_file) {
	p_errh->error("router configuration specified twice");
	goto bad_option;
      }
      router_file = clp->arg;
      file_is_expr = (opt == EXPRESSION_OPT);
      break;

     case OUTPUT_OPT:
      if (output_file) {
	p_errh->error("output file specified twice");
	goto bad_option;
      }
      output_file = clp->arg;
      break;

     case CONFIG_OPT:
      config_only = !clp->negated;
      break;

     case KERNEL_OPT:
      check_kernel = (clp->negated ? 0 : 1);
      break;
      
     case USERLEVEL_OPT:
      check_userlevel = (clp->negated ? 0 : 1);
      break;

     case VERBOSE_OPT:
      verbose = !clp->negated;
      break;
      
     bad_option:
     case Clp_BadOption:
      short_usage();
      exit(1);
      break;
      
     case Clp_Done:
      goto done;
      
    }
  }
  
 done:
  RouterT *r = read_router(router_file, file_is_expr, default_errh);
  if (r)
    r->flatten(default_errh);
  if (!r || default_errh->nerrors() > 0)
    exit(1);
  if (file_is_expr)
    router_file = "<expr>";
  else if (!router_file || strcmp(router_file, "-") == 0)
    router_file = "<stdin>";

  // open output file
  FILE *outf = stdout;
  if (output_file && strcmp(output_file, "-") != 0) {
    outf = fopen(output_file, "w");
    if (!outf)
      default_errh->fatal("%s: %s", output_file, strerror(errno));
  }

  // find and parse 'elementmap'
  ElementMap *emap = ElementMap::default_map();
  emap->parse_all_files(r, CLICK_SHAREDIR, p_errh);

  // check configuration for driver indifference
  bool indifferent = emap->driver_indifferent(r, Driver::ALLMASK, default_errh);
  if (indifferent) {
    if (check_kernel < 0 && check_userlevel < 0)
      // only bother to check one of them
      check_kernel = 0;
  } else {
    if (check_kernel < 0 && check_userlevel < 0) {
      check_kernel = emap->driver_compatible(r, Driver::LINUXMODULE);
      check_userlevel = emap->driver_compatible(r, Driver::USERLEVEL);
    }
  }

  // save numbers of inputs and outputs for later
  save_element_nports(r);

  // set types
  idlet = ElementClassT::base_type("Idle");
  
  // remove elements who make static routing decisions
  remove_static_switches(r, default_errh);
  remove_static_pull_switches(r, default_errh);
  remove_nulls(r, ElementClassT::base_type("Null"), default_errh);

  // remove dead elements to improve processing checking
  r->remove_dead_elements();
  
  // find live elements in the drivers
  Bitvector kernel_vec, user_vec;
  if (check_kernel > 0)
    find_live_elements(r, router_file, *emap,
		       Driver::LINUXMODULE, indifferent,
		       kernel_vec, default_errh);
  if (check_userlevel > 0)
    find_live_elements(r, router_file, *emap,
		       Driver::USERLEVEL, indifferent,
		       user_vec, default_errh);

  // an element is live if it's live in either driver
  Bitvector live_vec = kernel_vec | user_vec;
  if (!live_vec.size() && r->nelements())
    exit(1);

  // remove Idles
  for (int i = 0; i < r->nelements(); i++)
    if (!live_vec[i]) {
      ElementT *e = r->element(i);
      if (verbose)
	default_errh->lmessage(e->landmark(), "removing '%s'", e->declaration().cc());
      e->kill();
    }
  
  // remove dead connections (not elements yet: keep indexes in 'processing'
  // the same)
  r->kill_bad_connections();
  r->check();
  
  // remove redundant schedulers
  while (1) {
    int nchanges = 0;
    nchanges += remove_redundant_schedulers(r, ElementClassT::base_type("RoundRobinSched"), false, default_errh);
    nchanges += remove_redundant_schedulers(r, ElementClassT::base_type("PrioSched"), false, default_errh);
    nchanges += remove_redundant_schedulers(r, ElementClassT::base_type("StrideSched"), true, default_errh);
    nchanges += remove_redundant_tee_ports(r, ElementClassT::base_type("Tee"), false, default_errh);
    nchanges += remove_redundant_tee_ports(r, ElementClassT::base_type("PullTee"), true, default_errh);
    if (!nchanges) break;
  }

  // hook up blanked-out live ports to a new Idle
  replace_blank_ports(r);
  
  // NOW remove bad elements
  r->remove_dead_elements();
  
  if (config_only) {
    String config = r->configuration_string();
    fwrite(config.data(), 1, config.length(), outf);
  } else
    write_router_file(r, outf, default_errh);

  exit(0);
}