^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Resizable, Scalable, Concurrent Hash Table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) /**************************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * Self Test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) **************************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <linux/init.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/jhash.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/kthread.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include <linux/rcupdate.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #include <linux/rhashtable.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include <linux/sched.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) #include <linux/random.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) #include <linux/vmalloc.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #include <linux/wait.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) #define MAX_ENTRIES 1000000
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #define TEST_INSERT_FAIL INT_MAX
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) static int parm_entries = 50000;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) module_param(parm_entries, int, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) MODULE_PARM_DESC(parm_entries, "Number of entries to add (default: 50000)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) static int runs = 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) module_param(runs, int, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) static int max_size = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) module_param(max_size, int, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) MODULE_PARM_DESC(max_size, "Maximum table size (default: calculated)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) static bool shrinking = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) module_param(shrinking, bool, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) static int size = 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) module_param(size, int, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) static int tcount = 10;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) module_param(tcount, int, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) static bool enomem_retry = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) module_param(enomem_retry, bool, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) struct test_obj_val {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) int id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) int tid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) struct test_obj {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) struct test_obj_val value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) struct rhash_head node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) struct test_obj_rhl {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) struct test_obj_val value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) struct rhlist_head list_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) struct thread_data {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) unsigned int entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) int id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) struct task_struct *task;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) struct test_obj *objs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) static u32 my_hashfn(const void *data, u32 len, u32 seed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) const struct test_obj_rhl *obj = data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) return (obj->value.id % 10);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) const struct test_obj_rhl *test_obj = obj;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) const struct test_obj_val *val = arg->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) return test_obj->value.id - val->id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) static struct rhashtable_params test_rht_params = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) .head_offset = offsetof(struct test_obj, node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) .key_offset = offsetof(struct test_obj, value),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) .key_len = sizeof(struct test_obj_val),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) .hashfn = jhash,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) static struct rhashtable_params test_rht_params_dup = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) .head_offset = offsetof(struct test_obj_rhl, list_node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) .key_offset = offsetof(struct test_obj_rhl, value),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) .key_len = sizeof(struct test_obj_val),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) .hashfn = jhash,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) .obj_hashfn = my_hashfn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) .obj_cmpfn = my_cmpfn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) .nelem_hint = 128,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) .automatic_shrinking = false,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) static atomic_t startup_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) static DECLARE_WAIT_QUEUE_HEAD(startup_wait);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) static int insert_retry(struct rhashtable *ht, struct test_obj *obj,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) const struct rhashtable_params params)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) int err, retries = -1, enomem_retries = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) retries++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) err = rhashtable_insert_fast(ht, &obj->node, params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) if (err == -ENOMEM && enomem_retry) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) enomem_retries++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) err = -EBUSY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) } while (err == -EBUSY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (enomem_retries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) pr_info(" %u insertions retried after -ENOMEM\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) enomem_retries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) return err ? : retries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) unsigned int entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) struct test_obj *obj;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) bool expected = !(i % 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) struct test_obj_val key = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) .id = i,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) if (array[i / 2].value.id == TEST_INSERT_FAIL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) expected = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) if (expected && !obj) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) pr_warn("Test failed: Could not find key %u\n", key.id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) } else if (!expected && obj) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) pr_warn("Test failed: Unexpected entry found for key %u\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) key.id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) return -EEXIST;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) } else if (expected && obj) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) if (obj->value.id != i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) obj->value.id, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) cond_resched_rcu();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) unsigned int total = 0, chain_len = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) struct rhashtable_iter hti;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) struct rhash_head *pos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) rhashtable_walk_enter(ht, &hti);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) rhashtable_walk_start(&hti);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) while ((pos = rhashtable_walk_next(&hti))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) if (PTR_ERR(pos) == -EAGAIN) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) pr_info("Info: encountered resize\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) chain_len++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) } else if (IS_ERR(pos)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) PTR_ERR(pos));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) total++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) rhashtable_walk_stop(&hti);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) rhashtable_walk_exit(&hti);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) total, atomic_read(&ht->nelems), entries, chain_len);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) if (total != atomic_read(&ht->nelems) || total != entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) pr_warn("Test failed: Total count mismatch ^^^");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) unsigned int entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) struct test_obj *obj;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) int err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) unsigned int i, insert_retries = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) s64 start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) * Insertion Test:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) * Insert entries into table with all keys even numbers
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) pr_info(" Adding %d keys\n", entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) start = ktime_get_ns();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) struct test_obj *obj = &array[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) obj->value.id = i * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) err = insert_retry(ht, obj, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) if (err > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) insert_retries += err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) else if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) if (insert_retries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) pr_info(" %u insertions retried due to memory pressure\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) insert_retries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) test_bucket_stats(ht, entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) test_rht_lookup(ht, array, entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) test_bucket_stats(ht, entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) pr_info(" Deleting %d keys\n", entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) struct test_obj_val key = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) .id = i * 2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) if (array[i].value.id != TEST_INSERT_FAIL) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) BUG_ON(!obj);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) rhashtable_remove_fast(ht, &obj->node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) end = ktime_get_ns();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) pr_info(" Duration of test: %lld ns\n", end - start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) return end - start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) static struct rhashtable ht;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) static struct rhltable rhlt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) static int __init test_rhltable(unsigned int entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) struct test_obj_rhl *rhl_test_objects;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) unsigned long *obj_in_table;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) unsigned int i, j, k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) int ret, err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) if (entries == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) entries = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) rhl_test_objects = vzalloc(array_size(entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) sizeof(*rhl_test_objects)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) if (!rhl_test_objects)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) obj_in_table = vzalloc(array_size(sizeof(unsigned long),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) BITS_TO_LONGS(entries)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) if (!obj_in_table)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) goto out_free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) err = rhltable_init(&rhlt, &test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) if (WARN_ON(err))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) goto out_free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) k = prandom_u32();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) rhl_test_objects[i].value.id = k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) if (WARN(err, "error %d on element %d\n", err, i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) set_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) ret = err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) pr_info("test %d add/delete pairs into rhlist\n", entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) struct rhlist_head *h, *pos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) struct test_obj_rhl *obj;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) struct test_obj_val key = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) .id = k,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) bool found;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) h = rhltable_lookup(&rhlt, &key, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) if (i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) j = i - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) rhl_for_each_entry_rcu(obj, pos, h, list_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) cond_resched_rcu();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) found = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) rhl_for_each_entry_rcu(obj, pos, h, list_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) if (pos == &rhl_test_objects[i].list_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) found = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) if (WARN(!found, "element %d not found", i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) clear_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) if (ret == 0 && err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) ret = err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) if (WARN(err, "error %d on element %d\n", err, i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) set_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) pr_info("test %d random rhlist add/delete operations\n", entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) for (j = 0; j < entries; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) u32 i = prandom_u32_max(entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) u32 prand = prandom_u32();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) if (prand == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) prand = prandom_u32();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) if (prand & 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) prand >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) if (test_bit(i, obj_in_table)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) clear_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) if (WARN(err, "cannot remove element at slot %d", i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) if (WARN(err != -ENOENT, "removed non-existent element %d, error %d not %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) i, err, -ENOENT))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) if (prand & 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) prand >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) if (err == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) if (prand & 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) prand >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) i = prandom_u32_max(entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) if (test_bit(i, obj_in_table)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) WARN(err, "cannot remove element at slot %d", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) clear_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) WARN(err, "failed to insert object %d", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) set_bit(i, obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) if (test_bit(i, obj_in_table)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) if (WARN(err, "cannot remove element at slot %d", i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) if (WARN(err != -ENOENT, "removed non-existent element, error %d not %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) err, -ENOENT))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) rhltable_destroy(&rhlt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) out_free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) vfree(rhl_test_objects);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) vfree(obj_in_table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) static int __init test_rhashtable_max(struct test_obj *array,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) unsigned int entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) unsigned int i, insert_retries = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) int err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) test_rht_params.max_size = roundup_pow_of_two(entries / 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) err = rhashtable_init(&ht, &test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) for (i = 0; i < ht.max_elems; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) struct test_obj *obj = &array[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) obj->value.id = i * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) err = insert_retry(&ht, obj, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) if (err > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) insert_retries += err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) else if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) if (err == -E2BIG) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) pr_info("insert element %u should have failed with %d, got %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) ht.max_elems, -E2BIG, err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) if (err == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) err = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) rhashtable_destroy(&ht);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) static unsigned int __init print_ht(struct rhltable *rhlt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) struct rhashtable *ht;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) const struct bucket_table *tbl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) char buff[512] = "";
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) unsigned int i, cnt = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) ht = &rhlt->ht;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) /* Take the mutex to avoid RCU warning */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) mutex_lock(&ht->mutex);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) tbl = rht_dereference(ht->tbl, ht);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) for (i = 0; i < tbl->size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) struct rhash_head *pos, *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) struct test_obj_rhl *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) pos = rht_ptr_exclusive(tbl->buckets + i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) if (!rht_is_a_nulls(pos)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) while (!rht_is_a_nulls(pos)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) sprintf(buff, "%s[[", buff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) pos = &list->rhead;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) list = rht_dereference(list->next, ht);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) p = rht_obj(ht, pos);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) list? ", " : " ");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) cnt++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) } while (list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) pos = next,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) next = !rht_is_a_nulls(pos) ?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) rht_dereference(pos->next, ht) : NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) mutex_unlock(&ht->mutex);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) return cnt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) int cnt, bool slow)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) struct rhltable *rhlt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) unsigned int i, ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) const char *key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) int err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) rhlt = kmalloc(sizeof(*rhlt), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) if (WARN_ON(!rhlt))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) err = rhltable_init(rhlt, &test_rht_params_dup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) if (WARN_ON(err)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) kfree(rhlt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) for (i = 0; i < cnt; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) rhl_test_objects[i].value.tid = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) key = rht_obj(&rhlt->ht, &rhl_test_objects[i].list_node.rhead);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) key += test_rht_params_dup.key_offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) if (slow) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) err = PTR_ERR(rhashtable_insert_slow(&rhlt->ht, key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) &rhl_test_objects[i].list_node.rhead));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) if (err == -EAGAIN)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) err = rhltable_insert(rhlt,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) &rhl_test_objects[i].list_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) test_rht_params_dup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) goto skip_print;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) ret = print_ht(rhlt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) skip_print:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) rhltable_destroy(rhlt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) kfree(rhlt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) static int __init test_insert_duplicates_run(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) struct test_obj_rhl rhl_test_objects[3] = {};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) pr_info("test inserting duplicates\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) /* two different values that map to same bucket */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) rhl_test_objects[0].value.id = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) rhl_test_objects[1].value.id = 21;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) /* and another duplicate with same as [0] value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) * which will be second on the bucket list */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) test_insert_dup(rhl_test_objects, 2, false);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) test_insert_dup(rhl_test_objects, 3, false);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) test_insert_dup(rhl_test_objects, 2, true);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) test_insert_dup(rhl_test_objects, 3, true);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) static int thread_lookup_test(struct thread_data *tdata)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) unsigned int entries = tdata->entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) int i, err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) for (i = 0; i < entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) struct test_obj *obj;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) struct test_obj_val key = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) .id = i,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) .tid = tdata->id,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) pr_err(" found unexpected object %d-%d\n", key.tid, key.id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) err++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) } else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) pr_err(" object %d-%d not found!\n", key.tid, key.id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) err++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) } else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) pr_err(" wrong object returned (got %d-%d, expected %d-%d)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) obj->value.tid, obj->value.id, key.tid, key.id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) err++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) static int threadfunc(void *data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) int i, step, err = 0, insert_retries = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) struct thread_data *tdata = data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) if (atomic_dec_and_test(&startup_count))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) wake_up(&startup_wait);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) if (wait_event_interruptible(startup_wait, atomic_read(&startup_count) == -1)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) pr_err(" thread[%d]: interrupted\n", tdata->id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) for (i = 0; i < tdata->entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) tdata->objs[i].value.id = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) tdata->objs[i].value.tid = tdata->id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) if (err > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) insert_retries += err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) } else if (err) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) pr_err(" thread[%d]: rhashtable_insert_fast failed\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) tdata->id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) if (insert_retries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) pr_info(" thread[%d]: %u insertions retried due to memory pressure\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) tdata->id, insert_retries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) err = thread_lookup_test(tdata);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) if (err) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) pr_err(" thread[%d]: rhashtable_lookup_test failed\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) tdata->id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) for (step = 10; step > 0; step--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) for (i = 0; i < tdata->entries; i += step) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) if (err) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) pr_err(" thread[%d]: rhashtable_remove_fast failed\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) tdata->id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) tdata->objs[i].value.id = TEST_INSERT_FAIL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) err = thread_lookup_test(tdata);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) if (err) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) pr_err(" thread[%d]: rhashtable_lookup_test (2) failed\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) tdata->id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) while (!kthread_should_stop()) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) set_current_state(TASK_INTERRUPTIBLE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) schedule();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) static int __init test_rht_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) unsigned int entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) int i, err, started_threads = 0, failed_threads = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) u64 total_time = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) struct thread_data *tdata;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) struct test_obj *objs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) if (parm_entries < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) parm_entries = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) entries = min(parm_entries, MAX_ENTRIES);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) test_rht_params.automatic_shrinking = shrinking;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) test_rht_params.nelem_hint = size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) objs = vzalloc(array_size(sizeof(struct test_obj),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) test_rht_params.max_size + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) if (!objs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) size, max_size, shrinking);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) for (i = 0; i < runs; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) s64 time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) pr_info("Test %02d:\n", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) err = rhashtable_init(&ht, &test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) if (err < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) pr_warn("Test failed: Unable to initialize hashtable: %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) time = test_rhashtable(&ht, objs, entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) rhashtable_destroy(&ht);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) if (time < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) vfree(objs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) pr_warn("Test failed: return code %lld\n", time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) total_time += time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) pr_info("test if its possible to exceed max_size %d: %s\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) "no, ok" : "YES, failed");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) vfree(objs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) do_div(total_time, runs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) pr_info("Average test time: %llu\n", total_time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) test_insert_duplicates_run();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) if (!tcount)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) pr_info("Testing concurrent rhashtable access from %d threads\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) tcount);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) atomic_set(&startup_count, tcount);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) tdata = vzalloc(array_size(tcount, sizeof(struct thread_data)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) if (!tdata)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) objs = vzalloc(array3_size(sizeof(struct test_obj), tcount, entries));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) if (!objs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) vfree(tdata);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) test_rht_params.max_size = max_size ? :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) roundup_pow_of_two(tcount * entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) err = rhashtable_init(&ht, &test_rht_params);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) if (err < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) pr_warn("Test failed: Unable to initialize hashtable: %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) vfree(tdata);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) vfree(objs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) for (i = 0; i < tcount; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) tdata[i].id = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) tdata[i].entries = entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) tdata[i].objs = objs + i * entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) tdata[i].task = kthread_run(threadfunc, &tdata[i],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) "rhashtable_thrad[%d]", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) if (IS_ERR(tdata[i].task)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) pr_err(" kthread_run failed for thread %d\n", i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) atomic_dec(&startup_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) started_threads++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) if (wait_event_interruptible(startup_wait, atomic_read(&startup_count) == 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) pr_err(" wait_event interruptible failed\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) /* count is 0 now, set it to -1 and wake up all threads together */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) atomic_dec(&startup_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) wake_up_all(&startup_wait);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) for (i = 0; i < tcount; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) if (IS_ERR(tdata[i].task))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) if ((err = kthread_stop(tdata[i].task))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) pr_warn("Test failed: thread %d returned: %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) i, err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) failed_threads++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) rhashtable_destroy(&ht);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) vfree(tdata);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) vfree(objs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) * rhltable_remove is very expensive, default values can cause test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) * to run for 2 minutes or more, use a smaller number instead.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) err = test_rhltable(entries / 16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) started_threads, failed_threads, err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) static void __exit test_rht_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) module_init(test_rht_init);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) module_exit(test_rht_exit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) MODULE_LICENSE("GPL v2");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags