sys/dev/raidframe/rf_dagutils.c

   1 /*      $NetBSD: rf_dagutils.c,v 1.6 1999/12/09 02:26:09 oster Exp $    */
   2
   3 #include <sys/cdefs.h>
   4 __FBSDID("$FreeBSD$");
   5 /*
   6  * Copyright (c) 1995 Carnegie-Mellon University.
   7  * All rights reserved.
   8  *
   9  * Authors: Mark Holland, William V. Courtright II, Jim Zelenka
  10  *
  11  * Permission to use, copy, modify and distribute this software and
  12  * its documentation is hereby granted, provided that both the copyright
  13  * notice and this permission notice appear in all copies of the
  14  * software, derivative works or modified versions, and any portions
  15  * thereof, and that both notices appear in supporting documentation.
  16  *
  17  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  18  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
  19  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  20  *
  21  * Carnegie Mellon requests users of this software to return to
  22  *
  23  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  24  *  School of Computer Science
  25  *  Carnegie Mellon University
  26  *  Pittsburgh PA 15213-3890
  27  *
  28  * any improvements or extensions that they make and grant Carnegie the
  29  * rights to redistribute these changes.
  30  */
  31
  32 /******************************************************************************
  33  *
  34  * rf_dagutils.c -- utility routines for manipulating dags
  35  *
  36  *****************************************************************************/
  37
  38 #include <dev/raidframe/rf_archs.h>
  39 #include <dev/raidframe/rf_types.h>
  40 #include <dev/raidframe/rf_threadstuff.h>
  41 #include <dev/raidframe/rf_raid.h>
  42 #include <dev/raidframe/rf_dag.h>
  43 #include <dev/raidframe/rf_dagutils.h>
  44 #include <dev/raidframe/rf_dagfuncs.h>
  45 #include <dev/raidframe/rf_general.h>
  46 #include <dev/raidframe/rf_freelist.h>
  47 #include <dev/raidframe/rf_map.h>
  48 #include <dev/raidframe/rf_shutdown.h>
  49
  50 #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
  51
  52 RF_RedFuncs_t rf_xorFuncs = {
  53         rf_RegularXorFunc, "Reg Xr",
  54 rf_SimpleXorFunc, "Simple Xr"};
  55
  56 RF_RedFuncs_t rf_xorRecoveryFuncs = {
  57         rf_RecoveryXorFunc, "Recovery Xr",
  58 rf_RecoveryXorFunc, "Recovery Xr"};
  59
  60 static void rf_RecurPrintDAG(RF_DagNode_t *, int, int);
  61 static void rf_PrintDAG(RF_DagHeader_t *);
  62 static int
  63 rf_ValidateBranch(RF_DagNode_t *, int *, int *,
  64     RF_DagNode_t **, int);
  65 static void rf_ValidateBranchVisitedBits(RF_DagNode_t *, int, int);
  66 static void rf_ValidateVisitedBits(RF_DagHeader_t *);
  67
  68 /******************************************************************************
  69  *
  70  * InitNode - initialize a dag node
  71  *
  72  * the size of the propList array is always the same as that of the
  73  * successors array.
  74  *
  75  *****************************************************************************/
  76 void
  77 rf_InitNode(
  78     RF_DagNode_t * node,
  79     RF_NodeStatus_t initstatus,
  80     int commit,
  81     int (*doFunc) (RF_DagNode_t * node),
  82     int (*undoFunc) (RF_DagNode_t * node),
  83     int (*wakeFunc) (RF_DagNode_t * node, int status),
  84     int nSucc,
  85     int nAnte,
  86     int nParam,
  87     int nResult,
  88     RF_DagHeader_t * hdr,
  89     char *name,
  90     RF_AllocListElem_t * alist)
  91 {
  92         void  **ptrs;
  93         int     nptrs;
  94
  95         if (nAnte > RF_MAX_ANTECEDENTS)
  96                 RF_PANIC();
  97         node->status = initstatus;
  98         node->commitNode = commit;
  99         node->doFunc = doFunc;
 100         node->undoFunc = undoFunc;
 101         node->wakeFunc = wakeFunc;
 102         node->numParams = nParam;
 103         node->numResults = nResult;
 104         node->numAntecedents = nAnte;
 105         node->numAntDone = 0;
 106         node->next = NULL;
 107         node->numSuccedents = nSucc;
 108         node->name = name;
 109         node->dagHdr = hdr;
 110         node->visited = 0;
 111
 112         /* allocate all the pointers with one call to malloc */
 113         nptrs = nSucc + nAnte + nResult + nSucc;
 114
 115         if (nptrs <= RF_DAG_PTRCACHESIZE) {
 116                 /*
 117                  * The dag_ptrs field of the node is basically some scribble
 118                  * space to be used here. We could get rid of it, and always
 119                  * allocate the range of pointers, but that's expensive. So,
 120                  * we pick a "common case" size for the pointer cache. Hopefully,
 121                  * we'll find that:
 122                  * (1) Generally, nptrs doesn't exceed RF_DAG_PTRCACHESIZE by
 123                  *     only a little bit (least efficient case)
 124                  * (2) Generally, ntprs isn't a lot less than RF_DAG_PTRCACHESIZE
 125                  *     (wasted memory)
 126                  */
 127                 ptrs = (void **) node->dag_ptrs;
 128         } else {
 129                 RF_CallocAndAdd(ptrs, nptrs, sizeof(void *), (void **), alist);
 130         }
 131         node->succedents = (nSucc) ? (RF_DagNode_t **) ptrs : NULL;
 132         node->antecedents = (nAnte) ? (RF_DagNode_t **) (ptrs + nSucc) : NULL;
 133         node->results = (nResult) ? (void **) (ptrs + nSucc + nAnte) : NULL;
 134         node->propList = (nSucc) ? (RF_PropHeader_t **) (ptrs + nSucc + nAnte + nResult) : NULL;
 135
 136         if (nParam) {
 137                 if (nParam <= RF_DAG_PARAMCACHESIZE) {
 138                         node->params = (RF_DagParam_t *) node->dag_params;
 139                 } else {
 140                         RF_CallocAndAdd(node->params, nParam, sizeof(RF_DagParam_t), (RF_DagParam_t *), alist);
 141                 }
 142         } else {
 143                 node->params = NULL;
 144         }
 145 }
 146
 147
 148
 149 /******************************************************************************
 150  *
 151  * allocation and deallocation routines
 152  *
 153  *****************************************************************************/
 154
 155 void
 156 rf_FreeDAG(dag_h)
 157         RF_DagHeader_t *dag_h;
 158 {
 159         RF_AccessStripeMapHeader_t *asmap, *t_asmap;
 160         RF_DagHeader_t *nextDag;
 161         int     i;
 162
 163         while (dag_h) {
 164                 nextDag = dag_h->next;
 165                 for (i = 0; dag_h->memChunk[i] && i < RF_MAXCHUNKS; i++) {
 166                         /* release mem chunks */
 167                         rf_ReleaseMemChunk(dag_h->memChunk[i]);
 168                         dag_h->memChunk[i] = NULL;
 169                 }
 170
 171                 RF_ASSERT(i == dag_h->chunkIndex);
 172                 if (dag_h->xtraChunkCnt > 0) {
 173                         /* free xtraMemChunks */
 174                         for (i = 0; dag_h->xtraMemChunk[i] && i < dag_h->xtraChunkIndex; i++) {
 175                                 rf_ReleaseMemChunk(dag_h->xtraMemChunk[i]);
 176                                 dag_h->xtraMemChunk[i] = NULL;
 177                         }
 178                         RF_ASSERT(i == dag_h->xtraChunkIndex);
 179                         /* free ptrs to xtraMemChunks */
 180                         RF_Free(dag_h->xtraMemChunk, dag_h->xtraChunkCnt * sizeof(RF_ChunkDesc_t *));
 181                 }
 182                 rf_FreeAllocList(dag_h->allocList);
 183                 for (asmap = dag_h->asmList; asmap;) {
 184                         t_asmap = asmap;
 185                         asmap = asmap->next;
 186                         rf_FreeAccessStripeMap(t_asmap);
 187                 }
 188                 rf_FreeDAGHeader(dag_h);
 189                 dag_h = nextDag;
 190         }
 191 }
 192
 193 RF_PropHeader_t *
 194 rf_MakePropListEntry(
 195     RF_DagHeader_t * dag_h,
 196     int resultNum,
 197     int paramNum,
 198     RF_PropHeader_t * next,
 199     RF_AllocListElem_t * allocList)
 200 {
 201         RF_PropHeader_t *p;
 202
 203         RF_CallocAndAdd(p, 1, sizeof(RF_PropHeader_t),
 204             (RF_PropHeader_t *), allocList);
 205         p->resultNum = resultNum;
 206         p->paramNum = paramNum;
 207         p->next = next;
 208         return (p);
 209 }
 210
 211 static RF_FreeList_t *rf_dagh_freelist;
 212
 213 #define RF_MAX_FREE_DAGH 128
 214 #define RF_DAGH_INC       16
 215 #define RF_DAGH_INITIAL   32
 216
 217 static void rf_ShutdownDAGs(void *);
 218 static void
 219 rf_ShutdownDAGs(ignored)
 220         void   *ignored;
 221 {
 222         RF_FREELIST_DESTROY(rf_dagh_freelist, next, (RF_DagHeader_t *));
 223 }
 224
 225 int
 226 rf_ConfigureDAGs(listp)
 227         RF_ShutdownList_t **listp;
 228 {
 229         int     rc;
 230
 231         RF_FREELIST_CREATE(rf_dagh_freelist, RF_MAX_FREE_DAGH,
 232             RF_DAGH_INC, sizeof(RF_DagHeader_t));
 233         if (rf_dagh_freelist == NULL)
 234                 return (ENOMEM);
 235         rc = rf_ShutdownCreate(listp, rf_ShutdownDAGs, NULL);
 236         if (rc) {
 237                 RF_ERRORMSG3("Unable to add to shutdown list file %s line %d rc=%d\n",
 238                     __FILE__, __LINE__, rc);
 239                 rf_ShutdownDAGs(NULL);
 240                 return (rc);
 241         }
 242         RF_FREELIST_PRIME(rf_dagh_freelist, RF_DAGH_INITIAL, next,
 243             (RF_DagHeader_t *));
 244         return (0);
 245 }
 246
 247 RF_DagHeader_t *
 248 rf_AllocDAGHeader()
 249 {
 250         RF_DagHeader_t *dh;
 251
 252         RF_FREELIST_GET(rf_dagh_freelist, dh, next, (RF_DagHeader_t *));
 253         if (dh) {
 254                 bzero((char *) dh, sizeof(RF_DagHeader_t));
 255         }
 256         return (dh);
 257 }
 258
 259 void
 260 rf_FreeDAGHeader(RF_DagHeader_t * dh)
 261 {
 262         RF_FREELIST_FREE(rf_dagh_freelist, dh, next);
 263 }
 264 /* allocates a buffer big enough to hold the data described by pda */
 265 void   *
 266 rf_AllocBuffer(
 267     RF_Raid_t * raidPtr,
 268     RF_DagHeader_t * dag_h,
 269     RF_PhysDiskAddr_t * pda,
 270     RF_AllocListElem_t * allocList)
 271 {
 272         char   *p;
 273
 274         RF_MallocAndAdd(p, pda->numSector << raidPtr->logBytesPerSector,
 275             (char *), allocList);
 276         return ((void *) p);
 277 }
 278 /******************************************************************************
 279  *
 280  * debug routines
 281  *
 282  *****************************************************************************/
 283
 284 char   *
 285 rf_NodeStatusString(RF_DagNode_t * node)
 286 {
 287         switch (node->status) {
 288                 case rf_wait:return ("wait");
 289         case rf_fired:
 290                 return ("fired");
 291         case rf_good:
 292                 return ("good");
 293         case rf_bad:
 294                 return ("bad");
 295         default:
 296                 return ("?");
 297         }
 298 }
 299
 300 void
 301 rf_PrintNodeInfoString(RF_DagNode_t * node)
 302 {
 303         RF_PhysDiskAddr_t *pda;
 304         int     (*df) (RF_DagNode_t *) = node->doFunc;
 305         int     i, lk, unlk;
 306         void   *bufPtr;
 307
 308         if ((df == rf_DiskReadFunc) || (df == rf_DiskWriteFunc)
 309             || (df == rf_DiskReadMirrorIdleFunc)
 310             || (df == rf_DiskReadMirrorPartitionFunc)) {
 311                 pda = (RF_PhysDiskAddr_t *) node->params[0].p;
 312                 bufPtr = (void *) node->params[1].p;
 313                 lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
 314                 unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
 315                 RF_ASSERT(!(lk && unlk));
 316                 printf("r %d c %d offs %ld nsect %d buf 0x%lx %s\n", pda->row, pda->col,
 317                     (long) pda->startSector, (int) pda->numSector, (long) bufPtr,
 318                     (lk) ? "LOCK" : ((unlk) ? "UNLK" : " "));
 319                 return;
 320         }
 321         if (df == rf_DiskUnlockFunc) {
 322                 pda = (RF_PhysDiskAddr_t *) node->params[0].p;
 323                 lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
 324                 unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
 325                 RF_ASSERT(!(lk && unlk));
 326                 printf("r %d c %d %s\n", pda->row, pda->col,
 327                     (lk) ? "LOCK" : ((unlk) ? "UNLK" : "nop"));
 328                 return;
 329         }
 330         if ((df == rf_SimpleXorFunc) || (df == rf_RegularXorFunc)
 331             || (df == rf_RecoveryXorFunc)) {
 332                 printf("result buf 0x%lx\n", (long) node->results[0]);
 333                 for (i = 0; i < node->numParams - 1; i += 2) {
 334                         pda = (RF_PhysDiskAddr_t *) node->params[i].p;
 335                         bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p;
 336                         printf("    buf 0x%lx r%d c%d offs %ld nsect %d\n",
 337                             (long) bufPtr, pda->row, pda->col,
 338                             (long) pda->startSector, (int) pda->numSector);
 339                 }
 340                 return;
 341         }
 342 #if RF_INCLUDE_PARITYLOGGING > 0
 343         if (df == rf_ParityLogOverwriteFunc || df == rf_ParityLogUpdateFunc) {
 344                 for (i = 0; i < node->numParams - 1; i += 2) {
 345                         pda = (RF_PhysDiskAddr_t *) node->params[i].p;
 346                         bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p;
 347                         printf(" r%d c%d offs %ld nsect %d buf 0x%lx\n",
 348                             pda->row, pda->col, (long) pda->startSector,
 349                             (int) pda->numSector, (long) bufPtr);
 350                 }
 351                 return;
 352         }
 353 #endif                          /* RF_INCLUDE_PARITYLOGGING > 0 */
 354
 355         if ((df == rf_TerminateFunc) || (df == rf_NullNodeFunc)) {
 356                 printf("\n");
 357                 return;
 358         }
 359         printf("?\n");
 360 }
 361
 362 static void
 363 rf_RecurPrintDAG(node, depth, unvisited)
 364         RF_DagNode_t *node;
 365         int     depth;
 366         int     unvisited;
 367 {
 368         char   *anttype;
 369         int     i;
 370
 371         node->visited = (unvisited) ? 0 : 1;
 372         printf("(%d) %d C%d %s: %s,s%d %d/%d,a%d/%d,p%d,r%d S{", depth,
 373             node->nodeNum, node->commitNode, node->name, rf_NodeStatusString(node),
 374             node->numSuccedents, node->numSuccFired, node->numSuccDone,
 375             node->numAntecedents, node->numAntDone, node->numParams, node->numResults);
 376         for (i = 0; i < node->numSuccedents; i++) {
 377                 printf("%d%s", node->succedents[i]->nodeNum,
 378                     ((i == node->numSuccedents - 1) ? "\0" : " "));
 379         }
 380         printf("} A{");
 381         for (i = 0; i < node->numAntecedents; i++) {
 382                 switch (node->antType[i]) {
 383                 case rf_trueData:
 384                         anttype = "T";
 385                         break;
 386                 case rf_antiData:
 387                         anttype = "A";
 388                         break;
 389                 case rf_outputData:
 390                         anttype = "O";
 391                         break;
 392                 case rf_control:
 393                         anttype = "C";
 394                         break;
 395                 default:
 396                         anttype = "?";
 397                         break;
 398                 }
 399                 printf("%d(%s)%s", node->antecedents[i]->nodeNum, anttype, (i == node->numAntecedents - 1) ? "\0" : " ");
 400         }
 401         printf("}; ");
 402         rf_PrintNodeInfoString(node);
 403         for (i = 0; i < node->numSuccedents; i++) {
 404                 if (node->succedents[i]->visited == unvisited)
 405                         rf_RecurPrintDAG(node->succedents[i], depth + 1, unvisited);
 406         }
 407 }
 408
 409 static void
 410 rf_PrintDAG(dag_h)
 411         RF_DagHeader_t *dag_h;
 412 {
 413         int     unvisited, i;
 414         char   *status;
 415
 416         /* set dag status */
 417         switch (dag_h->status) {
 418         case rf_enable:
 419                 status = "enable";
 420                 break;
 421         case rf_rollForward:
 422                 status = "rollForward";
 423                 break;
 424         case rf_rollBackward:
 425                 status = "rollBackward";
 426                 break;
 427         default:
 428                 status = "illegal!";
 429                 break;
 430         }
 431         /* find out if visited bits are currently set or clear */
 432         unvisited = dag_h->succedents[0]->visited;
 433
 434         printf("DAG type:  %s\n", dag_h->creator);
 435         printf("format is (depth) num commit type: status,nSucc nSuccFired/nSuccDone,nAnte/nAnteDone,nParam,nResult S{x} A{x(type)};  info\n");
 436         printf("(0) %d Hdr: %s, s%d, (commit %d/%d) S{", dag_h->nodeNum,
 437             status, dag_h->numSuccedents, dag_h->numCommitNodes, dag_h->numCommits);
 438         for (i = 0; i < dag_h->numSuccedents; i++) {
 439                 printf("%d%s", dag_h->succedents[i]->nodeNum,
 440                     ((i == dag_h->numSuccedents - 1) ? "\0" : " "));
 441         }
 442         printf("};\n");
 443         for (i = 0; i < dag_h->numSuccedents; i++) {
 444                 if (dag_h->succedents[i]->visited == unvisited)
 445                         rf_RecurPrintDAG(dag_h->succedents[i], 1, unvisited);
 446         }
 447 }
 448 /* assigns node numbers */
 449 int
 450 rf_AssignNodeNums(RF_DagHeader_t * dag_h)
 451 {
 452         int     unvisited, i, nnum;
 453         RF_DagNode_t *node;
 454
 455         nnum = 0;
 456         unvisited = dag_h->succedents[0]->visited;
 457
 458         dag_h->nodeNum = nnum++;
 459         for (i = 0; i < dag_h->numSuccedents; i++) {
 460                 node = dag_h->succedents[i];
 461                 if (node->visited == unvisited) {
 462                         nnum = rf_RecurAssignNodeNums(dag_h->succedents[i], nnum, unvisited);
 463                 }
 464         }
 465         return (nnum);
 466 }
 467
 468 int
 469 rf_RecurAssignNodeNums(node, num, unvisited)
 470         RF_DagNode_t *node;
 471         int     num;
 472         int     unvisited;
 473 {
 474         int     i;
 475
 476         node->visited = (unvisited) ? 0 : 1;
 477
 478         node->nodeNum = num++;
 479         for (i = 0; i < node->numSuccedents; i++) {
 480                 if (node->succedents[i]->visited == unvisited) {
 481                         num = rf_RecurAssignNodeNums(node->succedents[i], num, unvisited);
 482                 }
 483         }
 484         return (num);
 485 }
 486 /* set the header pointers in each node to "newptr" */
 487 void
 488 rf_ResetDAGHeaderPointers(dag_h, newptr)
 489         RF_DagHeader_t *dag_h;
 490         RF_DagHeader_t *newptr;
 491 {
 492         int     i;
 493         for (i = 0; i < dag_h->numSuccedents; i++)
 494                 if (dag_h->succedents[i]->dagHdr != newptr)
 495                         rf_RecurResetDAGHeaderPointers(dag_h->succedents[i], newptr);
 496 }
 497
 498 void
 499 rf_RecurResetDAGHeaderPointers(node, newptr)
 500         RF_DagNode_t *node;
 501         RF_DagHeader_t *newptr;
 502 {
 503         int     i;
 504         node->dagHdr = newptr;
 505         for (i = 0; i < node->numSuccedents; i++)
 506                 if (node->succedents[i]->dagHdr != newptr)
 507                         rf_RecurResetDAGHeaderPointers(node->succedents[i], newptr);
 508 }
 509
 510
 511 void
 512 rf_PrintDAGList(RF_DagHeader_t * dag_h)
 513 {
 514         int     i = 0;
 515
 516         for (; dag_h; dag_h = dag_h->next) {
 517                 rf_AssignNodeNums(dag_h);
 518                 printf("\n\nDAG %d IN LIST:\n", i++);
 519                 rf_PrintDAG(dag_h);
 520         }
 521 }
 522
 523 static int
 524 rf_ValidateBranch(node, scount, acount, nodes, unvisited)
 525         RF_DagNode_t *node;
 526         int    *scount;
 527         int    *acount;
 528         RF_DagNode_t **nodes;
 529         int     unvisited;
 530 {
 531         int     i, retcode = 0;
 532
 533         /* construct an array of node pointers indexed by node num */
 534         node->visited = (unvisited) ? 0 : 1;
 535         nodes[node->nodeNum] = node;
 536
 537         if (node->next != NULL) {
 538                 printf("INVALID DAG: next pointer in node is not NULL\n");
 539                 retcode = 1;
 540         }
 541         if (node->status != rf_wait) {
 542                 printf("INVALID DAG: Node status is not wait\n");
 543                 retcode = 1;
 544         }
 545         if (node->numAntDone != 0) {
 546                 printf("INVALID DAG: numAntDone is not zero\n");
 547                 retcode = 1;
 548         }
 549         if (node->doFunc == rf_TerminateFunc) {
 550                 if (node->numSuccedents != 0) {
 551                         printf("INVALID DAG: Terminator node has succedents\n");
 552                         retcode = 1;
 553                 }
 554         } else {
 555                 if (node->numSuccedents == 0) {
 556                         printf("INVALID DAG: Non-terminator node has no succedents\n");
 557                         retcode = 1;
 558                 }
 559         }
 560         for (i = 0; i < node->numSuccedents; i++) {
 561                 if (!node->succedents[i]) {
 562                         printf("INVALID DAG: succedent %d of node %s is NULL\n", i, node->name);
 563                         retcode = 1;
 564                 }
 565                 scount[node->succedents[i]->nodeNum]++;
 566         }
 567         for (i = 0; i < node->numAntecedents; i++) {
 568                 if (!node->antecedents[i]) {
 569                         printf("INVALID DAG: antecedent %d of node %s is NULL\n", i, node->name);
 570                         retcode = 1;
 571                 }
 572                 acount[node->antecedents[i]->nodeNum]++;
 573         }
 574         for (i = 0; i < node->numSuccedents; i++) {
 575                 if (node->succedents[i]->visited == unvisited) {
 576                         if (rf_ValidateBranch(node->succedents[i], scount,
 577                                 acount, nodes, unvisited)) {
 578                                 retcode = 1;
 579                         }
 580                 }
 581         }
 582         return (retcode);
 583 }
 584
 585 static void
 586 rf_ValidateBranchVisitedBits(node, unvisited, rl)
 587         RF_DagNode_t *node;
 588         int     unvisited;
 589         int     rl;
 590 {
 591         int     i;
 592
 593         RF_ASSERT(node->visited == unvisited);
 594         for (i = 0; i < node->numSuccedents; i++) {
 595                 if (node->succedents[i] == NULL) {
 596                         printf("node=%lx node->succedents[%d] is NULL\n", (long) node, i);
 597                         RF_ASSERT(0);
 598                 }
 599                 rf_ValidateBranchVisitedBits(node->succedents[i], unvisited, rl + 1);
 600         }
 601 }
 602 /* NOTE:  never call this on a big dag, because it is exponential
 603  * in execution time
 604  */
 605 static void
 606 rf_ValidateVisitedBits(dag)
 607         RF_DagHeader_t *dag;
 608 {
 609         int     i, unvisited;
 610
 611         unvisited = dag->succedents[0]->visited;
 612
 613         for (i = 0; i < dag->numSuccedents; i++) {
 614                 if (dag->succedents[i] == NULL) {
 615                         printf("dag=%lx dag->succedents[%d] is NULL\n", (long) dag, i);
 616                         RF_ASSERT(0);
 617                 }
 618                 rf_ValidateBranchVisitedBits(dag->succedents[i], unvisited, 0);
 619         }
 620 }
 621 /* validate a DAG.  _at entry_ verify that:
 622  *   -- numNodesCompleted is zero
 623  *   -- node queue is null
 624  *   -- dag status is rf_enable
 625  *   -- next pointer is null on every node
 626  *   -- all nodes have status wait
 627  *   -- numAntDone is zero in all nodes
 628  *   -- terminator node has zero successors
 629  *   -- no other node besides terminator has zero successors
 630  *   -- no successor or antecedent pointer in a node is NULL
 631  *   -- number of times that each node appears as a successor of another node
 632  *      is equal to the antecedent count on that node
 633  *   -- number of times that each node appears as an antecedent of another node
 634  *      is equal to the succedent count on that node
 635  *   -- what else?
 636  */
 637 int
 638 rf_ValidateDAG(dag_h)
 639         RF_DagHeader_t *dag_h;
 640 {
 641         int     i, nodecount;
 642         int    *scount, *acount;/* per-node successor and antecedent counts */
 643         RF_DagNode_t **nodes;   /* array of ptrs to nodes in dag */
 644         int     retcode = 0;
 645         int     unvisited;
 646         int     commitNodeCount = 0;
 647
 648         if (rf_validateVisitedDebug)
 649                 rf_ValidateVisitedBits(dag_h);
 650
 651         if (dag_h->numNodesCompleted != 0) {
 652                 printf("INVALID DAG: num nodes completed is %d, should be 0\n", dag_h->numNodesCompleted);
 653                 retcode = 1;
 654                 goto validate_dag_bad;
 655         }
 656         if (dag_h->status != rf_enable) {
 657                 printf("INVALID DAG: not enabled\n");
 658                 retcode = 1;
 659                 goto validate_dag_bad;
 660         }
 661         if (dag_h->numCommits != 0) {
 662                 printf("INVALID DAG: numCommits != 0 (%d)\n", dag_h->numCommits);
 663                 retcode = 1;
 664                 goto validate_dag_bad;
 665         }
 666         if (dag_h->numSuccedents != 1) {
 667                 /* currently, all dags must have only one succedent */
 668                 printf("INVALID DAG: numSuccedents !1 (%d)\n", dag_h->numSuccedents);
 669                 retcode = 1;
 670                 goto validate_dag_bad;
 671         }
 672         nodecount = rf_AssignNodeNums(dag_h);
 673
 674         unvisited = dag_h->succedents[0]->visited;
 675
 676         RF_Calloc(scount, nodecount, sizeof(int), (int *));
 677         RF_Calloc(acount, nodecount, sizeof(int), (int *));
 678         RF_Calloc(nodes, nodecount, sizeof(RF_DagNode_t *), (RF_DagNode_t **));
 679         for (i = 0; i < dag_h->numSuccedents; i++) {
 680                 if ((dag_h->succedents[i]->visited == unvisited)
 681                     && rf_ValidateBranch(dag_h->succedents[i], scount,
 682                         acount, nodes, unvisited)) {
 683                         retcode = 1;
 684                 }
 685         }
 686         /* start at 1 to skip the header node */
 687         for (i = 1; i < nodecount; i++) {
 688                 if (nodes[i]->commitNode)
 689                         commitNodeCount++;
 690                 if (nodes[i]->doFunc == NULL) {
 691                         printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name);
 692                         retcode = 1;
 693                         goto validate_dag_out;
 694                 }
 695                 if (nodes[i]->undoFunc == NULL) {
 696                         printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name);
 697                         retcode = 1;
 698                         goto validate_dag_out;
 699                 }
 700                 if (nodes[i]->numAntecedents != scount[nodes[i]->nodeNum]) {
 701                         printf("INVALID DAG: node %s has %d antecedents but appears as a succedent %d times\n",
 702                             nodes[i]->name, nodes[i]->numAntecedents, scount[nodes[i]->nodeNum]);
 703                         retcode = 1;
 704                         goto validate_dag_out;
 705                 }
 706                 if (nodes[i]->numSuccedents != acount[nodes[i]->nodeNum]) {
 707                         printf("INVALID DAG: node %s has %d succedents but appears as an antecedent %d times\n",
 708                             nodes[i]->name, nodes[i]->numSuccedents, acount[nodes[i]->nodeNum]);
 709                         retcode = 1;
 710                         goto validate_dag_out;
 711                 }
 712         }
 713
 714         if (dag_h->numCommitNodes != commitNodeCount) {
 715                 printf("INVALID DAG: incorrect commit node count.  hdr->numCommitNodes (%d) found (%d) commit nodes in graph\n",
 716                     dag_h->numCommitNodes, commitNodeCount);
 717                 retcode = 1;
 718                 goto validate_dag_out;
 719         }
 720 validate_dag_out:
 721         RF_Free(scount, nodecount * sizeof(int));
 722         RF_Free(acount, nodecount * sizeof(int));
 723         RF_Free(nodes, nodecount * sizeof(RF_DagNode_t *));
 724         if (retcode)
 725                 rf_PrintDAGList(dag_h);
 726
 727         if (rf_validateVisitedDebug)
 728                 rf_ValidateVisitedBits(dag_h);
 729
 730         return (retcode);
 731
 732 validate_dag_bad:
 733         rf_PrintDAGList(dag_h);
 734         return (retcode);
 735 }
 736
 737
 738 /******************************************************************************
 739  *
 740  * misc construction routines
 741  *
 742  *****************************************************************************/
 743
 744 void
 745 rf_redirect_asm(
 746     RF_Raid_t * raidPtr,
 747     RF_AccessStripeMap_t * asmap)
 748 {
 749         int     ds = (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) ? 1 : 0;
 750         int     row = asmap->physInfo->row;
 751         int     fcol = raidPtr->reconControl[row]->fcol;
 752         int     srow = raidPtr->reconControl[row]->spareRow;
 753         int     scol = raidPtr->reconControl[row]->spareCol;
 754         RF_PhysDiskAddr_t *pda;
 755
 756         RF_ASSERT(raidPtr->status[row] == rf_rs_reconstructing);
 757         for (pda = asmap->physInfo; pda; pda = pda->next) {
 758                 if (pda->col == fcol) {
 759                         if (rf_dagDebug) {
 760                                 if (!rf_CheckRUReconstructed(raidPtr->reconControl[row]->reconMap,
 761                                         pda->startSector)) {
 762                                         RF_PANIC();
 763                                 }
 764                         }
 765                         /* printf("Remapped data for large write\n"); */
 766                         if (ds) {
 767                                 raidPtr->Layout.map->MapSector(raidPtr, pda->raidAddress,
 768                                     &pda->row, &pda->col, &pda->startSector, RF_REMAP);
 769                         } else {
 770                                 pda->row = srow;
 771                                 pda->col = scol;
 772                         }
 773                 }
 774         }
 775         for (pda = asmap->parityInfo; pda; pda = pda->next) {
 776                 if (pda->col == fcol) {
 777                         if (rf_dagDebug) {
 778                                 if (!rf_CheckRUReconstructed(raidPtr->reconControl[row]->reconMap, pda->startSector)) {
 779                                         RF_PANIC();
 780                                 }
 781                         }
 782                 }
 783                 if (ds) {
 784                         (raidPtr->Layout.map->MapParity) (raidPtr, pda->raidAddress, &pda->row, &pda->col, &pda->startSector, RF_REMAP);
 785                 } else {
 786                         pda->row = srow;
 787                         pda->col = scol;
 788                 }
 789         }
 790 }
 791
 792
 793 /* this routine allocates read buffers and generates stripe maps for the
 794  * regions of the array from the start of the stripe to the start of the
 795  * access, and from the end of the access to the end of the stripe.  It also
 796  * computes and returns the number of DAG nodes needed to read all this data.
 797  * Note that this routine does the wrong thing if the access is fully
 798  * contained within one stripe unit, so we RF_ASSERT against this case at the
 799  * start.
 800  */
 801 void
 802 rf_MapUnaccessedPortionOfStripe(
 803     RF_Raid_t * raidPtr,
 804     RF_RaidLayout_t * layoutPtr,/* in: layout information */
 805     RF_AccessStripeMap_t * asmap,       /* in: access stripe map */
 806     RF_DagHeader_t * dag_h,     /* in: header of the dag to create */
 807     RF_AccessStripeMapHeader_t ** new_asm_h,    /* in: ptr to array of 2
 808                                                  * headers, to be filled in */
 809     int *nRodNodes,             /* out: num nodes to be generated to read
 810                                  * unaccessed data */
 811     char **sosBuffer,           /* out: pointers to newly allocated buffer */
 812     char **eosBuffer,
 813     RF_AllocListElem_t * allocList)
 814 {
 815         RF_RaidAddr_t sosRaidAddress, eosRaidAddress;
 816         RF_SectorNum_t sosNumSector, eosNumSector;
 817
 818         RF_ASSERT(asmap->numStripeUnitsAccessed > (layoutPtr->numDataCol / 2));
 819         /* generate an access map for the region of the array from start of
 820          * stripe to start of access */
 821         new_asm_h[0] = new_asm_h[1] = NULL;
 822         *nRodNodes = 0;
 823         if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->raidAddress)) {
 824                 sosRaidAddress = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress);
 825                 sosNumSector = asmap->raidAddress - sosRaidAddress;
 826                 RF_MallocAndAdd(*sosBuffer, rf_RaidAddressToByte(raidPtr, sosNumSector), (char *), allocList);
 827                 new_asm_h[0] = rf_MapAccess(raidPtr, sosRaidAddress, sosNumSector, *sosBuffer, RF_DONT_REMAP);
 828                 new_asm_h[0]->next = dag_h->asmList;
 829                 dag_h->asmList = new_asm_h[0];
 830                 *nRodNodes += new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
 831
 832                 RF_ASSERT(new_asm_h[0]->stripeMap->next == NULL);
 833                 /* we're totally within one stripe here */
 834                 if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
 835                         rf_redirect_asm(raidPtr, new_asm_h[0]->stripeMap);
 836         }
 837         /* generate an access map for the region of the array from end of
 838          * access to end of stripe */
 839         if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->endRaidAddress)) {
 840                 eosRaidAddress = asmap->endRaidAddress;
 841                 eosNumSector = rf_RaidAddressOfNextStripeBoundary(layoutPtr, eosRaidAddress) - eosRaidAddress;
 842                 RF_MallocAndAdd(*eosBuffer, rf_RaidAddressToByte(raidPtr, eosNumSector), (char *), allocList);
 843                 new_asm_h[1] = rf_MapAccess(raidPtr, eosRaidAddress, eosNumSector, *eosBuffer, RF_DONT_REMAP);
 844                 new_asm_h[1]->next = dag_h->asmList;
 845                 dag_h->asmList = new_asm_h[1];
 846                 *nRodNodes += new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
 847
 848                 RF_ASSERT(new_asm_h[1]->stripeMap->next == NULL);
 849                 /* we're totally within one stripe here */
 850                 if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
 851                         rf_redirect_asm(raidPtr, new_asm_h[1]->stripeMap);
 852         }
 853 }
 854
 855
 856
 857 /* returns non-zero if the indicated ranges of stripe unit offsets overlap */
 858 int
 859 rf_PDAOverlap(
 860     RF_RaidLayout_t * layoutPtr,
 861     RF_PhysDiskAddr_t * src,
 862     RF_PhysDiskAddr_t * dest)
 863 {
 864         RF_SectorNum_t soffs = rf_StripeUnitOffset(layoutPtr, src->startSector);
 865         RF_SectorNum_t doffs = rf_StripeUnitOffset(layoutPtr, dest->startSector);
 866         /* use -1 to be sure we stay within SU */
 867         RF_SectorNum_t send = rf_StripeUnitOffset(layoutPtr, src->startSector + src->numSector - 1);
 868         RF_SectorNum_t dend = rf_StripeUnitOffset(layoutPtr, dest->startSector + dest->numSector - 1);
 869         return ((RF_MAX(soffs, doffs) <= RF_MIN(send, dend)) ? 1 : 0);
 870 }
 871
 872
 873 /* GenerateFailedAccessASMs
 874  *
 875  * this routine figures out what portion of the stripe needs to be read
 876  * to effect the degraded read or write operation.  It's primary function
 877  * is to identify everything required to recover the data, and then
 878  * eliminate anything that is already being accessed by the user.
 879  *
 880  * The main result is two new ASMs, one for the region from the start of the
 881  * stripe to the start of the access, and one for the region from the end of
 882  * the access to the end of the stripe.  These ASMs describe everything that
 883  * needs to be read to effect the degraded access.  Other results are:
 884  *    nXorBufs -- the total number of buffers that need to be XORed together to
 885  *                recover the lost data,
 886  *    rpBufPtr -- ptr to a newly-allocated buffer to hold the parity.  If NULL
 887  *                at entry, not allocated.
 888  *    overlappingPDAs --
 889  *                describes which of the non-failed PDAs in the user access
 890  *                overlap data that needs to be read to effect recovery.
 891  *                overlappingPDAs[i]==1 if and only if, neglecting the failed
 892  *                PDA, the ith pda in the input asm overlaps data that needs
 893  *                to be read for recovery.
 894  */
 895  /* in: asm - ASM for the actual access, one stripe only */
 896  /* in: faildPDA - which component of the access has failed */
 897  /* in: dag_h - header of the DAG we're going to create */
 898  /* out: new_asm_h - the two new ASMs */
 899  /* out: nXorBufs - the total number of xor bufs required */
 900  /* out: rpBufPtr - a buffer for the parity read */
 901 void
 902 rf_GenerateFailedAccessASMs(
 903     RF_Raid_t * raidPtr,
 904     RF_AccessStripeMap_t * asmap,
 905     RF_PhysDiskAddr_t * failedPDA,
 906     RF_DagHeader_t * dag_h,
 907     RF_AccessStripeMapHeader_t ** new_asm_h,
 908     int *nXorBufs,
 909     char **rpBufPtr,
 910     char *overlappingPDAs,
 911     RF_AllocListElem_t * allocList)
 912 {
 913         RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
 914
 915         /* s=start, e=end, s=stripe, a=access, f=failed, su=stripe unit */
 916         RF_RaidAddr_t sosAddr, sosEndAddr, eosStartAddr, eosAddr;
 917
 918         RF_SectorCount_t numSect[2], numParitySect;
 919         RF_PhysDiskAddr_t *pda;
 920         char   *rdBuf, *bufP;
 921         int     foundit, i;
 922
 923         bufP = NULL;
 924         foundit = 0;
 925         /* first compute the following raid addresses: start of stripe,
 926          * (sosAddr) MIN(start of access, start of failed SU),   (sosEndAddr)
 927          * MAX(end of access, end of failed SU),       (eosStartAddr) end of
 928          * stripe (i.e. start of next stripe)   (eosAddr) */
 929         sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress);
 930         sosEndAddr = RF_MIN(asmap->raidAddress, rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, failedPDA->raidAddress));
 931         eosStartAddr = RF_MAX(asmap->endRaidAddress, rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, failedPDA->raidAddress));
 932         eosAddr = rf_RaidAddressOfNextStripeBoundary(layoutPtr, asmap->raidAddress);
 933
 934         /* now generate access stripe maps for each of the above regions of
 935          * the stripe.  Use a dummy (NULL) buf ptr for now */
 936
 937         new_asm_h[0] = (sosAddr != sosEndAddr) ? rf_MapAccess(raidPtr, sosAddr, sosEndAddr - sosAddr, NULL, RF_DONT_REMAP) : NULL;
 938         new_asm_h[1] = (eosStartAddr != eosAddr) ? rf_MapAccess(raidPtr, eosStartAddr, eosAddr - eosStartAddr, NULL, RF_DONT_REMAP) : NULL;
 939
 940         /* walk through the PDAs and range-restrict each SU to the region of
 941          * the SU touched on the failed PDA.  also compute total data buffer
 942          * space requirements in this step.  Ignore the parity for now. */
 943
 944         numSect[0] = numSect[1] = 0;
 945         if (new_asm_h[0]) {
 946                 new_asm_h[0]->next = dag_h->asmList;
 947                 dag_h->asmList = new_asm_h[0];
 948                 for (pda = new_asm_h[0]->stripeMap->physInfo; pda; pda = pda->next) {
 949                         rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_NOBUFFER, 0);
 950                         numSect[0] += pda->numSector;
 951                 }
 952         }
 953         if (new_asm_h[1]) {
 954                 new_asm_h[1]->next = dag_h->asmList;
 955                 dag_h->asmList = new_asm_h[1];
 956                 for (pda = new_asm_h[1]->stripeMap->physInfo; pda; pda = pda->next) {
 957                         rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_NOBUFFER, 0);
 958                         numSect[1] += pda->numSector;
 959                 }
 960         }
 961         numParitySect = failedPDA->numSector;
 962
 963         /* allocate buffer space for the data & parity we have to read to
 964          * recover from the failure */
 965
 966         if (numSect[0] + numSect[1] + ((rpBufPtr) ? numParitySect : 0)) {       /* don't allocate parity
 967                                                                                  * buf if not needed */
 968                 RF_MallocAndAdd(rdBuf, rf_RaidAddressToByte(raidPtr, numSect[0] + numSect[1] + numParitySect), (char *), allocList);
 969                 bufP = rdBuf;
 970                 if (rf_degDagDebug)
 971                         printf("Newly allocated buffer (%d bytes) is 0x%lx\n",
 972                             (int) rf_RaidAddressToByte(raidPtr, numSect[0] + numSect[1] + numParitySect), (unsigned long) bufP);
 973         }
 974         /* now walk through the pdas one last time and assign buffer pointers
 975          * (ugh!).  Again, ignore the parity.  also, count nodes to find out
 976          * how many bufs need to be xored together */
 977         (*nXorBufs) = 1;        /* in read case, 1 is for parity.  In write
 978                                  * case, 1 is for failed data */
 979         if (new_asm_h[0]) {
 980                 for (pda = new_asm_h[0]->stripeMap->physInfo; pda; pda = pda->next) {
 981                         pda->bufPtr = bufP;
 982                         bufP += rf_RaidAddressToByte(raidPtr, pda->numSector);
 983                 }
 984                 *nXorBufs += new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
 985         }
 986         if (new_asm_h[1]) {
 987                 for (pda = new_asm_h[1]->stripeMap->physInfo; pda; pda = pda->next) {
 988                         pda->bufPtr = bufP;
 989                         bufP += rf_RaidAddressToByte(raidPtr, pda->numSector);
 990                 }
 991                 (*nXorBufs) += new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
 992         }
 993         if (rpBufPtr)
 994                 *rpBufPtr = bufP;       /* the rest of the buffer is for
 995                                          * parity */
 996
 997         /* the last step is to figure out how many more distinct buffers need
 998          * to get xor'd to produce the missing unit.  there's one for each
 999          * user-data read node that overlaps the portion of the failed unit
1000          * being accessed */
1001
1002         for (foundit = i = 0, pda = asmap->physInfo; pda; i++, pda = pda->next) {
1003                 if (pda == failedPDA) {
1004                         i--;
1005                         foundit = 1;
1006                         continue;
1007                 }
1008                 if (rf_PDAOverlap(layoutPtr, pda, failedPDA)) {
1009                         overlappingPDAs[i] = 1;
1010                         (*nXorBufs)++;
1011                 }
1012         }
1013         if (!foundit) {
1014                 RF_ERRORMSG("GenerateFailedAccessASMs: did not find failedPDA in asm list\n");
1015                 RF_ASSERT(0);
1016         }
1017         if (rf_degDagDebug) {
1018                 if (new_asm_h[0]) {
1019                         printf("First asm:\n");
1020                         rf_PrintFullAccessStripeMap(new_asm_h[0], 1);
1021                 }
1022                 if (new_asm_h[1]) {
1023                         printf("Second asm:\n");
1024                         rf_PrintFullAccessStripeMap(new_asm_h[1], 1);
1025                 }
1026         }
1027 }
1028
1029
1030 /* adjusts the offset and number of sectors in the destination pda so that
1031  * it covers at most the region of the SU covered by the source PDA.  This
1032  * is exclusively a restriction:  the number of sectors indicated by the
1033  * target PDA can only shrink.
1034  *
1035  * For example:  s = sectors within SU indicated by source PDA
1036  *               d = sectors within SU indicated by dest PDA
1037  *               r = results, stored in dest PDA
1038  *
1039  * |--------------- one stripe unit ---------------------|
1040  * |           sssssssssssssssssssssssssssssssss         |
1041  * |    ddddddddddddddddddddddddddddddddddddddddddddd    |
1042  * |           rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr         |
1043  *
1044  * Another example:
1045  *
1046  * |--------------- one stripe unit ---------------------|
1047  * |           sssssssssssssssssssssssssssssssss         |
1048  * |    ddddddddddddddddddddddd                          |
1049  * |           rrrrrrrrrrrrrrrr                          |
1050  *
1051  */
1052 void
1053 rf_RangeRestrictPDA(
1054     RF_Raid_t * raidPtr,
1055     RF_PhysDiskAddr_t * src,
1056     RF_PhysDiskAddr_t * dest,
1057     int dobuffer,
1058     int doraidaddr)
1059 {
1060         RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
1061         RF_SectorNum_t soffs = rf_StripeUnitOffset(layoutPtr, src->startSector);
1062         RF_SectorNum_t doffs = rf_StripeUnitOffset(layoutPtr, dest->startSector);
1063         RF_SectorNum_t send = rf_StripeUnitOffset(layoutPtr, src->startSector + src->numSector - 1);    /* use -1 to be sure we
1064                                                                                                          * stay within SU */
1065         RF_SectorNum_t dend = rf_StripeUnitOffset(layoutPtr, dest->startSector + dest->numSector - 1);
1066         RF_SectorNum_t subAddr = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, dest->startSector);  /* stripe unit boundary */
1067
1068         dest->startSector = subAddr + RF_MAX(soffs, doffs);
1069         dest->numSector = subAddr + RF_MIN(send, dend) + 1 - dest->startSector;
1070
1071         if (dobuffer)
1072                 dest->bufPtr += (soffs > doffs) ? rf_RaidAddressToByte(raidPtr, soffs - doffs) : 0;
1073         if (doraidaddr) {
1074                 dest->raidAddress = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, dest->raidAddress) +
1075                     rf_StripeUnitOffset(layoutPtr, dest->startSector);
1076         }
1077 }
1078 /*
1079  * Want the highest of these primes to be the largest one
1080  * less than the max expected number of columns (won't hurt
1081  * to be too small or too large, but won't be optimal, either)
1082  * --jimz
1083  */
1084 #define NLOWPRIMES 8
1085 static int lowprimes[NLOWPRIMES] = {2, 3, 5, 7, 11, 13, 17, 19};
1086 /*****************************************************************************
1087  * compute the workload shift factor.  (chained declustering)
1088  *
1089  * return nonzero if access should shift to secondary, otherwise,
1090  * access is to primary
1091  *****************************************************************************/
1092 int
1093 rf_compute_workload_shift(
1094     RF_Raid_t * raidPtr,
1095     RF_PhysDiskAddr_t * pda)
1096 {
1097         /*
1098          * variables:
1099          *  d   = column of disk containing primary
1100          *  f   = column of failed disk
1101          *  n   = number of disks in array
1102          *  sd  = "shift distance" (number of columns that d is to the right of f)
1103          *  row = row of array the access is in
1104          *  v   = numerator of redirection ratio
1105          *  k   = denominator of redirection ratio
1106          */
1107         RF_RowCol_t d, f, sd, row, n;
1108         int     k, v, ret, i;
1109
1110         row = pda->row;
1111         n = raidPtr->numCol;
1112
1113         /* assign column of primary copy to d */
1114         d = pda->col;
1115
1116         /* assign column of dead disk to f */
1117         for (f = 0; ((!RF_DEAD_DISK(raidPtr->Disks[row][f].status)) && (f < n)); f++);
1118
1119         RF_ASSERT(f < n);
1120         RF_ASSERT(f != d);
1121
1122         sd = (f > d) ? (n + d - f) : (d - f);
1123         RF_ASSERT(sd < n);
1124
1125         /*
1126          * v of every k accesses should be redirected
1127          *
1128          * v/k := (n-1-sd)/(n-1)
1129          */
1130         v = (n - 1 - sd);
1131         k = (n - 1);
1132
1133 #if 1
1134         /*
1135          * XXX
1136          * Is this worth it?
1137          *
1138          * Now reduce the fraction, by repeatedly factoring
1139          * out primes (just like they teach in elementary school!)
1140          */
1141         for (i = 0; i < NLOWPRIMES; i++) {
1142                 if (lowprimes[i] > v)
1143                         break;
1144                 while (((v % lowprimes[i]) == 0) && ((k % lowprimes[i]) == 0)) {
1145                         v /= lowprimes[i];
1146                         k /= lowprimes[i];
1147                 }
1148         }
1149 #endif
1150
1151         raidPtr->hist_diskreq[row][d]++;
1152         if (raidPtr->hist_diskreq[row][d] > v) {
1153                 ret = 0;        /* do not redirect */
1154         } else {
1155                 ret = 1;        /* redirect */
1156         }
1157
1158 #if 0
1159         printf("d=%d f=%d sd=%d v=%d k=%d ret=%d h=%d\n", d, f, sd, v, k, ret,
1160             raidPtr->hist_diskreq[row][d]);
1161 #endif
1162
1163         if (raidPtr->hist_diskreq[row][d] >= k) {
1164                 /* reset counter */
1165                 raidPtr->hist_diskreq[row][d] = 0;
1166         }
1167         return (ret);
1168 }
1169 /*
1170  * Disk selection routines
1171  */
1172
1173 /*
1174  * Selects the disk with the shortest queue from a mirror pair.
1175  * Both the disk I/Os queued in RAIDframe as well as those at the physical
1176  * disk are counted as members of the "queue"
1177  */
1178 void
1179 rf_SelectMirrorDiskIdle(RF_DagNode_t * node)
1180 {
1181         RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr;
1182         RF_RowCol_t rowData, colData, rowMirror, colMirror;
1183         int     dataQueueLength, mirrorQueueLength, usemirror;
1184         RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p;
1185         RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p;
1186         RF_PhysDiskAddr_t *tmp_pda;
1187         RF_RaidDisk_t **disks = raidPtr->Disks;
1188         RF_DiskQueue_t **dqs = raidPtr->Queues, *dataQueue, *mirrorQueue;
1189
1190         /* return the [row col] of the disk with the shortest queue */
1191         rowData = data_pda->row;
1192         colData = data_pda->col;
1193         rowMirror = mirror_pda->row;
1194         colMirror = mirror_pda->col;
1195         dataQueue = &(dqs[rowData][colData]);
1196         mirrorQueue = &(dqs[rowMirror][colMirror]);
1197
1198 #ifdef RF_LOCK_QUEUES_TO_READ_LEN
1199         RF_LOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle");
1200 #endif                          /* RF_LOCK_QUEUES_TO_READ_LEN */
1201         dataQueueLength = dataQueue->queueLength + dataQueue->numOutstanding;
1202 #ifdef RF_LOCK_QUEUES_TO_READ_LEN
1203         RF_UNLOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle");
1204         RF_LOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle");
1205 #endif                          /* RF_LOCK_QUEUES_TO_READ_LEN */
1206         mirrorQueueLength = mirrorQueue->queueLength + mirrorQueue->numOutstanding;
1207 #ifdef RF_LOCK_QUEUES_TO_READ_LEN
1208         RF_UNLOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle");
1209 #endif                          /* RF_LOCK_QUEUES_TO_READ_LEN */
1210
1211         usemirror = 0;
1212         if (RF_DEAD_DISK(disks[rowMirror][colMirror].status)) {
1213                 usemirror = 0;
1214         } else
1215                 if (RF_DEAD_DISK(disks[rowData][colData].status)) {
1216                         usemirror = 1;
1217                 } else
1218                         if (raidPtr->parity_good == RF_RAID_DIRTY) {
1219                                 /* Trust only the main disk */
1220                                 usemirror = 0;
1221                         } else
1222                                 if (dataQueueLength < mirrorQueueLength) {
1223                                         usemirror = 0;
1224                                 } else
1225                                         if (mirrorQueueLength < dataQueueLength) {
1226                                                 usemirror = 1;
1227                                         } else {
1228                                                 /* queues are equal length. attempt
1229                                                  * cleverness. */
1230                                                 if (SNUM_DIFF(dataQueue->last_deq_sector, data_pda->startSector)
1231                                                     <= SNUM_DIFF(mirrorQueue->last_deq_sector, mirror_pda->startSector)) {
1232                                                         usemirror = 0;
1233                                                 } else {
1234                                                         usemirror = 1;
1235                                                 }
1236                                         }
1237
1238         if (usemirror) {
1239                 /* use mirror (parity) disk, swap params 0 & 4 */
1240                 tmp_pda = data_pda;
1241                 node->params[0].p = mirror_pda;
1242                 node->params[4].p = tmp_pda;
1243         } else {
1244                 /* use data disk, leave param 0 unchanged */
1245         }
1246         /* printf("dataQueueLength %d, mirrorQueueLength
1247          * %d\n",dataQueueLength, mirrorQueueLength); */
1248 }
1249 /*
1250  * Do simple partitioning. This assumes that
1251  * the data and parity disks are laid out identically.
1252  */
1253 void
1254 rf_SelectMirrorDiskPartition(RF_DagNode_t * node)
1255 {
1256         RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr;
1257         RF_RowCol_t rowData, colData, rowMirror, colMirror;
1258         RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p;
1259         RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p;
1260         RF_PhysDiskAddr_t *tmp_pda;
1261         RF_RaidDisk_t **disks = raidPtr->Disks;
1262         RF_DiskQueue_t **dqs = raidPtr->Queues, *dataQueue, *mirrorQueue;
1263         int     usemirror;
1264
1265         /* return the [row col] of the disk with the shortest queue */
1266         rowData = data_pda->row;
1267         colData = data_pda->col;
1268         rowMirror = mirror_pda->row;
1269         colMirror = mirror_pda->col;
1270         dataQueue = &(dqs[rowData][colData]);
1271         mirrorQueue = &(dqs[rowMirror][colMirror]);
1272
1273         usemirror = 0;
1274         if (RF_DEAD_DISK(disks[rowMirror][colMirror].status)) {
1275                 usemirror = 0;
1276         } else
1277                 if (RF_DEAD_DISK(disks[rowData][colData].status)) {
1278                         usemirror = 1;
1279                 } else
1280                         if (raidPtr->parity_good == RF_RAID_DIRTY) {
1281                                 /* Trust only the main disk */
1282                                 usemirror = 0;
1283                         } else
1284                                 if (data_pda->startSector <
1285                                     (disks[rowData][colData].numBlocks / 2)) {
1286                                         usemirror = 0;
1287                                 } else {
1288                                         usemirror = 1;
1289                                 }
1290
1291         if (usemirror) {
1292                 /* use mirror (parity) disk, swap params 0 & 4 */
1293                 tmp_pda = data_pda;
1294                 node->params[0].p = mirror_pda;
1295                 node->params[4].p = tmp_pda;
1296         } else {
1297                 /* use data disk, leave param 0 unchanged */
1298         }
1299 }