rf_dagutils.c

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

      retcode = 1;
    }
    acount[ node->antecedents[i]->nodeNum ]++;
  }
  for (i=0; i<node->numSuccedents; i++) {
    if (node->succedents[i]->visited == unvisited) {
      if (rf_ValidateBranch(node->succedents[i], scount,
          acount, nodes, unvisited))
      {
        retcode = 1;
      }
    }
  }
  return(retcode);
}

static void rf_ValidateBranchVisitedBits(node, unvisited, rl)
  RF_DagNode_t  *node;
  int            unvisited;
  int            rl;
{
  int i;

  RF_ASSERT(node->visited == unvisited);
  for (i=0; i<node->numSuccedents; i++) {
    if (node->succedents[i] == NULL) {
      printf("node=%lx node->succedents[%d] is NULL\n", node, i);
      RF_ASSERT(0);
    }
    rf_ValidateBranchVisitedBits(node->succedents[i],unvisited, rl+1);
  }
}

/* NOTE:  never call this on a big dag, because it is exponential
 * in execution time
 */
static void rf_ValidateVisitedBits(dag)
  RF_DagHeader_t  *dag;
{
  int i, unvisited;

  unvisited = dag->succedents[0]->visited;

  for (i=0; i<dag->numSuccedents; i++) {
    if (dag->succedents[i] == NULL) {
      printf("dag=%lx dag->succedents[%d] is NULL\n", dag, i);
      RF_ASSERT(0);
    }
    rf_ValidateBranchVisitedBits(dag->succedents[i],unvisited,0);
  }
}

/* validate a DAG.  _at entry_ verify that:
 *   -- numNodesCompleted is zero
 *   -- node queue is null
 *   -- dag status is rf_enable
 *   -- next pointer is null on every node
 *   -- all nodes have status wait
 *   -- numAntDone is zero in all nodes
 *   -- terminator node has zero successors
 *   -- no other node besides terminator has zero successors
 *   -- no successor or antecedent pointer in a node is NULL
 *   -- number of times that each node appears as a successor of another node
 *      is equal to the antecedent count on that node
 *   -- number of times that each node appears as an antecedent of another node
 *      is equal to the succedent count on that node
 *   -- what else?
 */
int rf_ValidateDAG(dag_h)
  RF_DagHeader_t  *dag_h;
{
  int i, nodecount;
  int *scount, *acount;        /* per-node successor and antecedent counts */
  RF_DagNode_t **nodes;        /* array of ptrs to nodes in dag */
  int retcode = 0;
  int unvisited;
  int commitNodeCount = 0;

  if (rf_validateVisitedDebug)
    rf_ValidateVisitedBits(dag_h);
  
  if (dag_h->numNodesCompleted != 0) {
    printf("INVALID DAG: num nodes completed is %d, should be 0\n",dag_h->numNodesCompleted);
    retcode = 1; goto validate_dag_bad;
  }
  if (dag_h->status != rf_enable) {
    printf("INVALID DAG: not enabled\n");
    retcode = 1; goto validate_dag_bad;
  }
  if (dag_h->numCommits != 0) {
    printf("INVALID DAG: numCommits != 0 (%d)\n",dag_h->numCommits);
    retcode = 1; goto validate_dag_bad;
  }
  if (dag_h->numSuccedents != 1) {
    /* currently, all dags must have only one succedent */
    printf("INVALID DAG: numSuccedents !1 (%d)\n",dag_h->numSuccedents);
    retcode = 1; goto validate_dag_bad;
  }
  nodecount = rf_AssignNodeNums(dag_h);

  unvisited = dag_h->succedents[0]->visited;
    
  RF_Calloc(scount, nodecount, sizeof(int), (int *));
  RF_Calloc(acount, nodecount, sizeof(int), (int *));
  RF_Calloc(nodes,  nodecount, sizeof(RF_DagNode_t *), (RF_DagNode_t **));
  for (i=0; i<dag_h->numSuccedents; i++) {
    if ((dag_h->succedents[i]->visited == unvisited)
        && rf_ValidateBranch(dag_h->succedents[i], scount,
        acount, nodes, unvisited))
    {
      retcode = 1;
    }
  }
  /* start at 1 to skip the header node */
  for (i=1; i<nodecount; i++) {
    if ( nodes[i]->commitNode )
      commitNodeCount++;
    if ( nodes[i]->doFunc == NULL ) {
      printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name);
      retcode = 1;
      goto validate_dag_out;
    }
    if ( nodes[i]->undoFunc == NULL ) {
      printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name);
      retcode = 1;
      goto validate_dag_out;
    }
    if ( nodes[i]->numAntecedents != scount[ nodes[i]->nodeNum ] ) {
      printf("INVALID DAG: node %s has %d antecedents but appears as a succedent %d times\n",
	     nodes[i]->name, nodes[i]->numAntecedents, scount[nodes[i]->nodeNum]);
      retcode = 1;
      goto validate_dag_out;
    }
    if ( nodes[i]->numSuccedents != acount[ nodes[i]->nodeNum ] ) {
      printf("INVALID DAG: node %s has %d succedents but appears as an antecedent %d times\n",
	     nodes[i]->name, nodes[i]->numSuccedents, acount[nodes[i]->nodeNum]);
      retcode = 1;
      goto validate_dag_out;
    }
  }

  if ( dag_h->numCommitNodes != commitNodeCount ) {
    printf("INVALID DAG: incorrect commit node count.  hdr->numCommitNodes (%d) found (%d) commit nodes in graph\n",
      dag_h->numCommitNodes, commitNodeCount);
    retcode = 1;
    goto validate_dag_out;
  }

validate_dag_out:
  RF_Free(scount, nodecount*sizeof(int));
  RF_Free(acount, nodecount*sizeof(int));
  RF_Free(nodes,  nodecount*sizeof(RF_DagNode_t *));
  if (retcode)
    rf_PrintDAGList(dag_h);
  
  if (rf_validateVisitedDebug)
    rf_ValidateVisitedBits(dag_h);
  
  return(retcode);

validate_dag_bad:
  rf_PrintDAGList(dag_h);
  return(retcode);
}


/******************************************************************************
 *
 * misc construction routines
 *
 *****************************************************************************/

void rf_redirect_asm(
  RF_Raid_t             *raidPtr,
  RF_AccessStripeMap_t  *asmap)
{
  int ds = (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) ? 1 : 0;
  int row = asmap->physInfo->row;
  int fcol = raidPtr->reconControl[row]->fcol;
  int srow = raidPtr->reconControl[row]->spareRow;
  int scol = raidPtr->reconControl[row]->spareCol;
  RF_PhysDiskAddr_t *pda;

  RF_ASSERT( raidPtr->status[row] == rf_rs_reconstructing );
  for (pda = asmap->physInfo; pda; pda=pda->next) {
    if (pda->col == fcol) {
      if (rf_dagDebug) {
        if (!rf_CheckRUReconstructed(raidPtr->reconControl[row]->reconMap,
          pda->startSector))
        {
          RF_PANIC();
        }
      }
      /*printf("Remapped data for large write\n");*/
      if (ds) {
        raidPtr->Layout.map->MapSector(raidPtr, pda->raidAddress,
          &pda->row, &pda->col, &pda->startSector, RF_REMAP);
      }
      else {
        pda->row = srow; pda->col = scol;
      }
    }
  }
  for (pda = asmap->parityInfo; pda; pda=pda->next) {
    if (pda->col == fcol) {
      if (rf_dagDebug) {
        if (!rf_CheckRUReconstructed(raidPtr->reconControl[row]->reconMap, pda->startSector)) {
          RF_PANIC();
        }
      }
    }
    if (ds) {
      (raidPtr->Layout.map->MapParity)(raidPtr, pda->raidAddress, &pda->row, &pda->col, &pda->startSector, RF_REMAP);
    }
    else {
      pda->row = srow; pda->col = scol;
    }
  }
}


/* this routine allocates read buffers and generates stripe maps for the
 * regions of the array from the start of the stripe to the start of the
 * access, and from the end of the access to the end of the stripe.  It also
 * computes and returns the number of DAG nodes needed to read all this data.
 * Note that this routine does the wrong thing if the access is fully
 * contained within one stripe unit, so we RF_ASSERT against this case at the
 * start.
 */
void rf_MapUnaccessedPortionOfStripe(
  RF_Raid_t                    *raidPtr,
  RF_RaidLayout_t              *layoutPtr, /* in: layout information */
  RF_AccessStripeMap_t         *asmap,     /* in: access stripe map */
  RF_DagHeader_t               *dag_h,     /* in: header of the dag to create */
  RF_AccessStripeMapHeader_t  **new_asm_h, /* in: ptr to array of 2 headers, to be filled in */
  int                          *nRodNodes, /* out: num nodes to be generated to read unaccessed data */
  char                        **sosBuffer, /* out: pointers to newly allocated buffer */
  char                        **eosBuffer,
  RF_AllocListElem_t           *allocList)
{
  RF_RaidAddr_t sosRaidAddress, eosRaidAddress;
  RF_SectorNum_t sosNumSector, eosNumSector;

  RF_ASSERT( asmap->numStripeUnitsAccessed > (layoutPtr->numDataCol/2) );
  /* generate an access map for the region of the array from start of stripe
   * to start of access */
  new_asm_h[0] = new_asm_h[1] = NULL; *nRodNodes = 0;
  if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->raidAddress)) {
    sosRaidAddress = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress);
    sosNumSector   = asmap->raidAddress - sosRaidAddress;
    RF_MallocAndAdd(*sosBuffer, rf_RaidAddressToByte(raidPtr, sosNumSector), (char *), allocList);
    new_asm_h[0]   = rf_MapAccess(raidPtr, sosRaidAddress, sosNumSector, *sosBuffer, RF_DONT_REMAP);
    new_asm_h[0]->next = dag_h->asmList;
    dag_h->asmList = new_asm_h[0];
    *nRodNodes    += new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
    
    RF_ASSERT(new_asm_h[0]->stripeMap->next == NULL);
    /* we're totally within one stripe here */
    if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
      rf_redirect_asm(raidPtr, new_asm_h[0]->stripeMap);
  }
  /* generate an access map for the region of the array from end of access
   * to end of stripe */
  if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->endRaidAddress)) {
    eosRaidAddress = asmap->endRaidAddress;
    eosNumSector   = rf_RaidAddressOfNextStripeBoundary(layoutPtr, eosRaidAddress) - eosRaidAddress;
    RF_MallocAndAdd(*eosBuffer, rf_RaidAddressToByte(raidPtr, eosNumSector), (char *), allocList);
    new_asm_h[1]   = rf_MapAccess(raidPtr, eosRaidAddress, eosNumSector, *eosBuffer, RF_DONT_REMAP);
    new_asm_h[1]->next = dag_h->asmList;
    dag_h->asmList = new_asm_h[1];
    *nRodNodes    += new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
    
    RF_ASSERT(new_asm_h[1]->stripeMap->next == NULL);
    /* we're totally within one stripe here */
    if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
      rf_redirect_asm(raidPtr, new_asm_h[1]->stripeMap);
  }
}



/* returns non-zero if the indicated ranges of stripe unit offsets overlap */
int rf_PDAOverlap(
  RF_RaidLayout_t    *layoutPtr,
  RF_PhysDiskAddr_t  *src,
  RF_PhysDiskAddr_t  *dest)
{
  RF_SectorNum_t soffs = rf_StripeUnitOffset(layoutPtr, src->startSector);
  RF_SectorNum_t doffs = rf_StripeUnitOffset(layoutPtr, dest->startSector);
  /* use -1 to be sure we stay within SU */
  RF_SectorNum_t send = rf_StripeUnitOffset(layoutPtr, src->startSector + src->numSector-1);
  RF_SectorNum_t dend = rf_StripeUnitOffset(layoutPtr, dest->startSector + dest->numSector-1);
  return( (RF_MAX(soffs,doffs) <= RF_MIN(send,dend)) ? 1 : 0 );
}


/* GenerateFailedAccessASMs
 *
 * this routine figures out what portion of the stripe needs to be read
 * to effect the degraded read or write operation.  It's primary function
 * is to identify everything required to recover the data, and then
 * eliminate anything that is already being accessed by the user.
 *
 * The main result is two new ASMs, one for the region from the start of the
 * stripe to the start of the access, and one for the region from the end of
 * the access to the end of the stripe.  These ASMs describe everything that
 * needs to be read to effect the degraded access.  Other results are:
 *    nXorBufs -- the total number of buffers that need to be XORed together to
 *                recover the lost data,
 *    rpBufPtr -- ptr to a newly-allocated buffer to hold the parity.  If NULL
 *                at entry, not allocated.
 *    overlappingPDAs --
 *                describes which of the non-failed PDAs in the user access
 *                overlap data that needs to be read to effect recovery.
 *                overlappingPDAs[i]==1 if and only if, neglecting the failed
 *                PDA, the ith pda in the input asm overlaps data that needs
 *                to be read for recovery.
 */
 /* in: asm - ASM for the actual access, one stripe only */
 /* in: faildPDA - which component of the access has failed */
 /* in: dag_h - header of the DAG we're going to create */
 /* out: new_asm_h - the two new ASMs */
 /* out: nXorBufs - the total number of xor bufs required */
 /* out: rpBufPtr - a buffer for the parity read */
void rf_GenerateFailedAccessASMs(
  RF_Raid_t                    *raidPtr,
  RF_AccessStripeMap_t         *asmap,
  RF_PhysDiskAddr_t            *failedPDA,
  RF_DagHeader_t               *dag_h,
  RF_AccessStripeMapHeader_t  **new_asm_h,
  int                          *nXorBufs,
  char                        **rpBufPtr,
  char                         *overlappingPDAs,
  RF_AllocListElem_t           *allocList)
{
  RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);

  /* s=start, e=end, s=stripe, a=access, f=failed, su=stripe unit */
  RF_RaidAddr_t sosAddr, sosEndAddr, eosStartAddr, eosAddr;

  RF_SectorCount_t numSect[2], numParitySect;
  RF_PhysDiskAddr_t *pda;
  char *rdBuf, *bufP;
  int foundit, i;

  bufP = NULL;
  foundit = 0;
  /* first compute the following raid addresses:
       start of stripe,                            (sosAddr)