Re: [PATCH v3 03/15] interval-tree: Add a utility to iterate over spans in an interval tree

From: Jason Gunthorpe <jgg@nvidia.com>
To: "Tian, Kevin" <kevin.tian@intel.com>
Cc: Lu Baolu <baolu.lu@linux.intel.com>,
	"bpf@vger.kernel.org" <bpf@vger.kernel.org>,
	Jonathan Corbet <corbet@lwn.net>,
	David Woodhouse <dwmw2@infradead.org>,
	"iommu@lists.linux.dev" <iommu@lists.linux.dev>,
	Joerg Roedel <joro@8bytes.org>,
	"linux-doc@vger.kernel.org" <linux-doc@vger.kernel.org>,
	"linux-kselftest@vger.kernel.org"
	<linux-kselftest@vger.kernel.org>,
	"llvm@lists.linux.dev" <llvm@lists.linux.dev>,
	Nathan Chancellor <nathan@kernel.org>,
	Nick Desaulniers <ndesaulniers@google.com>,
	Miguel Ojeda <ojeda@kernel.org>,
	Robin Murphy <robin.murphy@arm.com>,
	Shuah Khan <shuah@kernel.org>,
	Suravee Suthikulpanit <suravee.suthikulpanit@amd.com>,
	Tom Rix <trix@redhat.com>, Will Deacon <will@kernel.org>,
	Alex Williamson <alex.williamson@redhat.com>,
	Chaitanya Kulkarni <chaitanyak@nvidia.com>,
	Cornelia Huck <cohuck@redhat.com>,
	Daniel Jordan <daniel.m.jordan@oracle.com>,
	David Gibson <david@gibson.dropbear.id.au>,
	Eric Auger <eric.auger@redhat.com>,
	Eric Farman <farman@linux.ibm.com>,
	Jason Wang <jasowang@redhat.com>,
	Jean-Philippe Brucker <jean-philippe@linaro.org>,
	"Martins, Joao" <joao.m.martins@oracle.com>,
	"kvm@vger.kernel.org" <kvm@vger.kernel.org>,
	Matthew Rosato <mjrosato@linux.ibm.com>,
	"Michael S. Tsirkin" <mst@redhat.com>,
	Nicolin Chen <nicolinc@nvidia.com>,
	Niklas Schnelle <schnelle@linux.ibm.com>,
	Shameerali Kolothum Thodi <shameerali.kolothum.thodi@huawei.com>,
	"Liu, Yi L" <yi.l.liu@intel.com>,
	Keqian Zhu <zhukeqian1@huawei.com>
Subject: Re: [PATCH v3 03/15] interval-tree: Add a utility to iterate over spans in an interval tree
Date: Fri, 4 Nov 2022 16:38:19 -0300	[thread overview]
Message-ID: <Y2VqK3m9i6FlQd9+@nvidia.com> (raw)
In-Reply-To: <BN9PR11MB527666424E77F8417DF1BF4C8C389@BN9PR11MB5276.namprd11.prod.outlook.com>

On Thu, Nov 03, 2022 at 05:31:17AM +0000, Tian, Kevin wrote:
> > From: Jason Gunthorpe <jgg@nvidia.com>
> > Sent: Wednesday, October 26, 2022 2:12 AM
> > +/*
> > + * This iterator travels over spans in an interval tree. It does not return
> > + * nodes but classifies each span as either a hole, where no nodes intersect,
> > or
> > + * a used, which is fully covered by nodes. Each iteration step toggles
> > between
> > + * hole and used until the entire range is covered. The returned spans
> > always
> > + * fully cover the requested range.
> > + *
> > + * The iterator is greedy, it always returns the largest hole or used possible,
> > + * consolidating all consecutive nodes.
> > + *
> > + * Only is_hole, start_hole/used and last_hole/used are part of the external
> > + * interface.
> 
> slightly better readability if moving this sentence into the structure as
> the break line

Do you mean like this?

@@ -37,13 +37,16 @@ interval_tree_iter_next(struct interval_tree_node *node,
  * The iterator is greedy, it always returns the largest hole or used possible,
  * consolidating all consecutive nodes.
- *
- * Only is_hole, start_hole/used and last_hole/used are part of the external
- * interface.
  */
 struct interval_tree_span_iter {
 	struct interval_tree_node *nodes[2];
 	unsigned long first_index;
 	unsigned long last_index;
+
+	/*
+	 * Only is_hole, start_hole/used and last_hole/used are part of the
+	 * external interface.
+	 */
 	union {
 		unsigned long start_hole;
 		unsigned long start_used;

> > +void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter,
> > +				     struct rb_root_cached *itree,
> > +				     unsigned long new_index)
> > +{
> > +	if (iter->is_hole == -1)
> > +		return;
> > +
> > +	iter->first_index = new_index;
> > +	if (new_index == iter->last_index) {
> > +		iter->is_hole = -1;
> > +		return;
> > +	}
> > +
> > +	/* Rely on the union aliasing hole/used */
> > +	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {
> 
> "<=" to "<"
> 
> > +		iter->start_hole = new_index;
> > +		return;
> > +	}

Hrm, I don't think so..  This is testing if new_index is valid for the
current span. new_index == start_XXX is a valid index of the span and
new_index == last_XX is also a valid index, so either of them should
just update start_XX and do nothing else.

Thanks,
Jason
