From nobody Wed Jul 6 17:04:59 2022 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 A25691D0C995; Wed, 6 Jul 2022 17:04:59 +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 4LdQrq3zdPz3CD5; Wed, 6 Jul 2022 17:04:59 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657127099; 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=TVv/OHRikm2g7ltvA8NlUXPArxMFV3tiSsd+NKfHreo=; b=AqQeafI1FtJXbpotkk9BmL77gYpJVhBNNVQwYzdlc6UZ8Oc0tJKrox3rY5mznxee0U91II M2LrPY26IDGGbu1hxknyRxa2hrlImUv4Yc3AU5HXXUOCuX7HL0gYNT8dt4AFEqcGIxcaJM xLI5y40/Arg0dT2JBfP1rNukuF3GDCTiDInkYvMTjUDYoWVh2ekoxUBL6vc6uZ/LXGzNex u6yoRbYHkFTA9cxlxLB7s2lnK2Wfp7+YWy2IFqyyChtKevFXC9Jr4Mw6E5DTwmT0drqOKs irs9kzSAoWY5AM9KAo17a6uJUo+vwx/NQlIQ5MOFJE0G2aJtf4GuMdVnYj5SDw== 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 68E601E479; Wed, 6 Jul 2022 17:04:59 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 266H4xbe083608; Wed, 6 Jul 2022 17:04:59 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 266H4xqX083607; Wed, 6 Jul 2022 17:04:59 GMT (envelope-from git) Date: Wed, 6 Jul 2022 17:04:59 GMT Message-Id: <202207061704.266H4xqX083607@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Doug Moore Subject: git: 80ad47c93250 - stable/13 - iommu_gas: Change find_space lower search order 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: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 80ad47c9325071083d1579aecd50188e0209c5a2 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657127099; 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=TVv/OHRikm2g7ltvA8NlUXPArxMFV3tiSsd+NKfHreo=; b=R6jeAmzc2U3nlUtLQ15ujDFL90czRAdxbn71Cq3FTArlOh5UwbpuQ0Tjj/4a9HcgTxYdme IeuuqzY9/4FZKJmV74SuKar1zQEY44GVM6KPupOPpKmIpZplr/UzFQYdoOvijewK4VmX0P 1sv/IHo4LiIu88SlUb4M5oSlsP8sQmEfJfnoeYJWzMEsNW00eYu0wXr87Zmi/qo2knYW1i SOIFczcTF9fPZ8qrg9IvKebJGnJFQ3BczKDhXRBVbjHFqBnrcOtPpaY7bJ/CBIb59zyR93 ri1Exn2T2nZtQgTru2ydNWLi0QrKgo2yQnT1uacwEbWimGObtdQJ7NBF8pg79Q== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1657127099; a=rsa-sha256; cv=none; b=vmqfo64IjUPSq+kUgsGmo0A9Nkmcc1Q/9/qkFzb+OD5eFZCGU3KM6rotJUbXDfWAik2gv7 JP+nTX3r2eq9eWwGO2kT7RO0ar6DgPQzA2p6pYFEG/4gs7Gr1hEInbaVw0mBSZs3y2cbUy u/3E+xl0WfVtdu8VBXn9oTE2aYdYy1z/wy0WwAhtN+CRiYIKZcf31Dxo+ykHep9DzO7JoV SrQ2BkGBf4qNBYTeZNGeONRf0A7UaVX2qMRHwC6kA37+Cu9HqZEMrEJg3ftF4XqAxOHYqG +DnppoPkUCugKXG40f+mEyEOgECCmhCGYQJkmXkkH0rUaIL2Fy7FnNLMKQdlNw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=80ad47c9325071083d1579aecd50188e0209c5a2 commit 80ad47c9325071083d1579aecd50188e0209c5a2 Author: Doug Moore AuthorDate: 2022-06-09 04:14:28 +0000 Commit: Doug Moore CommitDate: 2022-07-06 16:39:17 +0000 iommu_gas: Change find_space lower search order iommu_gas_lowermatch looks right, then left, then right again in its search for free space. Change to a more straightforward last-fit search that touches fewer tree nodes and improves performance. Reported by: wxzhu@rice.edu Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D35439 (cherry picked from commit 30031172534c22695ab7b26a9420bda7b20b0824) --- sys/dev/iommu/iommu_gas.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index b8bbcf0de7fb..d1a46ab6ee8f 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -377,14 +377,6 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent { struct iommu_map_entry *child; - child = RB_RIGHT(entry, rb_entry); - if (child != NULL && entry->end < a->common->lowaddr && - iommu_gas_match_one(a, entry->end, child->first, - a->common->lowaddr)) { - iommu_gas_match_insert(a); - return (0); - } - /* * If the subtree doesn't have free space for the requested allocation * plus two guard pages, give up. @@ -393,16 +385,22 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent return (ENOMEM); if (entry->first >= a->common->lowaddr) return (ENOMEM); - child = RB_LEFT(entry, rb_entry); + child = RB_RIGHT(entry, rb_entry); if (child != NULL && 0 == iommu_gas_lowermatch(a, child)) return (0); + if (child != NULL && entry->end < a->common->lowaddr && + iommu_gas_match_one(a, entry->end, child->first, + a->common->lowaddr)) { + iommu_gas_match_insert(a); + return (0); + } + child = RB_LEFT(entry, rb_entry); if (child != NULL && child->last < a->common->lowaddr && iommu_gas_match_one(a, child->last, entry->start, a->common->lowaddr)) { iommu_gas_match_insert(a); return (0); } - child = RB_RIGHT(entry, rb_entry); if (child != NULL && 0 == iommu_gas_lowermatch(a, child)) return (0); return (ENOMEM);