altq_fairq.c revision 298133
1251877Speter/* 2251877Speter * Copyright (c) 2008 The DragonFly Project. All rights reserved. 3251877Speter * 4251877Speter * This code is derived from software contributed to The DragonFly Project 5251877Speter * by Matthew Dillon <dillon@backplane.com> 6251877Speter * 7251877Speter * Redistribution and use in source and binary forms, with or without 8251877Speter * modification, are permitted provided that the following conditions 9251877Speter * are met: 10251877Speter * 11251877Speter * 1. Redistributions of source code must retain the above copyright 12251877Speter * notice, this list of conditions and the following disclaimer. 13251877Speter * 2. Redistributions in binary form must reproduce the above copyright 14251877Speter * notice, this list of conditions and the following disclaimer in 15251877Speter * the documentation and/or other materials provided with the 16251877Speter * distribution. 17251877Speter * 3. Neither the name of The DragonFly Project nor the names of its 18251877Speter * contributors may be used to endorse or promote products derived 19251877Speter * from this software without specific, prior written permission. 20251877Speter * 21251877Speter * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22251877Speter * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23251877Speter * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24251877Speter * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25251877Speter * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26251877Speter * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27251877Speter * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28251877Speter * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29251877Speter * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30251877Speter * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31251877Speter * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32251877Speter * SUCH DAMAGE. 33251877Speter * 34251877Speter * $DragonFly: src/sys/net/altq/altq_fairq.c,v 1.1 2008/04/06 18:58:15 dillon Exp $ 35251877Speter * $FreeBSD: stable/10/sys/contrib/altq/altq/altq_fairq.c 298133 2016-04-16 22:02:32Z loos $ 36251877Speter */ 37251877Speter/* 38251877Speter * Matt: I gutted altq_priq.c and used it as a skeleton on which to build 39251877Speter * fairq. The fairq algorithm is completely different then priq, of course, 40251877Speter * but because I used priq's skeleton I believe I should include priq's 41251877Speter * copyright. 42251877Speter * 43251877Speter * Copyright (C) 2000-2003 44251877Speter * Sony Computer Science Laboratories Inc. All rights reserved. 45251877Speter * 46251877Speter * Redistribution and use in source and binary forms, with or without 47251877Speter * modification, are permitted provided that the following conditions 48251877Speter * are met: 49251877Speter * 1. Redistributions of source code must retain the above copyright 50251877Speter * notice, this list of conditions and the following disclaimer. 51251877Speter * 2. Redistributions in binary form must reproduce the above copyright 52251877Speter * notice, this list of conditions and the following disclaimer in the 53251877Speter * documentation and/or other materials provided with the distribution. 54251877Speter * 55251877Speter * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 56251877Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 57251877Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 58251877Speter * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 59251877Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 60251877Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 61251877Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 62253895Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 63251877Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 64251877Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 65251877Speter * SUCH DAMAGE. 66251877Speter */ 67251877Speter 68253895Speter/* 69251877Speter * FAIRQ - take traffic classified by keep state (hashed into 70251877Speter * mbuf->m_pkthdr.altq_state_hash) and bucketize it. Fairly extract 71251877Speter * the first packet from each bucket in a round-robin fashion. 72253895Speter * 73251877Speter * TODO - better overall qlimit support (right now it is per-bucket). 74251877Speter * - NOTE: red etc is per bucket, not overall. 75251877Speter * - better service curve support. 76251877Speter * 77253895Speter * EXAMPLE: 78251877Speter * 79251877Speter * altq on em0 fairq bandwidth 650Kb queue { std, bulk } 80253895Speter * queue std priority 3 bandwidth 400Kb \ 81251877Speter * fairq (buckets 64, default, hogs 1Kb) qlimit 50 82251877Speter * queue bulk priority 2 bandwidth 100Kb \ 83253895Speter * fairq (buckets 64, hogs 1Kb) qlimit 50 84251877Speter * 85253895Speter * pass out on em0 from any to any keep state queue std 86251877Speter * pass out on em0 inet proto tcp ..... port ... keep state queue bulk 87253895Speter */ 88251877Speter#include "opt_altq.h" 89253895Speter#include "opt_inet.h" 90251877Speter#include "opt_inet6.h" 91251877Speter 92253895Speter#ifdef ALTQ_FAIRQ /* fairq is enabled in the kernel conf */ 93251877Speter 94251877Speter#include <sys/param.h> 95253895Speter#include <sys/malloc.h> 96251877Speter#include <sys/mbuf.h> 97251877Speter#include <sys/socket.h> 98253895Speter#include <sys/sockio.h> 99251877Speter#include <sys/systm.h> 100251877Speter#include <sys/proc.h> 101253895Speter#include <sys/errno.h> 102251877Speter#include <sys/kernel.h> 103251877Speter#include <sys/queue.h> 104253895Speter 105251877Speter#include <net/if.h> 106251877Speter#include <net/if_var.h> 107253895Speter#include <netinet/in.h> 108251877Speter 109253895Speter#include <netpfil/pf/pf.h> 110253895Speter#include <netpfil/pf/pf_altq.h> 111253895Speter#include <netpfil/pf/pf_mtag.h> 112251877Speter#include <altq/altq.h> 113251877Speter#include <altq/altq_fairq.h> 114251877Speter 115251877Speter/* 116251877Speter * function prototypes 117251877Speter */ 118251877Speterstatic int fairq_clear_interface(struct fairq_if *); 119251877Speterstatic int fairq_request(struct ifaltq *, int, void *); 120251877Speterstatic void fairq_purge(struct fairq_if *); 121251877Speterstatic struct fairq_class *fairq_class_create(struct fairq_if *, int, int, u_int, struct fairq_opts *, int); 122251877Speterstatic int fairq_class_destroy(struct fairq_class *); 123251877Speterstatic int fairq_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *); 124251877Speterstatic struct mbuf *fairq_dequeue(struct ifaltq *, int); 125251877Speter 126251877Speterstatic int fairq_addq(struct fairq_class *, struct mbuf *, u_int32_t); 127251877Speterstatic struct mbuf *fairq_getq(struct fairq_class *, uint64_t); 128251877Speterstatic struct mbuf *fairq_pollq(struct fairq_class *, uint64_t, int *); 129251877Speterstatic fairq_bucket_t *fairq_selectq(struct fairq_class *, int); 130251877Speterstatic void fairq_purgeq(struct fairq_class *); 131251877Speter 132251877Speterstatic void get_class_stats(struct fairq_classstats *, struct fairq_class *); 133251877Speterstatic struct fairq_class *clh_to_clp(struct fairq_if *, uint32_t); 134251877Speter 135251877Speterint 136251877Speterfairq_pfattach(struct pf_altq *a) 137251877Speter{ 138251877Speter struct ifnet *ifp; 139251877Speter int error; 140251877Speter 141251877Speter if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL) 142251877Speter return (EINVAL); 143251877Speter 144251877Speter error = altq_attach(&ifp->if_snd, ALTQT_FAIRQ, a->altq_disc, 145251877Speter fairq_enqueue, fairq_dequeue, fairq_request, NULL, NULL); 146251877Speter 147251877Speter return (error); 148251877Speter} 149251877Speter 150251877Speterint 151251877Speterfairq_add_altq(struct pf_altq *a) 152251877Speter{ 153251877Speter struct fairq_if *pif; 154251877Speter struct ifnet *ifp; 155251877Speter 156251877Speter if ((ifp = ifunit(a->ifname)) == NULL) 157251877Speter return (EINVAL); 158251877Speter if (!ALTQ_IS_READY(&ifp->if_snd)) 159251877Speter return (ENODEV); 160251877Speter 161251877Speter 162251877Speter pif = malloc(sizeof(struct fairq_if), 163251877Speter M_DEVBUF, M_WAITOK | M_ZERO); 164251877Speter pif->pif_bandwidth = a->ifbandwidth; 165251877Speter pif->pif_maxpri = -1; 166251877Speter pif->pif_ifq = &ifp->if_snd; 167251877Speter 168251877Speter /* keep the state in pf_altq */ 169251877Speter a->altq_disc = pif; 170251877Speter 171251877Speter return (0); 172251877Speter} 173251877Speter 174251877Speterint 175251877Speterfairq_remove_altq(struct pf_altq *a) 176251877Speter{ 177251877Speter struct fairq_if *pif; 178251877Speter 179251877Speter if ((pif = a->altq_disc) == NULL) 180251877Speter return (EINVAL); 181251877Speter a->altq_disc = NULL; 182251877Speter 183251877Speter fairq_clear_interface(pif); 184251877Speter 185251877Speter free(pif, M_DEVBUF); 186251877Speter return (0); 187251877Speter} 188251877Speter 189251877Speterint 190251877Speterfairq_add_queue(struct pf_altq *a) 191251877Speter{ 192251877Speter struct fairq_if *pif; 193251877Speter struct fairq_class *cl; 194251877Speter 195251877Speter if ((pif = a->altq_disc) == NULL) 196251877Speter return (EINVAL); 197251877Speter 198251877Speter /* check parameters */ 199251877Speter if (a->priority >= FAIRQ_MAXPRI) 200251877Speter return (EINVAL); 201251877Speter if (a->qid == 0) 202251877Speter return (EINVAL); 203251877Speter if (pif->pif_classes[a->priority] != NULL) 204251877Speter return (EBUSY); 205251877Speter if (clh_to_clp(pif, a->qid) != NULL) 206251877Speter return (EBUSY); 207251877Speter 208251877Speter cl = fairq_class_create(pif, a->priority, a->qlimit, a->bandwidth, 209251877Speter &a->pq_u.fairq_opts, a->qid); 210251877Speter if (cl == NULL) 211251877Speter return (ENOMEM); 212251877Speter 213251877Speter return (0); 214251877Speter} 215251877Speter 216251877Speterint 217251877Speterfairq_remove_queue(struct pf_altq *a) 218251877Speter{ 219251877Speter struct fairq_if *pif; 220251877Speter struct fairq_class *cl; 221251877Speter 222251877Speter if ((pif = a->altq_disc) == NULL) 223251877Speter return (EINVAL); 224251877Speter 225251877Speter if ((cl = clh_to_clp(pif, a->qid)) == NULL) 226251877Speter return (EINVAL); 227251877Speter 228251877Speter return (fairq_class_destroy(cl)); 229251877Speter} 230251877Speter 231251877Speterint 232251877Speterfairq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes) 233251877Speter{ 234251877Speter struct fairq_if *pif; 235251877Speter struct fairq_class *cl; 236251877Speter struct fairq_classstats stats; 237251877Speter int error = 0; 238251877Speter 239251877Speter if ((pif = altq_lookup(a->ifname, ALTQT_FAIRQ)) == NULL) 240251877Speter return (EBADF); 241251877Speter 242251877Speter if ((cl = clh_to_clp(pif, a->qid)) == NULL) 243251877Speter return (EINVAL); 244251877Speter 245251877Speter if (*nbytes < sizeof(stats)) 246251877Speter return (EINVAL); 247251877Speter 248251877Speter get_class_stats(&stats, cl); 249251877Speter 250251877Speter if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0) 251251877Speter return (error); 252251877Speter *nbytes = sizeof(stats); 253251877Speter return (0); 254251877Speter} 255251877Speter 256251877Speter/* 257251877Speter * bring the interface back to the initial state by discarding 258251877Speter * all the filters and classes. 259251877Speter */ 260251877Speterstatic int 261251877Speterfairq_clear_interface(struct fairq_if *pif) 262251877Speter{ 263251877Speter struct fairq_class *cl; 264251877Speter int pri; 265251877Speter 266251877Speter /* clear out the classes */ 267251877Speter for (pri = 0; pri <= pif->pif_maxpri; pri++) { 268251877Speter if ((cl = pif->pif_classes[pri]) != NULL) 269251877Speter fairq_class_destroy(cl); 270251877Speter } 271251877Speter 272251877Speter return (0); 273251877Speter} 274251877Speter 275251877Speterstatic int 276251877Speterfairq_request(struct ifaltq *ifq, int req, void *arg) 277251877Speter{ 278251877Speter struct fairq_if *pif = (struct fairq_if *)ifq->altq_disc; 279251877Speter 280251877Speter IFQ_LOCK_ASSERT(ifq); 281251877Speter 282251877Speter switch (req) { 283251877Speter case ALTRQ_PURGE: 284251877Speter fairq_purge(pif); 285251877Speter break; 286251877Speter } 287251877Speter return (0); 288251877Speter} 289251877Speter 290251877Speter/* discard all the queued packets on the interface */ 291251877Speterstatic void 292251877Speterfairq_purge(struct fairq_if *pif) 293251877Speter{ 294251877Speter struct fairq_class *cl; 295251877Speter int pri; 296251877Speter 297251877Speter for (pri = 0; pri <= pif->pif_maxpri; pri++) { 298251877Speter if ((cl = pif->pif_classes[pri]) != NULL && cl->cl_head) 299251877Speter fairq_purgeq(cl); 300251877Speter } 301251877Speter if (ALTQ_IS_ENABLED(pif->pif_ifq)) 302251877Speter pif->pif_ifq->ifq_len = 0; 303251877Speter} 304251877Speter 305251877Speterstatic struct fairq_class * 306251877Speterfairq_class_create(struct fairq_if *pif, int pri, int qlimit, 307251877Speter u_int bandwidth, struct fairq_opts *opts, int qid) 308251877Speter{ 309251877Speter struct fairq_class *cl; 310251877Speter int flags = opts->flags; 311251877Speter u_int nbuckets = opts->nbuckets; 312251877Speter int i; 313251877Speter 314251877Speter#ifndef ALTQ_RED 315251877Speter if (flags & FARF_RED) { 316251877Speter#ifdef ALTQ_DEBUG 317251877Speter printf("fairq_class_create: RED not configured for FAIRQ!\n"); 318251877Speter#endif 319251877Speter return (NULL); 320251877Speter } 321251877Speter#endif 322251877Speter#ifndef ALTQ_CODEL 323251877Speter if (flags & FARF_CODEL) { 324251877Speter#ifdef ALTQ_DEBUG 325251877Speter printf("fairq_class_create: CODEL not configured for FAIRQ!\n"); 326251877Speter#endif 327251877Speter return (NULL); 328251877Speter } 329251877Speter#endif 330251877Speter if (nbuckets == 0) 331251877Speter nbuckets = 256; 332251877Speter if (nbuckets > FAIRQ_MAX_BUCKETS) 333251877Speter nbuckets = FAIRQ_MAX_BUCKETS; 334251877Speter /* enforce power-of-2 size */ 335251877Speter while ((nbuckets ^ (nbuckets - 1)) != ((nbuckets << 1) - 1)) 336251877Speter ++nbuckets; 337251877Speter 338251877Speter if ((cl = pif->pif_classes[pri]) != NULL) { 339251877Speter /* modify the class instead of creating a new one */ 340251877Speter IFQ_LOCK(cl->cl_pif->pif_ifq); 341251877Speter if (cl->cl_head) 342251877Speter fairq_purgeq(cl); 343251877Speter IFQ_UNLOCK(cl->cl_pif->pif_ifq); 344251877Speter#ifdef ALTQ_RIO 345251877Speter if (cl->cl_qtype == Q_RIO) 346251877Speter rio_destroy((rio_t *)cl->cl_red); 347251877Speter#endif 348251877Speter#ifdef ALTQ_RED 349251877Speter if (cl->cl_qtype == Q_RED) 350251877Speter red_destroy(cl->cl_red); 351251877Speter#endif 352251877Speter#ifdef ALTQ_CODEL 353251877Speter if (cl->cl_qtype == Q_CODEL) 354251877Speter codel_destroy(cl->cl_codel); 355251877Speter#endif 356251877Speter } else { 357251877Speter cl = malloc(sizeof(struct fairq_class), 358251877Speter M_DEVBUF, M_WAITOK | M_ZERO); 359251877Speter cl->cl_nbuckets = nbuckets; 360251877Speter cl->cl_nbucket_mask = nbuckets - 1; 361251877Speter 362251877Speter cl->cl_buckets = malloc( 363251877Speter sizeof(struct fairq_bucket) * cl->cl_nbuckets, 364251877Speter M_DEVBUF, M_WAITOK | M_ZERO); 365251877Speter cl->cl_head = NULL; 366251877Speter } 367251877Speter 368251877Speter pif->pif_classes[pri] = cl; 369251877Speter if (flags & FARF_DEFAULTCLASS) 370251877Speter pif->pif_default = cl; 371251877Speter if (qlimit == 0) 372251877Speter qlimit = 50; /* use default */ 373251877Speter cl->cl_qlimit = qlimit; 374251877Speter for (i = 0; i < cl->cl_nbuckets; ++i) { 375251877Speter qlimit(&cl->cl_buckets[i].queue) = qlimit; 376251877Speter } 377251877Speter cl->cl_bandwidth = bandwidth / 8; 378251877Speter cl->cl_qtype = Q_DROPTAIL; 379251877Speter cl->cl_flags = flags & FARF_USERFLAGS; 380251877Speter cl->cl_pri = pri; 381251877Speter if (pri > pif->pif_maxpri) 382251877Speter pif->pif_maxpri = pri; 383251877Speter cl->cl_pif = pif; 384251877Speter cl->cl_handle = qid; 385251877Speter cl->cl_hogs_m1 = opts->hogs_m1 / 8; 386251877Speter cl->cl_lssc_m1 = opts->lssc_m1 / 8; /* NOT YET USED */ 387251877Speter 388251877Speter#ifdef ALTQ_RED 389251877Speter if (flags & (FARF_RED|FARF_RIO)) { 390251877Speter int red_flags, red_pkttime; 391251877Speter 392251877Speter red_flags = 0; 393251877Speter if (flags & FARF_ECN) 394251877Speter red_flags |= REDF_ECN; 395251877Speter#ifdef ALTQ_RIO 396251877Speter if (flags & FARF_CLEARDSCP) 397251877Speter red_flags |= RIOF_CLEARDSCP; 398251877Speter#endif 399251877Speter if (pif->pif_bandwidth < 8) 400251877Speter red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 401251877Speter else 402251877Speter red_pkttime = (int64_t)pif->pif_ifq->altq_ifp->if_mtu 403251877Speter * 1000 * 1000 * 1000 / (pif->pif_bandwidth / 8); 404251877Speter#ifdef ALTQ_RIO 405251877Speter if (flags & FARF_RIO) { 406251877Speter cl->cl_red = (red_t *)rio_alloc(0, NULL, 407251877Speter red_flags, red_pkttime); 408251877Speter if (cl->cl_red != NULL) 409251877Speter cl->cl_qtype = Q_RIO; 410251877Speter } else 411251877Speter#endif 412251877Speter if (flags & FARF_RED) { 413251877Speter cl->cl_red = red_alloc(0, 0, 414251877Speter cl->cl_qlimit * 10/100, 415251877Speter cl->cl_qlimit * 30/100, 416251877Speter red_flags, red_pkttime); 417251877Speter if (cl->cl_red != NULL) 418251877Speter cl->cl_qtype = Q_RED; 419251877Speter } 420251877Speter } 421251877Speter#endif /* ALTQ_RED */ 422251877Speter#ifdef ALTQ_CODEL 423251877Speter if (flags & FARF_CODEL) { 424251877Speter cl->cl_codel = codel_alloc(5, 100, 0); 425251877Speter if (cl->cl_codel != NULL) 426251877Speter cl->cl_qtype = Q_CODEL; 427251877Speter } 428251877Speter#endif 429251877Speter 430251877Speter return (cl); 431251877Speter} 432251877Speter 433251877Speterstatic int 434251877Speterfairq_class_destroy(struct fairq_class *cl) 435251877Speter{ 436251877Speter struct fairq_if *pif; 437251877Speter int pri; 438251877Speter 439251877Speter IFQ_LOCK(cl->cl_pif->pif_ifq); 440251877Speter 441251877Speter if (cl->cl_head) 442251877Speter fairq_purgeq(cl); 443251877Speter 444251877Speter pif = cl->cl_pif; 445251877Speter pif->pif_classes[cl->cl_pri] = NULL; 446251877Speter if (pif->pif_poll_cache == cl) 447251877Speter pif->pif_poll_cache = NULL; 448251877Speter if (pif->pif_maxpri == cl->cl_pri) { 449251877Speter for (pri = cl->cl_pri; pri >= 0; pri--) 450251877Speter if (pif->pif_classes[pri] != NULL) { 451251877Speter pif->pif_maxpri = pri; 452251877Speter break; 453251877Speter } 454251877Speter if (pri < 0) 455251877Speter pif->pif_maxpri = -1; 456251877Speter } 457251877Speter IFQ_UNLOCK(cl->cl_pif->pif_ifq); 458251877Speter 459251877Speter if (cl->cl_red != NULL) { 460251877Speter#ifdef ALTQ_RIO 461251877Speter if (cl->cl_qtype == Q_RIO) 462251877Speter rio_destroy((rio_t *)cl->cl_red); 463251877Speter#endif 464251877Speter#ifdef ALTQ_RED 465251877Speter if (cl->cl_qtype == Q_RED) 466251877Speter red_destroy(cl->cl_red); 467251877Speter#endif 468251877Speter#ifdef ALTQ_CODEL 469251877Speter if (cl->cl_qtype == Q_CODEL) 470251877Speter codel_destroy(cl->cl_codel); 471251877Speter#endif 472251877Speter } 473251877Speter free(cl->cl_buckets, M_DEVBUF); 474251877Speter free(cl, M_DEVBUF); 475251877Speter 476251877Speter return (0); 477251877Speter} 478251877Speter 479251877Speter/* 480251877Speter * fairq_enqueue is an enqueue function to be registered to 481251877Speter * (*altq_enqueue) in struct ifaltq. 482251877Speter */ 483251877Speterstatic int 484251877Speterfairq_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr) 485251877Speter{ 486251877Speter struct fairq_if *pif = (struct fairq_if *)ifq->altq_disc; 487251877Speter struct fairq_class *cl = NULL; /* Make compiler happy */ 488251877Speter struct pf_mtag *t; 489251877Speter u_int32_t qid_hash = 0; 490251877Speter int len; 491251877Speter 492251877Speter IFQ_LOCK_ASSERT(ifq); 493251877Speter 494251877Speter /* grab class set by classifier */ 495251877Speter if ((m->m_flags & M_PKTHDR) == 0) { 496251877Speter /* should not happen */ 497251877Speter printf("altq: packet for %s does not have pkthdr\n", 498253895Speter ifq->altq_ifp->if_xname); 499253895Speter m_freem(m); 500251877Speter return (ENOBUFS); 501251877Speter } 502251877Speter 503251877Speter if ((t = pf_find_mtag(m)) != NULL) { 504251877Speter cl = clh_to_clp(pif, t->qid); 505251877Speter qid_hash = t->qid_hash; 506251877Speter } 507251877Speter if (cl == NULL) { 508251877Speter cl = pif->pif_default; 509251877Speter if (cl == NULL) { 510251877Speter m_freem(m); 511251877Speter return (ENOBUFS); 512251877Speter } 513251877Speter } 514251877Speter cl->cl_flags |= FARF_HAS_PACKETS; 515251877Speter cl->cl_pktattr = NULL; 516251877Speter len = m_pktlen(m); 517251877Speter if (fairq_addq(cl, m, qid_hash) != 0) { 518251877Speter /* drop occurred. mbuf was freed in fairq_addq. */ 519251877Speter PKTCNTR_ADD(&cl->cl_dropcnt, len); 520251877Speter return (ENOBUFS); 521251877Speter } 522251877Speter IFQ_INC_LEN(ifq); 523251877Speter 524251877Speter return (0); 525251877Speter} 526251877Speter 527251877Speter/* 528251877Speter * fairq_dequeue is a dequeue function to be registered to 529251877Speter * (*altq_dequeue) in struct ifaltq. 530251877Speter * 531251877Speter * note: ALTDQ_POLL returns the next packet without removing the packet 532251877Speter * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 533251877Speter * ALTDQ_REMOVE must return the same packet if called immediately 534251877Speter * after ALTDQ_POLL. 535251877Speter */ 536251877Speterstatic struct mbuf * 537251877Speterfairq_dequeue(struct ifaltq *ifq, int op) 538251877Speter{ 539251877Speter struct fairq_if *pif = (struct fairq_if *)ifq->altq_disc; 540251877Speter struct fairq_class *cl; 541251877Speter struct fairq_class *best_cl; 542251877Speter struct mbuf *best_m; 543251877Speter struct mbuf *m = NULL; 544251877Speter uint64_t cur_time = read_machclk(); 545251877Speter int pri; 546251877Speter int hit_limit; 547251877Speter 548251877Speter IFQ_LOCK_ASSERT(ifq); 549251877Speter 550251877Speter if (IFQ_IS_EMPTY(ifq)) { 551251877Speter return (NULL); 552251877Speter } 553251877Speter 554251877Speter if (pif->pif_poll_cache && op == ALTDQ_REMOVE) { 555251877Speter best_cl = pif->pif_poll_cache; 556251877Speter m = fairq_getq(best_cl, cur_time); 557251877Speter pif->pif_poll_cache = NULL; 558251877Speter if (m) { 559251877Speter IFQ_DEC_LEN(ifq); 560251877Speter PKTCNTR_ADD(&best_cl->cl_xmitcnt, m_pktlen(m)); 561251877Speter return (m); 562251877Speter } 563251877Speter } else { 564251877Speter best_cl = NULL; 565251877Speter best_m = NULL; 566251877Speter 567251877Speter for (pri = pif->pif_maxpri; pri >= 0; pri--) { 568251877Speter if ((cl = pif->pif_classes[pri]) == NULL) 569251877Speter continue; 570251877Speter if ((cl->cl_flags & FARF_HAS_PACKETS) == 0) 571251877Speter continue; 572251877Speter m = fairq_pollq(cl, cur_time, &hit_limit); 573251877Speter if (m == NULL) { 574251877Speter cl->cl_flags &= ~FARF_HAS_PACKETS; 575251877Speter continue; 576251877Speter } 577251877Speter 578251877Speter /* 579251877Speter * Only override the best choice if we are under 580251877Speter * the BW limit. 581251877Speter */ 582251877Speter if (hit_limit == 0 || best_cl == NULL) { 583251877Speter best_cl = cl; 584251877Speter best_m = m; 585251877Speter } 586251877Speter 587251877Speter /* 588251877Speter * Remember the highest priority mbuf in case we 589251877Speter * do not find any lower priority mbufs. 590251877Speter */ 591251877Speter if (hit_limit) 592251877Speter continue; 593251877Speter break; 594251877Speter } 595251877Speter if (op == ALTDQ_POLL) { 596251877Speter pif->pif_poll_cache = best_cl; 597251877Speter m = best_m; 598251877Speter } else if (best_cl) { 599251877Speter m = fairq_getq(best_cl, cur_time); 600251877Speter if (m != NULL) { 601251877Speter IFQ_DEC_LEN(ifq); 602251877Speter PKTCNTR_ADD(&best_cl->cl_xmitcnt, m_pktlen(m)); 603251877Speter } 604251877Speter } 605251877Speter return (m); 606251877Speter } 607251877Speter return (NULL); 608251877Speter} 609251877Speter 610251877Speterstatic int 611251877Speterfairq_addq(struct fairq_class *cl, struct mbuf *m, u_int32_t bucketid) 612251877Speter{ 613251877Speter fairq_bucket_t *b; 614251877Speter u_int hindex; 615251877Speter uint64_t bw; 616251877Speter 617251877Speter /* 618251877Speter * If the packet doesn't have any keep state put it on the end of 619251877Speter * our queue. XXX this can result in out of order delivery. 620251877Speter */ 621251877Speter if (bucketid == 0) { 622251877Speter if (cl->cl_head) 623251877Speter b = cl->cl_head->prev; 624251877Speter else 625251877Speter b = &cl->cl_buckets[0]; 626251877Speter } else { 627251877Speter hindex = bucketid & cl->cl_nbucket_mask; 628251877Speter b = &cl->cl_buckets[hindex]; 629251877Speter } 630251877Speter 631251877Speter /* 632251877Speter * Add the bucket to the end of the circular list of active buckets. 633251877Speter * 634251877Speter * As a special case we add the bucket to the beginning of the list 635251877Speter * instead of the end if it was not previously on the list and if 636251877Speter * its traffic is less then the hog level. 637251877Speter */ 638251877Speter if (b->in_use == 0) { 639251877Speter b->in_use = 1; 640251877Speter if (cl->cl_head == NULL) { 641251877Speter cl->cl_head = b; 642251877Speter b->next = b; 643251877Speter b->prev = b; 644251877Speter } else { 645251877Speter b->next = cl->cl_head; 646251877Speter b->prev = cl->cl_head->prev; 647251877Speter b->prev->next = b; 648251877Speter b->next->prev = b; 649251877Speter 650251877Speter if (b->bw_delta && cl->cl_hogs_m1) { 651251877Speter bw = b->bw_bytes * machclk_freq / b->bw_delta; 652251877Speter if (bw < cl->cl_hogs_m1) 653251877Speter cl->cl_head = b; 654251877Speter } 655251877Speter } 656251877Speter } 657251877Speter 658251877Speter#ifdef ALTQ_RIO 659251877Speter if (cl->cl_qtype == Q_RIO) 660251877Speter return rio_addq((rio_t *)cl->cl_red, &b->queue, m, cl->cl_pktattr); 661251877Speter#endif 662251877Speter#ifdef ALTQ_RED 663251877Speter if (cl->cl_qtype == Q_RED) 664251877Speter return red_addq(cl->cl_red, &b->queue, m, cl->cl_pktattr); 665251877Speter#endif 666251877Speter#ifdef ALTQ_CODEL 667251877Speter if (cl->cl_qtype == Q_CODEL) 668251877Speter return codel_addq(cl->cl_codel, &b->queue, m); 669251877Speter#endif 670251877Speter if (qlen(&b->queue) >= qlimit(&b->queue)) { 671251877Speter m_freem(m); 672251877Speter return (-1); 673251877Speter } 674251877Speter 675251877Speter if (cl->cl_flags & FARF_CLEARDSCP) 676251877Speter write_dsfield(m, cl->cl_pktattr, 0); 677251877Speter 678251877Speter _addq(&b->queue, m); 679251877Speter 680251877Speter return (0); 681251877Speter} 682251877Speter 683251877Speterstatic struct mbuf * 684251877Speterfairq_getq(struct fairq_class *cl, uint64_t cur_time) 685251877Speter{ 686251877Speter fairq_bucket_t *b; 687251877Speter struct mbuf *m; 688251877Speter 689251877Speter b = fairq_selectq(cl, 0); 690251877Speter if (b == NULL) 691251877Speter m = NULL; 692251877Speter#ifdef ALTQ_RIO 693251877Speter else if (cl->cl_qtype == Q_RIO) 694251877Speter m = rio_getq((rio_t *)cl->cl_red, &b->queue); 695251877Speter#endif 696251877Speter#ifdef ALTQ_RED 697251877Speter else if (cl->cl_qtype == Q_RED) 698251877Speter m = red_getq(cl->cl_red, &b->queue); 699251877Speter#endif 700251877Speter#ifdef ALTQ_CODEL 701251877Speter else if (cl->cl_qtype == Q_CODEL) 702251877Speter m = codel_getq(cl->cl_codel, &b->queue); 703251877Speter#endif 704251877Speter else 705251877Speter m = _getq(&b->queue); 706251877Speter 707251877Speter /* 708251877Speter * Calculate the BW change 709251877Speter */ 710251877Speter if (m != NULL) { 711251877Speter uint64_t delta; 712251877Speter 713251877Speter /* 714251877Speter * Per-class bandwidth calculation 715251877Speter */ 716251877Speter delta = (cur_time - cl->cl_last_time); 717251877Speter if (delta > machclk_freq * 8) 718251877Speter delta = machclk_freq * 8; 719251877Speter cl->cl_bw_delta += delta; 720251877Speter cl->cl_bw_bytes += m->m_pkthdr.len; 721251877Speter cl->cl_last_time = cur_time; 722251877Speter cl->cl_bw_delta -= cl->cl_bw_delta >> 3; 723251877Speter cl->cl_bw_bytes -= cl->cl_bw_bytes >> 3; 724251877Speter 725251877Speter /* 726251877Speter * Per-bucket bandwidth calculation 727251877Speter */ 728251877Speter delta = (cur_time - b->last_time); 729251877Speter if (delta > machclk_freq * 8) 730251877Speter delta = machclk_freq * 8; 731251877Speter b->bw_delta += delta; 732251877Speter b->bw_bytes += m->m_pkthdr.len; 733251877Speter b->last_time = cur_time; 734251877Speter b->bw_delta -= b->bw_delta >> 3; 735251877Speter b->bw_bytes -= b->bw_bytes >> 3; 736251877Speter } 737251877Speter return(m); 738251877Speter} 739251877Speter 740251877Speter/* 741251877Speter * Figure out what the next packet would be if there were no limits. If 742251877Speter * this class hits its bandwidth limit *hit_limit is set to no-zero, otherwise 743251877Speter * it is set to 0. A non-NULL mbuf is returned either way. 744251877Speter */ 745251877Speterstatic struct mbuf * 746251877Speterfairq_pollq(struct fairq_class *cl, uint64_t cur_time, int *hit_limit) 747251877Speter{ 748251877Speter fairq_bucket_t *b; 749251877Speter struct mbuf *m; 750251877Speter uint64_t delta; 751251877Speter uint64_t bw; 752251877Speter 753251877Speter *hit_limit = 0; 754251877Speter b = fairq_selectq(cl, 1); 755251877Speter if (b == NULL) 756251877Speter return(NULL); 757251877Speter m = qhead(&b->queue); 758251877Speter 759251877Speter /* 760251877Speter * Did this packet exceed the class bandwidth? Calculate the 761251877Speter * bandwidth component of the packet. 762251877Speter * 763251877Speter * - Calculate bytes per second 764251877Speter */ 765251877Speter delta = cur_time - cl->cl_last_time; 766251877Speter if (delta > machclk_freq * 8) 767251877Speter delta = machclk_freq * 8; 768251877Speter cl->cl_bw_delta += delta; 769251877Speter cl->cl_last_time = cur_time; 770251877Speter if (cl->cl_bw_delta) { 771251877Speter bw = cl->cl_bw_bytes * machclk_freq / cl->cl_bw_delta; 772251877Speter 773251877Speter if (bw > cl->cl_bandwidth) 774251877Speter *hit_limit = 1; 775251877Speter#ifdef ALTQ_DEBUG 776251877Speter printf("BW %6ju relative to %6u %d queue %p\n", 777251877Speter (uintmax_t)bw, cl->cl_bandwidth, *hit_limit, b); 778251877Speter#endif 779251877Speter } 780251877Speter return(m); 781251877Speter} 782251877Speter 783251877Speter/* 784251877Speter * Locate the next queue we want to pull a packet out of. This code 785251877Speter * is also responsible for removing empty buckets from the circular list. 786251877Speter */ 787251877Speterstatic 788251877Speterfairq_bucket_t * 789251877Speterfairq_selectq(struct fairq_class *cl, int ispoll) 790251877Speter{ 791251877Speter fairq_bucket_t *b; 792251877Speter uint64_t bw; 793251877Speter 794251877Speter if (ispoll == 0 && cl->cl_polled) { 795251877Speter b = cl->cl_polled; 796251877Speter cl->cl_polled = NULL; 797251877Speter return(b); 798251877Speter } 799251877Speter 800251877Speter while ((b = cl->cl_head) != NULL) { 801251877Speter /* 802251877Speter * Remove empty queues from consideration 803251877Speter */ 804251877Speter if (qempty(&b->queue)) { 805251877Speter b->in_use = 0; 806251877Speter cl->cl_head = b->next; 807251877Speter if (cl->cl_head == b) { 808251877Speter cl->cl_head = NULL; 809251877Speter } else { 810251877Speter b->next->prev = b->prev; 811251877Speter b->prev->next = b->next; 812251877Speter } 813251877Speter continue; 814251877Speter } 815251877Speter 816251877Speter /* 817251877Speter * Advance the round robin. Queues with bandwidths less 818251877Speter * then the hog bandwidth are allowed to burst. 819251877Speter */ 820251877Speter if (cl->cl_hogs_m1 == 0) { 821251877Speter cl->cl_head = b->next; 822251877Speter } else if (b->bw_delta) { 823251877Speter bw = b->bw_bytes * machclk_freq / b->bw_delta; 824251877Speter if (bw >= cl->cl_hogs_m1) { 825251877Speter cl->cl_head = b->next; 826251877Speter } 827251877Speter /* 828251877Speter * XXX TODO - 829251877Speter */ 830251877Speter } 831251877Speter 832251877Speter /* 833251877Speter * Return bucket b. 834251877Speter */ 835251877Speter break; 836251877Speter } 837251877Speter if (ispoll) 838251877Speter cl->cl_polled = b; 839251877Speter return(b); 840251877Speter} 841251877Speter 842251877Speterstatic void 843251877Speterfairq_purgeq(struct fairq_class *cl) 844251877Speter{ 845251877Speter fairq_bucket_t *b; 846251877Speter struct mbuf *m; 847251877Speter 848251877Speter while ((b = fairq_selectq(cl, 0)) != NULL) { 849251877Speter while ((m = _getq(&b->queue)) != NULL) { 850251877Speter PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m)); 851251877Speter m_freem(m); 852251877Speter } 853251877Speter ASSERT(qlen(&b->queue) == 0); 854251877Speter } 855251877Speter} 856251877Speter 857251877Speterstatic void 858251877Speterget_class_stats(struct fairq_classstats *sp, struct fairq_class *cl) 859251877Speter{ 860251877Speter fairq_bucket_t *b; 861251877Speter 862251877Speter sp->class_handle = cl->cl_handle; 863251877Speter sp->qlimit = cl->cl_qlimit; 864251877Speter sp->xmit_cnt = cl->cl_xmitcnt; 865251877Speter sp->drop_cnt = cl->cl_dropcnt; 866251877Speter sp->qtype = cl->cl_qtype; 867251877Speter sp->qlength = 0; 868251877Speter 869251877Speter if (cl->cl_head) { 870251877Speter b = cl->cl_head; 871251877Speter do { 872251877Speter sp->qlength += qlen(&b->queue); 873251877Speter b = b->next; 874251877Speter } while (b != cl->cl_head); 875251877Speter } 876251877Speter 877251877Speter#ifdef ALTQ_RED 878251877Speter if (cl->cl_qtype == Q_RED) 879251877Speter red_getstats(cl->cl_red, &sp->red[0]); 880251877Speter#endif 881251877Speter#ifdef ALTQ_RIO 882251877Speter if (cl->cl_qtype == Q_RIO) 883251877Speter rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 884251877Speter#endif 885251877Speter#ifdef ALTQ_CODEL 886251877Speter if (cl->cl_qtype == Q_CODEL) 887251877Speter codel_getstats(cl->cl_codel, &sp->codel); 888251877Speter#endif 889251877Speter} 890251877Speter 891251877Speter/* convert a class handle to the corresponding class pointer */ 892251877Speterstatic struct fairq_class * 893251877Speterclh_to_clp(struct fairq_if *pif, uint32_t chandle) 894251877Speter{ 895251877Speter struct fairq_class *cl; 896251877Speter int idx; 897251877Speter 898251877Speter if (chandle == 0) 899251877Speter return (NULL); 900251877Speter 901251877Speter for (idx = pif->pif_maxpri; idx >= 0; idx--) 902251877Speter if ((cl = pif->pif_classes[idx]) != NULL && 903251877Speter cl->cl_handle == chandle) 904251877Speter return (cl); 905251877Speter 906251877Speter return (NULL); 907251877Speter} 908251877Speter 909251877Speter#endif /* ALTQ_FAIRQ */ 910251877Speter