radix_tree: redefine the clev field

[dougm]

Summary

The clev field in the node struct is almost always multiplied by WIDTH; occasionally, it is incremented and then multiplied by WIDTH. Instructions can be saved by storing it always multiplied by WIDTH.

For the computation of slot(), this just eliminates a multiplication. For trimkey(), where the caller always adds one to clev before passing it as an argument, this means having the caller not do that, and having trimkey handle it not by adding WIDTH to the input parameter, but by having it shift COUNT, and not 1. That leads to the same result when level is small, and it relieves keybarr of the need to test to avoid shifting by a possibly-too-large value, since level is always < 64.

Test Plan

A kernel boots.

[dougm]

Comparing vm_radix_lookup loops on amd64.

Before, 54 bytes

2d0: 48 89 f2                     	movq	%rsi, %rdx
 2d3: 48 d3 ea                     	shrq	%cl, %rdx
 2d6: 83 e2 0f                     	andl	$15, %edx
 2d9: 48 8b 44 d0 10               	movq	16(%rax,%rdx,8), %rax
 2de: a8 01                        	testb	$1, %al
 2e0: 75 26                        	jne	0x308 <vm_radix_lookup+0x48>
 2e2: 0f b6 50 0a                  	movzbl	10(%rax), %edx
 2e6: 48 8d 0c 95 00 00 00 00      	leaq	(,%rdx,4), %rcx
 2ee: 48 83 fa 0e                  	cmpq	$14, %rdx
 2f2: 77 dc                        	ja	0x2d0 <vm_radix_lookup+0x10>
 2f4: 48 c7 c2 f0 ff ff ff         	movq	$-16, %rdx
 2fb: 48 d3 e2                     	shlq	%cl, %rdx
 2fe: 48 21 f2                     	andq	%rsi, %rdx
 301: 48 3b 10                     	cmpq	(%rax), %rdx
 304: 74 ca                        	je	0x2d0 <vm_radix_lookup+0x10>

After, 40 bytes

2c0: 0f b6 48 0a                  	movzbl	10(%rax), %ecx
2c4: 48 c7 c2 f0 ff ff ff         	movq	$-16, %rdx
2cb: 48 d3 e2                     	shlq	%cl, %rdx
2ce: 48 21 f2                     	andq	%rsi, %rdx
2d1: 48 3b 10                     	cmpq	(%rax), %rdx
2d4: 75 1e                        	jne	0x2f4 <vm_radix_lookup+0x44>
2d6: 48 89 f2                     	movq	%rsi, %rdx
2d9: 48 d3 ea                     	shrq	%cl, %rdx
2dc: 83 e2 0f                     	andl	$15, %edx
2df: 48 8b 44 d0 10               	movq	16(%rax,%rdx,8), %rax
2e4: a8 01                        	testb	$1, %al
2e6: 74 d8                        	je	0x2c0 <vm_radix_lookup+0x10>

[kib]

sys/kern/subr_pctrie.c

92

The max level is 15 for 64bit, and 21 for 32bit, am I right? Or is it 22 for 32bit?

I.e., in any case, the max value stored in the field is ~66. Might be add some static assert ensuring that pn_clev width is enough.

[dougm]

sys/kern/subr_pctrie.c

92

If VM_RADIX_WIDTH is 4, then the max levels are 15 for 64 bit and 7 for 32 bit.
If VM_RADIX_WIDTH is 3, then the max levels are 21 and 10.

The max value stored in the field (after this change) is 63.

[dougm]

Add _Static_asserts that the number of bits in the index type is small enough to fit in the clev struct member.