From nobody Thu Jul 10 08:17:43 2025 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 4bd74l74bKz61j32; Thu, 10 Jul 2025 08:17:43 +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 "R10" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4bd74l5NsGz3rwf; Thu, 10 Jul 2025 08:17:43 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1752135463; 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=FMUmGhNOLHdkipVKt8mGrnNmL7mnzDFYfkZoO2wqDCA=; b=sGi2wIAEib8nKvbVsZJ3UtOXhSLcTunImlcnOi0kot6X84OJBbqcNpKrxwVey8De9Rdo9t 27wD8dBMONx6I9cf83EU4qNxhUQL620jVhV7Xz2bzaDAsbRzJjizMyEGID1s05PMS6fqBa SAxjl8jkIsa2TXNcQFb6qrrRzfl6jNfU49M08+6qEHXoDalqUUr1etd7xblhZzqXGIhn2H esXyJgUMKsuFnSi3tg6nIl0Yg/zkbW8FcnzSDtu2wCCpacbWDD8wqD5UtEN7NCbcbw/wjs MBoFa9KoE6q+ZpJQCKOonISd8CJYA+0FvdDhOa4wJGHwDWqqCx0oRlFBX2aFaQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1752135463; 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=FMUmGhNOLHdkipVKt8mGrnNmL7mnzDFYfkZoO2wqDCA=; b=MeGEJtJi/cprHFH/QUYTKAjeB2a0IwcQp3aZ4Na+gdRjmwRQLgKAMVEoi1s4fC0ELqkDUl FXV952KYxHwKonr86XUmJsPswc3JMWKOkpT0A1NUpEnFTZCNZxH4G3EFsUhJzrsn5Qlp/N QcMFwhJ800HBDpPsp4pJHJm12d9eeirZwiYy0PMVCt2KUYL6EiKl2ETcZvt6ZLz33H2vWr 1Qsq4YOAlIOZQkNL9iOpkbAl38qEdjq6iQe70+3Fkn18YWO4zemDESvw6QRZTGj7Bp5FEE cUWmmWKJ8jvmkBezuttG5MRKhwcOh8KNAJeRujhz9waYPPyE1uunCRxxLBysfA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1752135463; a=rsa-sha256; cv=none; b=HVnwEHqmEilw0H0IwYw2+3uRH6KndAZYuGDHtofBpPeMMWx3Oomf1/MAjmFleNf4TR9QyR 6VoH3ykLasAujr2HBfn+IZHqeuyD8vMOyleGtWN/jC3s096Q5vO4WLjHqhO1D0euH05kuE z+lmp0zdBj8SehJ/fe+/gxx/3bhsXKwEuPMP50uvNnEv19Vm1x05qLQDSYpyQubjnV1JgG aqlflj0febyv9tmRN3VEvnjugazBUraMEjue7MI8TxsWPborB1ayU0jFWZIo4HJszKzzUK N2ATdBy/5exq6D6CyOCQT0V3icfkF6bAkxlllePam0HjubLDTAJbiuxmIFMZaA== 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 4bd74l4rQjzyj7; Thu, 10 Jul 2025 08:17:43 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.18.1/8.18.1) with ESMTP id 56A8HhEo083909; Thu, 10 Jul 2025 08:17:43 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 56A8HhkK083906; Thu, 10 Jul 2025 08:17:43 GMT (envelope-from git) Date: Thu, 10 Jul 2025 08:17:43 GMT Message-Id: <202507100817.56A8HhkK083906@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: 8adb3acb63ee - main - pctrie: leave iter at root after ge_lookup failure 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: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-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: 8adb3acb63ee8e7c20c3da497a9640c481bc7612 Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=8adb3acb63ee8e7c20c3da497a9640c481bc7612 commit 8adb3acb63ee8e7c20c3da497a9640c481bc7612 Author: Doug Moore AuthorDate: 2025-07-10 08:14:07 +0000 Commit: Doug Moore CommitDate: 2025-07-10 08:14:07 +0000 pctrie: leave iter at root after ge_lookup failure If pctrie_lookup_iter_ge fails to return a node, the iterator is left with NULL as the current node. Instead, make the pctrie_root the current node when the pctrie has an internalnode. Do the same thing for lookup_iter_le. If an iterator is reused after a ge/le lookup fails, this will skip the step in _pctrie_lookup_node where a NULL is replaced by the node at the top of the trie. Reviewed by: alc Differential Revision: https://reviews.freebsd.org/D51232 --- sys/kern/subr_pctrie.c | 36 ++++++++++++++++++++---------------- 1 file changed, 20 insertions(+), 16 deletions(-) diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c index 3a3548bad52b..bb86c779b936 100644 --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -691,21 +691,23 @@ _pctrie_lookup_ge(struct pctrie *ptree, struct pctrie_node *node, */ if (node == PCTRIE_NULL || *pctrie_toval(node) < index) { /* Climb the path to find a node with a descendant > index. */ - for (node = parent; node != NULL; node = pctrie_parent(node)) { - slot = pctrie_slot(node, index) + 1; - if ((node->pn_popmap >> slot) != 0) + node = NULL; + while (parent != NULL) { + slot = pctrie_slot(parent, index) + 1; + if ((parent->pn_popmap >> slot) != 0) break; + node = parent; + parent = pctrie_parent(node); } - if (node == NULL) { + if (parent == NULL) { if (parent_out != NULL) - *parent_out = NULL; + *parent_out = node; return (NULL); } /* Step to the least child with a descendant > index. */ - slot += ffs(node->pn_popmap >> slot) - 1; - parent = node; - node = pctrie_node_load(&node->pn_child[slot], NULL, + slot += ffs(parent->pn_popmap >> slot) - 1; + node = pctrie_node_load(&parent->pn_child[slot], NULL, PCTRIE_LOCKED); } /* Descend to the least leaf of the subtrie. */ @@ -785,21 +787,23 @@ _pctrie_lookup_le(struct pctrie *ptree, struct pctrie_node *node, */ if (node == PCTRIE_NULL || *pctrie_toval(node) > index) { /* Climb the path to find a node with a descendant < index. */ - for (node = parent; node != NULL; node = pctrie_parent(node)) { - slot = pctrie_slot(node, index); - if ((node->pn_popmap & ((1 << slot) - 1)) != 0) + node = NULL; + while (parent != NULL) { + slot = pctrie_slot(parent, index); + if ((parent->pn_popmap & ((1 << slot) - 1)) != 0) break; + node = parent; + parent = pctrie_parent(node); } - if (node == NULL) { + if (parent == NULL) { if (parent_out != NULL) - *parent_out = NULL; + *parent_out = node; return (NULL); } /* Step to the greatest child with a descendant < index. */ - slot = ilog2(node->pn_popmap & ((1 << slot) - 1)); - parent = node; - node = pctrie_node_load(&node->pn_child[slot], NULL, + slot = ilog2(parent->pn_popmap & ((1 << slot) - 1)); + node = pctrie_node_load(&parent->pn_child[slot], NULL, PCTRIE_LOCKED); } /* Descend to the greatest leaf of the subtrie. */