From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by mx.groups.io with SMTP id smtpd.web08.7756.1610543697727429733 for ; Wed, 13 Jan 2021 05:15:03 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=TGhT91xK; spf=pass (domain: redhat.com, ip: 63.128.21.124, mailfrom: philmd@redhat.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610543696; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=zgBxS3OPsAYzGuiqMnZ9x0BI24lAsgMn2kgAvCy8RU0=; b=TGhT91xK9Y8Jtp8Pjcy392uo2cL5YiefHbsyWFLeHMlF5Ac5hcEEVEUjUn4ToNwAnw8c/X FnLjPAr8FRWRKDowMCDqbISPRcyb6PE19TrlxIqCqEm0mo4QtmdkXvPMF1pvS1iC5XZOOI O7uPMmjL5fE26q7tHs65/FNvr7T62QI= Received: from mail-wm1-f72.google.com (mail-wm1-f72.google.com [209.85.128.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-132-vUePhslfMca5kCWJlmGDQQ-1; Wed, 13 Jan 2021 08:14:53 -0500 X-MC-Unique: vUePhslfMca5kCWJlmGDQQ-1 Received: by mail-wm1-f72.google.com with SMTP id u18so795472wmu.4 for ; Wed, 13 Jan 2021 05:14:53 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=zgBxS3OPsAYzGuiqMnZ9x0BI24lAsgMn2kgAvCy8RU0=; b=WH1zj7wAf6LxQwpPainnKDyUP2DzkzGmacsmpC9EIxroEnJ1S9TcGUaCet0UR9NoGe ytUC33/UdySreM0qg7FTNIno3/lpBQy4IMa4vvyAmcYxuHD/iIUHRye9k0LQNYxeWMuw yebnb1aX1PxXwv0GXipU56Ky2sJbki/BwWC3fsV9R3eV4yQBK1CfjT+qMuiRKmmU+I6f og3U8OazIDWE++2HQsH5YQR//IJulSCP3oDLCIZC79DTSwDE8EOI+YUgGwDqwfX9k4QJ Wmdl2ZyIFoz3bQWqvIT2L77T/km81nQ3U0Xs7TNcXVxm44sMJucB7xUaj5c7mK1A5vjD OJIw== X-Gm-Message-State: AOAM530SbHopxuaGA2Ye8OMrxLmY+XGhQmjyTsHf/egmKSOSrfj/8qOQ 7EyB4oF+P2KoJlzigiad3hBK7mvXQm5CaEJyXC3TUxTBcaMrAdMeXISX1rZZIr88ZkGg2JVJuwr F3pYyCl+iauGtgw== X-Received: by 2002:a5d:6686:: with SMTP id l6mr2597382wru.236.1610543692037; Wed, 13 Jan 2021 05:14:52 -0800 (PST) X-Google-Smtp-Source: ABdhPJy6BSu9vYNY3pR4oTni0oDWc9D3iQzQ7NyrLOWs1XUFlDw2ycuNOfsK+si776c85xkIKvRP1A== X-Received: by 2002:a5d:6686:: with SMTP id l6mr2597356wru.236.1610543691758; Wed, 13 Jan 2021 05:14:51 -0800 (PST) Return-Path: Received: from [192.168.1.36] (190.red-83-57-173.dynamicip.rima-tde.net. [83.57.173.190]) by smtp.gmail.com with ESMTPSA id u13sm3453456wrw.11.2021.01.13.05.14.50 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 13 Jan 2021 05:14:50 -0800 (PST) Subject: Re: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() To: Laszlo Ersek , devel@edk2.groups.io Cc: Ray Ni , Zhichao Gao References: <20210113085453.10168-1-lersek@redhat.com> <20210113085453.10168-9-lersek@redhat.com> From: =?UTF-8?B?UGhpbGlwcGUgTWF0aGlldS1EYXVkw6k=?= Message-ID: <543264c0-1709-073b-e82b-8dcdf412213f@redhat.com> Date: Wed, 13 Jan 2021 14:14:49 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.6.0 MIME-Version: 1.0 In-Reply-To: <20210113085453.10168-9-lersek@redhat.com> Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=philmd@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit On 1/13/21 9:54 AM, Laszlo Ersek wrote: > The current implementation of EfiShellRemoveDupInFileList(): > - has quadratic time complexity, as a disadvantage, and > - needs no dynamic memory, as an advantage. > > Because the UEFI Shell Spec requires > EFI_SHELL_PROTOCOL.RemoveDupInFileList() to succeed at all times, keep the > current method as a fallback (it cannot fail due to needing no dynamic > memory). > > However, as a higher priority option, call the new ShellSortFileList() > function at first, separating out and releasing duplicates. > (ShellSortFileList() can fail due to EFI_OUT_OF_RESOURCES.) > > Beyond improving the runtime of EfiShellRemoveDupInFileList(), this change > has the extremely desirable effect that the ShellOpenFileMetaArg() > function in the ShellPkg/Library/UefiShellLib instance will produce file > lists that are sorted by FullName. > > Consequently, when used with wildcards, the ATTRIB, CP, FOR, LOAD, > LOADPCIROM, LS, MV, RM, TOUCH, TYPE commands will process files in > FullName order. (LS in recursive mode uses wildcards internally.) > > Before: > >> FS2:\> dir -r -sfo apps >> [...] >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\X64" >> FileInfo,"FS2:\apps\AARCH64" >> FileInfo,"FS2:\" >> FileInfo,"FS2:\apps\IA32" >> FileInfo,"FS2:\apps\X64\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\X64\SmiHandlerProfileInfo.efi" >> FileInfo,"FS2:\apps\X64\" >> FileInfo,"FS2:\apps\X64\VariableInfo.efi" >> FileInfo,"FS2:\apps\X64\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\X64\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\X64\Cpuid.efi" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\AARCH64\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\AARCH64\" >> FileInfo,"FS2:\apps\AARCH64\VariableInfo.efi" >> FileInfo,"FS2:\apps\AARCH64\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\AARCH64\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\IA32\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\IA32\SmiHandlerProfileInfo.efi" >> FileInfo,"FS2:\apps\IA32\" >> FileInfo,"FS2:\apps\IA32\VariableInfo.efi" >> FileInfo,"FS2:\apps\IA32\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\IA32\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\IA32\Cpuid.efi" >> FileInfo,"FS2:\apps\" > > After: > >> FS2:\> dir -r -sfo apps >> [...] >> FileInfo,"FS2:\" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\AARCH64" >> FileInfo,"FS2:\apps\IA32" >> FileInfo,"FS2:\apps\X64" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\AARCH64\" >> FileInfo,"FS2:\apps\AARCH64\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\AARCH64\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\AARCH64\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\AARCH64\VariableInfo.efi" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\IA32\" >> FileInfo,"FS2:\apps\IA32\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\IA32\Cpuid.efi" >> FileInfo,"FS2:\apps\IA32\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\IA32\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\IA32\SmiHandlerProfileInfo.efi" >> FileInfo,"FS2:\apps\IA32\VariableInfo.efi" >> FileInfo,"FS2:\apps\" >> FileInfo,"FS2:\apps\X64\" >> FileInfo,"FS2:\apps\X64\AcpiViewApp.efi" >> FileInfo,"FS2:\apps\X64\Cpuid.efi" >> FileInfo,"FS2:\apps\X64\DumpDynPcd.efi" >> FileInfo,"FS2:\apps\X64\MemoryProfileInfo.efi" >> FileInfo,"FS2:\apps\X64\SmiHandlerProfileInfo.efi" >> FileInfo,"FS2:\apps\X64\VariableInfo.efi" > > Regarding LS in non-SFO mode, the stability of ShellSortFileList() shows. > The ShellSortFileList() call added to LS in the previous patch re-sorts > the output of ShellOpenFileMetaArg(); and so this patch improves the > ordering between identical FileNames: > > Before: > >> FS2:\> dir -r apps >> Directory of: FS2:\apps\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 4,096 AARCH64 >> 12/22/2020 17:53 4,096 IA32 >> 12/22/2020 17:53 4,096 X64 >> 0 File(s) 0 bytes >> 5 Dir(s) >> Directory of: FS2:\apps\X64\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 126,656 AcpiViewApp.efi >> 12/22/2020 17:53 38,784 Cpuid.efi >> 12/22/2020 17:52 18,752 DumpDynPcd.efi >> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 11,456 VariableInfo.efi >> 6 File(s) 256,192 bytes >> 2 Dir(s) >> Directory of: FS2:\apps\AARCH64\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 139,264 AcpiViewApp.efi >> 12/22/2020 17:52 32,768 DumpDynPcd.efi >> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >> 12/22/2020 17:52 20,480 VariableInfo.efi >> 4 File(s) 233,472 bytes >> 2 Dir(s) >> Directory of: FS2:\apps\IA32\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 105,536 AcpiViewApp.efi >> 12/22/2020 17:53 36,096 Cpuid.efi >> 12/22/2020 17:52 17,344 DumpDynPcd.efi >> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 10,880 VariableInfo.efi >> 6 File(s) 224,768 bytes >> 2 Dir(s) >> >> FS2:\> dir apps\*\*.efi >> Directory of: FS2:\apps\*\ >> 12/22/2020 17:53 126,656 AcpiViewApp.efi >> 12/22/2020 17:53 139,264 AcpiViewApp.efi >> 12/22/2020 17:53 105,536 AcpiViewApp.efi >> 12/22/2020 17:53 38,784 Cpuid.efi >> 12/22/2020 17:53 36,096 Cpuid.efi >> 12/22/2020 17:52 18,752 DumpDynPcd.efi >> 12/22/2020 17:52 32,768 DumpDynPcd.efi >> 12/22/2020 17:52 17,344 DumpDynPcd.efi >> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 11,456 VariableInfo.efi >> 12/22/2020 17:52 20,480 VariableInfo.efi >> 12/22/2020 17:52 10,880 VariableInfo.efi >> 16 File(s) 714,432 bytes >> 0 Dir(s) > > After: > >> FS2:\> dir -r apps >> Directory of: FS2:\apps\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 4,096 AARCH64 >> 12/22/2020 17:53 4,096 IA32 >> 12/22/2020 17:53 4,096 X64 >> 0 File(s) 0 bytes >> 5 Dir(s) >> Directory of: FS2:\apps\AARCH64\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 139,264 AcpiViewApp.efi >> 12/22/2020 17:52 32,768 DumpDynPcd.efi >> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >> 12/22/2020 17:52 20,480 VariableInfo.efi >> 4 File(s) 233,472 bytes >> 2 Dir(s) >> Directory of: FS2:\apps\IA32\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 105,536 AcpiViewApp.efi >> 12/22/2020 17:53 36,096 Cpuid.efi >> 12/22/2020 17:52 17,344 DumpDynPcd.efi >> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 10,880 VariableInfo.efi >> 6 File(s) 224,768 bytes >> 2 Dir(s) >> Directory of: FS2:\apps\X64\ >> 01/01/1970 01:00 r 0 . >> 01/01/1970 01:00 r 0 .. >> 12/22/2020 17:53 126,656 AcpiViewApp.efi >> 12/22/2020 17:53 38,784 Cpuid.efi >> 12/22/2020 17:52 18,752 DumpDynPcd.efi >> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 11,456 VariableInfo.efi >> 6 File(s) 256,192 bytes >> 2 Dir(s) >> >> FS2:\> dir apps\*\*.efi >> Directory of: FS2:\apps\*\ >> 12/22/2020 17:53 139,264 AcpiViewApp.efi >> 12/22/2020 17:53 105,536 AcpiViewApp.efi >> 12/22/2020 17:53 126,656 AcpiViewApp.efi >> 12/22/2020 17:53 36,096 Cpuid.efi >> 12/22/2020 17:53 38,784 Cpuid.efi >> 12/22/2020 17:52 32,768 DumpDynPcd.efi >> 12/22/2020 17:52 17,344 DumpDynPcd.efi >> 12/22/2020 17:52 18,752 DumpDynPcd.efi >> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >> 12/22/2020 17:52 20,480 VariableInfo.efi >> 12/22/2020 17:52 10,880 VariableInfo.efi >> 12/22/2020 17:52 11,456 VariableInfo.efi >> 16 File(s) 714,432 bytes >> 0 Dir(s) > > Cc: Philippe Mathieu-Daudé > Cc: Ray Ni > Cc: Zhichao Gao > Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151 > Signed-off-by: Laszlo Ersek > Reviewed-by: Zhichao Gao > --- > > Notes: > v2: > - no changes > - pick up Zhichao's R-b > > ShellPkg/Application/Shell/ShellProtocol.c | 16 ++++++++++++++++ > 1 file changed, 16 insertions(+) Reviewed-by: Philippe Mathieu-Daude