From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id C7CD245B2B; Fri, 18 Oct 2024 15:42:25 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 5D9F74025F; Fri, 18 Oct 2024 15:42:25 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.19]) by mails.dpdk.org (Postfix) with ESMTP id 4CA2A4025C for ; Fri, 18 Oct 2024 15:42:23 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729258943; x=1760794943; h=message-id:date:subject:to:cc:references:from: in-reply-to:mime-version; bh=onebX7KxgVlb7U+9wsbSTOVz3nM4nFiyFBGSW7prRGc=; b=BGXdrnMGjg4rtbRFRNBMXHP0YiXUE8Nw67fZU4ifIBmgGBQ0S2M6l0Jr cfC1U9BIPs6uNksC8cZWoI0f/yScZXyF+TFcOs2YlrH8Gxpgt/kmUmvMd XrrpvNYgytfG+qfgqNhatY4wN+Jcvw63Oq1mMFa89/6t5Yik0mU9J61n3 vbIoNlCHhbYFmilvcaGub6iFMiIxs/WrmFPLYN201vu4sS6zNKprkYZ0z MgTDAVOJxgHCyrwyMEewrSD3DrsIfIrnsfeVmoGet38IRxc3gBsjBUD4V vmvrjInTKdg0DMQxAKAffnI/RjrtAPPvYYibpmTz0dMtm38ecqiZp1wtk A==; X-CSE-ConnectionGUID: T41UC4DWQkOM5jfyLL1IeQ== X-CSE-MsgGUID: OBFYrxmAQhOauBemibG92g== X-IronPort-AV: E=McAfee;i="6700,10204,11229"; a="28251544" X-IronPort-AV: E=Sophos;i="6.11,213,1725346800"; d="scan'208,217";a="28251544" Received: from orviesa001.jf.intel.com ([10.64.159.141]) by fmvoesa113.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 18 Oct 2024 06:42:22 -0700 X-CSE-ConnectionGUID: cSvHKKQiTM+h0+3GdoxgUA== X-CSE-MsgGUID: GiQX+JjVToaiqusFSCF/Rg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,213,1725346800"; d="scan'208,217";a="116330477" Received: from orsmsx601.amr.corp.intel.com ([10.22.229.14]) by orviesa001.jf.intel.com with ESMTP/TLS/AES256-GCM-SHA384; 18 Oct 2024 06:42:22 -0700 Received: from orsmsx612.amr.corp.intel.com (10.22.229.25) by ORSMSX601.amr.corp.intel.com (10.22.229.14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39; Fri, 18 Oct 2024 06:42:21 -0700 Received: from orsmsx610.amr.corp.intel.com (10.22.229.23) by ORSMSX612.amr.corp.intel.com (10.22.229.25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39; Fri, 18 Oct 2024 06:42:20 -0700 Received: from ORSEDG601.ED.cps.intel.com (10.7.248.6) by orsmsx610.amr.corp.intel.com (10.22.229.23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.39 via Frontend Transport; Fri, 18 Oct 2024 06:42:20 -0700 Received: from NAM10-MW2-obe.outbound.protection.outlook.com (104.47.55.49) by edgegateway.intel.com (134.134.137.102) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2507.39; Fri, 18 Oct 2024 06:42:20 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=rdmt6MTOk4flgjADw6cTdw+Cjv3fZ9FoR4KvZ6lIJv2Y5MnN93nkXn5YRFevMbfhGV1ii3UIw0SGEGnYxoN3V941H7KQ5CLwQBp9g/PHiSRSnal+UB4z05/KECGGVcSrVXAeHmgKREzykl+CvWj5Z2cU+oZa8u9kzlqZbmQvyY4YXdg3Jb8zvCdYVYpAE2mJsOrkC5+4IDLsuA+PFWzu7vN81XWj4MoWFGoEA0nZZhx5CTVt2EBc3YOWRJzvdHi0LZdHv4xPDeyHP7uVO6U61HiCRowcF02MZIUpE50UN9qIZNnyhhQcMRxccz+dx1brDpGk5pkUnxBB4RTp0TWOhQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; 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=8ht20WrXiEMniGJA5QvgClNE4AFILZn53xX0IZTYKMY=; b=qtTgUMRtr+Kg0OukVbgMacAwEzEiKudqp/KETxIs8nu6j/AUaMn+Vh5LDd4FneJfPU7jaEcgf0sGWSwiOpTU3eV3wvRmABANHX5v3oLFBL/WB1KN0iVmFFdahn27Yfist11T4GyWMVOxK4iZqsX/nnI8RI05RljDBtGfkCQ5PgI1YkeT/YShI14tm2i9Vw5oWPvNMOhKir8cUxHliTDJBnnJlez2ABEFdrl9FsXPmjXX9dXKznAT84rqR5HSZ7muPN3kmCJRQerHodxcOjyIQ14aFfk4p91YLGbtroN5SamueMocjwoFGvSHCTLhHkkGNmj+/EX7KpgVc9RMKF0F5A== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=intel.com; Received: from PH7PR11MB5765.namprd11.prod.outlook.com (2603:10b6:510:139::7) by IA1PR11MB6145.namprd11.prod.outlook.com (2603:10b6:208:3ef::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8069.24; Fri, 18 Oct 2024 13:42:18 +0000 Received: from PH7PR11MB5765.namprd11.prod.outlook.com ([fe80::fcf5:d65c:4fdd:4a2a]) by PH7PR11MB5765.namprd11.prod.outlook.com ([fe80::fcf5:d65c:4fdd:4a2a%3]) with mapi id 15.20.8069.016; Fri, 18 Oct 2024 13:42:18 +0000 Content-Type: multipart/alternative; boundary="------------Ch5gBxgySFlZ6T5Y00aNfL5J" Message-ID: <6c786266-20d8-45e8-9a95-247b0cadd6f0@intel.com> Date: Fri, 18 Oct 2024 14:42:12 +0100 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v3 2/4] hash: add dynamic polynomial calculation To: Stephen Hemminger CC: , Yipeng Wang , Sameh Gobriel , Bruce Richardson References: <20241010123331.749004-1-vladimir.medvedkin@intel.com> <20241011181703.236985-1-vladimir.medvedkin@intel.com> <20241011181703.236985-3-vladimir.medvedkin@intel.com> <20241015152945.530926a1@hermes.local> <9bd9e943-d277-44cb-86c4-36db3f1acf88@intel.com> <20241016202344.000c00f1@hermes.local> Content-Language: en-US From: "Medvedkin, Vladimir" In-Reply-To: <20241016202344.000c00f1@hermes.local> X-ClientProxiedBy: WA2P291CA0026.POLP291.PROD.OUTLOOK.COM (2603:10a6:1d0:1f::22) To PH7PR11MB5765.namprd11.prod.outlook.com (2603:10b6:510:139::7) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: PH7PR11MB5765:EE_|IA1PR11MB6145:EE_ X-MS-Office365-Filtering-Correlation-Id: 929cb91a-d44d-43b3-a2f3-08dcef7aaebf X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|366016|376014|1800799024|8096899003; X-Microsoft-Antispam-Message-Info: =?utf-8?B?VlZpZ1VDdVhld3grbGJPaFRsazhLTEoraE0xK2ZBdWJsQkI5N2QzVXRTcnZt?= =?utf-8?B?ME5FK2RlUW1kSC9UeXdBSVpDdWhvQVBKTlB4ZmRDZmtzbGhWdmJVc2xZaDRZ?= =?utf-8?B?cVVhdHV6UTdrVk1IdE1SUEkwNkFzMGZkdmJQMktYeEdURDkzaFNRUnpyNHdw?= =?utf-8?B?bjY3UXhUSjJoaFcxNjdSZTJkdDZtcU1MeHpldVgvUzNYbmxJR0VpNjR0VHg2?= =?utf-8?B?aGJ3YURUclZOU3F4K1c0d3Uyd1hIVzVBTy9Nd0ZwKzJPVFVySU5NTEpmODBR?= =?utf-8?B?VlIrbHZ6NmxwU09UN2hlZDYyL0Q2UEk3QkRFTVNqTUpyVjJCNkNsdGZxbjA3?= =?utf-8?B?RFhsWGRWaWM4VjF4SkQyeXNUdmxkU1o3NzFEYTZaM1hkV2ZrREdWUWJVajl2?= =?utf-8?B?VjhOY01Fd3Q2ei9MS2duOVNqbDJidlZuTFF2MTNJRmdkNVhKK2E1U1plZGVK?= =?utf-8?B?L1Z1T2pOSWlwYnpPUTBTMjh4TnZwenliL2JNWHNlaDI1MXlNY21LbjB1dGFV?= =?utf-8?B?cGNFR1d1OVRubzZ3QllrcXBGaHZ6UmI5K015L09YcGIrWTlpT05jOVNYeUlW?= =?utf-8?B?aWtIeVl4cVIzbzJhNGVLbEtxYnEybHJoWWVWK3UyT3NNVmhrT3VEQnVTZUdH?= =?utf-8?B?T0tHREpYKy9wdjVQUm4vNXUwb3A2Qys2VDJPeG1idkNreGcyYjNGU1FsWVRk?= =?utf-8?B?eG1yTzRRS0NCVnEyb2VxWmExVk1OQkJjZEdncDI2eWF0TnphQnRoSVVEOERV?= =?utf-8?B?VVN1cjZoWnkxMHo0OWViTWlRWm5wWmI1YkNMbStjUVd6bUcxamVsNjJwbUVK?= =?utf-8?B?cEs2eXJkeklZRmNobHVQd3dmUzNleDl5aTRkaXpsT2Zrci82a1E2c2habE83?= =?utf-8?B?RVZqNFhpa1FQVk1rdmZZbDBBa2gzaWxwNUNYQmZkeTBLTndYY0duSVh3UGkw?= =?utf-8?B?cm5rRDRKUXdMd0lHaFhBWmtNR3FzRUh3UjVJMVFTNy8wSEdsYXVjbUp1TUJ1?= =?utf-8?B?aXBrWW5TM2tyb0JQaUpoTC9ZNHpGL2J3S0dkcFdyeHZrSmpUam91WWNyc0FQ?= =?utf-8?B?Z284WEZpRGZzRStkeEIwL2RzTjRWSGlKVHlVZEtVQmY5SVVZczVhYWlMVjdq?= =?utf-8?B?b0JXd0htQ29ON2xraDdlSG91dTdlMmc0NlRxdVNBZmprV2FCZ1UyZlAzZTBa?= =?utf-8?B?Z3paODJyd1l5a2t2NlY4V29XM3pmQkJ5ZGx3QndKOWFMeXZnT0pYSi9GT3B4?= =?utf-8?B?aUFsSXZldk14UGhucE00bmg5NjFaSldMdUs1RG05RmZzZU5WdzkrZmdqRFFS?= =?utf-8?B?b1EwdlB2NW5qR08xZTUxZkZRZ0taaVJWUVlCUWlrTGJHeVdPUG52bUNLclZX?= =?utf-8?B?K21mdVREYkxvQURPYUwxOFVMQWM2UFZnV21EQkxEM3djcUk1dWZGSWs3WGp5?= =?utf-8?B?TmQ0SDBEYWN1ampwSzIzVDdWeXFvVUsrWEFkTXRoOFFzQmtCdGlLd1cybUwz?= =?utf-8?B?enVVaEtmREQ1M29PcVFueTZQa0l6N3p0K1p0NlNHM1dMMkl4clhoN1NNZ0cr?= =?utf-8?B?b2VkUEZPUlJsd2FTeVRYWTk0REpGSjhmV244bFdHczVhTVZwU1ZGK3ROSHg1?= =?utf-8?B?cUlDVDNMNDlORndiMmZ4cXE5UmcyeGd2UnczS3JmQ0QwWTZFWHhBdGNZTWNs?= =?utf-8?Q?swfRyAwoLGGco0BpvKrt?= X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:PH7PR11MB5765.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230040)(366016)(376014)(1800799024)(8096899003); DIR:OUT; SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?bk9GblpqTTJlbmNpYWhQZEduN0dIb2dxZ3J6NHdnZnBXT2RydUdTdjhCSXZM?= =?utf-8?B?QU9GMER1dFE5SXRIY01yM0UxRlJxamdxNkUzWDQ1VWpxRzI3VVFDM0hFdmFG?= =?utf-8?B?OWVrUjlWb2E1eWJMdVlKZzg4TlZ5RVhSS2NyYjlaaUQzWEx4Mk50MlhIeFNW?= =?utf-8?B?elpiRVlBTC92TGJJekU5dmRyYy9JaEVkakJyYVFRWUV6S1dOczUvWThpelNt?= =?utf-8?B?UEZkOEpzS1VRTWs5OEJuNTZwNlU1Z2M2QVJUMndRUzc1M2xWeFEvcEdxL3Yx?= =?utf-8?B?bngrTGVNRzFmcWpZS1dFeEtVeU1OT2psbG9xQ1AzejhaejM5alpQQ1pvSlVn?= =?utf-8?B?bUlxOW1VcTZYR1pMTzJ0SkJQMlRrT2ZqQzlFTmNxSGJ4R0w3QTZiZWtZSngv?= =?utf-8?B?Qm8vNDM5MXpPUERzRFo4N3Bpa1VwYlVjc2hhQXRlVUIzMXBKRHZUVDBpUXlN?= =?utf-8?B?c2F0SzdRRWZRVjBrd0FZNmVudWd3dUs2cS83UGQyT1NzSkZmbitOdXVjd3FC?= =?utf-8?B?amI3YVFjb3h6MDBYaDVSZTdBN2xJMUxkVU1PNit6bzNRUnBmbGFWL3J2Y3VP?= =?utf-8?B?N3hJWitKVlp6elQwVitlZkVTeHY5VWdnSi9nbDFPU1BpYVRZVHMvd0FmZUxj?= =?utf-8?B?ZWNWZlAxOS81MnRZYktPellnSG5xZTFIT0M3TStTeFBQUjR0S2lCS2tEOUNh?= =?utf-8?B?T05PUzBKaGxRQUNjS3ptYzRDdWVsQlRYUWk3Mkw3ck5MYkJKTEwxNm9kTlRs?= =?utf-8?B?aE9SQ3FWM2NrNSt5UGowRklIWXNPWXhaQXQ3UjNnaldIZURIQ2wrYkRlZjVj?= =?utf-8?B?UzJYZ0k5clYvMGJ0SFVmam8xWjgvY1lHdXNGdXFNTnFEdk1DeWYwWGVKa05R?= =?utf-8?B?a09XbGk0Qmt2WTFqN1kyZFhjTzUvcWlVMWdPNzVDRExKVWZlcmFuRVl6TXA0?= =?utf-8?B?WGVINWJYZnlmeWJvUE1vb2JQL2lvbFhVcjk0bTlsTmdUdnkwOU9UTTQ4M3lt?= =?utf-8?B?TXNpU1lUWFJHSDFuazU3dm9MNHBnNmRxYWFiUjhlbHFobFJkdkN3Q0owU1dp?= =?utf-8?B?R3VsMlFvWVdFeElyUENoVmJ1eWJDMm9QbWVXTDgyZXVIbUpFSjVybWdsMFhi?= =?utf-8?B?RWF0QW9pSGNWMFA2WVExUU9JNDZjWWxjQXNxZTBNdGkwb25RYVlLUFBCTzdu?= =?utf-8?B?K1VEMmJQaGovQXROVlRhVURzOHpjbWIzcVE5NWJPVm8wR0hZd3FDVUhJQkgy?= =?utf-8?B?MVl1TVRJU1lvTHYrR3NQZE42M2piR0tOT2pudzJGeU52Y0lEdkVid05iYUxZ?= =?utf-8?B?dE9YdE5HNFlNZ29JWHJVT3NBbW8zVUxnMlA2MjNNUjNjMU5vMFhpUFhKbUkv?= =?utf-8?B?dWEwaXY2cVdDQlNhelZ4SEI5eEJoTFBzSVFtdTNLTW1yVy8rWEtpQmZoMFJK?= =?utf-8?B?ck5ZbGFPeWtWOVU0SDBlb29BOFc3UUJRSkJoUnExcUNPL0M0U2Z5UG5YVmVs?= =?utf-8?B?QUorUEdGdkJ0Wmp6NnJEdGcyUWFOck5aSUVJL01pT2lqdG9Ka2xObVVIVkF1?= =?utf-8?B?azlzV3E2RUJ5Y1BMcTh1TXAwQXFUSTRCdDN5Qkg4Q1JHVEY3WlRDQnE5Q1pW?= =?utf-8?B?dk9uckdFWkpLZmZ5UVlLalVpRTlOVFZ4enpPU1ovYWR0cVllR0hGVVo0YnY4?= =?utf-8?B?c3dIMEtneTk3bVRYR3F0S3UrVENIQStmSUlEZXBjTzdkdko4ZWFyYXVEdlUz?= =?utf-8?B?RUhFeVBSSWgxM3BxQXI3clR5Y0hFYjgwcFVQazJ0aDFyR2kvVUs3YVo1dCtk?= =?utf-8?B?cEl3RjVkbUdlZjFvbEc3TFNUNWNQb0VJdHFWRDVzQUdpeUFHaTdGQW1EVUZM?= =?utf-8?B?MXRTVEZibVN2bW9NelczMUNiVmpUK2dab3g2S2V0NGY2VkZBemdhOTR4akdl?= =?utf-8?B?cVBIRW0yQko1Y2Q1VkQxd1VOVzlpUzM1ZzdBYTFKWURCTVVrQnlsRTU5b0dz?= =?utf-8?B?ckhjRkxWQmxPZ0JKenlQQ3plSkJaU1VTNWNFZE94c2xWQ09lcG8wWEQxQVNG?= =?utf-8?B?VllMdU1RZEEvQ1JyTGlLcEdGWTd1U0pFYXg3L0hNajlqR3FCN0g5QndSaWl4?= =?utf-8?B?Z0xHSDJDVjdNYkUzUjRJTVpoRDBWU3RoWitHNUluVUJGcUszSmNNd1laREdR?= =?utf-8?B?c1E9PQ==?= X-MS-Exchange-CrossTenant-Network-Message-Id: 929cb91a-d44d-43b3-a2f3-08dcef7aaebf X-MS-Exchange-CrossTenant-AuthSource: PH7PR11MB5765.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 Oct 2024 13:42:17.9657 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: 7tJ2DzDKfy/PB0xo0h7GgIZRr/O1KDORM2XezZbVxxFac36h1JHbMM3ec6GGhzBgt8gfP8ZT5Jpvdd9HqSiXUPyXMAbV8JXZ+boH+a78ogs= X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR11MB6145 X-OriginatorOrg: intel.com X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org --------------Ch5gBxgySFlZ6T5Y00aNfL5J Content-Type: text/plain; charset="UTF-8"; format=flowed Content-Transfer-Encoding: 7bit Hi Stephen, On 17/10/2024 04:23, Stephen Hemminger wrote: > On Wed, 16 Oct 2024 17:28:17 +0100 > "Medvedkin, Vladimir" wrote: > >> Hi Stephen, >> >> On 15/10/2024 23:29, Stephen Hemminger wrote: >>> On Fri, 11 Oct 2024 18:17:00 +0000 >>> Vladimir Medvedkin wrote: >>> >>>> + >>>> +uint32_t >>>> +rte_thash_get_rand_poly(uint32_t poly_degree) >>>> +{ >>>> + uint32_t ret_poly; >>>> + >>>> + if (poly_degree > 32) > Error log here? > >>>> + return 0; >>>> + >>>> + do >>>> + ret_poly = __thash_get_rand_poly(poly_degree); >>>> + while (thash_test_poly_order(ret_poly, poly_degree)); >>> Unbounded loop adds some risk, should there be an upper limit on retries. >> Thisis the probabilisticpartof the algorithm. >> >> __thash_get_rand_poly() returns a random polynomial that either >> satisfies the order criteria (element of the field must generate >> multiplicative subgroup of order not less than some number), or not. The >> probability that it does not meet this criteria is strictly less than 1. >> Thus, with each attempt, the probability of not finding suitable >> polynomial exponentially tends to zero. > Never trust probabilities to converge. Just add an upper bound of something big > like 32 tries and log error and give up. I disagree. I don't want this to give up. Take a look at this algorithm from the perspective of an equivalent bounded random function: https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171 or https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60 The job must be done. Imagine if these random functions may return something like "EAGAIN". The caller needs random value at this pointto continue, so there are only 2 options left - either panic or call the function again. We definitely don't want to panic here. But calling this algorithm again will have the same effect as not having runtime bound inside the algorithm at all. In other words, here I prefer to have "Las Vegas" rather than "Monte Carlo" algorithm. And it make sense since in these particular cases (i.e. my algorithm and bounded random implementations) we have: 1. A simple deterministic algorithm for checking the complianceof somerandomvariablewith a condition 2. Every random variable is independent from each other. So probability of getting unsatisfying random variable after n steps drops exponentially (negative outcome probabilities multiplies). That's why those algorithms runtime expected value is bounded. > >>> >>>> + >>>> + return ret_poly; >>>> +} >>>> diff --git a/lib/hash/version.map b/lib/hash/version.map >>>> index 4f13f1d5aa..7ce6ab1121 100644 >>>> --- a/lib/hash/version.map >>>> +++ b/lib/hash/version.map >>>> @@ -61,4 +61,5 @@ INTERNAL { >>>> >>>> rte_thash_gfni_stub; >>>> rte_thash_gfni_bulk_stub; >>>> + rte_thash_get_rand_poly; >>> Why does this function need to be moved to its own file? >>> Only used in one place in rte_thash.c. >> It was done just for convenience. If you insist, I'll move it to rte_thash.c > > It is actually good to put in seperate file, but you can keep the old name. > Best to reserve names with rte_ prefix for user visible prefixes. > > -- Regards, Vladimir --------------Ch5gBxgySFlZ6T5Y00aNfL5J Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: 8bit

Hi Stephen,

On 17/10/2024 04:23, Stephen Hemminger wrote:
On Wed, 16 Oct 2024 17:28:17 +0100
"Medvedkin, Vladimir" <vladimir.medvedkin@intel.com> wrote:


Hi Stephen,

On 15/10/2024 23:29, Stephen Hemminger wrote:

On Fri, 11 Oct 2024 18:17:00 +0000
Vladimir Medvedkin<vladimir.medvedkin@intel.com>  wrote:
 

+
+uint32_t
+rte_thash_get_rand_poly(uint32_t poly_degree)
+{
+	uint32_t ret_poly;
+
+	if (poly_degree > 32)

Error log here?


+		return 0;
+
+	do
+		ret_poly = __thash_get_rand_poly(poly_degree);
+	while (thash_test_poly_order(ret_poly, poly_degree));  

Unbounded loop adds some risk, should there be an upper limit on retries.  

Thisis the probabilisticpartof the algorithm.

__thash_get_rand_poly() returns a random polynomial that either 
satisfies the order criteria (element <x> of the field must generate 
multiplicative subgroup of order not less than some number), or not. The 
probability that it does not meet this criteria is strictly less than 1. 
Thus, with each attempt, the probability of not finding suitable 
polynomial exponentially tends to zero.

Never trust probabilities to converge. Just add an upper bound of something big
like 32 tries and log error and give up.

I disagree. I don't want this to give up. Take a look at this algorithm from the perspective of an equivalent bounded random function:

https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171

or

https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60

The job must be done. Imagine if these random functions may return something like "EAGAIN". The caller needs random value at this point to continue, so there are only 2 options left - either panic or call the function again.

We definitely don't want to panic here. But calling this algorithm again will have the same effect as not having runtime bound inside the algorithm at all. In other words, here I prefer to have "Las Vegas" rather than "Monte Carlo" algorithm. And it make sense since in these particular cases (i.e. my algorithm and bounded random implementations) we have:

1. A simple deterministic algorithm for checking the compliance of some random variable with a condition

2. Every random variable is independent from each other. So probability of getting unsatisfying random variable after n steps drops exponentially (negative outcome probabilities multiplies). That's why those algorithms runtime expected value is bounded.





        

          
 


          

            
+
+	return ret_poly;
+}
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 4f13f1d5aa..7ce6ab1121 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -61,4 +61,5 @@ INTERNAL {
  
  	rte_thash_gfni_stub;
  	rte_thash_gfni_bulk_stub;
+	rte_thash_get_rand_poly;  


          

          
Why does this function need to be moved to its own file?
Only used in one place in rte_thash.c.  


        

        
It was done just for convenience. If you insist, I'll move it to rte_thash.c


      

      

It is actually good to put in seperate file, but you can keep the old name.
Best to reserve names with rte_ prefix for user visible prefixes.




    

    
-- 
Regards,
Vladimir

  


--------------Ch5gBxgySFlZ6T5Y00aNfL5J--