From owner-svn-src-all@freebsd.org Mon Feb 11 05:17:34 2019 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 8997D14E8F85; Mon, 11 Feb 2019 05:17:34 +0000 (UTC) (envelope-from pkelsey@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 219C383DDE; Mon, 11 Feb 2019 05:17:34 +0000 (UTC) (envelope-from pkelsey@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 05181232CE; Mon, 11 Feb 2019 05:17:34 +0000 (UTC) (envelope-from pkelsey@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id x1B5HXCj004849; Mon, 11 Feb 2019 05:17:33 GMT (envelope-from pkelsey@FreeBSD.org) Received: (from pkelsey@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id x1B5HV5t004837; Mon, 11 Feb 2019 05:17:31 GMT (envelope-from pkelsey@FreeBSD.org) Message-Id: <201902110517.x1B5HV5t004837@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: pkelsey set sender to pkelsey@FreeBSD.org using -f From: Patrick Kelsey Date: Mon, 11 Feb 2019 05:17:31 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r343995 - in head/sys: net net/altq netpfil/pf X-SVN-Group: head X-SVN-Commit-Author: pkelsey X-SVN-Commit-Paths: in head/sys: net net/altq netpfil/pf X-SVN-Commit-Revision: 343995 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 219C383DDE X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-2.95 / 15.00]; local_wl_from(0.00)[FreeBSD.org]; NEURAL_HAM_MEDIUM(-1.00)[-0.997,0]; NEURAL_HAM_SHORT(-0.95)[-0.949,0]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; ASN(0.00)[asn:11403, ipnet:2610:1c1:1::/48, country:US] X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 Feb 2019 05:17:34 -0000 Author: pkelsey Date: Mon Feb 11 05:17:31 2019 New Revision: 343995 URL: https://svnweb.freebsd.org/changeset/base/343995 Log: Reduce the time it takes the kernel to install a new PF config containing a large number of queues In general, the time savings come from separating the active and inactive queues lists into separate interface and non-interface queue lists, and changing the rule and queue tag management from list-based to hash-bashed. In HFSC, a linear scan of the class table during each queue destroy was also eliminated. There are now two new tunables to control the hash size used for each tag set (default for each is 128): net.pf.queue_tag_hashsize net.pf.rule_tag_hashsize Reviewed by: kp MFC after: 1 week Sponsored by: RG Nets Differential Revision: https://reviews.freebsd.org/D19131 Modified: head/sys/net/altq/altq_cbq.c head/sys/net/altq/altq_codel.c head/sys/net/altq/altq_fairq.c head/sys/net/altq/altq_hfsc.c head/sys/net/altq/altq_hfsc.h head/sys/net/altq/altq_priq.c head/sys/net/altq/altq_subr.c head/sys/net/altq/altq_var.h head/sys/net/pfvar.h head/sys/netpfil/pf/pf.c head/sys/netpfil/pf/pf_ioctl.c Modified: head/sys/net/altq/altq_cbq.c ============================================================================== --- head/sys/net/altq/altq_cbq.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_cbq.c Mon Feb 11 05:17:31 2019 (r343995) @@ -223,12 +223,11 @@ cbq_pfattach(struct pf_altq *a) } int -cbq_add_altq(struct pf_altq *a) +cbq_add_altq(struct ifnet *ifp, struct pf_altq *a) { cbq_state_t *cbqp; - struct ifnet *ifp; - if ((ifp = ifunit(a->ifname)) == NULL) + if (ifp == NULL) return (EINVAL); if (!ALTQ_IS_READY(&ifp->if_snd)) return (ENODEV); Modified: head/sys/net/altq/altq_codel.c ============================================================================== --- head/sys/net/altq/altq_codel.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_codel.c Mon Feb 11 05:17:31 2019 (r343995) @@ -89,13 +89,12 @@ codel_pfattach(struct pf_altq *a) } int -codel_add_altq(struct pf_altq *a) +codel_add_altq(struct ifnet *ifp, struct pf_altq *a) { struct codel_if *cif; - struct ifnet *ifp; struct codel_opts *opts; - if ((ifp = ifunit(a->ifname)) == NULL) + if (ifp == NULL) return (EINVAL); if (!ALTQ_IS_READY(&ifp->if_snd)) return (ENODEV); Modified: head/sys/net/altq/altq_fairq.c ============================================================================== --- head/sys/net/altq/altq_fairq.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_fairq.c Mon Feb 11 05:17:31 2019 (r343995) @@ -148,12 +148,11 @@ fairq_pfattach(struct pf_altq *a) } int -fairq_add_altq(struct pf_altq *a) +fairq_add_altq(struct ifnet *ifp, struct pf_altq *a) { struct fairq_if *pif; - struct ifnet *ifp; - if ((ifp = ifunit(a->ifname)) == NULL) + if (ifp == NULL) return (EINVAL); if (!ALTQ_IS_READY(&ifp->if_snd)) return (ENODEV); Modified: head/sys/net/altq/altq_hfsc.c ============================================================================== --- head/sys/net/altq/altq_hfsc.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_hfsc.c Mon Feb 11 05:17:31 2019 (r343995) @@ -159,12 +159,11 @@ hfsc_pfattach(struct pf_altq *a) } int -hfsc_add_altq(struct pf_altq *a) +hfsc_add_altq(struct ifnet *ifp, struct pf_altq *a) { struct hfsc_if *hif; - struct ifnet *ifp; - if ((ifp = ifunit(a->ifname)) == NULL) + if (ifp == NULL) return (EINVAL); if (!ALTQ_IS_READY(&ifp->if_snd)) return (ENODEV); @@ -506,6 +505,7 @@ hfsc_class_create(struct hfsc_if *hif, struct service_ goto err_ret; } } + cl->cl_slot = i; if (flags & HFCF_DEFAULTCLASS) hif->hif_defaultclass = cl; @@ -558,7 +558,7 @@ hfsc_class_create(struct hfsc_if *hif, struct service_ static int hfsc_class_destroy(struct hfsc_class *cl) { - int i, s; + int s; if (cl == NULL) return (0); @@ -589,12 +589,7 @@ hfsc_class_destroy(struct hfsc_class *cl) ASSERT(p != NULL); } - for (i = 0; i < HFSC_MAX_CLASSES; i++) - if (cl->cl_hif->hif_class_tbl[i] == cl) { - cl->cl_hif->hif_class_tbl[i] = NULL; - break; - } - + cl->cl_hif->hif_class_tbl[cl->cl_slot] = NULL; cl->cl_hif->hif_classes--; IFQ_UNLOCK(cl->cl_hif->hif_ifq); splx(s); Modified: head/sys/net/altq/altq_hfsc.h ============================================================================== --- head/sys/net/altq/altq_hfsc.h Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_hfsc.h Mon Feb 11 05:17:31 2019 (r343995) @@ -214,6 +214,7 @@ struct runtime_sc { struct hfsc_class { u_int cl_id; /* class id (just for debug) */ + u_int cl_slot; /* slot in hif class table */ u_int32_t cl_handle; /* class handle */ struct hfsc_if *cl_hif; /* back pointer to struct hfsc_if */ int cl_flags; /* misc flags */ Modified: head/sys/net/altq/altq_priq.c ============================================================================== --- head/sys/net/altq/altq_priq.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_priq.c Mon Feb 11 05:17:31 2019 (r343995) @@ -95,12 +95,11 @@ priq_pfattach(struct pf_altq *a) } int -priq_add_altq(struct pf_altq *a) +priq_add_altq(struct ifnet * ifp, struct pf_altq *a) { struct priq_if *pif; - struct ifnet *ifp; - if ((ifp = ifunit(a->ifname)) == NULL) + if (ifp == NULL) return (EINVAL); if (!ALTQ_IS_READY(&ifp->if_snd)) return (ENODEV); Modified: head/sys/net/altq/altq_subr.c ============================================================================== --- head/sys/net/altq/altq_subr.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_subr.c Mon Feb 11 05:17:31 2019 (r343995) @@ -520,7 +520,7 @@ altq_pfdetach(struct pf_altq *a) * malloc with WAITOK, also it is not yet clear which lock to use. */ int -altq_add(struct pf_altq *a) +altq_add(struct ifnet *ifp, struct pf_altq *a) { int error = 0; @@ -535,27 +535,27 @@ altq_add(struct pf_altq *a) switch (a->scheduler) { #ifdef ALTQ_CBQ case ALTQT_CBQ: - error = cbq_add_altq(a); + error = cbq_add_altq(ifp, a); break; #endif #ifdef ALTQ_PRIQ case ALTQT_PRIQ: - error = priq_add_altq(a); + error = priq_add_altq(ifp, a); break; #endif #ifdef ALTQ_HFSC case ALTQT_HFSC: - error = hfsc_add_altq(a); + error = hfsc_add_altq(ifp, a); break; #endif #ifdef ALTQ_FAIRQ case ALTQT_FAIRQ: - error = fairq_add_altq(a); + error = fairq_add_altq(ifp, a); break; #endif #ifdef ALTQ_CODEL case ALTQT_CODEL: - error = codel_add_altq(a); + error = codel_add_altq(ifp, a); break; #endif default: Modified: head/sys/net/altq/altq_var.h ============================================================================== --- head/sys/net/altq/altq_var.h Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/altq/altq_var.h Mon Feb 11 05:17:31 2019 (r343995) @@ -199,40 +199,40 @@ int tbr_set(struct ifaltq *, struct tb_profile *); int altq_pfattach(struct pf_altq *); int altq_pfdetach(struct pf_altq *); -int altq_add(struct pf_altq *); +int altq_add(struct ifnet *, struct pf_altq *); int altq_remove(struct pf_altq *); int altq_add_queue(struct pf_altq *); int altq_remove_queue(struct pf_altq *); int altq_getqstats(struct pf_altq *, void *, int *, int); int cbq_pfattach(struct pf_altq *); -int cbq_add_altq(struct pf_altq *); +int cbq_add_altq(struct ifnet *, struct pf_altq *); int cbq_remove_altq(struct pf_altq *); int cbq_add_queue(struct pf_altq *); int cbq_remove_queue(struct pf_altq *); int cbq_getqstats(struct pf_altq *, void *, int *, int); int codel_pfattach(struct pf_altq *); -int codel_add_altq(struct pf_altq *); +int codel_add_altq(struct ifnet *, struct pf_altq *); int codel_remove_altq(struct pf_altq *); int codel_getqstats(struct pf_altq *, void *, int *, int); int priq_pfattach(struct pf_altq *); -int priq_add_altq(struct pf_altq *); +int priq_add_altq(struct ifnet *, struct pf_altq *); int priq_remove_altq(struct pf_altq *); int priq_add_queue(struct pf_altq *); int priq_remove_queue(struct pf_altq *); int priq_getqstats(struct pf_altq *, void *, int *, int); int hfsc_pfattach(struct pf_altq *); -int hfsc_add_altq(struct pf_altq *); +int hfsc_add_altq(struct ifnet *, struct pf_altq *); int hfsc_remove_altq(struct pf_altq *); int hfsc_add_queue(struct pf_altq *); int hfsc_remove_queue(struct pf_altq *); int hfsc_getqstats(struct pf_altq *, void *, int *, int); int fairq_pfattach(struct pf_altq *); -int fairq_add_altq(struct pf_altq *); +int fairq_add_altq(struct ifnet *, struct pf_altq *); int fairq_remove_altq(struct pf_altq *); int fairq_add_queue(struct pf_altq *); int fairq_remove_queue(struct pf_altq *); Modified: head/sys/net/pfvar.h ============================================================================== --- head/sys/net/pfvar.h Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/net/pfvar.h Mon Feb 11 05:17:31 2019 (r343995) @@ -41,6 +41,7 @@ #include #include #include +#include #include #include #include @@ -95,6 +96,9 @@ struct pf_addr_wrap { #ifdef _KERNEL +SYSCTL_DECL(_net_pf); +MALLOC_DECLARE(M_PFHASH); + struct pfi_dynaddr { TAILQ_ENTRY(pfi_dynaddr) entry; struct pf_addr pfid_addr4; @@ -1601,7 +1605,7 @@ VNET_DECLARE(uint64_t, pf_stateid[MAXCPU]); #define V_pf_stateid VNET(pf_stateid) TAILQ_HEAD(pf_altqqueue, pf_altq); -VNET_DECLARE(struct pf_altqqueue, pf_altqs[2]); +VNET_DECLARE(struct pf_altqqueue, pf_altqs[4]); #define V_pf_altqs VNET(pf_altqs) VNET_DECLARE(struct pf_palist, pf_pabuf); #define V_pf_pabuf VNET(pf_pabuf) @@ -1616,8 +1620,12 @@ VNET_DECLARE(u_int32_t, ticket_pabuf); #define V_ticket_pabuf VNET(ticket_pabuf) VNET_DECLARE(struct pf_altqqueue *, pf_altqs_active); #define V_pf_altqs_active VNET(pf_altqs_active) +VNET_DECLARE(struct pf_altqqueue *, pf_altq_ifs_active); +#define V_pf_altq_ifs_active VNET(pf_altq_ifs_active) VNET_DECLARE(struct pf_altqqueue *, pf_altqs_inactive); #define V_pf_altqs_inactive VNET(pf_altqs_inactive) +VNET_DECLARE(struct pf_altqqueue *, pf_altq_ifs_inactive); +#define V_pf_altq_ifs_inactive VNET(pf_altq_ifs_inactive) VNET_DECLARE(struct pf_rulequeue, pf_unlinked_rules); #define V_pf_unlinked_rules VNET(pf_unlinked_rules) Modified: head/sys/netpfil/pf/pf.c ============================================================================== --- head/sys/netpfil/pf/pf.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/netpfil/pf/pf.c Mon Feb 11 05:17:31 2019 (r343995) @@ -113,10 +113,12 @@ __FBSDID("$FreeBSD$"); */ /* state tables */ -VNET_DEFINE(struct pf_altqqueue, pf_altqs[2]); +VNET_DEFINE(struct pf_altqqueue, pf_altqs[4]); VNET_DEFINE(struct pf_palist, pf_pabuf); VNET_DEFINE(struct pf_altqqueue *, pf_altqs_active); +VNET_DEFINE(struct pf_altqqueue *, pf_altq_ifs_active); VNET_DEFINE(struct pf_altqqueue *, pf_altqs_inactive); +VNET_DEFINE(struct pf_altqqueue *, pf_altq_ifs_inactive); VNET_DEFINE(struct pf_kstatus, pf_status); VNET_DEFINE(u_int32_t, ticket_altqs_active); @@ -358,7 +360,7 @@ VNET_DEFINE(struct pf_limit, pf_limits[PF_LIMIT_MAX]); counter_u64_add(s->rule.ptr->states_cur, -1); \ } while (0) -static MALLOC_DEFINE(M_PFHASH, "pf_hash", "pf(4) hash header structures"); +MALLOC_DEFINE(M_PFHASH, "pf_hash", "pf(4) hash header structures"); VNET_DEFINE(struct pf_keyhash *, pf_keyhash); VNET_DEFINE(struct pf_idhash *, pf_idhash); VNET_DEFINE(struct pf_srchash *, pf_srchash); @@ -860,9 +862,13 @@ pf_initialize() /* ALTQ */ TAILQ_INIT(&V_pf_altqs[0]); TAILQ_INIT(&V_pf_altqs[1]); + TAILQ_INIT(&V_pf_altqs[2]); + TAILQ_INIT(&V_pf_altqs[3]); TAILQ_INIT(&V_pf_pabuf); V_pf_altqs_active = &V_pf_altqs[0]; - V_pf_altqs_inactive = &V_pf_altqs[1]; + V_pf_altq_ifs_active = &V_pf_altqs[1]; + V_pf_altqs_inactive = &V_pf_altqs[2]; + V_pf_altq_ifs_inactive = &V_pf_altqs[3]; /* Send & overload+flush queues. */ STAILQ_INIT(&V_pf_sendqueue); Modified: head/sys/netpfil/pf/pf_ioctl.c ============================================================================== --- head/sys/netpfil/pf/pf_ioctl.c Mon Feb 11 04:00:42 2019 (r343994) +++ head/sys/netpfil/pf/pf_ioctl.c Mon Feb 11 05:17:31 2019 (r343995) @@ -46,11 +46,14 @@ __FBSDID("$FreeBSD$"); #include "opt_pf.h" #include +#include +#include #include #include #include #include #include +#include #include #include #include @@ -129,18 +132,40 @@ VNET_DEFINE_STATIC(int, pf_altq_running); #define TAGID_MAX 50000 struct pf_tagname { - TAILQ_ENTRY(pf_tagname) entries; + TAILQ_ENTRY(pf_tagname) namehash_entries; + TAILQ_ENTRY(pf_tagname) taghash_entries; char name[PF_TAG_NAME_SIZE]; uint16_t tag; int ref; }; -TAILQ_HEAD(pf_tags, pf_tagname); -#define V_pf_tags VNET(pf_tags) -VNET_DEFINE(struct pf_tags, pf_tags); -#define V_pf_qids VNET(pf_qids) -VNET_DEFINE(struct pf_tags, pf_qids); -static MALLOC_DEFINE(M_PFTAG, "pf_tag", "pf(4) tag names"); +struct pf_tagset { + TAILQ_HEAD(, pf_tagname) *namehash; + TAILQ_HEAD(, pf_tagname) *taghash; + unsigned int mask; + uint32_t seed; + BITSET_DEFINE(, TAGID_MAX) avail; +}; + +VNET_DEFINE(struct pf_tagset, pf_tags); +#define V_pf_tags VNET(pf_tags) +static unsigned int pf_rule_tag_hashsize; +#define PF_RULE_TAG_HASH_SIZE_DEFAULT 128 +SYSCTL_UINT(_net_pf, OID_AUTO, rule_tag_hashsize, CTLFLAG_RDTUN, + &pf_rule_tag_hashsize, PF_RULE_TAG_HASH_SIZE_DEFAULT, + "Size of pf(4) rule tag hashtable"); + +#ifdef ALTQ +VNET_DEFINE(struct pf_tagset, pf_qids); +#define V_pf_qids VNET(pf_qids) +static unsigned int pf_queue_tag_hashsize; +#define PF_QUEUE_TAG_HASH_SIZE_DEFAULT 128 +SYSCTL_UINT(_net_pf, OID_AUTO, queue_tag_hashsize, CTLFLAG_RDTUN, + &pf_queue_tag_hashsize, PF_QUEUE_TAG_HASH_SIZE_DEFAULT, + "Size of pf(4) queue tag hashtable"); +#endif +VNET_DEFINE(uma_zone_t, pf_tag_z); +#define V_pf_tag_z VNET(pf_tag_z) static MALLOC_DEFINE(M_PFALTQ, "pf_altq", "pf(4) altq configuration db"); static MALLOC_DEFINE(M_PFRULE, "pf_rule", "pf(4) rules"); @@ -148,9 +173,14 @@ static MALLOC_DEFINE(M_PFRULE, "pf_rule", "pf(4) rules #error PF_QNAME_SIZE must be equal to PF_TAG_NAME_SIZE #endif -static u_int16_t tagname2tag(struct pf_tags *, char *); +static void pf_init_tagset(struct pf_tagset *, unsigned int *, + unsigned int); +static void pf_cleanup_tagset(struct pf_tagset *); +static uint16_t tagname2hashindex(const struct pf_tagset *, const char *); +static uint16_t tag2hashindex(const struct pf_tagset *, uint16_t); +static u_int16_t tagname2tag(struct pf_tagset *, char *); static u_int16_t pf_tagname2tag(char *); -static void tag_unref(struct pf_tags *, u_int16_t); +static void tag_unref(struct pf_tagset *, u_int16_t); #define DPFPRINTF(n, x) if (V_pf_status.debug >= (n)) printf x @@ -436,68 +466,141 @@ pf_free_rule(struct pf_rule *rule) free(rule, M_PFRULE); } +static void +pf_init_tagset(struct pf_tagset *ts, unsigned int *tunable_size, + unsigned int default_size) +{ + unsigned int i; + unsigned int hashsize; + + if (*tunable_size == 0 || !powerof2(*tunable_size)) + *tunable_size = default_size; + + hashsize = *tunable_size; + ts->namehash = mallocarray(hashsize, sizeof(*ts->namehash), M_PFHASH, + M_WAITOK); + ts->taghash = mallocarray(hashsize, sizeof(*ts->taghash), M_PFHASH, + M_WAITOK); + ts->mask = hashsize - 1; + ts->seed = arc4random(); + for (i = 0; i < hashsize; i++) { + TAILQ_INIT(&ts->namehash[i]); + TAILQ_INIT(&ts->taghash[i]); + } + BIT_FILL(TAGID_MAX, &ts->avail); +} + +static void +pf_cleanup_tagset(struct pf_tagset *ts) +{ + unsigned int i; + unsigned int hashsize; + struct pf_tagname *t, *tmp; + + /* + * Only need to clean up one of the hashes as each tag is hashed + * into each table. + */ + hashsize = ts->mask + 1; + for (i = 0; i < hashsize; i++) + TAILQ_FOREACH_SAFE(t, &ts->namehash[i], namehash_entries, tmp) + uma_zfree(V_pf_tag_z, t); + + free(ts->namehash, M_PFHASH); + free(ts->taghash, M_PFHASH); +} + +static uint16_t +tagname2hashindex(const struct pf_tagset *ts, const char *tagname) +{ + + return (murmur3_32_hash(tagname, strlen(tagname), ts->seed) & ts->mask); +} + +static uint16_t +tag2hashindex(const struct pf_tagset *ts, uint16_t tag) +{ + + return (tag & ts->mask); +} + static u_int16_t -tagname2tag(struct pf_tags *head, char *tagname) +tagname2tag(struct pf_tagset *ts, char *tagname) { - struct pf_tagname *tag, *p = NULL; - u_int16_t new_tagid = 1; + struct pf_tagname *tag; + u_int32_t index; + u_int16_t new_tagid; PF_RULES_WASSERT(); - TAILQ_FOREACH(tag, head, entries) + index = tagname2hashindex(ts, tagname); + TAILQ_FOREACH(tag, &ts->namehash[index], namehash_entries) if (strcmp(tagname, tag->name) == 0) { tag->ref++; return (tag->tag); } /* + * new entry + * * to avoid fragmentation, we do a linear search from the beginning - * and take the first free slot we find. if there is none or the list - * is empty, append a new entry at the end. + * and take the first free slot we find. */ - - /* new entry */ - if (!TAILQ_EMPTY(head)) - for (p = TAILQ_FIRST(head); p != NULL && - p->tag == new_tagid; p = TAILQ_NEXT(p, entries)) - new_tagid = p->tag + 1; - - if (new_tagid > TAGID_MAX) + new_tagid = BIT_FFS(TAGID_MAX, &ts->avail); + /* + * Tags are 1-based, with valid tags in the range [1..TAGID_MAX]. + * BIT_FFS() returns a 1-based bit number, with 0 indicating no bits + * set. It may also return a bit number greater than TAGID_MAX due + * to rounding of the number of bits in the vector up to a multiple + * of the vector word size at declaration/allocation time. + */ + if ((new_tagid == 0) || (new_tagid > TAGID_MAX)) return (0); + /* Mark the tag as in use. Bits are 0-based for BIT_CLR() */ + BIT_CLR(TAGID_MAX, new_tagid - 1, &ts->avail); + /* allocate and fill new struct pf_tagname */ - tag = malloc(sizeof(*tag), M_PFTAG, M_NOWAIT|M_ZERO); + tag = uma_zalloc(V_pf_tag_z, M_NOWAIT); if (tag == NULL) return (0); strlcpy(tag->name, tagname, sizeof(tag->name)); tag->tag = new_tagid; - tag->ref++; + tag->ref = 1; - if (p != NULL) /* insert new entry before p */ - TAILQ_INSERT_BEFORE(p, tag, entries); - else /* either list empty or no free slot in between */ - TAILQ_INSERT_TAIL(head, tag, entries); + /* Insert into namehash */ + TAILQ_INSERT_TAIL(&ts->namehash[index], tag, namehash_entries); + /* Insert into taghash */ + index = tag2hashindex(ts, new_tagid); + TAILQ_INSERT_TAIL(&ts->taghash[index], tag, taghash_entries); + return (tag->tag); } static void -tag_unref(struct pf_tags *head, u_int16_t tag) +tag_unref(struct pf_tagset *ts, u_int16_t tag) { - struct pf_tagname *p, *next; - + struct pf_tagname *t; + uint16_t index; + PF_RULES_WASSERT(); - for (p = TAILQ_FIRST(head); p != NULL; p = next) { - next = TAILQ_NEXT(p, entries); - if (tag == p->tag) { - if (--p->ref == 0) { - TAILQ_REMOVE(head, p, entries); - free(p, M_PFTAG); + index = tag2hashindex(ts, tag); + TAILQ_FOREACH(t, &ts->taghash[index], taghash_entries) + if (tag == t->tag) { + if (--t->ref == 0) { + TAILQ_REMOVE(&ts->taghash[index], t, + taghash_entries); + index = tagname2hashindex(ts, t->name); + TAILQ_REMOVE(&ts->namehash[index], t, + namehash_entries); + /* Bits are 0-based for BIT_SET() */ + BIT_SET(TAGID_MAX, tag - 1, &ts->avail); + uma_zfree(V_pf_tag_z, t); } break; } - } } static u_int16_t @@ -522,22 +625,25 @@ pf_qid_unref(u_int32_t qid) static int pf_begin_altq(u_int32_t *ticket) { - struct pf_altq *altq; + struct pf_altq *altq, *tmp; int error = 0; PF_RULES_WASSERT(); - /* Purge the old altq list */ - while ((altq = TAILQ_FIRST(V_pf_altqs_inactive)) != NULL) { - TAILQ_REMOVE(V_pf_altqs_inactive, altq, entries); - if (altq->qname[0] == 0 && - (altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { + /* Purge the old altq lists */ + TAILQ_FOREACH_SAFE(altq, V_pf_altq_ifs_inactive, entries, tmp) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { /* detach and destroy the discipline */ error = altq_remove(altq); - } else - pf_qid_unref(altq->qid); + } free(altq, M_PFALTQ); } + TAILQ_INIT(V_pf_altq_ifs_inactive); + TAILQ_FOREACH_SAFE(altq, V_pf_altqs_inactive, entries, tmp) { + pf_qid_unref(altq->qid); + free(altq, M_PFALTQ); + } + TAILQ_INIT(V_pf_altqs_inactive); if (error) return (error); *ticket = ++V_ticket_altqs_inactive; @@ -548,24 +654,27 @@ pf_begin_altq(u_int32_t *ticket) static int pf_rollback_altq(u_int32_t ticket) { - struct pf_altq *altq; + struct pf_altq *altq, *tmp; int error = 0; PF_RULES_WASSERT(); if (!V_altqs_inactive_open || ticket != V_ticket_altqs_inactive) return (0); - /* Purge the old altq list */ - while ((altq = TAILQ_FIRST(V_pf_altqs_inactive)) != NULL) { - TAILQ_REMOVE(V_pf_altqs_inactive, altq, entries); - if (altq->qname[0] == 0 && - (altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { + /* Purge the old altq lists */ + TAILQ_FOREACH_SAFE(altq, V_pf_altq_ifs_inactive, entries, tmp) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { /* detach and destroy the discipline */ error = altq_remove(altq); - } else - pf_qid_unref(altq->qid); + } free(altq, M_PFALTQ); } + TAILQ_INIT(V_pf_altq_ifs_inactive); + TAILQ_FOREACH_SAFE(altq, V_pf_altqs_inactive, entries, tmp) { + pf_qid_unref(altq->qid); + free(altq, M_PFALTQ); + } + TAILQ_INIT(V_pf_altqs_inactive); V_altqs_inactive_open = 0; return (error); } @@ -573,8 +682,8 @@ pf_rollback_altq(u_int32_t ticket) static int pf_commit_altq(u_int32_t ticket) { - struct pf_altqqueue *old_altqs; - struct pf_altq *altq; + struct pf_altqqueue *old_altqs, *old_altq_ifs; + struct pf_altq *altq, *tmp; int err, error = 0; PF_RULES_WASSERT(); @@ -584,14 +693,16 @@ pf_commit_altq(u_int32_t ticket) /* swap altqs, keep the old. */ old_altqs = V_pf_altqs_active; + old_altq_ifs = V_pf_altq_ifs_active; V_pf_altqs_active = V_pf_altqs_inactive; + V_pf_altq_ifs_active = V_pf_altq_ifs_inactive; V_pf_altqs_inactive = old_altqs; + V_pf_altq_ifs_inactive = old_altq_ifs; V_ticket_altqs_active = V_ticket_altqs_inactive; /* Attach new disciplines */ - TAILQ_FOREACH(altq, V_pf_altqs_active, entries) { - if (altq->qname[0] == 0 && - (altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { + TAILQ_FOREACH(altq, V_pf_altq_ifs_active, entries) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { /* attach the discipline */ error = altq_pfattach(altq); if (error == 0 && V_pf_altq_running) @@ -601,11 +712,9 @@ pf_commit_altq(u_int32_t ticket) } } - /* Purge the old altq list */ - while ((altq = TAILQ_FIRST(V_pf_altqs_inactive)) != NULL) { - TAILQ_REMOVE(V_pf_altqs_inactive, altq, entries); - if (altq->qname[0] == 0 && - (altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { + /* Purge the old altq lists */ + TAILQ_FOREACH_SAFE(altq, V_pf_altq_ifs_inactive, entries, tmp) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { /* detach and destroy the discipline */ if (V_pf_altq_running) error = pf_disable_altq(altq); @@ -615,10 +724,15 @@ pf_commit_altq(u_int32_t ticket) err = altq_remove(altq); if (err != 0 && error == 0) error = err; - } else - pf_qid_unref(altq->qid); + } free(altq, M_PFALTQ); } + TAILQ_INIT(V_pf_altq_ifs_inactive); + TAILQ_FOREACH_SAFE(altq, V_pf_altqs_inactive, entries, tmp) { + pf_qid_unref(altq->qid); + free(altq, M_PFALTQ); + } + TAILQ_INIT(V_pf_altqs_inactive); V_altqs_inactive_open = 0; return (error); @@ -675,10 +789,34 @@ pf_disable_altq(struct pf_altq *altq) return (error); } +static int +pf_altq_ifnet_event_add(struct ifnet *ifp, int remove, u_int32_t ticket, + struct pf_altq *altq) +{ + struct ifnet *ifp1; + int error = 0; + + /* Deactivate the interface in question */ + altq->local_flags &= ~PFALTQ_FLAG_IF_REMOVED; + if ((ifp1 = ifunit(altq->ifname)) == NULL || + (remove && ifp1 == ifp)) { + altq->local_flags |= PFALTQ_FLAG_IF_REMOVED; + } else { + error = altq_add(ifp1, altq); + + if (ticket != V_ticket_altqs_inactive) + error = EBUSY; + + if (error) + free(altq, M_PFALTQ); + } + + return (error); +} + void pf_altq_ifnet_event(struct ifnet *ifp, int remove) { - struct ifnet *ifp1; struct pf_altq *a1, *a2, *a3; u_int32_t ticket; int error = 0; @@ -700,7 +838,7 @@ pf_altq_ifnet_event(struct ifnet *ifp, int remove) return; /* Copy the current active set */ - TAILQ_FOREACH(a1, V_pf_altqs_active, entries) { + TAILQ_FOREACH(a1, V_pf_altq_ifs_active, entries) { a2 = malloc(sizeof(*a2), M_PFALTQ, M_NOWAIT); if (a2 == NULL) { error = ENOMEM; @@ -708,41 +846,43 @@ pf_altq_ifnet_event(struct ifnet *ifp, int remove) } bcopy(a1, a2, sizeof(struct pf_altq)); - if (a2->qname[0] != 0) { - if ((a2->qid = pf_qname2qid(a2->qname)) == 0) { - error = EBUSY; - free(a2, M_PFALTQ); - break; - } - a2->altq_disc = NULL; - TAILQ_FOREACH(a3, V_pf_altqs_inactive, entries) { - if (strncmp(a3->ifname, a2->ifname, - IFNAMSIZ) == 0 && a3->qname[0] == 0) { - a2->altq_disc = a3->altq_disc; - break; - } - } + error = pf_altq_ifnet_event_add(ifp, remove, ticket, a2); + if (error) + break; + + TAILQ_INSERT_TAIL(V_pf_altq_ifs_inactive, a2, entries); + } + if (error) + goto out; + TAILQ_FOREACH(a1, V_pf_altqs_active, entries) { + a2 = malloc(sizeof(*a2), M_PFALTQ, M_NOWAIT); + if (a2 == NULL) { + error = ENOMEM; + break; } - /* Deactivate the interface in question */ - a2->local_flags &= ~PFALTQ_FLAG_IF_REMOVED; - if ((ifp1 = ifunit(a2->ifname)) == NULL || - (remove && ifp1 == ifp)) { - a2->local_flags |= PFALTQ_FLAG_IF_REMOVED; - } else { - error = altq_add(a2); + bcopy(a1, a2, sizeof(struct pf_altq)); - if (ticket != V_ticket_altqs_inactive) - error = EBUSY; - - if (error) { - free(a2, M_PFALTQ); + if ((a2->qid = pf_qname2qid(a2->qname)) == 0) { + error = EBUSY; + free(a2, M_PFALTQ); + break; + } + a2->altq_disc = NULL; + TAILQ_FOREACH(a3, V_pf_altq_ifs_inactive, entries) { + if (strncmp(a3->ifname, a2->ifname, + IFNAMSIZ) == 0) { + a2->altq_disc = a3->altq_disc; break; } } + error = pf_altq_ifnet_event_add(ifp, remove, ticket, a2); + if (error) + break; TAILQ_INSERT_TAIL(V_pf_altqs_inactive, a2, entries); } +out: if (error != 0) pf_rollback_altq(ticket); else @@ -1222,6 +1362,28 @@ pf_import_kaltq(struct pfioc_altq_v1 *pa, struct pf_al } #endif /* ALTQ */ +static struct pf_altq * +pf_altq_get_nth_active(u_int32_t n) +{ + struct pf_altq *altq; + u_int32_t nr; + + nr = 0; + TAILQ_FOREACH(altq, V_pf_altq_ifs_active, entries) { + if (nr == n) + return (altq); + nr++; + } + + TAILQ_FOREACH(altq, V_pf_altqs_active, entries) { + if (nr == n) + return (altq); + nr++; + } + + return (NULL); +} + static int pfioctl(struct cdev *dev, u_long cmd, caddr_t addr, int flags, struct thread *td) { @@ -2269,9 +2431,8 @@ DIOCGETSTATES_full: PF_RULES_WLOCK(); /* enable all altq interfaces on active list */ - TAILQ_FOREACH(altq, V_pf_altqs_active, entries) { - if (altq->qname[0] == 0 && (altq->local_flags & - PFALTQ_FLAG_IF_REMOVED) == 0) { + TAILQ_FOREACH(altq, V_pf_altq_ifs_active, entries) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { error = pf_enable_altq(altq); if (error != 0) break; @@ -2289,9 +2450,8 @@ DIOCGETSTATES_full: PF_RULES_WLOCK(); /* disable all altq interfaces on active list */ - TAILQ_FOREACH(altq, V_pf_altqs_active, entries) { - if (altq->qname[0] == 0 && (altq->local_flags & - PFALTQ_FLAG_IF_REMOVED) == 0) { + TAILQ_FOREACH(altq, V_pf_altq_ifs_active, entries) { + if ((altq->local_flags & PFALTQ_FLAG_IF_REMOVED) == 0) { error = pf_disable_altq(altq); if (error != 0) break; @@ -2336,9 +2496,9 @@ DIOCGETSTATES_full: break; } altq->altq_disc = NULL; - TAILQ_FOREACH(a, V_pf_altqs_inactive, entries) { + TAILQ_FOREACH(a, V_pf_altq_ifs_inactive, entries) { if (strncmp(a->ifname, altq->ifname, - IFNAMSIZ) == 0 && a->qname[0] == 0) { + IFNAMSIZ) == 0) { altq->altq_disc = a->altq_disc; break; } @@ -2348,7 +2508,7 @@ DIOCGETSTATES_full: if ((ifp = ifunit(altq->ifname)) == NULL) altq->local_flags |= PFALTQ_FLAG_IF_REMOVED; else - error = altq_add(altq); + error = altq_add(ifp, altq); if (error) { PF_RULES_WUNLOCK(); @@ -2356,7 +2516,10 @@ DIOCGETSTATES_full: break; } - TAILQ_INSERT_TAIL(V_pf_altqs_inactive, altq, entries); + if (altq->qname[0] != 0) + TAILQ_INSERT_TAIL(V_pf_altqs_inactive, altq, entries); + else + TAILQ_INSERT_TAIL(V_pf_altq_ifs_inactive, altq, entries); /* version error check done on import above */ pf_export_kaltq(altq, pa, IOCPARM_LEN(cmd)); PF_RULES_WUNLOCK(); @@ -2370,6 +2533,8 @@ DIOCGETSTATES_full: PF_RULES_RLOCK(); pa->nr = 0; + TAILQ_FOREACH(altq, V_pf_altq_ifs_active, entries) + pa->nr++; TAILQ_FOREACH(altq, V_pf_altqs_active, entries) pa->nr++; pa->ticket = V_ticket_altqs_active; @@ -2381,7 +2546,6 @@ DIOCGETSTATES_full: case DIOCGETALTQV1: { struct pfioc_altq_v1 *pa = (struct pfioc_altq_v1 *)addr; struct pf_altq *altq; - u_int32_t nr; PF_RULES_RLOCK(); if (pa->ticket != V_ticket_altqs_active) { @@ -2389,12 +2553,7 @@ DIOCGETSTATES_full: error = EBUSY; break; } - nr = 0; - altq = TAILQ_FIRST(V_pf_altqs_active); - while ((altq != NULL) && (nr < pa->nr)) { - altq = TAILQ_NEXT(altq, entries); - nr++; - } + altq = pf_altq_get_nth_active(pa->nr); if (altq == NULL) { PF_RULES_RUNLOCK(); error = EBUSY; @@ -2415,7 +2574,6 @@ DIOCGETSTATES_full: case DIOCGETQSTATSV1: { struct pfioc_qstats_v1 *pq = (struct pfioc_qstats_v1 *)addr; struct pf_altq *altq; - u_int32_t nr; int nbytes; u_int32_t version; @@ -2426,12 +2584,7 @@ DIOCGETSTATES_full: break; } nbytes = pq->nbytes; - nr = 0; - altq = TAILQ_FIRST(V_pf_altqs_active); - while ((altq != NULL) && (nr < pq->nr)) { - altq = TAILQ_NEXT(altq, entries); - nr++; - } + altq = pf_altq_get_nth_active(pq->nr); if (altq == NULL) { PF_RULES_RUNLOCK(); error = EBUSY; @@ -4173,9 +4326,16 @@ dehook_pf(void) static void pf_load_vnet(void) { - TAILQ_INIT(&V_pf_tags); - TAILQ_INIT(&V_pf_qids); + V_pf_tag_z = uma_zcreate("pf tags", sizeof(struct pf_tagname), + NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0); + pf_init_tagset(&V_pf_tags, &pf_rule_tag_hashsize, + PF_RULE_TAG_HASH_SIZE_DEFAULT); +#ifdef ALTQ + pf_init_tagset(&V_pf_qids, &pf_queue_tag_hashsize, + PF_QUEUE_TAG_HASH_SIZE_DEFAULT); +#endif + pfattach_vnet(); V_pf_vnet_active = 1; } @@ -4240,6 +4400,12 @@ pf_unload_vnet(void) pf_cleanup(); if (IS_DEFAULT_VNET(curvnet)) pf_mtag_cleanup(); + + pf_cleanup_tagset(&V_pf_tags); +#ifdef ALTQ + pf_cleanup_tagset(&V_pf_qids); +#endif + uma_zdestroy(V_pf_tag_z); /* Free counters last as we updated them during shutdown. */ counter_u64_free(V_pf_default_rule.states_cur);