From patchwork Fri Oct 14 20:36:22 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Ojaswin Mujoo X-Patchwork-Id: 142 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp367703wrs; Fri, 14 Oct 2022 13:39:37 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7LPeRgLmVR8W257ZJpRcpKosqJSveIPHuEDOp9hz5zOD/PXjQqjGEuVegorRGg1hCnPNQL X-Received: by 2002:a17:90b:4f8e:b0:20c:c3a8:38b with SMTP id qe14-20020a17090b4f8e00b0020cc3a8038bmr7929746pjb.10.1665779977452; Fri, 14 Oct 2022 13:39:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665779977; cv=none; d=google.com; s=arc-20160816; b=nCwc3Sf1SrJ3en7OaxVAEsNlGojOssgl+/5+RYZfkCQvw3wfZYRWy4qoc23AK+yWWE v/g/AcP1Ha/fh4xGC6Re+J+tFC0Jbfnvgw3SO2mwJyaQ9MGdUypW5peYaV+x0NoQZoYr R4JqTKM5meL3X5C9mCspxSRtDaqKtEKY298ImY24XFsP0WzGuai75m9I1FiYJBTp9MEk /1aoehx1rlQd5wVQ/TODkG5jDWwnSPZcl4AvUVLaJlswx5qsiX/KWs/g0NfLkt6kPYDY eFCNV+WfeojN2Q02dlEMmkUEdc+NlleucvSmuL2Lgsf3nvNw+U2sITmb0799/aUHxxc8 bpHg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:mime-version:content-transfer-encoding :message-id:date:subject:cc:to:from:dkim-signature; bh=bindc1fvcFi+DBVoPCkVh4Kmo4x+uf3LRrw5U92XjqI=; b=WDLSZgDnzutf2kumxPJzv7F+CsaSZM1lEOt205eiVBYKX48APiWIlNxcPUi7faRFCz 4RLZ2HIUDKETTsdRRSls1ttXTbYQXdZqG/FWC8VXV5se6VGNxlFU+nd55MwVq5k55L5x h23vbKct6wRiW4DvMXyXZ4XJHc5MnXv9BAMyMCc7uXadYy6XWxz8nSAJ1OSJjrD+flxn nY1xPhUkTKwnCJM0UJFJDXDIYntWRBVwABmQIaLml0vkX27ZpjQIq1O//voaC+8CMIxv N/9Kx7v/fVSjTpwlWaK5WVNa/Pow0JFywQ0+8Y7uZRwYHV8HcJxIK2JWnV0Yth3EVHDP o3Qg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@ibm.com header.s=pp1 header.b=ltNUZysW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=ibm.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id y1-20020a63de41000000b00457bc51e1a4si3833378pgi.506.2022.10.14.13.39.24; Fri, 14 Oct 2022 13:39:37 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@ibm.com header.s=pp1 header.b=ltNUZysW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=ibm.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231474AbiJNUgt (ORCPT + 99 others); Fri, 14 Oct 2022 16:36:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38422 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231269AbiJNUgq (ORCPT ); Fri, 14 Oct 2022 16:36:46 -0400 Received: from mx0b-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1C94EE09DC; Fri, 14 Oct 2022 13:36:45 -0700 (PDT) Received: from pps.filterd (m0098421.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 29EKTOsp000689; Fri, 14 Oct 2022 20:36:40 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ibm.com; h=from : to : cc : subject : date : message-id : content-type : content-transfer-encoding : mime-version; s=pp1; bh=bindc1fvcFi+DBVoPCkVh4Kmo4x+uf3LRrw5U92XjqI=; b=ltNUZysWhCCKaLw9A95oZngVvo3HLpHzT5zc64Qvp8DDkQkLI+7Bxiv929VFhVoijylb QAiYtt1V0HEiYrgc3LQkE+V0YZlil+TJSR7Z9Bmo/icyRsBjWbB8LX2cGJkQzt28mK8R rPvtA3DL0NHn5Bf5Csz1lVMw5ZPtbA4vgX/CivTVrX0TWK1lzG1o2tyD4fepw63oIYFP NFm3ehtOV91e1wijCJXh1zTtcSkm5c0WGjZPpU6Xv1O/GI6CL8ABBh3krt15eAyFLEMM L30/WXiq+V19NmAEF7cE3rra59OHdKLPr+1Q7CDCxZ7GXeBtuwdwZnH57CvsJVRgV7Y2 /g== Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3k7euq8561-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 14 Oct 2022 20:36:40 +0000 Received: from m0098421.ppops.net (m0098421.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 29EKUErX003493; Fri, 14 Oct 2022 20:36:39 GMT Received: from ppma03fra.de.ibm.com (6b.4a.5195.ip4.static.sl-reverse.com [149.81.74.107]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3k7euq855b-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 14 Oct 2022 20:36:39 +0000 Received: from pps.filterd (ppma03fra.de.ibm.com [127.0.0.1]) by ppma03fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 29EKZtDa024850; Fri, 14 Oct 2022 20:36:37 GMT Received: from b06cxnps4075.portsmouth.uk.ibm.com (d06relay12.portsmouth.uk.ibm.com [9.149.109.197]) by ppma03fra.de.ibm.com with ESMTP id 3k30u9fhax-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 14 Oct 2022 20:36:37 +0000 Received: from d06av24.portsmouth.uk.ibm.com (mk.ibm.com [9.149.105.60]) by b06cxnps4075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 29EKaZOa23855442 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 14 Oct 2022 20:36:35 GMT Received: from d06av24.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 4999442041; Fri, 14 Oct 2022 20:36:35 +0000 (GMT) Received: from d06av24.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 1EBC94203F; Fri, 14 Oct 2022 20:36:33 +0000 (GMT) Received: from li-bb2b2a4c-3307-11b2-a85c-8fa5c3a69313.ibm.com (unknown [9.43.122.214]) by d06av24.portsmouth.uk.ibm.com (Postfix) with ESMTP; Fri, 14 Oct 2022 20:36:32 +0000 (GMT) From: Ojaswin Mujoo To: linux-ext4@vger.kernel.org, "Theodore Ts'o" Cc: Ritesh Harjani , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, Andreas Dilger , Jan Kara , rookxu Subject: [PATCH v2 0/8] ext4: Convert inode preallocation list to an rbtree Date: Sat, 15 Oct 2022 02:06:22 +0530 Message-Id: X-Mailer: git-send-email 2.31.1 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: Gqawbq0LXxbrwp-qBhws_c8QOkWQwwc3 X-Proofpoint-ORIG-GUID: 1j3EuVa6sZ5Qi4uJDfb5Pi4HmOG-uqPm X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.545,FMLib:17.11.122.1 definitions=2022-10-14_10,2022-10-14_01,2022-06-22_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 adultscore=0 lowpriorityscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 spamscore=0 impostorscore=0 clxscore=1015 mlxscore=0 bulkscore=0 priorityscore=1501 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2209130000 definitions=main-2210140112 X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_EF,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746696905677044194?= X-GMAIL-MSGID: =?utf-8?q?1746696905677044194?= This patch series aim to improve the performance and scalability of inode preallocation by changing inode preallocation linked list to an rbtree. I've ran xfstests quick on this series and plan to run auto group as well to confirm we have no regressions. ** Shortcomings of existing implementation ** Right now, we add all the inode preallocations(PAs) to a per inode linked list ei->i_prealloc_list. To prevent the list from growing infinitely during heavy sparse workloads, the length of this list was capped at 512 and a trimming logic was added to trim the list whenever it grew over this threshold, in patch 27bc446e2. This was discussed in detail in the following lore thread [1]. [1] https://lore.kernel.org/all/d7a98178-056b-6db5-6bce-4ead23f4a257@gmail.com/ But from our testing, we noticed that the current implementation still had issues with scalability as the performance degraded when the PAs stored in the list grew. Most of the degradation was seen in ext4_mb_normalize_request() and ext4_mb_use_preallocated() functions as they iterated the inode PA list. ** Improvements in this patchset ** To counter the above shortcomings, this patch series modifies the inode PA list to an rbtree, which: - improves the performance of functions discussed above due to the improved lookup speed. - improves scalability by changing lookup complexity from O(n) to O(logn). We no longer need the trimming logic as well. As a result, the RCU implementation was needed to be changed since lockless lookups of rbtrees do have some issues like skipping subtrees. Hence, RCU was replaced with read write locks for inode PAs. More information can be found in Patch 7 (that has the core changes). ** Performance Numbers ** Performance numbers were collected with and without these patches, using an nvme device. Details of tests/benchmarks used are as follows: Test 1: 200,000 1KiB sparse writes using (fio) Test 2: Fill 5GiB w/ random writes, 1KiB burst size using (fio) Test 3: Test 2, but do 4 sequential writes before jumping to random offset (fio) Test 4: Fill 8GB FS w/ 2KiB files, 64 threads in parallel (fsmark) +──────────+──────────────────+────────────────+──────────────────+──────────────────+ | | nodelalloc | delalloc | +──────────+──────────────────+────────────────+──────────────────+──────────────────+ | | Unpatched | Patched | Unpatched | Patched | +──────────+──────────────────+────────────────+──────────────────+──────────────────+ | Test 1 | 11.8 MB/s | 23.3 MB/s | 27.2 MB/s | 63.7 MB/s | | Test 2 | 1617 MB/s | 1740 MB/s | 2223 MB/s | 2208 MB/s | | Test 3 | 1715 MB/s | 1823 MB/s | 2346 MB/s | 2364 MB/s | | Test 4 | 14284 files/sec | 14347 files/s | 13762 files/sec | 13882 files/sec | +──────────+──────────────────+────────────────+──────────────────+──────────────────+ In test 1, we almost see 100 to 200% increase in performance due to the high number of sparse writes highlighting the bottleneck in the unpatched kernel. Further, on running "perf diff patched.data unpatched.data" for test 1, we see something as follows: 2.83% +29.67% [kernel.vmlinux] [k] _raw_spin_lock ... +3.33% [ext4] [k] ext4_mb_normalize_request.constprop.30 0.25% +2.81% [ext4] [k] ext4_mb_use_preallocated Here we can see that the biggest different is in the _raw_spin_lock() function of unpatched kernel, that is called from `ext4_mb_normalize_request()` as seen here: 32.47% fio [kernel.vmlinux] [k] _raw_spin_lock | ---_raw_spin_lock | --32.22%--ext4_mb_normalize_request.constprop.30 This is coming from the spin_lock(&pa->pa_lock) that is called for each PA that we iterate over, in ext4_mb_normalize_request(). Since in rbtrees, we lookup log(n) PAs rather than n PAs, this spin lock is taken less frequently, as evident in the perf. Furthermore, we see some improvements in other tests however since they don't exercise the PA traversal path as much as test 1, the improvements are relatively smaller. ** Summary of patches ** - Patch 1-5: Abstractions/Minor optimizations - Patch 6: Split common inode & locality group specific fields to a union - Patch 7: Core changes to move inode PA logic from list to rbtree - Patch 8: Remove the trim logic as it is not needed ** Changes since PATCH v1 ** - fixed styling issue - merged ext4_mb_rb_insert() and ext4_mb_pa_cmp() ** Changes since RFC v3 ** - Changed while loops to for loops in patch 7 - Fixed some data types - Made rbtree comparison logic more intuitive. The rbtree insertion function still kept separate from comparison function for reusability. ** Changes since RFC v2 ** - Added a function definition that was deleted during v2 rebase ** Changes since RFC v1 ** - Rebased over ext4 dev branch which includes Jan's patchset [1] that changed some code in mballoc.c [1] https://lore.kernel.org/all/20220908091301.147-1-jack@suse.cz/ *** BLURB HERE *** Ojaswin Mujoo (8): ext4: Stop searching if PA doesn't satisfy non-extent file ext4: Refactor code related to freeing PAs ext4: Refactor code in ext4_mb_normalize_request() and ext4_mb_use_preallocated() ext4: Move overlap assert logic into a separate function ext4: Abstract out overlap fix/check logic in ext4_mb_normalize_request() ext4: Convert pa->pa_inode_list and pa->pa_obj_lock into a union ext4: Use rbtrees to manage PAs instead of inode i_prealloc_list ext4: Remove the logic to trim inode PAs Documentation/admin-guide/ext4.rst | 3 - fs/ext4/ext4.h | 5 +- fs/ext4/mballoc.c | 418 ++++++++++++++++++----------- fs/ext4/mballoc.h | 17 +- fs/ext4/super.c | 4 +- fs/ext4/sysfs.c | 2 - 6 files changed, 274 insertions(+), 175 deletions(-)