bsd/net/classq/classq_fq_codel.c

   1 /*
   2  * Copyright (c) 2016-2017 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <sys/cdefs.h>
  30 #include <sys/param.h>
  31 #include <sys/mbuf.h>
  32 #include <sys/socket.h>
  33 #include <sys/sockio.h>
  34 #include <sys/systm.h>
  35 #include <sys/sysctl.h>
  36 #include <sys/syslog.h>
  37 #include <sys/proc.h>
  38 #include <sys/errno.h>
  39 #include <sys/kernel.h>
  40 #include <sys/kauth.h>
  41 #include <kern/zalloc.h>
  42 #include <netinet/in.h>
  43
  44 #include <net/classq/classq.h>
  45 #include <net/classq/if_classq.h>
  46 #include <net/pktsched/pktsched.h>
  47 #include <net/pktsched/pktsched_fq_codel.h>
  48 #include <net/classq/classq_fq_codel.h>
  49
  50 static struct zone *flowq_zone = NULL;
  51
  52 #define FQ_ZONE_MAX     (32 * 1024)     /* across all interfaces */
  53
  54 #define DTYPE_NODROP    0       /* no drop */
  55 #define DTYPE_FORCED    1       /* a "forced" drop */
  56 #define DTYPE_EARLY     2       /* an "unforced" (early) drop */
  57
  58 void
  59 fq_codel_init(void)
  60 {
  61         if (flowq_zone != NULL)
  62                 return;
  63
  64         flowq_zone = zinit(sizeof (struct flowq),
  65             FQ_ZONE_MAX * sizeof (struct flowq), 0, "flowq_zone");
  66         if (flowq_zone == NULL) {
  67                 panic("%s: failed to allocate flowq_zone", __func__);
  68                 /* NOTREACHED */
  69         }
  70         zone_change(flowq_zone, Z_EXPAND, TRUE);
  71         zone_change(flowq_zone, Z_CALLERACCT, TRUE);
  72 }
  73
  74 fq_t *
  75 fq_alloc(classq_pkt_type_t ptype)
  76 {
  77         fq_t *fq = NULL;
  78         fq = zalloc(flowq_zone);
  79         if (fq == NULL) {
  80                 log(LOG_ERR, "%s: unable to allocate from flowq_zone\n");
  81                 return (NULL);
  82         }
  83
  84         bzero(fq, sizeof (*fq));
  85         fq->fq_ptype = ptype;
  86         if (ptype == QP_MBUF) {
  87                 MBUFQ_INIT(&fq->fq_mbufq);
  88         }
  89         return (fq);
  90 }
  91
  92 void
  93 fq_destroy(fq_t *fq)
  94 {
  95         VERIFY(fq_empty(fq));
  96         VERIFY(!(fq->fq_flags & (FQF_NEW_FLOW | FQF_OLD_FLOW)));
  97         VERIFY(fq->fq_bytes == 0);
  98         zfree(flowq_zone, fq);
  99 }
 100
 101 static void
 102 fq_detect_dequeue_stall(fq_if_t *fqs, fq_t *flowq, fq_if_classq_t *fq_cl,
 103     u_int64_t *now)
 104 {
 105         u_int64_t maxgetqtime;
 106         if (FQ_IS_DELAYHIGH(flowq) || flowq->fq_getqtime == 0 ||
 107             fq_empty(flowq) ||
 108             flowq->fq_bytes < FQ_MIN_FC_THRESHOLD_BYTES)
 109                 return;
 110         maxgetqtime = flowq->fq_getqtime + fqs->fqs_update_interval;
 111         if ((*now) > maxgetqtime) {
 112                 /*
 113                  * there was no dequeue in an update interval worth of
 114                  * time. It means that the queue is stalled.
 115                  */
 116                 FQ_SET_DELAY_HIGH(flowq);
 117                 fq_cl->fcl_stat.fcl_dequeue_stall++;
 118         }
 119 }
 120
 121 void
 122 fq_head_drop(fq_if_t *fqs, fq_t *fq)
 123 {
 124         pktsched_pkt_t pkt;
 125         uint32_t *pkt_flags;
 126         uint64_t *pkt_timestamp;
 127         struct ifclassq *ifq = fqs->fqs_ifq;
 128
 129         _PKTSCHED_PKT_INIT(&pkt);
 130         if (fq_getq_flow_internal(fqs, fq, &pkt) == NULL)
 131                 return;
 132
 133         pktsched_get_pkt_vars(&pkt, &pkt_flags, &pkt_timestamp, NULL, NULL,
 134             NULL, NULL);
 135
 136         *pkt_timestamp = 0;
 137         if (pkt.pktsched_ptype == QP_MBUF)
 138                 *pkt_flags &= ~PKTF_PRIV_GUARDED;
 139
 140         IFCQ_DROP_ADD(ifq, 1, pktsched_get_pkt_len(&pkt));
 141         IFCQ_CONVERT_LOCK(ifq);
 142         pktsched_free_pkt(&pkt);
 143 }
 144
 145 int
 146 fq_addq(fq_if_t *fqs, pktsched_pkt_t *pkt, fq_if_classq_t *fq_cl)
 147 {
 148         int droptype = DTYPE_NODROP, fc_adv = 0, ret = CLASSQEQ_SUCCESS;
 149         u_int64_t now;
 150         fq_t *fq = NULL;
 151         uint64_t *pkt_timestamp;
 152         uint32_t *pkt_flags;
 153         uint32_t pkt_flowid, pkt_tx_start_seq;
 154         uint8_t pkt_proto, pkt_flowsrc;
 155
 156         pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, &pkt_flowid,
 157             &pkt_flowsrc, &pkt_proto, &pkt_tx_start_seq);
 158
 159         if (pkt->pktsched_ptype == QP_MBUF) {
 160                 /* See comments in <rdar://problem/14040693> */
 161                 VERIFY(!(*pkt_flags & PKTF_PRIV_GUARDED));
 162                 *pkt_flags |= PKTF_PRIV_GUARDED;
 163         }
 164
 165         if (*pkt_timestamp > 0) {
 166                 now = *pkt_timestamp;
 167         } else {
 168                 struct timespec now_ts;
 169                 nanouptime(&now_ts);
 170                 now = (now_ts.tv_sec * NSEC_PER_SEC) + now_ts.tv_nsec;
 171                 *pkt_timestamp = now;
 172         }
 173
 174         /* find the flowq for this packet */
 175         fq = fq_if_hash_pkt(fqs, pkt_flowid, pktsched_get_pkt_svc(pkt),
 176             now, TRUE, pkt->pktsched_ptype);
 177         if (fq == NULL) {
 178                 /* drop the packet if we could not allocate a flow queue */
 179                 fq_cl->fcl_stat.fcl_drop_memfailure++;
 180                 IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
 181                 return (CLASSQEQ_DROP);
 182         }
 183         VERIFY(fq->fq_ptype == pkt->pktsched_ptype);
 184
 185         fq_detect_dequeue_stall(fqs, fq, fq_cl, &now);
 186
 187         if (FQ_IS_DELAYHIGH(fq)) {
 188                 if ((fq->fq_flags & FQF_FLOWCTL_CAPABLE) &&
 189                     (*pkt_flags & PKTF_FLOW_ADV)) {
 190                         fc_adv = 1;
 191                         /*
 192                          * If the flow is suspended or it is not
 193                          * TCP, drop the packet
 194                          */
 195                         if (pkt_proto != IPPROTO_TCP) {
 196                                 droptype = DTYPE_EARLY;
 197                                 fq_cl->fcl_stat.fcl_drop_early++;
 198                         }
 199                 } else {
 200                         /*
 201                          * Need to drop a packet, instead of dropping this
 202                          * one, try to drop from the head of the queue
 203                          */
 204                         if (!fq_empty(fq)) {
 205                                 fq_head_drop(fqs, fq);
 206                                 droptype = DTYPE_NODROP;
 207                         } else {
 208                                 droptype = DTYPE_EARLY;
 209                         }
 210                         fq_cl->fcl_stat.fcl_drop_early++;
 211                 }
 212
 213         }
 214
 215         /* Set the return code correctly */
 216         if (fc_adv == 1 && droptype != DTYPE_FORCED) {
 217                 if (fq_if_add_fcentry(fqs, pkt, pkt_flowid, pkt_flowsrc,
 218                     fq_cl)) {
 219                         fq->fq_flags |= FQF_FLOWCTL_ON;
 220                         /* deliver flow control advisory error */
 221                         if (droptype == DTYPE_NODROP) {
 222                                 ret = CLASSQEQ_SUCCESS_FC;
 223                         } else {
 224                                 /* dropped due to flow control */
 225                                 ret = CLASSQEQ_DROP_FC;
 226                         }
 227                 } else {
 228                         /*
 229                          * if we could not flow control the flow, it is
 230                          * better to drop
 231                          */
 232                         droptype = DTYPE_FORCED;
 233                         ret = CLASSQEQ_DROP_FC;
 234                         fq_cl->fcl_stat.fcl_flow_control_fail++;
 235                 }
 236         }
 237
 238         /*
 239          * If the queue length hits the queue limit, drop a packet from the
 240          * front of the queue for a flow with maximum number of bytes. This
 241          * will penalize heavy and unresponsive flows. It will also avoid a
 242          * tail drop.
 243          */
 244         if (droptype == DTYPE_NODROP && fq_if_at_drop_limit(fqs)) {
 245                 if (fqs->fqs_large_flow == fq) {
 246                         /*
 247                          * Drop from the head of the current fq. Since a
 248                          * new packet will be added to the tail, it is ok
 249                          * to leave fq in place.
 250                          */
 251                         fq_head_drop(fqs, fq);
 252                 } else {
 253                         if (fqs->fqs_large_flow == NULL) {
 254                                 droptype = DTYPE_FORCED;
 255                                 fq_cl->fcl_stat.fcl_drop_overflow++;
 256                                 ret = CLASSQEQ_DROP;
 257
 258                                 /*
 259                                  * if this fq was freshly created and there
 260                                  * is nothing to enqueue, free it
 261                                  */
 262                                 if (fq_empty(fq) && !(fq->fq_flags &
 263                                     (FQF_NEW_FLOW | FQF_OLD_FLOW))) {
 264                                         fq_if_destroy_flow(fqs, fq_cl, fq);
 265                                         fq = NULL;
 266                                 }
 267                         } else {
 268                                 fq_if_drop_packet(fqs);
 269                         }
 270                 }
 271         }
 272
 273         if (droptype == DTYPE_NODROP) {
 274                 uint32_t pkt_len = pktsched_get_pkt_len(pkt);
 275                 fq_enqueue(fq, pkt->pktsched_pkt);
 276                 fq->fq_bytes += pkt_len;
 277                 fq_cl->fcl_stat.fcl_byte_cnt += pkt_len;
 278                 fq_cl->fcl_stat.fcl_pkt_cnt++;
 279
 280                 /*
 281                  * check if this queue will qualify to be the next
 282                  * victim queue
 283                  */
 284                 fq_if_is_flow_heavy(fqs, fq);
 285         } else {
 286                 IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
 287                 return ((ret != CLASSQEQ_SUCCESS) ? ret : CLASSQEQ_DROP);
 288         }
 289
 290         /*
 291          * If the queue is not currently active, add it to the end of new
 292          * flows list for that service class.
 293          */
 294         if ((fq->fq_flags & (FQF_NEW_FLOW|FQF_OLD_FLOW)) == 0) {
 295                 VERIFY(STAILQ_NEXT(fq, fq_actlink) == NULL);
 296                 STAILQ_INSERT_TAIL(&fq_cl->fcl_new_flows, fq, fq_actlink);
 297                 fq->fq_flags |= FQF_NEW_FLOW;
 298
 299                 fq_cl->fcl_stat.fcl_newflows_cnt++;
 300
 301                 fq->fq_deficit = fq_cl->fcl_quantum;
 302         }
 303         return (ret);
 304 }
 305
 306 void *
 307 fq_getq_flow_internal(fq_if_t *fqs, fq_t *fq, pktsched_pkt_t *pkt)
 308 {
 309         void *p;
 310         uint32_t plen;
 311         fq_if_classq_t *fq_cl;
 312         struct ifclassq *ifq = fqs->fqs_ifq;
 313
 314         fq_dequeue(fq, p);
 315         if (p == NULL)
 316                 return (NULL);
 317
 318         pktsched_pkt_encap(pkt, fq->fq_ptype, p);
 319         plen = pktsched_get_pkt_len(pkt);
 320
 321         VERIFY(fq->fq_bytes >= plen);
 322         fq->fq_bytes -= plen;
 323
 324         fq_cl = &fqs->fqs_classq[fq->fq_sc_index];
 325         fq_cl->fcl_stat.fcl_byte_cnt -= plen;
 326         fq_cl->fcl_stat.fcl_pkt_cnt--;
 327         IFCQ_DEC_LEN(ifq);
 328         IFCQ_DEC_BYTES(ifq, plen);
 329
 330         /* Reset getqtime so that we don't count idle times */
 331         if (fq_empty(fq))
 332                 fq->fq_getqtime = 0;
 333
 334         return (p);
 335 }
 336
 337 void *
 338 fq_getq_flow(fq_if_t *fqs, fq_t *fq, pktsched_pkt_t *pkt)
 339 {
 340         void *p;
 341         fq_if_classq_t *fq_cl;
 342         u_int64_t now;
 343         int64_t qdelay = 0;
 344         struct timespec now_ts;
 345         uint32_t *pkt_flags, pkt_tx_start_seq;
 346         uint64_t *pkt_timestamp;
 347
 348         p = fq_getq_flow_internal(fqs, fq, pkt);
 349         if (p == NULL)
 350                 return (NULL);
 351
 352         pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, NULL, NULL,
 353             NULL, &pkt_tx_start_seq);
 354
 355         nanouptime(&now_ts);
 356         now = (now_ts.tv_sec * NSEC_PER_SEC) + now_ts.tv_nsec;
 357
 358         /* this will compute qdelay in nanoseconds */
 359         if (now > *pkt_timestamp)
 360                 qdelay = now - *pkt_timestamp;
 361         fq_cl = &fqs->fqs_classq[fq->fq_sc_index];
 362
 363         if (fq->fq_min_qdelay == 0 ||
 364             (qdelay > 0 && (u_int64_t)qdelay < fq->fq_min_qdelay))
 365                 fq->fq_min_qdelay = qdelay;
 366         if (now >= fq->fq_updatetime) {
 367                 if (fq->fq_min_qdelay > fqs->fqs_target_qdelay) {
 368                         if (!FQ_IS_DELAYHIGH(fq))
 369                                 FQ_SET_DELAY_HIGH(fq);
 370                 } else {
 371                         FQ_CLEAR_DELAY_HIGH(fq);
 372                 }
 373
 374
 375                 /* Reset measured queue delay and update time */
 376                 fq->fq_updatetime = now + fqs->fqs_update_interval;
 377                 fq->fq_min_qdelay = 0;
 378         }
 379         if (!FQ_IS_DELAYHIGH(fq) || fq_empty(fq)) {
 380                 FQ_CLEAR_DELAY_HIGH(fq);
 381                 if (fq->fq_flags & FQF_FLOWCTL_ON) {
 382                         fq_if_flow_feedback(fqs, fq, fq_cl);
 383                 }
 384         }
 385
 386         if (fq_empty(fq)) {
 387                 /* Reset getqtime so that we don't count idle times */
 388                 fq->fq_getqtime = 0;
 389         } else {
 390                 fq->fq_getqtime = now;
 391         }
 392         fq_if_is_flow_heavy(fqs, fq);
 393
 394         *pkt_timestamp = 0;
 395         if (pkt->pktsched_ptype == QP_MBUF)
 396                 *pkt_flags &= ~PKTF_PRIV_GUARDED;
 397
 398         return (p);
 399 }