From nobody Thu Jun 09 04:20:15 2022 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 0EDCC847EB4; Thu, 9 Jun 2022 04:20:16 +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 4LJW8v5Pwwz3Qyn; Thu, 9 Jun 2022 04:20:15 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654748415; 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=Mfp6li19RCHILY3G7PtKMggrPygocOZT7Ksc13aJ57I=; b=k8OEBNnvM8Phlp0e2xfMSQ0WSDGMbBdL++++ictdBazM0fUy0OK+2JP40XK09lhEvucL0Y KdmppTr9INDyo5k8qywsKn1bhcJe0xbCUHYjMBbeIaPBqrO/DKTE1elNz3Oy2tW8aLTKQr 0o2ss/Sn01W4MPe+y3Tbroxv7HNBIWqqQEkF/O1y2ZUMOnrlUnlzMN97f2aBiUnv0RnknR zAOYdcWOiZE5rFlsy9ikR45/He193PXzA1EmKS8S/zQmwJZYem3mYLBDKCkFNxBVFNFhkO pIjYzyu+GGIHpAeLrPlzkNEEHiWnPLm51Kw3LZHFkFCVIgIEh3GRtL5YN9j7Rg== 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 9AF431D2B5; Thu, 9 Jun 2022 04:20:15 +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 2594KF5o001988; Thu, 9 Jun 2022 04:20:15 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2594KFtl001984; Thu, 9 Jun 2022 04:20:15 GMT (envelope-from git) Date: Thu, 9 Jun 2022 04:20:15 GMT Message-Id: <202206090420.2594KFtl001984@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: 30031172534c - main - iommu_gas: Change find_space lower search order 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: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: 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: 30031172534c22695ab7b26a9420bda7b20b0824 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654748415; 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=Mfp6li19RCHILY3G7PtKMggrPygocOZT7Ksc13aJ57I=; b=r2OvhOfDyL450HELd2ohFU1Ry/yyN0xsIM0xNQvyF+48gEIEDqOKhNRp4ZVnZlUFH/zEVQ JdbP3J7dS9dsVOu98Pr1+jO8rN6Ud5MPN2lbtg8ehu0mgJWAvxfOcAhI9W8uvINIqdlLbL rmjJh59uFPH/da+uBRUx8w3aycil7HF6gHH4SRwRxZw5Rvw734GVZyr28EVeSXNTfqSfkC 43gSX8j71gLduArvc/29VrsD4pHpLRWQWKHu+fLw9CNHlD5AIcugu5eqDA5RMeXWWNncZj okO7Lo4reUlIUrG3bbhbiZDgfds5tAirDXxKQDmmky+ju8Vi8op2BpGILQzzFA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1654748415; a=rsa-sha256; cv=none; b=oPFwQh/FKXcTed6kktxQDmqIifZ2py+aM4fdZ1A9eCg3Iu95fSFxhQACN6guu6MRwZmOBj OtKwOru6Ye4PgC7gtk3PgJxWqBF+fAUBihd+OXFqK/tRD1HTdh97OtTN6BlqJ2IBLA9Duu waRQcAh6XTyoBD3/TpRZoSgFfzzb3py9hJqHyannO/1tDK7iiyVIZtn0Uzhk+XY5XPhvVZ kO7vKlgqTNW/HwLOqdqzcAg/8K8o0gSvWTKjBNHaxoa/0chBFaChCGZrW2VDiW+4fw4glK b5EO6A0BC63vN69VKMOBdfISQqeKbXrdQ8g2sIpOS4ZB3gwkwUr69kl3k2hu7A== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=30031172534c22695ab7b26a9420bda7b20b0824 commit 30031172534c22695ab7b26a9420bda7b20b0824 Author: Doug Moore AuthorDate: 2022-06-09 04:14:28 +0000 Commit: Doug Moore CommitDate: 2022-06-09 04:14:28 +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 --- 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 78dd86c1f255..5b589e999926 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);