/* * Copyright (c) 2001 Mark Fullmer and The Ohio State University * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * *      $Id: ftfil.c,v 1.18 2003/04/02 16:07:12 maf Exp $ */#include "ftconfig.h"#include "ftlib.h"#include <sys/time.h>#include <sys/types.h>#include <sys/uio.h>#include <sys/socket.h>#include <sys/resource.h>#include <netinet/in.h>#include <arpa/inet.h>#include <sys/stat.h>#include <ctype.h>#include <syslog.h>#include <dirent.h>#include <limits.h>#include <unistd.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include <fcntl.h>#include <zlib.h>#if HAVE_STRINGS_H #include <strings.h>#endif#if HAVE_STRING_H  #include <string.h>#endif#if !HAVE_STRSEP  char    *strsep (char **, const char *);#endif#define PARSE_PRIMITIVE_TYPE_INIT(A)\  if (!(A = malloc (sizeof *A))) {\    fterr_warn("malloc()");\    return -1;\  }\  bzero(A, sizeof *A);\  A->init = 1;\  A->default_mode = FT_FIL_MODE_DENY;\  lp->cur_primitive->lookup = A;\#define RADIX_TRIE_INIT\  if (!rn_init_called) {\    max_keylen = sizeof(struct radix_sockaddr_in);\    rn_init();\    rn_init_called = 1;\  }\extern int max_keylen;extern u_int32 mask_lookup[];static int rn_init_called;static struct radix_node_head *rhead;enum ftfil_op { FT_FIL_OP_UNSET, FT_FIL_OP_LT, FT_FIL_OP_GT,                   FT_FIL_OP_EQ, FT_FIL_OP_NE, FT_FIL_OP_GE,                   FT_FIL_OP_LE };    enum ftfil_parse_state { PARSE_STATE_UNSET, PARSE_STATE_PRIMITIVE,                          PARSE_STATE_DEFINITION };    enum ftfil_def_match { FT_FIL_DEFINITION_MATCH_UNSET,                               FT_FIL_DEFINITION_MATCH_SRC_AS,                               FT_FIL_DEFINITION_MATCH_DST_AS,                               FT_FIL_DEFINITION_MATCH_IP_SRC_ADDR,                               FT_FIL_DEFINITION_MATCH_IP_DST_ADDR,                               FT_FIL_DEFINITION_MATCH_IP_EXPORTER_ADDR,                               FT_FIL_DEFINITION_MATCH_IP_NEXT_HOP_ADDR,                               FT_FIL_DEFINITION_MATCH_IP_SC_ADDR,                               FT_FIL_DEFINITION_MATCH_IP_PROTOCOL,                               FT_FIL_DEFINITION_MATCH_IP_SRC_PREFIX_LEN,                               FT_FIL_DEFINITION_MATCH_IP_DST_PREFIX_LEN,                               FT_FIL_DEFINITION_MATCH_IP_TOS,                               FT_FIL_DEFINITION_MATCH_IP_MARKED_TOS,                               FT_FIL_DEFINITION_MATCH_IP_TCP_FLAGS,                               FT_FIL_DEFINITION_MATCH_IP_SRC_PORT,                               FT_FIL_DEFINITION_MATCH_IP_DST_PORT,                               FT_FIL_DEFINITION_MATCH_INPUT_IF,                               FT_FIL_DEFINITION_MATCH_OUTPUT_IF,                               FT_FIL_DEFINITION_MATCH_START_TIME,                               FT_FIL_DEFINITION_MATCH_END_TIME,                               FT_FIL_DEFINITION_MATCH_FLOWS,                               FT_FIL_DEFINITION_MATCH_OCTETS,                               FT_FIL_DEFINITION_MATCH_PACKETS,                               FT_FIL_DEFINITION_MATCH_XTRA_PACKETS,                               FT_FIL_DEFINITION_MATCH_DURATION,                               FT_FIL_DEFINITION_MATCH_ENGINE_ID,                               FT_FIL_DEFINITION_MATCH_ENGINE_TYPE,                               FT_FIL_DEFINITION_MATCH_SRC_TAG,                               FT_FIL_DEFINITION_MATCH_DST_TAG,                               FT_FIL_DEFINITION_MATCH_PPS,                               FT_FIL_DEFINITION_MATCH_BPS,                               FT_FIL_DEFINITION_MATCH_RANDOM_SAMPLE };char *op_name_lookup[] = {"Unset", "lt", "gt", "eq", "ne", "ge", "le"};char *mode_name_lookup[] = {"Unset", "permit", "deny"};struct line_parser {  enum ftfil_parse_state state;  enum ftfil_primitive_type type;  enum ftfil_mode mode;  struct ftfil_primitive *cur_primitive;  struct ftfil_def *cur_def;  struct ftfil_match *cur_def_match;  struct ftsym *sym_ip_prot;  struct ftsym *sym_ip_tcp_port;  struct ftsym *sym_asn;  struct ftsym *sym_tag;  struct ftsym *sym_cur;  int lineno;  char *buf, *fname, *word;  };struct ftfil_lookup_ip_address {  struct ftchash *ftch;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_mask {  FT_STAILQ_HEAD(filipmhead, ftfil_lookup_ip_mask_rec) list;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_mask_rec {  FT_STAILQ_ENTRY(ftfil_lookup_ip_mask_rec) chain;  u_int32 ip, mask;  int mode; /* FT_FIL_MODE_PERMIT/DENY */};struct ftfil_lookup_ip_prefix_rec {  struct radix_node rt_nodes[2]; /* radix tree glue */  struct radix_sockaddr_in addr;  u_int8 masklen;  int mode; /* FT_FIL_MODE_PERMIT/DENY */};struct ftfil_lookup_ip_prefix {  struct radix_node_head *rhead;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_as {  u_int8 mode[65536];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_prot {  u_int8 mode[256];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_port {  u_int8 mode[65536];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_tos {  u_int8 mask;  u_int8 mode[256];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_tcp_flags {  u_int8 mask;  u_int8 mode[256];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_if_index {  u_int8 mode[65536];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_engine {  u_int8 mode[256];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_ip_prefix_len {  u_int8 mode[33];  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_counter_rec {  FT_STAILQ_ENTRY(ftfil_lookup_counter_rec) chain;  u_int32 val;  enum ftfil_op op; /* FT_FIL_OP */  int mode;};struct ftfil_lookup_counter {  FT_STAILQ_HEAD(fillchead, ftfil_lookup_counter_rec) list;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_double_rec {  FT_STAILQ_ENTRY(ftfil_lookup_double_rec) chain;  double val;  enum ftfil_op op; /* FT_FIL_OP */  int mode;};struct ftfil_lookup_double {  FT_STAILQ_HEAD(filldhead, ftfil_lookup_double_rec) list;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_tag {  struct ftchash *ftch;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_tag_mask_rec {  FT_STAILQ_ENTRY(ftfil_lookup_tag_mask_rec) chain;  u_int32 tag, mask;  int mode; /* FT_FIL_MODE_PERMIT/DENY */};struct ftfil_lookup_tag_mask {  FT_STAILQ_HEAD(filtmhead, ftfil_lookup_tag_mask_rec) list;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_time_rec {  FT_STAILQ_ENTRY(ftfil_lookup_time_rec) chain;  int hour, min, sec;  enum ftfil_op op; /* FT_FIL_OP */  int mode;};struct ftfil_lookup_time {  FT_STAILQ_HEAD(filltmehead, ftfil_lookup_time_rec) list;  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_lookup_rate {  int rate;  enum ftfil_mode mode; /* FT_FIL_MODE_PERMIT/DENY */  enum ftfil_mode default_mode; /* FT_FIL_MODE_PERMIT/DENY */  int init; /* initialized? */};struct ftfil_match_item_cache {  FT_SLIST_ENTRY(ftfil_match_item_cache) chain;  u_int32 time; /* cache time -- only valid for flow == curflow+1 */  void *flow; /* address of flow evaluating -- used to invalidate cache */  enum ftfil_mode mode; /* result FT_FIL_MODE_* */  void *lookup; /* data for evaluator */  int (*eval)(void *lookup, void *rec, struct fts3rec_offsets *fo);};static int walk_free(struct radix_node *rn, struct walkarg *UNUSED);static int ftfil_load_lookup(struct line_parser *lp, char *s, int size,  char *list, int mode);static int parse_definition(struct line_parser *lp,  struct ftfil *ftfil);static int parse_definition_match(struct line_parser *lp,  struct ftfil *ftfil);static int parse_definition_or(struct line_parser *lp,  struct ftfil *ftfil);static int parse_definition_invert(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive(struct line_parser *lp, struct ftfil *ftfil);static int parse_primitive_type(struct line_parser *lp, struct ftfil *ftfil);static int parse_primitive_deny(struct line_parser *lp, struct ftfil *ftfil);static int parse_primitive_permit(struct line_parser *lp, struct ftfil *ftfil);static int parse2_primitive_permitdeny(struct line_parser *lp,  struct ftfil *ftfil, int flag);static int parse_primitive_default(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_mask(struct line_parser *lp, struct ftfil *ftfil);static int parse_primitive_type_asn(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_prot(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_port(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_prefix_len(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_if_index(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_tos(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_tcp_flags(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_engine(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_ip_address(struct line_parser *lp,  struct ftfil *ftfil);int parse_primitive_type_ip_mask(struct line_parser *lp,  struct ftfil *ftfil);int parse_primitive_type_ip_prefix(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_tag(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_tag_mask(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_counter(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_time_date(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_time(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_double(struct line_parser *lp,  struct ftfil *ftfil);static int parse_primitive_type_rate(struct line_parser *lp,  struct ftfil *ftfil);inline int eval_match_src_as(struct ftfil_lookup_as *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_dst_as(struct ftfil_lookup_as *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_engine_type(struct ftfil_lookup_engine *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_engine_id(struct ftfil_lookup_engine *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_dst_if_index(struct ftfil_lookup_if_index *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_src_if_index(struct ftfil_lookup_if_index *lookup,  char *rec, struct fts3rec_offsets *fo); inline int eval_match_ip_dst_port(struct ftfil_lookup_ip_port *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_src_port(struct ftfil_lookup_ip_port *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_tcp_flags(struct ftfil_lookup_ip_tcp_flags *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_marked_tos(struct ftfil_lookup_ip_tos *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_tos(struct ftfil_lookup_ip_tos *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_dst_prefix_len(struct ftfil_lookup_ip_prefix_len  *lookup, char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_src_prefix_len(struct ftfil_lookup_ip_prefix_len  *lookup, char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_prot(struct ftfil_lookup_ip_prot *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_flows(struct ftfil_lookup_counter *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_octets(struct ftfil_lookup_counter *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_packets(struct ftfil_lookup_counter *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_xtra_packets(struct ftfil_lookup_counter *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_duration(struct ftfil_lookup_counter *lookup, char *rec,  struct fts3rec_offsets *fo);inline int eval_match_start_time_date(struct ftfil_lookup_counter *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_end_time_date(struct ftfil_lookup_counter *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_start_time(struct ftfil_lookup_time *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_end_time(struct ftfil_lookup_time *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_src_tag_l(struct ftfil_lookup_tag_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_src_tag_h(struct ftfil_lookup_tag *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_dst_tag_l(struct ftfil_lookup_tag_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_dst_tag_h(struct ftfil_lookup_tag *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_sc_addr_l(struct ftfil_lookup_ip_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_sc_addr_h(struct ftfil_lookup_ip_address *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_sc_addr_r(struct ftfil_lookup_ip_prefix *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_nexthop_addr_l(struct ftfil_lookup_ip_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_nexthop_addr_h(struct ftfil_lookup_ip_address *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_nexthop_addr_r(struct ftfil_lookup_ip_prefix *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_src_addr_l(struct ftfil_lookup_ip_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_src_addr_h(struct ftfil_lookup_ip_address *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_src_addr_r(struct ftfil_lookup_ip_prefix *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_dst_addr_l(struct ftfil_lookup_ip_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_dst_addr_h(struct ftfil_lookup_ip_address *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_dst_addr_r(struct ftfil_lookup_ip_prefix *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_exporter_addr_l(struct ftfil_lookup_ip_mask *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_exporter_addr_h(struct ftfil_lookup_ip_address *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_ip_exporter_addr_r(struct ftfil_lookup_ip_prefix *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_pps(struct ftfil_lookup_double *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_bps(struct ftfil_lookup_double *lookup,  char *rec, struct fts3rec_offsets *fo);inline int eval_match_random_sample(struct ftfil_lookup_rate *lookup,  char *rec, struct fts3rec_offsets *fo);static int resolve_primitives(struct ftfil *ftfil);#define NEXT_WORD(A,B)\  for (;;) {\    B = strsep(A, " \t");\    if ((B && *B != 0) || (!B))\      break;\  }\ struct jump {  char *name;  enum ftfil_parse_state state;  int (*func)(struct line_parser *lp, struct ftfil *ftfil);};static struct jump pjump[] = {          {"filter-primitive", 0, parse_primitive},          {"type", PARSE_STATE_PRIMITIVE, parse_primitive_type},          {"permit", PARSE_STATE_PRIMITIVE, parse_primitive_permit},          {"deny", PARSE_STATE_PRIMITIVE, parse_primitive_deny},          {"default", PARSE_STATE_PRIMITIVE, parse_primitive_default},          {"mask", PARSE_STATE_PRIMITIVE, parse_primitive_mask},          {"filter-definition", 0, parse_definition},          {"match", PARSE_STATE_DEFINITION, parse_definition_match},          {"or", PARSE_STATE_DEFINITION, parse_definition_or},          {"invert", PARSE_STATE_DEFINITION, parse_definition_invert},          {0, 0, 0},          };/* * data structures: * * Each primitive is stored in a linked list of struct ftfil_primitive.  The * head is ftfil.primitives.  Each primitive has a lookup entry which  * points to a struct ftfil_lookup_* based on the enum ftfil_primitive_type * stored as type.  Some lookup entries allocate further storage (ie * a hash, radix tree, or linked list for the linear lookups). * * Each definition is stored in a linked list of struct ftfil_def. * The head is ftfil.defs.  Each definition has a list of * ftfil_match matches.  The matches have a list of ftfil_match_items. * For a match to be satisfied each each item in the match must evaluate * true (AND).  For a definition to be satisfied (permitted) one of the * entries in the match list must be satisfied (OR). * * Each primitive (enum ftfil_primitive_type) has an associated * parse_primitive_type_xxx(). * * Each match type (enum ftfil_def_match) has an associated * eval_match_xxx(). * * ftfil_eval() walks the matches and the match items for the definition * passed to it looking for a match.  If every match item in a match * evaluated to permit (enum ftfil_mode) a permit is returned, else * a deny. * * The current evaluator code does not cache results.  For example * * match src-ip-addr test1 * match ip-protocol test2 * or * match src-ip-addr test1 * match ip-port test3 * * If the first two matches fail the result from "match src-ip-addr test1" * will need to be calculated a second time.  In practice this doesn't * seem to be a problem -- the performance impact is minimal for real * world definitions.  Adding a cache would most likely reduce performance * for most cases due to overhead of the cache test/update code. *