From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mout01.posteo.de (mout01.posteo.de [185.67.36.65]) by mx.groups.io with SMTP id smtpd.web09.17526.1632655251215776310 for ; Sun, 26 Sep 2021 04:20:52 -0700 Authentication-Results: mx.groups.io; dkim=fail reason="body hash did not verify" header.i=@posteo.de header.s=2017 header.b=PyM77SX5; spf=pass (domain: posteo.de, ip: 185.67.36.65, mailfrom: mhaeuser@posteo.de) Received: from submission (posteo.de [89.146.220.130]) by mout01.posteo.de (Postfix) with ESMTPS id 77E49240028 for ; Sun, 26 Sep 2021 13:20:49 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1632655249; bh=/hXe4xoVAV67vFQ+Pu/b4+zqsUNriGd1XkJyMbzEgPs=; h=Subject:To:Cc:From:Date:From; b=PyM77SX5QiTimJ7BEcN1dtClGz/5/SqqkBPL3qqw73iyVd9Czloi/8hhBBg/WBbjo c/gtMpvMgAH2ziy4zh9Lt8o5dJSbEsVVH642G5Xv+xuemysTGd5dnY4zneussJixrr 0J5EaFlrVR1moHFlFgkRFFVgt6IUkidfFQpF1OA9xBSZbpcmKdQFx060wnX6CbyGyq WVTk75FuIwQbROWkQgnklajpHwopuEgBml6jZliH5gpQeG4thLyDR/7cZ1oT2a5YLv IVOPwAFi1+jx1bgYnYy07zKHIskPlbgAWLHsNOAItmbzBRCiF/F9XFTMgemdQw1ksr QdXUfZwNu3NRw== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4HHNcG1C0jz9rxR; Sun, 26 Sep 2021 13:20:45 +0200 (CEST) Subject: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg To: devel@edk2.groups.io, ray.ni@intel.com, gaoliming , "Chan, Amy" , 'Andrew Fish' Cc: "Kinney, Michael D" , "'Gao, Liming'" , "Liu, Zhiguang" , "Wang, Jian J" , "Gao, Zhichao" References: <001a01d7aa99$d744af80$85ce0e80$@byosoft.com.cn> <003401d7aaa1$c7166830$55433890$@byosoft.com.cn> <16A70FAC1585C7C1.27516@groups.io> <00cf01d7b27a$59145d20$0b3d1760$@byosoft.com.cn> From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= Message-ID: Date: Sun, 26 Sep 2021 11:20:45 +0000 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-GB Content-Transfer-Encoding: quoted-printable Hey Ray, In my opinion that spec is too complicated. For some cases it is=20 obvious, but I think the last anyone wants to see is a (STATIC_)ASSERT=20 before most QuickSort calls to ensure the element size *really* is <=3D=20 256 Bytes. In my opinion, there are two roads: 1) Make the parameter required (I think this is what Liming suggested).=20 The caller would always need to provide said buffer, and it can do as it=20 sees fit - on the stack, in a pool, in a page, who knows. 2) Remove the parameter entirely. The library would depend on=20 MemoryAllocationLib again, but also would have an optimisation by=20 choosing stack vs pool based on ElementSize. Usually I would prefer 2), as it is less prone to caller errors, but=20 considering the low-level nature of edk2, I can totally see the point to=20 allow the caller to control whether there are dynamic memory allocations=20 made or not as possible with 1). 2) could technically also be a wrapper=20 for 1) if you want granular control and convenience/safety (why not=20 actually?). Both approaches have the advantage that it is crystal-clear what the=20 caller's job is - to always or to never allocate the buffer. Best regards, Marvin On 26/09/2021 04:24, Ni, Ray wrote: > > Liming, > > The purpose of the optional BufferOneElement is to ease consumer=E2=80=99= s=20 > life assuming most of the time the element size should be smaller than=20 > 256. > > Are you saying that it=E2=80=99s a bit hard to calculate the actual value= of=20 > sizeof (Element) when writing code? > > I recommend consumer always allocates memory if it=E2=80=99s hard to judg= e=20 > sizeof (Element) < 256. > > Searching edk2 code, I can find below code using PerformQuickSort(): > > 1. ShellPkg/UefiShellCommandLib: It=E2=80=99s sorting array of > (EFI_DEVICE_PATH_PROTOCOL *). > 2. UefiCpuPkg/CpuCacheInfoLib: It=E2=80=99s sorting array of =C2=A0CPU_C= ACHE_INFO. > 3. MinPlatformPkg/AcpiTables: It=E2=80=99s sorting array of EFI_CPU_ID_O= RDER_MAP. > 4. MdeModulePkg/UefiBootManagerLib: It=E2=80=99s sorting array of > EFI_BOOT_MANAGER_LOAD_OPTION. > 5. MdeModulePkg/CapsuleApp: It=E2=80=99s sorting array of (EFI_FILE_INFO= *) > 6. CryptoPkg/CrtWrapper: It=E2=80=99s sorting array of (unknown type). > 7. RedfishPkg/RedfishCrtLib: It=E2=80=99s sorting array of (unknown type= ). > > For 1~5, it=E2=80=99s easy to know that the size of the element is smalle= r=20 > than 256. The AllocatePool() can be skipped. > > Thanks, > > Ray > > *From:*gaoliming > *Sent:* Sunday, September 26, 2021 10:01 AM > *To:* Ni, Ray ; devel@edk2.groups.io; Chan, Amy=20 > ; 'Andrew Fish' > *Cc:* Kinney, Michael D ; 'Gao, Liming'=20 > ; Liu, Zhiguang ; Wang,=20 > Jian J ; Gao, Zhichao > *Subject:* =E5=9B=9E=E5=A4=8D: [edk2-devel] RFC: Add BaseLib/QuickSort in= MdePkg > > Ray: > > I may suggest to always require BufferOneElement. The consumer code=20 > may not know ElementSize. To avoid the error, the consumer must=20 > allocate buffer for BufferOneElement. If so, BufferOneElement is the=20 > required parameter. > > Thanks > > Liming > > *=E5=8F=91=E4=BB=B6=E4=BA=BA**:*Ni, Ray > > *=E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4:* 2021=E5=B9=B49=E6=9C=8824=E6=97= =A5 11:53 > *=E6=94=B6=E4=BB=B6=E4=BA=BA:* devel@edk2.groups.io ; Ni, Ray=20 > >; Chan, Amy=20 > >; gaoliming=20 > >; 'Andrew=20 > Fish' > > *=E6=8A=84=E9=80=81:* Kinney, Michael D >; 'Gao, Liming'=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > > > *=E4=B8=BB=E9=A2=98:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdeP= kg > > More details on new QuickSort() API: > > The new API needs to carry additional parameter =E2=80=9CBufferOneElement= =E2=80=9D. > > This parameter gives QuickSort() the temporary buffer for swapping in=20 > sorting. > > It=E2=80=99s to avoid BaseLib depends on MemoryAllocationLib. > > =E2=80=A6 > > @param [in] BufferOneElement =C2=A0When ElementSize > 256, caller needs t= o=20 > provide a buffer whose size > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 =C2=A0equals to ElementSize. It=E2=80=99s used by=20 > QuickSort() for swapping in sorting. > > When ElementSize <=3D 256, QuickSort() uses a local stack 256-byte buffer= . > > @retval EFI_INVALID_PARAMETER When (ElementSize > 256) and=20 > (BufferOneElement =3D=3D NULL). > > =E2=80=A6 > > VOID > > EFIAPI > > QuickSort=C2=A0( > > =C2=A0=C2=A0IN=C2=A0OUT VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0*BufferToSort, > > =C2=A0=C2=A0IN=C2=A0CONST=C2=A0UINTN ElementCount, > > =C2=A0=C2=A0IN=C2=A0CONST=C2=A0UINTN ElementSize, > > =C2=A0=C2=A0IN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0SORT_COMPARE Comp= areFunction, > > IN VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0 *BufferOneElement OPTIONAL > > ); > > Any comments? > > *From:*devel@edk2.groups.io =20 > > *On Behalf Of=20 > *Ni, Ray > *Sent:* Wednesday, September 22, 2021 2:04 PM > *To:* Chan, Amy >;=20 > gaoliming >; 'Andrew Fish' >; 'edk2-devel-groups-io'=20 > > > *Cc:* Kinney, Michael D >; 'Gao, Liming'=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > > > *Subject:* Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg > > I don=E2=80=99t see objection so far. > > So, the final solution is: > > 1. Add QuickSort() API to BaseLib in MdePkg. > 2. Update existing=C2=A0MdeModulePkg/SortLib to use QuickSort() in the > implementation (proposed by Andrew Fish and Liming Gao) > 3. Update UefiCpuPkg to use QuickSortLib to remove improper > dependency on MdeModulePkg > > Thanks, > > Ray > > *From:*Ni, Ray > *Sent:* Thursday, September 16, 2021 10:48 AM > *To:* Chan, Amy >;=20 > gaoliming >; 'Andrew Fish' >; 'edk2-devel-groups-io'=20 > > > *Cc:* Kinney, Michael D >; 'Gao, Liming'=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > > > *Subject:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg > > Amy, > > No. We only Add QuickSort() function API into BaseLib.h. > > *From:*Chan, Amy > > *Sent:* Thursday, September 16, 2021 10:46 AM > *To:* gaoliming >; 'Andrew Fish' >; 'edk2-devel-groups-io'=20 > > > *Cc:* Ni, Ray >; Kinney,=20 > Michael D >; 'Gao, Liming'=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > > > *Subject:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg > > Just to double confirm, will we have the null instance of QuickSort in=20 > MdePkg? > > Regards, > > Amy > > *From:*gaoliming > > *Sent:* Thursday, September 16, 2021 10:23 AM > *To:* 'Andrew Fish' >;=20 > 'edk2-devel-groups-io' > > *Cc:* Ni, Ray >; Kinney,=20 > Michael D >; 'Gao, Liming'=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > >; Chan, Amy=20 > > > *Subject:* =E5=9B=9E=E5=A4=8D: [edk2-devel] RFC: Add BaseLib/QuickSort in= MdePkg > > Andrew: > > Thanks for your suggestion. I think your idea is better. We add new=20 > QuickSort() API to BaseLib, and update SortLib library instance to=20 > consume BaseLib QuickSort() API. This way has no change in current=20 > SortLib library class. It is the compatible solution. > > Thanks > > Liming > > *=E5=8F=91=E4=BB=B6=E4=BA=BA**:*Andrew Fish > > *=E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4:* 2021=E5=B9=B49=E6=9C=8816=E6=97= =A5 10:13 > *=E6=94=B6=E4=BB=B6=E4=BA=BA:* edk2-devel-groups-io >; Liming Gao > > *=E6=8A=84=E9=80=81:* Ni, Ray = >; Mike=20 > Kinney >; Gao, Liming=20 > >; Liu, Zhiguang=20 > >; Wang, Jian J=20 > >; Gao, Zhichao=20 > >; Chan, Amy=20 > > > *=E4=B8=BB=E9=A2=98:* Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdeP= kg > > On Sep 15, 2021, at 6:26 PM, gaoliming > wrote: > > Ray: > > SortLib has been added since 2015. I would suggest to still keep > this library class. To resolve the package dependency, my proposal > is to move the library class header file SortLib.h from > MdeModulePkg to MdePkg, and still keep the library instance in > MdeModulePkg. This proposal has no impact on the existing platform. > > If we add QuickSort() API to the BaseLib can we not just port the=20 > existing=C2=A0MdeModulePkg/SortLib to use QuickSort() in the=20 > implementation? Or is there some other way to add the new thing in a=20 > backward compatible way. > > Thanks, > > Andrew Fish > > Thanks > > Liming > > *=E5=8F=91=E4=BB=B6=E4=BA=BA**:*devel@edk2.groups.io > >*=E4=BB=A3=E8=A1=A8***Ni, Ray > *=E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4:*2021=E5=B9=B49=E6=9C=8814=E6= =97=A514:15 > *=E6=94=B6=E4=BB=B6=E4=BA=BA:*Kinney, Michael D >; Gao, Liming > >; Liu, > Zhiguang >; > Wang, Jian J >; Gao, Zhichao > > > *=E6=8A=84=E9=80=81:*devel@edk2.groups.io ; Chan, Amy > > > *=E4=B8=BB=E9=A2=98:*[edk2-devel] RFC: Add BaseLib/QuickSort in MdePk= g > > Hi package maintainers of MdePkg, MdeModulePkg and ShellPkg, > community, > > A commit (UefiCpuPkg/CpuCacheInfoLib: Sort CpuCacheInfo array > ) > to UefiCpuPkg let > UefiCpuPkg depend on MdeModulePkg because the SortLib class and > instances are all in MdeModulePkg. > > UefiCpuPkg depending on MdeModulePkg breaks the rule that > =E2=80=9CUefiCpuPkg should ONLY depend on MdePkg=E2=80=9D. > > 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=E2=80=99s MdeModulePkg/SortLi= b. > > If you don=E2=80=99t have concerns, I plan to: > > 1. =E2=80=9CAdd QuickSort() to BaseLib=E2=80=9D and update all exist= ing consumers > to use this API instead. > > VOID > > EFIAPI > > QuickSort=C2=A0( > > =C2=A0=C2=A0IN=C2=A0OUT=C2=A0VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0*BufferToSort, > > =C2=A0=C2=A0IN=C2=A0CONST=C2=A0UINTN Count, > > =C2=A0=C2=A0IN=C2=A0CONST=C2=A0UINTN ElementSize, > > =C2=A0=C2=A0IN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0SORT_COMPARE= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0CompareFunction > > =C2=A0=C2=A0); > > 2. =E2=80=9CAdd new ShellPkg/SortCompareLib=E2=80=9D > > Background: ShellPkg requires to sort devicepath/string so 3 APIs > in UefiSortLib (DevicePathCompare, StringNoCaseCompare, > StringCompare) are provided for Shell usage. we can move the 3 > APIs to the SortCompareLib and update Shell code to use > BaseLib/QuickSort directly, with the sort compare function from > SortCompareLib. > > Any concerns? > > Thanks, > > Ray > >=20