ipfilter.cc

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

  switch (_type) {

   case TYPE_HOST:
    if (_data != TYPE_HOST)
      return errh->error("IP address missing in 'host' directive");
    if (_op != OP_EQ)
      return errh->error("can't use relational operators with 'host'");
    _mask.u = (provided_mask ? provided_mask : 0xFFFFFFFFU);
    break;

   case TYPE_NET:
    if (_data != TYPE_NET)
      return errh->error("IP prefix missing in 'net' directive");
    if (_op != OP_EQ)
      return errh->error("can't use relational operators with 'net'");
    _type = TYPE_HOST;
    // _mask already set
    if (provided_mask)
	_mask.u = provided_mask;
    break;

   case TYPE_PROTO:
    if (_data == TYPE_INT || _data == TYPE_PROTO) {
      if (_transp_proto != UNKNOWN && _transp_proto != _u.i)
	return errh->error("transport protocol specified twice");
      _data = TYPE_NONE;
    } else
      _u.i = _transp_proto;
    _transp_proto = UNKNOWN;
    if (_data != TYPE_NONE || _u.i == UNKNOWN)
      return errh->error("IP protocol missing in 'proto' directive");
    if (_u.i >= 256) {
      if (_op != OP_EQ || provided_mask)
	return errh->error("can't use relational operators or masks with '%s'", unparse_transp_proto(_u.i).c_str());
      _mask.u = 0xFF;
    } else if (set_mask(0xFF, 0, provided_mask, errh) < 0)
      return -1;
    if (_op == OP_EQ && _mask.u == 0xFF && !_op_negated) // set _transp_proto if allowed
      _transp_proto = _u.i;
    break;

   case TYPE_PORT:
    if (_data == TYPE_INT)
      _data = TYPE_PORT;
    if (_data != TYPE_PORT)
      return errh->error("port number missing in 'port' directive");
    if (_transp_proto == UNKNOWN)
      _transp_proto = IP_PROTO_TCP_OR_UDP;
    else if (_transp_proto != IP_PROTO_TCP && _transp_proto != IP_PROTO_UDP && _transp_proto != IP_PROTO_TCP_OR_UDP)
      return errh->error("bad protocol %d for 'port' directive", _transp_proto);
    if (set_mask(0xFFFF, 0, provided_mask, errh) < 0)
      return -1;
    break;

   case TYPE_TCPOPT:
    if (_data == TYPE_INT)
      _data = TYPE_TCPOPT;
    if (_data != TYPE_TCPOPT)
      return errh->error("TCP options missing in 'tcp opt' directive");
    if (_transp_proto == UNKNOWN)
      _transp_proto = IP_PROTO_TCP;
    else if (_transp_proto != IP_PROTO_TCP)
      return errh->error("bad protocol %d for 'tcp opt' directive", _transp_proto);
    if (_op != OP_EQ || _op_negated || provided_mask)
      return errh->error("can't use relational operators or masks with 'tcp opt'");
    if (_u.i < 0 || _u.i > 255)
      return errh->error("value %d out of range", _u.i);
    _mask.i = _u.i;
    break;

   case TYPE_IPECT:
     if (_data != TYPE_NONE && _data != TYPE_INT)
	 return errh->error("weird data given to 'ip ect' directive");
     if (_data == TYPE_NONE) {
	 _mask.u = IP_ECNMASK;
	 _u.u = 0;
	 _op_negated = true;
     }
     if (set_mask(0x3, 0, provided_mask, errh) < 0)
	 return -1;
     _type = FIELD_TOS;
     break;

   case TYPE_IPCE:
    if (_data != TYPE_NONE)
      return errh->error("'ip ce' directive takes no data");
    _mask.u = IP_ECNMASK;
    _u.u = IP_ECN_CE;
    _type = FIELD_TOS;
    break;

   case TYPE_IPFRAG:
    if (_data != TYPE_NONE)
      return errh->error("'ip frag' directive takes no data");
    _mask.u = 1; // don't want mask to be 0
    break;

   case TYPE_IPUNFRAG:
    if (_data != TYPE_NONE)
      return errh->error("'ip unfrag' directive takes no data");
    _op_negated = true;
    _mask.u = 1; // don't want mask to be 0
    _type = TYPE_IPFRAG;
    break;

   default:
    if (_type & TYPE_FIELD) {
      if (_data != TYPE_INT && _data != _type)
	return errh->error("value missing in '%s' directive", unparse_type().c_str());
      int nbits = ((_type & FIELD_LENGTH_MASK) >> FIELD_LENGTH_SHIFT) + 1;
      uint32_t mask = (nbits == 32 ? 0xFFFFFFFFU : (1 << nbits) - 1);
      if (set_mask(mask, 0, provided_mask, errh) < 0)
	return -1;
    }
    break;
    
  }

  // fix _srcdst
  if (_type == TYPE_HOST || _type == TYPE_PORT) {
    if (_srcdst == 0)
      _srcdst = SD_OR;
  } else if (old_srcdst)
    errh->warning("'src' or 'dst' is meaningless here");
  
  return 0;
}

static void
add_exprs_for_proto(int32_t proto, int32_t mask, Classifier *c, Vector<int> &tree)
{
  if (mask == 0xFF && proto == IP_PROTO_TCP_OR_UDP) {
    c->start_expr_subtree(tree);
    c->add_expr(tree, 8, htonl(IP_PROTO_TCP << 16), htonl(0x00FF0000));
    c->add_expr(tree, 8, htonl(IP_PROTO_UDP << 16), htonl(0x00FF0000));
    c->finish_expr_subtree(tree, Classifier::C_OR);
  } else if (mask == 0xFF && proto >= 256)
    /* nada */;
  else
    c->add_expr(tree, 8, htonl(proto << 16), htonl(mask << 16));
}

void
IPFilter::Primitive::add_comparison_exprs(Classifier *c, Vector<int> &tree, int offset, int shift, bool swapped) const
{
  assert(_op == IPFilter::OP_EQ || _op == IPFilter::OP_GT);

  uint32_t mask = _mask.u;
  uint32_t u = _u.u & mask;
  if (swapped) {
    mask = ntohl(mask);
    u = ntohl(u);
  }

  if (_op == IPFilter::OP_EQ) {
    c->add_expr(tree, offset, htonl(u << shift), htonl(mask << shift));
    if (_op_negated)
      c->negate_expr_subtree(tree);
    return;
  }

  // To implement a greater-than test for "input&MASK > U":
  // Check the top bit of U&MASK.
  // If the top bit is 0, then:
  //    Find TOPMASK, the top bits of MASK s.t. U&TOPMASK == 0.
  //    If "input&TOPMASK == 0", continue testing with lower bits of
  //    U and MASK; combine with OR.
  //    Otherwise, succeed.
  // If the top bit is 1, then:
  //    Find TOPMASK, the top bits of MASK s.t. (U+1)&TOPMASK == TOPMASK.
  //    If "input&TOPMASK == TOPMASK", continue testing with lower bits of
  //    U and MASK; combine with AND.
  //    Otherwise, fail.
  // Stop testing when U >= MASK.
  
  int high_bit_record = 0;
  int count = 0;

  while (u < mask) {
    int high_bit = (u > (mask >> 1));
    int first_different_bit = 33 - ffs_msb(high_bit ? ~(u+1) & mask : u);
    uint32_t upper_mask;
    if (first_different_bit == 33)
      upper_mask = mask;
    else
      upper_mask = mask & ~((1 << first_different_bit) - 1);
    uint32_t upper_u = (high_bit ? 0xFFFFFFFF & upper_mask : 0);

    c->start_expr_subtree(tree);
    c->add_expr(tree, offset, htonl(upper_u << shift), htonl(upper_mask << shift));
    if (!high_bit)
      c->negate_expr_subtree(tree);
    high_bit_record = (high_bit_record << 1) | high_bit;
    count++;

    mask &= ~upper_mask;
    u &= mask;
  }

  while (count > 0) {
    c->finish_expr_subtree(tree, (high_bit_record & 1 ? Classifier::C_AND : Classifier::C_OR));
    high_bit_record >>= 1;
    count--;
  }

  if (_op_negated)
    c->negate_expr_subtree(tree);
}

void
IPFilter::Primitive::add_exprs(Classifier *c, Vector<int> &tree) const
{
  c->start_expr_subtree(tree);

  // enforce first fragment: fragmentation offset == 0
  // (before transport protocol to enhance later optimizations)
  if (_type == TYPE_PORT || _type == TYPE_TCPOPT || ((_type & TYPE_FIELD) && (_type & FIELD_PROTO_MASK)))
    c->add_expr(tree, 4, 0, htonl(0x00001FFF));
  
  // handle transport protocol uniformly
  if (_transp_proto != UNKNOWN)
    add_exprs_for_proto(_transp_proto, 0xFF, c, tree);

  // handle other types
  switch (_type) {

   case TYPE_HOST:
    c->start_expr_subtree(tree);
    if (_srcdst == SD_SRC || _srcdst == SD_AND || _srcdst == SD_OR)
      add_comparison_exprs(c, tree, 12, 0, true);
    if (_srcdst == SD_DST || _srcdst == SD_AND || _srcdst == SD_OR)
      add_comparison_exprs(c, tree, 16, 0, true);
    c->finish_expr_subtree(tree, (_srcdst == SD_OR ? C_OR : C_AND));
    break;

   case TYPE_PROTO:
    if (_transp_proto < 256)
      add_comparison_exprs(c, tree, 8, 16);
    break;

   case TYPE_IPFRAG:
    c->add_expr(tree, 4, 0, htonl(0x00003FFF));
    if (!_op_negated)
      c->negate_expr_subtree(tree);
    break;

   case TYPE_PORT:
    c->start_expr_subtree(tree);
    if (_srcdst == SD_SRC || _srcdst == SD_AND || _srcdst == SD_OR)
      add_comparison_exprs(c, tree, TRANSP_FAKE_OFFSET, 16);
    if (_srcdst == SD_DST || _srcdst == SD_AND || _srcdst == SD_OR)
      add_comparison_exprs(c, tree, TRANSP_FAKE_OFFSET, 0);
    c->finish_expr_subtree(tree, (_srcdst == SD_OR ? C_OR : C_AND));
    break;

   case TYPE_TCPOPT:
    c->add_expr(tree, TRANSP_FAKE_OFFSET + 12, htonl(_u.u << 16), htonl(_mask.u << 16));
    break;

   default:
    if (_type & TYPE_FIELD) {
      int offset = (_type & FIELD_OFFSET_MASK) >> FIELD_OFFSET_SHIFT;
      int length = ((_type & FIELD_LENGTH_MASK) >> FIELD_LENGTH_SHIFT) + 1;
      int word_offset = (offset >> 3) & ~3, bit_offset = offset & 0x1F;
      int transp_offset = (_type & FIELD_PROTO_MASK ? TRANSP_FAKE_OFFSET : 0);
      add_comparison_exprs(c, tree, transp_offset + word_offset, 32 - (bit_offset + length));
    } else
      assert(0);
    break;

  }

  c->finish_expr_subtree(tree);
}


static void
separate_text(const String &text, Vector<String> &words)
{
  const char* s = text.data();
  int len = text.length();
  int pos = 0;
  while (pos < len) {
    while (pos < len && isspace(s[pos]))
      pos++;
    switch (s[pos]) {

     case '&': case '|':
      if (pos < len - 1 && s[pos+1] == s[pos])
	goto two_char;
      goto one_char;

     case '<': case '>': case '!': case '=':
      if (pos < len - 1 && s[pos+1] == '=')
	goto two_char;
      goto one_char;
      
     case '(': case ')': case '[': case ']': case ',': case ';':
     case '?':
     one_char:
      words.push_back(text.substring(pos, 1));
      pos++;
      break;

     two_char:
      words.push_back(text.substring(pos, 2));
      pos += 2;
      break;

     default: {
	int first = pos;
	while (pos < len && (isalnum(s[pos]) || s[pos] == '-' || s[pos] == '.' || s[pos] == '/' || s[pos] == '@' || s[pos] == '_' || s[pos] == ':'))
	  pos++;
	if (pos == first)
	  pos++;
	words.push_back(text.substring(first, pos - first));
	break;
      }
      
    }
  }
}

void
IPFilter::notify_noutputs(int n)
{
  set_noutputs(n);
}

/*
 * expr ::= orexpr
 *	|   orexpr ? expr : expr
 *	;
 * orexpr ::= orexpr || orexpr
 *	|   orexpr or orexpr
 *	|   term
 *	;
 * term ::= term && term
 *	|   term and term
 *	|   term factor			// juxtaposition = and
 *	|   term
 * factor ::= ! factor
 *	|   true
 *	|   false
 *	|   quals data
 *	|   quals relop data
 *	|   ( expr )
 *	;
 */

int
IPFilter::parse_expr(const Vector<String> &words, int pos,
		     Vector<int> &tree, Primitive &prev_prim,
		     ErrorHandler *errh)
{
  start_expr_subtree(tree);

  while (1) {
    pos = parse_orexpr(words, pos, tree, prev_prim, errh);
    if (pos >= words.size())
      break;
    if (words[pos] != "?")
      break;
    int old_pos = pos + 1;
    pos = parse_expr(words, old_pos, tree, prev_prim, errh);
    if (pos > old_pos && pos < words.size() && words[pos] == ":")
      pos++;
    else {
      errh->error("':' missing in ternary expression");
      break;
    }
  }

  finish_expr_subtree(tree, C_TERNARY);
  return pos;
}

int
IPFilter::parse_orexpr(const Vector<String> &words, int pos,
		     Vector<int> &tree, Primitive &prev_prim,
		     ErrorHandler *errh)
{
  start_expr_subtree(tree);

  while (1) {
    pos = parse_term(words, pos, tree, prev_prim, errh);
    if (pos >= words.size())
      break;
    if (words[pos] == "or" || words[pos] == "||")
      pos++;
    else
      break;
  }

  finish_expr_subtree(tree, C_OR);
  return pos;
}

int
IPFilter::parse_term(const Vector<String> &words, int pos,
		     Vector<int> &tree, Primitive &prev_prim,
		     ErrorHandler *errh)
{
  start_expr_subtree(tree);

  bool blank_ok = false;
  while (1) {
    int next = parse_factor(words, pos, tree, prev_prim, false, errh);
    if (next == pos)
      break;
    blank_ok = true;
    if (next < words.size() && (words[next] == "and" || words[next] == "&&")) {