From nobody Mon Sep 11 17:36:07 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 4Rkv5S2h0Dz4sbDS; Mon, 11 Sep 2023 17:36:12 +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 4Rkv5S2GDSz4WcR; Mon, 11 Sep 2023 17:36:12 +0000 (UTC) (envelope-from rpokala@freebsd.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1694453772; 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=TAjj2a1OO0QwT00e0bA5DGmxkYHNFXwg77C8t/yUtuc=; b=iiWaLvgEooI2u2gTKfno8PX9+ZppSjyViVuRTPIwub9hTz3LG2Uo91/gCLajC9TvPCDHbj qnPoUByQSRsKJgBK99BbBE3TD3WHmBQQmtW63O2dWvvEAIw8NfHE7EUJHtGML5VJ83vW7R v4064SN3qmwYQ2zydyefaruynuMSIZSh8DGXivM4Ef+vRQfQYy8GC7S2ox7556Fz9/BTt2 WOxRNLN7qkUifYw4KTBGlVxO4SCLggXqxSVgNVn+GFz3dmk9maawPPreYpyDzTjzK9nLzy Gz5zpFwsrD+kL0XCd5UgUbv8U6wbn5/aTRQkwmoQXH/Jd0hrM6OMJ7SdRqJMtQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1694453772; a=rsa-sha256; cv=none; b=D8qNMmFRdBPt+iBvHqD3DP+8sCssvwJEBo5+tS2+sDp+KEx7I3Azd2CX3LkFnzswuAXOuy q7PCTSHrDgeGWqbtNjXSfVzd/MLjGD/ey5OcZJYvw3k2Rp6rBh2Fq9pkK8kP62rnIttqez RWJCO4s/KS6bzPwEYX+WtQaDRyJLtiJba9GTzslNK4t0jFXlAbhttk/uLNyEVld/ff8n0e 3kd5gnurWkxiJsqB6dO9RKO+JQ9hYDMWJCTm4ACzfmJ4xSAJGwnwPu5U4kzPXcWK35z+kC 6SqBJRdZI0phQVRWPbVhCoR9/0c0uhl+BcSvCCqtxE9Fi2Ych6pChoS9wFgvMA== 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=1694453772; 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=TAjj2a1OO0QwT00e0bA5DGmxkYHNFXwg77C8t/yUtuc=; b=DUpEvqSfyLVNUjssdM7UrS1kiuaesP/Pc7l3DOFQLWrWWHnN7HOgdnL/q76xMw6hjAxDMP JA7ce7PBPG08Av3m3k6LEMUKss4XKNFuir/i5q5OGnJSri49wHEUA3PoK5n2NX3fbecrBn Oh6dgG46AE2YT0Ba/C3gXH3cg/JaDgCzlyXnM+uBhvRaQCz7Mpg3GyVFiOjzjOKlNxQzRR tjZKOUt/B74MDHQDVRfhevZCrmNug4EIueakSN2Txo8ITfvSScHC34I6STMX8jcgzME3he DnxFZbNVzQzxnDPCHlU32nhapZLJ5S5/WBlh7QbGdnO45g4ig8vGOazs20s2Pw== 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 4Rkv5R4TzBz1785; Mon, 11 Sep 2023 17:36:11 +0000 (UTC) (envelope-from rpokala@freebsd.org) User-Agent: Microsoft-MacOutlook/16.76.23082700 Date: Mon, 11 Sep 2023 10:36:07 -0700 Subject: Re: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use pctrie code" From: Ravi Pokala To: Doug Moore , , , Message-ID: <4D14E962-56B8-4C06-9252-0BEEDFA465AE@panasas.com> Thread-Topic: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use pctrie code" References: <202309110835.38B8Zl9t059626@gitrepo.freebsd.org> <25DD750F-38F2-4151-9E34-350844CE705C@panasas.com> <835d7376-4289-9ec5-415f-e94ea2c9b6d2@freebsd.org> In-Reply-To: <835d7376-4289-9ec5-415f-e94ea2c9b6d2@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 Thanks! -Ravi (rpokala@) =EF=BB=BF-----Original Message----- From: Doug Moore > Date: Monday, September 11, 2023 at 10:26 To: Ravi Pokala >, >, >, > Subject: Re: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use pc= trie code" Because jenkins reported failures on most of the non-amd64=20 architectures, and leaving 'main' broken while I figured out the problem=20 was not a sensible choice. Doug On 9/11/23 12:21, Ravi Pokala wrote: > 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: >>, >>, <= dev-commits-src-main@FreeBSD.org <= mailto:dev-commits-src-main@FreeBSD.org >> > Subject: git: 6cec93da46c4 - main - Revert "radix_trie: have vm_radix use= pctrie code" > > > The branch main has been updated by dougm: > > > URL: https://cgit.FreeBSD.org/src/commit/?id=3D6cec93da46c4a91a042b0be48884= 4052c0f8985a > > > 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 wi= thin > + * 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. Otherwi= se, > + * sets slot value, and returns false. > + */ > +static __inline bool > +vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t index, int *sl= ot) > +{ > + 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 otherwis= e. > + */ > +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 l= ock. > + * > + * 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 l= ock. > + * > + * 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= at > + * 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 inde= x. > + */ > +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 i= ndex); > +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_rad= ix_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= to a > + * page marked with a set 1-bit. A leaf may be associated with a null po= inter > + * 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 l= ock. > - * > - * 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 l= ock. > - * > - * 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= at > - * 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 inde= x. > - */ > -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 */ > > > >