From nobody Sat Oct 29 05:55:18 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 4MzpY26Pglz4h4TV; Sat, 29 Oct 2022 05:55:18 +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 4MzpY25JCQz41sM; Sat, 29 Oct 2022 05:55:18 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1667022918; 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=BVeFr4dvGsVBYu00UgIVaFZzIgj2pdByeZiNyIr+kxU=; b=AvQq7y3MioE/7ekQmmQdm2+CqdW8HeU03RJRWkfhxw1yBhKc9cHmr+JOKqB1+iFNGTry6g 8ZsapYuOly9mVHPFImfaRmHt18HJMQWvhzq8exwkHUVP8eIQB2C0893iJE8pBzu6Zl5qrl 10RAmE4a0CeLDj04XgU3HGWyPO/8ELf3i+rj/Bm0888jABNpyFaYnNiwJybuAtM39ZDSeT 4lWqten2PN5j9mTdLbb6sP+WKHIf8SEQ1T73ouEWr+cmDe+x5pIMqW9V9j/mtL41+H7/oZ crWwEt3phzGo0WT38MbqkwjAR4rAdr6kAjl+USO4589AK7Cg/wGU62lh+d1mrg== 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 4MzpY24GQxz16N2; Sat, 29 Oct 2022 05:55:18 +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 29T5tIFS072688; Sat, 29 Oct 2022 05:55:18 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 29T5tItF072687; Sat, 29 Oct 2022 05:55:18 GMT (envelope-from git) Date: Sat, 29 Oct 2022 05:55:18 GMT Message-Id: <202210290555.29T5tItF072687@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: 8b221ca631c2 - main - iommu_gas: start space search from 1st free space 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: 8b221ca631c2d28584a4b6207dc107d8ff5a1b2f Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1667022918; 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=BVeFr4dvGsVBYu00UgIVaFZzIgj2pdByeZiNyIr+kxU=; b=kN2n8EYh0U5yr9h55zWFawITZCgr8TRQ5pUq/F3t9FWFEE4OWenWAgUGMCQJ8muSbOpwE6 su6w0BjthkJ6OlcfT7W1awgoptMix8h4IlldGzReC4IJFYMwHV/UJdOz0Iw0aJtPAo3nHN hsOdTW9gg0kXs9D+VAwq6CWRMquCGUawN+5YFJw0Ng6K/JGFz8r7sFYnNTWrlKXLzxhwAN tuA5KW+RxOj6+5+VUBDR3KzHOtDdwcbMLLl8RsKvqVdRyFeo0ehmTBbZi3wjKmys/QaEv2 Xl86uV1tI90C/Nh/3iCpCvsUrM7rT1ZUEiN2isrNHtNrpCt1U/gr6cF9xN5RQA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1667022918; a=rsa-sha256; cv=none; b=vytb75K3UT5uqxE6NULCJKmaFmbpYCaOqofHTi8casjwGpy3T9/XDjNqtxEtWv0AOcN2i6 EoyDocHYngcVdtIEljAxpw9I71dOG2vc8V3KtTbE5ffdjMH9AWhGJf94k+R2+iiyzByg/r 6km+OK2dBQOTw9wZtSGf9my3mOb/YWmgEs8VhOiDENCAMDE/2Q3z98KhzCF7kHOInVwoy9 mch50mMNhCRYSRq1SJvwv7eXkYaO7Ney5In9hR6PHwqO9RZTdkj77/h7JI0v2btkIz494R E5YTUtxiDo7rE7MXtw+GS/L/xtYr62fqE7Qr6fFJJyfZ7rvBP9hDbMeXU8fHgA== 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=8b221ca631c2d28584a4b6207dc107d8ff5a1b2f commit 8b221ca631c2d28584a4b6207dc107d8ff5a1b2f Author: Doug Moore AuthorDate: 2022-10-29 05:50:44 +0000 Commit: Doug Moore CommitDate: 2022-10-29 05:50:44 +0000 iommu_gas: start space search from 1st free space Maintain a pointer to an element in the domain map that is left of any sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. On find_space, move that pointer to the leftmost leaf in the subtree of nodes with free_down greater than or equal to the minimum allocation size before starting the search for space from that pointer. On removal of a node with address less than that pointer, update that pointer to point to the predecessor or successor of the removed node. In experiments with netperf streaming, this reduces by about 40% the number of map entries examined in first-fit allocation. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36624 --- sys/dev/iommu/iommu.h | 1 + sys/dev/iommu/iommu_gas.c | 71 ++++++++++++++++++++++++++++++++++------------- 2 files changed, 52 insertions(+), 20 deletions(-) diff --git a/sys/dev/iommu/iommu.h b/sys/dev/iommu/iommu.h index 2531ef09d9cd..cee59a0b55c0 100644 --- a/sys/dev/iommu/iommu.h +++ b/sys/dev/iommu/iommu.h @@ -109,6 +109,7 @@ struct iommu_domain { struct iommu_map_entries_tailq unload_entries; /* (d) Entries to unload */ struct iommu_gas_entries_tree rb_root; /* (d) */ + struct iommu_map_entry *start_gap; /* (d) */ iommu_gaddr_t end; /* (c) Highest address + 1 in the guest AS */ struct iommu_map_entry *first_place, *last_place; /* (d) */ diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index 8c8d0e49c378..ffb5370b507e 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -209,7 +209,18 @@ iommu_gas_check_free(struct iommu_domain *domain) static void iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry) { - + struct iommu_map_entry *nbr; + + /* Removing entry may open a new free gap before domain->start_gap. */ + if (entry->end <= domain->start_gap->end) { + if (RB_RIGHT(entry, rb_entry) != NULL) + nbr = iommu_gas_entries_tree_RB_NEXT(entry); + else if (RB_LEFT(entry, rb_entry) != NULL) + nbr = RB_LEFT(entry, rb_entry); + else + nbr = RB_PARENT(entry, rb_entry); + domain->start_gap = nbr; + } RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); } @@ -253,6 +264,7 @@ iommu_gas_init_domain(struct iommu_domain *domain) begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin); + domain->start_gap = end; domain->first_place = begin; domain->last_place = end; domain->flags |= IOMMU_DOMAIN_GAS_INITED; @@ -296,7 +308,6 @@ iommu_gas_fini_domain(struct iommu_domain *domain) } struct iommu_gas_match_args { - struct iommu_domain *domain; iommu_gaddr_t size; int offset; const struct bus_dma_tag_common *common; @@ -395,16 +406,44 @@ iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free) return (curr); } +/* + * Address-ordered first-fit search of 'domain' for free space satisfying the + * conditions of 'a'. The space allocated is at least one page big, and is + * bounded by guard pages to left and right. The allocated space for 'domain' + * is described by an rb-tree of map entries at domain->rb_root, and + * domain->start_gap points a map entry less than or adjacent to the first + * free-space of size at least 3 pages. + */ static int -iommu_gas_find_space(struct iommu_gas_match_args *a) +iommu_gas_find_space(struct iommu_domain *domain, + struct iommu_gas_match_args *a) { - struct iommu_domain *domain; struct iommu_map_entry *curr, *first; iommu_gaddr_t addr, min_free; - IOMMU_DOMAIN_ASSERT_LOCKED(a->domain); + IOMMU_DOMAIN_ASSERT_LOCKED(domain); KASSERT(a->entry->flags == 0, - ("dirty entry %p %p", a->domain, a->entry)); + ("dirty entry %p %p", domain, a->entry)); + + /* + * start_gap may point to an entry adjacent to gaps too small for any + * new allocation. In that case, advance start_gap to the first free + * space big enough for a minimum allocation plus two guard pages. + */ + min_free = 3 * IOMMU_PAGE_SIZE; + first = domain->start_gap; + while (first != NULL && first->free_down < min_free) + first = RB_PARENT(first, rb_entry); + for (curr = first; curr != NULL; + curr = iommu_gas_next(curr, min_free)) { + if ((first = RB_LEFT(curr, rb_entry)) != NULL && + first->last + min_free <= curr->start) + break; + if ((first = RB_RIGHT(curr, rb_entry)) != NULL && + curr->end + min_free <= first->first) + break; + } + domain->start_gap = curr; /* * If the subtree doesn't have free space for the requested allocation @@ -413,20 +452,13 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) min_free = 2 * IOMMU_PAGE_SIZE + roundup2(a->size + a->offset, IOMMU_PAGE_SIZE); - /* - * Find the first entry in the lower region that could abut a big-enough - * range. - */ - domain = a->domain; - curr = RB_ROOT(&domain->rb_root); - first = NULL; - while (curr != NULL && curr->free_down >= min_free) { - first = curr; - curr = RB_LEFT(curr, rb_entry); - } + /* Climb to find a node in the subtree of big-enough ranges. */ + first = curr; + while (first != NULL && first->free_down < min_free) + first = RB_PARENT(first, rb_entry); /* - * Walk the big-enough ranges until one satisfies alignment + * Walk the big-enough ranges tree until one satisfies alignment * requirements, or violates lowaddr address requirement. */ addr = a->common->lowaddr + 1; @@ -746,7 +778,6 @@ iommu_gas_map(struct iommu_domain *domain, KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0, ("invalid flags 0x%x", flags)); - a.domain = domain; a.size = size; a.offset = offset; a.common = common; @@ -757,7 +788,7 @@ iommu_gas_map(struct iommu_domain *domain, return (ENOMEM); a.entry = entry; IOMMU_DOMAIN_LOCK(domain); - error = iommu_gas_find_space(&a); + error = iommu_gas_find_space(domain, &a); if (error == ENOMEM) { IOMMU_DOMAIN_UNLOCK(domain); iommu_gas_free_entry(entry);