From: Matthew Wilcox <willy@infradead.org>
To: linux-fsdevel@vger.kernel.org, linux-mm@kvack.org,
linux-kernel@vger.kernel.org
Cc: Matthew Wilcox <mawilcox@microsoft.com>
Subject: [PATCH 43/62] brd: Convert to XArray
Date: Wed, 22 Nov 2017 13:07:20 -0800 [thread overview]
Message-ID: <20171122210739.29916-44-willy@infradead.org> (raw)
In-Reply-To: <20171122210739.29916-1-willy@infradead.org>
From: Matthew Wilcox <mawilcox@microsoft.com>
Convert brd_pages from a radix tree to an XArray. Simpler and smaller
code; in particular another user of radix_tree_preload is eliminated.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
drivers/block/brd.c | 87 ++++++++++++++---------------------------------------
1 file changed, 23 insertions(+), 64 deletions(-)
diff --git a/drivers/block/brd.c b/drivers/block/brd.c
index 8028a3a7e7fd..c9fda03810ea 100644
--- a/drivers/block/brd.c
+++ b/drivers/block/brd.c
@@ -17,7 +17,7 @@
#include <linux/bio.h>
#include <linux/highmem.h>
#include <linux/mutex.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
#include <linux/fs.h>
#include <linux/slab.h>
#include <linux/backing-dev.h>
@@ -29,9 +29,9 @@
#define PAGE_SECTORS (1 << PAGE_SECTORS_SHIFT)
/*
- * Each block ramdisk device has a radix_tree brd_pages of pages that stores
- * the pages containing the block device's contents. A brd page's ->index is
- * its offset in PAGE_SIZE units. This is similar to, but in no way connected
+ * Each block ramdisk device has an xarray brd_pages that stores the pages
+ * containing the block device's contents. A brd page's ->index is its
+ * offset in PAGE_SIZE units. This is similar to, but in no way connected
* with, the kernel's pagecache or buffer cache (which sit above our block
* device).
*/
@@ -41,13 +41,7 @@ struct brd_device {
struct request_queue *brd_queue;
struct gendisk *brd_disk;
struct list_head brd_list;
-
- /*
- * Backing store of pages and lock to protect it. This is the contents
- * of the block device.
- */
- spinlock_t brd_lock;
- struct radix_tree_root brd_pages;
+ struct xarray brd_pages;
};
/*
@@ -62,17 +56,9 @@ static struct page *brd_lookup_page(struct brd_device *brd, sector_t sector)
* The page lifetime is protected by the fact that we have opened the
* device node -- brd pages will never be deleted under us, so we
* don't need any further locking or refcounting.
- *
- * This is strictly true for the radix-tree nodes as well (ie. we
- * don't actually need the rcu_read_lock()), however that is not a
- * documented feature of the radix-tree API so it is better to be
- * safe here (we don't have total exclusion from radix tree updates
- * here, only deletes).
*/
- rcu_read_lock();
idx = sector >> PAGE_SECTORS_SHIFT; /* sector to page index */
- page = radix_tree_lookup(&brd->brd_pages, idx);
- rcu_read_unlock();
+ page = xa_load(&brd->brd_pages, idx);
BUG_ON(page && page->index != idx);
@@ -87,7 +73,7 @@ static struct page *brd_lookup_page(struct brd_device *brd, sector_t sector)
static struct page *brd_insert_page(struct brd_device *brd, sector_t sector)
{
pgoff_t idx;
- struct page *page;
+ struct page *curr, *page;
gfp_t gfp_flags;
page = brd_lookup_page(brd, sector);
@@ -108,62 +94,36 @@ static struct page *brd_insert_page(struct brd_device *brd, sector_t sector)
if (!page)
return NULL;
- if (radix_tree_preload(GFP_NOIO)) {
- __free_page(page);
- return NULL;
- }
-
- spin_lock(&brd->brd_lock);
idx = sector >> PAGE_SECTORS_SHIFT;
page->index = idx;
- if (radix_tree_insert(&brd->brd_pages, idx, page)) {
+ curr = xa_cmpxchg(&brd->brd_pages, idx, NULL, page, GFP_NOIO);
+ if (curr) {
__free_page(page);
- page = radix_tree_lookup(&brd->brd_pages, idx);
+ page = curr;
BUG_ON(!page);
BUG_ON(page->index != idx);
}
- spin_unlock(&brd->brd_lock);
-
- radix_tree_preload_end();
return page;
}
/*
- * Free all backing store pages and radix tree. This must only be called when
+ * Free all backing store pages and xarray. This must only be called when
* there are no other users of the device.
*/
-#define FREE_BATCH 16
static void brd_free_pages(struct brd_device *brd)
{
- unsigned long pos = 0;
- struct page *pages[FREE_BATCH];
- int nr_pages;
-
- do {
- int i;
-
- nr_pages = radix_tree_gang_lookup(&brd->brd_pages,
- (void **)pages, pos, FREE_BATCH);
-
- for (i = 0; i < nr_pages; i++) {
- void *ret;
-
- BUG_ON(pages[i]->index < pos);
- pos = pages[i]->index;
- ret = radix_tree_delete(&brd->brd_pages, pos);
- BUG_ON(!ret || ret != pages[i]);
- __free_page(pages[i]);
- }
-
- pos++;
-
- /*
- * This assumes radix_tree_gang_lookup always returns as
- * many pages as possible. If the radix-tree code changes,
- * so will this have to.
- */
- } while (nr_pages == FREE_BATCH);
+ XA_STATE(xas, 0);
+ struct page *page;
+
+ /* lockdep can't know there are no other users */
+ xa_lock(&brd->brd_pages);
+ xas_for_each(&brd->brd_pages, &xas, page, ULONG_MAX) {
+ BUG_ON(page->index != xas.xa_index);
+ __free_page(page);
+ xas_store(&brd->brd_pages, &xas, NULL);
+ }
+ xa_unlock(&brd->brd_pages);
}
/*
@@ -373,8 +333,7 @@ static struct brd_device *brd_alloc(int i)
if (!brd)
goto out;
brd->brd_number = i;
- spin_lock_init(&brd->brd_lock);
- INIT_RADIX_TREE(&brd->brd_pages, GFP_ATOMIC);
+ xa_init(&brd->brd_pages);
brd->brd_queue = blk_alloc_queue(GFP_KERNEL);
if (!brd->brd_queue)
--
2.15.0
next prev parent reply other threads:[~2017-11-22 21:13 UTC|newest]
Thread overview: 79+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-11-22 21:06 [PATCH 00/62] XArray November 2017 Edition Matthew Wilcox
2017-11-22 21:06 ` [PATCH 01/62] tools: Make __test_and_clear_bit available Matthew Wilcox
2017-11-22 21:06 ` [PATCH 02/62] radix tree test suite: Remove ARRAY_SIZE Matthew Wilcox
2017-11-22 21:06 ` [PATCH 03/62] radix tree test suite: Check reclaim bit Matthew Wilcox
2017-11-22 21:06 ` [PATCH 04/62] idr test suite: Fix ida_test_random() Matthew Wilcox
2017-11-22 21:06 ` [PATCH 05/62] radix tree: Add a missing cast to gfp_t Matthew Wilcox
2017-11-22 21:28 ` Luc Van Oostenryck
2017-11-22 22:24 ` Matthew Wilcox
2017-11-22 22:35 ` Luc Van Oostenryck
2017-11-22 21:06 ` [PATCH 06/62] idr: Make cursor explicit for cyclic allocation Matthew Wilcox
2017-11-22 21:06 ` [PATCH 07/62] idr: Rewrite extended IDR API Matthew Wilcox
2017-11-22 21:06 ` [PATCH 08/62] Explicitly include radix-tree.h Matthew Wilcox
2017-11-22 21:06 ` [PATCH 09/62] arm64: Turn flush_dcache_mmap_lock into a no-op Matthew Wilcox
2017-11-22 21:06 ` [PATCH 10/62] unicore32: " Matthew Wilcox
2017-11-22 21:06 ` [PATCH 11/62] Export __set_page_dirty Matthew Wilcox
2017-11-22 21:06 ` [PATCH 12/62] xfs: Rename xa_ elements to ail_ Matthew Wilcox
2017-11-22 21:06 ` [PATCH 13/62] fscache: Use appropriate radix tree accessors Matthew Wilcox
2017-11-22 21:06 ` [PATCH 14/62] xarray: Add the xa_lock to the radix_tree_root Matthew Wilcox
2017-11-22 21:06 ` [PATCH 15/62] page cache: Use xa_lock Matthew Wilcox
2017-11-22 21:06 ` [PATCH 16/62] xarray: Replace exceptional entries Matthew Wilcox
2017-11-22 21:06 ` [PATCH 17/62] xarray: Change definition of sibling entries Matthew Wilcox
2017-11-22 21:06 ` [PATCH 18/62] xarray: Add definition of struct xarray Matthew Wilcox
2017-11-22 21:06 ` [PATCH 19/62] xarray: Define struct xa_node Matthew Wilcox
2017-11-22 21:06 ` [PATCH 20/62] xarray: Add xa_load Matthew Wilcox
2017-11-22 21:06 ` [PATCH 21/62] xarray: Add xa_get_tag, xa_set_tag and xa_clear_tag Matthew Wilcox
2017-11-22 21:06 ` [PATCH 22/62] xarray: Add xa_store Matthew Wilcox
2017-11-22 21:07 ` [PATCH 23/62] xarray: Add xa_cmpxchg Matthew Wilcox
2017-11-22 21:07 ` [PATCH 24/62] xarray: Add xa_for_each Matthew Wilcox
2017-11-22 21:07 ` [PATCH 25/62] xarray: Add xa_init Matthew Wilcox
2017-11-22 21:07 ` [PATCH 26/62] xarray: Add xas_for_each_tag Matthew Wilcox
2017-11-22 21:07 ` [PATCH 27/62] xarray: Add xa_get_entries and xa_get_tagged Matthew Wilcox
2017-11-22 21:07 ` [PATCH 28/62] xarray: Add xa_destroy Matthew Wilcox
2017-11-22 21:07 ` [PATCH 29/62] xarray: Add xas_prev_any Matthew Wilcox
2017-11-22 21:07 ` [PATCH 30/62] xarray: Add xas_find_any / xas_next_any Matthew Wilcox
2017-11-22 21:07 ` [PATCH 31/62] Convert IDR to use xarray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 32/62] ida: Convert to using xarray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 33/62] page cache: Convert page_cache_next_hole to XArray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 34/62] page cache: Use xarray for adding pages Matthew Wilcox
2017-11-22 21:07 ` [PATCH 35/62] page cache: Convert page_cache_tree_delete to xarray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 36/62] page cache: Convert find_get_entry " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 37/62] shmem: Convert replace " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 38/62] shmem: Convert shmem_confirm_swap to XArray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 39/62] shmem: Convert find_swap_entry " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 40/62] shmem: Convert shmem_tag_pins " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 41/62] shmem: Convert shmem_wait_for_pins " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 42/62] vmalloc: Convert to xarray Matthew Wilcox
2017-11-22 21:07 ` Matthew Wilcox [this message]
2017-11-22 21:07 ` [PATCH 44/62] xfs: Convert m_perag_tree to XArray Matthew Wilcox
2017-11-22 21:07 ` [PATCH 45/62] xfs: Convert pag_ici_root " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 46/62] xfs: Convert xfs dquot " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 47/62] xfs: Convert mru cache " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 48/62] block: Remove IDR preloading Matthew Wilcox
2017-11-22 21:07 ` [PATCH 49/62] rxrpc: " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 50/62] cgroup: Remove IDR wrappers Matthew Wilcox
2017-11-22 21:07 ` [PATCH 51/62] dca: Remove idr_preload calls Matthew Wilcox
2017-11-22 21:07 ` [PATCH 52/62] ipc: Remove call to idr_preload Matthew Wilcox
2017-11-22 21:07 ` [PATCH 53/62] irq: " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 54/62] scsi: Remove idr_preload in st driver Matthew Wilcox
2017-11-22 21:07 ` [PATCH 55/62] firewire: Remove call to idr_preload Matthew Wilcox
2017-11-22 21:07 ` [PATCH 56/62] drm: Remove drm_minor_lock and idr_preload Matthew Wilcox
2017-11-22 21:07 ` [PATCH 57/62] drm: Remove drm_syncobj_fd_to_handle Matthew Wilcox
2017-11-22 21:07 ` [PATCH 58/62] drm: Remove qxl driver IDR locks Matthew Wilcox
2017-11-22 21:07 ` [PATCH 59/62] drm: Replace virtio IDRs with IDAs Matthew Wilcox
2017-11-22 21:07 ` [PATCH 60/62] drm: Replace vmwgfx " Matthew Wilcox
2017-11-22 21:07 ` [PATCH 61/62] net: Redesign act_api use of IDR Matthew Wilcox
2017-11-22 21:07 ` [PATCH 62/62] mm: Convert page-writeback to XArray Matthew Wilcox
2017-11-23 1:25 ` [PATCH 00/62] XArray November 2017 Edition Dave Chinner
2017-11-23 2:46 ` Matthew Wilcox
2017-11-24 1:16 ` XArray documentation Matthew Wilcox
2017-11-24 4:30 ` Andreas Dilger
2017-11-24 17:17 ` Matthew Wilcox
2017-11-24 16:50 ` Martin Steigerwald
2017-11-24 17:03 ` Matthew Wilcox
2017-11-24 18:01 ` Martin Steigerwald
2017-11-24 19:48 ` Shakeel Butt
2017-11-24 19:56 ` Matthew Wilcox
2017-11-24 21:18 ` Matthew Wilcox
2017-11-24 22:02 ` Martin Steigerwald
2017-11-24 22:08 ` Matthew Wilcox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171122210739.29916-44-willy@infradead.org \
--to=willy@infradead.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mawilcox@microsoft.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).