ipfilter.cc

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

		       Vector<int> &tree, Primitive &prev_prim,
		       bool negated, ErrorHandler *errh)
{
  // return immediately on last word, ")", "||", "or", "?", ":"
  if (pos >= words.size() || words[pos] == ")" || words[pos] == "||" || words[pos] == "or" || words[pos] == "?" || words[pos] == ":")
    return pos;

  // easy cases

  // 'true' and 'false'
  if (words[pos] == "true") {
    add_expr(tree, 0, 0, 0);
    if (negated)
      negate_expr_subtree(tree);
    return pos + 1;
  }
  if (words[pos] == "false") {
    add_expr(tree, 0, 0, 0);
    if (!negated)
      negate_expr_subtree(tree);
    return pos + 1;
  }
  // ! factor
  if (words[pos] == "not" || words[pos] == "!") {
    int next = parse_factor(words, pos + 1, tree, prev_prim, !negated, errh);
    if (next == pos + 1)
      errh->error("missing factor after '%s'", words[pos].c_str());
    return next;
  }
  // ( expr )
  if (words[pos] == "(") {
    int next = parse_expr(words, pos + 1, tree, prev_prim, errh);
    if (next == pos + 1)
      errh->error("missing expression after '('");
    if (next >= 0) {
      if (next >= words.size() || words[next] != ")")
	errh->error("missing ')'");
      else
	next++;
      if (negated)
	negate_expr_subtree(tree);
    }
    return next;
  }

  // hard case

  // expect quals [relop] data
  int first_pos = pos;
  Primitive prim;

  // collect qualifiers
  for (; pos < words.size(); pos++) {
    String wd = words[pos];
    uint32_t wdata;
    int wt = lookup(wd, 0, UNKNOWN, wdata, 0);

    if (wt >= 0 && wt == TYPE_TYPE) {
      prim.set_type(wdata, errh);
      if ((wdata & TYPE_FIELD) && (wdata & FIELD_PROTO_MASK))
	prim.set_transp_proto((wdata & FIELD_PROTO_MASK) >> FIELD_PROTO_SHIFT, errh);

    } else if (wt >= 0 && wt == TYPE_PROTO)
      prim.set_transp_proto(wdata, errh);

    else if (wt != -1)
      break;

    else if (wd == "src") {
      if (pos < words.size() - 2 && (words[pos+2] == "dst" || words[pos+2] == "dest")) {
	if (words[pos+1] == "and" || words[pos+1] == "&&") {
	  prim.set_srcdst(SD_AND, errh);
	  pos += 2;
	} else if (words[pos+1] == "or" || words[pos+1] == "||") {
	  prim.set_srcdst(SD_OR, errh);
	  pos += 2;
	} else
	  prim.set_srcdst(SD_SRC, errh);
      } else
	prim.set_srcdst(SD_SRC, errh);
    } else if (wd == "dst" || wd == "dest")
      prim.set_srcdst(SD_DST, errh);

    else if (wd == "ip")
      /* nada */;

    else if (wd == "not" || wd == "!")
      negated = !negated;

    else
      break;
  }

  // prev_prim is not relevant if there were any qualifiers
  if (pos != first_pos)
    prev_prim.clear();

  // optional [] syntax
  String wd = (pos >= words.size() - 1 ? String() : words[pos]);
  if (wd == "[" && pos > first_pos && prim._type == TYPE_NONE) {
    pos = parse_brackets(prim, words, pos, errh);
    wd = (pos >= words.size() - 1 ? String() : words[pos]);
  }

  // optional bitmask
  uint32_t provided_mask = 0;
  if (wd == "&" && pos < words.size() - 1
      && cp_integer(words[pos + 1], &provided_mask)) {
      pos += 2;
      wd = (pos >= words.size() - 1 ? String() : words[pos]);
      if (provided_mask == 0)
	  errh->error("bitmask of 0 ignored");
  }

  // optional relational operation
  pos++;
  if (wd == "=" || wd == "==")
    /* nada */;
  else if (wd == "!=")
    prim._op_negated = true;
  else if (wd == ">")
    prim._op = OP_GT;
  else if (wd == "<")
    prim._op = OP_LT;
  else if (wd == ">=") {
    prim._op = OP_LT;
    prim._op_negated = true;
  } else if (wd == "<=") {
    prim._op = OP_GT;
    prim._op_negated = true;
  } else
    pos--;

  // now collect the actual data
  if (pos < words.size()) {
    wd = words[pos];
    uint32_t wdata;
    int wt = lookup(wd, prim._type, prim._transp_proto, wdata, errh);
    pos++;

    if (wt == -2)		// ambiguous or incorrect word type
      /* absorb word, but do nothing */
      prim._type = -2;

    else if (wt != -1 && wt != TYPE_TYPE) {
      prim._data = wt;
      prim._u.u = wdata;

    } else if (cp_integer(wd, &prim._u.i))
      prim._data = TYPE_INT;

    else if (cp_ip_address(wd, prim._u.c, this)) {
      if (pos < words.size() - 1 && words[pos] == "mask"
	  && cp_ip_address(words[pos+1], prim._mask.c, this)) {
	pos += 2;
	prim._data = TYPE_NET;
      } else if (prim._type == TYPE_NET && cp_ip_prefix(wd, prim._u.c, prim._mask.c, this))
	prim._data = TYPE_NET;
      else
	prim._data = TYPE_HOST;

    } else if (cp_ip_prefix(wd, prim._u.c, prim._mask.c, this))
      prim._data = TYPE_NET;

    else {
      if (prim._op != OP_EQ || prim._op_negated)
	errh->error("dangling operator near '%s'", wd.c_str());
      pos--;
    }
  }

  if (pos == first_pos) {
    errh->error("empty term near '%s'", wd.c_str());
    return pos;
  }

  // add if it is valid
  if (prim.check(prev_prim, provided_mask, errh) >= 0) {
    prim.add_exprs(this, tree);
    if (negated)
      negate_expr_subtree(tree);
    prev_prim = prim;
  }

  return pos;
}

int
IPFilter::configure(Vector<String> &conf, ErrorHandler *errh)
{
  int before_nerrors = errh->nerrors();
  _output_everything = -1;

  // requires packet headers be aligned
  _align_offset = 0;

  Vector<int> tree;
  init_expr_subtree(tree);

  // [QUALS] [host|net|port|proto] [data]
  // QUALS ::= src | dst | src and dst | src or dst | \empty
  //        |  ip | icmp | tcp | udp
  for (int argno = 0; argno < conf.size(); argno++) {
    Vector<String> words;
    separate_text(cp_unquote(conf[argno]), words);

    if (words.size() == 0) {
      errh->error("empty pattern %d", argno);
      continue;
    }

    PrefixErrorHandler cerrh(errh, "pattern " + String(argno) + ": ");

    // get slot
    int slot = noutputs();
    {
      String slotwd = words[0];
      if (slotwd == "allow") {
	slot = 0;
	if (noutputs() == 0)
	  cerrh.error("'allow' is meaningless, element has zero outputs");
      } else if (slotwd == "deny") {
	slot = noutputs();
	if (noutputs() > 1)
	  cerrh.warning("meaning of 'deny' has changed (now it means 'drop')");
      } else if (slotwd == "drop")
	slot = noutputs();
      else if (cp_integer(slotwd, &slot)) {
	if (slot < 0 || slot >= noutputs()) {
	  cerrh.error("slot '%d' out of range", slot);
	  slot = noutputs();
	}
      } else
	cerrh.error("unknown slot ID '%s'", slotwd.c_str());
    }

    start_expr_subtree(tree);

    // check for "-"
    if (words.size() == 1 || (words.size() == 2 && words[1] == "-")
	|| (words.size() == 2 && words[1] == "any")
	|| (words.size() == 2 && words[1] == "all"))
      add_expr(tree, 0, 0, 0);

    else {
      // start with a blank primitive
      Primitive prev_prim;

      int pos = parse_expr(words, 1, tree, prev_prim, &cerrh);
      if (pos < words.size())
	cerrh.error("garbage after expression at '%s'", words[pos].c_str());
    }

    finish_expr_subtree(tree, C_AND, -slot);
  }

  if (tree.size())
    finish_expr_subtree(tree, C_OR, -noutputs(), -noutputs());

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

  // Compress the program into _prog.
  // It helps to do another bubblesort for things like ports.
  bubble_sort_and_exprs();
  compress_exprs(_prog, PERFORM_BINARY_SEARCH, MIN_BINARY_SEARCH);

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

#if CLICK_USERLEVEL
String
IPFilter::compressed_program_string(Element *e, void *)
{
    IPFilter *c = static_cast<IPFilter *>(e);
    const Vector<uint32_t> &prog = c->_prog;

    StringAccum sa;
    for (int i = 0; i < prog.size(); ) {
	sa.snprintf(80, "%3d %3d/%08x%%%08x  yes->", i, (uint16_t) prog[i], htonl(prog[i+4]), htonl(prog[i+3]));
	if ((int32_t) prog[i+2] > 0)
	    sa << "step " << (prog[i+2] + i);
	else
	    sa << "[" << -((int32_t) prog[i+2]) << "]";
	if ((int32_t) prog[i+1] > 0)
	    sa << "  no->step " << (prog[i+1] + i);
	else
	    sa << "  no->[" << -((int32_t) prog[i+1]) << "]";
	sa << "\n";
	for (unsigned x = 1; x < (prog[i] >> 16); ++x)
	    sa.snprintf(80, "        %08x\n", htonl(prog[i+4+x]));
	i += (prog[i] >> 16) + 4;
    }
    if (prog.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();
}
#endif

void
IPFilter::add_handlers()
{
    Classifier::add_handlers();
#if CLICK_USERLEVEL
    add_read_handler("compressed_program", compressed_program_string, 0);
#endif
}


//
// RUNNING
//

void
IPFilter::length_checked_push(Packet *p)
{
  const unsigned char *neth_data = p->network_header();
  const unsigned char *transph_data = p->transport_header();
  int packet_length = p->length() + TRANSP_FAKE_OFFSET - p->transport_header_offset();
  const uint32_t *pr = _prog.begin();
  const uint32_t *pp;
  uint32_t data = 0;

  while (1) {
      int off = (int16_t) pr[0];
      if (off + 4 > packet_length)
	  goto check_length;

    length_ok:
      if (off >= TRANSP_FAKE_OFFSET)
	  data = *(const uint32_t *)(transph_data + off - TRANSP_FAKE_OFFSET);
      else
	  data = *(const uint32_t *)(neth_data + off);
      data &= pr[3];
      off = pr[0] >> 16;
      pp = pr + 4;
      if (!PERFORM_BINARY_SEARCH || off < MIN_BINARY_SEARCH) {
	  for (; off; --off, ++pp)
	      if (*pp == data) {
		  off = pr[2];
		  goto gotit;
	      }
      } else {
	  const uint32_t *px = pp + off;
	  while (pp < px) {
	      const uint32_t *pm = pp + (px - pp) / 2;
	      if (*pm == data) {
		  off = pr[2];
		  goto gotit;
	      } else if (*pm < data)
		  pp = pm + 1;
	      else
		  px = pm;
	  }
      }
    failure:
      off = pr[1];
    gotit:
      if (off <= 0) {
	  checked_output_push(-off, p);
	  return;
      }
      pr += off;
      continue;

    check_length:
      if (off < packet_length) {
	  unsigned available = packet_length - off;
	  const uint8_t *c = (const uint8_t *) &pr[3];
	  if (!(c[3]
		|| (c[2] && available <= 2)
		|| (c[1] && available == 1)))
	      goto length_ok;
      }
      goto failure;
  }
}

void
IPFilter::push(int, Packet *p)
{
  const unsigned char *neth_data = p->network_header();
  const unsigned char *transph_data = p->transport_header();

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

  const uint32_t *pr = _prog.begin();
  const uint32_t *pp;
  uint32_t data;
  while (1) {
      int off = (int16_t) pr[0];
      if (off >= TRANSP_FAKE_OFFSET)
	  data = *(const uint32_t *)(transph_data + off - TRANSP_FAKE_OFFSET);
      else
	  data = *(const uint32_t *)(neth_data + off);
      data &= pr[3];
      off = pr[0] >> 16;
      pp = pr + 4;
      if (!PERFORM_BINARY_SEARCH || off < MIN_BINARY_SEARCH) {
	  for (; off; --off, ++pp)
	      if (*pp == data) {
		  off = pr[2];
		  goto gotit;
	      }
      } else {
	  const uint32_t *px = pp + off;
	  while (pp < px) {
	      const uint32_t *pm = pp + (px - pp) / 2;
	      if (*pm == data) {
		  off = pr[2];
		  goto gotit;
	      } else if (*pm < data)
		  pp = pm + 1;
	      else
		  px = pm;
	  }
      }
      off = pr[1];
    gotit:
      if (off <= 0) {
	  checked_output_push(-off, p);
	  return;
      }
      pr += off;
  }
}

CLICK_ENDDECLS
ELEMENT_REQUIRES(Classifier)
EXPORT_ELEMENT(IPFilter)