rf_evenodd.c

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

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Chang-Ming Wu
 *
 * 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_evenodd.c -- implements EVENODD array architecture
 *
 ****************************************************************************************/

#include "rf_archs.h"

#if RF_INCLUDE_EVENODD > 0

#include "rf_types.h"
#include "rf_raid.h"
#include "rf_dag.h"
#include "rf_dagffrd.h"
#include "rf_dagffwr.h"
#include "rf_dagdegrd.h"
#include "rf_dagdegwr.h"
#include "rf_dagutils.h"
#include "rf_dagfuncs.h"
#include "rf_threadid.h"
#include "rf_etimer.h"
#include "rf_general.h"
#include "rf_evenodd.h"
#include "rf_configure.h"
#include "rf_parityscan.h"
#include "rf_utils.h"
#include "rf_map.h"
#include "rf_pq.h"
#include "rf_mcpair.h"
#include "rf_sys.h"
#include "rf_evenodd.h"
#include "rf_evenodd_dagfuncs.h"
#include "rf_evenodd_dags.h"

typedef struct RF_EvenOddConfigInfo_s {
  RF_RowCol_t **stripeIdentifier;                    /* filled in at config time & used by IdentifyStripe */
} RF_EvenOddConfigInfo_t;

rf_ConfigureEvenOdd(listp, raidPtr, cfgPtr)
  RF_ShutdownList_t  **listp;
  RF_Raid_t           *raidPtr;
  RF_Config_t         *cfgPtr;
{
  RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
  RF_EvenOddConfigInfo_t *info;
  RF_RowCol_t i, j, startdisk;
  
  RF_MallocAndAdd(info, sizeof(RF_EvenOddConfigInfo_t), (RF_EvenOddConfigInfo_t *), raidPtr->cleanupList);
  layoutPtr->layoutSpecificInfo = (void *) info;

  RF_ASSERT(raidPtr->numRow == 1);

  info->stripeIdentifier = rf_make_2d_array(raidPtr->numCol, raidPtr->numCol, raidPtr->cleanupList);
  startdisk = 0;
  for (i=0; i<raidPtr->numCol; i++) {
    for (j=0; j<raidPtr->numCol; j++) {
      info->stripeIdentifier[i][j] = (startdisk + j) % raidPtr->numCol;
    }
    if ((startdisk -= 2) < 0) startdisk += raidPtr->numCol; 
  }

  /* fill in the remaining layout parameters */
  layoutPtr->numStripe = layoutPtr->stripeUnitsPerDisk;
  layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit << raidPtr->logBytesPerSector;
  layoutPtr->numDataCol = raidPtr->numCol-2; /*  ORIG: layoutPtr->numDataCol = raidPtr->numCol-1;  */
#if RF_EO_MATRIX_DIM > 17
  if (raidPtr->numCol <= 17){
      printf("Number of stripe units in a parity stripe is smaller than 17. Please\n");
      printf("define the macro RF_EO_MATRIX_DIM in file rf_evenodd_dagfuncs.h to \n");
      printf("be 17 to increase performance. \n");
      return(EINVAL); 
  }
#elif RF_EO_MATRIX_DIM == 17
  if (raidPtr->numCol > 17) {
      printf("Number of stripe units in a parity stripe is bigger than 17. Please\n");
      printf("define the macro RF_EO_MATRIX_DIM in file rf_evenodd_dagfuncs.h to \n");
      printf("be 257 for encoding and decoding functions to work. \n");
      return(EINVAL);
  }
#endif
  layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit;
  layoutPtr->numParityCol = 2;
  layoutPtr->dataStripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk;
  raidPtr->sectorsPerDisk = layoutPtr->stripeUnitsPerDisk * layoutPtr->sectorsPerStripeUnit;

  raidPtr->totalSectors = layoutPtr->stripeUnitsPerDisk * layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit;

  return(0);
}

int rf_GetDefaultNumFloatingReconBuffersEvenOdd(RF_Raid_t *raidPtr)
{
  return(20);
}

RF_HeadSepLimit_t rf_GetDefaultHeadSepLimitEvenOdd(RF_Raid_t *raidPtr)
{
  return(10);
}

void rf_IdentifyStripeEvenOdd(
  RF_Raid_t        *raidPtr,
  RF_RaidAddr_t     addr,
  RF_RowCol_t     **diskids,
  RF_RowCol_t      *outRow)
{
  RF_StripeNum_t stripeID = rf_RaidAddressToStripeID(&raidPtr->Layout, addr);
  RF_EvenOddConfigInfo_t *info = (RF_EvenOddConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo;

  *outRow = 0;
  *diskids = info->stripeIdentifier[ stripeID % raidPtr->numCol ];
}

/* The layout of stripe unit on the disks are:      c0 c1 c2 c3 c4  

 						     0  1  2  E  P
						     5  E  P  3  4
						     P  6  7  8  E
	 					    10 11  E  P  9
						     E  P 12 13 14
						     ....

  We use the MapSectorRAID5 to map data information because the routine can be shown to map exactly 
  the layout of data stripe unit as shown above although we have 2 redundant information now.
  But for E and P, we use rf_MapEEvenOdd and rf_MapParityEvenOdd which are different method from raid-5.
*/


void rf_MapParityEvenOdd(
	RF_Raid_t 	*raidPtr, 
	RF_RaidAddr_t 	 raidSector, 
	RF_RowCol_t 	*row,   
	RF_RowCol_t 	*col, 
	RF_SectorNum_t  *diskSector,  
	int  	  	 remap)
{
  RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit;
  RF_StripeNum_t endSUIDofthisStrip = (SUID/raidPtr->Layout.numDataCol + 1)*raidPtr->Layout.numDataCol - 1;

  *row = 0;        
  *col = ( endSUIDofthisStrip + 2)%raidPtr->numCol;
  *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit +
    (raidSector % raidPtr->Layout.sectorsPerStripeUnit);
}

void rf_MapEEvenOdd(
  RF_Raid_t       *raidPtr,
  RF_RaidAddr_t    raidSector,
  RF_RowCol_t     *row,
  RF_RowCol_t     *col,
  RF_SectorNum_t  *diskSector,
  int              remap)
{
  RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit;
  RF_StripeNum_t endSUIDofthisStrip = (SUID/raidPtr->Layout.numDataCol + 1)*raidPtr->Layout.numDataCol - 1;

  *row = 0;        
  *col = ( endSUIDofthisStrip + 1)%raidPtr->numCol;
  *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit +
    (raidSector % raidPtr->Layout.sectorsPerStripeUnit);
}

void rf_EODagSelect(
  RF_Raid_t             *raidPtr,
  RF_IoType_t            type,
  RF_AccessStripeMap_t  *asmap,
  RF_VoidFuncPtr        *createFunc)
{
  RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
  unsigned ndfail = asmap->numDataFailed;
  unsigned npfail = asmap->numParityFailed +asmap->numQFailed;
  unsigned ntfail = npfail + ndfail;

  RF_ASSERT(RF_IO_IS_R_OR_W(type));
  if (ntfail > 2) 
    {
      RF_ERRORMSG("more than two disks failed in a single group!  Aborting I/O operation.\n");
      /* *infoFunc = */ *createFunc = NULL;
      return;
    }

  /* ok, we can do this I/O */
  if (type == RF_IO_TYPE_READ)
    {
      switch (ndfail)
	{
	case 0:
	  /* fault free read */
	  *createFunc = rf_CreateFaultFreeReadDAG;   /* same as raid 5 */
	  break;
	case 1:
	  /* lost a single data unit */
	  /* two cases:
	        (1) parity is not lost.
		    do a normal raid 5 reconstruct read.
		(2) parity is lost.
		    do a reconstruct read using "e".
          */
	  if (ntfail == 2) /* also lost redundancy */
	    {
	      if (asmap->failedPDAtwo->type == RF_PDA_TYPE_PARITY) 
		*createFunc = rf_EO_110_CreateReadDAG; 
	      else
		*createFunc = rf_EO_101_CreateReadDAG; 
	    }
	  else
	    {
	      /* P and E are ok. But is there a failure
		 in some unaccessed data unit?
              */
	      if (rf_NumFailedDataUnitsInStripe(raidPtr,asmap)==2)
		*createFunc = rf_EO_200_CreateReadDAG; 
	      else
		  *createFunc = rf_EO_100_CreateReadDAG; 
	    }
	  break;
	case 2:
	  /* *createFunc = rf_EO_200_CreateReadDAG; */
	  *createFunc = NULL;
	  break;
	}
      return;
    }

  /* a write */
  switch (ntfail)
    {
    case 0: /* fault free */
      if (rf_suppressLocksAndLargeWrites ||
	  (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) && (layoutPtr->numDataCol != 1)) ||
	   (asmap->parityInfo->next != NULL) || (asmap->qInfo->next != NULL) || rf_CheckStripeForFailures(raidPtr, asmap))) {
	
	*createFunc = rf_EOCreateSmallWriteDAG;
      }
      else {
	*createFunc = rf_EOCreateLargeWriteDAG;
      }
      break;

    case 1: /* single disk fault */
      if (npfail==1) 
	{
	  RF_ASSERT ((asmap->failedPDA->type == RF_PDA_TYPE_PARITY) ||  (asmap->failedPDA->type == RF_PDA_TYPE_Q));
	  if (asmap->failedPDA->type == RF_PDA_TYPE_Q)
	    { /* q died, treat like normal mode raid5 write.*/
	      if (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) || (asmap->numStripeUnitsAccessed == 1))
		  || (asmap->parityInfo->next!=NULL) || rf_NumFailedDataUnitsInStripe(raidPtr,asmap))
		*createFunc = rf_EO_001_CreateSmallWriteDAG;