classifier.cc

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

	  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)
{
  assert(start.size() == end.size() && start.size() > 1);
  if (in[end[0] - 1] <= 0) {
    int s = in[end[0] - 1];
    for (int j = 1; j < start.size(); j++)
      if (in[end[j] - 1] != s)
	goto not_end;
    return s;
  }
 not_end:
  Vector<int> intersection;
  intersect_lists(in, start, end, 0, start.size(), intersection);
  return intersection.back();
}

void
Classifier::DominatorOptimizer::shift_branch(int brno)
{
  // shift a branch by examining its dominators

  int s = stateno(brno);
  int32_t &to_state = expr(s).j[br(brno)];
  if (to_state <= 0)
    return;

  if (_domlist_start[s] + 1 == _domlist_start[s+1]) {
    // single domlist; faster algorithm
    int d = _domlist_start[s];
    to_state = dom_shift_branch(brno, to_state, _dom_start[d], _dom_start[d+1], 0);
  } else {
    Vector<int> vals, start, end;
    for (int d = _domlist_start[s]; d < _domlist_start[s+1]; d++) {
      start.push_back(vals.size());
      (void) dom_shift_branch(brno, to_state, _dom_start[d], _dom_start[d+1], &vals);
      end.push_back(vals.size());
    }
    to_state = last_common_state_in_lists(vals, start, end);
  }
}

void
Classifier::DominatorOptimizer::run(int state)
{
  assert(_domlist_start.size() == state + 1);
  calculate_dom(state);
  shift_branch(brno(state, true));
  shift_branch(brno(state, false));
}


// OPTIMIZATION

bool
Classifier::remove_unused_states()
{
  // Remove uninteresting exprs
  int first = 0;
  for (int i = 0; _output_everything < 0 && i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    int next = e.yes();
    if (e.yes() == e.no() || e.mask.u == 0) {
      if (i == first && next <= 0)
	_output_everything = e.yes();
      else {
	for (int j = 0; j < i; j++)
	    for (int k = 0; k < 2; k++)
		if (_exprs[j].j[k] == i)
		    _exprs[j].j[k] = next;
	if (i == 0)
	    first = next;
      }
    }
  }
  if (_output_everything < 0 && first > 0)
    _exprs[0] = _exprs[first];

  // Remove unreachable states
  for (int i = 1; i < _exprs.size(); i++) {
    for (int j = 0; j < i; j++)	// all branches are forward
      if (_exprs[j].yes() == i || _exprs[j].no() == i)
	goto done;
    // if we get here, the state is unused
    for (int j = i+1; j < _exprs.size(); j++)
      _exprs[j-1] = _exprs[j];
    _exprs.pop_back();
    for (int j = 0; j < _exprs.size(); j++)
	for (int k = 0; k < 2; k++)
	    if (_exprs[j].j[k] >= i)
		_exprs[j].j[k]--;
    i--;			// shifted downward, so must reconsider `i'
   done: ;
  }

  // Get rid of bad branches
  Vector<int> failure_states(_exprs.size(), FAILURE);
  bool changed = false;
  for (int i = _exprs.size() - 1; i >= 0; i--) {
    Expr &e = _exprs[i];
    for (int k = 0; k < 2; k++)
	if (e.j[k] > 0 && failure_states[e.j[k]] != FAILURE) {
	    e.j[k] = failure_states[e.j[k]];
	    changed = true;
	}
    if (e.yes() == FAILURE)
      failure_states[i] = e.no();
    else if (e.no() == FAILURE)
      failure_states[i] = e.yes();
  }
  return changed;
}

void
Classifier::combine_compatible_states()
{
  for (int i = 0; i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    if (e.no() > 0 && _exprs[e.no()].compatible(e) && e.flippable())
      e.flip();
    if (e.yes() <= 0)
      continue;
    Expr &ee = _exprs[e.yes()];
    if (e.no() == ee.yes() && ee.flippable())
      ee.flip();
    if (e.no() == ee.no() && ee.compatible(e)) {
      e.yes() = ee.yes();
      if (!e.mask.u)		// but probably ee.mask.u is always != 0...
	e.offset = ee.offset;
      e.value.u = (e.value.u & e.mask.u) | (ee.value.u & ee.mask.u);
      e.mask.u |= ee.mask.u;
      i--;
    }
  }
}

void
Classifier::count_inbranches(Vector<int> &inbranch) const
{
    inbranch.assign(_exprs.size(), -1);
    for (int i = 0; i < _exprs.size(); i++) {
	const Expr &e = _exprs[i];
	for (int k = 0; k < 2; k++)
	    if (e.j[k] > 0)
		inbranch[e.j[k]] = (inbranch[e.j[k]] >= 0 ? 0 : i);
    }
}

void
Classifier::bubble_sort_and_exprs(int sort_stopper)
{
    Vector<int> inbranch;
    count_inbranches(inbranch);

    // do bubblesort
    for (int i = 0; i < _exprs.size(); i++) {
	Expr &e1 = _exprs[i];
	for (int k = 0; k < 2; k++)
	    if (e1.j[k] > 0) {
		int j = e1.j[k];
		Expr &e2 = _exprs[j];
		if (e1.j[!k] == e2.j[!k]
		    && (e1.offset > e2.offset
			|| (e1.offset == e2.offset && e1.mask.u > e2.mask.u))
		    && e1.offset < sort_stopper && inbranch[j] > 0) {
		    Expr temp(e2);
		    e2 = e1;
		    e2.j[k] = temp.j[k];
		    e1 = temp;
		    e1.j[k] = j;
		    // step backwards to continue the sort
		    i = (inbranch[i] > 0 ? inbranch[i] - 1 : i - 1);
		    break;
		}
	    }
    }
}

void
Classifier::optimize_exprs(ErrorHandler *errh, int sort_stopper)
{
  // sort 'and' expressions
  bubble_sort_and_exprs(sort_stopper);

  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }

  // optimize using dominators
  {
    DominatorOptimizer dom(this);
    for (int i = 0; i < _exprs.size(); i++)
      dom.run(i);
    //dom.print();
    combine_compatible_states();
    (void) remove_unused_states();
  }

  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }

  // Check for case where all patterns have conflicts: _exprs will be empty
  // but _output_everything will still be < 0. We require that, when _exprs
  // is empty, _output_everything is >= 0.
  if (_exprs.size() == 0 && _output_everything < 0)
    _output_everything = noutputs();
  else if (_output_everything >= 0)
    _exprs.clear();

  // Calculate _safe_length
  _safe_length = 0;
  for (int i = 0; i < _exprs.size(); i++) {
    unsigned off = _exprs[i].offset + UBYTES;
    for (int j = 3; j >= 0; j--, off--)
      if (_exprs[i].mask.c[j])
	break;
    if (off > _safe_length)
      _safe_length = off;
  }
  _safe_length -= _align_offset;

  // Warn on patterns that can't match anything
  Vector<int> used_patterns(noutputs() + 1, 0);
  if (_output_everything >= 0)
    used_patterns[_output_everything] = 1;
  else
    for (int i = 0; i < _exprs.size(); i++)
	for (int k = 0; k < 2; k++)
	    if (_exprs[i].j[k] <= 0)
		used_patterns[-_exprs[i].j[k]] = 1;
  for (int i = 0; i < noutputs(); i++)
    if (!used_patterns[i])
      errh->warning("pattern %d matches no packets", i);

  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }
}

//
// CONFIGURATION
//

void
Classifier::init_expr_subtree(Vector<int> &tree)
{
  assert(!tree.size());
  tree.push_back(0);
}

void
Classifier::add_expr(Vector<int> &tree, const Expr &e)
{
    if (_exprs.size() < 0x7FFF) {
	_exprs.push_back(e);
	Expr &ee = _exprs.back();
	ee.yes() = SUCCESS;
	ee.no() = FAILURE;
	int level = tree[0];
	tree.push_back(level);
    }
}

void
Classifier::add_expr(Vector<int> &tree, int offset, uint32_t value, uint32_t mask)
{
  Expr e;
  e.offset = offset;
  e.value.u = value & mask;
  e.mask.u = mask;
  add_expr(tree, e);
}

void
Classifier::start_expr_subtree(Vector<int> &tree)
{
  tree[0]++;
}

void
Classifier::redirect_expr_subtree(int first, int last, int success, int failure)
{
  for (int i = first; i < last; i++) {
    Expr &e = _exprs[i];
    if (e.yes() == SUCCESS)
	e.yes() = success;
    else if (e.yes() == FAILURE)
	e.yes() = failure;
    if (e.no() == SUCCESS)
	e.no() = success;
    else if (e.no() == FAILURE)
	e.no() = failure;
  }
}

void
Classifier::finish_expr_subtree(Vector<int> &tree, Combiner combiner,
				int success, int failure)
{
  int level = tree[0];

  // 'subtrees' contains pointers to trees at level 'level'
  Vector<int> subtrees;
  {
    // move backward to parent subtree
    int ptr = _exprs.size();
    while (ptr > 0 && (tree[ptr] < 0 || tree[ptr] >= level))
      ptr--;
    // collect child subtrees
    for (ptr++; ptr <= _exprs.size(); ptr++)
      if (tree[ptr] == level)
	subtrees.push_back(ptr - 1);
  }

  if (subtrees.size()) {

    // combine subtrees

    // first mark all subtrees as next higher level
    tree[subtrees[0] + 1] = level - 1;
    for (int e = subtrees[0] + 2; e <= _exprs.size(); e++)
      tree[e] = -1;

    // loop over expressions
    int t;
    for (t = 0; t < subtrees.size() - 1; t++) {
      int first = subtrees[t];
      int next = subtrees[t+1];

      if (combiner == C_AND)
	redirect_expr_subtree(first, next, next, failure);
      else if (combiner == C_OR)
	redirect_expr_subtree(first, next, success, next);
      else if (combiner == C_TERNARY) {
	if (t < subtrees.size() - 2) {
	  int next2 = subtrees[t+2];
	  redirect_expr_subtree(first, next, next, next2);
	  redirect_expr_subtree(next, next2, success, failure);
	  t++;
	} else			// like C_AND
	  redirect_expr_subtree(first, next, next, failure);
      } else
	redirect_expr_subtree(first, next, success, failure);
    }