git: 72c3a43b16b2 - main - radix_trie: skip compare in lookup_le, lookup_ge

From: Doug Moore <dougm_at_FreeBSD.org>
Date: Tue, 27 Jun 2023 05:44:53 UTC
The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=72c3a43b16b20cdc86508e58f61c2e0e28e65549

commit 72c3a43b16b20cdc86508e58f61c2e0e28e65549
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2023-06-27 05:42:41 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2023-06-27 05:42:41 +0000

    radix_trie: skip compare in lookup_le, lookup_ge
    
    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'.
    Reviewed by:    alc
    Tested by:      pho
    Differential Revision:  https://reviews.freebsd.org/D40746
---
 sys/kern/subr_pctrie.c | 10 ++++++----
 sys/vm/vm_radix.c      | 10 ++++++----
 2 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index 44a00a9eef77..d9269bfb3885 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -560,8 +560,9 @@ ascend:
 				    NULL, PCTRIE_LOCKED);
 				if (pctrie_isleaf(child)) {
 					m = pctrie_toval(child);
-					if (*m >= index)
-						return (m);
+					KASSERT(*m >= index,
+					    ("pctrie_lookup_ge: leaf < index"));
+					return (m);
 				} else if (child != NULL)
 					goto descend;
 			} while (slot < (PCTRIE_COUNT - 1));
@@ -677,8 +678,9 @@ ascend:
 				    NULL, PCTRIE_LOCKED);
 				if (pctrie_isleaf(child)) {
 					m = pctrie_toval(child);
-					if (*m <= index)
-						return (m);
+					KASSERT(*m <= index,
+					    ("pctrie_lookup_le: leaf > index"));
+					return (m);
 				} else if (child != NULL)
 					goto descend;
 			} while (slot > 0);
diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c
index 7d3408226be1..9c8ba5287d4e 100644
--- a/sys/vm/vm_radix.c
+++ b/sys/vm/vm_radix.c
@@ -595,8 +595,9 @@ ascend:
 				    LOCKED);
 				if (vm_radix_isleaf(child)) {
 					m = vm_radix_topage(child);
-					if (m->pindex >= index)
-						return (m);
+					KASSERT(m->pindex >= index,
+					    ("vm_radix_lookup_ge: leaf<index"));
+					return (m);
 				} else if (child != NULL)
 					goto descend;
 			} while (slot < (VM_RADIX_COUNT - 1));
@@ -709,8 +710,9 @@ ascend:
 				    LOCKED);
 				if (vm_radix_isleaf(child)) {
 					m = vm_radix_topage(child);
-					if (m->pindex <= index)
-						return (m);
+					KASSERT(m->pindex <= index,
+					    ("vm_radix_lookup_le: leaf>index"));
+					return (m);
 				} else if (child != NULL)
 					goto descend;
 			} while (slot > 0);