From 46ca89e5c173c31ddc40b82a5a3e1764209c3259 Mon Sep 17 00:00:00 2001 From: loos Date: Sat, 16 Apr 2016 22:02:32 +0000 Subject: [PATCH] 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) git-svn-id: svn://svn.freebsd.org/base/stable/10@298133 ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f --- sbin/pfctl/parse.y | 76 ++++- sbin/pfctl/pfctl_altq.c | 43 +++ sbin/pfctl/pfctl_parser.h | 1 + sbin/pfctl/pfctl_qstats.c | 38 ++- share/man/man4/altq.4 | 7 +- sys/conf/NOTES | 1 + sys/conf/files | 1 + sys/conf/options | 1 + sys/contrib/altq/altq/altq.h | 3 +- sys/contrib/altq/altq/altq_cbq.c | 4 + sys/contrib/altq/altq/altq_cbq.h | 5 +- sys/contrib/altq/altq/altq_classq.h | 6 + sys/contrib/altq/altq/altq_codel.c | 477 +++++++++++++++++++++++++++ sys/contrib/altq/altq/altq_codel.h | 129 ++++++++ sys/contrib/altq/altq/altq_fairq.c | 35 ++ sys/contrib/altq/altq/altq_fairq.h | 12 +- sys/contrib/altq/altq/altq_hfsc.c | 36 ++ sys/contrib/altq/altq/altq_hfsc.h | 12 +- sys/contrib/altq/altq/altq_priq.c | 41 ++- sys/contrib/altq/altq/altq_priq.h | 12 +- sys/contrib/altq/altq/altq_rmclass.c | 31 +- sys/contrib/altq/altq/altq_rmclass.h | 8 +- sys/contrib/altq/altq/altq_subr.c | 20 ++ sys/contrib/altq/altq/altq_var.h | 5 + sys/netpfil/pf/pf_altq.h | 7 + 25 files changed, 990 insertions(+), 21 deletions(-) create mode 100644 sys/contrib/altq/altq/altq_codel.c create mode 100644 sys/contrib/altq/altq/altq_codel.h diff --git a/sbin/pfctl/parse.y b/sbin/pfctl/parse.y index a8275d095..056274639 100644 --- a/sbin/pfctl/parse.y +++ b/sbin/pfctl/parse.y @@ -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, 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 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 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 26936fb4b..a1abfdbea 100644 --- a/sbin/pfctl/pfctl_altq.c +++ b/sbin/pfctl/pfctl_altq.c @@ -40,6 +40,7 @@ __FBSDID("$FreeBSD$"); #include #include +#include #include #include #include @@ -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) @@ -1031,6 +1045,28 @@ print_hfsc_opts(const struct pf_altq *a, const struct node_queue_opt *qopts) return (0); } +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) { @@ -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 8a4e84e4f..2b7fea7bf 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 4087d7188..8ffd87de9 100644 --- a/sbin/pfctl/pfctl_qstats.c +++ b/sbin/pfctl/pfctl_qstats.c @@ -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_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; } } @@ -347,6 +353,28 @@ print_cbqstats(struct queue_stats cur) rate2str((8 * cur.avg_bytes) / STAT_INTERVAL)); } +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) { @@ -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; diff --git a/share/man/man4/altq.4 b/share/man/man4/altq.4 index 5191f6d53..771dc53d5 100644 --- a/share/man/man4/altq.4 +++ b/share/man/man4/altq.4 @@ -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" diff --git a/sys/conf/NOTES b/sys/conf/NOTES index 78fb6eed7..7b5c72567 100644 --- a/sys/conf/NOTES +++ b/sys/conf/NOTES @@ -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 diff --git a/sys/conf/files b/sys/conf/files index b73e5ad1f..8dd4b0968 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -252,6 +252,7 @@ compat/freebsd32/freebsd32_syscalls.c optional compat_freebsd32 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 diff --git a/sys/conf/options b/sys/conf/options index b80292641..4f1ab3a6e 100644 --- a/sys/conf/options +++ b/sys/conf/options @@ -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 diff --git a/sys/contrib/altq/altq/altq.h b/sys/contrib/altq/altq/altq.h index 1600ba87b..4ef6cd233 100644 --- a/sys/contrib/altq/altq/altq.h +++ b/sys/contrib/altq/altq/altq.h @@ -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 { diff --git a/sys/contrib/altq/altq/altq_cbq.c b/sys/contrib/altq/altq/altq_cbq.c index 3991d1d92..13f9721a3 100644 --- a/sys/contrib/altq/altq/altq_cbq.c +++ b/sys/contrib/altq/altq/altq_cbq.c @@ -241,6 +241,10 @@ get_class_stats(class_stats_t *statsp, struct rm_class *cl) 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 diff --git a/sys/contrib/altq/altq/altq_cbq.h b/sys/contrib/altq/altq/altq_cbq.h index 30a15c730..2ceaaac31 100644 --- a/sys/contrib/altq/altq/altq_cbq.h +++ b/sys/contrib/altq/altq/altq_cbq.h @@ -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 diff --git a/sys/contrib/altq/altq/altq_classq.h b/sys/contrib/altq/altq/altq_classq.h index dc5c646f5..daec9944a 100644 --- a/sys/contrib/altq/altq/altq_classq.h +++ b/sys/contrib/altq/altq/altq_classq.h @@ -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_t; #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); } diff --git a/sys/contrib/altq/altq/altq_codel.c b/sys/contrib/altq/altq/altq_codel.c new file mode 100644 index 000000000..45c5ca6ec --- /dev/null +++ b/sys/contrib/altq/altq/altq_codel.c @@ -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 && + 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)) + /* leave dropping state */ + c->vars.dropping = 0; + else + /* and schedule the next drop */ + c->vars.drop_next = + codel_control_law(c->vars.drop_next, + c->params.interval, + c->vars.rec_inv_sqrt); + } + } + } else if (drop) { + /* TODO ECN */ + PKTCNTR_ADD(&c->stats.drop_cnt, m_pktlen(m)); + m_freem(m); + + m = _getq(q); + drop = codel_should_drop(c, q, m, now); + + c->vars.dropping = 1; + /* if min went above target close to when we last went below it + * assume that the drop rate that controlled the queue on the + * last cycle is a good starting point to control it now. + */ + if (codel_time_before(now - c->vars.drop_next, + 16 * c->params.interval)) { + c->vars.count = (c->vars.count - c->vars.lastcount) | 1; + /* we dont care if rec_inv_sqrt approximation + * is not very precise : + * Next Newton steps will correct it quadratically. + */ + codel_Newton_step(&c->vars); + } else { + c->vars.count = 1; + c->vars.rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT; + } + c->vars.lastcount = c->vars.count; + c->vars.drop_next = codel_control_law(now, c->params.interval, + c->vars.rec_inv_sqrt); + } + + return (m); +} + +void +codel_getstats(struct codel *c, struct codel_stats *s) +{ + *s = c->stats; +} + +#endif /* ALTQ_CODEL */ diff --git a/sys/contrib/altq/altq/altq_codel.h b/sys/contrib/altq/altq/altq_codel.h new file mode 100644 index 000000000..991af424a --- /dev/null +++ b/sys/contrib/altq/altq/altq_codel.h @@ -0,0 +1,129 @@ +/* + * 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$ + */ + +#ifndef _ALTQ_ALTQ_CODEL_H_ +#define _ALTQ_ALTQ_CODEL_H_ + +struct codel_stats { + u_int32_t maxpacket; + struct pktcntr drop_cnt; + u_int marked_packets; +}; + +struct codel_ifstats { + u_int qlength; + u_int qlimit; + struct codel_stats stats; + struct pktcntr cl_xmitcnt; /* transmitted packet counter */ + struct pktcntr cl_dropcnt; /* dropped packet counter */ +}; + +#ifdef _KERNEL +#include + +/** + * struct codel_params - contains codel parameters + * target: target queue size (in time units) + * interval: width of moving time window + * ecn: is Explicit Congestion Notification enabled + */ +struct codel_params { + u_int64_t target; + u_int64_t interval; + int ecn; +}; + +/** + * struct codel_vars - contains codel variables + * count: how many drops we've done since the last time we + * entered dropping state + * lastcount: count at entry to dropping state + * dropping: set to true if in dropping state + * rec_inv_sqrt: reciprocal value of sqrt(count) >> 1 + * first_above_time: when we went (or will go) continuously above + * target for interval + * drop_next: time to drop next packet, or when we dropped last + * ldelay: sojourn time of last dequeued packet + */ +struct codel_vars { + u_int32_t count; + u_int32_t lastcount; + int dropping; + u_int16_t rec_inv_sqrt; + u_int64_t first_above_time; + u_int64_t drop_next; + u_int64_t ldelay; +}; + +struct codel { + int last_pps; + struct codel_params params; + struct codel_vars vars; + struct codel_stats stats; + struct timeval last_log; + u_int32_t drop_overlimit; +}; + +/* + * codel interface state + */ +struct codel_if { + struct codel_if *cif_next; /* interface state list */ + struct ifaltq *cif_ifq; /* backpointer to ifaltq */ + u_int cif_bandwidth; /* link bandwidth in bps */ + + class_queue_t *cl_q; /* class queue structure */ + struct codel codel; + + /* statistics */ + struct codel_ifstats cl_stats; +}; + +struct codel *codel_alloc(int, int, int); +void codel_destroy(struct codel *); +int codel_addq(struct codel *, class_queue_t *, struct mbuf *); +struct mbuf *codel_getq(struct codel *, class_queue_t *); +void codel_getstats(struct codel *, struct codel_stats *); + +#endif /* _KERNEL */ + +#endif /* _ALTQ_ALTQ_CODEL_H_ */ diff --git a/sys/contrib/altq/altq/altq_fairq.c b/sys/contrib/altq/altq/altq_fairq.c index 575b8cbb1..2189996a8 100644 --- a/sys/contrib/altq/altq/altq_fairq.c +++ b/sys/contrib/altq/altq/altq_fairq.c @@ -318,6 +318,14 @@ fairq_class_create(struct fairq_if *pif, int pri, int qlimit, #endif return (NULL); } +#endif +#ifndef ALTQ_CODEL + if (flags & FARF_CODEL) { +#ifdef ALTQ_DEBUG + printf("fairq_class_create: CODEL not configured for FAIRQ!\n"); +#endif + return (NULL); + } #endif if (nbuckets == 0) nbuckets = 256; @@ -340,6 +348,10 @@ fairq_class_create(struct fairq_if *pif, int pri, int qlimit, #ifdef ALTQ_RED if (cl->cl_qtype == Q_RED) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (cl->cl_qtype == Q_CODEL) + codel_destroy(cl->cl_codel); #endif } else { cl = malloc(sizeof(struct fairq_class), @@ -407,6 +419,13 @@ fairq_class_create(struct fairq_if *pif, int pri, int qlimit, } } #endif /* ALTQ_RED */ +#ifdef ALTQ_CODEL + if (flags & FARF_CODEL) { + cl->cl_codel = codel_alloc(5, 100, 0); + if (cl->cl_codel != NULL) + cl->cl_qtype = Q_CODEL; + } +#endif return (cl); } @@ -445,6 +464,10 @@ fairq_class_destroy(struct fairq_class *cl) #ifdef ALTQ_RED if (cl->cl_qtype == Q_RED) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (cl->cl_qtype == Q_CODEL) + codel_destroy(cl->cl_codel); #endif } free(cl->cl_buckets, M_DEVBUF); @@ -639,6 +662,10 @@ fairq_addq(struct fairq_class *cl, struct mbuf *m, u_int32_t bucketid) #ifdef ALTQ_RED if (cl->cl_qtype == Q_RED) return red_addq(cl->cl_red, &b->queue, m, cl->cl_pktattr); +#endif +#ifdef ALTQ_CODEL + if (cl->cl_qtype == Q_CODEL) + return codel_addq(cl->cl_codel, &b->queue, m); #endif if (qlen(&b->queue) >= qlimit(&b->queue)) { m_freem(m); @@ -669,6 +696,10 @@ fairq_getq(struct fairq_class *cl, uint64_t cur_time) #ifdef ALTQ_RED else if (cl->cl_qtype == Q_RED) m = red_getq(cl->cl_red, &b->queue); +#endif +#ifdef ALTQ_CODEL + else if (cl->cl_qtype == Q_CODEL) + m = codel_getq(cl->cl_codel, &b->queue); #endif else m = _getq(&b->queue); @@ -851,6 +882,10 @@ get_class_stats(struct fairq_classstats *sp, struct fairq_class *cl) if (cl->cl_qtype == Q_RIO) rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); #endif +#ifdef ALTQ_CODEL + if (cl->cl_qtype == Q_CODEL) + codel_getstats(cl->cl_codel, &sp->codel); +#endif } /* convert a class handle to the corresponding class pointer */ diff --git a/sys/contrib/altq/altq/altq_fairq.h b/sys/contrib/altq/altq/altq_fairq.h index 7ff6913cb..8fede5b23 100644 --- a/sys/contrib/altq/altq/altq_fairq.h +++ b/sys/contrib/altq/altq/altq_fairq.h @@ -40,6 +40,7 @@ #include #include +#include #include #include #include @@ -53,6 +54,7 @@ #define FARF_RED 0x0001 /* use RED */ #define FARF_ECN 0x0002 /* use RED/ECN */ #define FARF_RIO 0x0004 /* use RIO */ +#define FARF_CODEL 0x0008 /* use CoDel */ #define FARF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ #define FARF_DEFAULTCLASS 0x1000 /* default class */ @@ -74,9 +76,10 @@ struct fairq_classstats { struct pktcntr xmit_cnt; /* transmitted packet counter */ struct pktcntr drop_cnt; /* dropped packet counter */ - /* red and rio related info */ + /* codel, red and rio related info */ int qtype; struct redstats red[3]; /* rio has 3 red stats */ + struct codel_stats codel; }; #ifdef _KERNEL @@ -98,7 +101,12 @@ struct fairq_class { fairq_bucket_t *cl_buckets; fairq_bucket_t *cl_head; /* head of circular bucket list */ fairq_bucket_t *cl_polled; - struct red *cl_red; /* RED state */ + union { + struct red *cl_red; /* RED state */ + struct codel *cl_codel; /* CoDel state */ + } cl_aqm; +#define cl_red cl_aqm.cl_red +#define cl_codel cl_aqm.cl_codel u_int cl_hogs_m1; u_int cl_lssc_m1; u_int cl_bandwidth; diff --git a/sys/contrib/altq/altq/altq_hfsc.c b/sys/contrib/altq/altq/altq_hfsc.c index 03630167f..d4f7ab900 100644 --- a/sys/contrib/altq/altq/altq_hfsc.c +++ b/sys/contrib/altq/altq/altq_hfsc.c @@ -391,6 +391,14 @@ hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, return (NULL); } #endif +#ifndef ALTQ_CODEL + if (flags & HFCF_CODEL) { +#ifdef ALTQ_DEBUG + printf("hfsc_class_create: CODEL not configured for HFSC!\n"); +#endif + return (NULL); + } +#endif cl = malloc(sizeof(struct hfsc_class), M_DEVBUF, M_NOWAIT | M_ZERO); if (cl == NULL) @@ -407,6 +415,7 @@ hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, qlimit(cl->cl_q) = qlimit; qtype(cl->cl_q) = Q_DROPTAIL; qlen(cl->cl_q) = 0; + qsize(cl->cl_q) = 0; cl->cl_flags = flags; #ifdef ALTQ_RED if (flags & (HFCF_RED|HFCF_RIO)) { @@ -451,6 +460,13 @@ hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, #endif } #endif /* ALTQ_RED */ +#ifdef ALTQ_CODEL + if (flags & HFCF_CODEL) { + cl->cl_codel = codel_alloc(5, 100, 0); + if (cl->cl_codel != NULL) + qtype(cl->cl_q) = Q_CODEL; + } +#endif if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0)) { cl->cl_rsc = malloc(sizeof(struct internal_sc), @@ -542,6 +558,10 @@ hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_destroy(cl->cl_codel); #endif } if (cl->cl_fsc != NULL) @@ -616,6 +636,10 @@ hfsc_class_destroy(struct hfsc_class *cl) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_destroy(cl->cl_codel); #endif } @@ -843,6 +867,10 @@ hfsc_addq(struct hfsc_class *cl, struct mbuf *m) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + return codel_addq(cl->cl_codel, cl->cl_q, m); #endif if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { m_freem(m); @@ -867,6 +895,10 @@ hfsc_getq(struct hfsc_class *cl) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) return red_getq(cl->cl_red, cl->cl_q); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + return codel_getq(cl->cl_codel, cl->cl_q); #endif return _getq(cl->cl_q); } @@ -1652,6 +1684,10 @@ get_class_stats(struct hfsc_classstats *sp, struct hfsc_class *cl) if (q_is_rio(cl->cl_q)) rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); #endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_getstats(cl->cl_codel, &sp->codel); +#endif } /* convert a class handle to the corresponding class pointer */ diff --git a/sys/contrib/altq/altq/altq_hfsc.h b/sys/contrib/altq/altq/altq_hfsc.h index d04b37810..75ccb4dc7 100644 --- a/sys/contrib/altq/altq/altq_hfsc.h +++ b/sys/contrib/altq/altq/altq_hfsc.h @@ -34,6 +34,7 @@ #include #include +#include #include #include @@ -55,6 +56,7 @@ struct service_curve { #define HFCF_RED 0x0001 /* use RED */ #define HFCF_ECN 0x0002 /* use RED/ECN */ #define HFCF_RIO 0x0004 /* use RIO */ +#define HFCF_CODEL 0x0008 /* use CoDel */ #define HFCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ #define HFCF_DEFAULTCLASS 0x1000 /* default class */ @@ -101,9 +103,10 @@ struct hfsc_classstats { u_int parentperiod; /* parent's vt period seqno */ int nactive; /* number of active children */ - /* red and rio related info */ + /* codel, red and rio related info */ int qtype; struct redstats red[3]; + struct codel_stats codel; }; #ifdef ALTQ3_COMPAT @@ -229,7 +232,12 @@ struct hfsc_class { struct hfsc_class *cl_children; /* child classes */ class_queue_t *cl_q; /* class queue structure */ - struct red *cl_red; /* RED state */ + union { + struct red *cl_red; /* RED state */ + struct codel *cl_codel; /* CoDel state */ + } cl_aqm; +#define cl_red cl_aqm.cl_red +#define cl_codel cl_aqm.cl_codel struct altq_pktattr *cl_pktattr; /* saved header used by ECN */ u_int64_t cl_total; /* total work in bytes */ diff --git a/sys/contrib/altq/altq/altq_priq.c b/sys/contrib/altq/altq/altq_priq.c index 3ce65dc15..c77ba4092 100644 --- a/sys/contrib/altq/altq/altq_priq.c +++ b/sys/contrib/altq/altq/altq_priq.c @@ -297,6 +297,14 @@ priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) return (NULL); } #endif +#ifndef ALTQ_CODEL + if (flags & PRCF_CODEL) { +#ifdef ALTQ_DEBUG + printf("priq_class_create: CODEL not configured for PRIQ!\n"); +#endif + return (NULL); + } +#endif if ((cl = pif->pif_classes[pri]) != NULL) { /* modify the class instead of creating a new one */ @@ -317,6 +325,10 @@ priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_destroy(cl->cl_codel); #endif } else { cl = malloc(sizeof(struct priq_class), M_DEVBUF, @@ -338,6 +350,7 @@ priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) qlimit(cl->cl_q) = qlimit; qtype(cl->cl_q) = Q_DROPTAIL; qlen(cl->cl_q) = 0; + qsize(cl->cl_q) = 0; cl->cl_flags = flags; cl->cl_pri = pri; if (pri > pif->pif_maxpri) @@ -381,6 +394,13 @@ priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) } } #endif /* ALTQ_RED */ +#ifdef ALTQ_CODEL + if (flags & PRCF_CODEL) { + cl->cl_codel = codel_alloc(5, 100, 0); + if (cl->cl_codel != NULL) + qtype(cl->cl_q) = Q_CODEL; + } +#endif return (cl); @@ -393,6 +413,10 @@ priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_destroy(cl->cl_codel); #endif } if (cl->cl_q != NULL) @@ -444,6 +468,10 @@ priq_class_destroy(struct priq_class *cl) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) red_destroy(cl->cl_red); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_destroy(cl->cl_codel); #endif } free(cl->cl_q, M_DEVBUF); @@ -559,6 +587,10 @@ priq_addq(struct priq_class *cl, struct mbuf *m) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + return codel_addq(cl->cl_codel, cl->cl_q, m); #endif if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { m_freem(m); @@ -583,6 +615,10 @@ priq_getq(struct priq_class *cl) #ifdef ALTQ_RED if (q_is_red(cl->cl_q)) return red_getq(cl->cl_red, cl->cl_q); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + return codel_getq(cl->cl_codel, cl->cl_q); #endif return _getq(cl->cl_q); } @@ -628,7 +664,10 @@ get_class_stats(struct priq_classstats *sp, struct priq_class *cl) if (q_is_rio(cl->cl_q)) rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); #endif - +#ifdef ALTQ_CODEL + if (q_is_codel(cl->cl_q)) + codel_getstats(cl->cl_codel, &sp->codel); +#endif } /* convert a class handle to the corresponding class pointer */ diff --git a/sys/contrib/altq/altq/altq_priq.h b/sys/contrib/altq/altq/altq_priq.h index 481d31b8a..110847dcc 100644 --- a/sys/contrib/altq/altq/altq_priq.h +++ b/sys/contrib/altq/altq/altq_priq.h @@ -30,6 +30,7 @@ #include #include +#include #include #include @@ -59,6 +60,7 @@ struct priq_add_class { #define PRCF_RED 0x0001 /* use RED */ #define PRCF_ECN 0x0002 /* use RED/ECN */ #define PRCF_RIO 0x0004 /* use RIO */ +#define PRCF_CODEL 0x0008 /* use CoDel */ #define PRCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ #define PRCF_DEFAULTCLASS 0x1000 /* default class */ @@ -102,9 +104,10 @@ struct priq_classstats { struct pktcntr xmitcnt; /* transmitted packet counter */ struct pktcntr dropcnt; /* dropped packet counter */ - /* red and rio related info */ + /* codel, red and rio related info */ int qtype; struct redstats red[3]; /* rio has 3 red stats */ + struct codel_stats codel; }; #ifdef ALTQ3_COMPAT @@ -134,7 +137,12 @@ struct priq_class_stats { struct priq_class { u_int32_t cl_handle; /* class handle */ class_queue_t *cl_q; /* class queue structure */ - struct red *cl_red; /* RED state */ + union { + struct red *cl_red; /* RED state */ + struct codel *cl_codel; /* CoDel state */ + } cl_aqm; +#define cl_red cl_aqm.cl_red +#define cl_codel cl_aqm.cl_codel int cl_pri; /* priority */ int cl_flags; /* class flags */ struct priq_if *cl_pif; /* back pointer to pif */ diff --git a/sys/contrib/altq/altq/altq_rmclass.c b/sys/contrib/altq/altq/altq_rmclass.c index c433024e7..656d0ee9f 100644 --- a/sys/contrib/altq/altq/altq_rmclass.c +++ b/sys/contrib/altq/altq/altq_rmclass.c @@ -68,6 +68,7 @@ #include #include +#include #include #include #include @@ -218,6 +219,14 @@ rmc_newclass(int pri, struct rm_ifdat *ifd, u_int nsecPerByte, return (NULL); } #endif +#ifndef ALTQ_CODEL + if (flags & RMCF_CODEL) { +#ifdef ALTQ_DEBUG + printf("rmc_newclass: CODEL not configured for CBQ!\n"); +#endif + return (NULL); + } +#endif cl = malloc(sizeof(struct rm_class), M_DEVBUF, M_NOWAIT | M_ZERO); if (cl == NULL) @@ -302,6 +311,13 @@ rmc_newclass(int pri, struct rm_ifdat *ifd, u_int nsecPerByte, #endif } #endif /* ALTQ_RED */ +#ifdef ALTQ_CODEL + if (flags & RMCF_CODEL) { + cl->codel_ = codel_alloc(5, 100, 0); + if (cl->codel_ != NULL) + qtype(cl->q_) = Q_CODEL; + } +#endif /* * put the class into the class tree @@ -651,6 +667,10 @@ rmc_delete_class(struct rm_ifdat *ifd, struct rm_class *cl) #ifdef ALTQ_RED if (q_is_red(cl->q_)) red_destroy(cl->red_); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->q_)) + codel_destroy(cl->codel_); #endif } free(cl->q_, M_DEVBUF); @@ -1618,6 +1638,10 @@ _rmc_addq(rm_class_t *cl, mbuf_t *m) if (q_is_red(cl->q_)) return red_addq(cl->red_, cl->q_, m, cl->pktattr_); #endif /* ALTQ_RED */ +#ifdef ALTQ_CODEL + if (q_is_codel(cl->q_)) + return codel_addq(cl->codel_, cl->q_, m); +#endif if (cl->flags_ & RMCF_CLEARDSCP) write_dsfield(m, cl->pktattr_, 0); @@ -1646,6 +1670,10 @@ _rmc_getq(rm_class_t *cl) #ifdef ALTQ_RED if (q_is_red(cl->q_)) return red_getq(cl->red_, cl->q_); +#endif +#ifdef ALTQ_CODEL + if (q_is_codel(cl->q_)) + return codel_getq(cl->codel_, cl->q_); #endif return _getq(cl->q_); } @@ -1717,7 +1745,8 @@ void cbqtrace_dump(int counter) #endif /* CBQ_TRACE */ #endif /* ALTQ_CBQ */ -#if defined(ALTQ_CBQ) || defined(ALTQ_RED) || defined(ALTQ_RIO) || defined(ALTQ_HFSC) || defined(ALTQ_PRIQ) +#if defined(ALTQ_CBQ) || defined(ALTQ_RED) || defined(ALTQ_RIO) || \ + defined(ALTQ_HFSC) || defined(ALTQ_PRIQ) || defined(ALTQ_CODEL) #if !defined(__GNUC__) || defined(ALTQ_DEBUG) void diff --git a/sys/contrib/altq/altq/altq_rmclass.h b/sys/contrib/altq/altq/altq_rmclass.h index cf0ddf48e..782bc1354 100644 --- a/sys/contrib/altq/altq/altq_rmclass.h +++ b/sys/contrib/altq/altq/altq_rmclass.h @@ -164,7 +164,12 @@ struct rm_class { void (*overlimit)(struct rm_class *, struct rm_class *); void (*drop)(struct rm_class *); /* Class drop action. */ - struct red *red_; /* RED state pointer */ + union { + struct red *red_; /* RED state pointer */ + struct codel *codel_; /* codel state pointer */ + } cl_aqm_; +#define red_ cl_aqm_.red_ +#define codel_ cl_aqm_.codel_ struct altq_pktattr *pktattr_; /* saved hdr used by RED/ECN */ int flags_; @@ -233,6 +238,7 @@ struct rm_ifdat { #define RMCF_RIO 0x0004 #define RMCF_FLOWVALVE 0x0008 /* use flowvalve (aka penalty-box) */ #define RMCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ +#define RMCF_CODEL 0x0020 /* flags for rmc_init */ #define RMCF_WRR 0x0100 diff --git a/sys/contrib/altq/altq/altq_subr.c b/sys/contrib/altq/altq/altq_subr.c index d59751a35..bddf73ff9 100644 --- a/sys/contrib/altq/altq/altq_subr.c +++ b/sys/contrib/altq/altq/altq_subr.c @@ -541,6 +541,11 @@ altq_pfattach(struct pf_altq *a) case ALTQT_FAIRQ: error = fairq_pfattach(a); break; +#endif +#ifdef ALTQ_CODEL + case ALTQT_CODEL: + error = codel_pfattach(a); + break; #endif default: error = ENXIO; @@ -621,6 +626,11 @@ altq_add(struct pf_altq *a) case ALTQT_FAIRQ: error = fairq_add_altq(a); break; +#endif +#ifdef ALTQ_CODEL + case ALTQT_CODEL: + error = codel_add_altq(a); + break; #endif default: error = ENXIO; @@ -662,6 +672,11 @@ altq_remove(struct pf_altq *a) case ALTQT_FAIRQ: error = fairq_remove_altq(a); break; +#endif +#ifdef ALTQ_CODEL + case ALTQT_CODEL: + error = codel_remove_altq(a); + break; #endif default: error = ENXIO; @@ -776,6 +791,11 @@ altq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes) case ALTQT_FAIRQ: error = fairq_getqstats(a, ubuf, nbytes); break; +#endif +#ifdef ALTQ_CODEL + case ALTQT_CODEL: + error = codel_getqstats(a, ubuf, nbytes); + break; #endif default: error = ENXIO; diff --git a/sys/contrib/altq/altq/altq_var.h b/sys/contrib/altq/altq/altq_var.h index eb603ea94..355c94c17 100644 --- a/sys/contrib/altq/altq/altq_var.h +++ b/sys/contrib/altq/altq/altq_var.h @@ -243,6 +243,11 @@ int cbq_add_queue(struct pf_altq *); int cbq_remove_queue(struct pf_altq *); int cbq_getqstats(struct pf_altq *, void *, int *); +int codel_pfattach(struct pf_altq *); +int codel_add_altq(struct pf_altq *); +int codel_remove_altq(struct pf_altq *); +int codel_getqstats(struct pf_altq *, void *, int *); + int priq_pfattach(struct pf_altq *); int priq_add_altq(struct pf_altq *); int priq_remove_altq(struct pf_altq *); diff --git a/sys/netpfil/pf/pf_altq.h b/sys/netpfil/pf/pf_altq.h index db681fbb5..3efd4ff79 100644 --- a/sys/netpfil/pf/pf_altq.h +++ b/sys/netpfil/pf/pf_altq.h @@ -45,6 +45,12 @@ struct cbq_opts { int flags; }; +struct codel_opts { + u_int target; + u_int interval; + int ecn; +}; + struct priq_opts { int flags; }; @@ -103,6 +109,7 @@ struct pf_altq { uint16_t flags; /* misc flags */ union { struct cbq_opts cbq_opts; + struct codel_opts codel_opts; struct priq_opts priq_opts; struct hfsc_opts hfsc_opts; struct fairq_opts fairq_opts; -- 2.45.0