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

11 files changed, 331 insertions, 159 deletions

diff --git a/sys/net/altq/altq_cbq.c b/sys/net/altq/altq_cbq.c
index aa646848dc32..fd05955bb966 100644
--- a/sys/net/altq/altq_cbq.c
+++ b/sys/net/altq/altq_cbq.c
@@ -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);
diff --git a/sys/net/altq/altq_codel.c b/sys/net/altq/altq_codel.c
index ee3ea82b7ab9..a98553aa52f4 100644
--- a/sys/net/altq/altq_codel.c
+++ b/sys/net/altq/altq_codel.c
@@ -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);
diff --git a/sys/net/altq/altq_fairq.c b/sys/net/altq/altq_fairq.c
index b695a5133df0..c6ccea2b5dee 100644
--- a/sys/net/altq/altq_fairq.c
+++ b/sys/net/altq/altq_fairq.c
@@ -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);
diff --git a/sys/net/altq/altq_hfsc.c b/sys/net/altq/altq_hfsc.c
index 1405849c0fab..5a5f56fcd2fe 100644
--- a/sys/net/altq/altq_hfsc.c
+++ b/sys/net/altq/altq_hfsc.c
@@ -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_curve *rsc,
 			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_curve *rsc,
 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);
diff --git a/sys/net/altq/altq_hfsc.h b/sys/net/altq/altq_hfsc.h
index fa4aa81134b0..c43c6671ca59 100644
--- a/sys/net/altq/altq_hfsc.h
+++ b/sys/net/altq/altq_hfsc.h
@@ -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 */
diff --git a/sys/net/altq/altq_priq.c b/sys/net/altq/altq_priq.c
index 5a413e3401b6..578745023a9b 100644
--- a/sys/net/altq/altq_priq.c
+++ b/sys/net/altq/altq_priq.c
@@ -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);
diff --git a/sys/net/altq/altq_subr.c b/sys/net/altq/altq_subr.c
index 4e840a5b2e32..e49a925f5e83 100644
--- a/sys/net/altq/altq_subr.c
+++ b/sys/net/altq/altq_subr.c
@@ -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:
diff --git a/sys/net/altq/altq_var.h b/sys/net/altq/altq_var.h
index 47326a03f3dc..f711e09334cb 100644
--- a/sys/net/altq/altq_var.h
+++ b/sys/net/altq/altq_var.h
@@ -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 *);
diff --git a/sys/net/pfvar.h b/sys/net/pfvar.h
index 2924c06dbc43..ac7ae2b3748c 100644
--- a/sys/net/pfvar.h
+++ b/sys/net/pfvar.h
@@ -41,6 +41,7 @@
 #include <sys/cpuset.h>
 #include <sys/malloc.h>
 #include <sys/refcount.h>
+#include <sys/sysctl.h>
 #include <sys/lock.h>
 #include <sys/rmlock.h>
 #include <sys/tree.h>
@@ -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)
diff --git a/sys/netpfil/pf/pf.c b/sys/netpfil/pf/pf.c
index 2c7db9a7e5c8..46ffd4ee202a 100644
--- a/sys/netpfil/pf/pf.c
+++ b/sys/netpfil/pf/pf.c
@@ -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);
diff --git a/sys/netpfil/pf/pf_ioctl.c b/sys/netpfil/pf/pf_ioctl.c
index fd946d158ba1..cb22aa678bab 100644
--- a/sys/netpfil/pf/pf_ioctl.c
+++ b/sys/netpfil/pf/pf_ioctl.c
@@ -46,11 +46,14 @@ __FBSDID("$FreeBSD$");
 #include "opt_pf.h"
 
 #include <sys/param.h>
+#include <sys/_bitset.h>
+#include <sys/bitset.h>
 #include <sys/bus.h>
 #include <sys/conf.h>
 #include <sys/endian.h>
 #include <sys/fcntl.h>
 #include <sys/filio.h>
+#include <sys/hash.h>
 #include <sys/interrupt.h>
 #include <sys/jail.h>
 #include <sys/kernel.h>
@@ -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;
-				}
-			}
-		}
-		/* 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);
+		error = pf_altq_ifnet_event_add(ifp, remove, ticket, a2);
+		if (error)
+			break;
 
-			if (ticket != V_ticket_altqs_inactive)
-				error = EBUSY;
+		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;
+		}
+		bcopy(a1, a2, sizeof(struct pf_altq));
 
-			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_altq *q, size_t ioc_size)
 }
 #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,8 +4326,15 @@ 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;
@@ -4241,6 +4401,12 @@ pf_unload_vnet(void)
 	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);
 	counter_u64_free(V_pf_default_rule.states_tot);