From owner-svn-src-all@freebsd.org Sat Apr 16 22:02:34 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 742EFB10CE8; Sat, 16 Apr 2016 22:02:34 +0000 (UTC) (envelope-from loos@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 3CDFF1998; Sat, 16 Apr 2016 22:02:34 +0000 (UTC) (envelope-from loos@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id u3GM2XAc048699; Sat, 16 Apr 2016 22:02:33 GMT (envelope-from loos@FreeBSD.org) Received: (from loos@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id u3GM2WZE048683; Sat, 16 Apr 2016 22:02:32 GMT (envelope-from loos@FreeBSD.org) Message-Id: <201604162202.u3GM2WZE048683@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: loos set sender to loos@FreeBSD.org using -f From: Luiz Otavio O Souza Date: Sat, 16 Apr 2016 22:02:32 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r298133 - in stable/10: sbin/pfctl share/man/man4 sys/conf sys/contrib/altq/altq sys/netpfil/pf X-SVN-Group: stable-10 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 16 Apr 2016 22:02:34 -0000 Author: loos Date: Sat Apr 16 22:02:32 2016 New Revision: 298133 URL: https://svnweb.freebsd.org/changeset/base/298133 Log: MFC r287009, r287120 and r298131: 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. Obtained from: pfSense Sponsored by: Rubicon Communications (Netgate) Added: stable/10/sys/contrib/altq/altq/altq_codel.c (contents, props changed) stable/10/sys/contrib/altq/altq/altq_codel.h (contents, props changed) Modified: stable/10/sbin/pfctl/parse.y stable/10/sbin/pfctl/pfctl_altq.c stable/10/sbin/pfctl/pfctl_parser.h stable/10/sbin/pfctl/pfctl_qstats.c stable/10/share/man/man4/altq.4 stable/10/sys/conf/NOTES stable/10/sys/conf/files stable/10/sys/conf/options stable/10/sys/contrib/altq/altq/altq.h stable/10/sys/contrib/altq/altq/altq_cbq.c stable/10/sys/contrib/altq/altq/altq_cbq.h stable/10/sys/contrib/altq/altq/altq_classq.h stable/10/sys/contrib/altq/altq/altq_fairq.c stable/10/sys/contrib/altq/altq/altq_fairq.h stable/10/sys/contrib/altq/altq/altq_hfsc.c stable/10/sys/contrib/altq/altq/altq_hfsc.h stable/10/sys/contrib/altq/altq/altq_priq.c stable/10/sys/contrib/altq/altq/altq_priq.h stable/10/sys/contrib/altq/altq/altq_rmclass.c stable/10/sys/contrib/altq/altq/altq_rmclass.h stable/10/sys/contrib/altq/altq/altq_subr.c stable/10/sys/contrib/altq/altq/altq_var.h stable/10/sys/netpfil/pf/pf_altq.h Directory Properties: stable/10/ (props changed) Modified: stable/10/sbin/pfctl/parse.y ============================================================================== --- stable/10/sbin/pfctl/parse.y Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sbin/pfctl/parse.y Sat Apr 16 22:02:32 2016 (r298133) @@ -46,6 +46,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include @@ -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 priqflags_list priqflags_item %type hfscopts_list hfscopts_item hfsc_opts %type fairqopts_list fairqopts_item fairq_opts +%type codelopts_list codelopts_item codel_opts %type bandwidth %type filter_opts filter_opt filter_opts_l %type 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: stable/10/sbin/pfctl/pfctl_altq.c ============================================================================== --- stable/10/sbin/pfctl/pfctl_altq.c Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sbin/pfctl/pfctl_altq.c Sat Apr 16 22:02:32 2016 (r298133) @@ -40,6 +40,7 @@ __FBSDID("$FreeBSD$"); #include #include +#include #include #include #include @@ -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: stable/10/sbin/pfctl/pfctl_parser.h ============================================================================== --- stable/10/sbin/pfctl/pfctl_parser.h Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sbin/pfctl/pfctl_parser.h Sat Apr 16 22:02:32 2016 (r298133) @@ -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: stable/10/sbin/pfctl/pfctl_qstats.c ============================================================================== --- stable/10/sbin/pfctl/pfctl_qstats.c Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sbin/pfctl/pfctl_qstats.c Sat Apr 16 22:02:32 2016 (r298133) @@ -36,6 +36,7 @@ __FBSDID("$FreeBSD$"); #include #include +#include #include #include #include @@ -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: stable/10/share/man/man4/altq.4 ============================================================================== --- stable/10/share/man/man4/altq.4 Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/share/man/man4/altq.4 Sat Apr 16 22:02:32 2016 (r298133) @@ -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: stable/10/sys/conf/NOTES ============================================================================== --- stable/10/sys/conf/NOTES Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/conf/NOTES Sat Apr 16 22:02:32 2016 (r298133) @@ -699,6 +699,7 @@ options ALTQ options ALTQ_CBQ # Class Based Queueing options ALTQ_RED # Random Early Detection options ALTQ_RIO # RED In/Out +options ALTQ_CODEL # CoDel Active Queueing options ALTQ_HFSC # Hierarchical Packet Scheduler options ALTQ_FAIRQ # Fair Packet Scheduler options ALTQ_CDNR # Traffic conditioner Modified: stable/10/sys/conf/files ============================================================================== --- stable/10/sys/conf/files Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/conf/files Sat Apr 16 22:02:32 2016 (r298133) @@ -252,6 +252,7 @@ compat/freebsd32/freebsd32_syscalls.c op compat/freebsd32/freebsd32_sysent.c optional compat_freebsd32 contrib/altq/altq/altq_cbq.c optional altq contrib/altq/altq/altq_cdnr.c optional altq +contrib/altq/altq/altq_codel.c optional altq contrib/altq/altq/altq_fairq.c optional altq contrib/altq/altq/altq_hfsc.c optional altq contrib/altq/altq/altq_priq.c optional altq Modified: stable/10/sys/conf/options ============================================================================== --- stable/10/sys/conf/options Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/conf/options Sat Apr 16 22:02:32 2016 (r298133) @@ -384,6 +384,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_FAIRQ opt_altq.h ALTQ_HFSC opt_altq.h Modified: stable/10/sys/contrib/altq/altq/altq.h ============================================================================== --- stable/10/sys/contrib/altq/altq/altq.h Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/contrib/altq/altq/altq.h Sat Apr 16 22:02:32 2016 (r298133) @@ -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: stable/10/sys/contrib/altq/altq/altq_cbq.c ============================================================================== --- stable/10/sys/contrib/altq/altq/altq_cbq.c Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/contrib/altq/altq/altq_cbq.c Sat Apr 16 22:02:32 2016 (r298133) @@ -241,6 +241,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: stable/10/sys/contrib/altq/altq/altq_cbq.h ============================================================================== --- stable/10/sys/contrib/altq/altq/altq_cbq.h Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/contrib/altq/altq/altq_cbq.h Sat Apr 16 22:02:32 2016 (r298133) @@ -34,6 +34,7 @@ #define _ALTQ_ALTQ_CBQ_H_ #include +#include #include #include #include @@ -51,6 +52,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 */ @@ -90,9 +92,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: stable/10/sys/contrib/altq/altq/altq_classq.h ============================================================================== --- stable/10/sys/contrib/altq/altq/altq_classq.h Sat Apr 16 21:34:49 2016 (r298132) +++ stable/10/sys/contrib/altq/altq/altq_classq.h Sat Apr 16 22:02:32 2016 (r298133) @@ -49,6 +49,7 @@ extern "C" { #define Q_RED 0x01 #define Q_RIO 0x02 #define Q_DROPTAIL 0x03 +#define Q_CODEL 0x04 #ifdef _KERNEL @@ -59,6 +60,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 */ }; @@ -67,10 +69,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) @@ -100,6 +104,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 * @@ -114,6 +119,7 @@ _getq(class_queue_t *q) else qtail(q) = NULL; qlen(q)--; + qsize(q) -= m_pktlen(m0); m0->m_nextpkt = NULL; return (m0); } Added: stable/10/sys/contrib/altq/altq/altq_codel.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ stable/10/sys/contrib/altq/altq/altq_codel.c Sat Apr 16 22:02:32 2016 (r298133) @@ -0,0 +1,477 @@ +/* + * CoDel - The Controlled-Delay Active Queue Management algorithm + * + * Copyright (C) 2013 Ermal Luçi + * Copyright (C) 2011-2012 Kathleen Nichols + * Copyright (C) 2011-2012 Van Jacobson + * Copyright (C) 2012 Michael D. Taht + * Copyright (C) 2012 Eric Dumazet + * + * 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 +#include +#include +#include +#include + +#include +#include +#include + +#include +#include +#include +#include +#include + +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 && *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***