PERFORCE change 164841 for review
Tatsiana Elavaya
tsel at FreeBSD.org
Mon Jun 22 09:54:57 UTC 2009
http://perforce.freebsd.org/chv.cgi?CH=164841
Change 164841 by tsel at tsel_mz on 2009/06/22 09:54:28
Work in progress on switching to per rule optimization instruction
Introduce mergesort for linked lists algorithm
Sort instructions before adding to rule, use listsort to sort groups
Fix buffer release bug (noted by Fabio Checconi)
Do not store alias as first action command, it's supposed to be log action
Affected files ...
.. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#7 edit
.. //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/listsort.h#1 add
.. //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw2.c#4 edit
Differences ...
==== //depot/projects/soc2009/tsel_ipfw/sbin/ipfw/ipfw2.c#7 (text+ko) ====
@@ -53,6 +53,8 @@
#include <netinet/tcp.h>
#include <arpa/inet.h>
+#include "listsort.h"
+
struct cmdline_opts co; /* global options */
int resvd_set_number = RESVD_SET;
@@ -2034,8 +2036,11 @@
#undef NEXT
}
+LIST_HEAD(insn_match_rule_head, insn_match);
+LIST_HEAD(insn_match_group_head, insn_match_group);
+
struct insn_match_rule {
- LIST_HEAD(_match_rule, insn_match) rule_head;
+ struct insn_match_rule_head rule_head;
struct ip_fw *rule;
};
@@ -2055,11 +2060,15 @@
int label;
};
-LIST_HEAD(insn_match_group_head, insn_match_group);
+static LIST_MERGESORT_GENERATE(insn_match_group_sort, insn_match_group_head, insn_match_group, group_entries);
+
+static LIST_MERGESORT_GENERATE(insn_match_rule_cmd_sort, insn_match_rule_head, insn_match, rule_entries);
int
insn_eq(ipfw_insn *a, ipfw_insn *b)
{
+ if ((a->len | b->len) & (F_NOT | F_OR))
+ return 0;
if (F_LEN(a) != F_LEN(b) || a->arg1 != b->arg1 || a->opcode != b->opcode)
return 0;
switch (a->opcode) {
@@ -2130,7 +2139,7 @@
int
insn_match_insert(struct insn_match_group_head *group_head, ipfw_insn *cmd,
- struct insn_match_rule *rule, int *group_count)
+ struct insn_match_rule *rule)
{
struct insn_match_group *g;
struct insn_match *m, *new_m;
@@ -2154,7 +2163,6 @@
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;
}
@@ -2168,13 +2176,10 @@
free(m);
}
-int
-insn_match_group_cmp(const void *_a, const void *_b)
+static int
+insn_match_group_cmp(struct insn_match_group *_a, struct insn_match_group *_b)
{
- struct insn_match_group *a[2] = {
- *((struct insn_match_group **) _a),
- *((struct insn_match_group **) _b),
- };
+ struct insn_match_group *a[2] = { _a, _b };
int i;
if (a[0] == NULL)
@@ -2206,6 +2211,42 @@
}
+static int
+insn_match_rule_cmd_cmp(struct insn_match *a, struct insn_match *b)
+{
+ return b->group->rank - a->group->rank;
+}
+
+static int
+optimization_filter_groups(struct insn_match_group_head *head)
+{
+ struct insn_match_group *g, *g_tmp;
+ int labels_max, group_count;
+
+ group_count = sizeof(labels_max);
+ if (sysctlbyname("net.inet.ip.fw.optimization_buf_max",
+ &labels_max, &group_count, NULL, 0) == -1) {
+ errx(EX_DATAERR, "optimization not supported");
+ }
+ labels_max *= 8;
+
+ group_count = 0;
+ LIST_FOREACH_SAFE(g, head, group_entries, g_tmp) {
+ if (group_count >= labels_max || !g->rank) {
+ while (!LIST_EMPTY(&g->match_head)) {
+ insn_match_remove(LIST_FIRST(&g->match_head));
+ }
+ LIST_REMOVE(g, group_entries);
+ continue;
+ }
+ g->label = group_count++;
+ printf("sorted: %d; opcode %d; match_count %d; rank %d\n",
+ g->label, LIST_FIRST(&g->match_head)->cmd->opcode,
+ g->match_count, g->rank);
+ }
+ return group_count;
+}
+
static void
optimization_setup(int enable, int labels)
{
@@ -2221,33 +2262,33 @@
NULL, 0, &enable, sizeof(enable)) == -1) {
errx(EX_DATAERR, "optimization not supported");
}
-
}
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_group_head groups_opcode[O_LAST_OPCODE];
+ struct insn_match_group_head groups;
struct insn_match_rule *match_rules;
struct ip_fw **rules;
struct ip_fw *orule;
- int c, i, group_count, rules_count, labels_max;
+ int i, group_count, rules_count;
if (co.test_only) {
fprintf(stderr, "Testing only, optimization disabled\n");
return;
}
+ LIST_INIT(&groups);
for (i = 0; i < O_LAST_OPCODE; i++) {
- LIST_INIT(&groups[i]);
+ LIST_INIT(&groups_opcode[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++) {
+ for (i = 0; i < rules_count; i++) {
ipfw_insn *cmd;
int l;
@@ -2267,52 +2308,98 @@
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);
+ insn_match_insert(&groups_opcode[cmd->opcode], cmd, &match_rules[i]);
cmd += F_LEN(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;
+ for (i = 0; i < O_LAST_OPCODE; i++) {
+ while(!LIST_EMPTY(&groups_opcode[i])) {
+ struct insn_match_group *g = LIST_FIRST(&groups_opcode[i]);
- LIST_FOREACH(g, &groups[i], group_entries) {
- groups_sort[c++] = g;
+ LIST_REMOVE(g, group_entries);
+ LIST_INSERT_HEAD(&groups, g, group_entries);
}
}
- i = sizeof(labels_max);
- if (sysctlbyname("net.inet.ip.fw.optimization_buf_max",
- &labels_max, &i, NULL, 0) == -1) {
- errx(EX_DATAERR, "optimization not supported");
- }
- labels_max *= 8;
+ insn_match_group_sort(&groups, insn_match_group_cmp);
+
+ group_count = optimization_filter_groups(&groups);
+
+ optimization_setup(0, 0);
+
+ orule = (struct ip_fw*)safe_calloc(1, sizeof(struct ip_fw) + 255*4);
+ for (i = 0; rules[i]; i++) {
+ ipfw_insn *cmd, *rcmd;
+ struct insn_match *m;
+ ipfw_insn_u32 *optimize_cmd;
+ int l;
+
+ if (LIST_EMPTY(&match_rules[i].rule_head))
+ continue;
+
+ printf("rule %d; before sort: ", rules[i]->rulenum);
+ LIST_FOREACH(m, &match_rules[i].rule_head, rule_entries) {
+ printf("optimize %d:%d; ", m->cmd->opcode, m->group->rank);
+ }
+ printf("\n");
+ insn_match_rule_cmd_sort(&match_rules[i].rule_head, insn_match_rule_cmd_cmp);
+ printf("rule %d; after sort: ", rules[i]->rulenum);
+ LIST_FOREACH(m, &match_rules[i].rule_head, rule_entries) {
+ printf("optimize %d:%d; ", m->cmd->opcode, m->group->rank);
+ }
+ printf("\n");
+
+ memcpy(orule, rules[i], sizeof(struct ip_fw) - 4);
+ cmd = orule->cmd;
+ rcmd = rules[i]->cmd;
+ l = rules[i]->cmd_len;
- qsort(groups_sort, group_count, sizeof(void*), insn_match_group_cmp);
- for (i = 0; i < group_count && i < labels_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));
+ while ((rcmd->opcode == O_PROB || rcmd->opcode == O_PROBE_STATE) && l > 0) {
+ memcpy(cmd, rcmd, F_LEN(rcmd) * 4);
+ cmd += F_LEN(rcmd);
+ l -= F_LEN(rcmd);
}
- }
- group_count = c;
+
+ // FIXME
+ optimize_cmd = (ipfw_insn_u32 *) cmd;
+ optimize_cmd->o.len = F_INSN_SIZE(ipfw_insn_u32);
+ optimize_cmd->o.opcode = O_OPTIMIZE;
+ optimize_cmd->o.arg1 = 0;
+ optimize_cmd->d[0] = 0;
+ cmd += optimize_cmd->o.len;
+ orule->cmd_len += optimize_cmd->o.len;
+ orule->act_ofs += optimize_cmd->o.len;
- optimization_setup(0, 0);
+ LIST_FOREACH(m, &match_rules[i].rule_head, rule_entries) {
+ memcpy(cmd, m->cmd, F_LEN(m->cmd) * 4);
+ cmd += F_LEN(m->cmd);
+ l -= F_LEN(m->cmd);
+ }
- 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;
+ while (l > 0) {
+ int skip = 0;
- memcpy(orule, rules[i], RULESIZE(rules[i]));
+ LIST_FOREACH(m, &match_rules[i].rule_head, rule_entries) {
+ if (rcmd == m->cmd) {
+ skip = 1;
+ break;
+ }
+ }
+ if (!skip) {
+ memcpy(cmd, rcmd, F_LEN(rcmd) * 4);
+ cmd += F_LEN(rcmd);
+ l -= F_LEN(rcmd);
+ }
+ rcmd += F_LEN(rcmd);
+ }
+ printf(" insn original: ");
+ show_ipfw(rules[i], 0, 0);
+ printf("insn reordered: ");
+ show_ipfw(orule, 0, 0);
+ /*
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);
@@ -2334,19 +2421,17 @@
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);
+ l = orule->rulenum & 0xffff;
+ if (do_cmd(IP_FW_DEL, &l, sizeof(l)))
+ 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);
- }
+ l = RULESIZE(orule);
+ if (do_cmd(IP_FW_ADD, orule, (uintptr_t)&l))
+ errx(EX_DATAERR, "rule %u: setsockopt(IP_FW_ADD)", orule->rulenum);
+ if (co.verbose)
+ show_ipfw(orule, 0, 0);
}
optimization_setup(1, group_count);
@@ -2359,10 +2444,10 @@
if (!inet_aton(host, ipaddr)) {
if ((he = gethostbyname(host)) == NULL)
- return -1;
+ return(-1);
*ipaddr = *(struct in_addr *)he->h_addr_list[0];
}
- return 0;
+ return(0);
}
/*
@@ -3020,8 +3105,9 @@
/*
* various flags used to record that we entered some fields.
*/
+ ipfw_insn_alias alias_cmd;
ipfw_insn *have_state = NULL; /* check-state or keep-state */
- ipfw_insn *have_log = NULL, *have_altq = NULL, *have_tag = NULL;
+ ipfw_insn *have_log = NULL, *have_altq = NULL, *have_tag = NULL, *have_alias = NULL;
size_t len;
int i;
@@ -3053,7 +3139,6 @@
/* [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");
for (i = 0; isdigit(av[1][i]) || av[1][i] == '+' || av[1][i] == '-'; i++) { ; }
@@ -3062,11 +3147,11 @@
alias_rule = alias_lookup_rulenum(av[1]);
if (alias_rule > 0)
errx(EX_DATAERR, "rule %d already has alias %s", alias_rule, av[1]);
- 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);
+ 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);
+ have_alias = (ipfw_insn *) &alias_cmd;
}
/* [set N] -- set number (0..RESVD_SET), optional */
@@ -4024,6 +4109,11 @@
bcopy(have_tag, dst, i * sizeof(uint32_t));
dst += i;
}
+ if (have_alias) {
+ i = F_LEN(have_alias);
+ bcopy(have_alias, dst, i * sizeof(uint32_t));
+ dst += i;
+ }
/*
* copy all other actions
*/
==== //depot/projects/soc2009/tsel_ipfw/sys/netinet/ip_fw2.c#4 (text+ko) ====
@@ -2216,7 +2216,7 @@
mask = 1 << (*ind - 1);
do {
use = atomic_load_acq_32(&V_optimization_buf_use);
- } while (atomic_cmpset_32(&V_optimization_buf_use, use, use | mask) == 0);
+ } while (atomic_cmpset_32(&V_optimization_buf_use, use, use & ~mask) == 0);
*ind = 0;
}
More information about the p4-projects
mailing list