From patchwork Tue Mar 30 14:25:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172695 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 02890C433DB for ; Tue, 30 Mar 2021 14:26:20 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CAFF0619BD for ; Tue, 30 Mar 2021 14:26:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231730AbhC3OZs (ORCPT ); Tue, 30 Mar 2021 10:25:48 -0400 Received: from sonic308-54.consmr.mail.gq1.yahoo.com ([98.137.68.30]:37800 "EHLO sonic308-54.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232020AbhC3OZr (ORCPT ); Tue, 30 Mar 2021 10:25:47 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114346; bh=tUzFRPQCk/k3kOrqIax53zdggLUM9qodvvAwCj+kYE4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=J/FSRtpWoNQmHfNF8RCQ7IU27cNNvS+WULTjHNDRXPfU9NFQ9/RcrmMiwWUmzKB2OrXE1S20/N7JXzUf75q+no8m+yfAK+P8Od08IsNl7Qb5kvXsGcXpjtIRpKfKwEN91HChIpJaT/SDcbjoOEmhUyjY1M7iUiXfgTCpOY/wYGQTzC3hSlmnfu/CQr4AJxgogbSlyiZkxNlpt1qjnYvdvTKlm3PPlo9Q4ukogr+dkJzmHkgc9cLcxwav9lshpZEvTK2s5SfWaxkERJjw+7UxgBlXlStjwOCpFSr91MHGaEXedP7Ux0hh7soLM55lmOJff75wzcV/kFgnerof1xe53Q== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114346; bh=71jth4gSUW+J7lZzpk1eHXF4rhzP3vX9RgjWKOkxHkW=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=IY+Lf9mfIL6R0voicCXR3D7GfVvK4XJGEeU59coxYPv/6kLMFjIPiX3ulBC/IHqZ311197nd7H4Q0uUNQCC7tj6Oreac48RiHFj0F3qDvzPTDtIVp3QQ/nYDkTvDGTNNIwH3jSk9znARSJiuR+EwFShHsuEIaudmevmPMI/Z/Lyw1TCBOEPVq3mccwwd1p9LrCLOjmBvZWjTqWZyXhdwqQWzTBdVh++J7ZLSZnhTBL9AtPYHVJuEDb4ROR8XArK3H/9D3fRdCjJ3haRjGUiNP9Msj3mUX5DBqZk6aiRsa7PB49sYdHPSgw9XUqtX8R8Kc4Hxf9j2kbVl8jglqFTERQ== X-YMail-OSG: TxfUab0VM1lORk.aUO3q1LywUMiSn02eLr.QQZC1BJzkfajLtdWXSaJBQZjnRFt xAmeN5ZeNrV37vacMMhfc0jlZlxPb_52qToHCSI1OX1Sd4Hqe.gSqgngkyzpRLcXgHIb48AsSLXn 7WVL6v0h7Qhn950UKA1JAn9VUA4BgXutPKjLTPjsax51hkNnllwML1mZKPD.KqhEyNzPD0wLPb9G QRtEWSsDywxJhI9ORAL6WU4gN5BvgKpOjR5tD4aiq1B.5iPLdoRV_0QyhLisUXNoHLjHEh2KZozW Y2_fuZAj.w_v_Yi8CBxZhRYeTolyE7RNqEnjYkL5OgXEx4IZxjN.idXkKqUy58XNDqoJ9gRmTg6N k6R0cMtPztYXjzxjomS26EWIChvRFE1TgVYDGLN9WEeb8OdmHD2qpda7qwQBtRfIXYkBmLM9ApR4 v68kV0GrhnrEtNt67P2w9Me0PY09Wdh05tbqEvNu_JiXQlyQv6ydxRroqmy9FI4.LlHu9Wwcur.A cCfI8pz0Vb2WgpKKxXXiXUYn74LdsKkQq1JBi3EQCuAuNhqT4xee17JxvhbJ2UHEmzD7r.SuBW0t IulVyR4oT7KKRC_os8AQqnaCS1h1uHahWfHKfKNfcuAA0CIydLqRvve2EkiXtxPG_Gtnfm8tV3hZ aPaxnazKYSojNP2c6iMaBbMVwjAdSahVlPwUB9EBzgvkQAM7QcHu71O4SAJ438mnNWdufjnJoETy fvagFoMytW_6mXiRd0K9bfZKWfsxUU7.LmJ33kcI5ZNy8_kDIa2aBOuybHRX_rsjRIToj5zK8CfY W9LVy2vnfbdsh8KIv2CrGm61nm3e_MhOi6rKE1banGH8OI5gW1WO4Yaf.bdn8BMogve8dvEcqC.p lGBqT3PStOkJaoQbduZl6hqgNSr75L1tzL5LKts2UPhl2rmYCMsXZo.WtNpbLRJGbqjR.X9kYmr7 7O.KY6zyWF1Kx4VPoI2JQJ_9gf9PYoQZKxb2W488pc2No4TAZkJ.bLJALJsv7U0W9vjxyLQ0DxGp JoRiQ0b5D6JUEJySnwj.fEUe0l0D2gZ9LlzoB6QpdFHFcfwr1PUW36oqvNlMC0q55vmFYgc01HCU 3wrd9mEBmcqhK_WK.SWQRNtqZGwZRtfWjanbZ4nCWJfjhHspePrNqoSRgMlcjfG3xEexaCgeWXgu 6e6eADPQ87fdDPeIVIsUxBZ4d_yScKxqW5vjJwvN19QNLfp3DexHQ3I4m4Yy7vzLnsXdK1sIis4E e8WvOKafoJVNJIPLLzoBqf6z9wBhhReYxB8vTCch7wKSajQ0_tedw5NfWHlzgMr8k8inMiLbS3FV kCALK4Z5sfpfcTmbVq8hfWQR65rOKfwdecMT74NU4SfJvMHEqjeTH8q4o6Nl2yOHqI4rgTL3PE94 tKIm.yGAGGUUUNRzxJKwXREI.63HCDopc3byuUAuF1jCSFHFICUsoVtwL5Kn5ObnDJeJ.Bs.W_RE BYvDBWkM87t8nJbUDU4Y4SFdY0DjH5gTY9KFnYgaao3.C773BGOEj_z3werDGH5XVs4w5kmtWLCP LXDXkK89WMLhEHWcjPyqBTJX95f.jiHXR5hwysAVDAgrJUiOxGnowt_5cUBnSG42qf.xLhUgVIgH hY5zVZ_M2qcoRnfuP4ZzcsID3gZPIURodC1QqefynTJE56gMokPeVjLQZQPCNK2CkTFZnkqkq3ks LhKL86aMTjE5qQ13XggRnIur2u47UQDZFSbhDm.mSKLaxKAd5xUxl5EdiXx4rlR9gk8g6pPhRbDu zS.RNYkHPqYRE_pohc1iB2lhtAGA8nFJ8ChNa7wZAkXIdTIKdjoEWYCz6sXLjSwfbLc9xpFjr3XV zrfMnHiehA53fSFkr5bAFehALgHYFxFPUEc.UOFC3z5k0cR.tdNAGVRb23Fq1mLOUjZQoPhZQnEj a_CMmJG3bMvDDC5VKAUdDP6bYyFizO6qVV9Ldm4PblyserrdTtHN7kJvG9IGLHui7jcVsxAw5NCZ JtOGNLvILshAnGddJFQehMMxfBFRlPj1zRo2gp_i3p3zRsodtBSyrm9LeajM2emflae__ONUkGZ1 h5FVaAc_j0A6Ifcukjt2kFp.tZPClETfO5mjJoAw4coxXARTODprvs1hQo2Sc7bAwrz_sIQqn94O IcDv5BflVgcLmEClG9IgwK7sWJuyU5xYVvBEDnFHDxkKaASZ8bn.QIY2oR3GJw11E_wJ1q2mmWA3 c5xt0RBkLOewqryhQtZjPJdeNwh.zt4oMllr2BEgtYRPuk3Ubtvkob8254K2CrSHW3YfqCoLHYcg HpdA_BjOXIArJvVzF3UaQCksIVdqC78njjv1uCk24SREONMme9XSBIwX7n61lKDzt8IsBQLnvnFI eCQMQ2XDZps0tj2Cajj1tyDvVMLUPIskCHx.EXj_sOSyRCXAyMYkumkwMSV2tjlYdiCnNVjltd9n JiIWvmntpoBkxeW8C9TSgZWKD0ff1bVMgx6V0ppMsXQIMZXI_8Q53e.oQ2stN1V.CsvPA0qBzeMk XQ.xuONUZNk2c62tEndFoAA-- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic308.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:25:46 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:43 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Gao Xiang Subject: [PATCH v3 1/8] repair: turn bad inode list into array Date: Tue, 30 Mar 2021 22:25:24 +0800 Message-Id: <20210330142531.19809-2-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Gao Xiang Just use array and reallocate one-by-one here (not sure if bulk allocation is more effective or not.) Signed-off-by: Gao Xiang --- repair/dir2.c | 34 +++++++++++++++++----------------- repair/dir2.h | 2 +- 2 files changed, 18 insertions(+), 18 deletions(-) diff --git a/repair/dir2.c b/repair/dir2.c index eabdb4f2d497..b6a8a5c40ae4 100644 --- a/repair/dir2.c +++ b/repair/dir2.c @@ -20,40 +20,40 @@ * Known bad inode list. These are seen when the leaf and node * block linkages are incorrect. */ -typedef struct dir2_bad { - xfs_ino_t ino; - struct dir2_bad *next; -} dir2_bad_t; +struct dir2_bad { + unsigned int nr; + xfs_ino_t *itab; +}; -static dir2_bad_t *dir2_bad_list; +static struct dir2_bad dir2_bad; static void dir2_add_badlist( xfs_ino_t ino) { - dir2_bad_t *l; + xfs_ino_t *itab; - if ((l = malloc(sizeof(dir2_bad_t))) == NULL) { + itab = realloc(dir2_bad.itab, (dir2_bad.nr + 1) * sizeof(xfs_ino_t)); + if (!itab) { do_error( _("malloc failed (%zu bytes) dir2_add_badlist:ino %" PRIu64 "\n"), - sizeof(dir2_bad_t), ino); + sizeof(xfs_ino_t), ino); exit(1); } - l->next = dir2_bad_list; - dir2_bad_list = l; - l->ino = ino; + itab[dir2_bad.nr++] = ino; + dir2_bad.itab = itab; } -int +bool dir2_is_badino( xfs_ino_t ino) { - dir2_bad_t *l; + unsigned int i; - for (l = dir2_bad_list; l; l = l->next) - if (l->ino == ino) - return 1; - return 0; + for (i = 0; i < dir2_bad.nr; ++i) + if (dir2_bad.itab[i] == ino) + return true; + return false; } /* diff --git a/repair/dir2.h b/repair/dir2.h index 5795aac5eaab..af4cfb1da329 100644 --- a/repair/dir2.h +++ b/repair/dir2.h @@ -27,7 +27,7 @@ process_sf_dir2_fixi8( struct xfs_dir2_sf_hdr *sfp, xfs_dir2_sf_entry_t **next_sfep); -int +bool dir2_is_badino( xfs_ino_t ino); From patchwork Tue Mar 30 14:25:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172703 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9D68CC433DB for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6E1D7619D0 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231694AbhC3O0T (ORCPT ); Tue, 30 Mar 2021 10:26:19 -0400 Received: from sonic316-54.consmr.mail.gq1.yahoo.com ([98.137.69.30]:40123 "EHLO sonic316-54.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232004AbhC3OZv (ORCPT ); Tue, 30 Mar 2021 10:25:51 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114351; bh=0DKaLMLKGPV4V7NUDw1i/Rk6USZIsGSOjxW+ihUu+eY=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=Fox0ICOOc5TVGXqnZidlysbi8JDxQXBhGAbBhVqlepXwo+tKc4DLEZ9HcQMkqiHVPBNKVaTIzic4QkTyPKdGeQSK7s4Ih0RZl8lcyIRB+rnDSHx8X2eakFM6GlAEYtwLxxpQ27CR/iYs2FwUVBTMjBPbUtkOup8CS/UHwlkvs5BPnKYxT9d8v6dCyJnp0DrB7alFfECGGUUI4Qyo3tyEwC5KEF1h7AdsXpCW+wm03HMl76cm25/z0SigBuMSXDFCpO8TNuA9vHIETVPR0p3C0iu+Kgjn1do9vc+p3L0Q2ilkvVjj1mTWPNnnzEuNBrgRdL7ryMAeKldZdFSaYBEIjg== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114351; bh=WexBFiXV8eIXzbxhmTlGjDVTiRsql6qBDWosGxTLJ94=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=ilJZ8wAQr/PNMfM4W/awMDnDRYa+u1Dl2/vXUwQBbDUXRcaR3TsaVBVJDuJdnowVTXPp/srwpR3rWEsuBwUt+M4dtdDp82v8dgOGAdtTlfrdjX2A3iRQ86taQihuC1pEQbnwfpdfpkTzIrNzwyAy1+YMxPe5IBFxiEwqQs2CXl2C06lZk4hpp1/qoQ4L6DUsiilbSR+2/EYxfDL76rbgUYkSdVjk1YRMWlfi+4jlrdHZUxF4faQGK7X54PotkQj3Q5GvLO0q5U55CGb0Nnt8fbgZ/8fXSdFKe0+n5uhs2lzOXetMhX2eOqvGApS0bE2EMHmOW2LvoEwn2psRJR30hQ== X-YMail-OSG: fKCERFQVM1kvjLrZquSZjVyoWdXUNZl2nKz00khBjO8osclEwgLPL8jneabzlHP O9Uc_R9hdOL8k0B956r1L6rQzWwe74LEvFMjC.B97gId8fUgnWp0U7UUqVtjQhRUktXmaENsl2XE Uz4v5QDE3MnTo1l.8N6uaI8VV9_Ld04unzeTnAvIPM6.tfzLwlo1Eu1aAK0r_k8lLdLRGCQ6aDxw fqLq84EzrU6O.NNYrBLla_ts6NduilJUHoOL_Uar15SS_MLBA9apEffCTKXt7sj8XeDTH2cn1tHg dEkJ4pDfBBoQJ.OecCZEfAN2tPEAFVuEr.YsYdVZttI6pGFlX2jXasuVfvUS.Ix8V.CPeQm.ufa1 _BjunYsH8toh9JXeKuaD8daxP8L1qVzyGa6Vqai1yLwy2YZKtRpAost4wyQ7NIX2YPQfkyGIuKLF LzkreMmoV73hiyoYqzYa5HJsrwPqMcg0b6_moRegZT5bkGLq3OwhzX14nDsDQ6mv1pcK6MNdnEoQ o6or6twpXMoyAdFwogBXaWVY39MiiRnxaJ7gvbxTYeoRFiFReWkZoCLUyQUClKqelGtv5hOp58QZ L.7jKc5wvC5EvvNS4tPFnCUDYjBt1U6HuAlcdT3hakwjDSpc4uKJcuF7lT3ef2zh9_KHhfdBc6XX 8YGrFNGtkMSNO8NIGWv98L.xx0t_vrpwVpdihZSGPxGT3YpTwhtenyc_aIsgX8E.jsACsdGfVWcr xHzH7aORscql19GFfEVZ1rlhMFILs7hf6hbMNy8SPohn0zaOrAb4EF3GI1OK1lueOZ3fOUmBiuKb TqyUj3GWShJTTCilidEtxtjBqDpdkk3j.KtaNc9KFXnJI40MjVPT6wnL8ZWaNISmvyIlnh2UxVNI _Wo7uGXrezW9tzAAHhmy9O_xD_RDgGo9c2pp7Fp7VBmJ8wqekVuNSY.XZNWMES.Xwzn_I9uL8iPp .VXnOxhPpfWct2UlGUcT8qKrS8UUFMdfvba0qaNxixWp6vU3SX7uqi7Z1x8owRkY6_pre_liyKuD M1tv.ljSTiu.FSSPlZRy8PhP15GnfKF7FzEc4GX_PVeY0902jhqI9F.mlDbcY_zcNnO5YyBnVSC8 Jjd2lAEbc9_ywJlXFl7MwzZQ8pUrR4YW8pVcXK4zMJl_s8T1hS3yQG6xtXOFl.pd7DK7u24m.lfa NuZbB_b6oe3rNh4fnY0LXwowli7VmYAN6LfY9CxmyTjtVTpHFmDTI319Ega9Wsp7Xmfz8xMW9Vo_ CdHs9vDX1c9Ac9rFX84Ad.UHs5YPktBmfsfuO6weLuBsyereEhKD7Af2v_dd2n.gM4i1xgyu3Cw_ rgJdomiYvPq9E0vyojc4d4k5uusKDoeIMfnA7XFkTTrbIeUucRmxoy1HTdtnRic7efcXhAcogaSE RTb_Jq_N67p3S.v.U2v3hWvDFs7sDq7LD0n.5rYI1DWetMa7RDZxbIDVt8ps9.a_aXcIDF8x.k6C t8wmDigGAJGEOQr5IWgGC.KQzQTJ2YPVRmuUtlvyi.x_ei79ob2mL7AHg6850mIlpnbagNp9XrtP kCdCyjVvLfqN9ih2UHWVtwr5hxB4WtM_saLmfGSJWjDDJbyus6R.F6yLwJK4WUx7vRRBt.FpaqhH gWV4Uc7.yhFq.spg_7arfpRU1nhklSBn.7fU7AtlI2MEtW61FjTjFzBj0T661mmEmniwT026nFLf vO1lEKUuHVxgoy553KYbRWcy18VP3HYes5Lbzq4dX2s7W9EWkBtqT9qEQ0Rf1ejLpH3HrJUA9uKl 78S8Sm8om8OdA0Vbxaaoh6m.yM6EIpr0h9x7retEzjSM3NU.YWeJ4yPEmXcIhxheQI_sYC0gd6EN IFPP8OByH1ewGD9jybrIA85auDdfnYGuZS01sBpHyo63H7TbUcTjsWxhUF7q9vhzgxxl2yBxymFl 42N8U4aqfs1r_57lCbAR49YG6DjtxT1U2zQ_4eJT.uX712CFXLGpa1x_mkFQYyqu.u8FZU5QFFJ1 qsnP_JH34di2t4FZmBFVVLqw3E1HhpbjrIbfvijr5BeSFWUCw2Znnfbr4QnqSEOIAPPreopJ8GBB .R8oUvriP37VnQMjkfLsYE.0lEtmS5.oCfk0hWqLKv7NOrCSLqlxlZe9K.mMPx1gpOAnOm70xKG6 uGyqTureN5p8zM3c4RgbcLtlxmG5hCNHgVWAsxjeZwgfwtlfo.MHKZdcZKvpPvagZBFEqGrODtDP JKjiNJJqoHbDbXAcyNkA.KB5c9dpYBcPR74ZNMuIFS5Y5ErskLB3sbI3KNQDyZC6haC5.Ys8_6FD yFTi72bmr.b3wQvGCBexTKcLXAX0lDuy634yvVLIKc3dqlxvK3HRfdsMhL2l1Y9Kal.20DIHd5L2 8Z3S55XYT3BpKbq4d5Z71bXQxlrHnYONcyE7gXVp3qsKp43MBEqGe0HrdWfTnCZKYcUrkUOSNdvZ XhJ9o4cA6ETw2c9Ns.Loepie.Qnt430rpM6K.PZYkXnKlL6h2PB6sTpU4TzToBc5u3_KBq1TmOTP 3dfVg1.WgPJ2IvDkpnoYQcnammWX3zl6zrzTOLpeKjwZwT1DWNzlo7T4SCu7mb22ABKwxWOGxl7i B.pJPgoFC7dXfUclBJltXvmZWgZvxk.o_95h8 X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic316.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:25:51 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:47 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , "Darrick J . Wong" , Gao Xiang Subject: [PATCH v3 2/8] workqueue: bound maximum queue depth Date: Tue, 30 Mar 2021 22:25:25 +0800 Message-Id: <20210330142531.19809-3-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner Existing users of workqueues have bound maximum queue depths in their external algorithms (e.g. prefetch counts). For parallelising work that doesn't have an external bound, allow workqueues to throttle incoming requests at a maximum bound. Bounded workqueues also need to distribute work over all worker threads themselves as there is no external bounding or worker function throttling provided. Existing callers are not throttled and retain direct control of worker threads, only users of the new create interface will be throttled and concurrency managed. Reviewed-by: Darrick J. Wong Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang --- libfrog/workqueue.c | 42 +++++++++++++++++++++++++++++++++++++++--- libfrog/workqueue.h | 4 ++++ 2 files changed, 43 insertions(+), 3 deletions(-) diff --git a/libfrog/workqueue.c b/libfrog/workqueue.c index fe3de4289379..8c1a163e145f 100644 --- a/libfrog/workqueue.c +++ b/libfrog/workqueue.c @@ -40,13 +40,21 @@ workqueue_thread(void *arg) } /* - * Dequeue work from the head of the list. + * Dequeue work from the head of the list. If the queue was + * full then send a wakeup if we're configured to do so. */ assert(wq->item_count > 0); + if (wq->max_queued) + pthread_cond_broadcast(&wq->queue_full); + wi = wq->next_item; wq->next_item = wi->next; wq->item_count--; + if (wq->max_queued && wq->next_item) { + /* more work, wake up another worker */ + pthread_cond_signal(&wq->wakeup); + } pthread_mutex_unlock(&wq->lock); (wi->function)(wi->queue, wi->index, wi->arg); @@ -58,10 +66,11 @@ workqueue_thread(void *arg) /* Allocate a work queue and threads. Returns zero or negative error code. */ int -workqueue_create( +workqueue_create_bound( struct workqueue *wq, void *wq_ctx, - unsigned int nr_workers) + unsigned int nr_workers, + unsigned int max_queue) { unsigned int i; int err = 0; @@ -70,12 +79,16 @@ workqueue_create( err = -pthread_cond_init(&wq->wakeup, NULL); if (err) return err; + err = -pthread_cond_init(&wq->queue_full, NULL); + if (err) + goto out_wake; err = -pthread_mutex_init(&wq->lock, NULL); if (err) goto out_cond; wq->wq_ctx = wq_ctx; wq->thread_count = nr_workers; + wq->max_queued = max_queue; wq->threads = malloc(nr_workers * sizeof(pthread_t)); if (!wq->threads) { err = -errno; @@ -102,10 +115,21 @@ workqueue_create( out_mutex: pthread_mutex_destroy(&wq->lock); out_cond: + pthread_cond_destroy(&wq->queue_full); +out_wake: pthread_cond_destroy(&wq->wakeup); return err; } +int +workqueue_create( + struct workqueue *wq, + void *wq_ctx, + unsigned int nr_workers) +{ + return workqueue_create_bound(wq, wq_ctx, nr_workers, 0); +} + /* * Create a work item consisting of a function and some arguments and schedule * the work item to be run via the thread pool. Returns zero or a negative @@ -140,6 +164,7 @@ workqueue_add( /* Now queue the new work structure to the work queue. */ pthread_mutex_lock(&wq->lock); +restart: if (wq->next_item == NULL) { assert(wq->item_count == 0); ret = -pthread_cond_signal(&wq->wakeup); @@ -150,6 +175,16 @@ workqueue_add( } wq->next_item = wi; } else { + /* throttle on a full queue if configured */ + if (wq->max_queued && wq->item_count == wq->max_queued) { + pthread_cond_wait(&wq->queue_full, &wq->lock); + /* + * Queue might be empty or even still full by the time + * we get the lock back, so restart the lookup so we do + * the right thing with the current state of the queue. + */ + goto restart; + } wq->last_item->next = wi; } wq->last_item = wi; @@ -201,5 +236,6 @@ workqueue_destroy( free(wq->threads); pthread_mutex_destroy(&wq->lock); pthread_cond_destroy(&wq->wakeup); + pthread_cond_destroy(&wq->queue_full); memset(wq, 0, sizeof(*wq)); } diff --git a/libfrog/workqueue.h b/libfrog/workqueue.h index a56d1cf14081..a9c108d0e66a 100644 --- a/libfrog/workqueue.h +++ b/libfrog/workqueue.h @@ -31,10 +31,14 @@ struct workqueue { unsigned int thread_count; bool terminate; bool terminated; + int max_queued; + pthread_cond_t queue_full; }; int workqueue_create(struct workqueue *wq, void *wq_ctx, unsigned int nr_workers); +int workqueue_create_bound(struct workqueue *wq, void *wq_ctx, + unsigned int nr_workers, unsigned int max_queue); int workqueue_add(struct workqueue *wq, workqueue_func_t fn, uint32_t index, void *arg); int workqueue_terminate(struct workqueue *wq); From patchwork Tue Mar 30 14:25:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172699 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8D60CC433E0 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5DDC0619CD for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231622AbhC3O0U (ORCPT ); Tue, 30 Mar 2021 10:26:20 -0400 Received: from sonic311-23.consmr.mail.gq1.yahoo.com ([98.137.65.204]:46708 "EHLO sonic311-23.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231918AbhC3OZz (ORCPT ); Tue, 30 Mar 2021 10:25:55 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114355; bh=g5Yh0t0Afn9bSkRtW+yjgi1tpm/Hm7TbP7PeiMhsdm8=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=GeQZMhaL8EuSovwlNBnEl4SRtIy1UzXJ2Q91G9Cb3xelHcCOQ2/j1HHiVQ5EgodClvQm/yTYJhy7jIzMQ+jRy0exUY0ONPosHg3PyfZBqL+ReLq7XnYZAiM2N1GY3g0smNSFnH8ebUkXTA8f3IpK8EQEytZsjzNwtOU8JGKqZFP+Q1Ohb7UOzigNZ6DLR6cAkaePx/mkBwugcoMkzs9nMKmOLH4HWH7Pm5L0DhxV02nE0ciY0xTVH4VfKSWqj6JLdmI2NfvwPBBQbztZijlTtdAgj0shWP6B0UHeEex1HEYOId/kZKwbu25xWU/dNMbWk0hnQXnuf7nfXyBTSn3AvA== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114355; bh=aFDRp30xRtKwHe/nZkkSpjM1YJcKB9AxgIq9YKpgv8z=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=Uwf+xbmN+6MDc56MMTqJr5iteJyZxHRLns/ieXPTgFq08y/c16sWpg1w3QbFraMNa6u9N7vVJ/KQczclwxhQ3tKhxILe70LN6Tmu6BlB5tOwSlsxAm+5ZTIhg912NrADRYvLnX1eW5M2zwwnF3JCCjnX7rQUIbToiaHVVdVKn7hwqgvkn5DY8MMZkKlmb8fdBtn3zh5I6lgkLpMeSP+noDOO52vg23/L93G1N3Use7jNeDPVwaQQpHK6Zk/Gzr+T26LAAviQnV6N1m8LuZwPySPClaCv/LBII04zL1CeyluET6XBVHvhpt8lOi6di9Mx3xpvdPiYydHFuwZYPP6PIQ== X-YMail-OSG: X7hEIRYVM1mTaQET.MDNebYNTp1m974MY502dbhWFypx5RwSEjiLOQtnA4YXF6l uDQE0Yj6f3PX1puTJlhCBQ.ittzodb6lZIDmA6qhnzXChURCLKm9tRFOQF0kDVoAsOvOoY7wd6.m rlwH2ufw7adWcwD4ze3qwhGi9A5nxlzSXphqAXuzSeQQ0Rs0Ney1ZGWdpUnoMwDi2f6SIltbwLHC EmBdXc656AwHTxhK_Ay599ukdjimodzSDXwOIhwGop5A9sii.FlUPDiW8OixWRrCdMLbfS_OPUrE uVfDS_p.0GOt.lVW_2x7CbPWjxA51oYBslJ66FWIZcmqV93.T3wSeXBRRCXzaKQ4vzHFG89urwt2 9eB6XBbhsx94Dupr06G0La59aHt6LaIobUONosFhaloyyfOLjbWp8vtefnk.2klRLj_l_aS9qazg nwOvFf35U7go4w8.yr3NBdim19D4VAUJ_GFUJvIYdpIUeyroRbLuWoTvYdv_NCq6s2q1l6PdhpRM JxEPyQP7rLQr2_q3QcgLOzNvZxmV7HLNKXnj.L1RStLb8v852GpspCzIYqqMps2UWosHwX3TV3Wu V1SXR6_FRydDzMFa6ek40Npi5PAH3FHlrn3cpp3PdzGCFjhrssjgB8nUag9z3mBGG6qOVznN59eR vRYAku6ULP9N5IvuYX01C9lXeLldlQAkFd1v.ZEsHKooIZmmf4la7_WGqxXROcOuOav394J4_VVv ZfWTebVuEmy5A1V5LaDcUUlwJrCOGYxcKgXzVe8fcqqfTU6nFICv5388GSYc.BGoIulSVKVUtU3p W91XR9uDgJ1ZR6jODHzJCCm2QTEF5Q63B2EoveYErC6JFDtKL5Gu9bCv0_m7mOVKeBWkohNaUoCJ 2AOHVyRTD5rR0oAqDn50FdFKTWZWr8NhUGnXyzvV74D7x7rAWr5jjXvMphib3jhF8G9M3ZAWcYbx MN.aGX4D2MHkSM6kqS6lTN8FXCR2nZMOJWVhmXcupslhE_XX8Kb4LZcyHhOqR3496wlT6Cfiop9T kgtZLyORFDYSEeDT9BsSkYOR22tYflq.SIMNnAyqYawGJht3J2PFxP2rC4wBwS2maxluWSSlMGtW CVoPwwpLv8b9K.q.FopkiX2OpRhzhQODbX9HLI3HQcbQJgl_wjjlapBbFV1nbli.JouSI0kcPnmx _V5HkJ1PMQQunyIA31PV10wwVcC83H8uDB5LfDOfXJHj2AZI4U8z_0Gfqv4_6G5Lpijmlv8Khi1l Q8H3JhJusYHNodVWVLrxCOs53e5QUhtHrE6jNfvSJzWqC8NDRf6cvjWl.SsMrbg2pestUE9K3g2W y0hnTf0J5rQvSVnuG2A62Tqz3lV1qIqqHdW3cASinTQZ_oYTaTa2mxAhNAe7wj3NGFAynlx6Yog6 7FfKb4E1LZH9Hq4G54vbacr95rfu.dzPvvIf40Na8lhmvSX2.m1RRpgG9TY8DPoPljw2yuWdrSVn yJiU38ruI9HormtbImKYE3RPwa54kFDfWvKqNw5tKSkNhkgxENFBQzh8Jb7xMHzwBEMnmNL_CISB wIGI2FHsIrA8Ot.ZVTgKzGPwdDW.3z6pi1h6_ReUXCfFQnppxcgC_GqZ_iDqnr272w9C3gb6Su5O j1ZdV9sQHyUKhY6sAZZS3JkDdYXTVkeGfks_ojutgAndJyEjkb_WQqPbmnmt9RCBNUUiNQqY2ZbH aAv02InWxaZwiyMIRy_6Q6Uo3i56tFQaKGFRZs..sR79EmQqCUguYKN5vcXlfLCAGmSbDqb_fjdK I1C8lAzjvGtbWeF18B8Gtgg.YhMxgV3NB2DfrqHVyN3ar3MTEpb.vV3STeniwUwwGLZdGn_58qZI K0YGnKpmNv90iYu9ipJY7QFTPLZwEhnKaqciq22vOZNPvqvms_4r9i6dFdOlZZ3ETzbs2Se9MfqJ V46icTa889UAn38.r2H9jFr1j3Gc9yMFq.MBDtrRTarnIrZjqmnBaz8oDRl584aXYBxu3b4TjIJi bWMLW7Y8Nxa75ZSmFViG1VTHgZ5vd9Oz7Vc7hSdOEHdHxeQBJJNEZBWU_mMC3LrqbNlQLCH.p8r_ eBJwfzM4bDVyb1vxpUWDwa5YQ1NWXKpVCX8w8QJK34UpEEYAfpJLK.SH2ezc4fJX0TOc.GaCkqHI OJmjRuHqcyox.nGuVPZ.sfjtL1IHVXN7XRPBjYHh2dNp_QX3_fbo5dKdc3s7vHh0h2yX1gMH46tb tM0oS71UFp4S0hSXZKJ46WVcgcC5VtuPod5uAdQjA1Y6haylIcbCtHBa4n1UuQmQSQ4A6Jnj2OeB zUmk2ufny5bqjzffMrvKCD6x1nC9I_dHrtYcT7u9qWhEcR403ZJdTVh9KLj.Ra0En5.CPznw2Eur Cu0__DtCfsl9UbQyVjnz_sBRulJnG7r8Y7acIxJu1BY8Vm_n48UadnGr5bfLmSBJY3NguGFD2gtz q47Imp.mMe3RpcROBQudnRu4ad7m.b4jgEScQGVLGSMP5Kj5VcpbYTrV9TdaeQqKBKF1Ibr0Mf3f qd1Xot7nmvG4QuPI33Mj9nBNE.M_eVc.L2gRCUaKbkiKB43iRF.sc9FSv9SrUa_pFD08X42lYyrg QAP8FABMmnANOoxghZEeoigFVCORWmIbrgtT9VJUXSw-- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic311.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:25:55 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:50 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , "Darrick J . Wong" , Gao Xiang Subject: [PATCH v3 3/8] repair: Protect bad inode list with mutex Date: Tue, 30 Mar 2021 22:25:26 +0800 Message-Id: <20210330142531.19809-4-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner To enable phase 6 parallelisation, we need to protect the bad inode list from concurrent modification and/or access. Wrap it with a mutex and clean up the nasty typedefs. Reviewed-by: Darrick J. Wong Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang --- repair/dir2.c | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) diff --git a/repair/dir2.c b/repair/dir2.c index b6a8a5c40ae4..c1d262fb1207 100644 --- a/repair/dir2.c +++ b/repair/dir2.c @@ -26,6 +26,7 @@ struct dir2_bad { }; static struct dir2_bad dir2_bad; +pthread_mutex_t dir2_bad_lock = PTHREAD_MUTEX_INITIALIZER; static void dir2_add_badlist( @@ -33,6 +34,7 @@ dir2_add_badlist( { xfs_ino_t *itab; + pthread_mutex_lock(&dir2_bad_lock); itab = realloc(dir2_bad.itab, (dir2_bad.nr + 1) * sizeof(xfs_ino_t)); if (!ino) { do_error( @@ -42,18 +44,25 @@ _("malloc failed (%zu bytes) dir2_add_badlist:ino %" PRIu64 "\n"), } itab[dir2_bad.nr++] = ino; dir2_bad.itab = itab; + pthread_mutex_unlock(&dir2_bad_lock); } bool dir2_is_badino( xfs_ino_t ino) { - unsigned int i; + unsigned int i; + bool ret = false; - for (i = 0; i < dir2_bad.nr; ++i) - if (dir2_bad.itab[i] == ino) - return true; - return false; + pthread_mutex_lock(&dir2_bad_lock); + for (i = 0; i < dir2_bad.nr; ++i) { + if (dir2_bad.itab[i] == ino) { + ret = true; + break; + } + } + pthread_mutex_unlock(&dir2_bad_lock); + return ret; } /* From patchwork Tue Mar 30 14:25:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172701 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.9 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,UNWANTED_LANGUAGE_BODY, USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7EF82C433C1 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4AE7F619C8 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231882AbhC3O0U (ORCPT ); Tue, 30 Mar 2021 10:26:20 -0400 Received: from sonic312-23.consmr.mail.gq1.yahoo.com ([98.137.69.204]:45008 "EHLO sonic312-23.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232027AbhC3OZ6 (ORCPT ); Tue, 30 Mar 2021 10:25:58 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114358; bh=zhVB4g6LGbwzKv4Cl52Xh+NEV+mE7B3cm4bqqbPqkaM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=io50svib24yNcKB/mxERknuAj4akrWbc1EKfILwqZYSUmku9XscsUqDqC3r6bEvWLnrUoV3cVafecT98F23LwSfj+n3Vw60K3dkovHeS49TEiWVQsA7D4QDxQfGICWLFsERnLTHASBSTbevL9JmiM8IdlhnYVMFNM7ZU66HTmCUdI0rmoGTis/kv+iMhznWjUriwcbw6W49shShpZdwHm1YBUdx/V5+pvgLbgsgStGXPdFookANY0txc8m6CLyzxcZLNOAlTBcMkaybxBh+JLdjzFKBKkY70id7/215DnveyUWmLuxkIDSHuZ7ZIHKcU1vRTPL0LUA/vnXQ4cLtNdQ== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114358; bh=AThyH4QEFWmX6C0MsC3pgv08M4Pld9M+7t8Fd5t/lRR=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=XALguWIsjZXgvffbtLbLGexraQ1LwmGiCOBHqITScncGckQu4gvp4B5WAuhG6OLXjOPxmKGohcRd+bwdhERFFX2Fc5KmHF3vw5wB1czVyg2Z6wT+P2GoemK8W1+B/iDFmiE7iOVzrlWCQ/CFl7FU9P6m6EVUd2uMPHw2ujmwkYf6tJM0Z5o7AVT6ltFlOvv81kpRsSYj2cpR6US7AlDSV/HXxj724aQnInkVxAJBI6VeZfiHLCuqxLkhMWH+EOdQJ4UA9WuwtXuEcJMHx71ThK7cXFvqIbURM+A1Q/A6n+8aezsHwxeDb9Wq5j/+n8zfzyV695ZzyNaY+SPTFZBYrQ== X-YMail-OSG: iqaZvzcVM1n8UiUzBkGPq9tDIs7WeHDvsrskqkevogjwcRAp_k35QuWE9KffiAZ j.6J12OvDIQIIIUOROA1x1FElUoKOJOiD_b5l7rRRKNRe5TDXOtIcGyB9sRxCBxs59vpEQWC6COv NNHPcPbYkHoZ3j17FLWbh0Mb9jMz1nyh9U4SBQUejuE4z_38QnKfJN_4RpNHV9DNXOi1lqmoNKom qoF0eBKjYcKcPQEK_3iv2.zYvSKGaOgWY5XeUIVdxSLTX8GmJNd0hKy8LYN9yvfNePV8H0znbRcd GillGWjFUoz5BHbbn6a5olonsTZoL2JoJ_TfnmMKqTUwSoY3xfvJSxtMXeHBGgWW1m0yfRsAhn08 tAGr8Nz5J1C1PsAxTChU6UalpWD.EgMg.4ZCFScS6pSjXkIfgkgT8enxw5znMJGH0BjqfVBLE4TP wyeHFXVSS.epT4aaq73EUdP_CcGsEG8FVQ9JAUTrsi549f9S6l2p9.nX87BPslNJBRyon1m8Me3q VJSQAc0gSZF_RMJ9mOx4NA0kLiLSmXnW.Jy1rkdCj6GFOCEYo6Esc5DtZJqnhXOmG6KSUDL0pVRL DrRGogsW9YH7JOZqf84SYJbLAPpHJjPj2JERUwYHcZwFbcKJIzuI9Z7fsPiLc3AW7QNtxrph0vA6 B6AGx58ihXb0ku2KD7xXCiOvRbX8VUgF4s65wf37D1PZUyyJOGpNT7UZHJpxajsNlb.Mpuum5vWf 7nHKBophCqka1.JUClLBOsJD7YwyiqvLAyg.6kHGm8_WWLAsOTmp_Hb3i0f3OzlPNHDiJNG_u0ZR 5v7XeFbJ8EfKcy6YgcQaXosXGB4LlSf3J34zftnPXz.LB2FWvhlzehHA2vxIEbebH0tWwO2FL23J XUYtGmYkbPHE45HBsx._CRsXpEW7zLHzSp2ZjSmqWOU1pJmiJXGb_TtScWp3zeMak3MLgJgKPeXw U8ZwnTsCfJkl88Wnfgf5qVn9sF9_F5JGFz2w_lm1uSkFN3hn9lnFeXQxSHuhUTIZd6PJ2ZEjrLVN TJ1PjLRVPeh.bB9.CNwM2KMAQhIuDfaJcR4MmoMJJzyScEQqd4XXWrX2xyNcsSo0Sc3WUX3pd7Xi 4oGqrMUy9ceNE0X2XdMjkv6z_bmC2JGJfF2Sho0EJ_.bIjIzzVMA6SZQQz1k9VK5ZwnMxaRD_0QS GvC8QjGHejO60nQdWK34o4l3Dmf54qwjCLCziFTcKptiDYZN4TxYPfZ.g_YdZdO3uL_alI_GCB65 oNA19SiWs90DKDuV.oKwL5rICPwnGz0bqCrZ9XZwyPHn35BVCbQCkBim0j_xESIqkaCWDRkpq75Q EEHhfDkIZtHCc.UZfpcpWK60rFJSPN4fD3PsmgeWEmwcbq0_Fscp9zQ4YWZLhz6ipk4U_crGBNVO TSRe0ch6Ajbg0G11SEownZ_TxssR4mM0tSBpCymwgHhy3tBQVtaYXhuxIFEk0SjL2QvMAV_vGmCP IZuYkTi5bkpbkmEWzsW2LS7kRzdNFgexMf3m3uJ.mJCQT4K97VeTT.RaE9oMWzBDM0TDz46Nny7N 2JU0Mv5lavW1tjcSA8eNZMqcxDXp4CDpH8dpKjE0EEAHpy_1rKYInCjUo4cC3dxLEfN7dRs_atD2 7.1WLYPpOOh7jkMlqLgs8C0ypBn1cvFdxc69aJDyxabf0kGsB41rTbIIdf8zB5R.wrtDJPbzt7bD wybqM65QTm3RACjxusd_u1IlZwycmOPi2D0ITlfNi06_ZDYBuW1q_t5SmU90j_vRYuXoHtPruwrA s6wUmeVT_.gNXPb8FZRyacVFiO_sPv_w5gh0GsdcPIAEKf3ZzcfwNsA7LZlSYF16Jj5trRmG96V3 ZoLJ8UXIKVRoFTa1a307ZX1t6ZKO61Mjl9MEg97_dUU8b1z0NKiPco6y_BNdGJr.wt.zA5.tR5un iIApV.1ke.iMQErs0zhjxlDyMcBCbo_0mGoolcogEtaddepaZ62i_WJe4TT1UHF4Lwovp0eLfssL fLazqMyhY8wh5lX2hd33U9wR4PPQrG1e76lGCBG4v8bS9HDjMFVuREeaNUzsnRnrKfc1OqmMKtbM cr3pc6d6cyHl5gTwCLGa0jSuA9s8XY01ng1dWjBiVeJh5KeMjOmUpge1c5OjuH1Z3hkQ0kLDXl0o 8g9Ef8j2.Mm3QiV.EqyUbwi02vA_KyUTcQkpEvWGrf8dHlgrSmG0t2SuCuyt6jlN3xQcjgtOGsTn GTOyCksmcGqY3JilXLgVQzujIh_tbzg_lb0F8dh1jfhlPN54VYmSe.Uy4Hg4mMRJbLF87fEN61pr GmSMDXCiWSxjXII8NsFMQq8pPJuyLWnIQrFdzwunOGyHNObQEaJNEJJgFqtuo8IpIif522XWikz2 VZs5pe5YKfROzNQzlwu0HRGQhnQfnXvAP6gkFmPsqbRWFJ8XfMoc04CAQZvUU7jAy.TOscTaHcQP 8MHt2CtbxEVDK.7vsdd7c.I1VwFQBCCRh1I2ue1tRTxCRzY2pmwMLhDX2D7uY0DZhVB3JDOb0ZDe dFTLauJ2K7bemrfbHkQOjF5L5YR2mijpKObLW5X8jt4tvWruUGdEMYOM.TyWCjXOOiOOvtUnPOGQ lacaX.QbZuRGuVFq5lC2QHFsAZknTU8vBJVUTr4I7u7JxbimJJPJol8wnSm8nfExtNpCKXZiLDC3 oDemUYAnXVMjmTZojrKX4ObievnjXOyNZ.4KPwdea X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic312.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:25:58 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:53 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , "Darrick J . Wong" , Gao Xiang Subject: [PATCH v3 4/8] repair: protect inode chunk tree records with a mutex Date: Tue, 30 Mar 2021 22:25:27 +0800 Message-Id: <20210330142531.19809-5-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner Phase 6 accesses inode chunk records mostly in an isolated manner. However, when it finds a corruption in a directory or there are multiple hardlinks to an inode, there can be concurrent access to the inode chunk record to update state. Hence the inode record itself needs a mutex. This protects all state changes within the inode chunk record, as well as inode link counts and chunk references. That allows us to process multiple chunks at once, providing concurrency within an AG as well as across AGs. The inode chunk tree itself is not modified in the directory scanning and rebuilding part of phase 6 which we are making concurrent, hence we do not need to worry about locking for AVL tree lookups to find the inode chunk records themselves. Therefore internal locking is all we need here. Reviewed-by: Darrick J. Wong Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang --- repair/incore.h | 23 +++++++++++++++++++++++ repair/incore_ino.c | 15 +++++++++++++++ 2 files changed, 38 insertions(+) diff --git a/repair/incore.h b/repair/incore.h index 977e5dd04336..d64315fd2585 100644 --- a/repair/incore.h +++ b/repair/incore.h @@ -281,6 +281,7 @@ typedef struct ino_tree_node { parent_list_t *plist; /* phases 2-5 */ } ino_un; uint8_t *ftypes; /* phases 3,6 */ + pthread_mutex_t lock; } ino_tree_node_t; #define INOS_PER_IREC (sizeof(uint64_t) * NBBY) @@ -411,7 +412,9 @@ next_free_ino_rec(ino_tree_node_t *ino_rec) */ static inline void add_inode_refchecked(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_un.ex_data->ino_processed |= IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline int is_inode_refchecked(struct ino_tree_node *irec, int offset) @@ -437,12 +440,16 @@ static inline int is_inode_confirmed(struct ino_tree_node *irec, int offset) */ static inline void set_inode_isadir(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_isa_dir |= IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline void clear_inode_isadir(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_isa_dir &= ~IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline int inode_isadir(struct ino_tree_node *irec, int offset) @@ -455,15 +462,19 @@ static inline int inode_isadir(struct ino_tree_node *irec, int offset) */ static inline void set_inode_free(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); set_inode_confirmed(irec, offset); irec->ir_free |= XFS_INOBT_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline void set_inode_used(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); set_inode_confirmed(irec, offset); irec->ir_free &= ~XFS_INOBT_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline int is_inode_free(struct ino_tree_node *irec, int offset) @@ -476,7 +487,9 @@ static inline int is_inode_free(struct ino_tree_node *irec, int offset) */ static inline void set_inode_sparse(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ir_sparse |= XFS_INOBT_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline bool is_inode_sparse(struct ino_tree_node *irec, int offset) @@ -489,12 +502,16 @@ static inline bool is_inode_sparse(struct ino_tree_node *irec, int offset) */ static inline void set_inode_was_rl(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_was_rl |= IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline void clear_inode_was_rl(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_was_rl &= ~IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline int inode_was_rl(struct ino_tree_node *irec, int offset) @@ -507,12 +524,16 @@ static inline int inode_was_rl(struct ino_tree_node *irec, int offset) */ static inline void set_inode_is_rl(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_is_rl |= IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline void clear_inode_is_rl(struct ino_tree_node *irec, int offset) { + pthread_mutex_lock(&irec->lock); irec->ino_is_rl &= ~IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } static inline int inode_is_rl(struct ino_tree_node *irec, int offset) @@ -545,7 +566,9 @@ static inline int is_inode_reached(struct ino_tree_node *irec, int offset) static inline void add_inode_reached(struct ino_tree_node *irec, int offset) { add_inode_ref(irec, offset); + pthread_mutex_lock(&irec->lock); irec->ino_un.ex_data->ino_reached |= IREC_MASK(offset); + pthread_mutex_unlock(&irec->lock); } /* diff --git a/repair/incore_ino.c b/repair/incore_ino.c index 82956ae93005..299e4f949e5e 100644 --- a/repair/incore_ino.c +++ b/repair/incore_ino.c @@ -91,6 +91,7 @@ void add_inode_ref(struct ino_tree_node *irec, int ino_offset) { ASSERT(irec->ino_un.ex_data != NULL); + pthread_mutex_lock(&irec->lock); switch (irec->nlink_size) { case sizeof(uint8_t): if (irec->ino_un.ex_data->counted_nlinks.un8[ino_offset] < 0xff) { @@ -112,6 +113,7 @@ void add_inode_ref(struct ino_tree_node *irec, int ino_offset) default: ASSERT(0); } + pthread_mutex_unlock(&irec->lock); } void drop_inode_ref(struct ino_tree_node *irec, int ino_offset) @@ -120,6 +122,7 @@ void drop_inode_ref(struct ino_tree_node *irec, int ino_offset) ASSERT(irec->ino_un.ex_data != NULL); + pthread_mutex_lock(&irec->lock); switch (irec->nlink_size) { case sizeof(uint8_t): ASSERT(irec->ino_un.ex_data->counted_nlinks.un8[ino_offset] > 0); @@ -139,6 +142,7 @@ void drop_inode_ref(struct ino_tree_node *irec, int ino_offset) if (refs == 0) irec->ino_un.ex_data->ino_reached &= ~IREC_MASK(ino_offset); + pthread_mutex_unlock(&irec->lock); } uint32_t num_inode_references(struct ino_tree_node *irec, int ino_offset) @@ -161,6 +165,7 @@ uint32_t num_inode_references(struct ino_tree_node *irec, int ino_offset) void set_inode_disk_nlinks(struct ino_tree_node *irec, int ino_offset, uint32_t nlinks) { + pthread_mutex_lock(&irec->lock); switch (irec->nlink_size) { case sizeof(uint8_t): if (nlinks < 0xff) { @@ -182,6 +187,7 @@ void set_inode_disk_nlinks(struct ino_tree_node *irec, int ino_offset, default: ASSERT(0); } + pthread_mutex_unlock(&irec->lock); } uint32_t get_inode_disk_nlinks(struct ino_tree_node *irec, int ino_offset) @@ -253,6 +259,7 @@ alloc_ino_node( irec->nlink_size = sizeof(uint8_t); irec->disk_nlinks.un8 = alloc_nlink_array(irec->nlink_size); irec->ftypes = alloc_ftypes_array(mp); + pthread_mutex_init(&irec->lock, NULL); return irec; } @@ -294,6 +301,7 @@ free_ino_tree_node( } free(irec->ftypes); + pthread_mutex_destroy(&irec->lock); free(irec); } @@ -600,6 +608,7 @@ set_inode_parent( uint64_t bitmask; parent_entry_t *tmp; + pthread_mutex_lock(&irec->lock); if (full_ino_ex_data) ptbl = irec->ino_un.ex_data->parents; else @@ -625,6 +634,7 @@ set_inode_parent( #endif ptbl->pentries[0] = parent; + pthread_mutex_unlock(&irec->lock); return; } @@ -642,6 +652,7 @@ set_inode_parent( #endif ptbl->pentries[target] = parent; + pthread_mutex_unlock(&irec->lock); return; } @@ -682,6 +693,7 @@ set_inode_parent( #endif ptbl->pentries[target] = parent; ptbl->pmask |= (1ULL << offset); + pthread_mutex_unlock(&irec->lock); } xfs_ino_t @@ -692,6 +704,7 @@ get_inode_parent(ino_tree_node_t *irec, int offset) int i; int target; + pthread_mutex_lock(&irec->lock); if (full_ino_ex_data) ptbl = irec->ino_un.ex_data->parents; else @@ -709,9 +722,11 @@ get_inode_parent(ino_tree_node_t *irec, int offset) #ifdef DEBUG ASSERT(target < ptbl->cnt); #endif + pthread_mutex_unlock(&irec->lock); return(ptbl->pentries[target]); } + pthread_mutex_unlock(&irec->lock); return(0LL); } From patchwork Tue Mar 30 14:25:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172711 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D849DC433E4 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A70C9619D6 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231918AbhC3O0U (ORCPT ); Tue, 30 Mar 2021 10:26:20 -0400 Received: from sonic312-23.consmr.mail.gq1.yahoo.com ([98.137.69.204]:40382 "EHLO sonic312-23.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232038AbhC3OZ6 (ORCPT ); Tue, 30 Mar 2021 10:25:58 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114358; bh=6T7MFQGZWvo120ENbTkrCIAA6M7ISWh8ieg+g5XrEvg=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=t36XSjB0AZmXylXTZe2ucJYOibt6SIGvvPZmb8xRvAOzIyId2nihU9B1LdTWkylwVqtQc7/okRtuPhUN7+JqlD88cXnaWE9aua0waokerbUU/lWBAP8bUTYzZUmlZ7oqBo8NhrqH+xSmVI6Wm7hztsb0GPC6jMzqLC9DqGDSdw+4uGge4OqckJJrW8ZPC0wKY28+x5aE6ujrkfAkI4k2N1+EdnnDDp6/Js4yCCvObWJo3YXIG+JUcZml9+CY+pVaU1rtc3PIDbJzbCMhHgJmL2wQfP4nN091CVk7lYB85xvecr/ZjxTzhegh1RIcI5+BPvTEYA3OJtxFaZ1dM5jGGg== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114358; bh=8dZi0vV2P36nZdiMeZo8DZv0KEvEAKcTGgi9ggDXbbU=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=stCjc/bzmMGnJlqmoXyzWEzWczAjWVRprvG9DathvXlPSmlUXqDmXl7yVft4odzFOjwWrvnodSH1zynXNkDypfThPjK+st8yxFPGsyu6B0lfRm49HsEDJXCfJi0EyB4qJJYUnKMQs4NIiorJsZxi8/DsPl/4L3d1cxppkd4QfyRDAVT1y9MbKH65UPGlLOt/T7g8Y7jYEuWaMyNyljj6cYSI0kWYwMZq2NGK52Pxf+qLvZsAcXxrc3XLvt2B9A7jSRh+HqB8LVpcvr8qMP3dPVbcrouogWoAk9pGuyYWpmHqJKP00526i1iedE6CNRuRSsywYZ5UvNorD/okql9ZNQ== X-YMail-OSG: 9yaXsgsVM1m59mZ_l5qSAFJWtRkPDJTaLTqCjyQGxHQNSGXy4XM0.RxtC.WQ1tM mcpoQGeHQlHxcwytm8nYKciocif4y4m0nLe_Gg68HOXWTlaSPH4O86mxXu_8rlW2ICCQ9DqN69eC UmDuyy6lpOlfuxXlstSAr.5Bf60JDwcf9HOuo7G1YHAtu8Qjzy38AIeROJ.mOyWvmqrsPhQ2YGoj IoVZVCNoJsSBiZ8jfOvLak00.jqsedMOPbPvhg_P9zazZbQxyj.M9o2sq2YQwtZZxVOuLKRpvNzg 7okQTkxsusMhGXDS0dr7G7NlWGY.EaNa6_9p9A1rvTKI0yJ4zk0hbjMX53J6yIA3dvk8tK422Luq v6tpmEKxxpPuFYxS.ihFx0t.Alhs_3elsV35KQSFiM2Khw18zsg_RspJr0512YBoQEZlCOmVGDOY xxjkNVcm3FpCHPur4HpE26W0JUYq4zHOGQdp3eI.Jduul0B4K0xhxlPGKbC2NVclq9.Mmv7KaiqD xoWR.ItQZye22zHx.lwFV.rnzybdLP.p9OpfCU296jDaMYQ9uIjcpujfblGBL5P6Fi_MgLWEAOSo VtKldnHZPiOYjVct4RBbE1JbWaGpidosW5Z0KPurwv4vVm4klszM4Kvur__84apwcXibYs3_36iI GrWcOOHQS6kbri.AvG2R6ap4nduTC1xyG.bbHFtQXslatTqXrE.itFQDp479aWUSKhTYavgiDmrq TFGgtNdJNLcW1DQwluMMf863hq9vyqQG8urXkQGO1XosBv2WIsR9JQIr2e6zBcWxYc4Tse4ZIrYh H66g_4783QK2Koa2ivWwg.6MAqrJuwJPuM.XHPxyy9tUk8teIvSt18dRWDhoutzjj19seZkxh_d7 L_uSAwUcUfG06ee35lpQXP5s9UuZL2jeA.tXjwlojYUyu0ltCGhf5q4UeR4ODIcEiyplPnpLCteO bXPAx6Wu2x5kvrx4brhxcTZjXuYlrYAwNI_azniqK6jHxMIvcrGociVb98VFG5EhFCgxDRqnB8vQ esQqVnrFW0vo2OqxYyB4bSgV6GIZbWX_zknvBy4B99xgqhh49B_NttwhfH8u8AW1ss3B2EySx14T Lv9EweoiY5FPcbtOPE1E86KxFmspLKCGp.ucw0uvDdIFJA7csmqw72_KzPB8rnnVcUyx3VHta8GU V1FDYLnH.i6KNRto1d4SZIEkwj5tPXs5V0s7OCFCou9L2nWJUKPo8w.Hjz06QXHwAhsTPXcXM9eM adXA0vk1.BZFIzVhROUV7sqQ_68goT9zvgNmud8lvkBIBbcsev0JbE2nxXHfNLotznohmN3afE0w 4kd1Oa1w2.AqGlDzPZKixy7rqbSbcUjfefkFvTb.FNIiq3sMnLp1XyuOv7hK4gG86FEA4MFckHxi Kzrfyittw56TGm2domo2jee01OXn5YC9qA6lDWSmfHGtZrbd_LNazjKcieI_4kR7tgnbthWW.7aD AyWIy4Ho192AeW808eR.j1IIKQevJ33jn6V60uh6HabM3zhosR0ALICNSLzO_2YkO638bzHyVYa5 jvBUHZo3pchu32XQ6.vd80NheEc0iq93ivRPUdhrVBIItzkbXS7wkY2RedENiO81Mx_bphK0Ny1i aeh0UOXReXy_QAHi0xpI_x9D8zwDPrXS7h92qOxDSfHfopo2laMfaG1f9nKgIyDtEeCbXT7iUHlu 3owM8sN0W9ptBtpPCl_P5ivfj6438g9tOiA6WTaJcgzgFjvvcue2RxxNptiNQeEzJ.6CfQyNH4yI m5ACYxqaKFqJQTFjrXPB6dae9s7OkZteJiU0zCmDf8ypwMp2qFmidu6QpO5asqaYaij7LnjsMWUQ z4Ra3vfJLmnp2N7J1PpJ2j1vx0g0JwizQen6JpBcDy4TsRNbFrepqIIzLhopjsEaNDAXZyMKFJJm 4xRR5Q_TpkJHUgn9bN52MRa5Ts5z.evOiX_zjRj.oQKdZsaB6j08vCGtjakSii.iiLomLyfXWz6c BwRJqT9LZL_w5h5_LS.2a3In53UMNeInYUlTkCRr3hz1NayB_agugvht8aKo9KexshRTufSh6LNn hVMZYF4FQ4HCjDf4ScNhCn0Ai.01bt2unkoWXEhA8ANGA7VHn7nlC_QUb7HGGhZaznRxhhO0.1iY dH3bkFTrCvYAT.FU7x7vyI4Akj7SUUSBIQ2HmhJ9.43lSIlQk__X9x_w9A7u.Ho_B.1Vb6lby9GV 8SKSdAqyboHuhhNZDKZzKTOyKy3rDAggAXPpwTumfh67iR1IaHbqFCHIvHAjsLv9wlgBvEmsY6O0 j9EcsEeqFIJe6HAxX3UvSdm9EAR_mtrbQDAuUAMUhUP5cW0Jhs0CHGEaYm2d2t8yOI1r.l9xsuEw 53oo5Z1Em1Z6QO2sdMbAmk8RN5NtOJ4DKO3BMYQxaCNE2Vm7tawsRKKGnroDGg26.V0s4sHHLOzZ lG.2U7xYCzTzXA1pGImyD7NhP4YD0AvpGUAOVHGBR69iCFtgNX_tEcsIO4qwaDLpmyeLIknQf3i0 J1oZBytAhOyXn.07GR6atkR99giwogw-- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic312.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:25:58 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:56 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , Gao Xiang Subject: [PATCH v3 5/8] repair: parallelise phase 6 Date: Tue, 30 Mar 2021 22:25:28 +0800 Message-Id: <20210330142531.19809-6-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner A recent metadump provided to us caused repair to take hours in phase6. It wasn't IO bound - it was fully CPU bound the entire time. The only way to speed it up is to make phase 6 run multiple concurrent processing threads. The obvious way to do this is to spread the concurrency across AGs, like the other phases, and while this works it is not optimal. When a processing thread hits a really large directory, it essentially sits CPU bound until that directory is processed. IF an AG has lots of large directories, we end up with a really long single threaded tail that limits concurrency. Hence we also need to have concurrency /within/ the AG. This is realtively easy, as the inode chunk records allow for a simple concurrency mechanism within an AG. We can simply feed each chunk record to a workqueue, and we get concurrency within the AG for free. However, this allows prefetch to run way ahead of processing and this blows out the buffer cache size and can cause OOM. However, we can use the new workqueue depth limiting to limit the number of inode chunks queued, and this then backs up the inode prefetching to it's maximum queue depth. Hence we prevent having the prefetch code queue the entire AG's inode chunks on the workqueue blowing out memory by throttling the prefetch consumer. This takes phase 6 from taking many, many hours down to: Phase 6: 10/30 21:12:58 10/30 21:40:48 27 minutes, 50 seconds And burning 20-30 cpus that entire time on my test rig. Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang Reviewed-by: Darrick J. Wong --- repair/phase6.c | 42 ++++++++++++++++++++++++++++++++++-------- 1 file changed, 34 insertions(+), 8 deletions(-) diff --git a/repair/phase6.c b/repair/phase6.c index 14464befa8b6..e51784521d28 100644 --- a/repair/phase6.c +++ b/repair/phase6.c @@ -6,6 +6,7 @@ #include "libxfs.h" #include "threads.h" +#include "threads.h" #include "prefetch.h" #include "avl.h" #include "globals.h" @@ -3105,20 +3106,44 @@ check_for_orphaned_inodes( } static void -traverse_function( +do_dir_inode( struct workqueue *wq, - xfs_agnumber_t agno, + xfs_agnumber_t agno, void *arg) { - ino_tree_node_t *irec; + struct ino_tree_node *irec = arg; int i; + + for (i = 0; i < XFS_INODES_PER_CHUNK; i++) { + if (inode_isadir(irec, i)) + process_dir_inode(wq->wq_ctx, agno, irec, i); + } +} + +static void +traverse_function( + struct workqueue *wq, + xfs_agnumber_t agno, + void *arg) +{ + struct ino_tree_node *irec; prefetch_args_t *pf_args = arg; + struct workqueue lwq; + struct xfs_mount *mp = wq->wq_ctx; wait_for_inode_prefetch(pf_args); if (verbose) do_log(_(" - agno = %d\n"), agno); + /* + * The more AGs we have in flight at once, the fewer processing threads + * per AG. This means we don't overwhelm the machine with hundreds of + * threads when we start acting on lots of AGs at once. We just want + * enough that we can keep multiple CPUs busy across multiple AGs. + */ + workqueue_create_bound(&lwq, mp, ag_stride, 1000); + for (irec = findfirst_inode_rec(agno); irec; irec = next_ino_rec(irec)) { if (irec->ino_isa_dir == 0) continue; @@ -3126,18 +3151,19 @@ traverse_function( if (pf_args) { sem_post(&pf_args->ra_count); #ifdef XR_PF_TRACE + { + int i; sem_getvalue(&pf_args->ra_count, &i); pftrace( "processing inode chunk %p in AG %d (sem count = %d)", irec, agno, i); + } #endif } - for (i = 0; i < XFS_INODES_PER_CHUNK; i++) { - if (inode_isadir(irec, i)) - process_dir_inode(wq->wq_ctx, agno, irec, i); - } + queue_work(&lwq, do_dir_inode, agno, irec); } + destroy_work_queue(&lwq); cleanup_inode_prefetch(pf_args); } @@ -3165,7 +3191,7 @@ static void traverse_ags( struct xfs_mount *mp) { - do_inode_prefetch(mp, 0, traverse_function, false, true); + do_inode_prefetch(mp, ag_stride, traverse_function, false, true); } void From patchwork Tue Mar 30 14:25:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172705 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C4B51C433E3 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 93F97619C8 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231939AbhC3O0V (ORCPT ); Tue, 30 Mar 2021 10:26:21 -0400 Received: from sonic308-54.consmr.mail.gq1.yahoo.com ([98.137.68.30]:42338 "EHLO sonic308-54.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232050AbhC3O0C (ORCPT ); Tue, 30 Mar 2021 10:26:02 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114362; bh=jQFLtUMpum7DIShm1LZrwbac5hctvXo9TuoGTQbQLxQ=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=eGwAMIA34O3nFKexh4t95uEG1styvd+ohhwmVWOg3GqxyF5fvWcDCdcKTu5VowgOl99lntXLe5vfv/ZqwHSaec5cJVcJiC7rzuANmbQdiBOY/6qNglE/gXAks9duAzwf3OmMJoIZuyJedjHXw6o3tGBV1wYu05a4XeN47T5H639LcLbrpMr2v7D63ykTiKQbyw2DLjuy59lA1o6lnvEOm0XDLIw+ODurRdBuD4R+1qS84BoFsgoi5TqKATajVaMV3YNoNhnlghkziEH+ok73jkbkfqkGl3NGczTXhYcBxoZsYjk2NmLTbQtx1Th7fe8MvwHvI+n4CHmX9gCiPLHKTg== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114362; bh=jEg4Heqb7kfan2EkVwI/z/a0gu3wKmKJkh0orzOVSVz=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=a175LXfHur4vubWEZvWNBoUqnyYoejaHqTkcvMmnM8URDWCoL8ZWgaLG3STwBuhLd4aQzCzlQPzlUyaRX0sxfLgqUVqnEwn73Xvp23l6njp2lwBKwjh25rFRcyO+/l8POXAHkdZQYbx11SupHE/SpBQjZgq1YVVAEy+2nzjkV3ZmbgqaBmq0O6UyTEebZJ26/RbhWVrtltdVXLxkR6EnceCYFf0Z1ltb/57VXyO1CK2Z4L+VuUtqHBCUtHIzuDLYCN4MQv7qg1jb3dQ+8gJgV5t+8dUlECB/Pe+vd14pFcT1P+MyNH18WU0hrKpGoVpxV3kE04V+jWQp3xMv+489HA== X-YMail-OSG: rNQJmlIVM1kqWm0BgdOAR2npospsgNL2AZl6dbIzZreiQijLqTdQG2Kd9xApRz9 hppSuYDOYE5JXbcZ8FL0ZjoAKIE4a0PGgN1uKYhVMs2eMZ659niYtilkmxAtLXJoDlA_B5N8spCK y2MC8mdmkdj6dalHkyC1p0i8YUvymHd_BPQyXgGidoB93GK1F1uaR8Kds4cmpn_cMBAQU8jm2gyY d_itrTr7saYWAQoc.INQwS_pKeR5_aWaSE8kNUJyXATuX_JsTK9e.Mnnl6E7wk6Ry24_RRLT7Dzd 0FG4Kx7Txl8_TGLQCspb2x7FtX..1aGWAg.1UMlI2t1nkOxZQ3lhaZShcASrBFOcYlXL_hTswiAd j.l9oCp3QdNsPFCT8tRtznGcWzM2ZnKsdnD2UPeGjEsj5nUQzL4FCDfXep4mZuILAWqA5nosV1D8 ESVhkOFgaUDuCxN0BkRdf1_rmayCDdpCLMfX8OLkyeIkfm3YKHaSkOr23X8LMLb2_wg0gamoZeo8 VfYHNo4SsuX3K1Tf9LgMoj8WwzDVVgrkoiIcQOeOyAC0s41hyMvq8cqGU8AyZ_2VPyVTRvfaUz6k eOSqYzR81geDRHQ4uSmNp2xglfxhNySsr_fCcBpVHaxSZqr2.oeTKR65febK1nSwOvOlsFS3Y_W3 e35xEZnrFcHXuiDvINrB62wLughhsej6CpiO8swLiNTL8A2M8Q7Cih_0ME4XbGfdv8OShFzPeBAV lAPtSjXnoxH9K10Jv0P9zx37M_TY0TdbC1.6vAVzu2RPb2J_.U7byvxiM.yEUfbn2k4EQvDFQyfl YKZtGOAocMtYhCFQ7rtIGcSbadr9mYLDKVJSMuPETrmP56Yw2DUEWVohq0J76VlNawMkH1CvMnsN epGlZhT2VMaiPhwbqn.eopkMeG8TMxO6S5oGrER.e2z1E7Hq7WAwFTRfBMzG8eJa4L5Le2xH7hHi _gjTP614Zu5Hyj0X.qTnZHMVc_I6m8Aj9a3fDsVkpMMDknCUzxTorek1J0oufPqO5kA61X7py4ft .arQt4UCtIBW1DEaCk1AlWK70hJMCi.ii4UpKpDpARRqf.D966r8jDFeoF3GI6o6KRFswi4Gp7.6 siy5T7I3Q3xbTKgun_MAnb1ajnoE6PtsZvZ_Bkzesera4gsAdvayGXTjsKEJf9o6EmkwcA8UOeCj aTMF6m1qEKvA2NVmYnawHXO2VhXTLpcBFkzUXGEdsIdDn1Z9P60nzaQHTkf5OgkOMkUPDi7gz83p mLUXjhtUMEtbHeP25niNeBNMllQIINlXLoU5eR2_SA6qBr8wvQcEb3QtvDbKKDEVcBovcBeDvsQI OvU5_528LK1mHVaOKylllO7BUA6BncOqlQB3CpNQWh2ae0ep2HVdNvvOZwrstH2GirJpvSa_omN7 isDWa9OiuEnly1urCyRnUszyFwd__JM0E6u4EaU6uJkZ2k4JzH8EzJOjCDABgHItzlJEOnOuRbFh Silj9cdvwVMkMH.6ZaDzE5D56ejyzO9WNmcfF30mORHfknKO1DcugO2eQ7uM3HXPWNTMJWARRUDH MEWofAdWGO7hIIUHCp.2M.XQegujtkWTTrgIW_Mxvo4haIU6WijGIpFVOlf.4yqrYgxgjfiX5T1O V58wHFMdKXGmk2b76QYG6FUaJ4VHKyr0N8JDEGLvpxsCxWiAWdbp6i6SwU9CZEbjFPaV_EjnM3rO HsQxX_n9vworgqKfj9xEqruycgfMDe9fnPDMOuBYevX_cEA91ZcRobAaKx5zSLL9NI0qaJDROsFi QnVRoyJTPeSpB9JNorgBcoBjRAlUG5BqPhOtbUOYVPDyy4fdkqADFjzeEfZO3iu3v9WguerLZuSC kBksDJTIu0yWr62Iccpp82PhN2DrCwj4HikeXt9sA9q2rT_ZJNgDbL6iDBhr28W.EK_sueYEVoyA sWMJwB_Snaxk0AflRMNS7kciRvmnLVLU9BX6p7jhcTrDd8IbjOgxK7o_wD8ilYvxaAfE1KwmM4nV lbDx42SesAduKL7ldVT5zwv7aW4_qS3qR9d1.06krQEKlgDgBLvB.xIfoxLRU1yAi.hcr9k9tCbm lBfM3fOJLaZnaGi59cfCj8w2Ql6jGZCNCQjjp5Z0Qp0voBhsNnbGdAq.lodOi766g2y.7CSsYmlA 5gsUxCTa3sJPQ6LDoJk2e5Ga5HJZIWkoeHf_kqEvA1FWcK6u9bk8TncbSmNkXU562XR1_dBu30xF hZujT098J7sUAlBf7OE0sai_8NRR_MsyggOUyrWK.C_PnUH5qvAoklsCTpvJWkDSKhG.Rg386Qh_ RXdmu1m5Af.MICnqe_UQ083ZI1KdSARstL8puZSghC863GgK3hl6QlHtiPDS4gyeEXFXL1.1hon. yswdTzWSB9x_lmRWmoKVDOnISyL.UXDay.HlxrvVMeKhpZOLfQH1noSetVwJPANDLg4Sr_PngPJC .NBSom_TM4qZb3HJHvAN_4ym7O3bRMON7_CnSlMdCXLW5bYij1zBzDqJ_kPgN0BwNiMqgwirqhlz p0eG6kSIKvFtWiqQ_R5khAugshVWt_uYjl6iE8tp63jpJ9jwLizuuI0Gy2ZwqvnqcXrhZEOuIEiM .5TjiWq7b4NmccrGD2WFd3MzSkoKD31DTi3CbGRR3kTsn9Iojhh3OqvA9pZCKLTX8NEiGCJsWrpT eA3ogMQ3TC4qOm4PlCGOxg_g- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic308.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:26:02 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:25:59 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , "Darrick J . Wong" , Gao Xiang Subject: [PATCH v3 6/8] repair: don't duplicate names in phase 6 Date: Tue, 30 Mar 2021 22:25:29 +0800 Message-Id: <20210330142531.19809-7-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner The name hash in phase 6 is constructed by using names that point directly into the directory buffers. Hence before the buffers can be released, the constructed name hash has to duplicate all those names into meory it owns via dir_hash_dup_names(). Given that the structure that holds the name is dynamically allocated, it makes no sense to store a pointer to the name dir_hash_add() and then later have dynamically allocate the name. Extend the name hash allocation to contain space for the name itself, and copy the name into the name hash structure in dir_hash_add(). This allows us to get rid of dir_hash_dup_names(), and the directory checking code no longer needs to hold all the directory buffers in memory until the entire directory walk is complete and the names duplicated. Reviewed-by: Darrick J. Wong Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang --- repair/phase6.c | 101 ++++++++++++++---------------------------------- 1 file changed, 29 insertions(+), 72 deletions(-) diff --git a/repair/phase6.c b/repair/phase6.c index e51784521d28..df8db146c187 100644 --- a/repair/phase6.c +++ b/repair/phase6.c @@ -72,15 +72,15 @@ typedef struct dir_hash_ent { struct dir_hash_ent *nextbyorder; /* next in order added */ xfs_dahash_t hashval; /* hash value of name */ uint32_t address; /* offset of data entry */ - xfs_ino_t inum; /* inode num of entry */ + xfs_ino_t inum; /* inode num of entry */ short junkit; /* name starts with / */ short seen; /* have seen leaf entry */ struct xfs_name name; + unsigned char namebuf[]; } dir_hash_ent_t; typedef struct dir_hash_tab { int size; /* size of hash tables */ - int names_duped; /* 1 = ent names malloced */ dir_hash_ent_t *first; /* ptr to first added entry */ dir_hash_ent_t *last; /* ptr to last added entry */ dir_hash_ent_t **byhash; /* ptr to name hash buckets */ @@ -171,8 +171,6 @@ dir_hash_add( short junk; struct xfs_name xname; - ASSERT(!hashtab->names_duped); - xname.name = name; xname.len = namelen; xname.type = ftype; @@ -199,7 +197,12 @@ dir_hash_add( } } - if ((p = malloc(sizeof(*p))) == NULL) + /* + * Allocate enough space for the hash entry and the name in a single + * allocation so we can store our own copy of the name for later use. + */ + p = calloc(1, sizeof(*p) + namelen + 1); + if (!p) do_error(_("malloc failed in dir_hash_add (%zu bytes)\n"), sizeof(*p)); @@ -220,8 +223,12 @@ dir_hash_add( p->address = addr; p->inum = inum; p->seen = 0; - p->name = xname; + /* Set up the name in the region trailing the hash entry. */ + memcpy(p->namebuf, name, namelen); + p->name.name = p->namebuf; + p->name.len = namelen; + p->name.type = ftype; return !dup; } @@ -287,8 +294,6 @@ dir_hash_done( for (i = 0; i < hashtab->size; i++) { for (p = hashtab->byaddr[i]; p; p = n) { n = p->nextbyaddr; - if (hashtab->names_duped) - free((void *)p->name.name); free(p); } } @@ -385,27 +390,6 @@ dir_hash_see_all( return j == stale ? DIR_HASH_CK_OK : DIR_HASH_CK_BADSTALE; } -/* - * Convert name pointers into locally allocated memory. - * This must only be done after all the entries have been added. - */ -static void -dir_hash_dup_names(dir_hash_tab_t *hashtab) -{ - unsigned char *name; - dir_hash_ent_t *p; - - if (hashtab->names_duped) - return; - - for (p = hashtab->first; p; p = p->nextbyorder) { - name = malloc(p->name.len); - memcpy(name, p->name.name, p->name.len); - p->name.name = name; - } - hashtab->names_duped = 1; -} - /* * Given a block number in a fork, return the next valid block number (not a * hole). If this is the last block number then NULLFILEOFF is returned. @@ -1383,6 +1367,7 @@ dir2_kill_block( res_failed(error); libxfs_trans_ijoin(tp, ip, 0); libxfs_trans_bjoin(tp, bp); + libxfs_trans_bhold(tp, bp); memset(&args, 0, sizeof(args)); args.dp = ip; args.trans = tp; @@ -1414,7 +1399,7 @@ longform_dir2_entry_check_data( int *need_dot, ino_tree_node_t *current_irec, int current_ino_offset, - struct xfs_buf **bpp, + struct xfs_buf *bp, dir_hash_tab_t *hashtab, freetab_t **freetabp, xfs_dablk_t da_bno, @@ -1422,7 +1407,6 @@ longform_dir2_entry_check_data( { xfs_dir2_dataptr_t addr; xfs_dir2_leaf_entry_t *blp; - struct xfs_buf *bp; xfs_dir2_block_tail_t *btp; struct xfs_dir2_data_hdr *d; xfs_dir2_db_t db; @@ -1453,7 +1437,6 @@ longform_dir2_entry_check_data( }; - bp = *bpp; d = bp->b_addr; ptr = (char *)d + mp->m_dir_geo->data_entry_offset; nbad = 0; @@ -1554,10 +1537,8 @@ longform_dir2_entry_check_data( dir2_kill_block(mp, ip, da_bno, bp); } else { do_warn(_("would junk block\n")); - libxfs_buf_relse(bp); } freetab->ents[db].v = NULLDATAOFF; - *bpp = NULL; return; } @@ -2215,17 +2196,15 @@ longform_dir2_entry_check(xfs_mount_t *mp, int ino_offset, dir_hash_tab_t *hashtab) { - struct xfs_buf **bplist; + struct xfs_buf *bp; xfs_dablk_t da_bno; freetab_t *freetab; - int num_bps; int i; int isblock; int isleaf; xfs_fileoff_t next_da_bno; int seeval; int fixit = 0; - xfs_dir2_db_t db; struct xfs_da_args args; *need_dot = 1; @@ -2242,11 +2221,6 @@ longform_dir2_entry_check(xfs_mount_t *mp, freetab->ents[i].v = NULLDATAOFF; freetab->ents[i].s = 0; } - num_bps = freetab->naents; - bplist = calloc(num_bps, sizeof(struct xfs_buf*)); - if (!bplist) - do_error(_("calloc failed in %s (%zu bytes)\n"), - __func__, num_bps * sizeof(struct xfs_buf*)); /* is this a block, leaf, or node directory? */ args.dp = ip; @@ -2275,28 +2249,12 @@ longform_dir2_entry_check(xfs_mount_t *mp, break; } - db = xfs_dir2_da_to_db(mp->m_dir_geo, da_bno); - if (db >= num_bps) { - int last_size = num_bps; - - /* more data blocks than expected */ - num_bps = db + 1; - bplist = realloc(bplist, num_bps * sizeof(struct xfs_buf*)); - if (!bplist) - do_error(_("realloc failed in %s (%zu bytes)\n"), - __func__, - num_bps * sizeof(struct xfs_buf*)); - /* Initialize the new elements */ - for (i = last_size; i < num_bps; i++) - bplist[i] = NULL; - } - if (isblock) ops = &xfs_dir3_block_buf_ops; else ops = &xfs_dir3_data_buf_ops; - error = dir_read_buf(ip, da_bno, &bplist[db], ops, &fixit); + error = dir_read_buf(ip, da_bno, &bp, ops, &fixit); if (error) { do_warn( _("can't read data block %u for directory inode %" PRIu64 " error %d\n"), @@ -2316,21 +2274,25 @@ longform_dir2_entry_check(xfs_mount_t *mp, } /* check v5 metadata */ - d = bplist[db]->b_addr; + d = bp->b_addr; if (be32_to_cpu(d->magic) == XFS_DIR3_BLOCK_MAGIC || be32_to_cpu(d->magic) == XFS_DIR3_DATA_MAGIC) { - struct xfs_buf *bp = bplist[db]; - error = check_dir3_header(mp, bp, ino); if (error) { fixit++; + if (isblock) + goto out_fix; continue; } } longform_dir2_entry_check_data(mp, ip, num_illegal, need_dot, - irec, ino_offset, &bplist[db], hashtab, + irec, ino_offset, bp, hashtab, &freetab, da_bno, isblock); + if (isblock) + break; + + libxfs_buf_relse(bp); } fixit |= (*num_illegal != 0) || dir2_is_badino(ino) || *need_dot; @@ -2341,7 +2303,7 @@ longform_dir2_entry_check(xfs_mount_t *mp, xfs_dir2_block_tail_t *btp; xfs_dir2_leaf_entry_t *blp; - block = bplist[0]->b_addr; + block = bp->b_addr; btp = xfs_dir2_block_tail_p(mp->m_dir_geo, block); blp = xfs_dir2_block_leaf_p(btp); seeval = dir_hash_see_all(hashtab, blp, @@ -2358,11 +2320,10 @@ longform_dir2_entry_check(xfs_mount_t *mp, } } out_fix: + if (isblock && bp) + libxfs_buf_relse(bp); + if (!no_modify && (fixit || dotdot_update)) { - dir_hash_dup_names(hashtab); - for (i = 0; i < num_bps; i++) - if (bplist[i]) - libxfs_buf_relse(bplist[i]); longform_dir2_rebuild(mp, ino, ip, irec, ino_offset, hashtab); *num_illegal = 0; *need_dot = 0; @@ -2370,12 +2331,8 @@ out_fix: if (fixit || dotdot_update) do_warn( _("would rebuild directory inode %" PRIu64 "\n"), ino); - for (i = 0; i < num_bps; i++) - if (bplist[i]) - libxfs_buf_relse(bplist[i]); } - free(bplist); free(freetab); } From patchwork Tue Mar 30 14:25:30 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172707 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B98A4C433E2 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 82AC2619CE for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232002AbhC3O0V (ORCPT ); Tue, 30 Mar 2021 10:26:21 -0400 Received: from sonic317-20.consmr.mail.gq1.yahoo.com ([98.137.66.146]:39323 "EHLO sonic317-20.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232052AbhC3O0E (ORCPT ); Tue, 30 Mar 2021 10:26:04 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114364; bh=7IUf5etUR4dCzujJK/Mt7eksviSNatZqAHagCErASOE=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=cTomG97eW62f9eU7z0jz/9Ye6ZwDaZleTx87mh2ih2gfjfRTeKya1bfLeWVElSFbPlo7LR1zkQSdaRMeTUqQeCNv5RBuv/MqD3/k2vqQ3kihu47hw02gEl1Aqo4LQC0A00e9II+YYe9gFu+pKFwVnziFEOPD/n39H2V/l9M1JkpgD/YDYheG2TVhIN6wfreCzswEdA+diw9+3iiu8fZ8TdT2UO4vqtyxkJ80sd/98JatvpWx2EMqQbDifzbWuPCtr+9hWqvc0e5wwsEtQgg+4W+5N8gDP9m3GsxuQ54ti0uu/d9lbd43VqTCeqOOEfM+6pShUm1stkr9gVZOL7gBfg== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114364; bh=cSwaUqid39JtRnWUE1jI6sLx3Fs6p9sHpFDvFShunA+=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=LUvq2v0mjIOXT+SFMfQrU6wqf14AqPs9n20CP+nQTQ4RoQIuBiqdNmoj1s9XntfV7lMOH+GIUl+uciCEaQ/mlGtGRXYjtaiYr/8NtRy7snMgGBMBxpSuv7lzKKbT9b7yyd906yvtZvrKKs+h4sUBjhHJjasfZkFfHPL51jL+9gZdOCJ3sMhhb1MAJBV1SRU0x0MkwiRqW9v+i6f/O8ztD1iI5D/pzAo/W3cpQGJO+JqVH/d3o+u8OA7GoLszB8xfkd8twfq7+3YEUIt6ykDzVDNAJaxF0KEYhvaAVS76/+Q3Cx5929VBdR5VB6fC+b5xiPeGbTc3PNu5A9WE9O3e6Q== X-YMail-OSG: 5XF_w48VM1lYD.wST.kcIJBYzwU1V3hiHtOszogKiN6c8J3m1hIUuJ9RR5Hn2Jn D4wvgQcAhO4Bl.oe9Pvs3q0fkD.INFNFJzg2Ay0BV08w.lWSvu07BvBtlUM_DXv943CpdGjRguzp 9EutonImQ4l4Choe2Pba_gHRr.4I2cdgXKoY4aFAKp8HlKX907.n_gZdRzQATL.dm3DjYjGB2EXn tVshi1lNU1A2PXI5.vUppNvDI3Y38uUd5Znfpm0ad9YgbQ0FX9TZNXen9nXwvPBLuMmnVWliqaxt kgL0UOP.5br85fRZ4q_geh3h2pm1RVjYBvtjiLJbs3S7ck9Hm86gyKaM0Zoid4GH3QxwNEXUhmG7 jyH3gXyBYYZjii4SFPcM6Mdeqn70FgMPLuiN7TTaQNA8PMYpQ4tA.gSCGm900zRD3ETGBq8dkZq8 zK.6o8hBwPf3GqN6rXtRZpS7CGpMqvHiP0rb6iud3Uv8CJeSzVmqtYLplbSIdyxTwrbgdiVo0wlN KKa2cbX3bc4Z33Rd3F8R9wV12xZbvHE57VaZ_6H4593DNThgEeDNlYQ3KtsnwfMxtCHjDmHgAW13 gnvPGjxpbhojgXx7pFmWneo1t0yLIJi1vk_NtvhPeCmyRkL15LN7nZVk5gXY_wWYUOrGyFEu787y Tul3gBDHo9gwrMK601R9iJTK6PEoJ8Gl5WCAQdDOvjz4SIbto0_lG5IC4ObCXZ32lOkDRWdntDsI rEXg33tfO7h677wIImXf9VSim.yO7qmf1x5_zntWhLb41PRKS3GpflGst9_fl5HR4JOiie3bDTi2 eCH70XwDgYuvdhSh4_SYe37lHk2O4emUXvLe7nWhpuZC_BDpDxcEvml9fXFqrsgkcOPEhkxFgPbw vD3NYefF2dCXWJwVlvs6oRS_ZSA5HtXCGK6QKa8kWOjyo2A_ayhHOLZd5k3.0yH9xlneWjVNGzwQ cEAywnea9dv6bHGUZ0xRDNBNgRQRBwqJ.OCIpIuHilii70SHE3QpDk9gN.Es4JavtuCoD6ZKsnSP n5cv0fC3kgfQccAYBQBeRJFOA3h9JR7Yk2At9ZzcsZMjgAdfRvuGF_FZZB_pm65DvMBEBhpjxoKi TLBx9E9Gy8S0GwLt.v0tmF8pq_bhGu6JjRAfXiBzBdUctNbJAyyUCQARwiewsV03AibXnfY02BxN A3QeEPXKs9mUcevRENWaeNAhRJe2bHZpAXSUSAzrRXlc9mCN1aAA4JgZy2x89wgl3X46TEiPZakt G4_1CVDGcQ20u7IeYxr1U9S2D2DFA_5ZL7kOhmgovLIHTLnJGkcGbuEGFqaltO..8BJ7idZZK2pm S_xgfkJaONk7EY.ZQWYHlDtb7tvmoB.95I0MZYv4MfLekPY54t8VI9wRefDWFmHB1f_UD.M7NSTF CnRiQEVcJ2joPCKCFdXz1YXLPNDnANauO.zB9AZhQMbWlXWhLrhwA1XHGmc2JEsXFuvXaXVAyGcp Iv5hCuyEOvXUQwM_buUu8nVAfhuWScxsrh5YOgsi7nCj2gYR8Qeo1IfQCRz1C.IiPguU6TPjFT.u k8cXSswOhhP71Ms_OgGlmIvTuCOKnIchsJq_fXJVuq4I1vqh8GB9RETJR.aVt8EAU399sXFeMLqs PG..EADpjg_gOWuA86Dqs4L52t2xg5uCZCMARHECFwXuQ1tx1yxKy3bDDAIDFZqn1cghb4LANdmh BNtCewgOBbhhZH3XUDRewPQbqEFuO0OWy3fRicKmg0FalXrgqt.QXAWCr9G34DcyF2nLz7_5QYTy 2Q49maLOTpp_OJ8KAygCz1nx5FnpwK_05pb5ILs1GDCEbtrYZaWv60TGdRg708Lj.5gKeoNxtr_4 aLlqNhYgT4BbvV2wYFBCPStYGDA2lUhR8qV7V3.KxsjcZoyY0BF2jiYM0cIOQKDsAn_MhXoOIRrD j0jZzngKbBzCRbRRoW6yqXHmBvHb.Fi05.LrUYLLa9QglsSCGvnrVBfewHvenjebCTBg32NVwOid lG0_hGXcrSi0BIGUdq.v0UB9ooGBZmO7bgntUUkSs3HD77EwYy4uIB6DdVUDkoNR0YK_Uo4eHMDQ ZBj.Mq.cplfaKjZBei3Un.pAqRpxrF8iE9iLGFL0kMslvT0KRX7EkTUZedNKn.jykf9vX6J.3Aqs bnelocq8ZXeaLCz2NCr_BCxPspGUXdPfOpfAlDzQ7qrUV6JWlCoNZLyFLcy2TxiAJA84X65Th12w 3_rLfjApQTXjjysSBTbMVdvVMis8DB5Mf08kxYs5MxmIMwo1IhY8tbOqDwdX1wnotrdsKZkTRM7J lB.vTJTFbrn0WmXbdaAtZqj8p3a99Q6mOgP17DAcRJaujd5uj9ARJsRAtepzckLXcXRCLkWrMXR1 6WBQoa8zpWkjQAL82bRrUrO8tH55N92v1OJguc64nVa59BicZQoADhWSJ5_DeUKti4nRCdzI3ZuH gENkiy1fyOEBVXNSgTHDKbvgirBmTbuS4uFkrsl0mkvChsn35ZIAI6FK95TpsmzTra7JI.DtdK6I UreuAOQOc3mGpYRkYEZElKL2jtHsQ9zKa_HnSanl8C_R1pzobHxuPAOtqrofoAwkNUvSQP.0lNLj 5TKz3zzxepm1Yg0V0n7OJpKQwoaAEquXStsB5dB6ATNnRWEzoPYieF2bB6ueI X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic317.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:26:04 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:26:02 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , "Darrick J . Wong" , Gao Xiang Subject: [PATCH v3 7/8] repair: convert the dir byaddr hash to a radix tree Date: Tue, 30 Mar 2021 22:25:30 +0800 Message-Id: <20210330142531.19809-8-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner Phase 6 uses a hash table to track the data segment addresses of the entries it has seen in a directory. This is indexed by the offset into the data segment for the dirent, and is used to check if the entry exists, is a duplicate or has a bad hash value. The lookup operations involve walking long hash chains on large directories and they are done for every entry in the directory. This means certain operations have O(n^2) scalability (or worse!) and hence hurt on very large directories. It is also used to determine if the directory has unseen entries, which involves a full hash traversal that is very expensive on large directories. Hence the directory checking for unseen ends up being roughly a O(n^2 + n) algorithm. Switch the byaddr indexing to a radix tree. While a radix tree will burn more memory than the linked list, it gives us O(log n) lookup operations instead of O(n) on large directories, and use for tags gives us O(1) determination of whether all entries have been seen or not. This brings the "entry seen" algorithm scalability back to O(nlog n) and so is a major improvement for processing large directories. Given a filesystem with 10M empty files in a single directory, we see: 5.6.0: 97.56% xfs_repair [.] dir_hash_add.lto_priv.0 0.38% xfs_repair [.] avl_ino_start.lto_priv.0 0.37% libc-2.31.so [.] malloc 0.34% xfs_repair [.] longform_dir2_entry_check_data.lto_priv.0 Phase 6: 10/22 12:07:13 10/22 12:10:51 3 minutes, 38 seconds Patched: 97.11% xfs_repair [.] dir_hash_add 0.38% xfs_repair [.] longform_dir2_entry_check_data 0.34% libc-2.31.so [.] __libc_calloc 0.32% xfs_repair [.] avl_ino_start Phase 6: 10/22 12:11:40 10/22 12:14:28 2 minutes, 48 seconds So there's some improvement, but we are clearly still CPU bound due to the O(n^2) scalability of the duplicate name checking algorithm. Reviewed-by: Darrick J. Wong Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang --- libfrog/radix-tree.c | 46 +++++++++ repair/phase6.c | 222 ++++++++++++++++++++----------------------- 2 files changed, 148 insertions(+), 120 deletions(-) diff --git a/libfrog/radix-tree.c b/libfrog/radix-tree.c index c1c74876964c..261fc2487de9 100644 --- a/libfrog/radix-tree.c +++ b/libfrog/radix-tree.c @@ -312,6 +312,52 @@ void *radix_tree_lookup_first(struct radix_tree_root *root, unsigned long *index #ifdef RADIX_TREE_TAGS +/** + * radix_tree_tag_get - get a tag on a radix tree node + * @root: radix tree root + * @index: index key + * @tag: tag index (< RADIX_TREE_MAX_TAGS) + * + * Return values: + * + * 0: tag not present or not set + * 1: tag set + * + * Note that the return value of this function may not be relied on, even if + * the RCU lock is held, unless tag modification and node deletion are excluded + * from concurrency. + */ +int radix_tree_tag_get(struct radix_tree_root *root, + unsigned long index, unsigned int tag) +{ + unsigned int height, shift; + struct radix_tree_node *slot; + + height = root->height; + if (index > radix_tree_maxindex(height)) + return 0; + + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + slot = root->rnode; + + while (height > 0) { + int offset; + + if (slot == NULL) + return 0; + + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + if (!tag_get(slot, tag, offset)) + return 0; + + slot = slot->slots[offset]; + ASSERT(slot != NULL); + shift -= RADIX_TREE_MAP_SHIFT; + height--; + } + return 1; +} + /** * radix_tree_tag_set - set a tag on a radix tree node * @root: radix tree root diff --git a/repair/phase6.c b/repair/phase6.c index df8db146c187..063329636500 100644 --- a/repair/phase6.c +++ b/repair/phase6.c @@ -66,8 +66,7 @@ add_dotdot_update( * and whether their leaf entry has been seen. Also used for name * duplicate checking and rebuilding step if required. */ -typedef struct dir_hash_ent { - struct dir_hash_ent *nextbyaddr; /* next in addr bucket */ +struct dir_hash_ent { struct dir_hash_ent *nextbyhash; /* next in name bucket */ struct dir_hash_ent *nextbyorder; /* next in order added */ xfs_dahash_t hashval; /* hash value of name */ @@ -77,18 +76,19 @@ typedef struct dir_hash_ent { short seen; /* have seen leaf entry */ struct xfs_name name; unsigned char namebuf[]; -} dir_hash_ent_t; +}; -typedef struct dir_hash_tab { +struct dir_hash_tab { int size; /* size of hash tables */ - dir_hash_ent_t *first; /* ptr to first added entry */ - dir_hash_ent_t *last; /* ptr to last added entry */ - dir_hash_ent_t **byhash; /* ptr to name hash buckets */ - dir_hash_ent_t **byaddr; /* ptr to addr hash buckets */ -} dir_hash_tab_t; + struct dir_hash_ent *first; /* ptr to first added entry */ + struct dir_hash_ent *last; /* ptr to last added entry */ + struct dir_hash_ent **byhash; /* ptr to name hash buckets */ +#define HT_UNSEEN 1 + struct radix_tree_root byaddr; +}; #define DIR_HASH_TAB_SIZE(n) \ - (sizeof(dir_hash_tab_t) + (sizeof(dir_hash_ent_t *) * (n) * 2)) + (sizeof(struct dir_hash_tab) + (sizeof(struct dir_hash_ent *) * (n))) #define DIR_HASH_FUNC(t,a) ((a) % (t)->size) /* @@ -155,8 +155,8 @@ dir_read_buf( */ static int dir_hash_add( - xfs_mount_t *mp, - dir_hash_tab_t *hashtab, + struct xfs_mount *mp, + struct dir_hash_tab *hashtab, uint32_t addr, xfs_ino_t inum, int namelen, @@ -164,19 +164,18 @@ dir_hash_add( uint8_t ftype) { xfs_dahash_t hash = 0; - int byaddr; int byhash = 0; - dir_hash_ent_t *p; + struct dir_hash_ent *p; int dup; short junk; struct xfs_name xname; + int error; xname.name = name; xname.len = namelen; xname.type = ftype; junk = name[0] == '/'; - byaddr = DIR_HASH_FUNC(hashtab, addr); dup = 0; if (!junk) { @@ -206,8 +205,14 @@ dir_hash_add( do_error(_("malloc failed in dir_hash_add (%zu bytes)\n"), sizeof(*p)); - p->nextbyaddr = hashtab->byaddr[byaddr]; - hashtab->byaddr[byaddr] = p; + error = radix_tree_insert(&hashtab->byaddr, addr, p); + if (error == EEXIST) { + do_warn(_("duplicate addrs %u in directory!\n"), addr); + free(p); + return 0; + } + radix_tree_tag_set(&hashtab->byaddr, addr, HT_UNSEEN); + if (hashtab->last) hashtab->last->nextbyorder = p; else @@ -232,33 +237,14 @@ dir_hash_add( return !dup; } -/* - * checks to see if any data entries are not in the leaf blocks - */ -static int -dir_hash_unseen( - dir_hash_tab_t *hashtab) -{ - int i; - dir_hash_ent_t *p; - - for (i = 0; i < hashtab->size; i++) { - for (p = hashtab->byaddr[i]; p; p = p->nextbyaddr) { - if (p->seen == 0) - return 1; - } - } - return 0; -} - static int dir_hash_check( - dir_hash_tab_t *hashtab, - xfs_inode_t *ip, - int seeval) + struct dir_hash_tab *hashtab, + struct xfs_inode *ip, + int seeval) { - static char *seevalstr[DIR_HASH_CK_TOTAL]; - static int done; + static char *seevalstr[DIR_HASH_CK_TOTAL]; + static int done; if (!done) { seevalstr[DIR_HASH_CK_OK] = _("ok"); @@ -270,7 +256,8 @@ dir_hash_check( done = 1; } - if (seeval == DIR_HASH_CK_OK && dir_hash_unseen(hashtab)) + if (seeval == DIR_HASH_CK_OK && + radix_tree_tagged(&hashtab->byaddr, HT_UNSEEN)) seeval = DIR_HASH_CK_NOLEAF; if (seeval == DIR_HASH_CK_OK) return 0; @@ -285,27 +272,28 @@ dir_hash_check( static void dir_hash_done( - dir_hash_tab_t *hashtab) + struct dir_hash_tab *hashtab) { - int i; - dir_hash_ent_t *n; - dir_hash_ent_t *p; + int i; + struct dir_hash_ent *n; + struct dir_hash_ent *p; for (i = 0; i < hashtab->size; i++) { - for (p = hashtab->byaddr[i]; p; p = n) { - n = p->nextbyaddr; + for (p = hashtab->byhash[i]; p; p = n) { + n = p->nextbyhash; + radix_tree_delete(&hashtab->byaddr, p->address); free(p); } } free(hashtab); } -static dir_hash_tab_t * +static struct dir_hash_tab * dir_hash_init( - xfs_fsize_t size) + xfs_fsize_t size) { - dir_hash_tab_t *hashtab; - int hsize; + struct dir_hash_tab *hashtab; + int hsize; hsize = size / (16 * 4); if (hsize > 65536) @@ -315,51 +303,43 @@ dir_hash_init( if ((hashtab = calloc(DIR_HASH_TAB_SIZE(hsize), 1)) == NULL) do_error(_("calloc failed in dir_hash_init\n")); hashtab->size = hsize; - hashtab->byhash = (dir_hash_ent_t**)((char *)hashtab + - sizeof(dir_hash_tab_t)); - hashtab->byaddr = (dir_hash_ent_t**)((char *)hashtab + - sizeof(dir_hash_tab_t) + sizeof(dir_hash_ent_t*) * hsize); + hashtab->byhash = (struct dir_hash_ent **)((char *)hashtab + + sizeof(struct dir_hash_tab)); + INIT_RADIX_TREE(&hashtab->byaddr, 0); return hashtab; } static int dir_hash_see( - dir_hash_tab_t *hashtab, + struct dir_hash_tab *hashtab, xfs_dahash_t hash, xfs_dir2_dataptr_t addr) { - int i; - dir_hash_ent_t *p; + struct dir_hash_ent *p; - i = DIR_HASH_FUNC(hashtab, addr); - for (p = hashtab->byaddr[i]; p; p = p->nextbyaddr) { - if (p->address != addr) - continue; - if (p->seen) - return DIR_HASH_CK_DUPLEAF; - if (p->junkit == 0 && p->hashval != hash) - return DIR_HASH_CK_BADHASH; - p->seen = 1; - return DIR_HASH_CK_OK; - } - return DIR_HASH_CK_NODATA; + p = radix_tree_lookup(&hashtab->byaddr, addr); + if (!p) + return DIR_HASH_CK_NODATA; + if (!radix_tree_tag_get(&hashtab->byaddr, addr, HT_UNSEEN)) + return DIR_HASH_CK_DUPLEAF; + if (p->junkit == 0 && p->hashval != hash) + return DIR_HASH_CK_BADHASH; + radix_tree_tag_clear(&hashtab->byaddr, addr, HT_UNSEEN); + return DIR_HASH_CK_OK; } static void dir_hash_update_ftype( - dir_hash_tab_t *hashtab, + struct dir_hash_tab *hashtab, xfs_dir2_dataptr_t addr, uint8_t ftype) { - int i; - dir_hash_ent_t *p; + struct dir_hash_ent *p; - i = DIR_HASH_FUNC(hashtab, addr); - for (p = hashtab->byaddr[i]; p; p = p->nextbyaddr) { - if (p->address != addr) - continue; - p->name.type = ftype; - } + p = radix_tree_lookup(&hashtab->byaddr, addr); + if (!p) + return; + p->name.type = ftype; } /* @@ -368,7 +348,7 @@ dir_hash_update_ftype( */ static int dir_hash_see_all( - dir_hash_tab_t *hashtab, + struct dir_hash_tab *hashtab, xfs_dir2_leaf_entry_t *ents, int count, int stale) @@ -1222,19 +1202,19 @@ dir_binval( static void longform_dir2_rebuild( - xfs_mount_t *mp, + struct xfs_mount *mp, xfs_ino_t ino, - xfs_inode_t *ip, - ino_tree_node_t *irec, + struct xfs_inode *ip, + struct ino_tree_node *irec, int ino_offset, - dir_hash_tab_t *hashtab) + struct dir_hash_tab *hashtab) { int error; int nres; - xfs_trans_t *tp; + struct xfs_trans *tp; xfs_fileoff_t lastblock; - xfs_inode_t pip; - dir_hash_ent_t *p; + struct xfs_inode pip; + struct dir_hash_ent *p; int done = 0; /* @@ -1393,14 +1373,14 @@ _("directory shrink failed (%d)\n"), error); */ static void longform_dir2_entry_check_data( - xfs_mount_t *mp, - xfs_inode_t *ip, + struct xfs_mount *mp, + struct xfs_inode *ip, int *num_illegal, int *need_dot, - ino_tree_node_t *current_irec, + struct ino_tree_node *current_irec, int current_ino_offset, struct xfs_buf *bp, - dir_hash_tab_t *hashtab, + struct dir_hash_tab *hashtab, freetab_t **freetabp, xfs_dablk_t da_bno, int isblock) @@ -1927,10 +1907,10 @@ check_dir3_header( */ static int longform_dir2_check_leaf( - xfs_mount_t *mp, - xfs_inode_t *ip, - dir_hash_tab_t *hashtab, - freetab_t *freetab) + struct xfs_mount *mp, + struct xfs_inode *ip, + struct dir_hash_tab *hashtab, + struct freetab *freetab) { int badtail; __be16 *bestsp; @@ -2012,10 +1992,10 @@ longform_dir2_check_leaf( */ static int longform_dir2_check_node( - xfs_mount_t *mp, - xfs_inode_t *ip, - dir_hash_tab_t *hashtab, - freetab_t *freetab) + struct xfs_mount *mp, + struct xfs_inode *ip, + struct dir_hash_tab *hashtab, + struct freetab *freetab) { struct xfs_buf *bp; xfs_dablk_t da_bno; @@ -2187,14 +2167,15 @@ longform_dir2_check_node( * (ie. get libxfs to do all the grunt work) */ static void -longform_dir2_entry_check(xfs_mount_t *mp, - xfs_ino_t ino, - xfs_inode_t *ip, - int *num_illegal, - int *need_dot, - ino_tree_node_t *irec, - int ino_offset, - dir_hash_tab_t *hashtab) +longform_dir2_entry_check( + struct xfs_mount *mp, + xfs_ino_t ino, + struct xfs_inode *ip, + int *num_illegal, + int *need_dot, + struct ino_tree_node *irec, + int ino_offset, + struct dir_hash_tab *hashtab) { struct xfs_buf *bp; xfs_dablk_t da_bno; @@ -2397,13 +2378,14 @@ shortform_dir2_junk( } static void -shortform_dir2_entry_check(xfs_mount_t *mp, - xfs_ino_t ino, - xfs_inode_t *ip, - int *ino_dirty, - ino_tree_node_t *current_irec, - int current_ino_offset, - dir_hash_tab_t *hashtab) +shortform_dir2_entry_check( + struct xfs_mount *mp, + xfs_ino_t ino, + struct xfs_inode *ip, + int *ino_dirty, + struct ino_tree_node *current_irec, + int current_ino_offset, + struct dir_hash_tab *hashtab) { xfs_ino_t lino; xfs_ino_t parent; @@ -2745,15 +2727,15 @@ _("entry \"%s\" (ino %" PRIu64 ") in dir %" PRIu64 " is a duplicate name"), */ static void process_dir_inode( - xfs_mount_t *mp, + struct xfs_mount *mp, xfs_agnumber_t agno, - ino_tree_node_t *irec, + struct ino_tree_node *irec, int ino_offset) { xfs_ino_t ino; - xfs_inode_t *ip; - xfs_trans_t *tp; - dir_hash_tab_t *hashtab; + struct xfs_inode *ip; + struct xfs_trans *tp; + struct dir_hash_tab *hashtab; int need_dot; int dirty, num_illegal, error, nres; From patchwork Tue Mar 30 14:25:31 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gao Xiang X-Patchwork-Id: 12172709 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D98F1C433E5 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BDFAE619D8 for ; Tue, 30 Mar 2021 14:26:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232004AbhC3O0V (ORCPT ); Tue, 30 Mar 2021 10:26:21 -0400 Received: from sonic304-24.consmr.mail.gq1.yahoo.com ([98.137.68.205]:36953 "EHLO sonic304-24.consmr.mail.gq1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232067AbhC3O0I (ORCPT ); Tue, 30 Mar 2021 10:26:08 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1617114368; bh=C+ztXxiHumfPzPm5X3Le/YXGTxHnu+eEnHfWnfIpcXQ=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From:Subject:Reply-To; b=YAboQyijyqa7ZbZYMgzNnK3AhdSdnv69lncVMdBMlpksRn/uAzcjxnQWUQF58kTfl08bnXZGWmVQAf44ARWg1Uz02/Et1nj0mwRBwtdBAAGzg/t2wgDmJzRNrbXUP5zib5ELpcbciL2U63frSMT9COnj3jm1XwJKlHr5a5Df0Wrp8mLGo8RPLRv9WRifrlnJfwCweRAgxkn2WSqGxck2vSM16NSEeaUdds8xrD55VWy/oLMNSexV5ZY9wP/+J8kao2YjeAF4CxsMYmz0dxjIauWfO0uioC7ZlnEeOcyAFiww00ll9xuOAuSqCJxWeu6ha8THoz2u73eUbWWwVqccDg== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1617114368; bh=dwlmUaBefD5lBZIaQU1sPm+AV73CWKLAaEoQ3WWcPaO=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=S766LXjYqR/I3Uj46QHasLYEnqDR7NGbQjkcPvCvXqkJTkbmXHZblyezYE2B7ViQLlwQyRobH791JtlHvHUpIcVmFEgcR0PKZitIipBJZhNId5K9lu2WgP7cHE3c/6uf4imepvNSPUhROkUMwK1EePU7ssybnVeyhWWq9YO1X4aT4VLn8BrEeOqeahzE9Sjeu1/3YS1r7Grjc4Gq6VKWN+L9oyF4CaBZf0ruP4y03DGBZUg6lE9WfsXzH0HJAGi+hlxtv9nHei+JK1+GU8T82J+mRaHME9l/QyiG2TaQQxN20UOz/wAGgSrFjo+vgJ0K/ev/1RJPUxTZ7hurON4PPA== X-YMail-OSG: hh6qyJ0VM1k1OQjguSk88vK0GLiZUK.pyNy45WfrVjFOXv6JXQ7kux7wst.7vNh hMw68HEfgaV2Ygzbpjz9cl6SIqRA_j30V9c03u_m6SA2T5B8B4F8t0wk3rJ8tK.aK6XDiPlxu.bi wJEa1oV4m1zhMTU8H1Z5am7ZaiVmnKw166_84woExgYFCznBd9DvO9buf3s0sAG_66Jo4DBItEWh APTT_KpUhsHvPXVd.DnDTgeIvaAq8pexJ71w5IkHg9XR8_cy9v3KUsf8lp9C.XFpgcZOAfxo9Bd5 UQzcKTtRpzk85xC_DBsvV81026_oJI.llU6cEbRQ_ZZFz_LF.5q4lZgX87jC1WeFF.gDnPrco36a 7bLioL1BghVbLFDUrHNdrmTtWK5TauNLghgEKB85ocPybLvHTYOWhQQsA13fTNJu89spSZFuilOl MYspjBydqpbiepMdmJLrnSvqcp.j7B9BSFJwTeQlFRCztNC1uINv9btq16odvYFf.pAES9m6_ImS 458At6rGbw7e35K8oAyGiAkjTmiwqV38zhu2hZbbOxq84PVc1a.f1C7NlHahlJAJBDe1OIP78QSd 3KDPqF6iZdyXJW2EyRBk.Y7MtAt1KpO0alS7ymqJZAi.niz1lJj90MvZfw6p_5omIU8wE8Gf8uTh nZ6HEpx.OXtGdnP9b24nX5K4lOp.MO.VqM3HjW4pphAmfbzeYU1tSi3Rdb4j_fLB23OPIQhQO7na zRSrIvHQoS1ELDUZbIrDqwU_ruLl52dYvvBMLEFEqIq5Ls3htQsix_WqYu7S9DF96_iZ7Dy4kCkk VI3TAb_Ou3gbTcGPUSfe8aiE0mF7YoGbSFBA2B_WoznHzBHK5hyKFaM_znpe1WZJgWCheP4wnScQ X9ZFETq3ggVCFSNINdm9CDo6bxtkGQFnh9p1HTq0m_trsSWW1uhlTvfX.ef6ujrLn4Xj5Yh.rVY7 oDznc5lIvmW6Yeiwn0VbwEwDnMTdy9WySZWbAgBAZDqRfWV1dxtMNHFcp8kjLjSHv_TndHWmfjc9 fpynPp4ywUcL9lUUvXc.NgE8TMc8_h9i7hzeYdg8JEY4PlZd.ABodUX.IhDOX85kRKRcfAEhA7Me wsBR7Nax1xgdjV7dtZn5NVS7MTT4YRZp9HmoG2IrVaZkZec2N3Vso4ePWci4W4rQ8Me5xCSvECbK H_86Ej4DbUNfC.wS.9vZkP3StsOAluJbcQ_gjay5.X0WOv2nj05TpU79nsYE6i_gjKtUTE480pIr avmcqb3vvm047HFdu1r3JwM6AagBvXLv5udAStjEhpYHc7lH0.PdyZOkcYMwmE_rpgJNi3v8gsZf 4aXH3SVfmhDsj.A3nMZcGqkxPpAaPRMA3OPo.oPduz1YCqycIJDiafvUn0MztfIAXtn7RqwiTJAd rqvWfXmPI0b_WqQnJ0QrSaeTCElpJPd6VBD_xqL3InUcgP8ZZWAeYbT0.Mmk1pebLDswQGxtDtT7 NwSO_lbcRitD0UXxlt4eKjvv.mgTLSv1pVG2oFFp6UUgxtLHaTREIqo70qJfARg_0.lCNCuKJQBl uZqDjFzfifMWRHLKaSgEv2iybpnN5K71qnzlMEA0pRz40raGxE.xm73sEmIujqlfJo3PzbHUYyGj XBtp4WQyvTqVLQGmfVxw9M1swHYVhKCtySx5uMRAn24G09THc8ROmOnXdg7BecJjVtc.LMR4pvsD gc.M6kgufMo8jcW0FKs5LrMaSkUsosuJRzGZQ7mUBwmAvwKxG7QWVKWbqm0URO.SwCFy6jf1Rqv2 E8XCjUmckrOmq4J818KA5vv3PPSRBN2BDtFm4wG3_R20C_mIs2ORShmPz4SRR5qCbmOzfd8HZEW. jEsbcjp3uOCLYIC8l833lsy0oJPbCgZW0bzTOM1r0jYZMnw9vXFomNnFsEpQ0kc6gXdAHHlJQGR5 eZvAe1g.RoG0x0.sheEqI9ZFtKPc.BApXwxCRJggy7Zf4rj5f0yZuQugJnLd6QYQ2wLu7rhnQKGX BHFRcNMh5tdkpWN3LD6xyhHO3_ogRLmM7_AxarCaXp26_xsa.PhSqCiyOds0jzr7VStSde6JJAcg k7ZG1oKmZg8damO3Bm_OJRZqcCnZ_81aLqKC3o0SjEAGMsSKUdvqPCzY5AdwKgr22Ui..sA6OJ_k 3BUDq__w3hFvkNqYkBSrz1bKdT3e_1pzOSM1cpksG.iLL372YErQPW8KLomcD.R9JPpZ_Gv3Me4T R6eNmH8fbll1VXBcngl3tKAs6V1ULwF9ATEFU1p3XxGQdPi_6.fduWsbwkXzM0zDVQqXavOLb9rl 72CaBaW8ccdK40XvVZvUgfaTtVs8gkUSoSACqiv9azLULTLIgtrWVK2XEN1V3wCe2sRRUr5Ta1pJ nwC621qhkRlEZKmRqdltnMCQgPr.PiNvXlkJtxmR5jCYqw04QiiC4hECsKF.J79UkzaiJOfJ.7p3 kahPDaTiW5bAfEvGNElbnpyHZCsVskSiqtSbFMYP2oP4lzOYHpHDp98shcelsinvcnL68jqrDHhw evMc0HRv4H8kF43XxUt1P_Sc2xmErMCsdMvVsDVq.62JKTT7EsO_ELTo8y0E- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic304.consmr.mail.gq1.yahoo.com with HTTP; Tue, 30 Mar 2021 14:26:08 +0000 Received: by kubenode575.mail-prod1.omega.gq1.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d17ac850f756223f45b54c36ad526fbe; Tue, 30 Mar 2021 14:26:04 +0000 (UTC) From: Gao Xiang To: linux-xfs@vger.kernel.org Cc: Dave Chinner , Gao Xiang Subject: [PATCH v3 8/8] repair: scale duplicate name checking in phase 6. Date: Tue, 30 Mar 2021 22:25:31 +0800 Message-Id: <20210330142531.19809-9-hsiangkao@aol.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20210330142531.19809-1-hsiangkao@aol.com> References: <20210330142531.19809-1-hsiangkao@aol.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Dave Chinner phase 6 on large directories is cpu bound on duplicate name checking due to the algorithm having effectively O(n^2) scalability. Hence when the duplicate name hash table size is far smaller than the number of directory entries, we end up with long hash chains that are searched linearly on every new entry that is found in the directory to do duplicate detection. The in-memory hash table size is limited to 64k entries. Hence when we have millions of entries in a directory, duplicate entry lookups on the hash table have substantial overhead. Scale this table out to larger sizes so that we keep the chain lengths short and hence the O(n^2) scalability impact is limited because N is always small. For a 10M entry directory consuming 400MB of directory data, the hash table now sizes at 6.4 million entries instead of ~64k - it is ~100x larger. While the hash table now consumes ~50MB of RAM, the xfs_repair footprint barely changes as it's using already consuming ~9GB of RAM at this point in time. IOWs, the incremental memory usage change is noise, but the directory checking time: Unpatched: 97.11% xfs_repair [.] dir_hash_add 0.38% xfs_repair [.] longform_dir2_entry_check_data 0.34% libc-2.31.so [.] __libc_calloc 0.32% xfs_repair [.] avl_ino_start Phase 6: 10/22 12:11:40 10/22 12:14:28 2 minutes, 48 seconds Patched: 46.74% xfs_repair [.] radix_tree_lookup 32.13% xfs_repair [.] dir_hash_see_all 7.70% xfs_repair [.] radix_tree_tag_get 3.92% xfs_repair [.] dir_hash_add 3.52% xfs_repair [.] radix_tree_tag_clear 2.43% xfs_repair [.] crc32c_le Phase 6: 10/22 13:11:01 10/22 13:11:18 17 seconds has been reduced by an order of magnitude. Signed-off-by: Dave Chinner Signed-off-by: Gao Xiang Reviewed-by: Darrick J. Wong --- repair/phase6.c | 30 ++++++++++++++++++++++++------ 1 file changed, 24 insertions(+), 6 deletions(-) diff --git a/repair/phase6.c b/repair/phase6.c index 063329636500..aa991bf76da6 100644 --- a/repair/phase6.c +++ b/repair/phase6.c @@ -288,19 +288,37 @@ dir_hash_done( free(hashtab); } +/* + * Create a directory hash index structure based on the size of the directory we + * are about to try to repair. The size passed in is the size of the data + * segment of the directory in bytes, so we don't really know exactly how many + * entries are in it. Hence assume an entry size of around 64 bytes - that's a + * name length of 40+ bytes so should cover a most situations with large + * really directories. + */ static struct dir_hash_tab * dir_hash_init( xfs_fsize_t size) { - struct dir_hash_tab *hashtab; + struct dir_hash_tab *hashtab = NULL; int hsize; - hsize = size / (16 * 4); - if (hsize > 65536) - hsize = 63336; - else if (hsize < 16) + hsize = size / 64; + if (hsize < 16) hsize = 16; - if ((hashtab = calloc(DIR_HASH_TAB_SIZE(hsize), 1)) == NULL) + + /* + * Try to allocate as large a hash table as possible. Failure to + * allocate isn't fatal, it will just result in slower performance as we + * reduce the size of the table. + */ + while (hsize >= 16) { + hashtab = calloc(DIR_HASH_TAB_SIZE(hsize), 1); + if (hashtab) + break; + hsize /= 2; + } + if (!hashtab) do_error(_("calloc failed in dir_hash_init\n")); hashtab->size = hsize; hashtab->byhash = (struct dir_hash_ent **)((char *)hashtab +