Details

Reviewers

alc
markj

Commits

rG90710f4a3473: pctrie: add parent pointer to nodes

Summary

Add a parent pointer field to the pctrie_node struct, and maintain
it as part of inserting and removing pctrie items.

Much code is written to maintain one, or an array, of trailing
pointers; that maintenance can be dropped with parent pointers
available. Code affected includes remove, reclaim, lookup_le, and
lookup_ge. In places, functions written once for iterator-free
searching and again for iterator-maintaining searching can be replaced
with a single function that serves both purposes.

Diff Detail

Repository

rG FreeBSD src repository

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

dougm requested review of this revision.Jan 21 2025, 8:20 PM

dougm created this revision.

Drop PCTRIE_LIMIT; no longer used.

With this patch {F108995447} from @alc, additional stats are maintained about several functions the process pages. A test script from @alc repeatedly dumps these stats and makes buildworld. A summary of the stats produced from 14 buildworld cycles, with and without this change in place, is here:

                original                                with parent pointer
                calls           cycles/call             calls           cycles/call
build 1:
alloc_gpgs:     752816          3537.0446111666065      753403          3550.5407796358654
alloc_grab:     1431            436.8637316561845       1316            403.73936170212767
alloc_cd:       0                                       0
alloc:          374720268       1689.3377221618555      374752064       1657.7241438248623
opr:            1827808         41479.21354212258       1832337         40623.801139746676
collapse_scan:  63273           14629.339670949694      63263           14315.523591988998
osplit:         20480           3492.38447265625        20480           3440.943994140625
kmem_unback:    146             4874.1164383561645      260             4242.334615384615
kmem_back:      852             4399.960093896713       382             6580.9633507853405
alloc_stack:    318             16151.314465408805      284             15706.760563380281
build 2:
alloc_gpgs:     688519          3660.478534361434       688354          3678.9042367735206
alloc_grab:     267             810.2584269662922       352             674.3039772727273
alloc_cd:       0                                       0
alloc:          374704385       1691.3100248666692      374696048       1656.4751262815562
opr:            2046128         37211.38124692102       2047172         36545.44908879176
collapse_scan:  63439           14639.360078185344      63395           14275.927202460762
osplit:         20489           3561.668505051491       20484           3454.7404315563367
kmem_unback:    258             4278.662790697675       260             4290.292307692308
kmem_back:      256             4627.74609375           253             3952.2727272727275
alloc_stack:    0                                       18              18812.38888888889
build 3:
alloc_gpgs:     688218          3864.6552633031974      688204          3711.1900962505306
alloc_grab:     277             827.7581227436823       768             540.4986979166666
alloc_cd:       0                                       0
alloc:          374696359       1698.0116050473819      374702644       1659.0674712426103
opr:            2049112         37273.90167545747       2049020         36351.40199412402
collapse_scan:  63401           14524.794372328512      63264           14167.709629489125
osplit:         20481           3600.175333235682       20482           3432.226003319988
kmem_unback:    262             4392.267175572519       270             4364.766666666666
kmem_back:      288             4181.770833333333       309             3911.1035598705503
alloc_stack:    0                                       124             17914.266129032258
build 4:
alloc_gpgs:     687744          3800.126020728643       687712          3740.0869739076825
alloc_grab:     340             839.7911764705882       341             714.5014662756598
alloc_cd:       0                                       0
alloc:          374688863       1690.3822367973612      374699587       1653.7818580008202
opr:            2049554         37334.099850991974      2044332         36499.80497981737
collapse_scan:  63446           14867.006588279797      63339           14249.482830483588
osplit:         20481           3580.4441677652458      20483           3470.292193526339
kmem_unback:    260             4385.780769230769       260             4460.35
kmem_back:      278             4067.338129496403       246             4143.69918699187
alloc_stack:    0                                       0
build 5:
alloc_gpgs:     688152          3826.353221381323       687972          3779.962244102958
alloc_grab:     343             766.536443148688        406             672.9261083743843
alloc_cd:       0                                       0
alloc:          374690693       1703.3869736737763      374687147       1663.2264810754236
opr:            2051811         37256.08000395748       2050805         36251.66573906344
collapse_scan:  63268           14563.049819814125      63415           14279.111298588661
osplit:         20482           3544.8337564690946      20480           3477.351416015625
kmem_unback:    260             4459.638461538461       262             4477.282442748092
kmem_back:      263             4172.558935361217       287             3628.836236933798
alloc_stack:    0                                       18              20592.555555555555
build 6:
alloc_gpgs:     688004          3806.131516677229       687829          3918.2115060574647
alloc_grab:     330             882.2818181818182       322             703.0
alloc_cd:       0                                       0
alloc:          374712787       1695.407248701657       374726036       1666.4276835970907
opr:            2043810         37657.212912648436      2046742         36399.67708094132
collapse_scan:  63428           14539.063315885729      63371           14223.845465591517
osplit:         20481           3583.1160587861923      20484           3465.7334993165396
kmem_unback:    264             4467.329545454545       254             4414.653543307087
kmem_back:      267             2751.9962546816478      250             3754.316
alloc_stack:    0                                       0
build 7:
alloc_gpgs:     688950          4346.102490746789       687993          3833.713767436587
alloc_grab:     312             870.3301282051282       346             778.4971098265896
alloc_cd:       0                                       0
alloc:          374714264       1695.583141129103       374705160       1664.6016300309288
opr:            2043947         37450.46345135172       2046073         36433.35758792575
collapse_scan:  63391           14638.797763089398      63295           19596.62399873608
osplit:         20483           3616.549040667871       20480           3445.99716796875
kmem_unback:    270             4354.625925925926       262             4263.896946564885
kmem_back:      247             3854.8906882591095      288             4907.767361111111
alloc_stack:    0                                       0
build 8:
alloc_gpgs:     687590          3899.077585479719       687673          3859.243179534459
alloc_grab:     306             741.9346405228758       321             601.797507788162
alloc_cd:       0                                       0
alloc:          374690935       1685.1745528297877      374709180       1657.466125983356
opr:            2048853         37658.63132494132       2049303         36286.93291084823
collapse_scan:  63298           14569.034377073525      63338           14291.951877230098
osplit:         20483           3609.119416101157       20481           3424.3219081099555
kmem_unback:    262             4381.393129770992       260             4564.803846153846
kmem_back:      279             4225.426523297491       285             3910.964912280702
alloc_stack:    0                                       2               19425.0
build 9:
alloc_gpgs:     687997          3908.017542227655       687633          3880.068140999632
alloc_grab:     317             1241.6593059936909      346             632.4219653179191
alloc_cd:       0                                       0
alloc:          374678319       1689.0151406305417      374698354       1681.2159670309093
opr:            2047895         38083.22553207073       2044767         36356.434475419446
collapse_scan:  63310           14597.273779813615      63281           15126.219307533067
osplit:         20480           3590.35498046875        20482           3479.7703349282297
kmem_unback:    264             4430.469696969697       266             4434.992481203008
kmem_back:      261             4163.137931034483       260             3363.726923076923
alloc_stack:    0                                       2               24420.0
build 10:
alloc_gpgs:     687434          3929.363034124003       687568          3894.889996334908
alloc_grab:     329             784.5349544072948       312             700.7467948717949
alloc_cd:       0                                       0
alloc:          374680054       1697.0311052293166      374696123       1661.2210052490989
opr:            2045096         37432.122590333165      2048368         36551.21103092804
collapse_scan:  63295           14679.136645864603      63318           14366.743895890584
osplit:         20482           3592.103505517039       20481           3505.3367511351985
kmem_unback:    258             4378.333333333333       264             4559.689393939394
kmem_back:      261             4789.302681992337       266             4272.943609022556
alloc_stack:    0                                       0
build 11:
alloc_gpgs:     687837          3920.861872798352       687689          3926.053386050962
alloc_grab:     300             820.5366666666666       337             678.406528189911
alloc_cd:       0                                       0
alloc:          374682131       1693.1277865103207      374688080       1669.466059849035
opr:            2048878         37630.40325095003       2049557         36783.37298596721
collapse_scan:  63255           14638.254051063157      63302           14273.011563615684
osplit:         20482           3599.603944927253       20483           3448.433237318752
kmem_unback:    264             4401.598484848485       266             4556.703007518797
kmem_back:      266             3820.4586466165415      254             4037.515748031496
alloc_stack:    0                                       0
build 12:
alloc_gpgs:     687513          3954.9579004324282      687765          3977.521061699854
alloc_grab:     289             838.8373702422145       314             808.5796178343949
alloc_cd:       0                                       0
alloc:          374691515       1697.3248805407295      374694613       1660.9739711309915
opr:            2047851         37805.350147544916      2049391         36886.766914659034
collapse_scan:  63339           14706.091886515416      63332           14323.06151708457
osplit:         20485           3605.199804735172       20483           3459.903725040277
kmem_unback:    262             4588.141221374046       266             4628.06015037594
kmem_back:      259             3607.714285714286       231             3645.220779220779
alloc_stack:    0                                       0
build 13:
alloc_gpgs:     688376          3994.52645211338        687590          4470.740742302826
alloc_grab:     299             766.2341137123746       291             712.5360824742268
alloc_cd:       0                                       0
alloc:          374703810       1708.089823967896       374692668       1657.4581236614963
opr:            2045088         37540.87445821402       2042139         36728.149381604286
collapse_scan:  63396           14639.12155341031       63391           14262.63352841886
osplit:         20481           3603.1669840339828      20483           3463.4424156617683
kmem_unback:    270             4359.696296296296       254             3574.287401574803
kmem_back:      258             4497.077519379845       299             3702.846153846154
alloc_stack:    0                                       0
build 14:
alloc_gpgs:     687466          4179.131663238619       687588          4202.214941214797
alloc_grab:     308             835.8636363636364       290             645.8413793103448
alloc_cd:       0                                       0
alloc:          374695618       1686.2297781689028      374691403       1674.591030539337
opr:            2048923         37684.13060129639       2049880         36648.71118504498
collapse_scan:  63395           14641.129079580409      63347           14207.587636352155
osplit:         20486           3609.4090598457483      20484           3458.3530072251515
kmem_unback:    282             3742.3794326241136      286             3579.426573426573
kmem_back:      296             4105.25                 283             4075.2296819787985
alloc_stack:    0                                       0

The same information as posted before, reordered. For most of the counters, the change to use parent pointers reduces the cycles/call in most of the builds.

                original                                with parent pointer
                calls           cycles/call             calls           cycles/call
alloc_gpgs:     752816          3537.0446111666065      753403          3550.5407796358654
alloc_gpgs:     688519          3660.478534361434       688354          3678.9042367735206
alloc_gpgs:     688218          3864.6552633031974      688204          3711.1900962505306
alloc_gpgs:     687744          3800.126020728643       687712          3740.0869739076825
alloc_gpgs:     688152          3826.353221381323       687972          3779.962244102958
alloc_gpgs:     688004          3806.131516677229       687829          3918.2115060574647
alloc_gpgs:     688950          4346.102490746789       687993          3833.713767436587
alloc_gpgs:     687590          3899.077585479719       687673          3859.243179534459
alloc_gpgs:     687997          3908.017542227655       687633          3880.068140999632
alloc_gpgs:     687434          3929.363034124003       687568          3894.889996334908
alloc_gpgs:     687837          3920.861872798352       687689          3926.053386050962
alloc_gpgs:     687513          3954.9579004324282      687765          3977.521061699854
alloc_gpgs:     688376          3994.52645211338        687590          4470.740742302826
alloc_gpgs:     687466          4179.131663238619       687588          4202.214941214797
alloc_grab:     1431            436.8637316561845       1316            403.73936170212767
alloc_grab:     267             810.2584269662922       352             674.3039772727273
alloc_grab:     277             827.7581227436823       768             540.4986979166666
alloc_grab:     340             839.7911764705882       341             714.5014662756598
alloc_grab:     343             766.536443148688        406             672.9261083743843
alloc_grab:     330             882.2818181818182       322             703.0
alloc_grab:     312             870.3301282051282       346             778.4971098265896
alloc_grab:     306             741.9346405228758       321             601.797507788162
alloc_grab:     317             1241.6593059936909      346             632.4219653179191
alloc_grab:     329             784.5349544072948       312             700.7467948717949
alloc_grab:     300             820.5366666666666       337             678.406528189911
alloc_grab:     289             838.8373702422145       314             808.5796178343949
alloc_grab:     299             766.2341137123746       291             712.5360824742268
alloc_grab:     308             835.8636363636364       290             645.8413793103448
alloc:          374720268       1689.3377221618555      374752064       1657.7241438248623
alloc:          374704385       1691.3100248666692      374696048       1656.4751262815562
alloc:          374696359       1698.0116050473819      374702644       1659.0674712426103
alloc:          374688863       1690.3822367973612      374699587       1653.7818580008202
alloc:          374690693       1703.3869736737763      374687147       1663.2264810754236
alloc:          374712787       1695.407248701657       374726036       1666.4276835970907
alloc:          374714264       1695.583141129103       374705160       1664.6016300309288
alloc:          374690935       1685.1745528297877      374709180       1657.466125983356
alloc:          374678319       1689.0151406305417      374698354       1681.2159670309093
alloc:          374680054       1697.0311052293166      374696123       1661.2210052490989
alloc:          374682131       1693.1277865103207      374688080       1669.466059849035
alloc:          374691515       1697.3248805407295      374694613       1660.9739711309915
alloc:          374703810       1708.089823967896       374692668       1657.4581236614963
alloc:          374695618       1686.2297781689028      374691403       1674.591030539337
opr:            1827808         41479.21354212258       1832337         40623.801139746676
opr:            2046128         37211.38124692102       2047172         36545.44908879176
opr:            2049112         37273.90167545747       2049020         36351.40199412402
opr:            2049554         37334.099850991974      2044332         36499.80497981737
opr:            2051811         37256.08000395748       2050805         36251.66573906344
opr:            2043810         37657.212912648436      2046742         36399.67708094132
opr:            2043947         37450.46345135172       2046073         36433.35758792575
opr:            2048853         37658.63132494132       2049303         36286.93291084823
opr:            2047895         38083.22553207073       2044767         36356.434475419446
opr:            2045096         37432.122590333165      2048368         36551.21103092804
opr:            2048878         37630.40325095003       2049557         36783.37298596721
opr:            2047851         37805.350147544916      2049391         36886.766914659034
opr:            2045088         37540.87445821402       2042139         36728.149381604286
opr:            2048923         37684.13060129639       2049880         36648.71118504498
collapse_scan:  63273           14629.339670949694      63263           14315.523591988998
collapse_scan:  63439           14639.360078185344      63395           14275.927202460762
collapse_scan:  63401           14524.794372328512      63264           14167.709629489125
collapse_scan:  63446           14867.006588279797      63339           14249.482830483588
collapse_scan:  63268           14563.049819814125      63415           14279.111298588661
collapse_scan:  63428           14539.063315885729      63371           14223.845465591517
collapse_scan:  63391           14638.797763089398      63295           19596.62399873608
collapse_scan:  63298           14569.034377073525      63338           14291.951877230098
collapse_scan:  63310           14597.273779813615      63281           15126.219307533067
collapse_scan:  63295           14679.136645864603      63318           14366.743895890584
collapse_scan:  63255           14638.254051063157      63302           14273.011563615684
collapse_scan:  63339           14706.091886515416      63332           14323.06151708457
collapse_scan:  63396           14639.12155341031       63391           14262.63352841886
collapse_scan:  63395           14641.129079580409      63347           14207.587636352155
osplit:         20480           3492.38447265625        20480           3440.943994140625
osplit:         20489           3561.668505051491       20484           3454.7404315563367
osplit:         20481           3600.175333235682       20482           3432.226003319988
osplit:         20481           3580.4441677652458      20483           3470.292193526339
osplit:         20482           3544.8337564690946      20480           3477.351416015625
osplit:         20481           3583.1160587861923      20484           3465.7334993165396
osplit:         20483           3616.549040667871       20480           3445.99716796875
osplit:         20483           3609.119416101157       20481           3424.3219081099555
osplit:         20480           3590.35498046875        20482           3479.7703349282297
osplit:         20482           3592.103505517039       20481           3505.3367511351985
osplit:         20482           3599.603944927253       20483           3448.433237318752
osplit:         20485           3605.199804735172       20483           3459.903725040277
osplit:         20481           3603.1669840339828      20483           3463.4424156617683
osplit:         20486           3609.4090598457483      20484           3458.3530072251515
kmem_unback:    146             4874.1164383561645      260             4242.334615384615
kmem_unback:    258             4278.662790697675       260             4290.292307692308
kmem_unback:    262             4392.267175572519       270             4364.766666666666
kmem_unback:    260             4385.780769230769       260             4460.35
kmem_unback:    260             4459.638461538461       262             4477.282442748092
kmem_unback:    264             4467.329545454545       254             4414.653543307087
kmem_unback:    270             4354.625925925926       262             4263.896946564885
kmem_unback:    262             4381.393129770992       260             4564.803846153846
kmem_unback:    264             4430.469696969697       266             4434.992481203008
kmem_unback:    258             4378.333333333333       264             4559.689393939394
kmem_unback:    264             4401.598484848485       266             4556.703007518797
kmem_unback:    262             4588.141221374046       266             4628.06015037594
kmem_unback:    270             4359.696296296296       254             3574.287401574803
kmem_unback:    282             3742.3794326241136      286             3579.426573426573
kmem_back:      852             4399.960093896713       382             6580.9633507853405
kmem_back:      256             4627.74609375           253             3952.2727272727275
kmem_back:      288             4181.770833333333       309             3911.1035598705503
kmem_back:      278             4067.338129496403       246             4143.69918699187
kmem_back:      263             4172.558935361217       287             3628.836236933798
kmem_back:      267             2751.9962546816478      250             3754.316
kmem_back:      247             3854.8906882591095      288             4907.767361111111
kmem_back:      279             4225.426523297491       285             3910.964912280702
kmem_back:      261             4163.137931034483       260             3363.726923076923
kmem_back:      261             4789.302681992337       266             4272.943609022556
kmem_back:      266             3820.4586466165415      254             4037.515748031496
kmem_back:      259             3607.714285714286       231             3645.220779220779
kmem_back:      258             4497.077519379845       299             3702.846153846154
kmem_back:      296             4105.25                 283             4075.2296819787985
alloc_stack:    318             16151.314465408805      284             15706.760563380281
alloc_stack:    0                                       18              18812.38888888889
alloc_stack:    0                                       124             17914.266129032258
alloc_stack:    0                                       0
alloc_stack:    0                                       18              20592.555555555555
alloc_stack:    0                                       0
alloc_stack:    0                                       0
alloc_stack:    0                                       2               19425.0
alloc_stack:    0                                       2               24420.0
alloc_stack:    0                                       0
alloc_stack:    0                                       0
alloc_stack:    0                                       0
alloc_stack:    0                                       0
alloc_stack:    0                                       0

How do these changes affect the various counts? Some of these counts change because iterators are used, and some change because lookup_le now uses parent pointers.

alloc_gpgs (vm_page_grab_pages): A call to vm_radix_lookup_le is changed because that function now uses parent pointers.
alloc_grab (vm_page_grab): A call to vm_radix_lookup_le is changed because that function now uses parent pointers.
alloc (vm_page_alloc): A call to vm_radix_lookup_le is changed because that function now uses parent pointers.
opr (vm_object_page_remove): Uses lookup_ge/step iteration and iter_remove()
collapse_scan (vm_object_collapse_scan): Uses lookup_ge/step iteration and iter_remove()
osplit (vm_object_split): Uses lookup_ge/step iteration and iter_remove()
kmem_unback: Uses iter_lookup and iter_remove()
kmem_back(kmem_back_domain): A call to vm_radix_lookup_le is changed because that function now uses parent pointers.
alloc_stack (vm_thread_stack_create): A call to vm_radix_lookup_le is changed because that function now uses parent pointers.

In D48588#1111597, @dougm wrote:

With this patch {F108995447} from @alc

I don't seem to have permission to view the patch - could you please update its access restrictions?

sys/kern/subr_pctrie.c
363–365	Could you please update the comment to describe the parameters?
828–836	A comment here explaining the relationship between `node` and `child` would be helpful.

Add comments.

diff --git a/sys/vm/vm_glue.c b/sys/vm/vm_glue.c
index 0090904785ab..694dc01344ea 100644
--- a/sys/vm/vm_glue.c
+++ b/sys/vm/vm_glue.c
@@ -440,7 +440,7 @@ vm_thread_kstack_arena_release(void *arena, vmem_addr_t addr, vmem_size_t size)
  * Create the kernel stack for a new thread.
  */
 static vm_offset_t
-vm_thread_stack_create(struct domainset *ds, int pages)
+_vm_thread_stack_create(struct domainset *ds, int pages)
 {
 	vm_page_t ma[KSTACK_MAX_PAGES];
 	struct vm_domainset_iter di;
@@ -484,6 +484,28 @@ vm_thread_stack_create(struct domainset *ds, int pages)
 	return (0);
 }
 
+SYSCTL_DECL(_debug_counters);
+
+static COUNTER_U64_DEFINE_EARLY(alloc_stack_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_stack_calls, CTLFLAG_RD, &alloc_stack_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_stack_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_stack_cycles, CTLFLAG_RD, &alloc_stack_cycles,
+    "");
+
+static vm_offset_t
+vm_thread_stack_create(struct domainset *ds, int npages)
+{
+	vm_offset_t res;
+	uint64_t tsc = rdtsc();
+
+	res = _vm_thread_stack_create(ds, npages);
+	counter_u64_add(alloc_stack_cycles, rdtsc() - tsc);
+	counter_u64_add(alloc_stack_calls, 1);
+	return (res);
+}
+
 static __noinline void
 vm_thread_stack_dispose(vm_offset_t ks, int pages)
 {
diff --git a/sys/vm/vm_kern.c b/sys/vm/vm_kern.c
index a748a6c57d65..f6203c160799 100644
--- a/sys/vm/vm_kern.c
+++ b/sys/vm/vm_kern.c
@@ -526,8 +526,8 @@ kmem_malloc_domainset(struct domainset *ds, vm_size_t size, int flags)
  *	Allocate physical pages from the specified domain for the specified
  *	virtual address range.
  */
-int
-kmem_back_domain(int domain, vm_object_t object, vm_offset_t addr,
+static int
+_kmem_back_domain(int domain, vm_object_t object, vm_offset_t addr,
     vm_size_t size, int flags)
 {
 	vm_offset_t offset, i;
@@ -583,6 +583,29 @@ kmem_back_domain(int domain, vm_object_t object, vm_offset_t addr,
 	return (KERN_SUCCESS);
 }
 
+SYSCTL_DECL(_debug_counters);
+
+static COUNTER_U64_DEFINE_EARLY(kmem_back_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, kmem_back_calls, CTLFLAG_RD, &kmem_back_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(kmem_back_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, kmem_back_cycles, CTLFLAG_RD, &kmem_back_cycles,
+    "");
+
+int
+kmem_back_domain(int domain, vm_object_t object, vm_offset_t addr,
+    vm_size_t size, int flags)
+{
+	int res;
+	uint64_t tsc = rdtsc();
+
+	res = _kmem_back_domain(domain, object, addr, size, flags);
+	counter_u64_add(kmem_back_cycles, rdtsc() - tsc);
+	counter_u64_add(kmem_back_calls, 1);
+	return (res);
+}
+
 /*
  *	kmem_back:
  *
@@ -622,6 +645,14 @@ kmem_back(vm_object_t object, vm_offset_t addr, vm_size_t size, int flags)
 	return (rv);
 }
 
+static COUNTER_U64_DEFINE_EARLY(kmem_unback_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, kmem_unback_calls, CTLFLAG_RD, &kmem_unback_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(kmem_unback_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, kmem_unback_cycles, CTLFLAG_RD, &kmem_unback_cycles,
+    "");
+
 /*
  *	kmem_unback:
  *
@@ -638,6 +669,7 @@ _kmem_unback(vm_object_t object, vm_offset_t addr, vm_size_t size)
 	struct vmem *arena;
 	vm_page_t m;
 	vm_offset_t end, offset;
+	uint64_t tsc;
 	int domain;
 
 	KASSERT(object == kernel_object,
@@ -646,6 +678,7 @@ _kmem_unback(vm_object_t object, vm_offset_t addr, vm_size_t size)
 	if (size == 0)
 		return (NULL);
 	pmap_remove(kernel_pmap, addr, addr + size);
+	tsc = rdtsc();
 	offset = addr - VM_MIN_KERNEL_ADDRESS;
 	end = offset + size;
 	VM_OBJECT_WLOCK(object);
@@ -663,6 +696,8 @@ _kmem_unback(vm_object_t object, vm_offset_t addr, vm_size_t size)
 		vm_page_iter_free(&pages, m);
 	}
 	VM_OBJECT_WUNLOCK(object);
+	counter_u64_add(kmem_unback_cycles, rdtsc() - tsc);
+	counter_u64_add(kmem_unback_calls, 1);
 
 	return (arena);
 }
diff --git a/sys/vm/vm_object.c b/sys/vm/vm_object.c
index a3cfb4d036be..eecd632abc7f 100644
--- a/sys/vm/vm_object.c
+++ b/sys/vm/vm_object.c
@@ -1510,6 +1510,16 @@ vm_object_shadow(vm_object_t *object, vm_ooffset_t *offset, vm_size_t length,
 	*object = result;
 }
 
+SYSCTL_DECL(_debug_counters);
+
+static COUNTER_U64_DEFINE_EARLY(osplit_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, osplit_calls, CTLFLAG_RD, &osplit_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(osplit_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, osplit_cycles, CTLFLAG_RD, &osplit_cycles,
+    "");
+
 /*
  *	vm_object_split:
  *
@@ -1525,6 +1535,7 @@ vm_object_split(vm_map_entry_t entry)
 	vm_object_t orig_object, new_object, backing_object;
 	vm_pindex_t offidxstart;
 	vm_size_t size;
+	uint64_t tsc;
 
 	orig_object = entry->object.vm_object;
 	KASSERT((orig_object->flags & OBJ_ONEMAPPING) != 0,
@@ -1540,6 +1551,7 @@ vm_object_split(vm_map_entry_t entry)
 
 	new_object = vm_object_allocate_anon(size, orig_object,
 	    orig_object->cred, ptoa(size));
+	tsc = rdtsc();
 
 	/*
 	 * We must wait for the orig_object to complete any in-progress
@@ -1645,6 +1657,8 @@ vm_object_split(vm_map_entry_t entry)
 	vm_object_clear_flag(orig_object, OBJ_SPLIT);
 	VM_OBJECT_WUNLOCK(orig_object);
 	VM_OBJECT_WUNLOCK(new_object);
+	counter_u64_add(osplit_cycles, rdtsc() - tsc);
+	counter_u64_add(osplit_calls, 1);
 	entry->object.vm_object = new_object;
 	entry->offset = 0LL;
 	vm_object_deallocate(orig_object);
@@ -1685,7 +1699,7 @@ vm_object_collapse_scan_wait(struct pctrie_iter *pages, vm_object_t object,
 }
 
 static void
-vm_object_collapse_scan(vm_object_t object)
+_vm_object_collapse_scan(vm_object_t object)
 {
 	struct pctrie_iter pages;
 	vm_object_t backing_object;
@@ -1817,6 +1831,24 @@ vm_object_collapse_scan(vm_object_t object)
 	return;
 }
 
+static COUNTER_U64_DEFINE_EARLY(collapse_scan_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, collapse_scan_calls, CTLFLAG_RD, &collapse_scan_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(collapse_scan_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, collapse_scan_cycles, CTLFLAG_RD, &collapse_scan_cycles,
+    "");
+
+static void
+vm_object_collapse_scan(vm_object_t object)
+{
+	uint64_t tsc = rdtsc();
+
+	_vm_object_collapse_scan(object);
+	counter_u64_add(collapse_scan_cycles, rdtsc() - tsc);
+	counter_u64_add(collapse_scan_calls, 1);
+}
+
 /*
  *	vm_object_collapse:
  *
@@ -1983,8 +2015,8 @@ vm_object_collapse(vm_object_t object)
  *
  *	The object must be locked.
  */
-void
-vm_object_page_remove(vm_object_t object, vm_pindex_t start, vm_pindex_t end,
+static void
+_vm_object_page_remove(vm_object_t object, vm_pindex_t start, vm_pindex_t end,
     int options)
 {
 	struct pctrie_iter pages;
@@ -2070,6 +2102,25 @@ vm_object_page_remove(vm_object_t object, vm_pindex_t start, vm_pindex_t end,
 	    start);
 }
 
+static COUNTER_U64_DEFINE_EARLY(opr_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, opr_calls, CTLFLAG_RD, &opr_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(opr_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, opr_cycles, CTLFLAG_RD, &opr_cycles,
+    "");
+
+void
+vm_object_page_remove(vm_object_t object, vm_pindex_t start, vm_pindex_t end,
+    int options)
+{
+	uint64_t tsc = rdtsc();
+
+	_vm_object_page_remove(object, start, end, options);
+	counter_u64_add(opr_cycles, rdtsc() - tsc);
+	counter_u64_add(opr_calls, 1);
+}
+
 /*
  *	vm_object_page_noreuse:
  *
diff --git a/sys/vm/vm_page.c b/sys/vm/vm_page.c
index f351295c1af5..3d8cafbb5634 100644
--- a/sys/vm/vm_page.c
+++ b/sys/vm/vm_page.c
@@ -2160,8 +2160,8 @@ vm_page_mpred(vm_object_t object, vm_pindex_t pindex)
  *	VM_ALLOC_WIRED		wire the allocated page
  *	VM_ALLOC_ZERO		prefer a zeroed page
  */
-vm_page_t
-vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int req)
+static vm_page_t
+_vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int req)
 {
 
 	return (vm_page_alloc_after(object, pindex, req,
@@ -2483,8 +2483,8 @@ vm_page_find_contig_domain(int domain, int req, u_long npages, vm_paddr_t low,
 	return (NULL);
 }
 
-vm_page_t
-vm_page_alloc_contig_domain(vm_object_t object, vm_pindex_t pindex, int domain,
+static vm_page_t
+_vm_page_alloc_contig_domain(vm_object_t object, vm_pindex_t pindex, int domain,
     int req, u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment,
     vm_paddr_t boundary, vm_memattr_t memattr)
 {
@@ -4863,8 +4863,8 @@ vm_page_grab_pflags(int allocflags)
  * The object must be locked on entry.  The lock will, however, be released
  * and reacquired if the routine sleeps.
  */
-vm_page_t
-vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
+static vm_page_t
+_vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
 {
 	vm_page_t m;
 
@@ -5159,8 +5159,8 @@ vm_page_grab_valid_unlocked(vm_page_t *mp, vm_object_t object,
  * If VM_ALLOC_NOWAIT is not specified, this routine may sleep.  Otherwise, it
  * may return a partial prefix of the requested range.
  */
-int
-vm_page_grab_pages(vm_object_t object, vm_pindex_t pindex, int allocflags,
+static int
+_vm_page_grab_pages(vm_object_t object, vm_pindex_t pindex, int allocflags,
     vm_page_t *ma, int count)
 {
 	vm_page_t m, mpred;
@@ -5953,3 +5953,88 @@ DB_SHOW_COMMAND(pginfo, vm_page_print_pginfo)
 	    m->flags, m->a.act_count, m->busy_lock, m->valid, m->dirty);
 }
 #endif /* DDB */
+
+SYSCTL_NODE(_debug, OID_AUTO, counters, CTLFLAG_RD, 0, "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_calls, CTLFLAG_RD, &alloc_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_cycles, CTLFLAG_RD, &alloc_cycles,
+    "");
+
+vm_page_t
+vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int req)
+{
+	vm_page_t res;
+	uint64_t tsc = rdtsc();
+
+	res = _vm_page_alloc(object, pindex, req);
+	counter_u64_add(alloc_cycles, rdtsc() - tsc);
+	counter_u64_add(alloc_calls, 1);
+	return (res);
+}
+
+static COUNTER_U64_DEFINE_EARLY(alloc_cd_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_cd_calls, CTLFLAG_RD, &alloc_cd_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_cd_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_cd_cycles, CTLFLAG_RD, &alloc_cd_cycles,
+    "");
+
+vm_page_t
+vm_page_alloc_contig_domain(vm_object_t object, vm_pindex_t pindex, int domain,
+    int req, u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment,
+    vm_paddr_t boundary, vm_memattr_t memattr)
+{
+	vm_page_t res;
+	uint64_t tsc = rdtsc();
+
+	res = _vm_page_alloc_contig_domain(object, pindex, domain, req,
+	    npages, low, high, alignment, boundary, memattr);
+	counter_u64_add(alloc_cd_cycles, rdtsc() - tsc);
+	counter_u64_add(alloc_cd_calls, 1);
+	return (res);
+}
+
+static COUNTER_U64_DEFINE_EARLY(alloc_grab_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_grab_calls, CTLFLAG_RD, &alloc_grab_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_grab_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_grab_cycles, CTLFLAG_RD, &alloc_grab_cycles,
+    "");
+
+vm_page_t
+vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
+{
+	vm_page_t res;
+	uint64_t tsc = rdtsc();
+
+	res = _vm_page_grab(object, pindex, allocflags);
+	counter_u64_add(alloc_grab_cycles, rdtsc() - tsc);
+	counter_u64_add(alloc_grab_calls, 1);
+	return (res);
+}
+
+static COUNTER_U64_DEFINE_EARLY(alloc_gpgs_calls);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_gpgs_calls, CTLFLAG_RD, &alloc_gpgs_calls,
+    "");
+
+static COUNTER_U64_DEFINE_EARLY(alloc_gpgs_cycles);
+SYSCTL_COUNTER_U64(_debug_counters, OID_AUTO, alloc_gpgs_cycles, CTLFLAG_RD, &alloc_gpgs_cycles,
+    "");
+int
+vm_page_grab_pages(vm_object_t object, vm_pindex_t pindex, int allocflags,
+    vm_page_t *ma, int count)
+{
+	int res;
+	uint64_t tsc = rdtsc();
+
+	res = _vm_page_grab_pages(object, pindex, allocflags, ma, count);
+	counter_u64_add(alloc_gpgs_cycles, rdtsc() - tsc);
+	counter_u64_add(alloc_gpgs_calls, 1);
+	return (res);
+}

Use smr to handle the parent pointers, as suggested by @alc.

I read through most of the updated routines and find the new version to be a fair bit easier to read.

sys/kern/subr_pctrie.c
231	Extra newline.
804–805	Is it possible to have `(PCTRIE_COUNT << node->pn_clev) > UINT_MAX` here? I believe the value would be truncated if so.

Remove an extra blank line.

sys/kern/subr_pctrie.c
804–805	It is possible to have (PCTRIE_COUNT << node->pn_clev) be 0 if the pn_clev field has its max value. Since we're at the root in that case, we also have node->pn_owner == 0, so this test is just limit >= (uint64_t)-1.

markj added inline comments.Sat, Feb 8, 5:45 PM

sys/kern/subr_pctrie.c
804–805	I believe the expression `(PCTRIE_COUNT << node->pn_clev)` will not be promoted to 64 bits without an explicit cast. That is, if `log2(PCTRIE_COUNT) + node->pn_clev` > 31, the expression will evaluate to something undefined. (And if it's equal to 31 I believe the result will be sign-extended to 64 bits.) I suspect it should be written `((uint64_t)PCTRIE_COUNT << node->pn_clev)`.

Fix overflow in lookup_le.

markj accepted this revision.Sat, Feb 8, 8:36 PM

This revision is now accepted and ready to land.Sat, Feb 8, 8:36 PM

@alc asks for another set of performance test results, after changes to this patch and updates to main. Here it is:

                original                            with parent pointer
		calls       cycles/call             calls       cycles/call
alloc_gpgs:     753196      3433.368095422705       752726      3355.3264042958526
alloc_gpgs:     688207      3647.469512806467       688686      3821.166207821852 
alloc_gpgs:     688156      3743.130015577863       688349      3704.981878378555 
alloc_gpgs:     688269      3742.25097890505        687746      3715.175548821803 
alloc_gpgs:     687793      3944.3802786594224      687774      3750.804620413101 
alloc_gpgs:     689014      3815.0942433680593      687759      3992.3021465367956
alloc_gpgs:     687751      3852.21258711365        687811      3883.8159974178952
alloc_gpgs:     687905      3905.4081028630408      687477      3809.4209217181083
alloc_gpgs:     687491      3911.0166416724         688083      3824.728785626153 
alloc_gpgs:     687770      3930.235629643631       687481      3867.568508802425 
alloc_grab:     1367        419.04462326261887      1387        398.0901225666907 
alloc_grab:     298         546.1845637583892       295         716.4203389830509 
alloc_grab:     272         560.1691176470588       277         725.4404332129964 
alloc_grab:     324         632.9969135802469       341         736.8533724340176 
alloc_grab:     307         666.7231270358307       299         732.0802675585285 
alloc_grab:     367         607.7275204359673       343         728.7813411078718 
alloc_grab:     348         590.830459770115        808         590.1225247524752 
alloc_grab:     795         541.503144654088        342         745.9502923976609 
alloc_grab:     383         559.2506527415144       360         657.2638888888889 
alloc_grab:     326         661.8006134969326       319         772.2445141065831 
alloc:          374734039   1661.5303740048018      374736815   1655.4853595449383
alloc:          374677943   1645.3604560063468      374695612   1651.6346534183592
alloc:          374705783   1659.9918138760083      374656957   1650.9526509366274
alloc:          374694374   1646.9430845657694      374656264   1650.9533881488767
alloc:          374700870   1646.0406999321885      374706132   1673.9708710184652
alloc:          374712803   1638.2854540307767      374711529   1659.677373986003 
alloc:          374706900   1651.8480891785018      374704472   1664.8114564909704
alloc:          374710893   1644.8391402541906      374678074   1664.2531539061983
alloc:          374707275   1644.8703988306606      374718851   1652.7642452501009
alloc:          374708731   1655.4604014924862      374696792   1656.589977893379 
obj_pg_remove:  1832868     41150.9315378958        1826792     40585.617983875556
obj_pg_remove:  2046374     37175.23626033169       2046423     36473.161220334216
obj_pg_remove:  2048610     37332.15326538482       2048828     36474.79306364419 
obj_pg_remove:  2045565     37065.52460567129       2046909     36397.75766533832 
obj_pg_remove:  2048287     37015.12094740629       2048676     36404.38612303751 
obj_pg_remove:  2048429     37235.76688525695       2046298     36903.619496769286
obj_pg_remove:  2046552     37022.67188275695       2047582     36483.30982641965 
obj_pg_remove:  2049316     37681.329802724424      2045991     36339.97596079357 
obj_pg_remove:  2051458     37392.170965722915      2046729     36595.63567819677 
obj_pg_remove:  2044974     37176.49530556379       2051471     36782.796787768384
collapse_scan:  63483       14723.250775798246      63261       14992.358356649436
collapse_scan:  63436       14485.691894192572      63287       14267.66583974592 
collapse_scan:  63357       14457.598891992991      63372       14146.01221359591 
collapse_scan:  63334       14548.960368838223      63303       14244.791921393931
collapse_scan:  63342       14522.038536831802      63387       14202.634483411424
collapse_scan:  63281       14463.376068646197      63374       14262.221983778836
collapse_scan:  63360       14527.694365530304      63362       14339.31957640226 
collapse_scan:  63295       15358.915996524212      63277       14227.311313747492
collapse_scan:  63386       14503.375414129303      63333       14307.337928094359
collapse_scan:  63253       14562.801764343194      63378       14283.823203635331
obj_split:      20482       3497.562200956938       20480       3527.800048828125 
obj_split:      20482       3463.8174494678256      20482       3502.8623669563517
obj_split:      20481       3550.8835506078804      20483       3534.2704193721625
obj_split:      20481       3462.6370782676627      20480       3517.3703125      
obj_split:      20483       3535.2422496704585      20482       3555.1071184454645
obj_split:      20481       3528.128216395684       20483       3552.3775325879997
obj_split:      20482       3567.2863001659994      20483       3554.7438851730703
obj_split:      20482       3525.4178791133677      20483       3520.2981008641314
obj_split:      20481       3524.2495483618964      20483       3613.2776936972123
obj_split:      20482       3510.285128405429       20482       3562.6924616736646
kmem_unback:    250         4265.508                204         4180.274509803921 
kmem_unback:    262         4277.595419847328       248         3405.7903225806454
kmem_unback:    260         4227.819230769231       270         4265.825925925926 
kmem_unback:    260         3474.3                  258         4275.077519379845 
kmem_unback:    256         4248.3515625            268         4271.014925373134 
kmem_unback:    270         4316.118518518519       264         4526.05303030303  
kmem_unback:    256         4353.13671875           264         4364.598484848485 
kmem_unback:    272         4290.231617647059       260         4312.776923076923 
kmem_unback:    254         4813.787401574803       268         4466.0932835820895
kmem_unback:    254         3621.484251968504       254         4324.192913385827 
kmem_back:      475         5794.0442105263155      889         4415.985376827896 
kmem_back:      284         4148.169014084507       218         3903.5            
kmem_back:      271         3735.4981549815498      311         4454.27652733119  
kmem_back:      243         4085.6831275720165      260         4026.3115384615385
kmem_back:      267         3938.9063670411983      251         2976.2151394422312
kmem_back:      293         2930.9556313993176      281         3230.455516014235 
kmem_back:      258         3425.0813953488373      285         3963.5438596491226
kmem_back:      279         5211.8279569892475      229         3722.943231441048 
kmem_back:      252         4155.599206349207       295         4006.91186440678  
kmem_back:      260         4466.8961538461535      260         3590.1384615384613
alloc_stack:    304         16085.628289473685      306         15794.16339869281 
alloc_stack:    2           19628.5                 2           20072.5           
alloc_stack:    2           20165.0                 2           16187.5           
alloc_stack:    0                                   0                             
alloc_stack:    0                                   0                             
alloc_stack:    10          19795.0                 0                             
alloc_stack:    0                                   120         19134.55          
alloc_stack:    0                                   0                             
alloc_stack:    116         16920.48275862069       10          19536.0           
alloc_stack:    16          20139.5625              0                                 
alloc_stack:    0

I ran tests with D48588.150722.patch for two days without observing any problems.

Closed by commit rG90710f4a3473: pctrie: add parent pointer to nodes (authored by dougm). · Explain WhyMon, Feb 10, 8:20 PM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rG90710f4a3473: pctrie: add parent pointer to nodes.

Herald added subscribers: olce, imp. · View Herald TranscriptMon, Feb 10, 8:20 PM

pctrie: add parent pointer to nodes
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 150790

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

pctrie: add parent pointer to nodesClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 150790

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

pctrie: add parent pointer to nodes
ClosedPublic
Actions

Revision Contents
Changeset List