Index: sbin/pfctl/pfctl.h
===================================================================
--- sbin/pfctl/pfctl.h
+++ sbin/pfctl/pfctl.h
@@ -114,7 +114,6 @@
 
 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);
Index: sbin/pfctl/pfctl_altq.c
===================================================================
--- sbin/pfctl/pfctl_altq.c
+++ sbin/pfctl/pfctl_altq.c
@@ -24,6 +24,7 @@
 #define PFIOC_USE_LATEST
 
 #include <sys/types.h>
+#include <sys/bitset.h>
 #include <sys/ioctl.h>
 #include <sys/socket.h>
 
@@ -36,6 +37,7 @@
 #include <inttypes.h>
 #include <limits.h>
 #include <math.h>
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -53,33 +55,40 @@
 
 #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 *,
@@ -104,59 +113,101 @@
 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 +366,26 @@
 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 +399,16 @@
     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,16 +425,32 @@
 			    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;
 
+	if (eval_queue_opts(pa, opts,
+		parent == NULL ? pa->ifbandwidth : parent->pa.bandwidth))
+		return (1);
+
 	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);
 
+		/*
+		 * For HFSC, if the linkshare service curve m2 parameter is
+		 * set, it overrides the provided queue bandwidth parameter,
+		 * so adjust the queue bandwidth parameter accordingly here
+		 * to avoid false positives in the total child bandwidth
+		 * check below.
+		 */
+		if ((pa->scheduler == ALTQT_HFSC) &&
+		    (pa->pq_u.hfsc_opts.lssc_m2 != 0)) {
+			pa->bandwidth = pa->pq_u.hfsc_opts.lssc_m2;
+		}
+
 		if (pa->bandwidth > pa->ifbandwidth) {
 			fprintf(stderr, "bandwidth for %s higher than "
 			    "interface\n", pa->qname);
@@ -394,44 +458,36 @@
 		}
 		/* check the sum of the child bandwidth is under parent's */
 		if (parent != NULL) {
-			if (pa->bandwidth > parent->bandwidth) {
+			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;
+			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);
 			}
-			bwsum += pa->bandwidth;
-			if (bwsum > parent->bandwidth) {
-				warnx("the sum of the child bandwidth higher"
-				    " than parent \"%s\"", parent->qname);
-			}
 		}
 	}
 
-	if (eval_queue_opts(pa, opts,
-		parent == NULL ? pa->ifbandwidth : parent->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 +502,7 @@
 #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 +532,11 @@
 	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 +629,20 @@
 }
 
 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 +689,37 @@
  * 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 (if_ppa->meta.default_classes != 1) {
+		warnx("should have one default queue on %s", if_ppa->pa.ifname);
+		return (1);
 	}
-	if (default_class != 1) {
-		warnx("should have one default queue on %s", pa->ifname);
-		error++;
-	}
-	return (error);
+	return (0);
 }
 
 static int
@@ -720,15 +754,15 @@
  * 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 +770,21 @@
 		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 +814,22 @@
 	 * 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 +839,14 @@
 		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 +855,30 @@
 		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,8 +886,19 @@
 		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)
 		opts->lssc_m2 = pa->bandwidth;
@@ -894,122 +914,49 @@
 	 * 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
@@ -1351,8 +1298,7 @@
 	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 +1306,6 @@
 	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 +1316,7 @@
 	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 +1327,6 @@
 #else
 		err(1, "SIOCGIFMTU");
 #endif
-	if (close(s))
-		err(1, "close");
 	if (ifr.ifr_mtu > 0)
 		return (ifr.ifr_mtu);
 	else {
Index: sbin/pfctl/pfctl_parser.h
===================================================================
--- sbin/pfctl/pfctl_parser.h
+++ sbin/pfctl/pfctl_parser.h
@@ -177,6 +177,24 @@
 	}			 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 @@
 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);
Index: sbin/pfctl/pfctl_parser.c
===================================================================
--- sbin/pfctl/pfctl_parser.c
+++ sbin/pfctl/pfctl_parser.c
@@ -50,6 +50,7 @@
 #include <net/pfvar.h>
 #include <arpa/inet.h>
 
+#include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -72,7 +73,6 @@
 		    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 @@
 	{ 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 @@
 
 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 @@
 				    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 @@
 	freeifaddrs(ifap);
 }
 
-int
+static int
 get_socket_domain(void)
 {
 	int sdom;
@@ -1257,31 +1337,54 @@
 	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 @@
 }
 
 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 @@
 		}
 	}
 	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;