From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by mx.groups.io with SMTP id smtpd.web09.6208.1631600133954730039 for ; Mon, 13 Sep 2021 23:15:34 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=seAmjb0s; spf=pass (domain: intel.com, ip: 192.55.52.88, mailfrom: ray.ni@intel.com) X-IronPort-AV: E=McAfee;i="6200,9189,10106"; a="244222562" X-IronPort-AV: E=Sophos;i="5.85,292,1624345200"; d="scan'208,217";a="244222562" Received: from fmsmga007.fm.intel.com ([10.253.24.52]) by fmsmga101.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 13 Sep 2021 23:15:30 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.85,292,1624345200"; d="scan'208,217";a="469976551" Received: from fmsmsx601.amr.corp.intel.com ([10.18.126.81]) by fmsmga007.fm.intel.com with ESMTP; 13 Sep 2021 23:15:30 -0700 Received: from fmsmsx601.amr.corp.intel.com (10.18.126.81) by fmsmsx601.amr.corp.intel.com (10.18.126.81) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12; Mon, 13 Sep 2021 23:15:30 -0700 Received: from fmsedg601.ED.cps.intel.com (10.1.192.135) by fmsmsx601.amr.corp.intel.com (10.18.126.81) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12 via Frontend Transport; Mon, 13 Sep 2021 23:15:30 -0700 Received: from NAM10-BN7-obe.outbound.protection.outlook.com (104.47.70.107) by edgegateway.intel.com (192.55.55.70) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2242.12; Mon, 13 Sep 2021 23:15:29 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=bv4erDENdkRDE8LMyf8hyBVNgPOUSzJ0OZVmcgLlfNuDsQi2qY5HYfHQC6y8NyH/tgUAGH1dAu4eXk1DoyluXT0SymZwjsLE9rlC9X4QlrIxcuX/X2a2oaD5EbV/kab0oaltVna6tpo1RHUG6lZzXoZtCV4auYJM7qYat/uVjTh6NDvT7wLciuTkr0fHJi6cpp9hqVOAJJbYHdzr9+OIkacP/7CXdHQ7MDLM6xYl234LsuMBt40fsDw3XzvhCzXHgl/jU5c3gWd5Kj1DzTcirCHAbKXVPKiZGu9ts7qHcNCrrVbcD6/vOMx+xzAzQ2ojeDvKwgF4+tKQC4bBPr2BgA== 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; bh=G5/NsidE267vAzwJgVfqdwfIovYk7NWaieNqW1pfgWU=; b=XJOVxBATBZ/mwRPs2aJkqYvoCBopH0EVwwXdPCMuJlQmv0CH7/pQAAN/vf2GK4+Q3J2FhVaGzVjZYE44rYxRpPsyQtij+5glpabfM3sAU/LYHQps5yvRaKfYd2+MUL4NHTvq2ot/1AnHq8pOQDLPlh3jzecE6sFyWUvTgBTcGxaCZG/Fdqu7if+7JHWenoIcDyRnqHnEfX92TaW79j3yE5mTuAU4NsPxayNd1LE/5u6CGqWuoHfLCug7Vamcr7QzTgCsF8Gr5EmPQWLcP03Kj/FUUSwd7CvMXvW5SGBJKeQuIjtGrVo5U78Qe33XvF6xt0c16lAtYvr+r5UYM9N8SA== 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 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com; s=selector2-intel-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=G5/NsidE267vAzwJgVfqdwfIovYk7NWaieNqW1pfgWU=; b=seAmjb0sYHYaw2GxsmYYZehsmBjmAX6m/+B83ERp4uCwpSRoyZJD1KL3hLlgTZRKRzOd//W2N4texCryFNXOVA3wpwxv/Nk2u4FIDg7sIeF0PcAcY7/DCjSLyaRevEjVgtDlol9Tv2O6XCUk2aFU0xWNCiPegu3fiHEX68hHDEE= Received: from CO1PR11MB4930.namprd11.prod.outlook.com (2603:10b6:303:9b::11) by MWHPR11MB1277.namprd11.prod.outlook.com (2603:10b6:300:29::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4500.16; Tue, 14 Sep 2021 06:15:26 +0000 Received: from CO1PR11MB4930.namprd11.prod.outlook.com ([fe80::50ce:c9a3:ab37:9fac]) by CO1PR11MB4930.namprd11.prod.outlook.com ([fe80::50ce:c9a3:ab37:9fac%9]) with mapi id 15.20.4500.019; Tue, 14 Sep 2021 06:15:26 +0000 From: "Ni, Ray" To: "Kinney, Michael D" , "Gao, Liming" , "Liu, Zhiguang" , "Wang, Jian J" , "Gao, Zhichao" CC: "devel@edk2.groups.io" , "Chan, Amy" Subject: RFC: Add BaseLib/QuickSort in MdePkg Thread-Topic: RFC: Add BaseLib/QuickSort in MdePkg Thread-Index: AdepLqSqNr3XR8BzRta7Fw6/X0zQqw== Date: Tue, 14 Sep 2021 06:15:26 +0000 Message-ID: Accept-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-version: 11.6.200.16 dlp-reaction: no-action dlp-product: dlpe-windows authentication-results: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=intel.com; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 49996b96-339c-4b3f-34c6-08d977470b64 x-ms-traffictypediagnostic: MWHPR11MB1277: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:3276; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: ob4DPB4luOplMah8c3PM46K3UCBrnyuc5tBKxkHoKVLmzeer8FRJN2EcnuNGKHl/KS6dN/2Zc5yNQGO9lExXmuoHy9vkHRD+rfAodl8cqEG+14NfJF453TOM9LKC+pAOrOyfcv7lc14tkLQj6B1wXfBQZT7mxKHawqmBVPyR7I0wfAetlqsCfkxtoG5+SatCY/Xh/XTkVGQBSNw7sDzo6GRVOZhk981waOP1gM2JSCdkSqYUc9spL63+kHXFv2nWX9JUqVTLt8b5NzWd3fjIhh7hQc3Uij+oe5hEvdSBQYQ5g6pc697ft3Sf8yBm+pS3Cv6vebH8+Omkied5FX+3bgJ8DB7FSVPorxLKCKGe/WkYcU1mOw7P7BFsVODmJpk7ivNxnOSVcZqkn8hRCSjnH8H1h34zs/nte2+IMueCbJyc78bm6+b88npvuCnMRqlwiSqiTpAQwJaG7j7FxScRdjIQRdw2inT/gyiW97QGEpbJ6tkstGNHjxGvSUsP1Lom2ccI/xmNGfwwFGCYgnlwRaD4X2i4XnhhixukA8DZHGQwOTDdVr/O630HTINqwRoCIgE+88fg0qjmDwnZXakfbFrYRugKqnl3JvZaHlrRefpnoa7tYFfX/xjUOyZqiPLrY9cDQtcn2FvjAXcG/hMzghHNFutdQaJeR4LneEWpRIGz7SQlTni/7GIUwA80gyTcmAxUCeRlGHrnB7L/q8polzb0BNsM/Sj/FX0DmHgdmlRizL3jvhQ7y61Tkp1C0QJXw1XFO5JyQhaOptIuYS1fCaPeYl+xZBv3NO2ID7xPISN+nq11MioAuNrAIT+0HAKM x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:CO1PR11MB4930.namprd11.prod.outlook.com;PTR:;CAT:NONE;SFS:(4636009)(366004)(6506007)(6636002)(5660300002)(110136005)(7696005)(55016002)(33656002)(508600001)(2906002)(71200400001)(9686003)(8936002)(107886003)(316002)(186003)(8676002)(921005)(83380400001)(76116006)(52536014)(66556008)(38070700005)(38100700002)(66476007)(66946007)(64756008)(122000001)(86362001)(66446008)(166002)(54906003)(4326008)(26005);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?DV2C/keVJUyQGDQH2E37zIsBAeWuobg+QxS0EoKybeg77gQAtZZlfp2/oE+p?= =?us-ascii?Q?KCIUYncDJMumPOOhjJn3Uh/dU8lMQMXWxS5B61tMUoL5z1FaSOmwkZp5hfI0?= =?us-ascii?Q?7abvbIKOdwaF6DTu+p4nSFm4FTeEemPDh3rc3pxAAtZG5LOqcph0DiXVp81G?= =?us-ascii?Q?XiecXmL0p26So/CCnwTGmGfKQhIVlNmlWB2RuaZpKjkDZy+qa1r1ITB0vsa6?= =?us-ascii?Q?LwhRWAIxRIazA4mGuf/YYRmqcezbEwFLhnRbL8svq+OnyvP7q2gx1LlPkLzx?= =?us-ascii?Q?guWpnuqZC8jmxzHt5cdydz+sqFRXVTSNySHzCr5rbMNcmttsC5u4disUEbyM?= =?us-ascii?Q?8qruAz0aOTZOE39Qk+fPWU1v09DHXrtJ/7NyZGpRfPoBrB322mYHxyK7H0W/?= =?us-ascii?Q?S4WK6Z0LAt0c6Q8lEbIYapEXW0Ji0D1QaRkKV4cBxNBCroCV7aKvhXpyW8T3?= =?us-ascii?Q?Kne7SauPUWuzP6Ev7KcfGrAD/ug5rojkCVKnf4ha3K0YWs1uV/1PRwQqUitO?= =?us-ascii?Q?Rz1hwThjBuf7txuebO3UUsvczoNPKcGkxSVjNeoxzUIpGaP17slGVA8Vz4tU?= =?us-ascii?Q?NFath2po33vTmMIiUR8tDeb1veeMaFY8B8Jz6slkxDaBFjijTYqqXSRWI3IU?= =?us-ascii?Q?CATbXHksMq4eI/35wAVjdfJoGwhFloWesU7vb2Avis3OIqXnEac3k2wlqOXg?= =?us-ascii?Q?Eq1T6WGA8i+izY0pt15sSYH/45ua+gprj4DuuoJcxIeYDiSeGurVyzLb3vdO?= =?us-ascii?Q?ZupNzjwKRmb0QfH+2c6QAeJsMq/Ciy1k5Wi9722+EAixYO036cBXPkHBci/9?= =?us-ascii?Q?e85IEOwkm4glJ6allDhKyMWTlJ/luUy610xydAWpkWHDiBOFcctqTx5ZzzBM?= =?us-ascii?Q?7dASZlxMf1XfsDlSlwYzgj20H4kwfzcWj9rFHQaV6jAiIBjczUzqsqfeEYeR?= =?us-ascii?Q?PWmLAM6kYfiQ0HNW7BrlkwG2jMx5mAe/p9XMeSIZENv/Qj6HoKCIrPRxm7J8?= =?us-ascii?Q?UiiS+eW23fJ71zRXYRRGtVLrH9wvRLvTgsu+0Pf5+2P7aeGdcJDIBXGA/EUy?= =?us-ascii?Q?avpY2ZZ2ebt6uIa9Vr/i2haKyu2xY0Khd40zeiC991NdfCH4PSNOAWZLNJYL?= =?us-ascii?Q?RI22IKAcuzQVGfC1SVuUezhJ9JzIVipocIzAPq4q0bYkX1hKl/RklbG/FH58?= =?us-ascii?Q?g66h4Esks/WkXHGVxhQZ1mhHJA/NV454P1At8XD9+16Mj0owwU4Mo+vICydP?= =?us-ascii?Q?FhqG58TI94JD0kvZLgoehrbk5W7dvh6lRVAJq8U7qg55PRpUaPLRxwPkDy2s?= =?us-ascii?Q?0OCuI9svsdz9T3FlIuI1dG/p?= MIME-Version: 1.0 X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: CO1PR11MB4930.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 49996b96-339c-4b3f-34c6-08d977470b64 X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Sep 2021 06:15:26.6150 (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: 5E3c1G8j2mZqvcu+BdnfdaipxP3ZyKEGHN3ZgiLlcBTf2b7+MlyoEsVwuj/tbotlirgY3AlbN33/UuYtK1vA5A== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR11MB1277 Return-Path: ray.ni@intel.com X-OriginatorOrg: intel.com Content-Language: en-US Content-Type: multipart/alternative; boundary="_000_CO1PR11MB4930ECEBF04D3F22C3A14B9C8CDA9CO1PR11MB4930namp_" --_000_CO1PR11MB4930ECEBF04D3F22C3A14B9C8CDA9CO1PR11MB4930namp_ Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Hi package maintainers of MdePkg, MdeModulePkg and ShellPkg, community, A commit (UefiCpuPkg/CpuCacheInfoLib: Sort CpuCacheInfo array) to U= efiCpuPkg let UefiCpuPkg depend on MdeModulePkg because the SortLib class and instances a= re all in MdeModulePkg. UefiCpuPkg depending on MdeModulePkg breaks the rule that "UefiCpuPkg shoul= d ONLY depend on MdePkg". To address this issue, there are two approaches: 1. Duplicate the sort logic in UefiCpuPkg to not depend on MdeModulePkg/= SortLib 2. Add QuickSort() API to BaseLib in MdePkg. Approach #2 (MdePkg/BaseLib/QuickSort) makes more sense because quick sort = is a standard algorithm. We encourage consumers to update their code to use the quick sort in MdePkg= and gradually deprecate today's MdeModulePkg/SortLib. If you don't have concerns, I plan to: 1. "Add QuickSort() to BaseLib" and update all existing consumers to use= this API instead. VOID EFIAPI QuickSort ( IN OUT VOID *BufferToSort, IN CONST UINTN Count, IN CONST UINTN ElementSize, IN SORT_COMPARE CompareFunction ); 1. "Add new ShellPkg/SortCompareLib" Background: ShellPkg requires to sort devicepath/string so 3 APIs in UefiSo= rtLib (DevicePathCompare, StringNoCaseCompare, StringCompare) are provided = for Shell usage. we can move the 3 APIs to the SortCompareLib and update Sh= ell code to use BaseLib/QuickSort directly, with the sort compare function = from SortCompareLib. Any concerns? Thanks, Ray --_000_CO1PR11MB4930ECEBF04D3F22C3A14B9C8CDA9CO1PR11MB4930namp_ Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

Hi package maintainers of MdePkg, MdeModulePkg and S= hellPkg, community,

 

A commit (UefiCpuPkg/CpuCacheInfo= Lib: Sort CpuCacheInfo array) to UefiCpuPkg let
UefiCpuPkg depend on MdeModulePkg because the SortLib class and instances a= re all in MdeModulePkg.

 

UefiCpuPkg depending on MdeModulePkg breaks the rule= that “UefiCpuPkg should ONLY depend on MdePkg”.

 

To address this issue, there are two approaches:

  1. Duplicate the sort logic in UefiCpuPkg to not depend on MdeModulePkg/= SortLib
  2. Add QuickSort() API to BaseLib in MdePkg.=

 

Approach #2 (MdePkg/BaseLib/QuickSort) makes more se= nse because quick sort is a standard algorithm.

We encourage consumers to update their code to use t= he quick sort in MdePkg and gradually deprecate today’s MdeModulePkg/= SortLib.

 

If you don’t have concerns, I plan to:

  1. “Add QuickSort() to BaseLib” and update all existing cons= umers to use this API instead.

VOID

EFIAPI<= o:p>

QuickSo= rt (

 &= nbsp;IN OUT VOID        &= nbsp;          *BufferToS= ort,

 &= nbsp;IN CONST UINTN       &nbs= p;        Count,

 &= nbsp;IN CONST UINTN       &nbs= p;        ElementSize,

 &= nbsp;IN       SORT_COMPARE  &n= bsp;      CompareFunction

 &= nbsp;);

 

  1. “Add new ShellPkg/SortCompareLib”

Background: ShellPkg requires to sort devicep= ath/string so 3 APIs in UefiSortLib (DevicePathCompare, StringNoCaseCompare= , StringCompare) are provided for Shell usage. we can move the 3 APIs to th= e SortCompareLib and update Shell code to use BaseLib/QuickSort directly, with the sort compare function fro= m SortCompareLib.

 

Any concerns?

 

Thanks,

Ray

--_000_CO1PR11MB4930ECEBF04D3F22C3A14B9C8CDA9CO1PR11MB4930namp_--