From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6025BD4335C for ; Fri, 8 Nov 2024 02:31:00 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7B9516B00AD; Thu, 7 Nov 2024 21:30:59 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 742426B00AE; Thu, 7 Nov 2024 21:30:59 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5BB926B00B0; Thu, 7 Nov 2024 21:30:59 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 3C2516B00AD for ; Thu, 7 Nov 2024 21:30:59 -0500 (EST) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id B3CCE1C5B08 for ; Fri, 8 Nov 2024 02:30:58 +0000 (UTC) X-FDA: 82761348348.07.FB72DB2 Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf17.hostedemail.com (Postfix) with ESMTP id 7385240012 for ; Fri, 8 Nov 2024 02:30:28 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b="k/31aOZ3"; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf17.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731032885; a=rsa-sha256; cv=none; b=4RljL80tgQ0AnO7y+YBegtMtiRjSalsH2pelwWUUSIiNrkyn7F03zyyen+zUgaC1OT4xGf BbFWw45GJTWRPUw1r8/77j7sme3VxSICxAnqBN5Qb8uZr1mqhRVVAqqdxs2vaX/+7jJc0b zOBofZA6piCntjDWd/Rytv7YKWeO0Xw= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b="k/31aOZ3"; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf17.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731032885; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=0kY2au9+xSrAVqkU+dYB75IlxNPKyvTDx+2ghZq0aAA=; b=1oEIGxO+Os2QdrJ/h+CdQr+7YOyyUQeJiMFeWR7TmUai+x5I97v8sdgt64OrLF9jH5c98N AQ10e4rGAAfedatTtswBCNcX1c27shg6PMTrWy4dajW0rEDRKXbGPgd1GkbMswY1DNLfN8 kjU59QsVyFApwa36xIinjUHh/dRoNp0= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5c9388a00cfso1918844a12.3 for ; Thu, 07 Nov 2024 18:30:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731033055; x=1731637855; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=0kY2au9+xSrAVqkU+dYB75IlxNPKyvTDx+2ghZq0aAA=; b=k/31aOZ3h8z+Lfqjc+Ptnp4SGt9kEaqBRGvbCAjPvQ+3ZqUTJBlXrlZsGoPPRI9ALr UCx0+JrA1ncobVmxQZ3J4tLmchenxDK3nKIRqEuSaM6mGZ7sIl6AmXeXhecdzuCBixfd ABPidhWGK7cWk/J/djqGT0gLvReHDbId9RCGkhdfyLchx2E3S5x9GnccChXEk/aXZkxw KDwdNBFwvgw4kHIRFfNH8WyAbiucwM+DeQ2CJdYoGCLR6OTLMOVspBZrHjVGZYU7hDIi k3QbqzbFYTah3RJPkSk6AGVYmAkRjMeVdxI/WU6vraYkaeyNkTq6RP/N30DWOLCNi4L2 Phaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731033055; x=1731637855; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=0kY2au9+xSrAVqkU+dYB75IlxNPKyvTDx+2ghZq0aAA=; b=GmegWtfUnhE79O813WEeGSkYh3wt2b9lp7Umh61cjCS7ClfXs+j3IZvgnnLrDwhw+E rvvopE4Rv4zVmVjuWU1XOxpOjNFSbSAB9vAExYfVmXmxgJrGwmt3VsIZ3B8HrntRtcfL ePk8jDQ/UXbc06IHwMvxcwjdAGyXkW7hqHz5Ufj5MaYb7eKQaIUNv658hrIwiTJk20Z9 7WeAAxhdiTUCM/7xsIBEw2zuE7nu2mXe7//xP2A+bRX1Tdi96eOYo5DasYSlGHHfXlZ3 s+0TjEVkCdiR8ycf0utHJu/bO0gcLPq365Mim1vlu3ceZlThNyDsGV+5pMWLcK7OfEmV tHqg== X-Forwarded-Encrypted: i=1; AJvYcCViVueXeIHtaJs+jc6+oZPmRNtQi7gO8LQMaAUdAwrY5Yn5GLZ+BucUzIkYFnIY3sWqeeem+z8n4g==@kvack.org X-Gm-Message-State: AOJu0YzISL07/R4iLZgc9TQQUWvMMljgEYeO7rIowAgfEc/X6FAef70/ /m/g2vk6nbzRomuhq9EQnR0kQrPeBERjslgBWGWUrA23LwhgdzCf X-Google-Smtp-Source: AGHT+IH61uzUH5UT9iOQUuWtAysehY5NmUXI9FV80Er98dNn398I7K9LP9/byAtHOJdunmgo+Zi+mw== X-Received: by 2002:a05:6402:3583:b0:5cf:512:7ab4 with SMTP id 4fb4d7f45d1cf-5cf0a43e908mr737920a12.26.1731033054438; Thu, 07 Nov 2024 18:30:54 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03bb83acsm1457726a12.51.2024.11.07.18.30.51 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 07 Nov 2024 18:30:52 -0800 (PST) Date: Fri, 8 Nov 2024 02:30:50 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH 1/4] maple_tree: current split may result in deficient node Message-ID: <20241108023050.e7gnkqd7axotujea@master> Reply-To: Wei Yang References: <20241020024628.22469-1-richard.weiyang@gmail.com> <20241020024628.22469-2-richard.weiyang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Stat-Signature: s56pyykxj3q8t8d34t9hqisseza1j4j4 X-Rspamd-Queue-Id: 7385240012 X-Rspamd-Server: rspam08 X-Rspam-User: X-HE-Tag: 1731033028-38548 X-HE-Meta: U2FsdGVkX19kPCkyQET1OuI1vtJt9ewryRpXKOWWW8mamA68fzxr+9/ZOzgWe3PucYP9DdtYfTGavnoTVzVuR507JM4R60OajXJvwi99Gb1q93yzMM+4j1ayMjoTr/V1ZcuqRMCFqHt3lpUpczmmlC3OaRqwsZC784ILhro9wxRgByHOJufqO6GlcimCLE4gAzRWjhUZEqBrJq96cY+EOG4RLcu6jNN/lxfdp/R+LGzRcBCp4tj1o+iKf8hNDa0za4H+/8hFofU2JfGynBsbg56RVJwghzIzJo7quUVSv6+f+G83Hqc7CGznrnpsZi7XOWVWI97Jp5Cfv8dPdqjGcprYffUdninLeSw8eBa3ayvRrxQFXNvCtp0+jxeBgBbJDH+gOMRsUUaDDSAhEgp/gnrGD+Dn7UBR6R4imi2mI1cpqUbTmAwk79dn/24Y8TmfAOww2RCWtwuRy5/wF/qupxCyWc++uZzrKHowps0HzAt453SBVqrLHbzvF2a7S65qnyMUbvz2zBziPjrpBDQO+8f5qrzUKrwuSBhbnLSTkgfPWtXUQHs1Hn6/YjwZBqVUr8xD6ZJCHyFKAeJ2VtYRFvXUzoCFOdmMD9YUy6cIkKdXEOAZVII7098TJyEL5TZVRN7gWGDLldp1KZMLBAQrEasf6qS6BzUzwFA29qy4qvIiK2NL1oyjvltPb5upLY9GGNWU7b4BVZzkLEtrvPuYiGmlqwzDwLW5t2MXyvgUkwzA3LH243pfeTvrkjPP3g67QVUFoHyS0psDmJk9Y1S0/poZlOFGKVBnuoUIquxcBapxhNVBeFktsaWd3cDLUPQmzV4lcOonjgT4Dzuv2o6p8NlAN/wjkzwYxy+3+tET5bhPgOUrmwPpQCWdzThbYhwiFAHgdrX2YJTDqItlYSrO6zDpMmLyBm7/mz+QPfnUNSDVlHZrmowl8Ndz1Q2DJQhlLDzN+kaW3WeqXQJrIi9 +fweO+Lv co7EGmL5Xwhgy4GoZYje5KC3Oay0UJSY38hKqP0NBi2og/QvPlDajpt6wDmX2NWVmp/O89dbBXNIk6L9mHXnxMU7pLmi7ufUtkwWjcJLkACOE4LHVN2eXbfy9m/XpBBOXLP5bjf1hKKYH9alToOuDLyzRwXXMgQFS9eU1fQWUGOPyX1QIDJO1qxrtyCvGkNGx/urwqicFSK/QM1u1YLFyJEd/SJKuWQ4QDn6ZIPn7y6GUeVr6yD3rrkAz/OcDL7kZCP/M+cRnO7Umv1yvWfA3XVQVkxHziU17Mup85V1wUrjDBZnR/ZAAIicwez5PApb6Gk8k1ayW0wlJbAjS/fr/wHIgcRHh55YWlWcmkbtStClFWJowdowNlcPM3IwoDd9ebXeiTnv6E83JDQaDMznLZtayQPsSjfdUj3ced3lXBOK7NFTu6yvk9hImhwyoDZ1mYz/lgU5sIOnqVdzEBVVDLP5rMF+5xQ0u8M8yPwuKuXcops9dhk/zSquuXvf+sb+3hrDy5RgbJDzvgOhZSRtERLTzcB+4Q66LbyGT98YW72S04EfJuZVyr27wtE970FAn4YmiU5JpIL4ZWYJ+67IygrRLMLS9Vyelx1W6XyoFnudX/TEdE7mvJ1WO+hbfBTRbWhkUmf80xt5NdecbwyVULik9OYaCNU8FzuTJSOsid1n4JCFcGEhp2oz6dDtDPAltTLxd X-Bogosity: Ham, tests=bogofilter, spamicity=0.024367, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Sun, Oct 20, 2024 at 05:55:10PM -0400, Liam R. Howlett wrote: >* Wei Yang [241019 22:46]: [...] > >Don't state the code, it's stated below. > >I am still concerned about jitter that this patch set may cause. > If my understanding is correct, the change here won't cause worse jitter. Below is the dump result when this case happens. Let's name those nodes: n1, n2, n3. maple_tree(0x5611079e1680) flags 9, height 2 root 0x615000001c1e 0-18446744073709551615: node 0x615000001c00 depth 0 type 3 parent 0x5611079e1681 contents: 0 8 18446744073709551577 0 0 0 0 0 0 0 | 02 02| 0x61500000210c 10 0x615000001f0c 23 0x61500000120c 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0-10: node 0x615000002100 depth 1 type 1 parent 0x615000001c06 contents: 0x1 0 0x3 1 0x5 2 0x7 3 0x9 4 0xb 5 0xd 6 0xf 7 0x11 8 0x13 9 0x15 10 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0xa 0: value 0 (0x0) [0x1] 1: value 1 (0x1) [0x3] 2: value 2 (0x2) [0x5] 3: value 3 (0x3) [0x7] 4: value 4 (0x4) [0x9] 5: value 5 (0x5) [0xb] 6: value 6 (0x6) [0xd] 7: value 7 (0x7) [0xf] 8: value 8 (0x8) [0x11] 9: value 9 (0x9) [0x13] 10: value 10 (0xa) [0x15] 11-23: node 0x615000001f00 depth 1 type 1 parent 0x615000001c0e contents: 0x17 11 (nil) 19 0x29 20 0x2b 21 0x2d 22 0x2f 23 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x5 11: value 11 (0xb) [0x17] 12-19: (nil) 20: value 20 (0x14) [0x29] 21: value 21 (0x15) [0x2b] 22: value 22 (0x16) [0x2d] 23: value 23 (0x17) [0x2f] 24-18446744073709551615: node 0x615000001200 depth 1 type 1 parent 0x615000001c16 contents: 0x31 24 0x33 25 0x35 26 0x37 27 0x39 28 0x3b 29 0x3d 30 0x3f 31 0x41 32 0x43 33 0x45 34 0x47 35 0x49 36 0x4b 37 0x4d 38 (nil) 24: value 24 (0x18) [0x31] 25: value 25 (0x19) [0x33] 26: value 26 (0x1a) [0x35] 27: value 27 (0x1b) [0x37] 28: value 28 (0x1c) [0x39] 29: value 29 (0x1d) [0x3b] 30: value 30 (0x1e) [0x3d] 31: value 31 (0x1f) [0x3f] 32: value 32 (0x20) [0x41] 33: value 33 (0x21) [0x43] 34: value 34 (0x22) [0x45] 35: value 35 (0x23) [0x47] 36: value 36 (0x24) [0x49] 37: value 37 (0x25) [0x4b] 38: value 38 (0x26) [0x4d] 39-18446744073709551615: (nil) Since n2 is already deficient, removal a data from n2 would need rebalance, which is a jitter if my understanding is correct. After this change, removal a data from n2 would also result in a deficient node. So this is not worse than current behavior. Do you have other cases in concern? -- Wei Yang Help you, Help me