From nobody Mon Nov 21 08:25:39 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 4NG0nv37w1z4j3R9; Mon, 21 Nov 2022 08:25:39 +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 4NG0nv2ZJMz3KFf; Mon, 21 Nov 2022 08:25:39 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1669019139; 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=7HLpLmy8r2ZLUAKRTAEF1zGEYb3co9yBz3eIAANS+eo=; b=j6+cBzN8dbMrlf5Vnr1j04AixxEOsQhBI3XSbV85rAXjeBmuvVbBlqR4XnbJgpRHNKrb3u CVLMqwhJnxUuX6JxaSAqM60UIFubLW5POkZngQ49dIOvGnSEj0dwyEAakBg5apfo23O95R peTi6TGsWxw201fCUzj6271Ox8FFOiHMa+zGF90KvixPr9KQeYloB8YaW2/8487lJ8NPn4 ETKB0H0Muv84bDlkzDzR0ZVwDO7SvwUIL+VkKCWw0FF3Fx5ft0i/rG3qj5GtO4/Tf0lsFC EanAhJEkd3jXTiAkvuAYogeeG33hBCozYEzS6k97FP0dcyACEaLd+LgJqD17sg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1669019139; 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=7HLpLmy8r2ZLUAKRTAEF1zGEYb3co9yBz3eIAANS+eo=; b=qSXIgENi3CxtCOy49J6E1Ywve+xZdKW7pprnxK15/RI5JwfthL4Xt+S8gXm1L3MuufuVva 60yFga2yX5Om1HurtqoB7mkpMIU09iz/xJfnrS+2PqwOka9Aadk2k+81JBK3n+MHPeD+K7 pk2riQvG28S5lKFi3MjD3GsIYlf7tiiu9OGB+2y7ufa45vet0IF29PKZfLFHthAeeZMdBV DWUzHKTv07VwtzSOP82aNp9K5aEYRNaMIi3CFQ94baGTO1tRmQTwlTOtsJHtJXF6hp+YRQ fQGVOu96esbPxjXvtexXijsKY6L261PPSjG58kSYRlbAhFpBofYHDF1VnyWQHA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1669019139; a=rsa-sha256; cv=none; b=nra3vBgheWsY/mh3TwMCi40z9Hc1ffe2FNibq3Wxyp/W+yX1+fuesKTNneTd/hBsMpWJ/A egsgXACDmKE3t+AHtMa7ApQ77ZRA1GTIDGP/tVNshDO5MEmoD1lVRXbRX1ctON3MY/L0kl nUHvOVBlPs2S+RMiG6dfa0tRahSHmMiDNRb6E+UQ5dm7WPr2fHm0gW504Ru8z4cK5R2fop YrPOVmgTroTDmceWyIFHQnrGgkgNjQYxOX5Ky3lzK2cvvlMlwgxIYXcgO+2CbZvjAO7OGq mlM2VXIWQDwuo7gtTARH9NG18TnY3X4JkH62i9auCls6HcHV1zUMCC5dtCX75w== 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 4NG0nv1bdVzwTQ; Mon, 21 Nov 2022 08:25:39 +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 2AL8PdDw015628; Mon, 21 Nov 2022 08:25:39 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2AL8PdmM015627; Mon, 21 Nov 2022 08:25:39 GMT (envelope-from git) Date: Mon, 21 Nov 2022 08:25:39 GMT Message-Id: <202211210825.2AL8PdmM015627@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: db151ca0c343 - stable/13 - iommu_gas: start space search from 1st free space 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: db151ca0c343531256b8839f938a4ecbd8b4fd7e Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=db151ca0c343531256b8839f938a4ecbd8b4fd7e commit db151ca0c343531256b8839f938a4ecbd8b4fd7e Author: Doug Moore AuthorDate: 2022-10-29 05:50:44 +0000 Commit: Doug Moore CommitDate: 2022-11-21 08:24:57 +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 (cherry picked from commit 8b221ca631c2d28584a4b6207dc107d8ff5a1b2f) --- 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);