root/dev/raidframe/rf_decluster.c

DEFINITIONS

1. rf_ConfigureDeclustered
2. rf_ShutdownDeclusteredDS
3. rf_ConfigureDeclusteredDS
4. rf_MapSectorDeclustered
5. rf_MapParityDeclustered
6. rf_IdentifyStripeDeclustered
7. rf_GetDefaultHeadSepLimitDeclustered
8. rf_GetDefaultNumFloatingReconBuffersDeclustered
9. rf_decluster_adjust_params
10. rf_MapSIDToPSIDDeclustered
11. rf_remap_to_spare_space
12. rf_InstallSpareTable
13. rf_SetSpareTable
14. rf_GetNumSpareRUsDeclustered
15. rf_FreeSpareTable

    1 /*      $OpenBSD: rf_decluster.c,v 1.5 2002/12/16 07:01:03 tdeval Exp $ */
    2 /*      $NetBSD: rf_decluster.c,v 1.5 2000/03/07 01:54:29 oster Exp $   */
    4 /*
    5  * Copyright (c) 1995 Carnegie-Mellon University.
    6  * All rights reserved.
    7  *
    8  * Author: Mark Holland
    9  *
   10  * Permission to use, copy, modify and distribute this software and
   11  * its documentation is hereby granted, provided that both the copyright
   12  * notice and this permission notice appear in all copies of the
   13  * software, derivative works or modified versions, and any portions
   14  * thereof, and that both notices appear in supporting documentation.
   15  *
   16  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
   17  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
   18  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
   19  *
   20  * Carnegie Mellon requests users of this software to return to
   21  *
   22  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
   23  *  School of Computer Science
   24  *  Carnegie Mellon University
   25  *  Pittsburgh PA 15213-3890
   26  *
   27  * any improvements or extensions that they make and grant Carnegie the
   28  * rights to redistribute these changes.
   29  */
   31 /*****************************************************************************
   32  *
   33  * rf_decluster.c -- Code related to the declustered layout.
   34  *
   35  * Created 10-21-92 (MCH)
   36  *
   37  * Nov 93:      Adding support for distributed sparing. This code is a little
   38  *              complex; the basic layout used is as follows:
   39  *              Let F = (v-1)/GCD(r,v-1). The spare space for each set of
   40  *              F consecutive fulltables is grouped together and placed after
   41  *              that set of tables.
   42  *                      +-------------------------------+
   43  *                      |         F fulltables          |
   44  *                      |         Spare Space           |
   45  *                      |         F fulltables          |
   46  *                      |         Spare Space           |
   47  *                      |             ...               |
   48  *                      +-------------------------------+
   49  *
   50  *****************************************************************************/
   52 #include "rf_types.h"
   53 #include "rf_raid.h"
   54 #include "rf_raidframe.h"
   55 #include "rf_configure.h"
   56 #include "rf_decluster.h"
   57 #include "rf_debugMem.h"
   58 #include "rf_utils.h"
   59 #include "rf_alloclist.h"
   60 #include "rf_general.h"
   61 #include "rf_shutdown.h"
   63 extern int rf_copyback_in_progress;     /* Debug only. */
   65 /* Found in rf_kintf.c */
   66 int  rf_GetSpareTableFromDaemon(RF_SparetWait_t *);
   68 /* Configuration code. */
   70 int
rf_ConfigureDeclustered(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
RF_Config_t *cfgPtr)
   73 {
RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
   75         int b, v, k, r, lambda; /* block design params */
   76         int i, j;
RF_RowCol_t *first_avail_slot;
RF_StripeCount_t complete_FT_count, numCompleteFullTablesPerDisk;
RF_DeclusteredConfigInfo_t *info;
RF_StripeCount_t PUsPerDisk, spareRegionDepthInPUs,
numCompleteSpareRegionsPerDisk, extraPUsPerDisk;
RF_StripeCount_t totSparePUsPerDisk;
RF_SectorNum_t diskOffsetOfLastFullTableInSUs;
RF_SectorCount_t SpareSpaceInSUs;
   85         char *cfgBuf = (char *) (cfgPtr->layoutSpecific);
RF_StripeNum_t l, SUID;
SUID = l = 0;
numCompleteSpareRegionsPerDisk = 0;
   91         /* 1. Create layout specific structure. */
RF_MallocAndAdd(info, sizeof(RF_DeclusteredConfigInfo_t),
   93             (RF_DeclusteredConfigInfo_t *), raidPtr->cleanupList);
   94         if (info == NULL)
   95                 return (ENOMEM);
layoutPtr->layoutSpecificInfo = (void *) info;
info->SpareTable = NULL;
   99         /* 2. Extract parameters from the config structure. */
  100         if (layoutPtr->map->flags & RF_DISTRIBUTE_SPARE) {
bcopy(cfgBuf, info->sparemap_fname, RF_SPAREMAP_NAME_LEN);
  102         }
cfgBuf += RF_SPAREMAP_NAME_LEN;
b = *((int *) cfgBuf);
cfgBuf += sizeof(int);
v = *((int *) cfgBuf);
cfgBuf += sizeof(int);
k = *((int *) cfgBuf);
cfgBuf += sizeof(int);
r = *((int *) cfgBuf);
cfgBuf += sizeof(int);
lambda = *((int *) cfgBuf);
cfgBuf += sizeof(int);
raidPtr->noRotate = *((int *) cfgBuf);
cfgBuf += sizeof(int);
  118         /*
  119          * The sparemaps are generated assuming that parity is rotated, so we
  120          * issue a warning if both distributed sparing and no-rotate are on at
  121          * the same time.
  122          */
  123         if ((layoutPtr->map->flags & RF_DISTRIBUTE_SPARE) &&
raidPtr->noRotate) {
RF_ERRORMSG("Warning:  distributed sparing specified without"
  126                     " parity rotation.\n");
  127         }
  128         if (raidPtr->numCol != v) {
RF_ERRORMSG2("RAID: config error: table element count (%d)"
  130                     " not equal to no. of cols (%d).\n", v, raidPtr->numCol);
  131                 return (EINVAL);
  132         }
  133         /* 3. Set up the values used in the mapping code. */
info->BlocksPerTable = b;
info->Lambda = lambda;
info->NumParityReps = info->groupSize = k;
  137         /* b blks, k-1 SUs each. */
info->SUsPerTable = b * (k - 1) * layoutPtr->SUsPerPU;
info->SUsPerFullTable = k * info->SUsPerTable;  /* rot k times */
info->PUsPerBlock = k - 1;
info->SUsPerBlock = info->PUsPerBlock * layoutPtr->SUsPerPU;
info->TableDepthInPUs = (b * k) / v;
  143         /* k repetitions. */
info->FullTableDepthInPUs = info->TableDepthInPUs * k;
  146         /* Used only in distributed sparing case. */
  147         /* (v-1)/gcd fulltables. */
info->FullTablesPerSpareRegion = (v - 1) / rf_gcd(r, v - 1);
info->TablesPerSpareRegion = k * info->FullTablesPerSpareRegion;
info->SpareSpaceDepthPerRegionInSUs = (r * info->TablesPerSpareRegion /
  151             (v - 1)) * layoutPtr->SUsPerPU;
  153         /* Check to make sure the block design is sufficiently small. */
  154         if ((raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE)) {
  155                 if (info->FullTableDepthInPUs * layoutPtr->SUsPerPU +
info->SpareSpaceDepthPerRegionInSUs >
layoutPtr->stripeUnitsPerDisk) {
RF_ERRORMSG3("RAID: config error: Full Table depth"
  159                             " (%d) + Spare Space (%d) larger than disk size"
  160                             " (%d) (BD too big).\n",
  161                             (int) info->FullTableDepthInPUs,
  162                             (int) info->SpareSpaceDepthPerRegionInSUs,
  163                             (int) layoutPtr->stripeUnitsPerDisk);
  164                         return (EINVAL);
  165                 }
  166         } else {
  167                 if (info->TableDepthInPUs * layoutPtr->SUsPerPU >
layoutPtr->stripeUnitsPerDisk) {
RF_ERRORMSG2("RAID: config error: Table depth (%d)"
  170                             " larger than disk size (%d) (BD too big).\n",
  171                             (int) (info->TableDepthInPUs * layoutPtr->SUsPerPU),
  172                             (int) layoutPtr->stripeUnitsPerDisk);
  173                         return (EINVAL);
  174                 }
  175         }
  178         /*
  179          * Compute the size of each disk, and the number of tables in the last
  180          * fulltable (which need not be complete).
  181          */
  182         if (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) {
PUsPerDisk = layoutPtr->stripeUnitsPerDisk /
layoutPtr->SUsPerPU;
spareRegionDepthInPUs =
  187                     (info->TablesPerSpareRegion * info->TableDepthInPUs +
  188                     (info->TablesPerSpareRegion * info->TableDepthInPUs) /
  189                     (v - 1));
info->SpareRegionDepthInSUs =
spareRegionDepthInPUs * layoutPtr->SUsPerPU;
numCompleteSpareRegionsPerDisk =
PUsPerDisk / spareRegionDepthInPUs;
info->NumCompleteSRs = numCompleteSpareRegionsPerDisk;
extraPUsPerDisk = PUsPerDisk % spareRegionDepthInPUs;
  198                 /*
  199                  * Assume conservatively that we need the full amount of spare
  200                  * space in one region in order to provide spares for the
  201                  * partial spare region at the end of the array. We set "i"
  202                  * to the number of tables in the partial spare region. This
  203                  * may actually include some fulltables.
  204                  */
extraPUsPerDisk -= (info->SpareSpaceDepthPerRegionInSUs /
layoutPtr->SUsPerPU);
  207                 if (extraPUsPerDisk <= 0)
i = 0;
  209                 else
i = extraPUsPerDisk / info->TableDepthInPUs;
complete_FT_count = raidPtr->numRow *
  213                     (numCompleteSpareRegionsPerDisk *
  214                     (info->TablesPerSpareRegion / k) + i / k);
info->FullTableLimitSUID =
complete_FT_count * info->SUsPerFullTable;
info->ExtraTablesPerDisk = i % k;
  219                 /*
  220                  * Note that in the last spare region, the spare space is
  221                  * complete even though data/parity space is not.
  222                  */
totSparePUsPerDisk = (numCompleteSpareRegionsPerDisk + 1) *
  224                     (info->SpareSpaceDepthPerRegionInSUs / layoutPtr->SUsPerPU);
info->TotSparePUsPerDisk = totSparePUsPerDisk;
layoutPtr->stripeUnitsPerDisk =
  228                     ((complete_FT_count / raidPtr->numRow) *
info->FullTableDepthInPUs + /* data & parity space */
info->ExtraTablesPerDisk * info->TableDepthInPUs +
totSparePUsPerDisk          /* spare space */
  232                     ) * layoutPtr->SUsPerPU;
layoutPtr->dataStripeUnitsPerDisk =
  234                     (complete_FT_count * info->FullTableDepthInPUs +
info->ExtraTablesPerDisk * info->TableDepthInPUs) *
layoutPtr->SUsPerPU * (k - 1) / k;
  238         } else {
  239                 /*
  240                  * Non-dist spare case:  force each disk to contain an
  241                  * integral number of tables.
  242                  */
layoutPtr->stripeUnitsPerDisk /=
  244                     (info->TableDepthInPUs * layoutPtr->SUsPerPU);
layoutPtr->stripeUnitsPerDisk *=
  246                     (info->TableDepthInPUs * layoutPtr->SUsPerPU);
  248                 /*
  249                  * Compute the number of tables in the last fulltable, which
  250                  * need not be complete.
  251                  */
complete_FT_count =
  253                     ((layoutPtr->stripeUnitsPerDisk / layoutPtr->SUsPerPU) /
info->FullTableDepthInPUs) * raidPtr->numRow;
info->FullTableLimitSUID =
complete_FT_count * info->SUsPerFullTable;
info->ExtraTablesPerDisk =
  259                     ((layoutPtr->stripeUnitsPerDisk / layoutPtr->SUsPerPU) /
info->TableDepthInPUs) % k;
  261         }
raidPtr->sectorsPerDisk = layoutPtr->stripeUnitsPerDisk *
layoutPtr->sectorsPerStripeUnit;
  266         /*
  267          * Find the disk offset of the stripe unit where the last fulltable
  268          * starts.
  269          */
numCompleteFullTablesPerDisk = complete_FT_count / raidPtr->numRow;
diskOffsetOfLastFullTableInSUs = numCompleteFullTablesPerDisk *
info->FullTableDepthInPUs * layoutPtr->SUsPerPU;
  273         if (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) {
SpareSpaceInSUs = numCompleteSpareRegionsPerDisk *
info->SpareSpaceDepthPerRegionInSUs;
diskOffsetOfLastFullTableInSUs += SpareSpaceInSUs;
info->DiskOffsetOfLastSpareSpaceChunkInSUs =
diskOffsetOfLastFullTableInSUs + info->ExtraTablesPerDisk *
info->TableDepthInPUs * layoutPtr->SUsPerPU;
  280         }
info->DiskOffsetOfLastFullTableInSUs = diskOffsetOfLastFullTableInSUs;
info->numCompleteFullTablesPerDisk = numCompleteFullTablesPerDisk;
  284         /* 4. Create and initialize the lookup tables. */
info->LayoutTable = rf_make_2d_array(b, k, raidPtr->cleanupList);
  286         if (info->LayoutTable == NULL)
  287                 return (ENOMEM);
info->OffsetTable = rf_make_2d_array(b, k, raidPtr->cleanupList);
  289         if (info->OffsetTable == NULL)
  290                 return (ENOMEM);
info->BlockTable = rf_make_2d_array(info->TableDepthInPUs *
layoutPtr->SUsPerPU, raidPtr->numCol, raidPtr->cleanupList);
  293         if (info->BlockTable == NULL)
  294                 return (ENOMEM);
first_avail_slot = rf_make_1d_array(v, NULL);
  297         if (first_avail_slot == NULL)
  298                 return (ENOMEM);
  300         for (i = 0; i < b; i++)
  301                 for (j = 0; j < k; j++)
info->LayoutTable[i][j] = *cfgBuf++;
  304         /* Initialize the offset table. */
  305         for (i = 0; i < b; i++)
  306                 for (j = 0; j < k; j++) {
info->OffsetTable[i][j] =
first_avail_slot[info->LayoutTable[i][j]];
first_avail_slot[info->LayoutTable[i][j]]++;
  310                 }
  312         /* Initialize the block table. */
  313         for (SUID = l = 0; l < layoutPtr->SUsPerPU; l++) {
  314                 for (i = 0; i < b; i++) {
  315                         for (j = 0; j < k; j++) {
info->BlockTable[(info->OffsetTable[i][j] *
layoutPtr->SUsPerPU) + l]
  318                                     [info->LayoutTable[i][j]] = SUID;
  319                         }
SUID++;
  321                 }
  322         }
rf_free_1d_array(first_avail_slot, v);
  326         /* 5. Set up the remaining redundant-but-useful parameters. */
raidPtr->totalSectors = (k * complete_FT_count + raidPtr->numRow *
info->ExtraTablesPerDisk) * info->SUsPerTable *
layoutPtr->sectorsPerStripeUnit;
layoutPtr->numStripe = (raidPtr->totalSectors /
layoutPtr->sectorsPerStripeUnit) / (k - 1);
  334         /*
  335          * Strange evaluation order below to try and minimize overflow
  336          * problems.
  337          */
layoutPtr->dataSectorsPerStripe =
  340             (k - 1) * layoutPtr->sectorsPerStripeUnit;
layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit <<
raidPtr->logBytesPerSector;
layoutPtr->numDataCol = k - 1;
layoutPtr->numParityCol = 1;
  346         return (0);
  347 }
  349 /* Declustering with distributed sparing. */
  350 void rf_ShutdownDeclusteredDS(RF_ThreadArg_t);
  351 void
rf_ShutdownDeclusteredDS(RF_ThreadArg_t arg)
  353 {
RF_DeclusteredConfigInfo_t *info;
RF_Raid_t *raidPtr;
raidPtr = (RF_Raid_t *) arg;
info =
  359             (RF_DeclusteredConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo;
  360         if (info->SpareTable)
rf_FreeSpareTable(raidPtr);
  362 }
  364 int
rf_ConfigureDeclusteredDS(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
RF_Config_t *cfgPtr)
  367 {
  368         int rc;
rc = rf_ConfigureDeclustered(listp, raidPtr, cfgPtr);
  371         if (rc)
  372                 return (rc);
rc = rf_ShutdownCreate(listp, rf_ShutdownDeclusteredDS, raidPtr);
  375         if (rc) {
RF_ERRORMSG1("Got %d adding shutdown event for"
  377                     " DeclusteredDS.\n", rc);
rf_ShutdownDeclusteredDS(raidPtr);
  379                 return (rc);
  380         }
  382         return (0);
  383 }
  385 void
rf_MapSectorDeclustered(RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector,
RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t *diskSector, int remap)
  388 {
RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
RF_DeclusteredConfigInfo_t *info =
  391             (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
RF_StripeNum_t SUID = raidSector / layoutPtr->sectorsPerStripeUnit;
RF_StripeNum_t FullTableID, FullTableOffset, TableID, TableOffset;
RF_StripeNum_t BlockID, BlockOffset, RepIndex;
RF_StripeCount_t sus_per_fulltable = info->SUsPerFullTable;
RF_StripeCount_t fulltable_depth =
info->FullTableDepthInPUs * layoutPtr->SUsPerPU;
RF_StripeNum_t base_suid = 0, outSU, SpareRegion = 0, SpareSpace = 0;
rf_decluster_adjust_params(layoutPtr, &SUID, &sus_per_fulltable,
  401             &fulltable_depth, &base_suid);
  403         /* Fulltable ID within array (across rows). */
FullTableID = SUID / sus_per_fulltable;
  405         if (raidPtr->numRow == 1)
  406                 *row = 0;       /* Avoid a mod and a div in the common case. */
  407         else {
  408                 *row = FullTableID % raidPtr->numRow;
  409                 /* Convert to fulltable ID on this disk. */
FullTableID /= raidPtr->numRow;
  411         }
  412         if (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) {
SpareRegion = FullTableID / info->FullTablesPerSpareRegion;
SpareSpace = SpareRegion * info->SpareSpaceDepthPerRegionInSUs;
  415         }
FullTableOffset = SUID % sus_per_fulltable;
TableID = FullTableOffset / info->SUsPerTable;
TableOffset = FullTableOffset - TableID * info->SUsPerTable;
BlockID = TableOffset / info->PUsPerBlock;
BlockOffset = TableOffset - BlockID * info->PUsPerBlock;
BlockID %= info->BlocksPerTable;
RepIndex = info->PUsPerBlock - TableID;
  423         if (!raidPtr->noRotate)
BlockOffset += ((BlockOffset >= RepIndex) ? 1 : 0);
  425         *col = info->LayoutTable[BlockID][BlockOffset];
  427         /* Remap to distributed spare space if indicated. */
  428         if (remap) {
RF_ASSERT(raidPtr->Disks[*row][*col].status ==
rf_ds_reconstructing ||
raidPtr->Disks[*row][*col].status == rf_ds_dist_spared ||
  432                     (rf_copyback_in_progress &&
raidPtr->Disks[*row][*col].status == rf_ds_optimal));
rf_remap_to_spare_space(layoutPtr, info, *row, FullTableID,
TableID, BlockID, (base_suid) ? 1 : 0, SpareRegion, col,
  436                     &outSU);
  437         } else {
outSU = base_suid;
outSU += FullTableID * fulltable_depth;
  441                         /* Offset to start of FT. */
outSU += SpareSpace;
  443                         /* Skip rsvd spare space. */
outSU += TableID * info->TableDepthInPUs * layoutPtr->SUsPerPU;
  445                         /* Offset to start of table. */
outSU += info->OffsetTable[BlockID][BlockOffset] *
layoutPtr->SUsPerPU;
  448                         /* Offset to the PU. */
  449         }
outSU += TableOffset / (info->BlocksPerTable * info->PUsPerBlock);
  451                 /* offs to the SU within a PU */
  453         /*
  454          * Convert SUs to sectors, and, if not aligned to SU boundary, add in
  455          * offset to sector.
  456          */
  457         *diskSector = outSU * layoutPtr->sectorsPerStripeUnit +
  458             (raidSector % layoutPtr->sectorsPerStripeUnit);
RF_ASSERT(*col != -1);
  461 }
  463 /*
  464  * Prototyping this inexplicably causes the compile of the layout table
  465  * (rf_layout.c) to fail.
  466  */
  467 void
rf_MapParityDeclustered(RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector,
RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t *diskSector, int remap)
  470 {
RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
RF_DeclusteredConfigInfo_t *info =
  473             (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
RF_StripeNum_t SUID = raidSector / layoutPtr->sectorsPerStripeUnit;
RF_StripeNum_t FullTableID, FullTableOffset, TableID, TableOffset;
RF_StripeNum_t BlockID, BlockOffset, RepIndex;
RF_StripeCount_t sus_per_fulltable = info->SUsPerFullTable;
RF_StripeCount_t fulltable_depth =
info->FullTableDepthInPUs * layoutPtr->SUsPerPU;
RF_StripeNum_t base_suid = 0, outSU, SpareRegion = 0, SpareSpace = 0;
rf_decluster_adjust_params(layoutPtr, &SUID, &sus_per_fulltable,
  483             &fulltable_depth, &base_suid);
  485         /* Compute row & (possibly) spare space exactly as before. */
FullTableID = SUID / sus_per_fulltable;
  487         if (raidPtr->numRow == 1)
  488                 *row = 0;       /* Avoid a mod and a div in the common case. */
  489         else {
  490                 *row = FullTableID % raidPtr->numRow;
  491                 /* Convert to fulltable ID on this disk. */
FullTableID /= raidPtr->numRow;
  493         }
  494         if ((raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE)) {
SpareRegion = FullTableID / info->FullTablesPerSpareRegion;
SpareSpace = SpareRegion * info->SpareSpaceDepthPerRegionInSUs;
  497         }
  498         /* Compute BlockID and RepIndex exactly as before. */
FullTableOffset = SUID % sus_per_fulltable;
TableID = FullTableOffset / info->SUsPerTable;
TableOffset = FullTableOffset - TableID * info->SUsPerTable;
  502         /*TableOffset   = FullTableOffset % info->SUsPerTable;*/
  503         /*BlockID       = (TableOffset / info->PUsPerBlock) %
  504          *info->BlocksPerTable;*/
BlockID = TableOffset / info->PUsPerBlock;
  506         /*BlockOffset   = TableOffset % info->PUsPerBlock;*/
BlockOffset = TableOffset - BlockID * info->PUsPerBlock;
BlockID %= info->BlocksPerTable;
  510         /* The parity block is in the position indicated by RepIndex. */
RepIndex = (raidPtr->noRotate) ?
info->PUsPerBlock : info->PUsPerBlock - TableID;
  513         *col = info->LayoutTable[BlockID][RepIndex];
  515         if (remap) {
RF_ASSERT(raidPtr->Disks[*row][*col].status ==
rf_ds_reconstructing ||
raidPtr->Disks[*row][*col].status == rf_ds_dist_spared ||
  519                     (rf_copyback_in_progress &&
raidPtr->Disks[*row][*col].status == rf_ds_optimal));
rf_remap_to_spare_space(layoutPtr, info, *row, FullTableID,
TableID, BlockID, (base_suid) ? 1 : 0, SpareRegion, col,
  523                     &outSU);
  524         } else {
  526                 /*
  527                  * Compute sector as before, except use RepIndex instead of
  528                  * BlockOffset.
  529                  */
outSU = base_suid;
outSU += FullTableID * fulltable_depth;
outSU += SpareSpace;    /* skip rsvd spare space */
outSU += TableID * info->TableDepthInPUs * layoutPtr->SUsPerPU;
outSU += info->OffsetTable[BlockID][RepIndex] *
layoutPtr->SUsPerPU;
  536         }
outSU += TableOffset / (info->BlocksPerTable * info->PUsPerBlock);
  539         *diskSector = outSU * layoutPtr->sectorsPerStripeUnit +
  540             (raidSector % layoutPtr->sectorsPerStripeUnit);
RF_ASSERT(*col != -1);
  543 }
  545 /*
  546  * Return an array of ints identifying the disks that comprise the stripe
  547  * containing the indicated address.
  548  * The caller must _never_ attempt to modify this array.
  549  */
  550 void
rf_IdentifyStripeDeclustered(RF_Raid_t *raidPtr, RF_RaidAddr_t addr,
RF_RowCol_t **diskids, RF_RowCol_t *outRow)
  553 {
RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
RF_DeclusteredConfigInfo_t *info =
  556             (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
RF_StripeCount_t sus_per_fulltable = info->SUsPerFullTable;
RF_StripeCount_t fulltable_depth =
info->FullTableDepthInPUs * layoutPtr->SUsPerPU;
RF_StripeNum_t base_suid = 0;
RF_StripeNum_t SUID = rf_RaidAddressToStripeUnitID(layoutPtr, addr);
RF_StripeNum_t stripeID, FullTableID;
  563         int tableOffset;
rf_decluster_adjust_params(layoutPtr, &SUID, &sus_per_fulltable,
  566             &fulltable_depth, &base_suid);
  567         /* Fulltable ID within array (across rows). */
FullTableID = SUID / sus_per_fulltable;
  569         *outRow = FullTableID % raidPtr->numRow;
  570         /* Find stripe offset into array. */
stripeID = rf_StripeUnitIDToStripeID(layoutPtr, SUID);
  572         /* Find offset into block design table. */
tableOffset = (stripeID % info->BlocksPerTable);
  574         *diskids = info->LayoutTable[tableOffset];
  575 }
  577 /*
  578  * This returns the default head-separation limit, measured in
  579  * "required units for reconstruction". Each time a disk fetches
  580  * a unit, it bumps a counter. The head-sep code prohibits any disk
  581  * from getting more than headSepLimit counter values ahead of any
  582  * other.
  583  *
  584  * We assume here that the number of floating recon buffers is already
  585  * set. There are r stripes to be reconstructed in each table, and so
  586  * if we have a total of B buffers, we can have at most B/r tables
  587  * under recon at any one time. In each table, lambda units are required
  588  * from each disk, so given B buffers, the head sep limit has to be
  589  * (lambda*B)/r units. We subtract one to avoid weird boundary cases.
  590  *
  591  * For example, suppose we are given 50 buffers, r=19, and lambda=4 as in
  592  * the 20.5 design. There are 19 stripes/table to be reconstructed, so
  593  * we can have 50/19 tables concurrently under reconstruction, which means
  594  * we can allow the fastest disk to get 50/19 tables ahead of the slower
  595  * disk. There are lambda "required units" for each disk, so the fastest
  596  * disk can get 4*50/19 = 10 counter values ahead of the slowest.
  597  *
  598  * If numBufsToAccumulate is not 1, we need to limit the head sep further
  599  * because multiple bufs will be required for each stripe under recon.
  600  */
RF_HeadSepLimit_t
rf_GetDefaultHeadSepLimitDeclustered(RF_Raid_t *raidPtr)
  603 {
RF_DeclusteredConfigInfo_t *info =
  605             (RF_DeclusteredConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo;
  607         return (info->Lambda * raidPtr->numFloatingReconBufs /
info->TableDepthInPUs / rf_numBufsToAccumulate);
  609 }
  611 /*
  612  * Return the default number of recon buffers to use. The value
  613  * is somewhat arbitrary...  It's intended to be large enough to
  614  * allow for a reasonably large head-sep limit, but small enough
  615  * that you don't use up all your system memory with buffers.
  616  */
  617 int
rf_GetDefaultNumFloatingReconBuffersDeclustered(RF_Raid_t *raidPtr)
  619 {
  620         return (100 * rf_numBufsToAccumulate);
  621 }
  623 /*
  624  * Sectors in the last fulltable of the array need to be handled
  625  * specially since this fulltable can be incomplete. This function
  626  * changes the values of certain params to handle this.
  627  *
  628  * The idea here is that MapSector et. al. figure out which disk the
  629  * addressed unit lives on by computing the modulos of the unit number
  630  * with the number of units per fulltable, table, etc.  In the last
  631  * fulltable, there are fewer units per fulltable, so we need to adjust
  632  * the number of user data units per fulltable to reflect this.
  633  *
  634  * So, we (1) convert the fulltable size and depth parameters to
  635  * the size of the partial fulltable at the end, (2) compute the
  636  * disk sector offset where this fulltable starts, and (3) convert
  637  * the users stripe unit number from an offset into the array to
  638  * an offset into the last fulltable.
  639  */
  640 void
rf_decluster_adjust_params(RF_RaidLayout_t *layoutPtr, RF_StripeNum_t *SUID,
RF_StripeCount_t *sus_per_fulltable, RF_StripeCount_t *fulltable_depth,
RF_StripeNum_t *base_suid)
  644 {
RF_DeclusteredConfigInfo_t *info =
  646             (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
  648         if (*SUID >= info->FullTableLimitSUID) {
  649                 /* New full table size is size of last full table on disk. */
  650                 *sus_per_fulltable =
info->ExtraTablesPerDisk * info->SUsPerTable;
  653                 /* New full table depth is corresponding depth. */
  654                 *fulltable_depth =
info->ExtraTablesPerDisk * info->TableDepthInPUs *
layoutPtr->SUsPerPU;
  658                 /* Set up the new base offset. */
  659                 *base_suid = info->DiskOffsetOfLastFullTableInSUs;
  661                 /*
  662                  * Convert user's array address to an offset into the last
  663                  * fulltable.
  664                  */
  665                 *SUID -= info->FullTableLimitSUID;
  666         }
  667 }
  669 /*
  670  * Map a stripe ID to a parity stripe ID.
  671  * See comment above RaidAddressToParityStripeID in layout.c.
  672  */
  673 void
rf_MapSIDToPSIDDeclustered(RF_RaidLayout_t *layoutPtr, RF_StripeNum_t stripeID,
RF_StripeNum_t *psID, RF_ReconUnitNum_t *which_ru)
  676 {
RF_DeclusteredConfigInfo_t *info;
info = (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
  681         *psID = (stripeID / (layoutPtr->SUsPerPU * info->BlocksPerTable)) *
info->BlocksPerTable + (stripeID % info->BlocksPerTable);
  683         *which_ru = (stripeID % (info->BlocksPerTable * layoutPtr->SUsPerPU)) /
info->BlocksPerTable;
RF_ASSERT((*which_ru) < layoutPtr->SUsPerPU / layoutPtr->SUsPerRU);
  686 }
  688 /*
  689  * Called from MapSector and MapParity to retarget an access at the spare unit.
  690  * Modifies the "col" and "outSU" parameters only.
  691  */
  692 void
rf_remap_to_spare_space(RF_RaidLayout_t *layoutPtr,
RF_DeclusteredConfigInfo_t *info, RF_RowCol_t row,
RF_StripeNum_t FullTableID, RF_StripeNum_t TableID, RF_SectorNum_t BlockID,
RF_StripeNum_t base_suid, RF_StripeNum_t SpareRegion, RF_RowCol_t *outCol,
RF_StripeNum_t *outSU)
  698 {
RF_StripeNum_t ftID, spareTableStartSU, TableInSpareRegion,
lastSROffset, which_ft;
  702         /*
  703          * Note that FullTableID and hence SpareRegion may have gotten
  704          * tweaked by rf_decluster_adjust_params. We detect this by
  705          * noticing that base_suid is not 0.
  706          */
  707         if (base_suid == 0) {
ftID = FullTableID;
  709         } else {
  710                 /*
  711                  * There may be > 1.0 full tables in the last (i.e. partial)
  712                  * spare region. Find out which of these we are in.
  713                  */
lastSROffset = info->NumCompleteSRs *
info->SpareRegionDepthInSUs;
which_ft =
  717                     (info->DiskOffsetOfLastFullTableInSUs - lastSROffset) /
  718                     (info->FullTableDepthInPUs * layoutPtr->SUsPerPU);
  720                 /* Compute the actual full table ID. */
ftID = info->DiskOffsetOfLastFullTableInSUs /
  722                     (info->FullTableDepthInPUs * layoutPtr->SUsPerPU) +
which_ft;
SpareRegion = info->NumCompleteSRs;
  725         }
TableInSpareRegion = (ftID * info->NumParityReps + TableID) %
info->TablesPerSpareRegion;
  729         *outCol = info->SpareTable[TableInSpareRegion][BlockID].spareDisk;
RF_ASSERT(*outCol != -1);
spareTableStartSU = (SpareRegion == info->NumCompleteSRs) ?
info->DiskOffsetOfLastFullTableInSUs + info->ExtraTablesPerDisk *
info->TableDepthInPUs * layoutPtr->SUsPerPU :
  735             (SpareRegion + 1) * info->SpareRegionDepthInSUs -
info->SpareSpaceDepthPerRegionInSUs;
  737         *outSU = spareTableStartSU +
info->SpareTable[TableInSpareRegion][BlockID].spareBlockOffsetInSUs;
  739         if (*outSU >= layoutPtr->stripeUnitsPerDisk) {
printf("rf_remap_to_spare_space: invalid remapped disk SU"
  741                     " offset %ld.\n", (long) *outSU);
  742         }
  743 }
  745 int
rf_InstallSpareTable(RF_Raid_t *raidPtr, RF_RowCol_t frow, RF_RowCol_t fcol)
  747 {
RF_DeclusteredConfigInfo_t *info =
  749             (RF_DeclusteredConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo;
RF_SparetWait_t *req;
  751         int retcode;
RF_Malloc(req, sizeof(*req), (RF_SparetWait_t *));
req->C = raidPtr->numCol;
req->G = raidPtr->Layout.numDataCol + raidPtr->Layout.numParityCol;
req->fcol = fcol;
req->SUsPerPU = raidPtr->Layout.SUsPerPU;
req->TablesPerSpareRegion = info->TablesPerSpareRegion;
req->BlocksPerTable = info->BlocksPerTable;
req->TableDepthInPUs = info->TableDepthInPUs;
req->SpareSpaceDepthPerRegionInSUs =
info->SpareSpaceDepthPerRegionInSUs;
retcode = rf_GetSpareTableFromDaemon(req);
RF_ASSERT(!retcode);
  766         /* XXX -- Fix this to recover gracefully. -- XXX */
  768         return (retcode);
  769 }
  771 /*
  772  * Invoked via ioctl to install a spare table in the kernel.
  773  */
  774 int
rf_SetSpareTable(RF_Raid_t *raidPtr, void *data)
  776 {
RF_DeclusteredConfigInfo_t *info =
  778             (RF_DeclusteredConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo;
RF_SpareTableEntry_t **ptrs;
  780         int i, retcode;
  782         /*
  783          * What we need to copyin is a 2-d array, so first copyin the user
  784          * pointers to the rows in the table.
  785          */
RF_Malloc(ptrs, info->TablesPerSpareRegion *
  787             sizeof(RF_SpareTableEntry_t *), (RF_SpareTableEntry_t **));
retcode = copyin((caddr_t) data, (caddr_t) ptrs,
info->TablesPerSpareRegion * sizeof(RF_SpareTableEntry_t *));
  791         if (retcode)
  792                 return (retcode);
  794         /* Now allocate kernel space for the row pointers. */
RF_Malloc(info->SpareTable, info->TablesPerSpareRegion *
  796             sizeof(RF_SpareTableEntry_t *), (RF_SpareTableEntry_t **));
  798         /*
  799          * Now allocate kernel space for each row in the table, and copy it in
  800          * from user space. */
  801         for (i = 0; i < info->TablesPerSpareRegion; i++) {
RF_Malloc(info->SpareTable[i], info->BlocksPerTable *
  803                     sizeof(RF_SpareTableEntry_t), (RF_SpareTableEntry_t *));
retcode = copyin(ptrs[i], info->SpareTable[i],
info->BlocksPerTable * sizeof(RF_SpareTableEntry_t));
  806                 if (retcode) {
  807                         /* Blow off the memory we have allocated. */
info->SpareTable = NULL;
  809                         return (retcode);
  810                 }
  811         }
  813         /* Free up the temporary array we used. */
RF_Free(ptrs, info->TablesPerSpareRegion *
  815             sizeof(RF_SpareTableEntry_t *));
  817         return (0);
  818 }
RF_ReconUnitCount_t
rf_GetNumSpareRUsDeclustered(RF_Raid_t *raidPtr)
  822 {
RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
  825         return (((RF_DeclusteredConfigInfo_t *)
layoutPtr->layoutSpecificInfo)->TotSparePUsPerDisk);
  827 }
  830 void
rf_FreeSpareTable(RF_Raid_t *raidPtr)
  832 {
  833         long i;
RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
RF_DeclusteredConfigInfo_t *info =
  836             (RF_DeclusteredConfigInfo_t *) layoutPtr->layoutSpecificInfo;
RF_SpareTableEntry_t **table = info->SpareTable;
  839         for (i = 0; i < info->TablesPerSpareRegion; i++) {
RF_Free(table[i], info->BlocksPerTable *
  841                     sizeof(RF_SpareTableEntry_t));
  842         }
RF_Free(table, info->TablesPerSpareRegion *
  844             sizeof(RF_SpareTableEntry_t *));
info->SpareTable = (RF_SpareTableEntry_t **) NULL;
  846 }