| /* |
| * ipfilter.{cc,h} -- IP-packet filter with tcpdumplike syntax |
| * Eddie Kohler |
| * |
| * Copyright (c) 2000-2007 Mazu Networks, Inc. |
| * Copyright (c) 2004-2007 Regents of the University of California |
| * Copyright (c) 2007-2009 Dimitris Michailidis |
| * |
| * 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 <fcntl.h> |
| #include <assert.h> |
| #include <netdb.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include <arpa/inet.h> |
| #include "ipfilter.h" |
| |
| #define ACTION_SEP "=>" |
| |
| struct Entry { |
| const char *name; |
| uint32_t value; |
| }; |
| |
| static const Entry type_entries[] = { |
| { "aopen", IPFilter::TYPE_AOPEN }, |
| { "dest", IPFilter::TYPE_SYNTAX }, |
| { "dscp", IPFilter::FIELD_DSCP }, |
| { "dst", IPFilter::TYPE_SYNTAX }, |
| { "host", IPFilter::TYPE_HOST }, |
| { "listen", IPFilter::TYPE_LISTEN }, |
| { "mark", IPFilter::TYPE_MARK }, |
| { "net", IPFilter::TYPE_NET }, |
| { "not", IPFilter::TYPE_SYNTAX }, |
| { "popen", IPFilter::TYPE_POPEN }, |
| { "port", IPFilter::TYPE_PORT }, |
| { "src", IPFilter::TYPE_SYNTAX }, |
| { "tos", IPFilter::FIELD_TOS }, |
| { "vers", IPFilter::FIELD_VERSION }, |
| { "vlan", IPFilter::FIELD_VLAN }, |
| { 0, 0 } |
| }; |
| |
| static bool cp_integer(const std::string &s, int *valp) |
| { |
| char *p; |
| |
| *valp = strtoul(s.data(), &p, 0); |
| return *p == 0 && s[0]; |
| } |
| |
| static bool cp_integer(const std::string &s, uint32_t *valp) |
| { |
| char *p; |
| |
| *valp = strtoul(s.data(), &p, 0); |
| return *p == 0 && s[0]; |
| } |
| |
| static bool cp_integer(const std::string &s, int16_t *valp) |
| { |
| char *p; |
| unsigned long v; |
| |
| *valp = v = strtoul(s.data(), &p, 0); |
| return *p == 0 && s[0] && (v & ~0xffffUL) == 0; |
| } |
| |
| static bool cp_cong_algo(const std::string &s, int8_t *valp) |
| { |
| if (s == "reno") |
| *valp = 0; |
| else if (s == "tahoe") |
| *valp = 1; |
| else if (s == "newreno") |
| *valp = 2; |
| else if (s == "highspeed") |
| *valp = 3; |
| else |
| return false; |
| return true; |
| } |
| |
| static int ip_address_portion(const char *s, uint8_t *addr) |
| { |
| int d, part; |
| |
| for (d = 0; d < 4 && isdigit(*s); d++) { |
| for (part = 0; isdigit(*s) && part <= 255; s++) |
| part = part * 10 + *s - '0'; |
| if (part > 255) |
| return 0; |
| addr[d] = part; |
| |
| if (*s == '.') |
| s++; |
| } |
| |
| memset(addr + d, 0, 4 - d); |
| return *s == 0 ? d : 0; |
| } |
| |
| static bool cp_ip_address(const std::string &str, uint8_t *addr, |
| int af_allowed, int *af) |
| { |
| const char *s = str.c_str(); |
| bool v6 = strchr(s, ':') != NULL; |
| |
| if (v6) { |
| if (af_allowed == AF_INET) |
| return false; |
| if (inet_pton(AF_INET6, s, addr) <= 0) |
| return false; |
| if (af) |
| *af = AF_INET6; |
| } else { |
| if (af_allowed == AF_INET6) |
| return false; |
| if (ip_address_portion(s, addr) != 4) |
| return false; |
| if (af) |
| *af = AF_INET; |
| } |
| return true; |
| } |
| |
| /* |
| * cp_ip_mask is similar to cp_ip_address except it ensures the value read is |
| * indeed a mask rather than an arbitrary address. It also does not support |
| * AF_UNSPEC since a mask should match the corresponding address's family. |
| */ |
| static bool cp_ip_mask(const std::string &str, uint8_t *mask, int af) |
| { |
| if (!cp_ip_address(str, mask, af, NULL)) |
| return false; |
| |
| int addr_len = af == AF_INET ? 4 : 16; |
| while (addr_len--) { |
| uint8_t c = ~*mask++; |
| if (c & (c + 1)) |
| return false; |
| } |
| return true; |
| } |
| |
| static bool cp_ip_prefix(const std::string &str, uint8_t *return_value, |
| uint8_t *return_mask, bool allow_bare_address, |
| int af_allowed, int *af) |
| { |
| int addr_bytes; |
| int prefix_bits; |
| std::string ip_part, mask_part; |
| std::string::size_type slash = str.rfind('/'); |
| |
| if (slash == std::string::npos && allow_bare_address) |
| ip_part = str; |
| else if (slash != std::string::npos && slash < str.length() - 1) { |
| ip_part = str.substr(0, slash); |
| mask_part = str.substr(slash + 1); |
| } else |
| return false; |
| |
| bool v6 = ip_part.find(':') != std::string::npos; |
| if ((v6 && af_allowed == AF_INET) || (!v6 && af_allowed == AF_INET6)) |
| return false; |
| |
| int addr_len = v6 ? 16 : 4; |
| |
| // read IP address part |
| if (v6) { |
| if (inet_pton(AF_INET6, ip_part.c_str(), return_value) <= 0) |
| return false; |
| addr_bytes = 16; |
| } else { |
| addr_bytes = ip_address_portion(ip_part.c_str(), return_value); |
| if (addr_bytes == 0) |
| return false; |
| } |
| |
| if (af) |
| *af = v6 ? AF_INET6 : AF_INET; |
| |
| // check mask |
| if (allow_bare_address && !mask_part.length() && addr_bytes == addr_len) { |
| memset(return_mask, 255, addr_len); |
| return true; |
| } |
| |
| if (!cp_integer(mask_part, &prefix_bits) || prefix_bits < 0 || |
| prefix_bits > addr_len * 8 || addr_bytes < (prefix_bits + 7) / 8) |
| return false; |
| |
| // set mask bits |
| memset(return_mask, 0, addr_len); |
| memset(return_mask, 0xff, prefix_bits / 8); |
| if (prefix_bits % 8) |
| return_mask[prefix_bits / 8] = 0xff << (8 - prefix_bits % 8); |
| |
| return true; |
| } |
| |
| static inline int ffs_msb(uint32_t x) |
| { |
| return x ? __builtin_clz(x) + 1 : 0; |
| } |
| |
| int IPFilter::lookup(const std::string &word, int type, uint32_t &data) const |
| { |
| if (!isalpha(word[0])) // all potential translations start with a letter |
| return -1; |
| |
| // type queries always win if they occur |
| if (type == 0 || type == TYPE_TYPE) |
| for (const Entry *p = type_entries; p->name; p++) |
| if (word == p->name) { |
| data = p->value; |
| return data == TYPE_SYNTAX ? -1 : TYPE_TYPE; |
| } |
| |
| if (type == 0 || type == TYPE_PORT) { |
| /* |
| * Note that some glibcs are buggy and will match not only service |
| * names but random words in the /etc/services comments. At least |
| * the isalpha above doesn't let them match numbers and operators. |
| */ |
| struct servent *serv = getservbyname(word.c_str(), "tcp"); |
| if (serv) { |
| data = ntohs(serv->s_port); |
| return TYPE_PORT; |
| } |
| } |
| return -1; |
| } |
| |
| void IPFilter::Primitive::clear() |
| { |
| _type = _srcdst = 0; |
| _data = 0; |
| _op = OP_EQ; |
| _op_negated = false; |
| } |
| |
| void IPFilter::Primitive::set_type(int type, ErrorHandler *errh) |
| { |
| if (_type) |
| errh->error("type specified twice"); |
| _type = type; |
| } |
| |
| void IPFilter::Primitive::set_srcdst(int srcdst, ErrorHandler *errh) |
| { |
| if (_srcdst) |
| errh->error("'src' or 'dst' specified twice"); |
| _srcdst = srcdst; |
| } |
| |
| int IPFilter::Primitive::set_mask(uint32_t full_mask, int shift, |
| uint32_t provided_mask, ErrorHandler *errh) |
| { |
| uint32_t data = _u.u; |
| uint32_t this_mask = provided_mask ? provided_mask : full_mask; |
| |
| if ((this_mask & full_mask) != this_mask) |
| return errh->error("mask 0x%X out of range (0-0x%X)", provided_mask, |
| full_mask); |
| |
| if (_op == OP_GT || _op == OP_LT) { |
| // Check for comparisons that are always true or false. |
| if ((_op == OP_LT && (data == 0 || data > this_mask)) |
| || (_op == OP_GT && data >= this_mask)) { |
| bool will_be = (_op == OP_LT && data > this_mask ? |
| !_op_negated : _op_negated); |
| errh->warning("relation '%s %u' is always %s (range 0-%u)", |
| unparse_op(), data, will_be ? "true" : "false", |
| this_mask); |
| _u.u = _mask.u = 0; |
| _op_negated = !will_be; |
| _op = OP_EQ; |
| return 0; |
| } |
| |
| // value < X == !(value > (X - 1)) |
| if (_op == OP_LT) { |
| _u.u--; |
| _op_negated = !_op_negated; |
| _op = OP_GT; |
| } |
| |
| _u.u = (_u.u << shift) | ((1 << shift) - 1); |
| _mask.u = (this_mask << shift) | ((1 << shift) - 1); |
| // Want (_u.u & _mask.u) == _u.u. |
| // So change 'tcp[0] & 5 > 2' into the equivalent 'tcp[0] & 5 > 1': |
| // find the highest bit in _u that is not set in _mask, |
| // and turn on all lower bits. |
| if ((_u.u & _mask.u) != _u.u) { |
| uint32_t full_mask_u = (full_mask << shift) | ((1 << shift) - 1); |
| uint32_t missing_bits = (_u.u & _mask.u) ^ (_u.u & full_mask_u); |
| uint32_t add_mask = 0xFFFFFFFFU >> ffs_msb(missing_bits); |
| _u.u = (_u.u | add_mask) & _mask.u; |
| } |
| return 0; |
| } |
| |
| if (data > full_mask) |
| return errh->error("value %u out of range (0-%u)", data, full_mask); |
| |
| _u.u = data << shift; |
| _mask.u = this_mask << shift; |
| return 0; |
| } |
| |
| std::string IPFilter::Primitive::unparse_type(int srcdst, int type) |
| { |
| int len = 0; |
| char buf[512]; |
| const char *p = NULL; |
| |
| switch (srcdst) { |
| case SD_SRC: p = "src "; break; |
| case SD_DST: p = "dst "; break; |
| case SD_OR: p = "src or dst "; break; |
| case SD_AND: p = "src and dst "; break; |
| } |
| if (p) |
| len = sprintf(buf, p); |
| |
| p = NULL; |
| switch (type) { |
| case TYPE_NONE: p = "<none>"; break; |
| case TYPE_HOST: p = "host"; break; |
| case TYPE_PORT: p = "port"; break; |
| case TYPE_NET: p = "net"; break; |
| case TYPE_LISTEN: p = "listen"; break; |
| case TYPE_AOPEN: p = "active open"; break; |
| case TYPE_POPEN: p = "passive open"; break; |
| case TYPE_MARK: p = "mark"; break; |
| default: |
| if (type & TYPE_FIELD) { |
| switch (type) { |
| case FIELD_VERSION: p = "vers"; break; |
| case FIELD_TOS: p = "tos"; break; |
| case FIELD_DSCP: p = "dscp"; break; |
| case FIELD_VLAN: p = "vlan"; break; |
| } |
| } else |
| sprintf(buf + len, "<unknown type %d>", type); |
| break; |
| } |
| |
| if (p) |
| sprintf(buf + len, p); |
| |
| return std::string(buf); |
| } |
| |
| std::string IPFilter::Primitive::unparse_type() const |
| { |
| return unparse_type(_srcdst, _type); |
| } |
| |
| const char * IPFilter::Primitive::unparse_op() const |
| { |
| if (_op == OP_GT) |
| return _op_negated ? "<=" : ">"; |
| if (_op == OP_LT) |
| return _op_negated ? ">=" : "<"; |
| return _op_negated ? "!=" : "="; |
| } |
| |
| void IPFilter::Primitive::simple_negate() |
| { |
| assert(negation_is_simple()); |
| _op_negated = !_op_negated; |
| } |
| |
| /* |
| * Returns whether an expression primitive has integer type |
| */ |
| bool IPFilter::Primitive::is_int_type() const |
| { |
| return (_type & TYPE_FIELD) || _type == TYPE_MARK || _type == TYPE_PORT; |
| } |
| |
| int IPFilter::Primitive::check(const Primitive &p, uint32_t provided_mask, |
| ErrorHandler *errh) |
| { |
| // if _type is erroneous, return -1 right away |
| if (_type < 0) |
| return -1; |
| |
| // set _type if it was not specified |
| if (!_type) { |
| retry: |
| switch (_data) { |
| case TYPE_HOST: |
| case TYPE_NET: |
| case TYPE_PORT: |
| _type = _data; |
| if (!_srcdst) |
| _srcdst = p._srcdst; |
| break; |
| |
| case TYPE_INT: |
| if (!p.is_int_type()) |
| return errh->error("missing type for '%d'", _u.i); |
| _data = p._type; |
| goto retry; |
| |
| case TYPE_NONE: |
| return errh->error("partial directive"); |
| |
| default: |
| if (_data & TYPE_FIELD) |
| _type = _data; |
| else |
| return errh->error("unknown type '%s'", |
| unparse_type(0, _data).c_str()); |
| break; |
| } |
| } |
| |
| // check that _data and _type agree |
| 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'"); |
| if (provided_mask) |
| return errh->error("can't use masks with 'host', use 'net' instead"); |
| memset(_mask.c, 0xff, sizeof(_mask.c)); |
| 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'"); |
| if (provided_mask) |
| return errh->error("can't use & masks with 'net'"); |
| _type = TYPE_HOST; |
| // _mask already set |
| 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 (set_mask(0xFFFF, 0, provided_mask, errh) < 0) |
| return -1; |
| break; |
| |
| case TYPE_MARK: |
| if (_data == TYPE_INT) |
| _data = TYPE_MARK; |
| else if (_data != TYPE_MARK) |
| return errh->error("mark value missing in 'mark' directive"); |
| if (set_mask(0xFFFFFFFFU, 0, provided_mask, errh) < 0) |
| return -1; |
| break; |
| |
| case TYPE_LISTEN: |
| if (_data != TYPE_NONE) |
| return errh->error("'listen' directive takes no data"); |
| if (provided_mask) |
| return errh->error("can't use masks with 'listen'"); |
| _mask.u = 3; |
| _u.u = OPEN_TYPE_LISTEN; |
| break; |
| |
| case TYPE_AOPEN: |
| if (_data != TYPE_NONE) |
| return errh->error("'aopen' directive takes no data"); |
| if (provided_mask) |
| return errh->error("can't use masks with 'aopen'"); |
| _mask.u = 3; |
| _u.u = OPEN_TYPE_ACTIVE; |
| break; |
| |
| case TYPE_POPEN: |
| if (_data != TYPE_NONE) |
| return errh->error("'popen' directive takes no data"); |
| if (provided_mask) |
| return errh->error("can't use masks with 'popen'"); |
| _mask.u = 3; |
| _u.u = OPEN_TYPE_PASSIVE; |
| break; |
| |
| default: |
| if (_type & TYPE_FIELD) { |
| if (_data == TYPE_INT) |
| _data = _type; |
| else if (_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 (_srcdst) { |
| _srcdst = 0; |
| errh->warning("'src' or 'dst' is meaningless with '%s'", |
| unparse_type().c_str()); |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * Field explanation: |
| * |
| * offset: offset of the value we'll compare against in 32-bit units |
| * swapped: true if the value in the primitive is in the same byte order as the |
| * value it will be compared against |
| */ |
| void IPFilter::Primitive::add_comparison_exprs(Classifier *c, Vector<int> &tree, |
| int offset, int shift, bool swapped, bool op_negate) 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 && op_negate) |
| 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 && op_negate) |
| c->negate_expr_subtree(tree); |
| } |
| |
| void IPFilter::Primitive::add_exprs(Classifier *c, Vector<int> &tree) const |
| { |
| c->start_expr_subtree(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, SIP_WORD, SIP_OFFSET, true, false); |
| if (_srcdst == SD_DST || _srcdst == SD_AND || _srcdst == SD_OR) |
| add_comparison_exprs(c, tree, DIP_WORD, DIP_OFFSET, true, false); |
| c->finish_expr_subtree(tree, (_srcdst == SD_OR ? C_OR : C_AND)); |
| 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, SPORT_WORD, SPORT_OFFSET, false, |
| false); |
| if (_srcdst == SD_DST || _srcdst == SD_AND || _srcdst == SD_OR) |
| add_comparison_exprs(c, tree, DPORT_WORD, DPORT_OFFSET, false, |
| false); |
| c->finish_expr_subtree(tree, (_srcdst == SD_OR ? C_OR : C_AND)); |
| if (_op_negated) |
| c->negate_expr_subtree(tree); |
| break; |
| |
| case TYPE_LISTEN: |
| case TYPE_AOPEN: |
| case TYPE_POPEN: |
| c->add_expr(tree, OPENTYPE_WORD, htonl(_u.u << OPENTYPE_OFFSET), |
| htonl(_mask.u << OPENTYPE_OFFSET)); |
| break; |
| |
| case TYPE_MARK: |
| add_comparison_exprs(c, tree, MARK_WORD, MARK_OFFSET, true, true); |
| break; |
| |
| default: |
| if (_type & TYPE_FIELD) { |
| int offset = (_type & FIELD_OFFSET_MASK) >> FIELD_OFFSET_SHIFT; |
| int len = ((_type & FIELD_LENGTH_MASK) >> FIELD_LENGTH_SHIFT) + 1; |
| int word_offset = (offset >> 5), bit_offset = offset & 0x1F; |
| |
| add_comparison_exprs(c, tree, word_offset, 32 - (bit_offset + len), |
| false, true); |
| } else |
| assert(0); |
| break; |
| } |
| |
| c->finish_expr_subtree(tree); |
| } |
| |
| /* |
| * Returns true if a character is part of a word |
| */ |
| static bool is_word_char(const char c) |
| { |
| return isalnum(c) || c == '-' || c == '.' || c == '/' || c == '@' || |
| c == '_' || c == ':'; |
| } |
| |
| static bool is_or(const std::string &word) |
| { |
| return word == "or" || word == "||"; |
| } |
| |
| static bool is_and(const std::string &word) |
| { |
| return word == "and" || word == "&&"; |
| } |
| |
| static bool is_not(const std::string &word) |
| { |
| return word == "not" || word == "!"; |
| } |
| |
| static bool is_dst(const std::string &word) |
| { |
| return word == "dst" || word == "dest"; |
| } |
| |
| static void tokenize(const std::string &text, Vector<std::string> &words) |
| { |
| const char *s = text.data(); |
| int len = text.length(); |
| int pos = 0; |
| |
| while (pos < len) { |
| while (pos < len && isspace(s[pos])) |
| pos++; |
| if (pos >= len) |
| break; |
| |
| 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; |
| if (s[pos] == '=' && pos < len - 1 && s[pos + 1] == '>') |
| goto two_char; |
| goto one_char; |
| |
| case '(': case ')': case ',': case ';': case '?': |
| one_char: |
| words.push_back(text.substr(pos, 1)); |
| pos++; |
| break; |
| two_char: |
| words.push_back(text.substr(pos, 2)); |
| pos += 2; |
| break; |
| |
| default: |
| int first = pos; |
| while (pos < len && is_word_char(s[pos])) |
| pos++; |
| if (pos == first) // must consume at least a character per iteration |
| pos++; |
| words.push_back(text.substr(first, pos - first)); |
| break; |
| } |
| } |
| } |
| |
| /* |
| * expr ::= orexpr |
| * | orexpr ? expr : expr |
| * ; |
| * orexpr ::= orexpr || orexpr |
| * | orexpr or orexpr |
| * | term |
| * ; |
| * term ::= term && term |
| * | term and term |
| * | term factor // juxtaposition = and |
| * | factor |
| * factor ::= ! factor |
| * | true |
| * | false |
| * | quals data |
| * | quals relop data |
| * | ( expr ) |
| * ; |
| */ |
| |
| int |
| IPFilter::parse_expr(const Vector<std::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 ((vec_size_t)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) |
| break; |
| if ((vec_size_t)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<std::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 ((vec_size_t)pos >= words.size() || !is_or(words[pos])) |
| break; |
| pos++; |
| } |
| |
| finish_expr_subtree(tree, C_OR); |
| return pos; |
| } |
| |
| int |
| IPFilter::parse_term(const Vector<std::string> &words, int pos, |
| Vector<int> &tree, Primitive &prev_prim, |
| ErrorHandler *errh) |
| { |
| start_expr_subtree(tree); |
| |
| bool blank_ok = false; // controls whether a term is required |
| while (1) { |
| int next = parse_factor(words, pos, tree, prev_prim, false, errh); |
| if (next == pos) |
| break; |
| blank_ok = true; |
| if ((vec_size_t)next < words.size() && is_and(words[next])) { |
| blank_ok = false; |
| next++; |
| } |
| pos = next; |
| } |
| |
| if (!blank_ok) |
| errh->error("missing term"); |
| finish_expr_subtree(tree); |
| return pos; |
| } |
| |
| int |
| IPFilter::parse_factor(const Vector<std::string> &words, int pos, |
| Vector<int> &tree, Primitive &prev_prim, |
| bool negated, ErrorHandler *errh) |
| { |
| int nwords = words.size(); |
| uint32_t provided_mask = 0; |
| |
| // return immediately on last word, ")", "||", "or", "?", ":" |
| if (pos >= nwords || words[pos] == ")" || is_or(words[pos]) || |
| words[pos] == "?" || words[pos] == ":" || words[pos] == ACTION_SEP) |
| 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 (is_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 '('"); |
| else { |
| if (next >= nwords || 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 < nwords; pos++) { |
| uint32_t wdata; |
| const std::string &wd = words[pos]; |
| int wt = lookup(wd, 0, wdata); |
| |
| if (wt == TYPE_TYPE) |
| prim.set_type(wdata, errh); |
| else if (wt != -1) |
| break; |
| else if (wd == "src") { |
| if (pos < nwords - 2 && is_dst(words[pos + 2])) { |
| if (is_and(words[pos + 1])) { |
| prim.set_srcdst(SD_AND, errh); |
| pos += 2; |
| } else if (is_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 (is_dst(wd)) |
| prim.set_srcdst(SD_DST, errh); |
| else if (is_not(wd)) |
| negated = !negated; |
| else |
| break; |
| } |
| |
| // if any qualifiers were found next check for optional mask and relops |
| if (pos != first_pos) { |
| prev_prim.clear(); // prev_prim is irrelevant if there were qualifiers |
| |
| if (pos < nwords && words[pos] == "&") { |
| pos++; |
| if (pos >= nwords || !cp_integer(words[pos], &provided_mask)) |
| errh->error("missing mask after &"); |
| else if (provided_mask == 0) |
| errh->error("bitmask of 0 ignored"); |
| else |
| pos++; |
| } |
| |
| if (pos < nwords) { |
| const std::string &wd = words[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 < nwords) { |
| uint32_t wdata; |
| const std::string &wd = words[pos]; |
| int wt = lookup(wd, prim._type, wdata); |
| |
| pos++; |
| 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, AF_INET, NULL)) { |
| if (pos < nwords - 1 && words[pos] == "mask") { |
| if (cp_ip_mask(words[pos + 1], prim._mask.c, AF_INET)) { |
| pos += 2; |
| prim._data = TYPE_NET; |
| } else { |
| errh->error("illegal mask %s", words[pos + 1].c_str()); |
| return pos; |
| } |
| } else if (prim._type == TYPE_NET) { |
| memset(prim._mask.c, 255, 16); |
| prim._data = TYPE_NET; |
| } else |
| prim._data = TYPE_HOST; |
| } else if (cp_ip_prefix(wd, prim._u.c, prim._mask.c, false, AF_INET, |
| NULL)) |
| 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'", words[pos].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::parse_offload_settings(const stringvec &words, int pos, |
| ErrorHandler *errh) |
| { |
| int neg = 0, nwords = words.size(); |
| OffloadSettings os; |
| |
| while (pos < nwords) { |
| if (words[pos] == "!" or words[pos] == "not") |
| neg++; |
| else if (words[pos] == "offload") { |
| os.offload = (neg + 1) & 1; |
| neg = 0; |
| } else if (words[pos] == "ddp") { |
| os.ddp = (neg + 1) & 1; |
| neg = 0; |
| } else if (words[pos] == "coalesce") { |
| os.rx_coalesce = (neg + 1) & 1; |
| neg = 0; |
| } else if (words[pos] == "sack") { |
| os.sack = (neg + 1) & 1; |
| neg = 0; |
| } else if (words[pos] == "timestamp" || words[pos] == "tstamp") { |
| os.tstamp = (neg + 1) & 1; |
| neg = 0; |
| } else { |
| if (neg) { |
| errh->error("negation can't be used with '%s'", |
| words[pos].c_str()); |
| neg = 0; |
| } else if (words[pos] == "bind") { |
| if (pos + 1 >= nwords) |
| errh->error("missing value for 'bind'"); |
| else if (words[pos + 1] == "random") |
| os.bind_q = QUEUE_RANDOM; |
| else if (words[pos + 1] == "cpu") |
| os.bind_q = QUEUE_CPU; |
| else if (!cp_integer(words[pos + 1], &os.bind_q) || |
| os.bind_q < 0) |
| errh->error("'bind' needs an integer value >= 0, 'cpu', or " |
| "'random'"); |
| pos++; |
| } else if (words[pos] == "cong") { |
| if (pos + 1 >= nwords || |
| !cp_cong_algo(words[pos + 1], &os.cong_algo)) |
| errh->error("unknown congestion algorithm %s", |
| words[pos + 1].c_str()); |
| pos++; |
| } else if (words[pos] == "class") { |
| if (pos + 1 >= nwords || |
| !cp_integer(words[pos + 1], &os.sched_class) || |
| os.sched_class < 0) |
| errh->error("'class' needs an integer value between 0 " |
| "and 65535"); |
| pos++; |
| } else |
| return pos; |
| } |
| pos++; |
| } |
| if (neg) |
| errh->error("incomplete negation at end of rule"); |
| _settings.push_back(os); |
| return pos; |
| } |
| |
| static inline bool is_filter_wildcard(const std::string &word) |
| { |
| return word == "any" || word == "all" || word == "-"; |
| } |
| |
| int IPFilter::configure(stringvec &conf, ErrorHandler *errh) |
| { |
| _output_everything = -1; |
| _noutputs = conf.size(); |
| |
| Vector<int> tree; |
| init_expr_subtree(tree); |
| errh->snap_errors(); |
| |
| // [QUALS] [host|net|port] [data] |
| // QUALS ::= src | dst | src and dst | src or dst | \empty |
| for (vec_size_t argno = 0; argno < conf.size(); argno++) { |
| Vector<std::string> words; |
| tokenize(conf[argno], words); |
| |
| if (words.size() == 0) { |
| errh->error("empty pattern %d", argno); |
| continue; |
| } |
| |
| char pfx[80]; |
| sprintf(pfx, "rule %zd: ", argno); |
| errh->set_prefix(pfx); |
| |
| int pos, nwords = words.size(); |
| unsigned int old_errors = errh->nerrors(); |
| start_expr_subtree(tree); |
| |
| // check for "-" |
| if (nwords >= 2 && words[1] == ACTION_SEP && |
| is_filter_wildcard(words[0])) { |
| add_expr(tree, 0, 0, 0); |
| pos = 1; |
| } else { |
| // start with a blank primitive |
| Primitive prev_prim; |
| |
| pos = parse_expr(words, 0, tree, prev_prim, errh); |
| } |
| |
| if (errh->nerrors() != old_errors) |
| ; // don't bother with settings if the filter had errors |
| else if (pos < nwords && words[pos] == ACTION_SEP) { |
| pos = parse_offload_settings(words, pos + 1, errh); |
| if (pos < nwords) |
| errh->error("unexpected '%s'", words[pos].c_str()); |
| } else |
| errh->error("missing '" ACTION_SEP "' after rule filter"); |
| |
| finish_expr_subtree(tree, C_AND, -argno); |
| } |
| |
| // add sentinel offload settings |
| _settings.push_back(OffloadSettings()); |
| |
| finish_expr_subtree(tree, C_OR, -noutputs(), -noutputs()); |
| |
| errh->set_prefix(0); |
| if (errh->any_errors()) |
| return -1; |
| |
| optimize_exprs(errh); |
| if (_output_everything < 0) { |
| // It helps to do another bubblesort for things like ports. |
| bubble_sort_and_exprs(); |
| |
| // Compress the program into _prog. |
| compress_exprs(_prog, false); |
| } |
| return errh->any_errors() ? -1 : 0; |
| } |
| |
| void IPFilter::dump_integer_program(FILE *fp) const |
| { |
| fprintf(fp, "optimized classifier program:\n"); |
| |
| if (_output_everything >= 0) { |
| fprintf(fp, "all->[%d]\n", _output_everything); |
| return; |
| } |
| |
| for (vec_size_t i = 0; i < _prog.size(); ) { |
| int nvals = _prog[i] >> 16; |
| |
| fprintf(fp, "%4zd %d #%d %08x yes->", i, _prog[i] & 0xffff, nvals, |
| htonl(_prog[i+3])); |
| if ((int32_t) _prog[i+2] > 0) |
| fprintf(fp, "step %zd ", _prog[i+2] + i); |
| else |
| fprintf(fp, "[%d] ", -(int32_t)_prog[i+2]); |
| if ((int32_t) _prog[i+1] > 0) |
| fprintf(fp, "no->step %zd\n", _prog[i+1] + i); |
| else |
| fprintf(fp, "no->[%d]\n", -(int32_t)_prog[i+1]); |
| i += 4; |
| |
| while (nvals--) { |
| fprintf(fp, "%4zd %08x\n", i, htonl(_prog[i])); |
| i++; |
| } |
| } |
| } |
| |
| void IPFilter::dump_offload_settings(FILE *fp) const |
| { |
| fprintf(fp, "offload settings:\n"); |
| |
| for (vec_size_t i = 0; i < _settings.size(); i++) { |
| const OffloadSettings &os = _settings[i]; |
| |
| fprintf(fp, "%4zd: offload %u, ddp %d, coalesce %d, cong_algo %d, " |
| "queue %d, class %d, tstamp %d, sack %d\n", |
| i, os.offload, os.ddp, os.rx_coalesce, os.cong_algo, os.bind_q, |
| os.sched_class, os.tstamp, os.sack); |
| } |
| } |
| |
| /* |
| * An offload policy file consists of the following sections: |
| * - file header of size sizeof(ClassifierFileHeader) |
| * - unoptimized classification program of size header.prog_size * 20, where |
| * 20 is the size of a program "instruction" (5 ints) |
| * - optimized classification program of size header.opt_prog_size * 4 |
| * - offload settings of size header.nsettings * sizeof(OffloadSettings) |
| */ |
| int IPFilter::save(const char *fname) const |
| { |
| size_t sz; |
| |
| int fd = creat(fname, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH); |
| if (fd < 0) |
| return -1; |
| |
| ClassifierFileHeader h; |
| h.vers = 0; |
| h.output_everything = _output_everything; |
| h.nrules = noutputs(); |
| h.prog_size = _exprs.size(); |
| h.opt_prog_size = _prog.size(); |
| h.nsettings = _settings.size(); |
| if (write(fd, &h, sizeof(h)) != sizeof(h)) { |
| fail: close(fd); |
| return -1; |
| } |
| |
| sz = _exprs.size() * 5 * sizeof(int); |
| if (sz && write(fd, &_exprs[0], sz) != (ssize_t)sz) |
| goto fail; |
| |
| sz = _prog.size() * sizeof(int); |
| if (sz && write(fd, &_prog[0], sz) != (ssize_t)sz) |
| goto fail; |
| |
| sz = _settings.size() * sizeof(OffloadSettings); |
| if (write(fd, &_settings[0], sz) != (ssize_t)sz) |
| goto fail; |
| |
| close(fd); |
| return 0; |
| } |
| |
| int IPFilter::optimized_match(const OffloadReq &req) const |
| { |
| if (_output_everything >= 0) |
| return _output_everything; |
| |
| const uint32_t *q = (const uint32_t *)&req; |
| const uint32_t *pr = &_prog[0], *pp; |
| |
| while (1) { |
| int off = (int16_t) pr[0]; |
| uint32_t data = q[off] & pr[3]; |
| |
| for (off = pr[0] >> 16, pp = pr + 4; off; off--, pp++) |
| if (*pp == data) { |
| off = pr[2]; |
| goto gotit; |
| } |
| off = pr[1]; |
| gotit: |
| if (off <= 0) |
| return -off; |
| pr += off; |
| } |
| } |
| |
| #ifndef USE_STD_VECTOR |
| # include "vector.cc" |
| #endif |
| |
| // vim: shiftwidth=4 |
