From nobody Sun Jul 30 06:27:40 2023 X-Original-To: dev-commits-src-all@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 4RDBJW5Tfyz4pydQ; Sun, 30 Jul 2023 06:28:08 +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 4RDBJF5Fgfz3NPW; Sun, 30 Jul 2023 06:27:56 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690698478; 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=+SrmNcLqS/WJtUZaiLwQal6GnE4m8npNKYQoefw0dTU=; b=rCK4fY7r/FooVMnz+hyBeRq9LSBRcn4Yl7OZ1xvkU6xbACKVrWWlFQh1O0iD6MvKnWaoBH jRge4xKUTQV9axDowxvssojnqNDsN3cQpbwd5PNdy7Kn+I/ywPtFqiirA3rmoffGDWjvDW CW/8df+c1il/qOiRLFB1p+Q4lOYBbybBJYEzAq9EKPzyhoMUiXo3OCvT6YqtKwi2MINwol K2RDu96NT4lDh0KQzfvD3ZH0qEHOUX94VNdtlUnRFmRRZKAx3LcCPasIp7Z7At+vsOlzgP hJrn2qWgrtXCHNat8THsFTERONkY8cNB80BYoTydA9QXNCGJrvvB3Foo8iMa6g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1690698478; 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=+SrmNcLqS/WJtUZaiLwQal6GnE4m8npNKYQoefw0dTU=; b=Aaimb61bQIKwbMx1CkfgMCtS43PP7mjgIw5LY/z1IQu4Xve1JjLHDiI1R2S9YY0egEXa7r ZmwN+ZSsVoo3i69cJtCIJvkIMMJA3Wi2YAnzrWIM6twVpTCyXICf49ukJ7X5tOQUBuRT+4 t9xzhEPhqe+/25/m+cPnPbXSKmBXk0miOgo8oQ4WI1b53EW4nZ4hy2rGqYhuJEotXuZABU +x6xbGLQLlj9t4uGGenqV1aX1+iq1X9eaIg+BzkU6foiL6rSlJK8GXGBcp214QAg1Bt9RQ 7emYGSciOu7KcCXtIO9ZUAO65nICbZxU4WgVK4P0E5+3r6ewZV8peGTv4MwNgA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1690698478; a=rsa-sha256; cv=none; b=AAggam/Tr5n+HdNGHK1sXW+p1tOsgVRQHLpU8y6CEEs7RopfkRHKESRku+7ntQr2susNne WdpSDEl377Khol/5bPRbi/gjsjrw2adgUFi2goYe2X6Vzmi/2xeunozEvFyyq+mjlLjL8T k+uU2EH7XXVKmRXrx0sKoKu3+lMJj9YJh4zq4Vh87Q7QNHeoDDnKRRdXYoujvj/jDx94N+ WD9wpn/KrEJ/1yIZrdQIh+RXc1nkfXxvPj+zAq1TeJO4c5OBD07nOks+8ni9nhItrRFBTT 4OpfJ8GdLxXtvOBwguWT1giMfcD8e14DBNSCZXH6Kcb0OfPZ1rM9j5ubUl9SOQ== 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 4RDBHy4dN7z13yl; Sun, 30 Jul 2023 06:27:42 +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 36U6Re96064141; Sun, 30 Jul 2023 06:27:40 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 36U6ReV9064140; Sun, 30 Jul 2023 06:27:40 GMT (envelope-from git) Date: Sun, 30 Jul 2023 06:27:40 GMT Message-Id: <202307300627.36U6ReV9064140@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: 38f5cb1bfbe1 - main - radix_tree: redefine the clev field List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@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: 38f5cb1bfbe11bad92ba0266251ff3b0b8fcda73 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=38f5cb1bfbe11bad92ba0266251ff3b0b8fcda73 commit 38f5cb1bfbe11bad92ba0266251ff3b0b8fcda73 Author: Doug Moore AuthorDate: 2023-07-30 06:20:07 +0000 Commit: Doug Moore CommitDate: 2023-07-30 06:20:07 +0000 radix_tree: redefine the clev field 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 change has the caller, not the caller, do that. Trimkey() handles it not by adding WIDTH to the input parameter, but by shifting COUNT, and not 1. That produces the same result, and it relieves keybarr of the need to test to avoid shifting by more than 63 bits, since level is always <= 63. This takes 3 instrutions and 14 bytes out of the basic lookup loop on amd64. Reviewed by: kib Tested by: pho (as part of a larger change) Differential Revision: https://reviews.freebsd.org/D41226 --- sys/kern/subr_pctrie.c | 76 +++++++++++++++++++----------------------------- sys/vm/vm_radix.c | 78 ++++++++++++++++++++------------------------------ 2 files changed, 60 insertions(+), 94 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index 6d45d9762a78..c08e4b5910a5 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -83,17 +83,13 @@ _Static_assert(sizeof(pn_popmap_t) <= sizeof(int), #define PCTRIE_FLAGS (PCTRIE_ISLEAF) #define PCTRIE_PAD PCTRIE_FLAGS -/* Returns one unit associated with specified level. */ -#define PCTRIE_UNITLEVEL(lev) \ - ((uint64_t)1 << ((lev) * PCTRIE_WIDTH)) - struct pctrie_node; typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; struct pctrie_node { uint64_t pn_owner; /* Owner of record. */ pn_popmap_t pn_popmap; /* Valid children. */ - uint8_t pn_clev; /* Current level. */ + uint8_t pn_clev; /* Level * WIDTH. */ smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */ }; @@ -108,14 +104,14 @@ static __inline void pctrie_node_store(smr_pctnode_t *p, void *val, static __inline int pctrie_slot(uint64_t index, uint16_t level) { - return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK); + return ((index >> level) & PCTRIE_MASK); } -/* Computes the key (index) with the low-order 'level' radix-digits zeroed. */ +/* 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) { - return (index & -PCTRIE_UNITLEVEL(level)); + return (index & -((uint64_t)PCTRIE_COUNT << level)); } /* @@ -124,7 +120,7 @@ pctrie_trimkey(uint64_t index, uint16_t level) */ static struct pctrie_node * pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index, - uint16_t clevel) + uint64_t newind) { struct pctrie_node *node; @@ -142,8 +138,20 @@ pctrie_node_get(struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t index, PCTRIE_NULL, PCTRIE_UNSERIALIZED); node->pn_popmap = 0; } - node->pn_owner = pctrie_trimkey(index, clevel + 1); - node->pn_clev = clevel; + + /* + * From the highest-order bit where the indexes differ, + * compute the highest level in the trie where they differ. Then, + * compute the least index of this subtrie. + */ + KASSERT(index != newind, ("%s: passing the same key value %jx", + __func__, (uintmax_t)index)); + _Static_assert(sizeof(long long) >= sizeof(uint64_t), + "uint64 too wide"); + _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); return (node); } @@ -259,37 +267,18 @@ pctrie_toval(struct pctrie_node *node) * Make 'child' a child of 'node'. */ static __inline void -pctrie_addnode(struct pctrie_node *node, uint64_t index, uint16_t clev, +pctrie_addnode(struct pctrie_node *node, uint64_t index, struct pctrie_node *child, enum pctrie_access access) { int slot; - slot = pctrie_slot(index, clev); + slot = pctrie_slot(index, node->pn_clev); 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 the level where two keys differ. - * It cannot accept 2 equal keys. - */ -static __inline uint16_t -pctrie_keydiff(uint64_t index1, uint64_t index2) -{ - - KASSERT(index1 != index2, ("%s: passing the same key value %jx", - __func__, (uintmax_t)index1)); - CTASSERT(sizeof(long long) >= sizeof(uint64_t)); - - /* - * From the highest-order bit where the indexes differ, - * compute the highest level in the trie where they differ. - */ - return ((flsll(index1 ^ index2) - 1) / PCTRIE_WIDTH); -} - /* * Returns TRUE if it can be determined that key does not belong to the * specified node. Otherwise, returns FALSE. @@ -297,12 +286,8 @@ pctrie_keydiff(uint64_t index1, uint64_t index2) static __inline bool pctrie_keybarr(struct pctrie_node *node, uint64_t idx) { - - if (node->pn_clev < PCTRIE_LIMIT) { - idx = pctrie_trimkey(idx, node->pn_clev + 1); - return (idx != node->pn_owner); - } - return (false); + idx = pctrie_trimkey(idx, node->pn_clev); + return (idx != node->pn_owner); } /* @@ -366,7 +351,6 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) struct pctrie_node *leaf, *node, *parent; smr_pctnode_t *parentp; int slot; - uint16_t clev; index = *val; leaf = pctrie_toleaf(val); @@ -383,8 +367,7 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) if (parent == NULL) ptree->pt_root = leaf; else - pctrie_addnode(parent, index, - parent->pn_clev, leaf, + pctrie_addnode(parent, index, leaf, PCTRIE_LOCKED); return (0); } @@ -411,13 +394,12 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) */ parentp = (parent != NULL) ? &parent->pn_child[slot]: (smr_pctnode_t *)&ptree->pt_root; - clev = pctrie_keydiff(newind, index); - parent = pctrie_node_get(ptree, allocfn, index, clev); + parent = pctrie_node_get(ptree, allocfn, index, newind); if (parent == NULL) return (ENOMEM); /* These writes are not yet visible due to ordering. */ - pctrie_addnode(parent, index, clev, leaf, PCTRIE_UNSERIALIZED); - pctrie_addnode(parent, newind, clev, node, PCTRIE_UNSERIALIZED); + pctrie_addnode(parent, index, leaf, PCTRIE_UNSERIALIZED); + pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED); /* Synchronize to make the above visible. */ pctrie_node_store(parentp, parent, PCTRIE_LOCKED); return (0); @@ -714,7 +696,7 @@ DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) node = (struct pctrie_node *)addr; db_printf("node %p, owner %jx, children popmap %04x, level %u:\n", (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, - node->pn_clev); + node->pn_clev / PCTRIE_WIDTH); for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { slot = ffs(popmap) - 1; tmp = pctrie_node_load(&node->pn_child[slot], NULL, @@ -722,7 +704,7 @@ DB_SHOW_COMMAND(pctrienode, db_show_pctrienode) db_printf("slot: %d, val: %p, value: %p, clev: %d\n", slot, (void *)tmp, pctrie_isleaf(tmp) ? pctrie_toval(tmp) : NULL, - node->pn_clev); + node->pn_clev / PCTRIE_WIDTH); } } #endif /* DDB */ diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index 3c4ea9568108..f50f9e3605a1 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -107,10 +107,6 @@ _Static_assert(sizeof(rn_popmap_t) <= sizeof(int), #define VM_RADIX_FLAGS (VM_RADIX_ISLEAF) #define VM_RADIX_PAD VM_RADIX_FLAGS -/* Returns one unit associated with specified level. */ -#define VM_RADIX_UNITLEVEL(lev) \ - ((vm_pindex_t)1 << ((lev) * VM_RADIX_WIDTH)) - enum vm_radix_access { SMR, LOCKED, UNSERIALIZED }; struct vm_radix_node; @@ -119,7 +115,7 @@ typedef SMR_POINTER(struct vm_radix_node *) smrnode_t; struct vm_radix_node { vm_pindex_t rn_owner; /* Owner of record. */ rn_popmap_t rn_popmap; /* Valid children. */ - uint8_t rn_clev; /* Current level. */ + uint8_t rn_clev; /* Level * WIDTH. */ smrnode_t rn_child[VM_RADIX_COUNT]; /* Child nodes. */ }; @@ -135,21 +131,22 @@ static void vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v, static __inline int vm_radix_slot(vm_pindex_t index, uint16_t level) { - return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); + return ((index >> level) & VM_RADIX_MASK); } -/* Computes the key (index) with the low-order 'level' radix-digits zeroed. */ +/* 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) { - return (index & -VM_RADIX_UNITLEVEL(level)); + return (index & -((vm_pindex_t)VM_RADIX_COUNT << level)); } /* * Allocate a radix node. */ static struct vm_radix_node * -vm_radix_node_get(vm_pindex_t index, uint16_t clevel) +vm_radix_node_get(vm_pindex_t index, vm_pindex_t newind) { struct vm_radix_node *rnode; @@ -167,8 +164,20 @@ vm_radix_node_get(vm_pindex_t index, uint16_t clevel) VM_RADIX_NULL, UNSERIALIZED); rnode->rn_popmap = 0; } - rnode->rn_owner = vm_radix_trimkey(index, clevel + 1); - rnode->rn_clev = clevel; + + /* + * From the highest-order bit where the indexes differ, + * compute the highest level in the trie where they differ. Then, + * compute the least index of this subtrie. + */ + KASSERT(index != newind, ("%s: passing the same key value %jx", + __func__, (uintmax_t)index)); + _Static_assert(sizeof(long long) >= sizeof(vm_pindex_t), + "vm_pindex_t too wide"); + _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); return (rnode); } @@ -284,37 +293,18 @@ vm_radix_topage(struct vm_radix_node *rnode) * Make 'child' a child of 'rnode'. */ static __inline void -vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev, +vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, struct vm_radix_node *child, enum vm_radix_access access) { int slot; - slot = vm_radix_slot(index, clev); + slot = vm_radix_slot(index, rnode->rn_clev); 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 the level where two keys differ. - * It cannot accept 2 equal keys. - */ -static __inline uint16_t -vm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2) -{ - - KASSERT(index1 != index2, ("%s: passing the same key value %jx", - __func__, (uintmax_t)index1)); - CTASSERT(sizeof(long long) >= sizeof(vm_pindex_t)); - - /* - * From the highest-order bit where the indexes differ, - * compute the highest level in the trie where they differ. - */ - return ((flsll(index1 ^ index2) - 1) / VM_RADIX_WIDTH); -} - /* * Returns TRUE if it can be determined that key does not belong to the * specified rnode. Otherwise, returns FALSE. @@ -322,12 +312,8 @@ vm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2) static __inline bool vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx) { - - if (rnode->rn_clev < VM_RADIX_LIMIT) { - idx = vm_radix_trimkey(idx, rnode->rn_clev + 1); - return (idx != rnode->rn_owner); - } - return (false); + idx = vm_radix_trimkey(idx, rnode->rn_clev); + return (idx != rnode->rn_owner); } /* @@ -420,7 +406,6 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) struct vm_radix_node *leaf, *parent, *rnode; smrnode_t *parentp; int slot; - uint16_t clev; index = page->pindex; leaf = vm_radix_toleaf(page); @@ -437,8 +422,8 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) if (parent == NULL) rtree->rt_root = leaf; else - vm_radix_addnode(parent, index, - parent->rn_clev, leaf, LOCKED); + vm_radix_addnode(parent, index, leaf, + LOCKED); return (0); } newind = vm_radix_topage(rnode)->pindex; @@ -463,13 +448,12 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) */ parentp = (parent != NULL) ? &parent->rn_child[slot]: (smrnode_t *)&rtree->rt_root; - clev = vm_radix_keydiff(newind, index); - parent = vm_radix_node_get(index, clev); + parent = vm_radix_node_get(index, newind); if (parent == NULL) return (ENOMEM); /* These writes are not yet visible due to ordering. */ - vm_radix_addnode(parent, index, clev, leaf, UNSERIALIZED); - vm_radix_addnode(parent, newind, clev, rnode, UNSERIALIZED); + vm_radix_addnode(parent, index, leaf, UNSERIALIZED); + vm_radix_addnode(parent, newind, rnode, UNSERIALIZED); /* Serializing write to make the above visible. */ vm_radix_node_store(parentp, parent, LOCKED); return (0); @@ -808,14 +792,14 @@ DB_SHOW_COMMAND(radixnode, db_show_radixnode) rnode = (struct vm_radix_node *)addr; db_printf("radixnode %p, owner %jx, children popmap %04x, level %u:\n", (void *)rnode, (uintmax_t)rnode->rn_owner, rnode->rn_popmap, - rnode->rn_clev); + rnode->rn_clev / VM_RADIX_WIDTH); for (popmap = rnode->rn_popmap; popmap != 0; popmap ^= 1 << slot) { slot = ffs(popmap) - 1; tmp = vm_radix_node_load(&rnode->rn_child[slot], UNSERIALIZED); db_printf("slot: %d, val: %p, page: %p, clev: %d\n", slot, (void *)tmp, vm_radix_isleaf(tmp) ? vm_radix_topage(tmp) : NULL, - rnode->rn_clev); + rnode->rn_clev / VM_RADIX_WIDTH); } } #endif /* DDB */