Use macros to search vm_map

[dougm]

Summary

Replace a few utility functions for vm_map manipulation with macros, and add a boolean status argument to give the compiler a chance to generate better code.

Test Plan

On 2 tests that exercise the vm_map vigoriously, these are the runtimes and dc-misses with and without the change in place:

After:
Test 1 Test 2
seconds dc-misses seconds dc-misses
17.518129 719615104 16.613336 694618946
17.544017 717358163 16.560833 695521981
17.498316 722645549 16.519886 693421798
17.481360 723478804 16.559717 689488954
17.505018 720791939 16.494966 689094378

Before:
Test 1 Test 2
seconds dc-misses seconds dc-misses
18.448940 697424367 17.487485 680852142
18.520613 700154192 17.488678 670644687
18.369913 696744015 17.553468 668572905
18.412856 704237817 17.457770 664390472
18.513684 700244077 17.480940 664748569

[dougm]

Restore gap_end variable to fix findspace problem.

[pho]

I ran tests on D22544.64854 for 14 hours. No problems seen.

[markj]

Do you get similar results by using C functions with the __always_inline attribute instead of macros?

[dougm]

Replace the macros with __always_inline functions, which preserves, and perhaps slightly enhances the performance benefit.

[markj]

sys/vm/vm_map.c

1096 ↗

(On Diff #64894)

Isn't *found true iff root != NULL? Why do we need found at all?

[dougm]

Stop trying to insert 'found' into the splay search code.

[dougm]

sys/vm/vm_map.c

1102 ↗

(On Diff #64952)

I hear you ask - why not just keep this a simple while loop? Well, because it can't a simple while loop in the threaded tree, and I seek to make the final patch that switches from not-threaded to threaded to be one that can be easily understood, if I ever get there.

1096 ↗

(On Diff #64894)

I thought I was saving a root != NULL test and letting the break cases in LEFT_STEP/RIGHT_STEP go directly to handling the root!=NULL cases without testing. But I guess I was wrong. After stripping out 'found', I get:

17.482829 719261050 16.607015 704332901
17.536821 744567159 16.530198 691722248
17.491278 745792388 16.500271 692419053
17.513297 731784319 16.567252 709416066
17.473170 721502357 16.543261 709815515

which looks about the same. So I'll take it out.

[dougm]

Go ahead and make findnext and findprev look less weird.

[alc]

Can you explain why this change reduces the number of L1 data cache misses?

[dougm]

In D22544#493747, @alc wrote:

Can you explain why this change reduces the number of L1 data cache misses?

I haven't observed that. I didn't expect to impact L1 data cache misses.

[alc]

In D22544#493871, @dougm wrote:

In D22544#493747, @alc wrote:

Can you explain why this change reduces the number of L1 data cache misses?

I haven't observed that. I didn't expect to impact L1 data cache misses.

I misread the results.