From nobody Sun Jul 30 20:21:05 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4RDXnb3wKzz4pQ2s; Sun, 30 Jul 2023 20:21:07 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4RDXnZ20Xvz3lrc; Sun, 30 Jul 2023 20:21:06 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690748466; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=K9x16U0V7DBwWUeEVrms4iUIBjd0tdIyrxrgYzFW8oM=; b=jtDZP5+W8CWxZh+D85ps4w0ltHHbwfXfY0shdcswQ89jEMzAAkEcPtLrFMZ8TDF5xdhh8F UER7h2ZiCdoO1dm44ZHDCq46bUyLq2/Xd5zeXu4Rb9uhLz4Qabg5GtBj0ByUKU3XCcyvMY Jv1scqfoGgFEascdrRKNzP9nxiCF88An5RLYFQ8QNsM5Q+L22RpQM2X86kC4iwmvyanoeA mFmMtU6db08KxIwOkXiTJREON9IGD2hfYNMA0cUKWuT12yDANwdNwOp28enhtyKuakxEPo z60n/uHnXI7xy5oacIhsJJkQC6cPQHk0HL9FLpSwN8OpHyC38i22QZ/BfnULXw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690748466; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=K9x16U0V7DBwWUeEVrms4iUIBjd0tdIyrxrgYzFW8oM=; b=n0WIYNn/I91ib55KTk+sxfpWOZaXDbCK8NblEYy06uuMWEbMrvM6Xyu4rRux2yfAe6hkYb oKcWoLNhicmc3Flglb+hekUzdeayOdFsdIwIxDDrIX2Jh9+pmftji5ydnTUJVNbBDAnUJ7 45AIjZ3FJ8h8L1TxviDAFwtyhJ49Nb7aY4L+bzW8LRcVQEs254/OzSswF3/Tzzhj57lOHm Plz5T0g8nQzHVqTUhYqO9REVBnkOqt5T/qR7JJm1X46tHOj5TyfXWcYQm2TL96DQl1BXZE dZLYeVtxNmqlWZwLS1M06eHs+Te4zhdBlfSDSV4scPtLm96OQjvmkjZkmooG4A== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1690748466; a=rsa-sha256; cv=none; b=BWl8mZHjzDWGVuxkq50EmLB1JDB/JCMWSqFIBzuQwsZpoeMJcoQZ22ZfSlH2rcJ8WRWvcd /15+lTQ7ML/YrcYDyFE76I9earupKBBkZIlxDVFjaynsWimj6g/mPnnYiUx5NEDo3WDWt1 cOdSANCIH+qro9p5rw2XbZlOcXhplD2Rhd8+Z6sgEriHBhAwA8TwiND2tGdqjKJLdLkHdx A911ZAcV6WCzfRD1Z6lU6mjXKJtMpzjA8FDO1Dbp0gVF4vkmqEZRcMFOdiBbIfhdNPiep2 6aJLZg+Qpn557cYwEFwThD+L6zefQJ/EASOf362MtiuqAovq7fU3i3y9Zb2G5Q== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4RDXnY4dHPzSP9; Sun, 30 Jul 2023 20:21:05 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 36UKL5RG048771; Sun, 30 Jul 2023 20:21:05 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 36UKL54O048770; Sun, 30 Jul 2023 20:21:05 GMT (envelope-from git) Date: Sun, 30 Jul 2023 20:21:05 GMT Message-Id: <202307302021.36UKL54O048770@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: ac0572e66067 - main - radix_tree: compute slot from keybarr List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: ac0572e6606746aa0e9f39fb6439f9a20a455743 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=ac0572e6606746aa0e9f39fb6439f9a20a455743 commit ac0572e6606746aa0e9f39fb6439f9a20a455743 Author: Doug Moore AuthorDate: 2023-07-30 20:12:06 +0000 Commit: Doug Moore CommitDate: 2023-07-30 20:12:06 +0000 radix_tree: compute slot from keybarr The computation of keybarr(), the function that determines when a search has failed at a non-leaf node, can be done in a way that computes the 'slot' value when keybarr() fails, which is exactly when slot() would next be invoked. Computing things this way saves space in search loops. This reduces the amd64 coding of the search loop in vm_radix_lookup from 40 bytes to 28 bytes. Reviewed by: alc Tested by: pho (as part of a larger change) Differential Revision: https://reviews.freebsd.org/D41235 --- sys/kern/subr_pctrie.c | 57 +++++++++++++++++++++------------------------- sys/vm/vm_radix.c | 61 +++++++++++++++++++++----------------------------- 2 files changed, 51 insertions(+), 67 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index c08e4b5910a5..c0e100173adc 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -99,19 +99,26 @@ static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, enum pctrie_access access); /* - * Return the position in the array for a given level. + * Map index to an array position for the children of node, */ static __inline int -pctrie_slot(uint64_t index, uint16_t level) +pctrie_slot(struct pctrie_node *node, uint64_t index) { - return ((index >> level) & PCTRIE_MASK); + return ((index >> node->pn_clev) & PCTRIE_MASK); } -/* Computes the key (index) with the low-order 'level' + 1 radix-digits zeroed. */ -static __inline uint64_t -pctrie_trimkey(uint64_t index, uint16_t level) +/* + * Returns true if index does not belong to the specified node. Otherwise, + * sets slot value, and returns false. + */ +static __inline bool +pctrie_keybarr(struct pctrie_node *node, uint64_t index, int *slot) { - return (index & -((uint64_t)PCTRIE_COUNT << level)); + index = (index - node->pn_owner) >> node->pn_clev; + if (index >= PCTRIE_COUNT) + return (true); + *slot = index; + return (false); } /* @@ -151,7 +158,8 @@ pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index, _Static_assert(sizeof(uint64_t) * NBBY <= (1 << (sizeof(node->pn_clev) * NBBY)), "pn_clev too narrow"); node->pn_clev = rounddown(flsll(index ^ newind) - 1, PCTRIE_WIDTH); - node->pn_owner = pctrie_trimkey(index, node->pn_clev); + node->pn_owner = PCTRIE_COUNT; + node->pn_owner = index & -(node->pn_owner << node->pn_clev); return (node); } @@ -272,24 +280,13 @@ pctrie_addnode(struct pctrie_node *node, uint64_t index, { int slot; - slot = pctrie_slot(index, node->pn_clev); + slot = pctrie_slot(node, index); pctrie_node_store(&node->pn_child[slot], child, access); node->pn_popmap ^= 1 << slot; KASSERT((node->pn_popmap & (1 << slot)) != 0, ("%s: bad popmap slot %d in node %p", __func__, slot, node)); } -/* - * Returns TRUE if it can be determined that key does not belong to the - * specified node. Otherwise, returns FALSE. - */ -static __inline bool -pctrie_keybarr(struct pctrie_node *node, uint64_t idx) -{ - idx = pctrie_trimkey(idx, node->pn_clev); - return (idx != node->pn_owner); -} - /* * Internal helper for pctrie_reclaim_allnodes(). * This function is recursive. @@ -377,11 +374,10 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) __func__, (uintmax_t)index); break; } - if (pctrie_keybarr(node, index)) { + if (pctrie_keybarr(node, index, &slot)) { newind = node->pn_owner; break; } - slot = pctrie_slot(index, node->pn_clev); parent = node; node = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); @@ -424,9 +420,8 @@ _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr, return (m); break; } - if (pctrie_keybarr(node, index)) + if (pctrie_keybarr(node, index, &slot)) break; - slot = pctrie_slot(index, node->pn_clev); node = pctrie_node_load(&node->pn_child[slot], smr, access); } return (NULL); @@ -494,7 +489,7 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) return (m); break; } - if (pctrie_keybarr(node, index)) { + if (pctrie_keybarr(node, index, &slot)) { /* * If all values in this subtree are > index, then the * least value in this subtree is the answer. @@ -503,7 +498,6 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) succ = node; break; } - slot = pctrie_slot(index, node->pn_clev); /* * Just in case the next search step leads to a subtree of all @@ -528,7 +522,7 @@ pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) * Take a step to the next bigger sibling of the node chosen * last time. In that subtree, all values > index. */ - slot = pctrie_slot(index, succ->pn_clev) + 1; + slot = pctrie_slot(succ, index) + 1; KASSERT((succ->pn_popmap >> slot) != 0, ("%s: no popmap siblings past slot %d in node %p", __func__, slot, succ)); @@ -574,12 +568,11 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index) return (m); break; } - if (pctrie_keybarr(node, index)) { + if (pctrie_keybarr(node, index, &slot)) { if (node->pn_owner < index) pred = node; break; } - slot = pctrie_slot(index, node->pn_clev); if ((node->pn_popmap & ((1 << slot) - 1)) != 0) pred = node; node = pctrie_node_load(&node->pn_child[slot], NULL, @@ -588,7 +581,7 @@ pctrie_lookup_le(struct pctrie *ptree, uint64_t index) if (pred == NULL) return (NULL); if (pred != node) { - slot = pctrie_slot(index, pred->pn_clev); + slot = pctrie_slot(pred, index); KASSERT((pred->pn_popmap & ((1 << slot) - 1)) != 0, ("%s: no popmap siblings before slot %d in node %p", __func__, slot, pred)); @@ -624,7 +617,7 @@ pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) break; parent = node; node = child; - slot = pctrie_slot(index, node->pn_clev); + slot = pctrie_slot(node, index); child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); } @@ -649,7 +642,7 @@ pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn) if (parent == NULL) pctrie_root_store(ptree, child, PCTRIE_LOCKED); else { - slot = pctrie_slot(index, parent->pn_clev); + slot = pctrie_slot(parent, index); KASSERT(node == pctrie_node_load(&parent->pn_child[slot], NULL, PCTRIE_LOCKED), ("%s: invalid child value", __func__)); diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index f50f9e3605a1..c678bfe1baa7 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -126,20 +126,26 @@ static void vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v, enum vm_radix_access access); /* - * Return the position in the array for a given level. + * Map index to an array position for the children of rnode, */ static __inline int -vm_radix_slot(vm_pindex_t index, uint16_t level) +vm_radix_slot(struct vm_radix_node *rnode, vm_pindex_t index) { - return ((index >> level) & VM_RADIX_MASK); + return ((index >> rnode->rn_clev) & VM_RADIX_MASK); } -/* Computes the key (index) with the low-order 'level' + 1 radix-digits - * zeroed. */ -static __inline vm_pindex_t -vm_radix_trimkey(vm_pindex_t index, uint16_t level) +/* + * Returns true if index does not belong to the specified rnode. Otherwise, + * sets slot value, and returns false. + */ +static __inline bool +vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t index, int *slot) { - return (index & -((vm_pindex_t)VM_RADIX_COUNT << level)); + index = (index - rnode->rn_owner) >> rnode->rn_clev; + if (index >= VM_RADIX_COUNT) + return (true); + *slot = index; + return (false); } /* @@ -177,7 +183,8 @@ vm_radix_node_get(vm_pindex_t index, vm_pindex_t newind) _Static_assert(sizeof(vm_pindex_t) * NBBY <= (1 << (sizeof(rnode->rn_clev) * NBBY)), "rn_clev too narrow"); rnode->rn_clev = rounddown(flsll(index ^ newind) - 1, VM_RADIX_WIDTH); - rnode->rn_owner = vm_radix_trimkey(index, rnode->rn_clev); + rnode->rn_owner = VM_RADIX_COUNT; + rnode->rn_owner = index & -(rnode->rn_owner << rnode->rn_clev); return (rnode); } @@ -298,24 +305,13 @@ vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, { int slot; - slot = vm_radix_slot(index, rnode->rn_clev); + slot = vm_radix_slot(rnode, index); vm_radix_node_store(&rnode->rn_child[slot], child, access); rnode->rn_popmap ^= 1 << slot; KASSERT((rnode->rn_popmap & (1 << slot)) != 0, ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); } -/* - * Returns TRUE if it can be determined that key does not belong to the - * specified rnode. Otherwise, returns FALSE. - */ -static __inline bool -vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx) -{ - idx = vm_radix_trimkey(idx, rnode->rn_clev); - return (idx != rnode->rn_owner); -} - /* * Internal helper for vm_radix_reclaim_allnodes(). * This function is recursive. @@ -432,11 +428,10 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) __func__, (uintmax_t)index); break; } - if (vm_radix_keybarr(rnode, index)) { + if (vm_radix_keybarr(rnode, index, &slot)) { newind = rnode->rn_owner; break; } - slot = vm_radix_slot(index, rnode->rn_clev); parent = rnode; rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); } @@ -479,9 +474,8 @@ _vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, return (m); break; } - if (vm_radix_keybarr(rnode, index)) + if (vm_radix_keybarr(rnode, index, &slot)) break; - slot = vm_radix_slot(index, rnode->rn_clev); rnode = vm_radix_node_load(&rnode->rn_child[slot], access); } return (NULL); @@ -551,7 +545,7 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) return (m); break; } - if (vm_radix_keybarr(rnode, index)) { + if (vm_radix_keybarr(rnode, index, &slot)) { /* * If all pages in this subtree have pindex > index, * then the page in this subtree with the least pindex @@ -561,7 +555,6 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) succ = rnode; break; } - slot = vm_radix_slot(index, rnode->rn_clev); /* * Just in case the next search step leads to a subtree of all @@ -585,7 +578,7 @@ vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) * Take a step to the next bigger sibling of the node chosen * last time. In that subtree, all pages have pindex > index. */ - slot = vm_radix_slot(index, succ->rn_clev) + 1; + slot = vm_radix_slot(succ, index) + 1; KASSERT((succ->rn_popmap >> slot) != 0, ("%s: no popmap siblings past slot %d in node %p", __func__, slot, succ)); @@ -630,12 +623,11 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) return (m); break; } - if (vm_radix_keybarr(rnode, index)) { + if (vm_radix_keybarr(rnode, index, &slot)) { if (rnode->rn_owner < index) pred = rnode; break; } - slot = vm_radix_slot(index, rnode->rn_clev); if ((rnode->rn_popmap & ((1 << slot) - 1)) != 0) pred = rnode; rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); @@ -643,7 +635,7 @@ vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) if (pred == NULL) return (NULL); if (pred != rnode) { - slot = vm_radix_slot(index, pred->rn_clev); + slot = vm_radix_slot(pred, index); KASSERT((pred->rn_popmap & ((1 << slot) - 1)) != 0, ("%s: no popmap siblings before slot %d in node %p", __func__, slot, pred)); @@ -677,7 +669,7 @@ vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) break; parent = rnode; rnode = child; - slot = vm_radix_slot(index, rnode->rn_clev); + slot = vm_radix_slot(rnode, index); child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); } if ((m = vm_radix_topage(child)) == NULL || m->pindex != index) @@ -700,7 +692,7 @@ vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) if (parent == NULL) vm_radix_root_store(rtree, child, LOCKED); else { - slot = vm_radix_slot(index, parent->rn_clev); + slot = vm_radix_slot(parent, index); KASSERT(rnode == vm_radix_node_load(&parent->rn_child[slot], LOCKED), ("%s: invalid child value", __func__)); @@ -762,9 +754,8 @@ vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) } break; } - if (vm_radix_keybarr(rnode, index)) + if (vm_radix_keybarr(rnode, index, &slot)) break; - slot = vm_radix_slot(index, rnode->rn_clev); parent = rnode; rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); }