From nobody Sun Jul 09 20:07:00 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 4QzdT04ZFFz4mNSF; Sun, 9 Jul 2023 20:07:00 +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 4QzdT046Bfz4PZm; Sun, 9 Jul 2023 20:07:00 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1688933220; 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=NO/lND5QITqyybQCjOo+G2S50+GawOtq7ThssV5oADA=; b=MHfG1mHeef1GIvfTpJQm8igzk7hOFqfcqz1QSmCvBnITBGtHoo1n7c5oBhF+haaIzKuL1u l11Zq09QvNBFSBZwZErwXhq8Zhsw5ogf5YHg+GNz/mt36C1KhmuUDAaNJAQQrcDYB1W8Aw Cp43EfvR5jL+3JAJ+2/KUEwoObbni7r0VlMq7phJbJPdIIFfcIaiqQhBeAQjJ8+PWb4tEx s38OrtY6LlFbHG+zqRd0Hu3pLUopo9zb6fUK+cHd5PjAp7Mu0YUg7CcZSs0Tb4sl7qU7rJ yqRwOh3+RXyO4+v2TPsE4xEUa5FcLIk7qVy1KOW/6mITMBi/VN92UMpKznvd5g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1688933220; 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=NO/lND5QITqyybQCjOo+G2S50+GawOtq7ThssV5oADA=; b=q+v1Dd991HpwKaCuDDH5emdru9mWmwvFbg5ZJ33ytxTIbu739fdeadh+V0Alxwqt+RBNBZ OiPKxPY1EMugGcPwdtF6QKCf9pOKFZLgeLzqN108jdBAOvc85m0I7L+0Tuf6ZVXjCJ6cqO cIMYKti3b23KHf5DZ23b6eEpwaBVfgpBK2vQTJyFcWLGxSE1UH1ZlPKA72yb/MSQQtwgmf MrPJ5x9UfjcxE4qT9Gm2pHPuuciu7Zwy+08sFT26aJHeMlVl9oWgQpfc9hrPXrznDMPygz lj3asLVPWWr4nM95yOR0AK78Puh86xgJcGJ3IB+SN0FnG8HVu2CakkgmySpgYg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1688933220; a=rsa-sha256; cv=none; b=vExBEn41LJ4isxLQjGHZddrsfRvJ/l3LKik86IjrYzR6Iuoy/aLj7EZ8us+XPLE0XQBYDI W0visNoPaOKKmKGD3xXMGHPc6cePV0P+aHOAXZRRxrwYM8LTcI7K5H+oFjvDEzedpbBZKW VbcAS0susVXKIdgsz75LcjpHsC0riuORVv8M2zOD6stQ241X5cFYLmq4n8/9Ud1xzWzUbd E4cOT11XutXC7BSB1WtHNLO6Hw96V/+QIg2N4PYWzlJfyB9MepOHVfcV6mX08miDxCx8g8 6DwuZxxgLVKT/ZNnyW6Jen0Q0r2iWNXcL2xuGuUl0PVpDr08dPS8sKgfE5xTzw== 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 4QzdT03BFlzGVF; Sun, 9 Jul 2023 20:07:00 +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 369K70H7016542; Sun, 9 Jul 2023 20:07:00 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 369K703B016541; Sun, 9 Jul 2023 20:07:00 GMT (envelope-from git) Date: Sun, 9 Jul 2023 20:07:00 GMT Message-Id: <202307092007.369K703B016541@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: 16e01c05c09e - main - radix_trie: avoid code duplication in insert 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: 16e01c05c09e4223103fa36e4057f7ed3b92146b Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=16e01c05c09e4223103fa36e4057f7ed3b92146b commit 16e01c05c09e4223103fa36e4057f7ed3b92146b Author: Doug Moore AuthorDate: 2023-07-09 20:06:02 +0000 Commit: Doug Moore CommitDate: 2023-07-09 20:06:02 +0000 radix_trie: avoid code duplication in insert Two cases in the insert routine are written differently, when they're really doing the same thing. Writing that case only once saves 208 bytes in the compiled vm_radix_insert code and reduces instructions executed by about 2%. Reviewed by: alc Tested by: pho Differential Revision: https://reviews.freebsd.org/D40807 --- sys/kern/subr_pctrie.c | 51 ++++++++++++++++++-------------------------------- sys/vm/vm_radix.c | 50 ++++++++++++++++++------------------------------- 2 files changed, 36 insertions(+), 65 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index cf09903556ec..ae8408a6e1ef 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -256,17 +256,16 @@ pctrie_toval(struct pctrie_node *node) } /* - * Adds the val as a child of the provided node. + * Make 'child' a child of 'node'. */ static __inline void -pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev, - uint64_t *val, enum pctrie_access access) +pctrie_addnode(struct pctrie_node *node, uint64_t index, uint16_t clev, + struct pctrie_node *child, enum pctrie_access access) { int slot; slot = pctrie_slot(index, clev); - pctrie_node_store(&node->pn_child[slot], - pctrie_toleaf(val), access); + 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)); @@ -361,13 +360,13 @@ int pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) { uint64_t index, newind; - struct pctrie_node *node, *tmp; + struct pctrie_node *leaf, *node, *tmp; smr_pctnode_t *parentp; - uint64_t *m; int slot; uint16_t clev; index = *val; + leaf = pctrie_toleaf(val); /* * The owner of record for root is not really important because it @@ -375,58 +374,44 @@ pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) */ node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); if (node == NULL) { - ptree->pt_root = (uintptr_t)pctrie_toleaf(val); + ptree->pt_root = (uintptr_t)leaf; return (0); } - parentp = (smr_pctnode_t *)&ptree->pt_root; - for (;;) { + for (parentp = (smr_pctnode_t *)&ptree->pt_root;; node = tmp) { if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m == index) + newind = *pctrie_toval(node); + if (newind == index) panic("%s: key %jx is already present", __func__, (uintmax_t)index); - clev = pctrie_keydiff(*m, index); - tmp = pctrie_node_get(ptree, allocfn, index, clev); - if (tmp == NULL) - return (ENOMEM); - /* These writes are not yet visible due to ordering. */ - pctrie_addval(tmp, index, clev, val, - PCTRIE_UNSERIALIZED); - pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED); - /* Synchronize to make leaf visible. */ - pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); - return (0); - } else if (pctrie_keybarr(node, index)) break; + } else if (pctrie_keybarr(node, index)) { + newind = node->pn_owner; + break; + } slot = pctrie_slot(index, node->pn_clev); parentp = &node->pn_child[slot]; tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); if (tmp == NULL) { - pctrie_addval(node, index, node->pn_clev, val, + pctrie_addnode(node, index, node->pn_clev, leaf, PCTRIE_LOCKED); return (0); } - node = tmp; } /* * A new node is needed because the right insertion level is reached. * Setup the new intermediate node and add the 2 children: the - * new object and the older edge. + * new object and the older edge or object. */ - newind = node->pn_owner; clev = pctrie_keydiff(newind, index); tmp = pctrie_node_get(ptree, allocfn, index, clev); if (tmp == NULL) return (ENOMEM); - slot = pctrie_slot(newind, clev); /* These writes are not yet visible due to ordering. */ - pctrie_addval(tmp, index, clev, val, PCTRIE_UNSERIALIZED); - pctrie_node_store(&tmp->pn_child[slot], node, PCTRIE_UNSERIALIZED); - tmp->pn_popmap ^= 1 << slot; + pctrie_addnode(tmp, index, clev, leaf, PCTRIE_UNSERIALIZED); + pctrie_addnode(tmp, newind, clev, node, PCTRIE_UNSERIALIZED); /* Synchronize to make the above visible. */ pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); - return (0); } diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index d2cd2c2536fd..f6bdda70539b 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -281,17 +281,16 @@ vm_radix_topage(struct vm_radix_node *rnode) } /* - * Adds the page as a child of the provided node. + * Make 'child' a child of 'rnode'. */ static __inline void -vm_radix_addpage(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev, - vm_page_t page, enum vm_radix_access access) +vm_radix_addnode(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev, + struct vm_radix_node *child, enum vm_radix_access access) { int slot; slot = vm_radix_slot(index, clev); - vm_radix_node_store(&rnode->rn_child[slot], - vm_radix_toleaf(page), access); + 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)); @@ -401,13 +400,13 @@ int vm_radix_insert(struct vm_radix *rtree, vm_page_t page) { vm_pindex_t index, newind; - struct vm_radix_node *rnode, *tmp; + struct vm_radix_node *leaf, *rnode, *tmp; smrnode_t *parentp; - vm_page_t m; int slot; uint16_t clev; index = page->pindex; + leaf = vm_radix_toleaf(page); /* * The owner of record for root is not really important because it @@ -415,57 +414,44 @@ vm_radix_insert(struct vm_radix *rtree, vm_page_t page) */ rnode = vm_radix_root_load(rtree, LOCKED); if (rnode == NULL) { - rtree->rt_root = (uintptr_t)vm_radix_toleaf(page); + rtree->rt_root = (uintptr_t)leaf; return (0); } - parentp = (smrnode_t *)&rtree->rt_root; - for (;;) { + for (parentp = (smrnode_t *)&rtree->rt_root;; rnode = tmp) { if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex == index) + newind = vm_radix_topage(rnode)->pindex; + if (newind == index) panic("%s: key %jx is already present", __func__, (uintmax_t)index); - clev = vm_radix_keydiff(m->pindex, index); - tmp = vm_radix_node_get(index, clev); - if (tmp == NULL) - return (ENOMEM); - /* These writes are not yet visible due to ordering. */ - vm_radix_addpage(tmp, index, clev, page, UNSERIALIZED); - vm_radix_addpage(tmp, m->pindex, clev, m, UNSERIALIZED); - /* Synchronize to make leaf visible. */ - vm_radix_node_store(parentp, tmp, LOCKED); - return (0); - } else if (vm_radix_keybarr(rnode, index)) break; + } else if (vm_radix_keybarr(rnode, index)) { + newind = rnode->rn_owner; + break; + } slot = vm_radix_slot(index, rnode->rn_clev); parentp = &rnode->rn_child[slot]; tmp = vm_radix_node_load(parentp, LOCKED); if (tmp == NULL) { - vm_radix_addpage(rnode, index, rnode->rn_clev, page, + vm_radix_addnode(rnode, index, rnode->rn_clev, leaf, LOCKED); return (0); } - rnode = tmp; } /* * A new node is needed because the right insertion level is reached. * Setup the new intermediate node and add the 2 children: the - * new object and the older edge. + * new object and the older edge or object. */ - newind = rnode->rn_owner; clev = vm_radix_keydiff(newind, index); tmp = vm_radix_node_get(index, clev); if (tmp == NULL) return (ENOMEM); - slot = vm_radix_slot(newind, clev); /* These writes are not yet visible due to ordering. */ - vm_radix_addpage(tmp, index, clev, page, UNSERIALIZED); - vm_radix_node_store(&tmp->rn_child[slot], rnode, UNSERIALIZED); - tmp->rn_popmap ^= 1 << slot; + vm_radix_addnode(tmp, index, clev, leaf, UNSERIALIZED); + vm_radix_addnode(tmp, newind, clev, rnode, UNSERIALIZED); /* Serializing write to make the above visible. */ vm_radix_node_store(parentp, tmp, LOCKED); - return (0); }