From nobody Thu Jun 13 16:48:19 2024 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 4W0Syq5HYcz5NyH3; Thu, 13 Jun 2024 16:48:19 +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 4W0Syq4Sq4z4Vj6; Thu, 13 Jun 2024 16:48:19 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1718297299; 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=RtPkCY0tBNDiVMfw2jwCDmKW5u1ZKt2Aa5KEIsdF9wg=; b=Iq/eQ0HOItDT8ZXx5jUeAjpt86hNagFmQpmRvZXO8UcNzV5h+XJWOSMw9DS4jOpTtLEtuy h4VZY3+S9ZIBGVVsmYpbHF3U3K6UrsomgJJt/Q1qMHnp8zI0Nhp/VWPMd8SCEcK5fVr4Ql z/Rvv9yVUIifdLWB2y7+K9tSgHUUq8TT3ngUo4v82eSVNIBkAx8cvwK2wiDmPE5Nse5zfB n1rekkslwVx+2QcxBfigK3AbhcgOYGwgA7oI0YKUhzNWkdhmxQdkFVJUeO5w9xkQrCZSfS BV3hufZGOAc5q/3lHivf6eO6B22lewWUHXjSDzUUzAMzGMd8VbD7OZWoDxnApQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1718297299; a=rsa-sha256; cv=none; b=g45JIlKublHSx4mOJm9joQgIuUcTM/BJPSanqS8dfHcWicrsKweeDR3Z4PUShF+S1Rbni5 fle6tc/Enwd5d20sxg/bgVaa9RYpuKFTIVN80VXztGVlyVtq3rCIQTY5gsMWy5hQH9UpY/ Hb8+v3wGac5jbeQsTCivq8pvbv5kEDW9PXEw+zh30FJ1qCMiGhNJryWX9Ov2vIpF55RtZH aEGyrOuw6tjvAZW7u4NsNl+R/EvqyG6tC9r9VuNjgXNptBJO+mEj/Fh772bPb1Pj3g6dGl /37R8JQO8f11mSloknmwGO1Qn28whWtGNZBnIHIrnFPOM5CZbs06dsSofER1yA== 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=1718297299; 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=RtPkCY0tBNDiVMfw2jwCDmKW5u1ZKt2Aa5KEIsdF9wg=; b=b26H5PX1K2gp7pjTuq4jl+EZas0jzuKveVuxw3XgAFFndVV/+MlOpZ1EBiT+3t+zH6sNr5 x132jKdyX5bwRKEgC5FGcAwvFKesUb9q6sBffY2RhXMp5peQ/i3ApUxL9TxsA+rHLNd0y2 qfMyHhaPT5kBEKsDshPHP0MBfa3AUfiko0RWuwRPzZnecVzfmSsBXF5kpcQmm2+Vk1sZMw gEzqucavUTbGMTk6L17zUIF4p2+tsicRK4e0dV1VPoGlUOC+AV5mmQBDXH6/VNyHZ8dI7+ ITLBVK01lQCbegevXk2CPUMquHHPAOMt51XpuWE5u+auOHxCXpE31v/g8nM+RQ== 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 4W0Syq43rgzknH; Thu, 13 Jun 2024 16:48:19 +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 45DGmJDw086087; Thu, 13 Jun 2024 16:48:19 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 45DGmJlv086084; Thu, 13 Jun 2024 16:48:19 GMT (envelope-from git) Date: Thu, 13 Jun 2024 16:48:19 GMT Message-Id: <202406131648.45DGmJlv086084@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: c0d0bc2bed80 - main - subr_pctrie: add leaf callbacks to pctrie_reclaim 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: X-BeenThere: dev-commits-src-all@freebsd.org Sender: owner-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: c0d0bc2bed8003d2f2b24c3c29ce971ca8dfc556 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=c0d0bc2bed8003d2f2b24c3c29ce971ca8dfc556 commit c0d0bc2bed8003d2f2b24c3c29ce971ca8dfc556 Author: Doug Moore AuthorDate: 2024-06-13 16:44:38 +0000 Commit: Doug Moore CommitDate: 2024-06-13 16:48:09 +0000 subr_pctrie: add leaf callbacks to pctrie_reclaim PCTRIE_RECLAIM frees all the interior nodes in a pctrie, but is little used because most trie-destroyers want to free leaves of the tree too. Add PCTRIE_RECLAIM_CALLBACK, with two extra arguments, a callback function and an auxiliary argument, that is invoked on every non-NULL leaf in the tree as the tree is destroyed. Reviewed by: rlibby, kib (previous version) Differential Revision: https://reviews.freebsd.org/D45565 --- sys/kern/subr_pctrie.c | 78 ++++++++++++++++++++++++++++++++++++++------------ sys/sys/pctrie.h | 25 ++++++++++++++++ 2 files changed, 85 insertions(+), 18 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index 4017f98c207d..347c2bffd503 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -198,7 +198,6 @@ pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, static __inline bool pctrie_isleaf(struct pctrie_node *node) { - return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); } @@ -217,10 +216,18 @@ pctrie_toleaf(uint64_t *val) static __inline uint64_t * pctrie_toval(struct pctrie_node *node) { - return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); } +/* + * Returns the associated pointer extracted from node and field offset. + */ +static __inline void * +pctrie_toptr(struct pctrie_node *node, int keyoff) +{ + return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff)); +} + /* * Make 'child' a child of 'node'. */ @@ -792,14 +799,14 @@ pctrie_remove_lookup(struct pctrie *ptree, uint64_t index, } /* - * Prune all the leaves of 'node' before its first non-leaf child, make child - * zero of 'node' point up to 'parent', make 'node' into 'parent' and that - * non-leaf child into 'node'. Repeat until a node has been stripped of all - * children, and mark it for freeing, returning its parent. + * Walk the subtrie rooted at *pnode in order, invoking callback on leaves and + * using the leftmost child pointer for path reversal, until an interior node + * is stripped of all children, and returned for deallocation, with *pnode left + * pointing the parent of that node. */ -static struct pctrie_node * -pctrie_reclaim_prune(struct pctrie_node **pnode, - struct pctrie_node *parent) +static __always_inline struct pctrie_node * +pctrie_reclaim_prune(struct pctrie_node **pnode, struct pctrie_node *parent, + pctrie_cb_t callback, int keyoff, void *arg) { struct pctrie_node *child, *node; int slot; @@ -812,8 +819,11 @@ pctrie_reclaim_prune(struct pctrie_node **pnode, PCTRIE_UNSERIALIZED); pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_UNSERIALIZED); - if (pctrie_isleaf(child)) + if (pctrie_isleaf(child)) { + if (callback != NULL) + callback(pctrie_toptr(child, keyoff), arg); continue; + } /* Climb one level down the trie. */ pctrie_node_store(&node->pn_child[0], parent, PCTRIE_UNSERIALIZED); @@ -827,8 +837,9 @@ pctrie_reclaim_prune(struct pctrie_node **pnode, /* * Recover the node parent from its first child and continue pruning. */ -struct pctrie_node * -pctrie_reclaim_resume(struct pctrie_node **pnode) +static __always_inline struct pctrie_node * +pctrie_reclaim_resume_compound(struct pctrie_node **pnode, + pctrie_cb_t callback, int keyoff, void *arg) { struct pctrie_node *parent, *node; @@ -839,24 +850,55 @@ pctrie_reclaim_resume(struct pctrie_node **pnode) parent = pctrie_node_load(&node->pn_child[0], NULL, PCTRIE_UNSERIALIZED); pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, PCTRIE_UNSERIALIZED); - return (pctrie_reclaim_prune(pnode, parent)); + return (pctrie_reclaim_prune(pnode, parent, callback, keyoff, arg)); } /* * Find the trie root, and start pruning with a NULL parent. */ -struct pctrie_node * -pctrie_reclaim_begin(struct pctrie_node **pnode, - struct pctrie *ptree) +static __always_inline struct pctrie_node * +pctrie_reclaim_begin_compound(struct pctrie_node **pnode, + struct pctrie *ptree, + pctrie_cb_t callback, int keyoff, void *arg) { struct pctrie_node *node; node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED); pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED); - if (pctrie_isleaf(node)) + if (pctrie_isleaf(node)) { + if (callback != NULL && node != PCTRIE_NULL) + callback(pctrie_toptr(node, keyoff), arg); return (NULL); + } *pnode = node; - return (pctrie_reclaim_prune(pnode, NULL)); + return (pctrie_reclaim_prune(pnode, NULL, callback, keyoff, arg)); +} + +struct pctrie_node * +pctrie_reclaim_resume(struct pctrie_node **pnode) +{ + return (pctrie_reclaim_resume_compound(pnode, NULL, 0, NULL)); +} + +struct pctrie_node * +pctrie_reclaim_begin(struct pctrie_node **pnode, struct pctrie *ptree) +{ + return (pctrie_reclaim_begin_compound(pnode, ptree, NULL, 0, NULL)); +} + +struct pctrie_node * +pctrie_reclaim_resume_cb(struct pctrie_node **pnode, + pctrie_cb_t callback, int keyoff, void *arg) +{ + return (pctrie_reclaim_resume_compound(pnode, callback, keyoff, arg)); +} + +struct pctrie_node * +pctrie_reclaim_begin_cb(struct pctrie_node **pnode, struct pctrie *ptree, + pctrie_cb_t callback, int keyoff, void *arg) +{ + return (pctrie_reclaim_begin_compound(pnode, ptree, + callback, keyoff, arg)); } /* diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h index 06b9fca79528..4e1d8c7f8617 100644 --- a/sys/sys/pctrie.h +++ b/sys/sys/pctrie.h @@ -36,6 +36,8 @@ #ifdef _KERNEL +typedef void (*pctrie_cb_t)(void *ptr, void *arg); + #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \ PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ \ @@ -218,6 +220,24 @@ name##_PCTRIE_RECLAIM(struct pctrie *ptree) \ freefn(ptree, freenode); \ } \ \ +/* \ + * While reclaiming all internal trie nodes, invoke callback(leaf, arg) \ + * on every leaf in the trie, in order. \ + */ \ +static __inline __unused void \ +name##_PCTRIE_RECLAIM_CALLBACK(struct pctrie *ptree, \ + pctrie_cb_t callback, void *arg) \ +{ \ + struct pctrie_node *freenode, *node; \ + \ + for (freenode = pctrie_reclaim_begin_cb(&node, ptree, \ + callback, __offsetof(struct type, field), arg); \ + freenode != NULL; \ + freenode = pctrie_reclaim_resume_cb(&node, \ + callback, __offsetof(struct type, field), arg)) \ + freefn(ptree, freenode); \ +} \ + \ static __inline __unused struct type * \ name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \ { \ @@ -269,6 +289,11 @@ uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode, struct pctrie *ptree); struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode); +struct pctrie_node *pctrie_reclaim_begin_cb(struct pctrie_node **pnode, + struct pctrie *ptree, + pctrie_cb_t callback, int keyoff, void *arg); +struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode, + pctrie_cb_t callback, int keyoff, void *arg); uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index, struct pctrie_node **killnode); uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);