From owner-svn-src-projects@FreeBSD.ORG Sun Aug 3 15:49:04 2014 Return-Path: Delivered-To: svn-src-projects@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 5640B82E for ; Sun, 3 Aug 2014 15:49:04 +0000 (UTC) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 35FB42D63 for ; Sun, 3 Aug 2014 15:49:04 +0000 (UTC) Received: from melifaro (uid 1268) (envelope-from melifaro@FreeBSD.org) id 5143 by svn.freebsd.org (DragonFly Mail Agent v0.9+); Sun, 03 Aug 2014 15:49:03 +0000 From: Alexander V. Chernikov Date: Sun, 3 Aug 2014 15:49:03 +0000 (UTC) To: src-committers@freebsd.org, svn-src-projects@freebsd.org Subject: svn commit: r269477 - projects/ipfw/sys/netpfil/ipfw X-SVN-Group: projects MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Message-Id: <53de59f0.5143.2b115813@svn.freebsd.org> X-BeenThere: svn-src-projects@freebsd.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: "SVN commit messages for the src " projects" tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 03 Aug 2014 15:49:04 -0000 Author: melifaro Date: Sun Aug 3 15:49:03 2014 New Revision: 269477 URL: http://svnweb.freebsd.org/changeset/base/269477 Log: Implement O(1) skipto using indexed array. This adds 512K (2 * sizeof(u32) * 65k) bytes to the memory footprint. This feature is optionaly and may be turned on in any time (however it starts immediately in this commit. This will be changed.) Modified: projects/ipfw/sys/netpfil/ipfw/ip_fw2.c projects/ipfw/sys/netpfil/ipfw/ip_fw_private.h projects/ipfw/sys/netpfil/ipfw/ip_fw_sockopt.c Modified: projects/ipfw/sys/netpfil/ipfw/ip_fw2.c ============================================================================== --- projects/ipfw/sys/netpfil/ipfw/ip_fw2.c Sun Aug 3 15:09:13 2014 (r269476) +++ projects/ipfw/sys/netpfil/ipfw/ip_fw2.c Sun Aug 3 15:49:03 2014 (r269477) @@ -816,7 +816,10 @@ jump_fast(struct ip_fw_chain *chain, str /* make sure we do not jump backward */ if (jump_backwards == 0 && i <= f->rulenum) i = f->rulenum + 1; - f_pos = ipfw_find_rule(chain, i, 0); + if (chain->idxmap != NULL) + f_pos = chain->idxmap[i]; + else + f_pos = ipfw_find_rule(chain, i, 0); /* update the cache */ if (num != IP_FW_TABLEARG) { f->next_rule = (void *)(uintptr_t)f_pos; @@ -2688,6 +2691,7 @@ vnet_ipfw_init(const void *unused) rule->cmd[0].opcode = default_to_accept ? O_ACCEPT : O_DENY; chain->default_rule = chain->map[0] = rule; chain->id = rule->id = 1; + ipfw_init_skipto_cache(chain); /* Pre-calculate rules length for legacy dump format */ chain->static_len = sizeof(struct ip_fw_rule0); @@ -2750,6 +2754,7 @@ vnet_ipfw_uninit(const void *unused) } if (chain->map) free(chain->map, M_IPFW); + ipfw_destroy_skipto_cache(chain); IPFW_WUNLOCK(chain); IPFW_UH_WUNLOCK(chain); ipfw_destroy_tables(chain); Modified: projects/ipfw/sys/netpfil/ipfw/ip_fw_private.h ============================================================================== --- projects/ipfw/sys/netpfil/ipfw/ip_fw_private.h Sun Aug 3 15:09:13 2014 (r269476) +++ projects/ipfw/sys/netpfil/ipfw/ip_fw_private.h Sun Aug 3 15:49:03 2014 (r269477) @@ -264,6 +264,7 @@ struct ip_fw_chain { int n_rules; /* number of static rules */ LIST_HEAD(nat_list, cfg_nat) nat; /* list of nat entries */ void *tablestate; /* runtime table info */ + int *idxmap; /* skipto array of rules */ #if defined( __linux__ ) || defined( _WIN32 ) spinlock_t rwmtx; #else @@ -275,6 +276,7 @@ struct ip_fw_chain { struct ip_fw *default_rule; struct tables_config *tblcfg; /* tables module data */ void *ifcfg; /* interface module data */ + int *idxmap_back; /* standby skipto array of rules */ #if defined( __linux__ ) || defined( _WIN32 ) spinlock_t uh_lock; #else @@ -495,6 +497,8 @@ void ipfw_iface_del_notify(struct ip_fw_ int ipfw_list_ifaces(struct ip_fw_chain *ch, struct sockopt_data *sd); /* In ip_fw_sockopt.c */ +void ipfw_init_skipto_cache(struct ip_fw_chain *chain); +void ipfw_destroy_skipto_cache(struct ip_fw_chain *chain); int ipfw_find_rule(struct ip_fw_chain *chain, uint32_t key, uint32_t id); int ipfw_ctl(struct sockopt *sopt); int ipfw_ctl3(struct sockopt *sopt); Modified: projects/ipfw/sys/netpfil/ipfw/ip_fw_sockopt.c ============================================================================== --- projects/ipfw/sys/netpfil/ipfw/ip_fw_sockopt.c Sun Aug 3 15:09:13 2014 (r269476) +++ projects/ipfw/sys/netpfil/ipfw/ip_fw_sockopt.c Sun Aug 3 15:49:03 2014 (r269477) @@ -198,6 +198,104 @@ ipfw_find_rule(struct ip_fw_chain *chain } /* + * Builds skipto cache on rule set @map. + */ +static void +update_skipto_cache(struct ip_fw_chain *chain, struct ip_fw **map) +{ + int *smap, rulenum; + int i, mi; + + IPFW_UH_WLOCK_ASSERT(chain); + + mi = 0; + rulenum = map[mi]->rulenum; + smap = chain->idxmap_back; + + if (smap == NULL) + return; + + for (i = 0; i < 65536; i++) { + smap[i] = mi; + /* Use the same rule index until i < rulenum */ + if (i != rulenum || i == 65535) + continue; + /* Find next rule with num > i */ + rulenum = map[++mi]->rulenum; + while (rulenum == i) + rulenum = map[++mi]->rulenum; + } +} + +/* + * Swaps prepared (backup) index with current one. + */ +static void +swap_skipto_cache(struct ip_fw_chain *chain) +{ + int *map; + + IPFW_UH_WLOCK_ASSERT(chain); + IPFW_WLOCK_ASSERT(chain); + + map = chain->idxmap; + chain->idxmap = chain->idxmap_back; + chain->idxmap_back = map; +} + +/* + * Allocate and initialize skipto cache. + */ +void +ipfw_init_skipto_cache(struct ip_fw_chain *chain) +{ + int *idxmap, *idxmap_back; + + idxmap = malloc(65536 * sizeof(uint32_t *), M_IPFW, + M_WAITOK | M_ZERO); + idxmap_back = malloc(65536 * sizeof(uint32_t *), M_IPFW, + M_WAITOK | M_ZERO); + + /* + * Note we may be called at any time after initialization, + * for example, on first skipto rule, so we need to + * provide valid chain->idxmap on return + */ + + IPFW_UH_WLOCK(chain); + if (chain->idxmap != NULL) { + IPFW_UH_WUNLOCK(chain); + free(idxmap, M_IPFW); + free(idxmap_back, M_IPFW); + return; + } + + /* Set backup pointer first to permit building cache */ + chain->idxmap_back = idxmap_back; + update_skipto_cache(chain, chain->map); + IPFW_WLOCK(chain); + /* It is now safe to set chain->idxmap ptr */ + chain->idxmap = idxmap; + swap_skipto_cache(chain); + IPFW_WUNLOCK(chain); + IPFW_UH_WUNLOCK(chain); +} + +/* + * Destroys skipto cache. + */ +void +ipfw_destroy_skipto_cache(struct ip_fw_chain *chain) +{ + + if (chain->idxmap != NULL) + free(chain->idxmap, M_IPFW); + if (chain->idxmap != NULL) + free(chain->idxmap_back, M_IPFW); +} + + +/* * allocate a new map, returns the chain locked. extra is the number * of entries to add or delete. */ @@ -240,6 +338,7 @@ swap_map(struct ip_fw_chain *chain, stru chain->n_rules = new_len; old_map = chain->map; chain->map = new_map; + swap_skipto_cache(chain); IPFW_WUNLOCK(chain); return old_map; } @@ -498,6 +597,7 @@ commit_rules(struct ip_fw_chain *chain, } krule->id = chain->id + 1; + update_skipto_cache(chain, map); map = swap_map(chain, map, chain->n_rules + 1); chain->static_len += RULEUSIZE0(krule); IPFW_UH_WUNLOCK(chain); @@ -668,7 +768,9 @@ del_entry(struct ip_fw_chain *chain, uin /* 3. copy the final part of the map */ bcopy(chain->map + end, map + ofs, (chain->n_rules - end) * sizeof(struct ip_fw *)); - /* 4. swap the maps (under BH_LOCK) */ + /* 3.5. recalculate skipto cache */ + update_skipto_cache(chain, map); + /* 4. swap the maps (under UH_WLOCK + WHLOCK) */ map = swap_map(chain, map, chain->n_rules - n); /* 5. now remove the rules deleted from the old map */ if (cmd == 1) @@ -726,7 +828,6 @@ del_entry(struct ip_fw_chain *chain, uin free(map, M_IPFW); return error; } - /* * Clear counters for a specific rule. * Normally run under IPFW_UH_RLOCK, but these are idempotent ops