New RAID library supporting up to six parities
Subsystems (6)
v3 cover New RAID library supporting up to six parities
Hi,
Here another version of the new RAID library that addresses the Neil's comments. The new thing is an example patch to async_tx to support more parities and to use the new lib.
The RAID library itself is mostly unchanged besides some renaming, removing the controversial raid_sort() function, and more documentation. I don't have plan for further changes, and I think that it's now a good candidate for review and possible inclusion.
If some patch is missing due mailinglist size limit, you can download them at:
http://snapraid.sourceforge.net/linux/v3/
Changes from v2 to v3:
- Adds a new patch to change async_tx to use the new raid library for syncronous cases and to export a similar interface. Also modified md/raid5.c to use the new interface of async_tx. This is just example code not meant for inclusion!
- Renamed raid_par() to raid_gen() to match better existing naming.
- Removed raid_sort() and replaced with raid_insert() that allows to build a vector already in order instead of sorting it later. This function is declared in the new raid/helper.h.
- Better documentation in the raid.h/c files. Start from raid.h to see the documentation of the new interface.
Changes from v1 to v2:
- Adds a patch to btrfs to extend its support to more than double parity. This is just example code not meant for inclusion!
- Changes the main raid_rec() interface to merge the failed data and parity index vectors. This matches better the kernel usage.
- Uses alloc_pages_exact() instead of __get_free_pages().
- Removes unnecessary register loads from par1_sse().
- Converts the asm_begin/end() macros to inlined functions.
- Fixes some more checkpatch.pl warnings.
- Other minor style/comment changes.
---
This is a port to the Linux kernel of a RAID engine that I'm currently using in a hobby project called SnapRAID. This engine supports up to six parities levels and at the same time maintains compatibility with the existing Linux RAID6 one.
The mathematical method used was already discussed in the linux-raid/linux-btrfs mailing list in November in the thread "Triple parity and beyond":
http://thread.gmane.org/gmane.comp.file-systems.btrfs/30159
The first patch of the serie is the implementation of such discussion, done porting my existing code to the kernel environment.
The code compiles without warnings with gcc -Wall -Wextra, with the clang analyzer, and test programs run cleany with valgrind.
I verified that the module builds, loads and passes the self test in the x86, and x64 architectures. I expect no problems in other platforms, but they are not really tested.
The other two patches are a preliminary change in btrfs and async_tx to use the new interface and to extend the internal support to up to six parities. These are mainly provided to show how to use the new raid interface, and are not meant for inclusion at this stage as they are not tested at all.
A good entry point to understand the code is to start from the include/linux/raid/raid.h file. It contains the functions that external modules should call with a complete description of them.
Then follow with lib/raid/raid.c that contains an introductory description of the mathematical method used, and more details of the implementation of the new RAID interface.
Something that you can try is to build the new RAID Cauchy library as a module (it's in the configuration Library section), and load it with "speedtest=1" argument and see if it pass the selftest and the reported speed measurements.
WARNING! The btrfs/async_tx/md patches are not SAFE to try as they are not tested. They are only example code to show how the new raid library could be integrated in existing code.
Please let me know what do you think. Any kind of feedback is welcome.
Thanks,
Andrea
Andrea Mazzoleni (3):
lib: raid: New RAID library supporting up to six parities
fs: btrfs: Extends btrfs/raid56 to support up to six parities
crypto: async_tx: Extends crypto/async_tx to support up to six
parities
crypto/async_tx/async_pq.c | 257 +++--- crypto/async_tx/async_raid6_recov.c | 286 +++++-- drivers/md/Kconfig | 1 + drivers/md/raid5.c | 206 ++--- drivers/md/raid5.h | 2 +- fs/btrfs/Kconfig | 1 + fs/btrfs/raid56.c | 273 ++---- fs/btrfs/raid56.h | 12 +- fs/btrfs/volumes.c | 4 +- include/linux/async_tx.h | 15 +- include/linux/raid/helper.h | 32 + include/linux/raid/raid.h | 87 ++ lib/Kconfig | 17 + lib/Makefile | 1 + lib/raid/.gitignore | 3 + lib/raid/Makefile | 14 + lib/raid/cpu.h | 44 + lib/raid/gf.h | 109 +++ lib/raid/helper.c | 38 + lib/raid/int.c | 567 +++++++++++++ lib/raid/internal.h | 148 ++++ lib/raid/mktables.c | 338 ++++++++ lib/raid/module.c | 454 ++++++++++ lib/raid/raid.c | 492 +++++++++++ lib/raid/test/Makefile | 33 + lib/raid/test/combo.h | 155 ++++ lib/raid/test/fulltest.c | 74 ++ lib/raid/test/memory.c | 79 ++ lib/raid/test/memory.h | 78 ++ lib/raid/test/selftest.c | 42 + lib/raid/test/speedtest.c | 565 +++++++++++++ lib/raid/test/test.c | 314 +++++++ lib/raid/test/test.h | 59 ++ lib/raid/test/usermode.h | 91 ++ lib/raid/test/xor.c | 41 + lib/raid/x86.c | 1565 +++++++++++++++++++++++++++++++++++ 36 files changed, 5985 insertions(+), 512 deletions(-) create mode 100644 include/linux/raid/helper.h create mode 100644 include/linux/raid/raid.h create mode 100644 lib/raid/.gitignore create mode 100644 lib/raid/Makefile create mode 100644 lib/raid/cpu.h create mode 100644 lib/raid/gf.h create mode 100644 lib/raid/helper.c create mode 100644 lib/raid/int.c create mode 100644 lib/raid/internal.h create mode 100644 lib/raid/mktables.c create mode 100644 lib/raid/module.c create mode 100644 lib/raid/raid.c create mode 100644 lib/raid/test/Makefile create mode 100644 lib/raid/test/combo.h create mode 100644 lib/raid/test/fulltest.c create mode 100644 lib/raid/test/memory.c create mode 100644 lib/raid/test/memory.h create mode 100644 lib/raid/test/selftest.c create mode 100644 lib/raid/test/speedtest.c create mode 100644 lib/raid/test/test.c create mode 100644 lib/raid/test/test.h create mode 100644 lib/raid/test/usermode.h create mode 100644 lib/raid/test/xor.c create mode 100644 lib/raid/x86.c
Signature · 1 line
1.7.12.1
RFC v3 1/3 lib: raid: New RAID library supporting up to six parities
This patch adds a new lib/raid directory, containing a new RAID support based on a Cauchy matrix working for up to six parities, and backward compatible with the existing RAID6 support.
It was developed for kernel 3.13-rc4, but it should work with any other version because it's formed only of new files. The only modification is about adding a new CONFIG_RAID_CAUCHY option in the "lib" configuration section.
The interface is defined in include/linux/raid/raid.h and provides two new functions raid_gen() and raid_rec() that can handle parity generation and data recovering for up to six level of redundancy, and replace the previous RAID6 interface.
The library provides fast implementations using SSE2 and SSSE3 for x86/x64 and a portable C implementation working everythere.
If the RAID6 library is enabled in the kernel, its functionality is also used to maintain the existing level of performance for the first two parities in all the supported architectures.
At startup the module runs a very fast self test (about 1ms) to ensure that the used functions are correct.
You can also enable a speed test similar at the one used by raid6, using the "speedtest=1" argument when loading the module.
In the lib/raid/test directory are present also some user mode test programs:
selftest - Runs the same selftest and speedtest executed at the module startup. fulltest - Runs a more extensive test that checks all the built-in functions. speetest - Runs a more complete speed test.
As a reference, in my icore7 2.7GHz the speedtest program reports:
...
Speed test using 16 data buffers of 4096 bytes, for a total of 64 KiB. Memory blocks have a displacement of 64 bytes to improve cache performance. The reported value is the aggregate bandwidth of all data blocks in MiB/s, not counting parity blocks.
Memory write speed using the C memset() function:
memset 33518
RAID functions used for computing the parity:
int8 int32 int64 sse2 sse2e ssse3 ssse3e
gen1 11762 21450 44621 gen2 3520 6176 18100 20338
gen3 848 8009 9210
gen4 659 6518 7303
gen5 531 4931 5363
gen6 430 4069 4471
RAID functions used for recovering:
int8 ssse3
rec1 591 1126
rec2 272 456
rec3 80 305
rec4 49 216
rec5 34 151...
Legend:
genX functions to generate X parities
recX functions to recover X data blocks
int8 implemention based on 8 bits arithmetics int32 implemention based on 32 bits arithmetics int64 implemention based on 64 bits arithmetics sse2 implemention based on SSE2
sse2e implemention based on SSE2 with 16 registers (x64) ssse3 implemention based on SSSE3
ssse3e implemention based on SSSE3 with 16 registers (x64)
--- include/linux/raid/helper.h | 32 + include/linux/raid/raid.h | 87 +++ lib/Kconfig | 17 + lib/Makefile | 1 + lib/raid/.gitignore | 3 + lib/raid/Makefile | 14 + lib/raid/cpu.h | 44 ++ lib/raid/gf.h | 109 +++ lib/raid/helper.c | 38 ++ lib/raid/int.c | 567 ++++++++++++++++ lib/raid/internal.h | 148 ++++ lib/raid/mktables.c | 338 ++++++++++ lib/raid/module.c | 454 +++++++++++++ lib/raid/raid.c | 492 ++++++++++++++ lib/raid/test/Makefile | 33 + lib/raid/test/combo.h | 155 +++++ lib/raid/test/fulltest.c | 74 ++ lib/raid/test/memory.c | 79 +++ lib/raid/test/memory.h | 78 +++ lib/raid/test/selftest.c | 42 ++ lib/raid/test/speedtest.c | 565 ++++++++++++++++ lib/raid/test/test.c | 314 +++++++++ lib/raid/test/test.h | 59 ++ lib/raid/test/usermode.h | 91 +++ lib/raid/test/xor.c | 41 ++ lib/raid/x86.c | 1565 +++++++++++++++++++++++++++++++++++++++++++ 26 files changed, 5440 insertions(+) create mode 100644 include/linux/raid/helper.h create mode 100644 include/linux/raid/raid.h create mode 100644 lib/raid/.gitignore create mode 100644 lib/raid/Makefile create mode 100644 lib/raid/cpu.h create mode 100644 lib/raid/gf.h create mode 100644 lib/raid/helper.c create mode 100644 lib/raid/int.c create mode 100644 lib/raid/internal.h create mode 100644 lib/raid/mktables.c create mode 100644 lib/raid/module.c create mode 100644 lib/raid/raid.c create mode 100644 lib/raid/test/Makefile create mode 100644 lib/raid/test/combo.h create mode 100644 lib/raid/test/fulltest.c create mode 100644 lib/raid/test/memory.c create mode 100644 lib/raid/test/memory.h create mode 100644 lib/raid/test/selftest.c create mode 100644 lib/raid/test/speedtest.c create mode 100644 lib/raid/test/test.c create mode 100644 lib/raid/test/test.h create mode 100644 lib/raid/test/usermode.h create mode 100644 lib/raid/test/xor.c create mode 100644 lib/raid/x86.c
include/linux/raid/helper.h new file +32 -0
@@ -0,0 +1,32 @@ +/* +* Copyright (C) 2013 Andrea Mazzoleni +* +* This program is free software: you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation, either version 2 of the License, or +* (at your option) any later version. +* +* 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. +*/ + +#ifndef __RAID_HELPER_H +#define __RAID_HELPER_H + +/** +* Inserts an integer in a sorted vector. +* +* This function can be used to insert indexes in order, ready to be used for +* calling raid_rec(). +* +* @n Number of integers currently in the vector. +* @v Vector of integers already sorted. +* It must have extra space for the new elemet at the end. +* @i Value to insert. +*/ +void raid_insert (int n,int *v,int i); + +#endif +
include/linux/raid/raid.h new file +87 -0
87 lines not on this page · raw message
lib/Kconfig +17 -0
@@ -10,6 +10,23 @@ menu "Library routines" config RAID6_PQ tristate +config RAID_CAUCHY + tristate "RAID Cauchy functions" + help + This option enables the RAID parity library based on a Cauchy matrix + that supports up to six parities, and it's compatible with the + existing RAID6 support. + + This library provides optimized functions for triple parity and + beyond for architectures with SSSE3 support. + + The new interface is defined in the linux/raid/raid.h file. + If the RAID6 module is enabled, it's used to maintain the same + performance level for RAID5 and RAID6 in all the architectures + when using the new interface. + + Module will be called raid_cauchy. + config BITREVERSE tristate
lib/Makefile +1 -0
@@ -79,6 +79,7 @@ obj-$(CONFIG_LZ4HC_COMPRESS) += lz4/ obj-$(CONFIG_LZ4_DECOMPRESS) += lz4/ obj-$(CONFIG_XZ_DEC) += xz/ obj-$(CONFIG_RAID6_PQ) += raid6/ +obj-$(CONFIG_RAID_CAUCHY) += raid/ lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
lib/raid/.gitignore new file +3 -0
@@ -0,0 +1,3 @@ +mktables +tables.c +
lib/raid/Makefile new file +14 -0
@@ -0,0 +1,14 @@ +obj-$(CONFIG_RAID_CAUCHY) += raid_cauchy.o + +raid_cauchy-y += module.o raid.o tables.o int.o helper.o + +raid_cauchy-$(CONFIG_X86) += x86.o + +hostprogs-y += mktables + +quiet_cmd_mktable = TABLE $@ + cmd_mktable = $(obj)/mktables > $@ || ( rm -f $@ && exit 1 ) + +targets += tables.c +$(obj)/tables.c: $(obj)/mktables FORCE + $(call if_changed,mktable)
lib/raid/cpu.h new file +44 -0
44 lines not on this page · raw message
lib/raid/gf.h new file +109 -0
109 lines not on this page · raw message
lib/raid/helper.c new file +38 -0
@@ -0,0 +1,38 @@ +/* +* Copyright (C) 2013 Andrea Mazzoleni +* +* This program is free software: you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation, either version 2 of the License, or +* (at your option) any later version. +* +* 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 "internal.h" + +void raid_insert (int n,int *v,int i) +{ +/* we don't use binary search because this is intended */ +/* for very small vectors and we want to optimize the case */ +/* of elements inserted already in order */ + +/* insert at the end */ + v[n] = i; + +/* swap until in the correct position */ +while (n >0 && v[n-1 ] > v[n]) { +/* swap */ +int t = v[n-1 ]; + v[n-1 ] = v[n]; + v[n] = t; + +/* previous position */ + --n; + } +} +EXPORT_SYMBOL_GPL (raid_insert); +
lib/raid/int.c new file +567 -0
567 lines not on this page · raw message
lib/raid/internal.h new file +148 -0
148 lines not on this page · raw message
lib/raid/mktables.c new file +338 -0
338 lines not on this page · raw message
lib/raid/module.c new file +454 -0
454 lines not on this page · raw message
lib/raid/raid.c new file +492 -0
492 lines not on this page · raw message
lib/raid/test/Makefile new file +33 -0
@@ -0,0 +1,33 @@ +# +# This is a simple Makefile to test some of the RAID code +# from userspace. +# + +CC = gcc +CFLAGS = -I.. -I../../../include -Wall -Wextra -g -O2 +LD = ld +OBJS = raid.o int.o x86.o tables.o memory.o test.o helper.o module.o xor.o + +.c.o: + $(CC) $(CFLAGS) -c -o $@ $< + +%.c: ../%.c + cp -f $< $@ + +all: fulltest speedtest selftest + +fulltest: $(OBJS) fulltest.o + $(CC) $(CFLAGS) -o fulltest $^ + +speedtest: $(OBJS) speedtest.o + $(CC) $(CFLAGS) -o speedtest $^ + +selftest: $(OBJS) selftest.o + $(CC) $(CFLAGS) -o selftest $^ + +tables.c: mktables + ./mktables > tables.c + +clean: + rm -f *.o mktables.c mktables tables.c fulltest speedtest selftest +
lib/raid/test/combo.h new file +155 -0
155 lines not on this page · raw message
lib/raid/test/fulltest.c new file +74 -0
74 lines not on this page · raw message
lib/raid/test/memory.c new file +79 -0
79 lines not on this page · raw message
lib/raid/test/memory.h new file +78 -0
78 lines not on this page · raw message
lib/raid/test/selftest.c new file +42 -0
42 lines not on this page · raw message
lib/raid/test/speedtest.c new file +565 -0
183 lines not on this page · raw message
lib/raid/test/test.c new file +314 -0
314 lines not on this page · raw message
lib/raid/test/test.h new file +59 -0
59 lines not on this page · raw message
lib/raid/test/usermode.h new file +91 -0
91 lines not on this page · raw message
lib/raid/test/xor.c new file +41 -0
41 lines not on this page · raw message
lib/raid/x86.c new file +1565 -0
1,565 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
1.7.12.1
Part of the diff is not shown here. View the raw message.
RFC v3 2/3 fs: btrfs: Extends btrfs/raid56 to support up to six parities
In reply to Andrea MazzoleniThis patch makes btrfs/raid56.c to use the new raid interface and extends its support to an arbitrary number of parities.
More in details, the two faila/failb failure indexes are now replaced with a fail[] vector that keeps track of up to six failures. The new raid_gen() and raid_rec() functions are now used to handle all the RAID6 P/Q logic.
For kernel 3.13-rc4.
WARNING! This patch is not tested, and it's NOT meant for inclusion at this stage. It's only example code to show how the new raid library could be integrated in existing code.
--- fs/btrfs/Kconfig | 1 + fs/btrfs/raid56.c | 273 +++++++++++++++++------------------------------------ fs/btrfs/raid56.h | 12 ++- fs/btrfs/volumes.c | 4 +- 4 files changed, 97 insertions(+), 193 deletions(-)
fs/btrfs/Kconfig +1 -0
@@ -5,6 +5,7 @@ config BTRFS_FS select ZLIB_DEFLATE select LZO_COMPRESS select LZO_DECOMPRESS + select RAID_CAUCHY select RAID6_PQ select XOR_BLOCKS
fs/btrfs/raid56.c +86 -187
450 lines not on this page · raw message
fs/btrfs/raid56.h +8 -4
@@ -33,11 +33,15 @@ static inline int nr_data_stripes(struct map_lookup *map) {return map->num_stripes -nr_parity_stripes (map); } -#define RAID5_P_STRIPE ((u64)-2) -#define RAID6_Q_STRIPE ((u64)-1) -#define is_parity_stripe (x) (((x) == RAID5_P_STRIPE) || \ - ((x) == RAID6_Q_STRIPE)) +#define RAID_PAR1_STRIPE ((u64)-6) +#define RAID_PAR2_STRIPE ((u64)-5) +#define RAID_PAR3_STRIPE ((u64)-4) +#define RAID_PAR4_STRIPE ((u64)-3) +#define RAID_PAR5_STRIPE ((u64)-2) +#define RAID_PAR6_STRIPE ((u64)-1) + +#define is_parity_stripe (x) (((u64)(x) >= RAID_PAR1_STRIPE)) int raid56_parity_recover(struct btrfs_root *root, struct bio *bio, struct btrfs_bio *bbio, u64 *raid_map,
fs/btrfs/volumes.c +2 -2
@@ -4918,10 +4918,10 @@ static int __btrfs_map_block(struct btrfs_fs_info *fs_info, int rw, raid_map[(i+rot) % num_stripes] = em->start + (tmp + i) * map->stripe_len; - raid_map[(i+rot) % map->num_stripes] =RAID5_P_STRIPE ; + raid_map[(i+rot) % map->num_stripes] =RAID_PAR1_STRIPE ;if (map->type &BTRFS_BLOCK_GROUP_RAID6 ) raid_map[(i+rot+1 ) % num_stripes] = -RAID6_Q_STRIPE ; +RAID_PAR2_STRIPE ; *length = map->stripe_len; stripe_index =0 ;
Signature · 1 line
1.7.12.1
RFC v3 3/3 crypto: async_tx: Extends crypto/async_tx to support up to six parities
In reply to Andrea MazzoleniThis patch makes crypto/async_tx to use the new raid interface and generalize its interface to support an arbitrary number of parities.
New functions available are async_raid_gen() to compute parity, async_raid_val() to validate parity and async_raid_rec() to recover data. They are a one-to-one matching with the syncronous ones provided by the raid library.
Note that triple parity and beyond are handled in syncronous mode.
It also changes md/raid5.c to remove the RAID6 P/Q logic as now it's completely handled by the async_tx/raid layer.
Another change in raid5.c is the double spare page instead of single one, needed for parity validation. This avoids a double parity computation in the RAID6 syncronous case.
For kernel 3.13-rc4.
WARNING! This patch is not tested, and it's NOT meant for inclusion at this stage. It's only example code to show how the new raid library could be integrated in existing code.
--- crypto/async_tx/async_pq.c | 257 +++++++++++++++++++------------- crypto/async_tx/async_raid6_recov.c | 286 +++++++++++++++++++++++++++++------- drivers/md/Kconfig | 1 + drivers/md/raid5.c | 206 +++++++------------------- drivers/md/raid5.h | 2 +- include/linux/async_tx.h | 15 +- 6 files changed, 448 insertions(+), 319 deletions(-)
crypto/async_tx/async_pq.c +154 -103
@@ -23,6 +23,7 @@#include <linux/interrupt.h> #include <linux/module.h> #include <linux/dma-mapping.h> +#include <linux/raid/raid.h> #include <linux/raid/pq.h> #include <linux/async_tx.h> #include <linux/gfp.h>
@@ -33,15 +34,6 @@*/ static struct page *pq_scribble_page; -/* the struct page *blocks[] parameter passed to async_gen_syndrome() -* and async_syndrome_val() contains the 'P' destination address at -* blocks[disks-2] and the 'Q' destination address at blocks[disks-1] -* -* note: these are macros as they are used as lvalues -*/ -#define P (b, d) (b[d-2]) -#define Q (b, d) (b[d-1]) -/** * do_async_gen_syndrome - asynchronously calculate P and/or Q */
@@ -119,7 +111,8 @@ do_async_gen_syndrome(struct dma_chan *chan,* do_sync_gen_syndrome - synchronously calculate a raid6 syndrome */ static void -do_sync_gen_syndrome (struct page **blocks,unsigned int offset,int disks, +do_sync_gen_syndrome (struct page **blocks,unsigned int offset, +int data_disks,int parity_disks,size_t len,struct async_submit_ctl *submit) {void **srcs;
@@ -130,72 +123,93 @@ do_sync_gen_syndrome(struct page **blocks, unsigned int offset, int disks,else srcs = (void **) blocks; -for (i =0 ; i < disks; i++) { -if (blocks[i] ==NULL ) { -BUG_ON (i > disks -3 );/* P or Q can't be zero */ +/* map NULL data to zero page */ +for (i =0 ; i < data_disks; ++i) { +if (blocks[i] ==NULL ) srcs[i] = (void *)raid6_empty_zero_page; - }else +else srcs[i] =page_address (blocks[i]) + offset; } - raid6_call.gen_syndrome (disks, len, srcs); + +/* map NULL parity to scribble page */ +for (i =0 ; i < parity_disks; ++i) { +if (blocks[data_disks + i] ==NULL ) { + srcs[data_disks + i] = pq_scribble_page; +BUG_ON (len + offset >PAGE_SIZE ); + }else { + srcs[data_disks + i] = blocks[data_disks + i]; + } + } + +raid_gen (data_disks, parity_disks, len, srcs); +async_tx_sync_epilog (submit); }/** -* async_gen_syndrome - asynchronously calculate a raid6 syndrome -* @blocks: source blocks from idx 0..disks-3, P @ disks-2 and Q @ disks-1 +* async_raid_gen - asynchronously calculate a raid syndrome +* @blocks: source data blocks from idx 0..data_disks-1, +* and dest parity blocks from idx data_disks..data_disks+parity_disks-1 * @offset: common offset into each block (src and dest) to start transaction -* @disks: number of blocks (including missing P or Q, see below) +* @data_disks: number of data blocks +* @parity_disks: number of parity blocks * @len: length of operation in bytes * @submit: submission/completion modifiers * * General note: This routine assumes a field of GF(2^8) with a * primitive polynomial of 0x11d and a generator of {02}. * -* 'disks' note: callers can optionally omit either P or Q (but not -* both) from the calculation by setting blocks[disks-2] or -* blocks[disks-1] to NULL. When P or Q is omitted 'len' must be <= -* PAGE_SIZE as a temporary buffer of this size is used in the -* synchronous path. 'disks' always accounts for both destination -* buffers. If any source buffers (blocks[i] where i < disks - 2) are -* set to NULL those buffers will be replaced with the raid6_zero_page -* in the synchronous path and omitted in the hardware-asynchronous -* path. +* Callers can optionally omit some parities (but not all) from the +* calculation by setting the respective pointer in blocks[] to NULL. +* When some parity is omitted 'len' must be <= PAGE_SIZE as a temporary +* buffer of this size is used in the synchronous path. +* If any source data buffers are set to NULL those buffers will be replaced +* with the raid6_zero_page in the synchronous path and omitted in the +* hardware-asynchronous path. */ struct dma_async_tx_descriptor * -async_gen_syndrome (struct page **blocks,unsigned int offset,int disks, +async_raid_gen (struct page **blocks,unsigned int offset, +int data_disks,int parity_disks,size_t len,struct async_submit_ctl *submit) { -int src_cnt = disks -2 ; -struct dma_chan *chan =async_tx_find_channel (submit,DMA_PQ , - &P (blocks, disks),2 , - blocks, src_cnt, len); -struct dma_device *device = chan ? chan->device :NULL ; -struct dmaengine_unmap_data *unmap =NULL ; -BUG_ON (disks >255 || !(P (blocks, disks) ||Q (blocks, disks))); +struct dma_chan *chan =NULL ; +struct dma_device *device =NULL ; +struct dmaengine_unmap_data *unmap =NULL ; +/* async is supported only for two parities */ +if (parity_disks ==2 ) + chan =async_tx_find_channel (submit,DMA_PQ , + &blocks[data_disks], parity_disks, + blocks, data_disks, len); +if (chan) + device = chan->device;if (device) - unmap =dmaengine_get_unmap_data (device->dev, disks,GFP_NOIO ); + unmap =dmaengine_get_unmap_data (device->dev, data_disks + parity_disks,GFP_NOIO ); + +BUG_ON (data_disks + parity_disks >=RAID_DATA_MAX );if (unmap && - (src_cnt <=dma_maxpq (device,0 ) || + (data_disks <=dma_maxpq (device,0 ) ||dma_maxpq (device,DMA_PREP_CONTINUE ) >0 ) &&is_dma_pq_aligned (device, offset,0 , len)) {struct dma_async_tx_descriptor *tx;enum dma_ctrl_flags dma_flags =0 ; -unsigned char coefs[src_cnt]; +unsigned char coefs[data_disks];int i, j; +struct page **parity = &blocks[data_disks]; + +BUG_ON (parity[0 ] ==0 && parity[1 ] ==0 );/* run the p+q asynchronously */ -pr_debug ("%s: (async) disks: %d len: %zu\n" , - __func__, disks, len); +pr_debug ("%s: (async) disks: data: %d parity: %d len: %zu\n" , + __func__, data_disks, parity_disks, len);/* convert source addresses being careful to collapse 'empty' * sources and update the coefficients accordingly */ unmap->len = len; -for (i =0 , j =0 ; i < src_cnt; i++) { +for (i =0 , j =0 ; i < data_disks; i++) {if (blocks[i] ==NULL )continue ; unmap->addr[j] = dma_map_page(device->dev, blocks[i], offset,
@@ -210,8 +224,8 @@ async_gen_syndrome(struct page **blocks, unsigned int offset, int disks,* so use BIDIRECTIONAL mapping */ unmap->bidi_cnt++; -if (P (blocks, disks)) - unmap->addr[j++] =dma_map_page (device->dev,P (blocks, disks), +if (parity[0 ]) + unmap->addr[j++] =dma_map_page (device->dev, parity[0 ], offset, len,DMA_BIDIRECTIONAL );else { unmap->addr[j++] =0 ;
@@ -219,8 +233,8 @@ async_gen_syndrome(struct page **blocks, unsigned int offset, int disks, } unmap->bidi_cnt++; -if (Q (blocks, disks)) - unmap->addr[j++] =dma_map_page (device->dev,Q (blocks, disks), +if (parity[1 ]) + unmap->addr[j++] =dma_map_page (device->dev, parity[1 ], offset, len,DMA_BIDIRECTIONAL );else { unmap->addr[j++] =0 ;
@@ -235,43 +249,40 @@ async_gen_syndrome(struct page **blocks, unsigned int offset, int disks,dmaengine_unmap_put (unmap);/* run the pq synchronously */ -pr_debug ("%s: (sync) disks: %d len: %zu\n" , __func__, disks, len); +pr_debug ("%s: (sync) disks: data: %d parity: %d len: %zu\n" , + __func__, data_disks, parity_disks, len);/* wait for any prerequisite operations */ async_tx_quiesce (&submit->depend_tx); -if (!P (blocks, disks)) { -P (blocks, disks) = pq_scribble_page; -BUG_ON (len + offset >PAGE_SIZE ); - } -if (!Q (blocks, disks)) { -Q (blocks, disks) = pq_scribble_page; -BUG_ON (len + offset >PAGE_SIZE ); - } -do_sync_gen_syndrome (blocks, offset, disks, len, submit); +do_sync_gen_syndrome (blocks, offset, data_disks, parity_disks, len, submit);return NULL ; } -EXPORT_SYMBOL_GPL (async_gen_syndrome); +EXPORT_SYMBOL_GPL (async_raid_gen);static inline struct dma_chan * -pq_val_chan (struct async_submit_ctl *submit,struct page **blocks,int disks,size_t len) +pq_val_chan (struct async_submit_ctl *submit,struct page **blocks, +int data_disks,int parity_disks,size_t len) {#ifdef CONFIG_ASYNC_TX_DISABLE_PQ_VAL_DMA return NULL ;#endif return async_tx_find_channel (submit,DMA_PQ_VAL ,NULL ,0 , blocks, - disks, len); + data_disks + parity_disks, len); }/** -* async_syndrome_val - asynchronously validate a raid6 syndrome -* @blocks: source blocks from idx 0..disks-3, P @ disks-2 and Q @ disks-1 +* async_raid_val - asynchronously validate a raid syndrome +* @blocks: data blocks from idx 0..data_disks-1, +* and parity blocks from idx data_disks..data_disks+parity_disks-1 * @offset: common offset into each block (src and dest) to start transaction -* @disks: number of blocks (including missing P or Q, see below) +* @data_disks: number of data blocks +* @parity_disks: number of parity blocks * @len: length of operation in bytes * @pqres: on val failure SUM_CHECK_P_RESULT and/or SUM_CHECK_Q_RESULT are set -* @spare: temporary result buffer for the synchronous case +* @spare: vector of temporary page buffers for the synchronous case. +* This vector must contain one page for each parity_disks. * @submit: submission / completion modifiers * * The same notes from async_gen_syndrome apply to the 'blocks',
@@ -280,33 +291,41 @@ pq_val_chan(struct async_submit_ctl *submit, struct page **blocks, int disks, si* specified. */ struct dma_async_tx_descriptor * -async_syndrome_val (struct page **blocks,unsigned int offset,int disks, -size_t len,enum sum_check_flags *pqres,struct page *spare, +async_raid_val (struct page **blocks,unsigned int offset, +int data_disks,int parity_disks, +size_t len,enum sum_check_flags *pqres,struct page **spare,struct async_submit_ctl *submit) { -struct dma_chan *chan =pq_val_chan (submit, blocks, disks, len); -struct dma_device *device = chan ? chan->device :NULL ; +struct dma_chan *chan =NULL ; +struct dma_device *device =NULL ;struct dma_async_tx_descriptor *tx; -unsigned char coefs[disks-2 ]; +unsigned char coefs[data_disks];enum dma_ctrl_flags dma_flags = submit->cb_fn ?DMA_PREP_INTERRUPT :0 ;struct dmaengine_unmap_data *unmap =NULL ; -BUG_ON (disks <4 ); - +/* async is supported only for two parities */ +if (parity_disks ==2 ) + chan =pq_val_chan (submit, blocks, data_disks, parity_disks, len); +if (chan) + device = chan->device;if (device) - unmap =dmaengine_get_unmap_data (device->dev, disks,GFP_NOIO ); + unmap =dmaengine_get_unmap_data (device->dev, + data_disks + parity_disks,GFP_NOIO ); -if (unmap && disks <=dma_maxpq (device,0 ) && +if (unmap && + data_disks >=2 && + (data_disks + parity_disks) <=dma_maxpq (device,0 ) &&is_dma_pq_aligned (device, offset,0 , len)) {struct device *dev = device->dev;dma_addr_t pq[2 ];int i, j =0 , src_cnt =0 ; +struct page **parity = &blocks[data_disks]; -pr_debug ("%s: (async) disks: %d len: %zu\n" , - __func__, disks, len); +pr_debug ("%s: (async) disks: data:%d parity:%d len: %zu\n" , + __func__, data_disks, parity_disks, len); unmap->len = len; -for (i =0 ; i < disks-2 ; i++) +for (i =0 ; i < data_disks; i++)if (likely (blocks[i])) { unmap->addr[j] = dma_map_page(dev, blocks[i], offset, len,
@@ -317,21 +336,21 @@ async_syndrome_val(struct page **blocks, unsigned int offset, int disks, j++; } -if (!P (blocks, disks)) { +if (!parity[0 ]) { pq[0 ] =0 ; dma_flags |=DMA_PREP_PQ_DISABLE_P ; }else { - pq[0 ] =dma_map_page (dev,P (blocks, disks), + pq[0 ] =dma_map_page (dev, parity[0 ], offset, len,DMA_TO_DEVICE ); unmap->addr[j++] = pq[0 ]; unmap->to_cnt++; } -if (!Q (blocks, disks)) { +if (!parity[1 ]) { pq[1 ] =0 ; dma_flags |=DMA_PREP_PQ_DISABLE_Q ; }else { - pq[1 ] =dma_map_page (dev,Q (blocks, disks), + pq[1 ] =dma_map_page (dev, parity[1 ], offset, len,DMA_TO_DEVICE ); unmap->addr[j++] = pq[1 ];
@@ -358,16 +377,14 @@ async_syndrome_val(struct page **blocks, unsigned int offset, int disks,return tx; }else { -struct page *p_src =P (blocks, disks); -struct page *q_src =Q (blocks, disks);enum async_tx_flags flags_orig = submit->flags;dma_async_tx_callback cb_fn_orig = submit->cb_fn;void *scribble = submit->scribble;void *cb_param_orig = submit->cb_param; -void *p, *q, *s; +struct page **parity = &blocks[data_disks]; -pr_debug ("%s: (sync) disks: %d len: %zu\n" , - __func__, disks, len); +pr_debug ("%s: (sync) disks: data:%d paritiy:%d len: %zu\n" , + __func__, data_disks, parity_disks, len);/* caller must provide a temporary result buffer and * allow the input parameters to be preserved
@@ -377,35 +394,69 @@ async_syndrome_val(struct page **blocks, unsigned int offset, int disks,/* wait for any prerequisite operations */ async_tx_quiesce (&submit->depend_tx); -/* recompute p and/or q into the temporary buffer and then +/* recompute parity into the temporary buffer and then * check to see the result matches the current value */ tx =NULL ; *pqres =0 ; -if (p_src) { + +/* remove any missing parity at the end, reducing the */ +/* computation complexity required */ +while (parity_disks >0 && parity[parity_disks-1 ] ==0 ) + --parity_disks; + +if (parity_disks ==1 ) { +void *c_ptr; +void *p_ptr; + +/* special case with only one parity */ init_async_submit (submit,ASYNC_TX_XOR_ZERO_DST ,NULL ,NULL ,NULL , scribble); - tx =async_xor (spare, blocks, offset, disks-2 , len, submit); +BUG_ON (spare[0 ] ==0 ); + tx =async_xor (spare[0 ], blocks, offset, data_disks, len, submit);async_tx_quiesce (&tx); - p =page_address (p_src) + offset; - s =page_address (spare) + offset; - *pqres |= !!memcmp (p, s, len) <<SUM_CHECK_P ; - } -if (q_src) { -P (blocks, disks) =NULL ; -Q (blocks, disks) = spare; + c_ptr =page_address (parity[0 ]) + offset; + p_ptr =page_address (spare[0 ]) + offset; + *pqres |= !!memcmp (c_ptr, p_ptr, len) <<SUM_CHECK_P ; + }else if (parity_disks >=2 ) { +/* general case with at least two parities */ +struct page *copy[parity_disks]; +int i; + +/* save the parity pointers */ +for (i =0 ; i < parity_disks; ++i) + copy[i] = parity[i]; + +/* uses the spare buffers for the new parity */ +for (i =0 ; i < parity_disks; ++i) { +BUG_ON (spare[i] ==0 ); + parity[i] = spare[i]; + } +init_async_submit (submit,0 ,NULL ,NULL ,NULL , scribble); - tx =async_gen_syndrome (blocks, offset, disks, len, submit); + tx =async_raid_gen (blocks, offset, data_disks, parity_disks, len, submit);async_tx_quiesce (&tx); - q =page_address (q_src) + offset; - s =page_address (spare) + offset; - *pqres |= !!memcmp (q, s, len) <<SUM_CHECK_Q ; - } -/* restore P, Q and submit */ -P (blocks, disks) = p_src; -Q (blocks, disks) = q_src; +/* comparison of the result */ +for (i =0 ; i < parity_disks; ++i) { +void *c_ptr; +void *p_ptr; + +/* don't check for missing parities */ +if (copy[i] ==0 ) +continue ; + + c_ptr =page_address (copy[i]) + offset; + p_ptr =page_address (parity[i]) + offset; +if (memcmp (c_ptr, p_ptr, len) !=0 ) + *pqres |=1 << (SUM_CHECK_P +i); + } + +/* restore original parity */ +for (i =0 ; i < parity_disks; ++i) + parity[i] = copy[i]; + } submit->cb_fn = cb_fn_orig; submit->cb_param = cb_param_orig;
@@ -415,7 +466,7 @@ async_syndrome_val(struct page **blocks, unsigned int offset, int disks,return NULL ; } } -EXPORT_SYMBOL_GPL (async_syndrome_val); +EXPORT_SYMBOL_GPL (async_raid_val);static int __init async_pq_init (void ) {
@@ -437,5 +488,5 @@ static void __exit async_pq_exit(void)module_init (async_pq_init);module_exit (async_pq_exit); -MODULE_DESCRIPTION ("asynchronous raid6 syndrome generation/validation" ); +MODULE_DESCRIPTION ("asynchronous raid syndrome generation/validation" );MODULE_LICENSE ("GPL" );
crypto/async_tx/async_raid6_recov.c +232 -54
343 lines not on this page · raw message
drivers/md/Kconfig +1 -0
@@ -121,6 +121,7 @@ config MD_RAID10 config MD_RAID456 tristate "RAID-4/RAID-5/RAID-6 mode" depends on BLK_DEV_MD + select RAID_CAUCHY select RAID6_PQ select ASYNC_MEMCPY select ASYNC_XOR
drivers/md/raid5.c +53 -153
303 lines not on this page · raw message
drivers/md/raid5.h +1 -1
@@ -456,7 +456,7 @@ struct r5conf {int recovery_disabled;/* per cpu variables */ struct raid5_percpu { -struct page *spare_page;/* Used when checking P/Q in raid6 */ +struct page *spare_page[2 ];/* Used when checking P/Q in raid6 */ void *scribble;/* space for constructing buffer * lists and performing address * conversions
include/linux/async_tx.h +7 -8
@@ -185,20 +185,19 @@ async_memcpy(struct page *dest, struct page *src, unsigned int dest_offset,struct dma_async_tx_descriptor *async_trigger_callback (struct async_submit_ctl *submit);struct dma_async_tx_descriptor * -async_gen_syndrome (struct page **blocks,unsigned int offset,int src_cnt, +async_raid_gen (struct page **blocks,unsigned int offset, +int data_disks,int parity_disks,size_t len,struct async_submit_ctl *submit);struct dma_async_tx_descriptor * -async_syndrome_val (struct page **blocks,unsigned int offset,int src_cnt, -size_t len,enum sum_check_flags *pqres,struct page *spare, +async_raid_val (struct page **blocks,unsigned int offset, +int data_disks,int parity_disks, +size_t len,enum sum_check_flags *pqres,struct page **spare,struct async_submit_ctl *submit);struct dma_async_tx_descriptor * -async_raid6_2data_recov (int src_num,size_t bytes,int faila,int failb, -struct page **ptrs,struct async_submit_ctl *submit); - -struct dma_async_tx_descriptor * -async_raid6_datap_recov (int src_num,size_t bytes,int faila, +async_raid_rec (int rec_disks,int *rec_indexes, +int data_disks,int parity_disks,size_t bytes,struct page **ptrs,struct async_submit_ctl *submit);void async_tx_quiesce (struct dma_async_tx_descriptor **tx);
Signature · 1 line
1.7.12.1