fs/ocfs2/blockcheck.c

   1 /* -*- mode: c; c-basic-offset: 8; -*-
   2  * vim: noexpandtab sw=8 ts=8 sts=0:
   3  *
   4  * blockcheck.c
   5  *
   6  * Checksum and ECC codes for the OCFS2 userspace library.
   7  *
   8  * Copyright (C) 2006, 2008 Oracle.  All rights reserved.
   9  *
  10  * This program is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU General Public
  12  * License, version 2, as published by the Free Software Foundation.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * General Public License for more details.
  18  */
  19
  20 #include <linux/kernel.h>
  21 #include <linux/types.h>
  22 #include <linux/crc32.h>
  23 #include <linux/buffer_head.h>
  24 #include <linux/bitops.h>
  25 #include <asm/byteorder.h>
  26
  27 #include <cluster/masklog.h>
  28
  29 #include "ocfs2.h"
  30
  31 #include "blockcheck.h"
  32
  33
  34 /*
  35  * We use the following conventions:
  36  *
  37  * d = # data bits
  38  * p = # parity bits
  39  * c = # total code bits (d + p)
  40  */
  41
  42 /*
  43  * Calculate the bit offset in the hamming code buffer based on the bit's
  44  * offset in the data buffer.  Since the hamming code reserves all
  45  * power-of-two bits for parity, the data bit number and the code bit
  46  * number are offest by all the parity bits beforehand.
  47  *
  48  * Recall that bit numbers in hamming code are 1-based.  This function
  49  * takes the 0-based data bit from the caller.
  50  *
  51  * An example.  Take bit 1 of the data buffer.  1 is a power of two (2^0),
  52  * so it's a parity bit.  2 is a power of two (2^1), so it's a parity bit.
  53  * 3 is not a power of two.  So bit 1 of the data buffer ends up as bit 3
  54  * in the code buffer.
  55  */
  56 static unsigned int calc_code_bit(unsigned int i)
  57 {
  58         unsigned int b, p;
  59
  60         /*
  61          * Data bits are 0-based, but we're talking code bits, which
  62          * are 1-based.
  63          */
  64         b = i + 1;
  65
  66         /*
  67          * For every power of two below our bit number, bump our bit.
  68          *
  69          * We compare with (b + 1) becuase we have to compare with what b
  70          * would be _if_ it were bumped up by the parity bit.  Capice?
  71          */
  72         for (p = 0; (1 << p) < (b + 1); p++)
  73                 b++;
  74
  75         return b;
  76 }
  77
  78 /*
  79  * This is the low level encoder function.  It can be called across
  80  * multiple hunks just like the crc32 code.  'd' is the number of bits
  81  * _in_this_hunk_.  nr is the bit offset of this hunk.  So, if you had
  82  * two 512B buffers, you would do it like so:
  83  *
  84  * parity = ocfs2_hamming_encode(0, buf1, 512 * 8, 0);
  85  * parity = ocfs2_hamming_encode(parity, buf2, 512 * 8, 512 * 8);
  86  *
  87  * If you just have one buffer, use ocfs2_hamming_encode_block().
  88  */
  89 u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr)
  90 {
  91         unsigned int i, b;
  92
  93         BUG_ON(!d);
  94
  95         /*
  96          * b is the hamming code bit number.  Hamming code specifies a
  97          * 1-based array, but C uses 0-based.  So 'i' is for C, and 'b' is
  98          * for the algorithm.
  99          *
 100          * The i++ in the for loop is so that the start offset passed
 101          * to ocfs2_find_next_bit_set() is one greater than the previously
 102          * found bit.
 103          */
 104         for (i = 0; (i = ocfs2_find_next_bit(data, d, i)) < d; i++)
 105         {
 106                 /*
 107                  * i is the offset in this hunk, nr + i is the total bit
 108                  * offset.
 109                  */
 110                 b = calc_code_bit(nr + i);
 111
 112                 /*
 113                  * Data bits in the resultant code are checked by
 114                  * parity bits that are part of the bit number
 115                  * representation.  Huh?
 116                  *
 117                  * <wikipedia href="http://en.wikipedia.org/wiki/Hamming_code">
 118                  * In other words, the parity bit at position 2^k
 119                  * checks bits in positions having bit k set in
 120                  * their binary representation.  Conversely, for
 121                  * instance, bit 13, i.e. 1101(2), is checked by
 122                  * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1.
 123                  * </wikipedia>
 124                  *
 125                  * Note that 'k' is the _code_ bit number.  'b' in
 126                  * our loop.
 127                  */
 128                 parity ^= b;
 129         }
 130
 131         /* While the data buffer was treated as little endian, the
 132          * return value is in host endian. */
 133         return parity;
 134 }
 135
 136 u32 ocfs2_hamming_encode_block(void *data, unsigned int blocksize)
 137 {
 138         return ocfs2_hamming_encode(0, data, blocksize * 8, 0);
 139 }
 140
 141 /*
 142  * Like ocfs2_hamming_encode(), this can handle hunks.  nr is the bit
 143  * offset of the current hunk.  If bit to be fixed is not part of the
 144  * current hunk, this does nothing.
 145  *
 146  * If you only have one hunk, use ocfs2_hamming_fix_block().
 147  */
 148 void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr,
 149                        unsigned int fix)
 150 {
 151         unsigned int i, b;
 152
 153         BUG_ON(!d);
 154
 155         /*
 156          * If the bit to fix has an hweight of 1, it's a parity bit.  One
 157          * busted parity bit is its own error.  Nothing to do here.
 158          */
 159         if (hweight32(fix) == 1)
 160                 return;
 161
 162         /*
 163          * nr + d is the bit right past the data hunk we're looking at.
 164          * If fix after that, nothing to do
 165          */
 166         if (fix >= calc_code_bit(nr + d))
 167                 return;
 168
 169         /*
 170          * nr is the offset in the data hunk we're starting at.  Let's
 171          * start b at the offset in the code buffer.  See hamming_encode()
 172          * for a more detailed description of 'b'.
 173          */
 174         b = calc_code_bit(nr);
 175         /* If the fix is before this hunk, nothing to do */
 176         if (fix < b)
 177                 return;
 178
 179         for (i = 0; i < d; i++, b++)
 180         {
 181                 /* Skip past parity bits */
 182                 while (hweight32(b) == 1)
 183                         b++;
 184
 185                 /*
 186                  * i is the offset in this data hunk.
 187                  * nr + i is the offset in the total data buffer.
 188                  * b is the offset in the total code buffer.
 189                  *
 190                  * Thus, when b == fix, bit i in the current hunk needs
 191                  * fixing.
 192                  */
 193                 if (b == fix)
 194                 {
 195                         if (ocfs2_test_bit(i, data))
 196                                 ocfs2_clear_bit(i, data);
 197                         else
 198                                 ocfs2_set_bit(i, data);
 199                         break;
 200                 }
 201         }
 202 }
 203
 204 void ocfs2_hamming_fix_block(void *data, unsigned int blocksize,
 205                              unsigned int fix)
 206 {
 207         ocfs2_hamming_fix(data, blocksize * 8, 0, fix);
 208 }
 209
 210 /*
 211  * This function generates check information for a block.
 212  * data is the block to be checked.  bc is a pointer to the
 213  * ocfs2_block_check structure describing the crc32 and the ecc.
 214  *
 215  * bc should be a pointer inside data, as the function will
 216  * take care of zeroing it before calculating the check information.  If
 217  * bc does not point inside data, the caller must make sure any inline
 218  * ocfs2_block_check structures are zeroed.
 219  *
 220  * The data buffer must be in on-disk endian (little endian for ocfs2).
 221  * bc will be filled with little-endian values and will be ready to go to
 222  * disk.
 223  */
 224 void ocfs2_block_check_compute(void *data, size_t blocksize,
 225                                struct ocfs2_block_check *bc)
 226 {
 227         u32 crc;
 228         u32 ecc;
 229
 230         memset(bc, 0, sizeof(struct ocfs2_block_check));
 231
 232         crc = crc32_le(~0, data, blocksize);
 233         ecc = ocfs2_hamming_encode_block(data, blocksize);
 234
 235         /*
 236          * No ecc'd ocfs2 structure is larger than 4K, so ecc will be no
 237          * larger than 16 bits.
 238          */
 239         BUG_ON(ecc > USHORT_MAX);
 240
 241         bc->bc_crc32e = cpu_to_le32(crc);
 242         bc->bc_ecc = cpu_to_le16((u16)ecc);
 243 }
 244
 245 /*
 246  * This function validates existing check information.  Like _compute,
 247  * the function will take care of zeroing bc before calculating check codes.
 248  * If bc is not a pointer inside data, the caller must have zeroed any
 249  * inline ocfs2_block_check structures.
 250  *
 251  * Again, the data passed in should be the on-disk endian.
 252  */
 253 int ocfs2_block_check_validate(void *data, size_t blocksize,
 254                                struct ocfs2_block_check *bc)
 255 {
 256         int rc = 0;
 257         struct ocfs2_block_check check;
 258         u32 crc, ecc;
 259
 260         check.bc_crc32e = le32_to_cpu(bc->bc_crc32e);
 261         check.bc_ecc = le16_to_cpu(bc->bc_ecc);
 262
 263         memset(bc, 0, sizeof(struct ocfs2_block_check));
 264
 265         /* Fast path - if the crc32 validates, we're good to go */
 266         crc = crc32_le(~0, data, blocksize);
 267         if (crc == check.bc_crc32e)
 268                 goto out;
 269
 270         mlog(ML_ERROR,
 271              "CRC32 failed: stored: %u, computed %u.  Applying ECC.\n",
 272              (unsigned int)check.bc_crc32e, (unsigned int)crc);
 273
 274         /* Ok, try ECC fixups */
 275         ecc = ocfs2_hamming_encode_block(data, blocksize);
 276         ocfs2_hamming_fix_block(data, blocksize, ecc ^ check.bc_ecc);
 277
 278         /* And check the crc32 again */
 279         crc = crc32_le(~0, data, blocksize);
 280         if (crc == check.bc_crc32e)
 281                 goto out;
 282
 283         mlog(ML_ERROR, "Fixed CRC32 failed: stored: %u, computed %u\n",
 284              (unsigned int)check.bc_crc32e, (unsigned int)crc);
 285
 286         rc = -EIO;
 287
 288 out:
 289         bc->bc_crc32e = cpu_to_le32(check.bc_crc32e);
 290         bc->bc_ecc = cpu_to_le16(check.bc_ecc);
 291
 292         return rc;
 293 }
 294
 295 /*
 296  * This function generates check information for a list of buffer_heads.
 297  * bhs is the blocks to be checked.  bc is a pointer to the
 298  * ocfs2_block_check structure describing the crc32 and the ecc.
 299  *
 300  * bc should be a pointer inside data, as the function will
 301  * take care of zeroing it before calculating the check information.  If
 302  * bc does not point inside data, the caller must make sure any inline
 303  * ocfs2_block_check structures are zeroed.
 304  *
 305  * The data buffer must be in on-disk endian (little endian for ocfs2).
 306  * bc will be filled with little-endian values and will be ready to go to
 307  * disk.
 308  */
 309 void ocfs2_block_check_compute_bhs(struct buffer_head **bhs, int nr,
 310                                    struct ocfs2_block_check *bc)
 311 {
 312         int i;
 313         u32 crc, ecc;
 314
 315         BUG_ON(nr < 0);
 316
 317         if (!nr)
 318                 return;
 319
 320         memset(bc, 0, sizeof(struct ocfs2_block_check));
 321
 322         for (i = 0, crc = ~0, ecc = 0; i < nr; i++) {
 323                 crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size);
 324                 /*
 325                  * The number of bits in a buffer is obviously b_size*8.
 326                  * The offset of this buffer is b_size*i, so the bit offset
 327                  * of this buffer is b_size*8*i.
 328                  */
 329                 ecc = (u16)ocfs2_hamming_encode(ecc, bhs[i]->b_data,
 330                                                 bhs[i]->b_size * 8,
 331                                                 bhs[i]->b_size * 8 * i);
 332         }
 333
 334         /*
 335          * No ecc'd ocfs2 structure is larger than 4K, so ecc will be no
 336          * larger than 16 bits.
 337          */
 338         BUG_ON(ecc > USHORT_MAX);
 339
 340         bc->bc_crc32e = cpu_to_le32(crc);
 341         bc->bc_ecc = cpu_to_le16((u16)ecc);
 342 }
 343
 344 /*
 345  * This function validates existing check information on a list of
 346  * buffer_heads.  Like _compute_bhs, the function will take care of
 347  * zeroing bc before calculating check codes.  If bc is not a pointer
 348  * inside data, the caller must have zeroed any inline
 349  * ocfs2_block_check structures.
 350  *
 351  * Again, the data passed in should be the on-disk endian.
 352  */
 353 int ocfs2_block_check_validate_bhs(struct buffer_head **bhs, int nr,
 354                                    struct ocfs2_block_check *bc)
 355 {
 356         int i, rc = 0;
 357         struct ocfs2_block_check check;
 358         u32 crc, ecc, fix;
 359
 360         BUG_ON(nr < 0);
 361
 362         if (!nr)
 363                 return 0;
 364
 365         check.bc_crc32e = le32_to_cpu(bc->bc_crc32e);
 366         check.bc_ecc = le16_to_cpu(bc->bc_ecc);
 367
 368         memset(bc, 0, sizeof(struct ocfs2_block_check));
 369
 370         /* Fast path - if the crc32 validates, we're good to go */
 371         for (i = 0, crc = ~0; i < nr; i++)
 372                 crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size);
 373         if (crc == check.bc_crc32e)
 374                 goto out;
 375
 376         mlog(ML_ERROR,
 377              "CRC32 failed: stored: %u, computed %u.  Applying ECC.\n",
 378              (unsigned int)check.bc_crc32e, (unsigned int)crc);
 379
 380         /* Ok, try ECC fixups */
 381         for (i = 0, ecc = 0; i < nr; i++) {
 382                 /*
 383                  * The number of bits in a buffer is obviously b_size*8.
 384                  * The offset of this buffer is b_size*i, so the bit offset
 385                  * of this buffer is b_size*8*i.
 386                  */
 387                 ecc = (u16)ocfs2_hamming_encode(ecc, bhs[i]->b_data,
 388                                                 bhs[i]->b_size * 8,
 389                                                 bhs[i]->b_size * 8 * i);
 390         }
 391         fix = ecc ^ check.bc_ecc;
 392         for (i = 0; i < nr; i++) {
 393                 /*
 394                  * Try the fix against each buffer.  It will only affect
 395                  * one of them.
 396                  */
 397                 ocfs2_hamming_fix(bhs[i]->b_data, bhs[i]->b_size * 8,
 398                                   bhs[i]->b_size * 8 * i, fix);
 399         }
 400
 401         /* And check the crc32 again */
 402         for (i = 0, crc = ~0; i < nr; i++)
 403                 crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size);
 404         if (crc == check.bc_crc32e)
 405                 goto out;
 406
 407         mlog(ML_ERROR, "Fixed CRC32 failed: stored: %u, computed %u\n",
 408              (unsigned int)check.bc_crc32e, (unsigned int)crc);
 409
 410         rc = -EIO;
 411
 412 out:
 413         bc->bc_crc32e = cpu_to_le32(check.bc_crc32e);
 414         bc->bc_ecc = cpu_to_le16(check.bc_ecc);
 415
 416         return rc;
 417 }
 418
 419 /*
 420  * These are the main API.  They check the superblock flag before
 421  * calling the underlying operations.
 422  *
 423  * They expect the buffer(s) to be in disk format.
 424  */
 425 void ocfs2_compute_meta_ecc(struct super_block *sb, void *data,
 426                             struct ocfs2_block_check *bc)
 427 {
 428         if (ocfs2_meta_ecc(OCFS2_SB(sb)))
 429                 ocfs2_block_check_compute(data, sb->s_blocksize, bc);
 430 }
 431
 432 int ocfs2_validate_meta_ecc(struct super_block *sb, void *data,
 433                             struct ocfs2_block_check *bc)
 434 {
 435         int rc = 0;
 436
 437         if (ocfs2_meta_ecc(OCFS2_SB(sb)))
 438                 rc = ocfs2_block_check_validate(data, sb->s_blocksize, bc);
 439
 440         return rc;
 441 }
 442
 443 void ocfs2_compute_meta_ecc_bhs(struct super_block *sb,
 444                                 struct buffer_head **bhs, int nr,
 445                                 struct ocfs2_block_check *bc)
 446 {
 447         if (ocfs2_meta_ecc(OCFS2_SB(sb)))
 448                 ocfs2_block_check_compute_bhs(bhs, nr, bc);
 449 }
 450
 451 int ocfs2_validate_meta_ecc_bhs(struct super_block *sb,
 452                                 struct buffer_head **bhs, int nr,
 453                                 struct ocfs2_block_check *bc)
 454 {
 455         int rc = 0;
 456
 457         if (ocfs2_meta_ecc(OCFS2_SB(sb)))
 458                 rc = ocfs2_block_check_validate_bhs(bhs, nr, bc);
 459
 460         return rc;
 461 }
 462