mm: Microoptimise truncate xarray calls

By passing the xa_state to __clear_shadow_entry(), we can set up the
xa_state once per batch instead of once per shadow entry.  This only
has a tiny effect on Jan's benchmark, but it has no downside.

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

coresight: Convert etr_bufs to XArray

Use an XArray instead of an IDR to hold the etr_bufs.  The cmpxchg
operator leads to simpler code than the prior allocation code.  We don't
need the mutex any more as the XArray contains its own spinlock to
protect against simultaneous modifications.

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

xilinx_sdfec: Convert to IDA

This driver does not use the lookup abilities of the IDR, so convert it
to the more space-efficient IDA.

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

fastrpc: Convert ctxt_idr to XArray

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

habanalabs: Convert phys_pg_pack_handles to XArray

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

habanalabs: Convert ctx_handles to XArray

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

habanalabs: Convert cb_handles to XArray

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

habanalabs: Convert hl_devs_idr to XArray

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

mps2-uart: Convert ports_idr to XArray

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

interconnect: Convert icc_idr to XArray

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

XArray: Remove xa_reserve & xa_release

These turned out not to be needed.

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

radix-tree, idr: Remove IDR

All users are gone.

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

mtty: Remove unused IDR

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

chtls: Remove unused IDRs

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

vfio: Convert group_idr to XArray

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

uio: Convert uio_idr to XArray

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

optee: Convert supp to XArray

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

bcm2835-camera: Convert context_map to XArray

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

pi433: Convert pi433_idr to XArray

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

greybus: Convert uart tty_minors to XArray

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

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>