rf_dagdegrd.c

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

   */
  dag_h->numSuccedents = 1;

  rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
    NULL, nRudNodes+nRrdNodes+1, 0, 0, 0, dag_h, "Nil", allocList);
  rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
    NULL, 1, 1, 0, 0, dag_h, "Cmt", allocList);
  rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc,
    NULL, 0, 1, 0, 0, dag_h, "Trm", allocList);
  rf_InitNode(xorNode, rf_wait, RF_FALSE, recFunc->simple, rf_NullNodeUndoFunc,
    NULL, 1, nRudNodes+nRrdNodes+1, 2*nXorBufs+2, 1, dag_h, 
	recFunc->SimpleName, allocList);

  /* fill in the Rud nodes */
  for (pda=asmap->physInfo, i=0; i<nRudNodes; i++, pda=pda->next) {
    if (pda == failedPDA) {i--; continue;}
    rf_InitNode(&rudNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc,
      rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h,
      "Rud", allocList);
    RF_ASSERT(pda);
    rudNodes[i].params[0].p = pda;
    rudNodes[i].params[1].p = pda->bufPtr;
    rudNodes[i].params[2].v = parityStripeID;
    rudNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
  }

  /* fill in the Rrd nodes */
  i = 0;
  if (new_asm_h[0]) {
    for (pda=new_asm_h[0]->stripeMap->physInfo;
         i<new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
         i++, pda=pda->next)
    {
      rf_InitNode(&rrdNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc,
        rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0,
        dag_h, "Rrd", allocList);
      RF_ASSERT(pda);
      rrdNodes[i].params[0].p = pda;
      rrdNodes[i].params[1].p = pda->bufPtr;
      rrdNodes[i].params[2].v = parityStripeID;
      rrdNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
    }
  }
  if (new_asm_h[1]) {
    for (j=0,pda=new_asm_h[1]->stripeMap->physInfo;
         j<new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
         j++, pda=pda->next)
    {
      rf_InitNode(&rrdNodes[i+j], rf_wait, RF_FALSE, rf_DiskReadFunc,
        rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0,
        dag_h, "Rrd", allocList);
      RF_ASSERT(pda);
      rrdNodes[i+j].params[0].p = pda;
      rrdNodes[i+j].params[1].p = pda->bufPtr;
      rrdNodes[i+j].params[2].v = parityStripeID;
      rrdNodes[i+j].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
    }
  }

  /* make a PDA for the parity unit */
  RF_MallocAndAdd(parityPDA, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList);
  parityPDA->row = asmap->parityInfo->row;
  parityPDA->col = asmap->parityInfo->col;
  parityPDA->startSector = ((asmap->parityInfo->startSector / sectorsPerSU)
    * sectorsPerSU) + (failedPDA->startSector % sectorsPerSU);
  parityPDA->numSector = failedPDA->numSector;

  /* initialize the Rp node */
  rf_InitNode(rpNode, rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc,
    rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rp ", allocList);
  rpNode->params[0].p = parityPDA;
  rpNode->params[1].p = rpBuf;
  rpNode->params[2].v = parityStripeID;
  rpNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);

  /*
   * the last and nastiest step is to assign all
   * the parameters of the Xor node
   */
  paramNum=0;
  for (i=0; i<nRrdNodes; i++) {
    /* all the Rrd nodes need to be xored together */
    xorNode->params[paramNum++] = rrdNodes[i].params[0];
    xorNode->params[paramNum++] = rrdNodes[i].params[1];
  }
  for (i=0; i<nRudNodes; i++) {
    /* any Rud nodes that overlap the failed access need to be xored in */
    if (overlappingPDAs[i]) {
      RF_MallocAndAdd(pda, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList);
      bcopy((char *)rudNodes[i].params[0].p, (char *)pda, sizeof(RF_PhysDiskAddr_t));
      rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_DOBUFFER, 0);
      xorNode->params[paramNum++].p = pda;
      xorNode->params[paramNum++].p = pda->bufPtr;
    }
  }
  RF_Free(overlappingPDAs, asmap->numStripeUnitsAccessed * sizeof(char));

  /* install parity pda as last set of params to be xor'd */
  xorNode->params[paramNum++].p = parityPDA;
  xorNode->params[paramNum++].p = rpBuf;

  /*
   * the last 2 params to the recovery xor node are
   * the failed PDA and the raidPtr
   */
  xorNode->params[paramNum++].p = failedPDA;
  xorNode->params[paramNum++].p = raidPtr;
  RF_ASSERT( paramNum == 2*nXorBufs+2 );

  /*
   * The xor node uses results[0] as the target buffer.
   * Set pointer and zero the buffer. In the kernel, this
   * may be a user buffer in which case we have to remap it.
   */
  xorNode->results[0] = failedPDA->bufPtr;
  RF_BZERO(bp, failedPDA->bufPtr, rf_RaidAddressToByte(raidPtr,
    failedPDA->numSector));

  /* connect nodes to form graph */
  /* connect the header to the block node */
  RF_ASSERT(dag_h->numSuccedents == 1);
  RF_ASSERT(blockNode->numAntecedents == 0);
  dag_h->succedents[0] = blockNode;

  /* connect the block node to the read nodes */
  RF_ASSERT(blockNode->numSuccedents == (1 + nRrdNodes + nRudNodes));
  RF_ASSERT(rpNode->numAntecedents == 1);
  blockNode->succedents[0] = rpNode;
  rpNode->antecedents[0] = blockNode;
  rpNode->antType[0] = rf_control;
  for (i = 0; i < nRrdNodes; i++) {
    RF_ASSERT(rrdNodes[i].numSuccedents == 1);
    blockNode->succedents[1 + i] = &rrdNodes[i];
    rrdNodes[i].antecedents[0] = blockNode;
    rrdNodes[i].antType[0] = rf_control;
  }
  for (i = 0; i < nRudNodes; i++) {
    RF_ASSERT(rudNodes[i].numSuccedents == 1);
    blockNode->succedents[1 + nRrdNodes + i] = &rudNodes[i];
    rudNodes[i].antecedents[0] = blockNode;
    rudNodes[i].antType[0] = rf_control;
  }

  /* connect the read nodes to the xor node */
  RF_ASSERT(xorNode->numAntecedents == (1 + nRrdNodes + nRudNodes));
  RF_ASSERT(rpNode->numSuccedents == 1);
  rpNode->succedents[0] = xorNode;
  xorNode->antecedents[0] = rpNode;
  xorNode->antType[0] = rf_trueData;
  for (i = 0; i < nRrdNodes; i++) {
    RF_ASSERT(rrdNodes[i].numSuccedents == 1);
    rrdNodes[i].succedents[0] = xorNode;
    xorNode->antecedents[1 + i] = &rrdNodes[i];
    xorNode->antType[1 + i] = rf_trueData;
  }
  for (i = 0; i < nRudNodes; i++) {
    RF_ASSERT(rudNodes[i].numSuccedents == 1);
    rudNodes[i].succedents[0] = xorNode;
    xorNode->antecedents[1 + nRrdNodes + i] = &rudNodes[i];
    xorNode->antType[1 + nRrdNodes + i] = rf_trueData;
  }

  /* connect the xor node to the commit node */
  RF_ASSERT(xorNode->numSuccedents == 1);
  RF_ASSERT(commitNode->numAntecedents == 1);
  xorNode->succedents[0] = commitNode;
  commitNode->antecedents[0] = xorNode;
  commitNode->antType[0] = rf_control;

  /* connect the termNode to the commit node */
  RF_ASSERT(commitNode->numSuccedents == 1);
  RF_ASSERT(termNode->numAntecedents == 1);
  RF_ASSERT(termNode->numSuccedents == 0);
  commitNode->succedents[0] = termNode;
  termNode->antType[0] = rf_control;
  termNode->antecedents[0]  = commitNode;
}


/******************************************************************************
 * Create a degraded read DAG for Chained Declustering
 *
 * Hdr -> Nil -> R(p/s)d -> Cmt -> Trm
 *
 * The "Rd" node reads data from the surviving disk in the mirror pair
 *   Rpd - read of primary copy
 *   Rsd - read of secondary copy
 *
 * Parameters:  raidPtr   - description of the physical array
 *              asmap     - logical & physical addresses for this access
 *              bp        - buffer ptr (for holding write data)
 *              flags     - general flags (e.g. disk locking) 
 *              allocList - list of memory allocated in DAG creation
 *****************************************************************************/

void rf_CreateRaidCDegradedReadDAG(
  RF_Raid_t             *raidPtr,
  RF_AccessStripeMap_t  *asmap,
  RF_DagHeader_t        *dag_h,
  void                  *bp,
  RF_RaidAccessFlags_t   flags,
  RF_AllocListElem_t    *allocList)
{
  RF_DagNode_t *nodes, *rdNode, *blockNode, *commitNode, *termNode;
  RF_StripeNum_t parityStripeID;
  int useMirror, i, shiftable;
  RF_ReconUnitNum_t which_ru;
  RF_PhysDiskAddr_t *pda;

  if ((asmap->numDataFailed + asmap->numParityFailed) == 0) {
    shiftable = RF_TRUE;
  }
  else {
    shiftable = RF_FALSE;
  }
  useMirror = 0;
  parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout),
    asmap->raidAddress, &which_ru);

  if (rf_dagDebug) {
    printf("[Creating RAID C degraded read DAG]\n");
  }
  dag_h->creator = "RaidCDegradedReadDAG";
  /* alloc the Wnd nodes and the Wmir node */
  if (asmap->numDataFailed == 0)
    useMirror = RF_FALSE;
  else
    useMirror = RF_TRUE;

  /* total number of nodes = 1 + (block + commit + terminator) */
  RF_CallocAndAdd(nodes, 4, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList);
  i = 0;
  rdNode      = &nodes[i]; i++;
  blockNode   = &nodes[i]; i++;
  commitNode = &nodes[i]; i++;
  termNode    = &nodes[i]; i++;

  /*
   * This dag can not commit until the commit node is reached.
   * Errors prior to the commit point imply the dag has failed
   * and must be retried.
   */
  dag_h->numCommitNodes = 1;
  dag_h->numCommits = 0;
  dag_h->numSuccedents = 1;

  /* initialize the block, commit, and terminator nodes */
  rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
    NULL, 1, 0, 0, 0, dag_h, "Nil", allocList);
  rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
    NULL, 1, 1, 0, 0, dag_h, "Cmt", allocList);
  rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc,
    NULL, 0, 1, 0, 0, dag_h, "Trm", allocList);

  pda = asmap->physInfo;
  RF_ASSERT(pda != NULL);
  /* parityInfo must describe entire parity unit */
  RF_ASSERT(asmap->parityInfo->next == NULL);

  /* initialize the data node */
  if (!useMirror) {
    rf_InitNode(rdNode, rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc,
      rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rpd", allocList);
    if (shiftable && rf_compute_workload_shift(raidPtr, pda)) {
     /* shift this read to the next disk in line */
  	 rdNode->params[0].p = asmap->parityInfo;
   	 rdNode->params[1].p = pda->bufPtr;
	 rdNode->params[2].v = parityStripeID;
	 rdNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
	}
    else {
      /* read primary copy */
      rdNode->params[0].p = pda;  
      rdNode->params[1].p = pda->bufPtr;
      rdNode->params[2].v = parityStripeID;
      rdNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
    }
  }
  else {
    /* read secondary copy of data */
    rf_InitNode(rdNode, rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc,
      rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rsd", allocList);
    rdNode->params[0].p = asmap->parityInfo;
    rdNode->params[1].p = pda->bufPtr;
    rdNode->params[2].v = parityStripeID;
    rdNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru);
  }

  /* connect header to block node */
  RF_ASSERT(dag_h->numSuccedents == 1);
  RF_ASSERT(blockNode->numAntecedents == 0);
  dag_h->succedents[0] = blockNode;

  /* connect block node to rdnode */
  RF_ASSERT(blockNode->numSuccedents == 1);
  RF_ASSERT(rdNode->numAntecedents == 1);
  blockNode->succedents[0] = rdNode;
  rdNode->antecedents[0] = blockNode;
  rdNode->antType[0] = rf_control;

  /* connect rdnode to commit node */
  RF_ASSERT(rdNode->numSuccedents == 1);
  RF_ASSERT(commitNode->numAntecedents == 1);
  rdNode->succedents[0] = commitNode;
  commitNode->antecedents[0] = rdNode;
  commitNode->antType[0] = rf_control;

  /* connect commit node to terminator */
  RF_ASSERT(commitNode->numSuccedents == 1);
  RF_ASSERT(termNode->numAntecedents == 1);
  RF_ASSERT(termNode->numSuccedents == 0);
  commitNode->succedents[0] = termNode;
  termNode->antecedents[0] = commitNode;
  termNode->antType[0] = rf_control;
}

/*
 * XXX move this elsewhere?
 */
void rf_DD_GenerateFailedAccessASMs(
  RF_Raid_t              *raidPtr,
  RF_AccessStripeMap_t   *asmap,
  RF_PhysDiskAddr_t     **pdap,
  int                    *nNodep,
  RF_PhysDiskAddr_t     **pqpdap,
  int                    *nPQNodep,
  RF_AllocListElem_t     *allocList)
{
  RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
  int PDAPerDisk,i;
  RF_SectorCount_t secPerSU = layoutPtr->sectorsPerStripeUnit;
  int numDataCol = layoutPtr->numDataCol;
  int state;
  RF_SectorNum_t suoff, suend;
  unsigned firstDataCol, napdas, count;
  RF_SectorNum_t fone_start, fone_end, ftwo_start, ftwo_end;
  RF_PhysDiskAddr_t *fone = asmap->failedPDA, *ftwo = asmap->failedPDAtwo;
  RF_PhysDiskAddr_t *pda_p;
  RF_PhysDiskAddr_t *phys_p;
  RF_RaidAddr_t sosAddr;

  /* determine how many pda's we will have to generate per unaccess stripe.
     If there is only one failed data unit, it is one; if two, possibly two,
     depending wether they overlap. */

  fone_start = rf_StripeUnitOffset(layoutPtr,fone->startSector);
  fone_end = fone_start + fone->numSector;

#define CONS_PDA(if,start,num) \
  pda_p->row = asmap->if->row;    pda_p->col = asmap->if->col; \
  pda_p->startSector = ((asmap->if->startSector / secPerSU) * secPerSU) + start; \
  pda_p->numSector = num; \
  pda_p->next = NULL; \
  RF_MallocAndAdd(pda_p->bufPtr,rf_RaidAddressToByte(raidPtr,num),(char *), allocList)

  if (asmap->numDataFailed==1)
    {
      PDAPerDisk = 1;
      state = 1;
      RF_MallocAndAdd(*pqpdap,2*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList);
      pda_p = *pqpdap;
      /* build p */
      CONS_PDA(parityInfo,fone_start,fone->numSector);
      pda_p->type = RF_PDA_TYPE_PARITY;
      pda_p++;
      /* build q */
      CONS_PDA(qInfo,fone_start,fone->numSector);
      pda_p->type = RF_PDA_TYPE_Q;
    }
  else
    {
      ftwo_start = rf_StripeUnitOffset(layoutPtr,ftwo->startSector);
      ftwo_end = ftwo_start + ftwo->numSector;    
      if (fone->numSector + ftwo->numSector > secPerSU)
	{
	  PDAPerDisk = 1;
	  state = 2;
	  RF_MallocAndAdd(*pqpdap,2*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList);
	  pda_p = *pqpdap;
	  CONS_PDA(parityInfo,0,secPerSU);
	  pda_p->type = RF_PDA_TYPE_PARITY;
	  pda_p++;
	  CONS_PDA(qInfo,0,secPerSU);
	  pda_p->type = RF_PDA_TYPE_Q;
	}
      else
	{
	  PDAPerDisk = 2;
	  state = 3;
	  /* four of them, fone, then ftwo */
	  RF_MallocAndAdd(*pqpdap,4*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList);
	  pda_p = *pqpdap;
	  CONS_PDA(parityInfo,fone_start,fone->numSector);
	  pda_p->type = RF_PDA_TYPE_PARITY;
	  pda_p++;
	  CONS_PDA(qInfo,fone_start,fone->numSector);
	  pda_p->type = RF_PDA_TYPE_Q;
	  pda_p++;
	  CONS_PDA(parityInfo,ftwo_start,ftwo->numSector);
	  pda_p->type = RF_PDA_TYPE_PARITY;
	  pda_p++;
	  CONS_PDA(qInfo,ftwo_start,ftwo->numSector);
	  pda_p->type = RF_PDA_TYPE_Q;