svn commit: r287009 - in head: sbin/pfctl share/man/man4 sys/conf sys/net/altq sys/netpfil/pf
Ermal Luçi
ermal.luci at gmail.com
Sat Aug 22 09:18:39 UTC 2015
On Sat, Aug 22, 2015 at 12:02 AM, Luiz Otavio O Souza <loos at freebsd.org>
wrote:
> Author: loos
> Date: Fri Aug 21 22:02:22 2015
> New Revision: 287009
> URL: https://svnweb.freebsd.org/changeset/base/287009
>
> Log:
> 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)
>
I thought part of this commit message was taken from me as a reviewer, no?
> Obtained from: pfSense
> Sponsored by: Rubicon Communications (Netgate)
>
> Added:
> head/sys/net/altq/altq_codel.c (contents, props changed)
> head/sys/net/altq/altq_codel.h (contents, props changed)
> Modified:
> head/sbin/pfctl/parse.y
> head/sbin/pfctl/pfctl_altq.c
> head/sbin/pfctl/pfctl_parser.h
> head/sbin/pfctl/pfctl_qstats.c
> head/share/man/man4/altq.4
> head/sys/conf/files
> head/sys/conf/options
> head/sys/net/altq/altq.h
> head/sys/net/altq/altq_cbq.c
> head/sys/net/altq/altq_cbq.h
> head/sys/net/altq/altq_classq.h
> head/sys/net/altq/altq_fairq.c
> head/sys/net/altq/altq_fairq.h
> head/sys/net/altq/altq_hfsc.c
> head/sys/net/altq/altq_hfsc.h
> head/sys/net/altq/altq_priq.c
> head/sys/net/altq/altq_priq.h
> head/sys/net/altq/altq_rmclass.c
> head/sys/net/altq/altq_rmclass.h
> head/sys/net/altq/altq_subr.c
> head/sys/net/altq/altq_var.h
> head/sys/netpfil/pf/pf_altq.h
>
> Modified: head/sbin/pfctl/parse.y
>
> ==============================================================================
> --- head/sbin/pfctl/parse.y Fri Aug 21 21:47:29 2015 (r287008)
> +++ head/sbin/pfctl/parse.y Fri Aug 21 22:02:22 2015 (r287009)
> @@ -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, i
> %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, i
> %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 QUEU
> 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 no
>
> 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 no
> }
> );
> 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},
>
> Modified: head/sbin/pfctl/pfctl_altq.c
>
> ==============================================================================
> --- head/sbin/pfctl/pfctl_altq.c Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sbin/pfctl/pfctl_altq.c Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -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 p
> 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, unsi
> 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,
> 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,
> }
>
> 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
> 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, stru
> 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);
>
> Modified: head/sbin/pfctl/pfctl_parser.h
>
> ==============================================================================
> --- head/sbin/pfctl/pfctl_parser.h Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sbin/pfctl/pfctl_parser.h Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -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;
>
> Modified: head/sbin/pfctl/pfctl_qstats.c
>
> ==============================================================================
> --- head/sbin/pfctl/pfctl_qstats.c Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sbin/pfctl/pfctl_qstats.c Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -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_nod
> 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_a
> 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 str
> 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
> 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;
>
> Modified: head/share/man/man4/altq.4
>
> ==============================================================================
> --- head/share/man/man4/altq.4 Fri Aug 21 21:47:29 2015 (r287008)
> +++ head/share/man/man4/altq.4 Fri Aug 21 22:02:22 2015 (r287009)
> @@ -25,7 +25,7 @@
> .\"
> .\" $FreeBSD$
> .\"
> -.Dd June 24, 2015
> +.Dd July 24, 2015
> .Dt ALTQ 4
> .Os
> .Sh NAME
> @@ -35,6 +35,7 @@
> .Cd options ALTQ
> .Pp
> .Cd options ALTQ_CBQ
> +.Cd options ALTQ_CODEL
> .Cd options ALTQ_RED
> .Cd options ALTQ_RIO
> .Cd options ALTQ_HFSC
> @@ -74,6 +75,10 @@ Enable
> Build the
> .Dq "Class Based Queuing"
> discipline.
> +.It Dv ALTQ_CODEL
> +Build the
> +.Dq "Controlled Delay"
> +discipline.
> .It Dv ALTQ_RED
> Build the
> .Dq "Random Early Detection"
>
> Modified: head/sys/conf/files
>
> ==============================================================================
> --- head/sys/conf/files Fri Aug 21 21:47:29 2015 (r287008)
> +++ head/sys/conf/files Fri Aug 21 22:02:22 2015 (r287009)
> @@ -3429,6 +3429,7 @@ libkern/zlib.c optional crypto |
> geom_
> ddb_ctf | gzio | geom_uncompress
> net/altq/altq_cbq.c optional altq
> net/altq/altq_cdnr.c optional altq
> +net/altq/altq_codel.c optional altq
> net/altq/altq_hfsc.c optional altq
> net/altq/altq_fairq.c optional altq
> net/altq/altq_priq.c optional altq
>
> Modified: head/sys/conf/options
>
> ==============================================================================
> --- head/sys/conf/options Fri Aug 21 21:47:29 2015 (r287008)
> +++ head/sys/conf/options Fri Aug 21 22:02:22 2015 (r287009)
> @@ -388,6 +388,7 @@ ACCEPT_FILTER_HTTP
> ALTQ opt_global.h
> ALTQ_CBQ opt_altq.h
> ALTQ_CDNR opt_altq.h
> +ALTQ_CODEL opt_altq.h
> ALTQ_DEBUG opt_altq.h
> ALTQ_HFSC opt_altq.h
> ALTQ_FAIRQ opt_altq.h
>
> Modified: head/sys/net/altq/altq.h
>
> ==============================================================================
> --- head/sys/net/altq/altq.h Fri Aug 21 21:47:29 2015 (r287008)
> +++ head/sys/net/altq/altq.h Fri Aug 21 22:02:22 2015 (r287009)
> @@ -64,7 +64,8 @@
> #define ALTQT_PRIQ 11 /* priority queue */
> #define ALTQT_JOBS 12 /* JoBS */
> #define ALTQT_FAIRQ 13 /* fairq */
> -#define ALTQT_MAX 14 /* should be max
> discipline type + 1 */
> +#define ALTQT_CODEL 14 /* CoDel */
> +#define ALTQT_MAX 15 /* should be max
> discipline type + 1 */
>
> #ifdef ALTQ3_COMPAT
> struct altqreq {
>
> Modified: head/sys/net/altq/altq_cbq.c
>
> ==============================================================================
> --- head/sys/net/altq/altq_cbq.c Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sys/net/altq/altq_cbq.c Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -237,6 +237,10 @@ get_class_stats(class_stats_t *statsp, s
> if (q_is_rio(cl->q_))
> rio_getstats((rio_t *)cl->red_, &statsp->red[0]);
> #endif
> +#ifdef ALTQ_CODEL
> + if (q_is_codel(cl->q_))
> + codel_getstats(cl->codel_, &statsp->codel);
> +#endif
> }
>
> int
>
> Modified: head/sys/net/altq/altq_cbq.h
>
> ==============================================================================
> --- head/sys/net/altq/altq_cbq.h Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sys/net/altq/altq_cbq.h Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -36,6 +36,7 @@
>
> #include <net/altq/altq.h>
> #include <net/altq/altq_rmclass.h>
> +#include <net/altq/altq_codel.h>
> #include <net/altq/altq_red.h>
> #include <net/altq/altq_rio.h>
>
> @@ -52,6 +53,7 @@ extern "C" {
> #define CBQCLF_FLOWVALVE 0x0008 /* use flowvalve (aka
> penalty-box) */
> #define CBQCLF_CLEARDSCP 0x0010 /* clear diffserv
> codepoint */
> #define CBQCLF_BORROW 0x0020 /* borrow from parent */
> +#define CBQCLF_CODEL 0x0040 /* use CoDel */
>
> /* class flags only for root class */
> #define CBQCLF_WRR 0x0100 /* weighted-round robin */
> @@ -91,9 +93,10 @@ typedef struct _cbq_class_stats_ {
> int qcnt; /* # packets in queue */
> int avgidle;
>
> - /* red and rio related info */
> + /* codel, red and rio related info */
> int qtype;
> struct redstats red[3];
> + struct codel_stats codel;
> } class_stats_t;
>
> #ifdef ALTQ3_COMPAT
>
> Modified: head/sys/net/altq/altq_classq.h
>
> ==============================================================================
> --- head/sys/net/altq/altq_classq.h Fri Aug 21 21:47:29 2015
> (r287008)
> +++ head/sys/net/altq/altq_classq.h Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -50,6 +50,7 @@ extern "C" {
> #define Q_RED 0x01
> #define Q_RIO 0x02
> #define Q_DROPTAIL 0x03
> +#define Q_CODEL 0x04
>
> #ifdef _KERNEL
>
> @@ -60,6 +61,7 @@ struct _class_queue_ {
> struct mbuf *tail_; /* Tail of packet queue */
> int qlen_; /* Queue length (in number of packets) */
> int qlim_; /* Queue limit (in number of packets*) */
> + int qsize_; /* Queue size (in number of bytes*) */
> int qtype_; /* Queue type */
> };
>
> @@ -68,10 +70,12 @@ typedef struct _class_queue_ class_queue
> #define qtype(q) (q)->qtype_ /* Get queue type
> */
> #define qlimit(q) (q)->qlim_ /* Max packets to
> be queued */
> #define qlen(q) (q)->qlen_ /* Current queue
> length. */
> +#define qsize(q) (q)->qsize_ /* Current queue
> size. */
> #define qtail(q) (q)->tail_ /* Tail of the
> queue */
> #define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL)
>
> #define qempty(q) ((q)->qlen_ == 0) /* Is the queue
> empty?? */
> +#define q_is_codel(q) ((q)->qtype_ == Q_CODEL) /* Is the queue a
> codel queue */
> #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a
> red queue */
> #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a
> rio queue */
> #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED ||
> (q)->qtype_ == Q_RIO)
> @@ -101,6 +105,7 @@ _addq(class_queue_t *q, struct mbuf *m)
> m0->m_nextpkt = m;
> qtail(q) = m;
> qlen(q)++;
> + qsize(q) += m_pktlen(m);
> }
>
> static __inline struct mbuf *
> @@ -115,6 +120,7 @@ _getq(class_queue_t *q)
> else
> qtail(q) = NULL;
> qlen(q)--;
> + qsize(q) -= m_pktlen(m0);
> m0->m_nextpkt = NULL;
> return (m0);
> }
>
> Added: head/sys/net/altq/altq_codel.c
>
> ==============================================================================
> --- /dev/null 00:00:00 1970 (empty, because file is newly added)
> +++ head/sys/net/altq/altq_codel.c Fri Aug 21 22:02:22 2015
> (r287009)
> @@ -0,0 +1,477 @@
> +/*
> + * CoDel - The Controlled-Delay Active Queue Management algorithm
> + *
> + * Copyright (C) 2013 Ermal Luci <eri at FreeBSD.org>
>
Can you correct my name?
> + * Copyright (C) 2011-2012 Kathleen Nichols <nichols at pollere.com>
> + * Copyright (C) 2011-2012 Van Jacobson <van at pollere.net>
> + * Copyright (C) 2012 Michael D. Taht <dave.taht at bufferbloat.net>
> + * Copyright (C) 2012 Eric Dumazet <edumazet at google.com>
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions
> + * are met:
> + * 1. Redistributions of source code must retain the above copyright
> + * notice, this list of conditions, and the following disclaimer,
> + * without modification.
> + * 2. Redistributions in binary form must reproduce the above copyright
> + * notice, this list of conditions and the following disclaimer in the
> + * documentation and/or other materials provided with the distribution.
> + * 3. The names of the authors may not be used to endorse or promote
> products
> + * derived from this software without specific prior written
> permission.
> + *
> + * Alternatively, provided that this notice is retained in full, this
> + * software may be distributed under the terms of the GNU General
> + * Public License ("GPL") version 2, in which case the provisions of the
> + * GPL apply INSTEAD OF those given above.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
> + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
> + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
> + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
> + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
> + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
> + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> + * DAMAGE.
> + *
> + * $FreeBSD$
> + */
> +#include "opt_altq.h"
> +#include "opt_inet.h"
> +#include "opt_inet6.h"
> +
> +#ifdef ALTQ_CODEL /* CoDel is enabled by ALTQ_CODEL option in opt_altq.h
> */
> +
> +#include <sys/param.h>
> +#include <sys/malloc.h>
> +#include <sys/mbuf.h>
> +#include <sys/socket.h>
> +#include <sys/systm.h>
> +
> +#include <net/if.h>
> +#include <net/if_var.h>
> +#include <netinet/in.h>
> +
> +#include <netpfil/pf/pf.h>
> +#include <netpfil/pf/pf_altq.h>
> +#include <net/altq/if_altq.h>
> +#include <net/altq/altq.h>
> +#include <net/altq/altq_codel.h>
> +
> +static int codel_should_drop(struct codel *, class_queue_t *,
> + struct mbuf *, u_int64_t);
> +static void codel_Newton_step(struct codel_vars *);
> +static u_int64_t codel_control_law(u_int64_t t, u_int64_t,
> u_int32_t);
> +
> +#define codel_time_after(a, b) ((int64_t)(a) -
> (int64_t)(b) > 0)
> +#define codel_time_after_eq(a, b) ((int64_t)(a) -
> (int64_t)(b) >= 0)
> +#define codel_time_before(a, b) ((int64_t)(a) -
> (int64_t)(b) < 0)
> +#define codel_time_before_eq(a, b) ((int64_t)(a) -
> (int64_t)(b) <= 0)
> +
> +static int codel_request(struct ifaltq *, int, void *);
> +
> +static int codel_enqueue(struct ifaltq *, struct mbuf *, struct
> altq_pktattr *);
> +static struct mbuf *codel_dequeue(struct ifaltq *, int);
> +
> +int
> +codel_pfattach(struct pf_altq *a)
> +{
> + struct ifnet *ifp;
> +
> + if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL)
> + return (EINVAL);
> +
> + return (altq_attach(&ifp->if_snd, ALTQT_CODEL, a->altq_disc,
> + codel_enqueue, codel_dequeue, codel_request, NULL, NULL));
> +}
> +
> +int
> +codel_add_altq(struct pf_altq *a)
> +{
> + struct codel_if *cif;
> + struct ifnet *ifp;
> + struct codel_opts *opts;
> +
> + if ((ifp = ifunit(a->ifname)) == NULL)
> + return (EINVAL);
> + if (!ALTQ_IS_READY(&ifp->if_snd))
> + return (ENODEV);
> +
> + opts = &a->pq_u.codel_opts;
> +
> + cif = malloc(sizeof(struct codel_if), M_DEVBUF, M_NOWAIT | M_ZERO);
> + if (cif == NULL)
> + return (ENOMEM);
> + cif->cif_bandwidth = a->ifbandwidth;
> + cif->cif_ifq = &ifp->if_snd;
> +
> + cif->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, M_NOWAIT |
> M_ZERO);
> + if (cif->cl_q == NULL) {
> + free(cif, M_DEVBUF);
> + return (ENOMEM);
> + }
> +
> + if (a->qlimit == 0)
> + a->qlimit = 50; /* use default. */
> + qlimit(cif->cl_q) = a->qlimit;
> + qtype(cif->cl_q) = Q_CODEL;
> + qlen(cif->cl_q) = 0;
> + qsize(cif->cl_q) = 0;
> +
> + if (opts->target == 0)
> + opts->target = 5;
> + if (opts->interval == 0)
> + opts->interval = 100;
> + cif->codel.params.target = machclk_freq * opts->target / 1000;
> + cif->codel.params.interval = machclk_freq * opts->interval / 1000;
> + cif->codel.params.ecn = opts->ecn;
> + cif->codel.stats.maxpacket = 256;
> +
> + cif->cl_stats.qlength = qlen(cif->cl_q);
> + cif->cl_stats.qlimit = qlimit(cif->cl_q);
> +
> + /* keep the state in pf_altq */
> + a->altq_disc = cif;
> +
> + return (0);
> +}
> +
> +int
> +codel_remove_altq(struct pf_altq *a)
> +{
> + struct codel_if *cif;
> +
> + if ((cif = a->altq_disc) == NULL)
> + return (EINVAL);
> + a->altq_disc = NULL;
> +
> + if (cif->cl_q)
> + free(cif->cl_q, M_DEVBUF);
> + free(cif, M_DEVBUF);
> +
> + return (0);
> +}
> +
> +int
> +codel_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
> +{
> + struct codel_if *cif;
> + struct codel_ifstats stats;
> + int error = 0;
> +
> + if ((cif = altq_lookup(a->ifname, ALTQT_CODEL)) == NULL)
> + return (EBADF);
> +
> + if (*nbytes < sizeof(stats))
> + return (EINVAL);
> +
> + stats = cif->cl_stats;
> + stats.stats = cif->codel.stats;
> +
> + if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0)
> + return (error);
> + *nbytes = sizeof(stats);
> +
> + return (0);
> +}
> +
> +static int
> +codel_request(struct ifaltq *ifq, int req, void *arg)
> +{
> + struct codel_if *cif = (struct codel_if *)ifq->altq_disc;
> + struct mbuf *m;
> +
> + IFQ_LOCK_ASSERT(ifq);
> +
> + switch (req) {
> + case ALTRQ_PURGE:
> + if (!ALTQ_IS_ENABLED(cif->cif_ifq))
> + break;
> +
> + if (qempty(cif->cl_q))
> + break;
> +
> + while ((m = _getq(cif->cl_q)) != NULL) {
> + PKTCNTR_ADD(&cif->cl_stats.cl_dropcnt,
> m_pktlen(m));
> + m_freem(m);
> + IFQ_DEC_LEN(cif->cif_ifq);
> + }
> + cif->cif_ifq->ifq_len = 0;
> + break;
> + }
> +
> + return (0);
> +}
> +
> +static int
> +codel_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr
> *pktattr)
> +{
> +
> + struct codel_if *cif = (struct codel_if *) ifq->altq_disc;
> +
> + IFQ_LOCK_ASSERT(ifq);
> +
> + /* grab class set by classifier */
> + if ((m->m_flags & M_PKTHDR) == 0) {
> + /* should not happen */
> + printf("altq: packet for %s does not have pkthdr\n",
> + ifq->altq_ifp->if_xname);
> + m_freem(m);
> + PKTCNTR_ADD(&cif->cl_stats.cl_dropcnt, m_pktlen(m));
> + return (ENOBUFS);
> + }
> +
> + if (codel_addq(&cif->codel, cif->cl_q, m)) {
> + PKTCNTR_ADD(&cif->cl_stats.cl_dropcnt, m_pktlen(m));
> + return (ENOBUFS);
> + }
> + IFQ_INC_LEN(ifq);
> +
> + return (0);
> +}
> +
> +static struct mbuf *
> +codel_dequeue(struct ifaltq *ifq, int op)
> +{
> + struct codel_if *cif = (struct codel_if *)ifq->altq_disc;
> + struct mbuf *m;
> +
> + IFQ_LOCK_ASSERT(ifq);
> +
> + if (IFQ_IS_EMPTY(ifq))
> + return (NULL);
> +
> + if (op == ALTDQ_POLL)
> + return (qhead(cif->cl_q));
> +
> +
> + m = codel_getq(&cif->codel, cif->cl_q);
> + if (m != NULL) {
> + IFQ_DEC_LEN(ifq);
> + PKTCNTR_ADD(&cif->cl_stats.cl_xmitcnt, m_pktlen(m));
> + return (m);
> + }
> +
> + return (NULL);
> +}
> +
> +struct codel *
> +codel_alloc(int target, int interval, int ecn)
> +{
> + struct codel *c;
> +
> + c = malloc(sizeof(*c), M_DEVBUF, M_NOWAIT | M_ZERO);
> + if (c != NULL) {
> + c->params.target = machclk_freq * target / 1000;
> + c->params.interval = machclk_freq * interval / 1000;
> + c->params.ecn = ecn;
> + c->stats.maxpacket = 256;
> + }
> +
> + return (c);
> +}
> +
> +void
> +codel_destroy(struct codel *c)
> +{
> +
> + free(c, M_DEVBUF);
> +}
> +
> +#define MTAG_CODEL 1438031249
> +int
> +codel_addq(struct codel *c, class_queue_t *q, struct mbuf *m)
> +{
> + struct m_tag *mtag;
> + uint64_t *enqueue_time;
> +
> + if (qlen(q) < qlimit(q)) {
> + mtag = m_tag_locate(m, MTAG_CODEL, 0, NULL);
> + if (mtag == NULL)
> + mtag = m_tag_alloc(MTAG_CODEL, 0, sizeof(uint64_t),
> + M_NOWAIT);
> + if (mtag == NULL) {
> + m_freem(m);
> + return (-1);
> + }
> + enqueue_time = (uint64_t *)(mtag + 1);
> + *enqueue_time = read_machclk();
> + m_tag_prepend(m, mtag);
> + _addq(q, m);
> + return (0);
> + }
> + c->drop_overlimit++;
> + m_freem(m);
> +
> + return (-1);
> +}
> +
> +static int
> +codel_should_drop(struct codel *c, class_queue_t *q, struct mbuf *m,
> + u_int64_t now)
> +{
> + struct m_tag *mtag;
> + uint64_t *enqueue_time;
> +
> + if (m == NULL) {
> + c->vars.first_above_time = 0;
> + return (0);
> + }
> +
> + mtag = m_tag_locate(m, MTAG_CODEL, 0, NULL);
> + if (mtag == NULL) {
> + /* Only one warning per second. */
> + if (ppsratecheck(&c->last_log, &c->last_pps, 1))
> + printf("%s: could not found the packet mtag!\n",
> + __func__);
> + c->vars.first_above_time = 0;
> + return (0);
> + }
> + enqueue_time = (uint64_t *)(mtag + 1);
> + c->vars.ldelay = now - *enqueue_time;
> + c->stats.maxpacket = MAX(c->stats.maxpacket, m_pktlen(m));
> +
> + if (codel_time_before(c->vars.ldelay, c->params.target) ||
> + qsize(q) <= c->stats.maxpacket) {
> + /* went below - stay below for at least interval */
> + c->vars.first_above_time = 0;
> + return (0);
> + }
> + if (c->vars.first_above_time == 0) {
> + /* just went above from below. If we stay above
> + * for at least interval we'll say it's ok to drop
> + */
> + c->vars.first_above_time = now + c->params.interval;
> + return (0);
> + }
> + if (codel_time_after(now, c->vars.first_above_time))
> + return (1);
> +
> + return (0);
> +}
> +
> +/*
> + * Run a Newton method step:
> + * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
> + *
> + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka
> Q0.32
> + */
> +static void
> +codel_Newton_step(struct codel_vars *vars)
> +{
> + uint32_t invsqrt, invsqrt2;
> + uint64_t val;
> +
> +/* sizeof_in_bits(rec_inv_sqrt) */
> +#define REC_INV_SQRT_BITS (8 * sizeof(u_int16_t))
> +/* needed shift to get a Q0.32 number from rec_inv_sqrt */
> +#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
> +
> + invsqrt = ((u_int32_t)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
> + invsqrt2 = ((u_int64_t)invsqrt * invsqrt) >> 32;
> + val = (3LL << 32) - ((u_int64_t)vars->count * invsqrt2);
> + val >>= 2; /* avoid overflow in following multiply */
> + val = (val * invsqrt) >> (32 - 2 + 1);
> +
> + vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
> +}
> +
> +static u_int64_t
> +codel_control_law(u_int64_t t, u_int64_t interval, u_int32_t rec_inv_sqrt)
> +{
> +
> + return (t + (u_int32_t)(((u_int64_t)interval *
> + (rec_inv_sqrt << REC_INV_SQRT_SHIFT)) >> 32));
> +}
> +
> +struct mbuf *
> +codel_getq(struct codel *c, class_queue_t *q)
> +{
> + struct mbuf *m;
> + u_int64_t now;
> + int drop;
> +
> + if ((m = _getq(q)) == NULL) {
> + c->vars.dropping = 0;
> + return (m);
> + }
> +
> + now = read_machclk();
> + drop = codel_should_drop(c, q, m, now);
> + if (c->vars.dropping) {
> + if (!drop) {
> + /* sojourn time below target - leave dropping
> state */
> + c->vars.dropping = 0;
> + } else if (codel_time_after_eq(now, c->vars.drop_next)) {
> + /* It's time for the next drop. Drop the current
> + * packet and dequeue the next. The dequeue might
> + * take us out of dropping state.
> + * If not, schedule the next drop.
> + * A large backlog might result in drop rates so
> high
> + * that the next drop should happen now,
> + * hence the while loop.
> + */
> + while (c->vars.dropping &&
> + codel_time_after_eq(now, c->vars.drop_next)) {
> + c->vars.count++; /* don't care of possible
> wrap
> + * since there is no more
> + * divide */
> + codel_Newton_step(&c->vars);
> + /* TODO ECN */
> + PKTCNTR_ADD(&c->stats.drop_cnt,
> m_pktlen(m));
> + m_freem(m);
> + m = _getq(q);
> + if (!codel_should_drop(c, q, m, now))
>
> *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
>
>
--
Ermal
More information about the svn-src-all
mailing list