From nobody Wed Jul 6 17:05:03 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 24A4D1D0C879; Wed, 6 Jul 2022 17:05:05 +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 4LdQrw1z1Vz3CPd; Wed, 6 Jul 2022 17:05:04 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657127104; 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=f9y/S3wTu2Nj9i/X8MmBFl9ZMNupsDuGJGIfQ6cYNYw=; b=ibMqMRC5Kl+c+SsInlkGn1tTLAWYVpjg/ok3J/YIsh7OSRHSWms72gXXYigmynfblk3jRQ m+kWZyK3obyUsW6idbcWkmn7o2tyRD1WphtkGe1xJahq1ORQndv4wRjuNnklAQZbZmCw2Z KfvSfpQ9+CwYmwnM3JcfhzG5HsSlf8fe1pnRKH+PQDowiB9bpzfrjKG6dNsqFMGXo44nRA jC/aliCZFHNsyNt/E/l7lWeo4k2WBos1pz/aZ/r4Wo7CxlK7GRAasvYCSHyDuPq4qe8u/z u1YZe216bz8Ar8mrESq5iHgc8VPxGo1PthStfp1hSNzGnb2f8gmJspYLFEII2A== 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 E04FF1E3F0; Wed, 6 Jul 2022 17:05:03 +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 266H53Bt083717; Wed, 6 Jul 2022 17:05:03 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 266H53ed083716; Wed, 6 Jul 2022 17:05:03 GMT (envelope-from git) Date: Wed, 6 Jul 2022 17:05:03 GMT Message-Id: <202207061705.266H53ed083716@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: 3a33ebe65fce - stable/13 - 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/stable/13 X-Git-Reftype: branch X-Git-Commit: 3a33ebe65fcec5c9df28a4154aa9e27b94207d93 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657127104; 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=f9y/S3wTu2Nj9i/X8MmBFl9ZMNupsDuGJGIfQ6cYNYw=; b=cVWria0wfElasCZzezU9OhEnVslTqc95MXOieCBuSxDOZC4f8SEw5ufsFyIgXT/SU9Zicz Yl4kiNNh3yYbEyzCZl+iRiwYDyNA6IIkaFbO6f3lfqGodvZEaoyMeGFllgJiF/uQIe3Wpz mdXdPPQulE951q4KE+mLA2tjirN+prVlyw66+aBbp2z8PySQGeWEdJvwzsNr9J4ENL+73U ydQ4TWPP7F4ZcsrmhXJDtsq+LxeZtFdUabZ4XemtGjahbrg+h/js+wmPSxI0RFqlPW4kiR /of0LcsnYVgdDPe5yHwz8RIlmAbHPYq8Eq2iG/CWrc0x1aG2TEkXfYWFB8Ze5Q== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1657127104; a=rsa-sha256; cv=none; b=DVEp8SGVwj8DcrJ63dV/4ukywMIITFhUOcq40BfMM80/iy63qlzEpYzUGQD5o4mKTLQn8i Ln5rIq2vZR8mfmS27bPSbEoBZw88y3JsazelEaU8ZEXrgYc/38tWYlzZifdZOhvgK7JRxK 1OumMtKCVE4w9/x1TTLDaFFRLH+Xbt8fQLjyGr/T5k6Wpo05kjtzBU7S7dJtm1ie7FwTbM hb6yzFuat2YxtLOleXRo6xp9AynjPG+tTptusrSK1iR38y1a60X9NW9Q87E2z0/9cq9q52 jQzdpVeF1VNTPYi4YNy2n04AVCqktL9gdF6JCM5nv9Zwx1VKe3NKgbwlcWQbVg== 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=3a33ebe65fcec5c9df28a4154aa9e27b94207d93 commit 3a33ebe65fcec5c9df28a4154aa9e27b94207d93 Author: Doug Moore AuthorDate: 2022-06-15 16:32:56 +0000 Commit: Doug Moore CommitDate: 2022-07-06 16:43:37 +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 (cherry picked from commit f979ad00306508f0c9fc925ec05b2413b70ab5f1) --- 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 11a3e9ab695e..7ff44a7b0027 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); }