rf_sstf.c

RAIDFrame是个非常好的磁盘阵列RAID仿真工具

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Jim Zelenka
 *
 * Permission to use, copy, modify and distribute this software and
 * its documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 *
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 *
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  [e-mail]
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie the
 * rights to redistribute these changes.
 */

/*******************************************************************************
 *
 * sstf.c --  prioritized shortest seek time first disk queueing code
 *
 ******************************************************************************/

/*
 * $Locker:  $
 * $Log: rf_sstf.c,v $
 * Revision 1.7  1996/06/19  14:09:56  jimz
 * SstfPeek wasn't calling closest_to_arm() properly- would bogart
 * low priority I/Os
 *
 * Revision 1.6  1996/06/18  20:53:11  jimz
 * fix up disk queueing (remove configure routine,
 * add shutdown list arg to create routines)
 *
 * Revision 1.5  1996/06/13  20:42:13  jimz
 * add scan, cscan
 *
 * Revision 1.4  1996/06/07  22:26:27  jimz
 * type-ify which_ru (RF_ReconUnitNum_t)
 *
 * Revision 1.3  1996/06/07  21:33:04  jimz
 * begin using consistent types for sector numbers,
 * stripe numbers, row+col numbers, recon unit numbers
 *
 * Revision 1.2  1996/06/06  01:11:35  jimz
 * fixed many priority-related bugs
 *
 * Revision 1.1  1996/06/05  19:17:40  jimz
 * Initial revision
 *
 */

#include "rf_alloclist.h"
#include "rf_stripelocks.h"
#include "rf_layout.h"
#include "rf_diskqueue.h"
#include "rf_sstf.h"
#include "rf_debugMem.h"
#include "rf_general.h"
#include "rf_threadid.h"
#include "rf_options.h"

#define DIR_LEFT   1
#define DIR_RIGHT  2
#define DIR_EITHER 3

#define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))

#define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen))

static void do_sstf_ord_q(queuep, tailp, req)
  RF_DiskQueueData_t  **queuep;
  RF_DiskQueueData_t  **tailp;
  RF_DiskQueueData_t   *req;
{
	RF_DiskQueueData_t *r, *s;

	if (*queuep == NULL) {
		*queuep = req;
		*tailp = req;
		req->next = NULL;
		req->prev = NULL;
		return;
	}
	if (req->sectorOffset <= (*queuep)->sectorOffset) {
		req->next = *queuep;
		req->prev = NULL;
		(*queuep)->prev = req;
		*queuep = req;
		return;
	}
	if (req->sectorOffset > (*tailp)->sectorOffset) {
		/* optimization */
		r = NULL;
		s = *tailp;
		goto q_at_end;
	}
	for(s=NULL,r=*queuep;r;s=r,r=r->next) {
		if (r->sectorOffset >= req->sectorOffset) {
			/* insert after s, before r */
			RF_ASSERT(s);
			req->next = r;
			r->prev = req;
			s->next = req;
			req->prev = s;
			return;
		}
	}
q_at_end:
	/* insert after s, at end of queue */
	RF_ASSERT(r == NULL);
	RF_ASSERT(s);
	RF_ASSERT(s == (*tailp));
	req->next = NULL;
	req->prev = s;
	s->next = req;
	*tailp = req;
}

/* for removing from head-of-queue */
#define DO_HEAD_DEQ(_r_,_q_) { \
	_r_ = (_q_)->queue; \
	RF_ASSERT((_r_) != NULL); \
	(_q_)->queue = (_r_)->next; \
	(_q_)->qlen--; \
	if ((_q_)->qlen == 0) { \
		RF_ASSERT((_r_) == (_q_)->qtail); \
		RF_ASSERT((_q_)->queue == NULL); \
		(_q_)->qtail = NULL; \
	} \
	else { \
		RF_ASSERT((_q_)->queue->prev == (_r_)); \
		(_q_)->queue->prev = NULL; \
	} \
}

/* for removing from end-of-queue */
#define DO_TAIL_DEQ(_r_,_q_) { \
	_r_ = (_q_)->qtail; \
	RF_ASSERT((_r_) != NULL); \
	(_q_)->qtail = (_r_)->prev; \
	(_q_)->qlen--; \
	if ((_q_)->qlen == 0) { \
		RF_ASSERT((_r_) == (_q_)->queue); \
		RF_ASSERT((_q_)->qtail == NULL); \
		(_q_)->queue = NULL; \
	} \
	else { \
		RF_ASSERT((_q_)->qtail->next == (_r_)); \
		(_q_)->qtail->next = NULL; \
	} \
}

#define DO_BEST_DEQ(_l_,_r_,_q_) { \
	if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
		< SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
	{ \
		DO_HEAD_DEQ(_r_,_q_); \
	} \
	else { \
		DO_TAIL_DEQ(_r_,_q_); \
	} \
}

static RF_DiskQueueData_t *closest_to_arm(queue, arm_pos, dir, allow_reverse)
  RF_SstfQ_t      *queue;
  RF_SectorNum_t   arm_pos;
  int             *dir;
  int              allow_reverse;
{
	RF_SectorNum_t best_pos_l, this_pos_l, last_pos;
	RF_SectorNum_t best_pos_r, this_pos_r;
	RF_DiskQueueData_t *r, *best_l, *best_r;

	best_r = best_l = NULL;
	for(r=queue->queue;r;r=r->next) {
		if (r->sectorOffset < arm_pos) {
			if (best_l == NULL) {
				best_l = r;
				last_pos = best_pos_l = this_pos_l;
			}
			else {
				this_pos_l = arm_pos - r->sectorOffset;
				if (this_pos_l < best_pos_l) {
					best_l = r;
					last_pos = best_pos_l = this_pos_l;
				}
				else {
					last_pos = this_pos_l;
				}
			}
		}
		else {
			if (best_r == NULL) {
				best_r = r;
				last_pos = best_pos_r = this_pos_r;
			}
			else {
				this_pos_r = r->sectorOffset - arm_pos;
				if (this_pos_r < best_pos_r) {
					best_r = r;
					last_pos = best_pos_r = this_pos_r;
				}
				else {
					last_pos = this_pos_r;
				}
				if (this_pos_r > last_pos) {
					/* getting farther away */
					break;
				}
			}
		}
	}
	if ((best_r == NULL) && (best_l == NULL))
		return(NULL);
	if ((*dir == DIR_RIGHT) && best_r)
		return(best_r);
	if ((*dir == DIR_LEFT) && best_l)
		return(best_l);
	if (*dir == DIR_EITHER) {
		if (best_l == NULL)
			return(best_r);
		if (best_r == NULL)
			return(best_l);
		if (best_pos_r < best_pos_l)
			return(best_r);
		else
			return(best_l);
	}
	/*
	 * Nothing in the direction we want to go. Reverse or
	 * reset the arm. We know we have an I/O in the other
	 * direction.
	 */
	if (allow_reverse) {
		if (*dir == DIR_RIGHT) {
			*dir = DIR_LEFT;
			return(best_l);
		}
		else {
			*dir = DIR_RIGHT;
			return(best_r);
		}
	}
	/*
	 * Reset (beginning of queue).
	 */
	RF_ASSERT(*dir == DIR_RIGHT);
	return(queue->queue);
}

void *rf_SstfCreate(sect_per_disk, cl_list, listp)
  RF_SectorCount_t      sect_per_disk;
  RF_AllocListElem_t   *cl_list;
  RF_ShutdownList_t   **listp;
{
	RF_Sstf_t *sstfq;

	RF_CallocAndAdd(sstfq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
	sstfq->dir = DIR_EITHER;
	sstfq->allow_reverse = 1;
	return((void *)sstfq);
}

void *rf_ScanCreate(sect_per_disk, cl_list, listp)
  RF_SectorCount_t      sect_per_disk;
  RF_AllocListElem_t   *cl_list;
  RF_ShutdownList_t   **listp;
{
	RF_Sstf_t *scanq;

	RF_CallocAndAdd(scanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
	scanq->dir = DIR_RIGHT;
	scanq->allow_reverse = 1;
	return((void *)scanq);
}

void *rf_CscanCreate(sect_per_disk, cl_list, listp)
  RF_SectorCount_t      sect_per_disk;
  RF_AllocListElem_t   *cl_list;
  RF_ShutdownList_t   **listp;
{
	RF_Sstf_t *cscanq;

	RF_CallocAndAdd(cscanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
	cscanq->dir = DIR_RIGHT;
	return((void *)cscanq);
}

void rf_SstfEnqueue(qptr, req, priority)
  void                *qptr;
  RF_DiskQueueData_t  *req;
  int                  priority;
{
	RF_Sstf_t *sstfq;

	sstfq = (RF_Sstf_t *)qptr;

	if (priority == RF_IO_LOW_PRIORITY) {
		if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
			RF_DiskQueue_t *dq;
			int tid;
			rf_get_threadid(tid);
			dq = (RF_DiskQueue_t *)req->queue;
			printf("[%d] ENQ lopri %d,%d queues are %d,%d,%d\n",
				tid, dq->row, dq->col, sstfq->left.qlen, sstfq->right.qlen,
				sstfq->lopri.qlen);
		}
		do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
		sstfq->lopri.qlen++;
	}
	else {
		if (req->sectorOffset < sstfq->last_sector) {
			do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req);
			sstfq->left.qlen++;
		}
		else {
			do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req);
			sstfq->right.qlen++;
		}
	}
}

static void do_dequeue(queue, req)
  RF_SstfQ_t          *queue;
  RF_DiskQueueData_t  *req;
{
	RF_DiskQueueData_t  *req2;

	if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
		int tid;
		rf_get_threadid(tid);
		printf("[%d] do_dequeue\n", tid);
	}
	if (req == queue->queue) {
		DO_HEAD_DEQ(req2,queue);
		RF_ASSERT(req2 == req);
	}
	else if (req == queue->qtail) {
		DO_TAIL_DEQ(req2,queue);
		RF_ASSERT(req2 == req);