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

["Marvin Häuser" <mhaeuser@posteo.de>]

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
>
>