click-fastclassifier.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

/*
 * click-fastclassifier.cc -- specialize Click classifiers
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2000-2001 Mazu Networks, Inc.
 * Copyright (c) 2001 International Computer Science Institute
 * Copyright (c) 2007 Regents of the University of California
 *
 * 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 <click/error.hh>
#include <click/confparse.hh>
#include <click/straccum.hh>
#include <click/clp.h>
#include <click/driver.hh>
#include "toolutils.hh"
#include "elementmap.hh"
#include "click-fastclassifier.hh"
#include <click/md5.h>
#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 SOURCE_OPT		308
#define CONFIG_OPT		309
#define REVERSE_OPT		310
#define COMBINE_OPT		311
#define COMPILE_OPT		312
#define QUIET_OPT		313
#define VERBOSE_OPT		314

static const Clp_Option options[] = {
  { "classes", 0, COMPILE_OPT, 0, Clp_Negate },
  { "clickpath", 'C', CLICKPATH_OPT, Clp_ValString, 0 },
  { "combine", 0, COMBINE_OPT, 0, Clp_Negate },
  { "config", 'c', CONFIG_OPT, 0, Clp_Negate },
  { "expression", 'e', EXPRESSION_OPT, Clp_ValString, 0 },
  { "file", 'f', ROUTER_OPT, Clp_ValString, 0 },
  { "help", 0, HELP_OPT, 0, 0 },
  { "kernel", 'k', KERNEL_OPT, 0, 0 },
  { "output", 'o', OUTPUT_OPT, Clp_ValString, 0 },
  { "quiet", 'q', QUIET_OPT, 0, Clp_Negate },
  { "reverse", 'r', REVERSE_OPT, 0, Clp_Negate },
  { "source", 's', SOURCE_OPT, 0, Clp_Negate },
  { "user", 'u', USERLEVEL_OPT, 0, 0 },
  { "verbose", 'V', VERBOSE_OPT, 0, Clp_Negate },
  { "version", 'v', VERSION_OPT, 0, 0 }
};

static const char *program_name;
static String runclick_prog;
static String click_buildtool_prog;
static String quiet_arg;
static bool verbose;

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-fastclassifier' transforms a router configuration by replacing generic\n\
Classifier elements with specific generated code. The resulting configuration\n\
has both Click-language files and object files.\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\
      --no-combine              Do not combine adjacent Classifiers.\n\
      --no-classes              Do not generate FastClassifier elements.\n\
  -k, --kernel                  Compile into Linux kernel binary package.\n\
  -u, --user                    Compile into user-level binary package.\n\
  -s, --source                  Write source code only.\n\
  -c, --config                  Write new configuration only.\n\
  -r, --reverse                 Reverse transformation.\n\
  -q, --quiet                   Compile any packages quietly.\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);
}


// Classifier related stuff

static bool
combine_classifiers(RouterT *router, ElementT *from, int from_port, ElementT *to)
{
  ElementClassT *classifier_t = ElementClassT::base_type("Classifier");
  assert(from->type() == classifier_t && to->type() == classifier_t);

  // find where 'to' is heading for
  Vector<int> first_hop, second_hop;
  router->find_connection_vector_from(from, first_hop);
  router->find_connection_vector_from(to, second_hop);

  // check for weird configurations
  for (int i = 0; i < first_hop.size(); i++)
    if (first_hop[i] < 0)
      return false;
  for (int i = 0; i < second_hop.size(); i++)
    if (second_hop[i] < 0)
      return false;
  if (second_hop.size() == 0)
    return false;

  // combine configurations
  Vector<String> from_words, to_words;
  cp_argvec(from->configuration(), from_words);
  cp_argvec(to->configuration(), to_words);
  if (from_words.size() != first_hop.size()
      || to_words.size() != second_hop.size())
    return false;
  Vector<String> new_words;
  for (int i = 0; i < from_port; i++)
    new_words.push_back(from_words[i]);
  for (int i = 0; i < to_words.size(); i++)
    if (to_words[i] == "-")
      new_words.push_back(from_words[from_port]);
    else if (from_words[from_port] == "-")
      new_words.push_back(to_words[i]);
    else
      new_words.push_back(from_words[from_port] + " " + to_words[i]);
  for (int i = from_port + 1; i < from_words.size(); i++)
    new_words.push_back(from_words[i]);
  from->set_configuration(cp_unargvec(new_words));

  // change connections
  router->kill_connection(router->find_connection(first_hop[from_port]));
  for (int i = from_port + 1; i < first_hop.size(); i++)
    router->change_connection_from(first_hop[i], PortT(from, i + to_words.size() - 1));
  const Vector<ConnectionT> &conn = router->connections();
  for (int i = 0; i < second_hop.size(); i++)
    router->add_connection(PortT(from, from_port + i), conn[second_hop[i]].to());

  return true;
}

static bool
try_combine_classifiers(RouterT *router, ElementT *classifier)
{
  ElementClassT *classifier_t = ElementClassT::base_type("Classifier");
  if (classifier->type() != classifier_t)
    // cannot combine IPClassifiers yet
    return false;

  Vector<PortT> branches;
  router->find_connections_to(PortT(classifier, 0), branches);
  for (int i = 0; i < branches.size(); i++)
    if (branches[i].element->type() == classifier_t) {
      // perform a combination
      if (combine_classifiers(router, branches[i].element, branches[i].port, classifier)) {
	try_combine_classifiers(router, classifier);
	return true;
      }
    }

  return false;
}

static void
try_remove_classifiers(RouterT *router, Vector<ElementT *> &classifiers)
{
  for (int i = 0; i < classifiers.size(); i++) {
    Vector<PortT> v;
    router->find_connections_to(PortT(classifiers[i], 0), v);
    if (v.size() == 0) {
      classifiers[i]->simple_kill();
      classifiers[i] = classifiers.back();
      classifiers.pop_back();
      i--;
    }
  }

  router->remove_dead_elements();
  router->compact_connections();
}


/*
 * FastClassifier structures
 */

const String &
Classifier_Program::handler_value(const String &name) const
{
  for (int i = 0; i < handler_names.size(); i++)
    if (handler_names[i] == name)
      return handler_values[i];
  return String::make_empty();
}

bool
operator!=(const Classifier_Insn &s1, const Classifier_Insn &s2)
{
  return (s1.yes != s2.yes
	  || s1.no != s2.no
	  || s1.offset != s2.offset
	  || s1.mask.u != s2.mask.u
	  || s1.value.u != s2.value.u);
}

bool
operator==(const Classifier_Insn &s1, const Classifier_Insn &s2)
{
  return !(s1 != s2);
}

bool
operator==(const Classifier_Program &c1, const Classifier_Program &c2)
{
  if (c1.type != c2.type
      || c1.safe_length != c2.safe_length
      || c1.output_everything != c2.output_everything
      || c1.noutputs != c2.noutputs
      || c1.align_offset != c2.align_offset
      || c1.program.size() != c2.program.size())
    return false;
  for (int i = 0; i < c1.program.size(); i++)
    if (c1.program[i] != c2.program[i])
      return false;
  if (c1.handler_names.size() != c2.handler_names.size())
    return false;
  for (int i = 0; i < c1.handler_names.size(); i++)
    if (c1.handler_values[i] != c2.handler_value(c1.handler_names[i]))
      return false;
  return true;
}

bool
operator!=(const Classifier_Program &c1, const Classifier_Program &c2)
{
  return !(c1 == c2);
}


/*
 * registering CIDs
 */

struct FastClassifier_Cid {
  String name;
  int guaranteed_packet_length;
  void (*headers)(const Classifier_Program &, StringAccum &);
  void (*checked_body)(const Classifier_Program &, StringAccum &);
  void (*unchecked_body)(const Classifier_Program &, StringAccum &);
  void (*push_body)(const Classifier_Program &, StringAccum &);
};

static HashTable<String, int> cid_name_map(-1);
static Vector<FastClassifier_Cid *> cids;
static Vector<String> interesting_handler_names;

int
add_classifier_type(const String &name, int guaranteed_packet_length,
	void (*headers)(const Classifier_Program &, StringAccum &),
	void (*checked_body)(const Classifier_Program &, StringAccum &),
	void (*unchecked_body)(const Classifier_Program &, StringAccum &),
	void (*push_body)(const Classifier_Program &, StringAccum &))
{
  FastClassifier_Cid *cid = new FastClassifier_Cid;
  cid->name = name;
  cid->guaranteed_packet_length = guaranteed_packet_length;
  cid->headers = headers;
  cid->checked_body = checked_body;
  cid->unchecked_body = unchecked_body;
  cid->push_body = push_body;
  cids.push_back(cid);
  cid_name_map.set(cid->name, cids.size() - 1);
  return cids.size() - 1;
}

void
add_interesting_handler(const String &name)
{
  interesting_handler_names.push_back(name);
}


/*
 * translating Classifiers
 */

static String
translate_class_name(const String &s)
{
  StringAccum sa;
  for (int i = 0; i < s.length(); i++)
    if (s[i] == '_')
      sa << "_u";
    else if (s[i] == '@')
      sa << "_a";
    else if (s[i] == '/')
      sa << "_s";
    else
      sa << s[i];
  return sa.take_string();
}

static Vector<String> gen_eclass_names;
static Vector<String> gen_cxxclass_names;
static Vector<String> old_configurations;

static Vector<int> program_map;
static Vector<Classifier_Program> all_programs;

static void
change_landmark(ElementT *e)
{
    String lm = e->landmark();
    int colon = lm.find_right(':');
    if (colon >= 0)
	e->set_landmark(LandmarkT(lm.substring(0, colon) + "<click-fastclassifier>" + lm.substring(colon)));
    else
	e->set_landmark(LandmarkT(lm + "<click-fastclassifier>"));
}

static void
copy_elements(RouterT *oldr, RouterT *newr, ElementClassT *type)
{
  if (type)
    for (RouterT::type_iterator x = oldr->begin_elements(type); x; x++)
	newr->get_element(x->name(), type, x->configuration(), x->landmarkt());
}

static RouterT *
classifiers_program(RouterT *r, const Vector<ElementT *> &classifiers)
{
    RouterT *nr = new RouterT;

    ElementT *idle = nr->add_anon_element(ElementClassT::base_type("Idle"));
    const Vector<String> &old_requirements = r->requirements();
    for (int i = 0; i < old_requirements.size(); i++)
	nr->add_requirement(old_requirements[i]);

    // copy AlignmentInfos and AddressInfos
    copy_elements(r, nr, ElementClassT::base_type("AlignmentInfo"));
    copy_elements(r, nr, ElementClassT::base_type("AddressInfo"));

    // copy all classifiers
    for (int i = 0; i < classifiers.size(); i++) {
	ElementT *c = classifiers[i];

	// add new classifier and connections to idle
	ElementT *nc = nr->get_element(c->name(), c->type(), c->configuration(), c->landmarkt());

	nr->add_connection(idle, i, nc, 0);
	// count number of output ports
	int noutputs = c->noutputs();
	for (int j = 0; j < noutputs; j++)
	    nr->add_connection(nc, j, idle, 0);
    }

    return nr;
}

static void
analyze_classifiers(RouterT *nr, const Vector<ElementT *> &classifiers,
		    ErrorHandler *errh)
{
  // get classifiers
  HashTable<String, int> classifier_map(-1);
  Vector<Classifier_Program> iprograms;
  for (int i = 0; i < classifiers.size(); i++) {
    classifier_map.set(classifiers[i]->name(), i);
    iprograms.push_back(Classifier_Program());
  }

  // read the relevant handlers from user-level 'click'
  String handler_text;
  {
    StringAccum cmd_sa;
    cmd_sa << runclick_prog;
    for (int i = 0; i < interesting_handler_names.size(); i++)
      cmd_sa << " -h '*." << interesting_handler_names[i] << "'";
    cmd_sa << " -q";
    if (verbose)
      errh->message("Running command '%s' on configuration:\n%s", cmd_sa.c_str(), nr->configuration_string().c_str());
    handler_text = shell_command_output_string(cmd_sa.take_string(), nr->configuration_string(), errh);
  }

  // assign handlers to programs; assume handler results contain no par breaks
  {
    const char *s = handler_text.data();
    int len = handler_text.length();
    int pos = 0;
    String ename, hname, hvalue;
    while (pos < len) {
      // read element name
      int pos1 = pos;
      while (pos1 < len && s[pos1] != '.' && !isspace((unsigned char) s[pos1]))
	pos1++;
      ename = handler_text.substring(pos, pos1 - pos);
      bool ok = false;

      // read handler name
      if (pos1 < len && s[pos1] == '.') {
	pos1 = pos = pos1 + 1;
	while (pos1 < len && s[pos1] != ':' && !isspace((unsigned char) s[pos1]))
	  pos1++;
	hname = handler_text.substring(pos, pos1 - pos);

	// skip to EOL; data is good
	if (pos1 < len && s[pos1] == ':') {
	  for (pos1++; pos1 < len && s[pos1]!='\n' && s[pos1]!='\r'; pos1++)
	    /* nada */;
	  if (pos1 < len - 1 && s[pos1] == '\r' && s[pos1+1] == '\n')
	    pos1++;
	  pos1++;
	  ok = true;
	}
      }

      // skip to paragraph break
      int last_line_start = pos1;
      for (pos = pos1; pos1 < len; pos1++)
	if (s[pos1] == '\r' || s[pos1] == '\n') {
	  bool done = (pos1 == last_line_start);
	  if (pos1 < len - 1 && s[pos1] == '\r' && s[pos1+1] == '\n')
	    pos1++;
	  last_line_start = pos1 + 1; // loop will add 1 to pos1
	  if (done)
	    break;
	}
      hvalue = handler_text.substring(pos, pos1 - pos);

      // skip remaining whitespace
      for (pos = pos1; pos < len && isspace((unsigned char) s[pos]); pos++)
	/* nada */;

      // assign value to program if appropriate
      int prog_index = (ok ? classifier_map.get(ename) : -1);
      if (prog_index >= 0) {
	iprograms[prog_index].handler_names.push_back(hname);
	iprograms[prog_index].handler_values.push_back(hvalue);
      }
    }
  }

  // now parse each program
  for (int ci = 0; ci < iprograms.size(); ci++) {
    // check if valid handler
    String program = iprograms[ci].handler_value("program");
    if (!program) {
      program_map.push_back(-1);
      continue;
    }
    ElementT *c = classifiers[ci];

    // yes: valid handler; now parse program
    Classifier_Program &prog = iprograms[ci];
    String classifier_tname = c->type_name();
    prog.type = cid_name_map.get(classifier_tname);
    assert(prog.type >= 0);

    prog.safe_length = prog.output_everything = prog.align_offset = -1;
    prog.noutputs = c->noutputs();
    while (program) {
      // find step