Matthew Wilcox [Fri, 15 Feb 2019 20:08:36 +0000 (15:08 -0500)]
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>
Matthew Wilcox [Sun, 10 Feb 2019 04:14:03 +0000 (23:14 -0500)]
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>
Matthew Wilcox [Sun, 6 Jan 2019 20:23:54 +0000 (15:23 -0500)]
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>
Matthew Wilcox [Fri, 2 Nov 2018 03:26:21 +0000 (23:26 -0400)]
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>
Matthew Wilcox (Oracle) [Sun, 4 Aug 2019 11:20:30 +0000 (07:20 -0400)]
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>
Matthew Wilcox [Mon, 29 Oct 2018 16:26:24 +0000 (12:26 -0400)]
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>
Matthew Wilcox [Mon, 17 Dec 2018 23:05:18 +0000 (18:05 -0500)]
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>
Matthew Wilcox [Thu, 18 Oct 2018 20:15:35 +0000 (16:15 -0400)]
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>
Matthew Wilcox [Wed, 17 Oct 2018 18:19:14 +0000 (14:19 -0400)]
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>
Matthew Wilcox [Tue, 16 Oct 2018 21:01:23 +0000 (17:01 -0400)]
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>
Matthew Wilcox [Sat, 13 Oct 2018 11:47:30 +0000 (07:47 -0400)]
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>
Matthew Wilcox [Sun, 30 Sep 2018 04:12:02 +0000 (00:12 -0400)]
xen: Convert pvcalls-back to XArray
Pull the XArray out from under the semaphore as it is serialised by its
own spinlock. In pvcalls_back_release(), it's more efficient to erase
the element than to load it then erase it if it was present.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Matthew Wilcox [Wed, 26 Sep 2018 15:02:10 +0000 (11:02 -0400)]
sh: intc: Convert to XArray
The radix tree was being protected by a raw spinlock. I believe that
was not necessary, and the new internal regular spinlock will be
adequate for this array.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Matthew Wilcox [Wed, 26 Sep 2018 12:26:00 +0000 (08:26 -0400)]
irqdomain: Convert to XArray
This is a pretty straightforward conversion; mostly just removing
now-redundant locking. The only thing of note is just how much simpler
irq_domain_fix_revmap() becomes.
Signed-off-by: Matthew Wilcox <willy@infradead.org> Acked-by: Marc Zyngier <marc.zyngier@arm.com>
Matthew Wilcox [Tue, 25 Sep 2018 22:05:32 +0000 (18:05 -0400)]
vmalloc: Convert to XArray
The radix tree of vmap blocks is simpler to express as an XArray.
Saves a couple of hundred bytes of text and eliminates a user of the
radix tree preload API.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Matthew Wilcox [Tue, 25 Sep 2018 22:06:27 +0000 (18:06 -0400)]
mm: Convert cgroup writeback to XArray
We're still under the protection of the cgwb_lock as well as the xa_lock.
It could probably be removed or reduced in scope in a few places, but
I'll leave that to someone who understands this code better than I do.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Matthew Wilcox [Fri, 11 Jan 2019 20:05:50 +0000 (15:05 -0500)]
inotify: Convert IDR of marks to XArray
The IDR was being used in a somewhat complicated way where we'd look up
a mark to be deleted in the IDR, then pass it into the fsnotify machinery
which would pass the mark back to us, then we'd look it up again in order
to delete it. Just deleting it from the XArray in the first place lets
us simplify the reference counting tremendously.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Matthew Wilcox [Sat, 3 Nov 2018 16:14:05 +0000 (12:14 -0400)]
nfs: Convert cb_ident_idr to XArray
Rename it to cb_ids. The XArray does not need a 'destroy' function to
be called, so remove all trace of nfs_cleanup_cb_ident_idr(). Pass the
nfs_net parameter to nfs_cb_id_remove_locked() so it doesn't have to
look that up again.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
projects / users / willy / xarray.git / log