disk/raid6_recover.c

   1 /* raid6_recover.c - module to recover from faulty RAID6 arrays.  */
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 2006,2007,2008  Free Software Foundation, Inc.
   5  *
   6  *  GRUB is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  GRUB is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <grub/dl.h>
  21 #include <grub/disk.h>
  22 #include <grub/mm.h>
  23 #include <grub/err.h>
  24 #include <grub/misc.h>
  25 #include <grub/raid.h>
  26
  27 static grub_uint8_t raid6_table1[256][256];
  28 static grub_uint8_t raid6_table2[256][256];
  29
  30 static void
  31 grub_raid_block_mul (grub_uint8_t mul, char *buf, int size)
  32 {
  33   int i;
  34   grub_uint8_t *p;
  35
  36   p = (grub_uint8_t *) buf;
  37   for (i = 0; i < size; i++, p++)
  38     *p = raid6_table1[mul][*p];
  39 }
  40
  41 static void
  42 grub_raid6_init_table (void)
  43 {
  44   int i, j;
  45
  46   for (i = 0; i < 256; i++)
  47     raid6_table1[i][1] = raid6_table1[1][i] = i;
  48
  49   for (i = 2; i < 256; i++)
  50     for (j = i; j < 256; j++)
  51       {
  52         int n;
  53         grub_uint8_t c;
  54
  55         n = i >> 1;
  56
  57         c = raid6_table1[n][j];
  58         c = (c << 1) ^ ((c & 0x80) ? 0x1d : 0);
  59         if (i & 1)
  60           c ^= j;
  61
  62         raid6_table1[j][i] = raid6_table1[i][j] = c;
  63       }
  64
  65   raid6_table2[0][0] = 1;
  66   for (i = 1; i < 256; i++)
  67     raid6_table2[i][i] = raid6_table1[raid6_table2[i - 1][i - 1]][2];
  68
  69   for (i = 0; i < 254; i++)
  70     for (j = 0; j < 254; j++)
  71       {
  72         grub_uint8_t c, n;
  73         int k;
  74
  75         if (i == j)
  76           continue;
  77
  78         k = i - j;
  79         if (k < 0)
  80           k += 255;
  81
  82         c = n = raid6_table2[k][k] ^ 1;
  83         for (k = 0; k < 253; k++)
  84           c = raid6_table1[c][n];
  85
  86         raid6_table2[i][j] = raid6_table1[raid6_table2[255 - j][255 - j]][c];
  87       }
  88 }
  89
  90 static grub_err_t
  91 grub_raid6_recover (struct grub_raid_array *array, int disknr, int p,
  92                     char *buf, grub_disk_addr_t sector, int size)
  93 {
  94   int i, q, pos;
  95   int bad1 = -1, bad2 = -1;
  96   char *pbuf = 0, *qbuf = 0;
  97
  98   size <<= GRUB_DISK_SECTOR_BITS;
  99   pbuf = grub_malloc (size);
 100   if (!pbuf)
 101     goto quit;
 102
 103   qbuf = grub_malloc (size);
 104   if (!qbuf)
 105     goto quit;
 106
 107   q = p + 1;
 108   if (q == (int) array->total_devs)
 109     q = 0;
 110
 111   grub_memset (pbuf, 0, size);
 112   grub_memset (qbuf, 0, size);
 113
 114   pos = q + 1;
 115   if (pos == (int) array->total_devs)
 116     pos = 0;
 117
 118   for (i = 0; i < (int) array->total_devs - 2; i++)
 119     {
 120       if (pos == disknr)
 121         bad1 = i;
 122       else
 123         {
 124           if ((array->device[pos]) &&
 125               (! grub_disk_read (array->device[pos], sector, 0, size, buf)))
 126             {
 127               grub_raid_block_xor (pbuf, buf, size);
 128               grub_raid_block_mul (raid6_table2[i][i], buf, size);
 129               grub_raid_block_xor (qbuf, buf, size);
 130             }
 131           else
 132             {
 133               /* Too many bad devices */
 134               if (bad2 >= 0)
 135                 goto quit;
 136
 137               bad2 = i;
 138               grub_errno = GRUB_ERR_NONE;
 139             }
 140         }
 141
 142       pos++;
 143       if (pos == (int) array->total_devs)
 144         pos = 0;
 145     }
 146
 147   /* Invalid disknr or p */
 148   if (bad1 < 0)
 149     goto quit;
 150
 151   if (bad2 < 0)
 152     {
 153       /* One bad device */
 154       if ((array->device[p]) &&
 155           (! grub_disk_read (array->device[p], sector, 0, size, buf)))
 156         {
 157           grub_raid_block_xor (buf, pbuf, size);
 158           goto quit;
 159         }
 160
 161       if (! array->device[q])
 162         {
 163           grub_error (GRUB_ERR_READ_ERROR, "Not enough disk to restore");
 164           goto quit;
 165         }
 166
 167       grub_errno = GRUB_ERR_NONE;
 168       if (grub_disk_read (array->device[q], sector, 0, size, buf))
 169         goto quit;
 170
 171       grub_raid_block_xor (buf, qbuf, size);
 172       grub_raid_block_mul (raid6_table2[255 - bad1][255 - bad1], buf,
 173                            size);
 174     }
 175   else
 176     {
 177       /* Two bad devices */
 178       grub_uint8_t c;
 179
 180       if ((! array->device[p]) || (! array->device[q]))
 181         {
 182           grub_error (GRUB_ERR_READ_ERROR, "Not enough disk to restore");
 183           goto quit;
 184         }
 185
 186       if (grub_disk_read (array->device[p], sector, 0, size, buf))
 187         goto quit;
 188
 189       grub_raid_block_xor (pbuf, buf, size);
 190
 191       if (grub_disk_read (array->device[q], sector, 0, size, buf))
 192         goto quit;
 193
 194       grub_raid_block_xor (qbuf, buf, size);
 195
 196       c = raid6_table2[bad2][bad1];
 197       grub_raid_block_mul (c, qbuf, size);
 198
 199       c = raid6_table1[raid6_table2[bad2][bad2]][c];
 200       grub_raid_block_mul (c, pbuf, size);
 201
 202       grub_raid_block_xor (pbuf, qbuf, size);
 203       grub_memcpy (buf, pbuf, size);
 204     }
 205
 206 quit:
 207   grub_free (pbuf);
 208   grub_free (qbuf);
 209
 210   return grub_errno;
 211 }
 212
 213 GRUB_MOD_INIT(raid6rec)
 214 {
 215   grub_raid6_init_table ();
 216   grub_raid6_recover_func = grub_raid6_recover;
 217 }
 218
 219 GRUB_MOD_FINI(raid6rec)
 220 {
 221   grub_raid6_recover_func = 0;
 222 }