sys/dev/raidframe/rf_dagutils.c

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