Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys - Add a B_ORDERED flag to communicate to drivers that an...
details: https://anonhg.NetBSD.org/src/rev/35938e75cfef
branches: trunk
changeset: 480856:35938e75cfef
user: thorpej <thorpej%NetBSD.org@localhost>
date: Fri Jan 21 23:20:51 2000 +0000
description:
- Add a B_ORDERED flag to communicate to drivers that an I/O request should
be issued/completed in order; that is, provide a barrier for I/O queues.
- Change the buffer driver queue links to a TAILQ, rather than using
a home-grown equivalent. Provide BUFQ_*() macros to manipulate buffer
queues; these deal with the barrier provided by B_ORDERED.
- Update disksort() accordingly, and provide 3 versions:
- disksort_cylinder(): historical disksort(), which keys on
b_cylinder (and b_blkno for the case when b_cylinder matches).
- disksort_blkno(): sorts only on b_blkno. Essentially the
same as disksort_cylinder(), but with fewer comparisons.
- disksort_tail(): requests are simply inserted into the queue
at the tail. This is provided as an option so that drivers
can simply have a pointer to the appropriate sort function.
Note that disksort() now pays attention to B_ORDERED.
diffstat:
sys/kern/subr_disk.c | 189 +++++++++++++++++++++++++++++++++++++++++---------
sys/sys/buf.h | 100 ++++++++++++++++++++++++--
2 files changed, 245 insertions(+), 44 deletions(-)
diffs (truncated from 407 to 300 lines):
diff -r 7195e28d4c49 -r 35938e75cfef sys/kern/subr_disk.c
--- a/sys/kern/subr_disk.c Fri Jan 21 23:12:33 2000 +0000
+++ b/sys/kern/subr_disk.c Fri Jan 21 23:20:51 2000 +0000
@@ -1,7 +1,7 @@
-/* $NetBSD: subr_disk.c,v 1.25 1999/02/22 16:00:01 drochner Exp $ */
+/* $NetBSD: subr_disk.c,v 1.26 2000/01/21 23:20:51 thorpej Exp $ */
/*-
- * Copyright (c) 1996, 1997 The NetBSD Foundation, Inc.
+ * Copyright (c) 1996, 1997, 1999, 2000 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
@@ -98,28 +98,40 @@
* Seek sort for disks. We depend on the driver which calls us using b_resid
* as the current cylinder number.
*
- * The argument ap structure holds a b_actf activity chain pointer on which we
- * keep two queues, sorted in ascending cylinder order. The first queue holds
- * those requests which are positioned after the current cylinder (in the first
- * request); the second holds requests which came in after their cylinder number
- * was passed. Thus we implement a one way scan, retracting after reaching the
- * end of the drive to the first request on the second queue, at which time it
- * becomes the first queue.
+ * The argument bufq is an I/O queue for the device, on which there are
+ * actually two queues, sorted in ascending cylinder order. The first
+ * queue holds those requests which are positioned after the current
+ * cylinder (in the first request); the second holds requests which came
+ * in after their cylinder number was passed. Thus we implement a one-way
+ * scan, retracting after reaching the end of the drive to the first request
+ * on the second queue, at which time it becomes the first queue.
*
* A one-way scan is natural because of the way UNIX read-ahead blocks are
* allocated.
+ *
+ * This is further adjusted by any `barriers' which may exist in the queue.
+ * The bufq points to the last such ordered request.
*/
-
void
-disksort(ap, bp)
- register struct buf *ap, *bp;
+disksort_cylinder(bufq, bp)
+ struct buf_queue *bufq;
+ struct buf *bp;
{
- register struct buf *bq;
+ struct buf *bq, *nbq;
- /* If the queue is empty, then it's easy. */
- if (ap->b_actf == NULL) {
- bp->b_actf = NULL;
- ap->b_actf = bp;
+ /*
+ * If there are ordered requests on the queue, we must start
+ * the elevator sort after the last of these.
+ */
+ if ((bq = bufq->bq_barrier) == NULL)
+ bq = BUFQ_FIRST(bufq);
+
+ /*
+ * If the queue is empty, of if it's an ordered request,
+ * it's easy; we just go on the end.
+ */
+ if (bq == NULL || (bp->b_flags & B_ORDERED) != 0) {
+ BUFQ_INSERT_TAIL(bufq, bp);
return;
}
@@ -127,15 +139,14 @@
* If we lie after the first (currently active) request, then we
* must locate the second request list and add ourselves to it.
*/
- bq = ap->b_actf;
if (bp->b_cylinder < bq->b_cylinder) {
- while (bq->b_actf) {
+ while ((nbq = BUFQ_NEXT(bq)) != NULL) {
/*
* Check for an ``inversion'' in the normally ascending
* cylinder numbers, indicating the start of the second
* request list.
*/
- if (bq->b_actf->b_cylinder < bq->b_cylinder) {
+ if (nbq->b_cylinder < bq->b_cylinder) {
/*
* Search the second request list for the first
* request at a larger cylinder number. We go
@@ -143,18 +154,16 @@
* go at end.
*/
do {
- if (bp->b_cylinder <
- bq->b_actf->b_cylinder)
+ if (bp->b_cylinder < nbq->b_cylinder)
goto insert;
- if (bp->b_cylinder ==
- bq->b_actf->b_cylinder &&
- bp->b_blkno < bq->b_actf->b_blkno)
+ if (bp->b_cylinder == nbq->b_cylinder &&
+ bp->b_blkno < nbq->b_blkno)
goto insert;
- bq = bq->b_actf;
- } while (bq->b_actf);
+ bq = nbq;
+ } while ((nbq = BUFQ_NEXT(bq)) != NULL);
goto insert; /* after last */
}
- bq = bq->b_actf;
+ bq = BUFQ_NEXT(bq);
}
/*
* No inversions... we will go after the last, and
@@ -166,26 +175,134 @@
* Request is at/after the current request...
* sort in the first request list.
*/
- while (bq->b_actf) {
+ while ((nbq = BUFQ_NEXT(bq)) != NULL) {
/*
* We want to go after the current request if there is an
* inversion after it (i.e. it is the end of the first
* request list), or if the next request is a larger cylinder
* than our request.
*/
- if (bq->b_actf->b_cylinder < bq->b_cylinder ||
- bp->b_cylinder < bq->b_actf->b_cylinder ||
- (bp->b_cylinder == bq->b_actf->b_cylinder &&
- bp->b_blkno < bq->b_actf->b_blkno))
+ if (nbq->b_cylinder < bq->b_cylinder ||
+ bp->b_cylinder < nbq->b_cylinder ||
+ (bp->b_cylinder == nbq->b_cylinder &&
+ bp->b_blkno < nbq->b_blkno))
goto insert;
- bq = bq->b_actf;
+ bq = nbq;
}
/*
* Neither a second list nor a larger request... we go at the end of
* the first list, which is the same as the end of the whole schebang.
*/
-insert: bp->b_actf = bq->b_actf;
- bq->b_actf = bp;
+insert: BUFQ_INSERT_AFTER(bufq, bq, bp);
+}
+
+/*
+ * Seek sort for disks. This version sorts based on b_blkno, which
+ * indicates the block number.
+ *
+ * As before, there are actually two queues, sorted in ascendening block
+ * order. The first queue holds those requests which are positioned after
+ * the current block (in the first request); the second holds requests which
+ * came in after their block number was passed. Thus we implement a one-way
+ * scan, retracting after reaching the end of the driver to the first request
+ * on the second queue, at which time it becomes the first queue.
+ *
+ * A one-way scan is natural because of the way UNIX read-ahead blocks are
+ * allocated.
+ *
+ * This is further adjusted by any `barriers' which may exist in the queue.
+ * The bufq points to the last such ordered request.
+ */
+void
+disksort_blkno(bufq, bp)
+ struct buf_queue *bufq;
+ struct buf *bp;
+{
+ struct buf *bq, *nbq;
+
+ /*
+ * If there are ordered requests on the queue, we must start
+ * the elevator sort after the last of these.
+ */
+ if ((bq = bufq->bq_barrier) == NULL)
+ bq = BUFQ_FIRST(bufq);
+
+ /*
+ * If the queue is empty, or if it's an ordered request,
+ * it's easy; we just go on the end.
+ */
+ if (bq == NULL || (bp->b_flags & B_ORDERED) != 0) {
+ BUFQ_INSERT_TAIL(bufq, bp);
+ return;
+ }
+
+ /*
+ * If we lie after the first (currently active) request, then we
+ * must locate the second request list and add ourselves to it.
+ */
+ if (bp->b_blkno < bq->b_blkno) {
+ while ((nbq = BUFQ_NEXT(bq)) != NULL) {
+ /*
+ * Check for an ``inversion'' in the normally ascending
+ * block numbers, indicating the start of the second
+ * request list.
+ */
+ if (nbq->b_blkno < bq->b_blkno) {
+ /*
+ * Search the second request list for the first
+ * request at a larger block number. We go
+ * after that; if there is no such request, we
+ * go at the end.
+ */
+ do {
+ if (bp->b_blkno < nbq->b_blkno)
+ goto insert;
+ bq = nbq;
+ } while ((nbq = BUFQ_NEXT(bq)) != NULL);
+ goto insert; /* after last */
+ }
+ bq = BUFQ_NEXT(bq);
+ }
+ /*
+ * No inversions... we will go after the last, and
+ * be the first request in the second request list.
+ */
+ goto insert;
+ }
+ /*
+ * Request is at/after the current request...
+ * sort in the first request list.
+ */
+ while ((nbq = BUFQ_NEXT(bq)) != NULL) {
+ /*
+ * We want to go after the current request if there is an
+ * inversion after it (i.e. it is the end of the first
+ * request list), or if the next request is a larger cylinder
+ * than our request.
+ */
+ if (nbq->b_blkno < bq->b_blkno ||
+ bp->b_blkno < nbq->b_blkno)
+ goto insert;
+ bq = nbq;
+ }
+ /*
+ * Neither a second list nor a larger request... we go at the end of
+ * the first list, which is the same as the end of the whole schebang.
+ */
+insert: BUFQ_INSERT_AFTER(bufq, bq, bp);
+}
+
+/*
+ * Seek non-sort for disks. This version simply inserts requests at
+ * the tail of the queue.
+ */
+void
+disksort_tail(bufq, bp)
+ struct buf_queue *bufq;
+ struct buf *bp;
+{
+
+ BUFQ_INSERT_TAIL(bufq, bp);
}
/*
diff -r 7195e28d4c49 -r 35938e75cfef sys/sys/buf.h
--- a/sys/sys/buf.h Fri Jan 21 23:12:33 2000 +0000
+++ b/sys/sys/buf.h Fri Jan 21 23:20:51 2000 +0000
@@ -1,4 +1,41 @@
-/* $NetBSD: buf.h,v 1.35 1999/11/15 18:49:12 fvdl Exp $ */
+/* $NetBSD: buf.h,v 1.36 2000/01/21 23:20:51 thorpej Exp $ */
+
+/*-
+ * Copyright (c) 1999, 2000 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
+ * NASA Ames Research Center.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the NetBSD
+ * Foundation, Inc. and its contributors.
+ * 4. Neither the name of The NetBSD Foundation nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
/*
Home |
Main Index |
Thread Index |
Old Index