classifier.cc

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

/*
 * classifier.{cc,hh} -- element is a generic classifier
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2000 Mazu Networks, Inc.
 *
 * 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 "classifier.hh"
#include <click/glue.hh>
#include <click/error.hh>
#include <click/confparse.hh>
#include <click/straccum.hh>
#include <click/standard/alignmentinfo.hh>
CLICK_DECLS

//
// CLASSIFIER::EXPR OPERATIONS
//

bool
Classifier::Expr::implies(const Expr &e) const
  /* Returns true iff a packet that matches `*this' must match `e'. */
{
  if (!e.mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == e.mask.u
    && (value.u & both_mask) == e.value.u;
}

bool
Classifier::Expr::not_implies(const Expr &e) const
  /* Returns true iff a packet that DOES NOT match `*this' must match `e'. */
  /* This happens when (1) 'e' matches everything, or (2) 'e' and '*this'
     both match against the same single bit, and they have different values. */
{
  if (!e.mask.u)
    return true;
  else if (e.offset != offset || (mask.u & (mask.u - 1)) != 0
	   || mask.u != e.mask.u || value.u == e.value.u)
    return false;
  else
    return true;
}

bool
Classifier::Expr::implies_not(const Expr &e) const
  /* Returns true iff a packet that matches `*this' CANNOT match `e'. */
{
  if (!e.mask.u || e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == e.mask.u
    && (value.u & both_mask) != (e.value.u & both_mask);
}

bool
Classifier::Expr::not_implies_not(const Expr &e) const
  /* Returns true iff a packet that DOES NOT match `*this' CANNOT match `e'. */
{
  if (!mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return both_mask == mask.u
    && (value.u & both_mask) == (e.value.u & both_mask);
}

bool
Classifier::Expr::compatible(const Expr &e) const
{
  if (!mask.u || !e.mask.u)
    return true;
  else if (e.offset != offset)
    return false;
  uint32_t both_mask = mask.u & e.mask.u;
  return (value.u & both_mask) == (e.value.u & both_mask);
}

bool
Classifier::Expr::flippable() const
{
  if (!mask.u)
    return false;
  else
    return ((mask.u & (mask.u - 1)) == 0);
}

void
Classifier::Expr::flip()
{
  assert(flippable());
  value.u ^= mask.u;
  int tmp = yes;
  yes = no;
  no = tmp;
}

StringAccum &
operator<<(StringAccum &sa, const Classifier::Expr &e)
{
  char buf[20];
  int offset = e.offset;
  sprintf(buf, "%3d/", offset);
  sa << buf;
  for (int j = 0; j < 4; j++)
    sprintf(buf + 2*j, "%02x", e.value.c[j]);
  sprintf(buf + 8, "%%");
  for (int j = 0; j < 4; j++)
    sprintf(buf + 9 + 2*j, "%02x", e.mask.c[j]);
  sa << buf << "  yes->";
  if (e.yes <= 0)
    sa << "[" << -e.yes << "]";
  else
    sa << "step " << e.yes;
  sa << "  no->";
  if (e.no <= 0)
    sa << "[" << -e.no << "]";
  else
    sa << "step " << e.no;
  return sa;
}

String
Classifier::Expr::s() const
{
  StringAccum sa;
  sa << *this;
  return sa.take_string();
}

//
// CLASSIFIER ITSELF
//

Classifier::Classifier()
    : Element(1, 0), _output_everything(-1)
{
}

Classifier::~Classifier()
{
}

//
// COMPILATION
//

// DOMINATOR OPTIMIZER

/* Optimize Classifier decision trees by removing useless branches. If we have
   a path like:

   0: x>=5?  ---Y-->  1: y==2?  ---Y-->  2: x>=6?  ---Y-->  3: ...
       \
        --N-->...

   and every path to #1 leads from #0, then we can move #1's "Y" branch to
   point at state #3, since we know that the test at state #2 will always
   succeed.

   There's an obvious exponential-time algorithm to check this. Namely, given
   a state, enumerate all paths that could lead you to that state; then check
   the test against all tests on those paths. This terminates -- the
   classifier structure is a DAG -- but clearly in exptime.

   We reduce the algorithm to polynomial time by storing a bounded number of
   paths per state. For every state S, we maintain a set of up to
   MAX_DOMLIST==4 path subsets D1...D4, so *every* path to state S is a
   superset of at least one Di. (There is no requirement that S contains Di as
   a contiguous subpath. Rather, Di might leave out edges.) We can then shift
   edges as follows. Given an edge S.x-->T, check whether T is resolved (to
   the same answer) by every one of the path subsets D1...D4 corresponding to
   S. If so, then the edge S.x-->T is redundant; shift it to destination
   corresponding to the answer to T. (In the example above, we shift #1.Y to
   point to #3, since that is the destination of the #2.Y edge.)

   _dom holds all the Di sets for all states.
   _dom_start[k] says where, in _dom, a given Di begins.
   _domlist_start[S] says where, in _dom_start, the list of dominator sets
   for state S begins.
*/


Classifier::DominatorOptimizer::DominatorOptimizer(Classifier *c)
  : _c(c)
{
  _dom_start.push_back(0);
  _domlist_start.push_back(0);
}

inline Classifier::Expr &
Classifier::DominatorOptimizer::expr(int state) const
{
  return _c->_exprs[state];
}

inline int
Classifier::DominatorOptimizer::nexprs() const
{
  return _c->_exprs.size();
}

inline bool
Classifier::DominatorOptimizer::br_implies(int brno, int state) const
{
  assert(state > 0);
  if (br(brno))
    return expr(stateno(brno)).implies(expr(state));
  else
    return expr(stateno(brno)).not_implies(expr(state));
}

inline bool
Classifier::DominatorOptimizer::br_implies_not(int brno, int state) const
{
  assert(state > 0);
  if (br(brno))
    return expr(stateno(brno)).implies_not(expr(state));
  else
    return expr(stateno(brno)).not_implies_not(expr(state));
}

void
Classifier::DominatorOptimizer::find_predecessors(int state, Vector<int> &v) const
{
  for (int i = 0; i < state; i++) {
    Expr &e = expr(i);
    if (e.yes == state)
      v.push_back(brno(i, true));
    if (e.no == state)
      v.push_back(brno(i, false));
  }
}

#if CLICK_USERLEVEL
void
Classifier::DominatorOptimizer::print()
{
  String s = Classifier::program_string(_c, 0);
  fprintf(stderr, "%s\n", s.cc());
  for (int i = 0; i < _domlist_start.size() - 1; i++) {
    if (_domlist_start[i] == _domlist_start[i+1])
      fprintf(stderr, "S-%d   NO DOMINATORS\n", i);
    else {
      fprintf(stderr, "S-%d : ", i);
      for (int j = _domlist_start[i]; j < _domlist_start[i+1]; j++) {
	if (j > _domlist_start[i])
	  fprintf(stderr, "    : ");
	for (int k = _dom_start[j]; k < _dom_start[j+1]; k++)
	  fprintf(stderr, " %d.%c", stateno(_dom[k]), br(_dom[k]) ? 'Y' : 'N');
	fprintf(stderr, "\n");
      }
    }
  }
}
#endif

void
Classifier::DominatorOptimizer::calculate_dom(int state)
{
  assert(_domlist_start.size() == state + 1);
  assert(_dom_start.size() - 1 == _domlist_start.back());
  assert(_dom.size() == _dom_start.back());
  
  // find predecessors
  Vector<int> predecessors;
  find_predecessors(state, predecessors);
  
  // if no predecessors, kill this expr
  if (predecessors.size() == 0) {
    if (state > 0)
      expr(state).yes = expr(state).no = -_c->noutputs();
    else {
      assert(state == 0);
      _dom.push_back(brno(state, false));
      _dom_start.push_back(_dom.size());
    }
    _domlist_start.push_back(_dom_start.size() - 1);
    return;
  }

  // collect dominator lists from predecessors
  Vector<int> pdom, pdom_end;
  for (int i = 0; i < predecessors.size(); i++) {
    int p = predecessors[i], s = stateno(p);
    
    // if both branches point at same place, remove predecessor state from
    // tree
    if (i > 0 && stateno(predecessors[i-1]) == s) {
      assert(i == predecessors.size() - 1 || stateno(predecessors[i+1]) != s);
      assert(pdom_end.back() > pdom.back());
      assert(stateno(_dom[pdom_end.back() - 1]) == s);
      pdom_end.back()--;
      continue;
    }

    // append all dom lists to pdom and pdom_end; modify dom array to end with
    // branch 'p'
    for (int j = _domlist_start[s]; j < _domlist_start[s+1]; j++) {
      pdom.push_back(_dom_start[j]);
      pdom_end.push_back(_dom_start[j+1]);
      assert(stateno(_dom[pdom_end.back() - 1]) == s);
      _dom[pdom_end.back() - 1] = p;
    }
  }

  // We now have pdom and pdom_end arrays pointing at predecessors'
  // dominators.

  // If we have too many arrays, combine some of them.
  int pdom_pos = 0;
  if (pdom.size() > MAX_DOMLIST) {
    intersect_lists(_dom, pdom, pdom_end, 0, pdom.size(), _dom);
    _dom.push_back(brno(state, false));
    _dom_start.push_back(_dom.size());
    pdom_pos = pdom.size();	// skip loop
  }

  // Our dominators equal predecessors' dominators.
  for (int p = pdom_pos; p < pdom.size(); p++) {
    for (int i = pdom[p]; i < pdom_end[p]; i++) {
      int x = _dom[i];
      _dom.push_back(x);
    }
    _dom.push_back(brno(state, false));
    _dom_start.push_back(_dom.size());
  }

  _domlist_start.push_back(_dom_start.size() - 1);
}


void
Classifier::DominatorOptimizer::intersect_lists(const Vector<int> &in, const Vector<int> &start, const Vector<int> &end, int pos1, int pos2, Vector<int> &out)
  /* Define subvectors V1...Vk as in[start[i] ... end[i]-1] for each pos1 <= i
     < pos2. This code places an intersection of V1...Vk in 'out'. */
{
  assert(pos1 <= pos2 && pos2 <= start.size() && pos2 <= end.size());
  if (pos1 == pos2)
    return;
  else if (pos2 - pos1 == 1) {
    for (int i = start[pos1]; i < end[pos1]; i++)
      out.push_back(in[i]);
  } else {
    Vector<int> pos(start);
    
    // Be careful about lists that end with something <= 0.
    int x = -1;			// 'x' describes the intersection path.
    
    while (1) {
      int p = pos1, k = 0;
      // Search for an 'x' that is on all of V1...Vk. We step through V1...Vk
      // in parallel, using the 'pos' array (initialized to 'start'). On
      // reaching the end of any of the arrays, exit.
      while (k < pos2 - pos1) {
	while (pos[p] < end[p] && in[pos[p]] < x)
	  pos[p]++;
	if (pos[p] >= end[p])
	  goto done;
	// Stepped past 'x'; current value is a new candidate
	if (in[pos[p]] > x)
	  x = in[pos[p]], k = 0;
	p++;
	if (p == pos2)
	  p = pos1;
	k++;
      }
      // Went through all of V1...Vk without changing x, so it's on all lists
      // (0 will definitely be the first such); add it to 'out' and step
      // through again
      out.push_back(x);
      x++;
    }
   done: ;
  }
}

int
Classifier::DominatorOptimizer::dom_shift_branch(int brno, int to_state, int dom, int dom_end, Vector<int> *collector)
{
  // shift the branch from `brno' to `to_state' as far down as you can, using
  // information from `brno's dominators
  assert(dom_end > dom && stateno(_dom[dom_end - 1]) == stateno(brno));
  _dom[dom_end - 1] = brno;
  if (collector)
    collector->push_back(to_state);

  while (to_state > 0) {
    for (int j = dom_end - 1; j >= dom; j--)
      if (br_implies(_dom[j], to_state)) {
	to_state = expr(to_state).yes;
	goto found;
      } else if (br_implies_not(_dom[j], to_state)) {
	to_state = expr(to_state).no;
	goto found;
      }
    // not found
    break;
   found:
    if (collector)
      collector->push_back(to_state);
  }

  return to_state;
}

int
Classifier::DominatorOptimizer::last_common_state_in_lists(const Vector<int> &in, const Vector<int> &start, const Vector<int> &end)
{