From nobody Wed Oct 12 03:00:24 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 4MnHT50JRbz4f7sR; Wed, 12 Oct 2022 03:00:25 +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 4MnHT5027rz4HL9; Wed, 12 Oct 2022 03:00:25 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543625; 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=3bQu5MdJMlJ/dJyAyTgK3Vq1+OKPS87hFQmCIB0E7lg=; b=G9bq39gqQotGbo5hPmDsZqOprqG27lND+4pMfAF5x2YEuSM4V7N8I3FZpJZEHtg7Ui08OZ M42MtSvTJRim+2G0hsgsO2vXBtZtIApH5WR4RpQI86pn25pJBmu47JAI0WEvFO6OIH3wq3 9LbeVvdcwlCuuNY0dSUIbta6OrETC2pVIoWAgN3Cv+gTMohcsooCRq38hS9H6KyeCNrc39 +sMOzCYAo3/lKaxlqFX0QrxaoHjFdBM2SPpaQ4OSOfYQzwqkBeuRObFz9CzOOEHwcO1+Lh xe4A8dfxzqdVIlRhX40ZAmJSQzKh6sSE4loMSMjH35pvHuqa3aILgWew149jHA== 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 4MnHT45xQDz19kF; Wed, 12 Oct 2022 03:00:24 +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 29C30Ojv079496; Wed, 12 Oct 2022 03:00:24 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 29C30Ows079495; Wed, 12 Oct 2022 03:00:24 GMT (envelope-from git) Date: Wed, 12 Oct 2022 03:00:24 GMT Message-Id: <202210120300.29C30Ows079495@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: cd6395519895 - stable/13 - rb_tree: augmentation shortcut 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: cd639551989539c94c251c81abaa23ab912374a1 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543625; 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=3bQu5MdJMlJ/dJyAyTgK3Vq1+OKPS87hFQmCIB0E7lg=; b=q4hlBAYGxBebSwwztmTNPKLQR9BwbMq+QCQsSZ7y68FG5ACIZ8pnqlky247ixip9S8liII Fy/6jzsgSlbUiu6vVmbRd/3lSvyZDEAJYkAvsqqC+Ol1Uml3u+PhRxZqFjTNzdfYf16FDi PxlugmenYlila46cSzS5CDleLgEwMco6BCkT9rWFeBf/O7uJEZ9cAl9qr39u0BjPGmWdlm a6J3Vt1YUo4pXde2oziWU9sP5O7cKbvvDWB+uzpn4fX5gjW5yuMsAdHdnwHuvThWoWWv07 BKqfqjRcglbdLhiAe+CFS/kX9TC4OiTjdNi6nkp5OLvl1kPRkTPcK92aT2J7Qw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1665543625; a=rsa-sha256; cv=none; b=mZ2qSxUsI+gI8rHd2g8I+AjndjEgkqg8pm69CfsXcEOrFV9WN87Q6NG1YjWDRkxpuwl8UY ECenxWkhKn1OPfp3bkMfL1Y/gkxzpfAbeK51pmxAeLZF1s6KQyuZWvw9/Lvyt57xlFEpsR 2OnClr9TK5NJazFoj6iLK/T34KibwW++EgdoED/LIOs0eLX6c+nlBA/YGDHW072wCBkNTU CXIXoT2RmP473OVbVUCJDFUcrSQPMDtnnFACyXR39SnaEveQFkvajucXhfXdqi1CU8h0tJ FCXO75kvYHm7cQ+ZVBPBSL3PgDVVsUwl2sJPTMIP2YyYkObv621d9kXZnJi7ug== 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=cd639551989539c94c251c81abaa23ab912374a1 commit cd639551989539c94c251c81abaa23ab912374a1 Author: Doug Moore AuthorDate: 2022-09-21 04:21:14 +0000 Commit: Doug Moore CommitDate: 2022-10-12 02:45:23 +0000 rb_tree: augmentation shortcut RB-tree augmentation maintains data in each node of the tree that represents the product of some associative operator applied to all the nodes of the subtree rooted at that node. If a node in the tree changes, augmentation data for the node is updated for that node and all nodes on the path from that node to the tree root. However, sometimes, augmenting a node changes no data in that node, particularly if the associated operation is something involving 'max' or 'min'. If augmentation changes nothing in a node, then the work of walking to the tree root from that point is pointless, because augmentation will change nothing in those nodes either. This change makes it possible to avoid that wasted work. Define RB_AUGMENT_CHECK as a macro much like RB_AUGMENT, but which returns a value 'true' when augmentation changes the augmentation data of a node, and false otherwise. Change code that unconditionally walks and augments to the top of tree to code that stops once an augmentation has no effect. In the case of rebalancing the tree after insertion or deletion, where previously a node rotated into the path was inevitably augmented on the march to the tree root, now check to see if it needs augmentation because the march to the tree root stopped before reaching it. Change the augmentation function in iommu_gas.c so that it returns true/false to indicate whether the augmentation had any effect. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36509 (cherry picked from commit b16f993ec2cafe48fae96ca0eb27224951b30d7e) --- share/man/man3/Makefile | 1 + share/man/man3/tree.3 | 19 +++++++++++ sys/dev/iommu/iommu_gas.c | 60 +++++++++++++++++++++++----------- sys/sys/tree.h | 82 +++++++++++++++++++++++++++++++++-------------- 4 files changed, 120 insertions(+), 42 deletions(-) diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile index fa4f751ce553..872aec1e83ab 100644 --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -320,6 +320,7 @@ MLINKS+= timeradd.3 timerclear.3 \ timeradd.3 timespecisset.3 \ timeradd.3 timespeccmp.3 MLINKS+= tree.3 RB_AUGMENT.3 \ + tree.3 RB_AUGMENT_CHECK.3 \ tree.3 RB_EMPTY.3 \ tree.3 RB_ENTRY.3 \ tree.3 RB_FIND.3 \ diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index 86d6569d1955..eaddc9f811c4 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -100,6 +100,7 @@ .Nm RB_REMOVE , .Nm RB_REINSERT , .Nm RB_AUGMENT +.Nm RB_AUGMENT_CHECK, .Nm RB_UPDATE_AUGMENT .Nd "implementations of splay and rank-balanced (wavl) trees" .Sh SYNOPSIS @@ -197,6 +198,8 @@ .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "void" .Fn RB_AUGMENT NAME "struct TYPE *elm" +.Ft "bool" +.Fn RB_AUGMENT_CHECK NAME "struct TYPE *elm" .Ft "void" .Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm" .Sh DESCRIPTION @@ -620,6 +623,22 @@ It is typically used to maintain some associative accumulation of tree elements, such as sums, minima, maxima, and the like. .Pp The +.Fn RB_AUGMENT_CHECK +macro updates augmentation data of the element +.Fa elm +in the tree. +By default, it does nothing and returns false. +If +.Fn RB_AUGMENT_CHECK +is defined, then when an element is inserted or removed from the tree, +it is invoked for every element in the tree that is the root of an +altered subtree, working from the bottom of the tree up toward the +top, until it returns false to indicate that it did not change the +element and so working further up the tree would change nothing. +It is typically used to maintain some associative accumulation of tree +elements, such as sums, minima, maxima, and the like. +.Pp +The .Fn RB_UPDATE_AUGMENT macro updates augmentation data of the element .Fa elm diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index 68e22f16c69f..c04edb8451b4 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -31,7 +31,7 @@ #include __FBSDID("$FreeBSD$"); -#define RB_AUGMENT(entry) iommu_gas_augment_entry(entry) +#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry) #include #include @@ -139,27 +139,41 @@ iommu_gas_cmp_entries(struct iommu_map_entry *a, struct iommu_map_entry *b) return (0); } -static void +/* + * Update augmentation data based on data from children. + * Return true if and only if the update changes the augmentation data. + */ +static bool iommu_gas_augment_entry(struct iommu_map_entry *entry) { struct iommu_map_entry *child; - iommu_gaddr_t free_down; + iommu_gaddr_t bound, delta, free_down; free_down = 0; + bound = entry->start; if ((child = RB_LEFT(entry, rb_entry)) != NULL) { - free_down = MAX(free_down, child->free_down); - free_down = MAX(free_down, entry->start - child->last); - entry->first = child->first; - } else - entry->first = entry->start; - + free_down = MAX(child->free_down, bound - child->last); + bound = child->first; + } + delta = bound - entry->first; + entry->first = bound; + bound = entry->end; if ((child = RB_RIGHT(entry, rb_entry)) != NULL) { free_down = MAX(free_down, child->free_down); - free_down = MAX(free_down, child->first - entry->end); - entry->last = child->last; - } else - entry->last = entry->end; + free_down = MAX(free_down, child->first - bound); + bound = child->last; + } + delta += entry->last - bound; + if (delta == 0) + delta = entry->free_down - free_down; + entry->last = bound; entry->free_down = free_down; + + /* + * Return true either if the value of last-first changed, + * or if free_down changed. + */ + return (delta != 0); } RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry, @@ -228,16 +242,26 @@ iommu_gas_init_domain(struct iommu_domain *domain) KASSERT(RB_EMPTY(&domain->rb_root), ("non-empty entries %p", domain)); - begin->start = 0; - begin->end = IOMMU_PAGE_SIZE; - begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; - iommu_gas_rb_insert(domain, begin); - + /* + * The end entry must be inserted first because it has a zero-length gap + * between start and end. Initially, all augmentation data for a new + * entry is zero. Function iommu_gas_augment_entry will compute no + * change in the value of (start-end) and no change in the value of + * free_down, so it will return false to suggest that nothing changed in + * the entry. Thus, inserting the end entry second prevents + * augmentation information to be propogated to the begin entry at the + * tree root. So it is inserted first. + */ end->start = domain->end; end->end = domain->end; end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; iommu_gas_rb_insert(domain, end); + begin->start = 0; + begin->end = IOMMU_PAGE_SIZE; + begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; + iommu_gas_rb_insert(domain, begin); + domain->first_place = begin; domain->last_place = end; domain->flags |= IOMMU_DOMAIN_GAS_INITED; diff --git a/sys/sys/tree.h b/sys/sys/tree.h index c0cd65f41acb..e10d92bb5ce6 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -357,18 +357,25 @@ struct { \ } while (/*CONSTCOND*/ 0) /* - * Something to be invoked in a loop at the root of every modified subtree, - * from the bottom up to the root, to update augmented node data. + * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of + * every modified subtree, from the bottom up to the root, to update augmented + * node data. RB_AUGMENT_CHECK returns true only when the update changes the + * node data, so that updating can be stopped short of the root when it returns + * false. */ +#ifndef RB_AUGMENT_CHECK #ifndef RB_AUGMENT -#define RB_AUGMENT(x) break +#define RB_AUGMENT_CHECK(x) false +#else +#define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), true) +#endif #endif #define RB_UPDATE_AUGMENT(elm, field) do { \ __typeof(elm) rb_update_tmp = (elm); \ - do { \ - RB_AUGMENT(rb_update_tmp); \ - } while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \ + while (RB_AUGMENT_CHECK(rb_update_tmp) && \ + (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL) \ + ; \ } while (0) #define RB_SWAP_CHILD(head, par, out, in, field) do { \ @@ -422,10 +429,10 @@ struct { \ #define RB_PROTOTYPE_RANK(name, type, attr) #endif #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name *, \ + attr struct type *name##_RB_INSERT_COLOR(struct name *, \ struct type *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name *, \ + attr struct type *name##_RB_REMOVE_COLOR(struct name *, \ struct type *, struct type *) #define RB_PROTOTYPE_REMOVE(name, type, attr) \ attr struct type *name##_RB_REMOVE(struct name *, struct type *) @@ -465,7 +472,16 @@ struct { \ RB_GENERATE_REINSERT(name, type, field, cmp, attr) #ifdef _RB_DIAGNOSTIC +#ifndef RB_AUGMENT +#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x) +#else +#define _RB_AUGMENT_VERIFY(x) false +#endif #define RB_GENERATE_RANK(name, type, field, attr) \ +/* \ + * Return the rank of the subtree rooted at elm, or -1 if the subtree \ + * is not rank-balanced, or has inconsistent augmentation data. + */ \ attr int \ name##_RB_RANK(struct type *elm) \ { \ @@ -482,7 +498,8 @@ name##_RB_RANK(struct type *elm) \ right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) + \ name##_RB_RANK(right); \ if (left_rank != right_rank || \ - (left_rank == 2 && left == NULL && right == NULL)) \ + (left_rank == 2 && left == NULL && right == NULL) || \ + _RB_AUGMENT_VERIFY(elm)) \ return (-1); \ return (left_rank); \ } @@ -491,7 +508,7 @@ name##_RB_RANK(struct type *elm) \ #endif #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ -attr void \ +attr struct type * \ name##_RB_INSERT_COLOR(struct name *head, \ struct type *parent, struct type *elm) \ { \ @@ -516,7 +533,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ if (_RB_BITS(gpar) & elmdir) { \ /* shorten the parent-elm edge to rebalance */ \ _RB_BITSUP(parent, field) ^= elmdir; \ - return; \ + return (NULL); \ } \ sibdir = elmdir ^ _RB_LR; \ /* the other edge must change length */ \ @@ -582,10 +599,11 @@ name##_RB_INSERT_COLOR(struct name *head, \ _RB_UP(child, field) = gpar; \ RB_SWAP_CHILD(head, gpar, parent, child, field); \ if (elm != child) \ - RB_AUGMENT(elm); \ - RB_AUGMENT(parent); \ - break; \ + RB_AUGMENT_CHECK(elm); \ + RB_AUGMENT_CHECK(parent); \ + return (child); \ } while ((parent = gpar) != NULL); \ + return (NULL); \ } #ifndef RB_STRICT_HST @@ -600,7 +618,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ #endif #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ -attr void \ +attr struct type * \ name##_RB_REMOVE_COLOR(struct name *head, \ struct type *parent, struct type *elm) \ { \ @@ -614,7 +632,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \ elm = parent; \ if ((parent = _RB_UP(elm, field)) == NULL) \ - return; \ + return (NULL); \ } \ do { \ /* the rank of the tree rooted at elm shrank */ \ @@ -624,7 +642,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ if (_RB_BITS(gpar) & elmdir) { \ /* lengthen the parent-elm edge to rebalance */ \ _RB_UP(parent, field) = gpar; \ - return; \ + return (NULL); \ } \ if (_RB_BITS(gpar) & _RB_LR) { \ /* shorten other edge, retry from parent */ \ @@ -707,11 +725,19 @@ name##_RB_REMOVE_COLOR(struct name *head, \ RB_SET_PARENT(elm, gpar, field); \ RB_SWAP_CHILD(head, gpar, parent, elm, field); \ if (sib != elm) \ - RB_AUGMENT(sib); \ - break; \ + RB_AUGMENT_CHECK(sib); \ + return (parent); \ } while (elm = parent, (parent = gpar) != NULL); \ + return (NULL); \ } +#define _RB_AUGMENT_WALK(elm, match, field) \ +do { \ + if (match == elm) \ + match = NULL; \ +} while (RB_AUGMENT_CHECK(elm) && \ + (elm = RB_PARENT(elm, field)) != NULL) + #define RB_GENERATE_REMOVE(name, type, field, attr) \ attr struct type * \ name##_RB_REMOVE(struct name *head, struct type *out) \ @@ -744,12 +770,18 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ if (child != NULL) \ _RB_UP(child, field) = parent; \ if (parent != NULL) { \ - name##_RB_REMOVE_COLOR(head, parent, child); \ + opar = name##_RB_REMOVE_COLOR(head, parent, child); \ /* if rotation has made 'parent' the root of the same \ * subtree as before, don't re-augment it. */ \ - if (parent == in && RB_LEFT(parent, field) == NULL) \ + if (parent == in && RB_LEFT(parent, field) == NULL) { \ + opar = NULL; \ parent = RB_PARENT(parent, field); \ - RB_UPDATE_AUGMENT(parent, field); \ + } \ + _RB_AUGMENT_WALK(parent, opar, field); \ + if (opar != NULL) { \ + RB_AUGMENT_CHECK(opar); \ + RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ + } \ } \ return (out); \ } @@ -776,8 +808,10 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ RB_SET(elm, parent, field); \ *tmpp = elm; \ if (parent != NULL) \ - name##_RB_INSERT_COLOR(head, parent, elm); \ - RB_UPDATE_AUGMENT(elm, field); \ + tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ + _RB_AUGMENT_WALK(elm, tmp, field); \ + if (tmp != NULL) \ + RB_AUGMENT_CHECK(tmp); \ return (NULL); \ }