vm_radix: define vm_radix_insert_lookup_lt and use in vm_page_rename

[rlibby]

Summary

Use the new pctrie combined lookup/insert. This is an easy application
of the new facility. There are other places where we do this for pages
that may need more plumbing to use combined lookup/insert.

Sponsored by: Dell EMC Isilon

[kib]

sys/vm/vm_page.c

1862

[rlibby]

kib style feedback

[dougm]

sys/vm/vm_radix.h

86

So, the KASSERT you're dropping above has no effect in a GENERIC-NODEBUG build, but this check will still be made in that build. So is this better than KASSERT(error != EEXIST)?

[rlibby]

sys/vm/vm_radix.h

86

I believe I'm preserving the GENERIC-NODEBUG behavior from before the patch. vm_radix_insert() does a hard panic on a collision.

[markj]

I guess vm_page_insert() could be improved similarly, but that's more work. IMO a better long-term direction there is to remove the memq (insertion into which is the purpose of looking up mpred in the first place) and use the radix tree for iteration instead, but that's a separate topic.

[rlibby]

In D45396#1037485, @markj wrote:

I guess vm_page_insert() could be improved similarly, but that's more work.

Yes. It's not a lot of work, I just didn't want to get ahead of myself. I can put up a patch later this week when I get some more time.

IMO a better long-term direction there is to remove the memq (insertion into which is the purpose of looking up mpred in the first place) and use the radix tree for iteration instead, but that's a separate topic.

Yes, I've thought about that a little but haven't explored thoroughly. Honestly we may want to go that direction for bufs too. Maintaining tailq linkage can be costly as the neighbors may be cache cold. Privately we have added cache line prefetches in certain places which are surprisingly effective, but I don't know if we have an appetite for that sort of thing in tree.

If we actually want to take steps toward removing the linkage, we may need to provide better iterator primitives or at least conventions for pctrie, as otherwise scans may be more costly.

[jeff]

In D45396#1037489, @rlibby wrote:

In D45396#1037485, @markj wrote:

I guess vm_page_insert() could be improved similarly, but that's more work.

Yes. It's not a lot of work, I just didn't want to get ahead of myself. I can put up a patch later this week when I get some more time.

IMO a better long-term direction there is to remove the memq (insertion into which is the purpose of looking up mpred in the first place) and use the radix tree for iteration instead, but that's a separate topic.

Yes, I've thought about that a little but haven't explored thoroughly. Honestly we may want to go that direction for bufs too. Maintaining tailq linkage can be costly as the neighbors may be cache cold. Privately we have added cache line prefetches in certain places which are surprisingly effective, but I don't know if we have an appetite for that sort of thing in tree.

If we actually want to take steps toward removing the linkage, we may need to provide better iterator primitives or at least conventions for pctrie, as otherwise scans may be more costly.

I've prototyped this twice I think. Both times I struggled with performance parity. You really need a very capable iterator and probably some bounded batch lookup operations. If you eliminate the tailq you can support some lock free modifying operations as well.