From owner-p4-projects@FreeBSD.ORG Mon Jun 22 09:54:56 2009 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 28C2B1065677; Mon, 22 Jun 2009 09:54:56 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id DAC711065675 for ; Mon, 22 Jun 2009 09:54:55 +0000 (UTC) (envelope-from tsel@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [IPv6:2001:4f8:fff6::29]) by mx1.freebsd.org (Postfix) with ESMTP id C7D158FC17 for ; Mon, 22 Jun 2009 09:54:55 +0000 (UTC) (envelope-from tsel@FreeBSD.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.3/8.14.3) with ESMTP id n5M9stbg079131 for ; Mon, 22 Jun 2009 09:54:55 GMT (envelope-from tsel@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.3/8.14.3/Submit) id n5M9stcs079129 for perforce@freebsd.org; Mon, 22 Jun 2009 09:54:55 GMT (envelope-from tsel@FreeBSD.org) Date: Mon, 22 Jun 2009 09:54:55 GMT Message-Id: <200906220954.n5M9stcs079129@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to tsel@FreeBSD.org using -f From: Tatsiana Elavaya To: Perforce Change Reviews Cc: Subject: PERFORCE change 164841 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 22 Jun 2009 09:54:57 -0000 http://perforce.freebsd.org/chv.cgi?CH=164841 Change 164841 by tsel@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 #include +#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; }