From nobody Wed Jun 15 16:36:42 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 2B50785EA70; Wed, 15 Jun 2022 16:36: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 "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4LNWCv0XVMz4vb2; Wed, 15 Jun 2022 16:36:43 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655311003; 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=xZdCVLieous6g2TE+6NMdHsY072/NUu/4Wii3//VLFw=; b=sCPrvzVaRaWbhM47nNNT+K+9H9w7n1o9V006WEd4kP38ll+e1j4N4p8SZOJvcNqSV84qBu d0GpI1to2DuiGo32Qs3ZEsO3/lgprkDIjjzSPv+FG5V0n6M2kq1umnUtrk7MUxJj6k6Hvp 8IhIUQtq7ttjgxUIOKtblTsMNkYb5M3jSe4EDw3Qgwwctz93ijVjCnVX9DyLnAct9RCXs1 YKEi+HJVKT3xcrBYFcrsj/cpgqq3B9p2V50Zcoynlqnc4GjmkBe+a37cHwpNOyeG/pwjVE RWczdCDd/NWNzNbSoIFauNh814lPpXP5PiXfwRs4SyqUY5heEoZbTSRUBAkPkg== 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 E626922131; Wed, 15 Jun 2022 16:36:42 +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 25FGagP5065829; Wed, 15 Jun 2022 16:36:42 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 25FGagvO065828; Wed, 15 Jun 2022 16:36:42 GMT (envelope-from git) Date: Wed, 15 Jun 2022 16:36:42 GMT Message-Id: <202206151636.25FGagvO065828@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: f979ad003065 - main - iommu_gas: make iommu_gas_lowermatch non-recursive 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/main X-Git-Reftype: branch X-Git-Commit: f979ad00306508f0c9fc925ec05b2413b70ab5f1 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655311003; 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=xZdCVLieous6g2TE+6NMdHsY072/NUu/4Wii3//VLFw=; b=bMFqGx3dcE9VtcKjXgW7XuAXd4125ve4DVDrhiS66no708bKRjAjlVG0DKO5eUYjvISDPB 45lD4KXnYjKUNnJ3fNdrfG/j3xnM98NNRrhRh6kc2hZzqvpcXxEgp1Ex/KbJr5r/FBw9l2 /iKfaaXbw+7DH0PHmhxpQP3vF2UOqJxqJUYRG+76vOUXP7KRRjtQnlXw76PpnC1/h66wB8 xZoYuszqF8f4Og7JwMBDkMhchVus9ByOW7t2Zj9yKHWorBgS2g/raKAxmxuLgf8+o9O0aY OMB7uAmYBzHPi2To2dOPhzR2L3kc2xEGCESZqcIxXjWY2Zhov8B3sBgb+YD4rw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1655311003; a=rsa-sha256; cv=none; b=dApcoXjeb+VZrtyhWz4sXLnTb+C3RY81W5S7KVKs68U0cfaHOh/RpxtZvA6SzkTnujxRji 2lDx1eIMTbDR32hGBCzMcH1n7mEyZS1eTW/shVOiU1wEAIahqi+THJHfQlk6D2tvqFLa6U aAsvFo9QLpyYQgwtX2WGyd6RYicHuzEFp+JpsflcSlIKEcJvY+JnNgjRYw9o6qhD7C/WFQ uppx34Jy1NFiv0QRUyCu5pCv1wB9S6r7gYcHL04ek5I6bFd9YwiX+FJ6BW5hD6BVmyhaEt ZEd97y+I4hMM7bz9aIqHaghd3EHKkHhJGDjrZX+0mQ7kCEECx6uS4n8Bo6s9fQ== 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=f979ad00306508f0c9fc925ec05b2413b70ab5f1 commit f979ad00306508f0c9fc925ec05b2413b70ab5f1 Author: Doug Moore AuthorDate: 2022-06-15 16:32:56 +0000 Commit: Doug Moore CommitDate: 2022-06-15 16:32:56 +0000 iommu_gas: make iommu_gas_lowermatch non-recursive Change the recursive implementation to one that uses parent pointers to walk back up the rb-tree, to slightly improve performance. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D35486 --- sys/dev/iommu/iommu_gas.c | 76 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 53 insertions(+), 23 deletions(-) diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index e4f396d97fb7..27954de9db39 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -376,35 +376,65 @@ iommu_gas_match_insert(struct iommu_gas_match_args *a) static int iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry) { - struct iommu_map_entry *child; + struct iommu_map_entry *first; + iommu_gaddr_t min_free; /* * If the subtree doesn't have free space for the requested allocation - * plus two guard pages, give up. + * plus two guard pages, skip it. */ - if (entry->free_down < 2 * IOMMU_PAGE_SIZE + - roundup2(a->size + a->offset, IOMMU_PAGE_SIZE)) - return (ENOMEM); - if (entry->first >= a->common->lowaddr) - return (ENOMEM); - child = RB_LEFT(entry, rb_entry); - if (child != NULL && 0 == iommu_gas_lowermatch(a, child)) - return (0); - 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); + min_free = 2 * IOMMU_PAGE_SIZE + + roundup2(a->size + a->offset, IOMMU_PAGE_SIZE); + + /* Find the first entry that could abut a big-enough range. */ + first = NULL; + while (entry != NULL && entry->free_down >= min_free) { + first = entry; + entry = RB_LEFT(entry, rb_entry); } - 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); + + /* + * Walk the big-enough ranges until one satisfies alignment + * requirements, or violates lowaddr address requirement. + */ + entry = first; + while (entry != NULL) { + if ((first = RB_LEFT(entry, rb_entry)) != NULL) { + if (first->last >= a->common->lowaddr) { + /* All remaining ranges >= lowaddr */ + break; + } + if (iommu_gas_match_one(a, first->last, entry->start, + a->common->lowaddr)) { + iommu_gas_match_insert(a); + return (0); + } + } + if (entry->end >= a->common->lowaddr) { + /* All remaining ranges >= lowaddr */ + break; + } + if ((first = RB_RIGHT(entry, rb_entry)) != NULL && + iommu_gas_match_one(a, entry->end, first->first, + a->common->lowaddr)) { + iommu_gas_match_insert(a); + return (0); + } + /* Find the next entry that might abut a big-enough range. */ + if (first != NULL && first->free_down >= min_free) { + /* Find next entry in right subtree. */ + do + entry = first; + while ((first = RB_LEFT(entry, rb_entry)) != NULL && + first->free_down >= min_free); + } else { + /* Find next entry in a left-parent ancestor. */ + while ((first = RB_PARENT(entry, rb_entry)) != NULL && + entry == RB_RIGHT(first, rb_entry)) + entry = first; + entry = first; + } } - if (child != NULL && 0 == iommu_gas_lowermatch(a, child)) - return (0); return (ENOMEM); }