From 70ad1ba7b48364d758a112df0823edc5ca6632aa Mon Sep 17 00:00:00 2001 From: Joel Becker Date: Thu, 16 Oct 2008 17:54:25 -0700 Subject: ocfs2: Add the underlying blockcheck code. This is the code that computes crc32 and ecc for ocfs2 metadata blocks. There are high-level functions that check whether the filesystem has the ecc feature, mid-level functions that work on a single block or array of buffer_heads, and the low-level ecc hamming code that can handle multiple buffers like crc32_le(). It's not hooked up to the filesystem yet. Signed-off-by: Joel Becker Cc: Christoph Hellwig Signed-off-by: Mark Fasheh --- fs/ocfs2/blockcheck.c | 480 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 480 insertions(+) create mode 100644 fs/ocfs2/blockcheck.c (limited to 'fs/ocfs2/blockcheck.c') diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c new file mode 100644 index 000000000000..2bf3d7f61aec --- /dev/null +++ b/fs/ocfs2/blockcheck.c @@ -0,0 +1,480 @@ +/* -*- mode: c; c-basic-offset: 8; -*- + * vim: noexpandtab sw=8 ts=8 sts=0: + * + * blockcheck.c + * + * Checksum and ECC codes for the OCFS2 userspace library. + * + * Copyright (C) 2006, 2008 Oracle. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License, version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include +#include +#include +#include +#include +#include + +#include "ocfs2.h" + +#include "blockcheck.h" + + + +/* + * We use the following conventions: + * + * d = # data bits + * p = # parity bits + * c = # total code bits (d + p) + */ +static int calc_parity_bits(unsigned int d) +{ + unsigned int p; + + /* + * Bits required for Single Error Correction is as follows: + * + * d + p + 1 <= 2^p + * + * We're restricting ourselves to 31 bits of parity, that should be + * sufficient. + */ + for (p = 1; p < 32; p++) + { + if ((d + p + 1) <= (1 << p)) + return p; + } + + return 0; +} + +/* + * Calculate the bit offset in the hamming code buffer based on the bit's + * offset in the data buffer. Since the hamming code reserves all + * power-of-two bits for parity, the data bit number and the code bit + * number are offest by all the parity bits beforehand. + * + * Recall that bit numbers in hamming code are 1-based. This function + * takes the 0-based data bit from the caller. + * + * An example. Take bit 1 of the data buffer. 1 is a power of two (2^0), + * so it's a parity bit. 2 is a power of two (2^1), so it's a parity bit. + * 3 is not a power of two. So bit 1 of the data buffer ends up as bit 3 + * in the code buffer. + */ +static unsigned int calc_code_bit(unsigned int i) +{ + unsigned int b, p; + + /* + * Data bits are 0-based, but we're talking code bits, which + * are 1-based. + */ + b = i + 1; + + /* + * For every power of two below our bit number, bump our bit. + * + * We compare with (b + 1) becuase we have to compare with what b + * would be _if_ it were bumped up by the parity bit. Capice? + */ + for (p = 0; (1 << p) < (b + 1); p++) + b++; + + return b; +} + +/* + * This is the low level encoder function. It can be called across + * multiple hunks just like the crc32 code. 'd' is the number of bits + * _in_this_hunk_. nr is the bit offset of this hunk. So, if you had + * two 512B buffers, you would do it like so: + * + * parity = ocfs2_hamming_encode(0, buf1, 512 * 8, 0); + * parity = ocfs2_hamming_encode(parity, buf2, 512 * 8, 512 * 8); + * + * If you just have one buffer, use ocfs2_hamming_encode_block(). + */ +u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr) +{ + unsigned int p = calc_parity_bits(nr + d); + unsigned int i, j, b; + + BUG_ON(!p); + + /* + * b is the hamming code bit number. Hamming code specifies a + * 1-based array, but C uses 0-based. So 'i' is for C, and 'b' is + * for the algorithm. + * + * The i++ in the for loop is so that the start offset passed + * to ocfs2_find_next_bit_set() is one greater than the previously + * found bit. + */ + for (i = 0; (i = ocfs2_find_next_bit(data, d, i)) < d; i++) + { + /* + * i is the offset in this hunk, nr + i is the total bit + * offset. + */ + b = calc_code_bit(nr + i); + + for (j = 0; j < p; j++) + { + /* + * Data bits in the resultant code are checked by + * parity bits that are part of the bit number + * representation. Huh? + * + * + * In other words, the parity bit at position 2^k + * checks bits in positions having bit k set in + * their binary representation. Conversely, for + * instance, bit 13, i.e. 1101(2), is checked by + * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1. + * + * + * Note that 'k' is the _code_ bit number. 'b' in + * our loop. + */ + if (b & (1 << j)) + parity ^= (1 << j); + } + } + + /* While the data buffer was treated as little endian, the + * return value is in host endian. */ + return parity; +} + +u32 ocfs2_hamming_encode_block(void *data, unsigned int blocksize) +{ + return ocfs2_hamming_encode(0, data, blocksize * 8, 0); +} + +/* + * Like ocfs2_hamming_encode(), this can handle hunks. nr is the bit + * offset of the current hunk. If bit to be fixed is not part of the + * current hunk, this does nothing. + * + * If you only have one hunk, use ocfs2_hamming_fix_block(). + */ +void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr, + unsigned int fix) +{ + unsigned int p = calc_parity_bits(nr + d); + unsigned int i, b; + + BUG_ON(!p); + + /* + * If the bit to fix has an hweight of 1, it's a parity bit. One + * busted parity bit is its own error. Nothing to do here. + */ + if (hweight32(fix) == 1) + return; + + /* + * nr + d is the bit right past the data hunk we're looking at. + * If fix after that, nothing to do + */ + if (fix >= calc_code_bit(nr + d)) + return; + + /* + * nr is the offset in the data hunk we're starting at. Let's + * start b at the offset in the code buffer. See hamming_encode() + * for a more detailed description of 'b'. + */ + b = calc_code_bit(nr); + /* If the fix is before this hunk, nothing to do */ + if (fix < b) + return; + + for (i = 0; i < d; i++, b++) + { + /* Skip past parity bits */ + while (hweight32(b) == 1) + b++; + + /* + * i is the offset in this data hunk. + * nr + i is the offset in the total data buffer. + * b is the offset in the total code buffer. + * + * Thus, when b == fix, bit i in the current hunk needs + * fixing. + */ + if (b == fix) + { + if (ocfs2_test_bit(i, data)) + ocfs2_clear_bit(i, data); + else + ocfs2_set_bit(i, data); + break; + } + } +} + +void ocfs2_hamming_fix_block(void *data, unsigned int blocksize, + unsigned int fix) +{ + ocfs2_hamming_fix(data, blocksize * 8, 0, fix); +} + +/* + * This function generates check information for a block. + * data is the block to be checked. bc is a pointer to the + * ocfs2_block_check structure describing the crc32 and the ecc. + * + * bc should be a pointer inside data, as the function will + * take care of zeroing it before calculating the check information. If + * bc does not point inside data, the caller must make sure any inline + * ocfs2_block_check structures are zeroed. + * + * The data buffer must be in on-disk endian (little endian for ocfs2). + * bc will be filled with little-endian values and will be ready to go to + * disk. + */ +void ocfs2_block_check_compute(void *data, size_t blocksize, + struct ocfs2_block_check *bc) +{ + u32 crc; + u32 ecc; + + memset(bc, 0, sizeof(struct ocfs2_block_check)); + + crc = crc32_le(~0, data, blocksize); + ecc = ocfs2_hamming_encode_block(data, blocksize); + + /* + * No ecc'd ocfs2 structure is larger than 4K, so ecc will be no + * larger than 16 bits. + */ + BUG_ON(ecc > USHORT_MAX); + + bc->bc_crc32e = cpu_to_le32(crc); + bc->bc_ecc = cpu_to_le16((u16)ecc); +} + +/* + * This function validates existing check information. Like _compute, + * the function will take care of zeroing bc before calculating check codes. + * If bc is not a pointer inside data, the caller must have zeroed any + * inline ocfs2_block_check structures. + * + * Again, the data passed in should be the on-disk endian. + */ +int ocfs2_block_check_validate(void *data, size_t blocksize, + struct ocfs2_block_check *bc) +{ + int rc = 0; + struct ocfs2_block_check check; + u32 crc, ecc; + + check.bc_crc32e = le32_to_cpu(bc->bc_crc32e); + check.bc_ecc = le16_to_cpu(bc->bc_ecc); + + memset(bc, 0, sizeof(struct ocfs2_block_check)); + + /* Fast path - if the crc32 validates, we're good to go */ + crc = crc32_le(~0, data, blocksize); + if (crc == check.bc_crc32e) + goto out; + + /* Ok, try ECC fixups */ + ecc = ocfs2_hamming_encode_block(data, blocksize); + ocfs2_hamming_fix_block(data, blocksize, ecc ^ check.bc_ecc); + + /* And check the crc32 again */ + crc = crc32_le(~0, data, blocksize); + if (crc == check.bc_crc32e) + goto out; + + rc = -EIO; + +out: + bc->bc_crc32e = cpu_to_le32(check.bc_crc32e); + bc->bc_ecc = cpu_to_le16(check.bc_ecc); + + return rc; +} + +/* + * This function generates check information for a list of buffer_heads. + * bhs is the blocks to be checked. bc is a pointer to the + * ocfs2_block_check structure describing the crc32 and the ecc. + * + * bc should be a pointer inside data, as the function will + * take care of zeroing it before calculating the check information. If + * bc does not point inside data, the caller must make sure any inline + * ocfs2_block_check structures are zeroed. + * + * The data buffer must be in on-disk endian (little endian for ocfs2). + * bc will be filled with little-endian values and will be ready to go to + * disk. + */ +void ocfs2_block_check_compute_bhs(struct buffer_head **bhs, int nr, + struct ocfs2_block_check *bc) +{ + int i; + u32 crc, ecc; + + BUG_ON(nr < 0); + + if (!nr) + return; + + memset(bc, 0, sizeof(struct ocfs2_block_check)); + + for (i = 0, crc = ~0, ecc = 0; i < nr; i++) { + crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size); + /* + * The number of bits in a buffer is obviously b_size*8. + * The offset of this buffer is b_size*i, so the bit offset + * of this buffer is b_size*8*i. + */ + ecc = (u16)ocfs2_hamming_encode(ecc, bhs[i]->b_data, + bhs[i]->b_size * 8, + bhs[i]->b_size * 8 * i); + } + + /* + * No ecc'd ocfs2 structure is larger than 4K, so ecc will be no + * larger than 16 bits. + */ + BUG_ON(ecc > USHORT_MAX); + + bc->bc_crc32e = cpu_to_le32(crc); + bc->bc_ecc = cpu_to_le16((u16)ecc); +} + +/* + * This function validates existing check information on a list of + * buffer_heads. Like _compute_bhs, the function will take care of + * zeroing bc before calculating check codes. If bc is not a pointer + * inside data, the caller must have zeroed any inline + * ocfs2_block_check structures. + * + * Again, the data passed in should be the on-disk endian. + */ +int ocfs2_block_check_validate_bhs(struct buffer_head **bhs, int nr, + struct ocfs2_block_check *bc) +{ + int i, rc = 0; + struct ocfs2_block_check check; + u32 crc, ecc, fix; + + BUG_ON(nr < 0); + + if (!nr) + return 0; + + check.bc_crc32e = le32_to_cpu(bc->bc_crc32e); + check.bc_ecc = le16_to_cpu(bc->bc_ecc); + + memset(bc, 0, sizeof(struct ocfs2_block_check)); + + /* Fast path - if the crc32 validates, we're good to go */ + for (i = 0, crc = ~0; i < nr; i++) + crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size); + if (crc == check.bc_crc32e) + goto out; + + mlog(ML_ERROR, + "CRC32 failed: stored: %u, computed %u. Applying ECC.\n", + (unsigned int)check.bc_crc32e, (unsigned int)crc); + + /* Ok, try ECC fixups */ + for (i = 0, ecc = 0; i < nr; i++) { + /* + * The number of bits in a buffer is obviously b_size*8. + * The offset of this buffer is b_size*i, so the bit offset + * of this buffer is b_size*8*i. + */ + ecc = (u16)ocfs2_hamming_encode(ecc, bhs[i]->b_data, + bhs[i]->b_size * 8, + bhs[i]->b_size * 8 * i); + } + fix = ecc ^ check.bc_ecc; + for (i = 0; i < nr; i++) { + /* + * Try the fix against each buffer. It will only affect + * one of them. + */ + ocfs2_hamming_fix(bhs[i]->b_data, bhs[i]->b_size * 8, + bhs[i]->b_size * 8 * i, fix); + } + + /* And check the crc32 again */ + for (i = 0, crc = ~0; i < nr; i++) + crc = crc32_le(crc, bhs[i]->b_data, bhs[i]->b_size); + if (crc == check.bc_crc32e) + goto out; + + mlog(ML_ERROR, "Fixed CRC32 failed: stored: %u, computed %u\n", + (unsigned int)check.bc_crc32e, (unsigned int)crc); + + rc = -EIO; + +out: + bc->bc_crc32e = cpu_to_le32(check.bc_crc32e); + bc->bc_ecc = cpu_to_le16(check.bc_ecc); + + return rc; +} + +/* + * These are the main API. They check the superblock flag before + * calling the underlying operations. + * + * They expect the buffer(s) to be in disk format. + */ +void ocfs2_compute_meta_ecc(struct super_block *sb, void *data, + struct ocfs2_block_check *bc) +{ + if (ocfs2_meta_ecc(OCFS2_SB(sb))) + ocfs2_block_check_compute(data, sb->s_blocksize, bc); +} + +int ocfs2_validate_meta_ecc(struct super_block *sb, void *data, + struct ocfs2_block_check *bc) +{ + int rc = 0; + + if (ocfs2_meta_ecc(OCFS2_SB(sb))) + rc = ocfs2_block_check_validate(data, sb->s_blocksize, bc); + + return rc; +} + +void ocfs2_compute_meta_ecc_bhs(struct super_block *sb, + struct buffer_head **bhs, int nr, + struct ocfs2_block_check *bc) +{ + if (ocfs2_meta_ecc(OCFS2_SB(sb))) + ocfs2_block_check_compute_bhs(bhs, nr, bc); +} + +int ocfs2_validate_meta_ecc_bhs(struct super_block *sb, + struct buffer_head **bhs, int nr, + struct ocfs2_block_check *bc) +{ + int rc = 0; + + if (ocfs2_meta_ecc(OCFS2_SB(sb))) + rc = ocfs2_block_check_validate_bhs(bhs, nr, bc); + + return rc; +} + -- cgit v1.2.3 From d6b32bbb3eae3fb787f1c33bf9f767ca1ddeb208 Mon Sep 17 00:00:00 2001 From: Joel Becker Date: Fri, 17 Oct 2008 14:55:01 -0700 Subject: ocfs2: block read meta ecc. Add block check calls to the read_block validate functions. This is the almost all of the read-side checking of metaecc. xattr buckets are not checked yet. Writes are also unchecked, and so a read-write mount will quickly fail. Signed-off-by: Joel Becker Signed-off-by: Mark Fasheh --- fs/ocfs2/alloc.c | 17 +++++++++++++++++ fs/ocfs2/blockcheck.c | 9 +++++++++ fs/ocfs2/inode.c | 18 +++++++++++++++++- fs/ocfs2/quota_global.c | 13 +++++++++++-- fs/ocfs2/suballoc.c | 31 ++++++++++++++++++++++++++++++- fs/ocfs2/xattr.c | 17 +++++++++++++++++ 6 files changed, 101 insertions(+), 4 deletions(-) (limited to 'fs/ocfs2/blockcheck.c') diff --git a/fs/ocfs2/alloc.c b/fs/ocfs2/alloc.c index 84a7bd4db5da..6b27f74bb346 100644 --- a/fs/ocfs2/alloc.c +++ b/fs/ocfs2/alloc.c @@ -37,6 +37,7 @@ #include "alloc.h" #include "aops.h" +#include "blockcheck.h" #include "dlmglue.h" #include "extent_map.h" #include "inode.h" @@ -682,12 +683,28 @@ struct ocfs2_merge_ctxt { static int ocfs2_validate_extent_block(struct super_block *sb, struct buffer_head *bh) { + int rc; struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)bh->b_data; mlog(0, "Validating extent block %llu\n", (unsigned long long)bh->b_blocknr); + BUG_ON(!buffer_uptodate(bh)); + + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &eb->h_check); + if (rc) + return rc; + + /* + * Errors after here are fatal. + */ + if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { ocfs2_error(sb, "Extent block #%llu has bad signature %.*s", diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c index 2bf3d7f61aec..2ce6ae5e4b8c 100644 --- a/fs/ocfs2/blockcheck.c +++ b/fs/ocfs2/blockcheck.c @@ -24,6 +24,8 @@ #include #include +#include + #include "ocfs2.h" #include "blockcheck.h" @@ -292,6 +294,10 @@ int ocfs2_block_check_validate(void *data, size_t blocksize, if (crc == check.bc_crc32e) goto out; + mlog(ML_ERROR, + "CRC32 failed: stored: %u, computed %u. Applying ECC.\n", + (unsigned int)check.bc_crc32e, (unsigned int)crc); + /* Ok, try ECC fixups */ ecc = ocfs2_hamming_encode_block(data, blocksize); ocfs2_hamming_fix_block(data, blocksize, ecc ^ check.bc_ecc); @@ -301,6 +307,9 @@ int ocfs2_block_check_validate(void *data, size_t blocksize, if (crc == check.bc_crc32e) goto out; + mlog(ML_ERROR, "Fixed CRC32 failed: stored: %u, computed %u\n", + (unsigned int)check.bc_crc32e, (unsigned int)crc); + rc = -EIO; out: diff --git a/fs/ocfs2/inode.c b/fs/ocfs2/inode.c index 288512c9dbc2..9370b652ab94 100644 --- a/fs/ocfs2/inode.c +++ b/fs/ocfs2/inode.c @@ -38,6 +38,7 @@ #include "ocfs2.h" #include "alloc.h" +#include "blockcheck.h" #include "dlmglue.h" #include "extent_map.h" #include "file.h" @@ -1262,7 +1263,7 @@ void ocfs2_refresh_inode(struct inode *inode, int ocfs2_validate_inode_block(struct super_block *sb, struct buffer_head *bh) { - int rc = -EINVAL; + int rc; struct ocfs2_dinode *di = (struct ocfs2_dinode *)bh->b_data; mlog(0, "Validating dinode %llu\n", @@ -1270,6 +1271,21 @@ int ocfs2_validate_inode_block(struct super_block *sb, BUG_ON(!buffer_uptodate(bh)); + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &di->i_check); + if (rc) + goto bail; + + /* + * Errors after here are fatal. + */ + + rc = -EINVAL; + if (!OCFS2_IS_VALID_DINODE(di)) { ocfs2_error(sb, "Invalid dinode #%llu: signature = %.*s\n", (unsigned long long)bh->b_blocknr, 7, diff --git a/fs/ocfs2/quota_global.c b/fs/ocfs2/quota_global.c index 7dbcfd7f65e6..a0b8b14cca8f 100644 --- a/fs/ocfs2/quota_global.c +++ b/fs/ocfs2/quota_global.c @@ -16,6 +16,7 @@ #include "ocfs2_fs.h" #include "ocfs2.h" #include "alloc.h" +#include "blockcheck.h" #include "inode.h" #include "journal.h" #include "file.h" @@ -90,12 +91,20 @@ struct qtree_fmt_operations ocfs2_global_ops = { static int ocfs2_validate_quota_block(struct super_block *sb, struct buffer_head *bh) { - struct ocfs2_disk_dqtrailer *dqt = ocfs2_dq_trailer(sb, bh->b_data); + struct ocfs2_disk_dqtrailer *dqt = + ocfs2_block_dqtrailer(sb->s_blocksize, bh->b_data); mlog(0, "Validating quota block %llu\n", (unsigned long long)bh->b_blocknr); - return 0; + BUG_ON(!buffer_uptodate(bh)); + + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + return ocfs2_validate_meta_ecc(sb, bh->b_data, &dqt->dq_check); } int ocfs2_read_quota_block(struct inode *inode, u64 v_block, diff --git a/fs/ocfs2/suballoc.c b/fs/ocfs2/suballoc.c index 226fe21f2608..78755766c329 100644 --- a/fs/ocfs2/suballoc.c +++ b/fs/ocfs2/suballoc.c @@ -35,6 +35,7 @@ #include "ocfs2.h" #include "alloc.h" +#include "blockcheck.h" #include "dlmglue.h" #include "inode.h" #include "journal.h" @@ -250,8 +251,18 @@ int ocfs2_check_group_descriptor(struct super_block *sb, struct buffer_head *bh) { int rc; + struct ocfs2_group_desc *gd = (struct ocfs2_group_desc *)bh->b_data; + + BUG_ON(!buffer_uptodate(bh)); - rc = ocfs2_validate_gd_self(sb, bh, 1); + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &gd->bg_check); + if (!rc) + rc = ocfs2_validate_gd_self(sb, bh, 1); if (!rc) rc = ocfs2_validate_gd_parent(sb, di, bh, 1); @@ -261,9 +272,27 @@ int ocfs2_check_group_descriptor(struct super_block *sb, static int ocfs2_validate_group_descriptor(struct super_block *sb, struct buffer_head *bh) { + int rc; + struct ocfs2_group_desc *gd = (struct ocfs2_group_desc *)bh->b_data; + mlog(0, "Validating group descriptor %llu\n", (unsigned long long)bh->b_blocknr); + BUG_ON(!buffer_uptodate(bh)); + + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &gd->bg_check); + if (rc) + return rc; + + /* + * Errors after here are fatal. + */ + return ocfs2_validate_gd_self(sb, bh, 0); } diff --git a/fs/ocfs2/xattr.c b/fs/ocfs2/xattr.c index dfc51c305bb9..bc822d6ba542 100644 --- a/fs/ocfs2/xattr.c +++ b/fs/ocfs2/xattr.c @@ -42,6 +42,7 @@ #include "ocfs2.h" #include "alloc.h" +#include "blockcheck.h" #include "dlmglue.h" #include "file.h" #include "symlink.h" @@ -322,12 +323,28 @@ static void ocfs2_xattr_bucket_copy_data(struct ocfs2_xattr_bucket *dest, static int ocfs2_validate_xattr_block(struct super_block *sb, struct buffer_head *bh) { + int rc; struct ocfs2_xattr_block *xb = (struct ocfs2_xattr_block *)bh->b_data; mlog(0, "Validating xattr block %llu\n", (unsigned long long)bh->b_blocknr); + BUG_ON(!buffer_uptodate(bh)); + + /* + * If the ecc fails, we return the error but otherwise + * leave the filesystem running. We know any error is + * local to this block. + */ + rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &xb->xb_check); + if (rc) + return rc; + + /* + * Errors after here are fatal + */ + if (!OCFS2_IS_VALID_XATTR_BLOCK(xb)) { ocfs2_error(sb, "Extended attribute block #%llu has bad " -- cgit v1.2.3 From e798b3f8a920c82a8e556dd54df97f0d3d0f9144 Mon Sep 17 00:00:00 2001 From: Joel Becker Date: Mon, 15 Dec 2008 17:13:48 -0800 Subject: ocfs2: Don't hand-code xor in ocfs2_hamming_encode(). When I wrote ocfs2_hamming_encode(), I was following documentation of the algorithm and didn't have quite the (possibly still imperfect) grasp of it I do now. As part of this, I literally hand-coded xor. I would test a bit, and then add that bit via xor to the parity word. I can, of course, just do a single xor of the parity word and the source word (the code buffer bit offset). This cuts CPU usage by 53% on a mostly populated buffer (an inode containing utmp.h inline). Joel Signed-off-by: Joel Becker Signed-off-by: Mark Fasheh --- fs/ocfs2/blockcheck.c | 67 +++++++++++++++------------------------------------ 1 file changed, 20 insertions(+), 47 deletions(-) (limited to 'fs/ocfs2/blockcheck.c') diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c index 2ce6ae5e4b8c..1d5083cef3a2 100644 --- a/fs/ocfs2/blockcheck.c +++ b/fs/ocfs2/blockcheck.c @@ -31,7 +31,6 @@ #include "blockcheck.h" - /* * We use the following conventions: * @@ -39,26 +38,6 @@ * p = # parity bits * c = # total code bits (d + p) */ -static int calc_parity_bits(unsigned int d) -{ - unsigned int p; - - /* - * Bits required for Single Error Correction is as follows: - * - * d + p + 1 <= 2^p - * - * We're restricting ourselves to 31 bits of parity, that should be - * sufficient. - */ - for (p = 1; p < 32; p++) - { - if ((d + p + 1) <= (1 << p)) - return p; - } - - return 0; -} /* * Calculate the bit offset in the hamming code buffer based on the bit's @@ -109,10 +88,9 @@ static unsigned int calc_code_bit(unsigned int i) */ u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr) { - unsigned int p = calc_parity_bits(nr + d); - unsigned int i, j, b; + unsigned int i, b; - BUG_ON(!p); + BUG_ON(!d); /* * b is the hamming code bit number. Hamming code specifies a @@ -131,27 +109,23 @@ u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr */ b = calc_code_bit(nr + i); - for (j = 0; j < p; j++) - { - /* - * Data bits in the resultant code are checked by - * parity bits that are part of the bit number - * representation. Huh? - * - * - * In other words, the parity bit at position 2^k - * checks bits in positions having bit k set in - * their binary representation. Conversely, for - * instance, bit 13, i.e. 1101(2), is checked by - * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1. - * - * - * Note that 'k' is the _code_ bit number. 'b' in - * our loop. - */ - if (b & (1 << j)) - parity ^= (1 << j); - } + /* + * Data bits in the resultant code are checked by + * parity bits that are part of the bit number + * representation. Huh? + * + * + * In other words, the parity bit at position 2^k + * checks bits in positions having bit k set in + * their binary representation. Conversely, for + * instance, bit 13, i.e. 1101(2), is checked by + * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1. + * + * + * Note that 'k' is the _code_ bit number. 'b' in + * our loop. + */ + parity ^= b; } /* While the data buffer was treated as little endian, the @@ -174,10 +148,9 @@ u32 ocfs2_hamming_encode_block(void *data, unsigned int blocksize) void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr, unsigned int fix) { - unsigned int p = calc_parity_bits(nr + d); unsigned int i, b; - BUG_ON(!p); + BUG_ON(!d); /* * If the bit to fix has an hweight of 1, it's a parity bit. One -- cgit v1.2.3 From 7bb458a58588f397068e4166c615e9fcc7480c16 Mon Sep 17 00:00:00 2001 From: Joel Becker Date: Mon, 15 Dec 2008 18:24:33 -0800 Subject: ocfs2: Another hamming code optimization. In the calc_code_bit() function, we must find all powers of two beneath the code bit number, *after* it's shifted by those powers of two. This requires a loop to see where it ends up. We can optimize it by starting at its most significant bit. This shaves 32% off the time, for a total of 67.6% shaved off of the original, naive implementation. Signed-off-by: Joel Becker Signed-off-by: Mark Fasheh --- fs/ocfs2/blockcheck.c | 40 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) (limited to 'fs/ocfs2/blockcheck.c') diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c index 1d5083cef3a2..f102ec939c90 100644 --- a/fs/ocfs2/blockcheck.c +++ b/fs/ocfs2/blockcheck.c @@ -39,6 +39,35 @@ * c = # total code bits (d + p) */ + +/* + * Find the log base 2 of 32-bit v. + * + * Algorithm found on http://graphics.stanford.edu/~seander/bithacks.html, + * by Sean Eron Anderson. Code on the page is in the public domain unless + * otherwise noted. + * + * This particular algorithm is credited to Eric Cole. + */ +static int find_highest_bit_set(unsigned int v) +{ + + static const int MultiplyDeBruijnBitPosition[32] = + { + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 + }; + + v |= v >> 1; /* first round down to power of 2 */ + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v = (v >> 1) + 1; + + return MultiplyDeBruijnBitPosition[(u32)(v * 0x077CB531UL) >> 27]; +} + /* * Calculate the bit offset in the hamming code buffer based on the bit's * offset in the data buffer. Since the hamming code reserves all @@ -63,13 +92,22 @@ static unsigned int calc_code_bit(unsigned int i) */ b = i + 1; + /* + * As a cheat, we know that all bits below b's highest bit must be + * parity bits, so we can start there. + */ + p = find_highest_bit_set(b); + b += p; + /* * For every power of two below our bit number, bump our bit. * * We compare with (b + 1) becuase we have to compare with what b * would be _if_ it were bumped up by the parity bit. Capice? + * + * We start p at 2^p because of the cheat above. */ - for (p = 0; (1 << p) < (b + 1); p++) + for (p = (1 << p); p < (b + 1); p <<= 1) b++; return b; -- cgit v1.2.3 From 58896c4d0e5868360ea0693c607d5bf74f79da6b Mon Sep 17 00:00:00 2001 From: Joel Becker Date: Tue, 16 Dec 2008 13:54:40 -0800 Subject: ocfs2: One more hamming code optimization. The previous optimization used a fast find-highest-bit-set operation to give us a good starting point in calc_code_bit(). This version lets the caller cache the previous code buffer bit offset. Thus, the next call always starts where the last one left off. This reduces the calculation another 39%, for a total 80% reduction from the original, naive implementation. At least, on my machine. This also brings the parity calculation to within an order of magnitude of the crc32 calculation. Signed-off-by: Joel Becker Signed-off-by: Mark Fasheh --- fs/ocfs2/blockcheck.c | 61 ++++++++++++++++----------------------------------- 1 file changed, 19 insertions(+), 42 deletions(-) (limited to 'fs/ocfs2/blockcheck.c') diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c index f102ec939c90..2a947c44e594 100644 --- a/fs/ocfs2/blockcheck.c +++ b/fs/ocfs2/blockcheck.c @@ -40,34 +40,6 @@ */ -/* - * Find the log base 2 of 32-bit v. - * - * Algorithm found on http://graphics.stanford.edu/~seander/bithacks.html, - * by Sean Eron Anderson. Code on the page is in the public domain unless - * otherwise noted. - * - * This particular algorithm is credited to Eric Cole. - */ -static int find_highest_bit_set(unsigned int v) -{ - - static const int MultiplyDeBruijnBitPosition[32] = - { - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 - }; - - v |= v >> 1; /* first round down to power of 2 */ - v |= v >> 2; - v |= v >> 4; - v |= v >> 8; - v |= v >> 16; - v = (v >> 1) + 1; - - return MultiplyDeBruijnBitPosition[(u32)(v * 0x077CB531UL) >> 27]; -} - /* * Calculate the bit offset in the hamming code buffer based on the bit's * offset in the data buffer. Since the hamming code reserves all @@ -81,10 +53,14 @@ static int find_highest_bit_set(unsigned int v) * so it's a parity bit. 2 is a power of two (2^1), so it's a parity bit. * 3 is not a power of two. So bit 1 of the data buffer ends up as bit 3 * in the code buffer. + * + * The caller can pass in *p if it wants to keep track of the most recent + * number of parity bits added. This allows the function to start the + * calculation at the last place. */ -static unsigned int calc_code_bit(unsigned int i) +static unsigned int calc_code_bit(unsigned int i, unsigned int *p_cache) { - unsigned int b, p; + unsigned int b, p = 0; /* * Data bits are 0-based, but we're talking code bits, which @@ -92,24 +68,25 @@ static unsigned int calc_code_bit(unsigned int i) */ b = i + 1; - /* - * As a cheat, we know that all bits below b's highest bit must be - * parity bits, so we can start there. - */ - p = find_highest_bit_set(b); + /* Use the cache if it is there */ + if (p_cache) + p = *p_cache; b += p; /* * For every power of two below our bit number, bump our bit. * - * We compare with (b + 1) becuase we have to compare with what b + * We compare with (b + 1) because we have to compare with what b * would be _if_ it were bumped up by the parity bit. Capice? * - * We start p at 2^p because of the cheat above. + * p is set above. */ - for (p = (1 << p); p < (b + 1); p <<= 1) + for (; (1 << p) < (b + 1); p++) b++; + if (p_cache) + *p_cache = p; + return b; } @@ -126,7 +103,7 @@ static unsigned int calc_code_bit(unsigned int i) */ u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr) { - unsigned int i, b; + unsigned int i, b, p = 0; BUG_ON(!d); @@ -145,7 +122,7 @@ u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr * i is the offset in this hunk, nr + i is the total bit * offset. */ - b = calc_code_bit(nr + i); + b = calc_code_bit(nr + i, &p); /* * Data bits in the resultant code are checked by @@ -201,7 +178,7 @@ void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr, * nr + d is the bit right past the data hunk we're looking at. * If fix after that, nothing to do */ - if (fix >= calc_code_bit(nr + d)) + if (fix >= calc_code_bit(nr + d, NULL)) return; /* @@ -209,7 +186,7 @@ void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr, * start b at the offset in the code buffer. See hamming_encode() * for a more detailed description of 'b'. */ - b = calc_code_bit(nr); + b = calc_code_bit(nr, NULL); /* If the fix is before this hunk, nothing to do */ if (fix < b) return; -- cgit v1.2.3