| Message ID | 20240412082121.33382-2-yi.l.liu@intel.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | vfio-pci support pasid attach/detach | expand |
On Fri, 12 Apr 2024 01:21:18 -0700 Yi Liu <yi.l.liu@intel.com> 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@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; > + 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; > + 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. > + 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); bool ida_exists(struct ida *ida, unsigned int id) { return ida_find_first_range(ida, id, id) == id; } int ida_find_first(struct ida *ida) { return ida_find_first_range(ida, 0, ~0); } _min and _max variations of the latter would align with existing ida_alloc variants, but maybe no need to add them preemptively. 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, Alex > + > /** > * ida_free() - Release an allocated ID. > * @ida: IDA handle.
On 2024/4/17 00:03, Alex Williamson wrote: > On Fri, 12 Apr 2024 01:21:18 -0700 > Yi Liu <yi.l.liu@intel.com> 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@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; >> + > > 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); 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. >
On Thu, 18 Apr 2024 15:02:46 +0800 Yi Liu <yi.l.liu@intel.com> wrote: > On 2024/4/17 00:03, Alex Williamson wrote: > > On Fri, 12 Apr 2024 01:21:18 -0700 > > Yi Liu <yi.l.liu@intel.com> 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@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; > >> + > > > > 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. > > >
On Thu, Apr 18, 2024 at 10:23:14AM -0600, Alex Williamson wrote: > > 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); > } It should also always start from 0.. Ideally written more like: while ((id = ida_find_first(pasid_ida)) != EMPTY_IDA) { ida_remove(id); } Jason
On 2024/4/19 00:23, Alex Williamson wrote: > On Thu, 18 Apr 2024 15:02:46 +0800 > Yi Liu <yi.l.liu@intel.com> wrote: > >> On 2024/4/17 00:03, Alex Williamson wrote: >>> On Fri, 12 Apr 2024 01:21:18 -0700 >>> Yi Liu <yi.l.liu@intel.com> 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@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; >>>> + >>> >>> 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); > } aha, I see. :) > >> 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. >>> >> > >
On 2024/4/19 01:12, Jason Gunthorpe wrote: > On Thu, Apr 18, 2024 at 10:23:14AM -0600, Alex Williamson wrote: >>> 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); >> } > > It should also always start from 0.. any special reason to always start from 0? Here we want to loop all the IDs, and remove them. In this usage, it should be more efficient if we start from the last found ID. > Ideally written more like: > > while ((id = ida_find_first(pasid_ida)) != EMPTY_IDA) { > ida_remove(id); > }
On Fri, 19 Apr 2024 21:43:17 +0800 Yi Liu <yi.l.liu@intel.com> wrote: > On 2024/4/19 01:12, Jason Gunthorpe wrote: > > On Thu, Apr 18, 2024 at 10:23:14AM -0600, Alex Williamson wrote: > >>> 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); > >> } > > > > It should also always start from 0.. > > any special reason to always start from 0? Here we want to loop all the > IDs, and remove them. In this usage, it should be more efficient if we > start from the last found ID. In the above version, there's a possibility of an infinite loop, in the below there's not. I don't think the infinite loop is actually reachable, but given the xarray backend to ida I'm not sure you're gaining much to restart after the previously found id either. Thanks, Alex > > Ideally written more like: > > > > while ((id = ida_find_first(pasid_ida)) != EMPTY_IDA) { > > ida_remove(id); > > } >
On Fri, Apr 19, 2024 at 07:55:04AM -0600, Alex Williamson wrote: > On Fri, 19 Apr 2024 21:43:17 +0800 > Yi Liu <yi.l.liu@intel.com> wrote: > > > On 2024/4/19 01:12, Jason Gunthorpe wrote: > > > On Thu, Apr 18, 2024 at 10:23:14AM -0600, Alex Williamson wrote: > > >>> 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); > > >> } > > > > > > It should also always start from 0.. > > > > any special reason to always start from 0? Here we want to loop all the > > IDs, and remove them. In this usage, it should be more efficient if we > > start from the last found ID. > > In the above version, there's a possibility of an infinite loop, in the > below there's not. I don't think the infinite loop is actually > reachable, but given the xarray backend to ida I'm not sure you're > gaining much to restart after the previously found id either. Thanks, Right, there is no performance win on xarray and it only risks an infinite loop compared to: > > > while ((id = ida_find_first(pasid_ida)) != EMPTY_IDA) { > > > ida_remove(id); > > > } Which does not by construction Jason
On 2024/4/19 22:00, Jason Gunthorpe wrote: > On Fri, Apr 19, 2024 at 07:55:04AM -0600, Alex Williamson wrote: >> On Fri, 19 Apr 2024 21:43:17 +0800 >> Yi Liu <yi.l.liu@intel.com> wrote: >> >>> On 2024/4/19 01:12, Jason Gunthorpe wrote: >>>> On Thu, Apr 18, 2024 at 10:23:14AM -0600, Alex Williamson wrote: >>>>>> 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); >>>>> } >>>> >>>> It should also always start from 0.. >>> >>> any special reason to always start from 0? Here we want to loop all the >>> IDs, and remove them. In this usage, it should be more efficient if we >>> start from the last found ID. >> >> In the above version, there's a possibility of an infinite loop, in the >> below there's not. I don't think the infinite loop is actually >> reachable, but given the xarray backend to ida I'm not sure you're >> gaining much to restart after the previously found id either. Thanks, > > Right, there is no performance win on xarray and it only risks an > infinite loop compared to: > >>>> while ((id = ida_find_first(pasid_ida)) != EMPTY_IDA) { >>>> ida_remove(id); >>>> } > > Which does not by construction thanks, got you two. :) Let's go with below. < 0 should mean no ID found. while ((id = ida_find_first(pasid_ida)) < 0) { ida_free(id); }
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.
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(+)