From nobody Mon Sep 11 17:21:18 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 4RktmP41Gjz4sSFL; Mon, 11 Sep 2023 17:21:25 +0000 (UTC) (envelope-from rpokala@freebsd.org) Received: from smtp.freebsd.org (smtp.freebsd.org [96.47.72.83]) (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 "smtp.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4RktmP3s9Mz4R9S; Mon, 11 Sep 2023 17:21:25 +0000 (UTC) (envelope-from rpokala@freebsd.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1694452885; 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: in-reply-to:in-reply-to:references:references; bh=tXPD1TIDtjVituhKSQv8kr1UIWmUC4FUN8vDbGj9gc8=; b=cmQA7gOrrW8iX19sTaQ42YldanlxORvVBRLUmp2g1a40aQKPLXsq7uTqa4hHMCeLTatvMJ oXw6lUjx4yOAElePiCUy9H5ZBPqTybEaF9a2gpaAlV3hg6woTTE2JLHTQYQJjlzIl2Kj89 ZRipi07F/pTAFy5o7Pl3mcBrbZnYzAooHJO3dn/V1IzxqBFfMo/BmUyIKHFSKVW79f18Yb WE2d7Lzf/3nt8afXWW2Z+lWqyWxFH6A+AU+MovGYPdBXGYms6LhqmENDxCKsRn+vqvCDW7 rtYWCeIfjp3osjm+SmhapxbaneXNayY7SEmd8QWPpxIxEqol0rQmqA3PuL3O+w== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1694452885; a=rsa-sha256; cv=none; b=YZx0Seio0e2AkmXNmI7SMsGknvD7b2tPsPFT/1H9V/z4kswN3bHnbj8CzcLQZyZCi8z8fx KAD/Y5tNbzan10FAx6gACdwgoXM1k6a/YP+z/Uc3L4IOaZPYfUkVj2BO/jePS582/5pUGa q6+GbMcfaafyneGiJC1V0Qxtz3nbjmnkq5asRc5tBRWyba1H5y6LERgsYEkHBUGJdMWEpz y0WuopI3V4TwQlIv5nbQalWWFMzAwhhPQ0/TF9DZXjqeHeQjudjlRmA7wSfy/+40FWp7Xu ObuSRgEILG9ONvwM/xbnXPdZsGCKwjVZuhMxZ9bx60itCrI37hM0DQlaJVszyw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1694452885; 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: in-reply-to:in-reply-to:references:references; bh=tXPD1TIDtjVituhKSQv8kr1UIWmUC4FUN8vDbGj9gc8=; b=Ms5ua284aHpQ3WeO195coVpEUiJv9FJ8wBLgmJDbyTked6sgQJfxzFKyBlouH32pcmLf7V pKNHv2xXkQdyVGiL7Cc0GyoQAxsRO13IEZ7b8eQZ6q5FdtcO3cewuIIfNzfTXXV+Ng3Yrf zp7P11P3sLylzNHOrbo5U8S4Y+KOmkWZiGsE7RAgzzRhMp74UnLcPA+XYqvqsEqP86mDIL A2VpEoIg8IGpd9gjKMQJQNMGD5lMQQaJKOf8RqvAw/W6BIyf42OdaAOFG8JrvhEO0sU6/3 bsV6OYsYUyl/R3iLGq4T6NlmSFdliHX74wTsjfZ876nq3yWTjJmrrYodeQuFEA== Received: from [192.168.1.12] (c-98-248-120-44.hsd1.ca.comcast.net [98.248.120.44]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) (Authenticated sender: rpokala) by smtp.freebsd.org (Postfix) with ESMTPSA id 4RktmN5BMGz16m9; Mon, 11 Sep 2023 17:21:24 +0000 (UTC) (envelope-from rpokala@freebsd.org) User-Agent: Microsoft-MacOutlook/16.76.23082700 Date: Mon, 11 Sep 2023 10:21:18 -0700 Subject: Re: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use pctrie code" From: Ravi Pokala To: Doug Moore , , , Message-ID: <25DD750F-38F2-4151-9E34-350844CE705C@panasas.com> Thread-Topic: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use pctrie code" References: <202309110835.38B8Zl9t059626@gitrepo.freebsd.org> In-Reply-To: <202309110835.38B8Zl9t059626@gitrepo.freebsd.org> 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: quoted-printable Hi Doug, > Revert "radix_trie: have vm_radix use pctrie code" That's "what", not "why". Why are you reverting the change? Thanks, Ravi (rpokala@) =EF=BB=BF-----Original Message----- From: > on behalf of Doug Moore > Date: Monday, September 11, 2023 at 01:35 To: >, >, > Subject: git: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use p= ctrie code" The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=3D6cec93da46c4a91a042b0be4888440= 52c0f8985a commit 6cec93da46c4a91a042b0be488844052c0f8985a Author: Doug Moore > AuthorDate: 2023-09-11 08:34:46 +0000 Commit: Doug Moore > CommitDate: 2023-09-11 08:35:36 +0000 Revert "radix_trie: have vm_radix use pctrie code" This reverts commit a494d30465f21e8cb014a5c788a43001397325d7. --- sys/vm/_vm_radix.h | 9 +- sys/vm/vm_radix.c | 696 +++++++++++++++++++++++++++++++++++++++++++++++++++= +- sys/vm/vm_radix.h | 113 ++------- 3 files changed, 709 insertions(+), 109 deletions(-) diff --git a/sys/vm/_vm_radix.h b/sys/vm/_vm_radix.h index 2d9b05c7b52a..01eb25a9dccf 100644 --- a/sys/vm/_vm_radix.h +++ b/sys/vm/_vm_radix.h @@ -31,13 +31,16 @@ #ifndef __VM_RADIX_H_ #define __VM_RADIX_H_ -#include +/* + * Radix tree node. + */ +struct vm_radix_node; /* - * Radix tree + * Radix tree root. */ struct vm_radix { - struct pctrie rt_trie; + struct vm_radix_node *rt_root; }; #endif /* !__VM_RADIX_H_ */ diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index b8c693eca66f..768a56ed76f7 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -54,26 +54,302 @@ #include "opt_ddb.h" #include -#include +#include +#include +#include +#include +#include +#include +#include #include #include +#include +#include #include #include +#ifdef DDB +#include +#endif + +/* + * These widths should allow the pointers to a node's children to fit with= in + * a single cache line. The extra levels from a narrow width should not be + * a problem thanks to path compression. + */ +#ifdef __LP64__ +#define VM_RADIX_WIDTH 4 +#else +#define VM_RADIX_WIDTH 3 +#endif + +#define VM_RADIX_COUNT (1 << VM_RADIX_WIDTH) +#define VM_RADIX_MASK (VM_RADIX_COUNT - 1) +#define VM_RADIX_LIMIT \ + (howmany(sizeof(vm_pindex_t) * NBBY, VM_RADIX_WIDTH) - 1) + +#if VM_RADIX_WIDTH =3D=3D 3 +typedef uint8_t rn_popmap_t; +#elif VM_RADIX_WIDTH =3D=3D 4 +typedef uint16_t rn_popmap_t; +#elif VM_RADIX_WIDTH =3D=3D 5 +typedef uint32_t rn_popmap_t; +#else +#error Unsupported width +#endif +_Static_assert(sizeof(rn_popmap_t) <=3D sizeof(int), + "rn_popmap_t too wide"); + +/* Set of all flag bits stored in node pointers. */ +#define VM_RADIX_FLAGS (VM_RADIX_ISLEAF) +#define VM_RADIX_PAD VM_RADIX_FLAGS + +enum vm_radix_access { SMR, LOCKED, UNSERIALIZED }; + +struct vm_radix_node; +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; /* Level * WIDTH. */ + smrnode_t rn_child[VM_RADIX_COUNT]; /* Child nodes. */ +}; + static uma_zone_t vm_radix_node_zone; -smr_t vm_radix_smr; +static smr_t vm_radix_smr; + +static void vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v, + enum vm_radix_access access); -void * -vm_radix_node_alloc(struct pctrie *ptree) +/* + * Map index to an array position for the children of rnode, + */ +static __inline int +vm_radix_slot(struct vm_radix_node *rnode, vm_pindex_t index) { - return (uma_zalloc_smr(vm_radix_node_zone, M_NOWAIT)); + return ((index >> rnode->rn_clev) & VM_RADIX_MASK); } -void -vm_radix_node_free(struct pctrie *ptree, void *node) +/* + * 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= ) +{ + index =3D (index - rnode->rn_owner) >> rnode->rn_clev; + if (index >=3D VM_RADIX_COUNT) + return (true); + *slot =3D index; + return (false); +} + +/* + * Allocate a radix node. + */ +static struct vm_radix_node * +vm_radix_node_get(vm_pindex_t index, vm_pindex_t newind) +{ + struct vm_radix_node *rnode; + + rnode =3D uma_zalloc_smr(vm_radix_node_zone, M_NOWAIT); + if (rnode =3D=3D NULL) + return (NULL); + + /* + * We want to clear the last child pointer after the final section + * has exited so lookup can not return false negatives. It is done + * here because it will be cache-cold in the dtor callback. + */ + if (rnode->rn_popmap !=3D 0) { + vm_radix_node_store(&rnode->rn_child[ffs(rnode->rn_popmap) - 1], + VM_RADIX_NULL, UNSERIALIZED); + rnode->rn_popmap =3D 0; + } + + /* + * 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 !=3D newind, ("%s: passing the same key value %jx", + __func__, (uintmax_t)index)); + _Static_assert(sizeof(long long) >=3D sizeof(vm_pindex_t), + "vm_pindex_t too wide"); + _Static_assert(sizeof(vm_pindex_t) * NBBY <=3D + (1 << (sizeof(rnode->rn_clev) * NBBY)), "rn_clev too narrow"); + rnode->rn_clev =3D rounddown(flsll(index ^ newind) - 1, VM_RADIX_WIDTH); + rnode->rn_owner =3D VM_RADIX_COUNT; + rnode->rn_owner =3D index & -(rnode->rn_owner << rnode->rn_clev); + return (rnode); +} + +/* + * Free radix node. + */ +static __inline void +vm_radix_node_put(struct vm_radix_node *rnode) +{ +#ifdef INVARIANTS + int slot; + + KASSERT(powerof2(rnode->rn_popmap), + ("vm_radix_node_put: rnode %p has too many children %04x", rnode, + rnode->rn_popmap)); + for (slot =3D 0; slot < VM_RADIX_COUNT; slot++) { + if ((rnode->rn_popmap & (1 << slot)) !=3D 0) + continue; + KASSERT(smr_unserialized_load(&rnode->rn_child[slot], true) =3D=3D + VM_RADIX_NULL, + ("vm_radix_node_put: rnode %p has a child", rnode)); + } +#endif + uma_zfree_smr(vm_radix_node_zone, rnode); +} + +/* + * Fetch a node pointer from a slot in another node. + */ +static __inline struct vm_radix_node * +vm_radix_node_load(smrnode_t *p, enum vm_radix_access access) +{ + + switch (access) { + case UNSERIALIZED: + return (smr_unserialized_load(p, true)); + case LOCKED: + return (smr_serialized_load(p, true)); + case SMR: + return (smr_entered_load(p, vm_radix_smr)); + } + __assert_unreachable(); +} + +static __inline void +vm_radix_node_store(smrnode_t *p, struct vm_radix_node *v, + enum vm_radix_access access) +{ + + switch (access) { + case UNSERIALIZED: + smr_unserialized_store(p, v, true); + break; + case LOCKED: + smr_serialized_store(p, v, true); + break; + case SMR: + panic("vm_radix_node_store: Not supported in smr section."); + } +} + +/* + * Get the root node for a radix tree. + */ +static __inline struct vm_radix_node * +vm_radix_root_load(struct vm_radix *rtree, enum vm_radix_access access) +{ + + return (vm_radix_node_load((smrnode_t *)&rtree->rt_root, access)); +} + +/* + * Set the root node for a radix tree. + */ +static __inline void +vm_radix_root_store(struct vm_radix *rtree, struct vm_radix_node *rnode, + enum vm_radix_access access) +{ + + vm_radix_node_store((smrnode_t *)&rtree->rt_root, rnode, access); +} + +/* + * Returns TRUE if the specified radix node is a leaf and FALSE otherwise. + */ +static __inline bool +vm_radix_isleaf(struct vm_radix_node *rnode) +{ + + return (((uintptr_t)rnode & VM_RADIX_ISLEAF) !=3D 0); +} + +/* + * Returns page cast to radix node with leaf bit set. + */ +static __inline struct vm_radix_node * +vm_radix_toleaf(vm_page_t page) +{ + return ((struct vm_radix_node *)((uintptr_t)page | VM_RADIX_ISLEAF)); +} + +/* + * Returns the associated page extracted from rnode. + */ +static __inline vm_page_t +vm_radix_topage(struct vm_radix_node *rnode) +{ + + return ((vm_page_t)((uintptr_t)rnode & ~VM_RADIX_FLAGS)); +} + +/* + * Make 'child' a child of 'rnode'. + */ +static __inline void +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 =3D vm_radix_slot(rnode, index); + vm_radix_node_store(&rnode->rn_child[slot], child, access); + rnode->rn_popmap ^=3D 1 << slot; + KASSERT((rnode->rn_popmap & (1 << slot)) !=3D 0, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); +} + +/* + * Internal helper for vm_radix_reclaim_allnodes(). + * This function is recursive. + */ +static void +vm_radix_reclaim_allnodes_int(struct vm_radix_node *rnode) +{ + struct vm_radix_node *child; + int slot; + + while (rnode->rn_popmap !=3D 0) { + slot =3D ffs(rnode->rn_popmap) - 1; + child =3D vm_radix_node_load(&rnode->rn_child[slot], + UNSERIALIZED); + KASSERT(child !=3D VM_RADIX_NULL, + ("%s: bad popmap slot %d in rnode %p", + __func__, slot, rnode)); + if (!vm_radix_isleaf(child)) + vm_radix_reclaim_allnodes_int(child); + rnode->rn_popmap ^=3D 1 << slot; + vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL, + UNSERIALIZED); + } + vm_radix_node_put(rnode); +} + +/* + * radix node zone initializer. + */ +static int +vm_radix_zone_init(void *mem, int size, int flags) { - uma_zfree_smr(vm_radix_node_zone, node); + struct vm_radix_node *rnode; + + rnode =3D mem; + rnode->rn_popmap =3D 0; + for (int i =3D 0; i < nitems(rnode->rn_child); i++) + vm_radix_node_store(&rnode->rn_child[i], VM_RADIX_NULL, + UNSERIALIZED); + return (0); } #ifndef UMA_MD_SMALL_ALLOC @@ -107,14 +383,412 @@ void vm_radix_zinit(void) { - vm_radix_node_zone =3D uma_zcreate("RADIX NODE", pctrie_node_size(), - NULL, NULL, pctrie_zone_init, NULL, - PCTRIE_PAD, UMA_ZONE_VM | UMA_ZONE_SMR); + vm_radix_node_zone =3D uma_zcreate("RADIX NODE", + sizeof(struct vm_radix_node), NULL, NULL, vm_radix_zone_init, NULL, + VM_RADIX_PAD, UMA_ZONE_VM | UMA_ZONE_SMR); vm_radix_smr =3D uma_zone_get_smr(vm_radix_node_zone); } +/* + * Inserts the key-value pair into the trie. + * Panics if the key already exists. + */ +int +vm_radix_insert(struct vm_radix *rtree, vm_page_t page) +{ + vm_pindex_t index, newind; + struct vm_radix_node *leaf, *parent, *rnode; + smrnode_t *parentp; + int slot; + + index =3D page->pindex; + leaf =3D vm_radix_toleaf(page); + + /* + * The owner of record for root is not really important because it + * will never be used. + */ + rnode =3D vm_radix_root_load(rtree, LOCKED); + parent =3D NULL; + for (;;) { + if (vm_radix_isleaf(rnode)) { + if (rnode =3D=3D VM_RADIX_NULL) { + if (parent =3D=3D NULL) + rtree->rt_root =3D leaf; + else + vm_radix_addnode(parent, index, leaf, + LOCKED); + return (0); + } + newind =3D vm_radix_topage(rnode)->pindex; + if (newind =3D=3D index) + panic("%s: key %jx is already present", + __func__, (uintmax_t)index); + break; + } + if (vm_radix_keybarr(rnode, index, &slot)) { + newind =3D rnode->rn_owner; + break; + } + parent =3D rnode; + rnode =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + + /* + * 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 or object. + */ + parentp =3D (parent !=3D NULL) ? &parent->rn_child[slot]: + (smrnode_t *)&rtree->rt_root; + parent =3D vm_radix_node_get(index, newind); + if (parent =3D=3D NULL) + return (ENOMEM); + /* These writes are not yet visible due to ordering. */ + 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); +} + +/* + * Returns the value stored at the index. If the index is not present, + * NULL is returned. + */ +static __always_inline vm_page_t +_vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, + enum vm_radix_access access) +{ + struct vm_radix_node *rnode; + vm_page_t m; + int slot; + + rnode =3D vm_radix_root_load(rtree, access); + for (;;) { + if (vm_radix_isleaf(rnode)) { + if ((m =3D vm_radix_topage(rnode)) !=3D NULL && + m->pindex =3D=3D index) + return (m); + break; + } + if (vm_radix_keybarr(rnode, index, &slot)) + break; + rnode =3D vm_radix_node_load(&rnode->rn_child[slot], access); + } + return (NULL); +} + +/* + * Returns the value stored at the index assuming there is an external loc= k. + * + * If the index is not present, NULL is returned. + */ +vm_page_t +vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) +{ + + return _vm_radix_lookup(rtree, index, LOCKED); +} + +/* + * Returns the value stored at the index without requiring an external loc= k. + * + * If the index is not present, NULL is returned. + */ +vm_page_t +vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t index) +{ + vm_page_t m; + + smr_enter(vm_radix_smr); + m =3D _vm_radix_lookup(rtree, index, SMR); + smr_exit(vm_radix_smr); + + return (m); +} + +/* + * Returns the page with the least pindex that is greater than or equal to= the + * specified pindex, or NULL if there are no such pages. + * + * Requires that access be externally synchronized by a lock. + */ +vm_page_t +vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) +{ + struct vm_radix_node *rnode, *succ; + vm_page_t m; + int slot; + + /* + * Descend the trie as if performing an ordinary lookup for the page + * with the specified pindex. However, unlike an ordinary lookup, as we + * descend the trie, we use "succ" to remember the last branching-off + * point, that is, the interior node under which the page with the least + * pindex that is both outside our current path down the trie and more + * than the specified pindex resides. (The node's popmap makes it fast + * and easy to recognize a branching-off point.) If our ordinary lookup + * fails to yield a page with a pindex that is greater than or equal to + * the specified pindex, then we will exit this loop and perform a + * lookup starting from "succ". If "succ" is not NULL, then that lookup + * is guaranteed to succeed. + */ + rnode =3D vm_radix_root_load(rtree, LOCKED); + succ =3D NULL; + for (;;) { + if (vm_radix_isleaf(rnode)) { + if ((m =3D vm_radix_topage(rnode)) !=3D NULL && + m->pindex >=3D index) + return (m); + break; + } + 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 + * is the answer. + */ + if (rnode->rn_owner > index) + succ =3D rnode; + break; + } + + /* + * Just in case the next search step leads to a subtree of all + * pages with pindex < index, check popmap to see if a next + * bigger step, to a subtree of all pages with pindex > index, + * is available. If so, remember to restart the search here. + */ + if ((rnode->rn_popmap >> slot) > 1) + succ =3D rnode; + rnode =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + + /* + * Restart the search from the last place visited in the subtree that + * included some pages with pindex > index, if there was such a place. + */ + if (succ =3D=3D NULL) + return (NULL); + if (succ !=3D rnode) { + /* + * Take a step to the next bigger sibling of the node chosen + * last time. In that subtree, all pages have pindex > index. + */ + slot =3D vm_radix_slot(succ, index) + 1; + KASSERT((succ->rn_popmap >> slot) !=3D 0, + ("%s: no popmap siblings past slot %d in node %p", + __func__, slot, succ)); + slot +=3D ffs(succ->rn_popmap >> slot) - 1; + succ =3D vm_radix_node_load(&succ->rn_child[slot], LOCKED); + } + + /* + * Find the page in the subtree rooted at "succ" with the least pindex. + */ + while (!vm_radix_isleaf(succ)) { + KASSERT(succ->rn_popmap !=3D 0, + ("%s: no popmap children in node %p", __func__, succ)); + slot =3D ffs(succ->rn_popmap) - 1; + succ =3D vm_radix_node_load(&succ->rn_child[slot], LOCKED); + } + return (vm_radix_topage(succ)); +} + +/* + * Returns the page with the greatest pindex that is less than or equal to= the + * specified pindex, or NULL if there are no such pages. + * + * Requires that access be externally synchronized by a lock. + */ +vm_page_t +vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) +{ + struct vm_radix_node *pred, *rnode; + vm_page_t m; + int slot; + + /* + * Mirror the implementation of vm_radix_lookup_ge, described above. + */ + rnode =3D vm_radix_root_load(rtree, LOCKED); + pred =3D NULL; + for (;;) { + if (vm_radix_isleaf(rnode)) { + if ((m =3D vm_radix_topage(rnode)) !=3D NULL && + m->pindex <=3D index) + return (m); + break; + } + if (vm_radix_keybarr(rnode, index, &slot)) { + if (rnode->rn_owner < index) + pred =3D rnode; + break; + } + if ((rnode->rn_popmap & ((1 << slot) - 1)) !=3D 0) + pred =3D rnode; + rnode =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + if (pred =3D=3D NULL) + return (NULL); + if (pred !=3D rnode) { + slot =3D vm_radix_slot(pred, index); + KASSERT((pred->rn_popmap & ((1 << slot) - 1)) !=3D 0, + ("%s: no popmap siblings before slot %d in node %p", + __func__, slot, pred)); + slot =3D fls(pred->rn_popmap & ((1 << slot) - 1)) - 1; + pred =3D vm_radix_node_load(&pred->rn_child[slot], LOCKED); + } + while (!vm_radix_isleaf(pred)) { + KASSERT(pred->rn_popmap !=3D 0, + ("%s: no popmap children in node %p", __func__, pred)); + slot =3D fls(pred->rn_popmap) - 1; + pred =3D vm_radix_node_load(&pred->rn_child[slot], LOCKED); + } + return (vm_radix_topage(pred)); +} + +/* + * Remove the specified index from the trie, and return the value stored a= t + * that index. If the index is not present, return NULL. + */ +vm_page_t +vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) +{ + struct vm_radix_node *child, *parent, *rnode; + vm_page_t m; + int slot; + + rnode =3D NULL; + child =3D vm_radix_root_load(rtree, LOCKED); + for (;;) { + if (vm_radix_isleaf(child)) + break; + parent =3D rnode; + rnode =3D child; + slot =3D vm_radix_slot(rnode, index); + child =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + if ((m =3D vm_radix_topage(child)) =3D=3D NULL || m->pindex !=3D index) + return (NULL); + if (rnode =3D=3D NULL) { + vm_radix_root_store(rtree, VM_RADIX_NULL, LOCKED); + return (m); + } + KASSERT((rnode->rn_popmap & (1 << slot)) !=3D 0, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); + rnode->rn_popmap ^=3D 1 << slot; + vm_radix_node_store(&rnode->rn_child[slot], VM_RADIX_NULL, LOCKED); + if (!powerof2(rnode->rn_popmap)) + return (m); + KASSERT(rnode->rn_popmap !=3D 0, ("%s: bad popmap all zeroes", __func__)); + slot =3D ffs(rnode->rn_popmap) - 1; + child =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + KASSERT(child !=3D VM_RADIX_NULL, + ("%s: bad popmap slot %d in rnode %p", __func__, slot, rnode)); + if (parent =3D=3D NULL) + vm_radix_root_store(rtree, child, LOCKED); + else { + slot =3D vm_radix_slot(parent, index); + KASSERT(rnode =3D=3D + vm_radix_node_load(&parent->rn_child[slot], LOCKED), + ("%s: invalid child value", __func__)); + vm_radix_node_store(&parent->rn_child[slot], child, LOCKED); + } + /* + * The child is still valid and we can not zero the + * pointer until all smr references are gone. + */ + vm_radix_node_put(rnode); + return (m); +} + +/* + * Remove and free all the nodes from the radix tree. + * This function is recursive but there is a tight control on it as the + * maximum depth of the tree is fixed. + */ +void +vm_radix_reclaim_allnodes(struct vm_radix *rtree) +{ + struct vm_radix_node *root; + + root =3D vm_radix_root_load(rtree, LOCKED); + if (root =3D=3D VM_RADIX_NULL) + return; + vm_radix_root_store(rtree, VM_RADIX_NULL, UNSERIALIZED); + if (!vm_radix_isleaf(root)) + vm_radix_reclaim_allnodes_int(root); +} + +/* + * Replace an existing page in the trie with another one. + * Panics if there is not an old page in the trie at the new page's index. + */ +vm_page_t +vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) +{ + struct vm_radix_node *leaf, *parent, *rnode; + vm_page_t m; + vm_pindex_t index; + int slot; + + leaf =3D vm_radix_toleaf(newpage); + index =3D newpage->pindex; + rnode =3D vm_radix_root_load(rtree, LOCKED); + parent =3D NULL; + for (;;) { + if (vm_radix_isleaf(rnode)) { + if ((m =3D vm_radix_topage(rnode)) !=3D NULL && + m->pindex =3D=3D index) { + if (parent =3D=3D NULL) + rtree->rt_root =3D leaf; + else + vm_radix_node_store( + &parent->rn_child[slot], leaf, + LOCKED); + return (m); + } + break; + } + if (vm_radix_keybarr(rnode, index, &slot)) + break; + parent =3D rnode; + rnode =3D vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + panic("%s: original replacing page not found", __func__); +} + void vm_radix_wait(void) { uma_zwait(vm_radix_node_zone); } + +#ifdef DDB +/* + * Show details about the given radix node. + */ +DB_SHOW_COMMAND(radixnode, db_show_radixnode) +{ + struct vm_radix_node *rnode, *tmp; + int slot; + rn_popmap_t popmap; + + if (!have_addr) + return; + rnode =3D (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 / VM_RADIX_WIDTH); + for (popmap =3D rnode->rn_popmap; popmap !=3D 0; popmap ^=3D 1 << slot) { + slot =3D ffs(popmap) - 1; + tmp =3D 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 / VM_RADIX_WIDTH); + } +} +#endif /* DDB */ diff --git a/sys/vm/vm_radix.h b/sys/vm/vm_radix.h index a332618fc0e6..231edda65102 100644 --- a/sys/vm/vm_radix.h +++ b/sys/vm/vm_radix.h @@ -34,113 +34,36 @@ #include #ifdef _KERNEL -#include -#include +int vm_radix_insert(struct vm_radix *rtree, vm_page_t page); void vm_radix_wait(void); +vm_page_t vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index); +vm_page_t vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index); +vm_page_t vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index); +vm_page_t vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t ind= ex); +void vm_radix_reclaim_allnodes(struct vm_radix *rtree); +vm_page_t vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index); +vm_page_t vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage); void vm_radix_zinit(void); -void *vm_radix_node_alloc(struct pctrie *ptree); -void vm_radix_node_free(struct pctrie *ptree, void *node); -extern smr_t vm_radix_smr; - -static __inline void -vm_radix_init(struct vm_radix *rtree) -{ - pctrie_init(&rtree->rt_trie); -} - -static __inline bool -vm_radix_is_empty(struct vm_radix *rtree) -{ - return (pctrie_is_empty(&rtree->rt_trie)); -} - -PCTRIE_DEFINE_SMR(VM_RADIX, vm_page, pindex, vm_radix_node_alloc, vm_radix= _node_free, - vm_radix_smr); /* - * Inserts the key-value pair into the trie. - * Panics if the key already exists. + * Each search path in the trie terminates at a leaf, which is a pointer t= o a + * page marked with a set 1-bit. A leaf may be associated with a null poin= ter + * to indicate no page there. */ -static __inline int -vm_radix_insert(struct vm_radix *rtree, vm_page_t page) -{ - return (VM_RADIX_PCTRIE_INSERT(&rtree->rt_trie, page)); -} - -/* - * Returns the value stored at the index assuming there is an external loc= k. - * - * If the index is not present, NULL is returned. - */ -static __inline vm_page_t -vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) -{ - return (VM_RADIX_PCTRIE_LOOKUP(&rtree->rt_trie, index)); -} - -/* - * Returns the value stored at the index without requiring an external loc= k. - * - * If the index is not present, NULL is returned. - */ -static __inline vm_page_t -vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t index) -{ - return (VM_RADIX_PCTRIE_LOOKUP_UNLOCKED(&rtree->rt_trie, index)); -} +#define VM_RADIX_ISLEAF 0x1 +#define VM_RADIX_NULL (struct vm_radix_node *)VM_RADIX_ISLEAF -/* - * Returns the page with the least pindex that is greater than or equal to= the - * specified pindex, or NULL if there are no such pages. - * - * Requires that access be externally synchronized by a lock. - */ -static __inline vm_page_t -vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) -{ - return (VM_RADIX_PCTRIE_LOOKUP_GE(&rtree->rt_trie, index)); -} - -/* - * Returns the page with the greatest pindex that is less than or equal to= the - * specified pindex, or NULL if there are no such pages. - * - * Requires that access be externally synchronized by a lock. - */ -static __inline vm_page_t -vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) -{ - return (VM_RADIX_PCTRIE_LOOKUP_LE(&rtree->rt_trie, index)); -} - -/* - * Remove the specified index from the trie, and return the value stored a= t - * that index. If the index is not present, return NULL. - */ -static __inline vm_page_t -vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) -{ - return (VM_RADIX_PCTRIE_REMOVE_LOOKUP(&rtree->rt_trie, index)); -} - -/* - * Remove and free all the nodes from the radix tree. - */ static __inline void -vm_radix_reclaim_allnodes(struct vm_radix *rtree) +vm_radix_init(struct vm_radix *rtree) { - VM_RADIX_PCTRIE_RECLAIM(&rtree->rt_trie); + rtree->rt_root =3D VM_RADIX_NULL; } -/* - * Replace an existing page in the trie with another one. - * Panics if there is not an old page in the trie at the new page's index. - */ -static __inline vm_page_t -vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) +static __inline bool +vm_radix_is_empty(struct vm_radix *rtree) { - return (VM_RADIX_PCTRIE_REPLACE(&rtree->rt_trie, newpage)); + return (rtree->rt_root =3D=3D VM_RADIX_NULL); } #endif /* _KERNEL */