git.sesse.net Git - bcachefs-tools-debian/blob - c_src/raid/raid.h

   1 /*
   2  * Copyright (C) 2013 Andrea Mazzoleni
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  */
  14
  15 #ifndef __RAID_H
  16 #define __RAID_H
  17
  18 /**
  19  * RAID mode supporting up to 6 parities.
  20  *
  21  * It requires SSSE3 to get good performance with triple or more parities.
  22  *
  23  * This is the default mode set after calling raid_init().
  24  */
  25 #define RAID_MODE_CAUCHY 0
  26
  27 /**
  28  * RAID mode supporting up to 3 parities,
  29  *
  30  * It has a fast triple parity implementation without SSSE3, but it cannot
  31  * go beyond triple parity.
  32  *
  33  * This is mostly intended for low end CPUs like ARM and AMD Athlon.
  34  */
  35 #define RAID_MODE_VANDERMONDE 1
  36
  37 /**
  38  * Maximum number of parity disks supported.
  39  */
  40 #define RAID_PARITY_MAX 6
  41
  42 /**
  43  * Maximum number of data disks supported.
  44  */
  45 #define RAID_DATA_MAX 251
  46
  47 /**
  48  * Initializes the RAID system.
  49  *
  50  * You must call this function before any other.
  51  *
  52  * The RAID system is initialized in the RAID_MODE_CAUCHY mode.
  53  */
  54 void raid_init(void);
  55
  56 /**
  57  * Runs a basic functionality self test.
  58  *
  59  * The test is immediate, and it's intended to be run at application
  60  * startup to check the integrity of the RAID system.
  61  *
  62  * It returns 0 on success.
  63  */
  64 int raid_selftest(void);
  65
  66 /**
  67  * Sets the mode to use. One of RAID_MODE_*.
  68  *
  69  * You can change mode at any time, and it will affect next calls to raid_gen(),
  70  * raid_rec() and raid_data().
  71  *
  72  * The two modes are compatible for the first two levels of parity.
  73  * The third one is different.
  74  */
  75 void raid_mode(int mode);
  76
  77 /**
  78  * Sets the zero buffer to use in recovering.
  79  *
  80  * Before calling raid_rec() and raid_data() you must provide a memory
  81  * buffer filled with zero with the same size of the blocks to recover.
  82  *
  83  * This buffer is only read and never written.
  84  */
  85 void raid_zero(void *zero);
  86
  87 /**
  88  * Computes parity blocks.
  89  *
  90  * This function computes the specified number of parity blocks of the
  91  * provided set of data blocks.
  92  *
  93  * Each parity block allows to recover one data block.
  94  *
  95  * @nd Number of data blocks.
  96  * @np Number of parities blocks to compute.
  97  * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
  98  * @v Vector of pointers to the blocks of data and parity.
  99  *   It has (@nd + @np) elements. The starting elements are the blocks for
 100  *   data, following with the parity blocks.
 101  *   Data blocks are only read and not modified. Parity blocks are written.
 102  *   Each block has @size bytes.
 103  */
 104 void raid_gen(int nd, int np, size_t size, void **v);
 105
 106 /**
 107  * Recovers failures in data and parity blocks.
 108  *
 109  * This function recovers all the data and parity blocks marked as bad
 110  * in the @ir vector.
 111  *
 112  * Ensure to have @nr <= @np, otherwise recovering is not possible.
 113  *
 114  * The parities blocks used for recovering are automatically selected from
 115  * the ones NOT present in the @ir vector.
 116  *
 117  * In case there are more parity blocks than needed, the parities at lower
 118  * indexes are used in the recovering, and the others are ignored.
 119  *
 120  * Note that no internal integrity check is done when recovering. If the
 121  * provided parities are correct, the resulting data will be correct.
 122  * If parities are wrong, the resulting recovered data will be wrong.
 123  * This happens even in the case you have more parities blocks than needed,
 124  * and some form of integrity verification would be possible.
 125  *
 126  * @nr Number of failed data and parity blocks to recover.
 127  * @ir[] Vector of @nr indexes of the failed data and parity blocks.
 128  *   The indexes start from 0. They must be in order.
 129  *   The first parity is represented with value @nd, the second with value
 130  *   @nd + 1, just like positions in the @v vector.
 131  * @nd Number of data blocks.
 132  * @np Number of parity blocks.
 133  * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
 134  * @v Vector of pointers to the blocks of data and parity.
 135  *   It has (@nd + @np) elements. The starting elements are the blocks
 136  *   for data, following with the parity blocks.
 137  *   Each block has @size bytes.
 138  */
 139 void raid_rec(int nr, int *ir, int nd, int np, size_t size, void **v);
 140
 141 /**
 142  * Recovers failures in data blocks only.
 143  *
 144  * This function recovers all the data blocks marked as bad in the @id vector.
 145  * The parity blocks are not modified.
 146  *
 147  * @nr Number of failed data blocks to recover.
 148  * @id[] Vector of @nr indexes of the data blocks to recover.
 149  *   The indexes start from 0. They must be in order.
 150  * @ip[] Vector of @nr indexes of the parity blocks to use for recovering.
 151  *   The indexes start from 0. They must be in order.
 152  * @nd Number of data blocks.
 153  * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
 154  * @v Vector of pointers to the blocks of data and parity.
 155  *   It has (@nd + @ip[@nr - 1] + 1) elements. The starting elements are the
 156  *   blocks for data, following with the parity blocks.
 157  *   Each blocks has @size bytes.
 158  */
 159 void raid_data(int nr, int *id, int *ip, int nd, size_t size, void **v);
 160
 161 /**
 162  * Check the provided failed blocks combination.
 163  *
 164  * This function checks if the specified failed blocks combination satisfies
 165  * the redundancy information. A combination is assumed matching, if the
 166  * remaining valid parity is matching the expected value after recovering.
 167  *
 168  * The number of failed blocks @nr must be strictly less than the number of
 169  * parities @np, because you need one more parity to validate the recovering.
 170  *
 171  * No data or parity blocks are modified.
 172  *
 173  * @nr Number of failed data and parity blocks.
 174  * @ir[] Vector of @nr indexes of the failed data and parity blocks.
 175  *   The indexes start from 0. They must be in order.
 176  *   The first parity is represented with value @nd, the second with value
 177  *   @nd + 1, just like positions in the @v vector.
 178  * @nd Number of data blocks.
 179  * @np Number of parity blocks.
 180  * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
 181  * @v Vector of pointers to the blocks of data and parity.
 182  *   It has (@nd + @np) elements. The starting elements are the blocks
 183  *   for data, following with the parity blocks.
 184  *   Each block has @size bytes.
 185  * @return 0 if the check is satisfied. -1 otherwise.
 186  */
 187 int raid_check(int nr, int *ir, int nd, int np, size_t size, void **v);
 188
 189 /**
 190  * Scan for failed blocks.
 191  *
 192  * This function identifies the failed data and parity blocks using the
 193  * available redundancy.
 194  *
 195  * It uses a brute force method, and then the call can be expansive.
 196  * The expected execution time is proportional at the binomial coefficient
 197  * @np + @nd choose @np - 1, usually written as:
 198  *
 199  * ( @np + @nd )
 200  * (           )
 201  * (  @np - 1  )
 202  *
 203  * No data or parity blocks are modified.
 204  *
 205  * The failed block indexes are returned in the @ir vector.
 206  * It must have space for at least @np - 1 values.
 207  *
 208  * The returned @ir vector can then be used in a raid_rec() call to recover
 209  * the failed data and parity blocks.
 210  *
 211  * @ir[] Vector filled with the indexes of the failed data and parity blocks.
 212  *   The indexes start from 0 and they are in order.
 213  *   The first parity is represented with value @nd, the second with value
 214  *   @nd + 1, just like positions in the @v vector.
 215  * @nd Number of data blocks.
 216  * @np Number of parity blocks.
 217  * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
 218  * @v Vector of pointers to the blocks of data and parity.
 219  *   It has (@nd + @np) elements. The starting elements are the blocks
 220  *   for data, following with the parity blocks.
 221  *   Each block has @size bytes.
 222  * @return Number of block indexes returned in the @ir vector.
 223  *   0 if no error is detected.
 224  *   -1 if it's not possible to identify the failed disks.
 225  */
 226 int raid_scan(int *ir, int nd, int np, size_t size, void **v);
 227
 228 #endif
 229