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

Tue, 28 Sep 2021 15:26:08 -0700

I'll add my agreement to Marvin and Jeff: a low-level sort routine like this should let the caller be in charge of memory allocation, so it can be used in the widest variety of contexts (SEC, exception handlers, APs, etc.) So let's make the BufferOneElement parameter mandatory. 

Brian J. Johnson

-------- Original Message --------
From: Ni, Ray [mailto:ray...@intel.com]
Sent: Monday, September 27, 2021, 8:49 PM
To: Marvin Häuser <mhaeu...@posteo.de>, fanjianf...@byosoft.com.cn <fanjianf...@byosoft.com.cn>, devel@edk2.groups.io <devel@edk2.groups.io>, 'gaoliming' <gaolim...@byosoft.com.cn>, 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

Marvin,
I agree with your concerns, in a certain level. But I didn't treat it
as a very big problem of having caller pass the BufferOneElement
"intelligently".

I am ok to use your option 1), making BufferOneElement mandatory.
Caller should always supply the buffer that's sufficient to hold one
element.

By the way, I don't want to propose "swap-without-using-temporary-value"
method to avoid using the "BufferOneElement"?
Because that makes the simple thing complicated!

Thanks,
Ray


-----Original Message-----
From: Marvin Häuser <mhaeu...@posteo.de>
Sent: Monday, September 27, 2021 5:09 PM
To: fanjianf...@byosoft.com.cn; devel@edk2.groups.io; Ni, Ray 
<ray...@intel.com>; 'gaoliming'
<gaolim...@byosoft.com.cn>; 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: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg

On 27/09/2021 10:50, fanjianf...@byosoft.com.cn wrote:

For former caller, they could still keep as is to call the old API in
MdeModulePkg. I think Ray's design is compatible change for existing code.
Only when the existing code wants to remove the dependency on
MdeModuelPkg, they could migrate to the new API in baselib.

I agree with one split-API desgin what you mentioned.
But my point is to define one API in baselib and to make the baselib
not depend on memory allocation. And another wrapper API could be
designed to be placed in any other class.


Oh sure, it could totally live in another class. I'd just like to have
those two models (caller- and callee-owned buffer) strictly separate, I
personally do not mind where exactly they are implemented. Thanks!

Best regards,
Marvin



------------------------------------------------------------------------
Jeff
fanjianf...@byosoft.com.cn

     *From:* Marvin Häuser <mailto:mhaeu...@posteo.de>
     *Date:* 2021-09-27 16:14
     *To:* fanjianf...@byosoft.com.cn
     <mailto:fanjianf...@byosoft.com.cn>; devel@edk2.groups.io
     <mailto:devel@edk2.groups.io>; Ni, Ray <mailto:ray...@intel.com>;
     'gaoliming' <mailto:gaolim...@byosoft.com.cn>; Chan, Amy
     <mailto:amy.c...@intel.com>; 'Andrew Fish' <mailto:af...@apple.com>
     *CC:* Kinney, Michael D <mailto:michael.d.kin...@intel.com>; 'Gao,
     Liming' <mailto:liming....@intel.com>; Liu, Zhiguang
     <mailto:zhiguang....@intel.com>; Wang, Jian J
     <mailto:jian.j.w...@intel.com>; Gao, Zhichao
     <mailto:zhichao....@intel.com>
     *Subject:* Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
     On 27/09/2021 02:45, fanjianf...@byosoft.com.cn wrote:
     > 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.
     That is why I asked about a split-API scenario, one of which does not
     depend on dynamic memory allocation (SetVariable-like) and one does
     (wrapper-like).
     > 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.
     Yes, and because that is SetVariable's implementation, we have
     library
     functions to make it less error-prone and more convenient [1]. As a
     matter of fact, we have a (semi-lax) policy in our codebases to avoid
     such functions like the plague and use those library wrappers
     where-ever
     it can make sense. The only super-rare exceptions I can think of are
     when we know the size of the element ahead of time. Also
     SetVariable has
     no arbitrary constraint on when it may work the first time, and
     there is
     code that will fail when the first return is not EFI_BUFFER_TOO_SMALL.
     This solution honestly yields even more problems, because it
     introduces
     a Status return which was not there before. For common code safety
     and
     quality policy, this requires the value *must* be retrieved and
     checked
     in some fashion. So all callers, no matter the prior knowledge of the
     element size, now need either a runtime check and handling for a
     status
     that they (may) know can never be returned, or ASSERTs if the
     function
     spec really imposes the arbitrary 256 Bytes constraint. Latter
     doesn't
     really work I think. What if someone wants to sort in SEC and noticed
     they only have 64 Bytes on the stack to work with, realistically? Any
     code depending on the 256 Byte constraint, passing NULL and not doing
     additional handling, would seize to work. Former is too
     complicated, see
     wrappers. In my opinion, the memory must *either* be fully managed by
     the caller *or* the callee (and you may have both in separate
     functions,
     as I suggested), but not sometimes here, sometimes there.
     Best regards,
     Marvin
     [1]


https://github.com/tianocore/edk2/blob/46b4606ba23498d3d0e66b53e498eb3d5d592586/MdePkg/Library/UefiLib/UefiLib.c#L
1309-L1360

     >
     >
     ------------------------------------------------------------------------
     > Jeff
     > fanjianf...@byosoft.com.cn
     >
     >     *From:* Marvin Häuser <mailto:mhaeu...@posteo.de>
     >     *Date:* 2021-09-26 19:20
     >     *To:* devel <mailto:devel@edk2.groups.io>; ray.ni
     >     <mailto:ray...@intel.com>; gaoliming
     >     <mailto:gaolim...@byosoft.com.cn>; Chan, Amy
     >     <mailto:amy.c...@intel.com>; 'Andrew Fish'
     <mailto:af...@apple.com>
     >     *CC:* Kinney, Michael D <mailto:michael.d.kin...@intel.com>;
     'Gao,
     >     Liming' <mailto:liming....@intel.com>; Liu, Zhiguang
     >     <mailto:zhiguang....@intel.com>; Wang, Jian J
     >     <mailto:jian.j.w...@intel.com>; Gao, Zhichao
     >     <mailto:zhichao....@intel.com>
     >     *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 <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
     >     >
     >     >
     >
     >









--

                                                Brian

--------------------------------------------------------------------

   "Remember that ignorance is expensive."
                                           -- From LLIB




-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81234): https://edk2.groups.io/g/devel/message/81234
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