Date: Fri, 12 Jun 2009 10:35:05 GMT From: Tatsiana Elavaya <tsel@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 164163 for review Message-ID: <200906121035.n5CAZ55e047607@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=164163 Change 164163 by tsel@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:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200906121035.n5CAZ55e047607>