Skip to contentSkip to conversation

KVM: x86/mmu: Speed up slot_rmap_walk_next for sparsely populated rmaps

PATCH Superseded Vipin Sharma 4 participants 9 messages Mar 25, 2022 – Apr 26, 2022

Subsystems (3)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 KVM: x86/mmu: Speed up slot_rmap_walk_next for sparsely populated rmaps

Avoid calling handlers on empty rmap entries and skip to the next non empty rmap entry.

Empty rmap entries are noop in handlers.

Change-Id I8abf0f4d82a2aae4c5d58b80bcc17ffc30785ffc
---
 arch/x86/kvm/mmu/mmu.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
arch/x86/kvm/mmu/mmu.c +6 -3
index 51671cb34fb6..f296340803ba 100644
@@ -1499,11 +1499,14 @@ static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator)
 	return !!iterator->rmap;
 }
 
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void
+slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
 {
-	if (++iterator->rmap <= iterator->end_rmap) {
+	while (++iterator->rmap <= iterator->end_rmap) {
 		iterator->gfn += (1UL << KVM_HPAGE_GFN_SHIFT(iterator->level));
-		return;
+
+		if (iterator->rmap->val)
+			return;
 	}
 
 	if (++iterator->level > iterator->end_level) {

base-commit: c9b8fecddb5bb4b67e351bbaeaa648a6f7456912

Signature · 1 line
2.35.1.1021.g381101b075-goog
#1 lore raw
Quoted 9 lines · Vipin Sharma

Avoid calling handlers on empty rmap entries and skip to the next non empty rmap entry.

Empty rmap entries are noop in handlers.

Change-Id I8abf0f4d82a2aae4c5d58b80bcc17ffc30785ffc

nit: Omit Change-Id tags from upstream commits.

Quoted 9 lines
---
 arch/x86/kvm/mmu/mmu.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
arch/x86/kvm/mmu/mmu.c +0 -0
index 51671cb34fb6..f296340803ba 100644

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 5 lines
arch/x86/kvm/mmu/mmu.c +1 -1
@@ -1499,11 +1499,14 @@ static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator)
        return !!iterator->rmap;
 }
 
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

Quoted 17 lines
arch/x86/kvm/mmu/mmu.c +5 -2
+slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
 {
-       if (++iterator->rmap <= iterator->end_rmap) {
+       while (++iterator->rmap <= iterator->end_rmap) {
                iterator->gfn += (1UL << KVM_HPAGE_GFN_SHIFT(iterator->level));
-               return;
+
+               if (iterator->rmap->val)
+                       return;
        }
 
        if (++iterator->level > iterator->end_level) {

base-commit: c9b8fecddb5bb4b67e351bbaeaa648a6f7456912 --
2.35.1.1021.g381101b075-goog

#2 lore raw
Quoted 6 lines · David Matlack
Quoted 4 lines · Vipin Sharma

Avoid calling handlers on empty rmap entries and skip to the next non empty rmap entry.

Quoted 7 lines
Quoted 5 lines

Empty rmap entries are noop in handlers.

Change-Id I8abf0f4d82a2aae4c5d58b80bcc17ffc30785ffc

nit: Omit Change-Id tags from upstream commits.

Thanks for catching it.

Quoted 13 lines
Quoted 13 lines
---
 arch/x86/kvm/mmu/mmu.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
arch/x86/kvm/mmu/mmu.c +0 -0
index 51671cb34fb6..f296340803ba 100644
@@ -1499,11 +1499,14 @@ static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator)
        return !!iterator->rmap;
 }
 
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

maintainer
#3 lore raw
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Paolo

#4 lore raw

Thank you David and Paolo, for checking this patch carefully. With hindsight, I should have explicitly mentioned adding "noinline" in my patch email.

Quoted 18 lines · Paolo Bonzini
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

Quoted 4 lines

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Yeah, I should have added the "size mmu.o" output. Here is what I have found:

size arch/x86/kvm/mmu/mmu.o

Without noinline:
text data bss dec hex filename
89938 15793 72 105803 19d4b arch/x86/kvm/mmu/mmu.o

With noinline:
text data bss dec hex filename
90058 15793 72 105923 19dc3 arch/x86/kvm/mmu/mmu.o

With noinline, increase in size = 120

Curiously, I also checked file size with "ls -l" command File size:

        Without noinline: 1394272 bytes
        With noinline: 1381216 bytes

With noinline, decrease in size = 13056 bytes

I also disassembled mmu.o via "objdump -d" and found following Total lines in the generated assembly:

        Without noinline: 23438
        With noinline: 23393

With noinline, decrease in assembly code = 45

I can see in assembly code that there are multiple "call" operations in the "with noinline" object file, which is expected and has less lines of code compared to "without noinline". I am not sure why the size command is showing an increase in text segment for "with noinline" and what to infer with all of this data.

Thanks
Vipin

#5 lore raw
Quoted 54 lines · Vipin Sharma

Thank you David and Paolo, for checking this patch carefully. With hindsight, I should have explicitly mentioned adding "noinline" in my patch email.

Quoted 18 lines · Paolo Bonzini
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

Quoted 4 lines

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Yeah, I should have added the "size mmu.o" output. Here is what I have found:

size arch/x86/kvm/mmu/mmu.o

Without noinline:
text data bss dec hex filename
89938 15793 72 105803 19d4b arch/x86/kvm/mmu/mmu.o

With noinline:
text data bss dec hex filename
90058 15793 72 105923 19dc3 arch/x86/kvm/mmu/mmu.o

With noinline, increase in size = 120

Curiously, I also checked file size with "ls -l" command File size:

        Without noinline: 1394272 bytes
        With noinline: 1381216 bytes

With noinline, decrease in size = 13056 bytes

I also disassembled mmu.o via "objdump -d" and found following Total lines in the generated assembly:

        Without noinline: 23438
        With noinline: 23393
Quoted 7 lines

With noinline, decrease in assembly code = 45

I can see in assembly code that there are multiple "call" operations in the "with noinline" object file, which is expected and has less lines of code compared to "without noinline". I am not sure why the size command is showing an increase in text segment for "with noinline" and what to infer with all of this data.

The most common takeaway from these types of exercises is that trying to be smarter than the compiler is usually a fools errand. Smaller code footprint doesn't necessarily equate to better runtime performance. And conversely, inlining may not always be a win, which is why tagging static helpers (not in headers) with "inline" is generally discouraged.

IMO, unless there's an explicit side effect we want (or want to avoid), we should never use "noinline". E.g. the VMX <insn>_error() handlers use noinline so that KVM only WARNs once per failure of instruction type, and fxregs_fixup() uses it to keep the stack size manageable.

#6 lore raw
In reply to Paolo Bonzini
Quoted 18 lines · Paolo Bonzini
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

Quoted 7 lines

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Paolo

Let me know if you are still planning to modify the current patch by removing "noinline" and merge or if you prefer a v2 without noinline.

Thanks
Vipin

#7 lore raw
Quoted 25 lines · Vipin Sharma
Quoted 23 lines · Paolo Bonzini
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Quoted 5 lines
Quoted 2 lines

Paolo

Let me know if you are still planning to modify the current patch by removing "noinline" and merge or if you prefer a v2 without noinline.

Hi Paolo,

Any update on this patch?

Thanks
Vipin

#8 lore raw
Quoted 30 lines · Vipin Sharma
Quoted 28 lines · Vipin Sharma
Quoted 25 lines · Paolo Bonzini
Quoted 9 lines · Vipin Sharma
Quoted 4 lines

arch/x86/kvm/mmu/mmu.c static bool slot_rmap_walk_okay(struct slot_rmap_walk_iterator *iterator) · line 1502

Quoted 2 lines
arch/x86/kvm/mmu/mmu.c +1 -1
-static void slot_rmap_walk_next(struct slot_rmap_walk_iterator *iterator)
+static noinline void

What is the reason to add noinline?

My understanding is that since this method is called from __always_inline methods, noinline will avoid gcc inlining the slot_rmap_walk_next in those functions and generate smaller code.

Iterators are written in such a way that it's way more beneficial to inline them. After inlining, compilers replace the aggregates (in this case, struct slot_rmap_walk_iterator) with one variable per field and that in turn enables a lot of optimizations, so the iterators should actually be always_inline if anything.

For the same reason I'd guess the effect on the generated code should be small (next time please include the output of "size mmu.o"), but should still be there. I'll do a quick check of the generated code and apply the patch.

Paolo

Quoted 7 lines
Quoted 2 lines

Let me know if you are still planning to modify the current patch by removing "noinline" and merge or if you prefer a v2 without noinline.

Hi Paolo,

Any update on this patch?

Hi Paolo,

Still waiting for your response on this patch :)
Please let me know if you prefer v2 (without noinline) or you will merge this patch without noinline from your side. If there is any concern or feedback which I can address please let me know.

Thanks
Vipin Sharma