PERFORCE change 163713 for review
Tatsiana Elavaya
tsel at FreeBSD.org
Sun Jun 7 14:19:39 UTC 2009
http://perforce.freebsd.org/chv.cgi?CH=163713
Change 163713 by tsel at 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;
}
More information about the p4-projects
mailing list