classifier.cc

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

    if (t < subtrees.size()) {
      assert(t == subtrees.size() - 1);
      redirect_expr_subtree(subtrees[t], _exprs.size(), success, failure);
    }
  }

  tree[0]--;
}

void
Classifier::negate_expr_subtree(Vector<int> &tree)
{
  // swap 'SUCCESS' and 'FAILURE' within the last subtree
  int level = tree[0];
  int first = _exprs.size() - 1;
  while (first >= 0 && tree[first+1] != level)
    first--;

  for (int i = first; i < _exprs.size(); i++) {
    Expr &e = _exprs[i];
    if (e.yes() == FAILURE)
	e.yes() = SUCCESS;
    else if (e.yes() == SUCCESS)
	e.yes() = FAILURE;
    if (e.no() == FAILURE)
	e.no() = SUCCESS;
    else if (e.no() == SUCCESS)
	e.no() = FAILURE;
  }
}

static void
update_value_mask(int c, int shift, int &value, int &mask)
{
  int v = 0, m = 0xF;
  if (c == '?')
    v = m = 0;
  else if (c >= '0' && c <= '9')
    v = c - '0';
  else if (c >= 'A' && c <= 'F')
    v = c - 'A' + 10;
  else if (c >= 'a' && c <= 'f')
    v = c - 'a' + 10;
  value |= (v << shift);
  mask |= (m << shift);
}

int
Classifier::configure(Vector<String> &conf, ErrorHandler *errh)
{
    if (conf.size() != noutputs())
	return errh->error("need %d arguments, one per output port", noutputs());

  int before = errh->nerrors();

  // set align offset
  {
    int c, o;
    if (AlignmentInfo::query(this, 0, c, o) && c >= 4)
      // want `data - _align_offset' aligned at 4/(o%4)
      _align_offset = (4 - (o % 4)) % 4;
    else {
#if !HAVE_INDIFFERENT_ALIGNMENT
      errh->error("machine is sensitive to alignment: you must run config through click-align");
#endif
      _align_offset = 0;
    }
  }

  Vector<int> tree;
  init_expr_subtree(tree);
  start_expr_subtree(tree);

  for (int slot = 0; slot < conf.size(); slot++) {
    int i = 0;
    int len = conf[slot].length();
    const char *s = conf[slot].data();

    int slot_branch = _exprs.size();
    Vector<Expr> slot_exprs;

    start_expr_subtree(tree);

    if (s[0] == '-' && len == 1)
      // slot accepting everything
      i = 1;

    while (i < len) {

      while (i < len && isspace((unsigned char) s[i]))
	i++;
      if (i >= len) break;

      start_expr_subtree(tree);

      // negated?
      bool negated = false;
      if (s[i] == '!') {
	negated = true;
	i++;
	while (i < len && isspace((unsigned char) s[i]))
	  i++;
      }

      if (i >= len || !isdigit((unsigned char) s[i]))
	return errh->error("pattern %d: expected a digit", slot);

      // read offset
      int offset = 0;
      while (i < len && isdigit((unsigned char) s[i])) {
	offset *= 10;
	offset += s[i] - '0';
	i++;
      }

      if (i >= len || s[i] != '/')
	return errh->error("pattern %d: expected '/'", slot);
      i++;

      // scan past value
      int value_pos = i;
      while (i < len && (isxdigit((unsigned char) s[i]) || s[i] == '?'))
	i++;
      int value_end = i;

      // scan past mask
      int mask_pos = -1;
      int mask_end = -1;
      if (i < len && s[i] == '%') {
	i++;
	mask_pos = i;
	while (i < len && (isxdigit((unsigned char) s[i]) || s[i] == '?'))
	  i++;
	mask_end = i;
      }

      // check lengths
      if (value_end - value_pos < 2) {
	errh->error("pattern %d: value has less than 2 hex digits", slot);
	value_end = value_pos;
	mask_end = mask_pos;
      }
      if ((value_end - value_pos) % 2 != 0) {
	errh->error("pattern %d: value has odd number of hex digits", slot);
	value_end--;
	mask_end--;
      }
      if (mask_pos >= 0 && (mask_end - mask_pos) != (value_end - value_pos)) {
	bool too_many = (mask_end - mask_pos) > (value_end - value_pos);
	errh->error("pattern %d: mask has too %s hex digits", slot,
		    (too_many ? "many" : "few"));
	if (too_many)
	  mask_end = mask_pos + value_end - value_pos;
	else
	  value_end = value_pos + mask_end - mask_pos;
      }

      // add values to exprs
      bool first = true;
      offset += _align_offset;
      while (value_pos < value_end) {
	int v = 0, m = 0;
	update_value_mask(s[value_pos], 4, v, m);
	update_value_mask(s[value_pos+1], 0, v, m);
	value_pos += 2;
	if (mask_pos >= 0) {
	  int mv = 0, mm = 0;
	  update_value_mask(s[mask_pos], 4, mv, mm);
	  update_value_mask(s[mask_pos+1], 0, mv, mm);
	  mask_pos += 2;
	  m = m & mv & mm;
	}
	if (first || offset % 4 == 0) {
	  add_expr(tree, (offset / 4) * 4, 0, 0);
	  first = false;
	}
	_exprs.back().mask.c[offset % 4] = m;
	_exprs.back().value.c[offset % 4] = v & m;
	offset++;
      }

      // combine with "and"
      finish_expr_subtree(tree, C_AND);

      if (negated)
	negate_expr_subtree(tree);
    }

    // add fake expr if required
    if (_exprs.size() == slot_branch)
      add_expr(tree, 0, 0, 0);

    finish_expr_subtree(tree, C_AND, -slot);
  }

  finish_expr_subtree(tree, C_OR, -noutputs(), -noutputs());

  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }
  optimize_exprs(errh);
  //{ String sxx = program_string(this, 0); click_chatter("%s", sxx.c_str()); }
  return (errh->nerrors() == before ? 0 : -1);
}

String
Classifier::program_string(Element *element, void *)
{
  Classifier *c = (Classifier *)element;
  StringAccum sa;
  for (int i = 0; i < c->_exprs.size(); i++) {
    Expr e = c->_exprs[i];
    e.offset -= c->_align_offset;
    sa << (i < 10 ? " " : "") << i << ' ' << e << '\n';
  }
  if (c->_exprs.size() == 0)
    sa << "all->[" << c->_output_everything << "]\n";
  sa << "safe length " << c->_safe_length << "\n";
  sa << "alignment offset " << c->_align_offset << "\n";
  return sa.take_string();
}

void
Classifier::add_handlers()
{
    add_read_handler("program", Classifier::program_string, 0, Handler::CALM);
}

//
// COMPRESSED PROGRAMS
//

void
Classifier::compress_exprs(Vector<uint32_t> &prog, bool perform_binary_search,
			   unsigned min_binary_search) const
{
  // Compress the program into "prog."

  // The compressed program groups related Exprs together and sorts large
  // sequences of common primitives ("port 80 or port 90 or port 92 or ..."),
  // allowing the use of binary search.

  // The compressed program is a sequence of tests.  Each test consists of
  // five or more 32-bit words, as follows.
  //
  // +--------+--------+--------+--------+--------+-------
  // |nval|off|   no   |   yes  |  mask  |  value | value...
  // +--------+--------+--------+--------+--------+-------
  // nval (16 bits)  - number of values in the test
  // off (16 bits)   - offset of word into the data packet
  //                   (might be > TRANSP_FAKE_OFFSET)
  // no (32 bits)    - jump if test fails
  // yes (32 bits)   - jump if test succeeds
  // mask (32 bits)  - masked with packet data before comparing with values
  // value (32 bits) - comparison data (nval values).  The values are sorted
  //                   in numerical order if 'nval >= MIN_BINARY_SEARCH.'
  //
  // The test succeeds if the 32 bits of packet data starting at 'off,'
  // bitwise anded with 'mask,' equal any one of the 'value's.  If a 'jump'
  // value is <= 0, it is the negative of the relevant IPFilter output port.
  // A positive 'jump' value equals the number of 32-bit words to move the
  // instruction pointer.

  // It often helps to do another bubblesort for things like ports.

  assert(prog.size() == 0);

  Vector<int> wanted(_exprs.size() + 1, 0);
  wanted[0] = 1;
  for (const Expr *ex = _exprs.begin(); ex < _exprs.end(); ex++)
      if (wanted[ex - _exprs.begin()])
	  for (int j = 0; j < 2; j++)
	      if (ex->j[j] > 0)
		  wanted[ex->j[j]]++;

  Vector<int> offsets;
  for (int i = 0; i < _exprs.size(); i++) {
      int off = prog.size();
      offsets.push_back(off);
      if (wanted[i] == 0)
	  continue;
      assert(_exprs[i].offset >= 0);
      prog.push_back(_exprs[i].offset + 0x10000);
      prog.push_back(_exprs[i].no());
      prog.push_back(_exprs[i].yes());
      prog.push_back(_exprs[i].mask.u);
      prog.push_back(_exprs[i].value.u);
      int no;
      while ((no = (int32_t) prog[off+1]) > 0 && wanted[no] == 1
	     && _exprs[no].yes() == _exprs[i].yes()
	     && _exprs[no].offset == _exprs[i].offset
	     && _exprs[no].mask.u == _exprs[i].mask.u) {
	  prog[off] += 0x10000;
	  prog[off+1] = _exprs[no].no();
	  prog.push_back(_exprs[no].value.u);
	  wanted[no]--;
      }
      if (perform_binary_search && (prog[off] >> 16) >= min_binary_search)
	  click_qsort(&prog[off+4], prog[off] >> 16);
  }
  offsets.push_back(prog.size());

  for (int i = 0; i < _exprs.size(); i++)
      if (offsets[i] < prog.size() && offsets[i] < offsets[i+1]) {
	  int off = offsets[i];
	  if ((int32_t) prog[off+1] > 0)
	      prog[off+1] = offsets[prog[off+1]] - off;
	  if ((int32_t) prog[off+2] > 0)
	      prog[off+2] = offsets[prog[off+2]] - off;
      }
}

//
// RUNNING
//

void
Classifier::length_checked_push(Packet *p)
{
  const unsigned char *packet_data = p->data() - _align_offset;
  int packet_length = p->length() + _align_offset; // XXX >= MAXINT?
  Expr *ex = &_exprs[0];	// avoid bounds checking
  int pos = 0;
  uint32_t data;

  do {
    if (ex[pos].offset+UBYTES > packet_length)
      goto check_length;

   length_ok:
    data = *(const uint32_t *)(packet_data + ex[pos].offset);
    data &= ex[pos].mask.u;
    pos = ex[pos].j[data == ex[pos].value.u];
    continue;

   check_length:
    if (ex[pos].offset < packet_length) {
      unsigned available = packet_length - ex[pos].offset;
      if (!(ex[pos].mask.c[3]
	    || (ex[pos].mask.c[2] && available <= 2)
	    || (ex[pos].mask.c[1] && available == 1)))
	goto length_ok;
    }
    pos = ex[pos].no();
  } while (pos > 0);

  checked_output_push(-pos, p);
}

void
Classifier::push(int, Packet *p)
{
  const unsigned char *packet_data = p->data() - _align_offset;
  Expr *ex = &_exprs[0];	// avoid bounds checking
  int pos = 0;

  if (_output_everything >= 0) {
    // must use checked_output_push because the output number might be
    // out of range
    pos = -_output_everything;
    goto found;
  } else if (p->length() < _safe_length) {
    // common case never checks packet length
    length_checked_push(p);
    return;
  }

  do {
      uint32_t data = *((const uint32_t *)(packet_data + ex[pos].offset));
      data &= ex[pos].mask.u;
      pos = ex[pos].j[data == ex[pos].value.u];
  } while (pos > 0);

 found:
  checked_output_push(-pos, p);
}

CLICK_ENDDECLS
ELEMENT_REQUIRES(AlignmentInfo)
EXPORT_ELEMENT(Classifier)
ELEMENT_MT_SAFE(Classifier)