raid6_recover.c 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220
  1. /* raid6_recover.c - module to recover from faulty RAID6 arrays. */
  2. /*
  3. * GRUB -- GRand Unified Bootloader
  4. * Copyright (C) 2006,2007,2008,2009 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. #include <grub/dl.h>
  20. #include <grub/disk.h>
  21. #include <grub/mm.h>
  22. #include <grub/err.h>
  23. #include <grub/misc.h>
  24. #include <grub/raid.h>
  25. static grub_uint8_t raid6_table1[256][256];
  26. static grub_uint8_t raid6_table2[256][256];
  27. static void
  28. grub_raid_block_mul (grub_uint8_t mul, char *buf, int size)
  29. {
  30. int i;
  31. grub_uint8_t *p;
  32. p = (grub_uint8_t *) buf;
  33. for (i = 0; i < size; i++, p++)
  34. *p = raid6_table1[mul][*p];
  35. }
  36. static void
  37. grub_raid6_init_table (void)
  38. {
  39. int i, j;
  40. for (i = 0; i < 256; i++)
  41. raid6_table1[i][1] = raid6_table1[1][i] = i;
  42. for (i = 2; i < 256; i++)
  43. for (j = i; j < 256; j++)
  44. {
  45. int n;
  46. grub_uint8_t c;
  47. n = i >> 1;
  48. c = raid6_table1[n][j];
  49. c = (c << 1) ^ ((c & 0x80) ? 0x1d : 0);
  50. if (i & 1)
  51. c ^= j;
  52. raid6_table1[j][i] = raid6_table1[i][j] = c;
  53. }
  54. raid6_table2[0][0] = 1;
  55. for (i = 1; i < 256; i++)
  56. raid6_table2[i][i] = raid6_table1[raid6_table2[i - 1][i - 1]][2];
  57. for (i = 0; i < 254; i++)
  58. for (j = 0; j < 254; j++)
  59. {
  60. grub_uint8_t c, n;
  61. int k;
  62. if (i == j)
  63. continue;
  64. k = i - j;
  65. if (k < 0)
  66. k += 255;
  67. c = n = raid6_table2[k][k] ^ 1;
  68. for (k = 0; k < 253; k++)
  69. c = raid6_table1[c][n];
  70. raid6_table2[i][j] = raid6_table1[raid6_table2[255 - j][255 - j]][c];
  71. }
  72. }
  73. static grub_err_t
  74. grub_raid6_recover (struct grub_raid_array *array, int disknr, int p,
  75. char *buf, grub_disk_addr_t sector, int size)
  76. {
  77. int i, q, pos;
  78. int bad1 = -1, bad2 = -1;
  79. char *pbuf = 0, *qbuf = 0;
  80. size <<= GRUB_DISK_SECTOR_BITS;
  81. pbuf = grub_zalloc (size);
  82. if (!pbuf)
  83. goto quit;
  84. qbuf = grub_zalloc (size);
  85. if (!qbuf)
  86. goto quit;
  87. q = p + 1;
  88. if (q == (int) array->total_devs)
  89. q = 0;
  90. pos = q + 1;
  91. if (pos == (int) array->total_devs)
  92. pos = 0;
  93. for (i = 0; i < (int) array->total_devs - 2; i++)
  94. {
  95. if (pos == disknr)
  96. bad1 = i;
  97. else
  98. {
  99. if ((array->device[pos]) &&
  100. (! grub_disk_read (array->device[pos], sector, 0, size, buf)))
  101. {
  102. grub_raid_block_xor (pbuf, buf, size);
  103. grub_raid_block_mul (raid6_table2[i][i], buf, size);
  104. grub_raid_block_xor (qbuf, buf, size);
  105. }
  106. else
  107. {
  108. /* Too many bad devices */
  109. if (bad2 >= 0)
  110. goto quit;
  111. bad2 = i;
  112. grub_errno = GRUB_ERR_NONE;
  113. }
  114. }
  115. pos++;
  116. if (pos == (int) array->total_devs)
  117. pos = 0;
  118. }
  119. /* Invalid disknr or p */
  120. if (bad1 < 0)
  121. goto quit;
  122. if (bad2 < 0)
  123. {
  124. /* One bad device */
  125. if ((array->device[p]) &&
  126. (! grub_disk_read (array->device[p], sector, 0, size, buf)))
  127. {
  128. grub_raid_block_xor (buf, pbuf, size);
  129. goto quit;
  130. }
  131. if (! array->device[q])
  132. {
  133. grub_error (GRUB_ERR_READ_ERROR, "not enough disk to restore");
  134. goto quit;
  135. }
  136. grub_errno = GRUB_ERR_NONE;
  137. if (grub_disk_read (array->device[q], sector, 0, size, buf))
  138. goto quit;
  139. grub_raid_block_xor (buf, qbuf, size);
  140. grub_raid_block_mul (raid6_table2[255 - bad1][255 - bad1], buf,
  141. size);
  142. }
  143. else
  144. {
  145. /* Two bad devices */
  146. grub_uint8_t c;
  147. if ((! array->device[p]) || (! array->device[q]))
  148. {
  149. grub_error (GRUB_ERR_READ_ERROR, "not enough disk to restore");
  150. goto quit;
  151. }
  152. if (grub_disk_read (array->device[p], sector, 0, size, buf))
  153. goto quit;
  154. grub_raid_block_xor (pbuf, buf, size);
  155. if (grub_disk_read (array->device[q], sector, 0, size, buf))
  156. goto quit;
  157. grub_raid_block_xor (qbuf, buf, size);
  158. c = raid6_table2[bad2][bad1];
  159. grub_raid_block_mul (c, qbuf, size);
  160. c = raid6_table1[raid6_table2[bad2][bad2]][c];
  161. grub_raid_block_mul (c, pbuf, size);
  162. grub_raid_block_xor (pbuf, qbuf, size);
  163. grub_memcpy (buf, pbuf, size);
  164. }
  165. quit:
  166. grub_free (pbuf);
  167. grub_free (qbuf);
  168. return grub_errno;
  169. }
  170. GRUB_MOD_INIT(raid6rec)
  171. {
  172. grub_raid6_init_table ();
  173. grub_raid6_recover_func = grub_raid6_recover;
  174. }
  175. GRUB_MOD_FINI(raid6rec)
  176. {
  177. grub_raid6_recover_func = 0;
  178. }