rf_dagdegwr.c

RAIDFrame是个非常好的磁盘阵列RAID仿真工具

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Mark Holland, Daniel Stodolsky, William V. Courtright II
 *
 * Permission to use, copy, modify and distribute this software and
 * its documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 *
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 *
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  [e-mail]
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie the
 * rights to redistribute these changes.
 */

/*
 * rf_dagdegwr.c
 *
 * code for creating degraded write DAGs
 *
 * $Locker:  $
 * $Log: rf_dagdegwr.c,v $
 * Revision 1.22  1996/08/23  14:49:48  jimz
 * remove bogus assert from small write double deg DAG generator
 *
 * Revision 1.21  1996/08/21  05:09:44  jimz
 * get rid of bogus fakery in DoubleDegSmallWrite
 *
 * Revision 1.20  1996/08/21  04:14:35  jimz
 * cleanup doubledegsmallwrite
 * NOTE: we need doubledeglargewrite
 *
 * Revision 1.19  1996/08/19  21:39:38  jimz
 * CommonCreateSimpleDegradedWriteDAG() was unable to correctly create DAGs for
 * complete stripe overwrite accesses- it assumed the necessity to read old
 * data. Rather than do the "right" thing, and risk breaking a critical DAG so
 * close to release, I made a no-op read node to stick in and link up in this
 * case. Seems to work.
 *
 * Revision 1.18  1996/07/31  15:35:34  jimz
 * evenodd changes; bugfixes for double-degraded archs, generalize
 * some formerly PQ-only functions
 *
 * Revision 1.17  1996/07/28  20:31:39  jimz
 * i386netbsd port
 * true/false fixup
 *
 * Revision 1.16  1996/07/27  23:36:08  jimz
 * Solaris port of simulator
 *
 * Revision 1.15  1996/07/27  16:30:19  jimz
 * cleanup sweep
 *
 * Revision 1.14  1996/07/22  19:52:16  jimz
 * switched node params to RF_DagParam_t, a union of
 * a 64-bit int and a void *, for better portability
 * attempted hpux port, but failed partway through for
 * lack of a single C compiler capable of compiling all
 * source files
 *
 * Revision 1.13  1996/06/09  02:36:46  jimz
 * lots of little crufty cleanup- fixup whitespace
 * issues, comment #ifdefs, improve typing in some
 * places (esp size-related)
 *
 * Revision 1.12  1996/06/07  22:26:27  jimz
 * type-ify which_ru (RF_ReconUnitNum_t)
 *
 * Revision 1.11  1996/06/07  21:33:04  jimz
 * begin using consistent types for sector numbers,
 * stripe numbers, row+col numbers, recon unit numbers
 *
 * Revision 1.10  1996/05/31  22:26:54  jimz
 * fix a lot of mapping problems, memory allocation problems
 * found some weird lock issues, fixed 'em
 * more code cleanup
 *
 * Revision 1.9  1996/05/30  11:29:41  jimz
 * Numerous bug fixes. Stripe lock release code disagreed with the taking code
 * about when stripes should be locked (I made it consistent: no parity, no lock)
 * There was a lot of extra serialization of I/Os which I've removed- a lot of
 * it was to calculate values for the cache code, which is no longer with us.
 * More types, function, macro cleanup. Added code to properly quiesce the array
 * on shutdown. Made a lot of stuff array-specific which was (bogusly) general
 * before. Fixed memory allocation, freeing bugs.
 *
 * Revision 1.8  1996/05/27  18:56:37  jimz
 * more code cleanup
 * better typing
 * compiles in all 3 environments
 *
 * Revision 1.7  1996/05/24  22:17:04  jimz
 * continue code + namespace cleanup
 * typed a bunch of flags
 *
 * Revision 1.6  1996/05/24  04:28:55  jimz
 * release cleanup ckpt
 *
 * Revision 1.5  1996/05/23  21:46:35  jimz
 * checkpoint in code cleanup (release prep)
 * lots of types, function names have been fixed
 *
 * Revision 1.4  1996/05/23  00:33:23  jimz
 * code cleanup: move all debug decls to rf_options.c, all extern
 * debug decls to rf_options.h, all debug vars preceded by rf_
 *
 * Revision 1.3  1996/05/18  19:51:34  jimz
 * major code cleanup- fix syntax, make some types consistent,
 * add prototypes, clean out dead code, et cetera
 *
 * Revision 1.2  1996/05/08  21:01:24  jimz
 * fixed up enum type names that were conflicting with other
 * enums and function names (ie, "panic")
 * future naming trends will be towards RF_ and rf_ for
 * everything raidframe-related
 *
 * Revision 1.1  1996/05/03  19:21:50  wvcii
 * Initial revision
 *
 */

#include "rf_types.h"
#include "rf_raid.h"
#include "rf_dag.h"
#include "rf_dagutils.h"
#include "rf_dagfuncs.h"
#include "rf_threadid.h"
#include "rf_debugMem.h"
#include "rf_memchunk.h"
#include "rf_general.h"
#include "rf_dagdegwr.h"
#include "rf_sys.h"


/******************************************************************************
 *
 * General comments on DAG creation:
 * 
 * All DAGs in this file use roll-away error recovery.  Each DAG has a single
 * commit node, usually called "Cmt."  If an error occurs before the Cmt node
 * is reached, the execution engine will halt forward execution and work
 * backward through the graph, executing the undo functions.  Assuming that
 * each node in the graph prior to the Cmt node are undoable and atomic - or -
 * does not make changes to permanent state, the graph will fail atomically.
 * If an error occurs after the Cmt node executes, the engine will roll-forward
 * through the graph, blindly executing nodes until it reaches the end.
 * If a graph reaches the end, it is assumed to have completed successfully.
 *
 * A graph has only 1 Cmt node.
 *
 */


/******************************************************************************
 *
 * The following wrappers map the standard DAG creation interface to the
 * DAG creation routines.  Additionally, these wrappers enable experimentation
 * with new DAG structures by providing an extra level of indirection, allowing
 * the DAG creation routines to be replaced at this single point.
 */

static RF_CREATE_DAG_FUNC_DECL(rf_CreateSimpleDegradedWriteDAG)
{
  rf_CommonCreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp,
    flags, allocList,1, rf_RecoveryXorFunc, RF_TRUE);
}

void rf_CreateDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList)
  RF_Raid_t             *raidPtr;
  RF_AccessStripeMap_t  *asmap;
  RF_DagHeader_t        *dag_h;
  void                  *bp;
  RF_RaidAccessFlags_t   flags;
  RF_AllocListElem_t    *allocList;
{
  RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
  RF_PhysDiskAddr_t *failedPDA = asmap->failedPDA;
  
  RF_ASSERT( asmap->numDataFailed == 1 );
  dag_h->creator = "DegradedWriteDAG";

  /* if the access writes only a portion of the failed unit, and also writes
   * some portion of at least one surviving unit, we create two DAGs, one for
   * the failed component and one for the non-failed component, and do them
   * sequentially.  Note that the fact that we're accessing only a portion of
   * the failed unit indicates that the access either starts or ends in the
   * failed unit, and hence we need create only two dags.  This is inefficient
   * in that the same data or parity can get read and written twice using this
   * structure.  I need to fix this to do the access all at once.
   */
  RF_ASSERT(!(asmap->numStripeUnitsAccessed != 1 && failedPDA->numSector != layoutPtr->sectorsPerStripeUnit));
  rf_CreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags, allocList);
}



/******************************************************************************
 *
 * DAG creation code begins here
 */



/******************************************************************************
 *
 * CommonCreateSimpleDegradedWriteDAG -- creates a DAG to do a degraded-mode
 * write, which is as follows
 *
 *                                        / {Wnq} --\
 * hdr -> blockNode ->  Rod -> Xor -> Cmt -> Wnp ----> unblock -> term
 *                  \  {Rod} /            \  Wnd ---/
 *                                        \ {Wnd} -/
 *
 * commit nodes: Xor, Wnd
 *
 * IMPORTANT:
 * This DAG generator does not work for double-degraded archs since it does not
 * generate Q
 *
 * This dag is essentially identical to the large-write dag, except that the
 * write to the failed data unit is suppressed.
 *
 * IMPORTANT:  this dag does not work in the case where the access writes only
 * a portion of the failed unit, and also writes some portion of at least one
 * surviving SU.  this case is handled in CreateDegradedWriteDAG above.
 *
 * The block & unblock nodes are leftovers from a previous version.  They
 * do nothing, but I haven't deleted them because it would be a tremendous
 * effort to put them back in.
 *
 * This dag is used whenever a one of the data units in a write has failed.
 * If it is the parity unit that failed, the nonredundant write dag (below)
 * is used.
 *****************************************************************************/

void rf_CommonCreateSimpleDegradedWriteDAG(raidPtr, asmap, dag_h, bp, flags,
	allocList, nfaults, redFunc, allowBufferRecycle)
  RF_Raid_t              *raidPtr;
  RF_AccessStripeMap_t   *asmap;
  RF_DagHeader_t         *dag_h;
  void                   *bp;
  RF_RaidAccessFlags_t    flags;
  RF_AllocListElem_t     *allocList;
  int                     nfaults;
  int                   (*redFunc)();
  int                     allowBufferRecycle;
{
  int nNodes, nRrdNodes, nWndNodes, nXorBufs, i, j, paramNum, rdnodesFaked;
  RF_DagNode_t *blockNode, *unblockNode, *wnpNode, *wnqNode, *termNode;
  RF_DagNode_t *nodes, *wndNodes, *rrdNodes, *xorNode, *commitNode;
  RF_SectorCount_t sectorsPerSU;
  RF_ReconUnitNum_t which_ru;
  char *xorTargetBuf = NULL; /* the target buffer for the XOR operation */
  char *overlappingPDAs; /* a temporary array of flags */
  RF_AccessStripeMapHeader_t *new_asm_h[2];
  RF_PhysDiskAddr_t *pda, *parityPDA;
  RF_StripeNum_t parityStripeID;
  RF_PhysDiskAddr_t *failedPDA;
  RF_RaidLayout_t *layoutPtr;

  layoutPtr = &(raidPtr->Layout);
  parityStripeID = rf_RaidAddressToParityStripeID(layoutPtr, asmap->raidAddress,
    &which_ru);
  sectorsPerSU = layoutPtr->sectorsPerStripeUnit;
  /* failedPDA points to the pda within the asm that targets the failed disk */
  failedPDA = asmap->failedPDA;

  if (rf_dagDebug)
    printf("[Creating degraded-write DAG]\n");

  RF_ASSERT( asmap->numDataFailed == 1 );
  dag_h->creator = "SimpleDegradedWriteDAG";

  /*
   * Generate two ASMs identifying the surviving data
   * we need in order to recover the lost data.
   */
  /* overlappingPDAs array must be zero'd */
  RF_Calloc(overlappingPDAs, asmap->numStripeUnitsAccessed, sizeof(char), (char *));
  rf_GenerateFailedAccessASMs(raidPtr, asmap, failedPDA, dag_h, new_asm_h,
    &nXorBufs, NULL, overlappingPDAs, allocList);

  /* create all the nodes at once */
  nWndNodes = asmap->numStripeUnitsAccessed - 1;   /* no access is generated
                                                  * for the failed pda */

  nRrdNodes = ((new_asm_h[0]) ? new_asm_h[0]->stripeMap->numStripeUnitsAccessed : 0) +
              ((new_asm_h[1]) ? new_asm_h[1]->stripeMap->numStripeUnitsAccessed : 0);
  /*
   * XXX
   *
   * There's a bug with a complete stripe overwrite- that means 0 reads
   * of old data, and the rest of the DAG generation code doesn't like
   * that. A release is coming, and I don't wanna risk breaking a critical
   * DAG generator, so here's what I'm gonna do- if there's no read nodes,
   * I'm gonna fake there being a read node, and I'm gonna swap in a
   * no-op node in its place (to make all the link-up code happy).
   * This should be fixed at some point.  --jimz
   */
  if (nRrdNodes == 0) {
    nRrdNodes = 1;
    rdnodesFaked = 1;
  }
  else {
    rdnodesFaked = 0;
  }
  /* lock, unlock, xor, Wnd, Rrd, W(nfaults) */
  nNodes = 5 + nfaults + nWndNodes + nRrdNodes;
  RF_CallocAndAdd(nodes, nNodes, sizeof(RF_DagNode_t),
    (RF_DagNode_t *), allocList);