rf_dagffwr.c revision 1.9
1 1.9 oster /* $NetBSD: rf_dagffwr.c,v 1.9 2002/09/21 00:50:10 oster Exp $ */ 2 1.1 oster /* 3 1.1 oster * Copyright (c) 1995 Carnegie-Mellon University. 4 1.1 oster * All rights reserved. 5 1.1 oster * 6 1.1 oster * Author: Mark Holland, Daniel Stodolsky, William V. Courtright II 7 1.1 oster * 8 1.1 oster * Permission to use, copy, modify and distribute this software and 9 1.1 oster * its documentation is hereby granted, provided that both the copyright 10 1.1 oster * notice and this permission notice appear in all copies of the 11 1.1 oster * software, derivative works or modified versions, and any portions 12 1.1 oster * thereof, and that both notices appear in supporting documentation. 13 1.1 oster * 14 1.1 oster * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 15 1.1 oster * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 16 1.1 oster * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 17 1.1 oster * 18 1.1 oster * Carnegie Mellon requests users of this software to return to 19 1.1 oster * 20 1.1 oster * Software Distribution Coordinator or Software.Distribution (at) CS.CMU.EDU 21 1.1 oster * School of Computer Science 22 1.1 oster * Carnegie Mellon University 23 1.1 oster * Pittsburgh PA 15213-3890 24 1.1 oster * 25 1.1 oster * any improvements or extensions that they make and grant Carnegie the 26 1.1 oster * rights to redistribute these changes. 27 1.1 oster */ 28 1.1 oster 29 1.1 oster /* 30 1.1 oster * rf_dagff.c 31 1.1 oster * 32 1.1 oster * code for creating fault-free DAGs 33 1.1 oster * 34 1.1 oster */ 35 1.7 lukem 36 1.7 lukem #include <sys/cdefs.h> 37 1.9 oster __KERNEL_RCSID(0, "$NetBSD: rf_dagffwr.c,v 1.9 2002/09/21 00:50:10 oster Exp $"); 38 1.1 oster 39 1.6 oster #include <dev/raidframe/raidframevar.h> 40 1.6 oster 41 1.1 oster #include "rf_raid.h" 42 1.1 oster #include "rf_dag.h" 43 1.1 oster #include "rf_dagutils.h" 44 1.1 oster #include "rf_dagfuncs.h" 45 1.1 oster #include "rf_debugMem.h" 46 1.1 oster #include "rf_dagffrd.h" 47 1.1 oster #include "rf_general.h" 48 1.1 oster #include "rf_dagffwr.h" 49 1.1 oster 50 1.1 oster /****************************************************************************** 51 1.1 oster * 52 1.1 oster * General comments on DAG creation: 53 1.3 oster * 54 1.1 oster * All DAGs in this file use roll-away error recovery. Each DAG has a single 55 1.1 oster * commit node, usually called "Cmt." If an error occurs before the Cmt node 56 1.1 oster * is reached, the execution engine will halt forward execution and work 57 1.1 oster * backward through the graph, executing the undo functions. Assuming that 58 1.1 oster * each node in the graph prior to the Cmt node are undoable and atomic - or - 59 1.1 oster * does not make changes to permanent state, the graph will fail atomically. 60 1.1 oster * If an error occurs after the Cmt node executes, the engine will roll-forward 61 1.1 oster * through the graph, blindly executing nodes until it reaches the end. 62 1.1 oster * If a graph reaches the end, it is assumed to have completed successfully. 63 1.1 oster * 64 1.1 oster * A graph has only 1 Cmt node. 65 1.1 oster * 66 1.1 oster */ 67 1.1 oster 68 1.1 oster 69 1.1 oster /****************************************************************************** 70 1.1 oster * 71 1.1 oster * The following wrappers map the standard DAG creation interface to the 72 1.1 oster * DAG creation routines. Additionally, these wrappers enable experimentation 73 1.1 oster * with new DAG structures by providing an extra level of indirection, allowing 74 1.1 oster * the DAG creation routines to be replaced at this single point. 75 1.1 oster */ 76 1.1 oster 77 1.1 oster 78 1.3 oster void 79 1.3 oster rf_CreateNonRedundantWriteDAG( 80 1.3 oster RF_Raid_t * raidPtr, 81 1.3 oster RF_AccessStripeMap_t * asmap, 82 1.3 oster RF_DagHeader_t * dag_h, 83 1.3 oster void *bp, 84 1.3 oster RF_RaidAccessFlags_t flags, 85 1.3 oster RF_AllocListElem_t * allocList, 86 1.3 oster RF_IoType_t type) 87 1.1 oster { 88 1.3 oster rf_CreateNonredundantDAG(raidPtr, asmap, dag_h, bp, flags, allocList, 89 1.3 oster RF_IO_TYPE_WRITE); 90 1.1 oster } 91 1.1 oster 92 1.3 oster void 93 1.3 oster rf_CreateRAID0WriteDAG( 94 1.3 oster RF_Raid_t * raidPtr, 95 1.3 oster RF_AccessStripeMap_t * asmap, 96 1.3 oster RF_DagHeader_t * dag_h, 97 1.3 oster void *bp, 98 1.3 oster RF_RaidAccessFlags_t flags, 99 1.3 oster RF_AllocListElem_t * allocList, 100 1.3 oster RF_IoType_t type) 101 1.1 oster { 102 1.3 oster rf_CreateNonredundantDAG(raidPtr, asmap, dag_h, bp, flags, allocList, 103 1.3 oster RF_IO_TYPE_WRITE); 104 1.1 oster } 105 1.1 oster 106 1.3 oster void 107 1.3 oster rf_CreateSmallWriteDAG( 108 1.3 oster RF_Raid_t * raidPtr, 109 1.3 oster RF_AccessStripeMap_t * asmap, 110 1.3 oster RF_DagHeader_t * dag_h, 111 1.3 oster void *bp, 112 1.3 oster RF_RaidAccessFlags_t flags, 113 1.3 oster RF_AllocListElem_t * allocList) 114 1.1 oster { 115 1.3 oster /* "normal" rollaway */ 116 1.3 oster rf_CommonCreateSmallWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList, 117 1.3 oster &rf_xorFuncs, NULL); 118 1.1 oster } 119 1.1 oster 120 1.3 oster void 121 1.3 oster rf_CreateLargeWriteDAG( 122 1.3 oster RF_Raid_t * raidPtr, 123 1.3 oster RF_AccessStripeMap_t * asmap, 124 1.3 oster RF_DagHeader_t * dag_h, 125 1.3 oster void *bp, 126 1.3 oster RF_RaidAccessFlags_t flags, 127 1.3 oster RF_AllocListElem_t * allocList) 128 1.1 oster { 129 1.3 oster /* "normal" rollaway */ 130 1.3 oster rf_CommonCreateLargeWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList, 131 1.3 oster 1, rf_RegularXorFunc, RF_TRUE); 132 1.1 oster } 133 1.1 oster 134 1.1 oster 135 1.1 oster /****************************************************************************** 136 1.1 oster * 137 1.1 oster * DAG creation code begins here 138 1.1 oster */ 139 1.1 oster 140 1.1 oster 141 1.1 oster /****************************************************************************** 142 1.1 oster * 143 1.1 oster * creates a DAG to perform a large-write operation: 144 1.1 oster * 145 1.1 oster * / Rod \ / Wnd \ 146 1.1 oster * H -- block- Rod - Xor - Cmt - Wnd --- T 147 1.1 oster * \ Rod / \ Wnp / 148 1.1 oster * \[Wnq]/ 149 1.1 oster * 150 1.1 oster * The XOR node also does the Q calculation in the P+Q architecture. 151 1.1 oster * All nodes are before the commit node (Cmt) are assumed to be atomic and 152 1.1 oster * undoable - or - they make no changes to permanent state. 153 1.1 oster * 154 1.1 oster * Rod = read old data 155 1.1 oster * Cmt = commit node 156 1.1 oster * Wnp = write new parity 157 1.1 oster * Wnd = write new data 158 1.1 oster * Wnq = write new "q" 159 1.1 oster * [] denotes optional segments in the graph 160 1.1 oster * 161 1.1 oster * Parameters: raidPtr - description of the physical array 162 1.1 oster * asmap - logical & physical addresses for this access 163 1.1 oster * bp - buffer ptr (holds write data) 164 1.3 oster * flags - general flags (e.g. disk locking) 165 1.1 oster * allocList - list of memory allocated in DAG creation 166 1.1 oster * nfaults - number of faults array can tolerate 167 1.1 oster * (equal to # redundancy units in stripe) 168 1.1 oster * redfuncs - list of redundancy generating functions 169 1.1 oster * 170 1.1 oster *****************************************************************************/ 171 1.1 oster 172 1.3 oster void 173 1.3 oster rf_CommonCreateLargeWriteDAG( 174 1.3 oster RF_Raid_t * raidPtr, 175 1.3 oster RF_AccessStripeMap_t * asmap, 176 1.3 oster RF_DagHeader_t * dag_h, 177 1.3 oster void *bp, 178 1.3 oster RF_RaidAccessFlags_t flags, 179 1.3 oster RF_AllocListElem_t * allocList, 180 1.3 oster int nfaults, 181 1.3 oster int (*redFunc) (RF_DagNode_t *), 182 1.3 oster int allowBufferRecycle) 183 1.1 oster { 184 1.3 oster RF_DagNode_t *nodes, *wndNodes, *rodNodes, *xorNode, *wnpNode; 185 1.3 oster RF_DagNode_t *wnqNode, *blockNode, *commitNode, *termNode; 186 1.3 oster int nWndNodes, nRodNodes, i, nodeNum, asmNum; 187 1.3 oster RF_AccessStripeMapHeader_t *new_asm_h[2]; 188 1.3 oster RF_StripeNum_t parityStripeID; 189 1.3 oster char *sosBuffer, *eosBuffer; 190 1.3 oster RF_ReconUnitNum_t which_ru; 191 1.3 oster RF_RaidLayout_t *layoutPtr; 192 1.3 oster RF_PhysDiskAddr_t *pda; 193 1.3 oster 194 1.3 oster layoutPtr = &(raidPtr->Layout); 195 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(layoutPtr, asmap->raidAddress, 196 1.3 oster &which_ru); 197 1.3 oster 198 1.3 oster if (rf_dagDebug) { 199 1.3 oster printf("[Creating large-write DAG]\n"); 200 1.3 oster } 201 1.3 oster dag_h->creator = "LargeWriteDAG"; 202 1.3 oster 203 1.3 oster dag_h->numCommitNodes = 1; 204 1.3 oster dag_h->numCommits = 0; 205 1.3 oster dag_h->numSuccedents = 1; 206 1.3 oster 207 1.3 oster /* alloc the nodes: Wnd, xor, commit, block, term, and Wnp */ 208 1.3 oster nWndNodes = asmap->numStripeUnitsAccessed; 209 1.3 oster RF_CallocAndAdd(nodes, nWndNodes + 4 + nfaults, sizeof(RF_DagNode_t), 210 1.3 oster (RF_DagNode_t *), allocList); 211 1.3 oster i = 0; 212 1.3 oster wndNodes = &nodes[i]; 213 1.3 oster i += nWndNodes; 214 1.3 oster xorNode = &nodes[i]; 215 1.3 oster i += 1; 216 1.3 oster wnpNode = &nodes[i]; 217 1.3 oster i += 1; 218 1.3 oster blockNode = &nodes[i]; 219 1.3 oster i += 1; 220 1.3 oster commitNode = &nodes[i]; 221 1.3 oster i += 1; 222 1.3 oster termNode = &nodes[i]; 223 1.3 oster i += 1; 224 1.3 oster if (nfaults == 2) { 225 1.3 oster wnqNode = &nodes[i]; 226 1.3 oster i += 1; 227 1.3 oster } else { 228 1.3 oster wnqNode = NULL; 229 1.3 oster } 230 1.3 oster rf_MapUnaccessedPortionOfStripe(raidPtr, layoutPtr, asmap, dag_h, new_asm_h, 231 1.3 oster &nRodNodes, &sosBuffer, &eosBuffer, allocList); 232 1.3 oster if (nRodNodes > 0) { 233 1.3 oster RF_CallocAndAdd(rodNodes, nRodNodes, sizeof(RF_DagNode_t), 234 1.3 oster (RF_DagNode_t *), allocList); 235 1.3 oster } else { 236 1.3 oster rodNodes = NULL; 237 1.3 oster } 238 1.3 oster 239 1.3 oster /* begin node initialization */ 240 1.3 oster if (nRodNodes > 0) { 241 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 242 1.3 oster NULL, nRodNodes, 0, 0, 0, dag_h, "Nil", allocList); 243 1.3 oster } else { 244 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 245 1.3 oster NULL, 1, 0, 0, 0, dag_h, "Nil", allocList); 246 1.3 oster } 247 1.3 oster 248 1.3 oster rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, 249 1.3 oster nWndNodes + nfaults, 1, 0, 0, dag_h, "Cmt", allocList); 250 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 251 1.3 oster 0, nWndNodes + nfaults, 0, 0, dag_h, "Trm", allocList); 252 1.3 oster 253 1.3 oster /* initialize the Rod nodes */ 254 1.3 oster for (nodeNum = asmNum = 0; asmNum < 2; asmNum++) { 255 1.3 oster if (new_asm_h[asmNum]) { 256 1.3 oster pda = new_asm_h[asmNum]->stripeMap->physInfo; 257 1.3 oster while (pda) { 258 1.3 oster rf_InitNode(&rodNodes[nodeNum], rf_wait, RF_FALSE, rf_DiskReadFunc, 259 1.3 oster rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, 260 1.3 oster "Rod", allocList); 261 1.3 oster rodNodes[nodeNum].params[0].p = pda; 262 1.3 oster rodNodes[nodeNum].params[1].p = pda->bufPtr; 263 1.3 oster rodNodes[nodeNum].params[2].v = parityStripeID; 264 1.3 oster rodNodes[nodeNum].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 265 1.3 oster 0, 0, which_ru); 266 1.3 oster nodeNum++; 267 1.3 oster pda = pda->next; 268 1.3 oster } 269 1.3 oster } 270 1.3 oster } 271 1.3 oster RF_ASSERT(nodeNum == nRodNodes); 272 1.3 oster 273 1.3 oster /* initialize the wnd nodes */ 274 1.3 oster pda = asmap->physInfo; 275 1.3 oster for (i = 0; i < nWndNodes; i++) { 276 1.3 oster rf_InitNode(&wndNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 277 1.3 oster rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnd", allocList); 278 1.3 oster RF_ASSERT(pda != NULL); 279 1.3 oster wndNodes[i].params[0].p = pda; 280 1.3 oster wndNodes[i].params[1].p = pda->bufPtr; 281 1.3 oster wndNodes[i].params[2].v = parityStripeID; 282 1.3 oster wndNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 283 1.3 oster pda = pda->next; 284 1.3 oster } 285 1.3 oster 286 1.3 oster /* initialize the redundancy node */ 287 1.3 oster if (nRodNodes > 0) { 288 1.3 oster rf_InitNode(xorNode, rf_wait, RF_FALSE, redFunc, rf_NullNodeUndoFunc, NULL, 1, 289 1.3 oster nRodNodes, 2 * (nWndNodes + nRodNodes) + 1, nfaults, dag_h, 290 1.3 oster "Xr ", allocList); 291 1.3 oster } else { 292 1.3 oster rf_InitNode(xorNode, rf_wait, RF_FALSE, redFunc, rf_NullNodeUndoFunc, NULL, 1, 293 1.3 oster 1, 2 * (nWndNodes + nRodNodes) + 1, nfaults, dag_h, "Xr ", allocList); 294 1.3 oster } 295 1.3 oster xorNode->flags |= RF_DAGNODE_FLAG_YIELD; 296 1.3 oster for (i = 0; i < nWndNodes; i++) { 297 1.3 oster xorNode->params[2 * i + 0] = wndNodes[i].params[0]; /* pda */ 298 1.3 oster xorNode->params[2 * i + 1] = wndNodes[i].params[1]; /* buf ptr */ 299 1.3 oster } 300 1.3 oster for (i = 0; i < nRodNodes; i++) { 301 1.3 oster xorNode->params[2 * (nWndNodes + i) + 0] = rodNodes[i].params[0]; /* pda */ 302 1.3 oster xorNode->params[2 * (nWndNodes + i) + 1] = rodNodes[i].params[1]; /* buf ptr */ 303 1.3 oster } 304 1.3 oster /* xor node needs to get at RAID information */ 305 1.3 oster xorNode->params[2 * (nWndNodes + nRodNodes)].p = raidPtr; 306 1.3 oster 307 1.3 oster /* 308 1.3 oster * Look for an Rod node that reads a complete SU. If none, alloc a buffer 309 1.3 oster * to receive the parity info. Note that we can't use a new data buffer 310 1.3 oster * because it will not have gotten written when the xor occurs. 311 1.3 oster */ 312 1.3 oster if (allowBufferRecycle) { 313 1.3 oster for (i = 0; i < nRodNodes; i++) { 314 1.3 oster if (((RF_PhysDiskAddr_t *) rodNodes[i].params[0].p)->numSector == raidPtr->Layout.sectorsPerStripeUnit) 315 1.3 oster break; 316 1.3 oster } 317 1.3 oster } 318 1.3 oster if ((!allowBufferRecycle) || (i == nRodNodes)) { 319 1.3 oster RF_CallocAndAdd(xorNode->results[0], 1, 320 1.3 oster rf_RaidAddressToByte(raidPtr, raidPtr->Layout.sectorsPerStripeUnit), 321 1.3 oster (void *), allocList); 322 1.3 oster } else { 323 1.3 oster xorNode->results[0] = rodNodes[i].params[1].p; 324 1.3 oster } 325 1.3 oster 326 1.3 oster /* initialize the Wnp node */ 327 1.3 oster rf_InitNode(wnpNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 328 1.3 oster rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnp", allocList); 329 1.3 oster wnpNode->params[0].p = asmap->parityInfo; 330 1.3 oster wnpNode->params[1].p = xorNode->results[0]; 331 1.3 oster wnpNode->params[2].v = parityStripeID; 332 1.3 oster wnpNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 333 1.3 oster /* parityInfo must describe entire parity unit */ 334 1.3 oster RF_ASSERT(asmap->parityInfo->next == NULL); 335 1.3 oster 336 1.3 oster if (nfaults == 2) { 337 1.3 oster /* 338 1.3 oster * We never try to recycle a buffer for the Q calcuation 339 1.3 oster * in addition to the parity. This would cause two buffers 340 1.3 oster * to get smashed during the P and Q calculation, guaranteeing 341 1.3 oster * one would be wrong. 342 1.3 oster */ 343 1.3 oster RF_CallocAndAdd(xorNode->results[1], 1, 344 1.3 oster rf_RaidAddressToByte(raidPtr, raidPtr->Layout.sectorsPerStripeUnit), 345 1.3 oster (void *), allocList); 346 1.3 oster rf_InitNode(wnqNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 347 1.3 oster rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnq", allocList); 348 1.3 oster wnqNode->params[0].p = asmap->qInfo; 349 1.3 oster wnqNode->params[1].p = xorNode->results[1]; 350 1.3 oster wnqNode->params[2].v = parityStripeID; 351 1.3 oster wnqNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 352 1.3 oster /* parityInfo must describe entire parity unit */ 353 1.3 oster RF_ASSERT(asmap->parityInfo->next == NULL); 354 1.3 oster } 355 1.3 oster /* 356 1.3 oster * Connect nodes to form graph. 357 1.3 oster */ 358 1.3 oster 359 1.3 oster /* connect dag header to block node */ 360 1.3 oster RF_ASSERT(blockNode->numAntecedents == 0); 361 1.3 oster dag_h->succedents[0] = blockNode; 362 1.3 oster 363 1.3 oster if (nRodNodes > 0) { 364 1.3 oster /* connect the block node to the Rod nodes */ 365 1.3 oster RF_ASSERT(blockNode->numSuccedents == nRodNodes); 366 1.3 oster RF_ASSERT(xorNode->numAntecedents == nRodNodes); 367 1.3 oster for (i = 0; i < nRodNodes; i++) { 368 1.3 oster RF_ASSERT(rodNodes[i].numAntecedents == 1); 369 1.3 oster blockNode->succedents[i] = &rodNodes[i]; 370 1.3 oster rodNodes[i].antecedents[0] = blockNode; 371 1.3 oster rodNodes[i].antType[0] = rf_control; 372 1.3 oster 373 1.3 oster /* connect the Rod nodes to the Xor node */ 374 1.3 oster RF_ASSERT(rodNodes[i].numSuccedents == 1); 375 1.3 oster rodNodes[i].succedents[0] = xorNode; 376 1.3 oster xorNode->antecedents[i] = &rodNodes[i]; 377 1.3 oster xorNode->antType[i] = rf_trueData; 378 1.3 oster } 379 1.3 oster } else { 380 1.3 oster /* connect the block node to the Xor node */ 381 1.3 oster RF_ASSERT(blockNode->numSuccedents == 1); 382 1.3 oster RF_ASSERT(xorNode->numAntecedents == 1); 383 1.3 oster blockNode->succedents[0] = xorNode; 384 1.3 oster xorNode->antecedents[0] = blockNode; 385 1.3 oster xorNode->antType[0] = rf_control; 386 1.3 oster } 387 1.3 oster 388 1.3 oster /* connect the xor node to the commit node */ 389 1.3 oster RF_ASSERT(xorNode->numSuccedents == 1); 390 1.3 oster RF_ASSERT(commitNode->numAntecedents == 1); 391 1.3 oster xorNode->succedents[0] = commitNode; 392 1.3 oster commitNode->antecedents[0] = xorNode; 393 1.3 oster commitNode->antType[0] = rf_control; 394 1.3 oster 395 1.3 oster /* connect the commit node to the write nodes */ 396 1.3 oster RF_ASSERT(commitNode->numSuccedents == nWndNodes + nfaults); 397 1.3 oster for (i = 0; i < nWndNodes; i++) { 398 1.3 oster RF_ASSERT(wndNodes->numAntecedents == 1); 399 1.3 oster commitNode->succedents[i] = &wndNodes[i]; 400 1.3 oster wndNodes[i].antecedents[0] = commitNode; 401 1.3 oster wndNodes[i].antType[0] = rf_control; 402 1.3 oster } 403 1.3 oster RF_ASSERT(wnpNode->numAntecedents == 1); 404 1.3 oster commitNode->succedents[nWndNodes] = wnpNode; 405 1.3 oster wnpNode->antecedents[0] = commitNode; 406 1.3 oster wnpNode->antType[0] = rf_trueData; 407 1.3 oster if (nfaults == 2) { 408 1.3 oster RF_ASSERT(wnqNode->numAntecedents == 1); 409 1.3 oster commitNode->succedents[nWndNodes + 1] = wnqNode; 410 1.3 oster wnqNode->antecedents[0] = commitNode; 411 1.3 oster wnqNode->antType[0] = rf_trueData; 412 1.3 oster } 413 1.3 oster /* connect the write nodes to the term node */ 414 1.3 oster RF_ASSERT(termNode->numAntecedents == nWndNodes + nfaults); 415 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 416 1.3 oster for (i = 0; i < nWndNodes; i++) { 417 1.3 oster RF_ASSERT(wndNodes->numSuccedents == 1); 418 1.3 oster wndNodes[i].succedents[0] = termNode; 419 1.3 oster termNode->antecedents[i] = &wndNodes[i]; 420 1.3 oster termNode->antType[i] = rf_control; 421 1.3 oster } 422 1.3 oster RF_ASSERT(wnpNode->numSuccedents == 1); 423 1.3 oster wnpNode->succedents[0] = termNode; 424 1.3 oster termNode->antecedents[nWndNodes] = wnpNode; 425 1.3 oster termNode->antType[nWndNodes] = rf_control; 426 1.3 oster if (nfaults == 2) { 427 1.3 oster RF_ASSERT(wnqNode->numSuccedents == 1); 428 1.3 oster wnqNode->succedents[0] = termNode; 429 1.3 oster termNode->antecedents[nWndNodes + 1] = wnqNode; 430 1.3 oster termNode->antType[nWndNodes + 1] = rf_control; 431 1.3 oster } 432 1.1 oster } 433 1.1 oster /****************************************************************************** 434 1.1 oster * 435 1.1 oster * creates a DAG to perform a small-write operation (either raid 5 or pq), 436 1.1 oster * which is as follows: 437 1.1 oster * 438 1.1 oster * Hdr -> Nil -> Rop -> Xor -> Cmt ----> Wnp [Unp] --> Trm 439 1.1 oster * \- Rod X / \----> Wnd [Und]-/ 440 1.1 oster * [\- Rod X / \---> Wnd [Und]-/] 441 1.1 oster * [\- Roq -> Q / \--> Wnq [Unq]-/] 442 1.1 oster * 443 1.1 oster * Rop = read old parity 444 1.1 oster * Rod = read old data 445 1.1 oster * Roq = read old "q" 446 1.1 oster * Cmt = commit node 447 1.1 oster * Und = unlock data disk 448 1.1 oster * Unp = unlock parity disk 449 1.1 oster * Unq = unlock q disk 450 1.1 oster * Wnp = write new parity 451 1.1 oster * Wnd = write new data 452 1.1 oster * Wnq = write new "q" 453 1.1 oster * [ ] denotes optional segments in the graph 454 1.1 oster * 455 1.1 oster * Parameters: raidPtr - description of the physical array 456 1.1 oster * asmap - logical & physical addresses for this access 457 1.1 oster * bp - buffer ptr (holds write data) 458 1.3 oster * flags - general flags (e.g. disk locking) 459 1.1 oster * allocList - list of memory allocated in DAG creation 460 1.1 oster * pfuncs - list of parity generating functions 461 1.1 oster * qfuncs - list of q generating functions 462 1.1 oster * 463 1.1 oster * A null qfuncs indicates single fault tolerant 464 1.1 oster *****************************************************************************/ 465 1.1 oster 466 1.3 oster void 467 1.3 oster rf_CommonCreateSmallWriteDAG( 468 1.3 oster RF_Raid_t * raidPtr, 469 1.3 oster RF_AccessStripeMap_t * asmap, 470 1.3 oster RF_DagHeader_t * dag_h, 471 1.3 oster void *bp, 472 1.3 oster RF_RaidAccessFlags_t flags, 473 1.3 oster RF_AllocListElem_t * allocList, 474 1.3 oster RF_RedFuncs_t * pfuncs, 475 1.3 oster RF_RedFuncs_t * qfuncs) 476 1.1 oster { 477 1.3 oster RF_DagNode_t *readDataNodes, *readParityNodes, *readQNodes, *termNode; 478 1.3 oster RF_DagNode_t *unlockDataNodes, *unlockParityNodes, *unlockQNodes; 479 1.3 oster RF_DagNode_t *xorNodes, *qNodes, *blockNode, *commitNode, *nodes; 480 1.3 oster RF_DagNode_t *writeDataNodes, *writeParityNodes, *writeQNodes; 481 1.3 oster int i, j, nNodes, totalNumNodes, lu_flag; 482 1.3 oster RF_ReconUnitNum_t which_ru; 483 1.3 oster int (*func) (RF_DagNode_t *), (*undoFunc) (RF_DagNode_t *); 484 1.3 oster int (*qfunc) (RF_DagNode_t *); 485 1.3 oster int numDataNodes, numParityNodes; 486 1.3 oster RF_StripeNum_t parityStripeID; 487 1.3 oster RF_PhysDiskAddr_t *pda; 488 1.3 oster char *name, *qname; 489 1.3 oster long nfaults; 490 1.3 oster 491 1.3 oster nfaults = qfuncs ? 2 : 1; 492 1.3 oster lu_flag = (rf_enableAtomicRMW) ? 1 : 0; /* lock/unlock flag */ 493 1.3 oster 494 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout), 495 1.3 oster asmap->raidAddress, &which_ru); 496 1.3 oster pda = asmap->physInfo; 497 1.3 oster numDataNodes = asmap->numStripeUnitsAccessed; 498 1.3 oster numParityNodes = (asmap->parityInfo->next) ? 2 : 1; 499 1.3 oster 500 1.3 oster if (rf_dagDebug) { 501 1.3 oster printf("[Creating small-write DAG]\n"); 502 1.3 oster } 503 1.3 oster RF_ASSERT(numDataNodes > 0); 504 1.3 oster dag_h->creator = "SmallWriteDAG"; 505 1.3 oster 506 1.3 oster dag_h->numCommitNodes = 1; 507 1.3 oster dag_h->numCommits = 0; 508 1.3 oster dag_h->numSuccedents = 1; 509 1.3 oster 510 1.3 oster /* 511 1.3 oster * DAG creation occurs in four steps: 512 1.3 oster * 1. count the number of nodes in the DAG 513 1.3 oster * 2. create the nodes 514 1.3 oster * 3. initialize the nodes 515 1.3 oster * 4. connect the nodes 516 1.3 oster */ 517 1.3 oster 518 1.3 oster /* 519 1.3 oster * Step 1. compute number of nodes in the graph 520 1.3 oster */ 521 1.3 oster 522 1.3 oster /* number of nodes: a read and write for each data unit a redundancy 523 1.3 oster * computation node for each parity node (nfaults * nparity) a read 524 1.3 oster * and write for each parity unit a block and commit node (2) a 525 1.3 oster * terminate node if atomic RMW an unlock node for each data unit, 526 1.3 oster * redundancy unit */ 527 1.3 oster totalNumNodes = (2 * numDataNodes) + (nfaults * numParityNodes) 528 1.3 oster + (nfaults * 2 * numParityNodes) + 3; 529 1.3 oster if (lu_flag) { 530 1.3 oster totalNumNodes += (numDataNodes + (nfaults * numParityNodes)); 531 1.3 oster } 532 1.3 oster /* 533 1.3 oster * Step 2. create the nodes 534 1.3 oster */ 535 1.3 oster RF_CallocAndAdd(nodes, totalNumNodes, sizeof(RF_DagNode_t), 536 1.3 oster (RF_DagNode_t *), allocList); 537 1.3 oster i = 0; 538 1.3 oster blockNode = &nodes[i]; 539 1.3 oster i += 1; 540 1.3 oster commitNode = &nodes[i]; 541 1.3 oster i += 1; 542 1.3 oster readDataNodes = &nodes[i]; 543 1.3 oster i += numDataNodes; 544 1.3 oster readParityNodes = &nodes[i]; 545 1.3 oster i += numParityNodes; 546 1.3 oster writeDataNodes = &nodes[i]; 547 1.3 oster i += numDataNodes; 548 1.3 oster writeParityNodes = &nodes[i]; 549 1.3 oster i += numParityNodes; 550 1.3 oster xorNodes = &nodes[i]; 551 1.3 oster i += numParityNodes; 552 1.3 oster termNode = &nodes[i]; 553 1.3 oster i += 1; 554 1.3 oster if (lu_flag) { 555 1.3 oster unlockDataNodes = &nodes[i]; 556 1.3 oster i += numDataNodes; 557 1.3 oster unlockParityNodes = &nodes[i]; 558 1.3 oster i += numParityNodes; 559 1.3 oster } else { 560 1.3 oster unlockDataNodes = unlockParityNodes = NULL; 561 1.3 oster } 562 1.3 oster if (nfaults == 2) { 563 1.3 oster readQNodes = &nodes[i]; 564 1.3 oster i += numParityNodes; 565 1.3 oster writeQNodes = &nodes[i]; 566 1.3 oster i += numParityNodes; 567 1.3 oster qNodes = &nodes[i]; 568 1.3 oster i += numParityNodes; 569 1.3 oster if (lu_flag) { 570 1.3 oster unlockQNodes = &nodes[i]; 571 1.3 oster i += numParityNodes; 572 1.3 oster } else { 573 1.3 oster unlockQNodes = NULL; 574 1.3 oster } 575 1.3 oster } else { 576 1.3 oster readQNodes = writeQNodes = qNodes = unlockQNodes = NULL; 577 1.3 oster } 578 1.3 oster RF_ASSERT(i == totalNumNodes); 579 1.3 oster 580 1.3 oster /* 581 1.3 oster * Step 3. initialize the nodes 582 1.3 oster */ 583 1.3 oster /* initialize block node (Nil) */ 584 1.3 oster nNodes = numDataNodes + (nfaults * numParityNodes); 585 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 586 1.3 oster NULL, nNodes, 0, 0, 0, dag_h, "Nil", allocList); 587 1.3 oster 588 1.3 oster /* initialize commit node (Cmt) */ 589 1.3 oster rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 590 1.3 oster NULL, nNodes, (nfaults * numParityNodes), 0, 0, dag_h, "Cmt", allocList); 591 1.3 oster 592 1.3 oster /* initialize terminate node (Trm) */ 593 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, 594 1.3 oster NULL, 0, nNodes, 0, 0, dag_h, "Trm", allocList); 595 1.3 oster 596 1.3 oster /* initialize nodes which read old data (Rod) */ 597 1.3 oster for (i = 0; i < numDataNodes; i++) { 598 1.3 oster rf_InitNode(&readDataNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, 599 1.3 oster rf_GenericWakeupFunc, (nfaults * numParityNodes), 1, 4, 0, dag_h, 600 1.3 oster "Rod", allocList); 601 1.3 oster RF_ASSERT(pda != NULL); 602 1.3 oster /* physical disk addr desc */ 603 1.3 oster readDataNodes[i].params[0].p = pda; 604 1.3 oster /* buffer to hold old data */ 605 1.3 oster readDataNodes[i].params[1].p = rf_AllocBuffer(raidPtr, 606 1.3 oster dag_h, pda, allocList); 607 1.3 oster readDataNodes[i].params[2].v = parityStripeID; 608 1.3 oster readDataNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 609 1.3 oster lu_flag, 0, which_ru); 610 1.3 oster pda = pda->next; 611 1.3 oster for (j = 0; j < readDataNodes[i].numSuccedents; j++) { 612 1.3 oster readDataNodes[i].propList[j] = NULL; 613 1.3 oster } 614 1.3 oster } 615 1.3 oster 616 1.3 oster /* initialize nodes which read old parity (Rop) */ 617 1.3 oster pda = asmap->parityInfo; 618 1.3 oster i = 0; 619 1.3 oster for (i = 0; i < numParityNodes; i++) { 620 1.3 oster RF_ASSERT(pda != NULL); 621 1.3 oster rf_InitNode(&readParityNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, 622 1.3 oster rf_DiskReadUndoFunc, rf_GenericWakeupFunc, numParityNodes, 1, 4, 623 1.3 oster 0, dag_h, "Rop", allocList); 624 1.3 oster readParityNodes[i].params[0].p = pda; 625 1.3 oster /* buffer to hold old parity */ 626 1.3 oster readParityNodes[i].params[1].p = rf_AllocBuffer(raidPtr, 627 1.3 oster dag_h, pda, allocList); 628 1.3 oster readParityNodes[i].params[2].v = parityStripeID; 629 1.3 oster readParityNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 630 1.3 oster lu_flag, 0, which_ru); 631 1.3 oster pda = pda->next; 632 1.3 oster for (j = 0; j < readParityNodes[i].numSuccedents; j++) { 633 1.3 oster readParityNodes[i].propList[0] = NULL; 634 1.3 oster } 635 1.3 oster } 636 1.3 oster 637 1.3 oster /* initialize nodes which read old Q (Roq) */ 638 1.3 oster if (nfaults == 2) { 639 1.3 oster pda = asmap->qInfo; 640 1.3 oster for (i = 0; i < numParityNodes; i++) { 641 1.3 oster RF_ASSERT(pda != NULL); 642 1.3 oster rf_InitNode(&readQNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, 643 1.3 oster rf_GenericWakeupFunc, numParityNodes, 1, 4, 0, dag_h, "Roq", allocList); 644 1.3 oster readQNodes[i].params[0].p = pda; 645 1.3 oster /* buffer to hold old Q */ 646 1.3 oster readQNodes[i].params[1].p = rf_AllocBuffer(raidPtr, dag_h, pda, 647 1.3 oster allocList); 648 1.3 oster readQNodes[i].params[2].v = parityStripeID; 649 1.3 oster readQNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 650 1.3 oster lu_flag, 0, which_ru); 651 1.3 oster pda = pda->next; 652 1.3 oster for (j = 0; j < readQNodes[i].numSuccedents; j++) { 653 1.3 oster readQNodes[i].propList[0] = NULL; 654 1.3 oster } 655 1.3 oster } 656 1.3 oster } 657 1.3 oster /* initialize nodes which write new data (Wnd) */ 658 1.3 oster pda = asmap->physInfo; 659 1.3 oster for (i = 0; i < numDataNodes; i++) { 660 1.3 oster RF_ASSERT(pda != NULL); 661 1.3 oster rf_InitNode(&writeDataNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, 662 1.3 oster rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, 663 1.3 oster "Wnd", allocList); 664 1.3 oster /* physical disk addr desc */ 665 1.3 oster writeDataNodes[i].params[0].p = pda; 666 1.3 oster /* buffer holding new data to be written */ 667 1.3 oster writeDataNodes[i].params[1].p = pda->bufPtr; 668 1.3 oster writeDataNodes[i].params[2].v = parityStripeID; 669 1.3 oster writeDataNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 670 1.3 oster 0, 0, which_ru); 671 1.3 oster if (lu_flag) { 672 1.3 oster /* initialize node to unlock the disk queue */ 673 1.3 oster rf_InitNode(&unlockDataNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, 674 1.3 oster rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, 675 1.3 oster "Und", allocList); 676 1.3 oster /* physical disk addr desc */ 677 1.3 oster unlockDataNodes[i].params[0].p = pda; 678 1.3 oster unlockDataNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 679 1.3 oster 0, lu_flag, which_ru); 680 1.3 oster } 681 1.3 oster pda = pda->next; 682 1.3 oster } 683 1.3 oster 684 1.3 oster /* 685 1.3 oster * Initialize nodes which compute new parity and Q. 686 1.3 oster */ 687 1.3 oster /* 688 1.3 oster * We use the simple XOR func in the double-XOR case, and when 689 1.3 oster * we're accessing only a portion of one stripe unit. The distinction 690 1.3 oster * between the two is that the regular XOR func assumes that the targbuf 691 1.3 oster * is a full SU in size, and examines the pda associated with the buffer 692 1.3 oster * to decide where within the buffer to XOR the data, whereas 693 1.3 oster * the simple XOR func just XORs the data into the start of the buffer. 694 1.3 oster */ 695 1.3 oster if ((numParityNodes == 2) || ((numDataNodes == 1) 696 1.3 oster && (asmap->totalSectorsAccessed < raidPtr->Layout.sectorsPerStripeUnit))) { 697 1.3 oster func = pfuncs->simple; 698 1.3 oster undoFunc = rf_NullNodeUndoFunc; 699 1.3 oster name = pfuncs->SimpleName; 700 1.3 oster if (qfuncs) { 701 1.3 oster qfunc = qfuncs->simple; 702 1.3 oster qname = qfuncs->SimpleName; 703 1.3 oster } else { 704 1.3 oster qfunc = NULL; 705 1.3 oster qname = NULL; 706 1.3 oster } 707 1.3 oster } else { 708 1.3 oster func = pfuncs->regular; 709 1.3 oster undoFunc = rf_NullNodeUndoFunc; 710 1.3 oster name = pfuncs->RegularName; 711 1.3 oster if (qfuncs) { 712 1.3 oster qfunc = qfuncs->regular; 713 1.3 oster qname = qfuncs->RegularName; 714 1.3 oster } else { 715 1.3 oster qfunc = NULL; 716 1.3 oster qname = NULL; 717 1.3 oster } 718 1.3 oster } 719 1.3 oster /* 720 1.3 oster * Initialize the xor nodes: params are {pda,buf} 721 1.3 oster * from {Rod,Wnd,Rop} nodes, and raidPtr 722 1.3 oster */ 723 1.3 oster if (numParityNodes == 2) { 724 1.3 oster /* double-xor case */ 725 1.3 oster for (i = 0; i < numParityNodes; i++) { 726 1.3 oster /* note: no wakeup func for xor */ 727 1.3 oster rf_InitNode(&xorNodes[i], rf_wait, RF_FALSE, func, undoFunc, NULL, 728 1.3 oster 1, (numDataNodes + numParityNodes), 7, 1, dag_h, name, allocList); 729 1.3 oster xorNodes[i].flags |= RF_DAGNODE_FLAG_YIELD; 730 1.3 oster xorNodes[i].params[0] = readDataNodes[i].params[0]; 731 1.3 oster xorNodes[i].params[1] = readDataNodes[i].params[1]; 732 1.3 oster xorNodes[i].params[2] = readParityNodes[i].params[0]; 733 1.3 oster xorNodes[i].params[3] = readParityNodes[i].params[1]; 734 1.3 oster xorNodes[i].params[4] = writeDataNodes[i].params[0]; 735 1.3 oster xorNodes[i].params[5] = writeDataNodes[i].params[1]; 736 1.3 oster xorNodes[i].params[6].p = raidPtr; 737 1.3 oster /* use old parity buf as target buf */ 738 1.3 oster xorNodes[i].results[0] = readParityNodes[i].params[1].p; 739 1.3 oster if (nfaults == 2) { 740 1.3 oster /* note: no wakeup func for qor */ 741 1.3 oster rf_InitNode(&qNodes[i], rf_wait, RF_FALSE, qfunc, undoFunc, NULL, 1, 742 1.3 oster (numDataNodes + numParityNodes), 7, 1, dag_h, qname, allocList); 743 1.3 oster qNodes[i].params[0] = readDataNodes[i].params[0]; 744 1.3 oster qNodes[i].params[1] = readDataNodes[i].params[1]; 745 1.3 oster qNodes[i].params[2] = readQNodes[i].params[0]; 746 1.3 oster qNodes[i].params[3] = readQNodes[i].params[1]; 747 1.3 oster qNodes[i].params[4] = writeDataNodes[i].params[0]; 748 1.3 oster qNodes[i].params[5] = writeDataNodes[i].params[1]; 749 1.3 oster qNodes[i].params[6].p = raidPtr; 750 1.3 oster /* use old Q buf as target buf */ 751 1.3 oster qNodes[i].results[0] = readQNodes[i].params[1].p; 752 1.3 oster } 753 1.3 oster } 754 1.3 oster } else { 755 1.3 oster /* there is only one xor node in this case */ 756 1.3 oster rf_InitNode(&xorNodes[0], rf_wait, RF_FALSE, func, undoFunc, NULL, 1, 757 1.3 oster (numDataNodes + numParityNodes), 758 1.3 oster (2 * (numDataNodes + numDataNodes + 1) + 1), 1, dag_h, name, allocList); 759 1.3 oster xorNodes[0].flags |= RF_DAGNODE_FLAG_YIELD; 760 1.3 oster for (i = 0; i < numDataNodes + 1; i++) { 761 1.3 oster /* set up params related to Rod and Rop nodes */ 762 1.3 oster xorNodes[0].params[2 * i + 0] = readDataNodes[i].params[0]; /* pda */ 763 1.3 oster xorNodes[0].params[2 * i + 1] = readDataNodes[i].params[1]; /* buffer ptr */ 764 1.3 oster } 765 1.3 oster for (i = 0; i < numDataNodes; i++) { 766 1.3 oster /* set up params related to Wnd and Wnp nodes */ 767 1.3 oster xorNodes[0].params[2 * (numDataNodes + 1 + i) + 0] = /* pda */ 768 1.3 oster writeDataNodes[i].params[0]; 769 1.3 oster xorNodes[0].params[2 * (numDataNodes + 1 + i) + 1] = /* buffer ptr */ 770 1.3 oster writeDataNodes[i].params[1]; 771 1.3 oster } 772 1.3 oster /* xor node needs to get at RAID information */ 773 1.3 oster xorNodes[0].params[2 * (numDataNodes + numDataNodes + 1)].p = raidPtr; 774 1.3 oster xorNodes[0].results[0] = readParityNodes[0].params[1].p; 775 1.3 oster if (nfaults == 2) { 776 1.3 oster rf_InitNode(&qNodes[0], rf_wait, RF_FALSE, qfunc, undoFunc, NULL, 1, 777 1.3 oster (numDataNodes + numParityNodes), 778 1.3 oster (2 * (numDataNodes + numDataNodes + 1) + 1), 1, dag_h, 779 1.3 oster qname, allocList); 780 1.3 oster for (i = 0; i < numDataNodes; i++) { 781 1.3 oster /* set up params related to Rod */ 782 1.3 oster qNodes[0].params[2 * i + 0] = readDataNodes[i].params[0]; /* pda */ 783 1.3 oster qNodes[0].params[2 * i + 1] = readDataNodes[i].params[1]; /* buffer ptr */ 784 1.3 oster } 785 1.3 oster /* and read old q */ 786 1.3 oster qNodes[0].params[2 * numDataNodes + 0] = /* pda */ 787 1.3 oster readQNodes[0].params[0]; 788 1.3 oster qNodes[0].params[2 * numDataNodes + 1] = /* buffer ptr */ 789 1.3 oster readQNodes[0].params[1]; 790 1.3 oster for (i = 0; i < numDataNodes; i++) { 791 1.3 oster /* set up params related to Wnd nodes */ 792 1.3 oster qNodes[0].params[2 * (numDataNodes + 1 + i) + 0] = /* pda */ 793 1.3 oster writeDataNodes[i].params[0]; 794 1.3 oster qNodes[0].params[2 * (numDataNodes + 1 + i) + 1] = /* buffer ptr */ 795 1.3 oster writeDataNodes[i].params[1]; 796 1.3 oster } 797 1.3 oster /* xor node needs to get at RAID information */ 798 1.3 oster qNodes[0].params[2 * (numDataNodes + numDataNodes + 1)].p = raidPtr; 799 1.3 oster qNodes[0].results[0] = readQNodes[0].params[1].p; 800 1.3 oster } 801 1.3 oster } 802 1.3 oster 803 1.3 oster /* initialize nodes which write new parity (Wnp) */ 804 1.3 oster pda = asmap->parityInfo; 805 1.3 oster for (i = 0; i < numParityNodes; i++) { 806 1.3 oster rf_InitNode(&writeParityNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, 807 1.3 oster rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, 808 1.3 oster "Wnp", allocList); 809 1.3 oster RF_ASSERT(pda != NULL); 810 1.3 oster writeParityNodes[i].params[0].p = pda; /* param 1 (bufPtr) 811 1.3 oster * filled in by xor node */ 812 1.3 oster writeParityNodes[i].params[1].p = xorNodes[i].results[0]; /* buffer pointer for 813 1.3 oster * parity write 814 1.3 oster * operation */ 815 1.3 oster writeParityNodes[i].params[2].v = parityStripeID; 816 1.3 oster writeParityNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 817 1.3 oster 0, 0, which_ru); 818 1.3 oster if (lu_flag) { 819 1.3 oster /* initialize node to unlock the disk queue */ 820 1.3 oster rf_InitNode(&unlockParityNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, 821 1.3 oster rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, 822 1.3 oster "Unp", allocList); 823 1.3 oster unlockParityNodes[i].params[0].p = pda; /* physical disk addr 824 1.3 oster * desc */ 825 1.3 oster unlockParityNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 826 1.3 oster 0, lu_flag, which_ru); 827 1.3 oster } 828 1.3 oster pda = pda->next; 829 1.3 oster } 830 1.3 oster 831 1.3 oster /* initialize nodes which write new Q (Wnq) */ 832 1.3 oster if (nfaults == 2) { 833 1.3 oster pda = asmap->qInfo; 834 1.3 oster for (i = 0; i < numParityNodes; i++) { 835 1.3 oster rf_InitNode(&writeQNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, 836 1.3 oster rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, 837 1.3 oster "Wnq", allocList); 838 1.3 oster RF_ASSERT(pda != NULL); 839 1.3 oster writeQNodes[i].params[0].p = pda; /* param 1 (bufPtr) 840 1.3 oster * filled in by xor node */ 841 1.3 oster writeQNodes[i].params[1].p = qNodes[i].results[0]; /* buffer pointer for 842 1.3 oster * parity write 843 1.3 oster * operation */ 844 1.3 oster writeQNodes[i].params[2].v = parityStripeID; 845 1.3 oster writeQNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 846 1.3 oster 0, 0, which_ru); 847 1.3 oster if (lu_flag) { 848 1.3 oster /* initialize node to unlock the disk queue */ 849 1.3 oster rf_InitNode(&unlockQNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, 850 1.3 oster rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, 851 1.3 oster "Unq", allocList); 852 1.3 oster unlockQNodes[i].params[0].p = pda; /* physical disk addr 853 1.3 oster * desc */ 854 1.3 oster unlockQNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 855 1.3 oster 0, lu_flag, which_ru); 856 1.3 oster } 857 1.3 oster pda = pda->next; 858 1.3 oster } 859 1.3 oster } 860 1.3 oster /* 861 1.3 oster * Step 4. connect the nodes. 862 1.3 oster */ 863 1.3 oster 864 1.3 oster /* connect header to block node */ 865 1.3 oster dag_h->succedents[0] = blockNode; 866 1.3 oster 867 1.3 oster /* connect block node to read old data nodes */ 868 1.3 oster RF_ASSERT(blockNode->numSuccedents == (numDataNodes + (numParityNodes * nfaults))); 869 1.3 oster for (i = 0; i < numDataNodes; i++) { 870 1.3 oster blockNode->succedents[i] = &readDataNodes[i]; 871 1.3 oster RF_ASSERT(readDataNodes[i].numAntecedents == 1); 872 1.3 oster readDataNodes[i].antecedents[0] = blockNode; 873 1.3 oster readDataNodes[i].antType[0] = rf_control; 874 1.3 oster } 875 1.3 oster 876 1.3 oster /* connect block node to read old parity nodes */ 877 1.3 oster for (i = 0; i < numParityNodes; i++) { 878 1.3 oster blockNode->succedents[numDataNodes + i] = &readParityNodes[i]; 879 1.3 oster RF_ASSERT(readParityNodes[i].numAntecedents == 1); 880 1.3 oster readParityNodes[i].antecedents[0] = blockNode; 881 1.3 oster readParityNodes[i].antType[0] = rf_control; 882 1.3 oster } 883 1.3 oster 884 1.3 oster /* connect block node to read old Q nodes */ 885 1.3 oster if (nfaults == 2) { 886 1.3 oster for (i = 0; i < numParityNodes; i++) { 887 1.3 oster blockNode->succedents[numDataNodes + numParityNodes + i] = &readQNodes[i]; 888 1.3 oster RF_ASSERT(readQNodes[i].numAntecedents == 1); 889 1.3 oster readQNodes[i].antecedents[0] = blockNode; 890 1.3 oster readQNodes[i].antType[0] = rf_control; 891 1.3 oster } 892 1.3 oster } 893 1.3 oster /* connect read old data nodes to xor nodes */ 894 1.3 oster for (i = 0; i < numDataNodes; i++) { 895 1.3 oster RF_ASSERT(readDataNodes[i].numSuccedents == (nfaults * numParityNodes)); 896 1.3 oster for (j = 0; j < numParityNodes; j++) { 897 1.3 oster RF_ASSERT(xorNodes[j].numAntecedents == numDataNodes + numParityNodes); 898 1.3 oster readDataNodes[i].succedents[j] = &xorNodes[j]; 899 1.3 oster xorNodes[j].antecedents[i] = &readDataNodes[i]; 900 1.3 oster xorNodes[j].antType[i] = rf_trueData; 901 1.3 oster } 902 1.3 oster } 903 1.3 oster 904 1.3 oster /* connect read old data nodes to q nodes */ 905 1.3 oster if (nfaults == 2) { 906 1.3 oster for (i = 0; i < numDataNodes; i++) { 907 1.3 oster for (j = 0; j < numParityNodes; j++) { 908 1.3 oster RF_ASSERT(qNodes[j].numAntecedents == numDataNodes + numParityNodes); 909 1.3 oster readDataNodes[i].succedents[numParityNodes + j] = &qNodes[j]; 910 1.3 oster qNodes[j].antecedents[i] = &readDataNodes[i]; 911 1.3 oster qNodes[j].antType[i] = rf_trueData; 912 1.3 oster } 913 1.3 oster } 914 1.3 oster } 915 1.3 oster /* connect read old parity nodes to xor nodes */ 916 1.3 oster for (i = 0; i < numParityNodes; i++) { 917 1.3 oster RF_ASSERT(readParityNodes[i].numSuccedents == numParityNodes); 918 1.3 oster for (j = 0; j < numParityNodes; j++) { 919 1.3 oster readParityNodes[i].succedents[j] = &xorNodes[j]; 920 1.3 oster xorNodes[j].antecedents[numDataNodes + i] = &readParityNodes[i]; 921 1.3 oster xorNodes[j].antType[numDataNodes + i] = rf_trueData; 922 1.3 oster } 923 1.3 oster } 924 1.3 oster 925 1.3 oster /* connect read old q nodes to q nodes */ 926 1.3 oster if (nfaults == 2) { 927 1.3 oster for (i = 0; i < numParityNodes; i++) { 928 1.3 oster RF_ASSERT(readParityNodes[i].numSuccedents == numParityNodes); 929 1.3 oster for (j = 0; j < numParityNodes; j++) { 930 1.3 oster readQNodes[i].succedents[j] = &qNodes[j]; 931 1.3 oster qNodes[j].antecedents[numDataNodes + i] = &readQNodes[i]; 932 1.3 oster qNodes[j].antType[numDataNodes + i] = rf_trueData; 933 1.3 oster } 934 1.3 oster } 935 1.3 oster } 936 1.3 oster /* connect xor nodes to commit node */ 937 1.3 oster RF_ASSERT(commitNode->numAntecedents == (nfaults * numParityNodes)); 938 1.3 oster for (i = 0; i < numParityNodes; i++) { 939 1.3 oster RF_ASSERT(xorNodes[i].numSuccedents == 1); 940 1.3 oster xorNodes[i].succedents[0] = commitNode; 941 1.3 oster commitNode->antecedents[i] = &xorNodes[i]; 942 1.3 oster commitNode->antType[i] = rf_control; 943 1.3 oster } 944 1.3 oster 945 1.3 oster /* connect q nodes to commit node */ 946 1.3 oster if (nfaults == 2) { 947 1.3 oster for (i = 0; i < numParityNodes; i++) { 948 1.3 oster RF_ASSERT(qNodes[i].numSuccedents == 1); 949 1.3 oster qNodes[i].succedents[0] = commitNode; 950 1.3 oster commitNode->antecedents[i + numParityNodes] = &qNodes[i]; 951 1.3 oster commitNode->antType[i + numParityNodes] = rf_control; 952 1.3 oster } 953 1.3 oster } 954 1.3 oster /* connect commit node to write nodes */ 955 1.3 oster RF_ASSERT(commitNode->numSuccedents == (numDataNodes + (nfaults * numParityNodes))); 956 1.3 oster for (i = 0; i < numDataNodes; i++) { 957 1.3 oster RF_ASSERT(writeDataNodes[i].numAntecedents == 1); 958 1.3 oster commitNode->succedents[i] = &writeDataNodes[i]; 959 1.3 oster writeDataNodes[i].antecedents[0] = commitNode; 960 1.3 oster writeDataNodes[i].antType[0] = rf_trueData; 961 1.3 oster } 962 1.3 oster for (i = 0; i < numParityNodes; i++) { 963 1.3 oster RF_ASSERT(writeParityNodes[i].numAntecedents == 1); 964 1.3 oster commitNode->succedents[i + numDataNodes] = &writeParityNodes[i]; 965 1.3 oster writeParityNodes[i].antecedents[0] = commitNode; 966 1.3 oster writeParityNodes[i].antType[0] = rf_trueData; 967 1.3 oster } 968 1.3 oster if (nfaults == 2) { 969 1.3 oster for (i = 0; i < numParityNodes; i++) { 970 1.3 oster RF_ASSERT(writeQNodes[i].numAntecedents == 1); 971 1.3 oster commitNode->succedents[i + numDataNodes + numParityNodes] = &writeQNodes[i]; 972 1.3 oster writeQNodes[i].antecedents[0] = commitNode; 973 1.3 oster writeQNodes[i].antType[0] = rf_trueData; 974 1.3 oster } 975 1.3 oster } 976 1.3 oster RF_ASSERT(termNode->numAntecedents == (numDataNodes + (nfaults * numParityNodes))); 977 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 978 1.3 oster for (i = 0; i < numDataNodes; i++) { 979 1.3 oster if (lu_flag) { 980 1.3 oster /* connect write new data nodes to unlock nodes */ 981 1.3 oster RF_ASSERT(writeDataNodes[i].numSuccedents == 1); 982 1.3 oster RF_ASSERT(unlockDataNodes[i].numAntecedents == 1); 983 1.3 oster writeDataNodes[i].succedents[0] = &unlockDataNodes[i]; 984 1.3 oster unlockDataNodes[i].antecedents[0] = &writeDataNodes[i]; 985 1.3 oster unlockDataNodes[i].antType[0] = rf_control; 986 1.3 oster 987 1.3 oster /* connect unlock nodes to term node */ 988 1.3 oster RF_ASSERT(unlockDataNodes[i].numSuccedents == 1); 989 1.3 oster unlockDataNodes[i].succedents[0] = termNode; 990 1.3 oster termNode->antecedents[i] = &unlockDataNodes[i]; 991 1.3 oster termNode->antType[i] = rf_control; 992 1.3 oster } else { 993 1.3 oster /* connect write new data nodes to term node */ 994 1.3 oster RF_ASSERT(writeDataNodes[i].numSuccedents == 1); 995 1.3 oster RF_ASSERT(termNode->numAntecedents == (numDataNodes + (nfaults * numParityNodes))); 996 1.3 oster writeDataNodes[i].succedents[0] = termNode; 997 1.3 oster termNode->antecedents[i] = &writeDataNodes[i]; 998 1.3 oster termNode->antType[i] = rf_control; 999 1.3 oster } 1000 1.3 oster } 1001 1.3 oster 1002 1.3 oster for (i = 0; i < numParityNodes; i++) { 1003 1.3 oster if (lu_flag) { 1004 1.3 oster /* connect write new parity nodes to unlock nodes */ 1005 1.3 oster RF_ASSERT(writeParityNodes[i].numSuccedents == 1); 1006 1.3 oster RF_ASSERT(unlockParityNodes[i].numAntecedents == 1); 1007 1.3 oster writeParityNodes[i].succedents[0] = &unlockParityNodes[i]; 1008 1.3 oster unlockParityNodes[i].antecedents[0] = &writeParityNodes[i]; 1009 1.3 oster unlockParityNodes[i].antType[0] = rf_control; 1010 1.3 oster 1011 1.3 oster /* connect unlock nodes to term node */ 1012 1.3 oster RF_ASSERT(unlockParityNodes[i].numSuccedents == 1); 1013 1.3 oster unlockParityNodes[i].succedents[0] = termNode; 1014 1.3 oster termNode->antecedents[numDataNodes + i] = &unlockParityNodes[i]; 1015 1.3 oster termNode->antType[numDataNodes + i] = rf_control; 1016 1.3 oster } else { 1017 1.3 oster RF_ASSERT(writeParityNodes[i].numSuccedents == 1); 1018 1.3 oster writeParityNodes[i].succedents[0] = termNode; 1019 1.3 oster termNode->antecedents[numDataNodes + i] = &writeParityNodes[i]; 1020 1.3 oster termNode->antType[numDataNodes + i] = rf_control; 1021 1.3 oster } 1022 1.3 oster } 1023 1.3 oster 1024 1.3 oster if (nfaults == 2) { 1025 1.3 oster for (i = 0; i < numParityNodes; i++) { 1026 1.3 oster if (lu_flag) { 1027 1.3 oster /* connect write new Q nodes to unlock nodes */ 1028 1.3 oster RF_ASSERT(writeQNodes[i].numSuccedents == 1); 1029 1.3 oster RF_ASSERT(unlockQNodes[i].numAntecedents == 1); 1030 1.3 oster writeQNodes[i].succedents[0] = &unlockQNodes[i]; 1031 1.3 oster unlockQNodes[i].antecedents[0] = &writeQNodes[i]; 1032 1.3 oster unlockQNodes[i].antType[0] = rf_control; 1033 1.3 oster 1034 1.3 oster /* connect unlock nodes to unblock node */ 1035 1.3 oster RF_ASSERT(unlockQNodes[i].numSuccedents == 1); 1036 1.3 oster unlockQNodes[i].succedents[0] = termNode; 1037 1.3 oster termNode->antecedents[numDataNodes + numParityNodes + i] = &unlockQNodes[i]; 1038 1.3 oster termNode->antType[numDataNodes + numParityNodes + i] = rf_control; 1039 1.3 oster } else { 1040 1.3 oster RF_ASSERT(writeQNodes[i].numSuccedents == 1); 1041 1.3 oster writeQNodes[i].succedents[0] = termNode; 1042 1.3 oster termNode->antecedents[numDataNodes + numParityNodes + i] = &writeQNodes[i]; 1043 1.3 oster termNode->antType[numDataNodes + numParityNodes + i] = rf_control; 1044 1.3 oster } 1045 1.3 oster } 1046 1.3 oster } 1047 1.1 oster } 1048 1.1 oster 1049 1.1 oster 1050 1.1 oster /****************************************************************************** 1051 1.1 oster * create a write graph (fault-free or degraded) for RAID level 1 1052 1.1 oster * 1053 1.1 oster * Hdr -> Commit -> Wpd -> Nil -> Trm 1054 1.1 oster * -> Wsd -> 1055 1.1 oster * 1056 1.1 oster * The "Wpd" node writes data to the primary copy in the mirror pair 1057 1.1 oster * The "Wsd" node writes data to the secondary copy in the mirror pair 1058 1.1 oster * 1059 1.1 oster * Parameters: raidPtr - description of the physical array 1060 1.1 oster * asmap - logical & physical addresses for this access 1061 1.1 oster * bp - buffer ptr (holds write data) 1062 1.3 oster * flags - general flags (e.g. disk locking) 1063 1.1 oster * allocList - list of memory allocated in DAG creation 1064 1.1 oster *****************************************************************************/ 1065 1.1 oster 1066 1.3 oster void 1067 1.3 oster rf_CreateRaidOneWriteDAG( 1068 1.3 oster RF_Raid_t * raidPtr, 1069 1.3 oster RF_AccessStripeMap_t * asmap, 1070 1.3 oster RF_DagHeader_t * dag_h, 1071 1.3 oster void *bp, 1072 1.3 oster RF_RaidAccessFlags_t flags, 1073 1.3 oster RF_AllocListElem_t * allocList) 1074 1.1 oster { 1075 1.3 oster RF_DagNode_t *unblockNode, *termNode, *commitNode; 1076 1.3 oster RF_DagNode_t *nodes, *wndNode, *wmirNode; 1077 1.3 oster int nWndNodes, nWmirNodes, i; 1078 1.3 oster RF_ReconUnitNum_t which_ru; 1079 1.3 oster RF_PhysDiskAddr_t *pda, *pdaP; 1080 1.3 oster RF_StripeNum_t parityStripeID; 1081 1.3 oster 1082 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout), 1083 1.3 oster asmap->raidAddress, &which_ru); 1084 1.3 oster if (rf_dagDebug) { 1085 1.3 oster printf("[Creating RAID level 1 write DAG]\n"); 1086 1.3 oster } 1087 1.3 oster dag_h->creator = "RaidOneWriteDAG"; 1088 1.3 oster 1089 1.3 oster /* 2 implies access not SU aligned */ 1090 1.3 oster nWmirNodes = (asmap->parityInfo->next) ? 2 : 1; 1091 1.3 oster nWndNodes = (asmap->physInfo->next) ? 2 : 1; 1092 1.3 oster 1093 1.3 oster /* alloc the Wnd nodes and the Wmir node */ 1094 1.3 oster if (asmap->numDataFailed == 1) 1095 1.3 oster nWndNodes--; 1096 1.3 oster if (asmap->numParityFailed == 1) 1097 1.3 oster nWmirNodes--; 1098 1.3 oster 1099 1.3 oster /* total number of nodes = nWndNodes + nWmirNodes + (commit + unblock 1100 1.3 oster * + terminator) */ 1101 1.3 oster RF_CallocAndAdd(nodes, nWndNodes + nWmirNodes + 3, sizeof(RF_DagNode_t), 1102 1.3 oster (RF_DagNode_t *), allocList); 1103 1.3 oster i = 0; 1104 1.3 oster wndNode = &nodes[i]; 1105 1.3 oster i += nWndNodes; 1106 1.3 oster wmirNode = &nodes[i]; 1107 1.3 oster i += nWmirNodes; 1108 1.3 oster commitNode = &nodes[i]; 1109 1.3 oster i += 1; 1110 1.3 oster unblockNode = &nodes[i]; 1111 1.3 oster i += 1; 1112 1.3 oster termNode = &nodes[i]; 1113 1.3 oster i += 1; 1114 1.3 oster RF_ASSERT(i == (nWndNodes + nWmirNodes + 3)); 1115 1.3 oster 1116 1.3 oster /* this dag can commit immediately */ 1117 1.3 oster dag_h->numCommitNodes = 1; 1118 1.3 oster dag_h->numCommits = 0; 1119 1.3 oster dag_h->numSuccedents = 1; 1120 1.3 oster 1121 1.3 oster /* initialize the commit, unblock, and term nodes */ 1122 1.3 oster rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 1123 1.3 oster NULL, (nWndNodes + nWmirNodes), 0, 0, 0, dag_h, "Cmt", allocList); 1124 1.3 oster rf_InitNode(unblockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, 1125 1.3 oster NULL, 1, (nWndNodes + nWmirNodes), 0, 0, dag_h, "Nil", allocList); 1126 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, 1127 1.3 oster NULL, 0, 1, 0, 0, dag_h, "Trm", allocList); 1128 1.3 oster 1129 1.3 oster /* initialize the wnd nodes */ 1130 1.3 oster if (nWndNodes > 0) { 1131 1.3 oster pda = asmap->physInfo; 1132 1.3 oster for (i = 0; i < nWndNodes; i++) { 1133 1.3 oster rf_InitNode(&wndNode[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 1134 1.3 oster rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wpd", allocList); 1135 1.3 oster RF_ASSERT(pda != NULL); 1136 1.3 oster wndNode[i].params[0].p = pda; 1137 1.3 oster wndNode[i].params[1].p = pda->bufPtr; 1138 1.3 oster wndNode[i].params[2].v = parityStripeID; 1139 1.3 oster wndNode[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1140 1.3 oster pda = pda->next; 1141 1.3 oster } 1142 1.3 oster RF_ASSERT(pda == NULL); 1143 1.3 oster } 1144 1.3 oster /* initialize the mirror nodes */ 1145 1.3 oster if (nWmirNodes > 0) { 1146 1.3 oster pda = asmap->physInfo; 1147 1.3 oster pdaP = asmap->parityInfo; 1148 1.3 oster for (i = 0; i < nWmirNodes; i++) { 1149 1.3 oster rf_InitNode(&wmirNode[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, 1150 1.3 oster rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wsd", allocList); 1151 1.3 oster RF_ASSERT(pda != NULL); 1152 1.3 oster wmirNode[i].params[0].p = pdaP; 1153 1.3 oster wmirNode[i].params[1].p = pda->bufPtr; 1154 1.3 oster wmirNode[i].params[2].v = parityStripeID; 1155 1.3 oster wmirNode[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1156 1.3 oster pda = pda->next; 1157 1.3 oster pdaP = pdaP->next; 1158 1.3 oster } 1159 1.3 oster RF_ASSERT(pda == NULL); 1160 1.3 oster RF_ASSERT(pdaP == NULL); 1161 1.3 oster } 1162 1.3 oster /* link the header node to the commit node */ 1163 1.3 oster RF_ASSERT(dag_h->numSuccedents == 1); 1164 1.3 oster RF_ASSERT(commitNode->numAntecedents == 0); 1165 1.3 oster dag_h->succedents[0] = commitNode; 1166 1.3 oster 1167 1.3 oster /* link the commit node to the write nodes */ 1168 1.3 oster RF_ASSERT(commitNode->numSuccedents == (nWndNodes + nWmirNodes)); 1169 1.3 oster for (i = 0; i < nWndNodes; i++) { 1170 1.3 oster RF_ASSERT(wndNode[i].numAntecedents == 1); 1171 1.3 oster commitNode->succedents[i] = &wndNode[i]; 1172 1.3 oster wndNode[i].antecedents[0] = commitNode; 1173 1.3 oster wndNode[i].antType[0] = rf_control; 1174 1.3 oster } 1175 1.3 oster for (i = 0; i < nWmirNodes; i++) { 1176 1.3 oster RF_ASSERT(wmirNode[i].numAntecedents == 1); 1177 1.3 oster commitNode->succedents[i + nWndNodes] = &wmirNode[i]; 1178 1.3 oster wmirNode[i].antecedents[0] = commitNode; 1179 1.3 oster wmirNode[i].antType[0] = rf_control; 1180 1.3 oster } 1181 1.3 oster 1182 1.3 oster /* link the write nodes to the unblock node */ 1183 1.3 oster RF_ASSERT(unblockNode->numAntecedents == (nWndNodes + nWmirNodes)); 1184 1.3 oster for (i = 0; i < nWndNodes; i++) { 1185 1.3 oster RF_ASSERT(wndNode[i].numSuccedents == 1); 1186 1.3 oster wndNode[i].succedents[0] = unblockNode; 1187 1.3 oster unblockNode->antecedents[i] = &wndNode[i]; 1188 1.3 oster unblockNode->antType[i] = rf_control; 1189 1.3 oster } 1190 1.3 oster for (i = 0; i < nWmirNodes; i++) { 1191 1.3 oster RF_ASSERT(wmirNode[i].numSuccedents == 1); 1192 1.3 oster wmirNode[i].succedents[0] = unblockNode; 1193 1.3 oster unblockNode->antecedents[i + nWndNodes] = &wmirNode[i]; 1194 1.3 oster unblockNode->antType[i + nWndNodes] = rf_control; 1195 1.3 oster } 1196 1.3 oster 1197 1.3 oster /* link the unblock node to the term node */ 1198 1.3 oster RF_ASSERT(unblockNode->numSuccedents == 1); 1199 1.3 oster RF_ASSERT(termNode->numAntecedents == 1); 1200 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 1201 1.3 oster unblockNode->succedents[0] = termNode; 1202 1.3 oster termNode->antecedents[0] = unblockNode; 1203 1.3 oster termNode->antType[0] = rf_control; 1204 1.1 oster } 1205 1.1 oster 1206 1.1 oster 1207 1.9 oster #if 0 1208 1.1 oster /* DAGs which have no commit points. 1209 1.1 oster * 1210 1.1 oster * The following DAGs are used in forward and backward error recovery experiments. 1211 1.1 oster * They are identical to the DAGs above this comment with the exception that the 1212 1.1 oster * the commit points have been removed. 1213 1.1 oster */ 1214 1.1 oster 1215 1.1 oster 1216 1.1 oster 1217 1.3 oster void 1218 1.3 oster rf_CommonCreateLargeWriteDAGFwd( 1219 1.3 oster RF_Raid_t * raidPtr, 1220 1.3 oster RF_AccessStripeMap_t * asmap, 1221 1.3 oster RF_DagHeader_t * dag_h, 1222 1.3 oster void *bp, 1223 1.3 oster RF_RaidAccessFlags_t flags, 1224 1.3 oster RF_AllocListElem_t * allocList, 1225 1.3 oster int nfaults, 1226 1.3 oster int (*redFunc) (RF_DagNode_t *), 1227 1.3 oster int allowBufferRecycle) 1228 1.1 oster { 1229 1.3 oster RF_DagNode_t *nodes, *wndNodes, *rodNodes, *xorNode, *wnpNode; 1230 1.3 oster RF_DagNode_t *wnqNode, *blockNode, *syncNode, *termNode; 1231 1.3 oster int nWndNodes, nRodNodes, i, nodeNum, asmNum; 1232 1.3 oster RF_AccessStripeMapHeader_t *new_asm_h[2]; 1233 1.3 oster RF_StripeNum_t parityStripeID; 1234 1.3 oster char *sosBuffer, *eosBuffer; 1235 1.3 oster RF_ReconUnitNum_t which_ru; 1236 1.3 oster RF_RaidLayout_t *layoutPtr; 1237 1.3 oster RF_PhysDiskAddr_t *pda; 1238 1.3 oster 1239 1.3 oster layoutPtr = &(raidPtr->Layout); 1240 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout), asmap->raidAddress, &which_ru); 1241 1.3 oster 1242 1.3 oster if (rf_dagDebug) 1243 1.3 oster printf("[Creating large-write DAG]\n"); 1244 1.3 oster dag_h->creator = "LargeWriteDAGFwd"; 1245 1.3 oster 1246 1.3 oster dag_h->numCommitNodes = 0; 1247 1.3 oster dag_h->numCommits = 0; 1248 1.3 oster dag_h->numSuccedents = 1; 1249 1.3 oster 1250 1.3 oster /* alloc the nodes: Wnd, xor, commit, block, term, and Wnp */ 1251 1.3 oster nWndNodes = asmap->numStripeUnitsAccessed; 1252 1.3 oster RF_CallocAndAdd(nodes, nWndNodes + 4 + nfaults, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList); 1253 1.3 oster i = 0; 1254 1.3 oster wndNodes = &nodes[i]; 1255 1.3 oster i += nWndNodes; 1256 1.3 oster xorNode = &nodes[i]; 1257 1.3 oster i += 1; 1258 1.3 oster wnpNode = &nodes[i]; 1259 1.3 oster i += 1; 1260 1.3 oster blockNode = &nodes[i]; 1261 1.3 oster i += 1; 1262 1.3 oster syncNode = &nodes[i]; 1263 1.3 oster i += 1; 1264 1.3 oster termNode = &nodes[i]; 1265 1.3 oster i += 1; 1266 1.3 oster if (nfaults == 2) { 1267 1.3 oster wnqNode = &nodes[i]; 1268 1.3 oster i += 1; 1269 1.3 oster } else { 1270 1.3 oster wnqNode = NULL; 1271 1.3 oster } 1272 1.3 oster rf_MapUnaccessedPortionOfStripe(raidPtr, layoutPtr, asmap, dag_h, new_asm_h, &nRodNodes, &sosBuffer, &eosBuffer, allocList); 1273 1.3 oster if (nRodNodes > 0) { 1274 1.3 oster RF_CallocAndAdd(rodNodes, nRodNodes, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList); 1275 1.3 oster } else { 1276 1.3 oster rodNodes = NULL; 1277 1.3 oster } 1278 1.3 oster 1279 1.3 oster /* begin node initialization */ 1280 1.3 oster if (nRodNodes > 0) { 1281 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nRodNodes, 0, 0, 0, dag_h, "Nil", allocList); 1282 1.3 oster rf_InitNode(syncNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nWndNodes + 1, nRodNodes, 0, 0, dag_h, "Nil", allocList); 1283 1.3 oster } else { 1284 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, 1, 0, 0, 0, dag_h, "Nil", allocList); 1285 1.3 oster rf_InitNode(syncNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nWndNodes + 1, 1, 0, 0, dag_h, "Nil", allocList); 1286 1.3 oster } 1287 1.3 oster 1288 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 0, nWndNodes + nfaults, 0, 0, dag_h, "Trm", allocList); 1289 1.3 oster 1290 1.3 oster /* initialize the Rod nodes */ 1291 1.3 oster for (nodeNum = asmNum = 0; asmNum < 2; asmNum++) { 1292 1.3 oster if (new_asm_h[asmNum]) { 1293 1.3 oster pda = new_asm_h[asmNum]->stripeMap->physInfo; 1294 1.3 oster while (pda) { 1295 1.3 oster rf_InitNode(&rodNodes[nodeNum], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Rod", allocList); 1296 1.3 oster rodNodes[nodeNum].params[0].p = pda; 1297 1.3 oster rodNodes[nodeNum].params[1].p = pda->bufPtr; 1298 1.3 oster rodNodes[nodeNum].params[2].v = parityStripeID; 1299 1.3 oster rodNodes[nodeNum].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1300 1.3 oster nodeNum++; 1301 1.3 oster pda = pda->next; 1302 1.3 oster } 1303 1.3 oster } 1304 1.3 oster } 1305 1.3 oster RF_ASSERT(nodeNum == nRodNodes); 1306 1.3 oster 1307 1.3 oster /* initialize the wnd nodes */ 1308 1.3 oster pda = asmap->physInfo; 1309 1.3 oster for (i = 0; i < nWndNodes; i++) { 1310 1.3 oster rf_InitNode(&wndNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnd", allocList); 1311 1.3 oster RF_ASSERT(pda != NULL); 1312 1.3 oster wndNodes[i].params[0].p = pda; 1313 1.3 oster wndNodes[i].params[1].p = pda->bufPtr; 1314 1.3 oster wndNodes[i].params[2].v = parityStripeID; 1315 1.3 oster wndNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1316 1.3 oster pda = pda->next; 1317 1.3 oster } 1318 1.3 oster 1319 1.3 oster /* initialize the redundancy node */ 1320 1.3 oster rf_InitNode(xorNode, rf_wait, RF_FALSE, redFunc, rf_NullNodeUndoFunc, NULL, 1, nfaults, 2 * (nWndNodes + nRodNodes) + 1, nfaults, dag_h, "Xr ", allocList); 1321 1.3 oster xorNode->flags |= RF_DAGNODE_FLAG_YIELD; 1322 1.3 oster for (i = 0; i < nWndNodes; i++) { 1323 1.3 oster xorNode->params[2 * i + 0] = wndNodes[i].params[0]; /* pda */ 1324 1.3 oster xorNode->params[2 * i + 1] = wndNodes[i].params[1]; /* buf ptr */ 1325 1.3 oster } 1326 1.3 oster for (i = 0; i < nRodNodes; i++) { 1327 1.3 oster xorNode->params[2 * (nWndNodes + i) + 0] = rodNodes[i].params[0]; /* pda */ 1328 1.3 oster xorNode->params[2 * (nWndNodes + i) + 1] = rodNodes[i].params[1]; /* buf ptr */ 1329 1.3 oster } 1330 1.3 oster xorNode->params[2 * (nWndNodes + nRodNodes)].p = raidPtr; /* xor node needs to get 1331 1.3 oster * at RAID information */ 1332 1.3 oster 1333 1.3 oster /* look for an Rod node that reads a complete SU. If none, alloc a 1334 1.3 oster * buffer to receive the parity info. Note that we can't use a new 1335 1.3 oster * data buffer because it will not have gotten written when the xor 1336 1.3 oster * occurs. */ 1337 1.3 oster if (allowBufferRecycle) { 1338 1.3 oster for (i = 0; i < nRodNodes; i++) 1339 1.3 oster if (((RF_PhysDiskAddr_t *) rodNodes[i].params[0].p)->numSector == raidPtr->Layout.sectorsPerStripeUnit) 1340 1.3 oster break; 1341 1.3 oster } 1342 1.3 oster if ((!allowBufferRecycle) || (i == nRodNodes)) { 1343 1.3 oster RF_CallocAndAdd(xorNode->results[0], 1, rf_RaidAddressToByte(raidPtr, raidPtr->Layout.sectorsPerStripeUnit), (void *), allocList); 1344 1.3 oster } else 1345 1.3 oster xorNode->results[0] = rodNodes[i].params[1].p; 1346 1.3 oster 1347 1.3 oster /* initialize the Wnp node */ 1348 1.3 oster rf_InitNode(wnpNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnp", allocList); 1349 1.3 oster wnpNode->params[0].p = asmap->parityInfo; 1350 1.3 oster wnpNode->params[1].p = xorNode->results[0]; 1351 1.3 oster wnpNode->params[2].v = parityStripeID; 1352 1.3 oster wnpNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1353 1.3 oster RF_ASSERT(asmap->parityInfo->next == NULL); /* parityInfo must 1354 1.3 oster * describe entire 1355 1.3 oster * parity unit */ 1356 1.3 oster 1357 1.3 oster if (nfaults == 2) { 1358 1.3 oster /* we never try to recycle a buffer for the Q calcuation in 1359 1.3 oster * addition to the parity. This would cause two buffers to get 1360 1.3 oster * smashed during the P and Q calculation, guaranteeing one 1361 1.3 oster * would be wrong. */ 1362 1.3 oster RF_CallocAndAdd(xorNode->results[1], 1, rf_RaidAddressToByte(raidPtr, raidPtr->Layout.sectorsPerStripeUnit), (void *), allocList); 1363 1.3 oster rf_InitNode(wnqNode, rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnq", allocList); 1364 1.3 oster wnqNode->params[0].p = asmap->qInfo; 1365 1.3 oster wnqNode->params[1].p = xorNode->results[1]; 1366 1.3 oster wnqNode->params[2].v = parityStripeID; 1367 1.3 oster wnqNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1368 1.3 oster RF_ASSERT(asmap->parityInfo->next == NULL); /* parityInfo must 1369 1.3 oster * describe entire 1370 1.3 oster * parity unit */ 1371 1.3 oster } 1372 1.3 oster /* connect nodes to form graph */ 1373 1.3 oster 1374 1.3 oster /* connect dag header to block node */ 1375 1.3 oster RF_ASSERT(blockNode->numAntecedents == 0); 1376 1.3 oster dag_h->succedents[0] = blockNode; 1377 1.3 oster 1378 1.3 oster if (nRodNodes > 0) { 1379 1.3 oster /* connect the block node to the Rod nodes */ 1380 1.3 oster RF_ASSERT(blockNode->numSuccedents == nRodNodes); 1381 1.3 oster RF_ASSERT(syncNode->numAntecedents == nRodNodes); 1382 1.3 oster for (i = 0; i < nRodNodes; i++) { 1383 1.3 oster RF_ASSERT(rodNodes[i].numAntecedents == 1); 1384 1.3 oster blockNode->succedents[i] = &rodNodes[i]; 1385 1.3 oster rodNodes[i].antecedents[0] = blockNode; 1386 1.3 oster rodNodes[i].antType[0] = rf_control; 1387 1.3 oster 1388 1.3 oster /* connect the Rod nodes to the Nil node */ 1389 1.3 oster RF_ASSERT(rodNodes[i].numSuccedents == 1); 1390 1.3 oster rodNodes[i].succedents[0] = syncNode; 1391 1.3 oster syncNode->antecedents[i] = &rodNodes[i]; 1392 1.3 oster syncNode->antType[i] = rf_trueData; 1393 1.3 oster } 1394 1.3 oster } else { 1395 1.3 oster /* connect the block node to the Nil node */ 1396 1.3 oster RF_ASSERT(blockNode->numSuccedents == 1); 1397 1.3 oster RF_ASSERT(syncNode->numAntecedents == 1); 1398 1.3 oster blockNode->succedents[0] = syncNode; 1399 1.3 oster syncNode->antecedents[0] = blockNode; 1400 1.3 oster syncNode->antType[0] = rf_control; 1401 1.3 oster } 1402 1.3 oster 1403 1.3 oster /* connect the sync node to the Wnd nodes */ 1404 1.3 oster RF_ASSERT(syncNode->numSuccedents == (1 + nWndNodes)); 1405 1.3 oster for (i = 0; i < nWndNodes; i++) { 1406 1.3 oster RF_ASSERT(wndNodes->numAntecedents == 1); 1407 1.3 oster syncNode->succedents[i] = &wndNodes[i]; 1408 1.3 oster wndNodes[i].antecedents[0] = syncNode; 1409 1.3 oster wndNodes[i].antType[0] = rf_control; 1410 1.3 oster } 1411 1.3 oster 1412 1.3 oster /* connect the sync node to the Xor node */ 1413 1.3 oster RF_ASSERT(xorNode->numAntecedents == 1); 1414 1.3 oster syncNode->succedents[nWndNodes] = xorNode; 1415 1.3 oster xorNode->antecedents[0] = syncNode; 1416 1.3 oster xorNode->antType[0] = rf_control; 1417 1.3 oster 1418 1.3 oster /* connect the xor node to the write parity node */ 1419 1.3 oster RF_ASSERT(xorNode->numSuccedents == nfaults); 1420 1.3 oster RF_ASSERT(wnpNode->numAntecedents == 1); 1421 1.3 oster xorNode->succedents[0] = wnpNode; 1422 1.3 oster wnpNode->antecedents[0] = xorNode; 1423 1.3 oster wnpNode->antType[0] = rf_trueData; 1424 1.3 oster if (nfaults == 2) { 1425 1.3 oster RF_ASSERT(wnqNode->numAntecedents == 1); 1426 1.3 oster xorNode->succedents[1] = wnqNode; 1427 1.3 oster wnqNode->antecedents[0] = xorNode; 1428 1.3 oster wnqNode->antType[0] = rf_trueData; 1429 1.3 oster } 1430 1.3 oster /* connect the write nodes to the term node */ 1431 1.3 oster RF_ASSERT(termNode->numAntecedents == nWndNodes + nfaults); 1432 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 1433 1.3 oster for (i = 0; i < nWndNodes; i++) { 1434 1.3 oster RF_ASSERT(wndNodes->numSuccedents == 1); 1435 1.3 oster wndNodes[i].succedents[0] = termNode; 1436 1.3 oster termNode->antecedents[i] = &wndNodes[i]; 1437 1.3 oster termNode->antType[i] = rf_control; 1438 1.3 oster } 1439 1.3 oster RF_ASSERT(wnpNode->numSuccedents == 1); 1440 1.3 oster wnpNode->succedents[0] = termNode; 1441 1.3 oster termNode->antecedents[nWndNodes] = wnpNode; 1442 1.3 oster termNode->antType[nWndNodes] = rf_control; 1443 1.3 oster if (nfaults == 2) { 1444 1.3 oster RF_ASSERT(wnqNode->numSuccedents == 1); 1445 1.3 oster wnqNode->succedents[0] = termNode; 1446 1.3 oster termNode->antecedents[nWndNodes + 1] = wnqNode; 1447 1.3 oster termNode->antType[nWndNodes + 1] = rf_control; 1448 1.3 oster } 1449 1.1 oster } 1450 1.1 oster 1451 1.1 oster 1452 1.1 oster /****************************************************************************** 1453 1.1 oster * 1454 1.1 oster * creates a DAG to perform a small-write operation (either raid 5 or pq), 1455 1.1 oster * which is as follows: 1456 1.1 oster * 1457 1.1 oster * Hdr -> Nil -> Rop - Xor - Wnp [Unp] -- Trm 1458 1.1 oster * \- Rod X- Wnd [Und] -------/ 1459 1.1 oster * [\- Rod X- Wnd [Und] ------/] 1460 1.1 oster * [\- Roq - Q --> Wnq [Unq]-/] 1461 1.1 oster * 1462 1.1 oster * Rop = read old parity 1463 1.1 oster * Rod = read old data 1464 1.1 oster * Roq = read old "q" 1465 1.1 oster * Cmt = commit node 1466 1.1 oster * Und = unlock data disk 1467 1.1 oster * Unp = unlock parity disk 1468 1.1 oster * Unq = unlock q disk 1469 1.1 oster * Wnp = write new parity 1470 1.1 oster * Wnd = write new data 1471 1.1 oster * Wnq = write new "q" 1472 1.1 oster * [ ] denotes optional segments in the graph 1473 1.1 oster * 1474 1.1 oster * Parameters: raidPtr - description of the physical array 1475 1.1 oster * asmap - logical & physical addresses for this access 1476 1.1 oster * bp - buffer ptr (holds write data) 1477 1.3 oster * flags - general flags (e.g. disk locking) 1478 1.1 oster * allocList - list of memory allocated in DAG creation 1479 1.1 oster * pfuncs - list of parity generating functions 1480 1.1 oster * qfuncs - list of q generating functions 1481 1.1 oster * 1482 1.1 oster * A null qfuncs indicates single fault tolerant 1483 1.1 oster *****************************************************************************/ 1484 1.1 oster 1485 1.3 oster void 1486 1.3 oster rf_CommonCreateSmallWriteDAGFwd( 1487 1.3 oster RF_Raid_t * raidPtr, 1488 1.3 oster RF_AccessStripeMap_t * asmap, 1489 1.3 oster RF_DagHeader_t * dag_h, 1490 1.3 oster void *bp, 1491 1.3 oster RF_RaidAccessFlags_t flags, 1492 1.3 oster RF_AllocListElem_t * allocList, 1493 1.3 oster RF_RedFuncs_t * pfuncs, 1494 1.3 oster RF_RedFuncs_t * qfuncs) 1495 1.1 oster { 1496 1.3 oster RF_DagNode_t *readDataNodes, *readParityNodes, *readQNodes, *termNode; 1497 1.3 oster RF_DagNode_t *unlockDataNodes, *unlockParityNodes, *unlockQNodes; 1498 1.3 oster RF_DagNode_t *xorNodes, *qNodes, *blockNode, *nodes; 1499 1.3 oster RF_DagNode_t *writeDataNodes, *writeParityNodes, *writeQNodes; 1500 1.3 oster int i, j, nNodes, totalNumNodes, lu_flag; 1501 1.3 oster RF_ReconUnitNum_t which_ru; 1502 1.3 oster int (*func) (RF_DagNode_t *), (*undoFunc) (RF_DagNode_t *); 1503 1.3 oster int (*qfunc) (RF_DagNode_t *); 1504 1.3 oster int numDataNodes, numParityNodes; 1505 1.3 oster RF_StripeNum_t parityStripeID; 1506 1.3 oster RF_PhysDiskAddr_t *pda; 1507 1.3 oster char *name, *qname; 1508 1.3 oster long nfaults; 1509 1.3 oster 1510 1.3 oster nfaults = qfuncs ? 2 : 1; 1511 1.3 oster lu_flag = (rf_enableAtomicRMW) ? 1 : 0; /* lock/unlock flag */ 1512 1.3 oster 1513 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout), asmap->raidAddress, &which_ru); 1514 1.3 oster pda = asmap->physInfo; 1515 1.3 oster numDataNodes = asmap->numStripeUnitsAccessed; 1516 1.3 oster numParityNodes = (asmap->parityInfo->next) ? 2 : 1; 1517 1.3 oster 1518 1.3 oster if (rf_dagDebug) 1519 1.3 oster printf("[Creating small-write DAG]\n"); 1520 1.3 oster RF_ASSERT(numDataNodes > 0); 1521 1.3 oster dag_h->creator = "SmallWriteDAGFwd"; 1522 1.3 oster 1523 1.3 oster dag_h->numCommitNodes = 0; 1524 1.3 oster dag_h->numCommits = 0; 1525 1.3 oster dag_h->numSuccedents = 1; 1526 1.3 oster 1527 1.3 oster qfunc = NULL; 1528 1.3 oster qname = NULL; 1529 1.3 oster 1530 1.3 oster /* DAG creation occurs in four steps: 1. count the number of nodes in 1531 1.3 oster * the DAG 2. create the nodes 3. initialize the nodes 4. connect the 1532 1.3 oster * nodes */ 1533 1.3 oster 1534 1.3 oster /* Step 1. compute number of nodes in the graph */ 1535 1.3 oster 1536 1.3 oster /* number of nodes: a read and write for each data unit a redundancy 1537 1.3 oster * computation node for each parity node (nfaults * nparity) a read 1538 1.3 oster * and write for each parity unit a block node a terminate node if 1539 1.3 oster * atomic RMW an unlock node for each data unit, redundancy unit */ 1540 1.3 oster totalNumNodes = (2 * numDataNodes) + (nfaults * numParityNodes) + (nfaults * 2 * numParityNodes) + 2; 1541 1.3 oster if (lu_flag) 1542 1.3 oster totalNumNodes += (numDataNodes + (nfaults * numParityNodes)); 1543 1.3 oster 1544 1.3 oster 1545 1.3 oster /* Step 2. create the nodes */ 1546 1.3 oster RF_CallocAndAdd(nodes, totalNumNodes, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList); 1547 1.3 oster i = 0; 1548 1.3 oster blockNode = &nodes[i]; 1549 1.3 oster i += 1; 1550 1.3 oster readDataNodes = &nodes[i]; 1551 1.3 oster i += numDataNodes; 1552 1.3 oster readParityNodes = &nodes[i]; 1553 1.3 oster i += numParityNodes; 1554 1.3 oster writeDataNodes = &nodes[i]; 1555 1.3 oster i += numDataNodes; 1556 1.3 oster writeParityNodes = &nodes[i]; 1557 1.3 oster i += numParityNodes; 1558 1.3 oster xorNodes = &nodes[i]; 1559 1.3 oster i += numParityNodes; 1560 1.3 oster termNode = &nodes[i]; 1561 1.3 oster i += 1; 1562 1.3 oster if (lu_flag) { 1563 1.3 oster unlockDataNodes = &nodes[i]; 1564 1.3 oster i += numDataNodes; 1565 1.3 oster unlockParityNodes = &nodes[i]; 1566 1.3 oster i += numParityNodes; 1567 1.3 oster } else { 1568 1.3 oster unlockDataNodes = unlockParityNodes = NULL; 1569 1.3 oster } 1570 1.3 oster if (nfaults == 2) { 1571 1.3 oster readQNodes = &nodes[i]; 1572 1.3 oster i += numParityNodes; 1573 1.3 oster writeQNodes = &nodes[i]; 1574 1.3 oster i += numParityNodes; 1575 1.3 oster qNodes = &nodes[i]; 1576 1.3 oster i += numParityNodes; 1577 1.3 oster if (lu_flag) { 1578 1.3 oster unlockQNodes = &nodes[i]; 1579 1.3 oster i += numParityNodes; 1580 1.3 oster } else { 1581 1.3 oster unlockQNodes = NULL; 1582 1.3 oster } 1583 1.3 oster } else { 1584 1.3 oster readQNodes = writeQNodes = qNodes = unlockQNodes = NULL; 1585 1.3 oster } 1586 1.3 oster RF_ASSERT(i == totalNumNodes); 1587 1.1 oster 1588 1.3 oster /* Step 3. initialize the nodes */ 1589 1.3 oster /* initialize block node (Nil) */ 1590 1.3 oster nNodes = numDataNodes + (nfaults * numParityNodes); 1591 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, nNodes, 0, 0, 0, dag_h, "Nil", allocList); 1592 1.3 oster 1593 1.3 oster /* initialize terminate node (Trm) */ 1594 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 0, nNodes, 0, 0, dag_h, "Trm", allocList); 1595 1.3 oster 1596 1.3 oster /* initialize nodes which read old data (Rod) */ 1597 1.3 oster for (i = 0; i < numDataNodes; i++) { 1598 1.3 oster rf_InitNode(&readDataNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, (numParityNodes * nfaults) + 1, 1, 4, 0, dag_h, "Rod", allocList); 1599 1.3 oster RF_ASSERT(pda != NULL); 1600 1.3 oster readDataNodes[i].params[0].p = pda; /* physical disk addr 1601 1.3 oster * desc */ 1602 1.3 oster readDataNodes[i].params[1].p = rf_AllocBuffer(raidPtr, dag_h, pda, allocList); /* buffer to hold old 1603 1.3 oster * data */ 1604 1.3 oster readDataNodes[i].params[2].v = parityStripeID; 1605 1.3 oster readDataNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, lu_flag, 0, which_ru); 1606 1.3 oster pda = pda->next; 1607 1.3 oster for (j = 0; j < readDataNodes[i].numSuccedents; j++) 1608 1.3 oster readDataNodes[i].propList[j] = NULL; 1609 1.3 oster } 1610 1.3 oster 1611 1.3 oster /* initialize nodes which read old parity (Rop) */ 1612 1.3 oster pda = asmap->parityInfo; 1613 1.3 oster i = 0; 1614 1.3 oster for (i = 0; i < numParityNodes; i++) { 1615 1.3 oster RF_ASSERT(pda != NULL); 1616 1.3 oster rf_InitNode(&readParityNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, numParityNodes, 1, 4, 0, dag_h, "Rop", allocList); 1617 1.3 oster readParityNodes[i].params[0].p = pda; 1618 1.3 oster readParityNodes[i].params[1].p = rf_AllocBuffer(raidPtr, dag_h, pda, allocList); /* buffer to hold old 1619 1.3 oster * parity */ 1620 1.3 oster readParityNodes[i].params[2].v = parityStripeID; 1621 1.3 oster readParityNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, lu_flag, 0, which_ru); 1622 1.3 oster for (j = 0; j < readParityNodes[i].numSuccedents; j++) 1623 1.3 oster readParityNodes[i].propList[0] = NULL; 1624 1.3 oster pda = pda->next; 1625 1.3 oster } 1626 1.3 oster 1627 1.3 oster /* initialize nodes which read old Q (Roq) */ 1628 1.3 oster if (nfaults == 2) { 1629 1.3 oster pda = asmap->qInfo; 1630 1.3 oster for (i = 0; i < numParityNodes; i++) { 1631 1.3 oster RF_ASSERT(pda != NULL); 1632 1.3 oster rf_InitNode(&readQNodes[i], rf_wait, RF_FALSE, rf_DiskReadFunc, rf_DiskReadUndoFunc, rf_GenericWakeupFunc, numParityNodes, 1, 4, 0, dag_h, "Roq", allocList); 1633 1.3 oster readQNodes[i].params[0].p = pda; 1634 1.3 oster readQNodes[i].params[1].p = rf_AllocBuffer(raidPtr, dag_h, pda, allocList); /* buffer to hold old Q */ 1635 1.3 oster readQNodes[i].params[2].v = parityStripeID; 1636 1.3 oster readQNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, lu_flag, 0, which_ru); 1637 1.3 oster for (j = 0; j < readQNodes[i].numSuccedents; j++) 1638 1.3 oster readQNodes[i].propList[0] = NULL; 1639 1.3 oster pda = pda->next; 1640 1.3 oster } 1641 1.3 oster } 1642 1.3 oster /* initialize nodes which write new data (Wnd) */ 1643 1.3 oster pda = asmap->physInfo; 1644 1.3 oster for (i = 0; i < numDataNodes; i++) { 1645 1.3 oster RF_ASSERT(pda != NULL); 1646 1.3 oster rf_InitNode(&writeDataNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wnd", allocList); 1647 1.3 oster writeDataNodes[i].params[0].p = pda; /* physical disk addr 1648 1.3 oster * desc */ 1649 1.3 oster writeDataNodes[i].params[1].p = pda->bufPtr; /* buffer holding new 1650 1.3 oster * data to be written */ 1651 1.3 oster writeDataNodes[i].params[2].v = parityStripeID; 1652 1.3 oster writeDataNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1653 1.3 oster 1654 1.3 oster if (lu_flag) { 1655 1.3 oster /* initialize node to unlock the disk queue */ 1656 1.3 oster rf_InitNode(&unlockDataNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, "Und", allocList); 1657 1.3 oster unlockDataNodes[i].params[0].p = pda; /* physical disk addr 1658 1.3 oster * desc */ 1659 1.3 oster unlockDataNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, lu_flag, which_ru); 1660 1.3 oster } 1661 1.3 oster pda = pda->next; 1662 1.3 oster } 1663 1.3 oster 1664 1.3 oster 1665 1.3 oster /* initialize nodes which compute new parity and Q */ 1666 1.3 oster /* we use the simple XOR func in the double-XOR case, and when we're 1667 1.3 oster * accessing only a portion of one stripe unit. the distinction 1668 1.3 oster * between the two is that the regular XOR func assumes that the 1669 1.3 oster * targbuf is a full SU in size, and examines the pda associated with 1670 1.3 oster * the buffer to decide where within the buffer to XOR the data, 1671 1.3 oster * whereas the simple XOR func just XORs the data into the start of 1672 1.3 oster * the buffer. */ 1673 1.3 oster if ((numParityNodes == 2) || ((numDataNodes == 1) && (asmap->totalSectorsAccessed < raidPtr->Layout.sectorsPerStripeUnit))) { 1674 1.3 oster func = pfuncs->simple; 1675 1.3 oster undoFunc = rf_NullNodeUndoFunc; 1676 1.3 oster name = pfuncs->SimpleName; 1677 1.3 oster if (qfuncs) { 1678 1.3 oster qfunc = qfuncs->simple; 1679 1.3 oster qname = qfuncs->SimpleName; 1680 1.3 oster } 1681 1.3 oster } else { 1682 1.3 oster func = pfuncs->regular; 1683 1.3 oster undoFunc = rf_NullNodeUndoFunc; 1684 1.3 oster name = pfuncs->RegularName; 1685 1.3 oster if (qfuncs) { 1686 1.3 oster qfunc = qfuncs->regular; 1687 1.3 oster qname = qfuncs->RegularName; 1688 1.3 oster } 1689 1.3 oster } 1690 1.3 oster /* initialize the xor nodes: params are {pda,buf} from {Rod,Wnd,Rop} 1691 1.3 oster * nodes, and raidPtr */ 1692 1.3 oster if (numParityNodes == 2) { /* double-xor case */ 1693 1.3 oster for (i = 0; i < numParityNodes; i++) { 1694 1.3 oster rf_InitNode(&xorNodes[i], rf_wait, RF_FALSE, func, undoFunc, NULL, numParityNodes, numParityNodes + numDataNodes, 7, 1, dag_h, name, allocList); /* no wakeup func for 1695 1.3 oster * xor */ 1696 1.3 oster xorNodes[i].flags |= RF_DAGNODE_FLAG_YIELD; 1697 1.3 oster xorNodes[i].params[0] = readDataNodes[i].params[0]; 1698 1.3 oster xorNodes[i].params[1] = readDataNodes[i].params[1]; 1699 1.3 oster xorNodes[i].params[2] = readParityNodes[i].params[0]; 1700 1.3 oster xorNodes[i].params[3] = readParityNodes[i].params[1]; 1701 1.3 oster xorNodes[i].params[4] = writeDataNodes[i].params[0]; 1702 1.3 oster xorNodes[i].params[5] = writeDataNodes[i].params[1]; 1703 1.3 oster xorNodes[i].params[6].p = raidPtr; 1704 1.3 oster xorNodes[i].results[0] = readParityNodes[i].params[1].p; /* use old parity buf as 1705 1.3 oster * target buf */ 1706 1.3 oster if (nfaults == 2) { 1707 1.3 oster rf_InitNode(&qNodes[i], rf_wait, RF_FALSE, qfunc, undoFunc, NULL, numParityNodes, numParityNodes + numDataNodes, 7, 1, dag_h, qname, allocList); /* no wakeup func for 1708 1.3 oster * xor */ 1709 1.3 oster qNodes[i].params[0] = readDataNodes[i].params[0]; 1710 1.3 oster qNodes[i].params[1] = readDataNodes[i].params[1]; 1711 1.3 oster qNodes[i].params[2] = readQNodes[i].params[0]; 1712 1.3 oster qNodes[i].params[3] = readQNodes[i].params[1]; 1713 1.3 oster qNodes[i].params[4] = writeDataNodes[i].params[0]; 1714 1.3 oster qNodes[i].params[5] = writeDataNodes[i].params[1]; 1715 1.3 oster qNodes[i].params[6].p = raidPtr; 1716 1.3 oster qNodes[i].results[0] = readQNodes[i].params[1].p; /* use old Q buf as 1717 1.3 oster * target buf */ 1718 1.3 oster } 1719 1.3 oster } 1720 1.3 oster } else { 1721 1.3 oster /* there is only one xor node in this case */ 1722 1.3 oster rf_InitNode(&xorNodes[0], rf_wait, RF_FALSE, func, undoFunc, NULL, numParityNodes, numParityNodes + numDataNodes, (2 * (numDataNodes + numDataNodes + 1) + 1), 1, dag_h, name, allocList); 1723 1.3 oster xorNodes[0].flags |= RF_DAGNODE_FLAG_YIELD; 1724 1.3 oster for (i = 0; i < numDataNodes + 1; i++) { 1725 1.3 oster /* set up params related to Rod and Rop nodes */ 1726 1.3 oster xorNodes[0].params[2 * i + 0] = readDataNodes[i].params[0]; /* pda */ 1727 1.3 oster xorNodes[0].params[2 * i + 1] = readDataNodes[i].params[1]; /* buffer pointer */ 1728 1.3 oster } 1729 1.3 oster for (i = 0; i < numDataNodes; i++) { 1730 1.3 oster /* set up params related to Wnd and Wnp nodes */ 1731 1.3 oster xorNodes[0].params[2 * (numDataNodes + 1 + i) + 0] = writeDataNodes[i].params[0]; /* pda */ 1732 1.3 oster xorNodes[0].params[2 * (numDataNodes + 1 + i) + 1] = writeDataNodes[i].params[1]; /* buffer pointer */ 1733 1.3 oster } 1734 1.3 oster xorNodes[0].params[2 * (numDataNodes + numDataNodes + 1)].p = raidPtr; /* xor node needs to get 1735 1.3 oster * at RAID information */ 1736 1.3 oster xorNodes[0].results[0] = readParityNodes[0].params[1].p; 1737 1.3 oster if (nfaults == 2) { 1738 1.3 oster rf_InitNode(&qNodes[0], rf_wait, RF_FALSE, qfunc, undoFunc, NULL, numParityNodes, numParityNodes + numDataNodes, (2 * (numDataNodes + numDataNodes + 1) + 1), 1, dag_h, qname, allocList); 1739 1.3 oster for (i = 0; i < numDataNodes; i++) { 1740 1.3 oster /* set up params related to Rod */ 1741 1.3 oster qNodes[0].params[2 * i + 0] = readDataNodes[i].params[0]; /* pda */ 1742 1.3 oster qNodes[0].params[2 * i + 1] = readDataNodes[i].params[1]; /* buffer pointer */ 1743 1.3 oster } 1744 1.3 oster /* and read old q */ 1745 1.3 oster qNodes[0].params[2 * numDataNodes + 0] = readQNodes[0].params[0]; /* pda */ 1746 1.3 oster qNodes[0].params[2 * numDataNodes + 1] = readQNodes[0].params[1]; /* buffer pointer */ 1747 1.3 oster for (i = 0; i < numDataNodes; i++) { 1748 1.3 oster /* set up params related to Wnd nodes */ 1749 1.3 oster qNodes[0].params[2 * (numDataNodes + 1 + i) + 0] = writeDataNodes[i].params[0]; /* pda */ 1750 1.3 oster qNodes[0].params[2 * (numDataNodes + 1 + i) + 1] = writeDataNodes[i].params[1]; /* buffer pointer */ 1751 1.3 oster } 1752 1.3 oster qNodes[0].params[2 * (numDataNodes + numDataNodes + 1)].p = raidPtr; /* xor node needs to get 1753 1.3 oster * at RAID information */ 1754 1.3 oster qNodes[0].results[0] = readQNodes[0].params[1].p; 1755 1.3 oster } 1756 1.3 oster } 1757 1.3 oster 1758 1.3 oster /* initialize nodes which write new parity (Wnp) */ 1759 1.3 oster pda = asmap->parityInfo; 1760 1.3 oster for (i = 0; i < numParityNodes; i++) { 1761 1.3 oster rf_InitNode(&writeParityNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, numParityNodes, 4, 0, dag_h, "Wnp", allocList); 1762 1.3 oster RF_ASSERT(pda != NULL); 1763 1.3 oster writeParityNodes[i].params[0].p = pda; /* param 1 (bufPtr) 1764 1.3 oster * filled in by xor node */ 1765 1.3 oster writeParityNodes[i].params[1].p = xorNodes[i].results[0]; /* buffer pointer for 1766 1.3 oster * parity write 1767 1.3 oster * operation */ 1768 1.3 oster writeParityNodes[i].params[2].v = parityStripeID; 1769 1.3 oster writeParityNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1770 1.3 oster 1771 1.3 oster if (lu_flag) { 1772 1.3 oster /* initialize node to unlock the disk queue */ 1773 1.3 oster rf_InitNode(&unlockParityNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, "Unp", allocList); 1774 1.3 oster unlockParityNodes[i].params[0].p = pda; /* physical disk addr 1775 1.3 oster * desc */ 1776 1.3 oster unlockParityNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, lu_flag, which_ru); 1777 1.3 oster } 1778 1.3 oster pda = pda->next; 1779 1.3 oster } 1780 1.3 oster 1781 1.3 oster /* initialize nodes which write new Q (Wnq) */ 1782 1.3 oster if (nfaults == 2) { 1783 1.3 oster pda = asmap->qInfo; 1784 1.3 oster for (i = 0; i < numParityNodes; i++) { 1785 1.3 oster rf_InitNode(&writeQNodes[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, numParityNodes, 4, 0, dag_h, "Wnq", allocList); 1786 1.3 oster RF_ASSERT(pda != NULL); 1787 1.3 oster writeQNodes[i].params[0].p = pda; /* param 1 (bufPtr) 1788 1.3 oster * filled in by xor node */ 1789 1.3 oster writeQNodes[i].params[1].p = qNodes[i].results[0]; /* buffer pointer for 1790 1.3 oster * parity write 1791 1.3 oster * operation */ 1792 1.3 oster writeQNodes[i].params[2].v = parityStripeID; 1793 1.3 oster writeQNodes[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 1794 1.3 oster 1795 1.3 oster if (lu_flag) { 1796 1.3 oster /* initialize node to unlock the disk queue */ 1797 1.3 oster rf_InitNode(&unlockQNodes[i], rf_wait, RF_FALSE, rf_DiskUnlockFunc, rf_DiskUnlockUndoFunc, rf_GenericWakeupFunc, 1, 1, 2, 0, dag_h, "Unq", allocList); 1798 1.3 oster unlockQNodes[i].params[0].p = pda; /* physical disk addr 1799 1.3 oster * desc */ 1800 1.3 oster unlockQNodes[i].params[1].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, lu_flag, which_ru); 1801 1.3 oster } 1802 1.3 oster pda = pda->next; 1803 1.3 oster } 1804 1.3 oster } 1805 1.3 oster /* Step 4. connect the nodes */ 1806 1.3 oster 1807 1.3 oster /* connect header to block node */ 1808 1.3 oster dag_h->succedents[0] = blockNode; 1809 1.3 oster 1810 1.3 oster /* connect block node to read old data nodes */ 1811 1.3 oster RF_ASSERT(blockNode->numSuccedents == (numDataNodes + (numParityNodes * nfaults))); 1812 1.3 oster for (i = 0; i < numDataNodes; i++) { 1813 1.3 oster blockNode->succedents[i] = &readDataNodes[i]; 1814 1.3 oster RF_ASSERT(readDataNodes[i].numAntecedents == 1); 1815 1.3 oster readDataNodes[i].antecedents[0] = blockNode; 1816 1.3 oster readDataNodes[i].antType[0] = rf_control; 1817 1.3 oster } 1818 1.3 oster 1819 1.3 oster /* connect block node to read old parity nodes */ 1820 1.3 oster for (i = 0; i < numParityNodes; i++) { 1821 1.3 oster blockNode->succedents[numDataNodes + i] = &readParityNodes[i]; 1822 1.3 oster RF_ASSERT(readParityNodes[i].numAntecedents == 1); 1823 1.3 oster readParityNodes[i].antecedents[0] = blockNode; 1824 1.3 oster readParityNodes[i].antType[0] = rf_control; 1825 1.3 oster } 1826 1.3 oster 1827 1.3 oster /* connect block node to read old Q nodes */ 1828 1.3 oster if (nfaults == 2) 1829 1.3 oster for (i = 0; i < numParityNodes; i++) { 1830 1.3 oster blockNode->succedents[numDataNodes + numParityNodes + i] = &readQNodes[i]; 1831 1.3 oster RF_ASSERT(readQNodes[i].numAntecedents == 1); 1832 1.3 oster readQNodes[i].antecedents[0] = blockNode; 1833 1.3 oster readQNodes[i].antType[0] = rf_control; 1834 1.3 oster } 1835 1.3 oster 1836 1.3 oster /* connect read old data nodes to write new data nodes */ 1837 1.3 oster for (i = 0; i < numDataNodes; i++) { 1838 1.3 oster RF_ASSERT(readDataNodes[i].numSuccedents == ((nfaults * numParityNodes) + 1)); 1839 1.3 oster RF_ASSERT(writeDataNodes[i].numAntecedents == 1); 1840 1.3 oster readDataNodes[i].succedents[0] = &writeDataNodes[i]; 1841 1.3 oster writeDataNodes[i].antecedents[0] = &readDataNodes[i]; 1842 1.3 oster writeDataNodes[i].antType[0] = rf_antiData; 1843 1.3 oster } 1844 1.3 oster 1845 1.3 oster /* connect read old data nodes to xor nodes */ 1846 1.3 oster for (i = 0; i < numDataNodes; i++) { 1847 1.3 oster for (j = 0; j < numParityNodes; j++) { 1848 1.3 oster RF_ASSERT(xorNodes[j].numAntecedents == numDataNodes + numParityNodes); 1849 1.3 oster readDataNodes[i].succedents[1 + j] = &xorNodes[j]; 1850 1.3 oster xorNodes[j].antecedents[i] = &readDataNodes[i]; 1851 1.3 oster xorNodes[j].antType[i] = rf_trueData; 1852 1.3 oster } 1853 1.3 oster } 1854 1.3 oster 1855 1.3 oster /* connect read old data nodes to q nodes */ 1856 1.3 oster if (nfaults == 2) 1857 1.3 oster for (i = 0; i < numDataNodes; i++) 1858 1.3 oster for (j = 0; j < numParityNodes; j++) { 1859 1.3 oster RF_ASSERT(qNodes[j].numAntecedents == numDataNodes + numParityNodes); 1860 1.3 oster readDataNodes[i].succedents[1 + numParityNodes + j] = &qNodes[j]; 1861 1.3 oster qNodes[j].antecedents[i] = &readDataNodes[i]; 1862 1.3 oster qNodes[j].antType[i] = rf_trueData; 1863 1.3 oster } 1864 1.3 oster 1865 1.3 oster /* connect read old parity nodes to xor nodes */ 1866 1.3 oster for (i = 0; i < numParityNodes; i++) { 1867 1.3 oster for (j = 0; j < numParityNodes; j++) { 1868 1.3 oster RF_ASSERT(readParityNodes[i].numSuccedents == numParityNodes); 1869 1.3 oster readParityNodes[i].succedents[j] = &xorNodes[j]; 1870 1.3 oster xorNodes[j].antecedents[numDataNodes + i] = &readParityNodes[i]; 1871 1.3 oster xorNodes[j].antType[numDataNodes + i] = rf_trueData; 1872 1.3 oster } 1873 1.3 oster } 1874 1.3 oster 1875 1.3 oster /* connect read old q nodes to q nodes */ 1876 1.3 oster if (nfaults == 2) 1877 1.3 oster for (i = 0; i < numParityNodes; i++) { 1878 1.3 oster for (j = 0; j < numParityNodes; j++) { 1879 1.3 oster RF_ASSERT(readQNodes[i].numSuccedents == numParityNodes); 1880 1.3 oster readQNodes[i].succedents[j] = &qNodes[j]; 1881 1.3 oster qNodes[j].antecedents[numDataNodes + i] = &readQNodes[i]; 1882 1.3 oster qNodes[j].antType[numDataNodes + i] = rf_trueData; 1883 1.3 oster } 1884 1.3 oster } 1885 1.3 oster 1886 1.3 oster /* connect xor nodes to the write new parity nodes */ 1887 1.3 oster for (i = 0; i < numParityNodes; i++) { 1888 1.3 oster RF_ASSERT(writeParityNodes[i].numAntecedents == numParityNodes); 1889 1.3 oster for (j = 0; j < numParityNodes; j++) { 1890 1.3 oster RF_ASSERT(xorNodes[j].numSuccedents == numParityNodes); 1891 1.3 oster xorNodes[i].succedents[j] = &writeParityNodes[j]; 1892 1.3 oster writeParityNodes[j].antecedents[i] = &xorNodes[i]; 1893 1.3 oster writeParityNodes[j].antType[i] = rf_trueData; 1894 1.3 oster } 1895 1.3 oster } 1896 1.3 oster 1897 1.3 oster /* connect q nodes to the write new q nodes */ 1898 1.3 oster if (nfaults == 2) 1899 1.3 oster for (i = 0; i < numParityNodes; i++) { 1900 1.3 oster RF_ASSERT(writeQNodes[i].numAntecedents == numParityNodes); 1901 1.3 oster for (j = 0; j < numParityNodes; j++) { 1902 1.3 oster RF_ASSERT(qNodes[j].numSuccedents == 1); 1903 1.3 oster qNodes[i].succedents[j] = &writeQNodes[j]; 1904 1.3 oster writeQNodes[j].antecedents[i] = &qNodes[i]; 1905 1.3 oster writeQNodes[j].antType[i] = rf_trueData; 1906 1.3 oster } 1907 1.3 oster } 1908 1.3 oster 1909 1.3 oster RF_ASSERT(termNode->numAntecedents == (numDataNodes + (nfaults * numParityNodes))); 1910 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 1911 1.3 oster for (i = 0; i < numDataNodes; i++) { 1912 1.3 oster if (lu_flag) { 1913 1.3 oster /* connect write new data nodes to unlock nodes */ 1914 1.3 oster RF_ASSERT(writeDataNodes[i].numSuccedents == 1); 1915 1.3 oster RF_ASSERT(unlockDataNodes[i].numAntecedents == 1); 1916 1.3 oster writeDataNodes[i].succedents[0] = &unlockDataNodes[i]; 1917 1.3 oster unlockDataNodes[i].antecedents[0] = &writeDataNodes[i]; 1918 1.3 oster unlockDataNodes[i].antType[0] = rf_control; 1919 1.3 oster 1920 1.3 oster /* connect unlock nodes to term node */ 1921 1.3 oster RF_ASSERT(unlockDataNodes[i].numSuccedents == 1); 1922 1.3 oster unlockDataNodes[i].succedents[0] = termNode; 1923 1.3 oster termNode->antecedents[i] = &unlockDataNodes[i]; 1924 1.3 oster termNode->antType[i] = rf_control; 1925 1.3 oster } else { 1926 1.3 oster /* connect write new data nodes to term node */ 1927 1.3 oster RF_ASSERT(writeDataNodes[i].numSuccedents == 1); 1928 1.3 oster RF_ASSERT(termNode->numAntecedents == (numDataNodes + (nfaults * numParityNodes))); 1929 1.3 oster writeDataNodes[i].succedents[0] = termNode; 1930 1.3 oster termNode->antecedents[i] = &writeDataNodes[i]; 1931 1.3 oster termNode->antType[i] = rf_control; 1932 1.3 oster } 1933 1.3 oster } 1934 1.3 oster 1935 1.3 oster for (i = 0; i < numParityNodes; i++) { 1936 1.3 oster if (lu_flag) { 1937 1.3 oster /* connect write new parity nodes to unlock nodes */ 1938 1.3 oster RF_ASSERT(writeParityNodes[i].numSuccedents == 1); 1939 1.3 oster RF_ASSERT(unlockParityNodes[i].numAntecedents == 1); 1940 1.3 oster writeParityNodes[i].succedents[0] = &unlockParityNodes[i]; 1941 1.3 oster unlockParityNodes[i].antecedents[0] = &writeParityNodes[i]; 1942 1.3 oster unlockParityNodes[i].antType[0] = rf_control; 1943 1.3 oster 1944 1.3 oster /* connect unlock nodes to term node */ 1945 1.3 oster RF_ASSERT(unlockParityNodes[i].numSuccedents == 1); 1946 1.3 oster unlockParityNodes[i].succedents[0] = termNode; 1947 1.3 oster termNode->antecedents[numDataNodes + i] = &unlockParityNodes[i]; 1948 1.3 oster termNode->antType[numDataNodes + i] = rf_control; 1949 1.3 oster } else { 1950 1.3 oster RF_ASSERT(writeParityNodes[i].numSuccedents == 1); 1951 1.3 oster writeParityNodes[i].succedents[0] = termNode; 1952 1.3 oster termNode->antecedents[numDataNodes + i] = &writeParityNodes[i]; 1953 1.3 oster termNode->antType[numDataNodes + i] = rf_control; 1954 1.3 oster } 1955 1.3 oster } 1956 1.3 oster 1957 1.3 oster if (nfaults == 2) 1958 1.3 oster for (i = 0; i < numParityNodes; i++) { 1959 1.3 oster if (lu_flag) { 1960 1.3 oster /* connect write new Q nodes to unlock nodes */ 1961 1.3 oster RF_ASSERT(writeQNodes[i].numSuccedents == 1); 1962 1.3 oster RF_ASSERT(unlockQNodes[i].numAntecedents == 1); 1963 1.3 oster writeQNodes[i].succedents[0] = &unlockQNodes[i]; 1964 1.3 oster unlockQNodes[i].antecedents[0] = &writeQNodes[i]; 1965 1.3 oster unlockQNodes[i].antType[0] = rf_control; 1966 1.3 oster 1967 1.3 oster /* connect unlock nodes to unblock node */ 1968 1.3 oster RF_ASSERT(unlockQNodes[i].numSuccedents == 1); 1969 1.3 oster unlockQNodes[i].succedents[0] = termNode; 1970 1.3 oster termNode->antecedents[numDataNodes + numParityNodes + i] = &unlockQNodes[i]; 1971 1.3 oster termNode->antType[numDataNodes + numParityNodes + i] = rf_control; 1972 1.3 oster } else { 1973 1.3 oster RF_ASSERT(writeQNodes[i].numSuccedents == 1); 1974 1.3 oster writeQNodes[i].succedents[0] = termNode; 1975 1.3 oster termNode->antecedents[numDataNodes + numParityNodes + i] = &writeQNodes[i]; 1976 1.3 oster termNode->antType[numDataNodes + numParityNodes + i] = rf_control; 1977 1.3 oster } 1978 1.3 oster } 1979 1.1 oster } 1980 1.1 oster 1981 1.1 oster 1982 1.1 oster 1983 1.1 oster /****************************************************************************** 1984 1.1 oster * create a write graph (fault-free or degraded) for RAID level 1 1985 1.1 oster * 1986 1.1 oster * Hdr Nil -> Wpd -> Nil -> Trm 1987 1.1 oster * Nil -> Wsd -> 1988 1.1 oster * 1989 1.1 oster * The "Wpd" node writes data to the primary copy in the mirror pair 1990 1.1 oster * The "Wsd" node writes data to the secondary copy in the mirror pair 1991 1.1 oster * 1992 1.1 oster * Parameters: raidPtr - description of the physical array 1993 1.1 oster * asmap - logical & physical addresses for this access 1994 1.1 oster * bp - buffer ptr (holds write data) 1995 1.3 oster * flags - general flags (e.g. disk locking) 1996 1.1 oster * allocList - list of memory allocated in DAG creation 1997 1.1 oster *****************************************************************************/ 1998 1.1 oster 1999 1.3 oster void 2000 1.3 oster rf_CreateRaidOneWriteDAGFwd( 2001 1.3 oster RF_Raid_t * raidPtr, 2002 1.3 oster RF_AccessStripeMap_t * asmap, 2003 1.3 oster RF_DagHeader_t * dag_h, 2004 1.3 oster void *bp, 2005 1.3 oster RF_RaidAccessFlags_t flags, 2006 1.3 oster RF_AllocListElem_t * allocList) 2007 1.1 oster { 2008 1.3 oster RF_DagNode_t *blockNode, *unblockNode, *termNode; 2009 1.3 oster RF_DagNode_t *nodes, *wndNode, *wmirNode; 2010 1.3 oster int nWndNodes, nWmirNodes, i; 2011 1.3 oster RF_ReconUnitNum_t which_ru; 2012 1.3 oster RF_PhysDiskAddr_t *pda, *pdaP; 2013 1.3 oster RF_StripeNum_t parityStripeID; 2014 1.3 oster 2015 1.3 oster parityStripeID = rf_RaidAddressToParityStripeID(&(raidPtr->Layout), 2016 1.3 oster asmap->raidAddress, &which_ru); 2017 1.3 oster if (rf_dagDebug) { 2018 1.3 oster printf("[Creating RAID level 1 write DAG]\n"); 2019 1.3 oster } 2020 1.3 oster nWmirNodes = (asmap->parityInfo->next) ? 2 : 1; /* 2 implies access not 2021 1.3 oster * SU aligned */ 2022 1.3 oster nWndNodes = (asmap->physInfo->next) ? 2 : 1; 2023 1.3 oster 2024 1.3 oster /* alloc the Wnd nodes and the Wmir node */ 2025 1.3 oster if (asmap->numDataFailed == 1) 2026 1.3 oster nWndNodes--; 2027 1.3 oster if (asmap->numParityFailed == 1) 2028 1.3 oster nWmirNodes--; 2029 1.3 oster 2030 1.3 oster /* total number of nodes = nWndNodes + nWmirNodes + (block + unblock + 2031 1.3 oster * terminator) */ 2032 1.3 oster RF_CallocAndAdd(nodes, nWndNodes + nWmirNodes + 3, sizeof(RF_DagNode_t), (RF_DagNode_t *), allocList); 2033 1.3 oster i = 0; 2034 1.3 oster wndNode = &nodes[i]; 2035 1.3 oster i += nWndNodes; 2036 1.3 oster wmirNode = &nodes[i]; 2037 1.3 oster i += nWmirNodes; 2038 1.3 oster blockNode = &nodes[i]; 2039 1.3 oster i += 1; 2040 1.3 oster unblockNode = &nodes[i]; 2041 1.3 oster i += 1; 2042 1.3 oster termNode = &nodes[i]; 2043 1.3 oster i += 1; 2044 1.3 oster RF_ASSERT(i == (nWndNodes + nWmirNodes + 3)); 2045 1.3 oster 2046 1.3 oster /* this dag can commit immediately */ 2047 1.3 oster dag_h->numCommitNodes = 0; 2048 1.3 oster dag_h->numCommits = 0; 2049 1.3 oster dag_h->numSuccedents = 1; 2050 1.3 oster 2051 1.3 oster /* initialize the unblock and term nodes */ 2052 1.3 oster rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, (nWndNodes + nWmirNodes), 0, 0, 0, dag_h, "Nil", allocList); 2053 1.3 oster rf_InitNode(unblockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc, NULL, 1, (nWndNodes + nWmirNodes), 0, 0, dag_h, "Nil", allocList); 2054 1.3 oster rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc, NULL, 0, 1, 0, 0, dag_h, "Trm", allocList); 2055 1.3 oster 2056 1.3 oster /* initialize the wnd nodes */ 2057 1.3 oster if (nWndNodes > 0) { 2058 1.3 oster pda = asmap->physInfo; 2059 1.3 oster for (i = 0; i < nWndNodes; i++) { 2060 1.3 oster rf_InitNode(&wndNode[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wpd", allocList); 2061 1.3 oster RF_ASSERT(pda != NULL); 2062 1.3 oster wndNode[i].params[0].p = pda; 2063 1.3 oster wndNode[i].params[1].p = pda->bufPtr; 2064 1.3 oster wndNode[i].params[2].v = parityStripeID; 2065 1.3 oster wndNode[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 2066 1.3 oster pda = pda->next; 2067 1.3 oster } 2068 1.3 oster RF_ASSERT(pda == NULL); 2069 1.3 oster } 2070 1.3 oster /* initialize the mirror nodes */ 2071 1.3 oster if (nWmirNodes > 0) { 2072 1.3 oster pda = asmap->physInfo; 2073 1.3 oster pdaP = asmap->parityInfo; 2074 1.3 oster for (i = 0; i < nWmirNodes; i++) { 2075 1.3 oster rf_InitNode(&wmirNode[i], rf_wait, RF_FALSE, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, rf_GenericWakeupFunc, 1, 1, 4, 0, dag_h, "Wsd", allocList); 2076 1.3 oster RF_ASSERT(pda != NULL); 2077 1.3 oster wmirNode[i].params[0].p = pdaP; 2078 1.3 oster wmirNode[i].params[1].p = pda->bufPtr; 2079 1.3 oster wmirNode[i].params[2].v = parityStripeID; 2080 1.3 oster wmirNode[i].params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); 2081 1.3 oster pda = pda->next; 2082 1.3 oster pdaP = pdaP->next; 2083 1.3 oster } 2084 1.3 oster RF_ASSERT(pda == NULL); 2085 1.3 oster RF_ASSERT(pdaP == NULL); 2086 1.3 oster } 2087 1.3 oster /* link the header node to the block node */ 2088 1.3 oster RF_ASSERT(dag_h->numSuccedents == 1); 2089 1.3 oster RF_ASSERT(blockNode->numAntecedents == 0); 2090 1.3 oster dag_h->succedents[0] = blockNode; 2091 1.3 oster 2092 1.3 oster /* link the block node to the write nodes */ 2093 1.3 oster RF_ASSERT(blockNode->numSuccedents == (nWndNodes + nWmirNodes)); 2094 1.3 oster for (i = 0; i < nWndNodes; i++) { 2095 1.3 oster RF_ASSERT(wndNode[i].numAntecedents == 1); 2096 1.3 oster blockNode->succedents[i] = &wndNode[i]; 2097 1.3 oster wndNode[i].antecedents[0] = blockNode; 2098 1.3 oster wndNode[i].antType[0] = rf_control; 2099 1.3 oster } 2100 1.3 oster for (i = 0; i < nWmirNodes; i++) { 2101 1.3 oster RF_ASSERT(wmirNode[i].numAntecedents == 1); 2102 1.3 oster blockNode->succedents[i + nWndNodes] = &wmirNode[i]; 2103 1.3 oster wmirNode[i].antecedents[0] = blockNode; 2104 1.3 oster wmirNode[i].antType[0] = rf_control; 2105 1.3 oster } 2106 1.3 oster 2107 1.3 oster /* link the write nodes to the unblock node */ 2108 1.3 oster RF_ASSERT(unblockNode->numAntecedents == (nWndNodes + nWmirNodes)); 2109 1.3 oster for (i = 0; i < nWndNodes; i++) { 2110 1.3 oster RF_ASSERT(wndNode[i].numSuccedents == 1); 2111 1.3 oster wndNode[i].succedents[0] = unblockNode; 2112 1.3 oster unblockNode->antecedents[i] = &wndNode[i]; 2113 1.3 oster unblockNode->antType[i] = rf_control; 2114 1.3 oster } 2115 1.3 oster for (i = 0; i < nWmirNodes; i++) { 2116 1.3 oster RF_ASSERT(wmirNode[i].numSuccedents == 1); 2117 1.3 oster wmirNode[i].succedents[0] = unblockNode; 2118 1.3 oster unblockNode->antecedents[i + nWndNodes] = &wmirNode[i]; 2119 1.3 oster unblockNode->antType[i + nWndNodes] = rf_control; 2120 1.3 oster } 2121 1.3 oster 2122 1.3 oster /* link the unblock node to the term node */ 2123 1.3 oster RF_ASSERT(unblockNode->numSuccedents == 1); 2124 1.3 oster RF_ASSERT(termNode->numAntecedents == 1); 2125 1.3 oster RF_ASSERT(termNode->numSuccedents == 0); 2126 1.3 oster unblockNode->succedents[0] = termNode; 2127 1.3 oster termNode->antecedents[0] = unblockNode; 2128 1.3 oster termNode->antType[0] = rf_control; 2129 1.1 oster 2130 1.3 oster return; 2131 1.1 oster } 2132 1.9 oster #endif 2133
Indexes created Tue Oct 14 06:10:07 GMT 2025