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

Lint

Lint Skipped

Unit

Tests Skipped

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 150722

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

pctrie: add parent pointer to nodesClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 150722

sys/kern/subr_pctrie.c

sys/sys/pctrie.h

pctrie: add parent pointer to nodes
ClosedPublic
Actions

Revision Contents
Changeset List