From: "Ni, Ray" <ray.ni@intel.com>
To: gaoliming <gaoliming@byosoft.com.cn>,
"devel@edk2.groups.io" <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: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Date: Sun, 26 Sep 2021 02:24:24 +0000 [thread overview]
Message-ID: <CY4PR1101MB2072206581E14970D2AFBFCF8CA69@CY4PR1101MB2072.namprd11.prod.outlook.com> (raw)
In-Reply-To: <00cf01d7b27a$59145d20$0b3d1760$@byosoft.com.cn>
[-- Attachment #1: Type: text/plain, Size: 11567 bytes --]
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
);
1. “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: 47270 bytes --]
next prev parent reply other threads:[~2021-09-26 2:24 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-14 6:15 RFC: Add BaseLib/QuickSort in MdePkg Ni, Ray
2021-09-16 1:26 ` 回复: [edk2-devel] " gaoliming
2021-09-16 2:13 ` Andrew Fish
2021-09-16 2:23 ` 回复: " gaoliming
2021-09-16 2:45 ` Chan, Amy
2021-09-16 2:47 ` Ni, Ray
2021-09-22 6:03 ` Ni, Ray
[not found] ` <16A70FAC1585C7C1.27516@groups.io>
2021-09-24 3:53 ` Ni, Ray
2021-09-26 2:00 ` 回复: " gaoliming
2021-09-26 2:24 ` Ni, Ray [this message]
2021-09-26 11:20 ` Marvin Häuser
2021-09-27 0:45 ` Jeff Fan
2021-09-27 8:14 ` Marvin Häuser
2021-09-27 8:50 ` Jeff Fan
2021-09-27 9:09 ` Marvin Häuser
2021-09-28 1:49 ` Ni, Ray
2021-09-28 22:25 ` Brian J. Johnson
2021-09-29 0:51 ` 回复: " gaoliming
2021-09-29 2:42 ` Ni, Ray
[not found] ` <16A8A1ADDB4E97C4.26412@groups.io>
2021-09-27 9:06 ` Jeff Fan
2021-09-16 2:47 ` Ni, Ray
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CY4PR1101MB2072206581E14970D2AFBFCF8CA69@CY4PR1101MB2072.namprd11.prod.outlook.com \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox