rf_dagdegrd.c

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

	}
    }
  /* figure out number of nonaccessed pda */
  napdas = PDAPerDisk * (numDataCol - asmap->numStripeUnitsAccessed - (ftwo==NULL ? 1 : 0));
  *nPQNodep = PDAPerDisk;

  /* sweep over the over accessed pda's, figuring out the number of
     additional pda's to generate. Of course, skip the failed ones */

  count = 0;
  for ( pda_p=asmap->physInfo; pda_p; pda_p= pda_p->next)
    {
      if ((pda_p == fone) || (pda_p == ftwo))
	continue;
      suoff = rf_StripeUnitOffset(layoutPtr,pda_p->startSector);
      suend = suoff + pda_p->numSector;
      switch (state)
	{
	case 1: /* one failed PDA to overlap */
	  /* if a PDA doesn't contain the failed unit, it can
	     only miss the start or end, not both */
	  if ((suoff > fone_start) || (suend <fone_end))
	    count++;
	  break;
	case 2: /* whole stripe */
	  if (suoff) /* leak at begining */
	    count++;
	  if (suend < numDataCol) /* leak at end */
	    count++;
	  break;
	case 3: /* two disjoint units */
	  if ((suoff > fone_start) || (suend <fone_end))
	    count++;
	  if ((suoff > ftwo_start) || (suend <ftwo_end))
	    count++;
	  break;
	default:
	  RF_PANIC();
	}
    }

  napdas += count;
  *nNodep = napdas;
  if (napdas == 0) return; /* short circuit */

  /* allocate up our list of pda's */
     
  RF_CallocAndAdd(pda_p, napdas, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList);
  *pdap = pda_p;
    
  /* linkem together */
  for (i=0; i < (napdas-1); i++)
    pda_p[i].next = pda_p+(i+1);

  /* march through the one's up to the first accessed disk */
  firstDataCol = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),asmap->physInfo->raidAddress) % numDataCol;
  sosAddr      = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress);
  for (i=0; i < firstDataCol; i++)
    {
      if ((pda_p - (*pdap)) == napdas) 
	continue;
      pda_p->type = RF_PDA_TYPE_DATA;
      pda_p->raidAddress = sosAddr + (i * secPerSU);
      (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
      /* skip over dead disks */
      if (RF_DEAD_DISK(raidPtr->Disks[pda_p->row][pda_p->col].status)) 
	continue;
      switch (state)
	{
	case 1: /* fone */
	  pda_p->numSector = fone->numSector;
	  pda_p->raidAddress += fone_start;
	  pda_p->startSector += fone_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  break;
	case 2: /* full stripe */
	  pda_p->numSector = secPerSU;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,secPerSU), (char *), allocList);
	  break;
	case 3: /* two slabs */
	  pda_p->numSector = fone->numSector;
	  pda_p->raidAddress += fone_start;
	  pda_p->startSector += fone_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  pda_p++;
          pda_p->type = RF_PDA_TYPE_DATA;
          pda_p->raidAddress = sosAddr + (i * secPerSU);
          (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
	  pda_p->numSector = ftwo->numSector;
	  pda_p->raidAddress += ftwo_start;
	  pda_p->startSector += ftwo_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  break;
	default:
	  RF_PANIC();
	}
      pda_p++;
    }

  /* march through the touched stripe units */
  for (phys_p = asmap->physInfo; phys_p; phys_p = phys_p->next, i++)
    {
      if ((phys_p == asmap->failedPDA) || (phys_p == asmap->failedPDAtwo))
	continue;
      suoff = rf_StripeUnitOffset(layoutPtr,phys_p->startSector);
      suend = suoff + phys_p->numSector;
      switch(state)
	{
	case 1: /* single buffer */
	  if (suoff > fone_start)
	    { 
	      RF_ASSERT( suend >= fone_end );
	      /* The data read starts after the mapped access,
		 snip off the begining */
	      pda_p->numSector = suoff - fone_start;
	      pda_p->raidAddress = sosAddr + (i*secPerSU) + fone_start;
	      (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
	      RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	      pda_p++;
	    }
	  if (suend < fone_end)
	    {
	      RF_ASSERT ( suoff <= fone_start);
	      /* The data read stops before the end of the failed access, extend */
	      pda_p->numSector = fone_end - suend;
	      pda_p->raidAddress = sosAddr + (i*secPerSU) + suend; /* off by one? */
	      (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
	      RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	      pda_p++;
	    }
	  break;
	case 2: /* whole stripe unit */
	  RF_ASSERT( (suoff == 0) || (suend == secPerSU));
	  if (suend < secPerSU)
	    { /* short read, snip from end on */
	      pda_p->numSector = secPerSU - suend;
	      pda_p->raidAddress = sosAddr + (i*secPerSU) + suend; /* off by one? */
	      (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
	      RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	      pda_p++;
	    }
	  else
	    if (suoff > 0)
	      { /* short at front */
		pda_p->numSector = suoff;
		pda_p->raidAddress = sosAddr + (i*secPerSU);
		(raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
		RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
		pda_p++;
	      }
	  break;
	case 3: /* two nonoverlapping failures */
	  if ((suoff > fone_start) || (suend <fone_end))
	    {
	      if (suoff > fone_start)
		{ 
		  RF_ASSERT( suend >= fone_end );
		  /* The data read starts after the mapped access,
		     snip off the begining */
		  pda_p->numSector = suoff - fone_start;
		  pda_p->raidAddress = sosAddr + (i*secPerSU) + fone_start;
		  (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
		  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
		  pda_p++;
		}
	      if (suend < fone_end)
		{
		  RF_ASSERT ( suoff <= fone_start);
		  /* The data read stops before the end of the failed access, extend */
		  pda_p->numSector = fone_end - suend;
		  pda_p->raidAddress = sosAddr + (i*secPerSU) + suend; /* off by one? */
		  (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
		  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
		  pda_p++;
		}
	    }
	  if ((suoff > ftwo_start) || (suend <ftwo_end))
	    {
	      if (suoff > ftwo_start)
		{ 
		  RF_ASSERT( suend >= ftwo_end );
		  /* The data read starts after the mapped access,
		     snip off the begining */
		  pda_p->numSector = suoff - ftwo_start;
		  pda_p->raidAddress = sosAddr + (i*secPerSU) + ftwo_start;
		  (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
		  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
		  pda_p++;
		}
	      if (suend < ftwo_end)
		{
		  RF_ASSERT ( suoff <= ftwo_start);
		  /* The data read stops before the end of the failed access, extend */
		  pda_p->numSector = ftwo_end - suend;
		  pda_p->raidAddress = sosAddr + (i*secPerSU) + suend; /* off by one? */
		  (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
		  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
		  pda_p++;
		}
	    }
	  break;
	default:
	  RF_PANIC();
        }
    }

  /* after the last accessed disk */
  for (; i < numDataCol; i++ )
    {
      if ((pda_p - (*pdap)) == napdas) 
	continue;
      pda_p->type = RF_PDA_TYPE_DATA;
      pda_p->raidAddress = sosAddr + (i * secPerSU);
      (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
      /* skip over dead disks */
      if (RF_DEAD_DISK(raidPtr->Disks[pda_p->row][pda_p->col].status)) 
	continue;
      switch (state)
	{
	case 1: /* fone */
	  pda_p->numSector = fone->numSector;
	  pda_p->raidAddress += fone_start;
	  pda_p->startSector += fone_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  break;
	case 2: /* full stripe */
	  pda_p->numSector = secPerSU;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,secPerSU), (char *), allocList);
	  break;
	case 3: /* two slabs */
	  pda_p->numSector = fone->numSector;
	  pda_p->raidAddress += fone_start;
	  pda_p->startSector += fone_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  pda_p++;
          pda_p->type = RF_PDA_TYPE_DATA;
          pda_p->raidAddress = sosAddr + (i * secPerSU);
          (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0);
	  pda_p->numSector = ftwo->numSector;
	  pda_p->raidAddress += ftwo_start;
	  pda_p->startSector += ftwo_start;
	  RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList);
	  break;
	default:
	  RF_PANIC();
	}
      pda_p++;
    }

  RF_ASSERT  (pda_p - *pdap == napdas);
  return;
}

#define INIT_DISK_NODE(node,name) \
rf_InitNode(node, rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 2,1,4,0, dag_h, name, allocList); \
(node)->succedents[0] = unblockNode; \
(node)->succedents[1] = recoveryNode; \
(node)->antecedents[0] = blockNode; \
(node)->antType[0] = rf_control

#define DISK_NODE_PARAMS(_node_,_p_) \
  (_node_).params[0].p = _p_ ; \
  (_node_).params[1].p = (_p_)->bufPtr; \
  (_node_).params[2].v = parityStripeID; \
  (_node_).params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru)

void rf_DoubleDegRead(
  RF_Raid_t              *raidPtr,
  RF_AccessStripeMap_t   *asmap,
  RF_DagHeader_t         *dag_h,
  void                   *bp,
  RF_RaidAccessFlags_t    flags,
  RF_AllocListElem_t     *allocList,
  char                   *redundantReadNodeName,
  char                   *recoveryNodeName,
  int                   (*recovFunc)())
{
  RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
  RF_DagNode_t *nodes, *rudNodes, *rrdNodes, *recoveryNode, *blockNode, *unblockNode, *rpNodes, *rqNodes, *termNode;
  RF_PhysDiskAddr_t *pda, *pqPDAs;
  RF_PhysDiskAddr_t *npdas;
  int nNodes, nRrdNodes, nRudNodes, i;
  RF_ReconUnitNum_t which_ru;
  int nReadNodes, nPQNodes;
  RF_PhysDiskAddr_t *failedPDA = asmap->failedPDA;      
  RF_PhysDiskAddr_t *failedPDAtwo = asmap->failedPDAtwo;    
  RF_StripeNum_t parityStripeID = rf_RaidAddressToParityStripeID(layoutPtr, asmap->raidAddress, &which_ru);

  if (rf_dagDebug) printf("[Creating Double Degraded Read DAG]\n");
  rf_DD_GenerateFailedAccessASMs(raidPtr, asmap, &npdas, &nRrdNodes, &pqPDAs, &nPQNodes,allocList);

  nRudNodes = asmap->numStripeUnitsAccessed - (asmap->numDataFailed);
  nReadNodes = nRrdNodes + nRudNodes + 2*nPQNodes;
  nNodes = 4 /* block, unblock, recovery, term */ + nReadNodes;

  RF_CallocAndAdd(nodes, nNodes, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList);
  i = 0;
  blockNode    = &nodes[i]; i += 1;
  unblockNode  = &nodes[i]; i += 1;
  recoveryNode = &nodes[i]; i += 1;
  termNode     = &nodes[i]; i += 1;
  rudNodes     = &nodes[i]; i += nRudNodes;
  rrdNodes     = &nodes[i]; i += nRrdNodes;
  rpNodes      = &nodes[i]; i += nPQNodes;
  rqNodes      = &nodes[i]; i += nPQNodes;
  RF_ASSERT(i == nNodes);

  dag_h->numSuccedents = 1;
  dag_h->succedents[0] = blockNode;
  dag_h->creator = "DoubleDegRead";
  dag_h->numCommits = 0;
  dag_h->numCommitNodes = 1; /*unblock */

  rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 0, 2, 0, 0, dag_h, "Trm", allocList);
  termNode->antecedents[0]  = unblockNode;
  termNode->antType[0] = rf_control;
  termNode->antecedents[1]  = recoveryNode;
  termNode->antType[1] = rf_control;

  /* init the block and unblock nodes */
  /* The block node has all nodes except itself, unblock and recovery as successors. Similarly for 
     predecessors of the unblock. */
  rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nReadNodes, 0, 0, 0, dag_h, "Nil", allocList);
  rf_InitNode(unblockNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, 1, nReadNodes, 0, 0, dag_h, "Nil", allocList);
  
  for (i=0; i < nReadNodes; i++)
    {
      blockNode->succedents[i] = rudNodes+i;
      unblockNode->antecedents[i] = rudNodes+i;
      unblockNode->antType[i] = rf_control;
    }
  unblockNode->succedents[0] = termNode;

  /* The recovery node has all the reads as predecessors, and the term node as successors. It gets a pda as a param
     from each of the read nodes plus the raidPtr.
     For each failed unit is has a result pda. */
  rf_InitNode(recoveryNode, rf_wait, RF_FALSE, recovFunc, rf_NullNodeUndoFunc, NULL, 
	   1, /* succesors */
	   nReadNodes, /* preds */ 
	   nReadNodes+2, /* params */
	   asmap->numDataFailed, /* results */
	   dag_h, recoveryNodeName, allocList);
  
  recoveryNode->succedents[0] = termNode;
  for (i=0; i < nReadNodes; i++) {
    recoveryNode->antecedents[i] = rudNodes+i;
    recoveryNode->antType[i] = rf_trueData;
  }
  
  /* build the read nodes, then come back and fill in recovery params and results */
  pda = asmap->physInfo;
  for (i=0; i < nRudNodes; pda = pda->next)
    {
      if ((pda == failedPDA) || (pda == failedPDAtwo))
	continue;
      INIT_DISK_NODE(rudNodes+i,"Rud");
      RF_ASSERT(pda);
      DISK_NODE_PARAMS(rudNodes[i],pda);
      i++;
    }

  pda = npdas;
  for (i=0; i < nRrdNodes; i++, pda = pda->next)
    {
      INIT_DISK_NODE(rrdNodes+i,"Rrd");
      RF_ASSERT(pda);
      DISK_NODE_PARAMS(rrdNodes[i],pda);
    }
  
  /* redundancy pdas */
  pda = pqPDAs;
  INIT_DISK_NODE(rpNodes,"Rp");
  RF_ASSERT(pda);
  DISK_NODE_PARAMS(rpNodes[0],pda);
  pda++;
  INIT_DISK_NODE(rqNodes,redundantReadNodeName );
  RF_ASSERT(pda);
  DISK_NODE_PARAMS(rqNodes[0],pda);
  if (nPQNodes==2)
    {
      pda++;
      INIT_DISK_NODE(rpNodes+1,"Rp");
      RF_ASSERT(pda);
      DISK_NODE_PARAMS(rpNodes[1],pda);
      pda++;
      INIT_DISK_NODE( rqNodes+1,redundantReadNodeName );
      RF_ASSERT(pda);
      DISK_NODE_PARAMS(rqNodes[1],pda);
    }

  /* fill in recovery node params */
  for (i=0; i < nReadNodes; i++)
    recoveryNode->params[i] = rudNodes[i].params[0]; /* pda */
  recoveryNode->params[i++].p = (void *) raidPtr;
  recoveryNode->params[i++].p = (void *) asmap;
  recoveryNode->results[0] = failedPDA;
  if (asmap->numDataFailed ==2 )
    recoveryNode->results[1] = failedPDAtwo;

  /* zero fill the target data buffers? */
}