summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@infradead.org>2017-11-22 08:36:00 -0500
committerMatthew Wilcox <willy@infradead.org>2018-10-21 10:46:39 -0400
commite21a29552fa3f44ea41c53488875015ae70fd7f8 (patch)
tree615c10e662faa49f3910fb269d4be6d029513632
parenta12831bf4293d38518e41b80dd897af0122bb268 (diff)
shmem: Convert find_swap_entry to XArray
This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
-rw-r--r--lib/test_xarray.c56
-rw-r--r--mm/shmem.c27
-rw-r--r--tools/testing/radix-tree/main.c61
-rw-r--r--tools/testing/radix-tree/test.c22
-rw-r--r--tools/testing/radix-tree/test.h1
5 files changed, 66 insertions, 101 deletions
diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index 128c6489082f..815daffdd8c9 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -631,6 +631,61 @@ static noinline void check_find(struct xarray *xa)
check_multi_find_2(xa);
}
+/* See find_swap_entry() in mm/shmem.c */
+static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
+{
+ XA_STATE(xas, xa, 0);
+ unsigned int checked = 0;
+ void *entry;
+
+ rcu_read_lock();
+ xas_for_each(&xas, entry, ULONG_MAX) {
+ if (xas_retry(&xas, entry))
+ continue;
+ if (entry == item)
+ break;
+ checked++;
+ if ((checked % 4) != 0)
+ continue;
+ xas_pause(&xas);
+ }
+ rcu_read_unlock();
+
+ return entry ? xas.xa_index : -1;
+}
+
+static noinline void check_find_entry(struct xarray *xa)
+{
+#ifdef CONFIG_XARRAY_MULTI
+ unsigned int order;
+ unsigned long offset, index;
+
+ for (order = 0; order < 20; order++) {
+ for (offset = 0; offset < (1UL << (order + 3));
+ offset += (1UL << order)) {
+ for (index = 0; index < (1UL << (order + 5));
+ index += (1UL << order)) {
+ xa_store_order(xa, index, order,
+ xa_mk_value(index), GFP_KERNEL);
+ XA_BUG_ON(xa, xa_load(xa, index) !=
+ xa_mk_value(index));
+ XA_BUG_ON(xa, xa_find_entry(xa,
+ xa_mk_value(index)) != index);
+ }
+ XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
+ xa_destroy(xa);
+ }
+ }
+#endif
+
+ XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
+ xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
+ XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
+ XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_value(LONG_MAX)) != -1);
+ xa_erase_index(xa, ULONG_MAX);
+ XA_BUG_ON(xa, !xa_empty(xa));
+}
+
static noinline void check_move_small(struct xarray *xa, unsigned long idx)
{
XA_STATE(xas, xa, 0);
@@ -972,6 +1027,7 @@ static int xarray_checks(void)
check_multi_store(&array);
check_xa_alloc();
check_find(&array);
+ check_find_entry(&array);
check_destroy(&array);
check_move(&array);
check_create_range(&array);
diff --git a/mm/shmem.c b/mm/shmem.c
index ce91569426f3..a305529d6b89 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -1100,34 +1100,27 @@ static void shmem_evict_inode(struct inode *inode)
clear_inode(inode);
}
-static unsigned long find_swap_entry(struct radix_tree_root *root, void *item)
+static unsigned long find_swap_entry(struct xarray *xa, void *item)
{
- struct radix_tree_iter iter;
- void __rcu **slot;
- unsigned long found = -1;
+ XA_STATE(xas, xa, 0);
unsigned int checked = 0;
+ void *entry;
rcu_read_lock();
- radix_tree_for_each_slot(slot, root, &iter, 0) {
- void *entry = radix_tree_deref_slot(slot);
-
- if (radix_tree_deref_retry(entry)) {
- slot = radix_tree_iter_retry(&iter);
+ xas_for_each(&xas, entry, ULONG_MAX) {
+ if (xas_retry(&xas, entry))
continue;
- }
- if (entry == item) {
- found = iter.index;
+ if (entry == item)
break;
- }
checked++;
- if ((checked % 4096) != 0)
+ if ((checked % XA_CHECK_SCHED) != 0)
continue;
- slot = radix_tree_iter_resume(slot, &iter);
+ xas_pause(&xas);
cond_resched_rcu();
}
-
rcu_read_unlock();
- return found;
+
+ return entry ? xas.xa_index : -1;
}
/*
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 09deaf4f0959..79589ea570ab 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -236,63 +236,6 @@ void copy_tag_check(void)
item_kill_tree(&tree);
}
-static void __locate_check(struct radix_tree_root *tree, unsigned long index,
- unsigned order)
-{
- struct item *item;
- unsigned long index2;
-
- item_insert_order(tree, index, order);
- item = item_lookup(tree, index);
- index2 = find_item(tree, item);
- if (index != index2) {
- printv(2, "index %ld order %d inserted; found %ld\n",
- index, order, index2);
- abort();
- }
-}
-
-static void __order_0_locate_check(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- int i;
-
- for (i = 0; i < 50; i++)
- __locate_check(&tree, rand() % INT_MAX, 0);
-
- item_kill_tree(&tree);
-}
-
-static void locate_check(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- unsigned order;
- unsigned long offset, index;
-
- __order_0_locate_check();
-
- for (order = 0; order < 20; order++) {
- for (offset = 0; offset < (1 << (order + 3));
- offset += (1UL << order)) {
- for (index = 0; index < (1UL << (order + 5));
- index += (1UL << order)) {
- __locate_check(&tree, index + offset, order);
- }
- if (find_item(&tree, &tree) != -1)
- abort();
-
- item_kill_tree(&tree);
- }
- }
-
- if (find_item(&tree, &tree) != -1)
- abort();
- __locate_check(&tree, -1, 0);
- if (find_item(&tree, &tree) != -1)
- abort();
- item_kill_tree(&tree);
-}
-
static void single_thread_tests(bool long_run)
{
int i;
@@ -303,10 +246,6 @@ static void single_thread_tests(bool long_run)
rcu_barrier();
printv(2, "after multiorder_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
- locate_check();
- rcu_barrier();
- printv(2, "after locate_check: %d allocated, preempt %d\n",
- nr_allocated, preempt_count);
tag_check();
rcu_barrier();
printv(2, "after tag_check: %d allocated, preempt %d\n",
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 70ddf964d51c..470419bfd49d 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -209,28 +209,6 @@ int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock,
return tagged;
}
-/* Use the same pattern as find_swap_entry() in mm/shmem.c */
-unsigned long find_item(struct radix_tree_root *root, void *item)
-{
- struct radix_tree_iter iter;
- void **slot;
- unsigned long found = -1;
- unsigned long checked = 0;
-
- radix_tree_for_each_slot(slot, root, &iter, 0) {
- if (*slot == item) {
- found = iter.index;
- break;
- }
- checked++;
- if ((checked % 4) != 0)
- continue;
- slot = radix_tree_iter_resume(slot, &iter);
- }
-
- return found;
-}
-
static int verify_node(struct radix_tree_node *slot, unsigned int tag,
int tagged)
{
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index e3dc7a16f09b..9532c18c6cb1 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -32,7 +32,6 @@ void item_kill_tree(struct radix_tree_root *root);
int tag_tagged_items(struct radix_tree_root *, pthread_mutex_t *,
unsigned long start, unsigned long end, unsigned batch,
unsigned iftag, unsigned thentag);
-unsigned long find_item(struct radix_tree_root *, void *item);
void xarray_tests(void);
void tag_check(void);