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

Sun, 26 Sep 2021 04:20:56 -0700 

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 <gaolim...@byosoft.com.cn>
*Sent:* Sunday, September 26, 2021 10:01 AM

*To:* Ni, Ray <ray...@intel.com>; devel@edk2.groups.io; Chan, Amy 
<amy.c...@intel.com>; 'Andrew Fish' <af...@apple.com>
*Cc:* Kinney, Michael D <michael.d.kin...@intel.com>; 'Gao, Liming' 
<liming....@intel.com>; Liu, Zhiguang <zhiguang....@intel.com>; Wang, 
Jian J <jian.j.w...@intel.com>; Gao, Zhichao <zhichao....@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...@intel.com <mailto:ray...@intel.com>>
*发送时间:* 2021年9月24日 11:53

*收件人:* devel@edk2.groups.io <mailto:devel@edk2.groups.io>; Ni, Ray 
<ray...@intel.com <mailto:ray...@intel.com>>; Chan, Amy 
<amy.c...@intel.com <mailto:amy.c...@intel.com>>; gaoliming 
<gaolim...@byosoft.com.cn <mailto:gaolim...@byosoft.com.cn>>; 'Andrew 
Fish' <af...@apple.com <mailto:af...@apple.com>>
*抄送:* Kinney, Michael D <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; 'Gao, Liming' 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@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.c...@intel.com <mailto:amy.c...@intel.com>>; 
gaoliming <gaolim...@byosoft.com.cn 
<mailto:gaolim...@byosoft.com.cn>>; 'Andrew Fish' <af...@apple.com 
<mailto:af...@apple.com>>; 'edk2-devel-groups-io' 
<devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
*Cc:* Kinney, Michael D <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; 'Gao, Liming' 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@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.c...@intel.com <mailto:amy.c...@intel.com>>; 
gaoliming <gaolim...@byosoft.com.cn 
<mailto:gaolim...@byosoft.com.cn>>; 'Andrew Fish' <af...@apple.com 
<mailto:af...@apple.com>>; 'edk2-devel-groups-io' 
<devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
*Cc:* Kinney, Michael D <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; 'Gao, Liming' 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@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.c...@intel.com <mailto:amy.c...@intel.com>>
*Sent:* Thursday, September 16, 2021 10:46 AM

*To:* gaoliming <gaolim...@byosoft.com.cn 
<mailto:gaolim...@byosoft.com.cn>>; 'Andrew Fish' <af...@apple.com 
<mailto:af...@apple.com>>; 'edk2-devel-groups-io' 
<devel@edk2.groups.io <mailto:devel@edk2.groups.io>>
*Cc:* Ni, Ray <ray...@intel.com <mailto:ray...@intel.com>>; Kinney, 
Michael D <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; 'Gao, Liming' 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@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 <gaolim...@byosoft.com.cn 
<mailto:gaolim...@byosoft.com.cn>>

*Sent:* Thursday, September 16, 2021 10:23 AM

*To:* 'Andrew Fish' <af...@apple.com <mailto:af...@apple.com>>; 
'edk2-devel-groups-io' <devel@edk2.groups.io 
<mailto:devel@edk2.groups.io>>
*Cc:* Ni, Ray <ray...@intel.com <mailto:ray...@intel.com>>; Kinney, 
Michael D <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; 'Gao, Liming' 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@intel.com>>; Chan, Amy 
<amy.c...@intel.com <mailto:amy.c...@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 <af...@apple.com <mailto:af...@apple.com>>
*发送时间:* 2021年9月16日 10:13

*收件人:* edk2-devel-groups-io <devel@edk2.groups.io 
<mailto:devel@edk2.groups.io>>; Liming Gao <gaolim...@byosoft.com.cn 
<mailto:gaolim...@byosoft.com.cn>>
*抄送:* Ni, Ray <ray...@intel.com <mailto:ray...@intel.com>>; Mike 
Kinney <michael.d.kin...@intel.com 
<mailto:michael.d.kin...@intel.com>>; Gao, Liming 
<liming....@intel.com <mailto:liming....@intel.com>>; Liu, Zhiguang 
<zhiguang....@intel.com <mailto:zhiguang....@intel.com>>; Wang, Jian J 
<jian.j.w...@intel.com <mailto:jian.j.w...@intel.com>>; Gao, Zhichao 
<zhichao....@intel.com <mailto:zhichao....@intel.com>>; Chan, Amy 
<amy.c...@intel.com <mailto:amy.c...@intel.com>>

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

    On Sep 15, 2021, at 6:26 PM, gaoliming <gaolim...@byosoft.com.cn
    <mailto:gaolim...@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.kin...@intel.com
    <mailto:michael.d.kin...@intel.com>>; Gao, Liming
    <liming....@intel.com <mailto:liming....@intel.com>>; Liu,
    Zhiguang <zhiguang....@intel.com <mailto:zhiguang....@intel.com>>;
    Wang, Jian J <jian.j.w...@intel.com
    <mailto:jian.j.w...@intel.com>>; Gao, Zhichao
    <zhichao....@intel.com <mailto:zhichao....@intel.com>>
    *抄送:*devel@edk2.groups.io <mailto:devel@edk2.groups.io>; Chan, Amy
    <amy.c...@intel.com <mailto:amy.c...@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






-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81144): https://edk2.groups.io/g/devel/message/81144
Mute This Topic: https://groups.io/mt/85872410/21656
Group Owner: devel+ow...@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com]
-=-=-=-=-=-=-=-=-=-=-=-

























					Reply via email to