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;
Date:   Tue, 6 Jun 2023 15:41:01 -0700
From:   Mike Kravetz <mike.kravetz@oracle.com>
To:     Ackerley Tng <ackerleytng@google.com>
Cc:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        linux-fsdevel@vger.kernel.org, willy@infradead.org,
        sidhartha.kumar@oracle.com, songmuchun@bytedance.com,
        vannapurve@google.com, erdemaktas@google.com,
        akpm@linux-foundation.org
Subject: Re: [PATCH 1/1] page cache: fix page_cache_next/prev_miss off by one
Message-ID: <20230606224101.GB4150@monkey>
References: <20230602225747.103865-2-mike.kravetz@oracle.com>
 <diqzttvlom5g.fsf@ackerleytng-ctop.c.googlers.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <diqzttvlom5g.fsf@ackerleytng-ctop.c.googlers.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?Mzgr3+y85wffJ1NAdcfxLuPeGvtmUPUDJzCo27uz5W6xb/++K6uLKjgPsa9Y?=
 =?us-ascii?Q?zZxzwf7Aui17zzh+q7LK78yrZwwO0ravRpW/knf4FUsPcUvPU83Ua8UqmEiZ?=
 =?us-ascii?Q?OtIAgExKE4TXmvI8J3yWcwMFQPaijf4YyhgeuVowFE3C+NZeLWcO1fFWwVJt?=
 =?us-ascii?Q?liffovnImeD801ps4CNqgcRx9zk9NxonUKP5hT1JelJG5ECz/1/2vRW8AheA?=
 =?us-ascii?Q?W2AtUjGk/+OWMmt8qbtTP4xGRSTXeB3RpwCtm9LkvlEDFzmPcyXC65dJGps1?=
 =?us-ascii?Q?+DTFcagvVlB+MdCvK0JTBPyieoaxPodOFkiKDHSjrmmMmCj1f69iBs6tEhpm?=
 =?us-ascii?Q?ovvcQ+kKhDb5mdMq2E9FPW/EhTzr663wOTJ2Cuebqqor7V8s9zTuDznvtJVw?=
 =?us-ascii?Q?IMWUy0h1ilsutaj5kUtfvloJDD0ZUNe4FubZ6spLqgWdp8DKOX0BO8PI0cj2?=
 =?us-ascii?Q?zPfStXZiHCXpivq/WNRsn4CYouAB8H3mbROswL8pLSs33OT2kmzYfYzFaBOd?=
 =?us-ascii?Q?HVDSjrSg0XXs0Z+NeBkdPlBLkgmTmM/MElPSkrU+RUFGhUXVye4qwhHJSQtU?=
 =?us-ascii?Q?Du3fdyeCLwVMPxNm4aZrqsw9PgbvHEGbSySgRAwgi/mwEdmnPZj3FHxu1Z+e?=
 =?us-ascii?Q?PsZvnDOQny4gTKtIxShsHmztVQq2qFYkRrqOf0y+7lYuMoyI8pouoky58MUm?=
 =?us-ascii?Q?nlcNoDqQ/ysRRo4pk2t4q+CUtGHXsovDhZ+nnc1fc2xqOFVKfn3Hk3fqHUuS?=
 =?us-ascii?Q?LFh8lJQ2S2bYae7XpaJlnmjC/DuaBwXt+FbAaxuGCnrADrhgKI+OnQfSyvGZ?=
 =?us-ascii?Q?IIhYJHvUn4pp68nCOPlC8ValUoK9TARsmM81bRgGelPoGhXvKgKfCkmZ9y8+?=
 =?us-ascii?Q?skNSFeBVWGjf+O3jPgXgwRkIqcKP6zh1tB0Yv5IfH1ft9dSqnxl4DBi8MLC5?=
 =?us-ascii?Q?G7f06XJExluS/6cZ7fEX9RMjsJEhu3GzHwkII/Irt2Jiu0KgK8GflT6UgYj/?=
 =?us-ascii?Q?fGhWBFGsBjuHy7OIkIjyNORihgkTkmIEIbxmhLt1ORuT2/7lHACeSGw6C+xC?=
 =?us-ascii?Q?wJEbaMY6BQ4A7Trm9oWYDu6HqLK+vx9tx5XQskBUnnFzRC87UvKACXYL2HYx?=
 =?us-ascii?Q?b+00lOpvKv8Jyvsl5K7PFMj8Es/MxmzjDFdmaEqAiLGkSWNj+jzdvfvl2lAn?=
 =?us-ascii?Q?FlJXmdrAYc4U3LOfUUFd1/OMOm8iqvt0Tirbj9SxWqFm1+b/nvHvFFpUPH5w?=
 =?us-ascii?Q?UhjBEqQVfitDvi3puAM6ecP5spo1H+3XL+kB+nBU4WAVuTQKtoTIoNkNHrB6?=
 =?us-ascii?Q?pO7eBVHMnPdpexZdckItJCrP6zMrKTHC/dAuh5oIqgFa9pDf/x0JDTLClTQy?=
 =?us-ascii?Q?ScKas7wGZZSM8o87dWXveaf6LBuxbIYxg6cFHPOC70ms5ZaBBPkOEpKTBrjY?=
 =?us-ascii?Q?hd8+pSamAYfF339M0Q6hKCrB/kuyp3Qj/L1nRl9/bfefZryMTXyZYHT5m86H?=
 =?us-ascii?Q?dHqBHz5PwXu0vIqbQ7ldJLmSSBMKyC52JrtbGzRgfnXWg3bOEKT7DPWJ4H8y?=
 =?us-ascii?Q?PYe6lsXSt8Iq3YSJvlA8r9A49bqMgOJb3FP6CibJ?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?Qis1yVD9hTrGu3RIcKvhol220wy8Cx1mfXm3eWxM5RLP/wIkSfAdy41EitQO?=
 =?us-ascii?Q?OhUPWTldrO9BL+Yga0zZd5aW+Y1LoaHGBfi+ScospFNcKZuQRy2ZOHQ8ZDaY?=
 =?us-ascii?Q?EbcYJDNPNQ4DzQThHA6n7ioGpWWB56YPJso5EVpcwrmRGcEbavxBSdFS1iNq?=
 =?us-ascii?Q?eLpWciHCpvpby7Q/fyKzr3WIPWn5Rt26Bak27/mUeWXBBh+QmRgDCnwbMcxr?=
 =?us-ascii?Q?3vw3EIoAaLhaH6XoGlsXKsgrNVOfHT3JgTimRvdTmdkY0ITt9Bt9iM51Jewb?=
 =?us-ascii?Q?6pDkhtSlCcN7DZ0Yslv3dWLLVl6yO0hC9ymk8g1Mm4nVWNZr8FqIiBSiToU3?=
 =?us-ascii?Q?g9n/JStLKLHqNweCyLbxJIyu5p8PIw9/4rC32OWgTfOqIaUR1KlNH+m5qMk8?=
 =?us-ascii?Q?8TnrFhfIm8ApjOETXaOQHdxcoCYyyvwvrQcwzP66BA8KPJKupyhgpbqSZ57u?=
 =?us-ascii?Q?n7PFUKh5XhoMtn0ZiakVMh3B/8xYyymHih/icTl5vxBbAIwbBcCJaj9gW71M?=
 =?us-ascii?Q?QkKv+kT7PeVlhJe9jIMks1AQwoqOYRPb/4tD4h23xq29hT45XEERe3RsXqph?=
 =?us-ascii?Q?Y7eY7t726thTxa1oYGccVLNsj7RDSY02vrRNwJlOC3BSR3qQ3xPCU65XiRMd?=
 =?us-ascii?Q?KA/mLn59yYP9AymB0Lrsxf/E7GSApv/kUJiyVDCXL7u8z3dIpOO0cXWCg9A2?=
 =?us-ascii?Q?Db+yJcXxk/Ifh/wBnIHq317AgQtjH+q2ueWxGLJbLDawsT8uKdY9Me8J6hDP?=
 =?us-ascii?Q?bco9O5s/XzQeZwrDoSP8lMkye+E03jNVcSh6jSJPMkmBi5FQbfiNqLaIPZWu?=
 =?us-ascii?Q?vW/hDJHDZg7PJD+i0Iy6ypFF/moLWAl5aU6DE0T66AayaLFwNp7HZdP3GELf?=
 =?us-ascii?Q?oSmX2a68Xi+Qaj1MDLIaaisALkrBvTdFkMlWXCq8TKlfxyQYid1gRvhb1scG?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 125dcb6c-cd26-4f4c-41fd-08db66df1c0f
X-MS-Exchange-CrossTenant-AuthSource: BY5PR10MB4196.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Jun 2023 22:41:03.9927
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: o5vXlCbjjRsVpRdutD+uiQat4c9UWV62XAmALHJ67MZchrbx6Ybffyn7uEbt5HOQnOowGh+qfix30qbZM1TbBw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW4PR10MB6462
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26
 definitions=2023-06-06_16,2023-06-06_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 suspectscore=0 mlxscore=0
 malwarescore=0 adultscore=0 mlxlogscore=999 bulkscore=0 phishscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2305260000
 definitions=main-2306060189
X-Proofpoint-ORIG-GUID: Q2hCoZJxXP2RZqvGcRJLwOiLacu2sO-z
X-Proofpoint-GUID: Q2hCoZJxXP2RZqvGcRJLwOiLacu2sO-z
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,
        T_SCC_BODY_TEXT_LINE 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: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On 06/05/23 17:26, Ackerley Tng wrote:
> Mike Kravetz <mike.kravetz@oracle.com> writes:
> 
> This doesn't seem to work as expected:
> 
> Here's a test I did
> 
> /* Modified so I can pass in an xarray for this test */
> static unsigned long page_cache_next_miss(struct xarray *xa, unsigned long
> index,
> 					  unsigned long max_scan)
> {
> 	XA_STATE(xas, xa, index);
> 
> 	while (max_scan--) {
> 		void *entry = xas_next(&xas);
> 		if (!entry || xa_is_value(entry))
> 			return xas.xa_index;
> 		if (xas.xa_index == 0 && index != 0)
> 			return xas.xa_index;
> 	}
> 
> 	return xas.xa_index + 1;
> }
> 
> static noinline void check_find_5(void)
> {
> 	struct xarray xa;
> 	unsigned long max_scan;
> 	void *ptr = malloc(10);
> 
> 	xa_init(&xa);
> 	xa_store_range(&xa, 3, 5, ptr, GFP_KERNEL);
> 
> 	max_scan = 3;
> 	printk("page_cache_next_miss(xa, %d, %ld): %ld\n", 4, max_scan,
> 	       page_cache_next_miss(&xa, 4, max_scan));
> 
> }
> 
> The above gave me: page_cache_next_miss(xa, 4, 3): 7
> 
> But I was expecting a return value of 6.
> 
> I investigated a little, and it seems like entry at index 6 if we start
> iterating before 6 is 0xe, and xa_is_internal(entry) returns true.
> 
> Not yet familiar with the internals of xarrays, not sure what the fix
> should be.

I am NOT an expert with xarray.  However, the documentation says:

"Calling xa_store_range() stores the same entry in a range
 of indices.  If you do this, some of the other operations will behave
 in a slightly odd way.  For example, marking the entry at one index
 may result in the entry being marked at some, but not all of the other
 indices.  Storing into one index may result in the entry retrieved by
 some, but not all of the other indices changing."

This may be why your test is not functioning as expected?  I modified
your check_find_5() routine as follows (within lib/test_xarray.c):

static noinline void check_find_5(struct xarray *xa, bool mult)
{
	unsigned long max_scan;
	void *p = &max_scan;

	XA_BUG_ON(xa, !xa_empty(xa));

	if (mult) {
		xa_store(xa, 3, p, GFP_KERNEL);
		xa_store(xa, 4, p, GFP_KERNEL);
		xa_store(xa, 5, p, GFP_KERNEL);
	} else {
		xa_store_range(xa, 3, 5, p, GFP_KERNEL);
	}

	max_scan = 3;
	if (mult)
		printk("---> multiple stores\n");
	else
		printk("---> range store\n");

	printk("page_cache_next_miss(xa, %d, %ld): %ld\n", 4, max_scan,
		__page_cache_next_miss(xa, 4, max_scan));

	if (mult) {
		xa_store(xa, 3, NULL, GFP_KERNEL);
		xa_store(xa, 4, NULL, GFP_KERNEL);
		xa_store(xa, 5, NULL, GFP_KERNEL);
	} else {
		xa_store_range(xa, 3, 5, NULL, GFP_KERNEL);
	}

	xa_destroy(xa);
}

This results in:
[  149.998676] ---> multiple stores
[  149.999391] page_cache_next_miss(xa, 4, 3): 6
[  150.003342] ---> range store
[  150.007002] page_cache_next_miss(xa, 4, 3): 7

I am fairly confident the page cache code will make individual xa_store
calls as opposed to xa_store_range.
-- 
Mike Kravetz