~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/test_rhashtable.c

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Resizable, Scalable, Concurrent Hash Table
  3  *
  4  * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
  5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
  6  *
  7  * Based on the following paper:
  8  * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
  9  *
 10  * Code partially derived from nft_hash
 11  *
 12  * This program is free software; you can redistribute it and/or modify
 13  * it under the terms of the GNU General Public License version 2 as
 14  * published by the Free Software Foundation.
 15  */
 16 
 17 /**************************************************************************
 18  * Self Test
 19  **************************************************************************/
 20 
 21 #include <linux/init.h>
 22 #include <linux/jhash.h>
 23 #include <linux/kernel.h>
 24 #include <linux/module.h>
 25 #include <linux/rcupdate.h>
 26 #include <linux/rhashtable.h>
 27 #include <linux/slab.h>
 28 
 29 
 30 #define TEST_HT_SIZE    8
 31 #define TEST_ENTRIES    2048
 32 #define TEST_PTR        ((void *) 0xdeadbeef)
 33 #define TEST_NEXPANDS   4
 34 
 35 struct test_obj {
 36         void                    *ptr;
 37         int                     value;
 38         struct rhash_head       node;
 39 };
 40 
 41 static int __init test_rht_lookup(struct rhashtable *ht)
 42 {
 43         unsigned int i;
 44 
 45         for (i = 0; i < TEST_ENTRIES * 2; i++) {
 46                 struct test_obj *obj;
 47                 bool expected = !(i % 2);
 48                 u32 key = i;
 49 
 50                 obj = rhashtable_lookup(ht, &key);
 51 
 52                 if (expected && !obj) {
 53                         pr_warn("Test failed: Could not find key %u\n", key);
 54                         return -ENOENT;
 55                 } else if (!expected && obj) {
 56                         pr_warn("Test failed: Unexpected entry found for key %u\n",
 57                                 key);
 58                         return -EEXIST;
 59                 } else if (expected && obj) {
 60                         if (obj->ptr != TEST_PTR || obj->value != i) {
 61                                 pr_warn("Test failed: Lookup value mismatch %p!=%p, %u!=%u\n",
 62                                         obj->ptr, TEST_PTR, obj->value, i);
 63                                 return -EINVAL;
 64                         }
 65                 }
 66         }
 67 
 68         return 0;
 69 }
 70 
 71 static void test_bucket_stats(struct rhashtable *ht, bool quiet)
 72 {
 73         unsigned int cnt, rcu_cnt, i, total = 0;
 74         struct rhash_head *pos;
 75         struct test_obj *obj;
 76         struct bucket_table *tbl;
 77 
 78         tbl = rht_dereference_rcu(ht->tbl, ht);
 79         for (i = 0; i < tbl->size; i++) {
 80                 rcu_cnt = cnt = 0;
 81 
 82                 if (!quiet)
 83                         pr_info(" [%#4x/%zu]", i, tbl->size);
 84 
 85                 rht_for_each_entry_rcu(obj, pos, tbl, i, node) {
 86                         cnt++;
 87                         total++;
 88                         if (!quiet)
 89                                 pr_cont(" [%p],", obj);
 90                 }
 91 
 92                 rht_for_each_entry_rcu(obj, pos, tbl, i, node)
 93                         rcu_cnt++;
 94 
 95                 if (rcu_cnt != cnt)
 96                         pr_warn("Test failed: Chain count mismach %d != %d",
 97                                 cnt, rcu_cnt);
 98 
 99                 if (!quiet)
100                         pr_cont("\n  [%#x] first element: %p, chain length: %u\n",
101                                 i, tbl->buckets[i], cnt);
102         }
103 
104         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d\n",
105                 total, atomic_read(&ht->nelems), TEST_ENTRIES);
106 
107         if (total != atomic_read(&ht->nelems) || total != TEST_ENTRIES)
108                 pr_warn("Test failed: Total count mismatch ^^^");
109 }
110 
111 static int __init test_rhashtable(struct rhashtable *ht)
112 {
113         struct bucket_table *tbl;
114         struct test_obj *obj;
115         struct rhash_head *pos, *next;
116         int err;
117         unsigned int i;
118 
119         /*
120          * Insertion Test:
121          * Insert TEST_ENTRIES into table with all keys even numbers
122          */
123         pr_info("  Adding %d keys\n", TEST_ENTRIES);
124         for (i = 0; i < TEST_ENTRIES; i++) {
125                 struct test_obj *obj;
126 
127                 obj = kzalloc(sizeof(*obj), GFP_KERNEL);
128                 if (!obj) {
129                         err = -ENOMEM;
130                         goto error;
131                 }
132 
133                 obj->ptr = TEST_PTR;
134                 obj->value = i * 2;
135 
136                 rhashtable_insert(ht, &obj->node);
137         }
138 
139         rcu_read_lock();
140         test_bucket_stats(ht, true);
141         test_rht_lookup(ht);
142         rcu_read_unlock();
143 
144         for (i = 0; i < TEST_NEXPANDS; i++) {
145                 pr_info("  Table expansion iteration %u...\n", i);
146                 mutex_lock(&ht->mutex);
147                 rhashtable_expand(ht);
148                 mutex_unlock(&ht->mutex);
149 
150                 rcu_read_lock();
151                 pr_info("  Verifying lookups...\n");
152                 test_rht_lookup(ht);
153                 rcu_read_unlock();
154         }
155 
156         for (i = 0; i < TEST_NEXPANDS; i++) {
157                 pr_info("  Table shrinkage iteration %u...\n", i);
158                 mutex_lock(&ht->mutex);
159                 rhashtable_shrink(ht);
160                 mutex_unlock(&ht->mutex);
161 
162                 rcu_read_lock();
163                 pr_info("  Verifying lookups...\n");
164                 test_rht_lookup(ht);
165                 rcu_read_unlock();
166         }
167 
168         rcu_read_lock();
169         test_bucket_stats(ht, true);
170         rcu_read_unlock();
171 
172         pr_info("  Deleting %d keys\n", TEST_ENTRIES);
173         for (i = 0; i < TEST_ENTRIES; i++) {
174                 u32 key = i * 2;
175 
176                 obj = rhashtable_lookup(ht, &key);
177                 BUG_ON(!obj);
178 
179                 rhashtable_remove(ht, &obj->node);
180                 kfree(obj);
181         }
182 
183         return 0;
184 
185 error:
186         tbl = rht_dereference_rcu(ht->tbl, ht);
187         for (i = 0; i < tbl->size; i++)
188                 rht_for_each_entry_safe(obj, pos, next, tbl, i, node)
189                         kfree(obj);
190 
191         return err;
192 }
193 
194 static struct rhashtable ht;
195 
196 static int __init test_rht_init(void)
197 {
198         struct rhashtable_params params = {
199                 .nelem_hint = TEST_HT_SIZE,
200                 .head_offset = offsetof(struct test_obj, node),
201                 .key_offset = offsetof(struct test_obj, value),
202                 .key_len = sizeof(int),
203                 .hashfn = jhash,
204                 .max_shift = 1, /* we expand/shrink manually here */
205                 .nulls_base = (3U << RHT_BASE_SHIFT),
206         };
207         int err;
208 
209         pr_info("Running resizable hashtable tests...\n");
210 
211         err = rhashtable_init(&ht, &params);
212         if (err < 0) {
213                 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
214                         err);
215                 return err;
216         }
217 
218         err = test_rhashtable(&ht);
219 
220         rhashtable_destroy(&ht);
221 
222         return err;
223 }
224 
225 static void __exit test_rht_exit(void)
226 {
227 }
228 
229 module_init(test_rht_init);
230 module_exit(test_rht_exit);
231 
232 MODULE_LICENSE("GPL v2");
233 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp