From patchwork Wed Sep 11 14:27:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13800654 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 81A44EE49B7 for ; Wed, 11 Sep 2024 14:29:18 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BC787940042; Wed, 11 Sep 2024 10:29:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B780B940021; Wed, 11 Sep 2024 10:29:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A66E4940042; Wed, 11 Sep 2024 10:29:17 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 8C732940021 for ; Wed, 11 Sep 2024 10:29:17 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 339151213B4 for ; Wed, 11 Sep 2024 14:29:17 +0000 (UTC) X-FDA: 82552689954.18.5E93CF1 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf21.hostedemail.com (Postfix) with ESMTP id 4B2211C0007 for ; Wed, 11 Sep 2024 14:29:15 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=mecmS2LQ; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726064878; a=rsa-sha256; cv=none; b=Oe6Jgdq9CutFaY3xXvZbGaqHikjFlL5cjwW1wWZtTSbxJytVEjR/y+qbVR8jrFxxxUMx9+ gfsQ1PSL5qRmzIXH1NAcTI8iJ7QD/SY7Iixn4atedB/dg9FbTrHjJidpzdUy1fUam2hPg6 SiD2o8H7R/TbsJO5nTZrmoA/lESge+g= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=mecmS2LQ; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1726064878; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=hTiOL3lKqHTHQbMLysWfQFchzynQbjiI0iltu+yDx88=; b=rTO9yoElQDWjIwOSe6V3pJ46mPPLGCvposCsm2fmbEG7FJdMCKQgRp/WVJM9nPI3gOjx+P nGrtEn0zVK+nCIo+E8egfwqi0L2FpAUtbTU47JVeoANmiIUseWNAjERnKNapdkFwZCdJUX +fa+/hZ78TkA3HCl3NYnVdAybQPok/s= Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5c3ca32974fso7607411a12.3 for ; Wed, 11 Sep 2024 07:29:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1726064954; x=1726669754; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=hTiOL3lKqHTHQbMLysWfQFchzynQbjiI0iltu+yDx88=; b=mecmS2LQ6yqyBiHLRfoG8fg9Uh/73kihQVMGAW5P1nLPMKIKFo7op2Wxqodrrp9Q59 2SYPhYV0hFbtYsIpbzTD0cIfS402MwKspZf01Q7EYm1awXle0PfnTFPlbbjAj1E0dt4r 4VDboDJAtizKS+xpbQzNX0gRr4B93ELQhcY0/I1tlAwAihvabSy18xD6hBr3A3EYdhu3 ayYycFUxBff1C7x1KWkOfLqADOFys2lkQdZ+pUW+8OYSVFi+TAMJDTUx5GJX6Uw++Aju OtPIPttIIXVN0Loh62UJzyEuyVCw/9Lm1eEwltZIO0VEaHnAnv9dg+P5M+8ZwWzuidpM ToqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726064954; x=1726669754; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=hTiOL3lKqHTHQbMLysWfQFchzynQbjiI0iltu+yDx88=; b=kUdpPzEFJrUZ3KeY2SPVMcn/qMCUYsa7Dr/zZUwmmzM0nPg4xz+/LXEKIFICoVRcjC LiMPt2cVKhEZJNH8sLZgah7Y69L1jcYhRZtuJYFs43emkHawD8knNJKNdCB3yNvap6nA WbSzefRBUxWhmn4pmRwk7Ad+pR99y8LRFM/QX2Ua/29wuS31Of9onUG3SIgqq1BbkRUA bOOSxmsnVu4Vl82TZbFobL1CQZRNa2HwzLz9USjQHGTlMno6QcfAB1cle0P6CJA1wg0J gq95RSrse7w9XCLRhJyB03RNNwVCVB1xEoV49HSiKNRHvd43y9GNRSOvLzqcJXIQZ5f8 9uEA== X-Forwarded-Encrypted: i=1; AJvYcCUm2E38a9XrBaoUz+BIzDZ9MMsUUC6dyBnS2yAS+PGh3JjkYPi7rxp0VGQ263QbVHx3QWqiw9nuMQ==@kvack.org X-Gm-Message-State: AOJu0Yw/ToEIjkjlXuOxeGrWvHGL1RmSxpWYETeAMCwJqJcNAgspGt/h MIQ8r/iQLNxE2wRMeMqzjEfNO6MakOy6LtIQL4oLOds/rSTC/Ytp X-Google-Smtp-Source: AGHT+IHzJAvYY6+HHTsmQrhbDr9CIQjGBaWL+VJLOOm3s/A4pNbIxvoFqZ58XlHcwWQ5UpFA8Qh4bQ== X-Received: by 2002:a17:907:6eab:b0:a8a:445f:ac4d with SMTP id a640c23a62f3a-a8ffab29292mr410713966b.18.1726064953183; Wed, 11 Sep 2024 07:29:13 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a8d25ced18csm615790466b.161.2024.09.11.07.29.11 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 11 Sep 2024 07:29:12 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang Subject: [PATCH 1/2] maple_tree: i is always less than or equal to mas_end Date: Wed, 11 Sep 2024 14:27:58 +0000 Message-Id: <20240911142759.20989-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20240911142759.20989-1-richard.weiyang@gmail.com> References: <20240911142759.20989-1-richard.weiyang@gmail.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 4B2211C0007 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: wm5j13o36do3a1m953xr1yrgupw83me4 X-HE-Tag: 1726064955-437700 X-HE-Meta: U2FsdGVkX18JG236MW4aDKlNol9ODg9123HmfxvCTocpB/QNNJgByGH8VwXvrUMQK0AFEYNjpPE/bFqaH17YVjoio02MKQ4v9PLQrPibnpZH+lkyPJzFDZEKu6/mUHbxkE84OqzP4ZrfrfyNEebgKN0O80/7XoCmZibb/SSnCyuo7zFZMO+6MStUV7hEqzpPzMdqwHnSDsE/lVHRn4/S9F+gAC5ih3FF6d/SETMTEkaEzsx6F4+VILcbWTfed9yqfxYDNYf3m4LdDufs0KbPkCRgZhwiWK5V3IrxBnxq2SaSWlgXomZXppVoh9eWmbN+9wMaTQLJSvdsYfYTsugVRU4fAvK8byN+TghvagAbxIoz3T/7IU4ie4p07Tgx48AwH41/8wuoTVsSsDrWefoDjRP0tENbr2nBSnv4U5yV/+54K2hCDhY1sdRdVys63+sRsXzQOfb6RscYQNeVtQiUYjIy/80Jfw2qkaH1Z56Z6pXR4ZJfFuvLWpF7ltHUIVJHGINnssrJxZ53qbbfy06N/Spv81N/eHiW6Bjf0P/lh9lIgFrLnpvrJ5AUjkq+hXfYAK6OaPiknPIKJzcO0pZz2cuF8c30Z0tsz7MSHFJByaPnSen+RH3nvGg4etMeLuinOMoD2Btp8RszSdy7TgzNw2mp0YBnk8XCbw/Dyz7hyibCrIGNPJcH2oIG7XT5tcbf7yRN0zNancWceqa4H9+N0+4dU9I+vmf/m6ziimJh0OlqSc8T0xibaKpoADn8fjw5pQvrjMslClE2dPLqtvSdxkk75axvU7f2lRGkDpRzB2I0E09k8RO2VSl1NaG/k07lo7IgBe6D1n1rTgiWaIctl4/nFp5HhH9EdMEaIi6dhxlJczCjdwsVaVy5qJarqu3/TrdQc4fOk01eNiFlqanjPcO8qrPxSzcQ3YEJYmIah1x8a88XaPVxvUt+6q+/teLBdAoZfK6eeHonCrPm7/V uFFGdCIS 1f+2878MR+um/nl25koqQE2pJgBBQsAkzfmAZrQd1IRqOsCC6DvDjjl3zd7FQVYRg9A/ra6TK0FxCP/mCw2NJpvx+IigiET4WDDNJcqZnRsjXidrxIXDEF7XTuw6WwpS3S3KFmTyhKrAeYZ+RUpb9KKrI3dEX50hpgeeqRTt57iPKmpsc/UFNg2trp/4hUQQ/4DQ0DmeS+k1pu6ewbelev3PF4bRKtiJ1x3InD83bxey1HpigcKqZuFHVEjaRAkXh+oI2c9WcOLXilWK2WwQSag58vyLneDTnGQ5HQswYTiKpdIr3AJU1FoiEW6piJ2zc3/1/vYzRVRVOfq2zXGzBKHGQaJaVsiHcCbC1W/BYmAbNZO7BNmn5XamSOOTjXptH5l7dfA5IyOrfGs8iDcQAIfRHtF5NKthE821OvEe/VZhoZnCMqGGbDADa1bUzuwjHRhjZUN5T8q2E2atYrC0xZP6aNCowbBlAYh/vn4KvmozlBpMKfQrqpj2RJoK/1CacNUjL2eY90WzFQcoTWTq31WXcXhXEZxJAEi1n X-Bogosity: Ham, tests=bogofilter, spamicity=0.000692, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: mas_mab_cp() copy range [mas_start, mas_end] inclusively from a maple_node to maple_big_node. This implies mas_start <= mas_end. Based on the relationship of mas_start and mas_end, we can have the following four cases: | mas_start == mas_end | mas_start < mas_end ---------------+----------------------+---------------------- mas_start == 0 | 1 | 2 ---------------+----------------------+---------------------- mas_start != 0 | 3 | 4 We can see in all these four cases, i is always less than or equal to mas_end after finish the loop: Case 1: After assign pivot 0, i is set to 1, which is bigger than mas_end 0. So it jumps to complete and skip the check. Case 2: After assign pivot 0, i is set to 1. ∵ (mas_start < mas_end) && (mas_start == 0) ==> (1 <= mas_end) ∵ (i == 1) && (1 <= mas_end) ==> (i <= mas_end) ∴ Before loop, we have (i <= mas_end). And we still hold this if it skips the loop. For example, (i == mas_end). Now let's see what happens in the loop: ∵ piv_end = min(mas_end, mt_pivots[mt]) ==> (piv_end <= mas_end) ∵ loop condition is (i < piv_end) ==> (i <= piv_end) on finish the loop both normally or break ∵ (i <= piv_end) && (piv_end <= mas_end) ==> (i <= mas_end) ∴ After loop, we still get (i <= mas_end) in this case Case 3: This case would skip both if clause and loop. So when it comes to the check, i is still mas_start which equals to mas_end. Case 4: This case would skip the if clause. ∵ (mas_start < mas_end) && (i == mas_start) ==> (i < mas_end) ∴ Before loop, we have (i < mas_end). The loop process is similar with Case 2, so we get the same result. Now we can conclude in all cases, we get (i <= mas_end) when doing check. Then it is not necessary to do the check. Signed-off-by: Wei Yang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 76b68568f77b..6fd62b7ef240 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1948,8 +1948,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, goto complete; } - if (likely(i <= mas_end)) - b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); + b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); complete: b_node->b_end = ++j;