From nobody Tue Oct 22 21:58:42 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 4XY5fV2WySz5ZQsG; Tue, 22 Oct 2024 21:58:42 +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 "R11" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4XY5fV23F2z4F3q; Tue, 22 Oct 2024 21:58:42 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1729634322; 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=AB+YYkolte0zfrxYXEDMpG3di8v9P5OxBlNYCWm33SY=; b=EEZTY6/kAJnxXb9rtV4/W+ybN64HaXDmyH30wU0O9Rdj22SEUhdB3PgTTo4VoqnDiwTgZP MPZG4RtUSN8xLy2QgMEHedQfEuSYMwX5EcN9ZuJAAmRLj0GNnb5JoktjfncBGmshRgixlW DKGsQ919uu/tAqNT8gBK7INbFHTCUV1sN0CGxxJAz5fZ+RgKP0dbZ121+ON86/Ewqg7Nc4 CvVqTkp2gSpd0Ft5cPJtA/BPWe1FMOPdtYUlE/hObPHZinMfKIx+XFxI+R/MNl/YIO5SI+ f2zAbfUqwHQO4RyHr7fF+hhU0iOEinu5YJGK6cuq+7C6z6OzoXpIFlOZXyDwAA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1729634322; 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=AB+YYkolte0zfrxYXEDMpG3di8v9P5OxBlNYCWm33SY=; b=mxVAP/DMibw+7md+SH9iBYi08DqTQxLudxXFBiB9ZOOX+JR2uat7NkIS8dChctSSAZp/t9 vFBvvUjLkD2rlI3scK5jrlJJJWKmNXYdDCD+s++/39yoFKzFc4Kg5dj1hpEM9Vk7nUvarE v8pafftJMKjl3G8xjcXYlSDNjJ3AEYPrDMwFgRdyg7VfCoPgwfQEoukKDmlWbhcRRPXcsx lRqiKKPtYMlLa24Ox55OPBgJ+QdsHic2vYuHdlFP2g6r4ic1HnbjeMwkfqowuftXaPS9V5 jJ9oI/R5qAbmm8u1S8nIBvUNGneOtMjHuZlElO9d3VXygOs7dQotMChJ1UNn4g== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1729634322; a=rsa-sha256; cv=none; b=rMax+p6a5JFkcnz/2L4G2tGx4C5L6fcnpIv0fmDjN/gz9ViU52IPOR/IMFU4F5+RIA/aUh lOqQ8BoEpbOCgXsC7oRTMC67BqcaSSzIMuLyC6D+hfkBlEUUX/Auol2h956fGilz0oeso+ Qj/arnbUlHKu4zSiFWl00R6W8SGfP03OlOgE4cKthU04FOyGxxtX+uIJmVEOYjV4FccZ4u FMbME0liA5Y9W+JYush3B249L+o0CYKiCMyj15iuk0LsxlLu0ZOXh1f4/WqxXtrcy2Ha6U tRH9SsklSNn6JKhsut0yhotqWHArt764TEef44hrUusP0foivJFHTBdRcIAM9g== 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 4XY5fV1fQbzXb1; Tue, 22 Oct 2024 21:58:42 +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 49MLwg40077717; Tue, 22 Oct 2024 21:58:42 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 49MLwgjD077714; Tue, 22 Oct 2024 21:58:42 GMT (envelope-from git) Date: Tue, 22 Oct 2024 21:58:42 GMT Message-Id: <202410222158.49MLwgjD077714@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: e2414d91d33f - main - vfs_subr: maintain sorted tailq 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: e2414d91d33f31d6f2c9f49eef7a1553b5798c9e Auto-Submitted: auto-generated The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=e2414d91d33f31d6f2c9f49eef7a1553b5798c9e commit e2414d91d33f31d6f2c9f49eef7a1553b5798c9e Author: Doug Moore AuthorDate: 2024-10-22 21:54:34 +0000 Commit: Doug Moore CommitDate: 2024-10-22 21:54:34 +0000 vfs_subr: maintain sorted tailq Pctries are based on unsigned index values. Type daddr_t is signed. Using daddr_t as an index type for a pctrie works, except that the pctrie considers negative values greater than nonnegative ones. Building a sorted tailq of bufs, based on pctrie results, sorts negative daddr_ts larger than nonnegative ones, and makes code that depends on the tailq being actually sorted broken. Write wrappers for the functions that do pctrie operations that depend on index ordering that fix the order problem, and use them in place of direct pctrie operations. PR: 282134 Reported by: pho Reviewed by: kib, markj Tested by: pho Fixes: 2c8caa4b3925aa7335 vfs_subr: optimize inval_buf_range Differential Revision: https://reviews.freebsd.org/D47200 --- sys/kern/vfs_subr.c | 56 +++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 44 insertions(+), 12 deletions(-) diff --git a/sys/kern/vfs_subr.c b/sys/kern/vfs_subr.c index ff18c50546dd..3b00fdbe93b4 100644 --- a/sys/kern/vfs_subr.c +++ b/sys/kern/vfs_subr.c @@ -537,6 +537,42 @@ buf_trie_free(struct pctrie *ptree, void *node) PCTRIE_DEFINE_SMR(BUF, buf, b_lblkno, buf_trie_alloc, buf_trie_free, buf_trie_smr); +/* + * Lookup the next element greater than or equal to lblkno, accounting for the + * fact that, for pctries, negative values are greater than nonnegative ones. + */ +static struct buf * +buf_lookup_ge(struct bufv *bv, daddr_t lblkno) +{ + struct buf *bp; + + bp = BUF_PCTRIE_LOOKUP_GE(&bv->bv_root, lblkno); + if (bp == NULL && lblkno < 0) + bp = BUF_PCTRIE_LOOKUP_GE(&bv->bv_root, 0); + if (bp != NULL && bp->b_lblkno < lblkno) + bp = NULL; + return (bp); +} + +/* + * Insert bp, and find the next element smaller than bp, accounting for the fact + * that, for pctries, negative values are greater than nonnegative ones. + */ +static int +buf_insert_lookup_le(struct bufv *bv, struct buf *bp, struct buf **n) +{ + int error; + + error = BUF_PCTRIE_INSERT_LOOKUP_LE(&bv->bv_root, bp, n); + if (error != EEXIST) { + if (*n == NULL && bp->b_lblkno >= 0) + *n = BUF_PCTRIE_LOOKUP_LE(&bv->bv_root, ~0L); + if (*n != NULL && (*n)->b_lblkno >= bp->b_lblkno) + *n = NULL; + } + return (error); +} + /* * Initialize the vnode management data structures. * @@ -2489,9 +2525,8 @@ bnoreuselist(struct bufv *bufv, struct bufobj *bo, daddr_t startn, daddr_t endn) for (lblkno = startn;;) { again: - bp = BUF_PCTRIE_LOOKUP_GE(&bufv->bv_root, lblkno); - if (bp == NULL || bp->b_lblkno >= endn || - bp->b_lblkno < startn) + bp = buf_lookup_ge(bufv, lblkno); + if (bp == NULL || bp->b_lblkno >= endn) break; error = BUF_TIMELOCK(bp, LK_EXCLUSIVE | LK_SLEEPFAIL | LK_INTERLOCK, BO_LOCKPTR(bo), "brlsfl", 0, 0); @@ -2628,9 +2663,8 @@ v_inval_buf_range_locked(struct vnode *vp, struct bufobj *bo, clean = true; do { bv = clean ? &bo->bo_clean : &bo->bo_dirty; - bp = BUF_PCTRIE_LOOKUP_GE(&bv->bv_root, startlbn); - if (bp == NULL || bp->b_lblkno >= endlbn || - bp->b_lblkno < startlbn) + bp = buf_lookup_ge(bv, startlbn); + if (bp == NULL) continue; TAILQ_FOREACH_FROM_SAFE(bp, &bv->bv_hd, b_bobufs, nbp) { if (bp->b_lblkno >= endlbn) @@ -2709,13 +2743,13 @@ buf_vlist_find_or_add(struct buf *bp, struct bufobj *bo, b_xflags_t xflags) else bv = &bo->bo_clean; - error = BUF_PCTRIE_INSERT_LOOKUP_LE(&bv->bv_root, bp, &n); + error = buf_insert_lookup_le(bv, bp, &n); if (n == NULL) { KASSERT(error != EEXIST, ("buf_vlist_add: EEXIST but no existing buf found: bp %p", bp)); } else { - KASSERT((uint64_t)n->b_lblkno <= (uint64_t)bp->b_lblkno, + KASSERT(n->b_lblkno <= bp->b_lblkno, ("buf_vlist_add: out of order insert/lookup: bp %p n %p", bp, n)); KASSERT((n->b_lblkno == bp->b_lblkno) == (error == EEXIST), @@ -2728,16 +2762,14 @@ buf_vlist_find_or_add(struct buf *bp, struct bufobj *bo, b_xflags_t xflags) /* Keep the list ordered. */ if (n == NULL) { KASSERT(TAILQ_EMPTY(&bv->bv_hd) || - (uint64_t)bp->b_lblkno < - (uint64_t)TAILQ_FIRST(&bv->bv_hd)->b_lblkno, + bp->b_lblkno < TAILQ_FIRST(&bv->bv_hd)->b_lblkno, ("buf_vlist_add: queue order: " "%p should be before first %p", bp, TAILQ_FIRST(&bv->bv_hd))); TAILQ_INSERT_HEAD(&bv->bv_hd, bp, b_bobufs); } else { KASSERT(TAILQ_NEXT(n, b_bobufs) == NULL || - (uint64_t)bp->b_lblkno < - (uint64_t)TAILQ_NEXT(n, b_bobufs)->b_lblkno, + bp->b_lblkno < TAILQ_NEXT(n, b_bobufs)->b_lblkno, ("buf_vlist_add: queue order: " "%p should be before next %p", bp, TAILQ_NEXT(n, b_bobufs)));