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