Date:   Fri, 10 Mar 2023 12:58:42 -0500
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Peng Zhang <zhangpeng.00@bytedance.com>
Cc:     linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        maple-tree@lists.infradead.org
Subject: Re: [PATCH 1/4] maple_tree: Fix get wrong data_end in
 mtree_lookup_walk()
Message-ID: <20230310175842.qkw54rj6zg7dkymd@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org
References: <20230310140848.94485-1-zhangpeng.00@bytedance.com>
 <20230310140848.94485-2-zhangpeng.00@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20230310140848.94485-2-zhangpeng.00@bytedance.com>
User-Agent: NeoMutt/20220429
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?agKxnoI+twNdKuttUPikaj4UnlHEivRw2kQSN4KWA/5Uf2WIdq5N27+KttpA?=
 =?us-ascii?Q?NFg2a0rJfzH7eqPYGgqNb1OQQhAS3yfi74w8Aj5fbcvhcSqcs+pAPut9rsHU?=
 =?us-ascii?Q?eL+NzjE5PzAqZInmozZYKq9a+VYCnAScCQpASLvhvDbAzN6MDUXdbUk9G/Dz?=
 =?us-ascii?Q?bxQf5h+CAnQhQ6sjIzVDSnFgWYNl9qtkqs+3liCvTmVaO9a9qw0Liod+lYVZ?=
 =?us-ascii?Q?GQ9asTZgmRduwxcgR8oGq12lAyAn5pY+Cyqbaxk5WXm9Tksz5gtJNlTPnTDg?=
 =?us-ascii?Q?OpFNIfzFqllXi96bXyuXrilcjZon5n5TrEYWO0+ryNCUJV4j8rW+KuRMMTBL?=
 =?us-ascii?Q?ZVPz9Y8gmxKlzMSe32a7OMYjlroeQCK5VR3zaGlgTsMwqEl6SbpfX6pMv2TH?=
 =?us-ascii?Q?QGGpTI6BWZz/WnbkxdG1l2ldIS7liZr6Fc7SSf6RCyo6YGzZNFTA+EOQZHir?=
 =?us-ascii?Q?yZlk/bVEyK8z7ktHx32ghVpyHxk1cymVwhGIqIXEdPKhGQ3yK/mi2hqlPuFF?=
 =?us-ascii?Q?zjrcp8OWX2wqPVRTZnWFeoRJkd4nNs6F1UZ+yqOpiJ3DKpyfSVTY3S2cd4lv?=
 =?us-ascii?Q?QF2MGXicK+/+LJR4Nvz1ITlaYiShkps0lVclRrZgJ5Hhguwg3bNv2VlY6Wzl?=
 =?us-ascii?Q?Sa2hYLAsgccF2WbRtCGHf6FTcjykkmCj2gJmwodPmbnzA87so+BInlGvdUH/?=
 =?us-ascii?Q?lJUBG7rCui+6aXH0YOmp0H6lP0vO+/U8DP73rZe+le95bm/Di6YmnbjxV3qK?=
 =?us-ascii?Q?SzXRGvtJUrda97weGvpfl3oZ7TYfRTYojnKJZYnIz2J3Y/Z+nF5eDoVuL8oz?=
 =?us-ascii?Q?wN6dePQkoK97lSUgpz1IsvxKLLy7rAc6jqy0dqAo7cLIpyIU2ebdEWKFNmiE?=
 =?us-ascii?Q?ZM+Qa9mrrAUoKqAQxxleNcsUH4a81X6LMcRPCxL1T4M0CFmHM8gUDIWc/dzl?=
 =?us-ascii?Q?EdSRwUNPIM1xK1daqsnzmqCOF9lFy5Xn1Bg8bWLo96TjUmwZUEOj5iLs5Ibb?=
 =?us-ascii?Q?pzFxcLousOHIXs1F+x3Ij15ax/Sm2Mz9eH2xqYOATLTikZv+6VgexbLx8K+d?=
 =?us-ascii?Q?q8kOI3q5g8zb7r89QVb4QaCGbMx/dYtVQX5KHO/d9vL+OHPsUUCL64F0J9Lz?=
 =?us-ascii?Q?VOvq9Cs6TRhHiwbYv1XBbueK0tEOLauSQlx73BuB1eYT2YjAnKgr3jTzofTc?=
 =?us-ascii?Q?EohBshiOxGPbq1rfkQmM1xu1yzkgImfjxO/z96drRwi17memntnjttjtldYu?=
 =?us-ascii?Q?zwZCHTmMEKwPGtg0FEEe6MU6jz2bQHUbyJ5yE+uOLa48y+51LaXufP9XVq+v?=
 =?us-ascii?Q?Yx7d5rOFtA8WSV4nngrzJ+gK35+oDMhnIJtqhuOyXwhwqiyzSY5tffVw7NEU?=
 =?us-ascii?Q?9p9mu+Xk23VEJYpfzALtdlJKW1WfxYaZFHZ8xLWnEpPtfkorSYeyvuegEDJA?=
 =?us-ascii?Q?QA+Bjo61STTBfjyarnIXhB4K79jnsLVQoLB/3NhPWrp16EYDNt33LJz6vRU0?=
 =?us-ascii?Q?RUEZ/6NDTQFduOSf1xemzNtCno7ueoLwm1j7nXzoLu8sPt0tvQ2/GZ3poWcD?=
 =?us-ascii?Q?B5flXndYW4wxQTIs9dW/0BfavLa+lvFbNf/inV/gwVgFc2Rw1NocLVHxHX0M?=
 =?us-ascii?Q?fg=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: TO1cPS4/BxJPu4zl3FUKL/eBfCuizfqOymtxBPGtpTHYl2smTwCTz0L7Sxa+HSulmb+5PFtKbJs0ucyfnWJhIK/Of05uEa6Ui4FhDM2prWKecQvdLze9uuGe58BYIvgec4NzhI/z5ivN0ZPD0XVj+rVnk1+1gGZR1luHSHR56zOtvw8wEBra+GREoKT2PAnw0ALxPTmzRJjc/fbiUZ1v/WHfhT56FO8cxa8T+di0yYPQGqMqCThZ8x7XlZgKniL0Fq1fFjO1aQ+quwppHSkX+U62crsdYeOTcr1KFS4FIqNuxRGBg35oRd4sUgDBNhDf3kasAoIJhVQJ+drgemla/b7T6bO3/LjTORhnStGyoIt2or0kaM0wnAFRaHAIjiMwxMK6Bfia2aQ9JaGps7z0fsUxU9u8+gZxptoJfjbPxbhRsWaBZoRcBWaoW9V74HQXA9mS45qbvTQriODfKSZXDyNOBL9lOzLqHX4ZhjiliXtSHiXXn/K5NbrDrcUGP5zDp7ny3fCyh3em6d4Ds2q/sJj2v1mbdl9WsQiAyUeJ5UEpyo+no7RKHmMuE90F/19NS/GCtrx9ft7TibFKrP7xInPcAhGbASUHO3U527T+uNpckMOgiMh47LyS5UuV43XVg2aGUm5EFlAu9oCHF67r05YIaLY9PDsaN44fKkOqsXszylCSw2ySqDa24SRS1bWRIiAombKQ1YETSzSTShTUFZ8Y/Rt4MX3KKgMzxSPB1ydX4f+vpiB2LK+HdH3lyOs124P44lzo/Ax697lQiI/j0FGxX1nLvmnNDm4A+XNTsSCz0dVHxn3WhOt0FIeSbhVrDEiMg70s3J7K+bx+dyXj9FqCX1hQfNFD1+xhjI/Fm3afGKb1eZ5SmC8vFUqyoD/M
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 6ae0e1dd-6929-4f8d-1dae-08db21911785
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 Mar 2023 17:58:45.2881
 (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: L4Bi6oqJr4YKjfsHRkcOGkAI62M5jIuUK+DDEtdcMK6SA5FzKXQ9O+TNKPUCsh38hEvjwxdYLkfSES0Ahc+vsA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA0PR10MB7351
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-03-10_08,2023-03-10_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 bulkscore=0
 mlxlogscore=857 suspectscore=0 malwarescore=0 mlxscore=0 adultscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2212070000
 definitions=main-2303100143
X-Proofpoint-GUID: MkIH_ZVdrlgwUGFDKVwsqN7xAcJr33q1
X-Proofpoint-ORIG-GUID: MkIH_ZVdrlgwUGFDKVwsqN7xAcJr33q1
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Peng Zhang <zhangpeng.00@bytedance.com> [230310 09:09]:
> if (likely(offset > end))
> 	max = pivots[offset];
> 
> The above code should be changed to if (likely(offset < end)), which is
> correct. This affects the correctness of ma_data_end().

No.  The way it is written is correct.  If we are not at the last slot,
then we take the pivot as the max for the next level of the tree.  If we
are at the last slot, then the max is already the correct value.

>Now it seems
> that the final result will not be wrong, but it is best to change it.

Why is it best to change it?

> This patch does not change the code as above, because it simplifies the
> code by the way.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 15 +++++----------
>  1 file changed, 5 insertions(+), 10 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 646297cae5d1..b3164266cfde 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
>  		end = ma_data_end(node, type, pivots, max);
>  		if (unlikely(ma_dead_node(node)))
>  			goto dead_node;
> -
> -		if (pivots[offset] >= mas->index)
> -			goto next;
> -
>  		do {
> -			offset++;
> -		} while ((offset < end) && (pivots[offset] < mas->index));
> -
> -		if (likely(offset > end))
> -			max = pivots[offset];
> +			if (pivots[offset] >= mas->index) {
> +				max = pivots[offset];

You can overflow the pivots array here because offset can actually be
larger than the array.  I am surprised this passes the maple tree test
program, but with a full node and walking to the end, it will address
the pivots array out of bounds.

I wrote it the way I did to minimize the instructions in the loop by
avoiding the overflow check.

> +				break;
> +			}
> +		} while (++offset < end);
>  
> -next:
>  		slots = ma_slots(node, type);
>  		next = mt_slot(mas->tree, slots, offset);
>  		if (unlikely(ma_dead_node(node)))
> -- 
> 2.20.1
>