rf_map.c

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

/*
 * Copyright (c) 1995 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Author: Mark Holland
 *
 * 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.
 */

/**************************************************************************
 *
 * map.c -- main code for mapping RAID addresses to physical disk addresses
 *
 **************************************************************************/

/*
 * $Locker:  $
 * $Log: rf_map.c,v $
 * Revision 1.52  1996/08/20  19:58:39  jimz
 * initialize numParityFailed and numQFailed to 0 in MarkFailuresInASMList
 *
 * Revision 1.51  1996/08/19  22:26:31  jimz
 * add Chang's bugfixes for double-disk failures in MarkFailuresInASMList
 *
 * Revision 1.50  1996/08/19  21:38:06  jimz
 * stripeOffset was uninitialized in CheckStripeForFailures
 *
 * Revision 1.49  1996/07/31  15:34:56  jimz
 * evenodd changes; bugfixes for double-degraded archs, generalize
 * some formerly PQ-only functions
 *
 * Revision 1.48  1996/07/27  23:36:08  jimz
 * Solaris port of simulator
 *
 * 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/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.45  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.44  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.43  1996/06/07  21:33:04  jimz
 * begin using consistent types for sector numbers,
 * stripe numbers, row+col numbers, recon unit numbers
 *
 * Revision 1.42  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.41  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.40  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.39  1996/05/30  23:22:16  jimz
 * bugfixes of serialization, timing problems
 * more cleanup
 *
 * Revision 1.38  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.37  1996/05/27  18:56:37  jimz
 * more code cleanup
 * better typing
 * compiles in all 3 environments
 *
 * Revision 1.36  1996/05/23  21:46:35  jimz
 * checkpoint in code cleanup (release prep)
 * lots of types, function names have been fixed
 *
 * Revision 1.35  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.34  1996/05/20  16:14:45  jimz
 * switch to rf_{mutex,cond}_{init,destroy}
 *
 * Revision 1.33  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.32  1996/05/17  00:51:47  jimz
 * reformat for readability
 *
 * Revision 1.31  1996/05/16  23:06:26  jimz
 * convert asmhdr to use RF_FREELIST stuff
 *
 * Revision 1.30  1996/05/16  19:09:42  jimz
 * grow init asm freelist to 32
 *
 * Revision 1.29  1996/05/16  15:27:55  jimz
 * prime freelist pumps for asm and pda lists
 *
 * Revision 1.28  1996/05/02  14:58:35  jimz
 * legibility cleanup
 *
 * Revision 1.27  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.26  1995/12/01  19:25:06  root
 * added copyright info
 *
 * Revision 1.25  1995/11/17  19:01:57  wvcii
 * added call to MapQ in two fault tolerant case
 *
 * Revision 1.24  1995/11/17  15:10:53  wvcii
 * fixed bug in ASMCheckStatus - ASSERT was using disk sector addresses
 * rather than raidAddress
 *
 * Revision 1.23  1995/07/26  03:26:51  robby
 * map the allocation and freeing routines for some stuff non-static
 *
 * Revision 1.22  1995/06/28  09:33:45  holland
 * bug fixes related to dist sparing and multiple-row arrays
 *
 * Revision 1.21  1995/06/28  04:51:08  holland
 * added some asserts against zero-length accesses
 *
 * Revision 1.20  1995/06/23  13:40:06  robby
 * updeated to prototypes in rf_layout.h
 *
 */

#include "rf_types.h"
#include "rf_threadstuff.h"
#include "rf_raid.h"
#include "rf_general.h"
#include "rf_map.h"
#include "rf_freelist.h"
#include "rf_shutdown.h"
#include "rf_sys.h"

static void rf_FreePDAList(RF_PhysDiskAddr_t *start, RF_PhysDiskAddr_t *end, int count);
static void rf_FreeASMList(RF_AccessStripeMap_t *start, RF_AccessStripeMap_t *end,
	int count);

/*****************************************************************************************
 *
 * MapAccess -- main 1st order mapping routine.
 *
 * Maps an access in the RAID address space to the corresponding set of physical disk
 * addresses.  The result is returned as a list of AccessStripeMap structures, one per
 * stripe accessed.  Each ASM structure contains a pointer to a list of PhysDiskAddr
 * structures, which describe the physical locations touched by the user access.  Note
 * that this routine returns only static mapping information, i.e. the list of physical
 * addresses returned does not necessarily identify the set of physical locations that
 * will actually be read or written.
 *
 * The routine also maps the parity.  The physical disk location returned always
 * indicates the entire parity unit, even when only a subset of it is being accessed.
 * This is because an access that is not stripe unit aligned but that spans a stripe
 * unit boundary may require access two distinct portions of the parity unit, and we
 * can't yet tell which portion(s) we'll actually need.  We leave it up to the algorithm
 * selection code to decide what subset of the parity unit to access.
 *
 * Note that addresses in the RAID address space must always be maintained as
 * longs, instead of ints.
 *
 * This routine returns NULL if numBlocks is 0
 *
 ****************************************************************************************/

RF_AccessStripeMapHeader_t *rf_MapAccess(raidPtr, raidAddress, numBlocks, buffer, remap)
  RF_Raid_t         *raidPtr;
  RF_RaidAddr_t      raidAddress; /* starting address in RAID address space */
  RF_SectorCount_t   numBlocks;   /* number of blocks in RAID address space to access */
  caddr_t            buffer;      /* buffer to supply/receive data */
  int                remap;       /* 1 => remap addresses to spare space */
{
  RF_RaidLayout_t            *layoutPtr       = &(raidPtr->Layout);
  RF_AccessStripeMapHeader_t *asm_hdr         = NULL;
  RF_AccessStripeMap_t       *asm_list        = NULL, *asm_p = NULL;
  int                         faultsTolerated = layoutPtr->map->faultsTolerated;
  RF_RaidAddr_t               startAddress    = raidAddress;            /* we'll change raidAddress along the way */
  RF_RaidAddr_t               endAddress      = raidAddress + numBlocks;
  RF_RaidDisk_t             **disks           = raidPtr->Disks;

  RF_PhysDiskAddr_t          *pda_p, *pda_q;
  RF_StripeCount_t            numStripes = 0;
  RF_RaidAddr_t               stripeRealEndAddress, stripeEndAddress, nextStripeUnitAddress;
  RF_RaidAddr_t               startAddrWithinStripe, lastRaidAddr;
  RF_StripeCount_t            totStripes;
  RF_StripeNum_t              stripeID, lastSID, SUID, lastSUID;
  RF_AccessStripeMap_t  *asmList, *t_asm;
  RF_PhysDiskAddr_t     *pdaList, *t_pda;

  /* allocate all the ASMs and PDAs up front */
  lastRaidAddr = raidAddress + numBlocks - 1 ;
  stripeID     = rf_RaidAddressToStripeID(layoutPtr, raidAddress);
  lastSID      = rf_RaidAddressToStripeID(layoutPtr, lastRaidAddr);
  totStripes   = lastSID - stripeID + 1;
  SUID         = rf_RaidAddressToStripeUnitID(layoutPtr, raidAddress);
  lastSUID     = rf_RaidAddressToStripeUnitID(layoutPtr, lastRaidAddr);

  asmList = rf_AllocASMList(totStripes);
  pdaList = rf_AllocPDAList(lastSUID - SUID + 1 + faultsTolerated * totStripes);     /* may also need pda(s) per stripe for parity */
  
  if (raidAddress+numBlocks > raidPtr->totalSectors) {
    RF_ERRORMSG1("Unable to map access because offset (%d) was invalid\n", raidAddress);
    return(NULL);
  }
  if (rf_mapDebug)
    rf_PrintRaidAddressInfo(raidPtr, raidAddress, numBlocks);
  for (; raidAddress < endAddress; ) {
    /* make the next stripe structure */
    RF_ASSERT(asmList);
    t_asm = asmList;
    asmList = asmList->next;
    bzero((char *)t_asm, sizeof(RF_AccessStripeMap_t));
    if (!asm_p)
      asm_list = asm_p = t_asm;
    else {
      asm_p->next = t_asm;
      asm_p = asm_p->next;
    }
    numStripes++;

    /* map SUs from current location to the end of the stripe */
    asm_p->stripeID = /*rf_RaidAddressToStripeID(layoutPtr, raidAddress)*/ stripeID++;
    stripeRealEndAddress = rf_RaidAddressOfNextStripeBoundary(layoutPtr, raidAddress);
    stripeEndAddress = RF_MIN(endAddress,stripeRealEndAddress );
    asm_p->raidAddress    = raidAddress;
    asm_p->endRaidAddress = stripeEndAddress;

    /* map each stripe unit in the stripe */
    pda_p = NULL;
    startAddrWithinStripe = raidAddress;      /* Raid addr of start of portion of access that is within this stripe */
    for (; raidAddress < stripeEndAddress; ) {
      RF_ASSERT(pdaList);
      t_pda = pdaList;
      pdaList = pdaList->next;
      bzero((char *)t_pda, sizeof(RF_PhysDiskAddr_t));
      if (!pda_p) 
	asm_p->physInfo = pda_p = t_pda;
      else {
        pda_p->next = t_pda;
        pda_p = pda_p->next;
      }
      
      pda_p->type = RF_PDA_TYPE_DATA;
      (layoutPtr->map->MapSector)(raidPtr, raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), remap);

      /* mark any failures we find.  failedPDA is don't-care if there is more than one failure */
      pda_p->raidAddress = raidAddress;          /* the RAID address corresponding to this physical disk address */
      nextStripeUnitAddress = rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, raidAddress);
      pda_p->numSector = RF_MIN(endAddress, nextStripeUnitAddress) - raidAddress;
      RF_ASSERT(pda_p->numSector != 0);
      rf_ASMCheckStatus(raidPtr,pda_p,asm_p,disks,0);
      pda_p->bufPtr = buffer + rf_RaidAddressToByte(raidPtr, (raidAddress - startAddress));
      asm_p->totalSectorsAccessed += pda_p->numSector;
      asm_p->numStripeUnitsAccessed++;
      asm_p->origRow = pda_p->row;               /* redundant but harmless to do this in every loop iteration */
      
      raidAddress = RF_MIN(endAddress, nextStripeUnitAddress);
    }

    /* Map the parity. At this stage, the startSector and numSector fields
     * for the parity unit are always set to indicate the entire parity unit.
     * We may modify this after mapping the data portion.
     */
    switch (faultsTolerated)
      {
      case 0:
	break;
      case 1: /* single fault tolerant */
	RF_ASSERT(pdaList);