/*-
* Copyright (c) 1996, 1997, 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.
*
* 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.
*/
/*
* Copyright (c) 1982, 1986, 1988, 1993
* The Regents of the University of California. All rights reserved.
* (c) UNIX System Laboratories, Inc.
* All or some portions of this file are derived from material licensed
* to the University of California by American Telephone and Telegraph
* Co. or Unix System Laboratories, Inc. and are reproduced herein with
* the permission of UNIX System Laboratories, Inc.
*
* 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
*
* @(#)ufs_disksubr.c 8.5 (Berkeley) 1/21/94
*/
/*
* Seek sort for disks.
*
* There are two queues. The first queue holds read requests; the second
* holds write requests. The read queue is first-come first-served; the
* write queue is sorted in ascendening block order.
* The read queue is processed first. After PRIO_READ_BURST consecutive
* read requests with non-empty write queue PRIO_WRITE_REQ requests from
* the write queue will be processed.
*/
struct bufq_prio {
TAILQ_HEAD(, buf) bq_read, bq_write; /* actual list of buffers */
struct buf *bq_write_next; /* next request in bq_write */
struct buf *bq_next; /* current request */
int bq_read_burst; /* # of consecutive reads */
};
/*
* If it's a read request append it to the list.
*/
if ((bp->b_flags & B_READ) == B_READ) {
TAILQ_INSERT_TAIL(&prio->bq_read, bp, b_actq);
return;
}
bq = TAILQ_FIRST(&prio->bq_write);
/*
* If the write list is empty, simply append it to the list.
*/
if (bq == NULL) {
TAILQ_INSERT_TAIL(&prio->bq_write, bp, b_actq);
prio->bq_write_next = bp;
return;
}
/*
* If we lie after the next request, insert after this request.
*/
if (buf_inorder(prio->bq_write_next, bp, sortby))
bq = prio->bq_write_next;
/*
* Search for the first request at a larger block number.
* We go before this request if it exists.
*/
while (bq != NULL && buf_inorder(bq, bp, sortby))
bq = TAILQ_NEXT(bq, b_actq);
/*
* If no current request, get next from the lists.
*/
if (prio->bq_next == NULL) {
/*
* If at least one list is empty, select the other.
*/
if (TAILQ_FIRST(&prio->bq_read) == NULL) {
prio->bq_next = prio->bq_write_next;
prio->bq_read_burst = 0;
} else if (prio->bq_write_next == NULL) {
bp = prio->bq_next = TAILQ_FIRST(&prio->bq_read);
prio->bq_read_burst = 0;
KASSERT((bp == NULL) ||
((bp->b_flags & B_READ) == B_READ));
} else {
/*
* Both list have requests. Select the read list up
* to PRIO_READ_BURST times, then select the write
* list PRIO_WRITE_REQ times.
*/
if (prio->bq_read_burst++ < PRIO_READ_BURST)
prio->bq_next = TAILQ_FIRST(&prio->bq_read);
else if (prio->bq_read_burst <
PRIO_READ_BURST + PRIO_WRITE_REQ)
prio->bq_next = prio->bq_write_next;
else {
prio->bq_next = TAILQ_FIRST(&prio->bq_read);
prio->bq_read_burst = 0;
}
}
}
bp = prio->bq_next;
if (bp != NULL && remove) {
if ((bp->b_flags & B_READ) == B_READ)
TAILQ_REMOVE(&prio->bq_read, bp, b_actq);
else {
/*
* Advance the write pointer before removing
* bp since it is actually prio->bq_write_next.
*/
prio->bq_write_next =
TAILQ_NEXT(prio->bq_write_next, b_actq);
TAILQ_REMOVE(&prio->bq_write, bp, b_actq);
if (prio->bq_write_next == NULL)
prio->bq_write_next =
TAILQ_FIRST(&prio->bq_write);
}
