On Thu, 18 Apr 2024 15:02:46 +0800 Yi Liu <yi.l.liu@xxxxxxxxx> wrote: > On 2024/4/17 00:03, Alex Williamson wrote: > > On Fri, 12 Apr 2024 01:21:18 -0700 > > Yi Liu <yi.l.liu@xxxxxxxxx> wrote: > > > >> 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@xxxxxxxxxxxxx> > >> Suggested-by: Jason Gunthorpe <jgg@xxxxxxxxxx> > >> Signed-off-by: Yi Liu <yi.l.liu@xxxxxxxxx> > >> --- > >> 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; > >> + > > > > Could these be made consistent with the test in ida_alloc_range(), ie: > > > > if ((int)min < 0) > > return -EINVAL; > > if ((int)max < 0) > > max = INT_MAX; > > > > sure. > > >> + xa_lock_irqsave(&ida->xa, flags); > >> + > >> + entry = xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT); > >> + if (!entry) { > >> + ret = -ENOTTY; > > > > -ENOENT? Same for all below too. > > I see. > > >> + 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); > > > > The API is a bit awkward to me, I wonder if it might be helped with > > some renaming and wrappers... > > > > int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max); > > ok. > > > bool ida_exists(struct ida *ida, unsigned int id) > > { > > return ida_find_first_range(ida, id, id) == id; > > } > > this does helps in next patch. > > > > > int ida_find_first(struct ida *ida) > > { > > return ida_find_first_range(ida, 0, ~0); > > } > > > > perhaps it can be added in future. This series has two usages. One is to > check if a given ID is allocated. This can be covered by your ida_exists(). > Another usage is to loop each IDs, do detach and free. This can still use > the ida_find_first_range() like the example in the commit message. The > first loop starts from 0, and next would start from the last found ID. > This may be more efficient than starts from 0 in every loop. > > > > _min and _max variations of the latter would align with existing > > ida_alloc variants, but maybe no need to add them preemptively. > > yes. > > > Possibly an ida_for_each() could be useful in the use case of > > disassociating each id, but not required for the brute force iterative > > method. Thanks, > > yep. maybe we can start with the below code, no need for ida_for_each() > today. > > > int id = 0; > > while (!ida_is_empty(&pasid_ida)) { > id = ida_find_first_range(pasid_ida, id, INT_MAX); You've actually already justified the _min function here: static inline int ida_find_first_min(struct ida *ida, unsigned int min) { return ida_find_first_range(ida, min, ~0); } Thanks, Alex > if (unlikely(WARN_ON(id < 0)) > break; > iommufd_device_pasid_detach(); > ida_free(pasid_ida, pasid); > } > > > > >> + > >> /** > >> * ida_free() - Release an allocated ID. > >> * @ida: IDA handle. > > >