From patchwork Thu Nov 13 15:15:56 2008 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Yanok X-Patchwork-Id: 8579 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from ozlabs.org (localhost [127.0.0.1]) by ozlabs.org (Postfix) with ESMTP id 4BD60DDF45 for ; Fri, 14 Nov 2008 02:17:37 +1100 (EST) X-Original-To: linuxppc-dev@ozlabs.org Delivered-To: linuxppc-dev@ozlabs.org Received: from ocean.emcraft.com (ocean.emcraft.com [213.221.7.182]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 327B8DDF12 for ; Fri, 14 Nov 2008 02:16:48 +1100 (EST) Received: from [172.17.0.9] (helo=localhost.localdomain) by ocean.emcraft.com with esmtp (Exim 4.43) id 1L0dw3-00055K-8p; Thu, 13 Nov 2008 18:16:44 +0300 From: Ilya Yanok To: linux-raid@vger.kernel.org Subject: [PATCH 03/11] async_tx: add support for asynchronous RAID6 recovery operations Date: Thu, 13 Nov 2008 18:15:56 +0300 Message-Id: <1226589364-5619-4-git-send-email-yanok@emcraft.com> X-Mailer: git-send-email 1.5.6.5 In-Reply-To: <1226589364-5619-1-git-send-email-yanok@emcraft.com> References: <1226589364-5619-1-git-send-email-yanok@emcraft.com> X-Spam-Score: -4.3 (----) X-Spam-Report: Spam detection software, running on the system "pacific.emcraft.com", has identified this incoming email as possible spam. The original message has been attached to this so you can view it (if it isn't spam) or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: This patch extends async_tx API with two operations for recovery operations on RAID6 array with two failed disks using new async_pqxor() operation. New functions: async_r6_dd_recov() recovers after double data disk failure async_r6_dp_recov() recovers after D+P failure [...] Content analysis details: (-4.3 points, 2.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.8 ALL_TRUSTED Passed through trusted hosts only via SMTP -2.6 BAYES_00 BODY: Bayesian spam probability is 0 to 1% [score: 0.0000] 0.1 AWL AWL: From: address is in the auto white-list Cc: linuxppc-dev@ozlabs.org, dzu@denx.de, wd@denx.de, Ilya Yanok X-BeenThere: linuxppc-dev@ozlabs.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: Linux on PowerPC Developers Mail List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linuxppc-dev-bounces+patchwork-incoming=ozlabs.org@ozlabs.org Errors-To: linuxppc-dev-bounces+patchwork-incoming=ozlabs.org@ozlabs.org This patch extends async_tx API with two operations for recovery operations on RAID6 array with two failed disks using new async_pqxor() operation. New functions: async_r6_dd_recov() recovers after double data disk failure async_r6_dp_recov() recovers after D+P failure Signed-off-by: Yuri Tikhonov Signed-off-by: Ilya Yanok --- crypto/async_tx/Kconfig | 5 + crypto/async_tx/Makefile | 1 + crypto/async_tx/async_r6recov.c | 275 +++++++++++++++++++++++++++++++++++++++ include/linux/async_tx.h | 10 ++ 4 files changed, 291 insertions(+), 0 deletions(-) create mode 100644 crypto/async_tx/async_r6recov.c diff --git a/crypto/async_tx/Kconfig b/crypto/async_tx/Kconfig index b1705d1..31a0aae 100644 --- a/crypto/async_tx/Kconfig +++ b/crypto/async_tx/Kconfig @@ -18,3 +18,8 @@ config ASYNC_PQXOR tristate select ASYNC_CORE +config ASYNC_R6RECOV + tristate + select ASYNC_CORE + select ASYNC_PQXOR + diff --git a/crypto/async_tx/Makefile b/crypto/async_tx/Makefile index 32d6ce2..76fcd43 100644 --- a/crypto/async_tx/Makefile +++ b/crypto/async_tx/Makefile @@ -3,3 +3,4 @@ obj-$(CONFIG_ASYNC_MEMCPY) += async_memcpy.o obj-$(CONFIG_ASYNC_MEMSET) += async_memset.o obj-$(CONFIG_ASYNC_XOR) += async_xor.o obj-$(CONFIG_ASYNC_PQXOR) += async_pqxor.o +obj-$(CONFIG_ASYNC_R6RECOV) += async_r6recov.o diff --git a/crypto/async_tx/async_r6recov.c b/crypto/async_tx/async_r6recov.c new file mode 100644 index 0000000..4c6b100 --- /dev/null +++ b/crypto/async_tx/async_r6recov.c @@ -0,0 +1,275 @@ +/* + * Copyright(c) 2007 Yuri Tikhonov + * + * Developed for DENX Software Engineering GmbH + * + * Asynchronous RAID-6 recovery calculations ASYNC_TX API. + * + * based on async_xor.c code written by: + * Dan Williams + * + * 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. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 59 + * Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The full GNU General Public License is included in this distribution in the + * file called COPYING. + */ +#include +#include +#include +#include +#include + +#include "../drivers/md/raid6.h" + +/** + * async_r6_dd_recov - attempt to calculate two data misses using dma engines. + * @disks: number of disks in the RAID-6 array + * @bytes: size of strip + * @faila: first failed drive index + * @failb: second failed drive index + * @ptrs: array of pointers to strips (last two must be p and q, respectively) + * @flags: ASYNC_TX_ACK, ASYNC_TX_DEP_ACK + * @depend_tx: depends on the result of this transaction. + * @cb: function to call when the operation completes + * @cb_param: parameter to pass to the callback routine + */ +struct dma_async_tx_descriptor * +async_r6_dd_recov(int disks, size_t bytes, int faila, int failb, + struct page **ptrs, enum async_tx_flags flags, + struct dma_async_tx_descriptor *depend_tx, + dma_async_tx_callback cb, void *cb_param) +{ + struct dma_async_tx_descriptor *tx = NULL; + struct page *lptrs[disks]; + unsigned char lcoef[disks - 2]; + int i = 0, k = 0, fc = -1; + uint8_t bc[2]; + dma_async_tx_callback lcb = NULL; + void *lcb_param = NULL; + + /* Assume that failb > faila */ + if (faila > failb) { + fc = faila; + faila = failb; + failb = fc; + } + + /* + * Try to compute missed data asynchronously. + */ + + if (disks == 4) { + /* Pxy and Qxy are zero in this case so we already have + * P+Pxy and Q+Qxy in P and Q strips respectively. + */ + tx = depend_tx; + lcb = cb; + lcb_param = cb_param; + goto do_mult; + } + + /* (1) Calculate Qxy and Pxy: + * Qxy = A(0)*D(0) + ... + A(n-1)*D(n-1) + A(n+1)*D(n+1) + ... + + * A(m-1)*D(m-1) + A(m+1)*D(m+1) + ... + A(disks-1)*D(disks-1), + * where n = faila, m = failb. + */ + for (i = 0, k = 0; i < disks - 2; i++) { + if (i != faila && i != failb) { + lptrs[k] = ptrs[i]; + lcoef[k] = raid6_gfexp[i]; + k++; + } + } + + tx = async_pqxor(ptrs[faila], ptrs[failb], lptrs, lcoef, 0, k, bytes, + ASYNC_TX_XOR_ZERO_DST | ASYNC_TX_ASYNC_ONLY, + depend_tx, NULL, NULL); + if (!tx) { + /* Here may go to the synchronous variant */ + if (flags & ASYNC_TX_ASYNC_ONLY) + return NULL; + goto ddr_sync; + } + + /* The following operations will 'damage' P/Q strips; + * so now we condemned to move in a asynchronous way. + */ + + /* (2) Calculate Q+Qxy + */ + lptrs[0] = ptrs[failb]; + tx = async_pqxor(ptrs[disks-1], NULL, lptrs, NULL, 0, 1, bytes, + ASYNC_TX_DEP_ACK, tx, NULL, NULL); + + /* (3) Calculate P+Pxy + */ + lptrs[0] = ptrs[faila]; + tx = async_pqxor(ptrs[disks-2], NULL, lptrs, NULL, 0, 1, bytes, + ASYNC_TX_DEP_ACK, tx, NULL, NULL); + +do_mult: + /* (4) Compute (P+Pxy) * Bxy. Compute (Q+Qxy) * Cxy. XOR them and get + * faila. + * B = (2^(y-x))*((2^(y-x) + {01})^(-1)) + * C = (2^(-x))*((2^(y-x) + {01})^(-1)) + * B * [p] + C * [q] -> [failb] + */ + bc[0] = raid6_gfexi[failb-faila]; + bc[1] = raid6_gfinv[raid6_gfexp[faila]^raid6_gfexp[failb]]; + + lptrs[0] = ptrs[disks - 2]; + lptrs[1] = ptrs[disks - 1]; + tx = async_pqxor(NULL, ptrs[failb], lptrs, bc, 0, 2, bytes, + ASYNC_TX_DEP_ACK | ASYNC_TX_XOR_ZERO_DST, + tx, NULL, NULL); + + /* (5) Compute failed Dy using recovered [failb] and P+Pnm in [p] + */ + lptrs[0] = ptrs[disks-2]; + lptrs[1] = ptrs[failb]; + tx = async_pqxor(ptrs[faila], NULL, lptrs, NULL, 0, 2, bytes, + ASYNC_TX_DEP_ACK | ASYNC_TX_XOR_ZERO_DST, tx, lcb, + lcb_param); + + if (disks == 4) + return tx; + + /* (6) Restore the parities back + */ + flags |= ASYNC_TX_XOR_ZERO_DST; + flags |= ASYNC_TX_DEP_ACK; + + memcpy(lptrs, ptrs, (disks - 2) * sizeof(struct page *)); + return async_gen_syndrome(ptrs[disks-2], ptrs[disks-1], lptrs, 0, + disks - 2, bytes, flags, tx, cb, cb_param); + +ddr_sync: + { + void **sptrs = (void **)lptrs; + + /* + * Failed to compute asynchronously, do it in + * synchronous manner + */ + /* wait for any prerequisite operations */ + async_tx_quiesce(&depend_tx); + + i = disks; + while (i--) + sptrs[i] = page_address(ptrs[i]); + raid6_2data_recov(disks, bytes, faila, failb, sptrs); + + async_tx_sync_epilog(cb, cb_param); + } + + return tx; +} +EXPORT_SYMBOL_GPL(async_r6_dd_recov); + +/** + * async_r6_dp_recov - attempt to calculate one data miss using dma engines. + * @disks: number of disks in the RAID-6 array + * @bytes: size of strip + * @faila: failed drive index + * @ptrs: array of pointers to strips (last two must be p and q, respectively) + * @flags: ASYNC_TX_ACK, ASYNC_TX_DEP_ACK + * @depend_tx: depends on the result of this transaction. + * @cb: function to call when the operation completes + * @cb_param: parameter to pass to the callback routine + */ +struct dma_async_tx_descriptor * +async_r6_dp_recov(int disks, size_t bytes, int faila, struct page **ptrs, + enum async_tx_flags flags, struct dma_async_tx_descriptor *depend_tx, + dma_async_tx_callback cb, void *cb_param) +{ + struct dma_async_tx_descriptor *tx = NULL; + struct page *lptrs[disks]; + unsigned char lcoef[disks]; + int i = 0, k = 0; + + /* + * Try compute missed data asynchronously + */ + /* (1) Calculate Qn + Q: + * Qn = A(0)*D(0) + .. + A(n-1)*D(n-1) + A(n+1)*D(n+1) + .., + * where n = faila; + * then subtract Qn from Q and place result to Pn. + */ + for (i = 0; i < disks - 2; i++) { + if (i != faila) { + lptrs[k] = ptrs[i]; + lcoef[k++] = raid6_gfexp[i]; + } + } + lptrs[k] = ptrs[disks-1]; /* Q-parity */ + lcoef[k++] = 1; + + tx = async_pqxor(NULL, ptrs[disks-2], lptrs, lcoef, 0, k, + bytes, ASYNC_TX_XOR_ZERO_DST | ASYNC_TX_ASYNC_ONLY, + depend_tx, NULL, NULL); + if (!tx) { + if (flags & ASYNC_TX_ASYNC_ONLY) + return NULL; + goto dpr_sync; + } + + /* (2) Compute missed Dn: + * Dn = (Q + Qn) * [A(n)^(-1)] + */ + lptrs[0] = ptrs[disks-2]; + return async_pqxor(NULL, ptrs[faila], + lptrs, (u8 *)&raid6_gfexp[faila ? 255-faila : 0], + 0, 1, bytes, ASYNC_TX_DEP_ACK | ASYNC_TX_XOR_ZERO_DST, + tx, cb, cb_param); + +dpr_sync: + { + void **sptrs = (void **) lptrs; + + /* + * Failed to compute asynchronously, do it in + * synchronous manner + */ + /* wait for any prerequisite operations */ + async_tx_quiesce(&depend_tx); + + i = disks; + while (i--) + sptrs[i] = page_address(ptrs[i]); + raid6_datap_recov(disks, bytes, faila, (void *)sptrs); + + async_tx_sync_epilog(cb, cb_param); + } + + return tx; +} +EXPORT_SYMBOL_GPL(async_r6_dp_recov); + +static int __init async_r6recov_init(void) +{ + return 0; +} + +static void __exit async_r6recov_exit(void) +{ + do { } while (0); +} + +module_init(async_r6recov_init); +module_exit(async_r6recov_exit); + +MODULE_AUTHOR("Yuri Tikhonov "); +MODULE_DESCRIPTION("asynchronous RAID-6 recovery api"); +MODULE_LICENSE("GPL"); diff --git a/include/linux/async_tx.h b/include/linux/async_tx.h index 9038b06..f40e89a 100644 --- a/include/linux/async_tx.h +++ b/include/linux/async_tx.h @@ -177,5 +177,15 @@ async_syndrome_zero_sum(struct page *pdest, struct page *qdest, struct dma_async_tx_descriptor *depend_tx, dma_async_tx_callback callback, void *callback_param); +struct dma_async_tx_descriptor * +async_r6_dd_recov (int src_num, size_t bytes, int faila, int failb, struct page **ptrs, + enum async_tx_flags flags, struct dma_async_tx_descriptor *depend_tx, + dma_async_tx_callback callback, void *callback_param); + +struct dma_async_tx_descriptor * +async_r6_dp_recov (int src_num, size_t bytes, int faila, struct page **ptrs, + enum async_tx_flags flags, struct dma_async_tx_descriptor *depend_tx, + dma_async_tx_callback callback, void *callback_param); + void async_tx_quiesce(struct dma_async_tx_descriptor **tx); #endif /* _ASYNC_TX_H_ */