MFC r343287:

Reduce pf.conf parsing cost for configs that define N queues from O(N^2) to O(N)

The number of syscalls made during parsing of any config that
defines tables is also reduced, and incorrect warnings that HFSC
parent queue bandwidths were smaller than the sum of their child
bandwidths have been fixed.

Reviewed by:	kp
Sponsored by:	RG Nets
Differential Revision:	https://reviews.freebsd.org/D18759

MFC r343296:
Remove unused function gsc_destroy()

gsc_destroy() is no longer needed as of r343287.

MFC r344025:
Fix the fix added in r343287 for spurious HFSC bandwidth check errors

The logic added in r343287 to avoid false-positive
sum-of-child-bandwidth check errors for HFSC queues has a bug in it
that causes the upperlimit service curve of an HFSC queue to be pulled
down to its parent's linkshare service curve if it happens to be above
it.

Upon further inspection/reflection, this generic
sum-of-child-bandwidths check does not need to be fixed for HFSC - it
needs to be skipped.  For HFSC, the equivalent check is to ensure the
sum of child linkshare service curves are at or below the parent's
linkshare service curve, and this check is already being performed by
eval_pfqueue_hfsc().

This commit reverts the affected parts of r343287 and adds new logic
to skip the generic sum-of-child-bandwidths check for HFSC.

Sponsored by:	RG Nets
Differential Revision:	https://reviews.freebsd.org/D19124

4 files changed, 380 insertions, 341 deletions

diff --git a/sbin/pfctl/pfctl.h b/sbin/pfctl/pfctl.h
index a432f109726a..f43b71e19fec 100644
--- a/sbin/pfctl/pfctl.h
+++ b/sbin/pfctl/pfctl.h
@@ -114,7 +114,6 @@ extern	int loadopt;
 
 int		 check_commit_altq(int, int);
 void		 pfaltq_store(struct pf_altq *);
-struct pf_altq	*pfaltq_lookup(const char *);
 char		*rate2str(double);
 
 void	 print_addr(struct pf_addr_wrap *, sa_family_t, int);
diff --git a/sbin/pfctl/pfctl_altq.c b/sbin/pfctl/pfctl_altq.c
index e9218e0b2d65..f23fe057f703 100644
--- a/sbin/pfctl/pfctl_altq.c
+++ b/sbin/pfctl/pfctl_altq.c
@@ -24,6 +24,7 @@ __FBSDID("$FreeBSD$");
 #define PFIOC_USE_LATEST
 
 #include <sys/types.h>
+#include <sys/bitset.h>
 #include <sys/ioctl.h>
 #include <sys/socket.h>
 
@@ -36,6 +37,7 @@ __FBSDID("$FreeBSD$");
 #include <inttypes.h>
 #include <limits.h>
 #include <math.h>
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -53,38 +55,44 @@ __FBSDID("$FreeBSD$");
 
 #define is_sc_null(sc)	(((sc) == NULL) || ((sc)->m1 == 0 && (sc)->m2 == 0))
 
-static TAILQ_HEAD(altqs, pf_altq) altqs = TAILQ_HEAD_INITIALIZER(altqs);
-static LIST_HEAD(gen_sc, segment) rtsc, lssc;
+static STAILQ_HEAD(interfaces, pfctl_altq) interfaces = STAILQ_HEAD_INITIALIZER(interfaces);
+static struct hsearch_data queue_map;
+static struct hsearch_data if_map;
+static struct hsearch_data qid_map;
 
-struct pf_altq	*qname_to_pfaltq(const char *, const char *);
-u_int32_t	 qname_to_qid(const char *);
+static struct pfctl_altq *pfaltq_lookup(char *ifname);
+static struct pfctl_altq *qname_to_pfaltq(const char *, const char *);
+static u_int32_t	 qname_to_qid(char *);
 
-static int	eval_pfqueue_cbq(struct pfctl *, struct pf_altq *);
+static int	eval_pfqueue_cbq(struct pfctl *, struct pf_altq *,
+		    struct pfctl_altq *);
 static int	cbq_compute_idletime(struct pfctl *, struct pf_altq *);
-static int	check_commit_cbq(int, int, struct pf_altq *);
+static int	check_commit_cbq(int, int, struct pfctl_altq *);
 static int	print_cbq_opts(const struct pf_altq *);
 
 static int	print_codel_opts(const struct pf_altq *,
 		    const struct node_queue_opt *);
 
-static int	eval_pfqueue_priq(struct pfctl *, struct pf_altq *);
-static int	check_commit_priq(int, int, struct pf_altq *);
+static int	eval_pfqueue_priq(struct pfctl *, struct pf_altq *,
+		    struct pfctl_altq *);
+static int	check_commit_priq(int, int, struct pfctl_altq *);
 static int	print_priq_opts(const struct pf_altq *);
 
-static int	eval_pfqueue_hfsc(struct pfctl *, struct pf_altq *);
-static int	check_commit_hfsc(int, int, struct pf_altq *);
+static int	eval_pfqueue_hfsc(struct pfctl *, struct pf_altq *,
+		    struct pfctl_altq *, struct pfctl_altq *);
+static int	check_commit_hfsc(int, int, struct pfctl_altq *);
 static int	print_hfsc_opts(const struct pf_altq *,
 		    const struct node_queue_opt *);
 
-static int	eval_pfqueue_fairq(struct pfctl *, struct pf_altq *);
+static int	eval_pfqueue_fairq(struct pfctl *, struct pf_altq *,
+		    struct pfctl_altq *, struct pfctl_altq *);
 static int	print_fairq_opts(const struct pf_altq *,
 		    const struct node_queue_opt *);
-static int	check_commit_fairq(int, int, struct pf_altq *);
+static int	check_commit_fairq(int, int, struct pfctl_altq *);
 
 static void		 gsc_add_sc(struct gen_sc *, struct service_curve *);
 static int		 is_gsc_under_sc(struct gen_sc *,
 			     struct service_curve *);
-static void		 gsc_destroy(struct gen_sc *);
 static struct segment	*gsc_getentry(struct gen_sc *, double);
 static int		 gsc_add_seg(struct gen_sc *, double, double, double,
 			     double);
@@ -104,59 +112,101 @@ void		 print_hfsc_sc(const char *, u_int, u_int, u_int,
 void		 print_fairq_sc(const char *, u_int, u_int, u_int,
 		     const struct node_fairq_sc *);
 
+static __attribute__((constructor)) void
+pfctl_altq_init(void)
+{
+	/*
+	 * As hdestroy() will never be called on these tables, it will be
+	 * safe to use references into the stored data as keys.
+	 */
+	if (hcreate_r(0, &queue_map) == 0)
+		err(1, "Failed to create altq queue map");
+	if (hcreate_r(0, &if_map) == 0)
+		err(1, "Failed to create altq interface map");
+	if (hcreate_r(0, &qid_map) == 0)
+		err(1, "Failed to create altq queue id map");
+}
+
 void
 pfaltq_store(struct pf_altq *a)
 {
-	struct pf_altq	*altq;
-
+	struct pfctl_altq	*altq;
+	ENTRY 			 item;
+	ENTRY			*ret_item;
+	size_t			 key_size;
+	
 	if ((altq = malloc(sizeof(*altq))) == NULL)
-		err(1, "malloc");
-	memcpy(altq, a, sizeof(struct pf_altq));
-	TAILQ_INSERT_TAIL(&altqs, altq, entries);
+		err(1, "queue malloc");
+	memcpy(&altq->pa, a, sizeof(struct pf_altq));
+	memset(&altq->meta, 0, sizeof(altq->meta));
+
+	if (a->qname[0] == 0) {
+		item.key = altq->pa.ifname;
+		item.data = altq;
+		if (hsearch_r(item, ENTER, &ret_item, &if_map) == 0)
+			err(1, "interface map insert");
+		STAILQ_INSERT_TAIL(&interfaces, altq, meta.link);
+	} else {
+		key_size = sizeof(a->ifname) + sizeof(a->qname);
+		if ((item.key = malloc(key_size)) == NULL)
+			err(1, "queue map key malloc");
+		snprintf(item.key, key_size, "%s:%s", a->ifname, a->qname);
+		item.data = altq;
+		if (hsearch_r(item, ENTER, &ret_item, &queue_map) == 0)
+			err(1, "queue map insert");
+
+		item.key = altq->pa.qname;
+		item.data = &altq->pa.qid;
+		if (hsearch_r(item, ENTER, &ret_item, &qid_map) == 0)
+			err(1, "qid map insert");
+	}
 }
 
-struct pf_altq *
-pfaltq_lookup(const char *ifname)
+static struct pfctl_altq *
+pfaltq_lookup(char *ifname)
 {
-	struct pf_altq	*altq;
+	ENTRY	 item;
+	ENTRY	*ret_item;
 
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(ifname, altq->ifname, IFNAMSIZ) == 0 &&
-		    altq->qname[0] == 0)
-			return (altq);
-	}
-	return (NULL);
+	item.key = ifname;
+	if (hsearch_r(item, FIND, &ret_item, &if_map) == 0)
+		return (NULL);
+
+	return (ret_item->data);
 }
 
-struct pf_altq *
+static struct pfctl_altq *
 qname_to_pfaltq(const char *qname, const char *ifname)
 {
-	struct pf_altq	*altq;
+	ENTRY	 item;
+	ENTRY	*ret_item;
+	char	 key[IFNAMSIZ + PF_QNAME_SIZE];
 
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(ifname, altq->ifname, IFNAMSIZ) == 0 &&
-		    strncmp(qname, altq->qname, PF_QNAME_SIZE) == 0)
-			return (altq);
-	}
-	return (NULL);
+	item.key = key;
+	snprintf(item.key, sizeof(key), "%s:%s", ifname, qname);
+	if (hsearch_r(item, FIND, &ret_item, &queue_map) == 0)
+		return (NULL);
+
+	return (ret_item->data);
 }
 
-u_int32_t
-qname_to_qid(const char *qname)
+static u_int32_t
+qname_to_qid(char *qname)
 {
-	struct pf_altq	*altq;
-
+	ENTRY	 item;
+	ENTRY	*ret_item;
+	uint32_t qid;
+	
 	/*
 	 * We guarantee that same named queues on different interfaces
-	 * have the same qid, so we do NOT need to limit matching on
-	 * one interface!
+	 * have the same qid.
 	 */
+	item.key = qname;
+	if (hsearch_r(item, FIND, &ret_item, &qid_map) == 0)
+		return (0);
 
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(qname, altq->qname, PF_QNAME_SIZE) == 0)
-			return (altq->qid);
-	}
-	return (0);
+	qid = *(uint32_t *)ret_item->data;
+	return (qid);
 }
 
 void
@@ -315,28 +365,26 @@ eval_pfaltq(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw,
 int
 check_commit_altq(int dev, int opts)
 {
-	struct pf_altq	*altq;
-	int		 error = 0;
+	struct pfctl_altq	*if_ppa;
+	int			 error = 0;
 
 	/* call the discipline check for each interface. */
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (altq->qname[0] == 0) {
-			switch (altq->scheduler) {
-			case ALTQT_CBQ:
-				error = check_commit_cbq(dev, opts, altq);
-				break;
-			case ALTQT_PRIQ:
-				error = check_commit_priq(dev, opts, altq);
-				break;
-			case ALTQT_HFSC:
-				error = check_commit_hfsc(dev, opts, altq);
-				break;
-			case ALTQT_FAIRQ:
-				error = check_commit_fairq(dev, opts, altq);
-				break;
-			default:
-				break;
-			}
+	STAILQ_FOREACH(if_ppa, &interfaces, meta.link) {
+		switch (if_ppa->pa.scheduler) {
+		case ALTQT_CBQ:
+			error = check_commit_cbq(dev, opts, if_ppa);
+			break;
+		case ALTQT_PRIQ:
+			error = check_commit_priq(dev, opts, if_ppa);
+			break;
+		case ALTQT_HFSC:
+			error = check_commit_hfsc(dev, opts, if_ppa);
+			break;
+		case ALTQT_FAIRQ:
+			error = check_commit_fairq(dev, opts, if_ppa);
+			break;
+		default:
+			break;
 		}
 	}
 	return (error);
@@ -350,17 +398,16 @@ eval_pfqueue(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw,
     struct node_queue_opt *opts)
 {
 	/* should be merged with expand_queue */
-	struct pf_altq	*if_pa, *parent, *altq;
-	u_int64_t	 bwsum;
-	int		 error = 0;
+	struct pfctl_altq	*if_ppa, *parent;
+	int		 	 error = 0;
 
 	/* find the corresponding interface and copy fields used by queues */
-	if ((if_pa = pfaltq_lookup(pa->ifname)) == NULL) {
+	if ((if_ppa = pfaltq_lookup(pa->ifname)) == NULL) {
 		fprintf(stderr, "altq not defined on %s\n", pa->ifname);
 		return (1);
 	}
-	pa->scheduler = if_pa->scheduler;
-	pa->ifbandwidth = if_pa->ifbandwidth;
+	pa->scheduler = if_ppa->pa.scheduler;
+	pa->ifbandwidth = if_ppa->pa.ifbandwidth;
 
 	if (qname_to_pfaltq(pa->qname, pa->ifname) != NULL) {
 		fprintf(stderr, "queue %s already exists on interface %s\n",
@@ -377,7 +424,7 @@ eval_pfqueue(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw,
 			    pa->parent, pa->qname);
 			return (1);
 		}
-		pa->parent_qid = parent->qid;
+		pa->parent_qid = parent->pa.qid;
 	}
 	if (pa->qlimit == 0)
 		pa->qlimit = DEFAULT_QLIMIT;
@@ -385,53 +432,56 @@ eval_pfqueue(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw,
 	if (pa->scheduler == ALTQT_CBQ || pa->scheduler == ALTQT_HFSC ||
 		pa->scheduler == ALTQT_FAIRQ) {
 		pa->bandwidth = eval_bwspec(bw,
-		    parent == NULL ? pa->ifbandwidth : parent->bandwidth);
+		    parent == NULL ? pa->ifbandwidth : parent->pa.bandwidth);
 
 		if (pa->bandwidth > pa->ifbandwidth) {
 			fprintf(stderr, "bandwidth for %s higher than "
 			    "interface\n", pa->qname);
 			return (1);
 		}
-		/* check the sum of the child bandwidth is under parent's */
-		if (parent != NULL) {
-			if (pa->bandwidth > parent->bandwidth) {
+		/*
+		 * If not HFSC, then check that the sum of the child
+		 * bandwidths is less than the parent's bandwidth.  For
+		 * HFSC, the equivalent concept is to check that the sum of
+		 * the child linkshare service curves are under the parent's
+		 * linkshare service curve, and that check is performed by
+		 * eval_pfqueue_hfsc().
+		 */
+		if ((parent != NULL) && (pa->scheduler != ALTQT_HFSC)) {
+			if (pa->bandwidth > parent->pa.bandwidth) {
 				warnx("bandwidth for %s higher than parent",
 				    pa->qname);
 				return (1);
 			}
-			bwsum = 0;
-			TAILQ_FOREACH(altq, &altqs, entries) {
-				if (strncmp(altq->ifname, pa->ifname,
-				    IFNAMSIZ) == 0 &&
-				    altq->qname[0] != 0 &&
-				    strncmp(altq->parent, pa->parent,
-				    PF_QNAME_SIZE) == 0)
-					bwsum += altq->bandwidth;
-			}
-			bwsum += pa->bandwidth;
-			if (bwsum > parent->bandwidth) {
-				warnx("the sum of the child bandwidth higher"
-				    " than parent \"%s\"", parent->qname);
+			parent->meta.bwsum += pa->bandwidth;
+			if (parent->meta.bwsum > parent->pa.bandwidth) {
+				warnx("the sum of the child bandwidth (%" PRIu64
+				    ") higher than parent \"%s\" (%" PRIu64 ")",
+				    parent->meta.bwsum, parent->pa.qname,
+				    parent->pa.bandwidth);
 			}
 		}
 	}
 
 	if (eval_queue_opts(pa, opts,
-		parent == NULL ? pa->ifbandwidth : parent->bandwidth))
+		parent == NULL ? pa->ifbandwidth : parent->pa.bandwidth))
 		return (1);
 
+	if (parent != NULL)
+		parent->meta.children++;
+	
 	switch (pa->scheduler) {
 	case ALTQT_CBQ:
-		error = eval_pfqueue_cbq(pf, pa);
+		error = eval_pfqueue_cbq(pf, pa, if_ppa);
 		break;
 	case ALTQT_PRIQ:
-		error = eval_pfqueue_priq(pf, pa);
+		error = eval_pfqueue_priq(pf, pa, if_ppa);
 		break;
 	case ALTQT_HFSC:
-		error = eval_pfqueue_hfsc(pf, pa);
+		error = eval_pfqueue_hfsc(pf, pa, if_ppa, parent);
 		break;
 	case ALTQT_FAIRQ:
-		error = eval_pfqueue_fairq(pf, pa);
+		error = eval_pfqueue_fairq(pf, pa, if_ppa, parent);
 		break;
 	default:
 		break;
@@ -446,7 +496,7 @@ eval_pfqueue(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw,
 #define	RM_NS_PER_SEC	(1000000000)
 
 static int
-eval_pfqueue_cbq(struct pfctl *pf, struct pf_altq *pa)
+eval_pfqueue_cbq(struct pfctl *pf, struct pf_altq *pa, struct pfctl_altq *if_ppa)
 {
 	struct cbq_opts	*opts;
 	u_int		 ifmtu;
@@ -476,6 +526,11 @@ eval_pfqueue_cbq(struct pfctl *pf, struct pf_altq *pa)
 	if (pa->parent[0] == 0)
 		opts->flags |= (CBQCLF_ROOTCLASS | CBQCLF_WRR);
 
+	if (pa->pq_u.cbq_opts.flags & CBQCLF_ROOTCLASS)
+		if_ppa->meta.root_classes++;
+	if (pa->pq_u.cbq_opts.flags & CBQCLF_DEFCLASS)
+		if_ppa->meta.default_classes++;
+	
 	cbq_compute_idletime(pf, pa);
 	return (0);
 }
@@ -568,33 +623,20 @@ cbq_compute_idletime(struct pfctl *pf, struct pf_altq *pa)
 }
 
 static int
-check_commit_cbq(int dev, int opts, struct pf_altq *pa)
+check_commit_cbq(int dev, int opts, struct pfctl_altq *if_ppa)
 {
-	struct pf_altq	*altq;
-	int		 root_class, default_class;
-	int		 error = 0;
+	int	error = 0;
 
 	/*
 	 * check if cbq has one root queue and one default queue
 	 * for this interface
 	 */
-	root_class = default_class = 0;
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (altq->pq_u.cbq_opts.flags & CBQCLF_ROOTCLASS)
-			root_class++;
-		if (altq->pq_u.cbq_opts.flags & CBQCLF_DEFCLASS)
-			default_class++;
-	}
-	if (root_class != 1) {
-		warnx("should have one root queue on %s", pa->ifname);
+	if (if_ppa->meta.root_classes != 1) {
+		warnx("should have one root queue on %s", if_ppa->pa.ifname);
 		error++;
 	}
-	if (default_class != 1) {
-		warnx("should have one default queue on %s", pa->ifname);
+	if (if_ppa->meta.default_classes != 1) {
+		warnx("should have one default queue on %s", if_ppa->pa.ifname);
 		error++;
 	}
 	return (error);
@@ -641,51 +683,37 @@ print_cbq_opts(const struct pf_altq *a)
  * PRIQ support functions
  */
 static int
-eval_pfqueue_priq(struct pfctl *pf, struct pf_altq *pa)
+eval_pfqueue_priq(struct pfctl *pf, struct pf_altq *pa, struct pfctl_altq *if_ppa)
 {
-	struct pf_altq	*altq;
 
 	if (pa->priority >= PRIQ_MAXPRI) {
 		warnx("priority out of range: max %d", PRIQ_MAXPRI - 1);
 		return (-1);
 	}
-	/* the priority should be unique for the interface */
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) == 0 &&
-		    altq->qname[0] != 0 && altq->priority == pa->priority) {
-			warnx("%s and %s have the same priority",
-			    altq->qname, pa->qname);
-			return (-1);
-		}
-	}
+	if (BIT_ISSET(QPRI_BITSET_SIZE, pa->priority, &if_ppa->meta.qpris)) {
+		warnx("%s does not have a unique priority on interface %s",
+		    pa->qname, pa->ifname);
+		return (-1);
+	} else
+		BIT_SET(QPRI_BITSET_SIZE, pa->priority, &if_ppa->meta.qpris);
 
+	if (pa->pq_u.priq_opts.flags & PRCF_DEFAULTCLASS)
+		if_ppa->meta.default_classes++;
 	return (0);
 }
 
 static int
-check_commit_priq(int dev, int opts, struct pf_altq *pa)
+check_commit_priq(int dev, int opts, struct pfctl_altq *if_ppa)
 {
-	struct pf_altq	*altq;
-	int		 default_class;
-	int		 error = 0;
 
 	/*
 	 * check if priq has one default class for this interface
 	 */
-	default_class = 0;
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (altq->pq_u.priq_opts.flags & PRCF_DEFAULTCLASS)
-			default_class++;
-	}
-	if (default_class != 1) {
-		warnx("should have one default queue on %s", pa->ifname);
-		error++;
+	if (if_ppa->meta.default_classes != 1) {
+		warnx("should have one default queue on %s", if_ppa->pa.ifname);
+		return (1);
 	}
-	return (error);
+	return (0);
 }
 
 static int
@@ -720,15 +748,15 @@ print_priq_opts(const struct pf_altq *a)
  * HFSC support functions
  */
 static int
-eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa)
+eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa, struct pfctl_altq *if_ppa,
+    struct pfctl_altq *parent)
 {
-	struct pf_altq		*altq, *parent;
 	struct hfsc_opts_v1	*opts;
 	struct service_curve	 sc;
 
 	opts = &pa->pq_u.hfsc_opts;
 
-	if (pa->parent[0] == 0) {
+	if (parent == NULL) {
 		/* root queue */
 		opts->lssc_m1 = pa->ifbandwidth;
 		opts->lssc_m2 = pa->ifbandwidth;
@@ -736,9 +764,21 @@ eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa)
 		return (0);
 	}
 
-	LIST_INIT(&rtsc);
-	LIST_INIT(&lssc);
+	/* First child initializes the parent's service curve accumulators. */
+	if (parent->meta.children == 1) {
+		LIST_INIT(&parent->meta.rtsc);
+		LIST_INIT(&parent->meta.lssc);
+	}
 
+	if (parent->pa.pq_u.hfsc_opts.flags & HFCF_DEFAULTCLASS) {
+		warnx("adding %s would make default queue %s not a leaf",
+		    pa->qname, pa->parent);
+		return (-1);
+	}
+
+	if (pa->pq_u.hfsc_opts.flags & HFCF_DEFAULTCLASS)
+		if_ppa->meta.default_classes++;
+	
 	/* if link_share is not specified, use bandwidth */
 	if (opts->lssc_m2 == 0)
 		opts->lssc_m2 = pa->bandwidth;
@@ -768,51 +808,22 @@ eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa)
 	 * be smaller than the interface bandwidth, and the upper-limit should
 	 * be larger than the real-time service curve when both are defined.
 	 */
-	parent = qname_to_pfaltq(pa->parent, pa->ifname);
-	if (parent == NULL)
-		errx(1, "parent %s not found for %s", pa->parent, pa->qname);
-
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-
-		/* if the class has a real-time service curve, add it. */
-		if (opts->rtsc_m2 != 0 && altq->pq_u.hfsc_opts.rtsc_m2 != 0) {
-			sc.m1 = altq->pq_u.hfsc_opts.rtsc_m1;
-			sc.d = altq->pq_u.hfsc_opts.rtsc_d;
-			sc.m2 = altq->pq_u.hfsc_opts.rtsc_m2;
-			gsc_add_sc(&rtsc, &sc);
-		}
-
-		if (strncmp(altq->parent, pa->parent, PF_QNAME_SIZE) != 0)
-			continue;
-
-		/* if the class has a linkshare service curve, add it. */
-		if (opts->lssc_m2 != 0 && altq->pq_u.hfsc_opts.lssc_m2 != 0) {
-			sc.m1 = altq->pq_u.hfsc_opts.lssc_m1;
-			sc.d = altq->pq_u.hfsc_opts.lssc_d;
-			sc.m2 = altq->pq_u.hfsc_opts.lssc_m2;
-			gsc_add_sc(&lssc, &sc);
-		}
-	}
-
+	
 	/* check the real-time service curve.  reserve 20% of interface bw */
 	if (opts->rtsc_m2 != 0) {
 		/* add this queue to the sum */
 		sc.m1 = opts->rtsc_m1;
 		sc.d = opts->rtsc_d;
 		sc.m2 = opts->rtsc_m2;
-		gsc_add_sc(&rtsc, &sc);
+		gsc_add_sc(&parent->meta.rtsc, &sc);
 		/* compare the sum with 80% of the interface */
 		sc.m1 = 0;
 		sc.d = 0;
 		sc.m2 = pa->ifbandwidth / 100 * 80;
-		if (!is_gsc_under_sc(&rtsc, &sc)) {
+		if (!is_gsc_under_sc(&parent->meta.rtsc, &sc)) {
 			warnx("real-time sc exceeds 80%% of the interface "
 			    "bandwidth (%s)", rate2str((double)sc.m2));
-			goto err_ret;
+			return (-1);
 		}
 	}
 
@@ -822,14 +833,14 @@ eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa)
 		sc.m1 = opts->lssc_m1;
 		sc.d = opts->lssc_d;
 		sc.m2 = opts->lssc_m2;
-		gsc_add_sc(&lssc, &sc);
+		gsc_add_sc(&parent->meta.lssc, &sc);
 		/* compare the sum of the children with parent's sc */
-		sc.m1 = parent->pq_u.hfsc_opts.lssc_m1;
-		sc.d = parent->pq_u.hfsc_opts.lssc_d;
-		sc.m2 = parent->pq_u.hfsc_opts.lssc_m2;
-		if (!is_gsc_under_sc(&lssc, &sc)) {
+		sc.m1 = parent->pa.pq_u.hfsc_opts.lssc_m1;
+		sc.d = parent->pa.pq_u.hfsc_opts.lssc_d;
+		sc.m2 = parent->pa.pq_u.hfsc_opts.lssc_m2;
+		if (!is_gsc_under_sc(&parent->meta.lssc, &sc)) {
 			warnx("linkshare sc exceeds parent's sc");
-			goto err_ret;
+			return (-1);
 		}
 	}
 
@@ -838,38 +849,30 @@ eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa)
 		if (opts->ulsc_m1 > pa->ifbandwidth ||
 		    opts->ulsc_m2 > pa->ifbandwidth) {
 			warnx("upper-limit larger than interface bandwidth");
-			goto err_ret;
+			return (-1);
 		}
 		if (opts->rtsc_m2 != 0 && opts->rtsc_m2 > opts->ulsc_m2) {
 			warnx("upper-limit sc smaller than real-time sc");
-			goto err_ret;
+			return (-1);
 		}
 	}
 
-	gsc_destroy(&rtsc);
-	gsc_destroy(&lssc);
-
 	return (0);
-
-err_ret:
-	gsc_destroy(&rtsc);
-	gsc_destroy(&lssc);
-	return (-1);
 }
 
 /*
  * FAIRQ support functions
  */
 static int
-eval_pfqueue_fairq(struct pfctl *pf __unused, struct pf_altq *pa)
+eval_pfqueue_fairq(struct pfctl *pf __unused, struct pf_altq *pa,
+    struct pfctl_altq *if_ppa, struct pfctl_altq *parent)
 {
-	struct pf_altq		*altq, *parent;
 	struct fairq_opts	*opts;
 	struct service_curve	 sc;
 
 	opts = &pa->pq_u.fairq_opts;
 
-	if (pa->parent[0] == 0) {
+	if (pa->parent == NULL) {
 		/* root queue */
 		opts->lssc_m1 = pa->ifbandwidth;
 		opts->lssc_m2 = pa->ifbandwidth;
@@ -877,7 +880,18 @@ eval_pfqueue_fairq(struct pfctl *pf __unused, struct pf_altq *pa)
 		return (0);
 	}
 
-	LIST_INIT(&lssc);
+	/* First child initializes the parent's service curve accumulator. */
+	if (parent->meta.children == 1)
+		LIST_INIT(&parent->meta.lssc);
+
+	if (parent->pa.pq_u.fairq_opts.flags & FARF_DEFAULTCLASS) {
+		warnx("adding %s would make default queue %s not a leaf",
+		    pa->qname, pa->parent);
+		return (-1);
+	}
+
+	if (pa->pq_u.fairq_opts.flags & FARF_DEFAULTCLASS)
+		if_ppa->meta.default_classes++;
 
 	/* if link_share is not specified, use bandwidth */
 	if (opts->lssc_m2 == 0)
@@ -894,122 +908,49 @@ eval_pfqueue_fairq(struct pfctl *pf __unused, struct pf_altq *pa)
 	 * be smaller than the interface bandwidth, and the upper-limit should
 	 * be larger than the real-time service curve when both are defined.
 	 */
-	parent = qname_to_pfaltq(pa->parent, pa->ifname);
-	if (parent == NULL)
-		errx(1, "parent %s not found for %s", pa->parent, pa->qname);
-
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-
-		if (strncmp(altq->parent, pa->parent, PF_QNAME_SIZE) != 0)
-			continue;
-
-		/* if the class has a link-sharing service curve, add it. */
-		if (opts->lssc_m2 != 0 && altq->pq_u.fairq_opts.lssc_m2 != 0) {
-			sc.m1 = altq->pq_u.fairq_opts.lssc_m1;
-			sc.d = altq->pq_u.fairq_opts.lssc_d;
-			sc.m2 = altq->pq_u.fairq_opts.lssc_m2;
-			gsc_add_sc(&lssc, &sc);
-		}
-	}
 
-	/* check the link-sharing service curve. */
+	/* check the linkshare service curve. */
 	if (opts->lssc_m2 != 0) {
-		sc.m1 = parent->pq_u.fairq_opts.lssc_m1;
-		sc.d = parent->pq_u.fairq_opts.lssc_d;
-		sc.m2 = parent->pq_u.fairq_opts.lssc_m2;
-		if (!is_gsc_under_sc(&lssc, &sc)) {
+		/* add this queue to the child sum */
+		sc.m1 = opts->lssc_m1;
+		sc.d = opts->lssc_d;
+		sc.m2 = opts->lssc_m2;
+		gsc_add_sc(&parent->meta.lssc, &sc);
+		/* compare the sum of the children with parent's sc */
+		sc.m1 = parent->pa.pq_u.fairq_opts.lssc_m1;
+		sc.d = parent->pa.pq_u.fairq_opts.lssc_d;
+		sc.m2 = parent->pa.pq_u.fairq_opts.lssc_m2;
+		if (!is_gsc_under_sc(&parent->meta.lssc, &sc)) {
 			warnx("link-sharing sc exceeds parent's sc");
-			goto err_ret;
+			return (-1);
 		}
 	}
 
-	gsc_destroy(&lssc);
-
 	return (0);
-
-err_ret:
-	gsc_destroy(&lssc);
-	return (-1);
 }
 
 static int
-check_commit_hfsc(int dev, int opts, struct pf_altq *pa)
+check_commit_hfsc(int dev, int opts, struct pfctl_altq *if_ppa)
 {
-	struct pf_altq	*altq, *def = NULL;
-	int		 default_class;
-	int		 error = 0;
 
 	/* check if hfsc has one default queue for this interface */
-	default_class = 0;
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (altq->parent[0] == 0)  /* dummy root */
-			continue;
-		if (altq->pq_u.hfsc_opts.flags & HFCF_DEFAULTCLASS) {
-			default_class++;
-			def = altq;
-		}
-	}
-	if (default_class != 1) {
-		warnx("should have one default queue on %s", pa->ifname);
+	if (if_ppa->meta.default_classes != 1) {
+		warnx("should have one default queue on %s", if_ppa->pa.ifname);
 		return (1);
 	}
-	/* make sure the default queue is a leaf */
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (strncmp(altq->parent, def->qname, PF_QNAME_SIZE) == 0) {
-			warnx("default queue is not a leaf");
-			error++;
-		}
-	}
-	return (error);
+	return (0);
 }
 
 static int
-check_commit_fairq(int dev __unused, int opts __unused, struct pf_altq *pa)
+check_commit_fairq(int dev __unused, int opts __unused, struct pfctl_altq *if_ppa)
 {
-	struct pf_altq	*altq, *def = NULL;
-	int		 default_class;
-	int		 error = 0;
 
 	/* check if fairq has one default queue for this interface */
-	default_class = 0;
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (altq->pq_u.fairq_opts.flags & FARF_DEFAULTCLASS) {
-			default_class++;
-			def = altq;
-		}
-	}
-	if (default_class != 1) {
-		warnx("should have one default queue on %s", pa->ifname);
+	if (if_ppa->meta.default_classes != 1) {
+		warnx("should have one default queue on %s", if_ppa->pa.ifname);
 		return (1);
 	}
-	/* make sure the default queue is a leaf */
-	TAILQ_FOREACH(altq, &altqs, entries) {
-		if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0)
-			continue;
-		if (altq->qname[0] == 0)  /* this is for interface */
-			continue;
-		if (strncmp(altq->parent, def->qname, PF_QNAME_SIZE) == 0) {
-			warnx("default queue is not a leaf");
-			error++;
-		}
-	}
-	return (error);
+	return (0);
 }
 
 static int
@@ -1182,17 +1123,6 @@ is_gsc_under_sc(struct gen_sc *gsc, struct service_curve *sc)
 	return (1);
 }
 
-static void
-gsc_destroy(struct gen_sc *gsc)
-{
-	struct segment	*s;
-
-	while ((s = LIST_FIRST(gsc)) != NULL) {
-		LIST_REMOVE(s, _next);
-		free(s);
-	}
-}
-
 /*
  * return a segment entry starting at x.
  * if gsc has no entry starting at x, a new entry is created at x.
@@ -1351,8 +1281,7 @@ getifspeed(char *ifname)
 	struct ifreq	ifr;
 	struct if_data	ifrdat;
 
-	if ((s = socket(get_socket_domain(), SOCK_DGRAM, 0)) < 0)
-		err(1, "socket");
+	s = get_query_socket();
 	bzero(&ifr, sizeof(ifr));
 	if (strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name)) >=
 	    sizeof(ifr.ifr_name))
@@ -1360,8 +1289,6 @@ getifspeed(char *ifname)
 	ifr.ifr_data = (caddr_t)&ifrdat;
 	if (ioctl(s, SIOCGIFDATA, (caddr_t)&ifr) == -1)
 		err(1, "SIOCGIFDATA");
-	if (close(s))
-		err(1, "close");
 	return ((u_int32_t)ifrdat.ifi_baudrate);
 }
 #endif
@@ -1372,8 +1299,7 @@ getifmtu(char *ifname)
 	int		s;
 	struct ifreq	ifr;
 
-	if ((s = socket(get_socket_domain(), SOCK_DGRAM, 0)) < 0)
-		err(1, "socket");
+	s = get_query_socket();
 	bzero(&ifr, sizeof(ifr));
 	if (strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name)) >=
 	    sizeof(ifr.ifr_name))
@@ -1384,8 +1310,6 @@ getifmtu(char *ifname)
 #else
 		err(1, "SIOCGIFMTU");
 #endif
-	if (close(s))
-		err(1, "close");
 	if (ifr.ifr_mtu > 0)
 		return (ifr.ifr_mtu);
 	else {
diff --git a/sbin/pfctl/pfctl_parser.c b/sbin/pfctl/pfctl_parser.c
index aa44b4d6da3c..1575a6fa2338 100644
--- a/sbin/pfctl/pfctl_parser.c
+++ b/sbin/pfctl/pfctl_parser.c
@@ -50,6 +50,7 @@ __FBSDID("$FreeBSD$");
 #include <net/pfvar.h>
 #include <arpa/inet.h>
 
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -72,7 +73,6 @@ void		 print_fromto(struct pf_rule_addr *, pf_osfp_t,
 		    struct pf_rule_addr *, u_int8_t, u_int8_t, int, int);
 int		 ifa_skip_if(const char *filter, struct node_host *p);
 
-struct node_host	*ifa_grouplookup(const char *, int);
 struct node_host	*host_if(const char *, int);
 struct node_host	*host_v4(const char *, int);
 struct node_host	*host_v6(const char *, int);
@@ -209,6 +209,19 @@ const struct pf_timeout pf_timeouts[] = {
 	{ NULL,			0 }
 };
 
+static struct hsearch_data isgroup_map;
+
+static __attribute__((constructor)) void
+pfctl_parser_init(void)
+{
+	/*
+	 * As hdestroy() will never be called on these tables, it will be
+	 * safe to use references into the stored data as keys.
+	 */
+	if (hcreate_r(0, &isgroup_map) == 0)
+		err(1, "Failed to create interface group query response map");
+}
+
 const struct icmptypeent *
 geticmptypebynumber(u_int8_t type, sa_family_t af)
 {
@@ -1153,6 +1166,71 @@ check_netmask(struct node_host *h, sa_family_t af)
 
 static struct node_host	*iftab;
 
+/*
+ * Retrieve the list of groups this interface is a member of and make sure
+ * each group is in the group map.
+ */
+static void
+ifa_add_groups_to_map(char *ifa_name)
+{
+	int			 s, len;
+	struct ifgroupreq	 ifgr;
+	struct ifg_req		*ifg;
+
+	s = get_query_socket();
+
+	/* Get size of group list for this interface */
+	memset(&ifgr, 0, sizeof(ifgr));
+	strlcpy(ifgr.ifgr_name, ifa_name, IFNAMSIZ);
+	if (ioctl(s, SIOCGIFGROUP, (caddr_t)&ifgr) == -1)
+		err(1, "SIOCGIFGROUP");
+
+	/* Retrieve group list for this interface */
+	len = ifgr.ifgr_len;
+	ifgr.ifgr_groups =
+	    (struct ifg_req *)calloc(len / sizeof(struct ifg_req),
+		sizeof(struct ifg_req));
+	if (ifgr.ifgr_groups == NULL)
+		err(1, "calloc");
+	if (ioctl(s, SIOCGIFGROUP, (caddr_t)&ifgr) == -1)
+		err(1, "SIOCGIFGROUP");
+
+	ifg = ifgr.ifgr_groups;
+	for (; ifg && len >= sizeof(struct ifg_req); ifg++) {
+		len -= sizeof(struct ifg_req);
+		if (strcmp(ifg->ifgrq_group, "all")) {
+			ENTRY	 		 item;
+			ENTRY			*ret_item;
+			int			*answer;
+	
+			item.key = ifg->ifgrq_group;
+			if (hsearch_r(item, FIND, &ret_item, &isgroup_map) == 0) {
+				struct ifgroupreq	 ifgr2;
+
+				/* Don't know the answer yet */
+				if ((answer = malloc(sizeof(int))) == NULL)
+					err(1, "malloc");
+
+				bzero(&ifgr2, sizeof(ifgr2));
+				strlcpy(ifgr2.ifgr_name, ifg->ifgrq_group,
+				    sizeof(ifgr2.ifgr_name));
+				if (ioctl(s, SIOCGIFGMEMB, (caddr_t)&ifgr2) == 0)
+					*answer = ifgr2.ifgr_len;
+				else
+					*answer = 0;
+
+				item.key = strdup(ifg->ifgrq_group);
+				item.data = answer;
+				if (hsearch_r(item, ENTER, &ret_item,
+					&isgroup_map) == 0)
+					err(1, "interface group query response"
+					    " map insert");
+			}
+		}
+	}
+	free(ifgr.ifgr_groups);
+}
+
 void
 ifa_load(void)
 {
@@ -1220,6 +1298,8 @@ ifa_load(void)
 				    sizeof(struct in6_addr));
 			n->ifindex = ((struct sockaddr_in6 *)
 			    ifa->ifa_addr)->sin6_scope_id;
+		} else if (n->af == AF_LINK) {
+			ifa_add_groups_to_map(ifa->ifa_name);
 		}
 		if ((n->ifname = strdup(ifa->ifa_name)) == NULL)
 			err(1, "ifa_load: strdup");
@@ -1237,7 +1317,7 @@ ifa_load(void)
 	freeifaddrs(ifap);
 }
 
-int
+static int
 get_socket_domain(void)
 {
 	int sdom;
@@ -1257,31 +1337,54 @@ get_socket_domain(void)
 	return (sdom);
 }
 
+int
+get_query_socket(void)
+{
+	static int s = -1;
+
+	if (s == -1) {
+		if ((s = socket(get_socket_domain(), SOCK_DGRAM, 0)) == -1)
+			err(1, "socket");
+	}
+
+	return (s);
+}
+
+/*
+ * Returns the response len if the name is a group, otherwise returns 0.
+ */
+static int
+is_a_group(char *name)
+{
+	ENTRY	 		 item;
+	ENTRY			*ret_item;
+	
+	item.key = name;
+	if (hsearch_r(item, FIND, &ret_item, &isgroup_map) == 0)
+		return (0);
+
+	return (*(int *)ret_item->data);
+}
+
 struct node_host *
-ifa_exists(const char *ifa_name)
+ifa_exists(char *ifa_name)
 {
 	struct node_host	*n;
-	struct ifgroupreq	ifgr;
 	int			s;
 
 	if (iftab == NULL)
 		ifa_load();
 
-	/* check wether this is a group */
-	if ((s = socket(get_socket_domain(), SOCK_DGRAM, 0)) == -1)
-		err(1, "socket");
-	bzero(&ifgr, sizeof(ifgr));
-	strlcpy(ifgr.ifgr_name, ifa_name, sizeof(ifgr.ifgr_name));
-	if (ioctl(s, SIOCGIFGMEMB, (caddr_t)&ifgr) == 0) {
+	/* check whether this is a group */
+	s = get_query_socket();
+	if (is_a_group(ifa_name)) {
 		/* fake a node_host */
 		if ((n = calloc(1, sizeof(*n))) == NULL)
 			err(1, "calloc");
 		if ((n->ifname = strdup(ifa_name)) == NULL)
 			err(1, "strdup");
-		close(s);
 		return (n);
 	}
-	close(s);
 
 	for (n = iftab; n; n = n->next) {
 		if (n->af == AF_LINK && !strncmp(n->ifname, ifa_name, IFNAMSIZ))
@@ -1292,23 +1395,19 @@ ifa_exists(const char *ifa_name)
 }
 
 struct node_host *
-ifa_grouplookup(const char *ifa_name, int flags)
+ifa_grouplookup(char *ifa_name, int flags)
 {
 	struct ifg_req		*ifg;
 	struct ifgroupreq	 ifgr;
 	int			 s, len;
 	struct node_host	*n, *h = NULL;
 
-	if ((s = socket(get_socket_domain(), SOCK_DGRAM, 0)) == -1)
-		err(1, "socket");
+	s = get_query_socket();
+	len = is_a_group(ifa_name);
+	if (len == 0)
+		return (NULL);
 	bzero(&ifgr, sizeof(ifgr));
 	strlcpy(ifgr.ifgr_name, ifa_name, sizeof(ifgr.ifgr_name));
-	if (ioctl(s, SIOCGIFGMEMB, (caddr_t)&ifgr) == -1) {
-		close(s);
-		return (NULL);
-	}
-
-	len = ifgr.ifgr_len;
 	if ((ifgr.ifgr_groups = calloc(1, len)) == NULL)
 		err(1, "calloc");
 	if (ioctl(s, SIOCGIFGMEMB, (caddr_t)&ifgr) == -1)
@@ -1327,13 +1426,12 @@ ifa_grouplookup(const char *ifa_name, int flags)
 		}
 	}
 	free(ifgr.ifgr_groups);
-	close(s);
 
 	return (h);
 }
 
 struct node_host *
-ifa_lookup(const char *ifa_name, int flags)
+ifa_lookup(char *ifa_name, int flags)
 {
 	struct node_host	*p = NULL, *h = NULL, *n = NULL;
 	int			 got4 = 0, got6 = 0;
diff --git a/sbin/pfctl/pfctl_parser.h b/sbin/pfctl/pfctl_parser.h
index 05ebdf29f6fc..aa6d98d7cf91 100644
--- a/sbin/pfctl/pfctl_parser.h
+++ b/sbin/pfctl/pfctl_parser.h
@@ -177,6 +177,24 @@ struct node_queue_opt {
 	}			 data;
 };
 
+#define QPRI_BITSET_SIZE	256
+BITSET_DEFINE(qpri_bitset, QPRI_BITSET_SIZE);
+LIST_HEAD(gen_sc, segment);
+
+struct pfctl_altq {
+	struct pf_altq	pa;
+	struct {
+		STAILQ_ENTRY(pfctl_altq)	link;
+		u_int64_t			bwsum;
+		struct qpri_bitset		qpris;
+		int				children;
+		int				root_classes;
+		int				default_classes;
+		struct gen_sc			lssc;
+		struct gen_sc			rtsc;
+	} meta;
+};
+
 #ifdef __FreeBSD__
 /*
  * XXX
@@ -313,10 +331,10 @@ void			 set_ipmask(struct node_host *, u_int8_t);
 int			 check_netmask(struct node_host *, sa_family_t);
 int			 unmask(struct pf_addr *, sa_family_t);
 void			 ifa_load(void);
-int			 get_socket_domain(void);
-struct node_host	*ifa_exists(const char *);
-struct node_host	*ifa_grouplookup(const char *ifa_name, int flags);
-struct node_host	*ifa_lookup(const char *, int);
+int			 get_query_socket(void);
+struct node_host	*ifa_exists(char *);
+struct node_host	*ifa_grouplookup(char *ifa_name, int flags);
+struct node_host	*ifa_lookup(char *, int);
 struct node_host	*host(const char *);
 
 int			 append_addr(struct pfr_buffer *, char *, int);