Page MenuHomeFreeBSD

radix_trie: skip needless compare in lookup_le, lookup_ge
ClosedPublic

Authored by dougm on Jun 24 2023, 8:29 AM.
Tags
None
Referenced Files
F102661391: D40746.diff
Fri, Nov 15, 12:23 PM
Unknown Object (File)
Sep 26 2024, 8:45 AM
Unknown Object (File)
Sep 23 2024, 11:49 AM
Unknown Object (File)
Sep 22 2024, 1:48 PM
Unknown Object (File)
Sep 18 2024, 2:47 PM
Unknown Object (File)
Sep 18 2024, 9:40 AM
Unknown Object (File)
Sep 18 2024, 4:21 AM
Unknown Object (File)
Sep 2 2024, 6:50 AM
Subscribers

Details

Summary

In _lookup_ge, where a loop "looks for an available edge or val within the current bisection node" (to quote the code comment), the value of index has already been modified to guarantee that it is the least value than can be found in the non-NULL child node being examined. Therefore, if the non-NULL child is a leaf, there's no need to compare 'index' to anything, and the value can just be returned.

The same is true for _lookup_le with 'most' replacing 'least'.

Test Plan

A GENERIC kernel boots and no KASSERTS are triggered.

Peter, can you test this?

Diff Detail

Repository
rG FreeBSD src repository
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

dougm requested review of this revision.Jun 24 2023, 8:29 AM
dougm created this revision.
sys/vm/vm_radix.c
712–713

I would add a KASSERT.

dougm marked an inline comment as done.
dougm added a subscriber: pho.

I ran tests with D40746.id123750.diff for 10 hours without seeing any issues.

This revision is now accepted and ready to land.Jun 27 2023, 5:33 AM