From 048a0d3b5b2334dcd3e02980c07a901a476c9504 Mon Sep 17 00:00:00 2001 From: gibbs Date: Tue, 15 Sep 1998 08:55:03 +0000 Subject: When a buffer is removed from a buffer queue, remember it's block number and use it as "the currently active" buffer in doing disk sort calculations. --- sys/kern/subr_disklabel.c | 78 ++++++++++++++++++++++++++++++---------------- sys/sys/bio.h | 37 +++++++++++++--------- sys/sys/buf.h | 37 +++++++++++++--------- sys/ufs/ufs/ufs_disksubr.c | 78 ++++++++++++++++++++++++++++++---------------- 4 files changed, 148 insertions(+), 82 deletions(-) diff --git a/sys/kern/subr_disklabel.c b/sys/kern/subr_disklabel.c index de42e86..99dc708 100644 --- a/sys/kern/subr_disklabel.c +++ b/sys/kern/subr_disklabel.c @@ -36,7 +36,7 @@ * SUCH DAMAGE. * * @(#)ufs_disksubr.c 8.5 (Berkeley) 1/21/94 - * $Id: ufs_disksubr.c,v 1.34 1998/02/20 13:37:40 bde Exp $ + * $Id: ufs_disksubr.c,v 1.35 1998/07/28 18:25:51 bde Exp $ */ #include @@ -69,7 +69,9 @@ bufqdisksort(bufq, bp) { struct buf *bq; struct buf *bn; + struct buf *be; + be = TAILQ_LAST(&bufq->queue, buf_queue); /* * If the queue is empty or we are an * ordered transaction, then it's easy. @@ -86,38 +88,62 @@ bufqdisksort(bufq, bp) * we can only insert after the insert * point. */ - bq = TAILQ_NEXT(bufq->insert_point, b_act); - if (bq == NULL) { - bufq_insert_tail(bufq, bp); - return; - } - } - - /* - * If we lie before the first (currently active) request, then we - * must add ourselves to the second request list. - */ - if (bp->b_pblkno < bq->b_pblkno) { + bq = bufq->insert_point; + } else { - bq = bufq->switch_point; /* - * If we are starting a new secondary list, then it's easy. + * If we lie before the last removed (currently active) + * request, and are not inserting ourselves into the + * "locked" portion of the list, then we must add ourselves + * to the second request list. */ - if (bq == NULL) { - bufq->switch_point = bp; - bufq_insert_tail(bufq, bp); - return; - } - if (bp->b_pblkno < bq->b_pblkno) { - bufq->switch_point = bp; - TAILQ_INSERT_BEFORE(bq, bp, b_act); - return; + if (bp->b_pblkno < bufq->last_pblkno) { + + bq = bufq->switch_point; + /* + * If we are starting a new secondary list, + * then it's easy. + */ + if (bq == NULL) { + bufq->switch_point = bp; + bufq_insert_tail(bufq, bp); + return; + } + /* + * If we lie ahead of the current switch point, + * insert us before the switch point and move + * the switch point. + */ + if (bp->b_pblkno < bq->b_pblkno) { + bufq->switch_point = bp; + TAILQ_INSERT_BEFORE(bq, bp, b_act); + return; + } + } else { + if (bufq->switch_point != NULL) + be = TAILQ_PREV(bufq->switch_point, + buf_queue, b_act); + /* + * If we lie between last_pblkno and bq, + * insert before bq. + */ + if (bp->b_pblkno < bq->b_pblkno) { + TAILQ_INSERT_BEFORE(bq, bp, b_act); + return; + } } } + /* - * Request is at/after the current request... - * sort in the first request list. + * Request is at/after our current position in the list. + * Optimize for sequential I/O by seeing if we go at the tail. */ + if (bp->b_pblkno > be->b_pblkno) { + TAILQ_INSERT_AFTER(&bufq->queue, be, bp, b_act); + return; + } + + /* Otherwise, insertion sort */ while ((bn = TAILQ_NEXT(bq, b_act)) != NULL) { /* diff --git a/sys/sys/bio.h b/sys/sys/bio.h index 26ce956..ad4aa3b 100644 --- a/sys/sys/bio.h +++ b/sys/sys/bio.h @@ -36,7 +36,7 @@ * SUCH DAMAGE. * * @(#)buf.h 8.9 (Berkeley) 3/30/95 - * $Id: buf.h,v 1.54 1998/08/24 17:47:08 phk Exp $ + * $Id: buf.h,v 1.55 1998/09/05 14:13:12 phk Exp $ */ #ifndef _SYS_BUF_H_ @@ -170,32 +170,34 @@ struct buf { #define NOOFFSET (-1LL) /* No buffer offset calculated yet */ -typedef struct buf_queue_head { +struct buf_queue_head { TAILQ_HEAD(buf_queue, buf) queue; + daddr_t last_pblkno; struct buf *insert_point; struct buf *switch_point; -} buf_queue_head, *buf_queue_head_t; - -static __inline void bufq_init __P((buf_queue_head *head)); +}; -static __inline void bufq_insert_tail __P((buf_queue_head *head, - struct buf *bp)); +static __inline void bufq_init __P((struct buf_queue_head *head)); -static __inline void bufq_remove __P((buf_queue_head *head, +static __inline void bufq_insert_tail __P((struct buf_queue_head *head, struct buf *bp)); -static __inline struct buf *bufq_first __P((buf_queue_head *head)); +static __inline void bufq_remove __P((struct buf_queue_head *head, + struct buf *bp)); + +static __inline struct buf *bufq_first __P((struct buf_queue_head *head)); static __inline void -bufq_init(buf_queue_head *head) +bufq_init(struct buf_queue_head *head) { TAILQ_INIT(&head->queue); + head->last_pblkno = 0; head->insert_point = NULL; head->switch_point = NULL; } static __inline void -bufq_insert_tail(buf_queue_head *head, struct buf *bp) +bufq_insert_tail(struct buf_queue_head *head, struct buf *bp) { if ((bp->b_flags & B_ORDERED) != 0) { head->insert_point = bp; @@ -205,19 +207,24 @@ bufq_insert_tail(buf_queue_head *head, struct buf *bp) } static __inline void -bufq_remove(buf_queue_head *head, struct buf *bp) +bufq_remove(struct buf_queue_head *head, struct buf *bp) { - if (bp == head->insert_point) - head->insert_point = TAILQ_PREV(bp, buf_queue, b_act); if (bp == head->switch_point) head->switch_point = TAILQ_NEXT(bp, b_act); + if (bp == head->insert_point) { + head->insert_point = TAILQ_PREV(bp, buf_queue, b_act); + if (head->insert_point == NULL) + head->last_pblkno = 0; + } else if (bp == TAILQ_FIRST(&head->queue)) { + head->last_pblkno = bp->b_pblkno; + } TAILQ_REMOVE(&head->queue, bp, b_act); if (TAILQ_FIRST(&head->queue) == head->switch_point) head->switch_point = NULL; } static __inline struct buf * -bufq_first(buf_queue_head *head) +bufq_first(struct buf_queue_head *head) { return (TAILQ_FIRST(&head->queue)); } diff --git a/sys/sys/buf.h b/sys/sys/buf.h index 26ce956..ad4aa3b 100644 --- a/sys/sys/buf.h +++ b/sys/sys/buf.h @@ -36,7 +36,7 @@ * SUCH DAMAGE. * * @(#)buf.h 8.9 (Berkeley) 3/30/95 - * $Id: buf.h,v 1.54 1998/08/24 17:47:08 phk Exp $ + * $Id: buf.h,v 1.55 1998/09/05 14:13:12 phk Exp $ */ #ifndef _SYS_BUF_H_ @@ -170,32 +170,34 @@ struct buf { #define NOOFFSET (-1LL) /* No buffer offset calculated yet */ -typedef struct buf_queue_head { +struct buf_queue_head { TAILQ_HEAD(buf_queue, buf) queue; + daddr_t last_pblkno; struct buf *insert_point; struct buf *switch_point; -} buf_queue_head, *buf_queue_head_t; - -static __inline void bufq_init __P((buf_queue_head *head)); +}; -static __inline void bufq_insert_tail __P((buf_queue_head *head, - struct buf *bp)); +static __inline void bufq_init __P((struct buf_queue_head *head)); -static __inline void bufq_remove __P((buf_queue_head *head, +static __inline void bufq_insert_tail __P((struct buf_queue_head *head, struct buf *bp)); -static __inline struct buf *bufq_first __P((buf_queue_head *head)); +static __inline void bufq_remove __P((struct buf_queue_head *head, + struct buf *bp)); + +static __inline struct buf *bufq_first __P((struct buf_queue_head *head)); static __inline void -bufq_init(buf_queue_head *head) +bufq_init(struct buf_queue_head *head) { TAILQ_INIT(&head->queue); + head->last_pblkno = 0; head->insert_point = NULL; head->switch_point = NULL; } static __inline void -bufq_insert_tail(buf_queue_head *head, struct buf *bp) +bufq_insert_tail(struct buf_queue_head *head, struct buf *bp) { if ((bp->b_flags & B_ORDERED) != 0) { head->insert_point = bp; @@ -205,19 +207,24 @@ bufq_insert_tail(buf_queue_head *head, struct buf *bp) } static __inline void -bufq_remove(buf_queue_head *head, struct buf *bp) +bufq_remove(struct buf_queue_head *head, struct buf *bp) { - if (bp == head->insert_point) - head->insert_point = TAILQ_PREV(bp, buf_queue, b_act); if (bp == head->switch_point) head->switch_point = TAILQ_NEXT(bp, b_act); + if (bp == head->insert_point) { + head->insert_point = TAILQ_PREV(bp, buf_queue, b_act); + if (head->insert_point == NULL) + head->last_pblkno = 0; + } else if (bp == TAILQ_FIRST(&head->queue)) { + head->last_pblkno = bp->b_pblkno; + } TAILQ_REMOVE(&head->queue, bp, b_act); if (TAILQ_FIRST(&head->queue) == head->switch_point) head->switch_point = NULL; } static __inline struct buf * -bufq_first(buf_queue_head *head) +bufq_first(struct buf_queue_head *head) { return (TAILQ_FIRST(&head->queue)); } diff --git a/sys/ufs/ufs/ufs_disksubr.c b/sys/ufs/ufs/ufs_disksubr.c index de42e86..99dc708 100644 --- a/sys/ufs/ufs/ufs_disksubr.c +++ b/sys/ufs/ufs/ufs_disksubr.c @@ -36,7 +36,7 @@ * SUCH DAMAGE. * * @(#)ufs_disksubr.c 8.5 (Berkeley) 1/21/94 - * $Id: ufs_disksubr.c,v 1.34 1998/02/20 13:37:40 bde Exp $ + * $Id: ufs_disksubr.c,v 1.35 1998/07/28 18:25:51 bde Exp $ */ #include @@ -69,7 +69,9 @@ bufqdisksort(bufq, bp) { struct buf *bq; struct buf *bn; + struct buf *be; + be = TAILQ_LAST(&bufq->queue, buf_queue); /* * If the queue is empty or we are an * ordered transaction, then it's easy. @@ -86,38 +88,62 @@ bufqdisksort(bufq, bp) * we can only insert after the insert * point. */ - bq = TAILQ_NEXT(bufq->insert_point, b_act); - if (bq == NULL) { - bufq_insert_tail(bufq, bp); - return; - } - } - - /* - * If we lie before the first (currently active) request, then we - * must add ourselves to the second request list. - */ - if (bp->b_pblkno < bq->b_pblkno) { + bq = bufq->insert_point; + } else { - bq = bufq->switch_point; /* - * If we are starting a new secondary list, then it's easy. + * If we lie before the last removed (currently active) + * request, and are not inserting ourselves into the + * "locked" portion of the list, then we must add ourselves + * to the second request list. */ - if (bq == NULL) { - bufq->switch_point = bp; - bufq_insert_tail(bufq, bp); - return; - } - if (bp->b_pblkno < bq->b_pblkno) { - bufq->switch_point = bp; - TAILQ_INSERT_BEFORE(bq, bp, b_act); - return; + if (bp->b_pblkno < bufq->last_pblkno) { + + bq = bufq->switch_point; + /* + * If we are starting a new secondary list, + * then it's easy. + */ + if (bq == NULL) { + bufq->switch_point = bp; + bufq_insert_tail(bufq, bp); + return; + } + /* + * If we lie ahead of the current switch point, + * insert us before the switch point and move + * the switch point. + */ + if (bp->b_pblkno < bq->b_pblkno) { + bufq->switch_point = bp; + TAILQ_INSERT_BEFORE(bq, bp, b_act); + return; + } + } else { + if (bufq->switch_point != NULL) + be = TAILQ_PREV(bufq->switch_point, + buf_queue, b_act); + /* + * If we lie between last_pblkno and bq, + * insert before bq. + */ + if (bp->b_pblkno < bq->b_pblkno) { + TAILQ_INSERT_BEFORE(bq, bp, b_act); + return; + } } } + /* - * Request is at/after the current request... - * sort in the first request list. + * Request is at/after our current position in the list. + * Optimize for sequential I/O by seeing if we go at the tail. */ + if (bp->b_pblkno > be->b_pblkno) { + TAILQ_INSERT_AFTER(&bufq->queue, be, bp, b_act); + return; + } + + /* Otherwise, insertion sort */ while ((bn = TAILQ_NEXT(bq, b_act)) != NULL) { /* -- cgit v1.1