click-fastclassifier.cc

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

/*
 * 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
 *
 * 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 <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 Clp_Option options[] = {
  { "classes", 0, COMPILE_OPT, 0, Clp_Negate },
  { "clickpath", 'C', CLICKPATH_OPT, Clp_ArgString, 0 },
  { "combine", 0, COMBINE_OPT, 0, Clp_Negate },
  { "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 },
  { "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, 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 String runclick_prog;
static String click_buildtool_prog;
static String click_compile_prog;
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->configuration() = cp_unargvec(new_words);

  // change connections
  router->kill_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]->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::null_string();
}

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 HashMap<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.insert(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;