| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <147230737440.10044.477174670700890206.stgit@zurg>
Date: Sat, 27 Aug 2016 17:16:21 +0300
From: Konstantin Khlebnikov <koct9i@...il.com>
To: linux-mm@...ck.org
Cc: Andrew Morton <akpm@...ux-foundation.org>,
linux-kernel@...r.kernel.org,
"Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
Ross Zwisler <ross.zwisler@...ux.intel.com>
Subject: [PATCH RFC 3/4] testing/radix-tree: replace multi-order with range
operations
This patch updates test for multi-order operations according to changes
in radix-tree: huge entry now must remember its range.
Signed-off-by: Konstantin Khlebnikov <koct9i@...il.com>
---
tools/testing/radix-tree/linux/bug.h | 2 -
tools/testing/radix-tree/linux/err.h | 31 ++++++++
tools/testing/radix-tree/linux/kernel.h | 3 +
tools/testing/radix-tree/linux/rcupdate.h | 6 ++
tools/testing/radix-tree/multiorder.c | 113 ++++++++++++++++-------------
tools/testing/radix-tree/test.c | 49 ++++++++++---
tools/testing/radix-tree/test.h | 15 ++--
7 files changed, 151 insertions(+), 68 deletions(-)
create mode 100644 tools/testing/radix-tree/linux/err.h
diff --git a/tools/testing/radix-tree/linux/bug.h b/tools/testing/radix-tree/linux/bug.h
index ccbe444977df..7a77fa971e91 100644
--- a/tools/testing/radix-tree/linux/bug.h
+++ b/tools/testing/radix-tree/linux/bug.h
@@ -1 +1 @@
-#define WARN_ON_ONCE(x) assert(x)
+#define WARN_ON_ONCE(x) assert(!(x))
diff --git a/tools/testing/radix-tree/linux/err.h b/tools/testing/radix-tree/linux/err.h
new file mode 100644
index 000000000000..6fd3e608d4d7
--- /dev/null
+++ b/tools/testing/radix-tree/linux/err.h
@@ -0,0 +1,31 @@
+#ifndef _LINUX_ERR_H
+#define _LINUX_ERR_H
+
+#define MAX_ERRNO 4095
+
+#define IS_ERR_VALUE(x) unlikely((unsigned long)(void *)(x) >= (unsigned long)-MAX_ERRNO)
+
+static inline void *ERR_PTR(long error)
+{
+ return (void *) error;
+}
+
+static inline long PTR_ERR(const void *ptr)
+{
+ return (long) ptr;
+}
+
+static inline bool IS_ERR(const void *ptr)
+{
+ return IS_ERR_VALUE((unsigned long)ptr);
+}
+
+static inline int PTR_ERR_OR_ZERO(const void *ptr)
+{
+ if (IS_ERR(ptr))
+ return PTR_ERR(ptr);
+ else
+ return 0;
+}
+
+#endif /* _LINUX_ERR_H */
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index be98a47b4e1b..52714e86991b 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -32,6 +32,9 @@
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
+#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)
+#define is_power_of_2(n) ((n) != 0 && (((n) & ((n) - 1)) == 0))
+
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
diff --git a/tools/testing/radix-tree/linux/rcupdate.h b/tools/testing/radix-tree/linux/rcupdate.h
index f7129ea2a899..8c4ae8173778 100644
--- a/tools/testing/radix-tree/linux/rcupdate.h
+++ b/tools/testing/radix-tree/linux/rcupdate.h
@@ -3,6 +3,12 @@
#include <urcu.h>
+/* urcu.h includes errno.h which undefines ERANGE */
+#ifndef ERANGE
+#define ERANGE 34
+#endif
+
+#define RCU_INIT_POINTER(p, v) rcu_assign_pointer(p, v)
#define rcu_dereference_raw(p) rcu_dereference(p)
#define rcu_dereference_protected(p, cond) rcu_dereference(p)
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 39d9b9568fe2..f73a3bfa83d8 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -29,7 +29,7 @@ static void __multiorder_tag_test(int index, int order)
unsigned long first = 0;
/* our canonical entry */
- base = index & ~((1 << order) - 1);
+ base = index;
printf("Multiorder tag test with index %d, canonical entry %d\n",
index, base);
@@ -43,7 +43,7 @@ static void __multiorder_tag_test(int index, int order)
* item_insert_order().
*/
for_each_index(i, base, order) {
- err = __radix_tree_insert(&tree, i, order,
+ err = radix_tree_insert(&tree, i,
(void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
assert(err == -EEXIST);
}
@@ -55,18 +55,18 @@ static void __multiorder_tag_test(int index, int order)
assert(radix_tree_tag_set(&tree, index, 0));
- for_each_index(i, base, order) {
- assert(radix_tree_tag_get(&tree, i, 0));
+ assert(radix_tree_tag_get(&tree, index, 0));
+
+ for_each_index(i, base, order)
assert(!radix_tree_tag_get(&tree, i, 1));
- }
assert(radix_tree_range_tag_if_tagged(&tree, &first, ~0UL, 10, 0, 1) == 1);
assert(radix_tree_tag_clear(&tree, index, 0));
- for_each_index(i, base, order) {
+ assert(radix_tree_tag_get(&tree, index, 1));
+
+ for_each_index(i, base, order)
assert(!radix_tree_tag_get(&tree, i, 0));
- assert(radix_tree_tag_get(&tree, i, 1));
- }
assert(radix_tree_tag_clear(&tree, index, 1));
@@ -122,7 +122,7 @@ static void multiorder_tag_tests(void)
static void multiorder_check(unsigned long index, int order)
{
unsigned long i;
- unsigned long min = index & ~((1UL << order) - 1);
+ unsigned long min = index;
unsigned long max = min + (1UL << order);
RADIX_TREE(tree, GFP_KERNEL);
@@ -145,7 +145,7 @@ static void multiorder_check(unsigned long index, int order)
assert(radix_tree_insert(&tree, i, entry) == -EEXIST);
}
- assert(item_delete(&tree, index) != 0);
+ assert(item_delete_order(&tree, index, order) != 0);
for (i = 0; i < 2*max; i++)
item_check_absent(&tree, i);
@@ -178,7 +178,7 @@ static void multiorder_shrink(unsigned long index, int order)
for (i = max; i < 2*max; i++)
item_check_absent(&tree, i);
- if (!item_delete(&tree, 0)) {
+ if (!item_delete_order(&tree, 0, order)) {
printf("failed to delete index %ld (order %d)\n", index, order); abort();
}
@@ -221,14 +221,12 @@ void multiorder_iteration(void)
break;
radix_tree_for_each_slot(slot, &tree, &iter, j) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
int mask = (1 << order[i]) - 1;
assert(iter.index >= (index[i] &~ mask));
assert(iter.index <= (index[i] | mask));
- assert(iter.shift == shift);
- i++;
+ if (iter.index == (index[i] | mask))
+ i++;
}
}
@@ -248,36 +246,48 @@ void multiorder_tagged_iteration(void)
#define MT_NUM_ENTRIES 9
int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7};
-
-#define TAG_ENTRIES 7
- int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
+ int tag[MT_NUM_ENTRIES] = {1, 0, 1, 1, 0, 1, 1, 1, 1};
for (i = 0; i < MT_NUM_ENTRIES; i++)
assert(!item_insert_order(&tree, index[i], order[i]));
assert(!radix_tree_tagged(&tree, 1));
- for (i = 0; i < TAG_ENTRIES; i++)
- assert(radix_tree_tag_set(&tree, tag_index[i], 1));
+ for (i = 0; i < MT_NUM_ENTRIES; i++) {
+ unsigned long end = item_order_end(index[i], order[i]);
+
+ assert(!radix_tree_tag_get(&tree, index[i], 1));
+ assert(!radix_tree_tag_get(&tree, end, 1));
+ if (tag[i])
+ assert(radix_tree_tag_set(&tree, end, 1));
+ }
+
+ for (i = 0; i < MT_NUM_ENTRIES; i++) {
+ unsigned long end = item_order_end(index[i], order[i]);
+
+ if (tag[i])
+ assert(radix_tree_tag_get(&tree, end, 1));
+ else
+ assert(!radix_tree_tag_get(&tree, end, 1));
+ }
for (j = 0; j < 256; j++) {
- int mask, k;
+ int k;
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
+ for (k = 0; k < MT_NUM_ENTRIES; k++)
+ if (tag[k] && j <= item_order_end(index[k], order[k]))
break;
- }
radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
+ unsigned long end = item_order_end(index[k], order[k]);
+
+ assert(k < MT_NUM_ENTRIES);
+ assert(radix_tree_tag_get(&tree, iter.index, 1));
+ assert(iter.index >= index[k]);
+ assert(iter.index <= end);
+ if (iter.index == end)
+ while (++k < MT_NUM_ENTRIES && !tag[k])
+ ;
}
}
@@ -285,33 +295,36 @@ void multiorder_tagged_iteration(void)
MT_NUM_ENTRIES, 1, 2);
for (j = 0; j < 256; j++) {
- int mask, k;
+ int k;
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
+ for (k = 0; k < MT_NUM_ENTRIES; k++)
+ if (tag[k] && j <= item_order_end(index[k], order[k]))
break;
- }
radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
+ unsigned long end = item_order_end(index[k], order[k]);
+
+ assert(k < MT_NUM_ENTRIES);
+ assert(radix_tree_tag_get(&tree, iter.index, 2));
+ assert(iter.index >= index[k]);
+ assert(iter.index <= end);
+ if (iter.index == end)
+ while (++k < MT_NUM_ENTRIES && !tag[k])
+ ;
}
}
- first = 1;
+ assert(!radix_tree_tagged(&tree, 0));
+
+ first = index[1];
radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
MT_NUM_ENTRIES, 1, 0);
- i = 0;
+
radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
- assert(iter.index == tag_index[i]);
- i++;
+ assert(radix_tree_tag_get(&tree, iter.index, 0));
+ assert(iter.index >= index[2]);
+ assert(iter.index <= item_order_end(index[2], order[2]));
+ break;
}
item_kill_tree(&tree);
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index a6e8099eaf4f..d6761d1a157a 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -4,6 +4,7 @@
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/bitops.h>
+#include <linux/err.h>
#include "test.h"
@@ -24,21 +25,23 @@ int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
return radix_tree_tag_get(root, index, tag);
}
-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order)
+int item_insert(struct radix_tree_root *root, unsigned long index)
{
- return __radix_tree_insert(root, item->index, order, item);
+ return radix_tree_insert(root, index, item_create(index, index));
}
-int item_insert(struct radix_tree_root *root, unsigned long index)
+unsigned long item_order_end(unsigned long index, unsigned int order)
{
- return __item_insert(root, item_create(index), 0);
+ return index + (1ul << order) - 1;
}
int item_insert_order(struct radix_tree_root *root, unsigned long index,
- unsigned order)
+ unsigned int order)
{
- return __item_insert(root, item_create(index), order);
+ unsigned long end = item_order_end(index, order);
+
+ return PTR_ERR_OR_ZERO(radix_tree_fill_range(root, index, end,
+ item_create(index, end), 0));
}
int item_delete(struct radix_tree_root *root, unsigned long index)
@@ -47,17 +50,34 @@ int item_delete(struct radix_tree_root *root, unsigned long index)
if (item) {
assert(item->index == index);
+ assert(item->end == index);
free(item);
return 1;
}
return 0;
}
-struct item *item_create(unsigned long index)
+int item_delete_order(struct radix_tree_root *root, unsigned long index,
+ unsigned int order)
+{
+ struct item *item = radix_tree_lookup(root, index);
+ unsigned long end = item_order_end(index, order);
+
+ if (item) {
+ assert(item->index == index);
+ assert(item->end == end);
+ }
+ radix_tree_truncate_range(root, index, end);
+ free(item);
+ return !!item;
+}
+
+struct item *item_create(unsigned long index, unsigned long end)
{
struct item *ret = malloc(sizeof(*ret));
ret->index = index;
+ ret->end = end;
return ret;
}
@@ -207,10 +227,17 @@ void item_kill_tree(struct radix_tree_root *root)
int i;
for (i = 0; i < nfound; i++) {
- void *ret;
+ void *item;
+
+ if (items[i]->index != items[i]->end) {
+ radix_tree_truncate_range(root, items[i]->index,
+ items[i]->end);
+ free(items[i]);
+ break;
+ }
- ret = radix_tree_delete(root, items[i]->index);
- assert(ret == items[i]);
+ item = radix_tree_delete(root, items[i]->index);
+ assert(item == items[i]);
free(items[i]);
}
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 217fb2403f09..93a6ce5e5a59 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -4,16 +4,19 @@
#include <linux/rcupdate.h>
struct item {
- unsigned long index;
+ unsigned long index, end;
};
-struct item *item_create(unsigned long index);
-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order);
+struct item *item_create(unsigned long index, unsigned long end);
int item_insert(struct radix_tree_root *root, unsigned long index);
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
- unsigned order);
int item_delete(struct radix_tree_root *root, unsigned long index);
+
+unsigned long item_order_end(unsigned long index, unsigned int order);
+int item_insert_order(struct radix_tree_root *root, unsigned long index,
+ unsigned int order);
+int item_delete_order(struct radix_tree_root *root, unsigned long index,
+ unsigned int order);
+
struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
void item_check_present(struct radix_tree_root *root, unsigned long index);
Powered by blists - more mailing lists