Page MenuHomeFreeBSD

Eliminate some needless attempts to merge buddies
ClosedPublic

Authored by dougm on Aug 25 2018, 5:50 PM.

Details

Summary

In vm_phys_free_contig, many calls are made to vm_phys_free_pages, which attempts to merge free blocks with buddies to form larger free blocks. We can replace most of those calls with direct calls to vm_freelist_add that do not attempt merging, and call vm_phys_free_pages at most twice to get all the merging that is possible.

Test Plan

The testing for D20256 included a table showing the number of cycles consumed in breaking a reservation with first and last pages, only, allocated, with and without that change in place. The first column was the original code, and the second showed the effects of that change. I'm adding a third column that shows the affect of this change.

Pages 0 and 511 allocated, the rest free:
cycles/break: 4233: 4226: 3629
cycles/break: 4236: 4251: 3777
cycles/break: 4218: 4204: 3781
cycles/break: 4248: 4219: 3775
cycles/break: 4241: 4233: 3813
cycles/break: 4195: 4232: 3785
cycles/break: 4251: 4280: 3794
cycles/break: 4193: 4222: 3778
cycles/break: 4281: 4221: 3762
cycles/break: 4240: 4202: 3761

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

dougm created this revision.Aug 25 2018, 5:50 PM
kib added a comment.EditedSep 1 2018, 11:57 AM

Please provide the diff context.

I am curious how large impact this change has, do you observe situations where it really makes the difference ? In other words, how often is vm_phys_free_pages() called for the run of >= VM_NFREEORDER ? Is it for free of superpages ?

sys/vm/vm_phys.c
1098 ↗(On Diff #47291)

I think this comment is mis-placed. It seems that it should be near the call to vm_phys_nomerge_free_contig().

1112 ↗(On Diff #47291)

Continuation line should use +4 spaces for intent.

I would put this min() calculation into a helper function and moved the long comment above to it.

markj added inline comments.Sep 1 2018, 4:21 PM
sys/vm/vm_phys.c
1095 ↗(On Diff #47291)

m_start would seem to be a more common name for the first page in a contiguous range.

dougm updated this revision to Diff 47570.Sep 1 2018, 9:16 PM

Apply reviewer-recommended changes.

kib accepted this revision.Sep 1 2018, 10:02 PM
kib added inline comments.
sys/vm/vm_phys.c
1049 ↗(On Diff #47570)

return (min(....));

This revision is now accepted and ready to land.Sep 1 2018, 10:02 PM
dougm updated this revision to Diff 47571.Sep 1 2018, 11:41 PM

Add parens, as requested.

This revision now requires review to proceed.Sep 1 2018, 11:41 PM
alc added inline comments.Sep 8 2018, 6:26 PM
sys/vm/vm_phys.c
1077 ↗(On Diff #47571)

There is an undocumented assumption here and in the original vm_phys_free_contig() code: That the contiguous pages don't cross a vm_phys_segs[] boundary. Right now, this function is only called in two places: vm_page_startup() and vm_reserv_break(). In both cases, we know that the contiguous pages won't cross a vm_phys_segs[] boundary. Moreover, we know that coalescing won't occur. In other words, the two calls to vm_phys_free() on the boundaries aren't needed to handle the possibility of coalescing.

When I first talked to Doug about implementing this optimization, I was reluctant to provide a public function that requires the caller to know that coalescing can't occur. However, we already require the caller to know that the contiguous pages won't cross a vm_phys_segs[] boundary, so there is already one unusual requirement on the caller. Given that, should we just explicitly document the requirements, expose this non-coalescing version to callers, and use it in vm_page_startup() and vm_reserv_break()?

kib added inline comments.Sep 12 2018, 2:17 PM
sys/vm/vm_phys.c
1077 ↗(On Diff #47571)

I think it is not hard to assert that m->segind is not changing.

dougm updated this revision to Diff 55045.Mar 14 2019, 2:09 AM

This patch was ready to land, briefly, 6.5 months ago. This is just a refresh to account for unrelated changes to the modified file in the last 6.5 months.

dougm updated this revision to Diff 57350.May 13 2019, 5:06 AM

Refresh this patch. Avoid potentially unneeded evaluations of flsl by recognizing when the max free block size is reached. Rewrite to update one variable per loop iteration instead of two.

kib added a comment.May 13 2019, 8:49 AM

Refresh this patch. Avoid potentially unneeded evaluations of flsl by recognizing when the max free block size is reached. Rewrite to update one variable per loop iteration instead of two.

Doug, please note the Alan comment and my followup.

dougm added a comment.May 13 2019, 2:39 PM

I have noted Alan's comment and your followup. I speculate that, having noted them, you would have me

  1. explicitly document the requirements, expose this non-coalescing version to callers, and use it in vm_page_startup() and vm_reserv_break()

and

  1. assert that m->segind is not changing, somewhere in the code.

If you are not directing me to take these steps, please clarify.

kib added a comment.May 13 2019, 3:10 PM

I have noted Alan's comment and your followup. I speculate that, having noted them, you would have me

  1. explicitly document the requirements, expose this non-coalescing version to callers, and use it in vm_page_startup() and vm_reserv_break()

and

  1. assert that m->segind is not changing, somewhere in the code.

If you are not directing me to take these steps, please clarify.

#1 is reasonable, of course. And #2 was specifically asked for in my follow-up.

dougm added a comment.May 15 2019, 3:49 AM

If I use the non-coalescing version in the two places mentioned above, then we'll be left using the coalescing version exactly never, or so it seems. So ought we instead abandon all this cleverness and just make vm_phys_free_contig non-coalescing, and simpler?

dougm added inline comments.May 16 2019, 9:45 PM
sys/vm/vm_phys.c
1077 ↗(On Diff #47571)

In the cases of vm_page_startup() and vm_reserv_break(), some of us know that coalescing won't occur, but I am not one of them. So I'll leave this patch in perpetual limbo until I believe this thing that we all know.

dougm updated this revision to Diff 57977.May 28 2019, 1:37 AM

Rename the function that frees page ranges without merging across boundaries, since calling is "nomerge" suggests it doesn't merge adjacent freed pages in the range. Make that function public and use it in places where vm_phys_free_contig is used now. Add assertions to verify that the segment isn't changing as consecutive blocks of pages are freed.

kib accepted this revision.May 28 2019, 10:46 AM
This revision is now accepted and ready to land.May 28 2019, 10:46 AM
dougm edited the test plan for this revision. (Show Details)May 28 2019, 5:14 PM
alc added inline comments.May 30 2019, 4:46 AM
vm_phys.c
1098 ↗(On Diff #57977)

"... of a set of pages starting ..."

1102 ↗(On Diff #57977)

For the time being, style(9) still requires a blank line here. (There is a proposal to eliminate that rule that might apply here.)

1119 ↗(On Diff #57977)

"... must be superpage boundary, ...". No. I think that you are trying to explain why vm_reserv_break() can call this function. Reservations are provided by the buddy allocator, and thus they are aligned on an address that is a multiple of their size. When we are breaking a reservation, there is at least one allocated page within the reservation. The pages being freed by vm_reserv_break() can't possibly coalesce with a page from outside the reservation until those pages are freed.

1125 ↗(On Diff #57977)

I suggest vm_phys_enqueue_contig().

1145 ↗(On Diff #57977)

The page range that spans two segments is [original "m", current "m"), not [current "m", "m_end").

1147 ↗(On Diff #57977)

Unnecessary parentheses.

1155 ↗(On Diff #57977)

Unnecessary parentheses.

1164 ↗(On Diff #57977)

Unnecessary parentheses.

dougm updated this revision to Diff 58067.May 30 2019, 5:20 AM
dougm marked 8 inline comments as done.

Accept reviewer recommendations. Rebuild kernel and reinstall with no immediate problems.

This revision now requires review to proceed.May 30 2019, 5:20 AM
dougm added inline comments.May 30 2019, 5:20 AM
vm_phys.c
1119 ↗(On Diff #57977)

Paragraph deleted.

1145 ↗(On Diff #57977)

original "m" == m_end - npages.

alc added inline comments.May 31 2019, 4:26 AM
vm_phys.c
1142 ↗(On Diff #58067)

Deindent this line by one space.

1150 ↗(On Diff #58067)

Deindent this line by one space.

1158 ↗(On Diff #58067)

Deindent this line by one space.

vm_phys.h
91 ↗(On Diff #58067)

This declaration should move up to maintain sorted order.

dougm updated this revision to Diff 58103.May 31 2019, 4:33 AM
dougm marked 4 inline comments as done.

Apply all reviewer recommendations.

alc accepted this revision.May 31 2019, 4:48 AM
This revision is now accepted and ready to land.May 31 2019, 4:48 AM
alc added a comment.May 31 2019, 6:52 PM

Kostik, Mark,

While Kostik recently approved this change, I think that Doug is waiting for one of you to explicitly approve the latest version.

Doug,

When you write the commit message, you should include a sentence in that message quantifying the improvement.

kib accepted this revision.May 31 2019, 6:54 PM
markj accepted this revision.May 31 2019, 7:00 PM
This revision was automatically updated to reflect the committed changes.