rf_dagutils.c

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

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Authors: Mark Holland, William V. Courtright II, Jim Zelenka
 *
 * 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_dagutils.c -- utility routines for manipulating dags
 *
 *****************************************************************************/

/*
 * $Locker:  $
 * $Log: rf_dagutils.c,v $
 * Revision 1.55  1996/08/22  14:39:47  jimz
 * reduce v/k fraction (better load balancing)
 *
 * Revision 1.54  1996/08/21  04:14:12  jimz
 * minor workload shift tweaking
 *
 * Revision 1.53  1996/08/20  23:41:16  jimz
 * fix up workload shift computation
 *
 * Revision 1.52  1996/08/20  22:34:16  jimz
 * first cut at fixing workload shift
 * needs work
 *
 * Revision 1.51  1996/08/20  16:51:16  jimz
 * comment more verbosely compute_workload_shift()
 *
 * Revision 1.50  1996/08/11  00:40:50  jimz
 * fix up broken comment
 *
 * Revision 1.49  1996/07/27  23:36:08  jimz
 * Solaris port of simulator
 *
 * Revision 1.48  1996/07/27  18:40:01  jimz
 * cleanup sweep
 *
 * Revision 1.47  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.46  1996/07/18  22:57:14  jimz
 * port simulator to AIX
 *
 * Revision 1.45  1996/06/17  03:24:59  jimz
 * include shutdown.h for define of now-macroized ShutdownCreate
 *
 * Revision 1.44  1996/06/10  12:50:57  jimz
 * Add counters to freelists to track number of allocations, frees,
 * grows, max size, etc. Adjust a couple sets of PRIME params based
 * on the results.
 *
 * Revision 1.43  1996/06/10  11:55:47  jimz
 * Straightened out some per-array/not-per-array distinctions, fixed
 * a couple bugs related to confusion. Added shutdown lists. Removed
 * layout shutdown function (now subsumed by shutdown lists).
 *
 * Revision 1.42  1996/06/07  21:33:04  jimz
 * begin using consistent types for sector numbers,
 * stripe numbers, row+col numbers, recon unit numbers
 *
 * Revision 1.41  1996/06/06  17:28:58  jimz
 * make PrintNodeInfoString aware of new mirroring funcs
 *
 * Revision 1.40  1996/06/05  18:06:02  jimz
 * Major code cleanup. The Great Renaming is now done.
 * Better modularity. Better typing. Fixed a bunch of
 * synchronization bugs. Made a lot of global stuff
 * per-desc or per-array. Removed dead code.
 *
 * Revision 1.39  1996/06/03  23:28:26  jimz
 * more bugfixes
 * check in tree to sync for IPDS runs with current bugfixes
 * there still may be a problem with threads in the script test
 * getting I/Os stuck- not trivially reproducible (runs ~50 times
 * in a row without getting stuck)
 *
 * Revision 1.38  1996/06/02  17:31:48  jimz
 * Moved a lot of global stuff into array structure, where it belongs.
 * Fixed up paritylogging, pss modules in this manner. Some general
 * code cleanup. Removed lots of dead code, some dead files.
 *
 * Revision 1.37  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.36  1996/05/30  23:22:16  jimz
 * bugfixes of serialization, timing problems
 * more cleanup
 *
 * Revision 1.35  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.34  1996/05/27  18:56:37  jimz
 * more code cleanup
 * better typing
 * compiles in all 3 environments
 *
 * Revision 1.33  1996/05/24  22:17:04  jimz
 * continue code + namespace cleanup
 * typed a bunch of flags
 *
 * Revision 1.32  1996/05/24  04:28:55  jimz
 * release cleanup ckpt
 *
 * Revision 1.31  1996/05/23  21:46:35  jimz
 * checkpoint in code cleanup (release prep)
 * lots of types, function names have been fixed
 *
 * Revision 1.30  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.29  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.28  1996/05/16  23:05:52  jimz
 * changed InitNode() to use dag_ptrs field of node when appropriate
 * (see rf_dag.h or comments within InitNode() for details)
 *
 * Revision 1.27  1996/05/16  15:37:19  jimz
 * convert to RF_FREELIST stuff for dag headers
 *
 * Revision 1.26  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.25  1996/05/03  19:56:15  wvcii
 * added misc routines from old dag creation files
 *
 * Revision 1.24  1995/12/12  18:10:06  jimz
 * MIN -> RF_MIN, MAX -> RF_MAX, ASSERT -> RF_ASSERT
 * fix 80-column brain damage in comments
 *
 * Revision 1.23  1995/12/01  15:59:50  root
 * added copyright info
 *
 * Revision 1.22  1995/11/17  15:14:12  wvcii
 * PrintDAG now processes DiskReadMirrorFunc nodes
 *
 * Revision 1.21  1995/11/07  16:22:38  wvcii
 * InitNode and InitNodeFromBuf now initialize commit fields
 * beefed up ValidateDag
 * prettied up PrintDAGList
 *
 */

#include "rf_archs.h"
#include "rf_types.h"
#include "rf_threadstuff.h"
#include "rf_raid.h"
#include "rf_dag.h"
#include "rf_dagutils.h"
#include "rf_dagfuncs.h"
#include "rf_general.h"
#include "rf_freelist.h"
#include "rf_map.h"
#include "rf_shutdown.h"
#include "rf_sys.h"

#define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))

RF_RedFuncs_t rf_xorFuncs = {
	rf_RegularXorFunc, "Reg Xr",
	rf_SimpleXorFunc, "Simple Xr"};

RF_RedFuncs_t rf_xorRecoveryFuncs = {
	rf_RecoveryXorFunc, "Recovery Xr",
	rf_RecoveryXorFunc, "Recovery Xr"};


/******************************************************************************
 *
 * InitNode - initialize a dag node
 *
 * the size of the propList array is always the same as that of the
 * successors array.
 *
 *****************************************************************************/
void rf_InitNode(
  RF_DagNode_t         *node,
  RF_NodeStatus_t       initstatus,
  int                   commit,
  int                 (*doFunc)(),
  int                 (*undoFunc)(),
  int                 (*wakeFunc)(),
  int                   nSucc,
  int                   nAnte,
  int                   nParam,
  int                   nResult,
  RF_DagHeader_t       *hdr,
  char                 *name,
  RF_AllocListElem_t   *alist)
{
  void **ptrs;
  int nptrs;

  if (nAnte > RF_MAX_ANTECEDENTS)
    RF_PANIC();
  node->status         = initstatus;
  node->commitNode     = commit;
  node->doFunc         = doFunc;
  node->undoFunc       = undoFunc;
  node->wakeFunc       = wakeFunc;
  node->numParams      = nParam;
  node->numResults     = nResult;
  node->numAntecedents = nAnte;
  node->numAntDone     = 0;
  node->next           = NULL;
  node->numSuccedents  = nSucc;
  node->name           = name;
  node->dagHdr         = hdr;
  node->visited        = 0;

  /* allocate all the pointers with one call to malloc */
  nptrs = nSucc+nAnte+nResult+nSucc;
  
  if (nptrs <= RF_DAG_PTRCACHESIZE) {
    /*
     * The dag_ptrs field of the node is basically some scribble
     * space to be used here. We could get rid of it, and always
     * allocate the range of pointers, but that's expensive. So,
     * we pick a "common case" size for the pointer cache. Hopefully,
     * we'll find that:
     * (1) Generally, nptrs doesn't exceed RF_DAG_PTRCACHESIZE by
     *     only a little bit (least efficient case)
     * (2) Generally, ntprs isn't a lot less than RF_DAG_PTRCACHESIZE
     *     (wasted memory)
     */
    ptrs = (void **)node->dag_ptrs;
  }
  else {
    RF_CallocAndAdd(ptrs, nptrs, sizeof(void *), (void **), alist);
  }
  node->succedents  = (nSucc)   ? (RF_DagNode_t         **) ptrs                  : NULL;
  node->antecedents = (nAnte)   ? (RF_DagNode_t         **) (ptrs+nSucc)          : NULL;
  node->results     = (nResult) ? (void            **) (ptrs+nSucc+nAnte)         : NULL;
  node->propList    = (nSucc)   ? (RF_PropHeader_t **) (ptrs+nSucc+nAnte+nResult) : NULL;

  if (nParam) {
    if (nParam <= RF_DAG_PARAMCACHESIZE) {
      node->params = (RF_DagParam_t *)node->dag_params;
    }
    else {
      RF_CallocAndAdd(node->params, nParam, sizeof(RF_DagParam_t), (RF_DagParam_t *), alist);
    }
  }
  else {
    node->params = NULL;
  }
}



/******************************************************************************
 *
 * allocation and deallocation routines
 *
 *****************************************************************************/

void rf_FreeDAG(dag_h)
  RF_DagHeader_t  *dag_h;
{
  RF_AccessStripeMapHeader_t *asmap, *t_asmap;
  RF_DagHeader_t *nextDag;
  int i;

  while (dag_h) {
    nextDag = dag_h->next;
    for (i=0; dag_h->memChunk[i] && i < RF_MAXCHUNKS; i++) {
      /* release mem chunks */
      rf_ReleaseMemChunk(dag_h->memChunk[i]);
      dag_h->memChunk[i] = NULL;
    }
    
    RF_ASSERT(i == dag_h->chunkIndex);
    if (dag_h->xtraChunkCnt > 0) {
      /* free xtraMemChunks */
      for (i=0; dag_h->xtraMemChunk[i] && i < dag_h->xtraChunkIndex; i++) {
        rf_ReleaseMemChunk(dag_h->xtraMemChunk[i]);
        dag_h->xtraMemChunk[i] = NULL;
      }
      RF_ASSERT(i == dag_h->xtraChunkIndex);
      /* free ptrs to xtraMemChunks */
      RF_Free(dag_h->xtraMemChunk, dag_h->xtraChunkCnt * sizeof(RF_ChunkDesc_t *));
    }
    rf_FreeAllocList(dag_h->allocList);
    for (asmap = dag_h->asmList; asmap;) {
      t_asmap = asmap;
      asmap = asmap->next;
      rf_FreeAccessStripeMap(t_asmap);
    }
    rf_FreeDAGHeader(dag_h);
    dag_h = nextDag;
  }
}

RF_PropHeader_t *rf_MakePropListEntry(
  RF_DagHeader_t      *dag_h,
  int                  resultNum,
  int                  paramNum,
  RF_PropHeader_t     *next,
  RF_AllocListElem_t  *allocList)
{
  RF_PropHeader_t *p;

  RF_CallocAndAdd(p, 1, sizeof(RF_PropHeader_t),
    (RF_PropHeader_t *), allocList);
  p->resultNum = resultNum;
  p->paramNum = paramNum;
  p->next = next;
  return(p);