1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* 28 * Device Strategy 29 */ 30 #include <sys/dktp/cm.h> 31 #include <sys/kstat.h> 32 33 #include <sys/dktp/quetypes.h> 34 #include <sys/dktp/queue.h> 35 #include <sys/dktp/tgcom.h> 36 #include <sys/dktp/fctypes.h> 37 #include <sys/dktp/flowctrl.h> 38 #include <sys/param.h> 39 #include <vm/page.h> 40 #include <sys/modctl.h> 41 42 /* 43 * Object Management 44 */ 45 46 static struct buf *qmerge_nextbp(struct que_data *qfp, struct buf *bp_merge, 47 int *can_merge); 48 49 static struct modlmisc modlmisc = { 50 &mod_miscops, /* Type of module */ 51 "Device Strategy Objects" 52 }; 53 54 static struct modlinkage modlinkage = { 55 MODREV_1, 56 &modlmisc, 57 NULL 58 }; 59 60 int 61 _init(void) 62 { 63 return (mod_install(&modlinkage)); 64 } 65 66 int 67 _fini(void) 68 { 69 return (mod_remove(&modlinkage)); 70 } 71 72 int 73 _info(struct modinfo *modinfop) 74 { 75 return (mod_info(&modlinkage, modinfop)); 76 } 77 78 79 /* 80 * Common Flow Control functions 81 */ 82 83 /* 84 * Local static data 85 */ 86 #ifdef FLC_DEBUG 87 #define DENT 0x0001 88 #define DERR 0x0002 89 #define DIO 0x0004 90 static int flc_debug = DENT|DERR|DIO; 91 92 #include <sys/thread.h> 93 static int flc_malloc_intr = 0; 94 #endif /* FLC_DEBUG */ 95 96 static int flc_kstat = 1; 97 98 static struct flc_obj *fc_create(struct flc_objops *fcopsp); 99 static int fc_init(opaque_t queuep, opaque_t tgcom_objp, opaque_t que_objp, 100 void *lkarg); 101 static int fc_free(struct flc_obj *flcobjp); 102 static int fc_start_kstat(opaque_t queuep, char *devtype, int instance); 103 static int fc_stop_kstat(opaque_t queuep); 104 105 static struct flc_obj * 106 fc_create(struct flc_objops *fcopsp) 107 { 108 struct flc_obj *flcobjp; 109 struct fc_data *fcdp; 110 111 flcobjp = kmem_zalloc((sizeof (*flcobjp) + sizeof (*fcdp)), KM_NOSLEEP); 112 if (!flcobjp) 113 return (NULL); 114 115 fcdp = (struct fc_data *)(flcobjp+1); 116 flcobjp->flc_data = (opaque_t)fcdp; 117 flcobjp->flc_ops = fcopsp; 118 119 return ((opaque_t)flcobjp); 120 } 121 122 static int dmult_maxcnt = DMULT_MAXCNT; 123 124 static int 125 fc_init(opaque_t queuep, opaque_t tgcom_objp, opaque_t que_objp, void *lkarg) 126 { 127 struct fc_data *fcdp = (struct fc_data *)queuep; 128 129 mutex_init(&fcdp->ds_mutex, NULL, MUTEX_DRIVER, lkarg); 130 131 fcdp->ds_queobjp = que_objp; 132 fcdp->ds_tgcomobjp = tgcom_objp; 133 fcdp->ds_waitcnt = dmult_maxcnt; 134 135 QUE_INIT(que_objp, lkarg); 136 TGCOM_INIT(tgcom_objp); 137 return (DDI_SUCCESS); 138 } 139 140 static int 141 fc_free(struct flc_obj *flcobjp) 142 { 143 struct fc_data *fcdp; 144 145 fcdp = (struct fc_data *)flcobjp->flc_data; 146 if (fcdp->ds_queobjp) 147 QUE_FREE(fcdp->ds_queobjp); 148 if (fcdp->ds_tgcomobjp) { 149 TGCOM_FREE(fcdp->ds_tgcomobjp); 150 mutex_destroy(&fcdp->ds_mutex); 151 } 152 kmem_free(flcobjp, (sizeof (*flcobjp) + sizeof (*fcdp))); 153 return (0); 154 } 155 156 /*ARGSUSED*/ 157 static int 158 fc_start_kstat(opaque_t queuep, char *devtype, int instance) 159 { 160 struct fc_data *fcdp = (struct fc_data *)queuep; 161 if (!flc_kstat) 162 return (0); 163 164 if (!fcdp->ds_kstat) { 165 if (fcdp->ds_kstat = kstat_create("cmdk", instance, NULL, 166 "disk", KSTAT_TYPE_IO, 1, KSTAT_FLAG_PERSISTENT)) { 167 kstat_install(fcdp->ds_kstat); 168 } 169 } 170 return (0); 171 } 172 173 static int 174 fc_stop_kstat(opaque_t queuep) 175 { 176 struct fc_data *fcdp = (struct fc_data *)queuep; 177 178 if (fcdp->ds_kstat) { 179 kstat_delete(fcdp->ds_kstat); 180 fcdp->ds_kstat = NULL; 181 } 182 return (0); 183 } 184 185 186 /* 187 * Single Command per Device 188 */ 189 /* 190 * Local Function Prototypes 191 */ 192 static int dsngl_restart(); 193 194 static int dsngl_enque(opaque_t, struct buf *); 195 static int dsngl_deque(opaque_t, struct buf *); 196 197 struct flc_objops dsngl_ops = { 198 fc_init, 199 fc_free, 200 dsngl_enque, 201 dsngl_deque, 202 fc_start_kstat, 203 fc_stop_kstat, 204 0, 0 205 }; 206 207 struct flc_obj * 208 dsngl_create() 209 { 210 return (fc_create((struct flc_objops *)&dsngl_ops)); 211 } 212 213 static int 214 dsngl_enque(opaque_t queuep, struct buf *in_bp) 215 { 216 struct fc_data *dsnglp = (struct fc_data *)queuep; 217 opaque_t tgcom_objp; 218 opaque_t que_objp; 219 220 que_objp = dsnglp->ds_queobjp; 221 tgcom_objp = dsnglp->ds_tgcomobjp; 222 223 if (!in_bp) 224 return (0); 225 mutex_enter(&dsnglp->ds_mutex); 226 if (dsnglp->ds_bp || dsnglp->ds_outcnt) { 227 QUE_ADD(que_objp, in_bp); 228 if (dsnglp->ds_kstat) { 229 kstat_waitq_enter(KSTAT_IO_PTR(dsnglp->ds_kstat)); 230 } 231 mutex_exit(&dsnglp->ds_mutex); 232 return (0); 233 } 234 if (dsnglp->ds_kstat) { 235 kstat_waitq_enter(KSTAT_IO_PTR(dsnglp->ds_kstat)); 236 } 237 if (TGCOM_PKT(tgcom_objp, in_bp, dsngl_restart, 238 (caddr_t)dsnglp) != DDI_SUCCESS) { 239 240 dsnglp->ds_bp = in_bp; 241 mutex_exit(&dsnglp->ds_mutex); 242 return (0); 243 } 244 dsnglp->ds_outcnt++; 245 if (dsnglp->ds_kstat) 246 kstat_waitq_to_runq(KSTAT_IO_PTR(dsnglp->ds_kstat)); 247 mutex_exit(&dsnglp->ds_mutex); 248 TGCOM_TRANSPORT(tgcom_objp, in_bp); 249 return (0); 250 } 251 252 static int 253 dsngl_deque(opaque_t queuep, struct buf *in_bp) 254 { 255 struct fc_data *dsnglp = (struct fc_data *)queuep; 256 opaque_t tgcom_objp; 257 opaque_t que_objp; 258 struct buf *bp; 259 260 que_objp = dsnglp->ds_queobjp; 261 tgcom_objp = dsnglp->ds_tgcomobjp; 262 263 mutex_enter(&dsnglp->ds_mutex); 264 if (in_bp) { 265 dsnglp->ds_outcnt--; 266 if (dsnglp->ds_kstat) { 267 if (in_bp->b_flags & B_READ) { 268 KSTAT_IO_PTR(dsnglp->ds_kstat)->reads++; 269 KSTAT_IO_PTR(dsnglp->ds_kstat)->nread += 270 (in_bp->b_bcount - in_bp->b_resid); 271 } else { 272 KSTAT_IO_PTR(dsnglp->ds_kstat)->writes++; 273 KSTAT_IO_PTR(dsnglp->ds_kstat)->nwritten += 274 (in_bp->b_bcount - in_bp->b_resid); 275 } 276 kstat_runq_exit(KSTAT_IO_PTR(dsnglp->ds_kstat)); 277 } 278 } 279 for (;;) { 280 if (!dsnglp->ds_bp) 281 dsnglp->ds_bp = QUE_DEL(que_objp); 282 if (!dsnglp->ds_bp || 283 (TGCOM_PKT(tgcom_objp, dsnglp->ds_bp, dsngl_restart, 284 (caddr_t)dsnglp) != DDI_SUCCESS) || 285 dsnglp->ds_outcnt) { 286 mutex_exit(&dsnglp->ds_mutex); 287 return (0); 288 } 289 dsnglp->ds_outcnt++; 290 bp = dsnglp->ds_bp; 291 dsnglp->ds_bp = QUE_DEL(que_objp); 292 if (dsnglp->ds_kstat) 293 kstat_waitq_to_runq(KSTAT_IO_PTR(dsnglp->ds_kstat)); 294 mutex_exit(&dsnglp->ds_mutex); 295 296 TGCOM_TRANSPORT(tgcom_objp, bp); 297 298 if (!mutex_tryenter(&dsnglp->ds_mutex)) 299 return (0); 300 } 301 } 302 303 static int 304 dsngl_restart(struct fc_data *dsnglp) 305 { 306 (void) dsngl_deque(dsnglp, NULL); 307 return (-1); 308 } 309 310 311 /* 312 * Multiple Commands per Device 313 */ 314 /* 315 * Local Function Prototypes 316 */ 317 static int dmult_restart(); 318 319 static int dmult_enque(opaque_t, struct buf *); 320 static int dmult_deque(opaque_t, struct buf *); 321 322 struct flc_objops dmult_ops = { 323 fc_init, 324 fc_free, 325 dmult_enque, 326 dmult_deque, 327 fc_start_kstat, 328 fc_stop_kstat, 329 0, 0 330 }; 331 332 struct flc_obj * 333 dmult_create() 334 { 335 return (fc_create((struct flc_objops *)&dmult_ops)); 336 337 } 338 339 340 /* 341 * Some of the object management functions QUE_ADD() and QUE_DEL() 342 * do not accquire lock. 343 * They depend on dmult_enque(), dmult_deque() to do all locking. 344 * If this changes we have to grab locks in qmerge_add() and qmerge_del(). 345 */ 346 static int 347 dmult_enque(opaque_t queuep, struct buf *in_bp) 348 { 349 struct fc_data *dmultp = (struct fc_data *)queuep; 350 opaque_t tgcom_objp; 351 opaque_t que_objp; 352 353 que_objp = dmultp->ds_queobjp; 354 tgcom_objp = dmultp->ds_tgcomobjp; 355 356 if (!in_bp) 357 return (0); 358 mutex_enter(&dmultp->ds_mutex); 359 if ((dmultp->ds_outcnt >= dmultp->ds_waitcnt) || dmultp->ds_bp) { 360 QUE_ADD(que_objp, in_bp); 361 if (dmultp->ds_kstat) { 362 kstat_waitq_enter(KSTAT_IO_PTR(dmultp->ds_kstat)); 363 } 364 mutex_exit(&dmultp->ds_mutex); 365 return (0); 366 } 367 if (dmultp->ds_kstat) { 368 kstat_waitq_enter(KSTAT_IO_PTR(dmultp->ds_kstat)); 369 } 370 371 if (TGCOM_PKT(tgcom_objp, in_bp, dmult_restart, 372 (caddr_t)dmultp) != DDI_SUCCESS) { 373 374 dmultp->ds_bp = in_bp; 375 mutex_exit(&dmultp->ds_mutex); 376 return (0); 377 } 378 dmultp->ds_outcnt++; 379 if (dmultp->ds_kstat) 380 kstat_waitq_to_runq(KSTAT_IO_PTR(dmultp->ds_kstat)); 381 mutex_exit(&dmultp->ds_mutex); 382 383 TGCOM_TRANSPORT(tgcom_objp, in_bp); 384 return (0); 385 } 386 387 static int 388 dmult_deque(opaque_t queuep, struct buf *in_bp) 389 { 390 struct fc_data *dmultp = (struct fc_data *)queuep; 391 opaque_t tgcom_objp; 392 opaque_t que_objp; 393 struct buf *bp; 394 395 que_objp = dmultp->ds_queobjp; 396 tgcom_objp = dmultp->ds_tgcomobjp; 397 398 mutex_enter(&dmultp->ds_mutex); 399 if (in_bp) { 400 dmultp->ds_outcnt--; 401 if (dmultp->ds_kstat) { 402 if (in_bp->b_flags & B_READ) { 403 KSTAT_IO_PTR(dmultp->ds_kstat)->reads++; 404 KSTAT_IO_PTR(dmultp->ds_kstat)->nread += 405 (in_bp->b_bcount - in_bp->b_resid); 406 } else { 407 KSTAT_IO_PTR(dmultp->ds_kstat)->writes++; 408 KSTAT_IO_PTR(dmultp->ds_kstat)->nwritten += 409 (in_bp->b_bcount - in_bp->b_resid); 410 } 411 kstat_runq_exit(KSTAT_IO_PTR(dmultp->ds_kstat)); 412 } 413 } 414 415 for (;;) { 416 417 #ifdef FLC_DEBUG 418 if ((curthread->t_intr) && (!dmultp->ds_bp) && 419 (!dmultp->ds_outcnt)) 420 flc_malloc_intr++; 421 #endif 422 423 if (!dmultp->ds_bp) 424 dmultp->ds_bp = QUE_DEL(que_objp); 425 if (!dmultp->ds_bp || 426 (TGCOM_PKT(tgcom_objp, dmultp->ds_bp, dmult_restart, 427 (caddr_t)dmultp) != DDI_SUCCESS) || 428 (dmultp->ds_outcnt >= dmultp->ds_waitcnt)) { 429 mutex_exit(&dmultp->ds_mutex); 430 return (0); 431 } 432 dmultp->ds_outcnt++; 433 bp = dmultp->ds_bp; 434 dmultp->ds_bp = QUE_DEL(que_objp); 435 436 if (dmultp->ds_kstat) 437 kstat_waitq_to_runq(KSTAT_IO_PTR(dmultp->ds_kstat)); 438 439 mutex_exit(&dmultp->ds_mutex); 440 441 TGCOM_TRANSPORT(tgcom_objp, bp); 442 443 if (!mutex_tryenter(&dmultp->ds_mutex)) 444 return (0); 445 } 446 } 447 448 static int 449 dmult_restart(struct fc_data *dmultp) 450 { 451 (void) dmult_deque(dmultp, NULL); 452 return (-1); 453 } 454 455 /* 456 * Duplexed Commands per Device: Read Queue and Write Queue 457 */ 458 /* 459 * Local Function Prototypes 460 */ 461 static int duplx_restart(); 462 463 static int duplx_init(opaque_t queuep, opaque_t tgcom_objp, opaque_t que_objp, 464 void *lkarg); 465 static int duplx_free(struct flc_obj *flcobjp); 466 static int duplx_enque(opaque_t queuep, struct buf *bp); 467 static int duplx_deque(opaque_t queuep, struct buf *bp); 468 469 struct flc_objops duplx_ops = { 470 duplx_init, 471 duplx_free, 472 duplx_enque, 473 duplx_deque, 474 fc_start_kstat, 475 fc_stop_kstat, 476 0, 0 477 }; 478 479 struct flc_obj * 480 duplx_create() 481 { 482 struct flc_obj *flcobjp; 483 struct duplx_data *fcdp; 484 485 flcobjp = kmem_zalloc((sizeof (*flcobjp) + sizeof (*fcdp)), KM_NOSLEEP); 486 if (!flcobjp) 487 return (NULL); 488 489 fcdp = (struct duplx_data *)(flcobjp+1); 490 flcobjp->flc_data = (opaque_t)fcdp; 491 flcobjp->flc_ops = &duplx_ops; 492 493 fcdp->ds_writeq.fc_qobjp = qfifo_create(); 494 if (!(fcdp->ds_writeq.fc_qobjp = qfifo_create())) { 495 kmem_free(flcobjp, (sizeof (*flcobjp) + sizeof (*fcdp))); 496 return (NULL); 497 } 498 return (flcobjp); 499 } 500 501 static int 502 duplx_free(struct flc_obj *flcobjp) 503 { 504 struct duplx_data *fcdp; 505 506 fcdp = (struct duplx_data *)flcobjp->flc_data; 507 if (fcdp->ds_writeq.fc_qobjp) { 508 QUE_FREE(fcdp->ds_writeq.fc_qobjp); 509 } 510 if (fcdp->ds_readq.fc_qobjp) 511 QUE_FREE(fcdp->ds_readq.fc_qobjp); 512 if (fcdp->ds_tgcomobjp) { 513 TGCOM_FREE(fcdp->ds_tgcomobjp); 514 mutex_destroy(&fcdp->ds_mutex); 515 } 516 kmem_free(flcobjp, (sizeof (*flcobjp) + sizeof (*fcdp))); 517 return (0); 518 } 519 520 static int 521 duplx_init(opaque_t queuep, opaque_t tgcom_objp, opaque_t que_objp, void *lkarg) 522 { 523 struct duplx_data *fcdp = (struct duplx_data *)queuep; 524 fcdp->ds_tgcomobjp = tgcom_objp; 525 fcdp->ds_readq.fc_qobjp = que_objp; 526 527 QUE_INIT(que_objp, lkarg); 528 QUE_INIT(fcdp->ds_writeq.fc_qobjp, lkarg); 529 TGCOM_INIT(tgcom_objp); 530 531 mutex_init(&fcdp->ds_mutex, NULL, MUTEX_DRIVER, lkarg); 532 533 fcdp->ds_writeq.fc_maxcnt = DUPLX_MAXCNT; 534 fcdp->ds_readq.fc_maxcnt = DUPLX_MAXCNT; 535 536 /* queues point to each other for round robin */ 537 fcdp->ds_readq.next = &fcdp->ds_writeq; 538 fcdp->ds_writeq.next = &fcdp->ds_readq; 539 540 return (DDI_SUCCESS); 541 } 542 543 static int 544 duplx_enque(opaque_t queuep, struct buf *in_bp) 545 { 546 struct duplx_data *duplxp = (struct duplx_data *)queuep; 547 opaque_t tgcom_objp; 548 struct fc_que *activeq; 549 struct buf *bp; 550 551 mutex_enter(&duplxp->ds_mutex); 552 if (in_bp) { 553 if (duplxp->ds_kstat) { 554 kstat_waitq_enter(KSTAT_IO_PTR(duplxp->ds_kstat)); 555 } 556 if (in_bp->b_flags & B_READ) 557 activeq = &duplxp->ds_readq; 558 else 559 activeq = &duplxp->ds_writeq; 560 561 QUE_ADD(activeq->fc_qobjp, in_bp); 562 } else { 563 activeq = &duplxp->ds_readq; 564 } 565 566 tgcom_objp = duplxp->ds_tgcomobjp; 567 568 for (;;) { 569 if (!activeq->fc_bp) 570 activeq->fc_bp = QUE_DEL(activeq->fc_qobjp); 571 if (!activeq->fc_bp || 572 (TGCOM_PKT(tgcom_objp, activeq->fc_bp, duplx_restart, 573 (caddr_t)duplxp) != DDI_SUCCESS) || 574 (activeq->fc_outcnt >= activeq->fc_maxcnt)) { 575 576 /* switch read/write queues */ 577 activeq = activeq->next; 578 if (!activeq->fc_bp) 579 activeq->fc_bp = QUE_DEL(activeq->fc_qobjp); 580 if (!activeq->fc_bp || 581 (TGCOM_PKT(tgcom_objp, activeq->fc_bp, 582 duplx_restart, (caddr_t)duplxp) != DDI_SUCCESS) || 583 (activeq->fc_outcnt >= activeq->fc_maxcnt)) { 584 mutex_exit(&duplxp->ds_mutex); 585 return (0); 586 } 587 } 588 589 activeq->fc_outcnt++; 590 bp = activeq->fc_bp; 591 activeq->fc_bp = NULL; 592 593 if (duplxp->ds_kstat) 594 kstat_waitq_to_runq(KSTAT_IO_PTR(duplxp->ds_kstat)); 595 mutex_exit(&duplxp->ds_mutex); 596 597 TGCOM_TRANSPORT(tgcom_objp, bp); 598 599 if (!mutex_tryenter(&duplxp->ds_mutex)) 600 return (0); 601 602 activeq = activeq->next; 603 } 604 } 605 606 static int 607 duplx_deque(opaque_t queuep, struct buf *in_bp) 608 { 609 struct duplx_data *duplxp = (struct duplx_data *)queuep; 610 opaque_t tgcom_objp; 611 struct fc_que *activeq; 612 struct buf *bp; 613 614 mutex_enter(&duplxp->ds_mutex); 615 616 tgcom_objp = duplxp->ds_tgcomobjp; 617 618 if (in_bp->b_flags & B_READ) 619 activeq = &duplxp->ds_readq; 620 else 621 activeq = &duplxp->ds_writeq; 622 activeq->fc_outcnt--; 623 624 if (duplxp->ds_kstat) { 625 if (in_bp->b_flags & B_READ) { 626 KSTAT_IO_PTR(duplxp->ds_kstat)->reads++; 627 KSTAT_IO_PTR(duplxp->ds_kstat)->nread += 628 (in_bp->b_bcount - in_bp->b_resid); 629 } else { 630 KSTAT_IO_PTR(duplxp->ds_kstat)->writes++; 631 KSTAT_IO_PTR(duplxp->ds_kstat)->nwritten += 632 (in_bp->b_bcount - in_bp->b_resid); 633 } 634 kstat_runq_exit(KSTAT_IO_PTR(duplxp->ds_kstat)); 635 } 636 637 for (;;) { 638 639 /* if needed, try to pull request off a queue */ 640 if (!activeq->fc_bp) 641 activeq->fc_bp = QUE_DEL(activeq->fc_qobjp); 642 643 if (!activeq->fc_bp || 644 (TGCOM_PKT(tgcom_objp, activeq->fc_bp, duplx_restart, 645 (caddr_t)duplxp) != DDI_SUCCESS) || 646 (activeq->fc_outcnt >= activeq->fc_maxcnt)) { 647 648 activeq = activeq->next; 649 if (!activeq->fc_bp) 650 activeq->fc_bp = QUE_DEL(activeq->fc_qobjp); 651 652 if (!activeq->fc_bp || 653 (TGCOM_PKT(tgcom_objp, activeq->fc_bp, 654 duplx_restart, (caddr_t)duplxp) != DDI_SUCCESS) || 655 (activeq->fc_outcnt >= activeq->fc_maxcnt)) { 656 mutex_exit(&duplxp->ds_mutex); 657 return (0); 658 } 659 } 660 661 activeq->fc_outcnt++; 662 bp = activeq->fc_bp; 663 activeq->fc_bp = NULL; 664 665 if (duplxp->ds_kstat) 666 kstat_waitq_to_runq(KSTAT_IO_PTR(duplxp->ds_kstat)); 667 668 mutex_exit(&duplxp->ds_mutex); 669 670 TGCOM_TRANSPORT(tgcom_objp, bp); 671 672 if (!mutex_tryenter(&duplxp->ds_mutex)) 673 return (0); 674 675 activeq = activeq->next; 676 } 677 } 678 679 static int 680 duplx_restart(struct duplx_data *duplxp) 681 { 682 (void) duplx_enque(duplxp, NULL); 683 return (-1); 684 } 685 686 /* 687 * Tagged queueing flow control 688 */ 689 /* 690 * Local Function Prototypes 691 */ 692 693 struct flc_objops adapt_ops = { 694 fc_init, 695 fc_free, 696 dmult_enque, 697 dmult_deque, 698 fc_start_kstat, 699 fc_stop_kstat, 700 0, 0 701 }; 702 703 struct flc_obj * 704 adapt_create() 705 { 706 return (fc_create((struct flc_objops *)&adapt_ops)); 707 708 } 709 710 /* 711 * Common Queue functions 712 */ 713 714 /* 715 * Local static data 716 */ 717 #ifdef Q_DEBUG 718 #define DENT 0x0001 719 #define DERR 0x0002 720 #define DIO 0x0004 721 static int que_debug = DENT|DERR|DIO; 722 723 #endif /* Q_DEBUG */ 724 /* 725 * Local Function Prototypes 726 */ 727 static struct que_obj *que_create(struct que_objops *qopsp); 728 static int que_init(struct que_data *qfp, void *lkarg); 729 static int que_free(struct que_obj *queobjp); 730 static struct buf *que_del(struct que_data *qfp); 731 732 static struct que_obj * 733 que_create(struct que_objops *qopsp) 734 { 735 struct que_data *qfp; 736 struct que_obj *queobjp; 737 738 queobjp = kmem_zalloc((sizeof (*queobjp) + sizeof (*qfp)), KM_NOSLEEP); 739 if (!queobjp) 740 return (NULL); 741 742 queobjp->que_ops = qopsp; 743 qfp = (struct que_data *)(queobjp+1); 744 queobjp->que_data = (opaque_t)qfp; 745 746 return ((opaque_t)queobjp); 747 } 748 749 static int 750 que_init(struct que_data *qfp, void *lkarg) 751 { 752 mutex_init(&qfp->q_mutex, NULL, MUTEX_DRIVER, lkarg); 753 return (DDI_SUCCESS); 754 } 755 756 static int 757 que_free(struct que_obj *queobjp) 758 { 759 struct que_data *qfp; 760 761 qfp = (struct que_data *)queobjp->que_data; 762 mutex_destroy(&qfp->q_mutex); 763 kmem_free(queobjp, (sizeof (*queobjp) + sizeof (struct que_data))); 764 return (0); 765 } 766 767 static struct buf * 768 que_del(struct que_data *qfp) 769 { 770 struct buf *bp; 771 772 bp = qfp->q_tab.b_actf; 773 if (bp) { 774 qfp->q_tab.b_actf = bp->av_forw; 775 if (!qfp->q_tab.b_actf) 776 qfp->q_tab.b_actl = NULL; 777 bp->av_forw = 0; 778 } 779 return (bp); 780 } 781 782 783 784 /* 785 * Qmerge 786 * Local Function Prototypes 787 */ 788 static int qmerge_add(), qmerge_free(); 789 static struct buf *qmerge_del(struct que_data *qfp); 790 791 struct que_objops qmerge_ops = { 792 que_init, 793 qmerge_free, 794 qmerge_add, 795 qmerge_del, 796 0, 0 797 }; 798 799 /* fields in diskhd */ 800 #define hd_cnt b_back 801 #define hd_private b_forw 802 #define hd_flags b_flags 803 #define hd_sync_next av_forw 804 #define hd_async_next av_back 805 806 #define hd_sync2async sync_async_ratio 807 808 #define QNEAR_FORWARD 0x01 809 #define QNEAR_BACKWARD 0x02 810 #define QNEAR_ASYNCONLY 0x04 811 #define QNEAR_ASYNCALSO 0x08 812 813 #define DBLK(bp) ((unsigned long)(bp)->b_private) 814 815 #define BP_LT_BP(a, b) (DBLK(a) < DBLK(b)) 816 #define BP_GT_BP(a, b) (DBLK(a) > DBLK(b)) 817 #define BP_LT_HD(a, b) (DBLK(a) < (unsigned long)((b)->hd_private)) 818 #define BP_GT_HD(a, b) (DBLK(a) > (unsigned long)((b)->hd_private)) 819 #define QNEAR_ASYNC (QNEAR_ASYNCONLY|QNEAR_ASYNCALSO) 820 821 #define SYNC2ASYNC(a) ((a)->q_tab.hd_cnt) 822 823 824 /* 825 * qmerge implements a two priority queue, the low priority queue holding ASYNC 826 * write requests, while the rest are queued in the high priority sync queue. 827 * Requests on the async queue would be merged if possible. 828 * By default qmerge2wayscan is 1, indicating an elevator algorithm. When 829 * this variable is set to zero, it has the following side effects. 830 * 1. We assume fairness is the number one issue. 831 * 2. The next request to be picked indicates current head position. 832 * 833 * qmerge_sync2async indicates the ratio of scans of high prioriy 834 * sync queue to low priority async queue. 835 * 836 * When qmerge variables have the following values it defaults to qsort 837 * 838 * qmerge1pri = 1, qmerge2wayscan = 0, qmerge_max_merge = 0 839 * 840 */ 841 static int qmerge_max_merge = 128 * 1024; 842 static intptr_t qmerge_sync2async = 4; 843 static int qmerge2wayscan = 1; 844 static int qmerge1pri = 0; 845 static int qmerge_merge = 0; 846 847 /* 848 * Local static data 849 */ 850 struct que_obj * 851 qmerge_create() 852 { 853 struct que_data *qfp; 854 struct que_obj *queobjp; 855 856 queobjp = kmem_zalloc((sizeof (*queobjp) + sizeof (*qfp)), KM_NOSLEEP); 857 if (!queobjp) 858 return (NULL); 859 860 queobjp->que_ops = &qmerge_ops; 861 qfp = (struct que_data *)(queobjp+1); 862 qfp->q_tab.hd_private = 0; 863 qfp->q_tab.hd_sync_next = qfp->q_tab.hd_async_next = NULL; 864 qfp->q_tab.hd_cnt = (void *)qmerge_sync2async; 865 queobjp->que_data = (opaque_t)qfp; 866 867 return ((opaque_t)queobjp); 868 } 869 870 static int 871 qmerge_free(struct que_obj *queobjp) 872 { 873 struct que_data *qfp; 874 875 qfp = (struct que_data *)queobjp->que_data; 876 mutex_destroy(&qfp->q_mutex); 877 kmem_free(queobjp, (sizeof (*queobjp) + sizeof (*qfp))); 878 return (0); 879 } 880 881 static int 882 qmerge_can_merge(bp1, bp2) 883 struct buf *bp1, *bp2; 884 { 885 const int paw_flags = B_PAGEIO | B_ASYNC | B_WRITE; 886 887 if ((bp1->b_un.b_addr != 0) || (bp2->b_un.b_addr != 0) || 888 ((bp1->b_flags & (paw_flags | B_REMAPPED)) != paw_flags) || 889 ((bp2->b_flags & (paw_flags | B_REMAPPED)) != paw_flags) || 890 (bp1->b_bcount & PAGEOFFSET) || (bp2->b_bcount & PAGEOFFSET) || 891 (bp1->b_bcount + bp2->b_bcount > qmerge_max_merge)) 892 return (0); 893 894 if ((DBLK(bp2) + bp2->b_bcount / DEV_BSIZE == DBLK(bp1)) || 895 (DBLK(bp1) + bp1->b_bcount / DEV_BSIZE == DBLK(bp2))) 896 return (1); 897 else 898 return (0); 899 } 900 901 static void 902 qmerge_mergesetup(bp_merge, bp) 903 struct buf *bp_merge, *bp; 904 { 905 struct buf *bp1; 906 struct page *pp, *pp_merge, *pp_merge_prev; 907 int forward; 908 909 qmerge_merge++; 910 forward = DBLK(bp_merge) < DBLK(bp); 911 912 bp_merge->b_bcount += bp->b_bcount; 913 914 pp = bp->b_pages; 915 pp_merge = bp_merge->b_pages; 916 917 pp_merge_prev = pp_merge->p_prev; 918 919 pp_merge->p_prev->p_next = pp; 920 pp_merge->p_prev = pp->p_prev; 921 pp->p_prev->p_next = pp_merge; 922 pp->p_prev = pp_merge_prev; 923 924 bp1 = bp_merge->b_forw; 925 926 bp1->av_back->av_forw = bp; 927 bp->av_back = bp1->av_back; 928 bp1->av_back = bp; 929 bp->av_forw = bp1; 930 931 if (!forward) { 932 bp_merge->b_forw = bp; 933 bp_merge->b_pages = pp; 934 bp_merge->b_private = bp->b_private; 935 } 936 } 937 938 static void 939 que_insert(struct que_data *qfp, struct buf *bp) 940 { 941 struct buf *bp1, *bp_start, *lowest_bp, *highest_bp; 942 uintptr_t highest_blk, lowest_blk; 943 struct buf **async_bpp, **sync_bpp, **bpp; 944 struct diskhd *dp = &qfp->q_tab; 945 946 sync_bpp = &dp->hd_sync_next; 947 async_bpp = &dp->hd_async_next; 948 /* 949 * The ioctl used by the format utility requires that bp->av_back be 950 * preserved. 951 */ 952 if (bp->av_back) 953 bp->b_error = (intptr_t)bp->av_back; 954 if (!qmerge1pri && 955 ((bp->b_flags & (B_ASYNC|B_READ|B_FREE)) == B_ASYNC)) { 956 bpp = &dp->hd_async_next; 957 } else { 958 bpp = &dp->hd_sync_next; 959 } 960 961 962 if ((bp1 = *bpp) == NULL) { 963 *bpp = bp; 964 bp->av_forw = bp->av_back = bp; 965 if ((bpp == async_bpp) && (*sync_bpp == NULL)) { 966 dp->hd_flags |= QNEAR_ASYNCONLY; 967 } else if (bpp == sync_bpp) { 968 dp->hd_flags &= ~QNEAR_ASYNCONLY; 969 if (*async_bpp) { 970 dp->hd_flags |= QNEAR_ASYNCALSO; 971 } 972 } 973 return; 974 } 975 bp_start = bp1; 976 if (DBLK(bp) < DBLK(bp1)) { 977 lowest_blk = DBLK(bp1); 978 lowest_bp = bp1; 979 do { 980 if (DBLK(bp) > DBLK(bp1)) { 981 bp->av_forw = bp1->av_forw; 982 bp1->av_forw->av_back = bp; 983 bp1->av_forw = bp; 984 bp->av_back = bp1; 985 986 if (((bpp == async_bpp) && 987 (dp->hd_flags & QNEAR_ASYNC)) || 988 (bpp == sync_bpp)) { 989 if (!(dp->hd_flags & QNEAR_BACKWARD) && 990 BP_GT_HD(bp, dp)) { 991 *bpp = bp; 992 } 993 } 994 return; 995 } else if (DBLK(bp1) < lowest_blk) { 996 lowest_bp = bp1; 997 lowest_blk = DBLK(bp1); 998 } 999 } while ((DBLK(bp1->av_back) < DBLK(bp1)) && 1000 ((bp1 = bp1->av_back) != bp_start)); 1001 bp->av_forw = lowest_bp; 1002 lowest_bp->av_back->av_forw = bp; 1003 bp->av_back = lowest_bp->av_back; 1004 lowest_bp->av_back = bp; 1005 if ((bpp == async_bpp) && !(dp->hd_flags & QNEAR_ASYNC)) { 1006 *bpp = bp; 1007 } else if (!(dp->hd_flags & QNEAR_BACKWARD) && 1008 BP_GT_HD(bp, dp)) { 1009 *bpp = bp; 1010 } 1011 } else { 1012 highest_blk = DBLK(bp1); 1013 highest_bp = bp1; 1014 do { 1015 if (DBLK(bp) < DBLK(bp1)) { 1016 bp->av_forw = bp1; 1017 bp1->av_back->av_forw = bp; 1018 bp->av_back = bp1->av_back; 1019 bp1->av_back = bp; 1020 if (((bpp == async_bpp) && 1021 (dp->hd_flags & QNEAR_ASYNC)) || 1022 (bpp == sync_bpp)) { 1023 if ((dp->hd_flags & QNEAR_BACKWARD) && 1024 BP_LT_HD(bp, dp)) { 1025 *bpp = bp; 1026 } 1027 } 1028 return; 1029 } else if (DBLK(bp1) > highest_blk) { 1030 highest_bp = bp1; 1031 highest_blk = DBLK(bp1); 1032 } 1033 } while ((DBLK(bp1->av_forw) > DBLK(bp1)) && 1034 ((bp1 = bp1->av_forw) != bp_start)); 1035 bp->av_back = highest_bp; 1036 highest_bp->av_forw->av_back = bp; 1037 bp->av_forw = highest_bp->av_forw; 1038 highest_bp->av_forw = bp; 1039 1040 if (((bpp == sync_bpp) || 1041 ((bpp == async_bpp) && (dp->hd_flags & QNEAR_ASYNC))) && 1042 (dp->hd_flags & QNEAR_BACKWARD) && (BP_LT_HD(bp, dp))) 1043 *bpp = bp; 1044 } 1045 } 1046 1047 /* 1048 * dmult_enque() holds dmultp->ds_mutex lock, so we dont grab 1049 * lock here. If dmult_enque() changes we will have to visit 1050 * this function again 1051 */ 1052 static int 1053 qmerge_add(struct que_data *qfp, struct buf *bp) 1054 { 1055 1056 que_insert(qfp, bp); 1057 return (++qfp->q_cnt); 1058 } 1059 1060 static int 1061 qmerge_iodone(struct buf *bp) 1062 { 1063 struct buf *bp1; 1064 struct page *pp, *pp1, *tmp_pp; 1065 1066 if (bp->b_flags & B_REMAPPED) 1067 bp_mapout(bp); 1068 1069 bp1 = bp->b_forw; 1070 do { 1071 bp->b_forw = bp1->av_forw; 1072 bp1->av_forw->av_back = bp1->av_back; 1073 bp1->av_back->av_forw = bp1->av_forw; 1074 pp = (page_t *)bp1->b_pages; 1075 pp1 = bp->b_forw->b_pages; 1076 1077 tmp_pp = pp->p_prev; 1078 pp->p_prev = pp1->p_prev; 1079 pp->p_prev->p_next = pp; 1080 1081 pp1->p_prev = tmp_pp; 1082 pp1->p_prev->p_next = pp1; 1083 1084 if (bp->b_flags & B_ERROR) { 1085 bp1->b_error = bp->b_error; 1086 bp1->b_flags |= B_ERROR; 1087 } 1088 1089 biodone(bp1); 1090 } while ((bp1 = bp->b_forw) != bp->b_forw->av_forw); 1091 1092 biodone(bp1); 1093 kmem_free(bp, sizeof (*bp)); 1094 return (0); 1095 } 1096 1097 1098 1099 1100 static struct buf * 1101 qmerge_nextbp(struct que_data *qfp, struct buf *bp_merge, int *can_merge) 1102 { 1103 intptr_t private, cnt; 1104 int flags; 1105 struct buf *sync_bp, *async_bp, *bp; 1106 struct buf **sync_bpp, **async_bpp, **bpp; 1107 struct diskhd *dp = &qfp->q_tab; 1108 1109 if (qfp->q_cnt == 0) { 1110 return (NULL); 1111 } 1112 flags = qfp->q_tab.hd_flags; 1113 sync_bpp = &qfp->q_tab.hd_sync_next; 1114 async_bpp = &qfp->q_tab.hd_async_next; 1115 1116 begin_nextbp: 1117 if (flags & QNEAR_ASYNCONLY) { 1118 bp = *async_bpp; 1119 private = DBLK(bp); 1120 if (bp_merge && !qmerge_can_merge(bp, bp_merge)) { 1121 return (NULL); 1122 } else if (bp->av_forw == bp) { 1123 bp->av_forw = bp->av_back = NULL; 1124 flags &= ~(QNEAR_ASYNCONLY | QNEAR_BACKWARD); 1125 private = 0; 1126 } else if (flags & QNEAR_BACKWARD) { 1127 if (DBLK(bp) < DBLK(bp->av_back)) { 1128 flags &= ~QNEAR_BACKWARD; 1129 private = 0; 1130 } 1131 } else if (DBLK(bp) > DBLK(bp->av_forw)) { 1132 if (qmerge2wayscan) { 1133 flags |= QNEAR_BACKWARD; 1134 } else { 1135 private = 0; 1136 } 1137 } else if (qmerge2wayscan == 0) { 1138 private = DBLK(bp->av_forw); 1139 } 1140 bpp = async_bpp; 1141 1142 } else if (flags & QNEAR_ASYNCALSO) { 1143 sync_bp = *sync_bpp; 1144 async_bp = *async_bpp; 1145 if (flags & QNEAR_BACKWARD) { 1146 if (BP_GT_HD(sync_bp, dp) && BP_GT_HD(async_bp, dp)) { 1147 flags &= ~(QNEAR_BACKWARD|QNEAR_ASYNCALSO); 1148 *sync_bpp = sync_bp->av_forw; 1149 *async_bpp = async_bp->av_forw; 1150 SYNC2ASYNC(qfp) = (void *)qmerge_sync2async; 1151 qfp->q_tab.hd_private = 0; 1152 goto begin_nextbp; 1153 } 1154 if (BP_LT_HD(async_bp, dp) && BP_LT_HD(sync_bp, dp)) { 1155 if (BP_GT_BP(async_bp, sync_bp)) { 1156 bpp = async_bpp; 1157 bp = *async_bpp; 1158 } else { 1159 bpp = sync_bpp; 1160 bp = *sync_bpp; 1161 } 1162 } else if (BP_LT_HD(async_bp, dp)) { 1163 bpp = async_bpp; 1164 bp = *async_bpp; 1165 } else { 1166 bpp = sync_bpp; 1167 bp = *sync_bpp; 1168 } 1169 } else { 1170 if (BP_LT_HD(sync_bp, dp) && BP_LT_HD(async_bp, dp)) { 1171 if (qmerge2wayscan) { 1172 flags |= QNEAR_BACKWARD; 1173 *sync_bpp = sync_bp->av_back; 1174 *async_bpp = async_bp->av_back; 1175 goto begin_nextbp; 1176 } else { 1177 flags &= ~QNEAR_ASYNCALSO; 1178 SYNC2ASYNC(qfp) = 1179 (void *)qmerge_sync2async; 1180 qfp->q_tab.hd_private = 0; 1181 goto begin_nextbp; 1182 } 1183 } 1184 if (BP_GT_HD(async_bp, dp) && BP_GT_HD(sync_bp, dp)) { 1185 if (BP_LT_BP(async_bp, sync_bp)) { 1186 bpp = async_bpp; 1187 bp = *async_bpp; 1188 } else { 1189 bpp = sync_bpp; 1190 bp = *sync_bpp; 1191 } 1192 } else if (BP_GT_HD(async_bp, dp)) { 1193 bpp = async_bpp; 1194 bp = *async_bpp; 1195 } else { 1196 bpp = sync_bpp; 1197 bp = *sync_bpp; 1198 } 1199 } 1200 if (bp_merge && !qmerge_can_merge(bp, bp_merge)) { 1201 return (NULL); 1202 } else if (bp->av_forw == bp) { 1203 bp->av_forw = bp->av_back = NULL; 1204 flags &= ~QNEAR_ASYNCALSO; 1205 if (bpp == async_bpp) { 1206 SYNC2ASYNC(qfp) = (void *)qmerge_sync2async; 1207 } else { 1208 flags |= QNEAR_ASYNCONLY; 1209 } 1210 } 1211 private = DBLK(bp); 1212 } else { 1213 bp = *sync_bpp; 1214 private = DBLK(bp); 1215 if (bp_merge && !qmerge_can_merge(bp, bp_merge)) { 1216 return (NULL); 1217 } else if (bp->av_forw == bp) { 1218 private = 0; 1219 SYNC2ASYNC(qfp) = (void *)qmerge_sync2async; 1220 bp->av_forw = bp->av_back = NULL; 1221 flags &= ~QNEAR_BACKWARD; 1222 if (*async_bpp) 1223 flags |= QNEAR_ASYNCONLY; 1224 } else if (flags & QNEAR_BACKWARD) { 1225 if (DBLK(bp) < DBLK(bp->av_back)) { 1226 flags &= ~QNEAR_BACKWARD; 1227 cnt = (intptr_t)SYNC2ASYNC(qfp); 1228 if (cnt > 0) { 1229 cnt--; 1230 SYNC2ASYNC(qfp) = (void *)cnt; 1231 } else { 1232 if (*async_bpp) 1233 flags |= QNEAR_ASYNCALSO; 1234 SYNC2ASYNC(qfp) = 1235 (void *)qmerge_sync2async; 1236 } 1237 private = 0; 1238 } 1239 } else if (DBLK(bp) > DBLK(bp->av_forw)) { 1240 private = 0; 1241 if (qmerge2wayscan) { 1242 flags |= QNEAR_BACKWARD; 1243 private = DBLK(bp); 1244 } else { 1245 cnt = (intptr_t)SYNC2ASYNC(qfp); 1246 if (cnt > 0) { 1247 cnt--; 1248 SYNC2ASYNC(qfp) = (void *)cnt; 1249 } else { 1250 if (*async_bpp) 1251 flags |= QNEAR_ASYNCALSO; 1252 SYNC2ASYNC(qfp) = 1253 (void *)qmerge_sync2async; 1254 } 1255 } 1256 } else if (qmerge2wayscan == 0) { 1257 private = DBLK(bp->av_forw); 1258 } 1259 bpp = sync_bpp; 1260 } 1261 1262 if (bp->av_forw) { 1263 *can_merge = !(bp->b_flags & B_READ); 1264 if (flags & QNEAR_BACKWARD) { 1265 *bpp = bp->av_back; 1266 if ((DBLK(bp->av_back) + 1267 bp->av_back->b_bcount / DEV_BSIZE) != DBLK(bp)) 1268 *can_merge = 0; 1269 } else { 1270 *bpp = bp->av_forw; 1271 if ((DBLK(bp) + bp->b_bcount / DEV_BSIZE) != 1272 DBLK(bp->av_forw)) 1273 *can_merge = 0; 1274 } 1275 bp->av_forw->av_back = bp->av_back; 1276 bp->av_back->av_forw = bp->av_forw; 1277 bp->av_forw = bp->av_back = NULL; 1278 } else { 1279 *bpp = NULL; 1280 *can_merge = 0; 1281 } 1282 qfp->q_tab.hd_private = (void *)private; 1283 qfp->q_cnt--; 1284 qfp->q_tab.hd_flags = flags; 1285 if (bp->b_error) { 1286 bp->av_back = (void *)(intptr_t)bp->b_error; 1287 bp->b_error = 0; 1288 } 1289 return (bp); 1290 } 1291 1292 static struct buf * 1293 qmerge_del(struct que_data *qfp) 1294 { 1295 struct buf *bp, *next_bp, *bp_merge; 1296 int alloc_mergebp, merge; 1297 1298 if (qfp->q_cnt == 0) { 1299 return (NULL); 1300 } 1301 1302 bp_merge = bp = qmerge_nextbp(qfp, NULL, &merge); 1303 alloc_mergebp = 1; 1304 while (merge && (next_bp = qmerge_nextbp(qfp, bp_merge, &merge))) { 1305 if (alloc_mergebp) { 1306 bp_merge = kmem_alloc(sizeof (*bp_merge), KM_NOSLEEP); 1307 if (bp_merge == NULL) { 1308 mutex_exit(&qfp->q_mutex); 1309 return (bp); 1310 } 1311 bcopy(bp, bp_merge, sizeof (*bp_merge)); 1312 bp_merge->b_iodone = qmerge_iodone; 1313 bp_merge->b_forw = bp; 1314 bp_merge->b_back = (struct buf *)qfp; 1315 bp->av_forw = bp->av_back = bp; 1316 alloc_mergebp = 0; 1317 } 1318 qmerge_mergesetup(bp_merge, next_bp); 1319 } 1320 return (bp_merge); 1321 } 1322 1323 1324 /* 1325 * FIFO Queue functions 1326 */ 1327 /* 1328 * Local Function Prototypes 1329 */ 1330 static int qfifo_add(); 1331 1332 struct que_objops qfifo_ops = { 1333 que_init, 1334 que_free, 1335 qfifo_add, 1336 que_del, 1337 0, 0 1338 }; 1339 1340 /* 1341 * Local static data 1342 */ 1343 struct que_obj * 1344 qfifo_create() 1345 { 1346 return (que_create((struct que_objops *)&qfifo_ops)); 1347 } 1348 1349 static int 1350 qfifo_add(struct que_data *qfp, struct buf *bp) 1351 { 1352 1353 if (!qfp->q_tab.b_actf) 1354 qfp->q_tab.b_actf = bp; 1355 else 1356 qfp->q_tab.b_actl->av_forw = bp; 1357 qfp->q_tab.b_actl = bp; 1358 bp->av_forw = NULL; 1359 return (0); 1360 } 1361 1362 /* 1363 * One-Way-Scan Queue functions 1364 */ 1365 /* 1366 * Local Function Prototypes 1367 */ 1368 static int qsort_add(); 1369 static struct buf *qsort_del(); 1370 static void oneway_scan_binary(struct diskhd *dp, struct buf *bp); 1371 1372 struct que_objops qsort_ops = { 1373 que_init, 1374 que_free, 1375 qsort_add, 1376 qsort_del, 1377 0, 0 1378 }; 1379 1380 /* 1381 * Local static data 1382 */ 1383 struct que_obj * 1384 qsort_create() 1385 { 1386 return (que_create((struct que_objops *)&qsort_ops)); 1387 } 1388 1389 static int 1390 qsort_add(struct que_data *qfp, struct buf *bp) 1391 { 1392 qfp->q_cnt++; 1393 oneway_scan_binary(&qfp->q_tab, bp); 1394 return (0); 1395 } 1396 1397 1398 #define b_pasf b_forw 1399 #define b_pasl b_back 1400 static void 1401 oneway_scan_binary(struct diskhd *dp, struct buf *bp) 1402 { 1403 struct buf *ap; 1404 1405 ap = dp->b_actf; 1406 if (ap == NULL) { 1407 dp->b_actf = bp; 1408 bp->av_forw = NULL; 1409 return; 1410 } 1411 if (DBLK(bp) < DBLK(ap)) { 1412 ap = dp->b_pasf; 1413 if ((ap == NULL) || (DBLK(bp) < DBLK(ap))) { 1414 dp->b_pasf = bp; 1415 bp->av_forw = ap; 1416 return; 1417 } 1418 } 1419 while (ap->av_forw) { 1420 if (DBLK(bp) < DBLK(ap->av_forw)) 1421 break; 1422 ap = ap->av_forw; 1423 } 1424 bp->av_forw = ap->av_forw; 1425 ap->av_forw = bp; 1426 } 1427 1428 static struct buf * 1429 qsort_del(struct que_data *qfp) 1430 { 1431 struct buf *bp; 1432 1433 if (qfp->q_cnt == 0) { 1434 return (NULL); 1435 } 1436 qfp->q_cnt--; 1437 bp = qfp->q_tab.b_actf; 1438 qfp->q_tab.b_actf = bp->av_forw; 1439 bp->av_forw = 0; 1440 if (!qfp->q_tab.b_actf && qfp->q_tab.b_pasf) { 1441 qfp->q_tab.b_actf = qfp->q_tab.b_pasf; 1442 qfp->q_tab.b_pasf = NULL; 1443 } 1444 return (bp); 1445 } 1446 1447 /* 1448 * Tagged queueing 1449 */ 1450 /* 1451 * Local Function Prototypes 1452 */ 1453 1454 struct que_objops qtag_ops = { 1455 que_init, 1456 que_free, 1457 qsort_add, 1458 qsort_del, 1459 0, 0 1460 }; 1461 1462 /* 1463 * Local static data 1464 */ 1465 struct que_obj * 1466 qtag_create() 1467 { 1468 return (que_create((struct que_objops *)&qtag_ops)); 1469 } 1470