Page MenuHomeFreeBSD

Use bitstrings for reservation popmaps

Authored by dougm on Dec 6 2021, 11:20 PM.



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.

Diff Detail

Lint Skipped
Unit Tests Skipped

Event Timeline

dougm requested review of this revision.Dec 6 2021, 11:20 PM
dougm created this revision.

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.
[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]#

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)

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.


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.


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

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

Update after commit 6f1c8908272f3c0a6631e001bd2eb50a5b69261d.

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

dougm added inline comments.

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.


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

dougm marked an inline comment as done.

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

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

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


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.

Rewrite the alignment/boundary rounding a bit more carefully.

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

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.


Shouldn't the third parameter be npages?

dougm added inline comments.


dougm marked an inline comment as done.

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


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.

Undo last change.

Take a break while I think about this.


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.


This function should be documented in bitstring.3.


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.

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.

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.

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

This revision is now accepted and ready to land.Jan 11 2022, 6:07 PM
This revision was automatically updated to reflect the committed changes.