summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug4
-rw-r--r--lib/iov_iter.c124
-rw-r--r--lib/kunit/debugfs.c14
-rw-r--r--lib/kunit/kunit-test.c77
-rw-r--r--lib/kunit/test.c57
-rw-r--r--lib/list-test.c300
-rw-r--r--lib/maple_tree.c353
-rw-r--r--lib/test_vmalloc.c2
8 files changed, 728 insertions, 203 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index c8b379e2e9ad..39d1d93164bd 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1143,7 +1143,7 @@ menu "Scheduler Debugging"
config SCHED_DEBUG
bool "Collect scheduler debugging info"
- depends on DEBUG_KERNEL && PROC_FS
+ depends on DEBUG_KERNEL && DEBUG_FS
default y
help
If you say Y here, the /sys/kernel/debug/sched file will be provided
@@ -1392,7 +1392,7 @@ config LOCKDEP_STACK_TRACE_HASH_BITS
range 10 30
default 14
help
- Try increasing this value if you need large MAX_STACK_TRACE_ENTRIES.
+ Try increasing this value if you need large STACK_TRACE_HASH_SIZE.
config LOCKDEP_CIRCULAR_QUEUE_BITS
int "Bitsize for elements in circular_queue struct"
diff --git a/lib/iov_iter.c b/lib/iov_iter.c
index 274014e4eafe..967fba189c5f 100644
--- a/lib/iov_iter.c
+++ b/lib/iov_iter.c
@@ -126,13 +126,13 @@ __out: \
iterate_buf(i, n, base, len, off, \
i->ubuf, (I)) \
} else if (likely(iter_is_iovec(i))) { \
- const struct iovec *iov = i->iov; \
+ const struct iovec *iov = iter_iov(i); \
void __user *base; \
size_t len; \
iterate_iovec(i, n, base, len, off, \
iov, (I)) \
- i->nr_segs -= iov - i->iov; \
- i->iov = iov; \
+ i->nr_segs -= iov - iter_iov(i); \
+ i->__iov = iov; \
} else if (iov_iter_is_bvec(i)) { \
const struct bio_vec *bvec = i->bvec; \
void *base; \
@@ -355,7 +355,7 @@ size_t fault_in_iov_iter_readable(const struct iov_iter *i, size_t size)
size_t skip;
size -= count;
- for (p = i->iov, skip = i->iov_offset; count; p++, skip = 0) {
+ for (p = iter_iov(i), skip = i->iov_offset; count; p++, skip = 0) {
size_t len = min(count, p->iov_len - skip);
size_t ret;
@@ -398,7 +398,7 @@ size_t fault_in_iov_iter_writeable(const struct iov_iter *i, size_t size)
size_t skip;
size -= count;
- for (p = i->iov, skip = i->iov_offset; count; p++, skip = 0) {
+ for (p = iter_iov(i), skip = i->iov_offset; count; p++, skip = 0) {
size_t len = min(count, p->iov_len - skip);
size_t ret;
@@ -425,7 +425,7 @@ void iov_iter_init(struct iov_iter *i, unsigned int direction,
.nofault = false,
.user_backed = true,
.data_source = direction,
- .iov = iov,
+ .__iov = iov,
.nr_segs = nr_segs,
.iov_offset = 0,
.count = count
@@ -876,14 +876,14 @@ static void iov_iter_iovec_advance(struct iov_iter *i, size_t size)
i->count -= size;
size += i->iov_offset; // from beginning of current segment
- for (iov = i->iov, end = iov + i->nr_segs; iov < end; iov++) {
+ for (iov = iter_iov(i), end = iov + i->nr_segs; iov < end; iov++) {
if (likely(size < iov->iov_len))
break;
size -= iov->iov_len;
}
i->iov_offset = size;
- i->nr_segs -= iov - i->iov;
- i->iov = iov;
+ i->nr_segs -= iov - iter_iov(i);
+ i->__iov = iov;
}
void iov_iter_advance(struct iov_iter *i, size_t size)
@@ -958,12 +958,12 @@ void iov_iter_revert(struct iov_iter *i, size_t unroll)
unroll -= n;
}
} else { /* same logics for iovec and kvec */
- const struct iovec *iov = i->iov;
+ const struct iovec *iov = iter_iov(i);
while (1) {
size_t n = (--iov)->iov_len;
i->nr_segs++;
if (unroll <= n) {
- i->iov = iov;
+ i->__iov = iov;
i->iov_offset = n - unroll;
return;
}
@@ -980,7 +980,7 @@ size_t iov_iter_single_seg_count(const struct iov_iter *i)
{
if (i->nr_segs > 1) {
if (likely(iter_is_iovec(i) || iov_iter_is_kvec(i)))
- return min(i->count, i->iov->iov_len - i->iov_offset);
+ return min(i->count, iter_iov(i)->iov_len - i->iov_offset);
if (iov_iter_is_bvec(i))
return min(i->count, i->bvec->bv_len - i->iov_offset);
}
@@ -1095,13 +1095,14 @@ static bool iov_iter_aligned_iovec(const struct iov_iter *i, unsigned addr_mask,
unsigned k;
for (k = 0; k < i->nr_segs; k++, skip = 0) {
- size_t len = i->iov[k].iov_len - skip;
+ const struct iovec *iov = iter_iov(i) + k;
+ size_t len = iov->iov_len - skip;
if (len > size)
len = size;
if (len & len_mask)
return false;
- if ((unsigned long)(i->iov[k].iov_base + skip) & addr_mask)
+ if ((unsigned long)(iov->iov_base + skip) & addr_mask)
return false;
size -= len;
@@ -1194,9 +1195,10 @@ static unsigned long iov_iter_alignment_iovec(const struct iov_iter *i)
unsigned k;
for (k = 0; k < i->nr_segs; k++, skip = 0) {
- size_t len = i->iov[k].iov_len - skip;
+ const struct iovec *iov = iter_iov(i) + k;
+ size_t len = iov->iov_len - skip;
if (len) {
- res |= (unsigned long)i->iov[k].iov_base + skip;
+ res |= (unsigned long)iov->iov_base + skip;
if (len > size)
len = size;
res |= len;
@@ -1273,14 +1275,15 @@ unsigned long iov_iter_gap_alignment(const struct iov_iter *i)
return ~0U;
for (k = 0; k < i->nr_segs; k++) {
- if (i->iov[k].iov_len) {
- unsigned long base = (unsigned long)i->iov[k].iov_base;
+ const struct iovec *iov = iter_iov(i) + k;
+ if (iov->iov_len) {
+ unsigned long base = (unsigned long)iov->iov_base;
if (v) // if not the first one
res |= base | v; // this start | previous end
- v = base + i->iov[k].iov_len;
- if (size <= i->iov[k].iov_len)
+ v = base + iov->iov_len;
+ if (size <= iov->iov_len)
break;
- size -= i->iov[k].iov_len;
+ size -= iov->iov_len;
}
}
return res;
@@ -1396,13 +1399,14 @@ static unsigned long first_iovec_segment(const struct iov_iter *i, size_t *size)
return (unsigned long)i->ubuf + i->iov_offset;
for (k = 0, skip = i->iov_offset; k < i->nr_segs; k++, skip = 0) {
- size_t len = i->iov[k].iov_len - skip;
+ const struct iovec *iov = iter_iov(i) + k;
+ size_t len = iov->iov_len - skip;
if (unlikely(!len))
continue;
if (*size > len)
*size = len;
- return (unsigned long)i->iov[k].iov_base + skip;
+ return (unsigned long)iov->iov_base + skip;
}
BUG(); // if it had been empty, we wouldn't get called
}
@@ -1614,7 +1618,7 @@ static int iov_npages(const struct iov_iter *i, int maxpages)
const struct iovec *p;
int npages = 0;
- for (p = i->iov; size; skip = 0, p++) {
+ for (p = iter_iov(i); size; skip = 0, p++) {
unsigned offs = offset_in_page(p->iov_base + skip);
size_t len = min(p->iov_len - skip, size);
@@ -1691,14 +1695,14 @@ const void *dup_iter(struct iov_iter *new, struct iov_iter *old, gfp_t flags)
flags);
else if (iov_iter_is_kvec(new) || iter_is_iovec(new))
/* iovec and kvec have identical layout */
- return new->iov = kmemdup(new->iov,
+ return new->__iov = kmemdup(new->__iov,
new->nr_segs * sizeof(struct iovec),
flags);
return NULL;
}
EXPORT_SYMBOL(dup_iter);
-static int copy_compat_iovec_from_user(struct iovec *iov,
+static __noclone int copy_compat_iovec_from_user(struct iovec *iov,
const struct iovec __user *uvec, unsigned long nr_segs)
{
const struct compat_iovec __user *uiov =
@@ -1731,18 +1735,35 @@ uaccess_end:
}
static int copy_iovec_from_user(struct iovec *iov,
- const struct iovec __user *uvec, unsigned long nr_segs)
+ const struct iovec __user *uiov, unsigned long nr_segs)
{
- unsigned long seg;
+ int ret = -EFAULT;
- if (copy_from_user(iov, uvec, nr_segs * sizeof(*uvec)))
+ if (!user_access_begin(uiov, nr_segs * sizeof(*uiov)))
return -EFAULT;
- for (seg = 0; seg < nr_segs; seg++) {
- if ((ssize_t)iov[seg].iov_len < 0)
- return -EINVAL;
- }
- return 0;
+ do {
+ void __user *buf;
+ ssize_t len;
+
+ unsafe_get_user(len, &uiov->iov_len, uaccess_end);
+ unsafe_get_user(buf, &uiov->iov_base, uaccess_end);
+
+ /* check for size_t not fitting in ssize_t .. */
+ if (unlikely(len < 0)) {
+ ret = -EINVAL;
+ goto uaccess_end;
+ }
+ iov->iov_base = buf;
+ iov->iov_len = len;
+
+ uiov++; iov++;
+ } while (--nr_segs);
+
+ ret = 0;
+uaccess_end:
+ user_access_end();
+ return ret;
}
struct iovec *iovec_from_user(const struct iovec __user *uvec,
@@ -1767,7 +1788,7 @@ struct iovec *iovec_from_user(const struct iovec __user *uvec,
return ERR_PTR(-ENOMEM);
}
- if (compat)
+ if (unlikely(compat))
ret = copy_compat_iovec_from_user(iov, uvec, nr_segs);
else
ret = copy_iovec_from_user(iov, uvec, nr_segs);
@@ -1780,6 +1801,30 @@ struct iovec *iovec_from_user(const struct iovec __user *uvec,
return iov;
}
+/*
+ * Single segment iovec supplied by the user, import it as ITER_UBUF.
+ */
+static ssize_t __import_iovec_ubuf(int type, const struct iovec __user *uvec,
+ struct iovec **iovp, struct iov_iter *i,
+ bool compat)
+{
+ struct iovec *iov = *iovp;
+ ssize_t ret;
+
+ if (compat)
+ ret = copy_compat_iovec_from_user(iov, uvec, 1);
+ else
+ ret = copy_iovec_from_user(iov, uvec, 1);
+ if (unlikely(ret))
+ return ret;
+
+ ret = import_ubuf(type, iov->iov_base, iov->iov_len, i);
+ if (unlikely(ret))
+ return ret;
+ *iovp = NULL;
+ return i->count;
+}
+
ssize_t __import_iovec(int type, const struct iovec __user *uvec,
unsigned nr_segs, unsigned fast_segs, struct iovec **iovp,
struct iov_iter *i, bool compat)
@@ -1788,6 +1833,9 @@ ssize_t __import_iovec(int type, const struct iovec __user *uvec,
unsigned long seg;
struct iovec *iov;
+ if (nr_segs == 1)
+ return __import_iovec_ubuf(type, uvec, iovp, i, compat);
+
iov = iovec_from_user(uvec, nr_segs, fast_segs, *iovp, compat);
if (IS_ERR(iov)) {
*iovp = NULL;
@@ -1866,9 +1914,7 @@ int import_single_range(int rw, void __user *buf, size_t len,
if (unlikely(!access_ok(buf, len)))
return -EFAULT;
- iov->iov_base = buf;
- iov->iov_len = len;
- iov_iter_init(i, rw, iov, 1, len);
+ iov_iter_ubuf(i, rw, buf, len);
return 0;
}
EXPORT_SYMBOL(import_single_range);
@@ -1918,7 +1964,7 @@ void iov_iter_restore(struct iov_iter *i, struct iov_iter_state *state)
if (iov_iter_is_bvec(i))
i->bvec -= state->nr_segs - i->nr_segs;
else
- i->iov -= state->nr_segs - i->nr_segs;
+ i->__iov -= state->nr_segs - i->nr_segs;
i->nr_segs = state->nr_segs;
}
diff --git a/lib/kunit/debugfs.c b/lib/kunit/debugfs.c
index de0ee2e03ed6..b08bb1fba106 100644
--- a/lib/kunit/debugfs.c
+++ b/lib/kunit/debugfs.c
@@ -55,14 +55,24 @@ static int debugfs_print_results(struct seq_file *seq, void *v)
enum kunit_status success = kunit_suite_has_succeeded(suite);
struct kunit_case *test_case;
- if (!suite || !suite->log)
+ if (!suite)
return 0;
- seq_printf(seq, "%s", suite->log);
+ /* Print KTAP header so the debugfs log can be parsed as valid KTAP. */
+ seq_puts(seq, "KTAP version 1\n");
+ seq_puts(seq, "1..1\n");
+
+ /* Print suite header because it is not stored in the test logs. */
+ seq_puts(seq, KUNIT_SUBTEST_INDENT "KTAP version 1\n");
+ seq_printf(seq, KUNIT_SUBTEST_INDENT "# Subtest: %s\n", suite->name);
+ seq_printf(seq, KUNIT_SUBTEST_INDENT "1..%zd\n", kunit_suite_num_test_cases(suite));
kunit_suite_for_each_test_case(suite, test_case)
debugfs_print_result(seq, suite, test_case);
+ if (suite->log)
+ seq_printf(seq, "%s", suite->log);
+
seq_printf(seq, "%s %d %s\n",
kunit_status_to_ok_not_ok(success), 1, suite->name);
return 0;
diff --git a/lib/kunit/kunit-test.c b/lib/kunit/kunit-test.c
index 4df0335d0d06..42e44caa1bdd 100644
--- a/lib/kunit/kunit-test.c
+++ b/lib/kunit/kunit-test.c
@@ -6,6 +6,7 @@
* Author: Brendan Higgins <brendanhiggins@google.com>
*/
#include <kunit/test.h>
+#include <kunit/test-bug.h>
#include "try-catch-impl.h"
@@ -443,18 +444,6 @@ static struct kunit_suite kunit_resource_test_suite = {
.test_cases = kunit_resource_test_cases,
};
-static void kunit_log_test(struct kunit *test);
-
-static struct kunit_case kunit_log_test_cases[] = {
- KUNIT_CASE(kunit_log_test),
- {}
-};
-
-static struct kunit_suite kunit_log_test_suite = {
- .name = "kunit-log-test",
- .test_cases = kunit_log_test_cases,
-};
-
static void kunit_log_test(struct kunit *test)
{
struct kunit_suite suite;
@@ -481,6 +470,29 @@ static void kunit_log_test(struct kunit *test)
#endif
}
+static void kunit_log_newline_test(struct kunit *test)
+{
+ kunit_info(test, "Add newline\n");
+ if (test->log) {
+ KUNIT_ASSERT_NOT_NULL_MSG(test, strstr(test->log, "Add newline\n"),
+ "Missing log line, full log:\n%s", test->log);
+ KUNIT_EXPECT_NULL(test, strstr(test->log, "Add newline\n\n"));
+ } else {
+ kunit_skip(test, "only useful when debugfs is enabled");
+ }
+}
+
+static struct kunit_case kunit_log_test_cases[] = {
+ KUNIT_CASE(kunit_log_test),
+ KUNIT_CASE(kunit_log_newline_test),
+ {}
+};
+
+static struct kunit_suite kunit_log_test_suite = {
+ .name = "kunit-log-test",
+ .test_cases = kunit_log_test_cases,
+};
+
static void kunit_status_set_failure_test(struct kunit *test)
{
struct kunit fake;
@@ -521,7 +533,46 @@ static struct kunit_suite kunit_status_test_suite = {
.test_cases = kunit_status_test_cases,
};
+static void kunit_current_test(struct kunit *test)
+{
+ /* Check results of both current->kunit_test and
+ * kunit_get_current_test() are equivalent to current test.
+ */
+ KUNIT_EXPECT_PTR_EQ(test, test, current->kunit_test);
+ KUNIT_EXPECT_PTR_EQ(test, test, kunit_get_current_test());
+}
+
+static void kunit_current_fail_test(struct kunit *test)
+{
+ struct kunit fake;
+
+ kunit_init_test(&fake, "fake test", NULL);
+ KUNIT_EXPECT_EQ(test, fake.status, KUNIT_SUCCESS);
+
+ /* Set current->kunit_test to fake test. */
+ current->kunit_test = &fake;
+
+ kunit_fail_current_test("This should make `fake` test fail.");
+ KUNIT_EXPECT_EQ(test, fake.status, (enum kunit_status)KUNIT_FAILURE);
+ kunit_cleanup(&fake);
+
+ /* Reset current->kunit_test to current test. */
+ current->kunit_test = test;
+}
+
+static struct kunit_case kunit_current_test_cases[] = {
+ KUNIT_CASE(kunit_current_test),
+ KUNIT_CASE(kunit_current_fail_test),
+ {}
+};
+
+static struct kunit_suite kunit_current_test_suite = {
+ .name = "kunit_current",
+ .test_cases = kunit_current_test_cases,
+};
+
kunit_test_suites(&kunit_try_catch_test_suite, &kunit_resource_test_suite,
- &kunit_log_test_suite, &kunit_status_test_suite);
+ &kunit_log_test_suite, &kunit_status_test_suite,
+ &kunit_current_test_suite);
MODULE_LICENSE("GPL v2");
diff --git a/lib/kunit/test.c b/lib/kunit/test.c
index c9e15bb60058..e2910b261112 100644
--- a/lib/kunit/test.c
+++ b/lib/kunit/test.c
@@ -108,28 +108,51 @@ static void kunit_print_test_stats(struct kunit *test,
stats.total);
}
+/**
+ * kunit_log_newline() - Add newline to the end of log if one is not
+ * already present.
+ * @log: The log to add the newline to.
+ */
+static void kunit_log_newline(char *log)
+{
+ int log_len, len_left;
+
+ log_len = strlen(log);
+ len_left = KUNIT_LOG_SIZE - log_len - 1;
+
+ if (log_len > 0 && log[log_len - 1] != '\n')
+ strncat(log, "\n", len_left);
+}
+
/*
* Append formatted message to log, size of which is limited to
* KUNIT_LOG_SIZE bytes (including null terminating byte).
*/
void kunit_log_append(char *log, const char *fmt, ...)
{
- char line[KUNIT_LOG_SIZE];
va_list args;
- int len_left;
+ int len, log_len, len_left;
if (!log)
return;
- len_left = KUNIT_LOG_SIZE - strlen(log) - 1;
+ log_len = strlen(log);
+ len_left = KUNIT_LOG_SIZE - log_len - 1;
if (len_left <= 0)
return;
+ /* Evaluate length of line to add to log */
+ va_start(args, fmt);
+ len = vsnprintf(NULL, 0, fmt, args) + 1;
+ va_end(args);
+
+ /* Print formatted line to the log */
va_start(args, fmt);
- vsnprintf(line, sizeof(line), fmt, args);
+ vsnprintf(log + log_len, min(len, len_left), fmt, args);
va_end(args);
- strncat(log, line, len_left);
+ /* Add newline to end of log if not already present. */
+ kunit_log_newline(log);
}
EXPORT_SYMBOL_GPL(kunit_log_append);
@@ -147,10 +170,18 @@ EXPORT_SYMBOL_GPL(kunit_suite_num_test_cases);
static void kunit_print_suite_start(struct kunit_suite *suite)
{
- kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "KTAP version 1\n");
- kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "# Subtest: %s",
+ /*
+ * We do not log the test suite header as doing so would
+ * mean debugfs display would consist of the test suite
+ * header prior to individual test results.
+ * Hence directly printk the suite status, and we will
+ * separately seq_printf() the suite header for the debugfs
+ * representation.
+ */
+ pr_info(KUNIT_SUBTEST_INDENT "KTAP version 1\n");
+ pr_info(KUNIT_SUBTEST_INDENT "# Subtest: %s\n",
suite->name);
- kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "1..%zd",
+ pr_info(KUNIT_SUBTEST_INDENT "1..%zd\n",
kunit_suite_num_test_cases(suite));
}
@@ -167,10 +198,9 @@ static void kunit_print_ok_not_ok(void *test_or_suite,
/*
* We do not log the test suite results as doing so would
- * mean debugfs display would consist of the test suite
- * description and status prior to individual test results.
- * Hence directly printk the suite status, and we will
- * separately seq_printf() the suite status for the debugfs
+ * mean debugfs display would consist of an incorrect test
+ * number. Hence directly printk the suite result, and we will
+ * separately seq_printf() the suite results for the debugfs
* representation.
*/
if (suite)
@@ -437,7 +467,6 @@ static void kunit_run_case_catch_errors(struct kunit_suite *suite,
struct kunit_try_catch_context context;
struct kunit_try_catch *try_catch;
- kunit_init_test(test, test_case->name, test_case->log);
try_catch = &test->try_catch;
kunit_try_catch_init(try_catch,
@@ -533,6 +562,8 @@ int kunit_run_tests(struct kunit_suite *suite)
struct kunit_result_stats param_stats = { 0 };
test_case->status = KUNIT_SKIPPED;
+ kunit_init_test(&test, test_case->name, test_case->log);
+
if (!test_case->generate_params) {
/* Non-parameterised test. */
kunit_run_case_catch_errors(suite, test_case, &test);
diff --git a/lib/list-test.c b/lib/list-test.c
index d374cf5d1a57..0cc27de9cec8 100644
--- a/lib/list-test.c
+++ b/lib/list-test.c
@@ -8,6 +8,7 @@
#include <kunit/test.h>
#include <linux/list.h>
+#include <linux/klist.h>
struct list_test_struct {
int data;
@@ -1199,6 +1200,303 @@ static struct kunit_suite hlist_test_module = {
.test_cases = hlist_test_cases,
};
-kunit_test_suites(&list_test_module, &hlist_test_module);
+
+struct klist_test_struct {
+ int data;
+ struct klist klist;
+ struct klist_node klist_node;
+};
+
+static int node_count;
+static struct klist_node *last_node;
+
+static void check_node(struct klist_node *node_ptr)
+{
+ node_count++;
+ last_node = node_ptr;
+}
+
+static void check_delete_node(struct klist_node *node_ptr)
+{
+ node_count--;
+ last_node = node_ptr;
+}
+
+static void klist_test_add_tail(struct kunit *test)
+{
+ struct klist_node a, b;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, NULL);
+
+ klist_add_tail(&a, &mylist);
+ KUNIT_EXPECT_EQ(test, node_count, 1);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
+
+ klist_add_tail(&b, &mylist);
+ KUNIT_EXPECT_EQ(test, node_count, 2);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
+
+ /* should be [list] -> a -> b */
+ klist_iter_init(&mylist, &i);
+
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+static void klist_test_add_head(struct kunit *test)
+{
+ struct klist_node a, b;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, NULL);
+
+ klist_add_head(&a, &mylist);
+ KUNIT_EXPECT_EQ(test, node_count, 1);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
+
+ klist_add_head(&b, &mylist);
+ KUNIT_EXPECT_EQ(test, node_count, 2);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
+
+ /* should be [list] -> b -> a */
+ klist_iter_init(&mylist, &i);
+
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+static void klist_test_add_behind(struct kunit *test)
+{
+ struct klist_node a, b, c, d;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, NULL);
+
+ klist_add_head(&a, &mylist);
+ klist_add_head(&b, &mylist);
+
+ klist_add_behind(&c, &a);
+ KUNIT_EXPECT_EQ(test, node_count, 3);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
+
+ klist_add_behind(&d, &b);
+ KUNIT_EXPECT_EQ(test, node_count, 4);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
+
+ klist_iter_init(&mylist, &i);
+
+ /* should be [list] -> b -> d -> a -> c*/
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+static void klist_test_add_before(struct kunit *test)
+{
+ struct klist_node a, b, c, d;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, NULL);
+
+ klist_add_head(&a, &mylist);
+ klist_add_head(&b, &mylist);
+ klist_add_before(&c, &a);
+ KUNIT_EXPECT_EQ(test, node_count, 3);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
+
+ klist_add_before(&d, &b);
+ KUNIT_EXPECT_EQ(test, node_count, 4);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
+
+ klist_iter_init(&mylist, &i);
+
+ /* should be [list] -> b -> d -> a -> c*/
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+/*
+ * Verify that klist_del() delays the deletion of a node until there
+ * are no other references to it
+ */
+static void klist_test_del_refcount_greater_than_zero(struct kunit *test)
+{
+ struct klist_node a, b, c, d;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, &check_delete_node);
+
+ /* Add nodes a,b,c,d to the list*/
+ klist_add_tail(&a, &mylist);
+ klist_add_tail(&b, &mylist);
+ klist_add_tail(&c, &mylist);
+ klist_add_tail(&d, &mylist);
+
+ klist_iter_init(&mylist, &i);
+
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ /* Advance the iterator to point to node c*/
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
+
+ /* Try to delete node c while there is a reference to it*/
+ klist_del(&c);
+
+ /*
+ * Verify that node c is still attached to the list even after being
+ * deleted. Since the iterator still points to c, the reference count is not
+ * decreased to 0
+ */
+ KUNIT_EXPECT_TRUE(test, klist_node_attached(&c));
+
+ /* Check that node c has not been removed yet*/
+ KUNIT_EXPECT_EQ(test, node_count, 4);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
+
+ klist_iter_exit(&i);
+
+ /*
+ * Since the iterator is no longer pointing to node c, node c is removed
+ * from the list
+ */
+ KUNIT_EXPECT_EQ(test, node_count, 3);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
+
+}
+
+/*
+ * Verify that klist_del() deletes a node immediately when there are no
+ * other references to it.
+ */
+static void klist_test_del_refcount_zero(struct kunit *test)
+{
+ struct klist_node a, b, c, d;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, &check_delete_node);
+
+ /* Add nodes a,b,c,d to the list*/
+ klist_add_tail(&a, &mylist);
+ klist_add_tail(&b, &mylist);
+ klist_add_tail(&c, &mylist);
+ klist_add_tail(&d, &mylist);
+ /* Delete node c*/
+ klist_del(&c);
+
+ /* Check that node c is deleted from the list*/
+ KUNIT_EXPECT_EQ(test, node_count, 3);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
+
+ /* Should be [list] -> a -> b -> d*/
+ klist_iter_init(&mylist, &i);
+
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+static void klist_test_remove(struct kunit *test)
+{
+ /* This test doesn't check correctness under concurrent access */
+ struct klist_node a, b, c, d;
+ struct klist mylist;
+ struct klist_iter i;
+
+ node_count = 0;
+ klist_init(&mylist, &check_node, &check_delete_node);
+
+ /* Add nodes a,b,c,d to the list*/
+ klist_add_tail(&a, &mylist);
+ klist_add_tail(&b, &mylist);
+ klist_add_tail(&c, &mylist);
+ klist_add_tail(&d, &mylist);
+ /* Delete node c*/
+ klist_remove(&c);
+
+ /* Check the nodes in the list*/
+ KUNIT_EXPECT_EQ(test, node_count, 3);
+ KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
+
+ /* should be [list] -> a -> b -> d*/
+ klist_iter_init(&mylist, &i);
+
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
+ KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
+ KUNIT_EXPECT_NULL(test, klist_next(&i));
+
+ klist_iter_exit(&i);
+
+}
+
+static void klist_test_node_attached(struct kunit *test)
+{
+ struct klist_node a = {};
+ struct klist mylist;
+
+ klist_init(&mylist, NULL, NULL);
+
+ KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
+ klist_add_head(&a, &mylist);
+ KUNIT_EXPECT_TRUE(test, klist_node_attached(&a));
+ klist_del(&a);
+ KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
+
+}
+
+static struct kunit_case klist_test_cases[] = {
+ KUNIT_CASE(klist_test_add_tail),
+ KUNIT_CASE(klist_test_add_head),
+ KUNIT_CASE(klist_test_add_behind),
+ KUNIT_CASE(klist_test_add_before),
+ KUNIT_CASE(klist_test_del_refcount_greater_than_zero),
+ KUNIT_CASE(klist_test_del_refcount_zero),
+ KUNIT_CASE(klist_test_remove),
+ KUNIT_CASE(klist_test_node_attached),
+ {},
+};
+
+static struct kunit_suite klist_test_module = {
+ .name = "klist",
+ .test_cases = klist_test_cases,
+};
+
+kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module);
MODULE_LICENSE("GPL v2");
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 9e2735cbc2b4..1281a40d5735 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -185,7 +185,7 @@ static void mt_free_rcu(struct rcu_head *head)
*/
static void ma_free_rcu(struct maple_node *node)
{
- node->parent = ma_parent_ptr(node);
+ WARN_ON(node->parent != ma_parent_ptr(node));
call_rcu(&node->rcu, mt_free_rcu);
}
@@ -539,11 +539,14 @@ static inline struct maple_node *mte_parent(const struct maple_enode *enode)
*/
static inline bool ma_dead_node(const struct maple_node *node)
{
- struct maple_node *parent = (void *)((unsigned long)
- node->parent & ~MAPLE_NODE_MASK);
+ struct maple_node *parent;
+ /* Do not reorder reads from the node prior to the parent check */
+ smp_rmb();
+ parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
return (parent == node);
}
+
/*
* mte_dead_node() - check if the @enode is dead.
* @enode: The encoded maple node
@@ -555,6 +558,8 @@ static inline bool mte_dead_node(const struct maple_enode *enode)
struct maple_node *parent, *node;
node = mte_to_node(enode);
+ /* Do not reorder reads from the node prior to the parent check */
+ smp_rmb();
parent = mte_parent(enode);
return (parent == node);
}
@@ -625,6 +630,8 @@ static inline unsigned int mas_alloc_req(const struct ma_state *mas)
* @node - the maple node
* @type - the node type
*
+ * In the event of a dead node, this array may be %NULL
+ *
* Return: A pointer to the maple node pivots
*/
static inline unsigned long *ma_pivots(struct maple_node *node,
@@ -817,6 +824,11 @@ static inline void *mt_slot(const struct maple_tree *mt,
return rcu_dereference_check(slots[offset], mt_locked(mt));
}
+static inline void *mt_slot_locked(struct maple_tree *mt, void __rcu **slots,
+ unsigned char offset)
+{
+ return rcu_dereference_protected(slots[offset], mt_locked(mt));
+}
/*
* mas_slot_locked() - Get the slot value when holding the maple tree lock.
* @mas: The maple state
@@ -828,7 +840,7 @@ static inline void *mt_slot(const struct maple_tree *mt,
static inline void *mas_slot_locked(struct ma_state *mas, void __rcu **slots,
unsigned char offset)
{
- return rcu_dereference_protected(slots[offset], mt_locked(mas->tree));
+ return mt_slot_locked(mas->tree, slots, offset);
}
/*
@@ -900,6 +912,45 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
}
/*
+ * mt_clear_meta() - clear the metadata information of a node, if it exists
+ * @mt: The maple tree
+ * @mn: The maple node
+ * @type: The maple node type
+ * @offset: The offset of the highest sub-gap in this node.
+ * @end: The end of the data in this node.
+ */
+static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,
+ enum maple_type type)
+{
+ struct maple_metadata *meta;
+ unsigned long *pivots;
+ void __rcu **slots;
+ void *next;
+
+ switch (type) {
+ case maple_range_64:
+ pivots = mn->mr64.pivot;
+ if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) {
+ slots = mn->mr64.slot;
+ next = mt_slot_locked(mt, slots,
+ MAPLE_RANGE64_SLOTS - 1);
+ if (unlikely((mte_to_node(next) &&
+ mte_node_type(next))))
+ return; /* no metadata, could be node */
+ }
+ fallthrough;
+ case maple_arange_64:
+ meta = ma_meta(mn, type);
+ break;
+ default:
+ return;
+ }
+
+ meta->gap = 0;
+ meta->end = 0;
+}
+
+/*
* ma_meta_end() - Get the data end of a node from the metadata
* @mn: The maple node
* @mt: The maple node type
@@ -1096,8 +1147,11 @@ static int mas_ascend(struct ma_state *mas)
a_type = mas_parent_enum(mas, p_enode);
a_node = mte_parent(p_enode);
a_slot = mte_parent_slot(p_enode);
- pivots = ma_pivots(a_node, a_type);
a_enode = mt_mk_node(a_node, a_type);
+ pivots = ma_pivots(a_node, a_type);
+
+ if (unlikely(ma_dead_node(a_node)))
+ return 1;
if (!set_min && a_slot) {
set_min = true;
@@ -1249,26 +1303,21 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
node = mas->alloc;
node->request_count = 0;
while (requested) {
- max_req = MAPLE_ALLOC_SLOTS;
- if (node->node_count) {
- unsigned int offset = node->node_count;
-
- slots = (void **)&node->slot[offset];
- max_req -= offset;
- } else {
- slots = (void **)&node->slot;
- }
-
+ max_req = MAPLE_ALLOC_SLOTS - node->node_count;
+ slots = (void **)&node->slot[node->node_count];
max_req = min(requested, max_req);
count = mt_alloc_bulk(gfp, max_req, slots);
if (!count)
goto nomem_bulk;
+ if (node->node_count == 0) {
+ node->slot[0]->node_count = 0;
+ node->slot[0]->request_count = 0;
+ }
+
node->node_count += count;
allocated += count;
node = node->slot[0];
- node->node_count = 0;
- node->request_count = 0;
requested -= count;
}
mas->alloc->total = allocated;
@@ -1354,12 +1403,16 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
mas->max = ULONG_MAX;
mas->depth = 0;
+retry:
root = mas_root(mas);
/* Tree with nodes */
if (likely(xa_is_node(root))) {
mas->depth = 1;
mas->node = mte_safe_root(root);
mas->offset = 0;
+ if (mte_dead_node(mas->node))
+ goto retry;
+
return NULL;
}
@@ -1401,6 +1454,9 @@ static inline unsigned char ma_data_end(struct maple_node *node,
{
unsigned char offset;
+ if (!pivots)
+ return 0;
+
if (type == maple_arange_64)
return ma_meta_end(node, type);
@@ -1436,6 +1492,9 @@ static inline unsigned char mas_data_end(struct ma_state *mas)
return ma_meta_end(node, type);
pivots = ma_pivots(node, type);
+ if (unlikely(ma_dead_node(node)))
+ return 0;
+
offset = mt_pivots[type] - 1;
if (likely(!pivots[offset]))
return ma_meta_end(node, type);
@@ -1724,8 +1783,10 @@ static inline void mas_replace(struct ma_state *mas, bool advanced)
rcu_assign_pointer(slots[offset], mas->node);
}
- if (!advanced)
+ if (!advanced) {
+ mte_set_node_dead(old_enode);
mas_free(mas, old_enode);
+ }
}
/*
@@ -3659,10 +3720,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
slot++;
mas->depth = 1;
mas_set_height(mas);
-
+ ma_set_meta(node, maple_leaf_64, 0, slot);
/* swap the new root into the tree */
rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
- ma_set_meta(node, maple_leaf_64, 0, slot);
return slot;
}
@@ -3875,18 +3935,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
end = ma_data_end(node, type, pivots, max);
if (unlikely(ma_dead_node(node)))
goto dead_node;
-
- if (pivots[offset] >= mas->index)
- goto next;
-
do {
- offset++;
- } while ((offset < end) && (pivots[offset] < mas->index));
-
- if (likely(offset > end))
- max = pivots[offset];
+ if (pivots[offset] >= mas->index) {
+ max = pivots[offset];
+ break;
+ }
+ } while (++offset < end);
-next:
slots = ma_slots(node, type);
next = mt_slot(mas->tree, slots, offset);
if (unlikely(ma_dead_node(node)))
@@ -4164,6 +4219,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
done:
mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end);
if (in_rcu) {
+ mte_set_node_dead(mas->node);
mas->node = mt_mk_node(newnode, wr_mas->type);
mas_replace(mas, false);
} else {
@@ -4505,6 +4561,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
node = mas_mn(mas);
slots = ma_slots(node, mt);
pivots = ma_pivots(node, mt);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
mas->max = pivots[offset];
if (offset)
mas->min = pivots[offset - 1] + 1;
@@ -4526,6 +4585,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
slots = ma_slots(node, mt);
pivots = ma_pivots(node, mt);
offset = ma_data_end(node, mt, pivots, mas->max);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
if (offset)
mas->min = pivots[offset - 1] + 1;
@@ -4574,6 +4636,7 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
struct maple_enode *enode;
int level = 0;
unsigned char offset;
+ unsigned char node_end;
enum maple_type mt;
void __rcu **slots;
@@ -4597,7 +4660,11 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
node = mas_mn(mas);
mt = mte_node_type(mas->node);
pivots = ma_pivots(node, mt);
- } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max)));
+ node_end = ma_data_end(node, mt, pivots, mas->max);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
+ } while (unlikely(offset == node_end));
slots = ma_slots(node, mt);
pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
@@ -4613,6 +4680,9 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
mt = mte_node_type(mas->node);
slots = ma_slots(node, mt);
pivots = ma_pivots(node, mt);
+ if (unlikely(ma_dead_node(node)))
+ return 1;
+
offset = 0;
pivot = pivots[0];
}
@@ -4659,11 +4729,14 @@ static inline void *mas_next_nentry(struct ma_state *mas,
return NULL;
}
- pivots = ma_pivots(node, type);
slots = ma_slots(node, type);
- mas->index = mas_safe_min(mas, pivots, mas->offset);
+ pivots = ma_pivots(node, type);
count = ma_data_end(node, type, pivots, mas->max);
- if (ma_dead_node(node))
+ if (unlikely(ma_dead_node(node)))
+ return NULL;
+
+ mas->index = mas_safe_min(mas, pivots, mas->offset);
+ if (unlikely(ma_dead_node(node)))
return NULL;
if (mas->index > max)
@@ -4817,6 +4890,11 @@ retry:
slots = ma_slots(mn, mt);
pivots = ma_pivots(mn, mt);
+ if (unlikely(ma_dead_node(mn))) {
+ mas_rewalk(mas, index);
+ goto retry;
+ }
+
if (offset == mt_pivots[mt])
pivot = mas->max;
else
@@ -4887,7 +4965,8 @@ not_found:
* Return: True if found in a leaf, false otherwise.
*
*/
-static bool mas_rev_awalk(struct ma_state *mas, unsigned long size)
+static bool mas_rev_awalk(struct ma_state *mas, unsigned long size,
+ unsigned long *gap_min, unsigned long *gap_max)
{
enum maple_type type = mte_node_type(mas->node);
struct maple_node *node = mas_mn(mas);
@@ -4952,8 +5031,8 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size)
if (unlikely(ma_is_leaf(type))) {
mas->offset = offset;
- mas->min = min;
- mas->max = min + gap - 1;
+ *gap_min = min;
+ *gap_max = min + gap - 1;
return true;
}
@@ -4977,10 +5056,10 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
{
enum maple_type type = mte_node_type(mas->node);
unsigned long pivot, min, gap = 0;
- unsigned char offset;
- unsigned long *gaps;
- unsigned long *pivots = ma_pivots(mas_mn(mas), type);
- void __rcu **slots = ma_slots(mas_mn(mas), type);
+ unsigned char offset, data_end;
+ unsigned long *gaps, *pivots;
+ void __rcu **slots;
+ struct maple_node *node;
bool found = false;
if (ma_is_dense(type)) {
@@ -4988,13 +5067,15 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
return true;
}
- gaps = ma_gaps(mte_to_node(mas->node), type);
+ node = mas_mn(mas);
+ pivots = ma_pivots(node, type);
+ slots = ma_slots(node, type);
+ gaps = ma_gaps(node, type);
offset = mas->offset;
min = mas_safe_min(mas, pivots, offset);
- for (; offset < mt_slots[type]; offset++) {
- pivot = mas_safe_pivot(mas, pivots, offset, type);
- if (offset && !pivot)
- break;
+ data_end = ma_data_end(node, type, pivots, mas->max);
+ for (; offset <= data_end; offset++) {
+ pivot = mas_logical_pivot(mas, pivots, offset, type);
/* Not within lower bounds */
if (mas->index > pivot)
@@ -5229,6 +5310,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
unsigned long *pivots;
enum maple_type mt;
+ if (min >= max)
+ return -EINVAL;
+
if (mas_is_start(mas))
mas_start(mas);
else if (mas->offset >= 2)
@@ -5283,6 +5367,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
{
struct maple_enode *last = mas->node;
+ if (min >= max)
+ return -EINVAL;
+
if (mas_is_start(mas)) {
mas_start(mas);
mas->offset = mas_data_end(mas);
@@ -5302,7 +5389,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
mas->index = min;
mas->last = max;
- while (!mas_rev_awalk(mas, size)) {
+ while (!mas_rev_awalk(mas, size, &min, &max)) {
if (last == mas->node) {
if (!mas_rewind_node(mas))
return -EBUSY;
@@ -5317,17 +5404,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
return -EBUSY;
- /*
- * mas_rev_awalk() has set mas->min and mas->max to the gap values. If
- * the maximum is outside the window we are searching, then use the last
- * location in the search.
- * mas->max and mas->min is the range of the gap.
- * mas->index and mas->last are currently set to the search range.
- */
-
/* Trim the upper limit to the max. */
- if (mas->max <= mas->last)
- mas->last = mas->max;
+ if (max <= mas->last)
+ mas->last = max;
mas->index = mas->last - size + 1;
return 0;
@@ -5400,24 +5479,26 @@ no_gap:
}
/*
- * mas_dead_leaves() - Mark all leaves of a node as dead.
+ * mte_dead_leaves() - Mark all leaves of a node as dead.
* @mas: The maple state
* @slots: Pointer to the slot array
+ * @type: The maple node type
*
* Must hold the write lock.
*
* Return: The number of leaves marked as dead.
*/
static inline
-unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots)
+unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt,
+ void __rcu **slots)
{
struct maple_node *node;
enum maple_type type;
void *entry;
int offset;
- for (offset = 0; offset < mt_slot_count(mas->node); offset++) {
- entry = mas_slot_locked(mas, slots, offset);
+ for (offset = 0; offset < mt_slot_count(enode); offset++) {
+ entry = mt_slot(mt, slots, offset);
type = mte_node_type(entry);
node = mte_to_node(entry);
/* Use both node and type to catch LE & BE metadata */
@@ -5425,7 +5506,6 @@ unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots)
break;
mte_set_node_dead(entry);
- smp_wmb(); /* Needed for RCU */
node->type = type;
rcu_assign_pointer(slots[offset], node);
}
@@ -5433,151 +5513,160 @@ unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots)
return offset;
}
-static void __rcu **mas_dead_walk(struct ma_state *mas, unsigned char offset)
+/**
+ * mte_dead_walk() - Walk down a dead tree to just before the leaves
+ * @enode: The maple encoded node
+ * @offset: The starting offset
+ *
+ * Note: This can only be used from the RCU callback context.
+ */
+static void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset)
{
struct maple_node *node, *next;
void __rcu **slots = NULL;
- next = mas_mn(mas);
+ next = mte_to_node(*enode);
do {
- mas->node = ma_enode_ptr(next);
- node = mas_mn(mas);
+ *enode = ma_enode_ptr(next);
+ node = mte_to_node(*enode);
slots = ma_slots(node, node->type);
- next = mas_slot_locked(mas, slots, offset);
+ next = rcu_dereference_protected(slots[offset],
+ lock_is_held(&rcu_callback_map));
offset = 0;
} while (!ma_is_leaf(next->type));
return slots;
}
+/**
+ * mt_free_walk() - Walk & free a tree in the RCU callback context
+ * @head: The RCU head that's within the node.
+ *
+ * Note: This can only be used from the RCU callback context.
+ */
static void mt_free_walk(struct rcu_head *head)
{
void __rcu **slots;
struct maple_node *node, *start;
- struct maple_tree mt;
+ struct maple_enode *enode;
unsigned char offset;
enum maple_type type;
- MA_STATE(mas, &mt, 0, 0);
node = container_of(head, struct maple_node, rcu);
if (ma_is_leaf(node->type))
goto free_leaf;
- mt_init_flags(&mt, node->ma_flags);
- mas_lock(&mas);
start = node;
- mas.node = mt_mk_node(node, node->type);
- slots = mas_dead_walk(&mas, 0);
- node = mas_mn(&mas);
+ enode = mt_mk_node(node, node->type);
+ slots = mte_dead_walk(&enode, 0);
+ node = mte_to_node(enode);
do {
mt_free_bulk(node->slot_len, slots);
offset = node->parent_slot + 1;
- mas.node = node->piv_parent;
- if (mas_mn(&mas) == node)
- goto start_slots_free;
-
- type = mte_node_type(mas.node);
- slots = ma_slots(mte_to_node(mas.node), type);
- if ((offset < mt_slots[type]) && (slots[offset]))
- slots = mas_dead_walk(&mas, offset);
-
- node = mas_mn(&mas);
+ enode = node->piv_parent;
+ if (mte_to_node(enode) == node)
+ goto free_leaf;
+
+ type = mte_node_type(enode);
+ slots = ma_slots(mte_to_node(enode), type);
+ if ((offset < mt_slots[type]) &&
+ rcu_dereference_protected(slots[offset],
+ lock_is_held(&rcu_callback_map)))
+ slots = mte_dead_walk(&enode, offset);
+ node = mte_to_node(enode);
} while ((node != start) || (node->slot_len < offset));
slots = ma_slots(node, node->type);
mt_free_bulk(node->slot_len, slots);
-start_slots_free:
- mas_unlock(&mas);
free_leaf:
mt_free_rcu(&node->rcu);
}
-static inline void __rcu **mas_destroy_descend(struct ma_state *mas,
- struct maple_enode *prev, unsigned char offset)
+static inline void __rcu **mte_destroy_descend(struct maple_enode **enode,
+ struct maple_tree *mt, struct maple_enode *prev, unsigned char offset)
{
struct maple_node *node;
- struct maple_enode *next = mas->node;
+ struct maple_enode *next = *enode;
void __rcu **slots = NULL;
+ enum maple_type type;
+ unsigned char next_offset = 0;
do {
- mas->node = next;
- node = mas_mn(mas);
- slots = ma_slots(node, mte_node_type(mas->node));
- next = mas_slot_locked(mas, slots, 0);
+ *enode = next;
+ node = mte_to_node(*enode);
+ type = mte_node_type(*enode);
+ slots = ma_slots(node, type);
+ next = mt_slot_locked(mt, slots, next_offset);
if ((mte_dead_node(next)))
- next = mas_slot_locked(mas, slots, 1);
+ next = mt_slot_locked(mt, slots, ++next_offset);
- mte_set_node_dead(mas->node);
- node->type = mte_node_type(mas->node);
+ mte_set_node_dead(*enode);
+ node->type = type;
node->piv_parent = prev;
node->parent_slot = offset;
- offset = 0;
- prev = mas->node;
+ offset = next_offset;
+ next_offset = 0;
+ prev = *enode;
} while (!mte_is_leaf(next));
return slots;
}
-static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags,
+static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
bool free)
{
void __rcu **slots;
struct maple_node *node = mte_to_node(enode);
struct maple_enode *start;
- struct maple_tree mt;
- MA_STATE(mas, &mt, 0, 0);
-
- if (mte_is_leaf(enode))
+ if (mte_is_leaf(enode)) {
+ node->type = mte_node_type(enode);
goto free_leaf;
+ }
- mt_init_flags(&mt, ma_flags);
- mas_lock(&mas);
-
- mas.node = start = enode;
- slots = mas_destroy_descend(&mas, start, 0);
- node = mas_mn(&mas);
+ start = enode;
+ slots = mte_destroy_descend(&enode, mt, start, 0);
+ node = mte_to_node(enode); // Updated in the above call.
do {
enum maple_type type;
unsigned char offset;
struct maple_enode *parent, *tmp;
- node->slot_len = mas_dead_leaves(&mas, slots);
+ node->slot_len = mte_dead_leaves(enode, mt, slots);
if (free)
mt_free_bulk(node->slot_len, slots);
offset = node->parent_slot + 1;
- mas.node = node->piv_parent;
- if (mas_mn(&mas) == node)
- goto start_slots_free;
+ enode = node->piv_parent;
+ if (mte_to_node(enode) == node)
+ goto free_leaf;
- type = mte_node_type(mas.node);
- slots = ma_slots(mte_to_node(mas.node), type);
+ type = mte_node_type(enode);
+ slots = ma_slots(mte_to_node(enode), type);
if (offset >= mt_slots[type])
goto next;
- tmp = mas_slot_locked(&mas, slots, offset);
+ tmp = mt_slot_locked(mt, slots, offset);
if (mte_node_type(tmp) && mte_to_node(tmp)) {
- parent = mas.node;
- mas.node = tmp;
- slots = mas_destroy_descend(&mas, parent, offset);
+ parent = enode;
+ enode = tmp;
+ slots = mte_destroy_descend(&enode, mt, parent, offset);
}
next:
- node = mas_mn(&mas);
- } while (start != mas.node);
+ node = mte_to_node(enode);
+ } while (start != enode);
- node = mas_mn(&mas);
- node->slot_len = mas_dead_leaves(&mas, slots);
+ node = mte_to_node(enode);
+ node->slot_len = mte_dead_leaves(enode, mt, slots);
if (free)
mt_free_bulk(node->slot_len, slots);
-start_slots_free:
- mas_unlock(&mas);
-
free_leaf:
if (free)
mt_free_rcu(&node->rcu);
+ else
+ mt_clear_meta(mt, node, node->type);
}
/*
@@ -5593,10 +5682,10 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
struct maple_node *node = mte_to_node(enode);
if (mt_in_rcu(mt)) {
- mt_destroy_walk(enode, mt->ma_flags, false);
+ mt_destroy_walk(enode, mt, false);
call_rcu(&node->rcu, mt_free_walk);
} else {
- mt_destroy_walk(enode, mt->ma_flags, true);
+ mt_destroy_walk(enode, mt, true);
}
}
@@ -6617,11 +6706,11 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn,
while (likely(!ma_is_leaf(mt))) {
MT_BUG_ON(mas->tree, mte_dead_node(mas->node));
slots = ma_slots(mn, mt);
- pivots = ma_pivots(mn, mt);
- max = pivots[0];
entry = mas_slot(mas, slots, 0);
+ pivots = ma_pivots(mn, mt);
if (unlikely(ma_dead_node(mn)))
return NULL;
+ max = pivots[0];
mas->node = entry;
mn = mas_mn(mas);
mt = mte_node_type(mas->node);
@@ -6641,13 +6730,13 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn,
if (likely(entry))
return entry;
- pivots = ma_pivots(mn, mt);
- mas->index = pivots[0] + 1;
mas->offset = 1;
entry = mas_slot(mas, slots, 1);
+ pivots = ma_pivots(mn, mt);
if (unlikely(ma_dead_node(mn)))
return NULL;
+ mas->index = pivots[0] + 1;
if (mas->index > limit)
goto none;
diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c
index de4ee0d50906..cd2bdba6d3ed 100644
--- a/lib/test_vmalloc.c
+++ b/lib/test_vmalloc.c
@@ -334,7 +334,7 @@ kvfree_rcu_1_arg_vmalloc_test(void)
return -1;
p->array[0] = 'a';
- kvfree_rcu(p);
+ kvfree_rcu_mightsleep(p);
}
return 0;
generated by cgit v1.2.3 (git 2.39.0) at 2025-12-16 01:09:14 +0300