Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg

["Jeff Fan" <fanjianfeng@byosoft.com.cn>]

[-- Attachment #1: Type: text/plain, Size: 14700 bytes --]

Making baselib implementation depend on MemoryAllocationLib (indirectly on Pei Service and gBS), it may prevent this base API using at some seneraio. i don't think it's better.

Add this parameter and make this parameter is optional,
1, when NULL, use the local 256 bytes stack
2, if 256 bytes stack is not enough, return RETURE_BUFFER_TOO_SAMLL,
3, caller check the return status, to do nothing or to allocate enough buffer for retry

This is just like SetVariable()'s implementation.



Jeff
fanjianfeng@byosoft.com.cn
 
From: Marvin Häuser
Date: 2021-09-26 19:20
To: devel; ray.ni; gaoliming; Chan, Amy; 'Andrew Fish'
CC: Kinney, Michael D; 'Gao, Liming'; Liu, Zhiguang; Wang, Jian J; Gao, Zhichao
Subject: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Hey Ray,
 
In my opinion that spec is too complicated. For some cases it is 
obvious, but I think the last anyone wants to see is a (STATIC_)ASSERT 
before most QuickSort calls to ensure the element size *really* is <= 
256 Bytes. In my opinion, there are two roads:
 
1) Make the parameter required (I think this is what Liming suggested). 
The caller would always need to provide said buffer, and it can do as it 
sees fit - on the stack, in a pool, in a page, who knows.
 
2) Remove the parameter entirely. The library would depend on 
MemoryAllocationLib again, but also would have an optimisation by 
choosing stack vs pool based on ElementSize.
 
Usually I would prefer 2), as it is less prone to caller errors, but 
considering the low-level nature of edk2, I can totally see the point to 
allow the caller to control whether there are dynamic memory allocations 
made or not as possible with 1). 2) could technically also be a wrapper 
for 1) if you want granular control and convenience/safety (why not 
actually?).
 
Both approaches have the advantage that it is crystal-clear what the 
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’s 
> life assuming most of the time the element size should be smaller than 
> 256.
>
> Are you saying that it’s a bit hard to calculate the actual value of 
> sizeof (Element) when writing code?
>
> I recommend consumer always allocates memory if it’s hard to judge 
> sizeof (Element) < 256.
>
> Searching edk2 code, I can find below code using PerformQuickSort():
>
>  1. ShellPkg/UefiShellCommandLib: It’s sorting array of
>     (EFI_DEVICE_PATH_PROTOCOL *).
>  2. UefiCpuPkg/CpuCacheInfoLib: It’s sorting array of  CPU_CACHE_INFO.
>  3. MinPlatformPkg/AcpiTables: It’s sorting array of EFI_CPU_ID_ORDER_MAP.
>  4. MdeModulePkg/UefiBootManagerLib: It’s sorting array of
>     EFI_BOOT_MANAGER_LOAD_OPTION.
>  5. MdeModulePkg/CapsuleApp: It’s sorting array of (EFI_FILE_INFO *)
>  6. CryptoPkg/CrtWrapper: It’s sorting array of (unknown type).
>  7. RedfishPkg/RedfishCrtLib: It’s sorting array of (unknown type).
>
> For 1~5, it’s easy to know that the size of the element is smaller 
> than 256. The AllocatePool() can be skipped.
>
> Thanks,
>
> Ray
>
> *From:*gaoliming <gaoliming@byosoft.com.cn>
> *Sent:* Sunday, September 26, 2021 10:01 AM
> *To:* Ni, Ray <ray.ni@intel.com>; devel@edk2.groups.io; Chan, Amy 
> <amy.chan@intel.com>; 'Andrew Fish' <afish@apple.com>
> *Cc:* Kinney, Michael D <michael.d.kinney@intel.com>; 'Gao, Liming' 
> <liming.gao@intel.com>; Liu, Zhiguang <zhiguang.liu@intel.com>; Wang, 
> Jian J <jian.j.wang@intel.com>; Gao, Zhichao <zhichao.gao@intel.com>
> *Subject:* 回复: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> Ray:
>
> I may suggest to always require BufferOneElement. The consumer code 
> may not know ElementSize. To avoid the error, the consumer must 
> allocate buffer for BufferOneElement. If so, BufferOneElement is the 
> required parameter.
>
> Thanks
>
> Liming
>
> *发件人**:*Ni, Ray <ray.ni@intel.com <mailto:ray.ni@intel.com>>
> *发送时间:* 2021年9月24日 11:53
> *收件人:* devel@edk2.groups.io <mailto:devel@edk2.groups.io>; Ni, Ray 
> <ray.ni@intel.com <mailto:ray.ni@intel.com>>; Chan, Amy 
> <amy.chan@intel.com <mailto:amy.chan@intel.com>>; gaoliming 
> <gaoliming@byosoft.com.cn <mailto:gaoliming@byosoft.com.cn>>; 'Andrew 
> Fish' <afish@apple.com <mailto:afish@apple.com>>
> *抄送:* Kinney, Michael D <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; 'Gao, Liming' 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>
> *主题:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> More details on new QuickSort() API:
>
> The new API needs to carry additional parameter “BufferOneElement”.
>
> This parameter gives QuickSort() the temporary buffer for swapping in 
> sorting.
>
> It’s to avoid BaseLib depends on MemoryAllocationLib.
>
> …
>
> @param [in] BufferOneElement  When ElementSize > 256, caller needs to 
> provide a buffer whose size
>                               equals to ElementSize. It’s used by 
> QuickSort() for swapping in sorting.
>
> When ElementSize <= 256, QuickSort() uses a local stack 256-byte buffer.
>
> @retval EFI_INVALID_PARAMETER When (ElementSize > 256) and 
> (BufferOneElement == NULL).
>
> …
>
> VOID
>
> EFIAPI
>
> QuickSort (
>
>   IN OUT VOID                         *BufferToSort,
>
>   IN CONST UINTN ElementCount,
>
>   IN CONST UINTN ElementSize,
>
>   IN       SORT_COMPARE CompareFunction,
>
> IN VOID                         *BufferOneElement OPTIONAL
>
> );
>
> Any comments?
>
> *From:*devel@edk2.groups.io <mailto:devel@edk2.groups.io> 
> <devel@edk2.groups.io <mailto:devel@edk2.groups.io>> *On Behalf Of 
> *Ni, Ray
> *Sent:* Wednesday, September 22, 2021 2:04 PM
> *To:* Chan, Amy <amy.chan@intel.com <mailto:amy.chan@intel.com>>; 
> gaoliming <gaoliming@byosoft.com.cn 
> <mailto:gaoliming@byosoft.com.cn>>; 'Andrew Fish' <afish@apple.com 
> <mailto:afish@apple.com>>; 'edk2-devel-groups-io' 
> <devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
> *Cc:* Kinney, Michael D <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; 'Gao, Liming' 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>
> *Subject:* Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> I don’t see objection so far.
>
> So, the final solution is:
>
>  1. Add QuickSort() API to BaseLib in MdePkg.
>  2. Update existing MdeModulePkg/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 <amy.chan@intel.com <mailto:amy.chan@intel.com>>; 
> gaoliming <gaoliming@byosoft.com.cn 
> <mailto:gaoliming@byosoft.com.cn>>; 'Andrew Fish' <afish@apple.com 
> <mailto:afish@apple.com>>; 'edk2-devel-groups-io' 
> <devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
> *Cc:* Kinney, Michael D <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; 'Gao, Liming' 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <Zhiguang.Liu@intel.com <mailto:Zhiguang.Liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>
> *Subject:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> Amy,
>
> No. We only Add QuickSort() function API into BaseLib.h.
>
> *From:*Chan, Amy <amy.chan@intel.com <mailto:amy.chan@intel.com>>
> *Sent:* Thursday, September 16, 2021 10:46 AM
> *To:* gaoliming <gaoliming@byosoft.com.cn 
> <mailto:gaoliming@byosoft.com.cn>>; 'Andrew Fish' <afish@apple.com 
> <mailto:afish@apple.com>>; 'edk2-devel-groups-io' 
> <devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
> *Cc:* Ni, Ray <ray.ni@intel.com <mailto:ray.ni@intel.com>>; Kinney, 
> Michael D <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; 'Gao, Liming' 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>
> *Subject:* RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> Just to double confirm, will we have the null instance of QuickSort in 
> MdePkg?
>
> Regards,
>
> Amy
>
> *From:*gaoliming <gaoliming@byosoft.com.cn 
> <mailto:gaoliming@byosoft.com.cn>>
> *Sent:* Thursday, September 16, 2021 10:23 AM
> *To:* 'Andrew Fish' <afish@apple.com <mailto:afish@apple.com>>; 
> 'edk2-devel-groups-io' <devel@edk2.groups.io 
> <mailto:devel@edk2.groups.io>>
> *Cc:* Ni, Ray <ray.ni@intel.com <mailto:ray.ni@intel.com>>; Kinney, 
> Michael D <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; 'Gao, Liming' 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>; Chan, Amy 
> <amy.chan@intel.com <mailto:amy.chan@intel.com>>
> *Subject:* 回复: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
> Andrew:
>
> Thanks for your suggestion. I think your idea is better. We add new 
> QuickSort() API to BaseLib, and update SortLib library instance to 
> consume BaseLib QuickSort() API. This way has no change in current 
> SortLib library class. It is the compatible solution.
>
> Thanks
>
> Liming
>
> *发件人**:*Andrew Fish <afish@apple.com <mailto:afish@apple.com>>
> *发送时间:* 2021年9月16日 10:13
> *收件人:* edk2-devel-groups-io <devel@edk2.groups.io 
> <mailto:devel@edk2.groups.io>>; Liming Gao <gaoliming@byosoft.com.cn 
> <mailto:gaoliming@byosoft.com.cn>>
> *抄送:* Ni, Ray <ray.ni@intel.com <mailto:ray.ni@intel.com>>; Mike 
> Kinney <michael.d.kinney@intel.com 
> <mailto:michael.d.kinney@intel.com>>; Gao, Liming 
> <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu, Zhiguang 
> <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>; Wang, Jian J 
> <jian.j.wang@intel.com <mailto:jian.j.wang@intel.com>>; Gao, Zhichao 
> <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>; Chan, Amy 
> <amy.chan@intel.com <mailto:amy.chan@intel.com>>
> *主题:* Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
>     On Sep 15, 2021, at 6:26 PM, gaoliming <gaoliming@byosoft.com.cn
>     <mailto:gaoliming@byosoft.com.cn>> 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 
> existing MdeModulePkg/SortLib to use QuickSort() in the 
> implementation? Or is there some other way to add the new thing in a 
> backward compatible way.
>
> Thanks,
>
> Andrew Fish
>
>     Thanks
>
>     Liming
>
>     *发件人**:*devel@edk2.groups.io
>     <mailto:devel@edk2.groups.io><devel@edk2.groups.io
>     <mailto:devel@edk2.groups.io>>*代表***Ni, Ray
>     *发送时间:*2021年9月14日14:15
>     *收件人:*Kinney, Michael D <michael.d.kinney@intel.com
>     <mailto:michael.d.kinney@intel.com>>; Gao, Liming
>     <liming.gao@intel.com <mailto:liming.gao@intel.com>>; Liu,
>     Zhiguang <zhiguang.liu@intel.com <mailto:zhiguang.liu@intel.com>>;
>     Wang, Jian J <jian.j.wang@intel.com
>     <mailto:jian.j.wang@intel.com>>; Gao, Zhichao
>     <zhichao.gao@intel.com <mailto:zhichao.gao@intel.com>>
>     *抄送:*devel@edk2.groups.io <mailto:devel@edk2.groups.io>; Chan, Amy
>     <amy.chan@intel.com <mailto:amy.chan@intel.com>>
>     *主题:*[edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
>
>     Hi package maintainers of MdePkg, MdeModulePkg and ShellPkg,
>     community,
>
>     A commit (UefiCpuPkg/CpuCacheInfoLib: Sort CpuCacheInfo array
>     <https://github.com/tianocore/edk2/commit/4de77ae9890d241271f543e9195ab3516f3abec6>)
>     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
>     “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 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
>
>       );
>
>      2. “Add new ShellPkg/SortCompareLib”
>
>     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
>
> 
 
 
 

 
 
 

[-- Attachment #2: Type: text/html, Size: 24865 bytes --]