Home | History | Annotate | Line # | Download | only in raidframe
rf_sstf.c revision 1.1
      1  1.1  oster /*	$NetBSD: rf_sstf.c,v 1.1 1998/11/13 04:20:34 oster Exp $	*/
      2  1.1  oster /*
      3  1.1  oster  * Copyright (c) 1995 Carnegie-Mellon University.
      4  1.1  oster  * All rights reserved.
      5  1.1  oster  *
      6  1.1  oster  * Author: Jim Zelenka
      7  1.1  oster  *
      8  1.1  oster  * Permission to use, copy, modify and distribute this software and
      9  1.1  oster  * its documentation is hereby granted, provided that both the copyright
     10  1.1  oster  * notice and this permission notice appear in all copies of the
     11  1.1  oster  * software, derivative works or modified versions, and any portions
     12  1.1  oster  * thereof, and that both notices appear in supporting documentation.
     13  1.1  oster  *
     14  1.1  oster  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
     15  1.1  oster  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
     16  1.1  oster  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
     17  1.1  oster  *
     18  1.1  oster  * Carnegie Mellon requests users of this software to return to
     19  1.1  oster  *
     20  1.1  oster  *  Software Distribution Coordinator  or  Software.Distribution (at) CS.CMU.EDU
     21  1.1  oster  *  School of Computer Science
     22  1.1  oster  *  Carnegie Mellon University
     23  1.1  oster  *  Pittsburgh PA 15213-3890
     24  1.1  oster  *
     25  1.1  oster  * any improvements or extensions that they make and grant Carnegie the
     26  1.1  oster  * rights to redistribute these changes.
     27  1.1  oster  */
     28  1.1  oster 
     29  1.1  oster /*******************************************************************************
     30  1.1  oster  *
     31  1.1  oster  * sstf.c --  prioritized shortest seek time first disk queueing code
     32  1.1  oster  *
     33  1.1  oster  ******************************************************************************/
     34  1.1  oster 
     35  1.1  oster /*
     36  1.1  oster  * :
     37  1.1  oster  * Log: rf_sstf.c,v
     38  1.1  oster  * Revision 1.7  1996/06/19 14:09:56  jimz
     39  1.1  oster  * SstfPeek wasn't calling closest_to_arm() properly- would bogart
     40  1.1  oster  * low priority I/Os
     41  1.1  oster  *
     42  1.1  oster  * Revision 1.6  1996/06/18  20:53:11  jimz
     43  1.1  oster  * fix up disk queueing (remove configure routine,
     44  1.1  oster  * add shutdown list arg to create routines)
     45  1.1  oster  *
     46  1.1  oster  * Revision 1.5  1996/06/13  20:42:13  jimz
     47  1.1  oster  * add scan, cscan
     48  1.1  oster  *
     49  1.1  oster  * Revision 1.4  1996/06/07  22:26:27  jimz
     50  1.1  oster  * type-ify which_ru (RF_ReconUnitNum_t)
     51  1.1  oster  *
     52  1.1  oster  * Revision 1.3  1996/06/07  21:33:04  jimz
     53  1.1  oster  * begin using consistent types for sector numbers,
     54  1.1  oster  * stripe numbers, row+col numbers, recon unit numbers
     55  1.1  oster  *
     56  1.1  oster  * Revision 1.2  1996/06/06  01:11:35  jimz
     57  1.1  oster  * fixed many priority-related bugs
     58  1.1  oster  *
     59  1.1  oster  * Revision 1.1  1996/06/05  19:17:40  jimz
     60  1.1  oster  * Initial revision
     61  1.1  oster  *
     62  1.1  oster  */
     63  1.1  oster 
     64  1.1  oster #include "rf_alloclist.h"
     65  1.1  oster #include "rf_stripelocks.h"
     66  1.1  oster #include "rf_layout.h"
     67  1.1  oster #include "rf_diskqueue.h"
     68  1.1  oster #include "rf_sstf.h"
     69  1.1  oster #include "rf_debugMem.h"
     70  1.1  oster #include "rf_general.h"
     71  1.1  oster #include "rf_threadid.h"
     72  1.1  oster #include "rf_options.h"
     73  1.1  oster 
     74  1.1  oster #define DIR_LEFT   1
     75  1.1  oster #define DIR_RIGHT  2
     76  1.1  oster #define DIR_EITHER 3
     77  1.1  oster 
     78  1.1  oster #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
     79  1.1  oster 
     80  1.1  oster #define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen))
     81  1.1  oster 
     82  1.1  oster 
     83  1.1  oster static void do_sstf_ord_q(RF_DiskQueueData_t  **,
     84  1.1  oster 			  RF_DiskQueueData_t  **,
     85  1.1  oster 			  RF_DiskQueueData_t   *);
     86  1.1  oster 
     87  1.1  oster static RF_DiskQueueData_t *closest_to_arm(RF_SstfQ_t *,
     88  1.1  oster 					  RF_SectorNum_t,
     89  1.1  oster 					  int *,
     90  1.1  oster 					  int);
     91  1.1  oster static void do_dequeue(RF_SstfQ_t          *, RF_DiskQueueData_t  *);
     92  1.1  oster 
     93  1.1  oster 
     94  1.1  oster static void do_sstf_ord_q(queuep, tailp, req)
     95  1.1  oster   RF_DiskQueueData_t  **queuep;
     96  1.1  oster   RF_DiskQueueData_t  **tailp;
     97  1.1  oster   RF_DiskQueueData_t   *req;
     98  1.1  oster {
     99  1.1  oster 	RF_DiskQueueData_t *r, *s;
    100  1.1  oster 
    101  1.1  oster 	if (*queuep == NULL) {
    102  1.1  oster 		*queuep = req;
    103  1.1  oster 		*tailp = req;
    104  1.1  oster 		req->next = NULL;
    105  1.1  oster 		req->prev = NULL;
    106  1.1  oster 		return;
    107  1.1  oster 	}
    108  1.1  oster 	if (req->sectorOffset <= (*queuep)->sectorOffset) {
    109  1.1  oster 		req->next = *queuep;
    110  1.1  oster 		req->prev = NULL;
    111  1.1  oster 		(*queuep)->prev = req;
    112  1.1  oster 		*queuep = req;
    113  1.1  oster 		return;
    114  1.1  oster 	}
    115  1.1  oster 	if (req->sectorOffset > (*tailp)->sectorOffset) {
    116  1.1  oster 		/* optimization */
    117  1.1  oster 		r = NULL;
    118  1.1  oster 		s = *tailp;
    119  1.1  oster 		goto q_at_end;
    120  1.1  oster 	}
    121  1.1  oster 	for(s=NULL,r=*queuep;r;s=r,r=r->next) {
    122  1.1  oster 		if (r->sectorOffset >= req->sectorOffset) {
    123  1.1  oster 			/* insert after s, before r */
    124  1.1  oster 			RF_ASSERT(s);
    125  1.1  oster 			req->next = r;
    126  1.1  oster 			r->prev = req;
    127  1.1  oster 			s->next = req;
    128  1.1  oster 			req->prev = s;
    129  1.1  oster 			return;
    130  1.1  oster 		}
    131  1.1  oster 	}
    132  1.1  oster q_at_end:
    133  1.1  oster 	/* insert after s, at end of queue */
    134  1.1  oster 	RF_ASSERT(r == NULL);
    135  1.1  oster 	RF_ASSERT(s);
    136  1.1  oster 	RF_ASSERT(s == (*tailp));
    137  1.1  oster 	req->next = NULL;
    138  1.1  oster 	req->prev = s;
    139  1.1  oster 	s->next = req;
    140  1.1  oster 	*tailp = req;
    141  1.1  oster }
    142  1.1  oster 
    143  1.1  oster /* for removing from head-of-queue */
    144  1.1  oster #define DO_HEAD_DEQ(_r_,_q_) { \
    145  1.1  oster 	_r_ = (_q_)->queue; \
    146  1.1  oster 	RF_ASSERT((_r_) != NULL); \
    147  1.1  oster 	(_q_)->queue = (_r_)->next; \
    148  1.1  oster 	(_q_)->qlen--; \
    149  1.1  oster 	if ((_q_)->qlen == 0) { \
    150  1.1  oster 		RF_ASSERT((_r_) == (_q_)->qtail); \
    151  1.1  oster 		RF_ASSERT((_q_)->queue == NULL); \
    152  1.1  oster 		(_q_)->qtail = NULL; \
    153  1.1  oster 	} \
    154  1.1  oster 	else { \
    155  1.1  oster 		RF_ASSERT((_q_)->queue->prev == (_r_)); \
    156  1.1  oster 		(_q_)->queue->prev = NULL; \
    157  1.1  oster 	} \
    158  1.1  oster }
    159  1.1  oster 
    160  1.1  oster /* for removing from end-of-queue */
    161  1.1  oster #define DO_TAIL_DEQ(_r_,_q_) { \
    162  1.1  oster 	_r_ = (_q_)->qtail; \
    163  1.1  oster 	RF_ASSERT((_r_) != NULL); \
    164  1.1  oster 	(_q_)->qtail = (_r_)->prev; \
    165  1.1  oster 	(_q_)->qlen--; \
    166  1.1  oster 	if ((_q_)->qlen == 0) { \
    167  1.1  oster 		RF_ASSERT((_r_) == (_q_)->queue); \
    168  1.1  oster 		RF_ASSERT((_q_)->qtail == NULL); \
    169  1.1  oster 		(_q_)->queue = NULL; \
    170  1.1  oster 	} \
    171  1.1  oster 	else { \
    172  1.1  oster 		RF_ASSERT((_q_)->qtail->next == (_r_)); \
    173  1.1  oster 		(_q_)->qtail->next = NULL; \
    174  1.1  oster 	} \
    175  1.1  oster }
    176  1.1  oster 
    177  1.1  oster #define DO_BEST_DEQ(_l_,_r_,_q_) { \
    178  1.1  oster 	if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
    179  1.1  oster 		< SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
    180  1.1  oster 	{ \
    181  1.1  oster 		DO_HEAD_DEQ(_r_,_q_); \
    182  1.1  oster 	} \
    183  1.1  oster 	else { \
    184  1.1  oster 		DO_TAIL_DEQ(_r_,_q_); \
    185  1.1  oster 	} \
    186  1.1  oster }
    187  1.1  oster 
    188  1.1  oster static RF_DiskQueueData_t *closest_to_arm(queue, arm_pos, dir, allow_reverse)
    189  1.1  oster   RF_SstfQ_t      *queue;
    190  1.1  oster   RF_SectorNum_t   arm_pos;
    191  1.1  oster   int             *dir;
    192  1.1  oster   int              allow_reverse;
    193  1.1  oster {
    194  1.1  oster 	RF_SectorNum_t best_pos_l=0, this_pos_l=0, last_pos=0;
    195  1.1  oster 	RF_SectorNum_t best_pos_r=0, this_pos_r=0;
    196  1.1  oster 	RF_DiskQueueData_t *r, *best_l, *best_r;
    197  1.1  oster 
    198  1.1  oster 	best_r = best_l = NULL;
    199  1.1  oster 	for(r=queue->queue;r;r=r->next) {
    200  1.1  oster 		if (r->sectorOffset < arm_pos) {
    201  1.1  oster 			if (best_l == NULL) {
    202  1.1  oster 				best_l = r;
    203  1.1  oster 				last_pos = best_pos_l = this_pos_l;
    204  1.1  oster 			}
    205  1.1  oster 			else {
    206  1.1  oster 				this_pos_l = arm_pos - r->sectorOffset;
    207  1.1  oster 				if (this_pos_l < best_pos_l) {
    208  1.1  oster 					best_l = r;
    209  1.1  oster 					last_pos = best_pos_l = this_pos_l;
    210  1.1  oster 				}
    211  1.1  oster 				else {
    212  1.1  oster 					last_pos = this_pos_l;
    213  1.1  oster 				}
    214  1.1  oster 			}
    215  1.1  oster 		}
    216  1.1  oster 		else {
    217  1.1  oster 			if (best_r == NULL) {
    218  1.1  oster 				best_r = r;
    219  1.1  oster 				last_pos = best_pos_r = this_pos_r;
    220  1.1  oster 			}
    221  1.1  oster 			else {
    222  1.1  oster 				this_pos_r = r->sectorOffset - arm_pos;
    223  1.1  oster 				if (this_pos_r < best_pos_r) {
    224  1.1  oster 					best_r = r;
    225  1.1  oster 					last_pos = best_pos_r = this_pos_r;
    226  1.1  oster 				}
    227  1.1  oster 				else {
    228  1.1  oster 					last_pos = this_pos_r;
    229  1.1  oster 				}
    230  1.1  oster 				if (this_pos_r > last_pos) {
    231  1.1  oster 					/* getting farther away */
    232  1.1  oster 					break;
    233  1.1  oster 				}
    234  1.1  oster 			}
    235  1.1  oster 		}
    236  1.1  oster 	}
    237  1.1  oster 	if ((best_r == NULL) && (best_l == NULL))
    238  1.1  oster 		return(NULL);
    239  1.1  oster 	if ((*dir == DIR_RIGHT) && best_r)
    240  1.1  oster 		return(best_r);
    241  1.1  oster 	if ((*dir == DIR_LEFT) && best_l)
    242  1.1  oster 		return(best_l);
    243  1.1  oster 	if (*dir == DIR_EITHER) {
    244  1.1  oster 		if (best_l == NULL)
    245  1.1  oster 			return(best_r);
    246  1.1  oster 		if (best_r == NULL)
    247  1.1  oster 			return(best_l);
    248  1.1  oster 		if (best_pos_r < best_pos_l)
    249  1.1  oster 			return(best_r);
    250  1.1  oster 		else
    251  1.1  oster 			return(best_l);
    252  1.1  oster 	}
    253  1.1  oster 	/*
    254  1.1  oster 	 * Nothing in the direction we want to go. Reverse or
    255  1.1  oster 	 * reset the arm. We know we have an I/O in the other
    256  1.1  oster 	 * direction.
    257  1.1  oster 	 */
    258  1.1  oster 	if (allow_reverse) {
    259  1.1  oster 		if (*dir == DIR_RIGHT) {
    260  1.1  oster 			*dir = DIR_LEFT;
    261  1.1  oster 			return(best_l);
    262  1.1  oster 		}
    263  1.1  oster 		else {
    264  1.1  oster 			*dir = DIR_RIGHT;
    265  1.1  oster 			return(best_r);
    266  1.1  oster 		}
    267  1.1  oster 	}
    268  1.1  oster 	/*
    269  1.1  oster 	 * Reset (beginning of queue).
    270  1.1  oster 	 */
    271  1.1  oster 	RF_ASSERT(*dir == DIR_RIGHT);
    272  1.1  oster 	return(queue->queue);
    273  1.1  oster }
    274  1.1  oster 
    275  1.1  oster void *rf_SstfCreate(sect_per_disk, cl_list, listp)
    276  1.1  oster   RF_SectorCount_t      sect_per_disk;
    277  1.1  oster   RF_AllocListElem_t   *cl_list;
    278  1.1  oster   RF_ShutdownList_t   **listp;
    279  1.1  oster {
    280  1.1  oster 	RF_Sstf_t *sstfq;
    281  1.1  oster 
    282  1.1  oster 	RF_CallocAndAdd(sstfq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
    283  1.1  oster 	sstfq->dir = DIR_EITHER;
    284  1.1  oster 	sstfq->allow_reverse = 1;
    285  1.1  oster 	return((void *)sstfq);
    286  1.1  oster }
    287  1.1  oster 
    288  1.1  oster void *rf_ScanCreate(sect_per_disk, cl_list, listp)
    289  1.1  oster   RF_SectorCount_t      sect_per_disk;
    290  1.1  oster   RF_AllocListElem_t   *cl_list;
    291  1.1  oster   RF_ShutdownList_t   **listp;
    292  1.1  oster {
    293  1.1  oster 	RF_Sstf_t *scanq;
    294  1.1  oster 
    295  1.1  oster 	RF_CallocAndAdd(scanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
    296  1.1  oster 	scanq->dir = DIR_RIGHT;
    297  1.1  oster 	scanq->allow_reverse = 1;
    298  1.1  oster 	return((void *)scanq);
    299  1.1  oster }
    300  1.1  oster 
    301  1.1  oster void *rf_CscanCreate(sect_per_disk, cl_list, listp)
    302  1.1  oster   RF_SectorCount_t      sect_per_disk;
    303  1.1  oster   RF_AllocListElem_t   *cl_list;
    304  1.1  oster   RF_ShutdownList_t   **listp;
    305  1.1  oster {
    306  1.1  oster 	RF_Sstf_t *cscanq;
    307  1.1  oster 
    308  1.1  oster 	RF_CallocAndAdd(cscanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
    309  1.1  oster 	cscanq->dir = DIR_RIGHT;
    310  1.1  oster 	return((void *)cscanq);
    311  1.1  oster }
    312  1.1  oster 
    313  1.1  oster void rf_SstfEnqueue(qptr, req, priority)
    314  1.1  oster   void                *qptr;
    315  1.1  oster   RF_DiskQueueData_t  *req;
    316  1.1  oster   int                  priority;
    317  1.1  oster {
    318  1.1  oster 	RF_Sstf_t *sstfq;
    319  1.1  oster 
    320  1.1  oster 	sstfq = (RF_Sstf_t *)qptr;
    321  1.1  oster 
    322  1.1  oster 	if (priority == RF_IO_LOW_PRIORITY) {
    323  1.1  oster 		if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
    324  1.1  oster 			RF_DiskQueue_t *dq;
    325  1.1  oster 			int tid;
    326  1.1  oster 			rf_get_threadid(tid);
    327  1.1  oster 			dq = (RF_DiskQueue_t *)req->queue;
    328  1.1  oster 			printf("[%d] ENQ lopri %d,%d queues are %d,%d,%d\n",
    329  1.1  oster 				tid, dq->row, dq->col, sstfq->left.qlen, sstfq->right.qlen,
    330  1.1  oster 				sstfq->lopri.qlen);
    331  1.1  oster 		}
    332  1.1  oster 		do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
    333  1.1  oster 		sstfq->lopri.qlen++;
    334  1.1  oster 	}
    335  1.1  oster 	else {
    336  1.1  oster 		if (req->sectorOffset < sstfq->last_sector) {
    337  1.1  oster 			do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req);
    338  1.1  oster 			sstfq->left.qlen++;
    339  1.1  oster 		}
    340  1.1  oster 		else {
    341  1.1  oster 			do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req);
    342  1.1  oster 			sstfq->right.qlen++;
    343  1.1  oster 		}
    344  1.1  oster 	}
    345  1.1  oster }
    346  1.1  oster 
    347  1.1  oster static void do_dequeue(queue, req)
    348  1.1  oster   RF_SstfQ_t          *queue;
    349  1.1  oster   RF_DiskQueueData_t  *req;
    350  1.1  oster {
    351  1.1  oster 	RF_DiskQueueData_t  *req2;
    352  1.1  oster 
    353  1.1  oster 	if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
    354  1.1  oster 		int tid;
    355  1.1  oster 		rf_get_threadid(tid);
    356  1.1  oster 		printf("[%d] do_dequeue\n", tid);
    357  1.1  oster 	}
    358  1.1  oster 	if (req == queue->queue) {
    359  1.1  oster 		DO_HEAD_DEQ(req2,queue);
    360  1.1  oster 		RF_ASSERT(req2 == req);
    361  1.1  oster 	}
    362  1.1  oster 	else if (req == queue->qtail) {
    363  1.1  oster 		DO_TAIL_DEQ(req2,queue);
    364  1.1  oster 		RF_ASSERT(req2 == req);
    365  1.1  oster 	}
    366  1.1  oster 	else {
    367  1.1  oster 		/* dequeue from middle of list */
    368  1.1  oster 		RF_ASSERT(req->next);
    369  1.1  oster 		RF_ASSERT(req->prev);
    370  1.1  oster 		queue->qlen--;
    371  1.1  oster 		req->next->prev = req->prev;
    372  1.1  oster 		req->prev->next = req->next;
    373  1.1  oster 		req->next = req->prev = NULL;
    374  1.1  oster 	}
    375  1.1  oster }
    376  1.1  oster 
    377  1.1  oster RF_DiskQueueData_t *rf_SstfDequeue(qptr)
    378  1.1  oster   void  *qptr;
    379  1.1  oster {
    380  1.1  oster 	RF_DiskQueueData_t *req=NULL;
    381  1.1  oster 	RF_Sstf_t *sstfq;
    382  1.1  oster 
    383  1.1  oster 	sstfq = (RF_Sstf_t *)qptr;
    384  1.1  oster 
    385  1.1  oster 	if (rf_sstfDebug) {
    386  1.1  oster 		RF_DiskQueue_t *dq;
    387  1.1  oster 		int tid;
    388  1.1  oster 		rf_get_threadid(tid);
    389  1.1  oster 		dq = (RF_DiskQueue_t *)req->queue;
    390  1.1  oster 		RF_ASSERT(QSUM(sstfq)==dq->queueLength);
    391  1.1  oster 		printf("[%d] sstf: Dequeue %d,%d queues are %d,%d,%d\n", tid,
    392  1.1  oster 			dq->row, dq->col, sstfq->left.qlen, sstfq->right.qlen,
    393  1.1  oster 			sstfq->lopri.qlen);
    394  1.1  oster 	}
    395  1.1  oster 	if (sstfq->left.queue == NULL) {
    396  1.1  oster 		RF_ASSERT(sstfq->left.qlen == 0);
    397  1.1  oster 		if (sstfq->right.queue == NULL) {
    398  1.1  oster 			RF_ASSERT(sstfq->right.qlen == 0);
    399  1.1  oster 			if (sstfq->lopri.queue == NULL) {
    400  1.1  oster 				RF_ASSERT(sstfq->lopri.qlen == 0);
    401  1.1  oster 				return(NULL);
    402  1.1  oster 			}
    403  1.1  oster 			if (rf_sstfDebug) {
    404  1.1  oster 				int tid;
    405  1.1  oster 				rf_get_threadid(tid);
    406  1.1  oster 				printf("[%d] sstf: check for close lopri", tid);
    407  1.1  oster 			}
    408  1.1  oster 			req = closest_to_arm(&sstfq->lopri, sstfq->last_sector,
    409  1.1  oster 				&sstfq->dir, sstfq->allow_reverse);
    410  1.1  oster 			if (rf_sstfDebug) {
    411  1.1  oster 				int tid;
    412  1.1  oster 				rf_get_threadid(tid);
    413  1.1  oster 				printf("[%d] sstf: closest_to_arm said %lx", tid, (long)req);
    414  1.1  oster 			}
    415  1.1  oster 			if (req == NULL)
    416  1.1  oster 				return(NULL);
    417  1.1  oster 			do_dequeue(&sstfq->lopri, req);
    418  1.1  oster 		}
    419  1.1  oster 		else {
    420  1.1  oster 			DO_BEST_DEQ(sstfq->last_sector,req,&sstfq->right);
    421  1.1  oster 		}
    422  1.1  oster 	}
    423  1.1  oster 	else {
    424  1.1  oster 		if (sstfq->right.queue == NULL) {
    425  1.1  oster 			RF_ASSERT(sstfq->right.qlen == 0);
    426  1.1  oster 			DO_BEST_DEQ(sstfq->last_sector,req,&sstfq->left);
    427  1.1  oster 		}
    428  1.1  oster 		else {
    429  1.1  oster 			if (SNUM_DIFF(sstfq->last_sector,sstfq->right.queue->sectorOffset)
    430  1.1  oster 				< SNUM_DIFF(sstfq->last_sector,sstfq->left.qtail->sectorOffset))
    431  1.1  oster 			{
    432  1.1  oster 				DO_HEAD_DEQ(req,&sstfq->right);
    433  1.1  oster 			}
    434  1.1  oster 			else {
    435  1.1  oster 				DO_TAIL_DEQ(req,&sstfq->left);
    436  1.1  oster 			}
    437  1.1  oster 		}
    438  1.1  oster 	}
    439  1.1  oster 	RF_ASSERT(req);
    440  1.1  oster 	sstfq->last_sector = req->sectorOffset;
    441  1.1  oster 	return(req);
    442  1.1  oster }
    443  1.1  oster 
    444  1.1  oster RF_DiskQueueData_t *rf_ScanDequeue(qptr)
    445  1.1  oster   void  *qptr;
    446  1.1  oster {
    447  1.1  oster 	RF_DiskQueueData_t *req=NULL;
    448  1.1  oster 	RF_Sstf_t *scanq;
    449  1.1  oster 
    450  1.1  oster 	scanq = (RF_Sstf_t *)qptr;
    451  1.1  oster 
    452  1.1  oster 	if (rf_scanDebug) {
    453  1.1  oster 		RF_DiskQueue_t *dq;
    454  1.1  oster 		int tid;
    455  1.1  oster 		rf_get_threadid(tid);
    456  1.1  oster 		dq = (RF_DiskQueue_t *)req->queue;
    457  1.1  oster 		RF_ASSERT(QSUM(scanq)==dq->queueLength);
    458  1.1  oster 		printf("[%d] scan: Dequeue %d,%d queues are %d,%d,%d\n", tid,
    459  1.1  oster 			dq->row, dq->col, scanq->left.qlen, scanq->right.qlen,
    460  1.1  oster 			scanq->lopri.qlen);
    461  1.1  oster 	}
    462  1.1  oster 	if (scanq->left.queue == NULL) {
    463  1.1  oster 		RF_ASSERT(scanq->left.qlen == 0);
    464  1.1  oster 		if (scanq->right.queue == NULL) {
    465  1.1  oster 			RF_ASSERT(scanq->right.qlen == 0);
    466  1.1  oster 			if (scanq->lopri.queue == NULL) {
    467  1.1  oster 				RF_ASSERT(scanq->lopri.qlen == 0);
    468  1.1  oster 				return(NULL);
    469  1.1  oster 			}
    470  1.1  oster 			req = closest_to_arm(&scanq->lopri, scanq->last_sector,
    471  1.1  oster 				&scanq->dir, scanq->allow_reverse);
    472  1.1  oster 			if (req == NULL)
    473  1.1  oster 				return(NULL);
    474  1.1  oster 			do_dequeue(&scanq->lopri, req);
    475  1.1  oster 		}
    476  1.1  oster 		else {
    477  1.1  oster 			scanq->dir = DIR_RIGHT;
    478  1.1  oster 			DO_HEAD_DEQ(req,&scanq->right);
    479  1.1  oster 		}
    480  1.1  oster 	}
    481  1.1  oster 	else if (scanq->right.queue == NULL) {
    482  1.1  oster 		RF_ASSERT(scanq->right.qlen == 0);
    483  1.1  oster 		RF_ASSERT(scanq->left.queue);
    484  1.1  oster 		scanq->dir = DIR_LEFT;
    485  1.1  oster 		DO_TAIL_DEQ(req,&scanq->left);
    486  1.1  oster 	}
    487  1.1  oster 	else {
    488  1.1  oster 		RF_ASSERT(scanq->right.queue);
    489  1.1  oster 		RF_ASSERT(scanq->left.queue);
    490  1.1  oster 		if (scanq->dir == DIR_RIGHT) {
    491  1.1  oster 			DO_HEAD_DEQ(req,&scanq->right);
    492  1.1  oster 		}
    493  1.1  oster 		else {
    494  1.1  oster 			DO_TAIL_DEQ(req,&scanq->left);
    495  1.1  oster 		}
    496  1.1  oster 	}
    497  1.1  oster 	RF_ASSERT(req);
    498  1.1  oster 	scanq->last_sector = req->sectorOffset;
    499  1.1  oster 	return(req);
    500  1.1  oster }
    501  1.1  oster 
    502  1.1  oster RF_DiskQueueData_t *rf_CscanDequeue(qptr)
    503  1.1  oster   void  *qptr;
    504  1.1  oster {
    505  1.1  oster 	RF_DiskQueueData_t *req=NULL;
    506  1.1  oster 	RF_Sstf_t *cscanq;
    507  1.1  oster 
    508  1.1  oster 	cscanq = (RF_Sstf_t *)qptr;
    509  1.1  oster 
    510  1.1  oster 	RF_ASSERT(cscanq->dir == DIR_RIGHT);
    511  1.1  oster 	if (rf_cscanDebug) {
    512  1.1  oster 		RF_DiskQueue_t *dq;
    513  1.1  oster 		int tid;
    514  1.1  oster 		rf_get_threadid(tid);
    515  1.1  oster 		dq = (RF_DiskQueue_t *)req->queue;
    516  1.1  oster 		RF_ASSERT(QSUM(cscanq)==dq->queueLength);
    517  1.1  oster 		printf("[%d] scan: Dequeue %d,%d queues are %d,%d,%d\n", tid,
    518  1.1  oster 			dq->row, dq->col, cscanq->left.qlen, cscanq->right.qlen,
    519  1.1  oster 			cscanq->lopri.qlen);
    520  1.1  oster 	}
    521  1.1  oster 	if (cscanq->right.queue) {
    522  1.1  oster 		DO_HEAD_DEQ(req,&cscanq->right);
    523  1.1  oster 	}
    524  1.1  oster 	else {
    525  1.1  oster 		RF_ASSERT(cscanq->right.qlen == 0);
    526  1.1  oster 		if (cscanq->left.queue == NULL) {
    527  1.1  oster 			RF_ASSERT(cscanq->left.qlen == 0);
    528  1.1  oster 			if (cscanq->lopri.queue == NULL) {
    529  1.1  oster 				RF_ASSERT(cscanq->lopri.qlen == 0);
    530  1.1  oster 				return(NULL);
    531  1.1  oster 			}
    532  1.1  oster 			req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
    533  1.1  oster 				&cscanq->dir, cscanq->allow_reverse);
    534  1.1  oster 			if (req == NULL)
    535  1.1  oster 				return(NULL);
    536  1.1  oster 			do_dequeue(&cscanq->lopri, req);
    537  1.1  oster 		}
    538  1.1  oster 		else {
    539  1.1  oster 			/*
    540  1.1  oster 			 * There's I/Os to the left of the arm. Swing
    541  1.1  oster 			 * on back (swap queues).
    542  1.1  oster 			 */
    543  1.1  oster 			cscanq->right = cscanq->left;
    544  1.1  oster 			cscanq->left.qlen = 0;
    545  1.1  oster 			cscanq->left.queue = cscanq->left.qtail = NULL;
    546  1.1  oster 			DO_HEAD_DEQ(req,&cscanq->right);
    547  1.1  oster 		}
    548  1.1  oster 	}
    549  1.1  oster 	RF_ASSERT(req);
    550  1.1  oster 	cscanq->last_sector = req->sectorOffset;
    551  1.1  oster 	return(req);
    552  1.1  oster }
    553  1.1  oster 
    554  1.1  oster RF_DiskQueueData_t *rf_SstfPeek(qptr)
    555  1.1  oster   void  *qptr;
    556  1.1  oster {
    557  1.1  oster 	RF_DiskQueueData_t *req;
    558  1.1  oster 	RF_Sstf_t *sstfq;
    559  1.1  oster 
    560  1.1  oster 	sstfq = (RF_Sstf_t *)qptr;
    561  1.1  oster 
    562  1.1  oster 	if ((sstfq->left.queue == NULL) && (sstfq->right.queue == NULL)) {
    563  1.1  oster 		req = closest_to_arm(&sstfq->lopri, sstfq->last_sector, &sstfq->dir,
    564  1.1  oster 			sstfq->allow_reverse);
    565  1.1  oster 	}
    566  1.1  oster 	else {
    567  1.1  oster 		if (sstfq->left.queue == NULL)
    568  1.1  oster 			req = sstfq->right.queue;
    569  1.1  oster 		else {
    570  1.1  oster 			if (sstfq->right.queue == NULL)
    571  1.1  oster 				req = sstfq->left.queue;
    572  1.1  oster 			else {
    573  1.1  oster 				if (SNUM_DIFF(sstfq->last_sector,sstfq->right.queue->sectorOffset)
    574  1.1  oster 					<SNUM_DIFF(sstfq->last_sector,sstfq->left.qtail->sectorOffset))
    575  1.1  oster 				{
    576  1.1  oster 					req = sstfq->right.queue;
    577  1.1  oster 				}
    578  1.1  oster 				else {
    579  1.1  oster 					req = sstfq->left.qtail;
    580  1.1  oster 				}
    581  1.1  oster 			}
    582  1.1  oster 		}
    583  1.1  oster 	}
    584  1.1  oster 	if (req == NULL) {
    585  1.1  oster 		RF_ASSERT(QSUM(sstfq) == 0);
    586  1.1  oster 	}
    587  1.1  oster 	return(req);
    588  1.1  oster }
    589  1.1  oster 
    590  1.1  oster RF_DiskQueueData_t *rf_ScanPeek(qptr)
    591  1.1  oster   void  *qptr;
    592  1.1  oster {
    593  1.1  oster 	RF_DiskQueueData_t *req;
    594  1.1  oster 	RF_Sstf_t *scanq;
    595  1.1  oster 	int dir;
    596  1.1  oster 
    597  1.1  oster 	scanq = (RF_Sstf_t *)qptr;
    598  1.1  oster 	dir = scanq->dir;
    599  1.1  oster 
    600  1.1  oster 	if (scanq->left.queue == NULL) {
    601  1.1  oster 		RF_ASSERT(scanq->left.qlen == 0);
    602  1.1  oster 		if (scanq->right.queue == NULL) {
    603  1.1  oster 			RF_ASSERT(scanq->right.qlen == 0);
    604  1.1  oster 			if (scanq->lopri.queue == NULL) {
    605  1.1  oster 				RF_ASSERT(scanq->lopri.qlen == 0);
    606  1.1  oster 				return(NULL);
    607  1.1  oster 			}
    608  1.1  oster 			req = closest_to_arm(&scanq->lopri, scanq->last_sector,
    609  1.1  oster 				&dir, scanq->allow_reverse);
    610  1.1  oster 		}
    611  1.1  oster 		else {
    612  1.1  oster 			req = scanq->right.queue;
    613  1.1  oster 		}
    614  1.1  oster 	}
    615  1.1  oster 	else if (scanq->right.queue == NULL) {
    616  1.1  oster 		RF_ASSERT(scanq->right.qlen == 0);
    617  1.1  oster 		RF_ASSERT(scanq->left.queue);
    618  1.1  oster 		req = scanq->left.qtail;
    619  1.1  oster 	}
    620  1.1  oster 	else {
    621  1.1  oster 		RF_ASSERT(scanq->right.queue);
    622  1.1  oster 		RF_ASSERT(scanq->left.queue);
    623  1.1  oster 		if (scanq->dir == DIR_RIGHT) {
    624  1.1  oster 			req = scanq->right.queue;
    625  1.1  oster 		}
    626  1.1  oster 		else {
    627  1.1  oster 			req = scanq->left.qtail;
    628  1.1  oster 		}
    629  1.1  oster 	}
    630  1.1  oster 	if (req == NULL) {
    631  1.1  oster 		RF_ASSERT(QSUM(scanq) == 0);
    632  1.1  oster 	}
    633  1.1  oster 	return(req);
    634  1.1  oster }
    635  1.1  oster 
    636  1.1  oster RF_DiskQueueData_t *rf_CscanPeek(qptr)
    637  1.1  oster   void  *qptr;
    638  1.1  oster {
    639  1.1  oster 	RF_DiskQueueData_t *req;
    640  1.1  oster 	RF_Sstf_t *cscanq;
    641  1.1  oster 
    642  1.1  oster 	cscanq = (RF_Sstf_t *)qptr;
    643  1.1  oster 
    644  1.1  oster 	RF_ASSERT(cscanq->dir == DIR_RIGHT);
    645  1.1  oster 	if (cscanq->right.queue) {
    646  1.1  oster 		req = cscanq->right.queue;
    647  1.1  oster 	}
    648  1.1  oster 	else {
    649  1.1  oster 		RF_ASSERT(cscanq->right.qlen == 0);
    650  1.1  oster 		if (cscanq->left.queue == NULL) {
    651  1.1  oster 			RF_ASSERT(cscanq->left.qlen == 0);
    652  1.1  oster 			if (cscanq->lopri.queue == NULL) {
    653  1.1  oster 				RF_ASSERT(cscanq->lopri.qlen == 0);
    654  1.1  oster 				return(NULL);
    655  1.1  oster 			}
    656  1.1  oster 			req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
    657  1.1  oster 				&cscanq->dir, cscanq->allow_reverse);
    658  1.1  oster 		}
    659  1.1  oster 		else {
    660  1.1  oster 			/*
    661  1.1  oster 			 * There's I/Os to the left of the arm. We'll end
    662  1.1  oster 			 * up swinging on back.
    663  1.1  oster 			 */
    664  1.1  oster 			req = cscanq->left.queue;
    665  1.1  oster 		}
    666  1.1  oster 	}
    667  1.1  oster 	if (req == NULL) {
    668  1.1  oster 		RF_ASSERT(QSUM(cscanq) == 0);
    669  1.1  oster 	}
    670  1.1  oster 	return(req);
    671  1.1  oster }
    672  1.1  oster 
    673  1.1  oster int rf_SstfPromote(qptr, parityStripeID, which_ru)
    674  1.1  oster   void               *qptr;
    675  1.1  oster   RF_StripeNum_t      parityStripeID;
    676  1.1  oster   RF_ReconUnitNum_t   which_ru;
    677  1.1  oster {
    678  1.1  oster 	RF_DiskQueueData_t *r, *next;
    679  1.1  oster 	RF_Sstf_t *sstfq;
    680  1.1  oster 	int n;
    681  1.1  oster 
    682  1.1  oster 	sstfq = (RF_Sstf_t *)qptr;
    683  1.1  oster 
    684  1.1  oster 	n = 0;
    685  1.1  oster 	if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
    686  1.1  oster 		int tid;
    687  1.1  oster 		rf_get_threadid(tid);
    688  1.1  oster 		printf("[%d] promote %ld %d  queues are %d,%d,%d\n",
    689  1.1  oster 		       tid, (long)parityStripeID, (int)which_ru,
    690  1.1  oster 		       sstfq->left.qlen,
    691  1.1  oster 		       sstfq->right.qlen,
    692  1.1  oster 		       sstfq->lopri.qlen);
    693  1.1  oster 	}
    694  1.1  oster 	for(r=sstfq->lopri.queue;r;r=next) {
    695  1.1  oster 		next = r->next;
    696  1.1  oster 		if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
    697  1.1  oster 			int tid;
    698  1.1  oster 			rf_get_threadid(tid);
    699  1.1  oster 			printf("[%d] check promote %lx\n", tid, (long)r);
    700  1.1  oster 		}
    701  1.1  oster 		if ((r->parityStripeID == parityStripeID)
    702  1.1  oster 			&& (r->which_ru == which_ru))
    703  1.1  oster 		{
    704  1.1  oster 			do_dequeue(&sstfq->lopri, r);
    705  1.1  oster 			rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY);
    706  1.1  oster 			n++;
    707  1.1  oster 		}
    708  1.1  oster 	}
    709  1.1  oster 	if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
    710  1.1  oster 		int tid;
    711  1.1  oster 		rf_get_threadid(tid);
    712  1.1  oster 		printf("[%d] promoted %d matching I/Os queues are %d,%d,%d\n",
    713  1.1  oster 			tid, n, sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen);
    714  1.1  oster 	}
    715  1.1  oster 	return(n);
    716  1.1  oster }
    717