From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net [23.128.96.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DBF2B266DA for ; Tue, 24 Oct 2023 12:05:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=suse.com header.i=@suse.com header.b="HBQC3y3o" Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04on2058.outbound.protection.outlook.com [40.107.6.58]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6FE80120 for ; Tue, 24 Oct 2023 05:05:48 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=a3/7Oo0xzw1k0EsRpO6RQnHX1zXLPGSIn2pvXbOrjpZBr6H4N5xXaR1I7V6sYrVm9cAVXp9Ro9fZ8dG4W/jmrEOsLtZSho5yX7MJ4htzOzzKJG7oOM1p5X/T93nY+EHZjaTbj/zamLcVzTq2xO1FalLuk+IYbZsSoxwpmsqnNCM4KDbC9l1WEEnTFFRjp1I4a9MPw0xZG9QN6hWzOJMbwJX41QPCko4om2L2ynecRCVe9GETTKrVJOx0R8Oa+dZmKKXMFF/3pBIzsFNixuIbUXrzWiUhIO/EvdXVsitQkRLdmEY8jPAJbOvc1GKs8nhTpcWgy18oxEw8bsAOvZVrwQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=wFnwjdDx5+8F91T9G8iiViFcc+PDXF2e7IoURQms5ws=; b=TvaatsBAOvDnaBsvnFpViKPJoibxg6LCMara8nv8oLueft+PAmGX3kKLmHtMfjuqLGECduKeeW4j3mqUk5FOKpod8WXDeTmGpi6hQI3UZ0mH6fSLHez7TTxw9gl7X77WvwAnDSId2RhV64eOBwkWeNiLv3TWE5Z8TmWkmDRtKLfY7mVr15jpbj6nj/4NYU5G2cHsCjzO+1lWFJr8F9MMbk5AsJ398Pda4Vn5cEUP1reI9pCasaLXjPZfYTQrPdEDY5/LchQLRpbLL9mGuVfglC4l+hh/4UtCA3JszRRefrq9oigO/EuHIFuTfyWb+yiHKAKibGCDB7DECwgSguEx9w== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=suse.com; dmarc=pass action=none header.from=suse.com; dkim=pass header.d=suse.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=wFnwjdDx5+8F91T9G8iiViFcc+PDXF2e7IoURQms5ws=; b=HBQC3y3oGF7flkKBXi9KaKUa+pUoPbJseOhmOv8pqdGx4rTNIenqvR5U26dcKUBVNprnviaP9vNa+k24OUI6Gldt29EYaQP7JPkiYljDc3L0PLY/g02j1SVfCN50fbN/P75ktGqp4YCiCH8POcSd+6RmDm/ojm0/StIYKcyhKjyRjkZ7sp5MjDfA5kHsVV2OSvr2+4ilRTJd23x6j9ceEe849s4b77yHCo3GpZ1y/wYaOolpbZxR+By5aUt81D02zYI9TSObk05kupKUUT6C9KYtKMrW1CGKBHjgJAvavdu9SOB3b3lACoaop7xpuLDIDENHJi4lPDWQhI9H0wiEVA== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=suse.com; Received: from AS8PR04MB9510.eurprd04.prod.outlook.com (2603:10a6:20b:44a::11) by PAXPR04MB9188.eurprd04.prod.outlook.com (2603:10a6:102:222::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6933.11; Tue, 24 Oct 2023 12:05:46 +0000 Received: from AS8PR04MB9510.eurprd04.prod.outlook.com ([fe80::9f3e:3b47:5ccd:c47c]) by AS8PR04MB9510.eurprd04.prod.outlook.com ([fe80::9f3e:3b47:5ccd:c47c%6]) with mapi id 15.20.6933.011; Tue, 24 Oct 2023 12:05:46 +0000 Date: Tue, 24 Oct 2023 20:05:38 +0800 From: Shung-Hsi Yu To: Andrii Nakryiko Cc: Andrii Nakryiko , bpf@vger.kernel.org, ast@kernel.org, daniel@iogearbox.net, martin.lau@kernel.org, kernel-team@meta.com Subject: Re: [PATCH v4 bpf-next 3/7] bpf: enhance subregister bounds deduction logic Message-ID: References: <20231022205743.72352-1-andrii@kernel.org> <20231022205743.72352-4-andrii@kernel.org> Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-ClientProxiedBy: FR2P281CA0036.DEUP281.PROD.OUTLOOK.COM (2603:10a6:d10:14::23) To AS8PR04MB9510.eurprd04.prod.outlook.com (2603:10a6:20b:44a::11) Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AS8PR04MB9510:EE_|PAXPR04MB9188:EE_ X-MS-Office365-Filtering-Correlation-Id: c93a3211-1666-4ca3-1a12-08dbd4898dbf X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: WAotXbo4/OGuQbZ9Ih/pS20JpndaBLhr8PUwy4u0FWw6p2F92t535GMmKPUcNmOkVpFfUDRWzebEEmiLpdZhpkDvx1kMC9fzKLwUdJpj4/sNS5H1GanRfyfkh+GqIcFImJPKQs6EeJLGC5eaKFvy9ybU1sFRCttmHbPaej9m6FdZaUNRuRKxmCKCxq6oXmX2qPifEKaWL17v+iWMwqVkszUoIZH83BJE95QvjRmciukCltMxLNPLqDk4QT8Srat2GPbMat9Y1fJqMxfYF9XSHy9F8yGBrHHQ8QJNu9wqoNcr3YZk3rNX1eBa4/iKu11X1vsEPHMXyduIXP8LeCUbbeD5t2wrZJ+Lt/khXSIxh9yEBnImFs0JBaXLFsBTTqqvPOMDLIJHXiWJt0588v+tL+WRObe8/bNO/kg1uWvr14SHXkjyFb1Af4Ruhkm789kX2KDVfj3dD6yoQZlEq/8z5jWZyATtEk10Ks0bproBLPsBXCUQPFqn2KaVtaUYD/UxCpJ+7oFooRgbqo/oiN34GBXEjFUhW6BV6JLhnCHjBKzrKz2t1cWGxIGfrmntlS6Q X-Forefront-Antispam-Report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:AS8PR04MB9510.eurprd04.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230031)(7916004)(376002)(346002)(396003)(136003)(366004)(39860400002)(230922051799003)(186009)(64100799003)(1800799009)(451199024)(26005)(6512007)(9686003)(6666004)(6506007)(53546011)(83380400001)(41300700001)(5660300002)(8676002)(4326008)(8936002)(2906002)(6486002)(478600001)(33716001)(66556008)(316002)(66476007)(66946007)(6916009)(86362001)(38100700002);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?alNZWjd3VDJVMkxuRmcwNC8yWVdpTDA0S3FVTEl4c1I3b1A5Q2taNHdzQU4v?= =?utf-8?B?MWpRMDc3WmZ1a1JYbk55bkcxVFJqQ2swcWs1RmtldGNWdnE2cFgyVndUUEV2?= =?utf-8?B?cXZ1aHJNRVRYRkZjeGZCM09iZGk3c0xrR0ljQVQ5Ri81UUlIbUZxdXBQcXRw?= =?utf-8?B?d0lCbWJUZzhJOE50WUhKV0VpSGVzRU5CSWppNEtlNlV1RHp2aSs4SmxrY3p4?= =?utf-8?B?SlhYZERZRjlKMUUxd0hBZmY0RzNYUFZ3Vnl0cU90ZUtCVXRvSDAwaFdFRWNn?= =?utf-8?B?RGFUTUN6SjNoazdrbGxoYUxzOEQ5VitjZnhvc2xxRlBmMHE5S0tydlFKOFhS?= =?utf-8?B?Yk9WT1ZDVllyai9YNStSSVNDY2FjOTJTcDgzcVJmS2RheVYrcUNHMXdXSm9C?= =?utf-8?B?MWg0UzJZeW41MDEzUUdldCtlaHhiTVpkeE1XSUZEODByODhQdk14bFN6dmd6?= =?utf-8?B?TXB4K0lsUThkRHJXTjhxMmZvcU01ZG0yRzQzMm9sQ3BEOVlZSGo3dXM4UmxD?= =?utf-8?B?VTlaMUpIcnNMd3N1NTZsWmswRS8vbEpubDZEeVBFM2pTVXBLZnRmKzRibStq?= =?utf-8?B?b2NSaFkyUW40TERCQmFLQlE5YStoeVMwSTlUd2dXT0lkZFhCMUR6WmQ2VEZ4?= =?utf-8?B?dUp0SEUrY2tHcFUzNlh1WkhKQXZyTVVnVFUyZ1UwcjNGSXJ0TFBWUXhiK1BY?= =?utf-8?B?MTNQejBVM1hIZmZGb0JmZUowdTg0aDgycm9ZeDQ3RG5SU0xsb2o2WXZZVDZ1?= =?utf-8?B?MWpLSGlFek16cEFiR1FoN3QweWpQeEJxMHhzWkltMWRZNUZrNEpwMUVlczV0?= =?utf-8?B?RjFTT3lBMDhPVGtGK1ZaRXdhUGpVUHN5VXc5STNnRlFCMHd4N28zelZTakov?= =?utf-8?B?SGF1THZESjVKaXQ4UC9DQ2JzTDZNS1FpUW93Y1lmSmNnSi9qVmd3bWEyamJk?= =?utf-8?B?WkJjNWlPa3RiZXZrNXBRNWxZVENka2MzVUN1SzRySHE4RHZhOWRWbjZmcXgv?= =?utf-8?B?VlFBcXBZeno2ekVOUVBpZm1ZRHlOc2IvbEZzZ2V3aUh2L0hYWndna2RGU0xa?= =?utf-8?B?Q0puU1NINzV5RFdac0xsTjdVQlpMTjVxYlNvTlh5VzFYL1kzSG1ONjZrR3lN?= =?utf-8?B?SXpFSDVTQWxMcDFxOFNFVUdoYUp4Y1E3dHh0bzhYc29KMExmRTVTUDVWZVB1?= =?utf-8?B?WHZYUEpsNkJPd0xpcGZ5WjFFN3czTTRwOCs1NG56Nk8xdFUzV1JMcDFKWnF2?= =?utf-8?B?ZGQ1VnZnSmEzdU1CYUg0c3Y2NmlKblRsNFdoTDlKR05ZODBPUFdIM2VRdzls?= =?utf-8?B?a1NTRVE5dWxPSGY5VmkyUVpJbnY0VEMvUzVIZTZCR1NKbkdDeGtudUxCTGI3?= =?utf-8?B?M0dNZ2phc28zRWpFVmh3cGNkRnc5bHl1R2V2Q3JUN2Y2NWVEV0szYTYwV2lI?= =?utf-8?B?Ulh5STNCMnZOUFlabmlnQkdTa2c3REpmM0NtUU9IL2VDSG5aREtnYTVTZm1I?= =?utf-8?B?bmdkZnJzMWk0WmV6dmUveFd6bUUzZ3BLaTNPc2ozWkExcGFrbGs2cWV4a1hU?= =?utf-8?B?M2FYRFJqNkVzRnBPQU9OQlI5VnVEZkdIVmpvbUZDYjVYdjRuVmVMZzhIVmpx?= =?utf-8?B?bXRLTlRrdzZSZzFyRGFMZ0s5azEybDFPb3J4MHp4dFlTSThWRzJHV2JTOEw4?= =?utf-8?B?ZzFtZVZvNnpvY1lWWWlPc3hWak1rTHhsb0JGektWcklvVlNoR0VCRFozSkc2?= =?utf-8?B?MGFiUmpLRklkMDFvYTRiQ0FvYmk0c3MzSkpXbmJMalVhOVQ2TGtWMmJQN09Q?= =?utf-8?B?SGltK04rRGdkQ3BZL21MZWlBMGhnQUNreU00aXhzQnlNU3p2TlZaT2F5Y0F5?= =?utf-8?B?eDk3TU5ZaGtuQ0ZkZnBTYWY2RVBUczViRzQ0RGdCS2RZY0Y0cmRMOTYxeWdV?= =?utf-8?B?SjZVandmTWdDRzJjdkRHTFpDeHpPZG9uRmcvU0lmUnFQQ3NlK05Xb1Vkd0Qr?= =?utf-8?B?SHpNNG9QM1ZWY3lKOGwwRDZZdHMyMy9wenkzaWRXZG1nd2FHdkF0cFhSODha?= =?utf-8?B?Z0xlSDBmUWFneWJxYktjZGNRNmw0blp2b3oyeHRncHkydStsb2xTQVZyaEpt?= =?utf-8?Q?jcwUdb9n6kFsnBTlklrpM4H1h?= X-OriginatorOrg: suse.com X-MS-Exchange-CrossTenant-Network-Message-Id: c93a3211-1666-4ca3-1a12-08dbd4898dbf X-MS-Exchange-CrossTenant-AuthSource: AS8PR04MB9510.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Oct 2023 12:05:46.1675 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: f7a17af6-1c5c-4a36-aa8b-f5be247aa4ba X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: dEqG50SFXDllGbEYZ9hyBYxinMOZ7t1lwPV5rXB1gWr5hUKde8fuSKD7QzK9G1pZveiERRI88s0OXFrY3UBLyA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PAXPR04MB9188 On Mon, Oct 23, 2023 at 09:23:57AM -0700, Andrii Nakryiko wrote: > On Sun, Oct 22, 2023 at 8:57 PM Shung-Hsi Yu wrote: > > > > On Mon, Oct 23, 2023 at 11:20:46AM +0800, Shung-Hsi Yu wrote: > > > On Sun, Oct 22, 2023 at 01:57:39PM -0700, Andrii Nakryiko wrote: > > > > Add handling of a bunch of possible cases which allows deducing extra > > > > information about subregister bounds, both u32 and s32, from full register > > > > u64/s64 bounds. > > > > > > > > Also add smin32/smax32 bounds derivation from corresponding umin32/umax32 > > > > bounds, similar to what we did with smin/smax from umin/umax derivation in > > > > previous patch. > > > > > > > > Signed-off-by: Andrii Nakryiko > > > > > > > > --- > > > > kernel/bpf/verifier.c | 52 +++++++++++++++++++++++++++++++++++++++++++ > > > > 1 file changed, 52 insertions(+) > > > > > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > > index 885dd4a2ff3a..3fc9bd5e72b8 100644 > > > > --- a/kernel/bpf/verifier.c > > > > +++ b/kernel/bpf/verifier.c > > > > @@ -2130,6 +2130,58 @@ static void __update_reg_bounds(struct bpf_reg_state *reg) > > > > /* Uses signed min/max values to inform unsigned, and vice-versa */ > > > > static void __reg32_deduce_bounds(struct bpf_reg_state *reg) > > > > { > > > > + /* if upper 32 bits of u64/s64 range don't change, > > > > + * we can use lower 32 bits to improve our u32/s32 boundaries > > > > + */ > > > > + if ((reg->umin_value >> 32) == (reg->umax_value >> 32)) { > > > > + /* u64 to u32 casting preserves validity of low 32 bits as > > > > + * a range, if upper 32 bits are the same > > > > + */ > > > > + reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->umin_value); > > > > + reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->umax_value); > > > > + > > > > + if ((s32)reg->umin_value <= (s32)reg->umax_value) { > > > > + reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value); > > > > + reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value); > > > > + } > > > > + } > > > > + if ((reg->smin_value >> 32) == (reg->smax_value >> 32)) { > > > > + /* low 32 bits should form a proper u32 range */ > > > > + if ((u32)reg->smin_value <= (u32)reg->smax_value) { > > > > + reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->smin_value); > > > > + reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->smax_value); > > > > + } > > > > + /* low 32 bits should form a proper s32 range */ > > > > + if ((s32)reg->smin_value <= (s32)reg->smax_value) { > > > > + reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value); > > > > + reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value); > > > > + } > > > > + } > > > > + /* Special case where upper bits form a small sequence of two > > > > + * sequential numbers (in 32-bit unsigned space, so 0xffffffff to > > > > + * 0x00000000 is also valid), while lower bits form a proper s32 range > > > > + * going from negative numbers to positive numbers. > > > > + * E.g.: [0xfffffff0ffffff00; 0xfffffff100000010]. Iterating > > > > + * over full 64-bit numbers range will form a proper [-16, 16] > > > > + * ([0xffffff00; 0x00000010]) range in its lower 32 bits. > > > > + */ > > > > ... [graph removed] > > Yeah, tbh, the graphs above weren't really all that helpful, rather > more confusing. But I think you got the point correctly, that we are > stitching two s32 ranges, if we can. And we can if upper 32 bits are > two consecutive numbers and lower 32-bits goes from negative to > positive (as s32). Alright, graph removed. FWIW I think "stitching two s32 ranges together" is a great way to put it concisely to give some intuitive sense, it'd be nice if it can be incorporated into the above comment. > > > > + if ((u32)(reg->umin_value >> 32) + 1 == (u32)(reg->umax_value >> 32) && > > > > + (s32)reg->umin_value < 0 && (s32)reg->umax_value >= 0) { > > > > + reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value); > > > > + reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value); > > > > + } > > > > + if ((u32)(reg->smin_value >> 32) + 1 == (u32)(reg->smax_value >> 32) && > > > > + (s32)reg->smin_value < 0 && (s32)reg->smax_value >= 0) { > > > > + reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value); > > > > + reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value); > > > > + } > > > > + /* if u32 range forms a valid s32 range (due to matching sign bit), > > > > + * try to learn from that > > > > + */ > > > > + if ((s32)reg->u32_min_value <= (s32)reg->u32_max_value) { > > > > + reg->s32_min_value = max_t(s32, reg->s32_min_value, reg->u32_min_value); > > > > + reg->s32_max_value = min_t(s32, reg->s32_max_value, reg->u32_max_value); > > > > + } > > > > /* Learn sign from signed bounds. > > > > * If we cannot cross the sign boundary, then signed and unsigned bounds > > > > * are the same, so combine. This works even in the negative case, e.g. > > > > -- > > > > 2.34.1 > > > >