rf_dagdegwr.c revision 1.1
1/* $NetBSD: rf_dagdegwr.c,v 1.1 1998/11/13 04:20:27 oster Exp $ */ 2/* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Author: Mark Holland, Daniel Stodolsky, William V. Courtright II 7 * 8 * Permission to use, copy, modify and distribute this software and 9 * its documentation is hereby granted, provided that both the copyright 10 * notice and this permission notice appear in all copies of the 11 * software, derivative works or modified versions, and any portions 12 * thereof, and that both notices appear in supporting documentation. 13 * 14 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 15 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 16 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 17 * 18 * Carnegie Mellon requests users of this software to return to 19 * 20 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 21 * School of Computer Science 22 * Carnegie Mellon University 23 * Pittsburgh PA 15213-3890 24 * 25 * any improvements or extensions that they make and grant Carnegie the 26 * rights to redistribute these changes. 27 */ 28 29/* 30 * rf_dagdegwr.c 31 * 32 * code for creating degraded write DAGs 33 * 34 * : 35 * Log: rf_dagdegwr.c,v 36 * Revision 1.23 1996/11/05 21:10:40 jimz 37 * failed pda generalization 38 * 39 * Revision 1.22 1996/08/23 14:49:48 jimz 40 * remove bogus assert from small write double deg DAG generator 41 * 42 * Revision 1.21 1996/08/21 05:09:44 jimz 43 * get rid of bogus fakery in DoubleDegSmallWrite 44 * 45 * Revision 1.20 1996/08/21 04:14:35 jimz 46 * cleanup doubledegsmallwrite 47 * NOTE: we need doubledeglargewrite 48 * 49 * Revision 1.19 1996/08/19 21:39:38 jimz 50 * CommonCreateSimpleDegradedWriteDAG() was unable to correctly create DAGs for 51 * complete stripe overwrite accesses- it assumed the necessity to read old 52 * data. Rather than do the "right" thing, and risk breaking a critical DAG so 53 * close to release, I made a no-op read node to stick in and link up in this 54 * case. Seems to work. 55 * 56 * Revision 1.18 1996/07/31 15:35:34 jimz 57 * evenodd changes; bugfixes for double-degraded archs, generalize 58 * some formerly PQ-only functions 59 * 60 * Revision 1.17 1996/07/28 20:31:39 jimz 61 * i386netbsd port 62 * true/false fixup 63 * 64 * Revision 1.16 1996/07/27 23:36:08 jimz 65 * Solaris port of simulator 66 * 67 * Revision 1.15 1996/07/27 16:30:19 jimz 68 * cleanup sweep 69 * 70 * Revision 1.14 1996/07/22 19:52:16 jimz 71 * switched node params to RF_DagParam_t, a union of 72 * a 64-bit int and a void *, for better portability 73 * attempted hpux port, but failed partway through for 74 * lack of a single C compiler capable of compiling all 75 * source files 76 * 77 * Revision 1.13 1996/06/09 02:36:46 jimz 78 * lots of little crufty cleanup- fixup whitespace 79 * issues, comment #ifdefs, improve typing in some 80 * places (esp size-related) 81 * 82 * Revision 1.12 1996/06/07 22:26:27 jimz 83 * type-ify which_ru (RF_ReconUnitNum_t) 84 * 85 * Revision 1.11 1996/06/07 21:33:04 jimz 86 * begin using consistent types for sector numbers, 87 * stripe numbers, row+col numbers, recon unit numbers 88 * 89 * Revision 1.10 1996/05/31 22:26:54 jimz 90 * fix a lot of mapping problems, memory allocation problems 91 * found some weird lock issues, fixed 'em 92 * more code cleanup 93 * 94 * Revision 1.9 1996/05/30 11:29:41 jimz 95 * Numerous bug fixes. Stripe lock release code disagreed with the taking code 96 * about when stripes should be locked (I made it consistent: no parity, no lock) 97 * There was a lot of extra serialization of I/Os which I've removed- a lot of 98 * it was to calculate values for the cache code, which is no longer with us. 99 * More types, function, macro cleanup. Added code to properly quiesce the array 100 * on shutdown. Made a lot of stuff array-specific which was (bogusly) general 101 * before. Fixed memory allocation, freeing bugs. 102 * 103 * Revision 1.8 1996/05/27 18:56:37 jimz 104 * more code cleanup 105 * better typing 106 * compiles in all 3 environments 107 * 108 * Revision 1.7 1996/05/24 22:17:04 jimz 109 * continue code + namespace cleanup 110 * typed a bunch of flags 111 * 112 * Revision 1.6 1996/05/24 04:28:55 jimz 113 * release cleanup ckpt 114 * 115 * Revision 1.5 1996/05/23 21:46:35 jimz 116 * checkpoint in code cleanup (release prep) 117 * lots of types, function names have been fixed 118 * 119 * Revision 1.4 1996/05/23 00:33:23 jimz 120 * code cleanup: move all debug decls to rf_options.c, all extern 121 * debug decls to rf_options.h, all debug vars preceded by rf_ 122 * 123 * Revision 1.3 1996/05/18 19:51:34 jimz 124 * major code cleanup- fix syntax, make some types consistent, 125 * add prototypes, clean out dead code, et cetera 126 * 127 * Revision 1.2 1996/05/08 21:01:24 jimz 128 * fixed up enum type names that were conflicting with other 129 * enums and function names (ie, "panic") 130 * future naming trends will be towards RF_ and rf_ for 131 * everything raidframe-related 132 * 133 * Revision 1.1 1996/05/03 19:21:50 wvcii 134 * Initial revision 135 * 136 */ 137 138#include "rf_types.h" 139#include "rf_raid.h" 140#include "rf_dag.h" 141#include "rf_dagutils.h" 142#include "rf_dagfuncs.h" 143#include "rf_threadid.h" 144#include "rf_debugMem.h" 145#include "rf_memchunk.h" 146#include "rf_general.h" 147#include "rf_dagdegwr.h" 148#include "rf_sys.h" 149 150 151/****************************************************************************** 152 * 153 * General comments on DAG creation: 154 * 155 * All DAGs in this file use roll-away error recovery. Each DAG has a single 156 * commit node, usually called "Cmt." If an error occurs before the Cmt node 157 * is reached, the execution engine will halt forward execution and work 158 * backward through the graph, executing the undo functions. Assuming that 159 * each node in the graph prior to the Cmt node are undoable and atomic - or - 160 * does not make changes to permanent state, the graph will fail atomically. 161 * If an error occurs after the Cmt node executes, the engine will roll-forward 162 * through the graph, blindly executing nodes until it reaches the end. 163 * If a graph reaches the end, it is assumed to have completed successfully. 164 * 165 * A graph has only 1 Cmt node. 166 * 167 */ 168 169 170/****************************************************************************** 171 * 172 * The following wrappers map the standard DAG creation interface to the 173 * DAG creation routines. Additionally, these wrappers enable experimentation 174 * with new DAG structures by providing an extra level of indirection, allowing 175 * the DAG creation routines to be replaced at this single point. 176 */ 177 178static RF_CREATE_DAG_FUNC_DECL(rf_CreateSimpleDegradedWriteDAG) 179{ 180 rf_CommonCreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp, 181 flags, allocList,1, rf_RecoveryXorFunc, RF_TRUE); 182} 183 184void rf_CreateDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList) 185 RF_Raid_t *raidPtr; 186 RF_AccessStripeMap_t *asmap; 187 RF_DagHeader_t *dag_h; 188 void *bp; 189 RF_RaidAccessFlags_t flags; 190 RF_AllocListElem_t *allocList; 191{ 192 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 193 RF_PhysDiskAddr_t *failedPDA = asmap->failedPDAs[0]; 194 195 RF_ASSERT( asmap->numDataFailed == 1 ); 196 dag_h->creator = "DegradedWriteDAG"; 197 198 /* if the access writes only a portion of the failed unit, and also writes 199 * some portion of at least one surviving unit, we create two DAGs, one for 200 * the failed component and one for the non-failed component, and do them 201 * sequentially. Note that the fact that we're accessing only a portion of 202 * the failed unit indicates that the access either starts or ends in the 203 * failed unit, and hence we need create only two dags. This is inefficient 204 * in that the same data or parity can get read and written twice using this 205 * structure. I need to fix this to do the access all at once. 206 */ 207 RF_ASSERT(!(asmap->numStripeUnitsAccessed != 1 && failedPDA->numSector != layoutPtr->sectorsPerStripeUnit)); 208 rf_CreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList); 209} 210 211 212 213/****************************************************************************** 214 * 215 * DAG creation code begins here 216 */ 217 218 219 220/****************************************************************************** 221 * 222 * CommonCreateSimpleDegradedWriteDAG -- creates a DAG to do a degraded-mode 223 * write, which is as follows 224 * 225 * / {Wnq} --\ 226 * hdr -> blockNode -> Rod -> Xor -> Cmt -> Wnp ----> unblock -> term 227 * \ {Rod} / \ Wnd ---/ 228 * \ {Wnd} -/ 229 * 230 * commit nodes: Xor, Wnd 231 * 232 * IMPORTANT: 233 * This DAG generator does not work for double-degraded archs since it does not 234 * generate Q 235 * 236 * This dag is essentially identical to the large-write dag, except that the 237 * write to the failed data unit is suppressed. 238 * 239 * IMPORTANT: this dag does not work in the case where the access writes only 240 * a portion of the failed unit, and also writes some portion of at least one 241 * surviving SU. this case is handled in CreateDegradedWriteDAG above. 242 * 243 * The block & unblock nodes are leftovers from a previous version. They 244 * do nothing, but I haven't deleted them because it would be a tremendous 245 * effort to put them back in. 246 * 247 * This dag is used whenever a one of the data units in a write has failed. 248 * If it is the parity unit that failed, the nonredundant write dag (below) 249 * is used. 250 *****************************************************************************/ 251 252void rf_CommonCreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags, 253 allocList, nfaults, redFunc, allowBufferRecycle) 254 RF_Raid_t *raidPtr; 255 RF_AccessStripeMap_t *asmap; 256 RF_DagHeader_t *dag_h; 257 void *bp; 258 RF_RaidAccessFlags_t flags; 259 RF_AllocListElem_t *allocList; 260 int nfaults; 261 int (*redFunc)(RF_DagNode_t *); 262 int allowBufferRecycle; 263{ 264 int nNodes, nRrdNodes, nWndNodes, nXorBufs, i, j, paramNum, rdnodesFaked; 265 RF_DagNode_t *blockNode, *unblockNode, *wnpNode, *wnqNode, *termNode; 266 RF_DagNode_t *nodes, *wndNodes, *rrdNodes, *xorNode, *commitNode; 267 RF_SectorCount_t sectorsPerSU; 268 RF_ReconUnitNum_t which_ru; 269 char *xorTargetBuf = NULL; /* the target buffer for the XOR operation */ 270 char *overlappingPDAs; /* a temporary array of flags */ 271 RF_AccessStripeMapHeader_t *new_asm_h[2]; 272 RF_PhysDiskAddr_t *pda, *parityPDA; 273 RF_StripeNum_t parityStripeID; 274 RF_PhysDiskAddr_t *failedPDA; 275 RF_RaidLayout_t *layoutPtr; 276 277 layoutPtr = &(raidPtr->Layout); 278 parityStripeID = rf_RaidAddressToParityStripeID(layoutPtr, asmap->raidAddress, 279 &which_ru); 280 sectorsPerSU = layoutPtr->sectorsPerStripeUnit; 281 /* failedPDA points to the pda within the asm that targets the failed disk */ 282 failedPDA = asmap->failedPDAs[0]; 283 284 if (rf_dagDebug) 285 printf("[Creating degraded-write DAG]\n"); 286 287 RF_ASSERT( asmap->numDataFailed == 1 ); 288 dag_h->creator = "SimpleDegradedWriteDAG"; 289 290 /* 291 * Generate two ASMs identifying the surviving data 292 * we need in order to recover the lost data. 293 */ 294 /* overlappingPDAs array must be zero'd */ 295 RF_Calloc(overlappingPDAs, asmap->numStripeUnitsAccessed, sizeof(char), (char *)); 296 rf_GenerateFailedAccessASMs(raidPtr, asmap, failedPDA, dag_h, new_asm_h, 297 &nXorBufs, NULL, overlappingPDAs, allocList); 298 299 /* create all the nodes at once */ 300 nWndNodes = asmap->numStripeUnitsAccessed - 1; /* no access is generated 301 * for the failed pda */ 302 303 nRrdNodes = ((new_asm_h[0]) ? new_asm_h[0]->stripeMap->numStripeUnitsAccessed : 0) + 304 ((new_asm_h[1]) ? new_asm_h[1]->stripeMap->numStripeUnitsAccessed : 0); 305 /* 306 * XXX 307 * 308 * There's a bug with a complete stripe overwrite- that means 0 reads 309 * of old data, and the rest of the DAG generation code doesn't like 310 * that. A release is coming, and I don't wanna risk breaking a critical 311 * DAG generator, so here's what I'm gonna do- if there's no read nodes, 312 * I'm gonna fake there being a read node, and I'm gonna swap in a 313 * no-op node in its place (to make all the link-up code happy). 314 * This should be fixed at some point. --jimz 315 */ 316 if (nRrdNodes == 0) { 317 nRrdNodes = 1; 318 rdnodesFaked = 1; 319 } 320 else { 321 rdnodesFaked = 0; 322 } 323 /* lock, unlock, xor, Wnd, Rrd, W(nfaults) */ 324 nNodes = 5 + nfaults + nWndNodes + nRrdNodes; 325 RF_CallocAndAdd(nodes, nNodes, sizeof(RF_DagNode_t), 326 (RF_DagNode_t *), allocList); 327 i = 0; 328 blockNode = &nodes[i]; i += 1; 329 commitNode = &nodes[i]; i += 1; 330 unblockNode = &nodes[i]; i += 1; 331 termNode = &nodes[i]; i += 1; 332 xorNode = &nodes[i]; i += 1; 333 wnpNode = &nodes[i]; i += 1; 334 wndNodes = &nodes[i]; i += nWndNodes; 335 rrdNodes = &nodes[i]; i += nRrdNodes; 336 if (nfaults == 2) { 337 wnqNode = &nodes[i]; i += 1; 338 } 339 else { 340 wnqNode = NULL; 341 } 342 RF_ASSERT(i == nNodes); 343 344 /* this dag can not commit until all rrd and xor Nodes have completed */ 345 dag_h->numCommitNodes = 1; 346 dag_h->numCommits = 0; 347 dag_h->numSuccedents = 1; 348 349 RF_ASSERT( nRrdNodes > 0 ); 350 rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 351 NULL, nRrdNodes, 0, 0, 0, dag_h, "Nil", allocList); 352 rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 353 NULL, nWndNodes + nfaults, 1, 0, 0, dag_h, "Cmt", allocList); 354 rf_InitNode(unblockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 355 NULL, 1, nWndNodes + nfaults, 0, 0, dag_h, "Nil", allocList); 356 rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, 357 NULL, 0, 1, 0, 0, dag_h, "Trm", allocList); 358 rf_InitNode(xorNode, rf_wait, RF_FALSE, redFunc, rf_NullNodeUndoFunc, NULL, 1, 359 nRrdNodes, 2*nXorBufs+2, nfaults, dag_h, "Xrc", allocList); 360 361 /* 362 * Fill in the Rrd nodes. If any of the rrd buffers are the same size as 363 * the failed buffer, save a pointer to it so we can use it as the target 364 * of the XOR. The pdas in the rrd nodes have been range-restricted, so if 365 * a buffer is the same size as the failed buffer, it must also be at the 366 * same alignment within the SU. 367 */ 368 i = 0; 369 if (new_asm_h[0]) { 370 for (i=0, pda=new_asm_h[0]->stripeMap->physInfo; 371 i<new_asm_h[0]->stripeMap->numStripeUnitsAccessed; 372 i++, pda=pda->next) 373 { 374 rf_InitNode(&rrdNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, 375 rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rrd", allocList); 376 RF_ASSERT(pda); 377 rrdNodes[i].params[0].p = pda; 378 rrdNodes[i].params[1].p = pda->bufPtr; 379 rrdNodes[i].params[2].v = parityStripeID; 380 rrdNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 381 } 382 } 383 /* i now equals the number of stripe units accessed in new_asm_h[0] */ 384 if (new_asm_h[1]) { 385 for (j=0,pda=new_asm_h[1]->stripeMap->physInfo; 386 j<new_asm_h[1]->stripeMap->numStripeUnitsAccessed; 387 j++, pda=pda->next) 388 { 389 rf_InitNode(&rrdNodes[i+j], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, 390 rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rrd", allocList); 391 RF_ASSERT(pda); 392 rrdNodes[i+j].params[0].p = pda; 393 rrdNodes[i+j].params[1].p = pda->bufPtr; 394 rrdNodes[i+j].params[2].v = parityStripeID; 395 rrdNodes[i+j].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 396 if (allowBufferRecycle && (pda->numSector == failedPDA->numSector)) 397 xorTargetBuf = pda->bufPtr; 398 } 399 } 400 if (rdnodesFaked) { 401 /* 402 * This is where we'll init that fake noop read node 403 * (XXX should the wakeup func be different?) 404 */ 405 rf_InitNode(&rrdNodes[0], rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 406 NULL, 1, 1, 0, 0, dag_h, "RrN", allocList); 407 } 408 409 /* 410 * Make a PDA for the parity unit. The parity PDA should start at 411 * the same offset into the SU as the failed PDA. 412 */ 413 /* 414 * Danner comment: 415 * I don't think this copy is really necessary. 416 * We are in one of two cases here. 417 * (1) The entire failed unit is written. Then asmap->parityInfo will 418 * describe the entire parity. 419 * (2) We are only writing a subset of the failed unit and nothing 420 * else. Then the asmap->parityInfo describes the failed unit and 421 * the copy can also be avoided. 422 */ 423 424 RF_MallocAndAdd(parityPDA, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList); 425 parityPDA->row = asmap->parityInfo->row; 426 parityPDA->col = asmap->parityInfo->col; 427 parityPDA->startSector = ((asmap->parityInfo->startSector / sectorsPerSU) 428 * sectorsPerSU) + (failedPDA->startSector % sectorsPerSU); 429 parityPDA->numSector = failedPDA->numSector; 430 431 if (!xorTargetBuf) { 432 RF_CallocAndAdd(xorTargetBuf, 1, 433 rf_RaidAddressToByte(raidPtr, failedPDA->numSector), (char *), allocList); 434 } 435 436 /* init the Wnp node */ 437 rf_InitNode(wnpNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 438 rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnp", allocList); 439 wnpNode->params[0].p = parityPDA; 440 wnpNode->params[1].p = xorTargetBuf; 441 wnpNode->params[2].v = parityStripeID; 442 wnpNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 443 444 /* fill in the Wnq Node */ 445 if (nfaults == 2) { 446 { 447 RF_MallocAndAdd(parityPDA, sizeof(RF_PhysDiskAddr_t), 448 (RF_PhysDiskAddr_t *), allocList); 449 parityPDA->row = asmap->qInfo->row; 450 parityPDA->col = asmap->qInfo->col; 451 parityPDA->startSector = ((asmap->qInfo->startSector / sectorsPerSU) 452 * sectorsPerSU) + (failedPDA->startSector % sectorsPerSU); 453 parityPDA->numSector = failedPDA->numSector; 454 455 rf_InitNode(wnqNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 456 rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnq", allocList); 457 wnqNode->params[0].p = parityPDA; 458 RF_CallocAndAdd(xorNode->results[1], 1, 459 rf_RaidAddressToByte(raidPtr, failedPDA->numSector), (char *), allocList); 460 wnqNode->params[1].p = xorNode->results[1]; 461 wnqNode->params[2].v = parityStripeID; 462 wnqNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 463 } 464 } 465 466 /* fill in the Wnd nodes */ 467 for (pda=asmap->physInfo, i=0; i<nWndNodes; i++, pda=pda->next) { 468 if (pda == failedPDA) { 469 i--; 470 continue; 471 } 472 rf_InitNode(&wndNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 473 rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnd", allocList); 474 RF_ASSERT(pda); 475 wndNodes[i].params[0].p = pda; 476 wndNodes[i].params[1].p = pda->bufPtr; 477 wndNodes[i].params[2].v = parityStripeID; 478 wndNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 479 } 480 481 /* fill in the results of the xor node */ 482 xorNode->results[0] = xorTargetBuf; 483 484 /* fill in the params of the xor node */ 485 486 paramNum=0; 487 if (rdnodesFaked == 0) { 488 for (i=0; i<nRrdNodes; i++) { 489 /* all the Rrd nodes need to be xored together */ 490 xorNode->params[paramNum++] = rrdNodes[i].params[0]; 491 xorNode->params[paramNum++] = rrdNodes[i].params[1]; 492 } 493 } 494 for (i=0; i < nWndNodes; i++) { 495 /* any Wnd nodes that overlap the failed access need to be xored in */ 496 if (overlappingPDAs[i]) { 497 RF_MallocAndAdd(pda, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList); 498 bcopy((char *)wndNodes[i].params[0].p, (char *)pda, sizeof(RF_PhysDiskAddr_t)); 499 rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_DOBUFFER, 0); 500 xorNode->params[paramNum++].p = pda; 501 xorNode->params[paramNum++].p = pda->bufPtr; 502 } 503 } 504 RF_Free(overlappingPDAs, asmap->numStripeUnitsAccessed * sizeof(char)); 505 506 /* 507 * Install the failed PDA into the xor param list so that the 508 * new data gets xor'd in. 509 */ 510 xorNode->params[paramNum++].p = failedPDA; 511 xorNode->params[paramNum++].p = failedPDA->bufPtr; 512 513 /* 514 * The last 2 params to the recovery xor node are always the failed 515 * PDA and the raidPtr. install the failedPDA even though we have just 516 * done so above. This allows us to use the same XOR function for both 517 * degraded reads and degraded writes. 518 */ 519 xorNode->params[paramNum++].p = failedPDA; 520 xorNode->params[paramNum++].p = raidPtr; 521 RF_ASSERT( paramNum == 2*nXorBufs+2 ); 522 523 /* 524 * Code to link nodes begins here 525 */ 526 527 /* link header to block node */ 528 RF_ASSERT(blockNode->numAntecedents == 0); 529 dag_h->succedents[0] = blockNode; 530 531 /* link block node to rd nodes */ 532 RF_ASSERT(blockNode->numSuccedents == nRrdNodes); 533 for (i = 0; i < nRrdNodes; i++) { 534 RF_ASSERT(rrdNodes[i].numAntecedents == 1); 535 blockNode->succedents[i] = &rrdNodes[i]; 536 rrdNodes[i].antecedents[0] = blockNode; 537 rrdNodes[i].antType[0] = rf_control; 538 } 539 540 /* link read nodes to xor node*/ 541 RF_ASSERT(xorNode->numAntecedents == nRrdNodes); 542 for (i = 0; i < nRrdNodes; i++) { 543 RF_ASSERT(rrdNodes[i].numSuccedents == 1); 544 rrdNodes[i].succedents[0] = xorNode; 545 xorNode->antecedents[i] = &rrdNodes[i]; 546 xorNode->antType[i] = rf_trueData; 547 } 548 549 /* link xor node to commit node */ 550 RF_ASSERT(xorNode->numSuccedents == 1); 551 RF_ASSERT(commitNode->numAntecedents == 1); 552 xorNode->succedents[0] = commitNode; 553 commitNode->antecedents[0] = xorNode; 554 commitNode->antType[0] = rf_control; 555 556 /* link commit node to wnd nodes */ 557 RF_ASSERT(commitNode->numSuccedents == nfaults + nWndNodes); 558 for (i = 0; i < nWndNodes; i++) { 559 RF_ASSERT(wndNodes[i].numAntecedents == 1); 560 commitNode->succedents[i] = &wndNodes[i]; 561 wndNodes[i].antecedents[0] = commitNode; 562 wndNodes[i].antType[0] = rf_control; 563 } 564 565 /* link the commit node to wnp, wnq nodes */ 566 RF_ASSERT(wnpNode->numAntecedents == 1); 567 commitNode->succedents[nWndNodes] = wnpNode; 568 wnpNode->antecedents[0] = commitNode; 569 wnpNode->antType[0] = rf_control; 570 if (nfaults == 2) { 571 RF_ASSERT(wnqNode->numAntecedents == 1); 572 commitNode->succedents[nWndNodes + 1] = wnqNode; 573 wnqNode->antecedents[0] = commitNode; 574 wnqNode->antType[0] = rf_control; 575 } 576 577 /* link write new data nodes to unblock node */ 578 RF_ASSERT(unblockNode->numAntecedents == (nWndNodes + nfaults)); 579 for(i = 0; i < nWndNodes; i++) { 580 RF_ASSERT(wndNodes[i].numSuccedents == 1); 581 wndNodes[i].succedents[0] = unblockNode; 582 unblockNode->antecedents[i] = &wndNodes[i]; 583 unblockNode->antType[i] = rf_control; 584 } 585 586 /* link write new parity node to unblock node */ 587 RF_ASSERT(wnpNode->numSuccedents == 1); 588 wnpNode->succedents[0] = unblockNode; 589 unblockNode->antecedents[nWndNodes] = wnpNode; 590 unblockNode->antType[nWndNodes] = rf_control; 591 592 /* link write new q node to unblock node */ 593 if (nfaults == 2) { 594 RF_ASSERT(wnqNode->numSuccedents == 1); 595 wnqNode->succedents[0] = unblockNode; 596 unblockNode->antecedents[nWndNodes+1] = wnqNode; 597 unblockNode->antType[nWndNodes+1] = rf_control; 598 } 599 600 /* link unblock node to term node */ 601 RF_ASSERT(unblockNode->numSuccedents == 1); 602 RF_ASSERT(termNode->numAntecedents == 1); 603 RF_ASSERT(termNode->numSuccedents == 0); 604 unblockNode->succedents[0] = termNode; 605 termNode->antecedents[0] = unblockNode; 606 termNode->antType[0] = rf_control; 607} 608 609#define CONS_PDA(if,start,num) \ 610 pda_p->row = asmap->if->row; pda_p->col = asmap->if->col; \ 611 pda_p->startSector = ((asmap->if->startSector / secPerSU) * secPerSU) + start; \ 612 pda_p->numSector = num; \ 613 pda_p->next = NULL; \ 614 RF_MallocAndAdd(pda_p->bufPtr,rf_RaidAddressToByte(raidPtr,num),(char *), allocList) 615 616void rf_WriteGenerateFailedAccessASMs( 617 RF_Raid_t *raidPtr, 618 RF_AccessStripeMap_t *asmap, 619 RF_PhysDiskAddr_t **pdap, 620 int *nNodep, 621 RF_PhysDiskAddr_t **pqpdap, 622 int *nPQNodep, 623 RF_AllocListElem_t *allocList) 624{ 625 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 626 int PDAPerDisk,i; 627 RF_SectorCount_t secPerSU = layoutPtr->sectorsPerStripeUnit; 628 int numDataCol = layoutPtr->numDataCol; 629 int state; 630 unsigned napdas; 631 RF_SectorNum_t fone_start, fone_end, ftwo_start = 0, ftwo_end; 632 RF_PhysDiskAddr_t *fone = asmap->failedPDAs[0], *ftwo = asmap->failedPDAs[1]; 633 RF_PhysDiskAddr_t *pda_p; 634 RF_RaidAddr_t sosAddr; 635 636 /* determine how many pda's we will have to generate per unaccess stripe. 637 If there is only one failed data unit, it is one; if two, possibly two, 638 depending wether they overlap. */ 639 640 fone_start = rf_StripeUnitOffset(layoutPtr,fone->startSector); 641 fone_end = fone_start + fone->numSector; 642 643 if (asmap->numDataFailed==1) 644 { 645 PDAPerDisk = 1; 646 state = 1; 647 RF_MallocAndAdd(*pqpdap,2*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList); 648 pda_p = *pqpdap; 649 /* build p */ 650 CONS_PDA(parityInfo,fone_start,fone->numSector); 651 pda_p->type = RF_PDA_TYPE_PARITY; 652 pda_p++; 653 /* build q */ 654 CONS_PDA(qInfo,fone_start,fone->numSector); 655 pda_p->type = RF_PDA_TYPE_Q; 656 } 657 else 658 { 659 ftwo_start = rf_StripeUnitOffset(layoutPtr,ftwo->startSector); 660 ftwo_end = ftwo_start + ftwo->numSector; 661 if (fone->numSector + ftwo->numSector > secPerSU) 662 { 663 PDAPerDisk = 1; 664 state = 2; 665 RF_MallocAndAdd(*pqpdap,2*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList); 666 pda_p = *pqpdap; 667 CONS_PDA(parityInfo,0,secPerSU); 668 pda_p->type = RF_PDA_TYPE_PARITY; 669 pda_p++; 670 CONS_PDA(qInfo,0,secPerSU); 671 pda_p->type = RF_PDA_TYPE_Q; 672 } 673 else 674 { 675 PDAPerDisk = 2; 676 state = 3; 677 /* four of them, fone, then ftwo */ 678 RF_MallocAndAdd(*pqpdap,4*sizeof(RF_PhysDiskAddr_t),(RF_PhysDiskAddr_t *), allocList); 679 pda_p = *pqpdap; 680 CONS_PDA(parityInfo,fone_start,fone->numSector); 681 pda_p->type = RF_PDA_TYPE_PARITY; 682 pda_p++; 683 CONS_PDA(qInfo,fone_start,fone->numSector); 684 pda_p->type = RF_PDA_TYPE_Q; 685 pda_p++; 686 CONS_PDA(parityInfo,ftwo_start,ftwo->numSector); 687 pda_p->type = RF_PDA_TYPE_PARITY; 688 pda_p++; 689 CONS_PDA(qInfo,ftwo_start,ftwo->numSector); 690 pda_p->type = RF_PDA_TYPE_Q; 691 } 692 } 693 /* figure out number of nonaccessed pda */ 694 napdas = PDAPerDisk * (numDataCol - 2); 695 *nPQNodep = PDAPerDisk; 696 697 *nNodep = napdas; 698 if (napdas == 0) return; /* short circuit */ 699 700 /* allocate up our list of pda's */ 701 702 RF_CallocAndAdd(pda_p, napdas, sizeof(RF_PhysDiskAddr_t), (RF_PhysDiskAddr_t *), allocList); 703 *pdap = pda_p; 704 705 /* linkem together */ 706 for (i=0; i < (napdas-1); i++) 707 pda_p[i].next = pda_p+(i+1); 708 709 sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress); 710 for (i=0; i < numDataCol; i++) 711 { 712 if ((pda_p - (*pdap)) == napdas) 713 continue; 714 pda_p->type = RF_PDA_TYPE_DATA; 715 pda_p->raidAddress = sosAddr + (i * secPerSU); 716 (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0); 717 /* skip over dead disks */ 718 if (RF_DEAD_DISK(raidPtr->Disks[pda_p->row][pda_p->col].status)) 719 continue; 720 switch (state) 721 { 722 case 1: /* fone */ 723 pda_p->numSector = fone->numSector; 724 pda_p->raidAddress += fone_start; 725 pda_p->startSector += fone_start; 726 RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList); 727 break; 728 case 2: /* full stripe */ 729 pda_p->numSector = secPerSU; 730 RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,secPerSU), (char *), allocList); 731 break; 732 case 3: /* two slabs */ 733 pda_p->numSector = fone->numSector; 734 pda_p->raidAddress += fone_start; 735 pda_p->startSector += fone_start; 736 RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList); 737 pda_p++; 738 pda_p->type = RF_PDA_TYPE_DATA; 739 pda_p->raidAddress = sosAddr + (i * secPerSU); 740 (raidPtr->Layout.map->MapSector)(raidPtr,pda_p->raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), 0); 741 pda_p->numSector = ftwo->numSector; 742 pda_p->raidAddress += ftwo_start; 743 pda_p->startSector += ftwo_start; 744 RF_MallocAndAdd(pda_p->bufPtr, rf_RaidAddressToByte(raidPtr,pda_p->numSector), (char *), allocList); 745 break; 746 default: 747 RF_PANIC(); 748 } 749 pda_p++; 750 } 751 752 RF_ASSERT (pda_p - *pdap == napdas); 753 return; 754} 755 756#define DISK_NODE_PDA(node) ((node)->params[0].p) 757 758#define DISK_NODE_PARAMS(_node_,_p_) \ 759 (_node_).params[0].p = _p_ ; \ 760 (_node_).params[1].p = (_p_)->bufPtr; \ 761 (_node_).params[2].v = parityStripeID; \ 762 (_node_).params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru) 763 764void rf_DoubleDegSmallWrite( 765 RF_Raid_t *raidPtr, 766 RF_AccessStripeMap_t *asmap, 767 RF_DagHeader_t *dag_h, 768 void *bp, 769 RF_RaidAccessFlags_t flags, 770 RF_AllocListElem_t *allocList, 771 char *redundantReadNodeName, 772 char *redundantWriteNodeName, 773 char *recoveryNodeName, 774 int (*recovFunc)(RF_DagNode_t *)) 775{ 776 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 777 RF_DagNode_t *nodes, *wudNodes, *rrdNodes, *recoveryNode, *blockNode, *unblockNode, *rpNodes,*rqNodes, *wpNodes, *wqNodes, *termNode; 778 RF_PhysDiskAddr_t *pda, *pqPDAs; 779 RF_PhysDiskAddr_t *npdas; 780 int nWriteNodes, nNodes, nReadNodes, nRrdNodes, nWudNodes, i; 781 RF_ReconUnitNum_t which_ru; 782 int nPQNodes; 783 RF_StripeNum_t parityStripeID = rf_RaidAddressToParityStripeID(layoutPtr, asmap->raidAddress, &which_ru); 784 785 /* simple small write case - 786 First part looks like a reconstruct-read of the failed data units. 787 Then a write of all data units not failed. */ 788 789 790 /* 791 Hdr 792 | 793 ------Block- 794 / / \ 795 Rrd Rrd ... Rrd Rp Rq 796 \ \ / 797 -------PQ----- 798 / \ \ 799 Wud Wp WQ 800 \ | / 801 --Unblock- 802 | 803 T 804 805 Rrd = read recovery data (potentially none) 806 Wud = write user data (not incl. failed disks) 807 Wp = Write P (could be two) 808 Wq = Write Q (could be two) 809 810 */ 811 812 rf_WriteGenerateFailedAccessASMs(raidPtr, asmap, &npdas, &nRrdNodes, &pqPDAs, &nPQNodes,allocList); 813 814 RF_ASSERT(asmap->numDataFailed == 1); 815 816 nWudNodes = asmap->numStripeUnitsAccessed - (asmap->numDataFailed); 817 nReadNodes = nRrdNodes + 2*nPQNodes; 818 nWriteNodes = nWudNodes+ 2*nPQNodes; 819 nNodes = 4 + nReadNodes + nWriteNodes; 820 821 RF_CallocAndAdd(nodes, nNodes, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList); 822 blockNode = nodes; 823 unblockNode = blockNode+1; 824 termNode = unblockNode+1; 825 recoveryNode = termNode+1; 826 rrdNodes = recoveryNode+1; 827 rpNodes = rrdNodes + nRrdNodes; 828 rqNodes = rpNodes + nPQNodes; 829 wudNodes = rqNodes + nPQNodes; 830 wpNodes = wudNodes + nWudNodes; 831 wqNodes = wpNodes + nPQNodes; 832 833 dag_h->creator = "PQ_DDSimpleSmallWrite"; 834 dag_h->numSuccedents = 1; 835 dag_h->succedents[0] = blockNode; 836 rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 0, 1, 0, 0, dag_h, "Trm", allocList); 837 termNode->antecedents[0] = unblockNode; 838 termNode->antType[0] = rf_control; 839 840 /* init the block and unblock nodes */ 841 /* The block node has all the read nodes as successors */ 842 rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nReadNodes, 0, 0, 0, dag_h, "Nil", allocList); 843 for (i=0; i < nReadNodes; i++) 844 blockNode->succedents[i] = rrdNodes+i; 845 846 /* The unblock node has all the writes as successors */ 847 rf_InitNode(unblockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, 1, nWriteNodes, 0, 0, dag_h, "Nil", allocList); 848 for (i=0; i < nWriteNodes; i++) { 849 unblockNode->antecedents[i] = wudNodes+i; 850 unblockNode->antType[i] = rf_control; 851 } 852 unblockNode->succedents[0] = termNode; 853 854#define INIT_READ_NODE(node,name) \ 855 rf_InitNode(node, rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, name, allocList); \ 856 (node)->succedents[0] = recoveryNode; \ 857 (node)->antecedents[0] = blockNode; \ 858 (node)->antType[0] = rf_control; 859 860 /* build the read nodes */ 861 pda = npdas; 862 for (i=0; i < nRrdNodes; i++, pda = pda->next) { 863 INIT_READ_NODE(rrdNodes+i,"rrd"); 864 DISK_NODE_PARAMS(rrdNodes[i],pda); 865 } 866 867 /* read redundancy pdas */ 868 pda = pqPDAs; 869 INIT_READ_NODE(rpNodes,"Rp"); 870 RF_ASSERT(pda); 871 DISK_NODE_PARAMS(rpNodes[0],pda); 872 pda++; 873 INIT_READ_NODE(rqNodes, redundantReadNodeName ); 874 RF_ASSERT(pda); 875 DISK_NODE_PARAMS(rqNodes[0],pda); 876 if (nPQNodes==2) 877 { 878 pda++; 879 INIT_READ_NODE(rpNodes+1,"Rp"); 880 RF_ASSERT(pda); 881 DISK_NODE_PARAMS(rpNodes[1],pda); 882 pda++; 883 INIT_READ_NODE(rqNodes+1,redundantReadNodeName ); 884 RF_ASSERT(pda); 885 DISK_NODE_PARAMS(rqNodes[1],pda); 886 } 887 888 /* the recovery node has all reads as precedessors and all writes as successors. 889 It generates a result for every write P or write Q node. 890 As parameters, it takes a pda per read and a pda per stripe of user data written. 891 It also takes as the last params the raidPtr and asm. 892 For results, it takes PDA for P & Q. */ 893 894 895 rf_InitNode(recoveryNode, rf_wait, RF_FALSE, recovFunc, rf_NullNodeUndoFunc, NULL, 896 nWriteNodes, /* succesors */ 897 nReadNodes, /* preds */ 898 nReadNodes + nWudNodes + 3, /* params */ 899 2 * nPQNodes, /* results */ 900 dag_h, recoveryNodeName, allocList); 901 902 903 904 for (i=0; i < nReadNodes; i++ ) 905 { 906 recoveryNode->antecedents[i] = rrdNodes+i; 907 recoveryNode->antType[i] = rf_control; 908 recoveryNode->params[i].p = DISK_NODE_PDA(rrdNodes+i); 909 } 910 for (i=0; i < nWudNodes; i++) 911 { 912 recoveryNode->succedents[i] = wudNodes+i; 913 } 914 recoveryNode->params[nReadNodes+nWudNodes].p = asmap->failedPDAs[0]; 915 recoveryNode->params[nReadNodes+nWudNodes+1].p = raidPtr; 916 recoveryNode->params[nReadNodes+nWudNodes+2].p = asmap; 917 918 for ( ; i < nWriteNodes; i++) 919 recoveryNode->succedents[i] = wudNodes+i; 920 921 pda = pqPDAs; 922 recoveryNode->results[0] = pda; 923 pda++; 924 recoveryNode->results[1] = pda; 925 if ( nPQNodes == 2) 926 { 927 pda++; 928 recoveryNode->results[2] = pda; 929 pda++; 930 recoveryNode->results[3] = pda; 931 } 932 933 /* fill writes */ 934#define INIT_WRITE_NODE(node,name) \ 935 rf_InitNode(node, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, name, allocList); \ 936 (node)->succedents[0] = unblockNode; \ 937 (node)->antecedents[0] = recoveryNode; \ 938 (node)->antType[0] = rf_control; 939 940 pda = asmap->physInfo; 941 for (i=0; i < nWudNodes; i++) 942 { 943 INIT_WRITE_NODE(wudNodes+i,"Wd"); 944 DISK_NODE_PARAMS(wudNodes[i],pda); 945 recoveryNode->params[nReadNodes+i].p = DISK_NODE_PDA(wudNodes+i); 946 pda = pda->next; 947 } 948 /* write redundancy pdas */ 949 pda = pqPDAs; 950 INIT_WRITE_NODE(wpNodes,"Wp"); 951 RF_ASSERT(pda); 952 DISK_NODE_PARAMS(wpNodes[0],pda); 953 pda++; 954 INIT_WRITE_NODE(wqNodes,"Wq"); 955 RF_ASSERT(pda); 956 DISK_NODE_PARAMS(wqNodes[0],pda); 957 if (nPQNodes==2) 958 { 959 pda++; 960 INIT_WRITE_NODE(wpNodes+1,"Wp"); 961 RF_ASSERT(pda); 962 DISK_NODE_PARAMS(wpNodes[1],pda); 963 pda++; 964 INIT_WRITE_NODE(wqNodes+1,"Wq"); 965 RF_ASSERT(pda); 966 DISK_NODE_PARAMS(wqNodes[1],pda); 967 } 968} 969