sys/netinet/sctp_ss_functions.c

   1 /*-
   2  * Copyright (c) 2010-2012, by Michael Tuexen. All rights reserved.
   3  * Copyright (c) 2010-2012, by Randall Stewart. All rights reserved.
   4  * Copyright (c) 2010-2012, by Robin Seggelmann. All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  * a) Redistributions of source code must retain the above copyright notice,
  10  *    this list of conditions and the following disclaimer.
  11  *
  12  * b) Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in
  14  *    the documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  18  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  26  * THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include <sys/cdefs.h>
  30 __FBSDID("$FreeBSD$");
  31
  32 #include <netinet/sctp_pcb.h>
  33
  34 /*
  35  * Default simple round-robin algorithm.
  36  * Just interates the streams in the order they appear.
  37  */
  38
  39 static void
  40 sctp_ss_default_add(struct sctp_tcb *, struct sctp_association *,
  41     struct sctp_stream_out *,
  42     struct sctp_stream_queue_pending *, int);
  43
  44 static void
  45 sctp_ss_default_remove(struct sctp_tcb *, struct sctp_association *,
  46     struct sctp_stream_out *,
  47     struct sctp_stream_queue_pending *, int);
  48
  49 static void
  50 sctp_ss_default_init(struct sctp_tcb *stcb, struct sctp_association *asoc,
  51     int holds_lock)
  52 {
  53         uint16_t i;
  54
  55         TAILQ_INIT(&asoc->ss_data.out_wheel);
  56         /*
  57          * If there is data in the stream queues already, the scheduler of
  58          * an existing association has been changed. We need to add all
  59          * stream queues to the wheel.
  60          */
  61         for (i = 0; i < stcb->asoc.streamoutcnt; i++) {
  62                 stcb->asoc.ss_functions.sctp_ss_add_to_stream(stcb, &stcb->asoc,
  63                     &stcb->asoc.strmout[i],
  64                     NULL, holds_lock);
  65         }
  66         return;
  67 }
  68
  69 static void
  70 sctp_ss_default_clear(struct sctp_tcb *stcb, struct sctp_association *asoc,
  71     int clear_values SCTP_UNUSED, int holds_lock)
  72 {
  73         if (holds_lock == 0) {
  74                 SCTP_TCB_SEND_LOCK(stcb);
  75         }
  76         while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
  77                 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
  78
  79                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.rr.next_spoke);
  80                 strq->ss_params.rr.next_spoke.tqe_next = NULL;
  81                 strq->ss_params.rr.next_spoke.tqe_prev = NULL;
  82         }
  83         asoc->last_out_stream = NULL;
  84         if (holds_lock == 0) {
  85                 SCTP_TCB_SEND_UNLOCK(stcb);
  86         }
  87         return;
  88 }
  89
  90 static void
  91 sctp_ss_default_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq SCTP_UNUSED)
  92 {
  93         strq->ss_params.rr.next_spoke.tqe_next = NULL;
  94         strq->ss_params.rr.next_spoke.tqe_prev = NULL;
  95         return;
  96 }
  97
  98 static void
  99 sctp_ss_default_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 100     struct sctp_stream_out *strq,
 101     struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock)
 102 {
 103         if (holds_lock == 0) {
 104                 SCTP_TCB_SEND_LOCK(stcb);
 105         }
 106         /* Add to wheel if not already on it and stream queue not empty */
 107         if (!TAILQ_EMPTY(&strq->outqueue) &&
 108             (strq->ss_params.rr.next_spoke.tqe_next == NULL) &&
 109             (strq->ss_params.rr.next_spoke.tqe_prev == NULL)) {
 110                 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel,
 111                     strq, ss_params.rr.next_spoke);
 112         }
 113         if (holds_lock == 0) {
 114                 SCTP_TCB_SEND_UNLOCK(stcb);
 115         }
 116         return;
 117 }
 118
 119 static int
 120 sctp_ss_default_is_empty(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc)
 121 {
 122         if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
 123                 return (1);
 124         } else {
 125                 return (0);
 126         }
 127 }
 128
 129 static void
 130 sctp_ss_default_remove(struct sctp_tcb *stcb, struct sctp_association *asoc,
 131     struct sctp_stream_out *strq,
 132     struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock)
 133 {
 134         if (holds_lock == 0) {
 135                 SCTP_TCB_SEND_LOCK(stcb);
 136         }
 137         /*
 138          * Remove from wheel if stream queue is empty and actually is on the
 139          * wheel
 140          */
 141         if (TAILQ_EMPTY(&strq->outqueue) &&
 142             (strq->ss_params.rr.next_spoke.tqe_next != NULL ||
 143             strq->ss_params.rr.next_spoke.tqe_prev != NULL)) {
 144                 if (asoc->last_out_stream == strq) {
 145                         asoc->last_out_stream = TAILQ_PREV(asoc->last_out_stream,
 146                             sctpwheel_listhead,
 147                             ss_params.rr.next_spoke);
 148                         if (asoc->last_out_stream == NULL) {
 149                                 asoc->last_out_stream = TAILQ_LAST(&asoc->ss_data.out_wheel,
 150                                     sctpwheel_listhead);
 151                         }
 152                         if (asoc->last_out_stream == strq) {
 153                                 asoc->last_out_stream = NULL;
 154                         }
 155                 }
 156                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke);
 157                 strq->ss_params.rr.next_spoke.tqe_next = NULL;
 158                 strq->ss_params.rr.next_spoke.tqe_prev = NULL;
 159         }
 160         if (holds_lock == 0) {
 161                 SCTP_TCB_SEND_UNLOCK(stcb);
 162         }
 163         return;
 164 }
 165
 166
 167 static struct sctp_stream_out *
 168 sctp_ss_default_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net,
 169     struct sctp_association *asoc)
 170 {
 171         struct sctp_stream_out *strq, *strqt;
 172
 173         strqt = asoc->last_out_stream;
 174 default_again:
 175         /* Find the next stream to use */
 176         if (strqt == NULL) {
 177                 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 178         } else {
 179                 strq = TAILQ_NEXT(strqt, ss_params.rr.next_spoke);
 180                 if (strq == NULL) {
 181                         strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 182                 }
 183         }
 184
 185         /*
 186          * If CMT is off, we must validate that the stream in question has
 187          * the first item pointed towards are network destination requested
 188          * by the caller. Note that if we turn out to be locked to a stream
 189          * (assigning TSN's then we must stop, since we cannot look for
 190          * another stream with data to send to that destination). In CMT's
 191          * case, by skipping this check, we will send one data packet
 192          * towards the requested net.
 193          */
 194         if (net != NULL && strq != NULL &&
 195             SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) {
 196                 if (TAILQ_FIRST(&strq->outqueue) &&
 197                     TAILQ_FIRST(&strq->outqueue)->net != NULL &&
 198                     TAILQ_FIRST(&strq->outqueue)->net != net) {
 199                         if (strq == asoc->last_out_stream) {
 200                                 return (NULL);
 201                         } else {
 202                                 strqt = strq;
 203                                 goto default_again;
 204                         }
 205                 }
 206         }
 207         return (strq);
 208 }
 209
 210 static void
 211 sctp_ss_default_scheduled(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED,
 212     struct sctp_association *asoc SCTP_UNUSED,
 213     struct sctp_stream_out *strq, int moved_how_much SCTP_UNUSED)
 214 {
 215         asoc->last_out_stream = strq;
 216         return;
 217 }
 218
 219 static void
 220 sctp_ss_default_packet_done(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED,
 221     struct sctp_association *asoc SCTP_UNUSED)
 222 {
 223         /* Nothing to be done here */
 224         return;
 225 }
 226
 227 static int
 228 sctp_ss_default_get_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED,
 229     struct sctp_stream_out *strq SCTP_UNUSED, uint16_t * value SCTP_UNUSED)
 230 {
 231         /* Nothing to be done here */
 232         return (-1);
 233 }
 234
 235 static int
 236 sctp_ss_default_set_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED,
 237     struct sctp_stream_out *strq SCTP_UNUSED, uint16_t value SCTP_UNUSED)
 238 {
 239         /* Nothing to be done here */
 240         return (-1);
 241 }
 242
 243 /*
 244  * Real round-robin algorithm.
 245  * Always interates the streams in ascending order.
 246  */
 247 static void
 248 sctp_ss_rr_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 249     struct sctp_stream_out *strq,
 250     struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock)
 251 {
 252         struct sctp_stream_out *strqt;
 253
 254         if (holds_lock == 0) {
 255                 SCTP_TCB_SEND_LOCK(stcb);
 256         }
 257         if (!TAILQ_EMPTY(&strq->outqueue) &&
 258             (strq->ss_params.rr.next_spoke.tqe_next == NULL) &&
 259             (strq->ss_params.rr.next_spoke.tqe_prev == NULL)) {
 260                 if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
 261                         TAILQ_INSERT_HEAD(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke);
 262                 } else {
 263                         strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 264                         while (strqt != NULL && (strqt->stream_no < strq->stream_no)) {
 265                                 strqt = TAILQ_NEXT(strqt, ss_params.rr.next_spoke);
 266                         }
 267                         if (strqt != NULL) {
 268                                 TAILQ_INSERT_BEFORE(strqt, strq, ss_params.rr.next_spoke);
 269                         } else {
 270                                 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke);
 271                         }
 272                 }
 273         }
 274         if (holds_lock == 0) {
 275                 SCTP_TCB_SEND_UNLOCK(stcb);
 276         }
 277         return;
 278 }
 279
 280 /*
 281  * Real round-robin per packet algorithm.
 282  * Always interates the streams in ascending order and
 283  * only fills messages of the same stream in a packet.
 284  */
 285 static struct sctp_stream_out *
 286 sctp_ss_rrp_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED,
 287     struct sctp_association *asoc)
 288 {
 289         return (asoc->last_out_stream);
 290 }
 291
 292 static void
 293 sctp_ss_rrp_packet_done(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net,
 294     struct sctp_association *asoc)
 295 {
 296         struct sctp_stream_out *strq, *strqt;
 297
 298         strqt = asoc->last_out_stream;
 299 rrp_again:
 300         /* Find the next stream to use */
 301         if (strqt == NULL) {
 302                 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 303         } else {
 304                 strq = TAILQ_NEXT(strqt, ss_params.rr.next_spoke);
 305                 if (strq == NULL) {
 306                         strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 307                 }
 308         }
 309
 310         /*
 311          * If CMT is off, we must validate that the stream in question has
 312          * the first item pointed towards are network destination requested
 313          * by the caller. Note that if we turn out to be locked to a stream
 314          * (assigning TSN's then we must stop, since we cannot look for
 315          * another stream with data to send to that destination). In CMT's
 316          * case, by skipping this check, we will send one data packet
 317          * towards the requested net.
 318          */
 319         if (net != NULL && strq != NULL &&
 320             SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) {
 321                 if (TAILQ_FIRST(&strq->outqueue) &&
 322                     TAILQ_FIRST(&strq->outqueue)->net != NULL &&
 323                     TAILQ_FIRST(&strq->outqueue)->net != net) {
 324                         if (strq == asoc->last_out_stream) {
 325                                 strq = NULL;
 326                         } else {
 327                                 strqt = strq;
 328                                 goto rrp_again;
 329                         }
 330                 }
 331         }
 332         asoc->last_out_stream = strq;
 333         return;
 334 }
 335
 336
 337 /*
 338  * Priority algorithm.
 339  * Always prefers streams based on their priority id.
 340  */
 341 static void
 342 sctp_ss_prio_clear(struct sctp_tcb *stcb, struct sctp_association *asoc,
 343     int clear_values, int holds_lock)
 344 {
 345         if (holds_lock == 0) {
 346                 SCTP_TCB_SEND_LOCK(stcb);
 347         }
 348         while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
 349                 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 350
 351                 if (clear_values) {
 352                         strq->ss_params.prio.priority = 0;
 353                 }
 354                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.prio.next_spoke);
 355                 strq->ss_params.prio.next_spoke.tqe_next = NULL;
 356                 strq->ss_params.prio.next_spoke.tqe_prev = NULL;
 357
 358         }
 359         asoc->last_out_stream = NULL;
 360         if (holds_lock == 0) {
 361                 SCTP_TCB_SEND_UNLOCK(stcb);
 362         }
 363         return;
 364 }
 365
 366 static void
 367 sctp_ss_prio_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq)
 368 {
 369         strq->ss_params.prio.next_spoke.tqe_next = NULL;
 370         strq->ss_params.prio.next_spoke.tqe_prev = NULL;
 371         if (with_strq != NULL) {
 372                 strq->ss_params.prio.priority = with_strq->ss_params.prio.priority;
 373         } else {
 374                 strq->ss_params.prio.priority = 0;
 375         }
 376         return;
 377 }
 378
 379 static void
 380 sctp_ss_prio_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 381     struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED,
 382     int holds_lock)
 383 {
 384         struct sctp_stream_out *strqt;
 385
 386         if (holds_lock == 0) {
 387                 SCTP_TCB_SEND_LOCK(stcb);
 388         }
 389         /* Add to wheel if not already on it and stream queue not empty */
 390         if (!TAILQ_EMPTY(&strq->outqueue) &&
 391             (strq->ss_params.prio.next_spoke.tqe_next == NULL) &&
 392             (strq->ss_params.prio.next_spoke.tqe_prev == NULL)) {
 393                 if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
 394                         TAILQ_INSERT_HEAD(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke);
 395                 } else {
 396                         strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 397                         while (strqt != NULL && strqt->ss_params.prio.priority < strq->ss_params.prio.priority) {
 398                                 strqt = TAILQ_NEXT(strqt, ss_params.prio.next_spoke);
 399                         }
 400                         if (strqt != NULL) {
 401                                 TAILQ_INSERT_BEFORE(strqt, strq, ss_params.prio.next_spoke);
 402                         } else {
 403                                 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke);
 404                         }
 405                 }
 406         }
 407         if (holds_lock == 0) {
 408                 SCTP_TCB_SEND_UNLOCK(stcb);
 409         }
 410         return;
 411 }
 412
 413 static void
 414 sctp_ss_prio_remove(struct sctp_tcb *stcb, struct sctp_association *asoc,
 415     struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED,
 416     int holds_lock)
 417 {
 418         if (holds_lock == 0) {
 419                 SCTP_TCB_SEND_LOCK(stcb);
 420         }
 421         /*
 422          * Remove from wheel if stream queue is empty and actually is on the
 423          * wheel
 424          */
 425         if (TAILQ_EMPTY(&strq->outqueue) &&
 426             (strq->ss_params.prio.next_spoke.tqe_next != NULL ||
 427             strq->ss_params.prio.next_spoke.tqe_prev != NULL)) {
 428                 if (asoc->last_out_stream == strq) {
 429                         asoc->last_out_stream = TAILQ_PREV(asoc->last_out_stream, sctpwheel_listhead,
 430                             ss_params.prio.next_spoke);
 431                         if (asoc->last_out_stream == NULL) {
 432                                 asoc->last_out_stream = TAILQ_LAST(&asoc->ss_data.out_wheel,
 433                                     sctpwheel_listhead);
 434                         }
 435                         if (asoc->last_out_stream == strq) {
 436                                 asoc->last_out_stream = NULL;
 437                         }
 438                 }
 439                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke);
 440                 strq->ss_params.prio.next_spoke.tqe_next = NULL;
 441                 strq->ss_params.prio.next_spoke.tqe_prev = NULL;
 442         }
 443         if (holds_lock == 0) {
 444                 SCTP_TCB_SEND_UNLOCK(stcb);
 445         }
 446         return;
 447 }
 448
 449 static struct sctp_stream_out *
 450 sctp_ss_prio_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net,
 451     struct sctp_association *asoc)
 452 {
 453         struct sctp_stream_out *strq, *strqt, *strqn;
 454
 455         strqt = asoc->last_out_stream;
 456 prio_again:
 457         /* Find the next stream to use */
 458         if (strqt == NULL) {
 459                 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 460         } else {
 461                 strqn = TAILQ_NEXT(strqt, ss_params.prio.next_spoke);
 462                 if (strqn != NULL &&
 463                     strqn->ss_params.prio.priority == strqt->ss_params.prio.priority) {
 464                         strq = strqn;
 465                 } else {
 466                         strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 467                 }
 468         }
 469
 470         /*
 471          * If CMT is off, we must validate that the stream in question has
 472          * the first item pointed towards are network destination requested
 473          * by the caller. Note that if we turn out to be locked to a stream
 474          * (assigning TSN's then we must stop, since we cannot look for
 475          * another stream with data to send to that destination). In CMT's
 476          * case, by skipping this check, we will send one data packet
 477          * towards the requested net.
 478          */
 479         if (net != NULL && strq != NULL &&
 480             SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) {
 481                 if (TAILQ_FIRST(&strq->outqueue) &&
 482                     TAILQ_FIRST(&strq->outqueue)->net != NULL &&
 483                     TAILQ_FIRST(&strq->outqueue)->net != net) {
 484                         if (strq == asoc->last_out_stream) {
 485                                 return (NULL);
 486                         } else {
 487                                 strqt = strq;
 488                                 goto prio_again;
 489                         }
 490                 }
 491         }
 492         return (strq);
 493 }
 494
 495 static int
 496 sctp_ss_prio_get_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED,
 497     struct sctp_stream_out *strq, uint16_t * value)
 498 {
 499         if (strq == NULL) {
 500                 return (-1);
 501         }
 502         *value = strq->ss_params.prio.priority;
 503         return (1);
 504 }
 505
 506 static int
 507 sctp_ss_prio_set_value(struct sctp_tcb *stcb, struct sctp_association *asoc,
 508     struct sctp_stream_out *strq, uint16_t value)
 509 {
 510         if (strq == NULL) {
 511                 return (-1);
 512         }
 513         strq->ss_params.prio.priority = value;
 514         sctp_ss_prio_remove(stcb, asoc, strq, NULL, 1);
 515         sctp_ss_prio_add(stcb, asoc, strq, NULL, 1);
 516         return (1);
 517 }
 518
 519 /*
 520  * Fair bandwidth algorithm.
 521  * Maintains an equal troughput per stream.
 522  */
 523 static void
 524 sctp_ss_fb_clear(struct sctp_tcb *stcb, struct sctp_association *asoc,
 525     int clear_values, int holds_lock)
 526 {
 527         if (holds_lock == 0) {
 528                 SCTP_TCB_SEND_LOCK(stcb);
 529         }
 530         while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) {
 531                 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 532
 533                 if (clear_values) {
 534                         strq->ss_params.fb.rounds = -1;
 535                 }
 536                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.fb.next_spoke);
 537                 strq->ss_params.fb.next_spoke.tqe_next = NULL;
 538                 strq->ss_params.fb.next_spoke.tqe_prev = NULL;
 539         }
 540         asoc->last_out_stream = NULL;
 541         if (holds_lock == 0) {
 542                 SCTP_TCB_SEND_UNLOCK(stcb);
 543         }
 544         return;
 545 }
 546
 547 static void
 548 sctp_ss_fb_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq)
 549 {
 550         strq->ss_params.fb.next_spoke.tqe_next = NULL;
 551         strq->ss_params.fb.next_spoke.tqe_prev = NULL;
 552         if (with_strq != NULL) {
 553                 strq->ss_params.fb.rounds = with_strq->ss_params.fb.rounds;
 554         } else {
 555                 strq->ss_params.fb.rounds = -1;
 556         }
 557         return;
 558 }
 559
 560 static void
 561 sctp_ss_fb_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 562     struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED,
 563     int holds_lock)
 564 {
 565         if (holds_lock == 0) {
 566                 SCTP_TCB_SEND_LOCK(stcb);
 567         }
 568         if (!TAILQ_EMPTY(&strq->outqueue) &&
 569             (strq->ss_params.fb.next_spoke.tqe_next == NULL) &&
 570             (strq->ss_params.fb.next_spoke.tqe_prev == NULL)) {
 571                 if (strq->ss_params.fb.rounds < 0)
 572                         strq->ss_params.fb.rounds = TAILQ_FIRST(&strq->outqueue)->length;
 573                 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.fb.next_spoke);
 574         }
 575         if (holds_lock == 0) {
 576                 SCTP_TCB_SEND_UNLOCK(stcb);
 577         }
 578         return;
 579 }
 580
 581 static void
 582 sctp_ss_fb_remove(struct sctp_tcb *stcb, struct sctp_association *asoc,
 583     struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED,
 584     int holds_lock)
 585 {
 586         if (holds_lock == 0) {
 587                 SCTP_TCB_SEND_LOCK(stcb);
 588         }
 589         /*
 590          * Remove from wheel if stream queue is empty and actually is on the
 591          * wheel
 592          */
 593         if (TAILQ_EMPTY(&strq->outqueue) &&
 594             (strq->ss_params.fb.next_spoke.tqe_next != NULL ||
 595             strq->ss_params.fb.next_spoke.tqe_prev != NULL)) {
 596                 if (asoc->last_out_stream == strq) {
 597                         asoc->last_out_stream = TAILQ_PREV(asoc->last_out_stream, sctpwheel_listhead,
 598                             ss_params.fb.next_spoke);
 599                         if (asoc->last_out_stream == NULL) {
 600                                 asoc->last_out_stream = TAILQ_LAST(&asoc->ss_data.out_wheel,
 601                                     sctpwheel_listhead);
 602                         }
 603                         if (asoc->last_out_stream == strq) {
 604                                 asoc->last_out_stream = NULL;
 605                         }
 606                 }
 607                 TAILQ_REMOVE(&asoc->ss_data.out_wheel, strq, ss_params.fb.next_spoke);
 608                 strq->ss_params.fb.next_spoke.tqe_next = NULL;
 609                 strq->ss_params.fb.next_spoke.tqe_prev = NULL;
 610         }
 611         if (holds_lock == 0) {
 612                 SCTP_TCB_SEND_UNLOCK(stcb);
 613         }
 614         return;
 615 }
 616
 617 static struct sctp_stream_out *
 618 sctp_ss_fb_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net,
 619     struct sctp_association *asoc)
 620 {
 621         struct sctp_stream_out *strq = NULL, *strqt;
 622
 623         if (asoc->last_out_stream == NULL ||
 624             TAILQ_FIRST(&asoc->ss_data.out_wheel) == TAILQ_LAST(&asoc->ss_data.out_wheel, sctpwheel_listhead)) {
 625                 strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 626         } else {
 627                 strqt = TAILQ_NEXT(asoc->last_out_stream, ss_params.fb.next_spoke);
 628         }
 629         do {
 630                 if ((strqt != NULL) &&
 631                     ((SCTP_BASE_SYSCTL(sctp_cmt_on_off) > 0) ||
 632                     (SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0 &&
 633                     (net == NULL || (TAILQ_FIRST(&strqt->outqueue) && TAILQ_FIRST(&strqt->outqueue)->net == NULL) ||
 634                     (net != NULL && TAILQ_FIRST(&strqt->outqueue) && TAILQ_FIRST(&strqt->outqueue)->net != NULL &&
 635                     TAILQ_FIRST(&strqt->outqueue)->net == net))))) {
 636                         if ((strqt->ss_params.fb.rounds >= 0) && (strq == NULL ||
 637                             strqt->ss_params.fb.rounds < strq->ss_params.fb.rounds)) {
 638                                 strq = strqt;
 639                         }
 640                 }
 641                 if (strqt != NULL) {
 642                         strqt = TAILQ_NEXT(strqt, ss_params.fb.next_spoke);
 643                 } else {
 644                         strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel);
 645                 }
 646         } while (strqt != strq);
 647         return (strq);
 648 }
 649
 650 static void
 651 sctp_ss_fb_scheduled(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED,
 652     struct sctp_association *asoc, struct sctp_stream_out *strq,
 653     int moved_how_much SCTP_UNUSED)
 654 {
 655         struct sctp_stream_out *strqt;
 656         int subtract;
 657
 658         subtract = strq->ss_params.fb.rounds;
 659         TAILQ_FOREACH(strqt, &asoc->ss_data.out_wheel, ss_params.fb.next_spoke) {
 660                 strqt->ss_params.fb.rounds -= subtract;
 661                 if (strqt->ss_params.fb.rounds < 0)
 662                         strqt->ss_params.fb.rounds = 0;
 663         }
 664         if (TAILQ_FIRST(&strq->outqueue)) {
 665                 strq->ss_params.fb.rounds = TAILQ_FIRST(&strq->outqueue)->length;
 666         } else {
 667                 strq->ss_params.fb.rounds = -1;
 668         }
 669         asoc->last_out_stream = strq;
 670         return;
 671 }
 672
 673 /*
 674  * First-come, first-serve algorithm.
 675  * Maintains the order provided by the application.
 676  */
 677 static void
 678 sctp_ss_fcfs_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 679     struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp,
 680     int holds_lock);
 681
 682 static void
 683 sctp_ss_fcfs_init(struct sctp_tcb *stcb, struct sctp_association *asoc,
 684     int holds_lock)
 685 {
 686         uint32_t x, n = 0, add_more = 1;
 687         struct sctp_stream_queue_pending *sp;
 688         uint16_t i;
 689
 690         TAILQ_INIT(&asoc->ss_data.out_list);
 691         /*
 692          * If there is data in the stream queues already, the scheduler of
 693          * an existing association has been changed. We can only cycle
 694          * through the stream queues and add everything to the FCFS queue.
 695          */
 696         while (add_more) {
 697                 add_more = 0;
 698                 for (i = 0; i < stcb->asoc.streamoutcnt; i++) {
 699                         sp = TAILQ_FIRST(&stcb->asoc.strmout[i].outqueue);
 700                         x = 0;
 701                         /* Find n. message in current stream queue */
 702                         while (sp != NULL && x < n) {
 703                                 sp = TAILQ_NEXT(sp, next);
 704                                 x++;
 705                         }
 706                         if (sp != NULL) {
 707                                 sctp_ss_fcfs_add(stcb, &stcb->asoc, &stcb->asoc.strmout[i], sp, holds_lock);
 708                                 add_more = 1;
 709                         }
 710                 }
 711                 n++;
 712         }
 713         return;
 714 }
 715
 716 static void
 717 sctp_ss_fcfs_clear(struct sctp_tcb *stcb, struct sctp_association *asoc,
 718     int clear_values, int holds_lock)
 719 {
 720         if (clear_values) {
 721                 if (holds_lock == 0) {
 722                         SCTP_TCB_SEND_LOCK(stcb);
 723                 }
 724                 while (!TAILQ_EMPTY(&asoc->ss_data.out_list)) {
 725                         TAILQ_REMOVE(&asoc->ss_data.out_list, TAILQ_FIRST(&asoc->ss_data.out_list), ss_next);
 726                 }
 727                 if (holds_lock == 0) {
 728                         SCTP_TCB_SEND_UNLOCK(stcb);
 729                 }
 730         }
 731         return;
 732 }
 733
 734 static void
 735 sctp_ss_fcfs_init_stream(struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_out *with_strq SCTP_UNUSED)
 736 {
 737         /* Nothing to be done here */
 738         return;
 739 }
 740
 741 static void
 742 sctp_ss_fcfs_add(struct sctp_tcb *stcb, struct sctp_association *asoc,
 743     struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_queue_pending *sp,
 744     int holds_lock)
 745 {
 746         if (holds_lock == 0) {
 747                 SCTP_TCB_SEND_LOCK(stcb);
 748         }
 749         if (sp && (sp->ss_next.tqe_next == NULL) &&
 750             (sp->ss_next.tqe_prev == NULL)) {
 751                 TAILQ_INSERT_TAIL(&asoc->ss_data.out_list, sp, ss_next);
 752         }
 753         if (holds_lock == 0) {
 754                 SCTP_TCB_SEND_UNLOCK(stcb);
 755         }
 756         return;
 757 }
 758
 759 static int
 760 sctp_ss_fcfs_is_empty(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc)
 761 {
 762         if (TAILQ_EMPTY(&asoc->ss_data.out_list)) {
 763                 return (1);
 764         } else {
 765                 return (0);
 766         }
 767 }
 768
 769 static void
 770 sctp_ss_fcfs_remove(struct sctp_tcb *stcb, struct sctp_association *asoc,
 771     struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_queue_pending *sp,
 772     int holds_lock)
 773 {
 774         if (holds_lock == 0) {
 775                 SCTP_TCB_SEND_LOCK(stcb);
 776         }
 777         if (sp &&
 778             ((sp->ss_next.tqe_next != NULL) ||
 779             (sp->ss_next.tqe_prev != NULL))) {
 780                 TAILQ_REMOVE(&asoc->ss_data.out_list, sp, ss_next);
 781         }
 782         if (holds_lock == 0) {
 783                 SCTP_TCB_SEND_UNLOCK(stcb);
 784         }
 785         return;
 786 }
 787
 788
 789 static struct sctp_stream_out *
 790 sctp_ss_fcfs_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net,
 791     struct sctp_association *asoc)
 792 {
 793         struct sctp_stream_out *strq;
 794         struct sctp_stream_queue_pending *sp;
 795
 796         sp = TAILQ_FIRST(&asoc->ss_data.out_list);
 797 default_again:
 798         if (sp != NULL) {
 799                 strq = &asoc->strmout[sp->stream];
 800         } else {
 801                 strq = NULL;
 802         }
 803
 804         /*
 805          * If CMT is off, we must validate that the stream in question has
 806          * the first item pointed towards are network destination requested
 807          * by the caller. Note that if we turn out to be locked to a stream
 808          * (assigning TSN's then we must stop, since we cannot look for
 809          * another stream with data to send to that destination). In CMT's
 810          * case, by skipping this check, we will send one data packet
 811          * towards the requested net.
 812          */
 813         if (net != NULL && strq != NULL &&
 814             SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) {
 815                 if (TAILQ_FIRST(&strq->outqueue) &&
 816                     TAILQ_FIRST(&strq->outqueue)->net != NULL &&
 817                     TAILQ_FIRST(&strq->outqueue)->net != net) {
 818                         sp = TAILQ_NEXT(sp, ss_next);
 819                         goto default_again;
 820                 }
 821         }
 822         return (strq);
 823 }
 824
 825 struct sctp_ss_functions sctp_ss_functions[] = {
 826 /* SCTP_SS_DEFAULT */
 827         {
 828                 .sctp_ss_init = sctp_ss_default_init,
 829                 .sctp_ss_clear = sctp_ss_default_clear,
 830                 .sctp_ss_init_stream = sctp_ss_default_init_stream,
 831                 .sctp_ss_add_to_stream = sctp_ss_default_add,
 832                 .sctp_ss_is_empty = sctp_ss_default_is_empty,
 833                 .sctp_ss_remove_from_stream = sctp_ss_default_remove,
 834                 .sctp_ss_select_stream = sctp_ss_default_select,
 835                 .sctp_ss_scheduled = sctp_ss_default_scheduled,
 836                 .sctp_ss_packet_done = sctp_ss_default_packet_done,
 837                 .sctp_ss_get_value = sctp_ss_default_get_value,
 838                 .sctp_ss_set_value = sctp_ss_default_set_value
 839         },
 840 /* SCTP_SS_ROUND_ROBIN */
 841         {
 842                 .sctp_ss_init = sctp_ss_default_init,
 843                 .sctp_ss_clear = sctp_ss_default_clear,
 844                 .sctp_ss_init_stream = sctp_ss_default_init_stream,
 845                 .sctp_ss_add_to_stream = sctp_ss_rr_add,
 846                 .sctp_ss_is_empty = sctp_ss_default_is_empty,
 847                 .sctp_ss_remove_from_stream = sctp_ss_default_remove,
 848                 .sctp_ss_select_stream = sctp_ss_default_select,
 849                 .sctp_ss_scheduled = sctp_ss_default_scheduled,
 850                 .sctp_ss_packet_done = sctp_ss_default_packet_done,
 851                 .sctp_ss_get_value = sctp_ss_default_get_value,
 852                 .sctp_ss_set_value = sctp_ss_default_set_value
 853         },
 854 /* SCTP_SS_ROUND_ROBIN_PACKET */
 855         {
 856                 .sctp_ss_init = sctp_ss_default_init,
 857                 .sctp_ss_clear = sctp_ss_default_clear,
 858                 .sctp_ss_init_stream = sctp_ss_default_init_stream,
 859                 .sctp_ss_add_to_stream = sctp_ss_rr_add,
 860                 .sctp_ss_is_empty = sctp_ss_default_is_empty,
 861                 .sctp_ss_remove_from_stream = sctp_ss_default_remove,
 862                 .sctp_ss_select_stream = sctp_ss_rrp_select,
 863                 .sctp_ss_scheduled = sctp_ss_default_scheduled,
 864                 .sctp_ss_packet_done = sctp_ss_rrp_packet_done,
 865                 .sctp_ss_get_value = sctp_ss_default_get_value,
 866                 .sctp_ss_set_value = sctp_ss_default_set_value
 867         },
 868 /* SCTP_SS_PRIORITY */
 869         {
 870                 .sctp_ss_init = sctp_ss_default_init,
 871                 .sctp_ss_clear = sctp_ss_prio_clear,
 872                 .sctp_ss_init_stream = sctp_ss_prio_init_stream,
 873                 .sctp_ss_add_to_stream = sctp_ss_prio_add,
 874                 .sctp_ss_is_empty = sctp_ss_default_is_empty,
 875                 .sctp_ss_remove_from_stream = sctp_ss_prio_remove,
 876                 .sctp_ss_select_stream = sctp_ss_prio_select,
 877                 .sctp_ss_scheduled = sctp_ss_default_scheduled,
 878                 .sctp_ss_packet_done = sctp_ss_default_packet_done,
 879                 .sctp_ss_get_value = sctp_ss_prio_get_value,
 880                 .sctp_ss_set_value = sctp_ss_prio_set_value
 881         },
 882 /* SCTP_SS_FAIR_BANDWITH */
 883         {
 884                 .sctp_ss_init = sctp_ss_default_init,
 885                 .sctp_ss_clear = sctp_ss_fb_clear,
 886                 .sctp_ss_init_stream = sctp_ss_fb_init_stream,
 887                 .sctp_ss_add_to_stream = sctp_ss_fb_add,
 888                 .sctp_ss_is_empty = sctp_ss_default_is_empty,
 889                 .sctp_ss_remove_from_stream = sctp_ss_fb_remove,
 890                 .sctp_ss_select_stream = sctp_ss_fb_select,
 891                 .sctp_ss_scheduled = sctp_ss_fb_scheduled,
 892                 .sctp_ss_packet_done = sctp_ss_default_packet_done,
 893                 .sctp_ss_get_value = sctp_ss_default_get_value,
 894                 .sctp_ss_set_value = sctp_ss_default_set_value
 895         },
 896 /* SCTP_SS_FIRST_COME */
 897         {
 898                 .sctp_ss_init = sctp_ss_fcfs_init,
 899                 .sctp_ss_clear = sctp_ss_fcfs_clear,
 900                 .sctp_ss_init_stream = sctp_ss_fcfs_init_stream,
 901                 .sctp_ss_add_to_stream = sctp_ss_fcfs_add,
 902                 .sctp_ss_is_empty = sctp_ss_fcfs_is_empty,
 903                 .sctp_ss_remove_from_stream = sctp_ss_fcfs_remove,
 904                 .sctp_ss_select_stream = sctp_ss_fcfs_select,
 905                 .sctp_ss_scheduled = sctp_ss_default_scheduled,
 906                 .sctp_ss_packet_done = sctp_ss_default_packet_done,
 907                 .sctp_ss_get_value = sctp_ss_default_get_value,
 908                 .sctp_ss_set_value = sctp_ss_default_set_value
 909         }
 910 };