if (list_empty(&node->private_list)) list_add(&shadow_nodes, &node->private_list); } else { if (!list_empty(&node->private_list)) list_del_init(&node->private_list); }} static noinline void shadow_remove(struct xarray *xa){ struct xa_node *node; xa_lock(xa); while ((node = list_first_entry_or_null(&shadow_nodes, struct xa_node, private_list))) { XA_BUG_ON(xa, node->array != xa); list_del_init(&node->private_list); xa_delete_node(node, test_update_node); } xa_unlock(xa);} static noinline void check_workingset(struct xarray *xa, unsigned long index){ XA_STATE(xas, xa, index); xas_set_update(&xas, test_update_node); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(0)); xas_next(&xas); xas_store(&xas, xa_mk_value(1)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); XA_BUG_ON(xa, list_empty(&shadow_nodes)); xas_lock(&xas); xas_next(&xas); xas_store(&xas, &xas); XA_BUG_ON(xa, !list_empty(&shadow_nodes)); xas_store(&xas, xa_mk_value(2)); xas_unlock(&xas); XA_BUG_ON(xa, list_empty(&shadow_nodes)); shadow_remove(xa); XA_BUG_ON(xa, !list_empty(&shadow_nodes)); XA_BUG_ON(xa, !xa_empty(xa));} /* * Check that the pointer / value / sibling entries are accounted the * way we expect them to be. */static noinline void check_account(struct xarray *xa){#ifdef CONFIG_XARRAY_MULTI unsigned int order; for (order = 1; order < 12; order++) { XA_STATE(xas, xa, 1 << order); xa_store_order(xa, 0, order, xa, GFP_KERNEL); rcu_read_lock(); xas_load(&xas); XA_BUG_ON(xa, xas.xa_node->count == 0); XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); XA_BUG_ON(xa, xas.xa_node->nr_values != 0); rcu_read_unlock(); xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order), GFP_KERNEL); XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); xa_erase(xa, 1 << order); XA_BUG_ON(xa, xas.xa_node->nr_values != 0); xa_erase(xa, 0); XA_BUG_ON(xa, !xa_empty(xa)); }#endif} static noinline void check_get_order(struct xarray *xa){ unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j; for (i = 0; i < 3; i++) XA_BUG_ON(xa, xa_get_order(xa, i) != 0); for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xa_store_order(xa, i << order, order, xa_mk_index(i << order), GFP_KERNEL); for (j = i << order; j < (i + 1) << order; j++) XA_BUG_ON(xa, xa_get_order(xa, j) != order); xa_erase(xa, i << order); } }} static noinline void check_xas_get_order(struct xarray *xa){ XA_STATE(xas, xa, 0); unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j; for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xas_set_order(&xas, i << order, order); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(i)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); for (j = i << order; j < (i + 1) << order; j++) { xas_set_order(&xas, j, 0); rcu_read_lock(); xas_load(&xas); XA_BUG_ON(xa, xas_get_order(&xas) != order); rcu_read_unlock(); } xas_lock(&xas); xas_set_order(&xas, i << order, order); xas_store(&xas, NULL); xas_unlock(&xas); } }} static noinline void check_xas_conflict_get_order(struct xarray *xa){ XA_STATE(xas, xa, 0); void *entry; int only_once; unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j, k; for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xas_set_order(&xas, i << order, order); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(i)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); /* * Ensure xas_get_order works with xas_for_each_conflict. */ j = i << order; for (k = 0; k < order; k++) { only_once = 0; xas_set_order(&xas, j + (1 << k), k); xas_lock(&xas); xas_for_each_conflict(&xas, entry) { XA_BUG_ON(xa, entry != xa_mk_value(i)); XA_BUG_ON(xa, xas_get_order(&xas) != order); only_once++; } XA_BUG_ON(xa, only_once != 1); xas_unlock(&xas); } if (order < max_order - 1) { only_once = 0; xas_set_order(&xas, (i & ~1UL) << order, order + 1); xas_lock(&xas); xas_for_each_conflict(&xas, entry) { XA_BUG_ON(xa, entry != xa_mk_value(i)); XA_BUG_ON(xa, xas_get_order(&xas) != order); only_once++; } XA_BUG_ON(xa, only_once != 1); xas_unlock(&xas); } xas_set_order(&xas, i << order, order); xas_lock(&xas); xas_store(&xas, NULL); xas_unlock(&xas); } }} static noinline void check_destroy(struct xarray *xa){ unsigned long index; XA_BUG_ON(xa, !xa_empty(xa)); /* Destroying an empty array is a no-op */ xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); /* Destroying an array with a single entry */ for (index = 0; index < 1000; index++) { xa_store_index(xa, index, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); } /* Destroying an array with a single entry at ULONG_MAX */ xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); #ifdef CONFIG_XARRAY_MULTI /* Destroying an array with a multi-index entry */ xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa));#endif} static DEFINE_XARRAY(array); static int xarray_checks(void){ check_xa_err(&array); check_xas_retry(&array); check_xa_load(&array); check_xa_mark(&array); check_xa_shrink(&array); check_xas_erase(&array); check_insert(&array); check_cmpxchg(&array); check_cmpxchg_order(&array); check_reserve(&array); check_reserve(&xa0); check_multi_store(&array); check_multi_store_advanced(&array); check_get_order(&array); check_xas_get_order(&array); check_xas_conflict_get_order(&array); check_xa_alloc(); check_find(&array); check_find_entry(&array); check_pause(&array); check_account(&array); check_destroy(&array); check_move(&array); check_create_range(&array); check_store_range(&array); check_store_iter(&array); check_align(&xa0); check_split(&array); check_workingset(&array, 0); check_workingset(&array, 64); check_workingset(&array, 4096); printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run == tests_passed) ? 0 : -EINVAL;} static void xarray_exit(void){} module_init(xarray_checks);module_exit(xarray_exit);MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");MODULE_DESCRIPTION("XArray API test module");MODULE_LICENSE("GPL");Lines 2001–2278 of 2278. Previous lines
if (list_empty(&node->private_list)) list_add(&shadow_nodes, &node->private_list); } else { if (!list_empty(&node->private_list)) list_del_init(&node->private_list); } } static noinline void shadow_remove(struct xarray *xa) { struct xa_node *node; xa_lock(xa); while ((node = list_first_entry_or_null(&shadow_nodes, struct xa_node, private_list))) { XA_BUG_ON(xa, node->array != xa); list_del_init(&node->private_list); xa_delete_node(node, test_update_node); } xa_unlock(xa); } static noinline void check_workingset(struct xarray *xa, unsigned long index) { XA_STATE(xas, xa, index); xas_set_update(&xas, test_update_node); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(0)); xas_next(&xas); xas_store(&xas, xa_mk_value(1)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); XA_BUG_ON(xa, list_empty(&shadow_nodes)); xas_lock(&xas); xas_next(&xas); xas_store(&xas, &xas); XA_BUG_ON(xa, !list_empty(&shadow_nodes)); xas_store(&xas, xa_mk_value(2)); xas_unlock(&xas); XA_BUG_ON(xa, list_empty(&shadow_nodes)); shadow_remove(xa); XA_BUG_ON(xa, !list_empty(&shadow_nodes)); XA_BUG_ON(xa, !xa_empty(xa)); } /* * Check that the pointer / value / sibling entries are accounted the * way we expect them to be. */ static noinline void check_account(struct xarray *xa) { #ifdef CONFIG_XARRAY_MULTI unsigned int order; for (order = 1; order < 12; order++) { XA_STATE(xas, xa, 1 << order); xa_store_order(xa, 0, order, xa, GFP_KERNEL); rcu_read_lock(); xas_load(&xas); XA_BUG_ON(xa, xas.xa_node->count == 0); XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); XA_BUG_ON(xa, xas.xa_node->nr_values != 0); rcu_read_unlock(); xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order), GFP_KERNEL); XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); xa_erase(xa, 1 << order); XA_BUG_ON(xa, xas.xa_node->nr_values != 0); xa_erase(xa, 0); XA_BUG_ON(xa, !xa_empty(xa)); } #endif } static noinline void check_get_order(struct xarray *xa) { unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j; for (i = 0; i < 3; i++) XA_BUG_ON(xa, xa_get_order(xa, i) != 0); for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xa_store_order(xa, i << order, order, xa_mk_index(i << order), GFP_KERNEL); for (j = i << order; j < (i + 1) << order; j++) XA_BUG_ON(xa, xa_get_order(xa, j) != order); xa_erase(xa, i << order); } } } static noinline void check_xas_get_order(struct xarray *xa) { XA_STATE(xas, xa, 0); unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j; for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xas_set_order(&xas, i << order, order); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(i)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); for (j = i << order; j < (i + 1) << order; j++) { xas_set_order(&xas, j, 0); rcu_read_lock(); xas_load(&xas); XA_BUG_ON(xa, xas_get_order(&xas) != order); rcu_read_unlock(); } xas_lock(&xas); xas_set_order(&xas, i << order, order); xas_store(&xas, NULL); xas_unlock(&xas); } } } static noinline void check_xas_conflict_get_order(struct xarray *xa) { XA_STATE(xas, xa, 0); void *entry; int only_once; unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; unsigned int order; unsigned long i, j, k; for (order = 0; order < max_order; order++) { for (i = 0; i < 10; i++) { xas_set_order(&xas, i << order, order); do { xas_lock(&xas); xas_store(&xas, xa_mk_value(i)); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL)); /* * Ensure xas_get_order works with xas_for_each_conflict. */ j = i << order; for (k = 0; k < order; k++) { only_once = 0; xas_set_order(&xas, j + (1 << k), k); xas_lock(&xas); xas_for_each_conflict(&xas, entry) { XA_BUG_ON(xa, entry != xa_mk_value(i)); XA_BUG_ON(xa, xas_get_order(&xas) != order); only_once++; } XA_BUG_ON(xa, only_once != 1); xas_unlock(&xas); } if (order < max_order - 1) { only_once = 0; xas_set_order(&xas, (i & ~1UL) << order, order + 1); xas_lock(&xas); xas_for_each_conflict(&xas, entry) { XA_BUG_ON(xa, entry != xa_mk_value(i)); XA_BUG_ON(xa, xas_get_order(&xas) != order); only_once++; } XA_BUG_ON(xa, only_once != 1); xas_unlock(&xas); } xas_set_order(&xas, i << order, order); xas_lock(&xas); xas_store(&xas, NULL); xas_unlock(&xas); } } } static noinline void check_destroy(struct xarray *xa) { unsigned long index; XA_BUG_ON(xa, !xa_empty(xa)); /* Destroying an empty array is a no-op */ xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); /* Destroying an array with a single entry */ for (index = 0; index < 1000; index++) { xa_store_index(xa, index, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); } /* Destroying an array with a single entry at ULONG_MAX */ xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); #ifdef CONFIG_XARRAY_MULTI /* Destroying an array with a multi-index entry */ xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); XA_BUG_ON(xa, xa_empty(xa)); xa_destroy(xa); XA_BUG_ON(xa, !xa_empty(xa)); #endif } static DEFINE_XARRAY(array); static int xarray_checks(void) { check_xa_err(&array); check_xas_retry(&array); check_xa_load(&array); check_xa_mark(&array); check_xa_shrink(&array); check_xas_erase(&array); check_insert(&array); check_cmpxchg(&array); check_cmpxchg_order(&array); check_reserve(&array); check_reserve(&xa0); check_multi_store(&array); check_multi_store_advanced(&array); check_get_order(&array); check_xas_get_order(&array); check_xas_conflict_get_order(&array); check_xa_alloc(); check_find(&array); check_find_entry(&array); check_pause(&array); check_account(&array); check_destroy(&array); check_move(&array); check_create_range(&array); check_store_range(&array); check_store_iter(&array); check_align(&xa0); check_split(&array); check_workingset(&array, 0); check_workingset(&array, 64); check_workingset(&array, 4096); printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run == tests_passed) ? 0 : -EINVAL; } static void xarray_exit(void) { } module_init(xarray_checks); module_exit(xarray_exit); MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>"); MODULE_DESCRIPTION("XArray API test module"); MODULE_LICENSE("GPL");