spi: Convert spi_master_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

soc/qcom: Convert svcs_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rpmsg: Convert endpoints to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

reset: Convert reset-ti-sci to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

remoteproc: Convert notifyids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pps: Convert pps_idr to XArray

The pps_idr_lock mutex is unnecessary thanks to the included xa_lock.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

powercap: Convert IDRs to IDAs

Signed-off-by: Matthew Wilcox <willy@infradead.org>

power: Convert ds2782_battery to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

power: Convert bq27xxx_battery to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

power: Convert bq2415x_charger to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pci: Convert endpoint functions_idr to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

of: Convert ovcs_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ubiblock: Convert ubiblock_minor_idr to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

mtdcore: Convert mtd_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

scif: Convert scif_ports to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

mei: Convert mei_idr to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

i3c: Convert i3c_bus_idr to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

i2c: Convert i2c_adapter_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

events: Convert pmu_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

workqueue: Convert to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ac97: Convert ac97_adapter_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

fpga: Convert dfl idrs to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

firewire: Convert firewire_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

nicstar: Convert to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

arm_scmi: Convert scmi_protocols to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

idr: Handle integer overflow correctly

If there is an entry at INT_MAX then idr_for_each_entry() will increment
id after handling it.  This is undefined behaviour, and is caught by
UBSAN.  Adding 1U to id forces the operation to be carried out as an
unsigned addition which (when assigned to id) will result in INT_MIN.
Since there is never an entry stored at INT_MIN, idr_get_next() will
return NULL, ending the loop as expected.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

Remove idr_for_each()

With no more users remaining, delete the function.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

arm_scmi: Convert tx_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

target_core_user: Convert comamnds IDR to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

Remove idr_preload

With all users gone, we can delete the implementation and various pieces
of infrastructure that it used.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

visorhba: Convert to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

idr: Remove idr_replace()

All users are now converted.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

tifm: Convert to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

cxl: Convert adapter_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

cxl: Convert contexts_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rtsx_pcr: Convert to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

irq: Convert timings to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

tpm: Convert dev_nums to XArray

Also fix a couple of memory leaks on allocation failure.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

vmscan: Convert shrinker_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

memcontrol: Convert mem_cgroup IDR to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

c2port: Convert IDR to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

tee: Convert shm IDR to XArray

Also remove the unused shm_list

Signed-off-by: Matthew Wilcox <willy@infradead.org>

mspro_block: Convert disks IDR to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ms_block: Convert disk IDR to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

memstick: Convert host IDR to IDA

Signed-off-by: Matthew Wilcox <willy@infradead.org>

iscsi_target: Convert g_tiqn_list and tiqn_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

iommu: Convert intel_pasid to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

idr: Remove idr_alloc_u32

The last user is now gone, so remove the export of this function.
It reamins as a static function as it is used by idr_alloc(), and it's not
worth simplifying the source code since idr_alloc should be removed soon.
Also remove idr_get_next_ul() and idr_for_each_entry_ul().

Signed-off-by: Matthew Wilcox <willy@infradead.org>

apparmor: Convert aa_secids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

IDR: Remove idr_alloc_cyclic

With all users now converted to XArray, remove this API.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

bpf: Convert map & prog IDRs to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

bpf: Convert btf_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

target: Convert devices_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

soc: qcom: Convert txns to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

slimbus: Convert tid_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rpmsg: Convert riids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rpmsg; Convert liids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rpmsg: Convert rcids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rpmsg: Convert lcids to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

rapidio: Convert ch_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

x86,hyperv: Convert conn_to_evt to XArray

This IDR wasn't being used to allocate IDs, just as somewhere to store
pointers.  It moves out from under the protection of the mutex to its
own spinlock.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

scsi: Convert same_target_siblings to XArray

Generally each target has only one LUN, so the target will have a direct
pointer to the sdev.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

firewire: Convert resource_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

dca: Convert dca_idr to IDA

The DCA code never looks up the pointer it stores in the IDR, so it
can use the IDA which is more efficient and easier to use.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

dm: Convert _minor_idr to XArray

Drop the use of the custom MINOR_ALLOCATED define in favour of using the
ability to allocate an index for a NULL pointer.  Rename the structure
to dm_minors.

It's probably possible to replace the _minor_lock with the xa_lock, but
it might be better to separate out the multiple things which are being
protected.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

cgroup: Convert cgroup_hierarchy to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

cgroup: Convert css_idr to XArray

Remove the internal wrappers as the XArray behaves exactly how the
cgroup code wishes the IDR did.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

cgroup: Convert cgroup_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ipc: Convert ipcs_idr to XArray

The XArray has better loops than the IDR has, removing the need to
open-code them.  We also don't need to call idr_destroy() any more.
Allocating the ID is a little tricky due to needing to get 'seq'
correct.  Open-code a variant of __xa_alloc() which lets us set the
ID and the seq before depositing the pointer in the array.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove more unused functions

radix_tree_insert, radix_tree_delete, radix_tree_tag_set and
radix_tree_tag_clear are all now unused.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove unused iteration code

The ability to iterate over tags or iterate contiguously,
radix_tree_iter_delete(), radix_tree_iter_resume(),
radix_tree_iter_retry() and radix_tree_iter_lookup() are all now unused.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove radix_tree_{insert,replace}_slot

Now unused.  Also radix_tree_deref_slot, radix_tree_deref_slot_protected,
radix_tree_deref_retry and radix_tree_exception.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove radix_tree_gang_lookup*

Users of these functions have all been converted to use xa_extract().

Signed-off-by: Matthew Wilcox <willy@infradead.org>

XArray: Remove radix tree compatibility

The xa_flags field in the XArray was compatible with the radix tree
in order to make conversion easier.  With the page cache converted,
all future conversions will be done one data structure at a time, so
there is no more need for this compatibility.  This reduces the header
dependencies of the XArray to not require gfp.h, which would otherwise
introduce a header loop in a later patch.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree test suite: Convert to XArray

With only the IDR remaining as a user of the radix tree API, convert
the non-IDR pieces of the radix tree test suite to the XArray API.

radix tree test suite: Convert regression4 to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree test suite: Convert regression3 to XArray

Move the test to the in-kernel test suite

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pinctrl: Convert pin_desc_tree to XArray

Straightforward conversion; no locking changes.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pinctrl: Convert pin_function_tree to XArray

Straightforward conversion; no locking changes.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pinctrl: Convert pin_group_tree to XArray

Straightforward conversion; no locking changes.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

powerpc: Remove obsolete radix-tree includes

This code hasn't used the radix tree API since 2012.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

c6x: Remove unused radix-tree includes

These files do not use the radix tree API.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

nvme target: Convert p2p_ns_map to XArray

Straightforward conversion, no locking changes.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

dm-zoned-target: Convert to XArray

Switch the locking from a mutex to the xa spinlock.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

pwm: Convert to XArray

Straightforward conversion.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

scsi: tcmu: Convert to XArray

I used xa_for_each() instead of a counting loop which will speed up
deleting sparsely-populated devices.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

irqdesc: Convert to XArray

There was no locking here to convert; possibly this is a bugfix, or
maybe simultaneous modification was excluded in some other way.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ocxl: Convert minors_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ocxl: Convert contexts_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ocxl: Convert irq_idr to XArray

Signed-off-by: Matthew Wilcox <willy@infradead.org>

ocxl: Convert pe_tree to XArray

Straightforward conversion.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

dma-debug: Convert to XArray

The dma-debug code was using the radix tree tags in a tremendously
inefficient way.  Instead, chain dma entries which hit the same
cacheline just like the s390 and btrfs code do.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove preload API

With all callers gone, we can remove the radix_tree_preload API.
The mechanism remains in order to support the IDR preload API.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

erofs: Convert workstn_tree to XArray

Rename it to compression_work as a better reflection of what it's for.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

hwspinlock: Convert to XArray

I had to mess with the locking a bit as I converted the code from a
mutex to the xa_lock.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree: Remove radix_tree_maybe_preload

This function is now unused; delete it.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

md: Convert raid5-cache to XArray

This is the first user of the radix tree I've converted which was
storing numbers rather than pointers.  I'm fairly pleased with how
well it came out.  There's less boiler-plate involved than there was
with the radix tree, so that's a win.  It does use the advanced API,
and I think that's a signal that there needs to be a separate API for
using the XArray for only integers.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

s390: Convert vsie to XArray

No locking conversion, just using the new API.

Signed-off-by: Matthew Wilcox <willy@infradead.org>

s390: Convert gmap to XArray

The three radix trees in gmap are all converted to the XArray.
This is another case where the multiple locks held mandates the use
of the xa_reserve() API.  The gmap_insert_rmap() function is
considerably simplified by using the advanced API;
gmap_radix_tree_free() turns out to just be xa_destroy(), and
gmap_rmap_radix_tree_free() is a nice little iteration followed
by xa_destroy().

Signed-off-by: Matthew Wilcox <willy@infradead.org>

radix tree tests: Convert regression2 to XArray

The regression2 test was the last user of
radix_tree_gang_lookup_tag_slot() and was testing functionality that
was only used by the page cache, so it makes sense to convert it to
the XArray.  The actual bug that it attempts to catch was really in
radix_tree_range_tag_if_tagged() which was deleted months ago.

Signed-off-by: Matthew Wilcox <willy@infradead.org>