click-xform.cc

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

/*
 * click-xform.cc -- pattern-based optimizer for Click configurations
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * 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 "routert.hh"
#include "lexert.hh"
#include <click/error.hh>
#include <click/confparse.hh>
#include <click/variableenv.hh>
#include <click/driver.hh>
#include <click/clp.h>
#include "toolutils.hh"
#include "adjacency.hh"
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

bool match_config(const String &, const String &, HashTable<String, String> &);
// TODO: allow some special pports to be unconnected

class Matcher { public:

  Matcher(RouterT *, AdjacencyMatrix *, RouterT *, AdjacencyMatrix *, int, ErrorHandler *);
  ~Matcher();

  bool check_into(const PortT &, const PortT &);
  bool check_out_of(const PortT &, const PortT &);

  bool check_match();
  bool next_match();

  void replace_config(ElementT *) const;
  void replace(RouterT *, const String &, const LandmarkT &, ErrorHandler *);

 private:

  RouterT *_pat;
  AdjacencyMatrix *_pat_m;
  RouterT *_body;
  AdjacencyMatrix *_body_m;
  int _patid;

  ElementT *_pat_input;
  ElementT *_pat_output;

  Vector<ElementT *> _match;
  Vector<ElementT *> _back_match;
  HashTable<String, String> _defs;

  Vector<PortT> _to_pp_from;
  Vector<PortT> _to_pp_to;
  Vector<PortT> _from_pp_from;
  Vector<PortT> _from_pp_to;

};


Matcher::Matcher(RouterT *pat, AdjacencyMatrix *pat_m,
		 RouterT *body, AdjacencyMatrix *body_m,
		 int patid, ErrorHandler *errh)
  : _pat(pat), _pat_m(pat_m), _body(body), _body_m(body_m), _patid(patid),
    _pat_input(0), _pat_output(0)
{
  // check tunnel situation
  for (RouterT::iterator x = _pat->begin_elements(); x; x++) {
    if (!x->tunnel())
      /* nada */;
    else if (x->tunnel_connected())
      errh->lerror(x->landmark(), "pattern has active connection tunnels");
    else if (x->name() == "input" && !_pat_input)
      _pat_input = x;
    else if (x->name() == "output" && !_pat_output)
      _pat_output = x;
    else
      errh->lerror(x->landmark(), "connection tunnel with funny name '%s'", x->name_c_str());
  }
}

Matcher::~Matcher()
{
}

bool
Matcher::check_into(const PortT &houtside, const PortT &hinside)
{
  const Vector<ConnectionT> &pconn = _pat->connections();
  PortT phinside(_back_match[hinside.eindex()], hinside.port);
  PortT success;
  // now look for matches
  for (int i = 0; i < pconn.size(); i++)
    if (pconn[i].to() == phinside && pconn[i].from_element() == _pat_input
	&& (success.dead() || pconn[i].from() < success)) {
      Vector<PortT> pfrom_phf, from_houtside;
      // check that it's valid: all connections from tunnels are covered
      // in body
      _pat->find_connections_from(pconn[i].from(), pfrom_phf);
      _body->find_connections_from(houtside, from_houtside);
      for (int j = 0; j < pfrom_phf.size(); j++) {
	PortT want(_match[pfrom_phf[j].eindex()], pfrom_phf[j].port);
	if (want.index_in(from_houtside) < 0)
	  goto no_match;
      }
      // success: save it
      success = pconn[i].from();
     no_match: ;
    }
  // if succeeded, save it
  if (success.live()) {
    _to_pp_from.push_back(houtside);
    _to_pp_to.push_back(success);
    return true;
  } else
    return false;
}

bool
Matcher::check_out_of(const PortT &hinside, const PortT &houtside)
{
  const Vector<ConnectionT> &pconn = _pat->connections();
  PortT phinside(_back_match[hinside.eindex()], hinside.port);
  PortT success;
  // now look for matches
  for (int i = 0; i < pconn.size(); i++)
    if (pconn[i].from() == phinside && pconn[i].to_element() == _pat_output
	&& (success.dead() || pconn[i].to() < success)) {
      Vector<PortT> pto_pht, to_houtside;
      // check that it's valid: all connections to tunnels are covered
      // in body
      _pat->find_connections_to(pconn[i].to(), pto_pht);
      _body->find_connections_to(houtside, to_houtside);
      for (int j = 0; j < pto_pht.size(); j++) {
	PortT want(_match[pto_pht[j].eindex()], pto_pht[j].port);
	if (want.index_in(to_houtside) < 0)
	  goto no_match;
      }
      // success: save it
      success = pconn[i].to();
     no_match: ;
    }
  // if succeeded, save it
  if (success.live()) {
    _from_pp_from.push_back(success);
    _from_pp_to.push_back(houtside);
    return true;
  } else
    return false;
}

bool
Matcher::check_match()
{
  _from_pp_from.clear();
  _from_pp_to.clear();
  _to_pp_from.clear();
  _to_pp_to.clear();
  _defs.clear();

  // check configurations
  //fprintf(stderr, "CONF\n");
  for (int i = 0; i < _match.size(); i++)
    if (_match[i]) {
      if (!match_config(_pat->element(i)->configuration(), _match[i]->configuration(), _defs))
	return false;
    }

  int bnf = _body->nelements();
  _back_match.assign(bnf, 0);
  bool all_previous_match = true;
  for (int i = 0; i < _match.size(); i++)
    if (ElementT *m = _match[i]) {
      _back_match[m->eindex()] = _pat->element(i);
      if (m->flags != _patid)	// doesn't come from replacement of same pat
	all_previous_match = false;
    }

  // don't allow match if it consists entirely of elements previously replaced
  // by this pattern
  if (all_previous_match)
    return false;

  // find the pattern ports any cross-pattern jumps correspond to
  //fprintf(stderr, "XPJ\n");
  const Vector<ConnectionT> &conn = _body->connections();
  int nhook = conn.size();

  for (int i = 0; i < nhook; i++) {
    if (conn[i].dead())
      continue;
    const PortT &hf = conn[i].from(), &ht = conn[i].to();
    ElementT *pf = _back_match[hf.eindex()], *pt = _back_match[ht.eindex()];
    if (pf && pt) {
      if (!_pat->has_connection(PortT(pf, hf.port), PortT(pt, ht.port)))
	return false;
    } else if (!pf && pt) {
      if (!check_into(hf, ht))
	return false;
    } else if (pf && !pt) {
      if (!check_out_of(hf, ht))
	return false;
    }
  }

  // check for unconnected tunnels in the pattern
  //fprintf(stderr, "UNC\n");
  const Vector<ConnectionT> &pconn = _pat->connections();
  for (int i = 0; i < pconn.size(); i++) {
    if (pconn[i].from_element() == _pat_input
	&& pconn[i].from().index_in(_to_pp_to) < 0)
      return false;
    if (pconn[i].to_element() == _pat_output
	&& pconn[i].to().index_in(_from_pp_from) < 0)
      return false;
  }

  //fprintf(stderr, "  YES\n");
  return true;
}

bool
Matcher::next_match()
{
  while (_pat_m->next_subgraph_isomorphism(_body_m, _match)) {
    //fprintf(stderr, "NEXT\n");
    if (check_subgraph_isomorphism(_pat, _body, _match)
	&& check_match())
      return true;
  }
  return false;
}



static String
uniqueify_prefix(const String &base_prefix, RouterT *r)
{
  // speed up uniqueification on the same prefix
  static HashTable<String, int> *last_uniqueifier;
  if (!last_uniqueifier)
    last_uniqueifier = new HashTable<String, int>(1);
  int count = last_uniqueifier->get(base_prefix);

  while (1) {
    String prefix = base_prefix + "@" + String(count);
    count++;

    // look for things starting with that name
    int plen = prefix.length();
    for (RouterT::iterator x = r->begin_elements(); x; x++) {
      const String &n = x->name();
      if (n.length() > plen + 1 && n.substring(0, plen) == prefix
	  && n[plen] == '/')
	goto failed;
    }

    last_uniqueifier->set(base_prefix, count);
    return prefix;

   failed: ;
  }
}

void
Matcher::replace_config(ElementT *e) const
{
  Vector<String> confvec;
  cp_argvec(e->configuration(), confvec);

  bool changed = false;
  for (int i = 0; i < confvec.size(); i++) {
    if (confvec[i].length() <= 1 || confvec[i][0] != '$')
      continue;
    if (HashTable<String, String>::const_iterator it = _defs.find(confvec[i])) {
      confvec[i] = it.value();
      changed = true;
    }
  }

  if (changed)
    e->set_configuration(cp_unargvec(confvec));
}

void
Matcher::replace(RouterT *replacement, const String &try_prefix,
		 const LandmarkT &landmark, ErrorHandler *errh)
{
  //fprintf(stderr, "replace...\n");
  String prefix = uniqueify_prefix(try_prefix, _body);

  // free old elements
  Vector<int> changed_elements;
  Vector<String> old_names;
  for (int i = 0; i < _match.size(); i++)
    if (_match[i]) {
      changed_elements.push_back(_match[i]->eindex());
      old_names.push_back(_match[i]->name());
      _body->free_element(_match[i]);
    } else
      old_names.push_back(String());

  // add replacement
  // collect new element indices in 'changed_elements'
  _body->set_new_eindex_collector(&changed_elements);

  // make element named 'prefix'
  ElementT *new_e = _body->get_element(prefix, ElementClassT::tunnel_type(), String(), landmark);

  // expand 'replacement' into '_body'; need crap compound element
  Vector<String> crap_args;