Use bitstrings for reservation popmaps

[dougm]

Summary

vm_reserv.c uses its own bitstring implemenation for popmaps. Using the bitstring_t type from a standard header eliminates the code duplication, allows some bit-at-a-time operations to be replaced with more efficient bitstring range operations, and, in vm_reserv_test_contig, allows bit_ffc_area_at to more efficiently search for a big-enough set of consecutive zero-bits.

It makes a kernel that does not immediately crash.

[pho]

Which revision did you create the diff from?

[root@mercat1 /usr/src]# patch -C < /tmp/D33312.99617.diff
Hmm...  Looks like a unified diff to me...
The text leading up to this was:
--------------------------
|diff --git a/sys/vm/vm_reserv.c b/sys/vm/vm_reserv.c
|--- a/sys/vm/vm_reserv.c
|+++ b/sys/vm/vm_reserv.c
--------------------------
Patching file sys/vm/vm_reserv.c using Plan A...
Hunk #1 succeeded at 53.
Hunk #2 succeeded at 106.
Hunk #3 succeeded at 113.
Hunk #4 succeeded at 155.
Hunk #5 succeeded at 372.
Hunk #6 succeeded at 384.
Hunk #7 succeeded at 410.
Hunk #8 succeeded at 424.
Hunk #9 succeeded at 530.
Hunk #10 succeeded at 540.
Hunk #11 succeeded at 642.
Hunk #12 succeeded at 812.
Hunk #13 succeeded at 906.
Hunk #14 succeeded at 1001.
Hunk #15 succeeded at 1043.
Hunk #16 succeeded at 1063.
Hunk #17 succeeded at 1163.
Hmm...  Ignoring the trailing garbage.
done
[root@mercat1 /usr/src]# git branch -v
* main 43c4b47b75f37 flex_spi: Don't try to destroy disk if it doesn't exist
[root@mercat1 /usr/src]#

[dougm]

Which revision did you create the diff from?

I hope this is the kind of answer you're looking for:
commit e3044071dec1d752a7103b5ae55fe3cff2f5b957 (HEAD -> main, freebsd/main, freebsd/HEAD)

[pho]

In D33312#753182, @dougm wrote:

Which revision did you create the diff from?

I hope this is the kind of answer you're looking for:
commit e3044071dec1d752a7103b5ae55fe3cff2f5b957 (HEAD -> main, freebsd/main, freebsd/HEAD)

Yes, thank you very much.

[markj]

sys/vm/vm_reserv.c

925

As a micro-optimization, I wonder if it'd be preferable to have a bit_clear_all() or so which simply memset()s the map.

1190

How do we know that 0 <= lo < VM_LEVEL_0_NPAGES here?

[pho]

I ran stress test for 24 hours with D33312.99617.diff without seeing any problems.

[dougm]

Update after commit 6f1c8908272f3c0a6631e001bd2eb50a5b69261d.

Avoid needless call to bit_ffs_at in vm_reserv_find_contig when no alignment adjustment is needed.

[dougm]

sys/vm/vm_reserv.c

925

I conjecture, without testing, that with VM_LEVEL_0_NPAGES being a multiple of 64, a decent compiler could optimize out checks for writing <64 bits at the beginning or end of the map.

1190

After changes made elsewhere, ppn_align and ppn_bound should be <= VM_LEVEL_0_NPAGES, so lo should be also.

[dougm]

Use '__diagused' to avoid creating a function just to call it from KASSERT.

[pho]

I ran tests for 24 hours with D33312.100195.diff without seeing any problems.

[dougm]

Slightly reduce the object code size by dropping over-optimization in vm_reserv_find_contig.

[alc]

sys/vm/vm_reserv.c

925

The implementation of bit_nclear() is already hand-optimized for clearing ranges. That said, it handles the first and last long specially, and uses a loop for the longs in between:

ffffffff80f41b21: 49 c7 40 60 00 00 00 00       movq    $0, 96(%r8)
ffffffff80f41b29: 4d 39 e5              cmpq    %r12, %r13
ffffffff80f41b2c: 73 13                 jae     0xffffffff80f41b41 <vm_reserv_break+0x271>
ffffffff80f41b2e: 66 90                 nop
ffffffff80f41b30: 49 c7 45 00 00 00 00 00       movq    $0, (%r13)
ffffffff80f41b38: 49 83 c5 08           addq    $8, %r13
ffffffff80f41b3c: 4d 39 e5              cmpq    %r12, %r13
ffffffff80f41b3f: 72 ef                 jb      0xffffffff80f41b30 <vm_reserv_break+0x260>
ffffffff80f41b41: 49 c7 80 98 00 00 00 00 00 00 00      movq    $0, 152(%r8)

I omitted the extra instructions for initializing %r12 and %r13.

[dougm]

Rewrite the alignment/boundary rounding a bit more carefully.

[dougm]

Use roundup2 instead of rounddown2, since it is used elsewhere here, and because it is easier to spell.

[dougm]

Make changes in bitstring.h, and in vm_reserv_break, to shrink the object code size a bit. Some allow the compiler to optimize out code when compile-time constants are multiples of 64. Some allow the same code to find 1-bits as 0-bits, so that two nearly-identical copies of the code are not generated.

[dougm]

Update after commit 0d5fac287294490ac488d74e598e019334610bdb

[markj]

sys/vm/vm_reserv.c

631–632

Shouldn't the third parameter be npages?

[dougm]

sys/vm/vm_reserv.c

631–632

Yes.

[dougm]

Correct a bound error. Update for changes in surrounding code.

[dougm]

sys/vm/vm_reserv.c

631–632

No, on second thought. This is supposed to test npages bits, from index to index + npages -1. The first page not to be checked is at index + npages.

I'm changing it back.

[dougm]

Undo last change.

Take a break while I think about this.

[dougm]

sys/vm/vm_reserv.c

631–632

bit_ffs_at(str, start, nbits, result) examines up to nbits-start bits in a string of total length nbits. We want to examine up to npages bits, so nbits-start must be npages. With start and nbits as index and index+npages, we get that. The total length of popmap is likely more than index+npages, but we don't need to look at all the bits to the end of the map.

I can just write an ntest function for bitstring.h that would have parameters like those of nset and nclear, if that would make this clearer.

[markj]

sys/sys/bitstring.h

234–235

This function should be documented in bitstring.3.

sys/vm/vm_reserv.c

631–632

I see now. bit_ntest() seems like a sensible addition. The code is clear to me now for what it's worth, I was just unfamiliar with the bitstring.h functions.

[dougm]

Define a bit_ntest function, document it, and use it in place of bit_ffs in a couple of places.

Tune up ffs_area_at.

Document bit_ff_at and bit_ff_area_at.

[markj]

I discovered that we have some regression tests for bitstring(9), in tests/sys/sys/bitstring.c. A couple of them fail with this patch applied:

markj@nuc> kyua test bitstring_test
bitstring_test:bit_clear  ->  passed  [0.023s]   
bitstring_test:bit_count  ->  passed  [0.003s]
bitstring_test:bit_ffc  ->  passed  [0.003s]                                                                                                                                                                                                                                                                                  
bitstring_test:bit_ffc_area  ->  failed: /usr/home/markj/src/freebsd/tests/sys/sys/bitstring_test.c:440: 7 != location: bit_ffc_area: failed to find location of size 3  [0.003s]                                                                                                                                             
bitstring_test:bit_ffc_area_no_match  ->  passed  [0.003s]                                                                                                                                                                                                                                                                    
bitstring_test:bit_ffc_at  ->  passed  [0.003s]                                                                                                                
bitstring_test:bit_ffs  ->  passed  [0.003s]                                                                                                                                                                                                                                                                                  
bitstring_test:bit_ffs_area  ->  failed: /usr/home/markj/src/freebsd/tests/sys/sys/bitstring_test.c:368: 5 != location: bit_ffs_area: failed to find location of size 3  [0.003s]                                                                                                                                             
bitstring_test:bit_ffs_area_no_match  ->  passed  [0.001s]                                                                                                                                                                                                                                                                    
bitstring_test:bit_ffs_at  ->  passed  [0.001s]                                                                                                                                                                                                                                                                               
bitstring_test:bit_foreach  ->  passed  [0.001s]                                                                                                                                                                                                                                                                              
bitstring_test:bit_foreach_at  ->  passed  [0.010s]                                                                                                                                                                                                                                                                           
bitstring_test:bit_foreach_unset  ->  passed  [0.001s]                                                                                                                                                                                                                                                                        
bitstring_test:bit_foreach_unset_at  ->  passed  [0.011s]                                                                                                                                                                                                                                                                     
bitstring_test:bit_nclear  ->  passed  [0.040s]                                                                                                                
bitstring_test:bit_nset  ->  passed  [0.035s]                                                                                                                                                                                                                                                                                 
bitstring_test:bit_set  ->  passed  [0.005s]                                                                                                                                                                                                                                                                                  
bitstring_test:bitstr_in_struct  ->  passed  [0.001s]
bitstring_test:bitstr_size  ->  passed  [0.001s]

At some point it would be worth adding tests for the new bitstring primitives to tests/sys/sys/bitstring_test.c.

[dougm]

Fix initial mask on area_at. Fix off-by-one in end test on area_at. Add some test cases.