Received-SPF: pass (google.com: domain of linux-kernel+bounces-203527-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
Message-ID: <b72a6860-33b3-4d2e-8cca-0ceab7b9d22e@oracle.com>
Date: Wed, 5 Jun 2024 19:15:13 -0700
User-Agent: Mozilla Thunderbird
Subject: Re: [PATCH 04/18] maple_tree: introduce mas_wr_store_type()
To: "Liam R. Howlett" <Liam.Howlett@oracle.com>, linux-kernel@vger.kernel.org,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        akpm@linux-foundation.org, zhangpeng.00@bytedance.com,
        willy@infradead.org
References: <20240604174145.563900-1-sidhartha.kumar@oracle.com>
 <20240604174145.563900-5-sidhartha.kumar@oracle.com>
 <hk6t5c4fw564ne4znymgwhoo6blgbtjnk623thr6zgfd25uvjf@pkhk5uqzykww>
Content-Language: en-US
From: Sidhartha Kumar <sidhartha.kumar@oracle.com>
In-Reply-To: <hk6t5c4fw564ne4znymgwhoo6blgbtjnk623thr6zgfd25uvjf@pkhk5uqzykww>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?utf-8?B?TlozL1VhVytuZldmMmprSlNlRkgxZEZkbmhwQ05HZHNjWklibWxYVWNwenNL?=
 =?utf-8?B?SE8rdWF2NmdqTVJUODNWdmIvalEvQVM4NWNlaUNTOUJKZXRiWVdUU3FWbDdQ?=
 =?utf-8?B?Unh1WEtwOGJqSTRUZnpyZ2cxYkxBV0J0cVBiZDNsRVpHTmRiaGNSODVhWktm?=
 =?utf-8?B?VUQ0V1Z3aGoyY2k1cmtxbkwrTlFLcklVWVAxRVJWNjhhbTU1K0c0ZjErSnpX?=
 =?utf-8?B?akpTbTBHOVZ2MlViQzZOY2xEVDMvS1RBckFJa2Jhd1NGbENwd0h5Qk9FTVpG?=
 =?utf-8?B?dzFvaUtVbEhvNTJiVlpFOCs4YUFkQVY0dGlOajU5MDFITFVIZ3pieE1yRllr?=
 =?utf-8?B?OCt2MTJkUjZiaDhzdThUM3N0dUxLV0NzTy9tcWZVcVlQZk9PUlhxYTlTaTYv?=
 =?utf-8?B?a012dEhZY3FSSDR5amlnZmlRaHRGWW1YcUJMSmIveUZlemd4M0t1UUhPK2xV?=
 =?utf-8?B?cjJDR1BSM2xzUWhxZVJCdVV0UkRXV1J1UlhkMVFCSFZtWENBaUVxTTJlTDRx?=
 =?utf-8?B?UE5RcFEwbGV4ejdJWUhUNGhrYnNTMHFrUVVVVU1oSTI5MVJDd3BkQktuazA5?=
 =?utf-8?B?WHN3eDE1UUVtUmZjWklITmNCWVJUamdncmR2bVdUQXBFRHN0c3loeHI3UEVN?=
 =?utf-8?B?VUNSV0pyOFFLOEFSR1dHd3RlRXNnemUzY1VEc05lUEx3eWErMjdnU2tYSCtw?=
 =?utf-8?B?WEo0dWNSWWtvNXliWjgwK1hxbUFEZlpRN0xwYWRhc3orSjROUzZjNEllcWxs?=
 =?utf-8?B?UlVGbjB1OVJWK0d0UUVNMklqRjdaalZIb3MrRHhmQVQrTVNoanJBcENBTnAw?=
 =?utf-8?B?N05BTTAyaXVBRmhvVEEzUG0zUC84ekYrZ3VmcG00WFVQOWlpNnlxVWNGSUEx?=
 =?utf-8?B?Q3lkWmlJbGxidkRNM1NWRHhFOUxDY0p4UWRJWHNGV0JONm1sTUZ5ZUtubU1K?=
 =?utf-8?B?eVBOT1FxNjNqT2hQeFVKUGZ3VGcrelpwUDNvV2wvQ3hQM1llUVpxVnJVVE1U?=
 =?utf-8?B?VElPZ2tLM1kvaXBUQXJhWUErV2pvdmZDd3F4UWsrMkNPeGZNdGRVRVRkV010?=
 =?utf-8?B?aTBHME9qek5Ja0pxdkdzeWlUTUc5bytvL2FudlZSZ3psU1RQRWlWaThMcWRW?=
 =?utf-8?B?anc4OGtyT3hGSmljakpRNTQ5T3lrcmI4d0hRdTAzN2R1RUdVS1BCKzNMMFBH?=
 =?utf-8?B?R3F1bG9SMjlhd3Z2TStNSWswSXlNN3BUYnUyYklRTXBwTXVMNzBLQlhQNU9Z?=
 =?utf-8?B?Y3V1S2ZyaXJuQzZiNlBpZ0xNME1COGZZNlBJQTNWaFpEYk9xRkc5OHZYOUMv?=
 =?utf-8?B?dnNKQ2Y1RENEMnpJQWVoN1NNUThUUUFLMUtXbnBMTVBOQXN2TGkvYUwwR1R5?=
 =?utf-8?B?b3lMSEh4TFM5Z2w1WGxvZDdlUnF0b3VteVkzUldTck0yS1BvUzJZbzRuNkVU?=
 =?utf-8?B?SkV5ZWRVb0FhVXVRNFBRUFJ5WjRJUy9sMy9tTUJ6WmR6RTJLYVJJclBhWWxx?=
 =?utf-8?B?N2JQNWxYQmF1bFBWK2N6amo3UTdMWklHaGJmTlU3OElscWtzekV3OHRoZWor?=
 =?utf-8?B?YlVOTnp0Y2QxZ0JWVWtOR3ArcS9VWCtOR1ZuUzJBcmc4MGF2WEVpOURDL3oz?=
 =?utf-8?B?MVZzL3hhSG03NVI2eHJNQ2hPRjN5UGN5aVJOcGZJSFFXLzhZeHRZSG8xZW1q?=
 =?utf-8?B?T2p4RDJEZGtjYndpWXpvd0wvL2MrUllMWWl4ajg2NU9QOUYyc1RaUGNZanR5?=
 =?utf-8?B?OHB2akhHYk1SOHcyU2lmdStCS0lMUmZCTk1FK2pnQWF4V2dmbEsrZkFsb1VE?=
 =?utf-8?B?TTMrTFYxdzVzdVBxdWVjVmpoOWk1V0VBcStxbHpTUy9GdE0xdGdaUFRTSmlt?=
 =?utf-8?B?WnF6MlhBMTgxWWJzeHFkRU1ZaHQ0WVQ2R3VoaEJwVGNRVGdibWV3bFIzaTd6?=
 =?utf-8?B?NTFKTU5XeThpOUFQV3hCSTRxUlYrbWF6THhqMXJiTDUrRGhoTzFvNzlpd3NQ?=
 =?utf-8?B?RnFnbkR2VFQvOXlXTnQ3bU41RUY1VE5TZjZRa1pFcDZKcmNrWlVQbWR4UE1x?=
 =?utf-8?B?aEtGWWUrbHVXNldKUnBWNFAra0Y4SkhCMHFJcitoQzJIQjVRcE5jTmNFM256?=
 =?utf-8?B?RkIrK0RQOEdPVmpXRXRvdXZBODVGcS9vSUM0S1JEeHB4TldqbUdLWjI5VnNz?=
 =?utf-8?Q?vBcZ7FOyZ2KjqihIODdyS/k=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	J8bo5hBlvJ0sInjOL9piGY6PyTLvfxi4lmtR5neYBFGnw0+7Fj54s658ZC/9X1iGzFABtGF0Nb84EmecgZYu+N4dDM9WxThIOwAMQl2/i9IzMIypRgcNQIWx7dyCNuCtjTYRwlq/xsgitAJjefJc2ba5FNqkYHcdqXL8q/RW/QdxVe9wHL26GPbu612oy+q+ZgihcnydUcn+0InTYozkuA5vhYJ4jvFHZkUpIJGq1KA/8tGeMabWHVnDvdvmvc+gzbRiimlqjQf4EZDw++31NSmBOW2tpwmst8Kd2soKXuVwa8xDTAs3jFa0KBAY/FSrelqoXWUdeeCNj8TowkCxF2Lkp6VwlwyN3tzK8e89Xm58icsusyoUFVDondKAPMGH8lC+mVXjEyFKjMNqS/XmF1I3MVMTpKINlB14RwUMGc1pN6hPy15LuEOqsCFSXq5F5ldmXfIDL1nVkxi6HmsUOg+hLiwmZTs0U53VEPODNcjmxoGyR5kqOAgSGgpzt3wt/Y4owR2z0P93HSBa0UNARiHOJes72PmNYZ1qdvxB24UYv57B7NMk2WrEe5E3YLXDXw/JF4H1PLjUSqt8i+9vG2WxHv0ejQdc6YIdMZqoLN0=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: bc9ad946-84eb-4379-c94f-08dc85ce8127
X-MS-Exchange-CrossTenant-AuthSource: CH0PR10MB5113.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Jun 2024 02:15:15.7987
 (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: NEAdG7NmblknJsqAqDY5QQBEigKNm40QCx8Q/G7nyJb1h4H4or0mnr7Ertbt1lsCn7L17s/Qs9/iY1Q+mA6Q/Gnty9x2D9Jtq/wDO2PAecE=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW6PR10MB7685
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.293,Aquarius:18.0.1039,Hydra:6.0.680,FMLib:17.12.28.16
 definitions=2024-06-05_08,2024-06-05_02,2024-05-17_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 malwarescore=0
 suspectscore=0 spamscore=0 mlxlogscore=999 adultscore=0 phishscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2405010000
 definitions=main-2406060016
X-Proofpoint-ORIG-GUID: PNeyW8QPndA-gIqL1rOWMgkype5HifLi
X-Proofpoint-GUID: PNeyW8QPndA-gIqL1rOWMgkype5HifLi

On 6/4/24 12:07 PM, Liam R. Howlett wrote:
> * Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
>> Introduce mas_wr_store_type() which will set the correct store type
>> based on a walk of the tree.
>>
>> mas_prealloc_calc() is also introduced to abstract the calculation used
>> to determine the number of nodes needed for a store operation.
>>
>> Also, add a test case to validate the ordering for store type checks is
>> correct. This test models a vma expanding and then shrinking which is part
>> of the boot process.
>>
>> mas_wr_preallocate() is introduced as a wrapper function to set the store
>> type and preallcoate enough nodes.
>>
>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> ---

....................

>> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
>> index f1caf4bcf937..c57979de1576 100644
>> --- a/tools/testing/radix-tree/maple.c
>> +++ b/tools/testing/radix-tree/maple.c
>> @@ -36223,6 +36223,37 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
>>   
>>   extern void test_kmem_cache_bulk(void);
>>   
>> +
>> + /* test to simulate expanding a vma from [0x7fffffffe000, 0x7ffffffff000)
>> +  * to [0x7ffde4ca1000, 0x7ffffffff000) and then shrinking the vma to
>> +  * [0x7ffde4ca1000, 0x7ffde4ca2000)
>> +  */
>> +static inline int check_vma_modification(struct maple_tree *mt)
>> +{
>> +	MA_STATE(mas, mt, 0, 0);
> 
> 
> Don't we need locking in here?

Ya, I think I'm also missing a mas_destroy() at the end of this function. I'll 
add mt_lock()/mt_unlock() as well as mas_destroy().

Thanks,
Sid
> 
>> +
>> +	/* vma with old start and old end */
>> +	__mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
>> +	mas_store_prealloc(&mas, xa_mk_value(1));
>> +
>> +	/* next write occurs partly in previous range [0, 0x7fffffffe000)*/
>> +	mas_prev_range(&mas, 0);
>> +	/* expand vma to {0x7ffde4ca1000, 0x7ffffffff000) */
>> +	__mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
>> +	mas_store_prealloc(&mas, xa_mk_value(1));
>> +
>> +	/* shrink vma to [0x7ffde4ca1000, 7ffde4ca2000) */
>> +	__mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, NULL, GFP_KERNEL);
>> +	mas_store_prealloc(&mas, NULL);
>> +	mt_dump(mt, mt_dump_hex);
>> +
>> +	return 0;
>> +}
>> +
>> +
>>   void farmer_tests(void)
>>   {
>>   	struct maple_node *node;
>> @@ -36230,6 +36261,10 @@ void farmer_tests(void)
>>   
>>   	mt_dump(&tree, mt_dump_dec);
>>   
>> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU);
>> +	check_vma_modification(&tree);
>> +	mtree_destroy(&tree);
>> +
>>   	tree.ma_root = xa_mk_value(0);
>>   	mt_dump(&tree, mt_dump_dec);
>>   
>> -- 
>> 2.45.1
>>