From: Yi Liu <yi.l.liu@intel.com>
To: alex.williamson@redhat.com, jgg@nvidia.com, kevin.tian@intel.com
Cc: joro@8bytes.org, robin.murphy@arm.com, eric.auger@redhat.com,
nicolinc@nvidia.com, kvm@vger.kernel.org,
chao.p.peng@linux.intel.com, yi.l.liu@intel.com,
iommu@lists.linux.dev, baolu.lu@linux.intel.com,
zhenzhong.duan@intel.com, jacob.jun.pan@intel.com,
Matthew Wilcox <willy@infradead.org>
Subject: [PATCH v2 1/4] ida: Add ida_get_lowest()
Date: Fri, 12 Apr 2024 01:21:18 -0700 [thread overview]
Message-ID: <20240412082121.33382-2-yi.l.liu@intel.com> (raw)
In-Reply-To: <20240412082121.33382-1-yi.l.liu@intel.com>
There is no helpers for user to check if a given ID is allocated or not,
neither a helper to loop all the allocated IDs in an IDA and do something
for cleanup. With the two needs, a helper to get the lowest allocated ID
of a range can help to achieve it.
Caller can check if a given ID is allocated or not by:
int id = 200, rc;
rc = ida_get_lowest(&ida, id, id);
if (rc == id)
//id 200 is used
else
//id 200 is not used
Caller can iterate all allocated IDs by:
int id = 0;
while (!ida_is_empty(&pasid_ida)) {
id = ida_get_lowest(pasid_ida, id, INT_MAX);
if (id < 0)
break;
//anything to do with the allocated ID
ida_free(pasid_ida, pasid);
}
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Suggested-by: Jason Gunthorpe <jgg@nvidia.com>
Signed-off-by: Yi Liu <yi.l.liu@intel.com>
---
include/linux/idr.h | 1 +
lib/idr.c | 67 +++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 68 insertions(+)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index da5f5fa4a3a6..1dae71d4a75d 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -257,6 +257,7 @@ struct ida {
int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
void ida_free(struct ida *, unsigned int id);
void ida_destroy(struct ida *ida);
+int ida_get_lowest(struct ida *ida, unsigned int min, unsigned int max);
/**
* ida_alloc() - Allocate an unused ID.
diff --git a/lib/idr.c b/lib/idr.c
index da36054c3ca0..03e461242fe2 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -476,6 +476,73 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
}
EXPORT_SYMBOL(ida_alloc_range);
+/**
+ * ida_get_lowest - Get the lowest used ID.
+ * @ida: IDA handle.
+ * @min: Lowest ID to get.
+ * @max: Highest ID to get.
+ *
+ * Get the lowest used ID between @min and @max, inclusive. The returned
+ * ID will not exceed %INT_MAX, even if @max is larger.
+ *
+ * Context: Any context. Takes and releases the xa_lock.
+ * Return: The lowest used ID, or errno if no used ID is found.
+ */
+int ida_get_lowest(struct ida *ida, unsigned int min, unsigned int max)
+{
+ unsigned long index = min / IDA_BITMAP_BITS;
+ unsigned int offset = min % IDA_BITMAP_BITS;
+ unsigned long *addr, size, bit;
+ unsigned long flags;
+ void *entry;
+ int ret;
+
+ if (min >= INT_MAX)
+ return -EINVAL;
+ if (max >= INT_MAX)
+ max = INT_MAX;
+
+ xa_lock_irqsave(&ida->xa, flags);
+
+ entry = xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT);
+ if (!entry) {
+ ret = -ENOTTY;
+ goto err_unlock;
+ }
+
+ if (index > min / IDA_BITMAP_BITS)
+ offset = 0;
+ if (index * IDA_BITMAP_BITS + offset > max) {
+ ret = -ENOTTY;
+ goto err_unlock;
+ }
+
+ if (xa_is_value(entry)) {
+ unsigned long tmp = xa_to_value(entry);
+
+ addr = &tmp;
+ size = BITS_PER_XA_VALUE;
+ } else {
+ addr = ((struct ida_bitmap *)entry)->bitmap;
+ size = IDA_BITMAP_BITS;
+ }
+
+ bit = find_next_bit(addr, size, offset);
+
+ xa_unlock_irqrestore(&ida->xa, flags);
+
+ if (bit == size ||
+ index * IDA_BITMAP_BITS + bit > max)
+ return -ENOTTY;
+
+ return index * IDA_BITMAP_BITS + bit;
+
+err_unlock:
+ xa_unlock_irqrestore(&ida->xa, flags);
+ return ret;
+}
+EXPORT_SYMBOL(ida_get_lowest);
+
/**
* ida_free() - Release an allocated ID.
* @ida: IDA handle.
--
2.34.1
next prev parent reply other threads:[~2024-04-12 8:21 UTC|newest]
Thread overview: 72+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-12 8:21 [PATCH v2 0/4] vfio-pci support pasid attach/detach Yi Liu
2024-04-12 8:21 ` Yi Liu [this message]
2024-04-16 16:03 ` [PATCH v2 1/4] ida: Add ida_get_lowest() Alex Williamson
2024-04-18 7:02 ` Yi Liu
2024-04-18 16:23 ` Alex Williamson
2024-04-18 17:12 ` Jason Gunthorpe
2024-04-19 13:43 ` Yi Liu
2024-04-19 13:55 ` Alex Williamson
2024-04-19 14:00 ` Jason Gunthorpe
2024-04-23 7:19 ` Yi Liu
2024-04-19 13:40 ` Yi Liu
2024-04-12 8:21 ` [PATCH v2 2/4] vfio-iommufd: Support pasid [at|de]tach for physical VFIO devices Yi Liu
2024-04-16 9:01 ` Tian, Kevin
2024-04-16 9:24 ` Yi Liu
2024-04-16 9:47 ` Tian, Kevin
2024-04-18 7:04 ` Yi Liu
2024-04-23 12:43 ` Jason Gunthorpe
2024-04-24 0:33 ` Tian, Kevin
2024-04-24 4:48 ` Yi Liu
2024-04-12 8:21 ` [PATCH v2 3/4] vfio: Add VFIO_DEVICE_PASID_[AT|DE]TACH_IOMMUFD_PT Yi Liu
2024-04-16 9:13 ` Tian, Kevin
2024-04-16 9:36 ` Yi Liu
2024-04-23 12:45 ` Jason Gunthorpe
2024-04-12 8:21 ` [PATCH v2 4/4] vfio: Report PASID capability via VFIO_DEVICE_FEATURE ioctl Yi Liu
2024-04-16 9:40 ` Tian, Kevin
2024-04-16 17:57 ` Alex Williamson
2024-04-17 7:09 ` Tian, Kevin
2024-04-17 20:25 ` Alex Williamson
2024-04-18 0:21 ` Tian, Kevin
2024-04-18 8:23 ` Yi Liu
2024-04-18 16:34 ` Alex Williamson
2024-04-23 12:39 ` Jason Gunthorpe
2024-04-24 0:24 ` Tian, Kevin
2024-04-24 13:59 ` Jason Gunthorpe
2024-04-16 8:38 ` [PATCH v2 0/4] vfio-pci support pasid attach/detach Tian, Kevin
2024-04-16 17:50 ` Jason Gunthorpe
2024-04-17 7:16 ` Tian, Kevin
2024-04-17 12:20 ` Jason Gunthorpe
2024-04-17 23:02 ` Alex Williamson
2024-04-18 0:06 ` Tian, Kevin
2024-04-18 9:03 ` Yi Liu
2024-04-18 20:37 ` Alex Williamson
2024-04-19 5:52 ` Tian, Kevin
2024-04-19 16:35 ` Alex Williamson
2024-04-23 7:43 ` Tian, Kevin
2024-04-23 12:01 ` Jason Gunthorpe
2024-04-23 23:47 ` Tian, Kevin
2024-04-24 0:12 ` Jason Gunthorpe
2024-04-24 2:57 ` Tian, Kevin
2024-04-24 12:29 ` Baolu Lu
2024-04-24 14:04 ` Jason Gunthorpe
2024-04-24 5:19 ` Tian, Kevin
2024-04-24 14:15 ` Jason Gunthorpe
2024-04-24 18:38 ` Alex Williamson
2024-04-24 18:45 ` Jason Gunthorpe
2024-04-24 18:24 ` Alex Williamson
2024-04-24 18:36 ` Jason Gunthorpe
2024-04-24 20:13 ` Alex Williamson
2024-04-26 14:11 ` Jason Gunthorpe
2024-04-26 20:13 ` Alex Williamson
2024-04-28 6:19 ` Tian, Kevin
2024-04-29 7:43 ` Yi Liu
2024-04-29 17:15 ` Jason Gunthorpe
2024-04-29 17:44 ` Jason Gunthorpe
2024-04-27 5:05 ` Christoph Hellwig
2024-04-25 9:26 ` Yi Liu
2024-04-25 12:58 ` Alex Williamson
2024-04-26 9:01 ` Yi Liu
2024-04-19 13:59 ` Jason Gunthorpe
2024-04-23 7:58 ` Yi Liu
2024-04-23 12:05 ` Jason Gunthorpe
2024-04-19 13:34 ` Jason Gunthorpe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240412082121.33382-2-yi.l.liu@intel.com \
--to=yi.l.liu@intel.com \
--cc=alex.williamson@redhat.com \
--cc=baolu.lu@linux.intel.com \
--cc=chao.p.peng@linux.intel.com \
--cc=eric.auger@redhat.com \
--cc=iommu@lists.linux.dev \
--cc=jacob.jun.pan@intel.com \
--cc=jgg@nvidia.com \
--cc=joro@8bytes.org \
--cc=kevin.tian@intel.com \
--cc=kvm@vger.kernel.org \
--cc=nicolinc@nvidia.com \
--cc=robin.murphy@arm.com \
--cc=willy@infradead.org \
--cc=zhenzhong.duan@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.