| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAGsJ_4wUZrxqdzObpEk_gpcHEO6e75ai=8q-fsv4eXN2wNEbOw@mail.gmail.com>
Date: Thu, 8 May 2025 13:29:30 +1200
From: Barry Song <21cnbao@...il.com>
To: Xavier <xavier_qy@....com>
Cc: Ryan Roberts <ryan.roberts@....com>, dev.jain@....com, ioworker0@...il.com,
akpm@...ux-foundation.org, catalin.marinas@....com, david@...hat.com,
gshan@...hat.com, linux-arm-kernel@...ts.infradead.org,
linux-kernel@...r.kernel.org, will@...nel.org, willy@...radead.org,
ziy@...dia.com
Subject: Re: [mm/contpte v3 1/1] mm/contpte: Optimize loop to reduce redundant operations
On Sun, May 4, 2025 at 2:56 PM Xavier <xavier_qy@....com> wrote:
> At 2025-05-02 05:32:50, "Barry Song" <21cnbao@...il.com> wrote:
> >On Fri, May 2, 2025 at 9:19 AM Barry Song <21cnbao@...il.com> wrote:
> >>
> >> On Fri, May 2, 2025 at 12:41 AM Xavier <xavier_qy@....com> wrote:
> >> >
> >> >
> >> >
> >> > Hi Barry,
> >> >
> >> >
> >> > At 2025-05-01 07:17:36, "Barry Song" <21cnbao@...il.com> wrote:
> >> > >On Tue, Apr 22, 2025 at 9:34 PM Xavier <xavier_qy@....com> wrote:
> >> > >>
> >> > >>
> >> > >> Hi all,
> >> > >>
> >> > >>
> >> > >> At 2025-04-16 20:54:47, "Ryan Roberts" <ryan.roberts@....com> wrote:
> >> > >> >On 15/04/2025 09:22, Xavier wrote:
> >> > >> >> This commit optimizes the contpte_ptep_get function by adding early
> >> > >> >> termination logic. It checks if the dirty and young bits of orig_pte
> >> > >> >> are already set and skips redundant bit-setting operations during
> >> > >> >> the loop. This reduces unnecessary iterations and improves performance.
> >> > >> >>
> >> > >> >> Signed-off-by: Xavier <xavier_qy@....com>
> >> > >> >> ---
> >> > >> >> arch/arm64/mm/contpte.c | 20 ++++++++++++++++++--
> >> > >> >> 1 file changed, 18 insertions(+), 2 deletions(-)
> >> > >> >>
> >> > >> >> diff --git a/arch/arm64/mm/contpte.c b/arch/arm64/mm/contpte.c
> >> > >> >> index bcac4f55f9c1..0acfee604947 100644
> >> > >> >> --- a/arch/arm64/mm/contpte.c
> >> > >> >> +++ b/arch/arm64/mm/contpte.c
> >> > >> >> @@ -152,6 +152,16 @@ void __contpte_try_unfold(struct mm_struct *mm, unsigned long addr,
> >> > >> >> }
> >> > >> >> EXPORT_SYMBOL_GPL(__contpte_try_unfold);
> >> > >> >>
> >> > >> >> +/* Note: in order to improve efficiency, using this macro will modify the
> >> > >> >> + * passed-in parameters.*/
> >> > >> >> +#define CHECK_CONTPTE_FLAG(start, ptep, orig_pte, flag) \
> >> > >> >> + for (; (start) < CONT_PTES; (start)++, (ptep)++) { \
> >> > >> >> + if (pte_##flag(__ptep_get(ptep))) { \
> >> > >> >> + orig_pte = pte_mk##flag(orig_pte); \
> >> > >> >> + break; \
> >> > >> >> + } \
> >> > >> >> + }
> >> > >> >
> >> > >> >I'm really not a fan of this macro, it just obfuscates what is going on. I'd
> >> > >> >personally prefer to see the 2 extra loops open coded below.
> >> > >> >
> >> > >> >Or even better, could you provide results comparing this 3 loop version to the
> >> > >> >simpler approach I suggested previously? If the performance is similar (which I
> >> > >> >expect it will be, especially given Barry's point that your test always ensures
> >> > >> >the first PTE is both young and dirty) then I'd prefer to go with the simpler code.
> >> > >> >
> >> > >>
> >> > >> Based on the discussions in the previous email, two modifications were adopted
> >> > >> and tested, and the results are as follows:
> >> > >>
> >> > >> Modification 1
> >> > >>
> >> > >> pte_t contpte_ptep_get(pte_t *ptep, pte_t orig_pte)
> >> > >> {
> >> > >> pte_t pte;
> >> > >> int i;
> >> > >>
> >> > >> ptep = contpte_align_down(ptep);
> >> > >>
> >> > >> for (i = 0; i < CONT_PTES; i++, ptep++) {
> >> > >> pte = __ptep_get(ptep);
> >> > >>
> >> > >> if (pte_dirty(pte)) {
> >> > >> orig_pte = pte_mkdirty(orig_pte);
> >> > >> if (pte_young(orig_pte))
> >> > >> break;
> >> > >> }
> >> > >>
> >> > >> if (pte_young(pte)) {
> >> > >> orig_pte = pte_mkyoung(orig_pte);
> >> > >> if (pte_dirty(orig_pte))
> >> > >> break;
> >> > >> }
> >> > >> }
> >> > >>
> >> > >> return orig_pte;
> >> > >> }
> >> > >>
> >> > >> Modification 2
> >> > >>
> >> > >> pte_t contpte_ptep_get(pte_t *ptep, pte_t orig_pte)
> >> > >> {
> >> > >> pte_t pte;
> >> > >> int i;
> >> > >>
> >> > >> ptep = contpte_align_down(ptep);
> >> > >>
> >> > >> for (i = 0; i < CONT_PTES; i++, ptep++) {
> >> > >> pte = __ptep_get(ptep);
> >> > >>
> >> > >> if (pte_dirty(pte)) {
> >> > >> orig_pte = pte_mkdirty(orig_pte);
> >> > >> for (; i < CONT_PTES; i++, ptep++) {
> >> > >> pte = __ptep_get(ptep);
> >> > >> if (pte_young(pte)) {
> >> > >> orig_pte = pte_mkyoung(orig_pte);
> >> > >> break;
> >> > >> }
> >> > >> }
> >> > >> break;
> >> > >> }
> >> > >>
> >> > >> if (pte_young(pte)) {
> >> > >> orig_pte = pte_mkyoung(orig_pte);
> >> > >> i++;
> >> > >> ptep++;
> >> > >> for (; i < CONT_PTES; i++, ptep++) {
> >> > >> pte = __ptep_get(ptep);
> >> > >> if (pte_dirty(pte)) {
> >> > >> orig_pte = pte_mkdirty(orig_pte);
> >> > >> break;
> >> > >> }
> >> > >> }
> >> > >> break;
> >> > >> }
> >> > >> }
> >> > >>
> >> > >> return orig_pte;
> >> > >> }
> >> > >>
> >> > >> Test Code:
> >> > >>
> >> > >> #define PAGE_SIZE 4096
> >> > >> #define CONT_PTES 16
> >> > >> #define TEST_SIZE (4096* CONT_PTES * PAGE_SIZE)
> >> > >> #define YOUNG_BIT 8
> >> > >> void rwdata(char *buf)
> >> > >> {
> >> > >> for (size_t i = 0; i < TEST_SIZE; i += PAGE_SIZE) {
> >> > >> buf[i] = 'a';
> >> > >> volatile char c = buf[i];
> >> > >> }
> >> > >> }
> >> > >> void clear_young_dirty(char *buf)
> >> > >> {
> >> > >> if (madvise(buf, TEST_SIZE, MADV_FREE) == -1) {
> >> > >> perror("madvise free failed");
> >> > >> free(buf);
> >> > >> exit(EXIT_FAILURE);
> >> > >> }
> >> > >> if (madvise(buf, TEST_SIZE, MADV_COLD) == -1) {
> >> > >> perror("madvise free failed");
> >> > >> free(buf);
> >> > >> exit(EXIT_FAILURE);
> >> > >> }
> >> > >> }
> >> > >> void set_one_young(char *buf)
> >> > >> {
> >> > >> for (size_t i = 0; i < TEST_SIZE; i += CONT_PTES * PAGE_SIZE) {
> >> > >> volatile char c = buf[i + YOUNG_BIT * PAGE_SIZE];
> >> > >> }
> >> > >> }
> >> > >>
> >> > >> void test_contpte_perf() {
> >> > >> char *buf;
> >> > >> int ret = posix_memalign((void **)&buf, CONT_PTES * PAGE_SIZE, TEST_SIZE);
> >> > >> if ((ret != 0) || ((unsigned long)buf % CONT_PTES * PAGE_SIZE)) {
> >> > >> perror("posix_memalign failed");
> >> > >> exit(EXIT_FAILURE);
> >> > >> }
> >> > >>
> >> > >> rwdata(buf);
> >> > >> #if TEST_CASE2 || TEST_CASE3
> >> > >> clear_young_dirty(buf);
> >> > >> #endif
> >> > >> #if TEST_CASE2
> >> > >> set_one_young(buf);
> >> > >> #endif
> >> > >>
> >> > >> for (int j = 0; j < 500; j++) {
> >> > >> mlock(buf, TEST_SIZE);
> >> > >>
> >> > >> munlock(buf, TEST_SIZE);
> >> > >> }
> >> > >> free(buf);
> >> > >> }
> >> > >> ---
> >> > >>
> >> > >> Descriptions of three test scenarios
> >> > >>
> >> > >> Scenario 1
> >> > >> The data of all 16 PTEs are both dirty and young.
> >> > >> #define TEST_CASE2 0
> >> > >> #define TEST_CASE3 0
> >> > >>
> >> > >> Scenario 2
> >> > >> Among the 16 PTEs, only the 8th one is young, and there are no dirty ones.
> >> > >> #define TEST_CASE2 1
> >> > >> #define TEST_CASE3 0
> >> > >>
> >> > >> Scenario 3
> >> > >> Among the 16 PTEs, there are neither young nor dirty ones.
> >> > >> #define TEST_CASE2 0
> >> > >> #define TEST_CASE3 1
> >> > >>
> >> > >>
> >> > >> Test results
> >> > >>
> >> > >> |Scenario 1 | Original| Modification 1| Modification 2|
> >> > >> |-------------------|---------------|----------------|----------------|
> >> > >> |instructions | 37912436160| 18303833386| 18731580031|
> >> > >> |test time | 4.2797| 2.2687| 2.2949|
> >> > >> |overhead of | | | |
> >> > >> |contpte_ptep_get() | 21.31%| 4.72%| 4.80%|
> >> > >>
> >> > >> |Scenario 2 | Original| Modification 1| Modification 2|
> >> > >> |-------------------|---------------|----------------|----------------|
> >> > >> |instructions | 36701270862| 38729716276| 36115790086|
> >> > >> |test time | 3.2335| 3.5732| 3.0874|
> >> > >> |Overhead of | | | |
> >> > >> |contpte_ptep_get() | 32.26%| 41.35%| 33.57%|
> >> > >>
> >> > >> |Scenario 3 | Original| Modification 1| Modification 2|
> >> > >> |-------------------|---------------|----------------|----------------|
> >> > >> |instructions | 36706279735| 38305241759| 36750881878|
> >> > >> |test time | 3.2008| 3.5389| 3.1249|
> >> > >> |Overhead of | | | |
> >> > >> |contpte_ptep_get() | 31.94%| 41.30%| 34.59%|
> >> > >>
> >> > >>
> >> > >> For Scenario 1, Modification 1 can achieve an instruction count benefit of
> >> > >> 51.72% and a time benefit of 46.99%. Modification 2 can achieve an instruction
> >> > >> benefit of 50.59% and a time benefit of 46.38%.
> >> > >>
> >> > >> For Scenarios 2, Modification 2 can achieve an instruction count benefit of
> >> > >> 1.6% and a time benefit of 4.5%. while Modification 1 significantly increases
> >> > >> the instructions and time due to additional conditional checks.
> >> > >>
> >> > >> For Scenario 3, since all the PTEs have neither the young nor the dirty flag,
> >> > >> the branches taken by Modification 1 and Modification 2 should be the same as
> >> > >> those of the original code. In fact, the test results of Modification 2 seem
> >> > >> to be closer to those of the original code. I don't know why there is a
> >> > >> performance regression in Modification 1.
> >> > >>
> >> > >> Therefore, I believe modifying the code according to Modification 2 can bring
> >> > >> maximum benefits. Everyone can discuss whether this approach is acceptable,
> >> > >> and if so, I will send Patch V4 to proceed with submitting this modification.
> >> > >>
> >> > >
> >> > >modification 2 is not correct. if pte0~pte14 are all young and no one
> >> > >is dirty, we are
> >> > >having lots of useless "for (; i < CONT_PTES; i++, ptep++)"
> >> > >
> >> > > if (pte_young(pte)) {
> >> > > orig_pte = pte_mkyoung(orig_pte);
> >> > > i++;
> >> > > ptep++;
> >> > > for (; i < CONT_PTES; i++, ptep++) {
> >> > > pte = __ptep_get(ptep);
> >> > > if (pte_dirty(pte)) {
> >> > > orig_pte = pte_mkdirty(orig_pte);
> >> > > break;
> >> > > }
> >> > > }
> >> > > break;
> >> > > }
> >> > >
> >> >
> >> > I didn't understand which part you referred to when you said there were a lot of
> >> > useless loops. According to the scenario you mentioned, "if pte0~pte14 are all
> >> > young and no one is dirty", Modification 2 will enter the following branch when
> >> > judging pte0:
> >> >
> >> > if (pte_young(pte)) {
> >> > orig_pte = pte_mkyoung(orig_pte);
> >> > // The dirty status of pte0 has already been checked, skip it.
> >> > i++;
> >> > ptep++;
> >> > // Then we only need to check whether pte1~pte15 are dirty.
> >> > for (; i < CONT_PTES; i++, ptep++) {
> >> > pte = __ptep_get(ptep);
> >> > if (pte_dirty(pte)) {
> >> > // Exit as soon as a dirty entry is found.
> >> > orig_pte = pte_mkdirty(orig_pte);
> >> > break;
> >> > }
> >> > }
> >> > // Exit directly here without going through the outer loop again.
> >> > break;
> >> > }
> >> >
> >> > In this scenario, the total number of judgments in Modification 2 is nearly half less
> >> > than that of the original code. I should have understood it correctly, right?
> >>
> >> You're right—I missed the part where you're also taking a break, even though
> >> no one is dirty. Based on your data, modification 2 seems to be good.
> >>
> >> But I don't quite understand why you are doing
> >> i++;
> >> ptep++;
> >> before for (; i < CONT_PTES; i++, ptep++).
> >>
> >> it seems to be wrong. if i==15, you will get i=16. you are skipping
> >> the pte_dirty
> >> check for i==15. it is also true for any value between 0 and 15. My
> >> point is that
> >> you should drop it and re-test.
> >
> >Sorry, I missed that you already checked pte_dirty(pte) before calling
> >pte_young(). So please ignore my comment. The code's a bit hard to
> >follow now. :-)
> >
>
> The modification 2 is indeed a bit difficult to understand, but this is also to improve
> the execution efficiency. Thanks for your careful review. :-)
Agreed. Personally, I have no objections to Modification 2, as it demonstrates
performance improvements in nearly all cases according to your data.
>
> --
> Thanks,
> Xavier
Thanks
Barry
Powered by blists - more mailing lists