click-fastclassifier.cc

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

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

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

static void
analyze_classifiers(RouterT *r, const Vector<ElementT *> &classifiers,
		    ErrorHandler *errh)
{
  // set up new router
  RouterT nr;
  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
  HashMap<String, int> classifier_map(-1);
  Vector<Classifier_Program> iprograms;
  for (int i = 0; i < classifiers.size(); i++) {
    ElementT *c = classifiers[i];
    classifier_map.insert(c->name(), i);
    
    // add new classifier and connections to idle
    ElementT *nc =
      nr.get_element(c->name(), c->type(), c->configuration(), c->landmark());
  
    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);

    // add program
    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(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(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(s[pos]); pos++)
	/* nada */;

      // assign value to program if appropriate
      int prog_index = (ok ? classifier_map[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[classifier_tname];
    assert(prog.type >= 0);
    
    prog.safe_length = prog.output_everything = prog.align_offset = -1;
    prog.noutputs = c->noutputs();
    while (program) {
      // find step
      String step = program.substring(program.begin(), find(program, '\n'));
      program = program.substring(step.end() + 1, program.end());
      // check for many things
      if (isdigit(step[0]) || isspace(step[0])) {
	// real step
	Classifier_Insn e;
	int crap, pos;
	int v[4], m[4];
	sscanf(step.c_str(), "%d %d/%2x%2x%2x%2x%%%2x%2x%2x%2x yes->%n",
	       &crap, &e.offset, &v[0], &v[1], &v[2], &v[3],
	       &m[0], &m[1], &m[2], &m[3], &pos);
	for (int i = 0; i < 4; i++) {
	  e.value.c[i] = v[i];
	  e.mask.c[i] = m[i];
	}
	// read yes destination
	step = step.substring(pos);
	if (step[0] == '[') {
	  sscanf(step.c_str(), "[%d] no->%n", &e.yes, &pos);
	  e.yes = -e.yes;
	} else
	  sscanf(step.c_str(), "step %d no->%n", &e.yes, &pos);
	// read no destination
	step = step.substring(pos);
	if (step[0] == '[') {
	  sscanf(step.c_str(), "[%d]", &e.no);
	  e.no = -e.no;
	} else
	  sscanf(step.c_str(), "step %d", &e.no);
	// push expr onto list
	prog.program.push_back(e);
      } else if (sscanf(step.c_str(), "all->[%d]", &prog.output_everything))
	/* nada */;
      else if (sscanf(step.c_str(), "safe length %d", &prog.safe_length))
	/* nada */;
      else if (sscanf(step.c_str(), "alignment offset %d", &prog.align_offset))
	/* nada */;
    }

    // search for an existing fast classifier with the same program
    bool found_program = false;
    for (int i = 0; i < all_programs.size() && !found_program; i++)
      if (prog == all_programs[i]) {
	program_map.push_back(i);
	found_program = true;
      }

    if (!found_program) {
      // set new names
      String class_name = "Fast" + classifier_tname + "@@" + c->name();
      String cxx_name = translate_class_name(class_name);
      prog.eclass = ElementClassT::base_type(class_name);
      
      // add new program
      all_programs.push_back(prog);
      gen_eclass_names.push_back(class_name);
      gen_cxxclass_names.push_back(cxx_name);
      old_configurations.push_back(c->configuration());
      program_map.push_back(all_programs.size() - 1);
    }
  }

  // complain if any programs missing
  for (int i = 0; i < iprograms.size(); i++)
    if (program_map[i] < 0)
      errh->fatal("classifier program missing for '%s :: %s'!", classifiers[i]->name_c_str(), classifiers[i]->type_name().cc());
}

static void
output_classifier_program(int which,
			  StringAccum &header, StringAccum &source,
			  ErrorHandler *)
{
  String cxx_name = gen_cxxclass_names[which];
  String class_name = gen_eclass_names[which];
  const Classifier_Program &prog = all_programs[which];
  FastClassifier_Cid *cid = cids[prog.type];
  if (cid->headers) {
    cid->headers(prog, source);
    cid->headers = 0;		// only call cid->headers once
  }
  
  header << "class " << cxx_name << " : public Element {\n\
  void devirtualize_all() { }\n\
 public:\n  "
	 << cxx_name << "() { set_ninputs(1); set_noutputs(" << prog.noutputs
	 << "); }\n  ~"
	 << cxx_name << "() { }\n\
  const char *class_name() const { return \"" << class_name << "\"; }\n\
  " << cxx_name << " *clone() const { return new " << cxx_name << "; }\n\
  const char *processing() const { return PUSH; }\n";

  if (prog.output_everything >= 0) {
    header << "  void push(int, Packet *);\n};\n";
    source << "void\n" << cxx_name << "::push(int, Packet *p)\n{\n";
    if (prog.output_everything < prog.noutputs)
      source << "  output(" << prog.output_everything << ").push(p);\n";
    else
      source << "  p->kill();\n";
    source << "}\n";
  } else {
    bool need_checked = (prog.safe_length >= cid->guaranteed_packet_length);
    if (need_checked) {
      header << "  void length_checked_push(Packet *);\n";
      source << "void\n" << cxx_name << "::length_checked_push(Packet *p)\n{\n";
      cid->checked_body(prog, source);
      source << "}\n";
    }
    
    header << "  inline void length_unchecked_push(Packet *);\n\
  void push(int, Packet *);\n};\n";
    source << "inline void\n" << cxx_name
	   << "::length_unchecked_push(Packet *p)\n{\n";
    cid->unchecked_body(prog, source);
    source << "}\n";

    source << "void\n" << cxx_name << "::push(int, Packet *p)\n{\n";
    cid->push_body(prog, source);
    source << "}\n";
  }
}


static void
compile_classifiers(RouterT *r, const String &package_name,
		    Vector<ElementT *> &classifiers,
		    bool compile_kernel, bool compile_user, ErrorHandler *errh)
{
    // create C++ files
    StringAccum header, source, source_body;
    header << "#ifndef CLICK_" << package_name << "_HH\n"
	   << "#define CLICK_" << package_name << "_HH\n"
	   << "#include <click/package.hh>\n#include <click/element.hh>\n";

    // analyze Classifiers into programs
    analyze_classifiers(r, classifiers, errh);

    // add requirement
    r->add_requirement(package_name);

    // write Classifier programs
    for (int i = 0; i < all_programs.size(); i++)
	output_classifier_program(i, header, source_body, errh);

    // change element landmarks and types
    for (int i = 0; i < classifiers.size(); i++) {
	ElementT *classifier_e = classifiers[i];
	const Classifier_Program &prog = all_programs[program_map[i]];
	classifier_e->set_type(prog.eclass);
	classifier_e->set_configuration(String());
	change_landmark(classifier_e);
    }
  
    // write final text
    header << "#endif\n";
    source << "/** click-compile: -w */\n";
    {
	StringAccum elem2package, cmd_sa;
	int nclasses = gen_cxxclass_names.size();
	for (int i = 0; i < nclasses; i++)
	    elem2package <<  "-\t\"" << package_name << ".hh\"\t" << gen_cxxclass_names[i] << '-' << gen_eclass_names[i] << '\n';
	cmd_sa << click_buildtool_prog << " elem2package fastclassifier";
	source << shell_command_output_string(cmd_sa.take_string(), elem2package.take_string(), errh);
    }
    source << "CLICK_DECLS\n" << source_body << "CLICK_ENDDECLS\n";

    // compile files if required
    String tmpdir;
  
    if (compile_kernel || compile_user) {
	// create temporary directory
	if (!(tmpdir = click_mktmpdir(errh)))
	    exit(1);
    
	String filename = tmpdir + package_name + ".hh";
	FILE *f = fopen(filename.c_str(), "w");
	if (!f)
	    errh->fatal("%s: %s", filename.c_str(), strerror(errno));
	fwrite(header.data(), 1, header.length(), f);
	fclose(f);

	String cxx_filename = package_name + ".cc";
	f = fopen((tmpdir + cxx_filename).c_str(), "w");
	if (!f)
	    errh->fatal("%s%s: %s", tmpdir.cc(), cxx_filename.cc(), strerror(errno));
	fwrite(source.data(), 1, source.length(), f);
	fclose(f);
    
	// compile kernel module
	if (compile_kernel) {
	    String compile_command = click_compile_prog + " --directory=" + tmpdir + " --driver=kernel --package=" + package_name + ".ko " + cxx_filename;
	    int compile_retval = system(compile_command.cc());
	    if (compile_retval == 127)