PERFORCE change 164163 for review
Tatsiana Elavaya
tsel at FreeBSD.org
Fri Jun 12 10:35:06 UTC 2009
http://perforce.freebsd.org/chv.cgi?CH=164163
Change 164163 by tsel at tsel_mz on 2009/06/12 10:34:47
Add kernel support for optimization (by inserting O_OPTMIZE instruction before real one)
Use O_ALIAS instruction to specify rule alias
Use list implementation from sys/queue.h
Affected files ...
.. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#5 edit
.. //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw.h#3 edit
.. //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw2.c#2 edit
Differences ...
==== //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#5 (text+ko) ====
@@ -24,6 +24,7 @@
#include <sys/socket.h>
#include <sys/sockio.h>
#include <sys/sysctl.h>
+#include <sys/queue.h>
#include "ipfw2.h"
@@ -470,19 +471,20 @@
}
static struct ip_fw**
-get_rules_cached(void)
+get_rules_cached(int *len)
{
static struct ip_fw *raw_rules = NULL;
static struct ip_fw **rules = NULL;
- int i, rules_len;
+ static rules_len = 0;
+ int i, sz;
if (raw_rules == NULL || rules == NULL) {
char *r, *end;
- 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*));
+ raw_rules = (struct ip_fw*) ipfw_get_all(IP_FW_GET, &sz);
+ rules = safe_calloc(sz / sizeof(struct ip_fw) + 1, sizeof(void*));
r = (char*)raw_rules;
- end = r + rules_len;
+ end = r + sz;
for (i = 0; ; i++) {
if (r + RULESIZE(r) > end) {
rules[i] = NULL;
@@ -491,20 +493,39 @@
rules[i] = (struct ip_fw *)r;
r += RULESIZE(r);
}
+ rules_len = i;
}
+ if (len)
+ *len = rules_len;
return rules;
}
+static char*
+get_rule_alias(struct ip_fw *rule)
+{
+ ipfw_insn *cmd;
+ int l;
+
+ for (l = rule->cmd_len - rule->act_ofs, cmd = ACTION_PTR(rule);
+ l > 0 ; l -= F_LEN(cmd), cmd += F_LEN(cmd)) {
+ if (cmd->opcode == O_ALIAS)
+ return ((ipfw_insn_alias*) cmd)->alias;
+ }
+ return NULL;
+}
+
static int
alias_lookup_rulenum(const char *alias)
{
struct ip_fw **rules;
+ char *rule_alias;
int i;
- rules = get_rules_cached();
+ rules = get_rules_cached(NULL);
for (i = 0; rules[i]; i++) {
- if (!strcmp(rules[i]->alias, alias))
+ rule_alias = get_rule_alias(rules[i]);
+ if (rule_alias && !strcmp(rule_alias, alias))
return rules[i]->rulenum;
}
return -1;
@@ -516,10 +537,10 @@
struct ip_fw **rules;
int i;
- rules = get_rules_cached();
+ rules = get_rules_cached(NULL);
for (i = 0; rules[i]; i++) {
if (rules[i]->rulenum == rulenum)
- return rules[i]->alias[0] ? rules[i]->alias : NULL;
+ return get_rule_alias(rules[i]);
}
return NULL;
}
@@ -1005,6 +1026,7 @@
int l;
ipfw_insn *cmd, *tagptr = NULL;
const char *comment = NULL; /* ptr to comment if we have one */
+ const char *alias = NULL; /* ptr to alias if we have one */
int proto = 0; /* default */
int flags = 0; /* prerequisites */
ipfw_insn_log *logptr = NULL; /* set if we find an O_LOG */
@@ -1048,8 +1070,9 @@
}
}
- if (rule->alias[0])
- printf("alias %s ", rule->alias);
+ alias = get_rule_alias(rule);
+ if (alias)
+ printf("alias %s ", alias);
if (co.show_sets)
printf("set %d ", rule->set);
@@ -1174,6 +1197,9 @@
PRINT_UINT_ARG("setfib ", cmd->arg1);
break;
+ case O_ALIAS: /* O_ALIAS is printed first */
+ break;
+
case O_REASS:
printf("reass");
break;
@@ -1590,6 +1616,11 @@
O_TAGGED);
break;
+ case O_OPTIMIZE:
+ if (co.verbose)
+ printf(" [optimize %d %u]", cmd->arg1, ((ipfw_insn_u32*)cmd)->d[0]);
+ break;
+
default:
printf(" [opcode %d len %d]",
cmd->opcode, cmd->len);
@@ -1798,20 +1829,6 @@
}
}
-static void
-ipfw_list_aliases(void *data, uint nbytes, int ac, char *av[])
-{
- struct ip_fw *rules;
- int len, i;
-
- rules = (struct ip_fw*) data;
- len = nbytes / sizeof(struct ip_fw);
- for (i = 0; i < len; i++) {
- if (rules[i].alias[0] != '\0')
- printf("%-5d %s\n", rules[i].rulenum, rules[i].alias);
- }
-}
-
void
ipfw_list(int ac, char *av[], int show_counters)
{
@@ -1848,7 +1865,13 @@
}
if (ac && !strcmp(*av, "alias")) {
- ipfw_list_aliases(data, nbytes, ac, av);
+ char *alias;
+
+ for (r = data; r->rulenum < IPFW_DEFAULT_RULE; r = NEXT(r)) {
+ alias = get_rule_alias(r);
+ if (alias)
+ printf("%-5d %s\n", r, alias);
+ }
ac--; av++;
goto done;
}
@@ -2002,16 +2025,29 @@
#undef NEXT
}
+struct insn_match_rule {
+ LIST_HEAD(_match_rule, insn_match) rule_head;
+ struct ip_fw *rule;
+};
+
struct insn_match {
+ LIST_ENTRY(insn_match) match_entries;
+ LIST_ENTRY(insn_match) rule_entries;
+ struct insn_match_rule *match_rule;
ipfw_insn *cmd;
+ struct insn_match_group *group;
+};
+
+struct insn_match_group {
+ LIST_ENTRY(insn_match_group) group_entries;
+ LIST_HEAD(_match_head, insn_match) match_head;
int match_count;
- int list_size;
- struct insn_match *next;
- struct insn_match *next_match;
- struct ip_fw *rule;
int rank;
+ int label;
};
+LIST_HEAD(insn_match_group_head, insn_match_group);
+
int
insn_eq(ipfw_insn *a, ipfw_insn *b)
{
@@ -2078,48 +2114,57 @@
}
if (F_LEN(a) != F_LEN(b))
return(0);
- if (memcmp(a, b, F_LEN(a)) == 0)
+ if (memcmp(a, b, F_LEN(a) * 4) == 0)
return(1);
return(0);
}
int
-insn_match_insert(struct insn_match **m_head, ipfw_insn *cmd, struct ip_fw *rule)
+insn_match_insert(struct insn_match_group_head *group_head, ipfw_insn *cmd,
+ struct insn_match_rule *rule, int *group_count)
{
+ struct insn_match_group *g;
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);
- }
+ new_m->match_rule = rule;
+ LIST_INSERT_HEAD(&rule->rule_head, new_m, rule_entries);
- for (m = *m_head; m; m = m->next) {
+ LIST_FOREACH(g, group_head, group_entries) {
+ m = LIST_FIRST(&g->match_head);
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);
+ new_m->group = g;
+ LIST_INSERT_HEAD(&g->match_head, new_m, match_entries);
+ g->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;
+
+ g = safe_calloc(1, sizeof(struct insn_match_group));
+ new_m->group = g;
+ LIST_INSERT_HEAD(&g->match_head, new_m, match_entries);
+ LIST_INSERT_HEAD(group_head, g, group_entries);
+ (*group_count)++;
+
return(0);
}
+void
+insn_match_remove(struct insn_match *m)
+{
+ // printf("remove match: cmd = %d, rule = %d\n", m->cmd->opcode, m->match_rule->rule->rulenum);
+ LIST_REMOVE(m, rule_entries);
+ LIST_REMOVE(m, match_entries);
+ free(m);
+}
+
int
-insn_match_cmp(const void *_a, const void *_b)
+insn_match_group_cmp(const void *_a, const void *_b)
{
- struct insn_match *a[2] = {
- *((struct insn_match **) _a),
- *((struct insn_match **) _b),
+ struct insn_match_group *a[2] = {
+ *((struct insn_match_group **) _a),
+ *((struct insn_match_group **) _b),
};
int i;
@@ -2133,13 +2178,20 @@
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);
+ min_r = max_r = LIST_FIRST(&a[i]->match_head)->match_rule->rule->rulenum;
+ LIST_FOREACH(m, &a[i]->match_head, match_entries) {
+ int rulenum = m->match_rule->rule->rulenum;
+ if (rulenum < min_r)
+ min_r = rulenum;
+ else if (rulenum > max_r)
+ max_r = rulenum;
+ }
a[i]->rank = ((a[i]->match_count & 0x7fff) << 16) - (max_r - min_r);
+ /*
+ printf("rank %d: match_count: %d, dist: %d\n",
+ LIST_FIRST(&a[i]->match_head)->cmd->opcode,
+ a[i]->match_count, max_r - min_r);
+ */
}
return a[1]->rank - a[0]->rank;
@@ -2148,59 +2200,119 @@
void
ipfw_optimize(int argc, char **argv)
{
+ struct insn_match_group_head groups[O_LAST_OPCODE];
+ struct insn_match_group **groups_sort;
+ struct insn_match_rule *match_rules;
struct ip_fw **rules;
- struct insn_match **cmds, **cmds_sort;
- int c, i;
+ struct ip_fw *orule;
+ int c, i, group_count, rules_count;
if (co.test_only) {
fprintf(stderr, "Testing only, optimization disabled\n");
return;
}
- cmds = (struct insn_match**) safe_calloc(O_LAST_OPCODE, sizeof(void*));
+ for (i = 0; i < O_LAST_OPCODE; i++) {
+ LIST_INIT(&groups[i]);
+ }
+
+ rules = get_rules_cached(&rules_count);
+ match_rules = safe_calloc(rules_count, sizeof(struct insn_match_rule));
+
+ for (i = 0, group_count = 0; i < rules_count; i++) {
+ ipfw_insn *cmd;
+ int l;
+
- rules = get_rules_cached();
- for (i = 0; rules[i]; i++) {
- for (c = 0; c < rules[i]->cmd_len; c++) {
- int match;
+ if (i > 0 && rules[i]->rulenum == rules[i - 1]->rulenum)
+ errx(EX_DATAERR, "rule number is not unique: %d", rules[i]->rulenum);
- 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);
- }
- }
+ l = RULESIZE(rules[i]);
+ rules[i] = memcpy(safe_calloc(1, l), rules[i], l);
+ match_rules[i].rule = rules[i];
- 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);
+ for (l = rules[i]->cmd_len, cmd = rules[i]->cmd; l > 0;) {
+ l -= F_LEN(cmd);
+ /* remove old optimization labels */
+ if (cmd->opcode == O_OPTIMIZE) {
+ rules[i]->cmd_len -= F_LEN(cmd);
+ rules[i]->act_ofs -= F_LEN(cmd);
+ memcpy(cmd, cmd + F_LEN(cmd), l * 4);
+ } else {
+ insn_match_insert(&groups[cmd->opcode], cmd, &match_rules[i], &group_count);
+ cmd += F_LEN(cmd);
+ }
}
- 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;
+ groups_sort = (struct insn_match_group**) safe_calloc(group_count, sizeof(void*));
+ for (i = 0, c = 0; i < O_LAST_OPCODE; i++) {
+ struct insn_match_group *g;
- if (!cmds[i])
- continue;
- for (cmd = cmds[i]; cmd; cmd = cmd->next)
- cmds_sort[c++] = cmd;
+ LIST_FOREACH(g, &groups[i], group_entries) {
+ groups_sort[c++] = g;
+ }
}
- 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);
+ qsort(groups_sort, group_count, sizeof(void*), insn_match_group_cmp);
+ for (i = 0; i < group_count && i < IPFW_OPTIMIZE_LABEL_MAX && groups_sort[i]->rank; i++) {
+ struct insn_match *m = LIST_FIRST(&groups_sort[i]->match_head);
+ groups_sort[i]->label = i;
+ printf("sorted: %d; opcode %d; match_count %d; rank %d\n",
+ groups_sort[i]->label,
+ m->cmd->opcode, groups_sort[i]->match_count, groups_sort[i]->rank);
}
c = i;
+ for (; i < group_count; i++) {
+ while (!LIST_EMPTY(&groups_sort[i]->match_head)) {
+ insn_match_remove(LIST_FIRST(&groups_sort[i]->match_head));
+ }
+ }
+ group_count = c;
+
+ orule = (struct ip_fw*)safe_calloc(1, sizeof(struct ip_fw) + 255*4);
+ for (i = 0; rules[i]; i++) {
+ struct insn_match *m, *m_tmp;
+
+ memcpy(orule, rules[i], RULESIZE(rules[i]));
+
+ LIST_FOREACH_SAFE(m, &match_rules[i].rule_head, rule_entries, m_tmp) {
+ ipfw_insn_u32 optimize_cmd;
+ int cmd_offset = ((int32_t*) m->cmd) - ((int32_t*) rules[i]->cmd);
+
+ optimize_cmd.o.len = F_INSN_SIZE(ipfw_insn_u32);
+ optimize_cmd.o.opcode = O_OPTIMIZE;
+ optimize_cmd.o.arg1 = m->cmd->opcode;
+ optimize_cmd.d[0] = m->group->label;
- free(cmds);
- free(cmds_sort);
+ if (cmd_offset >= orule->act_ofs)
+ errx(EX_DATAERR, "optimizing action: rule %d\n", orule->rulenum);
+ if (orule->cmd_len + F_LEN(&optimize_cmd.o) > 255)
+ errx(EX_DATAERR, "option list is too long: rule %d", orule->rulenum);
+ memcpy(orule->cmd + cmd_offset + F_LEN(&optimize_cmd.o),
+ orule->cmd + cmd_offset,
+ (orule->cmd_len - cmd_offset) * 4);
+ memcpy(orule->cmd + cmd_offset, &optimize_cmd, F_LEN(&optimize_cmd.o) * 4);
+ orule->cmd_len += F_LEN(&optimize_cmd.o);
+ orule->act_ofs += F_LEN(&optimize_cmd.o);
+ // printf("rule %d; cmd %d; offset %d\n", orule->rulenum, m->cmd->opcode, cmd_offset);
+ }
+ if (!LIST_EMPTY(&match_rules[i].rule_head)) {
+ int x;
+
+ x = orule->rulenum & 0xffff;
+ if (do_cmd(IP_FW_DEL, &x, sizeof(x)))
+ errx(EX_DATAERR, "rule %u: setsockopt(IP_FW_DEL)", orule->rulenum);
+
+ x = RULESIZE(orule);
+ if (do_cmd(IP_FW_ADD, orule, (uintptr_t)&x))
+ errx(EX_DATAERR, "rule %u: setsockopt(IP_FW_ADD)", orule->rulenum);
+ if (co.verbose)
+ show_ipfw(orule, 0, 0);
+ }
+ }
}
-
static int
lookup_host (char *host, struct in_addr *ipaddr)
{
@@ -2902,13 +3014,17 @@
/* [alias ALIAS] */
if (ac > 1 && _substrcmp(*av, "alias") == 0) {
int alias_rule;
+ ipfw_insn_alias *alias_cmd = (ipfw_insn_alias *) action;
NEED1("missing alias name");
alias_rule = alias_lookup_rulenum(av[1]);
if (alias_rule > 0)
errx(EX_DATAERR, "rule %d already has alias %s", alias_rule, av[1]);
- strlcpy(rule->alias, av[1], IPFW_ALIAS_NAME_SIZE);
+ alias_cmd->o.opcode = O_ALIAS;
+ alias_cmd->o.len = F_INSN_SIZE(ipfw_insn_alias);
+ strlcpy(alias_cmd->alias, av[1], IPFW_ALIAS_NAME_SIZE);
av += 2; ac -= 2;
+ action = next_cmd(action);
}
/* [set N] -- set number (0..RESVD_SET), optional */
==== //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw.h#3 (text+ko) ====
@@ -42,6 +42,8 @@
*/
#define IPFW_TABLES_MAX 128
+#define IPFW_OPTIMIZE_LABEL_MAX 128
+
/*
* The kernel representation of ipfw rules is made of a list of
* 'instructions' (for all practical purposes equivalent to BPF
@@ -179,6 +181,9 @@
O_SETFIB, /* arg1=FIB number */
O_FIB, /* arg1=FIB desired fib number */
+ O_ALIAS,
+ O_OPTIMIZE, /* u32 position in bitset */
+
O_LAST_OPCODE /* not an opcode! */
};
@@ -305,6 +310,15 @@
} ipfw_insn_altq;
/*
+ * This is used to store rule alias.
+ */
+typedef struct _ipfw_insn_alias {
+ ipfw_insn o;
+#define IPFW_ALIAS_NAME_SIZE (4*6)
+ char alias[IPFW_ALIAS_NAME_SIZE];
+} ipfw_insn_alias;
+
+/*
* This is used for limit rules.
*/
typedef struct _ipfw_insn_limit {
@@ -421,8 +435,6 @@
*/
} ipfw_insn_icmp6;
-#define IPFW_ALIAS_NAME_SIZE 32
-
/*
* Here we have the structure representing an ipfw rule.
*
@@ -466,7 +478,6 @@
u_int64_t pcnt; /* Packet counter */
u_int64_t bcnt; /* Byte counter */
u_int32_t timestamp; /* tv_sec of last match */
- char alias[IPFW_ALIAS_NAME_SIZE];
ipfw_insn cmd[1]; /* storage for commands */
};
==== //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw2.c#2 (text+ko) ====
@@ -917,6 +917,10 @@
case O_REASS:
action = "Reass";
break;
+ case O_ALIAS:
+ snprintf(SNPARGS(action2, 0), "Alias %s",
+ ((ipfw_insn_alias *)cmd)->alias);
+ break;
default:
action = "UNKNOWN";
break;
@@ -2262,6 +2266,10 @@
/* end of ipv6 variables */
int is_ipv4 = 0;
+#define GET_OPTIMIZE_LABEL(a) optimize_state[(a) / 32] & (1 << ((a) % 32))
+#define SET_OPTIMIZE_LABEL(a) optimize_state[(a) / 32] |= (1 << ((a) % 32))
+ uint32_t optimize_state[IPFW_OPTIMIZE_LABEL_MAX/32];
+
if (m->m_flags & M_SKIP_FIREWALL)
return (IP_FW_PASS); /* accept */
@@ -2555,6 +2563,9 @@
m_tag_delete(m, mtag);
}
+ /* reset optimization state */
+ bzero(optimize_state, sizeof(optimize_state));
+
/*
* Now scan the rules, and parse microinstructions for each rule.
*/
@@ -2562,6 +2573,7 @@
ipfw_insn *cmd;
uint32_t tablearg = 0;
int l, cmdlen, skip_or; /* skip rest of OR block */
+ int optimize_match = 0;
again:
if (V_set_disable & (1 << f->set) )
@@ -2594,7 +2606,11 @@
}
match = 0; /* set to 1 if we succeed */
- switch (cmd->opcode) {
+ if (optimize_match > 0) {
+ printf("IPFW: optimize %d %d\n", cmd->opcode, optimize_match - 1);
+ optimize_match = 0;
+ match = !(cmd->len & F_NOT);
+ } else switch (cmd->opcode) {
/*
* The first set of opcodes compares the packet's
* fields with some pattern, setting 'match' if a
@@ -3138,6 +3154,15 @@
}
break;
}
+ case O_OPTIMIZE: {
+ int label = ((ipfw_insn_u32 *)cmd)->d[0];
+
+ if (GET_OPTIMIZE_LABEL(label))
+ optimize_match = label + 1;
+ else
+ optimize_match = -(label + 1);
+ continue;
+ }
/*
* The second set of opcodes represents 'actions',
@@ -3382,6 +3407,9 @@
} else
retval = IP_FW_DENY;
goto done;
+
+ case O_ALIAS:
+ break;
}
case O_REASS: {
@@ -3441,9 +3469,16 @@
match = !match;
if (match) {
+ if (optimize_match < 0) {
+ optimize_match = -optimize_match - 1;
+ SET_OPTIMIZE_LABEL(optimize_match);
+ printf("IPFW: set optimize match %d %d\n", cmd->opcode, optimize_match);
+ optimize_match = 0;
+ }
if (cmd->len & F_OR)
skip_or = 1;
} else {
+ optimize_match = 0;
if (!(cmd->len & F_OR)) /* not an OR block, */
break; /* try next rule */
}
@@ -4034,6 +4069,11 @@
goto bad_size;
break;
+ case O_OPTIMIZE:
+ if (cmdlen < F_INSN_SIZE(ipfw_insn_u32))
+ goto bad_size;
+ break;
+
case O_ALTQ:
if (cmdlen != F_INSN_SIZE(ipfw_insn_altq))
goto bad_size;
@@ -4101,6 +4141,10 @@
return EINVAL;
}
break;
+ case O_ALIAS:
+ if (cmdlen != F_INSN_SIZE(ipfw_insn_alias))
+ goto bad_size;
+ break;
#ifdef INET6
case O_IP6_SRC:
case O_IP6_DST:
More information about the p4-projects
mailing list