rf_dagutils.c

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

}

static RF_FreeList_t *rf_dagh_freelist;

#define RF_MAX_FREE_DAGH 128
#define RF_DAGH_INC       16
#define RF_DAGH_INITIAL   32

static void rf_ShutdownDAGs(ignored)
  void  *ignored;
{
	RF_FREELIST_DESTROY(rf_dagh_freelist,next,(RF_DagHeader_t *));
}

int rf_ConfigureDAGs(listp)
  RF_ShutdownList_t  **listp;
{
	int rc;

	RF_FREELIST_CREATE(rf_dagh_freelist, RF_MAX_FREE_DAGH,
		RF_DAGH_INC, sizeof(RF_DagHeader_t));
	if (rf_dagh_freelist == NULL)
		return(ENOMEM);
	rc = rf_ShutdownCreate(listp, rf_ShutdownDAGs, NULL);
	if (rc) {
		RF_ERRORMSG3("Unable to add to shutdown list file %s line %d rc=%d\n",
			__FILE__, __LINE__, rc);
		rf_ShutdownDAGs(NULL);
		return(rc);
	}
	RF_FREELIST_PRIME(rf_dagh_freelist, RF_DAGH_INITIAL,next,
		(RF_DagHeader_t *));
	return(0);
}

RF_DagHeader_t *rf_AllocDAGHeader()
{
	RF_DagHeader_t *dh;

	RF_FREELIST_GET(rf_dagh_freelist,dh,next,(RF_DagHeader_t *));
	if (dh) {
		bzero((char *)dh, sizeof(RF_DagHeader_t));
	}
	return(dh);
}

void rf_FreeDAGHeader(RF_DagHeader_t *dh)
{
	RF_FREELIST_FREE(rf_dagh_freelist,dh,next);
}

/* allocates a buffer big enough to hold the data described by pda */
void *rf_AllocBuffer(
  RF_Raid_t           *raidPtr,
  RF_DagHeader_t      *dag_h,
  RF_PhysDiskAddr_t   *pda,
  RF_AllocListElem_t  *allocList)
{
  char *p;

  RF_MallocAndAdd(p, pda->numSector << raidPtr->logBytesPerSector,
    (char *), allocList);
  return((void *)p);
}

/******************************************************************************
 *
 * debug routines
 *
 *****************************************************************************/

char *rf_NodeStatusString(RF_DagNode_t *node)
{
  switch (node->status) {
    case rf_wait: return("wait");
    case rf_fired: return("fired");
    case rf_good: return("good");
    case rf_bad: return("bad");
    default: return("?");
  }
}

void rf_PrintNodeInfoString(RF_DagNode_t *node)
{
  RF_PhysDiskAddr_t *pda;
  int (*df)() = node->doFunc;
  int i, lk, unlk;
  void *bufPtr;
  
  if ((df==rf_DiskReadFunc) || (df==rf_DiskWriteFunc)
      || (df==rf_DiskReadMirrorIdleFunc)
      || (df == rf_DiskReadMirrorPartitionFunc))
  {
    pda = (RF_PhysDiskAddr_t *)node->params[0].p;
    bufPtr = (void *)node->params[1].p;
    lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
    unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
    RF_ASSERT( !(lk && unlk) );
    printf("r %d c %d offs %ld nsect %d buf 0x%lx %s\n", pda->row, pda->col,
       pda->startSector, pda->numSector, bufPtr,
       (lk) ? "LOCK" : ((unlk) ? "UNLK" : " "));
    return;
  }

  if (df == rf_DiskUnlockFunc) {
    pda = (RF_PhysDiskAddr_t *)node->params[0].p;
    lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
    unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
    RF_ASSERT( !(lk && unlk) );
    printf("r %d c %d %s\n", pda->row, pda->col,
      (lk) ? "LOCK" : ((unlk) ? "UNLK" : "nop"));
    return;
  }

  if ((df==rf_SimpleXorFunc) || (df==rf_RegularXorFunc)
      || (df==rf_RecoveryXorFunc))
  {
    printf("result buf 0x%lx\n",(long) node->results[0]);
    for (i=0; i<node->numParams-1; i+=2) {
      pda = (RF_PhysDiskAddr_t *)node->params[i].p;
      bufPtr = (RF_PhysDiskAddr_t *)node->params[i+1].p;
      printf("    buf 0x%lx r%d c%d offs %ld nsect %d\n",
        bufPtr, pda->row, pda->col, pda->startSector, pda->numSector);
    }
    return;
  }

#if RF_INCLUDE_PARITYLOGGING > 0
  if (df==rf_ParityLogOverwriteFunc || df==rf_ParityLogUpdateFunc) {
    for (i=0; i<node->numParams-1; i+=2) {
      pda = (RF_PhysDiskAddr_t *)node->params[i].p;
      bufPtr = (RF_PhysDiskAddr_t *)node->params[i+1].p;
      printf(" r%d c%d offs %ld nsect %d buf 0x%lx\n", pda->row, pda->col,
        pda->startSector, pda->numSector, bufPtr);
    }
    return;
  }
#endif /* RF_INCLUDE_PARITYLOGGING > 0 */

  if ((df==rf_TerminateFunc) || (df==rf_NullNodeFunc)) {
    printf("\n");
    return;
  }

  printf("?\n");
}

static void rf_RecurPrintDAG(node, depth, unvisited)
  RF_DagNode_t  *node;
  int            depth;
  int            unvisited;
{
  char *anttype;
  int i;

  node->visited = (unvisited) ? 0 : 1;
  printf("(%d) %d C%d %s: %s,s%d %d/%d,a%d/%d,p%d,r%d S{", depth,
    node->nodeNum, node->commitNode, node->name, rf_NodeStatusString(node),
    node->numSuccedents, node->numSuccFired, node->numSuccDone, 
	node->numAntecedents, node->numAntDone, node->numParams,node->numResults);
  for (i=0; i<node->numSuccedents; i++) {
    printf("%d%s", node->succedents[i]->nodeNum,
      ((i==node->numSuccedents-1) ? "\0" : " "));
  }
  printf("} A{");
  for (i=0; i<node->numAntecedents; i++) {
    switch (node->antType[i]) {
    case rf_trueData :
      anttype = "T";
      break;
    case rf_antiData :
      anttype = "A";
      break;
    case rf_outputData :
      anttype = "O";
      break;
    case rf_control :
      anttype = "C";
      break;
    default :
      anttype = "?";
      break;
    }
    printf("%d(%s)%s", node->antecedents[i]->nodeNum, anttype, (i==node->numAntecedents-1) ? "\0" : " ");
  }
  printf("}; ");
  rf_PrintNodeInfoString(node);
  for (i=0; i<node->numSuccedents; i++) {
    if (node->succedents[i]->visited == unvisited)
      rf_RecurPrintDAG(node->succedents[i], depth+1, unvisited);
  }
}

static void rf_PrintDAG(dag_h)
  RF_DagHeader_t  *dag_h;
{
  int unvisited, i;
  char *status;

  /* set dag status */
  switch (dag_h->status) {
  case rf_enable :
    status = "enable";
    break;
  case rf_rollForward :
    status = "rollForward";
    break;
  case rf_rollBackward :
    status = "rollBackward";
    break;
  default :
    status = "illegal!";
    break;
  }
  /* find out if visited bits are currently set or clear */
  unvisited = dag_h->succedents[0]->visited;
  
  printf("DAG type:  %s\n", dag_h->creator);
  printf("format is (depth) num commit type: status,nSucc nSuccFired/nSuccDone,nAnte/nAnteDone,nParam,nResult S{x} A{x(type)};  info\n");
  printf("(0) %d Hdr: %s, s%d, (commit %d/%d) S{", dag_h->nodeNum,
    status, dag_h->numSuccedents, dag_h->numCommitNodes, dag_h->numCommits);
  for (i=0; i<dag_h->numSuccedents; i++) {
    printf("%d%s", dag_h->succedents[i]->nodeNum,
      ((i==dag_h->numSuccedents-1) ? "\0" : " "));
  }
  printf("};\n");
  for (i=0; i<dag_h->numSuccedents; i++) {
    if (dag_h->succedents[i]->visited == unvisited)
      rf_RecurPrintDAG(dag_h->succedents[i], 1, unvisited);
  }
}

/* assigns node numbers */
int rf_AssignNodeNums(RF_DagHeader_t *dag_h)
{
  int unvisited, i, nnum;
  RF_DagNode_t *node;

  nnum = 0;
  unvisited = dag_h->succedents[0]->visited;
  
  dag_h->nodeNum = nnum++;
  for (i=0; i<dag_h->numSuccedents; i++) {
    node = dag_h->succedents[i];
    if (node->visited == unvisited) {
      nnum = rf_RecurAssignNodeNums(dag_h->succedents[i], nnum, unvisited);
    }
  }
  return(nnum);
}

int rf_RecurAssignNodeNums(node, num, unvisited)
  RF_DagNode_t  *node;
  int            num;
  int            unvisited;
{
  int i;

  node->visited = (unvisited) ? 0 : 1;

  node->nodeNum = num++;
  for (i=0; i<node->numSuccedents; i++) {
    if (node->succedents[i]->visited == unvisited) {
      num = rf_RecurAssignNodeNums(node->succedents[i], num, unvisited);
    }
  }
  return(num);
}

/* set the header pointers in each node to "newptr" */
void rf_ResetDAGHeaderPointers(dag_h, newptr)
  RF_DagHeader_t  *dag_h;
  RF_DagHeader_t  *newptr;
{
  int i;
  for (i=0; i<dag_h->numSuccedents; i++)
    if (dag_h->succedents[i]->dagHdr != newptr)
      rf_RecurResetDAGHeaderPointers(dag_h->succedents[i], newptr);
}

void rf_RecurResetDAGHeaderPointers(node, newptr)
  RF_DagNode_t    *node;
  RF_DagHeader_t  *newptr;
{
  int i;
  node->dagHdr = newptr;
  for (i=0; i<node->numSuccedents; i++)
    if (node->succedents[i]->dagHdr != newptr)
      rf_RecurResetDAGHeaderPointers(node->succedents[i], newptr);
}


void rf_PrintDAGList(RF_DagHeader_t *dag_h)
{
  int i=0;

  for (; dag_h; dag_h=dag_h->next) {
    rf_AssignNodeNums(dag_h);
    printf("\n\nDAG %d IN LIST:\n",i++);
    rf_PrintDAG(dag_h);
  }
}

static int rf_ValidateBranch(node, scount, acount, nodes, unvisited)
  RF_DagNode_t   *node;
  int            *scount;
  int            *acount;
  RF_DagNode_t  **nodes;
  int             unvisited;
{
  int i, retcode = 0;

  /* construct an array of node pointers indexed by node num */
  node->visited = (unvisited) ? 0 : 1;
  nodes[ node->nodeNum ] = node;

  if (node->next != NULL) {
    printf("INVALID DAG: next pointer in node is not NULL\n");
    retcode = 1;
  }
  if (node->status != rf_wait) {
    printf("INVALID DAG: Node status is not wait\n");
    retcode = 1;
  }
  if (node->numAntDone != 0) {
    printf("INVALID DAG: numAntDone is not zero\n");
    retcode = 1;
  }
  if (node->doFunc == rf_TerminateFunc) {
    if (node->numSuccedents != 0) {
      printf("INVALID DAG: Terminator node has succedents\n");
      retcode = 1;
    }
  } else {
    if (node->numSuccedents == 0) {
      printf("INVALID DAG: Non-terminator node has no succedents\n");
      retcode = 1;
    }
  }
  for (i=0; i<node->numSuccedents; i++)  {
    if (!node->succedents[i]) {
      printf("INVALID DAG: succedent %d of node %s is NULL\n",i,node->name);
      retcode = 1;
    }
    scount[ node->succedents[i]->nodeNum ]++;
  }
  for (i=0; i<node->numAntecedents; i++) {
    if (!node->antecedents[i]) {
      printf("INVALID DAG: antecedent %d of node %s is NULL\n",i,node->name);