Date: Sun, 7 Jun 2009 14:19:37 GMT From: Tatsiana Elavaya <tsel@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 163713 for review Message-ID: <200906071419.n57EJbes015414@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=163713 Change 163713 by tsel@tsel_mz on 2009/06/07 14:19:09 Simplify get_rules_chached() usage Initial implementation of rule optimization Affected files ... .. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#3 edit .. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.h#3 edit .. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/main.c#3 edit Differences ... ==== //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#3 (text+ko) ==== @@ -469,31 +469,43 @@ return data; } -static struct ip_fw* -get_rule_cache(int *len) +static struct ip_fw** +get_rules_cached() { - static struct ip_fw *rules = NULL; - static int rules_len = 0; + static struct ip_fw *raw_rules = NULL; + static struct ip_fw **rules = NULL; + int i, rules_len; + + if (raw_rules == NULL || rules == NULL) { + char *r, *end; - if (rules == NULL) { - rules = (struct ip_fw*) ipfw_get_all(IP_FW_GET, &rules_len); - rules_len = rules_len / sizeof(struct ip_fw); + raw_rules = (struct ip_fw*) ipfw_get_all(IP_FW_GET, &rules_len); + rules = safe_calloc(rules_len / sizeof(struct ip_fw) + 1, sizeof(void*)); + r = (char*)raw_rules; + end = r + rules_len; + for (i = 0; ; i++) { + if (r + RULESIZE(r) > end) { + rules[i] = NULL; + break; + } + rules[i] = (struct ip_fw *)r; + r += RULESIZE(r); + } } - *len = rules_len; return rules; } static int alias_lookup_rulenum(const char *alias) { - struct ip_fw *rules; - int len, i; + struct ip_fw **rules; + int i; - rules = get_rule_cache(&len); - for (i = 0; i < len; i++) { - if (!strcmp(rules[i].alias, alias)) - return rules[i].rulenum; + rules = get_rules_cached(); + for (i = 0; rules[i]; i++) { + if (!strcmp(rules[i]->alias, alias)) + return rules[i]->rulenum; } return -1; } @@ -501,13 +513,13 @@ static char* alias_lookup(int rulenum) { - struct ip_fw *rules; - int len, i; + struct ip_fw **rules; + int i; - rules = get_rule_cache(&len); - for (i = 0; i < len; i++) { - if (rules[i].rulenum == rulenum) - return rules[i].alias[0] ? rules[i].alias : NULL; + rules = get_rules_cached(); + for (i = 0; rules[i]; i++) { + if (rules[i]->rulenum == rulenum) + return rules[i]->alias[0] ? rules[i]->alias : NULL; } return NULL; } @@ -1990,6 +2002,205 @@ #undef NEXT } +struct insn_match { + ipfw_insn *cmd; + int match_count; + int list_size; + struct insn_match *next; + struct insn_match *next_match; + struct ip_fw *rule; + int rank; +}; + +int +insn_eq(ipfw_insn *a, ipfw_insn *b) +{ + if (a->opcode != b->opcode) + return (0); + switch (a->opcode) { + case O_IP_SRC: + case O_IP_SRC_MASK: + case O_IP_SRC_ME: + case O_IP_SRC_SET: + case O_IP_DST: + case O_IP_DST_MASK: + case O_IP_DST_ME: + case O_IP_DST_SET: + case O_IP_SRCPORT: + case O_IP_DSTPORT: + case O_PROTO: + case O_MACADDR2: + case O_MAC_TYPE: + case O_LAYER2: + case O_IN: + case O_FRAG: + case O_RECV: + case O_XMIT: + case O_VIA: + case O_IPOPT: + case O_IPLEN: + case O_IPID: + case O_IPTOS: + case O_IPPRECEDENCE: + case O_IPTTL: + case O_IPVER: + case O_UID: + case O_GID: + case O_ESTAB: + case O_TCPFLAGS: + case O_TCPWIN: + case O_TCPSEQ: + case O_TCPACK: + case O_ICMPTYPE: + case O_TCPOPTS: + case O_VERREVPATH: + case O_VERSRCREACH: + case O_IPSEC: + case O_IP_SRC_LOOKUP: + case O_IP_DST_LOOKUP: + case O_ANTISPOOF: + case O_JAIL: + case O_TCPDATALEN: + case O_IP6_SRC: + case O_IP6_SRC_ME: + case O_IP6_SRC_MASK: + case O_IP6_DST: + case O_IP6_DST_ME: + case O_IP6_DST_MASK: + case O_FLOW6ID: + case O_ICMP6TYPE: + case O_EXT_HDR: + case O_IP6: + case O_IP4: + break; + default: + return(0); + } + if (F_LEN(a) != F_LEN(b)) + return(0); + if (memcmp(a, b, F_LEN(a)) == 0) + return(1); + return(0); +} + +int +insn_match_insert(struct insn_match **m_head, ipfw_insn *cmd, struct ip_fw *rule) +{ + struct insn_match *m, *new_m; + + new_m = safe_calloc(1, sizeof(struct insn_match)); + new_m->cmd = cmd; + new_m->rule = rule; + + if (!*m_head) { + *m_head = new_m; + return (0); + } + + for (m = *m_head; m; m = m->next) { + if (insn_eq(m->cmd, cmd)) { + /* preserve first element in list */ + new_m->next_match = m->next_match; + m->next_match = new_m; + m->match_count++; + printf("m->cmd %d: count = %d\n", cmd->opcode, m->match_count); + return(1); + } + } + new_m->list_size = (*m_head)->list_size + 1; + (*m_head)->list_size = 0; + new_m->next = *m_head; + *m_head = new_m; + return(0); +} + +int +insn_match_cmp(const void *_a, const void *_b) +{ + struct insn_match *a[2] = { + *((struct insn_match **) _a), + *((struct insn_match **) _b), + }; + int i; + + if (a[0] == NULL) + return (a[1] == NULL ? 0 : 1); + if (a[1] == NULL) + return -1; + for (i = 0; i < 2; i++) { + struct insn_match *m; + int min_r, max_r; + + if (a[i]->rank || a[i]->match_count == 0) + continue; + for (m = a[i], min_r = max_r = m->rule->rulenum; m; m = m->next_match) + if (m->rule->rulenum < min_r) + min_r = m->rule->rulenum; + else if (m->rule->rulenum > max_r) + max_r = m->rule->rulenum; + printf("rank %d: match_count: %d, dist: %d\n", a[i]->cmd->opcode, a[i]->match_count, max_r - min_r); + a[i]->rank = ((a[i]->match_count & 0x7fff) << 16) - (max_r - min_r); + } + return a[1]->rank - a[0]->rank; + +} + +void +ipfw_optimize(int argc, char **argv) +{ + struct ip_fw **rules; + struct insn_match **cmds, **cmds_sort; + int c, i; + + if (co.test_only) { + fprintf(stderr, "Testing only, optimization disabled\n"); + return; + } + + cmds = (struct insn_match**) safe_calloc(O_LAST_OPCODE, sizeof(void*)); + + rules = get_rules_cached(); + for (i = 0; rules[i]; i++) { + for (c = 0; c < rules[i]->cmd_len; c++) { + int match; + + ipfw_insn *cmd = &rules[i]->cmd[c]; + match = insn_match_insert(&cmds[cmd->opcode], cmd, rules[i]); + if (match) + printf("rule %d: op_code %d; match = %d\n", rules[i]->rulenum, cmd->opcode, match); + } + } + + for (c = 0, i = 0; i < O_LAST_OPCODE; i++) { + if (!cmds[i]) + continue; + if (cmds[i]->list_size) { + printf("list size: %d; opcode %d\n", cmds[i]->list_size, cmds[i]->cmd->opcode); + } + c += 1 + cmds[i]->list_size; + } + + cmds_sort = (struct insn_match**) safe_calloc(c, sizeof(void*)); + for (c = 0, i = 0; i < O_LAST_OPCODE; i++) { + struct insn_match *cmd; + + if (!cmds[i]) + continue; + for (cmd = cmds[i]; cmd; cmd = cmd->next) + cmds_sort[c++] = cmd; + } + + qsort(cmds_sort, c, sizeof(void*), insn_match_cmp); + for (i = 0; i < c && cmds_sort[i]->rank; i++) { + printf("sorted: %d; match_count %d; rank %d\n", cmds_sort[i]->cmd->opcode, cmds_sort[i]->match_count, cmds_sort[i]->rank); + } + c = i; + + free(cmds); + free(cmds_sort); +} + + static int lookup_host (char *host, struct in_addr *ipaddr) { ==== //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.h#3 (text+ko) ==== @@ -245,6 +245,7 @@ void ipfw_flush(int force); void ipfw_zero(int ac, char *av[], int optname); void ipfw_list(int ac, char *av[], int show_counters); +void ipfw_optimize(int ac, char *av[]); /* altq.c */ void altq_set_enabled(int enabled); ==== //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/main.c#3 (text+ko) ==== @@ -350,6 +350,8 @@ ipfw_sysctl_handler(ac, av, 1); else if (_substrcmp(*av, "disable") == 0) ipfw_sysctl_handler(ac, av, 0); + else if (_substrcmp(*av, "optimize") == 0) + ipfw_optimize(ac, av); else try_next = 1; }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200906071419.n57EJbes015414>