Add ALTQ(9) support for the CoDel algorithm.

CoDel is a parameterless queue discipline that handles variable bandwidth
and RTT.

It can be used as the single queue discipline on an interface or as a sub
discipline of existing queue disciplines such as PRIQ, CBQ, HFSC, FAIRQ.

Differential Revision:	https://reviews.freebsd.org/D3272
Reviewd by:	rpaulo, gnn (previous version)
Obtained from:	pfSense
Sponsored by:	Rubicon Communications (Netgate)

4 files changed, 149 insertions, 9 deletions

diff --git a/sbin/pfctl/parse.y b/sbin/pfctl/parse.y
index d352c31..676d768 100644
--- a/sbin/pfctl/parse.y
+++ b/sbin/pfctl/parse.y
@@ -46,6 +46,7 @@ __FBSDID("$FreeBSD$");
 #include <arpa/inet.h>
 #include <net/altq/altq.h>
 #include <net/altq/altq_cbq.h>
+#include <net/altq/altq_codel.h>
 #include <net/altq/altq_priq.h>
 #include <net/altq/altq_hfsc.h>
 #include <net/altq/altq_fairq.h>
@@ -299,7 +300,7 @@ struct pool_opts {
 
 } pool_opts;
 
-
+struct codel_opts	 codel_opts;
 struct node_hfsc_opts	 hfsc_opts;
 struct node_fairq_opts	 fairq_opts;
 struct node_state_opt	*keep_state_defaults = NULL;
@@ -425,6 +426,7 @@ typedef struct {
 		struct pool_opts	 pool_opts;
 		struct node_hfsc_opts	 hfsc_opts;
 		struct node_fairq_opts	 fairq_opts;
+		struct codel_opts	 codel_opts;
 	} v;
 	int lineno;
 } YYSTYPE;
@@ -449,8 +451,8 @@ int	parseport(char *, struct range *r, int);
 %token	REQUIREORDER SYNPROXY FINGERPRINTS NOSYNC DEBUG SKIP HOSTID
 %token	ANTISPOOF FOR INCLUDE
 %token	BITMASK RANDOM SOURCEHASH ROUNDROBIN STATICPORT PROBABILITY
-%token	ALTQ CBQ PRIQ HFSC FAIRQ BANDWIDTH TBRSIZE LINKSHARE REALTIME UPPERLIMIT
-%token	QUEUE PRIORITY QLIMIT HOGS BUCKETS RTABLE
+%token	ALTQ CBQ CODEL PRIQ HFSC FAIRQ BANDWIDTH TBRSIZE LINKSHARE REALTIME
+%token	UPPERLIMIT QUEUE PRIORITY QLIMIT HOGS BUCKETS RTABLE TARGET INTERVAL
 %token	LOAD RULESET_OPTIMIZATION
 %token	STICKYADDRESS MAXSRCSTATES MAXSRCNODES SOURCETRACK GLOBAL RULE
 %token	MAXSRCCONN MAXSRCCONNRATE OVERLOAD FLUSH SLOPPY
@@ -499,6 +501,7 @@ int	parseport(char *, struct range *r, int);
 %type	<v.number>		priqflags_list priqflags_item
 %type	<v.hfsc_opts>		hfscopts_list hfscopts_item hfsc_opts
 %type	<v.fairq_opts>		fairqopts_list fairqopts_item fairq_opts
+%type	<v.codel_opts>		codelopts_list codelopts_item codel_opts
 %type	<v.queue_bwspec>	bandwidth
 %type	<v.filter_opts>		filter_opts filter_opt filter_opts_l
 %type	<v.antispoof_opts>	antispoof_opts antispoof_opt antispoof_opts_l
@@ -1470,7 +1473,7 @@ altqif		: ALTQ interface queue_opts QUEUE qassign {
 			a.scheduler = $3.scheduler.qtype;
 			a.qlimit = $3.qlimit;
 			a.tbrsize = $3.tbrsize;
-			if ($5 == NULL) {
+			if ($5 == NULL && $3.scheduler.qtype != ALTQT_CODEL) {
 				yyerror("no child queues specified");
 				YYERROR;
 			}
@@ -1672,6 +1675,15 @@ scheduler	: CBQ				{
 			$$.qtype = ALTQT_FAIRQ;
 			$$.data.fairq_opts = $3;
 		}
+		| CODEL				{
+			$$.qtype = ALTQT_CODEL;
+			bzero(&$$.data.codel_opts,
+				sizeof(struct codel_opts));
+		}
+		| CODEL '(' codel_opts ')'	{
+			$$.qtype = ALTQT_CODEL;
+			$$.data.codel_opts = $3;
+		}
 		;
 
 cbqflags_list	: cbqflags_item				{ $$ |= $1; }
@@ -1689,6 +1701,8 @@ cbqflags_item	: STRING	{
 				$$ = CBQCLF_RED|CBQCLF_ECN;
 			else if (!strcmp($1, "rio"))
 				$$ = CBQCLF_RIO;
+			else if (!strcmp($1, "codel"))
+				$$ = CBQCLF_CODEL;
 			else {
 				yyerror("unknown cbq flag \"%s\"", $1);
 				free($1);
@@ -1711,6 +1725,8 @@ priqflags_item	: STRING	{
 				$$ = PRCF_RED|PRCF_ECN;
 			else if (!strcmp($1, "rio"))
 				$$ = PRCF_RIO;
+			else if (!strcmp($1, "codel"))
+				$$ = PRCF_CODEL;
 			else {
 				yyerror("unknown priq flag \"%s\"", $1);
 				free($1);
@@ -1811,6 +1827,8 @@ hfscopts_item	: LINKSHARE bandwidth				{
 				hfsc_opts.flags |= HFCF_RED|HFCF_ECN;
 			else if (!strcmp($1, "rio"))
 				hfsc_opts.flags |= HFCF_RIO;
+			else if (!strcmp($1, "codel"))
+				hfsc_opts.flags |= HFCF_CODEL;
 			else {
 				yyerror("unknown hfsc flag \"%s\"", $1);
 				free($1);
@@ -1866,6 +1884,8 @@ fairqopts_item	: LINKSHARE bandwidth				{
 				fairq_opts.flags |= FARF_RED|FARF_ECN;
 			else if (!strcmp($1, "rio"))
 				fairq_opts.flags |= FARF_RIO;
+			else if (!strcmp($1, "codel"))
+				fairq_opts.flags |= FARF_CODEL;
 			else {
 				yyerror("unknown fairq flag \"%s\"", $1);
 				free($1);
@@ -1875,6 +1895,45 @@ fairqopts_item	: LINKSHARE bandwidth				{
 		}
 		;
 
+codel_opts	:	{
+				bzero(&codel_opts,
+				    sizeof(struct codel_opts));
+			}
+		    codelopts_list				{
+			$$ = codel_opts;
+		}
+		;
+
+codelopts_list	: codelopts_item
+		| codelopts_list comma codelopts_item
+		;
+
+codelopts_item	: INTERVAL number				{
+			if (codel_opts.interval) {
+				yyerror("interval already specified");
+				YYERROR;
+			}
+			codel_opts.interval = $2;
+		}
+		| TARGET number					{
+			if (codel_opts.target) {
+				yyerror("target already specified");
+				YYERROR;
+			}
+			codel_opts.target = $2;
+		}
+		| STRING					{
+			if (!strcmp($1, "ecn"))
+				codel_opts.ecn = 1;
+			else {
+				yyerror("unknown codel option \"%s\"", $1);
+				free($1);
+				YYERROR;
+			}
+			free($1);
+		}
+		;
+
 qassign		: /* empty */		{ $$ = NULL; }
 		| qassign_item		{ $$ = $1; }
 		| '{' optnl qassign_list '}'	{ $$ = $3; }
@@ -4800,7 +4859,8 @@ expand_altq(struct pf_altq *a, struct node_if *interfaces,
 
 	if ((pf->loadopt & PFCTL_FLAG_ALTQ) == 0) {
 		FREE_LIST(struct node_if, interfaces);
-		FREE_LIST(struct node_queue, nqueues);
+		if (nqueues)
+			FREE_LIST(struct node_queue, nqueues);
 		return (0);
 	}
 
@@ -4891,7 +4951,8 @@ expand_altq(struct pf_altq *a, struct node_if *interfaces,
 		}
 	);
 	FREE_LIST(struct node_if, interfaces);
-	FREE_LIST(struct node_queue, nqueues);
+	if (nqueues)
+		FREE_LIST(struct node_queue, nqueues);
 
 	return (errs);
 }
@@ -5297,6 +5358,7 @@ lookup(char *s)
 		{ "buckets",		BUCKETS},
 		{ "cbq",		CBQ},
 		{ "code",		CODE},
+		{ "codelq",		CODEL},
 		{ "crop",		FRAGCROP},
 		{ "debug",		DEBUG},
 		{ "divert-reply",	DIVERTREPLY},
@@ -5326,6 +5388,7 @@ lookup(char *s)
 		{ "include",		INCLUDE},
 		{ "inet",		INET},
 		{ "inet6",		INET6},
+		{ "interval",		INTERVAL},
 		{ "keep",		KEEP},
 		{ "label",		LABEL},
 		{ "limit",		LIMIT},
@@ -5395,6 +5458,7 @@ lookup(char *s)
 		{ "table",		TABLE},
 		{ "tag",		TAG},
 		{ "tagged",		TAGGED},
+		{ "target",		TARGET},
 		{ "tbrsize",		TBRSIZE},
 		{ "timeout",		TIMEOUT},
 		{ "to",			TO},
diff --git a/sbin/pfctl/pfctl_altq.c b/sbin/pfctl/pfctl_altq.c
index 2b523fc..6b0443a 100644
--- a/sbin/pfctl/pfctl_altq.c
+++ b/sbin/pfctl/pfctl_altq.c
@@ -40,6 +40,7 @@ __FBSDID("$FreeBSD$");
 
 #include <net/altq/altq.h>
 #include <net/altq/altq_cbq.h>
+#include <net/altq/altq_codel.h>
 #include <net/altq/altq_priq.h>
 #include <net/altq/altq_hfsc.h>
 #include <net/altq/altq_fairq.h>
@@ -60,6 +61,9 @@ static int	cbq_compute_idletime(struct pfctl *, struct pf_altq *);
 static int	check_commit_cbq(int, int, struct pf_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	print_priq_opts(const struct pf_altq *);
@@ -185,6 +189,10 @@ print_altq(const struct pf_altq *a, unsigned int level,
 		if (!print_fairq_opts(a, qopts))
 			printf("fairq ");
 		break;
+	case ALTQT_CODEL:
+		if (!print_codel_opts(a, qopts))
+			printf("codel ");
+		break;
 	}
 
 	if (bw != NULL && bw->bw_percent > 0) {
@@ -591,6 +599,8 @@ print_cbq_opts(const struct pf_altq *a)
 			printf(" ecn");
 		if (opts->flags & CBQCLF_RIO)
 			printf(" rio");
+		if (opts->flags & CBQCLF_CODEL)
+			printf(" codel");
 		if (opts->flags & CBQCLF_CLEARDSCP)
 			printf(" cleardscp");
 		if (opts->flags & CBQCLF_FLOWVALVE)
@@ -678,6 +688,8 @@ print_priq_opts(const struct pf_altq *a)
 			printf(" ecn");
 		if (opts->flags & PRCF_RIO)
 			printf(" rio");
+		if (opts->flags & PRCF_CODEL)
+			printf(" codel");
 		if (opts->flags & PRCF_CLEARDSCP)
 			printf(" cleardscp");
 		if (opts->flags & PRCF_DEFAULTCLASS)
@@ -1010,6 +1022,8 @@ print_hfsc_opts(const struct pf_altq *a, const struct node_queue_opt *qopts)
 			printf(" ecn");
 		if (opts->flags & HFCF_RIO)
 			printf(" rio");
+		if (opts->flags & HFCF_CODEL)
+			printf(" codel");
 		if (opts->flags & HFCF_CLEARDSCP)
 			printf(" cleardscp");
 		if (opts->flags & HFCF_DEFAULTCLASS)
@@ -1032,6 +1046,28 @@ print_hfsc_opts(const struct pf_altq *a, const struct node_queue_opt *qopts)
 }
 
 static int
+print_codel_opts(const struct pf_altq *a, const struct node_queue_opt *qopts)
+{
+	const struct codel_opts *opts;
+
+	opts = &a->pq_u.codel_opts;
+	if (opts->target || opts->interval || opts->ecn) {
+		printf("codel(");
+		if (opts->target)
+			printf(" target %d", opts->target);
+		if (opts->interval)
+			printf(" interval %d", opts->interval);
+		if (opts->ecn)
+			printf("ecn");
+		printf(" ) ");
+
+		return (1);
+	}
+
+	return (0);
+}
+
+static int
 print_fairq_opts(const struct pf_altq *a, const struct node_queue_opt *qopts)
 {
 	const struct fairq_opts		*opts;
@@ -1053,6 +1089,8 @@ print_fairq_opts(const struct pf_altq *a, const struct node_queue_opt *qopts)
 			printf(" ecn");
 		if (opts->flags & FARF_RIO)
 			printf(" rio");
+		if (opts->flags & FARF_CODEL)
+			printf(" codel");
 		if (opts->flags & FARF_CLEARDSCP)
 			printf(" cleardscp");
 		if (opts->flags & FARF_DEFAULTCLASS)
@@ -1404,6 +1442,11 @@ eval_queue_opts(struct pf_altq *pa, struct node_queue_opt *opts,
 			    opts->data.fairq_opts.linkshare.d;
 		}
 		break;
+	case ALTQT_CODEL:
+		pa->pq_u.codel_opts.target = opts->data.codel_opts.target;
+		pa->pq_u.codel_opts.interval = opts->data.codel_opts.interval;
+		pa->pq_u.codel_opts.ecn = opts->data.codel_opts.ecn;
+		break;
 	default:
 		warnx("eval_queue_opts: unknown scheduler type %u",
 		    opts->qtype);
diff --git a/sbin/pfctl/pfctl_parser.h b/sbin/pfctl/pfctl_parser.h
index 8a4e84e..2b7fea7 100644
--- a/sbin/pfctl/pfctl_parser.h
+++ b/sbin/pfctl/pfctl_parser.h
@@ -168,6 +168,7 @@ struct node_queue_opt {
 	int			 qtype;
 	union {
 		struct cbq_opts		cbq_opts;
+		struct codel_opts	codel_opts;
 		struct priq_opts	priq_opts;
 		struct node_hfsc_opts	hfsc_opts;
 		struct node_fairq_opts	fairq_opts;
diff --git a/sbin/pfctl/pfctl_qstats.c b/sbin/pfctl/pfctl_qstats.c
index 2a40d95..3dd9d3a 100644
--- a/sbin/pfctl/pfctl_qstats.c
+++ b/sbin/pfctl/pfctl_qstats.c
@@ -36,6 +36,7 @@ __FBSDID("$FreeBSD$");
 
 #include <net/altq/altq.h>
 #include <net/altq/altq_cbq.h>
+#include <net/altq/altq_codel.h>
 #include <net/altq/altq_priq.h>
 #include <net/altq/altq_hfsc.h>
 #include <net/altq/altq_fairq.h>
@@ -48,6 +49,7 @@ union class_stats {
 	struct priq_classstats	priq_stats;
 	struct hfsc_classstats	hfsc_stats;
 	struct fairq_classstats fairq_stats;
+	struct codel_ifstats	codel_stats;
 };
 
 #define AVGN_MAX	8
@@ -77,6 +79,7 @@ struct pf_altq_node	*pfctl_find_altq_node(struct pf_altq_node *,
 void			 pfctl_print_altq_node(int, const struct pf_altq_node *,
 			    unsigned, int);
 void			 print_cbqstats(struct queue_stats);
+void			 print_codelstats(struct queue_stats);
 void			 print_priqstats(struct queue_stats);
 void			 print_hfscstats(struct queue_stats);
 void			 print_fairqstats(struct queue_stats);
@@ -165,7 +168,7 @@ pfctl_update_qstats(int dev, struct pf_altq_node **root)
 			return (-1);
 		}
 #ifdef __FreeBSD__
-		if (pa.altq.qid > 0 &&
+		if ((pa.altq.qid > 0 || pa.altq.scheduler == ALTQT_CODEL) &&
 		    !(pa.altq.local_flags & PFALTQ_FLAG_IF_REMOVED)) {
 #else
 		if (pa.altq.qid > 0) {
@@ -303,7 +306,7 @@ pfctl_print_altq_node(int dev, const struct pf_altq_node *node,
 void
 pfctl_print_altq_nodestat(int dev, const struct pf_altq_node *a)
 {
-	if (a->altq.qid == 0)
+	if (a->altq.qid == 0 && a->altq.scheduler != ALTQT_CODEL)
 		return;
 
 #ifdef __FreeBSD__
@@ -323,6 +326,9 @@ pfctl_print_altq_nodestat(int dev, const struct pf_altq_node *a)
 	case ALTQT_FAIRQ:
 		print_fairqstats(a->qstats);
 		break;
+	case ALTQT_CODEL:
+		print_codelstats(a->qstats);
+		break;
 	}
 }
 
@@ -348,6 +354,28 @@ print_cbqstats(struct queue_stats cur)
 }
 
 void
+print_codelstats(struct queue_stats cur)
+{
+	printf("  [ pkts: %10llu  bytes: %10llu  "
+	    "dropped pkts: %6llu bytes: %6llu ]\n",
+	    (unsigned long long)cur.data.codel_stats.cl_xmitcnt.packets,
+	    (unsigned long long)cur.data.codel_stats.cl_xmitcnt.bytes,
+	    (unsigned long long)cur.data.codel_stats.cl_dropcnt.packets +
+	    cur.data.codel_stats.stats.drop_cnt.packets,
+	    (unsigned long long)cur.data.codel_stats.cl_dropcnt.bytes +
+	    cur.data.codel_stats.stats.drop_cnt.bytes);
+	printf("  [ qlength: %3d/%3d ]\n",
+	    cur.data.codel_stats.qlength, cur.data.codel_stats.qlimit);
+
+	if (cur.avgn < 2)
+		return;
+
+	printf("  [ measured: %7.1f packets/s, %s/s ]\n",
+	    cur.avg_packets / STAT_INTERVAL,
+	    rate2str((8 * cur.avg_bytes) / STAT_INTERVAL));
+}
+
+void
 print_priqstats(struct queue_stats cur)
 {
 	printf("  [ pkts: %10llu  bytes: %10llu  "
@@ -428,7 +456,7 @@ update_avg(struct pf_altq_node *a)
 	u_int64_t		 b, p;
 	int			 n;
 
-	if (a->altq.qid == 0)
+	if (a->altq.qid == 0 && a->altq.scheduler != ALTQT_CODEL)
 		return;
 
 	qs = &a->qstats;
@@ -451,6 +479,10 @@ update_avg(struct pf_altq_node *a)
 		b = qs->data.fairq_stats.xmit_cnt.bytes;
 		p = qs->data.fairq_stats.xmit_cnt.packets;
 		break;
+	case ALTQT_CODEL:
+		b = qs->data.codel_stats.cl_xmitcnt.bytes;
+		p = qs->data.codel_stats.cl_xmitcnt.packets;
+		break;
 	default:
 		b = 0;
 		p = 0;