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