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 #ifdef __FreeBSD__ 30 #include <sys/cdefs.h> 31 __FBSDID("$FreeBSD: head/sys/netinet/sctp_ss_functions.c 235828 2012-05-23 11:26:28Z tuexen $"); 32 #endif 33 34 #include <netinet/sctp_pcb.h> 35 #if defined(__Userspace__) 36 #include <netinet/sctp_os_userspace.h> 37 #endif 38 39 /* 40 * Default simple round-robin algorithm. 41 * Just interates the streams in the order they appear. 42 */ 43 44 static void 45 sctp_ss_default_add(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_remove(struct sctp_tcb *, struct sctp_association *, 51 struct sctp_stream_out *, 52 struct sctp_stream_queue_pending *, int); 53 54 static void 55 sctp_ss_default_init(struct sctp_tcb *stcb, struct sctp_association *asoc, 56 int holds_lock) 57 { 58 uint16_t i; 59 60 TAILQ_INIT(&asoc->ss_data.out_wheel); 61 /* 62 * If there is data in the stream queues already, 63 * the scheduler of an existing association has 64 * been changed. We need to add all stream queues 65 * to the wheel. 66 */ 67 for (i = 0; i < stcb->asoc.streamoutcnt; i++) { 68 stcb->asoc.ss_functions.sctp_ss_add_to_stream(stcb, &stcb->asoc, 69 &stcb->asoc.strmout[i], 70 NULL, holds_lock); 71 } 72 return; 73 } 74 75 static void 76 sctp_ss_default_clear(struct sctp_tcb *stcb, struct sctp_association *asoc, 77 int clear_values SCTP_UNUSED, int holds_lock) 78 { 79 if (holds_lock == 0) { 80 SCTP_TCB_SEND_LOCK(stcb); 81 } 82 while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 83 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 84 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.rr.next_spoke); 85 strq->ss_params.rr.next_spoke.tqe_next = NULL; 86 strq->ss_params.rr.next_spoke.tqe_prev = NULL; 87 } 88 asoc->last_out_stream = NULL; 89 if (holds_lock == 0) { 90 SCTP_TCB_SEND_UNLOCK(stcb); 91 } 92 return; 93 } 94 95 static void 96 sctp_ss_default_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq SCTP_UNUSED) 97 { 98 strq->ss_params.rr.next_spoke.tqe_next = NULL; 99 strq->ss_params.rr.next_spoke.tqe_prev = NULL; 100 return; 101 } 102 103 static void 104 sctp_ss_default_add(struct sctp_tcb *stcb, struct sctp_association *asoc, 105 struct sctp_stream_out *strq, 106 struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock) 107 { 108 if (holds_lock == 0) { 109 SCTP_TCB_SEND_LOCK(stcb); 110 } 111 /* Add to wheel if not already on it and stream queue not empty */ 112 if (!TAILQ_EMPTY(&strq->outqueue) && 113 (strq->ss_params.rr.next_spoke.tqe_next == NULL) && 114 (strq->ss_params.rr.next_spoke.tqe_prev == NULL)) { 115 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, 116 strq, ss_params.rr.next_spoke); 117 } 118 if (holds_lock == 0) { 119 SCTP_TCB_SEND_UNLOCK(stcb); 120 } 121 return; 122 } 123 124 static int 125 sctp_ss_default_is_empty(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc) 126 { 127 if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 128 return (1); 129 } else { 130 return (0); 131 } 132 } 133 134 static void 135 sctp_ss_default_remove(struct sctp_tcb *stcb, struct sctp_association *asoc, 136 struct sctp_stream_out *strq, 137 struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock) 138 { 139 if (holds_lock == 0) { 140 SCTP_TCB_SEND_LOCK(stcb); 141 } 142 /* Remove from wheel if stream queue is empty and actually is on the wheel */ 143 if (TAILQ_EMPTY(&strq->outqueue) && 144 (strq->ss_params.rr.next_spoke.tqe_next != NULL || 145 strq->ss_params.rr.next_spoke.tqe_prev != NULL)) { 146 if (asoc->last_out_stream == strq) { 147 asoc->last_out_stream = TAILQ_PREV(asoc->last_out_stream, 148 sctpwheel_listhead, 149 ss_params.rr.next_spoke); 150 if (asoc->last_out_stream == NULL) { 151 asoc->last_out_stream = TAILQ_LAST(&asoc->ss_data.out_wheel, 152 sctpwheel_listhead); 153 } 154 if (asoc->last_out_stream == strq) { 155 asoc->last_out_stream = NULL; 156 } 157 } 158 TAILQ_REMOVE(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke); 159 strq->ss_params.rr.next_spoke.tqe_next = NULL; 160 strq->ss_params.rr.next_spoke.tqe_prev = NULL; 161 } 162 if (holds_lock == 0) { 163 SCTP_TCB_SEND_UNLOCK(stcb); 164 } 165 return; 166 } 167 168 169 static struct sctp_stream_out * 170 sctp_ss_default_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net, 171 struct sctp_association *asoc) 172 { 173 struct sctp_stream_out *strq, *strqt; 174 175 strqt = asoc->last_out_stream; 176 default_again: 177 /* Find the next stream to use */ 178 if (strqt == NULL) { 179 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 180 } else { 181 strq = TAILQ_NEXT(strqt, ss_params.rr.next_spoke); 182 if (strq == NULL) { 183 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 184 } 185 } 186 187 /* If CMT is off, we must validate that 188 * the stream in question has the first 189 * item pointed towards are network destination 190 * requested by the caller. Note that if we 191 * turn out to be locked to a stream (assigning 192 * TSN's then we must stop, since we cannot 193 * look for another stream with data to send 194 * to that destination). In CMT's case, by 195 * skipping this check, we will send one 196 * data packet towards the requested net. 197 */ 198 if (net != NULL && strq != NULL && 199 SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) { 200 if (TAILQ_FIRST(&strq->outqueue) && 201 TAILQ_FIRST(&strq->outqueue)->net != NULL && 202 TAILQ_FIRST(&strq->outqueue)->net != net) { 203 if (strq == asoc->last_out_stream) { 204 return (NULL); 205 } else { 206 strqt = strq; 207 goto default_again; 208 } 209 } 210 } 211 return (strq); 212 } 213 214 static void 215 sctp_ss_default_scheduled(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED, 216 struct sctp_association *asoc SCTP_UNUSED, 217 struct sctp_stream_out *strq, int moved_how_much SCTP_UNUSED) 218 { 219 asoc->last_out_stream = strq; 220 return; 221 } 222 223 static void 224 sctp_ss_default_packet_done(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED, 225 struct sctp_association *asoc SCTP_UNUSED) 226 { 227 /* Nothing to be done here */ 228 return; 229 } 230 231 static int 232 sctp_ss_default_get_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED, 233 struct sctp_stream_out *strq SCTP_UNUSED, uint16_t *value SCTP_UNUSED) 234 { 235 /* Nothing to be done here */ 236 return (-1); 237 } 238 239 static int 240 sctp_ss_default_set_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED, 241 struct sctp_stream_out *strq SCTP_UNUSED, uint16_t value SCTP_UNUSED) 242 { 243 /* Nothing to be done here */ 244 return (-1); 245 } 246 247 /* 248 * Real round-robin algorithm. 249 * Always interates the streams in ascending order. 250 */ 251 static void 252 sctp_ss_rr_add(struct sctp_tcb *stcb, struct sctp_association *asoc, 253 struct sctp_stream_out *strq, 254 struct sctp_stream_queue_pending *sp SCTP_UNUSED, int holds_lock) 255 { 256 struct sctp_stream_out *strqt; 257 258 if (holds_lock == 0) { 259 SCTP_TCB_SEND_LOCK(stcb); 260 } 261 if (!TAILQ_EMPTY(&strq->outqueue) && 262 (strq->ss_params.rr.next_spoke.tqe_next == NULL) && 263 (strq->ss_params.rr.next_spoke.tqe_prev == NULL)) { 264 if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 265 TAILQ_INSERT_HEAD(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke); 266 } else { 267 strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel); 268 while (strqt != NULL && (strqt->stream_no < strq->stream_no)) { 269 strqt = TAILQ_NEXT(strqt, ss_params.rr.next_spoke); 270 } 271 if (strqt != NULL) { 272 TAILQ_INSERT_BEFORE(strqt, strq, ss_params.rr.next_spoke); 273 } else { 274 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.rr.next_spoke); 275 } 276 } 277 } 278 if (holds_lock == 0) { 279 SCTP_TCB_SEND_UNLOCK(stcb); 280 } 281 return; 282 } 283 284 /* 285 * Real round-robin per packet algorithm. 286 * Always interates the streams in ascending order and 287 * only fills messages of the same stream in a packet. 288 */ 289 static struct sctp_stream_out * 290 sctp_ss_rrp_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net SCTP_UNUSED, 291 struct sctp_association *asoc) 292 { 293 return (asoc->last_out_stream); 294 } 295 296 static void 297 sctp_ss_rrp_packet_done(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net, 298 struct sctp_association *asoc) 299 { 300 struct sctp_stream_out *strq, *strqt; 301 302 strqt = asoc->last_out_stream; 303 rrp_again: 304 /* Find the next stream to use */ 305 if (strqt == NULL) { 306 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 307 } else { 308 strq = TAILQ_NEXT(strqt, ss_params.rr.next_spoke); 309 if (strq == NULL) { 310 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 311 } 312 } 313 314 /* If CMT is off, we must validate that 315 * the stream in question has the first 316 * item pointed towards are network destination 317 * requested by the caller. Note that if we 318 * turn out to be locked to a stream (assigning 319 * TSN's then we must stop, since we cannot 320 * look for another stream with data to send 321 * to that destination). In CMT's case, by 322 * skipping this check, we will send one 323 * data packet towards the requested net. 324 */ 325 if (net != NULL && strq != NULL && 326 SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) { 327 if (TAILQ_FIRST(&strq->outqueue) && 328 TAILQ_FIRST(&strq->outqueue)->net != NULL && 329 TAILQ_FIRST(&strq->outqueue)->net != net) { 330 if (strq == asoc->last_out_stream) { 331 strq = NULL; 332 } else { 333 strqt = strq; 334 goto rrp_again; 335 } 336 } 337 } 338 asoc->last_out_stream = strq; 339 return; 340 } 341 342 343 /* 344 * Priority algorithm. 345 * Always prefers streams based on their priority id. 346 */ 347 static void 348 sctp_ss_prio_clear(struct sctp_tcb *stcb, struct sctp_association *asoc, 349 int clear_values, int holds_lock) 350 { 351 if (holds_lock == 0) { 352 SCTP_TCB_SEND_LOCK(stcb); 353 } 354 while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 355 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 356 if (clear_values) { 357 strq->ss_params.prio.priority = 0; 358 } 359 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.prio.next_spoke); 360 strq->ss_params.prio.next_spoke.tqe_next = NULL; 361 strq->ss_params.prio.next_spoke.tqe_prev = NULL; 362 363 } 364 asoc->last_out_stream = NULL; 365 if (holds_lock == 0) { 366 SCTP_TCB_SEND_UNLOCK(stcb); 367 } 368 return; 369 } 370 371 static void 372 sctp_ss_prio_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq) 373 { 374 strq->ss_params.prio.next_spoke.tqe_next = NULL; 375 strq->ss_params.prio.next_spoke.tqe_prev = NULL; 376 if (with_strq != NULL) { 377 strq->ss_params.prio.priority = with_strq->ss_params.prio.priority; 378 } else { 379 strq->ss_params.prio.priority = 0; 380 } 381 return; 382 } 383 384 static void 385 sctp_ss_prio_add(struct sctp_tcb *stcb, struct sctp_association *asoc, 386 struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED, 387 int holds_lock) 388 { 389 struct sctp_stream_out *strqt; 390 391 if (holds_lock == 0) { 392 SCTP_TCB_SEND_LOCK(stcb); 393 } 394 /* Add to wheel if not already on it and stream queue not empty */ 395 if (!TAILQ_EMPTY(&strq->outqueue) && 396 (strq->ss_params.prio.next_spoke.tqe_next == NULL) && 397 (strq->ss_params.prio.next_spoke.tqe_prev == NULL)) { 398 if (TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 399 TAILQ_INSERT_HEAD(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke); 400 } else { 401 strqt = TAILQ_FIRST(&asoc->ss_data.out_wheel); 402 while (strqt != NULL && strqt->ss_params.prio.priority < strq->ss_params.prio.priority) { 403 strqt = TAILQ_NEXT(strqt, ss_params.prio.next_spoke); 404 } 405 if (strqt != NULL) { 406 TAILQ_INSERT_BEFORE(strqt, strq, ss_params.prio.next_spoke); 407 } else { 408 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke); 409 } 410 } 411 } 412 if (holds_lock == 0) { 413 SCTP_TCB_SEND_UNLOCK(stcb); 414 } 415 return; 416 } 417 418 static void 419 sctp_ss_prio_remove(struct sctp_tcb *stcb, struct sctp_association *asoc, 420 struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED, 421 int holds_lock) 422 { 423 if (holds_lock == 0) { 424 SCTP_TCB_SEND_LOCK(stcb); 425 } 426 /* Remove from wheel if stream queue is empty and actually is on the wheel */ 427 if (TAILQ_EMPTY(&strq->outqueue) && 428 (strq->ss_params.prio.next_spoke.tqe_next != NULL || 429 strq->ss_params.prio.next_spoke.tqe_prev != NULL)) { 430 if (asoc->last_out_stream == strq) { 431 asoc->last_out_stream = TAILQ_PREV(asoc->last_out_stream, sctpwheel_listhead, 432 ss_params.prio.next_spoke); 433 if (asoc->last_out_stream == NULL) { 434 asoc->last_out_stream = TAILQ_LAST(&asoc->ss_data.out_wheel, 435 sctpwheel_listhead); 436 } 437 if (asoc->last_out_stream == strq) { 438 asoc->last_out_stream = NULL; 439 } 440 } 441 TAILQ_REMOVE(&asoc->ss_data.out_wheel, strq, ss_params.prio.next_spoke); 442 strq->ss_params.prio.next_spoke.tqe_next = NULL; 443 strq->ss_params.prio.next_spoke.tqe_prev = NULL; 444 } 445 if (holds_lock == 0) { 446 SCTP_TCB_SEND_UNLOCK(stcb); 447 } 448 return; 449 } 450 451 static struct sctp_stream_out* 452 sctp_ss_prio_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net, 453 struct sctp_association *asoc) 454 { 455 struct sctp_stream_out *strq, *strqt, *strqn; 456 457 strqt = asoc->last_out_stream; 458 prio_again: 459 /* Find the next stream to use */ 460 if (strqt == NULL) { 461 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 462 } else { 463 strqn = TAILQ_NEXT(strqt, ss_params.prio.next_spoke); 464 if (strqn != NULL && 465 strqn->ss_params.prio.priority == strqt->ss_params.prio.priority) { 466 strq = strqn; 467 } else { 468 strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 469 } 470 } 471 472 /* If CMT is off, we must validate that 473 * the stream in question has the first 474 * item pointed towards are network destination 475 * requested by the caller. Note that if we 476 * turn out to be locked to a stream (assigning 477 * TSN's then we must stop, since we cannot 478 * look for another stream with data to send 479 * to that destination). In CMT's case, by 480 * skipping this check, we will send one 481 * data packet towards the requested net. 482 */ 483 if (net != NULL && strq != NULL && 484 SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) { 485 if (TAILQ_FIRST(&strq->outqueue) && 486 TAILQ_FIRST(&strq->outqueue)->net != NULL && 487 TAILQ_FIRST(&strq->outqueue)->net != net) { 488 if (strq == asoc->last_out_stream) { 489 return (NULL); 490 } else { 491 strqt = strq; 492 goto prio_again; 493 } 494 } 495 } 496 return (strq); 497 } 498 499 static int 500 sctp_ss_prio_get_value(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc SCTP_UNUSED, 501 struct sctp_stream_out *strq, uint16_t *value) 502 { 503 if (strq == NULL) { 504 return (-1); 505 } 506 *value = strq->ss_params.prio.priority; 507 return (1); 508 } 509 510 static int 511 sctp_ss_prio_set_value(struct sctp_tcb *stcb, struct sctp_association *asoc, 512 struct sctp_stream_out *strq, uint16_t value) 513 { 514 if (strq == NULL) { 515 return (-1); 516 } 517 strq->ss_params.prio.priority = value; 518 sctp_ss_prio_remove(stcb, asoc, strq, NULL, 1); 519 sctp_ss_prio_add(stcb, asoc, strq, NULL, 1); 520 return (1); 521 } 522 523 /* 524 * Fair bandwidth algorithm. 525 * Maintains an equal troughput per stream. 526 */ 527 static void 528 sctp_ss_fb_clear(struct sctp_tcb *stcb, struct sctp_association *asoc, 529 int clear_values, int holds_lock) 530 { 531 if (holds_lock == 0) { 532 SCTP_TCB_SEND_LOCK(stcb); 533 } 534 while (!TAILQ_EMPTY(&asoc->ss_data.out_wheel)) { 535 struct sctp_stream_out *strq = TAILQ_FIRST(&asoc->ss_data.out_wheel); 536 if (clear_values) { 537 strq->ss_params.fb.rounds = -1; 538 } 539 TAILQ_REMOVE(&asoc->ss_data.out_wheel, TAILQ_FIRST(&asoc->ss_data.out_wheel), ss_params.fb.next_spoke); 540 strq->ss_params.fb.next_spoke.tqe_next = NULL; 541 strq->ss_params.fb.next_spoke.tqe_prev = NULL; 542 } 543 asoc->last_out_stream = NULL; 544 if (holds_lock == 0) { 545 SCTP_TCB_SEND_UNLOCK(stcb); 546 } 547 return; 548 } 549 550 static void 551 sctp_ss_fb_init_stream(struct sctp_stream_out *strq, struct sctp_stream_out *with_strq) 552 { 553 strq->ss_params.fb.next_spoke.tqe_next = NULL; 554 strq->ss_params.fb.next_spoke.tqe_prev = NULL; 555 if (with_strq != NULL) { 556 strq->ss_params.fb.rounds = with_strq->ss_params.fb.rounds; 557 } else { 558 strq->ss_params.fb.rounds = -1; 559 } 560 return; 561 } 562 563 static void 564 sctp_ss_fb_add(struct sctp_tcb *stcb, struct sctp_association *asoc, 565 struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED, 566 int holds_lock) 567 { 568 if (holds_lock == 0) { 569 SCTP_TCB_SEND_LOCK(stcb); 570 } 571 if (!TAILQ_EMPTY(&strq->outqueue) && 572 (strq->ss_params.fb.next_spoke.tqe_next == NULL) && 573 (strq->ss_params.fb.next_spoke.tqe_prev == NULL)) { 574 if (strq->ss_params.fb.rounds < 0) 575 strq->ss_params.fb.rounds = TAILQ_FIRST(&strq->outqueue)->length; 576 TAILQ_INSERT_TAIL(&asoc->ss_data.out_wheel, strq, ss_params.fb.next_spoke); 577 } 578 if (holds_lock == 0) { 579 SCTP_TCB_SEND_UNLOCK(stcb); 580 } 581 return; 582 } 583 584 static void 585 sctp_ss_fb_remove(struct sctp_tcb *stcb, struct sctp_association *asoc, 586 struct sctp_stream_out *strq, struct sctp_stream_queue_pending *sp SCTP_UNUSED, 587 int holds_lock) 588 { 589 if (holds_lock == 0) { 590 SCTP_TCB_SEND_LOCK(stcb); 591 } 592 /* Remove from wheel if stream queue is empty and actually is on the wheel */ 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, 693 * the scheduler of an existing association has 694 * been changed. We can only cycle through the 695 * stream queues and add everything to the FCFS 696 * queue. 697 */ 698 while (add_more) { 699 add_more = 0; 700 for (i = 0; i < stcb->asoc.streamoutcnt; i++) { 701 sp = TAILQ_FIRST(&stcb->asoc.strmout[i].outqueue); 702 x = 0; 703 /* Find n. message in current stream queue */ 704 while (sp != NULL && x < n) { 705 sp = TAILQ_NEXT(sp, next); 706 x++; 707 } 708 if (sp != NULL) { 709 sctp_ss_fcfs_add(stcb, &stcb->asoc, &stcb->asoc.strmout[i], sp, holds_lock); 710 add_more = 1; 711 } 712 } 713 n++; 714 } 715 return; 716 } 717 718 static void 719 sctp_ss_fcfs_clear(struct sctp_tcb *stcb, struct sctp_association *asoc, 720 int clear_values, int holds_lock) 721 { 722 if (clear_values) { 723 if (holds_lock == 0) { 724 SCTP_TCB_SEND_LOCK(stcb); 725 } 726 while (!TAILQ_EMPTY(&asoc->ss_data.out_list)) { 727 TAILQ_REMOVE(&asoc->ss_data.out_list, TAILQ_FIRST(&asoc->ss_data.out_list), ss_next); 728 } 729 if (holds_lock == 0) { 730 SCTP_TCB_SEND_UNLOCK(stcb); 731 } 732 } 733 return; 734 } 735 736 static void 737 sctp_ss_fcfs_init_stream(struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_out *with_strq SCTP_UNUSED) 738 { 739 /* Nothing to be done here */ 740 return; 741 } 742 743 static void 744 sctp_ss_fcfs_add(struct sctp_tcb *stcb, struct sctp_association *asoc, 745 struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_queue_pending *sp, 746 int holds_lock) 747 { 748 if (holds_lock == 0) { 749 SCTP_TCB_SEND_LOCK(stcb); 750 } 751 if (sp && (sp->ss_next.tqe_next == NULL) && 752 (sp->ss_next.tqe_prev == NULL)) { 753 TAILQ_INSERT_TAIL(&asoc->ss_data.out_list, sp, ss_next); 754 } 755 if (holds_lock == 0) { 756 SCTP_TCB_SEND_UNLOCK(stcb); 757 } 758 return; 759 } 760 761 static int 762 sctp_ss_fcfs_is_empty(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_association *asoc) 763 { 764 if (TAILQ_EMPTY(&asoc->ss_data.out_list)) { 765 return (1); 766 } else { 767 return (0); 768 } 769 } 770 771 static void 772 sctp_ss_fcfs_remove(struct sctp_tcb *stcb, struct sctp_association *asoc, 773 struct sctp_stream_out *strq SCTP_UNUSED, struct sctp_stream_queue_pending *sp, 774 int holds_lock) 775 { 776 if (holds_lock == 0) { 777 SCTP_TCB_SEND_LOCK(stcb); 778 } 779 if (sp && 780 ((sp->ss_next.tqe_next != NULL) || 781 (sp->ss_next.tqe_prev != NULL))) { 782 TAILQ_REMOVE(&asoc->ss_data.out_list, sp, ss_next); 783 } 784 if (holds_lock == 0) { 785 SCTP_TCB_SEND_UNLOCK(stcb); 786 } 787 return; 788 } 789 790 791 static struct sctp_stream_out * 792 sctp_ss_fcfs_select(struct sctp_tcb *stcb SCTP_UNUSED, struct sctp_nets *net, 793 struct sctp_association *asoc) 794 { 795 struct sctp_stream_out *strq; 796 struct sctp_stream_queue_pending *sp; 797 798 sp = TAILQ_FIRST(&asoc->ss_data.out_list); 799 default_again: 800 if (sp != NULL) { 801 strq = &asoc->strmout[sp->stream]; 802 } else { 803 strq = NULL; 804 } 805 806 /* 807 * If CMT is off, we must validate that 808 * the stream in question has the first 809 * item pointed towards are network destination 810 * requested by the caller. Note that if we 811 * turn out to be locked to a stream (assigning 812 * TSN's then we must stop, since we cannot 813 * look for another stream with data to send 814 * to that destination). In CMT's case, by 815 * skipping this check, we will send one 816 * data packet towards the requested net. 817 */ 818 if (net != NULL && strq != NULL && 819 SCTP_BASE_SYSCTL(sctp_cmt_on_off) == 0) { 820 if (TAILQ_FIRST(&strq->outqueue) && 821 TAILQ_FIRST(&strq->outqueue)->net != NULL && 822 TAILQ_FIRST(&strq->outqueue)->net != net) { 823 sp = TAILQ_NEXT(sp, ss_next); 824 goto default_again; 825 } 826 } 827 return (strq); 828 } 829 830 struct sctp_ss_functions sctp_ss_functions[] = { 831 /* SCTP_SS_DEFAULT */ 832 { 833 #if defined(__Windows__) || defined(__Userspace_os_Windows) 834 sctp_ss_default_init, 835 sctp_ss_default_clear, 836 sctp_ss_default_init_stream, 837 sctp_ss_default_add, 838 sctp_ss_default_is_empty, 839 sctp_ss_default_remove, 840 sctp_ss_default_select, 841 sctp_ss_default_scheduled, 842 sctp_ss_default_packet_done, 843 sctp_ss_default_get_value, 844 sctp_ss_default_set_value 845 #else 846 .sctp_ss_init = sctp_ss_default_init, 847 .sctp_ss_clear = sctp_ss_default_clear, 848 .sctp_ss_init_stream = sctp_ss_default_init_stream, 849 .sctp_ss_add_to_stream = sctp_ss_default_add, 850 .sctp_ss_is_empty = sctp_ss_default_is_empty, 851 .sctp_ss_remove_from_stream = sctp_ss_default_remove, 852 .sctp_ss_select_stream = sctp_ss_default_select, 853 .sctp_ss_scheduled = sctp_ss_default_scheduled, 854 .sctp_ss_packet_done = sctp_ss_default_packet_done, 855 .sctp_ss_get_value = sctp_ss_default_get_value, 856 .sctp_ss_set_value = sctp_ss_default_set_value 857 #endif 858 }, 859 /* SCTP_SS_ROUND_ROBIN */ 860 { 861 #if defined(__Windows__) || defined(__Userspace_os_Windows) 862 sctp_ss_default_init, 863 sctp_ss_default_clear, 864 sctp_ss_default_init_stream, 865 sctp_ss_rr_add, 866 sctp_ss_default_is_empty, 867 sctp_ss_default_remove, 868 sctp_ss_default_select, 869 sctp_ss_default_scheduled, 870 sctp_ss_default_packet_done, 871 sctp_ss_default_get_value, 872 sctp_ss_default_set_value 873 #else 874 .sctp_ss_init = sctp_ss_default_init, 875 .sctp_ss_clear = sctp_ss_default_clear, 876 .sctp_ss_init_stream = sctp_ss_default_init_stream, 877 .sctp_ss_add_to_stream = sctp_ss_rr_add, 878 .sctp_ss_is_empty = sctp_ss_default_is_empty, 879 .sctp_ss_remove_from_stream = sctp_ss_default_remove, 880 .sctp_ss_select_stream = sctp_ss_default_select, 881 .sctp_ss_scheduled = sctp_ss_default_scheduled, 882 .sctp_ss_packet_done = sctp_ss_default_packet_done, 883 .sctp_ss_get_value = sctp_ss_default_get_value, 884 .sctp_ss_set_value = sctp_ss_default_set_value 885 #endif 886 }, 887 /* SCTP_SS_ROUND_ROBIN_PACKET */ 888 { 889 #if defined(__Windows__) || defined(__Userspace_os_Windows) 890 sctp_ss_default_init, 891 sctp_ss_default_clear, 892 sctp_ss_default_init_stream, 893 sctp_ss_rr_add, 894 sctp_ss_default_is_empty, 895 sctp_ss_default_remove, 896 sctp_ss_rrp_select, 897 sctp_ss_default_scheduled, 898 sctp_ss_rrp_packet_done, 899 sctp_ss_default_get_value, 900 sctp_ss_default_set_value 901 #else 902 .sctp_ss_init = sctp_ss_default_init, 903 .sctp_ss_clear = sctp_ss_default_clear, 904 .sctp_ss_init_stream = sctp_ss_default_init_stream, 905 .sctp_ss_add_to_stream = sctp_ss_rr_add, 906 .sctp_ss_is_empty = sctp_ss_default_is_empty, 907 .sctp_ss_remove_from_stream = sctp_ss_default_remove, 908 .sctp_ss_select_stream = sctp_ss_rrp_select, 909 .sctp_ss_scheduled = sctp_ss_default_scheduled, 910 .sctp_ss_packet_done = sctp_ss_rrp_packet_done, 911 .sctp_ss_get_value = sctp_ss_default_get_value, 912 .sctp_ss_set_value = sctp_ss_default_set_value 913 #endif 914 }, 915 /* SCTP_SS_PRIORITY */ 916 { 917 #if defined(__Windows__) || defined(__Userspace_os_Windows) 918 sctp_ss_default_init, 919 sctp_ss_prio_clear, 920 sctp_ss_prio_init_stream, 921 sctp_ss_prio_add, 922 sctp_ss_default_is_empty, 923 sctp_ss_prio_remove, 924 sctp_ss_prio_select, 925 sctp_ss_default_scheduled, 926 sctp_ss_default_packet_done, 927 sctp_ss_prio_get_value, 928 sctp_ss_prio_set_value 929 #else 930 .sctp_ss_init = sctp_ss_default_init, 931 .sctp_ss_clear = sctp_ss_prio_clear, 932 .sctp_ss_init_stream = sctp_ss_prio_init_stream, 933 .sctp_ss_add_to_stream = sctp_ss_prio_add, 934 .sctp_ss_is_empty = sctp_ss_default_is_empty, 935 .sctp_ss_remove_from_stream = sctp_ss_prio_remove, 936 .sctp_ss_select_stream = sctp_ss_prio_select, 937 .sctp_ss_scheduled = sctp_ss_default_scheduled, 938 .sctp_ss_packet_done = sctp_ss_default_packet_done, 939 .sctp_ss_get_value = sctp_ss_prio_get_value, 940 .sctp_ss_set_value = sctp_ss_prio_set_value 941 #endif 942 }, 943 /* SCTP_SS_FAIR_BANDWITH */ 944 { 945 #if defined(__Windows__) || defined(__Userspace_os_Windows) 946 sctp_ss_default_init, 947 sctp_ss_fb_clear, 948 sctp_ss_fb_init_stream, 949 sctp_ss_fb_add, 950 sctp_ss_default_is_empty, 951 sctp_ss_fb_remove, 952 sctp_ss_fb_select, 953 sctp_ss_fb_scheduled, 954 sctp_ss_default_packet_done, 955 sctp_ss_default_get_value, 956 sctp_ss_default_set_value 957 #else 958 .sctp_ss_init = sctp_ss_default_init, 959 .sctp_ss_clear = sctp_ss_fb_clear, 960 .sctp_ss_init_stream = sctp_ss_fb_init_stream, 961 .sctp_ss_add_to_stream = sctp_ss_fb_add, 962 .sctp_ss_is_empty = sctp_ss_default_is_empty, 963 .sctp_ss_remove_from_stream = sctp_ss_fb_remove, 964 .sctp_ss_select_stream = sctp_ss_fb_select, 965 .sctp_ss_scheduled = sctp_ss_fb_scheduled, 966 .sctp_ss_packet_done = sctp_ss_default_packet_done, 967 .sctp_ss_get_value = sctp_ss_default_get_value, 968 .sctp_ss_set_value = sctp_ss_default_set_value 969 #endif 970 }, 971 /* SCTP_SS_FIRST_COME */ 972 { 973 #if defined(__Windows__) || defined(__Userspace_os_Windows) 974 sctp_ss_fcfs_init, 975 sctp_ss_fcfs_clear, 976 sctp_ss_fcfs_init_stream, 977 sctp_ss_fcfs_add, 978 sctp_ss_fcfs_is_empty, 979 sctp_ss_fcfs_remove, 980 sctp_ss_fcfs_select, 981 sctp_ss_default_scheduled, 982 sctp_ss_default_packet_done, 983 sctp_ss_default_get_value, 984 sctp_ss_default_set_value 985 #else 986 .sctp_ss_init = sctp_ss_fcfs_init, 987 .sctp_ss_clear = sctp_ss_fcfs_clear, 988 .sctp_ss_init_stream = sctp_ss_fcfs_init_stream, 989 .sctp_ss_add_to_stream = sctp_ss_fcfs_add, 990 .sctp_ss_is_empty = sctp_ss_fcfs_is_empty, 991 .sctp_ss_remove_from_stream = sctp_ss_fcfs_remove, 992 .sctp_ss_select_stream = sctp_ss_fcfs_select, 993 .sctp_ss_scheduled = sctp_ss_default_scheduled, 994 .sctp_ss_packet_done = sctp_ss_default_packet_done, 995 .sctp_ss_get_value = sctp_ss_default_get_value, 996 .sctp_ss_set_value = sctp_ss_default_set_value 997 #endif 998 } 999 }; 1000