rf_diskqueue.c

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

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Mark Holland
 *
 * 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.
 */

/****************************************************************************************
 *
 * rf_diskqueue.c -- higher-level disk queue code
 *
 * the routines here are a generic wrapper around the actual queueing
 * routines.  The code here implements thread scheduling, synchronization, 
 * and locking ops (see below) on top of the lower-level queueing code.
 *
 * to support atomic RMW, we implement "locking operations".  When a locking op
 * is dispatched to the lower levels of the driver, the queue is locked, and no further
 * I/Os are dispatched until the queue receives & completes a corresponding "unlocking
 * operation".  This code relies on the higher layers to guarantee that a locking
 * op will always be eventually followed by an unlocking op.  The model is that
 * the higher layers are structured so locking and unlocking ops occur in pairs, i.e.
 * an unlocking op cannot be generated until after a locking op reports completion.
 * There is no good way to check to see that an unlocking op "corresponds" to the
 * op that currently has the queue locked, so we make no such attempt.  Since by
 * definition there can be only one locking op outstanding on a disk, this should
 * not be a problem.
 *
 * In the kernel, we allow multiple I/Os to be concurrently dispatched to the disk
 * driver.  In order to support locking ops in this environment, when we decide to
 * do a locking op, we stop dispatching new I/Os and wait until all dispatched I/Os
 * have completed before dispatching the locking op.
 *
 * Unfortunately, the code is different in the 3 different operating states
 * (user level, kernel, simulator).  In the kernel, I/O is non-blocking, and
 * we have no disk threads to dispatch for us.  Therefore, we have to dispatch
 * new I/Os to the scsi driver at the time of enqueue, and also at the time 
 * of completion.  At user level, I/O is blocking, and so only the disk threads 
 * may dispatch I/Os.  Thus at user level, all we can do at enqueue time is 
 * enqueue and wake up the disk thread to do the dispatch.
 *
 ***************************************************************************************/

/*
 * $Locker:  $
 *
 * $Log: rf_diskqueue.c,v $
 * Revision 1.50  1996/08/07  21:08:38  jimz
 * b_proc -> kb_proc
 *
 * Revision 1.49  1996/07/05  20:36:14  jimz
 * make rf_ConfigureDiskQueueSystem return 0
 *
 * Revision 1.48  1996/06/18  20:53:11  jimz
 * fix up disk queueing (remove configure routine,
 * add shutdown list arg to create routines)
 *
 * Revision 1.47  1996/06/14  14:16:36  jimz
 * fix handling of bogus queue type
 *
 * Revision 1.46  1996/06/13  20:41:44  jimz
 * add scan, cscan, random queueing
 *
 * Revision 1.45  1996/06/11  01:27:50  jimz
 * Fixed bug where diskthread shutdown would crash or hang. This
 * turned out to be two distinct bugs:
 * (1) [crash] The thread shutdown code wasn't properly waiting for
 * all the diskthreads to complete. This caused diskthreads that were
 * exiting+cleaning up to unlock a destroyed mutex.
 * (2) [hang] TerminateDiskQueues wasn't locking, and DiskIODequeue
 * only checked for termination _after_ a wakeup if the queues were
 * empty. This was a race where the termination wakeup could be lost
 * by the dequeueing thread, and the system would hang waiting for the
 * thread to exit, while the thread waited for an I/O or a signal to
 * check the termination flag.
 *
 * Revision 1.44  1996/06/10  11:55:47  jimz
 * Straightened out some per-array/not-per-array distinctions, fixed
 * a couple bugs related to confusion. Added shutdown lists. Removed
 * layout shutdown function (now subsumed by shutdown lists).
 *
 * Revision 1.43  1996/06/09  02:36:46  jimz
 * lots of little crufty cleanup- fixup whitespace
 * issues, comment #ifdefs, improve typing in some
 * places (esp size-related)
 *
 * Revision 1.42  1996/06/07  22:26:27  jimz
 * type-ify which_ru (RF_ReconUnitNum_t)
 *
 * Revision 1.41  1996/06/07  21:33:04  jimz
 * begin using consistent types for sector numbers,
 * stripe numbers, row+col numbers, recon unit numbers
 *
 * Revision 1.40  1996/06/06  17:28:04  jimz
 * track sector number of last I/O dequeued
 *
 * Revision 1.39  1996/06/06  01:14:13  jimz
 * fix crashing bug when tracerec is NULL (ie, from copyback)
 * initialize req->queue
 *
 * Revision 1.38  1996/06/05  19:38:32  jimz
 * fixed up disk queueing types config
 * added sstf disk queueing
 * fixed exit bug on diskthreads (ref-ing bad mem)
 *
 * Revision 1.37  1996/06/05  18:06:02  jimz
 * Major code cleanup. The Great Renaming is now done.
 * Better modularity. Better typing. Fixed a bunch of
 * synchronization bugs. Made a lot of global stuff
 * per-desc or per-array. Removed dead code.
 *
 * Revision 1.36  1996/05/30  23:22:16  jimz
 * bugfixes of serialization, timing problems
 * more cleanup
 *
 * Revision 1.35  1996/05/30  12:59:18  jimz
 * make etimer happier, more portable
 *
 * Revision 1.34  1996/05/30  11:29:41  jimz
 * Numerous bug fixes. Stripe lock release code disagreed with the taking code
 * about when stripes should be locked (I made it consistent: no parity, no lock)
 * There was a lot of extra serialization of I/Os which I've removed- a lot of
 * it was to calculate values for the cache code, which is no longer with us.
 * More types, function, macro cleanup. Added code to properly quiesce the array
 * on shutdown. Made a lot of stuff array-specific which was (bogusly) general
 * before. Fixed memory allocation, freeing bugs.
 *
 * Revision 1.33  1996/05/27  18:56:37  jimz
 * more code cleanup
 * better typing
 * compiles in all 3 environments
 *
 * Revision 1.32  1996/05/24  22:17:04  jimz
 * continue code + namespace cleanup
 * typed a bunch of flags
 *
 * Revision 1.31  1996/05/24  01:59:45  jimz
 * another checkpoint in code cleanup for release
 * time to sync kernel tree
 *
 * Revision 1.30  1996/05/23  21:46:35  jimz
 * checkpoint in code cleanup (release prep)
 * lots of types, function names have been fixed
 *
 * Revision 1.29  1996/05/23  00:33:23  jimz
 * code cleanup: move all debug decls to rf_options.c, all extern
 * debug decls to rf_options.h, all debug vars preceded by rf_
 *
 * Revision 1.28  1996/05/20  16:14:29  jimz
 * switch to rf_{mutex,cond}_{init,destroy}
 *
 * Revision 1.27  1996/05/18  19:51:34  jimz
 * major code cleanup- fix syntax, make some types consistent,
 * add prototypes, clean out dead code, et cetera
 *
 * Revision 1.26  1996/05/16  19:21:49  wvcii
 * fixed typo in init_dqd
 *
 * Revision 1.25  1996/05/16  16:02:51  jimz
 * switch to RF_FREELIST stuff for DiskQueueData
 *
 * Revision 1.24  1996/05/10  16:24:14  jimz
 * new cvscan function names
 *
 * Revision 1.23  1996/05/01  16:27:54  jimz
 * don't use ccmn bp management
 *
 * Revision 1.22  1995/12/12  18:10:06  jimz
 * MIN -> RF_MIN, MAX -> RF_MAX, ASSERT -> RF_ASSERT
 * fix 80-column brain damage in comments
 *
 * Revision 1.21  1995/12/01  15:59:59  root
 * added copyright info
 *
 * Revision 1.20  1995/11/07  16:27:20  wvcii
 * added Peek() function to diskqueuesw
 * non-locking accesses are never blocked (assume clients enforce proper
 * respect for lock acquisition)
 *
 * Revision 1.19  1995/10/05  18:56:52  jimz
 * fix req handling in IOComplete
 *
 * Revision 1.18  1995/10/04  20:13:50  wvcii
 * added asserts to monitor numOutstanding queueLength
 *
 * Revision 1.17  1995/10/04  07:43:52  wvcii
 * queue->numOutstanding now valid for user & sim
 * added queue->queueLength
 * user tested & verified, sim untested
 *
 * Revision 1.16  1995/09/12  00:21:19  wvcii
 * added support for tracing disk queue time
 *
 */

#include "rf_types.h"
#include "rf_threadstuff.h"
#include "rf_threadid.h"
#include "rf_raid.h"
#include "rf_diskqueue.h"
#include "rf_alloclist.h"
#include "rf_acctrace.h"
#include "rf_etimer.h"
#include "rf_configure.h"
#include "rf_general.h"
#include "rf_freelist.h"
#include "rf_debugprint.h"
#include "rf_shutdown.h"
#include "rf_cvscan.h"
#include "rf_sstf.h"
#include "rf_fifo.h"

#ifdef SIMULATE
#include "rf_diskevent.h"
#endif /* SIMULATE */

extern struct buf *ubc_bufget();

#define Dprintf1(s,a)         if (rf_queueDebug) rf_debug_printf(s,(void *)((unsigned long)a),NULL,NULL,NULL,NULL,NULL,NULL,NULL)
#define Dprintf2(s,a,b)       if (rf_queueDebug) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),NULL,NULL,NULL,NULL,NULL,NULL)
#define Dprintf3(s,a,b,c)     if (rf_queueDebug) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),NULL,NULL,NULL,NULL,NULL)
#define Dprintf4(s,a,b,c,d)   if (rf_queueDebug) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),NULL,NULL,NULL,NULL)
#define Dprintf5(s,a,b,c,d,e) if (rf_queueDebug) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),NULL,NULL,NULL)

#if !defined(KERNEL) && !defined(SIMULATE)

/* queue must be locked before invoking this */
#define SIGNAL_DISK_QUEUE(_q_,_wh_)  \
{                                    \
  if ( (_q_)->numWaiting > 0) {      \
    (_q_)->numWaiting--;             \
    RF_SIGNAL_COND( ((_q_)->cond) );    \
  }                                  \
}

/* queue must be locked before invoking this */
#define WAIT_DISK_QUEUE(_q_,_wh_)                                         \
{                                                                         \
  (_q_)->numWaiting++;                                                    \
  RF_WAIT_COND( ((_q_)->cond), ((_q_)->mutex) );                             \
}

#else /* !defined(KERNEL) && !defined(SIMULATE) */

#define SIGNAL_DISK_QUEUE(_q_,_wh_)
#define WAIT_DISK_QUEUE(_q_,_wh_)

#endif /* !defined(KERNEL) && !defined(SIMULATE) */

/*****************************************************************************************
 *
 * the disk queue switch defines all the functions used in the different queueing
 * disciplines
 *    queue ID, init routine, enqueue routine, dequeue routine
 *
 ****************************************************************************************/

static RF_DiskQueueSW_t diskqueuesw[] = {
	{"fifo", /* FIFO */
	rf_FifoCreate,
	rf_FifoEnqueue,
	rf_FifoDequeue,
	rf_FifoPeek,
	rf_FifoPromote},

	{"cvscan", /* cvscan */
	rf_CvscanCreate,
	rf_CvscanEnqueue,
	rf_CvscanDequeue,
	rf_CvscanPeek,
	rf_CvscanPromote },

	{"sstf", /* shortest seek time first */
	rf_SstfCreate,
	rf_SstfEnqueue,
	rf_SstfDequeue,
	rf_SstfPeek,